CSU22022, 5th Lecture, Dr. M. Manzke, Page: 1
ALU Design
The fundamental operation of the arithmetic is
addition.
All others:
Subtraction
Multiplication
Division
are implemented in terms of it.
We need therefore an efficient implementation.
CSU22022, 5th Lecture, Dr. M. Manzke, Page: 2
N-bit Ripple-Carry-Adder (RCA)
n Full Adders
S = x y =XY + xCin +yCin
An n-bit ripple-carry-adder is constructed from n
full-adders
CSU22022, 5th Lecture, Dr. M. Manzke, Page: 3
4-bit Adder
CSU22022, 5th Lecture, Dr. M. Manzke, Page: 4
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
CSU2022, 5th Lecture, Dr. M. Manzke, Page: 5
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
CSU22022, 5th Lecture, Dr. M. Manzke, Page: 6
Carry Lookahead
Boolean Expression
Ci+1 = gi + piCi
C1 = x0y0 + C0(x0 + y0)
= g0 + C0p0
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: 7
4-bit Carry Lookahead Adder
CSU22022, 5th Lecture, Dr. M. Manzke, Page: 8
C4 Carry Block
C4 = g3 + p3g2 + p2p3g1 + p1p2p3g0 + p0p1p2p3C0
CSU22022, 5th Lecture, Dr. M. Manzke, Page: 9
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: 10
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
G0’ = g3 + p3g2 + p2p3g1 + p1p2p3g0
P0’ = p0p1p2p3
C4 = G0’ + C0P0’
C8 = G1’ + P1’G0’ + P0’P1’C0
C12 = G2’ + P2’G1’ + P1’P2’G0’ + P0’P1’P2’C0
CSU22022, 5th Lecture, Dr. M. Manzke, Page: 11
C4 = G0’ + C0P0’
C8 = G1’ + P1’G0’ + P0’P1’C0
CSU22022, 5th Lecture, Dr. M. Manzke, Page: 12
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
CSU2022, 5th Lecture, Dr. M. Manzke, Page: 13
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
tpmax = 3 + 2 + 2 + 2 + 2 + 2 + 3
= 16 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: