第5章差錯控制編碼

1、1第第5 5章章 差錯控制編碼差錯控制編碼5.1 引言引言5.2 糾錯編碼的基本原理糾錯編碼的基本原理5.3 常用的簡單編碼常用的簡單編碼5.4 線性分組碼線性分組碼5.5 循環(huán)碼循環(huán)碼第5章 差錯控制編碼2數(shù)字信號在傳輸過程中受到干擾的影響，使信號波形變壞，發(fā)生誤碼，可以采用一些方法解決。v 有效性信源編碼v 可靠性信道編碼第5章 差錯控制編碼30 、復習、復習v 模擬信源：在無線廣播中，信源一般是一個語音源（話音或音樂）；在電視廣播中，信源主要是活動圖像的視頻信號源。這些信源的輸出都是模擬信號，所以稱之為模擬源。v 信源編碼：將模擬信息源的輸出轉化為數(shù)字信號，即A/D轉換。v 信源編碼目的

2、：提高通信有效性，減少原消息的冗余度。第5章 差錯控制編碼4差錯出現(xiàn)原因v 外界噪聲v 傳輸中碼間串擾解決方法v 合理地設計基帶信號，選擇調(diào)制、解調(diào)方式，采用均衡技術，發(fā)送功率等因素，使誤比特率降低。v 差錯控制措施了。第5章 差錯控制編碼5 差錯控制編碼屬信道編碼，要求在滿足有效性前提下，盡可能提高數(shù)字通信的可靠性。 差錯控制編碼是在信息序列上附加上一些監(jiān)督碼元，利用這些冗余的碼元，使原來不規(guī)律的或規(guī)律性不強的原始數(shù)字信號變?yōu)橛幸?guī)律的數(shù)字信號。例如奇偶校驗。 差錯控制譯碼則利用這些規(guī)律性來鑒別傳輸過程是否發(fā)生錯誤，或進而糾正錯誤。第5章 差錯控制編碼61、差錯控制編碼分類、差錯控制編碼分類第

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

4、0110110l可見發(fā)生了兩個長度分別為和的突發(fā)差錯，其錯誤圖樣分別為1101001和11011突發(fā)長度：指突發(fā)差錯首位與末位之間的長度（中間可能有沒錯的碼位）第5章 差錯控制編碼9l說明差錯序列或錯誤圖樣中的“”表示對應碼位沒錯，而“”表示有錯實際信道很復雜，所出現(xiàn)的差錯并不是單一的，往往是隨機和突發(fā)差錯并存，只不過以某種錯誤為主一般說來，糾正隨機差錯的編譯碼方法和設備比較簡單，成本較低，效果較顯著；而糾正突發(fā)差錯的編譯碼方法和設備比較復雜，成本較高，效果也不如前者顯著第5章 差錯控制編碼10 4、信道類型、信道類型v 隨機信道v 突發(fā)信道v 混合信道第5章 差錯控制編碼115、差錯控制方法

5、、差錯控制方法v檢錯重發(fā)（ARQ） 停發(fā)等候重發(fā) 返回重發(fā) 選擇重發(fā)v前向糾錯（FEC）v反饋校驗（IRQ）v混合方式（HEC）第5章 差錯控制編碼12（1）檢錯重發(fā)法（）檢錯重發(fā)法（ARQ） Automatic Repeat reQuest 收端在接收到的信碼中發(fā)現(xiàn)錯碼時，就通知發(fā)端重發(fā)，直到正確接收為止。例如奇偶校驗。 檢錯重發(fā)方式只用于檢測誤碼，能夠在接收單元中發(fā)現(xiàn)錯誤，但不一定知道該錯誤碼的具體位置。 需具備雙向信道。發(fā)發(fā)收收能夠發(fā)現(xiàn)錯誤的碼能夠發(fā)現(xiàn)錯誤的碼圖圖5.1-1（a) 檢錯重發(fā)（檢錯重發(fā)（ARQ)應答信號應答信號圖圖5.1-1（b) 檢錯重發(fā)（檢錯重發(fā)（ARQ)信信源源編碼器

6、和緩編碼器和緩沖存儲器沖存儲器重發(fā)控制重發(fā)控制雙雙向向信信道道解碼器解碼器指令產(chǎn)生器指令產(chǎn)生器輸出緩沖輸出緩沖存儲器存儲器收收信信者者正確時輸出錯誤時刪除判斷有無錯誤第5章 差錯控制編碼14 停發(fā)等候重發(fā)停發(fā)等候重發(fā)2發(fā)送端：接收端：133123ACKACKNAK發(fā)現(xiàn)錯誤TITw停頓時間圖圖5.1-2 停發(fā)等候重發(fā)停發(fā)等候重發(fā)第5章 差錯控制編碼15發(fā)端在Tw時間內(nèi)送出一個碼組；收端收到后檢查。如果未發(fā)現(xiàn)錯誤，則發(fā)回一個認可信號（ACK）給發(fā)送端，發(fā)送端收到ACK信號再發(fā)下一個碼組若檢測到錯誤，則發(fā)回一個否認信號（NAK），發(fā)送端收到NAK信號后重發(fā)前一碼組，并再次等候ACK信號或NAK信號發(fā)

7、送兩個碼組之間有停頓時間TI，影響了傳輸效率第5章 差錯控制編碼16 返回重發(fā)返回重發(fā)其發(fā)送端不停地送出一個個連續(xù)碼組，不再等候收端返回的ACK信號一旦收端發(fā)現(xiàn)錯誤并返回NAK信號，則發(fā)端從下一碼組開始重發(fā)前面的N個碼組N的大小取決于信號傳遞及處理所帶來的延時第5章 差錯控制編碼17發(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ā)圖圖5.1-3 返回重發(fā)返回重發(fā)第5章 差錯控制編碼18 選擇重發(fā)選擇重發(fā)也是連續(xù)不斷地發(fā)送碼組，收端檢測到錯誤后發(fā)回NAK信號。與返回重發(fā)不同的是，發(fā)端并不重發(fā)錯誤

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

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

10、5.1-6 信息反饋法信息反饋法數(shù)據(jù)信息數(shù)據(jù)信息第5章 差錯控制編碼24收端把收到的數(shù)據(jù)序列全部經(jīng)反向信道送回發(fā)端，發(fā)端比較發(fā)出和送回的數(shù)據(jù)序列，從而發(fā)現(xiàn)有否錯誤，如果有錯誤，發(fā)端將數(shù)據(jù)序列再次傳送，直到發(fā)端沒有發(fā)現(xiàn)錯誤。不需要糾錯、檢錯的編、譯碼器，設備簡單。需要和正向信道相同的反向信道，實時性差發(fā)端需要一定容量的存儲器以存儲發(fā)送碼組僅適應于傳輸速率較低，信道差錯率較低，具有雙向傳輸線路及控制簡單的系統(tǒng)第5章 差錯控制編碼25（4）混合糾錯檢錯（）混合糾錯檢錯（HEC） Hybrid Error CorrectionFEC與ARQ的結合發(fā)端發(fā)出同時具有檢錯和糾錯能力的碼，收端收到后，檢查錯誤

11、情況：如果錯誤在糾錯能力之內(nèi)，則自動糾正；若超出糾錯能力，但在檢錯能力之內(nèi)，則經(jīng)反向信道要求重發(fā)。在實時性和譯碼復雜性方面是FEC和ARQ的折衷。第5章 差錯控制編碼26發(fā)發(fā)收收能夠發(fā)現(xiàn)和糾正錯誤的碼能夠發(fā)現(xiàn)和糾正錯誤的碼圖圖5.1-7 混合糾錯檢錯（混合糾錯檢錯（HEC)應答信號應答信號第5章 差錯控制編碼27核心問題核心問題v 發(fā)現(xiàn)錯誤發(fā)現(xiàn)錯誤v 糾正錯誤糾正錯誤第5章 差錯控制編碼285.2 5.2 差錯控制編碼的基本原理差錯控制編碼的基本原理 在信息碼序列中加監(jiān)督碼就稱為差錯控制編碼，也叫糾錯編碼。不同的編碼方法，有不同的檢錯和糾錯能力，增加監(jiān)督碼元越多，檢（糾）錯能力越強。差錯控制編

12、碼原則上是降低編碼效率來換取可靠性提高。（即誤碼率更?。?第5章 差錯控制編碼29v理論依據(jù)：Shannon信道編碼定理。v定理指出： 對于一給定的有干擾信道，若其信道容量為C，只要發(fā)送端以低于C的速率R發(fā)送信息，則一定存在一種編碼方法，使編碼錯誤概率P隨著碼長n的增加，按指數(shù)下降到任意小的值。1、糾錯編碼的理論依據(jù)、糾錯編碼的理論依據(jù)5.2 5.2 差錯控制編碼的基本原理差錯控制編碼的基本原理第5章 差錯控制編碼30nE(R )pen :R :E(R ) : 編編 碼碼 長長 度度信信 息息 發(fā)發(fā) 送送 速速 率率錯錯 誤誤 指指 數(shù)數(shù)P1C,E(R)2n 為為了了方方法法 ：但但方方法法

13、 ：E(R)nCC1C2圖圖5.2-1 誤差指數(shù)曲線誤差指數(shù)曲線5.2 5.2 差錯控制編碼的基本原理差錯控制編碼的基本原理第5章 差錯控制編碼312、糾錯編碼的基本思想、糾錯編碼的基本思想5.2 5.2 差錯控制編碼的基本原理差錯控制編碼的基本原理v 發(fā)送端按照某種規(guī)則在信息序列上附加監(jiān)督碼元，接收端則按照同一規(guī)則檢查兩者間關系v 以犧牲通信的有效性（信息傳輸速率）來提高可靠性v 碼的檢錯和糾錯能力是用信息量的冗余來換取的。一般說來，添加的冗余越多，碼的檢錯、糾錯能力越強，但信道的傳輸效率下降也越多。第5章 差錯控制編碼32v 碼長：碼字中碼元的數(shù)目。v 碼距：兩個等長碼字中對應碼位上不同二

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

15、用碼字之間的距離，碼的最小距離越大，說明碼字間的最小差別越離，碼的最小距離越大，說明碼字間的最小差別越大，抗干擾能力就越強。大，抗干擾能力就越強。5.2 5.2 差錯控制編碼的基本原理差錯控制編碼的基本原理第5章 差錯控制編碼34舉例說明：假如要傳送舉例說明：假如要傳送A、B兩個消息兩個消息編碼一：消息A-“0”；消息B-“1”最小碼距1若傳輸中產(chǎn)生錯碼（“0”錯成“1”或“1”錯成“0”）收端無法發(fā)現(xiàn)，該編碼無檢錯糾錯能力。5.2 5.2 差錯控制編碼的基本原理差錯控制編碼的基本原理第5章 差錯控制編碼35編碼二：消息A-“00”；消息B-“11”最小碼距2若傳輸中產(chǎn)生一位錯碼，則變成“01

16、”或“10”，收端判決為有錯（因“01”“10”為禁用碼組），但無法確定錯碼位置，不能糾正，該編碼具有檢出一位錯碼的能力。這表明增加一位冗余碼元后碼具有檢出一位錯碼的能力5.2 5.2 差錯控制編碼的基本原理差錯控制編碼的基本原理編碼三：消息A-“000”；消息B-“111”最小碼距3傳輸中產(chǎn)生一位即使兩位錯碼，都將變成禁用碼組，收端判決傳輸有錯。該編碼具有檢出兩位錯碼的能力。在產(chǎn)生一位錯碼（錯1位概率遠遠大于錯2位、3位概率）情況下，收端可根據(jù)“大數(shù)”法則進行正確判決，能夠糾正這一位錯碼。該編碼具有糾正一位錯碼的能力。例如收到110，認為是111。這表明增加兩位冗余碼元后碼具有檢出兩位錯碼及

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

18、法無法判斷是否為錯碼；判斷是否為錯碼；dmine+15.2 5.2 差錯控制編碼的基本原理差錯控制編碼的基本原理第5章 差錯控制編碼391tABtdmin(b)糾正糾正t個錯碼個錯碼圖圖5.2-2(b) 碼距與檢錯糾錯能力的關系碼距與檢錯糾錯能力的關系A、B都為許用碼；都為許用碼；A、B都發(fā)生都發(fā)生t個錯；個錯；dmin2t+15.2 5.2 差錯控制編碼的基本原理差錯控制編碼的基本原理第5章 差錯控制編碼40ABtedmint(c)糾正糾正t個錯碼，檢測個錯碼，檢測e個錯碼個錯碼圖圖5.2-2(c) 碼距與檢錯糾錯能力的關系碼距與檢錯糾錯能力的關系A、B都為許用碼；都為許用碼；A發(fā)生發(fā)生e個錯；個錯；B發(fā)生發(fā)生t個錯；個錯； dmine+t+15.2 5.2 差錯控制編碼的基本原理差錯控制編碼的基本原理第5章 差錯控制編碼41當碼長n=7, P=10-3時，則有假設隨機信道中發(fā)送“0”碼與發(fā)送“1”碼傳錯概率相等都為P,且P(j-i)v 能檢出全部的奇數(shù)個錯碼：含有奇數(shù)項錯碼的多項式必不