《第五章信源编码习题答案-Read.docx》由会员分享，可在线阅读，更多相关《第五章信源编码习题答案-Read.docx（17页珍藏版）》请在三一文库上搜索。
1、XiX2X3X4X5XX75.1 设信源:X (X)0.2 0.19 0.18 0.17 0.15 0.1 0.01j(1)求信源嫡H(X);(2)编二进制香农码;(3)计算平均码长和编码效率。解：7H(X)7 p(x)log2 P(%) i 1(-(0.2 log20.2 0.19 log20.19 0.18 log20.18 0.17 log20.170.15 log20.15 0.1 log20.1 0.01 log20.01)= 2.609bit/symbol(2)X iP(Xi)Pa(Xi)ki码字1X0.2030002X0.190.230013X0.180.3930114X0.17
2、0.5731005X0.150.743101X60.10.8941110X70.010.9971111110K = 1%) = 302+3父0.193父。183父。17+354+7M。01二 314H(X) H(X) 2609 3, 831%3.145.2对信源尸(X) 一X1X2X3X4x5X60.2 0.19 0.18 0.17 0.15 0.1 0.01X7 编二进制费XiP(Xi)编俱；偃字iX10.20000X20.1910010X30.181011X40.171010诺码，计算编码效率。解:k2332K = 长隗)=2父02+3父0.19 3乂。18 2父。17+3。15 4父。1
3、+4父。i= 274HHM260995.3对信源XIp(X).R K 2.74:、XiX2X3 X4X5X6X7 :编0.20.190.180.170.150.10.01二进制和三进制哈夫曼码，计算各自的平均码长和编码效率。解: 二进制哈夫曼码:XiP(Xi)编码码字kiS61S50.610S40.391S30.350S20.261X10.20102X20.191112X30.1800003X40.1710013X50.1500103S10.111X60.1001104X70.01101114K = z kHx) = 2M02+2MO193MQ18 3MQ17 3Q154O1+4M0.01i=
4、 272一 H(X) . H(X) . 26091 - - - 959%272三进制哈夫曼码:XiP(Xi)编码码字kiS30.261S20.540S11Xi0.2221X20.190002X310.181012X40.172022X50.150102X60.11112X70.012122K 八 kipxi =1 0.2 2 (0.19 0.18 0.17 0.15 0.10 0.01) = 1.8 i_H XK ” c-L/log m 22.6091.8/log3291.4%5.4设信源：X MJP(X)2 4X3 X4 X5 X6 X7 X81 工J 1 18 16 32 64 128 1
5、28(1)求信源嫡H(X)；(2)编二进制香农码和二进制费诺码;(3)计算二进制香农码和二进制费诺码的平均码长和编码效率;(4)编三进制费诺码；(5)计算三进制费诺码的平均码长和编码效率;解:8H(X) - -% p(xjlog2 p(x)i 11111 =log2 2log2 4log2 82481611log216 32 log2 32 54 晦641X1281 log2128 128log=1.984 bit/symbol(2)二进制香农码:xip(xi)pa(x i )ki码字x10.5010x20.250.5210x30.1250.753110x40.06250.87541110x5
6、0.031250.9375511110x60.0156250.968756111110x0.0070.9843771111781255110x80.00781250.992187571111111二进制费诺码:xiP(Xi)编码码字kiX10.5001X20.2510102X30.125101103X40.06251011104X50.0312510111105X60.015625101111106X70.00781251011111107X80.0078125111111117香农编码效率:K = E kip(x) = 父1*一父2*一父3+ 一父4* 父5+ 乂 6* 黑 7* 乂 7i2
7、48163264128128= 1.984H(X) H(X) 1.984-100% 1.9841K = Z Kp(x)二父i2= 1.984费诺编码效率:1 - 2 1 3 4 5 6 7 748163264128128H(X) H(X) 1.98410(%R K 1.984(4)xip(xi)编俱；码字kix10.5001x20.25111x30.1250202x40.06251212x50.03125202203x60.015625212213x70.00781252022204x80.007812512221411111 c 1 c 1,1,K = KP(X)= i1+-M1 + f2+
8、 父2+ 父3+父 3+ 父 4+父 4i 248163264128128= 1.328H(X) H(X) =1.984i94.3%R K/lo乐2 1.328/0225.5 设Xi, X2, X3为独立的二进制随机变量，弁且有尾或1 = 1=1,?以2=1=1, PX3 = 1= 1 ,请给出联合随机变量(Xi, X2, X3)的 3 r 34Huffman编码，弁求其平均码长。解：根据已知条件可以得到联合随机变量( Xi, X2, X3)的概率分布，如表所75。Xi X2X3P(X1X2X3)0001/40011/120101/80111/241001/41011/121101/81111
9、/24然后根据Huffman编码算法得到编码结果为:XiX2X3码字000100011100010111011011010000101110111001011101111平均码长为：L 2 6 63 3 3 4 2 2 1 1 = 2.7524 -5.6 下面以码字集合的形式给出5种不同的编码，第一个码的码字符号集合为x, y z,其他4个码都是二进制码。xx, xz, y, zz, xyz000, 10, 00, 11100, 101, 0, 1101, 100, 011, 00, 111, 1010, 1011, 110101, 111, 011, 00, 010, 110对于上面列出的5
10、种编码，分别回答下述问题：此码的码长分布是否满足Kraft-McMillan不等式？此码是否是即时码？如果不是，请给出反例。此码是否是唯一可译码？如果不是，请给出反例。解：码字集合一：xx, xz, y, zz, xyz此码的码长分布满足Kraft-McMillan 不等式:19 d12711111+ _ +32 32 31 32 3333931+27 27 27 27 27根据码树图可知此码是即时码。由于此码是即时码，所以也是唯一可译码码字集合二：000, 10, 00, 11此码的码长分布满足Kraft-McMillan不等式:111112 2 2十+十232 2222 2+ 十 +此码不
11、是即时码，因为码字 00是码字000的前缀。此码不是唯一可译码，因为码符号序列000000可以译码为00,00, 00,也可以译码为 000, 000。码字集合三：100, 101, 0, 11此码的码长分布满足 Kraft-McMillan不等式:1111- 1142 . 8 I I I 11 I 111 I 111 “， T I2323212288888根据码树图可知此码是即时码。由于此码是即时码，所以也是唯一可译码。码字集合四：01, 100, 011, 00, 111, 1010, 1011, 1101此码的码长分布不满足Kraft-McMillan不等式：1111111117* *
12、- * - + 4 7 + T * 7 = 1222323222324242416因为不满足因为不满足Kraft-McMillan不等式，所以此码不是即时码。码。码字集合五：01,111, 011, 00, 010, 110Kraft-McMillan 不等式，所以此码不是唯一可译此码的码长分布满足 Kraft-McMillan不等式:111112 223232223238此码不是即时码，因为码字01是码字011的前缀。此码是唯一可译码。5.7 一离散信源的符号表为a, b, c, d, e,而x =daadcadbea为此 信源的观察序列。假设此信源为具体分布未知的独立同分布随机过程，通过观
13、察序列，可以得到信源概率分布函数的一个估计，根据这个 估计求信源的嫡。根据估计出来的信源概率分布函数构造一个Huffman码，计算平均码长弁指出对序列x编码所需的比特数与平均码长的关系。解：此时信源概率分布的估计为 0.4, 0.1, 0.1, 0.3, 0.1,相应的嫡为H =-0.4log20.4-3M0.1log20.1 0.3log20.3= 2.0464 比特/符号由上一问的概率分布， 根据Huffman编码算法可得到编码结果，如表所75。符号估计概率分布码字码长a0.411b0.10013c0.100004d0.3012e0.100014平均码长为：L= 0.4 1 0.3 2 0
14、.1 3 2 0.1 4= 2.1如果用表中的码字对序列 x =daadcadbea进行编码，则总共需要的比特数为：2d+1a+1a+2d+4c+1a+2d+3b+4e+1a=21而此序列的自信息为 10H=20.464bit。5.8 一个离散无记忆信源，其样本空间为W, B,符号 W出现的概率为0.99, B出现的概率为0.01。对此信源的二次扩展，求出信源符号序列的概率分布，找出相应的 Huffman编码弁求平均码长。对此信源的三次扩展重复上一问。计算信源的单符号嫡弁与上两问中的单符号平均码长进行比较。解：二次扩展信源的符号序列、概率分布及码字如表所示。不了 r b列概率码字WW0.99X
15、0.99=0.98010WB0.99X0.01=0.009911BW0.01 X 0.99=0.0099100BB0.01x 0.01=0.0001101平均码长为：L2 = 0.9801 1 0.0099 2 0.0099 3 0.0001 3 = 1.0299三次扩展信源的符号序列、概率分布及码字如表所示：不了 r b列概率码字WWW0.9702990WWB0.009801100WBW0.009801101BWW0.009801110WBB0.00009911100BWB0.00009911101BBW0.00009911110BBB0.00000111111平均码长为：L3 = 0.97
16、0299 1 0.009801 3 3 3 0.000099 5 5 5 0.000001 5 = 1.0（信源的单符号嫡为_11H（S）= 0.99log2 十 0.01log2=0.080179 比特/符号2 0.992 0.01二次扩展信源和三次扩展信源的单符号平均码长分别为：L2 = 0.51495 , L3 = 0.35333都远大于信源的单符号嫡。235.9已知离散无记忆信源如下:S SS283s435s6szpj0.20 0.19 0.18 0.17 0.15 0.10 0.01 .试求：信源符号嫡H (S);相应的二元Huffman编码及其编码效率；相应的三元Huffman编码
17、及其编码效率；若要求PE&10-3,采用定长二元码要求达到第问中的编码效率，至少需要多少信源符号一起编码才能实现？解：信源符号嫡为H( S)= 一 (0210g2 0.2 + 0.19log20.19+ 0.18log20.18+ 0.17log2 0.17+ 0.15log20.15+ 0.10log20.10 0.01log2 0.01 H S2 72，编码效率为 = = 96%=26比特/符号信源符号S1S2S3S4S5S6S7概率0.200.190.180.170.150.100.01码字101100000101001100111二元Huffman编码如表所示:平均码长为L三元Huffman编码如表所示:信源符号SiS2S3S4S5S6S7概率0.200.190.180.170.150.100.01码字2000102101112平均码长为L = 1.8 ,编码效率为io = =l log 3 2 = 92%信源自信息量的方差为二 2 二 E j si 2-h S i2 = 0.241 HS一 一按编码效率为96% ,即=0.96H S ；0.109因此有2 CTpEL 二2.03 104即需要约2.03X 104个信源符号一起编码。