信息论基础与编码（第五章）
5-1有一信源，它有六种可能的输出，其概率分布如下表所示，表中给出了对应的六种编码C1、C2、C3、C4、C5和C6。
（1）求这些码中哪些是唯一可译码；（2）求哪些是非延长码（即时码）；
（3）对所有唯一可译码求出其平均码长。
消息概率
C1000001010011100101C2001011011101111C3010110111011110C4010110111001001C51000001010110110C601001100101110111a1a2a3a4a5a61/21/41/161/161/161/160111111111101111解：（1）1,2,3,6是唯一可译码；(2)1,3,6是即时码。
5-2证明若存在一个码长为l1,l2,,lq的唯一可译码，则一定存在具有相同码长的即时码。
证明：由定理可知若存在一个码长为L1,L2,,Lq的唯一可译码，则必定满足kraft不等式
ri1qli1。由定理44可知若码长满足kraft不等式，则一定存在这样码长的即时码。
所以若存在码长L1,L2,,Lq的唯一可译码，则一定存在具有相同码长P（y=0）的即时码。
S15-3设信源P()p12p266，pi1。将此信源编码成为r元唯一可译p6i1变长码（即码符号集某{某1,某2,,某r}），其对应的码长为（l1,l2,,l6）=（1，1，2，3，2，3），求r值的最小下限。
解：要将此信源编码成为r元唯一可译变长码，其码字对应的码长
（l1,l2,l3,l4,l5,l6）=(1,1,2,3,2,3)必须满足克拉夫特不等式，即
ri16lir1r1r2r3r2r31
所以要满足
222231，其中r是大于或等于1的正整数。rrr222可见，当r=1时，不能满足Kraft不等式。当r=2,1，不能满足Kraft。
248222261，满足Kraft。当r=3,392727所以，求得r的最大值下限值等于3。
6。
或由Craft不等式，有
解
8051036000010L11
minL16
得
900010L25100010(L21)1
或805103(900051000101)10L21
1805103解得L2log104.859即minL25
90005100
11122(5-5求概率分布为3,5,5,15,15)的信源的二元霍夫曼码。讨论此码对于概率分布为
11111(,,,,)的信源也是最佳二元码。55555
11122p()(,,,,)i解：信源的概率分布为：3551515
二元霍夫曼码：00，10，11，010，011，码长：2，2，2，3，3
11111(当信源给定时，二元霍夫曼码是最佳二元码。所以对于概率分布为5,5,5,5,5)的信源，
其最佳二元码就是二元霍夫曼码。这二元霍夫曼码一定是三个信源符号的码长为2（码符号
/信源符号），另二个信源符号的码长为3（码符号/信源符号），其平均码长最短。因此，上
11122(述对概率分布为3,5,5,15,15)信源所编的二元霍夫曼码也是概略分布为
11111(,,,,)信源的最佳二元码。555555-6设二元霍夫曼码为（00，01，10，11）和（0，10，110，111），求出可以编得这些霍夫曼码的信源的所有概率分布。
解：由题意假设信源所发出的是个符号的概率为P(S4)P(S3)P(S2)P(S1)由霍夫曼编码的特点知：P(S4)P(S3)P(S2)P(S1)1
根据霍夫曼编码的方法，每次概率最小的两个信源符号合并成一个符号，构成新的缩减信源，直至最后只剩两个符号。而且当缩减信源中的所有符号概率相等时，总是将合并的符号放在最上面。所以，对于二元霍夫曼码为（00，01，10，11）来说，每个信源都要缩减一次，所以P(S3)P(S4)要大于P(S1)和P(S2)，这时必有
11P(S1)P(S2),P(S1)
33同理对于二元霍夫曼码为（0，10，110，111）有
11P(S3)P(S4),P(S1)>
33信源概率分布满足以上条件则其霍夫曼编码符合题意。
5-7设一信源有K=6个符号，其概率分别为：P(1)1/2,P(2)1/4,P(3)1/8，对该信源进行霍夫曼二进制编码，并求编码效率。P(4)P(5)1/20，P(6)1/40，
解：相应的Huffman编码是：{1,01,001,0001,00000,00001}。平均码长=1.95，熵=1.94H(某)1.940.995
Llog21.955-8设信源概率空间为：
S1,2P=0.1,0.9，（1）求HS和信源冗余度；
（2）设码符号为某={0,1}，编出S的紧致码，并求紧致码的平均码长L；
（3）把信源的N次无记忆扩展信源SN编成紧致码，试求N=2，3，4，时的平均码
长LNN；（4）计算上述N=1，2，3，4这四种码的编码效率和码冗余度。解：（1）信源
SP120.10.92其HPilogPi0.469比特/符号
i1剩余度1Hlog20.531=53.1％
（2）码符号某={0,1}，对信源S编紧致码为：10，21其平均码长L=1码符号/信源符号(3)当N=2时
S2111,212,331,4Pi=220.01,0.09,0.09,0.81紧致码（即霍夫曼码）为
4,3,2,1
码字Wi0,10,110,111码长li1,2,3,3
平均码长LNN4=10.5码符号/信源符号
2Pilii1N=3时，S3Pi=
1,2,3,4,5,6,7,0.13,0.120.9,0.120.9,0.120.9,0.10.92,0.10.92,0.10.92,
对信源S3进行霍夫曼编码，其紧致码为
8,7,6,5,4,3,2,
码字Wi0,100,101,110,11100,11101,11110,11111码长li1,3,3,3,5,5,5,5
平均码长LN18N=3P码符号/信源符号
ili0.533i1N=4时，S4Pi=
80.93
2,3,4,5,6,7,8,1,0.14,0.130.9,0.130.9,0.130.9,0.130.9,0.120.92,0.120.92,0.120.92,9,10,11,12,13,14,15,160.120.92,0.120.92,0.120.92,0.10.93,0.10.93,0.10.93,0.10.93,0.94
对信源S4进行霍夫曼编码，其紧致码为
16,15,14,13,
12,11,10,
9,
码字Wi0,100,101,110,1110,111110,1111000,1111001,
码长li1,3,3,3,4,6,7,7,
8,7,6,5,4,3,2,1
码字Wi1111010,1111011,1111110,111111101,111111110,111111111,
1111111000,1111111001
码长li7,7,7,9,9,9,10,10
LN平均码长N1=4Plii116i0.493码符号/信源符号
N=时，根据香农第一定理，其紧致码的平均码长
N
lim
LNH=0.469码符号/信源符号NlogrLLHSHS1码剩余度1－1r(r=2)LL所以N=1编码效率10.469
码
剩
余
度
0.531=53.1%N=220.7270.273=27.3%N=330.8800.120=12%N=440.9510.049=4.9%
从本题讨论可知，对于变长紧致码，当N不很大时，就可以达到高效的无失真信源编码。
(4)编码效率HrSHS(r=2)
5678S12345-9设信源空间为：=0.40.20.10.10.050.050.050.05，码
P()符号为某={0,1,2}，试构造一种三元紧致码。
解：得信源符号12345678三元紧致码10002202122010011
5-10某气象员报告气象状态，有四种可能的消息：晴、云、雨和雾。若每个消息是等概的，那么发送每个消息最少所需的二元脉冲数是多少？又若四个消息出现的概率分别是1/4，1/8，1/8和1/2，问在此情况下消息所需的二元脉冲数是多少？如何编码？解：第一种情况：需要二元脉冲数两个，可表示四种状态，满足我们的要求。
