ハミング限界のソースを表示

'''ハミング限界'''（ハミングげんかい、{{lang-en-short|Hamming bound}}）は、[[符号]]（[[線型符号]]とは限らない）のパラメータの限界値を指す。[[球充填]]の限界を[[情報理論]]の観点で言い直したものと言える。ハミング限界に従った符号を「完全符号; perfect code」と呼ぶ。

== 定義 ==
q進数の符号 <math>C</math> が長さ <math>n</math> で最小[[ハミング距離]] <math>d</math> であるとき、その可能な最大サイズ（符号語の総数）を <math>A_q(n,d)</math> とする。なお、q進数の符号は、<math>q</math> 個の要素の[[可換体|体]] <math>\mathbb{F}_q^n</math> 上の線型符号である。

すると、次が成り立つ。

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

ここで、

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

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

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

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

<math>C</math> に存在する符号語の総数を <math>M</math> とする。全ての符号語から球の[[合併 (集合論)|和集合]]をとると、結果として得られる符号語の総数は <math>\mathbb{F}_q^n</math> 以内となる。それぞれの球は重ならないので、それぞれの要素数の総和をとると、次が成り立つといえる。

:<math>
M \times \sum_{k=0}^t \binom{n}{k}(q-1)^k \leq \vert\mathbb{F}_q^n\vert = q^n
</math>

従って、次が導かれる。

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

== 関連項目 ==
*[[シングルトン限界]]
*[[ギルバート-バルシャモフ限界]]
*[[プロトキン限界]]
*[[ジョンソン限界]]

{{DEFAULTSORT:はみんくけんかい}}
[[Category:符号理論]]
[[Category:数学に関する記事]]