A linear code is a set of binary words closed under XOR. The chapter builds one from a generator and a parity-check matrix, proves that distance is the smallest weight and reads it off the columns of H.
The previous chapter, Matrices and Elimination over Finite Fields, row-reduced binary matrices, proved the rank theorem and put a generator matrix into systematic form. This chapter turns those tools into the definition of a code. A linear code is a set of binary words closed under XOR, which makes it a subspace in the sense of Vector Spaces over Finite Fields. A generator matrix lists every codeword as a combination of a few basis words, and a parity-check matrix lists the checks that every codeword passes.
In hardware the generator becomes a bank of XOR gates, one small tree per parity bit, and the columns of the parity-check matrix reveal how many errors the code can detect and correct without a single codeword being listed. The running example is the (7,4) Hamming code of Hamming's 1950 paper [1], which carries 4 message bits in 7 transmitted bits, with its positions reordered to put the message first.
Take the four words 00000, 01101, 10110 and 11011 of length 5, and XOR any two of them position by position. The result is again one of the four. For instance 01101⊕10110=11011, and 10110⊕11011=01101. Figure 1 lists all 16 sums. Call this set C5. Groups and Cosets met it as a subgroup, and Vector Spaces over Finite Fields as a subspace.
Figure 1. The XOR table of C5. Every sum of two codewords is a codeword, so C5 is closed under XOR. The odd-weight words of length 3 are not, because 001⊕010=011 falls outside the set.
Most sets of words fail this test. The four words of length 3 with an odd number of ones, 001, 010, 100 and 111, fail at once, because 001⊕010=011 has two ones. The four words with an even number of ones, 000, 011, 101 and 110, pass. The weight of x⊕y is w(x)+w(y) minus twice the number of positions where both words have a 1, so two even weights always give an even weight. Closure is rare. Of the 255 nonempty sets of words of length 3, only 16 are closed under XOR, every one of them contains 000, and their sizes are powers of two, one of size 1, seven of size 2, seven of size 4 and one of size 8.
Proof. Suppose C is nonempty and closed under XOR, and pick any c in C. Then c⊕c=0 lies in C. The only scalars in GF(2) are 0 and 1, and 0⋅c=0 and 1⋅c=c both lie in C, so C is closed under multiplication by scalars. Addition in GF(2)n is XOR, so C is closed under addition by hypothesis. The subspace test of Vector Spaces over Finite Fields now makes C a subspace. Conversely, a subspace is closed under addition, and addition is XOR. ■
Slepian treated binary codes closed under addition as groups in 1956 [2], and the lemma is why the group view and the subspace view describe the same codes. Over a larger field such as GF(4), closure under addition does not give closure under every scalar, so a linear code there is defined directly as a subspace.
Two words of C5, g1=10110 and g2=01101, produce all four codewords. The combination 0⋅g1+0⋅g2 is 00000, the words g2 and g1 are themselves codewords, and g1+g2=11011. Stack them as the rows of a matrix
G5=[1001111001]
and write a message as a row m=(m1,m2). The product mG5=m1g1+m2g2 is a codeword, and the four messages 00, 01, 10 and 11 give the four codewords 00000, 01101, 10110 and 11011. Read one column at a time, as Matrices and Elimination over Finite Fields read such products, entry j of mG5 is the parity sum of the message bits that column j of G5 selects. Column 3 holds a 1 in both rows, so the third bit is m1+m2, and the whole codeword is (m1,m2,m1+m2,m1,m2). Two message bits travel in five channel bits, a rate of 2/5=0.4.
Proof. The product mG is the combination m1g1+⋯+mkgk of the rows g1,…,gk of G. The rows span C, so every codeword is such a combination, and every codeword is mG for some message m. If mG=m′G, then (m−m′)G=0, a combination of the rows with coefficients mi−mi′ that equals zero. The rows are independent, so every coefficient is zero and m=m′. The map is therefore a one-to-one correspondence between the 2k messages and the codewords. ■
A code has many generator matrices, one for each basis. The rows 11011 and 01101 also span C5, as a worked example shows. Different generators pair messages with codewords differently, but the set of codewords, and every property this chapter measures, stays the same.
The running example of the chapter is the [7,4] code with generator
G=1000010000100001101111010111
which is the (7,4) Hamming code. Its four rows are independent, since its first four columns form the identity, so it holds 24=16 codewords. The message 1011 adds rows 1, 3 and 4, and 1000110⊕0010101⊕0001111=1011100.
A receiver needs a quick test of whether a received word is a codeword. Look again at the codeword (m1,m2,m1+m2,m1,m2) of C5. Bit 3 is the sum of bits 1 and 2, bit 4 equals bit 1, and bit 5 equals bit 2. Over GF(2) the equation a=b says the same as a+b=0, so the three rules read
c1+c2+c3=0,c1+c4=0,c2+c5=0.
Each rule is a parity check, a set of positions that must hold an even number of ones. Writing each check as the row of positions it selects gives the matrix
H5=110101100010001.
The codeword 11011 passes all three checks, since 1+1+0, 1+1 and 1+1 are all 0. The word 10111 fails the third, since bits 2 and 5 give 0+1=1.
Words in this chapter are written as rows, and the checks act on them as columns. The transpose AT of an m×n matrix A is the n×m matrix whose rows are the columns of A, so (AT)ij=Aji. The transpose of G5 is the 5×2 matrix with rows 10, 01, 11, 10 and 01, and the transpose xT of a word x is the same bits stood up as a column. All three checks at once then say H5xT=0. Matrices and Elimination over Finite Fields wrote Hr, with r already a column.
Proof. Entry (i,j) of ABT is ∑lAil(BT)lj=∑lAilBjl, which is the dot product of row i of A with row j of B. So ABT is zero exactly when all of these dot products are zero. The dot product is symmetric, by the lemma of Vector Spaces over Finite Fields, so bj⋅ai=ai⋅bj=0 for every pair, which is the statement BAT=0. ■
In particular, entry i of HxT is hi⋅x, check i applied to the word x.
Proof. By the lemma, each row hi of H is orthogonal to each row gl of G. A codeword is c=m1g1+⋯+mkgk, and the dot product is bilinear, so hi⋅c=m1(hi⋅g1)+⋯+mk(hi⋅gk)=0. Every check passes, so C lies inside the null space of H. The rank theorem of Matrices and Elimination over Finite Fields says the null space of H holds 2n−(n−k)=2k words, and C holds 2k codewords by the theorem that encoding is one to one. A finite set inside another set of the same size is all of it, so C equals the null space of H. ■
For C5, G5H5T is the 2×3 zero matrix and H5 has rank 3, since its last three columns form the identity. Of the 32 words of length 5, exactly the four codewords satisfy H5xT=0. The word 10111 gives H5xT=001, which flags it as damaged. Groups and Cosets called the map x↦HxT a syndrome, and here it only answers yes or no. A receiver checks n−k parity sums for zero instead of comparing the word with all 2k codewords.
The generator of the (7,4) code has the form G=[I4∣P], an identity block followed by
P=101111010111.
Bit 5 of a codeword is m1+m3+m4, read down the first column of P. The first four bits of the codeword are the message, ci=mi for i≤4, so the rule says c5=c1+c3+c4, which over GF(2) is the check c1+c3+c4+c5=0. The other two columns of P give the checks c1+c2+c4+c6=0 and c2+c3+c4+c7=0. Each check is one column of P laid on its side, with a single 1 added in the place of its parity bit. The three checks together form
Figure 2. The systematic generator G=[I4∣P] of the (7,4) Hamming code and its parity-check matrix H=[PT∣I3], both built from the same block P.
Proof. Row i of G is the word ei of length k, with a single 1 in place i, followed by row i of P. Row j of H is column j of P followed by the word of length n−k with a single 1 in place j. Their dot product has at most two nonzero terms. In the first k positions only place i of ei holds a 1, and it meets entry i of column j of P, which is Pij. In the last n−k positions only place j of the identity row holds a 1, and it meets entry j of row i of P, again Pij. The dot product is Pij+Pij=0, so GHT=0 by the lemma on transposes. The last n−k columns of H form In−k, so in a combination of the rows of H those columns show the coefficients themselves, and a combination equal to zero has every coefficient zero. So H has rank n−k, and the theorem that the checks define the code finishes the proof. ■
Over GF(q) with q>2 the same argument works for H=[−PT∣In−k], where the dot product becomes −Pij+Pij=0. Over GF(2), where −1=1, the sign disappears.
The companion script checks the formula for every one of the 212=4096 choices of a 4×3 block P, confirming each time that the row space of G and the null space of H are the same 16 words. For C5 the block P5 has rows 110 and 101, and [P5T∣I3] is exactly the matrix H5 found earlier by reasoning about the bits. A designer specifies only P, and the encoder and the checker are both read from it.
With G=[Ik∣P] the product mG splits into two pieces,
c=m[Ik∣P]=[m∣mP].
(4)
The first k bits of the codeword are the message itself, and the last n−k are parity bits computed from it. A generator of this shape, and the encoding it gives, is called systematic. Table 1 lists all 16 codewords of the (7,4) code in the order of their messages, and in every row the first four bits of the codeword repeat the message.
Table 1. The sixteen codewords of the (7,4) Hamming code in message order, with their weights
Message
Codeword
Weight
Message
Codeword
Weight
0000
0000000
0
1000
1000110
3
0001
0001111
4
1001
1001001
3
0010
0010101
3
1010
1010011
4
0011
0011010
3
1011
1011100
4
0100
0100011
3
1100
1100101
4
0101
0101100
3
1101
1101010
4
0110
0110110
4
1110
1110000
3
0111
0111001
4
1111
1111111
7
Source: reproduced by ch17_linear_codes.py.
A systematic generator costs nothing in error protection, since it changes only which message is paired with which codeword. The encoder passes the message bits straight through as wires, and a receiver that finds HrT=0 reads the message off the first k bits of r with no arithmetic.
Lin and Costello put the parity bits first instead, writing [P∣Ik][3]. The two layouts differ by a reordering of positions, and a reordering is always enough to make a code systematic.
Proof. By the lemma of Vector Spaces over Finite Fields, C has an information set, k positions on which the codewords run through all 2k patterns, each exactly once. Reorder the positions so that the information set comes first. For each i from 1 to k, exactly one codeword gi shows the pattern ei on the first k positions. Stack g1,…,gk as the rows of a matrix. Its first k columns form Ik, so it has the form [Ik∣P]. Its rows are independent, because the combination with coefficients a1,…,ak shows the word (a1,…,ak) in the first k positions and is zero only when every ai is zero. These are k independent codewords in a code of dimension k, so they form a basis, and the matrix is a generator. ■
Matrices and Elimination over Finite Fields reached the same conclusion by moving pivot columns to the front. The reordered code is an equivalent code in the sense of a later section, with the same weights and the same distance.
Read the columns of P as wiring instructions. Column 1 selects m1, m3 and m4, and the other two columns select their own three bits, so
c5=m1⊕m3⊕m4,c6=m1⊕m2⊕m4,c7=m2⊕m3⊕m4.
Each parity bit is the XOR of three message bits, and a two-input XOR gate combines two signals at a time, so each parity bit needs two gates. Figure 3 draws the encoder. The message bits run straight through to c1 to c4 as wires, and three trees of two gates each produce the parity bits, six gates in all. When the message 1011 enters, the trees compute c5=1⊕1⊕1=1, c6=1⊕0⊕1=0 and c7=0⊕1⊕1=0, and the codeword 1011100 comes out.
Figure 3. The encoder c=mG of the (7,4) code as three XOR trees, one per parity bit, with six two-input gates and two gate delays. The message 1011 becomes the codeword 1011100.
Proof. Each gate takes two signals and returns one, so it lowers by exactly one the number of signals still to be combined. The tree starts with s signals and ends with one, so it uses s−1 gates. For the depth, a tree whose longest path has D gates has at most 2D inputs. That holds for D=0, a bare wire with a single input, and a tree of depth D+1 is one output gate fed by two trees of depth at most D, which together have at most 2D+2D=2D+1 inputs. So s≤2D, which gives D≥log2s, and since D is a whole number, D≥⌈log2s⌉. A balanced tree pairs off the signals at each level, turning s signals into ⌈s/2⌉, so after D levels ⌈s/2D⌉ remain, and that is 1 as soon as 2D≥s. So it finishes in ⌈log2s⌉ levels. ■
Every column of P has weight 3, so each tree has 3−1=2 gates and ⌈log23⌉=2 levels, and the whole encoder costs six gates and two gate delays, with no clock and no memory. The encoder of C5 needs one gate, c3=m1⊕m2, since c4=m1 and c5=m2 are plain wires.
Trees can also share work. The sum m1⊕m4 appears in both c5 and c6, so one gate can compute it once for both. The network
t=m1⊕m4,c5=t⊕m3,c6=t⊕m2,u=m2⊕m3,c7=u⊕m4
uses five gates and is still two levels deep, and the companion script confirms that it agrees with the six-gate encoder on all 16 messages. The theorem settles that the weight of each column of P sets the cost of its tree, so among codes with equal distance a designer prefers light columns, a theme that returns in SECDED and Hsiao Codes.
Distance, Detection and Correction showed that a code with minimum distance d, the smallest number of positions in which two different codewords differ, detects every pattern of up to d−1 errors and corrects every pattern of up to ⌊(d−1)/2⌋. By brute force, finding d means comparing all (216)=120 pairs of codewords of the (7,4) code, and M codewords form M(M−1)/2 pairs. A linear code allows a shortcut.
The weights in Table 1 are 0 once, 3 seven times, 4 seven times and 7 once, and the smallest of the 120 distances, which the companion script computes, is 3, the smallest nonzero weight. Distance, Detection and Correction proved that this holds for every code closed under XOR, and the theorem below restates it for linear codes with one addition.
Proof. Two words differ in a position exactly when their XOR has a 1 there, so d(c,c′)=w(c⊕c′). If c and c′ are different codewords, then c⊕c′ is a codeword by closure and is not zero, so every distance between distinct codewords is the weight of a nonzero codeword, and d is at least the smallest nonzero weight. In the other direction, 0 is a codeword, and a nonzero codeword c lies at distance d(c,0)=w(c) from it, so the smallest nonzero weight is itself a distance, and d is at most that weight. For the second claim, fix a codeword c. The map c′↦c⊕c′ sends C into C by closure, and applying it twice returns c′, so it is a one-to-one correspondence of C with itself. The distance d(c,c′)=w(c⊕c′) therefore runs through the weights of all the codewords, each exactly once. ■
So every codeword sees the same neighborhood. From any codeword of the (7,4) code, one codeword lies at distance 0, seven at distance 3, seven at distance 4 and one at distance 7. Fifteen weights replace 120 distances and give d=3, so the code detects any two errors and corrects any single error. The weights of C5 are 3, 3 and 4, so C5 also has d=3.
The choice of P matters. Matrices and Elimination over Finite Fields built a [7,4] code with the systematic generator S of its Systematic Form section, whose rows 1000110, 0100011, 0010100 and 0001111 differ from G only in the last bit of row 3. Its row 0010100 has weight 2, and its weights are 0 once, 2 once, 3 six times, 4 five times, 5 twice and 6 once, so it detects a single error but cannot correct one. Figure 4 sets the two weight distributions side by side.
Figure 4. Weight distributions of two [7,4] codes whose generators differ in one bit. The Hamming code has minimum weight 3, and the code of Matrices and Elimination over Finite Fields has minimum weight 2. Data: computed by ch17_charts.py in the companion repository.
Minimum weight still asks for all 2k codewords to be listed. The parity-check matrix offers a test that lists none. Take x=1000110, with ones in positions 1, 5 and 6. Each check row of H adds up the bits in the positions it covers, so HxT is the sum of the columns of H at the positions where x has a 1. Those columns, read from top to bottom, are 110, 100 and 010, and their sum is 000. So x is a codeword, and its weight is 3. Figure 5 shows the three columns.
Figure 5. HxT is the sum of the columns of H at the ones of x. Columns 1, 5 and 6 add to zero, so 1000110 is a codeword, and because no column is zero and no two are equal, the minimum distance is 3.
Proof. By the column view of a matrix-vector product in Matrices and Elimination over Finite Fields, HxT=x1h1+⋯+xnhn. Each xj is 0 or 1, so the terms with xj=0 vanish, and the rest are the columns hj with xj=1. That proves the formula, and with it the test for a codeword, since C is the null space of H. A nonzero codeword of weight w therefore gives a nonempty set of w columns that add to zero. In the other direction, a nonempty set of w columns that add to zero gives the word with ones in exactly those positions, a nonzero codeword of weight w. Since C has a nonzero codeword, sets of both kinds exist, so the smallest nonzero weight of a codeword equals the smallest size of a nonempty set of columns that add to zero, and by the previous theorem that number is d. ■
Proof. By the theorem, d≥3 means that no single column and no pair of distinct columns adds to zero. A single column adds to zero exactly when it is the zero column. Two columns add to zero exactly when they are equal, because over GF(2) the equation hi+hj=0 says the same as hi=hj. ■
The seven columns of the (7,4) matrix H are 110, 011, 101, 111, 100, 010 and 001. They are all seven nonzero words of length 3, so none is zero and no two are equal, and d≥3. Columns 1, 5 and 6 add to zero, so d=3, read straight off the matrix.
The columns of H5 are 110, 101, 100, 010 and 001, again nonzero and distinct, and columns 1, 3 and 4 add to zero, so C5 has d=3. The code of Matrices and Elimination over Finite Fields has a parity-check matrix with columns 110, 011, 100, 111, 100, 010 and 001, and columns 3 and 5 are both 100, so d=2 at a glance.
Hamming Codes and Perfect Codes takes this column rule as far as it goes.
The three checks of the (7,4) code fit into a picture of three overlapping circles, one per check, each holding the positions its row of H covers. Circle 1 holds positions 1, 3, 4 and 5, circle 2 holds 1, 2, 4 and 6, and circle 3 holds 2, 3, 4 and 7. Position 4 is in all three circles, positions 1, 2 and 3 are each in two, and positions 5, 6 and 7 are each in one, so each of the seven regions holds one position. Figure 6 writes the codeword 1011100 into the regions, with four ones in circle 1 and two in each of the others.
Figure 6. The (7,4) Hamming code as three circles, one per check. A word is a codeword exactly when every circle holds an even number of ones, as 1011100 does.
Proof. Circle i holds the positions where row i of H has a 1, so the number of ones inside circle i is even exactly when the parity sum that row i computes on c is 0. All three circles are even exactly when HcT=0, which by the theorem that the checks define the code happens exactly when c is a codeword. ■
Each position gets a region to itself because the region of position j is fixed by the rows where column j of H has a 1, and the seven distinct nonzero columns use each of the seven nonempty sets of circles exactly once.
The message bits sit in the overlaps, and each parity bit sits alone in the private part of one circle, so it can always be chosen to make its circle even, which is the encoder again. The picture also hints at decoding. A single flipped bit makes odd exactly the circles that contain it, and each region belongs to a different set of circles, so the odd circles point to the error. Turning that hint into a decoder is a job for the next chapter.
Each row of H is a word of length 7, and so is every sum of rows. Adding the rows of H in all eight possible ways gives a set of eight words, closed under XOR because the sum of two sums of rows is again a sum of rows. Figure 7 lists them. Each is orthogonal to every codeword of the (7,4) code, because each row of H is, and the dot product is bilinear. This set is the dual code C⊥={y∈GF(2)n∣y⋅c=0 for every c∈C} of Vector Spaces over Finite Fields, and the parity-check matrix turns out to be its generator.
Figure 7. The dual of the (7,4) code, generated by the rows of H. Every nonzero word has weight 4, and all eight words are codewords of C as well.
Proof. Every codeword c satisfies HcT=0, so each row hi of H has hi⋅c=0 for every c in C, and lies in C⊥. The dual is a subspace, by the lemma of Vector Spaces over Finite Fields, so every sum of rows of H lies in it too, and the row space of H sits inside C⊥. The rows of H are independent, since H has rank n−k, so the row space has dimension n−k. The theorem that a code and its dual fill the length gives dimC⊥=n−k as well. Both subspaces have dimension n−k, so both hold 2n−k words, and the one inside the other is all of it. ■
Proof. The matrix H generates C⊥ by the theorem. The matrix G has rank k=n−(n−k), and HGT=0 by the lemma on transposes, since GHT=0. The theorem that the checks define the code, applied to C⊥ with generator H and the matrix G, makes C⊥ the null space of G, so G is a parity-check matrix of C⊥. Applying the theorem that the checks generate the dual to C⊥ and this parity-check matrix shows that the rows of G form a basis of the dual of C⊥, and those rows span C. ■
For C5, the rows of H5 generate the eight words 00000, 00111, 01001, 01110, 10010, 10101, 11011 and 11100, the list Vector Spaces over Finite Fields found for C5⊥, and 2+3=5. The dual of the (7,4) code has dimension 3, and all seven of its nonzero codewords have weight 4.
Proof. Pick a position i with yi=1, and let ei be the word with a single 1 in position i. The map h↦h⊕ei splits the 2m words into pairs, since applying it twice returns h and it never sends a word to itself. By bilinearity y⋅(h⊕ei)=y⋅h+yi=y⋅h+1, so the two words of each pair have different dot products with y. Each of the 2m−1 pairs therefore holds exactly one word with y⋅h=1. ■
Proof. The matrix H generates the dual, so a codeword of the dual is yH for some y in GF(2)3. Bit j of yH is y⋅hj, the dot product of y with column j of H read as a word of length 3. The seven columns are all seven nonzero words of length 3. For y=0, the lemma gives exactly four words h of length 3 with y⋅h=1, and none of them is 000, since y⋅000=0. So all four are columns of H, and yH has exactly four ones. ■
A dual can even overlap the code it checks. Every pair of rows of H shares an even number of ones, as an exercise confirms, so HHT=0, each row of H is a codeword, and the whole dual lies inside C. MacWilliams and Sloane develop the relation between a code and its dual much further [4].
Reorder the positions of every codeword of the (7,4) code in one fixed way, taking the old positions in the order 5, 6, 1, 7, 3, 2, 4. The codeword 1011100 becomes 1010101, its bits x5, x6, x1, x7, x3, x2 and x4 in turn. The new word is not a codeword of C, since the first check of H adds its bits in positions 1, 3, 4 and 5 to 1+1+0+1=1. Yet the 16 reordered codewords form a code with the same weights as C, 0 once, 3 seven times, 4 seven times and 7 once, and the same minimum distance 3. Figure 8 shows the matching reordering of the columns of H.
Figure 8. Taking the columns of H in the order 5, 6, 1, 7, 3, 2, 4 gives a matrix H′ whose columns count from 1 to 7 in binary. The new code differs from C as a set of words but has the same weights and the same distance.
Proof. The map x↦x′ moves bits without changing them, so w(x′)=w(x). It is one to one on all words of length n, because σ can be undone, and every word of length n is x′ for exactly one x. It commutes with XOR, (x⊕y)′=x′⊕y′, since both sides hold xσ(j)⊕yσ(j) in position j. So C′ is closed under XOR and is linear, and its codewords have the same weights as those of C. Minimum distance is the smallest nonzero weight for both codes, so they share it. For the checks, the column formula gives H′x′T=∑jxj′hj′=∑jxσ(j)hσ(j), and as j runs over all positions so does i=σ(j), so the sum equals ∑ixihi=HxT. A word x′ passes the checks of H′ exactly when x passes those of H, so C′ is the null space of H′. The matrix H′ has the columns of H in a new order, so it keeps the rank n−k. ■
Read as binary numbers with row 1 as the lowest bit, the columns of H are 3, 6, 5, 7, 1, 2 and 4. The order 5, 6, 1, 7, 3, 2, 4 picks them out as 1 to 7, so H′ has rows 1010101, 0110011 and 0001111, its column j is j in binary, the arrangement of Hamming's paper with the checks in positions 1, 2 and 4, and the reordered word 1010101 passes all three of its checks.
Equivalence is weaker than equality. Of the 7!=5040 orderings of seven positions, the companion script finds that 168 send C to itself and that all of them together produce exactly 30 distinct codes, and an exercise explains why 30=5040/168. Over larger fields, equivalence also allows each position to be multiplied by its own nonzero constant, which Huffman and Pless call monomial equivalence [5]. Equivalent codes are interchangeable for every property that depends only on weights.
An [n,k] code sends k message bits in n channel bits. Its rate
R=nk
(8)
is the fraction of the transmitted bits that carry the message. The code holds 2k codewords among the 2n words of length n, a fraction 2k/2n=2−(n−k), so each of the n−k checks halves the set of acceptable words. The (7,4) code holds 16 of the 128 words of length 7, one word in eight. Table 2 sets seven of the chapter's codes side by side, the two of length 3, C5, the [6,3] code and the three codes of length 7.
Table 2. Length, dimension, minimum distance, number of codewords and rate of seven linear codes from the chapter
Code
Length
Dimension
Distance
Codewords
Rate
Repetition code R3
3
1
3
2
0.333333
Even weight, length 3
3
2
2
4
0.666667
C5
5
2
3
4
0.400000
The [6,3] code of the worked examples
6
3
3
8
0.500000
(7,4) Hamming code
7
4
3
16
0.571429
Dual of the Hamming code
7
3
4
8
0.428571
Code of Matrices and Elimination
7
4
2
16
0.571429
Source: reproduced by ch17_linear_codes.py.
The repetition code R3={000,111} of Distance, Detection and Correction and the (7,4) code both correct one error, but the first has rate 1/3 and the second 4/7, about 0.571. The (7,4) code and the code of Matrices and Elimination over Finite Fields share length, dimension and rate, and differ in distance, 3 against 2. Rate is a count, while distance depends on which subspace was chosen.
A linear code is a subspace. A k×n generator lists its 2k codewords, an (n−k)×n parity-check matrix tests them, and GHT=0 ties the two together, with [Ik∣P] leading to [PT∣In−k]. The minimum distance is the smallest nonzero weight, and it is also the fewest columns of H, at least one, that add to zero. The dual code swaps the roles of the two matrices.
The next chapter, Syndrome Decoding and the Standard Array, puts H to work on received words that fail the checks. Hamming Codes and Perfect Codes then builds, for each number of checks m, a code of length 2m−1 whose parity-check columns are all the nonzero words of length m. Weight Distributions and Undetected Errors returns to the counts in Figure 4, and Bounds on Codes asks how large the distance of a code of given length and dimension can be.
[1]Hamming, Richard W. (1950). “Error Detecting and Error Correcting Codes.” Bell System Technical Journal, 29(2), pp. 147–160. doi:10.1002/j.1538-7305.1950.tb00463.x
[2]Slepian, David (1956). “A Class of Binary Signaling Alphabets.” Bell System Technical Journal, 35(1), pp. 203–234. doi:10.1002/j.1538-7305.1956.tb02379.x
[3]Lin, Shu and Costello, Jr., Daniel J. (2004). “Error Control Coding: Fundamentals and Applications.” 2nd edition. Pearson Prentice Hall.
[4]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
[5]Huffman, W. Cary and Pless, Vera (2003). “Fundamentals of Error-Correcting Codes.” Cambridge University Press. doi:10.1017/CBO9780511807077
— Anirban
Hardware–software at the seam where compilers meet microcode.