A 64-bit memory word needs a (72,64) code, a size no Hamming code has. The chapter extends, punctures, shortens, expurgates and augments codes, proves what each does to n, k and d, then combines codes into larger ones.
The previous chapter, Weight Distributions and Undetected Errors, described a code by how many of its codewords have each weight. Every code met so far has a length its construction dictated, but a memory bus is 64 bits wide whatever the construction says.
Five small operations turn one code into a neighbor of a different size. Extending adds a check bit, puncturing deletes a position, shortening removes a data bit, expurgating discards half the codewords and augmenting doubles them. Three constructions then combine two codes into one, the direct sum, the (u∣u+v) construction and the product code. For each, the chapter proves what happens to the length n, the dimension k and the minimum distance d, and counts what it costs in gates.
A server's main memory reads and writes 64 data bits at a time, and SECDED and Hsiao Codes protected each such word with 8 check bits, a code of length 72 and dimension 64. No Hamming code has that size. The Hamming codes of Hamming Codes and Perfect Codes exist only at the lengths 2m−1. With m=6 check bits the code is (63,57), which holds 57 data bits, seven too few. With m=7 it is (127,120), which holds 120 data bits, and 120−64=56 of its data positions would sit idle on every access.
The fix takes two steps. Shortening the (127,120) code 56 times removes 56 data positions and leaves a (71,64) code, which still corrects one error. Extending that code by one overall parity bit gives (72,64), which also detects two errors. The rate, the fraction of stored bits that are data, falls from 120/127≈0.945 to 64/72≈0.889, but the memory stores exactly its 64 bits.
A code is described here by the triple (n,k,d) of its length, dimension and minimum distance, the [n,k] of Linear Codes with the distance added. Words are strings of bits, ⊕ adds two words position by position modulo 2, and w(c) is the weight of c, its number of 1s. Linear Codes showed that the minimum distance of a linear code equals the least weight of a nonzero codeword, and every distance argument below rests on that fact. The running example is the (7,4,3) Hamming code of Linear Codes, with generator matrix G and parity-check matrix H,
A message m1m2m3m4 is sent as m1m2m3m4c5c6c7, with check bits c5=m1⊕m3⊕m4, c6=m1⊕m2⊕m4 and c7=m2⊕m3⊕m4. The code has 16 codewords. One has weight 0, seven have weight 3, seven have weight 4 and one, the all-ones word 1111111, has weight 7.
Table 1 lists every operation with its effect on the three parameters, and the section on each operation proves its row.
Table 1. What each operation does to the length, the dimension and the minimum distance, with the example the chapter works for it
Operation
What it does to the codewords
Length
Dimension
Minimum distance
Example in this chapter
Extending
appends the overall parity bit
n+1
k
d+1 for odd d, d for even d
(7,4,3)→(8,4,4)
Puncturing
deletes one position
n−1
k, when d>1
d or d−1
(8,4,4)→(7,4,3)
Shortening
keeps those with a 0 in one position, then deletes it
n−1
k−1
at least d
(7,4,3)→(6,3,3)
Expurgating
keeps the even-weight codewords
n
k−1
at least d, and even
(7,4,3)→(7,3,4)
Augmenting
adds the all-ones word
n
k+1
min(d,n−wmax)
(7,3,4)→(7,4,3)
Lengthening
augments, then extends
n+1
k+1
that of augmenting, raised to even
(7,3,4)→(8,4,4)
Direct sum
sets a codeword of each code side by side
n1+n2
k1+k2
min(d1,d2)
(4,3,2),(4,1,4)→(8,4,2)
(u∣u+v)
follows u with u⊕v
2n
k1+k2
min(2d1,d2)
(4,3,2),(4,1,4)→(8,4,4)
Product
encodes rows with one code, columns with the other
n1n2
k1k2
d1d2
(3,2,2),(3,2,2)→(9,4,4)
Source: reproduced by ch24_modifying_and_combining_codes.py.
Figure 1 draws the single-code operations as moves between codes built from the (7,4,3) code. Puncturing the extended code at its new position gives the (7,4,3) code back, and so does augmenting its expurgated code.
Figure 1. The single-code operations as moves between the codes built from the (7,4,3) Hamming code. Each box shows (n,k,d). Extending and puncturing at the new position undo each other, and so do expurgating and augmenting.
Take the codeword 1000110, the first row of G, which has weight 3. Appending the XOR of its seven bits, 1⊕0⊕0⊕0⊕1⊕1⊕0=1, gives 10001101, which has weight 4. Every codeword of weight 3 gains a 1 in the same way, and every codeword of weight 4 gains a 0, so the new code has no word of weight 3 at all. Its 16 codewords have weights 0, 4 and 8, fourteen of them weight 4, and its minimum distance is 4. One bit raised the distance by one.
Proof. The XOR of a list of bits is 1 exactly when the list holds an odd number of 1s, so p=1 when w(c) is odd and p=0 when w(c) is even. The weight of (c,p) is w(c)+p. When w(c) is odd this is odd plus 1, and when w(c) is even it is even plus 0. Either way it is even. ■
Proof. The parity of a sum is the sum of the parities, p(a⊕b)=p(a)⊕p(b), because the XOR of all the bits of a⊕b is the XOR of all the bits of a together with all the bits of b. So the map c↦(c,p(c)) is linear, and C^, its image, is a subspace. The first n bits of (c,p(c)) are c itself, so different codewords have different images and C^ holds 2k words, which makes its dimension k.
For a nonzero codeword c, the weight of (c,p(c)) is w(c) when w(c) is even and w(c)+1 when w(c) is odd, so it is at least w(c), which is at least d. Suppose d is odd. Every nonzero extended codeword has even weight by the lemma and weight at least d, so its weight is at least d+1, and a codeword of weight d extends to one of weight exactly d+1. Suppose instead d is even. A codeword of weight d gains a 0 and keeps weight d, and no extended codeword weighs less than d. ■
The parity-check matrix of C^ comes from H in one move. Border H with a column of zeros on the right, then add a row of ones underneath. For the (7,4,3) code this gives
Proof. Take an extended codeword (c,p). Each of the first n−k rows of H^ is a row of H followed by a 0, so it checks c exactly as H does and gives 0. The last row adds all n+1 bits, which is c1⊕⋯⊕cn⊕p=p⊕p=0. So H^ sends every codeword of C^ to zero.
For the rank, take any nonzero sum of rows of H^. If the sum includes the last row, its final bit is 1, because only the last row has a 1 there. If it does not, it is a nonzero sum of rows of H followed by a 0, and the rows of H are independent. Either way the sum is nonzero, so the n−k+1 rows are independent. By the rank theorem of Matrices and Elimination over Finite Fields, the null space of H^ has dimension (n+1)−(n−k+1)=k. It contains C^, which also has dimension k, so the two are equal. ■
For the (7,4,3) code, Figure 2 shows the bordered matrix, which has rank 4 and whose null space is the 16 words of the (8,4,4) code. The extended generator matrix is G with each row's parity appended, which gives the rows 10001101, 01000111, 00101011 and 00011110.
Figure 2. The parity-check matrix H^ of the extended (8,4,4) code. The block H is bordered by a zero column, so the old checks ignore the new bit, and by a row of ones, which checks the overall parity.
The overall parity bit need not be computed from all seven bits. In the (7,4) code,
Each of m1, m2 and m3 appears twice and cancels, and m4 appears three times and survives once, so c5⊕c6⊕c7=m4. The overall parity is then p=m1⊕m2⊕m3⊕m4⊕m4=m1⊕m2⊕m3. Written as coefficients on the message bits it is 1110, and it is built from two two-input XOR gates fed straight from the message.
When d is already even, extending buys nothing. Every codeword of the even-weight (4,3,2) code, with generator rows 1001, 0101 and 0011, has even weight, so every appended bit is 0. The extended rows are 10010, 01010 and 00110, and the distance stays 2.
Delete the last position of every codeword of the extended (8,4,4) code. The overall parity bit goes, and what remains is the (7,4,3) Hamming code, so puncturing at position 8 undoes the extension. Puncturing the (7,4,3) code itself at position 7 costs more. The row 0100011, of weight 3, loses its final 1 and becomes 010001, of weight 2. The punctured code is (6,4,2), with one word of weight 0, three of weight 2, eight of weight 3, three of weight 4 and one of weight 6. It still holds 16 codewords, so no message was lost, but one unit of distance was.
Proof. Deleting a position is a linear map from words of length n to words of length n−1, so Pi(C), the image of C, is a subspace. Two codewords with the same image differ only in position i, so their sum is either the zero word or the word ei with a single 1 at position i. The word ei has weight 1, which is less than d, so it is not a codeword. The sum is therefore zero, distinct codewords have distinct images, and Pi(C) holds 2k words, so its dimension is k.
The image of a nonzero codeword c has weight w(c)−ci, and it is nonzero because the map is one to one. Since ci is 0 or 1, this weight is at least w(c)−1≥d−1. If some codeword of weight d has ci=1, its image has weight exactly d−1, and d′=d−1. If every codeword of weight d has ci=0, those codewords keep weight d, and every codeword of weight d+1 or more keeps weight at least d, so d′=d. ■
In the (7,4,3) code each of the seven positions lies in exactly three of the seven weight-3 codewords, which accounts for all 7⋅3=21 of their 1s, so puncturing anywhere drops the distance to 2.
A code whose minimum-weight words avoid a position keeps its distance there. The code D spanned by 1110000 and 0001111 has the four codewords 0000000, 1110000, 0001111 and 1111111, a (7,2,3) code whose only word of weight 3 has a 0 in position 7. Punctured there, it becomes 000000, 111000, 000111 and 111111, a (6,2,3) code with the same distance and a higher rate. The encoder of Pi(C) is the encoder of C with output i left unconnected, so puncturing a check bit also removes the gates that computed it.
Keep only the codewords of the (7,4,3) code that begin with 0, which are the eight with m1=0, and delete that first position. Table 2 lists the eight words that remain. They form a (6,3,3) code, with four words of weight 3 and three of weight 4, and its generator matrix is rows 2 to 4 of G with the first column removed, the rows 100011, 010101 and 001111.
Table 2. The eight codewords of the (7,4,3) code with a 0 in position 1, and the (6,3,3) codewords left when that position is deleted
Message m2m3m4
Codeword of the (7,4,3) code
Shortened codeword
Weight
000
0000000
000000
0
001
0001111
001111
4
010
0010101
010101
3
011
0011010
011010
3
100
0100011
100011
3
101
0101100
101100
3
110
0110110
110110
4
111
0111001
111001
4
Source: reproduced by ch24_modifying_and_combining_codes.py.
Proof. Let K be the set of codewords with ci=0. The sum of two words with a 0 in position i again has a 0 there, so K is a subspace. Fix a codeword a with ai=1. Every codeword c with ci=1 can be written c=a⊕(a⊕c), and a⊕c has a 0 in position i, so it lies in K. The codewords therefore split into K and the set a⊕K of the same size, so ∣K∣=2k/2=2k−1.
Deleting position i from a word of K removes a 0, so it changes no weight and sends different words to different words. The map is linear, so Si(C) is a subspace with 2k−1 words, which makes its dimension k−1. Every nonzero word of Si(C) has the weight of a nonzero codeword of C, which is at least d. ■
Proof. Write H′ for H without column i. For a word x of length n−1, let x~ be the word of length n made by inserting a 0 at position i. The product Hx~T is the sum of the columns of H that x~ selects, and column i is never selected, so Hx~T=H′xT. Now x lies in Si(C) exactly when x~ lies in C, which happens exactly when Hx~T=0, which is the same as H′xT=0. So the null space of H′ is Si(C), which has dimension k−1 by the shortening theorem. By the rank theorem of Matrices and Elimination over Finite Fields, H′ then has rank (n−1)−(k−1)=n−k, as many as its rows. ■
Deleting column 1 of H gives the rows 011100, 101010 and 111001, which send all eight words of Table 2 to zero. Its six columns are distinct and nonzero, the property Hamming Codes and Perfect Codes needed for correcting one error, so the shortened code corrects one error as the original did. Shortening once more, at what is now position 1, keeps the four codewords with m2=0. The result is the (5,2,3) code with generator rows 10101 and 01111, whose parity-check matrix is H with its first two columns deleted, the rows 11100, 01010 and 11001. Its codewords are 00000, 10101, 01111 and 11010, of weights 0, 3, 4 and 3.
Shortening never lowers the distance, which is why it is the standard way to fit a code to a data width. SECDED and Hsiao Codes built its Hamming SECDED (72,64) code by deleting 56 data columns from the parity-check matrix of the extended (128,120) code, and an exercise at the end proves that extending and shortening can be taken in either order.
Half the codewords of the (7,4,3) code have even weight, the zero word and the seven words of weight 4. Adding any two of those eight gives another of them, so they form a code by themselves, a (7,3,4) code in which every nonzero word has weight exactly 4. Throwing away the odd-weight half cost one message bit and bought one unit of distance.
Proof. Sort the positions by what a and b hold there. Let t=w(a∧b) be the number of positions where both hold a 1, and let s be the number where exactly one of them does. The sum w(a)+w(b) counts each of the s positions once and each of the t positions twice, so w(a)+w(b)=s+2t. The word a⊕b has a 1 exactly at the s positions, so w(a⊕b)=s=w(a)+w(b)−2t. ■
For a=1000110 and b=0100011, of weight 3 each and sharing a 1 only in position 6, the lemma gives 3+3−2⋅1=4, and indeed a⊕b=1100101. The term 2t is even, so w(a⊕b) and w(a)+w(b) are both even or both odd.
Proof. Let E be the set of even-weight codewords. By the lemma, the sum of two words of even weight has even weight, and E contains the zero word, so E is a subspace. Fix a codeword a of odd weight. For any odd-weight codeword c, the word a⊕c has even weight, again by the lemma, so it lies in E, and c=a⊕(a⊕c) lies in a⊕E. The codewords therefore split into E and a⊕E, two sets of the same size, so ∣E∣=2k−1 and the dimension is k−1. Every nonzero word of E is a nonzero codeword of C, so its weight is at least d, and it is even. ■
For the (7,4,3) code the odd-weight codeword can be a=1000110, and the expurgated code is the zero word with the seven words of weight 4. Its generator matrix is H itself. Each row of H has weight 4 and any two rows share exactly two 1s, so every row of H has an even number of 1s in common with every row, which says HHT=0 and puts each row of H in the code. The three rows are independent, so they span 8 codewords, all of even weight by the lemma, and these are the 8 words of the expurgated code. A code whose generator is another code's parity-check matrix is that code's dual, written C⊥ in Linear Codes, so the expurgated Hamming code is the dual of the Hamming code, often called the (7,3,4) simplex code. In a decoder, expurgation adds the all-ones row to the parity-check matrix, one parity check more.
Run expurgation backward. The (7,3,4) code does not contain 1111111, since its words have weight 0 or 4. Adding 1111111 together with every sum 1111111⊕c doubles the code to 16 words. Adding the all-ones word flips every bit, so the new words have weights 7−0=7 and 7−4=3. The result is the (7,4,3) Hamming code, so augmenting the expurgated code gives the original back, and the distance falls to 3.
Proof. The augmented code is the span of C and 1, so it is a subspace. If some 1⊕c were equal to a codeword c′, then 1=c⊕c′ would be a codeword, which it is not. So C and 1⊕C do not overlap, the augmented code holds 2k+1 words, and its dimension is k+1.
Its nonzero words are of two kinds. Those in C have weight at least d, and some have weight exactly d. A word 1⊕c has a 1 exactly where c has a 0, so its weight is n−w(c). It is never the zero word, because that would need c=1. The least of these weights is n−wmax, reached at a codeword of largest weight. The least weight over both kinds is the smaller of the two minima. ■
For the (7,3,4) code wmax=4, so da=min(4,7−4)=3, as the example found. The (5,2,3) code from Shortening fares far worse. Its largest weight is 4, from 01111, so n−wmax=1 and the augmented code is (5,3,1), with the weight-1 word 11111⊕01111=10000 and weights 0, 1, 2, 2, 3, 3, 4 and 5. Augmenting pays off only when no codeword is close to all ones. The (7,4,3) code cannot be augmented at all, because 1111111 is already a codeword.
Augmenting adds a message bit and extending adds a check position, so taking both steps adds one of each and turns (n,k) into (n+1,k+1). That pair of steps is called lengthening. Lengthening the (7,3,4) code first augments it to the (7,4,3) code and then extends that to the (8,4,4) code.
Proof. The theorem on augmenting turns C into a linear (n,k+1,da) code. The theorem on extending turns that into a linear (n+1,k+1) code whose distance is da+1 when da is odd and da when da is even. ■
For the (7,3,4) code, da=3 is odd, so dℓ=4. Augmenting gave up one unit of distance and extending won it back. Lengthening is not, in general, the reverse of shortening, as a worked example below shows.
Place a codeword of the even-weight (4,3,2) code beside a codeword of the (4,1,4) repetition code, whose codewords are 0000 and 1111. Each of the 8⋅2=16 pairs gives a word of length 8, and together they form an (8,4,2) code. Its distance is only 2, because 11000000 is a codeword.
Weight Distributions and Undetected Errors defined the weight enumerator WC(x,y)=∑c∈Cxn−w(c)yw(c), in which x counts the zeros of a codeword and y its ones. Setting x=1 keeps only the ones, and this section writes WC(y) for that specialization WC(1,y)=∑c∈Cyw(c), whose coefficient of yj counts the codewords of weight j.
Proof. Adding two words of the direct sum adds their halves separately, (a∣b)⊕(a′∣b′)=(a⊕a′∣b⊕b′), and the halves stay in C1 and C2, so the direct sum is a subspace. A pair (a,b) can be read back from (a∣b), so the code holds 2k1⋅2k2=2k1+k2 words. The weight of (a∣b) is w(a)+w(b). In a nonzero word at least one half is nonzero, so its weight is at least d1 or at least d2, and in either case at least min(d1,d2). The words (a∣0) with w(a)=d1 and (0∣b) with w(b)=d2 reach both values, so the minimum is exactly min(d1,d2). For the enumerator,
The even-weight (4,3,2) code has one word of weight 0, six of weight 2 and one of weight 4, and the repetition code has one of weight 0 and one of weight 4. The theorem gives
(1+6y2+y4)(1+y4)=1+6y2+2y4+6y6+y8,
so the direct sum has one word of weight 0, six of weight 2, two of weight 4, six of weight 6 and one of weight 8. The code D of Puncturing was a direct sum all along, of the (3,1,3) and (4,1,4) repetition codes, which is why its distance is min(3,4)=3.
The direct sum is a poor code. Each half protects only its own bits, so the whole word is only as strong as its weaker half. The (8,4,2) direct sum and the (8,4,4) extended Hamming code have the same rate, 4/8=0.500, yet the second has twice the distance. The next construction uses the same two parts and reaches distance 4.
Take C1 to be the even-weight (4,3,2) code and C2 the (4,1,4) repetition code again, but this time send a word u∈C1 followed by u⊕v with v∈C2. For u=0110 and v=1111 the codeword is 01101001. The right half mixes the two codes, and that mixing is exactly what the direct sum lacked. The 16 codewords have weights 0, 4 and 8, fourteen of them weight 4, the weight distribution of the extended Hamming code. Reading each codeword's positions in the order 1, 2, 3, 5, 7, 6, 8, 4 turns this code into the extended (8,4,4) code itself, so the two are equivalent codes in the sense of Linear Codes.
The construction appears in Plotkin's work on codes with a given minimum distance [1] and in the family of single-error-correcting codes of Sloane and Whitehead [2], and MacWilliams and Sloane treat it in full [3]. Its distance rests on one inequality.
Proof. The lemma on the weight of a sum gives w(u⊕v)=w(u)+w(v)−2w(u∧v). The word u∧v has a 1 only where u does, so w(u∧v)≤w(u). Substituting, w(u⊕v)≥w(u)+w(v)−2w(u)=w(v)−w(u). ■
Proof. The sum of two codewords is (u⊕u′∣(u⊕u′)⊕(v⊕v′)), which is the codeword built from u⊕u′∈C1 and v⊕v′∈C2, so the code is a subspace. From a codeword (x∣y) the pair is recovered as u=x and v=x⊕y, so different pairs give different codewords and there are 2k1+k2 of them.
For the upper bound, two codewords suffice. With w(u)=d1 and v=0, the codeword (u∣u) has weight 2d1. With u=0 and w(v)=d2, the codeword (0∣v) has weight d2. So d≤min(2d1,d2).
For the lower bound, take a nonzero codeword (u∣u⊕v) and split into two cases. If v=0, then u=0 and the weight is 2w(u)≥2d1. If v=0, the lemma gives w(u)+w(u⊕v)≥w(u)+w(v)−w(u)=w(v)≥d2. In both cases the weight is at least min(2d1,d2). ■
For the length-4 codes, min(2⋅2,4)=4, and the two words of the upper bound are 10011001, from u=1001, and 00001111, from v=1111. A generator matrix stacks (g∣g) for each generator row g of C1 above (0∣g) for each generator row of C2, which gives the rows 10011001, 01010101, 00110011 and 00001111.
Figure 3. Encoding u=0110 and v=1111 into the (u∣u+v) codeword 01101001. The left half is u itself, and the right half costs one XOR gate per bit.
Figure 3 shows the hardware, one XOR gate per position of the right half on top of the encoders of C1 and C2. Figure 4 compares the weight distributions of the two constructions, which share their parts but not their least weight.
Figure 4. Weight distributions of the direct sum and of the (u∣u+v) code built from the same (4,3,2) and (4,1,4) codes. The direct sum has six words of weight 2, and the (u∣u+v) code has its least nonzero weight at 4. Data: computed by ch24_charts.py in the companion repository.
Applied again and again, starting from the smallest codes, the construction builds a whole family of codes whose lengths double at each step. That family is the subject of Reed–Muller Codes.
Arrange four data bits as a 2×2 array with rows 10 and 11. Encode each row with the (3,2,2) even-weight code, which appends the XOR of its two bits, so 10 becomes 101 and 11 becomes 110. Then encode each of the three columns with the same code. Column 1 holds 1 and 1 and gains 0, column 2 holds 0 and 1 and gains 1, and column 3 holds 1 and 0 and gains 1. The result is the 3×3 array drawn in Figure 5, with rows 101, 110 and 011, in which every row and every column has even weight. Read row by row, it is the 9-bit codeword 101110011.
The bit in the bottom right corner is a check on checks. It was computed from the column of row checks, 1 and 0, but computing it from the row of column checks, 0 and 1, gives the same 1, and the lemma below proves the agreement for every data array.
Figure 5. The (3,2,2)⊗(3,2,2) product codeword for the data rows 10 and 11. Row checks and column checks both lead to the same corner bit.
Multiplying on the right by G2 turns each row of M into its C2 codeword. Multiplying on the left by G1T does the same to each column with C1, since G1TyT is the transpose of yG1.
Proof. Rows first gives G1T(MG2) and columns first gives (G1TM)G2. Matrix multiplication is associative, as Matrices and Elimination over Finite Fields showed, so the two arrays are equal. Row r of X is row r of G1TM times G2, a C2 codeword. Column s of X is G1T times column s of MG2, a C1 codeword. ■
Proof. The array X=G1TMG2 depends linearly on M, so the set of arrays is a subspace of the words of length n1n2. To show that different data arrays give different codewords, suppose G1TMG2=0 and let Y=MG2. Each column y of Y satisfies G1Ty=0, which says that the sum of the rows of G1 selected by y is zero. The rows of G1 are independent, so y=0, and therefore Y=0. Then every row m of M satisfies mG2=0, and the rows of G2 are independent, so m=0 and M=0. The code therefore holds 2k1k2 arrays, and its dimension is k1k2.
For the upper bound, pick a∈C1 of weight d1 and b∈C2 of weight d2, with messages α and β such that a=αG1 and b=βG2. The data array M=αTβ gives X=G1TαTβG2=aTb, the array with a 1 in row r and column s exactly when ar=1 and bs=1. That array has weight d1d2.
For the lower bound, let X be a nonzero codeword, and choose a column s that holds a 1. By the lemma, column s is a nonzero codeword of C1, so it has at least d1 ones, and at least d1 rows of X are nonzero. Each of those rows is a nonzero codeword of C2 and has weight at least d2. So w(X)≥d1d2. ■
The product of the (3,2,2) code with itself is therefore a (9,4,4) code. Its 16 codewords are the zero word, nine of weight 4 and six of weight 6. Every codeword of weight 4 is a rectangle of four 1s, such as the array with rows 110, 110 and 000. It has at least two nonzero rows, each of even weight at least 2, so it has exactly two rows of weight 2. Each column has even weight, so a column that holds a 1 in one of those rows holds a 1 in the other, and the two rows are equal. Choosing the pair of rows and the pair of columns gives 3⋅3=9 rectangles, matching the count.
The rectangular parity of Distance, Detection and Correction is a product code. Its 4×4 data array, row parities, column parities and corner bit are the product of the (5,4,2) even-weight code with itself, a (25,16) code. The theorem gives its distance as 2⋅2=4, enough to correct one error and detect two at once. The rectangle argument applies unchanged and counts its codewords of weight 4 as (25)⋅(25)=10⋅10=100.
Product codes go back to Elias [4], and Lin and Costello give a textbook treatment [5]. Decoding a product code one row and one column at a time is the subject of Product and Concatenated Codes.
Figure 6 sets the codes of the chapter side by side, each bar its rate and each label its distance. The punctured (6,4,2) code has the highest rate, 4/6≈0.667, at distance 2. The shortened (5,2,3) code has the lowest, 0.400, and gained no distance for it. The product code has distance 4 at rate 4/9≈0.444, below the 0.500 of the extended Hamming code at the same distance.
Figure 6. Rate and minimum distance of the codes built from small codes in this chapter. A move to the right on a bar buys rate, a greener label buys distance, and no code here improves on the (8,4,4) code in both. Data: computed by ch24_charts.py in the companion repository.
At these sizes the product code looks wasteful. Its strength is that its distance is the product of its parts' distances, and the last exercise takes the (7,4,3) code times itself to distance 9.
Shortening costs nothing in hardware. A (71,64) encoder is a (127,120) encoder with 56 data inputs tied to 0, and a synthesis tool, the program that turns a circuit description into gates, removes every gate a constant input makes redundant. The counts that follow build one chain of gates per distinct check equation, with no partial sums shared. Figure 7 shows the effect on the (7,4) encoder, whose three checks each take a chain of two XOR gates, 6 in all. Tying m1 to 0 turns m1⊕m3 into m3 and m1⊕m2 into m2, so the (6,3) encoder has 4. Tying m2 to 0 as well leaves c5=c7=m3⊕m4 and c6=m4, so the (5,2) encoder has a single gate. A tool that also shares partial sums does better, building c7 as c5⊕m2 for 3 gates in the (6,3) encoder.
Figure 7. Shortening the (7,4) encoder to (6,3) by tying m1 to 0. The two dashed gates each pass their other input straight through and disappear, so 6 gates become 4.
Extending adds one XOR tree, and the derivation in Extending showed that for the (7,4) code the tree needs only the 2 gates of m1⊕m2⊕m3. Puncturing removes an output and any gates only that output used. Expurgating the (7,4) code keeps the messages whose overall parity m1⊕m2⊕m3 is 0, so m3 becomes m1⊕m2, one gate. Augmenting adds a message bit that inverts every output when it is 1, one XOR gate per output.
A product code reuses one small encoder. The (3,2,2)⊗(3,2,2) encoder needs one XOR gate for each of the 2 data rows and one for each of the 3 columns, the last of which encodes the column of row checks, so it has 2+3=5 gates. Building the five checks m1⊕m2, m3⊕m4, m1⊕m3, m2⊕m4 and m1⊕m2⊕m3⊕m4 as separate trees takes 1+1+1+1+3=7. The saving comes from the corner, which reuses the row checks.
Shortening and extending fit a Hamming code to a 64-bit word, the (u∣u+v) construction matched the extended Hamming code from two trivial parts, and the product code multiplied distances, each move with a proof of what it does to n, k and d.
The next chapter, Golay Codes, meets a perfect code that corrects more than one error, and its most used form is again an extended code, built by the extension of this chapter. Reed–Muller Codes then builds the doubling family of the (u∣u+v) construction, and Bounds on Codes asks how good any code of a given length and dimension can be, the yardstick for every operation here.
[1]Plotkin, Morris (1960). “Binary Codes with Specified Minimum Distance.” IRE Transactions on Information Theory, 6(4), pp. 445–450. doi:10.1109/TIT.1960.1057584
[2]Sloane, Neil J. A. and Whitehead, D. (1970). “New Family of Single-Error Correcting Codes.” IEEE Transactions on Information Theory, 16(6), pp. 717–719. doi:10.1109/TIT.1970.1054540
[3]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
[4]Elias, Peter (1954). “Error-free Coding.” Transactions of the IRE Professional Group on Information Theory, 4(4), pp. 29–37. doi:10.1109/TIT.1954.1057464
[5]Lin, Shu and Costello, Jr., Daniel J. (2004). “Error Control Coding: Fundamentals and Applications.” 2nd edition. Pearson Prentice Hall.
— Anirban
Hardware–software at the seam where compilers meet microcode.