第9章-差錯控制編碼-

第9章_差錯控制編碼_第一頁，共55頁。研究的問題

9.1引言9.2糾錯編碼的基本原理9.3常用的簡單編碼9.3線性分組碼9.4循環(huán)碼9.5卷積碼9.6網(wǎng)格編碼調(diào)制4/17/20232第二頁，共55頁。干擾乘性：均衡加性：調(diào)制解調(diào)體制、發(fā)送功率、最佳接收9.1引言

一、編碼問題的提出

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

1）雙向通道2）通信效率低3）不適于實時通信4）編、譯碼設(shè)備簡單5）編碼效率高總碼元(nbit)=

信元(kbit)+督元(r

bit)。只檢不糾，有錯自動要求重發(fā)。4/17/20235第五頁，共55頁。2.前向糾錯(FEC)收發(fā)可糾錯的碼特點：1）只需單向信道－－省信道！2）通信效率高；3）適于實時傳輸；4)譯碼設(shè)備復雜。檢錯并糾錯4/17/20236第六頁，共55頁。3.反饋檢驗法收發(fā)原理：收端將信碼原封不動地轉(zhuǎn)發(fā)回發(fā)端，并與原發(fā)送信碼相比較：發(fā)現(xiàn)錯－－重發(fā)；否則：PASS特點:

需要雙向通道；收發(fā)設(shè)備簡單；傳輸效率低（最低）。4/17/20237第七頁，共55頁。9.2糾錯編碼的基本原理

一.基本思想信元督元信元督元……信元和督元有一的函數(shù)關(guān)系，插入督元的過程就是一種編碼的過程，接收端可檢錯糾錯。顯然，傳輸效率↓（引入冗余碼）例：天氣預報信元督元000晴011云101陰110雨三位碼元有23=8種組合，實際使用了22=4種－－許用碼組。其余001，010，100，111為禁用碼組。檢錯能力：可檢錯奇數(shù)個錯；糾錯能力：無。4/17/20238第八頁，共55頁。例：天氣預報，可預報天晴信元督元000111冗余量加大，禁用碼組比例提高。檢錯能力：檢2；糾錯能力：糾1。許用碼組2個，禁用碼組6個晴陰4/17/20239第九頁，共55頁。二.糾錯編碼的分類線性碼和非線性碼分組碼、卷積碼和循環(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個督元碼長－－n4/17/202310第十頁，共55頁。碼組的重量和碼距及糾錯能力1.重量碼組中非0元素的個數(shù)例:A=(10110)碼重=32.碼距

兩兩碼組對應(yīng)位上數(shù)值不同的個數(shù)，記為d。最小碼距:某種編碼中各個碼組間距離的最小值，記做d0

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

14/17/202311第十一頁，共55頁。前例中：天氣預報信元督元000晴011云101陰110雨四個許用碼組之間的距離均為2。Why?擯棄d=1的碼－－禁用碼組。許用碼組最小碼距愈大，抗干擾能力愈強！確定最小碼距的目的：決定編碼的檢糾錯能力。4/17/202312第十二頁，共55頁。3.d0與糾檢錯能力若要求檢測e個錯,則d0≧e+1若要求糾正t個錯,則d0≧2t+1若要檢測e糾正t個錯(同時),則

d0>e+t+1,

且e>t碼距與檢錯和糾錯能力的關(guān)系如圖：t1te4/17/202313第十三頁，共55頁。0123Ad0(a)012345ABttd0(b)ABt1te(c)圖9-44/17/202314第十四頁，共55頁。 9.3常用的簡單編碼

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

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

滿足:

偶監(jiān)督碼：碼組中1的個數(shù)為偶數(shù)；奇監(jiān)督碼：碼組中1的個數(shù)為奇數(shù)。檢錯能力:所有奇數(shù)個錯。一半！應(yīng)用非常多。編碼效率:4/17/202315第十五頁，共55頁。二維奇偶監(jiān)督碼

－－進行橫、縱向監(jiān)督例:00001111010100110101000000110101101010橫向監(jiān)督縱向監(jiān)督糾檢錯能力:仍可檢錯奇數(shù)個錯還可檢錯偶數(shù)個錯可糾正一些錯碼●適于檢測突發(fā)性錯誤4/17/202316第十六頁，共55頁。橫比碼(等重碼)例:碼重為31.010111100110110許用碼組:C35=10禁用碼組:25-10=22檢錯能力:可檢測所有奇數(shù)個碼元的錯 和部分偶數(shù)個碼元的錯,但不能檢測碼組中“1”變?yōu)椤?”與“0”變?yōu)椤?”的錯碼數(shù)目相同的那些偶數(shù)錯碼編碼效率:4/17/202317第十七頁，共55頁。例：n=10,則k=5信元碼監(jiān)督碼合成碼校驗碼1011010110000000000010001011101111100000●接受端的檢測三.正反碼編碼規(guī)則:●信息位(n/2)中有奇數(shù)個“1”,則監(jiān)督位與信息位相同●信息位(n/2)中有偶數(shù)個“1”,則監(jiān)督位是信息位的反碼4/17/202318第十八頁，共55頁。 9.4線性分組碼定義：若分組碼（n,k）,督元與信元的關(guān)系可用一線性方程組來描述，則該分組碼（n,k）稱為線性分組碼。一、漢明碼－－能糾一位錯的線性分組碼。定義：是一種能糾正一位錯碼，且編碼效率較高的線性分組碼。最小碼距：d0=31.構(gòu)造原理考察：定義一個監(jiān)督方程（監(jiān)督關(guān)系式、偶監(jiān)督）：由于一位校正子只有兩種取值，故只能表示有錯或無錯，不能指出錯碼的位置。4/17/202319第十九頁，共55頁。推想:如果監(jiān)督位增加一位（即變成兩位），則可增加一個類似于上式的監(jiān)督關(guān)系，即可獲得兩個校正子，于是可有S1S20001011－－無錯可指示一個錯碼可能出現(xiàn)的位置，共有22-1=3個位置。4/17/202320第二十頁，共55頁。再推廣:S1S2……Sr00…….000…….1………………11….11－－無錯2r-1個錯的可能位置顯然：要求2r-1≥n（n=k+r），則可指示（僅一位錯時）任一錯碼的位置－－包括信元、督元。 或： 2r≥k+r+1－－可指示一個錯碼可能出現(xiàn)的2r-1個位置。4/17/202321第二十一頁，共55頁。2.例:構(gòu)造k=4的漢明碼（1）確定r由2r≥k+r+1得r=3，則n=

k+r=7－－

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

G=[IkQ]則，碼組行陣 A=[a6a5a4a3]G4/17/202329第二十九頁，共55頁。例：生成矩陣討論：●由具有[IkQ]形式的生成矩陣稱為典型生成陣?！裼傻湫蜕删仃嚨贸龅拇a組A中，信息位不變，監(jiān)督位附加其后－－這種碼稱為系統(tǒng)碼。碼組行陣：4/17/202330第三十頁，共55頁。一般形式:

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的碼組。4/17/202331第三十一頁，共55頁。4.線性分組碼的糾錯譯碼過程－－怎樣由含有錯誤的接收碼組中的接收碼組中恢復正確。

（1）錯誤圖樣設(shè)：發(fā)碼組為A,接受碼組為B則 B–A=E(模2)－－錯誤行陣或錯誤圖樣：

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

則E=[0110010]4/17/202332第三十二頁，共55頁。（2）校正子（或稱譯碼伴隨式）B=A+E代入上式，得結(jié)論：校正子S僅于錯誤圖案有關(guān)，與發(fā)送碼組無關(guān)。4/17/202333第三十三頁，共55頁。由收到的碼組B，按式：BHT=S→S由S=ET

→

E按B+E=A

→

A由A

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

4/17/202334第三十四頁，共55頁。5.線性分組碼的重要性（1）封閉性

設(shè)：

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

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

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

即A1+A2也是一個碼組。結(jié)論：線性碼組中任意兩個碼字之和，仍為該線性碼組之碼字。（2）線性分組碼的最小碼距即為該碼的最小重量: d0=Wmin（除全0碼組）證：由封閉性得，兩個碼組之間的距離（之差），必是另一碼組的重量。故最小碼距即是碼的最小重量！4/17/202335第三十五頁，共55頁。 9.5循環(huán)碼

－－仍屬于線性分組碼

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

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

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

an-2…a1

a0)，則：它的碼多項式表示為：其中：x僅是碼元位置的標記。4/17/202337第三十七頁，共55頁。例:設(shè)(7,3)循環(huán)碼組為(0111001)則相應(yīng)碼多項式為：反之，由碼多項式易得出碼組：(0111001)－－可由碼組直接寫出。4/17/202338第三十八頁，共55頁。（2）碼多項式的按模運算1）整數(shù)的按模運算若一個整數(shù)m可以表示為:則在模n運算下，有m≡p（模n）。例：同樣對于多項式而言，也有類似按模運算。4/17/202339第三十九頁，共55頁。其中：商Q(x)為多項式，余數(shù)R(x)的冪次低于N(x)的冪次。例:求x4+x2+1按模x3+1運算的余式R(x)2）碼多項式的按模運算 若則4/17/202340第四十頁，共55頁。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位！4/17/202341第四十一頁，共55頁。由此類推可見：一個長為n的循環(huán)碼，必為按模（xn+1）運算的一個余式。4/17/202342第四十二頁，共55頁。2.生成多項式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)！4/17/202343第四十三頁，共55頁。（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)也就確定了→整個碼組即確定！4/17/202344第四十四頁，共55頁。例:

(7，3)循環(huán)碼，g(x)=x4+x2+x+1求典型生成矩陣解:典型陣:可方便地直接寫成碼組形式4/17/202345第四十五頁，共55頁。（3）g(x)與T(x)的關(guān)系－－（7，3）表明：所有T(x)都可以被g(x)整除，而且任一次數(shù)不大于(k-1)的多項式乘以g(x)都是碼多項式。4/17/202346第四十六頁，共55頁。依據(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)4/17/202347第四十七頁，共55頁。上式左端分子和分母都是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ù)項不為零。4/17/202348第四十八頁，共55頁。（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)