Hamming bound

Hamming bound

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.

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""n" 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 ext{,} where the alphabet set mathcal{A}_q has q elements).

Then:

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

where

:t=leftlfloorfrac{d-1}{2} ight floor.

Proof

By definition of d, if at most t=leftlfloorfrac{d-1}{2} ight floor 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

:egin{matrix}\sum_{k=0}^t inom{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:

:egin{matrix}\M imes sum_{k=0}^t inom{n}{k}(q-1)^k leq |mathcal{A}_q^n| = q^n.\end{matrix}

Whence:

:egin{matrix}\A_q(n,d) leq frac{q^n}{sum_{k=0}^t inom{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. [Hill (1988) p.102]

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-pefect 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. [McWilliams and Sloane, p.19]

ee also

*Singleton bound
*Gilbert-Varshamov bound
*Plotkin bound
*Johnson bound

Notes

References

*
*
*
*
*

External links

* [http://geilenkotten.homeunix.org/wikicoding/index.php/Main_Page A wiki dedicated to coding theory]


Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Look at other dictionaries:

  • Gilbert-Varshamov bound — The Gilbert Varshamov bound is a bound on the parameters of a (not necessarily linear) code. It is occasionally known as the Gilbert Shannon Varshamov bound (or the GSV bound ), but the Gilbert Varshamov bound is by far the most popular… …   Wikipedia

  • Singleton bound — In coding theory, the Singleton bound, named after Richard Collom Singleton, is a relatively crude bound on the size of a block code C with block length n, size r and minimum distance d. Contents 1 Statement of the Bound 2 Proof …   Wikipedia

  • Plotkin bound — In the mathematics of coding theory, the Plotkin bound is a bound on the size of binary codes of length n and minimum distance d. Statement of the Bound Let C be a binary code of length n, i.e. a subset of mathbb{F} 2^n. Let d be the minimum… …   Wikipedia

  • Richard Hamming — Infobox Scientist name = Richard Wesley Hamming image width = caption = birth date = birth date|1915|2|11|mf=y birth place = Chicago, Illinois death date = death date and age|1998|1|7|1915|2|11 death place = Monterey, California residence =… …   Wikipedia

  • Johnson bound — The Johnson bound is a bound on the size of error correcting codes.Let C be a q ary code of length n, i.e. a subset of mathbb{F} q^n. Let d be the minimum distance of C, i.e. :d = min {x,y in C, x eq y} d(x,y) where d(x,y) is the Hamming distance …   Wikipedia

  • Distributed source coding — (DSC) is an important problem in information theory and communication. DSC problems regard the compression of multiple correlated information sources that do not communicate with each other.[1] By modeling the correlation between multiple sources …   Wikipedia

  • List of algebraic coding theory topics — This is a list of algebraic coding theory topics. ARQ[disambiguation needed  ] Adler 32 BCH code BCJR algorithm Berger code Berlekamp Massey algo …   Wikipedia

  • List of mathematics articles (H) — NOTOC H H cobordism H derivative H index H infinity methods in control theory H relation H space H theorem H tree Haag s theorem Haagerup property Haaland equation Haar measure Haar wavelet Haboush s theorem Hackenbush Hadamard code Hadamard… …   Wikipedia

  • Mutually unbiased bases — In quantum information theory, mutually unbiased bases in Hilbert space Cd are two orthonormal bases and such that the square of the magnitude of the inner product between any basis states and equals the inverse of the dimension d …   Wikipedia

  • Quantum error correction — is used in quantum computing to protect quantum information from errors due to decoherence and other quantum noise. Quantum error correction is essential if one is to achieve fault tolerant quantum computation that can deal not only with noise on …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”