ガロア LFSR
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/08/01 23:00 UTC 版)
「線形帰還シフトレジスタ」の記事における「ガロア LFSR」の解説
フランス人数学者エヴァリスト・ガロアの名を冠したガロアLFSRは、通常のLFSRと同じビット列を生成できる別の構成である[要出典]。ガロアLFSRでは、タップでないビットはクロック毎に次のフリップフロップにシフトされる（普通のLFSRと同じ）。タップの場合、新たな出力と前のビットの値をXORしたものを格納する。 通常の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」の解説は、「線形帰還シフトレジスタ」の解説の一部です。
「ガロア LFSR」を含む「線形帰還シフトレジスタ」の記事については、「線形帰還シフトレジスタ」の概要を参照ください。
- ガロア LFSRのページへのリンク
