ece552_07_carry_lookahead ppt in form of

In a binary addition of two numbers (A and B), each bit generates a carry that affects the next higher bit.
A Ripple Carry Adder waits for each carry to propagate through all previous stages, causing delay.
The Carry Look-Ahead Adder (CLA) solves this by predicting carries in advance using two key signals:

Generate (G) – indicates if a bit pair will generate a carry regardless of the input carry

𝐺
𝑖
=
𝐴
𝑖
⋅
𝐵
𝑖
G
i
​

=A
i
​

⋅B
i
​


Propagate (P) – indicates if a bit pair will propagate a carry if one comes in

𝑃
𝑖
=
𝐴
𝑖
+
𝐵
𝑖
P
i
​

=A
i
​

+B
i
​

1. ECE/CS 552: Carry Lookahead
© Prof. Mikko Lipasti
Lecture notes based in part on slides created by Mark
Hill, David Wood, Guri Sohi, John Shen and Jim Smith

2. Combined Ripple-carry
Adder/Subtractor
•The above ALU is too slow
–Gate delays for add = 32 x FA + XOR ~= 64
Full
Add
er
a0
b0
Full
Add
er
a1
b1
Full
Add
er
a2
b2
Full
Add
er
a31
b31
operation
Cout
2

3. Carry Lookahead
•Theoretically, in parallel
–Sum
0 = f(c
in, a
0, b
0)
–Sum
i = f(c
in, a
i…a
0,, b
i…b
0)
–Sum
31 = f(c
in, a
31…a
0, b
31…b
0)
•Any boolean function in two levels, right?
–Wrong! Too much fan-in!
3

4. Carry Lookahead
•Need compromise
–Build tree so delay is O(log
2
n) for n bits
–E.g. 2 x 5 gate delays for 32 bits
•We will consider basic concept with
–4 bits
–16 bits
•Warning: a little convoluted
4

5. Carry Lookahead
0101 0100
0011 0110
Need:
both 1 to generate carry
one or both 1s to propagate carry
Define:g
i = a
i * b
i ## carry generate
p
i = a
i + b
i ## carry propagate
Recall: c
i+1 = a
i * b
i + a
i * c
i + b
i * c
i
= a
i * b
i + (a
i + b
i) * c
i
= g
i + p
i * c
i
5

6. Carry Lookahead
•Therefore
c
1
= g
0
+ p
0
* c
0
c
2
= g
1
+ p
1
* c
1
= g
1
+ p
1
* (g
0
+ p
0
* c
0
)
= g
1 + p
1 * g
0 + p
1 * p
0 * c
0
c
3 = g
2 + p
2 * g
1 + p
2 * p
1 * g
0 + p
2 * p
1 * p
0 * c
0
c
4
= g
3
+ p
3
*g
2
+ p
3
*p
2
*g
1
+ p
3
*p
2
*p
1
*g
0
+ p
3
*p
2
*p
1
*p
0
*c
0
•Uses one level to form p
i
and g
i
, two levels for
carry
•But, this needs n+1 fanin at the OR and the
rightmost AND
6

7. 4-bit Carry Lookahead Adder
p3 g3a3 b3
s3
c3
p2 g2 a2 b2
s2
c2
p1 g1 a1 b1
s1
c1
p0 g0 a0 b0
s0
c0
Carry Lookahead Block
c0
c4
7

8. Hierarchical Carry Lookahead
for 16 bits
P Ga,b12-15
s12-15
c12
P G a,b8-11
s8-11
c8
P G a4-7b4-7
s4-7
c4
P G a0-3b0-3
s0-3
c0
Carry Lookahead Block
c0
c15
8

9. Hierarchical CLA for 16 bits
Build 16-bit adder from four 4-bit adders
Figure out G and P for 4 bits together
G
0,3 = g
3 + p
3 * g
2 + p
3 * p
2 * g
1 + p
3 * p
2 * p
1 * g
0
P
0,3
= p
3
* p
2
* p
1
* p
0
(Notation a little different from the book)
G
4,7
= g
7
+ p
7
* g
6
+ p
7
* p
6
* g
5
+ p
7
* p
6
* p
5
* g
4
P
4,7 = p
7 * p
6* p
5 * p
4
G
12,15 = g
15 + p
15 * g
14 + p
15* p
14 * g
13 + p
15 * p
14 * p
13 * g
12
P
12,15
= p
15
* p
14
* p
13
* p
12
9

10. Carry Lookahead Basics
Fill in the holes in the G’s and P’s
G
i, k = G
j+1,k + P
j+1, k * G
i,j (assume i < j +1 < k )
P
i,k
= P
i,j
* P
j+1, k
G
0,7 = G
4,7 + P
4,7 * G
0,3 P
0,7 = P
0,3* P
4,7
G
8,15
= G
12,15
+ P
12,15
* G
8,11
P
8,15
= P
8,11
* P
12, 15
G
0,15 = G
8,15 + P
8,15 * G
0,7 P
0,15 = P
0,7 * P
8, 15
10

11. CLA: Compute G’s and P’s
G0,7
P0,7
G8,15
P8,15
G0,15
P0,15
G12,15
P12,15
G8,11
P8,11
G4,7
P4,7
G0,3
P0,3
11

12. CLA: Compute Carries
G0,3
P0,3
G8,11
P8,11
G0,7
P0,7
c8
c12
c8
g12 - g15
p12 - p15
c4 c0
g8 - g11
p8 - p11
g4 - g7
p4 - p7
g0 - g3
p0 - p3
c0
c0
12

13. Other Adders: Carry Select
•Two adds in parallel; with and without c
in
–When C
in is done, select correct result
0
1
c
0
2-1 Mux
Full Adder
Full Adder
Full Adder
select
next
select
13

14. Other Adders: Carry Save
A + B => S
Save carries A + B => S, C
out
Use C
in
A + B + C => S1, S2 (3# to 2# in parallel)
Used in combinational multipliers by building a
Wallace Tree
c b
a
c
s
CSA
14
7 9
+ 1 8
C,S 0,81,7
Final8+1=9 7

15. Adding Up Many Bits
CSA CSA
CSA
CSA
S
0
S
1S
2
abcdef
15

16. Summary
•Carry lookahead
•Carry-select, Carry-save
•State of the art: parallel prefix adders
–aka. Brent-Kung, Kogge-Stone, …
–Generalization of CLA
–Physical design (e.g. wiring) of primary concern
–Covered in ECE 555
16