ハミング限界

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

定義

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

すると、次が成り立つ。

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

ここで、

t = ⌊ \frac{d - 1}{2} ⌋

証明

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

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

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

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

M \times \sum_{k = 0}^{t} (\binom{n}{k}) (q - 1)^{k} \leq | 𝔽_{q}^{n} | = q^{n}

従って、次が導かれる。

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

ハミング限界

定義

証明

関連項目

ナビゲーションメニュー

ハミング限界

定義

証明

関連項目

ナビゲーション メニュー

検索

ナビゲーションメニュー