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 proof of a poet is that his country absorbs him as affectionately as he has absorbed it.”
    —Walt Whitman (1819–1892)

    “a meek humble Man of modest sense,
    Who preaching peace does practice continence;
    Whose pious life’s a proof he does believe,
    Mysterious truths, which no Man can conceive.”
    —John Wilmot, 2d Earl Of Rochester (1647–1680)

    “In the reproof of chance
    Lies the true proof of men.”
    —William Shakespeare (1564–1616)