9. Matrix Hamming Codes We now address the question: how can we construct useful error-correcting codes that are easier to handle than randomly chosen codes? Suppose that the messages we will want to encode are all sequences of 0’s and 1’s. We shall design a system to take any sequence of length M, which we call the message word, and encode it by turning it into a somewhat longer sequence of length N called a code word, in such a manner that we can retrieve our message word from the code word, even if one of the digits has been altered. If m is our message, we will say that c(m) is its code word.1 To simplify coding and decoding, we start by giving structure to the message words and code words. Namely, we introduce the notion of addition, both of message words and code words, so that we treat both of these as vectors rather than mere sequences. The notion of addition that we introduce is not the ordinary addition of number you are used to. It differs in two respects: first, 2 is the same as 0, so 1 +1=0. Second, there is no carrying; each bit is independent of each other bit. (Those familiar with modular arithmetic will recognize this as addition mod 2). Thus, for example, 1011110 +1101011 = 0110101 in this system. Remember, in everything that follows 2 = 0! 9.1 Linear Codes The first step we take toward creating codes that are easy to encode and decode is to look at linear codes, which are also called matrix codes. This means that the code word for the sum of two message words will be the sum of the code words of the two message words. So if x and y are two message words, then the following is true for a linear code: c(x) + c( y) = c(x + y) This means, for example, that the code word for 0110101 must be the sum of the code words for the two other sequences above that sum to it. Furthermore, any code word can be written as the sum of two other code words, and the sum of any two code words is another code word. 1 It is not an unrealistic simplification to look at this problem in terms of binary messages because with the advent of computers, almost all messages are converted to binary before being stored or transmitted.This simple condition produces a tremendous simplification in encoding. It means that to define a linear code we need only provide the code words to the members of a basis in the space of messages. Then, since each message can be written as a sum of the basis vectors, the code word for any message is just the sum of the code words for the basis vectors that sum to it. (If you have not taken linear algebra this may not make sense to you. Consult a linear algebra textbook, a professor, or a fellow student to get the definition of a basis for a vector space). We now make some helpful definitions. The weight of a word or vector is the number of 1’s in it. So 0110101 has a weight of 4. The standard basis for message words will be the vectors of weight 1; if that 1 occurs in the j-th place in the message, we denote it as <j>. So, for example, 1000, 0100, 0010, and 0001 are the standard basis vectors of length 4, and <3> is the vector 0010 since the 1 is in the third place of the message vector. We can, as noted above, define our code completely by assigning a code word to each of the message vectors <j>. We form these code words into a matrix C, called the encoding matrix, whose j-th row is the code word for the message vector <j>. Here is an example of a code matrix C, which defines a code with N=7, given a message space with message vectors of length 4. We have 4 basis vectors so our matrix will have 4 rows, each of length 7: C = 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 The code word for 1010 = <1> + <3> will then be the sum of the first and third rows of the matrix, and a similar statement holds for any other combination of the basis vectors. The rule for encoding a message vector m is: C(m)= mC where the product mC is ordinary matrix multiplication2 of the row vector m and the matrix C (we use bold face to denote a vector). The rule for matrix multiplication is that you take the dot product of each row of the left factor with each column of the right factor and put the result in the row corresponding to that of the left factor and the column corresponding to the column chosen in the right factor. ⎤ ⎡ ⎥⎥⎥⎥ ⎢⎢⎢⎢ ⎦ ⎣ 2In our case, m has only one row while C has 7 columns, so our code word then is row vector of length 7. In this case, we need only define code words for 4 basis vectors in order to define code words for 24 or 16 potential messages. With longer message vectors, the difference between M and 2M becomes much greater. Thus, for M=10 we have only to define 10 basis message code words to provide a code that allows 210 or 1024 possible messages. 9.2 Constructing Linear Error Correcting Codes We have now shown how we can rather quickly develop a code by simply finding code words for the basis vectors of the message space. However, we have not yet addressed error correction, which is what we are trying to do. We now ask: what do we have to do to obtain a single error correcting linear code? (Later we will see how to correct more than 1 error). If we are using messages of length 4 and codes of length 7 as in the example above, we see that of the 27 = 128 possible sequences of length 7, only 16 of them are code words. This means that if an error is introduced into a code word, and one bit is changed, then it is likely that the new sequence may not be a code word at all. This fact will be very helpful in the discussion that follows. We can decode a received message, one that may have an error, by finding the code word that differs in the fewest bits from it. Thus, we will look for the code word whose Hamming distance from the received word is smallest. If the received message is a code word, then we will assume that no error has been introduced and just decode it as it stands. However, what if the error is such that it changes one code word into another? In this case, there would be no way for us to detect whether or not an error has occurred. Furthermore, it could be that there …