跳转到内容

非累赘取样编码

维基百科,自由的百科全书

非累赘取样编码法

[编辑]

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

多项式预测器所采取的方法是:测试下一个取样看看他是不是落在一个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年代被提出以来即受到很大的注意,也有很多成功的应用。基本上他和一次预测器类似。不同的是他的值根据取样的情况而改变。


演算法:扇形演算法

第一步:
设定第一个取样为非累赘取样: 第二步:为心向展开一扇形;
第三步:如果;读入下一取样
第三步:落在扇形内,则,则

回到第二步;
否则;
设定为非累赘取样;
回到第二步;
第四步:重复以上的步骤直到编码完所有取样点;
第五步:送出每个非累赘取样及其发生时间;
第六步:接收端收到非累赘取样后以线段将相邻之非累赘取样连起来即可。