非累赘取样编码

以下将探讨两类非累赘取样编码法：多项式预测器及多项式内插法

多项式预测器所采取的方法是：测试下一个取样看看他是不是落在一个n次多项市所展开的范围内。最常被使用的是0次及1次多项式。著名的串长编码(run-length coding)则是0次多项式的一个特别版本。

多项式内插法与多项式预测器类似，唯一的不同是他允许的机动的改变其所展开的范围。一次多项式内插法，又名善行算法，是用许多线段来取代原波形。

多项式预测器

非累赘取样压缩法中多项是预测器算是相当早期的发明。早在60年代早期便有许多论文在讨论他并且实际应用在许多实验上，其中在常被使用到的是0阶预测器及1阶预测器。

在多项式预测器里，下一个取样被预测是在一个n次多项式的范围内。数学上我们可以表示如下，其中${\displaystyle {\hat {x}}_{t}}$ 表示所预测的下一个取样值，${\displaystyle x_{t-i}}$ 为${\displaystyle x_{t}}$ 之前的第${\displaystyle i}$ 个取样

                              ${\displaystyle {\hat {x}}_{t}=x_{t-1}+{\Delta }x_{t-1}+{\Delta }^{2}x_{t-1}+\ldots \ldots +{\Delta }^{n}x_{t-1}\ldots \ldots \ldots \ldots \ldots (a)}$ 式

其中

                              ${\displaystyle {\Delta }x_{t-1}=x_{t-1}-x_{t-2}}$ 
                              ${\displaystyle {\Delta }x_{t-2}=x_{t-2}-x_{t-3}}$ 

以此类推，并且

                              ${\displaystyle {\Delta }^{n}x_{t-1}={\Delta }^{n-1}x_{t-1}-{\Delta }^{n-1}x_{t-2}}$ 

我们可以看出，不同阶次的多项式会产生不同的预测值。如果下一个取样值落在n次多项式之预测值得附近，那么他将会被认为是多余的、累赘的而不会被送出，否则他会被认为是非累赘取样而将其送出。

以下我们将更详细的介绍多项是预测器中最常见的两种：0次预测器及1次预测器。

0次预测器

0次预测器的式子为：

                              ${\displaystyle {\hat {x}}_{t}=x_{t-1}}$ 

换句话说，我们预测下一个取样值是和前一个取样值一样。在实际的设计上，我们得在这个预测值的上下个加上一个误差容忍范围，亦即${\displaystyle {\hat {x}}_{t}}$ 这个预测值并不是单一个${\displaystyle {\hat {x}}_{t-1}}$ 值，而是介于${\displaystyle {\hat {x}}_{t-1}-\lambda }$ 到${\displaystyle {\hat {x}}_{t-1}+\lambda }$ 的一个范围，其中${\displaystyle \lambda }$ 的值由设计人自行根据能容许的误差程度及所需要的压缩比来设定。只要${\displaystyle x_{t}}$ 是落在${\displaystyle (x_{t}-\lambda ,x_{t-1}+\lambda )}$ 这个范围之内，${\displaystyle x_{t}}$ 便会被当成是累赘取样。

以下为0次预测器之算法：
算法：0次预测器

第一步：储存便传送第一个取样${\displaystyle x_{1}}$ ：${\displaystyle i}$ ←${\displaystyle 1}$ ；
第二步：读入下一个取样，${\displaystyle x_{+1}}$ 
第三步：如果${\displaystyle x_{t-1}-\lambda <x_{t+1}<x_{t-1}+\lambda }$ 则${\displaystyle i}$ ←${\displaystyle i+1}$ ；回到第二步；否则储存并传送${\displaystyle (i+1,x_{i+1})}$ ；${\displaystyle i}$ ←${\displaystyle i-1}$ ；回到第二步；

1次预测器

一次预测器的式子为：

                              ${\displaystyle {\hat {x}}_{t}=x_{t-1}+{\delta }x_{t-1}}$ 

其中${\displaystyle {\delta }x_{t-1}=x_{t-1}-x_{t-2}}$ 。请注意，${\displaystyle {\delta }x_{t-1}}$ 可以解释为${\displaystyle x_{t-1}}$ 与${\displaystyle x_{t-2}}$ 所构成之线段的斜率(相邻两个取样之间隔为1，因使分母可以省略)。一次预测器因此可以解释为"假设斜率固定"。

实际上的算法也必须加上一个误差容忍范围${\displaystyle \lambda }$ 。
算法：1次预测器

第一步：储存便传送第一个取样${\displaystyle x_{1}}$ ：${\displaystyle i<-1}$ ；
第二步：储存并传送第二个取样，${\displaystyle x_{2}}$ ；
第三步：如果${\displaystyle n\leftarrow {1}}$ ；${\displaystyle j<i+1}$ ；读入下一取样${\displaystyle x_{j}}$ ；
第三步：若${\displaystyle x_{i+1}+n\times (x_{i+1}-x_{i})-\lambda <x_{j}<x_{i+1}+n\times (x_{i+1}-x_{i})+\lambda }$ ，则
${\displaystyle n\leftarrow {n+1}}$ ；${\displaystyle j\leftarrow {j+1}}$ 
读入下一个取样${\displaystyle x_{j}}$ 并回到第四步；
否则
储存并传送${\displaystyle x_{i}}$ 及其发生时间；
储存并传送${\displaystyle x_{j+1}}$ ；
${\displaystyle i\leftarrow {j}}$ 回到第三步；

多项式内插法

我们也讨论0次与1次的内插法。0次内插法与0次预测器除了前者的${\displaystyle \lambda }$ 可以改变外，其余完全一样。机动性调整${\displaystyle \lambda }$ 值可以让累赘取样更多。

一次内插法又称为扇形算法(fan algorithm)，从60年代被提出以来即受到很大的注意，也有很多成功的应用。基本上他和一次预测器类似。不同的是他的${\displaystyle \lambda }$ 值根据取样的情况而改变。

算法：扇形算法

第一步：${\displaystyle i\leftarrow {1}}$ ；${\displaystyle j\leftarrow {2}}$ ；
设定第一个取样${\displaystyle x_{i}}$ 为非累赘取样： 第二步：以${\displaystyle x_{i}}$ 为心向${\displaystyle x_{i}+\lambda }$ 及${\displaystyle x_{i}-\lambda }$ 展开一扇形；
第三步：如果${\displaystyle n\leftarrow {1}}$ ；${\displaystyle j<i+1}$ ；读入下一取样${\displaystyle x_{j}}$ ；
第三步：若${\displaystyle x_{j+1}}$ 落在扇形内，则，则
${\displaystyle i\leftarrow {j}}$ ；
回到第二步；
否则；
设定${\displaystyle x_{j}}$ 为非累赘取样； ${\displaystyle i\leftarrow {j}}$ ；${\displaystyle j\leftarrow {i+1}}$ ；
回到第二步；
第四步：重复以上的步骤直到编码完所有取样点；
第五步：送出每个非累赘取样及其发生时间；
第六步：接收端收到非累赘取样后以线段将相邻之非累赘取样连起来即可。