Understanding Carry Bit Calculation in Digital Systems

Slide Note

Explore the concepts of carry bit calculation in digital systems through re-examination of addition operations, generating carries, propagating carries, and scenarios where Cout must be zero. Discover how different combinations of Ak and Bk values influence the carry bit and learn about situations where Cout equals Cin, Cout is guaranteed to be 1 regardless of Cin, and when Cout must remain 0 irrespective of Cin.

lil_dis 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 Re-Examining Carry Bit Calculation Digital System Fundamentals Re-Examining Carry Bit Calculation 1 1 1

Re-Examining Addition For a bit position k, can the values of Akand Bk tell us something about that position s Coutbefore its Cinis known? An Bn Ak Bk Re-Examining Carry Bit Calculation A1 B1 A0 B0 A B A B A B A B Cn+1 Cn Ck+1 Ck C2 C1 C0 Cout Cin Cout Cin Cout Cin Cout Cin S S S S Sn Sk S1 S0 Specifically, can different combinations of Akand Bkvalues guarantee that: Coutis 1 regardless of the value of Cin? Coutwill be equal to Cin? Coutis 0 regardless of the value of Cin? 2 2 2

Generating Carries What values of A and B guarantee that Coutis 1 regardless of the value of Cin? Cin A B 0 1 Re-Examining Carry Bit Calculation ? 1 ? 1 Cout S 0 0 0 0 0 0 1 0 A B 0 0 1 1 1 0 0 1 0 0 1 0 1 0 1 1 X Cout Cin S 1 1 1 0 1 1 1 0 1 1 1 1 0 0 1 This bit position generates a carry, independent of results at lower bit positions! Cout is 1 regardless of Cin if A = 1 and B = 1 3 3 3

Propagating Carries What values of A and B guarantee Cout equals Cin? Re-Examining Carry Bit Calculation A B Cin Cout S ? ? 0 1 Two situations: ? 1 0 0 0 0 0 0 ? ? ? 0 0 1 0 1 A B 0 0 1 1 1 0 0 1 0 0 1 0 1 0 1 A B A B 1 1 Cin Cout 1 Cin Cout 1 1 1 Cout Cin S S S 1 1 1 0 1 1 1 0 1 1 1 1 0 0 1 This bit position propagates the incoming carry value to the next position! Cout is equal to Cin if A B 4 4 4

Propagating Carries These values of A and B also guarantee that a Cin value of 0 will cause Cout to be 0 Cin A B 0 1 Re-Examining Carry Bit Calculation Cout S Two situations: 0 0 0 0 ? 1 0 ? 0 1 ? ? 0 0 1 0 0 0 1 1 1 0 0 1 0 0 1 0 1 0 1 A B A B 0 0 0 0 Cout Cin Cout Cin S S 1 1 1 0 1 1 1 0 1 1 1 1 0 0 1 This bit position propagates the incoming carry value (even when the carry is 0) to the next position! Cout is equal to Cin if A B 5 5 5

Sometimes Cout Must Be Zero What values of A and B guarantee that Cout is 0 regardless of the value of Cin? Cin A B 0 1 Re-Examining Carry Bit Calculation ? 0 ? 0 Cout S 0 0 0 0 0 0 1 0 A B 0 0 1 1 1 0 0 1 0 0 1 0 1 0 1 0 X Cout Cin S 1 1 1 0 1 1 1 0 1 1 1 1 0 0 1 This bit position neither generates nor propagates a carry! Cout is 0 regardless of Cin if A = 0 and B = 0 6 6 6

Alternate Equations for Carry Bits Adder cell k generates a carry if Ak and Bk are both 1 Gk = AkBk Gk is TRUE if adder cell k generates a carry Adder cell k propagates the carry if either Ak or Bk are 1, but not both Pk = Ak XOR Bk Pk is TRUE if adder cell k propagates a carry How do we know if Ck+1, the carry-out of position k, is 1? Re-Examining Carry Bit Calculation propagates a carry AND its Cin is 1 generates a carry Bit position k s Coutis 1 if it OR Ck+1 = Gk + PkCk 7 7 7

Reorganizing the Full Adder Partial Full Adder (PFA) plus carry chain logic PFA: a full adder without the carry chain logic Carry chain: computes the carry values based on the generate (G) and propagate (P) signals from the PFA Re-Examining Carry Bit Calculation A B Carry Chain Cout Cin G P Cin Cout Cin PFA A B S S 8 8 8

Ripple-Carry Adder With PFAs Can create ripple-carry adder (RCA) with PFAs G: Generates a carry at this position P: Propagates a carry through this position Re-Examining Carry Bit Calculation C2 = G1 + P1 C1 C4 C0 G3 P3 C3 G2 P2 C2 G1 P1 C1 G0 P0 C0 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 G1 = A1 B1 B2 S2 A1 B1 S1 A0 B0 S0 P1 = A1 XOR B1 Could optimize the carry-chain to reduce delay 9 9 9

Delay in Logic Circuits A gate s output is not actually the result of its logic function until some time after the input(s) change This is that gate s gate delay Each gate along a path from a circuit input to a circuit output adds to the delay of that path i.e., the length of time it will take for the circuit output to become valid after that circuit input changes value Re-Examining Carry Bit Calculation C4 C0 G3 P3 C3 G2 P2 C2 G1 P1 C1 G0 P0 C0 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 The path with the longest delay from ANY input to ANY output is called the critical path The worst-case delay for any change on any input 10 10 10

Why Compute the Carry Differently? Ripple carry adders are small and easy to create Minimal logic, good tileable structure But ripple carry adders are slow! Design is limited by the delays in propagating carry through all of the bitwise additions The sum at any given bit position requires the values A0, B0, and C0 to propagate all the way to that point Re-Examining Carry Bit Calculation C4 C0 G3 P3 C3 G2 P2 C2 G1 P1 C1 G0 P0 C0 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 Could optimize the carry-chain to reduce delay 11 11 11