Linear Codes

Codes over $\FF[2]$ Lets suppose we are receiving a sequnce that has been encoded by adding a parity bit $G^t:\FF[2]^2 \rightarrow \FF[2]^3$ and we receive $r= \left( \begin{array}{c} 1\\ 0\\ 0 \end{array} \right)$. 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 $\epsilon$C? We need to check that the parity bit for r is a valid i.e. r has to be of the form r= $\left(\begin{array}{c}u_1\\ u_2\\ u_1+u_2 \end{array} \right)$ for some $u_1$ and $u_2$. In r we have $u_1=1,u_2=0,u_1+u_2=1\neq0$. 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: $\left( \begin{array}{c} 0\\ 0\\ 0 \end{array} \right)$ $\left( \begin{array}{c}1\\ 1\\ 0 \end{array} \right)$ $\left( \begin{array}{c} 1\\ 0\\ 1 \end{array} \right)$ These correspond to the unencoded words: $\left( \begin{array}{c} 0\\ 0 \end{array} \right)$ $\left( \begin{array}{c} 1\\ 1 \end{array} \right)$ $\left( \begin{array}{c} 1\\ 0 \end{array} \right)$ 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:

$G^t:\FF[2]^2 \rightarrow \FF[2]^4$ *Suppose we receive $e = \left( \begin{array}{c} 1\\ 1\\ 0\\ 1 \end{array} \right)$ *Is e a codeword? No. Possibilities for one error? $\left( \begin{array}{c} 1 \\ 0\\ 0\\ 1 \end{array} \right) \leftarrow$ closest valid codeword. *correct the error and e should be $\left( \begin{array}{c} 1 \\ 0\\ 0\\ 1 \end{array} \right)$ We should take a moment to explain some notation. The matrix $G$ 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 $G$ has the form:

$$G = ( I_{k\times k} \vert P)$$

Here $k$ is the dimension of the ``source'' space, i.e. the number of bits of information we wish to encode, and $I_{k\times k}$ is the identity matrix. The matrix $P$ describes the new information added in the encoding. Thus if $w$ is an unencoded word that we wish to transmit, we get an encoded word by computing $G^tw$. There is another matrix, formed from $P$, called the Parity Check Matrix which we denote by $H$. 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 $n$-dimensional vector space that $H$ has the form:

$$H = (-P^t \vert I_{(n-k)\times(n-k})$$

To see if there is an error in a received word $r$ we only need to determine if $Hr$ is not the zero vector.