Consider the binary code C = {00000, 10011, 01010, 11001, 00101, 10110, 01111, 11100}. Use nearest-neighbor decoding to decode 11101 and 01100. If the received word 11101 has exactly one error, can you determine the intended code word? Explain your reasoning.
The Correct Answer and Explanation is:
To solve this, we’ll decode the received words using nearest-neighbor decoding, which finds the codeword in CC that has the smallest Hamming distance from the received word.
Part 1: Nearest-Neighbor Decoding
Let’s compute the Hamming distance between each received word and every codeword in CC:
Code CC:
{00000, 10011, 01010, 11001, 00101, 10110, 01111, 11100}
a) Received word: 11101
| Codeword | Hamming Distance from 11101 |
|---|---|
| 00000 | 4 |
| 10011 | 3 |
| 01010 | 4 |
| 11001 | 1 ← closest |
| 00101 | 2 |
| 10110 | 3 |
| 01111 | 3 |
| 11100 | 1 ← tie |
Nearest neighbors: 11001 and 11100 (both distance 1)
b) Received word: 01100
| Codeword | Hamming Distance from 01100 |
|---|---|
| 00000 | 2 |
| 10011 | 4 |
| 01010 | 2 |
| 11001 | 3 |
| 00101 | 3 |
| 10110 | 4 |
| 01111 | 1 ← closest |
| 11100 | 1 ← tie |
Nearest neighbors: 01111 and 11100 (both distance 1)
Part 2: One-bit Error in 11101?
If 11101 has exactly one error, it must differ from the correct codeword by only one bit.
From above, two codewords (11001 and 11100) are 1 bit away. Since two codewords are equally close, we cannot determine with certainty which one was the intended codeword without additional information. The presence of two equally valid nearest neighbors prevents unique decoding.
Conclusion
Nearest-neighbor decoding selects the closest codeword to the received word based on Hamming distance. For the binary code C={00000,10011,01010,11001,00101,10110,01111,11100}C = \{00000, 10011, 01010, 11001, 00101, 10110, 01111, 11100\}, we decode the received words 11101 and 01100 by calculating the Hamming distance between each received word and every codeword.
For 11101, the closest codewords are 11001 and 11100, each with a Hamming distance of 1. This implies a tie between two nearest neighbors. Similarly, for 01100, the nearest codewords are 01111 and 11100, also both at distance 1. Nearest-neighbor decoding would thus yield ambiguity in both cases, with two codewords equally close to the received word.
Now, considering the case where 11101 has exactly one error, we expect the correct codeword to be at a Hamming distance of 1. However, since two codewords (11001 and 11100) satisfy this criterion, we cannot determine uniquely which was the original transmitted word. A decoding algorithm that relies only on Hamming distance cannot resolve ties without further context (such as frequency of transmission or error probabilities).
This situation highlights an important limitation in code design: if the minimum distance between codewords is less than 3, the code cannot correct one-bit errors uniquely. Therefore, while nearest-neighbor decoding can identify candidates, a code must be designed with a sufficient minimum distance to guarantee unique correction of single-bit errors.
