移位暫存器序列

移位暫存器序列(shift register sequence)是一類重要的碼，它是數字通信中利用反饋移位暫存器產生的一種偽隨機碼，由初始狀態(x₁，x₂，…，x_n)依反饋邏輯函式x_n+1=f(x₁，x₂，…，x_n)產生的二元序列x₁，…，x_n，x_n+1，…，稱為移位暫存器序列，簡稱移存器序列。

基本介紹

• 中文名：移位暫存器序列
• 外文名：shift register sequence
• 所屬學科：數學（組合設計）
• 簡介：反饋移位暫存器產生的偽隨機碼
• 簡稱：移存器序列

基本介紹

移位暫存器序列是數字通信中利用反饋移位暫存器產生的一種偽隨機碼，由初始狀態(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”和“0” 構成的序列。相應的時間波形是指由“1”和“-1”構成的時間函式，如圖1所示。

圖1（a）移位暫存器序列

圖1（b）移位暫存器波形

圖1（c）負邏輯關係

圖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序列。