Chapter 18 of 32

Magnitude Comparators

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