Paper
Part IILinear Block Codes

Modifying and Combining Codes

November 15, 202651 min readbeginner

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)(u \mid u + v) construction and the product code. For each, the chapter proves what happens to the length nn, the dimension kk and the minimum distance dd, and counts what it costs in gates.

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

01.A Code for a 64-Bit Word

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−12^m - 1. With m=6m = 6 check bits the code is (63,57)(63, 57), which holds 57 data bits, seven too few. With m=7m = 7 it is (127,120)(127, 120), which holds 120 data bits, and 120−64=56120 - 64 = 56 of its data positions would sit idle on every access.

The fix takes two steps. Shortening the (127,120)(127, 120) code 56 times removes 56 data positions and leaves a (71,64)(71, 64) code, which still corrects one error. Extending that code by one overall parity bit gives (72,64)(72, 64), which also detects two errors. The rate, the fraction of stored bits that are data, falls from 120/127≈0.945120/127 \approx 0.945 to 64/72≈0.88964/72 \approx 0.889, but the memory stores exactly its 64 bits.

A code is described here by the triple (n,k,d)(n, k, d) of its length, dimension and minimum distance, the [n,k][n, k] of Linear Codes with the distance added. Words are strings of bits, ⊕\oplus adds two words position by position modulo 2, and w(c)w(c) is the weight of cc, 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)(7, 4, 3) Hamming code of Linear Codes, with generator matrix GG and parity-check matrix HH,

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

A message m1m2m3m4m_1 m_2 m_3 m_4 is sent as m1m2m3m4c5c6c7m_1 m_2 m_3 m_4 c_5 c_6 c_7, with check bits c5=m1⊕m3⊕m4c_5 = m_1 \oplus m_3 \oplus m_4, c6=m1⊕m2⊕m4c_6 = m_1 \oplus m_2 \oplus m_4 and c7=m2⊕m3⊕m4c_7 = m_2 \oplus m_3 \oplus m_4. The code has 16 codewords. One has weight 0, seven have weight 3, seven have weight 4 and one, the all-ones word 11111111111111, has weight 7.

02.The Operations at a Glance

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

OperationWhat it does to the codewordsLengthDimensionMinimum distanceExample in this chapter
Extendingappends the overall parity bitn+1n + 1kkd+1d + 1 for odd dd, dd for even dd(7,4,3)→(8,4,4)(7,4,3) \to (8,4,4)
Puncturingdeletes one positionn−1n - 1kk, when d>1d > 1dd or d−1d - 1(8,4,4)→(7,4,3)(8,4,4) \to (7,4,3)
Shorteningkeeps those with a 0 in one position, then deletes itn−1n - 1k−1k - 1at least dd(7,4,3)→(6,3,3)(7,4,3) \to (6,3,3)
Expurgatingkeeps the even-weight codewordsnnk−1k - 1at least dd, and even(7,4,3)→(7,3,4)(7,4,3) \to (7,3,4)
Augmentingadds the all-ones wordnnk+1k + 1min⁡(d,n−wmax⁡)\min(d, n - w_{\max})(7,3,4)→(7,4,3)(7,3,4) \to (7,4,3)
Lengtheningaugments, then extendsn+1n + 1k+1k + 1that of augmenting, raised to even(7,3,4)→(8,4,4)(7,3,4) \to (8,4,4)
Direct sumsets a codeword of each code side by siden1+n2n_1 + n_2k1+k2k_1 + k_2min⁡(d1,d2)\min(d_1, d_2)(4,3,2),(4,1,4)→(8,4,2)(4,3,2), (4,1,4) \to (8,4,2)
(u∣u+v)(u \mid u + v)follows uu with u⊕vu \oplus v2n2nk1+k2k_1 + k_2min⁡(2d1,d2)\min(2 d_1, d_2)(4,3,2),(4,1,4)→(8,4,4)(4,3,2), (4,1,4) \to (8,4,4)
Productencodes rows with one code, columns with the othern1n2n_1 n_2k1k2k_1 k_2d1d2d_1 d_2(3,2,2),(3,2,2)→(9,4,4)(3,2,2), (3,2,2) \to (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)(7, 4, 3) code. Puncturing the extended code at its new position gives the (7,4,3)(7, 4, 3) code back, and so does augmenting its expurgated code.

The single-code operations as moves between six codes built from the (7,4,3) Hamming code. Extend leads right to the (8,4,4) code and puncture leads back. Expurgate leads up to the (7,3,4) code and augment leads back down. Puncture at position 7 leads left to the (6,4,2) code. Shorten leads down to the (6,3,3) code and again to the (5,2,3) code. A dashed lengthen arrow, augment then extend, runs from the (7,3,4) code to the (8,4,4) code. (7,3,4) (6,4,2) (7,4,3) (8,4,4) (6,3,3) (5,2,3) expurgated punctured Hamming extended shortened shortened twice extend puncture puncture at 7 expurgate augment shorten shorten lengthen augment, then extend
Figure 1. The single-code operations as moves between the codes built from the Hamming code. Each box shows . Extending and puncturing at the new position undo each other, and so do expurgating and augmenting.

03.Extending

Take the codeword 10001101000110, the first row of GG, which has weight 3. Appending the XOR of its seven bits, 1⊕0⊕0⊕0⊕1⊕1⊕0=11 \oplus 0 \oplus 0 \oplus 0 \oplus 1 \oplus 1 \oplus 0 = 1, gives 1000110110001101, 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=1p = 1 when w(c)w(c) is odd and p=0p = 0 when w(c)w(c) is even. The weight of (c,p)(c, p) is w(c)+pw(c) + p. When w(c)w(c) is odd this is odd plus 1, and when w(c)w(c) is even it is even plus 0. Either way it is even. ■\blacksquare

Proof. The parity of a sum is the sum of the parities, p(a⊕b)=p(a)⊕p(b)p(a \oplus b) = p(a) \oplus p(b), because the XOR of all the bits of a⊕ba \oplus b is the XOR of all the bits of aa together with all the bits of bb. So the map c↦(c,p(c))c \mapsto (c, p(c)) is linear, and C^\hat{C}, its image, is a subspace. The first nn bits of (c,p(c))(c, p(c)) are cc itself, so different codewords have different images and C^\hat{C} holds 2k2^k words, which makes its dimension kk.

For a nonzero codeword cc, the weight of (c,p(c))(c, p(c)) is w(c)w(c) when w(c)w(c) is even and w(c)+1w(c) + 1 when w(c)w(c) is odd, so it is at least w(c)w(c), which is at least dd. Suppose dd is odd. Every nonzero extended codeword has even weight by the lemma and weight at least dd, so its weight is at least d+1d + 1, and a codeword of weight dd extends to one of weight exactly d+1d + 1. Suppose instead dd is even. A codeword of weight dd gains a 0 and keeps weight dd, and no extended codeword weighs less than dd. ■\blacksquare

The parity-check matrix of C^\hat{C} comes from HH in one move. Border HH with a column of zeros on the right, then add a row of ones underneath. For the (7,4,3)(7, 4, 3) code this gives

H^=[H01  1  ⋯  11]=[10111000110101000111001011111111].\hat{H} = \left[\begin{array}{c|c} H & 0 \\ \hline 1 \; 1 \; \cdots \; 1 & 1 \end{array}\right] = \begin{bmatrix} 1 & 0 & 1 & 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 & 0 & 1 & 0 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \end{bmatrix}.
(2)

Proof. Take an extended codeword (c,p)(c, p). Each of the first n−kn - k rows of H^\hat{H} is a row of HH followed by a 0, so it checks cc exactly as HH does and gives 0. The last row adds all n+1n + 1 bits, which is c1⊕⋯⊕cn⊕p=p⊕p=0c_1 \oplus \cdots \oplus c_n \oplus p = p \oplus p = 0. So H^\hat{H} sends every codeword of C^\hat{C} to zero.

For the rank, take any nonzero sum of rows of H^\hat{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 HH followed by a 0, and the rows of HH are independent. Either way the sum is nonzero, so the n−k+1n - k + 1 rows are independent. By the rank theorem of Matrices and Elimination over Finite Fields, the null space of H^\hat{H} has dimension (n+1)−(n−k+1)=k(n + 1) - (n - k + 1) = k. It contains C^\hat{C}, which also has dimension kk, so the two are equal. ■\blacksquare

For the (7,4,3)(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)(8, 4, 4) code. The extended generator matrix is GG with each row's parity appended, which gives the rows 1000110110001101, 0100011101000111, 0010101100101011 and 0001111000011110.

The four by eight parity-check matrix of the extended (8,4,4) code. The shaded upper left block is the parity-check matrix H of the (7,4) Hamming code, bordered on the right by a zero column and below by a row of eight ones, the overall parity check. 1234 5678 1011 100 1101 010 0111 001 000 1111 1111 H zero column overall parity check
Figure 2. The parity-check matrix of the extended code. The block 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)(7, 4) code,

c5⊕c6⊕c7=(m1⊕m3⊕m4)⊕(m1⊕m2⊕m4)⊕(m2⊕m3⊕m4).c_5 \oplus c_6 \oplus c_7 = (m_1 \oplus m_3 \oplus m_4) \oplus (m_1 \oplus m_2 \oplus m_4) \oplus (m_2 \oplus m_3 \oplus m_4).

Each of m1m_1, m2m_2 and m3m_3 appears twice and cancels, and m4m_4 appears three times and survives once, so c5⊕c6⊕c7=m4c_5 \oplus c_6 \oplus c_7 = m_4. The overall parity is then p=m1⊕m2⊕m3⊕m4⊕m4=m1⊕m2⊕m3p = m_1 \oplus m_2 \oplus m_3 \oplus m_4 \oplus m_4 = m_1 \oplus m_2 \oplus m_3. Written as coefficients on the message bits it is 11101110, and it is built from two two-input XOR gates fed straight from the message.

When dd is already even, extending buys nothing. Every codeword of the even-weight (4,3,2)(4, 3, 2) code, with generator rows 10011001, 01010101 and 00110011, has even weight, so every appended bit is 0. The extended rows are 1001010010, 0101001010 and 0011000110, and the distance stays 2.

04.Puncturing

Delete the last position of every codeword of the extended (8,4,4)(8, 4, 4) code. The overall parity bit goes, and what remains is the (7,4,3)(7, 4, 3) Hamming code, so puncturing at position 8 undoes the extension. Puncturing the (7,4,3)(7, 4, 3) code itself at position 7 costs more. The row 01000110100011, of weight 3, loses its final 1 and becomes 010001010001, of weight 2. The punctured code is (6,4,2)(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 nn to words of length n−1n - 1, so Pi(C)P_i(C), the image of CC, is a subspace. Two codewords with the same image differ only in position ii, so their sum is either the zero word or the word eie_i with a single 1 at position ii. The word eie_i has weight 1, which is less than dd, so it is not a codeword. The sum is therefore zero, distinct codewords have distinct images, and Pi(C)P_i(C) holds 2k2^k words, so its dimension is kk.

The image of a nonzero codeword cc has weight w(c)−ciw(c) - c_i, and it is nonzero because the map is one to one. Since cic_i is 0 or 1, this weight is at least w(c)−1≥d−1w(c) - 1 \ge d - 1. If some codeword of weight dd has ci=1c_i = 1, its image has weight exactly d−1d - 1, and d′=d−1d' = d - 1. If every codeword of weight dd has ci=0c_i = 0, those codewords keep weight dd, and every codeword of weight d+1d + 1 or more keeps weight at least dd, so d′=dd' = d. ■\blacksquare

In the (7,4,3)(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=217 \cdot 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 DD spanned by 11100001110000 and 00011110001111 has the four codewords 00000000000000, 11100001110000, 00011110001111 and 11111111111111, a (7,2,3)(7, 2, 3) code whose only word of weight 3 has a 0 in position 7. Punctured there, it becomes 000000000000, 111000111000, 000111000111 and 111111111111, a (6,2,3)(6, 2, 3) code with the same distance and a higher rate. The encoder of Pi(C)P_i(C) is the encoder of CC with output ii left unconnected, so puncturing a check bit also removes the gates that computed it.

05.Shortening

Keep only the codewords of the (7,4,3)(7, 4, 3) code that begin with 0, which are the eight with m1=0m_1 = 0, and delete that first position. Table 2 lists the eight words that remain. They form a (6,3,3)(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 GG with the first column removed, the rows 100011100011, 010101010101 and 001111001111.

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 m2m3m4m_2 m_3 m_4Codeword of the (7,4,3)(7,4,3) codeShortened codewordWeight
00000000000000000
00100011110011114
01000101010101013
01100110100110103
10001000111000113
10101011001011003
11001101101101104
11101110011110014

Source: reproduced by ch24_modifying_and_combining_codes.py.

Proof. Let KK be the set of codewords with ci=0c_i = 0. The sum of two words with a 0 in position ii again has a 0 there, so KK is a subspace. Fix a codeword aa with ai=1a_i = 1. Every codeword cc with ci=1c_i = 1 can be written c=a⊕(a⊕c)c = a \oplus (a \oplus c), and a⊕ca \oplus c has a 0 in position ii, so it lies in KK. The codewords therefore split into KK and the set a⊕Ka \oplus K of the same size, so ∣K∣=2k/2=2k−1|K| = 2^k / 2 = 2^{k-1}.

Deleting position ii from a word of KK removes a 0, so it changes no weight and sends different words to different words. The map is linear, so Si(C)S_i(C) is a subspace with 2k−12^{k-1} words, which makes its dimension k−1k - 1. Every nonzero word of Si(C)S_i(C) has the weight of a nonzero codeword of CC, which is at least dd. ■\blacksquare

Proof. Write H′H' for HH without column ii. For a word xx of length n−1n - 1, let x~\tilde{x} be the word of length nn made by inserting a 0 at position ii. The product Hx~TH \tilde{x}^{\mathsf T} is the sum of the columns of HH that x~\tilde{x} selects, and column ii is never selected, so Hx~T=H′xTH \tilde{x}^{\mathsf T} = H' x^{\mathsf T}. Now xx lies in Si(C)S_i(C) exactly when x~\tilde{x} lies in CC, which happens exactly when Hx~T=0H \tilde{x}^{\mathsf T} = 0, which is the same as H′xT=0H' x^{\mathsf T} = 0. So the null space of H′H' is Si(C)S_i(C), which has dimension k−1k - 1 by the shortening theorem. By the rank theorem of Matrices and Elimination over Finite Fields, H′H' then has rank (n−1)−(k−1)=n−k(n - 1) - (k - 1) = n - k, as many as its rows. ■\blacksquare

Deleting column 1 of HH gives the rows 011100011100, 101010101010 and 111001111001, 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=0m_2 = 0. The result is the (5,2,3)(5, 2, 3) code with generator rows 1010110101 and 0111101111, whose parity-check matrix is HH with its first two columns deleted, the rows 1110011100, 0101001010 and 1100111001. Its codewords are 0000000000, 1010110101, 0111101111 and 1101011010, 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)(72, 64) code by deleting 56 data columns from the parity-check matrix of the extended (128,120)(128, 120) code, and an exercise at the end proves that extending and shortening can be taken in either order.

06.Expurgating

Half the codewords of the (7,4,3)(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)(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 aa and bb hold there. Let t=w(a∧b)t = w(a \wedge b) be the number of positions where both hold a 1, and let ss be the number where exactly one of them does. The sum w(a)+w(b)w(a) + w(b) counts each of the ss positions once and each of the tt positions twice, so w(a)+w(b)=s+2tw(a) + w(b) = s + 2t. The word a⊕ba \oplus b has a 1 exactly at the ss positions, so w(a⊕b)=s=w(a)+w(b)−2tw(a \oplus b) = s = w(a) + w(b) - 2t. ■\blacksquare

For a=1000110a = 1000110 and b=0100011b = 0100011, of weight 3 each and sharing a 1 only in position 6, the lemma gives 3+3−2⋅1=43 + 3 - 2 \cdot 1 = 4, and indeed a⊕b=1100101a \oplus b = 1100101. The term 2t2t is even, so w(a⊕b)w(a \oplus b) and w(a)+w(b)w(a) + w(b) are both even or both odd.

Proof. Let EE be the set of even-weight codewords. By the lemma, the sum of two words of even weight has even weight, and EE contains the zero word, so EE is a subspace. Fix a codeword aa of odd weight. For any odd-weight codeword cc, the word a⊕ca \oplus c has even weight, again by the lemma, so it lies in EE, and c=a⊕(a⊕c)c = a \oplus (a \oplus c) lies in a⊕Ea \oplus E. The codewords therefore split into EE and a⊕Ea \oplus E, two sets of the same size, so ∣E∣=2k−1|E| = 2^{k-1} and the dimension is k−1k - 1. Every nonzero word of EE is a nonzero codeword of CC, so its weight is at least dd, and it is even. ■\blacksquare

For the (7,4,3)(7, 4, 3) code the odd-weight codeword can be a=1000110a = 1000110, and the expurgated code is the zero word with the seven words of weight 4. Its generator matrix is HH itself. Each row of HH has weight 4 and any two rows share exactly two 1s, so every row of HH has an even number of 1s in common with every row, which says HHT=0H H^{\mathsf T} = 0 and puts each row of HH 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⊥C^{\perp} in Linear Codes, so the expurgated Hamming code is the dual of the Hamming code, often called the (7,3,4)(7, 3, 4) simplex code. In a decoder, expurgation adds the all-ones row to the parity-check matrix, one parity check more.

07.Augmenting

Run expurgation backward. The (7,3,4)(7, 3, 4) code does not contain 11111111111111, since its words have weight 0 or 4. Adding 11111111111111 together with every sum 1111111⊕c1111111 \oplus c doubles the code to 16 words. Adding the all-ones word flips every bit, so the new words have weights 7−0=77 - 0 = 7 and 7−4=37 - 4 = 3. The result is the (7,4,3)(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 CC and 1\mathbf{1}, so it is a subspace. If some 1⊕c\mathbf{1} \oplus c were equal to a codeword c′c', then 1=c⊕c′\mathbf{1} = c \oplus c' would be a codeword, which it is not. So CC and 1⊕C\mathbf{1} \oplus C do not overlap, the augmented code holds 2k+12^{k+1} words, and its dimension is k+1k + 1.

Its nonzero words are of two kinds. Those in CC have weight at least dd, and some have weight exactly dd. A word 1⊕c\mathbf{1} \oplus c has a 1 exactly where cc has a 0, so its weight is n−w(c)n - w(c). It is never the zero word, because that would need c=1c = \mathbf{1}. The least of these weights is n−wmax⁡n - w_{\max}, reached at a codeword of largest weight. The least weight over both kinds is the smaller of the two minima. ■\blacksquare

For the (7,3,4)(7, 3, 4) code wmax⁡=4w_{\max} = 4, so da=min⁡(4,7−4)=3d_a = \min(4, 7 - 4) = 3, as the example found. The (5,2,3)(5, 2, 3) code from Shortening fares far worse. Its largest weight is 4, from 0111101111, so n−wmax⁡=1n - w_{\max} = 1 and the augmented code is (5,3,1)(5, 3, 1), with the weight-1 word 11111⊕01111=1000011111 \oplus 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)(7, 4, 3) code cannot be augmented at all, because 11111111111111 is already a codeword.

08.Lengthening

Augmenting adds a message bit and extending adds a check position, so taking both steps adds one of each and turns (n,k)(n, k) into (n+1,k+1)(n + 1, k + 1). That pair of steps is called lengthening. Lengthening the (7,3,4)(7, 3, 4) code first augments it to the (7,4,3)(7, 4, 3) code and then extends that to the (8,4,4)(8, 4, 4) code.

Proof. The theorem on augmenting turns CC into a linear (n,k+1,da)(n, k + 1, d_a) code. The theorem on extending turns that into a linear (n+1,k+1)(n + 1, k + 1) code whose distance is da+1d_a + 1 when dad_a is odd and dad_a when dad_a is even. ■\blacksquare

For the (7,3,4)(7, 3, 4) code, da=3d_a = 3 is odd, so dℓ=4d_\ell = 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.

09.The Direct Sum

Place a codeword of the even-weight (4,3,2)(4, 3, 2) code beside a codeword of the (4,1,4)(4, 1, 4) repetition code, whose codewords are 00000000 and 11111111. Each of the 8⋅2=168 \cdot 2 = 16 pairs gives a word of length 8, and together they form an (8,4,2)(8, 4, 2) code. Its distance is only 2, because 1100000011000000 is a codeword.

Weight Distributions and Undetected Errors defined the weight enumerator WC(x,y)=∑c∈Cxn−w(c)yw(c)W_C(x, y) = \sum_{c \in C} x^{n - w(c)} y^{w(c)}, in which xx counts the zeros of a codeword and yy its ones. Setting x=1x = 1 keeps only the ones, and this section writes WC(y)W_C(y) for that specialization WC(1,y)=∑c∈Cyw(c)W_C(1, y) = \sum_{c \in C} y^{w(c)}, whose coefficient of yjy^j counts the codewords of weight jj.

Proof. Adding two words of the direct sum adds their halves separately, (a∣b)⊕(a′∣b′)=(a⊕a′∣b⊕b′)(a \mid b) \oplus (a' \mid b') = (a \oplus a' \mid b \oplus b'), and the halves stay in C1C_1 and C2C_2, so the direct sum is a subspace. A pair (a,b)(a, b) can be read back from (a∣b)(a \mid b), so the code holds 2k1⋅2k2=2k1+k22^{k_1} \cdot 2^{k_2} = 2^{k_1 + k_2} words. The weight of (a∣b)(a \mid b) is w(a)+w(b)w(a) + w(b). In a nonzero word at least one half is nonzero, so its weight is at least d1d_1 or at least d2d_2, and in either case at least min⁡(d1,d2)\min(d_1, d_2). The words (a∣0)(a \mid 0) with w(a)=d1w(a) = d_1 and (0∣b)(0 \mid b) with w(b)=d2w(b) = d_2 reach both values, so the minimum is exactly min⁡(d1,d2)\min(d_1, d_2). For the enumerator,

∑a∈C1∑b∈C2yw(a)+w(b)=(∑a∈C1yw(a))(∑b∈C2yw(b)).■\sum_{a \in C_1} \sum_{b \in C_2} y^{w(a) + w(b)} = \Big( \sum_{a \in C_1} y^{w(a)} \Big) \Big( \sum_{b \in C_2} y^{w(b)} \Big). \qquad \blacksquare

The even-weight (4,3,2)(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,(1 + 6y^2 + y^4)(1 + y^4) = 1 + 6y^2 + 2y^4 + 6y^6 + y^8 ,

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 DD of Puncturing was a direct sum all along, of the (3,1,3)(3, 1, 3) and (4,1,4)(4, 1, 4) repetition codes, which is why its distance is min⁡(3,4)=3\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)(8, 4, 2) direct sum and the (8,4,4)(8, 4, 4) extended Hamming code have the same rate, 4/8=0.5004/8 = 0.500, yet the second has twice the distance. The next construction uses the same two parts and reaches distance 4.

10.The (u∣u+v)(u \mid u + v) Construction

Take C1C_1 to be the even-weight (4,3,2)(4, 3, 2) code and C2C_2 the (4,1,4)(4, 1, 4) repetition code again, but this time send a word u∈C1u \in C_1 followed by u⊕vu \oplus v with v∈C2v \in C_2. For u=0110u = 0110 and v=1111v = 1111 the codeword is 0110100101101001. 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)(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)−2 w(u∧v)w(u \oplus v) = w(u) + w(v) - 2\, w(u \wedge v). The word u∧vu \wedge v has a 1 only where uu does, so w(u∧v)≤w(u)w(u \wedge v) \le w(u). Substituting, w(u⊕v)≥w(u)+w(v)−2 w(u)=w(v)−w(u)w(u \oplus v) \ge w(u) + w(v) - 2\, w(u) = w(v) - w(u). ■\blacksquare

Proof. The sum of two codewords is (u⊕u′∣(u⊕u′)⊕(v⊕v′))(u \oplus u' \mid (u \oplus u') \oplus (v \oplus v')), which is the codeword built from u⊕u′∈C1u \oplus u' \in C_1 and v⊕v′∈C2v \oplus v' \in C_2, so the code is a subspace. From a codeword (x∣y)(x \mid y) the pair is recovered as u=xu = x and v=x⊕yv = x \oplus y, so different pairs give different codewords and there are 2k1+k22^{k_1 + k_2} of them.

For the upper bound, two codewords suffice. With w(u)=d1w(u) = d_1 and v=0v = 0, the codeword (u∣u)(u \mid u) has weight 2d12 d_1. With u=0u = 0 and w(v)=d2w(v) = d_2, the codeword (0∣v)(0 \mid v) has weight d2d_2. So d≤min⁡(2d1,d2)d \le \min(2 d_1, d_2).

For the lower bound, take a nonzero codeword (u∣u⊕v)(u \mid u \oplus v) and split into two cases. If v=0v = 0, then u≠0u \ne 0 and the weight is 2 w(u)≥2d12\, w(u) \ge 2 d_1. If v≠0v \ne 0, the lemma gives w(u)+w(u⊕v)≥w(u)+w(v)−w(u)=w(v)≥d2w(u) + w(u \oplus v) \ge w(u) + w(v) - w(u) = w(v) \ge d_2. In both cases the weight is at least min⁡(2d1,d2)\min(2 d_1, d_2). ■\blacksquare

For the length-4 codes, min⁡(2⋅2,4)=4\min(2 \cdot 2, 4) = 4, and the two words of the upper bound are 1001100110011001, from u=1001u = 1001, and 0000111100001111, from v=1111v = 1111. A generator matrix stacks (g∣g)(g \mid g) for each generator row gg of C1C_1 above (0∣g)(0 \mid g) for each generator row of C2C_2, which gives the rows 1001100110011001, 0101010101010101, 0011001100110011 and 0000111100001111.

Encoding u = 0110 and v = 1111 into the (u | u + v) codeword. Four cells hold u, and four cells holding v sit below them. The whole of u is copied into the left half of an eight-bit codeword. Each bit of u and the matching bit of v feed one of four XOR gates, and the gate outputs, 1001, form the right half. The codeword reads 0110 1001. 0110 1111 u = 0110 v = 1111 u + v = 1001 copy of u 0110 1001 left half: u right half: u + v codeword 0110 1001
Figure 3. Encoding and into the codeword . The left half is 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 C1C_1 and C2C_2. Figure 4 compares the weight distributions of the two constructions, which share their parts but not their least weight.

Weight distributions of the direct sum and of the (u | u + v) code built from the (4,3,2) and (4,1,4) codes codeword weight number of codewords 0 4 8 12 16 0 1 1 1 2 6 3 4 2 14 5 6 6 7 8 1 1 direct sum, d = 2 (u | u + v), d = 4
Figure 4. Weight distributions of the direct sum and of the code built from the same and codes. The direct sum has six words of weight 2, and the 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.

11.Product Codes

Arrange four data bits as a 2×22 \times 2 array with rows 1010 and 1111. Encode each row with the (3,2,2)(3, 2, 2) even-weight code, which appends the XOR of its two bits, so 1010 becomes 101101 and 1111 becomes 110110. 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×33 \times 3 array drawn in Figure 5, with rows 101101, 110110 and 011011, in which every row and every column has even weight. Read row by row, it is the 9-bit codeword 101110011101110011.

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.

A codeword of the (3,2,2) by (3,2,2) product code as a three by three array of bits. The data 10 and 11 fill the upper left two by two block. The shaded third column holds the row checks 1 and 0, and the shaded third row holds the column checks 0 and 1. The corner bit 1, outlined in green, is the check on checks, reached by an arrow from the row checks and an arrow from the column checks. The rows read 101, 110 and 011. 101 110 01 1 data row checks column checks check on checks
Figure 5. The product codeword for the data rows and . Row checks and column checks both lead to the same corner bit.

Multiplying on the right by G2G_2 turns each row of MM into its C2C_2 codeword. Multiplying on the left by G1TG_1^{\mathsf T} does the same to each column with C1C_1, since G1TyTG_1^{\mathsf T} y^{\mathsf T} is the transpose of yG1y G_1.

Proof. Rows first gives G1T(MG2)G_1^{\mathsf T} (M G_2) and columns first gives (G1TM)G2(G_1^{\mathsf T} M) G_2. Matrix multiplication is associative, as Matrices and Elimination over Finite Fields showed, so the two arrays are equal. Row rr of XX is row rr of G1TMG_1^{\mathsf T} M times G2G_2, a C2C_2 codeword. Column ss of XX is G1TG_1^{\mathsf T} times column ss of MG2M G_2, a C1C_1 codeword. ■\blacksquare

Proof. The array X=G1TMG2X = G_1^{\mathsf T} M G_2 depends linearly on MM, so the set of arrays is a subspace of the words of length n1n2n_1 n_2. To show that different data arrays give different codewords, suppose G1TMG2=0G_1^{\mathsf T} M G_2 = 0 and let Y=MG2Y = M G_2. Each column yy of YY satisfies G1Ty=0G_1^{\mathsf T} y = 0, which says that the sum of the rows of G1G_1 selected by yy is zero. The rows of G1G_1 are independent, so y=0y = 0, and therefore Y=0Y = 0. Then every row mm of MM satisfies mG2=0m G_2 = 0, and the rows of G2G_2 are independent, so m=0m = 0 and M=0M = 0. The code therefore holds 2k1k22^{k_1 k_2} arrays, and its dimension is k1k2k_1 k_2.

For the upper bound, pick a∈C1a \in C_1 of weight d1d_1 and b∈C2b \in C_2 of weight d2d_2, with messages α\alpha and β\beta such that a=αG1a = \alpha G_1 and b=βG2b = \beta G_2. The data array M=αTβM = \alpha^{\mathsf T} \beta gives X=G1TαTβG2=aTbX = G_1^{\mathsf T} \alpha^{\mathsf T} \beta G_2 = a^{\mathsf T} b, the array with a 1 in row rr and column ss exactly when ar=1a_r = 1 and bs=1b_s = 1. That array has weight d1d2d_1 d_2.

For the lower bound, let XX be a nonzero codeword, and choose a column ss that holds a 1. By the lemma, column ss is a nonzero codeword of C1C_1, so it has at least d1d_1 ones, and at least d1d_1 rows of XX are nonzero. Each of those rows is a nonzero codeword of C2C_2 and has weight at least d2d_2. So w(X)≥d1d2w(X) \ge d_1 d_2. ■\blacksquare

The product of the (3,2,2)(3, 2, 2) code with itself is therefore a (9,4,4)(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 110110, 110110 and 000000. 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=93 \cdot 3 = 9 rectangles, matching the count.

The rectangular parity of Distance, Detection and Correction is a product code. Its 4×44 \times 4 data array, row parities, column parities and corner bit are the product of the (5,4,2)(5, 4, 2) even-weight code with itself, a (25,16)(25, 16) code. The theorem gives its distance as 2⋅2=42 \cdot 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 (52)⋅(52)=10⋅10=100\binom{5}{2} \cdot \binom{5}{2} = 10 \cdot 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.

12.Rate and Distance Together

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)(6, 4, 2) code has the highest rate, 4/6≈0.6674/6 \approx 0.667, at distance 2. The shortened (5,2,3)(5, 2, 3) code has the lowest, 0.4000.400, and gained no distance for it. The product code has distance 4 at rate 4/9≈0.4444/9 \approx 0.444, below the 0.5000.500 of the extended Hamming code at the same distance.

Rate and minimum distance of nine codes built from the small codes of this chapter rate k/n 0 0.25 0.5 0.75 1 (6,4,2) punctured 0.667 d = 2 (7,4,3) Hamming 0.571 d = 3 (8,4,4) extended 0.500 d = 4 (6,3,3) shortened 0.500 d = 3 (8,4,2) direct sum 0.500 d = 2 (8,4,4) (u | u + v) 0.500 d = 4 (9,4,4) product 0.444 d = 4 (7,3,4) expurgated 0.429 d = 4 (5,2,3) twice shortened 0.400 d = 3
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 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)(7, 4, 3) code times itself to distance 9.

13.The Operations in Hardware

Shortening costs nothing in hardware. A (71,64)(71, 64) encoder is a (127,120)(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)(7, 4) encoder, whose three checks each take a chain of two XOR gates, 6 in all. Tying m1m_1 to 0 turns m1⊕m3m_1 \oplus m_3 into m3m_3 and m1⊕m2m_1 \oplus m_2 into m2m_2, so the (6,3)(6, 3) encoder has 4. Tying m2m_2 to 0 as well leaves c5=c7=m3⊕m4c_5 = c_7 = m_3 \oplus m_4 and c6=m4c_6 = m_4, so the (5,2)(5, 2) encoder has a single gate. A tool that also shares partial sums does better, building c7c_7 as c5⊕m2c_5 \oplus m_2 for 3 gates in the (6,3)(6, 3) encoder.

The encoder of the (7,4) Hamming code as three chains of two-input XOR gates, one chain for each check bit. Check bit c5 is m1 XOR m3 XOR m4, c6 is m1 XOR m2 XOR m4, and c7 is m2 XOR m3 XOR m4. The input m1 is tied to 0, so the two gates that take m1 are drawn dashed in gray and labeled removed, since each passes its other input straight through. Four solid gates remain, and the outputs c5, c6 and c7 leave on the right. m1m3m4 m1m2m4 m2m3m4 tied to 0 tied to 0 removed removed c5 c6 c7 now m3 XOR m4 now m2 XOR m4 unchanged dashed gray: a gate that passes its other input through once m1 is 0 6 gates become 4
Figure 7. Shortening the encoder to by tying 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)(7, 4) code the tree needs only the 2 gates of m1⊕m2⊕m3m_1 \oplus m_2 \oplus m_3. Puncturing removes an output and any gates only that output used. Expurgating the (7,4)(7, 4) code keeps the messages whose overall parity m1⊕m2⊕m3m_1 \oplus m_2 \oplus m_3 is 0, so m3m_3 becomes m1⊕m2m_1 \oplus m_2, 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)(3, 2, 2) \otimes (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=52 + 3 = 5 gates. Building the five checks m1⊕m2m_1 \oplus m_2, m3⊕m4m_3 \oplus m_4, m1⊕m3m_1 \oplus m_3, m2⊕m4m_2 \oplus m_4 and m1⊕m2⊕m3⊕m4m_1 \oplus m_2 \oplus m_3 \oplus m_4 as separate trees takes 1+1+1+1+3=71 + 1 + 1 + 1 + 3 = 7. The saving comes from the corner, which reuses the row checks.

14.Looking Ahead

Shortening and extending fit a Hamming code to a 64-bit word, the (u∣u+v)(u \mid 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 nn, kk and dd.

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)(u \mid 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.

15.Worked Examples

16.Exercises

References

  1. [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. [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. [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. [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. [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.

FeedbackBook modePaper
error-correction-codinglinear-block-codes