** Next:** Parity Codes
** Up:** Spring 2004 Final Report
** Previous:** Finite Fields
** Contents**

__Codes over __
Lets suppose we are receiving a sequnce 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:** Parity Codes
** Up:** Spring 2004 Final Report
** Previous:** Finite Fields
** Contents**
Frederick Leitner
2004-05-12