Sphere-packing bound

From Wikipedia, the free encyclopedia

It has been suggested that Hamming bound be merged into this article or section. (Discuss)

In mathematics and computer science, the sphere-packing bound (also known as the Hamming bound, or the volume bound) is a limitation on the efficiency with which any error correcting code can utilize the n-dimensional space in which its code words are embedded.

1 Overview of error correcting codes
2 Perfect and imperfect codes
3 References
4 External links

[edit] Overview of 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.

[edit] Perfect and imperfect codes

Error correcting codes consist of code words together with their disjoint decoding regions. Larger decoding regions imply that more errors can be tolerated, while having more code words implies that a greater number of distinct messages can be reliably communicated. There is clearly a tension between these two desirable properties, and perhaps the simplest such tension is that the total volume of the decoding regions cannot exceed the total volume of the space. This is the limitation imposed by the sphere-packing bound:

$q^{n}\geq q^{m}\left[{\textstyle\binom{n}{0}} + {\textstyle\binom{n}{1}} (q-1) + {\textstyle\binom{n}{2}}(q-1)^{2} + \dots + {\textstyle\binom{n}{t}} (q-1)^t \,\right].$

Here qⁿ is the total number of points in the n-dimensional code word space, M is the total number of valid code words, t is the number of errors that can be detected and corrected by the code, and the expression in brackets counts all the possible errors that lie (in the Hamming sense) within radius t of an individual code word.

$q^{n} = q^{m}\left[{\textstyle\binom{n}{0}} + {\textstyle\binom{n}{1}} (q-1) + {\textstyle\binom{n}{2}}(q-1)^{2} + \dots + {\textstyle\binom{n}{t}} (q-1)^t \,\right]$

we call the code a perfect code because the code words and their disjoint decoding regions cover the entire n-dimensional space. In practice, most error correcting codes are imperfect; they leave "holes" between the disjoint decoding regions.