ハミング限界(ハミングげんかい、英: Hamming bound)は、符号(線型符号とは限らない)のパラメータの限界値を指す。球充填の限界を情報理論の観点で言い直したものと言える。ハミング限界に従った符号を「完全符号; perfect code」と呼ぶ。 q進数の符号 C {\displaystyle C} が長さ n {\displaystyle n} で最小ハミング距離 d {\displaystyle d} であるとき、その可能な最大サイズ(符号語の総数)を A q ( n , d ) {\displaystyle A_{q}(n,d)} とする。なお、q進数の符号は、 q {\displaystyle q} 個の要素の体 F q n {\displaystyle \mathbb {F} _{q}^{n}} 上の線型符号である。 すると、次が成り立つ。 A q ( n , d ) ≤ q n ∑ k = 0 t ( n k ) ( q − 1 ) k {\displaystyle A_{q}(n,d)\leq {\frac {q^{n}}{\sum _{k=0}^{t}{\binom {n}{k}}(q-1)^{k}}}} ここで、 t = ⌊ d − 1 2 ⌋ {\displaystyle t=\lfloor {\frac {d-1}{2}}\rfloor } d {\displaystyle d} の定義から、符号語の転送において最大で t = ⌊ d − 1 2 ⌋ {\displaystyle t=\lfloor {\tfrac {d-1}{2}}\rfloor } の誤りが発生したとすると、最小距離復号によって正しく復号できる(すなわち、符号化された符号語を正しく復号できる)。つまり、この符号は t {\displaystyle t} 個の誤りを訂正可能である。 c ∈ C {\displaystyle c\in C} であるようなある符号語について、 c {\displaystyle c} を中心とする半径 t {\displaystyle t} の球を考える。このような球の範囲内なら誤り訂正が正しく行われる。符号語を構成する n {\displaystyle n} 個の要素のうち t {\displaystyle t} 個まで誤りがあっても正しく復号できるため、それぞれの球には以下の符号語が含まれる(つまり、中心にある真の符号語の一部を変更した符号語群の数)。符号語の一桁は q進数であるから、とりうる値は ( q − 1 ) {\displaystyle (q-1)} 種類になる。 ∑ k = 0 t ( n k ) ( q − 1 ) k {\displaystyle \sum _{k=0}^{t}{\binom {n}{k}}(q-1)^{k}} C {\displaystyle C} に存在する符号語の総数を M {\displaystyle M} とする。全ての符号語から球の和集合をとると、結果として得られる符号語の総数は F q n {\displaystyle \mathbb {F} _{q}^{n}} 以内となる。それぞれの球は重ならないので、それぞれの要素数の総和をとると、次が成り立つといえる。 M × ∑ k = 0 t ( n k ) ( q − 1 ) k ≤ 。 F q n 。 = q n {\displaystyle M\times \sum _{k=0}^{t}{\binom {n}{k}}(q-1)^{k}\leq \vert \mathbb {F} _{q}^{n}\vert =q^{n}} 従って、次が導かれる。 A q ( n , d ) ≤ q n ∑ k = 0 t ( n k ) ( q − 1 ) k {\displaystyle A_{q}(n,d)\leq {\frac {q^{n}}{\sum _{k=0}^{t}{\binom {n}{k}}(q-1)^{k}}}}
定義
証明
関連項目
シングルトン限界
ギルバート-バルシャモフ限界
プロトキン限界
ジョンソン限界