通信原理(陳啟興) 第9章 差錯控制編碼v3

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

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

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

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

（3）反饋校驗。

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

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

差錯控制編碼的基本概念

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

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

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

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

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

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

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

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

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

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

d0

e+1（2）為了糾正t個錯碼元，要求最小碼距：：

d0

2t+1（3）為糾正t個錯碼元，同時檢測e個錯碼，要求最小碼距：d0

e+t+1109.2

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

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

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

d0

e+1（2）為了糾正t個錯碼元，要求最小碼距：：

d0

2t+1（3）為糾正t個錯碼元，同時檢測e個錯碼，要求最小碼距：d0

e+t+1129.3

線性分組碼2023/2/1

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

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

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

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

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

–1)個可能位置。149.3

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

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

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

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

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

a0

、a3、a4和a6四個碼元構(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

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

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

179.3

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

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

S1

S0

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

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

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

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

或AHT=

0209.3

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

矩陣H稱為監(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

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

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

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

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

將Q的左邊加上1個kk階單位方陣，就構(gòu)成1個矩陣GG稱為生成矩陣，因為由它可以產(chǎn)生整個碼組，即有239.3

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

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

=0，表示該接收碼元無錯；若ei=1，則表示該接收碼元有錯?？梢愿膶懗?/p>

B=A+E249.3

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

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

當(dāng)接收碼組有錯時，E

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

在循環(huán)碼中，一個(n,k)碼有2k個不同的許用碼組。若用g(x)表示r=n–k次多項式，g(x)對應(yīng)一個許用碼組，則g(x)，xg(x)，x2g(x)，，xk-1g(x)都是碼組，而且這k個碼組是線性無關(guān)的。因此它們可以用來構(gòu)成此循環(huán)碼的生成矩陣G。g(x)必須是一個常數(shù)項不為“0”的(n-k)次多項式，而且這個g(x)還是這種(n,k)碼中次數(shù)為(n–k)的唯一多項式。我們稱這唯一的(n–k)次多項式g(x)為碼的生成多項式。一旦確定了g(x)，則整個(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。由此表可見，唯一的一個(n–k)=4次碼多項式代表的碼組是“0010111”，與它相對應(yīng)的碼多項式（即生成多項式）為349.4.1循環(huán)碼原理（續(xù)）2023/2/1

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

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

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

(x)=g(x)

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

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

編碼步驟可以歸納如下：(1)用xn-k乘m(x)。這一運算實際上是在信息碼后附加上(n–k)個“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)用原生成多項式g(x)去除。當(dāng)傳輸中未發(fā)生錯誤時，接收碼組與發(fā)送碼組相同，即R(x)=T(x)，故接收碼組R(x)必定能被g(x)整除；若碼組在傳輸中發(fā)生錯誤，則R(x)

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

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

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

–1，(m

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

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

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

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

作為BCH碼應(yīng)用實例，H.320系統(tǒng)的會議電視利用A律PCM基群，即E1系統(tǒng)(2.048Mb/s)傳輸多媒體信息。當(dāng)信道誤碼率超過10-6時，采用BCH(511,493)碼，n-k=r=18，其生成多項式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)、糾錯能力較強的前向糾錯碼。

卷積碼在編碼時雖然也是把k個比特的信息段編成n個比特的碼組，但是監(jiān)督碼元不僅和當(dāng)前的k比特信息段有關(guān)，而且還同前面m=(N–1)個信息段有關(guān)。所以一個碼組中的監(jiān)督碼元監(jiān)督著N個信息段。通常將N稱為編碼約束度，并將nN稱為編碼約束長度。一般說來，對于卷積碼，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時，此編碼器輸出3比特bi、ci和di，輸入和輸出的關(guān)系為

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

以圖9-4所示的卷積碼為例。假設(shè)最先1個信息位ak進入編碼器之前，各級移存器都處于“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可以寫成如下形式：其中，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)階全零方陣。有時還將H1的末行稱為基本監(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階全零方陣。

將上式中矩陣第一行稱為基本生成矩陣

g=[Ik

Q1

Ok

Q2

Ok

Q3Ok

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

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

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

卷

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

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

錯碼檢測器采用二進制碼的大數(shù)邏輯解碼算法。大數(shù)邏輯解碼算法的基本原理是，利用一組“正交”校驗式進行計算。這里的“正交”是指，若被校驗的那個信息位出現(xiàn)在每一個校驗式中，而其它的信息位至多在一個校驗式中出現(xiàn)，則稱這組校驗式為正交校驗式?？梢愿鶕?jù)被錯碼影響了的校驗式數(shù)目在校驗式組中是否占多數(shù)來判斷該信息位是否錯了。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

時，監(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被稱為校正子，經(jīng)過簡單線性變換后，可以得出如下正交校驗式組：

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

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

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

2.卷積碼的幾何表述

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

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

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

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

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

在圖9-9中，三個寄存器的狀態(tài)組合aiai-1ai-2有000、001、010、011、100、101、110和111八種二進制組合。如果分別把它們用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)圖在時間上展開，可以得到網(wǎng)格圖，如圖9-11所示，用虛線表示輸入信息位為“0”時狀態(tài)轉(zhuǎn)變的路線；實線表示輸入信息位為“1”時狀態(tài)轉(zhuǎn)變的路線?？梢钥闯觯诘?時隙以后的網(wǎng)格圖形完全是重復(fù)第3時隙的圖形。這也反映了此(3,1,3)卷積碼的約束長度為3。749.5.3卷積碼的解碼(續(xù))2023/2/1

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

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

3.維特比解碼算法

維特比解碼算法是維特比于1967年提出的。由于這種解碼方法比較簡單，計算