通信原理第11章差錯控制編碼課件

1、第第1111章章 差錯控制編碼差錯控制編碼11.1 概述概述11.2 糾錯編碼的基本原理糾錯編碼的基本原理11.3 常用的簡單編碼常用的簡單編碼11.4 線性分組碼線性分組碼第11章 差錯控制編碼0 、復習、復習v 模擬信源：在無線廣播中，信源一般是一個語音源（話音或音樂）；在電視廣播中，信源主要是活動圖像的視頻信號源。這些信源的輸出都是模擬信號，所以稱之為模擬源。v 信源編碼：將模擬信息源的輸出轉化為數(shù)字信號，即A/D轉換。v 信源編碼目的：提高通信有效性，減少原消息的冗余度。第11章 差錯控制編碼差錯出現(xiàn)原因v 外界噪聲v 傳輸中碼間串擾解決方法v 合理地設計基帶信號，選擇調(diào)制、解調(diào)方式，

2、采用均衡技術，發(fā)送功率等因素，使誤比特率降低。v 差錯控制措施。信號在數(shù)字信道傳輸過程中受到干擾的影響，使信號波形變壞，發(fā)生誤碼，可以采用一些方法解決。第11章 差錯控制編碼 差錯控制編碼屬信道編碼，要求在滿足有效性前提下，盡可能提高數(shù)字通信的可靠性。 差錯控制編碼是在信息序列上附加上一些監(jiān)督碼元，利用這些冗余的碼元，使原來不規(guī)律的或規(guī)律性不強的原始數(shù)字信號變?yōu)橛幸?guī)律的數(shù)字信號。例如奇偶校驗。 差錯控制譯碼則利用這些規(guī)律性來鑒別傳輸過程是否發(fā)生錯誤，或進而糾正錯誤。第11章 差錯控制編碼1、差錯控制編碼分類、差錯控制編碼分類第11章 差錯控制編碼2、誤碼類型、誤碼類型v 隨機誤碼v 突發(fā)誤碼錯

3、碼出現(xiàn)是隨機的、錯碼之間統(tǒng)計獨立。由隨機噪聲引起存在隨機誤碼的信道稱為隨機信道無記憶信道差錯在短時間成串出現(xiàn)，而在其間又存在較長的無差錯區(qū)間，且差錯之間相關例如：脈沖噪聲，存儲系統(tǒng)中磁帶的缺陷或讀寫頭接觸不良引起，再例如用手機過涵洞，且無發(fā)射天線存在這種差錯的信道稱為突發(fā)信道有記憶信道3、錯誤圖樣、錯誤圖樣l例如：設發(fā)送數(shù)據(jù)序列為：111111111接收數(shù)據(jù)序列為： 111001001錯誤圖樣（差錯序列）：發(fā)送數(shù)據(jù)序列與接收序列對應碼位的模和則差錯序列為： 0000000110110l可見發(fā)生了兩個長度分別為和的突發(fā)差錯，其錯誤圖樣分別為和11011突發(fā)長度：指突發(fā)差錯首位與末位之間的長度（中

4、間可能有沒錯的碼位）第11章 差錯控制編碼l說明差錯序列或錯誤圖樣中的“”表示對應碼位沒錯，而“”表示有錯實際信道很復雜，所出現(xiàn)的差錯并不是單一的，往往是隨機和突發(fā)差錯并存，只不過以某種錯誤為主一般說來，糾正隨機差錯的編譯碼方法和設備比較簡單，成本較低，效果較顯著；而糾正突發(fā)差錯的編譯碼方法和設備比較復雜，成本較高，效果也不如前者顯著第11章 差錯控制編碼 4、信道類型、信道類型v 隨機信道v 突發(fā)信道v 混合信道第11章 差錯控制編碼5、差錯控制方法、差錯控制方法v檢錯重發(fā)（ARQ） 停發(fā)等候重發(fā) 返回重發(fā) 選擇重發(fā)v前向糾錯（FEC）v反饋校驗（IRQ）v檢錯刪除 （ECD）v混合方式（H

5、EC）第11章 差錯控制編碼（1）檢錯重發(fā)法（）檢錯重發(fā)法（ARQ） Automatic Repeat reQuest 收端在接收到的信碼中發(fā)現(xiàn)錯碼時，就通知發(fā)端重發(fā)，直到正確接收為止。例如奇偶校驗。 檢錯重發(fā)方式只用于檢測誤碼，能夠在接收單元中發(fā)現(xiàn)錯誤，但不一定知道該錯誤碼的具體位置。 需具備雙向信道。發(fā)發(fā)收收能夠發(fā)現(xiàn)錯誤的碼能夠發(fā)現(xiàn)錯誤的碼圖圖11.1-1（a) 檢錯重發(fā)（檢錯重發(fā)（ARQ)應答信號應答信號圖圖11.1-1（b) 檢錯重發(fā)（檢錯重發(fā)（ARQ)信信源源編碼器和緩編碼器和緩沖存儲器沖存儲器重發(fā)控制重發(fā)控制雙雙向向信信道道解碼器解碼器指令產(chǎn)生器指令產(chǎn)生器輸出緩沖輸出緩沖存儲器存儲

6、器收收信信者者正確時輸出錯誤時刪除判斷有無錯誤第11章 差錯控制編碼 停發(fā)等候重發(fā)停發(fā)等候重發(fā)2發(fā)送端：接收端：133123ACKACKNAK發(fā)現(xiàn)錯誤TITw停頓時間圖圖11.1-2 停發(fā)等候重發(fā)停發(fā)等候重發(fā)第11章 差錯控制編碼發(fā)端在Tw時間內(nèi)送出一個碼組；收端收到后檢查。如果未發(fā)現(xiàn)錯誤，則發(fā)回一個認可信號（ACK）給發(fā)送端，發(fā)送端收到ACK信號再發(fā)下一個碼組若檢測到錯誤，則發(fā)回一個否認信號（NAK），發(fā)送端收到NAK信號后重發(fā)前一碼組，并再次等候ACK信號或NAK信號發(fā)送兩個碼組之間有停頓時間TI，影響了傳輸效率第11章 差錯控制編碼 返回重發(fā)返回重發(fā)(拉回重發(fā)拉回重發(fā))其發(fā)送端不停地送出

7、一個個連續(xù)碼組，不再等候收端返回的ACK信號一旦收端發(fā)現(xiàn)錯誤并返回NAK信號，則發(fā)端從下一碼組開始重發(fā)前面的N個碼組N的大小取決于信號傳遞及處理所帶來的延時第11章 差錯控制編碼發(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)錯誤NAK從碼組2開始重發(fā)圖圖11.1-3 返回重發(fā)返回重發(fā)第11章 差錯控制編碼 選擇重發(fā)選擇重發(fā)也是連續(xù)不斷地發(fā)送碼組，收端檢測到錯誤后發(fā)回NAK信號。與返回重發(fā)不同的是，發(fā)端并不重發(fā)錯誤碼組后的所有碼組，而只重發(fā)有錯的那個碼組第11章 差錯控制編碼發(fā)送端：接收端：1 2 3 4 5 6 2

8、7 81 2 3 4 5 6 2 7 899發(fā)現(xiàn)錯誤NAK重發(fā)碼組2圖圖11.1-4 選擇重發(fā)選擇重發(fā)第11章 差錯控制編碼三者比較 選擇重發(fā)傳輸效率最高，但成本最貴：控制機制復雜，發(fā)端和收端都要有數(shù)據(jù)緩沖器； 返回重發(fā)、選擇重發(fā)需要全雙工數(shù)據(jù)鏈路，而停發(fā)等候重發(fā)只要求半雙工的數(shù)據(jù)鏈路。第11章 差錯控制編碼（2）前向糾錯法（）前向糾錯法（FEC） Forward Error Correction發(fā)發(fā)收收能夠糾正錯誤的碼能夠糾正錯誤的碼圖圖11.1-5 前向糾錯（前向糾錯（FEC)信信源源編編碼碼器器單單向向信信道道糾錯譯碼器糾錯譯碼器輸出緩沖輸出緩沖存儲器存儲器收收信信者者+第11章 差錯控

9、制編碼發(fā)送端將信息序列編碼成能夠糾正錯誤的碼，接收端根據(jù)編碼規(guī)則進行檢查，如果有錯自動糾正不需要反饋信道，特別適合只能提供單向信道場合自動糾錯，不要求檢錯重發(fā)，延時小，實時性好糾錯碼必須與信道的錯誤特性密切配合若糾錯較多，則編、譯碼設備復雜，傳輸效率低第11章 差錯控制編碼（3）信息反饋校驗法（）信息反饋校驗法（IRQ） Information Repeat reQuest接收端將接收到的信碼原封不動地轉發(fā)回發(fā)端，并與原發(fā)送信碼相比較，若發(fā)現(xiàn)錯誤，發(fā)端再重發(fā)。數(shù)據(jù)信息數(shù)據(jù)信息發(fā)收圖圖11.1-6 信息反饋法信息反饋法數(shù)據(jù)信息數(shù)據(jù)信息第11章 差錯控制編碼收端把收到的數(shù)據(jù)序列全部經(jīng)反向信道送回發(fā)

10、端，發(fā)端比較發(fā)出和送回的數(shù)據(jù)序列，從而發(fā)現(xiàn)有否錯誤，如果有錯誤，發(fā)端將數(shù)據(jù)序列再次傳送，直到發(fā)端沒有發(fā)現(xiàn)錯誤。不需要糾錯、檢錯的編、譯碼器，設備簡單。需要和正向信道相同的反向信道，實時性差發(fā)端需要一定容量的存儲器以存儲發(fā)送碼組僅適應于傳輸速率較低，信道差錯率較低，具有雙向傳輸線路及控制簡單的系統(tǒng)第11章 差錯控制編碼（4）檢錯刪除（）檢錯刪除（ECD） Error Correction Deletion接收端發(fā)現(xiàn)錯碼之后，立即將其刪除，不要求重發(fā)。適用在少數(shù)特定系統(tǒng)中，發(fā)送碼元中包含大量多余度，刪除部分接受碼元并不影響使用。設備復雜度低，不需要緩沖存儲裝置。第11章 差錯控制編碼（5）混合糾錯

11、檢錯（）混合糾錯檢錯（HEC） Hybrid Error CorrectionFEC與ARQ的結合發(fā)端發(fā)出同時具有檢錯和糾錯能力的碼，收端收到后，檢查錯誤情況：如果錯誤在糾錯能力之內(nèi)，則自動糾正；若超出糾錯能力，但在檢錯能力之內(nèi)，則經(jīng)反向信道要求重發(fā)。在實時性和譯碼復雜性方面是FEC和ARQ的折衷。第11章 差錯控制編碼發(fā)發(fā)收收能夠發(fā)現(xiàn)和糾正錯誤的碼能夠發(fā)現(xiàn)和糾正錯誤的碼圖圖11.1-7 混合糾錯檢錯（混合糾錯檢錯（HEC)應答信號應答信號第11章 差錯控制編碼核心問題核心問題v 發(fā)現(xiàn)錯誤發(fā)現(xiàn)錯誤v 糾正錯誤糾正錯誤第11章 差錯控制編碼11.2 11.2 差錯控制編碼的基本原理差錯控制編碼的

12、基本原理 在信息碼序列中加監(jiān)督碼就稱為差錯控制編碼，也叫糾錯編碼。不同的編碼方法，有不同的檢錯和糾錯能力，增加監(jiān)督碼元越多，檢（糾）錯能力越強。差錯控制編碼原則上是降低傳輸效率來換取可靠性提高。（即誤碼率更?。?。 第11章 差錯控制編碼v理論依據(jù)：Shannon信道編碼定理。v定理指出： 對于一給定的有干擾信道，若其信道容量為C，只要發(fā)送端以低于C的速率R發(fā)送信息，則一定存在一種編碼方法，使編碼錯誤概率P隨著碼長n的增加，按指數(shù)下降到任意小的值。1、糾錯編碼的理論依據(jù)、糾錯編碼的理論依據(jù)11.2 11.2 差錯控制編碼的基本原理差錯控制編碼的基本原理第11章 差錯控制編碼2、糾錯編碼的基本思想

13、、糾錯編碼的基本思想11.2 11.2 差錯控制編碼的基本原理差錯控制編碼的基本原理v 發(fā)送端按照某種規(guī)則在信息序列上附加監(jiān)督碼元，接收端則按照同一規(guī)則檢查兩者間關系v 以犧牲通信的有效性（信息傳輸速率）來提高可靠性v 碼的檢錯和糾錯能力是用信息量的冗余來換取的。一般說來，添加的冗余越多，碼的檢錯、糾錯能力越強，但信道的傳輸效率下降也越多。第11章 差錯控制編碼v 碼長：碼字中碼元的數(shù)目。v 碼距：兩個等長碼字中對應碼位上不同二進制碼元的位數(shù)定義兩碼字的距離，簡稱碼距（d）。對于二進制稱作這兩個碼字的漢明距離。如兩碼字“10011”與“11010”間碼距為2。3、碼距與檢錯和糾錯能力的關系、碼

14、距與檢錯和糾錯能力的關系niii 1dAB 11.2 11.2 差錯控制編碼的基本原理差錯控制編碼的基本原理（1）幾個概念）幾個概念第11章 差錯控制編碼v 最小碼距：在一個碼字集合中，任意兩個碼字間距離的最小值，即碼字集合中任意兩元素間的最小距離，記為dmin或d0v 碼重：碼字中非零碼元的數(shù)目定義為該碼字的重量，簡稱碼重。如“10011”碼字的碼重為3。糾錯碼的抗干擾能力完全取決于許用碼字之間的距糾錯碼的抗干擾能力完全取決于許用碼字之間的距離，碼的最小距離越大，說明碼字間的最小差別越離，碼的最小距離越大，說明碼字間的最小差別越大，抗干擾能力就越強。大，抗干擾能力就越強。11.2 11.2

15、差錯控制編碼的基本原理差錯控制編碼的基本原理第11章 差錯控制編碼舉例說明：假如要傳送舉例說明：假如要傳送A、B兩個消息兩個消息編碼一：消息A-“0”；消息B-“1”最小碼距1若傳輸中產(chǎn)生錯碼（“0”錯成“1”或“1”錯成“0”）收端無法發(fā)現(xiàn)，該編碼無檢錯糾錯能力。11.2 11.2 差錯控制編碼的基本原理差錯控制編碼的基本原理第11章 差錯控制編碼編碼二：消息A-“00”；消息B-“11”最小碼距2若傳輸中產(chǎn)生一位錯碼，則變成“01”或“10”，收端判決為有錯（因“01”“10”為禁用碼組），但無法確定錯碼位置，不能糾正，該編碼具有檢出一位錯碼的能力。這表明增加一位冗余碼元后碼具有檢出一位錯

16、碼的能力11.2 11.2 差錯控制編碼的基本原理差錯控制編碼的基本原理編碼三：消息A-“000”；消息B-“111”最小碼距3傳輸中產(chǎn)生一位甚至兩位錯碼，都將變成禁用碼組，收端判決傳輸有錯。該編碼具有檢出兩位錯碼的能力。在產(chǎn)生一位錯碼（錯1位概率遠遠大于錯2位、3位概率）情況下，收端可根據(jù)“最大似然”法則進行正確判決，能夠糾正這一位錯碼。該編碼具有糾正一位錯碼的能力。例如收到110，認為是111。這表明增加兩位冗余碼元后碼具有檢出兩位錯碼及糾正一位錯碼的能力。第11章 差錯控制編碼一個碼能檢測e個錯碼，則要求其最小碼dmine+1一個碼能糾正t個錯碼，則要求其最小dmin2t+1一個碼能糾正

17、t個錯碼，同時能檢測e個錯碼，則要求其最小碼距 dmine+t+1 (et)（2）最小碼距與檢錯和糾錯能力的關系）最小碼距與檢錯和糾錯能力的關系11.2 11.2 差錯控制編碼的基本原理差錯控制編碼的基本原理第11章 差錯控制編碼(a) 檢檢e個錯個錯圖圖11.2-2(a) 碼距與檢錯糾錯能力的關系碼距與檢錯糾錯能力的關系Ae1dminBA、B都為許用碼；都為許用碼；A發(fā)生發(fā)生e個錯；個錯；B不能靠在球面上不能靠在球面上，否則收到，否則收到B無法無法判斷是否為錯碼；判斷是否為錯碼；dmine+111.2 11.2 差錯控制編碼的基本原理差錯控制編碼的基本原理第11章 差錯控制編碼1tABtdm

18、in(b)糾正糾正t個錯碼個錯碼圖圖11.2-2(b) 碼距與檢錯糾錯能力的關系碼距與檢錯糾錯能力的關系A、B都為許用碼；都為許用碼；A、B都發(fā)生都發(fā)生t個錯；個錯；dmin2t+111.2 11.2 差錯控制編碼的基本原理差錯控制編碼的基本原理第11章 差錯控制編碼ABtedmint(c)糾正糾正t個錯碼，檢測個錯碼，檢測e個錯碼個錯碼圖圖11.2-2(c) 碼距與檢錯糾錯能力的關系碼距與檢錯糾錯能力的關系A、B都為許用碼；都為許用碼；A發(fā)生發(fā)生e個錯；個錯；B發(fā)生發(fā)生t個錯；個錯； dmine+t+111.2 11.2 差錯控制編碼的基本原理差錯控制編碼的基本原理第11章 差錯控制編碼當碼

19、長n=7, P=10-3時，則有假設隨機信道中發(fā)送“0”碼與發(fā)送“1”碼傳錯概率相等都為P,且P1,則在碼長為n的碼組中發(fā)生r個錯誤的概率為：rrn rrnnn!P (r)C p (1p)pr!(nr)! 137267397P (1)7p7107P (2)p21102 57P (3)p35103 4 ！4、誤碼率、誤碼率大概率事件大概率事件11.2 11.2 差錯控制編碼的基本原理差錯控制編碼的基本原理第11章 差錯控制編碼設n=k+r指一個碼組中信息位所占比重，用 表示=k/n=k/(k+r)，其中k為信息碼元的數(shù)目，n為碼長5、編碼效率、編碼效率11.2 11.2 差錯控制編碼的基本原理差

20、錯控制編碼的基本原理第11章 差錯控制編碼v 奇偶監(jiān)督碼v 二維奇偶監(jiān)督碼v 恒比碼v 正反碼vISBN國際圖書統(tǒng)一編號國際圖書統(tǒng)一編號11.3 11.3 常用的簡單編碼常用的簡單編碼 第11章 差錯控制編碼1、奇偶監(jiān)督碼、奇偶監(jiān)督碼 parity check1 2 3kk 1123kk 1k 1123k123kk 1k 1123kkaa a .ar1aaaa .aa0aaaa .aaaa .aa1aaaa .a1 對對 位位碼碼元元校校驗驗位位偶偶校校驗驗 奇奇校校驗驗 11.3 11.3 常用的簡單編碼常用的簡單編碼 奇偶監(jiān)督碼：在信息碼元后附加一位監(jiān)督位，使得碼組中奇偶監(jiān)督碼“1”的個數(shù)

21、為偶數(shù)或奇數(shù)。第11章 差錯控制編碼v 最小碼距dmin=2v 只能檢測出單個或奇數(shù)個錯誤，不能糾錯v 應用：以隨機錯誤為主的計算機通信系統(tǒng)，難于對付突發(fā)錯誤v 編碼效率=k/n=k/(k+1)11.3 11.3 常用的簡單編碼常用的簡單編碼 第11章 差錯控制編碼v 又稱為方陣碼、行列監(jiān)督碼、二維奇偶監(jiān)督碼。v 將水平奇偶監(jiān)督碼推廣到二維。即在水平監(jiān)督基礎上再對方陣中每一列進行奇偶校驗，發(fā)送時按列的順序傳輸v 接收端將碼元排成發(fā)送時的方陣形式，再分別按行、按列進行奇偶校驗2、水平垂直奇偶監(jiān)督碼、水平垂直奇偶監(jiān)督碼11.3 11.3 常用的簡單編碼常用的簡單編碼 第11章 差錯控制編碼46v

22、能夠發(fā)現(xiàn)某行、某列上所有奇數(shù)個錯誤以及突發(fā)長度不大于方陣行數(shù)或列數(shù)的突發(fā)錯誤；v 有可能檢測出偶數(shù)個錯誤（在行上檢測不出，但有可能在列上檢測出），但當偶數(shù)個錯誤剛好構成矩形時，則檢測不出v 可糾正一些錯誤mn(m1)(n1) 編編碼碼效效率率信信息息碼碼元元共共m m行行n n列列v 11.3 11.3 常用的簡單編碼常用的簡單編碼 信 息 碼 元監(jiān)督碼元1110000000111010011010100001110110001000010011001110111監(jiān)督碼元01101010011表表11-3 水平垂直奇偶監(jiān)督碼水平垂直奇偶監(jiān)督碼發(fā)送順序表表11-4 水平垂直奇偶監(jiān)督碼接收端糾錯示

23、例水平垂直奇偶監(jiān)督碼接收端糾錯示例信 息 碼 元監(jiān)督碼元1110000000111010011010100001110110001000010011001110111監(jiān)督碼元01101010011011例如：當碼組中僅在一行有奇數(shù)個錯誤時，能例如：當碼組中僅在一行有奇數(shù)個錯誤時，能夠確定錯誤位置，并糾正它。夠確定錯誤位置，并糾正它。表表11-5 水平垂直奇偶監(jiān)督碼接收端檢錯示例水平垂直奇偶監(jiān)督碼接收端檢錯示例信 息 碼 元監(jiān)督碼元1110000000111010011010100001110110001000010011001110111監(jiān)督碼元01101010011011構成矩形的偶數(shù)個誤碼

24、檢測不出。構成矩形的偶數(shù)個誤碼檢測不出。00表表11-6 水平垂直奇偶監(jiān)督碼接收端檢錯示例水平垂直奇偶監(jiān)督碼接收端檢錯示例信 息 碼 元監(jiān)督碼元1110000000111010011010100001110110001000010011001110111監(jiān)督碼元0110101001101有可能檢測出偶數(shù)個誤碼。有可能檢測出偶數(shù)個誤碼。001第11章 差錯控制編碼513、恒比碼、恒比碼v 每個碼組中含“1”和“0”的個數(shù)的比例恒定，又稱等重碼v 能檢測出所有1個和奇數(shù)個錯誤，并能部分檢測出偶數(shù)個錯誤（成對交換錯則檢測不出）v 簡單，適應于對字母或符號進行編碼11.3 11.3 常用的簡單編碼常用

25、的簡單編碼 表表11-7 保護電碼保護電碼（是一種五中取三碼）（是一種五中取三碼）數(shù)字數(shù)字電碼電碼數(shù)字數(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第11章 差錯控制編碼4、正反碼、正反碼v 監(jiān)督位數(shù)目與信息位數(shù)目相同，且監(jiān)督碼元與信息碼元或者相同或者相反，取決于信息序列中“1”的個數(shù)。v 電報通信用的正反碼的碼長n=10。信息位k=5，監(jiān)督位r=5。11.3 11.3 常用的簡單編碼常用的簡單編碼 第11章 差錯控制編碼v 碼組

26、中信息位有奇數(shù)個“1”，監(jiān)督碼元與信息碼元相同；v 碼組中信息位有偶數(shù)個“1”，監(jiān)督碼元與信息碼元相反。11.3 11.3 常用的簡單編碼常用的簡單編碼 （1）正反碼編碼規(guī)）正反碼編碼規(guī)則則第11章 差錯控制編碼v 將接收碼組中信息位與監(jiān)督位按位模2加，得到合成碼組v 產(chǎn)生校驗碼組：v 接收碼組中信息碼元有奇數(shù)個“1”，則校驗碼組=合成碼組，否則校驗碼組=合成碼組的反碼v 按照校驗碼組中“1”的個數(shù)進行判決及糾錯（表11-8）11.3 11.3 常用的簡單編碼常用的簡單編碼 （2）接收端解碼規(guī)則）接收端解碼規(guī)則校驗碼組組成校驗碼組組成誤碼情況誤碼情況全為全為0無誤碼無誤碼4個個“1”，1個個“

27、0”信息碼有一個錯碼，位置對應信息碼有一個錯碼，位置對應校驗碼組中校驗碼組中“0”的位置的位置1個個“1”，4個個“0”監(jiān)督碼有一個錯碼，位置對應監(jiān)督碼有一個錯碼，位置對應校驗碼組中校驗碼組中“1”的位置的位置其它其它錯碼多于錯碼多于1個個表表11-8 正反碼檢錯糾錯判決規(guī)則正反碼檢錯糾錯判決規(guī)則第11章 差錯控制編碼57例例11-1 假設發(fā)送碼組為假設發(fā)送碼組為1100111001，分析各種，分析各種正反碼判決糾錯情況。正反碼判決糾錯情況。 11.3 11.3 常用的簡單編碼常用的簡單編碼 碼長為碼長為10的正反碼能夠糾正的正反碼能夠糾正1位差錯，并能位差錯，并能檢測所有檢測所有2位及以下的

28、錯碼。位及以下的錯碼。第11章 差錯控制編碼5、ISBN國際圖書統(tǒng)一編號國際圖書統(tǒng)一編號International Standard Book NumberISBN 7-118-02481-3中國中國出出版版公公司司書書名名編編號號校校驗驗位位無誤碼，若不能被11整除，有誤碼11.3 11.3 常用的簡單編碼常用的簡單編碼 第11章 差錯控制編碼 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+3*1= 198（模（模11）=011.3 11.3 常用的簡單編碼常用的簡單編碼 能被11整除，無誤碼。第11章 差錯控制編碼5、ISB

29、N國際圖書統(tǒng)一編號國際圖書統(tǒng)一編號International Standard Book Number11.3 11.3 常用的簡單編碼常用的簡單編碼 早期的早期的ISBN號由號由10位十進制數(shù)字組成，位十進制數(shù)字組成，2007年起全世界的年起全世界的ISBN號統(tǒng)一升級為號統(tǒng)一升級為13位，簡稱位，簡稱“ISBN-13”。 ISBN-13的編碼結構組成 第11章 差錯控制編碼11.3 11.3 常用的簡單編碼常用的簡單編碼 每個每個ISBN號碼的前號碼的前12位與最后一位校驗位之間有通過固定算法形成位與最后一位校驗位之間有通過固定算法形成的約束關系。若它們之間不滿足這個約束關系，則該的約束關系

30、。若它們之間不滿足這個約束關系，則該ISBN號碼對應的圖號碼對應的圖書必為非法出版物。校驗位的具體算法包括：書必為非法出版物。校驗位的具體算法包括： 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+ 3 + 0 + 2 + 3 +3 + 6 + 3 + 3 = 82(3) MOD10=2(4) 10-2=8第11章 差錯控制編碼11.4 11.4 線性分組碼線性分組碼 (1) 分組碼：先將信息碼分組，然后給每組信碼附加若干監(jiān)督碼的編碼稱為分組碼，用符號(n,k)表示，k是信息碼的位數(shù)，n是編碼組總位數(shù)，又稱為碼

31、長，r=n-k為監(jiān)督位數(shù)。 (2) 代數(shù)碼：建立在代數(shù)學基礎上的編碼稱為代數(shù)碼。例如奇偶校驗碼。 v1、基本概念基本概念第11章 差錯控制編碼 (3) 線性碼：線性碼中信息位和監(jiān)督位是按一組線性方程構成的。線性碼是一種代數(shù)碼。 (4) 線性分組碼：信息碼分組后，附加的監(jiān)督碼和信息碼由一些線性代數(shù)方程聯(lián)系著的編碼稱為線性分組碼。11.4 11.4 線性分組碼線性分組碼第11章 差錯控制編碼2、線性分組碼的性質、線性分組碼的性質v任意兩個許用碼組之和（逐位模2和）仍為一許用碼組，即具有封閉性。v最小碼距=非零碼的最小碼重（1的個數(shù)）。v有零碼（信息碼元和監(jiān)督碼元均為零的碼組）11.4 11.4 線

32、性分組碼線性分組碼第11章 差錯控制編碼以漢明碼為例來說明編碼原理。漢明碼是一種設計用來糾正一位錯碼且編碼效率較高的線性分組碼，已廣泛應用于數(shù)字通信和數(shù)據(jù)存儲系統(tǒng)中，本節(jié)將以（7，4）漢明碼為例進行講述。 3、線性分組碼的編碼原理線性分組碼的編碼原理11.4 11.4 線性分組碼線性分組碼第11章 差錯控制編碼v 發(fā)送端編碼：將一位監(jiān)督碼元附加在信息碼元后，使得碼元中“1”碼元個數(shù)為偶數(shù)。v 接收端譯碼：計數(shù)接收碼組中“1”碼元個數(shù)是否為偶數(shù)，即計算：S=an-1+ an-2+ a0 （模（模2加）加）（11.4-1）S=0認為沒錯，S=1認為有錯。（11.4-1）式稱為監(jiān)督方程/監(jiān)督關系式，

33、S稱為校正子/校驗子/伴隨式（1）回憶奇偶監(jiān)督偶校驗碼）回憶奇偶監(jiān)督偶校驗碼11.4 11.4 線性分組碼線性分組碼第11章 差錯控制編碼v 監(jiān)督位增加到2位：有兩個監(jiān)督方程，兩個伴隨式；v 兩個伴隨式組合有四種（00表示無錯，01、10、11表示一位錯碼的三種可能位置）v 監(jiān)督位增加到r位：可指示一位錯碼的（2r-1）個可能位置v對于（n，k)分組碼，若希望用r=n-k個監(jiān)督位構造出的r個監(jiān)督關系式來指示一位錯碼的n種可能位置，則要求：2r-1n 即即2r k+r+1 （11.4-2） 可以這樣來考慮11.4 11.4 線性分組碼線性分組碼第11章 差錯控制編碼欲糾正一位錯碼，由（11.4-

34、2）式知r 3。取r=3，則n=k+r=7設7位碼元為：a6a5 a0；三個伴隨式：S1、S2、S3；可規(guī)定S1S2S3的八種組合與一位錯碼的對應關系（也可規(guī)定為另一種對應關系）：構造一（構造一（n，k)分組碼，分組碼，k=4并能糾正一位錯碼并能糾正一位錯碼(2) 漢明碼的構造漢明碼的構造11.4 11.4 線性分組碼線性分組碼第11章 差錯控制編碼S1S2S3錯碼位置錯碼位置S1S2S3錯碼位置錯碼位置000無錯無錯011a3001a0101a4010a1110a5100a2111a6表表11-9 S1S2S3的八種組合與一位錯碼的對應關系的八種組合與一位錯碼的對應關系11.4 11.4 線

35、性分組碼線性分組碼第11章 差錯控制編碼S1S2S3錯碼位置錯碼位置0 0 0無錯碼無錯碼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)督方程:第11章 差錯控制編碼（3）發(fā)端編碼的原則：發(fā)端編碼的原則：v 信息碼元a6 、a5 、a4、a3來源于待編碼的信息序列；v 監(jiān)督碼元 a2 、a1、 a0的取值應根據(jù)信息碼元按監(jiān)督關系式來決定，即使前面三式中的S1、 S

36、2 、S3均為0：11.4 11.4 線性分組碼線性分組碼第11章 差錯控制編碼Fa2 = a4+a5+a6Fa1 = a3+a5+a6Fa0 = a3+a4+a6v 給定信息位后，根據(jù)上式算出各監(jiān)督位，該編碼的所有碼組如表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 線性分組碼線性分組碼第11章 差錯控制編碼信息位信息位 監(jiān)督位監(jiān)督位 信息位信息位 監(jiān)督位監(jiān)督位a6a5a4a3a2a1a0a6a5a4a3a2a1a000000001000111000101110011000010101101

37、00100011110101100101001101100001010110111010100110011111010001110001111111表表11-10 （7，4）漢明編碼的許用碼組）漢明編碼的許用碼組第11章 差錯控制編碼v該漢明碼的編碼效率較高 R=k/n=4/757% v該碼的最小碼距為3，能糾正一個錯碼或檢測兩個錯碼v收到碼組，按照（7，4）漢明碼進行分析，判斷是否有誤，如果有，如何更正？ 按監(jiān)督方程計算可得：S1=0，S2=1，S3=1；再根據(jù)校正子組合與一位錯碼位置的對應關系，可知錯碼發(fā)生在a3位，并加以糾正。0000001 101101111.4 11.4 線性分組碼線

38、性分組碼第11章 差錯控制編碼（4）監(jiān)督矩陣）監(jiān)督矩陣沿（7，4）漢明碼出發(fā)，式（11.4-4）可改寫成：1 a6+ 1 a5+ 1 a4 +0 a3+ 1 a2 + 0 a1+ 0 a0=01 a6+ 1 a5+ 0 a4 +1 a3+ 0 a2 + 1 a1+ 0 a0=01 a6+ 0 a5+ 1 a4 +1 a3+ 0 a2 + 0 a1+ 1 a0=0寫成矩陣形式：0001001101010101100101110123456aaaaaaa(11.4-6)11.4 11.4 線性分組碼線性分組碼第11章 差錯控制編碼H稱為線性碼監(jiān)督矩陣可化簡為： HAT=0T 或AHT=0 6543

39、210Aa a a a a a aO0 0 0 r1110100H11010101011001P I 11.4 11.4 線性分組碼線性分組碼第11章 差錯控制編碼v rn階矩陣v 監(jiān)督矩陣H確定了編碼時監(jiān)督碼元與信息碼元的關系v 把具有PIr形式的H矩陣稱為典型形式的監(jiān)督矩陣，其中P為r k階矩陣, Ir為r r階單位方陣v H矩陣的各行應線性無關。矩陣若能寫成典型形式，則其各行一定線性無關監(jiān)督矩陣H特點11.4 11.4 線性分組碼線性分組碼第11章 差錯控制編碼上式右部前面矩陣就是監(jiān)督矩陣H中的P矩陣。62514036543aa1110aa1101aa1011aaaPaa (5) 生成矩陣生成矩陣（11.4-5）式也可寫成矩陣形式，即(11.4-7)11.4 11.4 線性分組碼線性分組碼第11章 差錯控制編碼其中Q=PT可見，Q為k r階矩陣。 QaaaaPaaaaaaaaaaaT345634563456012110101011111或寫成11.4 11.4 線性分組碼線性分組碼第11章 差錯控制編碼生成矩陣G：在Q矩陣的左邊加上一個k k階矩陣，即 Tkk10001110100110GI QI P00101010001011 生生成成矩矩陣陣 6543AaaaaG 11.4 11.4 線