線形コード

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

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

長さnで次元kの線形符号は、q個の要素を持つ有限体であるベクトル空間の次元kの線形部分空間Cです。このような符号は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}}$

各座標は、伝送エラーの確率が小さい「ノイズの多いチャネル」（バイナリ対称チャネル）を介して伝送される「ビット」を表すため、標準基底を与える必要があります。他の基底を使用すると、このモデルは使用できず、ハミング メトリックは、伝送中のエラーの数を、期待どおりに測定しません。 ${\displaystyle \mathbb {F} _{q}^{n}}$

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

核がCである線形関数を表す行列Hは、 Cの検査行列(またはパリティ検査行列)と呼ばれます。同様に、 Hはヌル空間がCである行列です。Cが標準形式の生成行列Gを持つコードである場合、 はC の検査行列です。H によって生成されるコードはCのデュアル コードと呼ばれます。G が行列であり、H が行列であることが確認できます。 ${\displaystyle \phi :\mathbb {F} _{q}^{n}\to \mathbb {F} _{q}^{nk}}$${\displaystyle {\boldsymbol {G}}=[I_{k}|P]}$${\displaystyle {\boldsymbol {H}}=[-P^{T}|I_{nk}]}$${\displaystyle k\times n}$${\displaystyle (nk)\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}}}|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}}_{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}}_{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 が存在し、その置換 p に対して C ₁に(c ₁ ,...,c _n ) が存在する場合とC _{2に (c p(1)} ,...,c _p(n) )が存在する場合に限り、C ₁と C _{2 は}置換同値であるといいます。より一般的には、C _{1 をC 2}に同型に送信する単項式行列が存在する場合、C ₁と C _{2 は}同値であるといいます。 ${\displaystyle n\times n}$ ${\displaystyle M\colon \mathbb {F} _{q}^{n}\to \mathbb {F} _{q}^{n}}$

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

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

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

非体アルファベット上のハミング空間も考慮されており、特に有限環上、特にZ ₄上のガロア環が注目されている。これにより、ベクトル空間の代わりにモジュールが、線形コードの代わりにリング線形コード（サブモジュールで識別される）が生成される。この場合に使用される典型的なメトリックはリー距離である。ハミング距離を持つ(すなわち GF(2 ^2m )) とリー距離を持つ (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]

• デコード方法

• JF Humphreys、MY Prest (2004)。Numbers , Groups and Codes (第2版)。ケンブリッジ大学出版局。ISBN 978-0-511-19420-7。第 5 章には、線形符号という主題についての (この記事よりも) より穏やかな入門が含まれています。

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