Let’s extend the idea of the parity-check code, from the previous exercise, as an add-on to any existing code with odd minimum distance. Let C ⊆ {0, 1} n be a code with minimum distance 2t + 1, for...

Let’s extend the idea of the parity-check code, from the previous exercise, as an add-on to any existing code with odd minimum distance. Let C ⊆ {0, 1} n be a code with minimum distance 2t + 1, for some integer t ≥ 0. Consider a new code C ′ , in which we augment every codeword of C by adding a parity bit, which is zero if the number of ones in the original codeword is even and one if the number is odd, as follows:

Then the minimum distance of C ′ is 2t + 2. (Hint: consider two distinct codewords x, y ∈ C. You have to argue that the corresponding codewords x′ , y ′ ∈ C have Hamming distance 2t + 2 or more. Use two different cases, depending on the value of ∆(x, y).)