《信息论基础与编码()》由会员分享，可在线阅读，更多相关《信息论基础与编码()（16页珍藏版）》请在金锄头文库上搜索。
1、5- 有一信源,它有六种也许的输出,其概率分布如下表所示,表中给出了相应的六种编码和。(1) 求这些码中哪些是唯一可译码;(2) 求哪些是非延长码（即时码);(3) 对所有唯一可译码求出其平均码长。消息概率1/2000101001110100001/01011010100110161111110110001101/161011111100111010101111111110111解：（）1,2,3,6是唯一可译码;()1，6是即时码。5-2证明若存在一种码长为的唯一可译码，则一定存在具有相似码长的即时码。证明:由定理可知若存在一种码长为的唯一可译码，则必然满足kraf不等式。由定理4可知若码长
2、满足kraft不等式，则一定存在这样码长的即时码。因此若存在码长的唯一可译码，则一定存在具有相似码长P(y0）的即时码。设信源,。将此信源编码成为r元唯一可译变长码（即码符号集），其相应的码长为（)=（1，1，,3,2,3),求r值的最小下限。解:要将此信源编码成为元唯一可译变长码，其码字相应的码长（1 ，l2,l3， l,，6)=(,，,2,3） 必须满足克拉夫特不等式,即 因此要满足 ，其中r是不小于或等于1的正整数。可见,当=1时,不能满足Kraft不等式。 当r=,，不能满足Kraft。 当=， ,满足raf。因此，求得r的最大值下限值等于3。5-4设某都市有8门公务电话和60000门
3、居民电话。作为系统工程师,你需要为这些顾客分派电话号码。所有号码均是十进制数,且不考虑电话系统中、1不可用在号码首位的限制。(提示:用异前缀码概念)(1）如果规定所有公务电话号码为3位长,所有居民电话号码等长，求居民号码长度 的最小值；(2)设都市分为A、B两个区,其中区有000门电话,B区有1000门电话。现进一步规定A区的电话号码比B区的短1位，试求区号码长度的最小值。解:(a) 805门电话要占用100个位数中的0个，即要占用首位为0 7的所有数字及以8为首的个数字。由于规定居民电话号码等长, 以9为首的数字5位长可定义1 00个号码,6位长可定义 00 个号码。因此。或由raft不等式
4、，有解得， 即 (b) 在(a)的基本上，将8为首的数字用于最后个公务电话,8186 为首的6位数用于区5 00个号码，以9为首的5位数用于区9 00个号码。因此,。或由Draf不等式,有 或 解得 即5-5求概率分布为的信源的二元霍夫曼码。讨论此码对于概率分布为的信源也是最佳二元码。解：信源的概率分布为: 二元霍夫曼码：00，1,11，1,011,码长:,2,，,3当信源给定期，二元霍夫曼码是最佳二元码。因此对于概率分布为的信源,其最佳二元码就是二元霍夫曼码。这二元霍夫曼码一定是三个信源符号的码长为2（码符号信源符号）,另二个信源符号的码长为3(码符号/信源符号)，其平均码长最短。因此,上述
5、对概率分布为信源所编的二元霍夫曼码也是概略分布为信源的最佳二元码。5-6设二元霍夫曼码为(00，01，1,11)和(0,10,1,111),求出可以编得这些霍夫曼码的信源的所有概率分布。解:由题意假设信源所发出的是个符号的概率为由霍夫曼编码的特点知：根据霍夫曼编码的措施，每次概率最小的两个信源符号合并成一种符号,构成新的缩减信源，直至最后只剩两个符号。并且当缩减信源中的所有符号概率相等时,总是将合并的符号放在最上面。因此,对于二元霍夫曼码为（00,1,10,1)来说,每个信源都要缩减一次,因此要不小于和,这时必有同理对于二元霍夫曼码为(0,1，110,11）有信源概率分布满足以上条件则其霍夫曼
6、编码符合题意。5-7 设一信源有K6个符号,其概率分别为:，,对该信源进行霍夫曼二进制编码,并求编码效率。解:相应的Hufman编码是：1,1,1，01,00000,0001。平均码长=1.5，熵=14-8 设信源概率空间为:,（1）求和信源冗余度;（)设码符号为X=0，1,编出S的紧致码，并求紧致码的平均码长;()把信源的N次无记忆扩展信源编成紧致码,试求=2,3,时的平均码长；(4)计算上述N1,2,3,4这四种码的编码效率和码冗余度。解：(1)信源其 比特符号剩余度05315.1%（2)码符号=0，1，对信源S编紧致码为：,其平均码长=1 码符号/信源符号（3） 当N=2时紧致码(即霍夫
7、曼码）为 码字 0 ， 1 ， 10, 11码长 1 , 2 , 3 ， 平均码长=0.645 码符号/信源符号N=时,=对信源进行霍夫曼编码,其紧致码为 码字 ， 100 , 101 ， 10 , 1110 , 111 , 1110, 1111码长 1 ， , 3 ， , 5, , 5 , 5平均码长 =033 码符号信源符号N时,=对信源进行霍夫曼编码,其紧致码为 码字 ， 100, 101 ， 0 ， 1110 , 11 , 1111000， 1101,码长 1, 3, , 3 , 4 ， ， ， 7 , 码字 11100 ， 111011 ， 111110， , , ， , 码长 7
8、, 7 ， , 9 , 9 ， 9 , 10 , 0平均码长=0.43码符号信源符号时,根据香农第一定理,其紧致码的平均码长=.46 码符号/信源符号(4)编码效率 （=2）码剩余度 1 (r=）因此 N=1 编码效率0.46 码剩余度0.53=53.% N=2 0.727 .273=7.3% N=3 .80 0.10=1% N= 0.91 04=4.9 从本题讨论可知,对于变长紧致码,当N不很大时，就可以达到高效的无失真信源编码。59设信源空间为: =,码符号为X=,1，2,试构造一种三元紧致码。解:得信源符号 s s3 4 s5 6 7 s三元紧致码 0 02 20 21 22 01015
9、-10某气象员报告气象状态，有四种也许的消息：晴、云、雨和雾。若每个消息是等概的,那么发送每个消息至少所需的二元脉冲数是多少?又若四个消息浮现的概率分别是1/4,/,1/和1/2,问在此状况下消息所需的二元脉冲数是多少?如何编码?解: 第一种状况：需要二元脉冲数两个，可表达四种状态，满足我们的规定。第二种状况：我们采用霍夫曼可编为12编为 ；1/4编为1,/8编为0和001，脉冲数显然。5-1 若某一信源有个符号,并且每个符号等概率浮现，对这信源用最佳霍夫曼码进行二元编码，问当和(是正整数)时,每个码字的长度等于多少？平均码长是多少?解:当时用霍夫曼编码措施进行最佳编码，由于每个符号是等概率分
10、布的,因此每个符号码长应相等,这样平均码长最短,并且信源符号个数正好等于,则满足： ,因此每个码字的码长。当个时，由于每个符号等概率分布浮现,因此每个符号的码长也应当基本相等,但目前信源符号个数不是正好等于,因此必须有两个信源符号的码长延长一位码长,这样平均码长最短。因此时个码字的码长为,其他2个码字的码长为。平均码长。5-12若有一信源每秒钟发出26个信源符号。将此信源的输出符号送入某一种二元信道中进行传播(假设信道是无噪无损的），而信道每秒钟只传递2个二元符号。试问信源不通过编码能否直接与信道连接？若通过合适编码能否在此信道中进行无失真传播?若能连接，试阐明如何编码并阐明因素。解:信源,其
11、信源熵而其每秒钟发出2.6个信源符号，因此信源输出的信息速率为:送入一种二元无噪无损信道，此信道的最大信息传播率（信道容量)。而信道每秒钟只传播两个二元符号,因此信道的最大信息传播速率为: 可见:。根据无噪信道编码定理（即无失真信源编码定理),因。因此总能对信源的输出进行合适的编码，使此信源能在此信道中进行无失真地传播。如果对信源不进行编码，直接将信源符号以“0”符号传送,以“1”符号传送,这时由于信源输出为2.66(二元信源符号/秒)，不小于2(二元信道符号/秒），就会使信道输入端导致信源符号的堆积，信息不能准时发送出去。因此,不通过编码此信源不能直接与信道连接。若要连接，必须对信源的输出符号序列进行编码,也就是对此信源的N次扩展信源进行编码。但扩展次数越大,编码越复杂,设备的代价也越大，因此尽量使扩展的次数N少，而又能使信源在此信道中无失真传播。先考虑,并对二次扩展信源进行霍夫曼编码，得：二元霍夫曼码得:二次扩展编码后,送入信道的传播速率为:因此,必须考虑即对三次扩展信源进行霍夫曼编码,得：二元霍夫曼码得：三次扩展码后,送入信道额传播速率为:此时,就可以在信道中进行无失真传播了。-13既有一幅已离散量化后的图像,图像的灰度量化提成8级，如下表所示。表中数字为相应像素上的灰度级。1111111111111111111111222222222223333333444444455
