9.2.1编码的理论基础

通用的数据压缩技术：行程编码、字典编码、熵编码等无损压缩技术，

以及PCM、DM、DPCM等有损压缩技术。

通用的压缩方法具有压缩比低、通用性强等特点 ，是其他压缩方法建立的基础。

数据压缩技术的理论基础是信息论。

根据信息论的原理，可以找到最佳数据压缩编码方法，数据压缩的理论极限是信息熵。

熵是信息量的度量方法，它表示某一事件出现的消息越多，事件发生的可能性就越小，数学上就是概率越小。 

1.信息与信息量

信息量是指信源中某种事件的信息度量或含量。一个事件出现的可能性愈小，其信息量愈多，反之亦然。

若pi为第i个事件的概率为0≤ pi ≤1，则该事件的信息量为

     设从N个数中选定任一个数xj的概率为p（xj），假定选定任意一个数的概率都相等，

      即p（xj）＝  ，则                                         

        I(xj)＝log  N＝-log     ＝-log  p(xj)=I[p(xj)]     

一个信源包括的所有数据叫数据量，而数据量中包含有冗余信息。冗余量的存在是数据压缩的主要依据之一。因此信源携带的信息量与数据量之间的关系表示为：信息量 = 数据量-冗余量 

2.信息熵

信息熵就是将信源所有可能事件的信息量的平均。 

设从N个数中选定任一个数xj的概率为p(xj)，假定选定任意一个数的概率都相等，即p(xj) ＝1/N，则

     I(xj)＝log2N＝-log2 1/N ＝-log2p(xj)=I[p(xj)] 

  上式中，p(xj)是信源X发出xj的概率。I(xj)的含义是信源X发出xj这个消息（随机事件）后，接收端收到信息量的量度。 

信源X发出的xj(j=1,2,…,n)共n个随机事件的信息量的统计平均，即

H(X)=E{I(xj)}=

   H(X)称为信源X的“熵”，即信源X发出任意一个随机变量的平均信息量。

其中，等概率事件的熵最大，假设有N个事件，此时熵为：

H(X)＝                                 ＝

当P(x1)＝1时，P(x2)＝P(x3)＝…＝P(xj)＝0，此时熵为

             H(X)＝－ P(x1)              ＝0

由上可得熵的范围为：

       0≤ H(X) ≤ 

在编码中用熵值来衡量是否为最佳编码。若以Lc表示编码器输出码字的平均码长，其计算公式为：

         Lc＝                           （j=1,2,…,n）

其中：P(xj) 是信源X发出xj的概率，L(xj)为xj的编码长。

平均码长与信息熵之间的关系为：

Lc≥H(X)    有冗余，不是最佳。

Lc＜H(X)    不可能。

Lc＝H(X)    最佳编码（Lc稍大于H(X)）。

熵值为平均码长Lc的下限。

9.2.2无损编码方法

1.霍夫曼编码

霍夫曼编码（Huffman）是运用信息熵原理的一种无损编码方法，这种编码方法根据源数据各信号发生的概率进行编码。

在源数据中出现概率大的信号，分配的码字越短；出现概率越小的信号，其码字越长，从而达到用尽可能少的码表示源数据。   

1.1霍夫曼编码的算法

（1）.初始化，根据符号概率的大小顺序对符号进行排序。

（2）.把概率最小的两个符号组成一个新符号（节点），即新符号的概率等于这两个符号概率之和。

（3）.重复第2步，直到形成一个符号为止（树），其概率和等于1。

（4）.分配码字。码字分配从最后一步开始反向进行，即从最后两个概率开始逐渐向前进行编码，对于每次相加的两个概率，给概率大的赋“0”，概率小的赋“1”（也可以全部相反，如果两个概率相等，则从中任选一个赋“0”，另一个赋“1”）。 

1.2 霍夫曼编码的特点

霍夫曼编码构造出来的编码值不是唯一的。

对不同信号源的编码效率不同

由于编码长度可变，因此译码时间较长；编码长度的不统一，也使得硬件实现有难度。

2.行程编码

行程编码又称行程长度编码（Run Length Encoding，RLE），是一种熵编码。这种编码方法广泛地应用于各种图像格式的数据压缩处理中。

行程编码的原理是在给定的图像数据中寻找连续重复的数值，然后用两个字符取代这些连续值。即将具有相同值的连续串用其串长和一个代表值来代替，该连续串就称为行程，串长称为行程长度。

如图所示，假定一幅灰度图像，第n行的像素值为： 

用RLE编码方法得到的代码为：4160831130。代码斜黑体表示的数字是行程长度，黑体字后面的数字代表像素的颜色值。例如黑体字60代表有连续60个像素具有相同的颜色值，它的颜色值是8。

对比RLE编码前后的代码数可以发现，在编码前要用80个代码表示这一行的数据，而编码后只要用10个代码表示代表原来的80个代码，压缩前后的数据量之比约为8:1，即压缩比为8:1。

2.1 行程编码的分类

定长编码

定长编码是指编码的行程长度所用的二进制位数固定 

不定长编码

变长行程编码是指对不同范围的行程长度使用不同位数的二进制位数进行编码。使用变长行程编码需要增加标志位来表明所使用的二进制位数。 

3.词典编码

词典编码（dictionary encoding）技术属于无损压缩技术，主要是利用数据本身包含许多重复的字符串的特性。可以用一些简单的代号代替这些字符串，就可以实现压缩，实际上就是利用了信源符号之间的相关性。字符串与代号的对应表就是词典。词典编码法的种类有很多，归纳起来大致有两种。

第一种方法的思想是查找目前正在压缩的字符序列在以前输入的数据中是否出现过，然后用出现过的字符串代替重复的部分，它的输出仅仅是指向早期出现过的字符串“指针”。

这种编码的概念如右图所示。这里所指的词典是指用以前处理过的数据表示编码过程中遇到的重复部分。这类编码的所有算法都是以LZ77算法为基础的。 

第二种算法的思想是从输入的数据中创建一个“短语词典”，这类短语不一定有具体的含义，可以是任意字符的组合。在编码过程中遇到在“短语词典”中出现的短语是，编码器就输出这个词典中的短语“索引号”，而不是短语本身。其概念如右图所示。

3.1词典编码-LZ77算法

LZ77是以以色列计算机专家Abraham Lempel和Jakob Ziv在1977年开发和发表的。

此算法的一个改进算法是由Storer和Szymanski在1982年开发的，称为LZSS算法。

LZ77 算法在某种意义上又可以称为“滑动窗口压缩”，该算法将一个虚拟的、可以跟随压缩进程滑动的窗口作为词典，要压缩的字符串如果在该窗口中出现，则输出其出现位置和长度。

3.1.1词典编码-LZ77算法中的概念

输入字符流(input stream)：要被压缩的字符序列。 

字符(character)：输入数据流中的基本单元。 

编码位置(coding position)：输入数据流中当前要编码的字符位置，指前向缓冲存储器中的开始字符。 

前向缓冲存储器(Lookahead buffer)：存放从编码位置到输入数据流结束的字符序列的存储器。 

窗口(window)：指包含W个字符的窗口，字符是从编码位置开始向后数也就是最后处理的字符数。 

指针(pointer)：指向窗口中的匹配串且含长度的指针。

3.1.2词典编码-LZ77算法步骤

把编码位置设置到输入数据流的开始位置。

找窗口中最长的匹配串

以“(Pointer, Length) Characters”的格式输出，其中Pointer是指向窗口中匹配串的指针，Length表示匹配字符的长度，Characters是前向缓冲存储器中的不匹配的第1个符。 

如果前向缓冲存储器不是空的，则把编码位置和窗口向前移(Length+1)个字符，然后返回到步骤（2）。

3.2词典编码-LZW算法

LZW压缩算法是一种新颖的压缩方法，它采用了一种先进的串表压缩，将每个第一次出现的串放在一个串表中，用一个数字来表示串，压缩文件只存贮数字，则不存贮串，从而使图像文件的压缩效率得到较大的提高。

LZW编码是围绕称为词典的转换表来完成的。

3.2.1词典编码-LZW相关概念

前缀(Prefix)： 在一个字符之前的字符序列。 

缀-符串(String)：前缀＋字符。 

码字(Code word)：码字流中的基本数据单元，代表词典中的一串字符。 

码字流(Codestream)： 码字和字符组成的序列，是编码器的输出。 

词典(Dictionary)： 缀-符串表。按照词典中的索引号对每条缀-符串(String)指定一个码字(Code word)。 

当前前缀(Current prefix)：在编码算法中使用，指当前正在处理的前缀，用符号P表示。 

当前字符(Current character)：在编码算法中使用，指当前前缀之后的字符，用符号C表示。 

当前码字(Current code word)： 在译码算法中使用，指当前处理的码字，用W表示当前码字，String.W表示当前码字的缀-符串。

3.2.2词典编码-LZW算法执行步骤

开始时的词典包含所有可能的根(Root)，而当前前缀P是空的；

当前字符(C) ：=字符流中的下一个字符；

判断缀-符串P+C是否在词典中

如果“是”：P ：= P+C // (用C扩展P) ；

如果“否”：① 把代表当前前缀P的码字输出到码字流；② 把缀-符串P+C添加到词典；③ 令P ：= C //(现在的P仅包含一个字符C)；

判断字符流中是否还有字符要编码

如果“是”，就返回到步骤2；

如果“否”：① 把代表当前前缀P的码字输出到码字流；② 结束。

9.2.3有损编码方法

1.脉冲编码调制

脉冲编码调制 (Pulse Code Modulation, PCM)就是将模拟调制信号的采样值变换为脉冲码组。 

PCM编码包括如下三个过程： 

采样，将模拟信号转换为时间离散的样本脉冲序列。 

量化，将离散时间连续幅度的抽样信号转换成为离散时间离散幅度的数字信号。

编码，用一定位数的脉冲码组表示量化采样值。

PCM方式是由采样，量化和编码三个基本环节完成的。音频信号经低通滤波器滤波后，经过采样、量化和编码三个环节完成PCM编码。编码后的音频信号再经过纠错编码和调制后，录制在记录媒介上。数字音响的记录媒介有激光唱片和盒式磁带等。放音时，从记录媒介上取出的数字信号经解调，纠错等处理后，恢复为PCM数字信号，由D/A变换器和低通滤波器还原成模拟音频信号。

PCM编码的优点：

有很强的抗干扰性

能方便的利用计算机编程，实现各种智能化设计。

2. 增量调制（DM）

增量调制也称△调制(delta modulation，DM)，它是一种预测编码技术，是PCM编码的一种变形。

DM是对实际的采样信号与预测的采样信号之差的极性进行编码，将极性变成“0”和“1”这两种可能的取值之一。如果实际的采样信号与预测的采样信号之差的极性为“正”，则用“1”表示；相反则用“0”表示，或者相反。

2. 增量调制（DM）-DM波形编码的原理 

在开始阶段增量调制器的输出不能保持跟踪输入信号的快速变化，这种现象就称为增量调制器的“斜率过载” 。

在输入信号缓慢变化部分，即输入信号与预测信号的差值接近零的区域，增量调制器的输出出现随机交变的“0”和“1”。这种现象称为增量调制器的粒状噪声 

3.差分脉冲编码调制

差分脉冲编码调制（Differential Pulse Code Modulation，DPCM）是利用样本与样本之间存在的信息冗余度来进行编码的一种数据压缩技术。

差值脉冲编码调制是利用信号的相关性找出可以反映信号变化特征的一个差值量进行编码。

3.差分脉冲编码调制-工作原理

根据过去的样本去估算（estimate）下一个样本信号的幅度大小，这个值称为预测值，然后对实际信号值与预测值之差进行量化编码，从而就减少了表示每个样本信号的位数。

它与脉冲编码调制（PCM）不同处在于，PCM是直接对采样信号进行量化编码，而DPCM是对实际信号值与预测值之差进行量化编码。

差分信号d(k)是离散输入信号S(k)和预测器输出的估算值Se(k-1)之差。注意，Se(k-1)是对S(k)的预测值，而不是过去样本的实际值。DPCM系统实际上就是对这个差值D(k)进行量化编码，用来补偿过去编码中产生的量化误差。DPCM系统是一个负反馈系统，采用这种结构可以避免量化误差的积累。重构信号Sy{k}是由逆量化器产生的量化差分信号dq(k)，与对过去样本信号的估算值Se(k-1)求和得到。它们的和，即Sy(k)作为预测器确定下一个信号估算值的输入信号。由于在发送端和接收端都使用相同的逆量化器和预测器，所以接收端的重构信号Sy(k)可从传送信号I(k)获得。