信源編碼定理

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

(1)需要對(duì)各種信源各符號(hào)或者長(zhǎng)為L(zhǎng)的信源符號(hào)序列的概率進(jìn)行精確的統(tǒng)計(jì)。

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

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