抗干擾編碼技術(shù)

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

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

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

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

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

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

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

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

9、一列各補(bǔ)充一位奇偶校驗(yàn)碼，這樣由行校驗(yàn)位r1(j+1)、r2(j+1)、 r(i+1)(j+1)和列校驗(yàn)位r(i+1)1、r(i+1)2、r(i+1)j 和數(shù)據(jù)位便構(gòu)同時(shí)具有縱向奇偶校驗(yàn)位和橫向奇偶校驗(yàn)位的縱橫奇偶校驗(yàn)碼。 在實(shí)際的操作中，我們可以把要傳送的每一個(gè)字節(jié)做為一行，而把每個(gè)字節(jié)中的對(duì)應(yīng)位做為一列，實(shí)現(xiàn)縱橫奇偶校驗(yàn)，對(duì)于每一列的校驗(yàn)，可以采用每傳送一個(gè)字節(jié)，做一次異或操作（偶校驗(yàn)）的辦法來(lái)實(shí)現(xiàn)。（奇校驗(yàn) ？）例：如有三個(gè)字節(jié)：第一個(gè)字節(jié)10110101第二個(gè)字節(jié)00011011第三個(gè)字節(jié)11100001縱向校驗(yàn)碼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é)研究生課程 這種縱橫奇偶校驗(yàn)方式具有較強(qiáng)的檢錯(cuò)能力，當(dāng)碼字中出現(xiàn)一位、兩位或三位錯(cuò)誤時(shí)，不管錯(cuò)誤位在上圖中如何分布，接收端通過(guò)譯碼都會(huì)發(fā)現(xiàn)橫向奇偶校驗(yàn)出錯(cuò)或縱向奇偶校驗(yàn)出錯(cuò)、或者橫向、縱向奇偶校驗(yàn)同時(shí)出錯(cuò)，從而實(shí)現(xiàn)檢錯(cuò)。如果碼字中的錯(cuò)誤位只有一位，這時(shí)同時(shí)會(huì)出現(xiàn)某一行和某一列的奇偶校驗(yàn)出錯(cuò)，則根據(jù)出錯(cuò)的行號(hào)和列號(hào)，便可以確定錯(cuò)誤位的位置，實(shí)現(xiàn)糾錯(cuò)。因此，這種碼可以糾正一位錯(cuò)誤、檢出三位以下的錯(cuò)誤，是所謂的“糾一檢三碼”。除此之外，還可以檢測(cè)出所有奇數(shù)個(gè)錯(cuò)誤和絕大多數(shù)

11、偶數(shù)個(gè)錯(cuò)誤（互相補(bǔ)償?shù)呐紨?shù)個(gè)錯(cuò)誤除外）。三、校驗(yàn)和CS（Check Sum）： 從這種縱向奇偶校驗(yàn)方法我們可以得到啟發(fā)，我們可以采用校驗(yàn)和的辦法實(shí)現(xiàn)縱向校驗(yàn)。 把m個(gè)長(zhǎng)度位 l 的數(shù)據(jù)組作為二進(jìn)制數(shù)按模 L 相加，形成校驗(yàn)和，把校驗(yàn)和附在 m 個(gè)數(shù)據(jù)位后一起發(fā)送，通常取 L = 2l 。在接收端，將收到的前面 m 個(gè)數(shù)據(jù)以同樣的方式按模 L 相加，得到接收端計(jì)算的校驗(yàn)和，并且與收到的校驗(yàn)和比較，如果二者一致，則說(shuō)明沒有錯(cuò)誤，如果不一致，則表明傳送過(guò)程中有錯(cuò)誤。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校驗(yàn)和28與碼元位對(duì)應(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 表中每個(gè)信息組長(zhǎng)度l 8，共有4組，以L = 2l 28為模（也就是28 0），溢出位舍棄。9電氣工程學(xué)院山東大學(xué)研究生課程表21 RS-232C 25針

13、連接器引腳信號(hào)分配4.3 循環(huán)碼 循環(huán)碼是線性分組碼的一個(gè)重要子集，它由嚴(yán)格的代數(shù)結(jié)構(gòu)，用近世代數(shù)方法可以找出許多編碼效率高、檢錯(cuò)糾錯(cuò)能力強(qiáng)的循環(huán)碼。由于它的編碼和檢錯(cuò)方法比較簡(jiǎn)單易行，而且找到了許多有效的糾錯(cuò)方法，因此，循環(huán)碼得到了廣泛的應(yīng)用。一、循環(huán)碼的定義： 一個(gè)（n，k）循環(huán)碼是碼長(zhǎng)為 n，有 k 位數(shù)據(jù)位的線性分組碼，它的特點(diǎn)是其任意一個(gè)碼字 C 的每次循環(huán)移位，得到的是另一個(gè)碼字。設(shè)： C = | cn-1，cn-2，c1，c0 | 是循環(huán)碼的一個(gè)碼字，則 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é)研究生課程例如：所示的線性分組碼就是一個(gè)（7，3）循環(huán)碼，由3位數(shù)據(jù)位、4位監(jiān)督碼元組成。二、碼組的多項(xiàng)式表示： 為了便于分析，常用碼多項(xiàng)式來(lái)描述碼元序列，如一個(gè)（n，k）線性分組碼用碼元序列 C 描述時(shí)為： C = | cn-1，cn-2，c1，c0 | 相應(yīng)地用碼多項(xiàng)式表示時(shí)，則可以表示為： 式中 x 的冪次對(duì)應(yīng)于各碼元的位置，系數(shù)則對(duì)應(yīng)于各碼元的取值，在二元制中系數(shù) Ci 取值

15、為“0”或“1”。碼多項(xiàng)式 C （x） 與碼元序列相對(duì)應(yīng)。（n，k）線性分組碼的碼長(zhǎng)為 n ，所以其碼多項(xiàng)式 C （x） 的最高次數(shù)不超過(guò) 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，寫成多項(xiàng)式形式就是： 兩個(gè)多項(xiàng)式之間的運(yùn)算是其對(duì)應(yīng)項(xiàng)系數(shù)的運(yùn)算，在二進(jìn)制中系數(shù)只取0和

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

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

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

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

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

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

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

23、最低次數(shù)為nk”矛盾了。所以首項(xiàng)和末項(xiàng)系數(shù)都必須是1。2、生成多項(xiàng)式g（x）的性質(zhì)（1）在一個(gè)（n，k）循環(huán)碼中，有且僅有一個(gè)（nk）次的生成多項(xiàng)式 g（x），該（n，k）循環(huán)碼中的每一個(gè)碼多項(xiàng)式 C（x）都是生成多項(xiàng)式的倍式，并且每個(gè)為 g（x）倍式的、次數(shù)不大于（n1）次的多項(xiàng)式，一定是一個(gè)碼多項(xiàng)式。設(shè)： g（x）是（n，k）循環(huán)碼的生成多項(xiàng)式。因?yàn)?g（x）是循環(huán)碼的一個(gè)碼字，所以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）仍是一個(gè)碼字。19電氣工程學(xué)院山東

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

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

26、項(xiàng)式的方法 根據(jù)想要生成一個(gè)碼長(zhǎng)為 n 位，信息位為 k 位的（n，k）循環(huán)碼，首先將因式xn1進(jìn)行因式分解，式中的 n 是碼長(zhǎng)的取值；在以上分解時(shí)，找出一個(gè)次數(shù)為（nk）次的因式；最后以這個(gè)（nk）次的因式為生成多項(xiàng)式，用它分別乘以2k 個(gè)不同的信息序列，便可以得到（n，k）循環(huán)碼的2k 個(gè)碼字。22電氣工程學(xué)院山東大學(xué)研究生課程例1：有一（7，3）循環(huán)碼如表所示: 就是該（7，3）循環(huán)碼的生成多項(xiàng)式。信息組碼 字信息組碼字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對(duì)于（7，3）循環(huán)碼來(lái)講：n7，k3，則可以對(duì)x71進(jìn)行因式分解： x71（x+1）（x3x21）（x3x1）取其nk734次因式，得： g1（x）（x+1）（x3+x2+1）x4x2x1，由于該碼字對(duì)應(yīng)的碼元序列為：0 0 1 0 1 1 1不在上述碼組中，因此，得到的g1（x）不是所求的生成多項(xiàng)式g（x）而： g2（x）（x1）（x3x1）x4x3x21 才是我們要找的生成多項(xiàng)式g（x） 根據(jù)生成多項(xiàng)式的定義，取其前面k1312位都是0的碼字（最低次的非零碼），寫成碼多

28、項(xiàng)式就是：23電氣工程學(xué)院山東大學(xué)研究生課程例2：如何形成一個(gè)（7，4）循環(huán)碼：首先，分解x71，找出nk743次的因式。 x71（x4x2x1）(x3x1）生成多項(xiàng)式為：g（x）=x3x1。對(duì)信息多項(xiàng)式 ，取m3 m2 m1 m0為十六種不同二進(jìn)制序列，分別完成運(yùn)算：運(yùn)算結(jié)果即是（7，4）循環(huán)碼的十六個(gè)碼字（見下表）24電氣工程學(xué)院山東大學(xué)研究生課程由g（x）=x3x1生成的（7，4）循環(huán)碼信息序列碼 多 項(xiàng) 式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、伴隨式計(jì)算及糾錯(cuò)假設(shè)發(fā)送端發(fā)送的碼字多項(xiàng)式是：而接收端收到的碼字多項(xiàng)式是：如果用接收到的碼多項(xiàng)式R（x）除以生成多項(xiàng)式g（x）時(shí)，如果得商式為P（x），余式為s（x），則有： 多項(xiàng)式s（x）稱為接收碼字R（x）的伴隨式。如果伴隨式s（x）為零，表明接收碼字多項(xiàng)式R（x）是生成多項(xiàng)式g（x）的倍式，譯碼判斷時(shí)認(rèn)為接收碼字就是發(fā)送端發(fā)來(lái)的碼字C（x）（接收沒有錯(cuò)誤）。若伴隨式不為零，則認(rèn)為收到的碼字中有錯(cuò)誤！ s（x）的次數(shù)必然不大于（nk1），所以伴隨式是 nk 位的序列，它最多可以取2nk種不同的取值。 如果把發(fā)送碼字在信道種受干擾的錯(cuò)誤圖樣用多項(xiàng)式表示為：26電氣工程學(xué)院山東

32、大學(xué)研究生課程則接收到的碼字為：R（x）C（x）E（x）計(jì)算伴隨式時(shí)需要完成的除法運(yùn)算是：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） 對(duì)比該兩式可以看出：接收碼字R（x）的伴隨式s（x）等于錯(cuò)誤圖樣E（x）除以生成多項(xiàng)式g（x）所得的余式s（x）?？梢姲殡S式中包含有疊加在發(fā)送碼

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

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

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

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

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

38、 位，可以表示為：C（x）xr 這樣在信息組的右邊就空出了 r 位，以便拼接 r 位校驗(yàn)位。CRC碼是用多項(xiàng)式C（x）xr 除以生成多項(xiàng)式 g（x）所得的余數(shù)作為校驗(yàn)位的，為了得到 r 位校驗(yàn)位（余數(shù)），生成多項(xiàng)式g（x）必須是 r1位。設(shè)所得的余數(shù)表達(dá)式為 r（x），商為q（x），將余數(shù)拼接在信息組左移空出的 r 位 上，就構(gòu)成了這個(gè)有效信息的CRC碼。因此，這個(gè)CRC碼可以用多項(xiàng)式表達(dá)為： 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碼是可以被生成多項(xiàng)式除盡的。例：對(duì)4位

39、有效信息組（1100）求CRC碼，選擇生成多項(xiàng)式為（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這是一個(gè)（7，4）循環(huán)碼的例子。37電氣工程學(xué)院山東大學(xué)研究生課程3、CRC的譯碼與糾錯(cuò) 將收到的循環(huán)校驗(yàn)碼用約定的生成多項(xiàng)式 g（x）去除，如果碼字正確則余數(shù)應(yīng)為0，如果有某一位出錯(cuò)，則余數(shù)不為0，不同位數(shù)出錯(cuò)則余數(shù)不同。通過(guò)上例求出其出錯(cuò)模式如下表所示。更換不同的待測(cè)碼字可以證明：余數(shù)

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

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