** Next:** Hamming Codes
** Up:** Linear Codes
** Previous:** Linear Maps
** Contents**

__Parity__
In order to transmit words, unencoded words are assigned to vectors.
Each letter of a word is matched to an element of a finite field.
The finite field we have been working with is
,
which has 64 elements. Each element is a dimension 6 vector over
. Every word vector is actually a series of letter
vectors. The letter vectors we are using have six numbers in them,
and these numbers can only be a one or a zero. We assign the letters
as in Section 3.3 ``Sentences as Numbers.
Let's say we wanted to transmit a word across a transmission line
that was noisy and might corrupt or data. One simple method for
trying to determining if the data is corrupt is to add a ``parity
bit" to the end of the unencoded word. The parity bit is the sum
of the letter vectors in the word. To encode the word we would
line up our letter vectors in the appropriate order, add all the
numbers together, and then append the word vector with this sum.
In order to encode a word like 'ace', we would transmit the binary
sequence: '000000' '010000' '001000' '__0__'. The
underlined last zero is the parity of the word 'ace'. Abstractly,
this can be illustrated by the following:
P

In the subsection ``Sentences as Numbers" there is an applet that
will convert between the words in our field and their base 2
representation.
When codewords are received, they are checked against the set of
possible encoded words to see if there are any errors. The short
coming of parity checking is that we can only detect an odd number
of errors, and we cannot say how many errors there are (whether
there are 1, 3, 5, etc. number of errors).

__Simple Example__
``parity
bit"

is the domain and
is the
codomain (not the
range).

{ set of possible unencoded words }

= {
}

=

C = range of encoding
= all possible encoded words

={
}
= {
}
__Notice__:
``subset". sits inside of

*Not everything in
is an encoded word. The
codewords are a special subset of
. This means
that all of the codewords are in that finite field, but there are
also elements of the finite field that are not codewords. For
example, if you received a codeword with an error, this corrupted
word would be in , but it would not be in the subset .
__Ex__
M

Now we want to add a ``parity bit" to a binary sequence (the
vector with for example). This added element will be 0 if
is even and 1 if is odd. This operation can be
written in terms of matricies over
as follows:
__Matrix__ for the ``parity bit"

=

G=
In general, to add a parity bit to a sequence
we use the matrix:
There are ones at the bottom of that matrix. The symbol
denotes the identity matrix which has
ones along the diagonal and zeros elsewhere. This matrix is the
from above. G is called the ``generating matrix". G is
discussed more in the sections on Linear Mapping and Hamming
Codes.
__Matrix__

codeword
=

codeword
=

** Next:** Hamming Codes
** Up:** Linear Codes
** Previous:** Linear Maps
** Contents**
Frederick Leitner
2004-09-01