Comparators
Test two numbers for equality with XNOR gates, and for order with a subtraction read the signed or the unsigned way.
You Will Be Able To
- Build an equality comparator from XNOR and AND gates.
- Get unsigned less-than from the borrow of a subtraction.
- Get signed less-than as N XOR V, and say why the sign bit alone fails.
- Chain comparator cells from the most significant bit.
- Lesson
- G4.8
- Time
- 25 min
- Runs on
- Your browser
- Check
- 5 questions
A greenhouse heater must run while the temperature is below 1 degree. The sensor gives a signed byte, but the compare was written on plain logic ports. At 0 degrees the heater runs, and at −1 degree it stops.
- Cycle 1
0 is below 1 either way, so both compares turn the heater on.
- Cycle 2
−1 is the byte ff. Read unsigned it is 255, far above 1, so the heater stops.
- Cycle 3
−5 is fb, or 251 unsigned. The colder it gets, the surer the controller is that it is warm.
Measured on the simulator. The same bit patterns, two kinds of compare.
Equality: XNOR Each Bit, Then AND
Two words are equal when every pair of bits is equal. An XNOR gate gives 1 for an equal pair. An AND of all the XNOR outputs gives 1 only when every pair matches.
On this site an 8-bit a == b synthesized to 15 cells: 8 XNOR and 7 AND gates, in 4 levels.
Less-Than from a Subtraction
Compute a − b with the adder of lesson G4.7 and read its flags. For unsigned numbers, a < b exactly when the subtraction borrows, that is when the carry out is 0.
For signed numbers, look at the sign N of the result. If the subtraction did not overflow, N = 1 means a < b. If it did overflow, the sign is wrong, and the overflow flag V says so. So signed a < b is N XOR V.
| Rule, checked on all 256 pairs of 4-bit numbers | Pairs where it is right |
|---|---|
| Unsigned a < b = NOT carry out | 256 |
| Signed a < b = N XOR V | 256 |
| Signed a < b = N alone | 192 |
Counted by simulating every pair. The sign alone fails in exactly the pairs whose subtraction overflows.
In the lab, 7f − 80 is 127 − (−128) = 255. That overflows, so d = ff has N = 1 although 127 is not less than −128. V = 1 flips the answer back to "not less".
Signed and Unsigned in SystemVerilog
A relational operator compares signed only when both operands are signed. If either one is unsigned, both are read as unsigned. A logic [7:0] port is unsigned unless you declare it signed.
Write the intent once, at the declaration. Casting in every expression is easy to forget in one place, and the mixed compare raises no error.
Iterative Comparator Cells
An iterative circuit is a chain of identical cells, one per bit. A comparator cell gets "greater so far" and "less so far" from the cell above. If either is set, it passes the decision on. If both are clear, the higher bits are equal, so it compares its own bits.
- Datapath
- I/O
- Data
- Bits 3 and 2 are equal
Neither cell decides, so gt = lt = 0 travels down.
Follow the calls, values and waits
- data 0, 0: Cell 3 → Cell 2
- data 0, 0: Cell 2 → Cell 1
- Bit 1 decides
a1 = 1 and b1 = 0, with all higher bits equal. Cell 1 sets gt.
Follow the calls, values and waits
- data gt = 1: Cell 1 → Cell 0
- Lower cells only pass it on
Cell 0 sees gt set and ignores its own bits. a > b, and eq = NOT (gt OR lt) = 0.
Follow the calls, values and waits
- data gt = 1: Cell 0 → gt, lt, eq
Read the diagram as text
- Cell 3: a3 = 1, b3 = 1
- Cell 2: a2 = 0, b2 = 0
- Cell 1: a1 = 1, b1 = 0
- Cell 0: a0 = 1, b0 = 1
- gt, lt, eq: a > b
- Cell 3 → Cell 2: gt, lt
- Cell 2 → Cell 1: gt, lt
- Cell 1 → Cell 0: gt, lt
- Cell 0 → gt, lt, eq: result
The first difference from the top decides. Lower bits only matter while everything above them is equal.
The chain is small, one cell per bit, but slow: the decision can travel through every cell. A subtraction-based comparator can use a fast adder instead.
A chain can also run from bit 0 upward, with another cell rule. A cell whose own bits differ overrides what comes from below. The direction and the cell rule must match.
Asked in interviews
How do you test two words for equality?
XNOR each pair of bits and AND all the results. Each XNOR is 1 for a matching pair, so the AND is 1 only when every pair matches.
How do you get signed less-than from a subtractor?
Compute a − b and take N XOR V. The sign of the result is correct unless the subtraction overflowed, and then V flips it.
Why does −1 < 1 fail in some code?
If either operand is unsigned, SystemVerilog compares both as unsigned. −1 in eight bits is ff, which reads as 255.
Try It
ff and 01 compare one way as unsigned (255 > 1) and the other way as signed (−1 < 1). The same subtractor gives both answers; only the flag that is read changes.
For 7f and 80 the subtraction overflows. N alone would say "less"; N XOR V says "not less".
Change the signed rule to lt = n; and run. Which line changes?
Add a gt output. Hint: gt = NOT lt AND NOT eq.
Synthesize the design to measure its cells and inspect the mapped gates.
ff vs 01 unsigned: eq=0 lt=0 signed (-1 vs 1): eq=0 lt=1 01 vs ff unsigned: eq=0 lt=1 signed (1 vs -1): eq=0 lt=0 7f vs 80 unsigned: eq=0 lt=1 signed (127 vs -128): eq=0 lt=0 42 vs 42 unsigned: eq=1 lt=0 signed (66 vs 66): eq=1 lt=0Original design · 43 cells · 0 flip-flops · 0 latches · 9 logic levels. Synthesis uses Yosys; counts depend on the toolchain.
Read included file: tb.sv
// tb.sv: the same bit patterns compared as unsigned and as signed numbers (read-only).
module tb;
logic [7:0] a, b;
logic sgn, eq, lt;
cmp8 dut (.a(a), .b(b), .sgn(sgn), .eq(eq), .lt(lt));
task automatic both(input logic [7:0] x, y);
a = x; b = y;
sgn = 0; #1 $write("%h vs %h unsigned: eq=%b lt=%b", a, b, eq, lt);
sgn = 1; #1 $display(" signed (%0d vs %0d): eq=%b lt=%b", $signed(a), $signed(b), eq, lt);
endtask
initial begin
both(8'hFF, 8'h01); // -1 and 1
both(8'h01, 8'hFF);
both(8'h7F, 8'h80); // 127 and -128: the subtraction overflows
both(8'h42, 8'h42);
end
endmodule
Check Yourself
Common Mistakes
Wrong Compare signed values with unsigned operands.
In SystemVerilog a compare is signed only when both operands are signed. −1 is then read as 255, which is more than 1.
Fix Declare both signed, or wrap both in $signed(...).
logic [7:0] temp, limit;
assign heat = temp < limit;logic signed [7:0] temp, limit;
assign heat = temp < limit;Wrong Take the sign of a − b as "a is less than b".
When the subtraction overflows, the sign bit is wrong. For 4-bit numbers that happens in 64 of the 256 pairs.
Fix Use N XOR V: the sign bit, corrected by the overflow flag.
Wrong Start an iterative comparator at the least significant bit.
The most significant bit that differs decides the order. A chain that lets the low bits decide gives 0001 > 1000.
Fix Pass the decision from the top bit down; a lower cell only decides while all higher bits are equal.
Wrong Test equality on fewer bits than the words have.
Two words that differ only in an untested bit read as equal. A short test with small numbers passes.
Fix XNOR every bit pair and AND all of them; a == b on full-width operands does that.
Remember
- Equality: XNOR every bit pair, then AND all the results.
- Unsigned a < b is the borrow of a − b: carry out = 0.
- Signed a < b is N XOR V; the sign alone fails when a − b overflows.
- SystemVerilog compares signed only when both operands are signed.
- An iterative comparator passes the decision down from the most significant bit.