第三章 信道編碼技術

1、在數(shù)字通信中，根據(jù)不同的目的，編碼可分為在數(shù)字通信中，根據(jù)不同的目的，編碼可分為信源編碼和信道信源編碼和信道編碼編碼。 信源編碼信源編碼是為了提高數(shù)字通信的有效性以及使模擬信號數(shù)字是為了提高數(shù)字通信的有效性以及使模擬信號數(shù)字化而采取的編碼技術?；扇〉木幋a技術。 信道編碼信道編碼是為了降低誤碼率，提高數(shù)字通信的可靠性而采取是為了降低誤碼率，提高數(shù)字通信的可靠性而采取的編碼。的編碼。v 一類信道編碼是對傳輸信號的一類信道編碼是對傳輸信號的碼型進行轉(zhuǎn)換碼型進行轉(zhuǎn)換，使之更適，使之更適合于信道特性或滿足接收端對恢復信號的要求，從而減少信合于信道特性或滿足接收端對恢復信號的要求，從而減少信息損失；息

2、損失；v 另一類信道編碼是在信息序列中人為的另一類信道編碼是在信息序列中人為的增加冗余位增加冗余位，使，使之具有相關特性，在接收端利用相關性進行檢錯或糾錯，從之具有相關特性，在接收端利用相關性進行檢錯或糾錯，從而達到可靠通信的目的。而達到可靠通信的目的。差錯（糾錯）控制差錯（糾錯）控制信道編碼技術信道編碼技術 信道分類：從差錯控制角度看信道分類：從差錯控制角度看隨機信道隨機信道：錯碼的出現(xiàn)是隨機的：錯碼的出現(xiàn)是隨機的 差錯是差錯是相互獨立相互獨立的的, ,不相關不相關，如白噪聲，如白噪聲突發(fā)信道突發(fā)信道：錯碼是成串集中出現(xiàn)的：錯碼是成串集中出現(xiàn)的錯誤與錯誤間有相關性錯誤與錯誤間有相關性, ,一

3、個差錯往往要影響到后面一串一個差錯往往要影響到后面一串字字，如脈沖干擾，如脈沖干擾 E: 0 0 1 0 0 1 0 0 0 0 0 00 0 1 0 0 1 0 0 0 0 0 0 1 0 0 1 1 1 0 0 0 0 0 0 01 0 0 1 1 1 0 0 0 0 0 0 0 混合信道混合信道：既存在隨機錯碼又存在突發(fā)錯碼：既存在隨機錯碼又存在突發(fā)錯碼 對于不同類型的信道應采用不同的差錯控制技術對于不同類型的信道應采用不同的差錯控制技術信道分類信道分類 突發(fā)長度= 4突發(fā)長度= 6本章內(nèi)容本章內(nèi)容v 差錯控制v 線性分組碼v 循環(huán)碼v 卷積碼第一節(jié)差錯控制第一節(jié)差錯控制v 差錯控制技術

4、v差錯編碼的基本原理v 碼距與糾檢錯能力的關系v差錯控制編碼的分類差錯控制差錯控制技術技術 自動請求重發(fā)自動請求重發(fā)(ARQ)(ARQ)：發(fā)端發(fā)送發(fā)端發(fā)送檢錯碼檢錯碼，收端譯碼器判斷當前碼字傳輸是否出錯；收端譯碼器判斷當前碼字傳輸是否出錯；當有錯時按某種協(xié)議通過一個當有錯時按某種協(xié)議通過一個反向信道反向信道請求請求發(fā)送端重傳已發(fā)送的碼字發(fā)送端重傳已發(fā)送的碼字( (全部或部分全部或部分) )。差錯控制差錯控制技術技術 優(yōu)點：譯碼設備簡單優(yōu)點：譯碼設備簡單缺點：缺點：系統(tǒng)是工作在半雙工狀態(tài)，系統(tǒng)是工作在半雙工狀態(tài)，時間沒有得到充分利用，傳輸效率時間沒有得到充分利用，傳輸效率較低較低，只有檢錯能力而

5、無糾錯能力只有檢錯能力而無糾錯能力差錯控制差錯控制技術技術 前向糾錯前向糾錯(FEC)(FEC)：發(fā)送端的信道編碼器將信息碼組編成具有一發(fā)送端的信道編碼器將信息碼組編成具有一定定糾錯能力糾錯能力的碼。的碼。接收端信道譯碼器對接收碼字進行譯碼接收端信道譯碼器對接收碼字進行譯碼, ,若傳若傳輸中產(chǎn)生的差錯數(shù)目在碼的糾錯能力之內(nèi)時輸中產(chǎn)生的差錯數(shù)目在碼的糾錯能力之內(nèi)時, ,譯碼器對差錯進行定位并加以糾正。譯碼器對差錯進行定位并加以糾正。差錯控制差錯控制技術技術 優(yōu)點：不會因反復重發(fā)延誤時間優(yōu)點：不會因反復重發(fā)延誤時間缺點：譯碼設備比較復雜缺點：譯碼設備比較復雜差錯控制差錯控制技術技術 信息反饋信息反

6、饋(IRQ)(IRQ)：收端把收到的數(shù)據(jù)收端把收到的數(shù)據(jù), ,原封不動地通過反饋信道送回到發(fā)端原封不動地通過反饋信道送回到發(fā)端, ,發(fā)發(fā)端比較發(fā)的數(shù)據(jù)與反饋來的數(shù)據(jù)端比較發(fā)的數(shù)據(jù)與反饋來的數(shù)據(jù), ,從而發(fā)現(xiàn)錯誤從而發(fā)現(xiàn)錯誤, ,并且把錯誤并且把錯誤的消息再次傳送的消息再次傳送, ,直到發(fā)端沒有發(fā)現(xiàn)錯誤為止。直到發(fā)端沒有發(fā)現(xiàn)錯誤為止。效率低效率低混合糾錯混合糾錯(HEC)(HEC)：是是FECFEC與與ARQARQ方式的結(jié)合。方式的結(jié)合。發(fā)端發(fā)送同時具有自動糾錯和檢測能力的碼組發(fā)端發(fā)送同時具有自動糾錯和檢測能力的碼組, ,收端收到碼收端收到碼組后組后, ,檢查差錯情況檢查差錯情況, ,如果差錯在

7、碼的糾錯能力以內(nèi)如果差錯在碼的糾錯能力以內(nèi), ,則自動則自動進行糾正。進行糾正。如果信道干擾很嚴重如果信道干擾很嚴重, ,錯誤很多錯誤很多, ,超過了碼的糾錯能力超過了碼的糾錯能力, ,但能但能檢測出來檢測出來, ,則經(jīng)反饋信道請求發(fā)端重發(fā)這組數(shù)據(jù)。則經(jīng)反饋信道請求發(fā)端重發(fā)這組數(shù)據(jù)。差錯控制差錯控制技術技術 從理論上講，差錯控制是以降低信息傳從理論上講，差錯控制是以降低信息傳輸速率為代價換取提高傳輸可靠性輸速率為代價換取提高傳輸可靠性糾錯編碼的基本原理糾錯編碼的基本原理分組碼基本原理：舉例說明如下。分組碼基本原理：舉例說明如下。設有一種由設有一種由3位二進制數(shù)字構成的碼組，它共有位二進制數(shù)字構

8、成的碼組，它共有8種不同的可能組合。若種不同的可能組合。若將其全部用來表示天氣，則可以表示將其全部用來表示天氣，則可以表示8種不同天氣，種不同天氣， 例如：例如：“000”（晴），（晴），“001”（云），（云）， “010”（陰），（陰），“011”（雨），（雨）， “100”（雪），（雪），“101”（霜），（霜）， “110”（霧），（霧），“111”（雹）。（雹）。其中任一碼組在傳輸中若發(fā)生一個或多個錯碼，則將變成另一個信息碼其中任一碼組在傳輸中若發(fā)生一個或多個錯碼，則將變成另一個信息碼組。這時，接收端將無法發(fā)現(xiàn)錯誤。組。這時，接收端將無法發(fā)現(xiàn)錯誤。13糾錯編碼的基本原理糾錯編碼的基本

9、原理若在上述若在上述8種碼組中只準許使用種碼組中只準許使用4種來傳送天氣，例如：種來傳送天氣，例如：“000”晴晴 “011”云云 “101”陰陰 “110”雨雨這時，雖然只能傳送這時，雖然只能傳送4種不同的天氣，但是接收端卻有可能發(fā)現(xiàn)碼組中種不同的天氣，但是接收端卻有可能發(fā)現(xiàn)碼組中的一個錯碼。的一個錯碼。例如，若例如，若“000”（晴）中錯了一位，則接收碼組將變成（晴）中錯了一位，則接收碼組將變成“100”或或“010”或或“001”。這。這3種碼組都是不準使用的，稱為種碼組都是不準使用的，稱為禁用碼組。接收端在收到禁用碼組時，就認為發(fā)現(xiàn)了錯碼。當發(fā)生接收端在收到禁用碼組時，就認為發(fā)現(xiàn)了錯碼

10、。當發(fā)生3個錯碼時，個錯碼時，“000”變成了變成了“111”，它也是禁用碼組，故這種編碼也能檢測，它也是禁用碼組，故這種編碼也能檢測3個錯碼。個錯碼。但是這種碼不能發(fā)現(xiàn)一個碼組中的兩個錯碼，因為發(fā)生兩個錯碼后產(chǎn)生但是這種碼不能發(fā)現(xiàn)一個碼組中的兩個錯碼，因為發(fā)生兩個錯碼后產(chǎn)生的是的是許用碼組。14糾錯編碼的基本原理糾錯編碼的基本原理檢錯和糾錯檢錯和糾錯上面這種編碼上面這種編碼只能檢測錯碼，不能糾正錯碼只能檢測錯碼，不能糾正錯碼。例如，當接收碼組為禁用。例如，當接收碼組為禁用碼組碼組“100”時，接收端將無法判斷是哪一位碼發(fā)生了錯誤，因為晴、陰、時，接收端將無法判斷是哪一位碼發(fā)生了錯誤，因為晴、

11、陰、雨三者錯了一位都可以變成雨三者錯了一位都可以變成“100”。要能夠糾正錯誤，還要增加多余度要能夠糾正錯誤，還要增加多余度。例如，若規(guī)定許用碼組只有兩個：。例如，若規(guī)定許用碼組只有兩個：“000”（晴），（晴），“111”（雨），其他都是禁用碼組，則能夠檢測兩個以下（雨），其他都是禁用碼組，則能夠檢測兩個以下錯碼，或能夠糾正一個錯碼。錯碼，或能夠糾正一個錯碼。例如，當收到禁用碼組例如，當收到禁用碼組“100”時，時，若當作僅有一個錯碼若當作僅有一個錯碼，則可以判斷此，則可以判斷此錯碼發(fā)生在錯碼發(fā)生在“1”位，從而糾正為位，從而糾正為“000”（晴）。因為（晴）。因為“111”（雨）發(fā)生任（雨

12、）發(fā)生任何一位錯碼時都不會變成何一位錯碼時都不會變成“100”這種形式。這種形式。 但是，這時若假定錯碼數(shù)不超過兩個，則存在兩種可能性：但是，這時若假定錯碼數(shù)不超過兩個，則存在兩種可能性：“000”錯一錯一位和位和“111”錯兩位都可能變成錯兩位都可能變成“100”，因而只能檢測出存在錯碼而無法糾因而只能檢測出存在錯碼而無法糾正錯碼正錯碼。分組碼的結(jié)構分組碼的結(jié)構將信息碼分組，為每組信息碼附加若干監(jiān)督碼的編碼稱為將信息碼分組，為每組信息碼附加若干監(jiān)督碼的編碼稱為分組碼 。在分組碼中，在分組碼中，監(jiān)督碼元僅監(jiān)督本碼組中的信息碼元監(jiān)督碼元僅監(jiān)督本碼組中的信息碼元。 信息位和監(jiān)督位的關系：舉例如下信

13、息位和監(jiān)督位的關系：舉例如下糾錯編碼的基本原理糾錯編碼的基本原理分組碼的一般結(jié)構分組碼的一般結(jié)構分組碼的符號：分組碼的符號：(n, k)N 碼組的總位數(shù)，又稱為碼組的長度（碼碼組的總位數(shù)，又稱為碼組的長度（碼長），長），k 碼組中信息碼元的數(shù)目，碼組中信息碼元的數(shù)目，n k r 碼組中的監(jiān)督碼元數(shù)目，或稱監(jiān)碼組中的監(jiān)督碼元數(shù)目，或稱監(jiān)督位數(shù)目。督位數(shù)目。 糾錯編碼的基本原理糾錯編碼的基本原理 v 碼重碼重：碼字中非零碼元的個數(shù)定義為該碼字的重量，：碼字中非零碼元的個數(shù)定義為該碼字的重量，簡稱碼重。如簡稱碼重。如“10011”碼字的碼重為碼字的碼重為3。v 碼距碼距：兩個等長碼字之間對應碼元不同

14、的兩個等長碼字之間對應碼元不同的數(shù)目，數(shù)目，即即兩個碼組之間對應位置上兩個碼組之間對應位置上1、0不同的位數(shù)，又叫漢明不同的位數(shù)，又叫漢明(Hamming)距通常用距通常用d表示。表示。10 1 1 0 碼重：碼重：301 1 0 0 2 距離：距離：3 糾錯編碼的基本原理糾錯編碼的基本原理碼距的幾何意義碼距的幾何意義對于對于3 3位的編碼組，可以在位的編碼組，可以在3 3維空間中說明碼距的幾何意義。維空間中說明碼距的幾何意義。 每個碼組的每個碼組的3 3個碼元的值個碼元的值( (a a1 1, , a a2 2, , a a3 3) )就是此立方體各頂點的坐標。就是此立方體各頂點的坐標。而上

15、述而上述碼距概念在此圖中就對應于各頂點之間沿立方體各邊行走的碼距概念在此圖中就對應于各頂點之間沿立方體各邊行走的幾何距離幾何距離。由此圖可以直觀看出，上例中由此圖可以直觀看出，上例中4 4個準用碼組之間的距離均為個準用碼組之間的距離均為2 2。(0,0,0)(0,0,1)(1,0,1)(1,0,0)(1,1,0)(0,1,0)(0,1,1)(1,1,1)a2a0a1糾錯編碼的基本原理糾錯編碼的基本原理v 最小碼距最小碼距：在一個碼字集合中，任意兩個碼字間距：在一個碼字集合中，任意兩個碼字間距離的最小值，即碼字集合中任意兩元素間的最小距離，離的最小值，即碼字集合中任意兩元素間的最小距離，記為記為

16、d dminmin或或d d0 0，例如例如11101110、10101010、10001000v 編碼效率：編碼效率：信息碼元數(shù)與碼長之比，通常用信息碼元數(shù)與碼長之比，通常用 表示，其中表示，其中k k為信息碼元的數(shù)目，為信息碼元的數(shù)目，n n為碼長為碼長。糾錯碼的抗干擾能力完全取決于許用碼字之間的距糾錯碼的抗干擾能力完全取決于許用碼字之間的距離，碼的最小距離越大，說明碼字間的最小差別越離，碼的最小距離越大，說明碼字間的最小差別越大，抗干擾能力就越強。大，抗干擾能力就越強。nk糾錯編碼的基本原理糾錯編碼的基本原理碼距和檢糾錯能力的關系碼距和檢糾錯能力的關系一種編碼的最小碼距一種編碼的最小碼距

17、d0的大小直接關的大小直接關系著這種編碼的檢錯和糾錯能力系著這種編碼的檢錯和糾錯能力 為檢測為檢測e個錯碼，要求最小碼距個錯碼，要求最小碼距 d0 e + 1碼距和檢糾錯能力的關系碼距和檢糾錯能力的關系【證】設一個碼組【證】設一個碼組A A位于位于OO點。若碼組點。若碼組A A中發(fā)生一個錯碼中發(fā)生一個錯碼，則我們可以認為，則我們可以認為A A的位置將移動至以的位置將移動至以O O點為圓心，點為圓心，以以1 1為半徑的圓上某點，但其位置不會超出此圓。為半徑的圓上某點，但其位置不會超出此圓。 若碼組若碼組A A中發(fā)生兩位錯碼，則其位置不會超出以中發(fā)生兩位錯碼，則其位置不會超出以O O點為圓心，以點

18、為圓心，以2 2為半徑的圓。因此，為半徑的圓。因此，只要最小碼距只要最小碼距不小于不小于3 3，碼組，碼組A A發(fā)生兩位以下錯碼時，發(fā)生兩位以下錯碼時，不可能變成另一個準用不可能變成另一個準用碼組，因而能檢測錯碼碼組，因而能檢測錯碼的位數(shù)等于的位數(shù)等于2 2。 0123BA漢明距離ed00 0: :晴晴, ,1 1: :雨雨若若10,0110,01。收端無法發(fā)現(xiàn)錯誤。收端無法發(fā)現(xiàn)錯誤00晴1001110011雨能發(fā)現(xiàn)一個錯誤禁用碼組插入插入1 1位監(jiān)督碼位監(jiān)督碼后具有后具有檢出檢出1 1位錯碼位錯碼的能的能力力, ,但不能予以糾正。但不能予以糾正。碼距和檢糾錯能力的關系碼距和檢糾錯能力的關系同

19、理，若一種編碼的最小碼距為同理，若一種編碼的最小碼距為d d0 0，則將能檢測，則將能檢測( (d d0 0 - 1) - 1)個個錯碼。反之，若要求檢測錯碼。反之，若要求檢測e e個錯碼，則最小碼距個錯碼，則最小碼距d d0 0至少應不至少應不小于小于( ( e e + 1)+ 1)。為了糾正為了糾正t t個錯碼，要求最小碼距個錯碼，要求最小碼距d d0 0 2 2t t + 1 + 1【證】圖中畫出碼組【證】圖中畫出碼組A A和和B B的距離為的距離為5 5。碼組。碼組A A或或B B若發(fā)生不多若發(fā)生不多于兩位錯碼，則其位置均不會超出半徑為于兩位錯碼，則其位置均不會超出半徑為2 2以原位置

20、為圓心以原位置為圓心的圓。這兩個圓是不重疊的。判決規(guī)則為：若接收碼組落于的圓。這兩個圓是不重疊的。判決規(guī)則為：若接收碼組落于以以A A為圓心的圓上就判決收到的是碼組為圓心的圓上就判決收到的是碼組A A，若落于以，若落于以B B為圓為圓心的圓上就判決為碼組心的圓上就判決為碼組B B。這樣，就能夠糾這樣，就能夠糾正兩位錯碼。正兩位錯碼。 BtA漢明距離012345td0碼距和檢糾錯能力的關系碼距和檢糾錯能力的關系000晴晴010001111000111雨雨晴晴在只有在只有1 1位錯碼位錯碼的情況下的情況下, ,可以判決哪位是錯碼可以判決哪位是錯碼并予以并予以糾正糾正, ,可以可以檢出檢出2 2位位

21、或或2 2位以下的錯碼。位以下的錯碼。100011101110雨雨碼距和檢糾錯能力的關系碼距和檢糾錯能力的關系若這種編碼中除碼組若這種編碼中除碼組A和和B外，還有許多種不同碼外，還有許多種不同碼組，但任兩碼組之間的碼距均不小于組，但任兩碼組之間的碼距均不小于5，則以各碼，則以各碼組的位置為中心以組的位置為中心以2為半徑畫出之圓都不會互相重為半徑畫出之圓都不會互相重疊。這樣，每種碼組如果發(fā)生不超過兩位錯碼都疊。這樣，每種碼組如果發(fā)生不超過兩位錯碼都將能被糾正。因此，當最小碼距將能被糾正。因此，當最小碼距d05時，能夠糾時，能夠糾正正2個錯碼，且最多能糾正個錯碼，且最多能糾正2個。若錯碼達到個。若

22、錯碼達到3個，個，就將落入另一圓上，從而發(fā)生錯判。故一般說來就將落入另一圓上，從而發(fā)生錯判。故一般說來，為糾正，為糾正t個錯碼，最小碼距應不小于個錯碼，最小碼距應不小于(2t + 1)。碼距和檢糾錯能力的關系碼距和檢糾錯能力的關系為糾正為糾正t個錯碼，同時檢測個錯碼，同時檢測e個錯碼，要求最小碼距個錯碼，要求最小碼距在解釋此式之前，先來分析下圖所示的例子。圖中碼組在解釋此式之前，先來分析下圖所示的例子。圖中碼組A和和B之之間距離為間距離為5。按照檢錯能力公式，最多能檢測。按照檢錯能力公式，最多能檢測4個錯碼，即個錯碼，即e = d0 1 = 5 1 = 4，按照糾錯能力公式糾錯時，能糾正，按照

23、糾錯能力公式糾錯時，能糾正2個錯碼。但是個錯碼。但是，不能同時作到兩者，因為當，不能同時作到兩者，因為當錯碼位數(shù)超過糾錯能力錯碼位數(shù)超過糾錯能力時，該碼組時，該碼組立即進入另一碼組的圓內(nèi)而被錯誤地立即進入另一碼組的圓內(nèi)而被錯誤地“糾正糾正”了。例如，碼組了。例如，碼組A若錯了若錯了3位，就會被誤認為碼組位，就會被誤認為碼組B錯了錯了2位造成的結(jié)果，從而被位造成的結(jié)果，從而被錯錯“糾糾”為為B。這就。這就是說，檢錯和糾錯是說，檢錯和糾錯公式不能同時成立公式不能同時成立或同時運用。或同時運用。 )(10tetedBtA漢明距離012345td0碼距和檢糾錯能力的關系碼距和檢糾錯能力的關系所以，為了

24、在可以糾正所以，為了在可以糾正t個錯碼的同時，能夠檢個錯碼的同時，能夠檢測測e個錯碼，就需要像下圖所示那樣，使某一碼個錯碼，就需要像下圖所示那樣，使某一碼組（譬如碼組組（譬如碼組A）發(fā)生發(fā)生e個錯誤之后所處的位置個錯誤之后所處的位置，與其他碼組（譬如碼組，與其他碼組（譬如碼組B）的糾錯圓圈至少）的糾錯圓圈至少距離等于距離等于1，不然將落在該糾錯圓上從而發(fā)生，不然將落在該糾錯圓上從而發(fā)生錯誤地錯誤地“糾正糾正”。因此，由此圖可以直觀看出。因此，由此圖可以直觀看出，要求最小碼距，要求最小碼距ABe1tt漢明距離)(10teted碼距和檢糾錯能力的關系碼距和檢糾錯能力的關系一個碼能檢測一個碼能檢測e個錯碼，則要求其最小碼個錯碼，則要求其最小碼dmine+1一個碼能糾正一個碼能糾正t個錯碼，則要求其最小個錯碼，則要求其最小dmin2t+1一個碼能糾正一個碼能糾正t個錯碼，同時能檢測個錯碼，同時能檢測e個錯碼，則要個錯碼，則要求其最小碼距求其最小碼距 dmine+t+1 (et)碼距和檢糾錯能力的關系碼距和檢糾錯能力的關系差錯控制編碼差錯控制編碼分類分類 從功能角度講從功能角度講, ,差錯碼分為檢錯碼和差錯碼分為檢錯碼和糾錯碼糾錯碼檢錯碼檢錯碼：用于發(fā)現(xiàn)差錯：用于發(fā)現(xiàn)差錯糾錯碼糾錯碼：能自動糾正差錯：能自動糾正差錯按照對信息序列的處理方法按照對信息序列的處