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 for the 72-bit codeword stored for a data word , and for the error pattern, a 72-bit word with a 1 at every flipped position. The decoder reads , where is bitwise addition modulo 2, and computes the syndrome with the check matrix . Every codeword has syndrome zero, so , the XOR of the columns 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 flips bit 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.
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.
| 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 the column , the binary number 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.
Proof. Both versions of are XORs of fixed syndrome bits, so . Every Hsiao column has odd weight, and every extended Hamming column has a 1 in row 7, so at every position . The syndrome is the XOR of columns, so is the XOR of ones, which is 1 exactly when is odd.
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 at position 0 and at position for from 0 to 6. An XOR of some of them has bit set for each it uses, so a zero XOR uses none of those, and what remains is alone or nothing, which forces the empty set.
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, , so and the decoder either flips a bit or raises uncorrectable. If matches no column, the word is flagged. If , position is not one of the three flipped positions , and , because would force , and the columns are distinct. The decoder therefore leaves , where has a single 1 at position . The word has weight 4 and syndrome , so it is a nonzero codeword, and by the second lemma it changes at least one data bit. The word is miscorrected.
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 carries the same argument to extended Hamming, whose columns do not all have odd weight.
Proof. The proof above sends each miscorrected triple to the codeword . A weight-4 codeword is reached from exactly four triples, for each of its four positions , since each such triple has syndrome and is pushed back onto . Distinct columns make unique for each triple, so the map is four to one onto the weight-4 codewords.
Proof. By Equation 1, . Every column has , so equals no column and the decoder never flips a bit. If , the pattern is a codeword, and by the second lemma it changes data that pass with no flag, so the word is undetected. Otherwise is nonzero and matches no column, and the word is flagged.
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 , since with and .
Both shares the lab measures are therefore set by one number per code, the count 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.
| 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 and gives Table 1.
Table 1. Every triple and every quadruple of the three codes, classified
| Code | Triples miscorrected | Triples flagged | Share | Quadruples undetected | Quadruples flagged | Share |
|---|---|---|---|---|---|---|
| Hsiao, balanced | 33,568 | 26,072 | 56.284% | 8,392 | 1,020,398 | 0.816% |
| Hsiao, dictionary | 34,032 | 25,608 | 57.062% | 8,508 | 1,020,282 | 0.827% |
| extended Hamming | 45,304 | 14,336 | 75.962% | 11,326 | 1,017,464 | 1.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 .
Two more routes reach the same . The script's syndrome_counts() builds a table , the number of patterns of weight with syndrome , one position at a time. A pattern leaves the new position out or uses it and has its syndrome moved by , so adding turns into . For every the second lemma then gives and , because a pattern with syndrome is pushed onto the nonzero codeword and a pattern with syndrome 0 is itself one. The section The MacWilliams Identity of Weight Distributions and Undetected Errors gives a third time, from the weights of the 256 words the rows of span [6]. All three routes agree for all three codes.
Listing is cheap here. One code has 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 is 13.6 times the weight-4 count and is 11,634 times it. Longer codes defeat the recursion, since check bits need syndrome bins, 4,294,967,296 for . 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 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 and no column matches. Figure 2 shows how the campaign surrounds it.
Each case comes from draw() in python/ch31_lab_measuring_miscorrection.py.
| 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 distinct positions equally likely, and each set is reached by the same orderings, so every set is equally likely. The one departure is that random() returns one of values, which split into 72 bins unevenly by less than one part in .
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.
| 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 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 , 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 .
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
| Code | Triples miscorrected | Triples flagged | Rate and interval | Quadruples undetected | Quadruples flagged | Rate and interval |
|---|---|---|---|---|---|---|
| Hsiao, balanced | 56,222 | 43,778 | 56.222%, 55.914 to 56.529 | 864 | 99,136 | 0.864%, 0.808 to 0.923 |
| Hsiao, dictionary | 56,984 | 43,016 | 56.984%, 56.677 to 57.291 | 829 | 99,171 | 0.829%, 0.775 to 0.887 |
| extended Hamming | 75,975 | 24,025 | 75.975%, 75.709 to 76.239 | 1,122 | 98,878 | 1.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 for the true share and for the number of hits in independent draws. Then follows the binomial distribution, the estimate is , and, because each draw contributes a variance and the variances of independent draws add, the standard error of is given by Equation 3.
For the balanced code at 100,000 draws this is 0.157 percentage points. The usual normal rule puts a 95% interval at , because a normal variable lies within 1.96 standard deviations of its mean 95% of the time. That rule plugs in for the unknown and fails where it is needed most. Near a share of 0.8% and at small its intervals cover the truth far less often than 95% of the time, and they can reach below zero [9].
Wilson's idea [10] is to keep the unknown inside the square root and ask which values of the observed is consistent with. Squaring the condition gives , a quadratic inequality in , and its two roots are the endpoints. The interval never leaves , its center is pulled from toward , and its coverage stays close to 95% even for small counts [11]. The script's wilson() computes it.
| 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 at level takes the number of draws in Equation 5.
For one percentage point at the balanced share, , and , the worst case, needs 9,604. The rule needs a guess at and promises nothing exact. Two bounds promise something for every and every .
Proof. For a random variable and a number , the inequality holds at every outcome, since the left side is when and 0 otherwise. Taking expectations gives Markov's inequality, . Apply it with and . The event is the event , and is the variance of . A single draw has , so its variance is . The variances of independent draws add to , and dividing by divides the variance by , which leaves and the first inequality. The second holds because .
Setting the right side to and solving gives , which is 50,000 draws for one point with at least 95% certainty, whatever the share. A sharper bound decays exponentially in .
Hoeffding proved it for any bounded independent draws. The proof applies Markov's inequality to an exponential of rather than to its square, the method of Chernoff bounds [12], and is not repeated here. Setting the bound to gives , 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 , 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.
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.
08.Measured Against Exact
Figure 5 puts the six measured rates and their intervals beside the exact shares of Table 1.
All six intervals contain their exact shares. That was likely, not certain, since six independent 95% intervals would all hold with probability , 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 of the extended Hamming code holds , so for three positions , and below 64 the XOR of their columns has bit 7 set, bit 6 clear and low six bits , which is the column of position , itself below 64. Every one of the 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 .
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 . 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 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 be 1 if only the dictionary matrix miscorrects it, if only the balanced one does, and 0 otherwise. With and the shares miscorrected by the balanced and the dictionary matrix alone, has mean and variance , 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 , and for from 0 to 69, and the question becomes how many of the 70 are miscorrected.
In the natural layout, cell holds bit . 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.
A stride layout puts bit in cell , for a stride 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
| Layout | Hsiao, balanced | Hsiao, dictionary | extended Hamming |
|---|---|---|---|
| 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 (stride 11) |
| random order, expected | 39.40 | 39.94 | 53.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 hold low positions only.
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.
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 words, each struck at a rate upsets per word-hour and scrubbed every hours. A scrub reads every word and writes back its corrected value [13], so a word gathers errors only between scrubs. With , the number of strikes on one word in one interval is Poisson, and exactly three occur with probability . 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 . A year holds intervals, with hours, so the silent-corruption rate from triples is given by Equation 8.
Table 4. Silent corruptions a year from triples, 4,096 words at an illustrative upset rate
| Code | Scrub every day | Scrub every 30 days | Scrub every year |
|---|---|---|---|
| Hsiao, balanced | |||
| extended Hamming |
Source: ch31_lab_measuring_miscorrection.py, at upsets per word-hour.
The model ignores four or more strikes between scrubs, rarer again by a factor of about , 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, in favor of Hsiao, whatever the scrub interval. The scrub moves it far more, because 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 . 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 . 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 . Rings and Fields builds those fields, opening the part on finite fields and their arithmetic.
12.Worked Examples
Position holds the column , so the columns are 131, 133 and 137. Their XOR has bit 7 set, since it appears three times, and low bits . In binary and , so , 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 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 , since . 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 , and . The center is . The half-width is . The Wilson interval runs from 43.289% to 62.489%, centered below because it leans toward . The normal rule gives , 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 hours, so and . Then and . The product is the expected number of word-intervals a year with exactly three strikes. Multiplying by and gives , about one silent corruption in 540 million years.
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]cocotb Project “Installation.” cocotb 2.1 documentation. Read 2026-11-14. https://docs.cocotb.org/en/stable/install.html
- [3]Verilator Project “Installation.” Verilator 5.054 documentation. Read 2026-11-14. https://verilator.org/guide/latest/install.html
- [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]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]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]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]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]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]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]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]Mitzenmacher, Michael and Upfal, Eli (2005). “Probability and Computing: Randomized Algorithms and Probabilistic Analysis.” Cambridge University Press. doi:10.1017/CBO9780511813603
- [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.