Microsoft PowerPoint – 053-2’s-complement-comparator
9/25/2016
University of Illinois at Urbana-Champaign
Dept. of Electrical and Computer Engineering
ECE 120: Introduction to Computing
A Comparator for 2’s Complement
ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 1
Comparing 2’s Complement Is Different from Unsigned
Let’s design a comparator for
2’s complement numbers.
Is the function the same as
with unsigned (like addition)?
For unsigned, 1001 > 0101.
Is the same true with 2’s complement?
No.
Should we just start over?
ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 2
Start with the Sign Bits
Let’s try a little harder first…
If we compare two non-negative numbers,
◦ the approach IS the same.
◦Right?
Maybe we can just use some extra logic to
handle the sign bits?
ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 3
Consider All Possible Combinations of Sign Bits
Let’s make a table based on the sign bits:
ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 4
As Bs interpretation solution
0 0 A ≥ 0 AND B ≥ 0 use unsigned
comparator
0 1 A ≥ 0 AND B < 0
1 0 A < 0 AND B ≥ 0
1 1 A < 0 AND B < 0
A > B
A < B
unknown
9/25/2016
Interpret 2’s Complement as Unsigned
Remember our “simple” rule for translating
2’s complement bit patterns to decimal?
The pattern A = aN-1aN-2 … a1a0
has value VA = -aN-12N-1 + aN-22N-2 + … + a020
Let A be negative (aN-1 = 1).
Interpreted as unsigned, the same bits
have value VA + 2N.*
*The statement is true by definition of 2’s complement, actually.
ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 5
Negative Numbers Can be Compared Directly
What happens if we feed two negative 2’s
complement numbers into our unsigned
comparator?
We compare VA + 2N with VB + 2N.
And we get an answer: <, =, or >.
Let’s say that we find VA + 2N < VB + 2N.
In that case, VA < VB, so we have the right
answer for 2’s complement.
The same result holds for other answers.
ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 6
We Need Special Logic for the Sign Bits
Now we can complete our table:
ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 7
As Bs interpretation solution
0 0 A ≥ 0 AND B ≥ 0 use unsigned
comparator
0 1 A ≥ 0 AND B < 0 A > B
1 0 A < 0 AND B ≥ 0 A < B
1 1 A < 0 AND B < 0 use unsigned
comparator
Simply Flip the Wires on the Most Significant Bit
Can we just flip the wires on the sign bits?
For As = 0 and Bs = 1,
◦ we feed in AN-1 = 1 and BN-1 = 0, and
◦ the unsigned comparator produces A > B.
For As = 1 and Bs = 0,
◦ we feed in AN-1 = 0 and BN-1 = 1, and
◦ the unsigned comparator produces A < B.
What about when As = Bs?
Flipping the bits then has no effect!
Answers are also correct in those cases.
ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 8
9/25/2016
One Comparator with a Control Signal can Do Both
Can we use a single comparator
to perform both kinds of comparisons?
Yes, if we
◦ add a control signal S
◦ to tell the comparator whether to do unsigned
(S=0) or 2’s complement (S=1) comparison.
Simply XOR’ing the most significant bits
of A and B with S suffices.
◦ This approach leverages flexibility in the
problem to reduce the logic needed.
◦ Analyze the design to understand how it works.
ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 9