Paper
Part IILinear Block Codes

Beyond SECDED

November 15, 202647 min readbeginner

One particle strike can flip two neighboring cells, which SEC-DED can only flag. The chapter builds codes for two random errors, two adjacent errors, one failed 4-bit symbol and errors that all flip one way.

A neutron from a cosmic-ray shower can strike a silicon nucleus in a memory chip, and the charged fragments of that collision leave a short trail of charge. When the charge reaches a storage cell it flips the bit the cell holds. Such a soft error damages no hardware, and the next write repairs it. As cells have shrunk, one strike has come to reach more than one cell, so two neighbors in a memory row can flip together [1]. A word stored with the (72,64)(72, 64) SEC-DED code of the chapter SECDED and Hsiao Codes then reads back with two wrong bits, and its decoder can only report the damage. The data is lost although the memory saw a single event.

This chapter asks what a memory designer can buy beyond SEC-DED, and at what price. Each answer starts from a fault model, a statement of which error patterns are likely, and ends with a code and a count of its check bits. Two random errors call for a double-error-correcting code built from a small finite field. Two adjacent errors call for a cheaper code that keeps Hsiao's eight check bits. A chip that fails whole calls for a code that corrects one multi-bit symbol, and bits that can fail only one way call for codes that count zeros. The chapter closes by setting all of them side by side for a 64-bit word.

Every code in the chapter is built, and every count, limit and syndrome it yields recomputed, by ch21_beyond_secded.py in the python/ folder of the companion repository ecc-book-lab, and the charts are drawn by ch21_charts.py in the same folder. The GNU Octave twin ch21_beyond_secded.m prints the same lines, as The Octave Route explains.

01.One Strike, Two Neighboring Bits

A memory row stores the 72 bits of a word in neighboring cells, so a strike whose charge spreads across two cells flips two neighboring bits of one word. Figure 1 draws a stretch of such a row. When the strike reaches one cell, the syndrome of Hsiao's (72,64)(72, 64) code [2] has odd weight, and the decoder flips the matching bit back. When it reaches two, the syndrome is the XOR of two odd-weight columns, which has even weight, and the decoder can only raise its uncorrectable-error flag.

One particle strike flips two neighboring cells of a 72-bit word protected by a (72,64) SEC-DED code. A single flipped cell gives an odd-weight syndrome and is corrected. Two flipped cells give an even-weight syndrome, so the decoder can only flag the word as uncorrectable. Part of one 72-bit word, bit positions 16 to 39, as stored in a memory row 1 0 1 1 0 0 1 0 1 1 1 1 1 1 0 0 1 1 0 1 0 1 1 0 ... ... 16 27 28 39 one particle strike two neighboring cells flip (72,64) SEC-DED decoder if only one cell flipped odd syndrome: corrected two neighboring cells flipped even syndrome: flagged, data lost
Figure 1. One particle strike flips two neighboring cells of a word stored with the (72,64) SEC-DED code. One flip would be corrected, but two give an even-weight syndrome that the decoder can only flag.

A count shows why the decoder has no better option. A 72-bit word can suffer a double error in (722)=2556\binom{72}{2} = 2556 ways, and eight check bits give only 256 syndromes, so most doubles must share a syndrome with other doubles. Only 71 of the 2556 pairs are neighbors, though. A fault model that names only adjacent doubles adds 71 patterns, which might fit inside the same eight check bits, while a model that names every double asks for far more. The chapter takes the expensive model first, because the field arithmetic it needs returns throughout the rest of the book.

02.Correcting Two Random Errors

Two flips anywhere in the word can come from two separate strikes between reads, or from one strike on a word that already holds a stuck cell.

How Many Check Bits Two Errors Need

A syndrome decoder corrects a set of error patterns exactly when no two share a syndrome, so that each can lead its own coset, as the chapter Syndrome Decoding and the Standard Array showed. An (n,k)(n, k) code has 2n−k2^{n-k} syndromes, and correcting every error of weight at most two means giving distinct syndromes to the error-free pattern, the nn singles and the (n2)\binom{n}{2} doubles. That is the sphere-packing bound of the chapter Hamming Codes and Perfect Codes with radius two.

Proof. With rr check bits the length is n=64+rn = 64 + r. At r=12r = 12 the left side of Equation 1 is 1+76+2850=29271 + 76 + 2850 = 2927, which fits in 212=40962^{12} = 4096. At r=11r = 11 it is 1+75+2775=28511 + 75 + 2775 = 2851, more than 211=20482^{11} = 2048, and every smaller rr fails too, since n≥65n \ge 65 gives 1+n2+n22>n22≥2112.5>2r1 + \tfrac{n}{2} + \tfrac{n^{2}}{2} > \tfrac{n^{2}}{2} \ge 2112.5 > 2^{r}.

For DEC-TED the distance must be at least six. Correction alone needs d≥5d \ge 5, so suppose d=5d = 5, with codewords xx and x′x' at distance 5. A word yy that agrees with x′x' on two of the five positions where they differ, and with xx elsewhere, is two errors from xx, so the decoder must return xx. It is also three errors from x′x', so if x′x' was sent the decoder must flag it. It cannot do both, so d≥6d \ge 6. Now delete one position from every codeword. Two codewords differ in at least 6 places, so they stay distinct, and the result is a linear code with 64 data bits, r−1r - 1 check bits and distance at least 5. It corrects two errors, so r−1≥12r - 1 \ge 12. ■\blacksquare

The theorem is a count. It rules out 12 or fewer check bits for DEC-TED and does not promise a code with 13. The code built below uses 15, and the gap is the price of a construction that can be written down and decoded quickly.

A Field of Sixteen Elements

The construction needs 4-bit words that can be multiplied and divided, not only XORed. The Part Finite Fields and Their Arithmetic builds such fields in general, and this chapter needs just one of them, written out as a table. Its 16 elements are the 4-bit words, and adding two of them means XORing their bits.

Multiplication comes from one rule. Take a symbol α\alpha and require α4=α+1\alpha^{4} = \alpha + 1, which is the polynomial x4+x+1x^{4} + x + 1 set to zero. Every power of α\alpha then reduces to a sum of 11, α\alpha, α2\alpha^{2} and α3\alpha^{3}, whose four coefficients c3c2c1c0c_3 c_2 c_1 c_0 are its bits. Multiplying by α\alpha shifts the bits left, and a 1 that leaves the top place stands for α4\alpha^{4}, so the shifted word is XORed with 00110011. From α0=0001\alpha^{0} = 0001 the shifts give 00100010, 01000100, 10001000, then α4=0011\alpha^{4} = 0011, α5=0110\alpha^{5} = 0110, α6=1100\alpha^{6} = 1100 and α7=1000⊕0011=1011\alpha^{7} = 1000 \oplus 0011 = 1011. Table 1 lists all fifteen.

Table 1. The fifteen nonzero elements of the field of sixteen elements, as powers of alpha, as polynomials in alpha and as four bits

PowerPolynomial in α\alphaBits c3c2c1c0c_3 c_2 c_1 c_0
α0\alpha^{0}1100010001
α1\alpha^{1}α\alpha00100010
α2\alpha^{2}α2\alpha^{2}01000100
α3\alpha^{3}α3\alpha^{3}10001000
α4\alpha^{4}α+1\alpha + 100110011
α5\alpha^{5}α2+α\alpha^{2} + \alpha01100110
α6\alpha^{6}α3+α2\alpha^{3} + \alpha^{2}11001100
α7\alpha^{7}α3+α+1\alpha^{3} + \alpha + 110111011
α8\alpha^{8}α2+1\alpha^{2} + 101010101
α9\alpha^{9}α3+α\alpha^{3} + \alpha10101010
α10\alpha^{10}α2+α+1\alpha^{2} + \alpha + 101110111
α11\alpha^{11}α3+α2+α\alpha^{3} + \alpha^{2} + \alpha11101110
α12\alpha^{12}α3+α2+α+1\alpha^{3} + \alpha^{2} + \alpha + 111111111
α13\alpha^{13}α3+α2+1\alpha^{3} + \alpha^{2} + 111011101
α14\alpha^{14}α3+1\alpha^{3} + 110011001

Source: reproduced by ch21_beyond_secded.py.

The fifteen powers are the fifteen nonzero words, each once, and the next shift returns α15=1\alpha^{15} = 1. So two nonzero elements multiply by adding exponents modulo 15, as Equation 2 records.

α4=α+1,αi⋅αj=α(i+j) mod 15\alpha^{4} = \alpha + 1, \qquad \alpha^{i} \cdot \alpha^{j} = \alpha^{(i + j) \bmod 15}
(2)

For example α6⋅α13=α19=α4=0011\alpha^{6} \cdot \alpha^{13} = \alpha^{19} = \alpha^{4} = 0011, and the inverse of α5\alpha^{5} is α10\alpha^{10}. The rule gives a field because x4+x+1x^{4} + x + 1 has no factor. A factor of degree 1 would make 0 or 1 a root, yet f(0)=f(1)=1f(0) = f(1) = 1. The only irreducible quadratic over GF(2)\mathrm{GF}(2) is x2+x+1x^{2} + x + 1, modulo which x3≡1x^{3} \equiv 1, so x4+x+1≡x+x+1=1x^{4} + x + 1 \equiv x + x + 1 = 1. The script also checks the table against shift-and-add multiplication on all 256 pairs, confirms that every nonzero element has an inverse and that no two nonzero elements multiply to zero, and checks associativity and distributivity on all 4,096 triples.

Three facts carry the proofs below, in every field GF(2m)\mathrm{GF}(2^{m}) built this way. Subtraction equals addition, since 1+1=01 + 1 = 0. Squaring distributes over a sum, (a+b)2=a2+b2(a + b)^{2} = a^{2} + b^{2}, because the cross term ab+abab + ab is zero. And a product of nonzero elements is never zero.

Proof. Since c=a+bc = a + b and 3=13 = 1, expanding gives c3=a3+a2b+ab2+b3c^{3} = a^{3} + a^{2}b + ab^{2} + b^{3}. Adding a3+b3a^{3} + b^{3} leaves a3+b3+c3=ab(a+b)=abca^{3} + b^{3} + c^{3} = ab(a + b) = abc. ■\blacksquare

Proof. Multiplying out, (x+a)(x+a+s)=x2+sx+a2+as(x + a)(x + a + s) = x^{2} + sx + a^{2} + as, and a2+sa+p=0a^{2} + sa + p = 0 gives p=a2+asp = a^{2} + as. If the product is zero, one factor is zero, since the field has no zero divisors. ■\blacksquare

Columns Built from Powers and Cubes

A Hamming check matrix uses each nonzero mm-bit word once as a column, and that is exactly why it cannot correct two errors. Two errors at positions whose columns are aa and bb give the syndrome a+ba + b, which is itself the column of some third position, so the decoder cannot tell the pair from a single error there, or from any other pair with the same sum. The cure is a second half under each column that hands the decoder a second equation about the same positions. The obvious candidate, the square βi2\beta_i^{2}, adds nothing, because squaring distributes over a sum and the bottom half of every syndrome would then be the square of its top half. The cube is the next power to try, and the theorem below shows that it is enough.

Double correction needs distance five, which means that no four or fewer columns of the check matrix sum to zero, by the column reading of distance in the chapter Linear Codes. The construction gives each position ii a distinct nonzero field element βi\beta_i and stacks βi\beta_i above its cube βi3\beta_i^{3}. With GF(16)\mathrm{GF}(16) and βi=αi\beta_i = \alpha^{i}, each column has eight bits and the matrix is Equation 3. A set of columns with elements a,b,…a, b, \ldots sums to zero exactly when a+b+⋯=0a + b + \cdots = 0 and a3+b3+⋯=0a^{3} + b^{3} + \cdots = 0 both hold.

H=[1αα2⋯α141α3α6⋯α42]H = \begin{bmatrix} 1 & \alpha & \alpha^{2} & \cdots & \alpha^{14} \\ 1 & \alpha^{3} & \alpha^{6} & \cdots & \alpha^{42} \end{bmatrix}
(3)

Figure 2 draws the same matrix bit by bit.

The check matrix of the (15,7) double-error-correcting code. Column i stacks the GF(16) element alpha to the i above alpha to the 3i, each as four bits c3 to c0, so the matrix has eight rows and fifteen columns. The ones are shaded. Columns 3 and 10 are outlined, and their sum is the syndrome 1111 1011. 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 c3 0 0 0 1 0 0 1 1 0 1 0 1 1 1 1 c2 0 0 1 0 0 1 1 0 1 0 1 1 1 1 0 c1 0 1 0 0 1 1 0 1 0 1 1 1 1 0 0 c0 1 0 0 0 1 0 0 1 1 0 1 0 1 1 1 c3 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 c2 0 0 1 0 1 0 0 1 0 1 0 0 1 0 1 c1 0 0 0 1 1 0 0 0 1 1 0 0 0 1 1 c0 1 0 0 0 1 1 0 0 0 1 1 0 0 0 1 alphai alpha3i Column i holds alphai in its top four rows and alpha3i in its bottom four, each written c3 c2 c1 c0 in GF(16). Columns 3 and 10, outlined, add to the syndrome 1111 1011.
Figure 2. The check matrix of the (15,7) code, with each column stacking a power of alpha above its cube. The outlined columns 3 and 10 sum to the syndrome of the worked example.

Proof. One column has top half a≠0a \ne 0. Two columns sum to zero only if a=ba = b. Three columns with a+b+c=0a + b + c = 0 have bottom half abc≠0abc \ne 0, by the lemma Three elements that sum to zero. For four, suppose a+b+c+d=0a + b + c + d = 0 and a3+b3+c3+d3=0a^{3} + b^{3} + c^{3} + d^{3} = 0, and write s=a+b=c+ds = a + b = c + d, which is nonzero. Expanding as in that lemma gives a3+b3=s(s2+ab)a^{3} + b^{3} = s(s^{2} + ab) and c3+d3=s(s2+cd)c^{3} + d^{3} = s(s^{2} + cd), so s(ab+cd)=0s(ab + cd) = 0 and ab=cdab = cd. Then c2+sc+ab=c2+(c+d)c+cd=0c^{2} + sc + ab = c^{2} + (c + d)c + cd = 0, so cc is a root of x2+sx+ab=(x+a)(x+b)x^{2} + sx + ab = (x + a)(x + b), and the lemma A quadratic has at most two roots makes cc equal to aa or bb, against distinctness. ■\blacksquare

The (15,7) Code

With all fifteen nonzero elements of GF(16)\mathrm{GF}(16) the matrix is 8×158 \times 15. Column 0 reads 0001000100010001 top to bottom, column 1 reads 0010100000101000 and column 14 reads 1001111110011111. The bottom halves take only five values, because (α3)5=1(\alpha^{3})^{5} = 1, yet the eight rows are independent. The script finds rank 8, so the code has k=7k = 7 data bits and 128 codewords, with weights A0=1A_0 = 1, A5=18A_5 = 18, A6=30A_6 = 30, A7=15A_7 = 15, A8=15A_8 = 15, A9=30A_9 = 30, A10=18A_{10} = 18 and A15=1A_{15} = 1. The minimum distance is exactly five, and the 121 patterns of weight at most two, 1+15+(152)1 + 15 + \binom{15}{2} of them, have 121 distinct syndromes. This is the double-error-correcting BCH code of length 15, from the family Bose and Ray-Chaudhuri described [3], and a later Part develops BCH codes in general [4].

For an error set EE, the two syndrome halves are the sums in Equation 4.

S1=∑i∈Eαi,S3=∑i∈Eα3iS_1 = \sum_{i \in E} \alpha^{i}, \qquad S_3 = \sum_{i \in E} \alpha^{3i}
(4)

If both are zero, the decoder assumes no error. One error at ii gives S1=αiS_1 = \alpha^{i} and S3=S13S_3 = S_1^{3}, which the decoder recognizes. Two errors at elements aa and bb give S1=a+b≠0S_1 = a + b \ne 0 and S3=S1(S12+ab)S_3 = S_1(S_1^{2} + ab), so ab=S3/S1+S12ab = S_3/S_1 + S_1^{2}, and both are roots of the locator polynomial in Equation 5.

x2+S1x+(S3S1+S12)=(x+a)(x+b)x^{2} + S_1 x + \left( \frac{S_3}{S_1} + S_1^{2} \right) = (x + a)(x + b)
(5)

The decoder tries all fifteen nonzero elements as xx and finds either two distinct roots, which name the error positions, or none, which means at least three errors, and the word is flagged. So does S1=0S_1 = 0 with S3≠0S_3 \ne 0. Three errors are not always caught, though. Three errors inside the support of one of the 18 codewords of weight 5 leave the word two bits from that codeword, which the decoder returns. The (15,7)(15, 7) code is DEC but not DEC-TED.

In hardware the division is the awkward step, and the decoder avoids it. When S1≠0S_1 \ne 0, multiplying Equation 5 through by S1S_1 gives the test S1x2+S12x+S3+S13=0S_1 x^{2} + S_1^{2} x + S_3 + S_1^{3} = 0, which holds at exactly the same values of xx and needs only products. Each bit position ii gets its own copy of the test with x=αix = \alpha^{i} fixed, and a product with a fixed power of α\alpha is a fixed pattern of XOR gates, so all fifteen tests run at once. Each drives the flip of its own bit only while S1≠0S_1 \ne 0, since an error-free word has S1=S3=0S_1 = S_3 = 0 and passes every test. For the errors at positions 3 and 10, with S1=α12S_1 = \alpha^{12} and S3=α7S_3 = \alpha^{7}, the script finds the test zero at x=α3x = \alpha^{3} and x=α10x = \alpha^{10} and nowhere else.

A DEC-TED Code for 64 Data Bits

In GF(2m)\mathrm{GF}(2^{m}) each column takes 2m2m bits and the length is at most 2m−12^{m} - 1. With m=6m = 6 that is 63, too short for 64 data bits, so the word needs m=7m = 7. The polynomial x7+x+1x^{7} + x + 1 builds GF(128)\mathrm{GF}(128), and the script confirms that the powers of α\alpha run through all 127 nonzero words before α127=1\alpha^{127} = 1. The 14×12714 \times 127 matrix has rank 14, a (127,113)(127, 113) code. Keeping its first 78 columns leaves rank 14 and gives a (78,64)(78, 64) code whose distance stays at least five by the lemma Shortening keeps the distance in SECDED and Hsiao Codes. Its 3082 patterns of weight at most two have 3082 distinct syndromes.

Triple detection needs one more bit. Add a row of all ones and a new column 0⋯010 \cdots 01 for an overall parity bit. Every column now ends in 1, so every codeword has even weight. A nonzero codeword has a nonzero first part, since a zero first part would force the parity bit to zero too, and that first part is a (78,64)(78, 64) codeword of weight at least 5. An even weight of at least 5 is at least 6, so the (79,64)(79, 64) code has d≥6d \ge 6, and the theorem Correcting and detecting together in the chapter Distance, Detection and Correction, with t=2t = 2 and s=3s = 3, gives DEC-TED since t+s≤d−1t + s \le d - 1. The script confirms 3161 distinct syndromes.

The price is 15 check bits, an overhead of 23.44%, two above the counting minimum of 13, against 21.88% for the (78,64)(78, 64) DEC code. Either is nearly twice SEC-DED, and the decoder must solve a quadratic over GF(128)\mathrm{GF}(128) whenever a read shows an error.

03.Correcting Two Adjacent Errors

If the fault model names only adjacent doubles, the code must correct 71 more patterns rather than 2556, and a careful choice of columns fits them into Hsiao's eight check bits.

Odd-weight columns, as in Hsiao's code, keep the analysis short. A single error at ii gives the odd syndrome hih_i. A double at ii and jj gives hi⊕hjh_i \oplus h_j, which is even by the lemma Parity of an XOR in SECDED and Hsiao Codes and nonzero because the columns are distinct. An adjacent double at ii and i+1i + 1 has the neighbor sum hi⊕hi+1h_i \oplus h_{i+1} as its syndrome.

Proof. Single syndromes are distinct odd words and neighbor sums are even, so the only possible collision is between two neighbor sums, and equal sums would leave two adjacent doubles indistinguishable. If the sums are distinct, the following decoder works. A zero syndrome means no error. An odd syndrome equal to a column names that single error, and any other odd syndrome is flagged. An even syndrome equal to a neighbor sum names that adjacent pair, and any other even syndrome is flagged. A double always gives an even syndrome, so it is never taken for a single. ■\blacksquare

The weak point is a nonadjacent double whose syndrome happens to equal a neighbor sum, because the decoder then flips the wrong pair. The wrong pair shares no position with the true one, since hi⊕hj=hl⊕hl+1h_i \oplus h_j = h_l \oplus h_{l+1} with ii equal to ll or l+1l + 1 would make the true pair adjacent. So a miscorrection leaves four wrong bits and reports the word as repaired.

Proof. The n−1n - 1 neighbor sums are distinct among the 2r−1−12^{r-1} - 1 nonzero even words, so n≤2r−1n \le 2^{r-1}. Equality would use every nonzero even word once. Each bit position is 1 in 2r−22^{r-2} even words, an even number when r≥3r \ge 3, so the XOR of all of them is zero. But the XOR of the neighbor sums telescopes to h0⊕hn−1h_0 \oplus h_{n-1}, which is not zero. ■\blacksquare

The limit sits one below the theorem The SEC-DED length bound in SECDED and Hsiao Codes, which allows 2r−12^{r-1}, so adjacency costs one position. With four check bits there are eight odd columns but only seven nonzero even words, so no (8,4)(8, 4) code of this kind exists, as the script's search confirms. Any linear SEC-DED-DAEC code must also give distinct syndromes to the error-free word, the nn singles and the n−1n - 1 adjacent doubles, which is Equation 6.

1+n+(n−1)=2n≤2r1 + n + (n - 1) = 2n \le 2^{r}
(6)

For 64 data bits, r=7r = 7 gives 2n=142>1282n = 142 > 128, while r=8r = 8 gives 144≤256144 \le 256, so eight check bits is the least, the same as for SEC-DED.

The smallest case is a (7,3)(7, 3) code with four check bits, as long as the lemma allows, drawn in Figure 3. Its columns in storage order are 00010001, 00100010, 01000100, 10001000, 01110111, 11101110 and 10111011, and its six neighbor sums 00110011, 01100110, 11001100, 11111111, 10011001 and 01010101 are distinct. They leave one nonzero even word unused, 10101010, and the nonadjacent pairs with that syndrome are the only doubles the decoder flags. The matrix has rank 4. The decoder corrects all 7 singles and all 6 adjacent doubles, and of the 15 nonadjacent doubles it miscorrects 12 and flags 3.

The check matrix of the (7,3) SEC-DED-DAEC code found by the search. Its seven columns, 0001, 0010, 0100, 1000, 0111, 1110 and 1011, all have odd weight. The six sums of neighboring columns, 0011, 0110, 1100, 1111, 1001 and 0101, are distinct even-weight words, so every adjacent double error has its own syndrome. The one even syndrome left over is 1010. 0 1 2 3 4 5 6 row 0 0 0 0 1 0 1 1 row 1 0 0 1 0 1 1 0 row 2 0 1 0 0 1 1 1 row 3 1 0 0 0 1 0 1 position 0011 1100 1001 0110 1111 0101 neighbor sums neighbor sums Each column has odd weight: it is the syndrome of a single error at that position. Each neighbor sum has even weight: it is the syndrome of a double error at those two positions. The even syndrome left over, 1010, belongs to the doubles at 0 and 6, 1 and 3, 2 and 5: flagged.
Figure 3. The (7,3) SEC-DED-DAEC code. Its odd-weight columns have six distinct neighbor sums, and the one even syndrome they leave unused marks the nonadjacent doubles the decoder flags.

Twelve of fifteen sounds poor, and a count shows it is the best four check bits can do.

Proof. Let SS be the set of columns and fix a neighbor sum ss. The sets SS and S⊕sS \oplus s each hold nn of the 2r−12^{r-1} odd words, so they share at least 2n−2r−12n - 2^{r-1}. Each shared word is a column whose partner h⊕sh \oplus s is also a column, and each such pair is counted from both ends, so at least n−2r−2n - 2^{r-2} pairs of columns sum to ss. One is the adjacent pair, and the rest are nonadjacent, because the neighbor sums are distinct, so the decoder miscorrects each of them. No pair has two sums, so adding over the n−1n - 1 neighbor sums gives the bound. ■\blacksquare

The script searched for each code depth first, trying odd words in increasing order for each position and backing up whenever none kept the neighbor sums distinct. Table 2 sets the codes it found beside the floor.

Table 2. SEC-DED-DAEC codes found by the search, with the adjacent doubles they correct, what happens to their nonadjacent doubles, and the floor on miscorrection

CodeRankAdjacent doubles correctedNonadjacent doublesMiscorrectedFlaggedFloor
(7,3)(7, 3)461512312
(13,8)(13, 8)51266511548
(39,32)(39, 32)738703490213228
(72,64)(72, 64)871248514651020497

Source: reproduced by ch21_beyond_secded.py.

The (7,3)(7, 3) code meets the floor exactly. The (72,64)(72, 64) code uses 8 unit columns, 47 of weight 3 and 17 of weight 5, and miscorrects 1465 of its 2485 nonadjacent doubles, 59.0%, against a floor of 497, or 20.0%. Four of that code's 71 neighbor sums carry the floor's count of 8 pairs, and the other 67 carry more. A search that weighs miscorrection can do better than one that stops at the first valid code. Dutta and Touba searched heuristically for SEC-DED-DAEC codes with the same number of check bits as SEC-DED, choosing the columns to reduce the miscorrection of nonadjacent doubles [5]. No choice of columns falls below the floor.

04.Interleaving Instead of Check Bits

Adjacent errors can also be handled without changing the code. Interleaving stores four 72-bit SEC-DED words in one row of 288 cells, with cell cc holding bit ⌊c/4⌋\lfloor c/4 \rfloor of word c mod 4c \bmod 4. Cell 13 holds bit 3 of word 1, and its neighbors belong to words 0 and 2. Figure 4 draws the arrangement with the words labeled A to D.

Four-way bit interleaving. Four 72-bit words A, B, C and D share one 288-cell row, so cell k holds bit k div 4 of word k mod 4. A burst of four neighboring cells, here cells 6 to 9, puts exactly one error in each word. A 4:1 multiplexer under every group of four cells selects the word being read. The first 16 of the 288 cells in one row. Cell k holds bit k div 4 of word k mod 4. 0 A0 1 B0 2 C0 3 D0 4 A1 5 B1 6 C1 7 D1 8 A2 9 B2 10 C2 11 D2 12 A3 13 B3 14 C3 15 D3 ... a burst of 4 cells puts one error in each word 4:1 word select, 2 bits bit 3 of the selected word to its SEC-DED decoder One 4:1 multiplexer per bit of the word: 72 of them under every 288-cell row, and no extra check bits. A burst of 5 to 8 cells puts at most two errors in any one word, which SEC-DED still detects.
Figure 4. Four-way interleaving. A burst of up to four neighboring cells puts at most one error in each word, which SEC-DED corrects, at the cost of a row four times as wide and a multiplexer for each bit.

For bursts of 1 to 9 neighboring cells, the script counts the most errors in one word as 1, 1, 1, 1, 2, 2, 2, 2 and 3. Every burst of up to 4 cells is corrected, every burst of up to 8 is detected, and nine cells can put three errors into one word. Cells cc and c+4c + 4 leave the same remainder on division by 4, so they belong to the same word, and a burst of bb neighboring cells therefore puts ⌈b/4⌉\lceil b/4 \rceil errors into its busiest word. The interleave costs no check bits. Its cost is wiring, a row four times as wide and 72 four-to-one multiplexers that select one word on each read. An array that already selects among several words per row gets this protection cheaply, which is why the cell layout and the code are best chosen together.

05.Errors Confined to One Symbol

Some memories build each word from several chips, each supplying four bits. When one chip fails, any of its four bits may be wrong, and the fault model becomes one bad symbol. A code that corrects it treats the word as a string of elements of GF(16)\mathrm{GF}(16).

A symbol can go wrong in q−1q - 1 ways, so with nn symbols and rr check symbols the error-free word and the n(q−1)n(q - 1) single-symbol errors need distinct syndromes, which is Equation 8.

1+n(q−1)≤qr1 + n(q - 1) \le q^{r}
(8)

Proof. An error of value e≠0e \ne 0 in symbol ii has syndrome e hie\,h_i. Suppose errors ee in symbol ii and e′e' in symbol jj share a syndrome. If i=ji = j, a nonzero entry of hih_i gives e=e′e = e'. If i≠ji \ne j, then hj=(e/e′) hih_j = (e/e')\,h_i, a multiple, which was ruled out. Conversely, if hj=c hih_j = c\,h_i, the error cc in symbol ii and the error 1 in symbol jj collide, and a zero column makes its symbol's errors invisible. ■\blacksquare

The theorem caps the length. The qr−1q^{r} - 1 nonzero columns fall into classes of q−1q - 1 multiples, and a code takes at most one from each, which gives Equation 9. The qq-ary Hamming code of the chapter Hamming Codes and Perfect Codes takes one from every class and meets it.

n≤qr−1q−1n \le \frac{q^{r} - 1}{q - 1}
(9)

For 64 data bits in 16 symbols of 4 bits, two check symbols allow at most 17 symbols, room for 60 data bits, and 18 symbols would need 271>256271 > 256 syndromes. Three check symbols allow 273, and 19 symbols need only 286, so a code over GF(16)\mathrm{GF}(16) needs three check symbols, or 12 check bits.

A code that meets this gives data symbols 0 to 14 the columns (1,γ,γ2)(1, \gamma, \gamma^{2}) with γ=αi\gamma = \alpha^{i}, data symbol 15 the column (0,1,1)(0, 1, 1), and the three check symbols the unit columns. The script confirms that no column is zero and that none of the 171 pairs has one column a multiple of the other, so the 285 single-symbol errors give 285 distinct nonzero syndromes. Expanding each element into 4 bits gives a 12×7612 \times 76 binary matrix of rank 12, a (76,64)(76, 64) code with an overhead of 18.75%, drawn in Figure 5.

A single-symbol-correcting code for 64 data bits. The 76-bit word is cut into 19 symbols of 4 bits, 16 for data and 3 for checks. Any error confined to one symbol is corrected. Here symbol 5, bits d20 to d23, carries the error value 0100, which is alpha squared in GF(16). Its three syndrome symbols are alpha squared, alpha to the 7 and alpha to the 12, and their common ratio alpha to the 5 names symbol 5. 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 16 data symbols, bits d0 to d63 3 check symbols A (76,64) code over GF(16): 19 symbols of 4 bits each 0 1 0 0 error in symbol 5, bits d20 to d23 error value e = 0100 = alpha2 syndrome S1, S2, S3 = alpha2, alpha7, alpha12 S2 / S1 = S3 / S2 = alpha5, so symbol 5
Figure 5. The (76,64) single-symbol-correcting code. One error inside a 4-bit symbol gives three syndrome elements whose ratio names the symbol and whose first element is the error value.

The decoder reads the syndrome as S1S_1, S2S_2 and S3S_3. An error ee in data symbol i≤14i \le 14 gives (e,eγ,eγ2)(e, e\gamma, e\gamma^{2}), so all three are nonzero, the equal ratios S2/S1=S3/S2=γS_2/S_1 = S_3/S_2 = \gamma name the symbol, and S1=eS_1 = e is the value to add back. An error in symbol 15 gives S1=0S_1 = 0 and S2=S3≠0S_2 = S_3 \ne 0, and an error in a check symbol makes exactly two of the three zero. Any other syndrome is flagged.

A binary code need not spend its check bits in whole symbols. Cut the 64+r64 + r bits into 4-bit symbols in order, the last one shorter if need be. With 8 check bits the 18 full symbols need 1+18⋅15=2711 + 18 \cdot 15 = 271 syndromes, more than 28=2562^{8} = 256. With 9 the word gains a 1-bit symbol, and the 272 syndromes needed fit within 29=5122^{9} = 512. The count does not promise a code, but the script carries a searched 9×739 \times 73 check matrix of rank 9 whose 271 single-symbol errors give 271 distinct nonzero syndromes, a (73,64)(73, 64) code with an overhead of 14.06%. Spreading the check bits over more, partly empty symbols lowers the count, but each extra symbol is another chip.

Designers still pay for whole symbols. In memory built from 4-bit chips, 9 check bits fill three chips, so the (73,64)(73, 64) word takes the same 19 chips as the (76,64)(76, 64) word, and the three extra bits buy detection. When two chips fail, the (73,64)(73, 64) code miscorrects 17,553 of 34,695 double-symbol errors, 50.6%, and the (76,64)(76, 64) code only 405 of 38,475, or 1.1%, flagging the rest.

Bytes work the same way with q=256q = 256. Kaneda and Fujiwara built byte codes of this kind for memory that also detect two bad bytes [6], Chen and Hsiao reviewed such codes for semiconductor memory [7], and Fujiwara's book collects the symbol-level codes of dependable systems [8]. The Reed–Solomon codes of a later Part correct several bad symbols at once.

06.Errors in One Direction

Some faults push bits one way only. Charge leaking from a cell can turn a stored 1 into a 0 but not the reverse, and lines that a fault ties to ground can only read 0. Such errors can hit many bits at once, and a code built for them detects large errors cheaply.

Proof. A 1→01 \to 0 error turns xx into a word yy that xx covers, with weight d(x,y)d(x, y), and every such yy is reached by exactly one such error, which goes undetected exactly when yy is a codeword. A 0→10 \to 1 error from yy is the same pair with the roles exchanged. ■\blacksquare

The lemma rules out linear codes, because every codeword covers the all-zero word, so codes that detect every unidirectional error are not linear.

The Berger Code

The count runs from 0 to kk, so it needs the check bits in Equation 10. Eight data bits need 4, and 64 need 7, an overhead of 10.94%. Berger introduced the code in 1961 for channels whose errors run one way [9].

r=⌈log⁡2(k+1)⌉r = \left\lceil \log_2 (k + 1) \right\rceil
(10)

Proof. Suppose (u,A)(u, A) covers (v,B)(v, B). In the data, vv has the zeros of uu plus the jdj_d positions where uu has a 1 and vv a 0, so B=z(v)=A+jdB = z(v) = A + j_d. In the check, every 1 of BB is a 1 of AA, so B≤AB \le A. Then jd=0j_d = 0, so v=uv = u and B=AB = A, and the covering-pair criterion finishes the proof. ■\blacksquare

A 1→01 \to 0 error can only raise the zero count of the data and can only lower the stored number, so the two never meet again. Figure 6 draws a checker for 8 data bits, and the script finds 0 covering pairs among all codewords for k=8k = 8.

A checker for the Berger code with 8 data bits. Each data bit d7 to d0 passes through a NOT gate, a counter adds the ones of the inverted bits to give the 4-bit number of zeros z3 to z0, four XOR gates compare that number with the stored check bits c3 to c0, and an OR of the four comparisons raises the error output. d7 d6 d5 d4 d3 d2 d1 d0 count the ones 4-bit sum z3 c3 z2 c2 z1 c1 z0 c0 error OR of 4 The NOT gates turn each 0 of the data into a 1, so the count of ones is the count of zeros of d. Each XOR compares one bit of that count, z, with the stored check bit c. Data 10110010 has check 0100.
Figure 6. A Berger checker for 8 data bits. It counts the zeros of the data by counting the ones of its complement, and it raises the error output when the count differs from the stored check.

Counting ones instead fails. The word 1101101011011010 has five ones and would carry 01010101, and 1101001011010010 has four and would carry 01000100, so the two 1→01 \to 0 flips that turn 11011010 010111011010\,0101 into 11010010 010011010010\,0100 land on a valid codeword. A 1→01 \to 0 error moves the zero count and the stored number in opposite directions, and the ones count in the same direction.

Proof. Let uiu_i have ones in its first ii positions, so uju_j covers uiu_i for i<ji < j. If two had the same check AA, then (uj,A)(u_j, A) would cover (ui,A)(u_i, A). So the k+1k + 1 checks are distinct. ■\blacksquare

For k=64k = 64 the bound is 7, the Berger code's own count.

Counting Zeros Modulo a Power of Two

A fault model that also bounds the error weight allows fewer check bits. The simplest idea keeps only the zero count modulo 2r2^{r}.

Proof. Take a 1→01 \to 0 error from codeword (u,A)(u, A) to codeword (v,B)(v, B) with jdj_d data flips and jcj_c check flips. Every 1 of BB is a 1 of AA, so D=A−BD = A - B is the word of flipped check bits and jc=wt(D)j_c = \mathrm{wt}(D), while z(v)=z(u)+jdz(v) = z(u) + j_d gives jd≡−D(mod2r)j_d \equiv -D \pmod{2^{r}}. If D=0D = 0, then jd≥2r≥r+1j_d \ge 2^{r} \ge r + 1. Otherwise jd≥2r−Dj_d \ge 2^{r} - D, so the weight is at least 2r−(D−wt(D))2^{r} - (D - \mathrm{wt}(D)). Adding 1 to a number raises its weight by at most 1, so D−wt(D)D - \mathrm{wt}(D) never decreases and is at most 2r−1−r2^{r} - 1 - r, which leaves a weight of at least r+1r + 1. A 0→10 \to 1 error is the same pair read backward. ■\blacksquare

With 64 data bits and rr from 2 to 6, the script finds the limit exactly rr each time. At r=7r = 7 nothing is reduced, and the code is the Berger code.

A small case shows why the limit cannot be raised. With r=2r = 2, the data 1101101011011010 has three zeros and carries the check 1111. Flipping its second bit and both check bits, all from 1 to 0, gives 10011010 0010011010\,00. The new data has four zeros, and 4 mod 4=04 \bmod 4 = 0 matches the stored 0000, so an error of weight 3=r+13 = r + 1 passes unseen. Here the stored number fell by D=3D = 3 at the cost of wt(D)=2\mathrm{wt}(D) = 2 check flips, and the single data flip made up the rest, so the weight 2r−(D−wt(D))=4−1=32^{r} - (D - \mathrm{wt}(D)) = 4 - 1 = 3 from the proof is met exactly.

Bose-Lin Codes

Spending the check patterns more cleverly does better. Bose and Lin gave systematic codes that detect 6 errors with 4 check bits and 5⋅2r−4+r−45 \cdot 2^{r-4} + r - 4 errors with r≥5r \ge 5 [10]. The two constructions below reach those figures, and the script checks every limit at k=64k = 64 over every pair of zero counts. The first is an offset zero count, which keeps the top two check bits as a flag holding exactly one 1, with the check in Equation 11. At r=4r = 4 it is Bose and Lin's code, and for larger rr a generalization made here.

c(u)=(z(u) mod 2r−1)+2r−2c(u) = \left( z(u) \bmod 2^{r-1} \right) + 2^{r-2}
(11)

Proof. The check lies between 2r−22^{r-2} and 3⋅2r−2−13 \cdot 2^{r-2} - 1, so its top two bits are 0101 or 1010, and neither covers the other. Under a 1→01 \to 0 error between codewords (u,A)(u, A) and (v,B)(v, B), the top bits therefore stay put, so D=A−B<2r−2D = A - B < 2^{r-2}, jc=wt(D)j_c = \mathrm{wt}(D) and jd≡−D(mod2r−1)j_d \equiv -D \pmod{2^{r-1}}. If D=0D = 0, the weight is at least 2r−1≥2r−2+r−12^{r-1} \ge 2^{r-2} + r - 1 for r≥4r \ge 4. Otherwise it is at least 2r−1−(2r−2−1−(r−2))=2r−2+r−12^{r-1} - \left(2^{r-2} - 1 - (r - 2)\right) = 2^{r-2} + r - 1. ■\blacksquare

At r=4r = 4 the check is (z mod 8)+4(z \bmod 8) + 4, which detects up to 6, where counting zeros modulo 16 in the same four bits detects 4. The offset matters. With 2r−12^{r-1} in its place at r=5r = 5, the top bit is always 1, and the code detects only 4.

The second construction, for r≥5r \ge 5, reduces the count modulo 6⋅2r−46 \cdot 2^{r-4}. Its top four check bits name which of six blocks the reduced count falls in, using the six words of weight two, 00110011, 01010101, 01100110, 10011001, 10101010 and 11001100, and its low r−4r - 4 bits give the place inside the block. The same argument gives a limit of 5⋅2r−4+r−45 \cdot 2^{r-4} + r - 4, which is 11, 22 and 43 at r=5r = 5, 6 and 7, against 11, 20 and 37 for the offset count. Figure 7 plots both beside the reduced count. For k=8k = 8 the script also checks all 65,536 pairs of codewords directly and finds limits of 2 and 3 for counting modulo 4 and 8, 6 for (z mod 8)+4(z \bmod 8) + 4, and every weight for the Berger code.

Unidirectional error weight detected against check bits, 64 data bits zeros mod 2r offset zero count Bose-Lin, second construction 2 r = 2 3 r = 3 4 6 r = 4 5 11 11 r = 5 6 20 22 r = 6 37 43 r = 7 Berger: every weight 0 16 32 48 64 Check bits r beside 64 data bits Largest weight always detected
Figure 7. The largest unidirectional error weight each zero-count code always detects, against its check bits, for 64 data bits. Data: computed by ch21_charts.py in the companion repository.

07.Choosing a Code from a Fault Model

Table 3 sets the chapter's codes side by side for 64 data bits, each with the counting minimum for its fault model, and Figure 8 draws the same comparison.

Table 3. Codes for 64 data bits matched to fault models, with their check bits, their overhead and the counting minimum for each model

Fault modelCodeCheck bitsOverheadCounting minimum
one random bitHamming SEC (71,64)(71, 64)710.94%7
one random bit, two detectedHsiao SEC-DED (72,64)(72, 64)812.5%8
two random bits, three detectedDEC-TED (79,64)(79, 64)1523.44%13
two adjacent bitsSEC-DED-DAEC (72,64)(72, 64)812.5%8
one 4-bit symbolsingle-symbol code (76,64)(76, 64)1218.75%9, or 12 in whole symbols
unidirectional, any weightBerger (71,64)(71, 64)710.94%7
unidirectional, at most 6 bitsBose-Lin (68,64)(68, 64)46.25%not derived

Source: reproduced by ch21_beyond_secded.py.

Check bits each fault model costs for 64 data bits check bits of the code counting minimum one random bit Hamming SEC (71,64) 7 one random bit, two detected Hsiao SEC-DED (72,64) 8 two random bits, three detected DEC-TED (79,64) 15 two adjacent bits SEC-DED-DAEC (72,64) 8 one 4-bit symbol S4EC (76,64) 12 unidirectional, any weight Berger (71,64) 7 unidirectional, at most 6 bits Bose-Lin (68,64) 4 0 4 8 12 16 Check bits beside 64 data bits
Figure 8. Check bits beside 64 data bits for each fault model, with the counting minimum the chapter derives marked on each bar where one exists. Data: computed by ch21_charts.py in the companion repository.

The table reads as a price list. A second random bit costs seven check bits more than SEC-DED, plus field arithmetic in the decoder, so it pays only where two independent errors in one word are likely. Adjacent pairs cost no extra check bits. A DAEC code adds decoder gates and miscorrects 59.0% of nonadjacent doubles in the code found here, while a four-way interleave adds multiplexers and leaves the code alone. A chip that can fail whole calls for symbol correction at 9 check bits, or 12 to flag most double-chip failures. Unidirectional faults are the cheapest, 7 bits for every weight and 4 for up to six, but those codes only detect, so the system must fetch a good copy or stop.

The Hamming, Hsiao, DAEC and Berger codes all meet their counting minimums, so none can be beaten. The (76,64)(76, 64) code sits three bits above the binary minimum of 9, the price of whole check symbols. The DEC-TED code sits two bits above its minimum of 13, and the count alone cannot say whether a code with 13 exists.

08.Looking Ahead

The chapter matched codes to four fault models beyond one random bit. Powers and cubes in GF(128)\mathrm{GF}(128) give a (79,64)(79, 64) DEC-TED code with 15 check bits. Odd-weight columns with distinct neighbor sums correct adjacent doubles within Hsiao's 8, at the price of miscorrecting some nonadjacent ones, and interleaving does the same job with wiring. A code over GF(16)\mathrm{GF}(16) corrects a 4-bit symbol with 12 check bits and a searched binary code with 9, and counting zeros detects unidirectional errors with 7 check bits for every weight or 4 for up to six.

All of these codes protect bits at rest. The next chapter, Arithmetic Codes and Checking Logic, protects bits in motion through an adder or a multiplier, where one faulty gate can corrupt many bits of a result. There AN and residue codes check the arithmetic, the Berger code returns as Berger check prediction, and two-rail and parity checkers expose their own faults.

09.Worked Examples

10.Exercises

References

  1. [1]Baumann, R. C. (2005). “Radiation-Induced Soft Errors in Advanced Semiconductor Technologies.” IEEE Transactions on Device and Materials Reliability, 5(3), pp. 305–316. doi:10.1109/TDMR.2005.853449
  2. [2]Hsiao, M. Y. (1970). “A Class of Optimal Minimum Odd-weight-column SEC-DED Codes.” IBM Journal of Research and Development, 14(4), pp. 395–401. doi:10.1147/rd.144.0395
  3. [3]Bose, R. C. and Ray-Chaudhuri, D. K. (1960). “On a Class of Error Correcting Binary Group Codes.” Information and Control, 3(1), pp. 68–79. doi:10.1016/S0019-9958(60)90287-4
  4. [4]Lin, Shu and Costello, Jr., Daniel J. (2004). “Error Control Coding: Fundamentals and Applications.” 2nd edition. Pearson Prentice Hall.
  5. [5]Dutta, Avijit and Touba, Nur A. (2007). “Multiple Bit Upset Tolerant Memory Using a Selective Cycle Avoidance Based SEC-DED-DAEC Code.” In 25th IEEE VLSI Test Symposium (VTS'07), pp. 349–354. doi:10.1109/VTS.2007.40
  6. [6]Kaneda, Shigeo and Fujiwara, Eiji (1982). “Single Byte Error Correcting-Double Byte Error Detecting Codes for Memory Systems.” IEEE Transactions on Computers, C-31(7), pp. 596–602. doi:10.1109/TC.1982.1676056
  7. [7]Chen, C. L. and Hsiao, M. Y. (1984). “Error-Correcting Codes for Semiconductor Memory Applications: A State-of-the-Art Review.” IBM Journal of Research and Development, 28(2), pp. 124–134. doi:10.1147/rd.282.0124
  8. [8]Fujiwara, Eiji (2006). “Code Design for Dependable Systems: Theory and Practical Applications.” Wiley. doi:10.1002/0471792748
  9. [9]Berger, J. M. (1961). “A Note on Error Detection Codes for Asymmetric Channels.” Information and Control, 4(1), pp. 68–73. doi:10.1016/S0019-9958(61)80037-5
  10. [10]Bose, Bella and Lin, Der Jei (1985). “Systematic Unidirectional Error-Detecting Codes.” IEEE Transactions on Computers, C-34(11), pp. 1026–1032. doi:10.1109/TC.1985.1676535

— Anirban

Hardware–software at the seam where compilers meet microcode.

FeedbackBook modePaper
error-correction-codinglinear-block-codes