Question

Let C be a q-ary code of length n. Assume the minimal distance d(C) is an odd number, d(C) = 2r + 1. We showed in class that C can always correct up to r errors. That is, whenever a codeword a from C is sent, and r or fewer errors occur in transmission, the Nearest Neighbour Decoding algorithm will decode the received word b correctly (i.e., will decode b as a).

Prove that C cannot always correct r + 1 errors. That is, show that there exists a codeword a in C and a word b with d(a, b) = r + 1 such that when a is transmitted and b is received, the Nearest Neighbour Decoding algorithm (either complete or incomplete) will not decode b correctly.

Answer 1