信息论基础-信源编码课件

数据压缩和信源编码3.1等长码3.2

变长编码3.3哈夫曼码3.4算术码

香农-费诺码3.5通用信源编码

LZW算法10.概述是第一个能够找到的好的变长码.原则：按照符号出现的概率从大到小排序，然后将其分成两个出现概率相同或几乎相同的子集—一个子集的编码均以0打头，另一个子集的编码均以1打头；然后把每个子集再分成两个更小的子集，同样确定所有码字的第二位，依次循环.

算术码—Shannon-Fano-Elias码2算术码—Shannon-Fano-Elias码例13算术码—Shannon-Fano-Elias码例25算术码—Shannon-Fano-Elias码例361.基本思路用二进制小数表示信源的概率分布，如果概率分布取值大，则它的二进制位数就低；另外，为了使算术码具有前缀性（无尾随后缀），对概率分布采用累计求和计算.

算术码—Shannon-Fano-Elias码7例1：若信源的概率分布为，取信号字母表为，求信源的算术码.算术码—Shannon-Fano-Elias码9例1：若信源的概率分布为，取信号字母表为，求信源的算术码.算术码—Shannon-Fano-Elias码10例1：若信源的概率分布为，取信号字母表为，求信源的算术码.算术码—Shannon-Fano-Elias码1011算术码—Shannon-Fano-Elias码13计算出给定信源香农码的平均码长若对上述信源采用等长编码，要做到无失真译码，每个符号至少要用3个比特表示。相比较，香农编码对信源进行了压缩。由离散无记忆信源熵定义，可计算出：对上述信源采用香农编码的信息率为编码效率为信源熵和信息率之比。则可以看出，编码效率并不是很高。算术码—Shannon-Fano-Elias码14思考（一）：用Shannon-Fano-Elias码方法将信源编成二元变长唯一可译码，并计算其码率.算术码—Shannon-Fano-Elias码15思考（二）：有两个信源X和Y如下：2)分别用Shannon-Fano-Elias编码法编成二元变长惟一可泽码．并计算编码效率.3)从X，Y两种不同信源来比较这三种编码方法的优缺点算术码—Shannon-Fano-Elias码17思考（二）：信源X的二元霍夫曼编码：算术码—Shannon-Fano-Elias码18算术码—Shannon-Fano-Elias码19思考（二）：信源Y的二元霍夫曼编码：算术码—Shannon-Fano-Elias码21算术码—Shannon-Fano-Elias码22思考（二）：信源Y的二元霍夫曼编码：其平均码长

编码效率算术码—Shannon-Fano-Elias码23算术码—Shannon-Fano-Elias码25思考（二）：信源X的Shannon-Fano编码：其平均码长

编码效率算术码—Shannon-Fano-Elias码26思考（二）：信源Y的Shannon-Fano码：算术码—Shannon-Fano-Elias码27思考（二）：信源Y的Shannon-Fano码：其平均码长

编码效率算术码—Shannon-Fano-Elias码29思考（二）：信源X的Shannon-Fano-Elias编码：其平均码长

编码效率算术码—Shannon-Fano-Elias码30思考（二）：信源Y的Shannon-Fano-Elias码：其平均码长

编码效率算术码—Shannon-Fano-Elias码31思考（二）：从信源X和Y的三种不同编码方法可以看出：Huffman编码所得平均码长最短，编码效率最高；Shannon-Fano-Elias编码所得平均码长最长，其编码效率最差；而Shannon-Fano码居中。算术码—Shannon-Fano-Elias码32Huffman码其编码时短码得到充分利用，而且一定是概率大的信源符号对应于短码，概率小的信源符号对应于长码：所以，其平均码长最短。

Shannon-Fano-Elias编码方法虽然概率大的符号其码长短，概率小的符号其码长长，但它短码没有被充分利用。所以，其平均码长增大。算术码—Shannon-Fano-Elias码33Shannon-Fano码也是一种较好的编码方法．如信源Y的Shannon-Fano码与Huffman码的编码效率一样好。而信源X的Shannon-Fano码的编码效率比其Huffman码的编码效率降低极少。这是因为信源Y在Shannon-Fano码编程过程中分两大组时“概率和”相差不多(为0.49与0.51)：而信源X在编码过程中每次分两组时，其“概率和”相差较远(第一次为0.57和0.43；第二次上面分组为0.2和0.37，下面分组为0.17和0.26)。算术码—Shannon-Fano-Elias码34数据压缩和信源编码3.1等长码3.2

变长编码3.3哈夫曼码3.4算术码3.5通用信源编码习题三香农-费诺码;香农-费诺-埃里斯码35编码理论（实例）以数字电视这一热门话题为例.

36数字电视的主要核心技术包括信源编码、信道编码和显示技术，它们分别解决数字电视节目在初始制作、中间传播和终端呈现三个主要环节上的问题。通俗地说就是满足了我们拍片子、播节目、看电视的需要。编码理论（实例）37信源编码技术解决的重点问题是数字音视频海量数据的编码压缩问题。众所周知，数字化视频的原始数据量是十分庞大的，例如，标准清晰度的数字视频每秒的数据量超过200M

bit，高清晰度数字电视每秒的数据量超过1G

bit。编码理论（实例）38信源编码技术解决的重点问题是数字音视频海量数据的编码压缩问题。高清晰度数字电视简称高清电视（HDTV）简单的说，是指图像水平清晰度大于720线、采用的是16:9显示方式的数字电视系统。从世界范围来看，目前高清电视主要包括1080i和720p这两种格式，两者图像的长宽比都是16：9，因此这符合人眼视觉的“黄金分割法则”。作为隔行扫描的1080i的分辨率则是1920×1080；720p是逐行扫描，分辨率为1280×720。

编码理论（实例）39数字音视频要在消费电子产品中得到应用，必须采用先进的压缩编码算法进行大幅度压缩。而反映压缩效率的压缩比也就成为数字电视乃至数字音视频产业的“基本指数”。编码理论（实例）40打个形象的比方，信源编码就好像制作压缩饼干的技术，如何将普通面粉制作成压缩饼干就是“编码”过程——挤掉冗余成分，只保留有效成分且体积（或所占用资源）尽可能小；而“译码”就是一个还原过程，将压缩饼干恢复到常态供给食用，并保证营养（或信息）损失尽可能少。

编码理论（实例）41MP3（MPEGAudioLayer）是一种以高保真为前提下实现的高效压缩技术。它采用了特殊的数据压缩算法对原先的音频信号进行处理，使数码音频文件的大小仅为原来的十几分之一，而音乐的质量却没有什么变化，几乎接近于CD唱盘的质量。一分钟的WAVE格式的文件有十几兆，而一分钟MP3格式的音频文件仅有一兆左右。编码理论（实例）42MP3技术使在较小的存储空间内，存储大量的音频数据成为可能：一张CD唱盘存储的音乐与一盒卡带差不多，若用MP3格式来存储，则可存上百首。播放MP3流行的软件有很多，最流行的播放器要算是WINAMP。我们自己也可以制作MP3。在超级解霸中提供了一个CD压缩工具，用它可以将CD音轨直接转换成MP3音乐。此外比如：WinPlay等。

编码理论（实例）43而信道就是信源的通路，信道编码就相当于压缩饼干的运输方式，用飞机、汽车、火车都可以将饼干从厂家运送到消费者手中，但选择何种运输方式就相当于采用哪种信道编码标准，目的地一致，但在成本和效率上会有各种差别。编码理论（实例）44由此可见，信源编码是数字电视的基础，离开了信源编码去谈信道编码就是无源之水、无本之木。编码理论（实例）45编码理论（实例）数字电视就是指从演播室到发射、传输、接收的所有环节都是使用数字电视信号或对该系统所有的信号传播都是通过由0、1数字串所构成的数字流来传播的，数字信号的传播速率是每秒19.39兆字节，如此大的数据流的传递保证了数字电视的高清晰度，克服了模拟电视的先天不足。同时还由于数字电视可以允许几种制式信号的同时存在，每个数字频道下又可分为几个子频道，从而既可以用一个大数据流--每秒19.39兆字节，也可将其分为几个分流：46编码理论（实例）例如4个，每个的速度就是每秒4.85兆字节，这样虽然图像的清晰度要大打折扣，却可大大增加信息的种类，满足不同的需求。例如在转播一场体育比赛时，观众需要高清晰度的图像，电视台就应采用每秒19.39兆字节的传播；而在进行新闻广播时，观众注意的是新闻内容而不是播音员的形象，所以没必要采用那么高的清晰度，这时只需每秒3兆字节的速度就可以了，剩下16.39兆字节可用来传输别的内容。47

以视频为例：视频能够压缩的根本原因在于视频数据具有较高的冗余度，压缩就是指冗余的消除，主要基于两种技术：统计学和心理视觉。编码理论（实例）48消除统计冗余的基本依据是视频数字化过程在时间和空间上采用了规则的采样过程。视频画面数字化为规则的像素阵列，其密集程度适于表征每点最高的空间频率，而绝大多数画面帧包含非常少甚至不含这种最高频率的细节。同样，所选的帧频能够表征场景中最快的运动，而理想的压缩系统只要描述场景所必需的瞬时运动即可。编码理论（实例）49简言之，理想的压缩系统能够动态适应视频在时间和空间上的变化，所需要的数据量远低于数字化采样所产生的原始数据。编码理论（实例）50

压缩效果的评价标准有主观评价和客观评价两种，各有优缺点。主观评判是聘请专门的评价人员来比较压缩之后再恢复的视听效果和原始效果的差异，通常是在专门的视听环境中按照一定的规则进行主观评分。客观评判则是通过一种具体的算法来统计多媒体数据压缩结果的损失，例如信噪比SNR（即信号与噪声之比的对数）。编码理论（实例）51主观评判和客观评判有时相差很大，因此衡量一个算法的好坏就需要在这二者之间找到一个平衡点。对一套标准的评价，通常开发过程中采用客观评价的方法，但最终要得到主观评价的确认。

编码理论（实例）52数据压缩和信源编码3.1等长码3.2

变长编码3.3哈夫曼码3.4算术码香农-费诺码3.5通用信源编码

LZW算法习题三53对于统计特性已知的平稳信源，有Huffman码和算术码等高效编码方法.但是，它们存在以下共同问题：①在编码时必须知道信源的概率分布，这在许多情况下是不可能的；②它们对无记忆信源较为合适，而实际应用中的信源一般都具有记忆性；因此如何利用信源的记忆性提高它的压缩率是信源编码所必需考虑的问题.

通用信源编码541通用码的一般理论通用编码是指在信源概率分布不知时，对其编码并使编码效率很高的一种码.基本原理：利用出现数据序列前后的相关性进行压缩.

通用信源编码55常用的通用码：LZ码及其改进算法—LZW码.LZ码是1977-1978年以色列研究人员J.Ziv&A.Lempel提出的，是一种基于字典的编码方法.1984年，T.A.Welch给出了LZ算法的实用修正形式，成为LZW算法.通用信源编码56LZ码的基本算法：将长度不同的符号串编成一个个新的短语(单词)，形成短语词典的索引表；它是一种分段编码，其短语词典是由前面已见到的文本分段来定义的.通用信源编码57LZ码的编码步骤：①取第一个符号x作为第一段（单词），记为（0，x）；②从第二个符号y起，分段时先查看是否与前面的短语相同（匹配）：若没有匹配的，记为（0，y）；若有匹配的符号，就找从该符号开始与之匹配的最大长度L，并使得匹配开始的距离ρ最近，记为（1，L,ρ）；

通用信源编码匹配时长度优先考虑，距离次之！58例1

设x11=a0a0a2a3a1a1a0a0a0a3a2，求它的LZ码.解：对x1的LZ码为（0，a0）；对x2的LZ码为（1，1，1）;对x3的LZ码为（0，a2）；对x4的LZ码为（0，a3）;对x5的LZ码为（0，a1）；对x6的LZ码为（1，1，1）;对x7的LZ码为（1,2,6）；对x8不编码；对x9的LZ码为（1，1，1）;对x10的LZ码为（1，1，6）;对x11的LZ码为（1，1，8）;

通用信源编码因此，它的LZ码为C={(0,a0),(1,1,1),……}59例1

设x11=a0a0a2a3a1a1a0a0a0a3a2，求它的LZ码.译码：①由（0，a0）得到x1=a0,xn=a0；②由（1，1，1）得到x2=a0,xn=a0a0……

通用信源编码因为，它的LZ码为C={(0,a0),(1,1,1),……}60常用的通用码：LZ码及其改进算法—LZW码.LZ码是1977-1978年以色列研究人员J.Ziv&A.Lempel提出的，是一种基于字典的编码方法.1984年，T.A.Welch给出了LZ算法的实用修正形式，成为LZW算法.

LZW就是通过建立一个字符串表,用较短的代码来表示较长的字符串来实现压缩.LZW压缩算法是Unisys的专利,有效期到2003年.通用信源编码61LZW算法保留了LZ的自适应性能，压缩效率大致相同；成为计算机文件压缩的标准算法，已经实现成为Unix操作系统中的标准文件压缩程序和arc文件压缩程序.可将典型的ASCII文本文件压缩成原文件的一半，得到广泛的应用.通用信源编码手机存储备份,是ARC文件

62LZW压缩有三个重要的对象：数据流(CharStream)、编码流(CodeStream)和编译表(String

Table)。在编码时，数据流是输入对象（文本文件的数据序列），编码流就是输出对象（经过压缩运算的编码数据）；在解码时，编码流则是输入对象，数据流是输出对象；而编译表是在编码和解码时都须要用借助的对象。.通用信源编码63

LZW压缩算法的基本原理：提取原始文本文件数据中的不同字符，基于这些字符创建一个编译表，然后用编译表中的字符的索引来替代原始文本文件数据中的相应字符，减少原始数据大小。看起来和调色板图象的实现原理差不多，但是应该注意到的是，我们这里的编译表不是事先创建好的，而是根据原始文件数据动态创建的，解码时还要从已编码的数据中还原出原来的编译表.

通用信源编码64

LZW算法流程：

1)初始化：将所有的单字符串放入串表；

2)读第一个输入字符给前缀串ω

3)Step:读下一个输入字符K;

if没有这样的K(输入已穷尽)：

码字(ω)输出；结束。

通用信源编码IfωK已存在于串表中：

ωK:=ω；repeatStep；

elseωK不在于串表中:

码字(ω)输出；

ωK加进串表；K:=ω；repeatStep.

65

例子：ababcbababaaaaaaa

LZW编码：a,b,c,ab,ba,abc,cb,bab,baba,aa,aaa,aaaa

通用信源编码66LZW码的编码步骤：①取第一个符号x作为第一段（单词），记为（0，x）；②从第二个符号y起，分段时先查看是否与前面的短语相同（匹配）：若没有匹配的，记为（0，y）；若有匹配的符号，并与第l个码字相同，就再取紧跟后面的一个符号z一起组成一个短语，以便与前面的短语不同，记为（l，z

）；

通用信源编码67例2

设x11=a0a0a2a3a1a1a0a0a0a3a2，求它的LZW码.解：对x1的LZW码为（0，a0）；对x2的LZW码为（1，a2）;对x3不编码；对x4的LZW码为（0，a3）;对x5的LZW码为（0，a1）；对x6的LZW码为（4，a0）;对x7不编码；对x8的LZW码为（1，a0）

；对x9不编码;对x10的LZ码为（3，a2）;对x11不编码;

通用信源编码因此，它的LZ码为C={(0,a0),(1,a2),……}68

LZW压缩的特点

LZW码能有效利用字符出现频率冗余度进行压缩，且字典是自适应生成的，但通常不能有效地利用位置冗余度。

具体特点如下：l)LZW压缩技术对于可预测性不大的数据具有较好的处理效果，常用于GIF格式的图像压缩，其平均压缩比在2:1以上，最高压缩比可达到3:1。通用信源编码69

2)对于数据流中连续重复出现的字节和字串，LZW压缩技术具有很高的压缩比。

3)除了用于图像数据处理以外，LZW压缩技术还被用于文本程序等数据压缩领域。

4)LZW压缩技术有很多变体，例如常见的ARC、PKZIP高效压缩程序。

5)对于任意宽度和像素位长度的图像，都具有稳定的压缩过程。压缩和解压缩速度较快。

6)对机器硬件条件要求不高。

通用信源编码70习题若

试构造它的LZW数据压缩编码.通用信源编码71

通用信源编码72数据压缩和信源编码3.1等长码3.2

变长编码3.3哈夫曼码3.4算术码

香农-费诺码3.5通用信源编码

LZW算法习题三731）(a)解：由长度满足Kraft不等式，可知利用该数集可以构造二进即时码.编码方法：任意选取长为1的码字：0；……习题课743）证明：最短码字“101”不是其他码的前缀；依次考查，码C3是C6的前缀，有可得，尾随后缀集合为{0，011，0001，10100}；由于该集合中没有码字，所以是唯一可译码.习题课755）提示：（a）进行哈