信息论与编码理论习题问题详解

《信息论与编码理论习题问题详解》由会员分享，可在线阅读，更多相关《信息论与编码理论习题问题详解（29页珍藏版）》请在装配图网上搜索。

1、word第二章 信息量和熵 八元编码系统，码长为3，第一个符号用于同步，每秒1000个码字，求它的信息速率。解：同步信息均一样，不含信息，因此 每个码字的信息量为 2=23=6 bit 因此，信息速率为 61000=6000 bit/s 掷一对无偏骰子，告诉你得到的总的点数为：(a) 7; (b) 12。问各得到多少信息量。 解：(1) 可能的组合为 1，6,2，5,3，4,4，3,5，2,6，1=得到的信息量 =2.585 bit (2) 可能的唯一，为 6，6= 得到的信息量=5.17 bit 经过充分洗牌后的一副扑克52，问：(a) 任何一种特定的排列所给出的信息量是多少？(b) 假如从

2、中抽取13牌，所给出的点数都不一样时得到多少信息量？解：(a) = 信息量=225.58 bit (b) = 信息量=13.208 bit 随机掷3颗骰子，X表示第一颗骰子的结果，Y表示第一和第二颗骰子的点数之和，Z表示3颗骰子的点数之和，试求、。 解：令第一第二第三颗骰子的结果分别为，相互独立，如此，=6=2.585 bit = =2(36+18+12+9+)+6 =3.2744 bit=-=- 而=，所以= 2-=1.8955 bit 或=-=+- 而= ，所以=2-=1.8955 bit=2.585 bit=+=1.8955+2.585=4.4805 bit 设一个系统传送10个数字，0

3、，1，9。奇数在传送过程中以0.5的概率错成另外一个奇数，其余正确接收，求收到一个数字平均得到的信息量。 解：=-因为输入等概，由信道条件可知，即输出等概，如此=10= =- =0- = - =25+845 =1 bit=-=10 -1=5=2.3219 bit 令为一等概消息集，各消息相应被编成下述二元码字=0000，=0011，=0101，=0110，=1001，=1010，=1100，=1111通过转移概率为p的BSC传送。求：(a)接收到的第一个数字0与之间的互信息量。(b)接收到的前二个数字00与之间的互信息量。(c)接收到的前三个数字000与之间的互信息量。(d)接收到的前四个数字

4、0000与之间的互信息量。解：即，=+=1+ bit= bit=31+ bit= bit、。=2(+) =3.5993 bit=-=-=1.0143 bit=-=-=0.3249 bit=-=-=1.0143 bit=-=-=0.6894 bit=-=-=0 bit 对于任意概率事件集X,Y,Z，证明下述关系式成立 (a)+，给出等号成立的条件 (b)=+ (c) 证明：(b) =- =- =- =+ (c) =- =- =- = 当=，即X给定条件下，Y与Z相互独立时等号成立 (a) 上式(c)左右两边加上，可得+于是+ 令概率空间，令Y是连续随机变量。条件概率密度为，求： (a)Y的概率密

5、度 (b) (c) 假如对Y做如下硬判决 求，并对结果进展解释。 解：(a) 由，可得=+ = (b)=2.5 bit= = =2 bit=-=0.5 bit (c) 由可得到V的分布律V-101p1/41/21/4 再由可知V-101p(V|x=-1)1/21/20p(V|x=1)01/21/2 bit=1 bit= 0.5 bit 令和是同一事件集U上的两个概率分布，相应的熵分别为和。 (a)对于，证明=+是概率分布 (b)是相应于分布的熵，试证明+ 证明：(a) 由于和是同一事件集U上的两个概率分布，于是0，0=1，=1 又，如此=+0=+=1 因此，是概率分布。 (b) = = 引理2

6、 =+第三章 信源编码离散信源无失真编码 试证明长为的元等长码至多有个码字。证：在元码树上，第一点节点有个，第二级有，每个节点对应一个码字，假如最长码有，如此函数有=，此时，所有码字对应码树中的所有节点。码长为1的个；码长为2的个，码长为的个总共=个3.2 设有一离散无记忆信源。假如对其输出的长为100的事件序列中含有两个或者少于两个的序列提供不同的码字。 (a) 在等长编码下，求二元码的最短码长。 (b) 求错误概率误组率。解: (a)不含的序列 1个长为100的序列中含有1个的序列 =100个 长为100的序列中含有2个的序列 =4950个 所需提供码的总数M=1+100+4950=505

7、1于是采用二元等长编码 =12.3，故取=13(b)当长度为100的序列中含有两个或更多的时出现错误，因此错误概率为=-= 设有一离散无记忆信源，U=，其熵为。考察其长为的输出序列，当时满足下式(a)在=0.05，(b)在=，=下求(c)令是序列的集合，其中 试求L=时情况(a)(b)下，T中元素个数的上下限。解：=0.81 bit =-=如此根据契比雪夫大数定理(a) =1884(b) =(c) 由条件可知为典型序列，假如设元素个数为，如此根据定理其中，可知 (i) ， 下边界： 上边界：= 故 (ii) ，=故 对于有4字母的离散无记忆信源有两个码A和码B，参看题表。字母概率码A码Ba11

8、1a20110a3001100a400011000(a) 各码是否满足异字头条件？是否为唯一可译码？(b) 当收到1时得到多少关于字母a的信息？(c) 当收到1时得到多少关于信源的平均信息？解：码A是异头字码，而B为逗点码，都是唯一可译码。码A bit码B bit码A U=1.32 bit 码B =0 bit收到1后，只知道它是码字开头，不能得到关于U的信息。 令离散无记忆信源(a) 求最优二元码,计算平均码长和编码效率。(b) 求最优三元码,计算平均码长和编码效率。解：(a)=3.234 bit平均码长 =3.26=效率 (b)平均码长 效率 3.6 令离散无记忆信源 (a) 求对U的最优二

9、元码、平均码长和编码效率。(b) 求对U的最优二元码、平均码长和编码效率。(c) 求对U的最优二元码、平均码长和编码效率。 解：(a) bit (b) 离散无记忆 H(UU)=2H(U)=2.97 bitp(aa)=0.25, p(aa)=0.15, p(aa)=0.1, p(aa)=0.15, p(aa)=0.09 p(aa)=0.06, p(aa)=0.1, p(aa)=0.06, p(aa=(c) 有关最优二元类似 略 令离散无记忆信源且0P(a)P(a). P(a)1，而Q1=0，今按下述方法进展二元编码。消息a的码字为实数Q的二元数字表示序列的截短例如1/2的二元数字表示序列为1/2

10、10000，1/40100,保存的截短序列长度n是大于或等于I(a)的最小整数。(a) 对信源构造码。(b) 证明上述编码法得到的码满足异字头条件，且平均码长满足H(U)H(U)+1。解：(a)符号QiLC040000400014001040011401003011210211 (b) 反证法证明异字头条件令kk，假如是的字头，如此又由可知， 从而得这与假设是的字头即相矛盾，故满足异字头条件。由可得对不等号两边取概率平均可得即 3.8 扩展源DMC，(a)求对U的最优二元码、平均码长和编码效率。(b)求对U的最优二元码、平均码长和编码效率。(c)求对U的最优二元码、平均码长和编码效率。(d)求

11、对U的最优二元码、平均码长和编码效率。解：(a) ，=1，=1 bit(b) DMC信道，(c)=2.944 =98.85%(d) 略3.9 设离散无记忆信源试求其二元和三元Huffman编码。解： 设信源有K个等概的字母,其中K=,12。今用Huffman编码法进展二元编码。a是否存在有长度不为j或j+1的码字，为什么？b利用和j表示长为j+1的码字数目。c码的平均长度是多少？ 解：Huffman思想：将概率小的用长码，大的用短码，保证，当等概时，趋于等长码。a) 对时，K=2j，如此用长度为j码表示；当时，用K=2j+1，用长度为j+1码表示。平均码长最短，如此当12时，如此介于两者之间，

12、即只存在j，j+1长的码字。b) 设长为j的码字个数为Nj，长度为j+1的码字数目为Nj+1，根据二元Huffman编码思想必定占满整个码树，即从而，c =3.12 设二元信源的字母概率为，。假如信源输出序列为 1011 0111 1011 0111 (a) 对其进展算术编码并进展计算编码效率。 (b) 对其进展LZ编码并计算编码效率。解：(a) 根据递推公式 可得如下表格其中，F(1)=0， F(1)= ， p(0)=， p(1)=101011011110110111 从而 C = 01 (b) 首先对信源序列进展分段：1 0 11 01 111 011 0111然后对其进展编码，编码字典如

13、下所示段号短语ij编码11010001200000003111100114012101015111310111601141100170111611101bit3.13 设DMS为U=，各a相应编成码字0、10、110和1110。 试证明对足够长的信源输出序列，相应的码序列中0和1出现的概率相等。解：概率信源符号码字1/201/4101/81101/81110设信源序列长为N，如此相应码字长为条件是N要足够长相应码序列中0出现的次数 p(0)= =p(1)=1-p(0)= 设有一DMS, U= 采用如下表的串长编码法进展编码信源输出序列0串长度或中间数字输出二元码字101001000000010

14、00000000127800000001001001111 (a)求H(U)。 (b)求对于每个中间数字相应的信源数字的平均长度。 (c)求每个中间数字对应的平均长度。(d)说明码的唯一可译性。解：(a) bit由可得下表先验概率信源输出序列0串长度或中间数字输出二元码字100000011000100120010000130011000014010000000150101000000160110000000017011100000000181(b) bit(c) bit(d) 异字码头 第四章 信道与信道容量 计算由下述转移概率矩阵给定的DMC的容量。(a)它是一对称信道，达到C需要输入等概，

15、即=C bit/符号(b) 它是一对称信道 bit/符号c它是分信道和的和信道由，可知 bit/符号a (b)解：a由图知发送符号1时等概率收到0,1,2,传对与传错概率完全一样，即不携带任何信息量，于是信道简化为二元纯删除信道 bit/符号b由图知为准对称当输入等概，即时达到信道容量C此时 = bit/符号4.5 N个一样的BSC级联如图。各信道的转移概率矩阵。令，且为。(a) 求的表达式。(b) 证明时有，且与取值无关，从而证明时的级联信道容量解：N个信道级联后BSC可表示为N个级联可以看成N-1个级联后与第N个级联同理可得从而(a)(b)因此与无关。由于与无关，因此，C=0。 一PCM语

16、音通信系统，信号带宽W=4000 Hz，采样频率为2W，且采用8级幅度量化，各级出现的概率为1/2，1/4，1/8，1/16，1/32，1/32，1/32，1/32。试求所需的信息速率.解： bit信息速率 bit/s 在数字电视编码中，假如每帧为500行，每行划分成600个像素，每个像素采用8电平量化，且每秒传送30帧时，试求所需的信息速率。解：每个像素信息量为3 bit每秒传输30帧，即个像素 bit/s 带宽为3 kHZ，信噪比为30 dB的系统，假如传送时间为3分钟，试估计可能传送话音信息的数目。解：=30dB=1000如此R bit/s=29.9 Kb/s又传送时间t=30分钟=18

17、0 s180=5.382 Mbit 假如要以R=的速率通过一个带宽为8 kHz、信噪比为31的连续信道传送，可否实现？解：根据SHANNON公式40 Kb/s当连续信道为高斯信道时，CR=，于是不可实现；然而信道为非高斯信道时，其信道容量小于C，因此不能判定它与R的大小关系，从而不能确定能否实现。第五章 离散信道编码定理5.1 设有一DMC，其转移概率矩阵为假如=1/2，=1/4，试求两种译码准如此下的译码规如此，并计算误码率。解：1最大后验概率译码准如此首先计算 译码规如此为2最大似然准如此译码计算译码规如此显然它不是最优。第六章 线性分组码6.1 设有4个消息和被编成长为5的二元码00000，01101，10111，11010。试给出码的一致校验关系。假如通过转移概率为p1/2的BSC传送，试给出最优译码表与相应的译码错误概率表示式。解：1从而构造出2 根据最小距离译码准如此，可得伴随式与错误图样的对应关系如下00100100 1011010001001000 1100001001100001 1110011010010000 0000000036.4 设二元(6,3)码的生成矩阵为试给出它的一致校验矩阵为。解：H29 / 29