Carry Bit Calculation in Digital Systems
ECE 352
Digital System Fundamentals
Re-Examining Carry Bit Calculation
Re-Examining Addition
•
For a bit position k, can the values of A
k
and B
k
tell us something about that position’s C
out
before
its C
in
is known?
•
Specifically, can different combinations of A
k
and
B
k
values guarantee that:
•
C
out
is 1 regardless of the value of C
in
?
•
C
out
will be equal to C
in
?
•
C
out
is 0 regardless of the value of C
in
?
Generating Carries
•
What values of A and B guarantee that C
out
is 1
regardless of the value of C
in
?
C
o
u
t
i
s
1
r
e
g
a
r
d
l
e
s
s
o
f
C
i
n
i
f
A
=
1
a
n
d
B
=
1
T
h
i
s
b
i
t
p
o
s
i
t
i
o
n
g
e
n
e
r
a
t
e
s
a
c
a
r
r
y
,
i
n
d
e
p
e
n
d
e
n
t
o
f
r
e
s
u
l
t
s
a
t
l
o
w
e
r
b
i
t
p
o
s
i
t
i
o
n
s
!
1
1
Propagating Carries
•
What values of A and B guarantee C
out
equals C
in
?
C
o
u
t
i
s
e
q
u
a
l
t
o
C
i
n
i
f
A
≠
B
T
w
o
s
i
t
u
a
t
i
o
n
s
:
T
h
i
s
b
i
t
p
o
s
i
t
i
o
n
p
r
o
p
a
g
a
t
e
s
t
h
e
i
n
c
o
m
i
n
g
c
a
r
r
y
v
a
l
u
e
t
o
t
h
e
n
e
x
t
p
o
s
i
t
i
o
n
!
1
0
0
1
Propagating Carries
•
These values of A and B also guarantee that a C
in
value of 0 will cause C
out
to be 0
C
o
u
t
i
s
e
q
u
a
l
t
o
C
i
n
i
f
A
≠
B
T
h
i
s
b
i
t
p
o
s
i
t
i
o
n
p
r
o
p
a
g
a
t
e
s
t
h
e
i
n
c
o
m
i
n
g
c
a
r
r
y
v
a
l
u
e
(
e
v
e
n
w
h
e
n
t
h
e
c
a
r
r
y
i
s
0
)
t
o
t
h
e
n
e
x
t
p
o
s
i
t
i
o
n
!
1
0
0
1
T
w
o
s
i
t
u
a
t
i
o
n
s
:
Sometimes C
out
Must Be Zero
•
What values of A and B guarantee that C
out
is 0
regardless of the value of C
in
?
C
o
u
t
i
s
0
r
e
g
a
r
d
l
e
s
s
o
f
C
i
n
i
f
A
=
0
a
n
d
B
=
0
T
h
i
s
b
i
t
p
o
s
i
t
i
o
n
n
e
i
t
h
e
r
g
e
n
e
r
a
t
e
s
n
o
r
p
r
o
p
a
g
a
t
e
s
a
c
a
r
r
y
!
0
0
Alternate Equations for Carry Bits
•
Adder cell k
generates
a carry if A
k
and B
k
are
both
1
•
G
k
= A
k
B
k
•
G
k
is TRUE if adder cell k
generates
a carry
•
Adder cell k
propagates
the carry if
either
A
k
or B
k
are 1,
but not both
•
P
k
= A
k
XOR B
k
•
P
k
is TRUE if adder cell k
propagates
a carry
•
How do we know if C
k+1
, the carry-out of position k, is 1?
C
k+1
=
G
k
+
Bit position k’s
C
out
is 1 if it…
g
e
n
e
r
a
t
e
s
a
c
a
r
r
y
OR
P
k
C
k
p
r
o
p
a
g
a
t
e
s
a
c
a
r
r
y
A
N
D
its C
in
is 1
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
PFA
Carry
Chain
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
•
Could optimize the carry-chain to reduce delay…
P
1
= A
1
XOR B
1
G
1
= A
1
B
1
C
2
= G
1
+ P
1
C
1
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
•
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
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
A
0
,
B
0
, and
C
0
to propagate all the way to that point
•
Could optimize the carry-chain to reduce delay…
ECE 352
Digital System Fundamentals
Re-Examining Carry Bit Calculation
In this presentation, we will take an in-depth look at the generation of carries in a binary adder. As we have seen previously in the ripple-carry adder, the carry-out from the least significant bit must propagate all the way through the adder to the most significant bit before the result is valid. This represents a significant delay.
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.
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
ECE 352 Re-Examining Carry Bit Calculation Digital System Fundamentals Re-Examining Carry Bit Calculation 12 12 12
