通用編碼

信源的統計特性不確知或者完全不知時的信源編碼問題，是美國學者L．D．戴維森於1966年提出的，後來他的研究集中於給出一類信源，並將這類信源中的每一個都假定出其統計特性。遇到的實際信源，其統計特性將是假定出的這一類信源中的某一個，這就可找出一種匹配碼錶，以完成編碼。這個結果可用於多用户數據處理中的數據通信。

通用編碼的研究，基本上可分為兩類：一類是以估計信源的概率統計特性為基礎，即邊統計、邊編碼，以使完成的編碼與信源概率統計特性近似地匹配；另一類是從序列複雜度理論入手，並以它作為單個序列進行通用編碼，以求得平均碼長的極限。對於平穩信源，以上兩類研究方法都可以從理論上證明達到漸近最優。對於非平穩信源，通用編碼的性能好壞主要體現在自適應性能上。

信源編碼的主要目的：提高傳輸效率；

信源編碼的基本思想：根據信源的統計特性，去除消息中的冗餘成分；

信源編碼的主要類別：

(1)無失真的信源編碼：編碼和譯碼是可逆的，譯碼後可無失真地恢復原來的信息；

(2)限失真的信源編碼：研究如何在滿足失真不大於某一值的條件下，任何獲得最有效的傳輸效率；

信源的分類

離散信源：只有有限種符號(狀態)的信源：如文字、數據、抽樣量化後的樣值；

連續信源：取值連續或有無限多種狀態的信源：未經抽樣量化（數字化）的信號，如模擬的語音、圖像和視頻等。

（1）離散信源編碼定理

A. 等長編碼定理

假定信源的統計特性滿足離散、無記憶、平穩和遍歷條件。

設信源是長度為L的矢量/分組序列，每一位有n種取值

編碼器輸出是長度為K的矢量/碼字，每一位有m種取值

無失真編碼要求：

每個不同輸入序列均可找到不同的輸出序列與其對應；

有效性編碼要求：

每一個編碼輸出序列沒有冗餘。

編碼的有效性和無失真要求有矛盾。

根據無失真編碼要求如圖1 。

典型序列與非典型序列

可以證明，當L足夠大時，某些序列的集合會以趨於1的概率

出現，每個這些序列以相同的概率出現

，稱這些序列為典型序列，典型序列的個數

。

B. 變長編碼定理香農(Shannon)第一變長編碼定理當L足夠大式，給定任意的

，若

，其中 k是平均的編碼長度，則可以找到一種編碼方法，使譯碼的差錯

。

編碼效率定義：通常變長編碼通常比等長編碼有更高的效率。

C. 等長編碼

(1)簡單的等長編碼

簡單地根據信源不同符號的個數，用等長碼字表示的一種編碼方式。

編碼效率的分析：

因為信源符號出現不等概，所以效率降低；

只有信源符號等概出現，效率才有可能達到100%。

(2)對信源序列進行等長編碼

考慮對信源輸出符號進行某種變換，使其具體“等概”特性，對每L個信源符號構成的序列聯合進行編碼，若序列足夠長，每個序列中所包含的各種不同符號的個數趨於一致(典型序列)，成為等概的序列，其餘的小概率的序列可以不予考慮。

D. 變長編碼

對出現概率大的符號用較短的碼字，概率小的符號用較長的碼字，使平均的碼字長度儘可能的短，以提高編碼效率。

(2)哈夫曼(Huffman)編碼

哈夫曼編碼應用的條件：信源的統計特性已知

哈夫曼編碼是一種最佳的不等長編碼

哈夫曼編碼的步驟：

a.將M信源符號按概率大小，以遞減次序，從上到下排成一列；

b.對處於最下面的概率最小的r個信源符號，一一對應地分別賦予碼符號a1、a2、…、ar，把這r個概率最小的信源符號相應的概率相加，所得的值用一個虛擬的符號代表，與餘下的M－r個符號組成含有(M-r)+1個符號的第一次縮減信源S1；

c.對縮減信源S1仍按其概率大小以遞減次序從上到下排列，按照步驟(2)的方法處理，得到一個含有[(M-r)+1]-r+1個符號的第二次縮減信源S2；

d.按照上述的方法，依次繼續下去，每次縮減所減少的符號數是r-1個；只要縮減後的信源Si符號的個數大於r，縮減就繼續進行；

e.當進行第k次縮減後信源Sk符號個數剛好等於r，即有

，則對最後這r個符號分別賦予符號a1、a2、…、ar；

f.從最後賦予的碼符號開始，沿着每一信源符號在各次縮減過程中得到的碼符號進行路線前向返回，達至每一信源符號，按前後次序，把返回路途中所遇到的碼符號排成符號序列，這個序列，就是相應終點信源符號對應的碼字；

通用編碼是一類具有現實意義、並很有發展前途的信源編碼方法與理論。