无损压缩编码（上）| 学习笔记

开发者学堂课程【高校精品课-华中科技大学 -智能媒体计算：无损压缩编码（上）】学习笔记，与课程紧密联系，让用户快速学习知识。

课程地址：https://developer.aliyun.com/learning/course/811/detail/15681

无损压缩编码（上）

内容介绍

一、统计编码的理论基础

二、熵编码

一、统计编码的理论基础

统计编码的理论基础是信息论，信息论的创始人是香农。理论基础是信息论，理论依据是变子长编码理论，变子长即有的用长字长，有的用短字长。

编码器设计的核心思想是解决什么时候用长字长或短字长的问题。换言之，编码器的编码输出码字是字长不等的码字，按照编码输入信息符号出现的统计概率，给输出码字分配以不同的字长。在分配方面，大概率的信息符号赋以短字长的输出码字，小概率的信息符号赋以长字长的输出码字。为了压缩数据，数据量会变少，经常出现的变短才能将数据减少，所以大概率的信息符号不赋以长字长的输出码字，小概率的信息符号不赋以短字长的输出码字。变子长编码理论就是概率越高，码字就越短，概率越小，码字就越长。

根据信息论的原理，可以找到最佳数据压缩编码方法，数据压缩的理论极限是信息熵，并不是随意压缩，所以信息理论很重要。

二、熵编码

1.信息熵

如果要求编码过程中不丢失信息量，即要求保存信息熵；同时这种信息保持编码又叫做熵编码。因此我们的统计编码是无损压缩的，因为他规定的最小码字要比信息熵要长，那么这样的会把信息熵保留，原始的信息量都在编码里。

2.熵(Entropy)的概念

熵是信息量的度量方法，这表示某一个事件包含的信息量越多，事件发生的概率就越小；相反事件发生的概率越小，信息量就越大，例如爆炸性的新闻。

举例说明：在若干年前杨振宁先生娶了翁帆，各大媒体争相报道，因为当年杨老先生82岁，而翁女士28岁，两人年龄差距太大，因为概率太小，所以很多人关注；而每天有很多恋人结婚像25岁嫁给26岁，28岁嫁给29岁，这种大概率的事件信息量小关注人少。这就是熵的意义。

3.计算熵

某个事件的信息量用I_I= -log₂p_i表示，其中用p为第i个事件的概率。此公式可以变换一下，将负号移动。按照香农( Shannon )的理论，信源s的熵定义为: .

p_i和本身第i事件的信息量相乘的累加和即为熵，这个p_i是信源符号s_i在大集合中出现的概率，i_i表示信息量，两者相乘的累加和为熵。熵表示信源编码的长度，如果最后编码的长度比 s 小，则没有把熵保存，信息就有所损失。最终的编码是否正确跟H比，比H 小，编码出现错误。因为熵编码一定不会比H小，如果大于H，则是无损的，小于H，信息就有损失。

例如：一幅用256级灰度表示的图像,如果每一个像素点灰度的概率均为p_i=1/256 ,编码每一个像素点就需要多少位?

解答：因为每一位出现的概率相等，一个像素出现一回。

I_I=-log₂p_i

p_i=1/256，则1/p_i=256；

而256=2^8,

log2⁸=8，所以需要8位.

所有的信源符号都是相同概率出现的，这个是不可能压缩的。

再有例题2：有一幅40个像素组成的灰度图像，40个像素中灰度共有5级,分别用符号A. B、C. D 和E 表示，140个像素中出现灰度A的像素数有15个,出现灰度B的像素数有7个，出现灰度C的像素数有7个等等，概率不相等。

如果用3位表示5个等级的灰度值，因为是5级灰度，要把5级表示成5个等级。2²=4,2³=8，选用2位不能表示5级，选用3位表示8级是足够的，也就是每个像素用3位表示；如果按照相同码字，应为3*40=120，所以有编码这幅图像总共需要120位。

则有问题：最少需要多少位？

因为概率不相同，按照信息论的基础，以及熵的算法来求看最少需要多少位，如下表：

按照统计值，A 出现15次，概率为15/40，即0.375；以此类推求出E。因为熵编码是统计编码，统计编码需要计算概率；算完以后按照熵的概念继续计算，

有H(S)=（15/40）×log₂（40/15）+（7/40）×log₂（40/7）+...+（5/40）×log₂（40/5）

=2.196

最后得到熵为2.196位，这指平均码长，即最小的码长，就是每一个最少分配2.196位，如果小于2.196位，则不能保留熵。换言之，每个符号用2.196位表示, 40个像素需用87.84位。