第7章差錯控制編碼和m

1、本章重點介紹常用的幾種控制編碼技術(shù)，要求掌握各類控制編碼技術(shù)的基本概念。M序列在現(xiàn)代通信中有重要的作用，所以，必須掌握它的概念和原理。l差錯控制編碼，又稱為信道編碼、可靠性編碼、抗干擾編碼或糾錯碼，它是提高數(shù)字信號可靠性的有效方法之一。l它產(chǎn)生于20世紀(jì)50年代初，發(fā)展到70年代趨向成熟。 l在數(shù)字通信中，根據(jù)不同的目的，編碼可分為信源編碼和信道編碼。l信源編碼是為了提高數(shù)字信號的有效性以及為了使模擬信號數(shù)字化而采取的編碼。l信道編碼是為了降低誤碼率，提高數(shù)字通信的可靠性而采取的編碼。l為了提高系統(tǒng)的抗干擾性能，可以加大發(fā)射功率，降低接收設(shè)備本身的噪聲，以及合理選擇調(diào)制、解調(diào)方法等。此外，還可

2、以采用信道編碼技術(shù)。l常用的差錯控制方式有3種：l 檢錯重發(fā)、前向糾錯和混合糾錯， l檢錯重發(fā)又稱自動請求重傳方式，記作ARQ（Automatic Repeat Request）。l如果發(fā)現(xiàn)錯誤，則通過反向信道把這一判決結(jié)果反饋給發(fā)端，然后，發(fā)端把收端認(rèn)為錯誤的信息再次重發(fā)，從而達(dá)到正確傳輸?shù)哪康?。l其特點是需要反饋信道，譯碼設(shè)備簡單，對突發(fā)錯誤和信道干擾較嚴(yán)重時有效，但實時性差，主要在計算機(jī)數(shù)據(jù)通信中得到應(yīng)用。l前向糾錯方式記作FEC（Forward Error Correction）。l發(fā)端發(fā)送能夠糾正錯誤的碼，收端收到信碼后自動地糾正傳輸中的錯誤。l其特點是單向傳輸，實時性好，但譯碼設(shè)備

3、較復(fù)雜。 l混合糾錯方式記作HEC（Hybrid Error Correction）是FEC和ARQ方式的結(jié)合。發(fā)端發(fā)送具有自動糾錯同時又具有檢錯能力的碼。收端收到碼后，檢查差錯情況，如果錯誤在碼的糾錯能力范圍以內(nèi)，則自動糾錯，如果超過了碼的糾錯能力，但能檢測出來，則經(jīng)過反饋信道請求發(fā)端重發(fā)。l這種方式具有自動糾錯和檢錯重發(fā)的優(yōu)點，可達(dá)到較低的誤碼率。 l（1）根據(jù)糾錯碼各碼組信息元和監(jiān)督元的函數(shù)關(guān)系，可分為線性碼和非線性碼。如果函數(shù)關(guān)系是線性的，即滿足一組線性方程式，則稱為線性碼，否則為非線性碼。l（2）根據(jù)上述關(guān)系涉及的范圍，可分為分組碼和卷積碼。分組碼的各碼元僅與本組的信息元有關(guān)；卷積碼

4、中的碼元不僅與本組的信息元有關(guān)，而且還與前面若干組的信息元有關(guān)。l（3）根據(jù)碼的用途，可分為檢錯碼和糾錯碼。檢錯碼以檢錯為目的，不一定能糾錯；而糾錯碼以糾錯為目的，一定能檢錯。 l1分組碼l分組碼一般可用(n，k)表示。l簡單地說，分組碼是對每段k位長的信息組以一定的規(guī)則增加r個監(jiān)督元，組成長為n的碼字。l在二進(jìn)制情況下，共有2k個不同的信息組，相應(yīng)地可得到2k個不同的碼字，稱為許用碼組。其余2n-2k個碼字未被選用，稱為禁用碼組。 l在分組碼中，非零碼元的數(shù)目稱為碼字的漢明重量，簡稱碼重。l例如，碼字10110，碼重w=3。l兩個等長碼組之間相應(yīng)位取值不同的數(shù)目稱為這兩個碼組的漢明（Hamm

5、ing）距離，簡稱碼距。例如110000與10011之間的距離d=3。碼組集中任意兩個碼字之間距離的最小值稱為碼的最小距離，用d0表示。最小碼距是碼的一個重要參數(shù)，它是衡量碼檢錯、糾錯能力的依據(jù)。l若分組碼碼字中的監(jiān)督元在信息元之后，而且是信息元的簡單重復(fù)，則稱該分組碼為重復(fù)碼。它是一種簡單實用的檢錯碼，并有一定的糾錯能力。例如（2，1）重復(fù)碼，兩個許用碼組是00與11，d0=2，收端譯碼，出現(xiàn)01、10禁用碼組時，可以發(fā)現(xiàn)傳輸中的一位錯誤。如果是（3，1）重復(fù)碼，兩個許用碼組是000與111，d0=3；當(dāng)收端出現(xiàn)兩個或三個1時，判為1，否則判為0。此時，可以糾正單個錯誤，或者該碼可以檢出兩個

6、錯誤。l碼的最小距離d0直接關(guān)系著碼的檢錯和糾錯能力；任一(n，k)分組碼，若要在碼字內(nèi)：l（1）檢測e個隨機(jī)錯誤，則要求碼的最小距離d0e+1；l（2）糾正t個隨機(jī)錯誤，則要求碼的最小距離d02t+1；l（3）糾正t個同時檢測e(t)個隨機(jī)錯誤，則要求碼的最小距離d0t+e+1。 l用差錯控制編碼提高通信系統(tǒng)的可靠性，是以降低有效性為代價換來的。我們定義編碼效率R來衡量有效性：lR=k/nl其中，k是信息元的個數(shù)，n為碼長。l對糾錯碼的基本要求是：檢錯和糾錯能力盡量強；編碼效率盡量高；編碼規(guī)律盡量簡單。際中要根據(jù)具體指標(biāo)要求，保證有一定糾、檢錯能力和編碼效率，并且易于實現(xiàn)。 l1奇偶監(jiān)督碼l

7、奇偶監(jiān)督碼是在原信息碼后面附加一個監(jiān)督元，使得碼組中“1”的個數(shù)是奇數(shù)或偶數(shù)?；蛘哒f，它是含一個監(jiān)督元，碼重為奇數(shù)或偶數(shù)的(n，n-1)系統(tǒng)分組碼。奇偶監(jiān)督碼又分為奇監(jiān)督碼和偶監(jiān)督碼。110010100000100001101001111000011100111000001010101010111000111100l碼字中1的數(shù)目與0的數(shù)目保持恒定比例的碼稱為恒比碼。l由于恒比碼中，每個碼組均含有相同數(shù)目的1和0，因此恒比碼又稱等重碼，定1碼。l這種碼在檢測時，只要計算接收碼元中1的數(shù)目是否正確，就知道有無錯誤。 l我國郵電部門電傳機(jī)傳輸漢字通信中普遍采用3:2碼，又稱“5中取3”的恒比碼，這

8、是5單位數(shù)字保護(hù)電報碼。我國每個漢字用4位阿拉伯?dāng)?shù)字表示，每個阿拉伯?dāng)?shù)字用5個比特的碼字表示。由于阿拉伯?dāng)?shù)字只有10個，因此從32中可能的碼字中挑出=10個1的個數(shù)為3個的碼字作為阿拉伯?dāng)?shù)字的編碼方式。l現(xiàn)以（7，4）分組碼為例來說明線性分組碼的特點。設(shè)其碼字為A=a7 a5 a4 a3 a2 a1 a0，其中前4位是信息元，后3位是監(jiān)督元，可用下列線性方程組來描述該分組碼，產(chǎn)生監(jiān)督元。265416530643aaaaaaaaaaaal循環(huán)碼除了具有線性碼的一般性質(zhì)外，具有許多特殊的代數(shù)性質(zhì)，如還具有循環(huán)性、并且簡化譯碼算法，目前發(fā)現(xiàn)的大部分線性碼與循環(huán)碼有密切關(guān)系。循環(huán)碼還有易于實現(xiàn)的特點，

9、很容易用帶反饋的移位寄存器實現(xiàn)其硬件。l由于循環(huán)碼具有碼的代數(shù)結(jié)構(gòu)清晰、性能較好、編譯碼簡單和易于實現(xiàn)的特點，因此在目前的計算機(jī)糾錯系統(tǒng)中所使用的線性分組碼幾乎都是循環(huán)碼。它不僅可以用于糾正獨立的隨機(jī)錯誤，而且也可以用于糾正突發(fā)錯誤。 l在代數(shù)理論中，為了便于計算，常用碼多項式表示碼字。(n，k)循環(huán)碼的碼字，其碼多項式（以降冪順序排列）為lA(x)=an-1xn-1+an-2xn-2+a1x+a0l如果一種碼的所有碼多項式都是多項式g(x)的倍式，則稱g(x)為該碼的生成多項式。在(n，k)循環(huán)碼中任意碼多項式A(x)都是最低次碼多項式的倍式。如表7-3的（7，3）循環(huán)碼中，g(x)=A1(

10、x)=x4+x3+x2+1l其他碼多項式都是g(x)的倍式，即lA0(x)=0 *g(x)lA2(x)=(x+1)* g(x)lA3(x)=x *g(x)llA7(x)=x2 *g(x)l為了便于對循環(huán)碼編譯碼，通常還定義監(jiān)督多項式，令 73231( )1( )*( )1xh xxxg xhxxxl在編碼時，首先要根據(jù)給定的(n，k)值選定生成多項式g(x)，即應(yīng)在xn+1的因式中選一r=n-k次多項式作為g(x)。設(shè)編碼前的信息多項式m(x)為：l循環(huán)碼的碼多項式可表示為lA(x)=xr *m(x)+R(x)21123( )kkm xaa xa xa xD0D1D2D3門1門2輸入信息組輸出

11、碼字1D0D1D2D37級緩存器接收碼組B輸出碼組A&l1基本概念l卷積碼又稱為連環(huán)碼，是1955年提出來的一種糾錯碼，它和分組碼有明顯的區(qū)別。（n，K）線性分組碼中，本組r=n-k個監(jiān)督元有關(guān)，與其他各組無關(guān)，也就是說分組碼編碼器本身并無記憶性。卷積碼則不同，每個（n，k）碼段（也稱為子碼，通常較短）內(nèi)的n個碼元不僅與該碼段內(nèi)的信息元有關(guān)，而且與前面m段的信息元有關(guān)。通常稱m為編碼存儲。卷積碼通常用符號（n，m，k）表示。 m1m2數(shù)據(jù)輸入碼字輸出S1S2S3C1C2l輸出碼字C由下式確定lC1=S1 S2 S3lC2=S1 S3l卷積碼常用的描述方法有矩陣法、圖解法。矩陣法太復(fù)雜，

12、圖解法直觀。常用的圖解法有3中：樹圖、狀態(tài)圖和格圖。l卷積碼的譯碼方法有代數(shù)譯碼法和概率譯碼法。前者是利用生成多項式來譯碼，最大的方法是大數(shù)邏輯譯碼。后者又有兩種方法：維特比譯碼和序列譯碼。目前，概率譯碼已成為卷積譯碼的最主要的方法。 lm序列又叫作偽隨機(jī)序列、偽噪聲（PN）碼或偽隨機(jī)碼。l可以預(yù)先確定并且可以重復(fù)實現(xiàn)的序列稱為確定序列。l既不能預(yù)先確定又不能重復(fù)實現(xiàn)的序列稱為隨機(jī)序列。l具有隨機(jī)特性，貌似隨機(jī)序列的確定序列稱為偽隨機(jī)序列。M序列是目前廣泛使用的一種偽隨機(jī)序列。l1線性反饋移位寄存器lm序列是由帶線性反饋的移位寄存器產(chǎn)生的周期最長的一種二進(jìn)制序列。線性反饋移位寄存器的一般結(jié)構(gòu)如

13、圖7-6所示。它由n級移位寄存器、若干模二加法器組成線性反饋邏輯網(wǎng)絡(luò)和時鐘脈沖產(chǎn)生器（省略未畫出來）連接而成。圖中移位寄存器的狀態(tài)用ai表示(i=0，1，n-1)，ci表示移位寄存器反饋線的連接狀態(tài)，相當(dāng)于反饋系數(shù)，ci=1表示此線接通，參與反饋邏輯運算，ci=0表示此線斷開，不參與運算，c0=cn=1。 an 11an 22a1n 1a0c1c2cn 1cn 1c0 1n輸出akl用4級線性反饋移位寄存器產(chǎn)生的m序列，其周期為p=24-1=15，其特征多項式f(x)是4次本原多項式，能整除(x15+1)。先將(x15+1)分解因式，使各因式為既約多項式，再尋找f(x)。l其中4次既約多項式有

14、3個，但（x4+x3+x2+x+1）能整除（x5+1），故它不是本原多項式，因此找到兩個4次本原多項式。（x4+x+1）和（x4+x3+1）。由其中任何一個都可以產(chǎn)生m序列。l用f(x)=（x4+x+1）構(gòu)成的m序列產(chǎn)生器如圖7-7所示。 l設(shè)4級移位寄存器的初始狀態(tài)為0001。C4=c1=c0=1，c3=c2=0。輸出序列ak的周期長度為15。l如表7-6所示的輸出序列。 l第3級和第4級的模二和的運算結(jié)果反饋到第1級。初始狀態(tài)下，除了第3級為1外，其他3級均為0。隨著移位時鐘節(jié)拍，各級移位寄存器的狀態(tài)發(fā)生轉(zhuǎn)移，在第15節(jié)拍時，移位寄存器的狀態(tài)與第0拍的狀態(tài)（初始狀態(tài)）相同，因此，從第16節(jié)

15、拍開始必定重復(fù)第115節(jié)拍的過程。表明了移位寄存器具有周期性，其周期長度為15。l輸出序列：la4=000100110101111l對于n=4的移位寄存器共有24=16種不同狀態(tài)。上述序列中出現(xiàn)了除全0以外狀態(tài)的所有狀態(tài)，因此是可能得到的最長周期序列。只要移位寄存器的初始狀態(tài)不是全0，就能得到周期長度為15的序列。其實，從任何一級寄存器所得到的序列都是周期為15的序列，只不過節(jié)拍不同而已，這些都是最長線性反饋移位寄存器序列。 lM序列的周期數(shù)總是奇數(shù)。lm序列每一周期中1的個數(shù)比0的個數(shù)多1個。由于p=2n-1為奇數(shù)，因而在每一周期中1的個數(shù)為(p+1)/2=2n-1為偶數(shù)，而0的個數(shù)為(p-

16、1)/2=2n-1-1為奇數(shù)。上例中p=15，1的個數(shù)為8，0的個數(shù)為7。當(dāng)p足夠大時，在一個周期中1與0出現(xiàn)的次數(shù)基本相等。l這就是m序列的一個最重要的特性-均衡性。 lm序列在通信領(lǐng)域有廣泛的應(yīng)用，它可以用在擴(kuò)頻通信、衛(wèi)星通信的碼分多址，數(shù)字?jǐn)?shù)據(jù)通信中的加密、加擾、同步、誤碼率測量等領(lǐng)域中。l1擴(kuò)展頻譜通信l擴(kuò)頻通信是將待傳送的基帶信號在頻域上擴(kuò)展到很寬的頻帶，遠(yuǎn)遠(yuǎn)大于原來的信號帶寬；在接收端再把已擴(kuò)展的信號變換到原來的頻帶上，恢復(fù)出原來的基帶信號。 l擴(kuò)展頻譜技術(shù)的理論基礎(chǔ)是山農(nóng)公式。對于加性白高斯噪聲的連續(xù)信道，其信道容量C與信道傳輸帶寬B及信噪比S/N之間的關(guān)系可以用下式表示l這個公

17、式表明，在保持信息傳輸速率不變的條件下，信噪比和帶寬之間具有互換關(guān)系。 2log1SCBNl（1）具有選擇地址能力；l（2）信號的功率譜密度很低，有利于信號的隱蔽；l（3）有利于加密，防止竊聽；l（4）抗干擾性強；l（5）抗衰落能力強；l（6）可以進(jìn)行高分辨率的測距。l擴(kuò)頻通信系統(tǒng)的工作方式有：直接序列擴(kuò)頻、跳變頻率擴(kuò)頻、跳變時間擴(kuò)頻和混合式擴(kuò)頻。以上3種工作方式是基本的工作方式，最常用的是直擴(kuò)方式和跳頻方式兩種。 l多址系統(tǒng)是指多個用戶通過一個共同的信道交換消息的通信系統(tǒng)。傳統(tǒng)的信號劃分方式有頻分復(fù)用和時分復(fù)用，相對應(yīng)有頻分多址系統(tǒng)和時分多址系統(tǒng)。l碼分多址系統(tǒng)是一種新的多址方式，它給每個用

18、戶分配一個多址碼，以次來區(qū)分不同的用戶。碼分多址擴(kuò)頻通信在移動通信網(wǎng)和衛(wèi)星通信網(wǎng)中有廣泛的應(yīng)用。l數(shù)字通信的一個重要優(yōu)點是容易做到加密，在這個方面m序列應(yīng)用很多。l數(shù)字加密的基本原理7-9所示。l將信源產(chǎn)生的二進(jìn)制數(shù)字序列和一個周期很長的m序列模2相加，這樣就將原消息變成了不可理解的另一種序列。這種加密的序列在信道中傳輸，被他人竊聽時不能理解其中的內(nèi)容，達(dá)到保密的目的。在接收端再加上同樣的m序列，就能還原信息。 信源發(fā)送信道接收用戶m序列產(chǎn)生器m序列產(chǎn)生器YYEX1EX1l設(shè)信源發(fā)送的序列為X1=1011010011，m序列Y=1100001011。模2加法運算得到序列E，E已經(jīng)不同與X1的意義。如果不知道m(xù)序列Y，就無法解出攜帶原始信息的數(shù)碼X1。假設(shè)信道傳輸中沒有產(chǎn)生誤碼，序列E達(dá)到接收端后與m序列Y再進(jìn)行模2加法運算，可恢復(fù)出原來信息X1，即lE Y=X1 Y Y=X1 1011010011110100001100011011101011010011原始信碼 X1m序列 Y加密輸出 E解密輸出