移位寄存器序列

移位寄存器序列是數字通信中利用反饋移位寄存器產生的一種偽隨機碼，由初始狀態(x₁，x₂，…，x_n)依反饋邏輯函數x_n+1=f(x₁，x₂，…，x_n)產生的二元序列x₁，…，x_n，x_n+1，…，稱為移位寄存器序列，簡稱移存器序列。這裏f是Fⁿ₂到F₂的一個映射，它所產生的狀態轉移圖是二元域上德布萊英-古德圖的一個部分圖，當f的多項式表示是x₁，…，x_n的線性齊次式時，相應的移存器序列稱為線性的，否則稱為非線性的，當狀態轉移圖是兩兩不相交的圈的並時，相應的f及序列稱為非奇的，移存器序列中最簡單的兩種是由f(x₁，x₂，…，x_n)=x₁及f(x₁，x₂，…，x_n)=1+x₁所產生的，分別稱為純輪換移存器及補輪換移存器。它們都是非奇的，其狀態轉移圖中圈的總數分別是

及

，

其中m為n的最大奇因子，這兩種移存器在移存器序列理論中佔重要地位。n級線性移存器序列中週期最長(等於2ⁿ-1)的一種稱為m序列，它共有φ(2ⁿ-1)/n個，恰與F₂上全部n次本原多項式一一對應，由於它具有很好的偽隨機性，已得到充分研究和廣泛應用，n級移存器中週期最長(等於2ⁿ)的一種稱為M序列，它是非線性的，非奇的，它共有

個，恰與n級德布萊英-古德圖的全部歐拉遊一一對應，由於它具有巨大的數量和較好的偽隨機性，已受到保密通信界的普遍重視，移存器序列是一類有着廣泛應用的偽隨機碼，不但在保密通信中起加密的作用，在連續波雷達中可用作測距信號，在遙控系統中可用作遙控信號，在多址通信中可用作地址信號，在數字通信中可用作羣同步信號，此外還可用作噪聲源等 ^[1]  。

移位寄存器序列是指由移位寄存器輸出的由“1”和“0” 構成的序列。相應的時間波形是指由“1”和“-1”構成的時間函數，如圖1所示 ^[2]  。

產生移位寄存器序列的移位寄存器如圖2所示，它是由時鐘控制的n個串接的存儲器、移位脈衝發生器、反饋函數和模2加法器組成構成。組成移位寄存器的存儲器稱為移位寄存器的級，從左至右為第一級、第二級、....第n級，移位寄存器內容

為0或1，在某一時刻， 移位寄存器各級的存數按順序排列所組成的序列稱為該移位寄存器的狀態。規定移位寄存器的狀態是各級存數從右至左的順序排列而成的序列，這樣的狀態叫正狀態或簡稱狀態。反之，稱移位寄存器狀態是各級存數從左至右的順序排列而成的序列叫反狀態。如果用a_n-i(i=1, 2, 3，..，n)表示第i級的狀態(存數)，則a_n-i=0或1。反饋函數的輸入端通過係數與移位寄存器的各級狀態相聯(c_i=0斷，或c_i=1通)輸出通過反饋線作為x₁的輸人。移位寄存器在時鐘的作用下把反饋函數的輸出存入x₁，在下一個時鐘週期又把新的反饋函數的輸出存入x₁而把原x₁的內容移入x₂，依次循環下去，x_n不斷輸出。

根據反饋函數對移位寄存器序列的作用方式，可將序列發生器分為：

1)線性反饋移位寄存器序列產生器(LFSRSG)：如果

為

的模2加。

2)非線性反饋移位寄存器序列產生器(NLF-SRSG)：如果

不是

的模2加。

移位寄存器可有不同的初始狀態和不同的反饋邏輯，產生不同的序列。這就是説，移位寄存器序列是由它的初始狀態和反饋邏輯確定的。

可以得到下列結論：

1)線性移位寄存器的輸出序列是一個週期序列。

2)當初始狀態是0狀態時，線性移位寄存器的輸出都是0序列。

3)級數相同的線性移位寄存器的輸出序列和反饋邏輯有關。

4)同一個線性移位寄存器的輸出序列還和起始狀態有關。

5)對於級數為n的線性移位寄存器，當週期p=2ⁿ-1時，改變移位寄存器初始狀態只改變序列的初相。這樣的序列稱為最大長度序列或m序列 ^[2]  。