ブロックコード

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

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

代数ブロックコードは通常、代数デコーダーを使用して ハードデコードされます。

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

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

ブロックコードとそのパラメータ

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

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

C:Σけ→Σn{\displaystyle C:\Sigma^{k}\to \Sigma^{n}}。

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

アルファベットΣ

符号化されるデータストリームは、あるアルファベット上の文字列としてモデル化されます。アルファベットのサイズは、しばしば と表記されます。 の場合、ブロック符号はバイナリブロック符号と呼ばれます。多くの応用において、 を素数 のべき乗とみなし、有限体と同一視することは有用です。 Σ{\displaystyle \Sigma }|Σ|{\displaystyle |\Sigma |}q{\displaystyle q}q＝2{\displaystyle q=2}q{\displaystyle q}Σ{\displaystyle \Sigma }Fq{\displaystyle \mathbb {F} _{q}}

メッセージ長k

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

ブロック長n

ブロック符号のブロック長は 、ブロック内のシンボルの数です。したがって、の要素は長さ の文字列であり、受信側が受信する可能性のあるブロックに対応します。そのため、これらは受信語とも呼ばれます。あるメッセージ に対して の場合、 はの符号語と呼ばれます。 n{\displaystyle n}c{\displaystyle c}Σn{\displaystyle \Sigma ^{n}}n{\displaystyle n}c＝C（メートル）{\displaystyle c=C(m)}メートル{\displaystyle m}c{\displaystyle c}メートル{\displaystyle m}

レートR

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

R＝け/n{\displaystyle R=k/n}。

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

距離d

ブロック符号の距離または最小距離dは、任意の2つの異なる符号語が異なる位置の最小数であり、相対距離は分数 である。正式には、受信語 に対して、との間のハミング距離、つまりと が異なる位置の数を表すものとする。この場合、符号の最小距離は次のように定義される 。δ{\displaystyle \delta}d/n{\displaystyle d/n}c1、c2∈Σn{\displaystyle c_{1},c_{2}\in \Sigma ^{n}}Δ（c1、c2）{\displaystyle \Delta (c_{1},c_{2})}c1{\displaystyle c_{1}}c2{\displaystyle c_{2}}c1{\displaystyle c_{1}}c2{\displaystyle c_{2}}d{\displaystyle d}C{\displaystyle C}

d:=分メートル1、メートル2∈Σけメートル1≠メートル2Δ[C（メートル1）、C（メートル2）]{\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つの位置で一致しないため、あらゆるコードの距離は少なくとも となります。さらに、この距離は線形ブロックコードの 最小重みに等しくなります。これは以下の理由によるものです。1{\displaystyle 1}

分メートル1、メートル2∈Σけメートル1≠メートル2Δ[C（メートル1）、C（メートル2）]＝分メートル1、メートル2∈Σけメートル1≠メートル2Δ[0、C（メートル2）−C（メートル1）]＝分メートル∈Σけメートル≠0わ[C（メートル）]＝わ分{\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_{2})-C(m_{1})]=\min _{m\in \Sigma ^{k} \atop m\neq \mathbf {0} }w[C(m)]=w_{\min }}。

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

この表記法は、サイズ のアルファベット上のブロック符号を記述するものであり、ブロック長、メッセージ長、距離 を持ちます。ブロック符号が線形ブロック符号である場合、表記法中の角括弧はその事実を表すために使用されます。 を持つバイナリ符号の場合、添え字は省略されることがあります。最大距離の分離可能符号の場合、距離は常に ですが、正確な距離が不明であったり、証明や明示が困難であったり、必要なかったりする場合があります。そのような場合、-要素は省略されることがあります。 （n、け、d）q{\displaystyle (n,k,d)_{q}}Σ{\displaystyle \Sigma }q{\displaystyle q}n{\displaystyle n}け{\displaystyle k}d{\displaystyle d}[n、け、d]q{\displaystyle [n,k,d]_{q}}q＝2{\displaystyle q=2}d＝n−け+1{\displaystyle d=n-k+1}d{\displaystyle d}

非ブロック符号の場合など、長さ の符号語を含む符号に対してこの表記法が使用されることがあります。長さ のメッセージを含むブロック符号の場合、この数値は になります。 （n、M、d）q{\displaystyle (n,M,d)_{q}}M{\displaystyle M}n{\displaystyle n}け{\displaystyle k}q{\displaystyle q}M＝qけ{\displaystyle M=q^{k}}

例

前述のように、実際にはブロック符号である誤り訂正符号は数多く存在します。最初の誤り訂正符号は、1950年にリチャード・W・ハミングによって開発されたハミング(7,4)符号です。この符号は、4ビットのメッセージに3つのパリティビットを追加することで、7ビットのコードワードに変換します。したがって、この符号はブロック符号です。また、線形符号でもあり、距離は3です。上記の略記法では、ハミング(7,4)符号は符号であることを意味します。 [7、4、3]2{\displaystyle [7,4,3]_{2}}

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

エラー検出および訂正特性

符号語は次元空間内の点とみなすことができ、符号はの部分集合です。符号が 距離 を持つということは、を中心とし半径 を持つハミング球内に他の符号語が存在しないことを意味します。ハミング球は、から へのハミング距離がを超えない次元語の集合として定義されます。同様に、（最小）距離 を持つ には、以下の特性があります。 c∈Σn{\displaystyle c\in \Sigma ^{n}}n{\displaystyle n}Σn{\displaystyle \Sigma ^{n}}C{\displaystyle {\mathcal {C}}}Σn{\displaystyle \Sigma ^{n}}C{\displaystyle {\mathcal {C}}}d{\displaystyle d}たc∈C{\displaystyle \forall c\in {\mathcal {C}}}c{\displaystyle c}d−1{\displaystyle d-1}n{\displaystyle n}c{\displaystyle c}d−1{\displaystyle d-1}C{\displaystyle {\mathcal {C}}}d{\displaystyle d}

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

ブロックコードの下限と上限

ハミング限界
理論的な限界（ハミング限界など）は存在しますが、実際にどのようなコードを構築できるかという疑問も存在します。これは、多次元の箱に球体を詰め込むようなものです。この図は、構築可能なコード（線形およびバイナリ）を示しています。x軸は保護されたシンボルの数k、y軸は必要なチェックシンボルの数n–kを示しています。プロットされているのは、 1（保護されていない）から34までの様々なハミング距離に対する限界です。点で示されているのは完全なコードです。
  • x軸の明るいオレンジ: 単純な保護されていないコード
  • y軸のオレンジ：単純な繰り返しコード
  • データセットd =3 の濃いオレンジ: 古典的な完全ハミング符号
  • 濃い赤と大きい：唯一の完全な2進ゴレイコード

コードファミリー

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

コード族Cのレートは次のように定義される。R（C）＝リム私→∞け私n私{\displaystyle R(C)=\lim _{i\to \infty}{k_{i} \over n_{i}}}

コード族Cの相対距離は次のように定義される。δ（C）＝リム私→∞d私n私{\displaystyle \delta (C)=\lim _{i\to \infty }{d_{i} \over n_{i}}}

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

ハミング境界

R≤1−1n⋅ログq⋅[∑私＝0⌊δ⋅n−12⌋（n私）（q−1）私]{\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 より大きくなることはできないというものです。

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

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

プロトキン縛り

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

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

  1. もしd＝（1−1q）n、|C|≤2qn{\displaystyle d=\left(1-{1 \over q}\right)n,|C|\leq 2qn}
  2. もしd>（1−1q）n、|C|≤qdqd−（q−1）n{\displaystyle d>\left(1-{1 \over q}\right)n,|C|\leq {qd \over {qd-\left(q-1\right)n}}}

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

ギルバート・ヴァルシャモフ境界

R≥1−Hq（δ）−ϵ{\displaystyle R\geq 1-H_{q}\left(\delta \right)-\epsilon }ここで、 はq元エントロピー関数です。 0≤δ≤1−1q、0≤ϵ≤1−Hq（δ）{\displaystyle 0\leq \delta \leq 1-{1 \over q},0\leq \epsilon \leq 1-H_{q}\left(\delta \right)}Hq（×） ＝def −×⋅ログq⁡×q−1−（1−×）⋅ログq⁡（1−×）{\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のハミングボール内のコードワードの最大数を とします。 Jq(δ) =def (1−1q)(1−1−qδq−1){\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)}Jq(n,d,e){\displaystyle J_{q}\left(n,d,e\right)}C⊆Fqn{\displaystyle C\subseteq \mathbb {F} _{q}^{n}}

するとジョンソン境界が得られる 。Jq(n,d,e)≤qnd{\displaystyle J_{q}\left(n,d,e\right)\leq qnd}en≤q−1q(1−1−qq−1⋅dn)=Jq(dn){\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)}

エリアス・バッサリゴ境界

R=logq⁡|C|n≤1−Hq(Jq(δ))+o(1){\displaystyle R={\log _{q}{|C|} \over n}\leq 1-H_{q}\left(J_{q}\left(\delta \right)\right)+o\left(1\right)}

球パッキングと格子

ブロック符号は、長年注目を集めてきた球面パッキング問題と関連しています。2次元では視覚化が容易です。テーブルの上にペニー硬貨を平らに並べ、押し付け合うと、蜂の巣のような六角形のパターンができます。しかし、ブロック符号はより多くの次元に依存しており、視覚化が容易ではありません。深宇宙通信で使用されている強力なゴレイ符号は24次元です。バイナリコードとして使用する場合（通常はバイナリコードとして使用されます）、次元は上記で定義したコードワードの長さを指します。

符号化理論では、 N次元球面モデルが用いられます。例えば、テーブル上または3次元の円の中にペニー硬貨を何枚詰め込めるか、地球儀の中にビー玉を何個詰め込めるかなどです。コードの選択には、他にも考慮すべき要素があります。例えば、長方形の箱という制約の中に六角形を詰め込むと、角に空きスペースが残ります。寸法が大きくなるにつれて、空きスペースの割合は小さくなります。しかし、ある寸法では、詰め込みによってすべてのスペースが使用され、このようなコードはいわゆる完全コードと呼ばれます。このようなコードはごくわずかです。

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

その結果、ノイズによって受信機が隣接ノードを選択（つまりエラー）する方法の数も増加します。これはブロック符号、そしてあらゆる符号の根本的な限界です。単一の隣接ノードにエラーを引き起こすことは困難かもしれませんが、隣接ノードの数が十分に大きくなると、全体のエラー確率は実際に悪化します。[ 1 ]

参照

参考文献

  1. ^ a b c Christian SchlegelとLance Pérez (2004).トレリスとターボ符号化. Wiley-IEEE. p. 73. ISBN 978-0-471-22755-7。
「 https://en.wikipedia.org/w/index.php?title=Block_code&oldid=1282779815」より取得