# Example of a code that can be decoded using bounded distance decoder

In the book Information theory, Inference and Learning Algorithm, in chapter 13, MacKay defines bounded distance decoding

A bounded distance decoder is a decoder that returns the closest codeword to a received binary vector $$\mathbf{r}$$ if the distance from $$\mathbf{r}$$ to that codeword is less than or equal to $$t$$; otherwise it returns a failure message.

Could anybody provide an example of a simple linear code that can be decoded by such a bounded distance decoder?

The simplest example is a repetition code. You encode the bit 0 as 000 and the bit 1 as 111. The decoder outputs the majority bit, which is always at distance at most $$t = 1$$.

As another example, suppose we encode 0 as 0000 and 1 as 1111. We can still correct up to one error (by taking the majority), but we cannot accommodate $$t = 2$$, since given 0011 we can't tell whether it came from 0000 or from 1111. Therefore we need to declare failure.

Any perfect code will do. A perfect code is a $$t-$$error correcting code where the spheres of Hamming radius $$t$$ around the codewords cover the whole space.

Edit: In response to OP's comment, if the $$t-$$spheres around codewords overlap, the code, by definition, is not a $$t-$$error correcting code.

In general, all decoding algorithms used in practice are bounded distance decoding algorithms, since except for very short lengths, it is not feasible to do a brute force comparison of the received word with all codewords.

The Syndrome decoding of a linear code is one such example, see any coding textbook, as well as Wikipedia entry here

• thanks, I was looking for examples of nonperfect codes for which this becomes necessary Commented Oct 9, 2019 at 17:01
• what becomes necessary, sorry? Commented Nov 3, 2019 at 0:30
• in a perfect code the distance from the received codeword to the nearest codeword is never more than the minimum distance. An error can be erroneously corrected, but the decoder will never know, e.g. in the repetition code, two errors might turn $000$ in $110$, which will be corrected into $111$, but the distance from $110$ to the nearest codeword is still $1$, hence the decoder will never "give up". You might construct a perfect code of distance $5$ and artificially give up on correcting more than $1$ error, but [...] Commented Nov 3, 2019 at 10:03
• I was asking if there are codes where the spheres do overlap and to avoid this we bound the maximum distance of the decoding Commented Nov 3, 2019 at 10:04