Chapter 5 Coding Theory 87
Note that H = (At|In−k). With this notation we see that x = x1x2x3x4x5x6 is a codeword if and only if Hxt = 0, since checking this equation is the same as checking whether the parity check equations hold.
In general, suppose that G is a k × n generator matrix with G = (Ik|A),
where A is a k× (n− k) matrix. To G we associate the parity check matrix H, where
H = (At|In−k). Then x is a codeword if and only if Hxt = 0. Note that from a generator matrix G we can find the associated parity check matrix H, and conversely, given a parity check matrix H, we can find the associated generator matrix G. More precisely, note that if H = (B|Ir), then G = (In−r|Bt).
We have seen that the parity check matrix can be used to detect errors. That is, to determine whether x is a codeword we check whether
Hxt = 0.
Not only can the parity check matrix be used to detect errors, but when the columns of this matrix are distinct and are all nonzero, it also can be used to correct errors. Under these assumptions, suppose that the codeword x is sent and that y is received, which may or may not be the same as x. Write y = x + e, where e is an error string. (We have e = 0 if no errors arose in the transmission). In general, the error string e has 1s in the positions where y differs from x and 0s in all other positions. Now suppose that only one error has been introduced when x was transmitted. Then e is a bit string that has only one nonzero bit which is in the position where x and y differ, say position j. Since Hxt = 0, it follows that
Hyt = H(xt + e)
= Hxt + et
where cj is the jth column of H. Hence, if we receive y and assume that no more than one error is present,
we can find the codeword x that was sent by computing Hyt. If this is zero, we know that y is the codeword sent. Otherwise, it will equal the jth column of H for some integer j. This means that the jth bit of y should be changed to produce x.
Example 16 Use the parity check matrix to determine which codeword from the code in Example 14 was sent if 001111 was received. Assume that at most one error was made.
88 Applications of Discrete Mathematics
Solution: We find that
⎛ ⎝ 1 1 1 1 0 01 1 0 0 1 0
1 0 1 0 0 1
⎞ ⎠ ⎛ ⎜⎜⎜⎜⎜⎝
0 0 1 1 1 1
⎞ ⎟⎟⎟⎟⎟⎠ =
⎛ ⎝ 01
⎞ ⎠ .
This is the fifth column of H. If follows that the fifth bit of 001111 is incorrect. Hence the code word sent was 001101.
Hamming Codes We can now define the Hamming codes. We define them using parity check matrices.
Definition 4 A Hamming code of order r where r is a positive integer, is a code generated when we take as parity check matrix H an r × (2r − 1) matrix with columns that are all the 2r − 1 nonzero bit strings of length r in any order such that the last r columns form the identity matrix.
Interchanging the order of the columns leads to what is known as an equiv- alent code. For details on equivalence of codes the reader is referred to the references at the end of this chapter.
Example 17 Find the codewords in a Hamming code of order 2.
Solution: The parity check matrix of this code is
H = (
1 1 0 1 0 1
We have H = (B|I2) where B = (
) . Hence, the generator matrix G of
this code equals G = (I3−2|Bt) = (1 1 1). Since the codewords are linear combinations of the rows of G, we see that this code has two codewords, 000 and 111. This is the linear repetition code of order 3.
Example 18 Find the codewords in a Hamming code of order 3.
Chapter 5 Coding Theory 89
Solution: For the parity check matrix of this code we use
⎛ ⎝ 0 1 1 1 1 0 01 0 1 1 0 1 0
1 1 0 1 0 0 1
⎞ ⎠ .
We have H = (B|I3) where
⎛ ⎝ 0 1 1 11 0 1 1
1 1 0 1
⎞ ⎠ .
Hence the generator matrix G of this code equals
G = (I7−3|Bt) =
1 0 0 0 0 1 1 0 1 0 0 1 0 1 0 0 1 0 1 1 0 0 0 0 1 1 1 1
⎞ ⎟⎠ .