Understanding Carry Look-Ahead Adders in Digital Systems

Slide Note

Explore the concept of Carry Look-Ahead Adders in digital system fundamentals. Learn how to optimize the carry chain, implement Partial Full Adders, and enhance speed by flattening carry logic. Dive into the mathematics behind Ripple-Carry Adders and Carry Look-Ahead Adders, unraveling multi-level functions and two-level functions for carry bits. Discover the algebraic approach to flattening ripple-carry equations for improved efficiency in adder circuits.

tom_the Follow

Uploaded on Oct 02, 2024 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

E N D

Presentation Transcript

ECE 352 Digital System Fundamentals Carry Look-Ahead Adders Carry Look-Ahead Adders 1 1 1

Optimize The Slow Part: Carry Chain For big adders, the carry chain is very long Separate the carry and sum logic in a full adder so that we can optimize the carry logic Partial Full Adder (PFA): a full adder without carry logic Modify the carry-chain logic to be a 2-level function instead of a multi-level function Carry Look-Ahead Adders A B Carry Chain Cout Cin G P Cin Cout Cin PFA A B S S 2 2 2

Carry Look-Ahead Adder (CLA) As usual, can trade area/power for speed Multi-level logic (ripple carry) reduces area Flattening carry logic increases speed Make carry logic a 2-level function of: Generate (G) Based on the operand values at just this bit position, will the carry-out for this position be 1 regardless of the carry-in? Propagate (P) Based on the operand values at just this bit position, will the carry-out for this position be equal to the carry-in? Carry Look-Ahead Adders 3 3 3

Ripple-Carry Adder Each carry bit is a multi-level function of the generates and propagates of the lower positions C3 = G2 + P2 C2 = G2 + P2 (G1 + P1 C1) = G2 + P2 (G1 + P1 (G0 + P0 C0)) Carry Look-Ahead Adders Ripple-carry adder C3 equation C4 C4 C0 C0 G3 G3 P3 P3 C3 C3 G2 G2 P2 P2 C2 C2 G1 G1 P1 P1 C1 C1 G0 G0 P0 P0 G G P P Cin Cin G G P P Cin Cin G G P P Cin Cin PFA PFA PFA PFA PFA PFA A A B B S S A A B B S S A A B B S S A3 A3 B3 B3 S3 S3 A2 A2 B2 B2 S2 S2 A1 A1 B1 B1 S1 S1 A0 A0 B0 B0 S0 S0 4 4 4

Carry Look-Ahead Adder Each carry bit is a two-level function of the generates and propagates of the lower positions Carry Look-Ahead Adders C4 C0 G3 P3 C3 G2 P2 C2 G1 P1 C1 G0 P0 G P Cin G P Cin G P Cin PFA PFA PFA A B S A B S A B S A3 B3 S3 A2 B2 S2 A1 B1 S1 A0 B0 S0 5 5 5

Getting There Algebraically Flatten the ripple-carry equation to two levels C3 = G2 + P2 (G1 + P1 (G0 + P0 C0)) = G2 + P2 G1 + P2 P1 (G0 + P0 C0) = G2 + P2 G1 + P2 P1 G0 + P2 P1 P0 C0 Carry look-ahead adder C3 equation Carry Look-Ahead Adders C4 C4 C0 C0 6 6 6 G3 G3 P3 P3 C3 C3 G2 G2 P2 P2 C2 C2 G1 G1 P1 P1 C1 C1 G0 G0 P0 P0

Carry Look-Ahead Logic You do not need to memorize the function for each carry bit! Instead, remember what generate and propagate mean, and how MATH works C3 C0 A3 A2 A1 A0 + B3 B2 B1 B0 Carry Look-Ahead Adders + G1 P2 + C0 P1 P2 C3 = G2 + G0 P1 P2 P0 C3 will be 1 if or if bit 1 generates a carry and it propagates at bit 2, or if bit 0 generates a carry and it propagates at bit 1 or if the carry-in at the least-significant bit is 1 and it propagates at bit 0 bit 2 generates a carry, and bit 2, and bit 1 and bit 2. 7 7 7

Extending Carry Look-Ahead Higher carry indices require more AND gates and a bigger OR gate There is a practical limit on the size of gates Carry Look-Ahead Adders How can we make wider adders? Hierarchy! Add look-ahead outputs indicating if the 4-bit group of PFAs generate or propagate a carry to the next group A higher-level look-ahead block uses group generates and propagates to determine carry-ins for each group Same idea as before, but for a group of bits Does this GROUP generate a carry? Does this GROUP propagate a carry? 8 8 8

Extending Carry Look-Ahead Replace C4 output with a group generate output GG, and a group propagate output PG GG is 1 if the group will generate a carry PG is 1 if the group will propagate the carry Carry Look-Ahead Adders GG PG C4 C0 C0 9 9 9 G3 G3 P3 P3 C3 C3 G2 G2 P2 P2 C2 C2 G1 G1 P1 P1 C1 C1 G0 G0 P0 P0

16-Bit Carry Look-Ahead Adder Entire 4-bit carry look-ahead adders (instead of PFAs) are connected to a top-level look-ahead Top-level look-ahead produces carry-in bits for each 4-bit CLA block based on group generates and propagates of the lower CLA blocks 4-bit look-ahead block Carry Look-Ahead Adders Look-Ahead C2 G2 P2 C16 C4 C0 G3 P3 C3 G1 P1 C1 G0 P0 GG3 PG3 C12 GG2PG2 GG C8 GG1 PG1 GG C4 GG0 PG0 GG PG PG GG PG PG Look-Ahead C2 G2 P2 C0 C0 C0 C0 C0 G3 P3 C3 G1 P1 C1 G0 P0 G7 P7 C7 G6 P6 C6 G5 P5 C5 G4 P4 4-Bit Carry Look-Ahead Adder 4-Bit Carry Look-Ahead Adder 4-Bit Carry Look-Ahead Adder G P Cin G P Cin G P Cin G P Cin PFA B PFA B PFA B PFA B A S A S A S A S A3 B3 S3 A2 B2 S2 A1 B1 S1 A0 B0 S0 A3 B3 S3 A2 B2 S2 A1 B1 S1 A0 B0 S0 A3 B3 S3 A2 B2 S2 A1 B1 S1 A0 B0 S0 A15 B15 S15 A14 B14 S14 A13 B13 S13 A12 B12 S12 A11 B11 S11 A10 B10 S10 A9 B9 S9 A8 B8 S8 A7 B7 S7 A6 B6 S6 A5 B5 S5 A4 B4 S4 A3 B3 S3 A2 B2 S2 A1 B1 S1 A0 B0 S0 4-bit carry look-ahead adders 10 10 10

16-Bit Carry Look-Ahead Adder Entire 4-bit carry look-ahead adders (instead of PFAs) are connected to a top-level look-ahead Top-level look-ahead produces carry-in bits for each 4-bit CLA block based on group generates and propagates of the lower CLA blocks 4-bit look-ahead block Carry Look-Ahead Adders Look-Ahead C2 G2 P2 C16 C4 C0 G3 P3 C3 G1 P1 C1 G0 P0 C4 = GG0 + PG0C0 GG3 PG3 C12 GG2PG2 GG C8 GG1 PG1 GG C4 GG0 PG0 GG PG PG GG PG PG Look-Ahead C2 G2 P2 C0 C0 C0 C0 C0 G3 P3 C3 G1 P1 C1 G0 P0 G7 P7 C7 G6 P6 C6 G5 P5 C5 G4 P4 4-Bit Carry Look-Ahead Adder 4-Bit Carry Look-Ahead Adder 4-Bit Carry Look-Ahead Adder G P Cin G P Cin G P Cin G P Cin PFA B PFA B PFA B PFA B A S A S A S A S A3 B3 S3 A2 B2 S2 A1 B1 S1 A0 B0 S0 A3 B3 S3 A2 B2 S2 A1 B1 S1 A0 B0 S0 A3 B3 S3 A2 B2 S2 A1 B1 S1 A0 B0 S0 A15 B15 S15 A14 B14 S14 A13 B13 S13 A12 B12 S12 A11 B11 S11 A10 B10 S10 A9 B9 S9 A8 B8 S8 A7 B7 S7 A6 B6 S6 A5 B5 S5 A4 B4 S4 A3 B3 S3 A2 B2 S2 A1 B1 S1 A0 B0 S0 11 11 11

16-Bit Carry Look-Ahead Adder Entire 4-bit carry look-ahead adders (instead of PFAs) are connected to a top-level look-ahead Top-level look-ahead produces carry-in bits for each 4-bit CLA block based on group generates and propagates of the lower CLA blocks 4-bit look-ahead block Carry Look-Ahead Adders Look-Ahead C2 G2 P2 C16 C4 C0 G3 P3 C3 G1 P1 C1 G0 P0 GG3 PG3 C12 GG2PG2 GG C8 GG1 PG1 GG C4 GG0 PG0 GG PG PG GG PG PG Look-Ahead C2 G2 P2 C0 C0 C0 C0 C0 G3 P3 C3 G1 P1 C1 G0 P0 G7 P7 C7 G6 P6 C6 G5 P5 C5 G4 P4 4-Bit Carry Look-Ahead Adder 4-Bit Carry Look-Ahead Adder 4-Bit Carry Look-Ahead Adder G P Cin G P Cin G P Cin G P Cin PFA B PFA B PFA B PFA B A S A S A S A S A3 B3 S3 A2 B2 S2 A1 B1 S1 A0 B0 S0 A3 B3 S3 A2 B2 S2 A1 B1 S1 A0 B0 S0 A3 B3 S3 A2 B2 S2 A1 B1 S1 A0 B0 S0 A15 B15 S15 A14 B14 S14 A13 B13 S13 A12 B12 S12 A11 B11 S11 A10 B10 S10 A9 B9 S9 A8 B8 S8 A7 B7 S7 A6 B6 S6 A5 B5 S5 A4 B4 S4 A3 B3 S3 A2 B2 S2 A1 B1 S1 A0 B0 S0 C12 = GG2 + PG2GG1 + PG2PG1GG0 + PG2PG1PG0C0 12 12 12

Extending Further We can make even larger carry look-ahead adders by adding more levels of hierarchy Build a 64-bit CLA with four 16-bit CLAs plus another look-ahead block Each 16-bit CLA would need a group generate and a group propagate output in its top-level look-ahead Does this group of 16 bits generate a carry? Does this group of 16 bits propagate a carry? Carry Look-Ahead Adders Hierarchical CLA carry chain is no longer two-level But far fewer levels than if it were a ripple-carry adder! CLA delay grows more slowly with operand size 13 13 13