Hamming bound: Article and Information about Hamming bound

Hamming bound - Fuhz Articles
Visually Impaired Edition.

Hamming bound article, this Fuhz page will hopefully provide the answers to the who, what where and why on the Hamming bound topic.
At the bottom of the page we often provide links to external documents relating to Hamming bound which may also help your research. Every effort is made to ensure the content on this page is as accurate and error free as possible, however whenever researching information that requires the utmost accuracy such as a term paper it is always best to cross reference facts with numerous sources.

In mathematics and computer science, in the field of coding theory, the Hamming bound is a limit on the parameters of an arbitrary block code: it is also known as the sphere-packing bound or the volume bound from an interpretation in terms of packing balls in the Hamming metric into the space of all possible words. It gives an important limitation on the efficiency with which any error correcting code can utilize the space in which its code words are embedded. A code which attains the Hamming bound is said to be a perfect code.

1 Background on error correcting codes
2 Statement of the bound
3 Proof
4 Perfect codes
5 See also
6 Notes
7 References
8 External links

Background on error correcting codes

An original message and an encoded version are both composed in an alphabet of q letters. Each code word contains n letters. The original message (of length m) is shorter than n letters. The message is converted into an n-letter code word by an encoding algorithm, transmitted over a noisy channel, and finally decoded by the receiver. The decoding process interprets a garbled code word as the valid code word "nearest" the n-letter received string.

Mathematically, there are exactly q^m possible messages of length m, and each such message can be regarded as a vector of length m. The encoding scheme converts an m-dimensional vector into an n-dimensional vector. Exactly q^m valid code words are possible, but any one of qⁿ garbled code words can be received, because the noisy channel might distort one or more of the n letters while the code word is being transmitted.

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.$

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 (i.e. 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 (Hamming sphere) is non-intersecting by the $t$ -error correcting property, and each ball contains (in other words the volume of the ball)

$\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$ = q^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} \\ |\mathcal{A}_q^n| \times \sum_{k=0}^t \binom{n}{k}(q-1)^k \leq M = 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}$

Perfect codes

Codes that attain the Hamming bound 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 $(F q) n$ . These are often called trivial perfect codes.

In 1973 it was proved that any non-trivial perfect code over a prime-power alphabet has the parameters of a Hamming code or a Golay code.¹

A perfect code may be interpreted as one in which the balls of Hamming radius t centred on codewords exactly fill out the space. A quasi-perfect code is one in which the balls of Hamming radius t centred on codewords are disjoint and the balls of radius t+1 cover the space, possibly with some overlaps.²

Notes

^ Hill (1988) p.102
^ McWilliams and Sloane, p.19

References

Raymond Hill (1988). A First Course In Coding Theory. Oxford University Press. ISBN 0-19-853803-0.
F.J. MacWilliams; N.J.A. Sloane (1977). The Theory of Error-Correcting Codes. North-Holland. ISBN 0-444-85193-3.
Vera Pless (1982). Introduction to the Theory of Error-Correcting Codes. John Wiley & Sons. ISBN 0-471-08684-3.
J.H. van Lint (1992). Introduction to Coding Theory. GTM. 86 (2nd ed.). Springer-Verlag. ISBN 3-540-54894-7.
J.H. van Lint (1975). "A survey of perfect codes". Rocky Mountain Math. J. 5: 199–224.

External links

A wiki dedicated to coding theory

Return to Fuhz Home - This article covering Hamming bound is enhanced for the visually impaired.

Article from Wikipedia. All text is available under the terms of the GNU Free Documentation License - Our Privacy Policy - Thanks Auto Blog Commenter

Contents