1、第三章 离散信源无失真编码3.2离散无记忆信源，熵为 Hx，对信源的 L 长序列进行等长编码，码字是长为 n 的 D 进制符号串，问：（1）满足什么条件，可实现无失真编码。（2）L 增大，编码效率 也会增大吗？解：（1）当 时，可实现无失真编码；log()nDLHX（2）等长编码时，从总的趋势来说，增加 L 可提高编码效率，且当 时，L。 但不一定 L 的每次增加都一定会使编码效率提高。3.3 变长编码定理指明，对信源进行变长编码，总可以找到一种惟一可译码，使码长 满足n+ 时，能否也找到惟一可译码？DXHlog)(nL1nDXHlog)(L1解：在 + 时，不能找到惟一可译码。证明：假设在
2、+ 时，能否也找到惟一可译码，则由变长编码定理当 满足nDXHlog)(L1 n+ 时，不能找到惟一可译码。L13.7 对一信源提供 6 种不同的编码方案：码 1码 6，如表 3-10 所示表 3-10 同一信源的 6 种不同编码信源消息 消息概率 码 1 码 2 码 3 码 4 码 5 码 6u1 1/4 0 001 1 1 00 000u2 1/4 10 010 10 01 01 001U3 1/8 00 011 100 001 100 011u4 1/8 11 100 1000 0001 101 100u5 1/8 01 101 10000 00001 110 101u6 1/16 00
3、1 110 100000 000001 1110 1110u7 1/16 111 111 1000000 0000001 1111 1111（1） 这些码中哪些是惟一可译码？（2） 这些码中哪些是即时码？（3） 对所有唯一可译码求出其平均码长。解：码 1： 其二次扩展码是奇异码，如 u1u2 和 u5u1 对应的码字均为 010；码 2： 是惟一可译码，非奇异等长码是惟一可译码，且是即时码，平均码长为 3；码 3： 是延长码，是惟一可译码，但不是即时码，平均码长为 = =3.06n71iip码 4： 是非延长码，故是惟一可译码，也是即时码；平均码长 = =3.0671ii码 5： 是数码，即非
4、延长码，因此是即时码；平均码长 = =2.625n71ii码 6：是非延长码，故是惟一可译码，也是即时码；平均码长 = =3.12571iip综上所述，码 26 均为惟一可译码，码 2、4、5、6 是即时码。3.10信源符号集 X=0,1,2，一信源含 8 个消息，编码为即时码，若要求码长只取 1,3,5 中的一个，应用克拉夫特不等式，分析按上述要求能否构成唯一可译码。解：根据克拉夫特不等式唯一可译码充要条件为 1mnD码长取 1，则不等式左边=8*1/31 ，则唯一可译。码长取 3，则不等式左边=8*(1/3)31 , 则唯一可译。码长为 5，则不等式左边=8*(1/3)51 , 则唯一可译
5、。3.11 某个信源有 N 个消息，等概率分布，对其进行最佳二进制编码，问当 N= 和 N= +1（m2m为整数）时，每个码字的长度等于多少？平均码长等于多少？解：当 N= ，最佳二进制编码每个码字的长度均为 m；平均码长 =m2m n当 N= +1，令 q(x1) q(x2) q(x3) q( ),最佳二进制编码前面 xm12m1 个码字的长度为 m，后 2 个码字的长度为 m+1；平均码长 =n2m3.15离散无记忆信源 = )(Xq5.01x32（1） 求 X 的最佳二元编码，平均码长及编码效率。（2） 求 的最佳二元编码，平均码长及编码效率。)2(（3） 求 的最佳二元编码，平均码长及
6、编码效率。3解：（1）编码结果如下图所示：a1 0.5a2 0.3a3 0.21010.5 10夫夫01110平均码长 =1 0.5+2 （0.3+0.2）=1.5（码元/符号）1n信源熵 H（X）= )(log31xmmmq= -0.5log0.5-0.3log0.3-0.2log0.2=0.5+0.521+0.464=1.49(比特/符号)编码效率 = = =0.99DnXHlog1)(2log5.491（2） = )(2q0x10x1.30x9.263x0.243x编码结果如下图所示：a1 0.25a2 0.15a3 0.15a4 0.10a5 0.10a6 0.09a7 0.06a8
7、0.06a9 0.040.1100.150.21010100.25100.3100.450.5511010夫夫011101010010001111111010011000平均码长 =2 0.25+3 0.5+4 0.25=3（码元/符号）2n信源熵 H（ ）=-X)( )(log291)2(xmmmq=0.5+0.821+0.664+0.313+0.487+0.186=2.31 (比特/符号)编码效率 = = =0.77Dnlog2)(23.（4） 编码如下图所示：序号k X)(D=2 霍夫曼编码D=2 编码码长 概率1 x1x1x1 100 4 0.1252 x1x1x2 1101 4 0.
8、0753 x1x2x1 1100 4 0.0754 x2x1x1 1011 4 0.0755 x1x1x3 0100 4 0.056 x1x3x1 0011 4 0.057 x3x1x1 0010 4 0.058 x1x2x2 0001 4 0.0459 x2x1x2 0000 4 0.04510 x2x2x1 11111 5 0.04511 x1x2x3 10100 5 0.0312 x1x3x2 01111 5 0.0313 x2x1x3 01110 5 0.0314 x2x3x1 01101 5 0.0315 x3x1x2 01100 5 0.0316 x3x2x1 01011 5 0.
9、0317 x2x2x2 01010 5 0.02718 x1x3x3 111011 6 0.0219 x3x1x3 111010 6 0.0220 x3x3x1 111001 6 0.0221 x2x2x3 111000 6 0.01822 x2x3x2 101011 6 0.01823 x3x2x2 101010 6 0.01824 x2x3x3 1111011 7 0.01225 x3x2x3 1111010 7 0.01226 x3x3x2 1111001 7 0.01227 x3x3x3 1111000 7 0.008a1 0.125a2 0.075a3 0.075a4 0.075a5
10、 0.05a6 0.05a7 0.05a8 0.045a9 0.045a10 0.045a11 0.03a12 0.03a13 0.03a14 0.03a15 0.03a16 0.03a17 0.027a18 0.02a19 0.02a20 0.02a21 0.018a22 0.018a23 0.018a24 0.012a25 0.012a26 0.012a27 0.0080.020.0240.0360.0380.041010101010100.04410100.06100.06101010100.090.0570.1070.120.0660.0780.0890.10.1410.150.167
11、0.190.227100.266100.317100.417 100.583 101夫夫10101010101010101001101110010110100001100100001000011111101000111101110011010110001011010101110111110101110011110001010111010101111011111101011110011111000平均码长 =3 0.125+4 0.465+5 0.252+6 0.114+7 0.044=4.49（码元/符号）n信源熵 H（ ）=- =4.46(比特/符号)X)3(log)32713(xmmmq编
12、码效率 = = =0.99Dnlog3)(249.6码元/符号0.892.1.()350%94.1log.logLHXnD3.21（1）两个无前缀变长码的级联定义为C=C1C2,即 CcCc21,21证明：无前缀变长码的级联仍然是无前缀变长码。（2）考虑以下系统：设有两个互相独立的信源= 和 = )(Xq31x6517x)(Yq510y24516y8定义 = ，k=0,1,2,3,4,5,6,7,8zkyk21为 偶 数为 奇 数 的熵为多少？k 对 分别设计 D=2，D=3 的霍夫曼编码，比较编码效率 ； 对 分别设计 D=2，D=3 的霍夫曼编码，将它们级联后得到一个新的无前缀变和 ykx
13、长码，并将它们的编码效率与的结果比较； 验证中的级联码是否仍然满足香农第一定理。解：（1）证明：设 = , ,， ，c112cM1= , ,， ，22C= ， ， ， ， ， 111M121c21M2因为 ， 都是无前缀编码，即 不是 的前缀（i!=j） ，同理 不是 的前缀c2cij ij（i!=j）故对任意的 C= = （ 1i,jM）12i1j2当 i 取任一值，j 为变量，因为 为无前缀码，故级联之后的仍为无前缀变长码；当 j 取任一值，i 为变量，因为 为无前缀码，故级联之后的仍为无前缀变长码；c1故 无前缀变长码的级联码仍为无前缀变长码。（2）由题知： Z z0 z1 z2 z3
14、z4 z5 z6 z7 z8q(Z) 1/10 1/6 1/10 1/6 1/10 1/12 1/10 1/12 1/10序号 a3 a1 a4 a2 a5 a8 a6 a8 a7则 H（ ）= =0.862+1.661+0.597=3.12(比特/符号) zk )(log80zkkq 编码图如下：a1 1/6a2 1/6a3 1/10a4 1/10a5 1/10a6 1/10a7 1/10a8 1/12a9 1/1211/6101/5101/5104/15101/3102/5 103/5 101夫夫110101100011010000001111111100a1 1/6a2 1/6a3 1/
15、10a4 1/10a5 1/10a6 1/10a7 1/10a8 1/12a9 1/12 0124/152103/1013/302102101夫夫222120121110020100D=2夫夫夫夫夫夫 D=3夫夫夫夫夫夫D=2 时，平均码长 =3 +4 = =3.17（码元/符号）n659编码效率 = = =0.984221DZHlog)(2log17.3D=3 时，平均码长 =2（码元 /符号）2n编码效率 = = =0.984252DZHlog)(3 的编码如下图:和 ykxx1 1/3x3 1/3x5 1/6x7 1/610101/32/3 101夫夫11100100x1 1/3x3 1
16、/3x5 1/6x7 1/6101/31210夫夫102021X夫D=2夫夫夫夫夫 X夫D=3夫夫夫夫夫y0 1/5y2 1/5y4 1/5y6 1/5y8 1/5102/5102/53/5 10101夫夫100100111110y0 1/5y2 1/5y4 1/5y6 1/5y8 1/52103/51210夫夫10222120Y夫D=2夫夫夫夫夫 Y夫D=3夫夫夫夫夫根据级联的定义易知，级联后的新变长码的霍夫曼编码为：序号k XYD=2 霍夫曼编码D=2 编码码长D=3 霍夫曼编码D=3 编码码长 概率1 x1y0 1110 4 11 2 1/152 x1y2 1101 4 10 2 1/1
17、53 x1y4 1100 4 122 3 1/154 x1y6 11111 5 121 3 1/155 x1y8 11110 5 120 3 1/156 x3y0 1010 4 01 2 1/157 x3y2 1001 4 00 2 1/158 x3y4 1000 4 022 3 1/159 x3y6 10111 5 021 3 1/1510 x3y8 10110 5 020 3 1/1511 x5y0 0110 4 211 3 1/3012 x5y2 0101 4 210 3 1/3013 x5y4 0100 4 2122 4 1/3014 x5y6 01111 5 2121 4 1/301
18、5 x5y8 01110 5 2120 4 1/3016 x7y0 0010 4 201 3 1/3017 x7y2 0001 4 200 3 1/3018 x7y4 0000 4 2022 4 1/3019 x7y6 00111 5 2021 4 1/3020 x7y8 00110 5 2020 4 1/30H(XY)= =4.24(比特/符号)(log)(201 yxkkkqqD=2 时，平均码长 =4 +5 = =4.4（码元/符号）n532编码效率 = = =0.963641DYXHlog)(log4.编码效率比所得的编码效率 0.98422 低；D=3 时，平均码长 =2 +3 +4 = =2.93（码元/符号）2n1581534编码效率 = = =0.913022DYXHlog)(log9.2编码效率比所得的编码效率 0.98425 低。（4） 当 D=2 时， =4.4， = =4.241nYXH)(24.故满足 +1，即满足香农第一定理；DYXHlog)(Dlog当 D=3 时， =2.93， = =2.682nYXH)(324.故满足 +1，即满足香农第一定理；DYXHlog)(Dlog
