LFSR計算機 - 線形帰還シフトレジスタ

線形帰還シフトレジスタ（LFSR）は、入力ビットが過去の状態ビットの一部に対する線形関数（XOR）で決まるシフトレジスタです。各クロックサイクルでレジスタは 1 つずつシフトされ、新しい入力ビットはフィードバックタップと呼ばれる特定位置のビットを XOR して計算され、出力はシフトアウトされたビットになります。結果の二進シーケンスはランダムに見えますが、完全に決定論的であり、周期はレジスタ長とタップの選び方によって決まります。 LFSR は、デジタル通信、暗号、BIST（組み込み自己テスト）回路、スペクトラム拡散システム、疑似乱数生成などで広く使われています。n 段の LFSR は、繰り返す前に最大で 2ⁿ − 1 ビットの系列を生成できます（全ゼロ状態は除外）。適切に選ばれた原始多項式タップを使えばこの最大長系列を実現できるため、LFSR は疑似乱数を効率よくハードウェア実装できます。 LFSR の代表的なアーキテクチャは 2 つあります。Fibonacci（外部帰還）LFSR では、帰還ビットは固定されたタップ位置から計算され、左端の段に入力され、他の段は右へシフトします。出力は右端の段から取ります。Galois（内部帰還）LFSR では、帰還ビットは入力に戻すだけでなく、複数の中間段へ直接 XOR されます。XOR 演算が直列ではなく並列に行われるため、Galois LFSR の方がハードウェアでは高速です。 最大長 LFSR、つまり繰り返す前に 2ⁿ − 1 個の非ゼロ状態をすべて巡回する LFSR には、原始多項式を帰還多項式として使う必要があります。タップ位置はその多項式の非ゼロ係数に対応します。4 ビット LFSR でタップが 4 と 3 の場合、原始多項式は x⁴ + x³ + 1 となり、LFSR は 15 個すべての非ゼロ状態を巡回します。 この計算機では、レジスタ長、シード、タップ位置、LFSR の種類を自由に組み合わせて試せます。結果の周期を見れば、選んだタップが最大長系列を作るか確認できます。周期が 2ⁿ − 1 なら、そのタップは原始多項式を構成します。用意した例で、よく知られた最大長構成を確認できます。 LFSR の応用範囲は広く、Wi‑Fi や Bluetooth では周波数ホッピングや直接拡散スペクトラムの拡散符号に使われます。ストレージや通信では CRC（巡回冗長検査）回路が LFSR として実装されます。暗号ストリーム暗号では、LFSR が中核原語になります（ただし現代の暗号は線形暗号解析への耐性を高めるため、複数の LFSR と非線形要素を組み合わせます）。チップテストでは、LFSR ベースのシグネチャ解析がテスト応答データを小さなシグネチャに圧縮します。