Singleton Bound - Proof

Proof

First observe that there are many q-ary words of length, since each letter in such a word may take one of different values, independently of the remaining letters.

Now let be an arbitrary q-ary block code of minimum distance . Clearly, all codewords are distinct. If we delete the first letters of each codeword, then all resulting codewords must still be pairwise different, since all original codewords in have Hamming distance at least from each other. Thus the size of the code remains unchanged.

The newly obtained codewords each have length

and thus there can be at most

of them. Hence the original code shares the same bound on its size :

Read more about this topic:  Singleton Bound

Famous quotes containing the word proof:

    Right and proof are two crutches for everything bent and crooked that limps along.
    Franz Grillparzer (1791–1872)

    Sculpture and painting are very justly called liberal arts; a lively and strong imagination, together with a just observation, being absolutely necessary to excel in either; which, in my opinion, is by no means the case of music, though called a liberal art, and now in Italy placed even above the other two—a proof of the decline of that country.
    Philip Dormer Stanhope, 4th Earl Chesterfield (1694–1773)

    The moment a man begins to talk about technique that’s proof that he is fresh out of ideas.
    Raymond Chandler (1888–1959)