Paper
Part IILinear Block Codes

Linear Codes

November 15, 202650 min readbeginner

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)(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.

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

01.Four Words Closed under XOR

Take the four words 0000000000, 0110101101, 1011010110 and 1101111011 of length 5, and XOR any two of them position by position. The result is again one of the four. For instance 01101⊕10110=1101101101 \oplus 10110 = 11011, and 10110⊕11011=0110110110 \oplus 11011 = 01101. Figure 1 lists all 16 sums. Call this set C5C_5. Groups and Cosets met it as a subgroup, and Vector Spaces over Finite Fields as a subspace.

The XOR table of the code C5, whose four words are 00000, 01101, 10110 and 11011. Every one of the sixteen entries is again one of the four codewords, and each row lists all four exactly once, so C5 is closed under XOR. Beside it, the four odd-weight words of length 3 fail the test, because 001 XOR 010 is 011, which is not in that set. XOR table of the code C5 XOR 00000 01101 10110 11011 00000 01101 10110 11011 00000 01101 10110 11011 01101 00000 11011 10110 10110 11011 00000 01101 11011 10110 01101 00000 every entry is a codeword, so C5 is closed under XOR each row lists all four codewords exactly once Odd weight, length 3 001 010 100 111 001 XOR 010 = 011 011 is not in the set not closed under XOR
Figure 1. The XOR table of . Every sum of two codewords is a codeword, so is closed under XOR. The odd-weight words of length 3 are not, because falls outside the set.

Most sets of words fail this test. The four words of length 3 with an odd number of ones, 001001, 010010, 100100 and 111111, fail at once, because 001⊕010=011001 \oplus 010 = 011 has two ones. The four words with an even number of ones, 000000, 011011, 101101 and 110110, pass. The weight of x⊕yx \oplus y is w(x)+w(y)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 000000, 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 CC is nonempty and closed under XOR, and pick any cc in CC. Then c⊕c=0c \oplus c = 0 lies in CC. The only scalars in GF(2)\mathrm{GF}(2) are 0 and 1, and 0⋅c=00 \cdot c = 0 and 1⋅c=c1 \cdot c = c both lie in CC, so CC is closed under multiplication by scalars. Addition in GF(2)n\mathrm{GF}(2)^n is XOR, so CC is closed under addition by hypothesis. The subspace test of Vector Spaces over Finite Fields now makes CC a subspace. Conversely, a subspace is closed under addition, and addition is XOR. ■\blacksquare

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)\mathrm{GF}(4), closure under addition does not give closure under every scalar, so a linear code there is defined directly as a subspace.

02.A Basis Lists Every Codeword

Two words of C5C_5, g1=10110g_1 = 10110 and g2=01101g_2 = 01101, produce all four codewords. The combination 0⋅g1+0⋅g20 \cdot g_1 + 0 \cdot g_2 is 0000000000, the words g2g_2 and g1g_1 are themselves codewords, and g1+g2=11011g_1 + g_2 = 11011. Stack them as the rows of a matrix

G5=[1011001101]G_5 = \begin{bmatrix} 1 & 0 & 1 & 1 & 0 \\ 0 & 1 & 1 & 0 & 1 \end{bmatrix}

and write a message as a row m=(m1,m2)m = (m_1, m_2). The product mG5=m1g1+m2g2m G_5 = m_1 g_1 + m_2 g_2 is a codeword, and the four messages 0000, 0101, 1010 and 1111 give the four codewords 0000000000, 0110101101, 1011010110 and 1101111011. Read one column at a time, as Matrices and Elimination over Finite Fields read such products, entry jj of mG5m G_5 is the parity sum of the message bits that column jj of G5G_5 selects. Column 3 holds a 1 in both rows, so the third bit is m1+m2m_1 + m_2, and the whole codeword is (m1,m2,m1+m2,m1,m2)(m_1, m_2, m_1 + m_2, m_1, m_2). Two message bits travel in five channel bits, a rate of 2/5=0.42/5 = 0.4.

Proof. The product mGmG is the combination m1g1+⋯+mkgkm_1 g_1 + \cdots + m_k g_k of the rows g1,…,gkg_1, \ldots, g_k of GG. The rows span CC, so every codeword is such a combination, and every codeword is mGmG for some message mm. If mG=m′GmG = m'G, then (m−m′)G=0(m - m') G = 0, a combination of the rows with coefficients mi−mi′m_i - m'_i that equals zero. The rows are independent, so every coefficient is zero and m=m′m = m'. The map is therefore a one-to-one correspondence between the 2k2^k messages and the codewords. ■\blacksquare

A code has many generator matrices, one for each basis. The rows 1101111011 and 0110101101 also span C5C_5, 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][7, 4] code with generator

G=[1000110010001100101010001111]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}

which is the (7,4)(7, 4) Hamming code. Its four rows are independent, since its first four columns form the identity, so it holds 24=162^4 = 16 codewords. The message 10111011 adds rows 1, 3 and 4, and 1000110⊕0010101⊕0001111=10111001000110 \oplus 0010101 \oplus 0001111 = 1011100.

03.Checks Every Codeword Passes

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)(m_1, m_2, m_1 + m_2, m_1, m_2) of C5C_5. Bit 3 is the sum of bits 1 and 2, bit 4 equals bit 1, and bit 5 equals bit 2. Over GF(2)\mathrm{GF}(2) the equation a=ba = b says the same as a+b=0a + b = 0, so the three rules read

c1+c2+c3=0,c1+c4=0,c2+c5=0.c_1 + c_2 + c_3 = 0, \qquad c_1 + c_4 = 0, \qquad c_2 + c_5 = 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=[111001001001001].H_5 = \begin{bmatrix} 1 & 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 & 1 \end{bmatrix}.

The codeword 1101111011 passes all three checks, since 1+1+01 + 1 + 0, 1+11 + 1 and 1+11 + 1 are all 0. The word 1011110111 fails the third, since bits 2 and 5 give 0+1=10 + 1 = 1.

Words in this chapter are written as rows, and the checks act on them as columns. The transpose ATA^{\mathsf T} of an m×nm \times n matrix AA is the n×mn \times m matrix whose rows are the columns of AA, so (AT)ij=Aji(A^{\mathsf T})_{ij} = A_{ji}. The transpose of G5G_5 is the 5×25 \times 2 matrix with rows 1010, 0101, 1111, 1010 and 0101, and the transpose xTx^{\mathsf T} of a word xx is the same bits stood up as a column. All three checks at once then say H5xT=0H_5 x^{\mathsf T} = 0. Matrices and Elimination over Finite Fields wrote HrH r, with rr already a column.

Proof. Entry (i,j)(i, j) of ABTA B^{\mathsf T} is ∑lAil(BT)lj=∑lAilBjl\sum_{l} A_{il} (B^{\mathsf T})_{lj} = \sum_{l} A_{il} B_{jl}, which is the dot product of row ii of AA with row jj of BB. So ABTA B^{\mathsf T} 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=0b_j \cdot a_i = a_i \cdot b_j = 0 for every pair, which is the statement BAT=0B A^{\mathsf T} = 0. ■\blacksquare

In particular, entry ii of HxTH x^{\mathsf T} is hi⋅xh_i \cdot x, check ii applied to the word xx.

Proof. By the lemma, each row hih_i of HH is orthogonal to each row glg_l of GG. A codeword is c=m1g1+⋯+mkgkc = m_1 g_1 + \cdots + m_k g_k, and the dot product is bilinear, so hi⋅c=m1(hi⋅g1)+⋯+mk(hi⋅gk)=0h_i \cdot c = m_1 (h_i \cdot g_1) + \cdots + m_k (h_i \cdot g_k) = 0. Every check passes, so CC lies inside the null space of HH. The rank theorem of Matrices and Elimination over Finite Fields says the null space of HH holds 2n−(n−k)=2k2^{n - (n - k)} = 2^k words, and CC holds 2k2^k 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 CC equals the null space of HH. ■\blacksquare

For C5C_5, G5H5TG_5 H_5^{\mathsf T} is the 2×32 \times 3 zero matrix and H5H_5 has rank 3, since its last three columns form the identity. Of the 32 words of length 5, exactly the four codewords satisfy H5xT=0H_5 x^{\mathsf T} = 0. The word 1011110111 gives H5xT=001H_5 x^{\mathsf T} = 001, which flags it as damaged. Groups and Cosets called the map x↦HxTx \mapsto H x^{\mathsf T} a syndrome, and here it only answers yes or no. A receiver checks n−kn - k parity sums for zero instead of comparing the word with all 2k2^k codewords.

04.From the Generator to the Checks

The generator of the (7,4)(7, 4) code has the form G=[ I4∣P ]G = \left[\, I_4 \mid P \,\right], an identity block followed by

P=[110011101111].P = \begin{bmatrix} 1 & 1 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 1 \end{bmatrix}.

Bit 5 of a codeword is m1+m3+m4m_1 + m_3 + m_4, read down the first column of PP. The first four bits of the codeword are the message, ci=mic_i = m_i for i≤4i \le 4, so the rule says c5=c1+c3+c4c_5 = c_1 + c_3 + c_4, which over GF(2)\mathrm{GF}(2) is the check c1+c3+c4+c5=0c_1 + c_3 + c_4 + c_5 = 0. The other two columns of PP give the checks c1+c2+c4+c6=0c_1 + c_2 + c_4 + c_6 = 0 and c2+c3+c4+c7=0c_2 + c_3 + c_4 + c_7 = 0. Each check is one column of PP laid on its side, with a single 1 added in the place of its parity bit. The three checks together form

H=[101110011010100111001]=[ PT∣I3 ],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} = \left[\, P^{\mathsf T} \mid I_3 \,\right],

and Figure 2 sets the two matrices side by side.

The generator matrix G of the (7,4) Hamming code in systematic form, an identity block I of size 4 beside the 4-by-3 block P with rows 110, 011, 101 and 111, and the parity-check matrix H built from it, the transpose of P, with rows 1011, 1101 and 0111, beside an identity block of size 3. The bits of P, marked in green, reappear in H with rows turned into columns, and every row of G satisfies all three checks of H. G = [ I | P ], 4 by 7 H = [ P transposed | I ], 3 by 7 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 I 4 by 4 P 4 by 3 transpose P rows become columns 1 0 1 1 1 0 0 1 1 0 1 0 1 0 0 1 1 1 0 0 1 P transposed 3 by 4 I 3 by 3 each row of G satisfies all three checks of H, so the product of G and H transposed is zero
Figure 2. The systematic generator of the Hamming code and its parity-check matrix , both built from the same block .

Proof. Row ii of GG is the word eie_i of length kk, with a single 1 in place ii, followed by row ii of PP. Row jj of HH is column jj of PP followed by the word of length n−kn - k with a single 1 in place jj. Their dot product has at most two nonzero terms. In the first kk positions only place ii of eie_i holds a 1, and it meets entry ii of column jj of PP, which is PijP_{ij}. In the last n−kn - k positions only place jj of the identity row holds a 1, and it meets entry jj of row ii of PP, again PijP_{ij}. The dot product is Pij+Pij=0P_{ij} + P_{ij} = 0, so GHT=0G H^{\mathsf T} = 0 by the lemma on transposes. The last n−kn - k columns of HH form In−kI_{n-k}, so in a combination of the rows of HH those columns show the coefficients themselves, and a combination equal to zero has every coefficient zero. So HH has rank n−kn - k, and the theorem that the checks define the code finishes the proof. ■\blacksquare

Over GF(q)\mathrm{GF}(q) with q>2q > 2 the same argument works for H=[ −PT∣In−k ]H = \left[\, -P^{\mathsf T} \mid I_{n-k} \,\right], where the dot product becomes −Pij+Pij=0-P_{ij} + P_{ij} = 0. Over GF(2)\mathrm{GF}(2), where −1=1-1 = 1, the sign disappears.

The companion script checks the formula for every one of the 212=40962^{12} = 4096 choices of a 4×34 \times 3 block PP, confirming each time that the row space of GG and the null space of HH are the same 16 words. For C5C_5 the block P5P_5 has rows 110110 and 101101, and [ P5T∣I3 ]\left[\, P_5^{\mathsf T} \mid I_3 \,\right] is exactly the matrix H5H_5 found earlier by reasoning about the bits. A designer specifies only PP, and the encoder and the checker are both read from it.

05.Systematic Encoding

With G=[ Ik∣P ]G = \left[\, I_k \mid P \,\right] the product mGmG splits into two pieces,

c=m[ Ik∣P ]=[ m∣mP ].c = m \left[\, I_k \mid P \,\right] = \left[\, m \mid mP \,\right].
(4)

The first kk bits of the codeword are the message itself, and the last n−kn - 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)(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

MessageCodewordWeightMessageCodewordWeight
000000000000100010001103
000100011114100110010013
001000101013101010100114
001100110103101110111004
010001000113110011001014
010101011003110111010104
011001101104111011100003
011101110014111111111117

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=0H r^{\mathsf T} = 0 reads the message off the first kk bits of rr with no arithmetic.

Lin and Costello put the parity bits first instead, writing [ P∣Ik ]\left[\, P \mid I_k \,\right] [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, CC has an information set, kk positions on which the codewords run through all 2k2^k patterns, each exactly once. Reorder the positions so that the information set comes first. For each ii from 1 to kk, exactly one codeword gig_i shows the pattern eie_i on the first kk positions. Stack g1,…,gkg_1, \ldots, g_k as the rows of a matrix. Its first kk columns form IkI_k, so it has the form [ Ik∣P ]\left[\, I_k \mid P \,\right]. Its rows are independent, because the combination with coefficients a1,…,aka_1, \ldots, a_k shows the word (a1,…,ak)(a_1, \ldots, a_k) in the first kk positions and is zero only when every aia_i is zero. These are kk independent codewords in a code of dimension kk, so they form a basis, and the matrix is a generator. ■\blacksquare

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.

06.The Encoder as XOR Trees

Read the columns of PP as wiring instructions. Column 1 selects m1m_1, m3m_3 and m4m_4, and the other two columns select their own three bits, so

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

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 c1c_1 to c4c_4 as wires, and three trees of two gates each produce the parity bits, six gates in all. When the message 10111011 enters, the trees compute c5=1⊕1⊕1=1c_5 = 1 \oplus 1 \oplus 1 = 1, c6=1⊕0⊕1=0c_6 = 1 \oplus 0 \oplus 1 = 0 and c7=0⊕1⊕1=0c_7 = 0 \oplus 1 \oplus 1 = 0, and the codeword 10111001011100 comes out.

The systematic encoder of the (7,4) Hamming code. The four message bits m1 to m4 pass straight through as codeword bits c1 to c4, and each parity bit is a tree of two two-input XOR gates: c5 is m1 + m3 + m4, c6 is m1 + m2 + m4 and c7 is m2 + m3 + m4, six gates in all and two gate delays deep. With the message 1011 the outputs are 1, 0, 1, 1, 1, 0 and 0, the codeword 1011100. m1 1 m2 0 m3 1 m4 1 output equals c1 = 1 m1 c2 = 0 m2 c3 = 1 m3 c4 = 1 m4 c5 = 1 m1 + m3 + m4 c6 = 0 m1 + m2 + m4 c7 = 0 m2 + m3 + m4 four plain wires and six two-input XOR gates, two gate delays deep
Figure 3. The encoder of the code as three XOR trees, one per parity bit, with six two-input gates and two gate delays. The message becomes the codeword .

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 ss signals and ends with one, so it uses s−1s - 1 gates. For the depth, a tree whose longest path has DD gates has at most 2D2^D inputs. That holds for D=0D = 0, a bare wire with a single input, and a tree of depth D+1D + 1 is one output gate fed by two trees of depth at most DD, which together have at most 2D+2D=2D+12^D + 2^D = 2^{D+1} inputs. So s≤2Ds \le 2^D, which gives D≥log⁡2sD \ge \log_2 s, and since DD is a whole number, D≥⌈log⁡2s⌉D \ge \lceil \log_2 s \rceil. A balanced tree pairs off the signals at each level, turning ss signals into ⌈s/2⌉\lceil s/2 \rceil, so after DD levels ⌈s/2D⌉\lceil s / 2^D \rceil remain, and that is 1 as soon as 2D≥s2^D \ge s. So it finishes in ⌈log⁡2s⌉\lceil \log_2 s \rceil levels. ■\blacksquare

Every column of PP has weight 3, so each tree has 3−1=23 - 1 = 2 gates and ⌈log⁡23⌉=2\lceil \log_2 3 \rceil = 2 levels, and the whole encoder costs six gates and two gate delays, with no clock and no memory. The encoder of C5C_5 needs one gate, c3=m1⊕m2c_3 = m_1 \oplus m_2, since c4=m1c_4 = m_1 and c5=m2c_5 = m_2 are plain wires.

Trees can also share work. The sum m1⊕m4m_1 \oplus m_4 appears in both c5c_5 and c6c_6, 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⊕m4t = m_1 \oplus m_4, \quad c_5 = t \oplus m_3, \quad c_6 = t \oplus m_2, \quad u = m_2 \oplus m_3, \quad c_7 = u \oplus m_4

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 PP 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.

07.Distance Is the Smallest Weight

Distance, Detection and Correction showed that a code with minimum distance dd, the smallest number of positions in which two different codewords differ, detects every pattern of up to d−1d - 1 errors and corrects every pattern of up to ⌊(d−1)/2⌋\lfloor (d - 1)/2 \rfloor. By brute force, finding dd means comparing all (162)=120\binom{16}{2} = 120 pairs of codewords of the (7,4)(7, 4) code, and MM codewords form M(M−1)/2M(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′)d(c, c') = w(c \oplus c'). If cc and c′c' are different codewords, then c⊕c′c \oplus c' is a codeword by closure and is not zero, so every distance between distinct codewords is the weight of a nonzero codeword, and dd is at least the smallest nonzero weight. In the other direction, 00 is a codeword, and a nonzero codeword cc lies at distance d(c,0)=w(c)d(c, 0) = w(c) from it, so the smallest nonzero weight is itself a distance, and dd is at most that weight. For the second claim, fix a codeword cc. The map c′↦c⊕c′c' \mapsto c \oplus c' sends CC into CC by closure, and applying it twice returns c′c', so it is a one-to-one correspondence of CC with itself. The distance d(c,c′)=w(c⊕c′)d(c, c') = w(c \oplus c') therefore runs through the weights of all the codewords, each exactly once. ■\blacksquare

So every codeword sees the same neighborhood. From any codeword of the (7,4)(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=3d = 3, so the code detects any two errors and corrects any single error. The weights of C5C_5 are 3, 3 and 4, so C5C_5 also has d=3d = 3.

The choice of PP matters. Matrices and Elimination over Finite Fields built a [7,4][7, 4] code with the systematic generator SS of its Systematic Form section, whose rows 10001101000110, 01000110100011, 00101000010100 and 00011110001111 differ from GG only in the last bit of row 3. Its row 00101000010100 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.

Weight distributions of two binary linear codes of length 7 and dimension 4. The (7,4) Hamming code has one codeword of weight 0, seven of weight 3, seven of weight 4 and one of weight 7, so its smallest nonzero weight, and its minimum distance, is 3. The code built from the systematic matrix of Matrices and Elimination over Finite Fields has weights 0, 2, 3, 4, 5 and 6 with counts 1, 1, 6, 5, 2 and 1, so its minimum distance is 2. weight of the codeword number of codewords 0 2 4 6 8 0 1 1 1 2 1 3 7 6 4 7 5 5 2 6 1 7 1 (7,4) Hamming code, d = 3 code of Matrices and Elimination, d = 2
Figure 4. Weight distributions of two 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.

08.Reading the Distance from the Columns of H

Minimum weight still asks for all 2k2^k codewords to be listed. The parity-check matrix offers a test that lists none. Take x=1000110x = 1000110, with ones in positions 1, 5 and 6. Each check row of HH adds up the bits in the positions it covers, so HxTH x^{\mathsf T} is the sum of the columns of HH at the positions where xx has a 1. Those columns, read from top to bottom, are 110110, 100100 and 010010, and their sum is 000000. So xx is a codeword, and its weight is 3. Figure 5 shows the three columns.

The parity-check matrix H of the (7,4) Hamming code, with rows 1011100, 1101010 and 0111001, and the word x = 1000110, whose ones sit in positions 1, 5 and 6. H times x is the sum of columns 1, 5 and 6 of H, which are 110, 100 and 010, and that sum is 000, so x is a codeword of weight 3. Since no column of H is zero and no two columns are equal, no codeword has weight 1 or 2, and the minimum distance is 3. the parity-check matrix H the columns x selects 1 2 3 4 5 6 7 1 0 1 1 1 0 0 1 1 0 1 0 1 0 0 1 1 1 0 0 1 H 1 0 0 0 1 1 0 x col 1 1 1 0 col 5 1 0 0 col 6 0 1 0 + + = sum 0 0 0 H x is the sum of columns 1, 5 and 6, which is 000, so x = 1000110 is a codeword no column is 000 and no two are equal, so no codeword has weight 1 or 2
Figure 5. is the sum of the columns of at the ones of . Columns 1, 5 and 6 add to zero, so 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+⋯+xnhnH x^{\mathsf T} = x_1 h_1 + \cdots + x_n h_n. Each xjx_j is 0 or 1, so the terms with xj=0x_j = 0 vanish, and the rest are the columns hjh_j with xj=1x_j = 1. That proves the formula, and with it the test for a codeword, since CC is the null space of HH. A nonzero codeword of weight ww therefore gives a nonempty set of ww columns that add to zero. In the other direction, a nonempty set of ww columns that add to zero gives the word with ones in exactly those positions, a nonzero codeword of weight ww. Since CC 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 dd. ■\blacksquare

Proof. By the theorem, d≥3d \ge 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)\mathrm{GF}(2) the equation hi+hj=0h_i + h_j = 0 says the same as hi=hjh_i = h_j. ■\blacksquare

The seven columns of the (7,4)(7, 4) matrix HH are 110110, 011011, 101101, 111111, 100100, 010010 and 001001. They are all seven nonzero words of length 3, so none is zero and no two are equal, and d≥3d \ge 3. Columns 1, 5 and 6 add to zero, so d=3d = 3, read straight off the matrix.

The columns of H5H_5 are 110110, 101101, 100100, 010010 and 001001, again nonzero and distinct, and columns 1, 3 and 4 add to zero, so C5C_5 has d=3d = 3. The code of Matrices and Elimination over Finite Fields has a parity-check matrix with columns 110110, 011011, 100100, 111111, 100100, 010010 and 001001, and columns 3 and 5 are both 100100, so d=2d = 2 at a glance.

Hamming Codes and Perfect Codes takes this column rule as far as it goes.

09.The Venn Diagram of the (7,4) Code

The three checks of the (7,4)(7, 4) code fit into a picture of three overlapping circles, one per check, each holding the positions its row of HH 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 10111001011100 into the regions, with four ones in circle 1 and two in each of the others.

The (7,4) Hamming code drawn as three overlapping circles with the seven codeword bits in the seven regions. Circle 1 holds c1, c3, c4 and c5, circle 2 holds c1, c2, c4 and c6, and circle 3 holds c2, c3, c4 and c7, so c4 sits in all three, c1, c2 and c3 each sit in two, and c5, c6 and c7 each sit in one. The codeword 1011100 is filled in, and each circle holds an even number of ones, four, two and two, which is the rule that defines a codeword. circle 1 circle 2 circle 3 c1 1 c2 0 c3 1 c4 1 c5 1 c6 0 c7 0 circle 1 c1 c3 c4 c5 1 1 1 1 four ones, even circle 2 c1 c2 c4 c6 1 0 1 0 two ones, even circle 3 c2 c3 c4 c7 0 1 1 0 two ones, even the codeword 1011100 written into the seven regions
Figure 6. The Hamming code as three circles, one per check. A word is a codeword exactly when every circle holds an even number of ones, as does.

Proof. Circle ii holds the positions where row ii of HH has a 1, so the number of ones inside circle ii is even exactly when the parity sum that row ii computes on cc is 0. All three circles are even exactly when HcT=0H c^{\mathsf T} = 0, which by the theorem that the checks define the code happens exactly when cc is a codeword. ■\blacksquare

Each position gets a region to itself because the region of position jj is fixed by the rows where column jj of HH 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.

10.The Dual Code

Each row of HH is a word of length 7, and so is every sum of rows. Adding the rows of HH 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)(7, 4) code, because each row of HH 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}C^{\perp} = \{ y \in \mathrm{GF}(2)^n \mid y \cdot c = 0 \text{ for every } c \in C \} of Vector Spaces over Finite Fields, and the parity-check matrix turns out to be its generator.

The dual of the (7,4) Hamming code, listed as the eight sums of the rows h1 = 1011100, h2 = 1101010 and h3 = 0111001 of its parity-check matrix. The words are 0000000, 1011100, 1101010, 0111001, 0110110, 1100101, 1010011 and 0001111. Every nonzero word has weight 4, every one of the eight is also a codeword of the Hamming code, and the dimensions 4 and 3 add up to the length 7. h1 = 1011100, h2 = 1101010, h3 = 0111001 are the rows of H rows of H added codeword of the dual weight also in C none (the zero word) 0000000 0 yes h1 1011100 4 yes h2 1101010 4 yes h3 0111001 4 yes h1 + h2 0110110 4 yes h1 + h3 1100101 4 yes h2 + h3 1010011 4 yes h1 + h2 + h3 0001111 4 yes every nonzero codeword of the dual has weight 4, and all eight lie inside C dimension 4 for C plus dimension 3 for the dual makes 7, the length
Figure 7. The dual of the code, generated by the rows of . Every nonzero word has weight 4, and all eight words are codewords of as well.

Proof. Every codeword cc satisfies HcT=0H c^{\mathsf T} = 0, so each row hih_i of HH has hi⋅c=0h_i \cdot c = 0 for every cc in CC, and lies in C⊥C^{\perp}. The dual is a subspace, by the lemma of Vector Spaces over Finite Fields, so every sum of rows of HH lies in it too, and the row space of HH sits inside C⊥C^{\perp}. The rows of HH are independent, since HH has rank n−kn - k, so the row space has dimension n−kn - k. The theorem that a code and its dual fill the length gives dim⁡C⊥=n−k\dim C^{\perp} = n - k as well. Both subspaces have dimension n−kn - k, so both hold 2n−k2^{n - k} words, and the one inside the other is all of it. ■\blacksquare

Proof. The matrix HH generates C⊥C^{\perp} by the theorem. The matrix GG has rank k=n−(n−k)k = n - (n - k), and HGT=0H G^{\mathsf T} = 0 by the lemma on transposes, since GHT=0G H^{\mathsf T} = 0. The theorem that the checks define the code, applied to C⊥C^{\perp} with generator HH and the matrix GG, makes C⊥C^{\perp} the null space of GG, so GG is a parity-check matrix of C⊥C^{\perp}. Applying the theorem that the checks generate the dual to C⊥C^{\perp} and this parity-check matrix shows that the rows of GG form a basis of the dual of C⊥C^{\perp}, and those rows span CC. ■\blacksquare

For C5C_5, the rows of H5H_5 generate the eight words 0000000000, 0011100111, 0100101001, 0111001110, 1001010010, 1010110101, 1101111011 and 1110011100, the list Vector Spaces over Finite Fields found for C5⊥C_5^{\perp}, and 2+3=52 + 3 = 5. The dual of the (7,4)(7, 4) code has dimension 3, and all seven of its nonzero codewords have weight 4.

Proof. Pick a position ii with yi=1y_i = 1, and let eie_i be the word with a single 1 in position ii. The map h↦h⊕eih \mapsto h \oplus e_i splits the 2m2^m words into pairs, since applying it twice returns hh and it never sends a word to itself. By bilinearity y⋅(h⊕ei)=y⋅h+yi=y⋅h+1y \cdot (h \oplus e_i) = y \cdot h + y_i = y \cdot h + 1, so the two words of each pair have different dot products with yy. Each of the 2m−12^{m-1} pairs therefore holds exactly one word with y⋅h=1y \cdot h = 1. ■\blacksquare

Proof. The matrix HH generates the dual, so a codeword of the dual is yHyH for some yy in GF(2)3\mathrm{GF}(2)^3. Bit jj of yHyH is y⋅hjy \cdot h_j, the dot product of yy with column jj of HH read as a word of length 3. The seven columns are all seven nonzero words of length 3. For y≠0y \neq 0, the lemma gives exactly four words hh of length 3 with y⋅h=1y \cdot h = 1, and none of them is 000000, since y⋅000=0y \cdot 000 = 0. So all four are columns of HH, and yHyH has exactly four ones. ■\blacksquare

A dual can even overlap the code it checks. Every pair of rows of HH shares an even number of ones, as an exercise confirms, so HHT=0H H^{\mathsf T} = 0, each row of HH is a codeword, and the whole dual lies inside CC. MacWilliams and Sloane develop the relation between a code and its dual much further [4].

11.Equivalent Codes

Reorder the positions of every codeword of the (7,4)(7, 4) code in one fixed way, taking the old positions in the order 5, 6, 1, 7, 3, 2, 4. The codeword 10111001011100 becomes 10101011010101, its bits x5x_5, x6x_6, x1x_1, x7x_7, x3x_3, x2x_2 and x4x_4 in turn. The new word is not a codeword of CC, since the first check of HH adds its bits in positions 1, 3, 4 and 5 to 1+1+0+1=11 + 1 + 0 + 1 = 1. Yet the 16 reordered codewords form a code with the same weights as CC, 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 HH.

Two equivalent codes. The parity-check matrix H of the (7,4) Hamming code has columns that read 3, 6, 5, 7, 1, 2 and 4 as binary numbers with row 1 as the lowest bit. Taking its columns in the order 5, 6, 1, 7, 3, 2, 4 gives H', whose columns read 1 to 7 in order. The same reordering sends the codeword 1011100 to 1010101, which satisfies H' but is not a codeword of the original code, so the two codes are different sets with the same weights and the same minimum distance 3. H, columns in the order 1 to 7 H', columns in the order 5 6 1 7 3 2 4 1 1 2 2 3 3 4 4 5 5 6 6 7 7 1 1 0 0 1 1 1 0 1 1 0 0 0 1 1 0 1 1 0 1 1 0 0 0 1 1 0 1 0 0 1 0 1 0 1 1 0 1 0 1 1 1 permute the columns as a number as a number 3 6 5 7 1 2 4 1 2 3 4 5 6 7 from column 5 6 1 7 3 2 4 1 0 1 1 1 0 0 1 0 1 0 1 0 1 x x' in C, since H x = 000 in the new code, not in C the two codes are different sets with the same 16 weights and the same distance 3 a column read as a number takes row 1 as its lowest bit
Figure 8. Taking the columns of in the order 5, 6, 1, 7, 3, 2, 4 gives a matrix whose columns count from 1 to 7 in binary. The new code differs from as a set of words but has the same weights and the same distance.

Proof. The map x↦x′x \mapsto x' moves bits without changing them, so w(x′)=w(x)w(x') = w(x). It is one to one on all words of length nn, because σ\sigma can be undone, and every word of length nn is x′x' for exactly one xx. It commutes with XOR, (x⊕y)′=x′⊕y′(x \oplus y)' = x' \oplus y', since both sides hold xσ(j)⊕yσ(j)x_{\sigma(j)} \oplus y_{\sigma(j)} in position jj. So C′C' is closed under XOR and is linear, and its codewords have the same weights as those of CC. 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)H' x'^{\mathsf T} = \sum_j x'_j h'_j = \sum_j x_{\sigma(j)} h_{\sigma(j)}, and as jj runs over all positions so does i=σ(j)i = \sigma(j), so the sum equals ∑ixihi=HxT\sum_i x_i h_i = H x^{\mathsf T}. A word x′x' passes the checks of H′H' exactly when xx passes those of HH, so C′C' is the null space of H′H'. The matrix H′H' has the columns of HH in a new order, so it keeps the rank n−kn - k. ■\blacksquare

Read as binary numbers with row 1 as the lowest bit, the columns of HH 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′H' has rows 10101011010101, 01100110110011 and 00011110001111, its column jj is jj in binary, the arrangement of Hamming's paper with the checks in positions 1, 2 and 4, and the reordered word 10101011010101 passes all three of its checks.

Equivalence is weaker than equality. Of the 7!=50407! = 5040 orderings of seven positions, the companion script finds that 168 send CC to itself and that all of them together produce exactly 30 distinct codes, and an exercise explains why 30=5040/16830 = 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.

12.How Many Codewords, and at What Rate

An [n,k][n, k] code sends kk message bits in nn channel bits. Its rate

R=knR = \frac{k}{n}
(8)

is the fraction of the transmitted bits that carry the message. The code holds 2k2^k codewords among the 2n2^n words of length nn, a fraction 2k/2n=2−(n−k)2^k / 2^n = 2^{-(n - k)}, so each of the n−kn - k checks halves the set of acceptable words. The (7,4)(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, C5C_5, the [6,3][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

CodeLengthDimensionDistanceCodewordsRate
Repetition code R3R_331320.333333
Even weight, length 332240.666667
C5C_552340.400000
The [6,3][6, 3] code of the worked examples63380.500000
(7,4)(7, 4) Hamming code743160.571429
Dual of the Hamming code73480.428571
Code of Matrices and Elimination742160.571429

Source: reproduced by ch17_linear_codes.py.

The repetition code R3={000,111}R_3 = \{000, 111\} of Distance, Detection and Correction and the (7,4)(7, 4) code both correct one error, but the first has rate 1/31/3 and the second 4/74/7, about 0.5710.571. The (7,4)(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.

13.Looking Ahead

A linear code is a subspace. A k×nk \times n generator lists its 2k2^k codewords, an (n−k)×n(n - k) \times n parity-check matrix tests them, and GHT=0G H^{\mathsf T} = 0 ties the two together, with [ Ik∣P ]\left[\, I_k \mid P \,\right] leading to [ PT∣In−k ]\left[\, P^{\mathsf T} \mid I_{n-k} \,\right]. The minimum distance is the smallest nonzero weight, and it is also the fewest columns of HH, 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 HH to work on received words that fail the checks. Hamming Codes and Perfect Codes then builds, for each number of checks mm, a code of length 2m−12^m - 1 whose parity-check columns are all the nonzero words of length mm. 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.

14.Worked Examples

15.Exercises

References

  1. [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. [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. [3]Lin, Shu and Costello, Jr., Daniel J. (2004). “Error Control Coding: Fundamentals and Applications.” 2nd edition. Pearson Prentice Hall.
  4. [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. [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.

FeedbackBook modePaper
error-correction-codinglinear-block-codes