第 差錯控制編碼PPT課件

1、2021-11-4111.1 概述 11.1.1 信道編碼 信元編碼：為了提高數(shù)字信號傳輸?shù)挠行远扇〉木幋a。 信道編碼：為了提高數(shù)字通信的可靠性而采取的編碼。 信道編碼方法：在信息序列上附加上一些監(jiān)督碼元，發(fā)現(xiàn)和糾正錯誤。第1頁/共35頁2021-11-42 11.1.2 差錯控制方式 發(fā)發(fā)可以糾正錯誤的碼(a) 前向糾錯(FEC)收收發(fā)能夠發(fā)現(xiàn)錯誤的碼應(yīng)答信號(b) 檢錯重發(fā)(ARQ)收可以發(fā)現(xiàn)和糾正錯誤的碼應(yīng)答信號(c) 混合糾錯檢錯(HEC)第2頁/共35頁2021-11-43 1、檢錯重發(fā)方式：檢錯重發(fā)（ARQ）的優(yōu)點主要表現(xiàn)在： （1）只需要少量的冗余碼，就可以得到極低的輸出誤碼

2、率； （2）有一定的自適應(yīng)能力； 某些不足主要表現(xiàn)在： （1）需要反向信道，故不能用于單向傳輸系統(tǒng)，并且實現(xiàn)重發(fā)控制比較復(fù)雜； （2）通信效率低，不適合嚴格實時傳輸系統(tǒng)。第3頁/共35頁2021-11-442、前向糾錯 發(fā)送端經(jīng)信道編碼后可以發(fā)出具有糾錯能力的碼字；接收端譯碼后不僅可以發(fā)現(xiàn)錯誤碼，而且可以判斷錯誤碼的位置并予以自動糾正。 3、混合糾錯方式 混合糾錯方式是前向糾錯方式和檢錯重發(fā)方式的結(jié)合。 第4頁/共35頁2021-11-45 11.1.3 糾錯編碼的分類 （1）按照信道編碼的不同功能，可以將它分為檢錯碼和糾錯碼。 （2）按照信息碼元和監(jiān)督碼元之間的檢驗關(guān)系，可以將它分為線性和非

3、線性碼。 （3）按照信息碼元和監(jiān)督碼元之間的約束方式不同，可以將它分為分組碼和卷積碼。 （4）按照信息碼元在編碼后是否保持原來的形式，可以將它分為系統(tǒng)碼和非系統(tǒng)碼。 第5頁/共35頁2021-11-46 （5）按照糾正錯誤的類型不同，可以將它分為糾正隨機錯誤碼和糾正突發(fā)錯誤碼。 隨著數(shù)字通信系統(tǒng)的發(fā)展，可以將信道編碼器和調(diào)制器統(tǒng)一起來綜合設(shè)計，這就是所謂的網(wǎng)格編碼調(diào)制。 11.1.4 糾錯編碼的基本原理 1、分組碼 表示為（n，k）, n表示碼組的長度； k信息的長度；r = n-k表示監(jiān)督位長度。 幾個概念：第6頁/共35頁2021-11-47 碼長：碼字中碼元的數(shù)目； 碼重：碼字中非0數(shù)字

4、的數(shù)目； 碼距：兩個等長碼字之間對應(yīng)位不同的數(shù)目，有時也稱作這兩個碼字的漢明距離。 最小碼距：在碼字集合中全體碼字之間距離的最小數(shù)值。 糾錯碼的抗干擾能力完全取決于許用碼字之間的距離，碼的最小距離越大，說明碼字間的最小差別越大，抗干擾能力就越強。 第7頁/共35頁2021-11-48 分組碼的最小漢明距離為d0 2、檢錯和糾錯能力 （1）當碼字用于檢測錯誤時，如果要檢測e個錯誤，則 d0 e + 1； （2）當碼字用于糾正錯誤時，如果要糾正t個錯誤，則 d0 2t + 1； （3）若碼字用于糾t個錯誤，同時檢e個錯誤時（e t），則 d0 t + e +1。 第8頁/共35頁2021-11-4

5、9eBAd0tAtB1tAeB1(a)(b)(c)d0d0編碼效率Rc可以用下式表示：nrnrnnkRc1第9頁/共35頁2021-11-41011.2 常用的幾種簡單分組碼 11.2.1 奇偶監(jiān)督碼 可以表示成為（n，n-1）。如果是奇監(jiān)督碼，在附加上一個監(jiān)督元以后，碼長為n的碼字中“1”的個數(shù)為奇數(shù)個；如果是偶監(jiān)督碼，在附加上一個監(jiān)督元以后，碼長為n的碼字中“1”的個數(shù)為偶數(shù)個。 an-1+ an-2+ + a1+ a0 = 0 第10頁/共35頁2021-11-411 奇偶監(jiān)督碼的編碼可以用軟件實現(xiàn)，也可用硬件電路實現(xiàn)。 如果碼組B無錯，BA，則M0；如果碼組B有單個（或奇數(shù)個）錯誤，則

6、M1。 編碼效率 : R=(n-1)/na4a3a2a1a0a4a3a2a1信息組編碼輸出b0b4b3b2b1接收碼組檢錯信號SBAM第11頁/共35頁2021-11-412 11.2.2 行列監(jiān)督碼 行列監(jiān)督碼又稱水平垂直一致監(jiān)督碼或二維奇偶監(jiān)督碼，有時還被稱為矩陣碼。1 1 0 0 1 0 1 0 0 00 1 0 0 0 0 1 1 0 10 1 1 1 1 0 0 0 0 11 0 0 1 1 1 0 0 0 01 0 1 0 1 0 1 0 1 000101 1 1 0 0 0 1 1 1 1 0 0第12頁/共35頁2021-11-413 二維奇偶監(jiān)督碼適于檢測突發(fā)錯碼。二維奇偶監(jiān)

7、督碼不僅可用來檢錯，還可用來糾正一些錯碼。 11.2.3 恒比碼 恒比碼又稱等重碼，該碼的碼字中1和0的位數(shù)保持恒定的比例。具體情況見表11.2.1。 目前我國電傳通信中普遍采用3：2碼，國際上通用的ARQ電報通信系統(tǒng)中，采用3：4碼即7中取3碼。 第13頁/共35頁2021-11-41411.3 線性分組碼 11.3.1 基本概念 分組碼是一組固定長度的碼組，可表示為（n , k），通常它用于前向糾錯。在編碼時，k個信息位被編為n位碼組長度，而n-k個監(jiān)督位的作用就是實現(xiàn)檢錯與糾錯。 這樣，一個k比特信息的線性分組碼可以映射到一個長度為n碼組上。 第14頁/共35頁2021-11-415 線

8、性分組碼的主要性質(zhì)如下： （1）任意兩許用碼之和仍為一許用碼，也就是說，線性分組碼具有封閉性； （2）碼組間的最小碼距等于非零碼的最小碼重。 對偶校驗時的監(jiān)督關(guān)系。在接收端解碼時，實際上就是在計算： S = bn-1+bn-2+ +b1+b0 若S0，則無錯；若S1就認為有錯。 第15頁/共35頁2021-11-416 以（7，4）碼為例進行分析，可以設(shè)碼字A= a6,a5 , a4,a3 a2,a1 ,a0 ，其中 a6,a5 , a4,a3 為信息位， a2,a1 ,a0 為監(jiān)督位，進而得到下面的方程組形式： 不難看出，上述（7，4）碼的最小碼距dmin3。000034613562456a

9、aaaaaaaaaaaaaaaaaaaaaaa034613562456第16頁/共35頁2021-11-417 11.3.2 監(jiān)督矩陣H和生成矩陣G 將（7，4）碼的三個監(jiān)督方程式可以重新改寫為如下形式：上式可以記作：HAT=0T或AHT=0 ，其中 010011010010101100010111012345601234560123456aaaaaaaaaaaaaaaaaaaaa0001001101010101100101110123456Taaaaaaa第17頁/共35頁2021-11-418rIPH1001101010101100101110000aaaaaaa0123456A也可以用矩

10、陣形式來表示：或表示成為： 這時Q = PT，如果在Q矩陣的左邊在加上一個kk的單位矩陣，就形成了一個新矩陣G： 3456012110110110111aaaaaaa Q34563456012110101011111aaaaaaaaaaa第18頁/共35頁2021-11-4191101000101010001100101110001QIGk 這里G稱為生成矩陣，利用它可以產(chǎn)生整個碼組： 11.3.3 校驗子S 設(shè)發(fā)送組碼A，在傳輸過程中有可能出現(xiàn)誤碼，這時接收到的碼組為B。則收發(fā)碼組之差為：GGMA3456aaaa021021021eeeaaabbbnnnnnnEAB第19頁/共35頁2021

11、-11-420其中： 則接收端利用接收到的碼組B計算校正子： S=BHT=(A+E)HT= AHT + EHT = EHT 因此，校正子僅與E有關(guān)，即錯誤圖樣與校正子之間有確定的關(guān)系。 漢明碼就是一個線性分組碼。有以下特點： （1）最小碼距dmin3，可糾正一位錯誤； （2）碼長n與監(jiān)督元個數(shù)r之間滿足iiiiiababe1012 rn第20頁/共35頁2021-11-42111.4 循環(huán)碼 循環(huán)碼是線性分組碼的一個重要子集，是目前研究得最成熟的一類碼，它有許多特殊的代數(shù)性質(zhì)。 特點：循環(huán)碼中任一許用碼組經(jīng)過循環(huán)移位后，所得到的碼組仍然是許用碼組。 描述：許用循環(huán)碼A=(an-1 an-2 a

12、1 a0)，可以將它的碼多項式表示為： 012211axaxaxaxAnnnn第21頁/共35頁2021-11-422若一個整數(shù)m可以表示為: : 則在模n運算下，有mp（模n），同樣對于多項式而言：則可以寫為：F(x)R(x) （模N(x)）。 在循環(huán)碼中，若A(x)是一個長為n的許用碼組，則在按模 運算下，亦是一個許用碼組。是整數(shù)QnpnpQnm xNxRxQxNxF1nx 1172353589256373xxxxxxxxxxxxxxAx模第22頁/共35頁2021-11-42311.4.1 生成多項式及生成矩陣 循環(huán)碼中次數(shù)最低的碼多項式稱為生成多項式，用g(x)表示。可以證明生成多項式

13、g(x)具有以下特性： （1） g(x)是一個常數(shù)項為1的 次多項式； （2） g(x)是 的一個因式； （3）該循環(huán)碼中其它碼多項式都是g(x)的倍式。 knr1nx第23頁/共35頁2021-11-424 為了保證構(gòu)成的生成矩陣G的各行線性不相關(guān)，通常用g(x)來構(gòu)造生成矩陣， 顯然，上式不符合 形式，所以此生成矩陣不是典型形式。 xgxgxxgxxgxxkk21G 因此，一旦生成多項式g(x)確定以后，該循環(huán)碼的生成矩陣就可以確定。 1111xaxaxxgrrrQIGk第24頁/共35頁2021-11-42511.4.2 監(jiān)督多項式及監(jiān)督矩陣 利用循環(huán)碼的特點來確定監(jiān)督矩陣H： 由于（n

14、,k）循環(huán)碼中g(shù)(x)是xn +1的因式，因此可令： 監(jiān)督矩陣表示為：其中： 11111xhxhxxgxxhkkkn xhxhxxhxxhxxHknkn21 112211xhxhxhxxhkkkk第25頁/共35頁2021-11-426 11.4.3 編碼方法和電路 1、編碼過程 首先需要根據(jù)給定循環(huán)碼的參數(shù)確定生成多項式g(x) ，然后，利用循環(huán)碼的編碼特點，即所有循環(huán)碼多項式A(x)都可以被g(x)整除，來定義生成多項式A(x)。下面就將以上各步處理加以解釋： （1）用xn-k乘m(x)。這一運算實際上是把信息碼后附加上（n-k）個“0”。 第26頁/共35頁2021-11-427 （2）

15、求R(x)。由于循環(huán)碼多項式A(x)都可以被g(x)整除，也就是：上式也等效于：這樣我們就得到了R(x)。 （3）編碼輸出系統(tǒng)循環(huán)碼多項式A(x)為： xgxRxgxmxxgxrxmxxQxgxAknkn xgxRxQxgxmxkn xRxmxxAkn第27頁/共35頁2021-11-428 上述三步編碼過程，在硬件實現(xiàn)時，可以利用除法電路來實現(xiàn)。 11.4.4 譯碼方法和電路 循環(huán)碼的譯碼可以分三步進行： （1）由接收到的碼多項式B(x)計算校正子（伴隨式）多項式S(x)； abcd1122輸出輸入mef第28頁/共35頁2021-11-429 （2）由校正子S(x)確定錯誤圖樣E(x)；

16、（3）將錯誤圖樣E(x)與B(x)相加，糾正錯誤。校正子計算電路錯誤圖樣識別k級緩存器輸入糾錯后輸出12n-k第29頁/共35頁2021-11-43011.4.5 BCH碼 特點：它的生成多項式g(x)與最小碼距之間有密切的關(guān)系，可以根據(jù)所要求的糾錯能力t，很容易地構(gòu)造出BCH碼。 相關(guān)知識：本原多項式的定義： (1) f(t)為既約多項式； (2) f(t)是(xp+1)因子，p=2n-1 (3) f(t)不是(xq+1)的因子， pq第30頁/共35頁2021-11-43111.5 糾正和檢測突發(fā)錯誤分組碼11.5.1 交錯碼11.5.2 Fire碼11.5.3 RS碼第31頁/共35頁2021-11-43211.6 卷積碼 卷積碼中編碼后的n個碼元不僅與當前段的k個信息有關(guān)，而且也與前面（N-1）段的信息有關(guān)，編碼過程中相互關(guān)聯(lián)的碼元為nN個。因此，這N段時間內(nèi)的碼元數(shù)目nN通常被稱為這種碼的約束長度。 由于與前面m段規(guī)定時間內(nèi)的信息位有關(guān)，這里的mN-1通常用（n，k，m）表示卷積碼 。第32頁/共35頁2021-11-433 例