線型符号のソースを表示

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

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

== 定義 ==
''q'' 個の元からなる[[有限体]] <math> F = \mathbb{F}_q</math> をとる。このとき ''n'' 次元[[線型空間]] ''F<sup>n</sup>'' の[[部分空間]] ''C'' を'''線型符号'''という。また ''k'' = dim<sub>''F''</sub> ''C'' とするとき、線型符号 ''C'' のことを (''n'', ''k'') 線型符号という<ref>(''n'', ''k'', ''d'') 線型符号ということもある。ここで ''d'' は最小[[ハミング距離|距離]]を表す。なお、長さ ''n''、サイズ ''r''、最小距離 ''d'' の非線型符号を [''n'',&nbsp;''r'',&nbsp;''d''] と表記することもあるが、これと混同しないよう注意が必要である。</ref>。''k'' 次元部分空間 ''C'' はその基底 ''g''<sub>1</sub>, &hellip;, ''g''<sub>''k''</sub> &isin; ''F<sup>n</sup>'' を指定すれば定まる。これらを並べた ''k''&times;''n'' 行列 ''G'' = (''g''<sub>1</sub><sup>''t''</sup>, &hellip;, ''g''<sub>''k''</sub><sup>''t''</sup>)<sup>''t''</sup> を線型符号 ''C'' の'''生成行列'''という。定義から
:<math>
 C = \{\, xG \mid x \in F^k \,\}
</math>
が成り立つ。また ''k'' 次元部分空間 ''C'' は[[連立一次方程式]]で指定しても定まる。そこで
:<math>
 C = \{\, y \in F^n \mid yH^t = 0 \,\}
</math>
となる(''n'' &minus; ''k'')&times;''n'' 行列 ''H'' を線型符号 ''C'' の'''パリティ検査行列'''という。定義から ''GH<sup>t</sup>'' = 0 が成り立つ。これらの行列は適当に線型符号 ''C'' の基底を取りなおすことによって
:<math>
 G = (I | P), \quad H = (-P^t | I)
</math>
の形にできる。このような ''G'', ''H'' を'''組織符号形式'''という。このとき符号化前の ''k'' 個の記号からなる情報系列がそのまま符号語に現れているので、容易に復号ができる。符号語の残り ''n'' &minus; ''k'' 個の記号はパリティ検査記号と呼ばれる。

== シンドローム復号 ==
(''n'', ''k'') 線型符号を ''C'' 、 そのパリティ検査行列を ''H'' とする。受信語 ''y'' &isin; ''F<sup>n</sup>'' に対して ''yH<sup>t</sup>'' を'''シンドローム'''という。[[商線型空間|剰余空間]] ''F<sup>n</sup>''/''C'' の[[完全代表系]] {''v''<sub>1</sub>, &hellip;, ''v''<sub>''q''<sup>''n'' &minus; ''k''</sup></sub>} は各 ''v<sub>i</sub>'' が剰余類 ''v<sub>i</sub>'' + ''C'' のなかで最小の[[ハミング重み|重み]]をもつとき、'''コセット・リーダ'''という。このとき受信語 ''y'' &isin; ''F<sup>n</sup>'' は ''yH<sup>t</sup>'' = ''vH<sup>t</sup>'' となるコセット・リーダ ''v'' をとると、符号語 ''y'' &minus; ''v'' &isin; ''C'' に復号される。これを'''シンドローム復号'''という。

== 例 ==
次の行列 ''G'' を生成行列、あるいは ''H'' をパリティ検査行列とする2元体 <math>\mathbb{F}_2</math>上の (7, 4) 線型符号を ''C'' とおく。この行列 ''G'', ''H'' は組織符号形式である。またコセット・リーダ ''v'' とそのシンドローム ''vH<sup>t</sup>'' は以下の表のようになる。
:<math>
 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}
</math>
<!-- 以下のシンドローム表はGAPによって次のように計算されたものを適当に並び替えたものです．
gap> LoadPackage("GUAVA");;
gap> C := GeneratorMatCode([           
> [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],            
> ], "C", GF(2));;
> Display(SyndromeTable(C));   
-->
{| class="wikitable" style="text-align:center; width:50%"
|+ (7, 4) 線型符号 ''C'' のシンドローム表
! コセット・リーダ ''v'' !! シンドローム ''vH<sup>t</sup>''
|-
| (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<sup>t</sup>'' = (0, 1, 1) である。そこで上のシンドローム表から対応するコセット・リーダ ''v'' = (1, 0, 0, 0, 0, 0, 0) を読み取ることで ''xG'' = ''y'' &minus; ''v'' と復号できる。生成行列 ''G'' は組織符号形式だったのでもとの情報系列はその先頭 (0, 1, 0, 1) を読み取ることでわかる。この符号 ''C'' は歴史的には[[リチャード・ハミング]]によって1947年に初めて発見された[[誤り訂正符号]]のひとつである{{sfn|ジョーンズ|ジョーンズ|2006|loc=例6.5, 例7.19, 例7.22}}。

== 特性 ==
* 線型符号の最小[[ハミング距離|距離]] ''d'' = min<sub>''x'' &ne; ''y''</sub>''d''(''x'', ''y'') と最小[[ハミング重み|重み]] ''w'' = min<sub>''x'' &ne; 0</sub> w(''x'') は一致する{{sfn|ユステセン|ホーホルト|2005|loc=補題1.2.1}}。
* (''n'', ''k'') 線型符号の最小距離 ''d'' は不等式 ''d'' &le; ''n'' &minus; ''k'' + 1 を満たす{{sfn|ジョーンズ|ジョーンズ|2006|loc=定理7.23}}。これをシングルトンの限界式という。
* (''n'', ''k'') 線型符号は ''t'' < ''d''/2 個の誤りを訂正できる{{sfn|ユステセン|ホーホルト|2005|loc=定理1.2.1}}。

== 利用 ==
2進線型符号は電子機器や記憶媒体などで広く使われている。例えば、[[コンパクトディスク]]にデジタルデータを格納する際には、[[リード・ソロモン符号]]が使われている。
また10桁の[[ISBN]]''a''<sub>1</sub> &hellip; ''a''<sub>10</sub>は（X = 10と見做して）11元体上の[[一次方程式]]
:<math>
 1a_1 + 2a_2 + \dotsb + 10a_{10} \equiv 0 \pmod{11}
</math>
で定まる線型符号である{{sfn|ジョーンズ|ジョーンズ|2006|loc=演習問題6.21}}。

== 脚注 ==
{{reflist|2}}

== 参考文献 ==
* {{cite book
|和書
|last1      = ジョーンズ
|first1     = G. A.
|last2      = ジョーンズ
|first2     = J. M.
|year       = 2006
|title      = 情報理論と符号理論
|publisher  = シュプリンガー・ジャパン
|isbn       = 4-431-71216-X
|ref        = harv
}}
* {{cite book
|和書
|last1      = ユステセン
|first1     = イエルン
|last2      = ホーホルト
|first2     = トム
|year       = 2005
|title      = 誤り訂正符号入門
|edition    = 第1版
|publisher  = 森北出版
|isbn       = 4-627-81711-8
|ref        = harv
}}

== 関連項目 ==
{{div col|cols=2}}
* [[反復符号]]
* [[巡回符号]]
* [[ハミング符号]]
* [[ゴレイ符号]]
* [[リード・ソロモン符号]]
* [[BCH符号]]
* [[リード・マラー符号]]
* [[ゴッパ符号]]
{{div col end}}

== 外部リンク ==
* [http://jason.mchu.com/QCode/index.html q-ary Code Generator Program]
* [http://ipsit.bu.edu/comp.html Compute parameters of linear codes] - 線型誤り訂正符号のパラメータを計算し生成するオンラインインタフェース
* [http://www.codetables.de/ Code Tables: Bounds on the parameters of various types of codes], ''IAKS, Fakultät für Informatik, Universität Karlsruhe (TH)''. 

{{DEFAULTSORT:せんけいふこう}}
[[Category:誤り検出訂正]]
[[Category:数学に関する記事]]
[[Category:体論]]
[[Category:符号理論]]
[[Category:有限体]]