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

1、例題例1簡(jiǎn)述最大離散熵定理。對(duì)于一個(gè)有m個(gè)符號(hào)的離散信源，其最大熵是多少?解：最大離散熵定理為：離散無(wú)記憶信源，等概率分布時(shí)熵最大。最大熵值為H max log2 m。例2什么是平均自信息(信息熵)？什么是平均互信息？比較一下兩個(gè)概念的異同之處。解：平均自信息為 H(X)p(Xi) log p(Xi)iP(Xiyj)logP(x I yj)P(Xi)平均互信息為l(X;Y)表示從Y獲得的關(guān)于每個(gè)表示信源的平均不確定度，也表示平均每個(gè)信源消息所提供的信息量。x的平均信息量，也表示發(fā)X前后丫的平均不確定性減少的量,還表示通信前后整個(gè)系統(tǒng)不確定性減少的量。例3解釋等長(zhǎng)信源編碼定理和無(wú)失真變長(zhǎng)信源編碼

2、定理，說(shuō)明對(duì)于等長(zhǎng)碼和變長(zhǎng)碼，最佳 碼的每符號(hào)平均碼長(zhǎng)最小為多少？編碼效率最咼可達(dá)多少？解：等長(zhǎng)信源編碼定理：對(duì)于任意 時(shí)必可使譯碼差錯(cuò)<。>0,K>0,只要 log mLHl(X)，則當(dāng)L足夠長(zhǎng)變長(zhǎng)信源編碼定理：只要H(X)log m等長(zhǎng)碼和變長(zhǎng)碼的最小平均碼長(zhǎng)均為K ()1, 一定存在一種無(wú)失真編碼。log mH (X)，編碼效率最咼可達(dá) 100%。log m例4解釋最小錯(cuò)誤概率譯碼準(zhǔn)則，最大似然譯碼準(zhǔn)則和最小距離譯碼準(zhǔn)則，說(shuō)明三者的關(guān) 系。解：最小錯(cuò)誤概率譯碼準(zhǔn)則下，將接收序列譯為后驗(yàn)概率最大時(shí)所對(duì)應(yīng)的碼字。最大似然譯碼準(zhǔn)則下，將接收序列譯為信道傳遞概率最大時(shí)所對(duì)應(yīng)的碼

3、字。最小距離譯碼準(zhǔn)則下，將接收序列譯為與其距離最小的碼字。三者關(guān)系為：輸入為等概率分布時(shí)，最大似然譯碼準(zhǔn)則等效于最小錯(cuò)誤概率譯碼準(zhǔn)則。 在二元對(duì)稱無(wú)記憶信道中，最小距離譯碼準(zhǔn)則等效于最大似然譯碼準(zhǔn)則。源，其失真矩陣DP例5什么是保真度準(zhǔn)則？對(duì)二元信P(X)求a 0a>0時(shí)率失真函數(shù)的 Dmin和Dmax ？ 解：1)保真度準(zhǔn)則為：平均失真度不大于允許的失真度。2)因?yàn)槭д婢仃囍忻啃卸加幸粋€(gè)0,所以有Dmin 0，而Dmax min( 1 p)a, pa。例6 一平穩(wěn)二元信源，它在任意時(shí)間，不論以前發(fā)出過(guò)什么符號(hào)，都按p(0)0.4, p(1) 0.6發(fā)出符號(hào)，求H(X2),H(X3以必2

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

5、 m個(gè)“ 1”，求其自信息量?(2) 求100個(gè)符號(hào)構(gòu)成的信源序列的熵。解: 1)p(a) p(0)100 m p(1)m 0.25100 m 0.75mI (a) log 2 p(a) 200 mlog2 3log2 42 bit/ 符號(hào)。C1 maxH(X)P2為具有歸并性能的信道，因此有 C2P3為具有發(fā)散性能的信道，因此有 C3max H (Y) log2 3 1.5995 bit/ 符號(hào)。 max H (X) log2 31.5995 bit/ 符號(hào)。例10寫出香農(nóng)公式，并說(shuō)明其物理意義。當(dāng)信道帶寬為5000Hz，信噪比為30dB時(shí)求信道容量。解：香農(nóng)公式為CtTim 1 N0Wbi

6、t/s，它是高斯加性白噪聲信道在單位時(shí)間內(nèi)的信道2)H(X100 )100H(X)81.128 bit/ 序列1000010100例9求以下三個(gè)信道的信道容量：P11000P2010000101001000010010.10.2 0.3 0.4000000P300000.30.700000 0 0 0000.40.20.10.3解：R為一一對(duì)應(yīng)確定信道，因此有容量，其值取決于信噪比和帶寬。由 10lgPN0WP30dB 得 NW1000，則 Ct5000 log 2(1 1000)49836bit / s例11二元平穩(wěn)馬氏鏈，已知P(0/0)=0.9，P( 1/1)=0.8，求：(1) 求該馬

7、氏信源的符號(hào)熵。(2) 每三個(gè)符號(hào)合成一個(gè)來(lái)編二進(jìn)制Hufman碼，試建立新信源的模型，給出編碼結(jié)果。(3) 求每符號(hào)對(duì)應(yīng)的平均碼長(zhǎng)和編碼效率。解：1)由眾常羅P(1)P(0|1)得極限概率P(0)2/3P(1)1/3則符號(hào)熵為H H0.5533bit/符號(hào)2)新信源共8個(gè)序列，各序列的概率為 P(X1X2X3) P(X1)P(X2 | X1)P(X3 |X1X2)信源模型為0000010100111001011101110.540.060.0130.053 0.060.0070.0530.313一種編碼結(jié)果（依信源模型中的序列次序）100011為 0, 11, 1001, 1010, 101

8、1, 10000, 100010,3) K1P(aJKj0.682 bit/ 符號(hào)3 i 1HK log 2 281.1%X例12信源空間為s1 s2S3S4S5S6S7s8試分別構(gòu)P(X)0.4 0.20.10.10.050.050.050.05造二兀和三?；舴蚵a，計(jì)算其平均碼長(zhǎng)和編碼效率。解：1）二元碼的碼字依序?yàn)椋?0, 11,010,011 ,1010,1011,1000,1001 o平均碼長(zhǎng)L=2.6bit/符號(hào)，編碼效率=0.972）三元碼的碼字依序?yàn)椋?, 00,02,20,2122,010,011 o平均碼長(zhǎng)L=1.7bit/符號(hào)，編碼效率=0.93(6100101例13設(shè)線

9、性分組碼的生成矩陣為G010110 ,求:001011（1 ）此（n, k）碼的n= ? k= ?，寫出此（n, k）碼的所有碼字。（2）求其對(duì)應(yīng)的一致校驗(yàn)矩陣Ho（3）確定最小碼距，問此碼能糾幾位錯(cuò)？列出其能糾錯(cuò)的所有錯(cuò)誤圖樣和對(duì)應(yīng)的伴隨式。（4）若接收碼字為000110，用伴隨式法求譯碼結(jié)果。解：1） n=6, k=3，由C=mG可得所有碼字為：000000, 001011, 010110, 011101 , 100101, 101110, 110011, 1110001012)此碼是系統(tǒng)碼，由G知，P110，則01111 0 100H PT|01 1 01010 1 0013)由H可知，

10、其任意2列線性無(wú)關(guān)，而有3列線性相關(guān)，故有dmin3，能糾一位錯(cuò)。錯(cuò)誤圖樣E伴隨式SEHT1000001010100001100010000110001001000000100100000010014)由 S rH T 110知 E= 010000,則 R r E 0101100.9 0.1例14二元對(duì)稱信道的信道矩陣為，信道傳輸速度為1500二元符號(hào)/秒，設(shè)信源0.1 0.9為等概率分布，信源消息序列共有13000個(gè)二元符號(hào)，問：(1) 試計(jì)算能否在10秒內(nèi)將信源消息序列無(wú)失真?zhèn)魉屯辏?2) 若信源概率分布為p(0) 0.7, p(1)0.3，求無(wú)失真?zhèn)魉鸵陨闲旁聪⑿蛄兄辽傩枰嚅L(zhǎng)時(shí)間？解

11、：1)信道容量為C 1 H (0.9.0.1)0.531bit/符號(hào)信源序列信息量為13000 H (0.5,0.5)7965bit而10秒內(nèi)信道能傳遞的信息量為1500 10 0.53仁7965bit故不能無(wú)失真地傳送完。2)此時(shí)信源序列信息量為13000 H (0.3,0.7)11456.77bit信息傳輸率為Rp(Xiyj)log2i 1 j 1p(yj |Xi)20.4558 bit/ 符號(hào)p(Xkyj)k 1則 T 11456.7716.7567s0.4558 1500例15已知(7，4)循環(huán)碼的生成多項(xiàng)式 g(x) X3 X 1，求:(1) 求該碼的編碼效率？(2) 求其對(duì)應(yīng)的一致

12、校驗(yàn)多項(xiàng)式h(x)解：1) n7,k4,k 57.14%n2) h(x)x714 X2XX1g(x)6 X43XX1011005 X32XX0101103) G(x)42 1 XX，G001011X3 XX 1000101(3) 寫出該碼的生成矩陣，校驗(yàn)矩陣。(4) 若消息碼式為 m(x) 1 x x2，求其碼字。00而011110 10 00 1110 100 0 1110 14) C(X)54m(x)g(x) x x 1,C0110001例16黑白氣象傳真圖的消息只有黑色和白色兩種，求:1)黑色出現(xiàn)的概率為0.3，白色出現(xiàn)的概率為0.7。給出這個(gè)只有兩個(gè)符號(hào)的信源X的數(shù)學(xué)模型。假設(shè)圖上黑白

13、消息出現(xiàn)前后沒有關(guān)聯(lián)，求熵；0.8，求其熵 H2(X)； a2白0.72)假設(shè)黑白消息出現(xiàn)前后有關(guān)聯(lián)，其依賴關(guān)系為：P(白/白)0.9，P(黑/白)0.1，P(白/黑)0.2，P(黑/黑)一q 黑解：1)信源模型為0.3H(X)p(aj log? p(aj 0.881bit/ 符號(hào)i 122)由 P(ai)r P(aj)P(ai laj)，l 1,2 得 p(白) 2 / 3, p(黑)1/3 p) p®)12 2則 H2(X)p(ajp(aj lajlog? p(aj |aj 0.5533 b it/ 符號(hào)i 1 j 1例17二元對(duì)稱信道如圖。1) 若 p(0)0.73, p(1)

14、0.25，求 H (X)和l(X;Y);2）求該信道的信道容量和最佳輸入分布。解：1)H (X)0.8113 bit/ 符號(hào)可=0=0I(X;Y) 0.0616 bit/ 符號(hào)2)C 0.082 b it/符號(hào)，最佳輸入概率分布為等概率分卜布。1000011101000100例18已知一（8，5）線性分組碼的生成矩陣為°01000100001000100001111求：1）輸入為全00011和10100時(shí)該碼的碼字；2）最小碼距。解：1）輸入為00011時(shí)，碼字為00011110;輸入為10100時(shí)，碼字為10100101。75%是身高160厘米以上的，“身高160厘米以上的某女孩X

15、X1 （是大學(xué)生）X2 （不是大學(xué)生）P(X)0.250.752）d min 2例19居住某地區(qū)的女孩子有 25%是大學(xué)生，在女大學(xué)生中有 而女孩子中身高160厘米以上的占總數(shù)的一半。假如我們得知是大學(xué)生”的消息，問獲得多少信息量？解：設(shè)隨機(jī)變量X代表女孩子學(xué)歷設(shè)隨機(jī)變量Y代表女孩子身高Yy (身高 >160cm)y2 (身高 <160cm)P(Y)0.50.5已知：在女大學(xué)生中有 75%是身高160厘米以上的，即:p(y1 / 咅)0.75 bit即：1（為/力）logp（X1/yJ.p(X1)p(yJX1), 0.25 0.75bitloglog1.415 bitP(%)0.5

16、X例20設(shè)離散無(wú)記憶信源P（X）x-! 0 x2 1 x3 2 x4 31234，其發(fā)出的信息為3/81/41/41/8身高160厘米以上的某女孩是大學(xué)生的信息量，求(1) 此消息的自信息量是多少？(2) 此消息中平均每符號(hào)攜帶的信息量是多少？解：(1)此消息總共有14個(gè)0、13個(gè)1、12個(gè)2、6個(gè)3，因此此消息發(fā)出的概率是:14253184此消息的信息量是:618I log p87.811 bit(2)此消息中平均每符號(hào)攜帶的信息量是：|/n 87.811/45 1.951 bit例21同時(shí)擲出兩個(gè)正常的骰子，也就是各面呈現(xiàn)的概率都為1/6，求：(1) “3和5同時(shí)出現(xiàn)”這事件的自信息；(2

17、) “兩個(gè)1同時(shí)出現(xiàn)”這事件的自信息； 兩個(gè)點(diǎn)數(shù)的各種組合(無(wú)序)對(duì)的熵和平均信息量；(4) 兩個(gè)點(diǎn)數(shù)之和(即2, 3,，12構(gòu)成的子集)的熵；(5) 兩個(gè)點(diǎn)數(shù)中至少有一個(gè)是1的自信息量。p( Xi)11 111解：(1)66 6618I(Xi)log p(Xi)1 log 184.170 bit11 1p(Xi)6636I(Xi)log p(Xi)1log365.170 bit兩個(gè)點(diǎn)數(shù)的排列如下：111213141516212223242526313233343536414243444546515253545556616263646566共有21種組合:1 1 1其中11, 22, 33, 44, 55, 66的概率是6 6361 1 1其他15個(gè)組合的概率是2 -6 6 181 1 1 1H (X)p(xjlog p(xj6 log 15 log 4.337 bit / symboli36361818(4)參考上面的兩個(gè)點(diǎn)數(shù)的排列，可以得出兩個(gè)點(diǎn)數(shù)求和的概率分布如下：X2345678910 1112zx丄丄丄1_5_1_5_11 1丄P(X)36 18 12936636912 1