非累贅取樣編碼法
以下將探討兩類非累贅取樣編碼法：多項式預測器及多項式內插法
多項式預測器所採取的方法是：測試下一個取樣看看他是不是落在一個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}^2x_{t-1}+\ldots\ldots+{\Delta}^nx_{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}^nx_{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則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；
第二步：儲存並傳送第二個取樣，x_2；
第三步：如果n\leftarrow{1}；j；讀入下一取樣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；讀入下一取樣x_j；
第三步：若x_{j+1}落在扇形內，則，則
i\leftarrow{j}；
回到第二步；
否則；
設定x_j為非累贅取樣；
i\leftarrow{j}；j\leftarrow{i+1}；
回到第二步；
第四步：重複以上的步驟直到編碼完所有取樣點；
第五步：送出每個非累贅取樣及其發生時間；
第六步：接收端收到非累贅取樣後以線段將相鄰之非累贅取樣連起來即可。
评论 (0)