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.

Temp < 1, Compared Unsigned and SignedOne temperature per step, with the heater decision from each kind of compare.
0123temp30-1-5heat (unsigned)heat (signed)freezing, heater off
Scroll horizontally ↔
  1. Cycle 1

    0 is below 1 either way, so both compares turn the heater on.

  2. Cycle 2

    −1 is the byte ff. Read unsigned it is 255, far above 1, so the heater stops.

  3. 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.

A 2-Bit Equality Comparator
a1a0b1b0eq
00001
00010
00100
00110
01000
01011
01100
01110
10000
10010
10101
10110
11000
11010
11100
11111
A 2-Bit Equality Comparatorn2 · XORn2=0n1 · NOTn1=1n4 · XORn4=0n3 · NOTn3=1n0 · ANDn0=1a1=0a0=0b1=0b0=0
a1=0 a0=0 b1=0 b0=0
n2 · XORa1=0, b1=0 → n2=0
n1 · NOTn2=0 → n1=1
n4 · XORa0=0, b0=0 → n4=0
n3 · NOTn4=0 → n3=1
n0 · ANDn1=1, n3=1 → n0=1
Read the connections
GateKindInputsOutput
n2XORa1, b1n2
n1NOTn2n1
n4XORa0, b0n4
n3NOTn4n3
n0ANDn1, n3n0

Outputs: n0. MUX inputs: d0, d1, select. Latch/flip-flop inputs: data, enable/clock. Unknown values are marked x; high impedance is folded into x in this model.

Two XNOR gates and an AND. eq is 1 on the four rows where a1 a0 equals b1 b0.

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 numbersPairs where it is right
Unsigned a < b = NOT carry out256
Signed a < b = N XOR V256
Signed a < b = N alone192

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.

Comparing a = 1011 with b = 1001, from the Top Bit DownFour cells in a chain. Each passes gt and lt to the cell below.
  • Datapath
  • I/O
  • Data
CallValueReturnWaiting
Comparing a = 1011 with b = 1001, from the top bit downFour cells in a chain. Each passes gt and lt to the cell below. datapath Cell 3 a3 = 1, b3 = 1 datapath Cell 2 a2 = 0, b2 = 0 datapath Cell 1 a1 = 1, b1 = 0 datapath Cell 0 a0 = 1, b0 = 1 io gt, lt, eq a > b gt, ltgt, ltgt, ltresult
  1. datapath Cell 3a3 = 1, b3 = 1
    • gt, lt → Cell 2
  2. datapath Cell 2a2 = 0, b2 = 0
    • gt, lt → Cell 1
  3. datapath Cell 1a1 = 1, b1 = 0
    • gt, lt → Cell 0
  4. datapath Cell 0a0 = 1, b0 = 1
    • result → gt, lt, eq
  5. io gt, lt, eqa > b
  1. Bits 3 and 2 are equal

    Neither cell decides, so gt = lt = 0 travels down.

    Follow the calls, values and waits
    1. data 0, 0: Cell 3 → Cell 2
    2. data 0, 0: Cell 2 → Cell 1
  2. Bit 1 decides

    a1 = 1 and b1 = 0, with all higher bits equal. Cell 1 sets gt.

    Follow the calls, values and waits
    1. data gt = 1: Cell 1 → Cell 0
  3. 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
    1. 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
  1. 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.

  2. 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.

  3. 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.

RTLIcarus Verilog · in your browser · Lint: Verilator service · Synthesize: Yosys service
Edit the design, then Run, Lint or Synthesize
Expected: 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=0

Original 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

Spot the bugEach option is the body of an always_comb block that must give signed a < b for 8-bit logic inputs. The bench tries 500 seeded pairs. Which body fails?
ConceptAfter computing a − b on unsigned numbers, which flag value means a < b?
ConceptAn iterative comparator chains its cells from bit 0 up to bit 7. Which pair does it get wrong?
ConceptHow many XNOR gates and how many two-input AND gates does a 16-bit equality comparator need, built as a tree?
Predict the outputPredict the exact line: an unsigned and a signed compare of the bytes ff and 01.
module tb;
  logic [7:0] a = 8'hFF, b = 8'h01;
  initial $display("%b %b", a < b, $signed(a) < $signed(b));
endmodule

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(...).

Before
logic [7:0] temp, limit;
assign heat = temp < limit;
After
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.

Practice

Report a problem with this page