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

《信息论与纠错编码题库.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章离散信源无失真编码3.2离散无记忆信源，熵为H[x]，对信源的L长序列进行等长编码，码字是长为n的D进制符号串，问：（1）满足什么条件，可实现无失真编码。（2）L增大，编码效率也会增大吗？解：（1）当时，可实现无失真编码；（2）等长编码时，从总的趋势来说，增加L可提高编码效率，且当时，。但不一定L的每次增加都一定会使编码效率提高。3.3变长编码定理指明，对信源进行变长编码，总可以找到一种惟一可译码，使码长满足<+,试问在>+时，能否也找到惟一可译码？解：在>+时，不能找到惟一可译码。证明：假设在>+时，能否也找到惟一可译码，则由变长编码定理当

2、满足<+，总可以找到一种惟一可译码知：在①时，总可以找到一种惟一可译码。由①式有：logD②对于离散无记忆信源，有H(x)=代入式②得：即在时，总可以找到一种惟一可译码；而由定理给定熵H（X）及有D个元素的码符号集，构成惟一可译码，其平均码长满足<+1两者矛盾，故假设不存在。所以，在>+时，不能找到惟一可译码。3.7对一信源提供6种不同的编码方案：码1~码6，如表3-10所示表3-10同一信源的6种不同编码信源消息消息概率码1码2码3码4码5码6u11/400011100000u21/410010100101001U31/8000111000011

3、00011u41/81110010000001101100u51/8011011000000001110101u61/1600111010000000000111101110u71/161111111000000000000111111111（1）这些码中哪些是惟一可译码？（2）这些码中哪些是即时码？（3）对所有唯一可译码求出其平均码长。解：码1：其二次扩展码是奇异码，如u1u2和u5u1对应的码字均为010；码2：是惟一可译码，非奇异等长码是惟一可译码，且是即时码，平均码长为3；码3：是延长码，是惟一可译码，但不是即时码，平均码长为==3.06码

4、4：是非延长码，故是惟一可译码，也是即时码；平均码长==3.06码5：是数码，即非延长码，因此是即时码；平均码长==2.625码6：是非延长码，故是惟一可译码，也是即时码；平均码长==3.125综上所述，码2~6均为惟一可译码，码2、4、5、6是即时码。3.10信源符号集X={0,1,2}，一信源含8个消息，编码为即时码，若要求码长只取1,3,5中的一个，应用克拉夫特不等式，分析按上述要求能否构成唯一可译码。解：根据克拉夫特不等式唯一可译码充要条件为码长取1，则不等式左边=8*1/3>1，则唯一可译。码长取3，则不等式左边=8*(1/3)^3<1,

5、则唯一可译。码长为5，则不等式左边=8*(1/3)^5<1,则唯一可译。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）求的最佳二元编码，平均码长及编码

6、效率。解：（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（1）编码如下图所示：序号kD=2霍夫曼编码D=2编码码长概率1x1x1x110

7、040.1252x1x1x2110140.0753x1x2x1110040.0754x2x1x1101140.0755x1x1x3010040.056x1x3x1001140.057x3x1x1001040.058x1x2x2000140.0459x2x1x2000040.04510x2x2x11111150.04511x1x2x31010050.0312x1x3x20111150.0313x2x1x30111050.0314x2x3x10110150.0315x3x1x20110050.0316x3x2x10101150.0317x2x2x201

8、01050.02718x1x3x311101160.0219x3x1x311101060.0220x3x3x1111001