More on Coding
We have already been introduced to a few of the basics of coding (click here for this review). Now we will look at this topic in more detail. In particular, we will investigate how to construct matrices that detect a single error. Then we will again use a matrix to correct the error, and finally will use a matrix to read the message.
The first m bits of the code is just the message itself and the final n-m bits are for error checking and error correcting. If b is the message, e is the encoding transformation, and C is the corresponding n x m matrix, then we can write
e(b) = Cb
There are many choices of matrices that will encode a message. One natural strategy to transform an m bit message into an n bit code is the following. The first m bits of the code is just the message itself and the final n-m bits are for error checking and error correcting. The matrix C will be the m x m identity matrix on top of an (n - m) x m matrix. An example for a two bit message and a five bit code is given below.
Notice that the first two rows make up the 2 x 2 identity matrix. We write
Notice that the rank of C is 2, since the first 2 rows are linearly independent. In general the rank of this type of encoding matrix with an m x m identity matrix above an (n - m) x m error checking matrix will always be m since the first m rows are linearly independent. Hence e(b) is a 1-1 transformation.
We can form the matrix of all possible messages. For 2 bit messages, there are four possible messages and the matrix is shown below.
To find the collection of all code words, we just multiply C by the above matrix
The columns of the matrix on the right hand side of the equation are the code words.
We now will find a check matrix G such that is x is the received message, then Gx = 0 if x is a code word and Gx will not be 0 if Gx is not a code word. First notice that since the rank of C is 2, the dimension of the null space is 5 - 2 = 3. Hence the matrix G must have 3 rows. If we let G have the form
The we need
GC = 0
b1 + 1 =
b2 + 1 = 0
Hence G is the matrix
It is not a coincidence that the first two columns of G are the same as the columns of D. This leads us to the theorem
The matrix transformation e(b) = Cb where C is the identity matrix on top of the matrix D has check matrix
G = [D In-m]
xi = x + ei
where ei is the ith basis vector. Now notice that
Gxi = G(x + ei) = Gx + Gei
= 0 + coli(G) = coli(G)
where coli(G) is the ith column of G.
This tells us that if a single error occurs in the ith entry, then multiplying by G will produce the ith column of G. Hence we can just compare Gx with the columns of G to find the location of the error.
Suppose that signal received with the matrix from our preceding example was
then when we multiply by G, we get
Since Gx is nonzero, we know that an error was made. Furthermore, since Gx is equal to the second column of G, we know that the error is in the second bit. We correct this by changing the second bit from a 1 to a 0. The code word that was supposed to be received is
Since the correction involves finding the column of G that is the same as Gx, this method will only work if G has distinct columns. Hence we need to seek a code matrix C that produces a check matrix G with distinct columns. Since both the matrices C and G are constructed by putting the matrices D and the identity matrices together, we can always find the matrix C if we know the matrix G.
One challenge is to find a matrix G (and thus C) that has distinct columns. In the 1950s, a mathematician named Richard Hamming developed a systematic way of finding a matrix G. He proposed letting the ith column of his matrix be the number i written in binary. For example the numbers from 1 to 6 in binary are
001, 010, 011, 100, 101, 110
Hence we define the Hamming matrix with 6 columns to be
You will notice that the columns of H are all distinct. It is clear that the columns in any Hamming matrix will always be distinct, since if two were the same, then they would represent the same number in binary. To find the code matrix C, we notice that the columns of C are a basis for the null space of H. We can find this basis by putting H into rref (just switch the first and third rows). We get
We find the null space by looking at the equations
x1 + x3 + x5 = 0
x1 = r + s
Hence the null space of H(6) has basis
Hence the code matrix C is
We call this code a (6,3) Hamming code since there are 6 columns of H and the dimension of the null space of H is 3.
You may be concerned that the Hamming matrix, H, and the Code matrix, C, do not fit the criterion of the matrix G, since the last three columns of H do not form the identity matrix and the first three rows of C do not form the identity matrix.. Fortunately, a minor modification will take care of this problem. Notice that the fourth, second, and first columns of H form the identity matrix. Our strategy is to rearrange the columns of H so that it is in the proper form of a check matrix. We can a rearrangement of the columns of a matrix a permutation, and the matrix that performs this transformation is called a permutation matrix. We can find the permutation matrix by correspondingly rearranging the rows of the identity matrix. We will see later that that permutation matrices P have the property that
P-1 = PT
Hence the inverse of a permutation is easy to find.
Below we write how to permute the rows of H(6) to get it in proper form.
So the permutation is given by
6 5 1 4 2 3
To find the permutation matrix corresponding to this permutation, we just take the identity matrix and permute its rows accordingly.
Suppose that the original message was
Then the (6,3) Hamming code sends it to
How do we get back to the original message? We just multiply the matrix with the identity as its first three columns and the zero matrix as the last three with the matrix P-1 = PT.
Multiplying this matrix by Cb gives the original message