信息論與編碼習(xí)題參考答案

1、5.1某離散無記憶信源的概率空間為 X 口2盤3饑4盤彳松不盤8_p_1/2 1/4 1/3 1/16 1/32 1/64 K12S 1/12S采用香農(nóng)碼和費(fèi)諾碼對(duì)該信源進(jìn)行二進(jìn)制變長編碼,寫出編碼輸出碼字, 并且求出平均碼長和編碼效率.解：計(jì)算相應(yīng)的自信息量1 (ajlbp(aj1比特IOIbp(a2)2比特I (a3)IbpdJ3比特1Ibp(a4)4比特I(a5)Ibp(a5)5比特I (a6)Ibp(a6)6比特I(a7)Ibp(a7)7比特1 (a7)Ibp(a7)7比特根據(jù)香農(nóng)碼編碼方法確定碼長I (ai )I i 1(a)1可以得到對(duì)應(yīng)碼長如表所示符號(hào)概率累計(jì)概率自信息量碼長碼字

2、a11/20110a21/41/22210a31/83/433110a41/167/8441110a51/3215/165511110a61/6431/3266111110a71/12863/64771111110a81/128127/128771111111平均碼長L11/ 2 11/ 4 21/ 8 31/ 16 41/ 32 51/ 64 61/ 128 71/ 128 7163/ 641. 984375由于每個(gè)符號(hào)的碼長等于自信息量,所以編碼效率為1.費(fèi)羅馬編碼過程符號(hào)碼字碼長a11/2001a21/410102a31/8101103a41/16101104a51/321011105a

3、61/6410111106a71/128101111107a81/128111111175.2某離散無記憶信源的概率空間為使用費(fèi)羅碼對(duì)該信源的擴(kuò)展信源進(jìn)行二進(jìn)制變長編碼,(1) 擴(kuò)展信源長度,寫出編碼碼字,計(jì)算平均碼長和編碼效率.(2) 擴(kuò)展信源長度,寫出編碼碼字,計(jì)算平均碼長和編碼效率.(3) 擴(kuò)展信源長度?_= 1,寫出編碼碼字,計(jì)算平均碼長和編碼效率,并且與(1)的結(jié)果進(jìn)行比擬.解：信息熵 H(X)0.75lb0.75 0. 25lb 0. 250.811 比特 / 符號(hào)(1)符號(hào)碼字碼長A101A211平均碼長L11比特/符號(hào)編碼效率為H( X)81. 1%96%(2)1 /9,3小3

4、1-2_(122161616H( X)0. 811編碼效率20. 84375平均碼長為3 163)0. 84375 比特 / 符號(hào)序列碼字碼長a1a19/16001a1a23/1610102a2a13/16101103a2a21/1611113(3)當(dāng) N=4時(shí),alal alal81/2560000alal a1a227/25610010alal a2a127/2561011a1a2 a1a127/256100100a2a1 a1a127/256101010a1a1 a2a29/25611011a1a2 a1a29/2561001100a1a2 a2a19/2561011010a2a1 a1

5、a29/256111011a2a1 a2a19/25610011100a2a2 a1a19/256111101a1a2 a2a23/256100111100a2a1 a2a23/2561111101a2a2 a1a23/25610111110a2a2 a2a13/256101111110a2a2 a2a21/25611111111序列碼長81c c27c27小99Li2 334244525625625625625633637173. 309256256256一 3 309平均碼長Li3.2090. 827H (X)Li0. 8110. 82798. 1%43可見,隨著信源擴(kuò)展長度的增加,平均碼

6、長逐漸逼近熵,編碼效率也逐漸提升.5.3某離散無記憶信源的概率空間為煎打o 8 0.2使用哈夫碼編碼法對(duì)該信源的擴(kuò)展信源進(jìn)行二進(jìn)制變長編碼,(1) 擴(kuò)展信源長度,寫出編碼碼字,計(jì)算平均碼長和編碼效率.(2) 擴(kuò)展信源長度,寫出編碼碼字,計(jì)算平均碼長和編碼效率.(3) 擴(kuò)展信源長度?_= 1,寫出編碼碼字,計(jì)算平均碼長和編碼效率,并且與(1)的結(jié)果進(jìn)行比擬.5.4某離散無記憶信源的概率空間 X '=1/261/31/32iru1兀4禺1/1281/12S使用約定碼表進(jìn)行哈夫曼進(jìn)行編碼,約定碼表的概率空間為 X '口戸1/21/41/31/161/321/1281/12S(1) 計(jì)

7、算平均碼長與編碼效率.(2) 如果直接對(duì)信源進(jìn)行哈夫曼編碼,寫出編碼碼字,計(jì)算平均碼長和編碼效率.(3) 比擬上述編碼結(jié)果,并進(jìn)行討論.解：信源的熵為 H(X)= 1.984375比特/符號(hào).1)利用約定碼表的概率空間進(jìn)行編碼,得到相應(yīng)的編碼碼表如下編碼碼字碼長a101a2102a31103a411104a5111105a61111106a711111107a811111117平均碼長為11111-3456832166412827112872.515625編碼效率為1HX)78. 9%2編碼碼表為編碼碼字碼長a201a1102a31103a511104a4111105a61111106a711

8、111107a811111117平均碼長為1.984375比特/符號(hào),編碼效率為 1.3當(dāng)實(shí)際數(shù)據(jù)統(tǒng)計(jì)規(guī)律與產(chǎn)生碼表對(duì)應(yīng)的概率相差較大時(shí),編碼效率會(huì)明顯降低.5.5某信源的概率空間為<7?6tS 斗乂、盤了_p_1/41/2 1/8 1/32 1/15 1/64 1/128 1/128 _使用3進(jìn)制符號(hào)0,1, 2進(jìn)行編碼,寫出哈夫碼和費(fèi)羅碼,并且計(jì)算編碼效率. 5.6某離散無記憶信源的概率空間為x r噸1砌注*比=| 032 0 22 0.18 016 0.03 0.041采用二進(jìn)制哈夫曼碼編碼對(duì)信源編碼,計(jì)算編碼效率.2如果采用等長碼編碼,要求錯(cuò)誤譯碼概率小于1L,那么序列長度為多少

9、?解：1編碼結(jié)果如下碼字碼長a1002a2102a3112a40103a501104a601114平均碼長為L 0. 3220. 2220. 1820. 1630. 0840.0442.4信源的熵為H (X ) =2.353比特/符號(hào)編碼效率為 1HX)2. 353L2. 498%2) 自信息量方差為 Dl(ai) = 0.527;將參數(shù)代入NDl(ai) 2H2(X)(1 -)22. 291075.8某信源輸出二進(jìn)制序列 (0000,0000,0000,0001,1111,0000,0010,0000),對(duì)該序列進(jìn)行不 同形式的游程編碼,分別給出編碼結(jié)果(1) 直接統(tǒng)計(jì)連續(xù)0和1的個(gè)數(shù).(2

10、) 采用四進(jìn)制數(shù)據(jù)進(jìn)行編碼,即如果連續(xù)出現(xiàn)符號(hào)數(shù)量為1,2,3,那么輸出符號(hào)“1 ,“ 2；',“ 3如果當(dāng)前編碼輸出為“ 3；'之后出現(xiàn)符號(hào)變化,那么應(yīng)當(dāng)一個(gè)“ 0；再對(duì)變化后的符號(hào)序列進(jìn)行編碼,寫出編碼結(jié)果.(3) 將符號(hào)序列分為 4個(gè)一組,如果一組的 4個(gè)符號(hào)全部為0,那么輸出符號(hào)“ 0;否那么輸 出符號(hào)“ 1；并且直接輸出該符號(hào)序列.解1)輸出結(jié)果為15,5,6,1,5;2) 3 3 3 3 3 0 3 2 3 3 0 1 3 2 ;3) 0 0 0 10001 11111 0 10010 0;5.8給定的序列進(jìn)行游程編碼.5.9使用表5.8二進(jìn)制游程編碼碼表對(duì)題解：0

11、 0 0 100 111111 0 1010 05.10離散無記憶信源的概率空間為jVI盤 位玄蟲4px) = lf2 lf4 1/3 V8_使用算術(shù)編碼方法對(duì)輸出序列- “ '進(jìn)行編碼,并且對(duì)結(jié)果進(jìn)行譯碼.解：累計(jì)概率Pi如表所示P10P20.5P30.75p4_0.875令 Co=0,A0=1;1) 6= C0+A0P2=0+1*0.5 =0.5;A仁 A0*p2=0.25;2) C2=C1+A1P 仁0.5+0.25*0 =0.5;A2=A1*p 仁0.25*0.5=0.125;3) C3=C2+A2P1=0.5+0.125*0 =0.5;A3=A2*p 仁0.125*0.5=0

12、.0625;4) C4=C3+A3P3=0.5+0.0625*0 .75=0.546875;A4=A3*p3=0.0625*0.125= 0.0078125;L= -lbA4 =7;編碼輸出為100110譯碼過程如下將接受到的碼字 100110轉(zhuǎn)化為概率 C0=0. 546875,并令A(yù)0=1 ;1) 由于概率處于0.5,0.75),所以第一個(gè)符號(hào)譯碼為a2,6= (C0-P2)/p2=(0. 546875-0.5)/0.25=0.1875 ；2) 由于C1處于區(qū)間0,0.5),所以第2個(gè)符號(hào)譯碼為a1;C2=(C1 -P1)/p1=0.375 ；3) 由于C2處于區(qū)間0,0.5),所以第3個(gè)

13、符號(hào)譯碼為a1;C3=(C2-P1)/p1=0.75 ；4) 由于C3處于區(qū)間0.75,0.875),所以第4個(gè)符號(hào)譯碼為a3;C4=(C1 -P3)/p3=0 ；5) 譯碼輸出符號(hào)數(shù)量已經(jīng)到達(dá)要求,譯碼結(jié)束.5.11某信源輸出符號(hào)有兩種類型,對(duì)應(yīng)的概率空間分別為尤21 r 1吐遜口 4血天)叮 41/g 1(3血?jiǎng)? 1/4 1J4 "4 "4輸出序列為-'-',對(duì)應(yīng)的符號(hào)類型分別為',使用算術(shù)編碼器進(jìn)行編碼,并且對(duì)結(jié)果進(jìn)行譯碼.解：首先計(jì)算累計(jì)概率P110P120.5P130.75P140.875P210P220.25P230.5P240.75A

14、0=1,C0=0 ；1) 第1個(gè)輸入符號(hào)為第1類數(shù)據(jù)的a2,所以有6= C0+A0P12 =0.5A仁 A0p12=0.252) 第2個(gè)輸入符號(hào)為第2類數(shù)據(jù)的a1,所以有C2=C1+A1P21 =0.5A2=A1p2 仁0.06253) 第3個(gè)輸入符號(hào)為第1類數(shù)據(jù)的al,所以有C3=C2+A2P11 =0.5A3=A2p11=0.031254) 第4個(gè)輸入符號(hào)為第1類數(shù)據(jù)的a3所以有C4=C3+A3P13=0.5234375A4=A3p13=0.00390625L=-lb0.00390625=8將 C4 小數(shù)局部用 8 比特二進(jìn)制表示出來,得到輸出碼字為 1000,0110譯碼過程：將接受到碼字化為概率 C0=0.52343751) 第 1 個(gè)數(shù)據(jù)為第 1 類數(shù)據(jù),處于區(qū)間 0.5,0.75) 譯碼輸出為 a2; C1=(C0-P12) /p12 = (0.5234375-0.5)/0.25 = 0.093752) 第2個(gè)數(shù)據(jù)為第 2類數(shù)據(jù),處于區(qū)間 0, 0.25)譯碼輸出為 a1; C2=