G3.9.2 Prove Two Circuits Equal

MediumImplementIcarus · browser samples / server checksReview the topic

Write a miter for a two-output comparator and an exhaustive sweep. Prove the gate-level version equal to its specification, or find the first row where it is not.

Hardware context: A NOR-gate implementation checked against its specification through a miter, and the decision diagrams behind equivalence tools. Prove a gate-level comparator equal to its specification with a two-output miter.

A 2-bit comparator has a specification and a gate-level implementation. Both have two outputs: y[1] is a > b and y[0] is a == b. With four inputs, trying all 16 rows is a complete proof.

This is an Implement problem. Write module miter: it must output diff = 1 on any row where the two circuits disagree on either output. Then write the task sweep in module equiv_check.

The sweep tries every row of x in increasing order. It returns how many rows differ and the lowest row that differs, or 0 if none does.

The hidden checks swap in other versions of the implementation, some with seeded bugs. A good miter and sweep find every one of them.

Signals in the Timeline

SignalWidthRole
impl2input of each check
Full specification
spec.sv: the two circuits (read-only)
// spec and impl (read-only). x = {a1, a0, b1, b0}: a = x[3:2], b = x[1:0]. y = {a > b, a == b}.
module spec (input logic [3:0] x, output logic [1:0] y);
  assign y = {x[3:2] > x[1:0], x[3:2] == x[1:0]};
endmodule

// The gate-level implementation.
module impl (input logic [3:0] x, output logic [1:0] y);
  logic a1, a0, b1, b0, e1, gt, eq;
  always_comb begin
    {a1, a0, b1, b0} = x;
    e1 = ~(a1 ^ b1);
    gt = (a1 & ~b1) | (e1 & a0 & ~b0);
    eq = e1 & ~(a0 ^ b0);
    // (the hidden checks may swap in another version here)
    y = {gt, eq};
  end
endmodule

PartWhat it must do
miterPorts x (4 bits in) and diff (1 bit out). Instantiate spec and impl on the same x. diff is 1 when any output bit differs.
equiv_checkHolds x, the miter and the task sweep. Keep the names.
sweepApply x = 0, 1, ..., 15 in order. After each, wait 1 ns, then read diff. Return bad (rows that differ) and first (the lowest such row, or 0).
TimeThe sweep may take at most 40 ns.

Four checks run your sweep against four versions of the implementation. Three more apply one row straight to your miter.

Examples

Example 1

The Correct Implementation
Input
implementation 0
Output
rows_that_differ = 0, first_row = 'b0000

No row differs: the sweep returns 0 rows and first = 0000. That is the proof of equivalence.

Example 2

The Miter on the Correct Implementation
Input
implementation 0, x = 0110
Output
diff = 0

Row 0110 against the correct implementation: both outputs agree, so diff is 0.

Example 3

The Miter on a Bug in a > b
Input
implementation 1, x = 0110
Output
diff = 1

This version is wrong in y[1] on row 0110. A miter that compares every output sets diff to 1.

Constraints and Contract

  • Keep the module names miter and equiv_check, the task name sweep and its two output arguments.
  • The sweep must finish within 40 ns. Do not use $finish.

Hints

Hint 1

XOR the two output vectors bit by bit, then OR the bits together: any 1 means a difference.

Hint 2

A miter that compares only one output, or ANDs the bits, misses bugs that change one output only.

Hint 3

Wait after setting x, so the circuits settle before you read diff. Keep the first difference: later rows must not overwrite it.

What the grader checks: The checks grade your miter and sweep, not a circuit you design. Four checks run the sweep against the correct implementation and three seeded bugs, and compare the count and first row with JavaScript. Three checks apply single rows to the miter. With 4 inputs, 16 rows are a proof; a formal tool would be needed for wide inputs.

7 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

The Correct Implementation

Input
implementation 0
Expected output
rows_that_differ = 0, first_row = 'b0000

No row differs: the sweep returns 0 rows and first = 0000. That is the proof of equivalence.

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

Icarus · browser samples / server checks