5.1信道編碼與差錯控制

5.2幾種簡單的差錯控制編碼

5.3線性分組碼

5.4循環碼

本章小結

思考與練習

第5章信道編碼技術5.1信道編碼與差錯控制在實際信道中傳輸數字信號時，由于信道傳輸特性不理想及加性噪聲的影響，接收端收到的數字信號不可避免地會發生錯誤。為了在已知信噪比的情況下達到一定的比特誤碼率指標，首先應該合理設計基帶信號，選擇調制解調方式，采用時域、頻域均衡，使比特誤碼率盡可能降低。但實際上，許多通信系統中的比特誤碼率并不能滿足實際需要，此時則必須采用信道編碼，才能將比特誤碼率進一步降低，以滿足系統指標要求。5.1.1信道編碼的基本概念為提高整個系統的抗干擾能力，一般需要在載波調制之前對數字基帶信號進行信道編碼。信道編碼也稱為差錯控制編碼或糾錯編碼，指用編碼和譯碼的方法去控制數字通信系統的信息比特差錯概率的大小，以便達到設計指標。它是提高數字信息傳輸可靠性的有效方法之一。5.1.2差錯控制編碼的基本思想差錯控制編碼的基本實現方法是在發送端給被傳輸的信息附上一些監督碼元，這些多余的碼元與信息碼元之間以某種確定的規則相互關聯。在接收端按照既定的規則校驗信息碼元與監督碼元之間的關系，一旦傳輸發生錯誤，則信息碼元與監督碼元的關系就受到破壞，從而使接收端可以發現錯誤，進而糾正錯誤。因此，各種編碼和譯碼方法是差錯控制編碼所要研究的問題。5.1.3差錯控制方式對于不同類型的信道，應采用不同的差錯控制技術。常用的差錯控制方式主要有以下3種，如圖5-1所示。圖5-13種差錯控制方式比較

1.前向糾錯(FEC)前向糾錯即自動糾錯，發送端發送能糾正錯誤的編碼，在接收端根據接收到的碼和編碼規則，能自動糾正傳輸中的錯誤。前向糾錯方式不需要反饋通道，特別適合只能提供單向信道的場合，特點是時延小，實時性好，但傳輸效率低，譯碼設備復雜。

2.檢錯重發(ARQ)檢錯重發又稱為自動反饋重發(AutomaticRepeatreQequest)。發送端采用某種能夠檢查出錯誤的碼，在接收端根據編碼規律校驗有無錯碼，如果發生了錯誤，則要求發送端重發。發送端根據接收端的要求，將包含錯誤的部分信號重發，從而達到糾正錯誤的目的。如重發后仍有錯碼，則再次重發，直至檢不出錯碼為止。檢錯重發的優點主要表現在:

(1)只需要少量的冗余碼,就可以得到極低的輸出誤碼率;

(2)有一定的自適應能力。檢錯重發的不足之處主要表現在：

(1)需要反向信道，故不能用于單向傳輸系統，并且實現重發控制比較復雜；

(2)通信效率低，不適合嚴格的實時傳輸系統。目前，這種方法在實際通信中應用最為普遍。定比碼是指每個碼字中均含有相同數目的“1”(碼字長一定，“1”的數目一定后，所含“0”的數目也就必然相同)，它是一種檢錯碼。國際無線電通信中采用的是7中取3定比碼，碼字長為7位，規定總有3個“1”。在計算機通信網中也常采用ARQ技術。

3.混合糾錯(HEC)混合糾錯就是前向糾錯和檢錯重發技術的結合，發送端發送糾錯碼，在接收端經校驗，如果錯碼較少且在糾錯能力之內，則譯碼器自動糾錯。如果錯碼較多，已超過糾錯能力，此時自動發出信號，通過反向信道控制發送端重發。混合糾錯具有前向糾錯和自動反饋重發的特點，需要反向信道和復雜的設備，但它能更好地發揮檢錯和糾錯能力，在較差的信道中也能獲得較低的誤碼率。5.1.4差錯控制編碼的分類差錯控制編碼的分類很多，通常按以下方式對其進行分類。

(1)按照差錯控制編碼功能的不同，可將差錯控制編碼分為檢錯碼、糾錯碼和糾刪碼。檢錯碼僅能檢測誤碼；糾錯碼僅可糾正誤碼；糾刪碼則兼有糾錯和檢錯能力，當發現不可糾正的錯誤時，可以發出錯誤信息指示或者簡單地刪除出現的、不可糾正的錯誤信息段落。

(2)按照信息碼元與附加的監督碼元之間的檢驗關系，可將差錯控制編碼分為線性碼與非線性碼。若監督碼元與信息碼元之間的關系為線性關系，即滿足一組線性方程式，則稱為線性碼；否則，稱為非線性碼。

(3)按照信息碼元和監督碼元之間約束方式的不同，可將差錯控制編碼分為分組碼與卷積碼兩類。在分組碼中，編碼后的碼元序列每n位分為一組，其中包括k個信息碼元和r個附加的監督碼元，即n=k+r。每組的監督碼元僅與本組的信息碼元有關，而與其它碼組的信息碼元無關。卷積碼則不同，雖然編碼后也劃分為碼組，但監督碼元不僅與本組信息碼元有關，而且還和其它碼組的信息碼元有關。

(4)按照信息碼元在編碼后是否保持原來的形式，可將差錯控制編碼分為系統碼和非系統碼。

(5)按照糾正錯誤類型的不同，可將差錯控制編碼分為糾正隨機錯誤碼和糾正突發錯誤碼。隨著數字通信系統的發展，可以將信道編碼器和調制器統一起來綜合設計，這就是所謂的網格編碼調制。5.2幾種簡單的差錯控制編碼下面介紹幾種簡單的差錯控制編碼，這些碼編碼簡單，易于實現，檢錯能力又較強，在實際中應用比較廣泛。我們首先來了解幾個重要的概念。5.2.1碼長、碼重與碼距

(1)碼長:碼字中碼元的數目。

(2)碼重:碼字中非0數字的數目，一般用W表示。

(3)碼距:兩個等長碼字之間對應位不同的數目，有時也稱為這兩個碼字的漢明(Hamming)距離，簡稱碼距，用d表示。例如:碼字10010101和碼字10111101，其碼距為d=2。

(4)最小碼距:在碼字集合中全體碼字之間距離的最小數值。糾錯碼的抗干擾能力完全取決于許用碼字之間的距離，碼的最小距離越大，說明碼字間的最小差別越大，抗干擾能力就越強。5.2.2糾/檢錯能力與最小碼距的關系在編碼的碼組集合中，任何兩個可用碼組之間距離的最小值稱為最小碼距dmin。dmin越大，說明兩個碼字之間的差別越大，檢錯和糾錯能力也就越強。最小碼距是信道編碼的一個重要參數，它直接與編碼的檢錯和糾錯能力相關。一般情況下，對于分組碼有以下結論。

(1)要檢測e個錯碼，最小距離應滿足dmin≥e+1

(5-1)由圖5-2可知，若c1中發生了e個錯誤變為

,則d(c1，)=e，設e=d－1，則d(，c2)=1，故≠c2，因此譯碼器不會錯判為c2，檢測到e=d－1個錯誤。

(2)為糾正t個錯誤，最小距離應滿足dmin≥2t+1

(5-2)由圖5-3可知，若c1與c2是(n，k)碼中任兩個碼字距離的最小者，且為2t+1，則發生t個錯誤以后變成，它們之間的距離d(c1，)=t，但d(，c2)=t+1。d(，c2)>d(c1，),所以譯碼器可根據它們之間距離的大小來正確譯碼，從而能糾正t個錯誤。

(3)為糾正t個錯誤，同時又能夠檢測e個錯誤，最小碼距應滿足dmin≥t+e+1(e>t)

(5-3)圖5-2糾錯碼糾錯能力圖示一圖5-3糾錯碼糾錯能力圖示二5.2.3奇偶監督碼奇偶監督碼(又稱為奇偶校驗碼)是一種最簡單的檢錯碼，它的基本思想是在n－1位信息碼元后面附加一位監督碼元，構成(n，n－1)的分組碼，監督碼元的作用是使碼長為n的碼組中“1”的個數保持為奇數或偶數。碼組中“1”的個數保持為奇數的編碼稱為奇數監督碼，保持為偶數的編碼稱為偶數監督碼。

一般情況下，奇偶監督碼的編碼規則是首先將要發送的二進制信息分組，然后對所有信息碼元和監督碼元進行模2加，選擇正確的監督碼元，以保證模2加的結果為0(偶校驗)或1(奇校驗)。假設要傳送的信息碼元為n－1位，即an－1，an－2，…，a2，a1。在偶數監督碼中，就是要使碼組中“1”的數目為偶數，即滿足下式:an－1⊕an－2⊕…⊕a0=0

(5-4)式中，⊕表示模2加，a0為監督位，其它為信息位。這種碼能夠檢測奇數個錯碼。在接收端將碼組中各碼元模2加，若結果為“1”，就說明存在錯碼，若為“0”，就認為無錯。奇數監督碼與其相似，只不過其碼組中“1”的數目為奇數，即滿足an－1⊕an－2⊕…⊕a0=1

(5-5)

奇偶監督碼最小碼距為2，無論是奇校驗還是偶校驗，都只能檢測出單個或奇數個錯誤，而不能檢測出偶數個錯誤，因此檢錯能力低，但編碼效率隨著n的增加而提高。5.2.4水平奇偶監督碼水平奇偶監督碼是奇偶監督碼的一種改進形式，該編碼方式是將信息按奇(偶)監督規則進行編碼，然后將信息以每個碼組一行排成一個陣列，在發送端按列的順序發送，在接收端也以列的順序排成方陣，然后進行奇(偶)校驗，所以稱之為水平奇偶校驗。如表5-1所示的例子采用的是偶校驗。發送時，該碼以列的形式，即1100110、0010011、0001111、1100000、0111101、0010011、0110100的形式發送，而在接收端將所接收的信號以列的形式排列，可得表5-1所示的陣列。5.2.5水平垂直奇偶監督碼水平垂直奇偶監督碼是在水平奇偶監督碼的基礎上提出的一種改進形式，它不僅對每一行進行奇偶校驗，同時對每一列也進行奇偶校驗。如表5-2所示的例子采用的是偶校驗。發送時，該碼是按11001100、00100111、00011110、11000000、01111011、00100111、01101001的順序發送，而在接收端將所接收的信號以列的形式排列，可得表5-2所示的陣列。水平垂直奇偶監督碼不僅能檢測每一行以及每一列的奇數個錯誤，還能發現長度不大于行數或列數的突發錯誤。5.2.6群計數碼群計數碼是將信息碼元分組之后，計算出每個信息碼組中“1”的數目，然后將這個數目用二進制表示，并作為監督碼元附加在信息碼元后面一起傳輸。例如:01100100共有3個“1”，用二進制011表示十進制的3，故傳輸碼組變為01100100011。群計數碼的檢錯能力很強，除了“1”變“0”和“0”變“1”的錯誤成對出現之外，能檢測出所有形式的錯誤。5.3線性分組碼5.3.1線性分組碼的定義與性質前面介紹的奇偶監督碼，其編碼原理利用了代數關系式。這種建立在代數基礎上的編碼稱為代數碼。線性分組碼是最常見的代數碼，這種碼每組碼元共有n位，包括k個信息碼元和r=n－k個監督碼元，其中，(n－k)個監督碼元是由信息碼元的線性運算產生的。就是說，通過預定的線性運算將長為k位的信息碼組變換成n(n>k)重的碼字，這樣形成的碼為分組碼。如直接將(n－k)位附加碼元附加在信息位后面所構成的分組碼稱為系統分組碼，簡稱系統碼。設待傳信息位數為k，即M=(m1，m2，…，mk)，編碼后的碼字C=(c1，c2，…，cn)，n>k。如果這種變換所依據的規則為下列一組函數關系式:(5-6)且函數f1，f2，…，fn都是線性函數，則由此所編出的碼為線性分組碼，否則為非線性碼。一般情況下，我們用符號(n，k)來表示線性分組碼，其中，n表示編碼后碼組的總長度，k表示該線性分組碼的信息碼元的個數，監督碼元個數為n－k個，所以線性分組碼的編碼效率為(5-7)

編碼效率或編碼速率也簡稱為碼率，它表明了信道利用效率，所以也叫做傳信率。η是衡量碼性能的一個重要參數。η越大，碼的效率或傳信率越高。由線性分組碼的定義可知，不同的線性分組碼對應著不同的線性方程組，也就是說，對于每一線性分組碼，將有唯一的生成矩陣和監督矩陣。為了解釋生成矩陣和監督矩陣，下面我們以一具體例子來說明。例5-1設n=7，k=4，碼字按下面的線性關系進行編碼：c1=m1c2=m2c3=m3c4=m4c5=m1+m3+m4c6=m1+m2+m3c7=m2+m3+m4

解將其寫成矩陣形式為令則C=MG

編碼后的碼字如表5-3所示。同時由上述線性關系，還可得：即

將上式寫成矩陣形式為令則HCT=0

通過本例我們可以看出，由式C=MG或者HCT=0就可以確定碼字，于是稱矩陣G為生成矩陣，稱矩陣H為監督矩陣。線性分組碼還具有以下一些性質:

(1)碼字集中碼元之間的任意線性組合仍是合法碼字，即碼字集對線性組合運算具有封閉性。

(2)碼的最小距離等于非零碼的最小碼重。5.3.2幾種典型的線性分組碼

1.漢明碼漢明碼是美國科學家Hamming于1950年提出來的，是一種高效的能糾單個錯誤的線性分組碼。其高效性體現在其糾單個錯誤時，所用的監督碼元最少，與其它碼長相同的能糾單個錯誤的碼相比，編碼效率最高，被廣泛用于數字通信和數據存儲系統中。漢明碼(n，k)的參數如下：

(1)監督碼元數目：r=n－k，r是不小于3的任意正整數(因為要糾t位錯誤，所以dmin>2t+1)；

(2)碼長:n=2r－1；

(3)信息碼元數目：k=2r－1－r；

(4)最小距離：dmin=3；

(5)糾錯能力：t=1。

2.BCH碼

BCH碼是一種非常重要的循環碼，它解決了生成多項式與最小碼距之間的關系，是線性分組碼中應用最為普遍的一類碼。在定義BCH碼之前，首先要了解本原多項式。如果一個m次多項式f(x)滿足以下3個條件:

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

(2)f(x)可以整除xn+1，其中n=2m－1；

(3)

q<n，f(x)不能整除xq+1。則稱f(x)是一個最高次數為m的本原多項式。

BCH碼可分為本原BCH碼和非本原BCH碼兩類。它們的主要區別在于本原BCH碼的生成多項式g(x)中含有最高次數為m的本原多項式，而且碼長n=2m－1；非本原BCH碼的生成多項式g(x)中不含有這種本原多項式，而且碼長n是2m－1的一個因子，即n一定能整除2m－1。

BCH碼長n、監督碼元數目r和糾錯能力t之間的關系如下:對于任意整數m和t≤m/2，必定存在一個碼長為n=2m－1、監督位數r=n－k≤mt，并能糾正所有不大于t個錯誤的BCH碼。

3.最大長度碼最大長度碼也稱為m序列，是漢明碼的對偶碼，即以漢明碼的校驗矩陣作為生成矩陣的碼。其碼長為n=2m－1，信息碼元數目為m，最小距離dmin=2m－1。最大長度碼也稱為偽隨機或偽噪聲碼，在擴頻通信和衛星通信中都有廣泛的應用。5.4循環碼5.4.1循環碼的定義與性質從上一節的例5-1的編碼中可以看出，由生成矩陣得到的碼字為1000110、0100011、1010001、1101000、0110100、0011010、0001101、1001011、1100101、1110010、0111001、1011100、0101110、0010111、1111111、0000000，這些碼字不論經過怎樣的循環移位，移位后碼字仍然是這些碼字中的內容，我們把具有這種特性的線性分組碼叫做循環碼。循環碼是線性分組碼的一個重要子集，是線性分組碼中最主要、最有用的一類，也是目前研究得最成熟的一類碼。循環碼具有嚴謹的代數結構和許多特殊的代數性質，這些性質有助于按所要求的糾錯能力系統地構造循環碼，且易于實現；同時循環碼的性能也較好，具有較強的檢錯和糾錯能力；編譯電路簡單，易于實現。循環碼最引人注目的兩個特點是:

(1)循環封閉性，即循環碼經過循環移位后仍為循環碼組中的許用碼字。

(2)用反饋線性移位寄存器可很容易地實現其編碼和伴隨式計算。5.4.2循環碼的編碼原理循環碼的主要優點之一是其編碼過程很容易用移位寄存器來實現。由于生成多項式g(x)可以惟一地確定循環碼，因此編碼方法可基于生成多項式g(x)。下面將給出一種基于g(x)的編碼方案。首先根據給定循環碼的參數確定生成多項式g(x)，也就是從xn+1的因子中選一個(n－k)次多項式作為g(x)；然后利用循環碼的編碼特點，即所有循環碼多項式C(x)都可以被g(x)整除的特點，來定義生成多項式g(x)。設要產生(n，k)系統循環碼，m(x)表示信息多項式，則其次數必小于k。其編碼主要按照以下三步進行:

(1)用xn－k乘m(x)，實際上是給信息碼后附加上(n－k)個“0”。例如，信息碼為110，信息多項式m(x)=x2+x。當n－k＝7－3＝4時，xn－km(x)=x6+x5，相當于1100000。

(2)除以g(x)，可得余數r(x)。

(3)r(x)加到信息位后作為監督位，就得到了系統循環碼多項式C(x)=xn－km(x)+r(x)。例5-2(7，4)循環碼的生成多項式g(x)=x3+x+1，信息碼m=［1010］，系統碼碼字多項式C(x)為多少?解：由于m=［1010］，因此m(x)=x3+x(5-8)xn－km(x)=x6+x4

(5-9)所以C(x)=xn－km(x)+r(x)=x6+x4+x+1

(5-10)編碼后的碼字為c=［1010011］。在實際中，對于以上三步的實現通常采用一個除法電路來完成，該電路是根據生成多項式做出的一個(n－k)級帶反饋的線性移位寄存器。在此我們以例5-1的(7，4)循環碼為例，其編碼電路如圖5-4所示。圖5-4(7，4)循環碼的編碼電路循環碼的工作過程如下:

(1)首先將3級寄存器清零，門1開，門2關，將信息碼元m=［1010］依次輸入電路，一方面由異或門輸出，另一方面送至生成多項式的除法電路，完成監督位的生成，同時m(x)從高端輸出，實現了xn－km(x)，即信息碼元的移位。

(2)經過4次移位后，m(x)已經輸出，同時寄存器生成了監督位r(x)。

(3)此時門1關，門2開。經過n－k＝7－4＝3次移位后輸出監督元。此時加上前面4位信息元就組成了一個7位的碼字。

(4)將3級寄存器清零，門1開，門2關，對第二個碼字進行編碼。5.4.3循環碼的譯碼對(n，k)循環碼，設發送碼字C(x)=cn－1xn－1+cn－2xn－2+…+c1x+c0，通過譯碼后接收碼字為R(x)=rn－1xn－1+rn－2xn－2+…+r1x+r0。考慮到信道干擾，接收碼字存在一定的錯誤，設錯誤圖樣為E(x)=en－1xn－1+en－2xn－2+…+e1x+e0，則R(x)=C(x)+E(x)。于是譯碼的主要任務就是如何從R(x)中正確地估計出C(x)，以此得到信息碼元m(x)。由于循環碼是線性碼的一種特殊情況，因此其譯碼同線性分組碼一樣，可分為以下三步進行:

(1)由接收碼字R(x)計算伴隨式S(x)；

(2)根據伴隨式S(x)確定錯誤圖樣E(x)；

(3)R(x)－E(x)=，得到譯碼器輸出的估計碼字，并送出譯碼器給用戶，檢測是否正確。上述第(1)步運算和檢錯譯碼類似，也就是求解R(x)整除g(x)的余式，即s(x)=R(x)/g(x)≡E(x)modg(x)。當s(x)=0時，譯碼正確；反之，則譯碼有錯。同時由于生成多項式g(x)的次數為n－k，則必定不大于n－k，即伴隨式矢量［sn－k－1

sn－k－2…s1

s0］的2n－k個狀態與錯位相對應。下面我們以(7，4)循環碼為例，來說明循環碼的譯碼。對于(7，4)循環碼的生成多項式g(x)=x3+x+1，當不存在錯位，即譯碼正確時，E(x)=0,則s(x)=E(x)modg(x)=0，［s2

s1

s0］=［000］，接收碼字R(x)=C(x)。若E(x)中e0=1，則s(x)=E(x)modg(x)=1，［s2

s1

s0］=［001］，接收碼字中r0位有錯。若E(x)中e1=1，則s(x)=E(x)modg(x)=x，［s2

s1

s0］=［010］，接收碼字中r1位有錯。若E(x)中e2=1，則s(x)=E(x)modg(x)=x2，［s2

s1

s0］=［100］，接收碼字中r2位有錯。若E(x)中e3=1，則s(x)=E(x)modg(x)=x+1，［s2

s1

s0］=［011］，接收碼字中r3位有錯。若E(x)中e4=1，則s(x)=E(x)modg(x)=x2+x，［s2

s1

s0］=［110］，接收碼字中r4位有錯。若E(x)中e5=1，則s(x)=E(x)modg(x)=x2+x+1，［s2

s1

s0］=［111］，接收碼字中r5位有錯。若E(x)中e6=1，則s(x)=E(x)modg(x)=x2+1，［s2

s1

s0］=［101］，接收碼字中r6位有錯。用表格表示見表5-4。從上面的譯碼可以看出，錯誤圖樣、伴隨式s(x)與錯位是一一對應的。在循環碼的譯碼方法中，基于錯誤圖樣識別的譯碼器稱為梅吉特譯碼器，其錯誤圖樣識別器是一個具有(n－k)個輸入端的邏輯電路，原則上可