[信息與通信]計算及通信第8章 差錯控制編碼.ppt

2019/4/14,1,第8章 差錯控制編碼,8.1 引言 8.2 常用簡單分組碼 8.3 線性分組碼 8.4 循環(huán)碼 8.5 卷積碼,2019/4/14,2,8.1 引言,8.1.1 信源編碼與信道編碼的基本概念 在數(shù)字通信系統(tǒng)中，為了提高數(shù)字信號傳輸?shù)挠行远扇〉木幋a稱為信源編碼；為了提高數(shù)字通信的可靠性而采取的編碼稱為信道編碼。 1、信源編碼,2019/4/14,3,2、信道編碼（差錯控制編碼） 差錯控制編碼是在信息序列上附加上一些監(jiān)督碼元，利用這些冗余的碼元，使原來不規(guī)律的或規(guī)律性不強的原始數(shù)字信號變?yōu)橛幸?guī)律的數(shù)字信號；差錯控制譯碼則利用這些規(guī)律性來鑒別傳輸過程是否發(fā)生錯誤，或進而糾正錯誤。,2019/4/14,4,8.1.2 糾錯編碼的分類 （1）按照信道編碼的不同功能，可以將它分為檢錯碼和糾錯碼。 （2）按照信息碼元和監(jiān)督碼元之間的檢驗關(guān)系，可以將它分為線性和非線性碼。 （3）按照信息碼元和監(jiān)督碼元之間的約束方式不同，可以將它分為分組碼和卷積碼。 （4）按照信息碼元在編碼后是否保持原來的形式，可以將它分為系統(tǒng)碼和非系統(tǒng)碼。,2019/4/14,5,（5）按照糾正錯誤的類型不同，可以將它分為糾正隨機錯誤碼和糾正突發(fā)錯誤碼。 （6）按照信道編碼所采用的數(shù)學(xué)方法不同，可以將它分為代數(shù)碼、幾何碼和算術(shù)碼。 隨著數(shù)字通信系統(tǒng)的發(fā)展，可以將信道編碼器和調(diào)制器統(tǒng)一起來綜合設(shè)計，這就是所謂的網(wǎng)格編碼調(diào)制。,2019/4/14,6,8.1.2 差錯控制方式,2019/4/14,7,檢錯重發(fā)方式： 檢錯重發(fā)（ARQ）的優(yōu)點主要表現(xiàn)在： （1）只需要少量的冗余碼，就可以得到極低的輸出誤碼率； （2）有一定的自適應(yīng)能力；,2019/4/14,8,某些不足主要表現(xiàn)在： （1）需要反向信道，故不能用于單向傳輸系統(tǒng)，并且實現(xiàn)重發(fā)控制比較復(fù)雜； （2）通信效率低，不適合嚴(yán)格實時傳輸系統(tǒng)。 混合糾錯方式是前向糾錯方式和檢錯重發(fā)方式的結(jié)合。,2019/4/14,9,8.1.2 糾錯編碼的基本原理 信道編碼有關(guān)的基本概念： 碼長：碼字中碼元的數(shù)目； 碼重：碼字中非0數(shù)字的數(shù)目； 碼距：兩個等長碼字之間對應(yīng)位不同的數(shù)目，有時也稱作這兩個碼字的漢明距離。 最小碼距：在碼字集合中全體碼字之間距離的最小數(shù)值。,10,糾錯碼的抗干擾能力完全取決于許用碼字之間的距離，碼的最小距離越大，說明碼字間的最小差別越大，抗干擾能力就越強。 分組碼的最小漢明距離d0與檢錯和糾錯能力之間滿足下列關(guān)系： （1）當(dāng)碼字用于檢測錯誤時，如果要檢測e個錯誤，則 d0 e+1； （2）當(dāng)碼字用于糾正錯誤時，如果要糾正t個錯誤，則 d0 2t+1；,2019/4/14,11,（3）若碼字用于糾t個錯誤，同時檢e個錯誤時（et），則 d0 t+e+1。 編碼效率Rc可以用下式表示：,2019/4/14,12,8.2 常用簡單分組碼,8.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,2019/4/14,13,奇偶監(jiān)督碼的編碼可以用軟件實現(xiàn)，也可用硬件電路實現(xiàn)。 如果碼組B無錯，BA，則M0；如果碼組B有單個（或奇數(shù)個）錯誤，則M1。,2019/4/14,14,8.2.2 行列監(jiān)督碼 行列監(jiān)督碼又稱水平垂直一致監(jiān)督碼或二維奇偶監(jiān)督碼，有時還被稱為矩陣碼。,2019/4/14,15,二維奇偶監(jiān)督碼適于檢測突發(fā)錯碼。二維奇偶監(jiān)督碼不僅可用來檢錯，還可用來糾正一些錯碼。 8.2.3 恒比碼 恒比碼又稱等重碼，該碼的碼字中1和0的位數(shù)保持恒定的比例。具體情況見表8-3。 目前我國電傳通信中普遍采用3：2碼，國際上通用的ARQ電報通信系統(tǒng)中，采用3：4碼即7中取3碼。,2019/4/14,16,8.3 線性分組碼,8.3.1 基本概念 分組碼是一組固定長度的碼組，可表示為（n , k），通常它用于前向糾錯。在編碼時，k個信息位被編為n位碼組長度，而n-k個監(jiān)督位的作用就是實現(xiàn)檢錯與糾錯。 這樣，一個k比特信息的線性分組碼可以映射到一個長度為n碼組上。,2019/4/14,17,線性分組碼的主要性質(zhì)如下： （1）任意兩許用碼之和仍為一許用碼，也就是說，線性分組碼具有封閉性； （2）碼組間的最小碼距等于非零碼的最小碼重。 對偶校驗時的監(jiān)督關(guān)系。在接收端解碼時，實際上就是在計算： S = bn-1+bn-2+b1+b0 若S0，則無錯；若S1就認(rèn)為有錯。,2019/4/14,18,當(dāng)r個監(jiān)督方程式計算得到的校正子有r位，可以用來指示2r-1種誤碼圖樣。 如果希望用r個監(jiān)督位構(gòu)造出r個監(jiān)督關(guān)系式來指示一位錯碼的n種可能，則要求： 例如r 3，若取r = 3，則n = k+r = 7。假設(shè)S3、S2、S1三位校正字碼組與誤碼位置的關(guān)系如表8-4。根據(jù)表8-4，可以構(gòu)成如下關(guān)系式：,2019/4/14,19,S1= a6+a5+a4+a2 , S2= a6+a5+a4+a2 , S3= a6+a4+a3+a0 進而得到下面的方程組形式： 接收端收到每個碼組后，計算出S3、S2和S1，如不全為0，則可按表8-4確定誤碼的位置，然后予以糾正。不難看出，上述（7，4）碼的最小碼距dmin3。,2019/4/14,20,8.3.2 監(jiān)督矩陣H和生成矩陣G 將（7，4）碼的三個監(jiān)督方程式可以重新改寫為如下形式： 上式可以記作：HAT=0T或AHT=0 ，其中,2019/4/14,21,也可以用矩陣形式來表示： 或表示成為： 這時Q = PT，如果在Q矩陣的左邊在加上一個kk的單位矩陣，就形成了一個新矩陣G：,2019/4/14,22,這里G稱為生成矩陣，利用它可以產(chǎn)生整個碼組：,2019/4/14,23,8.3.3 校驗子S 設(shè)發(fā)送組碼A，在傳輸過程中有可能出現(xiàn)誤碼，這時接收到的碼組為B。則收發(fā)碼組之差為： 其中： 則接收端利用接收到的碼組B計算校正子： S=BHT=(A+E)HT= AHT + EHT = EHT 因此，校正子僅與E有關(guān)，即錯誤圖樣與校正子之間有確定的關(guān)系。,2019/4/14,24,8.3.4 漢明碼 漢明碼是一種能夠糾正單個錯誤的線性分組碼。它有以下特點： （1）最小碼距dmin3，可糾正一位錯誤； （2）碼長n與監(jiān)督元個數(shù)r之間滿足關(guān)系式： 。 通常二進制漢明碼可以表示為：,2019/4/14,25,（7，4）系統(tǒng)漢明碼的編碼器和譯碼器電路：,2019/4/14,26,2019/4/14,27,8.4 循環(huán)碼,循環(huán)碼是線性分組碼的一個重要子集，是目前研究得最成熟的一類碼，它有許多特殊的代數(shù)性質(zhì)。 8.4.1 循環(huán)碼的特點 循環(huán)特性是指：循環(huán)碼中任一許用碼組經(jīng)過循環(huán)移位后，所得到的碼組仍然是許用碼組。,2019/4/14,28,為了利用代數(shù)理論研究循環(huán)碼，可以將碼組用代數(shù)多項是來表示，這個多項式被稱為碼多項式，對于許用循環(huán)碼A=(an-1 an-2 a1 a0)，可以將它的碼多項式表示為： 若一個整數(shù)m可以表示為: 則在模n運算下，有mp（模n），同樣對于多項式而言：,2019/4/14,29,則可以寫為：F(x)R(x) （模N(x)）。 在循環(huán)碼中，若A(x)是一個長為n的許用碼組，則在按模 運算下，亦是一個許用碼組。例如， 其對應(yīng)的碼組為0101110，它正是表8-7中第3碼字。,2019/4/14,30,8.4.2 循環(huán)碼的生成多項式和生成矩陣 循環(huán)碼中次數(shù)最低的碼多項式稱為生成多項式，用g(x)表示?？梢宰C明生成多項式g(x)具有以下特性： （1） g(x)是一個常數(shù)項為1的 次多項式； （2） g(x)是 的一個因式； （3）該循環(huán)碼中其它碼多項式都是g(x)的倍式。,2019/4/14,31,為了保證構(gòu)成的生成矩陣G的各行線性不相關(guān)，通常用g(x)來構(gòu)造生成矩陣， 顯然，上式不符合 形式，所以此生成矩陣不是典型形式。,因此，一旦生成多項式g(x)確定以后，該循環(huán)碼的生成矩陣就可以確定。,2019/4/14,32,利用循環(huán)碼的特點來確定監(jiān)督矩陣H： 由于（n,k）循環(huán)碼中g(shù)(x)是xn +1的因式，因此可令： 監(jiān)督矩陣表示為：,2019/4/14,33,8.4.3 循環(huán)碼的編、譯碼方法 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”。,2019/4/14,34,（2）求r(x)。由于循環(huán)碼多項式A(x)都可以被g(x)整除，也就是： 上式也等效于： 這樣我們就得到了r(x)。 （3）編碼輸出系統(tǒng)循環(huán)碼多項式A(x)為：,2019/4/14,35,上述三步編碼過程，在硬件實現(xiàn)時，可以利用除法電路來實現(xiàn)。 2、譯碼過程 循環(huán)碼的譯碼可以分三步進行： （1）由接收到的碼多項式B(x)計算校正子（伴隨式）多項式S(x)；,2019/4/14,36,（2）由校正子S(x)確定錯誤圖樣E(x)； （3）將錯誤圖樣E(x)與B(x)相加，糾正錯誤。,2019/4/14,37,8.5 卷積碼,卷積碼中編碼后的n個碼元不僅與當(dāng)前段的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