信息論第9章 糾錯(cuò)編碼

1、1第第9 9章章 糾錯(cuò)編碼糾錯(cuò)編碼2 因?yàn)橥ㄟ^(guò)分別進(jìn)行信源的數(shù)據(jù)壓縮編碼和信因?yàn)橥ㄟ^(guò)分別進(jìn)行信源的數(shù)據(jù)壓縮編碼和信道的數(shù)據(jù)傳輸編碼，即能做到有效又可靠地傳輸?shù)赖臄?shù)據(jù)傳輸編碼，即能做到有效又可靠地傳輸信息，又能大大地簡(jiǎn)化通信系統(tǒng)的設(shè)計(jì)，因此在信息，又能大大地簡(jiǎn)化通信系統(tǒng)的設(shè)計(jì)，因此在實(shí)際通信系統(tǒng)中得到廣泛應(yīng)用。實(shí)際通信系統(tǒng)中得到廣泛應(yīng)用。 針對(duì)各種不同信源如文本、語(yǔ)音、靜止圖像針對(duì)各種不同信源如文本、語(yǔ)音、靜止圖像、活動(dòng)圖像等數(shù)據(jù)壓縮的研究形成了數(shù)據(jù)壓縮理、活動(dòng)圖像等數(shù)據(jù)壓縮的研究形成了數(shù)據(jù)壓縮理論與技術(shù)；論與技術(shù)； 而針對(duì)信道編碼問(wèn)題的研究又形成了另一獨(dú)而針對(duì)信道編碼問(wèn)題的研究又形成了另一獨(dú)立

2、的分支立的分支-糾錯(cuò)碼理論糾錯(cuò)碼理論。34白噪聲白噪聲定義定義:白噪聲是指功率譜密度在整個(gè)頻域內(nèi)白噪聲是指功率譜密度在整個(gè)頻域內(nèi)均勻分布的噪聲。均勻分布的噪聲。 5附：附：定義定義白噪聲是指功率譜密度在整個(gè)頻域白噪聲是指功率譜密度在整個(gè)頻域內(nèi)均勻分布的噪聲。內(nèi)均勻分布的噪聲。 嚴(yán)格地說(shuō)，白噪聲只是一種理想化模型，因?yàn)閲?yán)格地說(shuō)，白噪聲只是一種理想化模型，因?yàn)閷?shí)際噪聲的功率譜密度不可能具有無(wú)限寬的帶實(shí)際噪聲的功率譜密度不可能具有無(wú)限寬的帶寬，否則它的平均功率將是無(wú)限大，是物理上寬，否則它的平均功率將是無(wú)限大，是物理上不可實(shí)現(xiàn)的。然而，白噪聲在數(shù)學(xué)處理上比較不可實(shí)現(xiàn)的。然而，白噪聲在數(shù)學(xué)處理上比較方

3、便，因此它是系統(tǒng)分析的有力工具。一般，方便，因此它是系統(tǒng)分析的有力工具。一般，只要一個(gè)噪聲過(guò)程所具有的頻譜寬度遠(yuǎn)遠(yuǎn)大于只要一個(gè)噪聲過(guò)程所具有的頻譜寬度遠(yuǎn)遠(yuǎn)大于它所作用系統(tǒng)的帶寬，并且在該帶寬中其頻譜它所作用系統(tǒng)的帶寬，并且在該帶寬中其頻譜密度基本上可以作為常數(shù)來(lái)考慮，就可以把它密度基本上可以作為常數(shù)來(lái)考慮，就可以把它作為白噪聲來(lái)處理。例如，熱噪聲和散彈噪聲作為白噪聲來(lái)處理。例如，熱噪聲和散彈噪聲在很寬的頻率范圍內(nèi)具有均勻的功率譜密度，在很寬的頻率范圍內(nèi)具有均勻的功率譜密度，通?？梢哉J(rèn)為它們是白噪聲。通?？梢哉J(rèn)為它們是白噪聲。6 7信息論與糾錯(cuò)編碼理論幾乎同時(shí)在二次大戰(zhàn)結(jié)束后信息論與糾錯(cuò)編碼理論

4、幾乎同時(shí)在二次大戰(zhàn)結(jié)束后不久誕生的。前者首先有不久誕生的。前者首先有shannon以他的不朽著作以他的不朽著作“通信的數(shù)學(xué)理論通信的數(shù)學(xué)理論”為標(biāo)志建立起來(lái)的，而后者則為標(biāo)志建立起來(lái)的，而后者則以以Hamming的經(jīng)典著作的經(jīng)典著作“糾錯(cuò)與檢錯(cuò)編碼糾錯(cuò)與檢錯(cuò)編碼”為代表。為代表。Shannon與與Hamming都在貝爾實(shí)驗(yàn)室工作，彼此都在貝爾實(shí)驗(yàn)室工作，彼此非常熟悉，在非常熟悉，在Shannon的文章中也利用了的文章中也利用了Hamming關(guān)于糾錯(cuò)編碼的結(jié)果。關(guān)于糾錯(cuò)編碼的結(jié)果。Shannon理論討論了信息的度量，以及對(duì)于信息表理論討論了信息的度量，以及對(duì)于信息表示和傳輸?shù)幕鞠拗?。示和傳輸?shù)?/p>

5、基本限制。Shannon的信道編碼定理表的信道編碼定理表明只要信息傳輸速率小于信道容量，則信息傳輸可明只要信息傳輸速率小于信道容量，則信息傳輸可以以任何小的錯(cuò)誤概率進(jìn)行。但是以以任何小的錯(cuò)誤概率進(jìn)行。但是Shannon并沒(méi)有并沒(méi)有告訴人們?nèi)绾稳?shí)現(xiàn)這一點(diǎn)。告訴人們?nèi)绾稳?shí)現(xiàn)這一點(diǎn)。Hamming提出的糾錯(cuò)提出的糾錯(cuò)編碼理論卻正是為了試圖解決這個(gè)問(wèn)題。編碼理論卻正是為了試圖解決這個(gè)問(wèn)題。8在通信中信源編碼、信道編碼與數(shù)據(jù)轉(zhuǎn)換編碼常常是同時(shí)使用的。在通信中信源編碼、信道編碼與數(shù)據(jù)轉(zhuǎn)換編碼常常是同時(shí)使用的。99.1基本概念加上適當(dāng)?shù)娜哂嘁约m正差錯(cuò)加上適當(dāng)?shù)娜哂嘁约m正差錯(cuò)去除或減少冗余去除或減少冗余1

6、0 通過(guò)在傳輸?shù)男畔⒋a元后通過(guò)在傳輸?shù)男畔⒋a元后增加一些多余的碼增加一些多余的碼元元(稱為校驗(yàn)元稱為校驗(yàn)元)，糾錯(cuò)編碼可以在信息損失或錯(cuò)，糾錯(cuò)編碼可以在信息損失或錯(cuò)誤后還能在接收端恢復(fù)原代碼。誤后還能在接收端恢復(fù)原代碼。 根據(jù)信息碼元和校驗(yàn)碼元之間不同的關(guān)系，根據(jù)信息碼元和校驗(yàn)碼元之間不同的關(guān)系，糾錯(cuò)碼按結(jié)構(gòu)分類糾錯(cuò)碼按結(jié)構(gòu)分類大致如下頁(yè)圖所示。大致如下頁(yè)圖所示。1112線性碼線性碼信息碼元與校驗(yàn)碼元之間呈線性關(guān)系。信息碼元與校驗(yàn)碼元之間呈線性關(guān)系。非線性碼非線性碼信息碼元與校驗(yàn)碼元之間不存在線性信息碼元與校驗(yàn)碼元之間不存在線性關(guān)系。關(guān)系。S 分組碼分組碼把信息序列以每把信息序列以每k個(gè)碼元分

7、組，然后個(gè)碼元分組，然后把每組把每組k個(gè)信息元按一定規(guī)律產(chǎn)生個(gè)信息元按一定規(guī)律產(chǎn)生r個(gè)多余的校驗(yàn)元個(gè)多余的校驗(yàn)元，輸出序列每組長(zhǎng)為，輸出序列每組長(zhǎng)為nk+r，則每一碼字的，則每一碼字的r個(gè)校驗(yàn)個(gè)校驗(yàn)元只與本碼字的元只與本碼字的k個(gè)信息冗有關(guān)，與別的碼字的信息個(gè)信息冗有關(guān)，與別的碼字的信息位無(wú)關(guān)，記為分組碼位無(wú)關(guān)，記為分組碼(n, k)。S 卷積碼卷積碼把信息序列以每把信息序列以每ko(通常較小通常較小)個(gè)碼元個(gè)碼元分段，編碼器輸出該段的校驗(yàn)元分段，編碼器輸出該段的校驗(yàn)元rn- ko不但與本段不但與本段的的ko個(gè)信息元有關(guān)，而且還與其前面?zhèn)€信息元有關(guān)，而且還與其前面m段的信息元有段的信息元有關(guān)，

8、故記為卷積碼關(guān)，故記為卷積碼(n，ko ，m) 。1314其中分組碼又可分循環(huán)碼和非循環(huán)碼：其中分組碼又可分循環(huán)碼和非循環(huán)碼： 循環(huán)碼循環(huán)碼該碼書的特點(diǎn)是，若將其全部碼字分成該碼書的特點(diǎn)是，若將其全部碼字分成若干組，則每組中任一碼字中碼元循環(huán)移位后仍是這若干組，則每組中任一碼字中碼元循環(huán)移位后仍是這組的碼字。組的碼字。 非循環(huán)碼非循環(huán)碼任一碼字中碼元的循環(huán)移位后不一定任一碼字中碼元的循環(huán)移位后不一定再是該碼書中的碼字再是該碼書中的碼字 。按照糾正錯(cuò)誤類型可分為糾正隨機(jī)錯(cuò)誤碼、糾正突發(fā)按照糾正錯(cuò)誤類型可分為糾正隨機(jī)錯(cuò)誤碼、糾正突發(fā)錯(cuò)誤碼、糾正隨機(jī)與突發(fā)錯(cuò)誤碼以及糾正同步錯(cuò)誤碼錯(cuò)誤碼、糾正隨機(jī)與突

9、發(fā)錯(cuò)誤碼以及糾正同步錯(cuò)誤碼等。等。 另外，按照每個(gè)碼元取值來(lái)分，有二元碼和另外，按照每個(gè)碼元取值來(lái)分，有二元碼和q元碼。元碼。目前傳輸系統(tǒng)或存儲(chǔ)系統(tǒng)大都采用二進(jìn)制的數(shù)字系統(tǒng)，目前傳輸系統(tǒng)或存儲(chǔ)系統(tǒng)大都采用二進(jìn)制的數(shù)字系統(tǒng)，所以一般提到的糾錯(cuò)碼都是指二元碼。所以一般提到的糾錯(cuò)碼都是指二元碼。15糾錯(cuò)編碼16 對(duì)于某一種編碼滿足上述要求是非常重要的。對(duì)于某一種編碼滿足上述要求是非常重要的。17n18分組碼1920編碼效率21線性分組碼22系統(tǒng)碼23漢明距離242526最小碼距27漢明重量28信道編碼提供了對(duì)于信息傳輸發(fā)生差錯(cuò)的控制能力。這種控制能力由編碼器的糾錯(cuò)能力與檢錯(cuò)能力來(lái)表征。檢錯(cuò)檢錯(cuò)是指當(dāng)

10、信息在信道上傳輸發(fā)生錯(cuò)誤時(shí)，譯碼器能發(fā)現(xiàn)發(fā)現(xiàn)傳輸有誤，并及時(shí)的告訴告訴接受者；而糾錯(cuò)糾錯(cuò)則是譯碼器能自動(dòng)糾正糾正這個(gè)錯(cuò)誤的能力。下面以重復(fù)碼為例說(shuō)明編碼的糾錯(cuò)和檢錯(cuò)能力。檢錯(cuò)與糾錯(cuò)：29例例1 考慮一個(gè)把考慮一個(gè)把1bit信息數(shù)據(jù)重復(fù)信息數(shù)據(jù)重復(fù)3次的重復(fù)編碼。該編碼器實(shí)現(xiàn)次的重復(fù)編碼。該編碼器實(shí)現(xiàn) “0” “000” ， “1” “111”這時(shí)這時(shí)n=3,k=1,r=2.接收到序列 譯出序列 000 0 001 ？ 010 ？ 011 ？ 100 ？ 101 ？ 110 ？ 111 1表中？表示接收到序列中有錯(cuò)。表中？表示接收到序列中有錯(cuò)。顯然一位和二位的錯(cuò)誤都可以顯然一位和二位的錯(cuò)誤都可以

11、被發(fā)現(xiàn)但譯碼器不知道錯(cuò)在哪里。被發(fā)現(xiàn)但譯碼器不知道錯(cuò)在哪里。比如接收到比如接收到“010”，譯碼器發(fā)現(xiàn)，譯碼器發(fā)現(xiàn)它既不是它既不是“000”，也不是，也不是“111”，所以肯定傳輸出了錯(cuò)，但它不清所以肯定傳輸出了錯(cuò)，但它不清楚這是由楚這是由“000”錯(cuò)一位，還是由錯(cuò)一位，還是由“111”錯(cuò)一位所致。錯(cuò)一位所致。因此，當(dāng)采用此表來(lái)譯碼時(shí)，可以因此，當(dāng)采用此表來(lái)譯碼時(shí)，可以檢測(cè)出最多檢測(cè)出最多2個(gè)錯(cuò)誤，也就是說(shuō)當(dāng)個(gè)錯(cuò)誤，也就是說(shuō)當(dāng)碼字發(fā)生一位或者兩位錯(cuò)誤時(shí)，碼字發(fā)生一位或者兩位錯(cuò)誤時(shí)，譯碼器能發(fā)現(xiàn)該序列有誤。譯碼器能發(fā)現(xiàn)該序列有誤。30例1 （續(xù)）如果采用下表方式譯碼，則上述重復(fù)碼可以糾正任何一位

12、錯(cuò)誤。接收到序列 譯出序列 000 0 001 0 010 0 011 1 100 0 101 1 110 1 111 1顯然表中的譯碼方法不能同時(shí)顯然表中的譯碼方法不能同時(shí)檢測(cè)出二位錯(cuò)誤。因?yàn)槿绻l(fā)生檢測(cè)出二位錯(cuò)誤。因?yàn)槿绻l(fā)生二位錯(cuò)誤，則譯碼器會(huì)錯(cuò)誤的二位錯(cuò)誤，則譯碼器會(huì)錯(cuò)誤的把它作為一位錯(cuò)誤而把它作為一位錯(cuò)誤而“糾正糾正”了。了。所以所以r=2的重復(fù)碼可以發(fā)現(xiàn)的重復(fù)碼可以發(fā)現(xiàn)二位錯(cuò)誤或者糾正一位錯(cuò)誤，二位錯(cuò)誤或者糾正一位錯(cuò)誤，但二者不能兼得。但二者不能兼得。31接收序列 譯出數(shù)據(jù) 接收序列 譯出數(shù)據(jù) 0000010000 000101001? 001001010? 0011？10111 010001100? 0101？11011 0110？11101 0111111111例例2。如果用。如果用r=3的重復(fù)編碼。該編碼器實(shí)現(xiàn)的重復(fù)編碼。該編碼器實(shí)現(xiàn) “0” “0000” ， “1” “1111”采用下表所示的譯碼方法，則可以檢測(cè)二位錯(cuò)誤，采用下表所示的譯碼方法，則可以檢測(cè)二位錯(cuò)誤，糾正一位錯(cuò)誤糾正一位錯(cuò)誤329.2糾錯(cuò)碼分類3334353637383940419.39.3線性分組碼線性分組碼424344454647484950515253549.3.2線性分組碼的檢糾錯(cuò)能力55565