第9章-差錯(cuò)控制編碼-

通信原理電子教案

第9章

差錯(cuò)控制編碼

陜西科技大學(xué)2/1/20231研究的問(wèn)題

9.1

引言9.2糾錯(cuò)編碼的基本原理9.3

常用的簡(jiǎn)單編碼9.3

線性分組碼9.4

循環(huán)碼9.5

卷積碼9.6網(wǎng)格編碼調(diào)制2/1/20232干擾乘性：均衡加性：調(diào)制解調(diào)體制、發(fā)送功率、最佳接收9.1引言

一、編碼問(wèn)題的提出

由于數(shù)字信號(hào)在傳輸過(guò)程中必不可免的受到干擾的影響，使碼元波形變壞，故傳輸?shù)浇邮斩撕罂赡馨l(fā)生錯(cuò)判。信道譯碼檢/糾錯(cuò)編碼若還不行，則需－－差錯(cuò)控制編碼。目的：在數(shù)字通信系統(tǒng)中，為了提高數(shù)字信號(hào)傳輸?shù)挠行远扇〉木幋a稱為信源編碼；為了提高數(shù)字通信的可靠性而采取的編碼稱為信道編碼。差錯(cuò)可控2/1/20233二、錯(cuò)誤的類型隨機(jī)性錯(cuò)誤（白噪聲引起） 特點(diǎn)：?jiǎn)蝹€(gè)錯(cuò)，錯(cuò)誤之間不相關(guān)。主要出現(xiàn)在無(wú)記憶信道。2.突發(fā)性錯(cuò)誤(脈沖干擾引起） 特點(diǎn)：成串錯(cuò)，錯(cuò)誤之間有相關(guān)性。主要出現(xiàn)在有記憶信道。錯(cuò)誤傳播。3.混合性錯(cuò)誤2/1/20234三、差錯(cuò)控制的方式1.檢錯(cuò)重發(fā)(ARQ)收發(fā)可檢錯(cuò)的碼特點(diǎn):

1）雙向通道

2）通信效率低

3）不適于實(shí)時(shí)通信

4）編、譯碼設(shè)備簡(jiǎn)單

5）編碼效率高總碼元

(nbit)=

信元(kbit)+督元(r

bit)。只檢不糾，有錯(cuò)自動(dòng)要求重發(fā)。2/1/202352.前向糾錯(cuò)(FEC)收發(fā)可糾錯(cuò)的碼特點(diǎn)：

1）只需單向信道－－省信道！

2）通信效率高；

3）適于實(shí)時(shí)傳輸；

4)譯碼設(shè)備復(fù)雜。檢錯(cuò)并糾錯(cuò)2/1/202363.反饋檢驗(yàn)法收發(fā)原理：收端將信碼原封不動(dòng)地轉(zhuǎn)發(fā)回發(fā)端，并與原發(fā)送信碼相比較：發(fā)現(xiàn)錯(cuò)－－重發(fā)；否則：PASS特點(diǎn):

需要雙向通道；收發(fā)設(shè)備簡(jiǎn)單；傳輸效率低（最低）。2/1/202379.2糾錯(cuò)編碼的基本原理

一.基本思想信元督元信元督元……信元和督元有一的函數(shù)關(guān)系，插入督元的過(guò)程就是一種編碼的過(guò)程，接收端可檢錯(cuò)糾錯(cuò)。顯然，傳輸效率↓（引入冗余碼）例：天氣預(yù)報(bào)信元督元

000晴

011云

101陰

110雨三位碼元有23=8種組合，實(shí)際使用了22=4種－－許用碼組。其余001，010，100，111

為禁用碼組。檢錯(cuò)能力：可檢錯(cuò)奇數(shù)個(gè)錯(cuò)；糾錯(cuò)能力：無(wú)。2/1/20238例：天氣預(yù)報(bào)，可預(yù)報(bào)天晴信元督元

000111冗余量加大，禁用碼組比例提高。檢錯(cuò)能力：檢2；糾錯(cuò)能力：糾1。許用碼組2個(gè)，禁用碼組6個(gè)晴陰2/1/20239二.糾錯(cuò)編碼的分類線性碼和非線性碼分組碼、卷積碼和循環(huán)碼系統(tǒng)碼和非系統(tǒng)碼三.分組碼定義:將信息碼分組，為每信息碼附加若干個(gè)監(jiān)督碼編碼，稱為分組碼。特點(diǎn):

在分組碼中，監(jiān)督碼元僅監(jiān)督本碼組中的信息碼元。符號(hào):(n,k),r=n–k碼字:結(jié)構(gòu):an-1an-2…arar-1…a0k個(gè)信元r個(gè)督元碼長(zhǎng)－－n2/1/202310碼組的重量和碼距及糾錯(cuò)能力1.重量碼組中非0元素的個(gè)數(shù)例:A=(10110)碼重=32.碼距

兩兩碼組對(duì)應(yīng)位上數(shù)值不同的個(gè)數(shù)，記為d。最小碼距:

某種編碼中各個(gè)碼組間距離的最小值，記做d0

d0=dmin碼距的幾何意義:(n=3)各頂點(diǎn)沿立方體各邊行走的幾何距離。碼元值：每一碼組的三個(gè)碼元值，就是此立方體各頂點(diǎn)的座標(biāo)（a2a1a0）最小碼距:

12/1/202311前例中：天氣預(yù)報(bào)信元督元

000晴

011云

101陰

110雨四個(gè)許用碼組之間的距離均為2。Why?擯棄d=1的碼－－禁用碼組。許用碼組最小碼距愈大，抗干擾能力愈強(qiáng)！確定最小碼距的目的：決定編碼的檢糾錯(cuò)能力。2/1/2023123.d0與糾檢錯(cuò)能力若要求檢測(cè)e個(gè)錯(cuò),則d0≧e+1

若要求糾正t個(gè)錯(cuò),則d0≧2t+1

若要檢測(cè)e糾正t

個(gè)錯(cuò)(同時(shí)),則

d0>e+t+1,

且e>t碼距與檢錯(cuò)和糾錯(cuò)能力的關(guān)系如圖：t1te2/1/2023130123Ad0(a)012345ABttd0(b)ABt1te(c)圖9-42/1/202314

9.3常用的簡(jiǎn)單編碼

－－屬于分組碼一類。簡(jiǎn)單、實(shí)用。

一.奇偶監(jiān)督碼

滿足:

偶監(jiān)督碼：碼組中1的個(gè)數(shù)為偶數(shù)；奇監(jiān)督碼：碼組中1的個(gè)數(shù)為奇數(shù)。檢錯(cuò)能力:

所有奇數(shù)個(gè)錯(cuò)。一半！應(yīng)用非常多。編碼效率:2/1/202315二維奇偶監(jiān)督碼

－－進(jìn)行橫、縱向監(jiān)督例:00001111010100110101000000110101101010橫向監(jiān)督縱向監(jiān)督糾檢錯(cuò)能力:

仍可檢錯(cuò)奇數(shù)個(gè)錯(cuò)還可檢錯(cuò)偶數(shù)個(gè)錯(cuò)可糾正一些錯(cuò)碼●適于檢測(cè)突發(fā)性錯(cuò)誤2/1/202316橫比碼(等重碼)例:碼重為31.010111100110110許用碼組:C35=10禁用碼組:25-10=22檢錯(cuò)能力:可檢測(cè)所有奇數(shù)個(gè)碼元的錯(cuò) 和部分偶數(shù)個(gè)碼元的錯(cuò),但不能檢測(cè)碼組中“1”變?yōu)椤?”與“0”變?yōu)椤?”的錯(cuò)碼數(shù)目相同的那些偶數(shù)錯(cuò)碼編碼效率:2/1/202317例：n=10,則k=5信元碼監(jiān)督碼合成碼校驗(yàn)碼1011010110000000000010001011101111100000●接受端的檢測(cè)三.正反碼編碼規(guī)則:●信息位(n/2)中有奇數(shù)個(gè)“1”,則監(jiān)督位與信息位相同●信息位(n/2)中有偶數(shù)個(gè)“1”,則監(jiān)督位是信息位的反碼2/1/202318

9.4線性分組碼定義：若分組碼（n,k）,督元與信元的關(guān)系可用一線性方程組來(lái)描述，則該分組碼（n,k）稱為線性分組碼。一、漢明碼－－能糾一位錯(cuò)的線性分組碼。定義：是一種能糾正一位錯(cuò)碼，且編碼效率較高的線性分組碼。最小碼距：d0=31.構(gòu)造原理考察：定義一個(gè)監(jiān)督方程（監(jiān)督關(guān)系式、偶監(jiān)督）：由于一位校正子只有兩種取值，故只能表示有錯(cuò)或無(wú)錯(cuò)，不能指出錯(cuò)碼的位置。2/1/202319推想:如果監(jiān)督位增加一位（即變成兩位），則可增加一個(gè)類似于上式的監(jiān)督關(guān)系，即可獲得兩個(gè)校正子，于是可有S1S20001011－－無(wú)錯(cuò)可指示一個(gè)錯(cuò)碼可能出現(xiàn)的位置，共有22-1=3個(gè)位置。2/1/202320再推廣:S1S2……Sr00…….000…….1………………11….11－－無(wú)錯(cuò)2r-1

個(gè)錯(cuò)的可能位置顯然：要求2r-1≥n（n=k+r），則可指示（僅一位錯(cuò)時(shí)）任一錯(cuò)碼的位置－－包括信元、督元。 或： 2r≥k+r+1－－可指示一個(gè)錯(cuò)碼可能出現(xiàn)的2r-1個(gè)位置。2/1/2023212.例:構(gòu)造k=4的漢明碼（1）確定r由2r≥k+r+1

得r=3，則n=

k+r=7－－

(7,4)

分組碼2/1/202322（2）寫出校正子的編碼表

r=3

共有3個(gè)校正子

S1S2S3

錯(cuò)碼位置S1S2S3

錯(cuò)碼位置001a0101a4

010a1110a5100a2111a6

011a3

000無(wú)錯(cuò)（3）由校正子編碼表得監(jiān)督方程組－－校正子和哪些碼元構(gòu)成偶監(jiān)督關(guān)系若S1S2S3=000

時(shí),即無(wú)錯(cuò)－－得校驗(yàn)方程:偶監(jiān)督關(guān)系2/1/202323得校驗(yàn)方程:即實(shí)際上確定了督元和信元之間的關(guān)系:校驗(yàn)方程督～信關(guān)系－－有了校正子編碼表，督元不是隨便選的?。?）給定了信元a6a5a4a3,可由“督～信關(guān)系”確定督元－－全部(7,4)碼組。2/1/202324（4）給定了信元a6a5a4a3,可確定督元－－全部(7,4)碼組2/1/202325二.線性分組碼1.線性方程組和監(jiān)督方程寫成矩陣式:111010011010101011001a6a5a4a3a2a1a02/1/202326可見(jiàn)：H一旦確定，督元和信元之間的關(guān)系也就確定了。若:則稱H為典型陣，一般，H總可以化為典型陣。111010011010101011001a6a5a4a3a2a1a02/1/2023272.生成矩陣矩陣形式:－－從督信方程入手由2/1/202328寫成行陣形式:其中Q=PT。上式表明：信息位給定后，就產(chǎn)生了監(jiān)督位！進(jìn)一步，令生成矩陣

G=[Ik

Q]則，碼組行陣 A=[a6a5a4a3]G2/1/202329例：生成矩陣討論：●由具有

[Ik

Q]形式的生成矩陣稱為典型生成陣。●由典型生成矩陣得出的碼組A中，信息位不變，監(jiān)督位附加其后－－這種碼稱為系統(tǒng)碼。碼組行陣：2/1/202330一般形式:

A=[an-1an-2…ar]G3.G和H的關(guān)系由Q=PT

或P=QT

則:H=[P·Ir

]G=[Ik

·Q]綜上：線性分組碼的編碼，就是根據(jù)其監(jiān)督陣H或生成陣G將長(zhǎng)為k的信息碼編成長(zhǎng)為n的碼組。2/1/2023314.線性分組碼的糾錯(cuò)譯碼過(guò)程－－怎樣由含有錯(cuò)誤的接收碼組中的接收碼組中恢復(fù)正確。

（1）錯(cuò)誤圖樣設(shè)：發(fā)碼組為A,接受碼組為B

則 B–A=E(模2)－－錯(cuò)誤行陣或錯(cuò)誤圖樣：

E=[en-1en-2……e0]例:A=[1111111]B=[1001101]

則E=[0110010]2/1/202332（2）校正子（或稱譯碼伴隨式）B=A+E

代入上式，得結(jié)論：校正子S僅于錯(cuò)誤圖案有關(guān)，與發(fā)送碼組無(wú)關(guān)。2/1/202333由收到的碼組B，按式：BHT=S→S由S=ET

→

E按B+E=A

→

A由A

→原始信息（3）糾錯(cuò)譯碼過(guò)程

2/1/2023345.線性分組碼的重要性（1）封閉性

設(shè)：

A1、A2

分別為一線性分組碼的任意兩個(gè)許用碼組。則：A1+A2

仍為該線性分組碼的許用碼組。證：由假設(shè)知 A1HT=0、A2HT=0

所以 A1HT+A2HT=（A1+A2）HT＝0

即A1+A2也是一個(gè)碼組。結(jié)論：線性碼組中任意兩個(gè)碼字之和，仍為該線性碼組之碼字。（2）線性分組碼的最小碼距即為該碼的最小重量: d0=Wmin（除全0碼組）證：由封閉性得，兩個(gè)碼組之間的距離（之差），必是另一碼組的重量。故最小碼距即是碼的最小重量！2/1/202335

9.5循環(huán)碼

－－仍屬于線性分組碼

特點(diǎn):

編譯碼設(shè)備簡(jiǎn)單，檢糾錯(cuò)能力強(qiáng)。

9.5.1循環(huán)碼的原理

具有線性分組碼的所有性質(zhì)之外，還具有循環(huán)性：循環(huán)碼中任一許用碼組經(jīng)過(guò)循環(huán)移位后，所得到的碼組仍然是許用碼組。2/1/202336碼多項(xiàng)式T(x)（1）定義－－為了利用代數(shù)理論研究循環(huán)碼，可以將碼組用代數(shù)多項(xiàng)是來(lái)表示，這個(gè)多項(xiàng)式被稱為碼多項(xiàng)式。設(shè)：許用循環(huán)碼A=(an-1

an-2…a1

a0)，則：它的碼多項(xiàng)式表示為：其中：x僅是碼元位置的標(biāo)記。2/1/202337例:

設(shè)(7,3)循環(huán)碼組為

(0111001)則相應(yīng)碼多項(xiàng)式為：反之，由碼多項(xiàng)式易得出碼組：(0111001)－－可由碼組直接寫出。2/1/202338（2）碼多項(xiàng)式的按模運(yùn)算1）整數(shù)的按模運(yùn)算若一個(gè)整數(shù)m可以表示為:則在模n運(yùn)算下，有m≡p（模n）。例：同樣對(duì)于多項(xiàng)式而言，也有類似按模運(yùn)算。2/1/202339其中：商Q(x)為多項(xiàng)式，余數(shù)R(x)的冪次低于N(x)的冪次。例:

求x4+x2+1

按模x3+1

運(yùn)算的余式R(x)2）碼多項(xiàng)式的按模運(yùn)算 若則2/1/202340

3）循環(huán)性在循環(huán)碼中，若T(x)

是一個(gè)長(zhǎng)為n的許用碼組，則xiT(x)

在按模xn+1運(yùn)算下，亦是一個(gè)許用碼組。即設(shè)：

T(x)

是長(zhǎng)為n的許用碼組多項(xiàng)式則：

T’(x)仍為該碼組中的一個(gè)碼多項(xiàng)式。例:

（7，3）碼

T(x)=x6+x5+x2+1(1100101)－－前碼組循環(huán)左移3位！2/1/202341由此類推可見(jiàn)：一個(gè)長(zhǎng)為n的循環(huán)碼，必為按模（xn+1）運(yùn)算的一個(gè)余式。2/1/2023422.生成多項(xiàng)式g(x)（1）存在性

(n，k)循環(huán)碼中有且僅有一個(gè)g(x)

g(x)=xn-k+……+1特點(diǎn):

最高的次數(shù):n-k=r；

最高次項(xiàng)和常數(shù)項(xiàng)系數(shù)必為1

。在循環(huán)碼中，除了全0碼組外，再也沒(méi)有連續(xù)k位均為0的碼組。即連0長(zhǎng)度最多為k-1位！這唯一的n-k次多項(xiàng)式稱為生成多項(xiàng)式，記為g(x)！2/1/202343（2）g(x)與生成矩陣G(x)的關(guān)系A(chǔ)=[an-1…ar

]GG=[IkQ]∵生成矩陣G的每一行都是一個(gè)碼組；G是k行n列矩陣，∴只要找到k個(gè)已知碼組，就能構(gòu)成生成矩陣G！生成多項(xiàng)式確定后，則g(x)、x

g(x)、……、xk-1

g(x)都是碼組，且這k個(gè)碼組信息無(wú)關(guān)，因此可以用來(lái)構(gòu)成生成矩陣。g(x)確定了→G(x)也就確定了→整個(gè)碼組即確定！2/1/202344例:

(7，3)循環(huán)碼，g(x)=x4+x2+x+1

求典型生成矩陣解:典型陣:可方便地直接寫成碼組形式2/1/202345（3）

g(x)與T(x)的關(guān)系－－（7，3）表明：所有T(x)都可以被g(x)整除，而且任一次數(shù)不大于(k-1)的多項(xiàng)式乘以g(x)都是碼多項(xiàng)式。2/1/202346依據(jù):

g(x)是xn+1的一個(gè)(n-k)次的因子，且常數(shù)項(xiàng)不為零。證：任一循環(huán)多項(xiàng)式T(x)都是g(x)的倍式，即而生成多項(xiàng)式g(x)本身也是一個(gè)碼組，即有由于碼組T’(x)為一（n-k）次多項(xiàng)式，故xkT’(x) 為一n次多項(xiàng)式。由知，xkT’(x)在模（xn+1）的運(yùn)算下，亦為一碼組，故可寫成（4）如何尋找g(x)2/1/202347上式左端分子和分母都是n次多項(xiàng)式，故商Q(x)＝1，因此上式可化成即將T(x)=h(x)g(x)、T’(x)=g(x)代入，并化簡(jiǎn)，得表明:

g(x)應(yīng)該是xn+1的一個(gè)因式！結(jié)論:

g(x)是xn+1的一個(gè)(n-k)次的因子，且常數(shù)項(xiàng)不為零。2/1/202348（4）如何尋找g(x)依據(jù):

g(x)是xn+1的一個(gè)(n-k)次的因子，且常數(shù)項(xiàng)不為零。如(x7+1)=(x+1)(x3+x2+1)(x3+x+1)n=7（7，4）：x3+x2+1、x3+x+1（7，3）：(x+1)(x3+x2+1)、(x+1)(x3+x+1)（7，6）：x+12/1/202349例:

（7，3）循環(huán)碼有多項(xiàng)式如下，找出（7，3）碼的生成多項(xiàng)式g(x)。

（1）x4+x3+x （2）x3+x2+1（3）