非累贅取樣編碼

非累贅取樣編碼法

以下將探討兩類非累贅取樣編碼法：多項式預測器及多項式內插法

多項式預測器所採取的方法是：測試下一個取樣看看他是不是落在一個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}+\mathrm{\Delta }{x}_{t-1}+{\mathrm{\Delta }}^2{x}_{t-1}+\dots \dots +{\mathrm{\Delta }}^n{x}_{t-1}\dots \dots \dots \dots \dots (a)$式

其中

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

以此類推，並且

                              ${\mathrm{\Delta }}^n{x}_{t-1}={\mathrm{\Delta }}^{n-1}{x}_{t-1}-{\mathrm{\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$；
回到第二步；
第四步：重複以上的步驟直到編碼完所有取樣點；
第五步：送出每個非累贅取樣及其發生時間；
第六步：接收端收到非累贅取樣後以線段將相鄰之非累贅取樣連起來即可。