概要
縁があって Berlekamp-Massey アルゴリズムについて調べたら、色々面白かったのでまとめました。
内容
Berlekamp-Massey アルゴリズムは、一番短いLinear feedback shift register (LFSR) を、与えられたバイナリの出力シークエンスから求めるアルゴリズムである。
また、このアルゴリズムは、体上のlinearly recurrent sequenceを与えられた時に、それのminimal な多項式を見つけることができる。
はい、１つ１つ追っていきましょう。
シフトレジスタについて
まず、シフトレジスタについて簡単に解説します。こちらのサイトがなかなか詳細に解説していました。すばらしい。
こちらを読むとわかるのですが、シフトレジスタを理解するのに、Dフリップフロップと、マルチプレクサについて知る必要があります。
Dフリップフロップは、簡単に言うと、１ビットの情報を記録するメモリです。Dフリップフロップは、D信号の論理（０か１かを）をクロックがLからHに遷移した時に記憶し、クロックの周波数後にQに出力として吐き出す働きをします。
マルチプレクサは、セレクタとも呼ばれ、Sの外部入力がLかHかによって、AもしくはBの入力をYに渡すかを決定します。例えが、SがLの時はBの論理をYに渡し、Hの時はAの論理をYに渡します。
これを踏まえて、例えば４ビットのシフトレジスタには、２つの異なる動作があります。
１つ目は、シフトレジスタの１つの端子に、Hを入力してシリアル入力モードにした場合で、２つ目はLを入力してパラレル入力モードにした場合です。
-
シリアル入力モードの場合
クロックが進むごとに、各出力がシフトしながら出力されます。たとえば、出力が４つあり、Q1, Q2, Q3, Q4 のときは、Q2の出力が１つ前のクロックでのQ1の値、Q3の出力は１つ前のクロックでのQ2の値、。。。という風にです。
このシフト動作を、シフトレジスタに記憶している数値への演算と考える場合、この演算をシフト演算と呼びアmす。 -
パラレル入力モードにした場合
クロック信号の立ち上がり時に、各Q信号を取り込み、それをD信号に受け渡す、単なるパラレル入力パラレル出力のレジスタ（ストレージレジスタ）として働きます。
LFSR (Linear Feedback Shift Register)
LFSRは、上のシフトレジスタで、入力が１つ前の状態の線形変換で構成されているものです。１ビットに対して一番よく使われる線形演算はXORです。
LFSRにへの初期入力のことをシードといい、LFSRのオペレーションが決定的、つまりある時刻での状態が決まると、その次の状態が一意に決まると言う特性があります。また、LFSRが有限個の状態を持っていることを考慮すると、LFSRの状態にはある周期がありますが、うまくフィードバック関数を選ぶことでその周期を「長く」取ることができます。これを利用し、LFSRは擬ランダム数の生成や、擬ノイズの生成などに使われます。
Berlekamp-Massey アルゴリズム に戻ってみる。
Berlekamp-Massey アルゴリズムは、一番短いLinear feedback shift register (LFSR) を、与えられたバイナリの出力シークエンスから求めるアルゴリズムである。
また、このアルゴリズムは、体上のlinearly recurrent sequenceを与えられた時に、それのminimal な多項式を見つけることができる。
まず、LFSRを勉強したことによって、１文目は理解できるようになりました。つまり、出てくる出力シークエンス（シフト演算シークエンス）が与えられた時に、どのようなフィードバックを持ったシフトレジスタが組まれているかを求めるアルゴリズムであると言うことです。
２文目に関しても、線形で回帰的に得られるシークエンスが与えられた時に、これらのシークエンスを解にもつ最小多項式を求めることができる、と言うことです。
回帰シークエンスに関してはウィキペディアに詳細に解説してありますが、簡単にまとめると、$a_t = W(a_0, a_1, ..., a_{t-1})$ で書かれるようなシークエンスのことです。
また、最小多項式についても解説してあります。ここ
おわりに
以上、Berlekamp-Massey アルゴリズムの一番最初の定義についてまとめて見ました。
次は具体的にBerlekamp-Massey アルゴリズムの内容について踏み込んでいけたらと思います。