信息论与编码习题参考答案

1、5.1某离散无记忆信源的概率空间为 X 口2盘3饥4盘彳松不盘8_p_1/2 1/4 1/3 1/16 1/32 1/64 K12S 1/12S采用香农码和费诺码对该信源进行二进制变长编码,写出编码输出码字, 并且求出平均码长和编码效率.解：计算相应的自信息量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比特根据香农码编码方法确定码长I (ai )I i 1(a)1可以得到对应码长如表所示符号概率累计概率自信息量码长码字

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由于每个符号的码长等于自信息量,所以编码效率为1.费罗马编码过程符号码字码长a11/2001a21/410102a31/8101103a41/16101104a51/321011105a

3、61/6410111106a71/128101111107a81/128111111175.2某离散无记忆信源的概率空间为使用费罗码对该信源的扩展信源进行二进制变长编码,(1) 扩展信源长度,写出编码码字,计算平均码长和编码效率.(2) 扩展信源长度,写出编码码字,计算平均码长和编码效率.(3) 扩展信源长度?_= 1,写出编码码字,计算平均码长和编码效率,并且与(1)的结果进行比拟.解：信息熵 H(X)0.75lb0.75 0. 25lb 0. 250.811 比特 / 符号(1)符号码字码长A101A211平均码长L11比特/符号编码效率为H( X)81. 1%96%(2)1 /9,3小3

4、1-2_(122161616H( X)0. 811编码效率20. 84375平均码长为3 163)0. 84375 比特 / 符号序列码字码长a1a19/16001a1a23/1610102a2a13/16101103a2a21/1611113(3)当 N=4时,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可见,随着信源扩展长度的增加,平均码

6、长逐渐逼近熵,编码效率也逐渐提升.5.3某离散无记忆信源的概率空间为煎打o 8 0.2使用哈夫码编码法对该信源的扩展信源进行二进制变长编码,(1) 扩展信源长度,写出编码码字,计算平均码长和编码效率.(2) 扩展信源长度,写出编码码字,计算平均码长和编码效率.(3) 扩展信源长度?_= 1,写出编码码字,计算平均码长和编码效率,并且与(1)的结果进行比拟.5.4某离散无记忆信源的概率空间 X '=1/261/31/32iru1兀4禺1/1281/12S使用约定码表进行哈夫曼进行编码,约定码表的概率空间为 X '口戸1/21/41/31/161/321/1281/12S(1) 计

7、算平均码长与编码效率.(2) 如果直接对信源进行哈夫曼编码,写出编码码字,计算平均码长和编码效率.(3) 比拟上述编码结果,并进行讨论.解：信源的熵为 H(X)= 1.984375比特/符号.1)利用约定码表的概率空间进行编码,得到相应的编码码表如下编码码字码长a101a2102a31103a411104a5111105a61111106a711111107a811111117平均码长为11111-3456832166412827112872.515625编码效率为1HX)78. 9%2编码码表为编码码字码长a201a1102a31103a511104a4111105a61111106a711

8、111107a811111117平均码长为1.984375比特/符号,编码效率为 1.3当实际数据统计规律与产生码表对应的概率相差较大时,编码效率会明显降低.5.5某信源的概率空间为<7?6tS 斗乂、盘了_p_1/41/2 1/8 1/32 1/15 1/64 1/128 1/128 _使用3进制符号0,1, 2进行编码,写出哈夫码和费罗码,并且计算编码效率. 5.6某离散无记忆信源的概率空间为x r吨1砌注*比=| 032 0 22 0.18 016 0.03 0.041采用二进制哈夫曼码编码对信源编码,计算编码效率.2如果采用等长码编码,要求错误译码概率小于1L,那么序列长度为多少

9、?解：1编码结果如下码字码长a1002a2102a3112a40103a501104a601114平均码长为L 0. 3220. 2220. 1820. 1630. 0840.0442.4信源的熵为H (X ) =2.353比特/符号编码效率为 1HX)2. 353L2. 498%2) 自信息量方差为 Dl(ai) = 0.527;将参数代入NDl(ai) 2H2(X)(1 -)22. 291075.8某信源输出二进制序列 (0000,0000,0000,0001,1111,0000,0010,0000),对该序列进行不 同形式的游程编码,分别给出编码结果(1) 直接统计连续0和1的个数.(2

10、) 采用四进制数据进行编码,即如果连续出现符号数量为1,2,3,那么输出符号“1 ,“ 2；',“ 3如果当前编码输出为“ 3；'之后出现符号变化,那么应当一个“ 0；再对变化后的符号序列进行编码,写出编码结果.(3) 将符号序列分为 4个一组,如果一组的 4个符号全部为0,那么输出符号“ 0;否那么输 出符号“ 1；并且直接输出该符号序列.解1)输出结果为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给定的序列进行游程编码.5.9使用表5.8二进制游程编码码表对题解：0

11、 0 0 100 111111 0 1010 05.10离散无记忆信源的概率空间为jVI盘 位玄虫4px) = lf2 lf4 1/3 V8_使用算术编码方法对输出序列- “ '进行编码,并且对结果进行译码.解：累计概率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转化为概率 C0=0. 546875,并令A0=1 ;1) 由于概率处于0.5,0.75),所以第一个符号译码为a2,6= (C0-P2)/p2=(0. 546875-0.5)/0.25=0.1875 ；2) 由于C1处于区间0,0.5),所以第2个符号译码为a1;C2=(C1 -P1)/p1=0.375 ；3) 由于C2处于区间0,0.5),所以第3个

13、符号译码为a1;C3=(C2-P1)/p1=0.75 ；4) 由于C3处于区间0.75,0.875),所以第4个符号译码为a3;C4=(C1 -P3)/p3=0 ；5) 译码输出符号数量已经到达要求,译码结束.5.11某信源输出符号有两种类型,对应的概率空间分别为尤21 r 1吐逊口 4血天)叮 41/g 1(3血劝= 1/4 1J4 "4 "4输出序列为-'-',对应的符号类型分别为',使用算术编码器进行编码,并且对结果进行译码.解：首先计算累计概率P110P120.5P130.75P140.875P210P220.25P230.5P240.75A

14、0=1,C0=0 ；1) 第1个输入符号为第1类数据的a2,所以有6= C0+A0P12 =0.5A仁 A0p12=0.252) 第2个输入符号为第2类数据的a1,所以有C2=C1+A1P21 =0.5A2=A1p2 仁0.06253) 第3个输入符号为第1类数据的al,所以有C3=C2+A2P11 =0.5A3=A2p11=0.031254) 第4个输入符号为第1类数据的a3所以有C4=C3+A3P13=0.5234375A4=A3p13=0.00390625L=-lb0.00390625=8将 C4 小数局部用 8 比特二进制表示出来,得到输出码字为 1000,0110译码过程：将接受到码字化为概率 C0=0.52343751) 第 1 个数据为第 1 类数据,处于区间 0.5,0.75) 译码输出为 a2; C1=(C0-P12) /p12 = (0.5234375-0.5)/0.25 = 0.093752) 第2个数据为第 2类数据,处于区间 0, 0.25)译码输出为 a1; C2=