第7章差錯控制編碼和m序列第一頁，共51頁。7.1概

述

差錯控制編碼，又稱為信道編碼、可靠性編碼、抗干擾編碼或糾錯碼，它是提高數字信號可靠性的有效方法之一。它產生于20世紀50年代初，發展到70年代趨向成熟。第二頁，共51頁。7.1.1信道編碼在數字通信中，根據不同的目的，編碼可分為信源編碼和信道編碼。信源編碼是為了提高數字信號的有效性以及為了使模擬信號數字化而采取的編碼。信道編碼是為了降低誤碼率，提高數字通信的可靠性而采取的編碼。為了提高系統的抗干擾性能，可以加大發射功率，降低接收設備本身的噪聲，以及合理選擇調制、解調方法等。此外，還可以采用信道編碼技術。第三頁，共51頁。7.1.2差錯控制方式常用的差錯控制方式有3種：檢錯重發、前向糾錯和混合糾錯，第四頁，共51頁。圖7-1差錯控制方式第五頁，共51頁。1．檢錯重發方式檢錯重發又稱自動請求重傳方式，記作ARQ（AutomaticRepeatRequest）。如果發現錯誤，則通過反向信道把這一判決結果反饋給發端，然后，發端把收端認為錯誤的信息再次重發，從而達到正確傳輸的目的。其特點是需要反饋信道，譯碼設備簡單，對突發錯誤和信道干擾較嚴重時有效，但實時性差，主要在計算機數據通信中得到應用。第六頁，共51頁。2．前向糾錯方式前向糾錯方式記作FEC（ForwardErrorCorrection）。發端發送能夠糾正錯誤的碼，收端收到信碼后自動地糾正傳輸中的錯誤。其特點是單向傳輸，實時性好，但譯碼設備較復雜。第七頁，共51頁。3．混合糾錯方式混合糾錯方式記作HEC（HybridErrorCorrection）是FEC和ARQ方式的結合。發端發送具有自動糾錯同時又具有檢錯能力的碼。收端收到碼后，檢查差錯情況，如果錯誤在碼的糾錯能力范圍以內，則自動糾錯，如果超過了碼的糾錯能力，但能檢測出來，則經過反饋信道請求發端重發。這種方式具有自動糾錯和檢錯重發的優點，可達到較低的誤碼率。第八頁，共51頁。7.1.3糾錯碼的分類（1）根據糾錯碼各碼組信息元和監督元的函數關系，可分為線性碼和非線性碼。如果函數關系是線性的，即滿足一組線性方程式，則稱為線性碼，否則為非線性碼。（2）根據上述關系涉及的范圍，可分為分組碼和卷積碼。分組碼的各碼元僅與本組的信息元有關；卷積碼中的碼元不僅與本組的信息元有關，而且還與前面若干組的信息元有關。（3）根據碼的用途，可分為檢錯碼和糾錯碼。檢錯碼以檢錯為目的，不一定能糾錯；而糾錯碼以糾錯為目的，一定能檢錯。第九頁，共51頁。7.1.4糾錯編碼的基本原理1．分組碼分組碼一般可用(n，k)表示。簡單地說，分組碼是對每段k位長的信息組以一定的規則增加r個監督元，組成長為n的碼字。在二進制情況下，共有2k個不同的信息組，相應地可得到2k個不同的碼字，稱為許用碼組。其余2n-2k個碼字未被選用，稱為禁用碼組。第十頁，共51頁。碼重和碼距在分組碼中，非零碼元的數目稱為碼字的漢明重量，簡稱碼重。例如，碼字10110，碼重w=3。兩個等長碼組之間相應位取值不同的數目稱為這兩個碼組的漢明（Hamming）距離，簡稱碼距。例如110000與10011之間的距離d=3。碼組集中任意兩個碼字之間距離的最小值稱為碼的最小距離，用d0表示。最小碼距是碼的一個重要參數，它是衡量碼檢錯、糾錯能力的依據。第十一頁，共51頁。2．檢錯和糾錯能力若分組碼碼字中的監督元在信息元之后，而且是信息元的簡單重復，則稱該分組碼為重復碼。它是一種簡單實用的檢錯碼，并有一定的糾錯能力。例如（2，1）重復碼，兩個許用碼組是00與11，d0=2，收端譯碼，出現01、10禁用碼組時，可以發現傳輸中的一位錯誤。如果是（3，1）重復碼，兩個許用碼組是000與111，d0=3；當收端出現兩個或三個1時，判為1，否則判為0。此時，可以糾正單個錯誤，或者該碼可以檢出兩個錯誤。第十二頁，共51頁。碼的最小距離d0直接關系著碼的檢錯和糾錯能力；任一(n，k)分組碼，若要在碼字內：（1）檢測e個隨機錯誤，則要求碼的最小距離d0≥e+1；（2）糾正t個隨機錯誤，則要求碼的最小距離d0≥2t+1；（3）糾正t個同時檢測e(≥t)個隨機錯誤，則要求碼的最小距離d0≥t+e+1。第十三頁，共51頁。3．編碼效率用差錯控制編碼提高通信系統的可靠性，是以降低有效性為代價換來的。我們定義編碼效率R來衡量有效性：R=k/n其中，k是信息元的個數，n為碼長。對糾錯碼的基本要求是：檢錯和糾錯能力盡量強；編碼效率盡量高；編碼規律盡量簡單。際中要根據具體指標要求，保證有一定糾、檢錯能力和編碼效率，并且易于實現。第十四頁，共51頁。7.2常用的幾種編碼技術碼

1．奇偶監督碼奇偶監督碼是在原信息碼后面附加一個監督元，使得碼組中“1”的個數是奇數或偶數。或者說，它是含一個監督元，碼重為奇數或偶數的(n，n-1)系統分組碼。奇偶監督碼又分為奇監督碼和偶監督碼。第十五頁，共51頁。2．行列監督碼

第十六頁，共51頁。3．恒比碼

碼字中1的數目與0的數目保持恒定比例的碼稱為恒比碼。由于恒比碼中，每個碼組均含有相同數目的1和0，因此恒比碼又稱等重碼，定1碼。這種碼在檢測時，只要計算接收碼元中1的數目是否正確，就知道有無錯誤。第十七頁，共51頁。我國郵電部門電傳機傳輸漢字通信中普遍采用3:2碼，又稱“5中取3”的恒比碼，這是5單位數字保護電報碼。我國每個漢字用4位阿拉伯數字表示，每個阿拉伯數字用5個比特的碼字表示。由于阿拉伯數字只有10個，因此從32中可能的碼字中挑出=10個1的個數為3個的碼字作為阿拉伯數字的編碼方式。第十八頁，共51頁。7.2.2線性分組碼現以（7，4）分組碼為例來說明線性分組碼的特點。設其碼字為A=［a7a5a4a3a2a1a0］，其中前4位是信息元，后3位是監督元，可用下列線性方程組來描述該分組碼，產生監督元。第十九頁，共51頁。7.2.3循環碼循環碼除了具有線性碼的一般性質外，具有許多特殊的代數性質，如還具有循環性、并且簡化譯碼算法，目前發現的大部分線性碼與循環碼有密切關系。循環碼還有易于實現的特點，很容易用帶反饋的移位寄存器實現其硬件。由于循環碼具有碼的代數結構清晰、性能較好、編譯碼簡單和易于實現的特點，因此在目前的計算機糾錯系統中所使用的線性分組碼幾乎都是循環碼。它不僅可以用于糾正獨立的隨機錯誤，而且也可以用于糾正突發錯誤。第二十頁，共51頁。在代數理論中，為了便于計算，常用碼多項式表示碼字。(n，k)循環碼的碼字，其碼多項式（以降冪順序排列）為A(x)=an-1xn-1+an-2xn-2+a1x+a0第二十一頁，共51頁。表7-3（7，3）循環碼

第二十二頁，共51頁。1．生成多項式如果一種碼的所有碼多項式都是多項式g(x)的倍式，則稱g(x)為該碼的生成多項式。在(n，k)循環碼中任意碼多項式A(x)都是最低次碼多項式的倍式。如表7-3的（7，3）循環碼中，g(x)=A1(x)=x4+x3+x2+1其他碼多項式都是g(x)的倍式，即A0(x)=0*g(x)A2(x)=(x+1)*g(x)A3(x)=x*g(x)…A7(x)=x2*g(x)第二十三頁，共51頁。2．監督多項式為了便于對循環碼編譯碼，通常還定義監督多項式，令第二十四頁，共51頁。3．編碼方法和電路在編碼時，首先要根據給定的(n，k)值選定生成多項式g(x)，即應在xn+1的因式中選一r=n-k次多項式作為g(x)。設編碼前的信息多項式m(x)為：循環碼的碼多項式可表示為A(x)=xr*m(x)+R(x)第二十五頁，共51頁。圖7-3（7，3）循環碼編碼電路

第二十六頁，共51頁。表7-4（7，3）循環碼的編碼過程

第二十七頁，共51頁。圖7-4（7，3）循環碼譯碼電路第二十八頁，共51頁。7.2.4卷積碼1．基本概念卷積碼又稱為連環碼，是1955年提出來的一種糾錯碼，它和分組碼有明顯的區別。（n，K）線性分組碼中，本組r=n-k個監督元有關，與其他各組無關，也就是說分組碼編碼器本身并無記憶性。卷積碼則不同，每個（n，k）碼段（也稱為子碼，通常較短）內的n個碼元不僅與該碼段內的信息元有關，而且與前面m段的信息元有關。通常稱m為編碼存儲。卷積碼通常用符號（n，m，k）表示。第二十九頁，共51頁。圖7-5卷積碼（2，1，2）編碼器

第三十頁，共51頁。輸出碼字C由下式確定C1=S1⊕S2⊕S3C2=S1⊕S3第三十一頁，共51頁。2．卷積碼的描述和譯碼方法卷積碼常用的描述方法有矩陣法、圖解法。矩陣法太復雜，圖解法直觀。常用的圖解法有3中：樹圖、狀態圖和格圖。卷積碼的譯碼方法有代數譯碼法和概率譯碼法。前者是利用生成多項式來譯碼，最大的方法是大數邏輯譯碼。后者又有兩種方法：維特比譯碼和序列譯碼。目前，概率譯碼已成為卷積譯碼的最主要的方法。第三十二頁，共51頁。7.3m

序列m序列又叫作偽隨機序列、偽噪聲（PN）碼或偽隨機碼。可以預先確定并且可以重復實現的序列稱為確定序列。既不能預先確定又不能重復實現的序列稱為隨機序列。具有隨機特性，貌似隨機序列的確定序列稱為偽隨機序列。M序列是目前廣泛使用的一種偽隨機序列。第三十三頁，共51頁。7.3.1m序列的產生1．線性反饋移位寄存器m序列是由帶線性反饋的移位寄存器產生的周期最長的一種二進制序列。線性反饋移位寄存器的一般結構如圖7-6所示。它由n級移位寄存器、若干模二加法器組成線性反饋邏輯網絡和時鐘脈沖產生器（省略未畫出來）連接而成。圖中移位寄存器的狀態用ai表示(i=0，1，…，n-1)，ci表示移位寄存器反饋線的連接狀態，相當于反饋系數，ci=1表示此線接通，參與反饋邏輯運算，ci=0表示此線斷開，不參與運算，c0=cn=1。第三十四頁，共51頁。圖7-6線性反饋移位寄存器

第三十五頁，共51頁。2．m序列產生器用4級線性反饋移位寄存器產生的m序列，其周期為p=24-1=15，其特征多項式f(x)是4次本原多項式，能整除(x15+1)。先將(x15+1)分解因式，使各因式為既約多項式，再尋找f(x)。其中4次既約多項式有3個，但（x4+x3+x2+x+1）能整除（x5+1），故它不是本原多項式，因此找到兩個4次本原多項式。（x4+x+1）和（x4+x3+1）。由其中任何一個都可以產生m序列。用f(x)=（x4+x+1）構成的m序列產生器如圖7-7所示。第三十六頁，共51頁。設4級移位寄存器的初始狀態為0001。C4=c1=c0=1，c3=c2=0。輸出序列{ak}的周期長度為15。如表7-6所示的輸出序列。第三十七頁，共51頁。表7-6{ak}輸出序列

第三十八頁，共51頁。第3級和第4級的模二和的運算結果反饋到第1級。初始狀態下，除了第3級為1外，其他3級均為0。隨著移位時鐘節拍，各級移位寄存器的狀態發生轉移，在第15節拍時，移位寄存器的狀態與第0拍的狀態（初始狀態）相同，因此，從第16節拍開始必定重復第1～15節拍的過程。表明了移位寄存器具有周期性，其周期長度為15。輸出序列：a4=1111第三十九頁，共51頁。對于n=4的移位寄存器共有24=16種不同狀態。上述序列中出現了除全0以外狀態的所有狀態，因此是可能得到的最長周期序列。只要移位寄存器的初始狀態不是全0，就能得到周期長度為15的序列。其實，從任何一級寄存器所得到的序列都是周期為15的序列，只不過節拍不同而已，這些都是最長線性反饋移位寄存器序列。第四十頁，共51頁。7.3.2m序列的性質M序列的周期數總是奇數。m序列每一周期中1的個數比0的個數多1個。由于p=2n-1為奇數，因而在每一周期中1的個數為(p+1)/2=2n-1為偶數，而0的個數為(p-1)/2=2n-1-1為奇數。上例中p=15，1的個數為8，0的個數為7。當p足夠大時，在一個周期中1與0出現的次數基本相等。這就是m序列的一個最重要的特性---均衡性。第四十一頁，共51頁。7.3.3m序列的應用m序列在通信領域有廣泛的應用，它可以用在擴頻通信、衛星通信的碼分多址，數字數據通信中的加密、加擾、同步、誤碼率測量等領域中。1．擴展頻譜通信擴頻通信是將待傳送的基帶信號在頻域上擴展到很寬的頻帶，遠遠大于原來的信號帶寬；在接收端再把已擴展的信號變換到原來的頻帶上，恢復出原來的基帶信號。第四十二頁，共51頁。擴展頻譜技術的理論基礎是山農公式。對于加性白高斯噪聲的連續信道，其信道容量C與信道傳輸帶寬B及信噪比S/N之間的關系可以用下式表示這個公式表明，在保持信息傳輸速率不變的條件下，信噪比和帶寬之間具有互換關系。第四十三頁，共51頁。擴頻系統有以下特點：（1）具有選擇地址能力；（2）信號的功率譜密度很低，有利于信號的隱蔽；（3）有利于加密，防止竊聽；（4）抗干擾性強；（5）抗衰落能力強；（6）可以進行高分辨率的測距。擴頻通信系統的工作方式有：直接序列擴頻、跳變頻率擴頻、跳變時間擴頻和混合式擴頻。以上3種工作方式是基本的工作方式，最常用的是直擴方式和跳頻方式兩種。第四十四頁，共51頁。2．碼分多址（CDMA）通信多址系統是指多個用戶通過一個共同的信道交換消息的通信系統。傳統的信號劃分方式有頻分復用和時分復用，相對應有頻分多址系統和時分多址系統。碼分多址系統是一種新的多址方式，它給每個用戶分配一個多址碼，以次來區