信源編碼定理

信源編碼定理第一頁，共九十九頁，2022年，8月28日課程內(nèi)容緒論信源的熵和互信息量信道和信道容量信息率失真函數(shù)信源編碼定理和方法信道編碼定理和方法密碼學第二頁，共九十九頁，2022年，8月28日第五章信源編碼定理和方法第三頁，共九十九頁，2022年，8月28日香農(nóng)信息論的主要內(nèi)容第四頁，共九十九頁，2022年，8月28日香農(nóng)信息論的主要內(nèi)容第五頁，共九十九頁，2022年，8月28日香農(nóng)信息論的主要內(nèi)容第六頁，共九十九頁，2022年，8月28日信源編碼定理和方法編碼的定義和類型無失真編碼定理限失真編碼定理最佳變長編碼方法常用信源編碼方法第七頁，共九十九頁，2022年，8月28日離散信源編碼第八頁，共九十九頁，2022年，8月28日離散信源編碼過程第九頁，共九十九頁，2022年，8月28日離散信源編碼過程第十頁，共九十九頁，2022年，8月28日編碼碼字的碼長第十一頁，共九十九頁，2022年，8月28日平均碼長第十二頁，共九十九頁，2022年，8月28日碼長偏差第十三頁，共九十九頁，2022年，8月28日第十四頁，共九十九頁，2022年，8月28日信源編碼過程第十五頁，共九十九頁，2022年，8月28日分組碼／非分組碼第十六頁，共九十九頁，2022年，8月28日變長碼／定長碼第十七頁，共九十九頁，2022年，8月28日變長碼／定長碼第十八頁，共九十九頁，2022年，8月28日奇異碼／非奇異碼非奇異碼：信源符號與碼字一一對應(yīng)；奇異碼：信源符號與碼字不是一一對應(yīng)；碼１碼２a10.500a20.251110a30.1250000a40.1251101奇異碼第十九頁，共九十九頁，2022年，8月28日唯一可譯碼／非唯一可譯碼唯一可譯碼：任意有限長的碼元序列，只能被唯一地分割成一個個的碼字；非唯一可譯碼：奇異碼，部分非奇異碼碼１碼２碼３碼４a10.50011a20.2511101001a30.1250000100001a40.125110110000001唯一可譯碼第二十頁，共九十九頁，2022年，8月28日唯一可譯碼／非唯一可譯碼碼１碼２碼３碼４a10.50011a20.2511101001a30.1250000100001a40.125110110000001唯一可譯碼例：{10000100}是由碼2{10,0,0,01,00}產(chǎn)生的，但譯碼可以有多種分割方法，如{10,0,00,10,0}等，此時就產(chǎn)生歧義。第二十一頁，共九十九頁，2022年，8月28日即時碼／非即時碼非即時碼：接收端收到一個完整的碼字后，不能立即譯碼，還需要等待下一個碼字開始接收后才能判斷是否可以譯碼。即時碼：任意一個碼字都不是其他碼字的前綴部分，又稱為非延長碼和異前綴碼。第二十二頁，共九十九頁，2022年，8月28日即時碼／非即時碼碼１碼２碼３碼４a10.50011a20.2511101001a30.1250000100001a40.125110110000001即時碼非即時碼第二十三頁，共九十九頁，2022年，8月28日各類碼的隸屬關(guān)系第二十四頁，共九十九頁，2022年，8月28日碼樹編碼的碼樹表示及碼樹定理第二十五頁，共九十九頁，2022年，8月28日碼樹定理編碼的碼樹表示及碼樹定理定長碼：滿樹變長碼：非滿樹第二十六頁，共九十九頁，2022年，8月28日唯一可譯碼存在充要條件第二十七頁，共九十九頁，2022年，8月28日Ｋraft不等式Ｋraft不等式只是一個存在性證明，但不能作為唯一可譯的判斷依據(jù)．第二十八頁，共九十九頁，2022年，8月28日Ｋraft不等式Ｋraft不等式只是一個存在性證明，但不能作為唯一可譯的判斷依據(jù)．第二十九頁，共九十九頁，2022年，8月28日信源編碼定理和方法編碼的定義和類型無失真編碼定理限失真編碼定理最佳變長編碼方法常用信源編碼方法第三十頁，共九十九頁，2022年，8月28日信源編碼器第三十一頁，共九十九頁，2022年，8月28日無失真信源編碼定理第三十二頁，共九十九頁，2022年，8月28日信源編碼器第三十三頁，共九十九頁，2022年，8月28日無失真信源編碼定理第三十四頁，共九十九頁，2022年，8月28日定長無失真信源編碼定理第三十五頁，共九十九頁，2022年，8月28日定長無失真信源編碼定理第三十六頁，共九十九頁，2022年，8月28日定長無失真信源編碼定理第三十七頁，共九十九頁，2022年，8月28日例5-2說明誤碼來源及無失真要求第三十八頁，共九十九頁，2022年，8月28日例5-2說明誤碼來源及無失真要求第三十九頁，共九十九頁，2022年，8月28日例5-1說明誤碼來源及無失真要求第四十頁，共九十九頁，2022年，8月28日信源序列長度Ｌ的界限第四十一頁，共九十九頁，2022年，8月28日信源序列長度Ｌ的界限第四十二頁，共九十九頁，2022年，8月28日編碼效率第四十三頁，共九十九頁，2022年，8月28日編碼過程第四十四頁，共九十九頁，2022年，8月28日例5-2計算保證高效時Ｌ的數(shù)量級第四十五頁，共九十九頁，2022年，8月28日例5-2計算保證高效時Ｌ的數(shù)量級第四十六頁，共九十九頁，2022年，8月28日變長無失真信源編碼定理第四十七頁，共九十九頁，2022年，8月28日單符號變長編碼定理第四十八頁，共九十九頁，2022年，8月28日離散平穩(wěn)無記憶序列變長編碼定理第四十九頁，共九十九頁，2022年，8月28日離散平穩(wěn)無記憶序列變長編碼定理第五十頁，共九十九頁，2022年，8月28日變長無失真編碼的編碼效率第五十一頁，共九十九頁，2022年，8月28日例5-3變長編碼的編碼效率第五十二頁，共九十九頁，2022年，8月28日例5-3變長編碼的編碼效率第五十三頁，共九十九頁，2022年，8月28日例5-3變長編碼的編碼效率第五十四頁，共九十九頁，2022年，8月28日比較例5-2定長和變長編碼的碼長第五十五頁，共九十九頁，2022年，8月28日比較例5-3定長和變長編碼的碼長第五十六頁，共九十九頁，2022年，8月28日信源編碼定理和方法編碼的定義和類型無失真編碼定理限失真編碼定理最佳變長編碼方法常用信源編碼方法第五十七頁，共九十九頁，2022年，8月28日限失真信源編碼定理第五十八頁，共九十九頁，2022年，8月28日限失真信源編碼方法對于連續(xù)平穩(wěn)無記憶信源，雖然無法進行無失真編碼，在限失真情況下，有與上述定理一樣的編碼定理。上述定理只能說明最佳編碼是存在的，而具體的構(gòu)造方法卻一無所知。因而就不能象無損編碼那樣從證明過程中引出概率匹配的編碼方法，一般只能從優(yōu)化的思路去實現(xiàn)最佳編碼。第五十九頁，共九十九頁，2022年，8月28日信源編碼定理和方法編碼的定義和類型無失真編碼定理限失真編碼定理最佳變長編碼方法常用信源編碼方法第六十頁，共九十九頁，2022年，8月28日最佳變長編碼方法最佳變長碼：能載荷一定的信息量，且碼字的平均長度最短，可分離的變長碼的碼字集合稱為最佳變長碼。特點：概率大的信息符號編以短碼；概率小的信息符號編以長碼；第六十一頁，共九十九頁，2022年，8月28日香農(nóng)(Shannon)編碼方法第六十二頁，共九十九頁，2022年，8月28日例5-4演示Shannon編碼過程例5-4對以下的信源進行單符號的二進制香農(nóng)編碼第六十三頁，共九十九頁，2022年，8月28日例5-4演示Shannon編碼過程第六十四頁，共九十九頁，2022年，8月28日例5-4演示Shannon編碼過程第六十五頁，共九十九頁，2022年，8月28日費諾(Fano)編碼方法第六十六頁，共九十九頁，2022年，8月28日例5-5對以下的信源進行二進制費諾編碼例5-5演示Fano編碼過程第六十七頁，共九十九頁，2022年，8月28日例5-5演示Fano編碼過程第六十八頁，共九十九頁，2022年，8月28日哈夫曼(Huffman)編碼方法第六十九頁，共九十九頁，2022年，8月28日例5-6對以下的信源進行二進制Huffman編碼例5-6演示Huffman編碼過程第七十頁，共九十九頁，2022年，8月28日例5-6演示Huffman編碼過程第七十一頁，共九十九頁，2022年，8月28日二進制Huffman編碼特點及注意事項1、碼樹上下的分支的分配碼元應(yīng)該固定，即上分支全為0，下分支全為1，或者上分支全為1，下分支全為0。不能有時上分支為0，下分支為1，有時上分支為1，下分支為0，反之亦然。2、如果合并后的概率與其它信源符號概率相同，則一般將合并后的概率放在信源符號概率之上，可以獲得比較小的碼長方差。3、即時碼第七十二頁，共九十九頁，2022年，8月28日例5-７計算以下兩種Huffman編碼的碼長方差第七十三頁，共九十九頁，2022年，8月28日例5-７計算以下兩種Huffman編碼的碼長方差第七十四頁，共九十九頁，2022年，8月28日例5-8比較符號序列長度對編碼效率的影響第七十五頁，共九十九頁，2022年，8月28日例5-8比較符號序列長度對編碼效率的影響第七十六頁，共九十九頁，2022年，8月28日例5-8比較符號序列長度對編碼效率的影響第七十七頁，共九十九頁，2022年，8月28日信源編碼定理和方法編碼的定義和類型無失真編碼定理限失真編碼定理最佳變長編碼方法常用信源編碼方法第七十八頁，共九十九頁，2022年，8月28日常用信源編碼方法游程編碼算術(shù)編碼矢量量化（限失真壓縮編碼）預測編碼變換編碼第七十九頁，共九十九頁，2022年，8月28日游程編碼第八十頁，共九十九頁，2022年，8月28日游程編碼第八十一頁，共九十九頁，2022年，8月28日游程編碼第八十二頁，共九十九頁，2022年，8月28日常用信源編碼方法游程編碼算術(shù)編碼矢量量化（限失真壓縮編碼）預測編碼變換編碼第八十三頁，共九十九頁，2022年，8月28日算術(shù)編碼分組碼的特點：直觀。

(1)需要對各種信源各符號或者長為L的信源符號序列的概率進行精確的統(tǒng)計。

(2)當L較大時，需要的編譯碼存儲設(shè)備開銷大。

(3)長度L改變時，需要重新計算概率分布非分組碼算術(shù)編碼是一種非分組碼,序貫編譯碼第八十四頁，共九十九頁，2022年，8月28日算術(shù)編碼第八十五頁，共九十九頁，2022年，8月28日算術(shù)編碼第八十六頁，共九十九頁，2022年，8月28日例5-9演示算術(shù)編碼過程第八十七頁，共九十九頁，2022年，8月28日例5-9演示算術(shù)編碼過程第八十八頁，共九十九頁，2022年，8月28日例5-9演示算術(shù)編碼過程第八十九頁，共九十九頁，2022年，8月28日例5-9演示算術(shù)編碼過程第九十頁，共九十九頁，2022年，8月28日例5-9演示算術(shù)譯碼過程第九十一頁，共九十九頁，2022年，8月28日常用信源編碼方法游程編碼算術(shù)編碼矢量量化（限失真壓縮編碼）預測編碼變換編碼第九十二頁，共九十九頁，2022年，8月28日矢量量化（限失真壓縮編碼）矢量量化用于壓縮幅度連續(xù),時間離散的數(shù)據(jù)矢量量化基于兩個事實:(1)壓縮符號序列比壓縮單獨符號在原理上可產(chǎn)生更好的效果;(2)相鄰數(shù)據(jù)項(如圖象、聲音的樣本)也很少會差別很大.第九十三頁，共九十九頁，2022年，8月28日矢量量化（限失真壓縮編碼）基本思想矢量量化時,一個數(shù)據(jù)流被分成許多包含N個字節(jié)的塊(N>1),一個預先訓練定義好的表包含了一系列的模式.對于每個塊,表用來查詢最為相似的模式(通過固定的標準),在表中的每個模式都有一個相關(guān)的索引,因此每個塊都被分配一個索引.這種表