信息论与编码201280572.ppt

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * (2) 自然语言信源 汉字统计的成果已被总结成国家标准 例如：GB2312-80、GB18030-2000等， 给出了一级字库、二级字库和三级字库 由于文字的使用总是与时俱进的，这种统计的工作必然一直是有意义的。 与英文类似，汉字同样必须考虑其关联性。 (2) 自然语言信源 可以用符号的联合概率或条件概率来描述自然语信源的关联性。 对于英文，可以将包含K个字母的单词看成是具有K个字母的符号序列，或称为K重符号序列，将其作为一个整体消息，其联合概率就已考虑了字母与字母间的关联性了。 也可以把由汉字组成的中文词汇作为符号序列。 还可以将句子、段落甚至整篇文章分别作为符号序列来考虑，用联合概率来描述。 有了符号或符号序列的信源空间就可以度量它们出现时所给出的信息量，并可以计算它们的信源熵。 (2) 自然语言信源 但无论是符号概率还是符号序列的联合概率都具有先验概率的性质，只能描述静态的情形，不能描述动态的过程。 条件概率描述了符号间的记忆特性，但它同时给出了符号间的转移特性，故也称之为转移概率。 以用第一个字母为T来构成3个字母的英文单词为例，第二个字母为H的概率可以用条件概率 P(H|T)来表示，第三个字母为E的概率可以用条件概率P(E|TH)来表示，其它各种可能的组合也都可用其条件概率来表示。 用转移概率来描述的信源就是一种典型的马尔可夫信源 (2) 举例－英语信源的熵 ① 把英语看成是离散无记忆信源 ② 把英语看成马尔可夫信源 ① 把英语看成是离散无记忆信源 英语字母26个，加上一个空格，共27个符号。 英语信源的最大熵(等概率) H0=log227=4.76(比特/符号) 英语字母并非等概率出现，字母之间有严格的依赖关系。表2.2.2是对27个符号出现的概率统计结果。 如果不考虑符号间的依赖关系，近似认为信源是离散无记忆的，则 按表2.2.2的概率分布，随机地选择英语字母并排列起来，得到一个输出序列： AI_NGAE_ITE_NNR_ASAEV_OTE_BAINTHA_HYROO_PORE_SETRYGAIETRWCO_EHDUARU_EUEU_C_FT_NSREM_DIY_EESE_F_O_SRIS_R_UNNASHOR… 这个序列看起来有点像英语，但不是。实际英语的某个字母出现后，后面的字母并非完全随机出现，而是满足一定关系的条件概率分布。例如T后面出现H,R的可能性较大，出现J,K,M,N的可能性极小，而根本不会出现Q,F,X。即英语字母之间有强烈的依赖性。上述序列仅考虑了字母出现的概率，忽略了依赖关系。 ② 把英语看成马尔可夫信源 为了进一步逼近实际情况，可把英语信源近似看做1阶，2阶，…∞阶马尔可夫信源，它们的熵为 H2=3.32(比特/符号) H3=3.1(比特/符号) 若把英语信源近似成2阶马尔可夫信源，可得到某个输出序列： IANKS_CAN_OU_ANG_RLER_THTTED_OF_TO_SHOR_OF_TO_HAVEMEM_A_I_MAND_AND_BUT_WHISS_ITABLY_THERVEREER… 这个序列中被空格分开的两字母或三字母，组成的大都是有意义的英语单词，而四个以上字母组成的“单词”，很难从英语词典中查到。因为该序列仅考虑了3个以下字母之间的依赖关系。实际英语字母之间的关系延伸到更多的符号，单词之间也有依赖关系。 有依赖关系的字母数越多，即马尔可夫信源的阶数越高，输出的序列就越接近于实际情况。当依赖关系延伸到无穷远时，信源输出的就是真正的英语，此时可求出马尔可夫的极限熵 H∞ =1.4(比特/符号)。 (3) 信源的冗余度 讨论信源的最主要目的是为了得到高效率的信源编码。 衡量信源编码效率的尺度是什么呢？ 或者说能够使信源编码提高效率的根本原因是什么呢？ 下面讨论的信源冗余度将回答这些问题。 (3) 信源的冗余度 ① 信息传输手段的浪费 ② 信源冗余度定义及意义 ③ 重要结论 离散信源的时间熵 ① 信息传输手段的浪费 对一般离散平稳信源， H∞就是实际信源熵。理论上只要有传送H∞的手段，就能把信源包含的信息全部发送出去。但实际上确定H∞非常困难，只好用Hm来代替。 Hm+1H∞，所以在传输手段上必然富裕，这样做很不经济，特别是有时只能得到H1，甚至H0，就更不经济。这种浪费是由信源符号的相关性引起的。 ② 信源冗余度定义及意义 信源熵的相对率η ：为了衡量符号间的相互依赖程度，定义信源实际的信息熵与同样符号数的最大熵的比值为信源熵的相