長江大學(xué)信息論與編碼典型例題

1、例1簡述最大離散熵定理。對于一個有m個符號的離散信源，其最大熵是多少？解：最大離散熵定理為：離散無記憶信源，等概率分布時熵最大。最大熵值為 H max = log2 m。例2什么是平均自信息(信息熵)？什么是平均互信息？比較一下兩個概念的異同之處。解：平均自信息為 H(X)-7 p(Xi) log p(Xi)i表示信源的平均不確定度，也表示平均每個信源消息所提供的信息量。平均互信息為 |(X;Y)- p(Xiyj)logPXyi jP(Xi)表示從Y獲得的關(guān)于每個 X的平均信息量，也表示發(fā)X前后Y的平均不確定性減少的量， 還表示通信前后整個系統(tǒng)不確定性減少的量。例3解釋等長信源編碼定理和無失真

2、變長信源編碼定理，說明對于等長碼和變長碼，最佳 碼的每符號平均碼長最小為多少？編碼效率最咼可達多少？K解：等長信源編碼定理：對于任意0, 0,只要 一Llogm_HL(X) ；，則當(dāng)L足夠長時必可使譯碼差錯變長信源編碼定理：只要 巴亠 ：也亠 1，一定存在一種無失真編碼。log mlog m等長碼和變長碼的最小平均碼長均為耳兇，編碼效率最高可達 100%log m例4解釋最小錯誤概率譯碼準(zhǔn)則，最大似然譯碼準(zhǔn)則和最小距離譯碼準(zhǔn)則，說明三者的關(guān) 系。解：最小錯誤概率譯碼準(zhǔn)則下，將接收序列譯為后驗概率最大時所對應(yīng)的碼字。最大似然譯碼準(zhǔn)則下，將接收序列譯為信道傳遞概率最大時所對應(yīng)的碼字。 最小距離譯碼

3、準(zhǔn)則下，將接收序列譯為與其距離最小的碼字。三者關(guān)系為：輸入為等概率分布時，最大似然譯碼準(zhǔn)則等效于最小錯誤概率譯碼準(zhǔn)則。 在二元對稱無記憶信道中，最小距離譯碼準(zhǔn)則等效于最大似然譯碼準(zhǔn)則。一 X P 1_0 al例5什么是保真度準(zhǔn)則？對二元信 |I源，其失真矩陣 D=,P(X) 一 p 1-p一 0求a 0a0時率失真函數(shù)的 Dmin和Dmax ？解：1)保真度準(zhǔn)則為：平均失真度不大于允許的失真度。2)因為失真矩陣中每行都有一個0,所以有Dmin =0，而Dmax =mn( 1 p)a, pa。例6 一平穩(wěn)二元信源，它在任意時間，不論以前發(fā)出過什么符號，都按p(0) =0.4,p(1)=0.6發(fā)出

4、符號，求 H(X2),H(X3 IX1X2)和平均符號熵lim 丄 H (X/2 XN)n- N解: H(X2) =2H(X) = 1.942 bit/2 個符號H(X3 | XN) = H(X3) =0.971 bit/ 符號 例7分別說明信源的概率分布和信道轉(zhuǎn)移概率對平均互信息的影響，說明平均互信息與信 道容量的關(guān)系。H(X1X2 Xn)NH (X)二 H(X) =0.971 bit/解：平均互信息相對于信源概率分布為上凸函數(shù)，相對于信道傳遞概率分布為下凹函數(shù)。平 均互信息的最大值為信道容量。例8二元無記憶信源，有p(0) = 0.25, p(1) =0.75求:(1 )某一信源序列由10

5、0個二元符號組成，其中有 m個“ 1”，求其自信息量?(2) 求100個符號構(gòu)成的信源序列的熵。解: 1)p(a) = p(0)100p(1)m = 0.251000.75mI (a) = -log 2 P(a) = 200 - mlog2 32)H(X100 ) = 100H(X) =81.128 bit/ 序列例9求以下三個信道的信道容量：R-0.10.20.30.40P3 =00000.3100000100*-00101001000P2 =0100001010-0100_001001 _00000 10.7000000.40.20.10.3解：R為對應(yīng)確定信道，因此有C1 =max H

6、(X) =log24 =2bit/符號。P2為具有歸并性能的信道，因此有C2二max H (Y) = log 2 3 =1.5995 bit/符號。P3為具有發(fā)散性能的信道，因此有C max H (X log 21.5995 bit/符號。例10寫出香農(nóng)公式，并說明其物理意義。當(dāng)信道帶寬為5000Hz，信噪比為30dB時求信道容量。P TjpC解:香農(nóng)公式為Ct =lim 1+ bit/ s，它是高斯加性白噪聲信道在單位時間內(nèi)的信道 嚴(yán)N0W丿容量，其值取決于信噪比和帶寬。Pp由 10lg30dB得1000，則 G = 5000log 2(11000) = 49836bit /sN0W ,B,

7、例11二元平穩(wěn)馬氏鏈，已知P(0/0)=0.9，P( 1/1)=0.8，求：(1) 求該馬氏信源的符號熵。(2) 每三個符號合成一個來編二進制Hufman碼，試建立新信源的模型，給出編碼結(jié)果。(3) 求每符號對應(yīng)的平均碼長和編碼效率?！盤(0) = 2/3P(1) = 1/3解 由；P(0) = P(0)P(0|0) + P(1)P(0|1)得極限概率解：1)由，得極限概率P(0) +P(1) =1則符號熵為H ： -比j =0.5533bit/符號2)新信源共8個序列，各序列的概率為 P(X1X2X3HP(X1)P(X2 | X1)P(X3 |X1X2)信源模型為0000.540010100

8、11 100 101 1101110.060.0130.053 0.0600070.0530.313一種編碼結(jié)果(依信源模型中的序列次序)100011為 0， 11, 1001， 1010, 1011, 10000, 100010,3)1亠佝)-0.682“ 符號3 y例12信源空間為I X IfP(X) 一0.4 0.2造二元和三元霍夫曼碼，計算其平均碼長和編碼效率。解：1)二元碼的碼字依序為：10, 11, 010, 011 ,S2S30.1S40.1K log 2 2S5S6S7S80.050.050.050.051010,1011,1000,1001。試分別構(gòu)=81.1%平均碼長L=2

9、.6bit/符號，編碼效率=0.972）三元碼的碼字依序為：1, 00, 02, 20, 21 , 22, 010, 011。-1001011G =010110，求00101n, k)碼的所有碼字。例13設(shè)線性分組碼的生成矩陣為平均碼長L=1.7bit/符號，編碼效率=0.936(1 )此(n, k)碼的n= ? k= ?，寫出此(2)求其對應(yīng)的一致校驗矩陣H。(3) 確定最小碼距，問此碼能糾幾位錯？列出其能糾錯的所有錯誤圖樣和對應(yīng)的伴隨式。(4) 若接收碼字為000110，用伴隨式法求譯碼結(jié)果。100101, 101110, 110011, 111000解：1) n=6, k=3，由C=mG

10、可得所有碼字為:1 0們2)此碼是系統(tǒng)碼，由G 知，P =1 10，則10 11 _1 1 0 1 0 01H =PTI=0 1 10 10I1 0 1 0 0 1 一3)由H可知，其任意2列線性無關(guān),而有3列線性相關(guān)，故有錯誤圖樣E伴隨式S = EH T100000101010000110001000011000100100000010010000001001000000, 001011 ,010110, 011101 ,dmin =3，能糾一位錯。4）由 S = rH T =110知 E= 010000,則 R = r E =010110例14二元對稱信道的信道矩陣為|0.9 0.1 I

11、,信道傳輸速度為1500二元符號/秒，設(shè)信源0.1 0.9 一為等概率分布，信源消息序列共有13000個二元符號，問：（1）試計算能否在10秒內(nèi)將信源消息序列無失真?zhèn)魉屯?？?） 若信源概率分布為p（0） =0.7, p（1） =0.3，求無失真?zhèn)魉鸵陨闲旁聪⑿蛄兄辽傩枰嚅L時間？解：1）信道容量為 C =1 -H （0.9,0.1） = 0.531bit/ 符號信源序列信息量為13000 H （0.5,0.5） = 7965bit而10秒內(nèi)信道能傳遞的信息量為1500 10 0.53仁7965bit故不能無失真地傳送完。2）此時信源序列信息量為13000 H （0.3,0.7） =1145

12、6.77bit2 2p(V |X)信息傳輸率為R p(Xjyj)log2冷 j 10.4558 bit/符號72 p(Xkyj)k4則 T 11456.7716.7567s0.4558x1500g (x) = x3 x 1，求:例15已知（7，4）循環(huán)碼的生成多項式（1）求該碼的編碼效率？（2） 求其對應(yīng)的一致校驗多項式h（x）(3)(4)解:寫出該碼的生成矩陣，校驗矩陣。若消息碼式為 m（x） = 1 x x2，kk =57.14%n1) n = 7,k = 4,求其碼字。2)h(x)x7 1g(x)x23)G(x)X6+ x4+ X31j011000_5 x+ x3+ x201011004

13、 x十X2十X1，G =0010110L x3+x+1 一10001011 一而4)10005C(x) =m(x)g(x) =xx41,C= 0110001例16黑白氣象傳真圖的消息只有黑色和白色兩種，求:1） 黑色出現(xiàn)的概率為 0.3，白色出現(xiàn)的概率為 0.7。給出這個只有兩個符號的信源X的數(shù)學(xué) 模型。假設(shè)圖上黑白消息出現(xiàn)前后沒有關(guān)聯(lián)，求熵；2） 假設(shè)黑白消息出現(xiàn)前后有關(guān)聯(lián)，其依賴關(guān)系為：P（白/白）=0.9，P（黑/白）=0.1，P（白 /黑）=0.2，P（黑/黑）=0.8，求其熵 H2（X）； 解：。信源模型為麗黑白2H(X) - p(ajlog2 卩佝)=0.881bit/ 符號2)由

14、卩)八斗 p(aj)p(ai|引),1 二1,2得p(白)=2/3,p(黑)=1/3J -p) p) =12 2則 H2(X)-八、p(ajp(aj |ai)log2 p(aj | a：)二 0.5533 b it/ 符號i4 J zi例17二元對稱信道如圖。1）若 p（0） =0.73, p（1） =0.25，求 H （X）和l（X;Y）；2）求該信道的信道容量和最佳輸入分布。=0解：1)H (X) =0.8113 bit/ 符號=0-1l(X;Y) =0.0616 bit/ 符號2）C =0.082 bit/符號，最佳輸入概率分布為等概率分布。0 10 0 0例18已知一（8，5）線性分組

15、碼的生成矩陣為0 0 10 0XX1 （是大學(xué)生）X2 （不是大學(xué)生）P(X)0.250.752） d min = 2例19居住某地區(qū)的女孩子有 25%是大學(xué)生，在女大學(xué)生中有 而女孩子中身高160厘米以上的占總數(shù)的一半。假如我們得知是大學(xué)生”的消息，問獲得多少信息量？解：設(shè)隨機變量X代表女孩子學(xué)歷設(shè)隨機變量Y代表女孩子身高p(y1 / 咅)=0.75 bit例20設(shè)離散無記憶信源,Xx)% =0、3/8卷可X3=2 x/3，其發(fā)出的信息為1/41/41/8.0 0 0 0 1 求：1）輸入為全00011和10100時該碼的碼字；2）最小碼距。10100101。解：1）輸入為00011時，碼字

16、為00011110;輸入為10100時，碼字為75%是身高160厘米以上的，“身高160厘米以上的某女孩Yy (身高 160cm)y2 (身高 160cm)P(Y)0.50.5已知：在女大學(xué)生中有 75%是身高160厘米以上的，即:身高160厘米以上的某女孩是大學(xué)生的信息量即：I(X1)log p(X1/yJlog 曲恥“)=_iog=1.415 bitp(yd0.5，求(1) 此消息的自信息量是多少？(2) 此消息中平均每符號攜帶的信息量是多少？解：(1)此消息總共有14個0、13個1、12個2、6個3，因此此消息發(fā)出的概率是:們 p = 丨 X - I X - I2丿14丿8；此消息的信息

17、量是：I = - log p =87.811 bit 此消息中平均每符號攜帶的信息量是：l/n =87.811/45=1.951 bit1/6，求:例21同時擲出兩個正常的骰子，也就是各面呈現(xiàn)的概率都為(1) “3和5同時出現(xiàn)”這事件的自信息；(2) “兩個1同時出現(xiàn)”這事件的自信息； 兩個點數(shù)的各種組合(無序)對的熵和平均信息量；(4) 兩個點數(shù)之和(即2, 3,，12構(gòu)成的子集)的熵;(5) 兩個點數(shù)中至少有一個是1的自信息量。解:(1)I (Xi) - -log p(Xi)1 丄6 _ 181-log 4.170 bit18p(x丄二丄6 636I (Xi) = -log p(Xi)-

18、log =5.170 bit36111213141516212223242526313233343536414243444546515253545556616263646566共有21種組合:其中11,22,33, 44,55,66的概率是兩個點數(shù)的排列如下:其他15個組合的概率是11X 6611 12 -661836H(X)=送 p(xi)log p(xj = 6 漢丄 log 丄+15 漢丄 log 丄=4.337 bit/symbol i36361818.丿8 9 10 11 12空1丄丄丄36 9 12 18 36(4)參考上面的兩個點數(shù)的排列，可以得出兩個點數(shù)求和的概率分布如下:X2345671 丄丄 11_P(X)(36 18 12 9 36 6H (X) - 八 P(x)og p(xji111111115511、