信息论基础与编码(第五章)

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

（1） 求这些码中哪些是唯一可译码； （2） 求哪些是非延长码（即时码）；（3） 对所有唯一可译码求出其平均码长。

解：（1(2)1,3,6是即时码。

5-2证明若存在一个码长为12,,,q l l l ⋅⋅⋅的唯一可译码，则一定存在具有相同码长的即时码。

证明：由定理可知若存在一个码长为Lq L L ,,2,1 的唯一可译码，则必定满足kraft 不等式∑=-qi l ir1≤1。

由定理44⋅可知若码长满足kraft 不等式，则一定存在这样码长的即时码。

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

5-3设信源126126()s s s S p p p P s ⋅⋅⋅⎡⎤⎡⎤=⎢⎥⎢⎥⋅⋅⋅⎣⎦⎣⎦，611i i p ==∑。

将此信源编码成为r 元唯一可译变长码（即码符号集12{,,,}r X x x x =⋅⋅⋅），其对应的码长为（126,,,l l l ⋅⋅⋅）=（1，1，2，3，2，3），求r 值的最小下限。

解：要将此信源编码成为 r 元唯一可译变长码，其码字对应的码长（l 1 ,l 2 ,l 3, l 4,l 5, l 6）=(1,1,2,3,2,3) 必须满足克拉夫特不等式，即132321161≤+++++=------=-∑r r r r r r ri li所以要满足122232≤++r r r ，其中 r 是大于或等于1的正整数。

可见，当r=1时，不能满足Kraft 不等式。

当r=2, 1824222>++，不能满足Kraft 。

当r=3,127262729232<=++，满足Kraft 。

所以，求得r 的最大值下限值等于3。

5-4设某城市有805门公务电话和60000门居民电话。

作为系统工程师，你需要为这些用户分配电话号码。

所有号码均是十进制数，且不考虑电话系统中0、1不可用在号码首位的限制。

（提示：用异前缀码概念） （1）如果要求所有公务电话号码为3位长，所有居民电话号码等长，求居民号码长度1L 的最小值；（2）设城市分为A 、B 两个区，其中A 区有9000门电话，B 区有51000门电话。

现进一步要求A 区的电话号码比B 区的短1位，试求A 区号码长度2L 的最小值。

解：(a) 805门电话要占用1000个3位数中的805个，即要占用首位为0～ 7的所有数字及以8为首的5个数字。

因为要求居民电话号码等长， 以9为首的数字5位长可定义10 000个号码，6位长可定义100 000 个号码。

所以min L 16=。

或由Craft 不等式，有805106000010131⨯+⨯≤--L 解得 L 1103180********5488≥--⨯=-log .， 即min L 16=(b) 在(a)的基础上，将80为首的数字用于最后5个公务电话，81～86 为首的6位数用于B 区51 000个号码，以9为首的5位数用于A 区9 000 个号码。

所以，min L 25=。

或由Draft 不等式，有 80510900010510001013122⨯+⨯+⨯≤---+L L ()或 8051090005100010101312⨯++⨯⨯≤---()L解得L 2103180510900051004859≥--⨯+=-log . 即min L 25=5-5求概率分布为)152,152,51,51,31(的信源的二元霍夫曼码。

讨论此码对于概率分布为)51,51,51,51,51(的信源也是最佳二元码。

解：信源的概率分布为：)152,152,51,51,31()(=i s p二元霍夫曼码：00，10，11，010，011，码长：2，2，2，3，3当信源给定时，二元霍夫曼码是最佳二元码。

所以对于概率分布为)51,51,51,51,51(的信源，其最佳二元码就是二元霍夫曼码。

这二元霍夫曼码一定是三个信源符号的码长为2（码符号/信源符号），另二个信源符号的码长为3（码符号/信源符号），其平均码长最短。

因此，上述对概率分布为)152,152,51,51,31(信源所编的二元霍夫曼码也是概略分布为)51,51,51,51,51(信源的最佳二元码。

5-6 设二元霍夫曼码为（00，01，10，11）和（0，10，110，111），求出可以编得这些霍夫曼码的信源的所有概率分布。

解：由题意 假设信源所发出的是个符号的概率为 )P(S )P(S )P(S )P(S 1234≥≥≥ 由霍夫曼编码的特点知：1)P(S )P(S )P(S )P(S 1234=+++根据霍夫曼编码的方法，每次概率最小的两个信源符号合并成一个符号，构成新的缩减信源，直至最后只剩两个符号。

而且当缩减信源中的所有符号概率相等时，总是将合并的符号放在最上面。

所以，对于二元霍夫曼码为（00，01，10，11）来说，每个信源都要缩减一次，所以34()()P S P S +要大于1()P S 和2()P S ，这时必有12111P(S )P(S ),P(S )33+≥≤同理对于二元霍夫曼码为（0，10，110，111）有34111P(S )P(S ),P(S )>33+<信源概率分布满足以上条件则其霍夫曼编码符合题意。

5-7 设一信源有K =6个符号，其概率分别为：123()1/2,()1/4,()1/8P s P s P s ===，45()()1/20P s P s ==，6()1/40P s =，对该信源进行霍夫曼二进制编码，并求编码效率。

解：相应的Huffman 编码是：{1,01,001,0001,00000,00001}。

平均码长=1.95，熵=1.94 () 1.940.9951.95log 2H X L η===5-8 设信源概率空间为：()⎥⎦⎤⎢⎣⎡s P S =⎥⎦⎤⎢⎣⎡9.0,1.0,21s s ，（1）求()S H 和信源冗余度；（2）设码符号为X ={0,1}，编出S 的紧致码，并求紧致码的平均码长L ；（3）把信源的N 次无记忆扩展信源N S 编成紧致码，试求N =2，3，4，∞时的平均码长⎪⎪⎭⎫ ⎝⎛N L N ； （4）计算上述N =1，2，3，4这四种码的编码效率和码冗余度。

解：（1）信源()=⎥⎦⎤⎢⎣⎡s P S ⎥⎦⎤⎢⎣⎡9.01.021s s 其 ()()()≈-=∑=ii is P s P s H log 210.469 比特/符号剩余度()=-=2log 1s H γ0.531=53.1％（2）码符号X={0,1}，对信源S 编紧致码为：1s 0→，12→s 其平均码长L =1 码符号/信源符号 (3) 当N=2时()⎥⎦⎤⎢⎣⎡i P S α2=⎥⎦⎤⎢⎣⎡====81.0,09.0,09.0,01.0,,,224133212111s s s s s s s s αααα 紧致码（即霍夫曼码）为,4α ,3α ,2α 1α码字i W 0 , 10 , 110 , 111 码长i l 1 , 2 , 3 , 3平均码长⎪⎪⎭⎫ ⎝⎛N LN=21()ii ilP ∑=41α≈0.645 码符号/信源符号N=3时，()⎥⎦⎤⎢⎣⎡i P S α3=()()()()()()()()⎥⎦⎤⎢⎣⎡⋅⋅⋅⋅⋅⋅32222223876543219.0,9.01.0,9.01.0,9.01.0,9.01.0,9.01.0,9.01.0,1.0,,,,,,,αααααααα 对信源3S 进行霍夫曼编码，其紧致码为,8α ,7α ,6α ,5α ,4α ,3α ,2α1α码字i W 0 , 100 , 101 , 110 , 11100 , 11101 , 11110 ,11111码长i l 1 , 3 , 3 , 3 , 5 , 5 , 5 ,5平均码长 ⎪⎪⎭⎫⎝⎛N L N=31()ii ilP ∑=81α≈0.533 码符号/信源符号N=4时，()⎥⎦⎤⎢⎣⎡i P S α4=()()()()()()()()()()()⎢⎣⎡,9.01.0,9.01.0,9.01.0,9.01.0,9.01.0,9.01.0,9.01.0,1.0,,,,,,,,2222223333487654321αααααααα()()()()()()()()()()()⎥⎦⎤433332222221615141312111099.0,9.01.0,9.01.0,9.01.0,9.01.0,9.01.0,9.01.0,9.01.0,,,,,,,αααααααα 对信源4S 进行霍夫曼编码，其紧致码为,16α ,15α ,14α ,13α ,12α ,11α ,10α,9α码字i W 0 , 100 , 101 , 110 , 1110 , 111110 , 1111000 ,1111001,码长i l 1 , 3 , 3 , 3 , 4 , 6 , 7 , 7 ,,8α ,7α ,6α ,5α ,4α ,3α ,2α 1α 码字i W 1111010 , 1111011 , 1111110 , 111111101 , 111111110 , 111111111 , 1111111000 , 1111111001码长i l 7 , 7 , 7 , 9 , 9 , 9 , 10 , 10平均码长⎪⎪⎭⎫ ⎝⎛N LN=41()≈∑=ii ilP 161α0.493 码符号/信源符号N=∞时，根据香农第一定理，其紧致码的平均码长∞→N limN L N =()rs H log ≈0.469 码符号/信源符号 (4) 编码效率 ()()L S H L S H r ==η (r=2)码剩余度 1－()()LS H L S H r -=-=11η (r=2) 所以 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 不很大时，就可以达到高效的无失真信源编码。

5-9设信源空间为：⎥⎦⎤⎢⎣⎡)s (P S =123456780.40.20.10.10.050.050.050.05s s s s s s s s ⎡⎤⎢⎥⎣⎦，码符号为X ={0,1,2}，试构造一种三元紧致码。

解：得信源符号 s 1 s 2 s 3 s 4 s 5 s 6 s 7 s 8 三元紧致码 1 00 02 20 21 22 010 0115-10 某气象员报告气象状态，有四种可能的消息：晴、云、雨和雾。