第10章-正交編碼與偽隨機(jī)序列v3

1通信原理第10章正交編碼與偽隨機(jī)序列2024/9/29210.1引言

2024/9/29

正交編碼不僅可以用于提高數(shù)字通信系統(tǒng)的可靠性，還可以用來實(shí)現(xiàn)碼分多址，在移動(dòng)蜂窩通信中廣泛應(yīng)用。偽隨機(jī)序列在誤碼率測(cè)量、時(shí)延測(cè)量、擴(kuò)譜通信和保密通信等領(lǐng)域都有著十分廣泛的應(yīng)用。32024/9/2910.2正交編碼的基本概念和常見的正交編碼10.2.1正交編碼的基本概念

設(shè)碼長為n的編碼中碼元只取值+1和-1。如果x和y是其中的兩個(gè)碼組：x=(x1,x2,…,xn)，y=(y1,y2,…,yn)，其中，xi,yi∈{+1,-1}，i=1,2,…,n，則碼組x和y的互相關(guān)系數(shù)被定義為

如果碼組x和y正交，則

(x,y)=0。42024/9/2910.2.1正交編碼的基本概念(續(xù))

這4個(gè)碼組中任意兩者之間的相關(guān)系數(shù)都為0，即這4個(gè)碼組兩兩正交。我們把這種兩兩正交的編碼稱為正交編碼。52024/9/2910.2.1正交編碼的基本概念(續(xù))一個(gè)長為n的碼組x的自相關(guān)系數(shù)被定義為其中，x的下標(biāo)按模n運(yùn)算，即xn＋k

xk。舉例：如果數(shù)組x=(x1,x2,x3,x4)=(1,1,-1,-1)，則62024/9/2910.2.1正交編碼的基本概念(續(xù))

在二進(jìn)制編碼理論中，常采用二進(jìn)制數(shù)字“0”和“1”表示碼元的可能取值。若規(guī)定用二進(jìn)制數(shù)字“0”代替上述碼組中的“-1”，用二進(jìn)制數(shù)字“1”代替“+1”，則碼組x和y的互相關(guān)系數(shù)被定義為其中，a表示碼組x和y中對(duì)應(yīng)碼元相同的個(gè)數(shù)，b表示碼組x和y中對(duì)應(yīng)碼元不同的個(gè)數(shù)。72024/9/2910.2.1正交編碼的基本概念(續(xù))

若兩個(gè)碼組間的互相關(guān)系數(shù)

<0，則稱這兩個(gè)碼組互相超正交。如果一種編碼中任意兩碼組之間均超正交，則稱這種編碼為超正交碼。例如，對(duì)于3個(gè)碼組：x1=(+1,+1,+1)，x2=(+1,-1,-1)，x3=(-1,-1,+1)，由它們構(gòu)成的編碼是超正交碼。

由正交編碼和其反碼構(gòu)成的編碼就是雙正交編碼。10.2.2常見的正交編碼

常見的正交編碼有Hadamard碼矩陣、Walsh矩陣和偽隨機(jī)序列等。82024/9/2910.2.2常見的正交編碼(續(xù))1.Hadamard碼矩陣Hadamard碼矩陣是法國數(shù)學(xué)家M.J.Hadamard于1893年首先構(gòu)造出來的一種方陣，僅由元素+1和-1構(gòu)成，而且其任意兩行(列)之間是互相正交的，簡(jiǎn)記為H矩陣。H矩陣的最低階數(shù)為2，即

為了簡(jiǎn)便起見，把上式中的＋1和－1簡(jiǎn)寫為＋和－，上式就表示為92024/9/2910.2.2常見的正交編碼(續(xù))

階

數(shù)為2k的高階H矩陣從下列遞推關(guān)系得出其中，k為正整數(shù)，

是直積運(yùn)算。上式的直積運(yùn)算是指將矩陣Hk/2中的每一個(gè)元素用矩陣H2代替，比如，102024/9/2910.2.2常見的正交編碼(續(xù))H2矩陣、H4矩陣和H8矩陣都是對(duì)稱矩陣，而且第一行和第一列的元素全為“＋”，我們把這樣的H矩陣稱為Hadamard碼矩陣的正規(guī)形式，或稱為正規(guī)Hadamard碼矩陣。112024/9/2910.2.2常見的正交編碼(續(xù))

按照遞推關(guān)系式可以構(gòu)造出所有2k階的H矩陣?？梢宰C明，高于2階的H矩陣的階數(shù)一定是4的倍數(shù)。

H矩陣是正交方陣。如果把其中每一行看作是一個(gè)碼組，則這些碼組也是互相正交的，而整個(gè)H矩陣就是一種碼長為n的正交編碼，它包含n個(gè)碼組。因?yàn)殚L度為n的編碼共有2n個(gè)不同碼組，如果只將這n個(gè)碼組作為許用碼組，其余(2n-n)個(gè)為禁用碼組，則可以將其多余度用來糾錯(cuò)。這種編碼在糾錯(cuò)編碼理論中稱為Reed-Muller碼。122024/9/2910.2.2常見的正交編碼(續(xù))2.Walsh矩陣 Walsh函數(shù)的定義常用三角函數(shù)法、拉德馬赫函數(shù)乘積表示法、Hadamard矩陣表示法和遞推公式法等。這里介紹Walsh函數(shù)的遞推公式形式，其定義為其中，j=0,1,2,…,q=0或1，[j/2]表示j/2的整數(shù)部分。132024/9/2910.2.2常見的正交編碼(續(xù))

為了便于理解，做以下幾點(diǎn)說明：(1)當(dāng)把Wal(j,t)改成Wal(j,2t)時(shí)，表示保持波形相對(duì)形狀不變，只是將時(shí)基從-1/2≤t≤1/2壓縮到-1/4≤t≤1/4；(2)當(dāng)把Wal(j,2t)改成Wal[j,2(t±1/4)]時(shí)，表示保持波形相對(duì)形狀不變，只是將波形向左(對(duì)應(yīng)“+”號(hào))或向右(對(duì)應(yīng)“-”號(hào))平移1/4。例如，Wal(5,t)應(yīng)該根據(jù)Wal(2,t)遞推出來，此時(shí)，k=5,j=2,q=1,[j/2]=1。142024/9/2910.2.2常見的正交編碼(續(xù))152024/9/2910.2.2常見的正交編碼(續(xù))162024/9/2910.2.2常見的正交編碼(續(xù))

前八個(gè)Walsh函數(shù)中的任意兩個(gè)函數(shù)都是正交的。將前N個(gè)Walsh函數(shù)在等距的N個(gè)點(diǎn)抽樣，再將抽樣值寫成矩陣形式，即得N×N矩陣。例如，N=8時(shí)，可以得到8×8矩陣：如果把Walsh矩陣的每一行作為一個(gè)碼組，就得到Walsh編碼。172024/9/2910.3偽隨機(jī)序列

偽隨機(jī)序列具有類似于隨機(jī)噪聲的某些統(tǒng)計(jì)特性，同時(shí)又能夠重復(fù)產(chǎn)生。目前廣泛應(yīng)用的偽隨機(jī)噪聲都是由周期性數(shù)字序列經(jīng)過濾波等處理后得出的。我們將這種周期性數(shù)字序列稱為偽隨機(jī)序列，它有時(shí)又被稱為偽隨機(jī)信號(hào)和偽隨機(jī)碼。

常用的偽隨機(jī)序列有m序列、M序列、二次剩余序列和雙素?cái)?shù)序列。182024/9/2910.3.1m序列的產(chǎn)生m序列是最長線性反饋移位寄存器序列的簡(jiǎn)稱，它是由帶線性反饋移存器產(chǎn)生的周期最長的一種序列。一個(gè)4級(jí)線性反饋移存器如圖10-3所示，其中的⊕表示模2加。192024/9/2910.3.1m序列的產(chǎn)生(續(xù))

設(shè)4個(gè)寄存器的初始狀態(tài)為為(a3,a2,a1,a0)=(1,0,0,0)，則在移位1次時(shí)，由a3和a0模2相加，作為a3新的輸入a3=1

0=1，新的狀態(tài)變?yōu)?a3,a3,a2,a1)=(1,1,0,0)。這樣移位15次后又回到初始狀態(tài)(1,0,0,0)。產(chǎn)生的隨機(jī)序列{bn,n=0,1,2,…}={0,0,0,1,1,1,1,0,1,0,1,1,0,0,1,0,0,0,1,1,…}。

如果初始狀態(tài)為全“0”，即(a3,a2,a1,a0)=(0,0,0,0)，則移位后得到的仍為全“0”狀態(tài)，應(yīng)該避免。

除全“0”狀態(tài)外，只剩15種狀態(tài)可用，由任何4級(jí)反饋移存器產(chǎn)生的序列的周期最長為15。202024/9/2910.3.1m序列的產(chǎn)生(續(xù))

一個(gè)n級(jí)線性反饋移存器可能產(chǎn)生的最長周期等于(2n-1)。這種最長的序列稱為最長線性反饋移存器序列，就是m序列。

一般的線性反饋移存器原理方框圖如圖10-4所示，其中，各級(jí)移存器的狀態(tài)用ai表示，ai=0或1，i為非負(fù)整數(shù)。反饋線的連接狀態(tài)用ci表示，ci＝1表示此線接通，ci＝0表示此線斷開。反饋線的連接狀態(tài)不同，輸出序列的周期就可能不同。212024/9/2910.3.1m序列的產(chǎn)生(續(xù))

寄存器an-1的新狀態(tài)為222024/9/2910.3.1m序列的產(chǎn)生(續(xù))

ci的取值決定了移存器的反饋連接和序列的周期長度，故ci是一個(gè)很重要的參量?，F(xiàn)在將它們與一個(gè)n階方程一一對(duì)應(yīng)，讓它們?cè)跒閚階方程的系數(shù)，即

這個(gè)n階方程被稱為特征方程或特征多項(xiàng)式。

任何一個(gè)寄存器的輸出都可以作為一個(gè)偽隨機(jī)序列。如果我們把寄存器an-1的輸出序列{an,n=0,1,2,…}的每個(gè)元素與一個(gè)代數(shù)方程建立一一對(duì)應(yīng)的關(guān)系，即母函數(shù)232024/9/2910.3.1m序列的產(chǎn)生(續(xù))

定理10-1

如果多項(xiàng)式u(x)的階數(shù)低于特征方程f(x)的階數(shù)，該特征方程f(x)對(duì)應(yīng)的母函數(shù)為G(x)，則證明242024/9/2910.3.1m序列的產(chǎn)生(續(xù))

當(dāng)電路給定后，h(x)僅決定于寄存器初始狀態(tài)(a-i，a-i

+1,

,a-1)。如果a－1=1，則h(x)的階數(shù)為(n–1)；若a－1=0，則h(x)的階數(shù)<(n–1)。因此，h(x)的階數(shù)

(n–1)。而f(x)的階數(shù)為n，因?yàn)閏n＝1。故h(x)的階數(shù)必定低于f(x)的階數(shù)。252024/9/2910.3.1m序列的產(chǎn)生(續(xù))

定理10-2

一個(gè)n級(jí)線性反饋移存器的狀態(tài)具有周期性，且周期p

2n－1。證明移存器的新狀態(tài)完全決定于所有寄存器的前一狀態(tài)。因此，對(duì)于某新狀態(tài)R，如果R與以前的某一狀態(tài)Q相同，則狀態(tài)R后之相繼狀態(tài)必定和Q之相繼狀態(tài)相同，也就是說，一個(gè)n級(jí)線性反饋移存器的狀態(tài)具有周期性。

在n級(jí)移存器中，每級(jí)移存器只能有兩種狀態(tài)：“1”或“0”。故n級(jí)移存器最多僅可能有2n種不同狀態(tài)。所以，在連續(xù)(2n

+1)個(gè)狀態(tài)中必有重復(fù)。如上所述，一旦狀態(tài)重復(fù)，就有周期性，且周期p

2n。

262024/9/2910.3.1m序列的產(chǎn)生(續(xù))

在2n種不同狀態(tài)中，其中有一種全“0”狀態(tài)。一旦發(fā)生全“0”狀態(tài)，則后繼狀態(tài)也為全“0”，這時(shí)的周期p＝1。因此，在一個(gè)長的周期中不能包括全“0”狀態(tài)。所以周期p

(2n

-1)。

定理10-3如果序列A={ak,k=0,1,2,…}具有最長周期p=2n-1，則其特征多項(xiàng)式f(x)應(yīng)為階數(shù)位n的既約多項(xiàng)式(所謂既約多項(xiàng)式是指不能分解因子的多項(xiàng)式)。證明：假設(shè)n次多項(xiàng)式f(x)能分解成兩個(gè)不同因子，即272024/9/2910.3.1m序列的產(chǎn)生(續(xù))

假設(shè)f1(x)的階數(shù)為n1，n1>0，f2(x)的階數(shù)為n2，n2>0，則n1+n2=n。母函數(shù)G(x)可以看成是兩個(gè)母函數(shù)G1(x)和G2(x)之和，其中G1(x)是由特征多項(xiàng)式f1(x)產(chǎn)生的，G2(x)是由特征多項(xiàng)式f2(x)產(chǎn)生的。由定理10-2可知，G1(x)對(duì)應(yīng)的輸出序列的最長周期為G2(x)對(duì)應(yīng)的輸出序列的最長周期為G(x)對(duì)應(yīng)的輸出序列的最長周期p應(yīng)是p1和p2的最小公倍數(shù)LCM[p1,p2]，即282024/9/2910.3.1m序列的產(chǎn)生(續(xù))

這與定理已知條件p=2n-1矛盾。因此，特征多項(xiàng)式f(x)應(yīng)為階數(shù)位n的既約多項(xiàng)式。定理10-4

如果n級(jí)線性反饋移存器的特征多項(xiàng)式f(x)是既約的，則由其產(chǎn)生的序列A={ak,k=0,1,2,…}的周期等于使(xp+1)被f(x)整除的最小正整數(shù)p。證明如果序列A具有周期p，則母函數(shù)292024/9/2910.3.1m序列的產(chǎn)生(續(xù))302024/9/2910.3.1m序列的產(chǎn)生(續(xù))設(shè)(xp

+1)被f(x)整除的商為

不妨考慮一種具體的初始狀態(tài)，a－1＝a－2＝

＝a－n＋1＝0，a－n＝1，則312024/9/2910.3.1m序列的產(chǎn)生(續(xù))

序列A的周期為p或p的某個(gè)因子。若A以p的某個(gè)因子p1為周期，p1<p，則由定理10-4可知，(xp1+1)必能被f(x)整除。所以，序列A={ak,k=0,1,2,…}的周期等于使(xp+1)被f(x)整除的最小正整數(shù)p。

若一個(gè)n次多項(xiàng)式f(x)滿足下列條件：

(1)f(x)為既約的；

(2)f(x)可整除(xp+1)，p=2n

–1，n為正整數(shù)。

(3)f(x)除不盡(xq+1)，q<p；則稱f(x)為本原多項(xiàng)式。

由定理10-4可知，一個(gè)線性反饋移存器能產(chǎn)生m序列的充要條件為：線性反饋移存器的特征多項(xiàng)式為本原多項(xiàng)式。322024/9/2910.3.1m序列的產(chǎn)生(續(xù))例10-1

用一個(gè)4級(jí)線性反饋移存器產(chǎn)生m序列，試求其特征多項(xiàng)式。解線性反饋移存器產(chǎn)生的m序列的周期為p=2n–1=15。由于其特征多項(xiàng)式f(x)應(yīng)可整除(xp+1)=(x15+1)。換言之，特征多項(xiàng)式f(x)應(yīng)該是(x15+1)的一個(gè)因子。由于f(x)不僅應(yīng)為(x15+1)的一個(gè)因子，而且還應(yīng)該是一個(gè)4次本原多項(xiàng)式。上式表明，(x15+1)可以分解為5個(gè)既約因子，其中3個(gè)是4次多項(xiàng)式。332024/9/2910.3.1m序列的產(chǎn)生(續(xù))342024/9/2910.3.2m序列的性質(zhì)1.均衡性

在m序列的一個(gè)周期中，“1”和“0”的數(shù)目基本相等。準(zhǔn)確地說，“1”的個(gè)數(shù)比“0”的個(gè)數(shù)多一個(gè)。2.游程分布規(guī)律

把序列中取值相同的那些相繼的(連在一起的)元素合稱為一個(gè)“游程”。在一個(gè)游程中元素的個(gè)數(shù)稱為游程長度。352024/9/2910.3.2m序列的性質(zhì)

在其一個(gè)周期(m個(gè)元素)中，共有8個(gè)游程，其中長度為4的游程有1個(gè)，即“1111”，長度為3的游程有1個(gè)，即“000”，長度為2的游程有2個(gè)，即“11”和“00”，長度為1的游程有4個(gè)，即兩個(gè)“1”和兩個(gè)“0”。

一般說來，在m序列中，長度為1的游程占游程總數(shù)的1/2；長度為2的游程占游程總數(shù)的1/4；長度為3的游程占1/8；以此類推。

嚴(yán)格講，長度為k的游程數(shù)目占游程總數(shù)的2-k，其中1

k

(n-1)。而且在長度為k的游程中[其中1

k

(n-2)]，連“1”的游程和連“0”的游程各占一半。362024/9/2910.3.2m序列的性質(zhì)

3.移位相加特性

一個(gè)m序列A與其經(jīng)過任意次延遲移位產(chǎn)生的另一個(gè)不同序列B模2相加，得到的仍是A的某次延遲移位序列C，即A

B=C4.自相關(guān)函數(shù)m序列的自相關(guān)函數(shù)可以定義為其中，A和D分別是m序列與其j次移位序列在一個(gè)周期中對(duì)應(yīng)元素相同的數(shù)目和不同的數(shù)目，m是m序列的周期長度。372024/9/2910.3.2m序列的性質(zhì)

由m序列的均衡性可知，m序列一個(gè)周期中“0”的數(shù)目比“1”的數(shù)目少一個(gè)。所以，上式分子等于－1。于是，若把m序列當(dāng)作周期為T的連續(xù)函數(shù)s(t)，則其自相關(guān)函數(shù)為382024/9/2910.3.2m序列的性質(zhì)

5.功率譜密度

信號(hào)的自相關(guān)函數(shù)與功率譜密度構(gòu)成一對(duì)傅里葉變換。m序列的功率譜密度為392024/9/291