ハミング限界

q進数の符号 ${\displaystyle C}$ が長さ ${\displaystyle n}$ で最小ハミング距離 ${\displaystyle d}$ であるとき、その可能な最大サイズ（符号語の総数）を ${\displaystyle A_{q}(n,d)}$ とする。なお、q進数の符号は、${\displaystyle q}$ 個の要素の体 ${\displaystyle \mathbb {F} _{q}^{n}}$ 上の線型符号である。

すると、次が成り立つ。

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

ここで、

${\displaystyle t=\lfloor {\frac {d-1}{2}}\rfloor }$

${\displaystyle d}$ の定義から、符号語の転送において最大で ${\displaystyle t=\lfloor {\tfrac {d-1}{2}}\rfloor }$ の誤りが発生したとすると、最小距離復号によって正しく復号できる（すなわち、符号化された符号語を正しく復号できる）。つまり、この符号は ${\displaystyle t}$ 個の誤りを訂正可能である。

${\displaystyle c\in C}$ であるようなある符号語について、${\displaystyle c}$ を中心とする半径 ${\displaystyle t}$ の球を考える。このような球の範囲内なら誤り訂正が正しく行われる。符号語を構成する ${\displaystyle n}$ 個の要素のうち ${\displaystyle t}$ 個まで誤りがあっても正しく復号できるため、それぞれの球には以下の符号語が含まれる（つまり、中心にある真の符号語の一部を変更した符号語群の数）。符号語の一桁は q進数であるから、とりうる値は ${\displaystyle (q-1)}$ 種類になる。

${\displaystyle \sum _{k=0}^{t}{\binom {n}{k}}(q-1)^{k}}$

${\displaystyle C}$ に存在する符号語の総数を ${\displaystyle M}$ とする。全ての符号語から球の和集合をとると、結果として得られる符号語の総数は ${\displaystyle \mathbb {F} _{q}^{n}}$ 以内となる。それぞれの球は重ならないので、それぞれの要素数の総和をとると、次が成り立つといえる。

${\displaystyle M\times \sum _{k=0}^{t}{\binom {n}{k}}(q-1)^{k}\leq \vert \mathbb {F} _{q}^{n}\vert =q^{n}}$

従って、次が導かれる。

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

• シングルトン限界
• ギルバート-バルシャモフ限界
• プロトキン限界
• ジョンソン限界