西工大通信原理(期末復(fù)習(xí)、考研、求職必備)-第9章-差錯(cuò)控制編碼課件

通信原理電子教案

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

西北工業(yè)大學(xué)

（2008.3）11/27/20221通信原理電子教案

第9章差錯(cuò)控制編碼西研究的問題

9.1引言9.2糾錯(cuò)編碼的基本原理9.3常用的簡(jiǎn)單編碼9.3線性分組碼9.4循環(huán)碼9.5卷積碼9.6網(wǎng)格編碼調(diào)制11/27/20222研究的問題9.1引言11/27/20222干擾乘性：均衡加性：調(diào)制解調(diào)體制、發(fā)送功率、最佳接收9.1引言

一、編碼問題的提出

由于數(shù)字信號(hào)在傳輸過程中必不可免的受到干擾的影響，使碼元波形變壞，故傳輸?shù)浇邮斩撕罂赡馨l(fā)生錯(cuò)判。信道譯碼檢/糾錯(cuò)編碼若還不行，則需－－差錯(cuò)控制編碼。目的：在數(shù)字通信系統(tǒng)中，為了提高數(shù)字信號(hào)傳輸?shù)挠行远扇〉木幋a稱為信源編碼；為了提高數(shù)字通信的可靠性而采取的編碼稱為信道編碼。差錯(cuò)可控11/27/20223干擾乘性：均衡9.1引言

一、編碼問題的提出

由于數(shù)字二、錯(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ò)誤11/27/20224二、錯(cuò)誤的類型11/27/20224三、差錯(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ā)。11/27/20225三、差錯(cuò)控制的方式收發(fā)可檢錯(cuò)的碼特點(diǎn):總碼元(nbit2.前向糾錯(cuò)(FEC)收發(fā)可糾錯(cuò)的碼特點(diǎn)：1）只需單向信道－－省信道！2）通信效率高；3）適于實(shí)時(shí)傳輸；4)譯碼設(shè)備復(fù)雜。檢錯(cuò)并糾錯(cuò)11/27/202262.前向糾錯(cuò)(FEC)收發(fā)可糾錯(cuò)的碼特點(diǎn)：檢錯(cuò)并糾錯(cuò)113.反饋檢驗(yàn)法收發(fā)原理：收端將信碼原封不動(dòng)地轉(zhuǎn)發(fā)回發(fā)端，并與原發(fā)送信碼相比較：發(fā)現(xiàn)錯(cuò)－－重發(fā)；否則：PASS特點(diǎn):

需要雙向通道；收發(fā)設(shè)備簡(jiǎn)單；傳輸效率低（最低）。11/27/202273.反饋檢驗(yàn)法收發(fā)原理：收端將信碼原封不動(dòng)地轉(zhuǎn)發(fā)回發(fā)端，并9.2糾錯(cuò)編碼的基本原理

一.基本思想信元督元信元督元……信元和督元有一的函數(shù)關(guān)系，插入督元的過程就是一種編碼的過程，接收端可檢錯(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ú)。11/27/202289.2糾錯(cuò)編碼的基本原理

一.基本思想信元督元信元督元例：天氣預(yù)報(bào)，可預(yù)報(bào)天晴信元督元000111冗余量加大，禁用碼組比例提高。檢錯(cuò)能力：檢2；糾錯(cuò)能力：糾1。許用碼組2個(gè)，禁用碼組6個(gè)晴陰11/27/20229例：天氣預(yù)報(bào)，可預(yù)報(bào)天晴信元督元冗余量加大，禁用碼二.糾錯(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)－－n11/27/202210二.糾錯(cuò)編碼的分類符號(hào):(n,k),r碼組的重量和碼距及糾錯(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）最小碼距:

111/27/202211碼組的重量和碼距及糾錯(cuò)能力11/27/202211前例中：天氣預(yù)報(bào)信元督元000晴011云101陰110雨四個(gè)許用碼組之間的距離均為2。Why?擯棄d=1的碼－－禁用碼組。許用碼組最小碼距愈大，抗干擾能力愈強(qiáng)！確定最小碼距的目的：決定編碼的檢糾錯(cuò)能力。11/27/202212前例中：天氣預(yù)報(bào)信元督元四個(gè)許用3.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)系如圖：t1te11/27/2022133.d0與糾檢錯(cuò)能力t0123Ad0(a)012345ABttd0(b)ABt1te(c)圖9-411/27/2022140123d0(a)012 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)用非常多。編碼效率:11/27/202215 9.3常用的簡(jiǎn)單編碼

－－屬于分組碼一類。簡(jiǎn)單、二維奇偶監(jiān)督碼

－－進(jìn)行橫、縱向監(jiān)督例:00001111010100110101000000110101101010橫向監(jiān)督縱向監(jiān)督糾檢錯(cuò)能力:仍可檢錯(cuò)奇數(shù)個(gè)錯(cuò)還可檢錯(cuò)偶數(shù)個(gè)錯(cuò)可糾正一些錯(cuò)碼●適于檢測(cè)突發(fā)性錯(cuò)誤11/27/202216二維奇偶監(jiān)督碼00001橫縱向監(jiān)督糾橫比碼(等重碼)例:碼重為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ò)碼編碼效率:11/27/202217橫比碼(等重碼)1.01011例：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)督位是信息位的反碼11/27/202218例：n=10,則k=5信元碼監(jiān)督碼 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ò)碼的位置。11/27/202219 9.4線性分組碼由于一位校正子只有兩種取值，故只推想:如果監(jiān)督位增加一位（即變成兩位），則可增加一個(gè)類似于上式的監(jiān)督關(guān)系，即可獲得兩個(gè)校正子，于是可有S1S20001011－－無(wú)錯(cuò)可指示一個(gè)錯(cuò)碼可能出現(xiàn)的位置，共有22-1=3個(gè)位置。11/27/202220推想:如果監(jiān)督位增加一位（即變成兩位），則可增加一個(gè)類似于上再推廣: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è)位置。11/27/202221再推廣:S1S2……Sr－－無(wú)錯(cuò)2r-1個(gè)錯(cuò)的顯2.例:構(gòu)造k=4的漢明碼（1）確定r由2r≥k+r+1得r=3，則n=

k+r=7－－

(7,4)分組碼11/27/2022222.例:構(gòu)造k=4的漢明碼11/27/202222（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)系11/27/202223（2）寫出校正子的編碼表S1S2S3錯(cuò)碼位得校驗(yàn)方程:即實(shí)際上確定了督元和信元之間的關(guān)系:校驗(yàn)方程督～信關(guān)系－－有了校正子編碼表，督元不是隨便選的?。?）給定了信元a6a5a4a3,可由“督～信關(guān)系”確定督元－－全部(7,4)碼組。11/27/202224得校驗(yàn)方程:即實(shí)際上確定了督元和信元之間的關(guān)系:校驗(yàn)方程督～（4）給定了信元a6a5a4a3,可確定督元－－全部(7,4)碼組11/27/202225（4）給定了信元a6a5a4a3,可確定督元－－全部(7二.線性分組碼1.線性方程組和監(jiān)督方程寫成矩陣式:111010011010101011001a6a5a4a3a2a1a011/27/202226二.線性分組碼寫成矩陣式:11101可見：H一旦確定，督元和信元之間的關(guān)系也就確定了。若:則稱H為典型陣，一般，H總可以化為典型陣。111010011010101011001a6a5a4a3a2a1a011/27/202227可見：H一旦確定，督元和信元之間的關(guān)系也就確定了。則稱H為典2.生成矩陣矩陣形式:－－從督信方程入手由11/27/2022282.生成矩陣矩陣形式:－－從督信方程入手11/27/202寫成行陣形式:其中Q=PT。上式表明：信息位給定后，就產(chǎn)生了監(jiān)督位！進(jìn)一步，令生成矩陣

G=[IkQ]則，碼組行陣 A=[a6a5a4a3]G11/27/202229寫成行陣形式:其中Q=PT。上式表明：信息位給定后，例：生成矩陣討論：●由具有[IkQ]形式的生成矩陣稱為典型生成陣。●由典型生成矩陣得出的碼組A中，信息位不變，監(jiān)督位附加其后－－這種碼稱為系統(tǒng)碼。碼組行陣：11/27/202230例：生成矩陣討論：碼組行陣：11/27/202230一般形式:

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的碼組。11/27/202231一般形式:3.G和H的關(guān)系11/27/202234.線性分組碼的糾錯(cuò)譯碼過程－－怎樣由含有錯(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]11/27/2022324.線性分組碼的糾錯(cuò)譯碼過程例:A=[11（2）校正子（或稱譯碼伴隨式）B=A+E代入上式，得結(jié)論：校正子S僅于錯(cuò)誤圖案有關(guān)，與發(fā)送碼組無(wú)關(guān)。11/27/202233（2）校正子（或稱譯碼伴隨式）B=A+E代入上式，得結(jié)由收到的碼組B，按式：BHT=S→S由S=ET

→

E按B+E=A

→

A由A

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

11/27/202234由收到的碼組B，按式：BHT=S→S（3）糾錯(cuò)譯碼過程15.線性分組碼的重要性（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è)碼組之間的距離（之差），必是另一碼組的重量。故最小碼距即是碼的最小重量！11/27/2022355.線性分組碼的重要性11/27/202235 9.5循環(huán)碼

－－仍屬于線性分組碼

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

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

具有線性分組碼的所有性質(zhì)之外，還具有循環(huán)性：循環(huán)碼中任一許用碼組經(jīng)過循環(huán)移位后，所得到的碼組仍然是許用碼組。11/27/202236 9.5循環(huán)碼

－－仍屬于線性分組碼碼多項(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)記。11/27/202237碼多項(xiàng)式T(x)其中：x僅是碼元位置的標(biāo)記。11/27/2例:設(shè)(7,3)循環(huán)碼組為(0111001)則相應(yīng)碼多項(xiàng)式為：反之，由碼多項(xiàng)式易得出碼組：(0111001)－－可由碼組直接寫出。11/27/202238例:設(shè)(7,3)循環(huán)碼組為反之，由碼多項(xiàng)式易得出（2）碼多項(xiàng)式的按模運(yùn)算1）整數(shù)的按模運(yùn)算若一個(gè)整數(shù)m可以表示為:則在模n運(yùn)算下，有m≡p（模n）。例：同樣對(duì)于多項(xiàng)式而言，也有類似按模運(yùn)算。11/27/202239（2）碼多項(xiàng)式的按模運(yùn)算則在模n運(yùn)算下，有m≡p（模n）。同其中：商Q(x)為多項(xiàng)式，余數(shù)R(x)的冪次低于N(x)的冪次。例:求x4+x2+1按模x3+1運(yùn)算的余式R(x)2）碼多項(xiàng)式的按模運(yùn)算 若則11/27/202240其中：商Q(x)為多項(xiàng)式，余數(shù)R(x)的冪次低于N(x)的冪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位！11/27/2022413）循環(huán)性則：T’(x)仍為該碼組中的一個(gè)碼多項(xiàng)式。例:由此類推可見：一個(gè)長(zhǎng)為n的循環(huán)碼，必為按模（xn+1）運(yùn)算的一個(gè)余式。11/27/202242由此類推可見：一個(gè)長(zhǎng)為n的循環(huán)碼，必為按模（xn+1）運(yùn)算的2.生成多項(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碼組外，再也沒有連續(xù)k位均為0的碼組。即連0長(zhǎng)度最多為k-1位！這唯一的n-k次多項(xiàng)式稱為生成多項(xiàng)式，記為g(x)！11/27/2022432.生成多項(xiàng)式g(x)在循環(huán)碼中，除了全0碼組外，再也沒有（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è)碼組即確定！11/27/202244（2）g(x)與生成矩陣G(x)的關(guān)系A(chǔ)=[例:

(7，3)循環(huán)碼，g(x)=x4+x2+x+1求典型生成矩陣解:典型陣:可方便地直接寫成碼組形式11/27/202245例:(7，3)循環(huán)碼，g(x)=x4+x2+x（3）g(x)與T(x)的關(guān)系－－（7，3）表明：所有T(x)都可以被g(x)整除，而且任一次數(shù)不大于(k-1)的多項(xiàng)式乘以g(x)都是碼多項(xiàng)式。11/27/202246（3）g(x)與T(x)的關(guān)系－－（7，3）表明：所依據(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)11/27/202247依據(jù):g(x)是xn+1的一個(gè)(n-k)次的因子，且常上式左端分子和分母都是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)不為零。11/27/202248上式左端分子和分母都是n次多項(xiàng)式，故商Q(x)＝1，因此上式（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+111/27/202249（4）如何尋找g(x)依據(jù):g(x)是xn+1的一個(gè)例:

（7，3）循環(huán)碼有多項(xiàng)式如下，找出（7，3）碼的生成多項(xiàng)式g(x)。（1）x4+x3+x （2）x3+x2+1（3）x+1（4）x4+x2+x+1（5）x4+x+1解:依據(jù)r=7-3=4，常數(shù)項(xiàng)不為零，有

（4）x4+x2+x+1（5）x4+x+1還須證其是不是xn+1=x7+1的因子?X7+1=(x4+x2+x+1)(x3+x+1)+0X7+1=(x4+x+1)(x3+1)+

(x2+x)故:僅有x4+x2+x+1為生成多項(xiàng)式g(x)。11/27/202250例:（7，3）循環(huán)碼有多項(xiàng)式如下，找出（7，3）碼的生成多9.5.2循環(huán)碼的編碼方法1.(n，k)循環(huán)碼的編碼步驟設(shè):已選好g(x)，給定信息碼組m(x):（1）作xn-km(x)－－實(shí)際上是把信息碼后附加上（n-k）個(gè)“0”。（2）作（3）編碼輸出系統(tǒng)循環(huán)碼多項(xiàng)式T(x)為：

－－得到了r(x)。由于循環(huán)碼多項(xiàng)式T(x)都可被g(x)整除，也就是：11/27/2022519.5.2循環(huán)碼的編碼方法（1）作xn-km(x)－－實(shí)際例:(7，3)循環(huán)碼，選g(x)=x4+x2+x+1

設(shè)

m(x)=x2+x+1←→(111)解:2.編碼的電路11/27/202252例:(7，3)循環(huán)碼，選g(x)=x4+x2+上述三步編碼過程，在硬件實(shí)現(xiàn)時(shí)，可以利用除法電路（曹志剛p344－348）來(lái)實(shí)現(xiàn)。編碼的電路11/27/202253上述三步編碼過程，在硬件實(shí)現(xiàn)時(shí)，可以利用除法電路（曹志剛p3工作過程：信息輸入時(shí)，開關(guān)合2：輸入碼一方面輸入除法器，另一方面直接輸出，在信息位全部進(jìn)入除法器后－－開關(guān)合1：輸出端接到移位寄存器，將移位寄存器中存儲(chǔ)的余項(xiàng)依次輸出，同時(shí)切斷反饋線。系統(tǒng)碼！11/27/202254工作過程：11/27/2022542、譯碼過程循環(huán)碼的譯碼可以分三步進(jìn)行：（1）由接收到的碼多項(xiàng)式B(x)計(jì)算校正子（伴隨式）多項(xiàng)式S(x)；（2）由校正子S(x)確定錯(cuò)誤圖樣E(x)；（3）將錯(cuò)誤圖樣E(x)與B(x)相加，糾正錯(cuò)誤。11/27/2022552、譯碼過程11/27/202255通信原理電子教案

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

西北工業(yè)大學(xué)

（2008.3）11/27/202256通信原理電子教案

第9章差錯(cuò)控制編碼西研究的問題

9.1引言9.2糾錯(cuò)編碼的基本原理9.3常用的簡(jiǎn)單編碼9.3線性分組碼9.4循環(huán)碼9.5卷積碼9.6網(wǎng)格編碼調(diào)制11/27/202257研究的問題9.1引言11/27/20222干擾乘性：均衡加性：調(diào)制解調(diào)體制、發(fā)送功率、最佳接收9.1引言

一、編碼問題的提出

由于數(shù)字信號(hào)在傳輸過程中必不可免的受到干擾的影響，使碼元波形變壞，故傳輸?shù)浇邮斩撕罂赡馨l(fā)生錯(cuò)判。信道譯碼檢/糾錯(cuò)編碼若還不行，則需－－差錯(cuò)控制編碼。目的：在數(shù)字通信系統(tǒng)中，為了提高數(shù)字信號(hào)傳輸?shù)挠行远扇〉木幋a稱為信源編碼；為了提高數(shù)字通信的可靠性而采取的編碼稱為信道編碼。差錯(cuò)可控11/27/202258干擾乘性：均衡9.1引言

一、編碼問題的提出

由于數(shù)字二、錯(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ò)誤11/27/202259二、錯(cuò)誤的類型11/27/20224三、差錯(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ā)。11/27/202260三、差錯(cuò)控制的方式收發(fā)可檢錯(cuò)的碼特點(diǎn):總碼元(nbit2.前向糾錯(cuò)(FEC)收發(fā)可糾錯(cuò)的碼特點(diǎn)：1）只需單向信道－－省信道！2）通信效率高；3）適于實(shí)時(shí)傳輸；4)譯碼設(shè)備復(fù)雜。檢錯(cuò)并糾錯(cuò)11/27/2022612.前向糾錯(cuò)(FEC)收發(fā)可糾錯(cuò)的碼特點(diǎn)：檢錯(cuò)并糾錯(cuò)113.反饋檢驗(yàn)法收發(fā)原理：收端將信碼原封不動(dòng)地轉(zhuǎn)發(fā)回發(fā)端，并與原發(fā)送信碼相比較：發(fā)現(xiàn)錯(cuò)－－重發(fā)；否則：PASS特點(diǎn):

需要雙向通道；收發(fā)設(shè)備簡(jiǎn)單；傳輸效率低（最低）。11/27/2022623.反饋檢驗(yàn)法收發(fā)原理：收端將信碼原封不動(dòng)地轉(zhuǎn)發(fā)回發(fā)端，并9.2糾錯(cuò)編碼的基本原理

一.基本思想信元督元信元督元……信元和督元有一的函數(shù)關(guān)系，插入督元的過程就是一種編碼的過程，接收端可檢錯(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ú)。11/27/2022639.2糾錯(cuò)編碼的基本原理

一.基本思想信元督元信元督元例：天氣預(yù)報(bào)，可預(yù)報(bào)天晴信元督元000111冗余量加大，禁用碼組比例提高。檢錯(cuò)能力：檢2；糾錯(cuò)能力：糾1。許用碼組2個(gè)，禁用碼組6個(gè)晴陰11/27/202264例：天氣預(yù)報(bào)，可預(yù)報(bào)天晴信元督元冗余量加大，禁用碼二.糾錯(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)－－n11/27/202265二.糾錯(cuò)編碼的分類符號(hào):(n,k),r碼組的重量和碼距及糾錯(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）最小碼距:

111/27/202266碼組的重量和碼距及糾錯(cuò)能力11/27/202211前例中：天氣預(yù)報(bào)信元督元000晴011云101陰110雨四個(gè)許用碼組之間的距離均為2。Why?擯棄d=1的碼－－禁用碼組。許用碼組最小碼距愈大，抗干擾能力愈強(qiáng)！確定最小碼距的目的：決定編碼的檢糾錯(cuò)能力。11/27/202267前例中：天氣預(yù)報(bào)信元督元四個(gè)許用3.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)系如圖：t1te11/27/2022683.d0與糾檢錯(cuò)能力t0123Ad0(a)012345ABttd0(b)ABt1te(c)圖9-411/27/2022690123d0(a)012 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)用非常多。編碼效率:11/27/202270 9.3常用的簡(jiǎn)單編碼

－－屬于分組碼一類。簡(jiǎn)單、二維奇偶監(jiān)督碼

－－進(jìn)行橫、縱向監(jiān)督例:00001111010100110101000000110101101010橫向監(jiān)督縱向監(jiān)督糾檢錯(cuò)能力:仍可檢錯(cuò)奇數(shù)個(gè)錯(cuò)還可檢錯(cuò)偶數(shù)個(gè)錯(cuò)可糾正一些錯(cuò)碼●適于檢測(cè)突發(fā)性錯(cuò)誤11/27/202271二維奇偶監(jiān)督碼00001橫縱向監(jiān)督糾橫比碼(等重碼)例:碼重為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ò)碼編碼效率:11/27/202272橫比碼(等重碼)1.01011例：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)督位是信息位的反碼11/27/202273例：n=10,則k=5信元碼監(jiān)督碼 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ò)碼的位置。11/27/202274 9.4線性分組碼由于一位校正子只有兩種取值，故只推想:如果監(jiān)督位增加一位（即變成兩位），則可增加一個(gè)類似于上式的監(jiān)督關(guān)系，即可獲得兩個(gè)校正子，于是可有S1S20001011－－無(wú)錯(cuò)可指示一個(gè)錯(cuò)碼可能出現(xiàn)的位置，共有22-1=3個(gè)位置。11/27/202275推想:如果監(jiān)督位增加一位（即變成兩位），則可增加一個(gè)類似于上再推廣: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è)位置。11/27/202276再推廣:S1S2……Sr－－無(wú)錯(cuò)2r-1個(gè)錯(cuò)的顯2.例:構(gòu)造k=4的漢明碼（1）確定r由2r≥k+r+1得r=3，則n=

k+r=7－－

(7,4)分組碼11/27/2022772.例:構(gòu)造k=4的漢明碼11/27/202222（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)系11/27/202278（2）寫出校正子的編碼表S1S2S3錯(cuò)碼位得校驗(yàn)方程:即實(shí)際上確定了督元和信元之間的關(guān)系:校驗(yàn)方程督～信關(guān)系－－有了校正子編碼表，督元不是隨便選的！（4）給定了信元a6a5a4a3,可由“督～信關(guān)系”確定督元－－全部(7,4)碼組。11/27/202279得校驗(yàn)方程:即實(shí)際上確定了督元和信元之間的關(guān)系:校驗(yàn)方程督～（4）給定了信元a6a5a4a3,可確定督元－－全部(7,4)碼組11/27/202280（4）給定了信元a6a5a4a3,可確定督元－－全部(7二.線性分組碼1.線性方程組和監(jiān)督方程寫成矩陣式:111010011010101011001a6a5a4a3a2a1a011/27/202281二.線性分組碼寫成矩陣式:11101可見：H一旦確定，督元和信元之間的關(guān)系也就確定了。若:則稱H為典型陣，一般，H總可以化為典型陣。111010011010101011001a6a5a4a3a2a1a011/27/202282可見：H一旦確定，督元和信元之間的關(guān)系也就確定了。則稱H為典2.生成矩陣矩陣形式:－－從督信方程入手由11/27/2022832.生成矩陣矩陣形式:－－從督信方程入手11/27/202寫成行陣形式:其中Q=PT。上式表明：信息位給定后，就產(chǎn)生了監(jiān)督位！進(jìn)一步，令生成矩陣

G=[IkQ]則，碼組行陣 A=[a6a5a4a3]G11/27/202284寫成行陣形式:其中Q=PT。上式表明：信息位給定后，例：生成矩陣討論：●由具有[IkQ]形式的生成矩陣稱為典型生成陣。●由典型生成矩陣得出的碼組A中，信息位不變，監(jiān)督位附加其后－－這種碼稱為系統(tǒng)碼。碼組行陣：11/27/202285例：生成矩陣討論：碼組行陣：11/27/202230一般形式:

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的碼組。11/27/202286一般形式:3.G和H的關(guān)系11/27/202234.線性分組碼的糾錯(cuò)譯碼過程－－怎樣由含有錯(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]11/27/2022874.線性分組碼的糾錯(cuò)譯碼過程例:A=[11（2）校正子（或稱譯碼伴隨式）B=A+E代入上式，得結(jié)論：校正子S僅于錯(cuò)誤圖案有關(guān)，與發(fā)送碼組無(wú)關(guān)。11/27/202288（2）校正子（或稱譯碼伴隨式）B=A+E代入上式，得結(jié)由收到的碼組B，按式：BHT=S→S由S=ET

→

E按B+E=A

→

A由A

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

11/27/202289由收到的碼組B，按式：BHT=S→S（3）糾錯(cuò)譯碼過程15.線性分組碼的重要性（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è)碼組之間的距離（之差），必是另一碼組的重量。故最小碼距即是碼的最小重量！11/27/2022905.線性分組碼的重要性11/27/202235 9.5循環(huán)碼

－－仍屬于線性分組碼

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

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

具有線性分組碼的所有性質(zhì)之外，還具有循環(huán)性：循環(huán)碼中任一許用碼組經(jīng)過循環(huán)移位后，所得到的碼組仍然是許用碼組。11/27/202291 9.5循環(huán)碼

－－仍屬于線性分組碼碼多項(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)記。11/27/202292碼多項(xiàng)式T(x)其中：x僅是碼元位置的標(biāo)記。11/27/2例:設(shè)(7,3)循環(huán)碼組為(0111001)則相應(yīng)碼多項(xiàng)式為：反之，由碼多項(xiàng)式易得出碼組：(0111001)－－可由碼組直接寫出。11/27/202293例:設(shè)(7,3)循環(huán)碼組為反之，由碼多項(xiàng)式易得出（2）碼多項(xiàng)式的按模運(yùn)算1）整數(shù)的按模運(yùn)算若一個(gè)整數(shù)m可以表示為:則在模n運(yùn)算下，有m≡p（模n）。例：同樣對(duì)于多項(xiàng)式而言，也有類似按模運(yùn)算。11/27/202294（2）碼多項(xiàng)式的按模運(yùn)算則在模n運(yùn)算下，有m≡p（模n）。同其中：商Q(x)為多項(xiàng)式，余數(shù)R(x)的冪次低于N(x)的冪次。例:求x4+x2+1按模x3+1運(yùn)算的余式R(x)2）碼多項(xiàng)式的按模運(yùn)算 若則11/27/202295其中：商Q(x)為多項(xiàng)式，余數(shù)R(x)的冪次低于N(x)的冪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位！11/27/2022963）循環(huán)性則：T’(x)仍為該碼組中的一個(gè)碼多項(xiàng)式。例:由此類推可見：一個(gè)長(zhǎng)為n的循環(huán)碼，必為按模（xn+1）運(yùn)算的一個(gè)余式。11/27/202297由此類推可見：一個(gè)長(zhǎng)為n的循環(huán)碼，必為按模（xn+1）運(yùn)算的2.生成多項(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碼組外，再也沒有連續(xù)k位均為0的碼組。即連0長(zhǎng)度最多為k-1位！這唯一的n-k次多項(xiàng)式稱為生成多項(xiàng)式，記為g(x)！11/27/2022982.生成多項(xiàng)式g(x)在循環(huán)碼中，除了全0碼組外，再也沒有（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è)碼組即確定！11/27/