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