Toluene (data page)

2013-03-21T09:51:34Z

145.93.217.108: /* MSDS sheets */

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 [[Sphere packing|packing balls]] in the [[Hamming metric]] into the [[Space (mathematics)|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 word]]s 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 codeword by an encoding algorithm, transmitted over a noisy [[channel (communications)|channel]], and finally decoded by the receiver. The decoding process interprets a garbled codeword, referred to as simply a ''word'', as the valid codeword "nearest" the ''n''-letter received string.

Mathematically, there are exactly ''q''''m'' possible messages of length ''m'', and each message can be regarded as a [[coordinate vector|vector]] of length ''m''. The encoding scheme converts an ''m''-dimensional vector into an ''n''-dimensional vector. Exactly ''q''''m'' valid codewords are possible, but any one of ''q''''n'' garbled codewords (words) can be received, because the noisy channel might distort one or more of the ''n'' letters while the codeword is being transmitted.

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

Then, the Hamming bound is:

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

where

:<math>t=\left\lfloor\frac{d-1}{2}\right\rfloor.</math>

==Proof==
By definition of <math>d</math>, if at most <math> t = \left\lfloor\frac{1}{2}(d-1)\right\rfloor</math> 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 <math>t</math> errors.

For a given codeword <math>c \in C</math>, consider the [[ball (mathematics)|ball]] of radius <math>t</math> around <math>c</math>. 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 [[binomial coefficients|choose]]) up to <math>t</math> of the <math>n</math> components of a word to deviate (from the value of the corresponding component of the ball's [[ball (mathematics)|centre]], which is a codeword) to one of <math>(q-1)</math> possible other values (recall, the code is q-ary: it takes values in <math>\mathcal{A}_q^n</math>), we can define:

:<math>m =
\begin{matrix}
\sum_{k=0}^t \binom{n}{k}(q-1)^k
\end{matrix}</math>

Since <math>A_q (n,d)</math> is the maximum total number of codewords in <math>C</math>, and thus the greatest number of balls, and no two balls have a word in common, by taking the [[union (set theory)|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 <math>\mathcal{A}_q^n</math> (where <math>|\mathcal{A}_q^n| = q^n</math> words) and deduce:

:<math> 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.</math>

Whence:

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

==Covering radius and packing radius==
:{{main|Covering radius}}
For an <math>A_q(n,d)</math> code ''C'' (a subset of <math>\mathcal{A}_q^n</math>), the ''covering radius'' of ''C'' is the smallest value of ''r'' such that every element of <math>\mathcal{A}_q^n</math> is contained in at least one ball of radius ''r'' centered at each codeword of ''C''. The ''packing radius'' of ''C'' is the largest value of ''s'' such that the set of balls of radius ''s'' centered at each codeword of ''C'' are mutually disjoint.

From the proof of the Hamming bound, it can be seen that for <math> t\,=\,\left\lfloor\frac{1}{2}(d-1)\right\rfloor</math>, we have:
:: ''s'' ≤ ''t'' and ''t'' ≤ ''r''.
Therefore, ''s'' ≤ ''r'' and if equality holds then ''s'' = ''r'' = ''t''. The case of equality means that the Hamming bound is attained.

== Perfect codes ==
Codes that attain the Hamming bound are called '''perfect codes'''. Examples include codes that have only one codeword, and codes that are the whole of <math>\scriptstyle\mathcal{A}_q^n</math>. Another example is given by the ''repeat codes'', where each symbol of the message is repeated an odd fixed number of times to obtain a codeword where ''q'' = 2. All of these examples are often called the ''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]].<ref>Hill (1988) p. 102</ref>

A perfect code may be interpreted as one in which the balls of Hamming radius ''t'' centered on codewords exactly fill out the space (''t'' is the covering radius = packing radius). A '''quasi-perfect code''' is one in which the balls of Hamming radius ''t'' centered on codewords are disjoint and the balls of radius ''t''+1 cover the space, possibly with some overlaps.<ref>McWilliams and Sloane, p. 19</ref> Another way to say this is that a code is ''quasi-perfect'' if its covering radius is one greater than its packing radius.<ref>{{harvnb|Roman|1992|loc=pg. 140}}</ref>

==See also==

*[[Griesmer bound]]
*[[Singleton bound]]
*[[Gilbert-Varshamov bound]]
*[[Plotkin bound]]
*[[Johnson bound]]
*[[Rate-distortion theory]]

==Notes==
{{reflist}}

== References ==
* {{cite book | author=Raymond Hill | title=A First Course In Coding Theory | publisher=[[Oxford University Press]] | year=1988 | isbn=0-19-853803-0 }}
* {{cite book | author=F.J. MacWilliams | authorlink=Jessie MacWilliams | coauthors=[[Neil Sloane|N.J.A. Sloane]] | title=The Theory of Error-Correcting Codes | publisher=North-Holland | year=1977 | isbn=0-444-85193-3 }}
* {{cite book | author=Vera Pless | authorlink=Vera Pless | title=Introduction to the Theory of Error-Correcting Codes | publisher=John Wiley & Sons | year=1982 | isbn=0-471-08684-3 }}
* {{citation|last=Roman|first=Steven|title=Coding and Information Theory|publisher=Springer-Verlag|place=New York|series=[[Graduate Texts in Mathematics|GTM]]|volume=134|year=1992|isbn=0-387-97812-7}}
* {{cite book | author=J.H. van Lint | authorlink=Jack van Lint | title=Introduction to Coding Theory | edition=2nd | publisher=Springer-Verlag | series=[[Graduate Texts in Mathematics|GTM]] | volume=86 | year=1992 | isbn=3-540-54894-7 }}
* {{cite journal | author=J.H. van Lint | authorlink=Jack van Lint | title=A survey of perfect codes | journal=[[Rocky Mountain Journal of Mathematics]] | volume=5 | year=1975 | pages=199–224 | doi=10.1216/RMJ-1975-5-2-199 | issue=2 }}

{{Packing problem}}

[[Category:Coding theory]]

formulasearchengine - User contributions [en]

Toluene (data page)