Design of Fast Adders
If an n-bit ripple carry adder is used in the addition /subtraction unit of Figure (3), it may have too much delay in developing its outputs, s0 through sn-1 and c n. The delay through any combinational logic network constructed from gates in a particular technology is determined by adding up the number of logic gate delays along the longest signal propagation path through the network. In the case of n-bit ripple-carry adder, the longest path is from inputs x0,y0, and c0 at the LSB position to outputs cn and sn-1 at the mostsignificant-bit(MSB) position.
Design of Carry Lookahead Adders
To reduce the computation time, there are faster ways to add two binary numbers by using carry lookahead adders. They work by creating two signals P and G known to be Carry Propagator and Carry Generator. The carry propagator is propagated to the next level whereas the carry generator is used to generate the output carry, regardless of input carry. The block diagram of a 4-bit Carry Lookahead Adder is shown here below -
Let us consider the design of a 4 bit adder is shown in figure (6). The carries can be implemented as C1=G0+P0C0
C2=G1+P1G0+P1P0C0
C3=G2+P2G1+P2P1G0+P2P1P0C0
C4=G3+P3G2+P3P1G1+P3P2P1G0+P3P2P1P0C0
Each of the carry equations can be implemented in a two-level logic network.Variables are the adder inputs and carry in to next stage
The number of gate levels for the carry propagation can be found from the circuit of full adder. The signal from input carry Cin to output carry Cout requires an AND gate and an OR gate, which constitutes two gate levels. So if there are four full adders in the parallel adder, the output carry C5 would have 2 X 4 = 8 gate levels from C1 to C5. For an n-bit parallel adder, there are 2n gate levels to propagate through..
Multiplication of Positive numbers
The usual algorithm for multiplying integers by hand is illustrated in figure7(a) for the binary system.This algorithm applies to unsigned numbers and to positive signed numbers. The product of two n-digit numbers can be accommodated in 2n digits, so the product of the 4 bit numbers in this example fits into 8 bits.
1101(13)
×1011(11)
1101
1101
0000
1101
10001111(143) Figure 7(a) Manual multiplication algorithm
Figure
Binary multiplication of positive operands can be implemented in a combinational two dimensional logic array as shown in figure7(b). The main component in each cell is a full adder FA. The AND gate in each cell determines whether a multiplicand bit mj , is added to the incoming partial product bit, based on the value of the multiplierbitqj. Each row I,where 0 ≤ I ≤ 3, adds the multiplicand to the incoming partial product, PPi to generate the outgoing partial product, PP(i+1), if qi=1. If qi=0, PPi is passed vertically downward unchanged. PP0 is all 0s, and PP4 is the desired product. The multiplicand is shifted left one position per row by the diagonal signal path.
Worst case signal propagation delay path is from the upper right corner of the array to the higher order product bit output at the bottom left corner of the array.
Sequential Circuit Binary multiplier
Registers A and Q combined hold PPi multiplier bit qi generates the signal Add/Noadd. This signal controls the addition of the multiplicand, M to PPi to genertae PP(i+1). The product is computed in n cycles. The partial product grows in length by one bit per cycle from the initial vector,PP0 of n 0s in register A. The carry-out from the adder is stored in flip-flop C, shown at the left end of register A. At the start, the multiplier is loaded into register Q, the multiplicand into register M, and C and A are cleared to 0. At the end of each cycle, C,A and Q are shifted right one bit position to allow for growth of the partial product as the multiplier is shifted out of register Q. Because of this shifting, multiplier bit qi appears at the LSB position Q to generate the Add/Noadd signal at the correct time, starting with q0 during the first cycle, q1 during the second cycle, and so on.
After they are used , the multiplier bits are discarded by the right shift operation. Note that the carry-out from the adder is the leftmost bit of PP(i+1), and must be held in the C flip-flop to be shifted right with the contents of A and Q. After n cycles, the high-order half of the product is held in register A and the low order half is in register Q.
Signed Multiplication