信息論與編碼ppt

信息論與編碼ppt第一頁，共十六頁，2022年，8月28日引言人類很早就學會利用語言文字來表示信息，而隨著時間的流逝，這些語言文字逐漸發(fā)展成更簡練的形式，即現(xiàn)代人表達和傳遞信息的文字形式。無論是古文字還是現(xiàn)代文字，都有相同之處，即基本組成要素的個數(shù)都是有限的。這個事實在信息論中依然有效，在此基礎上可建立相應的數(shù)學模型，也即編碼理論。第二頁，共十六頁，2022年，8月28日編碼的目的編碼理論更關心如何高效地表示信息，這是古代語言所不具備的特性。第三頁，共十六頁，2022年，8月28日語言與編碼形式語言(FormalLanguage)語言由符號(Symbol)組成，它是語言的基本元素且總數(shù)有限，其全體則組成了字母表(Alphabet)。編碼(Coding)碼字(Codeword)，所有碼字形成集合即碼簿(Codebook)。譯碼(Decoding)第四頁，共十六頁，2022年，8月28日編碼:正確vs性能采用標點符號進行斷句的方案如何衡量編碼性能數(shù)學期望形式描述每個隨機變量所需碼字長度編碼的期望長度(ExpectedLength)傳輸終止符號(EOT)的重要性壓縮是要尋找隨機變量的最小描述長度(MinimumDescriptionLength,MDL)。第五頁，共十六頁，2022年，8月28日唯一可譯碼編碼的擴展是非奇異的，稱此情況下的編碼是唯一可譯碼(UniquelyDecodableCode)。Sardinas和Patterson判斷唯一可譯碼方法編碼的拼接懸掛后綴(DanglingSuffix)。利用遍歷算法不但可判斷編碼的唯一可譯性，還可根據(jù)路徑構造出存在二義性的序列。懸掛前綴也可第六頁，共十六頁，2022年，8月28日即時碼與前綴碼讀入當前字符后立即得到譯碼結果的編碼稱之為即時碼(InstantaneousCode)。即時碼必須是唯一可譯碼，反之則不然。前綴碼(PrefixCode)后綴碼(SuffixCode)前綴碼和后綴碼都是唯一可譯碼，但如果采用了不合適的譯碼方式則它們則不為即時碼。第七頁，共十六頁，2022年，8月28日譯碼二叉樹第八頁，共十六頁，2022年，8月28日前綴碼的碼長約束Kraft不等式(Kraft'sInequality)可考察其碼字形成譯碼樹由于前綴碼的碼字必須放置于葉子結點碼字長度恰為根到葉子結點的路徑長度可使用上述結論證明Kraft不等式第九頁，共十六頁，2022年，8月28日唯一可譯碼的碼長約束唯一可譯碼也滿足Kraft不等式的特性取前綴碼即可Karush的簡化證明生成函數(shù)字母表中元素的不同排列形式任意次擴展情況下均成立，可取極限證之第十頁，共十六頁，2022年，8月28日最佳碼下界Shannon編碼第十一頁，共十六頁，2022年，8月28日Huffman編碼貪婪算法Huffman編碼是最佳碼典范碼(CanonicalCode)滿足的性質歸納證明Huffman編碼的最佳性一般情況下的Huffman編碼第十二頁，共十六頁，2022年，8月28日Fano編碼Huffman編碼使用了較為復雜的堆Fano編碼可給出較簡單的實現(xiàn)方式，不但可降低編碼實現(xiàn)難度，且擁有較好的性能近似等分Fano編碼的期望長度滿足第十三頁，共十六頁，2022年，8月28日Shannon-Fano-Elias編碼區(qū)間二叉樹(IntervalBinaryTree)修正累積分布函數(shù)從區(qū)間相互不相交特性證明唯一可譯將累積分布函數(shù)進一步減少可得到Shannon編碼，更為緊致更為一般的算術編碼第十四頁，共十六頁，2022年，8月28日總結通過對作者論文的學習，得知最好的壓縮工具將概率模型預測結果用于算術編碼。算術編碼由JormaRissanen發(fā)明，并且由Witten、Neal以及Cleary將它轉變成一個實用的方法。優(yōu)點：提高編碼效率；缺點：需要大量緩沖設備來存儲這些變長碼,然后再以恒定的碼率進行傳送；在傳輸?shù)倪^程中如果出現(xiàn)了誤碼,容易引起錯誤擴散,所以要求有優(yōu)質的信道。有時為了得到較高的編碼效率，先采用某種正交