通信原理差錯(cuò)控制編碼學(xué)習(xí)教案

1、會(huì)計(jì)學(xué)1通信通信(tng xn)原理差錯(cuò)控制編碼原理差錯(cuò)控制編碼第一頁，共92頁。0 、復(fù)習(xí)、復(fù)習(xí)(fx)v 模擬信源：在無線廣播(gungb)中，信源一般是一個(gè)語音源（話音或音樂）；在電視廣播(gungb)中，信源主要是活動(dòng)圖像的視頻信號(hào)源。這些信源的輸出都是模擬信號(hào)，所以稱之為模擬源。v 信源編碼(bin m)：將模擬信息源的輸出轉(zhuǎn)化為數(shù)字信號(hào)，即A/D轉(zhuǎn)換。v 信源編碼目的：提高通信有效性，減少原消息的冗余度。第1頁/共92頁第二頁，共92頁。差錯(cuò)出現(xiàn)(chxin)原因 外界噪聲 傳輸中碼間串?dāng)_解決方法 合理地設(shè)計(jì)基帶信號(hào)，選擇調(diào)制、解調(diào)方式，采用均衡(jnhng)技術(shù)，發(fā)送功率等因素，

2、使誤比特率降低。 差錯(cuò)控制措施。信號(hào)在數(shù)字信道傳輸過程中受到干擾的影響，使信號(hào)波形變壞，發(fā)生誤碼，可以采用一些方法解決。第2頁/共92頁第三頁，共92頁。 差錯(cuò)控制編碼屬信道編碼，要求在滿足有效性前提下，盡可能提高數(shù)字通信的可靠性。 差錯(cuò)控制編碼是在信息序列上附加上一些監(jiān)督碼元，利用這些冗余的碼元，使原來不規(guī)律的或規(guī)律性不強(qiáng)的原始數(shù)字信號(hào)變?yōu)橛幸?guī)律的數(shù)字信號(hào)。例如奇偶校驗(yàn)。 差錯(cuò)控制譯碼則利用這些規(guī)律性來鑒別傳輸過程是否發(fā)生(fshng)錯(cuò)誤，或進(jìn)而糾正錯(cuò)誤。第3頁/共92頁第四頁，共92頁。1、差錯(cuò)控制編碼、差錯(cuò)控制編碼(bin m)分類分類第4頁/共92頁第五頁，共92頁。2、誤碼類型、誤

3、碼類型(lixng)v 隨機(jī)(su j)誤碼v 突發(fā)(t f)誤碼錯(cuò)碼出現(xiàn)是隨機(jī)的、錯(cuò)碼之間統(tǒng)計(jì)獨(dú)立。由隨機(jī)噪聲引起存在隨機(jī)誤碼的信道稱為隨機(jī)信道無記憶信道差錯(cuò)在短時(shí)間成串出現(xiàn)，而在其間又存在較長的無差錯(cuò)區(qū)間，且差錯(cuò)之間相關(guān)例如：脈沖噪聲，存儲(chǔ)系統(tǒng)中磁帶的缺陷或讀寫頭接觸不良引起，再例如用手機(jī)過涵洞，且無發(fā)射天線存在這種差錯(cuò)的信道稱為突發(fā)信道有記憶信道第5頁/共92頁第六頁，共92頁。3、錯(cuò)誤、錯(cuò)誤(cuw)圖樣圖樣l例如：l設(shè)發(fā)送數(shù)據(jù)序列為：00000000001111111111l接收數(shù)據(jù)序列為： 01101001001111001001l錯(cuò)誤圖樣（差錯(cuò)(chcu)序列）：發(fā)送數(shù)據(jù)序列與接

4、收序列對(duì)應(yīng)碼位的模和l則差錯(cuò)(chcu)序列為： 01101001000000110110l可見l發(fā)生了兩個(gè)長度分別為和的突發(fā)差錯(cuò)(chcu)，其錯(cuò)誤圖樣分別為1101001和11011l突發(fā)長度：指突發(fā)差錯(cuò)(chcu)首位與末位之間的長度（中間可能有沒錯(cuò)的碼位）第6頁/共92頁第七頁，共92頁。l說明l差錯(cuò)序列或錯(cuò)誤圖樣中的“”表示對(duì)應(yīng)碼位沒錯(cuò)，而“”表示有錯(cuò)l實(shí)際信道很復(fù)雜，所出現(xiàn)的差錯(cuò)并不是單一的，往往是隨機(jī)和突發(fā)差錯(cuò)并存，只不過以某種錯(cuò)誤為主l一般說來，糾正隨機(jī)差錯(cuò)的編譯碼方法(fngf)和設(shè)備比較簡單，成本較低，效果較顯著；而糾正突發(fā)差錯(cuò)的編譯碼方法(fngf)和設(shè)備比較復(fù)雜，成本較

5、高，效果也不如前者顯著第7頁/共92頁第八頁，共92頁。 4、信道、信道(xn do)類型類型v 隨機(jī)(su j)信道v 突發(fā)(t f)信道v 混合信道第8頁/共92頁第九頁，共92頁。5、差錯(cuò)控制方法、差錯(cuò)控制方法(fngf)v檢錯(cuò)重發(fā)（ARQ）v 停發(fā)等候重發(fā)v 返回重發(fā)v 選擇重發(fā)v前向糾錯(cuò)（FEC）v反饋校驗(yàn)（IRQ）v檢錯(cuò)刪除 （ECD）v混合(hnh)方式（HEC）第9頁/共92頁第十頁，共92頁。（1）檢錯(cuò)重發(fā)法（）檢錯(cuò)重發(fā)法（ARQ） Automatic Repeat reQuest 收端在接收(jishu)到的信碼中發(fā)現(xiàn)錯(cuò)碼時(shí)，就通知發(fā)端重發(fā)，直到正確接收(jishu)為止。

6、例如奇偶校驗(yàn)。 檢錯(cuò)重發(fā)方式只用于檢測(cè)誤碼，能夠在接收(jishu)單元中發(fā)現(xiàn)錯(cuò)誤，但不一定知道該錯(cuò)誤碼的具體位置。 需具備雙向信道。第10頁/共92頁第十一頁，共92頁。發(fā)發(fā)收收能夠發(fā)現(xiàn)錯(cuò)誤的碼能夠發(fā)現(xiàn)錯(cuò)誤的碼圖圖11.1-1（a) 檢錯(cuò)重發(fā)（檢錯(cuò)重發(fā)（ARQ)應(yīng)答信號(hào)應(yīng)答信號(hào)圖圖11.1-1（b) 檢錯(cuò)重發(fā)（檢錯(cuò)重發(fā)（ARQ)信信源源編碼器和編碼器和緩沖存儲(chǔ)緩沖存儲(chǔ)器器重發(fā)控制重發(fā)控制雙雙向向信信道道解碼器解碼器指令產(chǎn)生指令產(chǎn)生器器輸出緩輸出緩沖存儲(chǔ)沖存儲(chǔ)器器收收信信者者正確時(shí)輸出錯(cuò)誤時(shí)刪除判斷有無(yu w)錯(cuò)誤第11頁/共92頁第十二頁，共92頁。 停發(fā)等候停發(fā)等候(dnghu)重發(fā)重

7、發(fā)2發(fā)送端：接收端：133123ACKACKNAK發(fā)現(xiàn)錯(cuò)誤TITw停頓時(shí)間圖圖11.1-2 停發(fā)等候停發(fā)等候(dnghu)重發(fā)重發(fā)第12頁/共92頁第十三頁，共92頁。發(fā)端在Tw時(shí)間內(nèi)送出一個(gè)碼組；收端收到后檢查。如果未發(fā)現(xiàn)錯(cuò)誤，則發(fā)回一個(gè)認(rèn)可信號(hào)（ACK）給發(fā)送端，發(fā)送端收到ACK信號(hào)再發(fā)下一個(gè)碼組若檢測(cè)到錯(cuò)誤，則發(fā)回一個(gè)否認(rèn)信號(hào)（NAK），發(fā)送端收到NAK信號(hào)后重發(fā)前一碼組，并再次等候ACK信號(hào)或NAK信號(hào)發(fā)送兩個(gè)碼組之間有停頓時(shí)間TI，影響(yngxing)了傳輸效率第13頁/共92頁第十四頁，共92頁。 返回返回(fnhu)重發(fā)重發(fā)(拉回重發(fā)拉回重發(fā))其發(fā)送端不停地送出一個(gè)個(gè)連續(xù)碼組，

8、不再等候收端返回的ACK信號(hào)一旦收端發(fā)現(xiàn)錯(cuò)誤并返回NAK信號(hào)，則發(fā)端(fdun)從下一碼組開始重發(fā)前面的N個(gè)碼組N的大小取決于信號(hào)傳遞及處理所帶來的延時(shí)第14頁/共92頁第十五頁，共92頁。發(fā)送端：接收端：1 2 3 4 5 6 2 3 41 2 3 4 5 6 2 3 45 6 7 8 95 6 7 8 9發(fā)現(xiàn)錯(cuò)誤NAK從碼組2開始重發(fā)圖圖11.1-3 返回返回(fnhu)重發(fā)重發(fā)第15頁/共92頁第十六頁，共92頁。 選擇選擇(xunz)重發(fā)重發(fā)也是連續(xù)不斷地發(fā)送(f sn)碼組，收端檢測(cè)到錯(cuò)誤后發(fā)回NAK信號(hào)。與返回重發(fā)不同的是，發(fā)端并不重發(fā)錯(cuò)誤碼組后的所有碼組，而只重發(fā)有錯(cuò)的那個(gè)碼組第

9、16頁/共92頁第十七頁，共92頁。發(fā)送端：接收端：1 2 3 4 5 6 2 7 81 2 3 4 5 6 2 7 899發(fā)現(xiàn)錯(cuò)誤NAK重發(fā)碼組2圖圖11.1-4 選擇選擇(xunz)重發(fā)重發(fā)第17頁/共92頁第十八頁，共92頁。三者比較 選擇重發(fā)傳輸效率最高，但成本最貴：控制機(jī)制復(fù)雜，發(fā)端和收端都要有數(shù)據(jù)緩沖器； 返回重發(fā)、選擇重發(fā)需要(xyo)全雙工數(shù)據(jù)鏈路，而停發(fā)等候重發(fā)只要求半雙工的數(shù)據(jù)鏈路。第18頁/共92頁第十九頁，共92頁。（2）前向糾錯(cuò)）前向糾錯(cuò)(ji cu)法（法（FEC） Forward Error Correction發(fā)發(fā)收收能夠糾正錯(cuò)誤的碼能夠糾正錯(cuò)誤的碼圖圖11.1

10、-5 前向糾錯(cuò)前向糾錯(cuò)(ji cu)（FEC)信信源源編編碼碼器器單單向向信信道道糾錯(cuò)譯碼糾錯(cuò)譯碼器器輸出緩輸出緩沖存儲(chǔ)沖存儲(chǔ)器器收收信信者者+第19頁/共92頁第二十頁，共92頁。發(fā)送端將信息(xnx)序列編碼成能夠糾正錯(cuò)誤的碼，接收端根據(jù)編碼規(guī)則進(jìn)行檢查，如果有錯(cuò)自動(dòng)糾正不需要反饋信道，特別適合只能提供單向信道場(chǎng)合自動(dòng)糾錯(cuò)，不要求檢錯(cuò)重發(fā)，延時(shí)小，實(shí)時(shí)性好糾錯(cuò)碼必須與信道的錯(cuò)誤特性密切配合若糾錯(cuò)較多，則編、譯碼設(shè)備復(fù)雜，傳輸效率低第20頁/共92頁第二十一頁，共92頁。（3）信息反饋校驗(yàn)）信息反饋校驗(yàn)(xio yn)法（法（IRQ） Information Repeat reQuest接收

11、端將接收到的信碼原封不動(dòng)地轉(zhuǎn)發(fā)回發(fā)端，并與原發(fā)送信(sn xn)碼相比較，若發(fā)現(xiàn)錯(cuò)誤，發(fā)端再重發(fā)。數(shù)據(jù)信息數(shù)據(jù)信息發(fā)收?qǐng)D圖11.1-6 信息反饋信息反饋法法數(shù)據(jù)信息數(shù)據(jù)信息第21頁/共92頁第二十二頁，共92頁。收端把收到的數(shù)據(jù)序列全部經(jīng)反向信道送回發(fā)端，發(fā)端比較發(fā)出和送回的數(shù)據(jù)序列，從而發(fā)現(xiàn)有否錯(cuò)誤，如果有錯(cuò)誤，發(fā)端將數(shù)據(jù)序列再次傳送，直到發(fā)端沒有發(fā)現(xiàn)錯(cuò)誤。不需要糾錯(cuò)、檢錯(cuò)的編、譯碼器，設(shè)備(shbi)簡單。需要和正向信道相同的反向信道，實(shí)時(shí)性差發(fā)端需要一定容量的存儲(chǔ)器以存儲(chǔ)發(fā)送碼組僅適應(yīng)于傳輸速率較低，信道差錯(cuò)率較低，具有雙向傳輸線路及控制簡單的系統(tǒng)第22頁/共92頁第二十三頁，共92頁。

12、（4）檢錯(cuò)刪除）檢錯(cuò)刪除(shnch)（ECD） Error Correction Deletion接收端發(fā)現(xiàn)錯(cuò)碼之后，立即將其刪除，不要求重發(fā)。適用在少數(shù)特定系統(tǒng)中，發(fā)送碼元中包含大量多余度，刪除部分接受碼元并不影響使用。設(shè)備復(fù)雜度低，不需要緩沖(hunchng)存儲(chǔ)裝置。第23頁/共92頁第二十四頁，共92頁。（5）混合）混合(hnh)糾錯(cuò)檢錯(cuò)（糾錯(cuò)檢錯(cuò)（HEC） Hybrid Error CorrectionFEC與ARQ的結(jié)合發(fā)端發(fā)出同時(shí)具有(jyu)檢錯(cuò)和糾錯(cuò)能力的碼，收端收到后，檢查錯(cuò)誤情況：如果錯(cuò)誤在糾錯(cuò)能力之內(nèi)，則自動(dòng)糾正；若超出糾錯(cuò)能力，但在檢錯(cuò)能力之內(nèi)，則經(jīng)反向信道要求重發(fā)

13、。在實(shí)時(shí)性和譯碼復(fù)雜性方面是FEC和ARQ的折衷。第24頁/共92頁第二十五頁，共92頁。發(fā)發(fā)收收能夠發(fā)現(xiàn)和糾正錯(cuò)誤的碼能夠發(fā)現(xiàn)和糾正錯(cuò)誤的碼圖圖11.1-7 混合糾錯(cuò)檢錯(cuò)（混合糾錯(cuò)檢錯(cuò)（HEC)應(yīng)答信號(hào)應(yīng)答信號(hào)第25頁/共92頁第二十六頁，共92頁。核心核心(hxn)問題問題v 發(fā)現(xiàn)錯(cuò)誤發(fā)現(xiàn)錯(cuò)誤v 糾正錯(cuò)誤糾正錯(cuò)誤第26頁/共92頁第二十七頁，共92頁。 在信息碼序列中加監(jiān)督碼就稱為差錯(cuò)控制編碼，也叫糾錯(cuò)編碼。不同的編碼方法，有不同的檢錯(cuò)和糾錯(cuò)能力，增加(zngji)監(jiān)督碼元越多，檢（糾）錯(cuò)能力越強(qiáng)。差錯(cuò)控制編碼原則上是降低傳輸效率來換取可靠性提高。（即誤碼率更?。?。 第27頁/共92頁第二

14、十八頁，共92頁。v理論依據(jù)：Shannon信道編碼定理。v定理指出：v 對(duì)于一給定的有干擾信道，若其信道容量為C，只要發(fā)送端以低于C的速率R發(fā)送信息，則一定存在一種編碼方法，使編碼錯(cuò)誤概率P隨著碼長n的增加，按指數(shù)(zhsh)下降到任意小的值。1、糾錯(cuò)、糾錯(cuò)(ji cu)編碼的理論依據(jù)編碼的理論依據(jù)11.2 11.2 差錯(cuò)控制編碼差錯(cuò)控制編碼(bin m)(bin m)的的基本原理基本原理第28頁/共92頁第二十九頁，共92頁。2、糾錯(cuò)編碼的基本、糾錯(cuò)編碼的基本(jbn)思想思想v 發(fā)送端按照某種規(guī)則在信息序列(xli)上附加監(jiān)督碼元，接收端則按照同一規(guī)則檢查兩者間關(guān)系v 以犧牲通信的有效性

15、（信息傳輸速率）來提高可靠性v 碼的檢錯(cuò)和糾錯(cuò)能力是用信息量的冗余來換取的。一般說來，添加的冗余越多，碼的檢錯(cuò)、糾錯(cuò)能力越強(qiáng)，但信道的傳輸效率下降也越多。第29頁/共92頁第三十頁，共92頁。3、碼距與檢錯(cuò)和糾錯(cuò)能力、碼距與檢錯(cuò)和糾錯(cuò)能力(nngl)的關(guān)系的關(guān)系niii 1dAB （1）幾個(gè)概念）幾個(gè)概念第30頁/共92頁第三十一頁，共92頁。v 最小碼距：在一個(gè)碼字集合中，任意兩個(gè)碼字間距離的最小值，即碼字集合中任意兩元素間的最小距離，記為dmin或d0v 碼重：碼字中非零碼元的數(shù)目(shm)定義為該碼字的重量，簡稱碼重。如“10011”碼字的碼重為3。糾錯(cuò)碼的抗干擾能力完全取決于許用碼字之

16、間的距離糾錯(cuò)碼的抗干擾能力完全取決于許用碼字之間的距離(jl)(jl)，碼的最小距離，碼的最小距離(jl)(jl)越大，說明碼字間的最越大，說明碼字間的最小差別越大，抗干擾能力就越強(qiáng)。小差別越大，抗干擾能力就越強(qiáng)。11.2 11.2 差錯(cuò)控制編碼差錯(cuò)控制編碼(bin m)(bin m)的基的基本原理本原理第31頁/共92頁第三十二頁，共92頁。舉例說明：假如要傳送舉例說明：假如要傳送A、B兩個(gè)兩個(gè)(lin )消息消息編碼一：消息A-“0”；消息B-“1”最小碼距1若傳輸中產(chǎn)生(chnshng)錯(cuò)碼（“0”錯(cuò)成“1”或“1”錯(cuò)成“0”）收端無法發(fā)現(xiàn)，該編碼無檢錯(cuò)糾錯(cuò)能力。11.2 11.2 差錯(cuò)

17、控制編碼差錯(cuò)控制編碼(bin m)(bin m)的的基本原理基本原理第32頁/共92頁第三十三頁，共92頁。編碼(bin m)二：消息A-“00”；消息B-“11”最小碼距2若傳輸中產(chǎn)生一位錯(cuò)碼，則變成“01”或“10”，收端判決為有錯(cuò)（因“01”“10”為禁用碼組），但無法確定錯(cuò)碼位置，不能糾正，該編碼(bin m)具有檢出一位錯(cuò)碼的能力。這表明增加一位冗余碼元后碼具有檢出一位錯(cuò)碼的能力11.2 11.2 差錯(cuò)控制編碼差錯(cuò)控制編碼(bin m)(bin m)的基的基本原理本原理第33頁/共92頁第三十四頁，共92頁。編碼三：消息A-“000”；消息B-“111”最小碼距3傳輸中產(chǎn)生一位甚至兩

18、位錯(cuò)碼，都將變成禁用碼組，收端判決(pnju)傳輸有錯(cuò)。該編碼具有檢出兩位錯(cuò)碼的能力。在產(chǎn)生一位錯(cuò)碼（錯(cuò)1位概率遠(yuǎn)遠(yuǎn)大于錯(cuò)2位、3位概率）情況下，收端可根據(jù)“最大似然”法則進(jìn)行正確判決(pnju)，能夠糾正這一位錯(cuò)碼。該編碼具有糾正一位錯(cuò)碼的能力。例如收到110，認(rèn)為是111。這表明增加兩位冗余碼元后碼具有檢出兩位錯(cuò)碼及糾正一位錯(cuò)碼的能力。第34頁/共92頁第三十五頁，共92頁。（2）最小碼距與檢錯(cuò)和糾錯(cuò)）最小碼距與檢錯(cuò)和糾錯(cuò)(ji cu)能力的關(guān)能力的關(guān)系系第35頁/共92頁第三十六頁，共92頁。(a) 檢檢e個(gè)錯(cuò)個(gè)錯(cuò)圖圖11.2-2(a) 碼距與檢錯(cuò)糾錯(cuò)碼距與檢錯(cuò)糾錯(cuò)(ji cu)能力的能

19、力的關(guān)系關(guān)系A(chǔ)e1dminBA、B都為許用碼；都為許用碼；A發(fā)生發(fā)生e個(gè)錯(cuò)；個(gè)錯(cuò)；B不能靠在球面不能靠在球面(qimin)上，否則上，否則收到收到B無法判斷是無法判斷是否為錯(cuò)碼；否為錯(cuò)碼；dmine+1第36頁/共92頁第三十七頁，共92頁。1tABtdmin(b)糾正糾正(jizhng)t個(gè)錯(cuò)個(gè)錯(cuò)碼碼圖圖11.2-2(b) 碼距與檢錯(cuò)糾錯(cuò)能力碼距與檢錯(cuò)糾錯(cuò)能力(nngl)的關(guān)系的關(guān)系A(chǔ)、B都為許用碼；都為許用碼；A、B都發(fā)生都發(fā)生(fshng)t個(gè)個(gè)錯(cuò)；錯(cuò)；dmin2t+1第37頁/共92頁第三十八頁，共92頁。ABtedmint(c)糾正糾正(jizhng)t個(gè)錯(cuò)碼，檢測(cè)個(gè)錯(cuò)碼，檢測(cè)e個(gè)個(gè)

20、錯(cuò)碼錯(cuò)碼圖圖11.2-2(c) 碼距與檢錯(cuò)糾錯(cuò)能力碼距與檢錯(cuò)糾錯(cuò)能力(nngl)的關(guān)的關(guān)系系A(chǔ)、B都為許用碼；都為許用碼；A發(fā)生發(fā)生(fshng)e個(gè)錯(cuò)；個(gè)錯(cuò)；B發(fā)生發(fā)生(fshng)t個(gè)錯(cuò)；個(gè)錯(cuò)； dmine+t+1第38頁/共92頁第三十九頁，共92頁。假設(shè)隨機(jī)(su j)信道中發(fā)送“0”碼與發(fā)送“1”碼傳錯(cuò)概率相等都為P,且P1,則在碼長為n的碼組中發(fā)生r個(gè)錯(cuò)誤的概率為：rrn rrnnn!P (r)C p (1p)pr!(nr)! 137267397P (1)7p7107P (2)p21102 57P (3)p35103 4 ！4、誤碼率、誤碼率大概率大概率(gil)事件事件第39頁/

21、共92頁第四十頁，共92頁。5、編碼、編碼(bin m)效率效率第40頁/共92頁第四十一頁，共92頁。 第41頁/共92頁第四十二頁，共92頁。1 2 3kk 1123kk 1k 1123k123kk 1k 1123kkaa a .ar1aaaa .aa0aaaa .aaaa .aa1aaaa .a1 對(duì)對(duì) 位位碼碼元元校校驗(yàn)驗(yàn)位位偶偶校校驗(yàn)驗(yàn) 奇奇校校驗(yàn)驗(yàn) 11.3 11.3 常用常用(chn yn)(chn yn)的簡單的簡單編碼編碼 奇偶監(jiān)督碼：在信息碼元后附加(fji)一位監(jiān)督位，使得碼組中奇偶監(jiān)督碼“1”的個(gè)數(shù)為偶數(shù)或奇數(shù)。第42頁/共92頁第四十三頁，共92頁。v 最小碼距dmi

22、n=2v 只能檢測(cè)出單個(gè)或奇數(shù)個(gè)錯(cuò)誤(cuw)，不能糾錯(cuò)v 應(yīng)用：以隨機(jī)錯(cuò)誤(cuw)為主的計(jì)算機(jī)通信系統(tǒng)，難于對(duì)付突發(fā)錯(cuò)誤(cuw)v 編碼效率=k/n=k/(k+1)11.3 11.3 常用的簡單常用的簡單(jindn)(jindn)編編碼碼 第43頁/共92頁第四十四頁，共92頁。11.3 11.3 常用常用(chn yn)(chn yn)的簡單的簡單編碼編碼 第44頁/共92頁第四十五頁，共92頁。46v 能夠發(fā)現(xiàn)某行、某列上所有奇數(shù)個(gè)錯(cuò)誤(cuw)以及突發(fā)長度不大于方陣行數(shù)或列數(shù)的突發(fā)錯(cuò)誤(cuw)；v 有可能檢測(cè)出偶數(shù)個(gè)錯(cuò)誤(cuw)（在行上檢測(cè)不出，但有可能在列上檢測(cè)出），但當(dāng)偶

23、數(shù)個(gè)錯(cuò)誤(cuw)剛好構(gòu)成矩形時(shí)，則檢測(cè)不出v 可糾正一些錯(cuò)誤(cuw)mn(m1)(n1) 編編碼碼效效率率信信息息碼碼元元共共m m行行n n列列v 11.3 11.3 常用常用(chn yn)(chn yn)的簡單的簡單編碼編碼 第45頁/共92頁第四十六頁，共92頁。信 息 碼 元監(jiān)督碼元1110000000111010011010100001110110001000010011001110111監(jiān)督碼元01101010011表表11-3 水平垂直奇偶水平垂直奇偶(q u)監(jiān)督監(jiān)督碼碼發(fā)送(f sn)順序第46頁/共92頁第四十七頁，共92頁。表表11-4 水平水平(shupng)垂直

24、奇偶監(jiān)督碼接收端垂直奇偶監(jiān)督碼接收端糾錯(cuò)示例糾錯(cuò)示例信 息 碼 元監(jiān)督碼元1110000000111010011010100001110110001000010011001110111監(jiān)督碼元01101010011011例如：當(dāng)碼組中僅在一行有奇數(shù)個(gè)錯(cuò)誤例如：當(dāng)碼組中僅在一行有奇數(shù)個(gè)錯(cuò)誤(cuw)時(shí)時(shí)，能夠確定錯(cuò)誤，能夠確定錯(cuò)誤(cuw)位置，并糾正它。位置，并糾正它。第47頁/共92頁第四十八頁，共92頁。表表11-5 水平水平(shupng)垂直奇偶監(jiān)督碼接收端檢錯(cuò)示垂直奇偶監(jiān)督碼接收端檢錯(cuò)示例例信 息 碼 元監(jiān)督碼元111000000011101001101010000111011000

25、1000010011001110111監(jiān)督碼元01101010011011構(gòu)成矩形構(gòu)成矩形(jxng)的偶數(shù)個(gè)誤碼檢測(cè)不出。的偶數(shù)個(gè)誤碼檢測(cè)不出。00第48頁/共92頁第四十九頁，共92頁。表表11-6 水平垂直奇偶監(jiān)督水平垂直奇偶監(jiān)督(jind)碼接收端檢錯(cuò)碼接收端檢錯(cuò)示例示例信 息 碼 元監(jiān)督碼元1110000000111010011010100001110110001000010011001110111監(jiān)督碼元0110101001101有可能檢測(cè)有可能檢測(cè)(jin c)出偶數(shù)個(gè)誤碼。出偶數(shù)個(gè)誤碼。001第49頁/共92頁第五十頁，共92頁。5111.3 11.3 常用常用(chn yn)

26、(chn yn)的簡的簡單編碼單編碼 第50頁/共92頁第五十一頁，共92頁。表表11-7 保護(hù)保護(hù)(boh)電碼電碼（是一種（是一種(y zhn)五中五中取三碼）取三碼）數(shù)字?jǐn)?shù)字電碼電碼數(shù)字?jǐn)?shù)字電碼電碼00 1 1 0 150 0 1 1 110 1 0 1 161 0 1 0 121 1 0 0 171 1 1 0 031 0 1 1 080 1 1 1 041 1 0 1 091 0 0 1 1第51頁/共92頁第五十二頁，共92頁。11.3 11.3 常用常用(chn yn)(chn yn)的簡單的簡單編碼編碼 第52頁/共92頁第五十三頁，共92頁。v 碼組中信息(xnx)位有奇數(shù)個(gè)

27、“1”，監(jiān)督碼元與信息(xnx)碼元相同；v 碼組中信息(xnx)位有偶數(shù)個(gè)“1”，監(jiān)督碼元與信息(xnx)碼元相反。11.3 11.3 常用的簡單常用的簡單(jindn)(jindn)編碼編碼 （1）正反碼編碼）正反碼編碼(bin m)規(guī)則規(guī)則第53頁/共92頁第五十四頁，共92頁。11.3 11.3 常用的簡單常用的簡單(jindn)(jindn)編編碼碼 （2）接收端解碼）接收端解碼(jim)規(guī)則規(guī)則第54頁/共92頁第五十五頁，共92頁。校驗(yàn)碼組組成校驗(yàn)碼組組成誤碼情況誤碼情況全為全為0無誤碼無誤碼4個(gè)個(gè)“1”，1個(gè)個(gè)“0”信息碼有一個(gè)錯(cuò)碼，位置對(duì)應(yīng)信息碼有一個(gè)錯(cuò)碼，位置對(duì)應(yīng)校驗(yàn)碼組中

28、校驗(yàn)碼組中“0”的位置的位置1個(gè)個(gè)“1”，4個(gè)個(gè)“0”監(jiān)督碼有一個(gè)錯(cuò)碼，位置對(duì)應(yīng)監(jiān)督碼有一個(gè)錯(cuò)碼，位置對(duì)應(yīng)校驗(yàn)碼組中校驗(yàn)碼組中“1”的位置的位置其它其它錯(cuò)碼多于錯(cuò)碼多于1個(gè)個(gè)表表11-8 正反碼檢錯(cuò)糾錯(cuò)判決正反碼檢錯(cuò)糾錯(cuò)判決(pnju)規(guī)則規(guī)則第55頁/共92頁第五十六頁，共92頁。57例例11-1 假設(shè)發(fā)送假設(shè)發(fā)送(f sn)碼組為碼組為1100111001，分析，分析各種正反碼判決糾錯(cuò)情況。各種正反碼判決糾錯(cuò)情況。 11.3 11.3 常用的簡單常用的簡單(jindn)(jindn)編編碼碼 第56頁/共92頁第五十七頁，共92頁。碼長為碼長為10的正反碼能夠糾正的正反碼能夠糾正1位差錯(cuò)位

29、差錯(cuò)(chcu)，并能檢測(cè)所有，并能檢測(cè)所有2位及以下的錯(cuò)碼。位及以下的錯(cuò)碼。第57頁/共92頁第五十八頁，共92頁。5、ISBN國際圖書統(tǒng)一國際圖書統(tǒng)一(tngy)編號(hào)編號(hào)International Standard Book NumberISBN 7-118-02481-3中中國國出出版版公公司司書書名名編編號(hào)號(hào)校校驗(yàn)驗(yàn)位位無誤(ww)碼，若不能被11整除，有誤碼11.3 11.3 常用的簡單常用的簡單(jindn)(jindn)編編碼碼 第58頁/共92頁第五十九頁，共92頁。 7 1 1 8 0 2 4 8 1 37*10+1*9+1*8+8*7+0*6+2*5+4*4+8*3+1*2

30、+3*1= 198（模（模11）=011.3 11.3 常用常用(chn yn)(chn yn)的簡的簡單編碼單編碼 能被11整除(zhngch)，無誤碼。第59頁/共92頁第六十頁，共92頁。5、ISBN國際圖書國際圖書(tsh)統(tǒng)一編號(hào)統(tǒng)一編號(hào)International Standard Book Number11.3 11.3 常用常用(chn yn)(chn yn)的簡單的簡單編碼編碼 早期早期(zoq)的的ISBN號(hào)由號(hào)由10位十進(jìn)制數(shù)字組成，位十進(jìn)制數(shù)字組成，2007年起全世年起全世界的界的ISBN號(hào)統(tǒng)一升級(jí)為號(hào)統(tǒng)一升級(jí)為13位，簡稱位，簡稱“ISBN-13”。 ISBN-13的編

31、碼結(jié)構(gòu)組成 第60頁/共92頁第六十一頁，共92頁。11.3 11.3 常用常用(chn yn)(chn yn)的簡的簡單編碼單編碼 每個(gè)每個(gè)ISBN號(hào)碼的前號(hào)碼的前12位與最后一位校驗(yàn)位之間有通過固定位與最后一位校驗(yàn)位之間有通過固定(gdng)算法形成的約束關(guān)系。若它們之間不滿足這個(gè)約束關(guān)系，則該算法形成的約束關(guān)系。若它們之間不滿足這個(gè)約束關(guān)系，則該ISBN號(hào)號(hào)碼對(duì)應(yīng)的圖書必為非法出版物。校驗(yàn)位的具體算法包括：碼對(duì)應(yīng)的圖書必為非法出版物。校驗(yàn)位的具體算法包括： 9 7 8 7 3 0 2 1 3 2 3 1(1) 1 3 1 3 1 3 1 3 1 3 1 3(2) 9+ 21+ 8+21+

32、 3 + 0 + 2 + 3 +3 + 6 + 3 + 3 = 82(3) MOD10=2(4) 10-2=8第61頁/共92頁第六十二頁，共92頁。v1、基本概念基本概念第62頁/共92頁第六十三頁，共92頁。第63頁/共92頁第六十四頁，共92頁。2、線性分組碼的性質(zhì)、線性分組碼的性質(zhì)(xngzh)v任意兩個(gè)許用碼組之和（逐位模2和）仍為一許用碼組，即具有封閉性。v最小碼距=非零碼的最小碼重（1的個(gè)數(shù)）。v有零碼（信息(xnx)碼元和監(jiān)督碼元均為零的碼組）11.4 11.4 線性分組碼線性分組碼第64頁/共92頁第六十五頁，共92頁。11.4 11.4 線性分組碼線性分組碼第65頁/共92

33、頁第六十六頁，共92頁。系式，S稱為校正子/校驗(yàn)子/伴隨式11.4 11.4 線性分組碼線性分組碼第66頁/共92頁第六十七頁，共92頁?？梢?ky)這樣來考慮11.4 11.4 線性分組碼線性分組碼第67頁/共92頁第六十八頁，共92頁。構(gòu)造構(gòu)造(guzo)一（一（n，k)分組碼，分組碼，k=4并能糾正一位并能糾正一位錯(cuò)碼錯(cuò)碼(2) 漢明碼的構(gòu)造漢明碼的構(gòu)造(guzo)11.4 11.4 線性分組碼線性分組碼第68頁/共92頁第六十九頁，共92頁。S1S2S3錯(cuò)碼位置錯(cuò)碼位置S1S2S3錯(cuò)碼位置錯(cuò)碼位置000無錯(cuò)無錯(cuò)011a3001a0101a4010a1110a5100a2111a6表表1

34、1-9 S1S2S3的八種組合與一位錯(cuò)碼的對(duì)應(yīng)的八種組合與一位錯(cuò)碼的對(duì)應(yīng)(duyng)關(guān)系關(guān)系11.4 11.4 線性分組碼線性分組碼第69頁/共92頁第七十頁，共92頁。S1S2S3錯(cuò)碼位置錯(cuò)碼位置0 0 0無錯(cuò)碼無錯(cuò)碼0 0 1a00 1 0a11 0 0a20 1 1a31 0 1a41 1 0a51 1 1a6信息碼信息碼監(jiān)督碼監(jiān)督碼a6 a5a4 a3a2 a1 a0FS1= a2+a4+a5+a6FS2= a1+a3+a5+a6FS3= a0+a3+a4+a6(11.4-3)監(jiān)督監(jiān)督(jind)方程方程:第70頁/共92頁第七十一頁，共92頁。（3）發(fā)端編碼）發(fā)端編碼(bin m)

35、的的原則：原則：v 信息碼元a6 、a5 、a4、a3來源于待編碼的信息序列；v 監(jiān)督碼元 a2 、a1、 a0的取值應(yīng)根據(jù)信息碼元按監(jiān)督關(guān)系式來決定(judng)，即使前面三式中的S1、 S2 、S3均為0：11.4 11.4 線性分組碼線性分組碼第71頁/共92頁第七十二頁，共92頁。Fa2 = a4+a5+a6Fa1 = a3+a5+a6Fa0 = a3+a4+a6v 給定信息位后，根據(jù)上式算出各監(jiān)督位，該編碼(bin m)的所有碼組如表11-10：(11.4-4)Fa6+a5+a4+a2=0Fa6+a5+a3+a1=0Fa6+a4+a3+a0=0(11.4-5)11.4 11.4 線性

36、分組碼線性分組碼第72頁/共92頁第七十三頁，共92頁。信息位信息位 監(jiān)督位監(jiān)督位 信息位信息位 監(jiān)督位監(jiān)督位a6a5a4a3a2a1a0a6a5a4a3a2a1a00000000100011100010111001100001010110100100011110101100101001101100001010110111010100110011111010001110001111111表表11-10 （7，4）漢明編碼）漢明編碼(bin m)的許用碼的許用碼組組第73頁/共92頁第七十四頁，共92頁。11.4 11.4 線性分組碼線性分組碼第74頁/共92頁第七十五頁，共92頁。000100

37、1101010101100101110123456aaaaaaa(11.4-6)11.4 11.4 線性分組碼線性分組碼第75頁/共92頁第七十六頁，共92頁。H稱為線性碼監(jiān)督(jind)矩陣可化簡為： HAT=0T 或AHT=0 6543210Aa a a a a a aO0 0 0 r1110100H11010101011001P I 11.4 11.4 線性分組碼線性分組碼第76頁/共92頁第七十七頁，共92頁。v rn階矩陣v 監(jiān)督矩陣H確定了編碼時(shí)監(jiān)督碼元與信息碼元的關(guān)系v 把具有PIr形式的H矩陣稱為典型(dinxng)形式的監(jiān)督矩陣，其中P為r k階矩陣, Ir為r r階單位方陣

38、v H矩陣的各行應(yīng)線性無關(guān)。矩陣若能寫成典型(dinxng)形式，則其各行一定線性無關(guān)監(jiān)督矩陣(j zhn)H特點(diǎn)11.4 11.4 線性分組碼線性分組碼第77頁/共92頁第七十八頁，共92頁。62514036543aa1110aa1101aa1011aaaPaa (5) 生成生成(shn chn)矩矩陣陣（11.4-5）式也可寫成矩陣(j zhn)形式，即(11.4-7)11.4 11.4 線性分組碼線性分組碼第78頁/共92頁第七十九頁，共92頁。 QaaaaPaaaaaaaaaaaT345634563456012110101011111或?qū)懗?1.4 11.4 線性分組碼線性分組碼第79頁/共92頁第八十頁，共92頁。生成矩陣G：在Q矩陣的左邊(zu bian)加上一個(gè)k k階矩陣，即 Tkk10001110100110GI QI P00101010001011 生生成成矩矩陣陣 6543AaaaaG 11.4 11.4 線性分組碼線性分組碼第80頁/共92頁第八十一頁，共92頁。行均為許用碼組生成矩陣(j zhn)G特點(diǎn)11.4 1