ハミングバウンド

数学およびコンピュータ科学の符号理論の分野において、ハミング限界は任意のブロック符号のパラメータの制限値です。これは、ハミング距離で球を詰め込み、可能なすべての単語の空間を埋め込むという解釈から、球充填限界または体積限界とも呼ばれます。これは、誤り訂正符号が符号語が埋め込まれる空間をどれだけ効率的に利用できるかという点において重要な制限値となります。ハミング限界を達成する符号は、完全符号と呼ばれます。

元のメッセージとエンコードされたバージョンはどちらもq文字のアルファベットで構成されています。各コードワードはn文字です。元のメッセージ（長さm ）はn文字より短くなっています。メッセージはエンコードアルゴリズムによってn文字のコードワードに変換され、ノイズのあるチャネルを介して送信され、最終的に受信側で復号されます。復号プロセスでは、単に「ワード」と呼ばれる判読不能なコードワードを、受信したn文字の文字列に「最も近い」有効なコードワードとして解釈します。

数学的には、長さmのメッセージはq ^m通り存在し、各メッセージは長さmのベクトルとみなすことができます。符号化方式では、 m次元ベクトルをn次元ベクトルに変換します。有効な符号語はq ^m通り存在しますが、符号語が送信される際に、雑音の多い通信チャネルによってn文字のうち 1 つ以上が歪む可能性があるため、q ⁿ通りの符号語が受信される可能性があります。

定義から導かれる${\displaystyle d}$せいぜい

${\displaystyle t=\left\lfloor {\frac {1}{2}}(d-1)\right\rfloor }$

符号語の送信中にエラーが発生した場合、最小距離復号法はそれを正しく復号します（つまり、受信した単語を送信された符号語として復号します）。したがって、このコードはエラーを訂正できると言われています。${\displaystyle t}$エラー。

各コードワードについて${\displaystyle c\in C}$固定半径の球体を考える${\displaystyle t}$その周り${\displaystyle c}$これらのボール（ハミングボール）のペアはすべて交差しない。${\displaystyle t}$-誤り訂正特性。${\displaystyle m}$各ボールに含まれる単語の数（つまり、ボールの体積）をとする。そのようなボールに含まれる単語は、最大で${\displaystyle t}$ボールの中心の構成要素から、コードワードとなる要素を選択します。このようなワードの数は、最大で${\displaystyle t}$の${\displaystyle n}$コードワードの構成要素が、${\displaystyle (q-1)}$考えられるその他の値（コードは${\displaystyle q}$-ary: 値を取ります${\displaystyle {\mathcal {A}}_{q}^{n}}$）。 したがって、

${\displaystyle m={\begin{matrix}\sum _{k=0}^{t}{\binom {n}{k}}(q-1)^{k}\end{matrix}}.}$

${\displaystyle A_{q}(n,d)}$は、コードワードの（最大）総数です。${\displaystyle C}$したがって、定義により${\displaystyle t}$、2つのボールに共通の単語がないボールの最大数。これらのボール内の単語をコードワードを中心にして和集合を取ると、各単語が正確に1回ずつカウントされる単語の集合が得られ、それは の部分集合である。${\displaystyle {\mathcal {A}}_{q}^{n}}$（どこ${\displaystyle |{\mathcal {A}}_{q}^{n}|=q^{n}}$（言葉）そして：

${\displaystyle A_{q}(n,d)\times m=A_{q}(n,d)\times {\begin{matrix}\sum _{k=0}^{t}{\binom {n}{k}}(q-1)^{k}\end{matrix}}\leq q^{n}.}$

由来:

${\displaystyle A_{q}(n,d)\leq {\frac {q^{n}}{\begin{matrix}\sum _{k=0}^{t}{\binom {n}{k}}(q-1)^{k}\end{matrix}}}.}$

のために${\displaystyle A_{q}(n,d)}$コードC (サブセット${\displaystyle {\mathcal {A}}_{q}^{n}}$)、Cの被覆半径は、すべての要素が${\displaystyle {\mathcal {A}}_{q}^{n}}$は、 Cの各コードワードを中心とする半径rの球の少なくとも 1 つに含まれる。Cのパッキング半径は、 Cの各コードワードを中心とする半径sの球の集合が互いに素となるようなsの最大値である。

ハミング限界の証明から、${\displaystyle t\,=\,\left\lfloor {\frac {1}{2}}(d-1)\right\rfloor }$、 我々は持っています：

s ≤ tかつt ≤ r。

したがって、s ≤ rであり、等号が成り立つ場合はs = r = tとなります。等号が成り立つということは、ハミング限界が達成されたことを意味します。

ハミング限界を達成する符号は完全符号と呼ばれます。例としては、符号語が1つしかない符号や、全体の符号などがあります。${\displaystyle {\mathcal {A}}_{q}^{n}}$。別の例として、繰り返し符号があります。これは、メッセージの各シンボルを奇数回繰り返して符号語を得るもので、q = 2 です。これらの例はすべて、しばしば自明な完全符号と呼ばれます。1973 年に、Tietäväinen は^{[ 1 ]}素数冪アルファベット上の任意の非自明な完全符号は、ハミング符号またはゴレイ符号のパラメータを持つことを証明しました。

完全符号は、符号語を中心とするハミング半径tの球が空間を完全に満たす符号と解釈できます( tは被覆半径 = パッキング半径)。準完全符号は、符号語を中心とするハミング半径tの球が互いに素であり、半径t +1の球が空間を覆う (多少の重なりがある場合もある) 符号です。^{[ 2 ]}別の言い方をすれば、被覆半径がパッキング半径より 1 大きい符号は準完全符号です。^{[ 3 ]}

• ギルバート＝ヴァルシャモフ行き
• グリースマー行き
• ジョンソン行き
• プロトキンに縛られた
• レート歪み理論
• シングルトンバウンド

• PJ Cameron; JA Thas; SE Payne (1976). "一般化六角形と完全符号の極性". Geometriae Dedicata . 5 (4): 525– 528. doi : 10.1007/BF00150782 . S2CID 121071671 . 
• Hill, R. (1988). 『符号理論入門』オックスフォード大学出版局ISBN 0-19-853803-0。
• MacWilliams, FJ ; NJA Sloane (1977).誤り訂正符号の理論. North-Holland. ISBN 0-444-85193-3。
• Pless, V. (1982).誤り訂正符号理論入門. John Wiley & Sons. ISBN 0-471-08684-3。
• Roman, S. (1992), Coding and Information Theory , GTM , vol.  134, New York: Springer-Verlag, ISBN 0-387-97812-7
• Tietäväinen, A. (1973). 「有限体上の完全符号の非存在について」 . SIAM J. Appl. Math . 24 : 88–96 . doi : 10.1137/0124010 .
• van Lint, JH (1992).符号理論入門. GTM . 第86巻 （第2 版）. Springer-Verlag. ISBN 3-540-54894-7。
• van Lint, JH (1975). 「完全符号の概観」 . Rocky Mountain Journal of Mathematics . 5 (2): 199–224 . doi : 10.1216/RMJ-1975-5-2-199 .