G4.8.2 Cascade the Comparator Cells

MediumImplementIcarus · browser samples / server checksReview the topic

Chain eight comparator cells into an 8-bit magnitude comparator, from the most significant bit down.

Hardware context: A data logger with mixed signed and unsigned sensors, and a deadline scheduler built from comparator cells. Chain eight iterative comparator cells from the top bit down.

A scheduler compares two 8-bit deadlines with a small iterative comparator, one cell per bit. Each cell passes "greater so far" and "less so far" to the cell below it.

This is an Implement problem. Write cmp8c as a netlist of cells from the read-only library: eight comparator cells and at most three gates. gt, lt and eq compare a and b as unsigned numbers; exactly one of them is 1.

The check applies eight pairs, one every 12 ns, and records gt, lt and eq after each. It also counts your cells.

Signals in the Timeline

SignalWidthRole
script128input of each check
Full specification
The module (keep the name and the ports)
module cmp8c (
  input  logic [7:0] a, b,       // unsigned
  output wire        gt, lt, eq
);
  // your netlist
endmodule
cmpcells.sv: the cell library (read-only). Ports are (outputs, inputs): the outputs come first
// cmpcells.sv: the cell library (read-only). Every cell takes 1 ns. Ports: outputs first.
// CMPC: one bit of an iterative comparator. If gt_i or lt_i is 1, a higher bit has decided, and the
// cell passes the decision on. If both are 0, the higher bits are equal, and the cell compares a with b.
// Every CMPC adds 1 to tb.n_cmp; every other cell adds 1 to tb.n_gate.
module CMPC (output wire gt_o, lt_o, input wire a, b, gt_i, lt_i);
  assign #1 gt_o = gt_i | (!lt_i & a & !b);
  assign #1 lt_o = lt_i | (!gt_i & !a & b);
  initial tb.n_cmp++;
endmodule
module INV  (output wire y, input wire a);       not #1 (y, a);    initial tb.n_gate++; endmodule
module NOR2 (output wire y, input wire a, b);    nor #1 (y, a, b); initial tb.n_gate++; endmodule
module OR2  (output wire y, input wire a, b);    or  #1 (y, a, b); initial tb.n_gate++; endmodule

RuleDetail
Functiongt = 1 when a > b, lt = 1 when a < b, eq = 1 when a = b (unsigned).
CellsExactly eight comparator cells and at most three other cells.
ConstantsThe first cell of the chain may take 1'b0 on its gt_i and lt_i.

The result shows gt, lt and eq after each of the eight pairs, and whether the cell count is wrong.

Examples

Example 1

Small Numbers
Input
01 vs 02, 02 vs 01, 05 vs 05, 00 vs 00, 03 vs 07, 07 vs 03, 09 vs 08, 08 vs 09
Output
gt_step0 = no, lt_step0 = yes, eq_step0 = no, gt_step1 = yes, lt_step1 = no, eq_step1 = no, gt_step2 = no, lt_step2 = no, eq_step2 = yes, gt_step3 = no, lt_step3 = no, eq_step3 = yes, gt_step4 = no, lt_step4 = yes, eq_step4 = no, gt_step5 = yes, lt_step5 = no, eq_step5 = no, gt_step6 = yes, lt_step6 = no, eq_step6 = no, gt_step7 = no, lt_step7 = yes, eq_step7 = no, cell_count_wrong = no

Only the low bits differ, so the upper cells pass "nothing decided" down until a differing bit sets gt or lt.

Example 2

The Top Bit Decides
Input
80 vs 7f, 7f vs 80, 81 vs 01, 01 vs 81, ff vs 7f, 7f vs ff, 80 vs 80, 00 vs 80
Output
gt_step0 = yes, lt_step0 = no, eq_step0 = no, gt_step1 = no, lt_step1 = yes, eq_step1 = no, gt_step2 = yes, lt_step2 = no, eq_step2 = no, gt_step3 = no, lt_step3 = yes, eq_step3 = no, gt_step4 = yes, lt_step4 = no, eq_step4 = no, gt_step5 = no, lt_step5 = yes, eq_step5 = no, gt_step6 = no, lt_step6 = no, eq_step6 = yes, gt_step7 = no, lt_step7 = yes, eq_step7 = no, cell_count_wrong = no

80 against 7f: bit 7 differs, so the first cell decides "greater" and every lower cell only passes it on.

Example 3

One Differing Bit at Each Place
Input
01 vs 00, 00 vs 02, 04 vs 00, 00 vs 08, 10 vs 00, 00 vs 20, 40 vs 00, 00 vs 80
Output
gt_step0 = yes, lt_step0 = no, eq_step0 = no, gt_step1 = no, lt_step1 = yes, eq_step1 = no, gt_step2 = yes, lt_step2 = no, eq_step2 = no, gt_step3 = no, lt_step3 = yes, eq_step3 = no, gt_step4 = yes, lt_step4 = no, eq_step4 = no, gt_step5 = no, lt_step5 = yes, eq_step5 = no, gt_step6 = yes, lt_step6 = no, eq_step6 = no, gt_step7 = no, lt_step7 = yes, eq_step7 = no, cell_count_wrong = no

Each pair differs in one bit only, in every position from bit 0 to bit 7. Each cell must decide when it is the one.

Constraints and Contract

  • Inputs are known 0/1 values. Each pair is held for 12 ns before the outputs are read.
  • Keep the module name and the ports.

Hints

Hint 1

Which bit decides the order of two numbers? Start the chain there, with "nothing decided yet" on its inputs.

Hint 2

Each cell feeds its gt_o and lt_o to the gt_i and lt_i of the next lower bit. Keep greater with greater and less with less.

Hint 3

After the last cell, a and b are equal when neither gt nor lt is set: one NOR gate.

What the grader checks: Five directed and eight seeded cases apply eight pairs each. gt, lt and eq are compared with a model written in JavaScript. The source may hold only cell instances: eight comparator cells and at most three gates.

13 checks on Icarus · browser samples / server checks. Run the examples first, then check the full regression. Full checks use the server judge. Downloads contain public samples only. A passing result establishes the tested cases, not a proof for all possible inputs.

See all 2 steps and the final capstone

Report a problem with this page

Your code SystemVerilogSaved locally
Ln 1, Col 1Tab indents · Ctrl/⌘ + Enter runs samples
Not run yet

Small Numbers

Input
01 vs 02, 02 vs 01, 05 vs 05, 00 vs 00, 03 vs 07, 07 vs 03, 09 vs 08, 08 vs 09
Expected output
gt_step0 = no, lt_step0 = yes, eq_step0 = no, gt_step1 = yes, lt_step1 = no, eq_step1 = no, gt_step2 = no, lt_step2 = no, eq_step2 = yes, gt_step3 = no, lt_step3 = no, eq_step3 = yes, gt_step4 = no, lt_step4 = yes, eq_step4 = no, gt_step5 = yes, lt_step5 = no, eq_step5 = no, gt_step6 = yes, lt_step6 = no, eq_step6 = no, gt_step7 = no, lt_step7 = yes, eq_step7 = no, cell_count_wrong = no

Only the low bits differ, so the upper cells pass "nothing decided" down until a differing bit sets gt or lt.

Run samples executes all 3 public checks. Check all tests runs 13 checks on the server.

Icarus · browser samples / server checks