信息论与纠错编码题库.doc

第三章 离散信源无失真编码3.2离散无记忆信源，熵为Hx，对信源的L长序列进行等长编码，码字是长为n的D进制符号串，问：（1）满足什么条件，可实现无失真编码。（2）L增大，编码效率 也会增大吗？解：（1）当时，可实现无失真编码；（2）等长编码时，从总的趋势来说，增加L可提高编码效率，且当时，。 但不一定L的每次增加都一定会使编码效率提高。3.3 变长编码定理指明，对信源进行变长编码，总可以找到一种惟一可译码，使码长满足+时，能否也找到惟一可译码？解：在+时，不能找到惟一可译码。证明：假设在+时，能否也找到惟一可译码，则由变长编码定理当满足+，总可以找到一种惟一可译码知：在 时，总可以找到一种惟一可译码。由式有：logD 对于离散无记忆信源，有H(x)= 代入式得： 即在 时，总可以找到一种惟一可译码；而由定理给定熵H（X）及有D个元素的码符号集，构成惟一可译码，其平均码长满足+时，不能找到惟一可译码。3.7 对一信源提供6种不同的编码方案：码1码6，如表3-10所示表3-10 同一信源的6种不同编码信源消息消息概率码1码2码3码4码5码6u11/400011100000u21/410010100101001U31/800011100001100011u41/81110010000001101100u51/8011011000000001110101u61/1600111010000000000111101110u71/161111111000000000000111111111（1） 这些码中哪些是惟一可译码？（2） 这些码中哪些是即时码？（3） 对所有唯一可译码求出其平均码长。解：码1： 其二次扩展码是奇异码，如u1u2和u5u1对应的码字均为010；码2： 是惟一可译码，非奇异等长码是惟一可译码，且是即时码，平均码长为3；码3： 是延长码，是惟一可译码，但不是即时码，平均码长为=3.06码4： 是非延长码，故是惟一可译码，也是即时码；平均码长=3.06码5： 是数码，即非延长码，因此是即时码；平均码长=2.625码6：是非延长码，故是惟一可译码，也是即时码；平均码长=3.125综上所述，码26均为惟一可译码，码2、4、5、6是即时码。3.10信源符号集X=0,1,2，一信源含8个消息，编码为即时码，若要求码长只取1,3,5中的一个，应用克拉夫特不等式，分析按上述要求能否构成唯一可译码。解：根据克拉夫特不等式唯一可译码充要条件为码长取1，则不等式左边=8*1/31 ，则唯一可译。码长取3，则不等式左边=8*(1/3)31 , 则唯一可译。码长为5，则不等式左边=8*(1/3)51 , 则唯一可译。3.11 某个信源有N个消息，等概率分布，对其进行最佳二进制编码，问当N=和N=+1（m为整数）时，每个码字的长度等于多少？平均码长等于多少？解：当N=，最佳二进制编码每个码字的长度均为m；平均码长=m 当N=+1，令q(x1)q(x2) q(x3) q(),最佳二进制编码前面1个码字的长度为m，后2个码字的长度为m+1；平均码长=3.15离散无记忆信源= （1） 求X的最佳二元编码，平均码长及编码效率。（2） 求的最佳二元编码，平均码长及编码效率。（3） 求的最佳二元编码，平均码长及编码效率。解：（1）编码结果如下图所示： 平均码长=10.5+2（0.3+0.2）=1.5（码元/符号）信源熵H（X）= -0.5log0.5-0.3log0.3-0.2log0.2=0.5+0.521+0.464=1.49(比特/符号)编码效率=0.99（2）= 编码结果如下图所示：平均码长=20.25+30.5+40.25=3（码元/符号）信源熵H（）=-=0.5+0.821+0.664+0.313+0.487+0.186=2.31 (比特/符号)编码效率=0.77（4） 编码如下图所示：序号kD=2霍夫曼编码D=2编码码长概率1x1x1x110040.1252x1x1x2110140.0753x1x2x1110040.0754x2x1x1101140.0755x1x1x3010040.056x1x3x1001140.057x3x1x1001040.058x1x2x2000140.0459x2x1x2000040.04510x2x2x11111150.04511x1x2x31010050.0312x1x3x20111150.0313x2x1x30111050.0314x2x3x10110150.0315x3x1x20110050.0316x3x2x10101150.0317x2x2x20101050.02718x1x3x311101160.0219x3x1x311101060.0220x3x3x111100160.0221x2x2x311100060.01822x2x3x210101160.01823x3x2x210101060.01824x2x3x3111101170.01225x3x2x3111101070.01226x3x3x2111100170.01227x3x3x3111100070.008平均码长=30.125+40.465+50.252+60.114+70.044=4.49（码元/符号）信源熵H（）=-=4.46(比特/符号)编码效率=0.99码元/符号 3.21（1）两个无前缀变长码的级联定义为 C=C1C2,即证明：无前缀变长码的级联仍然是无前缀变长码。（2）考虑以下系统：设有两个互相独立的信源= 和= 定义=，k=0,1,2,3,4,5,6,7,8 的熵为多少？ 对分别设计D=2，D=3的霍夫曼编码，比较编码效率； 对分别设计D=2，D=3的霍夫曼编码，将它们级联后得到一个新的无前缀变长码，并将它们的编码效率与的结果比较； 验证中的级联码是否仍然满足香农第一定理。解：（1）证明：设=,， =,，C=，因为，都是无前缀编码，即不是的前缀（i!=j），同理不是的前缀（i!=j）故对任意的C= （ 1i,jM）当i取任一值，j 为变量，因为为无前缀码，故级联之后的仍为无前缀变长码；当j取任一值，i 为变量，因为为无前缀码，故级联之后的仍为无前缀变长码；故 无前缀变长码的级联码仍为无前缀变长码。（2）由题知： Zz0 z1z2z3z4z5z6z7z8q(Z)1/101/61/101/61/101/121/101/121/10序号a3a1a4a2a5a8a6a8a7则H（）=0.862+1.661+0.597=3.12(比特/符号) 编码图如下：D=2时，平均码长=3+4=3.17（码元/符号）编码效率 =0.98422D=3时，平均码长=2（码元/符号）编码效率 =0.98425 的编码如下图:根据级联的定义易知，级联后的新变长码的霍夫曼编码为：序号kXYD=2霍夫曼编码D=2编码码长D=3霍夫曼编码D=3编码码长概率1x1y0111041121/152x1y2110141021/153x1y41100412231/154x1y611111512131/155x1y811110512031/156x3y0101040121/157x3y2100140021/158x3y41000402231/159x3y610111502131/1510x3y810110502031/1511x5y00110421131/3012x5y20101421031/3013x5y401004212241/3014x5y6011115212141/3015x5y8011105212041/3016x7y00010420131/3017x7y20001420031/3018x7y400004202241/3019x7y6001115202141/3020x7y8001105202041/30H(XY)= =4.24(比特/符号)D=2时，平均码长=4+5=4.