    Next: Linear Maps Up: Summer 2004 Final Report Previous: Matrices and Matrix Operations   Contents

# Linear Codes

Codes over Let's suppose we are receiving a sequence that has been encoded by adding a parity bit and we receive . We can ask, is this a codeword? If C=Im(G) denotes the set of all possible encoded words, then this is asking is r C? We need to check that the parity bit for r is a valid i.e. r has to be of the form r= for some and . In r we have . This means that received word r was not a valid codeword. In other words, we has an error in the transmitting. If we assume only one error was decoded we the following possibilities by changing the 1st, 2nd and 3rd entries respectively:   These correspond to the unencoded words:   Unfortunately, we have noway to distinguish between these possibilities, no way to find where the error was. All we can do is ask the sender to retransmit the encoded word. Another solution is to use a code which allows us to fix error. One example is the Hamming Code, which are discussed in more detail in later sections. The process of determining an error using a Hamming Code would look something like this: *Suppose we receive *Is e a codeword? No. Possibilities for one error? closest valid codeword. *correct the error and e should be We should take a moment to explain some notation. The matrix is called the Generating matrix for our code. The (transpose of the ) rows of this matrix form a basis for the space of encoded words. Using our standard basis, we can always assume that, for whatever code we use, that has the form: Here is the dimension of the source'' space, i.e. the number of bits of information we wish to encode, and is the identity matrix. The matrix describes the new information added in the encoding. Thus if is an unencoded word that we wish to transmit, we get an encoded word by computing . There is another matrix, formed from , called the Parity Check Matrix which we denote by . This matrix is used to test whether a received work is actually a code word, i.e. that there were no errors in transmission. If the code words live in a -dimensional vector space that has the form: To see if there is an error in a received word we only need to determine if is not the zero vector.

Subsections    Next: Linear Maps Up: Summer 2004 Final Report Previous: Matrices and Matrix Operations   Contents
Frederick Leitner 2004-09-01