線型符号

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

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

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

形式的定義[編集]

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

特性[編集]

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

部分空間の定義より、ある符号語 c0 と他の符号語 c ≠ c0 の最小ハミング距離は定数となる。C における2つの符号語の差 c − c0 も符号語であるため、また d(c, c0) = d(c − c0, 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 であるとき、これを (nkd) 符号と記する。

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

[編集]

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

利用[編集]

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

外部リンク[編集]

脚注[編集]

  1. ^ Thomas M. Cover and Joy A. Thomas (1991年). Elements of Information Theory. John Wiley & Sons, Inc. pp. 210-211. ISBN 0-471-06259-5.