$\newcommand{\identity}{\mathrm{id}} \newcommand{\notdivide}{\nmid} \newcommand{\notsubset}{\not\subset} \newcommand{\lcm}{\operatorname{lcm}} \newcommand{\gf}{\operatorname{GF}} \newcommand{\inn}{\operatorname{Inn}} \newcommand{\aut}{\operatorname{Aut}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\cis}{\operatorname{cis}} \newcommand{\chr}{\operatorname{char}} \newcommand{\Null}{\operatorname{Null}} \newcommand{\transpose}{\text{t}} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&}$

## Section8.4Efficient Decoding

We are now at the stage where we are able to generate linear codes that detect and correct errors fairly easily, but it is still a time-consuming process to decode a received $n$-tuple and determine which is the closest codeword, because the received $n$-tuple must be compared to each possible codeword to determine the proper decoding. This can be a serious impediment if the code is very large.

###### Example8.35

Given the binary matrix

\begin{equation*} H = \begin{pmatrix} 1 & 1 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 & 1 \end{pmatrix} \end{equation*}

and the $5$-tuples ${\mathbf x} = (11011)^\transpose$ and ${\mathbf y} = (01011)^\transpose\text{,}$ we can compute

\begin{equation*} H{\mathbf x} = \begin{pmatrix} 0 \\ 0 \\ 0 \end{pmatrix} \qquad \text{and} \qquad H{\mathbf y} = \begin{pmatrix} 1 \\ 0 \\ 1 \end{pmatrix}. \end{equation*}

Hence, ${\mathbf x}$ is a codeword and ${\mathbf y}$ is not, since ${\mathbf x}$ is in the null space and ${\mathbf y}$ is not. Notice that $H{\mathbf y}$ is identical to the first column of $H\text{.}$ In fact, this is where the error occurred. If we flip the first bit in ${\mathbf y}$ from $0$ to $1\text{,}$ then we obtain ${\mathbf x}\text{.}$

If $H$ is an $m \times n$ matrix and ${\mathbf x} \in {\mathbb Z}_2^n\text{,}$ then we say that the syndrome of ${\mathbf x}$ is $H{\mathbf x}\text{.}$ The following proposition allows the quick detection and correction of errors.

The proof follows from the fact that

\begin{equation*} H{\mathbf x} = H({\mathbf c} +{\mathbf e}) = H{\mathbf c} + H{\mathbf e} = {\mathbf 0} + H{\mathbf e} = H{\mathbf e}. \end{equation*}

This proposition tells us that the syndrome of a received word depends solely on the error and not on the transmitted codeword. The proof of the following theorem follows immediately from Proposition 8.36 and from the fact that $H{\mathbf e}$ is the $i$th column of the matrix $H\text{.}$

###### Example8.38

Consider the matrix

\begin{equation*} H = \begin{pmatrix} 1 & 0 & 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 & 1 & 0 \\ 1 & 1 & 1 & 0 & 0 & 1 \end{pmatrix} \end{equation*}

and suppose that the $6$-tuples ${\mathbf x} = (111110)^\transpose\text{,}$ ${\mathbf y} = (111111)^\transpose\text{,}$ and ${\mathbf z} = (010111)^\transpose$ have been received. Then

\begin{equation*} H{\mathbf x} = \begin{pmatrix} 1 \\ 1 \\ 1 \end{pmatrix}, H{\mathbf y} = \begin{pmatrix} 1 \\ 1 \\ 0 \end{pmatrix}, H{\mathbf z} = \begin{pmatrix} 1 \\ 0 \\ 0 \end{pmatrix}. \end{equation*}

Hence, ${\mathbf x}$ has an error in the third bit and ${\mathbf z}$ has an error in the fourth bit. The transmitted codewords for ${\mathbf x}$ and ${\mathbf z}$ must have been $(110110)$ and $(010011)\text{,}$ respectively. The syndrome of ${\mathbf y}$ does not occur in any of the columns of the matrix $H\text{,}$ so multiple errors must have occurred to produce ${\mathbf y}\text{.}$

### SubsectionCoset Decoding

We can use group theory to obtain another way of decoding messages. A linear code $C$ is a subgroup of ${\mathbb Z}_2^n\text{.}$ Coset or standard decoding uses the cosets of $C$ in ${\mathbb Z}_2^n$ to implement maximum-likelihood decoding. Suppose that $C$ is an $(n,m)$-linear code. A coset of $C$ in ${\mathbb Z}_2^n$ is written in the form ${\mathbf x} + C\text{,}$ where ${\mathbf x} \in {\mathbb Z}_2^n\text{.}$ By Lagrange's Theorem (Theorem 6.10), there are $2^{n-m}$ distinct cosets of $C$ in ${\mathbb Z}_2^n\text{.}$

###### Example8.39

Let $C$ be the $(5,3)$-linear code given by the parity-check matrix

\begin{equation*} H = \begin{pmatrix} 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 & 1 \end{pmatrix}. \end{equation*}

The code consists of the codewords

There are $2^{5-2} = 2^3$ cosets of $C$ in ${\mathbb Z}_2^5\text{,}$ each with order $2^2 =4\text{.}$ These cosets are listed in Table 8.40.

Our task is to find out how knowing the cosets might help us to decode a message. Suppose that ${\mathbf x}$ was the original codeword sent and that ${\mathbf r}$ is the $n$-tuple received. If ${\mathbf e}$ is the transmission error, then ${\mathbf r} = {\mathbf e} + {\mathbf x}$ or, equivalently, ${\mathbf x} = {\mathbf e} + {\mathbf r}\text{.}$ However, this is exactly the statement that ${\mathbf r}$ is an element in the coset ${\mathbf e} + C\text{.}$ In maximum-likelihood decoding we expect the error ${\mathbf e}$ to be as small as possible; that is, ${\mathbf e}$ will have the least weight. An $n$-tuple of least weight in a coset is called a coset leader. Once we have determined a coset leader for each coset, the decoding process becomes a task of calculating ${\mathbf r} + {\mathbf e}$ to obtain ${\mathbf x}\text{.}$

###### Example8.41

In Table 8.40, notice that we have chosen a representative of the least possible weight for each coset. These representatives are coset leaders. Now suppose that ${\mathbf r} = (01111)$ is the received word. To decode ${\mathbf r}\text{,}$ we find that it is in the coset $(00010) + C\text{;}$ hence, the originally transmitted codeword must have been $(01101) = (01111) + (00010)\text{.}$

A potential problem with this method of decoding is that we might have to examine every coset for the received codeword. The following proposition gives a method of implementing coset decoding. It states that we can associate a syndrome with each coset; hence, we can make a table that designates a coset leader corresponding to each syndrome. Such a list is called a decoding table.

Two $n$-tuples ${\mathbf x}$ and ${\mathbf y}$ are in the same coset of $C$ exactly when ${\mathbf x} - {\mathbf y} \in C\text{;}$ however, this is equivalent to $H({\mathbf x} - {\mathbf y}) = 0$ or $H {\mathbf x} = H{\mathbf y}\text{.}$

###### Example8.44

Table 8.42 is a decoding table for the code $C$ given in Example 8.39. If ${\mathbf x} = (01111)$ is received, then its syndrome can be computed to be

\begin{equation*} H {\mathbf x} = \begin{pmatrix} 0 \\ 1 \\ 1 \end{pmatrix}. \end{equation*}

Examining the decoding table, we determine that the coset leader is $(00010)\text{.}$ It is now easy to decode the received codeword.

Given an $(n,k)$-block code, the question arises of whether or not coset decoding is a manageable scheme. A decoding table requires a list of cosets and syndromes, one for each of the $2^{n - k}$ cosets of $C\text{.}$ Suppose that we have a $(32, 24)$-block code. We have a huge number of codewords, $2^{24}\text{,}$ yet there are only $2^{32 - 24} = 2^{8} = 256$ cosets.