程序代写代做代考 Microsoft PowerPoint – 051-bit-sliced-comparator

Microsoft PowerPoint – 051-bit-sliced-comparator

9/25/2016

University of Illinois at Urbana-Champaign
Dept. of Electrical and Computer Engineering

ECE 120: Introduction to Computing

Bit-Sliced Comparator

ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 1

How Do You Compare Unsigned Numbers?

ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 2

Let’s develop a bit-sliced design to
compare two unsigned numbers.

Which 8-bit unsigned number is bigger?

0 1 1 0 1 0 0 0
0 1 0 1 0 1 1 1

How did you know?
Did you start on the left or the right?

Humans Go from Left to Right

ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 3

Usually, humans start on the left. Why?
As soon as we notice a difference, we’re done!

a7a6a5a4a3a2a1a0
b7b6b5b4b3b2b1b0

Bit-sliced hardware cannot stop in the middle.
The information flows from one end to the other.
Output wires produce the answer (in bits).

0

0

1

1

1

0

humans compare this way

Our Design Compares from Right to Left

ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 4

Our comparator design will start on the right.

a7a6a5a4a3a2a1a0
b7b6b5b4b3b2b1b0

From least significant to most significant bit.

humans compare this way

our design will compare this way

9/25/2016

Three Possible Answers for Comparison of A and B

ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 5

When comparing two numbers, A and B,
we have three possible outcomes:

A < B A = B A > B

To decide the answer for N+1 bits, we need:
◦ the answer for N (less significant) bits,
◦ one bit of A, and
◦ one bit of B.

An Abstract Model of the Comparator Bit Slice

ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 6

A question for you:
How many bits must pass between slices?
Two!
This figure
shows an
abstract
model of our
bit slice.

We Need a Representation for Answers

ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 7

Another question for you:
How do we represent the
three possible answers?
Any way we want!
Our choice of
representation will
affect the amount of
logic we need.
Here’s a good one…

C1 C0 meaning
0 0 A = B
0 1 A < B 1 0 A > B
1 1 not used

A Single Bit Requires Two Minterms on A, B

ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 8

Let’s start by solving a single bit.
In this case, there are no less significant bits.
So we consider
only A and B.
Fill in the meanings,
then the bits.
Note that Z1 and Z0
are minterms.

A B Z1 Z0 meaning
0 0
0 1
1 0
1 1

A = B

A > B
A < B A = B 0 0 0 1 1 0 0 0 9/25/2016 Comparing Two Bits is Fairly Easy ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 9 An implementation for a single bit appears below. This structure forms the core of our bit slice, since it compares one bit of A with one bit of B. When A and B are Equal, Pass Along the Answer ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 10 Now for the full problem. We’ll start with the case of A = 0 and B = 0. A B C1 C0 meaning Z1 Z0 meaning 0 0 0 0 A = B 0 0 0 1 A < B 0 0 1 0 A > B
0 0 1 1 ???

A = B

A > B
A < B don’t care 0 0 0 1 1 0 x x When A and B are Equal, Pass Along the Answer ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 11 Is there any difference when A = 1 and B = 1? No, outputs are the same as the last case. A B C1 C0 meaning Z1 Z0 meaning 0 0 0 0 A = B 0 0 0 1 A < B 0 0 1 0 A > B
0 0 1 1 ???

A = B

A > B
A < B don’t care 0 0 0 1 1 0 x x When A and B Differ, Override the Previous Answer ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 12 What about case of A = 0 and B = 1? Always output A < B (for valid inputs). A B C1 C0 meaning Z1 Z0 meaning 0 1 0 0 A = B 0 1 0 1 A < B 0 1 1 0 A > B
0 1 1 1 ???

A < B A < B A < B don’t care 0 1 0 1 0 1 x x 9/25/2016 When A and B Differ, Override the Previous Answer ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 13 And the case of A = 1 and B = 0? Always output A > B (for valid inputs).

A B C1 C0 Meaning Z1 Z0 meaning
1 0 0 0 A = B
1 0 0 1 A < B 1 0 1 0 A > B
1 0 1 1 ???

A > B

A > B
A > B

don’t care

1 0
1 0
1 0
x x

Z1 is a Majority Function

ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 14

Let’s use a K-map to solve Z1.
What are the loops?
AB’
AC1
B’C1

So
Z1 = AB’ + AC1 + B’C1

Z1
AB

00 01 11 10

C1C0

00 0 0 0 1

01 0 0 0 1

11 x x x x

10 1 0 1 1

Z0 is Also a Majority Function

ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 15

Now let’s use a K-map to solve Z0.
What are the loops?
A’B
A’C0
BC0

So
Z0 = A’B + A’C0 + BC0

Z0
AB

00 01 11 10

C1C0

00 0 1 0 0

01 1 1 1 0

11 x x x x

10 0 1 0 0

Full Implementation as SOP Expressions

ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 16

Z1 = AB’ +
AC1 + B’C1

Z0 = A’B +
A’C0 + BC0

Notice the
symmetry.
And the
single-bit core.