Multiplication Division
ALU Design
The fundamental operation of the arithmetic is addition.
All others: Subtraction
are implemented in terms of it.
We need therefore an efficient implementation.
CSU22022, 5th Lecture, Dr. M. Manzke, Page: 1
N-bit Ripple-Carry-Adder (RCA) n Full Adders
An n-bit ripple-carry-adder is constructed from n full-adders
S = x y Cin Cout=XY + xCin +yCin
CSU22022, 5th Lecture, Dr. M. Manzke, Page: 2
4-bit Ripple Carry Adder
CSU22022, 5th Lecture, Dr. M. Manzke, Page: 3
RCA Equations
Si =xi yi Ci Ci+1=XiYi + xCi +yCi
Hence, using an AND+wired-OR and n-bit RCA intruduces n gate delays.
For 64 bit calculations this is too slow
CSU22022, 5th Lecture, Dr. M. Manzke, Page: 4
Carry Lookahead Boolean Expression
Ci+1 = xiyi + Ci(xi + yi)
C1 = x0y0 + C0(x0 + y0)
C2 = x1y1 + C1(x1 + y1)
= x1y1 + [x0y0 + C0(x0 + y0)](x1 + y1) with gi = xiyi Generate Carry
pi = xi + yi Carry Propagate Ci+1 = gi + piCi
CSU2022, 5th Lecture, Dr. M. Manzke, Page: 5
Ci+1 = gi + piCi
C1 = x0y0 + C0(x0 + y0) = g0 + C0p0
Carry Lookahead Boolean Expression
C2 = x1y1 + C1(x1 + y1)
= x1y1 + [x0y0 + C0(x0 + y0)](x1 + y1) = g1 + p1g0 + p0p1C0
C3 = g2 + p2g1 + p1p2g0 + p0p1p2C0
C4 = g3 + p3g2 + p2p3g1 + p1p2p3g0 + p0p1p2p3C0
CSU22022, 5th Lecture, Dr. M. Manzke, Page: 6
4-bit Carry Lookahead Adder
CSU22022, 5th Lecture, Dr. M. Manzke, Page: 7
C4 Carry Block
C4 = g3 + p3g2 + p2p3g1 + p1p2p3g0 + p0p1p2p3C0
CSU22022, 5th Lecture, Dr. M. Manzke, Page: 8
Carry Lookahead Adder
Ci+1 = gi + pigi-1 + pipi-1gi-2 + … + pipi-1…p0C0
This requires just two gate delays: One to generate gi and pi
Another to AND them Again we can use wired OR
But, it requires AND gates with a fan in of n
In practice we can only efficiently build single gates with a limited fan-in
we build the lookahead circuit as a multi-level circuit
CSU22022, 5th Lecture, Dr. M. Manzke, Page: 9
G0’ P0’
= g3 + p3g2 + p2p3g1 + p1p2p3g0 = p0p1p2p3
C4 C8
= G0’ + C0P0’
= G1’ + P1’G0’ + P0’P1’C0
C12
= G2’ + P2’G1’ + P1’P2’G0’ + P0’P1’P2’C0
Groups of Input Bits
For example, let fan-in = 4 and define:
Gi’ A carry out is generated in the ith group of four input bits Pi’ A carry out is propagated by the ith group of four input bits
CSU22022, 5th Lecture, Dr. M. Manzke, Page: 10
C4 = G0’ + C0P0’
C8 = G1’ + P1’G0’ + P0’P1’C0
CSU22022, 5th Lecture, Dr. M. Manzke, Page: 11
Generate G’’ and Propagate P’’ The next level of generate G’’ and propagate P’’
terms will cover 16 bits
G’’ = G3’ + P3’G2’ + P3’P2’G1’ + P3’P2’P1’G0 P’’ = P3’P2’P1’P0
CSU22022, 5th Lecture, Dr. M. Manzke, Page: 12
64-bit Adder Propagation Delay
We can implement a 64-bit adder using AND-or logic with a fan-in = 4 and a maximum propergation delay of:
tpmax = 3(G1’) + 2(G1’’) + 2(C48) + 2(C60) + 3(S63) = 12 gate delays
Compare this with RCA using AND-wiredOR which requires 64 gate delays.
If we add a third layer (G’’’, P’’’) we can construct a 4×64 = 256 bit adder with maximum delay:
tpmax = 3 + 2 + 2 + 2 + 2 + 2 + 3 = 16 gate delays
CSU2022, 5th Lecture, Dr. M. Manzke, Page: 13