第十章差錯(cuò)控制

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

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

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

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

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

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

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

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

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

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

線性分組碼是一類重要的糾錯(cuò)碼，應(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階矩陣，各行也是線性無(wú)關(guān)的。

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

Wmin=3因此，①檢測(cè)e個(gè)隨機(jī)錯(cuò)誤，則要求最小碼距dmin≥e+1；②糾正t個(gè)隨機(jī)錯(cuò)誤，則要求最小碼距dmin≥2t+1；③糾正t個(gè)同時(shí)檢測(cè)e（e＞t）個(gè)隨機(jī)錯(cuò)誤，則要求最小碼距dmin≥t+e+1?？芍?，該碼有檢2錯(cuò)，或糾1錯(cuò)，或糾1錯(cuò)同時(shí)檢1錯(cuò)的能力。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)督矩陣，或稱一致校驗(yàn)矩陣，一旦H給定，信息位和監(jiān)督位之間的關(guān)系也就確定了。H為m×n階矩陣，H矩陣每行之間是彼此線性無(wú)關(guān)的。H矩陣可分成兩部分，其中P為k×m階矩陣，Im為m×m階單位陣。能寫成H=［PTIm］形式的矩陣稱為典型監(jiān)督矩陣。10.2線性分組碼

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

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

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

S=EHT解出E矢量。由得

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

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

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

C=RE=[111011][010000]

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

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

碼組為漢明碼時(shí)取等號(hào)。即用來(lái)糾正單個(gè)錯(cuò)誤時(shí)，漢明碼所用的監(jiān)督碼元個(gè)數(shù)最少，效率最高。10.2線性分組碼漢明碼的特點(diǎn)如下：（1）監(jiān)督碼元的個(gè)數(shù)m=n-k，碼長(zhǎng)滿足n=2m-1，k=n-m。m≥2。（2）無(wú)論碼長(zhǎng)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)系式計(jì)算得S2S1S0=011。

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

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

4)糾錯(cuò)--對(duì)碼字的a3位取反得正確碼字："0010101"

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

10.2線性分組碼10.2線性分組碼4.對(duì)一般線性分組碼的討論

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

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

3）線性碼具有封閉性，這是它的一個(gè)重要性質(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ù)理論中，為了便于計(jì)算，常用碼多項(xiàng)式表示碼字。（n，k）循環(huán)碼的碼字

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

其碼多項(xiàng)式（以降冪順序排列）為

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

(x)

除以(xn+1)后的余式（可列豎式進(jìn)行驗(yà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)的碼多項(xià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)的碼多項(xiàng)式c(i)(x)是xi·c

(x)

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

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

(x)

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

D=[d1,d2,…,dk

]可用信息多項(xiàng)式d

(x)

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

(x)=d(x)·g

(x)

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

(x)=[d1xk-1g

(x)

+d2xk-2g

(x)

+…+dk]g

(x)上式說(shuō)明c(x)是一個(gè)不大于n-1次多項(xiàng)式。將式c

(x)=d(x)·g

(x)表示的碼多項(xiàng)式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)因?yàn)榍懊嬉呀?jīng)設(shè)定(

xn+1)

是g(x)

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

的倍式?？梢员磉_(dá)為

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

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

(x)=d(x)·g

(x)

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

xn+1)

的n-k次多項(xiàng)式，所以對(duì)(

xn+1)

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

x7+1)

的3次因式。對(duì)(

x7+1)

分解因式，有

x7+1=(

x+1)(x3+

x+1)(x3+

x2+1)得到2個(gè)生成多項(xiàng)式：

g1(x)

=x3+

x+1g2(x)

=x3+

x2+110.3循環(huán)碼

(2)

由式c

(x)=d(x)·g

(x)

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

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和生成多項(xiàng)式g(x)直接求出的碼組不是系統(tǒng)碼。在上例的結(jié)果中，碼組的前4位碼不是[1010]。為了得到系統(tǒng)循環(huán)碼，必須按照系統(tǒng)碼的規(guī)則表示碼組。根據(jù)系統(tǒng)碼的定義，碼組C的前k位是信息碼元，后m位是校驗(yàn)碼元，用多項(xiàng)式可表示為

c

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

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

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

c

(x)=Q

(x)·g

(x)Q

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

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

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

(x)

對(duì)照后可得

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

(x)·g

(x)移項(xiàng)后為

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)得到的余式，表示為例：用上例的生成多項(xiàng)式求系統(tǒng)循環(huán)碼的碼組，已知D=[1010]。解：當(dāng)g1(x)

=x3+

x+1

時(shí)，信息多項(xiàng)式和升位后的多項(xiàng)式分別為

d(x)

=x3+

x

x7-4

d(x)=x3(x3+

x)=x6+

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

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

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

時(shí)，同樣方法可得

r(x)

=1

c2

(x)=x6+

x4

+

1C2

=[1010001]

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

[1101000]為許用碼組？

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

10.3循環(huán)碼

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

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

g

(x)

=x3+

x2+1

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

(x)x2+xx

+1

x2+x+1

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

R=[1000101]由此可寫出接收碼組多項(xiàng)式

R

(x)

=x6+

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

E

(x)

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

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

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

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

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

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

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

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

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

在所考查的12個(gè)碼元（b1至b6

，c1至c6

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

卷積碼常用符號(hào)（n，k，N）表示。其中，n為碼長(zhǎng)，k為碼組中信息碼元的個(gè)數(shù)，N為相互關(guān)聯(lián)的碼組的個(gè)數(shù)。 卷積碼同樣也可以用矩陣的方法描述，但較抽象。因此，采用圖解的方法直觀描述其編碼過(guò)程。常用的圖解法有3種：樹(shù)圖、狀態(tài)圖和格圖。10.4卷積碼（1）樹(shù)圖樹(shù)圖描述的是在任何數(shù)據(jù)序列輸入時(shí)，碼字所有可能的輸出。下圖所示是一種（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存儲(chǔ)以前信息位(當(dāng)前寄存器m1=b1,m2=b2)。下表舉例示出此編碼器的狀態(tài)。+++b111010000b3b2c1c2狀態(tài)0011a0101b1101d1000c0110b1011c0000a0000a10.4卷積碼當(dāng)?shù)?位信息為1時(shí)，即b1=1，因b3b2=00，故輸出碼元c1c2=11；第2位信息為1，這時(shí)b1=1，b3b2=01，c1c2=01，依此類推。為保證輸入的全部信息位11010都能通過(guò)移存器，還必須在信息位加3個(gè)零。現(xiàn)在我們來(lái)分析卷積碼的樹(shù)狀圖。

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

00000011100111000110011011起點(diǎn)

0111abc1c2abcdabcdabcdabcdabcdabcdabcd輸出碼元序列為1101010010.4卷積碼上圖中，當(dāng)?shù)?位信息b1=1時(shí)，碼元c1c2為11，則狀態(tài)從起點(diǎn)a通過(guò)下支路到達(dá)狀態(tài)b；當(dāng)?shù)?位信息b1=0時(shí)，碼元c1c2為00，則狀態(tài)從起點(diǎn)a通過(guò)上支路到達(dá)狀態(tài)a。依此類推可求得整個(gè)碼樹(shù)狀圖。由該圖可以看出，從第4條支路開(kāi)始，碼樹(shù)呈現(xiàn)出重復(fù)性，即圖中標(biāo)明的上半部與下半部完全相同。這就意味著從第4位信息開(kāi)始，輸出碼元已與第1位信息無(wú)關(guān)。這正說(shuō)明前一圖所示的編碼器的編碼約束長(zhǎng)度為6的含義。當(dāng)輸入信息位為11010時(shí)，在樹(shù)圖中用虛線標(biāo)出了其軌跡，并得到輸出碼元序列為11010100…?？梢?jiàn)，該結(jié)果與前一表的結(jié)果是一致的。10.4卷積碼（2）狀態(tài)圖除了用樹(shù)圖表示編碼器的工作過(guò)程外，還可以用狀態(tài)圖來(lái)描述。下圖所示的是該（2，1，3）卷積編碼器當(dāng)前狀態(tài)與下一狀態(tài)的關(guān)系。線旁數(shù)字為輸出碼元，節(jié)點(diǎn)表示狀態(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)圖在時(shí)間上展開(kāi)而得到，如下圖，對(duì)于各種可能輸入，畫(huà)出了狀態(tài)轉(zhuǎn)移的全部可能軌跡。起點(diǎn)00a=00b=01c=10d=11110110101010010101000000001111111111111100000010101001010110.4卷積碼

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

b2，

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

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

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

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

這里，僅就Viterbi解碼的思路作一簡(jiǎn)要介紹。

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

b3b2b1c1c210.4卷積碼

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

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

。級(jí)012345678起點(diǎn)a=00b=01c=10d=11001101101001000000111111110010100100101000011101解碼11010000收碼

01

01011010010001發(fā)碼

11

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

110101114211010111b0000001111010100

3211010100c00001110001101013400001110d0011011000001101

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

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

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

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

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

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