信息论基础与编码（第五章）

5-1 有一信源，它有六种可能的输出，其概率分布如下表所示，表中给出了对应的六种编码C1、C2、C3、C4、C5和C6。

（1） 求这些码中哪些是唯一可译码； （2） 求哪些是非延长码（即时码）；

（3） 对所有唯一可译码求出其平均码长。

消息 概率C1 000 001 010 011 100 101 C2 0 01 011 0111 01111 C3 0 10 110 1110 11110 C4 0 10 1101 1100 1001 C5 1 000 001 010 110 110 C6 01 001 100 101 110 111 a1 a2 a3 a4 a5 a6 1/2 1/4 1/16 1/16 1/16 1/16 011111 111110 1111 解：（1）1,2,3,6是唯一可译码； (2)1,3,6是即时码。

5-2证明若存在一个码长为l1,l2,???,lq的唯一可译码，则一定存在具有相同码长的即时码。

证明：由定理可知若存在一个码长为L1,L2,?,Lq的唯一可译码，则必定满足kraft不等式

?ri?1q?li?1。由定理4?4可知若码长满足kraft不等式，则一定存在这样码长的即时码。

所以若存在码长L1,L2,?,Lq的唯一可译码，则一定存在具有相同码长P（y=0）的即时码。

?S??s15-3设信源?????P(s)??p1s2???p2???s6?6，?pi?1。将此信源编码成为r元唯一可译?p6?i?1变长码（即码符号集X?{x1,x2,???,xr}），其对应的码长为（l1,l2,???,l6）=（1，1，2，3，2，3），求r值的最小下限。

解：要将此信源编码成为 r元唯一可译变长码，其码字对应的码长

（l1 ,l2 ,l3, l4,l5, l6）=(1,1,2,3,2,3) 必须满足克拉夫特不等式，即

?ri?16?li?r?1?r?1?r?2?r?3?r?2?r?3?1

所以要满足

222?2?3?1 ，其中 r是大于或等于1的正整数。 rrr222可见，当r=1时，不能满足Kraft不等式。 当r=2, ???1，不能满足Kraft。

24822226??1，满足Kraft。 当r=3, ??392727所以，求得r的最大值下限值等于3。

5-4设某城市有805门公务电话和60000门居民电话。作为系统工程师，你需要为这些用户分配电话号码。所有号码均是十进制数，且不考虑电话系统中0、1不可用在号码首位的限制。（提示：用异前缀码概念） （1）如果要求所有公务电话号码为3位长，所有居民电话号码等长，求居民号码长度L1 的最小值；

（2）设城市分为A、B两个区，其中A区有9000门电话，B区有51000门电话。现进一步要求A区的电话号码比B区的短1位，试求A区号码长度L2的最小值。

解：(a) 805门电话要占用1000个3位数中的805个，即要占用首位为0～ 7的所有数字及以8为首的5个数字。因为要求居民电话号码等长， 以9为首的数字5位长可定义10 000个号码，6位长可定义100 000 个号码。所以minL1

?6。

或由Craft不等式，有

解

805?10?3?60000?10?L1?1

minL1?6

得

1?805?10?3， 即 L1??log10?5488.60000 (b) 在(a)的基础上，将80为首的数字用于最后5个公务电话，81～86 为首的6位数用于B区51 000个号码，以9为首的5位数用于A区9 000 个号码。所以，minL2Draft不等式，有 805?10?3?5。或由

?9000?10?L2?51000?10?(L2?1)?1

或 805?10?3?(9000?51000?10?1)?10?L2?1

1?805?10?3 解得L2??log10?4.859 即minL2?5

9000?5100

11122(5-5求概率分布为3,5,5,15,15)的信源的二元霍夫曼码。讨论此码对于概率分布为

11111(,,,,)的信源也是最佳二元码。 55555

11122p(s)?(,,,,)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(s1)?1/2,P(s2)?1/4,P(s3)?1/8，对该信源进行霍夫曼二进制编码，并求编码效率。 P(s4)?P(s5)?1/20，P(s6)?1/40，

解：相应的Huffman编码是：{1,01,001,0001,00000,00001}。平均码长=1.95，熵=1.94 ??H(X)1.94??0.995

Llog21.955-8 设信源概率空间为：

?S??s1,s2??P?s??=?0.1,0.9?， ????（1）求H?S?和信源冗余度；

（2）设码符号为X={0,1}，编出S的紧致码，并求紧致码的平均码长L；

（3）把信源的N次无记忆扩展信源SN编成紧致码，试求N=2，3，4，?时的平均码

长??LN????N?； ?（4）计算上述N=1，2，3，4这四种码的编码效率和码冗余度。 解：（1）信源

??S???P?s?????s1s2??0.10.9?? ?2其 H?s???P?si?logP?si??0.469 比特/符号

i?1剩余度??1?H?s?log2?0.531=53.1％

（2）码符号X={0,1}，对信源S编紧致码为：s1?0，s2?1 其平均码长L=1 码符号/信源符号 (3) 当N=2时

??S2???1?s1s1,?2?s1s2,?3?s3s1,?4??P??i???=?s2s2??0.01,0.09,0.09,0.81?? 紧致码（即霍夫曼码）为

?4, ?3, ?2, ?1

码字Wi 0 , 10 , 110 , 111 码长li 1 , 2 , 3 , 3

平均码长??L??NN?4?=1??0.645 码符号/信源符号

??2?Pi?li?i?1N=3时，??S3??P??i???=

???1,?2,?3,?4,?5,?6,?7,??0.1?3,?0.1?2?0.9,?0.1?2?0.9,?0.1?2?0.9,0.1??0.9?2,0.1??0.9?2,0.1??0.9?2,

对信源S3进行霍夫曼编码，其紧致码为

?8, ?7, ?6, ?5, ?4, ?3, ?2,

?1

码字Wi 0 , 100 , 101 , 110 , 11100 , 11101 , 11110 , 11111 码长li 1 , 3 , 3 , 3 , 5 , 5 , 5 , 5

平均码长 ??L??N?18?N?=3P??码符号/信源符号

??i?li?0.533 i?1N=4时，??S4??P??i???=

?8??0.9?3??

?2,?3,?4,?5,?6,?7,?8,??1,??0.1?4,?0.1?30.9,?0.1?30.9,?0.1?30.9,?0.1?30.9,?0.1?2?0.9?2,?0.1?2?0.9?2,?0.1?2?0.9?2,??9,?10,?11,?12,?13,?14,?15,?16??0.1?2?0.9?2,?0.1?2?0.9?2,?0.1?2?0.9?2,0.1?0.9?3,0.1?0.9?3,0.1?0.9?3,0.1?0.9?3,?0.9?4??

对信源S4进行霍夫曼编码，其紧致码为

?16, ?15, ?14, ?13,

?12, ?11, ?10,

?9,

码字Wi 0 , 100 , 101 , 110 , 1110 , 111110 , 1111000 , 1111001,

码长li 1 , 3 , 3 , 3 , 4 , 6 , 7 , 7 ,

?8, ?7, ?6, ?5, ?4, ?3, ?2, ?1

码字Wi 1111010 , 1111011 , 1111110 , 111111101 , 111111110 , 111111111 ,

1111111000 , 1111111001

码长li 7 , 7 , 7 , 9 , 9 , 9 , 10 , 10

?LN平均码长??N??1?=?4??P???lii?116i?0.493 码符号/信源符号

N=?时，根据香农第一定理，其紧致码的平均码长

N??

lim

LNH?s?=?0.469 码符号/信源符号 NlogrLLH?S?H?S??1?码剩余度 1－??1?r (r=2) LL所以 N=1 编码效率?1?0.469 码剩余度?0.531=53.1% N=2 ?2?0.727 ?0.273=27.3% N=3 ?3?0.880 ?0.120=12% N=4 ?4?0.951 ?0.049=4.9%

从本题讨论可知，对于变长紧致码，当N不很大时，就可以达到高效的无失真信源编码。

(4) 编码效率 ??Hr?S??H?S? (r=2)

s5s6s7s8??S??s1s2s3s45-9设信源空间为：?? =?0.40.20.10.10.050.050.050.05?，码

P(s)????符号为X={0,1,2}，试构造一种三元紧致码。

解：得信源符号 s1 s2 s3 s4 s5 s6 s7 s8 三元紧致码 1 00 02 20 21 22 010 011

5-10 某气象员报告气象状态，有四种可能的消息：晴、云、雨和雾。若每个消息是等概的，那么发送每个消息最少所需的二元脉冲数是多少？又若四个消息出现的概率分别是1/4，1/8，1/8和1/2，问在此情况下消息所需的二元脉冲数是多少？如何编码？ 解： 第一种情况：需要二元脉冲数两个，可表示四种状态，满足我们的要求。

本文来源：https://www.bwwdw.com/article/g35v.html