第六章 有噪信道編碼

1、信息論與編碼信息論與編碼第六章第六章有噪信道編碼有噪信道編碼 信息論與編碼信息論與編碼6.1 譯碼準(zhǔn)則 與譯碼錯(cuò)誤概率 有噪聲信道編碼的主要目的是提高傳輸可靠性，增加抗干擾能力，因此也稱(chēng)為糾錯(cuò)編碼或抗干擾編碼。 信源編碼之后的碼字序列抗干擾能力很脆弱，在信道噪聲的影響下容易產(chǎn)生差錯(cuò)，為了提高通信系統(tǒng)的有效性和可靠性，要在信源編碼器和信道之間加上一個(gè)信道編碼器，信息論與編碼信息論與編碼6.1.1 譯碼準(zhǔn)則的含義譯碼準(zhǔn)則的含義一個(gè)例子一個(gè)例子影響通信系統(tǒng)可靠性的一個(gè)重要問(wèn)題是譯碼方式，可以通過(guò)一個(gè)例子看一下；有一個(gè)BSC信道，如圖所示。信息論與編碼信息論與編碼對(duì)于這樣一個(gè)信道，如果采用自然的譯碼準(zhǔn)

2、則，即收0判0，收1判1；這時(shí)可以明顯看到，當(dāng)信源先驗(yàn)概率的等概時(shí)p(0)=p(1)=1/2；這時(shí)收到Y(jié)判X的后驗(yàn)概率等于信道轉(zhuǎn)移概率，系統(tǒng)正確的譯碼概率為1/4，錯(cuò)誤譯碼概率為3/4。但如果采用另一種譯碼準(zhǔn)則，收0判1，收1判0；則系統(tǒng)正確的譯碼概率為3/4，錯(cuò)誤譯碼概率為1/4，通信的可靠性提高了。譯碼準(zhǔn)則譯碼準(zhǔn)則信息論與編碼信息論與編碼 這時(shí)定義一個(gè)收到y(tǒng)j后判定為xi的單值函數(shù)，即： F(yj)=xi (i=1,2,n; j=1,2,m)；這個(gè)函數(shù)稱(chēng)為譯碼函數(shù)。它構(gòu)成一個(gè)譯碼函數(shù)組，這些函數(shù)的值組成了譯碼準(zhǔn)則。 對(duì)于有n個(gè)輸入，m個(gè)輸出的信道來(lái)說(shuō)，可以有nm個(gè)不同的譯碼準(zhǔn)則。例如上面例

3、子中有4中譯碼準(zhǔn)則分別為： A:F(0)=0;F(1)=0 B:F(0)=0;F(1)=1 C:F(0)=1;F(1)=0 D:F(0)=1;F(1)=1信息論與編碼信息論與編碼6.1.2譯碼錯(cuò)誤概率 譯碼準(zhǔn)則確定之后，當(dāng)接收端收到一個(gè)yj后，則按譯碼準(zhǔn)則譯成F(yj)=xi，這時(shí)如果發(fā)送的為xi則為正確譯碼，如果發(fā)送的不是xi則為錯(cuò)誤譯碼。所以接收到y(tǒng)j后正確譯碼的概率就是接收端收到y(tǒng)j后，推測(cè)發(fā)送端發(fā)出xi的后驗(yàn)概率： Prj=PF(yj)=P(xi/yj) 而錯(cuò)誤譯碼的概率為收到y(tǒng)j后，推測(cè)發(fā)出除了xi之外其它符號(hào)的概率：Pej=Pe/yj=1-PF(yj)=xi/yj 信息論與編碼信息

4、論與編碼 其中e表示除了xi之外的所有其它信源符號(hào)的集合。然后對(duì)所有的yj取平均，則平均正確譯碼概率為：PP yPp yp F yxyrjrjjmjjijjm()() ()/11同樣可以得到平均錯(cuò)誤譯碼概率為：Pp yP eyp yP F yxyejjjjijjmjm() /()()/111信息論與編碼信息論與編碼6.1.3最大后驗(yàn)概率準(zhǔn)則最大后驗(yàn)概率準(zhǔn)則 由平均錯(cuò)誤譯碼概率的表達(dá)式可以看出，錯(cuò)誤譯碼概率與信道輸出端隨機(jī)變量Y的概率分布p(yj)有關(guān)，也與譯碼準(zhǔn)則有關(guān)。當(dāng)信道信道轉(zhuǎn)移概率p(yj/xi)確定后，而且信源統(tǒng)計(jì)特性p(xi)確定之后，信道輸出端的p(yj)也就確定了。因?yàn)椋簆(xi

5、,yj)=p(xi)p(yj/xi); 而p(yj)可以由p(xi,yj)的(i=1,2, n)求和得到。 因此，在這種情況下，平均錯(cuò)誤譯碼概率只與譯碼準(zhǔn)則有關(guān)了。通過(guò)選擇譯碼準(zhǔn)則可以使平均譯碼概率達(dá)到最小值。 當(dāng)式中的每一項(xiàng)的PF(yj)=xi/yj達(dá)到最大值時(shí)，平均錯(cuò)誤譯碼概率就可以為最小值。 設(shè)信源X的信源空間為：信息論與編碼信息論與編碼 收到每一個(gè)yj(j=1,2,m)后，推測(cè)發(fā)送為xi(i=1,2,n)的后驗(yàn)概率共有n個(gè)，為：p(x1/yj),p(x2/yj),p(xn/yj)。這其中必有一個(gè)為最大的，設(shè)其為：p(x*/yj)，即有：p(x*/yj)p(xi/yj) (對(duì)一切的i)這

6、表明：收到符號(hào)yj后就譯為輸入符號(hào)x*，即譯碼函數(shù)選為：F(yj)=a* (j=1,2,m)這種譯碼準(zhǔn)則稱(chēng)為“最大后驗(yàn)概率準(zhǔn)則”。信息論與編碼信息論與編碼 這個(gè)表達(dá)式平均錯(cuò)誤譯碼概率的最小值，是把每一個(gè)yj對(duì)應(yīng)的后驗(yàn)概率排除后再連續(xù)求和。 從表達(dá)式中可以看到，這個(gè)最小值與信源先驗(yàn)概率和信道轉(zhuǎn)移概率有關(guān)，特別是信道轉(zhuǎn)移概率，如果除了p(yj/x*)外，其它的項(xiàng)多很小，錯(cuò)誤譯碼概率會(huì)減小。信息論與編碼信息論與編碼6.1.4 最大似然準(zhǔn)則最大似然準(zhǔn)則 使用最大后驗(yàn)概率譯碼準(zhǔn)則必須已知后驗(yàn)概率，但信道的統(tǒng)計(jì)特性描述總是給出信道轉(zhuǎn)移概率，因此利用信道轉(zhuǎn)移概率的譯碼準(zhǔn)則。 由概率中的貝葉斯定理可有：p x

7、yp xp yxp yijijij(/)() (/)()p xyp xp yxp yjjj(/)() (/)()*信息論與編碼信息論與編碼這樣，根據(jù)最大后驗(yàn)概率譯碼準(zhǔn)則，如果 p(x*)p(yj/x*)p(xi)p(yj/xi) (i=1,2,n) 就等于：p(x*/yj)p(xi/yj) 則選擇譯碼準(zhǔn)則：F(yj)=x* (j=1,2,n) 這樣，可以看到當(dāng)信道輸入符號(hào)集X的先驗(yàn)概率為等概時(shí)p(xi)=1/n，比較上面三個(gè)式子，最大后驗(yàn)概率可以用最大信道轉(zhuǎn)移概率來(lái)取代。 這時(shí)，在X的先驗(yàn)概率為等概時(shí)，如果p(yj/x*)是yj相應(yīng)的n個(gè)信道轉(zhuǎn)移概率 p(yj/x1),p(yj/x2),p(y

8、j/xn)中的最大者，則我們就將yj譯成x*，這種譯碼方法稱(chēng)為“最大似然譯碼準(zhǔn)則”。 信息論與編碼信息論與編碼最大似然譯碼準(zhǔn)則利用了信道轉(zhuǎn)移概率，而不用后驗(yàn)概率，將會(huì)更方便。為了減小錯(cuò)誤譯碼概率，主要方法是改變信道轉(zhuǎn)移概率，信息論與編碼信息論與編碼6.2信道編碼定理信道編碼定理定理：有噪聲信道編碼定理（Shannon第二編碼定理） 如一個(gè)離散有噪聲信道有n個(gè)輸入符號(hào)，m個(gè)輸出符號(hào)，信道容量為C。當(dāng)信道的熵速率RC時(shí)，只要碼長(zhǎng)足夠長(zhǎng)，總可以找到一種編碼方法及譯碼準(zhǔn)則，使信道輸出端的平均錯(cuò)誤譯碼概率達(dá)到任意小，pe=。當(dāng)RC時(shí)，則不可能找到一種編碼方法及譯碼準(zhǔn)則，使信道輸出端的平均錯(cuò)誤譯碼概率達(dá)到

9、任意小。信息論與編碼信息論與編碼 編碼定理的證明比較復(fù)雜，主要參考課本140頁(yè) 這個(gè)定理是一個(gè)存在定理，指出錯(cuò)誤率趨于0的編碼方法是存在的。 定理表明，在錯(cuò)誤率趨于0的同時(shí)，還可以使R趨于C，這是具有理論指導(dǎo)意義的。信息論與編碼信息論與編碼引入冗余 一個(gè)BSC信道，輸入為X=0，1，且為等概分布，信道模型為：信息論與編碼信息論與編碼 按最大似然譯碼準(zhǔn)則為：F(0)=0; F(1)=1; pe=0.01這里沒(méi)有采用任何信道編碼。 信息論與編碼信息論與編碼編譯碼方法將0編為000，1編為111。這時(shí)的可用碼字為8；分別為：X1=000 X2=001 X3=010 X4=100X5=011 X6=1

10、10 X7=101 X8=111而許用碼字為000和111，相當(dāng)于信道輸入為X1=000，X2=111，而信道輸出端為：Y1=000；Y2=001；Y3=010；Y4=100Y5=011；Y6=110；Y7=101；Y8=111這時(shí)的信道轉(zhuǎn)移矩陣為：信息論與編碼信息論與編碼這時(shí)如果按最大似然法則譯碼，將為：F(Y1)=F(Y2)=F(Y3)=F(Y4)=X1=000F(Y5)=F(Y6)=F(Y7)=F(Y8)=X2=111錯(cuò)誤譯碼概率為：Pe 310-4可見(jiàn)簡(jiǎn)單重復(fù)碼可以將錯(cuò)誤譯碼概率下降兩個(gè)數(shù)量級(jí)。這是三次方法；可以看出如果是五次重復(fù)碼，誤碼率還要降低 信息論與編碼信息論與編碼 6.3 信

11、道編碼信道編碼信道編碼又稱(chēng)為差錯(cuò)控制編碼，簡(jiǎn)稱(chēng)為糾錯(cuò)編碼，即在信息序列中按一定的規(guī)則附加若干監(jiān)督碼元，以便對(duì)信息傳輸（或存儲(chǔ)）起檢錯(cuò)檢錯(cuò)與糾錯(cuò)糾錯(cuò)作用，目的在于提高通信（或存儲(chǔ)）的可靠性，減低提高通信（或存儲(chǔ)）的可靠性，減低誤碼率誤碼率。信息論與編碼信息論與編碼6.3.1分類(lèi)信息論與編碼信息論與編碼幾個(gè)基本概念碼字空間： 如果原始信源空間有M個(gè)碼字，對(duì)其進(jìn)行q元等長(zhǎng)碼的信道編碼，碼長(zhǎng)為N，信道碼字空間的所有碼字為qN個(gè)，編碼器將在這qN個(gè)可用碼字中選擇M個(gè)碼字分別代表原始信源中的M個(gè)碼字，信道編碼碼字空間的這M個(gè)碼字稱(chēng)為“許用碼字”，而另外的qN-M個(gè)碼字稱(chēng)為“禁用碼字”。為了實(shí)現(xiàn)糾錯(cuò)編碼，一

12、定有qNM。這M個(gè)許用碼字也稱(chēng)為一個(gè)碼組，或稱(chēng)為碼字集合。信息論與編碼信息論與編碼漢明距離：(Hamming distance)在一個(gè)碼組（碼字集合）中，任意兩個(gè)等長(zhǎng)碼字之間，如果有d個(gè)相對(duì)應(yīng)的碼元不同，則稱(chēng)d為這兩個(gè)碼字的漢明距離。 例如：和為碼組X中的兩個(gè)不同碼字，X為一個(gè)長(zhǎng)度為N的二元碼組，其中： =a1,a2,aN ai0,1 =b1,b2,bN bi0,1 則與的漢明距離為： d=0表明為全同碼，d=N表明為全異碼，如果用模2加法的概念，有 模2 加法等同于“異或”運(yùn)算 信息論與編碼信息論與編碼 最小碼距： dabiiiN( ,) 1在一個(gè)碼字集合中，任何兩個(gè)碼字之間的漢明距離組成一

13、個(gè)元素集合，D(,),這個(gè)集合中的最小值稱(chēng)為這個(gè)碼字集合的最小漢明距離，簡(jiǎn)稱(chēng)最小碼距，記為：dmin。dmin=mind(,) ,X 信息論與編碼信息論與編碼碼字重量（漢明重量）(Hamming weight) 在二元編碼的碼字集合中，碼字中“1”碼元的個(gè)數(shù)稱(chēng)為這個(gè)碼字的重量。記為：W() 信息論與編碼信息論與編碼舉例: 氣象臺(tái)預(yù)報(bào)天氣 信碼 監(jiān)督元 碼字 （偶校驗(yàn)）傳輸中錯(cuò)一位 晴 00 0 （000）100，010，001 云 01 1 （011） 111，001，010 陰 10 1 （101） 001，111，100 雨 11 0 （110） 010，100，111 許用碼字許用碼字

14、禁用碼組禁用碼組 可檢一位錯(cuò)，之所以能檢錯(cuò)，是因?yàn)橐肓丝蓹z一位錯(cuò)，之所以能檢錯(cuò)，是因?yàn)橐肓巳哂啵ń哂啵ń么a組）用碼組）信息論與編碼信息論與編碼 例例2 可檢查出2位錯(cuò)。附加兩個(gè)監(jiān)督元，設(shè)只有“晴”、“雨”兩種信息: 信碼 監(jiān)督元 碼字 傳輸中錯(cuò)一位 晴 0 00 （000）100，010，001 0 雨 1 11 （111） 011，101，110 1 可糾1位錯(cuò)（000）（111）許用碼字許用碼字 ,其他為禁用碼字其他為禁用碼字.在例2中，若編碼規(guī)則為 晴 011， 雨 000， 則無(wú)糾錯(cuò)能力。當(dāng)發(fā)生1位錯(cuò)時(shí)：（011）111，001，010（000） 001，100，010則不能糾

15、1位錯(cuò)，但仍能檢1位錯(cuò)。信息論與編碼信息論與編碼糾、檢錯(cuò)能力與最小距離糾、檢錯(cuò)能力與最小距離d0之間的關(guān)系之間的關(guān)系 一個(gè)碼能夠檢測(cè)出min1dtd個(gè)錯(cuò)誤；只用于糾錯(cuò)，能糾正min12cdtmin1cdttd個(gè)錯(cuò)誤；用于既糾tc個(gè)錯(cuò)，又檢td個(gè)錯(cuò)信息論與編碼信息論與編碼6.3.2線(xiàn)性分組碼 分組碼是一種代數(shù)編碼，它的基本關(guān)系一個(gè)碼字包括獨(dú)立的信息元和監(jiān)督元，其監(jiān)督元與信息元之間是一種代數(shù)關(guān)系，如果這種代數(shù)關(guān)系為線(xiàn)性的則稱(chēng)為線(xiàn)性分組碼。分組碼的編碼器的模型為：信息論與編碼信息論與編碼 m為編碼器的輸入，稱(chēng)為信息碼元（信息位），它由k位碼元組成。C為編碼器的輸出，稱(chēng)為碼字矢量，它由n位碼元組成，其

16、中有k位信息元，r=n-k位監(jiān)督元。 線(xiàn)性分組碼：線(xiàn)性分組碼：監(jiān)督元與信息元之間的關(guān)系可用一組線(xiàn)性方程組來(lái)描述的(n, k)分組碼。信息論與編碼信息論與編碼以(7,4)漢明碼為例簡(jiǎn)單介紹 N=7,k=4,r=3.C=c6,c5,c4,c3,c2,c1,c0；其中c6,c5,c4,c3為信息位，c2,c1,c0為監(jiān)督位。信息論與編碼信息論與編碼 由HCT=0可知：監(jiān)督方程為：c2=c5+c4+c3c1=c6+c4+c3c0=c6+c5+c3其中加號(hào)為”模2和”規(guī)則.信息論與編碼信息論與編碼 根據(jù)這個(gè)方程組可以進(jìn)行編碼。例如信息碼元m=1011，則有c2=c5+c4+c3=0+1+1=0c1=c6

17、+c4+c3=1+1+1=1c0=c6+c5+c3=1+0+1=0 則漢明碼字C=1011010。 信息論與編碼信息論與編碼 假如接收碼字為R=0100101可以看到：ST=HRT=0這時(shí)表明無(wú)差錯(cuò)；如果接收碼字有一位差錯(cuò)，R=0110101；即錯(cuò)誤圖樣E=0010000；接收碼字的第三位錯(cuò)。這時(shí)校驗(yàn)子矢量為：信息論與編碼信息論與編碼 可見(jiàn)這時(shí)校驗(yàn)子ST不為0，譯碼器認(rèn)為有錯(cuò)，且正好等于H的第三列，表明接收碼字的第三位碼元錯(cuò)了。這時(shí)判斷發(fā)送碼字位0100101，譯碼正確。信息論與編碼信息論與編碼 如果接收碼字由兩位差錯(cuò)，R=0111101；即錯(cuò)誤圖樣E=0011000；接收碼字的第三、四位錯(cuò)。這時(shí)校驗(yàn)子矢量為：信息論與編碼信息論與編碼 可見(jiàn)這時(shí)，校驗(yàn)子矢量不為0，但是如果這時(shí)接收機(jī)按原來(lái)的譯碼方法，將認(rèn)為第7位出錯(cuò)。但如果接收機(jī)設(shè)計(jì)為檢錯(cuò)系統(tǒng)，當(dāng)校驗(yàn)子不為0，就認(rèn)為有錯(cuò)。因?yàn)?7,4)漢明碼的最小碼距為3 (31+2+1)，其不具備一種方法同時(shí)具有糾錯(cuò)檢錯(cuò)能力.信息論與編碼信息論與編碼 注意：糾錯(cuò)碼的選用要小心，要根據(jù)信道注意：糾錯(cuò)碼的選用要小心，要根據(jù)信道條件來(lái)確定，如果信道較差，而使用的糾條件來(lái)確定，如果信道較差，而使用的糾錯(cuò)碼能力不夠，可能使譯碼錯(cuò)誤反而增加，錯(cuò)碼能