《數(shù)字通信系統(tǒng)》課件第7章 糾錯(cuò)編碼

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

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

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

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

圖7.2（a）表示停發(fā)等候重發(fā)系統(tǒng)的發(fā)送端、接收端的信號(hào)傳遞過程。發(fā)送端在TW時(shí)間內(nèi)送出一個(gè)碼組給接收端，接收端收到后經(jīng)檢測(cè)若未發(fā)現(xiàn)錯(cuò)誤，則發(fā)回一個(gè)認(rèn)可信號(hào)（ACK）給發(fā)送端，發(fā)送端收到ACK信號(hào)后再發(fā)出下一個(gè)碼組。返回重發(fā)系統(tǒng)如圖7.2（b）所示。7.1.2前向糾錯(cuò)在前向糾錯(cuò)系統(tǒng)中，發(fā)送端經(jīng)編碼發(fā)出能夠糾正錯(cuò)誤的碼，接收端收到這些碼組后，通過譯碼能自動(dòng)發(fā)現(xiàn)并糾正傳輸中的錯(cuò)誤。前向糾錯(cuò)方式不需要反饋信道，特別適合于只能提供單向信道的場(chǎng)合。由于該系統(tǒng)能自動(dòng)糾錯(cuò)，不要求檢錯(cuò)重發(fā)，因而具有延時(shí)小，實(shí)時(shí)性好等特點(diǎn)。7.1.3混合糾錯(cuò)混合糾錯(cuò)方式是前向糾錯(cuò)方式和檢錯(cuò)重發(fā)方式的結(jié)合。在這種系統(tǒng)中，發(fā)送端不但有糾正錯(cuò)誤的能力，而且對(duì)超出糾錯(cuò)能力的錯(cuò)誤有檢測(cè)能力。遇到后一種情況時(shí)，通過反饋信道要求發(fā)送端重發(fā)一遍?；旌霞m錯(cuò)方式在實(shí)時(shí)性和譯碼復(fù)雜性方面是前向糾錯(cuò)和檢錯(cuò)重發(fā)方式的折衷。7.2糾錯(cuò)編碼的基本原理

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

000=晴

011=云

101=陰

110=雨(7.1)

分組碼一般用符號(hào)（n，k）表示，其中k是每組二進(jìn)制信息碼元的數(shù)目，n是編碼組的總位數(shù)，又稱為碼組長(zhǎng)度（碼長(zhǎng)），n-k=r為每個(gè)碼組中的監(jiān)督碼元數(shù)目或稱監(jiān)督位數(shù)目。通常，將分組碼規(guī)定為具有如圖7.3所示的結(jié)構(gòu)。圖中前面k位（an-1

…ar）為信息位，后面附加r個(gè)監(jiān)督位（ar-1

…a0）。在式（7.1）的分組碼中，n=3，k=2，r=1。表7.1圖7.3分組碼的結(jié)構(gòu)

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

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

(1）為檢測(cè)e個(gè)錯(cuò)碼，要求最小碼距為

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

位差錯(cuò)的能力。因?yàn)楫?dāng)編碼之間最小碼距為d0,比錯(cuò)碼位數(shù)大于1時(shí),只要編碼中出現(xiàn)的錯(cuò)碼位數(shù)不超過e,則都不可能變成另一個(gè)允許使用的編碼,因此接收端能發(fā)現(xiàn)這樣的差錯(cuò)(2)若編碼組中編碼之間最小碼距滿足:

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

位差錯(cuò)的能力。因?yàn)楫?dāng)碼組中允許使用的編碼發(fā)生t

位差錯(cuò)時(shí),形成的錯(cuò)誤編碼與另一個(gè)允許使用的編碼錯(cuò)t

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

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

位差錯(cuò)并檢測(cè)e

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

位內(nèi),則對(duì)其進(jìn)行糾錯(cuò);若接收到的編碼與某一允許的編碼之間的距離超過t,則只能對(duì)其進(jìn)行檢錯(cuò),檢錯(cuò)能力范圍為e

。當(dāng)某一允許使用的編碼出現(xiàn)e位差錯(cuò)后與另一個(gè)允許使用的編碼間距離至少為t-1,否則會(huì)進(jìn)入另一個(gè)允許使用的編碼的糾錯(cuò)范圍而被錯(cuò)糾為另一編碼。

假設(shè)在隨機(jī)信道中發(fā)送“0”時(shí)的錯(cuò)誤概率和發(fā)送“1”時(shí)的相等，都等于p，且p<<1,容易證明，在碼長(zhǎng)為n的碼組中恰好發(fā)生r個(gè)錯(cuò)碼的概率為

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

一般情況下奇偶監(jiān)督碼的編碼規(guī)則是：首先將要傳輸?shù)男畔⒎殖山M，然后將各位二元信息及附加監(jiān)督位用模2和相加，選擇正確的監(jiān)督位，保證模2和的結(jié)果為0（偶校驗(yàn)）或1（奇校驗(yàn)）。這種監(jiān)督關(guān)系可以用公式表示。設(shè)碼組長(zhǎng)度為n，表示為（an-1an-2

an-3

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

按式（7.6a）條件構(gòu)成的偶數(shù)監(jiān)督碼由于使用了1位監(jiān)督位a0，因此它就能和信息位an-1

…a1一起構(gòu)成一個(gè)代數(shù)式，如式（7.6a）所示。在接收端解碼時(shí)，實(shí)際上就是計(jì)算（7.7）

一般說來，若碼長(zhǎng)為n，信息位數(shù)為k，則監(jiān)督位數(shù)r=n-k。如果希望用r個(gè)監(jiān)督位構(gòu)造出r個(gè)監(jiān)督關(guān)系式來指示一位錯(cuò)碼的n種可能位置，則要求

2r-1≥n

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

下面我們通過一個(gè)例子來說明如何構(gòu)成這些監(jiān)督關(guān)系式。表7.3

由表中規(guī)定可見，僅當(dāng)1個(gè)錯(cuò)碼位置在a2、a4、a5或a6時(shí)，校正子S1為1；否則S1為0。這就意味著a2、a4、a5和a6

4個(gè)碼元構(gòu)成的偶數(shù)監(jiān)督關(guān)系為

S1=a6⊕a5⊕a4⊕a2

（7.9）同理，a1、a3、a5和a6構(gòu)成的偶數(shù)監(jiān)督關(guān)系為

S2=a6⊕a5⊕a3⊕a1

（7.10）

以及a0、a3、a4和a6構(gòu)成的偶數(shù)監(jiān)督關(guān)系為

S3=a6⊕a4⊕a3⊕a0

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

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

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

，S3=1。由于S1S2S3等于011，故根據(jù)表7.3可知在a3位有一錯(cuò)碼。7.4.2線性分組碼的矩陣描述現(xiàn)在我們?cè)賮碛懻摼€性分組碼的一般原理。上面已經(jīng)提到，線性碼是指信息位和監(jiān)督位滿足一組線性方程的碼。式（7.12）就是這樣一組線性方程的例子?，F(xiàn)在將它改寫成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)

注：

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

H·AT=OT

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

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

式中，

Q為k×r階矩陣，它為

P的轉(zhuǎn)置，即

Q=PT

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

Q就能產(chǎn)生出監(jiān)督位。我們將

Q的左邊加上一個(gè)k×k階單位方陣就構(gòu)成一矩陣

G

(7.21)

式中，G稱為生成矩陣，因?yàn)橛伤梢援a(chǎn)生整個(gè)碼組，即有［a6a5a4a3a2a1a0］=［a6a5a4a3］·G

（7.22）或者

A=［a6a5a4a3］·G

（7.23）與H矩陣相似,我們也要求G矩陣的各行是線性無關(guān)的。因?yàn)橛墒?7.23)可以看出,任意碼組A都是G的各行的線性組合。G

共有k

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

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

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

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

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

B，即

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

B-A=E

（模2）（7.25）式中，

E是傳輸中產(chǎn)生的錯(cuò)碼行矩陣，其值為

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

因此，若en

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

也可以改寫成

B=A+E

（7.27）例如，若發(fā)送碼組A=［1000111］，錯(cuò)碼矩陣

E=［0000100］，則接收碼組

B=［1000011］

。錯(cuò)碼矩陣有時(shí)也稱為錯(cuò)誤圖樣。

接收端譯碼時(shí)，可將接收碼組

B代入式（7.16）中計(jì)算。若接收碼組中無錯(cuò)碼，即

E=0

，則

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

B·HT=0（7.28）

當(dāng)接收碼組有錯(cuò)時(shí)，

E≠0，將

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

B變?yōu)榱硪辉S用碼組，則式（7.28）仍能成立。這樣的錯(cuò)碼是不可檢測(cè)的。在未超過檢錯(cuò)能力時(shí)，式(7.28)不成立，即其右端不等于零。假設(shè)這時(shí)式（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卷積碼的結(jié)構(gòu)及描述

卷積碼編碼器的一般形式如圖7.5所示，它包括：一個(gè)由N段組成的輸入移位寄存器，每段有k級(jí)，共nN位寄存器；一組n個(gè)模2和相加器；一個(gè)由n級(jí)組成的輸出移位寄存器。圖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)

現(xiàn)若按（2，1，3）卷積碼編碼器進(jìn)行編碼，當(dāng)M=［11010］時(shí)，由式（7.31）可知：

x1j

=［10001100］

x2j

=［11100100］

則輸出序列為

X={1101010010110000}1.樹狀圖如圖7.6所示，在（2,1,3）卷積碼編碼器中，輸出移位寄存器用轉(zhuǎn)換開關(guān)代替，每輸入一個(gè)信息比特，經(jīng)編碼產(chǎn)生2個(gè)輸出比特。假設(shè)移位寄存器的起始狀態(tài)為全0，則當(dāng)?shù)谝粋€(gè)輸入比特為0時(shí)，輸出比特為00；當(dāng)?shù)谝粋€(gè)輸入比特為1時(shí)，輸出比特為11。隨著第二個(gè)比特的輸入，第一個(gè)比特右移1位，此時(shí)輸出比特同時(shí)受當(dāng)前輸入比特和前一個(gè)輸入比特的影響。第三個(gè)比特輸入時(shí)，第一、二個(gè)比特分別右移1位，同時(shí)輸出兩個(gè)由這3位移位寄存器存儲(chǔ)內(nèi)容所共同決定的比特。圖7.7（2,1,3）卷積碼的樹狀圖表示

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

x1j=［00000000］

x2j

=［00000000］

X=［0000000000000000］卷積碼編碼器輸出的碼對(duì)應(yīng)碼樹中的每個(gè)分支的上支，用圖7.7中上支所示的虛線表示。

若M=［11111］，則有

x1j

=［10111010］

x2j

=［11000110］

X=［1101101010011100］卷積碼對(duì)應(yīng)碼樹每個(gè)分支的下支，用圖7.8中下支所示的虛線表示。若M=［0101］，則有

x1j=［0110110］

x2j

=［0100010］

X=［00111000101100］

例7.2

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

解

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

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

走下支

始點(diǎn)a

路徑值11終點(diǎn)b

來0

走上支

始點(diǎn)b

路徑值10

終點(diǎn)c

來1

走下支

始點(diǎn)c

路徑值00

終點(diǎn)b

來1

走下支

始點(diǎn)b

路徑值01

終點(diǎn)d

來0

走上支

始點(diǎn)d

路徑值01

終點(diǎn)c

來1

走下支

始點(diǎn)c

路徑值00

終點(diǎn)b

來0

走上支

始點(diǎn)b

路徑值10

終點(diǎn)c

來0

走上支

始點(diǎn)c

路徑值11

終點(diǎn)a

來0

走上支

始點(diǎn)a

路徑值00

終點(diǎn)a卷積碼編碼結(jié)果X就是把路徑按先后次序?qū)懗?，即得X=［111000010100101100］2.網(wǎng)格圖按照碼樹中觀察到的重復(fù)性，得到一種更為緊湊的圖形表示，即網(wǎng)格圖，如圖7.9所示。

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

在網(wǎng)格圖中，把碼樹中具有相同狀態(tài)的節(jié)點(diǎn)合并在一起。碼樹中的上支路（對(duì)應(yīng)于輸入比特0）用實(shí)線表示，下支路(對(duì)應(yīng)于輸入比特1)用虛線表示。網(wǎng)格圖中支路上標(biāo)注的碼元為輸出比特，自上而下四行節(jié)點(diǎn)分別表示a、b、c、d四種狀態(tài)。一般情況下應(yīng)有2N-1

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

例7.3

設(shè)M=［111001010111］，試分別用碼樹圖、理論公式直接計(jì)算和碼狀態(tài)圖三種方法進(jìn)行卷積編碼，再對(duì)結(jié)果進(jìn)行比較。

例7.3

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

解

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

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

假設(shè)所有信息序列是等概率出現(xiàn)的，譯碼器在收到Y(jié)序列情況下，若

P［Y/X（M′）］≥P［Y/X（M）］M′≠M(fèi)

（7.33）

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

種狀態(tài)，每個(gè)節(jié)點(diǎn)（即每個(gè)狀態(tài)）有2k條支路引入,也有2k條支路引出。為簡(jiǎn)便起見，我們討論k=1的情形，從全0狀態(tài)起始點(diǎn)開始討論。由網(wǎng)格圖的前N-1條連續(xù)支路構(gòu)成的路徑互不相交，即最初的2N-1

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

為了更具體地闡明維特比譯碼法的過程，這里仍以圖7.7所示的（2，1，3）編碼器所編的卷積碼為例。當(dāng)發(fā)送數(shù)據(jù)為M=［11010］時(shí)，為使全部數(shù)據(jù)通過編碼器，在后面再加三個(gè)“0”，此時(shí)數(shù)據(jù)變?yōu)?/p>

M=［11010000］，編碼的碼字X為［1101010010110000］若通過信道傳輸后有差錯(cuò)，則收端的碼字Y序列要變，假若變?yōu)椋?

101011

01001001

0］則16個(gè)碼元中有4個(gè)出錯(cuò)（錯(cuò)碼下面劃有橫杠）。

維特比解碼法的解碼過程如下：第一步，確定至三級(jí)節(jié)點(diǎn)a，b，c，d的路徑。由于該卷積碼的編碼約束度為3，因此先選接收碼字序列的前3組，即010101，并用下標(biāo)表示節(jié)點(diǎn)的級(jí)別，如a3表示第3級(jí)節(jié)點(diǎn)a，依次類推。起點(diǎn)至第3級(jí)節(jié)點(diǎn)的路徑有8條，可算出8條可能路徑的碼距（寫在括號(hào)內(nèi)）為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)

每個(gè)節(jié)點(diǎn)保留一條碼距較小者的路徑，若至同一節(jié)點(diǎn)的兩條路徑碼距相等，則任選一條。經(jīng)過第一步篩選，保留的路徑分別為

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

a0→c3：110101；a0→d3：001101

第二步，將級(jí)別由第3級(jí)增至第4級(jí)，每個(gè)節(jié)點(diǎn)有兩條路徑，又有8條路徑，接收碼用作比較的部分增加一組，變?yōu)?1010110，則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

第三步，把級(jí)數(shù)增加至第5級(jí)，路徑還有4條主干，8條分支，如圖7.13所示。用于比較的接收碼字序列再增加一組，相應(yīng)的碼距為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第四步，將級(jí)數(shù)增至第6級(jí)，又有8個(gè)分支，相應(yīng)的碼距為

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

第五步，將級(jí)數(shù)增至第7級(jí)，又有8個(gè)分支，相應(yīng)的碼距為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