Paper
Part IILinear Block Codes

SECDED and Hsiao Codes

November 15, 202647 min readbeginner

Main memory stores each 64-bit word with eight check bits. The chapter proves why eight is the least, builds SEC-DED codes from the extended Hamming code and from Hsiao's odd-weight columns, and counts their gates.

A server's main memory stores every 64-bit word with eight extra bits beside it, and the memory controller checks all 72 bits each time the word is read. If one bit has flipped since the word was written, the controller puts it back. If two bits have flipped, the controller cannot tell which two, but it reports that the word is damaged, so the system can stop before a wrong value spreads. A code with both powers is called SEC-DED, also written SECDED, for single-error-correcting and double-error-detecting, and codes of this kind are the usual protection for semiconductor main memory, as the review of [1] surveys.

The chapter Hamming Codes and Perfect Codes already built one such code, the extended Hamming code, by adding an overall parity bit to a Hamming code. This chapter asks what every SEC-DED code needs, proves that eight check bits are the least a linear code can add to a 64-bit word, and then follows M. Y. Hsiao's 1970 observation that a different choice of check-matrix columns gives the same protection with fewer gates and a shallower decoder [2]. The last section asks what each code does when three bits flip, a case neither code is designed for, and finds that the choice of columns matters there as well.

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

01.A 64-Bit Word and Its Check Bits

Hardware numbers bits from 0, and this chapter does the same. A 64-bit data word has bits d0d_0 to d63d_{63}, and its eight check bits are c0c_0 to c7c_7. Grouped into bytes of eight, the data fills bytes 0 to 7 and the check bits fill byte 8, so the stored word is nine bytes, 72 bits in all. Figure 1 draws the word three times. In the first strip nothing has gone wrong, in the second d21d_{21} has flipped and a SEC-DED decoder puts it back, and in the third d6d_6 and d50d_{50} have flipped and the decoder reports the word as damaged without touching any bit.

A 64-bit data word stored as a 72-bit SECDED codeword, drawn as nine bytes of eight bit cells. Bytes 0 to 7 hold the data bits d0 to d63 and byte 8 holds the check bits c0 to c7. In the second strip one cell, d21, is flipped, and the decoder corrects it. In the third strip two cells, d6 and d50, are flipped, and the decoder reports an error without correcting anything. 64 data bits, bytes 0 to 7 8 check bits d0-d7 d8-d15 d16-d23 d24-d31 d32-d39 d40-d47 d48-d55 d56-d63 c0-c7 one bit flipped, d21: the decoder finds it and flips it back d21 two bits flipped, d6 and d50: the decoder flags the word but cannot locate them d6 d50 72 bits in all, 9 bytes: 8 check bits for 64 data bits, an overhead of 12.5 percent
Figure 1. A 64-bit word stored with eight check bits as nine bytes. One flipped bit is corrected, and two flipped bits are detected and reported.

Why eight check bits, and not seven or nine? The chapter Hamming Codes and Perfect Codes answered the first half of the question. With rr check bits the syndrome can take 2r2^r values. A decoder that corrects every single error needs one value to mean "no error" and one distinct value for each of the n=k+rn = k + r positions where the error could be, so

2r≥k+r+1.2^r \ge k + r + 1 .
(1)

For k=64k = 64 data bits, r=6r = 6 gives 26=642^6 = 64 against 64+6+1=7164 + 6 + 1 = 71, which fails, and r=7r = 7 gives 128128 against 7272, which holds. So correction alone needs seven check bits. The next section proves that detecting double errors as well needs the stronger condition 2r−1≥k+r2^{r-1} \ge k + r. For k=64k = 64, r=7r = 7 gives 26=642^6 = 64 against 7171, which fails, and r=8r = 8 gives 27=1282^7 = 128 against 7272, which holds. Eight check bits are therefore the least, the codeword has n=72n = 72 bits, and the check bits cost 8/64=12.58/64 = 12.5 percent of the data.

Table 1. The least number of check bits for single-error correction and for SEC-DED at six data widths, with the SEC-DED codeword length and the check bits as a percentage of the data bits

Data bits kkCheck bits for SECCheck bits for SEC-DEDLength nnOverhead
4348100.0%
8451362.5%
16562237.5%
32673921.9%
64787212.5%
128891377.0%

Source: reproduced by ch20_secded_and_hsiao_codes.py.

Table 1 shows two patterns. SEC-DED always costs exactly one check bit more than correction alone, because writing r+1r + 1 for rr in the condition 2r−1≥k+r2^{r-1} \ge k + r gives back Equation 1. And the overhead falls as the word widens, since the check bits grow only with the logarithm of the width. A 128-bit word needs nine check bits, 7.0 percent, but its 137 bits do not fill a whole number of bytes, while the 72-bit word fills exactly nine.

02.When One Correction and Two Detections Are Possible

The promise of a SEC-DED code concerns two kinds of error.

The chapter Distance, Detection and Correction proved that a bounded-distance decoder with radius tt corrects every error of weight up to tt and flags every error of weight t+1t + 1 to ss whenever t+s≤d−1t + s \le d - 1. With t=1t = 1 and s=2s = 2 that condition reads d≥4d \ge 4. The theorem below adds the converse, so distance four is not merely enough for SEC-DED but required.

Proof. If d≥4d \ge 4, then t=1t = 1 and s=2s = 2 satisfy t+s=3≤d−1t + s = 3 \le d - 1, and the theorem Correcting and detecting together from Distance, Detection and Correction gives a decoder that corrects every single error and flags every double error. For the converse, suppose d≤3d \le 3 and pick two codewords c≠c′c \ne c' at distance dd. If d=3d = 3, let yy be c′c' with one of the three positions where cc and c′c' differ set to its value in cc. Then yy differs from c′c' in one position and from cc in two. A single error on c′c' produces yy, so a decoder that corrects every single error must return c′c' on yy. A double error on cc also produces yy, and the decoder returns c′c' instead of flagging it, so the code is not SEC-DED. If d=2d = 2, change one of the two differing positions of c′c' in the same way. The result is one bit from c′c' and one bit from cc, so single errors on two different codewords produce the same word, and the decoder can return only one of them. If d=1d = 1, then c′c' is cc with one bit flipped, and on input c′c' the decoder must return c′c' for the error-free case and cc for the single error on cc, which is impossible. In every case the code fails, so d≥4d \ge 4 is necessary. ■\blacksquare

For a linear code the condition turns into a statement about columns. The chapter Linear Codes showed that the minimum distance of a linear code is the least number of columns of its check matrix HH that sum to zero. Over GF(2)\mathrm{GF}(2) one column sums to zero only if it is the zero column, and two columns sum to zero only if they are equal. So d≥4d \ge 4 holds exactly when the columns h0,…,hn−1h_0, \ldots, h_{n-1} of HH are nonzero, distinct, and no three of them sum to zero.

Each condition has a meaning for the decoder. An error in position jj alone gives the syndrome s=hjs = h_j, and errors in positions ii and jj give s=hi⊕hjs = h_i \oplus h_j. Distinct columns make every double-error syndrome nonzero, and the rule against three columns summing to zero says that hi⊕hjh_i \oplus h_j never equals a third column hlh_l. So a double error can never look like no error or like a single error, and a decoder can follow three questions in turn. If s=0s = 0, nothing is wrong. If ss equals a column hjh_j, bit jj is flipped back. Anything else is flagged.

How long can such a code be? The answer is the bound promised above.

Proof. Let SS be the set of the nn columns of HH, all distinct and nonzero words of length rr, and fix one column hh. Form the set S⊕hS \oplus h of all words s⊕hs \oplus h with ss in SS. The map s↦s⊕hs \mapsto s \oplus h undoes itself, so it is one-to-one and S⊕hS \oplus h also has nn members. Suppose some word lay in both sets, so that s⊕h=ts \oplus h = t with ss and tt in SS. If s=hs = h, then t=0t = 0, but no column is zero. If s≠hs \ne h, then t≠st \ne s because h≠0h \ne 0, and t≠ht \ne h because s≠0s \ne 0, so s⊕h⊕t=0s \oplus h \oplus t = 0 is a sum of three distinct columns equal to zero, which the code forbids. So the two sets share no word, and together they hold 2n2n distinct words of length rr. There are only 2r2^r such words, so 2n≤2r2n \le 2^r and n≤2r−1n \le 2^{r-1}. ■\blacksquare

The bound is the reason for eight check bits. With r=8r = 8 the length can reach 128, leaving room for up to 120 data bits, while r=7r = 7 allows a length of at most 64 and so at most 57 data bits, too few for a 64-bit word. A SEC-DED code with r+1r + 1 check bits may reach length 2r2^r, one bit longer than a Hamming code with rr, so the extra check bit buys detection and one more position.

03.SEC-DED from the Extended Hamming Code

Hamming's 1950 paper already added an overall parity check to detect double errors [3], and the extended Hamming code with eight check bits meets the bound exactly. It has length 128=27128 = 2^7 and 120 data bits, and its check matrix has a simple rule. Number the positions 0 to 127. The column for position jj holds the binary form of jj in rows 0 to 6, with the least significant bit in row 0, and a 1 in row 7, the overall parity row that covers every bit. Position 0 has the column with zeros in rows 0 to 6 and a 1 in row 7, so it is the overall parity bit, and positions 1, 2, 4, 8, 16, 32 and 64 are the Hamming check bits. Throughout the chapter a column or syndrome is written as a string of bits with row 0 first, so the column of position 5 is 1010000110100001.

A memory word needs 64 data bits, not 120, and the way to get a shorter code from a longer one is to shorten it [4].

Proof. Take a nonzero codeword of the shortened code and put zeros back in the deleted positions. The result is a codeword of the original code, because it satisfies every original parity check, which reads only the kept positions where the word is unchanged and the deleted positions where it is zero. It has the same weight as the shortened word. So every nonzero weight in the shortened code is also a nonzero weight in the original, and the least of them cannot be smaller. ■\blacksquare

Keeping positions 0 to 71 and deleting positions 72 to 127 removes 56 positions. None of the deleted positions is a power of 2, so all of them are data positions. The shortened code keeps the eight check positions 0, 1, 2, 4, 8, 16, 32 and 64 and the 64 data positions among 1 to 71, so it is a (72,64)(72, 64) code with d=4d = 4.

Decoding uses the two-part syndrome from Hamming Codes and Perfect Codes. Rows 0 to 6 give a 7-bit word s′s', the Hamming syndrome, and row 7 gives a single bit pp, the parity of the whole received word. A single error at position jj sets p=1p = 1 and makes s′s' the binary form of jj. A double error sets p=0p = 0, because two flips leave the parity unchanged, and makes s′s' the XOR of two different positions, which is nonzero. An error at position 37, whose binary form is 100101100101, gives s′=1010010s' = 1010010 with row 0 first and p=1p = 1, so the decoder flips position 37. Table 2 collects the four cases.

Table 2. The decision an extended Hamming decoder makes from the two parts of its syndrome, the Hamming syndrome s' and the overall parity p

s′s'ppWhat happenedWhat the decoder does
zero0no errorpasses the word unchanged
nonzero1one error at position s′s'flips that position
zero1one error in the parity bitflips position 0
nonzero0two errorsflags the word

Source: reproduced by ch20_secded_and_hsiao_codes.py.

Figure 2 draws the same decision as a flow that applies to every SEC-DED code in this chapter. The extended Hamming code answers its odd-weight question with the parity bit pp.

The decision a SEC-DED decoder makes from its syndrome s. A zero syndrome means no error. A nonzero syndrome of even weight means two errors, which are flagged and not corrected. An odd syndrome that equals a column of the check matrix names the one bit to flip, and an odd syndrome that matches no column can only come from three or more errors and raises the no-match flag. syndrome s, r bits s = 0 ? weight of s odd ? s a column of H ? yes no error: pass the word unchanged no two errors: raise the double-error flag yes one error: flip the matching bit no yes no three or more: raise the no-match flag In the extended Hamming code the odd-weight test reads the overall parity bit p instead.
Figure 2. The decision a SEC-DED decoder makes from its syndrome. In the extended Hamming code the odd-weight test reads the overall parity bit instead.

The code works, and its cost is visible in the check matrix. Rows 0, 1 and 2 hold 36 ones each, rows 3, 4 and 5 hold 32 each, row 6 holds only 8, because only positions 64 to 71 have bit 6 set, and the parity row holds 72, one for every position. That is 284 ones. Each syndrome bit is computed by an XOR tree over the bits its row selects, and a row with ww ones needs w−1w - 1 two-input XOR gates, so the syndrome takes 284−8=276284 - 8 = 276 gates. The parity row is the problem. Its tree has 72 inputs, the widest in the decoder, and every bit of the word passes through it.

04.Hsiao's Odd-Weight Columns

Hsiao's idea replaces the parity row by a property of the columns. The smallest example has four data bits and four check bits. Its eight columns are

d0=1110,d1=1101,d2=1011,d3=0111,c0=1000,c1=0100,c2=0010,c3=0001,d_0 = 1110,\quad d_1 = 1101,\quad d_2 = 1011,\quad d_3 = 0111,\quad c_0 = 1000,\quad c_1 = 0100,\quad c_2 = 0010,\quad c_3 = 0001,

four data columns of weight 3 and four check columns of weight 1. These are all eight words of length 4 with odd weight, and no row of the matrix holds a 1 in every column. Each row holds four ones, sixteen in all.

Encoding works as in any systematic code. Check bit cic_i is the XOR of the data bits whose columns have a 1 in row ii. Row 0 selects d0d_0, d1d_1 and d2d_2, row 1 selects d0d_0, d1d_1 and d3d_3, row 2 selects d0d_0, d2d_2 and d3d_3, and row 3 selects d1d_1, d2d_2 and d3d_3. For the data 10111011, meaning d0=1d_0 = 1, d1=0d_1 = 0, d2=1d_2 = 1 and d3=1d_3 = 1, the checks are c0=1⊕0⊕1=0c_0 = 1 \oplus 0 \oplus 1 = 0, c1=1⊕0⊕1=0c_1 = 1 \oplus 0 \oplus 1 = 0, c2=1⊕1⊕1=1c_2 = 1 \oplus 1 \oplus 1 = 1 and c3=0⊕1⊕1=0c_3 = 0 \oplus 1 \oplus 1 = 0, so the check bits are 00100010.

Now decode. An error in d2d_2 gives the syndrome 10111011, the column of d2d_2, which has weight 3. Errors in d0d_0 and c1c_1 give 1110⊕0100=10101110 \oplus 0100 = 1010, which has weight 2. The single error left an odd syndrome and the double error an even one, and Table 3 shows that this is no accident. All 28 double errors give even syndromes, and they fall into seven classes of four.

Table 3. Every syndrome of the Hsiao (8,4) code and the errors that cause it

SyndromeWeightErrors that produce it
00000none
1110, 1101, 1011, 01113one error in d0d_0, d1d_1, d2d_2 or d3d_3
1000, 0100, 0010, 00011one error in c0c_0, c1c_1, c2c_2 or c3c_3
11114d0c3d_0 c_3, d1c2d_1 c_2, d2c1d_2 c_1, d3c0d_3 c_0
11002d0c2d_0 c_2, d1c3d_1 c_3, d2d3d_2 d_3, c0c1c_0 c_1
10102d0c1d_0 c_1, d1d3d_1 d_3, d2c3d_2 c_3, c0c2c_0 c_2
10012d0d3d_0 d_3, d1c1d_1 c_1, d2c2d_2 c_2, c0c3c_0 c_3
01102d0c0d_0 c_0, d1d2d_1 d_2, d3c3d_3 c_3, c1c2c_1 c_2
01012d0d2d_0 d_2, d1c0d_1 c_0, d3c2d_3 c_2, c1c3c_1 c_3
00112d0d1d_0 d_1, d2c0d_2 c_0, d3c1d_3 c_1, c2c3c_2 c_3

Source: reproduced by ch20_secded_and_hsiao_codes.py.

The 16 syndromes split as one zero word, eight odd words for the eight single errors and seven even nonzero words for the double errors, 1+8+7=161 + 8 + 7 = 16. The reason is a fact about weights. The lemma The weight of an XOR in Distance, Detection and Correction proved the identity w(a⊕b)=w(a)+w(b)−2 w(a∧b)w(a \oplus b) = w(a) + w(b) - 2\,w(a \wedge b), where a∧ba \wedge b is the word with ones where both aa and bb have ones. Its last term is even, which leads to the following.

Proof. For m=1m = 1 both sides are w(a1)w(a_1). Suppose the claim holds for m−1m - 1 words, and write b=a1⊕⋯⊕am−1b = a_1 \oplus \cdots \oplus a_{m-1}. The weight identity gives w(b⊕am)=w(b)+w(am)−2 w(b∧am)w(b \oplus a_m) = w(b) + w(a_m) - 2\,w(b \wedge a_m), and the last term is even, so w(b⊕am)≡w(b)+w(am)(mod2)w(b \oplus a_m) \equiv w(b) + w(a_m) \pmod 2. Replacing w(b)w(b) by w(a1)+⋯+w(am−1)w(a_1) + \cdots + w(a_{m-1}), which the assumption allows modulo 2, gives the claim for mm words. ■\blacksquare

So the XOR of an odd number of odd-weight words has odd weight, and the XOR of an even number of them has even weight. That is all a SEC-DED code needs.

Hsiao's own class also asks for the fewest ones and the most even rows, so the name is used loosely here.

Proof. The zero word has weight 0, which is even, so no column is zero. The columns are distinct, so no two of them sum to zero. Three columns hi⊕hj⊕hlh_i \oplus h_j \oplus h_l have, by the parity lemma, a weight with the parity of three odd numbers, which is odd, so their sum is not zero. No one, two or three columns sum to zero, so d≥4d \ge 4 by the column test of Linear Codes. A single error at jj gives s=hjs = h_j, of odd weight. A double error at ii and jj gives s=hi⊕hjs = h_i \oplus h_j, of even weight by the parity lemma, and nonzero because hi≠hjh_i \ne h_j. ■\blacksquare

The decoder therefore learns whether one or two bits failed from the parity of its own syndrome, an XOR over rr bits, instead of from a parity row over all nn bits. The price might seem to be length, since only odd words may serve as columns. The next lemma shows that nothing is lost.

Proof. Flipping bit 0 maps the set of words of length rr to itself, and doing it twice returns every word, so the map is one-to-one. It changes the weight by exactly one, so it sends every odd-weight word to an even-weight word and every even-weight word to an odd-weight word. The odd and even words are therefore equal in number, and each set holds half of 2r2^r, which is 2r−12^{r-1}. ■\blacksquare

For r=4,5,6,7,8r = 4, 5, 6, 7, 8 the counts are 8, 16, 32, 64 and 128. A Hsiao code can use every odd word as a column, which gives length 2r−12^{r-1}, exactly the SEC-DED bound.

A slightly larger code shows how the columns are chosen when there are more odd words than positions. With r=5r = 5 there are 16 odd words, namely five of weight 1, ten of weight 3 and one of weight 5. The five weight-1 words become the check columns. Eight data bits need eight more columns, and the cheapest are eight of the ten weight-3 words. The code in Figure 3 leaves out 1110011100 and 1001110011, which gives the data columns

11010, 11001, 10110, 10101, 01110, 01101, 01011, 0011111010,\ 11001,\ 10110,\ 10101,\ 01110,\ 01101,\ 01011,\ 00111

for d0d_0 to d7d_7.

The check matrix of a Hsiao (13,8) code. Its 13 columns are the eight data columns d0 to d7, each a 5-bit word of weight 3, and the five check columns c0 to c4, the weight-1 words. The ones are shaded. The rows hold 5, 6, 6, 6 and 6 ones, 29 in all, and every column has odd weight. data columns, weight 3 check columns, weight 1 d0 d1 d2 d3 d4 d5 d6 d7 c0 c1 c2 c3 c4 row 0 1 1 1 1 0 0 0 0 1 0 0 0 0 5 row 1 1 1 0 0 1 1 1 0 0 1 0 0 0 6 row 2 0 0 1 1 1 1 0 1 0 0 1 0 0 6 row 3 1 0 1 0 1 0 1 1 0 0 0 1 0 6 row 4 0 1 0 1 0 1 1 1 0 0 0 0 1 6 ones weight 3 3 3 3 3 3 3 3 1 1 1 1 1 29 No column is zero, no two are equal, and every column has odd weight, so d = 4.
Figure 3. The check matrix of a Hsiao (13,8) code. Every column has odd weight and no two are equal, so the distance is 4.

Reading the matrix by rows gives the five check equations.

c0=d0⊕d1⊕d2⊕d3,c1=d0⊕d1⊕d4⊕d5⊕d6,c2=d2⊕d3⊕d4⊕d5⊕d7,c3=d0⊕d2⊕d4⊕d6⊕d7,c4=d1⊕d3⊕d5⊕d6⊕d7.\begin{aligned} c_0 &= d_0 \oplus d_1 \oplus d_2 \oplus d_3, \\ c_1 &= d_0 \oplus d_1 \oplus d_4 \oplus d_5 \oplus d_6, \\ c_2 &= d_2 \oplus d_3 \oplus d_4 \oplus d_5 \oplus d_7, \\ c_3 &= d_0 \oplus d_2 \oplus d_4 \oplus d_6 \oplus d_7, \\ c_4 &= d_1 \oplus d_3 \oplus d_5 \oplus d_6 \oplus d_7 . \end{aligned}

For the data 1011001010110010, with d0=1d_0 = 1, d2=1d_2 = 1, d3=1d_3 = 1 and d6=1d_6 = 1 and the rest zero, these give c0=1c_0 = 1, c1=0c_1 = 0, c2=0c_2 = 0, c3=1c_3 = 1 and c4=0c_4 = 0, so the check bits are 1001010010 and the codeword has weight 6. The rows hold 5, 6, 6, 6 and 6 ones, 29 in all.

Every one of the 32 possible syndromes now has a meaning. The zero word means no error. The 13 columns name the 13 single errors. The 15 nonzero even words are the double-error syndromes, and all 15 occur among the 78 pairs of positions. The three odd words that are not columns, 1110011100, 1001110011 and 1111111111, cannot come from one or two errors at all, so they can only mean three or more. That accounts for 1+13+15+3=321 + 13 + 15 + 3 = 32 syndromes.

05.Choosing the Columns

A 64-bit word with eight check bits has 128 odd words of length 8 to choose from and needs only 72 of them. The choice decides how many gates the circuit needs and how deep it is. A first limit applies to every systematic SEC-DED code, odd columns or not.

Proof. A column of weight 0 is the zero column, which is forbidden. A column of weight 1 equals one of the columns of IrI_r, and two equal columns are forbidden. A column of weight 2 has ones in some rows ii and jj, so it equals ei⊕eje_i \oplus e_j, the sum of two columns of IrI_r, and these three columns sum to zero, which is forbidden. So every data column has weight at least 3. The kk data columns then hold at least 3k3k ones and IrI_r holds rr more. ■\blacksquare

For k=64k = 64 and r=8r = 8 the lemma gives at least 200 ones. A Hsiao code cannot reach that, because there are only (83)=56\binom{8}{3} = 56 words of length 8 and weight 3, and the next odd weight is 5.

Proof. Let aa of the 64 data columns have weight 3. They are distinct, so a≤56a \le 56. The remaining 64−a64 - a data columns have odd weight other than 1, which the columns of I8I_8 hold, and other than 3, so weight at least 5. The data columns therefore hold at least 3a+5(64−a)=320−2a≥320−112=2083a + 5(64 - a) = 320 - 2a \ge 320 - 112 = 208 ones, and I8I_8 adds 8, for at least 216. Taking all 56 weight-3 words and any 8 weight-5 words as data columns gives exactly 8+3⋅56+5⋅8=2168 + 3 \cdot 56 + 5 \cdot 8 = 216, and the result is an odd-weight-column code. ■\blacksquare

The extended Hamming matrix held 284 ones, so the Hsiao matrix saves 68, and with them 68 XOR gates in the syndrome. Hsiao asked for one more property [2]. The ones should be spread as evenly over the rows as possible, because the slowest syndrome bit sets the speed of the whole decoder. With 216 ones over 8 rows, some row holds at least ⌈216/8⌉=27\lceil 216/8 \rceil = 27, and a perfectly even spread puts 27 in every row.

A short count shows how to reach it. A weight-3 column with a 1 in a given row needs two more rows out of the remaining seven, so each row lies in (72)=21\binom{7}{2} = 21 of the 56 weight-3 columns. For the eight weight-5 columns, take the eight runs of five consecutive rows, wrapping around from row 7 to row 0.

11111000, 01111100, 00111110, 00011111, 10001111, 11000111, 11100011, 1111000111111000,\ 01111100,\ 00111110,\ 00011111,\ 10001111,\ 11000111,\ 11100011,\ 11110001

A row tt lies in the run that starts at row ii exactly when (t−i) mod 8(t - i) \bmod 8 is one of 0, 1, 2, 3 and 4, so every row lies in exactly five runs. Each row then holds 21+5+1=2721 + 5 + 1 = 27 ones, the last from I8I_8, and the matrix is balanced.

Any other eight weight-5 words also give 216 ones, but not necessarily an even spread. The first eight in dictionary order, the row sets {0,1,2,3,4}\{0,1,2,3,4\}, {0,1,2,3,5}\{0,1,2,3,5\} and so on up to {0,1,2,5,6}\{0,1,2,5,6\}, all contain rows 0, 1 and 2, and they leave the rows with 30, 30, 30, 26, 26, 25, 25 and 24 ones. Figure 4 compares the three matrices row by row.

Ones in each row of three (72,64) SEC-DED check matrices Extended Hamming (72,64) Hsiao, dictionary order Hsiao, balanced 5 levels 6 levels 7 levels row 0 row 1 row 2 row 3 row 4 row 5 row 6 row 7 0 16 32 48 64 80 Row of the check matrix, one syndrome bit each Ones in the row
Figure 4. Ones in each row of three (72,64) SEC-DED check matrices. A row with 17 to 32 ones needs a two-input XOR tree of 5 levels, 33 to 64 ones need 6, and 65 to 128 need 7. Data: computed by ch20_charts.py in the companion repository.

With two-input XOR gates the balancing buys less than it might seem. A tree over ww inputs has ⌈log⁡2w⌉\lceil \log_2 w \rceil levels, because each level of gates at most halves the number of signals, and both 27 and 30 lie between 24=162^4 = 16 and 25=322^5 = 32, so both trees take 5 levels. The difference appears with three-input XOR gates, where a tree takes ⌈log⁡3w⌉\lceil \log_3 w \rceil levels. Since 33=273^3 = 27, the balanced rows take 3 levels and a 30-input row takes 4.

The same reasoning sizes a 32-bit word with seven check bits. There are (73)=35\binom{7}{3} = 35 weight-3 words of length 7, more than the 32 data columns need, so every data column can have weight 3 and the matrix meets the lower bound 3k+r=1033k + r = 103 exactly. Each row lies in (62)=15\binom{6}{2} = 15 weight-3 columns. Leaving out the three words with row sets {0,1,2}\{0,1,2\}, {0,3,4}\{0,3,4\} and {1,5,6}\{1,5,6\} takes two ones from rows 0 and 1 and one from each other row, so the rows hold 14, 14, 15, 15, 15, 15 and 15 ones. The largest row of any such matrix holds at least ⌈103/7⌉=15\lceil 103/7 \rceil = 15, so this is as even as the count allows. The extended Hamming (39,32)(39, 32) code, by comparison, holds 135 ones with rows of 19, 19, 19, 16, 16, 7 and 39. Table 4 collects the five matrices.

Table 4. Ones, largest row, two-input XOR levels and syndrome XOR gates for five SEC-DED check matrices

CodeOnes in HHLargest rowLevelsSyndrome XOR gates
Extended Hamming (72,64)284727276
Hsiao (72,64), dictionary order216305208
Hsiao (72,64), balanced216275208
Extended Hamming (39,32)135396128
Hsiao (39,32)10315496

Source: reproduced by ch20_secded_and_hsiao_codes.py.

06.The Decoder in Gates

Figure 5 lays out the decoder for the balanced Hsiao (72,64)(72, 64) code. Its parts follow the flow of Figure 2.

The full decoder of a Hsiao (72,64) code in gates. Eight XOR trees form the syndrome s from the received 72-bit word. An eight-input OR tests whether s is nonzero, an eight-input XOR tests whether its weight is odd, and an AND of nonzero with not odd raises the double-error flag. For each of the 72 columns an eight-input AND matches s against that column, here column 11100000 of bit 0, and for each data bit an XOR flips the received bit when its match fires. A 72-input OR of all the match signals gives M, and an AND of odd weight with not M raises the no-match flag. received word y 72 bits syndrome s 8 XOR trees 27 inputs each 72 8 8 OR of 8 8 XOR of 8 s nonzero odd weight double error AND of 8 match 0 71 other matches OR of 72 M no match received bit 0 corrected bit 0 One match gate per column, 72 in all. The 64 data-bit matches each drive a correcting XOR. Drawn for bit 0, column 11100000: s0 to s2 enter directly, s3 to s7 inverted. The OR collects all 72 matches, and an odd syndrome that matches none raises the no-match flag.
Figure 5. A SEC-DED decoder for the Hsiao (72,64) code, drawn for data bit 0. Every data bit has its own match gate and correcting XOR, 64 of each, and the eight check columns have match gates that feed only the no-match flag.

The syndrome block is eight XOR trees, one per row, each over the received bits its row selects, and with 27 inputs per row it takes 8×26=2088 \times 26 = 208 gates and 5 levels. The zero detector is an OR over the eight syndrome bits, 7 gates, and its output says that something is wrong. The parity detector is an XOR over the same eight bits, 7 more gates, and its output says the syndrome has odd weight. The double-error flag is an AND of "nonzero" with the inverse of "odd", one gate and one inverter.

Correction needs a match signal for every data bit. The match for bit jj is an AND of eight inputs that is 1 exactly when s=hjs = h_j. It takes sis_i directly where hjh_j has a 1 and through an inverter where hjh_j has a 0, so for bit 0, whose column is 1110000011100000, bits s0s_0 to s2s_2 enter directly and s3s_3 to s7s_7 enter inverted. Eight inverters, one per syndrome bit, serve all the match gates. An eight-input AND is a tree of 7 two-input gates and 3 levels, so the 64 match signals take 64×7=44864 \times 7 = 448 gates. Each match then drives an XOR with its received bit, 64 more gates. Since the columns are distinct, at most one match fires, and since every column is odd, none fires on an even syndrome, so a double error leaves the data unchanged.

The no-match flag covers the last branch of the flow. Eight more match gates, 8×7=568 \times 7 = 56 gates, compare ss with the check columns. They flip no data bit, but without them a single check-bit error would look unmatched. An OR over all 72 match signals, 71 gates, gives a signal MM that is 1 when some column matched, and the flag is an AND of "odd" with the inverse of MM.

Correction and the double-error flag take 208+7+7+448+64+1=735208 + 7 + 7 + 448 + 64 + 1 = 735 two-input gates, and the no-match flag adds 56+71+1=12856 + 71 + 1 = 128, for 863 gates and 10 inverters. The path to a corrected data bit runs through 5 levels of syndrome, 3 of match and 1 of correction, 9 levels in all. The double-error flag also sits 9 levels deep, 5 for the syndrome, 3 for the OR or the XOR, and 1 for the final AND. The no-match flag is the slowest output, since MM arrives after 5+3+7=155 + 3 + 7 = 15 levels and the AND adds one, for 16. The encoder is the syndrome block without the check bits, so each check bit is an XOR over 26 data bits, 8×25=2008 \times 25 = 200 gates.

The extended Hamming decoder has the same parts, sized differently. Its syndrome takes 276 gates and 7 levels. Its parity bit pp is already a syndrome bit, so it needs no parity detector, and its zero detector covers only the seven bits of s′s', 6 gates. The total is 923 gates, the corrected data appears after 7+3+1=117 + 3 + 1 = 11 levels, and the no-match flag after 18. Its double-error flag waits for the slower of pp, at 7 levels, and the zero detector on s′s', whose widest tree of 36 inputs takes 6 levels and whose 7-input OR takes 3 more, so it sits max⁡(7,9)+1=10\max(7, 9) + 1 = 10 levels deep. Table 5 sets the four decoders side by side.

Table 5. Two-input gates in each part of four SEC-DED decoders, with the logic depth to a corrected data bit and to each flag

PartHsiao (72,64)Ext. Hamming (72,64)Hsiao (39,32)Ext. Hamming (39,32)
Syndrome XOR gates20827696128
Zero detector7665
Parity detector7060
Data match AND gates448448192192
Correcting XOR gates64643232
Double-error AND1111
Check match AND gates56564242
Any-match OR71713838
No-match AND1111
Total863923414439
Levels to corrected data911810
Levels to the double-error flag91089
Levels to the no-match flag16181416

Source: reproduced by ch20_secded_and_hsiao_codes.py.

The Hsiao decoder saves 68 syndrome gates and spends 8 of them back on its parity detector and wider zero detector, a net saving of 60 gates, and it delivers corrected data two levels sooner. The data match logic, at 448 gates, is the largest part of both decoders and, like the no-match logic, the same in each. The saving is therefore modest in gates and real in depth, and depth is what limits how fast a memory read can finish.

07.Three Errors

A SEC-DED code promises nothing about three errors, but its decoder still acts on them, and the parity lemma says how.

Proof. The syndrome is s=hi⊕hj⊕hls = h_i \oplus h_j \oplus h_l, the XOR of three odd-weight words, so it has odd weight by Equation 3. Odd weight rules out the zero word and every double-error syndrome, which are even. Suppose s=hms = h_m for some position mm. If mm were ii, then hj⊕hl=0h_j \oplus h_l = 0 and hj=hlh_j = h_l, which distinct columns forbid, and the same holds for jj and ll, so mm is a fourth position. The decoder flips bit mm, leaving the error pattern with ones at ii, jj, ll and mm. Its syndrome is hi⊕hj⊕hl⊕hm=s⊕s=0h_i \oplus h_j \oplus h_l \oplus h_m = s \oplus s = 0, so the returned word is a codeword, and it differs from the sent codeword in exactly four positions. ■\blacksquare

The first outcome is a miscorrection, the worst thing a decoder can do, because the word leaves the decoder with no flag, as a wrong codeword four bits from the one sent. The second outcome raises the no-match flag. For the Hsiao (72,64)(72, 64) code there are (723)=59,640\binom{72}{3} = 59{,}640 three-bit errors, and running the decoder of Figure 5 on all of them finds 33,568 miscorrected, 56.3 percent, and the other 26,072 flagged.

A rough estimate explains the figure. The syndrome of a triple is an odd word of length 8, and 72 of the 128 such words are columns. If the syndromes were spread evenly over the odd words, 72/128=56.2572/128 = 56.25 percent would match a column. Table 6 shows the exact split by the weight of the syndrome. Every weight-1 word is a check column and every weight-3 word is a data column, so those triples always miscorrect. Only 8 of the 56 weight-5 words are columns, and none of the 8 weight-7 words is, so most of those triples are flagged.

Table 6. Three-bit errors of the balanced Hsiao (72,64) code, grouped by the weight of their syndrome

Syndrome weightTriplesMiscorrectedFlagged
13,9523,9520
326,11226,1120
526,0403,50422,536
73,53603,536

Source: reproduced by ch20_secded_and_hsiao_codes.py.

The extended Hamming code fares much worse, and the reason is the structure of its column numbers. A triple at positions ii, jj and ll sets p=1p = 1, which looks like a single error, and makes s′s' the binary XOR of the three position numbers. The decoder miscorrects whenever that XOR is a position the shortened code still has.

Proof. A number below 64 has its ones only in bits 0 to 5, and so does the XOR of such numbers, so the XOR mm of three distinct positions ii, jj and ll below 64 is again below 64 and is a position of the code. The three flips give p=1p = 1 and s′=ms' = m, exactly the syndrome of a single error at mm. If mm were ii, then j⊕l=0j \oplus l = 0 and j=lj = l, which is false, and the same holds for jj and ll, so mm is a fourth position and the decoder flips it. ■\blacksquare

That alone is (643)=41,664\binom{64}{3} = 41{,}664 miscorrected triples, and triples that touch positions 64 to 71 add 3,640 more, for 45,304 in all, 76.0 percent. Figure 6 compares six codes, and Table 7 adds the dictionary-order matrix as a seventh.

What a SEC-DED decoder does with a three-bit error miscorrected, a fourth bit flipped flagged miscorrected Hsiao (8,4) 100.0% Hsiao (13,8) 76.9% Hsiao (39,32) 59.7% Extended Hamming (39,32) 69.3% Hsiao (72,64) 56.3% Extended Hamming (72,64) 76.0% 0 25 50 75 100 Share of all three-bit errors, percent
Figure 6. What a SEC-DED decoder does with every possible three-bit error, for six codes. Data: computed by ch20_charts.py in the companion repository.

Table 7. Three-bit errors miscorrected and flagged by the full decoder for seven SEC-DED codes, counted over every triple of positions

CodeTriplesMiscorrectedFlaggedShare miscorrected
Hsiao (8,4)56560100.0%
Hsiao (13,8)2862206676.9%
Hsiao (39,32)9,1395,4523,68759.7%
Extended Hamming (39,32)9,1396,3322,80769.3%
Hsiao (72,64), balanced59,64033,56826,07256.3%
Hsiao (72,64), dictionary order59,64034,03225,60857.1%
Extended Hamming (72,64)59,64045,30414,33676.0%

Source: reproduced by ch20_secded_and_hsiao_codes.py.

The small codes are the extreme case. The Hsiao (8,4)(8, 4) code uses all eight odd words as columns, so every odd syndrome matches one and every triple is miscorrected. The choice of the eight weight-5 columns in the (72,64)(72, 64) code matters too, though less, since the dictionary-order matrix miscorrects 464 more triples than the balanced one.

Those 26,072 flagged triples are what the 128 gates of the no-match flag buy, since a decoder without them would pass every one through uncorrected and unflagged.

08.Looking Ahead

A SEC-DED code corrects one bit and detects two, and the chapter found that eight check bits are the least a linear code can add to a 64-bit word, that odd-weight columns deliver the same promise with a shallower decoder, and that the choice of columns also decides how often three errors slip through as a silent miscorrection. Each of these results treats every bit as failing on its own.

Real memories do not always fail one bit at a time. The next chapter, Beyond SECDED, asks what to build when errors arrive in pairs, in neighboring bits, or in whole bytes, and how to choose a code from what is known about the faults.

09.Worked Examples

10.Exercises

References

  1. [1]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
  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]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
  4. [4]Lin, Shu and Costello, Jr., Daniel J. (2004). “Error Control Coding: Fundamentals and Applications.” 2nd edition. Pearson Prentice Hall.

— Anirban

Hardware–software at the seam where compilers meet microcode.

FeedbackBook modePaper
error-correction-codinglinear-block-codes