偽隨機序列

偽隨機序列的理論與應用研究大體上可以分成三個階段:(1)純粹理論研究階段 (1948年以前)；(2)m序列研究的黃金階段(1948-1969)； (3)非線性生成器的研究階段 (1969-)。

1948年以前，學者們研究偽隨機序列的理論僅僅是因為其優美的數學結構。最早的研究可以追溯到1894年，作為一個組合問題來研究所謂的De Bruijn序列；上世紀30年代，環上的線性遞歸序列則成為人們的研究重點.

1948年Shannon信息論誕生後，這種情況得到了改變。偽隨機序列己經被廣泛的應用在通信以及密碼學等重要的技術領域。Shannon證明了“一次一密”是無條件安全的，無條件保密的密碼體制要求進行保密通信的密鑰量至少與明文量一樣大。因此在此後的一段時間內，學者們一直致力於研究具有足夠長週期的偽隨機序列。如何產生這樣的序列是20世紀50年代早期的研究熱點。線性反饋移位寄存器 (LFSR)序列是這個時期研究最多的，因為一個n級LFSR可以產生週期為的最大長度序列，而且具有滿足Golomb隨機性假設的隨機特性，通常稱之為m序列。這段時期的研究奠定了LFSR序列的基本理論和一些經典結論。

但是，在1969年Massey發表了“移位寄存器綜合與BCH譯碼”一文，引發了序列研究方向的根本性變革，從此偽隨機序列的研究進入了構造非線性序列生成器的階段。Berlekamp-Massey算法(簡稱B-M算法)指出:如果序列的線性複雜度為n，則只需要2n個連續比特就可以恢復出全部的序列。從這個結論可以看出m序列是一種“極差”的序列，它的線性複雜度太小，因而不能夠直接用來做流密碼系統的密鑰流序列。從這裏還可以看到僅僅靠Golomb的三個隨機性假設來評測序列是不夠的，還需要其它的一些指標。此後直到今天，密碼學界的學者們一直在努力尋找構造“好”的偽隨機序列的方法。

偽隨機序列是具有某種隨機特性的確定的序列。它們是由移位寄存器產生確定序列，然而他們卻具有某種隨機特性的隨機序列。因為同樣具有隨機特性，無法從一個已經產生的序列的特性中判斷是真隨機序列還是偽隨機序列，只能根據序列的產生辦法來判斷。偽隨機序列系列具有良好的隨機性和接近於白噪聲的相關函數，並且有預先的可確定性和可重複性。這些特性使得偽隨機序列得到了廣泛的應用，特別是在CDMA系統中作為擴頻碼已成為CDMA技術中的關鍵問題。特性為序列中兩種元素出現的個數大致相等。

如果把n個元素連續出現叫做一個長度為n的元素遊程，則序列中長度為n的元素遊程比長度為n+1的元素遊程多一倍。

序列元素間有確定關係存在，但具有與隨機序列類似性質的一種特殊的離散信號形式，可表示為

…，ɑ-1，ɑ0，ɑ1，ɑ2，…

其中ɑi可取值0，1或1，-1；也可以取符號域GF(q)（見分組碼）中的元素。前者叫二元序列，後者叫 q元序列。但實用中最主要的還是前者。序列長度可以為有限，也可以為無窮。後者主要着重的是週期序列，即存在最小正整數夞，使對一切i有ɑp=ɑp+i，p為週期。

序列的各元素為相互獨立且具有相同分佈的隨機變量時，稱為隨機序列。實際應用的主要是偽隨機列。它指序列元素間有確定關係存在，但具有與隨機序列類似的下列性質：①在有限長度或一週期內各元素個數相差不超過1，即接近等概率；②出現 l個相同值或稱l長遊程的概率接近1/ql；③相關函數在τ=0時為p,τ厵0時不超過±1，式中p為序列的長度或週期。實際上有時將大體滿足以上條件的序列也稱為偽隨機序列。

偽隨機序列可用圖中 ɑ的反饋移位寄存器得到。圖中f(ɑn+i-1,ɑn+i-2,…,ɑi)表示反饋函數。n 級移位寄存器只能有2n（一般為qn）種狀態, 故經一定時間後會回到原來的某一狀態, 產生週期性輸出, 若反饋函數的輸出ɑn+i與各輸入ɑn+i-1，…，ɑi間有線性關係存在,則為線性移位寄存器，否則為非線性移位寄存器。圖中b和c分別是三級線性和非線性反饋移位寄存器。

對於線性移位寄存器序列有

ɑn+i=c0ɑn+i-1+c1ɑn+i-2+…+cn-1ɑi

(i=0,1,…)

它當初始值 ɑ0,ɑ1,…,ɑn-1全為零時輸出恆為零。除去這種全零狀態外，它最多可能取遍所有2n-1個非零狀態，故最大週期為2n-1。一般情況下週期是2n-1的因子。 　週期達到2n-1的序列稱為最長線性移位寄存器序列，簡稱M序列，圖中b就是三級M序列，它的輸出為…，0，0，1，0，1，1，1,…。M序列完全滿足偽隨機序列的三點要求，特別是它的相關函數為因而是典型的偽隨機序列。

M序列的週期一定是2n-1,實用上還需要有其他的週期,這可用非線性移位寄存器序列得到。n級非線性移位寄存器序列的週期不大於2n，達到2n的序列稱M序列。

一般M序列的相關函數不完全接近衝激函數。接近衝激函數的非線性移位寄存器序列主要有二次剩餘或稱勒讓德序列,簡稱L序列，以及孿生素數序列。兩者的相關函數均如式(3)。L序列是週期為形如4k-1的素數時所構造的序列，k為自然數。前幾個L序列的週期為3，7，11，19,23,…。當週期不超過任一大的正整數時,L序列的種類比M序列多得多。孿生素數序列是週期為k(k+2)的偽隨機序列，在此k與k+2均為素數，前幾個序列的週期為15，35，143，…。

應用中有關的全部序列叫序列族，且通常取週期相同的一族序列。既有良好的自相關特性又有良好的互相關特性的線性偽隨機序列族，主要有戈爾德序列族和嵩忠雄序列族等。

戈爾德序列族是由適當選擇的一對n級M序列線性組合構成，在此n呏1(mod 4)或n呏2(mod 4)。序列族中共有2n+1個序列，週期均為2n-1，兩兩之間的互相關函數最大值為2【(n+2)-2】+1，此處【X】表示不超過x的最大整數。n為偶數時戈爾德序列的性能較差,而嵩忠雄序列卻可達到最佳。後者由n級M序列和相應的n/2級M序列的線性組合構成。它的週期也是2n-1,但序列只有2個,互相關函數最大值是2+1。

迄今為止，人們獲得的偽隨機序列仍主要是PC（相控）序列，移位寄存器序列（m和M序列），Gold序列，GMW序列，級聯GMW序列，Kasami序列，Bent序列，No序列。

其中m序列是最有名和最簡單的,也是研究的最透徹的序列。m序列還是研究其它序列的基礎。它序列平衡，有最好的自相關特性，但互相關滿足一定條件的族序列數很少(對於本原多項式的階數小於等於13的m序列，互為優選對的序列數不多於6)，且線性複雜度很小。M序列族序列數極其巨大（當寄存器級數等於6時，有226個序列）。但其生成困難，且其互相關特性目前知之甚少，一般很少用。Gold序列互相關函數為3值，序列部分平衡，有良好的相關特性，族序列數相對較大，但它有致命的弱點，線性複雜度很低，僅是相同長度的m序列的兩倍，這制約了Gold序列的廣泛應用，特別在抗干擾及密碼學中的應用。GMW序列具有序列平衡，線性複雜度大，自相關性能好（同m序列）等優點。它是非線性序列，且數量比m序列多。作為單個序列GMW序列有優勢，但一族GMW序列滿足一定互相關條件的序列數很少。一般不用於多址通信作地址碼。級聯GMW序列平衡性和相關性同於GMW序列，族數比GMW序列多，一般情況下，線性複雜度比GMW序列大。Kasami序列分小集Kasami序列和大集Kasami序列。小集Kasami序列族序列數大，且互相關值達welch下界，大集Kasami序列族序列數非常大，互相關較小集Kasami序列為劣。它們都有共同的弱點，序列是不平衡的，線性複雜度不大(但比m, Gold序列稍大)。Bent序列是80年代初構造出來的，具有序列平衡，相關值達welch下界，族序列數多，線性複雜度大等優點。它在整個80年代，90年代大放光芒，也是目前綜合性能最好的偽隨機序列。但Bent序列構造較難，未有滿足一定要求的快速算法。No序列是80年代末構造出來的一種新型偽隨機序列，它的突出優點是線性複雜度很大，且相關值可達welch下界，族序列數多，但有序列不平衡的弱點。

m序列 ^[1]  是最長線性反饋移存器序列的簡稱，它是由帶線性反饋的移存器產生的週期最長的一種序列。

擾碼的目的是使短週期輸入序列變為長週期的信道序列。從原則上看，就可以用將一個長週期序列疊加在輸入序列上的方法來實現，並且疊加序列的週期越長越好。從理論上説，一個真正的隨機（二進制）序列的“週期”是無限長的，但是，採用這種序列時在接收端將無法產生相同的序列與之同步。所以，人們就不得不企圖用簡單電路來產生儘量長的序列。同時隨機噪聲在通信技術中，首先是作為有損通信質量的因素受到人們重視的。信道中存在的隨機噪聲會使模擬信號產生失真，或使數字信號解調後出現誤碼；同時，它還是限制信道容量的一個重要因素。因此，最早人們是企圖設計消除或減小通信系統的隨機噪聲，但是，有時人們也希望獲得隨機噪聲。例如，在實驗室中對通信設備或系統進行測試時，有時要故意加入一定的隨機噪聲，這時則需要產生它。

20世紀40年代末，隨着通信理論的發展，仙農（Shannon）就曾指出，在某種情況下，為了實現最有效的通信，應採用具有白噪聲的統計特性的信號。另外，為了實現高可靠的保密通信，也希望利用隨機噪聲。然而，利用隨機噪聲的最大困難是它難以產生和處理。直到60年代，偽隨機噪聲的出現才使上述困難得到解決。

偽隨機噪聲具有類是與隨機噪聲的一些統計特性，同時又便於重複產生和處理。由於它具有隨機噪聲的優點，又避免了它的缺點，因此獲得了日益廣泛的實際應用。目前廣泛應用的偽隨機噪聲都是由數字電路產生的週期序列（即濾波等處理後）得到的。今後我們將這種週期序列稱為偽隨機序列。

通常產生偽隨機序列的電路為一反饋移存器。他又可分為線性反饋移存器和非線性反饋遺存器兩類。由線性反饋遺存器產生出的週期最長的二進制數字序列，稱為最大長度線性反饋遺存器序列，通常簡稱為m序列。由於它的理論比較成熟，實現比較簡便，實際應用也比較廣泛，故這裏將重點討論它。

m序列是最長線性反饋移存器序列的簡稱，它是由帶線性反饋的移存器產生的週期最長的一種序列 。n級移位寄存器，其中有若干級經模2加法器反饋到第1級。不難看出，在任何一個時刻去觀察移位寄存器的狀態，必然是個狀態之一，其中每一狀態代表一個n位的二進制數字；但是，必須把全0排斥在外，因為如果一個進入全0，不論反饋線多少或在哪些級，這種狀態就不會再改變。所以，寄存器的狀態可以是非全0的狀態之一。這個電路的輸出序列是從寄存器移出的，儘管移位寄存器的狀態每一移位節拍改變一次，但無疑地是循環的。如果反饋線所分佈的級次是恰當的，那麼，移位寄存器的狀態必然各態歷經後才會循環。這裏所謂“各態歷經”就是所有個狀態都經過了。由此可見，應用n級移位寄存器所產生的序列的週期最長是。同時由於這種序列雖然是週期的，但當n足夠大時週期可以很長，在一個週期內0和1的排列有很多不同方式，對每一位來説是0還是1，看來好像是隨機的，所以又稱為偽隨機碼；又因為它的某一些性質和隨機噪聲很相似，所以又稱為偽噪聲碼（PN碼）。

m序列優選對的兩個n次本原多項式乘積構成的新序列為Gold序列，或m序列優選對的兩個本原多項式所產生序列的移位模2和新序列也叫做Gold序列 ^[2]  。

[1]在通信加密中的應用 ^[3]  m序列自相關性較好，容易產生和複製，而且具有偽隨機性，利用m序列加密數字信號使加密後的信號在攜帶原始信息的同時具有偽噪聲的特點，以達到在信號傳輸的過程中隱藏信息的目的；在信號接收端，再次利用m序列加以解密，恢復出原始信號。

[2] 在雷達信號設計中的應用 近年興起的擴展頻譜雷達所採用的信號是已調製的具有類似噪聲性質的偽隨機序列，它具有很高的距離分辨力和速度分辨力。這種雷達的接收機採用相關解調的方式工作，能夠在低信噪比的條件下工作，同時具有很強的抗干擾能力。該型雷達實質上是一種連續波雷達，具有低截獲概率性，是一種體制新、性能高、適應現代高技術戰爭需要的雷達。採用偽隨機序列作為發射信號的雷達系統具有許多突出的優點。首先，它是一種連續波雷達，可以較好地利用發射機的功率。其次，它在一定的信噪比時，能夠達到很好的測量精度，保證測量的單值性，比單脈衝雷達具有更高的距離分辨力和速度分辨力。最後，它具有較強的抗干擾能力，敵方要干擾這種寬帶雷達信號，將比干擾普通的雷達信號困難得多。

[3] 在通信系統中的應用 偽隨機序列是一種貌似隨機，實際上是有規律的週期性二進制序列，具有類似噪聲序列的性質，在CDMA中，地址碼都是從偽隨機序列中選取的，在CDMA中使用一種最易實現的偽隨機序列：m序列，利用m序列不同相位來區分不同用户；為了數據安全，在CDMA的尋呼信道和正向業務信道中使用了數據掩碼（即數據擾亂）技術，其方法是用長度為2的42次方減1的m序列用於對業務信道進行擾碼（注意不是擴頻），它在分組交織器輸出的調製字符上進行，通過交織器輸出字符與長碼PN碼片的二進制模工相加而完成。