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 chief contribution of Protestantism to human thought is its massive proof that God is a bore.”
    —H.L. (Henry Lewis)

    “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)

    “To cease to admire is a proof of deterioration.”
    —Charles Horton Cooley (1864–1929)