通信原理第9章差錯(cuò)控制編碼2023/2/1129.1引言

一般地，信息傳輸涉及可行性編碼、可靠性編碼、有效性編碼和安全性編碼這四個(gè)領(lǐng)域的編碼或信號(hào)設(shè)計(jì)?？煽啃跃幋a常又稱(chēng)為信道編碼，狹義的信道編碼又稱(chēng)為糾錯(cuò)編碼。主要目的是通過(guò)設(shè)計(jì)信號(hào)自身具有的數(shù)據(jù)結(jié)構(gòu)，使信息傳輸?shù)慕邮斩四軌驒z測(cè)或糾正數(shù)據(jù)在傳輸中發(fā)生的部分差錯(cuò)。

差錯(cuò)控制技術(shù)主要有以下四種。（1）檢錯(cuò)重發(fā).2023/2/139.1引言(續(xù))

（2）前向糾錯(cuò)。接收端利用發(fā)送端在發(fā)送碼元序列中加入的差錯(cuò)控制碼元，不但能夠發(fā)現(xiàn)錯(cuò)碼，還能將錯(cuò)碼恢復(fù)其正確取值。（4）檢錯(cuò)刪除。

（3）反饋校驗(yàn)。

四種技術(shù)中，除第（3）種外，其共同特點(diǎn)是都在收端識(shí)別有無(wú)錯(cuò)碼。在發(fā)送端需要在信息碼元序列中增加一些差錯(cuò)控制碼元，它們稱(chēng)為監(jiān)督碼元。這些監(jiān)督碼元和信息碼元之間有確定的關(guān)系，比如某種函數(shù)關(guān)系，使接收端有可能利用這種關(guān)系發(fā)現(xiàn)或糾正可能存在的錯(cuò)碼。2023/2/149.1引言(續(xù))

差錯(cuò)控制編碼常稱(chēng)為糾錯(cuò)編碼。有的編碼方法只能檢錯(cuò)，不能糾錯(cuò)。一般說(shuō)來(lái)，付出的代價(jià)越大，檢（糾）錯(cuò)的能力越強(qiáng)。這里所說(shuō)的代價(jià)，就是指增加的監(jiān)督碼元多少，它通常用多余度來(lái)衡量。設(shè)編碼序列中信息碼元數(shù)量為k，總碼元數(shù)為n，則比值k/n就是碼率；而監(jiān)督碼元數(shù)(n-k)和信息碼元數(shù)k之比為(n-k)/k稱(chēng)為冗余度。從理論上講，差錯(cuò)控制是以降低信息傳輸速率為代價(jià)換取提高傳輸可靠性。2023/2/159.2

差錯(cuò)控制編碼的基本概念

現(xiàn)在先用一個(gè)例子說(shuō)明糾錯(cuò)編碼的基本原理。設(shè)有一種由3位二進(jìn)制數(shù)字構(gòu)成的碼組，它共有8種不同的可能組合。若將其全部用來(lái)表示天氣，則可以表示8種不同的天氣，例如：“000”（云），“001”（晴），“010”（陰），“011”（雪），“100”（雨），“101”（霜），“110”（雹），“111”（霧）。其中任一碼組在傳輸中若發(fā)生一個(gè)或多個(gè)錯(cuò)碼，則將變成另一個(gè)信息碼組。這時(shí)，接收端將無(wú)法發(fā)現(xiàn)錯(cuò)誤。2023/2/169.2

差錯(cuò)控制編碼的基本概念（續(xù)）

若在上述8種碼組中只準(zhǔn)許使用4種來(lái)傳送天氣，例如：“000”表示云，“011”表示晴，“101”表示霜，“110”表示雹。這時(shí)，雖然只能傳送4種不同的天氣，但是接收端卻有可能發(fā)現(xiàn)碼組中的一個(gè)錯(cuò)碼。例如，若“000”（云）中錯(cuò)了一位，則接收碼組將變成“100”或“010”或“001”。這3種碼組都是不準(zhǔn)使用的，稱(chēng)為禁用碼組。接收端在收到禁用碼組時(shí)，就認(rèn)為發(fā)現(xiàn)了錯(cuò)碼。當(dāng)發(fā)生3個(gè)錯(cuò)碼時(shí)，“000”變成了“111”，它也是禁用碼組，故這種編碼也能檢測(cè)3個(gè)錯(cuò)碼。但是這種碼不能發(fā)現(xiàn)一個(gè)碼組中的兩個(gè)錯(cuò)碼，因?yàn)榘l(fā)生兩個(gè)錯(cuò)碼后產(chǎn)生的是許用碼組。2023/2/179.2

差錯(cuò)控制編碼的基本概念（續(xù)）2023/2/1

表9-1信息位和監(jiān)督位的關(guān)系表示的信息信息位監(jiān)督位云000晴011霜101雹110

分組碼一般用符號(hào)(n,k)表示，其中n是碼組的總位數(shù)，又稱(chēng)為碼組的長(zhǎng)度（碼長(zhǎng)），k是碼組中信息碼元的數(shù)目，n-k=r為碼組中的監(jiān)督碼元數(shù)目，或稱(chēng)監(jiān)督位數(shù)目。89.2

差錯(cuò)控制編碼的基本概念（續(xù)）2023/2/1

在分組碼中，把碼組中“1”的個(gè)數(shù)稱(chēng)為碼組的重量，簡(jiǎn)稱(chēng)碼重。把兩個(gè)碼組中對(duì)應(yīng)位上數(shù)字不同的位數(shù)稱(chēng)為碼組的距離，簡(jiǎn)稱(chēng)碼距。碼距又稱(chēng)漢明距離。把某種編碼中各個(gè)碼組之間距離的最小值稱(chēng)為最小碼距。99.2

差錯(cuò)控制編碼的基本概念（續(xù)）2023/2/1

一種編碼的最小碼距d0的大小直接關(guān)系著這種編碼的檢錯(cuò)和糾錯(cuò)能力:（1）為檢測(cè)e個(gè)錯(cuò)碼元，要求最小碼距：

d0

e+1（2）為了糾正t個(gè)錯(cuò)碼元，要求最小碼距：：

d0

2t+1（3）為糾正t個(gè)錯(cuò)碼元，同時(shí)檢測(cè)e個(gè)錯(cuò)碼，要求最小碼距：d0

e+t+1109.2

差錯(cuò)控制編碼的基本概念（續(xù)）2023/2/1119.2

差錯(cuò)控制編碼的基本概念（續(xù)）2023/2/1

一種編碼的最小碼距d0的大小直接關(guān)系著這種編碼的檢錯(cuò)和糾錯(cuò)能力:（1）為檢測(cè)e個(gè)錯(cuò)碼元，要求最小碼距：

d0

e+1（2）為了糾正t個(gè)錯(cuò)碼元，要求最小碼距：：

d0

2t+1（3）為糾正t個(gè)錯(cuò)碼元，同時(shí)檢測(cè)e個(gè)錯(cuò)碼，要求最小碼距：d0

e+t+1129.3

線(xiàn)性分組碼2023/2/1

(n,k)線(xiàn)性分組碼是以n長(zhǎng)碼字的集合構(gòu)成的獨(dú)立糾錯(cuò)碼。其組成由k位信息位的線(xiàn)性組合決定n-k個(gè)監(jiān)督位。

信源編碼的k位信碼集合，共有2k個(gè)信息碼字，在其最低位后加1位奇偶監(jiān)督元，變成n=k+1的奇偶檢驗(yàn)碼，即

由于加入了a0這一位監(jiān)督碼元，新碼字的漢明距離d0=2，則有了至少可以檢出1位錯(cuò)，奇偶檢驗(yàn)碼可以檢測(cè)奇數(shù)位錯(cuò)碼。在接收解碼時(shí)，按上式進(jìn)行模2加計(jì)算，結(jié)果S為139.3

線(xiàn)性分組碼（續(xù)）2023/2/1

由S等于1或0而檢測(cè)出有錯(cuò)及無(wú)錯(cuò)兩種結(jié)果。現(xiàn)將式(9-5)稱(chēng)為監(jiān)督關(guān)系式，S稱(chēng)為校正子(又稱(chēng)校驗(yàn)子、伴隨式)。現(xiàn)在若監(jiān)督位再增加一位，即變成兩位，則能增加一個(gè)類(lèi)似的監(jiān)督關(guān)系式。由于兩個(gè)校正子的可能值有4中組合：00，01，10，11，故能表示4種不同的信息。若用其中1種組合表示無(wú)錯(cuò)，則其余3種組合就有可能用來(lái)指示一個(gè)錯(cuò)碼的3種不同位置。同理，r個(gè)監(jiān)督關(guān)系式能指示1位錯(cuò)碼的(2r

–1)個(gè)可能位置。149.3

線(xiàn)性分組碼（續(xù)）2023/2/1

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

例：設(shè)分組碼(n,k)中k=4，為了糾正1位錯(cuò)碼，要求監(jiān)督位數(shù)r

3。若取r=3，則n=k+r=7。我們用a6a5…a0表示這7個(gè)碼元，用S0、S1和S2表示3個(gè)監(jiān)督關(guān)系式中的校正子，則S0、S1和S2的值與錯(cuò)碼位置的對(duì)應(yīng)關(guān)系可以規(guī)定如表9-2所列。159.3

線(xiàn)性分組碼（續(xù)）2023/2/1

a0

、a3、a4和a6四個(gè)碼元構(gòu)成偶數(shù)監(jiān)督關(guān)系：a1、a3、a5和a6構(gòu)成偶數(shù)監(jiān)督關(guān)系：a2、a4、a5

和a6構(gòu)成偶數(shù)監(jiān)督關(guān)系：169.3

線(xiàn)性分組碼（續(xù)）2023/2/1

在發(fā)送端編碼時(shí)，信息位a6、a5、a4和a3的值決定于輸入信號(hào)，因此它們是隨機(jī)的。監(jiān)督位a2、a1和a0應(yīng)根據(jù)信息位的取值按監(jiān)督關(guān)系來(lái)確定，即信息位和監(jiān)督位應(yīng)使式(9-7)~式(9-9)中S0、S1和S2的值為0（表示編成的碼組中應(yīng)無(wú)錯(cuò)碼）：

179.3

線(xiàn)性分組碼（續(xù)）2023/2/1

接收端收到每個(gè)碼組后，先按式(9-7)~式(9-9)計(jì)算出S0、S1和S2，再查表(9-2)判斷錯(cuò)碼情況。例如，若接收碼組為0000011，按上式(9-7)~式(9-9)計(jì)算可得：S0=0，S2=1，S2=1。由于S2

S1

S0

等于011，故查表(9-2)可知在a3位錯(cuò)。189.3

線(xiàn)性分組碼（續(xù)）2023/2/1199.3

線(xiàn)性分組碼（續(xù)）2023/2/1

把左邊的3×7矩陣的一行和第三行互換，等式仍然成立，即上式可以簡(jiǎn)記為HAT=0T

或AHT=

0209.3

線(xiàn)性分組碼（續(xù)）2023/2/1

矩陣H稱(chēng)為監(jiān)督矩陣(parity-checkmatrix)。H的行數(shù)就是監(jiān)督關(guān)系式的數(shù)目，它等于監(jiān)督位的數(shù)目r。H的每行中“1”的位置表示相應(yīng)碼元之間存在的監(jiān)督關(guān)系。例如，H的第一行1110100表示監(jiān)督位a2是由a6

a5

a4之和決定的。H矩陣可以分成兩部分其中，P為r

k階矩陣，Ir為r

r階單位方陣。219.3

線(xiàn)性分組碼（續(xù)）2023/2/1

將具有[PIr]形式的H矩陣稱(chēng)為典型陣。H矩陣的各行應(yīng)該是線(xiàn)性無(wú)關(guān)的。式(9-11)也可以改寫(xiě)成其中，Q為一個(gè)k

r階矩陣，它為P的轉(zhuǎn)置。229.3

線(xiàn)性分組碼（續(xù)）2023/2/1

將Q的左邊加上1個(gè)kk階單位方陣，就構(gòu)成1個(gè)矩陣GG稱(chēng)為生成矩陣，因?yàn)橛伤梢援a(chǎn)生整個(gè)碼組，即有239.3

線(xiàn)性分組碼（續(xù)）2023/2/1

發(fā)送的碼組就是A，若設(shè)接收碼組為一n列的行矩陣B，即則發(fā)送碼組和接收碼組之差為B–A=E(模2) 若ei

=0，表示該接收碼元無(wú)錯(cuò)；若ei=1，則表示該接收碼元有錯(cuò)?？梢愿膶?xiě)成

B=A+E249.3

線(xiàn)性分組碼（續(xù)）2023/2/1

例如，若發(fā)送碼組A=[1000111]，錯(cuò)碼矩陣E=[0000100]，則接收碼組B=[1000011]。錯(cuò)碼矩陣有時(shí)也稱(chēng)為錯(cuò)誤圖樣。接收端解碼時(shí)，可將接收碼組B代人式(9-14)中計(jì)算。若接收碼組中無(wú)錯(cuò)碼，即E=0,則B=A+E=A。

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

0。在錯(cuò)碼較多，已超過(guò)這種編碼的檢錯(cuò)能力時(shí)，B變?yōu)榱硪辉S用碼組，則式(9-26)仍能成立。這樣的錯(cuò)碼是不可檢測(cè)的。259.3

線(xiàn)性分組碼（續(xù)）2023/2/1

假設(shè)這時(shí)該式(9-26)的右端為S，即

BHT=S將B=A+E代入式(9-24)，可得

S=(A+E)HT=AHT+EHT由式(9-14)可知AHT=0，所以

S=EHT其中，S稱(chēng)為校正子。S能用來(lái)指示錯(cuò)碼的位置。因?yàn)镾和錯(cuò)碼E之間有確定的線(xiàn)性變換關(guān)系。若S和E之間一一對(duì)應(yīng)，則S將能代表錯(cuò)碼的位置。269.3

線(xiàn)性分組碼（續(xù)）2023/2/1

線(xiàn)性碼有一個(gè)重要性質(zhì)，就是它具有封閉性。所謂封閉性，是指一種線(xiàn)性碼中的任意兩個(gè)碼組之和仍為這種碼中的一個(gè)碼組。279.4

循環(huán)碼2023/2/19.4.1循環(huán)碼原理

循環(huán)碼是一種線(xiàn)性碼，具有循環(huán)性。循環(huán)性是指任一碼組循環(huán)一位（即將最右端的一個(gè)碼元移至左端，或反之）以后，仍為該碼中的一個(gè)碼組。289.4.1循環(huán)碼原理（續(xù)）2023/2/1

在代數(shù)編碼理論中，把這樣的碼組中各碼元當(dāng)作是一個(gè)多項(xiàng)式的系數(shù)，即把一個(gè)長(zhǎng)度為n的碼組表示成

這種多項(xiàng)式中，x僅是碼元位置的標(biāo)記。我們并不關(guān)心x的取值。這種多項(xiàng)式有時(shí)稱(chēng)為碼多項(xiàng)式。1.碼多項(xiàng)式的按模運(yùn)算若一個(gè)整數(shù)m可以表示為在模n運(yùn)算下，有m

p(模n)299.4.1循環(huán)碼原理（續(xù)）2023/2/1

在碼多項(xiàng)式運(yùn)算中也有類(lèi)似的按模運(yùn)算。若一任意多項(xiàng)式F(x)被一n次多項(xiàng)式N(x)除，得到商式Q(x)和一個(gè)次數(shù)小于n的余式R(x)，即則寫(xiě)為

這時(shí)，碼多項(xiàng)式系數(shù)仍按模2運(yùn)算，即系數(shù)只取0和1。例309.4.1循環(huán)碼原理（續(xù)）2023/2/1

值得注意的是，由于在模2運(yùn)算中，用加法代替了減法，故余項(xiàng)不是x2–x+1，而是x2+x+1。

在循環(huán)碼中，若T(x)是一個(gè)長(zhǎng)為n的許用碼組，則xiT(x)在按模xn+1運(yùn)算下，也是該編碼中的一個(gè)許用碼組。若則（模(xn+1)）319.4.1循環(huán)碼原理（續(xù)）2023/2/1

式(9-32)中的循環(huán)碼組的一個(gè)許用碼組“1100101”對(duì)應(yīng)的多項(xiàng)式是為其對(duì)應(yīng)的碼組為“0010111”，它正是表9-3中的一個(gè)許用碼組x2T(x)對(duì)應(yīng)的多項(xiàng)式是為2.循環(huán)碼的生成矩陣G

生成矩陣G的每一行都是一個(gè)碼組。若能找到k個(gè)已知碼組，就能構(gòu)成矩陣G。但是，這k個(gè)已知碼組必須是線(xiàn)性不相關(guān)的。329.4.1循環(huán)碼原理（續(xù)）2023/2/1

在循環(huán)碼中，一個(gè)(n,k)碼有2k個(gè)不同的許用碼組。若用g(x)表示r=n–k次多項(xiàng)式，g(x)對(duì)應(yīng)一個(gè)許用碼組，則g(x)，xg(x)，x2g(x)，，xk-1g(x)都是碼組，而且這k個(gè)碼組是線(xiàn)性無(wú)關(guān)的。因此它們可以用來(lái)構(gòu)成此循環(huán)碼的生成矩陣G。g(x)必須是一個(gè)常數(shù)項(xiàng)不為“0”的(n-k)次多項(xiàng)式，而且這個(gè)g(x)還是這種(n,k)碼中次數(shù)為(n–k)的唯一多項(xiàng)式。我們稱(chēng)這唯一的(n–k)次多項(xiàng)式g(x)為碼的生成多項(xiàng)式。一旦確定了g(x)，則整個(gè)(n,k)循環(huán)碼就被確定了。339.4.1循環(huán)碼原理（續(xù)）2023/2/1

循環(huán)碼的生成矩陣G可以表示為

例如，在表9-4中所給出的(7,3)循環(huán)碼中，n=7,k=3,r=n–k=4。由此表可見(jiàn)，唯一的一個(gè)(n–k)=4次碼多項(xiàng)式代表的碼組是“0010111”，與它相對(duì)應(yīng)的碼多項(xiàng)式（即生成多項(xiàng)式）為349.4.1循環(huán)碼原理（續(xù)）2023/2/1

循環(huán)碼的生成矩陣G可以表示為359.4.1循環(huán)碼原理（續(xù)）2023/2/1

上式表明，所有碼多項(xiàng)式T(x)都可被g(x)整除，而且任意一個(gè)次數(shù)不大于(k–1)的多項(xiàng)式乘g(x)都是碼多項(xiàng)式。3.任一(n,k)循環(huán)碼的生成多項(xiàng)式

任一循環(huán)碼多項(xiàng)式T(x)都是g(x)的倍式，故它可以寫(xiě)成T(x)=h(x)g(x)369.4.1循環(huán)碼原理（續(xù)）2023/2/1生成多項(xiàng)式g(x)本身也是一個(gè)碼組，即有T

(x)=g(x)

上式表明，生成多項(xiàng)式g(x)應(yīng)該是(xn+1)的一個(gè)(n-k)次因式。379.4.2循環(huán)碼的編解碼方法2023/2/11.循環(huán)碼的編碼方法

在編碼時(shí)，首先要根據(jù)給定的(n,k)值選定生成多項(xiàng)式g(x)，即從(xn+1)的因子中選一個(gè)(n-k)次多項(xiàng)式作為g(x)。

編碼步驟可以歸納如下：(1)用xn-k乘m(x)。這一運(yùn)算實(shí)際上是在信息碼后附加上(n–k)個(gè)“0”。(2)用g(x)除xn

-km(x)，得到商Q(x)和余式r(x)，即389.4.2循環(huán)碼的編解碼方法（續(xù)）2023/2/1(3)編出的碼組

為2.循環(huán)碼的解碼方法

在接收端可以將接收碼組R(x)用原生成多項(xiàng)式g(x)去除。當(dāng)傳輸中未發(fā)生錯(cuò)誤時(shí)，接收碼組與發(fā)送碼組相同，即R(x)=T(x)，故接收碼組R(x)必定能被g(x)整除；若碼組在傳輸中發(fā)生錯(cuò)誤，則R(x)

T(x)，R(x)被g(x)除時(shí)可能除不盡而有余項(xiàng)。因此，我們就以余項(xiàng)是否為零來(lái)判別接收碼組中有無(wú)錯(cuò)碼。399.4.2循環(huán)碼的編解碼方法（續(xù)）2023/2/1

需要指出，有錯(cuò)碼的接收碼組也有可能g(x)整除。這時(shí)的錯(cuò)碼就不能檢出了。這種錯(cuò)誤稱(chēng)為不可檢錯(cuò)誤。不可檢錯(cuò)誤中的誤碼數(shù)必定超過(guò)了這種編碼的檢錯(cuò)能力。

原則上糾錯(cuò)可按下述步驟進(jìn)行：(1)用生成多項(xiàng)式g(x)除接收碼組R(x)，得出余式r(x)。(2)按余式r(x)，用查表的方法或通過(guò)某種計(jì)算得到錯(cuò)誤圖樣E(x)；例如，通過(guò)計(jì)算校正子S和查類(lèi)似表9-4中的關(guān)系，就可以確定錯(cuò)碼的位置。(3)從R(x)中減去E(x)，便得到已經(jīng)糾正錯(cuò)碼的原發(fā)送碼組T(x)。409.4.3BCH碼2023/2/1BCH碼是一種獲得廣泛應(yīng)用的、能夠在一個(gè)分組中糾正多位錯(cuò)誤的循環(huán)碼，是以3位發(fā)明這種碼的人名(Bose-Chaudhuri-Hocguenghem)命名的。BCH碼可以是二元碼，也可以是多元碼，本節(jié)僅討論二元BCH碼。BCH碼可以分為本原BCH碼和非本原BCH碼兩類(lèi)。它們主要區(qū)別在于，本原BCH碼的生成多項(xiàng)式g(x)中含有最高次數(shù)為m的本原多項(xiàng)式，且碼長(zhǎng)為n=2m

–1，(m

3，為正整數(shù))；非本原BCH碼的生成多項(xiàng)式中不含這種本原多項(xiàng)式，且碼長(zhǎng)n是(2m–1)的一個(gè)因子，即碼長(zhǎng)n一定除得盡2m–1。419.4.3BCH碼2023/2/1

素多項(xiàng)式又叫不可約多項(xiàng)式，是指不能被因式分解為更低冪次的多項(xiàng)式。素多項(xiàng)式是素?cái)?shù)概念在多項(xiàng)式域內(nèi)的推廣。若(xn+1)是可以被次數(shù)為m的素多項(xiàng)式f(x)整除的次數(shù)最小的多項(xiàng)式，則稱(chēng)n為f(x)的周期。進(jìn)一步，如果n=2m

–1，則稱(chēng)素多項(xiàng)式f(x)本原多項(xiàng)式。BCH碼的分組碼長(zhǎng)為BCH碼的信息碼位數(shù)為BCH碼的最小漢明距離為其中，m為正整數(shù)，一般m≥3；t為糾錯(cuò)位數(shù),t<(2m-1)/2。429.4.3BCH碼（續(xù)）2023/2/1BCH碼可以提供靈活的參量選擇，如碼長(zhǎng)n和碼率R=k/n，而且碼長(zhǎng)可高達(dá)上百比特。BCH是目前同樣碼長(zhǎng)及碼率的所有分組碼中的最優(yōu)碼。439.4.3BCH碼（續(xù)）2023/2/1449.4.3BCH碼（續(xù)）2023/2/1

部分二進(jìn)制非本原BCH碼生成多項(xiàng)式系數(shù)如表9-6所示，其中，(23,12)碼被稱(chēng)為戈萊(Golay)碼，它能糾正3位錯(cuò)誤。459.4.3BCH碼（續(xù)）2023/2/1BCH碼的長(zhǎng)度都是奇數(shù)。如果想得到偶數(shù)長(zhǎng)度的BCH碼，并增強(qiáng)檢錯(cuò)能力，可以對(duì)生成多項(xiàng)式再乘上一個(gè)因式(x+1)，得到擴(kuò)展BCH碼(n+1,k)。擴(kuò)展BCH碼不再具有循環(huán)性。

作為BCH碼應(yīng)用實(shí)例，H.320系統(tǒng)的會(huì)議電視利用A律PCM基群，即E1系統(tǒng)(2.048Mb/s)傳輸多媒體信息。當(dāng)信道誤碼率超過(guò)10-6時(shí)，采用BCH(511,493)碼，n-k=r=18，其生成多項(xiàng)式g(x)=

(x9+x4+1)(x9+x6+x5+x3+1)，n=2m–1=

29–1=511,m=9,k=493，t=2。469.

5

卷積碼2023/2/1

卷積碼屬于非分組碼，它是一種小分組(n0,k0)、多碼段相關(guān)、糾錯(cuò)能力較強(qiáng)的前向糾錯(cuò)碼。

卷積碼在編碼時(shí)雖然也是把k個(gè)比特的信息段編成n個(gè)比特的碼組，但是監(jiān)督碼元不僅和當(dāng)前的k比特信息段有關(guān)，而且還同前面m=(N–1)個(gè)信息段有關(guān)。所以一個(gè)碼組中的監(jiān)督碼元監(jiān)督著N個(gè)信息段。通常將N稱(chēng)為編碼約束度，并將nN稱(chēng)為編碼約束長(zhǎng)度。一般說(shuō)來(lái)，對(duì)于卷積碼，k和n的值是比較小的整數(shù)。我們將卷積碼記作(n,k,N)。碼率則仍定義為k/n。479.5.1卷積碼的基本原理2023/2/1489.5.1卷積碼的基本原理（續(xù)）2023/2/1499.5.1卷積碼的基本原理（續(xù)）2023/2/1

設(shè)輸入信息比特序列是…ak-2

ak-1

akak+1…，則當(dāng)輸入ak時(shí)，此編碼器輸出3比特bi、ci和di，輸入和輸出的關(guān)系為

在編碼輸出中，信息位在前，監(jiān)督位在后，如圖9-5所示。這里的編碼約束長(zhǎng)度nN=9。509.5.1卷積碼的基本原理（續(xù)）2023/2/1519.5.2卷積碼的代數(shù)描述2023/2/11.監(jiān)督矩陣H

以圖9-4所示的卷積碼為例。假設(shè)最先1個(gè)信息位ak進(jìn)入編碼器之前，各級(jí)移存器都處于“0”狀態(tài)，則監(jiān)督位bi、ci、di與信息位之間的關(guān)系可以為529.5.2卷積碼的代數(shù)描述(續(xù))2023/2/1539.5.2卷積碼的代數(shù)描述(續(xù))2023/2/1549.5.2卷積碼的代數(shù)描述(續(xù))2023/2/1559.5.2卷積碼的代數(shù)描述(續(xù))2023/2/1截短監(jiān)督矩陣H1可以寫(xiě)成如下形式：其中，I2

為2階單位方陣；Pi為21階矩陣，i=1,2,3；O2為2階全零方陣。569.5.2卷積碼的代數(shù)描述(續(xù))2023/2/1卷積碼的截短監(jiān)督矩陣的形式為其中，In-k為(n–k)階單位方陣；Pi為(n–k)k階矩陣；On-k為(n–k)階全零方陣。有時(shí)還將H1的末行稱(chēng)為基本監(jiān)督矩陣h=[PN

On-k

PN-1

On-k

PN-2

On-k

P1

In-k]。

579.5.2卷積碼的代數(shù)描述(續(xù))2023/2/12.生成矩陣G

以圖9-4所示的(3,1,3)卷積碼為例，輸出碼元序列為[b1c1d1b2c2d2b3c3d3b4c4d4

……]=

[a1a1a1a2(a1+a2)(a1+a2)a3(a2+a3)

(a1+a2+a3)a4(a3+a4)

(a2+a3+a4)

]

589.5.2卷積碼的代數(shù)描述(續(xù))2023/2/1

599.5.2卷積碼的代數(shù)描述(續(xù))2023/2/1

卷積碼的截短生成矩陣G1具有如下形式：其中,Ik為k階單位方陣；Qi為(n–k)k階矩陣；Ok為k階全零方陣。

將上式中矩陣第一行稱(chēng)為基本生成矩陣

g=[Ik

Q1

Ok

Q2

Ok

Q3Ok

QN]609.5.3卷積碼的解碼2023/2/1

卷積碼的解碼方法有代數(shù)解碼和概率解碼兩類(lèi)。代數(shù)解碼利用編碼本身的代數(shù)結(jié)構(gòu)進(jìn)行解碼，不考慮信道的統(tǒng)計(jì)特性。卷積碼代數(shù)解碼的最主要一種方法是大數(shù)邏輯解碼，大數(shù)邏輯解碼又稱(chēng)門(mén)限解碼。大數(shù)邏輯解碼對(duì)于約束長(zhǎng)度較短的卷積碼最為有效，而且設(shè)備較簡(jiǎn)單。概率解碼又稱(chēng)最大似然解碼，它基于信道的統(tǒng)計(jì)特性和卷積碼的特點(diǎn)進(jìn)行計(jì)算。沃克拉夫特提出的序貫解碼和維特比(Viterbi)提出的Viterbi譯碼都是典型的概率解碼方法。619.5.3卷積碼的解碼(續(xù))2023/2/1

1.大數(shù)邏輯解碼

卷

積碼的大數(shù)邏輯解碼的一般工作原理如圖9-7所示。在圖9-7中，首先將接收信息位暫存于移存器中；然后，根據(jù)接收碼元的信息位和監(jiān)督位計(jì)算校正子和正交校驗(yàn)式，比較正交校驗(yàn)式不等于零的個(gè)數(shù)是否大于1，如果大于1，輸出高電平，否則輸出低電平；最后，利用一個(gè)模2加電路糾正錯(cuò)誤碼元，并反饋回信息位移位寄存器，糾正其中相應(yīng)的信息位。629.5.3卷積碼的解碼(續(xù))2023/2/1

639.5.3卷積碼的解碼(續(xù))2023/2/1

錯(cuò)碼檢測(cè)器采用二進(jìn)制碼的大數(shù)邏輯解碼算法。大數(shù)邏輯解碼算法的基本原理是，利用一組“正交”校驗(yàn)式進(jìn)行計(jì)算。這里的“正交”是指，若被校驗(yàn)的那個(gè)信息位出現(xiàn)在每一個(gè)校驗(yàn)式中，而其它的信息位至多在一個(gè)校驗(yàn)式中出現(xiàn)，則稱(chēng)這組校驗(yàn)式為正交校驗(yàn)式。可以根據(jù)被錯(cuò)碼影響了的校驗(yàn)式數(shù)目在校驗(yàn)式組中是否占多數(shù)來(lái)判斷該信息位是否錯(cuò)了。649.5.3卷積碼的解碼(續(xù))2023/2/1

在圖9-4所示的(3,1,3)卷積碼編碼器中，監(jiān)督位和信息位的關(guān)系為ci=ai+ai-1，di=ai+ai-1+ai-2。當(dāng)輸入序列為a1

a2

a3

a4

時(shí)，監(jiān)督位為 c1=a1 d1=a1 c2=a2+a1 d2=a2+a1 c3=a3+a2 d3=a3+a2+a1 c4=a4+a3 d4=a4+a3+a2 …659.5.3卷積碼的解碼(續(xù))2023/2/1

監(jiān)督關(guān)系式為 S1=a1+c1 S2=a1+d1 S3=a1+a2+c2 S4=a1+a2+d2 S5=a2+a3+c3 S6=a1+a2+a3+d3 S7=a3+a4+c4 S8=a2+a3+a4+d4 S9=a4+a5+c5 S10=a3+a4+a5+d5 S11=a5+a6+c6 S12=a4+a5+a6+d6

……669.5.3卷積碼的解碼(續(xù))2023/2/1

Si被稱(chēng)為校正子，經(jīng)過(guò)簡(jiǎn)單線(xiàn)性變換后，可以得出如下正交校驗(yàn)式組：

只有信息位a3出現(xiàn)在每個(gè)校驗(yàn)式中，監(jiān)督位和其它信息位最多只出現(xiàn)一次。因此，在接收端解碼時(shí)，考察a2~a4,c3~c5,d5

共7個(gè)碼元，在一位出錯(cuò)的情況下，僅當(dāng)a3出錯(cuò)時(shí)，上式中才可能有3個(gè)校驗(yàn)式等于“1”，而其它比特出錯(cuò)時(shí)，只有一個(gè)校驗(yàn)式等于“1”。根據(jù)校驗(yàn)式等于“1”的數(shù)量，就能判斷是否a3出錯(cuò)。679.5.3卷積碼的解碼(續(xù))2023/2/1

689.5.3卷積碼的解碼(續(xù))2023/2/1

2.卷積碼的幾何表述

卷積碼的維特比解碼算法是基于卷積碼的幾何表述之上的。所以在介紹卷積碼的維特比解碼算法之前，先介紹卷積碼的三種幾何表述方法。(1)碼樹(shù)圖699.5.3卷積碼的解碼(續(xù))2023/2/1

709.5.3卷積碼的解碼(續(xù))2023/2/1

由此碼樹(shù)圖還可以看到，從第4級(jí)支路開(kāi)始，碼樹(shù)的上半部和下半部相同。這意味著，從第4個(gè)輸入信息位開(kāi)始，輸出碼元已經(jīng)與第1位輸入信息位無(wú)關(guān)，即此編碼器的約束度N=3。

碼樹(shù)圖還可以用于解碼。在解碼時(shí)，按照漢明距離最小的準(zhǔn)則沿碼樹(shù)進(jìn)行搜索。例如，若接收碼元序列為111010001111B，則它和序列111011001111B的漢明距離僅為1，是最短的。這樣，就判斷它的正確序列為111011001111B，對(duì)照碼樹(shù)圖，得到糾正的輸出信息序列為1001B。719.5.3卷積碼的解碼(續(xù))2023/2/1

(2)狀態(tài)轉(zhuǎn)換圖

在圖9-9中，三個(gè)寄存器的狀態(tài)組合aiai-1ai-2有000、001、010、011、100、101、110和111八種二進(jìn)制組合。如果分別把它們用s0、s1、s2、s3、s4、s5、s6和s7表示，則可以如圖9-10所示的狀態(tài)轉(zhuǎn)換圖。729.5.3卷積碼的解碼(續(xù))2023/2/1

739.5.3卷積碼的解碼(續(xù))2023/2/1

(3)網(wǎng)格圖

將狀態(tài)圖在時(shí)間上展開(kāi)，可以得到網(wǎng)格圖，如圖9-11所示，用虛線(xiàn)表示輸入信息位為“0”時(shí)狀態(tài)轉(zhuǎn)變的路線(xiàn)；實(shí)線(xiàn)表示輸入信息位為“1”時(shí)狀態(tài)轉(zhuǎn)變的路線(xiàn)?？梢钥闯觯诘?時(shí)隙以后的網(wǎng)格圖形完全是重復(fù)第3時(shí)隙的圖形。這也反映了此(3,1,3)卷積碼的約束長(zhǎng)度為3。749.5.3卷積碼的解碼(續(xù))2023/2/1

759.5.3卷積碼的解碼(續(xù))2023/2/1

769.5.3卷積碼的解碼(續(xù))2023/2/1

3.維特比解碼算法

維特比解碼算法是維特比于1967年提出的。由于這種解碼方法比較簡(jiǎn)單，計(jì)算