信源编码.ppt

《信源编码.ppt》由会员分享，可在线阅读，更多相关《信源编码.ppt（62页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、信息论与编码技术展爱云通信工程教研室Coding and Information Theroy本课程的相关要求课程基础（概率论）上课要求 学习要求实验要求（CC+)本课程的重点信息的基本概念信息量的计算典型的几种信源编码方法典型的几种信道编码方法无失真信源编码定理-香农第一定理信道编码定理-香农第二定理限失真信源编码定理-香农第三定理第5章 信源编码编码的意义编码的意义编码定义编码定义最佳编码方法第5章 信源编码M=m1,m2,mnA=a1,a2,anC=c1,c2,cn一、编码的意义一、编码的意义第5章 信源编码信源编码的目的：信源编码的目的：1、便于信道的传输、便于信道的传输例如：语音信号

2、的数字传输例如：语音信号的数字传输2、提高有效性、提高有效性第5章 信源编码例：设某计算机终端用来控制检查流水线上产品的质量，按优、中、劣三级来分类记录。从统计中已知产品在三级中的比例为优、劣各占1/4，中占1/2。以下研究如何将检查结果编成二进制码，以通过网络传送到主机中进行存储和处理。第5章 信源编码第一种编码方法：产 品 等级出现概率编码优1/411中1/210劣1/400第5章 信源编码平均编码长度：L1=1/4*2+1/2*2+1/4*2=2bit/符号第5章 信源编码产 品 等级出现概率编码优1/41中1/210劣1/400第二种编码方法第5章 信源编码平均编码长度：L2=1/4*

3、1+1/2*2+1/4*2=1.75bit/符号第5章 信源编码产 品 等级出现概率编码优1/411中1/21劣1/400第三种编码方法第5章 信源编码平均编码长度：L3=1/4*2+1/2*1+1/4*2=1.5bit/符号第5章 信源编码结论：1、不同的编码方法，平均的编码长度不一样2、L1L2L3第5章 信源编码思考：为什么平均编码长度不一样？第5章 信源编码结论：概率越大，用的码长短，则平均编码长度则越小。第5章 信源编码二、编码定义1、等长码和变长码如果一种码的各个码字都是由同样多个码元构成的，则成为等长码。例如：00，01，10第5章 信源编码2、单义码和非单义码如果由W的一组码字

4、构成的任意长的码序列，只能有唯一的方式分割成若干前后连接的码字，则W叫做单义码。例如：1，01，0010001101例如：0，10，0101001思考一下，有没有其他的划分01001第5章 信源编码3、码树码树是表示元素之间的结构层次的方法。第5章 信源编码4、非续长码任意一个码字都不是由另外一个码字的续长而成的。例如：W=0，10，11非续长W=0，10，100续长第5章 信源编码5、平均编码长度设N个码字中的第I个码字的长度为ni,他所代表的编码对象xi的概率为p(xi),则码字的平均编码长度为：L=p(xi)ni第5章 信源编码6、编码效率最小的平均编码长度和实际的编码长度的比值。Lmi

5、n=H(X)/logD=Lmin/L编码的剩余度r=1-第5章 信源编码产 品 等级出现概率编码优1/411中1/21劣1/400例:第5章 信源编码平均编码长度：L3=1/4*2+1/2*1+1/4*2=1.5bit/符号Lmin=1.5=1第5章 信源编码三、最佳编码方法满足两个条件：1、唯一可译性2、码长是最小的第5章 信源编码1、香农编码1)步骤A将信源符号按概率从大到小排列B求累加和C求自信息量，确定码字长度D将累加和用二进制表示，并取小数点后码字的长度的码字第5章 信源编码2)编码过程例:有离散无记忆信源X=x1,x2,x3,x4,x5,x6,相应的概率矩阵为P(X)=0.250.

6、25,0.2,0.15,0.1,0.05,对该信源进行二进制香农编码。第5章 信源编码xip(xi)Pa(xi)ki码字X10.250.000200X20.250.250201X30.200.5003100X40.150.7003101X50.100.85041101X60.050.950511110第5章 信源编码平均编码长度：L=0.25*2+0.25*2+0.20*3+0.15*3+0.10*4+0.05*5=2.7bit/符号H(X)=2.42bit/符号=86.93%3)结论：香农编码的剩余度较大，实用性不大，但有重要的意义。思考一下，什么时候可以使编码效率高呢？第5章 信源编码第5

7、章 信源编码2、费诺编码1）步骤A将概率按从大到小的顺序排列B按编码进制数将概率分组，使每组概率和尽可能接近或相等。C给每组分配一位码元D将每一分组再按同样原则划分，重复b和c，直到概率不再可分为止第5章 信源编码2）编码过程例、有离散无记忆信源X=x1,x2,x3,x4,x5,x6,相应的概率矩阵为P(X)=0.250.25,0.2,0.15,0.1,0.05,对该信源进行二进制费诺编码。第5章 信源编码xip(xi)码字X10.250000X20.25101X30.201010X40.1510110X50.10101110X60.0511111第5章 信源编码H(X)=2.42bit/符号

8、L=0.25*2+0.25*2+0.20*2+0.15*3+0.10*4+0.05*4=2.45bit/符号=98.77%思考一下，什么时候可以使编码效率高呢？Huffman 编码就是利用就是利用变字字长最佳最佳编码实现信信源符号按概率大小源符号按概率大小顺序排列。序排列。第5章 信源编码3、哈夫曼编码（Huffman)第5章 信源编码1）步骤A把信源符号按概率大小顺序排列，并设法按逆次序分配码字的长度。B在分配码字长度时，首先将出现概率最小的两个符号的概率相加合成一个概率C把这个合成概率看成是一个新组合符号地概率，重复上述做法直到最后只剩下两个符号概率为止。D完成以上概率顺序排列后，再反过来

9、逐步向前进行编码，每一次有二个分支各赋予一个二进制码，可以对概率大的赋为零，概率小的赋为1。2)编码过程例、有离散无记忆信源X=x1,x2,x3,x4,x5,x6,x7,相应的概率矩阵为P(X)=0.20.19,0.18,0.17,0.15,0.10，0.01,对该信源进行二进制哈夫曼编码。第5章 信源编码第5章 信源编码x10.2001x20.1900 x30.18111x40.17110 x50.15101x60.101001x70.01100010111000.3900.3510.2600.1100.611第5章 信源编码思考：哈夫曼编码的方法唯一么？不同的结果，会使得平均编码长度不一样

10、么？第5章 信源编码例：单符号离散无记忆信源X=x1,x2,x3,x4,x5，相应的概率矩阵为P(X)=0.40.2,0.2,0.1,0.1,对该信源进行二进制哈夫曼编码。x10.4x20.2x30.2x40.1x50.1010.2010.4010.60101011011101111L=0.4*1+0.2*2+0.2*3+0.1*4+0.1*4=2.2第5章 信源编码x10.4x20.2x30.2x40.1x50.10.20.401010.600110101100110111L=0.4*1+0.2*3+0.2*3+0.1*3+0.1*3=2.2第5章 信源编码x10.4x20.2x30.2x4

11、0.1x50.10.2010.40110.601.001100001110111L=0.4*2+0.2*2+0.2*2+0.1*3+0.1*3=2.2第5章 信源编码3)结论：(p178)在哈夫曼的编码过程中，对缩减信源符号按概率有大到小的顺序重新排列时，应使合并后的新符号尽可能排在靠前的位置。第5章 信源编码哈夫曼方法构造出来的码不是唯一的。原因原因在给两个分支赋值时,可以是左支(或上支)为0,也可以是右支(或下支)为0,造成编码的不唯一。当两个消息的概率相等时,谁前谁后也是随机的,构造出来的码字就不是唯一的。哈夫曼编码码字字长参差不齐,因此硬件实现起来不大方便。4)哈夫曼编码的特点第5章

12、信源编码哈夫曼编码对不同的信源的编码效率是不同的。当信源概率是2的负幂时,哈夫曼码的编码效率达到100%;当信源概率相等时,其编码效率最低。只有在概率分布很不均匀时,哈夫曼编码才会收到显著的效果,而在信源分布均匀的情况下,一般不使用哈夫曼编码。第5章 信源编码对信源进行哈夫曼编码后,形成了一个哈夫曼编码表。解码时,必须参照这一哈夫编码表才能正确译码。在信源的存储与传输过程中必须首先存储或传输这一哈哈夫曼编码表夫曼编码表在实际计算压缩效果时,必须考虑哈夫曼编码表占有的比特数。在某些应用场合,信源概率服从于某一分布或存在一定规律(这主要由大量的统计得到),这样就可以在发送端和接收端固定哈夫曼编码表

13、,在传输数据时就省去了传输哈夫曼编码表,这种方法称为哈夫曼编码表缺省使用。第5章 信源编码使用缺省的哈夫曼编码表有两点好处两点好处:降低了编码的时间,改变了编码和解码的时间不对称改变了编码和解码的时间不对称性性;便于用硬件实现,编码和解码电路相对简单。这种方编码和解码电路相对简单。这种方法适用于实时性要求较强的场合。虽然这种方法对某一法适用于实时性要求较强的场合。虽然这种方法对某一个特定应用来说不一定最好个特定应用来说不一定最好,但从总体上说但从总体上说,只要哈夫只要哈夫曼编表基于大量概率统计曼编表基于大量概率统计,其编码效果是足够好的。其编码效果是足够好的。第5章 信源编码5)应用：文本压缩

14、技术霍夫曼（Huffman）编码第5章 信源编码霍夫曼编码实例 第5章 信源编码Finaltreeandcode第5章 信源编码Huffmanencoding第5章 信源编码Huffmandecoding第5章 信源编码4Run-lengthencoding(游程长度编码游程长度编码)将数据中连续出现的符号用符将数据中连续出现的符号用符号和该符号重复的次数来代替。号和该符号重复的次数来代替。第5章 信源编码游程编码（Run-Length Encoding）：它通过将信源中相同符号序列转换成一个计数字段再加上一个重复字符标志实现压缩。第5章 信源编码Run-lengthencodingexamp

15、le第5章 信源编码游程编码多用于黑白二值图像的压缩中。例如00000000111111111111000001111111被转化为一系列黑串和白串长度的编码：81257。因为串长度并非等概率分布，所以一般要配合以统计编码（Huffman编码）。第5章 信源编码RLE编码简单直观，编码/解码速度快，因此许多图形和视频文件，如.BMP.TIFF及AVI等格式文件的压缩均采用此方法.第5章 信源编码5 算术编码基本思想：算术编码不是将单个信源符号映射成一个码字，而是把整个信源表示为实数线上的0到1之间的一个区间，其长度等于该序列的概率，再在该区间内选择一个代表性的小数，转化为二进制作为实际的编码输

16、出。消息序列中的每个元素都要用来缩短这个区间。消息序列中元素越多，所得到的区间就越小，当区间变小时，就需要更多的数位来表示这个区间。采用算术编码每个符号的平均编码长度可以为小数。第5章 信源编码算术编码举例符号00011011概率0.10.40.20.3初始区间0,0.1)0.1,0.5)0.5,0.7)0.7,1)第5章 信源编码6 词典编码词典编码主要利用数据本身包含许多重复的字符串的特性。例如：吃葡萄不吐葡萄皮，不吃葡萄倒吐葡萄皮。我们如果用一些简单的代号代替这些字符串，就可以实现压缩，实际上就是利用了信源符号之间的相关性。字符串与代号的对应表就是词典。实用的词典编码算法的核心就是如何动态地形成词典，以及如何选择输出格式以减小冗余。第5章 信源编码词典编码举例词典法的想法是企图查找正在压缩的字符序列是否在以前输入的数据中出现过，然后用已经出现过的字符串替代重复的部分，它的输出仅仅是指向早期出现过的字符串的“指针”。第5章 信源编码