如果一個序列，一方面它是可以預先確定的，並且是可以重複地生產和複製的；一方面它又具有某種隨機序列的隨機特性（即統計特性），我們便稱這種序列為偽隨機序列。
偽隨機序列理論的發展歷史,簡介,構造,序列族,偽隨機序列研究現狀,m序列,m序列的定義,m序列的產生,Gold序列,Gold序列的定義,偽隨機序列的套用及其意義,
偽隨機序列理論的發展歷史
偽隨機序列的理論與套用研究大體上可以分成三個階段:(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序列
m序列的定義
m序列是最長線性反饋移存器序列的簡稱，它是由帶線性反饋的移存器產生的周期最長的一種序列。
m序列的產生
擾碼的目的是使短周期輸入序列變為長周期的信道序列。從原則上看，就可以用將一個長周期序列疊加在輸入序列上的方法來實現，並且疊加序列的周期越長越好。從理論上說，一個真正的隨機（二進制）序列的“周期”是無限長的，但是，採用這種序列時在接收端將無法產生相同的序列與之同步。所以，人們就不得不企圖用簡單電路來產生儘量長的序列。同時隨機噪聲在通信技術中，首先是作為有損通信質量的因素受到人們重視的。信道中存在的隨機噪聲會使模擬信號產生失真，或使數位訊號解調後出現誤碼；同時，它還是限制信道容量的一個重要因素。因此，最早人們是企圖設計消除或減小通信系統的隨機噪聲，但是，有時人們也希望獲得隨機噪聲。例如，在實驗室中對通信設備或系統進行測試時，有時要故意加入一定的隨機噪聲，這時則需要產生它。
20世紀40年代末，隨著通信理論的發展，仙農（Shannon）就曾指出，在某種情況下，為了實現最有效的通信，應採用具有白噪聲的統計特性的信號。另外，為了實現高可靠的保密通信，也希望利用隨機噪聲。然而，利用隨機噪聲的最大困難是它難以產生和處理。直到60年代，偽隨機噪聲的出現才使上述困難的到解決。
偽隨機噪聲具有類是與隨機噪聲的一些統計特性，同時又便於重複產生和處理。由於它具有隨機噪聲的優點，又避免了它的缺點，因此獲得了日益廣泛的實際套用。目前廣泛套用的偽隨機噪聲都是由數字電路產生的周期序列（即濾波等處理後）得到的。今後我們將這種周期序列稱為偽隨機序列。
通常產生偽隨機序列的電路為一反饋移存器。他又可分為線性反饋移存器和非線性反饋遺存器兩類。由線性反饋遺存器產生出的周期最長的二進制數字序列，稱為最大長度線性反饋遺存器序列，通常簡稱為m序列。由於它的理論比較成熟，實現比較簡便，實際套用也比較廣泛，故這裡將重點討論它。
m序列是最長線性反饋移存器序列的簡稱，它是由帶線性反饋的移存器產生的周期最長的一種序列 。圖1就是一個這樣的電路。圖中示出了n級移位暫存器，其中有若干級經模2加法器反饋到第1級。不難看出，在任何一個時刻去觀察移位暫存器的狀態，必然是個狀態之一，其中每一狀態代表一個n位的二進制數字；但是，必須把全0排斥在外，因為如果一個進入全0，不論反饋線多少或在哪些級，這種狀態就不會再改變。所以，暫存器的狀態可以是非全0的狀態之一。這個電路的輸出序列是從暫存器移出的，儘管移位暫存器的狀態每一移位節拍改變一次，但無疑地是循環的。如果反饋線所分布的級次是恰當的，那么，移位暫存器的狀態必然各態歷經後才會循環。這裡所謂“各態歷經”就是所有個狀態都經過了。由此可見，套用n級移位暫存器所產生的序列的周期最長是。同時由於這種序列雖然是周期的，但當n足夠大時周期可以很長，在一個周期內0和1的排列有很多不同方式，對每一位來說是0還是1，看來好像是隨機的，所以又稱為偽隨機碼；又因為它的某一些性質和隨機噪聲很相似，所以又稱為偽噪聲碼（PN碼）。
Gold序列
Gold序列的定義
m序列優選對的兩個n次本原多項式乘積構成的新序列為Gold序列，或m序列優選對的兩個本原多項式所產生序列的移位模2和新序列也叫做Gold序列。
偽隨機序列的套用及其意義
[1]在通信加密中的套用 m序列自相關性較好，容易產生和複製，而且具有偽隨機性，利用m序列加密數位訊號使加密後的信號在攜帶原始信息的同時具有偽噪聲的特點，以達到在信號傳輸的過程中隱藏信息的目的；在信號接收端，再次利用m序列加以解密，恢復出原始信號。
[2] 在雷達信號設計中的套用 近年興起的擴展頻譜雷達所採用的信號是已調製的具有類似噪聲性質的偽隨機序列，它具有很高的距離分辨力和速度分辨力。這種雷達的接收機採用相關解調的方式工作，能夠在低信噪比的條件下工作，同時具有很強的抗干擾能力。該型雷達實質上是一種連續波雷達，具有低截獲機率性，是一種體制新、性能高、適應現代高技術戰爭需要的雷達。採用偽隨機序列作為發射信號的雷達系統具有許多突出的優點。首先，它是一種連續波雷達，可以較好地利用發射機的功率。其次，它在一定的信噪比時，能夠達到很好的測量精度，保證測量的單值性，比單脈衝雷達具有更高的距離分辨力和速度分辨力。最後，它具有較強的抗干擾能力，敵方要干擾這種寬頻雷達信號，將比干擾普通的雷達信號困難得多。
[3] 在通信系統中的套用 偽隨機序列是一種貌似隨機，實際上是有規律的周期性二進制序列，具有類似噪聲序列的性質，在CDMA中，地址碼都是從偽隨機序列中選取的，在CDMA中使用一種最易實現的偽隨機序列：m序列，利用m序列不同相位來區分不同用戶；為了數據安全，在CDMA的尋呼信道和正向業務信道中使用了數據掩碼（即數據擾亂）技術，其方法是用長度為2的42次方減1的m序列用於對業務信道進行擾碼（注意不是擴頻），它在分組交織器輸出的調製字元上進行，通過交織器輸出字元與長碼PN碼片的二進制模工相加而完成。
