Due: | 2009.07.23 @ 11:59pm |
---|---|

TA: | Josh Hug <jhug@lists.berkeley.edu> |

This assignment will check your understanding of combinational logic and IEEE floating 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.

b. Is there any error between your IEEE floating point number and the given integer? If so, how much?

#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.

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.

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.

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

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?

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.

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.