線形帰還シフトレジスタ
フランス人数学者エヴァリスト・ガロアの名を冠したガロアLFSRは、通常のLFSRと同じビット列を生成できる別の構成である。ガロアLFSRでは、タップでないビットはクロック毎に次のフリップフロップにシフトされる(普通のLFSRと同じ)。タップの場合、新たな出力と前のビットの値をXORしたものを格納する。
通常のLFSRと同じ出力シーケンスを得るには、ビット順序を逆にする(図参照)。そうしないとシーケンスが逆転する。なお、LFSRの内部状態は同じである必要はない。図に示したガロアLFSRは、上の図で示したフィボナッチLFSRと同じ出力となる。
ガロアLFSRでは、全タップの値を使って入力を生成するわけではなく、XORは個別に各タップ位置で行われる。つまり、XOR演算を並列に実行でき、高速化が可能である。
ソフトウェアで実装すると、ワード全体のビット演算で一度にXORできるので、さらに効率的な実装になる。
以下は32ビットの最長ガロアLFSRをC言語およびC++で実装したものである(unsigned int は32ビットと仮定)。
次のコードは、図にある16ビットの例である。