在信息論中，克勞德·香農(nóng)的信源編碼定理（或無噪聲編碼定理）確立了數(shù)據(jù)壓縮的限度，以及香農(nóng)的操作意義。信源編碼定理表明（在極限情況下，隨著獨立同分布隨機變量數(shù)據(jù)流的長度趨于無窮）不可能把數(shù)據(jù)壓縮得碼率（每個符號的比特的平均數(shù)）比信源的香農(nóng)熵還小，不滿足的幾乎可以肯定，信息將丟失。但是有可能使碼率任意接近香農(nóng)熵，且損失的概率極小。碼符號的信源編碼定理把碼字的最小可能期望長度看作輸入字（看作隨機變量）的熵和目標編碼表的大小的一個函數(shù)，給出了此函數(shù)的上界和下界。
簡介
信源編碼是從信息源的符號（序列）到碼符號集（通常是bit）的映射，使得信源符號可以從二進制位元（無損信源編碼）或有一些失真（有損信源編碼）中準確恢復。在信息論中，信源編碼定理非正式地陳述為：
N 個熵均為 的獨立同分布的隨機變量在 時，可以很小的信息損失風險壓縮成多于 ；但相反地，若壓縮到少于 ，則信息幾乎一定會丟失。令，表示兩個有限編碼表，并令 和（分別）表示來自那些編碼表的所有有限字的集合。設 X 為從 取值的隨機變量，令 ?f? 為從 到 的可譯碼，其中。令 S 表示字長 給出的隨機變量。
如果 ?f? 是對 X 擁有最小期望字長的最佳碼，那么(Shannon 1948)：
證明
對于令 表示每個可能的 的字長。定義，其中 C 會使得。于是
其中第二行由吉布斯不等式推出，而第五行由克拉夫特不等式推出：
對第二個不等式我們可以令
于是：
因此
并且
因此由克拉夫特不等式，存在一種有這些字長的無前綴編碼。因此最小的 S 滿足
發(fā)展
在以大數(shù)據(jù)為特征的信息時代，大量的信息流對信息數(shù)據(jù)的存儲和傳輸帶來了極大的挑戰(zhàn)。大量的數(shù)據(jù)直接存儲是高代價且不聰明的做法，信息壓縮存儲往往更加高效。很早以前，工程師們就已經(jīng)掌握了簡單的壓縮技巧，例如 Huffman 壓縮，復雜度低且效率很高的算數(shù)編碼，以及通用的信源編碼算法，像常用的 Lempel-Ziv 算法。然而，由于很多數(shù)據(jù)之間存在關聯(lián)性，另外多信源情形下數(shù)據(jù)的分布式特性，使得可能存在更加聰明有效的信息壓縮新技術，通信的網(wǎng)絡化特征也預示著更為復雜的聯(lián)合壓縮策略相較于單獨壓縮，是更好的選擇。所有這些，也迫切要求相應的信源編碼理論得到不斷發(fā)展，以提供理論支持。
美國數(shù)學家及工程師 C. E. 克勞德·香農(nóng)在 1948 年發(fā)表了題為《A Mathematical Theory of Communication》的學術論文。在該論文中，他提出了通信的數(shù)學模型，從信息的抽象概念、信息的度量、壓縮與傳輸?shù)确矫娼⒘艘徽紫鄬ν暾耐ㄐ艛?shù)學理論。在這篇論文中，
Shannon 首次給出了著名的信源編碼定理與信道編碼定理這兩大編碼定理，奠定了一門嶄新的學科，即信息論的基礎，宣告了信息時代的到來。信息論作為一門關于通信基本理論的學科，自開創(chuàng)以來，指導了各種信息新技術的發(fā)展并指明了可以繼續(xù)改進的方向，為信息時代的進步提供了最為根本的理論依據(jù)。克勞德·香農(nóng) 把所有可以產(chǎn)生信息的源端，比如聲源、光源等抽象為“信源”，以一個概率空間p ，作為其數(shù)學表示。為了解決如何有效表示以及有效存儲信息的問題，Shannon 在進行了深入的研究以后，最終給出了信源編碼定理。該定理以一個簡潔漂亮的數(shù)學量，即信源的信源熵 H?，作為一個信源可以被無損壓縮的理論下界。他在 1959 年發(fā)表的另一篇論文中，討論了率失真問題，提出了率失真編碼定理，豐富了信源編碼理論。信源編碼理論的另一個突破來自兩位貝爾實驗室的研究人員，D. Slepian 和J. Wolf，他們在 1973 年解決了分布式相關信源編碼問題。分布式是通信網(wǎng)絡的一個重要特征，一個關于分布式的理論無疑會對工程應用產(chǎn)生積極的推動和指導作用。自此之后，對于各種模型的多用戶信源編碼問題的研究得到了快速的發(fā)展，取得了大量的研究成果。然而，盡管有不少重大的突破和十分漂亮的結果，信源編碼理論還遠不是一個完整的理論，甚至于已解決的問題遠遠少于未解決的問題。自 Slepian 和 Wolf 發(fā)表他們里程碑式的論文以后，30 多年過去了。但是后續(xù)絕大部分關于多信源編碼問題考慮的是序列編碼情形，關于無錯變長多信源編碼問題研究的相對少得多，這一理論需要得到發(fā)展。大多數(shù)學者在證明
克勞德·香農(nóng) 信源、信道編碼定理，以及各種網(wǎng)絡編碼定理時，一般都使用隨機編碼技術與典型、聯(lián)合典型等數(shù)學工具，得出了信源漸進無損壓縮或限失真時的理論下限和信息漸進無錯傳輸?shù)睦碚撋舷蓿枋鰹楦鞣N Shannon 信息量）。
然而，漸進可忽略的錯誤需要在編碼長度非常大時才能獲得，所以隨機編碼技術并不能直接拿來應用。另外，如果要求接收端知道信源壓縮前的準確信息而不會出錯，那么上述隨機編碼技術就沒有作用了。由于無錯誤的信息論問題與組合、圖論中的很多問題有密切的聯(lián)系，比如 克勞德·香農(nóng) 著名的無錯信道容量問題就可以描述為求一個 n次乘積圖的獨立頂點個數(shù)，以及兩維 Kraft 不等式與相關信源特征圖中最大團（clique）的個數(shù)的關系，以及其他一些原因，使得無錯信息理論得到了科研工作者的重視，這一理論也逐漸發(fā)展成為信息論的一大研究分支。從任意小的漸進和忽略的錯誤概率到完全沒有錯誤，似乎并不是很大的跳躍。然而事實情況是，這兩種情形是截然不同的問題，解決各自問題的方法和工具也完全不相同。
許多研究人員對無錯信源編碼理論進行了討論，提出了解決這一類問題的主要數(shù)學工具和手段，尤其是 J. Korner 結合圖理論提出的圖熵概念以及R. Ahlswede 的超圖染色方法，對后續(xù)研究具有很大的啟示作用。實現(xiàn)無錯的編碼方案有很多種，本文主要關注采用變長編碼的方法。Shannon 的經(jīng)典信源編碼定理發(fā)表以后，很快 D. Huffman給出了最小開銷碼構造的 Huffman 編碼程序。我們知道對于概率分布已知的單信源，Huffman 編碼將給出前綴碼，通過觀察輸出碼字序列，可以還原原始信源消息。作為前綴碼存在的充分和必要條件的 Kraft 不等式首先由 Mc Millan給予證明，隨后 Karush給出了更為常用證明方法。可譯碼是比前綴碼更廣泛的一類碼，檢驗其可譯性的Sardinas-Patterson 程序由 A. Sardinas 和 G. W. Patterson在 1956 年給出。
信源編碼
為減小信源冗余度而對信源符號進行變換的方法。根據(jù)信源性質(zhì)分類，有信源統(tǒng)計特性已知或未知、無失真或限失真、無記憶或有記憶信源的編碼；按編碼方法分類，有分組碼或非分組碼、等長碼或變長碼等。最常見的是信源統(tǒng)計特性已知的離散、平穩(wěn)、無失真信源編碼。主要方法有：①統(tǒng)計編碼，如仙農(nóng)碼、費諾碼、赫夫曼碼、算術碼等。②預測編碼。③變換編碼，以及上述方法的組合(混合編碼)。對于信源統(tǒng)計特性未知的信源編碼稱為通用編碼。衡量信源編碼的主要指標是壓縮比。在無失真編碼中，壓縮的極限是編碼的平均碼表等于信源的符號熵。在限失真編碼中，冗余度的壓縮極限與平均失真的關系服從信源的信息率失真函數(shù)。在工程應用中則是在壓縮比，平均失真和工程實現(xiàn)之間尋求折中。
參考資料 >