ハミング境界

数学とコンピュータサイエンスの符号理論の分野において、ハミング境界は任意のブロック符号のパラメータの制限です。ハミング距離の球をすべての可能なワードの空間に詰め込むという解釈から、球詰め境界または体積境界とも呼ばれます。これは、誤り訂正符号がコードワードが埋め込まれている空間を利用できる効率に重要な制限を与えます。ハミング境界を達成するコードは完全なコードと言われています。

元のメッセージとエンコードされたバージョンは、どちらもq文字のアルファベットで構成されています。各コードワードにはn文字が含まれます。元のメッセージ (長さm )はn文字より短いです。メッセージはエンコード アルゴリズムによってn文字のコードワードに変換され、ノイズの多いチャネルを介して送信され、最後に受信機によってデコードされます。デコード プロセスでは、単に単語と呼ばれる文字化けしたコードワードを、受信したn文字の文字列に「最も近い」有効なコードワードとして解釈します。

数学的には、長さmのメッセージはちょうどq ^m個あり、各メッセージは長さmのベクトルとみなすことができます。エンコード方式は、m次元ベクトルをn次元ベクトルに変換します。ちょうどq ^{m 個}の有効なコードワードが可能ですが、コードワードが送信されるときにノイズの多いチャネルによってn文字のうちの 1 つ以上が歪む可能性があるため、q ⁿ個のワードのいずれかが受信される可能性があります。

アルファベット セットは、要素を持つ記号の集合です。アルファベット セット上の長さの文字列の集合は で表されます。(この文字列の集合には、異なる文字列が存在します。)長さの -ary ブロック コードは、の文字列のサブセットです。ここで、アルファベット セットは、要素を持つ任意のアルファベット セットです。(アルファベットのサイズが であれば、アルファベット セットの選択によって結果が変わることはありません。) ${\displaystyle {\mathcal {A}}_{q}}$${\displaystyle q}$${\displaystyle n}$${\displaystyle {\mathcal {A}}_{q}}$${\displaystyle {\mathcal {A}}_{q}^{n}}$${\displaystyle q^{n}}$${\displaystyle q}$${\displaystyle n}$${\displaystyle {\mathcal {A}}_{q}^{n}}$${\displaystyle {\mathcal {A}}_{q}}$${\displaystyle q}$${\displaystyle {\mathcal {A}}_{q}}$${\displaystyle q}$

が長さ の-ary ブロック符号の最大可能サイズと、ブロック符号の要素間の最小ハミング距離( の場合は必ず正) を表します。${\displaystyle \ A_{q}(n,d)}$${\displaystyle q}$${\displaystyle \C}$${\displaystyle n}$ ${\displaystyle d}$${\displaystyle q^{n}>1}$

したがって、ハミング境界は次のようになります。

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

どこ

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

の定義から、最大でも ${\displaystyle d}$

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

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

各コードワード について、の周囲に固定半径を持つ球を考えます。これらの球 (ハミング球) のすべてのペアは、-誤り訂正特性により交差しません。を各球内の単語数 (つまり、球の体積) とします。このような球内の単語は、球の中心の要素から最大 だけずれることができます。これがコードワードです。このような単語の数は、コードワードの要素を最大 まで選択して、他の可能な値の 1 つにずれるようにすることで得られます(コードは-ary であるため、 内の値を取ることに注意してください)。したがって、 ${\displaystyle c\in C}$${\displaystyle t}$${\displaystyle c}$${\displaystyle t}$${\displaystyle m}$${\displaystyle t}$${\displaystyle t}$${\displaystyle n}$${\displaystyle (q-1)}$${\displaystyle q}$${\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)}$は 内のコードワードの (最大) 総数であり、 の定義により、2 つのボールが共通の単語を持たないボールの最大数です。コードワードを中心とするこれらのボールの単語の和集合をとると、単語の集合が生成されます。各単語は 1 回だけカウントされ、 のサブセットになります(単語は )。したがって、次のようになります。 ${\displaystyle C}$${\displaystyle t}$${\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{行列}}}.}$

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

ハミング境界の証明から、 に対して次式が得られることがわかります。 ${\displaystyle t\,=\,\left\lfloor {\frac {1}{2}}(d-1)\right\rfloor }$

s ≤ tかつt ≤ r。

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

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

完全なコードとは、コードワードを中心とするハミング半径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.
• ヒル、R. (1988)。コーディング理論入門。オックスフォード大学出版局。ISBN 0-19-853803-0。
• MacWilliams, FJ ; NJA Sloane (1977)。誤り訂正符号の理論。ノースホランド。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、ニューヨーク：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). 「完全コードの調査」ロッキーマウンテン数学ジャーナル. 5 (2): 199–224. doi : 10.1216/RMJ-1975-5-2-199 .