Efficient Decoding

Given the binary matrix \[\begin{aligned}\end{aligned}\] and the \(5\)-tuples \({\mathbf x} = (\codeword{11011})^\transpose\) and \({\mathbf y} = (\codeword{01011})^\transpose\), we can compute \[\begin{aligned}\end{aligned}\]. 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\). In fact, this is where the error occurred. If we flip the first bit in \({\mathbf y}\) from \(0\) to \(1\), then we obtain \({\mathbf x}\).

Consider the matrix \[\begin{aligned}\end{aligned}\] and suppose that the \(6\)-tuples \({\mathbf x} = (\codeword{111110})^\transpose\), \({\mathbf y} = (\codeword{111111})^\transpose\), and \({\mathbf z} = (\codeword{010111})^\transpose\) have been received. Then \[\begin{aligned}\end{aligned}\]. 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 \((\codeword{110110})\) and \((\codeword{010011})\), respectively. The syndrome of \({\mathbf y}\) does not occur in any of the columns of the matrix \(H\), so multiple errors must have occurred to produce \({\mathbf y}\).

Let \(C\) be the \((5,3)\)-linear code given by the parity-check matrix \[\begin{aligned}\end{aligned}\]. The code consists of the codewords \[\begin{aligned}\end{aligned}\]. There are \(2^{5-2} = 2^3\) cosets of \(C\) in \({\mathbb Z}_2^5\), each with order \(2^2 =4\). These cosets are listed in .

In , 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} = (\codeword{01111})\) is the received word. To decode \({\mathbf r}\), we find that it is in the coset \((\codeword{00010}) + C\); hence, the originally transmitted codeword must have been \((\codeword{01101}) = (\codeword{01111}) + (\codeword{00010})\).