非累赘取样编码
![]() |
非累赘取样编码法
以下将探讨两类非累赘取样编码法:多项式预测器及多项式内插法
多项式预测器所采取的方法是:测试下一个取样看看他是不是落在一个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年代被提出以来即受到很大的注意,也有很多成功的应用。基本上他和一次预测器类似。不同的是他的值根据取样的情况而改变。
算法:扇形算法
第一步:;;
设定第一个取样为非累赘取样:
第二步:以为心向及展开一扇形;
第三步:如果;;读入下一取样;
第三步:若落在扇形内,则,则
;
回到第二步;
否则;
设定为非累赘取样;
;;
回到第二步;
第四步:重复以上的步骤直到编码完所有取样点;
第五步:送出每个非累赘取样及其发生时间;
第六步:接收端收到非累赘取样后以线段将相邻之非累赘取样连起来即可。