0.13 Coding  (Page 18/22)

In effect, at the end of every calculation, the answer is taken modulo 2.For instance, in standard arithmetic, $x_{4}G=11112$ . The correct code word $c_4$ is found by reducing each calculation modulo 2. In M atlab , this is done with mod(x4*g,2) where x4=[1,1] and g is defined as in [link] . In modulo 2 arithmetic, 1 represents any odd number and0 represents any even number. This is also true for negative numbers so that, for instance, $-1=+1$ and $-4=0$ .

After transmission, the received signal $\mathbf{y}$ is multiplied by $H^T$ . If there were no errors in transmission, then $\mathbf{y}$ is equal to one of the four code words $c_i$ . With $H$ defined as in [link] , $c_1{H}^T=c_2{H}^T=c_3{H}^T=c_4{H}^T=0$ , where the arithmetic is binary, and where 0 means thezero vector of size 1 by 3 (in general, 1 by $(n-k)$ ). Thus $\mathbf{y}{H}^T=0$ and the received signal is one of the code words.

However, when there are errors, $\mathbf{y}{H}^T\ne 0$ , and the value can be used to determine the most likely errorto have occurred. To see how this works, rewrite

where $\mathbf{e}$ represents the error(s) that have occurred in the transmission. Note that

since $\mathbf{c}{H}^T=0$ . The value of $\mathbf{e}{H}^T$ is used by looking in the syndrome [link] . For example, suppose that the symbol $x_2=01$ is transmitted using the code $c_2=01011$ . But an error occurs in transmission so that $\mathbf{y}=11011$ is received. Multiplication by the parity check matrix gives $\mathbf{y}{H}^T=\mathbf{e}{H}^T=101$ . Looking this up in the syndrome table shows that the most likely error was 10000.Accordingly, the most likely code word to have been transmitted was $\mathbf{y}-\mathbf{e}=11011-10000=01011$ , which is indeed the correct code word $c_2$ .

On the other hand, if more than one error occurred in a single symbol, then the (5,2) code cannot necessarilyfind the correct code word. For example, suppose that the symbol $x_2=01$ is transmitted using the code $c_2=01011$ but that two errors occur in transmission so that $\mathbf{y}=00111$ is received. Multiplication by the parity check matrix gives $\mathbf{y}{H}^T=\mathbf{e}{H}^T=111$ . Looking this up in the syndrome table shows that the most likely error was 10010.Accordingly, the most likely symbol to have been transmitted was $\mathbf{y}-\mathbf{e}=00111+10010=10101$ , which is the code word $c_3$ corresponding to the symbol $x_3$ , and not $c_2$ .

The syndrome table can be built as follows. First, take each possible single error pattern, that is, each ofthe $n=5$ $\mathbf{e}$ 's with exactly one 1, and calculate $\mathbf{e}{H}^T$ for each. As long as the columns of $H$ are nonzero and distinct, each error pattern corresponds to a different syndrome.To fill out the remainder of the table, take each of the possible double errors (each of the $\mathbf{e}$ 's with exactly two 1's) and calculate $\mathbf{e}{H}^T$ . Pick two that correspond to the remaining unused syndromes.Since there are many more possible double errors $n(n-1)=20$ than there are syndromes ( $2^{n-k}=8$ ), these are beyond the ability of the code to correct.

The M atlab program blockcode52.m shows details of how this encoding and decoding proceeds. The first part defines the relevantparameters of the $(5,2)$ binary linear block code: the generator g , the parity check matrix h , and the syndrome table syn . The rows of syn are ordered so that the binary digits of $e{H}^T$ can be used to directly index into the table.