ハミング限界

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

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

定義[編集]

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

すると、次が成り立つ。


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

ここで、

t=\left\lfloor\frac{d-1}{2}\right\rfloor

証明[編集]

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

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


\begin{matrix}
\\
\sum_{k=0}^t \binom{n}{k}(q-1)^k
\\
\end{matrix}

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


\begin{matrix}
\\
M \times \sum_{k=0}^t \binom{n}{k}(q-1)^k \leq |\mathbb{F}_q^n| = q^n
\\
\end{matrix}

従って、次が導かれる。


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

関連項目[編集]