Paper
Part IILinear Block Codes

Syndrome Decoding and the Standard Array

November 15, 202652 min readbeginner

On a binary symmetric channel the most likely codeword is the nearest one. The standard array, the syndrome and a small lookup table turn that rule into XOR trees and a ROM, recover erased bits and price every failure.

A receiver holds the six bits 111101111101. It knows that the sender transmits only the eight codewords of one fixed code, and that the channel flips each bit with probability p=0.1p = 0.1, independently of the others. The word 111101111101 is not one of the eight, so at least one bit was flipped. Which codeword was sent? No answer is certain, since enough flips can turn any codeword into 111101111101. What the receiver can do is make the guess most likely to be right, and make it fast enough to keep up with a memory bus or a radio link.

Linear Codes described a code by a generator matrix GG and a parity-check matrix HH with GHT=0GH^T = 0. Groups and Cosets split the words of a small code into cosets, led each coset by a word of least weight, and showed that a short syndrome names the coset of each word of C5C_5. This chapter carries those ideas to every linear code. It proves that on a binary symmetric channel the most likely codeword is the nearest one, builds the standard array, and shows that the syndrome s=rHTs = rH^T always names the coset of the received word. The array then shrinks to a table of 2n−k2^{n-k} entries, built from XOR gates and a small memory. The same columns of HH recover erased bits, and the coset leaders give the exact probability that the decoder is right.

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

01.Which Codeword Was Sent?

The code behind the opening word has length n=6n = 6 and carries k=3k = 3 message bits, a (6,3)(6,3) code called C6C_6 in this chapter. Its generator matrix has the systematic form [ I∣P ]\left[\,I \mid P\,\right] of Linear Codes, and its parity-check matrix has the matching form [ PT∣I ]\left[\,P^T \mid I\,\right]. It is not the code of the same name in the exercises of Linear Codes, whose generator rows are 100011100011, 010101010101 and 001110001110.

G=[100110010011001111],H=[101100111010011001].G = \begin{bmatrix} 1 & 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 & 1 \end{bmatrix}, \qquad H = \begin{bmatrix} 1 & 0 & 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 & 0 & 1 \end{bmatrix}.

Multiplying the eight messages 000,001,…,111000, 001, \dots, 111 by GG gives, in that order, the eight codewords

C6={000000, 001111, 010011, 011100, 100110, 101001, 110101, 111010}.C_6 = \{000000,\ 001111,\ 010011,\ 011100,\ 100110,\ 101001,\ 110101,\ 111010\}.

Their weights are 0,4,3,3,3,3,4,40, 4, 3, 3, 3, 3, 4, 4, so the theorem on the minimum distance of a code closed under XOR, in Distance, Detection and Correction, gives d=3d = 3. Suppose the message 110110 was sent as 110101110101 and the third bit flipped. The receiver sees r=111101r = 111101 and has to work backward from it.

The channel is the binary symmetric channel BSC(p)\text{BSC}(p) of Channels, Signals and Likelihoods. Each bit arrives unchanged with probability 1−p1 - p and flipped with probability pp, independently of every other bit. Figure 1 draws it, together with a second view. A flip is an XOR with 1, so the channel adds an error pattern ee to the codeword, and r=c⊕er = c \oplus e with a 1 in ee at every flipped position.

The binary symmetric channel. On the left each sent bit arrives unchanged with probability 1 - p and flipped with probability p. On the right the same channel adds an error word to the codeword: 110101 plus 001000 gives the received word 111101, with position 3 flipped. sent received 0 1 0 1 1 - p 1 - p p p each bit flips with probability p the channel adds an error word sent c 1 1 0 1 0 1 error e 0 0 1 0 0 0 received r 1 1 1 1 0 1 + addition in GF(2) flips position 3 the weight of e counts the flips
Figure 1. The binary symmetric channel . Each bit arrives unchanged with probability and flipped with probability , independently of every other bit. Sending and flipping position 3 is the same as adding the error pattern to the codeword.

Fix a codeword cc. The words rr and cc differ in d(r,c)d(r, c) positions, where dd is the Hamming distance of Distance, Detection and Correction, and each of those bits must have flipped, with probability pp. Each of the other n−d(r,c)n - d(r, c) bits must have come through, with probability 1−p1 - p. The bits are independent, so the probabilities multiply.

P(r∣c)=p d(r,c) (1−p) n−d(r,c).P(r \mid c) = p^{\,d(r,c)}\,(1-p)^{\,n - d(r,c)}.
(1)

The number P(r∣c)P(r \mid c) is called the likelihood of cc. It is the probability of what was seen, computed as if cc had been sent. Table 1 lists the distance and the likelihood of every codeword for r=111101r = 111101 and p=0.1p = 0.1.

Table 1. The eight codewords of with their distance from and their likelihood at

MessageCodeword ccd(r,c)d(r, c)P(r∣c)P(r \mid c)
00000000000000000050.000009
00100100111100111130.000729
01001001001101001140.000081
01101101110001110020.006561
10010010011010011040.000081
10110110100110100120.006561
11011011010111010110.059049
11111111101011101030.000729

Source: reproduced by ch18_syndrome_decoding_and_the_standard_array.py.

The codeword 110101110101, at distance 1, has likelihood 0.1×0.95=0.0590490.1 \times 0.9^5 = 0.059049. Each extra unit of distance trades a factor 0.90.9 for a factor 0.10.1, which divides the likelihood by 9.

A likelihood is not yet the probability that cc was sent. That probability, written P(c∣r)P(c \mid r), comes from Bayes' rule. When the sender picks each of the 2k2^k messages with the same probability 2−k2^{-k}, the equal prior factors P(c)P(c) cancel.

P(c∣r)=P(r∣c) P(c)∑c′∈CP(r∣c′) P(c′)=P(r∣c)∑c′∈CP(r∣c′).P(c \mid r) = \frac{P(r \mid c)\,P(c)}{\sum_{c' \in C} P(r \mid c')\,P(c')} = \frac{P(r \mid c)}{\sum_{c' \in C} P(r \mid c')}.
(2)

The eight likelihoods add up to 0.0738000.073800, so P(110101∣111101)=0.059049/0.073800=0.800122P(110101 \mid 111101) = 0.059049 / 0.073800 = 0.800122. A receiver that answers 110101110101 is right four times in five when this word arrives, and every other codeword holds a smaller share.

02.Maximum Likelihood on the Binary Symmetric Channel

The table suggests two decoding rules that agree here. One picks the codeword with the largest likelihood, which is the rule probability recommends. The other picks the nearest codeword, which needs nothing but XORs and bit counts.

With equal priors, Equation 2 divides every likelihood by the same total, so the codeword of largest likelihood is also the codeword most likely to have been sent, and no other decoder is right more often. The theorem below says exactly when the easy rule and the right rule agree.

Proof. Write δ=d(r,c)\delta = d(r, c) and pull the factor (1−p)n(1-p)^n out of Equation 1.

P(r∣c)=(1−p)n(p1−p)δ=(1−p)nρ δ,ρ=p1−p.P(r \mid c) = (1-p)^n \left(\frac{p}{1-p}\right)^{\delta} = (1-p)^n \rho^{\,\delta}, \qquad \rho = \frac{p}{1-p}.
(3)

The factor (1−p)n(1-p)^n is positive and the same for every codeword, so the likelihoods are ordered exactly as the numbers ρδ\rho^{\delta}. If p<1/2p < 1/2, then p<1−pp < 1 - p and 0<ρ<10 < \rho < 1, so ρδ\rho^{\delta} strictly decreases as δ\delta grows. The largest likelihood then belongs to the smallest distance, and two codewords have equal likelihood exactly when they have equal distance. If p=1/2p = 1/2, then ρ=1\rho = 1 and every likelihood equals (1/2)n=2−n(1/2)^n = 2^{-n}. If p>1/2p > 1/2, then ρ>1\rho > 1, so ρδ\rho^{\delta} strictly increases with δ\delta and the largest likelihood belongs to the largest distance. ■\blacksquare

Channels, Signals and Likelihoods proved the first case. The other two show why the condition p<1/2p < 1/2 is there. At p=1/2p = 1/2 every codeword gives the opening word the likelihood 2−6=0.0156252^{-6} = 0.015625, so rr says nothing about what was sent and every decoder is reduced to guessing. At p=0.9p = 0.9 the farthest codeword wins, 000000000000 at distance 5, with likelihood 0.95×0.1=0.0590490.9^5 \times 0.1 = 0.059049. Inverting every bit turns BSC(0.9)\text{BSC}(0.9) into BSC(0.1)\text{BSC}(0.1), the inverted word is 000010000010, and its nearest codeword is again 000000000000. A channel worse than a coin toss is a good channel with its labels swapped, so the rest of the chapter takes p<1/2p < 1/2.

The theorem has a second reading. Receiving rr when cc was sent means that the channel produced the error pattern e=r⊕ce = r \oplus c, whose weight w(e)w(e) equals d(r,c)d(r, c). So one error pattern of weight ww has probability pw(1−p)n−wp^{w}(1-p)^{n-w}, which depends on nothing but the weight. Figure 2 plots it for n=6n = 6 and three values of pp. Below one half, light patterns are likely and heavy ones rare, so the best guess for the error is the lightest pattern that explains what was received.

Likelihood of an error pattern against its weight for three crossover probabilities weight w of the error pattern, which is the distance to the codeword likelihood, log scale 10−6 10−5 10−4 10−3 10−2 10−1 1 0 1 2 3 4 5 6 p = 0.1 p = 0.5 p = 0.8
Figure 2. The likelihood of one 6-bit error pattern of weight , which is also the likelihood of a codeword at distance , for three crossover probabilities. Below one half it falls with every extra flip, at one half it is flat, and above one half it rises. Data: computed by ch18_charts.py in the companion repository.

03.The Standard Array

The lightest-pattern guess can be worked out once, in advance, for every word the receiver could see. Groups and Cosets defined the standard array of a code closed under XOR, and Slepian gave a procedure that writes it row by row without first knowing what the cosets are [1].

For C6C_6 the first row is the code itself, 8 of the 64 words of length 6. No word of weight 1 is a codeword, because d=3d = 3, so the six words of weight 1 become the next six leaders, taken in order of increasing binary value. After those seven rows, 8 words remain.

000101, 001010, 010110, 011001, 100011, 101100, 110000, 111111.000101,\ 001010,\ 010110,\ 011001,\ 100011,\ 101100,\ 110000,\ 111111.

None has weight 1, and three of them, 000101000101, 001010001010 and 110000110000, have weight 2. The tie goes to the smallest binary value, 000101000101, and its row turns out to be exactly the eight remaining words, which completes Table 2.

Table 2. The standard array of . Each entry is the leader of its row XORed with the codeword heading its column, and the last column is the syndrome that the whole row shares

Leader ℓ\ellℓ⊕001111\ell \oplus 001111ℓ⊕010011\ell \oplus 010011ℓ⊕011100\ell \oplus 011100ℓ⊕100110\ell \oplus 100110ℓ⊕101001\ell \oplus 101001ℓ⊕110101\ell \oplus 110101ℓ⊕111010\ell \oplus 111010Syndrome
000000000000001111001111010011010011011100011100100110100110101001101001110101110101111010111010000000
000001000001001110001110010010010010011101011101100111100111101000101000110100110100111011111011001001
000010000010001101001101010001010001011110011110100100100100101011101011110111110111111000111000010010
000100000100001011001011010111010111011000011000100010100010101101101101110001110001111110111110100100
001000001000000111000111011011011011010100010100101110101110100001100001111101111101110010110010111111
010000010000011111011111000011000011001100001100110110110110111001111001100101100101101010101010011011
100000100000101111101111110011110011111100111100000110000110001001001001010101010101011010011010110110
000101000101001010001010010110010110011001011001100011100011101100101100110000110000111111111111101101

Source: reproduced by ch18_syndrome_decoding_and_the_standard_array.py.

The construction never checks that a new row repeats nothing, so that needs a proof. The coset rules of Groups and Cosets supply every step.

Proof. The row led by ℓ\ell is the set ℓ⊕C\ell \oplus C, the coset of ℓ\ell, so the coset rules apply to it. A coset has as many elements as the code, so the 2k2^k entries of a row are all different. A new leader ℓ′\ell' comes from the words not yet written, so ℓ′\ell' lies in no earlier row, while it does lie in its own coset. That coset therefore differs from every earlier row, and two cosets that differ are disjoint by the coset rules, so no entry of the new row repeats an earlier one. So the whole coset of ℓ′\ell' was still unwritten, and a lightest unwritten word is a lightest word of its coset, which makes ℓ′\ell' a coset leader in the sense of Groups and Cosets. Each row uses up 2k2^k new words, so the construction stops, and it stops only when every word is written. The rows are disjoint and each holds 2k2^k words, so there are 2n/2k=2n−k2^n / 2^k = 2^{n-k} rows, which is what Lagrange's theorem says about the number of cosets. ■\blacksquare

For C6C_6 that is 26−3=82^{6-3} = 8 rows of 8 words. The opening word 111101111101 sits in the row led by 001000001000, under the codeword 110101110101, which is the codeword the likelihoods picked.

04.Decoding with the Array

The array turns decoding into a lookup. Find the received word rr in the array and return the codeword at the top of its column. If rr sits in the row of leader ℓ\ell under the codeword cc, then r=ℓ⊕cr = \ell \oplus c, so the output is c=r⊕ℓc = r \oplus \ell, and the decoder has guessed that the error pattern was ℓ\ell. Groups and Cosets proved, in the theorem that leader decoding finds a nearest codeword, that this guess is never beaten on distance, for every code closed under XOR.

Proof. By the leader decoding theorem of Groups and Cosets, r⊕ℓr \oplus \ell is a codeword and no codeword lies closer to rr. By the theorem on likelihood against distance, for p<1/2p < 1/2 a codeword at the least distance has the largest likelihood, and codewords at equal distance have equal likelihood. So r⊕ℓr \oplus \ell has the largest likelihood, even when other codewords tie with it. ■\blacksquare

Ties are where the choice of leaders shows. Take r=000101r = 000101, the leader of the last row. Its distances to the eight codewords, in the order of the code, are 2,2,3,3,3,3,2,62, 2, 3, 3, 3, 3, 2, 6, so 000000000000, 001111001111 and 110101110101 tie for nearest, as Figure 3 shows. The array returns 000000000000, because 000101000101 leads its row and sits under 000000000000. Had 001010001010 led the row instead, the same word would have been decoded as 000101⊕001010=001111000101 \oplus 001010 = 001111. Both answers are maximum likelihood, and each is right less than one time in three when this word arrives, because the three tied codewords are equally likely and the four at distance 3 keep a small share. At p=0.1p = 0.1 each tied codeword holds 0.2903100.290310 of the total likelihood. What the array guarantees is one fixed answer, which is what hardware needs.

The eight codewords of the (6,3) code placed by their Hamming distance from the received word 000101. None lies at distance 0 or 1. Three lie at distance 2, namely 000000, 001111 and 110101, so the nearest codeword is not unique, and the standard array returns 000000. Four lie at distance 3 and one, 111010, at distance 6. 0 1 2 3 4 5 6 Hamming distance from the received word 000101 000101 received 000000 001111 110101 three-way tie 010011 011100 100110 101001 111010 a nearest codeword, tied at distance 2 the one the standard array returns a codeword farther away
Figure 3. The codewords of placed by their distance from . Three codewords tie at distance 2, so the nearest codeword is not unique, and the standard array returns because leads its row.

The column under cc is the set c⊕Lc \oplus L, where LL is the set of the 2n−k2^{n-k} leaders. Those are exactly the received words decoded to cc, called the decision region of cc. In C6C_6 each region holds its codeword, the six words at distance 1 from it and one word at distance 2, and the eight regions share out the 64 words without overlap.

The array decodes as well as any decoder can, but it costs too much as it stands. It holds all 2n2^n words, 64 for C6C_6 and 2722^{72} for a code of length 72. The next section gives each row a short name, so that the decoder can find the row without finding rr.

05.The Syndrome

Multiply the opening word by HTH^T, which forms the dot product of rr with each row of HH. The first row of HH picks out positions 1, 3 and 4, giving r1⊕r3⊕r4=1⊕1⊕1=1r_1 \oplus r_3 \oplus r_4 = 1 \oplus 1 \oplus 1 = 1. The second picks out positions 1, 2, 3 and 5, giving 1⊕1⊕1⊕0=11 \oplus 1 \oplus 1 \oplus 0 = 1, and the third picks out 2, 3 and 6, giving 1⊕1⊕1=11 \oplus 1 \oplus 1 = 1. The result 111111 is the third column of HH, and the leader 001000001000 of the row that holds 111101111101 gives the same 111111. Three bits computed from rr have found the row.

The second form is the column view of the theorem on two views of a matrix-vector product, in Matrices and Elimination over Finite Fields. It says that the syndrome is the XOR of the columns of HH in the positions where rr holds a 1. For r=111101r = 111101 that is h1⊕h2⊕h3⊕h4⊕h6=110⊕011⊕111⊕100⊕001=111h_1 \oplus h_2 \oplus h_3 \oplus h_4 \oplus h_6 = 110 \oplus 011 \oplus 111 \oplus 100 \oplus 001 = 111, which agrees with the computation row by row.

Proof. Matrix multiplication distributes over XOR, so rHT=cHT⊕eHTrH^T = cH^T \oplus eH^T. Every codeword is c=mGc = mG for some message mm, so cHT=m (GHT)=0cH^T = m\,(GH^T) = 0, using GHT=0GH^T = 0 from Linear Codes. What remains is eHTeH^T. ■\blacksquare

That is why the opening word 110101⊕001000110101 \oplus 001000 shares the syndrome of 001000001000. The converse needs one more fact, that nothing outside the code has syndrome zero.

Proof. This is the theorem that the checks define the code, proved in Linear Codes. The pair G=[ I∣P ]G = \left[\,I \mid P\,\right], H=[ PT∣I ]H = \left[\,P^T \mid I\,\right] meets its conditions. Their product is GHT=P⊕P=0GH^T = P \oplus P = 0, and each row of HH alone has a 1 in its own column of the identity block, so no set of rows adds to zero and the rank is n−kn - k. ■\blacksquare

Proof. The equation rHT=r′HTrH^T = r'H^T holds exactly when (r⊕r′)HT=0(r \oplus r')H^T = 0, by distributivity, and by the lemma that holds exactly when r⊕r′r \oplus r' is a codeword. Under XOR every word is its own inverse, so the coset rule that a∗C=b∗Ca \ast C = b \ast C exactly when a−1∗b∈Ca^{-1} \ast b \in C reads here that r⊕C=r′⊕Cr \oplus C = r' \oplus C exactly when r⊕r′∈Cr \oplus r' \in C. Equal syndromes and equal cosets are therefore the same condition. ■\blacksquare

Proof. Read in one direction, the previous theorem says that all the words of one coset share a syndrome, so the map is well defined. Read in the other, it says that two cosets with the same syndrome are the same coset, so no two cosets share a syndrome. There are 2n−k2^{n-k} cosets, by the theorem that every word appears exactly once, and 2n−k2^{n-k} possible syndromes. Different values for all 2n−k2^{n-k} cosets use up all 2n−k2^{n-k} syndromes. ■\blacksquare

The syndrome column of Table 2 shows all of this at once. Every row has its own syndrome, the eight syndromes are the eight words of three bits, and a leader with a single 1 in position jj has the syndrome hjh_j, because Equation 4 then picks out that one column.

06.The Syndrome Table

The correspondence lets the decoder keep one leader per syndrome and forget the rest of the array.

The syndrome decoder returns exactly what the standard array returns, because ℓ(s)\ell(s) is the leader of the row that holds rr. The table is the last column of the array turned into an index. Table 3 is the table for C6C_6. The six single-bit leaders sit at the six columns of HH, and the two remaining syndromes go to 000000000000 and to the leader of weight 2, 000101000101.

Table 3. The syndrome table of

Syndrome ssLeader ℓ(s)\ell(s)Error it corrects
000000000000000000none
001001000001000001position 6
010010000010000010position 5
011011010000010000position 2
100100000100000100position 4
101101000101000101positions 4 and 6
110110100000100000position 1
111111001000001000position 3

Source: reproduced by ch18_syndrome_decoding_and_the_standard_array.py.

Take the received word 100100100100. The three rows of HH give 1⊕0⊕1=01 \oplus 0 \oplus 1 = 0, then 1⊕0⊕0⊕0=11 \oplus 0 \oplus 0 \oplus 0 = 1, then 0⊕0⊕0=00 \oplus 0 \oplus 0 = 0, so s=010s = 010. The table gives the leader 000010000010, and the decoder returns 100100⊕000010=100110100100 \oplus 000010 = 100110, the codeword of message 100100. A few XORs and one table read have replaced a search through 64 words.

The best-known code to decode this way is the (7,4)(7,4) Hamming code [2], which Linear Codes drew as three overlapping circles. This chapter keeps the systematic matrices of Linear Codes, with PP holding the rows 110110, 011011, 101101 and 111111.

G=[1000110010001100101010001111],H=[101110011010100111001].G = \begin{bmatrix} 1 & 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 \end{bmatrix}, \qquad H = \begin{bmatrix} 1 & 0 & 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 1 & 0 & 0 & 1 \end{bmatrix}.

The columns of HH are 110,011,101,111,100,010,001110, 011, 101, 111, 100, 010, 001, all seven nonzero words of three bits, each used once. Of the 16 codewords, one has weight 0, seven have weight 3, seven have weight 4 and one has weight 7, so d=3d = 3. Because every nonzero syndrome is a column of HH, every nonzero syndrome belongs to a leader of weight 1, and Table 4 has no room for anything heavier.

Table 4. The syndrome table of the Hamming code

Syndrome ssLeader ℓ(s)\ell(s)Flipped position
00000000000000000000none
001001000000100000017
010010000001000000106
011011010000001000002
100100000010000001005
101101001000000100003
110110100000010000001
111111000100000010004

Source: reproduced by ch18_syndrome_decoding_and_the_standard_array.py.

The message 10011001 is sent as 10010011001001, the XOR of the first and fourth rows of GG. If bit 6 flips, then r=1001011r = 1001011, and the rows of HH give s1=r1⊕r3⊕r4⊕r5=1⊕0⊕1⊕0=0s_1 = r_1 \oplus r_3 \oplus r_4 \oplus r_5 = 1 \oplus 0 \oplus 1 \oplus 0 = 0, then s2=r1⊕r2⊕r4⊕r6=1⊕0⊕1⊕1=1s_2 = r_1 \oplus r_2 \oplus r_4 \oplus r_6 = 1 \oplus 0 \oplus 1 \oplus 1 = 1, then s3=r2⊕r3⊕r4⊕r7=0⊕0⊕1⊕1=0s_3 = r_2 \oplus r_3 \oplus r_4 \oplus r_7 = 0 \oplus 0 \oplus 1 \oplus 1 = 0. The syndrome 010010 is column 6, the table returns 00000100000010, and 1001011⊕0000010=10010011001011 \oplus 0000010 = 1001001 is the codeword sent.

Lin and Costello develop the same decoder for linear codes in general [3]. Its number of entries grows with the number of check bits n−kn - k rather than with the length nn, which makes it practical for codes with few checks.

07.Syndrome Decoding in Hardware

Each syndrome bit is an XOR of the received bits picked out by one row of HH. For the (7,4)(7,4) code each row has four 1s, and adding four bits takes three two-input XOR gates in a tree two levels deep. Figure 4 draws the three trees, nine gates in all, with the values for r=1001011r = 1001011.

The syndrome of the (7,4) Hamming code computed by three trees of two-input XOR gates. Each syndrome bit adds the received bits in the positions where its row of H holds a 1: s1 adds r1, r3, r4 and r5, s2 adds r1, r2, r4 and r6, and s3 adds r2, r3, r4 and r7. Each tree uses three gates in two levels, nine gates in all. With the received word 1001011 the syndrome is 010. r1 1 r2 0 r3 0 r4 1 r5 0 r6 1 r7 1 syndrome bit row of H s1 = 0 1011100 s2 = 1 1101010 s3 = 0 0111001
Figure 4. The syndrome of the Hamming code as three trees of two-input XOR gates, one tree for each row of . Each tree adds four received bits in two levels of gates. For the trees give .

By the theorem on the cost of an XOR tree in Linear Codes, a row with mm ones needs m−1m - 1 gates, and a balanced tree has the least depth ⌈log⁡2m⌉\lceil \log_2 m \rceil, so the delay grows slowly even for long rows. The syndrome then addresses a read-only memory, or ROM, whose word at each address is the leader. Figure 5 shows the whole decoder. The ROM has 8 words of 7 bits, holding 00000000000000, 00000010000001, 00000100000010, 01000000100000, 00001000000100, 00100000010000, 10000001000000 and 00010000001000 at the addresses 0 to 7, and seven XOR gates add the leader to rr bit by bit.

A syndrome table decoder for the (7,4) Hamming code. The received word r feeds the syndrome logic, whose 3-bit syndrome addresses a ROM of 8 words of 7 bits holding the coset leaders. The leader read out is added to r by seven XOR gates, drawn as one XOR gate on 7-bit buses, and the result is the estimate c-hat. With r = 1001011 the syndrome is 010, the leader is 0000010 and the estimate is 1001001. r syndrome logic 9 XOR gates s = 010 syndrome table ROM, 8 words of 7 bits leader 0000010 7 7 1001011 7 c 1001001
Figure 5. A syndrome table decoder for the Hamming code. The syndrome logic forms , the 3-bit syndrome addresses a ROM of 8 words of 7 bits that holds the leaders, and seven XOR gates add the leader to to form the estimate . For the syndrome is , the leader is and .

The syndrome table of the (7,4)(7,4) code holds 8×7=568 \times 7 = 56 bits. A ROM that mapped each received word straight to its 4-bit message would need 27×4=5122^7 \times 4 = 512 bits, and a stored standard array 27×7=8962^7 \times 7 = 896 bits. Memory with error correction commonly stores each 64-bit word with 8 check bits, a code of length 72 of the kind Hsiao designed for memory systems [4]. Its syndrome table has 28=2562^8 = 256 entries, while a table addressed by all 72 received bits would need 272≈4.72×10212^{72} \approx 4.72 \times 10^{21}.

For a table this small, gates can replace the ROM. The leader for ss has a 1 in position jj exactly when s=hjs = h_j, and a three-input AND gate detects that when it is fed sis_i wherever hjh_j has a 1 and the complement si′s_i' wherever hjh_j has a 0. For h6=010h_6 = 010 the gate computes e6=s1′ s2 s3′e_6 = s_1' \, s_2 \, s_3', which is 1 for the syndrome 010010 and no other. Figure 6 draws the seven gates and the three inverters that supply the complements. Leaving the inverters aside, the whole decoder is 9 XOR gates for the syndrome, 7 AND gates for the table and 7 XOR gates for the correction, 23 gates in all.

The syndrome table of the (7,4) Hamming code built from gates. Three inverters supply the complements, marked with a prime, and seven three-input AND gates each watch for one syndrome: gate j takes s_i where column j of H holds a 1 and the complement where it holds a 0, so it outputs 1 exactly when the syndrome equals column j. With s = 010 only e6 is 1. s1 0 s1' s2 1 s2' s3 0 s3' output on s = e1 = 0 110 e2 = 0 011 e3 = 0 101 e4 = 0 111 e5 = 0 100 e6 = 1 010 e7 = 0 001
Figure 6. The syndrome table of the Hamming code built from gates. Three inverters supply the complements , and , and gate outputs exactly when the syndrome equals column of . With only is 1.

The gates and the ROM compute the same function. Gates answer sooner and need no memory, while a ROM can be refilled with the leaders of another code.

08.Erasures

Some channels report a doubt along with a bit. A storage system can know which disk failed, and a network can know which packet never arrived. The receiver then knows where a bit was lost but not its value, and marks the position, called an erasure, with a question mark.

Suppose the (7,4)(7,4) codeword 10010011001001 loses its first and sixth bits, so that the receiver holds ?0010?1?0010?1. Call the unknown bits x1x_1 and x6x_6, and let u=0001001u = 0001001 be the received word with zeros in the gaps. Every word consistent with what arrived is u⊕x1δ1⊕x6δ6u \oplus x_1 \delta_1 \oplus x_6 \delta_6, where δj\delta_j has a single 1 in position jj. By the lemma that the code is the null space of HH, such a word is a codeword exactly when its syndrome uHT⊕x1h1⊕x6h6uH^T \oplus x_1 h_1 \oplus x_6 h_6 is zero. Moving uHTuH^T to the other side, which over GF(2)\mathrm{GF}(2) changes nothing, gives a linear system.

x1h1⊕x6h6=s,s=uHT.x_1 h_1 \oplus x_6 h_6 = s, \qquad s = uH^T.
(6)

Here uu has its 1s in positions 4 and 7, so s=h4⊕h7=111⊕001=110s = h_4 \oplus h_7 = 111 \oplus 001 = 110, and the coefficients are the columns h1=110h_1 = 110 and h6=010h_6 = 010. Adding the first row of the augmented matrix to the second completes the elimination.

[101111000]⟶[101010000].\left[\begin{array}{cc|c} 1 & 0 & 1 \\ 1 & 1 & 1 \\ 0 & 0 & 0 \end{array}\right] \quad\longrightarrow\quad \left[\begin{array}{cc|c} 1 & 0 & 1 \\ 0 & 1 & 0 \\ 0 & 0 & 0 \end{array}\right].

The reduced rows read x1=1x_1 = 1 and x6=0x_6 = 0, so the codeword is 10010011001001. Figure 7 shows the same computation on the columns of HH. No guessing was involved, and two erasures were filled exactly by a code that corrects only one error.

Erasure decoding on the (7,4) Hamming code. Positions 1 and 6 of the received word are lost, so only columns 1 and 6 of H carry unknowns. The known bits, with zeros in the lost places, have syndrome 110. Solving x1 h1 + x6 h6 = 110 by elimination on the augmented matrix, adding row 1 to row 2, gives x1 = 1 and x6 = 0, which restores the codeword 1001001. 1 2 3 4 5 6 7 received ? 0 0 1 0 ? 1 H 1 0 1 1 1 0 0 1 1 0 1 0 1 0 0 1 1 1 0 0 1 known bits 0001001 give the syndrome 110 solve x1 h1 + x6 h6 = 110 h1 h6 s 1 0 1 1 1 1 0 0 0 R2 + R1 h1 h6 s 1 0 1 0 1 0 0 0 0 x1 = 1, x6 = 0 recovered 1 0 0 1 0 0 1
Figure 7. Erasure decoding on the Hamming code. Positions 1 and 6 are lost, so only the columns and of carry unknowns. The known bits, with zeros in the lost places, have syndrome , and elimination on gives and , which restores .

Whether the solution is unique depends on the erased columns of HH, and the minimum distance controls those columns.

Proof. Let xx be the word with 1s exactly on SS. By Equation 4, xHTxH^T is the XOR of the columns hjh_j with j∈Sj \in S, so the first claim is the codeword test in the theorem on distance from the columns of the check matrix, in Linear Codes. For the second, the only coefficients over GF(2)\mathrm{GF}(2) are 0 and 1, so a set of columns is dependent exactly when some nonempty subset of it adds to zero. A nonempty subset SS of fewer than dd columns that added to zero would make the word with 1s on SS a nonzero codeword of weight ∣S∣<d|S| < d, which the minimum distance forbids. ■\blacksquare

Proof. Let EE be the set of erased positions, with ∣E∣=e≤d−1|E| = e \le d - 1, and let cc be the codeword sent. A solution exists, because the bits of cc in the positions of EE turn the candidate word into cc, a codeword. The coefficient matrix AA of the system has the ee columns hjh_j with j∈Ej \in E, which are independent by the lemma because e<de < d. So AA has rank ee, and by the rank theorem its null space has dimension e−e=0e - e = 0. By the theorem on solutions of a linear system in Matrices and Elimination over Finite Fields, the solution set is one particular solution plus N(A)N(A), so the solution is unique, and it is the one that cc supplies. ■\blacksquare

The bound cannot be raised. The codeword 11100001110000 has weight 3, with 1s in positions 1, 2 and 3, so h1⊕h2⊕h3=110⊕011⊕101=000h_1 \oplus h_2 \oplus h_3 = 110 \oplus 011 \oplus 101 = 000. Erase those three positions of 10010011001001. The known part is u=0001001u = 0001001, with syndrome h4⊕h7=110h_4 \oplus h_7 = 110, and the system has two solutions, (x1,x2,x3)=(1,0,0)(x_1, x_2, x_3) = (1, 0, 0) and (0,1,1)(0, 1, 1). They give 10010011001001 and 01110010111001, which agree outside the erasures and differ by 11100001110000. Both fit every received bit, so no decoder can choose between them.

Most sets of three erasures still succeed. By the lemma, three columns add to zero exactly on the support of a codeword of weight 3, its set of nonzero positions. The (7,4)(7,4) code has seven such codewords among the (73)=35\binom{7}{3} = 35 sets of three positions, so 28 sets are still recovered. For C6C_6 the four dependent triples are the supports {1,3,6}\{1, 3, 6\}, {1,4,5}\{1, 4, 5\}, {2,3,4}\{2, 3, 4\} and {2,5,6}\{2, 5, 6\} of its codewords of weight 3. In both codes four erasures always fail, and always leave exactly two candidates. Their four columns of HH are distinct nonzero words of three bits, and four such words cannot fit in a subspace of dimension 2, which holds only three nonzero words, so they span GF(2)3\mathrm{GF}(2)^3, the system has rank 3, and its null space has dimension 4−3=14 - 3 = 1. Table 5 lists the counts.

Table 5. How many sets of erased positions leave independent columns of , and so can always be filled

Code1 erasure2 erasures3 erasures4 erasures
(7,4)(7,4) Hamming code7 of 721 of 2128 of 350 of 35
C6C_66 of 615 of 1516 of 200 of 15

Source: reproduced by ch18_syndrome_decoding_and_the_standard_array.py.

The theorem is the error-free case of the bound 2t+e<d2t + e < d from Distance, Detection and Correction, and it allows two erasures in the (7,4)(7,4) code against one error. An erasure gives away its position, and finding the position is what costs an error the extra distance.

09.When Decoding Fails

A syndrome decoder returns r⊕ℓr \oplus \ell, where ℓ\ell leads the coset of rr, and Groups and Cosets showed that if r=c⊕er = c \oplus e this equals cc exactly when e=ℓe = \ell. So the decoder is right exactly when the error pattern is one of the leaders, which turns its success rate into an exact sum.

Proof. The decoder is right exactly when the error pattern equals one of the leaders, and the events e=ℓe = \ell for different leaders cannot happen together, so their probabilities add. The channel produces each error pattern of weight ww with probability pw(1−p)n−wp^{w}(1-p)^{n-w}, whatever codeword it acts on, and αw\alpha_w of the leaders have weight ww. Grouping the leaders by weight gives the sum. ■\blacksquare

For C6C_6 the leaders give α0=1\alpha_0 = 1, α1=6\alpha_1 = 6 and α2=1\alpha_2 = 1, so Pc=(1−p)6+6p(1−p)5+p2(1−p)4P_c = (1-p)^6 + 6p(1-p)^5 + p^2(1-p)^4. For the (7,4)(7,4) code, α0=1\alpha_0 = 1 and α1=7\alpha_1 = 7, and the two terms share the factor (1−p)6(1-p)^6.

Pc=(1−p)7+7p(1−p)6=(1−p)6((1−p)+7p)=(1−p)6(1+6p).P_c = (1-p)^7 + 7p(1-p)^6 = (1-p)^6 \big((1-p) + 7p\big) = (1-p)^6 (1 + 6p).
(8)

Table 6 evaluates both at three crossover probabilities, next to the probability that the same message bits arrive intact with no code at all, (1−p)3(1-p)^3 for three bits and (1−p)4(1-p)^4 for four. At p=0.01p = 0.01 the (7,4)(7,4) decoder gets a block wrong with probability 1−0.997969=0.002031 - 0.997969 = 0.00203, against 0.0394040.039404 for four bare bits.

Table 6. The probability that the message arrives correctly, with the syndrome table and with no code

Schemep=0.01p = 0.01p=0.05p = 0.05p=0.1p = 0.1
C6C_6 with its syndrome table0.9986360.9692620.892296
Three bits sent bare0.9702990.8573750.729000
(7,4)(7,4) code with its syndrome table0.9979690.9556190.850306
Four bits sent bare0.9605960.8145060.656100

Source: reproduced by ch18_syndrome_decoding_and_the_standard_array.py.

Proof. Divide Equation 8 by the probability (1−p)4(1-p)^4 for four bare bits.

R(p)=(1−p)6(1+6p)(1−p)4=(1−p)2(1+6p).R(p) = \frac{(1-p)^6 (1 + 6p)}{(1-p)^4} = (1-p)^2 (1 + 6p).
(9)

Multiplying out, R(p)=(1−2p+p2)(1+6p)=1+4p−11p2+6p3R(p) = (1 - 2p + p^2)(1 + 6p) = 1 + 4p - 11p^2 + 6p^3, so R(p)−1=p (6p2−11p+4)=p (2p−1)(3p−4)R(p) - 1 = p\,(6p^2 - 11p + 4) = p\,(2p - 1)(3p - 4), as expanding the last product confirms. On 0<p<1/20 < p < 1/2 the factor pp is positive while 2p−12p - 1 and 3p−43p - 4 are both negative, so the product is positive and R(p)>1R(p) > 1. For the largest value, the product rule gives R′(p)=−2(1−p)(1+6p)+6(1−p)2=(1−p)(4−18p)R'(p) = -2(1-p)(1+6p) + 6(1-p)^2 = (1-p)(4 - 18p). The factor 1−p1 - p is positive, so R′R' is positive below p=2/9p = 2/9 and negative above it, and RR peaks there at (7/9)2(1+12/9)=(49/81)(21/9)=1029/729=343/243(7/9)^2 (1 + 12/9) = (49/81)(21/9) = 1029/729 = 343/243. ■\blacksquare

The peak ratio 343/243≈1.411523343/243 \approx 1.411523 means that near p=0.22p = 0.22 the code is about 41 percent more likely than bare bits to deliver the message intact. At p=1/2p = 1/2 the ratio is exactly 1, and Figure 8 shows both curves meeting there at 0.06250.0625, for a reason that holds for every code.

Probability of correct decoding for the (7,4) Hamming code and for four bits sent bare crossover probability p probability of correct decoding 0.0 0.1 0.2 0.3 0.4 0.5 0.0 0.2 0.4 0.6 0.8 1.0 0.850 0.656 (7,4) code, syndrome table four bits sent bare both 0.0625 at p = 0.5
Figure 8. The probability of correct decoding for the Hamming code with its syndrome table and for four bits sent bare. At the code delivers against , and the curves meet at when . Data: computed by ch18_charts.py in the companion repository.

Proof. At p=1/2p = 1/2 every error pattern has probability 2−n2^{-n}. The decoder is right on the 2n−k2^{n-k} leaders, so Pc=2n−k⋅2−n=2−kP_c = 2^{n-k} \cdot 2^{-n} = 2^{-k}. ■\blacksquare

That is the probability of guessing a kk-bit message at random, 0.1250.125 for C6C_6 and 0.06250.0625 for the (7,4)(7,4) code. Table 6 holds pp fixed for each channel bit, so it leaves out the energy that seven channel bits cost against four, which Error-Control Strategies and Performance priced as coding gain.

For C6C_6, with d=3d = 3, the radius is t=1t = 1. Only the coset of syndrome 101101 has no leader of weight 0 or 1, so the bounded-distance decoder is the same table with that entry replaced by a flag. At p=0.1p = 0.1 it is right whenever at most one bit flips, with probability 0.531441+0.354294=0.8857350.531441 + 0.354294 = 0.885735. It flags the block when the error pattern lies in the coset of 101101, which holds three words of weight 2, four of weight 3 and one of weight 6, with probability 3×0.006561+4×0.000729+0.000001=0.0226003 \times 0.006561 + 4 \times 0.000729 + 0.000001 = 0.022600. Otherwise it is wrong, with probability 0.0916650.091665. On that syndrome the complete decoder returns r⊕000101r \oplus 000101, which is right only for the error 000101000101, with probability 0.0065610.006561, and wrong with probability 0.0160390.016039. Table 7 sets the two decoders side by side.

Table 7. Two decoders for at

DecoderCorrectFlaggedWrong
Complete, full syndrome table0.89229600.107704
Bounded distance, radius 10.8857350.0226000.091665

Source: reproduced by ch18_syndrome_decoding_and_the_standard_array.py.

The bounded decoder gives up 0.0065610.006561 of correct decodes and in exchange turns 0.0160390.016039 of wrong answers into flags. With a return channel, a flagged block can be sent again by automatic repeat request, or ARQ, so a known failure costs only time, while a wrong answer passes downstream unnoticed. Some wrong answers no decoder can flag, because the received word is itself a codeword.

Proof. By the lemma that the syndrome sees only the error, rHT=eHTrH^T = eH^T, and by the lemma on the null space, eHT=0eH^T = 0 exactly when e∈Ce \in C. A received word with zero syndrome is a codeword, so the complete decoder and the bounded-distance decoder both return it unchanged, and the output is wrong exactly when e≠0e \ne 0. Each codeword of weight ww occurs as the error pattern with probability pw(1−p)n−wp^{w}(1-p)^{n-w}, these events cannot happen together, and a nonzero codeword has weight at least dd. ■\blacksquare

For C6C_6, with four codewords of weight 3 and three of weight 4, Pu=4p3(1−p)3+3p4(1−p)2P_u = 4p^3(1-p)^3 + 3p^4(1-p)^2, which at p=0.1p = 0.1 is 4×0.000729+3×0.000081=0.0031594 \times 0.000729 + 3 \times 0.000081 = 0.003159. That much of the complete decoder's 0.1077040.107704 lay beyond the reach of any decoder. The numbers AwA_w form the weight distribution of the code, and MacWilliams showed that they determine the weight distribution of the dual code [5], which is one way such sums are found for codes too large to list.

10.Looking Ahead

The (7,4)(7,4) code had a property that C6C_6 lacked. Its parity-check matrix used every nonzero word of three bits as a column, so every nonzero syndrome pointed at one bit and no coset was left over for a heavier leader. In C6C_6 the syndrome 101101 matched no column, and its coset needed a leader of weight 2 that the decoder corrects only by luck.

The next chapter, Hamming Codes and Perfect Codes, builds the first kind of matrix for every number mm of check bits, letting the columns run through all 2m−12^m - 1 nonzero words of mm bits. It then counts how many words lie within the correction radius of each codeword, which leads to the sphere-packing bound, and asks when those spheres fill the whole space with nothing left over. The codes that manage it are called perfect.

11.Worked Examples

12.Exercises

References

  1. [1]Slepian, David (1956). “A Class of Binary Signaling Alphabets.” Bell System Technical Journal, 35(1), pp. 203–234. doi:10.1002/j.1538-7305.1956.tb02379.x
  2. [2]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
  3. [3]Lin, Shu and Costello, Jr., Daniel J. (2004). “Error Control Coding: Fundamentals and Applications.” 2nd edition. Pearson Prentice Hall.
  4. [4]Hsiao, M. Y. (1970). “A Class of Optimal Minimum Odd-weight-column SEC-DED Codes.” IBM Journal of Research and Development, 14(4), pp. 395–401. doi:10.1147/rd.144.0395
  5. [5]MacWilliams, Jessie (1963). “A Theorem on the Distribution of Weights in a Systematic Code.” Bell System Technical Journal, 42(1), pp. 79–94. doi:10.1002/j.1538-7305.1963.tb04003.x

— Anirban

Hardware–software at the seam where compilers meet microcode.

FeedbackBook modePaper
error-correction-codinglinear-block-codes