信息论第四章

《信息论第四章》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第四章无失真信源编码4.1编码器4.2等长码4.3渐进等分割性和典型序列4.5变长码4.4等长信源编码定理4.6变长信源编码定理4.7霍夫曼码和其他编码方法第四章无失真信源编码1、信源编码的目的——第4章、第7章在不失真或允许一定失真条件下，如何用尽可能少的符号来传送信源信息，以便提高信息传输率。2、信道编码的目的——第5章在信道受干扰的情况下，如何增加信号的抗干扰能力，同时又使得信息传输率最大。4.1编码器4.1.1编码器的构成4.1.2有关常用码的概念4.1编码器4.1.1编码器的构成编码器S:信源符号码符号

2、，或码元编码实质上是对信源的原始符号按一定的数学规则进行的一种变换。码字长度或码长C码字(信源符号)(信源序列)码字由码元组成码C由码字组成编码就是从信源符号到码字的一种映射，且一一对应，可逆，则可实现无失真编码。4.1.2有关常用码的概念1、二元码码符号集为，所得码字是二元序列。二元码是数字通信和计算机系统中最常用的一种码。2、等长码一组码中所有码字的码长都相同。3、变长码一组码中所有码字的码长各不相同。4、非奇异码C一组码中所有码字都不相同。即5、奇异码C一组码中有相同的码字。即6、同价码码符号集中每个码符号

3、所占的传输时间都相同。一般二元码是同价码。对于同价码，等长码中每个码字的传输时间都相同，变长码每个码字的传输时间就不一定相同7、码的N次扩展码N次扩展信源对应的N个码字组成的码字序列的集合。N次扩展码举例信源符号的码和二次扩展码的形式信源符号si符号概率P(si)码1码2s1P(s1)000s2P(s2)0101s3P(s3)10001s4P(s4)11111表4.1等长码变长码非奇异码表码2的二次扩展码信源符号扩展码字信源符号扩展码字信源S的二次扩展信源信源S的二次扩展码8、唯一可译码码的任意一串有限长的码符号

4、序列只能被唯一地译成所对应的信源符号序列，则此码称唯一可译码或单译可译码。(1)信源符号对应的码是非奇异码。(2)任意有限长的N次扩展码是非奇异的。表4.1中，码1是唯一可译码，而码2是非唯一可译码。例：码符号序列“0010”“0010”4.2等长码4.2.1等长码的唯一可译性4.2.2等长码的编码长度4.2等长码4.2.1等长码的唯一可译性若等长码是非奇异码，则它的任意有限长N次扩展码一定也是非奇异码，因此一定是唯一可译码。信源符号si符号概率P(si)码1码2s1P(s1)0000s2P(s2)0111s3P

5、(s3)1010s4P(s4)1111表4.2唯一可译码非唯一可译码4.2.2等长码的编码长度1、q个信源符号：码元数为r：则码长必须满足下式例:(1)(2)（表4.2）个信源符号：可得到等长非奇异码取对数：当N=1时是平均每个信源符号所需要的码符号个数。2、对N次扩展信源编码则3、等长码的码长仍可压缩考虑符号出现的概率和符号间的依赖关系，码长可压缩。例：其余且二次扩展信源理论上有个符号,此时压缩至4个符号,编码即可.结论:考虑信源符号间的依赖关系后,再考虑符号出现的概率时,所需平均码长可能缩短.4.3渐进等分割

6、性和典型序列对于离散无记忆信源N次扩展信源当为有限值时,定理4.1渐进等分割性(AEP):若随机序列中相互统计独立并且服从同一概率分布,又，则依概率收敛于。也可表示成,对于任意弱大数定律:此渐近等分割性说明,离散无记忆信源的N次扩展信源中,信源序列的自信息的均值以概率收敛于信源熵.当N为有限长时,在所有个长为N的信源序列中必有一些,其自信息量的均值与信源熵之差小于,即:或称N长序列为典型序列.中所有典型序列的集合表示为非典型序列集(2)若，则(3)设表示典型序列集中包含的典型序列的个数，定理4.2:对于任意小的正

7、数当N足够大时，则(1)而显然证明:(1)可由定理4.1直接推得当时，由契比可夫不等式当依概率收敛于(2)可由变形证得。推论：当N足够大时，可任意小，表明典型序列出现的概率近似相等，所以称为渐进等概率序列。(3)由上述性质(2)证得。性质(1)表明，典型序列是经常出现的信源序列。时，成为必然事件。性质(2)表明接近等概分布性质(3)表明当时,典型序列的总数占信源序列的比值为：一般所以，当即是高概率集，但它含有序列数常常比非典型序列数要少很多。所有信源序列非典型序列集典型序列集结论：我们可以只对少数的高概率典型序列

8、进行一一对应的等长编码。这样码字总数减少，所需码长就可以减少了。4.4等长信源编码定理4.4.1等长信源编码定理4.4.2平稳有记忆信源的码长4.4.3对于编码好坏的评价4.4.1等长信源编码定理—定理4.31、定理内容：一个离散无记忆信源，熵为，信源长为N，码符号r个，码字长，对于任意，只要满足则当N足够大时，可实现几乎无失真编码。即译码错误概率能为任意小。反之，若则不