Hamming bound

From Wikipedia, the free encyclopedia

Merge arrow
 It has been suggested that this article or section be merged into Sphere-packing bound. (Discuss)

In coding theory, the Hamming bound is a limit on the parameters of an arbitrary block code. It is a re-statement of the sphere-packing bound from an information-theoretical point of view. A code which attains the Hamming bound is said to be a perfect code.

Contents

[edit] Statement of the Bound

Let \ A_q(n,d) denote the maximum possible size of a q-ary block code \ C of length n and minimum Hamming distance d (a q-ary block code of length n is a subset of the strings of \mathcal{A}_q^n\text{,} where the alphabet set \mathcal{A}_q has q elements).

Then:

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

where

t=\left\lfloor\frac{d-1}{2}\right\rfloor

[edit] Proof

By definition of d, if at most t=\left\lfloor\frac{d-1}{2}\right\rfloor errors are made during transmission of a codeword then minimum distance decoding will decode it correctly (ie it decodes the received codeword as the codeword that was sent). Thus the code is said to be capable of correcting t errors.

For a given codeword c \in C, consider the ball of radius t around c. Each such ball is non-intersecting by the t-error correcting property, and each ball contains

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

codewords since we may allow (or choose) up to t of the n components of a codeword to deviate (from the value of the corresponding component of the ball's centre) to one of (q − 1) possible other values (recall: the code is q-ary: it takes values in \mathcal{A}_q^n).

Let M be the total number of codewords in C. Taking the union of the balls over all codewords we observe that the resulting set of codewords is contained in \mathcal{A}_q^n. Then since each ball is non-intersecting we may sum the number of elements in each to deduce:

\begin{matrix} \\ M \times \sum_{k=0}^t \binom{n}{k}(q-1)^k \leq |\mathcal{A}_q^n| = q^n \\ \end{matrix}

Whence:

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

[edit] Perfect Codes

Codes that attain the Hamming bound and are called perfect codes. Examples include binary repetition codes of odd length, codes that have only one codeword, and codes that use the whole of (Fq)n. These are often called trivial perfect codes.

In 1973 it was proved that any non-trivial perfect code has the parameters of a Hamming code or a Golay code (Raymond, 1988:102).

[edit] See also

[edit] References

  • Hill, Raymond. (1988). A First Course In Coding Theory, New York: Oxford University Press.