5.1 有一信源，它有6个可能的输出，其概率分布如题5.1表所示，表中给出了对应的码
A,B,C,D,E 和 F。
题表 5.1 消息 p(ai) 1/2 1/4 1/16 1/16 1/16 1/16 A 000 001 010 011 100 101 B 0 01 011 0111 01111 C 0 10 110 1110 11110 D 0 10 110 1110 1011 1101 E 0 10 1100 1101 1100 1111 F 0 100 101 110 111 011 a1 a2 a3 a4 a5 a6 011111 111110
(1) 求这些码中哪些是唯一可译码； (2) 求哪些是非延长码（即时码）； (3) 对所有唯一可译码求出其平均码长L。
解：
(1) 唯一可译码：A，B，C
A 是等长码，码长3，每个码字各不相同，因此是唯一可译码。 B 是非即时码，前缀码，是唯一可译码。 C 是即时码，是唯一可译码。
D 是变长码，码长{1, 2, 3, 4, 4, 4}，不是唯一可译码，因为不满足Kraft不等式。
?ri?li?1??1??1??1??????????????3?1.0625?1 ?2??2??2??2?1234E 是变长码，码长{1, 2, 4, 4, 4, 4}，满足Kraft不等式，但是有相同的码字，W3?W5?1100，不是唯一可译码。
?ri?li?1??1??1???????????4?1?1 ?2??2??2?124F 是变长码，码长{1, 3, 3, 3, 3, 3}，不满足Kraft不等式，不是唯一可译码。
?ri?li?1??1????????5?1.125?1 ?2??2?13
(2) 非延长码：A，C (3)
LA?3LB?LC??pi?li?i 111111?1??2??3??4??5??6?1.312524161616165.7 设离散信源的概率空间为
s2s3s4s5s6??S??s1?P???0.250.250.200.150.100.05?
????对其采用香农编码，并求出平均码长和编码效率。
解：
xi x1 x2 x3 x4 x5 x6 x7
p(xi) 0.2 0.19 0.18 0.17 0.15 0.1 0.01 pa(xi) 0 0.2 0.39 0.57 0.74 0.89 0.99 ki 3 3 3 3 3 4 7 码字 000 001 011 100 101 1110 1111110 L??pi?li?0.25?2?0.25?2?0.2?3?0.15?3?0.1?4?0.05?5?2.7iH(S)???pilogpi???0.25?log0.25?...?0.05?log0.05??2.423 bit
i??
H(S)2.423??89.7%L2.75.8 设无记忆二元信源，其概率p1?0.005, p2?0.995。信源输出N?100的二元序列。在长为N?100的信源序列中只对含有3个或小于3个“1”的各信源序列构成一一对应的一组等长码。
(1) 求码字所需要的长度；
(2) 考虑没有给予编码的信源序列出现的概率，该等长码引起的错误概率pE是多少？
解： (1)
0码字中有0个“1”，码字的个数：C100?1 1码字中有1个“1”，码字的个数：C100?100 2码字中有2个“1”，码字的个数：C100?4950
码字中有3个“1”，码字的个数：C100?161700
0123q?C100?C100?C100?C100?1?100?4950?161700?1667513rli?qli?logrq?log166751?17.35li?18
(2)
码字中有0个“1”，错误概率：pa1??0.995?100
码字中有1个“1”，错误概率：pa2??0.995??0.005
99码字中有2个“1”，错误概率：pa3??0.995???0.005?
982码字中有3个“1”，错误概率：pa4??0.995???0.005?
9730123p?G?N??pa1C100?pa2C100?pa3C100?pa4C100100 ?0.995?1?0.99599?0.005?100?0.99598? 0.0052?4950?0.99597?0.0053?161700 ?0.9983pE?1?p?G?N??1?0.9983?0.0017
5.9 设有离散无记忆信源
s2s3s4s5s6s7s8??S??s1??P??0.220.200.180.150.100.080.050.02?? ???码符号集X?{0, 1, 2}，现对该信源S进行三元哈夫曼编码，试求信源熵H(S)，码平均长度L和编码效率?。
解：
满树叶子节点的个数：r?k?r?1??3?2k??3, 5, 7, 9, ...?，q?8，不能构成满树。
si wi li s1 1 1 s2 22 2
s7s90.07s100.25s12s1s4s11s30.53s2s5s8s6s3 21 2 s4 20 2
s5 02 2 s6 01 2 s7 000 3 s8 001 3
L??pi?li?0.22?1?0.2?2?0.18?2?0.15?2?0.1?2?0.08?2?0.05?3?0.02?3?1.85
i