预测编码

预测编码的历史相当之久。最早可以追溯到40年代提出的Delta编码(Delta modulation)，乃至于到今日我们都还可以常常在学术性期刊上看到线性预测编码的论文。一个领域研究了五十多年还继续有新的结果不断的出现，一方面很少见，另一方面也足见有其重要性了。

预测编码是属于时间领域的编码法。他的基本理念是(有几分马可夫过程的味道)利用前面已经出现了的符号来预测目前的符号，然后将实际上的符号与预测符号得到预测误差，将此误差编码并送出。预测误差的编码法可以采用无失真资料压缩法或失真资料压缩法。若采用前者，则整个系统仍然是无失真资料压缩法；反之，若采用后者，则整个系统就成了失真资料压缩法。因此预测编码既是属于无失真资料压缩法，也是属于失真资料压缩法。

使用预测编码的动机是误差讯号的变化要比原讯号的变化小许多，因此我们可以使用比较少的位元来为每一个误差讯号的取样做编码以达到资料压缩的目的。

本条目将介绍两个著名的技术：

Delta编码与误差讯号编码(differential pulse code modulation)。两种技术都各有适应性与非适应性两种方法。

Delta编码(DM)

Delta编码(Delta modulation)是预测编码中最简单的一种，它使用前一个取样值来预测目前的取样值并且将预测值与实际值之误差量化成只有两阶。如果这个误差值为正，则加$\Delta$，如果是负的，则减$\Delta$。Delta编码的一个重要特色是它只允许$\Delta$与$-\Delta$两个量化阶，因此可以用一个位元来表示。也就是因为如此，他有时也被称为单位原(1-bit)系统。

传统式的Delta编码

Delta编码器由三个部分组成：减法器、二阶量化器及积分器。整个Delta编码器的输出决定于输入之取样值与由积分器所预测之取样值，这两个值的差；如果这个差值为正则系统送出正脉冲(pulse)，若为负则送出负脉冲。整个系统不需要任何的缓冲区(buffer)，他持续的送出正脉冲：代表$\Delta$，或负脉冲：代表$-\Delta$，因此系统的输出与原讯号同步，没有延迟。有些系统会希望他的压缩系统能做到这一步。

解码端其实只需要一个积分器即可。累加编码端所送出的正负脉冲，即$(\pm \Delta )$就可得到解码讯号。 有时重建讯号之波行会赶不上原讯号波形，这是Delta编码的一个先天限制，我们称之为斜率超负载(slope overload)。构成斜率超负载的原因是因为Delta编码所能产生出的最大斜率为： 最大斜率$=(\pm \Delta )\times$(取样频率) 而此最大斜率小于原讯号波形之斜率所致。

适应性Delta编码(ADM)

由于传统式的Delta编码会有增加粒状杂讯的缺点。折衷办法便是选择SNR最大时的$\Delta$值。但是这无法满足大部分的要求，预期使该系统具备适应性。

适应性的Delta编码法的种类虽然很多，大部分都有一个共同的特性：监视员讯号斜率的变化情形以调整$\Delta$值的大小。斜率的监测则是借由监视连续脉冲的来完成。如果接连出现的脉冲都是正的(或者都是负的)，那么很有可能这一段波形的斜率相当大(或者很大的负斜率)。这个时候就应该考虑改变$\Delta$值(加大)值到负(正)的脉冲出现为止。

Song所提出的方法提出。Delta编码器的输出为+1及-1，每当输出值没改变则增加$\Delta$值50%，反之，如果改变则减少50%。利用这种方法便可以同时降低斜率超负载时，$\Delta$的值会逐渐地以50%的速度加大以赶上输入讯号；反之，如果发生超出原讯号或者脉冲改变正负号时，$\Delta$的值便以50%的速度逐渐减小以降低粒状杂讯。另$E_{k+1}$表示输出之脉冲值$(+1,-1)$，$S_{k+1}$为目前的输入值，$X_{k+1}$为预测值，$\Delta _{m}in$，为所允许之最小$\Delta$值，则$\Delta _{k}+1$的值可以表示如下：

                              $E_{k+1}=[S_{k+1}-X_{k}]$之正負號

                              $\Delta _{k+1}={\begin{cases}|\Delta _{k}|[E_{k+1}+{\frac {1}{2}}E_{k}],if|\Delta _{k}|\geq \Delta _{min}\\\Delta _{min}E_{k+1},if|\Delta _{k}|<\Delta _{min}\end{cases}}$

误差讯号编码(DPCM)

误差讯号编码(differential pulse code modulation)，以下简称(DPCM)是预测编码中最常使用的一种。在DPCM里，实际之取样值与预测值相减得一误差值，此误差值在经过量化与编码后送出。和Delta编码不同的是，DPCM使用较精确的预测器而且他的输出也不再是只有两种值。DPCM的压缩效能主要决定于预测器与量化器设计优劣。

在DPCM中，$m$个刚读过的取样(如果是影像，这m个像素通常指的是目前像素的邻居)透过一个线性预测函数得到一个目前这个取样的预测值，即

                              ${\hat {x}}_{m}=\sum _{i=0}^{m-1}\alpha _{i}x_{i}$

其中${\hat {x}}_{m}$为预测所得的目前取样值，$x_{0}$、$x_{1}$、$x_{2}$、……、$x_{m-1}$维刚读过的前$m$个取样，$\alpha _{0}$、$\alpha _{1}$、$\alpha _{2}$、……、$\alpha _{m-1}$则为此线性预测函数之系数(加权值)。误差讯号$e_{m}$则定义为实际取样值与预测值之差；即

                              $e_{m}=x_{m}-{\hat {x}}_{m}$

和原讯号相比，误差讯号的特色是：它的变化比较小，取样间累赘也比较小。失真与无失真DPCM的主要差别就在于误差讯号的处理方式。如果我们采用无失真资料压缩法来编码误差讯号，即为无失真DPCM；反之，就像大部分情形一样，DPCM为了达到更低的位元率。会更进一步的将误差讯号量化在做传送。

预测器之最佳化

预测器内的系数，α_i，可以是事先设计好供所有的同类讯号(也就是所有的影像)使用，也可以是针对每一笔资料各自设计一组系数，甚至于同一笔资料内的系数可以随时时间改变。和马可夫过程类似，我们定义被用来预测目前取样值的前面刚读过的取样点之数目为DPCM之阶次(order)。一般来说，高阶次的DPCM系统之表现会优于低阶次的DPCM系统。然而，当阶次高过某一个值以后，提高阶次的收益将很有限／譬如说，研究显示超过三阶以上的电视画面及X-光片影像之DPCM系统顶多只能多得到及小的收益，而类似的，超过二阶以上的心电图讯号之DPCM系统也只能多得到极小的收益。

以下为一笔资料预测器系数的最佳化问题。如前所述，将MSE最小化是很普遍的被接受的标准，因此我们的设计也是以令MSE最小为目标。在这个标准下，$x_{m}$的最佳线性预测值${\hat {x}}_{m}$必须要能够使误差的平方之期望值为最小；也就是说，他必须使下列的式子最小化：

                              ${\sigma _{e}}^{2}=E{(x_{m}-\sum _{i=0}^{m-1}\alpha _{i}x_{i})^{2}}=E{(x_{m}-{\hat {x}}_{m})^{2}}$

要找${\sigma _{e}}^{2}$到的最小值，我们计算偏微分并且令其为零：

                              ${\frac {{\sigma }E{(x_{m}-{\hat {x}}_{m})^{2}}}{\sigma \alpha _{i}}}={\frac {{\sigma }E{[x_{m}-(a_{0}x_{0}+a_{1}x_{1}+\ldots +a_{m-1}x_{m-1})]^{2}}}{\sigma \alpha _{i}}}=-2E[(x_{m}-{\hat {x}}_{m})x_{i}]=0\ldots \ldots \ldots \ldots \ldots (a)$式

定义

                              $R_{ij}=E(x_{i}x_{j})$

为相关联值(autocorrelation)，则由(a)式得知

                              $E[x_{m}x_{i}]=E[{{\hat {x}}_{m}}x_{i}]$

                              $R_{mi}=E[a_{0}x_{0}x_{i}+a_{1}x_{1}x_{i}+\ldots +a_{m-1}x_{m-1}x_{i}]=a_{0}R_{0i}+a_{1}R_{1i}+\ldots +a_{m-1}R_{(m-1)i}\ldots \ldots \ldots \ldots \ldots (b)$式

                              其中$i=0,1,\ldots ,{m-1}$

这是一组$m$个变数的联立方程式，只要解了这组联立方程式便可以求得最佳化之$\alpha _{0}$、$\alpha _{1}$、$\alpha _{2}$、$\ldots \ldots$、$\alpha _{m-1}$值。如果预测$x_{m}$值的线性预测器是使用的是这些最佳化的$\alpha _{i}$，则MSE为

                              ${\sigma _{e}}^{2}=E{(x_{m}-{\hat {x}}_{m})^{2}}=E{(x_{m}-{\hat {x}}_{m})x_{m}}-{(x_{m}-{\hat {x}}_{m}){\hat {x}}}$

                              但是從(a)式知道${(x_{m}-{\hat {x}}_{m}){\hat {x}}}=0$；於是

                              ${\sigma _{e}}^{2}=E{(x_{m}-{\hat {x}}_{m})x_{m}}=E[(x_{m})^{2}]-E[{\hat {x}}_{m}x_{m}]=R_{mm}-(\alpha _{0}R_{0m}+\alpha _{1}R_{1m}\ldots \ldots \ldots \ldots \ldots (c)$式

如果我们将${\sigma _{e}}^{2}$视为误差讯号之方差而将$R_{mm}$视为原讯号之方差，那么很显然的误差讯号的方差比原讯号的方差小。(c)式给了我们这个结果也等于为DPCM的使用提供了一个很有力的证明。

而由(b)式我们可以知道预测器的复杂度决定于$m$的大小。若$m=1$，即只使用前一个取样值来预测目前的取样值，则这种最简单的预测器其系数应该是：

                              $\alpha _{0}={\frac {R_{10}}{R_{00}}}={\frac {R_{10}}{{\sigma }^{2}}}$

换句话说，我们的预测器应该设为

                              ${\hat {x}}_{1}={\frac {R_{10}}{{\sigma }^{2}}}x_{0}$

预测器之最佳化

使用DPCM技术能做到资料压缩的部分原因是：误差讯号会再经过量化。量化器之设计可以是以统计标准或者视觉标准为基础。虽然之前已经有许多以视觉标准为基础的量化器设计，但是只要我们想到人类视觉系统(HVS)的复杂度，就不难了解何以用这种方法至今仍然充满著争议：什么是最好的HVS?如何验证?以下的讨论，因此还是在统计标准的基础上寻求最佳化的量化器设计。

量化器基本上是一个将许多输入值(也许是无穷多个)对应到比较少而且有限输出值的阶梯函数，我们值得探讨Lloya-Max量化器，因为除了DPCM外在其他地方他也用的到。他整个推导式子的过程是将下列的式子最小化：

                              $D=\sum _{i=0}^{N-1}\int _{d_{i}}^{d_{i+1}}{(e-r_{i})}^{2}p(e)\,\mathrm {d} e$

其中$d_{i}$及$r_{i}$之定义如前。他所得的解为：

                              $d_{i}={\frac {r_{i-1}+r_{i}}{2}}\ldots \ldots \ldots \ldots \ldots (d)$式

                              $r_{i}={\frac {\int _{d_{i}}^{d_{i+1}}ep(e)\,\mathrm {d} e}{\int _{d_{i}}^{d_{i+1}}p(e)\,\mathrm {d} e}}\ldots \ldots \ldots \ldots \ldots (e)$式

一般而言，(d)与(e)必须藉茱萸数值方法来求解。在某些特殊情况下，例如Laplacian机率分布，我们可以直接求得其解。一般的情况下，我们可以利用下面的数值方法来求得

第一步：随意设定$d_{i}$的起始值，其中$d_{0}<d_{1}<\ldots <d_{n}$
第二步：根据目前之$d_{i}$值使用(e)式求得新的$r_{i}$
第三步：根据目前之$r_{i}$值使用(d)式求得新的$d_{i}$
第四步：所求得之新的$d_{i}$、$r_{i}$值如果与前一次求得之值相差很小，则$d_{i}$、$r_{i}$即为所求；否则回到第二步

在大部分得情况下，$d_{i}$及$r_{i}$的值会很快的收敛，因此演算法可以在几次轮回后即跳出。

适应性DPCM(ADPCM)

DPCM的最大限制便是他的预测器及量化器都是固定的。可以让他具备适应性：或者在预测器、或者在量化器、或者两者都加上适应性。适应性预测器通常都可以降低预测误差。较低的预测误差输入到量化器内，在相同的位元率下，其量化误差也会比较小，因此重建讯号品质会较高。另一方面，适应性量化可以借由统计的方式机动的改变$d_{i}$与$r_{i}$值而直接降低量化误差。

适应性预测

非适应性的预测器通常在讯号产生突然的变化时会有很差的表现，例如影像的边。我们可以针对不同方向的边各设计一组预测器系数。采用一些常用的经验法则去判断边的方向，然后根据边的方向选组一组预测器。

另一个方法是在预测器的输出再乘以一个适应性系数。适应性系数k的值决定于前一个量化器的重建值。如果前一个重建值是一个最大的正数，那么有很大的可能性会是斜率超负载的情况，因此我们可以选择k大于1以加快重建讯号的脚步。且这方法也可以改善整个系统的品质。

虽然以上两个方法都能重现讯号之品质有所改善，一般大家所常用的还是固定的预测器加上一个适应性量化器。

适应性量化

为了配合DPCM回圈内之量化器具备适应性，已经有许多方法可用，如下所示：

误差讯号常态化：由于一般在设计DPCM回圈内的量化器时常都是假设误差讯号Laplacian分布，因此标准差${\sigma }_{e}$可以很容易就求得
替代量化器：另一种方法则是使用好几个量化器来配合误差讯号。以马可夫过程来描述误差讯号，决定于目前的马可夫过程走到那一个状态，我们可以选择一个特定的量化器。一般二阶、三阶的马可夫过程都有人使用
空间罩(spatial masking)：就影像的DPCM系统，通常我们所使用来预测目前取药值的不会只是左方的取样，通常还包刮上方、左上方、右上方等取样，形成二维的情况。
映射量化器：由于DPCM的误差讯号是预测值与实际值的差，他可能为正为负。为了保持住这个正负号，我们必须使用一个位元来表示，所以我们少了一个表示大小的位元，但其实是可以省下来这个位元的。