Paper
Part IILinear Block Codes

Verifying ECC Hardware

November 16, 202647 min readbeginner

How a hardware team shows that a SEC-DED decoder keeps its code's promise, with exhaustive simulation, random fault injection and a formal proof, each scored on four bugs planted in a small Hsiao decoder.

A SEC-DED decoder sits on the path from a memory to a processor, and every word the processor reads passes through it. A wrong decoder can hand the processor a damaged word with no warning raised, and the code behind it can be flawless all the same, because a code is a set of words and a decoder is a circuit. One missing wire in one XOR tree breaks the circuit without changing the code.

The previous chapter, Bounds on Codes, asked how much protection a code of a given length can offer. This chapter asks how a hardware team shows that a decoder, once built, keeps its code's promise. The running design is the Hsiao (13,8) decoder from SECDED and Hsiao Codes, small enough to check down to the last case. Exhaustive simulation runs every case the promise covers, a random fault-injection campaign draws cases at random, and a formal proof asks a solver whether any input breaks the promise. Four bugs are planted in the decoder, and each check is scored by which of them it catches.

Every number in the chapter is recomputed by ch28_verifying_ecc_hardware.py in the python/ folder of the companion repository ecc-book-lab, and the charts are drawn by ch28_charts.py in the same folder. The GNU Octave twin ch28_verifying_ecc_hardware.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 secded subfolder. The bench and the formal runner have no Octave twin, because cocotb and SymbiYosys are both driven from Python.

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.A Decoder Between Memory and Processor

Picture a small memory that stores bytes. On each write an encoder computes five check bits and the memory stores all thirteen. On each read the thirteen bits come back, perhaps with some flipped by a particle strike [1] or a weak cell, and the decoder turns them into eight data bits and two flags. The flag corrected says a single error was found and put right, and uncorrectable says an error was found that the code cannot repair.

The code is the Hsiao (13,8) code [2]. Its check matrix has eight data columns followed by five check columns.

H=[11110000100001100111001000001111010010010101011000100101011100001]H = \begin{bmatrix} 1&1&1&1&0&0&0&0&1&0&0&0&0 \\ 1&1&0&0&1&1&1&0&0&1&0&0&0 \\ 0&0&1&1&1&1&0&1&0&0&1&0&0 \\ 1&0&1&0&1&0&1&1&0&0&0&1&0 \\ 0&1&0&1&0&1&1&1&0&0&0&0&1 \end{bmatrix}

(1)

Each data column has three ones and each check column one, so all thirteen columns have odd weight, the Hsiao condition, and all differ. Data bit djd_j sits at codeword position jj and check bit cic_i at position 8+i8 + i. Making each row of Equation 1 sum to zero over the codeword gives c0=d0⊕d1⊕d2⊕d3c_0 = d_0 \oplus d_1 \oplus d_2 \oplus d_3, c1=d0⊕d1⊕d4⊕d5⊕d6c_1 = d_0 \oplus d_1 \oplus d_4 \oplus d_5 \oplus d_6, c2=d2⊕d3⊕d4⊕d5⊕d7c_2 = d_2 \oplus d_3 \oplus d_4 \oplus d_5 \oplus d_7, c3=d0⊕d2⊕d4⊕d6⊕d7c_3 = d_0 \oplus d_2 \oplus d_4 \oplus d_6 \oplus d_7 and c4=d1⊕d3⊕d5⊕d6⊕d7c_4 = d_1 \oplus d_3 \oplus d_5 \oplus d_6 \oplus d_7, where ⊕\oplus is the exclusive OR, addition in GF(2)\mathrm{GF}(2).

Three conventions hold throughout. A data word is written with d7d_7 on the left, as a byte is usually printed, the reverse of the d0d_0-first order SECDED and Hsiao Codes used. A check word, a column and a syndrome are written row 0 first, as SECDED and Hsiao Codes prints them. An error pattern is a 13-bit string with position 12 on the left, so its last eight characters land on the data. The byte 0x69 is 0110100101101001, its check bits c0c_0 to c4c_4 are 0100101001, and the pattern 00000000001000000000000100 flips d2d_2 alone.

The decoder recomputes each row's sum from the received word rr, which gives the five syndrome bits s0s_0 to s4s_4 from XOR trees of 5, 6, 6, 6 and 6 inputs. Thirteen comparators then match the syndrome against each column [3]. A match with data column jj flips data bit jj back, a match with a check column leaves the data alone, and either way corrected rises. A nonzero syndrome that matches no column raises uncorrectable, and the data passes exactly as it was received.

The bench that checks the Hsiao (13,8) decoder. A cocotb test draws a data word d and an error pattern e. Inside secded_bench, the encoder secded_enc turns d into the 13-bit codeword c, a row of XOR gates, drawn as one XOR gate symbol, flips each bit of c where e holds a 1, and the decoder under test, secded_dec, turns the received word r into data_out and the corrected and uncorrectable flags. A reference model, secded_model.py, computes from d and e alone the outputs the guarantees require, and the test compares the two sets of outputs, counting every wrong case and every silent one. cocotb secded_enc secded_dec compare test reference model draws d and e encoder channel decoder under test count the wrong and silent cases d e c r data_out corrected uncorrectable d, e secded_model.py secded_bench expected
Figure 1. The path from a stored byte to the processor, wrapped in the bench that checks it. The error pattern stands in for whatever flipped bits in the memory, and the reference model sees only and , never the circuit, so it cannot share the circuit's bugs.

Figure 1 serves every check in the chapter, and the decoder's interface, from hdl/secded/secded_dec.sv, is what all of them test.

SystemVerilog
module secded_dec #(
parameter int MUTANT = 0 // 0 is the correct decoder; 1 to 4 plant a bug
) (
input logic [12:0] received, // {c4 .. c0, d7 .. d0} as it arrived
output logic [7:0] data, // the data bits, corrected when possible
output logic corrected, // a single error was found and handled
output logic uncorrectable // an error was found that cannot be corrected
);

The parameter MUTANT builds the correct decoder at 0, the only value a real design would use, and plants one bug at each value from 1 to 4. The encoder in hdl/secded/secded_enc.sv is the five check-bit equations, with no such parameter, since every planted bug is in the decoder.

02.What the Decoder Must Guarantee

A test needs a statement of what correct means, and for a decoder that statement depends on how many bits flipped. Write dd for the data word, cc for its codeword, ee for the 13-bit error pattern, with a 1 wherever a bit flipped, and r=c⊕er = c \oplus e for the received word. Write wt(e)\mathrm{wt}(e) for the number of ones in ee, and eDe_{\mathrm{D}} for its low eight bits, the part that lands on the data.

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

(2)

The check-bit clause is easily forgotten. A flipped check bit leaves the data untouched, so a data-only test would pass a decoder that never raised corrected, though a memory controller may count corrected errors to spot a failing part. The third line fixes a choice too, since with two errors the decoder could flip some bit or none, and the guarantee says none.

Silent cases are the dangerous ones, because wrong data with the flag down goes straight into a register. Whether the guarantees can be met at all rests on one property of the syndrome.

Proof. Multiplying a matrix by a vector over GF(2)\mathrm{GF}(2) distributes over ⊕\oplus, so H(c⊕e)T=HcT⊕HeTH(c \oplus e)^{\mathsf T} = H c^{\mathsf T} \oplus H e^{\mathsf T}. Every codeword satisfies HcT=0H c^{\mathsf T} = 0, because the encoder chose each check bit to make its row sum to zero, and so the first term vanishes. ■\blacksquare

Proof. By the lemma the syndrome of rr is HeTH e^{\mathsf T}, the XOR of the columns at the positions ee flips. With wt(e)=0\mathrm{wt}(e) = 0 the syndrome is zero, so nothing is flipped and no flag rises. With wt(e)=1\mathrm{wt}(e) = 1 the syndrome is the column hih_i of the flipped position ii. The thirteen columns are distinct, so the decoder identifies ii, flips it back when it is a data position, leaves the data alone when it is a check position, and raises corrected in both cases. With wt(e)=2\mathrm{wt}(e) = 2 the syndrome is hi⊕hjh_i \oplus h_j for i≠ji \ne j. It is nonzero because the two columns differ, and it has even weight because two words of odd weight XOR to a word of even weight, so it equals no column. The decoder flips nothing and raises uncorrectable. ■\blacksquare

The proof repeats two theorems of SECDED and Hsiao Codes on one small matrix. Of the 78 double errors, 52 give a syndrome of weight 2 and 26 one of weight 4, a split one of the exercises counts by hand.

Outside the envelope the guarantees say nothing, and Figure 2 shows how lopsided the split is, 92 of the 8,192 patterns inside and 8,100 outside. Of the 286 triples this decoder miscorrects 220, 76.9 percent, and flags 66, as SECDED and Hsiao Codes counted. That is the code's behavior, not a bug, and Lab: Measuring Miscorrection measures it.

The 8,192 error patterns of the Hsiao (13,8) code, by weight 1 0 13 1 78 2 286 3 715 4 1,287 5 1,716 6 1,716 7 1,287 8 715 9 286 10 78 11 13 12 1 13 inside the envelope, 92 patterns outside the envelope, 8,100 patterns triples 0 500 1,000 1,500 Weight of the error pattern, the number of bits flipped Patterns of that weight
Figure 2. The 8,192 error patterns of the Hsiao (13,8) code, by weight. The design envelope is the 92 patterns of weight at most 2, about 1 percent of the total, and the 286 triples in orange are where the code itself miscorrects 220 times. Data: drawn by ch28_charts.py from the pattern counts of ch28_verifying_ecc_hardware.py.

03.Counting the Cases

The guarantees cover a finite list of cases, so the most direct check is to try them all. For a code of length nn with kk data bits, the envelope size and the number of cases are given by Equation 3.

∣En∣=1+n+(n2),Cn,k=2k ∣En∣|E_n| = 1 + n + \binom{n}{2}, \qquad C_{n,k} = 2^{k} \, |E_n|

(3)

For the (13,8) code that is 256×92=23,552256 \times 92 = 23{,}552 cases, and every pattern of every weight on every byte is 256×8,192=2,097,152256 \times 8{,}192 = 2{,}097{,}152 cases. At an assumed, not measured, rate of 10910^9 cases a second, a simulator would sweep the envelope in 23.6 microseconds and the whole space in 2.1 milliseconds. Table 1 gives the counts for four Hsiao codes, up to the (72,64) code of SECDED and Hsiao Codes, and Figure 3 plots them on a logarithmic axis.

Table 1. Cases a complete check needs for four Hsiao SEC-DED codes, counting the envelope on one codeword, the envelope on every data word, and every error pattern on every data word

CodeEnvelope patternsEnvelope casesAll cases
(13,8)9223,5522,097,152
(22,16)25416,646,144274,877,906,944
(39,32)7813,354,369,458,1762,361,183,241,434,822,606,848
(72,64)2,629about 4.85×10224.85 \times 10^{22}21362^{136}, about 8.71×10408.71 \times 10^{40}

Source: reproduced by ch28_verifying_ecc_hardware.py.

At the same rate, one (72,64) codeword's envelope of 1+72+2,556=2,6291 + 72 + 2{,}556 = 2{,}629 patterns takes 2.6 microseconds. Every pattern on that one codeword, 2722^{72} of them, would take 149,642 years, every envelope pattern on every data word 1.54 million years, and all 21362^{136} cases about 2.76×10242.76 \times 10^{24} years.

How many cases a complete check of a SEC-DED decoder needs one second one day one year a million years time taken at an assumed 109 a second (13,8) (22,16) (39,32) (72,64) 100 106 1012 1018 1024 1030 1036 1042 envelope on one codeword envelope, every data word every pattern, every data word Hsiao SEC-DED code (n,k) Cases to check
Figure 3. How many cases a complete check of a SEC-DED decoder needs, for four Hsiao codes. The envelope on one codeword stays small, and the factor from the data words is what puts the wide codes out of reach. Data: drawn by ch28_charts.py from the envelope sizes of ch28_verifying_ecc_hardware.py.

The growth comes almost entirely from the data words, since the envelope grows only with the square of nn. If one codeword could stand for all of them, even the (72,64) envelope would be a quick check, and When One Codeword Stands for All shows when that is true.

04.Four Planted Bugs

A check that has never failed has not shown that it can. Mutation testing measures a check's strength by planting bugs on purpose and counting how many it catches [4].

The decoder carries four mutants behind its MUTANT parameter, and Figure 4 marks where each one lives. Mutant 1, written M1, leaves r6r_6 out of the XOR tree for s1s_1, a term missed while copying row 1 of the matrix. M2 raises uncorrectable only when the syndrome holds exactly two ones, as if every double error gave a weight-2 syndrome. M3 sends the hit for d5d_5 to the flip of d4d_4 and never flips d5d_5, a crossed wire between neighboring comparators. M4 lets the flip of d0d_0 happen only while r7r_7 is 0, a stray term of the kind a hand-edited equation picks up.

The Hsiao (13,8) decoder in blocks, with the place each planted bug lives. Five XOR trees, of 5, 6, 6, 6 and 6 inputs, form the syndrome bits s0 to s4 from the received word r, and mutant M1 leaves r6 out of the tree for s1. Thirteen column comparators match the syndrome s against each column of the check matrix. The eight data-column hits form the flip mask, where M3 steers the hit for d5 to the flip of d4 and M4 lets the flip of d0 happen only while r7 is 0, and eight XOR gates flip the data bits r0 to r7 to give data_out. An OR of all thirteen hits gives corrected. An OR of the five syndrome bits gives nonzero, and an AND of nonzero with not corrected gives uncorrectable, to which M2 adds a third input that is 1 only when s holds exactly two 1s. received word r column comparators flip mask 13, one per column of H 8 XOR gates OR of 13 hits OR of 5, nonzero exactly two 1s M3 d5 hit flips d4 M4 d0 flips only if r7 = 0 M1 r6 left out M2 only data bits r0 to r7 13 bits 5 6 6 6 6 s0 s1 s2 s3 s4 5 s 8 13 5 8 8 r7 data_out corrected uncorrectable
Figure 4. Where the four planted bugs live in the decoder. M1 sits in a syndrome tree, M3 and M4 in the flip mask, and M2 in the logic of the uncorrectable flag.

The excerpt below, from hdl/secded/secded_dec.sv, shows M2, M3 and M4 beside the correct logic. M1 lives in the tree for s1s_1.

SystemVerilog
// The correction mask: which data bits to flip back.
logic [7:0] flip;
always_comb begin
flip = data_hit;
if (MUTANT == 3) begin
flip[4] = data_hit[4] | data_hit[5];
flip[5] = 1'b0;
end
if (MUTANT == 4) begin
flip[0] = data_hit[0] & ~received[7];
end
end
assign data = received[7:0] ^ flip;
assign corrected = |{data_hit, check_hit};
assign uncorrectable = (MUTANT == 2) ? (nonzero & ~corrected & two_ones)
: (nonzero & ~corrected);

In the correct decoder each data bit is XORed with its own hit, corrected is the OR of all thirteen hits, and uncorrectable is a nonzero syndrome that matched nothing. Table 2 gives what each mutant does to the 23,552 cases.

Table 2. The correct decoder M0 and the four mutants over the 23,552 envelope cases, with the wrong cases, the silent ones, the patterns wrong on the zero codeword, and whether the identity of the reduction theorem holds

DecoderThe slipWrong cases mmSilentWrong patterns on the zero codewordReduction identity
M0none000holds
M1r6r_6 left out of s1s_19,8566,52812fails in 9,856 cases
M2flag needs a weight-2 syndrome6,6566,65626holds
M3the hit for d5d_5 flips d4d_42562561holds
M4d0d_0 flips only while r7=0r_7 = 01281280fails in 128 cases

Source: reproduced by ch28_verifying_ecc_hardware.py.

M1 is wrong on 9,856 cases, 6,528 of them silent, and its damage depends on the byte. On a codeword with d6=0d_6 = 0 the syndrome is still zero, and 12 of the 92 patterns go wrong. Each flips d6d_6, since only then is r6r_6 a 1, and the thirteenth that flips d6d_6, paired with c0c_0, decodes correctly, because its mutant syndrome 1001110011 matches no column and raises the flag. A codeword with d6=1d_6 = 1 arrives with s1s_1 already flipped, so even the error-free word looks damaged, and 65 of the 92 patterns go wrong. Half the bytes have each value of d6d_6, so m=128×12+128×65=9,856m = 128 \times 12 + 128 \times 65 = 9{,}856.

M2 is wrong on 6,656 cases, all silent, namely the 26 double errors whose syndrome has weight 4, on every byte. Each flips at least one data bit, and the flag stays down. A test that tries only single errors passes it.

M3 is wrong on 256 cases, the single error in d5d_5 on every byte. The decoder sees the right syndrome, flips d4d_4 instead, raises corrected, and hands over a byte with two wrong bits. All 256 are silent, on the most ordinary event a memory has.

M4 is wrong on 128 cases, the single error in d0d_0 on each byte with d7=1d_7 = 1. There the stray term blocks the correction, corrected rises all the same, and the byte leaves with d0d_0 still flipped. M4 is right on every byte with d7=0d_7 = 0, the zero byte included, and that property is what the next section turns on.

05.When One Codeword Stands for All

By the lemma a correct decoder's syndrome ignores the codeword. If the rest of the decoder ignores it too, all 256 bytes behave alike, and the envelope on the zero codeword alone settles every case. Below, rDr_{\mathrm{D}} is the low eight bits of a received word rr and D(r)D(r) the decoder's three outputs on rr.

D(c⊕e)=(d⊕data(e), F(e))D(c \oplus e) = \bigl(d \oplus \mathrm{data}(e),\ F(e)\bigr)

(4)

Proof. Let r=c⊕er = c \oplus e. By the first two hypotheses, s(r)=s(c)⊕s(e)=s(e)s(r) = s(c) \oplus s(e) = s(e). The encoder is systematic, so the low eight bits of cc are dd and rD=d⊕eDr_{\mathrm{D}} = d \oplus e_{\mathrm{D}}. Since rr and ee have the same syndrome, the third hypothesis gives M(r)=M(e)M(r) = M(e) and F(r)=F(e)F(r) = F(e). The data output is therefore d⊕eD⊕M(e)d \oplus e_{\mathrm{D}} \oplus M(e), and eD⊕M(e)e_{\mathrm{D}} \oplus M(e) is data(e)\mathrm{data}(e), the data output when the zero codeword suffers the error ee, while the flags are F(e)F(e). That is Equation 4. The guarantees have the same shape, since in each line of Equation 2 the data is dd XORed with something fixed by ee and the flags depend on wt(e)\mathrm{wt}(e) alone, so spec(d,e)\mathrm{spec}(d, e) is spec(0,e)\mathrm{spec}(0, e) with dd XORed into its data. XORing the same dd into two words leaves them equal or unequal as they were, so the outputs of (d,e)(d, e) match the guarantee exactly when the outputs of (0,e)(0, e) do. ■\blacksquare

Counting over the 256 bytes gives m=256 ∣W∣m = 256 \, |W|, where WW is the set of envelope patterns wrong on the zero codeword, and silence carries over the same way. The chapter's script checks the identity on all 23,552 cases of each decoder. It holds for M0, M2 and M3, whose bugs touch only the mask or the flags, and the count is exact, 26×256=6,65626 \times 256 = 6{,}656 for M2 and 1×256=2561 \times 256 = 256 for M3.

The identity fails for M1 in 9,856 cases and for M4 in 128. M1 breaks the second hypothesis, since a codeword with d6=1d_6 = 1 has a nonzero syndrome under it, and M4 breaks the third, since its flip of d0d_0 reads r7r_7 directly. On both the zero codeword misleads. It shows M1 wrong on 12 patterns where a byte with d6=1d_6 = 1 shows 65, and M4 right on all 92, so a zero-codeword test would pass a decoder that silently corrupts 128 cases.

The hypotheses are claims about the circuit. Checking the third means showing that no received bit reaches an output except through the syndrome, a claim about all 2n2^n received words, 8,192 for the (13,8) decoder and 2722^{72} for the (72,64) decoder, the 149,642 years of Counting the Cases. A formal tool can settle such a claim without trying the words one at a time.

06.Exhaustive Simulation

For the (13,8) decoder every case fits in a simulation. The bench of Figure 1 is the module secded_bench in hdl/secded/secded_bench.sv, which wires the encoder, a row of XOR gates that applies the error pattern, and the decoder under test. A cocotb test in tb/secded/test_secded.py drives the bench through the Verilator simulator [5] [6], setting its inputs from Python and reading the outputs back [7]. A reference model in tb/secded/secded_model.py computes from dd and ee alone both the output the guarantees require and the output each mutant should produce. The heart of the test is a double loop over every byte and every envelope pattern.

Python
for d in range(2**K):
codeword = encode(d)
for e in envelope_patterns():
got = await apply(dut, d, e)
assert dut.codeword.value.to_unsigned() == codeword, f"codeword for data {d:#04x}"
assert got == decode(codeword ^ e, MUTANT), (
f"hardware {got} differs from the mutant-{MUTANT} model for d={d:#04x} e={e:#06x}")
is_wrong = got != spec(d, e)
wrong += is_wrong
silent += is_wrong and got[0] != d and not got[2]
if is_wrong and first_wrong is None:
first_wrong = (d, e)
cases += 1

Each case is checked three ways. The first assertion checks the codeword, so an encoder fault cannot pass as a decoder bug. The second checks the outputs against the model of the mutant being built, so the circuit is the design it claims to be. The comparison with the guarantees then marks the case wrong, and silent when the data is wrong with the flag down. After the loop the test demands that its counts match the model's, with no wrong case from the correct decoder and at least one from each mutant.

The runner tb/secded/run_secded.py builds the decoder once for each value of MUTANT and runs the loop on each build, 23,552 cases apiece. The hardware, the model and the chapter's script agree on every count, m=0m = 0 for the correct decoder and 9,856, 6,656, 256 and 128 for the mutants. A second test widens the loop for the correct decoder to all 2,097,152 cases, checking the hardware against the model everywhere and against the guarantees inside the envelope, and it passes. Exhaustive simulation kills all four mutants, as a check that tries every case must, until the cases outgrow the time available.

07.Random Fault-Injection Campaigns

For a wide decoder the envelope on every data word is out of reach, and teams fall back on random fault injection, comparing each randomly drawn case with a reference model. The (13,8) decoder, unlike a real design, lets a campaign's odds be checked against the truth.

Two questions measure a campaign, how long it takes to try every pattern at least once and how likely it is to miss a bug of a given size. The first has a classical answer.

E[Tall]=NHN,HN=∑j=1N1j\mathbb{E}[T_{\mathrm{all}}] = N H_N, \qquad H_N = \sum_{j=1}^{N} \frac{1}{j}

(5)

Proof. Split the campaign into stages. Stage ii starts once i−1i - 1 distinct items have been seen and ends at the draw that brings the ii-th new one. During stage ii each draw is new with probability pi=(N−i+1)/Np_i = (N - i + 1)/N, independently of the others. A trial that succeeds with probability pp takes 1/p1/p tries on average, so stage ii lasts N/(N−i+1)N/(N - i + 1) draws on average. The average of a sum is the sum of the averages, so the expected total is ∑i=1NN/(N−i+1)=N∑j=1N1/j=NHN\sum_{i=1}^{N} N/(N - i + 1) = N \sum_{j=1}^{N} 1/j = N H_N [8]. ■\blacksquare

For the 92 envelope patterns H92=5.1044H_{92} = 5.1044, so a campaign needs 469.6 draws on average to see every pattern once, about five times an ordered sweep. Figure 5 follows one seeded campaign, seed 28, which had seen all 92 by draw 454. The last patterns take longest, because once 91 have been seen each draw finds the last with probability 1/921/92. For the 2,629 patterns of the (72,64) envelope the average is 2,629 H2629=22,219.72{,}629 \, H_{2629} = 22{,}219.7 draws, so the factor HNH_N over an ordered sweep grows like ln⁡N\ln N.

How many of the 92 envelope patterns a random campaign has drawn all 92 patterns 469.6 draws expected for all 92 seed 28: all 92 by draw 454 0 100 200 300 400 500 600 700 0 20 40 60 80 100 seeded campaign, seed 28 expected, 92 (1 - (1 - 1/92)T) Draws T, each a uniform case from the 23,552 Distinct patterns drawn
Figure 5. How many of the 92 envelope patterns a random campaign has drawn, against the number of draws. The first patterns come quickly and the last few take the longest, so seeing all 92 takes 469.6 draws on average. Data: drawn by ch28_charts.py from the seeded draws of ch28_verifying_ecc_hardware.py.

Seeing every pattern is not catching every bug, since a bug may be wrong on only some bytes.

Pmiss(T)=(1−mN)TP_{\mathrm{miss}}(T) = \left(1 - \frac{m}{N}\right)^{T}

(6)

Proof. One draw lands on a wrong case with probability m/Nm/N, so it misses with probability 1−m/N1 - m/N. The draws are independent, so the probability that all TT of them miss is the product of their separate probabilities, (1−m/N)T(1 - m/N)^T. ■\blacksquare

Setting the miss probability to at most a small target δ\delta and solving for TT gives the length a campaign needs.

The approximation uses −ln⁡(1−x)≈x-\ln(1 - x) \approx x for small xx, and since −ln⁡(1−x)-\ln(1 - x) is slightly larger than xx, the exact length is slightly shorter. With δ=10−6\delta = 10^{-6}, a bug on one of the 92 patterns of one codeword needs 1,265 draws, against the approximation's 1,271, and one on one of the 2,629 patterns of a (72,64) codeword needs 36,315, against 36,321.

For the four mutants the chance that one draw hits is m/Nm/N, which is 0.4185, 0.2826, 0.0109 and 0.0054. A campaign of 100 draws misses M1 and M2 with a probability that rounds to 0.000, M3 with probability 0.335 and M4 with probability 0.580. A miss below 10−610^{-6} takes 26 draws for M1, 42 for M2, 1,265 for M3 and 2,536 for M4. M3 is wrong on exactly one case in 92, the rate of one bad pattern on one codeword, so it needs the same 1,265.

Seeded runs agree. One campaign of 100 with seed 28 drew 59 distinct patterns on 77 distinct bytes and hit M1 33 times, M2 29 times, M3 once and M4 never. Of 10,000 seeded campaigns of 100, none missed M1 or M2, while 3,401 missed M3 and 5,883 missed M4, shares of 0.3401 and 0.5883 against the predicted 0.335 and 0.580. Figure 6 plots the closed form beside 10,000 seeded campaigns at each length, and its points at 100 draws are this run.

The chance a random campaign misses a planted bug mutant 1, m = 9,856 mutant 2, m = 6,656 mutant 3, m = 256 mutant 4, m = 128 one wrong case, m = 1 1 10 100 1,000 10,000 0.00 0.25 0.50 0.75 1.00 (1 - m/23,552)T share of 10,000 seeded campaigns that missed Campaign size T, draws, on a logarithmic axis Chance the campaign misses the bug
Figure 6. The chance that a campaign of uniform draws over the 23,552 envelope cases misses each planted bug, from , with the share of 10,000 seeded campaigns at each length that missed it as markers. A bug as small as one case is missed more often than not by every campaign up to the 10,000 draws shown. Data: drawn by ch28_charts.py from the wrong-case sets of ch28_verifying_ecc_hardware.py.

A uniform campaign spends 78 of every 92 draws on double errors, yet the two bugs it misses most often are in single-error handling, the case the code exists to correct.

08.Formal Proof

A formal tool does not run cases. It turns the circuit and a set of properties into logical equations and asks a solver whether any input satisfies the circuit's equations while breaking a property. If none does, the property holds for every input, and if one does, the solver returns it as a counterexample.

The properties live in a wrapper, hdl/secded/secded_formal.sv, drawn in Figure 7. Its only inputs are a free data word d and a free error pattern e, which the solver may set freely. The wrapper encodes d, XORs in e, decodes the result and states the guarantees about the outputs.

The formal wrapper secded_formal. Two free inputs, the data word d and the error pattern e, enter from the left. The encoder secded_enc turns d into the codeword c, an XOR gate adds e to give the received word r, and the decoder secded_dec, built with any MUTANT value from 0 to 4, gives its three outputs. A block computes wt, the weight of e. The assume block restricts the solver to wt at most 2, the cover block asks for one input of each weight 0, 1 and 2, and the assert block states the guarantees in terms of d, e, wt and the outputs, namely (d, 0, 0) at weight 0, (d, 1, 0) at weight 1, (d XOR e[7:0], 0, 1) at weight 2, and data_out equal to d whenever uncorrectable is 0. SymbiYosys hands the wrapper to yosys-smtbmc with the z3 solver, which looks for a pair (d, e) inside the assumption that breaks an assertion, and reports PASS or a counterexample. secded_enc secded_dec wt assert assume cover MUTANT 0 to 4 weight of e wt at most 2 wt = 0, 1 and 2 wt = 0 gives (d, 0, 0) wt = 1 gives (d, 1, 0) wt = 2 gives (d XOR e[7:0], 0, 1) every case gives data_out = d unless uncorrectable is 1 PASS, or a counterexample (d, e) outputs SymbiYosys runs yosys-smtbmc with the z3 solver and looks for a pair (d, e) inside the assumption that breaks an assertion free inputs d e c r d e wt secded_formal
Figure 7. The formal wrapper. The solver controls only and , the assumption keeps it inside the envelope, the assertions state the guarantees, and the covers show that each weight was reachable.
SystemVerilog
logic [3:0] wt; // the weight of e, 0 to 13
always_comb begin
wt = 4'd0;
for (int i = 0; i < 13; i++) wt = wt + {3'd0, e[i]};
end
always_comb begin
if (VACUOUS == 0) begin
assume (wt <= 4'd2);
end else if (VACUOUS == 1) begin
assume (wt < 4'd2);
end else begin
assume (wt == 4'd0);
assume (wt == 4'd1);
assume (wt == 4'd2);
end
if (wt == 4'd0) assert (data_out == d && !corrected && !uncorrectable);
if (wt == 4'd1) assert (data_out == d && corrected && !uncorrectable);
if (wt == 4'd2) assert (data_out == (d ^ e[7:0]) && !corrected && uncorrectable);
assert (data_out == d || uncorrectable);
cover (wt == 4'd0);
cover (wt == 4'd1);
cover (wt == 4'd2);
end

The first block counts the ones in e. With VACUOUS at 0, a single assumption keeps the solver inside the envelope. The first three assertions are the three lines of Equation 2, and the fourth, that the data is right or the flag is up, states the rule against silent miscorrection directly. The covers ask for an input of each weight, so a passing proof is known to have considered all three. The other values of VACUOUS plant mistakes, read in the warning below.

The wrapper has 8+13=218 + 13 = 21 free input bits, the same 221=2,097,1522^{21} = 2{,}097{,}152 combinations as the full simulation sweep. The solver, z3 [9] [10], is an SMT solver, a program that decides whether a set of logical equations has a solution. It assigns a few bits, deduces what they force, and at each contradiction learns a rule that excludes a whole region of inputs. Its cost depends more on the structure of the equations than on the count of inputs, though nothing guarantees this, since satisfiability is hard in the worst case.

The proofs are run by SymbiYosys, a front end that reads a .sby file naming the design files, the mode and the solver, and drives Yosys [11] and the solver for each task [12]. Its installation guide lists Yosys and SymbiYosys as required, Boolector as the recommended solver and Z3 as an optional one [13], and these runs used z3. The heart of formal/secded/secded.sby is three short sections.

Code
[options]
prove: mode prove
cover: mode cover
depth 1
[engines]
smtbmc z3
[script]
read -formal secded_enc.sv secded_dec.sv secded_formal.sv
m0: chparam -set MUTANT 0 secded_formal
m1: chparam -set MUTANT 1 secded_formal
m2: chparam -set MUTANT 2 secded_formal
m3: chparam -set MUTANT 3 secded_formal
m4: chparam -set MUTANT 4 secded_formal
narrow: chparam -set VACUOUS 1 secded_formal
empty: chparam -set VACUOUS 2 secded_formal
prep -top secded_formal

These sections ask for a proof of every assertion or a witness to every cover, run yosys-smtbmc with z3, and unroll one step, enough for a decoder with no clock and no stored state. The file's ten tasks each build one mutant under one assumption. The runner formal/secded/run_formal.py runs all ten, and Table 3 lists what each returned.

Table 3. The ten SymbiYosys tasks on the Hsiao (13,8) decoder, with the decoder each one builds, its assumption on the weight of e, its mode and the result the run returned

TaskDecoderAssumptionModeResult
prove_m0M0wt(e)≤2\mathrm{wt}(e) \le 2provePASS
prove_m1M1wt(e)≤2\mathrm{wt}(e) \le 2proveFAIL, with a counterexample
prove_m2M2wt(e)≤2\mathrm{wt}(e) \le 2proveFAIL, with a counterexample
prove_m3M3wt(e)≤2\mathrm{wt}(e) \le 2proveFAIL, with a counterexample
prove_m4M4wt(e)≤2\mathrm{wt}(e) \le 2proveFAIL, with a counterexample
cover_m0M0wt(e)≤2\mathrm{wt}(e) \le 2coverPASS, every cover reached
narrow_prove_m2M2wt(e)≤1\mathrm{wt}(e) \le 1provePASS
narrow_cover_m2M2wt(e)≤1\mathrm{wt}(e) \le 1coverFAIL, the weight-2 cover unreached
empty_prove_m3M3weight 0, 1 and 2 at onceproveERROR, assumptions unsatisfiable
empty_cover_m3M3weight 0, 1 and 2 at oncecoverFAIL, no cover reached

Source: reproduced by run_formal.py in formal/secded/.

The correct decoder passes, and each mutant fails with a counterexample. The runner replays each counterexample's pair (d,e)(d, e) through the reference model, so it counts only once the model agrees the case is wrong. For M3 the solver chose d=10111100d = 10111100 with the single error in d5d_5. The syndrome is 0110101101, the column of d5d_5, and M3 flips d4d_4 instead, giving (10001100,1,0)(10001100, 1, 0) where the guarantee asks for (10111100,1,0)(10111100, 1, 0), wrong and silent. For M4 it chose d=10011001d = 10011001 with the single error in d0d_0, and since d7=1d_7 = 1 the flip is blocked and the output is (10011000,1,0)(10011000, 1, 0). For M2 it chose d=01000000d = 01000000 with errors in d2d_2 and c1c_1, whose syndrome 1111011110 has four ones, so the output is (01000100,0,0)(01000100, 0, 0) with the flag down. The counterexample for M1 is read in Worked Examples. These are the pairs one z3 build returned, and another may choose others, which the runner reports.

09.What a Proof Does Not Cover

A passing proof says that the assertions hold on every input the assumptions allow, in the design as the tool read it. Each part of that sentence is a limit.

The assertions can be incomplete. A wrapper that checked only data_out would miss a bug that touches only a flag, and one of the exercises asks which mutant that is. Writing properties is design work that needs review as much as the circuit, running them against mutants is one cheap test of them, and covers check that the assumptions are not too strong.

The proof is about the model, not the silicon. It covers the SystemVerilog as Yosys read it, not the synthesized netlist, the gate timing, the wiring to the memory or the cells themselves, and a bug in the tool's reading of the source would make it wrong with no visible sign. Each lower level needs its own check, such as an equivalence check between source and netlist and a timing analysis. Nor does it say anything outside the envelope.

The chapter's claims about the tools are limited the same way. Beyond the SymbiYosys documentation, they rest on the ten tasks above, run with z3 on this one design, and say nothing about proof time, other solvers or wider decoders.

10.Which Check, When

The three checks answer different questions, and Table 4 puts the four mutants against all of them.

Table 4. Each planted bug against the three checks, with its wrong cases, the hits of one seeded campaign of 100 draws, the share of 10,000 seeded campaigns of 100 that missed it, the closed-form miss probability at 100 draws, and the verdicts of exhaustive simulation and formal proof

MutantmmHits, seed 28, 100 drawsSeeded miss shareClosed-form miss at 100 drawsExhaustive simulationFormal proof
M19,8563300.000killedkilled
M26,6562900.000killedkilled
M325610.34010.335killedkilled
M412800.58830.580killedkilled

Source: reproduced by ch28_verifying_ecc_hardware.py, with the last two columns from run_secded.py and run_formal.py.

For a decoder as small as this one, exhaustive simulation of the envelope is the first gate. Its verdict on the guarantees is final rather than probable, it needs no property language, and a failure arrives as the exact case that broke. Its limit is scale.

Random fault injection earns its place where exhaustion is impossible, but its result is a probability, and a count of draws means nothing without the size of the bug it is meant to catch, which is the one thing the team does not know.

Planting bugs measures the checks themselves. A suite that kills every planted bug is not thereby complete, but one that lets a bug through has a hole, and the survivor says where. Bugs that break the reduction theorem's hypotheses, like M1 and M4, are the most useful to plant, because a shortcut misses them.

Formal proof is the only check whose cost is not tied to the number of cases, so it alone can hope to cover every case of a wide decoder. Its properties still need review, its assumptions need covers, and the hardware below the source needs checks of its own, so it adds to the other two instead of replacing them.

11.Looking Ahead

Every check in this chapter could be measured against the truth because the decoder was small, and a production decoder is not.

The next chapter, Case Study: ECC in Processor Caches, places SEC-DED and its relatives inside a processor, where caches and register files choose their protection under tight area and delay limits, and reads the SEC-DED primitives of the open-source OpenTitan project as one implementation. Later, Project: A SEC-DED Encoder and Decoder builds the (72,64) Hsiao decoder, proves it with the methods of this chapter and synthesizes it, and Lab: Measuring Miscorrection injects triple and quadruple errors to measure what the code does beyond its envelope.

12.Worked Examples

The pattern 00010000001000001000000100 has ones at position 9, c1c_1, and position 2, d2d_2. By the lemma the syndrome is the XOR of their columns, 10110⊕01000=1111010110 \oplus 01000 = 11110, which is nonzero, has four ones and matches no column. The correct decoder therefore flips nothing, raises uncorrectable, and passes the data as received, 0110100101101001 with d2d_2 flipped, which is 0110110101101101. Its output (01101101,0,1)(01101101, 0, 1) is exactly spec(d,e)\mathrm{spec}(d, e). M2 raises the flag only for a syndrome with two ones, so it outputs (01101101,0,0)(01101101, 0, 0), a case both wrong and silent. It is one of the 26 patterns M2 gets wrong on every byte.

The pattern flips d0d_0 and d1d_1, a double error, so the guarantee asks for (d⊕eD,0,1)=(11111111,0,1)(d \oplus e_{\mathrm{D}}, 0, 1) = (11111111, 0, 1). The correct syndrome would be 11010⊕11001=0001111010 \oplus 11001 = 00011. The byte has d6=1d_6 = 1 and the pattern leaves d6d_6 alone, so r6=1r_6 = 1, and dropping it from s1s_1 flips that bit. The mutant's syndrome is 00011⊕01000=0101100011 \oplus 01000 = 01011, the column of d6d_6, so the mutant flips d6d_6, turning the received 1111111111111111 into 1011111110111111, and raises corrected. Its output (10111111,1,0)(10111111, 1, 0) has wrong data with the flag down, so the case is silent. On a byte with d6=0d_6 = 0 the same pattern would decode correctly, because there r6=0r_6 = 0 and dropping it changes nothing.

The hit rate is m/N=128/23,552=1/184m/N = 128/23{,}552 = 1/184, and Equation 7 with δ=10−6\delta = 10^{-6} gives T=⌈ln⁡106/−ln⁡(183/184)⌉=2,536T = \lceil \ln 10^6 / -\ln(183/184) \rceil = 2{,}536 draws, about a ninth of the 23,552 cases of the exhaustive sweep. That saving assumes the bug's size is known. The same confidence against a bug wrong on a single case takes 325,376 draws, 13.8 times the sweep, so for this decoder the exhaustive sweep is cheaper than any campaign aimed at the smallest bugs, and certain where the campaign is only probable.

M4 changes only the flip of d0d_0, which needs the hit for d0d_0 and r7=0r_7 = 0. The hit fires only when the syndrome is 1101011010, and inside the envelope only the single error in d0d_0 gives that syndrome, since double errors give even syndromes. On the zero codeword that error arrives with r7=0r_7 = 0, so the flip happens, and every other envelope pattern leaves the hit low, so M4 behaves like the correct decoder on all 92. On a byte with d7=1d_7 = 1 the same error arrives with r7=1r_7 = 1 and the flip is blocked. Half the bytes have d7=1d_7 = 1, so m=128m = 128, and each case is silent, since d0d_0 stays flipped while only corrected rises.

13.Exercises

References

  1. [1]Baumann, R. C. (2005). “Radiation-Induced Soft Errors in Advanced Semiconductor Technologies.” IEEE Transactions on Device and Materials Reliability, 5(3), pp. 305–316. doi:10.1109/TDMR.2005.853449
  2. [2]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
  3. [3]Chen, C. L. and Hsiao, M. Y. (1984). “Error-Correcting Codes for Semiconductor Memory Applications: A State-of-the-Art Review.” IBM Journal of Research and Development, 28(2), pp. 124–134. doi:10.1147/rd.282.0124
  4. [4]DeMillo, R. A. and Lipton, R. J. and Sayward, F. G. (1978). “Hints on Test Data Selection: Help for the Practicing Programmer.” Computer, 11(4), pp. 34–41. doi:10.1109/C-M.1978.218136
  5. [5]Verilator Project “Installation.” Verilator 5.054 documentation. Read 2026-11-14. https://verilator.org/guide/latest/install.html
  6. [6]cocotb Project “Installation.” cocotb 2.1 documentation. Read 2026-11-14. https://docs.cocotb.org/en/stable/install.html
  7. [7]cocotb Project “Simulator Support.” cocotb 2.1 documentation. Read 2026-11-14. https://docs.cocotb.org/en/stable/simulator_support.html
  8. [8]Mitzenmacher, Michael and Upfal, Eli (2005). “Probability and Computing: Randomized Algorithms and Probabilistic Analysis.” Cambridge University Press. doi:10.1017/CBO9780511813603
  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]Microsoft Research “The Z3 Theorem Prover.” GitHub repository Z3Prover/z3. Read 2026-11-15. https://github.com/Z3Prover/z3
  11. [11]YosysHQ “Installation.” Yosys documentation. Read 2026-11-14. https://yosyshq.readthedocs.io/projects/yosys/en/latest/getting_started/installation.html
  12. [12]YosysHQ “Reference for .sby file format.” SymbiYosys documentation. Read 2026-11-15. https://symbiyosys.readthedocs.io/en/latest/reference.html
  13. [13]YosysHQ “Installation guide.” SymbiYosys documentation. Read 2026-11-15. https://symbiyosys.readthedocs.io/en/latest/install.html

— Anirban

Hardware–software at the seam where compilers meet microcode.

FeedbackBook modePaper
error-correction-codinglinear-block-codes