線型符号

線型符号（せんけいふごう、英: Linear code）は、誤り検出訂正に使われるブロック符号の種類を指す。線型符号は他の符号に比べて、符号化と復号が効率的であるという特徴を持つ（例えば、シンドローム復号など）。

線型符号は、伝送路上を記号列（ビット列）を転送する方法に適用される。従って通信中に誤りが発生しても、一部の誤りを受信側で検出することができる。線型符号の「符号」は記号のブロックであり、本来の送るべき記号列よりも多くの記号（ビット）を使って符号化されている。長さ n の線型符号は、n 個の記号を含むブロックを転送する。例えば、"(7,4)" ハミング符号は2進線型符号であり、4ビットの値を表すのに 7ビットの値を用いる。このようにすると、受信側はブロック当たり 2ビットまでの誤りを検出できる。4ビットの値は16種類あるので、(7,4) ハミング符号の「ランク; rank」は 16 となる。

形式的定義

長さ n、ランク k の線型符号は、次数 k のベクトル空間 $\mathbb{F}_q^n$ の線型部分空間 C であり、ここで $\mathbb{F}_q$ は q 個の要素の有限体である。このような q 個のパラメータの符号を q-ary 符号と呼ぶ（例えば、q = 5 なら 5-ary 符号）。q = 2 または q = 3 であるとき、その符号を2進符号または3進符号と呼ぶ。

特性

$\mathbb{F}_q^n$ の線型部分空間であるので、符号全体である C は符号語の最小集合の部分空間（linear span）として表される（線型代数学における「基底; basis」）。これら基底符号語は、符号 C の生成行列と呼ばれる行列の行で示されることが多い。

部分空間の定義より、ある符号語 c₀ と他の符号語 c ≠ c₀ の最小ハミング距離は定数となる。C における2つの符号語の差 c − c₀ も符号語であるため、また d(c, c₀) = d(c − c₀, 0) であることから、次が成り立つ。

$\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).$

一般的な記法

符号は一般に C で表される。長さ n、ランク k の線型符号（基底として、生成行列に k 個の符号語を持つ）の最小ハミング重みが d であるとき、これを (n, k, d) 符号と記する。

なお、長さ n、サイズ r、最小ハミング距離 d の非線型符号を [n, r, d] と表記することもあるが、これと上記の記法を混同しないよう注意が必要である。

例

以下に線型符号の例を挙げる。

• 反復符号
• 巡回符号
• ハミング符号
• ゴレイ符号
• リード・ソロモン符号
• BCH符号
• リード・マラー符号
• ゴッパ符号

利用

2進線型符号は電子機器や記憶媒体などで広く使われている。例えば、コンパクトディスクにデジタルデータを格納する際には、リード・ソロモン符号が使われている。

外部リンク

• q-ary Code Generator Program
• Compute parameters of linear codes - 線型誤り訂正符号のパラメータを計算し生成するオンラインインタフェース
• Code Tables: Bounds on the parameters of various types of codes, IAKS, Fakultät für Informatik, Universität Karlsruhe (TH).