Parity Codes

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 $\FF[2^6]$, which has 64 elements. Each element is a dimension 6 vector over $\FF[2]$. 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: $\FF[2]^{18} \rightarrow$P $\rightarrow \FF[2]^{19}$
$\left(\begin{array}{c}u_1\\ \vdots\\ u_{18} \end{array}\right) \longrightarrow... ...array}{c}u_1\\ u_2\\ \vdots\\ u_{18}\\ u_1+u_2+\dots+u_{18} \end{array}\right)$ 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 $\FF[2]^2$ $\rightarrow (P=$``parity bit" $)\rightarrow \FF[2]^3$

$$\left( \begin{tabular}{c} $u_1$\\ $u_2$ \end{tabular} \righ... ...t( \begin{tabular}{c} $u_1$\\ $u_2$\\ $u_1+u_2$ \end{tabular} \right)$$

$\FF[2]^2$ is the domain and $\FF[2]^3$ is the codomain (not the range).
$U=${ set of possible unencoded words }
= { $$\left( \begin{array}{c} 0\\ 0 \end{array} \right), \lef... ...ight), \left( \begin{array}{c} 1\\ 1 \end{array} \right)$$ }
= $\FF[2]^2$
C = range of encoding = all possible encoded words
={ $$P \left( \begin{array}{c} 0\\ 0 \end{array} \right), P ... ...ht), P \left( \begin{array}{c} 1\\ 1 \end{array} \right)$$ } = { $$\left( \begin{array}{c} 0\\ 0\\ 0 \end{array} \right)... ... \left( \begin{array}{c} 1\\ 1\\ 0 \end{array} \right)$$ } Notice: $C\neq\FF[2]^3$ $C\subseteq\FF[2]^3$ ``subset". $C$ sits inside of $\FF[2]^3$
*Not everything in $\FF[2]^3$ is an encoded word. The codewords are a special subset of $\FF[2]^3$. 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 $\FF[2]^3$, but it would not be in the subset $C$. Ex $\FF[2]^2\rightarrow$ M $\rightarrow\FF[2]^4$

$$\left( \begin{array}{c} 0\\ 0 \end{array} \right) \righta... ... \left( \begin{array}{c} 0\\ 0\\ 0\\ 0 \end{array} \right)$$

$$\left( \begin{array}{c} 1\\ 0 \end{array} \right) \righta... ... \left( \begin{array}{c} 1\\ 0\\ 0\\ 1 \end{array} \right)$$

$$\left( \begin{array}{c} 0\\ 1 \end{array} \right) \righta... ... \left( \begin{array}{c} 0\\ 1\\ 1\\ 1 \end{array} \right)$$

$$\left( \begin{array}{c} 1\\ 1 \end{array} \right) = \left... ...( \begin{array}{c} 1\\ 1\\ 1\\ 0 \end{array} \right)$$

Now we want to add a ``parity bit" $u_3$ to a binary sequence (the vector with $u_1, u_2$ for example). This added element will be 0 if $u_1+u_2$ is even and 1 if $u_1+u_2$ is odd. This operation can be written in terms of matricies over $\FF[2]$ as follows: Matrix for the ``parity bit" $G^t:\FF[2]^2 \rightarrow \FF[2]^3$
= $G^t*{ u_1 \choose u_2 }$

$$G^t{u_1 \choose u_2} = \left( \begin{array}{cc} 1&0\\ 0&1... ...egin{array}{c} u_1\\ u_2\\ u_3 \end{array} \right)$$

G= $\left( \begin{array}{ccc} 1&0&1\\ 0&1&1 \end{array} \right)$ In general, to add a parity bit $u_{n+1}$ to a sequence $(u_1,u_1,\hdots, u_n)$ we use the matrix:

$$\left( \begin{array}{cccccc} & & I_{nxn}\\ 1&1&1&1&\hdots&1 \end{array}\right)$$

There are $n$ ones at the bottom of that matrix. The symbol $I_{n\times n}$ denotes the $n\times n$ identity matrix which has ones along the diagonal and zeros elsewhere. This matrix is the $G^t$ from above. G is called the ``generating matrix". G is discussed more in the sections on Linear Mapping and Hamming Codes. Matrix
$\FF[2]^3 \rightarrow \FF[2]^4$
$\FF[2]^3$ codeword $\rightarrow$ $P*\FF[2]^3$ = $\FF[2]^4$
$\FF[2]^n$ codeword $\rightarrow$ $P*\FF[2]^n$ = $\FF[2]^{n+1}$

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.