第9章-差錯控制編碼1課件

通信原理電子教案

第9章差錯控制編碼西北工業(yè)大學(xué)（2012.5）7/28/20231干擾乘性：均衡加性：調(diào)制解調(diào)體制、發(fā)送功率、最佳接收9.1引言

一、編碼問題的提出

由于數(shù)字信號在傳輸過程中必不可免的受到干擾的影響，使碼元波形變壞，故傳輸?shù)浇邮斩撕罂赡馨l(fā)生錯判。信道譯碼檢/糾錯編碼若還不行，則需－－差錯控制編碼。目的：在數(shù)字通信系統(tǒng)中，為了提高數(shù)字通信的可靠性而采取的編碼稱為信道編碼。差錯可控之前：為了提高數(shù)字信號傳輸?shù)挠行远扇〉木幋a稱為信源編碼。如：PCM二、方法/模型7/28/20232研究問題：9.1引言9.2差錯控制編碼的基本概念

9.3常用的簡單檢錯碼

9.4線性分組碼9.5循環(huán)碼

9.6檢測和糾正突發(fā)錯誤的分組碼——交織碼

9.7卷積碼

9.8網(wǎng)格編碼調(diào)制(TCM)

7/28/202331.

隨機性差錯：差錯是隨機的且相互之間獨立—單個錯。通常由高斯白噪聲引起。突發(fā)性差錯：錯誤之間有相關(guān)性----成串錯。由脈沖性干擾引起，在短暫的時間內(nèi)出現(xiàn)連續(xù)的差錯，而這些短暫時間之后卻又存在較長的無誤碼區(qū)間。9.2.1差錯類型

9.2

糾錯編碼的基本概念3.混合性差錯：既存在隨機差錯又有突發(fā)性差錯。以上兩種錯誤性質(zhì)不同，可分別處理。7/28/20234可以用來檢測一位錯誤可糾正一位錯誤或檢測兩位錯誤AB

許用碼組禁用碼組

00

01

11

10

采用2位二進制碼許用碼組禁用碼組

000

001010100

111

101110

011采用3位二進制碼采用1位二進制碼019.2.2差錯控制的基本方法

在信息序列之后附加一些監(jiān)督碼元，這些多余的碼元與信息碼元之間以某種確定的規(guī)則相互關(guān)聯(lián)，接收端按照既定的規(guī)則檢驗出關(guān)聯(lián)關(guān)系，如這種規(guī)則受到破壞，將會發(fā)現(xiàn)錯誤，乃至糾正錯誤。例：7/28/20235檢錯與糾錯能力與最小碼距d0

的關(guān)系(c)為了同時檢測e個錯誤，糾正t個錯誤d0

≧

e＋t＋1，e>t(b)為了糾正t個錯誤d0

≧2t＋1(a)為了檢測e個錯誤，d0

≧

e＋1碼距：兩個碼組對應(yīng)位上不同的數(shù)目。碼重：碼組中“1”的數(shù)目。結(jié)論：最小碼距決定檢錯和糾錯能力。7/28/202369.2.3

差錯控制方式2.前向糾錯（FEC）

可糾錯的碼

發(fā)

收3.混和糾錯（HEC）

可以發(fā)現(xiàn)和糾正錯誤

發(fā)

收

應(yīng)答信號

比較：譯碼復(fù)雜性、實時性和占用傳輸鏈路(單向還是雙向)。1.檢錯重發(fā)（ARQ）

可檢錯的碼

發(fā)收

應(yīng)答信號ARQ：自動重復(fù)請求發(fā)送接收端所識別到的錯誤超過了自身的糾錯能力時，就請求發(fā)送端重發(fā)。7/28/202379.2.4差錯控制編碼的效用

假設(shè)在隨機信道中發(fā)“0”和發(fā)“1”的概率相同，在碼長為n的碼組中恰好發(fā)生r個錯誤的概率為：(p為誤碼率)當(dāng)碼長n＝7，誤碼率時，則有：結(jié)論：采用差錯控制編碼，即使僅能糾正（或檢測）1～2個錯誤，就能使誤碼率下降幾個數(shù)量級。（9.2-4）

7/28/202389.2.5

糾錯碼的分類1.分組碼與卷積碼分組碼：將信息碼分組，為每組信息碼后面附加若干位監(jiān)督碼元，且

監(jiān)督碼元僅監(jiān)督本碼組中的信息位。卷積碼：將信息序列分組，后面附加監(jiān)督位，但監(jiān)督位不但與本碼組的信息位有關(guān)，還與前面碼組的信息位有關(guān)，或者說監(jiān)督位不僅監(jiān)督本碼組的信息位還監(jiān)督其它碼組的信息位。2.系統(tǒng)碼與非系統(tǒng)碼系統(tǒng)碼：

就是信息位在前，監(jiān)督位在后的碼字。非系統(tǒng)碼:信息位與監(jiān)督位之間無特定的位置關(guān)系。編碼效率：k/n（

n，k）碼

7/28/20239

9.3常用的簡單糾錯碼9.3.1

奇偶校驗構(gòu)成：n-1位信息位、1位監(jiān)督位。n位編碼構(gòu)成以下約束關(guān)系接收端計算校正子（偶監(jiān)督）檢錯能力：所有奇數(shù)個錯誤。一半！應(yīng)用非常廣泛。編碼效率：7/28/2023109.3.2縱向奇偶校驗（LRC）－用于檢測突發(fā)錯誤1110011111011101001110011010100111100111110111010011100110101001縱向排列原始數(shù)據(jù)1110011111011101001110011010100110101010突發(fā)錯誤接收方檢驗是否滿足LRCLRC

10101010監(jiān)督碼元交織編碼：針對突發(fā)性錯誤n位的LRC可以檢測一個n位突發(fā)錯誤。7/28/202311

信息

碼

元

0101101100010101001000110000111100011100001111111100010011111110110000監(jiān)督碼元

0011100001

0監(jiān)督碼元

10010119.3.3水平垂直奇偶校驗（二維）●它能發(fā)現(xiàn)某一行或某一列上所有奇數(shù)個錯誤以及長度不大于行數(shù)（或列數(shù)）的突發(fā)錯誤?！窨蓹z某些偶數(shù)個錯誤。

●具有一定的糾錯能力。7/28/2023129.3.4群計數(shù)碼111001100信息位監(jiān)督位功能：發(fā)現(xiàn)所有奇數(shù)個錯誤，以及一些偶數(shù)個錯誤，除“0”變“1”，和“1”變“0”成對出現(xiàn)。規(guī)則：信息碼元分組后計算“1”的個數(shù)，然后將這個數(shù)目的二進制碼元表示作為監(jiān)督碼元附加在信息碼元之后。7/28/2023139.3.5等重碼（恒比碼）功能：檢測所有奇數(shù)個錯誤，以及一些偶數(shù)個錯誤，除“0”變“1”，和“1”變“0”成對出現(xiàn)。數(shù)字電碼數(shù)字電碼

001101500111101011610101211001711100310110801110411010910011表9-3電傳五中取三碼許用碼組:C35=10禁用碼組:25-10=22編碼效率：等重碼是從特定碼長的碼組中，選取固定個數(shù)的“1”作為碼組的許用碼組，這種碼de碼重相同，或“1”與“0”之比保持恒定。例：我國電傳漢字電碼，每個漢字用4位阿拉伯?dāng)?shù)字表示，每個阿拉伯?dāng)?shù)字又用5位二進制符號表示，其中3個“1”，碼重為3。7/28/2023149.4

線性分組碼定義：信息位和監(jiān)督位之間的關(guān)系由線性方程組約束的分組碼稱作線性分組碼。特征：督元由信元的線性組合而產(chǎn)生。奇偶校驗碼就是一種效率很高的線性分組碼。這里S稱為校正子：若S＝0，表示無錯，S＝1表示有錯。

●因僅用了1位監(jiān)督位a0

，所計算的1個校正子只能表示有錯與無錯。

●若監(jiān)督位增加到2位，就可增加一個監(jiān)督方程式，便可獲得2個校正子S1、S2，于是：7/28/202315推廣：顯然：要求2r-1≥n（n=k+r），則可指示（僅一位錯時）任一錯碼的位置－－包括信元、督元。 或： 2r≥k+r+1對于二進制編碼，知道了錯誤的位置，就可以實現(xiàn)糾錯了。7/28/202316●一般說來對于(n，k)碼。要想指出一位錯碼的所有可能位置，則要求：對于糾正t個錯誤，需滿足：（糾正1個錯誤）7/28/2023179.4.1線性分組碼的構(gòu)成例：構(gòu)造k＝4的漢明碼（能糾一位錯的線性分組碼）。（1）確定r

由得r≧3，取r＝3，則n＝7。（7,4）碼?。?）寫出校正子的編碼表7/28/202318表9-4校正子表

S1S2S3

誤碼位置

S1S2S3

誤碼位置

001

a0101a4

010a1110a5

100a2111a6

011a3000無錯因此接收端計算下面3個校驗關(guān)系，可確定誤碼的位置:校正子表不是唯一的!這里的“+”代表模2和

（2）寫出校正子的編碼表----r=3

共有3個校正子7/28/202319發(fā)送端構(gòu)成偶校驗方程→可得督--信方程（線性組合）表9-516個許用碼組！信息位監(jiān)督位信息位監(jiān)督位

0000000100011100010111001100001010110100100011110101100101001101100001010110111010100110011111010001110001111111（3）生成全部許用碼組7/28/2023209.4.2線性分組碼的監(jiān)督矩陣和生成矩陣1.

監(jiān)督矩陣－從校驗方程入手記為或有7/28/202321其中：----監(jiān)督矩陣

----碼組的行矩陣

----零矩陣

可見：H一旦確定，督元和信元之間的關(guān)系也就確定了。若:----則稱H為典型陣。由線性代數(shù)理論：典型陣各行一定是線性無關(guān)的；非典型陣可通過矩陣的初等變換化為典型陣。7/28/2023222.生成矩陣矩陣形式:－－從督信方程入手由7/28/202323寫成行陣形式:其中Q=PT。上式表明：信息位給定后，就產(chǎn)生了監(jiān)督位！進一步，令生成矩陣

G=[Ik

Q]則，碼組行陣 A=[a6a5a4a3]G

Q能生成督元G才生成線性分組碼如何裝配：信元＋督元？7/28/202324例：生成矩陣討論：●由信息位與生成矩陣G相乘可得到全部碼字A?！窬哂?/p>

[Ik

Q]形式的生成矩陣稱為典型生成陣?！裼傻湫蜕删仃嚨贸龅拇a組為系統(tǒng)碼。碼組行陣：督元由相應(yīng)的信息位決定！7/28/202325一般形式:

A=[an-1an-2…ar]G

3.G

和H

的關(guān)系由Q=PT

或P=QT

則:H=[P·Ir

]

G=[Ik

·Q]綜上：線性分組碼的編碼，就是根據(jù)其監(jiān)督陣H或生成陣G將長為k的信息碼編成長為n的碼組。7/28/2023264.線性分組碼的性質(zhì)（1）封閉性

設(shè)：

A1、A2

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

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

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

即A1+A2也是一個碼組。結(jié)論：線性碼組中任意兩個碼字之和，仍為該線性碼組之碼字。（2）線性分組碼的最小距離等于非零碼的最小重量。即

: d0=Wmin（除全0碼組）證：由封閉性得，兩個碼組之間的距離（之差），必是另一碼組的重量。故最小碼距即是碼的最小重量！7/28/2023279.4.3線性分組碼的伴隨式譯碼設(shè)：發(fā)送碼組為A，接收碼組為R。則：

R-A＝E（模2）

為錯誤行陣或錯誤圖樣。對于前面（7，4）碼的例子，一位錯誤圖樣為：(1000000),(0100000)，(0010000)，(0001000)，(0000100)，(0000001),(0000001)計算校正子或伴隨式：結(jié)論：校正子S僅與錯誤圖案有關(guān)，與發(fā)送碼組無關(guān)。7/28/202328伴隨式與糾錯：結(jié)論：校正子S只與E有關(guān)，若接收碼字R中第i位有錯，那么導(dǎo)出的伴隨式恰好同于監(jiān)督矩陣H的第i列。例：對于前面（7，4）碼例子，一位錯誤圖樣為：(1000000),(0100000)，(0010000)，(0001000)，(0000100)，(0000001),(0000001)，分別計算當(dāng)錯誤圖樣為上面七種形式之一時的伴隨式值。7/28/202329結(jié)論：利用伴隨式不僅可以判決接收碼字中是否有錯，而且可以指出差錯的位置。7/28/202330例：若接收的碼組為1001101，請指出錯誤位置并譯碼。解：計算伴隨式

最后一位有錯，譯碼得：1001100。7/28/2023319.5.1循環(huán)碼的概念

定義：是一種具有循環(huán)移位特性的線性分組碼。

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

9.5

循環(huán)碼

構(gòu)成原理：

具有線性分組碼的所有性質(zhì)之外，還具有循環(huán)性：循環(huán)碼中任一許用碼組經(jīng)過循環(huán)移位后，所得到的碼組仍然是許用碼組。7/28/202332碼多項式定義：

為了利用代數(shù)理論研究循環(huán)碼，可以將碼組用代數(shù)多項是來表示，這個多項式被稱為碼多項式。設(shè)：許用循環(huán)碼A=(an-1

an-2…a1

a0)則：它的碼多項式表示為：其中：xi僅是碼元位置的標(biāo)記。碼字與碼多項式一一對應(yīng)！7/28/202333表9-6(7，3)循環(huán)碼反之，由碼多項式易得出碼組。7/28/2023342.碼多項式的按模運算1）整數(shù)的按模運算若一個整數(shù)m可以表示為:則在模n運算下，有m≡p（模n）。例：同樣對于多項式而言，也有類似按模運算。7/28/202335其中：商Q(x)為多項式，余數(shù)R(x)的冪次低于N(x)的冪次。例:

求

x4+x2+1按模

x3+1

運算的余式R(x)2）碼多項式的按模運算 若則7/28/202336

3）循環(huán)性可以證明：在循環(huán)碼中，若A(x)

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

在按模xn+1運算下，亦是許用碼組。即若有則A'(x)也是一個許用碼組。例:

前述（7，3）碼：A(x)=x6+x5+x4+x2

（1110100）－－前碼組循環(huán)左移1位！多項式除法：余式7/28/2023379.5.2循環(huán)碼的生成多項式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)！7/28/202338（2）生成多項式g(x)與生成矩陣G(x)的關(guān)系A(chǔ)=[an-1…ar

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

g(x)、……、xk-1

g(x)都是碼組，且這k個碼組信息無關(guān)，因此可以用來構(gòu)成生成矩陣。g(x)確定了→G(x)也就確定了→整個碼組即確定！7/28/202339例:

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

求典型生成矩陣解:可方便地直接寫成碼組形式典型陣:7/28/202340（3）生成多項式g(x)與碼多項式A(x)的關(guān)系－－（7，3）表明：所有A(x)都可以被g(x)整除，而且任一次數(shù)不大于(k-1)的多項式乘以g(x)都是碼多項式。

A(x)∣模g(x)=0。h(x)為不大于(k-1)的多項式！7/28/202341結(jié)論:

g(x)是xn+1的一個(n-k)次的因子，且常數(shù)項不為零。證明：任一循環(huán)多項式A(x)都是g(x)的倍式，即而生成多項式g(x)本身也是一個碼組，即有由于碼組A'(x)為一（n-k）次多項式，故xkA'(x) 為一n次多項式。由知，xkA'

(x)在模（xn+1）的運算下，亦為一碼組，故可寫成（4）如何尋找g(x)7/28/202342上式左端分子和分母都是n次多項式，故商Q(x)＝1，因此上式可化成即將A(x)=h(x)g(x)、A'(x)=g(x)代入，并整理，得表明:

g(x)應(yīng)該是xn+1的一個因式！證得:

g(x)是xn+1的一個(n-k)次的因子，且常數(shù)項不為零。7/28/202343例：如(x7+1)=(x+1)(x3+x2+1)(x3+x+1)則有g(shù)(x)：

（7，4）：x3+x2+1、x3+x+1

（7，3）：(x+1)(x3+x2+1)、(x+1)(x3+x+1)

（7，6）：x+17/28/202344例:

（7，3）循環(huán)碼有多項式如下，找出（7，3）碼的生成多項式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ù)項不為零，有

（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

為生成多項式g(x)。7/28/202345表9-7(7,k)循環(huán)碼結(jié)論：循環(huán)碼完全由其碼組長度n及生成多項式g(x)決定。表中：h(x)稱為監(jiān)督多項式。7/28/202346例9.5.1

一個(7，4)循環(huán)碼的生成多項式為確定該循環(huán)碼的典型化的生成矩陣和監(jiān)督矩陣。解：由g(x)構(gòu)成的生成矩陣為：典型生成矩陣：典型監(jiān)督矩陣：7/28/2023479.5.3系統(tǒng)循環(huán)碼的編碼實現(xiàn)系統(tǒng)碼組中的最左邊的k位是信息碼元，隨后是n-k位的監(jiān)督碼元，即碼多項式為：因此：

有：結(jié)論（編碼步驟）：m(x)xn-k/g(x)除法求余得到r

(x)；

m(x)xn-k+r(x)求得A(x)。m(x)—信息多項式

r(x)—監(jiān)督多項式7/28/202348例9.5.2已知(7，4)循環(huán)碼的生成多項式為若信息碼為1001

，求編碼碼字。因此：解：

即：編碼碼組為：1001011或：直接由信息碼元1001+監(jiān)督碼元011拼接而成！7/28/202349上述編碼過程，在硬件實現(xiàn)時，可以利用除法電路（曹志剛p344－348）來實現(xiàn)。編碼的電路7/28/202350工作過程：信息輸入時，開關(guān)合2：輸入碼一方面輸入除法器，另一方面直接輸出，在信息位全部進入除法器后－－開關(guān)合1：輸出端接到移位寄存器，將移位寄存器中存儲的余項依次輸出，同時切斷反饋線。系統(tǒng)碼！7/28/202351循環(huán)碼的譯碼可以分三步進行：（1）由接收到的碼多項式R(x)計算校正子（伴隨式）多項式S(x)；（2）由校正子S(x)確定錯誤圖樣E(x)；（3）將錯誤圖樣E(x)與B(x)相加，糾正錯誤。

9.5.4

循環(huán)碼的譯碼7/28/2023529.6交織碼，9.7卷積碼，9.8TCM為選講內(nèi)容可根據(jù)課時情況選擇講授7/28/202353前面介紹的線性分組碼和循環(huán)碼都是用來糾正隨機錯誤的，交織碼是一種糾正和檢測突發(fā)錯誤的分組碼。在縱向奇偶校驗碼中，按列進行檢驗，就可以檢測出每一行上不超過列數(shù)的突發(fā)性錯誤，這種方法同樣可以用于糾正突發(fā)性錯誤，由此構(gòu)造的糾錯碼稱為交織碼。

*9.6糾正和檢測突發(fā)錯誤的分組碼---交織碼7/28/202354（1）若將能糾正t個隨機錯誤的碼作為方陣的行碼，m個行碼組構(gòu)成一個方陣，這種交織碼保證可以糾正t個突發(fā)長度為m的突發(fā)錯誤。（2）但若將能糾正b個突發(fā)錯誤的碼作為行碼，則m個行碼組構(gòu)成的方陣，可以保證糾正長度為b·m個突發(fā)錯誤。m行、n列交織度m7/28/202355

編碼器輸出時，按列的順序自左至右讀出，這時的序列為:在接收端，將上述過程逆向重復(fù)，即把收到的序列按列寫入存儲器再按行讀出，這時就仍然恢復(fù)成原來的

(n,k)分組碼交織碼實際上是一種時間擴散技術(shù)，當(dāng)交織度足夠大時，就把突發(fā)錯誤離散成隨機錯誤，從而被分組碼所糾正,但是m受到傳輸時延的限制。7/28/202356因而(m

n,m

k)也是循環(huán)碼，(n,

k)碼中每一個碼組在(m

n,m

k)碼中對應(yīng)有一個碼組，它們有相同的碼重只是各碼元相隔

m位。

采用循環(huán)碼構(gòu)造交織碼時，不必用n×m陣列就能實現(xiàn)編碼，假設(shè)交織碼每行為(n,k)循環(huán)碼，其生成多項式為g(x)，則g(x)

必定能除盡xn+1。交織度為m的交織碼(m

n,m

k)，其生成多項式為，它的物理意義是在g(x)的各項之間插入(m-1)個0，顯然能除盡

。7/28/202357

例：用生成多項式為的（7，4）線性分組碼，構(gòu)成交織度為3的（21，12）交織碼，求交織碼的生成多項式及監(jiān)督矩陣。＋＋輸入(7,4)碼編碼器＋＋輸入(21，12)碼編碼器交織碼譯碼時，必須將碼元排列成n×m

陣列，然后分別獨立的對其進行譯碼。7/28/202358*9.7卷積碼(n，k，N)卷積碼通常用（n,k,N)來表示，它是把k個信息比特編成n個編碼比特，其中N定義為編碼約束長度，說明編碼過程中互相約束的碼段個數(shù)。

卷積碼的編碼器具有記憶性，任意時刻輸出的n個比特，不僅與當(dāng)前輸入的k比特有關(guān)系，還與前N-1個k比特輸入有關(guān)。因此，編碼過程中相互關(guān)聯(lián)的碼元就有nN個。定義ηc=k/n為卷積碼的編碼效率，ηc和N是衡量卷積碼性能的兩個重要參數(shù)。由于卷積碼的編碼過程充分利用了各碼組的相關(guān)性，且n和k也較小，因此，在與分組碼相同的編碼效率下，卷積碼的性能更優(yōu)。在相似的糾錯能力下，卷積碼的實現(xiàn)通常比分組碼更加簡單。

7/28/202359圖9-15卷積編碼器的一般形式9.7.1

卷積碼的基本原理

注：模2加法器輸入端的數(shù)目不一定相同。7/28/202360圖9-16(3,1,3)卷積碼編碼器(3,1,3)卷積編碼器的輸入與輸出邏輯關(guān)系為：(9.7-1)

例：以一個簡單的(3,1,3)卷積碼為例來簡述卷積碼的編碼過程，此時最高的編碼效率為ηc=1/3。

7/28/202361圖9-17(3,1,3)卷積碼樹狀圖

(每輸入0或1時輸出狀態(tài))9.7.2

卷積碼的圖解表示7/28/202362圖9-21閉合型狀態(tài)圖a,b,c,d

為移位寄存器狀態(tài)圖9-19(3,1,3)卷積碼網(wǎng)格圖輸入碼：10101狀態(tài)：1001100110輸出碼：111001100001100

7/28/2023639.7.3