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.