通信原理電子教案

第9章

差錯控制編碼

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

9.1

引言9.2糾錯編碼的基本原理9.3

常用的簡單編碼9.3

線性分組碼9.4

循環(huán)碼9.5

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

一、編碼問題的提出

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

1）雙向通道

2）通信效率低

3）不適于實時通信

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

5）編碼效率高總碼元

(nbit)=

信元(kbit)+督元(r

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

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

2）通信效率高；

3）適于實時傳輸；

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

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

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

000晴

011云

101陰

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

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

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

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

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

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

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

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

000晴

011云

101陰

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

若要求糾正t個錯,則d0≧2t+1

若要檢測e糾正t

個錯(同時),則

d0>e+t+1,

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

9.3常用的簡單編碼

－－屬于分組碼一類。簡單、實用。

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

滿足:

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

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

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

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

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

個錯的可能位置顯然：要求2r-1≥n（n=k+r），則可指示（僅一位錯時）任一錯碼的位置－－包括信元、督元。 或： 2r≥k+r+1－－可指示一個錯碼可能出現(xiàn)的2r-1個位置。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個校正子

S1S2S3

錯碼位置S1S2S3

錯碼位置001a0101a4

010a1110a5100a2111a6

011a3

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

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

G=[Ik

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

[Ik

Q]形式的生成矩陣稱為典型生成陣?！裼傻湫蜕删仃嚨贸龅拇a組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將長為k的信息碼編成長為n的碼組。2/1/2023314.線性分組碼的糾錯譯碼過程－－怎樣由含有錯誤的接收碼組中的接收碼組中恢復(fù)正確。

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

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

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

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

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

→

E按B+E=A

→

A由A

→原始信息（3）糾錯譯碼過程

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

設(shè)：

A1、A2

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

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

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

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

9.5循環(huán)碼

－－仍屬于線性分組碼

特點:

編譯碼設(shè)備簡單，檢糾錯能力強。

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

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

an-2…a1

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

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

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

求x4+x2+1

按模x3+1

運算的余式R(x)2）碼多項式的按模運算 若則2/1/202340

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

是一個長為n的許用碼組，則xiT(x)

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

T(x)

是長為n的許用碼組多項式則：

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

（7，3）碼

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

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

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

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

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

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

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

g(x)、……、xk-1

g(x)都是碼組，且這k個碼組信息無關(guān)，因此可以用來構(gòu)成生成矩陣。g(x)確定了→G(x)也就確定了→整個碼組即確定！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)的多項式乘以g(x)都是碼多項式。2/1/202346依據(jù):

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

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

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

g(x)是xn+1的一個(n-k)次的因子，且常數(shù)項不為零。如(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)碼有多項式如下，找出（7，3）碼的生成多項式g(x)。

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