填充塔
[拼音]：weisuiji xulie
[英文]：pseudorandom sequence
序列元素間有確定關係存在，但具有與隨機序列類似性質的一種特殊的離散訊號形式，可表示為…，ɑ-1，ɑ0，ɑ1，ɑ2，…
其中ɑi可取值0，1或1，-1；也可以取符號域GF(q)（見分組碼）中的元素。前者叫二元序列，後者叫 q元序列。但實用中最主要的還是前者。序列長度可以為有限，也可以為無窮。後者主要著重的是週期序列，即存在最小正整數夞，使對一切i有ɑp＝ɑp+i，p為週期。
序列的各元素為相互獨立且具有相同分佈的隨機變數時，稱為隨機序列。實際應用的主要是偽隨機序列。它指序列元素間有確定關係存在，但具有與隨機序列類似的下列性質：
（1）在有限長度或一週期內各元素的個數相差不超過1，即接近等概率；
（2）出現 l個相同值或稱l長遊程的概率接近1/ql；
（3）相關函式
(1)
在τ＝0時為p，τ厵0時不超過±1，式中p為序列的長度或週期。實際上有時將大體滿足以上條件的序列也稱為偽隨機序列。
發展概況
相關函式接近衝激函式的訊號是相關檢測系統中比較理想的形式。為了構造這樣的訊號，1953年R.H.巴克首先找到長度為有限的一些二元序列具有上述特點，稱之為巴克序列。可惜，已知的巴克序列最大長度為13，且已證明不存在比13更長的奇長巴克序列，對於偶長巴克序列長度應為4v2，已證明2＜v＜54的序列也不存在，故難以滿足要求較高的場合。為了獲得長度較長、效能較好且數量較多的序列，理論上較易解決的是可用反饋移位暫存器實現的無限週期序列。這主要有M序列和L序列等，前者為線性移位暫存器序列，後者為非線性移位暫存器序列。
應用中除了要求單個序列有好的效能外，還希望不同序列間的互相關函式小，理論上解決較好的有戈爾德序列族和嵩忠雄序列族，均為線性族。非線性的則有彎函式序列族或稱OSW序列族。
序列的構造
偽隨機序列可用圖中 ɑ的反饋移位暫存器得到。圖中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 (2)
(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序列完全滿足偽隨機序列的三點要求，特別是它的相關函式為
(3)
因而是典型的偽隨機序列。
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。
應用
偽隨機序列作為一種訊號形式，具有良好的相關特性，可作為雷達測距、同步和線性系統測量的訊號。它還具有偽隨機性，因而可用於加密系統和偽隨機跳頻等場合。這時常將序列經非線性變換，即構造前饋序列；或者用多個序列組合後輸出以增加保密性。它還可用以產生偽隨機數適於計算機的系統模擬和在數字系統中作為誤碼測試訊號等。偽隨機序列還可用於擴頻，在多址系統中作為地址訊號等。偽隨機序列有多方面的應用，對它的要求也很不相同。例如用於多址訊號時不但要求它通常的互相關函式要小，而且和在中間任意一位處反相後的互相關函式也要小；又如用於加密系統時，不但要考慮它的分析，而且要考慮它的綜合和計算複雜性。關於非線性移位暫存器序列，尚有許多問題沒有完全解決。
參考書目
萬哲先、代宗鐸、劉木蘭、馮緒寧：《非線性移位暫存器》，科學出版社，北京，1978。
S.W.Golomb， Shift Register Sequences，Holden-Day， San Francisco，1967.