In Section 4.2.5, we proved an upper bound for the rate of a code with a particular minimum distance, based on the volume of “spheres” around each codeword. There are other bounds that we can prove,...

In Section 4.2.5, we proved an upper bound for the rate of a code with a particular minimum distance, based on the volume of “spheres” around each codeword. There are other bounds that we can prove, with different justification

Suppose that we have a code C ⊆ {0, 1} n with |C| = 2k and minimum distance d. Prove the Singleton bound, which states that k ≤ n − d + 1. (Hint: what happens if we delete the first d − 1 bits from each codeword?)