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:

    “The insatiable thirst for everything which lies beyond, and which life reveals, is the most living proof of our immortality.”
    —Charles Baudelaire (1821–1867)

    “A short letter to a distant friend is, in my opinion, an insult like that of a slight bow or cursory salutation—a proof of unwillingness to do much, even where there is a necessity of doing something.”
    —Samuel Johnson (1709–1784)

    “It comes to pass oft that a terrible oath, with a swaggering accent sharply twanged off, gives manhood more approbation than ever proof itself would have earned him.”
    —William Shakespeare (1564–1616)