Lab: A First Hardware Checker

Distance, Detection and Correction proved that a single parity check flags a received word exactly when an odd number of its bits have flipped, and Project: A Channel Simulator checked the code's undetected-error rate against a closed form, with every bit held in a Python integer. Both treated the checker as arithmetic. This chapter builds it as hardware, a circuit of logic gates described in SystemVerilog, a language chip designers use to describe circuits, and tests that circuit the way chip designers test theirs, by simulating it and comparing every output with an independent software model.

The circuit is small. A tree of six XOR gates makes the parity bit of a 7-bit message, a tree of seven gates checks the 8-bit word that arrives, and a bench joins the two through a channel that flips whichever bits the test chooses. Verilator, an open-source simulator, turns the description into a compiled program, and a testbench written with cocotb, a Python library for testing hardware, drives it with 800,000 words through a simulated binary symmetric channel at eight crossover probabilities, then with all 32,768 pairings of a message and an error pattern. Surfer displays the signals as a waveform, a picture of each signal against time, and Yosys, an open-source synthesis tool, reports the gates the description becomes. The share of damaged words the checker catches is finally set against a formula derived here, and two of eight Wilson intervals miss it.

The four SystemVerilog files sit in parity/ under the hdl/ folder of the companion repository ecc-book-lab, the cocotb testbench in tb/parity/ and the synthesis script in synth/. Every number the chapter prints is reproduced by ch12_lab_first_hardware_checker.py, which replays the testbench's random draws without any simulator, prints each value beside the value stated here, and stops at the first disagreement. The four computed figures are drawn by ch12_charts.py. Both scripts use only the Python standard library.

This chapter does not teach SystemVerilog or cocotb. Every listing arrives finished, and the text explains what the hardware does and proves why it is right. The languages themselves are taught from the beginning in RTL Design and Verification and in the material on hardware description languages in Computer Architecture. One notation note comes first. The listings call the number of message bits K, the name of a SystemVerilog parameter, and the prose writes it $k$, so a codeword has $n = k + 1$ bits, the same $n$ as in Distance, Detection and Correction, and 8 in the main experiment.

01.Setting Up

The lab needs five programs and one Python library, all open source and all available on macOS, Linux and Windows. Verilator simulates the hardware, and cocotb, the Python library the testbench is written in, supports Verilator from version 5.036 on [1]. cocotb needs Python 3.9 or newer together with libpython, the form of Python that another program can load [2], the repository's scripts need 3.10, and cocotb 2.1.0 refuses to install on any Python newer than 3.14, so the lab needs Python 3.10 to 3.14, as Setting Up the Lab Bench explains. Surfer displays the waveform, git fetches the repository, and Yosys, needed only for the gate counts of What Synthesis Builds, is optional. Verilator also needs a C++ compiler and make whenever it builds a design [3]. The steps below assume Python and git are installed, as in Project: A Channel Simulator.

Each step follows the official documentation of the tool it installs. The order of preference is the platform's own package manager, then the Windows Subsystem for Linux on Windows, and Docker only as a last resort.

macOS

Apple's Command Line Tools supply the C++ compiler and make. Homebrew's installation page names them, installed with xcode-select --install, as what building from source requires, and Verilator needs them on every run since every run compiles C++. Homebrew then installs the three tools, each from a formula of its own, and Surfer's documentation names Homebrew as the macOS route [4]. Homebrew's default python3 was Python 3.15.2 on 2026-11-14 [5], too new for cocotb, so the brew line also installs python@3.14, whose command is python3.14 [6].

When checked on 2026-11-14, Homebrew provided Verilator 5.054, Surfer 0.7.0 and Yosys 0.71. Surfer's prebuilt binary for Apple silicon is unsigned, and its documentation warns that most users will not be able to install it as it is.

Linux

The Verilator guide calls a distribution's package manager the easiest way to get started and points to Repology, a site that tracks the version each distribution packages [3]. On 2026-11-14 Repology listed Verilator 5.054 for Arch Linux and 5.046 for Fedora, both new enough for cocotb. The guide gives no command for either, so the lines below use the package names Repology lists, plus the compiler and make.

The guide's Git Quick Install, shown below without its optional packages, builds the latest stable release. The guide says to ignore an error from the three lines it marks Ubuntu only.

cocotb's installation page adds the packages Python needs to be loaded by a simulator, with sudo apt-get install make python3 python3-pip libpython3-dev on Debian and Ubuntu and sudo yum install make python3 python3-pip python3-libs on Red Hat systems. It gives no line for Arch, whose Verilator package already depends on python.

Surfer's documentation lists the distributions that package it and offers prebuilt binaries for x86 Linux, Rocky Linux and ARM Linux. Otherwise Surfer builds from source with cargo, the package manager of the Rust language, once Rust is installed as rust-lang.org describes.

The Yosys documentation calls the OSS CAD Suite, nightly builds of the open-source hardware tools for Linux, macOS and Windows, the easiest route, and adds that many distributions package Yosys, without naming the commands [7]. The gate counts in this chapter were measured with Yosys 0.71.

Windows

The Verilator guide names WSL2, version 2 of the Windows Subsystem for Linux, among the platforms Verilator has been built on, and cocotb's installation page sends Windows users either to Conda or to WSL, following the Linux steps. This lab takes WSL2 with ArchWSL, set up as Project: A Channel Simulator describes, because Arch Linux carries a Verilator new enough for cocotb. Inside ArchWSL one pacman command installs the toolchain.

The package names come from Arch's own package list, since no Verilator, cocotb or Yosys page covers this step.

Surfer's prebuilt Windows binary runs on the Windows side, and its documentation warns that Windows Defender may wrongly flag it. Surfer's README says the program can also run inside WSL, prefers starting the faster Windows version from WSL through the repository's surfer.sh script, and warns that WSL has several issues [8].

Containers

Docker comes last. The Verilator guide publishes an executable container image, verilator/verilator, that runs Verilator itself, as in docker run -ti verilator/verilator:latest --version. No official page describes a container that also holds cocotb, so a reader taking that route builds the Linux steps into an image of their own [3].

Cloning and Running

The commands below fetch the repository, create a virtual environment, a private folder of Python packages that leaves the system's Python untouched, install cocotb into it, and run the lab. Python's documentation gives the lines that create and activate the environment [9], and cocotb's installation page the two that install and check it.

On Linux and in WSL the third line reads python3 -m venv .venv wherever python3 --version reports 3.10 to 3.14, and otherwise names an installed interpreter inside that window, such as python3.12. The specifier ~=2.1 asks for the newest release from 2.1 up to, but not including, 3.0. Every new terminal needs the source line again. On Debian and Ubuntu the venv module is a separate package, which the Python Packaging User Guide installs with sudo apt install python3-venv [10]. The second-to-last line needs Yosys and can be skipped. The last needs no simulator at all and ends with All chapter 12 numbers reproduced.

02.The Bench at a Glance

Unlike the Python simulator of the last chapter, Verilator reads the SystemVerilog, writes a C++ program that computes the same signals, and compiles it. cocotb then loads Python into that program, and each test is a Python function that writes values onto the design's inputs, lets simulated time move forward, and reads the outputs back. Figure 1 shows how the files and the tools fit together.

The design under test is the bench of Figure 2, with five signals. The test drives data, a 7-bit message, and error_mask, an 8-bit pattern. The generator turns data into codeword, 8 bits of even weight, where the weight of a word, written $w(\cdot)$ as in Distance, Detection and Correction, is its number of 1 bits. The channel flips every codeword bit wherever the mask holds a 1 and delivers received, and the checker raises error when the received word has odd weight.

Every block is combinational. Nothing is stored, so after a change at the inputs the outputs settle to new values that depend on those inputs alone. The test therefore holds each pair of data and error_mask for 10 ns of simulated time, reads the outputs, and moves on. The channel sits in the bench rather than inside the generator or the checker because a checker in a real chip sees whatever the wires deliver, and the only way to test it is to hand it corrupted words on purpose. That is fault injection, and the mask is how the test chooses the corruption.

03.One Tree of XOR Gates

An XOR gate has two inputs and one output, and the output is 1 when exactly one input is 1, so $0 \oplus 0 = 0$, $0 \oplus 1 = 1 \oplus 0 = 1$ and $1 \oplus 1 = 0$. The symbol $\oplus$ is the exclusive OR, the same as addition modulo 2, which keeps only the last binary digit of a sum. Chaining it, the XOR of many bits is 1 exactly when an odd number of them are 1, which is the parity of the bits.

Take the message 1101100, written as all binary strings in this chapter are, highest bit first. Naming its bits $d_6$ down to $d_0$, so that $d_i$ sits at position $i$, gives $d_6 = 1$, $d_5 = 1$, $d_4 = 0$, $d_3 = 1$, $d_2 = 1$, $d_1 = 0$ and $d_0 = 0$. Four bits are 1, so the parity bit is 0. The hardware finds that 0 by splitting. It divides the seven bits into a low group of three, $d_0 d_1 d_2 = 0, 0, 1$, and a high group of four, $d_3 d_4 d_5 d_6 = 1, 0, 1, 1$. The low group splits again into $d_0$ alone and the pair $d_1, d_2$, so one gate forms $d_1 \oplus d_2 = 1$ and a second forms $d_0 \oplus 1 = 1$. The high group splits into two pairs, giving $d_3 \oplus d_4 = 1$ and $d_5 \oplus d_6 = 0$, and a third gate combines them to $1 \oplus 0 = 1$. The last gate, the root, combines the two groups, $1 \oplus 1 = 0$. Six gates have been used, and the longest route any bit takes, from $d_6$ for instance, passes through three of them. The codeword places the parity bit on top of the message, 01101100.

Chaining the six gates, $((d_0 \oplus d_1) \oplus d_2) \oplus \cdots$, gives the same answer, since exclusive OR does not care how its inputs are grouped, but the signal from $d_0$ would then pass through all six. Each gate takes a moment to respond, so the longest route sets how soon the output can be trusted, and the tree cuts it from six gates to three. The file xor_tree.sv builds such a tree for any number of inputs.

The module calls itself, once for each half, and the if (W == 1) branch stops the descent at a single bit. The recursion happens only when a tool reads the design and fixes the parameter W, the number of inputs, at a value. The hardware it describes is a fixed tree, and nothing recurses while the circuit runs. Two quantities measure the tree. Write $G(W)$ for its number of gates and $D(W)$ for its depth, the largest number of gates on a path from an input to the output. The rounding-up function $\lceil x \rceil$ returns the smallest whole number at least $x$, and $\log_2 W$ is the power to which 2 must be raised to give $W$.

Proof. Both claims go by strong induction on $W$, which assumes the claim for every width below $W$ and proves it for $W$. A single input needs no gate and has depth 0, which matches $1 - 1 = 0$ and $\lceil \log_2 1 \rceil = 0$. For $W \ge 2$ the tree splits into a low half of $L = \lfloor W/2 \rfloor$ inputs, where $\lfloor x \rfloor$ rounds down, and a high half of $H = W - L = \lceil W/2 \rceil$ inputs, both smaller than $W$, and adds one gate. The gate count is then $(L - 1) + (H - 1) + 1 = W - 1$.

For the depth, the deepest path runs through the deeper half and then through the root, so $D(W) = 1 + \max(D(L), D(H))$. Since $L \le H$ and rounding $\log_2$ up never decreases as its argument grows, the induction hypothesis gives $D(L) \le D(H)$, and $D(W) = 1 + \lceil \log_2 H \rceil$. Let $m = \lceil \log_2 W \rceil$, so that $2^{m-1} < W \le 2^m$ with $m \ge 1$. Halving, then rounding $W/2$ up to $H$, gives

$$2^{m-2} < \frac{W}{2} \le H = \left\lceil \frac{W}{2} \right\rceil \le 2^{m-1},$$

where the last step holds because $2^{m-1}$ is a whole number no smaller than $W/2$, and rounding up never passes such a number. A whole number in that range has $\lceil \log_2 H \rceil = m - 1$, so $D(W) = 1 + (m - 1) = m$. $\blacksquare$

No tree of two-input gates can be shallower, since a tree of depth $d$ has at most $2^d$ inputs, which Exercise: No Shallower Tree proves. Figure 3 draws the generator's tree for $k = 7$, with the deepest path of the 1101100 example, the one from $d_6$, picked out.

04.The Generator and the Checker

The generator is a tree over the $k$ message bits with the parity bit placed on top. Its port codeword is $k + 1$ bits wide, and the braces in {parity, data} join two signals side by side, the first in the high positions.

The checker is a tree over all $n$ bits of the received word. It needs no knowledge of which bit was the parity bit, because a codeword is any word of even weight and the tree reports the parity of whatever arrives.

Suppose 01101100 is sent and bit 2 flips. The checker sees 01101000, three bits are 1, and error rises. If bit 5 flips as well, the word 01001000 has two 1 bits and passes unflagged although it is wrong. The theorem What Single Parity Catches and Misses in Distance, Detection and Correction made that rule exact for the arithmetic. Its hardware form adds one step, showing that the tree computes the XOR of its inputs whatever its shape.

Proof. A tree computes the XOR of all its inputs, by induction on the width. A single input is its own XOR, and for a wider tree the root combines the XOR of the low inputs with the XOR of the high inputs, which is the XOR of all of them because exclusive OR, like ordinary addition, can be regrouped and reordered freely. The checker therefore outputs $r_0 \oplus r_1 \oplus \cdots \oplus r_{n-1}$, where $r_i = c_i \oplus e_i$ is bit $i$ of the received word. Regrouping splits this into $(c_0 \oplus \cdots \oplus c_{n-1}) \oplus (e_0 \oplus \cdots \oplus e_{n-1})$. The first group is the XOR of the message bits combined with the parity bit, which is that same XOR again, and anything combined with itself gives 0. The second group is 1 exactly when an odd number of the $e_i$ are 1, which is $w(e) \bmod 2$. $\blacksquare$

The checker's tree for $n = 8$ appears in Figure 4. Eight is a power of 2, so the tree is perfectly balanced, four bits to a side and two to each pair, and its depth equals the generator's even though it holds one gate more.

The bench joins the two. Its single line of channel, assign received = codeword ^ error_mask;, is a row of eight XOR gates, one for each bit, and the operator ^ is SystemVerilog's exclusive OR applied bit by bit.

05.The Testbench

The testbench tb/parity/test_parity.py never trusts the hardware's answer. It computes the right answer separately, with a model short enough to read at a glance, and compares. The model is the excerpt below. Here & and | are bitwise AND and OR on Python integers, and << k shifts a bit up to position $k$.

The function apply drives one pair of inputs, lets 10 ns of simulated time pass, and checks all three outputs. If the codeword, the received word or the flag disagrees with the model, an assert statement stops the test and prints the values that disagreed. Every vector of every test passes through these checks.

The random inputs come from bsc_stream, which draws each data bit as 1 with probability one half and builds each mask the way Building the Channels in Project: A Channel Simulator built the binary symmetric channel $\text{BSC}(p)$, the channel that flips each bit independently with crossover probability $p$. One uniform draw $u$ between 0 and 1 is made for each of the 8 bits, and the bit flips when $u < p$, which happens with probability $p$.

Two generators keep the data and the channel apart, as in the last chapter. The data generator starts from seed 1,000,000,012 and the channel generator from seed 12, and both restart for every crossover probability, so all eight values of $p$ see the same data words and the same uniform draws. Python's generator is the Mersenne Twister of Matsumoto and Nishimura [11], and the Python documentation guarantees that its random() method reproduces the same sequence for the same seed across Python versions. That guarantee is what lets the companion script replay any stretch of any run without a simulator.

Figure 5 shows the loop of the test test_bsc_faults. For each word it records three things. A word is damaged when its mask is not zero, flagged when the checker raises error, and slipped when it is damaged but not flagged, an undetected error. A flagged word must be damaged, since a clean codeword has even weight, so the flagged count is also the caught count.

06.Running the Lab

The runner tb/parity/run_parity.py builds the bench three times, and the list below names each build, its value of $K$, its tests and whether it records a waveform. The second build exists only to keep the waveform short, and the third shows the same design working at a second width, the code of length 4.

Each build turns on Verilator's lint and style warnings with -Wall, and Verilator treats any warning as fatal unless told otherwise, so a build that completes raised none. The test log then carries one line per crossover probability and a last line for the exhaustive test. Three of them are shown below, the first $p$, the first interval that misses, and the exhaustive count.

The fields read left to right. The time stamp is simulated time, which advances by 10 ns per word, so the eight runs of 100,000 words end at 8,000,000 ns. Then come the counts, the measured detection coverage, its Wilson interval, the formula's value and a verdict on whether the interval contains it. A passing run ends each build with a summary line reporting no failures, TESTS=3 PASS=3 FAIL=0 for the first build. The test test_clean_words also sends all 128 messages with no fault and checks that each codeword has even weight and passes unflagged.

07.Every Error Pattern, Exhaustively

Random vectors can miss a corner. For a design this small there is no need to sample, because the test test_exhaustive drives every message against every mask. For $k = 3$ that is $2^3 \times 2^4 = 128$ vectors, of which the checker flagged 64 and 56 slipped. For $k = 7$ it is $2^7 \times 2^8 = 32{,}768$ vectors, with 16,384 flagged and 16,256 slipped, 128 flagged and 127 slipped for each message. The test also asserts, vector by vector, that the flag equals $w(e) \bmod 2$, so the theorem What the Checker Reports has been checked on every input the 8-bit bench can receive.

For each message the checker sees all $2^n$ masks, and it flags the ones of odd weight.

Proof. Flipping bit 0 turns each mask into another one, and doing it twice gives back the original, so the masks fall into pairs. The two masks of a pair differ in exactly one bit, so their weights differ by one, and one of them is odd and the other even. Each pair therefore holds one odd mask, and there are $2^n / 2 = 2^{n-1}$ pairs. The all-zero mask is even and is the one even mask that does no damage. $\blacksquare$

For $n = 8$ the lemma gives 128 flagged masks and 127 slipped ones for each message, so of the 255 masks that damage a word, $127/255 = 0.498$ slip through. That fraction counts patterns, not probabilities. On a real channel a heavy mask is far rarer than a light one, which is why the measured detection coverage below is much higher than one half at small $p$.

Exhaustive testing does not scale. The number of vectors is $2^k \times 2^{k+1} = 2^{2k+1}$, which doubles twice for every bit added to the message, and a checker for 32-bit codewords would need $2^{63}$ vectors. Proving a design correct for every input without trying them one by one is the job of formal verification.

08.Reading the Waveform in Surfer

The build k7-wave runs only the test test_waveform, which sends the first 12 words of the $p = 0.2$ run, one every 10 ns. With tracing on, cocotb's Verilator support writes the signals to a file named dump.vcd [1]. A VCD file, short for value change dump, is plain text that lists the value of every signal each time it changes, and Surfer opens it with the command at the top of the command file below.

Surfer's option --command-file runs the commands in a file once the waveform has loaded, though Surfer's help marks the option as temporary, and variable_add adds one signal to the view by its full name [12]. The same commands can be typed one at a time into Surfer's command prompt, which the space bar opens.

Figure 6 draws those 12 words in the layout of a waveform viewer, redrawn from the replay rather than captured from Surfer, and Table 1 lists them. Each multi-bit signal is drawn as a band holding its value, here in binary, and the band changes wherever the value does. The single-bit error is drawn as a line that is high for 1 and low for 0.

Example: One Word Through the Bench follows the word at 20 ns through every signal. Down the whole window error is high exactly where the mask weight is odd, at 20, 30, 50, 60 and 70 ns. The other seven words were all damaged too, every one by an even number of flips, and the checker passed each of them. At $p = 0.2$ a word slips with probability 0.341, so twelve words expect about 4.1 slips, and seven or more happens about 7% of the time, an unlucky stretch rather than a strange one.

09.Measured Coverage Against the Formula

At $p = 0.01$ the test sent 100,000 words. Of them, 7,640 were damaged, the checker flagged 7,379, and 261 slipped past it, so the checker caught $7{,}379/7{,}640 = 0.96584$ of the damaged words. Whether that number is right depends on what the checker ought to catch, and that has a closed form.

Project: A Channel Simulator used coverage for the share of intervals that contain the true value, and this section needs both meanings.

On $\text{BSC}(p)$ a word survives undamaged only if all $n$ bits survive, so $P_{\text{damaged}} = 1 - (1 - p)^n$. The alarm needs an odd number of flips. Write $E$ for the probability of an even number and $O$ for an odd number. Exactly $j$ flips has probability $\binom{n}{j} p^j (1 - p)^{n - j}$, where $\binom{n}{j}$ counts the ways to choose which $j$ bits flip, and the binomial theorem sums these terms twice, once as they stand and once with the sign $(-1)^j$, which is $+1$ for even $j$ and $-1$ for odd.

$$\begin{aligned} E + O &= \sum_{j=0}^{n} \binom{n}{j} p^j (1 - p)^{n - j} = \bigl((1 - p) + p\bigr)^n = 1, \\ E - O &= \sum_{j=0}^{n} \binom{n}{j} (-p)^j (1 - p)^{n - j} = \bigl((1 - p) - p\bigr)^n = (1 - 2p)^n. \end{aligned}$$

Subtracting the second line from the first gives $2O = 1 - (1 - 2p)^n$, which is the theorem Undetected Errors of Single Parity of Project: A Channel Simulator seen from the other side.

For $n = 8$ and $p = 0.01$ the formula gives $C = 0.96587$, worked step by step in Example: The Closed Forms at p = 0.01, and the measured 0.96584 sits close to it. A short approximation explains the size. When $p$ is small, nearly every damaged word has one flip and nearly every slipped word has two, and the ratio of the two probabilities is $\binom{n}{2} p^2 / (np) = (n - 1)p/2$. So $C \approx 1 - (n - 1)p/2 = 0.965$, and the checker loses about 3.5% of damaged words at $p = 0.01$ because about that share of damaged words carry a second flip.

The measured coverage is a count of successes among a count of trials, so it gets a Wilson interval [13], with one care about what the trials are. The number of damaged words $D$ is itself random. But given which words were damaged, each damaged word's mask is an independent draw from the channel's masks, given that it is not zero, and so is flagged with probability $C$, so the caught count is binomial with $D$ trials and success probability $C$. The interval of Intervals That Miss in Project: A Channel Simulator therefore applies to the caught count over $D$, and its half-width is about $1.96\sqrt{C(1 - C)/D}$, which is 0.0041 at $p = 0.01$. Table 2 gives all eight runs.

Six intervals contain the formula and two miss, at $p = 0.1$ and $p = 0.3$, as Figure 7 shows. Measured in standard deviations of the binomial count, the caught count at $p = 0.1$ lies 2.59 below its expected value and the one at $p = 0.3$ lies 2.23 below. Eight 95% intervals expect $8 \times 0.05 = 0.4$ misses, so two is more than expected, though Exercise: Two Misses in Eight finds that two or more would happen with probability 0.057, about one chance in 17, even if the eight intervals were independent. That is unusual but not alarming.

The intervals are not fully independent, because every value of $p$ reuses the same uniform draws. A draw below 0.1 is also below 0.3, so every bit flipped at $p = 0.1$ is also flipped at $p = 0.3$, and the damaged counts in Table 2 can only rise. The nesting ties runs together most at small $p$, where most masks at $p = 0.02$ are the masks at $p = 0.01$ unchanged, and hardly at all between 0.1 and 0.3, where the added flips make each mask's parity close to a fresh coin toss. Over seeds 0 to 399, 5,000 words each, the companion script finds a correlation of 0.43 between the standardized differences at $p = 0.01$ and $0.02$, and 0.02, no different from zero, at $p = 0.1$ and $0.3$. The two runs that missed are close to independent.

A cleaner test of the interval separates the seeds. The companion script repeats the $p = 0.1$ experiment with seeds 0 to 299, 20,000 words each, and 12 of those 300 intervals miss the formula, 4% against the 5% a 95% interval promises, with a Wilson interval of 0.023 to 0.069 on that share. The 300 standardized differences have mean $-0.09$ and standard deviation 0.97, close to the 0 and 1 of a standard normal variable. The two misses with seed 12 are chance, and they stay in the table, because changing the seed to remove them would be the seed shopping that Project: A Channel Simulator warned against.

The same run also measures the undetected-error rate, 261 slips in 100,000 words, or 0.00261, with a Wilson interval from 0.00231 to 0.00295. The closed form $P_{\text{ud}} = \bigl(1 + (1 - 2p)^n\bigr)/2 - (1 - p)^n = 0.0026368$ lies inside. A slip is rare, so Example: Words for the Undetected Rate finds that 100,000 words measure this rate only to about 12%, while detection coverage is pinned to within 0.0041.

10.What Synthesis Builds

The theorem Size and Depth of the XOR Tree counts gates in the description. Synthesis shows what a tool builds from it. The script synth/synth_parity.py asks Yosys to synthesize the generator and the checker at codeword lengths 8, 16, 32 and 64, flattening each design into a single netlist and counting its cells, the gates of Yosys's own small library, and the cells on its longest path from input to output. Table 3 gives the result.

Every gate count is $W - 1$ and every depth is $\lceil \log_2 W \rceil$, so Yosys reaches both of the theorem's figures, which no tree of two-input gates can beat. Each netlist is also a tree, because $W - 1$ two-input cells have $2(W - 1)$ cell inputs, and the $W$ inputs and the $W - 2$ outputs that are not the result fill them exactly once each. But the netlists hold two kinds of cell. Some are XOR gates, and others are XNOR gates, whose output is the opposite of XOR's, 1 when the two inputs agree, and the wrong mix would compute the wrong function.

Proof. XNOR is 1 exactly when XOR is 0, which is what combining with 1 does, so each XNOR gate equals an XOR gate with an extra input fixed at 1. The tree then computes the XOR of all its true inputs and of $x$ constant 1s, and regrouping collects the constants into $1 \oplus \cdots \oplus 1$, $x$ times, which is $x \bmod 2$. $\blacksquare$

Every XNOR count in Table 3 is even, 6, 10, 22 and 42 for the generators and 4, 10, 20 and 42 for the checkers, so every netlist computes the parity. The generator at $n = 8$ is built of XNOR gates alone, six of them, and the inversions cancel in pairs. The script checks each count, each depth and each XNOR count, and it ends with Every gate count is W - 1, every depth is ceil(log2 W), every XNOR count is even.

11.Looking Ahead

Part I ends here, with the simplest code carried into gates. Every code after parity needs arithmetic that parity hides. A Hamming code's checks are several parity sums at once, chosen by a matrix, and a Reed–Solomon code does its arithmetic in a finite field, a small number system in which division by any nonzero number works.

Part II, Linear Block Codes, therefore opens with arithmetic modulo a whole number, from divisibility and Euclid's algorithm through the theorems of Fermat and Euler to the integers modulo a prime $p$, written $\mathbb{Z}_p$, the first finite field. The XOR gate of this chapter is already arithmetic in the smallest of them, $\mathbb{Z}_2$, the integers modulo 2, where $1 + 1 = 0$.

12.Worked Examples

13.Exercises

References

1. [1]cocotb Project “Simulator Support.” cocotb 2.1 documentation. Read 2026-11-14. https://docs.cocotb.org/en/stable/simulator_support.html
2. [2]cocotb Project “Installation.” cocotb 2.1 documentation. Read 2026-11-14. https://docs.cocotb.org/en/stable/install.html
3. [3]Verilator Project “Installation.” Verilator 5.054 documentation. Read 2026-11-14. https://verilator.org/guide/latest/install.html
4. [4]Surfer Project “Introduction.” The Surfer book. Read 2026-11-14. https://docs.surfer-project.org/book/
5. [5]Homebrew Project “python@3.15.” Homebrew Formulae. Read 2026-11-14. https://formulae.brew.sh/formula/python@3.15
6. [6]Homebrew Project “python@3.14.” Homebrew Formulae. Read 2026-11-14. https://formulae.brew.sh/formula/python@3.14
7. [7]YosysHQ “Installation.” Yosys documentation. Read 2026-11-14. https://yosyshq.readthedocs.io/projects/yosys/en/latest/getting_started/installation.html
8. [8]Surfer Project “Surfer.” Project README on GitLab. Read 2026-11-14. https://gitlab.com/surfer-project/surfer
9. [9]Python Software Foundation “venv: Creation of virtual environments.” The Python 3 documentation. Read 2026-11-14. https://docs.python.org/3/library/venv.html
10. [10]Python Packaging Authority “Installing pip/setuptools/wheel with Linux Package Managers.” Python Packaging User Guide. Read 2026-11-14. https://packaging.python.org/en/latest/guides/installing-using-linux-tools/
11. [11]Matsumoto, Makoto and Nishimura, Takuji (1998). “Mersenne Twister: A 623-Dimensionally Equidistributed Uniform Pseudo-Random Number Generator.” ACM Transactions on Modeling and Computer Simulation, 8(1), pp. 3–30. doi:10.1145/272991.272995
12. [12]Surfer Project “Commands.” The Surfer book. Read 2026-11-14. https://docs.surfer-project.org/book/commands/index.html
13. [13]Wilson, Edwin B. (1927). “Probable Inference, the Law of Succession, and Statistical Inference.” Journal of the American Statistical Association, 22(158), pp. 209–212. doi:10.1080/01621459.1927.10502953
14. [14]Hanley, James A. and Lippman-Hand, Abby (1983). “If Nothing Goes Wrong, Is Everything All Right? Interpreting Zero Numerators.” JAMA, 249(13), pp. 1743–1745. doi:10.1001/jama.1983.03330370053031