2.2　線形フィードバックシフトレジスタ（ＬＦＳＲ）




　２．１で述べたｍ系列を生成する装置として線形フィードバックシフトレジ
スタ（ＬＦＳＲ）というものがあります。この装置を下図に示します。


図：線形フィードバックシフトレジスタ（ＬＦＳＲ）


　このように、シフトレジスタの各セルにフィードバックをかけます。ｑi
(i=0,1,・・・,n)の値は{0,1}であり、１の時は、そのセルの内容をフィ
ードバックして、０の時はフィードバックしません。フィードバックの値は排他
的論理和(EOR)によって加算され、最後に０or１がフィードバック値として戻さ
れます。
　式で書くと以下のようになります。

  1. aiqi(i=0,1,・・・,n)のEORを計算する。

  2. レジスタの最右セル(a0)を出力する。

  3. レジスタの内容を一つ右にシフトする。

  4. 3の計算結果(０or１)をレジスタの最左セルに格納する。

　上記のような１〜４を繰り返すことによって出力系列がｍ系列となります。


　またｑ＝ｑn-1Ｘn-1＋ｑn-2Ｘn-2 ＋・・・＋ｑ1Ｘ＋ｑ0を特性多項式と呼びます。
　この特性多項式が原始多項式である時（因数分解ができない時）、ｍ系列の
周期は最大周期Ｔ＝２n−１となります。