非累赘取样编码

非累赘取样编码法

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

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

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

多项式预测器

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

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

                              ${\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)$式

其中

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

以此类推，并且

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

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

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

0次预测器

0次预测器的式子为：

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

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

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

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

1次预测器

一次预测器的式子为：

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

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

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

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

多项式内插法

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

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

算法：扇形算法

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