線形帰還シフトレジスタ
線形帰還シフトレジスタ(せんけいきかんシフトレジスタ、英: linear feedback shift register, LFSR)は、入力ビットが直前の状態の線形写像になっているシフトレジスタである。
値域が単一のビットとなる線形写像は、XORおよびXORの否定だけである。したがって、線形帰還シフトレジスタとは、その値を構成するビット列の一部の排他的論理和を入力ビットとするシフトレジスタである。
LFSR の初期値をシードと呼ぶ。レジスタの動作は決定的であるため、レジスタが生成する値の列はその状態によって完全に決定される。同様に、レジスタの取りうる状態は有限個であるため、最終的に周期的動作になる。しかし、帰還関数をうまく設定したLFSRは乱数のようなビット列を生成し、その周期も非常に長い。
LFSRの用途としては、擬似乱数生成、擬似ノイズ生成、高速デジタルカウンタ、白色化などがある。LFSR にはハードウェアによる実装もソフトウェアによる実装もある。
LFSRで、次の入力ビットに影響を与えるビットを「タップ (tap)」と呼び、それらの位置を列挙したものをタップシーケンスと呼ぶ。図では、タップシーケンスが [16, 14, 13, 11, 0] である。タップは順次XORされ、その結果が左端にフィードバックされる。
入力に影響する出力を「タップ」と呼ぶ(図では黒)。
最長LFSRはM系列を生成する。最長LFSRとは、全ビットがゼロという状態以外の全てのとりうる状態( 2 n − 1 {\displaystyle 2^{n}-1} )が周期に現れるLFSRである。(全ビットがゼロの場合、全く変化しない。初期状態として設定しない限り、最長LFSRにおいて自然にそうなることはない)
LFSRの生成するビット列は、2進数やグレイコードと見なすことができる。
LFSRのタップシーケンスは2を法とする多項式で表せる。つまり、多項式の各項の係数は1か0である。これを帰還多項式あるいは特性多項式と呼ぶ。例えば、図のようにタップが16番目、14番目、13番目、11番目にあるとき、帰還多項式は次のようになる。
x 16 + x 14 + x 13 + x 11 + 1 {\displaystyle x^{16}+x^{14}+x^{13}+x^{11}+1\,}
最後に1があるが、これはタップとは対応していない。