Design lab: from a specification to a three-input majority circuit

Fix the conditions before implementing

Build a circuit with y=1 when at least two of inputs a, b and c are 1. Assume stable 0/1 inputs, equal weight for every input, and no memory of previous inputs. “Exactly two” and “at least two” define different functions at 111.

Each of the three terms means that a pair of inputs is simultaneously 1. The same function can be factored as $y=ab+c(a+b)$. Which implementation is faster depends on cells and arrival times.

Majority is a full adder's carry function

Read cin below as the third input c. cout is our y; sum is odd parity^{iParity A value indicating whether the number of 1 bits is odd or even. A parity check detects an odd number of bit errors but can miss an even number. Learn more}. Comparing 001 and 111 exposes the mistake of using parity as majority.

Derive the checking criterion independently from the specification

Copying (a & b) | (a & c) | (b & c) into a reference model can reproduce the same mistake. Instead, compute the specification's “at least two ones” with integers.

module voter3(input logic a, b, c, output logic y);
  assign y = (a & b) | (a & c) | (b & c);
endmodule

module tb;
  timeunit 1ns;
  timeprecision 1ps;
  logic a, b, c, y;
  int ones;
  voter3 dut(.*);
  initial begin
    for (int v = 0; v < 8; v++) begin
      {a, b, c} = v[2:0];
      #1;
      ones = int'(a) + int'(b) + int'(c);
      assert (y === (ones >= 2))
        else $fatal(1, "voter mismatch at %03b", {a,b,c});
    end
    $finish;
  end
endmodule

Each bit is extended to int to avoid ambiguity about one-bit arithmetic widths. #1 allows this test's combinational logic to update; it is not evidence that a physical chip operates in 1 ns.

Change the specification and find counterexamples

Adding an output enable e gives $y=e(ab+ac+bc)$. There are now four inputs, so exhaustive testing requires 16 combinations. Also check the invariant^{iInvariant A condition that must remain true in every permitted execution. For example, the occupancy of a depth-4 FIFO must always lie between 0 and 4. Learn more} that a, b and c are ignored whenever e=0.