第十章差錯控制

10.8關(guān)于幀或分組順序的差錯控制（10.4卷積碼10.3循環(huán)碼10.1差錯控制編碼的基本概念第十章差錯控制學(xué)習(xí)目錄10.2線性分組碼10.7不用編碼的差錯控制10.5網(wǎng)格編碼調(diào)制（TCM）（略）10.6Turbo碼10.9差錯控制編碼對系統(tǒng)性能的改善10.1差錯控制編碼的基本概念

按照噪聲或干擾的變化規(guī)律，可把信道分為三類：隨機信道：恒參高斯白噪聲信道是典型的隨機信道，其中差錯的出現(xiàn)是隨機的，而且錯誤之間是統(tǒng)計獨立的。突發(fā)信道：具有脈沖干擾的信道，是典型的突發(fā)信道。錯誤是成串成群出現(xiàn)的，即在短時間內(nèi)出現(xiàn)大量錯誤。混合信道10.1差錯控制編碼的基本概念1.差錯控制的工作方式

差錯控制的基本工作方式有4種：前向糾錯檢錯重發(fā)混合糾錯反饋校驗。10.1差錯控制編碼的基本概念（1）前向糾錯方式(ForwardErrorCorrection，F(xiàn)EC)發(fā)收可以糾正錯誤的碼（2）檢錯重發(fā)方式（AutoReQuestRepeat，ARQ)發(fā)收能夠發(fā)現(xiàn)錯誤的碼應(yīng)答信號

在具體實現(xiàn)檢錯重發(fā)系統(tǒng)時，通常有三種形式，即停發(fā)等候重發(fā)，返回重發(fā)和選擇重發(fā)。10.1差錯控制編碼的基本概念（3）混合糾錯方式(HybridErrorCorrection,HEC)發(fā)收可以糾正和發(fā)現(xiàn)錯誤的碼（4）信息反饋方式（InformationFeedback,IF）發(fā)收數(shù)據(jù)信息數(shù)據(jù)信息回程校驗:發(fā)端將反饋信息和原發(fā)送信息進(jìn)行比較，發(fā)現(xiàn)錯誤進(jìn)行重發(fā)。10.1差錯控制編碼的基本概念2.差錯控制編碼的分類按照差錯控制編碼的用途：檢錯碼、糾錯碼和糾刪碼。按照信息碼元和監(jiān)督碼元之間的函數(shù)關(guān)系：線性碼和非線性碼。按照對信息元處理方式的：分組碼和卷積碼。按照碼組中信息碼元在編碼前后是否相同：系統(tǒng)碼和非系統(tǒng)碼。按照糾（檢）錯誤的類型：糾（檢）隨機錯誤碼、糾（檢）突發(fā)錯誤碼和既能糾（檢）隨機錯誤同時又能糾（檢）突發(fā)錯誤碼。按照每個碼元的取值：二進(jìn)碼和多進(jìn)碼。10.1差錯控制編碼的基本概念

差錯編碼的基本思想是在被傳輸信息中增加一些冗余碼，利用附加碼元和信息碼元之間的約束關(guān)系加以校驗，以檢測和糾正錯誤，增加冗余碼的個數(shù)可增加糾檢錯能力。3.差錯控制編碼的基本原理10.1差錯控制編碼的基本概念

編碼碼組的碼元總位數(shù)稱為碼組的長度，簡稱碼長。碼組中，“1”碼元的數(shù)目稱為碼組的重量，簡稱碼重。兩個等長碼組之間對應(yīng)位上碼元不同的數(shù)目稱為這兩個碼組的距離，簡稱碼距。（1）碼長、碼重、碼距（000）（110）（100）（010）（111）（101）（011）（001）A1A2A32）檢錯和糾錯能力10.1差錯控制編碼的基本概念①檢測e個隨機錯誤，則要求最小碼距dmin≥e+1；c1e-11dminc2110.1差錯控制編碼的基本概念 ②糾正t個隨機錯誤，則要求最小碼距dmin≥2t+1；c1t1dminc2t10.1差錯控制編碼的基本概念③糾正t個同時檢測e（et）個隨機錯誤，則要求最小碼距dmin≥t+e+1。t1dminc2tc1e10.1差錯控制編碼的基本概念（3）編碼效率用差錯控制編碼提高通信系統(tǒng)的的可靠性，是以降低有效性為代價換來的。定義編碼效率η來衡量有效性：

η=k/n=k/(k+r)

其中，k是信息元的個數(shù)，n為碼長，r為校驗碼個數(shù)。10.1差錯控制編碼的基本概念4.常用的幾種簡單編碼（1）奇偶監(jiān)督碼奇偶監(jiān)督碼是在原信息碼后面附加一個監(jiān)督元，使得碼組中“1”的個數(shù)是奇數(shù)或偶數(shù)，或者說，它是含一個監(jiān)督元，碼重為奇數(shù)或偶數(shù)的（n，n-1）系統(tǒng)分組碼。奇偶監(jiān)督碼又分為奇監(jiān)督碼和偶監(jiān)督碼。10.1差錯控制編碼的基本概念（2）行列監(jiān)督碼（水平奇偶監(jiān)督碼）奇偶監(jiān)督碼不能發(fā)現(xiàn)偶數(shù)個錯誤。此引入行列監(jiān)督碼：將經(jīng)過奇偶監(jiān)督碼的碼元序列排成方陣，每行為一組再做奇偶監(jiān)督編碼，發(fā)送時則按列的順序傳輸。一維奇偶監(jiān)督碼信息碼監(jiān)督碼元1110010100100101011001000110000110101001信息碼監(jiān)督碼元1110010100100101011001000110000110101001監(jiān)督碼元0011001100二維奇偶監(jiān)督碼10.1差錯控制編碼的基本概念10.1差錯控制編碼的基本概念（3）漢明(Hamming)奇偶監(jiān)督碼漢明校驗是分組奇偶校驗。校驗位Pn的權(quán)值為2n-1例:傳送信息:1000101編碼:P1P21P3000P4101組P1P21P3000P41011√√√√√√2√√√√√√3√√√√4√√√√分組10.1差錯控制編碼的基本概念編碼，設(shè)發(fā)送與接收雙方均采用奇校驗，則

P1=0，P2=1，P3=1，P4

=1發(fā)送端發(fā)送的比特流為01110001101接收端接收到的比特流為01100001101（能否糾檢錯？）組P1P21P3000P41011√√√√√√2√√√√√√3√√√√4√√√√10.1差錯控制編碼的基本概念（3）重復(fù)碼重復(fù)碼是在每位碼元之后，用簡單重復(fù)多次的方法編碼。例如重復(fù)兩次，用111傳輸1碼，用000傳輸0碼。（4）恒比碼碼字中1的數(shù)目與0的數(shù)目保持恒定比例的碼稱為恒比碼。由于恒比碼中，每個碼組均含有相同數(shù)目的1和0，因此恒比碼又稱等重碼，定1碼。這種碼在檢測時，只要計算接收碼元中1的個數(shù)是否與規(guī)定的相同，就可判斷有無錯誤。10.1差錯控制編碼的基本概念（5）群計數(shù)碼群計數(shù)碼是將信息碼元分組后，計算每組碼元中“1”的個數(shù)，然后將這個數(shù)目的二進(jìn)制表示作為監(jiān)督碼元，一起送往發(fā)送端。返回結(jié)束10.2線性分組碼1.線性分組碼的定義和特點線性分組碼，是指信息碼元與監(jiān)督碼元之間的關(guān)系可以用一組線性方程來表示的分組碼，即在（n，k）分組碼中，每一個監(jiān)督碼元都是碼組中某些信息碼元按模2和而得到的。

線性分組碼是一類重要的糾錯碼，應(yīng)用很廣。（1）生成矩陣

設(shè)分組碼的碼組由n位碼組成，即c1,c2…cn

；信息碼組由k位碼組成，即d1,d2,…,dk

。以上碼組記為（n，k）碼，碼組和信息碼組用行矩陣表示：

C=[c1,c2,…,cn]D=[d1,d2,…,dk

]系統(tǒng)分組碼用聯(lián)立方程可表示為

c1=d1

ck=dk

ck+1=h11d1h12d2h1kdkcn=hn-k,1d1hn-k,2d2hn-k,kdk++++++10.2線性分組碼10.2線性分組碼

將碼組C寫成矩陣形式：

C=D?G其中矩陣G稱為生成矩陣10.2線性分組碼

由生成矩陣G和信息組就可以產(chǎn)生全部碼字。G為k×n階矩陣，各行也是線性無關(guān)的。

數(shù)學(xué)上已經(jīng)證明，線性碼的最小碼距dmin正好等于非零碼的最小碼重。例：已知（6，3）碼的生成矩陣為：10.2線性分組碼試求：（1）編碼碼組和各個碼組的碼重；（2）最小碼距和該碼的差錯控制能力。解：由3位碼組成的信息碼組矩陣為10.2線性分組碼碼組矩陣為10.2線性分組碼10.2線性分組碼信息碼組、編碼碼組及碼重如下表所示。信息碼組編碼碼組碼重0000010100111001011101110000000011100100110111011001011010111101101110000334344310.2線性分組碼由上表可知，非零碼的最小碼重

Wmin=3因此，①檢測e個隨機錯誤，則要求最小碼距dmin≥e+1；②糾正t個隨機錯誤，則要求最小碼距dmin≥2t+1；③糾正t個同時檢測e（e＞t）個隨機錯誤，則要求最小碼距dmin≥t+e+1。可知，該碼有檢2錯，或糾1錯，或糾1錯同時檢1錯的能力。10.2線性分組碼（2）監(jiān)督矩陣碼組C又寫成矩陣形式：

C=D?G=D?[Ik,P]=[DIk,DP]=[D,Cm]于是有

DP=Cm（m=n-k）

DPCm=0寫成矩陣形式+10.2線性分組碼令或有我們把

H

稱為監(jiān)督矩陣，或稱一致校驗矩陣，一旦H給定，信息位和監(jiān)督位之間的關(guān)系也就確定了。H為m×n階矩陣，H矩陣每行之間是彼此線性無關(guān)的。H矩陣可分成兩部分，其中P為k×m階矩陣，Im為m×m階單位陣。能寫成H=［PTIm］形式的矩陣稱為典型監(jiān)督矩陣。10.2線性分組碼

設(shè)接收組碼為R，它是n位碼組成的行矢量。如果接收組碼有錯，組碼可分解為正確組碼C與錯誤組碼E之和，即定義伴隨式或校正子為S=RHT。

S=RHT=（C+E）HT=EHT

由此可見，伴隨式S與錯誤圖樣E之間有確定的線性變換關(guān)系，與發(fā)送碼組C無關(guān)。接收端譯碼器的任務(wù)就是從伴隨式確定錯誤圖樣，然后從接收到的碼字中減去錯誤圖樣。10.2線性分組碼當(dāng)碼組出現(xiàn)錯誤時，由

S=EHT解出E矢量。由得

C=RE+如何解方程S=EHT？

S為零矢量時，E=0？10.2線性分組碼S=EHT的解不唯一（n個變量，m（=n-k）個方程組）。S為零矢量時，E不一定為0。為了選擇正確的結(jié)果，要使用最大似然比準(zhǔn)則，選擇與R最相似的C。從幾何意義上來說，就是選擇與R距離最小的碼組。當(dāng)R與C之間距離最近時意味著差錯矢量E是1碼最少的矢量。10.2線性分組碼例：已知（6，3）碼的生成矩陣為試列出S與R的對照表。當(dāng)收到碼組R=[111011]時，解出對應(yīng)的信息碼組D。10.2線性分組碼解：生成矩陣監(jiān)督矩陣轉(zhuǎn)置10.2線性分組碼S=EHT共有23種形式，相對的碼重最小的E矢量有8種，對應(yīng)關(guān)系如下表。ES00000010000001000000100000010000001000000110001000010101111010001000111110.2線性分組碼將接收的碼組矢量R=[111011]代入S=EHT，得由上表可找到差錯矢量E為

E=[010000]10.2線性分組碼正確的碼組為

C=RE=[111011][010000]

=[101011]+所以信息碼組為

D=[101]從以上分析可以得出線性分組碼譯碼的基本步驟：①計算接收碼組R的伴隨式S；②根據(jù)S找出錯誤圖樣E，判定誤碼位置；③根據(jù)E糾正錯誤，得到正確的碼組。+10.2線性分組碼4.漢明碼漢明碼(1950)是一類常見的線性分組碼，是一種能夠糾正單個錯誤的完備碼。要糾正碼組中的單個錯誤，則要求與單個錯誤圖樣對應(yīng)的伴隨式各不相同，且不能為全零。若碼長為n，監(jiān)督碼元的個數(shù)為m，則要求2m-1≥n

碼組為漢明碼時取等號。即用來糾正單個錯誤時，漢明碼所用的監(jiān)督碼元個數(shù)最少，效率最高。10.2線性分組碼漢明碼的特點如下：（1）監(jiān)督碼元的個數(shù)m=n-k，碼長滿足n=2m-1，k=n-m。m≥2。（2）無論碼長n為多少，漢明碼最小碼距dmin=3。（3）其編碼效率為η=k/n=(2m-1-m)/(2m-1)=1-m/n。10.2線性分組碼例1.已知：信息碼為“0010”。漢明碼的監(jiān)督關(guān)系式為：

S2=a2+a4+a5+a6

S1=a1+a3+a5+a6

S0=a0+a3+a4+a6

求：漢明碼碼字。解：1)由監(jiān)督關(guān)系式知冗余碼為a2a1a0。

2)冗余碼與信息碼合成的漢明碼是

0010a2a1a010.2線性分組碼設(shè)S2=S1=S0=0,由監(jiān)督關(guān)系式得：

a2=a4+a5+a6=1

a1=a3+a5+a6=0

a0=a3+a4+a6=1

因此，漢明碼碼字為："0010101"

漢明碼是線性碼，其生成矩陣？10.2線性分組碼例2.已知：漢明碼的監(jiān)督關(guān)系式為：

S2=a2+a4+a5+a6

S1=a1+a3+a5+a6

S0=a0+a3+a4+a6

接收碼字為："0011101"(n=7)求：發(fā)送端的信息碼。解：1)由漢明碼的監(jiān)督關(guān)系式計算得S2S1S0=011。

2)由監(jiān)督關(guān)系式可構(gòu)造出下面錯碼位置關(guān)系表：S2S1S0000001010100011101110111錯碼位置無錯a0a1a2a3a4a5a6

3)由S2S1S0=011查表得知錯碼位置是a3。

4)糾錯--對碼字的a3位取反得正確碼字："0010101"

5)把冗余碼a2a1a0刪除得發(fā)送端的信息碼："0010"

10.2線性分組碼10.2線性分組碼4.對一般線性分組碼的討論

1）在線性碼中信息位和監(jiān)督位滿足一組線性方程，或者說信息位和監(jiān)督位之間有某種線性變換關(guān)系,該線性方程規(guī)定了信息碼元與監(jiān)督碼元間的相互制約的關(guān)系,這個方程組（線性變換）叫做碼組的一致監(jiān)督方程或制約方程；

2）利用矩陣H可以表征碼字的特性，為此把H稱為線性碼的一致監(jiān)督矩陣,只要監(jiān)督矩陣H給定，編碼時監(jiān)督位和信息位的關(guān)系就完全被確定了；

3）線性碼具有封閉性，這是它的一個重要性質(zhì)；10.2線性分組碼4）H的行數(shù)就是監(jiān)督關(guān)系式的數(shù)目。它等于監(jiān)督位的數(shù)目m。H每行中的“1”的位置表示相應(yīng)碼元之間存在的關(guān)系式

5）信息位給定后，用信息位的行矩陣乘矩陣G就產(chǎn)生出監(jiān)督位；

6）如果找到了碼的生成矩陣G，則編碼的方法就完全確定了；

7）在線性碼中，碼組中的監(jiān)督碼元并不固定監(jiān)督某位或某幾位信息碼元，而是碼組中的所有監(jiān)督碼元共同監(jiān)督碼組中所有的信息碼元和監(jiān)督碼元。返回結(jié)束10.3循環(huán)碼

循環(huán)碼是另一類重要的線性分組碼，它除了具有線性碼的一般性質(zhì)外，還具有循環(huán)性，即循環(huán)碼組中任一碼組循環(huán)移位所得的碼組仍為該循環(huán)碼中的一許用碼組。在代數(shù)理論中，為了便于計算，常用碼多項式表示碼字。（n，k）循環(huán)碼的碼字

C=[c1,c2,…,cn-1,cn]

其碼多項式（以降冪順序排列）為

c(x)=c1xn-1+c2xn-2+…+cn-1x+cn碼組C移位1次得到C(1)仍是碼組，相應(yīng)的碼多項式c(1)(x)為c(1)(x)=c2xn-1+c3xn-2+…+cnx+c1上式正好是x·c

(x)

除以(xn+1)后的余式（可列豎式進(jìn)行驗算），即x·c

(x)=c1xn+c2xn-1+…+cn-1x2

+cnx+c1+c1=c1(

xn+1)+c(1)(x)

即x·c

(x)=c1(

xn+1)+c(1)(x)

10.3循環(huán)碼10.3循環(huán)碼碼組C移位2次得到C(2)仍是碼組，相應(yīng)的碼多項式c(2)(x)為c(2)(x)=c3xn-1+c4xn-2+…+c1x+c2上式正好是c(1)(x)移位1次而得到，因此利用前面結(jié)果，有x·c(1)(x)=c2(

xn+1)+c(2)(x)

x·[x·c

(x)=c1(

xn+1)]=c2

(

xn+1)+c(2)(x)

x2·c

(x)=(c1x+

c2)

(

xn+1)+c(2)(x)

即c(2)(x)正好是x2·c

(x)

除以(xn+1)后的余式10.3循環(huán)碼

以此類推。碼組C移位i次，相應(yīng)的碼多項式c(i)(x)是xi·c

(x)

除以(xn+1)后的余式。

因此在模(xn+1)意義下，若c(x)是碼多項式，則xi·c

(x)

都是碼多項式。循環(huán)碼的編碼過程也同樣可用多項式描述。一個k位的信息碼組

D=[d1,d2,…,dk

]可用信息多項式d

(x)

表示，有d(x)=d1xk-1+d2xk-2+…+dk-1x+dk如果已知d(x)，求解相應(yīng)的碼組多項式c(x)，就構(gòu)成了編碼問題。10.3循環(huán)碼假設(shè)碼組多項式可表示為c

(x)=d(x)·g

(x)

式中g(shù)(x)是(xn+1)的n-k次因式，稱為生成多項式。則c

(x)=[d1xk-1g

(x)

+d2xk-2g

(x)

+…+dk]g

(x)上式說明c(x)是一個不大于n-1次多項式。將式c

(x)=d(x)·g

(x)表示的碼多項式c(x)提高1次，得

x·c

(x)=x·d(x)·g

(x)上式是g(x)的倍式。10.3循環(huán)碼另一方面，由前面分析，有x·c

(x)=c1xn+c2xn-1+…+cn-1x2

+cnx=c1(

xn+1)+c(1)(x)因為前面已經(jīng)設(shè)定(

xn+1)

是g(x)

的倍式。所以c(1)(x)也是g(x)

的倍式。可以表達(dá)為

c(1)(x)=Q(x)·g

(x)式中Q(x)對應(yīng)于某個信息碼組。10.3循環(huán)碼以上分析過程說明用式c

(x)=d(x)·g

(x)

產(chǎn)生的碼組一定是循環(huán)碼。換言之，循環(huán)碼完全由其碼組長度n及生成多項式g(x)所決定，由于g(x)是一個能除盡(

xn+1)

的n-k次多項式，所以對(

xn+1)

進(jìn)行因式分解，便可得到相應(yīng)的g(x)。10.3循環(huán)碼例：求(7,4)循環(huán)碼的生成多項式g(x)。當(dāng)信息碼組D=[1010]時，求輸出碼組C。解:(1)由條件可知n=7,k=4,m=n-k=3，g(x)應(yīng)為(

x7+1)

的3次因式。對(

x7+1)

分解因式，有

x7+1=(

x+1)(x3+

x+1)(x3+

x2+1)得到2個生成多項式：

g1(x)

=x3+

x+1g2(x)

=x3+

x2+110.3循環(huán)碼

(2)

由式c

(x)=d(x)·g

(x)

可計算輸出碼組C。由于有2個生成多項式，經(jīng)計算可得到2個碼多項式和2個碼組，計算過程如下：

d(x)

=x3+

xc1

(x)=d(x)·g1(x)=(x3+

x)(x3+

x+1)=x6+

x3+

x2+xC1

=[1001110]

c2

(x)=d(x)·g2(x)=(x3+

x)(x3+

x2+1)=x6+

x5+

x4+x

C2

=[1110010]

[1100101]為許用碼組？循環(huán)碼是線性分組碼？10.3循環(huán)碼通常，由信息碼組D和生成多項式g(x)直接求出的碼組不是系統(tǒng)碼。在上例的結(jié)果中，碼組的前4位碼不是[1010]。為了得到系統(tǒng)循環(huán)碼，必須按照系統(tǒng)碼的規(guī)則表示碼組。根據(jù)系統(tǒng)碼的定義，碼組C的前k位是信息碼元，后m位是校驗碼元，用多項式可表示為

c

(x)=xn-kd(x)+r

(x)式中d(x)是不大于k-1次多項式，xn-kd(x)是不大于n-1次多項式，r

(x)是不大于m-1次多項式，稱r(x)為校驗位多項式。10.3循環(huán)碼用Q(x)代表某一個信息多項式，將碼組多項式表示為

c

(x)=Q

(x)·g

(x)Q

(x)是不大于k-1次多項式，g

(x)是不大于m-1次的生成多項式。與式c

(x)=xn-kd(x)+r

(x)

對照后可得

xn-kd(x)+r(x)=Q

(x)·g

(x)移項后為

xn-kd(x)

=Q

(x)·g

(x)+r

(x)10.3循環(huán)碼xn-kd(x)

=Q

(x)·g

(x)+r

(x)即10.3循環(huán)碼由上式可知，r(x)是xn-kd(x)

除以g(x)得到的余式，表示為例：用上例的生成多項式求系統(tǒng)循環(huán)碼的碼組，已知D=[1010]。解：當(dāng)g1(x)

=x3+

x+1

時，信息多項式和升位后的多項式分別為

d(x)

=x3+

x

x7-4

d(x)=x3(x3+

x)=x6+

x410.3循環(huán)碼求余式r(x)的豎式為

10.3循環(huán)碼余式和碼組多項式分別為

r(x)

=x+

1

c1

(x)=Q1(x)·g1(x)=(x3+

1)(x3+

x+1)=x6+

x4

+

x+1或

c

1(x)=xn-kd(x)+r

(x)=x7-4

(x3+

x)+x+

1=x6+

x4+x+

1可得系統(tǒng)循環(huán)碼碼組為

C1

=[1010011]10.3循環(huán)碼當(dāng)g2(x)

=x3+

x2+1

時，同樣方法可得

r(x)

=1

c2

(x)=x6+

x4

+

1C2

=[1010001]

由以上結(jié)果可以看出，用不同的生成多項式，都可以得到系統(tǒng)循環(huán)碼。

[1101000]為許用碼組？

10.3循環(huán)碼（2）循環(huán)碼的譯碼 由c(x)=Q(x)·g(x)可知，發(fā)送碼組多項式c(x)是生成多項式g(x)的倍式。如果經(jīng)信道傳輸后發(fā)生錯誤，接收碼組多項式R(x)不再是g(x)的倍式，可表示為或者寫成其中s(x)是R(x)除以g(x)后的余式，是不大于m-1次的碼組多項式，稱為伴隨多項式或校正子多項式。

10.3循環(huán)碼

接收碼組多項式R(x)可表示為發(fā)送碼組多項式與差錯多項式之和，即代入上式，得由s(x)就可進(jìn)一步確定E(x)。對于一個s(x)，E(x)可能有多種形式。由s(x)確定E(x)時同樣使用最大似然比準(zhǔn)則。10.3循環(huán)碼對最小碼重的差錯多項式E(x)，由求出對應(yīng)的伴隨多項式s(x)，將E(x)與s(x)的對應(yīng)關(guān)系列成譯碼表。當(dāng)收到任一碼組R(x)后，利用式求出s(x)，對照譯碼表找到E(x)，再用式求c(x)，即10.3循環(huán)碼

原則上糾錯可按下述步驟進(jìn)行：①用生成多項式g（x）去除接收碼組R（x）=c（x）+E（x），得出余式s（x）；②按余式s（x）用查表的方法或通過某種運算得到錯誤圖樣E（x），就可以確定錯碼位置。 ③從R（x）中減去E（x），便得到已糾正錯誤的原發(fā)送碼組c（x）。10.3循環(huán)碼例：已知糾單錯(7,4)系統(tǒng)循環(huán)碼的生成多項式為

g

(x)

=x3+

x2+1

，試構(gòu)成譯碼表。若接收碼組R=[1000101]，求發(fā)送碼組。解：對碼重為1的差錯多項式E(x)，求出相應(yīng)的伴隨多項式s(x)，將其對應(yīng)結(jié)果表成譯碼表，如下表所示。E(x)x6x5x4x3x2x1s

(x)x2+xx

+1

x2+x+1

x2+1x2x110.3循環(huán)碼當(dāng)接收碼組無錯誤時，E(x)=0，則s(x)=0。本題給出的接收碼組為

R=[1000101]由此可寫出接收碼組多項式

R

(x)

=x6+

x2+1對應(yīng)的伴隨多項式為10.3循環(huán)碼查表得到

E

(x)

=x5由R(x)和E(x)可得到譯碼碼組多項式相應(yīng)的碼組為

C=[1100101]由于是系統(tǒng)循環(huán)碼，所以信息碼組為

D=[1100]10.3循環(huán)碼10.4卷積碼

卷積碼又稱連環(huán)碼，是1955年提出來的一種糾錯碼，它和分組碼有明顯的區(qū)別，屬于非分組碼。1.基本概念 卷積碼編碼器在任何一段規(guī)定時間內(nèi)產(chǎn)生的n個碼元，不僅取決于這段時間中k個信息位，而且還取決于前N-1段規(guī)定時間內(nèi)的信息位。監(jiān)督位監(jiān)督著這N段時間內(nèi)的信息。這N段時間內(nèi)的碼元數(shù)目nN稱為這種碼的約束長度。卷積碼常用符號（n，k，N）表示。其編碼效率為：η=k/n10.4卷積碼簡單例子：下圖為一個卷積碼的編碼器。654321+輸入bi移位寄存器輸出bicib1b1c1b2c2b3c3b4c4b5c5b6c6b2b3b4b5b6輸入輸出卷積碼的參量：k=1,n=2,N=6。10.4卷積碼現(xiàn)討論卷積碼的解碼問題，這里介紹門限解碼。一般說來，卷積碼的譯碼可分為代數(shù)譯碼（利用編碼本身的代數(shù)結(jié)構(gòu)進(jìn)行解碼）和概率譯碼（解碼時要用到信道的統(tǒng)計特性）兩大類。

門限解碼是一種二進(jìn)制碼的擇多邏輯解碼法，屬于代數(shù)解碼。它利用一組正交校驗方程進(jìn)行計算。“正交”是指所解的信息位，作為校驗方程的一個元素，出現(xiàn)在這一方程組的每一方程中，而其他的信息位至多在一個方程中出現(xiàn)。這樣一來，就可以根據(jù)被錯碼破壞了的方程組中方程數(shù)目在方程組中是否占多數(shù)來判斷所待解的信息位是否錯了。對應(yīng)以上例子的門限解碼器如下圖。b6b5b4b3b2b1+輸入一級移位寄存器輸出信息移位寄存器S6S5S4S3S2S1+接收監(jiān)督位重算監(jiān)督位門限電路校正子移位寄存器+“1”的個數(shù)310.4卷積碼

由上圖可以看出，當(dāng)傳輸?shù)拇a發(fā)生第一個位錯時（且只有一位錯誤）：1）若錯碼為信息位，則僅當(dāng)它位于信息移存器中第6，3，2，1級時才使校正子等于“1”，因此，這時的校正子序列為100111；2）若錯碼為監(jiān)督位，校正子序列為100000。

可見，當(dāng)校正子序列中出現(xiàn)第一個“1”時，則表示已檢出一個錯碼。后面幾個校正子則指出是信息位錯了還是監(jiān)督位錯了。10.4卷積碼

按上圖電路連線，假定b1以前各碼均未發(fā)生錯誤，則校正子移存器各級中寄存的校正子值S可用下列邏輯方程組表示。10.4卷積碼其中上式經(jīng)過簡單線性變換，可以改寫為

這是一組正交于E(b1)的正交校驗方程。因為每個方程中均有一項E(b1)，而所有其它E(bi)和E(ci)項，在整個方程組中至多出現(xiàn)一次。10.4卷積碼

在所考查的12個碼元（b1至b6

，c1至c6

）中，在錯誤不多于2個的條件下，僅當(dāng)E(b1)=1，即b1出錯時，上述方程組才可能有3個以上方程等于1。將代表上式的4個方程的電壓送到一個門限電路累計“1”的個數(shù)，當(dāng)結(jié)果大于等于3時，門限電路輸出“1”。門限電路的這一輸出除了送到解碼器輸出端的一級移存器糾正輸出碼元b1的錯誤外，同時送到受E(b1)影響的各級校正子移存器糾正其中錯誤。10.4卷積碼2.卷積碼編碼

卷積碼常用符號（n，k，N）表示。其中，n為碼長，k為碼組中信息碼元的個數(shù)，N為相互關(guān)聯(lián)的碼組的個數(shù)。 卷積碼同樣也可以用矩陣的方法描述，但較抽象。因此，采用圖解的方法直觀描述其編碼過程。常用的圖解法有3種：樹圖、狀態(tài)圖和格圖。10.4卷積碼（1）樹圖樹圖描述的是在任何數(shù)據(jù)序列輸入時，碼字所有可能的輸出。下圖所示是一種（2，1，3）卷積碼的編碼器。b3b2b1c1c210.4卷積碼圖中，m1與m2為移位寄存器，它們的初態(tài)均為0，即b1b2b3為000。c1，c2與b1，

b2，

b3的關(guān)系如下：

c1=b1b2b3c2=b1b3b1代表當(dāng)前輸入信息位,而移位寄存器狀態(tài)b3b2存儲以前信息位(當(dāng)前寄存器m1=b1,m2=b2)。下表舉例示出此編碼器的狀態(tài)。+++b111010000b3b2c1c2狀態(tài)0011a0101b1101d1000c0110b1011c0000a0000a10.4卷積碼當(dāng)?shù)?位信息為1時，即b1=1，因b3b2=00，故輸出碼元c1c2=11；第2位信息為1，這時b1=1，b3b2=01，c1c2=01，依此類推。為保證輸入的全部信息位11010都能通過移存器，還必須在信息位加3個零?，F(xiàn)在我們來分析卷積碼的樹狀圖。

(下例以b1=0,b3b2=00為起點)卷積碼的樹圖上圖對應(yīng)的（2,1,3）卷積碼的樹圖如下圖所示00111001110001100011100111000110aa=00b3b2b=01c=10d=11狀態(tài)

00000011100111000110011011起點

0111abc1c2abcdabcdabcdabcdabcdabcdabcd輸出碼元序列為1101010010.4卷積碼上圖中，當(dāng)?shù)?位信息b1=1時，碼元c1c2為11，則狀態(tài)從起點a通過下支路到達(dá)狀態(tài)b；當(dāng)?shù)?位信息b1=0時，碼元c1c2為00，則狀態(tài)從起點a通過上支路到達(dá)狀態(tài)a。依此類推可求得整個碼樹狀圖。由該圖可以看出，從第4條支路開始，碼樹呈現(xiàn)出重復(fù)性，即圖中標(biāo)明的上半部與下半部完全相同。這就意味著從第4位信息開始，輸出碼元已與第1位信息無關(guān)。這正說明前一圖所示的編碼器的編碼約束長度為6的含義。當(dāng)輸入信息位為11010時，在樹圖中用虛線標(biāo)出了其軌跡，并得到輸出碼元序列為11010100…?？梢姡摻Y(jié)果與前一表的結(jié)果是一致的。10.4卷積碼（2）狀態(tài)圖除了用樹圖表示編碼器的工作過程外，還可以用狀態(tài)圖來描述。下圖所示的是該（2，1，3）卷積編碼器當(dāng)前狀態(tài)與下一狀態(tài)的關(guān)系。線旁數(shù)字為輸出碼元，節(jié)點表示狀態(tài)。當(dāng)前狀態(tài)下一狀態(tài)0000=a

01=b10=

c11=

da=00b=01c=10d=11111100100110信息為“1”信息為“0”10.4卷積碼10.4卷積碼卷積碼的狀態(tài)圖下圖所示的是該（2，1，3）卷積編碼器的狀態(tài)圖。10.4卷積碼（3）格圖格圖也稱網(wǎng)絡(luò)圖或籬笆圖，它由狀態(tài)圖在時間上展開而得到，如下圖，對于各種可能輸入，畫出了狀態(tài)轉(zhuǎn)移的全部可能軌跡。起點00a=00b=01c=10d=11110110101010010101000000001111111111111100000010101001010110.4卷積碼

以上3種圖解方法不僅有助于求解卷積碼的輸出序列，了解編碼過程，而且對研究解碼方法也非常有用。例：卷積編碼器如下圖所示，初態(tài)為a，輸入比特序列為110100，求輸出序列和狀態(tài)變化路徑。b3b2b1c1c210.4卷積碼解：c1，c2與b1，

b2，

b3的關(guān)系如下：

c1=b1b2b3c2=b1b3卷積碼的網(wǎng)格圖如下圖。+++起點00a=00b=01c=10d=11110110101010010101000000001111111111111100000010101001010110.4卷積碼當(dāng)輸入比特序列為110100時，找出編碼時網(wǎng)格圖中的路徑如下圖所示。由此可得到輸出序列和狀態(tài)變化路徑。

a=00b=01c=10d=11輸入碼1101001101010010輸出碼110101001011狀態(tài)abdcbca1110.4卷積碼3.卷積碼的譯碼 前面已經(jīng)提到卷積碼的解碼一般有兩類，它們分別是：代數(shù)解碼和概率解碼。卷積碼不是分組碼，但仍屬于線性碼，同樣可由生成矩陣G和監(jiān)督矩陣H來確定。代數(shù)譯碼就是利用生成矩陣和監(jiān)督矩陣來譯碼。 下面我們再來簡要討論卷積碼的概率解碼。這種解碼最早始于1961年由烏曾格來夫（Wozencrxft）提出的序列解碼。1963年費諾（Fano）對序列解碼的改進(jìn)，提出了費諾算法，從而推動了序列解碼的實際應(yīng)用。10.4卷積碼（1）維特比譯碼

1967年Viterbi提出了另一種概率解碼算法簡稱VB算法。在碼的束長度較小時，它比序列解碼算法效率要高、速度要快，解碼器也較簡單，因而廣泛地應(yīng)用于各種數(shù)字通信系統(tǒng)，特別是衛(wèi)星通信系統(tǒng)中。在卷積碼解碼方法中，有一類最大似然算法，它的基本想法是：把接收序列與所有可能的發(fā)送序列比較，選擇一種碼距最小的序列作為發(fā)送序列。如果發(fā)送一個k位序列，則有2k種可能序列，計算機應(yīng)存儲這些序列，以便用作比較。當(dāng)k較大時，存儲量太大，受到限制。Viterbi對最大似然解碼作了簡化，使之實用化。10.4卷積碼

這里，僅就Viterbi解碼的思路作一簡要介紹。

下面我們?nèi)杂孟聢D所示的（2,1,3）編碼器所編出的卷積碼為例，來說明Viterbi解碼方法的思路。

b3b2b1c1c210.4卷積碼

當(dāng)發(fā)送信息序列為11010時，為了使全部信息位能通過編碼器，在發(fā)送信息序列后面加上了3個零。使輸入編碼器的信息序列變?yōu)?101000。計算的結(jié)果如下表。b111010000b3b2c1c2狀態(tài)0011a0101b1101d1000c0110b1011c0000a0000a由此可得編碼器輸出的序列為1101010010110000，移位寄存器的狀態(tài)轉(zhuǎn)移為a→b→d→c→b→c→a→a，最后回到a。10.4卷積碼假設(shè)接收序列有差錯，變成0101011010010001?，F(xiàn)在對照網(wǎng)格圖來說明解碼步驟和方法。起點00a=00b=01c=10d=111101101010100101010000000011111111111111000000101010010101

由于該卷積的編碼約束長度為6，故先選前3段接收序列010101作為標(biāo)準(zhǔn)，與到達(dá)第3級的4個節(jié)點的8條路徑進(jìn)行對照，逐步算出每條路徑與作為標(biāo)準(zhǔn)的接收序列010101之間的累計碼距。由網(wǎng)格圖可得下表。到達(dá)第3級節(jié)點路徑與010101之間的碼距幸存路徑a00000011101134000000b00001111100034000011c00111011010141110101d00110111011023001101這些路徑如下圖中所示的到達(dá)第3級節(jié)點a,b,c和d

。級012345678起點a=00b=01c=10d=11001101101001000000111111110010100100101000011101解碼11010000收碼

01

01011010010001發(fā)碼

11

01010010110000若將當(dāng)前節(jié)點移到第4級，同樣也有8條路徑。由網(wǎng)格圖可得下表。到達(dá)第4級節(jié)點路徑與01010110之間的碼距幸存路徑a00000000

110101114211010111b0000001111010100

3211010100c00001110001101013400001110d0011011000001101

2400110110這些路徑到達(dá)第4級節(jié)點a,b,c和d

。10.4卷積碼（2）序列譯碼 當(dāng)m很大時，可以采用序列譯碼法。其過程如下。譯碼先從碼樹的起始節(jié)點開始，把接收到的第一個子碼的n個碼元與自始

逐步推進(jìn)篩選幸存路徑，到第7級時，只要選出到達(dá)節(jié)點a和c的兩條路徑即可，因為到達(dá)終點a只可能從第7級的節(jié)點a或c出發(fā)。最后得到了到達(dá)終點a的一條幸存路徑，即為解碼路徑，如圖中紅線所示。根據(jù)這條路徑，對照網(wǎng)格圖可知解碼結(jié)果為11010000，與發(fā)送信息序列一致。10.4卷積碼節(jié)點出發(fā)的兩條分支按照最小漢明距離進(jìn)行比較，沿著差異最小的分支走向第二個節(jié)點。在第二個節(jié)點上，譯碼器仍以同樣原理到達(dá)下一個節(jié)點，依此類推，最后得到一條路徑。若接收碼組有錯，則自某節(jié)點開始，譯碼器就一直在不正確的路徑中行進(jìn)，譯碼也一直錯誤。因此，譯碼器有一個門限值，當(dāng)接收碼元與譯碼器所走的路徑上的碼元之間的差異總數(shù)超過門限值時，譯碼器判定有錯，并且返回試走另一分支。經(jīng)數(shù)次返回找出一條正確的路徑，最后譯碼輸出。10.5網(wǎng)格編碼調(diào)制（TCM）

前面討論的數(shù)字通信系統(tǒng)中，差錯控制編碼和調(diào)制是分開設(shè)計和考慮的。編碼增益是依靠降低信息傳輸速率或增加系統(tǒng)帶寬來獲得，多進(jìn)制數(shù)字調(diào)制系統(tǒng)的整體性能無法達(dá)到最佳。1974年梅西（Messey）根據(jù)Shannon信息論，證明了把編碼與調(diào)制作為一個整體考慮時，可明顯改善通信系統(tǒng)的性能。1982年，昂格爾博克（Ungerbook）提出了編碼（卷積碼）與調(diào)制相結(jié)合的網(wǎng)格編碼調(diào)制（TrellisCodedModulation，TCM）。10.5網(wǎng)格編碼調(diào)制（TCM） TCM技術(shù)是利用編碼效率為n/（n+1）的卷積碼，并將每一碼段映射為2n+1個調(diào)制信號集中的一個信號，使信號點之間相互依賴。目前，TCM技術(shù)已經(jīng)得到廣泛的應(yīng)用，它不僅用于高速的調(diào)制解調(diào)中，而且還用于衛(wèi)星通信、移動通信以及擴(kuò)頻通信等多個領(lǐng)域中。10.5網(wǎng)格編碼調(diào)制（TCM）TCM技術(shù)有兩個基本特點。（1）在信號空間中的信號點數(shù)目比無編碼的調(diào)制情況下對應(yīng)的信號點數(shù)目要多，這些增加的信號點使編碼有了冗余，而不犧牲帶寬。（2）采用卷積碼的編碼規(guī)則，使信號點之間引入相互依賴關(guān)系。僅有某些信號點圖樣或序列是允許用的信號序列，并可模型化成為網(wǎng)格狀結(jié)構(gòu)，因此又稱為“格狀”編碼。在收端采用維特比算法執(zhí)行最大似然檢測。（1）TCM編碼器結(jié)構(gòu)選擇信號子集中信號點選擇信號子集卷積碼編碼器信號點集合劃分映射未編碼的k個信息比特n=k+1個比特未編碼的k-k個信息比特}}

昂格爾博克提出的TCM編碼方案是通過“集合劃分映射”的方法，將卷積碼編碼器對信息碼元的編碼轉(zhuǎn)化為對星座圖中信號的編碼，在接收端采用維特比譯碼算法進(jìn)行判決。TCM編碼器結(jié)構(gòu)10.5網(wǎng)格編碼調(diào)制（TCM）（2）歸一化歐幾里德距離任意兩個信號點（信號序列）之間的距離，稱為歸一化歐幾里得距離，簡稱為歐氏距離，其中所有兩個信號點（信號序列）之間的最小歐氏距離稱為歐氏自由距離，記為dfree。下圖為8PSK信號的星座圖。0010100000111001011101111012310.5網(wǎng)格編碼調(diào)制（TCM）

歐氏自由距離越大，錯誤判決的概率越小。因此在TCM編碼時要尋找具有最大的歐氏自由距離編碼信號序列。在多進(jìn)制系統(tǒng)中，漢明距離和歐氏距離并不等價。10.5網(wǎng)格編碼調(diào)制（TCM）（3）信號點集的劃分在TCM編碼中，通過對信號點集的劃分，建立卷積碼編碼器輸出的編碼與星座圖上的信號點之間的映射關(guān)系。信號點集的劃分是指把星座圖上所有信號點組成的集合不斷地分解為2,4,