第4章习题解答.doc

信息论与编码习题详解 第四章 - PAGE 42 - 4。1 某集源按P（0)=3/4，P(1）=1/4的概率产生统计独立的二元序列. (1) 试求N0，使当NN0时有： P｛｜I(ai)/N－H(S）｜ ≥0.05}≤0.01 其中H（S)是信源的熵。 (2)试求当N= N0时典型序列集GεN中含有的信源序列个数. 解： (1) H(S)= —∑Pi㏒Pi= -3/4㏒(3/4)—1/4㏒(1/4） =0.811 比特/符号 根据契比雪夫不等式，对于任意ε＞0，当N＞N0时， P｛∣I(αi)/N – H(S）∣≥ε｝≤D[I(Si）］/Nε2 现有ε=0.05,欲证原式，只要 D［I(Si）]/Nε2≤0。01 根据信源，D［I（Si)]=∑P（Si）［㏒P(Si)］2 – H2（S) =3/4（㏒3/4)2+1/4（㏒1/4)2—(0。811)2 =0。471 ∴N0= D[I(Si)]/0。01ε2=0.471/0。01×（0.05)2=18840 (2) 序列GεN是所有N长的ε典型序列集合， （1-δ）2N［H（S）—ε]≤‖GεN‖≤2N[H（S）-ε] 0.99×214342。5≤‖GεN‖≤216226。5 4。2 设无记忆二元信源，其概率为P1=0.005, P0=0。995.信源输出N＝100的二元序列.在长为N＝100的信源序列中只对含有3个或小于3个“1”的各信源序列构成一一对应的一组等长码。 （1）求码字所需的最小长度。 （2）计算式（4.27a）中的ε。 (3）考虑没有给予编码的信源序列出现的概率，该等长码引起的错误概率PE是多少？若从契比雪夫不等式（4。22）考虑，PE应是多少？试加以比较。 解： （1）无记忆二元信源 N=100的扩展信源 现只对含有3个或小于3个“1”的各信源序列构成一一对应的一组二元等长码。那么,在这个N长的信源序列中含有小于3个“1”和含有3个“1”的序列个数有 M==1+100+4950+161700166750 对M个信源序列进行无失真的二元等长编码，必须 =166750 所以码字所需的最小长度＝18 （2）对于这二元信源，其H（S）0。0454 比特/符号 现根据所编码的N（＝100)长的信源序列来计算。在这N长的信源序列中全零序列其最大，则其最小；而其中含3个“1”的序列其最小则最大。所以，全零序列 ＝ ＝－log P（)0。723 根据典型序列的条件有 所以 〉—0.0382- 得 0.0382 含3个“1”的序列其 ＝ ＝－log23.63 又可计算有 〉0。1909〉- 0.1909 由上分析 所以 〉0。1909 (3)按编码考虑，除了含有3个或小于3个“1”的信源序列给予了一一对应的编码外，其他信源序列没有给予编码，那么这些信源序列的出现会使编码带来错误。所以,本题等长码引起的错误概率就是其他序列的发生概率之和。得 0。0017 若按契比雪夫不等式考虑 即 其中由上面计算 而 所以 比较二种计算结果，可见 这是因为按照契比雪夫不等式所计算错误概率时，我们只是对典型序列进行编码,非典型不编码就引起错误。现典型序列个数为 而我们实际是对所有含3个和小于3个“1”的信源序列都进行编码，其个数M》,所以 4。3有一信源它有六种可能的输出，其概率分布如下图所示，表中给出了对应的码A、B、C、D、E和F。 （1）求这些码中哪些是唯一可以码. （2）求哪些是非延长码（即时码) （3）对所有唯一可译码求出其平均码长 消息 P(ai) A B C D E F a1 a2 a3 a4 a5 a6 1/2 1/4 1/16 1/16 1/16 1/16 000 001 010 011 100 101 0 01 011 0111 01111 011111 0 10 110 1110 11110 111110 0 10 110 1110 1011 1101 0 10 1100 1101 1110 1111 0 100 101 110 111 011 解：（1）A码为等长码且是非奇异码 所以是唯一可译码 B码和C码由唯一可译码的判定方法知识唯一可译码 D码由Craft不等式知不满足不等式所以不是唯一可译码 E码由即时码的定义知E码是即