第2章擴(kuò)展頻譜通信中的偽隨機(jī)序列2.1偽隨機(jī)序列的概念2.2幾種常見(jiàn)偽隨機(jī)序列的構(gòu)造2.3

m序列2.4

Gold序列族2.5截短m序列2.6

M序列

2.1偽隨機(jī)序列的概念

2.1.1基本概念

任何一個(gè)序列都是由一個(gè)個(gè)碼元組成的。對(duì)于二進(jìn)制序列，其碼元只可能是“0”或“1”；對(duì)于雙極性碼，其碼元是“-1”或“1”。在周期或長(zhǎng)度為N的序列中，相同碼元的碼元串稱為游程。其中，游程中所包含的碼元數(shù)稱為該游程的長(zhǎng)度。例如序列1110010110001包含6個(gè)游程，即“1111”、“00”、“1”、“0”、“11”、“000”。注意該序列的最后一個(gè)碼元“1”應(yīng)循環(huán)移位到序列首，與序列起始的三個(gè)碼元“111”共同組成一個(gè)游程。在研究序列之間的關(guān)系時(shí)，我們討論得比較多的是序列的相關(guān)特性，下面給出幾個(gè)有關(guān)相關(guān)特性的定義。假設(shè)有兩個(gè)序列長(zhǎng)度為N的雙極性序列，分別為X={x1,x2,x3,…，xN}，Y={y1,y2,y3,…,yN}，它們的相關(guān)系數(shù)由下式定義(2－1－1)

顯然，相關(guān)系數(shù)給出的是兩個(gè)序列在特定相對(duì)相位下的相關(guān)程度，而相關(guān)函數(shù)或互相關(guān)函數(shù)給出的是序列在所有相對(duì)相位下的相關(guān)程度，其定義式為(2－1－2)

對(duì)于二進(jìn)制碼，其相關(guān)函數(shù)也可以表示為(2－1－3)其中，A為X、Y對(duì)應(yīng)碼元相同的數(shù)目，而D為對(duì)應(yīng)碼元不同的數(shù)目。

X序列的自相關(guān)函數(shù)為

在描述序列自相關(guān)特性的時(shí)候，我們往往用周期和非周期自相關(guān)函數(shù)來(lái)表示。周期自相關(guān)函數(shù)的定義式為(2－1－4)

可見(jiàn)，周期自相關(guān)函數(shù)是序列和它的循環(huán)移位序列之間的相關(guān)系數(shù)表示。非周期自相關(guān)函數(shù)（或部分自相關(guān)函數(shù)）的定義式為(2－1－5)同樣，對(duì)于互相關(guān)函數(shù)也有類似的周期和非周期互相關(guān)函數(shù)定義。上面給出的自相關(guān)函數(shù)的定義都是歸一化的，在有些情況下，我們也采用非歸一化的定義，即公式的前面沒(méi)有1/N項(xiàng)。有了序列相關(guān)函數(shù)的定義，我們就可以定義序列的正交性。如果兩個(gè)序列的相關(guān)系數(shù)為0，則稱這兩個(gè)序列是正交的。即滿足(2－1－6)

例2.1

8位長(zhǎng)的Walsh序列組如下所示，驗(yàn)證該序列組中任何一對(duì)序列都是正交的。這里只給出ρ(W2,W7)，大家可以自行驗(yàn)證其他的序列對(duì)。如果某一組序列中，不同的兩個(gè)序列之間的相關(guān)系數(shù)總是為負(fù)，則稱這組序列為超正交序列。

例2.2給出兩個(gè)序列：

求它們的相關(guān)系數(shù)?？梢?jiàn)，根據(jù)定義，這兩個(gè)序列是超正交的。細(xì)心的讀者也許可以發(fā)現(xiàn)，Y序列實(shí)際上是X序列循環(huán)右移3位后得到的序列。2.1.2偽隨機(jī)序列的定義及分類

由“偽噪聲序列”的名稱可以看出，偽隨機(jī)序列是一種具有類似噪聲特性的序列，即偽隨機(jī)序列就是一種盡量接近噪聲特性的序列。那么一個(gè)噪聲信號(hào)具有哪些特性呢？我們知道，高斯白噪聲信號(hào)的分布函數(shù)為其自相關(guān)函數(shù)為即噪聲功率為功率譜密度函數(shù)為其中,N0是噪聲信號(hào)的單邊功率譜密度。高斯白噪聲本身是一種模擬信號(hào)，而且至今無(wú)法實(shí)現(xiàn)對(duì)白噪聲的放大、調(diào)制、檢測(cè)、同步及控制等，而只能用具有類似于帶限白噪聲統(tǒng)計(jì)特性的偽隨機(jī)碼來(lái)逼近它，并作為擴(kuò)頻系統(tǒng)的擴(kuò)頻碼。目前常用的偽隨機(jī)序列都是二元偽隨機(jī)序列，序列中的元素只有“0”或“1”（對(duì)應(yīng)雙極性信號(hào)的“-1”和“1”）。因此高斯白噪聲不可能從信號(hào)的幅度分布上逼近，而主要從碼元的分布、相關(guān)特性等方面進(jìn)行逼近。目前一般將滿足以下三個(gè)隨機(jī)性條件的序列稱為偽隨機(jī)序列：

（1）平衡特性：序列中“0”和“1”出現(xiàn)的概率相同，也就是說(shuō)序列中“0”和“1”的數(shù)目相同或基本相同。

（2）游程特性：在每個(gè)碼字周期內(nèi)，長(zhǎng)度為n的游程數(shù)比長(zhǎng)度為n+1的游程數(shù)多一倍。一般情況下，長(zhǎng)度為p的游程數(shù)占游程總數(shù)的 。

（3）相關(guān)特性：碼的自相關(guān)函數(shù)具有接近于δ函數(shù)的形式，即具有尖銳的自相關(guān)特性。例2.3下面分別給出了長(zhǎng)度為7和15的兩個(gè)m序列及兩個(gè)長(zhǎng)度為16的M序列。

m序列:11100，10

11110，10110，01000

M序列：01001，10101，11100，0

01100，10111，10100，0

驗(yàn)證它們是否滿足三個(gè)隨機(jī)性條件。

通過(guò)驗(yàn)證，可以知道所給出的序列基本上滿足三個(gè)給定的隨機(jī)條件。其中m序列中“1”比“0”多1個(gè)，而M序列中的“1”與“0”的數(shù)目相等。

實(shí)際應(yīng)用中，偽隨機(jī)序列根據(jù)不同的產(chǎn)生條件分為很多種，一般分為狹義偽隨機(jī)序列和廣義偽隨機(jī)序列。凡自相關(guān)函數(shù)具有(2－1－7)形式的序列，稱為狹義偽隨機(jī)序列。很顯然，狹義偽隨機(jī)序列對(duì)序列的相關(guān)特性要求較高，所以滿足要求的序列數(shù)量少。而實(shí)際應(yīng)用當(dāng)中，對(duì)相關(guān)性要求不一定如此苛刻，因此有廣義偽隨機(jī)序列的概念。而廣義偽隨機(jī)序列又分為第一類和第二類廣義偽隨機(jī)序列。其中第一類廣義偽隨機(jī)序列定義為：凡自相關(guān)函數(shù)具有(2－1－8)狹義偽隨機(jī)序列和第一類廣義偽隨機(jī)序列只對(duì)序列的自相關(guān)特性提出了要求，而實(shí)用中對(duì)序列的互相關(guān)特性也是有要求的，因此，人們給出了第二類廣義偽隨機(jī)序列的定義：如果有一組序列C1，C2，C3，…，CP，其中兩兩相關(guān)系數(shù)滿足(2－1－9)則稱該序列組為第二類廣義偽隨機(jī)序列組，其中任何一個(gè)序列都是第二類廣義偽隨機(jī)序列。第一類廣義偽隨機(jī)序列和第二類廣義偽隨機(jī)序列統(tǒng)稱為廣義偽隨機(jī)序列。顯然，狹義偽隨機(jī)序列是第一類廣義偽隨機(jī)序列的特例，而正交序列則是第二類廣義偽隨機(jī)序列的特例。2.1.3擴(kuò)譜通信對(duì)偽隨機(jī)序列的要求

從擴(kuò)譜通信的抗干擾、抗截獲、易于同步的角度看，對(duì)偽隨機(jī)序列的要求主要體現(xiàn)在以下幾個(gè)方面：

（1）具有尖銳的自相關(guān)函數(shù)，而互相關(guān)函數(shù)應(yīng)接近于0。擴(kuò)譜通信對(duì)偽隨機(jī)序列相關(guān)特性的要求主要是通信信號(hào)的同步以及實(shí)現(xiàn)多址通信的要求。尖銳的自相關(guān)特性可以減小接收機(jī)同步時(shí)誤捕的概率，而互相關(guān)函數(shù)接近于0可以使得不同用戶之間的干擾盡可能地小。（2）有足夠長(zhǎng)的碼周期和復(fù)雜度，以確?？箓刹?、抗干擾的要求。擴(kuò)譜通信的一個(gè)主要優(yōu)點(diǎn)就是抗偵察、抗截獲特性，但是該特性主要依賴于擴(kuò)譜通信所采用的偽隨機(jī)序列，偽隨機(jī)序列越長(zhǎng)、序列的復(fù)雜度越大，則擴(kuò)譜信號(hào)的抗偵察、抗截獲性能越好。偽隨機(jī)序列的復(fù)雜度一般用線性長(zhǎng)度來(lái)衡量，線性長(zhǎng)度的定義將在2.3節(jié)給出。

（3）滿足要求的序列數(shù)足夠多，以實(shí)現(xiàn)碼分多址的要求。擴(kuò)譜通信中的碼分多址即指每個(gè)用戶的擴(kuò)譜調(diào)制采用不同的偽隨機(jī)序列。

（4）工程上易于產(chǎn)生、加工、復(fù)制和控制。

2.2幾種常見(jiàn)偽隨機(jī)序列的構(gòu)造

2.2.1雙值自相關(guān)序列

如果一個(gè)碼長(zhǎng)為N的周期序列的自相關(guān)函數(shù)滿足(2－2－1)我們就把這種具有雙值自相關(guān)特性的序列叫做雙值自相關(guān)序列，它屬于廣義偽隨機(jī)序列。如果式中，則該序列為狹義偽隨機(jī)序列。雙值自相關(guān)序列的構(gòu)造與差集是密切相關(guān)的，即可以通過(guò)構(gòu)造差集來(lái)構(gòu)造雙值自相關(guān)序列。一個(gè)差集通常用3個(gè)參數(shù)來(lái)表征，即v、k、λ。

設(shè)有一個(gè)模v的整數(shù)集V，存在一個(gè)含有k個(gè)元的子集D，即D={d1,d2,…,dk}，且di-dj(modv)(i≠j)恰好遍取1,2,…,v-1各λ次，這樣的整數(shù)集V的子集D稱為差集。

例2.4

給定兩個(gè)集合D={1,2,4}、D={0,2,3}，驗(yàn)證它們均是參數(shù)為v=7,k=3,λ=1的差集。

證明對(duì)于第一個(gè)集合，有顯然，第一個(gè)集合滿足差集的定義，因此是參數(shù)為v=7,k=3,λ=1的差集。對(duì)于第二個(gè)集合，大家可以自行驗(yàn)證。有了一個(gè)差集后，我們就可以根據(jù)該差集按照下面的方法來(lái)構(gòu)造雙值自相關(guān)序列。對(duì)于給定的差集（v,k,λ)可以寫出令X={x0，x1,x2,…,xv-1}為一長(zhǎng)度為v的碼，且則X={x0，x1,x2,…,xv-1}就是一個(gè)雙值自相關(guān)的廣義偽隨機(jī)序列，且其自相關(guān)函數(shù)為(2－2－2)寫出模v的整數(shù)集及其循環(huán)移位整數(shù)集:V={0,1,2,……,v-1}V′={v-1,0,1,2,……,v-2}作V-V′:{0-(v-1),1-0,2-1,…,(v-1)-(v-2)}顯然上述結(jié)果為{1,1,1,…,1}(mod

v)。（1）上述結(jié)果中包含了整數(shù)集V中不同元做差結(jié)果為1的所有組合。

（2）根據(jù)差集的定義，集V中有k個(gè)元組成差集D，且di-dj(modv)(i≠j)恰好遍取1,2,…,v-1各λ次，這λ次的運(yùn)算必然包含在{0-(v-1),1-0,2-1,…,(v-1)-(v-2)}中，即這λ項(xiàng)是由差集D中的元構(gòu)成的差。

（3）由于D中有k個(gè)元，因此V-V′中必然有2(k-λ)項(xiàng)是由一個(gè)D中的元和一個(gè)非D中的元構(gòu)成的差，最后還剩v-2(k-λ)項(xiàng)都是由非D中的元構(gòu)成的差。根據(jù)由差集構(gòu)造雙值自相關(guān)序列的定義，可以寫出由差集（v,k,λ）構(gòu)造的雙值自相關(guān)序列X與其右移一位序列X1為X={x1,x2，……,xv-1}X1={xv-1,x1,x2，……,xv-2}二者的對(duì)應(yīng)碼元中均為1的有λ項(xiàng)，一個(gè)為1、一個(gè)為-1的有2(k-λ)項(xiàng)，二者均為-1的有v-λ-2(k-λ)項(xiàng)，故同理可證j=2,3,…,v-1時(shí)也有另當(dāng)j=0時(shí)，RX(0)=1。得證。

例2.5求分別以參數(shù)為v=7,k=3,λ=1的差集D={1,2,4}、D={0,2,3}和參數(shù)為v=23,k=11,λ=5的差集D={1,2,3,4,6,8,9,12,13,16,18}構(gòu)成的雙值自相關(guān)序列的自相關(guān)函數(shù)。

例2.6對(duì)于v=7,k=3,λ=1的差集D={1,2,4}，驗(yàn)證2就是該差集的乘子。

用2分別乘差集中的每一個(gè)元素并取模7運(yùn)算，得到 D′={2,4,1}

即

t·di=di+1(mod

7)

所以2是該差集的乘子。

定理2.1(乘子定理)設(shè)D是某個(gè)差集，令n=k-λ，又n1是n的因子，且(n1,v)=1（n1與v互素）,n1>λ。如果對(duì)于n1的每個(gè)素?cái)?shù)因子pl均存在jl，使得

那么t就是差集模v的一個(gè)乘子。

利用此定理，可由給定的（v,k,λ）構(gòu)造出相應(yīng)的差集。

例2.7：利用乘子定理構(gòu)造參數(shù)為v＝23,k＝11,λ＝5的差集。

由n1>λ=5、n1是n=k-λ=6的因子、n1與23互素，得n1=6=2×3即p1=2，p2=3再由 可求出t=4,9,16等,即在模23運(yùn)算情況下，22＝33＝4，25＝32＝9，24＝36＝16以t=4為例，由tm(modv),m=0,1,2，…，可得V的一個(gè)子集為{1,4,16,18,3,12,2,8,9,13,6}這就是V的一個(gè)差集D1，寫成D1={1,2,3,4,6,8,9,12,13,16,18}此外，由5tm(modv),m=0,1,2,…，還可以得到另一個(gè)子集（之所以乘5，是因?yàn)镈1中未出現(xiàn)的最小數(shù)是5），可得D2={5,10,15,20,7,17,22,14,19,11,21}2.2.2平方余數(shù)碼

平方余數(shù)碼（或稱平方剩余碼、方余碼）是雙值自相關(guān)序列的特例，是根據(jù)平方余數(shù)差集構(gòu)成的。

若某個(gè)與p互素的整數(shù)i使a2≡i(modp)有解，則i是模p的平方余數(shù)。當(dāng)p=4t-1為一素?cái)?shù)時(shí)，模p的平方余數(shù)構(gòu)成一個(gè)差集。根據(jù)此差集構(gòu)成的雙值自相關(guān)碼稱為平方剩余碼。例2.8求t=3，p=11的平方余數(shù)碼。a:0,1,2,3,4,5,6,7,8,9,10i:0,1,4,9,5,3,3,5,9,4,1即{1，3，4，5，9}是v=11,k=5,λ=2的差集，對(duì)應(yīng)的平方余數(shù)碼為{-1,1,-1,1,1,1,-1,-1,-1,1,-1}其自相關(guān)函數(shù)為因此求平方余數(shù)碼的方法為：當(dāng)p=4t-1為素?cái)?shù)時(shí)，存在周期為p的偽隨機(jī)序列｛x0,x1,x2,…,xp-1｝，其中(2－2－3)

又當(dāng)p為奇數(shù)時(shí)，上面定義的xi正是所謂的勒讓德（Legender）符號(hào):于是有,因此平方余數(shù)碼又被稱為勒讓德碼，簡(jiǎn)稱L碼或L序列。2.2.3孿生素?cái)?shù)碼

孿生素?cái)?shù)碼又稱TP碼，它的構(gòu)造與雅克比符號(hào)有關(guān)，雅可比符號(hào)的定義如下：其中，(i,n)=1，n=p1p2…ps，且pk都是奇素?cái)?shù)。當(dāng)n=p(p+2)，即p1=p,p2=p+2時(shí),有這時(shí)存在周期為n的孿生素?cái)?shù)碼{xi}，其中(2－2－4)這種孿生素?cái)?shù)碼也是偽隨機(jī)序列。例2.9構(gòu)造n=15=3(3+2)的孿生素?cái)?shù)碼。則孿生素?cái)?shù)碼為1,1,1,-1,1,1,-1,-1,1,-1,1,-1,-1,-1,-1孿生素?cái)?shù)碼序列的自相關(guān)函數(shù)為可見(jiàn)，它也是一種狹義偽隨機(jī)序列。2.2.4巴克序列

若一個(gè)序列的局部自相關(guān)函數(shù)為當(dāng)它滿足下式時(shí)，這種序列稱為巴克序列或巴克碼。巴克序列也是一種相關(guān)特性很好的偽隨機(jī)序列，但是目前已知的巴克序列很少，且長(zhǎng)度較短，如表2－1所示。表2-1目前已知的巴克序列

目前已經(jīng)證明不存在p>13的奇數(shù)長(zhǎng)度的巴克碼，偶數(shù)長(zhǎng)度巴克碼的可能長(zhǎng)度為4t2，但是16≤p≤11664(2≤t≤54)的偶數(shù)長(zhǎng)度巴克碼不存在。t>54的巴克碼的情況還不清楚。 2.3

m序列

2.3.1

m序列的定義

m序列是最大長(zhǎng)度的線性移位寄存器序列。

在“脈沖與數(shù)字電路”課程中，我們了解到移位寄存器的概念，并知道可以用移位寄存器來(lái)產(chǎn)生周期序列。為了方便對(duì)序列進(jìn)行研究，我們可以用數(shù)學(xué)方法對(duì)移位寄存器（序列產(chǎn)生器）進(jìn)行描述。移位寄存器的后續(xù)狀態(tài)可以用當(dāng)前狀態(tài)及特定矩陣來(lái)表示，該矩陣是n×n階矩陣，稱為A矩陣。例如，圖2－1所示的移位寄存器（序列產(chǎn)生器）的A矩陣為圖2－1移位寄存器序列產(chǎn)生器

可以看出，A矩陣的第m行對(duì)應(yīng)移位寄存器第m級(jí)的饋入狀態(tài)。在給定移位寄存器的初始狀態(tài)后，可由A矩陣求出后續(xù)狀態(tài)，即(2－3－1)故由式（2－3－1)顯然有(2－3－2)當(dāng)存在Ak=I時(shí)有X(j+k)=X(j)，即寄存器中的內(nèi)容在第j個(gè)狀態(tài)和第j+k個(gè)狀態(tài)是相同的,也就是說(shuō)序列產(chǎn)生器從第j個(gè)狀態(tài)開(kāi)始，經(jīng)過(guò)k次狀態(tài)轉(zhuǎn)移后，又回到第j個(gè)狀態(tài)。假如對(duì)0<l<k有X(j+l)≠X(j)，則該序列產(chǎn)生器以第j個(gè)狀態(tài)為初始狀態(tài)所產(chǎn)生的序列長(zhǎng)度為k。因此，對(duì)于最大長(zhǎng)度線性移位寄存器(序列產(chǎn)生器)，必然有（2-3-3）對(duì)于一個(gè)n級(jí)序列產(chǎn)生器，其A矩陣的a1n必為1。否則，該序列產(chǎn)生器就必然退化成為級(jí)數(shù)小于n的移位寄存器（序列產(chǎn)生器）。

對(duì)于簡(jiǎn)單移位寄存器（序列產(chǎn)生器），其A矩陣有如下形式：(2－3－4)對(duì)于n×n階矩陣A，λ為其特征值，則有即在二元域內(nèi)-1=+1，上式可簡(jiǎn)化為定義，即特征方程為(2－3－5)特征多項(xiàng)式定義為(2－3－6)

例2.10對(duì)于圖2－2給出的簡(jiǎn)單移位寄存器（序列產(chǎn)生器），求其特征方程和特征多項(xiàng)式。(2－3－7)圖2－2簡(jiǎn)單移位寄存器（序列產(chǎn)生器）對(duì)于圖2－3所示的序列產(chǎn)生器，有將之代入生成函數(shù)式，得圖2－3序列產(chǎn)生器方框圖即又因在二元域內(nèi),故（2－3－8a）如對(duì)上式用長(zhǎng)除法，可獲得多項(xiàng)式a0+a1x+a2x2+…。如取a-1=a-2=…=a1-n=0及a-n=-1，則生成函數(shù)可以簡(jiǎn)化為(2－3－8b)即特征多項(xiàng)式的倒數(shù)為初始狀態(tài)為00…01時(shí)的生成函數(shù)。圖2－4序列產(chǎn)生器方框圖

例2.11對(duì)于圖2－4給出的序列產(chǎn)生器，利用生成函數(shù)求初始狀態(tài)為001的輸出序列。

解由圖可知，c0=c1=c3=1,c2=0,故用長(zhǎng)除法有可得輸出序列為111010011…。

定理2.2取特征多項(xiàng)式f1(x)、f2(x)，則由這兩個(gè)多項(xiàng)式分別產(chǎn)生的序列的模2和得到的序列，可以由以f1(x)·f2(x)作為特征多項(xiàng)式的簡(jiǎn)單移位寄存器來(lái)產(chǎn)生。

證明定義deg［g(x)］表示g(x)的階數(shù),Gi(x)表示以fi(x)為特征多項(xiàng)式生成的序列的生成函數(shù)。于是有又因?yàn)樗杂幸虼?，G1（x）+G2（x）是分子階數(shù)小于分母階數(shù)的某一適當(dāng)?shù)纳珊瘮?shù)，且其特征多項(xiàng)式為f1（x）·f2（x）。證畢。即設(shè)由，有所以，{an}是周期為p的序列。若一個(gè)多項(xiàng)式f(x)不能被1和f(x)之外的其他多項(xiàng)式整除，則該多項(xiàng)式被稱為既約多項(xiàng)式，或者說(shuō)該多項(xiàng)式是既約的。

定理2.5若n級(jí)移位寄存器產(chǎn)生的是周期為2n-1的最大長(zhǎng)度線性移位序列，則它的特征多項(xiàng)式是既約的。

證明下面我們用反證法來(lái)證明該定理。

假設(shè)該產(chǎn)生器的特征多項(xiàng)式f(x)不是既約的，有兩個(gè)獨(dú)立的因子，即f(x)=f1(x)·f2(x),則這與 相矛盾，故假設(shè)不成立。

例2.12

f(x)=x6+x3+1是既約多項(xiàng)式，但是由于f(x)|1+x9，由定理2.3可知，以該多項(xiàng)式作為特征多項(xiàng)式的序列產(chǎn)生器，在初始狀態(tài)為000001時(shí)將產(chǎn)生長(zhǎng)度為9的序列，而不是長(zhǎng)度為63的m序列。人們已經(jīng)證明：每個(gè)階數(shù)大于1的既約多項(xiàng)式，都能整除多項(xiàng)式1+x2n-1。由該結(jié)論容易得到下面的定理。

定理2.6

若給定特征多項(xiàng)式為n階既約多項(xiàng)式，則移位寄存器產(chǎn)生的序列的周期是2n-1的因子。

推論：若N=2n-1是素?cái)?shù)，則每個(gè)既約多項(xiàng)式對(duì)應(yīng)一個(gè)最大長(zhǎng)度線性移位序列。

當(dāng)N=2n-1不是素?cái)?shù)，而我們需要獲得一個(gè)n級(jí)的m序列時(shí)，就必須限定特征多項(xiàng)式為本原多項(xiàng)式。當(dāng)一個(gè)n階既約多項(xiàng)式能整除多項(xiàng)式1+xm，且m≥2n-1時(shí)，這個(gè)n階既約多項(xiàng)式被稱為本原多項(xiàng)式。

定理2.7以n階本原多項(xiàng)式作為特征多項(xiàng)式生成的是長(zhǎng)度為2n-1的最大長(zhǎng)度線性移位序列，即m序列。

由生成函數(shù)的表示式可見(jiàn)，初始條件00…001下產(chǎn)生的序列具有最長(zhǎng)的周期，這是因?yàn)镚(x)的分子是1，與分母不可能存在公因子。

當(dāng)生成函數(shù)的分子與分母存在公因子時(shí)，就會(huì)出現(xiàn)相消的情況，這相當(dāng)于分母階數(shù)降低，其產(chǎn)生的序列長(zhǎng)度就有可能降低。2.3.2

m序列的隨機(jī)特性

1.平衡特性

m序列在每個(gè)周期的2n-1個(gè)序列中，1出現(xiàn)2n-1次，0出現(xiàn)2n-1-1次，1比0多出現(xiàn)一次。

證明

m序列的周期為N=2n-1，其移位寄存器的狀態(tài)共有1~2n-1個(gè)，即00…00100…01000…011

11…10011…10111…11011…111…其每一列對(duì)應(yīng)m序列的一個(gè)周期中的輸出序列（前后順序不同），由于狀態(tài)中沒(méi)有全0態(tài)，故末尾1狀態(tài)比0狀態(tài)多1個(gè)，即1出現(xiàn)2n-1次，0出現(xiàn)2n-1-1次。

得證。

2.游程特性

在m序列的每個(gè)周期中，共有2n-1個(gè)游程，其中0游程和1游程的數(shù)目各占一半；并且對(duì)于n>2，當(dāng)1≤k≤n-2時(shí)，長(zhǎng)為k的游程占游程總數(shù)的1/2k,其中0游程和1游程的數(shù)目各占一半,長(zhǎng)為n-1的游程只有一個(gè)，為0游程，長(zhǎng)為n的游程也只有一個(gè)，為1游程。(2-3-9)4、相關(guān)特性

m序列的自相關(guān)函數(shù)為

證明：由m序列的移位相加特性，m序列與其移位序列模2后是此序列的另一位移序列。即

由序列自相關(guān)函數(shù)的定義：又根據(jù)m序列的平衡特性，有A-D=-1，因此當(dāng)j=0時(shí)，結(jié)果顯然。證畢。2.3.3

m序列的構(gòu)造

由定理2.7可知：每個(gè)n階本原多項(xiàng)式對(duì)應(yīng)一個(gè)相應(yīng)階的m序列，即找到一個(gè)本原多項(xiàng)式，即可用它作為特征多項(xiàng)式產(chǎn)生一個(gè)m序列。

附錄中給出了既約多項(xiàng)式表，表中后綴英文字母為A、B、C、D的為非本原多項(xiàng)式，而后綴為E、F、G、H的為本原多項(xiàng)式。

表中以八進(jìn)制給出了多項(xiàng)式的系數(shù)，每一位代表3位系數(shù)。

例2.13求n=9的本原多項(xiàng)式1021E對(duì)應(yīng)的m序列。

解該本原多項(xiàng)式對(duì)應(yīng)的系數(shù)為1，000，010，001，即c0=c4=c9=1，c1=c2=c3=c5=c6=c7=c8=0,所以f(x)=x9+x4+1。對(duì)應(yīng)的線性移位寄存器如圖2－5所示。圖2－5m序列產(chǎn)生器原理方框圖

應(yīng)該注意的是：本原多項(xiàng)式的互反式還是本原多項(xiàng)式。

對(duì)于上例，1021的互反為1，000，100，001，即1041，對(duì)應(yīng)的特征多項(xiàng)式為f(x)=x9+x5+1。

當(dāng)給定m序列的長(zhǎng)度或階數(shù)后，我們就可以通過(guò)本原多項(xiàng)式的數(shù)目確定m序列的數(shù)目。為此，我們需要了解兩個(gè)數(shù)論函數(shù)。

1.歐拉函數(shù)

由算術(shù)的惟一分解定理可知，每個(gè)大于1的正整數(shù)n，可以用素?cái)?shù)的冪的乘積來(lái)表示，且是惟一的，即(2－3－10)其中，pi為第i個(gè)素?cái)?shù)，αi為對(duì)應(yīng)的素?cái)?shù)的冪。歐拉函數(shù)定義為(2－3－11)例2.14計(jì)算n=90的歐拉函數(shù)。

解由n=90=2×32×5得所以

2.莫比烏函數(shù)

莫比烏函數(shù)的定義為(2-3－12)其中，αi的定義與歐拉函數(shù)中的相同。例2.15計(jì)算n=90的莫比烏函數(shù)。

解由n=90=2×32×5得μ(90)=0。

人們證明：n階模2既約多項(xiàng)式的數(shù)目為(2－3－13)

例2.16計(jì)算n=6的既約多項(xiàng)式的數(shù)目。

解對(duì)于n=6，d=1,2,3,6,則有人們證明：n階模2本原多項(xiàng)式的數(shù)目為(2－3－14)

例2.17計(jì)算n=6的本原多項(xiàng)式的數(shù)目。即碼長(zhǎng)為63的m序列共有6個(gè)。 2.4

Gold序列族

上一節(jié)中討論了最大長(zhǎng)度線性移位寄存器序列，即m序列。m序列具有優(yōu)良的自相關(guān)特性，但是使用m序列作為CDMA通信地址碼時(shí)，其主要問(wèn)題是由m序列組成的互相關(guān)特性很好的序列集很小。例如，階數(shù)為9的m序列（序列長(zhǎng)為511）有48個(gè)，取出一個(gè)序列，可以找出12個(gè)m序列與其最大互相關(guān)值為33，但找不到多于3個(gè)序列的集合，其中任意兩個(gè)序列之間的最大互相關(guān)值小于等于33。即約束最大互相關(guān)值為33的、碼長(zhǎng)為511的m序列集不大于3個(gè)。顯然，若要求地址數(shù)較多，只有降低互相關(guān)要求。當(dāng)最大互相關(guān)值不超過(guò)65時(shí)，可以從48個(gè)序列中挑選出幾組集合大小為6的m序列集。當(dāng)階數(shù)增加，如n=12時(shí)，滿足條件的集合大小也不超過(guò)6。因此對(duì)于多址通信應(yīng)用來(lái)說(shuō)，如果用m序列實(shí)現(xiàn)CDMA，其地址數(shù)太少了。這樣，人們就開(kāi)始尋找能夠提供更多地址數(shù)的序列。

Gold序列具有良好的自相關(guān)和互相關(guān)特性，且地址數(shù)遠(yuǎn)遠(yuǎn)大于m序列地址數(shù)。由于Gold序列也是基于m序列而產(chǎn)生的，因此，其序列產(chǎn)生器的結(jié)構(gòu)也比較簡(jiǎn)單，且控制起來(lái)也比較容易。例如碼長(zhǎng)為511的m序列共有48個(gè)，若要尋找一個(gè)511位m序列組，且要求碼組內(nèi)不同碼的互相關(guān)絕對(duì)值小于33，則最多只能找到3個(gè)滿足條件的碼；而在相同約束條件下的Gold序列有512個(gè)。2.4.1

m序列優(yōu)選對(duì)

設(shè)q是一個(gè)正整數(shù)，從序列的每q個(gè)元素中取一個(gè)，從而構(gòu)成一個(gè)新的序列v，即vi=uqi，i∈Z,則稱序列u以q采樣而得到序列v，或說(shuō)序列v是u的q采樣，記作v=u［q］。

對(duì)于m序列u來(lái)說(shuō)，當(dāng)N、q的最大公約數(shù)為1，即gcd(N,q)=1時(shí)，通過(guò)采樣就可以得到與序列u具有相同周期的序列，這種采樣常稱為本征采樣。

在用本原多項(xiàng)式f(x)產(chǎn)生的m序列u的N個(gè)平移等價(jià)序列中，存在惟一的一個(gè)序列u,稱為特征序列或m序列u的特征相位，使得結(jié)合采樣的概念，上述的性質(zhì)可以改寫為其中C1、C2是本征陪集，C3、C4是非本征陪集，C5是零陪集。以3采樣：以5采樣：以7采樣:以11采樣：以15采樣:圖2－6

5階m序列的采樣關(guān)系圖其中q、q′為對(duì)稱點(diǎn)上的采樣值。圖2－6中：（3）互反特性：在通過(guò)圓心的同一軸線上的兩個(gè)m序列是一對(duì)互反序列。

類似與n=5，可得n=6,7,8,9,10,……的采樣關(guān)系圖（其中n=8,9,10時(shí)為雙層序列，同一軸線上內(nèi)層序列與另一端的外層序列互反）。

m序列優(yōu)選對(duì)是指在m序列集中，互相關(guān)函數(shù)絕對(duì)值的最大值|RXY(j)|max最接近或達(dá)到互相關(guān)下限（最小值）的一對(duì)m序列。那么m序列的互相關(guān)下限值是多少呢？設(shè)有兩個(gè)長(zhǎng)度為N的序列X、Y，其自相關(guān)函數(shù)分別為則有(2-4-1)由柯西不等式(2－4－2)則有(2－4－3)式（2－4－3）給出了兩個(gè)序列的自相關(guān)特性和互相關(guān)特性之間的約束關(guān)系。對(duì)于m序列，有(2－4－4)所以，兩個(gè)m序列的互相關(guān)值中至少有一個(gè)值的絕對(duì)值超過(guò)事實(shí)上已經(jīng)證明，兩個(gè)m序列的互相關(guān)值至少有一個(gè)滿足下式(2－4－5)顯然，如果e小，則RAB（i）也小。n為奇數(shù)時(shí)，e最小可取1；n為偶數(shù)且不能被4整除時(shí)，e最小可取2。(2－4－6)則這對(duì)m序列被稱為m序列優(yōu)選對(duì)。寫成更具體的形式為：設(shè)A、B分別是n級(jí)本原多項(xiàng)式f(x)、g(x)產(chǎn)生的m序列，當(dāng)它們的互相關(guān)函數(shù)滿足(2-4-7)2.4.2

Gold序列族

Gold序列是由兩個(gè)碼長(zhǎng)相等、碼時(shí)鐘速率相同的m序列優(yōu)選對(duì)模2和構(gòu)成的。每改變兩個(gè)m序列的相對(duì)相移就可以得到一個(gè)Gold序列，再加上兩個(gè)m序列，共有2n+1個(gè)Gold序列。Gold序列族中除了兩個(gè)m序列外，其他序列都具有三值自相關(guān)特性，且都具有三值互相關(guān)特性。

假設(shè)一個(gè)由m序列優(yōu)選對(duì)u、v構(gòu)成的Gold序列族，任取其中兩個(gè)序列Ti1uTj1v和Ti2uTj2v，分析它們的互相關(guān)函數(shù)分布情況。其中，I、J是與i1、i2、j1、j2、l及序列u、v相關(guān)的非負(fù)整數(shù)?？梢?jiàn)，這兩個(gè)Gold序列的互相關(guān)函數(shù)值就是u、v平移等價(jià)序列的互相關(guān)函數(shù)值。經(jīng)過(guò)研究后發(fā)現(xiàn)，Gold序列互相關(guān)函數(shù)值分布如表2－2所示。

例2.20畫出用兩個(gè)特征多項(xiàng)式分別為f1（x）=x6+x+1、f2(x)=x6+x5+x2+x+1的m序列構(gòu)成的Gold序列產(chǎn)生器的方框圖。其并聯(lián)型結(jié)構(gòu)的Gold序列產(chǎn)生器如圖2－7所示。根據(jù)線性序列的特性，兩個(gè)序列的模2和序列可以以這兩個(gè)序列的特征多項(xiàng)式的乘積作為特征多項(xiàng)式的序列產(chǎn)生器來(lái)產(chǎn)生。Gold序列正是兩個(gè)m序列的模2和序列，因此可以用這種結(jié)構(gòu)來(lái)產(chǎn)生，這種產(chǎn)生器被稱為串連型的Gold序列產(chǎn)生器。圖2－7并聯(lián)型Gold序列產(chǎn)生器

例2.21給出例2.20中Gold序列產(chǎn)生器的串連型結(jié)構(gòu)產(chǎn)生器。

由例2.20可得串連型產(chǎn)生器的特征多項(xiàng)式為其產(chǎn)生器的方框圖如圖2-8所示。圖2－8串連型Gold序列產(chǎn)生器如果產(chǎn)生Gold序列的m序列的特征多項(xiàng)式是n級(jí)的，則串連型產(chǎn)生器的特征多項(xiàng)式就是2n級(jí)的。而由前面的討論可知，2n級(jí)特征多項(xiàng)式的線性反饋產(chǎn)生器最長(zhǎng)可以產(chǎn)生22n-1長(zhǎng)度的序列。因此，串連型產(chǎn)生器產(chǎn)生的有可能不是所需要的Gold序列。此時(shí)必須求出需要產(chǎn)生的Gold序列的一個(gè)2n長(zhǎng)度相位，作為產(chǎn)生器的初始相位，以保證產(chǎn)生所需序列。2.4.3平衡Gold序列

碼長(zhǎng)為2n-1的Gold序列族中的Gold序列按照平衡性，可以分為平衡Gold序列和非平衡Gold序列。平衡Gold序列中1比0多一個(gè)，非平衡Gold序列中1和0的數(shù)量差大于1。

表2－3給出了n為奇數(shù)的Gold平衡和非平衡序列的分布情況。表2-3

n為奇數(shù)的Gold平衡和非平衡序列數(shù)量表

平衡Gold序列的產(chǎn)生與m序列的特征相位有關(guān)。設(shè)序列{a}是用n級(jí)本原多項(xiàng)式f(x)生成的m序列，其特征相位由g(x)/f(x)確定，多項(xiàng)式g(x)由下式確定(2－4－9)其特征相位生成函數(shù)為(2－4－10)例2.22求本原多項(xiàng)式f(x)=x5+x2+1的特征相位，并驗(yàn)證處于特征相位的序列的隔1抽樣序列是否與原序列一致。因?yàn)閚=5為奇數(shù)，所以用長(zhǎng)除法，得即特征相位為10000，處在特征相位的序列及隔1抽樣序列分別為100001010111011000111……10000101011……可見(jiàn)，其隔1抽樣序列與原序列是完全相同的。由本原多項(xiàng)式的特性，有f(x)=1+…，n為奇數(shù)時(shí)，根據(jù)式（2－4－9），有g(shù)(x)=1+…。由式（2－4－10）可得：n為奇數(shù)時(shí)，處于特征相位的序列首位必為1；n為偶數(shù)時(shí)，處于特征相位的序列首位必為0。

下面我們給出一種產(chǎn)生平衡Gold序列的具體方法：設(shè)序列A和B是一對(duì)m序列優(yōu)選對(duì),B=A［q］，且滿足優(yōu)選對(duì)約束關(guān)系q=2k+1；使序列B處于特征相位，循環(huán)移位序列A，直到它的首位與B序列的首位相異，當(dāng)處于這種相對(duì)相位時(shí)，A與B的模2和就是平衡Gold序列。

例2.23由附錄中既約多項(xiàng)式表可知，n=5的m序列特征多項(xiàng)式（1）45E產(chǎn)生的序列為A，取k=2、e=gcd(5,2)=1，則根據(jù)平衡Gold序列的產(chǎn)生方法，q=2k+1=5，A［5］對(duì)應(yīng)的m序列A的優(yōu)選對(duì)序列的特征多項(xiàng)式為（5）67H。下面求出由這兩個(gè)m序列產(chǎn)生的平衡Gold序列。解由式(2－4－9)、式(2－4－10)得序列B的特征相位生成函數(shù)為則處于特征相位的序列B為1110110011100001101010010001011以1+x2作分子，求得此相位上的序列A為1000010101110110001111100110100以為基準(zhǔn)，循環(huán)移動(dòng){a}使{a}的0對(duì)準(zhǔn)的第一個(gè)1，或以{a}為基準(zhǔn)，移動(dòng)使的第一個(gè)1對(duì)準(zhǔn){a}的0。循環(huán)移動(dòng){a}，使{a}的第一個(gè)0對(duì)準(zhǔn)的第一個(gè)1，得到模2和后的平衡Gold序列為111011001110000110101001000101100001010111011000111110011010011110011000001101110101011100010

例2.24由附錄中既約多項(xiàng)式表可知，n=6的m序列特征多項(xiàng)式（1）103F產(chǎn)生的序列為A，取k=2，e=gcd(5,2)=2,6/2＝3為奇正整數(shù)，則根據(jù)平衡Gold序列產(chǎn)生方法，q=2k+1=5，A［5］對(duì)應(yīng)的m序列A的優(yōu)選對(duì)序列的特征多項(xiàng)式為（5）147H。下面求出由這兩個(gè)m序列產(chǎn)生的平衡Gold序列。解：由式(2－4－9)、式(2－4－10)得序列B的特征相位生成函數(shù)為得處于特征相位的序列B為01101，00010，00010，11001，01010，01001，11100，00011，01110，01100，01110，10111，111以1為分子，求得序列A的生成函數(shù)為得序列A為11111，10101，01100，11011，10110，10010，01110，00101，11100，10100，01100，00100，000A序列首位與B序列相異，其模2和產(chǎn)生的平衡Gold序列如下：10010，10111，01110，00010，11100，11011，10010，00110，10010，11000，00010，10011，111序列中“1”的個(gè)數(shù)為32個(gè)，是平衡Gold序列。

將產(chǎn)生平衡Gold序列的步驟歸納如下：

（1）按照平衡Gold序列產(chǎn)生的約束條件，找到一對(duì)m序列優(yōu)選對(duì)及其對(duì)應(yīng)的特征多項(xiàng)式fa(x)和fb(x)。

（2）將B序列作為參考序列，按照式(2－4－9)和式（2－4－10）求出其特征相位及處在特征相位上的序列。

（3）求出A序列（可以處在特征相位上，也可以不處在特征相位上）。

（4）循環(huán)移動(dòng)A序列，使其首序列起始碼元為“0”，然后將其與處于特征相位上的B序列模2和，即求得一個(gè)平衡Gold序列。

（5）重復(fù)步驟（4）直到得到所有的平衡Gold序列。

2.5截短m序列

上面介紹的m序列和Gold序列都是有特定長(zhǎng)度的，但是在實(shí)際的應(yīng)用中，往往所需要的序列是非標(biāo)準(zhǔn)長(zhǎng)度的。此時(shí)，可以將現(xiàn)有的序列截短后得到需要的長(zhǎng)度序列。截短m序列就是從m序列中截去一段得到N′<N的截短序列。

對(duì)m序列的截短相當(dāng)于使原序列在經(jīng)過(guò)N′個(gè)狀態(tài)后發(fā)生跳躍，跳過(guò)后續(xù)的ΔN=N-N′個(gè)狀態(tài)而回到原來(lái)的第一個(gè)狀態(tài)。截短序列具體實(shí)現(xiàn)的難易程度和狀態(tài)跳躍點(diǎn)的選擇有很大關(guān)系。(2－5－1)在n級(jí)線性移位寄存器中除全零狀態(tài)外，由n個(gè)元素組成的N-1個(gè)非零狀態(tài)一定要出現(xiàn)且只出現(xiàn)一次。因此總能在新的位移序列中找到一個(gè)從某一位(設(shè)為第k+q位)開(kāi)始由一個(gè)1和n-1個(gè)0組成的狀態(tài)，即(2－5－2)（2-5-3）

例2.25基于特征多項(xiàng)式f(x)=x4+x3+1的4級(jí)m序列，產(chǎn)生長(zhǎng)度為11的截短m序列。

解對(duì)于該m序列，當(dāng)初始狀態(tài)為(1111)時(shí)，根據(jù)式(2－3－8a)，序列的生成函數(shù)為產(chǎn)生的周期為15的序列為

000100110101111

將該序列循環(huán)左移11位，得到新序列

111100010011010

將上面兩個(gè)序列模2和得到

111000100110101從模2和序列中找到“1000”狀態(tài)，即可得到該m序列的“0100”狀態(tài)與“1100”狀態(tài)相差11個(gè)。即只要控制該m序列產(chǎn)生器在“1100”狀態(tài)時(shí)，不轉(zhuǎn)入其后續(xù)的“1000”狀態(tài)，而是進(jìn)入“0100”的后續(xù)狀態(tài)“1001”，此時(shí)恰好躍過(guò)4個(gè)狀態(tài)，而產(chǎn)生所需的11位截短m序列。圖2－9

N′=11的截短序列產(chǎn)生器（2）找出{ai+q}中的10…0狀態(tài)(共n個(gè)元素)。（3）{ai+q}的10…0狀態(tài)對(duì)應(yīng)的{ai+N′}中的狀態(tài)(例2.24中為1100)就是跳躍點(diǎn)，這一狀態(tài)也就是檢測(cè)器要檢測(cè)的狀態(tài)。

還有一種產(chǎn)生截短序列的方法，這種方法很容易尋找跳躍點(diǎn)，不要求跳躍點(diǎn)和初始狀態(tài)(參考點(diǎn))之間差別盡量小。這種方法是利用觸發(fā)器本身置位和清零的邏輯功能來(lái)實(shí)現(xiàn)狀態(tài)跳躍的。對(duì)于n級(jí)m序列發(fā)生器，可以以2n-1個(gè)非0狀態(tài)中的任一狀態(tài)作為參考點(diǎn)。若要求截短序列長(zhǎng)N′=k(1<k<2n-1)，從參考點(diǎn)出發(fā)，找出移位寄存器的第k個(gè)狀態(tài)，這個(gè)狀態(tài)就是檢測(cè)態(tài)。當(dāng)移位寄存器由初態(tài)出發(fā)到達(dá)第k個(gè)狀態(tài)時(shí)，檢測(cè)器送出一個(gè)脈沖，控制觸發(fā)器的清零端或置位端的連線(初態(tài)置位線)，使移位寄存器的k+1個(gè)狀態(tài)又回到初始狀態(tài)。1111→1110→1100→1000→0001→0010→0100→1001→0011→0110→1101→1010→0101→1011→0111→因此，N′=11的檢測(cè)態(tài)就是(1101)。根據(jù)檢測(cè)態(tài)設(shè)置狀態(tài)檢測(cè)線，根據(jù)初態(tài)(1111)設(shè)置初態(tài)置位線。當(dāng)檢測(cè)到1101狀態(tài)時(shí)，狀態(tài)檢測(cè)器送出一負(fù)脈沖至初態(tài)置位線，使?fàn)顟B(tài)跳回到初始狀態(tài)，完成截短功能。 2.6

M序列

M序列是碼長(zhǎng)為2n的周期序列，這是n級(jí)移位寄存器所能產(chǎn)生的最長(zhǎng)周期序列，所以稱之為最大長(zhǎng)度序列，又叫全長(zhǎng)序列。由于M序列中包含了全0狀態(tài)，因此用n級(jí)移位寄存器產(chǎn)生碼長(zhǎng)為2n的M序列時(shí)，其反饋邏輯函數(shù)不能表達(dá)為的形式，此時(shí)可以用更一般的布爾函數(shù)來(lái)表示其反饋邏輯關(guān)系。我們知道，任何一個(gè)布爾函數(shù)都可以表示成最小項(xiàng)的和（布爾或）運(yùn)算的形式，也可以用真值表的形式