0.13 Coding  (Page 17/22)

Channel coding

some redundancy to a signal before it is transmitted so that it becomes possible to detect when errors have occurredand to correct them, when possible.

Perhaps the simplest technique is to send each bit three times. Thus, in order to transmit a 0, the sequence 000is sent. In order to transmit 1, 111 is sent.This is the encoder . At the receiver, there must be a decoder . There are eight possible sequences that can be received,and a “majority rules” decoder assigns

This encoder/decoder can identify and correct any isolated single error and so the transmissionhas smaller probability of error. For instance, assuming no more than one error per block, if101 was received, then the error must have occurred in the middle bit, while if 110 was received,then the error must have been in the third bit. But the majority rules coding scheme is costly:three times the number of symbols must be transmitted, which reduces the bit rate by a factor of three.Over the years, many alternative schemes have been designed to reduce the probability of error in thetransmission, without incurring such a heavy penalty.

Linear block codes are popular because they are easy to design, easy to implement, and because they havea number of useful properties. With $n>k$ , an $(n,k)$ linear code operates on sets of $k$ symbols, and transmits a length $n$ code word for each set. Each code is defined by two matrices:the $k$ by $n$ generator matrix $G$ , and the $n-k$ by $n$ parity check matrix $H$ . In outline, the operation of the code is as follows:

1. Collect $k$ symbols into a vector $\mathbf{x}=\{x_1,x_2,...,x_k\}$ .
2. Transmit the length $n$ code word $\mathbf{c}=\mathbf{x}G$ .
3. At the receiver, the vector $\mathbf{y}$ is received. Calculate $\mathbf{y}{H}^T$ .
4. If $\mathbf{y}{H}^T=0$ , then no errors have occurred.
5. When $\mathbf{y}{H}^T\ne 0$ , errors have occurred. Look up $\mathbf{y}{H}^T$ in a table of “syndromes,” which contains a list of all possible received valuesand the most likely code word to have been transmitted, given the error that occurred.
6. Translate the corrected code word back in to the vector $\mathbf{x}$ .

The simplest way to understand this is to work through an example in detail.

A $(\mathbf{5},\mathbf{2})$ Binary linear block code

To be explicit, consider the case of a $(5,2)$ binary code with generator matrix

and parity check matrix

This code bundles the bits into pairs, and the four corresponding code words are

There is one subtlety. The arithmetic used in the calculation of the code words (and indeed throughout the linear block codemethod) is not standard. Because the input source is binary, the arithmetic is also binary.Binary addition and multiplication are shown in [link] . The operations of binary arithmetic may be more familiar as exclusive OR (binary addition), and logical AND (binary multiplication).