線形コード

符号理論において、線形符号とは、任意の符号語の線形結合が符号語となる誤り訂正符号である。線形符号は伝統的にブロック符号と畳み込み符号に分類されるが、ターボ符号はこれら2種類のハイブリッドとみなすこともできる。^[1]線形符号は、他の符号よりも効率的な符号化・復号アルゴリズムを可能にする（シンドローム復号を参照）。^[要出典]

線形コードは前方誤り訂正に使用され、通信チャネルでシンボル（ビットなど）を送信する方法で適用されます。これにより、通信でエラーが発生した場合、メッセージブロックの受信者が一部のエラーを訂正または検出できます。線形ブロックコードのコードワードは、送信される元の値よりも多くのシンボルを使用してエンコードされたシンボルのブロックです。^[2]長さn の線形コードは、n個のシンボルを含むブロックを送信します。たとえば、[7,4,3]ハミングコードは、7 ビットのコードワードを使用して 4 ビットのメッセージを表す線形バイナリコードです。2 つの異なるコードワードは、少なくとも 3 ビットが異なります。結果として、コードワードごとに最大 2 つのエラーを検出でき、1 つのエラーを訂正できます。^[3] このコードには、2 ⁴  = 16 のコードワードが含まれます。

定義とパラメータ

長さn、次元kの線形符号は、q個の元を持つ有限体のベクトル空間Cの次元kの線形部分空間です。このような符号はq元符号と呼ばれます。q  = 2 またはq = 3の場合 、符号はそれぞれ2元符号、3元符号として記述されます。C のベクトルは符号語と呼ばれます。符号のサイズは符号語の数であり、 q ^kに等しくなります。 ${\displaystyle \mathbb {F} _{q}^{n}}$ ${\displaystyle \mathbb {F} _{q}}$

符号語の重みは、その符号語に含まれる非ゼロ要素の数であり、2つの符号語間の距離は、それらの間のハミング距離、つまり、それらの符号語が異なる要素の数です。線形符号の距離dは、その非ゼロ符号語の最小重み、あるいは異なる符号語間の最小距離です。長さn、次元k、距離dの線形符号は、[ n , k , d ] 符号（より正確には、符号） と呼ばれます。${\displaystyle [n,k,d]_{q}}$

標準基底を与える理由は、各座標が「ノイズの多い通信路」（ 2元対称通信路）を介して伝送される「ビット」を表し、伝送エラーの確率がわずかであるためです。他の基底を用いると、このモデルは使用できず、ハミング計量は、私たちが期待する伝送エラーの数を測定できません。 ${\displaystyle \mathbb {F} _{q}^{n}}$

ジェネレータとチェックマトリックス

の線形部分空間として、コードC全体（非常に大きくなる場合もある）は、コードワード集合（線形代数における基底として知られる）のスパンとして表すことができます。これらの基底コードワードは、コードCの生成行列として知られる行列 G の行に並べられることがよくあります。G がブロック行列形式（ただしは単位行列、 P は何らかの行列）を持つ場合、G は標準形式であるといいます。 ${\displaystyle \mathbb {F} _{q}^{n}}$ ${\displaystyle k}$ ${\displaystyle {\boldsymbol {G}}=[I_{k}\mid P]}$ ${\displaystyle I_{k}}$ ${\displaystyle k\times k}$ ${\displaystyle k\times (n-k)}$

核がCである線形関数を表す行列Hは、 Cの検査行列（またはパリティ検査行列）と呼ばれます。同様に、 Hは零空間がCである行列です。Cが標準形の生成行列Gを持つ符号である場合、はCの検査行列です。Hによって生成される符号はCの双対符号と呼ばれます。Gが行列であり、Hが行列であることは検証できます。 ${\displaystyle \phi :\mathbb {F} _{q}^{n}\to \mathbb {F} _{q}^{n-k}}$ ${\displaystyle {\boldsymbol {G}}=[I_{k}\mid P]}$ ${\displaystyle {\boldsymbol {H}}=[-P^{T}\mid I_{n-k}]}$ ${\displaystyle k\times n}$ ${\displaystyle (n-k)\times n}$

線形性は、符号語c ₀と他の符号語c  ≠  c ₀との間の最小ハミング距離 d がc ₀に依存しないことを保証する。これは、 C内の2つの符号語の差c  −  c ₀もまた符号語（すなわち、部分空間Cの要素）であるという性質と、 d ( c , c ₀ ) =  d ( c  −  c ₀ , 0 )という性質から導かれる。これらの性質は、

${\displaystyle \min _{c\in C,\ c\neq c_{0}}d(c,c_{0})=\min _{c\in C,\ c\neq c_{0}}d(c-c_{0},0)=\min _{c\in C,\ c\neq 0}d(c,0)=d.}$

言い換えれば、線形符号の符号語間の最小距離を求めるには、非ゼロ符号語に注目するだけで十分です。重みが最小の非ゼロ符号語は、ゼロ符号語との距離が最小となり、それによって符号の最小距離が決まります。

線形コードCの距離d は、検査行列Hの線形従属列の最小数にも等しくなります。

証明:は と等価であるため 、 はの列です。 を持つ項目を削除します。 を持つ項目は線形従属です。したがって、は少なくとも線形従属列の最小数です。一方、は列インデックス セット である線形従属列の最小セットを考えます。ここで、の場合となるベクトルを考えます。 であるためであることに注意してください。したがって、 が得られ、これは における線形従属列の最小数です。したがって、主張された特性は証明されました。 ${\displaystyle {\boldsymbol {H}}\cdot {\boldsymbol {c}}^{T}={\boldsymbol {0}}}$ ${\displaystyle \sum _{i=1}^{n}(c_{i}\cdot {\boldsymbol {H_{i}}})={\boldsymbol {0}}}$ ${\displaystyle {\boldsymbol {H_{i}}}}$ ${\displaystyle i^{th}}$ ${\displaystyle {\boldsymbol {H}}}$ ${\displaystyle c_{i}=0}$ ${\displaystyle {\boldsymbol {H_{i}}}}$ ${\displaystyle c_{i}\neq 0}$ ${\displaystyle d}$ ${\displaystyle \{{\boldsymbol {H_{j}}}\mid j\in S\}}$ ${\displaystyle S}$ ${\displaystyle \sum _{i=1}^{n}(c_{i}\cdot {\boldsymbol {H_{i}}})=\sum _{j\in S}(c_{j}\cdot {\boldsymbol {H_{j}}})+\sum _{j\notin S}(c_{j}\cdot {\boldsymbol {H_{j}}})={\boldsymbol {0}}}$ ${\displaystyle {\boldsymbol {c'}}}$ ${\displaystyle c_{j}'=0}$ ${\displaystyle j\notin S}$ ${\displaystyle {\boldsymbol {c'}}\in C}$ ${\displaystyle {\boldsymbol {H}}\cdot {\boldsymbol {c'}}^{T}={\boldsymbol {0}}}$ ${\displaystyle d\leq wt({\boldsymbol {c'}})}$ ${\displaystyle {\boldsymbol {H}}}$

例: ハミング符号

ハミング符号は、誤り訂正を目的として開発された最初の線形符号であり、デジタル通信システムで広く利用されています。任意の正の整数 に対して、ハミング符号が存在します。 であるため、このハミング符号は1ビットの誤りを訂正できます。 ${\displaystyle r\geq 2}$ ${\displaystyle [2^{r}-1,2^{r}-r-1,3]_{2}}$ ${\displaystyle d=3}$

例:次の生成行列とパリティ検査行列を持つ線形ブロック コードはハミング コードです。 ${\displaystyle [7,4,3]_{2}}$

${\displaystyle {\boldsymbol {G}}={\begin{pmatrix}1&0&0&0&1&1&0\\0&1&0&0&0&1&1\\0&0&1&0&1&1&1\\0&0&0&1&1&0&1\end{pmatrix}},}$ ${\displaystyle {\boldsymbol {H}}={\begin{pmatrix}1&0&1&1&1&0&0\\1&1&\ 1&0&0&1&0\\0&1&1&1&0&0&1\end{pmatrix}}}$

例: アダマール符号

アダマール符号は線形符号であり、多くの誤りを訂正できます。アダマール符号は列ごとに構成できます。列とは、整数 の2進表現のビットです（次の例を参照）。アダマール符号は最小距離を持つため、誤りを訂正できます。 ${\displaystyle [2^{r},r,2^{r-1}]_{2}}$ ${\displaystyle i^{th}}$ ${\displaystyle i}$ ${\displaystyle 2^{r-1}}$ ${\displaystyle 2^{r-2}-1}$

例: 次の生成行列を持つ線形ブロック コードは、アダマール コード です。 ${\displaystyle [8,3,4]_{2}}$ ${\displaystyle {\boldsymbol {G}}_{\mathrm {Had} }={\begin{pmatrix}0&0&0&0&1&\ 1&1&1\\0&0&1&1&0&0&1&1\\0&1&0&1&0&1&0&1\end{pmatrix}}}$

アダマール符号はリード・ミュラー符号の特殊なケースです。 から最初の列（すべてゼロの列）を取り除くと、ハミング符号の双対符号である単体符号が得られます。 ${\displaystyle {\boldsymbol {G}}_{\mathrm {Had} }}$ ${\displaystyle [7,3,4]_{2}}$

最近傍アルゴリズム

パラメータdは、符号の誤り訂正能力と密接に関係しています。以下の構成/アルゴリズムは、このことを示しています（最近傍復号アルゴリズムと呼ばれます）。

入力:受信したベクトルv${\displaystyle \mathbb {F} _{q}^{n}.}$

出力:に最も近い 内のコードワード（存在する場合）。 ${\displaystyle w}$ ${\displaystyle C}$ ${\displaystyle v}$

• から始めて、次の 2 つの手順を繰り返します。${\displaystyle t=0}$
• 受信した単語 の周りの(ハミング)半径 の球の元を列挙します(と表記) 。 ${\displaystyle t}$ ${\displaystyle v}$ ${\displaystyle B_{t}(v)}$
  • の各 について、に含まれるかどうかを確認します。 含まれる場合、を解として返します。${\displaystyle w}$ ${\displaystyle B_{t}(v)}$ ${\displaystyle w}$ ${\displaystyle C}$ ${\displaystyle w}$
• 増分します。列挙が完了し、解決策が見つからなかった場合にのみ失敗します。${\displaystyle t}$ ${\displaystyle t>(d-1)/2}$

の各に対して に最大で 1 つのコードワードが存在する場合、線形 は -誤り訂正可能であると言えます。 ${\displaystyle C}$ ${\displaystyle t}$ ${\displaystyle B_{t}(v)}$ ${\displaystyle v}$ ${\displaystyle \mathbb {F} _{q}^{n}}$

一般的な表記法

一般的に、符号は文字Cで表記されることが多く、長さn、階数 kの符号（つまり、基底にn 個の符号語があり、生成行列にk行がある符号）は、一般的に ( n ,  k ) 符号と呼ばれます。線形ブロック符号は、しばしば [ n ,  k ,  d ] 符号と表記されます。ここで、 d は任意の 2 つの符号語間の最小ハミング距離を表します。

（[ n ,  k ,  d ]表記は、長さn、サイズM（つまり、M個のコードワードを持つ）、最小ハミング距離dの非線形コードを表すために使用される( n ,  M ,  d )表記と混同しないでください。）

シングルトン境界

補題（シングルトン境界）：すべての線形[ n、k、d ]コードCは次式を満たします。 ${\displaystyle k+d\leq n+1}$

パラメータがk  + d  =  n  + 1を満たす符号Cは、最大距離分離可能符号、またはMDSと呼ばれます。このような符号が存在する場合、それはある意味で最良の符号と言えます。

C ₁とC _{2 が長さ}nの2つの符号であり、対称群S _nに順列pが存在し、 C ₁に( c ₁ ,..., c _n ) が存在する場合とC _{2に (} c _{p (1)} ,..., c _{p ( n )} ) が存在する場合に限り、 C ₁とC _2は順列同値であるといえる。より一般的には、C _1をC ₂に同型に送信する単項式行列が存在する場合、C 1_とC 2_は同値であるといえる。 ${\displaystyle n\times n}$ ${\displaystyle M\colon \mathbb {F} _{q}^{n}\to \mathbb {F} _{q}^{n}}$

補題: 任意の線形コードは、標準形式のコードと置換等価である。

ボニソリの定理

コードは、定数dが存在し、コードの異なるコードワードの任意の2つの間の距離がdに等しい場合にのみ、等距離であると定義されます。^{[4] 1984年にArrigo Bonisoliは有限体上の線形1重みコードの構造を決定し、すべての等距離線形コードは}双対ハミングコードのシーケンスであることを証明しました。^[5]

例

線形コードの例としては次のようなものがあります。

• 繰り返しコード
• パリティコード
• 巡回コード
• ハミングコード
• Golayコード（バイナリバージョンと3進バージョンの両方）
• 多項式符号（ BCH符号がその一例）
• リード・ソロモン符号
• リード・ミュラー符号
• 代数幾何学コード
• バイナリゴッパコード
• 低密度パリティ検査符号
• エクスパンダーコード
• 多次元パリティチェックコード
• トーリックコード
• ターボコード
• ローカルで回復可能なコード

一般化

非体アルファベット上のハミング空間も考察されており、特に有限環上、特にZ ₄上のガロア環が注目されている。これにより、ベクトル空間の代わりにモジュールが、線形符号の代わりに環線形符号（部分モジュールで識別される）が生成される。この場合に使用される典型的なメトリックはリー距離である。ハミング距離を持つ（すなわちGF(2 ^{2 m} )）とリー距離を持つ（GR(4,m)とも表記される）の間にはグレイ等長変換が存在する。その主な魅力は、 上の線形ではないいくつかの「良い」符号と、からの環線形符号の像との間の対応を確立することである。^{[6] [7] [8]}${\displaystyle \mathbb {Z} _{2}^{2m}}$ ${\displaystyle \mathbb {Z} _{4}^{m}}$ ${\displaystyle \mathbb {Z} _{2}^{2m}}$ ${\displaystyle \mathbb {Z} _{4}^{m}}$

一部の著者は、このような環上の符号を単に線形符号とも呼んでいる。^[9]

参照

• デコード方法

参考文献

1. William E. RyanとShu Lin (2009). Channel Codes: Classical and Modern . Cambridge University Press. p. 4. ISBN 978-0-521-84868-8。
2. MacKay, David, JC (2003). 情報理論、推論、学習アルゴリズム(PDF) . Cambridge University Press . p. 9. Bibcode :2003itil.book.....M. ISBN 9780521642989線形ブロック符号では、追加ビットは元のビットの線形関数であり、これらの追加ビットはパリティチェックビットと呼ばれる。${\displaystyle N-K}$ ${\displaystyle K}$
3. Thomas M. CoverとJoy A. Thomas (1991). 『情報理論の要素』John Wiley & Sons, Inc. pp. 210–211. ISBN 978-0-471-06259-2。
4. エツィオン、トゥヴィ;ラヴィブ、ネタネル (2013)。 「グラスマン語における等距離コード」。arXiv : 1308.6231 [math.CO]。
5. Bonisoli, A. (1984). 「すべての等距離線形符号は双対ハミング符号の列である」. Ars Combinatoria . 18 : 181–186 .
6. Marcus Greferath (2009). 「環線形符号理論入門」. Massimiliano Sala, Teo Mora, Ludovic Perret, Shojiro Sakata, Carlo Traverso (編). Gröbner Bases, Coding, and Cryptography . Springer Science & Business Media. ISBN 978-3-540-93806-4。
7. 「数学百科事典」www.encyclopediaofmath.org .
8. JH van Lint (1999).符号理論入門（第3版）. Springer. 第8章 ℤ4以上の_符号. ISBN 978-3-540-64133-9。
9. ST Dougherty、J.-L. Kim、P. Sole (2015). 「符号理論における未解決問題」。Steven Dougherty、Alberto Facchini、Andre Gerard Leroy、Edmund Puczylowski、Patrick Sole (編) 『非可換環とその応用』 アメリカ数学会、p. 80. ISBN 978-1-4704-1032-2。

参考文献

• JF Humphreys; MY Prest (2004). Numbers, Groups and Codes (第2版). Cambridge University Press. ISBN 978-0-511-19420-7。第 5 章では、線形符号の主題について (この記事よりも) より穏やかな入門が行われます。

外部リンク

• q-aryコード生成プログラム
• コード テーブル: さまざまなタイプのコードのパラメーターの境界、IAKS、Fakultät für Informatik、Universität Karlsruhe (TH)]。オンラインの最適なバイナリ コードの最新テーブルには、非バイナリ コードも含まれています。
• Z4 コードのデータベース オンライン、最適な Z4 コードの最新データベース。