非累赘取样编码

非累赘取样编码法

编辑

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

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

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

多项式预测器

编辑

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

在多项式预测器里,下一个取样被预测是在一个n次多项式的范围内。数学上我们可以表示如下,其中 表示所预测的下一个取样值,  之前的第 个取样


                               

其中

                               
                               

以此类推,并且

                               

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

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

0次预测器

编辑

0次预测器的式子为:

                               

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

以下为0次预测器之演算法:
演算法:0次预测器

第一步:储存便传送第一个取样   
第二步:读入下一个取样, 
第三步:如果   ;回到第二步;否则储存并传送   ;回到第二步;

1次预测器

编辑

一次预测器的式子为:

                               

其中 。请注意, 可以解释为  所构成之线段的斜率(相邻两个取样之间隔为1,因使分母可以省略)。一次预测器因此可以解释为"假设斜率固定"。

实际上的演算法也必须加上一个误差容忍范围 
演算法:1次预测器

第一步:储存便传送第一个取样  
第二步:储存并传送第二个取样, 
第三步:如果  ;读入下一取样 
第三步: ,则
  
读入下一个取样 并回到第四步;
否则
储存并传送 及其发生时间;
储存并传送 
 回到第三步;

多项式内插法

编辑

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

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


演算法:扇形演算法

第一步:  
设定第一个取样 为非累赘取样: 第二步: 为心向  展开一扇形;
第三步:如果  ;读入下一取样 
第三步: 落在扇形内,则,则
 
回到第二步;
否则;
设定 为非累赘取样;   
回到第二步;
第四步:重复以上的步骤直到编码完所有取样点;
第五步:送出每个非累赘取样及其发生时间;
第六步:接收端收到非累赘取样后以线段将相邻之非累赘取样连起来即可。