線型符号

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

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

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

定義[編集]

q 個の元からなる有限体  F = \mathbb{F}_q をとる。このとき n 次元線型空間 Fn部分空間 C線型符号という。また k = dimF C とするとき、線型符号 C のことを (n, k) 線型符号という[1]k 次元部分空間 C はその基底 g1, …, gkFn を指定すれば定まる。これらを並べた k×n 行列 G = (g1t, …, gkt)t を線型符号 C生成行列という。定義から


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

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


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

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


 G = (I | P), \quad H = (-P^t | I)

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

シンドローム復号[編集]

(n, k) 線型符号を C 、 そのパリティ検査行列を H とする。受信語 yFn に対して yHtシンドロームという。剰余空間 Fn/C完全代表系 {v1, …, vqnk} は各 vi が剰余類 vi + C のなかで最小の重みをもつとき、コセット・リーダという。このとき受信語 yFnyHt = vHt となるコセット・リーダ v をとると、符号語 yvC に復号される。これをシンドローム復号という。

[編集]

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


 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) になったとすると、そのシンドロームは yHt = (0, 1, 1) である。そこで上のシンドローム表から対応するコセット・リーダ v = (1, 0, 0, 0, 0, 0, 0) を読み取ることで xG = yv と復号できる。生成行列 G は組織符号形式だったのでもとの情報系列はその先頭 (0, 1, 0, 1) を読み取ることでわかる。この符号 C は歴史的にはリチャード・ハミングによって1947年に初めて発見された誤り訂正符号のひとつである[2]

特性[編集]

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

利用[編集]

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


 1a_1 + 2a_2 + \dotsb + 10a_{10} \equiv 0 \pmod{11}

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

脚注[編集]

  1. ^ (n, k, d) 線型符号ということもある。ここで d は最小距離を表す。なお、長さ n、サイズ r、最小距離 d の非線型符号を [nrd] と表記することもあるが、これと混同しないよう注意が必要である。
  2. ^ ジョーンズ & ジョーンズ 2006, 例6.5, 例7.19, 例7.22.
  3. ^ ユステセン & ホーホルト 2005, 補題1.2.1.
  4. ^ ジョーンズ & ジョーンズ 2006, 定理7.23.
  5. ^ ユステセン & ホーホルト 2005, 定理1.2.1.
  6. ^ ジョーンズ & ジョーンズ 2006, 演習問題6.21.

参考文献[編集]

  • ジョーンズ, G. A.、ジョーンズ, J. M. 『情報理論と符号理論』 シュプリンガー・ジャパン、2006年ISBN 4-431-71216-X
  • ユステセン, イエルン、ホーホルト, トム 『誤り訂正符号入門』 森北出版、2005年、第1版。ISBN 4-627-81711-8

関連項目[編集]

外部リンク[編集]