Next: Hamming Distance
Up: Linear Codes
Previous: Linear Codes
  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
. Ever 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
=
Below is an applet that demonstrates how words are encoded using a
parity code. At the top of the applet are two boxes, one marked
``block size" and the other ``input words". The word entered in
the second box will be broken up into smaller words with the same
amount of letters as entered in the block size box. If the length
of the word mod the block size is not zero, it will be padded with
spaces. The encoded form of each block will be displayed below the
``encode" button. Each encoded block will have 6*block size+1
numbers in it. The last number is the parity bit. The user can
then change the numbers in the block size to create errors. To
decode/check the parity, press the second button on the applet.
The decoded word will appear at the bottom. If there was an error
in one of the blocks an ``*" will appear in the decode box. The
parity code will only detect an odd number of errors, so if two
numbers in a block are changed the decoded word will not be the
same as the original.
Next: Hamming Distance
Up: Linear Codes
Previous: Linear Codes
  Contents
Frederick Leitner
2004-05-12