信息論與編碼ppt

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