第5章差錯(cuò)控制編碼

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

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

3、5章 差錯(cuò)控制編碼72、誤碼類型、誤碼類型v 隨機(jī)誤碼v 突發(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ā)信道有記憶信道3、錯(cuò)誤圖樣、錯(cuò)誤圖樣l例如：設(shè)發(fā)送數(shù)據(jù)序列為：00000000001111111111接收數(shù)據(jù)序列為： 01101001001111001001錯(cuò)誤圖樣（差錯(cuò)序列）：發(fā)送數(shù)據(jù)序列與接收序列對(duì)應(yīng)碼位的模和則差錯(cuò)序列為： 0110100100000

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

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

6、和緩編碼器和緩沖存儲(chǔ)器沖存儲(chǔ)器重發(fā)控制重發(fā)控制雙雙向向信信道道解碼器解碼器指令產(chǎn)生器指令產(chǎn)生器輸出緩沖輸出緩沖存儲(chǔ)器存儲(chǔ)器收收信信者者正確時(shí)輸出錯(cuò)誤時(shí)刪除判斷有無錯(cuò)誤第5章 差錯(cuò)控制編碼14 停發(fā)等候重發(fā)停發(fā)等候重發(fā)2發(fā)送端：接收端：133123ACKACKNAK發(fā)現(xiàn)錯(cuò)誤TITw停頓時(shí)間圖圖5.1-2 停發(fā)等候重發(fā)停發(fā)等候重發(fā)第5章 差錯(cuò)控制編碼15發(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ā)

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

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

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

10、5.1-6 信息反饋法信息反饋法數(shù)據(jù)信息數(shù)據(jù)信息第5章 差錯(cuò)控制編碼24收端把收到的數(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è)備簡(jiǎn)單。需要和正向信道相同的反向信道，實(shí)時(shí)性差發(fā)端需要一定容量的存儲(chǔ)器以存儲(chǔ)發(fā)送碼組僅適應(yīng)于傳輸速率較低，信道差錯(cuò)率較低，具有雙向傳輸線路及控制簡(jiǎn)單的系統(tǒng)第5章 差錯(cuò)控制編碼25（4）混合糾錯(cuò)檢錯(cuò)（）混合糾錯(cuò)檢錯(cuò)（HEC） Hybrid Error CorrectionFEC與ARQ的結(jié)合發(fā)端發(fā)出同時(shí)具有檢錯(cuò)和糾錯(cuò)能力的碼，收端收到后，檢查錯(cuò)誤

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

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

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

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

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

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

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

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