Paper
Part IILinear Block Codes

Project: A SEC-DED Encoder and Decoder

November 16, 202649 min readbeginner

Building the (72,64) SEC-DED encoder and decoder of a 64-bit memory port in two codes, checking it against a model, proving it with a solver, and counting the gates and levels Yosys really builds.

SECDED and Hsiao Codes compared two (72,64) codes on paper, the extended Hamming code and Hsiao's code, by counting the ones in their check matrices and predicting the gates and gate delays each would cost. This project builds both. It writes the encoder and decoder of a 64-bit memory port, generic over the check matrix, checks them against a software model on 2,802,514 simulated cases per code, proves them correct with a solver for all 2642^{64} data words, and synthesizes them to test the predictions. Some predictions hold exactly, one reverses, and the reasons are the most useful part of the chapter.

Every number in the chapter is recomputed by ch30_project_secded_encoder_and_decoder.py in the python/ folder of the companion repository ecc-book-lab, and the charts are drawn by ch30_charts.py in the same folder. The GNU Octave twin ch30_project_secded_encoder_and_decoder.m prints the same lines, as The Octave Route explains. The hardware is in hdl/, the cocotb bench that simulates it is in tb/, and the formal runner is in formal/, each under a secded72 subfolder, while the synthesis script is in synth/. The bench and the formal runner are driven from Python and have no Octave twin.

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.

01.Setting Up

Setting Up the Lab Bench installs the tools and a Python virtual environment holding cocotb. The results were measured with the versions it records for 2026-11-14, Verilator 5.054, Yosys 0.71, SymbiYosys 0.71 and Z3 5.4.1, and the Yosys build was git 5628c13. With that environment active, the five commands below, run from the root of the companion repository, reproduce every hardware result in the chapter.

Bash
python tb/secded72/check_secded72.py
python tb/secded72/run_secded72.py
python tb/secded72/run_secded72.py --flag parity
python synth/synth_secded72.py
python formal/secded72/run_formal72.py

The first ties every matrix to SECDED and Hsiao Codes, the second and third run the bench with each form of the uncorrectable flag, the fourth synthesizes every block and compares the counts with the recorded data, and the fifth runs the nine formal tasks. On the recorded run each bench command took about a minute and a half and the formal tasks about eight minutes. The option --code picks one code, and the exercises use it.

02.A 64-Bit Word Behind a Memory Port

Where the SEC-DED logic sits in a memory port. On the write path, 64 bits of write data enter the encoder, eight XOR trees, which adds 8 check bits and stores a 72-bit word in the memory. On the read path, the 72-bit word leaves the memory and enters the decoder, which returns 64 bits of read data and two flags, corrected and uncorrectable. A note under the encoder says the gate count sets area, paid again at every port, and a dimension line under the read path says the logic depth there adds latency to every load. Encoder 8 XOR trees Memory 72-bit words, 64 data and 8 check Decoder syndrome, match, correct, flags 64 72 72 64 write data read data corrected uncorrectable Write path: on every store Read path: on every load gate count sets area, paid again at every port logic depth on the read path adds latency to every load
Figure 1. The encoder and decoder in a memory port. Gates cost area at every port, and levels on the read path cost latency on every load.

Figure 1 shows where the logic sits. A 64-bit word on its way into memory passes through the encoder, which appends 8 check bits, and the memory stores all 72. On the way out, the decoder returns 64 data bits and two flags. The flag corrected says that one bit was wrong and has been put right, and uncorrectable says that the word holds an error the code cannot repair. Its gates are area, paid again at every port, and its gate delays between the memory and the data output are latency, added to every load.

The decoder must keep a precise promise, which Verifying ECC Hardware calls the guarantee, over a set of error patterns it calls the design envelope. Write dd for the 64-bit data word, cc for its 72-bit codeword, ee for the 72-bit error pattern with a 1 wherever the memory flipped a bit, and wt(e)\mathrm{wt}(e) for the number of ones in ee. The decoder sees c⊕ec \oplus e, where ⊕\oplus is bitwise XOR, and returns its data output, corrected and uncorrectable.

D(c⊕e)={(d, 0, 0)if wt(e)=0,(d, 1, 0)if wt(e)=1,(d⊕eD, 0, 1)if wt(e)=2.D(c \oplus e) = \begin{cases} (d,\ 0,\ 0) & \text{if } \mathrm{wt}(e) = 0,\\ (d,\ 1,\ 0) & \text{if } \mathrm{wt}(e) = 1,\\ (d \oplus e_{\mathrm{D}},\ 0,\ 1) & \text{if } \mathrm{wt}(e) = 2. \end{cases}
(1)

Here eDe_{\mathrm{D}} is the 64-bit data part of ee, so on a double error the decoder passes the received data bits through untouched and raises uncorrectable. The envelope holds 1+72+(722)=1+72+2,556=2,6291 + 72 + \binom{72}{2} = 1 + 72 + 2{,}556 = 2{,}629 patterns, where (722)\binom{72}{2} counts the ways to choose two of the 72 positions. Beyond it the code promises nothing.

03.Architecture Decisions

Four decisions shape the design. The first is the code. SECDED and Hsiao Codes predicted that Hsiao's matrix [1], with 216 ones and no row heavier than 27, needs 208 XOR gates in 5 levels for its syndrome, against 276 gates in 7 levels for the extended Hamming matrix [2], whose 284 ones include a 72-input parity row. Hsiao is the default, and extended Hamming is built beside it so that the prediction is tested rather than assumed.

The second is genericity. Every module takes one parameter, CODE, naming a code in a generated package of constants, and derives its widths N and K from it, so no one can set a width that disagrees with the matrix. The third is that neither block holds a register. A combinational decoder adds gate delays but no clock cycle, and leaves the placement of any register to the design around it.

The fourth is the bit order. The Hsiao codeword puts the data at positions 0 to 63 and the check bits at 64 to 71. The extended Hamming codeword keeps the order of SECDED and Hsiao Codes, with check bits at positions 0, 1, 2, 4, 8, 16, 32 and 64 and data in the other positions in increasing order, so the low seven bits of the column at position jj spell jj in binary. The interface of the decoder, from hdl/secded72/secded72_dec.sv, is the contract every check in the chapter tests.

SystemVerilog
module secded72_dec #(
parameter int CODE = secded72_pkg::HSIAO, // which code of secded72_pkg.sv
parameter int FLAG = 0, // 0: no-match form, 1: parity form
parameter int N = secded72_pkg::n_of(CODE), // derived from CODE; never set by hand
parameter int K = secded72_pkg::k_of(CODE) // derived from CODE; never set by hand
) (
input logic [N-1:0] received, // bit j is codeword position j
output logic [K-1:0] data, // the corrected data bits
output logic corrected, // a single error was corrected
output logic uncorrectable // the word holds an error it cannot correct
);

The parameter FLAG picks one of two ways to compute uncorrectable, and a later section proves that they agree everywhere the guarantee speaks.

04.One Source for Every Matrix

Two copies of a matrix, one in the hardware and one in the model that checks it, can drift apart, so the project writes each matrix once, as a list of columns in tb/secded72/secded72_model.py, where each column is an 8-bit number whose bit ii is the entry in row ii. The Hsiao list is the 56 weight-3 columns, one for each choice of three of the eight rows, then the eight cyclic rotations of the weight-5 column with ones in rows 0 to 4, then the eight weight-1 check columns. The extended Hamming list puts at position jj the number jj in rows 0 to 6 and a 1 in row 7, the overall parity row.

The two (72,64) check matrices, one square for each 1 ones Hsiao (72,64), balanced, 216 ones, largest row 27 s0 27 s1 27 s2 27 s3 27 s4 27 s5 27 s6 27 s7 27 0 8 16 24 32 40 48 56 64 71 Extended Hamming (72,64), 284 ones, largest row 72 s0 36 s1 36 s2 36 s3 32 s4 32 s5 32 s6 8 s7 72 0 8 16 24 32 40 48 56 64 71 Column = bit position 0 to 71 of the stored word, row = syndrome bit. marks a check-bit position, whose 1s are drawn in green.
Figure 2. The two (72,64) check matrices, a square for each 1. The Hsiao rows are balanced at 27 ones each, while the extended Hamming rows run from 8 to 72. Data: drawn by ch30_charts.py from the matrices of ch20_secded_and_hsiao_codes.py, which check_secded72.py checks against secded72_model.py.

Figure 2 draws both, and the balance of the Hsiao rows follows from the construction. A row lies in (72)=21\binom{7}{2} = 21 weight-3 columns, since the other two rows of such a column can be any two of the remaining seven, in 5 of the 8 rotations, and in one check column, so every row holds 21+5+1=2721 + 5 + 1 = 27 ones. The extended Hamming rows run from 8 ones in row 6, which only positions 64 to 71 reach, to 72 in the parity row.

Two scripts guard the list. tb/secded72/gen_secded72_pkg.py writes hdl/secded72/secded72_pkg.sv from the model, with each code's columns, rows, positions and encoder masks, and with --check reports whether the package on disk is current. tb/secded72/check_secded72.py compares every column list with the one the script of SECDED and Hsiao Codes builds, checks that the columns are distinct and nonzero with no three summing to zero, which makes the minimum distance at least four, and runs the package check. The bench runner calls it first, so a drifted matrix stops the run before a single case.

05.The Encoder

An encoder chooses check bits that make every row of the check matrix sum to zero over the codeword. Write HH for the 8×728 \times 72 check matrix over GF(2)\mathrm{GF}(2), the arithmetic of single bits in which addition is XOR and multiplication is AND, HijH_{ij} for its entry in row ii and column jj, and rjr_j for bit jj of a 72-bit word rr. The syndrome of rr has the bits

si=⨁j=071Hij rj,i=0,1,…,7,s_i = \bigoplus_{j=0}^{71} H_{ij}\, r_j, \qquad i = 0, 1, \ldots, 7,
(2)

so sis_i is the XOR of the bits row ii covers, and rr is a codeword exactly when all eight are zero.

Proof. The column at position 64+t64 + t has its single 1 in row tt, so row tt covers one check bit, the one at position 64+t64 + t, besides its data bits. Setting st=0s_t = 0 in Equation 2 says that this check bit XORed with those data bits is zero, and XORing both sides with the data bits gives the check bit as their XOR. Each row holds its own check bit and no other, so the eight choices do not interfere. ■\blacksquare

Each Hsiao row holds 27 ones, one of them the check bit, so each check bit is a 26-input XOR. The next lemma says what such a gate costs.

Proof. Each gate of a tree takes two signals and returns one, so it lowers by one the number still to be combined, and going from ww signals to one takes w−1w - 1 gates. For depth, an input at level 0 depends on 20=12^0 = 1 input. A gate at level ℓ\ell combines two signals of level at most ℓ−1\ell - 1, each depending on at most 2ℓ−12^{\ell - 1} inputs, so it depends on at most 2ℓ2^{\ell}. An output depending on ww inputs therefore has 2ℓ≥w2^{\ell} \ge w, and since ℓ\ell is a whole number, ℓ≥⌈log⁡2w⌉\ell \ge \lceil \log_2 w \rceil. A balanced tree halves the number of signals at each level, rounding up, and leaves one after exactly ⌈log⁡2w⌉\lceil \log_2 w \rceil levels. ■\blacksquare

The Hsiao encoder is therefore eight trees of 25 gates, 200 in all, each ⌈log⁡226⌉=5\lceil \log_2 26 \rceil = 5 levels deep. Extended Hamming is less obliging, since its parity row covers every check column, so the model solves the eight check equations by Gauss-Jordan elimination, the row reduction that turns the check columns into the identity, and reads off for each check bit a mask of the data bits it XORs. The masks hold 35, 35, 35, 35, 31, 31, 31 and 7 data bits, which makes 232 gates as separate trees, 6 levels deep. The encoder, from hdl/secded72/secded72_enc.sv, is two loops the package fills in.

SystemVerilog
for (genvar b = 0; b < K; b++) begin : g_data
localparam int P = int'(DATA_POS[8*b +: 8]);
assign codeword[P] = data[b];
end
for (genvar t = 0; t < R; t++) begin : g_check
localparam int P = int'(CHECK_POS[8*t +: 8]);
localparam logic [K-1:0] MASK = CHECK_MASKS[MAX_K*t +: K];
assign codeword[P] = ^(data & MASK);
end

The first loop copies each data bit to its position, and the second makes each check bit the XOR of the data bits its mask selects, since the unary ^ of SystemVerilog XORs every bit of its operand. One body serves every matrix because the positions and masks are package constants.

06.The Decoder

The (72,64) decoder, stage by stage. The 72 received bits enter a syndrome block of eight XOR trees, 208 XOR gates for Hsiao and 276 for extended Hamming, which gives the 8-bit syndrome s. Each of 72 comparators is an AND gate over the eight syndrome bits, with an inversion bubble on every bit where its column holds a 0, so 72 times 7 makes 504 AND gates, and together they give the 72 match lines. A 72-input OR of the match lines, 71 OR gates, gives corrected. Each of the 64 data bits leaves through an XOR gate that flips the received bit when its own match line is 1, 64 XOR gates in all, giving data out. In the no-match form of the flag, an OR of the eight syndrome bits, 7 OR gates, says s is nonzero, and an AND with corrected inverted gives uncorrectable. A dashed panel shows the parity form for Hsiao instead: an XOR of the eight syndrome bits with its output inverted, 7 XOR gates, and the OR of the syndrome bits, 7 OR gates, meet in one AND gate, which agrees with the no-match form on every pattern of weight 2 or less. A note lists the levels on the longest Hsiao paths: 5 for the syndrome, 3 for a comparator and 1 for the correcting XOR make 9 to data out, the OR of 72 lines adds 7 to make 15 to corrected, and the final AND adds 1 to make 16 to uncorrectable. Syndrome 8 XOR trees 208 or 276 XOR received 72 8 72 64 s match the 64 received data bits one comparator per column 72 × 7 = 504 AND 64 XOR 71 OR 7 OR 1 AND data out corrected uncorrectable no-match form Levels on the longest Hsiao paths syndrome 5, comparator 3, correcting XOR 1: data out at 9 OR of 72 lines adds 7: corrected at 15 final AND adds 1: uncorrectable at 16 The parity form of the flag, Hsiao s 8 7 XOR 7 OR 1 AND uncorrectable agrees with the no-match form on every pattern of weight 2 or less, and leaves the 71 corrected ORs free
Figure 3. The decoder in three stages, with the gates of each and the levels on the longest Hsiao paths. The dashed panel is the parity form of the uncorrectable flag.

The decoder works in the three stages of Figure 3. The syndrome stage computes ss with eight XOR trees over all 72 bits, the column-match stage compares ss with each column, and the correction stage flips each data bit whose own column matched.

A single error at position jj has syndrome hjh_j, because Equation 2 is linear and the codeword contributes zero, so exactly the match line mjm_j rises, the columns being distinct. Flipping bit jj back is then one XOR. The stages and flags, from hdl/secded72/secded72_dec.sv, read almost as that sentence does.

SystemVerilog
// ---- column-match stage: match[j] is 1 when the syndrome equals column j
logic [N-1:0] match;
for (genvar j = 0; j < N; j++) begin : g_match
localparam logic [R-1:0] COLUMN = COLUMNS[MAX_R*j +: R];
assign match[j] = (syndrome == COLUMN);
end
// ---- correction stage: flip the data bit whose column matched
for (genvar b = 0; b < K; b++) begin : g_correct
localparam int P = int'(DATA_POS[8*b +: 8]);
assign data[b] = received[P] ^ match[P];
end
// ---- flags
assign corrected = |match;
if (FLAG == 0) begin : g_nomatch
assign uncorrectable = (|syndrome) & ~corrected;
end else if (PARITY_ROW < 0) begin : g_even
assign uncorrectable = (|syndrome) & ~(^syndrome);
end else begin : g_parity_bit
assign uncorrectable = (|syndrome[PARITY_ROW-1:0]) & ~syndrome[PARITY_ROW];
end
endmodule

The output corrected is the OR of all 72 match lines, so it rises for a single error in a check bit too, where no data bit changes. The no-match form of uncorrectable says that the syndrome is nonzero and no column matched. Counting the gates of Figure 3 stage by stage gives the hand count that SECDED and Hsiao Codes began.

Proof. Each term counts one stage. The syndrome costs SS gates. Each of the nn match lines is an AND of rr bits, a tree of r−1r - 1 gates by the lemma on wide gates, with the inversions free. Each of the kk data bits passes one XOR. The OR of the nn match lines takes n−1n - 1 gates. The no-match flag needs the OR of the rr syndrome bits, r−1r - 1 gates, and one AND with corrected inverted. A data bit waits LsL_s levels for the syndrome, ⌈log⁡2r⌉\lceil \log_2 r \rceil for a balanced AND over rr inputs and one for its XOR. The output corrected replaces that XOR with a balanced OR over nn lines, and uncorrectable adds its AND after corrected, which arrives later than the OR of the syndrome bits. ■\blacksquare

For Hsiao, S=208S = 208 and Ls=5L_s = 5, so G=208+504+64+71+7+1=855G = 208 + 504 + 64 + 71 + 7 + 1 = 855 at depths 9, 15 and 16. For extended Hamming, S=276S = 276 and Ls=7L_s = 7, giving 923 gates at depths 11, 17 and 18. The parity forms change only the flag. For Hsiao it is the OR and the XOR of the eight syndrome bits, 7 gates each, joined by one AND, for 862 gates, at depth 5+3+1=95 + 3 + 1 = 9 since it no longer waits for corrected. For extended Hamming it is the OR of the seven low syndrome bits, 6 gates, and an AND with the parity bit inverted, for 922 gates at depth max⁡(6+3, 7)+1=10\max(6 + 3,\ 7) + 1 = 10, the low trees being at most 6 deep and the parity row 7.

07.Two Flags That Agree Inside the Envelope

Proof. Take Hsiao first. Every column has odd weight, 1, 3 or 5. If P(s)=1P(s) = 1, then ss is nonzero and of even weight, so it is no column and N(s)=1N(s) = 1. If N(s)=1N(s) = 1 and P(s)=0P(s) = 0, then ss is nonzero, no column, and of odd weight, which is UU. In the envelope, wt(e)=0\mathrm{wt}(e) = 0 gives s=0s = 0 and both forms 0. A single error gives a column, so N=0N = 0, and its odd weight gives P=0P = 0. A double error at positions ii and jj gives s=hi⊕hjs = h_i \oplus h_j, nonzero because the columns are distinct, and of even weight because wt(a⊕b)=wt(a)+wt(b)−2 wt(a∧b)\mathrm{wt}(a \oplus b) = \mathrm{wt}(a) + \mathrm{wt}(b) - 2\,\mathrm{wt}(a \wedge b), so P=1P = 1 and therefore N=1N = 1.

For extended Hamming every column has s7=1s_7 = 1, and the low bits of the columns are the distinct numbers 0 to 71. If P(s)=1P(s) = 1, then s7=0s_7 = 0, so ss is no column, and s≠0s \ne 0, so N(s)=1N(s) = 1. If N(s)=1N(s) = 1, then slow≠0s_{\mathrm{low}} \ne 0, since a zero low part leaves ss as zero or as the column of position 0, neither of which NN flags. If also P(s)=0P(s) = 0, then s7=1s_7 = 1 and the low bits match no column, so they are 72 or more. In the envelope, a single error gives a column, so N=0N = 0, and s7=1s_7 = 1 gives P=0P = 0. A double error at ii and jj gives s7=1⊕1=0s_7 = 1 \oplus 1 = 0 and low bits i⊕j≠0i \oplus j \ne 0, so P=1P = 1 and therefore N=1N = 1. ■\blacksquare

The companion script checks every case. Of the 256 syndromes, 72 match a column, so NN fires on 256−1−72=183256 - 1 - 72 = 183. PP fires on 127, so for each code UU holds 183−127=56183 - 127 = 56 syndromes, and PP never fires alone. On the 2,629 patterns of the envelope the two forms disagree on none.

The parity form is shallower, since it never reads the match lines, so by the hand count the Hsiao flag is ready at depth 9 rather than 16, and the netlist below gives 10. The no-match form catches more beyond the envelope, where a syndrome in UU raises it and slips past the parity form. For both codes the parity form flags no triple at all, since three odd-weight Hsiao columns XOR to odd weight and three ones in row 7 make s7=1s_7 = 1, as the second worked example shows.

08.The Reference Model

The model in tb/secded72/secded72_model.py is plain Python with nothing beyond the standard library. A word is an integer whose bit jj is position jj, and these functions are the syndrome, the data extraction, the flag and the decoder.

Python
def syndrome(self, word: int) -> int:
s = 0
for i, mask in enumerate(self.row_masks):
s |= ((word & mask).bit_count() & 1) << i
return s
def data_bits(self, word: int) -> int:
d = 0
for b, p in enumerate(self.data_positions):
d |= ((word >> p) & 1) << b
return d
def uncorrectable(self, s: int, matched: bool, flag: str) -> bool:
if flag == "nomatch":
return s != 0 and not matched
if self.parity_row is None:
return s != 0 and s.bit_count() % 2 == 0
hamming_bits = s & ((1 << self.parity_row) - 1)
return hamming_bits != 0 and not (s >> self.parity_row) & 1
def decode(self, received: int, flag: str = "nomatch") -> tuple:
"""Return (data, corrected, uncorrectable) for one received word."""
s = self.syndrome(received)
j = self.position_of.get(s)
matched = j is not None
if matched:
received ^= 1 << j
return (self.data_bits(received), int(matched), int(self.uncorrectable(s, matched, flag)))

The integer row_masks[i] has bit jj set when position jj lies in row ii, so (word & mask).bit_count() & 1 is the XOR of the bits row ii covers. The dictionary position_of maps each column back to its position, so the model decodes by lookup rather than with 72 comparators.

The model and the hardware still share the column list, and the package's masks come from the model's elimination, so a mistake there would sit in both. The bench therefore checks each case against a second oracle too, the guarantee of Equation 1, which the function spec computes from dd, ee and the weight of ee alone. A wrong mask makes some codeword's syndrome nonzero, so a clean word is misread and the guarantee fails even where the model agrees. A shared mistake that still leaves a valid SEC-DED code passes both oracles, and the column check against SECDED and Hsiao Codes exists for that case.

09.The Bench

The simulation bench for the (72,64) encoder and decoder. A stimulus block forms every pair of a data word d and an error pattern e: 1,066 data words, namely all zeros, all ones, the 64 walking ones and 1,000 random words drawn with seed 30, and 2,629 error patterns, one of weight 0, 72 of weight 1 and 2,556 of weight 2. Inside secded72_bench, built by Verilator, the encoder turns d into a 72-bit codeword, an XOR gate adds e, and the decoder returns 66 bits, the 64 data bits and the two flags. The same pair goes to the Python model secded72_model.py, whose expected outputs meet the hardware outputs in a compare block, which checks data out and both flags against the model and against the guarantee. A note gives the totals for each (72,64) code: 2,802,514 cases with no disagreement, 1,066 of weight 0, 76,752 of weight 1 and 2,724,696 of weight 2, swept in 44.1 seconds for Hsiao and 45.2 seconds for extended Hamming. secded72_bench, built by Verilator Every pair (d, e) 1,066 data words d: all zeros, all ones, 64 walking ones, 1,000 random, seed 30 2,629 patterns e: 1 + 72 + 2,556 of weight 0, 1 and 2 Encoder Decoder Python model secded72_model.py Compare data out and both flags with the model and the guarantee d 64 e 72 66 c the same pair expected outputs Per (72,64) code: 1,066 × 2,629 = 2,802,514 cases, 0 disagreements by weight: 1,066 of weight 0, 76,752 of weight 1, 2,724,696 of weight 2 sweep time: Hsiao 44.1 s, extended Hamming 45.2 s
Figure 4. The bench. Each pair of a data word and an error pattern goes to the hardware and to the model, and every output is checked against the model and against the guarantee.

The bench hdl/secded72/secded72_bench.sv wires the encoder to the decoder through the channel assign received = codeword ^ error;, so a test drives a data word and an error pattern and reads back the codeword and the decoder's outputs. The channel lives in the bench, which keeps both blocks synthesizable as they stand. The test in tb/secded72/test_secded72.py runs under cocotb [3] and Verilator [4], and its heart is one loop.

Python
for d in words:
codeword = CODE.encode(d)
dut.data.value = d
for e in patterns:
dut.error.value = e
await Timer(1, unit="ns")
got_codeword = dut.codeword.value.to_unsigned()
got = (dut.data_out.value.to_unsigned(), int(dut.corrected.value), int(dut.uncorrectable.value))
want = CODE.decode(codeword ^ e, FLAG)
cases += 1
by_weight[e.bit_count()] += 1
if got_codeword != codeword or got != want:
model_mismatches += 1
if first is None:
first = f"model: d={d:#x} e={e:#x} hardware {got} codeword {got_codeword:#x}, model {want}"
if got != model.spec(CODE, d, e):
spec_mismatches += 1
if first is None:
first = f"guarantee: d={d:#x} e={e:#x} hardware {got}, guarantee {model.spec(CODE, d, e)}"

For each data word the loop encodes once in the model, then drives each pattern and waits one nanosecond of simulated time for the logic to settle. The codeword is compared with the model's, the outputs with the model's decode and with the guarantee, and each case is counted by its weight. The words are the all-zero word, the all-ones word, the 64 words with a single 1 and 1,000 random words drawn with the fixed seed 30, so the cases number

1,066×2,629=2,802,514,1{,}066 \times 2{,}629 = 2{,}802{,}514,
(6)

of which 1,0661{,}066 have weight 0, 1,066×72=76,7521{,}066 \times 72 = 76{,}752 weight 1 and 1,066×2,556=2,724,6961{,}066 \times 2{,}556 = 2{,}724{,}696 weight 2.

Table 1. The four sweeps of the bench, one for each code and form of the uncorrectable flag, with the time each sweep took inside the simulator on the recorded run

CodeFlagCasesDisagreementsSweep time
Hsiao (72,64)no-match2,802,514044.1 s
extended Hamming (72,64)no-match2,802,514045.2 s
Hsiao (72,64)parity2,802,514045.4 s
extended Hamming (72,64)parity2,802,514046.7 s

Source: measured by tb/secded72/run_secded72.py, with the case counts reproduced by ch30_project_secded_encoder_and_decoder.py.

Table 1 records zero disagreements with either oracle in all four sweeps, and a theorem of Verifying ECC Hardware, in its section When One Codeword Stands for All, makes that stronger than it looks. If the encoder is systematic, the syndrome ss is linear over GF(2)\mathrm{GF}(2) with s(c)=0s(c) = 0 on every codeword, and the match logic and flags see the received word only through ss, then the case of dd and ee is wrong exactly when the case of the zero word and ee is wrong.

Proof. The encoder copies each data bit unchanged to its position, so it is systematic. Each syndrome bit is an XOR of received bits, as in Equation 2, which is linear over GF(2)\mathrm{GF}(2). The masks solve the check equations, as the lemma on the Hsiao check bits shows for Hsiao and the model's elimination does for every code, so s(c)=0s(c) = 0 on every codeword. The match lines compare ss with constants, both flags read only ss and the match lines, and the correction XORs each received data bit with a match line, so the match logic and flags see the received word only through ss. ■\blacksquare

So for the design as written, the 2,629 patterns on the zero word settle all 2642^{64} data words, and the other 1,065 words are there because a bug can break a hypothesis. The zero word encodes to zero under any XOR encoder, so a wrong mask is invisible on it. The 64 words with a single 1 test every mask bit, since an XOR encoder's output is the XOR of the contributions of single data bits, and the all-ones and random words catch a bug that is not linear at all, such as an AND typed where an XOR belongs.

The bench still simulates only the RTL inside the envelope, and its 1,066 words stand for every data word only through a lemma about the design that passed. The formal proof closes that gap.

10.The Formal Proof

The formal wrapper secded72_formal for the (72,64) codes. Five free inputs enter from the left: the data word d of 64 bits, two error positions p1 and p2, and two bits v1 and v2 that say whether each position is used. A block builds the error pattern e, with a 1 at each used position, and its weight wt, which is 0, 1 or 2. The encoder turns d into the codeword c, an XOR gate adds e to give the received word, and the decoder returns 66 bits, the data out and the two flags. An assert block states four guarantees in terms of d, wt, the received data bits r and the outputs, written as (data out, corrected, uncorrectable): (d, 0, 0) at weight 0, (d, 1, 0) at weight 1, (r, 0, 1) at weight 2, and at any weight data out equal to d unless uncorrectable is raised. An assume block keeps both positions below 72, and in the narrow task also forces v2 to 0. A cover block asks for one input of each weight 0, 1 and 2. SymbiYosys runs the proofs on the abc pdr engine and the covers on yosys-smtbmc with z3, and reports PASS or a counterexample. secded72_formal Encoder Build e a 1 at each used position, and wt Decoder assert wt 0: (d, 0, 0) wt 1: (d, 1, 0) wt 2: (r, 0, 1) any: d, or flag (data out, corrected, uncorrectable) assume p1 < 72 and p2 < 72 narrow task adds v2 = 0 cover one input of each weight 0, 1 and 2 SymbiYosys prove: abc pdr cover: smtbmc z3 d 64 p1, p2 v1, v2 c e wt 66 received received data bits r verdict
Figure 5. The formal wrapper. Its inputs are free, so the solver must show the assertions for every data word and every pattern of the envelope, and the covers show that each weight is reachable.

A solver checks a statement for every input at once. The wrapper hdl/secded72/secded72_formal.sv builds the bench's chain of encoder, channel and decoder but leaves its inputs free, so SymbiYosys [5] may pick any of them. The data word d ranges over all 2642^{64} values, and the error pattern is built from two optional positions, p1 and p2, each used when its bit v1 or v2 is set.

SystemVerilog
assign e = (v1 ? (N'(1) << p1) : '0) | (v2 ? (N'(1) << p2) : '0);
assign wt = (v1 && v2 && p1 != p2) ? 2'd2 : (v1 || v2) ? 2'd1 : 2'd0;

The pattern therefore ranges over exactly the patterns of weight 0, 1 and 2. When both positions are used and equal, the OR makes a pattern of weight 1, and wt agrees. The properties follow.

SystemVerilog
always_comb begin
assume (int'(p1) < N);
assume (int'(p2) < N);
if (VACUOUS == 1) assume (!v2);
if (wt == 2'd0) assert (data_out == d && !corrected && !uncorrectable);
if (wt == 2'd1) assert (data_out == d && corrected && !uncorrectable);
if (wt == 2'd2) assert (data_out == received_data && !corrected && uncorrectable);
assert (data_out == d || uncorrectable);
cover (wt == 2'd0);
cover (wt == 2'd1);
cover (wt == 2'd2);
end

The first three assertions are Equation 1 line by line, with received_data standing for the received data bits. The fourth, at any weight, says the data out is right unless uncorrectable is raised, which rules out wrong data handed over in silence. The three covers ask for an input of each weight on the balanced Hsiao and extended Hamming codes, guarding against a vacuous proof, one whose assumptions exclude the cases that matter, and every proof makes the same assumptions. The SymbiYosys file formal/secded72/secded72.sby [6] names nine tasks and their engines.

Code
[tasks]
prove_hsiao prove hsiao nomatch
prove_hsiao_parity prove hsiao parity
prove_hamming prove hamming nomatch
prove_hamming_parity prove hamming parity
cover_hsiao cover hsiao nomatch
cover_hamming cover hamming nomatch
narrow_cover_hsiao cover hsiao nomatch narrow
prove_dictionary prove dictionary nomatch
prove_39_32 prove h39 nomatch
[options]
prove: mode prove
cover: mode cover
depth 1
[engines]
prove: abc pdr
cover: smtbmc z3

The proofs run on the pdr command of ABC [7], which its own help describes as property-directed reachability, the method Bradley introduced as IC3 [8], and the covers on yosys-smtbmc with Z3 [9]. The design has no register, so a single time step holds every behavior and a depth of 1 suffices.

Table 2. The nine formal tasks, with the verdict each must give and the time each took on the recorded run

TaskWhat it checksVerdictTime
prove_hsiaoHsiao, no-match flagPASS18.1 s
prove_hsiao_parityHsiao, parity flagPASS19.7 s
prove_hammingextended Hamming, no-match flagPASS189.4 s
prove_hamming_parityextended Hamming, parity flagPASS237.7 s
cover_hsiaoeach weight reachable, HsiaoPASS0.5 s
cover_hammingeach weight reachable, extended HammingPASS0.4 s
narrow_cover_hsiaoa narrowed assumptionFAIL, as intended0.4 s
prove_dictionaryHsiao in dictionary orderPASS21.3 s
prove_39_32Hsiao (39,32)PASS2.0 s

Source: measured by formal/secded72/run_formal72.py, 489.6 s in all.

Table 2 shows every task giving its expected verdict. The four proofs say that both decoders, with both flags, meet the guarantee for every data word and every pattern of the envelope, about 4.85×10224.85 \times 10^{22} cases each by the count of Verifying ECC Hardware. The engine matters. An earlier run of prove_hsiao on yosys-smtbmc with Z3, the engine Verifying ECC Hardware used, took 723 seconds. Solver times vary between runs too, prove_hamming having taken 290.5 seconds on an earlier run, so they measure the proof and not the hardware.

The task narrow_cover_hsiao plants the classic mistake on purpose. With VACUOUS set to 1 the wrapper assumes !v2, which forbids every pattern of weight 2. A proof under that assumption would pass trivially, and only the cover notices. The solver reports the weight-2 cover at line 90 of the wrapper unreached, and the runner counts that FAIL as the verdict it expects.

A failing proof shows one wrinkle of the installation. SymbiYosys writes a counterexample trace with yosys-witness, which needs the Python module click, and without it the task ends DONE (ERROR, rc=16) with engine_0 (abc pdr) returned FAIL in its log. The runner reads that line and reports FAIL, so a broken decoder never passes for a broken tool. The proof covers the RTL inside the envelope, not the gates, timing or heavier patterns, and it inherits the matrix from the package, which is why the column check runs first.

11.Counting Gates in a Real Netlist

The script synth/synth_secded72.py asks Yosys [10] what it really builds. It flattens each block and hands it to ABC [7] with abc -g AND,OR,XOR and the script strash; balance -x; map. As ABC's own help describes them, strash turns the logic into two-input ANDs and inverters, balance -x rebalances it to minimize levels, wide XORs included, and map performs standard-cell mapping with area recovery, onto a library Yosys writes in which AND, OR, XOR and the inverter all have the same delay. The script then counts as the hand count does, with inverters free.

Each block is synthesized two ways. As separate trees, each syndrome bit and check bit is synthesized alone, so no gate can serve two outputs, which is the hand count's model. As a whole block, ABC may share any gate, as it would in a real design.

Table 3. Two-input gates and levels for each block, predicted by hand and measured in the Yosys netlist, for both (72,64) codes. A decoder's levels are given for its data output, corrected and uncorrectable

BlockHsiao, predictedHsiao, measuredExt. Hamming, predictedExt. Hamming, measured
Syndrome, separate trees208, 5 levels208, 5 levels276, 7 levels276, 7 levels
Encoder, separate trees200200232232
Syndrome, whole block208, 5 levels169, 5 levels276, 7 levels137, 7 levels
Encoder, whole block200, 5 levels159, 5 levels232, 6 levels175, 6 levels
Decoder, no-match flag855, levels 9/15/16550, levels 9/15/16923, levels 11/17/18478, levels 11/17/18
Decoder, parity flag862, levels 9/15/9457, levels 9/15/10922, levels 11/17/10385, levels 11/17/10

Source: measured by synth/synth_secded72.py into data/ch30/secded72_gates.json, with the predictions and the comparison reproduced by ch30_project_secded_encoder_and_decoder.py.

Gates counted by hand and gates in the synthesized netlist, for both (72,64) codes counted by hand, two-input gates Yosys and ABC, whole block Syndrome stage Hsiao 208 169 extended Hamming 276 137 Encoder Hsiao 200 159 extended Hamming 232 175 Decoder, no-match flag Hsiao 855 550 extended Hamming 923 478 Decoder, parity flag Hsiao 862 457 extended Hamming 922 385 0 200 400 600 800 1000 Two-input gates, with inverters not counted
Figure 6. Gates counted by hand against gates in the netlist. Sharing removes a third or more of every decoder, and removes more from extended Hamming than from Hsiao. Data: drawn by ch30_charts.py from the gate counts of data/ch30/secded72_gates.json.

The separate trees match the hand count exactly, gate for gate and level for level, as the lemma on wide gates says they must. Allowed to share, ABC cuts the Hsiao syndrome from 208 gates to 169 and the extended Hamming syndrome from 276 to 137, so the matrix with more ones ends with fewer gates, as Figure 6 shows. The reason is in the columns. Positions 2m2m and 2m+12m + 1 of the extended Hamming code, for any whole number mm, differ only in row 0, because the binary numbers 2m2m and 2m+12m + 1 differ only in their last digit. Every other row that covers one covers both, so one gate computing r2m⊕r2m+1r_{2m} \oplus r_{2m+1} serves all those rows, and the argument repeats for groups of four positions, and on up. The Hsiao matrix avoids such repeats. Two weight-3 columns share at most two rows and a check column lies in one row only, so a gate over a pair of positions serves few rows.

Sharing cost no level in the syndrome or the encoder. The whole-block Hsiao syndrome is 5 levels deep in every bit, and the extended Hamming bits are 6, 6, 6, 5, 5, 5, 3 and 7 deep, exactly ⌈log⁡2w⌉\lceil \log_2 w \rceil for the row weights 36, 36, 36, 32, 32, 32, 8 and 72. The extended Hamming encoder shares far less than its syndrome, from 232 gates to 175, since no encoder mask is a 72-input parity row reusing almost every piece of the others. The Hsiao encoder goes from 200 to 159, so Hsiao keeps a 9.1 percent advantage there.

The decoder shares the most, because its 72 comparators all read the same eight syndrome bits. Each comparator is an AND of eight literals, a literal being a syndrome bit or its inverse. Four bits can be set only 16 ways, so 16 four-input ANDs over rows 0 to 3 and 16 over rows 4 to 7 can serve every comparator, each of which then needs one more AND, the trick a memory's address decoder calls predecoding. The 855 Hsiao gates of the hand count become 550 and the 923 extended Hamming gates become 478, 35.7 and 48.2 percent shared away.

What the Hsiao code saves or costs against extended Hamming, measured Hsiao needs fewer Hsiao needs more Measured as separate trees syndrome XOR gates 24.6% fewer encoder XOR gates 13.8% fewer syndrome levels 28.6% fewer Measured as one whole block syndrome gates 23.4% more encoder gates 9.1% fewer decoder gates, no-match flag 15.1% more decoder gates, parity flag 18.7% more levels to the corrected data 18.2% fewer 30 20 10 0 10 20 30 Hsiao more Hsiao fewer Percent of the extended Hamming figure
Figure 7. What Hsiao saves or costs against extended Hamming. The gate saving of the hand count reverses once gates may be shared, and the saving in levels survives. Data: drawn by ch30_charts.py from the gate counts and depths of data/ch30/secded72_gates.json.

Here the prediction reverses, as Figure 7 shows. By hand the Hsiao decoder is the smaller, 855 gates against 923. In the netlist it is the larger, 550 against 478, which is 15.1 percent more, because the extended Hamming syndrome shares so much more. What Hsiao keeps is depth. Its data output is 9 levels deep against 11, which is 18.2 percent fewer, and its corrected and uncorrectable outputs are 15 and 16 deep against 17 and 18, exactly the hand prediction for both codes. Sharing moves gates and leaves the longest paths where the lemma pins them, and the longest paths are what a read waits for.

One depth does differ. The Hsiao parity flag sits at 10 levels where the hand count says 9, because ABC built some XORs of two syndrome bits aa and bb as (a∧¬b)∨(¬a∧b)(a \wedge \neg b) \vee (\neg a \wedge b), two levels deep, to share those AND terms with the comparators. ABC is a heuristic, not a minimizer, so these counts belong to this recipe on this build, and only the separate trees are figures a proof pins down.

12.What the Numbers Mean for a Designer

Read latency is the number to watch, because every level on the path to the data output is added to every load. Hsiao's 9 levels against 11 are the reason to prefer it, and that reason survived synthesis. Whether 9 levels fit beside the memory access in one cycle depends on the process and the clock, which is why the chapter counts levels rather than picoseconds.

The flags are later than the data, at 15 levels for corrected and 16 for the no-match uncorrectable, because each waits for the OR of all 72 match lines. A design that must act on the flag in the cycle of the read can use the parity form, whose flag arrives at 10 levels, and accept that some words beyond the envelope pass unflagged, or it can register the flags and act a cycle later while the data goes ahead.

Area is paid per port. The Hsiao decoder is 550 two-input gates in this netlist and its encoder 159, and a memory with several read ports pays for a decoder at each. Where area matters more than latency, the netlist favors extended Hamming at 478 gates, which the hand count alone would have hidden. If the read path is too long for one cycle, a register after the syndrome stage splits it, and it holds only the 8 syndrome bits and the 64 received data bits the correction still needs.

13.Looking Ahead

Every check in this chapter stayed inside the envelope, and the code promises nothing outside it. The next chapter, Lab: Measuring Miscorrection, drives the same hardware with patterns of weight 3 and 4 and counts what it does. SECDED and Hsiao Codes predicted the answer for triple errors from the matrices alone. Of the 59,640 ways to choose three of the 72 positions, Hsiao miscorrects 33,568 and flags 26,072, and extended Hamming miscorrects 45,304 and flags 14,336. The lab samples triples on the hardware and checks the measured split against those counts, and the theorem of this chapter already says where the two forms of the flag must part, on the triples whose syndrome lands in UU.

14.Worked Examples

The syndrome of a pattern is the XOR of the columns it flips. Printed with s0s_0 first, position 0 holds 1110000011100000 and position 1 holds 1101000011010000, so the syndrome is 11100000⊕11010000=0011000011100000 \oplus 11010000 = 00110000. It is nonzero with two ones, and every Hsiao column has odd weight, so no match line rises. Nothing is flipped and corrected is 0. The flag uncorrectable is 1 in the no-match form, since the syndrome is nonzero with no match, and 1 in the parity form, since its weight is even. The data output is dd with bits 0 and 1 flipped, which is d⊕eDd \oplus e_{\mathrm{D}} as Equation 1 requires.

Position 70 holds the weight-1 column 0000001000000010, so the syndrome is 11100000⊕00010110⊕00000010=1111010011100000 \oplus 00010110 \oplus 00000010 = 11110100, with five ones. The weight-5 columns are the eight runs of five consecutive rows, counted around the eight rows as a circle, and rows 0, 1, 2, 3 and 5 are no such run, so the syndrome lies in UU and corrected is 0. The no-match form raises uncorrectable, since the syndrome is nonzero with no match. The parity form leaves it at 0, since the weight is odd, and the decoder hands out data with bits 0 and 49 wrong and no flag, which is silent corruption.

A check bit is the XOR of the data bits in its mask, which for the all-ones word is the parity of the mask's size. Every Hsiao mask holds 26 data bits, an even number, so all eight check bits are 0, printed 0000000000000000, and the codeword is 64 ones followed by 8 zeros. The extended Hamming masks hold 35, 35, 35, 35, 31, 31, 31 and 7 data bits, all odd, so all eight check bits are 1, printed 1111111111111111, and the codeword is 72 ones. The last exercise uses both facts.

Eight trees over 216 inputs in all lose one gate each, so S=216−8=208S = 216 - 8 = 208, and Ls=⌈log⁡227⌉=5L_s = \lceil \log_2 27 \rceil = 5. The comparators add 72×7=50472 \times 7 = 504, the correction 64, the OR for corrected 71, the OR of the syndrome bits 7 and the final AND 1, for G=855G = 855. The depths are 5+3+1=95 + 3 + 1 = 9 to the data, 5+3+7=155 + 3 + 7 = 15 to corrected and 16 to uncorrectable. The netlist has 550 gates at exactly those depths, so the hand count overstates the gates by the 35.7 percent that sharing removes and gets every depth right.

15.Exercises

References

  1. [1]Hsiao, M. Y. (1970). “A Class of Optimal Minimum Odd-weight-column SEC-DED Codes.” IBM Journal of Research and Development, 14(4), pp. 395–401. doi:10.1147/rd.144.0395
  2. [2]Hamming, Richard W. (1950). “Error Detecting and Error Correcting Codes.” Bell System Technical Journal, 29(2), pp. 147–160. doi:10.1002/j.1538-7305.1950.tb00463.x
  3. [3]cocotb Project “Installation.” cocotb 2.1 documentation. Read 2026-11-14. https://docs.cocotb.org/en/stable/install.html
  4. [4]Verilator Project “Installation.” Verilator 5.054 documentation. Read 2026-11-14. https://verilator.org/guide/latest/install.html
  5. [5]YosysHQ “Installation guide.” SymbiYosys documentation. Read 2026-11-15. https://symbiyosys.readthedocs.io/en/latest/install.html
  6. [6]YosysHQ “Reference for .sby file format.” SymbiYosys documentation. Read 2026-11-15. https://symbiyosys.readthedocs.io/en/latest/reference.html
  7. [7]Brayton, Robert and Mishchenko, Alan (2010). “ABC: An Academic Industrial-Strength Verification Tool.” In Computer Aided Verification, pp. 24–40. doi:10.1007/978-3-642-14295-6_5
  8. [8]Bradley, Aaron R. (2011). “SAT-Based Model Checking without Unrolling.” In Verification, Model Checking, and Abstract Interpretation, pp. 70–87. doi:10.1007/978-3-642-18275-4_7
  9. [9]de Moura, Leonardo and Bjørner, Nikolaj (2008). “Z3: An Efficient SMT Solver.” In Tools and Algorithms for the Construction and Analysis of Systems, pp. 337–340. doi:10.1007/978-3-540-78800-3_24
  10. [10]YosysHQ “Installation.” Yosys documentation. Read 2026-11-14. https://yosyshq.readthedocs.io/projects/yosys/en/latest/getting_started/installation.html

— Anirban

Hardware–software at the seam where compilers meet microcode.

FeedbackBook modePaper
error-correction-codinglinear-block-codes