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 $\mathbb{F}_{2^6}$, which has 64 elements. Each element is a dimension 6 vector over $\mathbb{F}_{2}$. 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: $\mathbb{F}_{2}^{18} \rightarrow$P $\rightarrow \mathbb{F}_{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 $\mathbb{F}_{2}^2$ $\rightarrow (P=$``parity bit" $)\rightarrow \mathbb{F}_{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)$$

$\mathbb{F}_{2}^2$ is the domain and $\mathbb{F}_{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)$$ }
= $\mathbb{F}_{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\mathbb{F}_{2}^3$ $C\subseteq\mathbb{F}_{2}^3$ ``subset". $C$ sits inside of $\mathbb{F}_{2}^3$
*Not everything in $\mathbb{F}_{2}^3$ is an encoded word. The codewords are a special subset of $\mathbb{F}_{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 $\mathbb{F}_{2}^2\rightarrow$ M $\rightarrow\mathbb{F}_{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 $\mathbb{F}_{2}$ as follows: Matrix for the ``parity bit" $G^t:\mathbb{F}_{2}^2 \rightarrow \mathbb{F}_{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
$\mathbb{F}_{2}^3 \rightarrow \mathbb{F}_{2}^4$
$\mathbb{F}_{2}^3$ codeword $\rightarrow$ $P*\mathbb{F}_{2}^3$ = $\mathbb{F}_{2}^4$
$\mathbb{F}_{2}^n$ codeword $\rightarrow$ $P*\mathbb{F}_{2}^n$ = $\mathbb{F}_{2}^{n+1}$