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 111101. 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.1, independently of the others. The word 111101 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 111101. 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 G and a parity-check matrix H with GHT=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 C5. 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=rHT always names the coset of the received word. The array then shrinks to a table of 2n−k entries, built from XOR gates and a small memory. The same columns of H recover erased bits, and the coset leaders give the exact probability that the decoder is right.
The code behind the opening word has length n=6 and carries k=3 message bits, a (6,3) code called C6 in this chapter. Its generator matrix has the systematic form [I∣P] of Linear Codes, and its parity-check matrix has the matching form [PT∣I]. It is not the code of the same name in the exercises of Linear Codes, whose generator rows are 100011, 010101 and 001110.
Their weights are 0,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=3. Suppose the message 110 was sent as 110101 and the third bit flipped. The receiver sees r=111101 and has to work backward from it.
The channel is the binary symmetric channel BSC(p) of Channels, Signals and Likelihoods. Each bit arrives unchanged with probability 1−p and flipped with probability p, 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 e to the codeword, and r=c⊕e with a 1 in e at every flipped position.
Figure 1. The binary symmetric channel BSC(p). Each bit arrives unchanged with probability 1−p and flipped with probability p, independently of every other bit. Sending 110101 and flipping position 3 is the same as adding the error pattern 001000 to the codeword.
Fix a codeword c. The words r and c differ in d(r,c) positions, where d is the Hamming distance of Distance, Detection and Correction, and each of those bits must have flipped, with probability p. Each of the other n−d(r,c) bits must have come through, with probability 1−p. The bits are independent, so the probabilities multiply.
P(r∣c)=pd(r,c)(1−p)n−d(r,c).
(1)
The number P(r∣c) is called the likelihood of c. It is the probability of what was seen, computed as if c had been sent. Table 1 lists the distance and the likelihood of every codeword for r=111101 and p=0.1.
Table 1. The eight codewords of C6 with their distance from r=111101 and their likelihood at p=0.1
Message
Codeword c
d(r,c)
P(r∣c)
000
000000
5
0.000009
001
001111
3
0.000729
010
010011
4
0.000081
011
011100
2
0.006561
100
100110
4
0.000081
101
101001
2
0.006561
110
110101
1
0.059049
111
111010
3
0.000729
Source: reproduced by ch18_syndrome_decoding_and_the_standard_array.py.
The codeword 110101, at distance 1, has likelihood 0.1×0.95=0.059049. Each extra unit of distance trades a factor 0.9 for a factor 0.1, which divides the likelihood by 9.
A likelihood is not yet the probability that c was sent. That probability, written P(c∣r), comes from Bayes' rule. When the sender picks each of the 2k messages with the same probability 2−k, the equal prior factors P(c) cancel.
The eight likelihoods add up to 0.073800, so P(110101∣111101)=0.059049/0.073800=0.800122. A receiver that answers 110101 is right four times in five when this word arrives, and every other codeword holds a smaller share.
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) and pull the factor (1−p)n out of Equation 1.
P(r∣c)=(1−p)n(1−pp)δ=(1−p)nρδ,ρ=1−pp.
(3)
The factor (1−p)n is positive and the same for every codeword, so the likelihoods are ordered exactly as the numbers ρδ. If p<1/2, then p<1−p and 0<ρ<1, so ρδ strictly decreases as δ 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/2, then ρ=1 and every likelihood equals (1/2)n=2−n. If p>1/2, then ρ>1, so ρδ strictly increases with δ and the largest likelihood belongs to the largest distance. ■
Channels, Signals and Likelihoods proved the first case. The other two show why the condition p<1/2 is there. At p=1/2 every codeword gives the opening word the likelihood 2−6=0.015625, so r says nothing about what was sent and every decoder is reduced to guessing. At p=0.9 the farthest codeword wins, 000000 at distance 5, with likelihood 0.95×0.1=0.059049. Inverting every bit turns BSC(0.9) into BSC(0.1), the inverted word is 000010, and its nearest codeword is again 000000. A channel worse than a coin toss is a good channel with its labels swapped, so the rest of the chapter takes p<1/2.
The theorem has a second reading. Receiving r when c was sent means that the channel produced the error pattern e=r⊕c, whose weight w(e) equals d(r,c). So one error pattern of weight w has probability pw(1−p)n−w, which depends on nothing but the weight. Figure 2 plots it for n=6 and three values of p. 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.
Figure 2. The likelihood pw(1−p)6−w of one 6-bit error pattern of weight w, which is also the likelihood of a codeword at distance w, 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.
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 C6 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=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.
None has weight 1, and three of them, 000101, 001010 and 110000, have weight 2. The tie goes to the smallest binary value, 000101, and its row turns out to be exactly the eight remaining words, which completes Table 2.
Table 2. The standard array of C6. 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 ℓ
ℓ⊕001111
ℓ⊕010011
ℓ⊕011100
ℓ⊕100110
ℓ⊕101001
ℓ⊕110101
ℓ⊕111010
Syndrome
000000
001111
010011
011100
100110
101001
110101
111010
000
000001
001110
010010
011101
100111
101000
110100
111011
001
000010
001101
010001
011110
100100
101011
110111
111000
010
000100
001011
010111
011000
100010
101101
110001
111110
100
001000
000111
011011
010100
101110
100001
111101
110010
111
010000
011111
000011
001100
110110
111001
100101
101010
011
100000
101111
110011
111100
000110
001001
010101
011010
110
000101
001010
010110
011001
100011
101100
110000
111111
101
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 ℓ is the set ℓ⊕C, the coset of ℓ, so the coset rules apply to it. A coset has as many elements as the code, so the 2k entries of a row are all different. A new leader ℓ′ comes from the words not yet written, so ℓ′ 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 ℓ′ was still unwritten, and a lightest unwritten word is a lightest word of its coset, which makes ℓ′ a coset leader in the sense of Groups and Cosets. Each row uses up 2k new words, so the construction stops, and it stops only when every word is written. The rows are disjoint and each holds 2k words, so there are 2n/2k=2n−k rows, which is what Lagrange's theorem says about the number of cosets. ■
For C6 that is 26−3=8 rows of 8 words. The opening word 111101 sits in the row led by 001000, under the codeword 110101, which is the codeword the likelihoods picked.
The array turns decoding into a lookup. Find the received word r in the array and return the codeword at the top of its column. If r sits in the row of leader ℓ under the codeword c, then r=ℓ⊕c, so the output is c=r⊕ℓ, and the decoder has guessed that the error pattern was ℓ. 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⊕ℓ is a codeword and no codeword lies closer to r. By the theorem on likelihood against distance, for p<1/2 a codeword at the least distance has the largest likelihood, and codewords at equal distance have equal likelihood. So r⊕ℓ has the largest likelihood, even when other codewords tie with it. ■
Ties are where the choice of leaders shows. Take r=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,6, so 000000, 001111 and 110101 tie for nearest, as Figure 3 shows. The array returns 000000, because 000101 leads its row and sits under 000000. Had 001010 led the row instead, the same word would have been decoded as 000101⊕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.1 each tied codeword holds 0.290310 of the total likelihood. What the array guarantees is one fixed answer, which is what hardware needs.
Figure 3. The codewords of C6 placed by their distance from r=000101. Three codewords tie at distance 2, so the nearest codeword is not unique, and the standard array returns 000000 because 000101 leads its row.
The column under c is the set c⊕L, where L is the set of the 2n−k leaders. Those are exactly the received words decoded to c, called the decision region of c. In C6 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 2n words, 64 for C6 and 272 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 r.
Multiply the opening word by HT, which forms the dot product of r with each row of H. The first row of H picks out positions 1, 3 and 4, giving r1⊕r3⊕r4=1⊕1⊕1=1. The second picks out positions 1, 2, 3 and 5, giving 1⊕1⊕1⊕0=1, and the third picks out 2, 3 and 6, giving 1⊕1⊕1=1. The result 111 is the third column of H, and the leader 001000 of the row that holds 111101 gives the same 111. Three bits computed from r 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 H in the positions where r holds a 1. For r=111101 that is h1⊕h2⊕h3⊕h4⊕h6=110⊕011⊕111⊕100⊕001=111, which agrees with the computation row by row.
Proof. Matrix multiplication distributes over XOR, so rHT=cHT⊕eHT. Every codeword is c=mG for some message m, so cHT=m(GHT)=0, using GHT=0 from Linear Codes. What remains is eHT. ■
That is why the opening word 110101⊕001000 shares the syndrome of 001000. 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], H=[PT∣I] meets its conditions. Their product is GHT=P⊕P=0, and each row of H 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−k. ■
Proof. The equation rHT=r′HT holds exactly when (r⊕r′)HT=0, by distributivity, and by the lemma that holds exactly when r⊕r′ is a codeword. Under XOR every word is its own inverse, so the coset rule that a∗C=b∗C exactly when a−1∗b∈C reads here that r⊕C=r′⊕C exactly when r⊕r′∈C. Equal syndromes and equal cosets are therefore the same condition. ■
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−k cosets, by the theorem that every word appears exactly once, and 2n−k possible syndromes. Different values for all 2n−k cosets use up all 2n−k syndromes. ■
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 j has the syndrome hj, because Equation 4 then picks out that one column.
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) is the leader of the row that holds r. The table is the last column of the array turned into an index. Table 3 is the table for C6. The six single-bit leaders sit at the six columns of H, and the two remaining syndromes go to 000000 and to the leader of weight 2, 000101.
Table 3. The syndrome table of C6
Syndrome s
Leader ℓ(s)
Error it corrects
000
000000
none
001
000001
position 6
010
000010
position 5
011
010000
position 2
100
000100
position 4
101
000101
positions 4 and 6
110
100000
position 1
111
001000
position 3
Source: reproduced by ch18_syndrome_decoding_and_the_standard_array.py.
Take the received word 100100. The three rows of H give 1⊕0⊕1=0, then 1⊕0⊕0⊕0=1, then 0⊕0⊕0=0, so s=010. The table gives the leader 000010, and the decoder returns 100100⊕000010=100110, the codeword of message 100. 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) Hamming code [2], which Linear Codes drew as three overlapping circles. This chapter keeps the systematic matrices of Linear Codes, with P holding the rows 110, 011, 101 and 111.
The columns of H are 110,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=3. Because every nonzero syndrome is a column of H, 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 (7,4) Hamming code
Syndrome s
Leader ℓ(s)
Flipped position
000
0000000
none
001
0000001
7
010
0000010
6
011
0100000
2
100
0000100
5
101
0010000
3
110
1000000
1
111
0001000
4
Source: reproduced by ch18_syndrome_decoding_and_the_standard_array.py.
The message 1001 is sent as 1001001, the XOR of the first and fourth rows of G. If bit 6 flips, then r=1001011, and the rows of H give s1=r1⊕r3⊕r4⊕r5=1⊕0⊕1⊕0=0, then s2=r1⊕r2⊕r4⊕r6=1⊕0⊕1⊕1=1, then s3=r2⊕r3⊕r4⊕r7=0⊕0⊕1⊕1=0. The syndrome 010 is column 6, the table returns 0000010, and 1001011⊕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−k rather than with the length n, which makes it practical for codes with few checks.
Each syndrome bit is an XOR of the received bits picked out by one row of H. For the (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=1001011.
Figure 4. The syndrome of the (7,4) Hamming code as three trees of two-input XOR gates, one tree for each row of H. Each tree adds four received bits in two levels of gates. For r=1001011 the trees give s=010.
By the theorem on the cost of an XOR tree in Linear Codes, a row with m ones needs m−1 gates, and a balanced tree has the least depth ⌈log2m⌉, 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 0000000, 0000001, 0000010, 0100000, 0000100, 0010000, 1000000 and 0001000 at the addresses 0 to 7, and seven XOR gates add the leader to r bit by bit.
Figure 5. A syndrome table decoder for the (7,4) Hamming code. The syndrome logic forms s=rHT, 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 r to form the estimate c^. For r=1001011 the syndrome is 010, the leader is 0000010 and c^=1001001.
The syndrome table of the (7,4) code holds 8×7=56 bits. A ROM that mapped each received word straight to its 4-bit message would need 27×4=512 bits, and a stored standard array 27×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=256 entries, while a table addressed by all 72 received bits would need 272≈4.72×1021.
For a table this small, gates can replace the ROM. The leader for s has a 1 in position j exactly when s=hj, and a three-input AND gate detects that when it is fed si wherever hj has a 1 and the complement si′ wherever hj has a 0. For h6=010 the gate computes e6=s1′s2s3′, which is 1 for the syndrome 010 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.
Figure 6. The syndrome table of the (7,4) Hamming code built from gates. Three inverters supply the complements s1′, s2′ and s3′, and gate j outputs ej=1 exactly when the syndrome equals column j of H. With s=010 only e6 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.
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) codeword 1001001 loses its first and sixth bits, so that the receiver holds ?0010?1. Call the unknown bits x1 and x6, and let u=0001001 be the received word with zeros in the gaps. Every word consistent with what arrived is u⊕x1δ1⊕x6δ6, where δj has a single 1 in position j. By the lemma that the code is the null space of H, such a word is a codeword exactly when its syndrome uHT⊕x1h1⊕x6h6 is zero. Moving uHT to the other side, which over GF(2) changes nothing, gives a linear system.
x1h1⊕x6h6=s,s=uHT.
(6)
Here u has its 1s in positions 4 and 7, so s=h4⊕h7=111⊕001=110, and the coefficients are the columns h1=110 and h6=010. Adding the first row of the augmented matrix to the second completes the elimination.
110010110⟶100010100.
The reduced rows read x1=1 and x6=0, so the codeword is 1001001. Figure 7 shows the same computation on the columns of H. No guessing was involved, and two erasures were filled exactly by a code that corrects only one error.
Figure 7. Erasure decoding on the (7,4) Hamming code. Positions 1 and 6 are lost, so only the columns h1 and h6 of H carry unknowns. The known bits, with zeros in the lost places, have syndrome 110, and elimination on x1h1⊕x6h6=110 gives x1=1 and x6=0, which restores 1001001.
Whether the solution is unique depends on the erased columns of H, and the minimum distance controls those columns.
Proof. Let x be the word with 1s exactly on S. By Equation 4, xHT is the XOR of the columns hj with j∈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) are 0 and 1, so a set of columns is dependent exactly when some nonempty subset of it adds to zero. A nonempty subset S of fewer than d columns that added to zero would make the word with 1s on S a nonzero codeword of weight ∣S∣<d, which the minimum distance forbids. ■
Proof. Let E be the set of erased positions, with ∣E∣=e≤d−1, and let c be the codeword sent. A solution exists, because the bits of c in the positions of E turn the candidate word into c, a codeword. The coefficient matrix A of the system has the e columns hj with j∈E, which are independent by the lemma because e<d. So A has rank e, and by the rank theorem its null space has dimension e−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), so the solution is unique, and it is the one that c supplies. ■
The bound cannot be raised. The codeword 1110000 has weight 3, with 1s in positions 1, 2 and 3, so h1⊕h2⊕h3=110⊕011⊕101=000. Erase those three positions of 1001001. The known part is u=0001001, with syndrome h4⊕h7=110, and the system has two solutions, (x1,x2,x3)=(1,0,0) and (0,1,1). They give 1001001 and 0111001, which agree outside the erasures and differ by 1110000. 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) code has seven such codewords among the (37)=35 sets of three positions, so 28 sets are still recovered. For C6 the four dependent triples are the supports {1,3,6}, {1,4,5}, {2,3,4} and {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 H 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, the system has rank 3, and its null space has dimension 4−3=1. Table 5 lists the counts.
Table 5. How many sets of erased positions leave independent columns of H, and so can always be filled
Code
1 erasure
2 erasures
3 erasures
4 erasures
(7,4) Hamming code
7 of 7
21 of 21
28 of 35
0 of 35
C6
6 of 6
15 of 15
16 of 20
0 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<d from Distance, Detection and Correction, and it allows two erasures in the (7,4) code against one error. An erasure gives away its position, and finding the position is what costs an error the extra distance.
A syndrome decoder returns r⊕ℓ, where ℓ leads the coset of r, and Groups and Cosets showed that if r=c⊕e this equals c exactly when e=ℓ. 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=ℓ for different leaders cannot happen together, so their probabilities add. The channel produces each error pattern of weight w with probability pw(1−p)n−w, whatever codeword it acts on, and αw of the leaders have weight w. Grouping the leaders by weight gives the sum. ■
For C6 the leaders give α0=1, α1=6 and α2=1, so Pc=(1−p)6+6p(1−p)5+p2(1−p)4. For the (7,4) code, α0=1 and α1=7, and the two terms share the factor (1−p)6.
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 for three bits and (1−p)4 for four. At p=0.01 the (7,4) decoder gets a block wrong with probability 1−0.997969=0.00203, against 0.039404 for four bare bits.
Table 6. The probability that the message arrives correctly, with the syndrome table and with no code
Scheme
p=0.01
p=0.05
p=0.1
C6 with its syndrome table
0.998636
0.969262
0.892296
Three bits sent bare
0.970299
0.857375
0.729000
(7,4) code with its syndrome table
0.997969
0.955619
0.850306
Four bits sent bare
0.960596
0.814506
0.656100
Source: reproduced by ch18_syndrome_decoding_and_the_standard_array.py.
Proof. Divide Equation 8 by the probability (1−p)4 for four bare bits.
R(p)=(1−p)4(1−p)6(1+6p)=(1−p)2(1+6p).
(9)
Multiplying out, R(p)=(1−2p+p2)(1+6p)=1+4p−11p2+6p3, so R(p)−1=p(6p2−11p+4)=p(2p−1)(3p−4), as expanding the last product confirms. On 0<p<1/2 the factor p is positive while 2p−1 and 3p−4 are both negative, so the product is positive and R(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). The factor 1−p is positive, so R′ is positive below p=2/9 and negative above it, and R peaks there at (7/9)2(1+12/9)=(49/81)(21/9)=1029/729=343/243. ■
The peak ratio 343/243≈1.411523 means that near p=0.22 the code is about 41 percent more likely than bare bits to deliver the message intact. At p=1/2 the ratio is exactly 1, and Figure 8 shows both curves meeting there at 0.0625, for a reason that holds for every code.
Figure 8. The probability of correct decoding for the (7,4) Hamming code with its syndrome table and for four bits sent bare. At p=0.1 the code delivers 0.850 against 0.656, and the curves meet at 0.0625 when p=1/2. Data: computed by ch18_charts.py in the companion repository.
Proof. At p=1/2 every error pattern has probability 2−n. The decoder is right on the 2n−k leaders, so Pc=2n−k⋅2−n=2−k. ■
That is the probability of guessing a k-bit message at random, 0.125 for C6 and 0.0625 for the (7,4) code. Table 6 holds p 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 C6, with d=3, the radius is t=1. Only the coset of syndrome 101 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.1 it is right whenever at most one bit flips, with probability 0.531441+0.354294=0.885735. It flags the block when the error pattern lies in the coset of 101, 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.022600. Otherwise it is wrong, with probability 0.091665. On that syndrome the complete decoder returns r⊕000101, which is right only for the error 000101, with probability 0.006561, and wrong with probability 0.016039. Table 7 sets the two decoders side by side.
Table 7. Two decoders for C6 at p=0.1
Decoder
Correct
Flagged
Wrong
Complete, full syndrome table
0.892296
0
0.107704
Bounded distance, radius 1
0.885735
0.022600
0.091665
Source: reproduced by ch18_syndrome_decoding_and_the_standard_array.py.
The bounded decoder gives up 0.006561 of correct decodes and in exchange turns 0.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=eHT, and by the lemma on the null space, eHT=0 exactly when e∈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=0. Each codeword of weight w occurs as the error pattern with probability pw(1−p)n−w, these events cannot happen together, and a nonzero codeword has weight at least d. ■
For C6, with four codewords of weight 3 and three of weight 4, Pu=4p3(1−p)3+3p4(1−p)2, which at p=0.1 is 4×0.000729+3×0.000081=0.003159. That much of the complete decoder's 0.107704 lay beyond the reach of any decoder. The numbers Aw 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.
The (7,4) code had a property that C6 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 C6 the syndrome 101 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 m of check bits, letting the columns run through all 2m−1 nonzero words of m 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.
[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]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]Lin, Shu and Costello, Jr., Daniel J. (2004). “Error Control Coding: Fundamentals and Applications.” 2nd edition. Pearson Prentice Hall.
[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]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.