Paper
Part IILinear Block Codes

Case Study: ECC in Processor Caches

November 16, 202643 min readbeginner

A 32 KiB cache array spends 12.5 percent on parity or on SEC-DED. The chapter weighs the two, prices byte stores and scrubbing, spreads bursts by interleaving, and checks OpenTitan's open prim_secded codes.

A processor keeps the data it is working on in caches, small and fast memory arrays built on the same die as the logic that reads them. A 32 KiB data cache holds 262,144 data bits, each one a tiny stored charge that a stray particle can disturb. When one of those bits flips, the cache faces a choice that the theory of parity and SEC-DED prepared but never had to make on real hardware. It can store one parity bit per byte and notice the flip, or it can store a SEC-DED code and repair it, and the two choices cost exactly the same number of extra bits.

Like Case Study: Codes in the Wild, this chapter proves little that is new and checks a great deal. It carries the codes of SECDED and Hsiao Codes into caches and register files in the generic terms textbooks use [1], never as a claim about any commercial processor. The one hardware it names is open source, the prim_secded encoders and decoders of the OpenTitan project, whose matrices the chapter checks from the published masks.

Every number in the chapter is recomputed by ch29_case_study_ecc_in_processor_caches.py in the python/ folder of the companion repository ecc-book-lab, and the charts are drawn by ch29_charts.py in the same folder. The GNU Octave twin ch29_case_study_ecc_in_processor_caches.m prints the same lines, as The Octave Route explains.

01.A 32 KiB Array, Two Ways

Take a data array of 32 KiB, which is 32,768 bytes or 262,144 bits, organized as 4,096 words of 64 bits each. Byte parity stores one extra bit beside each byte, which is 32,768 extra bits. A (72,64)(72, 64) SEC-DED code stores eight check bits beside each word, which is 4,096×8=32,7684{,}096 \times 8 = 32{,}768 extra bits, the same number. Figure 1 draws one word stored both ways. The overhead of either scheme is

32,768262,144=18=12.5%,\frac{32{,}768}{262{,}144} = \frac{1}{8} = 12.5\% ,
(1)

and the array stores 294,912 bits in all.

The same 64 data bits protected two ways, with 72 bits stored either way. Above, byte parity gives each of the eight bytes its own parity bit p, and two flips inside byte 2 leave that byte's parity unchanged, so the error is missed. Below, a (72,64) SEC-DED code computes eight check bits over the whole word, and the same two flips give a nonzero syndrome of even weight, which the decoder flags as a double error. Byte parity: one parity bit p for each byte byte 0 byte 1 byte 2 byte 3 byte 4 byte 5 byte 6 byte 7 p p p p p p p p Two flips in byte 2 leave its parity unchanged, so the error is missed. 64 data bits and 8 parity bits: 72 bits stored, 12.5% extra. Detects one flip in a byte, corrects none. (72,64) SEC-DED: eight check bits cover the whole word data bits 0 to 63 check bits c0 to c7 The same two flips give a nonzero syndrome of even weight: flagged as a double error. 64 data bits and 8 check bits: 72 bits stored, 12.5% extra. Corrects one flip in the word, detects two.
Figure 1. The same 64 data bits stored two ways at the same cost of eight extra bits. Byte parity gives each byte its own parity bit and misses two flips inside one byte, while the (72,64) SEC-DED code computes eight check bits over the whole word and flags the same two flips as a double error.

Proof. A healthy group of nine bits has XOR 0. Flipping one bit changes the XOR of the group, because x⊕1x \oplus 1 differs from xx for either value of xx. After tt flips the XOR has changed tt times, so it is 1 exactly when tt is odd. ■\blacksquare

The lemma says what parity buys. It detects every single flip but corrects nothing, because the parity bit says that a byte is wrong without saying which of its nine bits changed, and two flips in one byte pass unseen. A 72-bit stored word has (722)=2,556\binom{72}{2} = 2{,}556 two-bit errors. Under byte parity its bits form eight groups of nine, so 8×(92)=8×36=2888 \times \binom{9}{2} = 8 \times 36 = 288 of those errors fall inside one group. Byte parity misses those 288, or 11.27 percent, and reports the rest as damage it cannot repair.

A SEC-DED code spends the same eight bits on the whole word. Its minimum distance is four, so by Distance, Detection and Correction its decoder corrects every single flip among the 72 bits and flags every pair. The script confirms the second half by running all 2,556 two-bit errors through the (72,64)(72, 64) check matrix of OpenTitan's SEC-DED Generator, and every one of them is flagged as a double error, with none passing silently.

02.Clean Lines and Dirty Lines

Suppose a read finds an error in two different caches. In the first, the line holds instructions, which the processor reads but never writes. In the second, it holds data that a store changed a moment ago and that has not yet reached the next level. The same detected error has very different consequences in the two.

Figure 2 follows both cases. A detected error in a clean line costs only time. The cache invalidates the line and fetches it again, as if the access had missed, and the program never sees the error. For an array whose every line is clean, such as an instruction cache or a write-through data cache, detection is enough and parity is a sound choice. A dirty line is different, because the correct value exists nowhere else. Parity can report the loss but cannot repair it, so the error becomes a detected unrecoverable error, the DUE of Error-Control Strategies and Performance [2]. SEC-DED repairs a single flip in place, and the data survives.

What happens after a cache read finds a bad word. If the line is clean, a correct copy exists at the next level, so the line is invalidated and fetched again and nothing is lost, which parity alone can support. If the line is dirty it is the only copy. With parity only, the error is detected but the data cannot be rebuilt, so an uncorrectable error is reported. With SEC-DED, a single flip is corrected in place and nothing is lost. Instruction caches and write-through caches hold only clean lines. error found on a read dirty? no: clean yes: dirty Clean line invalidate it and refetch from the next level parity is enough, no data lost Dirty line, parity only this line is the only copy, so it cannot be rebuilt uncorrectable error reported, data lost Dirty line, SEC-DED one flip is corrected, two are detected single flip corrected, no data lost Instruction caches and write-through caches hold only clean lines, so they always take the top path.
Figure 2. Recovery after a detected error. A clean line is invalidated and fetched again from the next level, so parity is enough. A dirty line is the only copy, so parity can only report the loss, while SEC-DED corrects a single flip in place.

Textbook treatments of soft errors draw the same line, with parity where a clean copy always exists and an error-correcting code where it may not [3]. A write-back cache holds clean and dirty lines side by side, so it is protected for its worst line.

03.Partial Writes

Stores do not always write whole words. Take the word 0x0123456789ABCDEF, stored under the OpenTitan (72,64)(72, 64) code with check bits 0110101001101010, written c0c_0 first. A store now writes the byte 0x5A into byte 2, bits 16 to 23, which held 0xAB. The new word is 0x01234567895ACDEF, and encoding it from scratch gives check bits 0001111100011111. Five of the eight check bits changed, those in rows 1, 2, 3, 5 and 7, although only one byte of data did.

Under byte parity the same store is simple. The parity bit of byte 2 depends on byte 2 alone, so the cache writes 0x5A, which holds four ones, together with its even-parity bit 0, and touches nothing else. Under SEC-DED every check bit can depend on every byte, so the cache follows the sequence of Figure 3.

A partial write to a word protected by a (72,64) SEC-DED code. The whole 72-bit word is read and decoded, which corrects a single flip. The decoder's double-error output enters an AND gate through an inverting input, so the array's write enable is the store request gated by the absence of a double error, and a double error stops the write. A 64-bit multiplexer then takes each byte either from the corrected word or from the store, chosen by an 8-bit byte enable, one select bit per byte. The merged 64 bits are encoded again and all 72 bits are written back. Byte parity needs no read, since the new byte is written with its own new parity bit. data array 72-bit words 72 read and correct SEC-DED decoder double error store request write 64 store data 64 merge the new bytes 0 1 8 byte enable 64 re-encode SEC-DED encoder 72 write back all 72 bits With byte parity no read is needed, since the new byte is written with its own new parity bit.
Figure 3. A one-byte store into a word protected by a (72,64) SEC-DED code. The whole word is read and corrected, the byte enable selects each byte from the store or from the corrected word, the merged word is encoded again, and all 72 bits are written back. Byte parity needs no read.

The new check bits need not be computed from scratch. A systematic code computes its check bits as c=Pdc = P d over GF(2)\mathrm{GF}(2), where dd is the 64-bit data column and PP is the data part of the check matrix, an 8×648 \times 64 matrix with columns p0,…,p63p_0, \dots, p_{63}.

Proof. Matrix multiplication over GF(2)\mathrm{GF}(2) distributes over ⊕\oplus, so P(d⊕Δ)=Pd⊕PΔ=c⊕PΔP(d \oplus \Delta) = Pd \oplus P\Delta = c \oplus P\Delta. The product PΔP\Delta is the sum Δ0p0⊕Δ1p1⊕⋯⊕Δ63p63\Delta_0 p_0 \oplus \Delta_1 p_1 \oplus \cdots \oplus \Delta_{63} p_{63}, in which every term with Δj=0\Delta_j = 0 is zero, leaving the XOR of the columns where Δ\Delta has a one. With a single one at position jj the sum is pjp_j alone, and XORing pjp_j into cc flips exactly the rows where pjp_j holds a one. ■\blacksquare

In the example the change in byte 2 is 0xAB XOR 0x5A, which is 0xF1, so data bits 16, 20, 21, 22 and 23 change. Their columns in the OpenTitan matrix, written row 0 first, are

p16=10001010,p20=10000011,p21=01110000,p22=01101000,p23=01100100,p_{16} = 10001010, \quad p_{20} = 10000011, \quad p_{21} = 01110000, \quad p_{22} = 01101000, \quad p_{23} = 01100100,

and their XOR is 0111010101110101. Then 01101010⊕01110101=0001111101101010 \oplus 01110101 = 00011111, the same check bits that encoding the new word produced.

The lemma shrinks the encoding but does not remove the read. Computing Δ\Delta needs the old byte and updating cc needs the old check bits, and both must be checked first, which needs the syndrome of all 72 bits. A delta update that trusts an unchecked old byte folds any flip in it into the new check bits, and the first worked example below shows a later read then correcting a bit that was never wrong.

So a partial store into a SEC-DED array costs a read before the write. A buffer can gather stores to one word until all eight bytes are present, or the code can cover a narrower unit that matches the smallest store, at the higher overhead SECDED and Hsiao Codes tabulates for shorter words.

04.Scrubbing

A word that the program never reads can sit in an array for hours. SEC-DED will repair one flipped bit on the next read, but only if a second flip has not landed in the same word first. The danger grows with time, and a scrubber bounds the time.

How long may TT be? Fix one 72-bit word and let upsets strike it at a steady rate of λ\lambda per hour, so that μ=λT\mu = \lambda T upsets are expected in one interval. Slice the interval into nn equal pieces, each so short that it holds one upset with probability μ/n\mu / n and otherwise none, independently of the others. The number of upsets NN is then a binomial count, as in Probability for Coding, and

P(N=0)=(1−μn)n,P(N=1)=n⋅μn(1−μn)n−1=μ(1−μn)n−1.P(N = 0) = \left(1 - \frac{\mu}{n}\right)^{n}, \qquad P(N = 1) = n \cdot \frac{\mu}{n}\left(1 - \frac{\mu}{n}\right)^{n-1} = \mu \left(1 - \frac{\mu}{n}\right)^{n-1} .

As nn grows, (1−μ/n)n(1 - \mu/n)^n tends to e−μe^{-\mu}, a standard limit of calculus, and (1−μ/n)n−1(1 - \mu/n)^{n-1} tends to the same value, since the two differ by a factor 1−μ/n1 - \mu/n that tends to 1. So P(N=0)P(N = 0) tends to e−μe^{-\mu} and P(N=1)P(N = 1) to μe−μ\mu e^{-\mu}, and the same limit for a general count gives the model below.

Proof. The events N=0N = 0, N=1N = 1 and N≥2N \ge 2 cannot happen together, and between them they cover every outcome, so their probabilities add to 1. Hence P(N≥2)=1−P(N=0)−P(N=1)=1−e−μ−μe−μP(N \ge 2) = 1 - P(N = 0) - P(N = 1) = 1 - e^{-\mu} - \mu e^{-\mu}, which is the stated form with μ=λT\mu = \lambda T. ■\blacksquare

Proof. Write f(μ)=1−e−μ(1+μ)f(\mu) = 1 - e^{-\mu}(1 + \mu). Then f(0)=0f(0) = 0, and the product rule gives f′(μ)=e−μ(1+μ)−e−μ=μe−μf'(\mu) = e^{-\mu}(1 + \mu) - e^{-\mu} = \mu e^{-\mu}, so by the fundamental theorem of calculus f(μ)=∫0μxe−x dxf(\mu) = \int_0^{\mu} x e^{-x} \, dx. For x≥0x \ge 0 the factor e−xe^{-x} is at most 1, so f(μ)≤∫0μx dx=μ2/2f(\mu) \le \int_0^{\mu} x \, dx = \mu^2/2. For the lower bound, let g(x)=e−x−1+xg(x) = e^{-x} - 1 + x. Then g(0)=0g(0) = 0 and g′(x)=1−e−x≥0g'(x) = 1 - e^{-x} \ge 0 for x≥0x \ge 0, so gg never decreases there and e−x≥1−xe^{-x} \ge 1 - x. Hence f(μ)≥∫0μx(1−x) dx=μ2/2−μ3/3f(\mu) \ge \int_0^{\mu} x(1 - x) \, dx = \mu^2/2 - \mu^3/3. Subtracting gives 0≤μ2/2−f(μ)≤μ3/30 \le \mu^2/2 - f(\mu) \le \mu^3/3, and dividing by μ2/2\mu^2/2 gives the fraction 2μ/32\mu/3. ■\blacksquare

For a daily scrub at the assumed rate, μ=10−6×24=2.4×10−5\mu = 10^{-6} \times 24 = 2.4 \times 10^{-5}, so one word collects two upsets in a day with probability 2.88×10−102.88 \times 10^{-10}, and the square law is accurate to a fraction 1.6×10−51.6 \times 10^{-5} of itself. The real question, though, is the whole array over its working life.

Proof. Give each word an indicator that is 1 when the word collects two or more upsets in one interval and 0 otherwise. Each indicator has expectation P(N≥2)P(N \ge 2) at μ=λT\mu = \lambda T, so by linearity of expectation, from Probability for Coding, the expected loss in one interval is WP(N≥2)W P(N \ge 2). A time YY that is a whole number of intervals holds Y/TY/T of them, and otherwise Y/TY/T is the long-run count of intervals per time YY, so the loss is W(Y/T)P(N≥2)W (Y/T) P(N \ge 2). Multiplying the bounds of the square-law theorem by WY/TWY/T, and using (λT)2/2×Y/T=λ2TY/2(\lambda T)^2 / 2 \times Y/T = \lambda^2 T Y / 2, gives the two bounds, which differ only by the factor 1−2λT/31 - 2\lambda T/3 that tends to 1 as λT\lambda T shrinks. ■\blacksquare

The model ignores repairs by ordinary reads and counts two strikes on the same bit as a loss although they cancel, so it slightly overstates the loss. A word that collects exactly two upsets is a DUE, because SEC-DED flags two flips, while one with three or more can be miscorrected silently, the hazard Lab: Measuring Miscorrection measures, though such words are only about 8.0×10−68.0 \times 10^{-6} of the loss for a daily scrub, 2.4×10−42.4 \times 10^{-4} for a 30-day scrub and 2.9×10−32.9 \times 10^{-3} for a year without scrubbing.

Table 1. A 4,096-word array at an illustrative 1,000 FIT per word over one year of 8,760 hours, for four scrub intervals

Scrub interval TTλT\lambda TP(N≥2)P(N \ge 2)Words lost a year
1 hour1.0×10−61.0 \times 10^{-6}5.0000×10−135.0000 \times 10^{-13}1.7940×10−51.7940 \times 10^{-5}
1 day, 24 hours2.4×10−52.4 \times 10^{-5}2.8800×10−102.8800 \times 10^{-10}4.3056×10−44.3056 \times 10^{-4}
1 week, 168 hours1.68×10−41.68 \times 10^{-4}1.4110×10−81.4110 \times 10^{-8}3.0137×10−33.0137 \times 10^{-3}
30 days, 720 hours7.2×10−47.2 \times 10^{-4}2.5908×10−72.5908 \times 10^{-7}1.2911×10−21.2911 \times 10^{-2}

Source: reproduced by ch29_case_study_ecc_in_processor_caches.py.

Table 1 and Figure 4 show the corollary at work, with each longer interval multiplying the loss by about the same factor as the interval. With no scrubbing at all for a year, μ=8.76×10−3\mu = 8.76 \times 10^{-3}, and an expected 0.15624 of the array's 4,096 words, a fraction 3.8145×10−53.8145 \times 10^{-5} of them, hold two or more upsets by the year's end, 363 times the daily-scrub figure. The ratio is 363 rather than 365 because at the larger μ\mu the factor 1−2μ/31 - 2\mu/3 has fallen to about 0.994.

Expected words a year that collect two or more upsets between scrubs, against the scrub interval T from 1 to 1,000 hours, on log scales, for upset rates of 1,000, 100 and 10 FIT per 72-bit word in a 4,096-word array. Each curve is a straight line of slope one, so doubling the interval doubles the loss, and each tenfold cut in the rate cuts the loss a hundredfold. Dots mark the hourly, daily, weekly and monthly intervals on the 1,000 FIT curve. 10-9 10-8 10-7 10-6 10-5 10-4 10-3 10-2 10-1 1 10 100 1,000 day week month 1,000 FIT 100 FIT 10 FIT per word Scrub interval T, hours, log scale Words a year with two or more upsets 4,096 words of 72 bits, one year of 8,760 hours, Poisson upsets
Figure 4. Expected words a year that collect two or more upsets between scrubs, against the scrub interval on logarithmic axes, for an illustrative 4,096-word array at 1,000, 100 and 10 FIT per word. Each line has slope one, and each tenfold cut in the rate lowers the loss a hundredfold. Data: computed by ch29_charts.py in the companion repository.

The loss grows as λ2\lambda^2 but only linearly in TT, so a harsher environment needs a much shorter interval, while a scrubber need not be fast, only regular. Each pass competes with the program for the array, which sets a lower limit on TT. Saleh, Serrano and Patel analyzed scrubbing for memories under single-error-correcting codes in depth [5].

05.Bursts and Interleaving

The Poisson model treats upsets as independent single flips, but one particle strike can disturb several neighboring cells at once [4]. Beyond SECDED answered this in its section Interleaving Instead of Check Bits, and in a cache the arrangement works as follows. Take one physical row of 288 cells holding four 72-bit words. In the interleaved layout, cell cc holds bit ⌊c/4⌋\lfloor c/4 \rfloor of word c mod 4c \bmod 4, so cell 9 holds bit 2 of word 1. In the side-by-side layout, word ii fills cells 72i72i to 72i+7172i + 71. Figure 5 shows the first 16 cells both ways.

The first 16 cells of a physical row that holds four 72-bit words, laid out two ways. Interleaved, cell c holds bit c div 4 of word c mod 4, so a burst over cells 4 to 7 flips bit 1 of each of the four words once, and SEC-DED corrects each word. Side by side, word 0 fills the first 72 cells, so the same burst flips four bits of word 0, which is past what SEC-DED corrects. Interleaved: cell c holds bit c div 4 of word c mod 4 0123456789101112131415 w0w1w2w3w0w1w2w3w0w1w2w3w0w1w2w3 b0b0b0b0b1b1b1b1b2b2b2b2b3b3b3b3 A burst over cells 4 to 7 flips bit 1 of each of the four words. Each word sees one flip, which SEC-DED corrects. Side by side: word 0 fills the first 72 cells 0123456789101112131415 w0w0w0w0w0w0w0w0w0w0w0w0w0w0w0w0 b0b1b2b3b4b5b6b7b8b9b10b11b12b13b14b15 The same burst flips bits 4 to 7 of word 0, four flips in one word, which is past what SEC-DED corrects. A full row is 288 cells holding four 72-bit words. Only its first 16 cells are drawn.
Figure 5. The first 16 of 288 cells in a row holding four 72-bit words. Interleaved, a burst over cells 4 to 7 flips bit 1 of each word once, and each word is corrected. Side by side, the same burst flips bits 4 to 7 of word 0, which SEC-DED cannot correct.

Proof. Two of the integers differ by an amount between 1 and b−1≤3b - 1 \le 3. Two integers leave the same remainder on division by 4 exactly when their difference is a multiple of 4, and no number from 1 to 3 is a multiple of 4. ■\blacksquare

In the interleaved row a cell's word is its remainder on division by 4, so by the lemma a burst of one to four adjacent cells touches each word at most once, and SEC-DED corrects every word. The script checks every position, 288+287+286+285=1,146288 + 287 + 286 + 285 = 1{,}146 bursts of one to four cells, and finds no word with more than one flip. Longer bursts lose the guarantee gradually. Any eight consecutive integers hold each remainder exactly twice, so a burst of five to eight cells puts at most two flips in a word, which SEC-DED still detects.

Side by side, a burst of three or four cells spans at most two words, so one takes at least two flips, and a two-cell burst is corrected only when it straddles one of the three word boundaries. In all, 855 bursts of two to four cells leave some word uncorrectable, against none interleaved. Interleaving adds no check bits, and in an array that already stores several words in each row and selects one with a column multiplexer, it changes only which cells feed which word.

06.The Decoder in the Read Path

A SEC-DED decoder works on every read. In the OpenTitan (72,64)(72, 64) code each syndrome bit is the XOR of 27 inputs, which a tree of two-input gates computes in five levels, since 24=16<27≤32=252^4 = 16 < 27 \le 32 = 2^5, and the corrector then flips the bit the syndrome names. A read that waits for the corrector pays those levels on every access, even the vast majority with no error.

A generic remedy, shown in Figure 6, is to use the data before it is checked. The raw word goes at once to the instructions that need it while the syndrome is computed in parallel, and a nonzero syndrome cancels the dependent work and replays it with the corrected word. The decoder's delay leaves the common case, at the price of a replay path that verification must reach.

A read path that uses data before it is checked. The raw 72-bit word goes straight to the dependent instructions, early. In parallel, XOR trees form the 8-bit syndrome, and an OR of its bits says whether it is nonzero. If it is, the dependent work is cancelled and replayed, and the corrector, which flips the bad bit named by the syndrome, supplies the corrected word later. A read with a zero syndrome pays nothing for the check. data array read port 72 early: raw data, used at once syndrome XOR trees 8 OR of 8 s nonzero: cancel and replay corrector flips the bad bit late: corrected word, on replay dependent instructions Most reads find s = 0, so the check adds nothing to their latency. Only a read with an error pays.
Figure 6. A read path that uses data before it is checked. The raw word goes ahead to the dependent instructions while XOR trees form the syndrome. A nonzero syndrome cancels and replays the dependent work with the corrected word, and a zero syndrome, the common case, costs nothing.

Speculation needs one firm rule. The check must finish before any result computed from unchecked data becomes permanent, such as a store reaching memory or an instruction retiring. An array of clean lines can instead treat any nonzero syndrome as a miss and fetch the line again, so the read path needs no corrector. The Ibex instruction cache of Register Files and the Ibex Core works this way.

07.OpenTitan's SEC-DED Generator

OpenTitan is an open-source silicon root-of-trust project, published on GitHub as lowRISC/opentitan. Its prim_secded primitives are SystemVerilog encoders and decoders that a Python program, secded_gen.py, generates from a configuration file, secded_cfg.hjson [6] [7]. Every file was read at commit 4ced702ca207ad420fbae5226ac8685a17ebef7b, and Table 2 links each one there.

Table 2. The OpenTitan files read for this chapter, each linked at commit 4ced702ca207

FileWhat it holds
util/design/secded_gen.pyThe generator
util/design/data/secded_cfg.hjsonThe list of codes to generate
prim_secded_39_32_enc.sv, prim_secded_39_32_dec.svThe Hsiao (39,32)(39, 32) encoder and decoder
prim_secded_72_64_enc.sv, prim_secded_72_64_dec.svThe Hsiao (72,64)(72, 64) encoder and decoder
prim_secded_inv_39_32_enc.sv, prim_secded_inv_39_32_dec.svThe inverted (39,32)(39, 32) encoder and decoder
prim_secded_inv_72_64_enc.sv, prim_secded_inv_72_64_dec.svThe inverted (72,64)(72, 64) encoder and decoder
security.rst, icache.rstThe Ibex documentation on register-file and cache ECC
ibex_core.sv, ibex_icache.svWhere Ibex instantiates the codes

Source: the lowRISC/opentitan repository at commit 4ced702ca207ad420fbae5226ac8685a17ebef7b.

Each generated encoder computes a check bit as the XOR of the data bits that a mask selects. Line 15 of prim_secded_inv_39_32_enc.sv at that commit reads data_o[33] = (^(data_i & 32'hDEBA8050)) ^ 1'b1;. The & keeps the data bits where the mask 0xDEBA8050 has a one, the leading ^ folds them into one parity bit, and the trailing ^ 1'b1 inverts the result, for a reason Inverted Codes gives. Line 15 of the plain encoder prim_secded_39_32_enc.sv differs only in lacking that inversion. Each mask is one row of the data part of the check matrix, and the script transcribes the masks of both sizes as integers.

Table 3 lists the 22 codes the configuration asks for at that commit, six Hsiao codes, five extended Hamming codes of the kind built in Hamming Codes and Perfect Codes, and an inverted version of each. Every one uses the fewest check bits that SEC-DED allows for its data width. The (64,57)(64, 57) code leaves no freedom at all, since seven check bits admit exactly 64 distinct odd-weight columns and the code has 64 positions.

Table 3. Every code that secded_cfg.hjson asks the generator for at commit 4ced702ca207

KindCodes (n,k)(n, k)
Hsiao(22,16)(22, 16), (28,22)(28, 22), (39,32)(39, 32), (64,57)(64, 57), (72,64)(72, 64), (137,128)(137, 128)
Extended Hamming(22,16)(22, 16), (39,32)(39, 32), (72,64)(72, 64), (76,68)(76, 68), (137,128)(137, 128)
Inverted Hsiao(22,16)(22, 16), (28,22)(28, 22), (39,32)(39, 32), (64,57)(64, 57), (72,64)(72, 64), (137,128)(137, 128)
Inverted extended Hamming(22,16)(22, 16), (39,32)(39, 32), (72,64)(72, 64), (76,68)(76, 68), (137,128)(137, 128)

Source: reproduced by ch29_case_study_ecc_in_processor_caches.py.

Proof. This is the theorem of the same name in the section Hsiao's Odd-Weight Columns of SECDED and Hsiao Codes, which shows that no one, two or three such columns can sum to zero [8]. ■\blacksquare

The script checks the three conditions on both matrices, and checks the conclusion directly as well, confirming that no column is the sum of two others. Figure 7 draws the (39,32)(39, 32) matrix. All 32 of its data columns have weight three, and its rows hold 15, 15, 15, 15, 15, 15 and 13 ones, 103 in all. The (72,64)(72, 64) matrix mixes data columns of weight three and five, because only (83)=56\binom{8}{3} = 56 columns of length eight have weight three, too few for 64 data bits, and each of its eight rows holds 27 ones, 216 in all.

The check matrix of OpenTitan's Hsiao (39,32) code, rebuilt from the seven encoder masks, with seven rows, 32 data columns of weight three and seven check columns of weight one. The rows hold 15, 15, 15, 15, 15, 15 and 13 ones. Three data columns, marked with triangles, are columns the book's (39,32) matrix does not use. data bits 0 to 31 check bits 0 4 8 12 16 20 24 28 32 36 38 row 0 15 row 1 15 row 2 15 row 3 15 row 4 15 row 5 15 row 6 13 ones weight 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 1 1 1 1 1 1 1 Triangles mark data columns 0, 15 and 27, which the book's (39,32) matrix lacks. Every column has odd weight, and no two columns are equal. a 1 in a data column a 1 in a check column a 0 Rebuilt from prim_secded_39_32_enc.sv, OpenTitan commit 4ced702ca207
Figure 7. OpenTitan's Hsiao (39,32) check matrix, rebuilt from the seven encoder masks of prim_secded_39_32_enc.sv at commit 4ced702ca207. All 32 data columns have weight three, and the rows hold 15, 15, 15, 15, 15, 15 and 13 ones. Triangles mark the three data columns that the matrix of SECDED and Hsiao Codes does not use. Data: computed by ch29_charts.py in the companion repository.

Counting ones turns into counting gates. A syndrome bit whose row has weight ww is the XOR of ww inputs, which takes w−1w - 1 two-input XOR gates, so the (39,32)(39, 32) syndrome needs 103−7=96103 - 7 = 96 gates and the (72,64)(72, 64) syndrome needs 216−8=208216 - 8 = 208. The encoder XORs only the data ones of each row, one gate fewer per row, which gives 89 gates and 200. The longest rows, of 15 and 27 inputs, need trees of 4 and 5 levels. No matrix can keep every row below the average, so the fullest row holds at least ⌈96/7⌉=14\lceil 96/7 \rceil = 14 data ones at (39,32)(39, 32) and 208/8=26208/8 = 26 at (72,64)(72, 64), and both matrices meet those floors exactly. A synthesis tool may share XOR terms between rows, so these counts are estimates, and Project: A SEC-DED Encoder and Decoder measures a real netlist instead.

SECDED and Hsiao Codes built its own (39,32)(39, 32) and (72,64)(72, 64) matrices under the same conditions, and the script imports them from ch20_secded_and_hsiao_codes.py and compares. Table 4 sets out the result.

Table 4. OpenTitan's Hsiao matrices against those of SECDED and Hsiao Codes, at both sizes

PropertyOpenTitan (39,32)(39, 32)Earlier (39,32)(39, 32)OpenTitan (72,64)(72, 64)Earlier (72,64)(72, 64)
Ones in each row15, 15, 15, 15, 15, 15, 1314, 14, 15, 15, 15, 15, 1527 in each of 827 in each of 8
Ones in the matrix103103216216
Syndrome XOR gates9696208208
Data columns shared29 of 3229 of 3257 of 6457 of 64
Shared columns at the same position115656
Codewords of weight 41,3661,3638,3968,392

Source: reproduced by ch29_case_study_ecc_in_processor_caches.py.

At (39,32)(39, 32) the two matrices share 29 of their 32 data columns, and only one of the 29 sits at the same position. OpenTitan uses the columns with ones in rows (0,3,4)(0, 3, 4), (0,1,2)(0, 1, 2) and (1,5,6)(1, 5, 6), the matrix of SECDED and Hsiao Codes uses (0,1,6)(0, 1, 6), (2,5,6)(2, 5, 6) and (3,4,6)(3, 4, 6) instead, and the row weights differ even after sorting. At (72,64)(72, 64), 57 data columns are shared and 56 of them sit at the same positions, the row weights agree exactly, and the seven columns that differ all have weight five. The weight-five columns still differ in structure, since pairs of them share two, three or four rows 8, 16 and 4 times in OpenTitan's matrix, against 12, 8 and 8 in the earlier one.

Are the matrices the same code in a different order? Rearranging columns keeps every row's weight, so the differing (39,32)(39, 32) row weights rule out a plain rearrangement of the matrix. But adding one row of a check matrix to another changes the matrix without changing the code, because a word passes the new checks exactly when it passes the old ones, so row weights alone cannot settle the question. The weight distribution can.

Proof. A fixed permutation of positions maps each codeword of the first code to exactly one codeword of the second and back again, so it is a one-to-one correspondence. Moving bits to new positions does not change how many of them are ones, so corresponding codewords have equal weight, and the count of each weight is the same in both codes. ■\blacksquare

OpenTitan's (39,32)(39, 32) code has 1,366 codewords of weight four against 1,363 for the code of SECDED and Hsiao Codes, and its (72,64)(72, 64) code has 8,396 against 8,392. By the lemma, no permutation of positions turns either code into its counterpart. The two are different choices with the same properties, because Hsiao's conditions fix the distance and the total of ones, not the matrix.

Three consequences follow for a designer. An encoder and a decoder must come from the same matrix, since a word encoded under one and checked under the other gives a nonzero syndrome for most good data. Test vectors are matrix-specific, so the check bits 0110101001101010 of the partial-write example belong to OpenTitan's matrix alone. And the weight-four count is the number of four-bit error patterns that pass with a zero syndrome, as Weight Distributions and Undetected Errors explained, so two valid Hsiao codes of the same size differ slightly in what they let through. Confirming that generated hardware implements its intended matrix is the work of Verifying ECC Hardware.

08.Inverted Codes

The encoder line quoted in OpenTitan's SEC-DED Generator ended in ^ 1'b1, which inverts check bit c1c_1. The inverted (39,32)(39, 32) encoder inverts c1c_1, c3c_3 and c5c_5 the same way, and its decoder inverts them back before computing the syndrome, as Figure 8 shows, by XORing the read word with the constant 39'h2A00000000, whose ones sit at bits 33, 35 and 37. A comment in secded_gen.py at that commit gives the reason, saying that "only odd bits are inverted to avoid all-0 / all-1 encodings", and the generator puts a one at every odd-numbered check bit. For (72,64)(72, 64) that rule gives 0xAA0000000000000000, with ones at c1c_1, c3c_3, c5c_5 and c7c_7, and the script uses both constants as copied from the two inverted decoders at that commit.

An inverted (39,32) SEC-DED code. On the write side the encoder produces 32 data bits and check bits c0 to c6, and check bits c1, c3 and c5 pass through NOT gates before they are stored. On the read side the same three bits pass through NOT gates again before an ordinary syndrome decoder, so a healthy word decodes as usual. A word read as all zeros, as from a stuck or unpowered array, then gives a syndrome with ones at bits 1, 3 and 5, weight three, which the (39,32) decoder reads as a single error, while the same fault in the (72,64) code gives weight four and reads as a double error. write read SEC-DED encoder array plain syndrome decoder 32 data 32 c0c1c2c3c4c5c6 c0c1c2c3c4c5c6 NOT gates on c1, c3 and c5 store the word as a coset of the plain code, and undo it on the read. All zeros read from a dead array, (39,32): syndrome ones at bits 1, 3, 5, weight 3, a false single error. The same fault in the (72,64) code, check bits 1, 3, 5, 7 inverted: weight 4, flagged as a double error.
Figure 8. The inverted (39,32) code. Check bits c1, c3 and c5 are inverted on the way into the array and inverted back on the way out, so healthy words decode as before. An all-zero read then gives a syndrome of weight three, which the (39,32) decoder takes for a single error and miscorrects to 0x00000040, while the (72,64) code gives weight four and flags a double error, so only the larger code refuses the data.

Why would all zeros matter? A linear code always contains the all-zero word. An array that reads back as all zeros, because its cells are stuck, its supply has failed or a fault has cleared it, returns a valid codeword holding data 0, and a plain decoder accepts it without complaint. The inversion moves the code off the all-zero word.

Proof. Distance is the weight of the XOR, and (x⊕a)⊕(y⊕a)=x⊕y(x \oplus a) \oplus (y \oplus a) = x \oplus y because a⊕a=0a \oplus a = 0, so d(x⊕a,y⊕a)=wt(x⊕y)=d(x,y)d(x \oplus a, y \oplus a) = \mathrm{wt}(x \oplus y) = d(x, y). For the second claim, suppose first that a∈Ca \in C. Closure of a linear code puts x⊕ax \oplus a in CC for every x∈Cx \in C, and the map x↦x⊕ax \mapsto x \oplus a is one-to-one, so it fills all of CC, and C⊕a=CC \oplus a = C is linear. Suppose instead that a∉Ca \notin C. The all-zero word equals x⊕ax \oplus a only for x=ax = a, which is not in CC, so the translate does not contain the all-zero word. Every linear code contains it, since x⊕x=0x \oplus x = 0 for any codeword xx, so the translate is not linear. ■\blacksquare

In hardware terms, the first half says that the inverted code keeps every guarantee of the plain one, since the decoder removes the constant and then decodes exactly as before. The second half says when the move works. The constant has syndrome 01010100101010 under the (39,32)(39, 32) matrix, because its ones sit on check positions whose columns are single ones, so it is not a codeword, and the inverted code does not contain the all-zero word.

Proof. The syndrome of the all-one word 1\mathbf{1} is H1H\mathbf{1}, whose entry in row ii is the XOR of the entries of row ii, which is 1 when the row has odd weight and 0 when it has even weight. The word is a codeword exactly when every entry of H1H\mathbf{1} is 0. ■\blacksquare

Every row of both OpenTitan Hsiao matrices has odd weight, so even the plain codes reject the all-one word, with syndromes 11111111111111 and 1111111111111111, and the inversion must not let it back in. The script checks this with the real constants. In the inverted codes the all-one read has syndrome 1111111⊕0101010=10101011111111 \oplus 0101010 = 1010101 at (39,32)(39, 32) and 11111111⊕01010101=1010101011111111 \oplus 01010101 = 10101010 at (72,64)(72, 64), both of weight four, so both decoders flag it as a double error. In the other direction, every row holds an even number of data ones, so all-zero and all-one data store the same check part, 01010100101010 at (39,32)(39, 32) and 0101010101010101 at (72,64)(72, 64), and no stored word is ever all zeros or all ones.

The all-zero read shows why the decoder's labels matter. At (72,64)(72, 64) its syndrome 0101010101010101 has weight four and is flagged as a double error. At (39,32)(39, 32) its syndrome 01010100101010 has weight three, and the OpenTitan decoder, whose single-error flag is err_o[0] = ^syndrome_o, labels every odd-weight syndrome a single error. That syndrome equals data column 6, so OpenTitan's inverted (39,32)(39, 32) decoder itself returns 0x00000040 and reports one repaired bit. The Ibex core of Register Files and the Ibex Core escapes the hazard only because both of its uses act on any reported error and never on the corrected data. The generator's comment is careful too, saying the inversion works for most codes with balanced fan-in and that formal assertions should prove no all-zero or all-one encoding exists. The inversion itself costs a few inverters.

09.Register Files and the Ibex Core

OpenTitan vendors the Ibex core, a small open RISC-V processor from lowRISC, which at the pinned commit can use these codes in its instruction cache and its register file. Both are options, since ICacheECC and RegFileECC default to 1'b0 in ibex_core.sv.

With ICacheECC set, ibex_icache.sv protects each tag entry, a valid bit and a 21-bit tag in the documented 4 kB configuration and zero-padded to 22 bits in larger ones, with prim_secded_inv_28_22, and each 32-bit beat of data with prim_secded_inv_39_32. The documentation says that the cache "never performs corrections" [10]. Any error in any of its RAMs cancels the hit, the request fetches from main memory as a miss would, a forced write invalidates the line, and a minor alert is raised. This is the clean-line recovery of Clean Lines and Dirty Lines, built in the open.

With SecureIbex and RegFileECC set, the core runs a shadow copy of itself on delayed inputs, and the documentation describes two register file instances, one driven by the main core and holding the data, the other driven by the shadow core and holding the corresponding check bits, which the shadow core checks [11]. In ibex_core.sv the code for the 32-bit data is prim_secded_inv_39_32, with one encoder on the write data and one decoder on each of the two read ports. In the CHERIoT configuration a second set guards each register's 35 capability bits with prim_secded_inv_64_57, zero-padded to 57 bits with only the seven check bits stored. All of these decoders leave their corrected-data outputs unconnected. The stated purpose is detecting fault injection attacks over the register file's large area, and a detected error raises a major alert rather than being corrected, so the false single error of an all-zero read raises the alert like any other.

In generic terms, a register file differs from a cache array in three ways. Its contents usually have no other copy, so every entry is in effect dirty. Its words are written whole, so it needs no read-modify-write. And its read ports feed the execution units directly, where the decoder's delay costs most, which favors checking beside use, or detecting and alerting as Ibex does. A storage code guards values at rest, while the checks of Arithmetic Codes and Checking Logic guard the logic that computes them.

10.Looking Ahead

A cache array can spend the same 12.5 percent on byte parity or on SEC-DED. Clean lines can be fetched again, so detection is enough, while dirty lines hold the only copy and need correction. A byte store into a SEC-DED word costs a read first, scrubbing keeps the loss linear in the interval, and interleaving splits a four-cell burst into four single flips. OpenTitan's open matrices meet Hsiao's conditions without matching those of SECDED and Hsiao Codes.

The gate counts here came from counting ones. Project: A SEC-DED Encoder and Decoder builds a (72,64)(72, 64) Hsiao encoder and decoder, verifies them, and measures the gate count of a real netlist.

11.Worked Examples

12.Exercises

References

  1. [1]Hennessy, John L. and Patterson, David A. (2017). “Computer Architecture: A Quantitative Approach.” 6th edition. Morgan Kaufmann. https://shop.elsevier.com/books/computer-architecture/hennessy/978-0-12-811905-1
  2. [2]Mukherjee, Shubhendu S. and Emer, Joel and Reinhardt, Steven K. (2005). “The Soft Error Problem: An Architectural Perspective.” In Proceedings of the 11th International Symposium on High-Performance Computer Architecture (HPCA-11), pp. 243–247. doi:10.1109/HPCA.2005.37
  3. [3]Mukherjee, Shubu (2008). “Architecture Design for Soft Errors.” Morgan Kaufmann. doi:10.1016/B978-0-12-369529-1.X5001-0
  4. [4]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
  5. [5]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
  6. [6]OpenTitan Project “SECDED Encoder and Decoder Generator.” lowRISC/opentitan repository, commit 4ced702ca207ad420fbae5226ac8685a17ebef7b. Read 2026-11-15. https://github.com/lowRISC/opentitan/blob/4ced702ca207ad420fbae5226ac8685a17ebef7b/util/design/secded_gen.py
  7. [7]OpenTitan Project “SECDED Code Configuration.” lowRISC/opentitan repository, commit 4ced702ca207ad420fbae5226ac8685a17ebef7b. Read 2026-11-15. https://github.com/lowRISC/opentitan/blob/4ced702ca207ad420fbae5226ac8685a17ebef7b/util/design/data/secded_cfg.hjson
  8. [8]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
  9. [9]Lin, Shu and Costello, Jr., Daniel J. (2004). “Error Control Coding: Fundamentals and Applications.” 2nd edition. Pearson Prentice Hall.
  10. [10]lowRISC Ibex Project “Instruction Cache.” Ibex documentation as vendored in lowRISC/opentitan, commit 4ced702ca207ad420fbae5226ac8685a17ebef7b. Read 2026-11-15. https://github.com/lowRISC/opentitan/blob/4ced702ca207ad420fbae5226ac8685a17ebef7b/hw/vendor/lowrisc_ibex/doc/03_reference/icache.rst
  11. [11]lowRISC Ibex Project “Security Features.” Ibex documentation as vendored in lowRISC/opentitan, commit 4ced702ca207ad420fbae5226ac8685a17ebef7b. Read 2026-11-15. https://github.com/lowRISC/opentitan/blob/4ced702ca207ad420fbae5226ac8685a17ebef7b/hw/vendor/lowrisc_ibex/doc/03_reference/security.rst

— Anirban

Hardware–software at the seam where compilers meet microcode.

FeedbackBook modePaper
error-correction-codinglinear-block-codes