More on Coding

Code Matrices

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.

Check Matrices

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

or

       b₁ + 1  =  0                        b₂ + 1  =  0
       b₃        =  0                        b₄ + 1  =  0
       b₅ + 1  =  0                        b₆        =  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

Theorem

The matrix transformation e(b) = Cb  where C is the identity matrix on top of the matrix D has check matrix

        G  =  [D  I_n-m]

Once we find the check matrix G, we can use it to see if a signal is a code word.  If it is, we can then decode it.  If it is not, then G can also assist us in correcting the signal and finding the correct code word.  Suppose that the code word that was supposed to be sent was x and that there was a single error in the i^th position.  Then the signal received will be

        x_i  =  x + e_i 

where e_i is the i^th basis vector.  Now notice that

        Gx_i  =  G(x + e_i)  =  Gx + Ge_i 

        =  0 + col_i(G)  =  col_i(G)

where col_i(G) is the i^th column of G.

This tells us that if a single error occurs in the i^th entry, then multiplying by G will produce the i^th column of G.  Hence we can just compare Gx with the columns of G to find the location of the error.

Example

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.  

Hamming Codes

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

        x₁ + x₃ + x₅  =  0
        x₂ + x₃ + x₆  =  0
        x₄ + x₅ + x₆  =  0

        x₁  =  r + s
        x₂  =  r + t
        x₃  =  r
        x₄  =  s + t
        x₅  =  s
        x₆  =  t

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  =  P^T

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.

Example

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  =  P^T.

Multiplying this matrix by Cb gives the original message

Back to the Matrices and Applications Home Page

Back to the Linear Algebra Home Page

Back to the Math Department Home Page

e-mail Questions and Suggestions