預測編碼

預測編碼的歷史相當之久。最早可以追溯到40年代提出的Delta編碼(Delta modulation)，乃至於到今日我們都還可以常常在學術性期刊上看到線性預測編碼的論文。一個領域研究了五十多年還繼續有新的結果不斷的出現，一方面很少見，另一方面也足見有其重要性了。

預測編碼是屬於時間領域的編碼法。他的基本理念是(有幾分馬可夫過程的味道)利用前面已經出現了的符號來預測目前的符號，然後將實際上的符號與預測符號得到預測誤差，將此誤差編碼並送出。預測誤差的編碼法可以採用無失真資料壓縮法或失真資料壓縮法。若採用前者，則整個系統仍然是無失真資料壓縮法；反之，若採用後者，則整個系統就成了失真資料壓縮法。因此預測編碼既是屬於無失真資料壓縮法，也是屬於失真資料壓縮法。

使用預測編碼的動機是誤差訊號的變化要比原訊號的變化小許多，因此我們可以使用比較少的位元來為每一個誤差訊號的取樣做編碼以達到資料壓縮的目的。

本條目將介紹兩個著名的技術：

Delta編碼與誤差訊號編碼(differential pulse code modulation)。兩種技術都各有適應性與非適應性兩種方法。

Delta編碼(DM)

Delta編碼(Delta modulation)是預測編碼中最簡單的一種，它使用前一個取樣值來預測目前的取樣值並且將預測值與實際值之誤差量化成只有兩階。如果這個誤差值為正，則加$\Delta$，如果是負的，則減$\Delta$。Delta編碼的一個重要特色是它只允許$\Delta$與$-\Delta$兩個量化階，因此可以用一個位元來表示。也就是因為如此，他有時也被稱為單位原(1-bit)系統。

傳統式的Delta編碼

Delta編碼器由三個部分組成：減法器、二階量化器及積分器。整個Delta編碼器的輸出決定於輸入之取樣值與由積分器所預測之取樣值，這兩個值的差；如果這個差值為正則系統送出正脈衝(pulse)，若為負則送出負脈衝。整個系統不需要任何的緩衝區(buffer)，他持續的送出正脈衝：代表$\Delta$，或負脈衝：代表$-\Delta$，因此系統的輸出與原訊號同步，沒有延遲。有些系統會希望他的壓縮系統能做到這一步。

解碼端其實只需要一個積分器即可。累加編碼端所送出的正負脈衝，即$(\pm \Delta )$就可得到解碼訊號。 有時重建訊號之波行會趕不上原訊號波形，這是Delta編碼的一個先天限制，我們稱之為斜率超負載(slope overload)。構成斜率超負載的原因是因為Delta編碼所能產生出的最大斜率為： 最大斜率$=(\pm \Delta )\times$(取樣頻率) 而此最大斜率小於原訊號波形之斜率所致。

適應性Delta編碼(ADM)

由於傳統式的Delta編碼會有增加粒狀雜訊的缺點。折衷辦法便是選擇SNR最大時的$\Delta$值。但是這無法滿足大部分的要求，預期使該系統具備適應性。

適應性的Delta編碼法的種類雖然很多，大部分都有一個共同的特性：監視員訊號斜率的變化情形以調整$\Delta$值的大小。斜率的監測則是藉由監視連續脈衝的來完成。如果接連出現的脈衝都是正的(或者都是負的)，那麼很有可能這一段波形的斜率相當大(或者很大的負斜率)。這個時候就應該考慮改變$\Delta$值(加大)值到負(正)的脈衝出現為止。

Song所提出的方法提出。Delta編碼器的輸出為+1及-1，每當輸出值沒改變則增加$\Delta$值50%，反之，如果改變則減少50%。利用這種方法便可以同時降低斜率超負載時，$\Delta$的值會逐漸地以50%的速度加大以趕上輸入訊號；反之，如果發生超出原訊號或者脈衝改變正負號時，$\Delta$的值便以50%的速度逐漸減小以降低粒狀雜訊。另$E_{k+1}$表示輸出之脈衝值$(+1,-1)$，$S_{k+1}$為目前的輸入值，$X_{k+1}$為預測值，$\Delta _{m}in$，為所允許之最小$\Delta$值，則$\Delta _{k}+1$的值可以表示如下：

                              $E_{k+1}=[S_{k+1}-X_{k}]$之正負號

                              $\Delta _{k+1}={\begin{cases}|\Delta _{k}|[E_{k+1}+{\frac {1}{2}}E_{k}],if|\Delta _{k}|\geq \Delta _{min}\\\Delta _{min}E_{k+1},if|\Delta _{k}|<\Delta _{min}\end{cases}}$

誤差訊號編碼(DPCM)

誤差訊號編碼(differential pulse code modulation)，以下簡稱(DPCM)是預測編碼中最常使用的一種。在DPCM裡，實際之取樣值與預測值相減得一誤差值，此誤差值在經過量化與編碼後送出。和Delta編碼不同的是，DPCM使用較精確的預測器而且他的輸出也不再是只有兩種值。DPCM的壓縮效能主要決定於預測器與量化器設計優劣。

在DPCM中，$m$個剛讀過的取樣(如果是影像，這m個像素通常指的是目前像素的鄰居)透過一個線性預測函數得到一個目前這個取樣的預測值，即

                              ${\hat {x}}_{m}=\sum _{i=0}^{m-1}\alpha _{i}x_{i}$

其中${\hat {x}}_{m}$為預測所得的目前取樣值，$x_{0}$、$x_{1}$、$x_{2}$、……、$x_{m-1}$維剛讀過的前$m$個取樣，$\alpha _{0}$、$\alpha _{1}$、$\alpha _{2}$、……、$\alpha _{m-1}$則為此線性預測函數之係數(加權值)。誤差訊號$e_{m}$則定義為實際取樣值與預測值之差；即

                              $e_{m}=x_{m}-{\hat {x}}_{m}$

和原訊號相比，誤差訊號的特色是：它的變化比較小，取樣間累贅也比較小。失真與無失真DPCM的主要差別就在於誤差訊號的處理方式。如果我們採用無失真資料壓縮法來編碼誤差訊號，即為無失真DPCM；反之，就像大部分情形一樣，DPCM為了達到更低的位元率。會更進一步的將誤差訊號量化在做傳送。

預測器之最佳化

預測器內的係數，α_i，可以是事先設計好供所有的同類訊號(也就是所有的影像)使用，也可以是針對每一筆資料各自設計一組係數，甚至於同一筆資料內的係數可以隨時時間改變。和馬可夫過程類似，我們定義被用來預測目前取樣值的前面剛讀過的取樣點之數目為DPCM之階次(order)。一般來說，高階次的DPCM系統之表現會優於低階次的DPCM系統。然而，當階次高過某一個值以後，提高階次的收益將很有限／譬如說，研究顯示超過三階以上的電視畫面及X-光片影像之DPCM系統頂多只能多得到及小的收益，而類似的，超過二階以上的心電圖訊號之DPCM系統也只能多得到極小的收益。

以下為一筆資料預測器係數的最佳化問題。如前所述，將MSE最小化是很普遍的被接受的標準，因此我們的設計也是以令MSE最小為目標。在這個標準下，$x_{m}$的最佳線性預測值${\hat {x}}_{m}$必須要能夠使誤差的平方之期望值為最小；也就是說，他必須使下列的式子最小化：

                              ${\sigma _{e}}^{2}=E{(x_{m}-\sum _{i=0}^{m-1}\alpha _{i}x_{i})^{2}}=E{(x_{m}-{\hat {x}}_{m})^{2}}$

要找${\sigma _{e}}^{2}$到的最小值，我們計算偏微分並且令其為零：

                              ${\frac {{\sigma }E{(x_{m}-{\hat {x}}_{m})^{2}}}{\sigma \alpha _{i}}}={\frac {{\sigma }E{[x_{m}-(a_{0}x_{0}+a_{1}x_{1}+\ldots +a_{m-1}x_{m-1})]^{2}}}{\sigma \alpha _{i}}}=-2E[(x_{m}-{\hat {x}}_{m})x_{i}]=0\ldots \ldots \ldots \ldots \ldots (a)$式

定義

                              $R_{ij}=E(x_{i}x_{j})$

為相關聯值(autocorrelation)，則由(a)式得知

                              $E[x_{m}x_{i}]=E[{{\hat {x}}_{m}}x_{i}]$

                              $R_{mi}=E[a_{0}x_{0}x_{i}+a_{1}x_{1}x_{i}+\ldots +a_{m-1}x_{m-1}x_{i}]=a_{0}R_{0i}+a_{1}R_{1i}+\ldots +a_{m-1}R_{(m-1)i}\ldots \ldots \ldots \ldots \ldots (b)$式

                              其中$i=0,1,\ldots ,{m-1}$

這是一組$m$個變數的聯立方程式，只要解了這組聯立方程式便可以求得最佳化之$\alpha _{0}$、$\alpha _{1}$、$\alpha _{2}$、$\ldots \ldots$、$\alpha _{m-1}$值。如果預測$x_{m}$值的線性預測器是使用的是這些最佳化的$\alpha _{i}$，則MSE為

                              ${\sigma _{e}}^{2}=E{(x_{m}-{\hat {x}}_{m})^{2}}=E{(x_{m}-{\hat {x}}_{m})x_{m}}-{(x_{m}-{\hat {x}}_{m}){\hat {x}}}$

                              但是從(a)式知道${(x_{m}-{\hat {x}}_{m}){\hat {x}}}=0$；於是

                              ${\sigma _{e}}^{2}=E{(x_{m}-{\hat {x}}_{m})x_{m}}=E[(x_{m})^{2}]-E[{\hat {x}}_{m}x_{m}]=R_{mm}-(\alpha _{0}R_{0m}+\alpha _{1}R_{1m}\ldots \ldots \ldots \ldots \ldots (c)$式

如果我們將${\sigma _{e}}^{2}$視為誤差訊號之方差而將$R_{mm}$視為原訊號之方差，那麼很顯然的誤差訊號的方差比原訊號的方差小。(c)式給了我們這個結果也等於為DPCM的使用提供了一個很有力的證明。

而由(b)式我們可以知道預測器的複雜度決定於$m$的大小。若$m=1$，即只使用前一個取樣值來預測目前的取樣值，則這種最簡單的預測器其係數應該是：

                              $\alpha _{0}={\frac {R_{10}}{R_{00}}}={\frac {R_{10}}{{\sigma }^{2}}}$

換句話說，我們的預測器應該設為

                              ${\hat {x}}_{1}={\frac {R_{10}}{{\sigma }^{2}}}x_{0}$

預測器之最佳化

使用DPCM技術能做到資料壓縮的部分原因是：誤差訊號會再經過量化。量化器之設計可以是以統計標準或者視覺標準為基礎。雖然之前已經有許多以視覺標準為基礎的量化器設計，但是只要我們想到人類視覺系統(HVS)的複雜度，就不難了解何以用這種方法至今仍然充滿著爭議：什麼是最好的HVS?如何驗證?以下的討論，因此還是在統計標準的基礎上尋求最佳化的量化器設計。

量化器基本上是一個將許多輸入值(也許是無窮多個)對應到比較少而且有限輸出值的階梯函數，我們值得探討Lloya-Max量化器，因為除了DPCM外在其他地方他也用的到。他整個推導式子的過程是將下列的式子最小化：

                              $D=\sum _{i=0}^{N-1}\int _{d_{i}}^{d_{i+1}}{(e-r_{i})}^{2}p(e)\,\mathrm {d} e$

其中$d_{i}$及$r_{i}$之定義如前。他所得的解為：

                              $d_{i}={\frac {r_{i-1}+r_{i}}{2}}\ldots \ldots \ldots \ldots \ldots (d)$式

                              $r_{i}={\frac {\int _{d_{i}}^{d_{i+1}}ep(e)\,\mathrm {d} e}{\int _{d_{i}}^{d_{i+1}}p(e)\,\mathrm {d} e}}\ldots \ldots \ldots \ldots \ldots (e)$式

一般而言，(d)與(e)必須藉茱萸數值方法來求解。在某些特殊情況下，例如Laplacian機率分布，我們可以直接求得其解。一般的情況下，我們可以利用下面的數值方法來求得

第一步：隨意設定$d_{i}$的起始值，其中$d_{0}<d_{1}<\ldots <d_{n}$
第二步：根據目前之$d_{i}$值使用(e)式求得新的$r_{i}$
第三步：根據目前之$r_{i}$值使用(d)式求得新的$d_{i}$
第四步：所求得之新的$d_{i}$、$r_{i}$值如果與前一次求得之值相差很小，則$d_{i}$、$r_{i}$即為所求；否則回到第二步

在大部分得情況下，$d_{i}$及$r_{i}$的值會很快的收斂，因此演算法可以在幾次輪迴後即跳出。

適應性DPCM(ADPCM)

DPCM的最大限制便是他的預測器及量化器都是固定的。可以讓他具備適應性：或者在預測器、或者在量化器、或者兩者都加上適應性。適應性預測器通常都可以降低預測誤差。較低的預測誤差輸入到量化器內，在相同的位元率下，其量化誤差也會比較小，因此重建訊號品質會較高。另一方面，適應性量化可以藉由統計的方式機動的改變$d_{i}$與$r_{i}$值而直接降低量化誤差。

適應性預測

非適應性的預測器通常在訊號產生突然的變化時會有很差的表現，例如影像的邊。我們可以針對不同方向的邊各設計一組預測器係數。採用一些常用的經驗法則去判斷邊的方向，然後根據邊的方向選組一組預測器。

另一個方法是在預測器的輸出再乘以一個適應性係數。適應性係數k的值決定於前一個量化器的重建值。如果前一個重建值是一個最大的正數，那麼有很大的可能性會是斜率超負載的情況，因此我們可以選擇k大於1以加快重建訊號的腳步。且這方法也可以改善整個系統的品質。

雖然以上兩個方法都能重現訊號之品質有所改善，一般大家所常用的還是固定的預測器加上一個適應性量化器。

適應性量化

為了配合DPCM迴圈內之量化器具備適應性，已經有許多方法可用，如下所示：

誤差訊號常態化：由於一般在設計DPCM迴圈內的量化器時常都是假設誤差訊號Laplacian分布，因此標準差${\sigma }_{e}$可以很容易就求得
替代量化器：另一種方法則是使用好幾個量化器來配合誤差訊號。以馬可夫過程來描述誤差訊號，決定於目前的馬可夫過程走到那一個狀態，我們可以選擇一個特定的量化器。一般二階、三階的馬可夫過程都有人使用
空間罩(spatial masking)：就影像的DPCM系統，通常我們所使用來預測目前取藥值的不會只是左方的取樣，通常還包刮上方、左上方、右上方等取樣，形成二維的情況。
映射量化器：由於DPCM的誤差訊號是預測值與實際值的差，他可能為正為負。為了保持住這個正負號，我們必須使用一個位元來表示，所以我們少了一個表示大小的位元，但其實是可以省下來這個位元的。