非累贅取樣編碼

非累贅取樣編碼法

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

多項式預測器所採取的方法是：測試下一個取樣看看他是不是落在一個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}$；
回到第二步；
第四步：重複以上的步驟直到編碼完所有取樣點；
第五步：送出每個非累贅取樣及其發生時間；
第六步：接收端收到非累贅取樣後以線段將相鄰之非累贅取樣連起來即可。