數(shù)字通信原理與技術(shù)(第五版) 課件 第9、10章　差錯(cuò)控制編碼、偽隨機(jī)序列及應(yīng)用

第9章差錯(cuò)控制編碼9.1概述9.2檢錯(cuò)與糾錯(cuò)9.3常用差錯(cuò)控制碼9.4線性分組碼9.5循環(huán)碼9.6卷積碼*9.7網(wǎng)格編碼調(diào)制9.1概述9.1.1信道編碼在數(shù)字通信中，根據(jù)不同的目的，編碼可分為信源編碼和信道編碼。信源編碼是為了提高數(shù)字信號(hào)的有效性以及為了使模擬信號(hào)數(shù)字化而采取的編碼。信道編碼是為了降低誤碼率，提高數(shù)字通信的可靠性而采取的編碼。數(shù)字信號(hào)在傳輸過程中，加性噪聲、碼間串?dāng)_等都會(huì)產(chǎn)生誤碼。為了提高系統(tǒng)的抗干擾性能，可以加大發(fā)射功率，降低接收設(shè)備本身的噪聲，以及合理選擇調(diào)制、解調(diào)方法等。此外，還可以采用信道編碼技術(shù)。9.1.2差錯(cuò)控制方式圖9-1差錯(cuò)控制方式

1.檢錯(cuò)重發(fā)方式檢錯(cuò)重發(fā)又稱自動(dòng)請(qǐng)求重傳方式，記作ARQ(AutomaticRepeatRequest)。由發(fā)端送出能夠發(fā)現(xiàn)錯(cuò)誤的碼，由收端判決傳輸中無錯(cuò)誤產(chǎn)生，如果發(fā)現(xiàn)錯(cuò)誤，則通過反向信道把這一判決結(jié)果反饋給發(fā)端，然后，發(fā)端把收端認(rèn)為錯(cuò)誤的信息再次重發(fā)，從而達(dá)到正確傳輸?shù)哪康摹Ｆ涮攸c(diǎn)是需要反饋信道，譯碼設(shè)備簡(jiǎn)單，對(duì)突發(fā)錯(cuò)誤和信道干擾較嚴(yán)重時(shí)有效，但實(shí)時(shí)性差，主要在計(jì)算機(jī)數(shù)據(jù)通信中得到應(yīng)用。2.前向糾錯(cuò)方式前向糾錯(cuò)方式記作FEC(ForwordErrorCorrection)。發(fā)端發(fā)送能夠糾正錯(cuò)誤的碼，收端收到信碼后自動(dòng)地糾正傳輸中的錯(cuò)誤。其特點(diǎn)是單向傳輸，實(shí)時(shí)性好，但譯碼設(shè)備較復(fù)雜。3.混合糾錯(cuò)方式混合糾錯(cuò)方式記作HEC(HybridErrorCorrection)是FEC和ARQ方式的結(jié)合。發(fā)端發(fā)送具有自動(dòng)糾錯(cuò)同時(shí)又具有檢錯(cuò)能力的碼。收端收到碼后，檢查差錯(cuò)情況，如果錯(cuò)誤在碼的糾錯(cuò)能力范圍以內(nèi)，則自動(dòng)糾錯(cuò)，如果超過了碼的糾錯(cuò)能力，但能檢測(cè)出來，則經(jīng)過反饋信道請(qǐng)求發(fā)端重發(fā)。這種方式具有自動(dòng)糾錯(cuò)和檢錯(cuò)重發(fā)的優(yōu)點(diǎn)，可達(dá)到較低的誤碼率，因此，近年來得到廣泛應(yīng)用。

另外，按照噪聲或干擾的變化規(guī)律，可把信道分為三類：隨機(jī)信道、突發(fā)信道和混合信道。恒參高斯白噪聲信道是典型的隨機(jī)信道，其中差錯(cuò)的出現(xiàn)是隨機(jī)的，而且錯(cuò)誤之間是統(tǒng)計(jì)獨(dú)立的。具有脈沖干擾的信道是典型的突發(fā)信道，錯(cuò)誤是成串成群出現(xiàn)的，即在短時(shí)間內(nèi)出現(xiàn)大量錯(cuò)誤。短波信道和對(duì)流層散射信道是混合信道的典型例子，隨機(jī)錯(cuò)誤和成串錯(cuò)誤都占有相當(dāng)比例。對(duì)于不同類型的信道，應(yīng)采用不同的差錯(cuò)控制方式。9.2.1糾錯(cuò)碼的分類

(1)根據(jù)糾錯(cuò)碼各碼組信息元和監(jiān)督元的函數(shù)關(guān)系，可分為線性碼和非線性碼。如果函數(shù)關(guān)系是線性的，即滿足一組線性方程式，則稱為線性碼，否則為非線性碼。

(2)根據(jù)上述關(guān)系涉及的范圍，可分為分組碼和卷積碼。分組碼的各碼元僅與本組的信息元有關(guān)；卷積碼中的碼元不僅與本組的信息元有關(guān)，而且還與前面若干組的信息元有關(guān)。

(3)根據(jù)碼的用途，可分為檢錯(cuò)碼和糾錯(cuò)碼。檢錯(cuò)碼以檢錯(cuò)為目的，不一定能糾錯(cuò)；而糾錯(cuò)碼以糾錯(cuò)為目的，一定能檢錯(cuò)。9.2檢錯(cuò)與糾錯(cuò)9.2.2糾錯(cuò)編碼的基本原理1.分組碼分組碼一般可用(n,k)表示。其中，k是每組二進(jìn)制信息碼元的數(shù)目，n是編碼碼組的碼元總位數(shù)，又稱為碼組長(zhǎng)度，簡(jiǎn)稱碼長(zhǎng)。n-k=r為每個(gè)碼組中的監(jiān)督碼元數(shù)目。簡(jiǎn)單地說，分組碼是對(duì)每段k位長(zhǎng)的信息組以一定的規(guī)則增加r個(gè)監(jiān)督元，組成長(zhǎng)為n的碼字。在二進(jìn)制情況下，共有2k個(gè)不同的信息組，相應(yīng)地可得到2k個(gè)不同的碼字，稱為許用碼組。其余2n-2k個(gè)碼字未被選用，稱為禁用碼組。

在分組碼中，非零碼元的數(shù)目稱為碼字的漢明重量，簡(jiǎn)稱碼重。例如，碼字10110，碼重w=3。兩個(gè)等長(zhǎng)碼組之間相應(yīng)位取值不同的數(shù)目稱為這兩個(gè)碼組的漢明(Hamming)距離，簡(jiǎn)稱碼距。例如11000與10011之間的距離d=3。碼組集中任意兩個(gè)碼字之間距離的最小值稱為碼的最小距離，用d０表示。最小碼距是碼的一個(gè)重要參數(shù)，它是衡量碼檢錯(cuò)、糾錯(cuò)能力的依據(jù)。2.檢錯(cuò)和糾錯(cuò)能力

若分組碼碼字中的監(jiān)督元在信息元之后，而且是信息元的簡(jiǎn)單重復(fù)，則稱該分組碼為重復(fù)碼。它是一種簡(jiǎn)單實(shí)用的檢錯(cuò)碼，并有一定的糾錯(cuò)能力。例如(2,1)重復(fù)碼，兩個(gè)許用碼組是00與11，d0=2，收端譯碼，出現(xiàn)01、10禁用碼組時(shí)，可以發(fā)現(xiàn)傳輸中的一位錯(cuò)誤。如果是(3,1)重復(fù)碼，兩個(gè)許用碼組是000與111,d0=3;當(dāng)收端出現(xiàn)兩個(gè)或三個(gè)1時(shí)，判為1，否則判為0。此時(shí)，可以糾正單個(gè)錯(cuò)誤，或者該碼可以檢出兩個(gè)錯(cuò)誤。

碼的最小距離d0直接關(guān)系著碼的檢錯(cuò)和糾錯(cuò)能力；任一(n,k)分組碼，若要在碼字內(nèi):(1)檢測(cè)e個(gè)隨機(jī)錯(cuò)誤，則要求碼的最小距離d0≥e+1;(2)糾正t個(gè)隨機(jī)錯(cuò)誤，則要求碼的最小距離d0≥2t+1;(3)糾正t個(gè)同時(shí)檢測(cè)e(≥t)個(gè)隨機(jī)錯(cuò)誤，則要求碼的最小距離d0≥t+e+1。3.編碼效率用差錯(cuò)控制編碼提高通信系統(tǒng)的可靠性，是以降低有效性為代價(jià)換來的。我們定義編碼效率R來衡量有效性:

其中,k是信息元的個(gè)數(shù)，n為碼長(zhǎng)。對(duì)糾錯(cuò)碼的基本要求是:檢錯(cuò)和糾錯(cuò)能力盡量強(qiáng)；編碼效率盡量高；編碼規(guī)律盡量簡(jiǎn)單。際中要根據(jù)具體指標(biāo)要求，保證有一定糾、檢錯(cuò)能力和編碼效率，并且易于實(shí)現(xiàn)。(9-1)9.3常用的幾種簡(jiǎn)單分組碼9.3.1奇偶監(jiān)督碼

奇偶監(jiān)督碼是在原信息碼后面附加一個(gè)監(jiān)督元，使得碼組中“1”的個(gè)數(shù)是奇數(shù)或偶數(shù)?；蛘哒f，它是含一個(gè)監(jiān)督元，碼重為奇數(shù)或偶數(shù)的(n,n-1)系統(tǒng)分組碼。奇偶監(jiān)督碼又分為奇監(jiān)督碼和偶監(jiān)督碼。設(shè)碼字A=［an-1,an-2,…,a1,a0］，對(duì)偶監(jiān)督碼有

奇監(jiān)督碼情況相似，只是碼組中“1”的數(shù)目為奇數(shù)，即滿足條件而檢錯(cuò)能力與偶監(jiān)督碼相同。奇偶監(jiān)督碼的編碼效率R為(9-2)(9-3)9.3.2水平奇偶監(jiān)督碼為了提高奇偶監(jiān)督碼的檢錯(cuò)能力,特別是克服其不能檢測(cè)突發(fā)錯(cuò)誤的缺點(diǎn),可以將經(jīng)過奇偶監(jiān)督的碼元序列按行排成方陣,每行為一組奇偶監(jiān)督碼,如表9－1所示。發(fā)送時(shí)按列的順序傳輸,接收時(shí)仍將碼元序列還原為發(fā)送時(shí)的方陣形式,然后按行進(jìn)行奇偶校驗(yàn)。表9－1水平奇偶監(jiān)督碼9.3.3行列監(jiān)督碼奇偶監(jiān)督碼不能發(fā)現(xiàn)偶數(shù)個(gè)錯(cuò)誤。為了改善這種情況，引入行列監(jiān)督碼。這種碼不僅對(duì)水平(行)方向的碼元，而且對(duì)垂直(列)方向的碼元實(shí)施奇偶監(jiān)督。這種碼既可以逐行傳輸，也可以逐列傳輸。一般地，L×M個(gè)信息元附加L+M+1個(gè)監(jiān)督元，組成(LM+L+M+1,LM)行列監(jiān)督碼的一個(gè)碼字(L+1行，M+1列)。表9－2是(66,50)行列監(jiān)督碼的一個(gè)碼字。這種碼具有較強(qiáng)的檢測(cè)能力，適于檢測(cè)突發(fā)錯(cuò)誤，還可用于糾錯(cuò)。表9－2

(66,50)行列監(jiān)督碼9.3.4群計(jì)數(shù)碼把信息碼元中“1”的個(gè)數(shù)用二進(jìn)制數(shù)字表示,并作為監(jiān)督碼元放在信息碼元的后面,這樣構(gòu)成的碼稱為群計(jì)數(shù)碼。例如,一碼組的信息碼元為1010111,其中“1”的個(gè)數(shù)為5,用二進(jìn)制數(shù)字表示為“101”,將它作為監(jiān)督碼元附加在信息碼元之后,即傳輸?shù)拇a組為1010111101。群計(jì)數(shù)碼有較強(qiáng)的檢錯(cuò)能力,除了同時(shí)出現(xiàn)碼組中“1”變“0”和“0”變“1”的成對(duì)錯(cuò)誤外,它還能糾正所有形式的錯(cuò)誤。9.3.5恒比碼

碼字中1的數(shù)目與0的數(shù)目保持恒定比例的碼稱為恒比碼。由于恒比碼中，每個(gè)碼組均含有相同數(shù)目的1和0，因此恒比碼又稱等重碼，定1碼。這種碼在檢測(cè)時(shí)，只要計(jì)算接收碼元中1的數(shù)目是否正確，就知道有無錯(cuò)誤。目前我國電傳通信中普遍采用3∶2碼，又稱“5中取3”的恒比碼，即每個(gè)碼組的長(zhǎng)度為5，其中3個(gè)“1”。這時(shí)可能編成的不同碼組數(shù)目等于從5中取3的組合數(shù)10，這10個(gè)許用碼組恰好可表示10個(gè)阿拉伯?dāng)?shù)字，如表7-1所示。而每個(gè)漢字又是以四位十進(jìn)制數(shù)來代表的。實(shí)踐證明，采用這種碼后，我國漢字電報(bào)的差錯(cuò)率大為降低。表9-33∶2恒比碼9.4線性分組碼9.4.1基本概念在(n,k)分組碼中,若每一個(gè)監(jiān)督元都是碼組中某些信息元按模二和而得到的,即監(jiān)督元是按線性關(guān)系相加而得到的,則稱線性分組碼。或者說,可用線性方程組表述碼規(guī)律性的分組碼稱為線性分組碼。線性分組碼是一類重要的糾錯(cuò)碼,應(yīng)用很廣泛。

現(xiàn)以(7,4)分組碼為例來說明線性分組碼的特點(diǎn)。設(shè)其碼字為A=［a6

a5

a4

a3

a2

a1

a0］，其中前4位是信息元，后3位是監(jiān)督元，可用下列線性方程組來描述該分組碼，產(chǎn)生監(jiān)督元。(9-4)我們可以把(n,k)線性分組碼看成一個(gè)n維線性空間,每一個(gè)碼字就是這個(gè)空間的一個(gè)矢量。n維線性空間長(zhǎng)度為n的碼組共有2n個(gè),但線性分組碼的碼字共有2k個(gè),k<n。顯然,這2k個(gè)分組碼構(gòu)成了n維線性空間的K維線性子空間,它是線性分組碼的許用碼組,剩余的空間構(gòu)成的碼組是禁用碼組。9.4.2漢明(Hamming)碼漢明碼是一種用來糾正單個(gè)錯(cuò)誤的線性分組碼,已作為差錯(cuò)控制碼廣泛用于數(shù)字通信和數(shù)據(jù)存儲(chǔ)系統(tǒng)中。一般來說,若碼長(zhǎng)為n,信息位為k,則監(jiān)督元為r=n-k。如果求用r個(gè)監(jiān)督位構(gòu)造出r個(gè)監(jiān)督方程能糾正1位或1位以上錯(cuò)誤的線性碼,則必須有

2r-1≥n (9－5)

現(xiàn)以(n,k)漢明碼為例來說明線性分組碼的特點(diǎn)。在前面討論奇偶監(jiān)督碼時(shí),如考慮偶監(jiān)督,用式(9－2)作為監(jiān)督方程,而在接收端譯碼時(shí),實(shí)際是按下式計(jì)算:(9－6)若S=0，就認(rèn)為無錯(cuò)；若S=1，就認(rèn)為有錯(cuò)，我們稱上式為監(jiān)督方程，S校正子（校驗(yàn)子），又稱伴隨式。如果增加一位監(jiān)督元，就可以寫出兩個(gè)監(jiān)督方程，計(jì)算出兩個(gè)校正子S1和S2。S1S2為00時(shí)，表示無錯(cuò)；S1S2為01、10、11時(shí)，指示3種不同的錯(cuò)誤圖樣。由此可見，若有r位監(jiān)督元，就可以構(gòu)成r個(gè)監(jiān)督方程，計(jì)算得到的校正子有r位，可用來指示2r-1種不同的錯(cuò)誤圖樣，r位校正子為全零時(shí)，表示無錯(cuò)。設(shè)分組碼中信息位k=4,又假設(shè)該碼能糾正一位錯(cuò)碼,這時(shí),d0≥3。要滿足2r-1≥n,取r≤3,當(dāng)r=3時(shí),n=k+r=7,這樣就構(gòu)成了(7,4)漢明碼。這里用A=［a6

a5

a4

a3

a2

a1

a0］表示碼字,其中,前4位是信息元,后3位是監(jiān)督元。用S1,S2,S3表示由3個(gè)監(jiān)督方程得到的3個(gè)校正子。3個(gè)校正子S1,S2,S3指示23-1種不同的錯(cuò)誤圖樣。校正子與錯(cuò)碼位置的對(duì)應(yīng)關(guān)系如表9－5所示。(9－7)(9－8)(9－9)在發(fā)送端編碼時(shí),a6,a5,a4,a3為信息元,由傳輸?shù)男畔Q定;而監(jiān)督元a2,a1,a0則由監(jiān)督方程(9－7)、(9－8)、(9－9)來決定。當(dāng)3個(gè)校正子S1,S2,S3均為0時(shí),編碼組中無錯(cuò)碼發(fā)生,于是有下列方程組:(9－10)由上式可以求得監(jiān)督元a2,a1,a0為(9－11)已知信息元a6,a5,a4,a3,就可以直接由上式計(jì)算出監(jiān)督元a2,a1,a0。由此得到(7,4)漢明碼的16個(gè)許用碼組,如表9－6所示。在接收端收到每組碼后,按監(jiān)督方程(9－7)、(9－8)、(9－9)計(jì)算出S1,S2和S3。如不全為0,則可按表9－5確定誤碼的位置,然后加以糾正。漢明碼有較高的編碼效率,其編碼效率為9.4.3監(jiān)督矩陣(9-12)

不難看出,上述(7,4)碼的最小碼距d0=3,它能糾正一個(gè)錯(cuò)誤或檢測(cè)兩個(gè)錯(cuò)誤?？蓪⑹?9－10)所述(7,4)漢明碼的3個(gè)監(jiān)督方程式改寫成以下線性方程組:這組線性方程可用矩陣形式表示為

(9-13)

并簡(jiǎn)記為(9-14)其中，AT是A的轉(zhuǎn)置，0T是0=［000］的轉(zhuǎn)置，HT是H的轉(zhuǎn)置。

(9-15)H稱為監(jiān)督矩陣，一旦H給定，信息位和監(jiān)督位之間的關(guān)系也就確定了。H為r×n階矩陣，H矩陣每行之間是彼此線性無關(guān)的。式(10-7)所示的H矩陣可分成兩部分

其中,P為r×k階矩陣，Ir為r×r階單位矩陣?？梢詫懗蒆=［PIr］形式的矩陣稱為典型監(jiān)督矩陣。

HAT=0T，說明H矩陣與碼字的轉(zhuǎn)置乘積必為零，可以用來作為判斷接收碼字A是否出錯(cuò)的依據(jù)。(9-16)若把監(jiān)督方程補(bǔ)充為下列方程(9-17)可改寫為矩陣形式(9－18)即(9－19)變換為其中(9-20)稱為生成矩陣，由G和信息組就可以產(chǎn)生全部碼字。G為k×n階矩陣，各行也是線性無關(guān)的。生成矩陣也可以分為兩部分，即(9-21)其中

(9-22)Q為k×r階矩陣,Ik為k階單位陣?？梢詫懗墒?9-21)形式的G矩陣，稱為典型生成矩陣。非典型形式的矩陣經(jīng)過運(yùn)算也一定可以化為典型矩陣形式。

9.4.5校正和檢錯(cuò)

設(shè)發(fā)送碼組A=［an-1,an-2,…,a1,a0］，在傳輸過程中可能發(fā)生誤碼。接收碼組B=［bn-1,bn-2,…,b1,b0］，則收發(fā)碼組之差定義為錯(cuò)誤圖樣E，也稱為誤差矢量，即其中E=［en-1,en-2,…,e1,e0］，且當(dāng)bi=ai

當(dāng)bi≠ai

(9-23)(9-24)式(9-23)也可寫作令S=BHT，稱為伴隨式或校正子。(9-25)(9-26)

由此可見，伴隨式S與錯(cuò)誤圖樣E之間有確定的線性變換關(guān)系。接收端譯碼器的任務(wù)就是從伴隨式確定錯(cuò)誤圖樣，然后從接收到的碼字中減去錯(cuò)誤圖樣。

表9-7(7,4)碼S與E的對(duì)應(yīng)關(guān)系9.4.6線性分組碼的性質(zhì)線性分組碼是一種群碼,對(duì)于模2加運(yùn)算,其性質(zhì)滿足以下幾條:

(1)封閉性。所謂封閉性,是指群碼中任意兩個(gè)許用碼組之和仍為一許用碼組,這種性質(zhì)也稱為自閉率。

(2)有零碼。所有信息元和監(jiān)督元均為零的碼組,稱為零碼,即A0=［00…0］。任一碼組與零碼相運(yùn)算其值不變。Ai+A0=Ai(3)有負(fù)元。一個(gè)線性分組碼中任一碼組即是它自身的負(fù)元。Ai+Ai=A0(4)結(jié)合律。即A2+A3=A3+A2（A1+A2）+A3=A1+（A2+A3）(5)交換律。即(6)最小碼距等于線性分組碼中非全零碼組的最小重量。線性分組碼的封閉性表明,碼組集中任意兩個(gè)碼組模2相加所得的碼組一定在該碼組集中,因而兩個(gè)碼組之間的距離必是另一碼組的重量。為此,碼的最小距離也就是碼的最小重量。9.5循環(huán)碼9.5.1循環(huán)特性循環(huán)碼的前k位為信息碼,后r位為監(jiān)督碼元。除了具有線性碼的一般性質(zhì)外,還具有循環(huán)性,即循環(huán)碼組中任一碼組循環(huán)移位所得的碼組仍為一個(gè)許用碼組。表9－8中給出一種(7,3)循環(huán)碼的全部碼組。在代數(shù)理論中,為了便于計(jì)算,常用碼多項(xiàng)式表示碼字。(n,k)循環(huán)碼的碼字,其碼多項(xiàng)式(以降冪順序排列)為(9－27)如表9－8中第5組碼字可用多項(xiàng)式表示為在循環(huán)碼中,若A(x)是一個(gè)長(zhǎng)為n的許用碼組,則xi·A(x)在按模xn+1運(yùn)算下,也是一個(gè)許用碼組。也就是說:一個(gè)長(zhǎng)為n的(n,k)分組碼,它必定是按模xn+1運(yùn)算的一個(gè)余式。9.5.2生成多項(xiàng)式及生成矩陣如果一種碼的所有碼多項(xiàng)式都是多項(xiàng)式g(x)的倍式,則稱g(x)為該碼的生成多項(xiàng)式。在(n,k)循環(huán)碼中,任意碼多項(xiàng)式A(x)都是最低次碼多項(xiàng)式的倍式。因此,循環(huán)碼中次數(shù)最低的多項(xiàng)式(全0碼字除外)就是生成多項(xiàng)式g(x)?？梢宰C明,g(x)是常數(shù)項(xiàng)為1的r=n-k次多項(xiàng)式,是xn+1的一個(gè)因式。循環(huán)碼的生成矩陣常用多項(xiàng)式的形式來表示其中

(9-28)

(9-29)例如(7,3)循環(huán)碼，n=7,k=3,r=4,其生成多項(xiàng)式及生成矩陣分別為即

g(x)=A2(x)=x4+x2+x+1(9－30)(9－31)

將上式變換為典型的生成矩陣(將矩陣中第一行與第三行相加后取代第一行),可得到(9－32)將信息元與生成矩陣相乘就可以得到全部碼組,即A=MG

(9－33)(9－34)

由此可見,任一循環(huán)碼A(x)都是g(x)的倍式,即都可以被g(x)整除,而且任一次數(shù)不大于(k-1)的多項(xiàng)式乘g(x)都是碼多項(xiàng)式。式(9－34)實(shí)際上可以表示為A(x)=m(x)g(x)其中,m(x)為信息組多項(xiàng)式,最高次數(shù)為k-1。一般而言,知道m(xù)(x)和g(x)就可以生成全部碼字。但是由式(9－34)直接產(chǎn)生的碼字并非系統(tǒng)碼,因?yàn)樾畔⒃捅O(jiān)督元沒有分開。只有使用典型生成矩陣并按照式(9－33)得出的碼字才是系統(tǒng)碼,或者運(yùn)用代數(shù)算法求出系統(tǒng)循環(huán)碼。由于循環(huán)碼的所有碼多項(xiàng)式都是g(x)的倍數(shù),最高次數(shù)為n-1,因此系統(tǒng)循環(huán)碼多項(xiàng)式可以表示為(9－35)上述(7,3)循環(huán)碼的生成多項(xiàng)式g(x)是xn+1的一個(gè)n-k=4的一個(gè)因式,因?yàn)?/p>

xn+1=(x+1)(x3+x2+1)(x3+x+1)n-k=4的因式有兩個(gè):(x+1)(x3+x2+1)=x4+x2+x+1(x+1)(x3+x+1)=x4+x3+x2+1(9－36)(9－37)

以上兩式都可以作為碼生成多項(xiàng)式g(x)。選用的生成多項(xiàng)式不同,產(chǎn)生的循環(huán)碼的碼組也不同。這里的(7,3)循環(huán)碼對(duì)應(yīng)的碼生成多項(xiàng)式g(x)是式(9－36),所產(chǎn)生的循環(huán)碼就是表9－8列出的碼。9.5.3監(jiān)督多項(xiàng)式及監(jiān)督矩陣為了便于對(duì)循環(huán)碼編譯碼，通常還定義監(jiān)督多項(xiàng)式，令

其中g(shù)(x)是常數(shù)項(xiàng)為1的r次多項(xiàng)式，是生成多項(xiàng)式；h(x)是常數(shù)項(xiàng)為1的k次多項(xiàng)式，稱為監(jiān)督多項(xiàng)式。同理，可得監(jiān)督矩陣H

(9-38)(9-39)是h(x)的逆多項(xiàng)式。例如(7，3)循環(huán)碼，其中則

即

9.5.4編碼方法

在編碼時(shí)，首先要根據(jù)給定的(n,k)值選定生成多項(xiàng)式g(x)，即應(yīng)在xn+1的因式中選一r=n-k次多項(xiàng)式作為g(x)。設(shè)編碼前的信息多項(xiàng)式m(x)為(9-40)m(x)的最高冪次為k-1。循環(huán)碼中的所有碼多項(xiàng)式都可被g(x)整除，根據(jù)這條原則，就可以對(duì)給定的信息進(jìn)行編碼。用xr乘m(x)，得到xr·m(x)的次數(shù)小于n。用g(x)去除xr·m(x)，得到余式R(x),R(x)的次數(shù)必小于g(x)的次數(shù)，即小于(n-k)。將此余式加于信息位之后作為監(jiān)督位，即將R(x)與xrm(x)相加，得到的多項(xiàng)式必為一碼多項(xiàng)式，因?yàn)樗啬鼙籫(x)整除，且商的次數(shù)不大于(k-1)。循環(huán)碼的碼多項(xiàng)式可表示為(9-41)其中，xr·m(x)代表信息位，R(x)是xr·m(x)與g(x)相除得到的余式，代表監(jiān)督位。圖9-2(7,3)循環(huán)碼編碼電路

編碼電路的主體由生成多項(xiàng)式構(gòu)成的除法電路，再加上適當(dāng)?shù)目刂齐娐方M成。g(x)=x4+x3+x2+1時(shí)，(7,3)循環(huán)碼的編碼電路如圖9-2所示。

g(x)的次數(shù)等于移位寄存器的級(jí)數(shù)；g(x)的x0,x1,x2,…、xr的非零系數(shù)對(duì)應(yīng)移位寄存器的反饋抽頭。首先，移位寄存器清零，3位信息元輸入時(shí)，門1斷開,門2接通，直接輸出信息元。第3次移位脈沖到來時(shí)將除法電路運(yùn)算所得的余數(shù)存入移位寄存器。第4～7次移位時(shí)，門2斷開，門1接通，輸出監(jiān)督元。具體編碼過程如表10-5所示，此時(shí)輸入信息元為110。表9-9(7,3)循環(huán)碼的編碼過程9.5.5解碼方法接收端譯碼的目的是檢錯(cuò)和糾錯(cuò)。由于任一碼多項(xiàng)式A(x)都應(yīng)能被生成多項(xiàng)式g(x)整除,所以在接收端可以將接收碼組B(x)用生成多項(xiàng)式去除。當(dāng)傳輸中未發(fā)生錯(cuò)誤時(shí),接收碼組和發(fā)送碼組相同,即A(x)=B(x),故接收碼組B(x)必定能被g(x)整除。若碼組在傳輸中發(fā)生錯(cuò)誤,則B(x)≠A(x),B(x)除以g(x)時(shí)除不盡而有余項(xiàng)。所以,可以用余項(xiàng)是否為0來判別碼組中有無誤碼。對(duì)于糾正單個(gè)錯(cuò)誤,單個(gè)錯(cuò)誤出現(xiàn)在接收碼組首位時(shí)的(7,3)循環(huán)碼譯碼電路如圖9－3所示。由于循環(huán)碼的伴隨式也具有移位特性,因此利用移存器的循環(huán)移位就可以糾正任何一位上的單個(gè)錯(cuò)誤。圖9-3(7,3)循環(huán)碼譯碼電路表9－10

(7,3)循環(huán)碼的譯碼過程9.6卷積碼9.6.1卷積碼的概念卷積碼的編碼器是由一個(gè)有k個(gè)輸入位、n個(gè)輸出位,且有m節(jié)移位寄存器構(gòu)成的有限狀態(tài)的有記憶系統(tǒng),其原理圖如圖9－4所示。圖9－5是一個(gè)具體卷積碼(2,1,2)的編碼器原理圖。它由移位寄存器、模2加法器及開關(guān)電路組成。圖9－4卷積碼的編碼器原理圖圖9-5卷積碼(2,1,2)編碼器起始狀態(tài)各級(jí)移位寄存器清零,即D1D2為00。u等于當(dāng)前輸入數(shù)據(jù),而移位寄存器狀態(tài)D1D2存儲(chǔ)以前的數(shù)據(jù),輸出碼字Ci由下式確定:當(dāng)輸入數(shù)據(jù)D=u1,u2,…，ui時(shí)，輸出碼字為(C1C2)1，(C1C2)2，…，(C1C2)i。圖9－6卷積碼(2,1,2)解碼器9.6.2卷積碼的圖解表示

1.樹圖樹圖描述的是在任何數(shù)據(jù)序列輸入時(shí),碼字所有可能的輸出。有一個(gè)(2,1,2)卷積碼的編碼電路如圖9－7所示,可以畫出其樹圖如圖9－8所示。當(dāng)輸入碼組為11010時(shí),編碼器的工作過程如表9－11所示。圖9－7

(2,1,2)卷積碼的編碼電路圖9－8

(2,1,2)碼的樹狀圖表9－11

(2,1,2)編碼器的工作過程

2.狀態(tài)圖除了用樹圖表示編碼器的工作過程外，還可以用狀態(tài)圖來描述。圖9－9就是該(2,1,2)卷積編碼器的狀態(tài)圖。圖9－9

(2,1,2)碼的狀態(tài)圖

3.格圖格圖也稱網(wǎng)絡(luò)圖或籬笆圖，它由狀態(tài)圖在時(shí)間上展開而得到，如圖9-10所示。圖中畫出了所有可能的數(shù)據(jù)輸入時(shí)，狀態(tài)轉(zhuǎn)移的全部可能軌跡，實(shí)線表示數(shù)據(jù)為0，虛線表示數(shù)據(jù)為

1，

線旁數(shù)字為輸出碼字，節(jié)點(diǎn)表示狀態(tài)。

圖9-10(2,1,2)碼的格圖9.6.3卷積碼的譯碼

1.維特比譯碼維特比譯碼是一種最大似然譯碼算法。最大似然譯碼算法的基本思路是：把接收碼字與所有可能的碼字比較，選擇一種碼距最小的碼字作為解碼輸出。由于接收序列通常很長(zhǎng)，所以維特比譯碼時(shí)最大似然譯碼做了簡(jiǎn)化，即它把接收碼字分段累接處理，每接收一段碼字，計(jì)算、比較一次，

保留碼距最小的路徑，直至譯完整個(gè)序列。

現(xiàn)以上述(2，1，2)碼為例說明維特比譯碼過程。設(shè)發(fā)送端的信息數(shù)據(jù)D=［11010000］，由編碼器輸出的碼字C=［1101010010110000］，接收端接收的碼序列B=［0101011010010010］，有4位碼元差錯(cuò)。下面參照?qǐng)D10-8的格狀圖說明譯碼過程。如圖9-11所示，先選前3個(gè)碼作為標(biāo)準(zhǔn)，對(duì)到達(dá)第3級(jí)的4個(gè)節(jié)點(diǎn)的8條路徑進(jìn)行比較，逐步算出每條路徑與接收碼字之間的累計(jì)碼距。累計(jì)碼距分別用括號(hào)內(nèi)的數(shù)字標(biāo)出，對(duì)照后保留一條到達(dá)該節(jié)點(diǎn)的碼距較小的路徑作為幸存路徑。再將當(dāng)前節(jié)點(diǎn)移到第4級(jí)，計(jì)算、比較、保留幸存路徑，直至最后得到到達(dá)終點(diǎn)的一條幸存路徑，即為解碼路徑，

如圖

9-11中實(shí)線所示。

根據(jù)該路徑，

得到解碼結(jié)果。

圖9－11維特比譯碼格圖2.序列譯碼當(dāng)m很大時(shí)，可以采用序列譯碼法。其過程如下：譯碼先從碼樹的起始節(jié)點(diǎn)開始，把接收到的第一個(gè)子碼的n個(gè)碼元與自始節(jié)點(diǎn)出發(fā)的兩條分支按照最小漢明距離進(jìn)行比較，沿著差異最小的分支走向第二個(gè)節(jié)點(diǎn)。在第二個(gè)節(jié)點(diǎn)上，譯碼器仍以同樣原理到達(dá)下一個(gè)節(jié)點(diǎn)，以此類推，最后得到一條路徑。若接收碼組有錯(cuò)，則自某節(jié)點(diǎn)開始，譯碼器就一直在不正確的路徑中行進(jìn)，譯碼也一直錯(cuò)誤。因此，譯碼器有一個(gè)門限值，當(dāng)接收碼元與譯碼器所走的路徑上的碼元之間的差異總數(shù)超過門限值時(shí)，譯碼器判定有錯(cuò)，并且返回試走另一分支。經(jīng)數(shù)次返回找出一條正確的路徑，最后譯碼輸出。*9.7網(wǎng)格編碼調(diào)制9.7.1

TCM信號(hào)的產(chǎn)生

TCM的編碼和調(diào)制方法是建立在Ungerboeck提出的集劃分方法的基礎(chǔ)上的。TCM有三個(gè)基本操作:①采用擴(kuò)展的信號(hào)星座,其信號(hào)集大于同樣的數(shù)據(jù)率對(duì)非網(wǎng)格編碼調(diào)制所需的信號(hào)集,從而得到冗余信號(hào)點(diǎn),以便用以代替冗余碼。②將擴(kuò)展的信號(hào)星座進(jìn)行逐級(jí)分割,以使每級(jí)子集的最小Euclide距離最大。③進(jìn)行卷積編碼和信號(hào)映射,只應(yīng)用某些信號(hào)點(diǎn)的序列,以達(dá)到盡量增大漢明(Hamming)距離。上述前兩條構(gòu)成TCM的一個(gè)重要技術(shù),即調(diào)制信號(hào)集的分割原理。這種劃分方法的基本原則是將信號(hào)星座圖劃分成若干子集,使子集中的信號(hào)點(diǎn)間的距離比原來的大,每劃分一次,新的子集中信號(hào)點(diǎn)間的距離就增大一次。圖9－12中給出了8PSK信號(hào)星座圖劃分的過程。8PSK星座有8個(gè)信號(hào)點(diǎn)均勻分布在半徑為1的圓周上,其最小Euclide距離d0=0.765。首先將這個(gè)8PSK星座劃分為B0和B1兩個(gè)子集,在子集中相鄰信號(hào)點(diǎn)間的距離為d1,。將這兩個(gè)子集再劃分一次,得到4個(gè)子集C0、C1、C2和C3,它們中相鄰信號(hào)點(diǎn)間的距離為d2=2。顯然,d2>d1>d0。圖9－128PSK信號(hào)星座圖的分割原理

上述TCM系統(tǒng)的例子中,需要根據(jù)已編碼的3個(gè)比特來選擇信號(hào)點(diǎn),即選擇波形的相位。這個(gè)系統(tǒng)中卷積碼編碼器的方框圖如圖9－13所示。由圖可見,這個(gè)卷積碼的約束長(zhǎng)度等于3。編碼器輸出的前兩個(gè)比特c1和c2用來選擇星座圖劃分的路徑,最后1個(gè)比特c3用于選定星座圖第3級(jí)(最低級(jí))中的信號(hào)點(diǎn)。在圖9－12中,c1,c2,c3表示已編碼的3個(gè)碼元,圖中最下一行注明了c1c2c3的值。圖9－13一種TCM編碼器方框圖一般來說,TCM編碼器結(jié)構(gòu)如圖9－14所示,它將k比特輸入信息分為k1和k2兩段,前k1比特通過一個(gè)(n1,k1,K)卷積碼編碼器,產(chǎn)生n1比特輸出,用于選擇信號(hào)星座圖中2n1個(gè)劃分之一,后面的k2比特用于選定星座圖中的信號(hào)點(diǎn)。這表明星座圖被劃分為2n1個(gè)子集,每個(gè)子集中含有2n2個(gè)信號(hào)點(diǎn)。在圖9－13中,k1=k2=1。圖9－14

TCM編碼器的一般結(jié)構(gòu)圖圖9－15給出了這個(gè)8PSK系統(tǒng)的網(wǎng)格圖。由于未編碼比特有兩種取值,所以每個(gè)狀態(tài)下有兩根線。例如,設(shè)初始狀態(tài)b1b2=00,k1=k2=0。當(dāng)輸入信號(hào)序列k1為“0110100”時(shí),移存器狀態(tài)以及輸出c1c2之間的關(guān)系如表9－12所示。圖9－158PSK編碼器網(wǎng)格圖9.7.2

TCM信號(hào)的解調(diào)

TCM信號(hào)的解調(diào)通常都采用維特比算法,但是現(xiàn)在的網(wǎng)格圖表示的狀態(tài)是波形,而不是碼組。解碼器的任務(wù)是計(jì)算接收信號(hào)序列路徑和各種可能的編碼網(wǎng)格路徑(簡(jiǎn)稱可能路徑)間的距離。若所有發(fā)送信號(hào)序列是等概率的,則判定與接收序列距離最小的可能路徑(又稱為最大似然路徑)為發(fā)送序列。假若選用全“0”序列作為測(cè)試序列,如圖9－16中虛線路徑U所示。圖中還用實(shí)線給出另一許用波形序列路徑V,它從全“0”序列路徑分開,又回到全“0”序列路徑。若發(fā)送序列是全“0”序列,但是接收序列中有錯(cuò)誤,使接收序列路徑離開全“0”路徑,然后又回到全“0”序列,且中間沒有返回狀態(tài)a,則解碼器需要比較此接收序列路徑和U的距離與接收序列路徑和V的距離之大小。若后者小,則將發(fā)生一次錯(cuò)誤判決。這里的距離指歐氏距離。圖9－16

8PSK解碼路徑示意圖這里,我們將引入自由歐氏距離Fed(FreeEuclideanDistance)的概念。自由歐氏距離是指許用波形序列集合中各元素之間的最小距離,它決定了產(chǎn)生錯(cuò)誤判決的概率。自由歐氏距離越大,錯(cuò)誤判決的概率越小。在上例中,按照在歐氏空間求矢量和的方法,U和V兩條路徑間的歐氏距離d為因此(9－42)

另外一種許用波形序列的路徑是U1WU3,如圖9－16的上端所示。它和V序列相似,從狀態(tài)a開始,離開U,再回到狀態(tài)a。這個(gè)路徑和U的距離為d2=d2(U1,U1)+d2(U2,W)+d2(U3,U3)＝d2(000,000)+d2(000,001)+d2(000,010)＝0＋(2)2＋0

=4即d=2(9－43)比較式(9－42)和式(9－43)可見,路徑U1WU3和路徑V相比,前者和路徑U的距離更小。并且可以逐個(gè)驗(yàn)證,這是和路徑U距離最小的許用序列的路徑。因此,按照上述定義,式(9－43)中的距離就是這種編碼的自由歐氏距離。故可以將其寫為dFed＝2(9－44)另一方面,未編碼的QPSK信號(hào)的碼元之間沒有約束,將其自由歐氏距離作為參考距離dRef,則由圖9－12可知(9－45)由此可見,與未編碼QPSK系統(tǒng)相比,8PSK的TCM系統(tǒng)可以獲得的漸近編碼增益為(9－46)第10章偽隨機(jī)序列及應(yīng)用10.1偽隨機(jī)序列的概念10.2正交碼與偽隨機(jī)碼10.3偽隨機(jī)序列的產(chǎn)生10.4

m序列10.5沃爾什碼10.6偽隨機(jī)序列的應(yīng)用10.1偽隨機(jī)序列的概念

在通信技術(shù)中，隨機(jī)噪聲是造成通信質(zhì)量下降的重要因素，因而它最早受到人們的關(guān)注。如果信道中存在著隨機(jī)噪聲，對(duì)于模擬信號(hào)來說，輸出信號(hào)就會(huì)產(chǎn)生失真，對(duì)于數(shù)字信號(hào)來說，解調(diào)輸出就會(huì)出現(xiàn)誤碼。另外，如果信道的信噪比下降，那么信道的傳輸容量將會(huì)受到限制。

偽隨機(jī)序列應(yīng)當(dāng)具有類似隨機(jī)序列的性質(zhì)。在工程上常用二元{0，1}序列來產(chǎn)生偽噪聲碼，它具有以下幾個(gè)特點(diǎn)：

(1)在隨機(jī)序列的每一個(gè)周期內(nèi)0和1出現(xiàn)的次數(shù)近似相等。

(2)每一周期內(nèi)，長(zhǎng)度為n的游程取值(相同碼元的碼元串)出現(xiàn)的次數(shù)比長(zhǎng)度為n+1的游程次數(shù)多一倍。

(3)隨機(jī)序列的自相關(guān)類似于白噪聲自相關(guān)函數(shù)的性質(zhì)。10.2正交碼與偽隨機(jī)碼

若M個(gè)周期為T的模擬信號(hào)s1(t)，s2(t)，…，sM(t)構(gòu)成正交信號(hào)集合，則有

(10-1)

設(shè)序列周期為p的編碼中，碼元只取值+1和-1,而x和y是其中兩個(gè)碼組:常數(shù)i=j0式中，xi,yi∈（+1，-1）,i=1,2,…，n,則x

和y之間的互相關(guān)函數(shù)定義為(10-2)

若碼組x和y正交，則有ρ(x,y)=0。如果一種編碼碼組中任意兩者之間的相關(guān)系數(shù)都為0，即碼組兩兩正交，這種兩兩正交的編碼就稱為正交編碼。由于正交碼各碼組之間的相關(guān)性很弱，受到干擾后不容易互相混淆，因而具有較強(qiáng)的抗干擾能力。類似地，對(duì)于長(zhǎng)度為ρ的碼組x的自相關(guān)函數(shù)定義為

(10-3)

對(duì)于{0，1}二進(jìn)制碼，

式(11-2)的互相關(guān)函數(shù)定義可簡(jiǎn)化為

ρ(x,y)=(A-D)/(A+D)=(A-D)/p

(10-4)式中，A是x和y中對(duì)應(yīng)碼元相同的個(gè)數(shù)；D是x和y中對(duì)應(yīng)碼元不同的個(gè)數(shù)。式(11-3)的自相關(guān)函數(shù)也表示為ρx(j)=(A-D)/(A+D)=(A-D)/p

(10-5)式中，A是碼字xi與其位移碼字xi+j的對(duì)應(yīng)碼元相同的個(gè)數(shù)：D是對(duì)應(yīng)碼元不同的個(gè)數(shù)。偽隨機(jī)碼具有白噪聲的統(tǒng)計(jì)特性，因此，對(duì)偽隨機(jī)碼定義可寫為

(1)凡自相關(guān)函數(shù)具有（10-6）

形式的碼，

稱為偽隨機(jī)碼，

又稱為狹義偽隨機(jī)碼。

（2）

凡自相關(guān)函數(shù)具有

（10-7）

形式的碼，稱為廣義偽隨機(jī)碼。狹義偽隨機(jī)碼是廣義偽隨機(jī)碼的特例。

10.3偽隨機(jī)序列的產(chǎn)生

編碼理論的數(shù)學(xué)基礎(chǔ)是抽象代數(shù)的有限域理論。一個(gè)有限域是指集合F元素個(gè)數(shù)是有限的，而且滿足所規(guī)定的加法運(yùn)算和乘法運(yùn)算中的交換律、結(jié)合律、分配律等。常用的只含（0，1）兩個(gè)元素的二元集F2,由于受自封性的限制，這個(gè)二元集只有對(duì)模二加和模二乘才是一個(gè)域。一般來說，對(duì)整數(shù)集Fp={0,1,2,…,p-1},若p為素?cái)?shù)，對(duì)于模p的加法和乘法來說，F(xiàn)p是一個(gè)有限域。

可以用移位寄存器作為偽隨機(jī)碼產(chǎn)生器，產(chǎn)生二元域F2及其擴(kuò)展域F2m中的各個(gè)元，m為正整數(shù)?？捎糜蛏隙囗?xiàng)式來表示一個(gè)碼組，

域上多項(xiàng)式定義為

（10-8）

稱其為F的n階多項(xiàng)式，加號(hào)為模二和。式中，ai是F的元，anxn稱為f(x)的首項(xiàng)，an是f(x)的首項(xiàng)系數(shù)。記F域上所有多項(xiàng)式組成的集合為F(x)。若g(x)是F(x)中的另一多項(xiàng)式，

（10-9）

如果n≥m，規(guī)定f(x)和g(x)的模二和為

（10-10）

其中,bm+1=bm+2=…=bn=0。

規(guī)定f(x)和g(x)的模二乘為

（10-11）

若g(x)≠0，則在F(x)總能找到一對(duì)多項(xiàng)式q(x)(稱為商)和r(x)(稱為余式)使得

f(x)=q(x)g(x)+r(x)（10-12）

這里r(x)的階數(shù)小于g(x)的階數(shù)。

式（10-12）稱為帶余除法算式，當(dāng)余式r(x)=0,就說f(x)可被g(x)整除。

圖10-1是一個(gè)4級(jí)移位寄存器，用它就可產(chǎn)生偽隨機(jī)序列。規(guī)定移位寄存器的狀態(tài)是各級(jí)存數(shù)從右至左的順序排列而成的序列，這樣的狀態(tài)叫正狀態(tài)或簡(jiǎn)稱狀態(tài)；反之，稱移位寄存器狀態(tài)是各級(jí)存數(shù)從左至右的順序排列而成的序列叫反狀態(tài)。圖10-1中的反饋邏輯為

(10-13)圖

10-14級(jí)移位寄存器

當(dāng)移位寄存器的初始狀態(tài)是1000時(shí)，即an-4=1,an-3=0,an-2=0,an-1=0,經(jīng)過一個(gè)時(shí)鐘節(jié)拍后，各級(jí)狀態(tài)自左向右移到下一級(jí)，末級(jí)輸出一位數(shù)，與此同時(shí)模二加法器輸出加到移位寄存器第一級(jí)，從而形成移位寄存器的新狀態(tài)，下一個(gè)時(shí)鐘節(jié)拍到來又繼續(xù)上述過程，末級(jí)輸出序列就是偽隨機(jī)序列。在這種條件下，圖11-1產(chǎn)生的偽隨機(jī)序列是{an-4}=1000100110101111000100110101111…P=15這是一個(gè)周期長(zhǎng)度p=15的隨機(jī)序列。

當(dāng)圖10-1的初始狀態(tài)是0狀態(tài)時(shí)，即an-4=an-3=an-2=an-1=0移存器的輸出是一個(gè)0序列。

4級(jí)移存器共有16個(gè)狀態(tài)，除去一個(gè)0狀態(tài)外，還有15個(gè)狀態(tài)。對(duì)于圖10-1來說，只要隨機(jī)序列的周期達(dá)到最大值，這時(shí)無論如何改變移存器的初始狀態(tài)，其輸出只改變序列的初相，序列的排序規(guī)律不會(huì)改變。但是，如果改變圖10-1四級(jí)移存器的反饋邏輯，其輸出序列就會(huì)發(fā)生變化。例如，

當(dāng)反饋邏輯變成

(10-14)時(shí)，給定不同的初始狀態(tài)1111、0001、1011，可以得到三個(gè)完全不同的輸出序列111100111100…，

000101000001…，

101101101101它們的周期分別是6、6和3。

由此，我們可以得出以下幾點(diǎn)結(jié)論：（1）線性移位寄存器的輸出序列是一個(gè)周期序列。（2）當(dāng)初始狀態(tài)是0狀態(tài)時(shí)，線性移位寄存器的輸出是一個(gè)0序列。（3）級(jí)數(shù)相同的線性移位寄存器的輸出序列與寄存器的反饋邏輯有關(guān)。（4）序列周期p<2n-1(n級(jí)線性移位寄存器)的同一個(gè)線性移存器的輸出還與起始狀態(tài)有關(guān)。（5）序列周期p=2n-1的線性移位寄存器，改變移位寄存起初始狀態(tài)只改變序列的起始相位，而周期序列排序規(guī)律不變。10.4m

序

列

10.4.1線性反饋移位寄存器的特征多項(xiàng)式

1.線性反饋移位寄存器的遞推關(guān)系式遞推關(guān)系式又稱為反饋邏輯函數(shù)或遞推方程。設(shè)圖10-2所示的線性反饋移位寄存器的初始狀態(tài)為(a0a1…an-2an-1)，經(jīng)一次移位線性反饋，移位寄存器左端第一級(jí)的輸入為若經(jīng)k次移位，則第一級(jí)的輸入為

(10-15)其中，l=n+k-1≥n,k=1,2,3,…

由此可見，移位寄存器第一級(jí)的輸入，由反饋邏輯及移位寄存器的原狀態(tài)所決定。式(10-15)稱為遞推關(guān)系式。圖

10-2n級(jí)線性反饋移位寄存器

2.線性反饋移位寄存器的特征多項(xiàng)式用多項(xiàng)式f(x)來描述線性反饋移位寄存器的反饋連接狀態(tài)：(10-16)式(10-16)稱為特征多項(xiàng)式或特征方程。其中，xi存在，表明ci=1，否則ci=0，x本身的取值并無實(shí)際意義。ci的取值決定了移位寄存器的反饋連接。由于c0=cn=1，因此，f(x)是一個(gè)常數(shù)項(xiàng)為1的n次多項(xiàng)式，n為移位寄存器級(jí)數(shù)。

可以證明，一個(gè)n級(jí)線性反饋移位寄存器能產(chǎn)生m序列的充要條件是它的特征多項(xiàng)式為一個(gè)n次本原多項(xiàng)式。若一個(gè)n次多項(xiàng)式f(x)滿足下列條件:(1)f(x)為既約多項(xiàng)式(即不能分解因式的多項(xiàng)式)；

(2)f(x)可整除(xp+1),p=2n-1;(3)f(x)除不盡(xq+1),q<p。則稱f(x)為本原多項(xiàng)式。以上為我們構(gòu)成m序列提供了理論根據(jù)。10.4.2m序列產(chǎn)生器用線性反饋移位寄存器構(gòu)成m序列產(chǎn)生器，關(guān)鍵是由特征多項(xiàng)式f(x)來確定反饋線的狀態(tài)，而且特征多項(xiàng)式f(x)必須是本原多項(xiàng)式?，F(xiàn)以n=4為例來說明m序列產(chǎn)生器的構(gòu)成。用4級(jí)線性反饋移位寄存器產(chǎn)生的m序列，其周期為p=24-1=15，其特征多項(xiàng)式f(x)是4次本原多項(xiàng)式，能整除(x15+1)。先將(x15+1)分解因式，使各因式為既約多項(xiàng)式，再尋找f(x)。其中，4次既約多項(xiàng)式有3個(gè)，但(x4+x3+x2+x+1)能整除(x5+1)，故它不是本原多項(xiàng)式。因此找到兩個(gè)4次本原多項(xiàng)式(x4+x+1)和(x4+x3+1)。由其中任何一個(gè)都可產(chǎn)生m序列。用f(x)=(x4+x+1)構(gòu)成的m序列產(chǎn)生器如圖10-3所示。圖

10-3m序列產(chǎn)生器

設(shè)4級(jí)移位寄存器的初始狀態(tài)為1000。c4=c1=c0=1,c3=c2=0。輸出序列{ak}的周期長(zhǎng)度為

15。

10.4.3m序列的性質(zhì)

1.均衡特性(平衡性)m序列每一周期中1的個(gè)數(shù)比0的個(gè)數(shù)多1個(gè)。由于p=2n-1為奇數(shù)，因而在每一周期中1的個(gè)數(shù)為(p+1)/2=2n-1(偶數(shù))，而0的個(gè)數(shù)為(p-1)/2=2n-1-1(奇數(shù))。上例中p=15,1的個(gè)數(shù)為8，0的個(gè)數(shù)為7。當(dāng)p足夠大時(shí)，在一個(gè)周期中1與0出現(xiàn)的次數(shù)基本相等。

2.游程特性(游程分布的隨機(jī)性)

我們把一個(gè)序列中取值(1或0)相同連在一起的元素合稱為一個(gè)游程。在一個(gè)游程中元素的個(gè)數(shù)稱為游程長(zhǎng)度。例如圖

11-2中給出的m序列

{ak}=000111101011001…在其一個(gè)周期的15個(gè)元素中，共有8個(gè)游程，其中長(zhǎng)度為4的游程1個(gè)，即1111;長(zhǎng)度為3的游程1個(gè)，即000；長(zhǎng)度為2的游程2個(gè)，即11與00；長(zhǎng)度為1的游程

4個(gè)，

即

2個(gè)

1與

2個(gè)

0。

m序列的一個(gè)周期(p=2n-1)中，游程總數(shù)為2n-1。其中，長(zhǎng)度為1的游程個(gè)數(shù)占游程總數(shù)的1/2；長(zhǎng)度為2的游程個(gè)數(shù)占游程總數(shù)的1/22=1/4；長(zhǎng)度為3的游程個(gè)數(shù)占游程總數(shù)的1/23=1/8；等等。一般地，長(zhǎng)度為k的游程個(gè)數(shù)占游程總數(shù)的1/2k=2-k，其中1≤k≤(n-2)。而且，在長(zhǎng)度為k的游程中，連1游程與連0游程各占一半，長(zhǎng)為(n-1)的游程是連0游程，長(zhǎng)為

n

的游程是連1游程。

3.移位相加特性(線性疊加性)

m序列和它的位移序列模二相加后所得序列仍是該m序列的某個(gè)位移序列。設(shè)mr是周期為p的m序列mp的r次延遲移位后的序列，

那么

(10-17)其中，ms為mp某次延遲移位后的序列。例如，

mp=000111101011001,…mp延遲兩位后得mr,再模二相加

mr=010001111010110,…

ms=mp⊕mr=010110010001111,…

可見，ms=mp⊕mr為mp延遲

8位后的序列。

4.自相關(guān)特性

m序列具有非常重要的自相關(guān)特性。在m序列中，常常用+1代表0，用-1代表1。此時(shí)定義：設(shè)長(zhǎng)為

p的m序列，記作a1,a2,a3,…,ap(p=2n-1)經(jīng)過j次移位后，m序列為

aj+1,aj+2,aj+3,…,aj+p

其中，ai+p=ai(以p為周期)，以上兩序列的對(duì)應(yīng)項(xiàng)相乘然后相加，利用所得的總和

來衡量一個(gè)m序列與它的j次移位序列之間的相關(guān)程度，并把它叫做m序列(a1,a2,a3,…,ap)的自相關(guān)函數(shù)。

記作

(10-18)

當(dāng)采用二進(jìn)制數(shù)字

0和

1代表碼元的可能取值時(shí)，式(10-18)可表示為

(10-19)式中，A、D分別是m序列與其j次移位的序列在一個(gè)周期中對(duì)應(yīng)元素相同、不相同的數(shù)目。

式(10-19)還可以改寫為

(10-20)由移位相加特性可知，ai⊕ai+j仍是m序列中的元素，所以式(11-20)分子就等于m序列中一個(gè)周期中0的數(shù)目與1的數(shù)目之差。另外由m序列的均衡性可知，在一個(gè)周期中0比1的個(gè)數(shù)少一個(gè)，故得A-D=-1(j為非零整數(shù)時(shí))或p(j為零時(shí))。因此得(10-21)如圖

10-4所示。

m序列的自相關(guān)函數(shù)只有兩種取值(1和-1/p)。

R(j)是一個(gè)周期函數(shù)，

即

R(j)=R(j+kp)(10-22)式中，k=1,2,…,p=(2n-1)為周期。而且R(j)是偶函數(shù)，

即

R(j)=R(-j)j=整數(shù)

(10-23)圖

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

5.偽噪聲特性如果我們對(duì)一個(gè)正態(tài)分布白噪聲取樣，若取樣值為正，記為+1，若取樣值為負(fù)，記為-1，將每次取樣所得極性排成序列，可以寫成

…+1,-1,+1,+1,+1,-1,-1,+1,-1,…這是一個(gè)隨機(jī)序列，它具有如下基本性質(zhì)：

(1)序列中+1和-1出現(xiàn)的概率相等；

(2)序列中長(zhǎng)度為1的游程約占1/2，長(zhǎng)度為2的游程約占1/4，長(zhǎng)度為3的游程約占1/8,…一般地，長(zhǎng)度為k的游程約占1/2k，而且+1、-1游程的數(shù)目各占一半；

(3)由于白噪聲的功率譜為常數(shù)，因此其自相關(guān)函數(shù)為一沖擊函數(shù)δ(τ)。把m序列與上述隨機(jī)序列比較，當(dāng)周期長(zhǎng)度p足夠大時(shí)，m序列與隨機(jī)序列的性質(zhì)是十分相似的?？梢?，m序列是一種偽噪聲特性較好的偽隨機(jī)序列，且易產(chǎn)生，因此應(yīng)用十分廣泛。 10.5沃爾什碼沃爾什函數(shù)集是完備的非正弦型的二元(取值為+1與-1)正交函數(shù)集,其相應(yīng)的離散沃爾什函數(shù)簡(jiǎn)稱為沃爾什序列或沃爾什碼,用WN(n)表示,n為離散沃爾什函數(shù)的編號(hào),N為離散沃爾什函數(shù)長(zhǎng)度(即元素或碼元的個(gè)數(shù))。兩個(gè)離散沃爾什函數(shù)只有當(dāng)它們的編號(hào)和長(zhǎng)度相同時(shí),這兩個(gè)離散沃爾什函數(shù)才是相同的。離散沃爾什函數(shù)可由哈達(dá)馬(Hadamard)矩陣的行(或列)構(gòu)成。一階哈達(dá)馬矩陣為高階哈達(dá)馬矩陣的遞推公式如下:(10－24)式中:Nm=2m,m=1,2,3,…。例如:m=1時(shí),m=2時(shí),m=3時(shí),m=4,5,6,…時(shí),其哈達(dá)馬矩陣可依次遞推。Nm階哈達(dá)馬矩陣的通式可表示為(10－25)式中:Nm=2m,m=1,2,3,…(10－26)

10.6偽隨機(jī)序列的應(yīng)用10.6.1擴(kuò)展頻譜通信擴(kuò)展頻譜通信系統(tǒng)是將待傳送的基帶信號(hào)在頻域上擴(kuò)展為很寬的頻譜，遠(yuǎn)遠(yuǎn)大于原來信號(hào)的帶寬；在接收端再把已擴(kuò)展頻譜的信號(hào)變換到原來信號(hào)的頻帶上，恢復(fù)出原來的基帶信號(hào)。該系統(tǒng)的方框圖如圖10－5所示。圖10－5擴(kuò)展頻譜通信系統(tǒng)擴(kuò)展頻譜技術(shù)的理論基礎(chǔ)是香農(nóng)公式。對(duì)于加性白高斯噪聲的連續(xù)信道，其信道容量C與信道傳輸帶寬B及信噪比S/N之間的關(guān)系可以用下式表示:(10－27)

這個(gè)公式表明，在保持信息傳輸速率不變的條件下，信噪比和帶寬之間具有互換關(guān)系。就是說，可以用擴(kuò)展信號(hào)的頻譜作為代價(jià)，換取用很低信噪比傳送信號(hào)，同樣可以得到很低的差錯(cuò)率。擴(kuò)頻系統(tǒng)有以下特點(diǎn)：(1)具有選擇地址能力；(2)信號(hào)的功率譜密度很低，有利于信號(hào)的隱蔽；(3)有利于加密，防止竊聽；(4)抗干擾性強(qiáng)；(5)抗衰落能力強(qiáng)；(6)可以進(jìn)行高分辨率的測(cè)距。擴(kuò)頻通信系統(tǒng)的工作方式有：直接序列擴(kuò)頻、跳變頻率擴(kuò)頻、跳變時(shí)間擴(kuò)頻和混合式擴(kuò)頻。

1.直接序列擴(kuò)頻方式直接序列擴(kuò)頻(DirectSequenceSpreadSpectrum)又稱為直擴(kuò)(DS)，它是用高速率的偽隨機(jī)序列與信息序列模二加后的序列去控制載波的相位而獲得直擴(kuò)信號(hào)的。圖10-6(a)和(b)就是直擴(kuò)系統(tǒng)的原理方框圖和擴(kuò)頻信號(hào)傳輸圖。在圖10-6中，信息碼與偽碼模二加后產(chǎn)生發(fā)送序列，進(jìn)行2PSK調(diào)制后輸出。在接收端用一個(gè)和發(fā)射端同步的偽隨機(jī)碼所調(diào)制的本地信號(hào)，與接收到的信號(hào)進(jìn)行相關(guān)處理，相關(guān)器輸出中頻信號(hào)經(jīng)中頻電路和解調(diào)器，恢復(fù)原信息。圖10－6直擴(kuò)系統(tǒng)方框圖和擴(kuò)頻信號(hào)傳輸圖(a)直擴(kuò)系統(tǒng)原理方框圖;(b)擴(kuò)頻信號(hào)傳輸圖

2.跳變頻率擴(kuò)頻方式跳變頻率擴(kuò)頻(FrequencyHoppingSpreadSpectrum)又稱跳頻(FH)，它是用偽碼構(gòu)成跳頻指令來控制頻率合成器，并在多個(gè)頻率中進(jìn)行選擇的移頻鍵控。跳頻指令由所傳信息碼與偽隨機(jī)碼模二加的組合來構(gòu)成，它又稱為跳頻圖案。跳頻系統(tǒng)原理圖如圖10－7所示。圖10－7跳頻系統(tǒng)原理圖

3.跳變時(shí)間擴(kuò)頻方式跳變時(shí)間擴(kuò)頻(TimeHoppingSpreadSpectrum)又稱為跳時(shí)(TH)，該系統(tǒng)是用偽碼序列來啟閉信號(hào)的發(fā)射時(shí)刻和持續(xù)時(shí)間的。該方式一般和其他方式混合使用。以上

3種工作方式是基本的工作方式，

最常用的是直擴(kuò)方式和跳頻方式兩種。

4.混合式擴(kuò)頻方式在實(shí)際系統(tǒng)中，僅僅采用單一工作方式不能達(dá)到所希望的性能時(shí)，往往采用兩種或兩種以上工作方式的混合式擴(kuò)頻。

如FH/DS,DS/TH,FH/TH等。

10.6.2碼分多址(CDMA)通信碼分多址系統(tǒng)給每個(gè)用戶分配一個(gè)多址碼。要求這些碼的自相關(guān)特性尖銳,而互相關(guān)特性的峰值盡量小,以便準(zhǔn)確識(shí)別和提取有用信息。同時(shí)各個(gè)用戶間的干擾可減小到最低限度。碼分多址系統(tǒng)有以下特點(diǎn):①所有用戶可以異步地共享整個(gè)頻帶資源,也就是說,不同用戶碼元發(fā)送信號(hào)的時(shí)間并不要求同步;②系統(tǒng)容量大;③信道數(shù)據(jù)率非常高。

1)跳頻碼分多址(FH－CDMA)跳頻是指將待傳送碼元的載波分量隨著時(shí)間順序受一個(gè)偽隨機(jī)序列控制而隨機(jī)跳動(dòng)。在該系統(tǒng)中,每個(gè)用戶根據(jù)各自的偽隨機(jī)序列,動(dòng)態(tài)改變其已調(diào)信號(hào)的中心頻率。各用戶的中心頻率可在給定的系統(tǒng)帶寬內(nèi)隨機(jī)改變。其主要特征是帶寬通常要比各用戶已調(diào)信號(hào)的帶寬寬得多。

FH－CDMA類似于FDMA,但使用的頻道是動(dòng)態(tài)變化的,且各用戶使用的頻率序列要求相互正交,在任一時(shí)刻都不相同。跳頻的具體實(shí)現(xiàn)方框圖如圖10－8所示。圖10－8跳頻發(fā)送、接收端實(shí)現(xiàn)框圖

2)直擴(kuò)碼分多址(DS－CDMA)在直接序列擴(kuò)頻碼分多址系統(tǒng)中,所有用戶工作在相同的中心頻率上,輸入數(shù)據(jù)序列與偽隨機(jī)序列相乘得到寬帶信號(hào)。不同的用戶(或信道)使用不同的偽隨機(jī)序列。這些偽隨機(jī)序列相互正交,從而可像FDMA和TDMA系統(tǒng)中利用頻率和時(shí)隙區(qū)分不同用戶一樣,利用偽隨機(jī)序列來區(qū)分不同的用戶。

(1)DS－CDMA系統(tǒng)框圖,DS－CDMA系統(tǒng)實(shí)現(xiàn)框圖如圖10－9所示。圖10－9

DS－CDMA系統(tǒng)發(fā)、收端實(shí)現(xiàn)框圖圖10－10

DS－CDMA構(gòu)成方式(a)用地址碼區(qū)分用戶;(b)用偽隨機(jī)碼區(qū)分用戶

(2)DS－CDMA構(gòu)成方式。DS－CDMA的方式有兩個(gè),如圖10－10所示。

(3)DS－CDMA特點(diǎn)。①具有抗干擾和抗多徑衰落的能力。數(shù)字信息的擴(kuò)展頻譜信號(hào)占有帶寬BW遠(yuǎn)遠(yuǎn)大于基帶信號(hào)帶寬BS。

BW與BS之比稱為擴(kuò)頻增益GP(GP=BW/BS)。它表示擴(kuò)頻系統(tǒng)解擴(kuò)后信噪比的改善程度。GP越大,抗干擾能力越強(qiáng)。②保密性能強(qiáng)。無論是直擴(kuò)還是跳頻,擴(kuò)頻后其頻譜均為近似白噪聲,因此具有良好的保密性能。③易于實(shí)現(xiàn)大容量多址通信。降低系統(tǒng)干擾,可直接提高系統(tǒng)容量。CDMA的系統(tǒng)容量為FDMA系統(tǒng)容量的20倍左右。④良好的隱蔽性能。由于擴(kuò)頻屬于寬帶系統(tǒng),因而頻帶越寬,功率譜密度就越低。⑤可與窄帶系統(tǒng)共存。許多碼分信道共用一個(gè)載波頻率,擴(kuò)頻傳輸?shù)目垢蓴_能力可使CDMA系統(tǒng)在相鄰小區(qū)重復(fù)使用該頻率,這不僅可使頻率分配和管理簡(jiǎn)單,而且可以與窄帶FDMA、TDMA系統(tǒng)共享頻帶,相互影響很小。⑥存在自身多址干擾和遠(yuǎn)近效應(yīng)。自身多址干擾的存在是因?yàn)樗杏脩舳脊ぷ髟谙嗤念l率上,且各用戶的地址不可能完全正交。因此進(jìn)入接收機(jī)的信號(hào)除了所希望的有用信號(hào)外,還疊加有其他用戶的地址碼信號(hào)(即多址干擾)。我們知道,多址干擾直接限制著系統(tǒng)容量的擴(kuò)大。多址干擾的大小取決于在該頻率上工作的用戶數(shù)及各用戶的功率大小。10.6.3通信加密數(shù)字通信的一個(gè)重要優(yōu)點(diǎn)是容易做到加密,在這方面m序列應(yīng)用很多。數(shù)字加密的基本原理如圖10-11所示。將信源產(chǎn)生的二進(jìn)制數(shù)字消息和一個(gè)周期很長(zhǎng)的m序列模二相加,這樣就將原消息變成不可理解的另一序列。將這種加密序列在信道中傳輸，被他人竊聽也不可理解其內(nèi)容。在接收端再加上一同樣的m序列，就能恢復(fù)為原發(fā)送消息。圖10-11利用m序列加密設(shè)信源發(fā)送的數(shù)碼為X1={1011010011…},m序列Y={1100001011…}。數(shù)碼X1與m序列Y的各對(duì)應(yīng)位分別進(jìn)行模二加運(yùn)算后，獲得序列E，顯然E不同于X1，它已失去了原信息的意義。如果不知道m(xù)序列Y，就無法解出攜帶原信息的數(shù)碼X1,從而起到保密作用。假設(shè)信道傳輸過程中無誤碼，序列E到達(dá)接收端后與m序列Y再進(jìn)行模二加運(yùn)算，可恢復(fù)原數(shù)碼X1

，即上述工作過程如圖

10-12所示。

圖

10-12數(shù)字信號(hào)的加密與解密

10.6.4誤碼率的測(cè)量在數(shù)字通信中誤碼率是一項(xiàng)主要的性能指標(biāo)。在實(shí)際測(cè)量數(shù)字通信系統(tǒng)的誤碼率時(shí)，一般測(cè)量結(jié)果與信源送出信號(hào)的統(tǒng)計(jì)特性有關(guān)。通常認(rèn)為二進(jìn)制信號(hào)中0和1是以等概率隨機(jī)出現(xiàn)的，所以測(cè)量誤碼率時(shí)最理想的信源應(yīng)是隨機(jī)信號(hào)產(chǎn)生器。