エリアス・バサリゴは拘束される

エリアス・バッサリゴ境界は、データ送信または通信 中のエラー訂正のための符号理論で使用される数学的限界です。

を長さ の -ary コード、つまり の部分集合とする。[ ^1]をの速度、相対距離、および ${\displaystyle C}$${\displaystyle q}$${\displaystyle n}$${\displaystyle [q]^{n}}$${\displaystyle R}$${\displaystyle C}$${\displaystyle \delta}$

${\displaystyle B_{q}(y,\rho n)=\left\{x\in [q]^{n}\ :\ \Delta (x,y)\leqslant \rho n\right\}}$

を中心とする半径 のハミング球とする。を半径 のハミング球の体積とする。ハミング球の体積は並進不変、すなわち に無関係であることは明らかである。特に、${\displaystyle \rho n}$${\displaystyle y}$${\displaystyle {\text{Vol}}_{q}(y,\rho n)=|B_{q}(y,\rho n)|}$${\displaystyle \rho n}$${\displaystyle y.}$${\displaystyle |B_{q}(y,\rho n)|=|B_{q}(0,\rho n)|.}$

が十分に大きい場合、速度と相対距離はエリアス・バッサリゴの境界を満たします。${\displaystyle n}$ ${\displaystyle R}$ ${\displaystyle \delta}$

${\displaystyle R\leqslant 1-H_{q}(J_{q}(\delta ))+o(1),}$

どこ

${\displaystyle H_{q}(x)\equiv _{\text{def}}-x\log _{q}\left({x \over {q-1}}\right)-(1-x)\log _{q}{(1-x)}}$

はq元エントロピー関数であり、

${\displaystyle J_{q}(\delta )\equiv _{\text{def}}\left(1-{1 \over q}\right)\left(1-{\sqrt {1-{q\delta \over {q-1}}}}\right)}$

はジョンソン境界に関連する関数です。

エリアス・バッサリゴ境界を証明するには、次の補題から始めます。

補題およびに対して、少なくとも ${\displaystyle C\subseteq [q]^{n}}$${\displaystyle 0\leqslant e\leqslant n}$${\displaystyle e}$

${\displaystyle {\frac {|C|{\text{Vol}}_{q}(0,e)}{q^{n}}}}$

コードワードが含まれています。

補題の証明。受信語をランダムに選び、を中心とし、半径のハミング球とする。は（一様）ランダムに選択されるので、重なり合う領域の期待サイズは ${\displaystyle y\in [q]^{n}}$${\displaystyle B_{q}(y,0)}$${\displaystyle y}$${\displaystyle e}$${\displaystyle y}$${\displaystyle |B_{q}(y,e)\cap C|}$

${\displaystyle {\frac {|C|{\text{Vol}}_{q}(y,e)}{q^{n}}}}$

これはサイズの期待値なので、少なくとも1つは存在しなければなりません。 ${\displaystyle y}$

${\displaystyle |B_{q}(y,e)\cap C|\geqslant {{|C|{\text{Vol}}_{q}(y,e)} \over {q^{n}}}={{|C|{\text{Vol}}_{q}(0,e)} \over {q^{n}}},}$

それ以外の場合、期待値はこの値よりも小さくなければなりません。

ここで、エリアス・バッサリゴ境界を証明します。定義補題により、次のようなコードワードを持つハミング球が存在します。 ${\displaystyle e=nJ_{q}(\delta )-1.}$${\displaystyle B}$

${\displaystyle B\geqslant {{|C|{\text{Vol}}(0,e)} \over {q^{n}}}}$

ジョンソン境界により、 となる。したがって、 ${\displaystyle B\leqslant qdn}$

${\displaystyle |C|\leqslant qnd\cdot {{q^{n}} \over {{\text{Vol}}_{q}(0,e)}}\leqslant q^{n(1-H_{q}(J_{q}(\delta ))+o(1))}}$

2番目の不等式はハミング球の体積の下限から導かれます。

${\displaystyle {\text{Vol}}_{q}\left(0,\left\left\lfloor {\frac {d-1}{2}}\right\rfloor \right)\geqslant q^{H_{q}\left({\frac {\delta }{2}}\right)no(n)}.}$

と を入れると、2 番目の不等式が得られます。 ${\displaystyle d=2e+1}$${\displaystyle \delta ={\tfrac {d}{n}}}$

したがって、

${\displaystyle R={\log _{q}{|C|} \over n}\leqslant 1-H_{q}(J_{q}(\delta ))+o(1)}$

• ギルバート・ヴァルシャモフ境界
• ハミング境界
• ジョンソン行き
• プロトキン縛り
• シングルトンバウンド

Bassalygo, LA (1965)、「誤り訂正符号の新しい上限」、情報伝送の問題、1 (1): 32–35

Claude E. Shannon、Robert G. Gallager、Berlekamp、Elwyn R. (1967)、「離散メモリレスチャネルでのコーディングのエラー確率の下限。パート I。」、情報と制御、10：65–103、doi：10.1016 / s0019-9958（67）90052-6

Claude E. Shannon、Robert G. Gallager、Berlekamp、Elwyn R. (1967)、「離散メモリレスチャネルでのコーディングのエラー確率の下限。パート II。」、情報制御、10 : 522–552、doi : 10.1016/s0019-9958(67)91200-4