CS61CL Summer 2009 Homework 5

Combinational Logic and IEEE Floating Point

Due: 2009.07.23 @ 11:59pm
TA: Josh Hug <jhug@lists.berkeley.edu>

Background

Goals

This assignment will check your understanding of combinational logic and IEEE floating point.

Question 1

    a. Explain the most significant advantage(s) and disadvantage(s) (in your opinion) of using IEEE floating point vs. fixed point.
    b. Does each finite non-zero IEEE floating point number have a unique additive inverse? If so, give a brief proof. If not, give a binary counterexample.

Question 2

    a. What is the 32 bit IEEE floating point representation of the number -7,340,032?
    b. Is there any error between your IEEE floating point number and the given integer? If so, how much?

Question 3

    a. Fill in the following C function so that the float variable k contains the largest finite IEEE floating value. Do not use FLT_MAX inside of your code. Your code should be submitted (see submission details) as hw5.c. Provide the output of your code in your submitted answer.

#include <stdio.h>
#include <stdlib.h>
#include <float.h>

int main()
{
 float k=0;
 //YOUR CODE
 printf("the var k is %f\n", k);
 printf("max float is %f\n", FLT_MAX);
}

    b. What is the result when we store the result of k+k into another floating point variable (after your code has set k)?
    c. What is the smallest possible number (in IEEE floating point binary) that we can add to k and get the same behavior? Explain how your found this number.

Question 4

Consider the following circuit:


    a. Write the truth table for this network of gates.
    b. Write the simplest Sum of Products for this network.
    c. Implement the function you derived in part b with two NAND gates.

Question 5

The Wolfeschlegelsteinhausenbergerdorff brothers (A, B, and C) are always getting into fights with their nemesis Lu Xi at a local smoothie bar, and will attack him on sight. However, they also love telling stories to each other, so if all three are together, they will not attack Lu Xi.

Boolean variables A, B, and C represent the presence of the three respective brothers and variable D represents the presence of Lu Xi.

    a. Write a minimal Sum of Products expression which returns true when the Wolfeschlegelsteinhausenbergerdorff brother(s) will attack Lu Xi. (If you want a grapical method for doing this, check out Karnaugh Maps. This technique is not necessary to solve the problem, but it's arguably the easiest way).
    b. Is this minimal SOP expression unique (i.e. can you find another expression with the same number and size of products)? If so, give a short proof sketch. If not, give another minimal SOP with the same output.
    c. Now suppose that Lu Xi likes to start trouble, and that he will only enter the smoothie bar if he sees at least one of the Wolfeschlegelsteinhausenbergerdorff brothers. Logically, we can now say that we don't care about the state A'B'C'D. Give a new SOP expression which is simpler than your answer for part a, but still correct for all cases we care about.
    d. Is this new minimal SOP unique? If so, give a short proof sketch. If not, give another minimal SOP with the same output.

Question 6

    A. In this subproblem, we'll investigate what it takes to implement the product and sum of N and M terms respectively..
        i.  In terms of N, what is the minimum number of two input AND gates are needed to represent a product of N terms?
        ii. In terms of N, what is the longest path length (number of gates between input and output) needed to form a product of N terms out of two input AND gates [assuming we use the minimum number of AND gates]?
        iii. In terms of M, how many two input OR gates are needed to represent a sum of M terms?
        iv. In terms of M, what is the longest path length (number of gates between input and output) needed to form a sum of M terms out of two input OR gates [assuming we use the minimum number of OR gates]?

    B. We know that given a boolean function f, there are many possible ways to write this function. Let us define the naive Sum of Products expression as an SOP where each product corresponds to exactly one row of the truth table with output 1 (so the naive SOP for Q=A+B with two inputs would be Q=AB+A'B+AB', and the native SOP for Q=1 would be Q=AB+A'B+AB'+A'B'). Consider an arbitrary naive SOP with N inputs, and assume for this problem that we have access to inverted versions of each input. You may also assume that the maximum fan-out is 1 [i.e. each gate's output can only be used one time]. Answer the following questions in terms of N.

        0.How many variables in each product? What is the maximum possible number of products?
        i. What is the maximum possible total number of two input AND gates needed to calculate all products for our naive SOP?
        ii. What is the maximum number of two input OR gates needed to complete the implementation of our naive SOP?
        iii. Assume that each gate has a uniform delay of 1 ns.What is the maximum time it takes for a change in an input to propagate to the output?

Question 7

In Question 6, we considered non-optimized networks of gates. Of course, in the real world, we'll simplify our logic functions. In this problem, we'll analyze the optimized function case. You may again assume that we have access to all inverted inputs, and that maximum fan-out is 1.

Consider a minimal SOP expression of N inputs.
    a. What is the maximum number of terms in a given product?
    b. What is the maximum number of products? (Hint: Consider the maximum number of products for the 2 input case, 3 input case, and 4 input case. Again, Karnaugh maps are the easiest tool, but not necessary).
    c. Using your answer so far and Question 6 as a guide, what is the maximum number of two inputs gates needed to implement a minimal SOP expression of N inputs?
    d. Assuming each gate has a uniform delay of 1 ns, what is the maximum time needed for a change to propagate to the output?
    e (bonus question, not for a grade). Describe the function that requires the maximum number of gates.
    f (bonus question, not for a grade). Does the solution change if we allow fan-out of more than 1? If so, how?

We've now derived the maximum amount of resources it will take to build an arbitrary logic function, and how long it takes to compute such a function. This is the sort of analysis that lies at the heart of deciding how many transistors it's going to take to do something on a chip, as well as the maximum speed that a chip can run.

Of course in the real world, there are more exotic things to consider such as heat dissipation and gate sizing, but it's a start.

Submission Details

Create a directory named 'hw5' containing a README and any additional files needed for your submission. The README should say where to look for each question's solution. Preferably you should put all of your answers in one file. Don't forget to submit your hw5.c.

While in your directory amed hw5, run 'submit hw5'. If you included an image, make sure to say "yes" when the submit script prompts you about it. Please only submit images in the following formats: GIF, JPG, and PDF.