PROBLEM NOTES:

Carry-Lookahead Addition 2. To speed up addition it is necessary to compute the carry-out sooner. Consider the carry-out at stage n. Let gn = XnYn and pn = xn Yn. Note that both gn and pn can be computed using a half adder. Then, from the full adder Boolean formula: Cn = 9n-1 + Cn-1'Pn-1 Using the expression above, write Boolean expressions for C1, C2, C3, and C4 using repeated substitution. In other words, write an expression for C1 using the above, then write an expression for C2 and substitute your ci expression within the ca expression. Similarly, write expressions for c3 and C4 utilizing your previous C expressions. In the end, all four of your expressions should be sum-of-products expressions that only involve go...93, p....P3, and Co. Propagation Delay for the 1-bit Full Adder Recall from class that the basic building blocks for addition circuits are defined by the following Boolean functions, where x, y, and Cin denote binary inputs, s the sum output and Cout the carry output: 1-bit HALF-ADDER: S = x y, Cout = xy. This device computes the sum of two 1-bit quantities. Note that it also provides the Boolean functions and and xor. 1-bit FULL-ADDER: S=xycin, Cout=xy+Cin(xy). This device computes the sum of three 1-bit quantities. The propagation delay is the delay that accumulates along a path from a source input to an output as a result of the individual propagation delays of the components along the path. In other words, the more gates a signal has to go through to produce an output, the higher the propagation delay. For the full adder above, let's assume that passing through every single gate with up to 5 inputs takes 1 nanosecond (ns). Then the output signal s has a propagation delay of 1 ns for the single xor gate needed. The output signal cout will have a propagation delay of 3 ns: Ins to compute xOy using a 3-input xor gate, 1 ns to compute the result of xy and cin (x y ) (which can be done in parallel) using two 2-input and gates, and 1 ns to compute the or of those two signals with a 2-input or gate. Thus, the two signals s and cout will be available after 3 ns, the larger of the two propagation delays. Propagation Delay for the n-bit Full Adder To add two n-bit numbers the following tabular notation is often used: Ca-1 Ca-2 ...C2 C. O *a-1 X1-2 ...X. X. X Yn- Yn-2 ...Y: Y: Yo ------------ Con-1 SA-2...52 51 50 Each column can be implemented with a 1-bit full adder, as shown for a 4-bit adder in Figure 1. In each case the carry-in for a given stage is defined by the carry-out from the previous stage to the right. * EA EAEAEA FAO Figure 1: 4-bit Full Adder This method of implementing large adders is inefficient, since the carry-out is required to propagate through the entire system. This means the propagation delay is proportional to the number of bits in each operand. Carry-Lookahead Addition 2. To speed up addition it is necessary to compute the carry-out sooner. Consider the carry-out at stage n. Let gn = XnYn and pn = xn Yn. Note that both gn and pn can be computed using a half adder. Then, from the full adder Boolean formula: Cn = 9n-1 + Cn-1'Pn-1 Using the expression above, write Boolean expressions for C1, C2, C3, and C4 using repeated substitution. In other words, write an expression for C1 using the above, then write an expression for C2 and substitute your ci expression within the ca expression. Similarly, write expressions for c3 and C4 utilizing your previous C expressions. In the end, all four of your expressions should be sum-of-products expressions that only involve go...93, p....P3, and Co. Propagation Delay for the 1-bit Full Adder Recall from class that the basic building blocks for addition circuits are defined by the following Boolean functions, where x, y, and Cin denote binary inputs, s the sum output and Cout the carry output: 1-bit HALF-ADDER: S = x y, Cout = xy. This device computes the sum of two 1-bit quantities. Note that it also provides the Boolean functions and and xor. 1-bit FULL-ADDER: S=xycin, Cout=xy+Cin(xy). This device computes the sum of three 1-bit quantities. The propagation delay is the delay that accumulates along a path from a source input to an output as a result of the individual propagation delays of the components along the path. In other words, the more gates a signal has to go through to produce an output, the higher the propagation delay. For the full adder above, let's assume that passing through every single gate with up to 5 inputs takes 1 nanosecond (ns). Then the output signal s has a propagation delay of 1 ns for the single xor gate needed. The output signal cout will have a propagation delay of 3 ns: Ins to compute xOy using a 3-input xor gate, 1 ns to compute the result of xy and cin (x y ) (which can be done in parallel) using two 2-input and gates, and 1 ns to compute the or of those two signals with a 2-input or gate. Thus, the two signals s and cout will be available after 3 ns, the larger of the two propagation delays. Propagation Delay for the n-bit Full Adder To add two n-bit numbers the following tabular notation is often used: Ca-1 Ca-2 ...C2 C. O *a-1 X1-2 ...X. X. X Yn- Yn-2 ...Y: Y: Yo ------------ Con-1 SA-2...52 51 50 Each column can be implemented with a 1-bit full adder, as shown for a 4-bit adder in Figure 1. In each case the carry-in for a given stage is defined by the carry-out from the previous stage to the right. * EA EAEAEA FAO Figure 1: 4-bit Full Adder This method of implementing large adders is inefficient, since the carry-out is required to propagate through the entire system. This means the propagation delay is proportional to the number of bits in each operand