線型符号

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

線型符号は、伝送路上を記号列を転送する方法に適用される。したがって通信中に誤りが発生しても、一部の誤りを受信側で検出することができる。線型符号の「符号」は記号のブロックであり、本来の送るべき記号列よりも多くの記号を使って符号化されている。長さ n の線型符号は、n 個の記号を含むブロックを転送する。

定義

q 個の元からなる有限体 ${\displaystyle F=\mathbb {F} _{q}}$ をとる。このとき n 次元線型空間 Fⁿ の部分空間 C を線型符号という。また k = dim_F C とするとき、線型符号 C のことを (n, k) 線型符号という^[1]。k 次元部分空間 C はその基底 g₁, …, g_k ∈ Fⁿ を指定すれば定まる。これらを並べた k×n 行列 G = (g₁^t, …, g_k^t)^t を線型符号 C の生成行列という。定義から

${\displaystyle C=\{\,xG\mid x\in F^{k}\,\}}$

が成り立つ。また k 次元部分空間 C は連立一次方程式で指定しても定まる。そこで

${\displaystyle C=\{\,y\in F^{n}\mid yH^{t}=0\,\}}$

となる(n − k)×n 行列 H を線型符号 C のパリティ検査行列という。定義から GH^t = 0 が成り立つ。これらの行列は適当に線型符号 C の基底を取りなおすことによって

${\displaystyle G=(I|P),\quad H=(-P^{t}|I)}$

の形にできる。このような G, H を組織符号形式という。このとき符号化前の k 個の記号からなる情報系列がそのまま符号語に現れているので、容易に復号ができる。符号語の残り n − k 個の記号はパリティ検査記号と呼ばれる。

シンドローム復号

(n, k) 線型符号を C 、 そのパリティ検査行列を H とする。受信語 y ∈ Fⁿ に対して yH^t をシンドロームという。剰余空間 Fⁿ/C の完全代表系 {v₁, …, v_{q^{n − k}}} は各 v_i が剰余類 v_i + C のなかで最小の重みをもつとき、コセット・リーダという。このとき受信語 y ∈ Fⁿ は yH^t = vH^t となるコセット・リーダ v をとると、符号語 y − v ∈ C に復号される。これをシンドローム復号という。

例

次の行列 G を生成行列、あるいは H をパリティ検査行列とする2元体 ${\displaystyle \mathbb {F} _{2}}$上の (7, 4) 線型符号を C とおく。この行列 G, H は組織符号形式である。またコセット・リーダ v とそのシンドローム vH^t は以下の表のようになる。

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

(7, 4) 線型符号 C のシンドローム表

コセット・リーダ v	シンドローム vHt
(0, 0, 0, 0, 0, 0, 0)	(0, 0, 0)
(1, 0, 0, 0, 0, 0, 0)	(0, 1, 1)
(0, 1, 0, 0, 0, 0, 0)	(1, 0, 1)
(0, 0, 1, 0, 0, 0, 0)	(1, 1, 0)
(0, 0, 0, 1, 0, 0, 0)	(1, 1, 1)
(0, 0, 0, 0, 1, 0, 0)	(1, 0, 0)
(0, 0, 0, 0, 0, 1, 0)	(0, 1, 0)
(0, 0, 0, 0, 0, 0, 1)	(0, 0, 1)

たとえば送信したい情報系列を x = (0, 1, 0, 1) とすれば xG = (0, 1, 0, 1, 0, 1, 0) と符号化される。ここで符号語 xG のうち末尾の (0, 1, 0) がパリティ検査記号である。通信中に先頭で誤りが起こり、受信語が y = (1, 1, 0, 1, 0, 1, 0) になったとすると、そのシンドロームは yH^t = (0, 1, 1) である。そこで上のシンドローム表から対応するコセット・リーダ v = (1, 0, 0, 0, 0, 0, 0) を読み取ることで xG = y − v と復号できる。生成行列 G は組織符号形式だったのでもとの情報系列はその先頭 (0, 1, 0, 1) を読み取ることでわかる。この符号 C は歴史的にはリチャード・ハミングによって1947年に初めて発見された誤り訂正符号のひとつである^[2]。

特性

• 線型符号の最小距離 d = min_{x ≠ y}d(x, y) と最小重み w = min_{x ≠ 0} w(x) は一致する^[3]。
• (n, k) 線型符号の最小距離 d は不等式 d ≤ n − k + 1 を満たす^[4]。これをシングルトンの限界式という。
• (n, k) 線型符号は t < d/2 個の誤りを訂正できる^[5]。

利用

2進線型符号は電子機器や記憶媒体などで広く使われている。例えば、コンパクトディスクにデジタルデータを格納する際には、リード・ソロモン符号が使われている。 また10桁のISBNa₁ … a₁₀は（X = 10と見做して）11元体上の一次方程式

${\displaystyle 1a_{1}+2a_{2}+\dotsb +10a_{10}\equiv 0{\pmod {11}}}$

で定まる線型符号である^[6]。