1、通信原理1通信原理第第12章章 正交編碼與偽隨機序列正交編碼與偽隨機序列2第12章 正交編碼與偽隨機序列l引言引言正交編碼與偽隨機序列在數字通信技術中都是十分重要的。正交編碼不僅可以用作糾錯編碼，還可以用來實現碼分多址通信，目前已經廣泛用于蜂窩網中。偽隨機序列在誤碼率測量、時延測量、擴譜通信、密碼及分離多徑等方面都有著十分廣泛的應用。因此，本章將在簡要討論正交編碼概念之后，著重討論偽隨機序列及其應用。3第12章 正交編碼與偽隨機序列l12.2 正交編碼正交編碼n12.2.1 正交編碼的基本概念u正交性p若兩個周期為T的模擬信號s1(t)和s2(t)互相正交，則有同理，若M個周期為T的模擬信號s

2、1(t)，s2(t)，sM(t)構成一個正交信號集合，則有u互相關系數p對于二進制數字信號，用一數字序列表示碼組。這里，我們只討論二進制且碼長相同的編碼。這時，兩個碼組的正交性可用如下形式的互相關系數來表述。Tdttsts0210)()(Tdttsts0210)()( i j；i, j1, 2, , M4第12章 正交編碼與偽隨機序列設長為n的編碼中碼元只取值+1和-1，以及x和y是其中兩個碼組：其中 則x和y間的互相關系數定義為若碼組x和y正交，則必有(x, y) = 0。 ),(321nxxxxx),(321nyyyyyniyxii, 2 , 1),1, 1(,niiiyxnyx11),(

3、5第12章 正交編碼與偽隨機序列u正交編碼例如，下圖所示4個數字信號可以看作是如下4個碼組：按照互相關系數定義式計算容易得知，這4個碼組中任意兩者之間的相關系數都為0，即這4個碼組兩兩正交。我們把這種兩兩正交的編碼稱為正交編碼。s1(t)s2(t)s3(t)s4(t)1, 1, 1, 1(:)()1, 1, 1, 1(:)()1, 1, 1, 1(:)()1, 1, 1, 1(:)(4321tstststs6第12章 正交編碼與偽隨機序列u自相關系數：類似上述互相關系數的定義，可以對于一個長為n的碼組x定義其自相關系數為式中，x的下標按模n運算，即有xnk xk 。例如，設則有nijiixnj

4、xxnj1) 1( , 1 , 0,1)() 1, 1, 1, 1(),(4321xxxxx0)(4141) 3(1)(4141)2(0) 1111(41)(4141) 1 (141)0(342312414132413423141214433221411412xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxiiixiiixiiixiix7第12章 正交編碼與偽隨機序列u用二進制數字表示互相關系數p在二進制編碼理論中，常采用二進制數字“0”和“1”表示碼元的可能取值。這時，若規定用二進制數字“0”代替上述碼組中的“1”，用二進制數字“1”代替“1”，則上述互相關系數定義式將變為式中

5、，A x和y中對應碼元相同的個數； D x和y中對應碼元不同的個數。p例如，按照上式規定，上面例子可以改寫成DADAyx),() 1 , 0 , 1 , 0( : )()0 , 1 , 1 , 0( : )() 1 , 1 , 0 , 0( : )()0 , 0 , 0 , 0( : )(4321tstststs8第12章 正交編碼與偽隨機序列u用二進制數字表示自相關系數p上式中，若用x的j次循環移位代替y，就得到x的自相關系數x (j)。具體地講，令代入定義式就得到自相關系數x (j)。),(),(212121jnjjnxxxxxxyxxxxDADAyx),(9第12章 正交編碼與偽隨機序列

6、u超正交碼和雙正交碼p超正交碼：相關系數 的取值范圍在1之間，即有-1 +1。若兩個碼組間的相關系數 0，則稱這兩個碼組互相超正交。如果一種編碼中任兩碼組間均超正交，則稱這種編碼為超正交碼。例如，在上例中，若僅取后3個碼組，并且刪去其第一位，構成如下新的編碼：則不難驗證，由這3個碼組所構成的編碼是超正交碼。) 1 , 0 , 1 (:)( )0 , 1 , 1 (:)( ) 1 , 1 , 0(:)( 321tststs10第12章 正交編碼與偽隨機序列p雙正交編碼 由正交編碼和其反碼便可以構成雙正交編碼。例： 上例中正交碼為其反碼為上兩者的總體即構成如下雙正交碼：(0,0,0,0) (1,1

7、,1,1) (0,0,1,1) (1,1,0,0)(0,1,1,0) (1,0,0,1) (0,1,0,1) (1,0,1,0)此碼共有8種碼組，碼長為4，任兩碼組間的相關系數為0或1。)1 ,0,1 ,0(:)()0,1 ,1 ,0(:)()1 ,1 ,0,0(:)()0,0,0,0(:)(4321tstststs)0 , 1 , 0 , 1 () 1 , 0 , 0 , 1 ()0 , 0 , 1 , 1 () 1 , 1 , 1 , 1 (11第12章 正交編碼與偽隨機序列n12.2.2 阿達瑪矩陣u定義：p阿達瑪矩陣簡記為H矩陣。它是一種方陣，僅由元素+1和1構成，而且其各行（和列）是

8、互相正交的。最低階的H矩陣是2階的，即下面為了簡單，把上式中的1和1簡寫為和，這樣上式變成11112H H2H H12第12章 正交編碼與偽隨機序列階數為2的冪的高階H矩陣可以從下列遞推關系得出 H N H N / 2 H 2式中，N 2m； 直積。上式中直積是指將矩陣HN / 2中的每一個元素用矩陣H2代替。例如：2 22 22 22 22 2H HH HH HH HH HH HH H2413第12章 正交編碼與偽隨機序列p上面給出幾個H矩陣的例子，都是對稱矩陣，而且第一行和第一列的元素全為“”。我們把這樣的H矩陣稱為阿達瑪矩陣的正規形式正規形式，或稱為正規阿達瑪矩陣正規阿達瑪矩陣。4444

9、48H H- -H HH HH HH HH HH H2 214第12章 正交編碼與偽隨機序列u性質p在H矩陣中，交換任意兩行，或交換任意兩列，或改變任一行中每個元素的符號，或改變任一列中每個元素的符號，都不會影響矩陣的正交性質。因此，正規H矩陣經過上述各種交換或改變后仍為H矩陣，但不一定是正規的了。p按照遞推關系式可以構造出所有2k階的H矩陣。可以證明，高于2階的H矩陣的階數一定是4的倍數。不過，以4的倍數作為階數是否一定存在H矩陣，這一問題并未解決。p H矩陣是正交方陣。若把其中每一行看作是一個碼組，則這些碼組也是互相正交的，而整個H矩陣就是一種長為n的正交編碼，它包含n個碼組。因為長度為n

10、的編碼共有2n個不同碼組，現在若只將這n個碼組作為準用碼組，其余(2n - n)個為禁用碼組，則可以將其多余度用來糾錯。這種編碼在糾錯編碼理論中稱為里德-繆勒(Reed-Muller)碼。15第12章 正交編碼與偽隨機序列n 12.2.3 沃爾什函數和沃爾什矩陣u沃爾什函數定義式中 p = 0或1，j = 0，1，2，及指數中的j / 2表示取j / 2的整數部分。 u正弦和余弦函數可以構成一個完備正交函數系。由于正弦和余弦函數具有完備和正交性，所以由其構成的無窮級數或積分（即傅里葉級數和傅里葉積分）可以表示任一波形。類似地，由取值“1”和“1”構成的沃爾什函數也具有完備正交性，也可以用其表示

11、任一波形 )4/1(2 ,) 1()4/1(2 ,() 1(),2(2/jwaljwalpjwalpjpj2/1, 2/102/12/11), 0(wal16第12章 正交編碼與偽隨機序列u前8個沃爾什函數的波形示于下圖中 +10+10-1+10-1+10-1+10-1+10-1+10-1+10-117第12章 正交編碼與偽隨機序列u由于沃爾什函數的取值僅為“1”和“1”，所以可以用其離散的抽樣值表示成矩陣形式。例如，上圖中的8個沃爾什函數可以寫成如下沃爾什矩陣：由上圖和矩陣可以看出，沃爾什矩陣是按照每一行中“1”和“1”的交變次數由少到多排列的。沃爾什函數（矩陣）天生具有數字信號的特性，所以

12、它們在數字信號處理和編碼理論中有不小應用前景。 W W18第12章 正交編碼與偽隨機序列l12.3 偽隨機序列偽隨機序列n12.3.1 基本概念u什么是偽隨機噪聲？具有類似于隨機噪聲的某些統計特性，同時又能夠重復產生的波形。u優點：它具有隨機噪聲的優點，又避免了隨機噪聲的缺點，因此獲得了日益廣泛的實際應用。u如何產生偽隨機噪聲？目前廣泛應用的偽隨機噪聲都是由周期性數字序列經過濾波等處理后得出的。在后面我們將這種周期性數字序列稱為偽隨機序列。它有時又稱為偽隨機信號和偽隨機碼。n12.3.2 m序列um序列的產生：m序列是最長線性反饋移位寄存器序列的簡稱。它是由帶線性反饋的移存器產生的周期最長的一

13、種序列。19第12章 正交編碼與偽隨機序列p例： 下圖中示出一個4級線性反饋移存器。設其初始狀態為(a3, a2, a1, a0) = (1, 0, 0, 0)，則在移位1次時，由a3和a0模2相加產生新的輸入a4 = 1 0 = 1，新的狀態變為(a4, a3, a2, a1) = (1, 1, 0, 0)。這樣移位15次后又回到初始狀態(1, 0, 0, 0)。若初始狀態為全“0”，即(0, 0, 0, 0)，則移位后得到的仍為全“0”狀態。應該避免出現全“0”狀態，否則移存器的狀態將不會改變。 20第12章 正交編碼與偽隨機序列因為4級移存器共有24 = 16種可能的狀態。除全“0”狀態

14、外，只剩15種狀態可用。這就是說，由任何4級反饋移存器產生的序列的周期最長為15。我們常常希望用盡可能少的級數產生盡可能長的序列。由上例可見，一般來說，一個n級線性反饋移存器可能產生的最長周期等于(2n - 1)。我們將這種最長的序列稱為最長線性反饋移存器序列，簡稱m序列。 反饋電路如何連接才能使移存器產生的序列最長，這就是本節將要討論的主題。21第12章 正交編碼與偽隨機序列p一般的線性反饋移存器原理方框圖圖中各級移存器的狀態用ai表示，ai = 0或1，i 整數。反饋線的連接狀態用ci表示，ci1表示此線接通（參加反饋）；ci0表示此線斷開。反饋線的連接狀態不同，就可能改變此移存器輸出序列

15、的周期p。 22第12章 正交編碼與偽隨機序列p基本的關系式遞推方程 設一個n級移存器的初始狀態為：a1 a2 an，經過1次移位后，狀態變為a0 a1 an1。經過n次移位后，狀態為an1 an2 a0，上圖所示就是這一狀態。再移位1次時，移存器左端新得到的輸入an，按照圖中線路連接關系，可以寫為因此，一般說來，對于任意一個輸入ak，有稱為遞推方程它給出移位輸入ak與移位前各級狀態的關系。按照遞推方程計算，可以用軟件產生m序列，不必須用硬件電路實現。）（模210112211niininnnnnacacacacacaniikikaca123第12章 正交編碼與偽隨機序列特征方程（特征多項式）

16、ci的取值決定了移存器的反饋連接和序列的結構，故ci是一個很重要的參量。現在將它用下列方程表示： 特征方程式中xi僅指明其系數（1或0）代表ci的值，x本身的取值并無實際意義，也不需要去計算x的值。例如，若特征方程為則它僅表示x0，x1和x4的系數c0c1c41，其余的ci為0，即c2c30。按照這一特征方程構成的反饋移存器就是上圖所示的。niiinnxcxcxcxccxf02210)(41)(xxxf24第12章 正交編碼與偽隨機序列母函數我們也可以將反饋移存器的輸出序列 ak用代數方程表示為上式稱為母函數 。遞推方程、特征方程和母函數就是我們要建立的3個基本關系式。下面的幾個定理將給出它們

17、與線性反饋移存器及其產生的序列之間的關系。02210)(kkkxaxaxaaxG25第12章 正交編碼與偽隨機序列p定理【定理定理12.1】 式中，h(x)為次數低于f(x)的次數的多項式。【證】將遞推方程代入母函數，得到移項整理后，得到)()()(xhxGxf)()()(111)1()1(1011)1()1(110010 xGxcxaxaxaxcxaxaxaxaxcxaxcxxacxaxGniiiiiiiniiikkkiiiiniiiniikkikiikiikniikikkk niiiiiiiniiixaxaxaxcxGxc111)1()1(1)(126第12章 正交編碼與偽隨機序列將上式右

18、端用符號h(x)表示，并因c0 1，故上式變成 式中由此式可以看出，當電路給定后，h(x)僅決定于初始狀態(a-i a-1)。再將特征方程代入上式，最后得出niiiiiiiniiixaxaxaxcxGxc111)1()1(1)(1)()(0 xhxGxcniii niiiiiiixaxaxaxcxh111)1()1()()()()(xhxGxf27第12章 正交編碼與偽隨機序列在中，若a1 = 1，則h(x)的最高次項為xn-1；若a1 = 0，則最高項次數 0， f2(x)的次數為n2，n2 0，且有)()()(21xfxfxf)()()(xhxGxf)()()()()()()(2211xf

19、xhxfxhxfxhxGnnn2130第12章 正交編碼與偽隨機序列令則上式可以改寫成上式表明，輸出序列G(x)可以看成是兩個序列G1(x)和G2(x)之和，其中G1(x)是由特征多項式f1(x)產生的輸出序列，G2(x)是由特征多項式f2(x)產生的輸出序列。而且，由定理12.2可知，G1(x)的周期為G2(x)的周期為所以，G(x)的周期p應是p1和p2的最小公倍數LCMp1, p2，即上式表明，p 一定小于最長可能周期(2n - 1)。若f(x)可以分解成兩個相同的因子，即上面的f1(x)f2(x)，同樣可以證明p 2n1。所以，若f (x)能分解因子，必定有p 2n 1。【證畢】)(/

20、 )()();(/ )()(222111xfxhxGxfxhxG)()()(21xGxGxG1211np1222np 123212221212,21212121nnnnnnnppppLCMp31第12章 正交編碼與偽隨機序列【定理定理12.4】一個n級移存器的特征多項式f (x)若為既約的，則由其產生的序列A = ak 的周期等于使f (x)能整除的(xp + 1)中最小正整數 p。【證】若序列A 具有周期p，則有上式移項整理后，變成)(11)(1)()()()()()(1110111021110211101122101211101122100pppppppppppPppppPppppkkkx

21、axaaxxaxaaxxxaxaaxxaxaaxxaxaxaaxaxaxaxaxaxaaxaxGxfxh)()() 1()(1110pppxaxaaxfxxh32第12章 正交編碼與偽隨機序列由定理12.1可知，h(x)的次數比f (x)的低，而且現已假定f (x)為既約的，所以上式表明(xp + 1)必定能被f (x)整除。應當注意，此時序列A之周期p與初始狀態或者說與h(x)無關。當然，這里不考慮全“0”作為初始狀態。上面證明了若序列A具有周期p，則(xp +1)必能被f (x)整除。另一方面，若f(x)能整除(xp +1)，令其商為又因為在f (x)為既約的條件下，周期p與初始狀態無關，

22、現在考慮初始狀態a1a2an10，an1，由式可知，此時有h(x) = 1。故有)()() 1()(1110pppxaxaaxfxxh1110ppxbxbbniiiiiiixaxaxaxcxh111)1()1()(33第12章 正交編碼與偽隨機序列上式表明，序列A以p或p的某個因子為周期。若A以p的某個因子p1為周期，p1 p，則由式已經證明(xp1 + 1)必能被f (x)整除。所以，序列A之周期等于使f (x)能整除的中最小正整數p。【證畢】1110111011102111011)(1)()()(ppppppppppppxbxbbxxbxbbxbxbbxxxxbxbbxfxfxhxG)()

23、() 1()(1110pppxaxaaxfxxh34第12章 正交編碼與偽隨機序列p本原多項式定義：若一個n次多項式f(x)滿足下列條件：f (x)為既約的；f (x)可整除(xm + 1)，m = 2n 1；f (x)除不盡(xq + 1)，q m； 則稱 f (x)為本原多項式。由定理12.4可以簡單寫出一個線性反饋移存器能產生m序列的充要條件為：反饋移存器的特征多項式為本原多項式。35第12章 正交編碼與偽隨機序列【例】要求用一個4級反饋移存器產生m序列，試求其特征多項式。這時，n = 4，故此移存器產生的m序列的長度為m = 2n 1 = 15。由于其特征多項式f (x)應可整除(xm

24、 + 1) = (x15 + 1)，或者說，應該是(x15+1)的一個因子，故我們將(x15+1)分解因子，從其因子中找 f (x)：f(x)不僅應為(x15+1)的一個因子，而且還應該是一個4次本原多項式。上式表明，(x15+1)可以分解為5個既約因子，其中3個是4次多項式。可以證明，這3個4次多項式中，前2個是本原多項式，第3個不是。因為 111111223434415xxxxxxxxxxxx1115234xxxxxx36第12章 正交編碼與偽隨機序列這就是說，(x4 + x3 +x2 +x + 1)不僅可整除(x15+1)，而且還可以整除(x5+1)，故它不是本原的。于是，我們找到了兩個

25、4次本原多項式：和。由其中任何一個都可以產生m序列，用作為特征多項式構成的4級反饋移存器就是上圖中給出的。本原多項式表由上述可見，只要找到了本原多項式，我們就能由它構成m序列產生器。但是尋找本原多項式并不是很簡單的。經過前人大量的計算，已將常用本原多項式列成表備查。在下表中列出了部分已經找到的本原多項式。 1115234xxxxxx37第12章 正交編碼與偽隨機序列n本原多項式n本原多項式代數式8進制表示法代數式8進制表示法2345678910111213x2 + x + 1x3 + x + 1x4 + x + 1x5 + x2 + 1x6+ x + 1x7 + x3 + 1x8 + x4 +

26、 x3 + x2 + 1x9 + x4 + 1x10 + x3 + 1x11 + x2 + 1x12 + x6 + x4 + x + 1x13 + x4 + x3 + x + 171323451032114351021201140051012320033141516171819202122232425x14 + x10 + x6 + x + 1x15 + x + 1x16 + x12 + x3 + x + 1x17 + x3 + 1x18 + x7 + 1x19 + x5 + x2 + x + 1x20 + x3 + 1x21 + x2 + 1x22 + x + 1x23 + x5 + 1x2

27、4 + x7 + x2 + x + 1x25 + x3 + 14210310000321001340001110002012000047400001110000005200000034000004110000020720000001138第12章 正交編碼與偽隨機序列在制作m序列產生器時，移存器反饋線（及模2加法電路）的數目直接決定于本原多項式的項數。為了使m序列產生器的組成盡量簡單，我們希望使用項數最少的那些本原多項式。由表可見，本原多項式最少有3項（這時只需要用一個模2加法器）。對于某些n值，由于不存在3項的本原多項式，我們只好列入較長的本原多項式。由于本原多項式的逆多項式也是本原多項式，

28、例如， (x15 + 1)的因子中的(x4 + x + 1)與(x4 + x3 + 1)互為逆多項式，即10011與11001互為逆碼，所以在表中每一本原多項式可以組成兩種m序列產生器。39第12章 正交編碼與偽隨機序列在一些書刊中，有時將本原多項式用8進制數字表示。我們也將這種表示方法示于此表中右側。例如，對于n = 4表中給出“23”，它表示 2 3 0 1 00 1 1 c5c4c3c2c1c0即c0 = c1 = c4 = 1，c2 = c3 = c5 = 0。40第12章 正交編碼與偽隨機序列u m序列的性質p均衡性在m序列的一個周期中，“1”和“0”的數目基本相等。準確地說，“1”

29、的個數比“0”的個數多一個。【證】設一個m序列的周期為m = 2n 1，則此序列可以表示為由于此序列中任何相繼的n位都是產生此序列的n級移存器的一個狀態，而且此移存器共有m個不同狀態，所以可以把此移存器的這些相繼狀態列表，如下表所示。表中每一行為移存器的一個狀態。m個相繼的狀態構成此m序列的一個周期。由此表直接看出，最后一列的元素按自上而下排列次序就構成上式中的m序列。自然，其他各列也構成同樣的m序列，只是初始相位不同。10111210aaaaaaaaamnnn41第12章 正交編碼與偽隨機序列an-1anan+i-1an-2an-1an-2an-1an+i-2an-3an-2a2a3ai+2

30、a1a2a1a2ai+1a0a1a0a1aian-1a042第12章 正交編碼與偽隨機序列因為此表中每一元素為一位2進制數字，即ai (0, 1)，i = 0, 1, ，(m - 1)。所以表中每一位移存器狀態可以看成是一個n位2進制數字。這m個不同狀態對應1至(2n 1)間的m個不同的2進制數字。由于1和m = (2n 1)都是奇數，故1至(2n 1)間這m個整數中奇數比偶數多1個。在2進制中，奇數的末位必為“1”，偶數的末位必為“0”，而此末位數字就是表中最后一列。故表中最右列的相繼m個二進數字中“1”比“0”多一個。由于每列都構成一m序列，所以m序列中“1”比“0”多一個。【證畢】43第

31、12章 正交編碼與偽隨機序列p游程分布我們把一個序列中取值相同的那些相繼的（連在一起的）元素合稱為一個“游程游程”。在一個游程中元素的個數稱為游程長度。例如，在前例中給出的m序列可以重寫如下：在其一個周期（m個元素）中，共有8個游程，其中長度為4的游程有1個，即“1 1 1 1”，長度為3的游程有1個，即“0 0 0”，長度為2的游程有2個，即“1 1”和“0 0”，長度為1的游程有4個，即兩個“1”和兩個“0”。一般說來，在m序列中，長度為1的游程占游程總數的1/2；長度為2的游程占游程總數的1/4；長度為3的游程占1/8 ；. . . 。 1 0 0 0 1 1 1 1 0 1 0 1 1

32、 0 0 1 0 m 1544第12章 正交編碼與偽隨機序列嚴格講，長度為k的游程數目占游程總數的2-k，其中1 k (n-1)。而且在長度為k 的游程中其中1 k (n-2)，連“1”的游程和連“0”的游程各占一半。下面我們就來證明游程的這種分布規律。【證】在上表中，每一行有n個元素。我們考慮恰好含有連續 k 個“1”的那些行，它們具有形狀：其中左側(k + 2)個元素中兩端為“0”，中間全為“1”，這樣就保證恰好含有連續k個“1”，而右側的(n 2 k)個元素用“”表示，它們可以任意取值“0”或“1”，不受限制。在上表的一個周期(m = 2n 1行)中，符合上式形式的行的數目，按排列組合理

33、論可知，等于2n 2 k 。 0 1 1 1 1 0 k個(n 2 k)個（1 k n 2)45第12章 正交編碼與偽隨機序列由反饋移存器產生m序列的原理可知，形式如上式的一行中的k個“1”，必定經過逐次位移最后輸出，在輸出序列中構成長度為k的一個連“1”游程。反之，輸出序列中任何一個長度為k的連“1”游程，必然對應上表中這樣的一行。所以，在m序列一個周期中長度為k的連“1”游程數目也等于2n k 2。同理，長度為k的連“0”游程數目也等于2n k 2。所以長度為k的游程總數（包括連“1”和連“0”的兩種游程）等于在序列的每一周期中，長度在1 k (n - 2)范圍內的游程所包含的總碼元數等于

34、上式求和計算中利用了下列算術幾何級數公式：122222knknkn2114321222) 2(2322212nknnnnknnnk2110)1 ()1 (11)(qqrqqqrnaaqkrannnkk46第12章 正交編碼與偽隨機序列因為序列的每一周期中共有(2n 1)個碼元，所以除上述碼元外，尚余(2n 1) (2n 2n) = (2n 1)個碼元。這些碼元中含有的游程長度，從上表觀察分析可知，應該等于n和(n 1)，即應有長為n的連“1”游程一個，長為(n 1)的連“0”游程一個，這兩個游程長度之和恰為(2n 1)。并且由此構成的序列一個周期中，“1”的個數恰好比“0”的個數多一個。最后，

35、我們得到，在每一周期中，游程總數為計算上式求和時，利用了下列等比級數公式：所以，長度為k的游程占游程總數的比例為1211222nnkkn1111qqaaqnnkk)2(1,22211nkknkn47第12章 正交編碼與偽隨機序列由于長度為k = (n 1)的游程只有一個，它在游程總數2n-1中占的比例為1 / 2n-1 = 2-(n-1)，所以上式仍然成立。因此，可將上式改寫為長度為k的游程所占比例 = 2-k， 1 k (n 1)【證畢】48第12章 正交編碼與偽隨機序列p移位相加特性一個m序列Mp與其經過任意次延遲移位產生的另一個不同序列Mr模2相加，得到的仍是Mp的某次延遲移位序列Ms，

36、即Mp Mr = Ms現在分析一個m = 7的m序列Mp作為例子。設Mp的一個周期為1110010。另一個序列Mr是Mp向右移位一次的結果，即Mr的一個相應周期為0121001。這兩個序列的模2和為1110010 0111001 = 1001011上式得出的為Ms的一個相應的周期，它與Mp向右移位5次的結果相同。下面我們對m序列的這種移位相加特性作一般證明。49第12章 正交編碼與偽隨機序列【證】設產生序列Mp的n級反饋移存器的初始狀態如下圖所示。這一初始狀態也就是上表中第一行的a0a1a2an-1。由這一初始狀態代入遞推方程式得到移存器下一個輸入為若將序列Mp的初始狀態的r次延遲移位作為序列

37、Mr的初始狀態，則將Mr的初始狀態ar ar+1 ar+2 an+r+1代入遞推方程式，得到下一個輸入：02211acacacannnnrnrnrnrnacacaca221150第12章 正交編碼與偽隨機序列將上兩式相加（模2），得到上式右端n個括弧中兩元素模2相加的結果一定是上表中另一行的元素。這是因為表中的各行包含了除全“0”外的全部n位二進數字。設相加結果為則上式可以改寫為上式表明(an + an+r)仍為原n級反饋移存器按另一初始狀態(ai+n-1 ai+n-2 ai+1 ai)產生的輸入，這是因為c1c2 cn未改變，移存器的反饋線接法也未改變。這個初始狀態比Mp的初始狀態延遲了i位

38、。故序列Mp和Mr之和是 Mp經過延遲i位的移位序列。【證畢】)()()(0222111rnrnnrnnrnnaacaacaacaaiininiaaaa121inninirnnacacacaa221151第12章 正交編碼與偽隨機序列p自相關函數現在我們討論m序列的自相關函數。由12.2節互相關系數定義式得知 ，m序列的自相關函數可以定義為：式中 A m序列與其j次移位序列一個周期中對應元素相同的數目； D m序列與其j次移位序列一個周期中對應元素不同的數目； m m序列的周期。上式還可以改寫成如下形式：mDADADAj)(maaaajjiijii的數目的數目10)(52第12章 正交編碼與偽

39、隨機序列由m序列的延遲相加特性可知，上式分子中的aiai+j仍為m序列的一個元素。所以上式分子就等于m序列一個周期中“0”的數目與“1”的數目之差。另外，由m序列的均衡性可知，m序列一個周期中“0”的數目比“1”的數目少一個。所以上式分子等于1。這樣，就有當j = 0時，顯然(0) = 1。所以，我們最后寫成：不難看出，由于m序列有周期性，故其自相關函數也有周期性，周期也是m，即而且 ( j )是偶函數，即有121,1)(mjmj，當1, 2, 1,10, 1)(mjmjj當當, 2, 1,),()(kkmjkmjj當整數jjj),()(53第12章 正交編碼與偽隨機序列上面數字序列的自相關函

40、數 ( j )只定義在離散的點上（j只取整數）。但是，若把m序列當作周期性連續函數求其自相關函數，則從周期函數的自相關函數的定義：式中 T0 s(t)的周期，可以求出其自相關函數R()的表示式為 2/2/000)()(1)(TTdttstsTR其他處,/1, 2 , 1 , 0,0,11)(0000mimTiTiTTmR54按照上面的公式畫出的 ( j )和R()的曲線示于下圖中。圖中的圓點表示j取整數時的 ( j )取值，而折線是R()的連續曲線。可以看出，兩者是重合的。由圖還可以看出，當周期T0非常長和碼元寬度T0 / m極小時，R()近似于沖激函數(t)的形狀。由上述可知，m序列的自相關

41、函數只有兩種取值：0和(1/m)。有時把這類序列稱為雙值自相關雙值自相關序列。第12章 正交編碼與偽隨機序列(j)T0R() 55第12章 正交編碼與偽隨機序列p功率譜密度信號的自相關函數與功率譜密度構成一對傅里葉變換。因此，很容易對m序列的自相關函數式作傅里葉變換，求出其功率譜密度按照上式畫出的曲線示于下圖中。由此圖可見，在T0 和m/T0 時，Ps()的特性趨于白噪聲的功率譜密度特性。)(12)2/()2/sin(1)(2002002mTnmTmTmmPnns56第12章 正交編碼與偽隨機序列p偽噪聲特性我們對一正態分布白噪聲取樣，若取樣值為正，則記為“”；若取樣值為負，則記為“”。將每次

42、取樣所得極性排成序列，例如這是一個隨機序列，它具有如下3個基本性質：序列中“”和“”的出現概率相等。序列中長度為1的游程約占1/2；長度為2的游程約占1/4；長度為3的游程約占1/8；.。一般說來，長度為k的游程約占1/2k。而且在長度為k的游程中，“”游程和“”游程約各占一半。由于白噪聲的功率譜密度為常數，功率譜密度的逆傅里葉變換，即自相關函數，為一沖激函數 ()。當 0時， ()0。僅當 = 0時， ()是個面積為1的脈沖。57第12章 正交編碼與偽隨機序列由于m序列的均衡性、游程分布和自相關特性與上述隨機序列的基本性質極相似，所以通常將m序列稱為偽噪聲(PN)序列，或稱為偽隨機序列。但是

43、，具有或部分具有上述基本性質的PN序列不僅只有m序列一種。m序列只是其中最常見的一種。除m序列外，M序列、二次剩余序列（或稱為Legendre序列）、霍爾(Hall)序列和雙素數序列等都是PN序列。58第12章 正交編碼與偽隨機序列l59第12章 正交編碼與偽隨機序列n12.3.3 其他偽隨機序列簡介 uM序列序列p定義：由非線性反饋移存器產生的周期最長的序列稱為M序列。由上節對m序列產生器的分析可知，一個n級m序列產生器只可能有(2n 1)種不同的狀態。但是n級移存器最多可有2n種狀態，在m序列中不能出現的是全“0”狀態。在線性反饋條件下，全“0”狀態出現后，產生器的狀態將不會再改變；但是在

44、非線性反饋條件下，卻不一定如此。因此，非線性反饋移存器的最長周期可達2n，我們稱這種周期長達2n的序列為M序列序列。60第12章 正交編碼與偽隨機序列pM序列的產生方法目前，如何產生M序列的問題，尚未從理論上完全解決，人們只找到很少幾種構造它的方法。下面僅簡單介紹利用m序列產生器構成M序列產生器的方法。首先觀察右圖中的例子。它是一個n = 4級的m序列產生器。圖中給出了它的15種狀態。若使它增加一個“000”狀態，就可變成M序列產生器了。61第12章 正交編碼與偽隨機序列因為移存器中后級狀態必須是由其前級狀態移入而得，故此“0000”狀態必須處于初始狀態“1000”之前和“0001”狀態之后。

45、這就是說，我們需要將其遞推方程修改為非線性方程，使“0001”狀態代入新的遞推方程后，產生狀態“0000”（而不是“1000”），并且在“0000”狀態代入后產生狀態“1000”（而不是保持“0000”不變）。修改前的遞推方程為為滿足上述要求，修改后的遞推方程應為411kkniikikaaaca41321321414321432141ikkkikikkkkkkkkkkkkkkkkaaaacaaaaaaaaaaaaaaaa62第12章 正交編碼與偽隨機序列對于n級m序列產生器也一樣。為使n級m序列產生器變成M序列產生器，也只需使其遞推方程改為有了遞推方程，就不難構造出此M序列產生器。例如用這種方

46、法得到的一個4級M序列產生器如下圖所示。11141121njikniikiinkkkikikaacaaaaca63第12章 正交編碼與偽隨機序列pM序列的性質M序列與m序列類似，也在一定程度上具有噪聲特性。它滿足m序列的前兩個性質，即：在M序列的一個周期中，出現“0”與“1”的數目相等。在n級M序列的一個周期中，游程共有2n-1個，其中長度為k的游程占1/2k，1 k n 2；長為n的游程有兩個，沒有長為(n 1)的游程。在同長的游程中，“0”游程和“1”游程各占一半。這兩個性質的證明方法與m序列的一樣。但是，M序列不再具有m序列的移位相加特性及雙值自相關特性。64第12章 正交編碼與偽隨機序

47、列pM序列的優點M序列與m序列相比，最主要的優點是數量大，即同樣級數n的移存器能夠產生的平移不等價M序列總數比m序列的大得多，且隨n的增大迅速增加。在下表中給出了級數n與可能產生的兩種序列數目的比較。M序列的數量雖然相當大，但是目前能夠實際產生出來的M序列數目卻還不很多。這還有待于今后繼續研究。n1 2 3 4 5 6 7 8 9 10m序列數目1 1 2 2 6 6 18 16 48 60 M序列數目1 1 2 16 2048 6.71088 1.44115 1.32922 2.26156 1.30935 107 1017 1036 1074 10151 65第12章 正交編碼與偽隨機序列u

48、二次剩余序列p定義：二次剩余又稱平方剩余數，例如，32 = 9；9被7除得到的余數是2，即有32 = 9 2 (mod 7)則稱2為模7的平方剩余數。一般說來，如果能找到一個整數x，它使x2 i (mod p)若此方程成立，我們就認為這個方程有解。滿足此方程的i就是模p的二次剩余；否則，i就是模p的二次非剩余。當規定a0 = -1，且其中p為奇數，則稱ai為二次剩余序列，i = 0, 1, 2, .，其周期為p。的非二次剩余是模若的二次剩余是模若pipiai, 1, 166第12章 正交編碼與偽隨機序列p例：設p = 19，容易算出12 1 (mod 19)，22 4 (mod 19)，32

49、9 (mod 19)，42 16 (mod 19)，52 6 (mod 19)，62 17 (mod 19)，72 11 (mod 19)，82 7 (mod 19)，92 5 (mod 19)，102 5 (mod 19)，112 7 (mod 19)，122 11 (mod 19)，132 17 (mod 19)，142 6 (mod 19)，152 16 (mod 19)，162 9 (mod 19)，172 4 (mod 19)，182 1 (mod 19)。因此，1、4、5、6、7、9、11、16、17是模19的二次剩余；而2、3、8、10、12、13、14、15、18是模19的非二

50、次剩余。 67第12章 正交編碼與偽隨機序列這樣，得到周期p = 19的二次剩余序列為：式中 1； 1。這種序列具有隨機序列基本性質的第1)條性質，但一般不具備第2)條性質。當p = 4t 1時（t = 正整數），它是雙值自相關序列，即具有近于隨機序列基本性質第3)條的性質；當p = 4t + 1時，它不是雙值自相關序列。但是若p很大，它仍具有近于第3)條的性質。一般認為它也屬于偽隨機序列。68第12章 正交編碼與偽隨機序列u雙素數序列p上述二次剩余序列的周期p為素數。在雙素數序列中，周期p是兩個素數p1和p2的乘積，而且p2 = p1 + 2，即有p定義：雙素數序列ai的定義為：式中(i，p

51、) = 1表示i和p互為素數（最大公因子為1）。)2(1121ppppp為其他值當當當ipipipipiai, 1)(mod0, 11),(,221)2 , 1(, 1, 1jpipipijjj的非二次剩余是模若的二次剩余是模若69第12章 正交編碼與偽隨機序列p例：設p1= 3，p2 = 5，p = 3 5 = 15。這時在一個周期中滿足(i, p) = 1條件的i，即小于15且與15互素的正整數有：1、2、4、7、8、11、13、14。對于這些i值，可以計算出： , 1513585752,131431138321313373431:21pipi70第12章 正交編

52、碼與偽隨機序列對這些i值作(i/p1)(i/p2)的運算后，得出a1 = a2 = a4 = a8 = 1以及a7 = a11 = a13 = a14 = -1。又因i = 0 5 = 10 (mod 5)，故a0 = a5 = a10 = 1。對于其余的i，有a3 = a6 = a9 = a12 = -1。所以此雙素數序列為：式中 1； 1。可以驗證，雙素數序列也基本滿足隨機序列的基本性質，所以也屬于PN序列。71第12章 正交編碼與偽隨機序列l12.4擴展頻譜通信擴展頻譜通信n分類：u直接序列(DS)擴譜：它通常用一段偽隨機序列（又稱為偽碼）表示一個信息碼元，對載波進行調制。偽碼的一個單元

53、稱為一個碼片碼片。由于碼片的速率遠高于信息碼元的速率，所以已調信號的頻譜得到擴展。u 跳頻(FH)擴譜：它使發射機的載頻在一個信息碼元的時間內，按照預定的規律，離散地快速跳變，從而達到擴譜的目的。載頻跳變的規律一般也是由偽碼控制的。u線性調頻線性調頻：載頻在一個信息碼元時間內在一個寬的頻段中線性地變化，從而使信號帶寬得到擴展。由于此線性調頻信號若工作在低頻范圍，則它聽起來像鳥聲，故又稱“鳥聲”調制。72第12章 正交編碼與偽隨機序列n目的p提高抗窄帶干擾的能力，特別是提高抗有意干擾的能力。由于這類干擾的帶寬窄，所以對于寬帶擴譜信號的影響不大。p 防止竊聽。擴譜信號的發射功率譜密度可以很小，小到

54、低于噪聲的功率譜密度，將發射信號隱藏在背景噪聲中，使偵聽者很難發現。此外，由于采用了偽碼，竊聽者不能方便地聽懂發送的消息。p 提高抗多徑傳輸效應的能力。由于擴譜調制采用了擴譜偽碼，它可以用來分離多徑信號，所以有可能提高其抗多徑的能力。p 多個用戶可以共用同一頻帶。在同一擴譜頻帶內，不同用戶采用互相正交的不同擴譜碼，就可以區分各個用戶的信號，從而按照碼分多址的原理工作。p 提供測距能力。通過測量擴譜信號的自相關特性的峰值出現時刻，可以從信號傳輸時間的大小計算出傳輸距離73第12章 正交編碼與偽隨機序列n直接序列擴譜系統 u原理p用一組偽碼代表信息碼元去調制載波。最常用的是2PSK。這種信號的典型

55、功率譜密度曲線示于下圖中。圖中所示主瓣帶寬（零點至零點）是偽碼時鐘速率Rc的兩倍。每個旁瓣的帶寬等于Rc。例如，若所用碼片的速率為5 Mb/s，則主瓣帶寬將為10 MHz，每個旁瓣寬為5 MHz。74第12章 正交編碼與偽隨機序列u原理方框圖u調制器簡化方框圖：先將兩路編碼序列模2相加，然后再去進行反相鍵控。75第12章 正交編碼與偽隨機序列u接收過程圖解(a)信碼；(b)偽碼序列；(c)發送序列；(d)發送載波相位；(e)混頻用本振相位；(f) 中頻相位；(g)解調信號；(h)干擾信號相位；(i) 混頻后干擾信號相位。76第12章 正交編碼與偽隨機序列u信號和干擾信號在頻域中的變化 (a)

56、在接收機輸入端 (b) 在接收機中放輸出端77第12章 正交編碼與偽隨機序列l12.5偽隨機序列的其他應用偽隨機序列的其他應用n分離多徑技術u目的：多徑衰落的原因在于每條路徑的接收信號的相位不同。分離多徑技術能夠在接收端將多徑信號的各條路徑分離開，并分別校正每條路徑接收信號的相位，使之按同相相加，從而克服衰落現象。u原理p考察發射的一個數字信號碼元。設這個碼元是用m序列的一個周期去調制的余弦載波 其中M(t)為一取值1的m序列。假設經過多徑傳輸后，在接收機中頻部分得到的輸出信號為)cos()(ttM10cos)(njjijjtjtMA78第12章 正交編碼與偽隨機序列其中共有n條路徑的信號。第

57、j條路徑信號的振幅為Aj，延遲時間為j，載波附加的隨機相位為j，中頻角頻率為i。在此式中，忽略了各條路徑共同的延遲，并且認為相鄰路徑的延遲時間差相等，均等于秒。在設計中我們選用此值作為m序列的一個碼元寬度。為了消除各條射線隨機相位j的影響，可以采用自適應校相濾波器。10cos)(njjijjtjtMA79第12章 正交編碼與偽隨機序列p自適應校相濾波器設sj(t)是的第j條射線它加于上圖中電路的輸入端。此電路由兩個相乘器和一個窄帶濾波器組成。在第1個相乘器中，sj(t)與本地振蕩電壓s(t) = cos (0t + )相乘。相乘結果通過窄帶濾波器，后者的中心角頻率為(i - 0)，其通帶極窄，

58、只能通過(i - 0)分量而不能通過各邊帶分量。故濾波輸出g(t)在忽略一常數因子后可以表示為jijjjtjtMAts)(cos)()(jiijtjtAtg0cos)(80第12章 正交編碼與偽隨機序列在第2個相乘器中，sj(t)與g(t)相乘，取出乘積中差頻項f(t)，仍忽略常數因子，可將f(t)表示為在上圖中省略了上述分離出差頻項f(t)的帶通濾波器。由上式可見，經過自適應校相濾波器后，接收信號中的隨機相位可以消除。上面只分析了一條路徑接收信號的情況。當多徑信號輸入此濾波器時，每條路徑信號都同樣受到相位校正，故使各路徑信號具有相同的相位。這時的輸出f(t)變為此式中各路徑信號的載波得到了校

59、正，但是包絡M(t - j)仍然有差別。為了校正各路徑包絡的相對延遲，可以采用下圖所示的辦法。 )cos()()(02tjtMAtfj)cos()()(1002njjtjtMAtf81第12章 正交編碼與偽隨機序列 此圖中AF為自適應校相濾波器，抽頭延遲線的抽頭間隔時間為。設現在共有4條路徑的信號，n = 4，抽頭延遲線共有3段，每段延遲時間為，則相加器的輸入信號包絡為未經延遲的： A02M(t) + A12M(t-) + A22M(t-2) + A32M(t-3)經延遲的： A02M(t-) + A12M(t-2) + A22M(t-3) + A32M(t-4)經延遲2的：A02M(t-2) + A12M(t-3) + A22M(t-4) + A32M(t-5)經延遲3的： A02M(t-3) + A12M(t-4) + A22M(t-5) + A32M(t-6)82第12章 正交編碼與偽隨機序列相加器輸出信號的載波仍為cos(0t +)，包絡則為上式中各項之和。若上圖中本地m序列產生器的輸出為M(t - 3)，則在相乘器2中與接收的多徑信號相乘并經積分后，就能分離出包絡為(A02 + A12 + A22 + A32)M(t - 3)