第7章糾錯編碼7.1差錯控制方式7.2糾錯編碼的基本原理7.3常用的簡單編碼7.4線性分組碼7.5卷積碼習題與思考題7.1差錯控制方式

常用的差錯控制方式主要有三種：檢錯重發（ARQ，Automatic-Request-Repetition）、前向糾錯（FEC,Forward-Error-Control）和混合糾錯（HEC,Hybrid-Error-Correction）。它們的系統構成如圖7.1所示。

圖7.1差錯控制方式的系統構成(a)檢錯重發；(b)前向糾錯；(c)混合糾錯7.1.1檢錯重發在檢錯重發方式中，發送端經編碼后發出能夠發現錯誤的碼，接收端收到后經檢驗如果發現傳輸中有錯誤，則通過反向信道把這一判斷結果反饋給發送端，然后，發送端把前面發出的信息重新傳送一次，直到接收端認為已正確地收到信息為止。常用的檢錯重發系統有三種，即停發等候重發、返回重發和選擇重發。圖7.2中畫出了這三種系統的工作原理圖。

圖7.2ARQ差錯控制系統工作原理(a)停發等候重發；(b)返回重發；(c)選擇重發

圖7.2（a）表示停發等候重發系統的發送端、接收端的信號傳遞過程。發送端在TW時間內送出一個碼組給接收端，接收端收到后經檢測若未發現錯誤，則發回一個認可信號（ACK）給發送端，發送端收到ACK信號后再發出下一個碼組。返回重發系統如圖7.2（b）所示。7.1.2前向糾錯在前向糾錯系統中，發送端經編碼發出能夠糾正錯誤的碼，接收端收到這些碼組后，通過譯碼能自動發現并糾正傳輸中的錯誤。前向糾錯方式不需要反饋信道，特別適合于只能提供單向信道的場合。由于該系統能自動糾錯，不要求檢錯重發，因而具有延時小，實時性好等特點。7.1.3混合糾錯混合糾錯方式是前向糾錯方式和檢錯重發方式的結合。在這種系統中，發送端不但有糾正錯誤的能力，而且對超出糾錯能力的錯誤有檢測能力。遇到后一種情況時，通過反饋信道要求發送端重發一遍。混合糾錯方式在實時性和譯碼復雜性方面是前向糾錯和檢錯重發方式的折衷。7.2糾錯編碼的基本原理

現在我們來討論糾錯編碼的基本原理。為了便于理解，先通過一個例子來說明。一個由三位二進制數字構成的碼組，共有八種不同的可能組合。若將其全部利用來表示天氣，則可以表示八種不同的天氣，譬如：000（晴），001（云），010（雨），011（陰），100（雪），101（霜），110（霧），111（雹）。其中，任意碼組在傳輸中若發生1個或多個錯碼，則該碼組將變成另一信息碼組。這時接收端將無法發現錯誤。若在上述八種碼組中只準許使用四種來傳送信息，譬如：

000=晴

011=云

101=陰

110=雨(7.1)

分組碼一般用符號（n，k）表示，其中k是每組二進制信息碼元的數目，n是編碼組的總位數，又稱為碼組長度（碼長），n-k=r為每個碼組中的監督碼元數目或稱監督位數目。通常，將分組碼規定為具有如圖7.3所示的結構。圖中前面k位（an-1

…ar）為信息位，后面附加r個監督位（ar-1

…a0）。在式（7.1）的分組碼中，n=3，k=2，r=1。表7.1圖7.3分組碼的結構

在分組碼中，我們把“1”的數目稱為碼組的重量，而把兩個碼組對應位上數字不同的位數稱為碼組的距離，簡稱碼距，又稱漢明（Hamming）距離。式（7.1）中四個碼組之間任何兩個的距離均為2。我們把某種編碼中各個碼組間距離的最小值稱為最小碼距（d0），例如，按式（7.1）編碼的最小碼距d0=2。圖7.4碼距的幾何意義

一種編碼的最小碼距d0的大小直接關系到這種編碼的檢錯和糾錯能力。下面我們將具體對此加以說明。

(1）為檢測e個錯碼，要求最小碼距為

d0≥e+1(7.2)則該碼組中的編碼具有檢測e

位差錯的能力。因為當編碼之間最小碼距為d0,比錯碼位數大于1時,只要編碼中出現的錯碼位數不超過e,則都不可能變成另一個允許使用的編碼,因此接收端能發現這樣的差錯(2)若編碼組中編碼之間最小碼距滿足:

d0≥2t+1（7.3）則該碼組中的編碼具有糾正t

位差錯的能力。因為當碼組中允許使用的編碼發生t

位差錯時,形成的錯誤編碼與另一個允許使用的編碼錯t

位碼后形成的編碼之間還有至少1位的碼距,則這兩個編碼就不會被混淆,就可糾正為原來的正確編碼;否則就可能被錯誤地糾正為另一個允許使用的編碼,而使差錯更大。(3）為糾正t個錯碼，同時檢測e個錯碼，要求最小碼距為

d0≥e+t+1(e>t)(7.4)則該碼組中的編碼具有糾正t

位差錯并檢測e

位差錯的能力。需要注意的是:若接收到的編碼與某一允許使用的編碼之間的距離在糾錯范圍t

位內,則對其進行糾錯;若接收到的編碼與某一允許的編碼之間的距離超過t,則只能對其進行檢錯,檢錯能力范圍為e

。當某一允許使用的編碼出現e位差錯后與另一個允許使用的編碼間距離至少為t-1,否則會進入另一個允許使用的編碼的糾錯范圍而被錯糾為另一編碼。

假設在隨機信道中發送“0”時的錯誤概率和發送“1”時的相等，都等于p，且p<<1,容易證明，在碼長為n的碼組中恰好發生r個錯碼的概率為

（7.5）可見,采用差錯控制編碼,即使僅能糾正(或檢測)這種碼組中1~2個錯誤,也可以使誤碼率下降幾個數量級。這就表明,即使是較簡單的差錯控制編碼也具有較大的使用價值。7.3常用的簡單編碼7.3.1奇偶監督碼奇偶監督碼是一種最簡單的檢錯碼，又稱奇偶校驗碼，在計算機數據傳輸中得到了廣泛的應用。在ISO和CCITT提出的七單位國際5層字母表、美國信息交換碼ASCII字母表及我國的七單位字符編碼標準中都采用7比特碼組表示128種字符，如字符A的編碼表示為1000001（在第8章將較詳細地介紹）。

一般情況下奇偶監督碼的編碼規則是：首先將要傳輸的信息分成組，然后將各位二元信息及附加監督位用模2和相加，選擇正確的監督位，保證模2和的結果為0（偶校驗）或1（奇校驗）。這種監督關系可以用公式表示。設碼組長度為n，表示為（an-1an-2

an-3

…a0），其中前n-1位為信息，第n位為校驗位，則偶校驗時有監督碼元a0即為(7.6a)（7.6b）奇校驗時有（7.6c）（7.6d）監督碼元a0為7.3.2水平奇偶監督碼針對上述奇偶監督碼檢錯能力不高，特別是不能檢測突發錯誤的缺點，可以將經過奇偶監督編碼的碼元序列按行排列成方陣，每行為一組奇偶監督碼（如表7.2所示），但發送時則按列的順序傳輸：00010011101…1001011，接收端仍然將碼元排成發送時的方陣形式，然后按行進行奇偶校驗。由于按橫行進行奇偶校驗，因此稱其為水平奇偶監督碼或行奇偶監督碼。表7.2水平奇偶監督碼7.3.4群計數碼在群計數碼中，信息碼元分組后計算其“1”的個數，然后將這個數目的二進制表示作為監督碼元附加在信息碼元之后送往信道。例如一組信息碼元為11100101，其中有5個“1”，用二進制數字表示為“101”，傳輸的碼組即為11100101101。這種碼的檢錯能力很強，除了發生1變0和0變1成對的錯誤之外，它能檢測出所有形式的錯誤。7.4線性分組碼7.4.1線性分組碼的概念前面介紹的奇偶監督碼其編碼原理利用了代數關系式，我們把這類建立在代數基礎上的編碼稱為代數碼。在代數碼中，常見的是線性碼。線性碼中的信息位和監督位是由一些線性代數方程聯系著的，或者說，線性碼是按一組線性方程構成的。這里將以漢明碼為例引入線性分組碼的一般原理。

按式（7.6a）條件構成的偶數監督碼由于使用了1位監督位a0，因此它就能和信息位an-1

…a1一起構成一個代數式，如式（7.6a）所示。在接收端解碼時，實際上就是計算（7.7）

一般說來，若碼長為n，信息位數為k，則監督位數r=n-k。如果希望用r個監督位構造出r個監督關系式來指示一位錯碼的n種可能位置，則要求

2r-1≥n

或2r≥k+r+1(7.8)

下面我們通過一個例子來說明如何構成這些監督關系式。表7.3

由表中規定可見，僅當1個錯碼位置在a2、a4、a5或a6時，校正子S1為1；否則S1為0。這就意味著a2、a4、a5和a6

4個碼元構成的偶數監督關系為

S1=a6⊕a5⊕a4⊕a2

（7.9）同理，a1、a3、a5和a6構成的偶數監督關系為

S2=a6⊕a5⊕a3⊕a1

（7.10）

以及a0、a3、a4和a6構成的偶數監督關系為

S3=a6⊕a4⊕a3⊕a0

（7.11）在發端編碼時，信息位a6、a5、a4和a3的值決定于輸入信號，因此它們是隨機的。監督位a2、a1和a0應根據信息位的取值按監督關系來確定，監督位應使上式中S1、S2和S3的值為零（表示編成的碼組中應無錯碼），即a6⊕a5⊕a4⊕a2=0a6⊕a5⊕a3⊕a1=0a6⊕a4⊕a3⊕a0=0(7.12)由上式經移項運算，解出監督位為

a2=a6⊕a5⊕a4a1=a6⊕a5⊕a3a0=a6⊕a4⊕a3(7.13)

接收端收到每個碼組后，先按式（7.9）~式（7.11）計算出S1、S2和S3，再按表7.3判斷錯誤情況。例如，若接收碼組為0000011，則按式（7.9）～式（7.11）計算可得S1=0，S2=1

，S3=1。由于S1S2S3等于011，故根據表7.3可知在a3位有一錯碼。7.4.2線性分組碼的矩陣描述現在我們再來討論線性分組碼的一般原理。上面已經提到，線性碼是指信息位和監督位滿足一組線性方程的碼。式（7.12）就是這樣一組線性方程的例子。現在將它改寫成1·a6＋1·a5＋1·a4＋0·a3＋1·a2＋0·a1＋0·a0=01·a6＋1·a5＋0·a4＋1·a3＋0·a2＋1·a1＋0·a0=01·a6＋0·a5＋1·a4＋1·a3＋0·a2＋0·a1＋1·a0=0(7.14)

注：

上式中將“⊕”簡寫為“+”。在本章后面，除非另加說明，這類式中的“+”都指模2加。式（7.14）又可以表示成(模2)（7.15）上式還可以簡記為

H·AT=OT

或A·HT=0（7.16）其中：

類似于式（7.12）改變成式（7.15）中矩陣形式那樣，式（7.13）也可以改寫成以下形式：（7.18）或者（7.19）

式中，

Q為k×r階矩陣，它為

P的轉置，即

Q=PT

（7.20）式（7.19）表明，信息位給定后，用信息位的行矩陣乘矩陣

Q就能產生出監督位。我們將

Q的左邊加上一個k×k階單位方陣就構成一矩陣

G

(7.21)

式中，G稱為生成矩陣，因為由它可以產生整個碼組，即有［a6a5a4a3a2a1a0］=［a6a5a4a3］·G

（7.22）或者

A=［a6a5a4a3］·G

（7.23）與H矩陣相似,我們也要求G矩陣的各行是線性無關的。因為由式(7.23)可以看出,任意碼組A都是G的各行的線性組合。G

共有k

行,若它們線性無關,則可組合出2k種不同的碼組A,它恰是有k

位信息位的全部碼組;若G

的各行有線性相關的,則不可能由G生成2k種不同碼組了。實際上,G

的各行本身就是一個碼組。因此,如果已有k

個線性無關的碼組,則可以用其作為生成矩陣G,并由它生成其余的碼組。7.4.3線性分組碼的糾錯和檢錯一般來說，式（7.23）中A為一n列的行矩陣。此矩陣的n個元素就是碼組中的n個碼元，所以發送的碼組就是A。此碼組在傳輸中可能由于干擾而引入差錯，故接收碼組與A不一定相同。若設接收碼組為一n列的行矩陣

B，即

B=［bn-1bn-2...b0］（7.24）則發送碼組和接收碼組之差為

B-A=E

（模2）（7.25）式中，

E是傳輸中產生的錯碼行矩陣，其值為

E=［en-1en-2...e0］（7.26）其中:

因此，若en

=0，則表示該位接收碼元無錯；若en=1，則表示該位接收碼元有錯。式（7.25）

也可以改寫成

B=A+E

（7.27）例如，若發送碼組A=［1000111］，錯碼矩陣

E=［0000100］，則接收碼組

B=［1000011］

。錯碼矩陣有時也稱為錯誤圖樣。

接收端譯碼時，可將接收碼組

B代入式（7.16）中計算。若接收碼組中無錯碼，即

E=0

，則

B=A+E=A，把它代入式（7.16）后，該式仍成立，即有

B·HT=0（7.28）

當接收碼組有錯時，

E≠0，將

B代入式（7.16）不一定成立。在錯碼較多，已超過這種編碼的檢錯能力時，

B變為另一許用碼組，則式（7.28）仍能成立。這樣的錯碼是不可檢測的。在未超過檢錯能力時，式(7.28)不成立，即其右端不等于零。假設這時式（7.28）的右端為S，即

B·HT=S

（7.29）

將

B=A+E代入式(7.29)可得

S=（A+E）HT

=A·HT+EHT

由式（7.16）知A·HT=0，所以有

S=EHT

（7.30）7.5卷積碼7.5.1卷積碼的結構及描述

卷積碼編碼器的一般形式如圖7.5所示，它包括：一個由N段組成的輸入移位寄存器，每段有k級，共nN位寄存器；一組n個模2和相加器；一個由n級組成的輸出移位寄存器。圖7.5卷積碼編碼器的一般形式

描述卷積碼的方法有兩類：圖解表示和解析表示。這里我們以圖7.6所示的（2，1，3）卷積碼為例介紹圖解法。圖7.6(2，1，3)卷積碼編碼器7.5.2卷積碼的圖解表示由圖7.6可得

x1j

=mj⊕mj-1

⊕mj-2

x2j

=mj⊕mj-2

(7.31)

X={x11x21

,x12

x22

,x13x23...x1jx2j...}(7.32)

現若按（2，1，3）卷積碼編碼器進行編碼，當M=［11010］時，由式（7.31）可知：

x1j

=［10001100］

x2j

=［11100100］

則輸出序列為

X={1101010010110000}1.樹狀圖如圖7.6所示，在（2,1,3）卷積碼編碼器中，輸出移位寄存器用轉換開關代替，每輸入一個信息比特，經編碼產生2個輸出比特。假設移位寄存器的起始狀態為全0，則當第一個輸入比特為0時，輸出比特為00；當第一個輸入比特為1時，輸出比特為11。隨著第二個比特的輸入，第一個比特右移1位，此時輸出比特同時受當前輸入比特和前一個輸入比特的影響。第三個比特輸入時，第一、二個比特分別右移1位，同時輸出兩個由這3位移位寄存器存儲內容所共同決定的比特。圖7.7（2,1,3）卷積碼的樹狀圖表示

例如，信息碼M=［00000］按式（7.31）和式（7.32）分別有

x1j=［00000000］

x2j

=［00000000］

X=［0000000000000000］卷積碼編碼器輸出的碼對應碼樹中的每個分支的上支，用圖7.7中上支所示的虛線表示。

若M=［11111］，則有

x1j

=［10111010］

x2j

=［11000110］

X=［1101101010011100］卷積碼對應碼樹每個分支的下支，用圖7.8中下支所示的虛線表示。若M=［0101］，則有

x1j=［0110110］

x2j

=［0100010］

X=［00111000101100］

例7.2

設M=［101101］，用（2，1，3）編碼器求其輸出值X。

解

為使最后一位信息碼被充分利用，應在信息碼流尾部添加三個“0”，即

M=［101101000］具體編碼步驟如下：來1

走下支

始點a

路徑值11終點b

來0

走上支

始點b

路徑值10

終點c

來1

走下支

始點c

路徑值00

終點b

來1

走下支

始點b

路徑值01

終點d

來0

走上支

始點d

路徑值01

終點c

來1

走下支

始點c

路徑值00

終點b

來0

走上支

始點b

路徑值10

終點c

來0

走上支

始點c

路徑值11

終點a

來0

走上支

始點a

路徑值00

終點a卷積碼編碼結果X就是把路徑按先后次序寫出，即得X=［111000010100101100］2.網格圖按照碼樹中觀察到的重復性，得到一種更為緊湊的圖形表示，即網格圖，如圖7.9所示。

圖7.8(2,1,3)卷積碼的網格圖表示

在網格圖中，把碼樹中具有相同狀態的節點合并在一起。碼樹中的上支路（對應于輸入比特0）用實線表示，下支路(對應于輸入比特1)用虛線表示。網格圖中支路上標注的碼元為輸出比特，自上而下四行節點分別表示a、b、c、d四種狀態。一般情況下應有2N-1

種狀態，從第N節（從左向右計數）開始，網格圖的圖形開始重復。3.狀態圖取出已達到穩定狀態的一節網格，便得到圖7.9（a）所示的狀態圖。再把目前狀態與下行狀態重疊起來，即可得到圖7.9（b）所示的反映狀態轉移圖。圖中兩個自閉合圓環分別表示a-a和d-d狀態轉移。當給定輸入信息序列和起始狀態時，可以用上述三種圖解表示法的任何一種，找到輸出序列和狀態變化路徑。圖7.9（2,1,3）卷積碼的狀態圖

例7.3

設M=［111001010111］，試分別用碼樹圖、理論公式直接計算和碼狀態圖三種方法進行卷積編碼，再對結果進行比較。

例7.3

圖7.7所示的卷積碼編碼器若起始狀態為a，輸入序列為110111001000，求輸出序列和狀態變化路徑。

解

由卷積碼的網格圖表示，找出編碼時網格圖中的路徑，如圖7.11所示，由此可得到輸出序列和狀態變化路徑，示于同一圖中。圖7.11(2,1,3)卷積碼的編碼過程及路徑7.5.3卷積碼的維特比譯碼方法

卷積碼的譯碼方式有三種：維特比譯碼、序列譯碼和門限譯碼。其中維特比譯碼和序列譯碼都是以最大似然譯碼的原理為基礎的，由于篇幅的限制，這里只初步介紹一下維特比譯碼的原理和方法。1.最大似然譯碼原理在一個卷積碼編/譯碼系統中，輸入信息序列M被編碼為序列X，此X序列可以用樹狀或網格圖中某一特定的路徑來表示，假設X序列經過有噪聲的無記憶信道傳送給譯碼器，如圖7.12所示。圖7.11編、譯碼系統模型

假設所有信息序列是等概率出現的，譯碼器在收到Y序列情況下，若

P［Y/X（M′）］≥P［Y/X（M）］M′≠M

（7.33）

對二進制對稱信道來說，若P(1/0)=P(0/1)=P，假設發送序列X的長度為L個符號，并在傳輸過程中發生了e個符號錯誤，即X與Y有e個位置上的符號不同，它們的漢明距為e，則對數似然函數為(7.34)2.維特比譯碼前面我們已經談到，卷積碼網格圖中共有2k(N-1)

種狀態，每個節點（即每個狀態）有2k條支路引入,也有2k條支路引出。為簡便起見，我們討論k=1的情形，從全0狀態起始點開始討論。由網格圖的前N-1條連續支路構成的路徑互不相交，即最初的2N-1

條路徑各不相同，當接收到第N條支路時，每條路徑都有兩條支路延伸到第N級上，而第N級上的每兩條支路又都匯聚在一個節點上。3.維特比解碼法根據前面的原理敘述，維特比解碼法的基本思路是：在接收端碼字序列中先取前面組數等于編碼約束度N的接收碼字序列，與碼網格圖中N級的節點a，b，c，d的可能路徑進行比較，然后按碼距較小原則，每個節點選一條路徑。以后逐次升高級別，逐次篩選路徑，最后保留下來一條路徑，則該路徑的值就是編碼輸出。

為了更具體地闡明維特比譯碼法的過程，這里仍以圖7.7所示的（2，1，3）編碼器所編的卷積碼為例。當發送數據為M=［11010］時，為使全部數據通過編碼器，在后面再加三個“0”，此時數據變為

M=［11010000］，編碼的碼字X為［1101010010110000］若通過信道傳輸后有差錯，則收端的碼字Y序列要變，假若變為［0

101011

01001001

0］則16個碼元中有4個出錯（錯碼下面劃有橫杠）。

維特比解碼法的解碼過程如下：第一步，確定至三級節點a，b，c，d的路徑。由于該卷積碼的編碼約束度為3，因此先選接收碼字序列的前3組，即010101，并用下標表示節點的級別，如a3表示第3級節點a，依次類推。起點至第3級節點的路徑有8條，可算出8條可能路徑的碼距（寫在括號內）為a0→a3：

000000

111011a0→b3：

000011111000

010101(3)

010101(4)

010101(3)

010101(4)a0→c3：

001110

110101a0→d3：

001101

110110010101(4)

010101(1)

010101(2)

010101(3)

每個節點保留一條碼距較小者的路徑，若至同一節點的兩條路徑碼距相等，則任選一條。經過第一步篩選，保留的路徑分別為

a0→a3：000000；a0→b3：000011；

a0→c3：110101；a0→d3：001101

第二步，將級別由第3級增至第4級，每個節點有兩條路徑，又有8條路徑，接收碼用作比較的部分增加一組，變為01010110，則8條路徑的碼距為a0→a3→a4：

00000000

a0→c3→a4：

11010111

01010110（4）

01010110（2）

a0→a3→b4：

00000011

a0→c3→b4：

11010100

01010110（4）

01010110（2）

a0→b3→c4：

00001110

a0→d3→c4：

00110101

01010110（3）01010110（4）

a0→b3→d4：

00001101

a0→d3→d4：

00110110

01010110（5）

01010110（2）第二步篩選出的路徑為

a0→a4：11010111；a0→b4：11010100；

a0→c4：00001110；a0→d4：00110110

第三步，把級數增加至第5級，路徑還有4條主干，8條分支，如圖7.13所示。用于比較的接收碼字序列再增加一組，相應的碼距為a0→a4→a5：

1101011100（3）

a0→c4→a5：

0000111011（4）

0101011010

0101011010a0→a4→b5：

1101011111（3）

a0→c4→b5：

0000111000（4）

0101011010

0101011010a0→b4→c5：

1101010010（2）

a0→d4→c5：

0011011001（4）

0101011010

0101011010a0→b4→d5：

1101010001（4）

a0→d4→d5：

0011011010（2）

0101011010

0101011010圖7.13維特比解碼過程第三步篩選出的路徑為

a0→a5：1101011100；a0→b5：1101011111；

a0→c5：1101010010；a0→d5：0011011010第四步，將級數增至第6級，又有8個分支，相應的碼距為

a0→a5→a6：

110101110000（4）

a0→c5→a6：

110101001011（3）

010101101001

010101101001a0→a5→b6：

110101110011（4）

a0→c5→b6：

110101001000（3）

010101101001

010101101001a0→b5→c6：

110101111110（5）

a0→d5→c6：

001101101001（2）

010101101001

010101101001a0→b5→d6：

110101111101（3）

a0→d5→d6：

001101101010（4）

010101101001

010101101001

第四步篩選出的路徑為為

a0→a6：110101001011；

a0→b6：110101001000；

a0→c6：001101101001；

a0→d6：110101111101

第五步，將級數增至第7級，又有8個分支，相應的碼距為a0→a6→a7：

11010100101100（3）

a0→c6→a7：

00110110100111（4）

01010110100100

01010110100100a0→a6→b7：

11010100101111（5）

a0→c6→b7：

00110110100100（2）

01010110100100

01010110100100a0→b6→c7：

11010100100010（4）

a0→d6→c7：

11010111110101（4）

01010110100100

01010110100100a0→b6→d7：

11010100100001（4）

a0→d6→d7：

11010111110110（4）

01010110100100