Solution - Homework Combinatorial Logic

Question 1: Here is the truth table:

Question 2:

$CNOT(n,i)=i\cdot \overline{n}+\overline{i}\cdot n$

Question 3:

Question 4:

Question 5: The propagation time of the carry chain is easy to determine. Since the $a$ and $b$ inputs are valid at $t=0$, the $i$-th carry depends only on the incoming ($c_{i-1}$) carry. Therefore the $i$-th carry is valid at $t=i$, and the propagation time for the last (outgoing) carry is $P$.

For the sum ouput, each sum bit $s_i$ needs to wait for the incoming carry $c_i$. Adding the computation time, the propagation time for $s_i$ is $i+2$, and the last sum bit $s_{P-1}$ arrives at $P+1$.

Question 6: The basic idea of the CSA is to break the long carry chains of the carry-ripple adder. As we have seen in the previous exercise, in order to compute the sum and carry output bits, we need to wait for the incoming carry bit. In order to speed up the computation, we cut the operands in half, obtaining two parts of four bits each. For the lower part, we use a simple carry-ripple adder. For the upper part, instead of waiting for the incoming $c_4$ carry bit, we perform two computations in advance, for the two possible cases of $c_4=0$ and $c_4=1$, respectively. Then, once the actual value of $c_4$ is known, we select the correct response using a multiplexer. While this is potentially faster, we have duplicated the logic for the addition of the higher half of the operands.

Question 7: Based on the result from Question 5, the carry bits of the three adders are available at $t=4ns$, and the last sum bits at $t=5$. Adding the propagation time of the multiplexers, we obtain the overall time of 6 ns, or $P/2+2$ in the general case.