數(shù)字通信第10章差錯控制編碼課件

第10章差錯控制編碼

10.1概述10.2常用的幾種簡單分組碼10.3線性分組碼10.4循環(huán)碼10.5卷積碼*10.6網(wǎng)格編碼調(diào)制第10章差錯控制編碼10.1概述10.1概述

10.1.1信道編碼在數(shù)字通信中，根據(jù)不同的目的，編碼可分為信源編碼和信道編碼。信源編碼是為了提高數(shù)字信號的有效性以及為了使模擬信號數(shù)字化而采取的編碼。信道編碼是為了降低誤碼率，提高數(shù)字通信的可靠性而采取的編碼。數(shù)字信號在傳輸過程中，加性噪聲、碼間串?dāng)_等都會產(chǎn)生誤碼。為了提高系統(tǒng)的抗干擾性能，可以加大發(fā)射功率，降低接收設(shè)備本身的噪聲，以及合理選擇調(diào)制、解調(diào)方法等。此外，還可以采用信道編碼技術(shù)。10.1概述10.1.1信道編碼10.1.2差錯控制方式

圖10-1差錯控制方式

10.1.2差錯控制方式圖10-1差錯控制方式1.檢錯重發(fā)方式檢錯重發(fā)又稱自動請求重傳方式，記作ARQ(AutomaticRepeatRequest)。由發(fā)端送出能夠發(fā)現(xiàn)錯誤的碼，由收端判決傳輸中無錯誤產(chǎn)生，如果發(fā)現(xiàn)錯誤，則通過反向信道把這一判決結(jié)果反饋給發(fā)端，然后，發(fā)端把收端認(rèn)為錯誤的信息再次重發(fā)，從而達到正確傳輸?shù)哪康摹Ｆ涮攸c是需要反饋信道，譯碼設(shè)備簡單，對突發(fā)錯誤和信道干擾較嚴(yán)重時有效，但實時性差，主要在計算機數(shù)據(jù)通信中得到應(yīng)用。1.檢錯重發(fā)方式2.前向糾錯方式前向糾錯方式記作FEC(ForwordErrorCorrection)。發(fā)端發(fā)送能夠糾正錯誤的碼，收端收到信碼后自動地糾正傳輸中的錯誤。其特點是單向傳輸，實時性好，但譯碼設(shè)備較復(fù)雜。

2.前向糾錯方式3.混合糾錯方式混合糾錯方式記作HEC(HybridErrorCorrection)是FEC和ARQ方式的結(jié)合。發(fā)端發(fā)送具有自動糾錯同時又具有檢錯能力的碼。收端收到碼后，檢查差錯情況，如果錯誤在碼的糾錯能力范圍以內(nèi)，則自動糾錯，如果超過了碼的糾錯能力，但能檢測出來，則經(jīng)過反饋信道請求發(fā)端重發(fā)。這種方式具有自動糾錯和檢錯重發(fā)的優(yōu)點，可達到較低的誤碼率，因此，近年來得到廣泛應(yīng)用。3.混合糾錯方式

另外，按照噪聲或干擾的變化規(guī)律，可把信道分為三類：隨機信道、突發(fā)信道和混合信道。恒參高斯白噪聲信道是典型的隨機信道，其中差錯的出現(xiàn)是隨機的，而且錯誤之間是統(tǒng)計獨立的。具有脈沖干擾的信道是典型的突發(fā)信道，錯誤是成串成群出現(xiàn)的，即在短時間內(nèi)出現(xiàn)大量錯誤。短波信道和對流層散射信道是混合信道的典型例子，隨機錯誤和成串錯誤都占有相當(dāng)比例。對于不同類型的信道，應(yīng)采用不同的差錯控制方式。另外，按照噪聲或干擾的變化規(guī)律，可把信道分為10.1.3糾錯碼的分類(1)根據(jù)糾錯碼各碼組信息元和監(jiān)督元的函數(shù)關(guān)系，可分為線性碼和非線性碼。如果函數(shù)關(guān)系是線性的，即滿足一組線性方程式，則稱為線性碼，否則為非線性碼。(2)根據(jù)上述關(guān)系涉及的范圍，可分為分組碼和卷積碼。分組碼的各碼元僅與本組的信息元有關(guān)；卷積碼中的碼元不僅與本組的信息元有關(guān)，而且還與前面若干組的信息元有關(guān)。(3)根據(jù)碼的用途，可分為檢錯碼和糾錯碼。檢錯碼以檢錯為目的，不一定能糾錯；而糾錯碼以糾錯為目的，一定能檢錯。10.1.3糾錯碼的分類10.1.4糾錯編碼的基本原理

1.分組碼分組碼一般可用(n,k)表示。其中，k是每組二進制信息碼元的數(shù)目，n是編碼碼組的碼元總位數(shù)，又稱為碼組長度，簡稱碼長。n-k=r為每個碼組中的監(jiān)督碼元數(shù)目。簡單地說，分組碼是對每段k位長的信息組以一定的規(guī)則增加r個監(jiān)督元，組成長為n的碼字。在二進制情況下，共有2k個不同的信息組，相應(yīng)地可得到2k個不同的碼字，稱為許用碼組。其余2n-2k個碼字未被選用，稱為禁用碼組。

10.1.4糾錯編碼的基本原理1.分組碼

在分組碼中，非零碼元的數(shù)目稱為碼字的漢明重量，簡稱碼重。例如，碼字10110，碼重w=3。兩個等長碼組之間相應(yīng)位取值不同的數(shù)目稱為這兩個碼組的漢明(Hamming)距離，簡稱碼距。例如11000與10011之間的距離d=3。碼組集中任意兩個碼字之間距離的最小值稱為碼的最小距離，用d０表示。最小碼距是碼的一個重要參數(shù)，它是衡量碼檢錯、糾錯能力的依據(jù)。

在分組碼中，非零碼元的數(shù)目稱為碼字的漢明重量2.檢錯和糾錯能力

若分組碼碼字中的監(jiān)督元在信息元之后，而且是信息元的簡單重復(fù)，則稱該分組碼為重復(fù)碼。它是一種簡單實用的檢錯碼，并有一定的糾錯能力。例如(2,1)重復(fù)碼，兩個許用碼組是00與11，d0=2，收端譯碼，出現(xiàn)01、10禁用碼組時，可以發(fā)現(xiàn)傳輸中的一位錯誤。如果是(3,1)重復(fù)碼，兩個許用碼組是000與111,d0=3;當(dāng)收端出現(xiàn)兩個或三個1時，判為1，否則判為0。此時，可以糾正單個錯誤，或者該碼可以檢出兩個錯誤。2.檢錯和糾錯能力若分組碼碼字中的監(jiān)督

碼的最小距離d0直接關(guān)系著碼的檢錯和糾錯能力；任一(n,k)分組碼，若要在碼字內(nèi):(1)檢測e個隨機錯誤，則要求碼的最小距離d0≥e+1;(2)糾正t個隨機錯誤，則要求碼的最小距離d0≥2t+1;(3)糾正t個同時檢測e(≥t)個隨機錯誤，則要求碼的最小距離d0≥t+e+1。

碼的最小距離d0直接關(guān)系著碼的檢錯和糾錯能力3.編碼效率用差錯控制編碼提高通信系統(tǒng)的可靠性，是以降低有效性為代價換來的。我們定義編碼效率R來衡量有效性:R=k/n其中,k是信息元的個數(shù)，n為碼長。對糾錯碼的基本要求是:檢錯和糾錯能力盡量強；編碼效率盡量高；編碼規(guī)律盡量簡單。際中要根據(jù)具體指標(biāo)要求，保證有一定糾、檢錯能力和編碼效率，并且易于實現(xiàn)。3.編碼效率10.2常用的幾種簡單分組碼10.2.1奇偶監(jiān)督碼

奇偶監(jiān)督碼是在原信息碼后面附加一個監(jiān)督元，使得碼組中“1”的個數(shù)是奇數(shù)或偶數(shù)?；蛘哒f，它是含一個監(jiān)督元，碼重為奇數(shù)或偶數(shù)的(n,n-1)系統(tǒng)分組碼。奇偶監(jiān)督碼又分為奇監(jiān)督碼和偶監(jiān)督碼。10.2常用的幾種簡單分組碼10.2.1奇偶監(jiān)督碼設(shè)碼字A=［an-1,an-2,…,a1,a0］，對偶監(jiān)督碼有

奇監(jiān)督碼情況相似，只是碼組中“1”的數(shù)目為奇數(shù)，即滿足條件而檢錯能力與偶監(jiān)督碼相同。奇偶監(jiān)督碼的編碼效率R為(10-1)(10-2)設(shè)碼字A=［an-1,an-2,…,a1,a0］，對偶監(jiān)督碼10.2.2行列監(jiān)督碼奇偶監(jiān)督碼不能發(fā)現(xiàn)偶數(shù)個錯誤。為了改善這種情況，引入行列監(jiān)督碼。這種碼不僅對水平(行)方向的碼元，而且對垂直(列)方向的碼元實施奇偶監(jiān)督。這種碼既可以逐行傳輸，也可以逐列傳輸。一般地，L×M個信息元附加L+M+1個監(jiān)督元，組成(LM+L+M+1,LM)行列監(jiān)督碼的一個碼字(L+1行，M+1列)。圖10-2是(66,50)行列監(jiān)督碼的一個碼字。這種碼具有較強的檢測能力，適于檢測突發(fā)錯誤，還可用于糾錯。10.2.2行列監(jiān)督碼圖10-2(66,50)行列監(jiān)督碼

圖10-2(66,50)行列監(jiān)督碼10.2.3恒比碼

碼字中1的數(shù)目與0的數(shù)目保持恒定比例的碼稱為恒比碼。由于恒比碼中，每個碼組均含有相同數(shù)目的1和0，因此恒比碼又稱等重碼，定1碼。這種碼在檢測時，只要計算接收碼元中1的數(shù)目是否正確，就知道有無錯誤。

目前我國電傳通信中普遍采用3∶2碼，又稱“5中取3”的恒比碼，即每個碼組的長度為5，其中3個“1”。這時可能編成的不同碼組數(shù)目等于從5中取3的組合數(shù)10，這10個許用碼組恰好可表示10個阿拉伯?dāng)?shù)字，如表7-1所示。而每個漢字又是以四位十進制數(shù)來代表的。實踐證明，采用這種碼后，我國漢字電報的差錯率大為降低。

10.2.3恒比碼碼字中1的數(shù)目與表10-13∶2恒比碼表10-13∶2恒比碼10.3線性分組碼

在(n,k)分組碼中，若每一個監(jiān)督元都是碼組中某些信息元按模二和而得到的，即監(jiān)督元是按線性關(guān)系相加而得到的，則稱線性分組碼。或者說，可用線性方程組表述碼規(guī)律性的分組碼稱為線性分組碼。

現(xiàn)以(7,4)分組碼為例來說明線性分組碼的特點。設(shè)其碼字為A=［a6

a5

a4

a3

a2

a1

a0］，其中前4位是信息元，后3位是監(jiān)督元，可用下列線性方程組來描述該分組碼，產(chǎn)生監(jiān)督元。

(10-3)10.3線性分組碼在(n,k)分組碼中，表10-2(7,4)碼的碼字表表10-2(7,4)碼的碼字表10.3.2監(jiān)督矩陣H和生成矩陣G

式(10-3)所述(7,4)碼的3個監(jiān)督方程式可以改寫為

(10-4)

這組線性方程可用矩陣形式表示為

(10-5)

10.3.2監(jiān)督矩陣H和生成矩陣G式(10-3)所述(并簡記為

(10-6)

其中，AT是A的轉(zhuǎn)置，0T是0=［000］的轉(zhuǎn)置，HT是H的轉(zhuǎn)置。(10-7)

H稱為監(jiān)督矩陣，一旦H給定，信息位和監(jiān)督位之間的關(guān)系也就確定了。H為r×n階矩陣，H矩陣每行之間是彼此線性無關(guān)的。式(10-7)所示的H矩陣可分成兩部分并簡記為(10-6)其中，AT是A的轉(zhuǎn)置，0T是0=［0

其中,P為r×k階矩陣，Ir為r×r階單位矩陣?？梢詫懗蒆=［PIr］形式的矩陣稱為典型監(jiān)督矩陣。HAT=0T，說明H矩陣與碼字的轉(zhuǎn)置乘積必為零，可以用來作為判斷接收碼字A是否出錯的依據(jù)。(10-8)其中,P為r×k階矩陣，Ir為r×r階單若把監(jiān)督方程補充為下列方程

(10-9)

若把監(jiān)督方程補充為下列方程(10-9)可改寫為矩陣形式

(10-10)(10-11)

即

變換為

可改寫為矩陣形式(10-10)(10-11)即變換為其中稱為生成矩陣，由G和信息組就可以產(chǎn)生全部碼字。G為k×n階矩陣，各行也是線性無關(guān)的。生成矩陣也可以分為兩部分，即

(10-12)(10-13)其中稱為生成矩陣，由G和信息組就可以產(chǎn)生全部碼字。G為k×其中

(10-14)Q為k×r階矩陣,Ik為k階單位陣。可以寫成式(10-13)形式的G矩陣，稱為典型生成矩陣。非典型形式的矩陣經(jīng)過運算也一定可以化為典型矩陣形式。其中(10-14)Q為k×r階矩陣,Ik為k階單位陣?？梢?0.3.3伴隨式(校正子)S

設(shè)發(fā)送碼組A=［an-1,an-2,…,a1,a0］，在傳輸過程中可能發(fā)生誤碼。接收碼組B=［bn-1,bn-2,…,b1,b0］，則收發(fā)碼組之差定義為錯誤圖樣E，也稱為誤差矢量，即

其中E=［en-1,en-2,…,e1,e0］，且當(dāng)bi=ai

當(dāng)bi≠ai

(10-15)(10-16)

10.3.3伴隨式(校正子)S設(shè)發(fā)送碼組A式(7-15)也可寫作

令S=BHT，稱為伴隨式或校正子。

(10-17)

(10-18)

由此可見，伴隨式S與錯誤圖樣E之間有確定的線性變換關(guān)系。接收端譯碼器的任務(wù)就是從伴隨式確定錯誤圖樣，然后從接收到的碼字中減去錯誤圖樣。式(7-15)也可寫作令S=BHT，稱為伴隨式或校正子表10-3(7,4)碼S與E的對應(yīng)關(guān)系表10-3(7,4)碼S與E的對應(yīng)關(guān)系10.4循環(huán)碼

循環(huán)碼是一類重要的線性分組碼，它除了具有線性碼的一般性質(zhì)外，還具有循環(huán)性，即循環(huán)碼組中任一碼字循環(huán)移位所得的碼字仍為該碼組中的一個碼字。在代數(shù)理論中，為了便于計算，常用碼多項式表示碼字。(n,k)循環(huán)碼的碼字，其碼多項式(以降冪順序排列)為(10-19)10.4循環(huán)碼循環(huán)碼是一類重要的線性分表10-4(7,3)循環(huán)碼表10-4(7,3)循環(huán)碼10.4.1生成多項式及生成矩陣

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

其它碼多項式都是g(x)的倍式，即

10.4.1生成多項式及生成矩陣如果一種碼因此，循環(huán)碼中次數(shù)最低的多項式(全0碼字除外)就是生成多項式g(x)?？梢宰C明，g(x)是常數(shù)項為1的r=n-k次多項式，是xn+1的一個因式。循環(huán)碼的生成矩陣常用多項式的形式來表示

(10-20)其中

(10-21)

因此，循環(huán)碼中次數(shù)最低的多項式(全0碼字除外)就是生成多例如(7,3)循環(huán)碼，n=7,k=3,r=4,其生成多項式及生成矩陣分別為即

例如(7,3)循環(huán)碼，n=7,k=3,r=4,其生成多

10.4.2監(jiān)督多項式及監(jiān)督矩陣為了便于對循環(huán)碼編譯碼，通常還定義監(jiān)督多項式，令

其中g(shù)(x)是常數(shù)項為1的r次多項式，是生成多項式；h(x)是常數(shù)項為1的k次多項式，稱為監(jiān)督多項式。同理，可得監(jiān)督矩陣H

(10-22)(10-23)10.4.2監(jiān)督多項式及監(jiān)督是h(x)的逆多項式。例如(7，3)循環(huán)碼，其中

(10-24)則

是h(x)的逆多項式。例如(7，3)循環(huán)碼，其中(10-2即

即10.4.3編碼方法和電路

在編碼時，首先要根據(jù)給定的(n,k)值選定生成多項式g(x)，即應(yīng)在xn+1的因式中選一r=n-k次多項式作為g(x)。設(shè)編碼前的信息多項式m(x)為(10-25)

10.4.3編碼方法和電路在編碼時，首先m(x)的最高冪次為k-1。循環(huán)碼中的所有碼多項式都可被g(x)整除，根據(jù)這條原則，就可以對給定的信息進行編碼。用xr乘m(x)，得到xr·m(x)的次數(shù)小于n。用g(x)去除xr·m(x)，得到余式R(x),R(x)的次數(shù)必小于g(x)的次數(shù)，即小于(n-k)。將此余式加于信息位之后作為監(jiān)督位，即將R(x)與xrm(x)相加，得到的多項式必為一碼多項式，因為它必能被g(x)整除，且商的次數(shù)不大于(k-1)。循環(huán)碼的碼多項式可表示為(10-26)

其中，xr·m(x)代表信息位，R(x)是xr·m(x)與g(x)相除得到的余式，代表監(jiān)督位。m(x)的最高冪次為k-1。循環(huán)碼中的所有碼多項式都可被g(圖10-3(7,3)循環(huán)碼編碼電路

編碼電路的主體由生成多項式構(gòu)成的除法電路，再加上適當(dāng)?shù)目刂齐娐方M成。g(x)=x4+x3+x2+1時，(7,3)循環(huán)碼的編碼電路如圖10-3所示。圖10-3(7,3)循環(huán)碼編碼電路編碼電

g(x)的次數(shù)等于移位寄存器的級數(shù)；g(x)的x0,x1,x2,…、xr的非零系數(shù)對應(yīng)移位寄存器的反饋抽頭。首先，移位寄存器清零，3位信息元輸入時，門1斷開,門2接通，直接輸出信息元。第3次移位脈沖到來時將除法電路運算所得的余數(shù)存入移位寄存器。第4～7次移位時，門2斷開，門1接通，輸出監(jiān)督元。具體編碼過程如表10-5所示，此時輸入信息元為110。

g(x)的次數(shù)等于移位寄存器的級數(shù)；g(x)表10-5(7,3)循環(huán)碼的編碼過程表10-5(7,3)循環(huán)碼的編碼過程10.4.4譯碼方法和電路

接收端譯碼的目的是檢錯和糾錯。由于任一碼多項式A(x)都應(yīng)能被生成多項式g(x)整除，所以在接收端可以將接收碼組B(x)用生成多項式去除。當(dāng)傳輸中未發(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)系。

10.4.4譯碼方法和電路接收端譯碼的目的是檢錯圖10-4(7,3)循環(huán)碼譯碼電路

圖10-4(7,3)循環(huán)碼譯碼電路10.5卷積碼

10.5.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)。通常稱m為編碼存儲。卷積碼常用符號(n,k,m)表示。

10.5卷積碼10.5.1基本概念卷積碼

圖10-5是卷積碼(2,1,2)的編碼器。它由移位寄存器、模二加法器及開關(guān)電路組成。圖10-5卷積碼(2,1,2)編碼器

圖10-5是卷積碼(2,1,2)的編碼器。它由

起始狀態(tài)，各級移位寄存器清零，即S1S2S3為000。S1等于當(dāng)前輸入數(shù)據(jù)，而移位寄存器狀態(tài)S2S3存儲以前的數(shù)據(jù)，輸出碼字C由下式確定起始狀態(tài)，各級移位寄存器清零，即S1S2S3

當(dāng)輸入數(shù)據(jù)D=［11010］時，輸出碼字可以計算出來，具體計算過程如表10-6所示。另外，為了保證全部數(shù)據(jù)通過寄存器，還必須在數(shù)據(jù)位后加3個0。從上述的計算可知，每1位數(shù)據(jù)，影響(m+1)個輸出子碼，稱(m+1)為編碼約束度。每個子碼有n個碼元，在卷積碼中有約束關(guān)系的最大碼元長度則為(m+1)·n,稱為編碼約束長度。(2,1,2)卷積碼的編碼約束度為3，約束長度為6。

當(dāng)輸入數(shù)據(jù)D=［11010］時，輸出碼表10-6(2,1,2)編碼器的工作過程表10-6(2,1,2)編碼器的工作過程10.5.2卷積碼的描述

1.樹圖

樹圖描述的是在任何數(shù)據(jù)序列輸入時，碼字所有可能的輸出。對應(yīng)于圖10-5所示的(2,1,2)卷積碼的編碼電路，可以畫出其樹圖如圖10-6所示。10.5.2卷積碼的描述1.樹圖樹圖描述的是圖10-6(2,1,2)碼的樹圖圖10-6(2,1,2)碼的樹圖

以S1S2S3=000作為起點，用a,b,c和d表示出S3S2的4種可能狀態(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;依次類推，可得整個樹圖。輸入不同的信息序列，編碼器就走不同的路徑，輸出不同的碼序列。例如，當(dāng)輸入數(shù)據(jù)為［11010］時，其路徑如圖10-6中虛線所示，并得到輸出碼序列為［11010100…］，與表10-6的結(jié)果一致。

以S1S2S3=000作為起點，用a,b,c和d表示2.狀態(tài)圖

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

在圖中有4個節(jié)點a,b,c,d，同樣分別表示S3S2的4種可能狀態(tài)。每個節(jié)點有兩條線離開該節(jié)點，實線表示輸入數(shù)據(jù)為0，虛線表示輸入數(shù)據(jù)為1，線旁的數(shù)字即為輸出碼字。2.狀態(tài)圖除了用樹圖表示編碼器的工作過程外，還圖10-7(2,1,2)碼的狀態(tài)圖圖10-7(2,1,2)碼的狀態(tài)圖

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

1.維特比譯碼維特比譯碼是一種最大似然譯碼算法。最大似然譯碼算法的基本思路是：把接收碼字與所有可能的碼字比較，選擇一種碼距最小的碼字作為解碼輸出。由于接收序列通常很長，所以維特比譯碼時最大似然譯碼做了簡化，即它把接收碼字分段累接處理，每接收一段碼字，計算、比較一次，保留碼距最小的路徑，直至譯完整個序列。

10.5.3卷積碼的譯碼1.維特比譯碼

現(xiàn)以上述(2，1，2)碼為例說明維特比譯碼過程。設(shè)發(fā)送端的信息數(shù)據(jù)D=［11010000］，由編碼器輸出的碼字C=［1101010010110000］，接收端接收的碼序列B=［0101011010010010］，有4位碼元差錯。下面參照圖10-8的格狀圖說明譯碼過程。如圖10-9所示，先選前3個碼作為標(biāo)準(zhǔn)，對到達第3級的4個節(jié)點的8條路徑進行比較，逐步算出每條路徑與接收碼字之間的累計碼距。累計碼距分別用括號內(nèi)的數(shù)字標(biāo)出，對照后保留一條到達該節(jié)點的碼距較小的路徑作為幸存路徑。再將當(dāng)前節(jié)點移到第4級，計算、比較、保留幸存路徑，直至最后得到到達終點的一條幸存路徑，即為解碼路徑，如圖10-9中實線所示。根據(jù)該路徑，得到解碼結(jié)果?，F(xiàn)以上述(2，1，2)碼為例說明維特比譯碼過程。設(shè)圖10-9維特比譯碼格圖圖10-9維特比譯碼格圖

2.序列譯碼當(dāng)m很大時，可以采用序列譯碼法。其過程如下：譯碼先從碼樹的起始節(jié)點開始，把接收到的第一個子碼的n個碼元與自始節(jié)點出發(fā)的兩條分支按照最小漢明距離進行比較，沿著差異最小的分支走向第二個節(jié)點。在第二個節(jié)點上，譯碼器仍以同樣原理到達下一個節(jié)點，以此類推，最后得到一條路徑。若接收碼組有錯，則自某節(jié)點開始，譯碼器就一直在不正確的路徑中行進，譯碼也一直錯誤。因此，譯碼器有一個門限值，當(dāng)接收碼元與譯碼器所走的路徑上的碼元之間的差異總數(shù)超過門限值時，譯碼器判定有錯，并且返回試走另一分支。經(jīng)數(shù)次返回找出一條正確的路徑，最后譯碼輸出。

2.序列譯碼*10.6網(wǎng)格編碼調(diào)制(TCM)

網(wǎng)絡(luò)編碼調(diào)制(TrellisCodedModulation,縮寫為TCM)技術(shù)。它是利用編碼效率為n/(n+1)的卷積碼，并將每一碼段映射為2n+1個調(diào)制信號集中的一個信號。在收端信號解調(diào)后經(jīng)反映射變換為卷積碼，再送入維特比譯碼器譯碼。它有兩個基本特點：(1)在信號空間中的信號點數(shù)目比無編碼的調(diào)制情況下對應(yīng)的信號點數(shù)目要多，這些增加的信號點使編碼有了冗余，而不犧牲帶寬。(2)采用卷積碼的編碼規(guī)則，使信號點之間引入相互依賴關(guān)系。僅有某些信號點圖樣或序列是允許用的信號序列，并可模型化成為網(wǎng)格狀結(jié)構(gòu)，因此又稱為“格狀”編碼。

*10.6網(wǎng)格編碼調(diào)制(TCM)網(wǎng)絡(luò)編碼調(diào)圖10–108PSK信號空間的集合劃分

圖10–108PSK信號空間的集合劃分

圖10-10畫出了一種8PSK信號空間的集合劃分，所有8個信號點分布在一個圓周上，都具有單位能量。連續(xù)3次劃分后，分別產(chǎn)生2,4,8個子集，最小歐氏距離逐次增大，即如圖10-10所示。

圖10-10畫出了一種8PSK信號空間

根據(jù)上述思想，可以得到TCM的編碼調(diào)制器的系統(tǒng)方框圖，如圖10-11所示。設(shè)輸入碼字有n比特，在采用多電平/多相位調(diào)制時，有同相分量和正交分量，因此在無編碼的調(diào)制時，在二維信號空間中應(yīng)有2n個信號點與它對應(yīng)。在應(yīng)用編碼調(diào)制時，為增加冗余度，有2n+1個信號點。在圖10-10中，可劃分為4個子集，對應(yīng)于碼字的1比特加到編碼效率為1/2的卷積碼編碼器輸入端，輸出2比特，選擇相應(yīng)的子集。碼字的剩余的未編碼數(shù)據(jù)比特確定信號與子集中信號點之間的映射關(guān)系。根據(jù)上述思想，可以得到TCM的編碼調(diào)制器的系統(tǒng)圖10–11TCM編碼調(diào)制器方框圖圖10–11TCM編碼調(diào)制器方框圖

在接收端采用維特比算法執(zhí)行最大似然檢測。編碼網(wǎng)格狀圖中的每一條支路對應(yīng)于一個子集，而不是一個信號點。檢測的第一步是確定每個子集中的信號點，在歐氏距離意義下，這個子集是最靠近接收信號的子集。圖10-12(a)描述了最簡單的傳輸2比特碼字的8PSKTCM編碼方案。它采用了效率為1/2的卷積碼編碼器，對應(yīng)的格圖如圖10-12(b)所示。該結(jié)構(gòu)有4個狀態(tài)，每個狀態(tài)對應(yīng)于圖10-10中距離為d2的4個子集。

在接收端采用維特比算法執(zhí)行最大似然檢測。編碼網(wǎng)格狀圖10-124狀態(tài)編碼方案

圖10-124狀態(tài)編碼方案第10章差錯控制編碼

10.1概述10.2常用的幾種簡單分組碼10.3線性分組碼10.4循環(huán)碼10.5卷積碼*10.6網(wǎng)格編碼調(diào)制第10章差錯控制編碼10.1概述10.1概述

10.1.1信道編碼在數(shù)字通信中，根據(jù)不同的目的，編碼可分為信源編碼和信道編碼。信源編碼是為了提高數(shù)字信號的有效性以及為了使模擬信號數(shù)字化而采取的編碼。信道編碼是為了降低誤碼率，提高數(shù)字通信的可靠性而采取的編碼。數(shù)字信號在傳輸過程中，加性噪聲、碼間串?dāng)_等都會產(chǎn)生誤碼。為了提高系統(tǒng)的抗干擾性能，可以加大發(fā)射功率，降低接收設(shè)備本身的噪聲，以及合理選擇調(diào)制、解調(diào)方法等。此外，還可以采用信道編碼技術(shù)。10.1概述10.1.1信道編碼10.1.2差錯控制方式

圖10-1差錯控制方式

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

2.前向糾錯方式3.混合糾錯方式混合糾錯方式記作HEC(HybridErrorCorrection)是FEC和ARQ方式的結(jié)合。發(fā)端發(fā)送具有自動糾錯同時又具有檢錯能力的碼。收端收到碼后，檢查差錯情況，如果錯誤在碼的糾錯能力范圍以內(nèi)，則自動糾錯，如果超過了碼的糾錯能力，但能檢測出來，則經(jīng)過反饋信道請求發(fā)端重發(fā)。這種方式具有自動糾錯和檢錯重發(fā)的優(yōu)點，可達到較低的誤碼率，因此，近年來得到廣泛應(yīng)用。3.混合糾錯方式

另外，按照噪聲或干擾的變化規(guī)律，可把信道分為三類：隨機信道、突發(fā)信道和混合信道。恒參高斯白噪聲信道是典型的隨機信道，其中差錯的出現(xiàn)是隨機的，而且錯誤之間是統(tǒng)計獨立的。具有脈沖干擾的信道是典型的突發(fā)信道，錯誤是成串成群出現(xiàn)的，即在短時間內(nèi)出現(xiàn)大量錯誤。短波信道和對流層散射信道是混合信道的典型例子，隨機錯誤和成串錯誤都占有相當(dāng)比例。對于不同類型的信道，應(yīng)采用不同的差錯控制方式。另外，按照噪聲或干擾的變化規(guī)律，可把信道分為10.1.3糾錯碼的分類(1)根據(jù)糾錯碼各碼組信息元和監(jiān)督元的函數(shù)關(guān)系，可分為線性碼和非線性碼。如果函數(shù)關(guān)系是線性的，即滿足一組線性方程式，則稱為線性碼，否則為非線性碼。(2)根據(jù)上述關(guān)系涉及的范圍，可分為分組碼和卷積碼。分組碼的各碼元僅與本組的信息元有關(guān)；卷積碼中的碼元不僅與本組的信息元有關(guān)，而且還與前面若干組的信息元有關(guān)。(3)根據(jù)碼的用途，可分為檢錯碼和糾錯碼。檢錯碼以檢錯為目的，不一定能糾錯；而糾錯碼以糾錯為目的，一定能檢錯。10.1.3糾錯碼的分類10.1.4糾錯編碼的基本原理

1.分組碼分組碼一般可用(n,k)表示。其中，k是每組二進制信息碼元的數(shù)目，n是編碼碼組的碼元總位數(shù)，又稱為碼組長度，簡稱碼長。n-k=r為每個碼組中的監(jiān)督碼元數(shù)目。簡單地說，分組碼是對每段k位長的信息組以一定的規(guī)則增加r個監(jiān)督元，組成長為n的碼字。在二進制情況下，共有2k個不同的信息組，相應(yīng)地可得到2k個不同的碼字，稱為許用碼組。其余2n-2k個碼字未被選用，稱為禁用碼組。

10.1.4糾錯編碼的基本原理1.分組碼

在分組碼中，非零碼元的數(shù)目稱為碼字的漢明重量，簡稱碼重。例如，碼字10110，碼重w=3。兩個等長碼組之間相應(yīng)位取值不同的數(shù)目稱為這兩個碼組的漢明(Hamming)距離，簡稱碼距。例如11000與10011之間的距離d=3。碼組集中任意兩個碼字之間距離的最小值稱為碼的最小距離，用d０表示。最小碼距是碼的一個重要參數(shù)，它是衡量碼檢錯、糾錯能力的依據(jù)。

在分組碼中，非零碼元的數(shù)目稱為碼字的漢明重量2.檢錯和糾錯能力

若分組碼碼字中的監(jiān)督元在信息元之后，而且是信息元的簡單重復(fù)，則稱該分組碼為重復(fù)碼。它是一種簡單實用的檢錯碼，并有一定的糾錯能力。例如(2,1)重復(fù)碼，兩個許用碼組是00與11，d0=2，收端譯碼，出現(xiàn)01、10禁用碼組時，可以發(fā)現(xiàn)傳輸中的一位錯誤。如果是(3,1)重復(fù)碼，兩個許用碼組是000與111,d0=3;當(dāng)收端出現(xiàn)兩個或三個1時，判為1，否則判為0。此時，可以糾正單個錯誤，或者該碼可以檢出兩個錯誤。2.檢錯和糾錯能力若分組碼碼字中的監(jiān)督

碼的最小距離d0直接關(guān)系著碼的檢錯和糾錯能力；任一(n,k)分組碼，若要在碼字內(nèi):(1)檢測e個隨機錯誤，則要求碼的最小距離d0≥e+1;(2)糾正t個隨機錯誤，則要求碼的最小距離d0≥2t+1;(3)糾正t個同時檢測e(≥t)個隨機錯誤，則要求碼的最小距離d0≥t+e+1。

碼的最小距離d0直接關(guān)系著碼的檢錯和糾錯能力3.編碼效率用差錯控制編碼提高通信系統(tǒng)的可靠性，是以降低有效性為代價換來的。我們定義編碼效率R來衡量有效性:R=k/n其中,k是信息元的個數(shù)，n為碼長。對糾錯碼的基本要求是:檢錯和糾錯能力盡量強；編碼效率盡量高；編碼規(guī)律盡量簡單。際中要根據(jù)具體指標(biāo)要求，保證有一定糾、檢錯能力和編碼效率，并且易于實現(xiàn)。3.編碼效率10.2常用的幾種簡單分組碼10.2.1奇偶監(jiān)督碼

奇偶監(jiān)督碼是在原信息碼后面附加一個監(jiān)督元，使得碼組中“1”的個數(shù)是奇數(shù)或偶數(shù)?；蛘哒f，它是含一個監(jiān)督元，碼重為奇數(shù)或偶數(shù)的(n,n-1)系統(tǒng)分組碼。奇偶監(jiān)督碼又分為奇監(jiān)督碼和偶監(jiān)督碼。10.2常用的幾種簡單分組碼10.2.1奇偶監(jiān)督碼設(shè)碼字A=［an-1,an-2,…,a1,a0］，對偶監(jiān)督碼有

奇監(jiān)督碼情況相似，只是碼組中“1”的數(shù)目為奇數(shù)，即滿足條件而檢錯能力與偶監(jiān)督碼相同。奇偶監(jiān)督碼的編碼效率R為(10-1)(10-2)設(shè)碼字A=［an-1,an-2,…,a1,a0］，對偶監(jiān)督碼10.2.2行列監(jiān)督碼奇偶監(jiān)督碼不能發(fā)現(xiàn)偶數(shù)個錯誤。為了改善這種情況，引入行列監(jiān)督碼。這種碼不僅對水平(行)方向的碼元，而且對垂直(列)方向的碼元實施奇偶監(jiān)督。這種碼既可以逐行傳輸，也可以逐列傳輸。一般地，L×M個信息元附加L+M+1個監(jiān)督元，組成(LM+L+M+1,LM)行列監(jiān)督碼的一個碼字(L+1行，M+1列)。圖10-2是(66,50)行列監(jiān)督碼的一個碼字。這種碼具有較強的檢測能力，適于檢測突發(fā)錯誤，還可用于糾錯。10.2.2行列監(jiān)督碼圖10-2(66,50)行列監(jiān)督碼

圖10-2(66,50)行列監(jiān)督碼10.2.3恒比碼

碼字中1的數(shù)目與0的數(shù)目保持恒定比例的碼稱為恒比碼。由于恒比碼中，每個碼組均含有相同數(shù)目的1和0，因此恒比碼又稱等重碼，定1碼。這種碼在檢測時，只要計算接收碼元中1的數(shù)目是否正確，就知道有無錯誤。

目前我國電傳通信中普遍采用3∶2碼，又稱“5中取3”的恒比碼，即每個碼組的長度為5，其中3個“1”。這時可能編成的不同碼組數(shù)目等于從5中取3的組合數(shù)10，這10個許用碼組恰好可表示10個阿拉伯?dāng)?shù)字，如表7-1所示。而每個漢字又是以四位十進制數(shù)來代表的。實踐證明，采用這種碼后，我國漢字電報的差錯率大為降低。

10.2.3恒比碼碼字中1的數(shù)目與表10-13∶2恒比碼表10-13∶2恒比碼10.3線性分組碼

在(n,k)分組碼中，若每一個監(jiān)督元都是碼組中某些信息元按模二和而得到的，即監(jiān)督元是按線性關(guān)系相加而得到的，則稱線性分組碼?；蛘哒f，可用線性方程組表述碼規(guī)律性的分組碼稱為線性分組碼。

現(xiàn)以(7,4)分組碼為例來說明線性分組碼的特點。設(shè)其碼字為A=［a6

a5

a4

a3

a2

a1

a0］，其中前4位是信息元，后3位是監(jiān)督元，可用下列線性方程組來描述該分組碼，產(chǎn)生監(jiān)督元。

(10-3)10.3線性分組碼在(n,k)分組碼中，表10-2(7,4)碼的碼字表表10-2(7,4)碼的碼字表10.3.2監(jiān)督矩陣H和生成矩陣G

式(10-3)所述(7,4)碼的3個監(jiān)督方程式可以改寫為

(10-4)

這組線性方程可用矩陣形式表示為

(10-5)

10.3.2監(jiān)督矩陣H和生成矩陣G式(10-3)所述(并簡記為

(10-6)

其中，AT是A的轉(zhuǎn)置，0T是0=［000］的轉(zhuǎn)置，HT是H的轉(zhuǎn)置。(10-7)

H稱為監(jiān)督矩陣，一旦H給定，信息位和監(jiān)督位之間的關(guān)系也就確定了。H為r×n階矩陣，H矩陣每行之間是彼此線性無關(guān)的。式(10-7)所示的H矩陣可分成兩部分并簡記為(10-6)其中，AT是A的轉(zhuǎn)置，0T是0=［0

其中,P為r×k階矩陣，Ir為r×r階單位矩陣。可以寫成H=［PIr］形式的矩陣稱為典型監(jiān)督矩陣。HAT=0T，說明H矩陣與碼字的轉(zhuǎn)置乘積必為零，可以用來作為判斷接收碼字A是否出錯的依據(jù)。(10-8)其中,P為r×k階矩陣，Ir為r×r階單若把監(jiān)督方程補充為下列方程

(10-9)

若把監(jiān)督方程補充為下列方程(10-9)可改寫為矩陣形式

(10-10)(10-11)

即

變換為

可改寫為矩陣形式(10-10)(10-11)即變換為其中稱為生成矩陣，由G和信息組就可以產(chǎn)生全部碼字。G為k×n階矩陣，各行也是線性無關(guān)的。生成矩陣也可以分為兩部分，即

(10-12)(10-13)其中稱為生成矩陣，由G和信息組就可以產(chǎn)生全部碼字。G為k×其中

(10-14)Q為k×r階矩陣,Ik為k階單位陣。可以寫成式(10-13)形式的G矩陣，稱為典型生成矩陣。非典型形式的矩陣經(jīng)過運算也一定可以化為典型矩陣形式。其中(10-14)Q為k×r階矩陣,Ik為k階單位陣。可以10.3.3伴隨式(校正子)S

設(shè)發(fā)送碼組A=［an-1,an-2,…,a1,a0］，在傳輸過程中可能發(fā)生誤碼。接收碼組B=［bn-1,bn-2,…,b1,b0］，則收發(fā)碼組之差定義為錯誤圖樣E，也稱為誤差矢量，即

其中E=［en-1,en-2,…,e1,e0］，且當(dāng)bi=ai

當(dāng)bi≠ai

(10-15)(10-16)

10.3.3伴隨式(校正子)S設(shè)發(fā)送碼組A式(7-15)也可寫作

令S=BHT，稱為伴隨式或校正子。

(10-17)

(10-18)

由此可見，伴隨式S與錯誤圖樣E之間有確定的線性變換關(guān)系。接收端譯碼器的任務(wù)就是從伴隨式確定錯誤圖樣，然后從接收到的碼字中減去錯誤圖樣。式(7-15)也可寫作令S=BHT，稱為伴隨式或校正子表10-3(7,4)碼S與E的對應(yīng)關(guān)系表10-3(7,4)碼S與E的對應(yīng)關(guān)系10.4循環(huán)碼

循環(huán)碼是一類重要的線性分組碼，它除了具有線性碼的一般性質(zhì)外，還具有循環(huán)性，即循環(huán)碼組中任一碼字循環(huán)移位所得的碼字仍為該碼組中的一個碼字。在代數(shù)理論中，為了便于計算，常用碼多項式表示碼字。(n,k)循環(huán)碼的碼字，其碼多項式(以降冪順序排列)為(10-19)10.4循環(huán)碼循環(huán)碼是一類重要的線性分表10-4(7,3)循環(huán)碼表10-4(7,3)循環(huán)碼10.4.1生成多項式及生成矩陣

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

其它碼多項式都是g(x)的倍式，即

10.4.1生成多項式及生成矩陣如果一種碼因此，循環(huán)碼中次數(shù)最低的多項式(全0碼字除外)就是生成多項式g(x)?？梢宰C明，g(x)是常數(shù)項為1的r=n-k次多項式，是xn+1的一個因式。循環(huán)碼的生成矩陣常用多項式的形式來表示

(10-20)其中

(10-21)

因此，循環(huán)碼中次數(shù)最低的多項式(全0碼字除外)就是生成多例如(7,3)循環(huán)碼，n=7,k=3,r=4,其生成多項式及生成矩陣分別為即

例如(7,3)循環(huán)碼，n=7,k=3,r=4,其生成多

10.4.2監(jiān)督多項式及監(jiān)督矩陣為了便于對循環(huán)碼編譯碼，通常還定義監(jiān)督多項式，令

其中g(shù)(x)是常數(shù)項為1的r次多項式，是生成多項式；h(x)是常數(shù)項為1的k次多項式，稱為監(jiān)督多項式。同理，可得監(jiān)督矩陣H

(10-22)(10-23)10.4.2監(jiān)督多項式及監(jiān)督是h(x)的逆多項式。例如(7，3)循環(huán)碼，其中

(10-24)則

是h(x)的逆多項式。例如(7，3)循環(huán)碼，其中(10-2即

即10.4.3編碼方法和電路

在編碼時，首先要根據(jù)給定的(n,k)值選定生成多項式g(x)，即應(yīng)在xn+1的因式中選一r=n-k次多項式作為g(x)。設(shè)編碼前的信息多項式m(x)為(10-25)

10.4.3編碼方法和電路在編碼時，首先m(x)的最高冪次為k-1。循環(huán)碼中的所有碼多項式都可被g(x)整除，根據(jù)這條原則，就可以對給定的信息進行編碼。用xr乘m(x)，得到xr·m(x)的次數(shù)小于n。用g(x)去除xr·m(x)，得到余式R(x),R(x)的次數(shù)必小于g(x)的次數(shù)，即小于(n-k)。將此余式加于信息位之后作為監(jiān)督位，即將R(x)與xrm(x)相加，得到的多項式必為一碼多項式，因為它必能被g(x)整除，且商的次數(shù)不大于(k-1)。循環(huán)碼的碼多項式可表示為(10-26)

其中，xr·m(x)代表信息位，R(x)是xr·m(x)與g(x)相除得到的余式，代表監(jiān)督位。m(x)的最高冪次為k-1。循環(huán)碼中的所有碼多項式都可被g(圖10-3(7,3)循環(huán)碼編碼電路

編碼電路的主體由生成多項式構(gòu)成的除法電路，再加上適當(dāng)?shù)目刂齐娐方M成。g(x)=x4+x3+x2+1時，(7,3)循環(huán)碼的編碼電路如圖10-3所示。圖10-3(7,3)循環(huán)碼編碼電路編碼電

g(x)的次數(shù)等于移位寄存器的級數(shù)；g(x)的x0,x1,x2,…、xr的非零系數(shù)對應(yīng)移位寄存器的反饋抽頭。首先，移位寄存器清零，3位信息元輸入時，門1斷開,門2接通，直接輸出信息元。第3次移位脈沖到來時將除法電路運算所得的余數(shù)存入移位寄存器。第4～7次移位時，門2斷開，門1接通，輸出監(jiān)督元。具體編碼過程如表10-5所示，此時輸入信息元為110。

g(x)的次數(shù)等于移位寄存器的級數(shù)；g(x)表10-5(7,3)循環(huán)碼的編碼過程表10-5(7,3)循環(huán)碼的編碼過程10.4.4譯碼方法和電路

接收端譯碼的目的是檢錯和糾錯。由于任一碼多項式A(x)都應(yīng)能被生成多項式g(x)整除，所以在接收端可以將接收碼組B(x)用生成多項式去除。當(dāng)傳輸中未發(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)系。

10.4.4譯碼方法和電路接收端譯碼的目的是檢錯圖10-4(7,3)循環(huán)碼譯碼電路

圖10-4(7,3)循環(huán)碼譯碼電路10.5卷積碼

10.5.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)。通常稱m為編碼存儲。卷積碼常用符號(n,k,m)表示。

10.5卷積碼10.5.1基本概念卷積碼

圖10-5是卷積碼(2,1,2)的編碼器。它由移位寄存器、模二加法器及開關(guān)電路組成。圖10-5卷積碼(2,1,2)編碼器

圖10-5是卷積碼(2,1,2)的編碼器。它由

起始狀態(tài)，各級移位寄存器清零，即S1S2S3為000。S1等于當(dāng)前輸入數(shù)據(jù)，而移位寄存器狀態(tài)S2S3存儲以前的數(shù)據(jù)，輸出碼字C由下式確定起始狀態(tài)，各級移位寄存器清零，即S1S2S3

當(dāng)輸入數(shù)據(jù)D=［11010］時，輸出碼字可以計算出來，具體計算過程如表10-6所示。另外，為了保證全部數(shù)據(jù)通過寄存器，還必須在數(shù)據(jù)位后加3個0。從上述的計算可知，每1位數(shù)據(jù)，影響(m+1)個輸出子碼，稱(m+1)為編碼約束度。每個子碼有n個碼元，在卷積碼中有約束關(guān)系的最大碼元長度則為(m+1)·n,稱為編碼約束長度。(2,1,2)卷積碼的編碼約束度為3，約束長度為6。

當(dāng)輸入數(shù)據(jù)D=［11010］時，輸出碼表10-6(2,1,2)編碼器的工作過程表10-6(2,1,2)編碼器的工作過程10.5.2卷積碼的描述

1.樹圖

樹圖描述的是在任何數(shù)據(jù)序列輸入時，碼字所有可能的輸出。對應(yīng)于圖10-5所示的(2,1,2)卷積碼的編碼電路，可以畫出其樹圖如圖10-6所示。10.5.2卷積碼的描述1.樹圖樹圖描述的是圖10-6(2,1,2)碼的樹圖圖10-6(2,1,2)碼的樹圖

以S1S2S3=000作為起點，用a,b,c和d表示出S3S2的4種可能狀態(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;依次類推，可得整個樹圖。輸入不同的信息序列，編碼器就走不同的路徑，輸出不同的碼序列。例如，當(dāng)輸入數(shù)據(jù)為［11010］時，其路徑如圖10-6中虛線所示，并得到輸出碼序列為［11010100…］，與表10-6的結(jié)果一致。

以S1S2S3=000作為起點，用a,b,c和d表示2.狀態(tài)圖

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

在圖中有4個節(jié)點a,b,c,d，同樣分別表示S3S2的4種可能狀態(tài)。每個節(jié)點有兩條線離開該節(jié)點，實線表示輸入數(shù)據(jù)為0，虛線表示輸入數(shù)據(jù)為1，線旁的數(shù)字即為輸出碼字。2.狀態(tài)圖除了用樹圖表示編碼器的工作過程外，還圖10-7(2,1,2)碼的狀態(tài)圖圖10-7(2,1,2)碼的狀態(tài)圖