第7章-物聯(lián)網(wǎng)通信技術(shù)(曾憲武)LXX2014.7

1、第7章差錯控制技術(shù)1 1第7章差錯控制技術(shù)7.1差錯控制技術(shù)概述差錯控制技術(shù)概述7.2差錯控制方法差錯控制方法7.3常用檢錯碼常用檢錯碼7.4循環(huán)碼循環(huán)碼7.5卷積碼卷積碼本章小結(jié)本章小結(jié)第7章差錯控制技術(shù)2 27.1 差錯控制技術(shù)概述差錯控制技術(shù)概述7.1.1 差錯控制的基本原理差錯控制的基本原理在二進制編碼中， 1位二進制編碼可表示2種不同的狀態(tài)， 2位二進制編碼可表示4種不同的狀態(tài)， n位二進制編碼可以表示2n種不同的狀態(tài)。 在n位二進制編碼的2n種不同的狀態(tài)中， 能表示有用信息的碼組稱為許用碼組， 不能表示有用信息的碼組稱為禁用碼組。 第7章差錯控制技術(shù)3 3現(xiàn)以3位二進制編碼構(gòu)成的碼

2、組集合000, 001, 010, 011, 100, 101,110, 111為例， 分三種情況討論。 （1） 情況1。 若8個狀態(tài)都表示有用信息， 即均是許用碼組， 則其中任一碼字出錯都將變成另一個碼字， 于是， 接收端無法識別哪個出錯。 第7章差錯控制技術(shù)4 4（2） 情況2。若只取4個狀態(tài)， 則取000、 011、 101、 110表示許用碼組， 001、 100、 010、 111表示禁用碼組。如果000中錯1位， 那么可能變?yōu)?01、 100、 010中的任一個， 而這三個均是禁用碼組， 可知傳輸出錯。 當(dāng)000出現(xiàn)三個錯誤時， 將變?yōu)?11， 也是禁用碼； 當(dāng)000出現(xiàn)兩個錯誤時

3、， 將變?yōu)?11、 110、 101， 它們均是許用碼， 可見在接收端無法發(fā)現(xiàn)錯誤。 從上述分析可以看出， 采用這種方法可以發(fā)現(xiàn)部分差錯， 但不能糾錯。 又如， 在接收端收到100， 盡管可以知道是一個錯碼， 但000、 101和110在發(fā)生一位錯碼的情況下均可以是100。 第7章差錯控制技術(shù)5 5（3）情況3。 若要糾正錯碼， 就需增加冗余。 如果僅取000和111表示許用碼組， 其他為禁用碼組， 那么可以檢驗出2個錯碼， 并能糾正1個錯碼。 例如， 收到100時， 若只有一個錯碼， 則可以判斷錯碼在第一位， 并糾正為000， 因為111的任何一位誤碼均不會為100， 而可能為011、101

4、或110； 但若假設(shè)誤碼數(shù)不超過2位， 則存在兩種可能， 即000錯1位和111錯2位， 均可能變?yōu)?00， 因此只能檢測出錯誤， 而無法糾錯。 第7章差錯控制技術(shù)6 67.1.2 差錯控制編碼的特性與能力差錯控制編碼的特性與能力差錯控制編碼的能力與差錯控制編碼的特性有關(guān)。 編碼的特性主要包括碼字的漢明重量、 碼間距離和最小碼距。 我們用C表示由許多碼元Ci(0in1)構(gòu)成的碼字， 碼字中碼元的個數(shù)用n表示。 以下先介紹漢明重量、 碼間距離和最小碼距的概念。第7章差錯控制技術(shù)7 71. 碼字的漢明重量(Hamming Weight)碼字C=Cn1Cn2C0的漢明重量是指碼字中非零碼元的個數(shù)，

5、用HW(C)表示。 例如， 1101的漢明重量為3（可寫成HW(1101)=3）， HW(110101)=4。 第7章差錯控制技術(shù)8 82. 碼間距離(d)碼間距離又稱為海明距離， 是指一碼組集合中任意兩個碼字之間的對應(yīng)位上碼元不同的個數(shù)，用d表示， 可表示為式中， Ci、Cj分別表示碼組集合中的任意兩個碼組（碼字）， Ci=Cin1Cin2Ci0。 例如， 對于兩個碼字1101和0111， =1+0+1+0=2d(10101, 11010)=4。 第7章差錯控制技術(shù)9 93. 最小碼距在一個碼組集合(C1，C2， ， CN）中， 各碼字之間的距離可能是不相同的， 就稱該碼組集合中最小的碼距為

6、最小碼距， 用d0表示。 例如， 對于碼組集合(0111100, 1011011, 1101001)， d(0111100, 1011011)=5， d(0111100, 1101001)=4， d(1011011, 1101001)=3，于是最小碼距d0=3。第7章差錯控制技術(shù)10 10在分析一組碼字（碼組）的檢錯糾錯能力時， 總用最小碼距d0來衡量， 這是一種最不利的情況。 在3位二進制碼中， 把8個碼字的許用碼變?yōu)?個碼字許用碼就具有了糾錯能力， 這是因為這8個碼字的d0=1， 而在000， 001,101,110中， 它們的d0=2， 在000,111中它們的d0=3。 由此可見， 碼

7、組集合中的最小碼距d0不同， 糾錯檢錯的能力不同， 碼組集合中的最小碼距越大， 其糾錯檢錯的能力也就越強。 第7章差錯控制技術(shù)11 114. 編碼糾錯檢錯能力與最小碼距d0的關(guān)系差錯控制編碼的抗干擾能力與碼的結(jié)構(gòu)有關(guān)， 一種編碼的結(jié)構(gòu)是與它們的碼距有關(guān)的， 碼距的長度可以反映出該種編碼方式抗干擾的能力， 碼距與糾錯檢錯能力之間的關(guān)系可用如下定理表述。 第7章差錯控制技術(shù)12 12定理7.1.1 若一種碼的最小碼距為d0， 則它能檢查傳輸差錯個數(shù)（或稱為檢錯能力）e應(yīng)滿足d0e+1。 由定理7.1.1可知， 對于3位二進制編碼， 8個碼字均是許用碼時， d0=1， 于是e=0，這說明該碼沒有差錯

8、能力； 當(dāng)使用4個碼字時， d0=2， 則e=1， 說明能查出1個差錯；若取2個碼字時， d0=3， 則e=2， 說明能查出2個差錯。 因此， 要想使傳輸?shù)拇a字具有檢錯能力， 該碼組集合的最小碼距必須大于或等于2。第7章差錯控制技術(shù)13 13定理 7.1.2 若一種碼的最小距離為d0， 則它能糾正傳輸差錯的個數(shù)（又稱為糾錯能力）t應(yīng)滿足d02t+1。 定理7.1.3 若一種碼的最小距離為d0， 則它能檢查e個差錯， 同時又能糾正t個以下差錯的條件為d0t+e+1。 定理7.1.3說明， 當(dāng)傳輸差錯等于或小于t時， 該碼可以自動糾正這些差錯， 但當(dāng)差錯大于t而又小于e時， 該碼只能檢測出錯來。

9、第7章差錯控制技術(shù)14 14例7.1.1 求碼組集合000,011,101,110和000,111的糾錯檢錯能力。 解 碼組集合000,001,101,110的最小距離d0=2， e=d01=1， 由定理7.1.1可知， 能檢查出一個錯。 對于000,111， d0=3， e=d01=2， 可以查出2個錯。 由定理7.1.2可知，t=1， 能糾正一個錯。第7章差錯控制技術(shù)15 155. 編碼效率控制差錯編碼需要加入一定的監(jiān)督碼才能進行差錯控制， 該編碼方式屬于分組編碼的一種。在編碼時， 加入的監(jiān)督碼位數(shù)越多， 其糾錯的能力也越強， 但同時降低了編碼效率。 若碼長用n表示， 其中的信息碼的長度為

10、k， 監(jiān)督碼的長度為r， 則有n=k+r， 于是， 編碼效率為第7章差錯控制技術(shù)16 167.2 差錯控制方法差錯控制方法7.2.1 自動請求重發(fā)自動請求重發(fā)(ARQ)方式方式由于采用檢錯編碼時， 系統(tǒng)僅能發(fā)現(xiàn)傳輸錯誤， 而不知道錯誤發(fā)生的確切位置， 因此需要采用自動請求重發(fā)工作方式。 接收端根據(jù)校驗序列的編碼規(guī)則判斷所接收的數(shù)據(jù)是否發(fā)生傳輸錯誤， 并把判斷結(jié)果通過反饋信道傳送給發(fā)送端。 接收端判斷的結(jié)果有三種可能： 第7章差錯控制技術(shù)17 17第一種是肯定確認， 即接收端對收到的校驗幀校驗后未發(fā)現(xiàn)錯誤， 會向發(fā)送端發(fā)送一個肯定確認信號， 用ACK表示， 發(fā)送端收到ACK信號后即可知道該幀發(fā)送

11、成功。 第二種是否定確認。 接收端收到一個幀后， 經(jīng)校驗發(fā)現(xiàn)有錯誤， 則回送一個否定確認信號，用NAK表示， 發(fā)送端收到NAK信號后必須重發(fā)該幀。 第7章差錯控制技術(shù)18 18第三種是超時重發(fā)。 發(fā)送端在發(fā)出一個幀后開始計時， 如果在規(guī)定的時間內(nèi)沒有收到該幀的確認信號（ACK或NAK）， 則認為發(fā)生幀的丟失或確認信號丟失， 必須重發(fā)該幀。 在傳送數(shù)據(jù)時， 發(fā)送需經(jīng)過發(fā)送、 等待、 確認這三個階段， 即所謂的“停等ARQ”。 在數(shù)據(jù)幀的發(fā)送中， 發(fā)送端每次僅發(fā)送緩沖區(qū)中的一個數(shù)據(jù)幀， 并在發(fā)送后立即啟動定時器， 等待接收端回送的確認幀。 第7章差錯控制技術(shù)19 19定時器啟動后， 如在規(guī)定的時間

12、內(nèi)沒有收到確認信息幀， 則認為發(fā)生幀的丟失或確認信號丟失， 需要重新發(fā)送。 假如在規(guī)定的時間沒有收到確認信息， 系統(tǒng)就會自動重發(fā)， 重發(fā)會造成重復(fù)幀的現(xiàn)象， 即可能發(fā)生沒有出錯的數(shù)據(jù)幀重復(fù)發(fā)送到接收端的情況。 為了解決重復(fù)幀的問題， 可在每個數(shù)據(jù)幀的幀頭增加一個發(fā)送序號， 當(dāng)收到重復(fù)幀時， 根據(jù)序號可將重復(fù)的幀丟棄掉。第7章差錯控制技術(shù)2020為了提高傳輸效率， 人們提出了連續(xù)重發(fā)請求(Continuous ARQ )技術(shù)， 該技術(shù)的特點是不等待前一幀的確認， 而直接發(fā)送下一幀。 這樣可能會出現(xiàn)發(fā)送端未發(fā)現(xiàn)出錯之前， 就有很多幀到達接收端， 而接收端會將這些幀丟棄。 為解決連續(xù)重發(fā)請求中出現(xiàn)的

13、問題， 人們提出了返回N幀ARQ及選擇性重發(fā)ARQ技術(shù)。 第7章差錯控制技術(shù)21 21ARQ方式具有以下特點： （1） 只需要少量的冗余碼元就可獲得較高的傳輸可靠性。（2） 與前向糾錯相比， 復(fù)雜性和成本較低。（3） ARQ方式要求有反饋信道， 因此不能用于單向傳輸和同步傳輸。 （4） 控制規(guī)程及控制過程較復(fù)雜， 系統(tǒng)重復(fù)傳幀的現(xiàn)象較嚴重， 通信效率低， 不適合實時性要求高的場合。 第7章差錯控制技術(shù)22227.2.2 前向糾錯前向糾錯(FEC)方式方式FEC是利用糾錯編碼使接收端的譯碼器發(fā)現(xiàn)錯誤并準確地判斷出出錯的位置， 從而能自動糾正的差錯控制方式。 FEC方式具有如下特點： （1） 實時

14、性高， 無限反饋信道， 特別適合于單向多點同時傳送， 控制規(guī)則簡單， 但譯碼設(shè)備較復(fù)雜。（2） 糾錯碼的冗余度較高， 傳輸效率較低， 并且糾錯碼與信道特性要相配合， 對信道的要求較高。 第7章差錯控制技術(shù)23237.2.3 混合糾錯混合糾錯(HEC)方式方式混合糾錯方式是由FEC和ARQ兩者結(jié)合而成的差錯控制方式。 它不僅能檢測出錯誤， 而且還能在一定程度上糾正錯誤。 HFC方式具有如下特點： （1） 可以降低FEC的復(fù)雜度， 改善ARQ的連貫性。（2） 通信效率較低， 通信的可靠性較高， 在衛(wèi)星通信中應(yīng)用廣泛。 第7章差錯控制技術(shù)24247.2.4 信息反饋信息反饋(IRQ)方式方式信息反饋

15、方式也稱為回程校驗方式， 它是在發(fā)送端檢測錯誤的。 其工作過程為， 發(fā)送端不對信息進行差錯編碼， 而是直接將信息發(fā)送給接收端， 接收端收到后， 將其存儲起來， 再將其通過反饋信道回送給發(fā)送端， 由接收端比較并發(fā)現(xiàn)是否出錯。 第7章差錯控制技術(shù)2525IRQ方式具有以下特點： （1） 設(shè)備及控制規(guī)程簡單。（2） 需要反饋信道， 收發(fā)兩端均需要大容量的存儲設(shè)備來存儲傳輸信息。（3） 傳輸效率低。 第7章差錯控制技術(shù)2626 7.3 常用檢錯碼常用檢錯碼7.3.1 奇偶校驗碼奇偶校驗碼1. 編碼方法奇偶校驗編碼只需在信息碼后加1位校驗位（或稱為監(jiān)督位）， 使碼組中“1”的個數(shù)為奇數(shù)或偶數(shù)。 兩者的監(jiān)

16、督方程分別為式中，Cn，Cn1， ， C1為信息碼元，C0為監(jiān)督碼元。 第7章差錯控制技術(shù)27272. 奇偶校驗編碼的特點奇偶校驗編碼的優(yōu)點是操作簡單， 冗余度低， 編碼效率高； 缺點是奇校驗只能發(fā)現(xiàn)奇數(shù)個錯誤， 不能發(fā)現(xiàn)偶數(shù)個錯誤。 第7章差錯控制技術(shù)28287.3.2 恒比碼恒比碼恒比碼是指碼字中所含“1”的個數(shù)相同的碼。 由于碼長一定， 則碼字中“1”和“0”的個數(shù)之比是恒定的， 所以稱該種編碼方式為恒比碼。 碼字中“1”的個數(shù)稱為碼重。 1. 編碼方法在恒比碼中， 只需保持碼字中“1”和“0”的比例恒定即可。 在接收端， 只要判斷“1”的個數(shù)是否正確便可判斷傳輸是否正確。 第7章差錯控

17、制技術(shù)2929我國的電傳機傳輸漢字時是采用“保護電碼”來進行的， 該碼為5中取3的恒定碼， 碼的長度為5， 碼中“1”的個數(shù)為3， “0”的個數(shù)為2。 5位碼組成的碼組集合的碼字共有25=32個， 而5中取3的恒定碼共有C35=5!/(53)!3!=10, 恰好可以表示10個狀態(tài)， 即可表示09共10個阿拉伯?dāng)?shù)字， 并用它拼成漢字。 我國的“保護電碼”比國際電碼的抗干擾能力強。 第7章差錯控制技術(shù)3030一般情況下， 從“n中取m（nm）”恒比碼的碼字數(shù)目為可見， 恒比碼實際上是用n比特傳送了lbCmn比特信息量， 如用“5中取3”的恒比碼來傳送數(shù)據(jù)， 每個碼字的信息量為lb10=3.3(bi

18、t)， 而5位二進制碼的每個碼字的信息量為lb25=5(bit)， 也就是說用53.3=1.7的信息量作為檢驗碼而“浪費”的。 第7章差錯控制技術(shù)31 31恒比碼的編碼效率為“5中取3”的恒比碼編碼效率為=3.35=0.66。 在國際無線電報中， 采用7位編碼， 碼字中有3個1， 共有C37=35個， 可表示26個英文字母和其他一些符號。第7章差錯控制技術(shù)32322. 特點恒比碼所具有的優(yōu)點是編碼簡單， 糾錯能力比奇偶校驗碼要強， 適用于電傳機或其他鍵盤設(shè)備； 缺點是不適用隨機二進制序列的編碼。 恒比碼必能發(fā)現(xiàn)錯誤的類型只有一種情況， 即“1”錯為“0”的數(shù)目恰好是“0”錯為“1”的數(shù)目。 第

19、7章差錯控制技術(shù)33337.3.3 矩陣校驗碼矩陣校驗碼1. 編碼方法將若干個所要傳送的數(shù)字序列編排成一個矩陣， 矩陣中的每一行為一個碼字， 在每一行的最后加上一個監(jiān)督碼元， 進行奇偶校驗， 矩陣中的每一列則由不同碼字相同位置的碼元組成， 在每列的最后也加上一個監(jiān)督碼元， 進行奇偶校驗, 如圖7.3.1所示。 第7章差錯控制技術(shù)3434圖7.3.1 矩陣碼組成第7章差錯控制技術(shù)3535圖7.3.1中， a10, , am0為m行奇偶監(jiān)督碼中的m個監(jiān)督位， cn1， ， c0為按列進行監(jiān)督的n列奇偶校驗的n個監(jiān)督位。 這種碼有可能檢測出偶數(shù)個錯誤。 因為每行的監(jiān)督位a10, ， am0雖然不能用

20、于檢測本行中的偶數(shù)個錯誤， 但按列有可能由cn1, ， c0監(jiān)督出來。 有一些偶數(shù)個錯誤不可能檢測出來， 譬如a1n2, a11, a2n2, a21所構(gòu)成的4個錯碼。 第7章差錯控制技術(shù)3636如數(shù)字序列11010101 00101011 00110011 10101010， 現(xiàn)將8位作為一個碼字， 編成一個矩陣， 每個碼字采用奇校驗， 則編碼結(jié)果如圖7.3.2所示。 圖7.3.2 編矩陣碼結(jié)果第7章差錯控制技術(shù)37372. 特點這種二維奇偶監(jiān)督碼適于檢測突發(fā)錯碼。 因為這種突發(fā)錯碼常常成串出現(xiàn)， 隨后有較長一段無錯區(qū)間， 所以在某一行出現(xiàn)多個奇偶錯碼的機會較多， 而這種矩陣碼正適合于檢測這

21、類突發(fā)錯誤。 由于矩陣碼只對構(gòu)成的四角誤碼無法檢測， 所以它的檢測能力較強， 一些試驗表明， 這種碼可以使誤碼率降低至原誤碼率的百萬分之一到萬分之一。 第7章差錯控制技術(shù)38387.3.4 正反碼正反碼正反碼是一種簡單的能糾錯的碼， 該種碼的監(jiān)督位與信息位相同， 且監(jiān)督碼與信息碼相同或相反， 主要用于單位電碼的前向自動糾錯設(shè)備， 能糾正1位錯誤， 發(fā)現(xiàn)大部分2位以上的錯誤。 第7章差錯控制技術(shù)39391. 編碼方法每一個正反碼字由10個碼元組成， 其中5位信息碼， 5位監(jiān)督碼。 當(dāng)信息碼中“1”的個數(shù)為偶數(shù)時， 監(jiān)督碼元是信息碼的反碼。 例如： 信息碼為10101， 監(jiān)督碼為10101， 因為

22、信息碼中“1”為奇數(shù)， 所以監(jiān)督碼與信息碼相同；構(gòu)成的碼字為10101 10101。 信息碼為10010， 監(jiān)督碼為01101， 因為信息碼中“1”為偶數(shù)， 所以監(jiān)督碼與信息碼相反； 構(gòu)成的碼字為10010 01101。 第7章差錯控制技術(shù)40402. 譯碼在接收端， 先將所接收碼字中的信息位和監(jiān)督位， 按對應(yīng)的位進行模2加， 得到一個5位的合成碼, 然后用合成碼產(chǎn)生一個校驗碼。 若接收碼字中信息碼中“1”的個數(shù)為奇數(shù)， 則合成碼作為校驗碼； 如果信息碼中“1”的個數(shù)為偶數(shù)， 則校驗碼為合成碼的反碼。 最后觀察校驗碼字中“1”的個數(shù)， 并根據(jù)表7.3.1中的判決規(guī)則進行判決。 第7章差錯控制技

23、術(shù)41 41例如， 發(fā)送碼字為10101 10101， 接收碼字為10101 10101，合成碼為1010110101=00000， 由于接收碼字中信息碼“1”的個數(shù)為奇數(shù)個， 因此校驗碼為00000， 對應(yīng)表7.3.1 可看到無錯誤傳輸。 又例如， 發(fā)送碼字為10101 10101， 接收碼字為11101 10101，合成碼為1110110101=01000， 由于接收碼字中信息碼“1”的個數(shù)為偶數(shù)個， 因此校驗碼為10111， 對應(yīng)表7.3.1 可知信息碼有1位錯， 位置在校驗碼“0”所對應(yīng)的位置， 故可自動糾正為10101。第7章差錯控制技術(shù)4242第7章差錯控制技術(shù)43437.3.5

24、線性分組碼線性分組碼線性分組碼(Linear Block Codes)是信道編碼中最基本的一類編碼， 在線性分組碼中，監(jiān)督碼僅與所在碼組中的信息碼元有關(guān)， 且兩者之間是通過預(yù)設(shè)的線性關(guān)系聯(lián)系的。 線性分組碼的構(gòu)成是將信息序列劃分為等長為k位的序列段后， 在每段之后附加r位監(jiān)督碼元(Parity Check bits)， 所構(gòu)成的長度為n=k+r的碼組記為(n, k)分組碼。 第7章差錯控制技術(shù)4444n位長度二進制碼可編成2n個碼字， 但由于信息碼的長度僅為k， 即信息碼字的個數(shù)為2k個（稱其為許用碼）， 所以其他2n2k個碼字不能表示信息， 這些不能表示信息的碼稱為禁用碼。 在(n, k)分

25、組碼中， 碼的長度為n， 其中表示信息的碼長為k， 共有2k個不同的長度為n的碼來對應(yīng)所表示的信息， 這些碼構(gòu)成的碼組集合可用數(shù)學(xué)中的“群”來表示， 并具有以下性質(zhì)。第7章差錯控制技術(shù)4545性質(zhì)1: 封閉性, 即任意兩個碼字之模2和仍為一個碼字。 性質(zhì)2: 碼的最小距離等于非零碼的最小重量。 線性分組編碼就是對長度為k的信息碼按照一定規(guī)則加入長度為nk的監(jiān)督碼的過程，并且所增加的監(jiān)督碼與信息碼的碼元之間構(gòu)成某種線性關(guān)系。 以下以(7, 4)線性分組碼的編碼為例來說明其整個編碼過程。 第7章差錯控制技術(shù)4646(7,4)碼中， 信息碼的長度為4， 可用C6C5C4C3來表示， 監(jiān)督碼可用C2C

26、1C0來表示， 編碼后所形成的線性分組編碼可用C6C5C4C3C2C1C0來表示， 監(jiān)督碼元C2、 C1、 C0與信息碼元C6、 C5、 C4及C3構(gòu)成了如下的線性關(guān)系：利用式(7.3.5)可得到(7, 4)線性分組碼， 其結(jié)果如表7.3.2所示。第7章差錯控制技術(shù)4747第7章差錯控制技術(shù)48487.4 循循 環(huán)環(huán) 碼碼7.4.1 循環(huán)碼的基本概念循環(huán)碼的基本概念在數(shù)據(jù)通信中， 尤其是在計算機通信中， 應(yīng)用非常廣泛的一種差錯控制編碼是循環(huán)冗余校驗碼(CRC)。 CRC編碼實際上是一種線性分組碼， 具有很強的糾錯能力。第7章差錯控制技術(shù)49491. 循環(huán)冗余校驗碼(CRC)的定義若線性分組碼各

27、碼字中的碼元循環(huán)左移位（或右移位）所形成的碼字仍然是碼組集合中的一個碼字（除全零碼外）， 則這種碼就稱為循環(huán)碼。 如n長度循環(huán)碼中的一個碼為C=Cn1Cn2C1C0, 依次循環(huán)位移后得到的碼為各碼字均是循環(huán)碼中的碼組。 第7章差錯控制技術(shù)50502. 碼多項式一個由二進制碼元序列組成的碼組都可以和一個只含有“0”和“1”兩個系數(shù)的多項式建立起一一對應(yīng)的關(guān)系， 這個多項式就稱為碼多項式。 一個n位長的二進制序列， 它是碼多項式Xn1到X0的n1次多項式的系數(shù)。 如二進制碼元序列110110所對應(yīng)的碼多項式為第7章差錯控制技術(shù)51 51把碼組中的碼元當(dāng)作多項式系數(shù)（取0或1）， 把n長度的碼字寫成

28、最高次方n1次的多項式：（7.4.1）一個碼字（碼組）與碼多項式是一一對應(yīng)的， 如碼組1001101所對應(yīng)的碼多項式為T(X)=X6+X3+X2+1； 而碼多項式X5+X4+X2+X對應(yīng)的碼組為110110。 二進制碼多項式間可進行加減運算， 即進行邏輯上的異或運算。如兩個二進制碼多項式A1(X)、A2(X)間的加減運算為第7章差錯控制技術(shù)52523. 碼多項式的同余若用X7+1去除X7+X6+X5+X3所得的余式和用X7+1去除X6+X5+X3+1所得的余式相同， 即則稱兩個多項式X7+X6+X5+X3和X6+X5+X3+1同余， 并記為第7章差錯控制技術(shù)5353利用同余的概念可以將循環(huán)碼通

29、過對應(yīng)的碼多項式進行分析處理。 在循環(huán)碼中， 所有的非零碼都具有循環(huán)特性， 即一個碼字可以由另一碼字向左（或向右）循環(huán)位移而得到， 對應(yīng)于這種循環(huán)碼多項式也具有循環(huán)特性， 即每個碼多項式都可以由一個次數(shù)低的碼多項式得到。該碼循環(huán)一次的碼多項式是原碼多項式C(x)乘以x， 除以xn+1的余式， 記為C1(x)=xC（x） （mod xn+1）第7章差錯控制技術(shù)5454推廣下去， C（x）的i次循環(huán)位移Ci（x）是C（x）乘以xi， 除以xn+1的余式， 即Ci（x）=xiC（x） （mod xn+1） （7.4.2） 循環(huán)碼是線性分組碼的一種， 因此可以應(yīng)用線性分組碼的編譯碼方法。 在(n, k

30、)循環(huán)碼集合中， 取前k1位都為零的碼字g(x)， 根據(jù)循環(huán)碼的循環(huán)特性， 將g(x)進行k1循環(huán)移位， 可得到k個碼字g(x), xg(x), ， xk1g(x)。第7章差錯控制技術(shù)5555這k個碼多項式線性無關(guān)， 因此可利用這k個多項式相對應(yīng)的碼字作為各行構(gòu)成碼生成矩陣， 于是得到(n, k)循環(huán)碼的生成矩陣第7章差錯控制技術(shù)5656碼生成矩陣一旦確定， 碼也就確定了。 式(7.4.3）說明(n, k)循環(huán)碼可以由它的一個(n, k)次碼多項式g(x)來確定， 稱g(x)為碼生成多項式。 (n, k)次碼生成多項式g(x)具有下列性質(zhì)： 性質(zhì)1: g(x) 是唯一的(n, k)次碼多項式，

31、 并且它的次數(shù)最低。性質(zhì)2: g(x) 是xn+1的因式， 即xn+1=h(x)g(x)， h(x)稱為監(jiān)督多項式。 第7章差錯控制技術(shù)57577.4.2 循環(huán)碼的編碼和譯碼循環(huán)碼的編碼和譯碼1. 編碼方法循環(huán)碼是由信息碼元和監(jiān)督碼元構(gòu)成的。 首先把信息序列分為等長為k的若干個序列段，每信息段附加r位長度的監(jiān)督碼元， 從而構(gòu)成長度為n=k+r的循環(huán)碼。 循環(huán)碼用(n, k)表示， 它也可以用一個n1次多項式來表示。 循環(huán)碼的格式如圖7.4.1所示。 第7章差錯控制技術(shù)5858圖7.4.1 循環(huán)碼的格式第7章差錯控制技術(shù)5959一個n位循環(huán)碼由k位信息碼加上r位校驗碼組成， 其中r=nk。 表征

32、循環(huán)碼(CRC)的多項式稱為生成多項式G(X)。k位二進制碼元加上r位CRC校驗位后， 信息位要向左移， 這相當(dāng)于A(X)乘上X。 XA(X)除以生成多項式G(X)， 得到整數(shù)多項式Q(X)加上余數(shù)多項式R(X)， 即從而有第7章差錯控制技術(shù)6060利用多項式加減法的性質(zhì)， 有這說明信息多項式A(X)和余數(shù)多項式R(X)可以合并為一個新的多項式C(X)， 稱為循環(huán)多項式， 該多項式是生成多項式G(X)的整數(shù)Q(X)倍。第7章差錯控制技術(shù)61 612. 循環(huán)碼的性質(zhì)在循環(huán)碼中， nk次碼多項式有一個且僅有一個生成多項式G(X)。 在循環(huán)碼中， 所有碼多項式能被生成多項式G(X)整除。 循環(huán)碼的輸

33、出多項式G(X)是Xn+1的一個因式。第7章差錯控制技術(shù)62623. CRC校驗碼的生成和校驗根據(jù)信息序列的分組長度和檢錯能力的要求， 每個k位信息段附加r位監(jiān)督碼元構(gòu)成n=k+r位循環(huán)碼， 其生成步驟如下： (1) 在k位信息碼組的后面加上r個0。 r是監(jiān)督碼元的位數(shù)， 比生成多項式G(X)的位數(shù)r+1少1位。 第7章差錯控制技術(shù)6363(2) 采用二進制除法將新的加長的長度為n的碼組用G(X)來除， 所產(chǎn)生的余數(shù)就是CRC校驗碼。 (3) 用r個碼元的CRC校驗碼元替代信息段后面附加的r個0， 如果余數(shù)的位數(shù)小于r， 則在最左端用0補足r位； 如果除法運算沒有產(chǎn)生余數(shù)（信息碼組是可以被整除

34、的）， 則用r位0作為校驗碼。第7章差錯控制技術(shù)6464在接收端進行校驗時， 可按以下步驟進行： 第一步， 將接收到的數(shù)據(jù)分為若干個長度為n的數(shù)據(jù)段， 用G(X)來除。 第二步， 如果n位數(shù)據(jù)段能被G(X)整除， 則說明該數(shù)據(jù)段在傳送的過程中未發(fā)生差錯， 否則， 說明傳送過程中出現(xiàn)了差錯。 以下以兩個例子來說明循環(huán)碼的編碼過程。 第7章差錯控制技術(shù)6565例如， 信息碼組為1101， 生成多項式為G(X)=X3+X+1， 編(7, 4)循環(huán)碼。 編碼步驟如下： (1) A(X)=1101為4位二進制碼， 需附加r=74=3位監(jiān)督碼， 在1101后附加000， 變?yōu)?101000。 (2) 用G

35、(X)=X3+X+1（對應(yīng)的碼組為1011）去除1101000， 即將1101000作為被除數(shù)， 1011作為除數(shù)， 進行除法運算, 得到的余數(shù)為1， 于是CRC校驗碼為001。 第7章差錯控制技術(shù)6666(3) 用001替代第一步中的000， 最后的編碼為1101001。 注意， 在進行除法運算時， 需要進行減法運算， 該減法運算實際上是一個異或運算， 如1001， 則結(jié)果為11。 又例如， 信息碼組為101， 編一個(7, 3)的循環(huán)碼。 編碼的步驟如下： （1） 確定監(jiān)督碼的碼長， 監(jiān)督位的碼長為r=nk=73=4。 （2） 確定生成多項式G（X）。 根據(jù)循環(huán)碼的性質(zhì)， 循環(huán)碼的生成多項

36、式G（X）Xn+1的一個因式， 所以生成多項式G（X）是X7+1的一個因式， 而G（X）是nk=4次因式。 第7章差錯控制技術(shù)6767對X7+1可分解因式為X7+1=（X+1）（X3+X2+1）（X3+X2+1） 從X7+1的因式分解中任意選擇4次因式， 我們選擇G(X)=(X+1)(X3+X2+1)， 需要注意的是上述的因式分解與嚴格意義上的初等數(shù)學(xué)的因式分解不同， 這里執(zhí)行的運算是異或運算， 如X+X=0， 因此G(X)=(X+1)(X3+X2+1)=X4+X3+X2+1所對應(yīng)的碼為11101。 第7章差錯控制技術(shù)6868(3) 在信息碼組后附加4位0， 變?yōu)?010000。 (4) 除法

37、運算， 并求余。 (5) 用余數(shù)0011替代0000， 得到最后的編碼為1010011。 第7章差錯控制技術(shù)69694. 循環(huán)碼的應(yīng)用及特點在串行通信中， 常常采用CRC-16、 CRC-CCITT及CRC-32這3種常用的生成多項式來產(chǎn)生校驗碼。 CRC-16的生成多項式為G(X)=X16+X15+X2+1; CRC-CCITT的生成多項式為G(X)=X16+X12+X5+1; CRC-32的生成多項式為G(X)=X32+X26+X23+X22+X16+X12+X11+X10+X8+X7+X5+X4+X2+X+1。 第7章差錯控制技術(shù)70707.5 卷卷 積積 碼碼7.5.1 基本原理基本原

38、理卷積碼是一種非分組碼， 它的校驗位不僅和本組碼有關(guān)， 而且還與前組及前若干組碼有關(guān)， 具有連環(huán)監(jiān)督作用， 因此卷積碼也稱為連環(huán)碼。 卷積碼的整個編碼過程是環(huán)環(huán)相扣連鎖進行的。 編碼時， 信息序列分為k0個碼元段， 每段在經(jīng)過編碼后變?yōu)閚0(n0k0)個碼元的碼組， 通常n0和k0都是較小的整數(shù)。第7章差錯控制技術(shù)71 71編碼器的每個單位時間內(nèi)所輸出的n0個碼元不僅與此時輸入的k0個信息碼元有關(guān)， 而且還與之前較長一段時間內(nèi)輸入的信息碼元有關(guān)。 圖7.5.1所示為一個簡單的n0=3， k0=1 的卷積編碼器。 第7章差錯控制技術(shù)7272圖7.5.1 n0=3, k0=1的卷積編碼器第7章差錯

39、控制技術(shù)7373在每一個單位時間內(nèi)， 當(dāng)一個新的信息碼元mj進入編碼器， 存儲在存儲器中的碼組向右依次移動一位， 此時新的信息碼元一方面直接進入信道， 同時前面兩個單位時間內(nèi)輸入的信息碼元mj1、 mj2按一定方式進行模2加的運算， 得到兩個監(jiān)督碼元Pj1、 Pj2后依次隨mj送入信道。 由圖7.5.1可知：（7.5.1）第7章差錯控制技術(shù)7474若下一個單位時間內(nèi)輸入的信息碼元為mj+1， 則它的兩個監(jiān)督碼元為（7.5.2）若輸入的信息碼元為mj、 mj+1， 則輸出的編碼為mj Pj1Pj2 mj+1 P（j+1）1 P（j+1）2。 若mjmj+1=11， 則輸出為111101。第7章差

40、錯控制技術(shù)75757.5.2 編碼和譯碼編碼和譯碼1. 簡單卷積編碼器簡單卷積編碼器如圖7.5.2所示。 它由兩個移位寄存器R1和R2及一個模2加法器構(gòu)成。圖7.5.2 簡單卷積編碼器原理圖第7章差錯控制技術(shù)7676移位寄存器按信息碼率的速度進行工作， 當(dāng)輸入1位信息碼元時， 電子開關(guān)倒換一次，即前半拍接通a端， 后半拍接通b端。 因此， 若輸入信息為a0a1a2a3， 第一拍， 從寄存器R1中移出的為a0， 所以a端輸出的是a0； 寄存器R2移出的是0（初始值為0）， 所以b端輸出的為b0=a0 + 0=a0。第7章差錯控制技術(shù)77772. 解碼器與圖7.5.2所對應(yīng)的解碼器如圖7.5.3所示。 解碼器的輸入端是一個電子開關(guān)， 它按節(jié)拍把信息碼元與監(jiān)督碼元分別接到a端和b端， 3個移位寄存器R1、 R2和R3的節(jié)拍為碼元序列節(jié)拍的一半。 R1、 R2在信息碼元到達時移位，監(jiān)督碼元到達期間保持原狀態(tài)。 寄存器R3在監(jiān)督碼元到達時移位， 在信息碼元到達時保持原狀態(tài)。第7章差錯控制技術(shù)7878R1、 R2及加法器1構(gòu)成與發(fā)送端一樣的編碼器， 它從接收到的信息碼元序列中計算出監(jiān)督碼序