Hamming bound

<h2 id="background-on-error-correcting-codes">Background on error-correcting codes</h2>
An original message and an encoded version are both composed in an alphabet of q letters. Each <a href="/facts/Code_word_(communication)/sASREopJ">code word</a> 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 <a href="/facts/Communication_channel/MtlxEShV">channel</a>, 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 qm possible messages of length m, and each message can be regarded as a <a href="/facts/Coordinate_vector/TEcLqS40">vector</a> of length m. The encoding scheme converts an m-dimensional vector into an n-dimensional vector. Exactly qm valid codewords are possible, but any one of qn words can be received because the noisy channel might distort one or more of the n letters when a codeword is transmitted.

<h2 id="statement-of-the-bound">Statement of the bound</h2>
<h3>Preliminary definitions</h3>
An alphabet set 
 
 
 
 
 
 
 A
 
 
 
 q
 
 
 
 
 {\displaystyle {\mathcal {A}}_{q}}
 
 is a set of symbols with 
 
 
 
 q
 
 
 {\displaystyle q}
 
 elements. The set of strings of length 
 
 
 
 n
 
 
 {\displaystyle n}
 
 on the alphabet set 
 
 
 
 
 
 
 A
 
 
 
 q
 
 
 
 
 {\displaystyle {\mathcal {A}}_{q}}
 
 are denoted 
 
 
 
 
 
 
 A
 
 
 
 q
 
 
 n
 
 
 
 
 {\displaystyle {\mathcal {A}}_{q}^{n}}
 
. (There are 
 
 
 
 
 q
 
 n
 
 
 
 
 {\displaystyle q^{n}}
 
 distinct strings in this set of strings.) A 
 
 
 
 q
 
 
 {\displaystyle q}
 
-ary block code of length 
 
 
 
 n
 
 
 {\displaystyle n}
 
 is a subset of the strings of 
 
 
 
 
 
 
 A
 
 
 
 q
 
 
 n
 
 
 
 
 {\displaystyle {\mathcal {A}}_{q}^{n}}
 
, where the alphabet set 
 
 
 
 
 
 
 A
 
 
 
 q
 
 
 
 
 {\displaystyle {\mathcal {A}}_{q}}
 
 is any alphabet set having 
 
 
 
 q
 
 
 {\displaystyle q}
 
 elements. (The choice of alphabet set 
 
 
 
 
 
 
 A
 
 
 
 q
 
 
 
 
 {\displaystyle {\mathcal {A}}_{q}}
 
 makes no difference to the result, provided the alphabet is of size 
 
 
 
 q
 
 
 {\displaystyle q}
 
.)

<h3>Defining the bound</h3>
Let 
 
 
 
  
 
 A
 
 q
 
 
 (
 n
 ,
 d
 )
 
 
 {\displaystyle \ A_{q}(n,d)}
 
 denote the maximum possible size of a 
 
 
 
 q
 
 
 {\displaystyle q}
 
-ary block code 
 
 
 
  
 C
 
 
 {\displaystyle \ C}
 
 of length 
 
 
 
 n
 
 
 {\displaystyle n}
 
 and minimum <a href="/facts/Hamming_distance/MgdtbYPo">Hamming distance</a> 
 
 
 
 d
 
 
 {\displaystyle d}
 
 between elements of the block code (necessarily positive for 
 
 
 
 
 q
 
 n
 
 
 >
 1
 
 
 {\displaystyle q^{n}>1}
 
).
Then, the Hamming bound is:

A
          
            q
          
        
        (
        n
        ,
        d
        )
        ≤
        
          
            
              q
              
                n
              
            
            
              
                ∑
                
                  k
                  =
                  0
                
                
                  t
                
              
              
                
                  
                    (
                  
                  
                    n
                    k
                  
                  
                    )
                  
                
              
              (
              q
              −
              1
              
                )
                
                  k
                
              
            
          
        
      
    
    {\displaystyle \ A_{q}(n,d)\leq {\frac {q^{n}}{\sum _{k=0}^{t}{\binom {n}{k}}(q-1)^{k}}}}

where

t
        =
        
          ⌊
          
            
              
                d
                −
                1
              
              2
            
          
          ⌋
        
        .
      
    
    {\displaystyle t=\left\lfloor {\frac {d-1}{2}}\right\rfloor .}

<h2 id="proof">Proof</h2>
It follows from the definition of 
 
 
 
 d
 
 
 {\displaystyle d}
 
 that if at most

t
        =
        
          ⌊
          
            
              
                1
                2
              
            
            (
            d
            −
            1
            )
          
          ⌋
        
      
    
    {\displaystyle t=\left\lfloor {\frac {1}{2}}(d-1)\right\rfloor }

errors are made during transmission of a <a href="/facts/Code_word_(communication)/sASREopJ">codeword</a> then <a href="/facts/Minimum_distance_decoding/A0x9Dpgq">minimum distance decoding</a> 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 
 
 
 
 t
 
 
 {\displaystyle t}
 
 errors.
For each codeword 
 
 
 
 c
 ∈
 C
 
 
 {\displaystyle c\in C}
 
, consider a <a href="/facts/Ball_(mathematics)/f9vpMVMp">ball</a> of fixed radius 
 
 
 
 t
 
 
 {\displaystyle t}
 
 around 
 
 
 
 c
 
 
 {\displaystyle c}
 
. Every pair of these balls (<a href="/facts/Hamming_ball/XXzf4UYm">Hamming balls</a>) are non-intersecting by the 
 
 
 
 t
 
 
 {\displaystyle t}
 
-error-correcting property. Let 
 
 
 
 m
 
 
 {\displaystyle m}
 
 be the number of words in each ball (in other words, the volume of the ball). A word that is in such a ball can deviate in at most 
 
 
 
 t
 
 
 {\displaystyle t}
 
 components from those of the ball's <a href="/facts/Ball_(mathematics)/f9vpMVMp">centre</a>, which is a codeword. The number of such words is then obtained by <a href="/facts/Binomial_coefficients/Tsx7eY5h">choosing</a> up to 
 
 
 
 t
 
 
 {\displaystyle t}
 
 of the 
 
 
 
 n
 
 
 {\displaystyle n}
 
 components of a codeword to deviate to one of 
 
 
 
 (
 q
 −
 1
 )
 
 
 {\displaystyle (q-1)}
 
 possible other values (recall, the code is 
 
 
 
 q
 
 
 {\displaystyle q}
 
-ary: it takes values in 
 
 
 
 
 
 
 A
 
 
 
 q
 
 
 n
 
 
 
 
 {\displaystyle {\mathcal {A}}_{q}^{n}}
 
). Thus,

m
        =
        
          
            
              
                
                  ∑
                  
                    k
                    =
                    0
                  
                  
                    t
                  
                
                
                  
                    
                      (
                    
                    
                      n
                      k
                    
                    
                      )
                    
                  
                
                (
                q
                −
                1
                
                  )
                  
                    k
                  
                
              
            
          
        
        .
      
    
    {\displaystyle m={\begin{matrix}\sum _{k=0}^{t}{\binom {n}{k}}(q-1)^{k}\end{matrix}}.}

A
 
 q
 
 
 (
 n
 ,
 d
 )
 
 
 {\displaystyle A_{q}(n,d)}
 
 is the (maximum) total number of codewords in 
 
 
 
 C
 
 
 {\displaystyle C}
 
, and so, by the definition of 
 
 
 
 t
 
 
 {\displaystyle t}
 
, the greatest number of balls with no two balls having a word in common. Taking the <a href="/facts/Union_(set_theory)/KVVXKfWl">union</a> of the words in these balls centered at codewords, results in a set of words, each counted precisely once, that is a subset of 
 
 
 
 
 
 
 A
 
 
 
 q
 
 
 n
 
 
 
 
 {\displaystyle {\mathcal {A}}_{q}^{n}}
 
 (where 
 
 
 
 
 |
 
 
 
 
 A
 
 
 
 q
 
 
 n
 
 
 
 |
 
 =
 
 q
 
 n
 
 
 
 
 {\displaystyle |{\mathcal {A}}_{q}^{n}|=q^{n}}
 
 words) and so:

A
          
            q
          
        
        (
        n
        ,
        d
        )
        ×
        m
        =
        
          A
          
            q
          
        
        (
        n
        ,
        d
        )
        ×
        
          
            
              
                
                  ∑
                  
                    k
                    =
                    0
                  
                  
                    t
                  
                
                
                  
                    
                      (
                    
                    
                      n
                      k
                    
                    
                      )
                    
                  
                
                (
                q
                −
                1
                
                  )
                  
                    k
                  
                
              
            
          
        
        ≤
        
          q
          
            n
          
        
        .
      
    
    {\displaystyle 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}.}

Whence:

A
          
            q
          
        
        (
        n
        ,
        d
        )
        ≤
        
          
            
              q
              
                n
              
            
            
              
                
                  
                    ∑
                    
                      k
                      =
                      0
                    
                    
                      t
                    
                  
                  
                    
                      
                        (
                      
                      
                        n
                        k
                      
                      
                        )
                      
                    
                  
                  (
                  q
                  −
                  1
                  
                    )
                    
                      k
                    
                  
                
              
            
          
        
        .
      
    
    {\displaystyle A_{q}(n,d)\leq {\frac {q^{n}}{\begin{matrix}\sum _{k=0}^{t}{\binom {n}{k}}(q-1)^{k}\end{matrix}}}.}

<h2 id="covering-radius-and-packing-radius">Covering radius and packing radius</h2>
Main article: <a href="/facts/Delone_set/VKGgETLd">Delone set</a>
For an 
 
 
 
 
 A
 
 q
 
 
 (
 n
 ,
 d
 )
 
 
 {\displaystyle A_{q}(n,d)}
 
 code C (a subset of 
 
 
 
 
 
 
 A
 
 
 
 q
 
 
 n
 
 
 
 
 {\displaystyle {\mathcal {A}}_{q}^{n}}
 
), the covering radius of C is the smallest value of r such that every element of 
 
 
 
 
 
 
 A
 
 
 
 q
 
 
 n
 
 
 
 
 {\displaystyle {\mathcal {A}}_{q}^{n}}
 
 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 <a href="/facts/Disjoint_sets/nLr8XRVd">disjoint</a>.
From the proof of the Hamming bound, it can be seen that for 
 
 
 
 t
 
 =
 
 
 ⌊
 
 
 
 1
 2
 
 
 (
 d
 −
 1
 )
 
 ⌋
 
 
 
 {\displaystyle t\,=\,\left\lfloor {\frac {1}{2}}(d-1)\right\rfloor }
 
, 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.

<h2 id="perfect-codes">Perfect codes</h2>
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 
 
 
 
 
 
 
 
 A
 
 
 
 q
 
 
 n
 
 
 
 
 
 {\displaystyle \scriptstyle {\mathcal {A}}_{q}^{n}}
 
. 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, Tietäväinen proved<a class="footnote-ref" id="fnref:1" href="#fn:1">1</a> that any non-trivial perfect code over a prime-power alphabet has the parameters of a <a href="/facts/Hamming_code/zsI8cTRC">Hamming code</a> or a <a href="/facts/Golay_code_(disambiguation)/DFznCkLF">Golay code</a>.
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.<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a> Another way to say this is that a code is quasi-perfect if its covering radius is one greater than its packing radius.<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a>

<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Gilbert-Varshamov_bound/VSfMngso">Gilbert-Varshamov bound</a></li>
<li><a href="/facts/Griesmer_bound/wNjEVItl">Griesmer bound</a></li>
<li><a href="/facts/Johnson_bound/bCn73V5H">Johnson bound</a></li>
<li><a href="/facts/Plotkin_bound/3BTlazT1">Plotkin bound</a></li>
<li><a href="/facts/Rate-distortion_theory/a5P5krWF">Rate-distortion theory</a></li>
<li><a href="/facts/Singleton_bound/FEeBetsk">Singleton bound</a></li></ul>
<h2 id="notes">Notes</h2>

<ul><li>P. J. Cameron; J. A. Thas; S. E. Payne (1976). "Polarities of generalized hexagons and perfect codes". Geometriae Dedicata. 5 (4): 525–528. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2FBF00150782">10.1007/BF00150782</a>. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:121071671">121071671</a>.</li>
<li>Hill, R. (1988). <a href="https://archive.org/details/firstcourseincod0000hill">A First Course In Coding Theory</a>. <a href="/facts/Oxford_University_Press/CYyTzzWG">Oxford University Press</a>. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-19-853803-0.</li>
<li><a href="/facts/Jessie_MacWilliams/pGWBIGmI">MacWilliams, F. J.</a>; <a href="/facts/Neil_Sloane/kLWw29Me">N.J.A. Sloane</a> (1977). <a href="https://archive.org/details/theoryoferrorcor0000macw">The Theory of Error-Correcting Codes</a>. North-Holland. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-444-85193-3.</li>
<li><a href="/facts/Vera_Pless/na9l860I">Pless, V.</a> (1982). <a href="/facts/Introduction_to_the_Theory_of_Error-Correcting_Codes/VKWbax0T">Introduction to the Theory of Error-Correcting Codes</a>. John Wiley & Sons. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-471-08684-3.</li>
<li>Roman, S. (1992), Coding and Information Theory, <a href="/facts/Graduate_Texts_in_Mathematics/VTIfY29j">GTM</a>, vol. 134, New York: Springer-Verlag, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-387-97812-7</li>
<li>Tietäväinen, A. (1973). <a href="https://epubs.siam.org/doi/pdf/10.1137/0124010">"On the nonexistence of perfect codes over finite fields"</a>. SIAM J. Appl. Math. 24: 88–96. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1137%2F0124010">10.1137/0124010</a>.</li>
<li><a href="/facts/Jack_van_Lint/JMDwvfkS">van Lint, J. H.</a> (1992). <a href="https://archive.org/details/introductiontoco0000lint">Introduction to Coding Theory</a>. <a href="/facts/Graduate_Texts_in_Mathematics/VTIfY29j">GTM</a>. Vol. 86 (2nd ed.). Springer-Verlag. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 3-540-54894-7.</li>
<li><a href="/facts/Jack_van_Lint/JMDwvfkS">van Lint, J. H.</a> (1975). <a href="https://doi.org/10.1216%2FRMJ-1975-5-2-199">"A survey of perfect codes"</a>. <a href="/facts/Rocky_Mountain_Journal_of_Mathematics/nlSmyEuF">Rocky Mountain Journal of Mathematics</a>. 5 (2): 199–224. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1216%2FRMJ-1975-5-2-199">10.1216/RMJ-1975-5-2-199</a>.</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Tietäväinen 1973. - Tietäväinen, A. (1973). "On the nonexistence of perfect codes over finite fields". SIAM J. Appl. Math. 24: 88–96. doi:10.1137/0124010. <a href="https://epubs.siam.org/doi/pdf/10.1137/0124010" target="_blank">https://epubs.siam.org/doi/pdf/10.1137/0124010</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">McWilliams and Sloane, p. 19 <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Roman 1992, p. 140 - Roman, S. (1992), Coding and Information Theory, GTM, vol. 134, New York: Springer-Verlag, ISBN 0-387-97812-7 <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
</ol>

Hamming bound open-in-new

Hamming bound