程序代写代做代考 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

Posted in Uncategorized

Leave a Reply

Your email address will not be published. Required fields are marked *