Problem 1. [70%] This problem explores further the iterative design scheme that you have seen earlier for n-bit binary addition. Recall that given two n-bit unsigned binary numbers, A = (an-1, ...,a0) and B = (bn-1,..., b0), we can express the usual hand algorithm for adding these two numbers as follows:
for i=0,n-1 {
ci+1 = maj(ai, bi, ci);
si = sum(ai, bi, ci);
}
where, ci, si, and ci+1 are respectively the carry-in, sum and carry-out bits of stage i, and we assume that c0 = 0.
For this problem, again, we consider two n-bit unsigned numbers A and B, as above. However, this time your task is to design an iterative comparator logic that produces three Boolean outputs: L (for A<B), G (for A>B), and E (for A=B). Carry out the design and its analysis in the following steps:
(a) Write an iterative loop for the algorithm to carry out the comparison. You will find that, unlike the binary addition that proceeds from the least significant to the most significant bit, the comparison is easier to do by proceeding in the opposite direction. That is, assume that the comparison results Li, Gi, and Ei for the binary numbers corresponding to the left prefixes (an-1,...,ai+1) and (bn-1,..., bi+1) of stage i, are available to you from prior iterations of the loop and the iterative step computes Li-1, Gi-1, and Ei-1 as Boolean functions of Li, Gi, Ei, ai and bi . Be sure to initialize these values before entering the loop.
(b) Translate the iterative algorithm to iterative logic by creating and connecting n identical cells to correspond to the algorithm. Show the iterative logic in the schematic form.
(c) Write a compact truth table for the Boolean functions Li-1, Gi-1, and Ei-1. You should try to minimize the number of rows in the compact truth table. Be sure to justify the completeness and correctness of your compact truth table.
(d) From the compact truth table in the previous step, write Boolean expressions for the three functions implemented by each cell (note that the input part of the table will have five Boolean variables Li, Gi, Ei, ai and bi .)
(e) From the Boolean expressions of the previous step, derive and show a gate-level schematic diagram for the functions implemented by each cells. Be sure to mark the primary inputs and outputs of the overall logic and to show the correct initial values of the comparison inputs to the leftmost cell.
(f) Explore an alternative implementation, based on a different way of encoding the three inputs Li, Gi, and Ei, to the cell. Notice that these three inputs are not independent, e.g., if Li =1, we know that Gi and Ei will be 0. From this observation, derive a two-bit encoding of the three original Boolean variables. Notice that this encoding will reduce the number of inputs to each cell from five to four, thus potentially leading to a simpler cell implementation. Redo the cell design in terms of your two-bit encoding and compare its literal-cost against the original implementation.
(g) Do a timing analysis of your original implementation, assuming that
1. Only uncomplemented variables are available as inputs
2. Only And, Or, and Not gates are being used
3. Each one or two input gate has a delay of one unit of time
4. Each additional input to two-input gate adds an additional unit of delay
The result of your timing analysis should be the worst-case delay for carrying out the comparison. Express this as a function of the n, the number of bits.
Problem 2. [30%] Assume A and B are two n-bit
unsigned number and you are asked to build the logic to carry out the
subtraction operation A - B. Your subtractor should produce the correct
result as long as the result is positive.
Your design should follow steps similar to the ones we used to build an
n-bit adder. That is, from the iterative scheme used for performing
binary subtraction manually, devise a schematic of the n-bit subtractor
that uses instances of a full
subtractor for each stage. Next, after
doing a few trial subtractions by hand, derive the truth table for the
full subtractor and from the truth table, write as compact SOP
expressions for the outputs as you can. From the logic
expressions, obtain a logic-gate schematic for the full subtractor.