"Is the temperature above the set point?" "Has the counter reached 59?" "Is this address inside the allowed range?" "Should the loop branch because i < n?" Every one of these questions is answered in hardware by a magnitude comparator, a circuit that compares two binary numbers and tells which one is bigger.
A magnitude comparator is a combinational circuit that takes two n-bit numbers A and B and produces three outputs: G (A > B), E (A = B) and L (A < B). Exactly one of the three is 1 for every input.
In this chapter we design the 1-bit comparator, derive the 2-bit comparator with K-maps, find the general pattern for 4 bits and beyond, cascade the 7485 chip, look at comparison by subtraction and at signed numbers, and simulate a 4-bit comparator in Verilog.
The Key Idea: Compare from the Most Significant Bit
How do you compare 4,738 and 4,712 in your head? You look at the thousands digits (equal), then the hundreds (equal), then the tens: 3 > 1, so the first number is larger. You never look at the units. This is exactly how a dictionary orders words, and exactly how a comparator works:
Scan from the most significant bit. At the first position where A and B differ, the number that has the 1 there is larger. If no position differs, A = B.
So the comparator needs two kinds of information at every bit position: "are these two bits equal?" and "if not, which one is 1?"
1-Bit Comparator
A | B | G (A > B) | E (A = B) | L (A < B) |
|---|---|---|---|---|
0 | 0 | 0 | 1 | 0 |
0 | 1 | 0 | 0 | 1 |
1 | 0 | 1 | 0 | 0 |
1 | 1 | 0 | 1 | 0 |
G = A·B′
L = A′·B
E = A′B′ + AB = (A ⊕ B)′ = A ⊙ B (XNOR)
= (G + L)′ (NOR of the other two outputs)
The last line is a nice trick: since exactly one output is 1, "equal" is simply "neither greater nor less". So a 1-bit comparator is 2 NOT gates, 2 AND gates and 1 NOR gate. The XNOR (A ⊕ B)′ is called the equality or coincidence function (see Logic Gates).
2-Bit Comparator
Now A = A1A0 and B = B1B0, four inputs and 16 rows. Taking minterm numbers in the order A1A0B1B0:
A > B for (A,B) = (1,0) (2,0) (2,1) (3,0) (3,1) (3,2) → G = Σm(4, 8, 9, 12, 13, 14)
A = B for (A,B) = (0,0) (1,1) (2,2) (3,3) → E = Σm(0, 5, 10, 15)
A < B for the remaining 6 rows → L = Σm(1, 2, 3, 6, 7, 11)
K-Map for G
B1B0
00 01 11 10
A1A0 00 | 0 0 0 0
01 | 1 0 0 0
11 | 1 1 0 1
10 | 1 1 0 0
Quad rows 11,10 × cols 00,01 → A1·B1′
Pair rows 01,11 × col 00 → A0·B1′·B0′
Pair row 11 × cols 00,10 → A1·A0·B0′
G = A1B1′ + A0B1′B0′ + A1A0B0′
By symmetry (swap the roles of A and B):
L = A1′B1 + A0′B1B0 + A1′A0′B0
And E has four isolated 1s on the K-map diagonal (no two are adjacent), so it does not simplify as a sum of products; instead we write it with XNORs:
E = (A1 ⊙ B1)·(A0 ⊙ B0)
The Structured Form
The K-map answer is minimal, but it hides the "scan from the MSB" idea. Define xi = (Ai ⊕ Bi)′, which is 1 when bit i of A and B are equal. Then:
G = A1B1′ + x1·A0B0′ "A wins at bit 1, or bit 1 ties and A wins at bit 0"
L = A1′B1 + x1·A0′B0 "B wins at bit 1, or bit 1 ties and B wins at bit 0"
E = x1·x0
Both forms of G are the same Boolean function (you can confirm this row by row on the 16-row truth table). The structured form is the one that generalises.
4-Bit Comparator
With xi = (Ai ⊕ Bi)′ for i = 3, 2, 1, 0:
E = x3·x2·x1·x0
G = A3B3′ + x3·A2B2′ + x3x2·A1B1′ + x3x2x1·A0B0′
L = A3′B3 + x3·A2′B2 + x3x2·A1′B1 + x3x2x1·A0′B0
Each term of G reads like a sentence: "A is greater if it wins at bit 3; or it ties at bit 3 and wins at bit 2; or it ties at bits 3 and 2 and wins at bit 1; or it ties at bits 3, 2, 1 and wins at bit 0." The pattern extends to any n: G has n product terms, the k-th term containing k − 1 equality signals.
Hardware for the 4-bit version: 4 XNOR gates for the xi, 8 AND-terms for G and L (of sizes 2, 3, 4 and 5 inputs), one 4-input OR each for G and L, and one 4-input AND for E (or E = (G + L)′ with a NOR).
Example 1: A = 1011, B = 1001
Bit: 3 2 1 0
A: 1 0 1 1
B: 1 0 0 1
xi: 1 1 0 1
E = x3x2x1x0 = 1·1·0·1 = 0
G terms: A3B3′ = 1·0 = 0
x3·A2B2′ = 1·0·1 = 0
x3x2·A1B1′ = 1·1·1·1 = 1 ← bit 1 decides
→ G = 1
L terms: A3′B3 = 0, x3·A2′B2 = 0, x3x2·A1′B1 = 0, x3x2x1·A0′B0 = 0 → L = 0
Result: A > B (11 > 9 ✓)
Cascading the 7485
The 7485 (74LS85, 74HC85) is a 4-bit magnitude comparator with three extra cascading inputs, IA>B, IA=B and IA<B. They answer the question "what did the less significant bits say?", and the chip only uses them when its own four bits are equal.
8-bit comparison of A7..A0 with B7..B0:
A3..A0, B3..B0 A7..A4, B7..B4
│ │
0 ──> I(A>B) ┌──────────┐ A>B ──> I(A>B) ┌──────────┐ ──> A>B
1 ──> I(A=B) │ 7485 LOW │ A=B ──> I(A=B) │ 7485 HIGH│ ──> A=B (final)
0 ──> I(A<B) └──────────┘ A<B ──> I(A<B) └──────────┘ ──> A<B
The least significant chip gets IA>B = 0, IA=B = 1, IA<B = 0: "below me, everything is equal".
The high chip decides on its own if A7..4 ≠ B7..4; only on a tie does it pass on the low chip's verdict.
k chips compare 4k bits. The verdict ripples through all of them, so the delay grows linearly, much like the ripple-carry adder in Ripple-Carry & Carry Look-Ahead Adders. For wide words, datasheets show faster tree arrangements in which several chips compare groups in parallel and one final chip combines them.
Comparing by Subtraction
Inside a processor there is usually no separate comparator: the ALU simply computes A − B and looks at the flags (see Subtractors).
Unsigned: compute A + B′ + 1. If there is no carry out (that is, a borrow), A < B. If the result is all zeros, A = B. Otherwise A > B.
Signed (2's complement): A < B when the sign flag differs from the overflow flag (N ⊕ V = 1), because overflow flips the apparent sign of the result.
This is how a cmp instruction followed by a conditional branch works. A dedicated comparator is used when the comparison must run in parallel with other work, or when no adder is around (a timer that compares a counter with a preset value, for example).
Signed Numbers with an Unsigned Comparator
An unsigned comparator gives the wrong answer for 2's complement numbers: 1110 (−2) looks larger than 0011 (+3) because 14 > 3. The fix is one inverter per number: complement the sign bits of both A and B, then compare unsigned. Flipping the MSB adds 2n−1 to every value, which maps −8...+7 onto 0...15 while keeping the order. Example: 1110 → 0110 (6), 0011 → 1011 (11), and 6 < 11, so −2 < +3. (Checked for all 256 pairs of 4-bit numbers.)
Verilog Model
The 4-bit comparator written from the structured equations, with a testbench that compares it against Verilog's own >, == and < for all 256 input pairs.
// 4-bit magnitude comparator built from the textbook equations
module comp4 (input logic [3:0] a, b, output logic gt, eq, lt);
logic [3:0] x; // x[i] = 1 when bit i of A and B are equal
assign x = ~(a ^ b);
assign eq = x[3] & x[2] & x[1] & x[0];
assign gt = (a[3] & ~b[3])
| (x[3] & a[2] & ~b[2])
| (x[3] & x[2] & a[1] & ~b[1])
| (x[3] & x[2] & x[1] & a[0] & ~b[0]);
assign lt = (~a[3] & b[3])
| (x[3] & ~a[2] & b[2])
| (x[3] & x[2] & ~a[1] & b[1])
| (x[3] & x[2] & x[1] & ~a[0] & b[0]);
endmodule
module tb;
logic [3:0] a, b; logic gt, eq, lt; int errors = 0;
comp4 dut (.*);
initial begin
for (int i = 0; i < 256; i++) begin
{a, b} = i[7:0]; #1;
if (gt !== (a > b) || eq !== (a == b) || lt !== (a < b)) errors++;
end
$display("Checked all 256 input pairs, errors = %0d", errors);
a = 4'd9; b = 4'd12; #1 $display("A=%0d B=%0d -> gt=%b eq=%b lt=%b", a, b, gt, eq, lt);
a = 4'd13; b = 4'd13; #1 $display("A=%0d B=%0d -> gt=%b eq=%b lt=%b", a, b, gt, eq, lt);
a = 4'd6; b = 4'd5; #1 $display("A=%0d B=%0d -> gt=%b eq=%b lt=%b", a, b, gt, eq, lt);
end
endmodule
Output (iverilog -g2012, vvp):
Checked all 256 input pairs, errors = 0
A=9 B=12 -> gt=0 eq=0 lt=1
A=13 B=13 -> gt=0 eq=1 lt=0
A=6 B=5 -> gt=1 eq=0 lt=0
In real projects you would just write assign gt = (a > b); and let the synthesis tool build the gates; the structural version is here so that you can see the equations working.
Counting Facts Worth Remembering
Quantity (n-bit A and B) | Formula | n = 2 | n = 4 |
|---|---|---|---|
Rows in the truth table | 22n | 16 | 256 |
Rows with A = B | 2n | 4 | 16 |
Rows with A > B (same for A < B) | (22n − 2n) / 2 | 6 | 120 |
Product terms in structured G | n | 2 | 4 |
XNOR gates for the xi | n | 2 | 4 |
Common Mistakes
Starting the comparison at the LSB. The most significant differing bit decides; lower bits matter only after a tie.
Forgetting the equality factors. G = A1B1′ + A0B0′ is wrong: A = 01, B = 10 would give G = 1.
Using XOR for equality. XOR is 1 when bits differ; equality is XNOR.
Wrong cascade inputs on the lowest 7485. They must be (A>B, A=B, A<B) = (0, 1, 0); leaving them all at 0 gives an invalid result when the numbers are equal.
Comparing 2's complement numbers with an unsigned comparator. Invert both sign bits first.
Interview and GATE Questions
Q1. Write the minimal SOP for A < B in a 2-bit comparator. How many literals does it have?
L = A1′B1 + A0′B1B0 + A1′A0′B0, with 2 + 3 + 3 = 8 literals.
Q2. How many minterms does the function "A > B" have for 3-bit unsigned A and B?
(26 − 23) / 2 = (64 − 8) / 2 = 28.
Q3. How many 7485 chips are needed to compare two 12-bit numbers in cascade, and what goes on the cascade inputs of the lowest chip?
Three chips (12 / 4). The lowest chip gets IA>B = 0, IA=B = 1, IA<B = 0.
Q4. Why can E be computed as (G + L)′?
For any pair of numbers exactly one of G, E, L is 1. So E is 1 exactly when both G and L are 0, which is NOR(G, L).
Q5. Using the 4-bit equations, what are G, E, L for A = 0110 and B = 0111?
x3 = x2 = x1 = 1, x0 = 0. The only non-zero term is x3x2x1·A0′B0 = 1 in L. So G = 0, E = 0, L = 1 (6 < 7).
Q6. Compare A = 1001 and B = 0100 as 4-bit 2's complement numbers using an unsigned comparator.
Invert the sign bits: A becomes 0001 (1) and B becomes 1100 (12). 1 < 12, so A < B. Check: A = −7, B = +4. Correct.
Q7. How does a processor decide "branch if A < B (unsigned)" without a comparator circuit?
It computes A − B as A + B′ + 1 in the ALU. For unsigned numbers, A < B exactly when this produces no carry out (a borrow occurred). Many ISAs expose this as the carry or borrow flag.
Summary
A magnitude comparator produces G, E, L for two n-bit numbers; exactly one is 1.
1 bit: G = AB′, L = A′B, E = A ⊙ B = (G + L)′.
The first differing bit from the MSB decides. With xi = Ai ⊙ Bi: E = ∏xi, and G = A3B3′ + x3A2B2′ + x3x2A1B1′ + x3x2x1A0B0′ (L similarly).
2-bit minimal SOP: G = A1B1′ + A0B1′B0′ + A1A0B0′.
The 7485 compares 4 bits and cascades via IA>B, IA=B, IA<B; the lowest chip gets (0, 1, 0).
Processors compare by subtracting and checking flags; for signed numbers with an unsigned comparator, invert both sign bits.
Next, Code Converters designs circuits that translate between binary, Gray, BCD and Excess-3.