ハミング限界

ハミング限界について

ハミング限界（Hamming Bound）は、符号理論における重要な概念で、符号のパラメータとしての最大値を示します。これは、情報理論の視点から見た球充填の限界を表現したものと考えられます。この限界に従う符号は「完全符号（perfect code）」と呼ばれ、誤り訂正能力を最大限に活用します。

定義

符号 C が長さ n で、最小ハミング距離 d を持つ場合、可能な最大の符号語の数を A_q(n, d) と定義します。ここで、q は符号に使われる進数で、各符号語は体 F_q^n 上の線形符号に位置します。ハミング限界は次の不等式で表されます。

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

ここで、t は最小ハミング距離 d に基づき以下のように定義されます。

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

証明の概略

最小ハミング距離 d の特性から、符号語が最大で t 個の誤りを訂正できることがわかります。これは、最小距離復号を通じて正しく符号語が復元できるためです。符号語 c を中心に半径 t の球を考えると、この球に含まれる符号語は誤り訂正が可能となります。

これは、符号語を構成する n 個の要素の中で、t 個までの誤りを正しく復号する能力を意味します。各球には中心の真の符号語に基づく変更を加えた符号語群が含まれ、これらの符号語は、次の和で総合的に示されます。

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

ここで、C に含まれる符号語の総数を M とします。全ての符号語から得られる球の和集合は、F_q^n の範囲内に収まる必要があります。球が重ならない限り、その各要素の数の総和を求めることで、以下の関係が成り立ちます。

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

以上より、ハミング限界の不等式が導かれます。これは、誤りの発生に対する符号の耐性を示し、実際に使用される符号設計にとって非常に重要な指針となります。

関連項目

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

これらの限界は、符号理論におけるさまざまな場面で有用であり、符号設計者の指針となっています。ハミング限界は、特にエラー訂正に焦点を当てた情報通信システムにおいて、信号の精度を保つための基礎となる原則を提供します。

もう一度検索