Paper
Part IILinear Block Codes

Lab: Measuring Miscorrection

November 16, 202647 min readbeginner

Triple and quadruple errors drawn at random into the (72,64) SEC-DED decoder under Verilator, the miscorrection rate measured with Wilson intervals, and Hsiao set against extended Hamming beside the exact counts.

One particle strike in a memory array can upset two or three neighboring cells at once [1], and a (72,64) SEC-DED code promises nothing about three errors. So when three bits of a stored word flip, how often does the decoder hand on a wrong data word with no flag? SECDED and Hsiao Codes answered by counting, 33,568 of the 59,640 possible triples for the balanced Hsiao code. This lab answers by experiment. It drives random triples and quadruples through the hardware decoder of Project: A SEC-DED Encoder and Decoder, measures the share that goes wrong in silence, puts an error bar on that share, and checks it against the count. A measurement that recovers a known answer can then be trusted where no count is possible.

Every number in the chapter is recomputed by ch31_lab_measuring_miscorrection.py in the python/ folder of the companion repository ecc-book-lab, and the charts are drawn by ch31_charts.py in the same folder. The GNU Octave twin ch31_lab_measuring_miscorrection.m prints the same lines, as The Octave Route explains. The hardware is the bench in hdl/ under secded72, the campaign is in tb/ under miscorrection, and the recorded counts are in data/ under ch31. Only the cocotb campaign has 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.What Leaves the Decoder

Write cc for the 72-bit codeword stored for a data word dd, and ee for the error pattern, a 72-bit word with a 1 at every flipped position. The decoder reads r=c⊕er = c \oplus e, where ⊕\oplus is bitwise addition modulo 2, and computes the syndrome s=HrTs = H r^{\mathsf{T}} with the 8×728 \times 72 check matrix HH. Every codeword has syndrome zero, so s=HeTs = H e^{\mathsf{T}}, the XOR of the columns hjh_j at the flipped positions. The decoder of Project: A SEC-DED Encoder and Decoder then does one of three things. A zero syndrome passes the word unchanged. A syndrome equal to a column hjh_j flips bit jj and raises the flag corrected. Any other syndrome raises uncorrectable.

What matters to the system reading the memory is the 64-bit word that leaves and whether a flag came with it. Sorting by those two facts gives four outcomes, drawn in Figure 1.

The four outcomes of decoding a received word. The received word r is the sent codeword c plus the error pattern e, bit by bit modulo 2, and its syndrome s equals H times e, so it depends on the error pattern alone. When s is zero the decoder passes r unchanged with no flag, and the result is correct when the data are right and undetected when they are wrong. When s equals column j of H the decoder flips bit j and sets corrected, and the result is correct when the data are right and miscorrected when they are wrong. When s is nonzero and matches no column the decoder sets uncorrectable, and the result is flagged. Undetected and miscorrected both hand on a wrong data word with no flag raised. Received word Syndrome Pass r unchanged Flip bit j Raise the flag Correct Undetected Correct Miscorrected Flagged r = c + e, mod 2 s = H r = H e corrected = 1 uncorrectable = 1 no flip, no flag sent data back wrong, no flag sent data back wrong, no flag word refused set by the error pattern alone s = 0 s equals column j s matches no column data right data wrong data right data wrong Undetected and miscorrected both hand on a wrong data word with no flag raised. They are the silent outcomes this lab counts on paper and measures on hardware.
Figure 1. The four outcomes of a decoded word, sorted by the syndrome and by whether the data that leave are right. Miscorrected and undetected words both leave wrong with no uncorrectable flag.

A flagged word costs a retry or a machine-check exception, but the system knows. A miscorrected or undetected word reaches a register as though it were good. The two differ in mechanism, a correction that leaves the data wrong against silence, and the chapter keeps them apart because they obey different counting rules.

02.Setting Up

Setting Up the Lab Bench installs the tools and a Python virtual environment holding cocotb [2], and this lab needs nothing new. The results were measured with the versions it records, Verilator 5.054 [3] and cocotb 2.1.0, and the software side needs only the Python standard library. With that environment active, the commands below, run from the root of the companion repository, reproduce every number and chart in the chapter.

Bash
python3 python/ch31_lab_measuring_miscorrection.py
octave --no-window-system --norc --quiet octave/ch31_lab_measuring_miscorrection.m
python tb/miscorrection/run_miscorrection.py
python3 python/ch31_charts.py --out figures

The first enumerates every triple and quadruple of the three codes, runs the software campaign, checks each result against the recorded data, and ends with All chapter 31 numbers reproduced. The second is its Octave twin. The third builds the bench under Verilator for each check matrix and runs the hardware campaign, failing if any case disagrees with the model, in about 4 to 6 seconds per matrix once compiled. The fourth draws the four charts into figures/.

03.Triples and Quadruples, Proved

The three matrices are those of SECDED and Hsiao Codes. Both Hsiao matrices follow Hsiao's construction from odd-weight columns [4]. The balanced one takes all 56 columns of weight 3 and eight weight-5 columns that SECDED and Hsiao Codes chose as rotations of one another. The dictionary Hsiao matrix takes the same 56 and the first eight weight-5 columns in dictionary order, so it agrees with the balanced one at 65 of the 72 positions. The extended Hamming matrix gives position jj the column j+128j + 128, the binary number jj with a 1 added in row 7 [5]. In all three the eight check bits sit at fixed positions, 64 to 71 for Hsiao and 0, 1, 2, 4, 8, 16, 32 and 64 for extended Hamming. Two lemmas cover all three at once.

π(s)=wt(e) mod 2\pi(s) = \mathrm{wt}(e) \bmod 2

(1)

Proof. Both versions of π\pi are XORs of fixed syndrome bits, so π(x⊕y)=π(x)⊕π(y)\pi(x \oplus y) = \pi(x) \oplus \pi(y). Every Hsiao column has odd weight, and every extended Hamming column has a 1 in row 7, so π(hj)=1\pi(h_j) = 1 at every position jj. The syndrome is the XOR of wt(e)\mathrm{wt}(e) columns, so π(s)\pi(s) is the XOR of wt(e)\mathrm{wt}(e) ones, which is 1 exactly when wt(e)\mathrm{wt}(e) is odd. ■\blacksquare

Proof. A nonzero codeword with ones only at check positions would make the XOR of a nonempty set of check columns zero. The Hsiao check columns are the eight unit vectors, and a nonempty XOR of distinct unit vectors is never zero. The extended Hamming check columns are 128128 at position 0 and 128+2k128 + 2^k at position 2k2^k for kk from 0 to 6. An XOR of some of them has bit kk set for each 128+2k128 + 2^k it uses, so a zero XOR uses none of those, and what remains is 128128 alone or nothing, which forces the empty set. ■\blacksquare

The script checks the lemma by counting the codewords on the check positions alone, 0 for all three codes. So any nonzero codeword the decoder adds to the stored word shows up in the data.

Proof. By Equation 1, π(s)=1\pi(s) = 1, so s≠0s \neq 0 and the decoder either flips a bit or raises uncorrectable. If ss matches no column, the word is flagged. If s=hjs = h_j, position jj is not one of the three flipped positions aa, bb and cc, because ha⊕hb⊕hc=hah_a \oplus h_b \oplus h_c = h_a would force hb=hch_b = h_c, and the columns are distinct. The decoder therefore leaves c⊕e⊕ujc \oplus e \oplus u_j, where uju_j has a single 1 at position jj. The word e⊕uje \oplus u_j has weight 4 and syndrome s⊕hj=0s \oplus h_j = 0, so it is a nonzero codeword, and by the second lemma it changes at least one data bit. The word is miscorrected. ■\blacksquare

SECDED and Hsiao Codes proved the Hsiao case as its theorem What an odd-weight-column decoder does with three errors, in the section Three Errors. The functional π\pi carries the same argument to extended Hamming, whose columns do not all have odd weight.

Proof. The proof above sends each miscorrected triple ee to the codeword e⊕uje \oplus u_j. A weight-4 codeword xx is reached from exactly four triples, x⊕ujx \oplus u_j for each of its four positions jj, since each such triple has syndrome hjh_j and is pushed back onto xx. Distinct columns make jj unique for each triple, so the map is four to one onto the weight-4 codewords. ■\blacksquare

Proof. By Equation 1, π(s)=0\pi(s) = 0. Every column has π(hj)=1\pi(h_j) = 1, so ss equals no column and the decoder never flips a bit. If s=0s = 0, the pattern is a codeword, and by the second lemma it changes data that pass with no flag, so the word is undetected. Otherwise ss is nonzero and matches no column, and the word is flagged. ■\blacksquare

Weight Distributions and Undetected Errors proved the general form of this as Theorem: Undetected patterns are the nonzero codewords, in the section When a Check Stays Silent, for a decoder that only detects. Here the decoder corrects as well, and the parity functional is what stops a quadruple from passing for a single error.

Proof. The two theorems give the shares in Equation 2. Their ratio is 4(724)/(723)=4⋅694=694\binom{72}{4}/\binom{72}{3} = 4 \cdot \tfrac{69}{4} = 69, since (nk+1)=(nk)n−kk+1\binom{n}{k+1} = \binom{n}{k}\tfrac{n-k}{k+1} with n=72n = 72 and k=3k = 3. ■\blacksquare

pM(3)=4A4(723),pU(4)=A4(724)p_{\mathrm{M}}(3) = \frac{4A_4}{\binom{72}{3}}, \qquad p_{\mathrm{U}}(4) = \frac{A_4}{\binom{72}{4}}

(2)

Both shares the lab measures are therefore set by one number per code, the count A4A_4 of weight-4 codewords.

04.Counting Every Pattern

The exact shares come from listing every pattern. The function outcome() in python/ch31_lab_measuring_miscorrection.py decides the fate of one pattern from the positions it flips, and the hardware campaign is checked against the same function.

Python
def outcome(code: Code, positions) -> str:
"""What the decoder does with the error pattern that flips these positions.
The syndrome is the XOR of the flipped columns. A zero syndrome leaves the
word alone, a syndrome equal to column j flips bit j, and any other syndrome
raises the uncorrectable flag. The outcome is then read from the data bits
that leave the decoder: no flag and no data bit wrong is correct, no flag and
some data bit wrong is a miscorrection if a bit was flipped and an undetected
error if none was.
"""
s = 0
e = 0
for p in positions:
s ^= code.cols[p]
e ^= 1 << p
if s == 0:
return UNDETECTED if e & code.data_mask else CORRECT
j = code.position_of.get(s)
if j is None:
return FLAGGED
return MISCORRECTED if (e ^ (1 << j)) & code.data_mask else CORRECT

The data_mask holds a 1 at each of the 64 data positions, so e & code.data_mask is nonzero exactly when a data bit is wrong. Feeding it every combination from itertools.combinations(range(72), w) for w=3w = 3 and w=4w = 4 gives Table 1.

Table 1. Every triple and every quadruple of the three codes, classified

CodeTriples miscorrectedTriples flaggedShareQuadruples undetectedQuadruples flaggedShare
Hsiao, balanced33,56826,07256.284%8,3921,020,3980.816%
Hsiao, dictionary34,03225,60857.062%8,5081,020,2820.827%
extended Hamming45,30414,33675.962%11,3261,017,4641.101%

Source: ch31_lab_measuring_miscorrection.py, which lists all 59,640 triples and all 1,028,790 quadruples of each code.

The table bears out both theorems. Every triple count is four times its quadruple count, and for the balanced code 56.284/69=0.81656.284/69 = 0.816.

Two more routes reach the same A4A_4. The script's syndrome_counts() builds a table Nw[s]N_w[s], the number of patterns of weight ww with syndrome ss, one position at a time. A pattern leaves the new position tt out or uses it and has its syndrome moved by hth_t, so adding tt turns Nw[s]N_w[s] into Nw[s]+Nw−1[s⊕ht]N_w[s] + N_{w-1}[s \oplus h_t]. For every w≥2w \ge 2 the second lemma then gives Mw=∑jNw[hj]M_w = \sum_j N_w[h_j] and Uw=Nw[0]U_w = N_w[0], because a pattern with syndrome hjh_j is pushed onto the nonzero codeword e⊕uje \oplus u_j and a pattern with syndrome 0 is itself one. The section The MacWilliams Identity of Weight Distributions and Undetected Errors gives A4A_4 a third time, from the weights of the 256 words the rows of HH span [6]. All three routes agree for all three codes.

Listing is cheap here. One code has 59,640+1,028,790=1,088,43059{,}640 + 1{,}028{,}790 = 1{,}088{,}430 patterns of weight 3 or 4, and the script classifies all 3,265,290 of the three codes in about a second.

Three changes take that cheapness away. Heavier patterns multiply fast, since (725)=13,991,544\binom{72}{5} = 13{,}991{,}544 is 13.6 times the weight-4 count and (728)=11,969,016,345\binom{72}{8} = 11{,}969{,}016{,}345 is 11,634 times it. Longer codes defeat the recursion, since rr check bits need 2r2^r syndrome bins, 4,294,967,296 for r=32r = 32. And a decoder that does not act on the syndrome alone defeats both methods, because its outcome can then depend on the data word, which no table indexed by ss can hold. Sampling survives all three changes, and this lab calibrates it where the exact answer is known.

05.The Bench

The hardware is secded72_bench from Project: A SEC-DED Encoder and Decoder, which encodes a 64-bit data word, XORs a 72-bit error pattern into the codeword and decodes the result in one combinational pass. Its parameter CODE picks the check matrix, and the campaign builds it once for each. Its parameter FLAG picks the form of the uncorrectable flag, and the campaign uses FLAG=0, the no-match form, which raises the flag when s≠0s \neq 0 and no column matches. Figure 2 shows how the campaign surrounds it.

The miscorrection campaign around the (72,64) bench. A draw block fed by random.Random(31) forms 100,000 error patterns of weight 3 and then 100,000 of weight 4, each with its own random data word d made from two draws and an error pattern e whose positions are drawn one at a time, a repeat drawn again. Inside the bench secded72_bench, built by Verilator, the encoder turns the 64 data bits into a 72-bit codeword c, a row of XOR gates adds the 72-bit pattern e to it, and the decoder returns 66 bits, the 64 data bits out and the two flags corrected and uncorrectable. A classify block sorts each case into correct, flagged, miscorrected or undetected from those outputs and checks it against the Python model and the outcome predicted from the error pattern alone, which receive the same pair. A tally block counts each outcome by weight and keeps running totals. For each matrix the run drives 200,210 cases, 200,000 drawn and 210 adjacent windows, with 0 disagreements, in about 4 to 6 seconds. secded72_bench, built by Verilator Seeded draws Random(31) 100,000 patterns of weight 3, then 100,000 of weight 4 d from two draws e one position a draw, a repeat drawn again Encoder Decoder Model and prediction secded72_model, outcome() Classify one of four outcomes from the outputs, checked against the model and the prediction Tallies counts by weight, running totals d 64 e 72 66 c the same pair expected Per (72,64) matrix: 200,210 cases, 200,000 drawn and 210 adjacent windows 0 disagreements with the model or the prediction, about 4 to 6 s for each matrix
Figure 2. The campaign around the bench. Each case is checked against the reference model and against the outcome predicted from the error pattern alone.

Each case comes from draw() in python/ch31_lab_measuring_miscorrection.py.

Python
def draw(rng: random.Random, weight: int) -> tuple:
"""One case of the campaign: a 64-bit data word and `weight` distinct positions.
Only rng.random() is used, the one method whose sequence Python's
documentation promises across versions. Each half of the data word is a
random() draw scaled to 32 bits, and each position is a draw scaled to 72
and truncated, drawn again whenever it repeats one already chosen, so every
set of `weight` positions is equally likely, to a few parts in 10**14.
"""
data = int(rng.random() * 2 ** 32) | int(rng.random() * 2 ** 32) << 32
positions = []
while len(positions) < weight:
p = int(rng.random() * N)
if p not in positions:
positions.append(p)
return data, positions

Python's random.Random is the Mersenne Twister [7], and random() is the one method whose sequence Python's documentation promises to keep across versions [8], so seed 31 gives the same campaign on any machine. Drawing again on a repeat makes every ordered sequence of ww distinct positions equally likely, and each set is reached by the same w!w! orderings, so every set is equally likely. The one departure is that random() returns one of 2532^{53} values, which split into 72 bins unevenly by less than one part in 101410^{14}.

The campaign draws 100,000 patterns of weight 3 and then 100,000 of weight 4 from one generator seeded with 31. The loop that drives them is in tb/miscorrection/test_miscorrection.py.

Python
for w, d, positions in lab.campaign_cases(SEED, DRAWS, WEIGHTS):
found = await run.case(d, positions)
counts[w][found] += 1
letters[w].append(LETTER[found])
if len(letters[w]) in lab.CHECKPOINTS:
running[w].append(counts[w][lab.tracked(w)])

run.case() writes the data word and the pattern into the bench and sorts the case from the outputs alone. A raised uncorrectable is flagged, data equal to dd is correct, a raised corrected with wrong data is miscorrected, and wrong data with neither flag is undetected. The case is then checked against the Python model secded72_model.py and against what outcome() predicts from the positions, and the test fails on any disagreement. The running count of the tracked outcome, miscorrected for triples and undetected for quadruples, is saved at ten checkpoints from 100 draws to 100,000.

Each case carries its own random data word, though the outcome cannot depend on it. The theorem One codeword stands for all, in the section When One Codeword Stands for All of Verifying ECC Hardware, says that when the encoder is systematic, the decoder outputs the received data bits XOR a flip mask, the syndrome is linear over GF(2)\mathrm{GF}(2), every codeword has syndrome zero, and the flip mask and the flags depend on the received word only through the syndrome, then the wrong data bits and the flags depend on the error pattern alone. The random data test those hypotheses rather than lean on them, since a wiring fault in the encoder, or a decoder that reads a data bit it should not, breaks them for some data words, and the prediction check fails the moment an outcome depends on dd.

06.Running the Campaign

The command python tb/miscorrection/run_miscorrection.py builds the bench and runs the campaign for each matrix in turn, 100,000 drawn cases of each weight plus the 210 adjacent windows that the section on bursts uses, 200,210 cases per matrix. On the recorded run every case agreed with the model and with the prediction, and a whole run took about 12 to 19 seconds once built. Only the default run, seed 31 with 100,000 draws of weights 3 and 4, writes its counts to data/ch31/miscorrection_counts.json, so an exercise never overwrites the record. Table 2 lists the counts.

Table 2. The hardware campaign, 100,000 draws of each weight per matrix, with 95% Wilson intervals

CodeTriples miscorrectedTriples flaggedRate and intervalQuadruples undetectedQuadruples flaggedRate and interval
Hsiao, balanced56,22243,77856.222%, 55.914 to 56.52986499,1360.864%, 0.808 to 0.923
Hsiao, dictionary56,98443,01656.984%, 56.677 to 57.29182999,1710.829%, 0.775 to 0.887
extended Hamming75,97524,02575.975%, 75.709 to 76.2391,12298,8781.122%, 1.059 to 1.189

Source: data/ch31/miscorrection_counts.json, recorded by run_miscorrection.py with seed 31, and the intervals of ch31_lab_measuring_miscorrection.py.

No triple came out correct or undetected and no quadruple correct or miscorrected, in hardware as in the theorems. The software script draws the same 600,000 patterns through outcome() and checks that its counts, running counts included, equal the hardware's.

07.Reading a Rate

A measured count needs a statement of how far it could sit from the truth. Verifying ECC Hardware asked of random draws whether a campaign meets a wrong case at all, through the theorems Coupon collector and Miss probability in its section Random Fault-Injection Campaigns. Here the question is how often the draws land in a class, and the answer is a proportion with an error bar.

Each draw either lands in the tracked outcome or not. Write pp for the true share and mm for the number of hits in NN independent draws. Then mm follows the binomial distribution, the estimate is p^=m/N\hat p = m/N, and, because each draw contributes a variance p(1−p)p(1-p) and the variances of independent draws add, the standard error of p^\hat p is given by Equation 3.

SE(p^)=p(1−p)N\mathrm{SE}(\hat p) = \sqrt{\frac{p(1-p)}{N}}

(3)

For the balanced code at 100,000 draws this is 0.157 percentage points. The usual normal rule puts a 95% interval at p^±1.96 SE\hat p \pm 1.96\,\mathrm{SE}, because a normal variable lies within 1.96 standard deviations of its mean 95% of the time. That rule plugs p^\hat p in for the unknown pp and fails where it is needed most. Near a share of 0.8% and at small NN its intervals cover the truth far less often than 95% of the time, and they can reach below zero [9].

p^+z22N±zp^(1−p^)N+z24N21+z2N\frac{\hat p + \dfrac{z^2}{2N} \pm z\sqrt{\dfrac{\hat p(1-\hat p)}{N} + \dfrac{z^2}{4N^2}}}{1 + \dfrac{z^2}{N}}

(4)

Wilson's idea [10] is to keep the unknown pp inside the square root and ask which values of pp the observed p^\hat p is consistent with. Squaring the condition gives (p^−p)2≤z2p(1−p)/N(\hat p - p)^2 \le z^2 p(1-p)/N, a quadratic inequality in pp, and its two roots are the endpoints. The interval never leaves [0,1][0, 1], its center is pulled from p^\hat p toward 1/21/2, and its coverage stays close to 95% even for small counts [11]. The script's wilson() computes it.

Python
def wilson(m: int, n: int, z: float = Z) -> tuple:
"""The Wilson score interval for a proportion, m successes in n trials."""
ph = m / n
center = ph + z * z / (2 * n)
half = z * sqrt(ph * (1 - ph) / n + z * z / (4 * n * n))
scale = 1 + z * z / n
return (center - half) / scale, (center + half) / scale

For the balanced triples at 100,000 draws it gives 55.914% to 56.529%, a half-width of 0.307 points, almost exactly the normal rule's, because the two agree at large counts.

Turned around, the normal rule says how many draws a target needs. A half-width hh at level zz takes the number of draws in Equation 5.

N=⌈z2 p(1−p)h2⌉N = \left\lceil \frac{z^2\, p(1-p)}{h^2} \right\rceil

(5)

For one percentage point at the balanced share, N=⌈1.962×0.56284×0.43716/0.012⌉=9,453N = \lceil 1.96^2 \times 0.56284 \times 0.43716 / 0.01^2 \rceil = 9{,}453, and p=1/2p = 1/2, the worst case, needs 9,604. The rule needs a guess at pp and promises nothing exact. Two bounds promise something for every NN and every pp.

Pr⁡(∣p^−p∣≥h)≤p(1−p)Nh2≤14Nh2\Pr\bigl(|\hat p - p| \ge h\bigr) \le \frac{p(1-p)}{N h^2} \le \frac{1}{4Nh^2}

(6)

Proof. For a random variable Y≥0Y \ge 0 and a number a>0a > 0, the inequality a⋅1[Y≥a]≤Ya \cdot \mathbf{1}[Y \ge a] \le Y holds at every outcome, since the left side is a≤Ya \le Y when Y≥aY \ge a and 0 otherwise. Taking expectations gives Markov's inequality, aPr⁡(Y≥a)≤E[Y]a \Pr(Y \ge a) \le \mathrm{E}[Y]. Apply it with Y=(p^−p)2Y = (\hat p - p)^2 and a=h2a = h^2. The event Y≥h2Y \ge h^2 is the event ∣p^−p∣≥h|\hat p - p| \ge h, and E[Y]\mathrm{E}[Y] is the variance of p^\hat p. A single draw Xi∈{0,1}X_i \in \{0, 1\} has E[Xi2]=E[Xi]=p\mathrm{E}[X_i^2] = \mathrm{E}[X_i] = p, so its variance is p−p2=p(1−p)p - p^2 = p(1-p). The variances of NN independent draws add to Np(1−p)Np(1-p), and dividing mm by NN divides the variance by N2N^2, which leaves p(1−p)/Np(1-p)/N and the first inequality. The second holds because 14−p(1−p)=(p−12)2≥0\tfrac14 - p(1-p) = (p - \tfrac12)^2 \ge 0. ■\blacksquare

Setting the right side to δ=0.05\delta = 0.05 and solving gives N=1/(4δh2)N = 1/(4\delta h^2), which is 50,000 draws for one point with at least 95% certainty, whatever the share. A sharper bound decays exponentially in NN.

Pr⁡(∣p^−p∣≥h)≤2e−2Nh2\Pr\bigl(|\hat p - p| \ge h\bigr) \le 2e^{-2Nh^2}

(7)

Hoeffding proved it for any bounded independent draws. The proof applies Markov's inequality to an exponential of p^−p\hat p - p rather than to its square, the method of Chernoff bounds [12], and is not repeated here. Setting the bound to δ\delta gives N=ln⁡(2/δ)/(2h2)N = \ln(2/\delta)/(2h^2), which is 18,445 draws for one point at 95%. Figure 3 sets the three rules side by side. At 100,000 draws Chebyshev guarantees 0.707 points and Hoeffding 0.429, against 0.310 from the normal rule at p=1/2p = 1/2, and the normal rule at the quadruple share of 0.816% gives 0.056, because a rare outcome has a small variance. The bounds are the safe answer before anything is known, and the normal and Wilson rules are the sharp answer once the count is in.

Half-width of a 95 percent interval against the number of draws one point 100,000 draws Chebyshev, any rate Hoeffding, any rate normal, rate 56.28% normal, rate 0.816% 100 1,000 10,000 100,000 1,000,000 0.01 0.1 1 10 Draws, on a logarithmic scale Half-width, percentage points
Figure 3. Half-width of a 95% interval against the number of draws. The two bounds hold at any share, and the normal rule is drawn at the two balanced shares. Data: drawn by ch31_charts.py from the draw count in data/ch31/miscorrection_counts.json and the bounds of ch31_lab_measuring_miscorrection.py.

The campaign saved its running counts, and it is tempting to watch the interval shrink and stop once it looks settled. Figure 4 draws the running share at each checkpoint with its interval.

Running shares of the campaign with their intervals, against the exact shares Triples, running share miscorrected, percent 40 50 60 70 80 90 100 1,000 10,000 100,000 Hamming, exact 75.962 dictionary, exact 57.062 balanced, exact 56.284 Quadruples, running share undetected, percent 0.4 0.8 1.2 1.6 2.0 2.4 2.8 100 1,000 10,000 100,000 Hamming, exact 1.101 balanced, exact 0.816 dictionary, exact 0.827 Draws so far, on a logarithmic scale interval contains the exact share interval misses it exact share
Figure 4. The running share at each checkpoint with its Wilson interval, triples from 100 draws and quadruples from 1,000. Hollow markers are intervals that miss the exact share. Data: drawn by ch31_charts.py from the running counts in data/ch31/miscorrection_counts.json and the exact shares and intervals of ch31_lab_measuring_miscorrection.py.

08.Measured Against Exact

Figure 5 puts the six measured rates and their intervals beside the exact shares of Table 1.

Measured miscorrection and undetected rates beside the exact shares Triples, share miscorrected, percent balanced measured 56.222, interval 55.914 to 56.529, exact 56.284 dictionary measured 56.984, interval 56.677 to 57.291, exact 57.062 Hamming measured 75.975, interval 75.709 to 76.239, exact 75.962 55 60 65 70 75 80 Quadruples, share undetected, percent balanced measured 0.864, interval 0.808 to 0.923, exact 0.816 dictionary measured 0.829, interval 0.775 to 0.887, exact 0.827 Hamming measured 1.122, interval 1.059 to 1.189, exact 1.101 0.7 0.8 0.9 1.0 1.1 1.2 measured on 100,000 draws, with its 95% Wilson interval exact share, every pattern counted
Figure 5. Measured rates with their 95% Wilson intervals beside the exact shares, for triples and quadruples and all three matrices. Every interval contains its exact share. Data: drawn by ch31_charts.py from data/ch31/miscorrection_counts.json and the exact shares and intervals of ch31_lab_measuring_miscorrection.py.

All six intervals contain their exact shares. That was likely, not certain, since six independent 95% intervals would all hold with probability 0.956=0.7350.95^6 = 0.735, and these six are not independent, because all three matrices were run on the same patterns. A single miss would not have been a hardware failure. The evidence is the agreement across both outcomes and all three matrices, with the model and the prediction agreeing on every one of the 600,630 cases.

The chart's largest feature is the gap between the two families. Extended Hamming miscorrects 76% of triples against Hsiao's 56%, and SECDED and Hsiao Codes explained why in Proposition: Triples inside positions 0 to 63. Position jj of the extended Hamming code holds j+128j + 128, so for three positions aa, bb and cc below 64 the XOR of their columns has bit 7 set, bit 6 clear and low six bits v=a⊕b⊕cv = a \oplus b \oplus c, which is the column of position vv, itself below 64. Every one of the (643)=41,664\binom{64}{3} = 41{,}664 such triples is miscorrected. The 8 high positions, 64 to 71, supply the rest. All 1,792 triples with two high positions and all 56 with three are miscorrected by the same XOR argument, and of the 16,128 with one, the 1,792 whose two low positions agree in bits 3 to 5 are. The total is 41,664+1,792+1,792+56=45,30441{,}664 + 1{,}792 + 1{,}792 + 56 = 45{,}304.

Hsiao's share sits near a simple benchmark. Every triple's syndrome has odd weight, there are 128 odd-weight syndromes, and 72 of them are columns, so a syndrome spread evenly over the 128 would be miscorrected with probability 72/128=56.25%72/128 = 56.25\%. The balanced matrix comes within 0.04 points of that. The low six bits of the Hamming columns below 64 take all 64 values, the property that made positions 1 to 63 the perfect (63,57) Hamming code of Hamming Codes and Perfect Codes, so any three such columns XOR to a fourth, and that closure herds triples onto columns.

The two Hsiao matrices make a finer test. Their exact triple shares differ by 464/59,640=0.778464/59{,}640 = 0.778 points, from 5,583 triples miscorrected by the balanced matrix alone against 6,047 by the dictionary matrix alone, and their intervals barely separate. Both matrices saw the same 100,000 patterns, which gives a sharper tool. For each pattern let DD be 1 if only the dictionary matrix miscorrects it, −1-1 if only the balanced one does, and 0 otherwise. With aa and bb the shares miscorrected by the balanced and the dictionary matrix alone, DD has mean b−ab - a and variance a+b−(b−a)2a + b - (b - a)^2, less than half the sum of the two separate variances, because the patterns both miscorrect cancel. The campaign had 9,392 draws for the balanced matrix alone and 10,154 for the dictionary matrix alone, a paired difference of 0.762 points with 95% interval 0.488 to 1.036 by the normal rule, safe here because both counts run to thousands. It excludes zero and contains the exact 0.778. Two separate campaigns of this size would most likely settle it too, but with a half-width of 0.434 points against the paired 0.274, so pairing buys the same certainty from about 40% of the draws.

09.Bursts of Adjacent Cells

A particle strike does not choose three positions at random. It upsets cells that sit next to each other, and which codeword bits those cells hold is the memory designer's choice. Model the word as a row of 72 cells and call the assignment of bits to cells the layout. A strike on three adjacent cells hits one of 70 windows, cells kk, k+1k+1 and k+2k+2 for kk from 0 to 69, and the question becomes how many of the 70 are miscorrected.

In the natural layout, cell kk holds bit kk. The first window of the balanced Hsiao code holds positions 0, 1 and 2, whose columns cover rows 0, 1 and 2, rows 0, 1 and 3, and rows 0, 1 and 4. Rows 0 and 1 appear three times and survive the XOR, so the syndrome covers rows 0 to 4, which is the column of position 56. The decoder flips data bit 56 and the window is miscorrected. Figure 6 follows the first windows of three layouts.

Three layouts of the 72 codeword bits of the balanced Hsiao code along a row of cells, with the first 14 cells of each and the outcome of the first 12 windows of three adjacent cells. In the natural order the cells hold bits 0 to 13 and the windows read M F F M F F F F F F F F, and 35 of the 70 windows are miscorrected. In the stride-11 order the cells hold bits 0, 11, 22, 33, 44, 55, 66, 5, 16, 27, 38, 49, 60 and 71 and the windows read M F M M M F F M F M F M, and 39 of 70 are miscorrected. In the searched order the cells hold bits 0, 1, 3, 2, 4 and then 5 to 13 and every window reads F, and none of the 70 is miscorrected. M marks a miscorrected window and F a flagged one. Bit held by each of the first 14 cells, and the outcome of each window of three cells window 0, the burst on cells 0, 1 and 2 Natural order Stride 11 Searched order 35 of 70 miscorrected 39 of 70 miscorrected 0 of 70 miscorrected 012345678910111213 01122334455665162738496071 013245678910111213 MFFMFFFFFFFF MFMMMFFMFMFM FFFFFFFFFFFF Each letter sits under the middle cell of its window. M miscorrected, a wrong word with no flag. F flagged.
Figure 6. The first windows of three adjacent cells in three layouts of the balanced Hsiao code. The searched order flags every window.

A stride layout puts bit Sk mod 72Sk \bmod 72 in cell kk, for a stride SS that shares no factor with 72, so that every bit lands in exactly one cell. The script also searches, depth first, for an order in which no window is miscorrected. No such order exists for extended Hamming, as the lemma below shows, so no search runs for it and its searched row repeats stride 11. Table 3 lists the results.

Table 3. Windows of three adjacent cells miscorrected, of 70, by layout

LayoutHsiao, balancedHsiao, dictionaryextended Hamming
natural352870
stride 5494865
stride 7434253
stride 11394246
stride 13393346
stride 29332946
searched0046 (stride 11)
random order, expected39.4039.9453.17

Source: ch31_lab_measuring_miscorrection.py. The bench drove the natural, stride-11 and searched layouts in hardware and agreed with the script on every window, 210 for each Hsiao matrix and 140 distinct ones for extended Hamming, whose searched layout repeats stride 11.

The uniform share of Table 1 is a property of the code. The adjacent share is a property of the code and the layout together, and it runs from 0 to 49 of 70 windows for the balanced matrix. The searched order, found in 5,039 steps of the search for the balanced matrix and 8,291 for the dictionary one, flags every adjacent triple, so a three-cell burst under that layout is always caught. A random layout lands on average at 70 times the uniform share, 39.40, 39.94 and 53.17 windows, because each window is then a uniformly random set of three positions and expectations add over the 70 windows. A layout chosen with care beats that by a wide margin, and a careless one, such as the natural layout for extended Hamming, loses every window.

Proof. A window whose three positions all lie below 64 is miscorrected, by the closure argument of the previous section. Each of the 8 high positions sits in at most 3 windows, so at most 24 windows hold a high position, and at least 70−24=4670 - 24 = 46 hold low positions only. ■\blacksquare

Strides 11, 13 and 29 reach that floor exactly, and the script checks that no layout it tries flags more than 24 windows. Figure 7 draws the whole table. The layout can rescue Hsiao from three-cell bursts completely and can never rescue extended Hamming.

Miscorrected windows of three adjacent cells in seven layouts 0 10 20 30 40 50 60 70 natural 35 28 70 stride 5 49 48 65 stride 7 43 42 53 stride 11 39 42 46 stride 13 39 33 46 stride 29 33 29 46 searched 0 0 46* random expected 39.40 39.94 53.17 balanced dictionary Hamming Hamming floor in any layout, 46 windows Windows miscorrected, of 70 balanced Hsiao dictionary Hsiao extended Hamming hollow, a random order * No search runs for extended Hamming, so its searched bar repeats stride 11.
Figure 7. Windows of three adjacent cells miscorrected, of 70, in seven layouts and under a random order. No layout takes extended Hamming below 46, and its searched bar repeats stride 11. Data: drawn by ch31_charts.py from data/ch31/miscorrection_counts.json for the layouts the bench drove, and from ch31_lab_measuring_miscorrection.py for the other layouts and the random expectation.

Case Study: ECC in Processor Caches described the usual defense in its section Bursts and Interleaving, which gives adjacent cells to different words so that a strike across three cells puts one error into each of three words. Without interleaving of degree at least the burst length, the layout of one word's bits decides the adjacent share.

10.What a Designer Does With the Number

A miscorrected share is a conditional probability, the chance of silent corruption given a triple. Multiplying it by how often triples occur turns it into a rate.

Take an illustrative memory of W=4,096W = 4{,}096 words, each struck at a rate λ=10−6\lambda = 10^{-6} upsets per word-hour and scrubbed every tt hours. A scrub reads every word and writes back its corrected value [13], so a word gathers errors only between scrubs. With μ=λt\mu = \lambda t, the number of strikes on one word in one interval is Poisson, and exactly three occur with probability μ36e−μ\tfrac{\mu^3}{6}e^{-\mu}. Those three must land on different cells to make a triple, since a second strike on a cell flips it back, and three strikes on 72 cells are all distinct with probability D=71×70722=0.9587D = \tfrac{71 \times 70}{72^2} = 0.9587. A year holds Y/tY/t intervals, with Y=8,760Y = 8{,}760 hours, so the silent-corruption rate from triples is given by Equation 8.

Rsilent=W⋅Yt⋅μ36 e−μ⋅D⋅pM(3)R_{\mathrm{silent}} = W \cdot \frac{Y}{t} \cdot \frac{\mu^3}{6}\, e^{-\mu} \cdot D \cdot p_{\mathrm{M}}(3)

(8)

Table 4. Silent corruptions a year from triples, 4,096 words at an illustrative upset rate

CodeScrub every dayScrub every 30 daysScrub every year
Hsiao, balanced1.86×10−91.86 \times 10^{-9}1.67×10−61.67 \times 10^{-6}2.45×10−42.45 \times 10^{-4}
extended Hamming2.51×10−92.51 \times 10^{-9}2.26×10−62.26 \times 10^{-6}3.31×10−43.31 \times 10^{-4}

Source: ch31_lab_measuring_miscorrection.py, at 10−610^{-6} upsets per word-hour.

The model ignores four or more strikes between scrubs, rarer again by a factor of about μ/4\mu/4, and the rate shows the shape of the answer rather than describing a real part. Two levers move the result. The code moves it by the ratio of the shares, 0.75962/0.56284=1.3500.75962/0.56284 = 1.350 in favor of Hsiao, whatever the scrub interval. The scrub moves it far more, because Ytμ3=Yλ3t2\tfrac{Y}{t}\mu^3 = Y\lambda^3 t^2 makes the rate grow as the square of the interval, and going from a 30-day scrub to a daily one buys a factor of 899.4, close to 302=90030^2 = 900. A designer who cannot change the code can still buy silent corruption down, as long as the triples build up one strike at a time.

Bursts do not build up. One particle strike can upset several neighboring cells at once [1], so the errors of a burst arrive together and no scrub interval is short enough to separate them. For bursts the levers are those of the previous section, a layout that flags adjacent triples, interleaving that spreads them across words, or a stronger code.

11.Looking Ahead

The codes measured here needed only XOR over GF(2)\mathrm{GF}(2). The codes ahead, cyclic codes and then BCH and Reed–Solomon, catch long bursts and correct several errors or whole bytes at once, and locating those errors means solving equations that need division in fields larger than GF(2)\mathrm{GF}(2). Rings and Fields builds those fields, opening the part on finite fields and their arithmetic.

12.Worked Examples

Position jj holds the column j+128j + 128, so the columns are 131, 133 and 137. Their XOR has bit 7 set, since it appears three times, and low bits 3⊕5⊕93 \oplus 5 \oplus 9. In binary 3⊕5=011⊕101=110=63 \oplus 5 = 011 \oplus 101 = 110 = 6 and 6⊕9=0110⊕1001=1111=156 \oplus 9 = 0110 \oplus 1001 = 1111 = 15, so s=143s = 143, the column of position 15. The decoder flips bit 15 and raises corrected. None of 3, 5, 9 and 15 is a check position, since those are 0, 1, 2, 4, 8, 16, 32 and 64, so the word leaves with four data bits wrong, and {3,5,9,15}\{3, 5, 9, 15\} is the weight-4 codeword the first corollary pairs it with. The outcome is miscorrected.

The columns are 128, 131, 133 and 134. Bit 7 appears four times and cancels, and the low bits give 0⊕3⊕5⊕6=00 \oplus 3 \oplus 5 \oplus 6 = 0, since 3⊕5=63 \oplus 5 = 6. The syndrome is zero, so the decoder passes the word unchanged with no flag. Position 0 is a check bit, but 3, 5 and 6 are data bits, so three data bits are wrong. The pattern is one of the 11,326 weight-4 codewords, and the outcome is undetected.

Here p^=0.53\hat p = 0.53, N=100N = 100 and z2=3.8416z^2 = 3.8416. The center is (0.53+3.8416/200)/(1+3.8416/100)=0.549208/1.038416=0.52889(0.53 + 3.8416/200)/(1 + 3.8416/100) = 0.549208/1.038416 = 0.52889. The half-width is 1.960.53×0.47/100+3.8416/40,000/1.038416=1.960.00258704/1.038416=0.0960031.96\sqrt{0.53 \times 0.47/100 + 3.8416/40{,}000}/1.038416 = 1.96\sqrt{0.00258704}/1.038416 = 0.096003. The Wilson interval runs from 43.289% to 62.489%, centered below p^\hat p because it leans toward 1/21/2. The normal rule gives 0.53±1.960.002491=0.53±0.0980.53 \pm 1.96\sqrt{0.002491} = 0.53 \pm 0.098, from 43.2% to 62.8%. Both contain the exact 56.284%. At 53 hits the two differ by less than a point at each end, and both are about 19 points wide, which is what 100 draws can say.

A daily scrub means t=24t = 24 hours, so μ=2.4×10−5\mu = 2.4 \times 10^{-5} and Y/t=365Y/t = 365. Then μ3/6=1.3824×10−14/6=2.304×10−15\mu^3/6 = 1.3824 \times 10^{-14}/6 = 2.304 \times 10^{-15} and e−μ=0.999976e^{-\mu} = 0.999976. The product 4,096×365×2.304×10−15×0.999976=3.4445×10−94{,}096 \times 365 \times 2.304 \times 10^{-15} \times 0.999976 = 3.4445 \times 10^{-9} is the expected number of word-intervals a year with exactly three strikes. Multiplying by D=0.9587D = 0.9587 and pM(3)=0.56284p_{\mathrm{M}}(3) = 0.56284 gives 1.86×10−91.86 \times 10^{-9}, about one silent corruption in 540 million years.

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]cocotb Project “Installation.” cocotb 2.1 documentation. Read 2026-11-14. https://docs.cocotb.org/en/stable/install.html
  3. [3]Verilator Project “Installation.” Verilator 5.054 documentation. Read 2026-11-14. https://verilator.org/guide/latest/install.html
  4. [4]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
  5. [5]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
  6. [6]MacWilliams, Jessie (1963). “A Theorem on the Distribution of Weights in a Systematic Code.” Bell System Technical Journal, 42(1), pp. 79–94. doi:10.1002/j.1538-7305.1963.tb04003.x
  7. [7]Matsumoto, Makoto and Nishimura, Takuji (1998). “Mersenne Twister: A 623-Dimensionally Equidistributed Uniform Pseudo-Random Number Generator.” ACM Transactions on Modeling and Computer Simulation, 8(1), pp. 3–30. doi:10.1145/272991.272995
  8. [8]Python Software Foundation “random: Generate pseudo-random numbers.” The Python 3 documentation. Read 2026-11-14. https://docs.python.org/3/library/random.html
  9. [9]Brown, Lawrence D. and Cai, T. Tony and DasGupta, Anirban (2001). “Interval Estimation for a Binomial Proportion.” Statistical Science, 16(2), pp. 101–133. doi:10.1214/ss/1009213286
  10. [10]Wilson, Edwin B. (1927). “Probable Inference, the Law of Succession, and Statistical Inference.” Journal of the American Statistical Association, 22(158), pp. 209–212. doi:10.1080/01621459.1927.10502953
  11. [11]Agresti, Alan and Coull, Brent A. (1998). “Approximate is Better than "Exact" for Interval Estimation of Binomial Proportions.” The American Statistician, 52(2), pp. 119–126. doi:10.1080/00031305.1998.10480550
  12. [12]Mitzenmacher, Michael and Upfal, Eli (2005). “Probability and Computing: Randomized Algorithms and Probabilistic Analysis.” Cambridge University Press. doi:10.1017/CBO9780511813603
  13. [13]Saleh, A. M. and Serrano, J. J. and Patel, J. H. (1990). “Reliability of Scrubbing Recovery-Techniques for Memory Systems.” IEEE Transactions on Reliability, 39(1), pp. 114–122. doi:10.1109/24.52622

— Anirban

Hardware–software at the seam where compilers meet microcode.

FeedbackBook modePaper
error-correction-codinglinear-block-codes