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.
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 sits at codeword position and check bit at position . Making each row of Equation 1 sum to zero over the codeword gives , , , and , where is the exclusive OR, addition in .
Three conventions hold throughout. A data word is written with on the left, as a byte is usually printed, the reverse of the -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 , its check bits to are , and the pattern flips alone.
The decoder recomputes each row's sum from the received word , which gives the five syndrome bits to 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 flips data bit 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.
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.
| 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 for the data word, for its codeword, for the 13-bit error pattern, with a 1 wherever a bit flipped, and for the received word. Write for the number of ones in , and for its low eight bits, the part that lands on the data.
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 distributes over , so . Every codeword satisfies , because the encoder chose each check bit to make its row sum to zero, and so the first term vanishes.
Proof. By the lemma the syndrome of is , the XOR of the columns at the positions flips. With the syndrome is zero, so nothing is flipped and no flag rises. With the syndrome is the column of the flipped position . The thirteen columns are distinct, so the decoder identifies , 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 the syndrome is for . 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.
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.
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 with data bits, the envelope size and the number of cases are given by Equation 3.
For the (13,8) code that is cases, and every pattern of every weight on every byte is cases. At an assumed, not measured, rate of 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
| Code | Envelope patterns | Envelope cases | All cases |
|---|---|---|---|
| (13,8) | 92 | 23,552 | 2,097,152 |
| (22,16) | 254 | 16,646,144 | 274,877,906,944 |
| (39,32) | 781 | 3,354,369,458,176 | 2,361,183,241,434,822,606,848 |
| (72,64) | 2,629 | about | , about |
Source: reproduced by ch28_verifying_ecc_hardware.py.
At the same rate, one (72,64) codeword's envelope of patterns takes 2.6 microseconds. Every pattern on that one codeword, of them, would take 149,642 years, every envelope pattern on every data word 1.54 million years, and all cases about years.
The growth comes almost entirely from the data words, since the envelope grows only with the square of . 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 out of the XOR tree for , 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 to the flip of and never flips , a crossed wire between neighboring comparators. M4 lets the flip of happen only while is 0, a stray term of the kind a hand-edited equation picks up.
The excerpt below, from hdl/secded/secded_dec.sv, shows M2, M3 and M4 beside the correct logic. M1 lives in the tree for .
| // 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
| Decoder | The slip | Wrong cases | Silent | Wrong patterns on the zero codeword | Reduction identity |
|---|---|---|---|---|---|
| M0 | none | 0 | 0 | 0 | holds |
| M1 | left out of | 9,856 | 6,528 | 12 | fails in 9,856 cases |
| M2 | flag needs a weight-2 syndrome | 6,656 | 6,656 | 26 | holds |
| M3 | the hit for flips | 256 | 256 | 1 | holds |
| M4 | flips only while | 128 | 128 | 0 | fails 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 the syndrome is still zero, and 12 of the 92 patterns go wrong. Each flips , since only then is a 1, and the thirteenth that flips , paired with , decodes correctly, because its mutant syndrome matches no column and raises the flag. A codeword with arrives with 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 , so .
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 on every byte. The decoder sees the right syndrome, flips 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 on each byte with . There the stray term blocks the correction, corrected rises all the same, and the byte leaves with still flipped. M4 is right on every byte with , 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, is the low eight bits of a received word and the decoder's three outputs on .
Proof. Let . By the first two hypotheses, . The encoder is systematic, so the low eight bits of are and . Since and have the same syndrome, the third hypothesis gives and . The data output is therefore , and is , the data output when the zero codeword suffers the error , while the flags are . That is Equation 4. The guarantees have the same shape, since in each line of Equation 2 the data is XORed with something fixed by and the flags depend on alone, so is with XORed into its data. XORing the same into two words leaves them equal or unequal as they were, so the outputs of match the guarantee exactly when the outputs of do.
Counting over the 256 bytes gives , where 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, for M2 and 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 has a nonzero syndrome under it, and M4 breaks the third, since its flip of reads directly. On both the zero codeword misleads. It shows M1 wrong on 12 patterns where a byte with 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 received words, 8,192 for the (13,8) decoder and 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 and 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.
| 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, 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.
Proof. Split the campaign into stages. Stage starts once distinct items have been seen and ends at the draw that brings the -th new one. During stage each draw is new with probability , independently of the others. A trial that succeeds with probability takes tries on average, so stage lasts draws on average. The average of a sum is the sum of the averages, so the expected total is [8].
For the 92 envelope patterns , 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 . For the 2,629 patterns of the (72,64) envelope the average is draws, so the factor over an ordered sweep grows like .
Seeing every pattern is not catching every bug, since a bug may be wrong on only some bytes.
Proof. One draw lands on a wrong case with probability , so it misses with probability . The draws are independent, so the probability that all of them miss is the product of their separate probabilities, .
Setting the miss probability to at most a small target and solving for gives the length a campaign needs.
The approximation uses for small , and since is slightly larger than , the exact length is slightly shorter. With , 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 , 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 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.
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.
| 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 free input bits, the same 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.
| [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
| Task | Decoder | Assumption | Mode | Result |
|---|---|---|---|---|
| prove_m0 | M0 | prove | PASS | |
| prove_m1 | M1 | prove | FAIL, with a counterexample | |
| prove_m2 | M2 | prove | FAIL, with a counterexample | |
| prove_m3 | M3 | prove | FAIL, with a counterexample | |
| prove_m4 | M4 | prove | FAIL, with a counterexample | |
| cover_m0 | M0 | cover | PASS, every cover reached | |
| narrow_prove_m2 | M2 | prove | PASS | |
| narrow_cover_m2 | M2 | cover | FAIL, the weight-2 cover unreached | |
| empty_prove_m3 | M3 | weight 0, 1 and 2 at once | prove | ERROR, assumptions unsatisfiable |
| empty_cover_m3 | M3 | weight 0, 1 and 2 at once | cover | FAIL, 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 through the reference model, so it counts only once the model agrees the case is wrong. For M3 the solver chose with the single error in . The syndrome is , the column of , and M3 flips instead, giving where the guarantee asks for , wrong and silent. For M4 it chose with the single error in , and since the flip is blocked and the output is . For M2 it chose with errors in and , whose syndrome has four ones, so the output is 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
| Mutant | Hits, seed 28, 100 draws | Seeded miss share | Closed-form miss at 100 draws | Exhaustive simulation | Formal proof | |
|---|---|---|---|---|---|---|
| M1 | 9,856 | 33 | 0 | 0.000 | killed | killed |
| M2 | 6,656 | 29 | 0 | 0.000 | killed | killed |
| M3 | 256 | 1 | 0.3401 | 0.335 | killed | killed |
| M4 | 128 | 0 | 0.5883 | 0.580 | killed | killed |
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 has ones at position 9, , and position 2, . By the lemma the syndrome is the XOR of their columns, , which is nonzero, has four ones and matches no column. The correct decoder therefore flips nothing, raises uncorrectable, and passes the data as received, with flipped, which is . Its output is exactly . M2 raises the flag only for a syndrome with two ones, so it outputs , a case both wrong and silent. It is one of the 26 patterns M2 gets wrong on every byte.
The pattern flips and , a double error, so the guarantee asks for . The correct syndrome would be . The byte has and the pattern leaves alone, so , and dropping it from flips that bit. The mutant's syndrome is , the column of , so the mutant flips , turning the received into , and raises corrected. Its output has wrong data with the flag down, so the case is silent. On a byte with the same pattern would decode correctly, because there and dropping it changes nothing.
The hit rate is , and Equation 7 with gives 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 , which needs the hit for and . The hit fires only when the syndrome is , and inside the envelope only the single error in gives that syndrome, since double errors give even syndromes. On the zero codeword that error arrives with , 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 the same error arrives with and the flip is blocked. Half the bytes have , so , and each case is silent, since stays flipped while only corrected rises.
13.Exercises
References
- [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]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]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]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]Verilator Project “Installation.” Verilator 5.054 documentation. Read 2026-11-14. https://verilator.org/guide/latest/install.html
- [6]cocotb Project “Installation.” cocotb 2.1 documentation. Read 2026-11-14. https://docs.cocotb.org/en/stable/install.html
- [7]cocotb Project “Simulator Support.” cocotb 2.1 documentation. Read 2026-11-14. https://docs.cocotb.org/en/stable/simulator_support.html
- [8]Mitzenmacher, Michael and Upfal, Eli (2005). “Probability and Computing: Randomized Algorithms and Probabilistic Analysis.” Cambridge University Press. doi:10.1017/CBO9780511813603
- [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]Microsoft Research “The Z3 Theorem Prover.” GitHub repository Z3Prover/z3. Read 2026-11-15. https://github.com/Z3Prover/z3
- [11]YosysHQ “Installation.” Yosys documentation. Read 2026-11-14. https://yosyshq.readthedocs.io/projects/yosys/en/latest/getting_started/installation.html
- [12]YosysHQ “Reference for .sby file format.” SymbiYosys documentation. Read 2026-11-15. https://symbiyosys.readthedocs.io/en/latest/reference.html
- [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.