限失真信源编码
- 格式:pptx
- 大小:2.56 MB
- 文档页数:54
对香农三大定理的分析与探讨摘要本文针对香农三大定理的内容,进行理论分析,探讨了无失真信源编码、有噪信道编码和保真度准则下的信源编码定理。
通过对离散信源熵的分析,延伸到了对扩展信源的理解,同时结合著名的香农公式和信息论与编码的发展史,指出了香农三大定理的意义。
一、香农第一定理香农第一定理主要研究信息的测度,对应的是无失真信源编码定理。
采用无失真最佳信源编码,可以使得用于每个信源符号的编码位数尽可能地小,但它的极限是原始信源的熵值,超过了这一极限就不可能实现无失真的译码。
1.1 离散信源熵1.1.1 信源的概念信源发出消息,消息载荷信息,而消息又具有不确定性,故而可以用随机变量或随机矢量来描述信源输出的消息。
从随机变量出发来研究信息,这正是香农信息论的基本假说。
而离散信源指的是这类信源输出的消息常以一个符号、一个符号的形式出现,这些符号的取值是有限的或者是可数的。
单符号离散信源只涉及一个随机事件,多符号离散信源则涉及多个随机事件。
1.1.2 信源熵的概念及其性质在度量信息的各种方法中,香农提出了解决信息度量问题的方法——熵,这是香农信息论最基本的,也是最重要的概念[1]。
信源熵,即信源的信息熵,又称香农熵、无条件熵,简称熵。
信源各个离散消息的自信息量的数学期望是信源的平均信息量,实质上是无记忆信源平均不确定度的度量。
信源熵表示在信源输出消息前,信源的平均不确定度,也表示在信源输出消息后,平均每个离散消息所提供的信息量,能够反映变量的随机性。
当消息出现的概率相同时,猜测每一个消息发生错误的概率均相同,说明等概率信源的不确定性最大,具有最大熵[2]。
1.2 无失真离散信源编码1.2.1 信源编码的概念信源编码处于通信系统的前端,直接对信源发出的信号进行变换处理。
通过压缩每个信源符号的平均比特数或信源的码率,以较少的码率来传送同样多的信息,增加单位时间内传送的平均信息量,来压缩信源的冗余度,从而提高通信的有效性。
1. 在无失真的信源中,信源输出由 H (X ) 来度量;在有失真的信源中,信源输出由 R (D ) 来度量。
2. 要使通信系统做到传输信息有效、可靠和保密,必须首先 信源 编码, 然后_____加密____编码,再______信道_____编码,最后送入信道。
3. 带限AWGN 波形信道在平均功率受限条件下信道容量的基本公式,也就是有名的香农公式是log(1)C W SNR =+;当归一化信道容量C/W 趋近于零时,也即信道完全丧失了通信能力,此时E b /N 0为 -1.6 dB ,我们将它称作香农限,是一切编码方式所能达到的理论极限。
4. 保密系统的密钥量越小,密钥熵H (K )就越 小 ,其密文中含有的关于明文的信息量I (M ;C )就越 大 。
5. 已知n =7的循环码42()1g x x x x =+++,则信息位长度k 为 3 ,校验多项式 h(x)= 31x x ++ 。
6. 设输入符号表为X ={0,1},输出符号表为Y ={0,1}。
输入信号的概率分布为p =(1/2,1/2),失真函数为d (0,0) = d (1,1) = 0,d (0,1) =2,d (1,0) = 1,则D min = 0 ,R (D min )= 1bit/symbol ,相应的编码器转移概率矩阵[p(y/x )]=1001⎡⎤⎢⎥⎣⎦;D max = 0.5 ,R (D max )= 0 ,相应的编码器转移概率矩阵[p(y/x )]=1010⎡⎤⎢⎥⎣⎦。
7. 已知用户A 的RSA 公开密钥(e,n )=(3,55),5,11p q ==,则()φn = 40 ,他的秘密密钥(d,n )=(27,55) 。
若用户B 向用户A 发送m =2的加密消息,则该加密后的消息为 8 。
二、判断题1. 可以用克劳夫特不等式作为唯一可译码存在的判据。
(√ )2. 线性码一定包含全零码。
(√ )3. 算术编码是一种无失真的分组信源编码,其基本思想是将一定精度数值作为序列的 编码,是以另外一种形式实现的最佳统计匹配编码。
第8章无失真的信源编码●信源编码主要可分为无失真信源编码和限失真信源编码。
●无失真信源编码主要适用于离散信源或数字信号,要求进行无失真地数据压缩,要求完全能够无失真地可逆恢复。
●限失真信源编码主要适用于波形信源或波形信号(即模拟信号),不要求完全可逆地恢复,而是允许在一定限度内可以有失真的压缩。
●两种信源编码都是为了用较少的码率来传送同样多的信息,增加单位时间内传送的信息量,从而提高通信系统的有效性。
香农信息理论——香农第一定理和香农第三定理是信源压缩编码的理论基础,从理论上给出了进行无失真信源压缩和限失真信源压缩的理论极限,还论证与指出了理想最佳信源编码是存在的,但没有给出信源编码实际构造方法和实用码的结构。
本章主要研究无失真信源编码的技术和方法。
从第5章香农第一定理已知,信源的信息熵是信源进行无失真编码的理论极限值。
总能找到某种合适的编码方法使编码后信源的信息传输率R’任意地逼近信源的信息熵而不存在任何失真。
在数据压缩技术中无失真信源编码又常被称为熵编码。
从第二章的讨论可知,正是由于信源概率分布的不均匀性,或者信源是有记忆的、具有相关性,使信源中或多或少含有一定的剩余度。
只要寻找到去除相关性或者改变概率分布不均匀的方法和手段,就能找到熵编码的具体方法和实用码的结构。
●本章首先讨论了典型的霍夫曼编码、游程编码及算术编码的原理和方法。
这都是当信源的统计特性已确知时,能达到或接近压缩极限界限的编码方法。
前者主要适用于多元独立的信源,后两者主要适用于二元信源及具有一定相关性的有记忆信源。
最后讨论了通用编码(又称字典码)的原理和方法。
是针对信源的统计特性未确知或不知时所采用的压缩编码方法。
●本章主要介绍霍夫曼编码。
香农Shannon 编码——非最佳码 香农码的编码流程:1、将信源符号以概率递减次序排列起来。
2、确定满足下列不等式的整数码长3、为编成唯一可译码,计算第i 个消息的累加概率:4、将累加概率P i 变换成二进制数。