《數(shù)字通信原理》課件第9章

第9章信道編碼理論9.1概述9.2線性分組碼9.3循環(huán)碼9.4卷積碼9.5其他信道編碼技術(shù)9.1概述

9.1.1差錯控制方式

差錯控制的基本工作方式有四種：前向糾錯(FEC)、檢錯重發(fā)(ARQ)、混合糾錯(HEC)和反饋校驗(IF)，如圖9-1所

示，圖中有陰影的方框表示在該端可檢出錯誤。圖9-1差錯控制的工作方式(a)前向糾錯(FEC);(b)檢錯重發(fā)(ARQ);(c)混合糾錯(HEC);(d)信息反饋(IF)

1.前向糾錯方式

前向糾錯方式又稱自動糾錯，發(fā)端發(fā)送時能夠糾正錯誤的碼，收端收到信碼后自動地糾正傳輸中的錯誤。其特點是單向傳輸，實時性好，但譯碼設(shè)備較復(fù)雜。

2.檢錯重發(fā)方式

檢錯重發(fā)方式又稱自動請求重傳，發(fā)端送出能夠發(fā)現(xiàn)錯誤的碼，由收端判決傳輸中有或無錯誤產(chǎn)生。如果收端發(fā)現(xiàn)錯誤，那么通過反向信道把這一判決結(jié)果反饋給發(fā)端，然后發(fā)端把收端認為錯誤的信息再次重發(fā)，從而達到正確傳輸?shù)哪康?。其特點是需要反饋信道，譯碼設(shè)備簡單，對突發(fā)錯誤和信道干擾較嚴重時有效，但實時性差，主要應(yīng)用在計算機數(shù)據(jù)通信中。

3.混合糾錯方式

混合糾錯方式是FEC和ARQ方式的結(jié)合。發(fā)端發(fā)送具有自動檢錯和糾錯能力的碼，收端收到碼后，檢查差錯情況。如果出現(xiàn)的錯誤在碼的糾錯能力范圍以內(nèi)，那么自動糾錯；如果錯誤超過了碼的糾錯能力，就將其檢測出來，經(jīng)過反饋信道請求發(fā)端重發(fā)。這種方式具有FEC和ARQ的特點，能充分發(fā)揮碼的檢錯和糾錯性能，可達到較低的誤碼率，但需要反饋信道以及較復(fù)雜的譯碼設(shè)備和控制系統(tǒng)。

4.信息反饋方式

信息反饋方式又稱反饋檢驗，收端將接收的消息原封不動地送回發(fā)端，由發(fā)端將反饋信息和原發(fā)送信息進行比較，若發(fā)現(xiàn)錯誤則進行重發(fā)。其特點是方法和設(shè)備簡單，無需糾(檢)錯編譯系統(tǒng)，但是需要反饋信道，且傳輸效率低，實時性差。9.1.2信道編碼的分類

差錯控制編碼按照用途不同可分為檢錯碼、糾錯碼和糾刪碼。檢錯碼以檢錯為目的，不一定能糾錯；糾錯碼以糾錯為目的，一定能檢錯；而糾刪碼同時具有糾錯和檢錯能力，當發(fā)現(xiàn)不可糾正的錯誤時，發(fā)出錯誤指示并將其刪除。按照信息碼元和監(jiān)督碼元之間的函數(shù)關(guān)系可分為線性碼和非線性碼。如果函數(shù)關(guān)系是線性的，即滿足一組線性方程式，則稱為線性碼；反之稱為非線性碼。按照信息碼元和監(jiān)督碼元之間關(guān)系涉及的范圍可分為分組碼和卷積碼。分組碼的監(jiān)督碼元僅與本組的信息碼元有關(guān)；而卷積碼的監(jiān)督碼元不僅與本組的信息碼元有關(guān)，還與其前面若干組的信息碼元有關(guān)。卷積碼又稱連環(huán)碼。在線性分組碼中，把具有循環(huán)移位特性的碼稱為循環(huán)碼；否則稱為非循環(huán)碼。按照碼組中信息碼元在編碼的前、后是否相同可分為系統(tǒng)碼和非系統(tǒng)碼。如果編碼前、后的信息碼元保持不變則稱為系統(tǒng)碼或組織碼；反之稱為非系統(tǒng)碼或非組織碼。

按照糾(檢)錯誤的類型可分為糾(檢)隨機錯誤碼、糾(檢)突發(fā)錯誤碼和既能糾(檢)隨機錯誤同時又能糾(檢)突發(fā)錯誤碼。按照碼元取值的進制可分為二進制碼和多進制碼。9.1.3信道編碼的基本原理

1.碼長、碼重和碼距

編碼碼組(碼字)的碼元總位數(shù)稱為碼組的長度，簡稱碼長，用n表示。如“1011”的碼長n=4，“110011”的碼長n=6。碼組中非“0”位的數(shù)目稱為碼組的重量，簡稱碼重，用

W表示。對于二進制碼而言，碼重就是碼組中“1”碼元的數(shù)目，如“10110”的碼重W=3。兩個等長碼組之間對應(yīng)位上碼元不同的數(shù)目稱為這兩個碼組的距離，簡稱碼距，又稱漢明距離，用d表示。如“11000”與“11011”有兩個對應(yīng)位不同，故碼距d=2。碼組集合中任意

兩個碼字之間距離的最小值稱為最小碼距，用d0表示。由于兩個碼組模2相加，其不同的對應(yīng)位必為“1”，因此兩個碼組模2相加得到的新碼組的重量就是這兩個碼組之間的距離。

2.檢錯和糾錯能力

信道編碼的檢錯和糾錯能力是通過信息量的冗余度來換取的。為了便于理解，先通過一個例子來說明。假設(shè)要發(fā)送天氣預(yù)報消息，而且天氣只用兩種狀態(tài)表示：晴天和雨天。用一個二進制碼元編碼時，將晴天編為“1”，雨天編為“0”，最小碼距d0=1。在這種情況下，若傳輸中產(chǎn)生錯碼，即“1”錯為“0”或者“0”錯為“1”，收端將無法檢測到差錯。因此，當d0=1時，這種編碼沒有檢錯和糾錯能力。如果用兩個二進制碼元編碼，將晴天編為“11”，雨天編為“00”，最小碼距d0=2,那么在兩個二進制碼元的四種可能碼組中，“00”和“11”是許用碼組，“01”和“10”是禁用碼組。如果在傳輸過程中發(fā)生一位錯碼，即許用碼組變成禁用碼組，那么譯碼器就可判決為有錯，但由于不能判決是哪一位發(fā)生了錯碼，所以沒有糾錯能力。因此，當d0=2時，只能檢一位錯碼而不能糾錯。如果在信息碼元后附加兩位相同的監(jiān)督碼元，即晴天編為“111”，雨天編為“000”，最小碼距d0=3。那么在三位二元碼的八種可能碼組中，除去兩組許用碼組外，余下的六組：“001”、“010”、“011”、“100”、“101”、“110”均為禁用碼組。此時，如果傳輸中產(chǎn)生一位錯碼，那么收端將收到禁用碼組，可以判決傳輸有錯，而且還可以根據(jù)“大數(shù)判決法則”來譯碼，即碼組中出現(xiàn)2個或3個“1”時，譯為晴天；若碼組中出現(xiàn)2個或3個“0”時，則譯為雨天，此時可以糾正一位錯碼。如果傳輸中產(chǎn)生兩位錯碼，那么收端也將收到禁用碼組，此時譯碼器可檢兩位錯，但不具有糾錯能力。如果傳輸中產(chǎn)生三位錯碼，那么收端將收到許用碼組，這時其不再具有檢錯能力。因此，當d0=3時，信道編碼具有檢出兩位或兩位以下錯碼的能力，并具有糾正一位錯碼的能力。

(1)檢測e個隨機錯誤，則要求最小碼距為

d0≥e+1

(9-1)

式(9-1)可用圖9-2(a)來說明。圖中A為一個碼組，B為

另一個碼組。若碼組A有兩位錯碼，則碼組A變?yōu)橐訟為圓

心、以2為半徑的圓上某點。只要最小碼距不小于3，在半徑為2的圓上及圓內(nèi)就不會有其他許用碼組，因而可判斷出其

出錯，并且能檢測錯碼的位數(shù)等于2。即最小碼距d0能檢測

(d0－1)個錯誤。若要檢測e個錯誤，則必須滿足d0≥e+1。

(2)糾正t個隨機錯誤，則要求最小碼距為

d0≥2t+1

(9-2)

式(9-2)可用圖9-2(b)來說明。當碼組A發(fā)生兩位錯碼時，則其落在以A為圓心、以2為半徑的圓上某點。當碼組B有兩位錯碼時，則落在以B為圓心、以2為半徑的圓上某點。只

要這兩個圓不重疊、不相交，就能區(qū)分、判別得出左邊圓上的為碼組A，右邊圓上的為碼組B。可見為了能糾正兩位錯碼，則要求最小碼距為5。所以若糾正t個錯誤，則必須滿足d0≥2t+1。

(3)糾正t個隨機錯誤，同時檢測e(e>t)個隨機錯誤，則要求最小碼距為

d0≥t+e+1

(9-3)

式(9-3)可用圖9-2(c)來說明。當碼組A出現(xiàn)e個錯碼，它就落在以A為圓心、以e為半徑的圓上某點。碼組B出現(xiàn)t個錯碼時，將落在以B為圓心、以t為半徑的圓上某點。要糾正碼組B的錯誤，同時又能檢出碼組A的錯誤，就要求A的大圓和B的小圓不重疊、不相交，即A和B之間的距離要大于e+t。也就是說，最小碼距d0≥t+e+1。圖9-2最小碼距與檢錯糾錯能力的關(guān)系(a)檢測e個隨機錯誤;(b)糾正t個隨機錯誤;(c)糾正t個隨機錯誤，同時檢測e個隨機錯誤(e>t)

3.信道編碼的效用

假設(shè)在隨機信道中發(fā)送“0”時的錯誤概率與發(fā)送“1”時的相等，均等于P，且P<<1，則容易證明，在碼長為n的碼組中恰好發(fā)生r個錯誤的概率為(9-4)例如，當碼長n=7，P=10－3時，則有

P7(1)≈7P=7×10－3

P7(2)≈21P2=2.1×10－5

P7(3)≈35P3=3.5×10－8

可見，采用信道編碼后，即使僅能糾正(或檢測)這種碼組中1~2個錯誤，也可以使誤碼率下降幾個數(shù)量級。這表明信道編碼具有較大的實際應(yīng)用價值。

4.編碼效率

在分組碼中，傳遞的信息碼元稱為信息位;為糾、檢錯而增加的碼元稱為監(jiān)督位。分組碼一般用(n，k)表示，其中n是碼組長度，k是信息碼元個數(shù)，而r=n－k是監(jiān)督碼元個數(shù)。

用信道編碼提高通信系統(tǒng)的的可靠性，是以降低有效性為代價的。編碼效率R是用來衡量有效性的，它是碼組中信息碼元個數(shù)k與碼組長度n的比值。即(9-5)9.1.4常用的簡單編碼

1.奇偶監(jiān)督碼

奇偶監(jiān)督碼是在原信息碼后面附加一個監(jiān)督元，使得碼組中“1”的個數(shù)是奇數(shù)或偶數(shù)。或者說，它是含一個監(jiān)督元，碼重為奇數(shù)或偶數(shù)的(n，n－1)系統(tǒng)分組碼。奇偶監(jiān)督碼又

分為奇監(jiān)督碼和偶監(jiān)督碼。

設(shè)碼字A=［an－1,an－2,…,a1,a0］，偶監(jiān)督碼有

an－1⊕an－2⊕…⊕a1⊕a0=0(9-6)

式中，an－1、an－2、…、a1為信息元;a0為監(jiān)督元。由于該碼的每一個碼組均按同一規(guī)則構(gòu)成式(9-6)，故又稱為一致監(jiān)督碼。接收端譯碼時，按式(9-6)將碼組中的碼元模2相加，若結(jié)果為“0”，則認為無錯；若結(jié)果為“1”，則可斷定該碼組經(jīng)傳輸后有奇數(shù)個錯誤。奇監(jiān)督碼與其相似，只是碼組中“1”的個數(shù)為奇數(shù)，即滿足條件

an－1⊕an－2⊕…⊕a1⊕a0=1

(9-7)

且其檢錯能力與偶監(jiān)督碼相同。(9-8)

2.行列監(jiān)督碼

一般地，L×M個信息元附加L+M+1個監(jiān)督元，組成(LM+L+M+1，LM)行列監(jiān)督碼的一個碼字(L+1行，M+1列)。表9-1是(66，50)行列監(jiān)督碼的一個碼字(L=5，M=10)，它的

各行和各列對“1”的數(shù)目實行偶數(shù)監(jiān)督。譯碼時分別檢查各行、各列的監(jiān)督關(guān)系，判斷是否有錯。行列監(jiān)督碼具有較強的檢測隨機錯誤的能力。它不僅可以檢測每行的奇數(shù)個錯和每列的奇數(shù)個錯，而且行列交叉還可以檢測每行或每列的偶數(shù)個錯。但是分布在矩形的四個頂點的偶數(shù)個錯卻不能檢測出來。

行列監(jiān)督碼適于檢測突發(fā)錯誤。因為這種突發(fā)錯碼常常成串出現(xiàn)，隨后有較長一段無錯區(qū)間，所以在某一行中出現(xiàn)多個奇數(shù)或偶數(shù)錯碼的機會較多，而這種行列監(jiān)督碼正適于檢測這類錯碼。

3.恒比碼

碼字中“1”的數(shù)目與“0”的數(shù)目保持恒定比例的碼稱為恒比碼。由于恒比碼中，每個碼組均含有相同數(shù)目的“1”和“0”，因此恒比碼又稱等重碼，或定1碼。這種碼在檢測時，只要

計算接收碼元中“1”的個數(shù)是否與規(guī)定的相同，就可判斷有或無錯誤。目前我國電傳通信中普遍采用3∶2的恒比碼，又稱“5中取3”碼，即每個碼組的長度為5，其中有3個“1”。那么，許用碼組的數(shù)目為C35=10，恰好表示10個阿拉伯數(shù)字，如表9-2所示。由于每個漢字是以四位十進制數(shù)來代表的，因此提高十進制數(shù)字傳輸?shù)目煽啃裕偷扔谔岣邼h字傳輸?shù)目煽啃?。實踐證明，采用恒比碼后，我國漢字電報的差錯率大為降低。

4.群計數(shù)碼

群計數(shù)碼是將信息碼元分組后，計算每組碼元中“1”的個數(shù)，然后將該數(shù)目的二進制表示作為監(jiān)督碼元，一起送往發(fā)送端。如一組8位的信息碼元為“10111001”，其中“1”的個

數(shù)為5個，于是將“101”作為監(jiān)督碼元，傳輸?shù)拇a組為“10111001101”。收端只要檢測監(jiān)督碼元所表示的“1”的個數(shù)與信息碼元中“1”的個數(shù)是否相同，就可以判斷是否出現(xiàn)錯誤。

9.2線性分組碼

9.2.1線性分組碼的基本概念

線性分組碼，是指信息碼元與監(jiān)督碼元之間的關(guān)系可以用一組線性方程來表示的分組碼。即在(n，k)分組碼中，每一個監(jiān)督碼元都是碼組中某些信息碼元按模2和而得到的。線性分組碼是一類重要的糾錯碼，應(yīng)用很廣，前面所講的重復(fù)碼和奇偶監(jiān)督碼均是簡單的線性分組碼。一般來說，若碼長為n，信息位數(shù)為k，則監(jiān)督位數(shù)

r=n－k。如果希望用r個監(jiān)督位構(gòu)造出r個監(jiān)督關(guān)系式來指示

一位錯碼的n種可能位置，那么要求

2r－1≥n

或2r≥k+r+1

(9-9)

現(xiàn)以(7，4)分組碼為例來說明線性分組碼的特點。設(shè)其碼字為A=［a6a5a4a3a2a1a0］，其中a6、a5、a4、a3為信息碼元，a2、a1、a0為監(jiān)督碼元，可用下列線性方程組來表述這種線性分組碼產(chǎn)生的3個監(jiān)督碼元,即(9-10)顯然，式(9-10)中的三個方程是線性無關(guān)的。經(jīng)計算可得(7，4)碼的16種許用碼字，如表9-3所示。9.2.2監(jiān)督矩陣和生成矩陣

1.監(jiān)督矩陣H

將式(9-10)所述(7，4)碼的三個監(jiān)督關(guān)系式改寫為

(9-11)這組線性方程可用矩陣形式表示為并簡記為

HAT=0T

或AHT=0

(9-13)其中，AT是A的轉(zhuǎn)置;0T是0=［0

0

0］的轉(zhuǎn)置;HT是H的轉(zhuǎn)置。(9-14)稱為(7，4)碼的監(jiān)督矩陣，或稱一致校驗矩陣。一旦H給定，信息位和監(jiān)督位之間的關(guān)系也就確定了。(n，k)線性分組碼的監(jiān)督矩陣H是r×n階矩陣，每行之間是彼此線性無關(guān)的。監(jiān)督矩陣可以分成兩部分,即(9-15)式中，P為r×k階矩陣;Ir為r×r階單位陣。具有［PIr］形式的H矩陣稱為典型監(jiān)督矩陣。監(jiān)督矩陣H是產(chǎn)生監(jiān)督碼元的依據(jù)，也是檢錯和糾錯的

依據(jù)。由式(9-13)可知，許用碼字矩陣與H矩陣的轉(zhuǎn)置的乘積必為0，所以在接收端可以用H矩陣來校驗接收的碼字是否是許用碼。設(shè)接收到的碼字矩陣為B，將B代入(9-13)式，若BHT=0，則說明B為許用碼；若BHT≠0，則說明不是許用碼，即可以判斷為誤碼。

2.生成矩陣G

生成矩陣是在已知信息碼元時確定相應(yīng)的許用碼字

A=［a6a5a4a3a2a1a0］的矩陣。由式(9-10)可以產(chǎn)生監(jiān)督碼元

a2、a1、a0，只要在其中添上信息碼元的方程即可得到許用碼字，如式(9-16)所示。(9-16)將式(9-16)寫成矩陣形式,為(9-17)即(9-18)變換為

A=［a6a5a4a3］·G

(9-19)其中(9-20)稱為生成矩陣。由G和信息碼元就可以產(chǎn)生全部碼字。(n，k)線性分組碼的生成矩陣G為k×n階矩陣，各行也是線性無關(guān)的。生成矩陣也可以分為兩部分,其中Q為k×r階矩陣;Ik為k階單位陣。將具有［IkQ］形式的G矩陣稱為典型生成矩陣。

3.監(jiān)督矩陣H和生成矩陣G之間的關(guān)系

由上述分析可知，監(jiān)督矩陣H和生成矩陣G之間有一一

對應(yīng)的關(guān)系。由于G的每一行都為碼字，因此它必然滿足式(9-13)，即

(9-21)(9-22)式中，0為k×(n－k)階零矩陣；“+”為模2加。只有當P=QT時，式(9-22)才等于0。因此，監(jiān)督矩陣可寫成

H=［PIr］=［QTIr］(9-23)

同樣，生成矩陣可寫成

G=［IkQ］=［IkPT］(9-24)因此，只要得到了監(jiān)督矩陣H，生成矩陣G就確定了，反之亦然。9.2.3線性分組碼的譯碼

設(shè)發(fā)送碼字A=［an－1,an－2,…,a1,a0］，它符合AHT=0。由于在傳輸過程中可能發(fā)生誤碼，設(shè)接收碼字

B=［bn－1,bn－2,…,b1,b0］，因此收發(fā)碼字之差為

E=B－A

(9-25)

式中，E=［en－1,en－2,…,e1,e0］稱為錯誤圖樣，或誤差矢量;且

(9-26)

E矩陣中哪位出現(xiàn)1，就表示接收碼字B中相應(yīng)的碼元出錯了。接收端利用監(jiān)督矩陣來檢測接收碼字B中的錯誤。令S=BHT，稱S為伴隨式或校正子，則

S=BHT=(A+E)HT=AHT+EHT=EHT(9-27)

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

上述(7，4)碼的伴隨式與錯誤圖樣的對應(yīng)關(guān)系如表9-4所示。從表9-4可以看出，伴隨式S有2r種不同的形式，可以代表2r－1種錯誤圖樣。為了用伴隨式指明單個錯誤的位置以便糾正，必須要求2r－1≥n。9.2.4漢明碼

(1)監(jiān)督碼元個數(shù)為r，碼長滿足n=2r－1，則信息碼元個數(shù)k=n－r，r≥2且為正整數(shù)。給定r后，就可確定n和k。

(2)無論碼長n為多少，漢明碼的最小碼距均為d0=3，因此它只能糾1位錯碼。漢明碼可用于FEC系統(tǒng)，一般不用于ARQ、HEC系統(tǒng)。

(3)編碼效率為

9.3循環(huán)碼

9.3.1循環(huán)碼的基本概念

表9-5中給出一種(7，3)循環(huán)碼的全部碼字。(7，3)循環(huán)碼有兩個循環(huán)圈，一個是編號為1的全0碼字組成的循環(huán)圈，碼重為0；另一個是剩余7個碼字組成的循環(huán)圈。若從編號為

1的碼字開始，每次向左移動一位，可以得到1→3→7→6→5

→2→4→1的循環(huán)圈，其碼重為4。

為了便于用代數(shù)學理論分析、計算循環(huán)碼，常用代數(shù)多項式來表示碼字，稱為碼多項式。(n，k)循環(huán)碼的碼多項式按降冪順序排列為

A(x)=an－1xn－1+an－2xn－2+…+a1x+a0(9-28)

碼組中各碼元的取值是其碼多項式中相應(yīng)各項的系數(shù)值

(0或1)，運算時其系數(shù)的運算為模2運算。

例如表9-5中的碼字1001110、1101001用碼多項式表示分別為

A4(x)=x6+x3+x2+x

A6(x)=x6+x5+x3+1

且A4(x)+A6(x)=A2(x)=x5+x2+x+1，即1001110⊕1101001=

0100111。9.3.2生成多項式和生成矩陣

如果一種碼的所有碼多項式都是多項式g(x)的倍式，則稱g(x)為該碼的生成多項式。在(n，k)循環(huán)碼中,任意的碼多項式A(x)都是最低次碼多項式的倍式。在表9-5所示的(7，3)循環(huán)碼中

g(x)=A1(x)=x4+x3+x2+1

(9-29)

其他碼多項式都是g(x)的倍式，即(9-30)因此，循環(huán)碼中次數(shù)最低的多項式(全0碼字除外)就是

生成多項式g(x)?？梢宰C明，g(x)是常數(shù)項為1的r=n－k次多

項式，是xn+1的一個因式。選擇不同的因式作為生成多項式，可構(gòu)成不同形式的循環(huán)碼。為了尋找生成多項式，必須對xn+1進行因式分解。用碼多項式來表示生成矩陣的各行，則循環(huán)碼的生成矩陣可以寫成例如(7，3)循環(huán)碼，n=7，k=3，r=4，其生成多項式及生成矩陣分別為(9-32)(9-33)即(9-34)因為式(9-34)不符合典型生成矩陣的形式，所以它不是典型生成矩陣，由它編制的碼字不是系統(tǒng)碼，但是對此矩陣做線性變化可以變換成典型形式。設(shè)上例中信息碼為［a6a5a4］，由生成矩陣多項式可以寫出該循環(huán)碼的碼字為(9-35)式中，m(x)是信息碼［a6a5a4］的多項式。在已知信息碼M=［mk－1,mk－2,…,m1,m0］和生成多項式g(x)后，(n，k)循環(huán)碼的所有碼字就可以由(9-36)式生成。

A(x)=M·G(x)=［mk－1,mk－2,…,m1,m0］·G(x)

=m(x)·g(x)

(9-36)

式中，m(x)為信息位所對應(yīng)的多項式，其最高次數(shù)為k－1。9.3.3監(jiān)督多項式和監(jiān)督矩陣

為了便于對循環(huán)碼編/譯碼，通常還定義監(jiān)督多項

式，令(9-37)由于g(x)是常數(shù)項為1的r次多項式，因此h(x)是常數(shù)項為1的k次多項式。將h(x)稱為監(jiān)督多項式。同理，它的監(jiān)督矩陣H可以表示為

(9-38)其中(9-39)是h(x)的逆多項式。例如(7，3)循環(huán)碼，生成多項式g(x)=x4+x3+x2+1，則其

監(jiān)督多項式為(9-40)h(x)的逆多項式為

h*(x)=x3+x+1(9-41)其監(jiān)督矩陣為

(9-43)監(jiān)督矩陣H也可由生成矩陣G得出，而G一定要為典型形式，即

H=［PIr］，

G=［IkQ］，P=QT(9-44)9.3.4循環(huán)碼的編碼和譯碼

1.循環(huán)碼的編碼

在編碼時，首先要根據(jù)給定的(n，k)值選定生成多項式g(x)，即從xn+1的因式中選一個r次多項式作為g(x)。由式

(9-36)可知，循環(huán)碼中的所有碼多項式都可被g(x)整除，根據(jù)這條原則，就可以對給定的信息進行編碼：設(shè)m(x)為信息多項式，其次數(shù)小于為k,那么用xr乘以m(x)，得到xr·m(x)的次數(shù)小于n;用g(x)去除xr·m(x)，得到余式r(x)，r(x)的次數(shù)必小于g(x)的次數(shù)，即小于(n－k)。將余式r(x)加于信息位之后作為監(jiān)督位，即將r(x)與xrm(x)相加，得到多項式

A(x)=xr·m(x)+r(x)(9-45)

式中，xr·m(x)代表信息位；r(x)是xr·m(x)除以g(x)得到的

余式，代表監(jiān)督位。A(x)必為一碼多項式，這是因為它能被g(x)整除，且商的次數(shù)不大于k－1。

(1)用xr乘以m(x)。這一運算實際上是在信息碼之后附加上r個“0”，給監(jiān)督位留出地方。例如，信息碼為110，它相當于m(x)=x2+x。對(7，3)循環(huán)碼，r=4，則xr·m(x)=x4(x2+x)

=x6+x5，它相當于1100000。

(2)用g(x)去除xr·m(x)，得到商Q(x)和余式r(x)，即(9-46)

例如，(7，3)循環(huán)碼的生成多項式為g(x)=x4+x3+x2+1，則(9-47)得余式r(x)=x2，即監(jiān)督碼的多項式。式(9-47)相當于(9-48)

(3)編制的碼組為A(x)=xr·m(x)+r(x)。在上例中，1100000+1001=1101001。上述編碼過程可用除法電路來完成。除法電路的主體由一些移位寄存器和模2加法器組成。當g(x)=x4+x3+x2+1時，(7，3)循環(huán)碼的編碼電路如圖9-3所示。g(x)的次數(shù)等于移位寄存器的級數(shù)，即有4級移位寄存器，分別用D0、D1、D2、D3表示；g(x)的x0、x1、x2、…、xr的非零系數(shù)對應(yīng)移位寄存器的反饋抽頭。首先，將4級移位寄存器清0，當3位信息元輸入時，

門1斷開、門2接通，然后直接輸出信息元。第3次移位脈沖到來時將除法電路運算所得的余數(shù)存入4級移位寄存器中。

第4~7次移位時，門2斷開、門1接通，輸出監(jiān)督碼。設(shè)輸入信息碼為110，表9-6給出了上述編碼過程中各點的狀態(tài)變化情況。

2.循環(huán)碼的譯碼

接收端譯碼的目的是檢錯和糾錯。只進行檢錯的譯碼原理十分簡單,因為任意碼多項式A(x)都應(yīng)該能被生成多項式g(x)整除，所以在收端可以將接收碼組B(x)用生成多項式去除即可。當傳輸中未發(fā)生錯誤時，接收碼組和發(fā)送碼組相同，即A(x)=B(x)，故接收碼組B(x)必定能被g(x)整除。若碼組在傳輸中發(fā)生錯誤，則B(x)≠A(x)，B(x)除以g(x)時除不盡而有余項，所以，可以用余項是否為0來判別碼組中有或無誤碼。在接收端為糾錯而采用的譯碼方法自然比檢錯時復(fù)雜。同樣，為了能夠糾錯，就要求每個可糾正的錯誤圖樣必須與一個特定余式有一一對應(yīng)的關(guān)系。原則上糾錯可按下述步驟進行：

(1)用生成多項式g(x)除接收碼組B(x)=A(x)+E(x)，得出余式r(x)；

(2)按余式r(x)用查表的方法或通過某種運算得到錯誤圖樣E(x)，就可以確定錯碼位置；

(3)從B(x)中減去E(x)，便得到已糾正錯誤的原發(fā)送碼組A(x)。圖9-4所示為一種(7，3)循環(huán)碼糾單個錯的譯碼電路，它包含除法電路、7級緩存器、門電路及輸出前做模2運算的異或。接收碼組B(x)輸入后分兩路，一路送入7級緩存器暫存，另一路送入除法電路做除法。當碼組全部進入除法電路后，若B(x)能被g(x)整除，則除法電路中移位寄存器的狀態(tài)全為0，說明接收碼組為許用碼組，判斷無錯，直接將緩存器暫存的B(x)輸出。若B(x)不能被g(x)整除，則除法電路中的存數(shù)指出錯誤位置，經(jīng)移位(碼組全部進入除法電路，再移位則輸入為0)，與門在相應(yīng)的出錯碼位上的輸出為“1”。這個輸出的“1”有兩個功用，一是與緩存器輸出的錯碼模2相加，糾正錯碼；二是反饋回除法電路，使各級移位寄存器清0。圖9-4(7，3)循環(huán)碼的譯碼電路9.3.5實用循環(huán)碼簡介

1.BCH碼

對于任意碼長m≥2、糾錯數(shù)目為t的編碼，都存在滿足下列參數(shù)的BCH碼：碼長n=2m－1，監(jiān)督位個數(shù)n－k≤mt，最小碼距d0=2t+1。由于m和t可以任意選擇，因此在碼長和碼率的設(shè)計上有很大的選擇余地。BCH碼已經(jīng)過詳細的推導，并且有了碼長為7～255的BCH碼生成多項式的系數(shù)表。

2.CRC碼

循環(huán)冗余校驗碼，簡稱CRC碼，是一種簡單、有效的實用循環(huán)編碼。其編碼器和錯誤檢測電路都很容易實現(xiàn)，已成為最常用的一種校驗方式。因為r=n－k，所以常將(n，k)循

環(huán)碼稱為CRC-r碼。實用的CRC碼已有多種生成多項式。表

9-7列出了已成為國際標準的CRC-r碼的生成多項式及應(yīng)用。

3.RS碼

RS碼是由里德和索洛蒙提出的，故RS碼又稱為里德-索洛蒙(Reed-Solomon)碼。它是一種特殊的多進制BCH碼，即碼字c=(c1,c2,…,cn)中的任意元素ci是一個M進制數(shù)，M=2m，這時每個M進制字符包含m比特信息，其中m是大于2的正整數(shù)。

(n，k)RS碼是按照下列條件定義的BCH碼：碼長n=M－1=2m－1，最小碼距d0=n－k+1，碼率R=k/n。RS碼能夠糾正t=(d0－1)/2個碼元錯誤。

RS碼具有優(yōu)越的距離特性，特別適合于M進制調(diào)制聯(lián)合使用。RS碼還能夠有效地糾正突發(fā)錯誤，因此特別適用于突發(fā)錯誤信道，例如移動通信網(wǎng)等衰落信道。

4.交織碼

交織碼是一種能糾正突發(fā)錯誤的碼。它利用糾正隨機錯誤的碼字，以交織的方法來構(gòu)造新的碼字。把糾正隨機錯誤的(n，k)線性分組碼的m個碼字，排成m行的一個矩陣，該矩陣稱為交織碼陣。一個交織碼陣就是交織碼的一個碼字。交織碼的每一行稱為交織碼的子碼；行數(shù)m稱為交織度。圖9-5所示是一個m=4的(28，16)交織碼，其子碼是能糾正單個隨機錯誤的(7，4)線性分組碼。圖9-5m=4的(28，16)交織碼在圖9-5中，傳輸時按列的次序進行，因此送往信道的碼字為a61a62a63a64a51a52…a01a02a03a04。在傳輸過程中，如果發(fā)生長度小于4的單個突發(fā)錯誤，那么無論從哪一位開始，至多只影響每個子碼中的一個碼元。收端將接收到的碼字重新按照交織方式再排列成圖9-5所示的碼陣，然后逐行進行譯碼，由于每一行能糾正一個錯誤，因此在對4行譯碼完成后，就可把突發(fā)錯誤糾正過來。如果要糾正較長的突發(fā)錯誤，那么可以把碼陣中的行數(shù)增加，即增大交織度。一般來說，若一個(n，k)碼能糾正t個隨機錯誤，按照上述方法進行交織，交織度為m，則可得到一個(nm，km)交織碼。該交織碼能糾正長度小于mt的單個突發(fā)錯誤。可以證明，如果(n，k)線性分組碼是一個循環(huán)碼，它的生成多項式為g(x)，那么(nm，km)交織碼也是一個循環(huán)碼，其生成多項式為g(xm)，且碼率與其子碼的相同。

9.4卷積碼

9.4.1卷積碼的基本概念

卷積碼又稱連環(huán)碼，是1955年提出來的一種糾錯碼，它和分組碼有明顯的區(qū)別，屬于非分組碼。(n，k)線性分組碼中，本組r=n－k個監(jiān)督元僅與本組的k個信息元有關(guān)，與其他

各組無關(guān)，也就是說分組碼編碼器本身并無記憶性。卷積碼則不同，每個(n，k)碼段(也稱子碼，通常較短)內(nèi)的n個碼元不僅與該碼段內(nèi)的信息元有關(guān)，而且與前面m段的信息元有關(guān)。卷積碼常用符號(n，k，m)表示。其中，n為碼長，

k為碼組中信息碼元的個數(shù)，m為相互關(guān)聯(lián)的碼組的個數(shù)。圖9-6所示的是(2，1，2)卷積碼的編碼器，它由移位寄存器、模2加法器及開關(guān)電路組成。圖9-6(2，1，2)卷積碼編碼器起始狀態(tài)，各級移位寄存器清0，即S1S2S3為000。S1

等于當前輸入數(shù)據(jù)，而移位寄存器狀態(tài)S2S3存儲以前的數(shù)據(jù)，輸出碼字C由下式確定(9-49)當輸入數(shù)據(jù)D=［11010］時，輸出碼字可以計算出來，具體計算過程如表9-8所示。另外，為了保證全部數(shù)據(jù)通過寄存器，還必須在數(shù)據(jù)位之后加3個“0”。9.4.2卷積碼的圖解描述

1.樹圖

樹圖描述的是在任何數(shù)據(jù)序列輸入時，碼字所有可能的輸出。對應(yīng)于圖9-6所示的(2，1，2)卷積碼的編碼電路，可以畫出其樹圖如圖9-7所示。圖9-7(2，1，2)卷積碼的樹圖圖9-7中每一分支代表一個輸入比特。一般輸入為“0”對應(yīng)上分支，輸入為“1”對應(yīng)下分支，每個分支上面標出與輸入對應(yīng)的輸出碼。以S1S2S3=000作為起點，用a、b、c和d表示出S2S3的四種可能狀態(tài)：00、01、10和11。若第一位數(shù)據(jù)S1=0，輸出C1C2=00，從起點通過上支路

到達狀態(tài)a，即S3S2=00；若S1=1，C1C2=11，從起點通過下支路到達狀態(tài)b，即S3S2=01；依此類推，可得整個樹圖。輸入不同的信息序列，編碼器就走不同的路徑，輸出不同的碼序列。例如當輸入數(shù)據(jù)為［11010］時，其路徑如圖9-7中虛線所示，并得到輸出碼序列為［11010100…］，與表9-8所列的結(jié)果一致。

2.狀態(tài)圖

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

圖9-8中有4個節(jié)點a、b、c、d，同樣分別表示S3S2的四種可能狀態(tài)。每個節(jié)點上有兩條線離開，其中實線表示輸入數(shù)據(jù)為0，虛線表示輸入數(shù)據(jù)為1，線旁的數(shù)字即為輸出碼字。圖9-8(2，1，2)卷積碼的狀態(tài)圖

3.格圖

格圖也稱網(wǎng)絡(luò)圖或籬笆圖，由狀態(tài)圖在時間上展開而得到，如圖9-9所示。圖中畫出了所有可能的數(shù)據(jù)輸入時，狀態(tài)轉(zhuǎn)移的全部可能軌跡，其中實線表示輸入數(shù)據(jù)為“0”，虛線表示輸入數(shù)據(jù)為“1”，線旁數(shù)字為輸出碼字，節(jié)點表示狀態(tài)。圖9-9(2，1，2)卷積碼的格圖9.4.3卷積碼的譯碼

1.維特比譯碼

維特比譯碼是一種最大似然譯碼算法，它是維特比于1967年提出的。由于這種譯碼方法比較簡單，計算快，因此得到了廣泛應(yīng)用，特別是在衛(wèi)星通信和蜂窩網(wǎng)通信系統(tǒng)中的應(yīng)用。最大似然譯碼算法的基本思路是，把接收碼字與所有可能的碼字比較，選擇一種碼距最小的碼字作為譯碼輸出?，F(xiàn)還以上述(2，1，2)卷積碼為例說明維特比譯碼過程。設(shè)發(fā)端的信息數(shù)據(jù)D=［11010000］，由編碼器輸出的碼

字C=［1101010010110000］，收端接收的碼序列

B=［0101011010010010］，有4位碼元差錯。下面參照圖9-9的格圖說明譯碼過程。如圖9-10所示，先選前3個碼作為標準，對到達第3級的4個節(jié)點的8條路徑進行比較，逐步算出每條路徑與接收碼字之間的累計碼距。累計碼距分別用括號內(nèi)的數(shù)字標出，將其對比后保留一條到達該節(jié)點的碼距較小的路徑作為幸存路徑。再將當前節(jié)點移到第4級，計算、比較、保留幸存路徑，直至最后得到一條到達終點的幸存路徑為止，即為譯碼路徑，如圖9-10中實線所示。根據(jù)該路徑，得到譯碼結(jié)果。從譯碼過程中可以看出，維特比算法的存儲量僅要求為2m+1，對于

m＜10時，該算法有較大吸引力。圖9-10維特比譯碼法圖解

2.序列譯碼

當m很大時，可以采用序列譯碼法。其過程是：譯碼先從碼樹的起始節(jié)點開始，把接收到的第一個子碼的n個碼元與自始節(jié)點出發(fā)的兩條分支按照最小漢明距離進行比較，沿著差異最小的分支走向第二個節(jié)點。在第二個節(jié)點上，譯碼器仍以同樣原理到達下一個節(jié)點，依此類推，最后得到一條路徑。若接收碼組有錯，則自某節(jié)點開始，譯碼器就一直在不正確的路徑中行進，譯碼也一直是錯誤的。

9.5其他信道編碼技術(shù)

9.5.1級聯(lián)碼

1.級聯(lián)碼原理

級聯(lián)碼原理方框如圖9-11所示，它是由兩個短碼串聯(lián)而成的。其中，將(n1，k1)稱為內(nèi)碼；(n2，k2)稱為外碼。圖9-11級聯(lián)碼原理方框圖

Foney提出的級聯(lián)結(jié)構(gòu)如下：

(n,k)=［n1n2,k1k2］=［(n1,k1),(n2,k2)］(9-50)

(1)設(shè)總的信息位為k位，它由k2字節(jié)構(gòu)成，每個字節(jié)為k1比特，故有k=k1k2。

(2)外碼(n2，k2)一般設(shè)計成糾錯能力強且較為復(fù)雜的碼，最常用的是RS碼。外編碼后，每k2字節(jié)變?yōu)閚2字節(jié)的碼，

即輸入k=k1k2比特信息碼，輸出k1n2比特外碼。