信源編碼定理

信源編碼定理第1頁(yè)，課件共99頁(yè)，創(chuàng)作于2023年2月課程內(nèi)容緒論信源的熵和互信息量信道和信道容量信息率失真函數(shù)信源編碼定理和方法信道編碼定理和方法密碼學(xué)第2頁(yè)，課件共99頁(yè)，創(chuàng)作于2023年2月第五章信源編碼定理和方法第3頁(yè)，課件共99頁(yè)，創(chuàng)作于2023年2月香農(nóng)信息論的主要內(nèi)容第4頁(yè)，課件共99頁(yè)，創(chuàng)作于2023年2月香農(nóng)信息論的主要內(nèi)容第5頁(yè)，課件共99頁(yè)，創(chuàng)作于2023年2月香農(nóng)信息論的主要內(nèi)容第6頁(yè)，課件共99頁(yè)，創(chuàng)作于2023年2月信源編碼定理和方法編碼的定義和類型無(wú)失真編碼定理限失真編碼定理最佳變長(zhǎng)編碼方法常用信源編碼方法第7頁(yè)，課件共99頁(yè)，創(chuàng)作于2023年2月離散信源編碼第8頁(yè)，課件共99頁(yè)，創(chuàng)作于2023年2月離散信源編碼過(guò)程第9頁(yè)，課件共99頁(yè)，創(chuàng)作于2023年2月離散信源編碼過(guò)程第10頁(yè)，課件共99頁(yè)，創(chuàng)作于2023年2月編碼碼字的碼長(zhǎng)第11頁(yè)，課件共99頁(yè)，創(chuàng)作于2023年2月平均碼長(zhǎng)第12頁(yè)，課件共99頁(yè)，創(chuàng)作于2023年2月碼長(zhǎng)偏差第13頁(yè)，課件共99頁(yè)，創(chuàng)作于2023年2月第14頁(yè)，課件共99頁(yè)，創(chuàng)作于2023年2月信源編碼過(guò)程第15頁(yè)，課件共99頁(yè)，創(chuàng)作于2023年2月分組碼／非分組碼第16頁(yè)，課件共99頁(yè)，創(chuàng)作于2023年2月變長(zhǎng)碼／定長(zhǎng)碼第17頁(yè)，課件共99頁(yè)，創(chuàng)作于2023年2月變長(zhǎng)碼／定長(zhǎng)碼第18頁(yè)，課件共99頁(yè)，創(chuàng)作于2023年2月奇異碼／非奇異碼非奇異碼：信源符號(hào)與碼字一一對(duì)應(yīng)；奇異碼：信源符號(hào)與碼字不是一一對(duì)應(yīng)；碼１碼２a10.500a20.251110a30.1250000a40.1251101奇異碼第19頁(yè)，課件共99頁(yè)，創(chuàng)作于2023年2月唯一可譯碼／非唯一可譯碼唯一可譯碼：任意有限長(zhǎng)的碼元序列，只能被唯一地分割成一個(gè)個(gè)的碼字；非唯一可譯碼：奇異碼，部分非奇異碼碼１碼２碼３碼４a10.50011a20.2511101001a30.1250000100001a40.125110110000001唯一可譯碼第20頁(yè)，課件共99頁(yè)，創(chuàng)作于2023年2月唯一可譯碼／非唯一可譯碼碼１碼２碼３碼４a10.50011a20.2511101001a30.1250000100001a40.125110110000001唯一可譯碼例：{10000100}是由碼2{10,0,0,01,00}產(chǎn)生的，但譯碼可以有多種分割方法，如{10,0,00,10,0}等，此時(shí)就產(chǎn)生歧義。第21頁(yè)，課件共99頁(yè)，創(chuàng)作于2023年2月即時(shí)碼／非即時(shí)碼非即時(shí)碼：接收端收到一個(gè)完整的碼字后，不能立即譯碼，還需要等待下一個(gè)碼字開始接收后才能判斷是否可以譯碼。即時(shí)碼：任意一個(gè)碼字都不是其他碼字的前綴部分，又稱為非延長(zhǎng)碼和異前綴碼。第22頁(yè)，課件共99頁(yè)，創(chuàng)作于2023年2月即時(shí)碼／非即時(shí)碼碼１碼２碼３碼４a10.50011a20.2511101001a30.1250000100001a40.125110110000001即時(shí)碼非即時(shí)碼第23頁(yè)，課件共99頁(yè)，創(chuàng)作于2023年2月各類碼的隸屬關(guān)系第24頁(yè)，課件共99頁(yè)，創(chuàng)作于2023年2月碼樹編碼的碼樹表示及碼樹定理第25頁(yè)，課件共99頁(yè)，創(chuàng)作于2023年2月碼樹定理編碼的碼樹表示及碼樹定理定長(zhǎng)碼：滿樹變長(zhǎng)碼：非滿樹第26頁(yè)，課件共99頁(yè)，創(chuàng)作于2023年2月唯一可譯碼存在充要條件第27頁(yè)，課件共99頁(yè)，創(chuàng)作于2023年2月Ｋraft不等式Ｋraft不等式只是一個(gè)存在性證明，但不能作為唯一可譯的判斷依據(jù)．第28頁(yè)，課件共99頁(yè)，創(chuàng)作于2023年2月Ｋraft不等式Ｋraft不等式只是一個(gè)存在性證明，但不能作為唯一可譯的判斷依據(jù)．第29頁(yè)，課件共99頁(yè)，創(chuàng)作于2023年2月信源編碼定理和方法編碼的定義和類型無(wú)失真編碼定理限失真編碼定理最佳變長(zhǎng)編碼方法常用信源編碼方法第30頁(yè)，課件共99頁(yè)，創(chuàng)作于2023年2月信源編碼器第31頁(yè)，課件共99頁(yè)，創(chuàng)作于2023年2月無(wú)失真信源編碼定理第32頁(yè)，課件共99頁(yè)，創(chuàng)作于2023年2月信源編碼器第33頁(yè)，課件共99頁(yè)，創(chuàng)作于2023年2月無(wú)失真信源編碼定理第34頁(yè)，課件共99頁(yè)，創(chuàng)作于2023年2月定長(zhǎng)無(wú)失真信源編碼定理第35頁(yè)，課件共99頁(yè)，創(chuàng)作于2023年2月定長(zhǎng)無(wú)失真信源編碼定理第36頁(yè)，課件共99頁(yè)，創(chuàng)作于2023年2月定長(zhǎng)無(wú)失真信源編碼定理第37頁(yè)，課件共99頁(yè)，創(chuàng)作于2023年2月例5-2說(shuō)明誤碼來(lái)源及無(wú)失真要求第38頁(yè)，課件共99頁(yè)，創(chuàng)作于2023年2月例5-2說(shuō)明誤碼來(lái)源及無(wú)失真要求第39頁(yè)，課件共99頁(yè)，創(chuàng)作于2023年2月例5-1說(shuō)明誤碼來(lái)源及無(wú)失真要求第40頁(yè)，課件共99頁(yè)，創(chuàng)作于2023年2月信源序列長(zhǎng)度Ｌ的界限第41頁(yè)，課件共99頁(yè)，創(chuàng)作于2023年2月信源序列長(zhǎng)度Ｌ的界限第42頁(yè)，課件共99頁(yè)，創(chuàng)作于2023年2月編碼效率第43頁(yè)，課件共99頁(yè)，創(chuàng)作于2023年2月編碼過(guò)程第44頁(yè)，課件共99頁(yè)，創(chuàng)作于2023年2月例5-2計(jì)算保證高效時(shí)Ｌ的數(shù)量級(jí)第45頁(yè)，課件共99頁(yè)，創(chuàng)作于2023年2月例5-2計(jì)算保證高效時(shí)Ｌ的數(shù)量級(jí)第46頁(yè)，課件共99頁(yè)，創(chuàng)作于2023年2月變長(zhǎng)無(wú)失真信源編碼定理第47頁(yè)，課件共99頁(yè)，創(chuàng)作于2023年2月單符號(hào)變長(zhǎng)編碼定理第48頁(yè)，課件共99頁(yè)，創(chuàng)作于2023年2月離散平穩(wěn)無(wú)記憶序列變長(zhǎng)編碼定理第49頁(yè)，課件共99頁(yè)，創(chuàng)作于2023年2月離散平穩(wěn)無(wú)記憶序列變長(zhǎng)編碼定理第50頁(yè)，課件共99頁(yè)，創(chuàng)作于2023年2月變長(zhǎng)無(wú)失真編碼的編碼效率第51頁(yè)，課件共99頁(yè)，創(chuàng)作于2023年2月例5-3變長(zhǎng)編碼的編碼效率第52頁(yè)，課件共99頁(yè)，創(chuàng)作于2023年2月例5-3變長(zhǎng)編碼的編碼效率第53頁(yè)，課件共99頁(yè)，創(chuàng)作于2023年2月例5-3變長(zhǎng)編碼的編碼效率第54頁(yè)，課件共99頁(yè)，創(chuàng)作于2023年2月比較例5-2定長(zhǎng)和變長(zhǎng)編碼的碼長(zhǎng)第55頁(yè)，課件共99頁(yè)，創(chuàng)作于2023年2月比較例5-3定長(zhǎng)和變長(zhǎng)編碼的碼長(zhǎng)第56頁(yè)，課件共99頁(yè)，創(chuàng)作于2023年2月信源編碼定理和方法編碼的定義和類型無(wú)失真編碼定理限失真編碼定理最佳變長(zhǎng)編碼方法常用信源編碼方法第57頁(yè)，課件共99頁(yè)，創(chuàng)作于2023年2月限失真信源編碼定理第58頁(yè)，課件共99頁(yè)，創(chuàng)作于2023年2月限失真信源編碼方法對(duì)于連續(xù)平穩(wěn)無(wú)記憶信源，雖然無(wú)法進(jìn)行無(wú)失真編碼，在限失真情況下，有與上述定理一樣的編碼定理。上述定理只能說(shuō)明最佳編碼是存在的，而具體的構(gòu)造方法卻一無(wú)所知。因而就不能象無(wú)損編碼那樣從證明過(guò)程中引出概率匹配的編碼方法，一般只能從優(yōu)化的思路去實(shí)現(xiàn)最佳編碼。第59頁(yè)，課件共99頁(yè)，創(chuàng)作于2023年2月信源編碼定理和方法編碼的定義和類型無(wú)失真編碼定理限失真編碼定理最佳變長(zhǎng)編碼方法常用信源編碼方法第60頁(yè)，課件共99頁(yè)，創(chuàng)作于2023年2月最佳變長(zhǎng)編碼方法最佳變長(zhǎng)碼：能載荷一定的信息量，且碼字的平均長(zhǎng)度最短，可分離的變長(zhǎng)碼的碼字集合稱為最佳變長(zhǎng)碼。特點(diǎn)：概率大的信息符號(hào)編以短碼；概率小的信息符號(hào)編以長(zhǎng)碼；第61頁(yè)，課件共99頁(yè)，創(chuàng)作于2023年2月香農(nóng)(Shannon)編碼方法第62頁(yè)，課件共99頁(yè)，創(chuàng)作于2023年2月例5-4演示Shannon編碼過(guò)程例5-4對(duì)以下的信源進(jìn)行單符號(hào)的二進(jìn)制香農(nóng)編碼第63頁(yè)，課件共99頁(yè)，創(chuàng)作于2023年2月例5-4演示Shannon編碼過(guò)程第64頁(yè)，課件共99頁(yè)，創(chuàng)作于2023年2月例5-4演示Shannon編碼過(guò)程第65頁(yè)，課件共99頁(yè)，創(chuàng)作于2023年2月費(fèi)諾(Fano)編碼方法第66頁(yè)，課件共99頁(yè)，創(chuàng)作于2023年2月例5-5對(duì)以下的信源進(jìn)行二進(jìn)制費(fèi)諾編碼例5-5演示Fano編碼過(guò)程第67頁(yè)，課件共99頁(yè)，創(chuàng)作于2023年2月例5-5演示Fano編碼過(guò)程第68頁(yè)，課件共99頁(yè)，創(chuàng)作于2023年2月哈夫曼(Huffman)編碼方法第69頁(yè)，課件共99頁(yè)，創(chuàng)作于2023年2月例5-6對(duì)以下的信源進(jìn)行二進(jìn)制Huffman編碼例5-6演示Huffman編碼過(guò)程第70頁(yè)，課件共99頁(yè)，創(chuàng)作于2023年2月例5-6演示Huffman編碼過(guò)程第71頁(yè)，課件共99頁(yè)，創(chuàng)作于2023年2月二進(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í)碼第72頁(yè)，課件共99頁(yè)，創(chuàng)作于2023年2月例5-７計(jì)算以下兩種Huffman編碼的碼長(zhǎng)方差第73頁(yè)，課件共99頁(yè)，創(chuàng)作于2023年2月例5-７計(jì)算以下兩種Huffman編碼的碼長(zhǎng)方差第74頁(yè)，課件共99頁(yè)，創(chuàng)作于2023年2月例5-8比較符號(hào)序列長(zhǎng)度對(duì)編碼效率的影響第75頁(yè)，課件共99頁(yè)，創(chuàng)作于2023年2月例5-8比較符號(hào)序列長(zhǎng)度對(duì)編碼效率的影響第76頁(yè)，課件共99頁(yè)，創(chuàng)作于2023年2月例5-8比較符號(hào)序列長(zhǎng)度對(duì)編碼效率的影響第77頁(yè)，課件共99頁(yè)，創(chuàng)作于2023年2月信源編碼定理和方法編碼的定義和類型無(wú)失真編碼定理限失真編碼定理最佳變長(zhǎng)編碼方法常用信源編碼方法第78頁(yè)，課件共99頁(yè)，創(chuàng)作于2023年2月常用信源編碼方法游程編碼算術(shù)編碼矢量量化（限失真壓縮編碼）預(yù)測(cè)編碼變換編碼第79頁(yè)，課件共99頁(yè)，創(chuàng)作于2023年2月游程編碼第80頁(yè)，課件共99頁(yè)，創(chuàng)作于2023年2月游程編碼第81頁(yè)，課件共99頁(yè)，創(chuàng)作于2023年2月游程編碼第82頁(yè)，課件共99頁(yè)，創(chuàng)作于2023年2月常用信源編碼方法游程編碼算術(shù)編碼矢量量化（限失真壓縮編碼）預(yù)測(cè)編碼變換編碼第83頁(yè)，課件共99頁(yè)，創(chuàng)作于2023年2月算術(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ù)編碼是一種非分組碼,序貫編譯碼第84頁(yè)，課件共99頁(yè)，創(chuàng)作于2023年2月算術(shù)編碼第85頁(yè)，課件共99頁(yè)，創(chuàng)作于2023年2月算術(shù)編碼第86頁(yè)，課件共99頁(yè)，創(chuàng)作于2023年2月例5-9演示算術(shù)編碼過(guò)程第87頁(yè)，課件共99頁(yè)，創(chuàng)作于2023年2月例5-9演示算術(shù)編碼過(guò)程第88頁(yè)，課件共99頁(yè)，創(chuàng)作于2023年2月例5-9演示算術(shù)編碼過(guò)程第89頁(yè)，課件共99頁(yè)，創(chuàng)作于2023年2月例5-9演示算術(shù)編碼過(guò)程第90頁(yè)，課件共99頁(yè)，創(chuàng)作于2023年2月例5-9演示算術(shù)譯碼過(guò)程第91頁(yè)，課件共99頁(yè)，創(chuàng)作于2023年2月常用信源編碼方法游程編碼算術(shù)編碼矢量量化（限失真壓縮編碼）預(yù)測(cè)編碼變換編碼第92頁(yè)，課件共99頁(yè)，創(chuàng)作于2023年2月矢量量化（限失真壓縮編碼）矢量量化用于壓縮幅度連續(xù),時(shí)間離散的數(shù)據(jù)矢量量化基于兩個(gè)事實(shí):(1)壓縮符號(hào)序列比壓縮單獨(dú)符號(hào)在原理上可產(chǎn)生更好的效果;(2)相鄰數(shù)據(jù)項(xiàng)(如圖象、聲音的樣本)也很少會(huì)差別很大.第93頁(yè)，課件共99頁(yè)，創(chuàng)作于2023年2月矢量量化（限失真壓縮編碼）基本思想矢量量化時(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è)索引.