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 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 codewords, and at exactly the balls cover all words with none left over. The same count for ternary words of length 11 gives balls of radius 2 holding words, so codewords would fill all . 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 code and the ternary 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
| Code | Field | Corrects | Codewords | Property | |||
|---|---|---|---|---|---|---|---|
| , extended binary | 24 | 12 | 8 | 3 errors | 4,096 | self-dual | |
| , perfect binary | 23 | 12 | 7 | 3 errors | 4,096 | perfect | |
| , extended ternary | 12 | 6 | 6 | 2 errors | 729 | self-dual | |
| , perfect ternary | 11 | 6 | 5 | 2 errors | 729 | perfect |
Source: reproduced by ch25_golay_codes.py.
02.Building the Matrix B
The binary construction starts from arithmetic modulo 11. Squaring 1 to 5 and reducing modulo 11 gives , , , and . The squares of 6 to 10 repeat these, because . The nonzero squares modulo 11 are therefore , half of the ten nonzero residues, and adding 0 to them gives the set
Row 0 of an 11-column pattern puts a 1 in each column whose number lies in , which gives 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 . A left shift by places moves column to column modulo 11, so row has a 1 in column exactly when lies in . For row 1 that is the set , exactly the places of the 1s in .
The matrix 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.
Rows 0 to 10 have weight 7, six 1s from and one from the border, and row 11 has weight 11. Write for row of , a word of 12 bits, so that and .
Row of is , where is the 12-bit unit word with its only 1 in place . Coordinates 0 to 11 of a codeword carry the message and coordinates 12 to 23 carry the checks, with coordinate under column of . Places are numbered from 0 here, where Modifying and Combining Codes numbered them from 1. Figure 2 draws all of as a grid of cells.
To encode the message , add rows 0 and 2 of , since has its 1s in places 0 and 2. The message part is itself, and the check part is , worked one column at a time.
The codeword is , of weight .
Proof. Inside the block, the entry in row and column is 1 exactly when lies in . The sum does not change when and trade places, so the entry in row and column 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.
03.Rows That Meet in Pairs
Rows 0 and 1 of have their 1s in columns and , so they share the four columns . Write for the word with a 1 wherever both and have one. Over the inner product is the number of shared 1s taken modulo 2, , so , while .
Proof. Entry of is . 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 and among rows 0 to 10. In columns 0 to 10 their 1s lie on the sets and . Adding to every element of both sets only renames the columns, and it turns them into and , with . For and , the sets and become and . So the pair shares as many elements as and do. Adding to both of those shows that and meet in equally many elements, so only 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 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 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 , and since this says .
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 | Rows, for example | Shared in columns 0 to 10 | With column 11 | ||
|---|---|---|---|---|---|
| 1 | 0 and 1, 0 and 10 | 3 | 4 | ||
| 2 | 0 and 2, 0 and 9 | 3 | 4 | ||
| 3 | 0 and 3, 0 and 8 | 3 | 4 | ||
| 4 | 0 and 4, 0 and 7 | 3 | 4 | ||
| 5 | 0 and 5, 0 and 6 | 3 | 4 |
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.
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
The distance between and , the number of places where they differ, is .
Proof. For two rows among rows 0 to 10 the weight of their sum is , and for row 11 against any other row it is .
04.A Code Equal to Its Own Dual
Linear Codes defined the dual of a code as the set of all words orthogonal to every codeword. The theorem on makes its own dual.
Proof. Multiplying by blocks, , since over . So every row of 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 . The identity block makes the 12 rows independent, so the code has dimension 12, and its dual has dimension . A subspace with the same dimension as a space containing it is that whole space, so the two codes are equal.
Self-duality constrains weights. The rows , of weight 8, and , of weight 12, share six 1s, all in the check part, an even number as orthogonality requires. So , which the sum confirms. The weight came out a multiple of 4 again, and that is no accident.
Proof. Every codeword is a sum of rows of , so induct on the number of rows added, starting from the zero codeword, of weight 0. Suppose is a codeword with and is a row of , of weight 8 or 12. Self-duality gives , so is even and is a multiple of 4. Each term of is then a multiple of 4, and so is the result.
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 . If is a codeword, then , and multiplying by gives . The check part fixes the message part through the same matrix, so generates the same code with the two halves trading roles.
Proof. Suppose is a codeword of weight 4. Then , so one half has weight at most 2. Take first . If , then and is the zero word. If , then and , of weight 7 or 11, so is 8 or 12. If , then and , which has weight 6 by the lemma on rows of , so . None of these is 4. If instead , the same three cases run with in place of and give the same weights.
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 has weight 8. A word at distance 4 from one codeword is at distance at least 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.
Proof. Add all 12 rows of . The message part is , all 1s. Bit of the check part is the sum of column of modulo 2. Since is symmetric, its columns have the weights of its rows, 7 or 11, both odd, so every check bit is 1 as well.
Adding to a codeword of weight flips every bit and gives its complement, a codeword of weight . Complements therefore pair the codewords of weight with those of weight , so , where is the number of codewords of weight , the count Weight Distributions and Undetected Errors wrote as .
06.Counting Codewords by Weight
The possible weights are therefore 0, 8, 12, 16 and 24. Since and , the 4,096 codewords give , and everything rests on the single count . 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 words, and is every word of length 23, so the balls hold each word exactly once.
The codeword has its 1s on coordinate 0 and on the coordinates for the columns where has a 1, that is on . 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 be a set of 5 coordinates and pick one of them, . Delete coordinate from every codeword, and let be the word of length 23 with 1s on the four coordinates of other than . By the lemma, exactly one punctured codeword lies within distance 3 of . It is not the zero word, which is at distance 4 from , and its weight differs from by at most 3, so . 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 , which forces , so has a 1 on each coordinate of . The codeword that came from has weight 7 or 8, and no codeword has weight 7, so has weight 8 with a 1 at coordinate too. Its octad contains all of .
For uniqueness, suppose two different octads both contain . They share at least 5 coordinates, so the sum of their codewords is a nonzero codeword of weight at most , and no such codeword exists.
The theorem says that the 24 coordinates, with the octads as blocks, form a Steiner system . The letter 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 such sets, and by the theorem each of the sets of 5 coordinates lies in exactly one octad. So and . Complements give , and then .
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.
07.The Perfect Golay Code
Deleting one coordinate now gives the code the opening asked for.
Proof. The lemma on deleting a coordinate, with , 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 has a 1 at coordinate 23 and loses it, which leaves a codeword of weight 7.
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 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 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 such words, so
The other octads have a 0 at coordinate 23 and give . 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 and . 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 in | Comes from, in | |
|---|---|---|
| 0 | 1 | the zero word |
| 7 | 253 | octads with a 1 at coordinate 23 |
| 8 | 506 | octads with a 0 at coordinate 23 |
| 11 | 1,288 | dodecads with a 1 at coordinate 23 |
| 12 | 1,288 | dodecads with a 0 at coordinate 23 |
| 15 | 506 | weight-16 codewords with a 1 at coordinate 23 |
| 16 | 253 | weight-16 codewords with a 0 at coordinate 23 |
| 23 | 1 | the all-ones word |
Source: reproduced by ch25_golay_codes.py.
Proof. Let be a codeword of with coordinate 23 deleted. The parity bit appended to is . Every weight in is even and , so the parity bit equals , and the extended word is itself.
A code equivalent to , 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 , the numbers 0, 1 and 2 with addition and multiplication modulo 3. In it , so 2 behaves as , and . 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 , , and , so the nonzero squares modulo 5 are 1 and 4. Label each residue with if , if is a nonzero square, and otherwise, which gives
In the matrix , rows and columns 1 to 5 stand for the residues 0 to 4, and row , column holds , with written as 2. Row 0 and column 0 form a border of 1s with a 0 in the corner. Row 1, for , is its border entry 1 followed by , which is , so row 1 is . The whole matrix is
It is symmetric, because swapping and turns into , and for every , since and .
Two inner products by hand show the pattern. Row 1 of with itself is , which is . Row 1 with row 2, , is .
Proof. Take the entries in four groups. Row 0 with itself is five products , so . Row 0 with row gets 0 from column 0 and the sum of block row from columns 1 to 5, which holds two 1s and two 2s and so sums to . Row with itself gets 1 from column 0 and four products from the block, a total of .
For two different rows and , let , which is not 0. Column 0 contributes . Writing , so that , the block contributes . For the five terms are , and for they are , so both sums are . Replacing by turns the sum for into the sum for , which covers and . Every such entry is , and with the theorem follows.
Proof. By blocks, , and the dimension argument used for , with 6 in place of 12, gives . For the weights, a nonzero entry is 1 or 2, and and , so . Self-duality makes for every codeword , so .
Proof. From , the inverse of is . A codeword has and therefore . Suppose . Then one half has weight at most 1. If , then and . If with , then is times row of , of weight 5, so . If instead , the same holds with in place of . No codeword has weight 3, the weights are multiples of 3, and the rows of have weight 6, so the minimum distance is 6.
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 words, and is every ternary word of length 11. Row 0 of has a nonzero entry at coordinate 11 and drops to weight 5, so the distance is exactly 5.
The deleted digit can be put back, though not by the overall sum that extends a binary code. Every codeword of is orthogonal to row 0 of , which is , so , and the weighted check digit rebuilds each codeword from its punctured word. Row 1 of is , and the rule gives , the digit that was deleted. Its digits add to , 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 of . Each of the 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 such words, so 132 weight-6 codewords are nonzero at coordinate , and counting the pairs of a weight-6 codeword and a coordinate where it is nonzero gives , or .
Reading coordinate is a linear map onto , so a third of the codewords, 243, are zero there. They are the zero word, of weight 6 and, since a weight-12 codeword has no zero, 110 of weight 9. Then gives , and . 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 | 0 | 5 | 6 | 8 | 9 | 11 | 12 |
|---|---|---|---|---|---|---|---|
| in | 1 | 0 | 264 | 0 | 440 | 0 | 24 |
| in | 1 | 132 | 132 | 330 | 110 | 24 | 0 |
Source: reproduced by ch25_golay_codes.py.
09.Decoding by Hand
Suppose the codeword is sent and arrives, where the error pattern has a 1 wherever a bit flipped. Split both into halves, and , 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, . The syndrome of Syndrome Decoding and the Standard Array is , and since it takes a simple form.
A codeword gives , and the syndrome is linear in , so it depends on the error alone, . Multiplying by gives , 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 , return .
-
(b) If for some row of , return .
-
(c) Compute . If , return .
-
(d) If for some , return .
-
(e) Otherwise, report that four or more errors occurred.
Each step guesses the shape of the error. Step (a) guesses that every error is in the left half, so and . Step (b) guesses exactly one error in the right half, at coordinate , so and . Steps (c) and (d) make the same two guesses with the halves swapped, reading .
Proof. The syndrome of a pattern is , and the proof uses and . Step (a) returns , with syndrome . Step (b) returns , with syndrome . Step (c) returns , with syndrome . Step (d) returns , with syndrome . The weights are at most , , and , by the tests that let each step fire.
Proof. At most one pattern of weight 3 or less has a given syndrome, because two such patterns and with the same syndrome would make 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 have weight at most 3. Then or , since otherwise the weight would be at least 4, and that leaves four cases. If , then has weight at most 3 and step (a) fires. If , then has weight at most 2 and step (b) fires. If , then has weight at most 3 and step (c) fires. If , then has weight at most 2 and step (d) fires.
Proof. Suppose has weight 4 and some step fires with a pattern . By the lemma has syndrome and weight at most 3, so has syndrome 0 and is a codeword. It is not zero, since and have different weights, and its weight is at most . No nonzero codeword weighs less than 8, so no step fires.
The script runs the decoder on all 2,324 patterns of weight 1 to 3 and all 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 , and step (d), with . 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 weight | Patterns | Step (a) | Step (b) | Step (c) | Step (d) | Flagged by step (e) |
|---|---|---|---|---|---|---|
| 1 | 24 | 12 | 12 | 0 | 0 | 0 |
| 2 | 276 | 66 | 144 | 66 | 0 | 0 |
| 3 | 2,024 | 220 | 792 | 220 | 792 | 0 |
| 1 to 3 | 2,324 | 298 | 948 | 286 | 792 | 0 |
| 4 | 10,626 | 0 | 0 | 0 | 0 | 10,626 |
Source: reproduced by ch25_golay_codes.py.
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 syndromes, while the steps above need only the 12 rows of .
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 of the syndrome is plus the bits for which has a 1 in row and column . Column 0 of has its 1s in rows 0, 1, 3, 4, 5, 9 and 11, so
Eight inputs need 7 two-input XOR gates, which a balanced tree arranges in 3 levels, and bits to have the same shape, since columns 0 to 10 all have weight 7. Bit reads column 11, of weight 11, so it has 12 inputs, 11 gates and 4 levels. The syndrome network therefore holds gates in 4 levels. A second network of the same kind computes from , with 76 gates in 4 levels, as an exercise derives, so the two networks hold 164 XOR gates between them.
Step (b) tests for each of the 12 rows. Built literally, each test adds a constant row to 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 , 88 of them built unshared, since the 12 rows hold ones. Every test reads the same 12 bits of , 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 , and that record whether at least one, two or three 1s have appeared so far. A new bit updates them as , and , using the old values on the right. The first bit sets 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 gates. A fourth flag makes an at-least-4 chain of gates. The script checks both chains against a direct count of 1s on all 4,096 inputs. Inverted, the two flags give the tests and .
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 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 , and the folded words and . 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 . 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
| Part | Gates |
|---|---|
| Syndrome network, 12 XOR trees, 4 levels deep | 88 XOR2 |
| Network for , 4 levels deep | 76 XOR2 |
| Both XOR networks | 164 XOR2 |
| One bank of 12 row tests, built literally | 144 XOR2 |
| The same bank with its constants folded, unshared | 88 NOT |
| The same bank with its inverters shared | 12 NOT |
| Chain flagging at least 3 of 12 bits | 51 AND and OR |
| Chain flagging at least 4 of 12 bits | 68 AND and OR |
| One bank of 13 weight tests | 680 AND and OR |
| The 24 weight-at-most-2 tests of both banks | 1,224 AND and OR |
| The 2 weight-at-most-3 tests of both banks | 136 AND and OR |
| Correction of by | 24 XOR2 |
Source: reproduced by 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- code such as , 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 to .
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 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]Golay, Marcel J. E. (1949). “Notes on Digital Coding.” Proceedings of the IRE, 37(6), pp. 657. doi:10.1109/JRPROC.1949.233620
- [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]van Lint, J. H. (1999). “Introduction to Coding Theory.” 3rd edition. Springer. doi:10.1007/978-3-642-58575-3
- [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]Huffman, W. Cary and Pless, Vera (2003). “Fundamentals of Error-Correcting Codes.” Cambridge University Press. doi:10.1017/CBO9780511807077
- [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]Lin, Shu and Costello, Jr., Daniel J. (2004). “Error Control Coding: Fundamentals and Applications.” 2nd edition. Pearson Prentice Hall.
- [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.