概要
縁があって Berlekamp-Massey アルゴリズムについて調べたら、深淵にはまったのでできるだけ備忘録的にまとめてみました。
前回は
Berlekamp-Massey アルゴリズムは、一番短いLinear feedback shift register (LFSR) を、与えられたバイナリの出力シークエンスから求めるアルゴリズムである。
また、このアルゴリズムは、体上のlinearly recurrent sequenceを与えられた時に、それのminimal な多項式を見つけることができる。
というBerlemap-Masseyアルゴリズムの定義について理解しました。
ウィキペディア先生の解説をもうちょい下ってみます。
内容
The Berlekamp–Massey algorithm is an alternative to the Reed–Solomon Peterson decoder for solving the set of linear equations.
Berlekamp-Massey アルゴリズムは、線形方程式のセットを解くための、リード・ソロモンデコーダーの代替となる。
これについて考えてみます。
リード・ソロモン符号と復号
正直、このウィキペディア記事がわかりやすすぎて素晴らしいので、そちらを見て欲しいのですが、簡単にまとめます。
まず何がしたいのかと言うと、ある信号が飛んできたときに、それが正しいかどうか判定したい、また、信号がエラーを含んでいるとすればそれがどこに含まれ、どうやればエラーを訂正できるか。という問題に対して、
符号化
送る情報（ビット列）をシンボルと呼ばれるブロックに分ける。例えば１ブロック１バイトであれば８ビットです。この時、８ビットを１シンボルとした場合には、そのシンボルの情報を、８次の最小多項式から定義される拡大体であるガロア体を定義し、１シンボルの情報をこのガロア体を用いて１つの生成多項式として書きます。さらに、例えばこの符号化を２シンボルのエラーに対応させたいとすると、その望みのシンボル数に対応した生成多項式を生成します。
まとめると、
- リードソロモン符号と呼ばれるものを有限体であるガロア体を用いて生成し、
- 送りたい情報を符号化します（この多項式のことを情報多項式と呼ぶ。）
- それに付随して生成多項式というものも生成、送信します。
ここまでが符号化であり、データ受信者はこれを元にエラーを訂正します。（復号）
復号
情報を受け取った側はエラーを含んでいる可能性のある情報を受け取っているわけですが、その訂正（復号）は、いくつかやり方があるようで、そのなかでもピーターソン法を用いると、
- シンドロームという数値をガロア体の根と受け取った多項式から算出します。
- シンドロームを元に作った行列の行列式を計算し、誤りを含むシンボルの数をまず断定します。
- その後、誤りを含むシンボルの位置について断定します。
- 位置を断定した後は、連立一次方程式を用いて、断定したエラーを含む次数の項を補正する数値を算出します。
- もともと受け取った情報（多項式に）この補正数値を対応した次数の係数とした補正多項式を足し合わせ、エラーを訂正します。
おわりに
これらをもとに、Berlekamp-Masseyアルゴリズムについてもう少し踏み込んで見たいとおもいます。