Paper
Part IILinear Block Codes

Golay Codes

November 16, 202653 min readbeginner

Twelve message bits, 24 coded bits and any three errors corrected. The chapter builds the binary and ternary Golay codes, proves their distances and weight distributions, and decodes the binary code by hand and in gates.

Twelve message bits, eleven check bits, and any three of the 23 bits allowed to flip. Hamming Codes and Perfect Codes showed that a binary code meeting that demand would leave no word of length 23 to spare. Marcel Golay published such a code in 1949, in a short note that also gave a ternary code of length 11 that corrects two errors [1].

The chapter builds all four Golay codes from one small matrix each, proves their distances and weight distributions, and decodes the binary code by hand and in gates, before turning to the Voyager spacecraft.

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

01.Twelve Bits That Fill a Space

Hamming Codes and Perfect Codes counted the ball of radius 3 around a binary word of length 23, the words that differ from it in three places or fewer, and found 211=20482^{11} = 2048 of them. A code that corrects every pattern of three errors needs those balls to be disjoint, because a received word lying in two balls could have come from either center. So a 23-bit code of that kind holds at most 2122^{12} codewords, and at exactly 2122^{12} the balls cover all 2232^{23} words with none left over. The same count for ternary words of length 11 gives balls of radius 2 holding 35=2433^5 = 243 words, so 363^6 codewords would fill all 3113^{11}. The counts say what a perfect code would need, not that one exists.

Four codes come out of the construction, and Table 1 lists them. Two are perfect, the binary (23,12,7)(23, 12, 7) code and the ternary (11,6,5)(11, 6, 5) code. The other two, the extended codes, are one coordinate longer and one unit of distance further apart. The extended codes have the cleaner structure, so the chapter builds them first and reaches each perfect code by deleting a coordinate, as Figure 1 draws.

Table 1. The four Golay codes, with the field their symbols come from, the length n, the message length k, the minimum distance d, the errors corrected, the number of codewords and the property that sets each apart

CodeFieldnnkkddCorrectsCodewordsProperty
G24\mathcal{G}_{24}, extended binaryGF(2)\mathrm{GF}(2)241283 errors4,096self-dual
G23\mathcal{G}_{23}, perfect binaryGF(2)\mathrm{GF}(2)231273 errors4,096perfect
G12\mathcal{G}_{12}, extended ternaryGF(3)\mathrm{GF}(3)12662 errors729self-dual
G11\mathcal{G}_{11}, perfect ternaryGF(3)\mathrm{GF}(3)11652 errors729perfect

Source: reproduced by ch25_golay_codes.py.

The four Golay codes. Puncturing the extended binary code (24,12,8) gives the perfect binary code (23,12,7), and puncturing the extended ternary code (12,6,6) gives the perfect ternary code (11,6,5). Extending the perfect binary code with an overall parity bit gives (24,12,8) back, and appending a weighted check digit to the perfect ternary code gives (12,6,6) back. extended codes, self-dual perfect codes extended binary code perfect binary code extended ternary code perfect ternary code G24= (24, 12, 8) G23= (23, 12, 7) G12= (12, 6, 6) G11= (11, 6, 5) self-dual, 4096 codewords perfect, corrects 3 errors self-dual, 729 codewords perfect, corrects 2 errors puncture extend puncture weighted check binary above, ternary below
Figure 1. The four Golay codes. Puncturing an extended code, which deletes one coordinate, gives the perfect code beside it. An overall parity bit takes the perfect binary code back to the extended one, and the ternary code needs a weighted check digit instead.

02.Building the Matrix B

The binary construction starts from arithmetic modulo 11. Squaring 1 to 5 and reducing modulo 11 gives 11, 44, 99, 16≡516 \equiv 5 and 25≡325 \equiv 3. The squares of 6 to 10 repeat these, because (11−x)2≡x2(mod11)(11 - x)^2 \equiv x^2 \pmod{11}. The nonzero squares modulo 11 are therefore {1,3,4,5,9}\{1, 3, 4, 5, 9\}, half of the ten nonzero residues, and adding 0 to them gives the set

S={0,1,3,4,5,9}.S = \{0, 1, 3, 4, 5, 9\}.
(1)

Row 0 of an 11-column pattern puts a 1 in each column whose number lies in SS, which gives 1101110001011011100010 with column 0 first. Each later row is the row above shifted one place to the left, the bit that falls off the left end coming back in on the right, so row 1 is 1011100010110111000101. A left shift by ii places moves column jj to column j−ij - i modulo 11, so row ii has a 1 in column jj exactly when (i+j) mod 11(i + j) \bmod 11 lies in SS. For row 1 that is the set S−1={10,0,2,3,4,8}S - 1 = \{10, 0, 2, 3, 4, 8\}, exactly the places of the 1s in 1011100010110111000101.

The matrix BB borders these 11 rows with a column of 1s on the right and a row of eleven 1s below, with a 0 where the two meet.

B=[110111000101101110001011011100010111111000101101110001011011100010110111000101101111001011011101010110111001101101110001011011100011111111111110].B = \left[\begin{array}{ccccccccccc|c} 1&1&0&1&1&1&0&0&0&1&0&1\\ 1&0&1&1&1&0&0&0&1&0&1&1\\ 0&1&1&1&0&0&0&1&0&1&1&1\\ 1&1&1&0&0&0&1&0&1&1&0&1\\ 1&1&0&0&0&1&0&1&1&0&1&1\\ 1&0&0&0&1&0&1&1&0&1&1&1\\ 0&0&0&1&0&1&1&0&1&1&1&1\\ 0&0&1&0&1&1&0&1&1&1&0&1\\ 0&1&0&1&1&0&1&1&1&0&0&1\\ 1&0&1&1&0&1&1&1&0&0&0&1\\ 0&1&1&0&1&1&1&0&0&0&1&1\\ \hline 1&1&1&1&1&1&1&1&1&1&1&0 \end{array}\right].
(2)

Rows 0 to 10 have weight 7, six 1s from SS and one from the border, and row 11 has weight 11. Write bib_i for row ii of BB, a word of 12 bits, so that b0=110111000101b_0 = 110111000101 and b11=111111111110b_{11} = 111111111110.

Row ii of GG is gi=(ui,bi)g_i = (u_i, b_i), where uiu_i is the 12-bit unit word with its only 1 in place ii. Coordinates 0 to 11 of a codeword carry the message and coordinates 12 to 23 carry the checks, with coordinate 12+j12 + j under column jj of BB. Places are numbered from 0 here, where Modifying and Combining Codes numbered them from 1. Figure 2 draws all of GG as a grid of cells.

The generator matrix of the extended binary Golay code as a 12 by 24 grid, the identity on the left and the matrix B on the right, every row of weight 8 or 12 message part, the identity check part, the matrix B column 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 weight row 0 8 row 1 8 row 2 8 row 3 8 row 4 8 row 5 8 row 6 8 row 7 8 row 8 8 row 9 8 row 10 8 row 11 12 a 1 of the identity a 1 of B a 0 the 11 by 11 block drawn from the squares modulo 11 column 23 and row 11 border it, with a 0 where they meet
Figure 2. The generator matrix of the extended binary Golay code, with the identity on the left and the matrix B on the right. Rows 0 to 10 have weight 8 and row 11 has weight 12. Data: drawn by ch25_charts.py from the matrix B of ch25_golay_codes.py.

To encode the message m=101000000000m = 101000000000, add rows 0 and 2 of GG, since mm has its 1s in places 0 and 2. The message part is mm itself, and the check part is b0⊕b2b_0 \oplus b_2, worked one column at a time.

b0110111000101b2011100010111b0⊕b2101011010010\begin{array}{rl} b_0 & 110111000101 \\ b_2 & 011100010111 \\ \hline b_0 \oplus b_2 & 101011010010 \end{array}

The codeword is (101000000000,101011010010)(101000000000, 101011010010), of weight 2+6=82 + 6 = 8.

Proof. Inside the 11×1111 \times 11 block, the entry in row ii and column jj is 1 exactly when (i+j) mod 11(i + j) \bmod 11 lies in SS. The sum i+ji + j does not change when ii and jj trade places, so the entry in row jj and column ii is the same. The border is symmetric too, because column 11 holds 1s in rows 0 to 10 and row 11 holds 1s in columns 0 to 10, and the corner 0 lies on the diagonal. ■\blacksquare

03.Rows That Meet in Pairs

Rows 0 and 1 of BB have their 1s in columns {0,1,3,4,5,9,11}\{0, 1, 3, 4, 5, 9, 11\} and {0,2,3,4,8,10,11}\{0, 2, 3, 4, 8, 10, 11\}, so they share the four columns {0,3,4,11}\{0, 3, 4, 11\}. Write x∧yx \wedge y for the word with a 1 wherever both xx and yy have one. Over GF(2)\mathrm{GF}(2) the inner product x⋅yx \cdot y is the number of shared 1s taken modulo 2, w(x∧y) mod 2w(x \wedge y) \bmod 2, so b0⋅b1=4 mod 2=0b_0 \cdot b_1 = 4 \bmod 2 = 0, while b0⋅b0=7 mod 2=1b_0 \cdot b_0 = 7 \bmod 2 = 1.

Proof. Entry (i,i′)(i, i') of BBTBB^{\mathsf T} is bi⋅bi′b_i \cdot b_{i'}. On the diagonal the count of shared 1s is the weight of the row, 7 or 11, both odd, so every diagonal entry is 1.

Take two different rows ii and i′i' among rows 0 to 10. In columns 0 to 10 their 1s lie on the sets S−iS - i and S−i′S - i'. Adding ii to every element of both sets only renames the columns, and it turns them into (S−i)+i=S(S - i) + i = S and (S−i′)+i=S−(i′−i)=S−t(S - i') + i = S - (i' - i) = S - t, with t=(i′−i) mod 11t = (i' - i) \bmod 11. For i=1i = 1 and i′=2i' = 2, the sets {10,0,2,3,4,8}\{10, 0, 2, 3, 4, 8\} and {9,10,1,2,3,7}\{9, 10, 1, 2, 3, 7\} become SS and S−1S - 1. So the pair shares as many elements as SS and S−tS - t do. Adding tt to both of those shows that S−tS - t and S+t=S−(11−t)S + t = S - (11 - t) meet SS in equally many elements, so only t=1t = 1 to 5 need checking, and Table 2 checks them. Each shift leaves three shared elements in columns 0 to 10, and both rows also have a 1 in column 11, so they share 3+1=43 + 1 = 4 columns and the entry is 0. The 55 pairs among rows 0 to 10 fall into the five shift classes, 11 pairs to a class, so the table covers every one of them.

Row 11 has 1s in columns 0 to 10 and a 0 in column 11, while row i≤10i \le 10 has six 1s in columns 0 to 10 and its seventh in column 11. The two share six columns, again an even number. Every entry off the diagonal is 0, so BBT=I12BB^{\mathsf T} = I_{12}, and since BT=BB^{\mathsf T} = B this says B2=I12B^2 = I_{12}. ■\blacksquare

Table 2. The elements the set S shares with each shift S minus t, for t from 1 to 5, with the pairs of rows of B that each shift covers and the 1s those rows share

Shift ttS−tS - tS∩(S−t)S \cap (S - t)Rows, for exampleShared in columns 0 to 10With column 11
1{10,0,2,3,4,8}\{10, 0, 2, 3, 4, 8\}{0,3,4}\{0, 3, 4\}0 and 1, 0 and 1034
2{9,10,1,2,3,7}\{9, 10, 1, 2, 3, 7\}{1,3,9}\{1, 3, 9\}0 and 2, 0 and 934
3{8,9,0,1,2,6}\{8, 9, 0, 1, 2, 6\}{0,1,9}\{0, 1, 9\}0 and 3, 0 and 834
4{7,8,10,0,1,5}\{7, 8, 10, 0, 1, 5\}{0,1,5}\{0, 1, 5\}0 and 4, 0 and 734
5{6,7,9,10,0,4}\{6, 7, 9, 10, 0, 4\}{0,4,9}\{0, 4, 9\}0 and 5, 0 and 634

Source: reproduced by ch25_golay_codes.py.

Figure 3 lays rows 1 to 5 and row 11 against row 0 and marks the cells each shares with it.

Rows 1 to 5 and row 11 of the matrix B compared with row 0: rows 1 to 5 share three 1s in the first eleven columns and one in the last, row 11 shares six column 0 1 2 3 4 5 6 7 8 9 10 11 shared 1s shift row 0 1 1 0 1 1 1 0 0 0 1 0 1 the reference row row 1 1 0 1 1 1 0 0 0 1 0 1 1 3 + 1 = 4 1 row 2 0 1 1 1 0 0 0 1 0 1 1 1 3 + 1 = 4 2 row 3 1 1 1 0 0 0 1 0 1 1 0 1 3 + 1 = 4 3 row 4 1 1 0 0 0 1 0 1 1 0 1 1 3 + 1 = 4 4 row 5 1 0 0 0 1 0 1 1 0 1 1 1 3 + 1 = 4 5 row 11 1 1 1 1 1 1 1 1 1 1 1 0 6 + 0 = 6 border Each count adds the shared 1s in columns 0 to 10 to those in column 11. Every count is even, so B times B is 0 off the diagonal, modulo 2. a 1 the row shares with row 0
Figure 3. Rows 1 to 5 and row 11 of B laid against row 0. Every shared count is even, so row 0 is orthogonal to each of them. Data: drawn by ch25_charts.py from the rows of B in ch25_golay_codes.py.

Shared counts also measure distance, through the weight of a sum proved in Modifying and Combining Codes. Each place where both words have a 1 becomes a 0 in their sum and costs two 1s, so

w(x⊕y)=w(x)+w(y)−2 w(x∧y).w(x \oplus y) = w(x) + w(y) - 2\,w(x \wedge y).
(3)

The distance between xx and yy, the number of places where they differ, is w(x⊕y)w(x \oplus y).

Proof. For two rows among rows 0 to 10 the weight of their sum is 7+7−2⋅4=67 + 7 - 2 \cdot 4 = 6, and for row 11 against any other row it is 11+7−2⋅6=611 + 7 - 2 \cdot 6 = 6. ■\blacksquare

04.A Code Equal to Its Own Dual

Linear Codes defined the dual C⊥C^{\perp} of a code CC as the set of all words orthogonal to every codeword. The theorem on BB makes G24\mathcal{G}_{24} its own dual.

Proof. Multiplying by blocks, GGT=I12I12T+BBT=I12+I12=0GG^{\mathsf T} = I_{12} I_{12}^{\mathsf T} + BB^{\mathsf T} = I_{12} + I_{12} = 0, since 1+1=01 + 1 = 0 over GF(2)\mathrm{GF}(2). So every row of GG is orthogonal to every row, itself included. Every codeword is a sum of rows and the inner product distributes over sums, so every codeword is orthogonal to every codeword, and G24⊆G24⊥\mathcal{G}_{24} \subseteq \mathcal{G}_{24}^{\perp}. The identity block makes the 12 rows independent, so the code has dimension 12, and its dual has dimension 24−12=1224 - 12 = 12. A subspace with the same dimension as a space containing it is that whole space, so the two codes are equal. ■\blacksquare

Self-duality constrains weights. The rows g0g_0, of weight 8, and g11g_{11}, of weight 12, share six 1s, all in the check part, an even number as orthogonality requires. So w(g0⊕g11)=8+12−2⋅6=8w(g_0 \oplus g_{11}) = 8 + 12 - 2 \cdot 6 = 8, which the sum (100000000001,001000111011)(100000000001, 001000111011) confirms. The weight came out a multiple of 4 again, and that is no accident.

Proof. Every codeword is a sum of rows of GG, so induct on the number of rows added, starting from the zero codeword, of weight 0. Suppose xx is a codeword with 4∣w(x)4 \mid w(x) and gg is a row of GG, of weight 8 or 12. Self-duality gives x⋅g=0x \cdot g = 0, so w(x∧g)w(x \wedge g) is even and 2 w(x∧g)2\,w(x \wedge g) is a multiple of 4. Each term of w(x⊕g)=w(x)+w(g)−2 w(x∧g)w(x \oplus g) = w(x) + w(g) - 2\,w(x \wedge g) is then a multiple of 4, and so is the result. ■\blacksquare

A code whose weights are all multiples of 4 is called doubly even.

05.Minimum Distance Eight

The weights are multiples of 4, so the smallest nonzero weight is 4 or at least 8. Ruling out 4 uses B2=I12B^2 = I_{12}. If c=(a,b)c = (a, b) is a codeword, then b=aBb = aB, and multiplying by BB gives bB=aB2=abB = aB^2 = a. The check part fixes the message part through the same matrix, so [ B∣I12 ][\,B \mid I_{12}\,] generates the same code with the two halves trading roles.

Proof. Suppose c=(a,b)c = (a, b) is a codeword of weight 4. Then w(a)+w(b)=4w(a) + w(b) = 4, so one half has weight at most 2. Take first w(a)≤2w(a) \le 2. If a=0a = 0, then b=0B=0b = 0B = 0 and cc is the zero word. If w(a)=1w(a) = 1, then a=uia = u_i and b=bib = b_i, of weight 7 or 11, so w(c)w(c) is 8 or 12. If w(a)=2w(a) = 2, then a=ui⊕uja = u_i \oplus u_j and b=bi⊕bjb = b_i \oplus b_j, which has weight 6 by the lemma on rows of BB, so w(c)=8w(c) = 8. None of these is 4. If instead w(b)≤2w(b) \le 2, the same three cases run with a=bBa = bB in place of b=aBb = aB and give the same weights. ■\blacksquare

Proof. The minimum distance of a linear code is its smallest nonzero weight. The nonzero weights are multiples of 4 and none is 4, so all are at least 8, and g0g_0 has weight 8. A word at distance 4 from one codeword is at distance at least 8−4=48 - 4 = 4 from every other, so it lies in no ball of radius 3, and a decoder can flag it instead of changing it into a wrong codeword. ■\blacksquare

Proof. Add all 12 rows of GG. The message part is u0⊕u1⊕⋯⊕u11u_0 \oplus u_1 \oplus \cdots \oplus u_{11}, all 1s. Bit jj of the check part is the sum of column jj of BB modulo 2. Since BB is symmetric, its columns have the weights of its rows, 7 or 11, both odd, so every check bit is 1 as well. ■\blacksquare

Adding 1\mathbf{1} to a codeword of weight ww flips every bit and gives its complement, a codeword of weight 24−w24 - w. Complements therefore pair the codewords of weight ww with those of weight 24−w24 - w, so Aw=A24−wA_w = A_{24 - w}, where AwA_w is the number of codewords of weight ww, the count Weight Distributions and Undetected Errors wrote as AiA_i.

06.Counting Codewords by Weight

The possible weights are therefore 0, 8, 12, 16 and 24. Since A0=A24=1A_0 = A_{24} = 1 and A16=A8A_{16} = A_8, the 4,096 codewords give A12=4096−2−2A8A_{12} = 4096 - 2 - 2A_8, and everything rests on the single count A8A_8. Finding it takes a short detour through length 23.

Proof. Two different codewords differ in at least 8 places, and deleting a coordinate removes at most one of those differences, so the punctured words differ in at least 7 places and are distinct. A word within distance 3 of two of them would put those two within distance 6 of each other, so the balls of radius 3 around the 4,096 words are disjoint. Each ball holds 211=20482^{11} = 2048 words, and 4096⋅2048=2234096 \cdot 2048 = 2^{23} is every word of length 23, so the balls hold each word exactly once. ■\blacksquare

The codeword g0g_0 has its 1s on coordinate 0 and on the coordinates 12+j12 + j for the columns j∈{0,1,3,4,5,9,11}j \in \{0, 1, 3, 4, 5, 9, 11\} where b0b_0 has a 1, that is on {0,12,13,15,16,17,21,23}\{0, 12, 13, 15, 16, 17, 21, 23\}. A binary codeword is fixed by the places of its 1s, so sets like this one name the codewords of weight 8 one for one.

Proof. Let TT be a set of 5 coordinates and pick one of them, ii. Delete coordinate ii from every codeword, and let vv be the word of length 23 with 1s on the four coordinates of TT other than ii. By the lemma, exactly one punctured codeword c′c' lies within distance 3 of vv. It is not the zero word, which is at distance 4 from vv, and its weight differs from w(v)=4w(v) = 4 by at most 3, so 1≤w(c′)≤71 \le w(c') \le 7. Deleting a coordinate lowers a weight by 1 or leaves it alone, so the punctured weights are 0, 7, 8, 11, 12, 15, 16 and 23, and only 7 is in range. The weight of a sum now gives 4+7−2 w(v∧c′)≤34 + 7 - 2\,w(v \wedge c') \le 3, which forces w(v∧c′)=4w(v \wedge c') = 4, so c′c' has a 1 on each coordinate of vv. The codeword cc that c′c' came from has weight 7 or 8, and no codeword has weight 7, so cc has weight 8 with a 1 at coordinate ii too. Its octad contains all of TT.

For uniqueness, suppose two different octads both contain TT. They share at least 5 coordinates, so the sum of their codewords is a nonzero codeword of weight at most 8+8−2⋅5=68 + 8 - 2 \cdot 5 = 6, and no such codeword exists. ■\blacksquare

The theorem says that the 24 coordinates, with the octads as blocks, form a Steiner system S(5,8,24)S(5, 8, 24). The letter SS here names the system and has nothing to do with the set of squares modulo 11.

Proof. Count the pairs made of an octad and a set of 5 coordinates inside it. Each octad contains (85)=56\binom{8}{5} = 56 such sets, and by the theorem each of the (245)=42504\binom{24}{5} = 42504 sets of 5 coordinates lies in exactly one octad. So 56A8=4250456 A_8 = 42504 and A8=759A_8 = 759. Complements give A16=759A_{16} = 759, and then A12=4096−2−2⋅759=2576A_{12} = 4096 - 2 - 2 \cdot 759 = 2576. ■\blacksquare

The script lists all 759 octads and checks the theorem on all 42,504 sets of 5. Figure 4 draws the distribution beside that of the perfect code. MacWilliams and Sloane [2] and van Lint [3] treat the octads and the Steiner system at greater length. The permutations of the coordinates that carry octads to octads form a group, which Case Study: Golay, Leech and the Monster takes up.

Weight distributions of the extended (24,12,8) and perfect (23,12,7) binary Golay codes: 1, 759, 2576, 759, 1 and 1, 253, 506, 1288, 1288, 506, 253, 1 0 500 1000 1500 2000 2500 3000 codewords of weight w extended code, length 24 1 0 759 8 2576 12 759 16 1 24 weight w perfect code, length 23 1 0 253 7 506 8 1288 11 1288 12 506 15 253 16 1 23 weight w
Figure 4. Weight distributions of the extended and perfect binary Golay codes. Data: computed by ch25_charts.py in the companion repository.

07.The Perfect Golay Code

Deleting one coordinate now gives the code the opening asked for.

Proof. The lemma on deleting a coordinate, with i=23i = 23, gives 4,096 distinct words at distance at least 7, whose balls of radius 3 hold every word of length 23 exactly once. The distance is exactly 7, because g0g_0 has a 1 at coordinate 23 and loses it, which leaves a codeword of weight 7. ■\blacksquare

Hamming Codes and Perfect Codes quoted the classification of perfect codes [4]. Every nontrivial perfect code over a prime-power alphabet has the parameters of a Hamming code or of one of the two perfect Golay codes, so no other perfect code corrects more than one error.

Deleting coordinate 23 lowers by one the weight of each codeword of G24\mathcal{G}_{24} with a 1 there and leaves the rest alone. The weight-7 codewords come from the octads that contain coordinate 23, and the perfect property counts them directly. Each of the (234)=8855\binom{23}{4} = 8855 words of weight 4 lies within distance 3 of exactly one codeword, and the proof of the octad theorem showed that this codeword has weight 7 and holds all four 1s of the word. A codeword of weight 7 holds (74)=35\binom{7}{4} = 35 such words, so

A7=885535=253.A_7 = \frac{8855}{35} = 253 .
(4)

The other 759−253=506759 - 253 = 506 octads have a 0 at coordinate 23 and give A8=506A_8 = 506. Complementing swaps the bit at coordinate 23, so the 2,576 dodecads split evenly, 1,288 becoming codewords of weight 11 and 1,288 staying at weight 12. A weight-16 codeword is the complement of an octad and has a 1 at coordinate 23 exactly when the octad has a 0 there, so A15=506A_{15} = 506 and A16=253A_{16} = 253. Table 3 collects the counts, which add up to 4,096.

Table 3. The weight distribution of the perfect binary Golay code, with the codewords of the extended code that each weight comes from

Weight ww in G23\mathcal{G}_{23}AwA_wComes from, in G24\mathcal{G}_{24}
01the zero word
7253octads with a 1 at coordinate 23
8506octads with a 0 at coordinate 23
111,288dodecads with a 1 at coordinate 23
121,288dodecads with a 0 at coordinate 23
15506weight-16 codewords with a 1 at coordinate 23
16253weight-16 codewords with a 0 at coordinate 23
231the all-ones word

Source: reproduced by ch25_golay_codes.py.

Proof. Let c′c' be a codeword cc of G24\mathcal{G}_{24} with coordinate 23 deleted. The parity bit appended to c′c' is w(c′) mod 2=(w(c)−c23) mod 2w(c') \bmod 2 = (w(c) - c_{23}) \bmod 2. Every weight in G24\mathcal{G}_{24} is even and −1≡1(mod2)-1 \equiv 1 \pmod 2, so the parity bit equals c23c_{23}, and the extended word is cc itself. ■\blacksquare

A code equivalent to G23\mathcal{G}_{23}, the same code with its coordinates permuted, is cyclic, so every cyclic shift of one of its codewords is again a codeword. Cyclic Codes and Generator Polynomials develops cyclic codes, Zeros, Idempotents and Cyclic Code Families returns to the squares modulo 11, and Bounds on Codes sets the Golay codes against the limits every code must satisfy.

08.The Ternary Golay Codes

The ternary codes work over GF(3)\mathrm{GF}(3), the numbers 0, 1 and 2 with addition and multiplication modulo 3. In it 1+2=01 + 2 = 0, so 2 behaves as −1-1, and 2⋅2=4≡12 \cdot 2 = 4 \equiv 1. The weight of a ternary word still counts its nonzero places, and the inner product of two words sums the products of their entries modulo 3.

The matrix comes from the squares modulo 5. Squaring 1 to 4 gives 11, 44, 9≡49 \equiv 4 and 16≡116 \equiv 1, so the nonzero squares modulo 5 are 1 and 4. Label each residue xx with χ(x)=0\chi(x) = 0 if x=0x = 0, χ(x)=1\chi(x) = 1 if xx is a nonzero square, and χ(x)=−1\chi(x) = -1 otherwise, which gives

χ(0)=0,χ(1)=1,χ(2)=−1,χ(3)=−1,χ(4)=1.\chi(0) = 0, \quad \chi(1) = 1, \quad \chi(2) = -1, \quad \chi(3) = -1, \quad \chi(4) = 1 .
(5)

In the 6×66 \times 6 matrix B3B_3, rows and columns 1 to 5 stand for the residues 0 to 4, and row 1+a1 + a, column 1+b1 + b holds χ(b−a)\chi(b - a), with −1-1 written as 2. Row 0 and column 0 form a border of 1s with a 0 in the corner. Row 1, for a=0a = 0, is its border entry 1 followed by χ(0),χ(1),χ(2),χ(3),χ(4)\chi(0), \chi(1), \chi(2), \chi(3), \chi(4), which is 0,1,2,2,10, 1, 2, 2, 1, so row 1 is 101221101221. The whole matrix is

B3=[011111101221110122121012122101112210].B_3 = \begin{bmatrix} 0&1&1&1&1&1\\ 1&0&1&2&2&1\\ 1&1&0&1&2&2\\ 1&2&1&0&1&2\\ 1&2&2&1&0&1\\ 1&1&2&2&1&0 \end{bmatrix}.
(6)

It is symmetric, because swapping aa and bb turns χ(b−a)\chi(b - a) into χ(a−b)\chi(a - b), and χ(−x)=χ(x)\chi(-x) = \chi(x) for every xx, since χ(1)=χ(4)\chi(1) = \chi(4) and χ(2)=χ(3)\chi(2) = \chi(3).

Two inner products by hand show the pattern. Row 1 of B3B_3 with itself is 1+0+1+4+4+1=11≡21 + 0 + 1 + 4 + 4 + 1 = 11 \equiv 2, which is −1-1. Row 1 with row 2, 101221⋅110122101221 \cdot 110122, is 1+0+0+2+4+2=9≡01 + 0 + 0 + 2 + 4 + 2 = 9 \equiv 0.

Proof. Take the entries in four groups. Row 0 with itself is five products 1⋅11 \cdot 1, so 5≡−15 \equiv -1. Row 0 with row 1+a1 + a gets 0 from column 0 and the sum of block row aa from columns 1 to 5, which holds two 1s and two 2s and so sums to 6≡06 \equiv 0. Row 1+a1 + a with itself gets 1 from column 0 and four products (±1)2=1(\pm 1)^2 = 1 from the block, a total of 5≡−15 \equiv -1.

For two different rows 1+a1 + a and 1+a′1 + a', let t=a′−at = a' - a, which is not 0. Column 0 contributes 1⋅1=11 \cdot 1 = 1. Writing x=b−a′x = b - a', so that b−a=x+tb - a = x + t, the block contributes ∑x=04χ(x+t) χ(x)\sum_{x=0}^{4} \chi(x + t)\,\chi(x). For t=1t = 1 the five terms are 0,−1,1,−1,00, -1, 1, -1, 0, and for t=2t = 2 they are 0,−1,−1,0,10, -1, -1, 0, 1, so both sums are −1-1. Replacing xx by x−tx - t turns the sum for tt into the sum for −t-t, which covers t=4≡−1t = 4 \equiv -1 and t=3≡−2t = 3 \equiv -2. Every such entry is 1+(−1)=01 + (-1) = 0, and with B3T=B3B_3^{\mathsf T} = B_3 the theorem follows. ■\blacksquare

Proof. By blocks, G3G3T=I6+B3B3T=I6−I6=0G_3 G_3^{\mathsf T} = I_6 + B_3 B_3^{\mathsf T} = I_6 - I_6 = 0, and the dimension argument used for G24\mathcal{G}_{24}, with 6 in place of 12, gives G12=G12⊥\mathcal{G}_{12} = \mathcal{G}_{12}^{\perp}. For the weights, a nonzero entry is 1 or 2, and 12=11^2 = 1 and 22=4≡12^2 = 4 \equiv 1, so x⋅x≡w(x)(mod3)x \cdot x \equiv w(x) \pmod 3. Self-duality makes x⋅x=0x \cdot x = 0 for every codeword xx, so 3∣w(x)3 \mid w(x). ■\blacksquare

Proof. From B32=−I6B_3^2 = -I_6, the inverse of B3B_3 is −B3-B_3. A codeword c=(a,b)c = (a, b) has b=aB3b = aB_3 and therefore a=−bB3a = -bB_3. Suppose w(c)=3w(c) = 3. Then one half has weight at most 1. If a=0a = 0, then b=0b = 0 and c=0c = 0. If a=λuia = \lambda u_i with λ=±1\lambda = \pm 1, then bb is λ\lambda times row ii of B3B_3, of weight 5, so w(c)=6w(c) = 6. If instead w(b)≤1w(b) \le 1, the same holds with a=−bB3a = -bB_3 in place of b=aB3b = aB_3. No codeword has weight 3, the weights are multiples of 3, and the rows of G3G_3 have weight 6, so the minimum distance is 6. ■\blacksquare

Proof. Deleting one coordinate lowers each distance by at most 1, so the 729 punctured words are distinct and at least 5 apart, and the balls of radius 2 around them are disjoint. Each holds 35=2433^5 = 243 words, and 36⋅35=3113^6 \cdot 3^5 = 3^{11} is every ternary word of length 11. Row 0 of G3G_3 has a nonzero entry at coordinate 11 and drops to weight 5, so the distance is exactly 5. ■\blacksquare

The deleted digit can be put back, though not by the overall sum that extends a binary code. Every codeword of G12\mathcal{G}_{12} is orthogonal to row 0 of G3G_3, which is (1,0,0,0,0,0,0,1,1,1,1,1)(1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1), so c0+c7+c8+c9+c10+c11=0c_0 + c_7 + c_8 + c_9 + c_{10} + c_{11} = 0, and the weighted check digit c11=−(c0+c7+c8+c9+c10)c_{11} = -(c_0 + c_7 + c_8 + c_9 + c_{10}) rebuilds each codeword from its punctured word. Row 1 of G3G_3 is (0,1,0,0,0,0,1,0,1,2,2,1)(0, 1, 0, 0, 0, 0, 1, 0, 1, 2, 2, 1), and the rule gives −(0+0+1+2+2)=−5≡1-(0 + 0 + 1 + 2 + 2) = -5 \equiv 1, the digit that was deleted. Its digits add to 8≡28 \equiv 2, not 0, so appending the digit that makes each word's sum 0 gives a different code, of minimum distance 5.

The ternary weight distributions come from the same counting. Delete any coordinate ii of G12\mathcal{G}_{12}. Each of the (113)⋅23=1320\binom{11}{3} \cdot 2^3 = 1320 ternary words of weight 3 and length 11 lies within distance 2 of exactly one punctured codeword, whose weight lies between 1 and 5. Of the punctured weights 0, 5, 6, 8, 9 and 11 only 5 is in range, so that codeword has weight 5 and agrees with the word on 3 of its 5 nonzero places. Each covers (53)=10\binom{5}{3} = 10 such words, so 132 weight-6 codewords are nonzero at coordinate ii, and counting the pairs of a weight-6 codeword and a coordinate where it is nonzero gives 6A6=12⋅1326A_6 = 12 \cdot 132, or A6=264A_6 = 264.

Reading coordinate ii is a linear map onto GF(3)\mathrm{GF}(3), so a third of the codewords, 243, are zero there. They are the zero word, 264−132=132264 - 132 = 132 of weight 6 and, since a weight-12 codeword has no zero, 110 of weight 9. Then 3A9=12⋅1103A_9 = 12 \cdot 110 gives A9=440A_9 = 440, and A12=729−1−264−440=24A_{12} = 729 - 1 - 264 - 440 = 24. Puncturing at coordinate 11 lowers by one the weight of the 132 weight-6 codewords, the 330 weight-9 codewords and the 24 weight-12 codewords that are nonzero there. Table 4 lists both distributions, and Huffman and Pless [5] develop the ternary codes alongside the binary ones.

Table 4. The weight distributions of the extended and perfect ternary Golay codes

Weight ww056891112
AwA_w in G12\mathcal{G}_{12}102640440024
AwA_w in G11\mathcal{G}_{11}1132132330110240

Source: reproduced by ch25_golay_codes.py.

09.Decoding by Hand

Suppose the codeword c=(m,mB)c = (m, mB) is sent and r=c⊕er = c \oplus e arrives, where the error pattern ee has a 1 wherever a bit flipped. Split both into halves, r=(rL,rR)r = (r_{\mathrm L}, r_{\mathrm R}) and e=(eL,eR)e = (e_{\mathrm L}, e_{\mathrm R}), with coordinates 0 to 11 on the left and 12 to 23 on the right. The code is self-dual, so its generator matrix also serves as a parity-check matrix, H=G=[ I12∣B ]H = G = [\,I_{12} \mid B\,]. The syndrome of Syndrome Decoding and the Standard Array is s=rHT=rLI12⊕rRBTs = rH^{\mathsf T} = r_{\mathrm L} I_{12} \oplus r_{\mathrm R} B^{\mathsf T}, and since BT=BB^{\mathsf T} = B it takes a simple form.

A codeword gives m⊕mB2=m⊕m=0m \oplus mB^2 = m \oplus m = 0, and the syndrome is linear in rr, so it depends on the error alone, s=eL⊕eRBs = e_{\mathrm L} \oplus e_{\mathrm R} B. Multiplying by BB gives sB=eLB⊕eRsB = e_{\mathrm L} B \oplus e_{\mathrm R}, the same information with the halves trading roles. The decoder runs five steps in order and stops at the first that applies, and Figure 5 draws them as a flowchart.

  • (a) If w(s)≤3w(s) \le 3, return e=(s,0)e = (s, 0).

  • (b) If w(s⊕bi)≤2w(s \oplus b_i) \le 2 for some row bib_i of BB, return e=(s⊕bi,ui)e = (s \oplus b_i, u_i).

  • (c) Compute sBsB. If w(sB)≤3w(sB) \le 3, return e=(0,sB)e = (0, sB).

  • (d) If w(sB⊕bi)≤2w(sB \oplus b_i) \le 2 for some ii, return e=(ui,sB⊕bi)e = (u_i, sB \oplus b_i).

  • (e) Otherwise, report that four or more errors occurred.

The five steps of the hand decoder for the extended binary Golay code. Compute the syndrome s; if s is light, or lies within two of a row of B, the error is found from s; otherwise compute s B and make the same two tests on it; if every test fails, flag four or more errors. compute the syndrome s = r1+ r2B is w(s) at most 3 ? is w(s + bi) at most 2 for some i ? compute s B is w(s B) at most 3 ? is w(s B + bi) at most 2 for some i ? flag: four or more errors (a) (b) (c) (d) (e) e = (s, 0) e = (s + bi, ui) e = (0, s B) e = (ui, s B + bi) error pattern returned yes yes yes yes no no no no biis row i of B uihas a single 1, in place i
Figure 5. The five steps of the hand decoder for the extended binary Golay code.

Each step guesses the shape of the error. Step (a) guesses that every error is in the left half, so eR=0e_{\mathrm R} = 0 and s=eLs = e_{\mathrm L}. Step (b) guesses exactly one error in the right half, at coordinate 12+i12 + i, so s=eL⊕bis = e_{\mathrm L} \oplus b_i and s⊕bi=eLs \oplus b_i = e_{\mathrm L}. Steps (c) and (d) make the same two guesses with the halves swapped, reading sBsB.

Proof. The syndrome of a pattern (x,y)(x, y) is x⊕yBx \oplus yB, and the proof uses uiB=biu_i B = b_i and biB=uiB2=uib_i B = u_i B^2 = u_i. Step (a) returns (s,0)(s, 0), with syndrome ss. Step (b) returns (s⊕bi,ui)(s \oplus b_i, u_i), with syndrome s⊕bi⊕bi=ss \oplus b_i \oplus b_i = s. Step (c) returns (0,sB)(0, sB), with syndrome sB2=ssB^2 = s. Step (d) returns (ui,sB⊕bi)(u_i, sB \oplus b_i), with syndrome ui⊕sB2⊕biB=ui⊕s⊕ui=su_i \oplus sB^2 \oplus b_i B = u_i \oplus s \oplus u_i = s. The weights are at most 33, 2+12 + 1, 33 and 1+21 + 2, by the tests that let each step fire. ■\blacksquare

Proof. At most one pattern of weight 3 or less has a given syndrome, because two such patterns ee and ff with the same syndrome would make e⊕fe \oplus f a nonzero codeword of weight at most 6. By the lemma, whichever step fires first therefore returns the true error, and what remains is to show that some step fires.

Let e=(eL,eR)e = (e_{\mathrm L}, e_{\mathrm R}) have weight at most 3. Then w(eL)≤1w(e_{\mathrm L}) \le 1 or w(eR)≤1w(e_{\mathrm R}) \le 1, since otherwise the weight would be at least 4, and that leaves four cases. If eR=0e_{\mathrm R} = 0, then s=eLs = e_{\mathrm L} has weight at most 3 and step (a) fires. If eR=uie_{\mathrm R} = u_i, then s⊕bi=eLs \oplus b_i = e_{\mathrm L} has weight at most 2 and step (b) fires. If eL=0e_{\mathrm L} = 0, then sB=eRsB = e_{\mathrm R} has weight at most 3 and step (c) fires. If eL=uie_{\mathrm L} = u_i, then sB⊕bi=eRsB \oplus b_i = e_{\mathrm R} has weight at most 2 and step (d) fires. ■\blacksquare

Proof. Suppose ee has weight 4 and some step fires with a pattern ff. By the lemma ff has syndrome ss and weight at most 3, so e⊕fe \oplus f has syndrome 0 and is a codeword. It is not zero, since ee and ff have different weights, and its weight is at most 4+3=74 + 3 = 7. No nonzero codeword weighs less than 8, so no step fires. ■\blacksquare

The script runs the decoder on all 2,324 patterns of weight 1 to 3 and all (244)=10626\binom{24}{4} = 10626 of weight 4, and Table 5 records the step that resolved each. A pattern can fit the shapes of two steps, as a single error in the left half fits step (a), with eR=0e_{\mathrm R} = 0, and step (d), with eL=uie_{\mathrm L} = u_i. The earlier step fires first, which is why step (d) resolves nothing below weight 3. Figure 6 draws the same counts as shares of each weight.

Table 5. The step of the hand decoder that resolves each error pattern of weight 1 to 4, counted over every pattern

Error weightPatternsStep (a)Step (b)Step (c)Step (d)Flagged by step (e)
1241212000
2276661446600
32,0242207922207920
1 to 32,3242989482867920
410,626000010,626

Source: reproduced by ch25_golay_codes.py.

How the five steps of the Golay decoder resolve every error pattern of weight 1 to 4, each bar segment labelled with its step and its count: all 2324 patterns of weight 1 to 3 are corrected by steps (a) to (d) and all 10626 of weight 4 are flagged by step (e) share of the error patterns of each weight resolved by each step patterns weight 1 (a) 12 (b) 12 24 corrected weight 2 (a) 66 (b) 144 (c) 66 276 corrected weight 3 (a) 220 (b) 792 (c) 220 (d) 792 2024 corrected weight 4 (e) 10626 10626 flagged 0% 25% 50% 75% 100% steps (a) to (d), the error corrected step (e), the word flagged
Figure 6. How the steps of the hand decoder share the error patterns of each weight. Every pattern of weight 1 to 3 is corrected and every pattern of weight 4 is flagged. Data: computed by ch25_charts.py in the companion repository.

Pless published decoders for the Golay codes that use their structure rather than a table [6], and Lin and Costello give the five-step form used here [7]. A lookup table would need an entry for each of the 212=40962^{12} = 4096 syndromes, while the steps above need only the 12 rows of BB.

10.The Decoder in Hardware

Every part of the hand decoder is an XOR tree or a weight test, the same parts as in the decoders of SECDED and Hsiao Codes. Figure 7 draws the result and Table 6 counts its gates.

Bit jj of the syndrome s=rL⊕rRBs = r_{\mathrm L} \oplus r_{\mathrm R} B is rjr_j plus the bits r12+kr_{12 + k} for which BB has a 1 in row kk and column jj. Column 0 of BB has its 1s in rows 0, 1, 3, 4, 5, 9 and 11, so

s0=r0⊕r12⊕r13⊕r15⊕r16⊕r17⊕r21⊕r23.s_0 = r_0 \oplus r_{12} \oplus r_{13} \oplus r_{15} \oplus r_{16} \oplus r_{17} \oplus r_{21} \oplus r_{23} .
(8)

Eight inputs need 7 two-input XOR gates, which a balanced tree arranges in 3 levels, and bits s1s_1 to s10s_{10} have the same shape, since columns 0 to 10 all have weight 7. Bit s11s_{11} reads column 11, of weight 11, so it has 12 inputs, 11 gates and 4 levels. The syndrome network therefore holds 11⋅7+11=8811 \cdot 7 + 11 = 88 gates in 4 levels. A second network of the same kind computes sBsB from ss, with 76 gates in 4 levels, as an exercise derives, so the two networks hold 164 XOR gates between them.

Step (b) tests w(s⊕bi)≤2w(s \oplus b_i) \le 2 for each of the 12 rows. Built literally, each test adds a constant row to ss with 12 XOR gates, 144 for the bank. Adding a constant 1 to a bit only inverts it and adding a constant 0 does nothing, so those gates fold into one inverter for each 1 of BB, 88 of them built unshared, since the 12 rows hold 11⋅7+11=8811 \cdot 7 + 11 = 88 ones. Every test reads the same 12 bits of ss, so 12 shared inverters supply all of them.

A weight test asks whether at least 3, or at least 4, of 12 bits are 1, and a chain of AND and OR gates answers it. Scan the bits in order, keeping flags t1t_1, t2t_2 and t3t_3 that record whether at least one, two or three 1s have appeared so far. A new bit xx updates them as t3←t3∨(t2∧x)t_3 \leftarrow t_3 \lor (t_2 \land x), t2←t2∨(t1∧x)t_2 \leftarrow t_2 \lor (t_1 \land x) and t1←t1∨xt_1 \leftarrow t_1 \lor x, using the old values on the right. The first bit sets t1t_1 with no gates, the second costs 2 gates, the third 4, and each of the last nine 5, so the at-least-3 chain uses 2+4+9⋅5=512 + 4 + 9 \cdot 5 = 51 gates. A fourth flag makes an at-least-4 chain of 2+4+6+8⋅7=682 + 4 + 6 + 8 \cdot 7 = 68 gates. The script checks both chains against a direct count of 1s on all 4,096 inputs. Inverted, the two flags give the tests w≤2w \le 2 and w≤3w \le 3.

Each of the two banks holds 13 tests, one at-least-4 chain for step (a) or (c) and twelve at-least-3 chains for step (b) or (d), so a bank uses 68+12⋅51=68068 + 12 \cdot 51 = 680 AND and OR gates beside its inverters. Across both banks the 24 weight-at-most-2 tests use 1,224 gates and the 2 weight-at-most-3 tests use 136. A priority select reads the 26 flags and, as data, the candidate patterns built from ss, sBsB and the folded words s⊕bis \oplus b_i and sB⊕bisB \oplus b_i. It passes on the pattern of the first test that fires, in the order (a) to (d), and raises the flag when none does. Its gates, the 26 flag inversions among them, depend on how the patterns are wired, and the chapter leaves them uncounted. A last row of 24 XOR gates forms the corrected word r⊕er \oplus e. The whole decoder is combinational, with no clock and no stored table.

Table 6. Gate counts for the parts of the hand decoder built in hardware

PartGates
Syndrome network, 12 XOR trees, 4 levels deep88 XOR2
Network for sBsB, 4 levels deep76 XOR2
Both XOR networks164 XOR2
One bank of 12 row tests, built literally144 XOR2
The same bank with its constants folded, unshared88 NOT
The same bank with its inverters shared12 NOT
Chain flagging at least 3 of 12 bits51 AND and OR
Chain flagging at least 4 of 12 bits68 AND and OR
One bank of 13 weight tests680 AND and OR
The 24 weight-at-most-2 tests of both banks1,224 AND and OR
The 2 weight-at-most-3 tests of both banks136 AND and OR
Correction of rr by ee24 XOR2

Source: reproduced by ch25_golay_codes.py.

The decoder of the extended binary Golay code in hardware: the XOR tree for syndrome bit 0, and the syndrome network, the s B network, two banks of weight tests whose flags and candidate words feed a priority select, and a row of XOR gates that adds the chosen error pattern e to r syndrome bit 0: 8 inputs, 7 XOR gates, 3 levels r0 r12 r13 r15 r16 r17 r21 r23 s0 Bits s1 to s10 have the same shape. Bit s11 has 12 inputs and needs 11 gates in 4 levels, so the 12 trees hold 88 two-input XOR gates in all. r, 24 bits syndrome network 88 XOR2, 4 levels s s B network 76 XOR2, 4 levels s s B test bank 1 13 weight tests on s 680 AND/OR, 12 NOT 13 flags 13 words test bank 2 13 weight tests on s B 680 AND/OR, 12 NOT 13 flags 13 words priority select the first test that fires picks e from s, s + bi, s B or s B + bi e correction r + e, 24 XOR2 r corrected word, or the flag
Figure 7. The hand decoder in hardware, with the XOR tree for syndrome bit 0 and the block diagram of the whole decoder. Data: drawn by ch25_charts.py from the gate counts of ch25_golay_codes.py.

11.Golay Codes in Flight

A Jet Propulsion Laboratory summary of the Voyager telecommunications lists among the spacecraft's new features a single telemetry channel protected by a Golay code and a convolutional code in concatenation, a pairing later replaced in flight by a Reed–Solomon code with the convolutional code [8]. Concatenated means that the data passes through two encoders in turn.

The Golay encoding used at Jupiter and Saturn sent one overhead bit for every information bit, an overhead of 100 percent. A rate-1/21/2 code such as G24\mathcal{G}_{24}, with 12 check bits for 12 message bits, gives exactly that ratio, but the report does not name the code's length, so the match is an inference. For the longer range of the Uranus and Neptune encounters, an experimental Reed–Solomon encoder cut the overhead to about one bit in five and lowered the bit-error rate of the decoded output from 5×10−35 \times 10^{-3} to 10−610^{-6}.

The ground stations then allowed downlink rates of up to 115,200 bits per second at Jupiter in 1979 and 44,800 at Saturn in 1981, the latter for Voyager 2. If the code was the (24,12)(24, 12) code, it cost half the channel, and once a stronger code delivered a lower error rate at a fifth of the overhead, the mission changed codes in flight.

12.Looking Ahead

The Golay codes each come from one exceptional matrix, and the classification of perfect codes says that no nontrivial perfect code over a prime-power alphabet with other parameters corrects more than one error. Reed–Muller Codes takes the opposite approach, a rule that builds binary codes at every length that is a power of 2, each from two smaller ones, decoded by majority vote.

13.Worked Examples

14.Exercises

References

  1. [1]Golay, Marcel J. E. (1949). “Notes on Digital Coding.” Proceedings of the IRE, 37(6), pp. 657. doi:10.1109/JRPROC.1949.233620
  2. [2]MacWilliams, F. Jessie and Sloane, Neil J. A. (1977). “The Theory of Error-Correcting Codes.” North-Holland. doi:10.1016/S0924-6509(08)X7030-8
  3. [3]van Lint, J. H. (1999). “Introduction to Coding Theory.” 3rd edition. Springer. doi:10.1007/978-3-642-58575-3
  4. [4]Tietäväinen, Aimo (1973). “On the Nonexistence of Perfect Codes over Finite Fields.” SIAM Journal on Applied Mathematics, 24(1), pp. 88–96. doi:10.1137/0124010
  5. [5]Huffman, W. Cary and Pless, Vera (2003). “Fundamentals of Error-Correcting Codes.” Cambridge University Press. doi:10.1017/CBO9780511807077
  6. [6]Pless, Vera (1986). “Decoding the Golay Codes.” IEEE Transactions on Information Theory, 32(4), pp. 561–567. doi:10.1109/TIT.1986.1057197
  7. [7]Lin, Shu and Costello, Jr., Daniel J. (2004). “Error Control Coding: Fundamentals and Applications.” 2nd edition. Pearson Prentice Hall.
  8. [8]Ludwig, Roger and Taylor, Jim (2002). “Voyager Telecommunications.” DESCANSO Design and Performance Summary Series, Article 4, Jet Propulsion Laboratory. March 2002. https://descanso.jpl.nasa.gov/DPSummary/Descanso4--Voyager_new.pdf

— Anirban

Hardware–software at the seam where compilers meet microcode.

FeedbackBook modePaper
error-correction-codinglinear-block-codes