線形帰還シフトレジスタ
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/12/18 14:12 UTC 版)
線形帰還シフトレジスタ（せんけいきかんシフトレジスタ、英: linear feedback shift register, LFSR）は、入力ビットが直前の状態の線形写像になっているシフトレジスタである。
値域が単一のビットとなる線形写像は、XORおよびXORの否定だけである。したがって、線形帰還シフトレジスタとは、その値を構成するビット列の一部の排他的論理和を入力ビットとするシフトレジスタである。
LFSR の初期値をシードと呼ぶ。レジスタの動作は決定的であるため、レジスタが生成する値の列はその状態によって完全に決定される。同様に、レジスタの取りうる状態は有限個であるため、最終的に周期的動作になる。しかし、帰還関数をうまく設定したLFSRは乱数のようなビット列を生成し、その周期も非常に長い。
LFSRの用途としては、擬似乱数生成、擬似ノイズ生成、高速デジタルカウンタ、白色化などがある。LFSR にはハードウェアによる実装もソフトウェアによる実装もある。
フィボナッチ LFSR
LFSRで、次の入力ビットに影響を与えるビットを「タップ (tap)」と呼び、それらの位置を列挙したものをタップシーケンスと呼ぶ。図では、タップシーケンスが [16, 14, 13, 11, 0] である。タップは順次XORされ、その結果が左端にフィードバックされる。
- 入力に影響する出力を「タップ」と呼ぶ（図では黒）。
- 最長LFSRはM系列を生成する。最長LFSRとは、全ビットがゼロという状態以外の全てのとりうる状態（
16ビットのガロアLFSR。黒い番号は上のフィボナッチLFSRと同じ多項式の項に対応しているが、シフト方向が逆である点に注意。このレジスタも全て0状態以外の65535個の最長の状態遷移をする。図に示されている ACE1 の状態の次は E270 となる（16進）。 通常のLFSRと同じ出力シーケンスを得るには、ビット順序を逆にする（図参照）。そうしないとシーケンスが逆転する。なお、LFSRの内部状態は同じである必要はない。図に示したガロアLFSRは、上の図で示したフィボナッチLFSRと同じ出力となる。
- ガロアLFSRでは、全タップの値を使って入力を生成するわけではなく、XORは個別に各タップ位置で行われる。つまり、XOR演算を並列に実行でき、高速化が可能である。
- ソフトウェアで実装すると、ワード全体のビット演算で一度にXORできるので、さらに効率的な実装になる。
以下は32ビットの最長ガロアLFSRをC言語およびC++で実装したものである（unsigned int は32ビットと仮定）。
unsigned int lfsr = 1; unsigned int period = 0; do { lfsr = (lfsr >> 1) ^ (-(lfsr & 1u) & 0xd0000001u); /* taps 32 31 29 1 */ ++period; } while(lfsr != 1u);
次のコードは、図にある16ビットの例である。
unsigned short lfsr = 0xACE1u; unsigned int period = 0; do { lfsr = (lfsr >> 1) ^ (-(short)(lfsr & 1u) & 0xB400u); ++period; } while(lfsr != 0xACE1u);
最長LFSRとなる多項式の例
ビット数 帰還多項式 周期 n
線形帰還シフトレジスタ
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/12/09 18:40 UTC 版)
詳細は「線形帰還シフトレジスタ」を参照 線形帰還シフトレジスタ (Linear Feedback Shift Register, LFSR) はデジタル回路を用いて容易に実装することができる。特性多項式を適切に選択することによって、等頻度性、無相関性及び周期が保障される。乱数としては最長周期を保障するM系列を使う。
※この「線形帰還シフトレジスタ」の解説は、「擬似乱数」の解説の一部です。
「線形帰還シフトレジスタ」を含む「擬似乱数」の記事については、「擬似乱数」の概要を参照ください。
線形帰還シフトレジスタと同じ種類の言葉
| レジスタに関連する言葉 | レジスタ アドレスレジスタ 線形帰還シフトレジスタ 指標レジスタ キャッシュレジスタ |
- 線形帰還シフトレジスタのページへのリンク
