ブロックコード

符号理論において、ブロック符号は、データをブロックに符号化する大規模で重要な誤り訂正符号のファミリーです。ブロック符号の例は膨大にあり、その多くは幅広い実用的用途に使用されています。ブロック符号の抽象的な定義は概念的に有用です。なぜなら、これにより、符号理論家、数学者、およびコンピューター科学者が、すべてのブロック符号の制限を統一的に研究できるからです。このような制限は、多くの場合、ブロック符号のレートや誤りを検出して訂正する能力など、ブロック符号のさまざまなパラメータを相互に関連付ける 境界の形をとります。

ブロック符号の例としては、リード・ソロモン符号、ハミング符号、アダマール符号、エクスパンダー符号、ゴレイ符号、リード・ミュラー符号、極座標符号などがあります。これらの例も線形符号のクラスに属しているため、線形ブロック符号と呼ばれます。より具体的には、これらの符号はブール多項式を使用して生成できるため、代数ブロック符号または巡回ブロック符号として知られています。

代数ブロック符号は通常、代数デコーダを使用してハードデコードされます。^{[専門用語]}

ブロック コードという用語は、入力データのビットのブロックに作用して出力データのビットを生成するエラー訂正コードを指す場合もあります。したがって、ブロック コーダはメモリのないデバイスです。この定義では、ターボ コード、終端畳み込みコード、その他の反復デコード可能なコード (ターボのようなコード) などのコードもブロック コードと見なされます。非終端畳み込みエンコーダは非ブロック (フレームなし) コードの例であり、メモリがあり、ツリー コードとして分類されます。 ${\displaystyle k}$${\displaystyle n}$${\displaystyle (n,k)}$

この記事では「代数ブロックコード」について扱います。

誤り訂正符号は、チャネル ノイズの影響を受ける信頼性の低い通信チャネルを介してデジタル データを確実に送信するために使用されます。送信者がブロック コードを使用して非常に長い可能性のあるデータ ストリームを送信する場合、送信者はストリームを固定サイズの断片に分割します。このような各断片はメッセージと呼ばれ、ブロック コードによって指定された手順により、各メッセージが個別にコードワードにエンコードされます。コードワードは、ブロック コードのコンテキストではブロックとも呼ばれます。次に、送信者はすべてのブロックを受信者に送信します。受信者は、何らかのデコード メカニズムを使用して、破損している可能性のある受信ブロックから元のメッセージを (うまくいけば) 復元できます。全体的な送信のパフォーマンスと成功は、チャネルとブロック コードのパラメーターによって決まります。

正式には、ブロックコードは単射写像 である。

${\displaystyle C:\Sigma ^{k}\to \Sigma ^{n}}$。

ここで、は有限かつ空でない集合であり、および は整数です。これら 3 つのパラメータとコードに関連するその他のパラメータの意味と重要性については、以下で説明します。 ${\displaystyle \Sigma }$${\displaystyle k}$${\displaystyle n}$

エンコードされるデータ ストリームは、あるアルファベット上の文字列としてモデル化されます。アルファベットのサイズは、 と表記されることがよくあります。 の場合、ブロック コードはバイナリブロック コードと呼ばれます。多くのアプリケーションでは、 を素数累乗と見なし、有限体と同一視すると便利です。 ${\displaystyle \Sigma }$${\displaystyle |\Sigma |}$${\displaystyle q}$${\displaystyle q=2}$${\displaystyle q}$${\displaystyle \Sigma }$ ${\displaystyle \mathbb {F} _{q}}$

メッセージは の要素、つまり長さ の文字列です。したがって、この数値はメッセージ長またはブロック コードの 次元と呼ばれます。${\displaystyle m}$${\displaystyle \Sigma ^{k}}$${\displaystyle k}$${\displaystyle k}$

ブロック コードのブロック長は 、ブロック内のシンボルの数です。したがって、の要素は長さの文字列であり、受信機が受信するブロックに対応します。したがって、これらは受信語とも呼ばれます。あるメッセージ の場合、 はのコードワードと呼ばれます。 ${\displaystyle n}$${\displaystyle c}$${\displaystyle \Sigma ^{n}}$${\displaystyle n}$${\displaystyle c=C(m)}$${\displaystyle m}$${\displaystyle c}$${\displaystyle m}$

ブロック コードのレートはそのメッセージ長とブロック長の比率として定義されます。

${\displaystyle R=k/n}$。

レートが大きいということは、送信されるブロックあたりの実際のメッセージの量が多いことを意味します。この意味で、レートは送信速度を測定し、量はブロック コードによるエンコードによって発生するオーバーヘッドを測定します。一般にデータはロスレス圧縮できないため、レートが超過することはないというのは、単純な情報理論上の事実です。形式的には、これはコードが単射マップであるという事実から生じます。 ${\displaystyle 1-R}$${\displaystyle 1}$${\displaystyle C}$

ブロックコードの距離または最小距離dは、 2つの異なるコードワードが異なる位置の最小数であり、相対距離は分数です。正式には、受信語 に対して、と の間のハミング距離、つまり とが異なる位置の数を表します。すると、コードの最小距離は次のように定義されます。 ${\displaystyle \delta}$${\displaystyle d/n}$${\displaystyle c_{1},c_{2}\in \Sigma ^{n}}$${\displaystyle \Delta (c_{1},c_{2})}$${\displaystyle c_{1}}$${\displaystyle c_{2}}$${\displaystyle c_{1}}$${\displaystyle c_{2}}$${\displaystyle d}$${\displaystyle C}$

${\displaystyle d:=\min _{m_{1},m_{2}\in \Sigma ^{k} \atop m_{1}\neq m_{2}}\Delta [C(m_{1}),C(m_{2})]}$。

任意のコードは単射でなければならないため、任意の 2 つのコードワードは少なくとも 1 つの位置で一致しません。そのため、任意のコードの距離は少なくとも です。さらに、距離は線形ブロック コードの 最小重みに等しくなります。これは次の理由によるものです。${\displaystyle 1}$

${\displaystyle \min _{m_{1},m_{2}\in \Sigma ^{k} \atop m_{1}\neq m_{2}}\Delta [C(m_{1}),C(m_{2})]=\min _{m_{1},m_{2}\in \Sigma ^{k} \atop m_{1}\neq m_{2}}\Delta [\mathbf {0} ,C(m_{1})+C(m_{2})]=\min _{m\in \Sigma ^{k} \atop m\neq \mathbf {0} }w[C(m)]=w_{\min }}$。

距離が大きいほど、より多くのエラー訂正および検出が可能になります。たとえば、送信されたコードワードのシンボルを変更する可能性があり、シンボルを消去または追加することはないエラーのみを考慮する場合、エラーの数は、送信されたコードワードと受信されたワードが異なる位置の数です。距離dのコードでは、コードワードの位置を変更しても別のコードワードが偶然に生成されることは決してないため、受信機は最大で の伝送エラーを検出できます。さらに、 を超える伝送エラーが発生しない場合、受信機は受信したワードをコードワードに一意にデコードできます。これは、受信されたすべてのワードが距離 に最大で 1 つのコードワードを持つためです。 を超える伝送エラーが発生した場合、複数のコードワードが考えられるため、受信機は一般に受信したワードを一意にデコードできません。受信機がこの状況に対処する 1 つの方法は、リスト デコード を使用することです。リスト デコードでは、デコーダーは特定の半径内のすべてのコードワードのリストを出力します。 ${\displaystyle d-1}$${\displaystyle d-1}$${\displaystyle (d-1)/2}$${\displaystyle (d-1)/2}$${\displaystyle (d-1)/2}$

この表記は、サイズ のアルファベット上のブロック符号を、ブロック長、メッセージ長、距離で表します。ブロック符号が線形ブロック符号である場合、表記内の角括弧はその事実を表すために使用されます。 のバイナリ符号の場合、インデックスは省略されることがあります。最大距離の分離可能符号の場合、距離は常に ですが、正確な距離が不明であったり、証明または述べるのが難しかったり、必要なかったりする場合があります。このような場合、- 成分が欠落している可能性があります。 ${\displaystyle (n,k,d)_{q}}$${\displaystyle \Sigma }$${\displaystyle q}$${\displaystyle n}$${\displaystyle k}$${\displaystyle d}$${\displaystyle [n,k,d]_{q}}$${\displaystyle q=2}$${\displaystyle d=n-k+1}$${\displaystyle d}$

場合によっては、特に非ブロック コードの場合、長さ のコードワードを含むコードに対して表記法が使用されます。サイズ のアルファベットを超える長さのメッセージを含むブロック コードの場合、この数は になります。 ${\displaystyle (n,M,d)_{q}}$${\displaystyle M}$${\displaystyle n}$${\displaystyle k}$${\displaystyle q}$${\displaystyle M=q^{k}}$

上で述べたように、実際にはブロック コードであるエラー訂正コードは数多くあります。最初のエラー訂正コードは、1950 年にRichard W. Hammingによって開発されたHamming(7,4)コードです。このコードは、4 ビットのメッセージを 3 つのパリティ ビットを追加して 7 ビットのコードワードに変換します。したがって、このコードはブロック コードです。また、線形コードでもあり、距離は 3 であることがわかります。上記の省略表記では、Hamming(7,4) コードがコードであることを意味します。 ${\displaystyle [7,4,3]_{2}}$

リード・ソロモン符号は、 およびが素数べきである符号の族です。ランク符号は、 およびである符号の族です。アダマール符号は、およびである符号の族です。 ${\displaystyle [n,k,d]_{q}}$${\displaystyle d=n-k+1}$${\displaystyle q}$${\displaystyle [n,k,d]_{q}}$${\displaystyle d\leq n-k+1}$${\displaystyle [n,k,d]_{2}}$${\displaystyle n=2^{k-1}}$${\displaystyle d=2^{k-2}}$

コードワードは、次元空間内の点と見なすことができ、コードはのサブセットです。コードが 距離を持つということは、を中心とし、半径 を持つハミング球内に他のコードワードが存在しないことを意味します。ハミング球は、へのハミング距離が を超えない次元ワードの集合として定義されます。同様に、（最小）距離 を持つ には、次の特性があります。 ${\displaystyle c\in \Sigma ^{n}}$${\displaystyle n}$${\displaystyle \Sigma ^{n}}$${\displaystyle {\mathcal {C}}}$${\displaystyle \Sigma ^{n}}$${\displaystyle {\mathcal {C}}}$${\displaystyle d}$${\displaystyle \forall c\in {\mathcal {C}}}$${\displaystyle c}$${\displaystyle d-1}$${\displaystyle n}$${\displaystyle c}$${\displaystyle d-1}$${\displaystyle {\mathcal {C}}}$${\displaystyle d}$

• ${\displaystyle {\mathcal {C}}}$はエラーを検出できます。コードワードは、半径 でそれ自身を中心とするハミング球内の唯一のコードワードであるため、 のエラーパターンまたはそれ以下のエラーによってコードワードが別のコードワードに変更されることはありません。受信側が、受信したベクトルが のコードワードではないことを検出すると、エラーが検出されます (ただし、訂正される保証はありません)。${\displaystyle d-1}$${\displaystyle c}$${\displaystyle d-1}$${\displaystyle d-1}$${\displaystyle {\mathcal {C}}}$
• ${\displaystyle {\mathcal {C}}}$はエラーを訂正できます。 コードワードは、半径 でそれ自身を中心とするハミング球内の唯一のコードワードであるため、両方の半径 でそれぞれ異なるコードワードを中心とする 2 つのハミング球は互いに重なり合いません。 したがって、エラー訂正を、受信語 に最も近いコードワードを見つけることと考えると、エラー数が を超えない限り、半径 でを中心とするハミング球内のコードワードは 1 つだけであるため、すべてのエラーを訂正できます。${\displaystyle \textstyle \left\lfloor {{d-1} \over 2}\right\rfloor }$${\displaystyle c}$${\displaystyle d-1}$${\displaystyle \textstyle \left\lfloor {{d-1} \over 2}\right\rfloor }$${\displaystyle y}$${\displaystyle \textstyle \left\lfloor {{d-1} \over 2}\right\rfloor }$${\displaystyle y}$${\displaystyle \textstyle \left\lfloor {{d-1} \over 2}\right\rfloor }$
• 複数のエラーがある場合にデコードするには、リストデコードまたは最大尤度デコードを使用できます。${\displaystyle (d-1)/2}$
• ${\displaystyle {\mathcal {C}}}$消失を訂正できます。消失とは、消去されたシンボルの位置がわかっていることを意味します。訂正はパッシング デコードによって実現できます。パッシングでは、消去された位置にシンボルが埋め込まれ、エラー訂正が実行されます。エラーの数が を超えないパッシングが 1 つあるはずであり、したがって消失を訂正できます。${\displaystyle d-1}$ ${\displaystyle q}$${\displaystyle i^{th}}$${\displaystyle i^{th}}$${\displaystyle \textstyle \left\lfloor {{d-1} \over 2}\right\rfloor }$

${\displaystyle C=\{C_{i}\}_{i\geq 1}}$はコードの族と呼ばれ、 は単調増加するコードです。 ${\displaystyle C_{i}}$${\displaystyle (n_{i},k_{i},d_{i})_{q}}$${\displaystyle n_{i}}$

コード族Cのレートは次のように定義される。${\displaystyle R(C)=\lim _{i\to \infty }{k_{i} \over n_{i}}}$

コード群Cの相対距離は次のように定義される。${\displaystyle \delta (C)=\lim _{i\to \infty }{d_{i} \over n_{i}}}$

との関係を調べるために、ブロック符号の下限と上限のセットが知られています。 ${\displaystyle R(C)}$${\displaystyle \delta (C)}$

${\displaystyle R\leq 1-{1 \over n}\cdot \log _{q}\cdot \left[\sum _{i=0}^{\left\lfloor {{\delta \cdot n-1} \over 2}\right\rfloor }{\binom {n}{i}}(q-1)^{i}\right]}$

シングルトン境界とは、ブロックコードのレートと相対距離の合計が 1 より大きくなることはできないということです。

${\displaystyle R+\delta \leq 1+{\frac {1}{n}}}$。

言い換えれば、すべてのブロック符号は不等式 を満たします。 リード・ソロモン符号は、等式を伴うシングルトン境界を満たす符号の重要な例です。 ${\displaystyle k+d\leq n+1}$

については、。言い換えれば、。 ${\displaystyle q=2}$${\displaystyle R+2\delta \leq 1}$${\displaystyle k+2d\leq n}$

一般的なケースでは、距離d を持つ任意のものに対して次の Plotkin 境界が成り立ちます。 ${\displaystyle C\subseteq \mathbb {F} _{q}^{n}}$

1. もし${\displaystyle d=\left(1-{1 \over q}\right)n,|C|\leq 2qn}$
2. もし${\displaystyle d>\left(1-{1 \over q}\right)n,|C|\leq {qd \over {qd-\left(q-1\right)n}}}$

距離 の任意のq進コードの場合、${\displaystyle \delta }$${\displaystyle R\leq 1-\left({q \over {q-1}}\right)\delta +o\left(1\right)}$

${\displaystyle R\geq 1-H_{q}\left(\delta \right)-\epsilon }$ここで、 はq元エントロピー関数です。 ${\displaystyle 0\leq \delta \leq 1-{1 \over q},0\leq \epsilon \leq 1-H_{q}\left(\delta \right)}$${\displaystyle H_{q}\left(x\right)~{\overset {\underset {\mathrm {def} }{}}{=}}~-x\cdot \log _{q}{x \over {q-1}}-\left(1-x\right)\cdot \log _{q}{\left(1-x\right)}}$

を定義します。距離dの任意のコードに対して、半径eのハミングボール内のコードワードの最大数を と します。 ${\displaystyle J_{q}\left(\delta \right)~{\overset {\underset {\mathrm {def} }{}}{=}}~\left(1-{1 \over q}\right)\left(1-{\sqrt {1-{q\delta \over {q-1}}}}\right)}$
${\displaystyle J_{q}\left(n,d,e\right)}$${\displaystyle C\subseteq \mathbb {F} _{q}^{n}}$

するとジョンソン境界が成立する 。${\displaystyle J_{q}\left(n,d,e\right)\leq qnd}$${\displaystyle {e \over n}\leq {{q-1} \over q}\left({1-{\sqrt {1-{q \over {q-1}}\cdot {d \over n}}}}\,\right)=J_{q}\left({d \over n}\right)}$

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

ブロック コードは、長年にわたって注目されてきた球体パッキング問題と結びついています。2 次元では、簡単に視覚化できます。テーブルの上に平らに置いたペニー硬貨の束を一緒に押し付けます。その結果、蜂の巣のような六角形のパターンができます。ただし、ブロック コードは、簡単に視覚化できないより多くの次元に依存します。深宇宙通信で使用される強力なGolay コードは、24 次元を使用します。バイナリ コードとして使用する場合 (通常はバイナリ コードとして使用します)、次元は、上記で定義したコードワードの長さを指します。

コーディングの理論では、 N次元球モデルを使用します。たとえば、テーブル上または 3 次元の円にペニーを何枚詰め込めるか、地球儀にビー玉を何個詰め込めるかなどです。コードの選択には他の考慮事項も関係します。たとえば、長方形のボックスの制約に六角形を詰め込むと、角に空きスペースが残ります。寸法が大きくなるにつれて、空きスペースの割合は小さくなります。しかし、特定の寸法では、詰め込みにすべてのスペースが使用され、これらのコードはいわゆる完全コードです。このようなコードは非常に少ないです。

もう 1 つの特性は、単一のコードワードが持つことができる近傍の数です。^[1] 再び、ペニーを例に考えてみましょう。まず、ペニーを長方形のグリッドに詰めます。各ペニーには 4 つの近傍があります (さらに遠い角にも 4 つ)。六角形では、各ペニーには 6 つの近傍があります。3 次元と 4 次元では、最大の詰​​め込みはそれぞれ12 面と24 セルで、それぞれ 12 と 24 の近傍があります。次元を増やすと、近傍の数は非常に急速に増加します。一般に、値はキス数によって与えられます。

その結果、ノイズによって受信機が隣接ノードを選択（つまりエラー）する方法の数も増えます。これはブロックコード、そして実際すべてのコードの基本的な制限です。1つの隣接ノードにエラーを引き起こすことは難しいかもしれませんが、隣接ノードの数が十分に多いと、合計エラー確率は実際に低下します。^[1]

• チャネル容量
• シャノン・ハートレーの定理
• ノイズの多いチャンネル
• リストデコード^[1]
• 球詰め

• JH van Lint (1992)。コーディング理論入門。GTM。第86巻（第2版）。Springer-Verlag。p. 31。ISBN 3-540-54894-7。
• FJ MacWilliams ; NJA Sloane (1977)。誤り訂正符号の理論。ノースホランド。p. 35。ISBN 0-444-85193-3。
• W. Huffman、V.Pless (2003)。誤り訂正符号の基礎。ケンブリッジ大学出版局。ISBN 978-0-521-78280-7。
• S. Lin; DJ Jr. Costello (1983)。『エラー制御コーディング: 基礎と応用』。Prentice- Hall。ISBN 0-13-283796-X。

• チャラン・ラングトン (2001) コーディングの概念とブロックコーディング