程序代写代做代考 Microsoft PowerPoint – 049-ripple-carry-adder
Microsoft PowerPoint – 049-ripple-carry-adder
9/22/2016
University of Illinois at Urbana-Champaign
Dept. of Electrical and Computer Engineering
ECE 120: Introduction to Computing
The Ripple Carry Adder
ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 1
Build an Addition Device Based on Human Addition
ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 2
Weeks ago, we talked about a
“hardware device” to perform addition.
Now, you’re ready to design it.
Let’s start by reviewing the human approach.
Basing a design on the human approach
◦ is usually the easiest way, and
◦often leads to a good design, too.
◦ (Humans are pretty smart.)
Example: Addition of Unsigned Bit Patterns
Let’s do an example with 5-bit unsigned
01110 (14)
+ 00100 (4)
Good, we got the right answer!
ECE 120: Introduction to Computing slide 3
011
1
0
1
0 (18)
© 2016 Steven S. Lumetta. All rights reserved.
There is no
“blank” bit.
Each 1-bit
sum needs a
C input.
Let’s do an example with 5-bit unsigned
01110
+ 00100
Good, we got the right answer!
For least significant bit, C←0.
For other bits, C comes from next bit to right.
Name Signals (Bits) for Our Hardware Design
ECE 120: Introduction to Computing slide 4
011
1
0
1
0
© 2016 Steven S. Lumetta. All rights reserved.
A
B
sum S
carry C 000
9/22/2016
Inputs and Outputs for a Full (One-Bit) Adder
Think about adding a single bit (a column).
A full adder* has three inputs
◦ A (one bit of the number A)
◦ B (one bit of the number B)
◦ Cin (a carry input from the next least significant bit, or 0 for bit 0)
And a full adder produces two outputs
◦ Cout (a carry output for the next most significant bit)
◦ S (one bit of the sum S)
*A one-bit adder is called a “full adder” for historical reasons.
A “half adder” adds two bits instead of three.
ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 5
Connecting the Full Adder to the N-Bit Problem
Consider bit M of
the addition (bit 0
is on the right, bit
1 to the left of bit 0,
and so forth).
We need to add AM,
BM, and CM to
produce bit SM, of
the sum and bit CM+1,
the carry into bit M+1 of the addition.
ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 6
Write a Truth Table for Full Adder Outputs
Let’s calculate the
outputs for a full
adder.
You may remember
solving this truth
table a few weeks
ago.
But let’s do it again…
ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 7
A B Cin Cout S
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
00
10
10
01
10
01
01
11
Fill a K-map for Cout from the Truth Table
Now fill in the truth
table for Cout.
ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 8
Cout
BCin
00 01 11 10
A
0
1
0
1
A B Cin Cout S
0 0 0 0 0
0 0 1 0 1
0 1 0 0 1
0 1 1 1 0
1 0 0 0 1
1 0 1 1 0
1 1 0 1 0
1 1 1 1 1
1 00
1 10
9/22/2016
Solve the K-map to Find Cout
And find the loops.
So we can write Cout = AB + ACin + BCin
(called a majority function, by the way).
ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 9
Cout
BCin
00 01 11 10
A
0 0 0 1 0
1 0 1 1 1
The Sum is Best Written as an XOR
What about S? We
can (of course) use
another K-map.
But a K-map doesn’t
give us the best
answer in this case
(a rare case!).
S is 1 when an odd
number of inputs
are 1.
So S = A B C.
ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 10
A B Cin Cout S
0 0 0 0 0
0 0 1 0 1
0 1 0 0 1
0 1 1 1 0
1 0 0 0 1
1 0 1 1 0
1 1 0 1 0
1 1 1 1 1
XOR Shows up as a Checkerboard Pattern
Here’s the K-map
for S. Notice the
checkerboard pattern
of the XOR.
ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 11
S BCin
00 01 11 10
A
0 0 1 0 1
1 1 0 1 0
A B Cin Cout S
0 0 0 0 0
0 0 1 0 1
0 1 0 0 1
0 1 1 1 0
1 0 0 0 1
1 0 1 1 0
1 1 0 1 0
1 1 1 1 1
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
Circuit for a Full Adder Using AND, OR, and XOR
We can draw our full adder using AND, OR,
and XOR.
ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 12
9/22/2016
CMOS Implementation Using NAND and XOR
In CMOS, we replace AND/OR with NAND/
NAND.
The XOR
remains as
an XOR
gate.
ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 13
How Do We Add N Bits?
Use a full adder for each of the N columns.
Feed a 0 into Cin for the least significant bit.
Cout of the most significant bit
is the adder’s carry out.
For the other carry signals, connect Cout of
each bit to Cin of the next most significant bit.
Divide the bits of A and B
amongst the full adders.
Collect the bits of S from the full adders.
ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 14
Use N One-Bit Adders to Build an N-Bit Adder
The figure below illustrates construction of an
N-bit adder from N full adders.
This approach is called a ripple carry adder
because the carry ripples slowly from low to
high. We also call it a bit-sliced adder.
ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 15
Symbol for an N-Bit Adder
We draw an
N-bit adder
as shown here.
Note the shape.
Note also the
crosshatch and
bit width (“N”)
for multi-bit
signals.
ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 16
9/22/2016
To Build a Bigger Adder, Just Connect Cout to Cin
We can build bigger adders by connecting
adders together physically (as shown below)
or virtually (by saving the carry out bit and
using it as
the carry in
to the next
adder).
ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 17