線形帰還シフトレジスタ

線形帰還シフトレジスタ（せんけいきかんシフトレジスタ、英: linear feedback shift register, LFSR）は、入力ビットが直前の状態の線形写像になっているシフトレジスタである。 値域が単一のビットとなる線形写像は、XORおよびXORの否定だけである。したがって、線形帰還シフトレジスタとは、その値を構成するビット列の一部の排他的論理和を入力ビットとするシフトレジスタである。 LFSR の初期値をシードと呼ぶ。レジスタの動作は決定的であるため、レジスタが生成する値の列はその状態によって完全に決定される。同様に、レジスタの取りうる状態は有限個であるため、最終的に周期的動作になる。しかし、帰還関数をうまく設定したLFSRは乱数のようなビット列を生成し、その周期も非常に長い。 LFSRの用途としては、擬似乱数生成、擬似ノイズ生成、高速デジタルカウンタ、白色化などがある。LFSR にはハードウェアによる実装もソフトウェアによる実装もある。