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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

23、術(shù)41 41例如， 發(fā)送碼字為10101 10101， 接收碼字為10101 10101，合成碼為1010110101=00000， 由于接收碼字中信息碼“1”的個(gè)數(shù)為奇數(shù)個(gè)， 因此校驗(yàn)碼為00000， 對應(yīng)表7.3.1 可看到無錯(cuò)誤傳輸。 又例如， 發(fā)送碼字為10101 10101， 接收碼字為11101 10101，合成碼為1110110101=01000， 由于接收碼字中信息碼“1”的個(gè)數(shù)為偶數(shù)個(gè)， 因此校驗(yàn)碼為10111， 對應(yīng)表7.3.1 可知信息碼有1位錯(cuò)， 位置在校驗(yàn)碼“0”所對應(yīng)的位置， 故可自動(dòng)糾正為10101。第7章差錯(cuò)控制技術(shù)4242第7章差錯(cuò)控制技術(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章差錯(cuò)控制技術(shù)4444n位長度二進(jìn)制碼可編成2n個(gè)碼字， 但由于信息碼的長度僅為k， 即信息碼字的個(gè)數(shù)為2k個(gè)（稱其為許用碼）， 所以其他2n2k個(gè)碼字不能表示信息， 這些不能表示信息的碼稱為禁用碼。 在(n, k)分

25、組碼中， 碼的長度為n， 其中表示信息的碼長為k， 共有2k個(gè)不同的長度為n的碼來對應(yīng)所表示的信息， 這些碼構(gòu)成的碼組集合可用數(shù)學(xué)中的“群”來表示， 并具有以下性質(zhì)。第7章差錯(cuò)控制技術(shù)4545性質(zhì)1: 封閉性, 即任意兩個(gè)碼字之模2和仍為一個(gè)碼字。 性質(zhì)2: 碼的最小距離等于非零碼的最小重量。 線性分組編碼就是對長度為k的信息碼按照一定規(guī)則加入長度為nk的監(jiān)督碼的過程，并且所增加的監(jiān)督碼與信息碼的碼元之間構(gòu)成某種線性關(guān)系。 以下以(7, 4)線性分組碼的編碼為例來說明其整個(gè)編碼過程。 第7章差錯(cuò)控制技術(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章差錯(cuò)控制技術(shù)4747第7章差錯(cuò)控制技術(shù)48487.4 循循 環(huán)環(huán) 碼碼7.4.1 循環(huán)碼的基本概念循環(huán)碼的基本概念在數(shù)據(jù)通信中， 尤其是在計(jì)算機(jī)通信中， 應(yīng)用非常廣泛的一種差錯(cuò)控制編碼是循環(huán)冗余校驗(yàn)碼(CRC)。 CRC編碼實(shí)際上是一種線性分組碼， 具有很強(qiáng)的糾錯(cuò)能力。第7章差錯(cuò)控制技術(shù)49491. 循環(huán)冗余校驗(yàn)碼(CRC)的定義若線性分組碼各

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

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

29、過對應(yīng)的碼多項(xiàng)式進(jìn)行分析處理。 在循環(huán)碼中， 所有的非零碼都具有循環(huán)特性， 即一個(gè)碼字可以由另一碼字向左（或向右）循環(huán)位移而得到， 對應(yīng)于這種循環(huán)碼多項(xiàng)式也具有循環(huán)特性， 即每個(gè)碼多項(xiàng)式都可以由一個(gè)次數(shù)低的碼多項(xiàng)式得到。該碼循環(huán)一次的碼多項(xiàng)式是原碼多項(xiàng)式C(x)乘以x， 除以xn+1的余式， 記為C1(x)=xC（x） （mod xn+1）第7章差錯(cuò)控制技術(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)進(jìn)行k1循環(huán)移位， 可得到k個(gè)碼字g(x), xg(x), ， xk1g(x)。第7章差錯(cuò)控制技術(shù)5555這k個(gè)碼多項(xiàng)式線性無關(guān)， 因此可利用這k個(gè)多項(xiàng)式相對應(yīng)的碼字作為各行構(gòu)成碼生成矩陣， 于是得到(n, k)循環(huán)碼的生成矩陣第7章差錯(cuò)控制技術(shù)5656碼生成矩陣一旦確定， 碼也就確定了。 式(7.4.3）說明(n, k)循環(huán)碼可以由它的一個(gè)(n, k)次碼多項(xiàng)式g(x)來確定， 稱g(x)為碼生成多項(xiàng)式。 (n, k)次碼生成多項(xiàng)式g(x)具有下列性質(zhì)： 性質(zhì)1: g(x) 是唯一的(n, k)次碼多項(xiàng)式，

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

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

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

34、的）， 則用r位0作為校驗(yàn)碼。第7章差錯(cuò)控制技術(shù)6464在接收端進(jìn)行校驗(yàn)時(shí)， 可按以下步驟進(jìn)行： 第一步， 將接收到的數(shù)據(jù)分為若干個(gè)長度為n的數(shù)據(jù)段， 用G(X)來除。 第二步， 如果n位數(shù)據(jù)段能被G(X)整除， 則說明該數(shù)據(jù)段在傳送的過程中未發(fā)生差錯(cuò)， 否則， 說明傳送過程中出現(xiàn)了差錯(cuò)。 以下以兩個(gè)例子來說明循環(huán)碼的編碼過程。 第7章差錯(cuò)控制技術(shù)6565例如， 信息碼組為1101， 生成多項(xiàng)式為G(X)=X3+X+1， 編(7, 4)循環(huán)碼。 編碼步驟如下： (1) A(X)=1101為4位二進(jìn)制碼， 需附加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ù)， 進(jìn)行除法運(yùn)算, 得到的余數(shù)為1， 于是CRC校驗(yàn)碼為001。 第7章差錯(cuò)控制技術(shù)6666(3) 用001替代第一步中的000， 最后的編碼為1101001。 注意， 在進(jìn)行除法運(yùn)算時(shí)， 需要進(jìn)行減法運(yùn)算， 該減法運(yùn)算實(shí)際上是一個(gè)異或運(yùn)算， 如1001， 則結(jié)果為11。 又例如， 信息碼組為101， 編一個(gè)(7, 3)的循環(huán)碼。 編碼的步驟如下： （1） 確定監(jiān)督碼的碼長， 監(jiān)督位的碼長為r=nk=73=4。 （2） 確定生成多項(xiàng)式G（X）。 根據(jù)循環(huán)碼的性質(zhì)， 循環(huán)碼的生成多項(xiàng)

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

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

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

39、控制技術(shù)7373在每一個(gè)單位時(shí)間內(nèi)， 當(dāng)一個(gè)新的信息碼元mj進(jìn)入編碼器， 存儲在存儲器中的碼組向右依次移動(dòng)一位， 此時(shí)新的信息碼元一方面直接進(jìn)入信道， 同時(shí)前面兩個(gè)單位時(shí)間內(nèi)輸入的信息碼元mj1、 mj2按一定方式進(jìn)行模2加的運(yùn)算， 得到兩個(gè)監(jiān)督碼元Pj1、 Pj2后依次隨mj送入信道。 由圖7.5.1可知：（7.5.1）第7章差錯(cuò)控制技術(shù)7474若下一個(gè)單位時(shí)間內(nèi)輸入的信息碼元為mj+1， 則它的兩個(gè)監(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、錯(cuò)控制技術(shù)75757.5.2 編碼和譯碼編碼和譯碼1. 簡單卷積編碼器簡單卷積編碼器如圖7.5.2所示。 它由兩個(gè)移位寄存器R1和R2及一個(gè)模2加法器構(gòu)成。圖7.5.2 簡單卷積編碼器原理圖第7章差錯(cuò)控制技術(shù)7676移位寄存器按信息碼率的速度進(jìn)行工作， 當(dāng)輸入1位信息碼元時(shí)， 電子開關(guān)倒換一次，即前半拍接通a端， 后半拍接通b端。 因此， 若輸入信息為a0a1a2a3， 第一拍， 從寄存器R1中移出的為a0， 所以a端輸出的是a0； 寄存器R2移出的是0（初始值為0）， 所以b端輸出的為b0=a0 + 0=a0。第7章差錯(cuò)控制技術(shù)77772. 解碼器與圖7.5.2所對應(yīng)的解碼器如圖7.5.3所示。 解碼器的輸入端是一個(gè)電子開關(guān)， 它按節(jié)拍把信息碼元與監(jiān)督碼元分別接到a端和b端， 3個(gè)移位寄存器R1、 R2和R3的節(jié)拍為碼元序列節(jié)拍的一半。 R1、 R2在信息碼元到達(dá)時(shí)移位，監(jiān)督碼元到達(dá)期間保持原狀態(tài)。 寄存器R3在監(jiān)督碼元到達(dá)時(shí)移位， 在信息碼元到達(dá)時(shí)保持原狀態(tài)。第7章差錯(cuò)控制技術(shù)7878R1、 R2及加法器1構(gòu)成與發(fā)送端一樣的編碼器， 它從接收到的信息碼元序列中計(jì)算出監(jiān)督碼序