|
線形帰還シフトレジスタ（せんけいきかんシフトレジスタ、）は、入力ビットが直前の状態の線形写像になっているシフトレジスタである。 値域が単一のビットとなる線形写像は、XORおよびXORの否定だけである。したがって、線形帰還シフトレジスタとは、その値を構成するビット列の一部の排他的論理和を入力ビットとするシフトレジスタである。 LFSR の初期値をシードと呼ぶ。レジスタの動作は決定的であるため、レジスタが生成する値の列はその状態によって完全に決定される。同様に、レジスタの取りうる状態は有限個であるため、最終的に周期的動作になる。しかし、帰還関数をうまく設定したLFSRは乱数のようなビット列を生成し、その周期も非常に長い。 LFSRの用途としては、擬似乱数生成、擬似ノイズ生成、高速デジタルカウンタ、白色化などがある。LFSR にはハードウェアによる実装もソフトウェアによる実装もある。 == フィボナッチ LFSR == LFSRで、次の入力ビットに影響を与えるビットを「タップ (tap)」と呼び、それらの位置を列挙したものをタップシーケンスと呼ぶ。図では、タップシーケンスが 14, 13, 11, 0 である。タップは順次XORされ、その結果が左端にフィードバックされる。 * 入力に影響する出力を「タップ」と呼ぶ（図では黒）。 * 最長LFSRはM系列を生成する。最長LFSRとは、全ビットがゼロという状態以外の全てのとりうる状態（）が周期に現れるLFSRである。（全ビットがゼロの場合、全く変化しない。初期状態として設定しない限り、最長LFSRにおいて自然にそうなることはない） LFSRの生成するビット列は、2進数やグレイコードと見なすことができる。 LFSRのタップシーケンスは2を法とする多項式で表せる。つまり、多項式の各項の係数は1か0である。これを帰還多項式あるいは特性多項式と呼ぶ。例えば、図のようにタップが16番目、14番目、13番目、11番目にあるとき、帰還多項式は次のようになる。 :: 最後に1があるが、これはタップとは対応していない。これは、最初のビットへの入力に対応している（つまり、''x0'' であり、1と等価である）。各項のべき乗部分はタップ位置を表していて、左端から何番目かに対応している。左端は常に入力、右端は常にタップとして連結する。 最長LFSRを構成する多項式（タップシーケンス）の性質を以下に示す。 * LFSRが最長となるのは、タップ数が偶数の場合のみである。非常に長いレジスタであっても2個や4個のタップで十分である。 * タップ集合は互いに素でなければならない。全タップ間の1以外の公約数が存在してはならない。 * LFSRの長さによっては、最長となる複数の多項式が存在する。 * 最長となるタップシーケンスが1つ見つかると、他は自動的に得られる。''n''ビットのLFSRで、タップシーケンス が見つかったとき（0は に対応）、もう1つのタップシーケンスは である。例えば、 に対応するのは である。どちらも最長である。 C/C++ のコーディング例を以下に示す。 uint16_t reg = 0xACE1; uint16_t bit; while(1) このコードでは、左端ビットが1番目の位置である。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「線形帰還シフトレジスタ」の詳細全文を読む 英語版ウィキペディアに対照対訳語「 Linear feedback shift register 」があります。 スポンサード リンク
|