信息論與編碼ppt

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