1.2 信源編碼問題

1.無失真信源編碼

對于離散信源，當已知信源符號的概率分布時可以計算信源的熵，用它可以表示每個信源符號平均承載的信息量。信源編碼定理表明必然存在一種編碼方法，使得代碼的平均長度可以任意接近但不能低于信源的熵，而且還闡明為了達到這一目標，應該使得概率與碼長匹配。

從無失真信源編碼定理出發，1948年香農在論文中提出并給出了一種簡單的編碼方法，即香農編碼。1952年，R.M.Fano提出了費諾碼。同年，D.A.Huffman提出了一種編碼方法并證明了它是最佳碼，稱為霍夫曼碼。霍夫曼碼是有限長度的塊碼中最好的碼，其代碼總長度最短。但是，霍夫曼碼在實際應用中存在一些塊碼和變長碼所具有的缺點：首先，信源的概率分布必須精確地測量，如果略有變化，就需要更換碼表；其次，對于二進制信源，常需要多個符號合起來編碼才能取得好的效果。

針對霍夫曼碼在實用中的局限，出現了一種稱為算術碼的非塊碼，它是從整個序列的概率匹配角度來進行編碼的。這種概念也是由香農首先提出的，后經許多學者改進逐漸進入實用階段。1968年前后，P.Elias發展了香農—費諾碼，提出了算術編碼的初步思想。1976年，J.J.Rissanen給出和發展了算術編碼，1982年他和G.G.Langdon一起將算術編碼系統化，省去了乘法運算，使其更為簡單，從而易于實現。

如果離散信源符號的概率分布未知，或是對于不確知的信源進行有效編碼時，上述方法就無能為力了，因此人們希望能有一種適用于各類概率特性信源的編碼方法。通用編碼就是在信源統計特性未知時可以進行編碼且編碼效率很高的一種碼。1977年，A.Lempel和J.Ziv提出了一種語法解析碼，稱為LZ碼。1978年，他們又提出了改進算法LZ77和LZ78。1984年，T.A.Welch以LZ編碼中的LZ78算法為基礎設計了一種實用的算法，稱為LZW算法。LZW算法保留了LZ78算法的自適應性能，壓縮效果大致相同，并且邏輯性更強，易于硬件實現，價格低廉，運算速度快，目前作為一種通用壓縮方法廣泛應用于二進制數據的壓縮。

2.限失真信源編碼

無失真信源編碼只適用于離散信源，對輸出模擬信號的連續信源并不適用。因為連續信源輸出信號的每個樣值所載荷的信息量是無限大的，所以用有限長度的信息序列進行編碼時必然導致失真。不過，作為信宿的人或機器都存在一定的靈敏度和分辨力，超過靈敏度和分辨力所傳送的信息是毫無價值的，也是完全沒有必要的，故而當失真在某一限度以下時是不影響正常通信的。例如，語音信源當量化分層超過256級時人耳就很難分辨，所以沒有必要在量化時超過256級。對圖像信源亦是如此，人們看電影時，可以充分利用人眼的視覺暫留效應，當放映速度達24張/秒時，人眼就能將離散的照片在人腦內反映成連續畫面，因此大大超過24張/秒的放映速度是沒有意義的。

限失真信源編碼的研究相對于信道編碼和無失真信源編碼落后約十年左右。1948年，香農的論文已體現了關于率失真函數的思想。1959年，他發表了《保真度準則下的離散信源編碼定理》，首先提出了率失真函數及率失真信源編碼定理。1971年，T.Berger的《信息率失真理論》是一本較全面的論述有關率失真理論的專著。率失真信源編碼理論是信源編碼的核心問題，是頻帶壓縮、數據壓縮的理論基礎，直到今天它仍是信息論研究的課題。

連續信源的信號編成代碼后就不能無失真地再恢復成原來的連續值，此時只能根據率失真理論進行限失真編碼，因此限失真編碼實際上就是最佳量化問題。最佳標量量化常不能達到率失真函數所規定的R（D）值，因此人們后來又提出了向量量化的概念，將多個信源符號合成一個向量并對它進行編碼。從理論上講，某些條件下用向量量化來編碼可以達到上述的R（D）值，但在實現上還是非常困難的，有待進一步改進。1955年，P.Elias提出了預測編碼方法，利用前幾個符號來預測后一個符號的值，然后將預測值與實際值之差即預測誤差作為待編碼的符號，這樣得到的符號間的相關性就大為減弱，從而可提高壓縮比。另一種限失真信源編碼方式是變換編碼，該方法通過樣值空間的變換，例如從時域變到頻域，在某些情況下可以減弱符號間的相關性，從而取得良好的壓縮比。