線形帰還シフトレジスタ
これは、最初のビットへの入力に対応している(つまり、x であり、1と等価である)。各項のべき乗部分はタップ位置を表していて、左端から何番目かに対応している。左端は常に入力、右端は常にタップとして連結する。
LFSRは、帰還多項式が(タップシーケンス)は原始多項式であるならば最長LFSRとなる。よって、次の性質を持つ。
最長LFSRのタップ数は必ず偶数。非常に長いレジスタであっても2個や4個のタップで十分である。
最長LFSRのタップ集合は互いに素でなければならない。つまり、全タップ間の1以外の公約数が存在してはならない。
最大LFSRを構築することができる原始多項式のリストを、下の表と参考文献に示す。
LFSRの長さによっては、最長となる複数の多項式が存在する。この場合、最長となるタップシーケンスが1つ見つかると、他は自動的に得られる。nビットのLFSRで、タップシーケンス [n,A,B,C,0] が見つかったとき(0は x 0 = 1 {\displaystyle x^{0}=1} に対応)、もう1つのタップシーケンスは [n,n-C,n-B,n-A,0] である。例えば、[32,3,2,0] に対応するのは [32,30,29,0] である。どちらも最長である。
C/C++ のコーディング例を以下に示す。
このコードでは、左端ビットが1番目の位置である。
0や1が連続すると、シンボルの区切りがわからなくなる危険性があるため、線形帰還シフトレジスタを使ってビットストリームを無作為化することが多い。この無作為化は受信側で復調後に除去される。LFSRと転送シンボルストリームが同じレートで動作する場合、この技法をスクランブリングと呼ぶ。LFSRの方がシンボルストリームよりずっと高速に動作し、信号送信時の帯域幅を拡張させる場合、これを直接シーケンス・スペクトラム拡散と呼ぶ。
LFSRによるスクランブリングは暗号化ではなく、解読には、一般的な暗号において必要な困難は全く無い。
LFSRを使っているデジタル放送システム:
ATSC (北米)
DAB (デジタルラジオ)
DVB-T (ヨーロッパ、オーストラリア)
NICAM (イギリスなどのテレビ用デジタル音声システム)
その他のLFSRを使っているデジタル通信システム:
IBS (INTELSAT business service)
IDR (Intermediate Data Rate service)
SDI (シリアルデジタルインタフェース)
公衆交換電話網上のデータ転送(ITU-TのVシリーズ勧告)
CDMA携帯電話
100BASE-T2 高速イーサネットでは、LFSRでビットのスクランブルを行う。
1000BASE-T イーサネットでも、LFSRでビットのスクランブルを行う。