Chapter 4 / 4.5 / 4.5.6

4.5.6 Decoding

Although decoding could theoretically be performed by table lookup, this is impractical for large code sets. Instead, matrix algebra is used to verify and correct codewords efficiently. The decoder multiplies the received n-bit word by the transpose of a parity-check matrix, H, that has the property:

where T denotes matrix transposition (rows and columns interchanged). The parity-check matrix corresponding to the generator matrix in Equation (4.17) is:

The decoder computes the syndrome vector S by multiplying the received codeword, R, by the transpose of H:

If S=0, no error is detected; a non-zero syndrome identifies the presence (and pattern) of bit errors.

Example: Block Code

Using the generator matrix in Equation (4.17), determine the output codeword for the input data word D = 0011.

From the data vector D = [0011].

Multiply by G over GF(2):

$C=DG=0.\mathrm{r}\mathrm{o}\mathrm{w}1\oplus 0.\mathrm{r}\mathrm{o}\mathrm{w}2\oplus 1.\mathrm{r}\mathrm{o}\mathrm{w}3\oplus 1.\mathrm{r}\mathrm{o}\mathrm{w}4$

$=\left[0010101\right]\oplus \left[0001011\right]=\left[0011110\right]$

So, the input data word [0011] is transformed into the output code word [0011110].

We can quickly check that the code word is systematic because we can see the data word [0011] as the first four bits of C.

We can further check that the code word is correct by multiplying it by the transpose of the parity check matrix from Equation (4.19) to identify the syndrome, S:

$\begin{array}{c}S=C{H}^T=\left[\text{0011110}\right]\left[\begin{array}{ccc}1& 1& 1\\ 1& 1& 0\\ 1& 0& 1\\ 0& 1& 1\\ 1& 0& 0\\ 0& 1& 0\\ 0& 0& 1\end{array}\right]=\left[000\right]\end{array}$

Since the syndrome is zero, the codeword is correct.

If we look a little closer at the Equation (4.20) we can note that, if we replace the original codeword with the received code word, R, which is the original codeword plus any error—that is R=C+E:

In other words, the syndrome of the received vector depends only on the error and is independent of the code word. Furthermore, the syndrome indicates the location of the error so a single-bit error can be detected and corrected.

Example: Block Code with Errors

In the previous example, we saw that using the generator matrix in Equation (4.17), determine the output codeword for the input data word D = 0011 is C = 0011110.

Consider that an error is introduced in the channel and the received codeword is R = [0011110] which has an error in the second bit (marked with an underscore in this example).

The decoder checks the syndrome, S:

$\begin{array}{c}S=C{H}^T=\left[\text{0}\underset{\_}{1}\text{11110}\right]\left[\begin{array}{ccc}1& 1& 1\\ 1& 1& 0\\ 1& 0& 1\\ 0& 1& 1\\ 1& 0& 0\\ 0& 1& 0\\ 0& 0& 1\end{array}\right]=\left[110\right]\end{array}$

Since the syndrome is non-zero, the codeword is not correct. Furthermore, the syndrome points to the second row in the transpose matrix, indicating that the error is in the second bit.

A little further investigation will show why. The error vector is [0100000] so:

$\begin{array}{c}S=E{H}^T=\left[\text{0}\underset{\_}{1}00000\right]\left[\begin{array}{ccc}1& 1& 1\\ 1& 1& 0\\ 1& 0& 1\\ 0& 1& 1\\ 1& 0& 0\\ 0& 1& 0\\ 0& 0& 1\end{array}\right]=\left[110\right]\end{array}$

Consider that two errors have been introduced in the channel and the received codeword is R = [0001110] which has an error in the second and third bits.

The decoder checks the syndrome, S:

$\begin{array}{c}S=C{H}^T=\left[\text{0}\underset{\_}{1}\underset{\_}{0}\text{1110}\right]\left[\begin{array}{ccc}1& 1& 1\\ 1& 1& 0\\ 1& 0& 1\\ 0& 1& 1\\ 1& 0& 0\\ 0& 1& 0\\ 0& 0& 1\end{array}\right]=\left[011\right]\end{array}$

The syndrome indicates a single error in the fourth bit and therefore the output is [0100110] which is a valid code word corresponding to data word [0100]. So, the decoder detects that the received codeword is not valid but assumes it to be a single-bit error and therefore ‘corrects’ it inappropriately. Remember, with a minimum distance of 3 in a (7,4) code, two errors result in a received code word that is only a single bit different from a valid code word.

Of course, three errors will be undetected by the decoder because it will ‘correctly’ determine the codeword to be valid since in a (7,4) code there is a Hamming distance of 3 between valid code words.