Hamming Bound - Proof

Proof

By definition of, if at most errors are made during transmission of a codeword then minimum distance decoding will decode it correctly (i.e., it decodes the received word as the codeword that was sent). Thus the code is said to be capable of correcting errors.

For a given codeword, consider the ball of radius around . Every pair of balls (Hamming spheres) are non-intersecting by the t-error-correcting property, and each ball contains (in other words, the volume of the ball) m words. Since we may allow (or choose) up to of the components of a word to deviate (from the value of the corresponding component of the ball's centre, which is a codeword) to one of possible other values (recall, the code is q-ary: it takes values in ), we can define:

m = \begin{matrix} \sum_{k=0}^t \binom{n}{k}(q-1)^k \end{matrix}

Since is the maximum total number of codewords in, and thus the greatest number of balls, and no two balls have a word in common, by taking the union of the words in balls centered at codewords we observe that the resulting set of words, each counted precisely once, is a subset of (where words) and deduce:

A_q(n,d) \times m = A_q(n,d) \times \begin{matrix} \sum_{k=0}^t \binom{n}{k}(q-1)^k \end{matrix} \leq q^n.

Whence:

A_q(n,d) \leq \frac{q^n}{ \begin{matrix} \sum_{k=0}^t \binom{n}{k}(q-1)^k \end{matrix}}.

Read more about this topic:  Hamming Bound

Famous quotes containing the word proof:

    “If any doubt has arisen as to me, my country [Virginia] will have my political creed in the form of a “Declaration &c.” which I was lately directed to draw. This will give decisive proof that my own sentiment concurred with the vote they instructed us to give.”
    —Thomas Jefferson (1743–1826)

    “Ah! I have penetrated to those meadows on the morning of many a first spring day, jumping from hummock to hummock, from willow root to willow root, when the wild river valley and the woods were bathed in so pure and bright a light as would have waked the dead, if they had been slumbering in their graves, as some suppose. There needs no stronger proof of immortality. All things must live in such a light. O Death, where was thy sting? O Grave, where was thy victory, then?”
    —Henry David Thoreau (1817–1862)

    “He who has never failed somewhere, that man can not be great. Failure is the true test of greatness. And if it be said, that continual success is a proof that a man wisely knows his powers,—it is only to be added, that, in that case, he knows them to be small.”
    —Herman Melville (1819–1891)