信息论与编码习题集

1、第二章习题：补充题：掷色子，（1）若各面出现概率相同（2）若各面出现概率与点数成正比试求该信源的数学模型解： （1）根据，且，得，所以信源概率空间为 （2）根据，且，得。2-2 由符号集组成的二阶马尔可夫链，其转移概率为P(0/00)=0.8，P(0/11)=0.2，P(1/00)=0.2， P(1/11)=0.8，P(0/01)=0.5，P(0/10)=0.5，P(1/01)=0.5，P(1/10)=0.5。画出状态图，并计算各状态的稳态概率。解：由二阶马氏链的符号转移概率可得二阶马氏链的状态转移概率为： P(00/00)=0.8 P(10/11)=0.2 P(01/00)=0.2 P(11

2、/11)=0.8 P(10/01)=0.5 P(00/10)=0.5 P(11/01)=0.5 P(01/10)=0.5二进制二阶马氏链的状态集S=00，01，10，11 状态转移图各状态稳定概率计算：即 得： 即：P(00)=P(11)= P(01)=P(10)=2-6掷两粒骰子，当其向上的面的小圆点数之和是3时，该消息所包含的信息量是多少？当小圆点数之和是7时，该消息所包含的信息量又是多少？解： 2-7 2-7设有一离散无记忆信源,其概率空间为 该信源发出的消息符号序列为(202 120 130 213 001 203 210 110 321 010 021 032 011 223 210

3、),求此消息的自信息量是多少及平均每个符号携带的信息量?解:消息序列中,“0”个数为=14,“1”个数为=13,“2”个数为=12,“3”个数为=6. 消息序列总长为=+=45(个符号)(1) 消息序列的自信息量: - (2) 平均每个符号携带的信息量为: 2-14 在一个二进制信道中，信息源消息集X=0，1，且P(1)=P(0),信宿的消息集Y=0，1，信道传输概率P（1/0）=1/4，P（0/1）=1/8。求： （1）在接收端收到y=0后，所提供的关于传输消息x的平均条件互信息量I（X;y=0）。 (2) 该情况所能提供的平均互信息量I（X；Y）。 解：X=0,1,Y=0,1 求 (2)

4、2-25 某一无记忆信源的符号集为0，1，已知，。（1）求符号的平均熵。（2）由100个符号构成的序列，求某一特定序列（例如有m个0和100-m个1）的自信息量的表达式。（3）计算(2) 中的序列的熵。解：（1）对离散无记忆信源符号的平均熵： 比特/符号 （2）长度为L=100的符号序列中某特定序列，其中“0”的个数为m，“1”的个数为100-m.该特定序列的概率为 对离散无记忆信源，其符号独立出现，即 则该特定序列的自信息量为：=41+1.59m (bit) (3)长度为L=100的符号序列离散无记忆信源熵： =H(XXX)=81（比特/序列）2-30有一马尔可夫信源，已知转移概率为，。试画

5、出状态转移图，并求出信源熵。解：（1）由题意知，该马尔可夫信源阶数为1，状态集S= ， 状态转移图为：(2) 信源熵：a) 求稳态概率 计算方程： 即： 得： 即：P(S)=0.75 ，P(S)=0.25b) 求H(X/S)H(X/S)则信源熵：H =H =0.69 比特/符号2-33 一阶马尔可夫信源的状态图如图2-14所示，信源X符号集为0，1，2。（1）求平稳后信源的概率分布；（2）求信源熵；（3）求当p=0或p=1时信源的熵，并说明其理由。解：（1）一阶马尔可夫信源的状态空间S=X=0，1，2，由图2-14状态转移图中分析得，此马尔可夫链是时齐的，状态有限的和不可约闭集，非周期，所以具

6、有各态历经性。平稳后状态的极限分布存在，因为是一阶马尔可夫信源，状态的极限分布即平稳后信源符号的一维概率分布，即 根据状态转移图，得状态一步转移矩阵：计算方程组 即 整理计算得：即 状态极限概率 P(0)=P(1)=P(2)=1/3(2) 根据马尔可夫信源熵的表达式： = 由 =同理 从而 比特/符号（3）当p=0或p=1时信源的熵，这是因为p=0或p=1时信源为确定性信源，观察着对信源发出什么符号不存在任何不确定度，所以信源不提供任何的信息量。第三章 3-1设二进制对称信道的概率转移距阵为.（1）若p( )=3/4，p()=1/4,求H(X),H(X|Y),H(Y|X)和I(X;Y)。(选做

7、)（2）求该信道的信道容量及其达到信道容量时的输入概率分布。解：（1）由题意可得 x的先验概率P( )=3/4,p()=1/4.H(x)=H(3/4,1/4)=0.82bit/符号由概率转移距阵得符号转移概率：p( | )=2/3,p(| )=1/3,p (| )=1/3,p(| )=2/3.联合概率：p(, )=p()p( | )=1/2同理：p( , )=1/4，p( , )=1/12，p( , )=1/6则条件熵：=0.91bit/符号另外p()=7/12 p()=5/12=0.9799根据得=0.7494bit/符号互信息：=0.066bit/符号 (2) 由概率转移距阵，可知该信道为

8、对称DMC信道故其信道容量： (m=2为接收端信宿符号集中符号数目) =0.082bit/符号当其达到信道容量时输入为等概分布p()=p()=1/2.3-5 求下列两个信道的容量，并加以比较（1）（2）解：由于两信道均为准对称信道（行元素对应相同，但列元素不相同），可分解为 其信道容量公式为则 ，即信道2比信道1好一些。3-10. 一个平均功率受限制的连续信道，其通频带为1MHZ，信道上存在白色高斯噪声。（1）已知信道上的信道的信号与噪声的平均功率比值为10，求该信道的信道容量；（2）信道上的信道与噪声的平均功率比值降至5，要达到相同的信道容量，信道通频带应为多大？（3）若信道通频带减为0.5

9、MHZ时，要保持相同的信道容量，信道上的信号与噪声的平均功率比值应等于多大？解：(1)由题意可得:由SNR=10信道的信道容量：C=W=3.46Mbit/s（2）若SNR=5,信道容量保持不变.由C=W 得W=C/ =1.34MHZ(3)若W减为0.5 MHZ,信道容量保持不变.由C= W 易得 1+SNR=121 故SNR=120.第四章 4-1 设有一个二元等概信源X=0，1，通过一个二进制对称信道（BSC）。其失真函数与信道转移概率分别定义为 试求失真矩阵d和平均失真。解：由失真矩阵转移概率矩阵平均失真为4-3 设输入符号表与输出符号表为X=Y=0，1，2，3，且输入信号的分布为，设失真

10、矩阵为 求，和，以及相应的编码器转移概率矩阵。解：对离散信源， 当时为无失真编码，信源符号与码符号一一对应，即则信道转移概率矩阵为得假设时失真达到，即则此时信道转移概率矩阵为 4-5 具有符号集的二元信源，信源发生概率为：，。Z信道如图4-7所示，接收符号集，转移概率为：，。发出符号与接收符号的失真：，。（1）计算平均失真；（2）率失真函数R(D)的最大值是什么？ 当q为什么值时可达到该最大值？ 此时平均失真D是多大？ （3）率失真函数R(D)的最小值是什么？ 当q为什么值时可达到该最小值？ 此时平均失真D是多大？（4）画出R(D)D的曲线。解：概率转移矩阵为：失真矩阵为（1）（2），率失真函

11、数取最大值时比对 应最小的失真，对离散信源，最小失真为零，即，由于，所以，则（3），对应最大的失真， 此时（4）R(D)D曲线： Ø （2）（3）的传统解法：（2） 解方程 得 则平均失真 （3），令，得此时平均失真第五章 信源编码5-1 将下表所列的某六进制信源进行二进制编码，试问(1) 这些码中哪些是唯一可译码？(2)哪些码是非延长码（即时码）？ (3) 对所有的唯一可译码求出其平均码长和编码效率。解：C1=000，001，010，011，100，101 C2=0，01，011，0111，01111，011111C3=0，10，110，1110，11110，111110 (1)

12、C1码组为等长码，因各码字均不相同，则必为唯一可译码。C2码组中各码字长度分别为，则根据克劳夫特不等式 则存在该码长分布的唯一可译码；下一步检验该码长构成的具体码字：最短的码字“0”是其他码的前缀，尾随后缀分别为1，11，111，1111，11111，这些尾随后缀都不是码组中的单独码字；次短的码字“01”是码字011，0111，01111，011111的 前缀，其尾随后缀为11，111，1111，11111不是码组中的单独码字，.依次可判断其他次短码字虽然是长码字的前缀，但尾随后缀均不是码组中的单独码字，由此可断定该码字是唯一可译码。C3码组的码长分布与C2码组相同，满足克劳夫特不等式，下一步

13、检验该码长构成的具体码字：最短的码字”0” 不是其他码字的前缀，没有尾随后缀，次短码字”10”、110” “1110“、“11110”都不是其他码字的前缀，没有尾随后缀，所以必是唯一可译码。（C3码组满足克劳夫特不等式，又是非前缀码，所以是唯一可译码）(2) C1 、C2、C3是唯一可译码，在唯一可译码中，分为即时码和非即时码。即时码的判断方法有两种： 根据定义：即时码又叫非前缀码或非延长码。则C1、C3是即时码根据码树：码组中的各码字都处在树的终端节点上，则为即时码。 码树省略 判断结果为：C1、C3的各码字均处在码树的终端节点上，是即时码(3) 根据公式 根据编码效率公式得比特/符号5-1

14、0 设有离散无记忆信源P(X)=0.37,0.25,0.18,0.10,0.07,0.03;(1)求该信源符号熵H(X);(2) 用哈夫曼编码编成二进制变长码，计算编码效率。(3)要求译码错误小于，采用定长二元码要达到(2)中的哈夫曼编码效率，问需要多少个信源符号连在一起编？解：（1）信源熵 比特/符号(2) 用哈夫曼编码编成二进制变长码为00，01，11，101，1000，1001平均码长 码符号/信源符号编码效率 (3)要求译码错误小于，采用定长二元码要达到(2)中的哈夫曼编码效率。第一步： 根据第二步 要求译码错误小于，令，则需要一起编的符号长度应满足 5-12 已知一信源包含8个消息符

15、号，其出现的概率P(X)=0.1,0.18,0.4,0.05,0.06,0.1,0.07,0.04，则求(1) 该信源在每秒内发出一个符号，求该信源的熵及信息传输速率；(2) 对这8个符号作哈夫曼编码，写出相应码字，并求出编码效率；(3) 进行香农编码，写出相应码字，并求出编码效率；(4) 进行费诺编码，写出相应码字，并求出编码效率；解：（1）信源熵 比特/符号信息传输速率 (2) 对这8个符号作哈夫曼编码所编码为1，001，011，0000，0100，0101，00010，00011；平均码长 码符号/信源符号编码效率 （3）香农编码编码过程：所编码为00，011，1001，1010，110

16、0，11011，11101，11110；平均码长 码符号/信源符号编码效率 （4）费诺编码所编码为00，01，100，101，1100，1101，1110，1111；平均码长 码符号/信源符号编码效率 补充1：几种实用的无失真信源编码方法1 MH编码MH编码是用于黑白二值文件传真的数据压缩编码。它是一维编码方案。它将游程编码和哈夫曼编码相结合的一种标准的改进哈夫曼码。2 算术编码3 LZ码LZ码是一种通用编码方法，无需知道信源的统计特性，而且编码效率很高。基本算法是：将长度不同的符号串编成一个新的短语(符号串)，形成短语词典的索引表。LZ78是一种分段编码 ，它的短语词典是由前面已见到的文本字

17、段来定义的。(续上) 补充2：几种常用的限失真信源编码方法：4 矢量量化5补充3：香农第二定理信道编码定理方法，可见，根据无噪信道编码定理（即无失真信源编码定理），因为，所以总能对信源的输出进行适当的编码，使此信源在此信道中进行无失真传输。如果对信源不进行编码，直接将信源符号s1以0符号传送，s2以1符号传送，这时因为信源输出为2.66二元信源符号/秒，大于2二元信道符号/秒，就会使信道输入端造成信源符号的堆积，信息不能按时发送出去。所以，不通过编码此信源不能直接与信道连接。若要连接，必须对信源的输出符号序列进行编码，也就是对此信源的N次扩展信源进行编码。但扩展次数N越大，编码越复杂，设备代价

18、越大，所以尽量使扩展次数 N小，而又能使信源在此信道中无失真传输。先考虑N=2，并对二次扩展信源进行哈夫曼编码，得所以，必须考虑N=3即对三次扩展信源进行哈夫曼编码，得可见，根据无噪信道编码定理（即无失真信源编码定理），因为，所以不论进行任何编码此信源都不可能在此信道中实现无失真的传输，所以信源在此信道中传输会引起错误和失真。 比特/信源符号 比特/秒若 则此信源在此信道中传输时不会引起错误。也就是不会因为信道而增加信源新的失真。总的信源的失真是信源压缩编码所造成的允许失真D。所以有 故 D=0.0415D=0.0415第六章 信道编码例1 设有一离散信道，其信道转移矩阵为 并设，试分别按最小错误概率准则与最大似然译码准则确定译码规则，并计算相应的平均错误概率。解：由于本离散信道的输入符号的先验概率不是等概分布，所以对于最小错误概率准则必须根据联合概率的大小来选择。联合概率矩阵为对于y1, 对于y2, 对于y1, 所以，按最小错误概率准则确定的译码规则是 对于最大似然译码规则，我们可以直接从信道矩阵的转移概率中来选择。对于y1, 对于y2, 对于y3, 所以，按最大似然译码准则确定的译码规则是 平均错误概率为 所以，按最小错误概率准则确定的译码规则引起的平均错误概率为 最大似然译码准则确定的译码规则引起的平均错误概率 例2 设某二元码为C=1110