抗干擾編碼技術(shù)

1、第四章通信中的抗干擾編碼技術(shù)4.1 抗干擾編碼簡介信息在傳送的過程中，受到干擾會發(fā)生差錯，降低通信的可靠性。為提高所傳送信息的可靠性，采取專門的編碼方式，以提高其抗干擾能力。1、抗干擾編碼：通過編碼對要傳送的數(shù)據(jù)進行改造，使其內(nèi)部結(jié)構(gòu)具有一定的規(guī)律性和相關(guān)性，當(dāng)干擾破壞了碼字的部分結(jié)構(gòu)時，仍能根據(jù)碼字原有的規(guī)律性和相關(guān)性，發(fā)現(xiàn)甚至糾正錯誤。也稱為信道編碼、差錯控制。2、抗干擾編碼的一般方法：對要傳送的數(shù)據(jù)信息序列按照某種規(guī)律，添加一定的校驗碼元（監(jiān)督位），由信息序列和校驗碼構(gòu)成一個有抗干擾能力的碼字。 添加校驗碼元的規(guī)律或規(guī)則不同，就形成了不同的抗干擾編碼方法，傳送數(shù)據(jù)抗干擾能力的提高，是以犧

2、牲通信效率為代價的。1山東大學(xué)研究生課程電氣工程學(xué)院編碼效率為： 其中：k為傳送的有效數(shù)據(jù)碼元數(shù)，n為總的傳送碼元數(shù)。（3）實現(xiàn)編碼和譯碼的方法要簡便。一、最小碼距和碼的檢錯、糾錯能力 若用 k 表示要傳送的數(shù)據(jù)序列 m 的長度，用n表示經(jīng)抗干擾編碼后的碼字位數(shù)，則碼字中的校驗碼位數(shù)就是（nk）位，一般寫為：r nk，記做（n，k）碼，任意一個（n，k）碼可能包含的碼字最多可以有2k個。 在接收端，對收到的每一個碼字譯碼的時候，可以采用最大似然譯碼法，就是把收到的碼字同抗干擾編碼時可能出現(xiàn)的2k個碼字比較，看其與哪個碼字最相似，并將這個最相似的碼字作為正確的接收碼字。碼字的相似程度可以用碼距的

3、大小來判斷。1、碼距兩個同樣長度的碼字之間，對應(yīng)碼位上不相同的碼元數(shù)目，稱為兩個碼字的漢明距離，簡稱碼距。3、對抗干擾編碼的基本要求是：（1）碼的性能要好：能檢出或糾正最可能出現(xiàn)的那些錯誤類型；（2）編碼效率要高：所加監(jiān)督位要盡可能的少，編碼以后的傳輸效率要高；2山東大學(xué)研究生課程電氣工程學(xué)院 在一種碼的所有碼字集合中，任意兩個碼字之間的碼距并非相等，我們把所有可能的碼字對之間碼距的最小值，稱為這個碼字集合的最小碼距，記為dmin。2、碼重 碼字中非零碼元的個數(shù)，對于二進制碼元，就是碼字中“1”碼元的個數(shù)，用 W 來表示。3、線形分組碼： 對長度為k的數(shù)據(jù)，按一定規(guī)律增加 r 位監(jiān)督位，組成長

4、度為nkr 的碼元序列，Cn-1，Cn-2，C1，C0。這種按組進行編碼，碼的長度為n，其中有 k 位數(shù)據(jù)碼元的碼，叫做分組碼，記做（n，k）碼，rnk 是監(jiān)督位的長度。 分組碼中，監(jiān)督位與數(shù)據(jù)位之間滿足線性關(guān)系的（監(jiān)督位與數(shù)據(jù)位之間的關(guān)系是由一組線性方程來確定），稱為線性分組碼。 在一組線性分組碼中，任意兩個碼字相加（模2運算）得到的新碼字也在這組線性分組碼中。模 2 運算：當(dāng)相加的兩個碼字中對應(yīng)位的碼元不同時，新碼字中對應(yīng)位的碼元為“1”，否則為“0”。一組線性分組碼中，任意兩個碼字之間的碼距，正好等于這兩個碼字相加后所得新碼字的的碼重。 3山東大學(xué)研究生課程電氣工程學(xué)院4、碼的檢錯、糾錯

5、能力： 根據(jù)碼距的定義，兩個碼字的碼距越小則越相似，所謂最大似然譯碼就是根據(jù)這一點來實現(xiàn)的，根據(jù)接收到的碼字，與所有可能出現(xiàn)的碼字比較，和哪個碼字的碼距最小，就譯為哪個碼字。 一種碼的最小碼距是衡量這種編碼檢錯糾錯能力的重要參數(shù)，它能糾正的碼字中的錯誤個數(shù) t 和能檢出的錯誤個數(shù) l 滿足如下關(guān)系： 增加一種碼的最小碼距，可以提高這種碼的檢錯糾錯能力，這是以增加監(jiān)督位的位數(shù)、犧牲傳碼效率為代價的。例： 要傳送一個開關(guān)的狀態(tài)量，只需要一位二進制數(shù)就可以了，其最小碼距為1，因此它沒有檢錯糾錯能力。如果采用重復(fù)碼，用“11”和“00”分別代表合閘與分閘，則其最小碼距為2，它就能夠檢出一位錯誤，但還不

6、能糾錯；若用“111”和“000”分別代表合閘與分閘，其最小碼距變?yōu)?，則發(fā)生一位錯碼時，不僅能檢出來，還可以根據(jù)最大似然譯碼原則實現(xiàn)糾錯。4山東大學(xué)研究生課程電氣工程學(xué)院 抗干擾編碼就是通過某種編碼方法，對要傳送的k為位數(shù)據(jù)序列，按照某種規(guī)律添加校驗碼元（監(jiān)督位），以達到增大這種碼的最小碼距、提高其檢錯糾錯能力的目的。 一種好的抗干擾編碼方案，要既能最大程度的增加其檢錯糾錯能力，又有比較高的傳碼效率，而且易于實現(xiàn)。4.2 奇偶校驗碼一、奇偶校驗碼： 奇偶校驗碼是一個（n，n1）分組碼，它的編碼規(guī)則是在 n1 位有效數(shù)據(jù)位的后面，添加一位奇校驗或偶校驗碼元，使每個碼字中“1”碼元的個數(shù)恒為奇數(shù)

7、或偶數(shù)。 設(shè)碼字cn-1，cn-2，c1，c0，其中cn-1，cn-2，c1 為數(shù)據(jù)位， c0 為校驗碼元（監(jiān)督位）。當(dāng)碼字中的“1”碼元的個數(shù)恒為偶數(shù)時（偶校驗），滿足： 或： 這種碼稱為偶校驗碼。由此可知：偶校驗碼的校驗碼元等于數(shù)據(jù)碼元的模 2 和；5山東大學(xué)研究生課程電氣工程學(xué)院如果碼字中“1”的個數(shù)恒為奇數(shù)（奇校驗），則滿足： 或這種碼稱為奇校驗碼，奇校驗碼的校驗碼元等于數(shù)據(jù)碼元的模2和再取非。 奇偶校驗碼是應(yīng)用的最多的一種抗干擾編碼方式，最大的好處是實現(xiàn)簡單，編碼效率高，其編碼效率為： 但奇偶校驗碼的檢錯能力較差，不能糾錯。當(dāng)接收碼字錯奇數(shù)個碼元時，它能夠監(jiān)測出有錯碼，但不能分辯究竟

8、是哪一位碼元發(fā)生錯誤；若接收碼字錯偶數(shù)個碼元時，則其失去檢錯能力，會誤判為碼字中沒有錯誤發(fā)生。二、縱橫奇偶校驗： 縱橫奇偶校驗碼是在縱向和橫向兩個方向上都進行奇偶校驗的一種編碼方法，也稱為水平垂直奇偶校驗碼。下圖是縱橫奇偶校驗碼的構(gòu)成圖：6電氣工程學(xué)院山東大學(xué)研究生課程校驗位mk-1 mk-2 mk-jmk-(j+1) mk-(j+2) mk-2j| | | |mi-1 mi-2 m0 r1(j+1)r2(j+1)ri(j+1)|j列i 行r(i+1)1 r(i+1)2 r(i+1)j r(i+1)(j+1)校驗位把數(shù)據(jù)序列mk-1、mk-2、 m0 排成 i行 j 列的矩陣，然后在每一行和每

9、一列各補充一位奇偶校驗碼，這樣由行校驗位r1(j+1)、r2(j+1)、 r(i+1)(j+1)和列校驗位r(i+1)1、r(i+1)2、r(i+1)j 和數(shù)據(jù)位便構(gòu)同時具有縱向奇偶校驗位和橫向奇偶校驗位的縱橫奇偶校驗碼。 在實際的操作中，我們可以把要傳送的每一個字節(jié)做為一行，而把每個字節(jié)中的對應(yīng)位做為一列，實現(xiàn)縱橫奇偶校驗，對于每一列的校驗，可以采用每傳送一個字節(jié)，做一次異或操作（偶校驗）的辦法來實現(xiàn)。（奇校驗 ？）例：如有三個字節(jié)：第一個字節(jié)10110101第二個字節(jié)00011011第三個字節(jié)11100001縱向校驗碼01001111 1 0 1 1 0 1 0 1） 0 0 0 1 1

10、0 1 1 1 0 1 0 1 1 1 0） 1 1 1 0 0 0 0 1 0 1 0 0 1 1 1 17電氣工程學(xué)院山東大學(xué)研究生課程 這種縱橫奇偶校驗方式具有較強的檢錯能力，當(dāng)碼字中出現(xiàn)一位、兩位或三位錯誤時，不管錯誤位在上圖中如何分布，接收端通過譯碼都會發(fā)現(xiàn)橫向奇偶校驗出錯或縱向奇偶校驗出錯、或者橫向、縱向奇偶校驗同時出錯，從而實現(xiàn)檢錯。如果碼字中的錯誤位只有一位，這時同時會出現(xiàn)某一行和某一列的奇偶校驗出錯，則根據(jù)出錯的行號和列號，便可以確定錯誤位的位置，實現(xiàn)糾錯。因此，這種碼可以糾正一位錯誤、檢出三位以下的錯誤，是所謂的“糾一檢三碼”。除此之外，還可以檢測出所有奇數(shù)個錯誤和絕大多數(shù)

11、偶數(shù)個錯誤（互相補償?shù)呐紨?shù)個錯誤除外）。三、校驗和CS（Check Sum）： 從這種縱向奇偶校驗方法我們可以得到啟發(fā)，我們可以采用校驗和的辦法實現(xiàn)縱向校驗。 把m個長度位 l 的數(shù)據(jù)組作為二進制數(shù)按模 L 相加，形成校驗和，把校驗和附在 m 個數(shù)據(jù)位后一起發(fā)送，通常取 L = 2l 。在接收端，將收到的前面 m 個數(shù)據(jù)以同樣的方式按模 L 相加，得到接收端計算的校驗和，并且與收到的校驗和比較，如果二者一致，則說明沒有錯誤，如果不一致，則表明傳送過程中有錯誤。8電氣工程學(xué)院山東大學(xué)研究生課程例：1 0 1 0 1 1 0 11 0 0 1 1 1 0 00 1 0 1 0 0 1 10 0 1

12、 0 1 0 0 11 0 0 1 0 1 0 127 26 25 24 23 21 2012341校驗和28與碼元位對應(yīng)的權(quán)數(shù)據(jù)組 表中；再與相加，得1，再與 相加得1，由于是模2加，紅色的數(shù)位溢出丟棄。 1 0 0 1 1 1 0 0） 0 1 0 1 0 0 1 1 1 1 1 0 1 1 1 1） 0 0 1 0 1 0 0 1 1 0 0 0 1 1 0 0 0） 1 0 0 1 0 1 0 1 1 1 0 1 0 1 1 0 1 表中每個信息組長度l 8，共有4組，以L = 2l 28為模（也就是28 0），溢出位舍棄。9電氣工程學(xué)院山東大學(xué)研究生課程表21 RS-232C 25針

13、連接器引腳信號分配4.3 循環(huán)碼 循環(huán)碼是線性分組碼的一個重要子集，它由嚴(yán)格的代數(shù)結(jié)構(gòu)，用近世代數(shù)方法可以找出許多編碼效率高、檢錯糾錯能力強的循環(huán)碼。由于它的編碼和檢錯方法比較簡單易行，而且找到了許多有效的糾錯方法，因此，循環(huán)碼得到了廣泛的應(yīng)用。一、循環(huán)碼的定義： 一個（n，k）循環(huán)碼是碼長為 n，有 k 位數(shù)據(jù)位的線性分組碼，它的特點是其任意一個碼字 C 的每次循環(huán)移位，得到的是另一個碼字。設(shè)： C = | cn-1，cn-2，c1，c0 | 是循環(huán)碼的一個碼字，則 C(1) = | cn-2 ，cn-3，c0 ，cn-1 | C(2) = | cn-3 ，cn-4，cn-1 ， cn-2

14、| C(i) = | cn-I-1 ，cn-I-2， c0 ，cn-1 ， ， cn-I+1 ， cn-i | C(n-1) = | c0 ，cn-1，c2 ，c1 |也都是該循環(huán)碼的碼字。10電氣工程學(xué)院山東大學(xué)研究生課程例如：所示的線性分組碼就是一個（7，3）循環(huán)碼，由3位數(shù)據(jù)位、4位監(jiān)督碼元組成。二、碼組的多項式表示： 為了便于分析，常用碼多項式來描述碼元序列，如一個（n，k）線性分組碼用碼元序列 C 描述時為： C = | cn-1，cn-2，c1，c0 | 相應(yīng)地用碼多項式表示時，則可以表示為： 式中 x 的冪次對應(yīng)于各碼元的位置，系數(shù)則對應(yīng)于各碼元的取值，在二元制中系數(shù) Ci 取值

15、為“0”或“1”。碼多項式 C （x） 與碼元序列相對應(yīng)。（n，k）線性分組碼的碼長為 n ，所以其碼多項式 C （x） 的最高次數(shù)不超過 n1。數(shù) 據(jù)碼 字?jǐn)?shù) 據(jù)碼 字0 0 00 0 0 0 0 0 0 1 0 01 0 0 1 1 1 00 0 10 0 1 1 1 0 11 0 11 0 1 0 0 1 10 1 00 1 0 0 1 1 11 1 01 1 0 1 0 0 10 1 10 1 1 1 0 1 01 1 11 1 1 0 1 0 011電氣工程學(xué)院山東大學(xué)研究生課程例：有一碼元序列C，寫成多項式形式就是： 兩個多項式之間的運算是其對應(yīng)項系數(shù)的運算，在二進制中系數(shù)只取0和

16、1，系數(shù)之間按照模 2 運算。 如果給碼多項式乘以 x，則相當(dāng)于將碼序列左移一位。例如將上式乘以 x 以后，就變?yōu)椋?而與 C（x） 對應(yīng)的碼元序列為C，恰好是原碼元序列C左移一位。同理，對于碼多項式乘以 x i ，相當(dāng)于將相應(yīng)的碼元序列 C 左移 i 位。 （n，k）線性分組碼的碼多項式 C（x） 在乘以 x i 后， x i .C（x）的最高冪次可能超過 n1。在（n，k）線性分組循環(huán)碼多項式運算中，以 xn1 為模，碼多項式的最高冪次不會超過 n1，給碼多項式C（x）乘以 x i 時就可以實現(xiàn)對應(yīng)碼元序列的 i 位循環(huán)左移。12電氣工程學(xué)院山東大學(xué)研究生課程三、按模運算：1、整數(shù)按模運算

17、 一個整數(shù) m 被非零整數(shù) n 除后，得到商數(shù) q 和余數(shù) r。r 是小于 n 的一個整數(shù): mq nr （r n） 按模 n 運算時將小于 n 的整數(shù)0，1，2，n1，共 n 個，稱為按模 n 的剩余類。若只關(guān)心被 n 除后所得的余數(shù)，則所有整數(shù)可按 n 劃分成 n 個剩余類。例如 n5時有5個剩余類，分別表示|0|，|1|，|2|，|3|，|4|。任一整數(shù)，譬如8，被5 整除后余數(shù)為3，故按模5運算時8屬于剩余類|3|，表示成83（模5）。符號“”表示左右兩邊的余數(shù)相同（同余）。按模5運算時所有整數(shù)分屬下列5個剩余類： |0| |1| |2| |3| |4| 0 1 2 3 4 5 6 7

18、 8 9 10 11 12 13 14 按模 n 運算時整數(shù)之間的相加、相乘等運算可按常規(guī)進行，但所得結(jié)果應(yīng)按模 n 處理。例如按模5運算時，4312 2（模5）。 13電氣工程學(xué)院山東大學(xué)研究生課程2、多項式按模運算 與整數(shù)按模運算類似，對于任意多項式F（x），可以用一個次數(shù)為 n 的多項式N（x）去除，得到商式Q（x）和余式R（x）， R（x）的次數(shù)小于 n ，即： F（x）= Q（x） N（x）+ R（x）表示為： F（x） R（x） 模N（x）上式符號“”表示左右兩邊的余式相同。這稱為模 N（x）運算，在二進制情況下，多項式的系數(shù)只取0或者1。碼多項式運算時，其系數(shù)按模2運算。任意多項

19、式F（x）在按模 N（x）的運算下，其結(jié)果是F（x）除以 N（x）所得的余式。例：F（x）=x5，N（x）=x4+x3+x2+1，則有： x5 x2+x+1 （模 x4+x3+x2+1） （ x4+x3+x2+1）x5x 1x5+x4+x3+xx4+x3+ xx4+x3+x2+ 1x2+x+1注意：所有運算均為模2運算14電氣工程學(xué)院山東大學(xué)研究生課程 有時如果已經(jīng)約定了N（x），模N（x）可以省略不寫，只寫出同余符號“”，對于上例中，如果已經(jīng)約定N(x)=x4+x3+x2+1，則可以寫為： x5 x2 + x + 1 若用 xn+1 去除任意多項式F（x），所得余式次數(shù)小于n。在二進制中多項

20、式系數(shù)只取0或者1，因而這種 余式共可以有 2n 種，構(gòu)成 2n個剩余類，稱為按模 xn+1 的剩余類。四、循環(huán)碼的按模xn1 運算 給碼多項式C（x）乘以x，相當(dāng)于將原來的碼元序列C左移一位。對于循環(huán)碼來說：設(shè)（n，k）線性分組循環(huán)碼的碼多項式C（x）為：碼長為n，C（x）的最高次數(shù)不超過n1。對C（x）乘以x后得：在（n，k）線性分組碼中，碼多項式按模 xn1運算， xn1 0，xn 1，故上式可以寫為：15電氣工程學(xué)院山東大學(xué)研究生課程（模 xn +1） 可見在模 xn+1運算下，碼多項式 所對應(yīng)的的是將原來的碼元序列C循環(huán)左移一位。（n，k）線性分組循環(huán)碼按模 xn+1運算， xn+1

21、 0， xn 1 x0, x0位與xn等效，其物理意義可以看作時移位時高端溢出的碼元被返送到低端，首尾相接，從而形成了循環(huán)移位。 同理，給碼多項式C（x）乘以 xi 時，設(shè)：則若以 xn1為模， xn 1，上式可寫為：（模 xn +1）16電氣工程學(xué)院山東大學(xué)研究生課程 可見在按模 xn+1 的運算下，碼多項式 所對應(yīng)的是將原來的碼元序列 C 循環(huán)左移 i 位。 也可以寫成如下形式：式中：17電氣工程學(xué)院山東大學(xué)研究生課程按模 xn1運算時，就可以得到：（模 xn1） 因而對于（n，k）線性分組循環(huán)碼，若C（x）是一個碼字，則在按模 xn1運算下，就是以xn1除多項式 所得的余式C（i）（x）

22、也是一個碼字，它對應(yīng)于將原來的碼字循環(huán)左移 i 位。余式是次數(shù)小于 n 的碼多項式。每一個碼長為 n 的循環(huán)碼必屬于以 xn1為模的某一剩余類。五、循環(huán)碼的生成多項式1、生成多項式的定義： 一般來說，生成多項式 g（x）是（n，k）循環(huán)碼中最低次非零碼多項式，其次數(shù)為nk?？砂?g（x）寫成：式中：gi 為生成多項式的系數(shù)，為0或者1。 g(x)的首項系數(shù)為1，末項系數(shù)也必須為1。首項系數(shù)為1是顯而易見的，否則其次數(shù)就不是nk了，而若末項系數(shù)為0的話，則 g（x）就變成了18電氣工程學(xué)院山東大學(xué)研究生課程當(dāng)g（x）循環(huán)移位 n1次后得到的碼多項式為：其次數(shù)低于nk，定義中“碼字中非零碼多項式的

23、最低次數(shù)為nk”矛盾了。所以首項和末項系數(shù)都必須是1。2、生成多項式g（x）的性質(zhì)（1）在一個（n，k）循環(huán)碼中，有且僅有一個（nk）次的生成多項式 g（x），該（n，k）循環(huán)碼中的每一個碼多項式 C（x）都是生成多項式的倍式，并且每個為 g（x）倍式的、次數(shù)不大于（n1）次的多項式，一定是一個碼多項式。設(shè)： g（x）是（n，k）循環(huán)碼的生成多項式。因為 g（x）是循環(huán)碼的一個碼字，所以x g（x）， x2 g（x），xk-i g（x）也都是碼字。設(shè) mi 為信息位，i0，1，2，k1， mi 取值0或1，則 g（x）的任意次移位組成的C（x）為：這里C（x）仍是一個碼字。19電氣工程學(xué)院山東

24、大學(xué)研究生課程把信息組（mk-1，mk-2， m0）寫成信息多項式m（x）根據(jù)以上兩式，得：C（x）m（x）g（x）這說明：任一循環(huán)碼的碼多項式都是生成多項式的倍式。 由這一性質(zhì)可知：如果用信息多項式 代表 k 位信息序列，（n，k） 循環(huán)碼中的每個碼多項式C（x）都可以表示成： 對信息序列的編碼，相當(dāng)于用信息多項式m（x）乘以生成多項式g（x）。所以生成多項式g（x）確定了由 2k 個信息序列生成的 2k 個碼字的編碼。 g（x）的次數(shù)（nk）等于碼字中校驗碼元的個數(shù)。（2）（n，k）循環(huán)碼的生成多項式g（x）是（xn1）的一個因式。即 xn1g（x）h（x）20電氣工程學(xué)院山東大學(xué)研究生課

25、程式中： 正是g（x）左移 k 次的結(jié)果，它必為一個碼字，而且是g（x）的倍式。可以寫成：Ck（x）g（x）。所以：得：這說明（n，k）循環(huán)碼的生成多項式是xn1的因式。據(jù)此我們可以知道：為得到（n，k）循環(huán)碼的生成多項式，可以先對xn1進行因式分解，然后取nk次因式，就得到生成多項式g（x）（3）若g（x）是一個（nk）次多項式，且是xn1的因式，則g（x）生成一個（ n，k ）循環(huán)碼。將生成多項式g（x）乘以xk，得：21電氣工程學(xué)院山東大學(xué)研究生課程根據(jù)生成多項式的性質(zhì)，我們可以知道：（1）要生成一個（n，k）循環(huán)碼，必須首先找到生成多項式g（x），它的次數(shù)是（nk）次；（2）尋找生成多

26、項式的方法 根據(jù)想要生成一個碼長為 n 位，信息位為 k 位的（n，k）循環(huán)碼，首先將因式xn1進行因式分解，式中的 n 是碼長的取值；在以上分解時，找出一個次數(shù)為（nk）次的因式；最后以這個（nk）次的因式為生成多項式，用它分別乘以2k 個不同的信息序列，便可以得到（n，k）循環(huán)碼的2k 個碼字。22電氣工程學(xué)院山東大學(xué)研究生課程例1：有一（7，3）循環(huán)碼如表所示: 就是該（7，3）循環(huán)碼的生成多項式。信息組碼 字信息組碼字0 0 0 0 0 0 0 0 0 01 0 01 0 0 1 1 1 00 0 1 0 0 1 1 1 0 11 0 11 0 1 0 0 1 10 1 00 1 0

27、0 1 1 11 1 01 1 0 1 0 0 10 1 10 1 1 1 0 1 01 1 11 1 1 0 1 0 0對于（7，3）循環(huán)碼來講：n7，k3，則可以對x71進行因式分解： x71（x+1）（x3x21）（x3x1）取其nk734次因式，得： g1（x）（x+1）（x3+x2+1）x4x2x1，由于該碼字對應(yīng)的碼元序列為：0 0 1 0 1 1 1不在上述碼組中，因此，得到的g1（x）不是所求的生成多項式g（x）而： g2（x）（x1）（x3x1）x4x3x21 才是我們要找的生成多項式g（x） 根據(jù)生成多項式的定義，取其前面k1312位都是0的碼字（最低次的非零碼），寫成碼多

28、項式就是：23電氣工程學(xué)院山東大學(xué)研究生課程例2：如何形成一個（7，4）循環(huán)碼：首先，分解x71，找出nk743次的因式。 x71（x4x2x1）(x3x1）生成多項式為：g（x）=x3x1。對信息多項式 ，取m3 m2 m1 m0為十六種不同二進制序列，分別完成運算：運算結(jié)果即是（7，4）循環(huán)碼的十六個碼字（見下表）24電氣工程學(xué)院山東大學(xué)研究生課程由g（x）=x3x1生成的（7，4）循環(huán)碼信息序列碼 多 項 式C（x）m（x）g（x）碼 字m3 m2 m1 m0c6 c5 c4 c3 c2 c1 c00 0 0 00（ x3x1 ）00 0 0 0 0 0 00 0 0 11（ x3x1

29、） x3x1 0 0 0 1 0 1 10 0 1 0 x（ x3x1 ）=x4x2x0 0 1 0 1 1 00 0 1 1（x1）（x3x1）=x4x3x210 0 1 1 1 0 10 1 0 0 x2（ x3x1 ）x5x3x20 1 0 1 1 0 00 1 0 1（x21）（ x3x1 ）x5x2x10 1 0 0 1 1 1 0 1 1 0（x2x）（ x3x1 ）x5x4x3x0 1 1 1 0 1 00 1 1 1（x2x1）（ x3x1 ）x5x410 1 1 0 0 0 11 0 0 0 x3（ x3x1 ）x6x4x31 0 1 1 0 0 01 0 0 1（x31）（

30、 x3x1 ）x6x4x11 0 1 0 0 1 11 0 1 0（x3x）（ x3x1 ）x6x3x2x1 0 0 1 1 1 01 0 1 1（x3x1）（ x3x1 ）x6x211 0 0 0 1 0 11 1 0 0（x3x2）（ x3x1 ）x6x5x4x21 1 1 0 1 0 01 1 0 1（x3x21）（ x3x1 ）x6x5x4x3x2x11 1 1 1 1 1 11 1 1 0（x3x2x）（ x3x1 ）x6x5x1 1 0 0 0 1 01 1 1 1 （x3x2x1）（ x3x1 ）x6x5x311 1 0 1 0 0 125電氣工程學(xué)院山東大學(xué)研究生課程六、循環(huán)碼

31、的抗干擾能力1、伴隨式計算及糾錯假設(shè)發(fā)送端發(fā)送的碼字多項式是：而接收端收到的碼字多項式是：如果用接收到的碼多項式R（x）除以生成多項式g（x）時，如果得商式為P（x），余式為s（x），則有： 多項式s（x）稱為接收碼字R（x）的伴隨式。如果伴隨式s（x）為零，表明接收碼字多項式R（x）是生成多項式g（x）的倍式，譯碼判斷時認(rèn)為接收碼字就是發(fā)送端發(fā)來的碼字C（x）（接收沒有錯誤）。若伴隨式不為零，則認(rèn)為收到的碼字中有錯誤！ s（x）的次數(shù)必然不大于（nk1），所以伴隨式是 nk 位的序列，它最多可以取2nk種不同的取值。 如果把發(fā)送碼字在信道種受干擾的錯誤圖樣用多項式表示為：26電氣工程學(xué)院山東

32、大學(xué)研究生課程則接收到的碼字為：R（x）C（x）E（x）計算伴隨式時需要完成的除法運算是：R（x）/ g（x）C（x）E（x） / g（x）C（x）/ g（x）E（x）/ g（x）注意：上式中，發(fā)送碼字C（x）必為g（x）的倍式，如果C（x）除以g（x）的商式為q（x）， E（x）除以 g（x）的商式是p（x），余式是s（x），得：R（x）q（x）g（x）+ p（x） g（x） s（x）Q（x） g（x） s（x）其中： Q（x） q（x） p（x） 對比該兩式可以看出：接收碼字R（x）的伴隨式s（x）等于錯誤圖樣E（x）除以生成多項式g（x）所得的余式s（x）。可見伴隨式中包含有疊加在發(fā)送碼

33、字上的錯誤圖樣的信息，所以不僅可以利用伴隨式進行檢錯，還可以用伴隨式完成一定范圍內(nèi)的糾錯。 按照最小碼距 dmin和碼的檢錯、糾錯能力之間的關(guān)系，伴隨式和錯誤圖樣之間的關(guān)系為：27電氣工程學(xué)院山東大學(xué)研究生課程1、當(dāng)接收碼字R（x）中的錯誤碼元數(shù)為 t 位，并且滿足 t （ dmin-1）/2時，對于任何一種重量為 t 的錯誤圖樣，唯一地對應(yīng)一個伴隨式。從而可以根據(jù)錯誤圖樣與伴隨式之間的對應(yīng)關(guān)系，由伴隨式確定錯誤圖樣并實現(xiàn)糾錯；即：用伴隨式可以檢出并糾正 t 位錯誤，條件是t （ dmin-1）/2。2、當(dāng)接收碼字中的錯誤碼元數(shù)為 l ，且滿足（ dmin-1）/2 l dmin-1時，可以出

34、現(xiàn)多個錯誤圖樣對應(yīng)同一個伴隨式的情況，這時不能由伴隨式確定唯一的一個錯誤圖樣，因此不能完成糾錯，但根據(jù)伴隨式不為零可以實現(xiàn)檢錯；即：用伴隨式可以檢出 l 位錯誤，條件是（ dmin-1）/2 nk 時，檢測不出的突發(fā)錯誤占同樣長度的可能的突發(fā)錯誤總數(shù)的百分比為： 2（nk） 當(dāng)b1 nk 2（nk1） 當(dāng)b1 nk 在突發(fā)錯誤E（x）xiB（x）中， B（x）是 b1 次多項式。由于突發(fā)錯誤的首尾兩位必有錯，故B（x）的x0項及xb1項的系數(shù)必為1，可以知道B（x）總共可取2b2個不同的多項式，即：突發(fā)長度為 b 時，可能的突發(fā)錯誤總數(shù)為2b2個。33電氣工程學(xué)院山東大學(xué)研究生課程只有當(dāng)B（x

35、）能被g（x）除盡時， E（x）的錯誤才檢測不出來，這時滿足： B（x）q（x）g（x）其中q（x）為b1（ nk ），則q（x）為零次多項式，即q（x）1。這時存在唯一的不可檢測的錯誤圖樣B（x） g（x）。在這種情況下，不可檢測的突發(fā)錯誤數(shù)為1，可能的突發(fā)錯誤總數(shù)為2b2 2nk1，它們的比為：若b1 nk ， q（x）共可能有2b2（nk）個不同的多項式，即不可檢測的錯誤圖樣總共可以有2b2（nk）個，它與可能的突發(fā)錯誤總數(shù)之比為： 可見，由nk 次多項式g（x）生成的循環(huán)碼，不僅能檢測出所有長度不大于nk 的突發(fā)錯誤，而且可以檢測出絕大部分更長的突發(fā)錯誤。同理，還可以分析出更多的檢錯情

36、況。34電氣工程學(xué)院山東大學(xué)研究生課程七、循環(huán)冗余校驗碼（CRC） 循環(huán)冗余校驗碼是循環(huán)碼的一種，是最常用的一種差錯控制校驗方式，它具有較強的檢錯能力和一定的糾錯能力，編碼和解碼實現(xiàn)起來也比較簡單，在串行通信、磁盤文件讀寫、文件的壓縮/解壓、多媒體技術(shù)、網(wǎng)絡(luò)技術(shù)、密碼技術(shù)等方面，得到較為普遍的應(yīng)用。 CRC Cyclic Redundancy Check 循環(huán)冗余校驗1、CRC校驗碼的檢錯方法：CRC碼由兩部分組成，其中，左面有 k 位信息位，右面是 r 位校驗位，字長是 n 位，n = k + r。如下圖所示： 1 2 3 k 1 r信息位（k 位）校驗位（r 位）CRC碼（kr 位）CRC

37、碼格式35電氣工程學(xué)院山東大學(xué)研究生課程 CRC校驗是將要發(fā)送的數(shù)據(jù)多項式m（x）在發(fā)送端除以一個預(yù)先約定的生成多項式 g（x），求得一個余數(shù)多項式 r（x），將余數(shù)多項式加到數(shù)據(jù)多項式之后，形成一個發(fā)送多項式 f（x）發(fā)送到接收端。在接受端用同樣的生成多項式g（x）去除接收到的多項式 f（x），得到計算余數(shù)多項式，如果計算余數(shù)多項式與接收余數(shù)多項式相同，則表示傳輸無差錯；如果計算余數(shù)多項式不等于接收余數(shù)多項式，則表示傳輸有錯誤，從而實現(xiàn)了檢錯。2、CRC校驗碼的編碼方法首先，將待發(fā)送的 k 位信息位寫為多項式形式C（x）Ck-1xk-1Ck-2xk-2Cixi+C1xC0 為將信息位左移 r

38、 位，可以表示為：C（x）xr 這樣在信息組的右邊就空出了 r 位，以便拼接 r 位校驗位。CRC碼是用多項式C（x）xr 除以生成多項式 g（x）所得的余數(shù)作為校驗位的，為了得到 r 位校驗位（余數(shù)），生成多項式g（x）必須是 r1位。設(shè)所得的余數(shù)表達式為 r（x），商為q（x），將余數(shù)拼接在信息組左移空出的 r 位 上，就構(gòu)成了這個有效信息的CRC碼。因此，這個CRC碼可以用多項式表達為： 36電氣工程學(xué)院山東大學(xué)研究生課程C（x）xr r（x） q（x）g（x）r（x）r（x） q（x）g（x） r（x） r（x） q（x）g（x）因此，所得的CRC碼是可以被生成多項式除盡的。例：對4位

39、有效信息組（1100）求CRC碼，選擇生成多項式為（1011），即： C（x）x3x2 1100 C（x）xr x6x5 g（x）x3x1 1011x3+x+1 x6 + x5x3+x2+xx6 + x4 + x3 x5 + x4 + x3 x5 + x3 + x2 x4 + x2 x4 + x2 + x x這是一個（7，4）循環(huán)碼的例子。37電氣工程學(xué)院山東大學(xué)研究生課程3、CRC的譯碼與糾錯 將收到的循環(huán)校驗碼用約定的生成多項式 g（x）去除，如果碼字正確則余數(shù)應(yīng)為0，如果有某一位出錯，則余數(shù)不為0，不同位數(shù)出錯則余數(shù)不同。通過上例求出其出錯模式如下表所示。更換不同的待測碼字可以證明：余數(shù)

40、與出錯位的對應(yīng)關(guān)系是不變的，只與碼制和生成多項式有關(guān)。因此該表可以作為（7，4）碼的判別依據(jù)。對于其他碼制或選用其他生成多項式，出錯模式將會發(fā)生變化。（7，4）循環(huán)碼的出錯模式【生成多項式 g（x）1011】38電氣工程學(xué)院山東大學(xué)研究生課程 如果循環(huán)碼有一位出錯，用 g（x）作模 2 除將得到一個不為 0 的余數(shù)。如果對余數(shù)補一個 0 繼續(xù)除下去，我們將發(fā)現(xiàn)一個現(xiàn)象：各次余數(shù)將按照上表順序循環(huán)。如：第6位出錯，余數(shù)是 001，補 0 再除，第二次余數(shù)為 010，以后依次為100，011，.，反復(fù)循環(huán)，這是 CRC 校驗碼的一個有價值的特點。如果我們在求出余數(shù)不為 0 后，一邊對余數(shù)補 0 繼

41、續(xù)做模2除，同時讓被檢測的校驗碼字循環(huán)左移，上表說明，當(dāng)出現(xiàn)余數(shù)（101）時，出錯位也移到 C0 的位置?？梢酝ㄟ^異或操作將它糾正后在下一次移位時送回 C6 。繼續(xù)移滿一個循環(huán)（對于7，4碼共需移七次），就得到了一個糾正后的碼字。通過這種方式，可以實現(xiàn) CRC 碼的糾錯。 也就是說，當(dāng)信息傳輸出現(xiàn)錯誤時，循環(huán)冗余校驗碼被生成多項式整除所得到的余數(shù)與出錯位有一一對應(yīng)的關(guān)系，據(jù)此，可以確定出錯的位置，從而實現(xiàn)糾錯。39電氣工程學(xué)院山東大學(xué)研究生課程4、循環(huán)冗余校驗碼的檢錯能力： 可以證明，循環(huán)冗余校驗碼可以：（1）能檢查出全部單個錯誤；（2）能檢查出全部離散的二位錯誤；（3）能檢查出全部奇數(shù)個錯誤；（4）能檢查出全部長度小于或等于 r 位的突發(fā)錯誤；（5）能以1（1/2）r-1的概率檢查出長度為（r+1）位的突發(fā)錯誤。 例如，如果 r 16，則該CRC校