信息論與編碼理論 第三章課件

第三章信源編碼（一）

離散信源無失真編碼第三章信源編碼（一）

離散信源無失真編碼13.1信源及其分類3.2離散無記憶信源的等長(zhǎng)編碼3.3離散無記憶信源的不等長(zhǎng)編碼3.4最佳不等長(zhǎng)編碼3.1信源及其分類23.1信源及其分類3.1信源及其分類3信源及其分類離散信源…U-2,U-1,U0,U1,U2,…，Ul取自字母表A無記憶信源:Ul彼此獨(dú)立有記憶信源：Ul彼此相關(guān)簡(jiǎn)單信源：Ul獨(dú)立同分布平穩(wěn)信源，各態(tài)歷經(jīng)源M階記憶源（有限狀態(tài)馬爾可夫鏈）連續(xù)信源時(shí)間離散連續(xù)源隨機(jī)波形源信源及其分類離散信源…U-2,U-1,U0,U1,U2,43.2離散無記憶源的等長(zhǎng)編碼3.2離散無記憶源的等長(zhǎng)編碼5離散無記憶源字母表A={a1,…,aK},概率p1,…,pK,長(zhǎng)為L(zhǎng)的源輸出序列uL={u1,…,uL}，共有KL種序列碼符號(hào)字母表B={b1,…,bD},以碼符號(hào)表示源輸出序列，D元碼等長(zhǎng)D元碼，不等長(zhǎng)D元碼單義可譯碼，每個(gè)消息都至少有一個(gè)碼字與之對(duì)應(yīng)。單義可譯碼存在充要條件DN≥KL

N≥LlogK/logD離散無記憶源字母表A={a1,…,aK},概率p1,…,pK6DMS的等長(zhǎng)編碼NlogD≥LH(U)H(U)是統(tǒng)計(jì)平均值，L達(dá)到無限時(shí)，一個(gè)具體的源輸出序列的平均每符號(hào)的信息量才等于H(U)選L足夠長(zhǎng)，使NlogD≥L[H(U)+eL]DMS的等長(zhǎng)編碼NlogD≥LH(U)7DMS序列的自信息量DMS序列的自信息量8弱、強(qiáng)e典型序列集弱、強(qiáng)e典型序列集9信源劃分定理典型序列集非典型序列集序列集合信源劃分定理典型序列集非典型序列集序列集合10典型序列的比例典型序列的比例11編碼速率和等長(zhǎng)編碼定理R=(1/L)logM=(N/L)logD,M為碼字總數(shù)定義：對(duì)于給定信源和編碼速率R以及任意e>0，若有L0,以及編譯碼方法，使得L>L0,錯(cuò)誤概率小于e，R是可達(dá)的等長(zhǎng)編碼定理R>H(U),R是可達(dá)的，R<H(U)是不可達(dá)的編碼效率=H(U)/R

編碼速率和等長(zhǎng)編碼定理R=(1/L)logM=(N/L)lo123.3DMS的不等長(zhǎng)編碼3.3DMS的不等長(zhǎng)編碼13平均碼長(zhǎng)平均碼長(zhǎng)14幾個(gè)定義唯一可譯碼逗點(diǎn)碼，無逗點(diǎn)碼字頭或前綴異字頭碼或異前綴碼樹碼，滿樹，非滿樹，全樹樹碼構(gòu)造異字頭碼幾個(gè)定義唯一可譯碼15例子信源字母集概率碼A碼B碼C碼Da1a2a3a40.50.250.1250.125001100100110101101110010110111例子信源字母集概率碼A碼B碼C碼Da10.5000016Shannon－Fano編碼D元碼每次信源符號(hào)化為概率近似相等的D個(gè)子集這樣可以保證D個(gè)碼元近似等概，每個(gè)碼字承載的信息量近似最大，碼就近似最短。理想情況I(ak)=nklogD,p(ak)=D-nkShannon－Fano編碼D元碼17Kraft不等式長(zhǎng)度為n1，n2，…，nK的D-元異字頭碼存在的充分必要條件是二元異字頭碼Kraft不等式等號(hào)成立定理:任意唯一可譯碼必滿足Kraft不等式Kraft不等式長(zhǎng)度為n1，n2，…，nK的D-元異字頭碼存18不等長(zhǎng)編碼定理編碼速率不等長(zhǎng)編碼定理編碼速率193.4最佳不等長(zhǎng)編碼3.4最佳不等長(zhǎng)編碼20Huffman編碼的最佳性所謂最佳：是指在所有可能的編碼方法中，其編碼得到的平均碼長(zhǎng)最短。定理3.4.1：對(duì)于給定信源，存在有最佳惟一可譯二元碼，其最小概率的兩個(gè)碼字CK-1和CK的長(zhǎng)度最長(zhǎng)且相等，它們之間僅最后一位碼元取值不同(一個(gè)為0，另一個(gè)為1)。Huffman編碼的最佳性所謂最佳：是指在所有可能的編碼方法21Huffman編碼的最佳性對(duì)信源可對(duì)aK-1和aK的碼字的最后一位分別指定為1和0，然后作一輔助集Huffman編碼的最佳性對(duì)信源22Huffman編碼的最佳性定理3.4.2對(duì)輔助集U

’為最佳的碼，對(duì)原始消息集U也是最佳的。若C’1，C’2，…，C’K-1是對(duì)輔助集U'的最佳碼，相應(yīng)碼長(zhǎng)為n’1，n’2，…，n’K-1，則對(duì)U的碼字C1，C2,…,CK的碼長(zhǎng)為nk=n’k

k≤K–2nk=n’K-1+1k=K,K–1Huffman編碼的最佳性定理3.4.2對(duì)輔助集U’為23Huffman編碼的最佳性

Huffman編碼的最佳性24例：Huffman編碼過程例：Huffman編碼過程25例：Huffman編碼過程例：Huffman編碼過程26Shannon-Fano編碼例子cabcedeacacdeddaaabaababaaabbacdebaceada共40個(gè)字母頻度a-16，b-7，c-6，d-6，e-51)將給定符號(hào)按照其頻率從大到小排序。a-16b-7c-6d-6e–52)將序列分成左右兩部分，使得左部頻率總和盡可能接近右部頻率總和。有：(a,b),(c,d,e)Shannon-Fano編碼例子cabcedeacacded27Shannon-Fano編碼例子3)我們把第二步中劃分出的上部作為二叉樹的左子樹，記0，下部作為二叉樹的右子樹，記1。4)分別對(duì)左右子樹重復(fù)23兩步，直到所有的符號(hào)都成為二叉樹的樹葉為止。bacde00101011a00b01c10d110e111Shannon-Fano編碼例子3)我們把第二步中劃分出的28Shannon-Fano編碼例子編碼結(jié)果Cabcedeacacdeddaaabaababaaabbacdebaceada1000011011111011100100010......長(zhǎng)91bit采用3bit等長(zhǎng)編碼需120bit采用ASCII碼需要320bitShannon-Fano編碼例子編碼結(jié)果29采用Huffman編碼a16b7c6d6e511132401010101a0b100c101d110e111總比特?cái)?shù)88，信源熵為86.601bit采用Huffman編碼a16b7c6d6e30Huffman編碼Shannon-Fano編碼構(gòu)造二叉樹是自樹根到樹葉，很難保證最佳性。Huffman編碼則是從樹葉到樹根，是最佳的Huffman編碼Shannon-Fano編碼構(gòu)造二叉樹是自31總結(jié)Huffman需要知道信源的概率分布，這在實(shí)際中有時(shí)是比較困難的。采用半靜態(tài)模型、自適應(yīng)模型、markov模型，部分匹配預(yù)測(cè)模型等等解決這一問題?？偨Y(jié)Huffman需要知道信源的概率分布，這在實(shí)際中有時(shí)是比32D元Huffman編碼共有K個(gè)符號(hào)，概率最小的R個(gè)符號(hào)碼長(zhǎng)最長(zhǎng)K+B=D+m(D-1)注意B<D-1K-2=m(D-1)+D-2-BB個(gè)R個(gè)B=D-2-((K-2)mod(D-1))R=2+((K-2)mod(D-1))D元Huffman編碼共有K個(gè)符號(hào)，概率最小的R個(gè)符號(hào)碼長(zhǎng)最33Shannon-Fano-Elias編碼累計(jì)分布函數(shù)修正累計(jì)分布函數(shù)Shannon-Fano-Elias編碼累計(jì)分布函數(shù)修正累計(jì)34Shannon-Fano-Elias編碼采用的數(shù)值作為ak的碼字碼長(zhǎng)Shannon-Fano-Elias編碼采用35Shannon-Fano-Elias編碼Shannon-Fano-Elias編碼36Shannon-Fano-Elias編碼信源符號(hào)P(ak)F(ak)修正值二進(jìn)制碼長(zhǎng)碼字a10.250.250.1250.0013001a20.50.750.50.10210a30.1250.8750.81250.110141101a40.1251.00.93750.111141111Shannon-Fano-Elias編碼信源符號(hào)P(ak)F37算術(shù)碼應(yīng)用于JPEG2000,H.263等圖像壓縮標(biāo)準(zhǔn)算術(shù)碼應(yīng)用于JPEG2000,H.263等圖像壓縮標(biāo)準(zhǔn)38算術(shù)碼信源序列(u1u2…un)的累計(jì)分布算術(shù)編碼是計(jì)算序列的累計(jì)分布，用累計(jì)分布值表示序列，所以稱為算術(shù)編碼以二元信源輸出序列的編碼為例01110P(0)P(1)F(0)F(1)01算術(shù)碼信源序列(u1u2…un)的累計(jì)分布P(0)P(1)F39算術(shù)碼P(00)P(01)F(0)F(01)F(1)P(010)P(011)F(011)P(0110)P(0111)F(0111)P(01110)P(01111)F(01111)算術(shù)碼P(00)P(01)F(0)F(01)F(1)P(0140算術(shù)碼信源符號(hào)序列u對(duì)應(yīng)區(qū)間的寬度等于符號(hào)序列的概率算術(shù)碼信源符號(hào)序列u對(duì)應(yīng)區(qū)間的寬度等于符號(hào)序列的概率41算術(shù)編碼F(u)將[0,1)分割成許多小區(qū)間，取小區(qū)間內(nèi)的一個(gè)點(diǎn)代表該序列，以該點(diǎn)數(shù)值的二進(jìn)制小數(shù)表示該序列，碼字長(zhǎng)度為算術(shù)編碼F(u)將[0,1)分割成許多小區(qū)間，取小區(qū)間內(nèi)的一42算術(shù)編碼算術(shù)編碼43例：P(0)=0.25,P(1)=0.75,u=11111100P(u=11111100)=0.7560.252L=7F(s)=0.110100100111C=1101010編碼效率92.7%例：P(0)=0.25,P(1)=0.75,u=1111144LZ編碼利用字典編碼方法信源符號(hào)A=(a1…aK)將序列分為不同的段取最短長(zhǎng)度的連續(xù)符號(hào)構(gòu)成段，保證互不相同。先取一個(gè)符號(hào)分段，若與前面段相同，就再取一個(gè)符號(hào)，直至序列結(jié)束得到字典表，碼字由段號(hào)加后一個(gè)符號(hào)組成。單符號(hào)的碼字，段號(hào)為0LZ編碼利用字典編碼方法45LZ編碼符號(hào)碼字a0a1a2a300011011LZ編碼符號(hào)碼字a00046LZ編碼00000001100001100001100000010001110

1234567LZ編碼000000011000011000011047LZ編碼設(shè)長(zhǎng)為L(zhǎng)的信源序列u分為M(u)個(gè)碼段，每段短語的二元碼符號(hào)長(zhǎng)度為總碼長(zhǎng)平均+LZ編碼設(shè)長(zhǎng)為L(zhǎng)的信源序列u分為M(u)個(gè)碼段，每段短語的二48LZ編碼設(shè)長(zhǎng)度為l段有Kl種。若把長(zhǎng)為L(zhǎng)的信源序列u分為M(u)個(gè)碼段后，設(shè)最長(zhǎng)的段長(zhǎng)為lmax，而且所有小于等于lmax的段型全部都有，則LZ編碼設(shè)長(zhǎng)度為l段有Kl種。若把長(zhǎng)為L(zhǎng)的信源序列u分為M(49LZ編碼典型段，ak出現(xiàn)的次數(shù)為lmaxp(ak)LZ編碼典型段，ak出現(xiàn)的次數(shù)為lmaxp(ak)50LZ編碼設(shè)較短的段型忽略不計(jì)LZ編碼設(shè)較短的段型忽略不計(jì)51第三章信源編碼（一）

離散信源無失真編碼第三章信源編碼（一）

離散信源無失真編碼523.1信源及其分類3.2離散無記憶信源的等長(zhǎng)編碼3.3離散無記憶信源的不等長(zhǎng)編碼3.4最佳不等長(zhǎng)編碼3.1信源及其分類533.1信源及其分類3.1信源及其分類54信源及其分類離散信源…U-2,U-1,U0,U1,U2,…，Ul取自字母表A無記憶信源:Ul彼此獨(dú)立有記憶信源：Ul彼此相關(guān)簡(jiǎn)單信源：Ul獨(dú)立同分布平穩(wěn)信源，各態(tài)歷經(jīng)源M階記憶源（有限狀態(tài)馬爾可夫鏈）連續(xù)信源時(shí)間離散連續(xù)源隨機(jī)波形源信源及其分類離散信源…U-2,U-1,U0,U1,U2,553.2離散無記憶源的等長(zhǎng)編碼3.2離散無記憶源的等長(zhǎng)編碼56離散無記憶源字母表A={a1,…,aK},概率p1,…,pK,長(zhǎng)為L(zhǎng)的源輸出序列uL={u1,…,uL}，共有KL種序列碼符號(hào)字母表B={b1,…,bD},以碼符號(hào)表示源輸出序列，D元碼等長(zhǎng)D元碼，不等長(zhǎng)D元碼單義可譯碼，每個(gè)消息都至少有一個(gè)碼字與之對(duì)應(yīng)。單義可譯碼存在充要條件DN≥KL

N≥LlogK/logD離散無記憶源字母表A={a1,…,aK},概率p1,…,pK57DMS的等長(zhǎng)編碼NlogD≥LH(U)H(U)是統(tǒng)計(jì)平均值，L達(dá)到無限時(shí)，一個(gè)具體的源輸出序列的平均每符號(hào)的信息量才等于H(U)選L足夠長(zhǎng)，使NlogD≥L[H(U)+eL]DMS的等長(zhǎng)編碼NlogD≥LH(U)58DMS序列的自信息量DMS序列的自信息量59弱、強(qiáng)e典型序列集弱、強(qiáng)e典型序列集60信源劃分定理典型序列集非典型序列集序列集合信源劃分定理典型序列集非典型序列集序列集合61典型序列的比例典型序列的比例62編碼速率和等長(zhǎng)編碼定理R=(1/L)logM=(N/L)logD,M為碼字總數(shù)定義：對(duì)于給定信源和編碼速率R以及任意e>0，若有L0,以及編譯碼方法，使得L>L0,錯(cuò)誤概率小于e，R是可達(dá)的等長(zhǎng)編碼定理R>H(U),R是可達(dá)的，R<H(U)是不可達(dá)的編碼效率=H(U)/R

編碼速率和等長(zhǎng)編碼定理R=(1/L)logM=(N/L)lo633.3DMS的不等長(zhǎng)編碼3.3DMS的不等長(zhǎng)編碼64平均碼長(zhǎng)平均碼長(zhǎng)65幾個(gè)定義唯一可譯碼逗點(diǎn)碼，無逗點(diǎn)碼字頭或前綴異字頭碼或異前綴碼樹碼，滿樹，非滿樹，全樹樹碼構(gòu)造異字頭碼幾個(gè)定義唯一可譯碼66例子信源字母集概率碼A碼B碼C碼Da1a2a3a40.50.250.1250.125001100100110101101110010110111例子信源字母集概率碼A碼B碼C碼Da10.5000067Shannon－Fano編碼D元碼每次信源符號(hào)化為概率近似相等的D個(gè)子集這樣可以保證D個(gè)碼元近似等概，每個(gè)碼字承載的信息量近似最大，碼就近似最短。理想情況I(ak)=nklogD,p(ak)=D-nkShannon－Fano編碼D元碼68Kraft不等式長(zhǎng)度為n1，n2，…，nK的D-元異字頭碼存在的充分必要條件是二元異字頭碼Kraft不等式等號(hào)成立定理:任意唯一可譯碼必滿足Kraft不等式Kraft不等式長(zhǎng)度為n1，n2，…，nK的D-元異字頭碼存69不等長(zhǎng)編碼定理編碼速率不等長(zhǎng)編碼定理編碼速率703.4最佳不等長(zhǎng)編碼3.4最佳不等長(zhǎng)編碼71Huffman編碼的最佳性所謂最佳：是指在所有可能的編碼方法中，其編碼得到的平均碼長(zhǎng)最短。定理3.4.1：對(duì)于給定信源，存在有最佳惟一可譯二元碼，其最小概率的兩個(gè)碼字CK-1和CK的長(zhǎng)度最長(zhǎng)且相等，它們之間僅最后一位碼元取值不同(一個(gè)為0，另一個(gè)為1)。Huffman編碼的最佳性所謂最佳：是指在所有可能的編碼方法72Huffman編碼的最佳性對(duì)信源可對(duì)aK-1和aK的碼字的最后一位分別指定為1和0，然后作一輔助集Huffman編碼的最佳性對(duì)信源73Huffman編碼的最佳性定理3.4.2對(duì)輔助集U

’為最佳的碼，對(duì)原始消息集U也是最佳的。若C’1，C’2，…，C’K-1是對(duì)輔助集U'的最佳碼，相應(yīng)碼長(zhǎng)為n’1，n’2，…，n’K-1，則對(duì)U的碼字C1，C2,…,CK的碼長(zhǎng)為nk=n’k

k≤K–2nk=n’K-1+1k=K,K–1Huffman編碼的最佳性定理3.4.2對(duì)輔助集U’為74Huffman編碼的最佳性

Huffman編碼的最佳性75例：Huffman編碼過程例：Huffman編碼過程76例：Huffman編碼過程例：Huffman編碼過程77Shannon-Fano編碼例子cabcedeacacdeddaaabaababaaabbacdebaceada共40個(gè)字母頻度a-16，b-7，c-6，d-6，e-51)將給定符號(hào)按照其頻率從大到小排序。a-16b-7c-6d-6e–52)將序列分成左右兩部分，使得左部頻率總和盡可能接近右部頻率總和。有：(a,b),(c,d,e)Shannon-Fano編碼例子cabcedeacacded78Shannon-Fano編碼例子3)我們把第二步中劃分出的上部作為二叉樹的左子樹，記0，下部作為二叉樹的右子樹，記1。4)分別對(duì)左右子樹重復(fù)23兩步，直到所有的符號(hào)都成為二叉樹的樹葉為止。bacde00101011a00b01c10d110e111Shannon-Fano編碼例子3)我們把第二步中劃分出的79Shannon-Fano編碼例子編碼結(jié)果Cabcedeacacdeddaaabaababaaabbacdebaceada1000011011111011100100010......長(zhǎng)91bit采用3bit等長(zhǎng)編碼需120bit采用ASCII碼需要320bitShannon-Fano編碼例子編碼結(jié)果80采用Huffman編碼a16b7c6d6e511132401010101a0b100c101d110e111總比特?cái)?shù)88，信源熵為86.601bit采用Huffman編碼a16b7c6d6e81Huffman編碼Shannon-Fano編碼構(gòu)造二叉樹是自樹根到樹葉，很難保證最佳性。Huffman編碼則是從樹葉到樹根，是最佳的Huffman編碼Shannon-Fano編碼構(gòu)造二叉樹是自82總結(jié)Huffman需要知道信源的概率分布，這在實(shí)際中有時(shí)是比較困難的。采用半靜態(tài)模型、自適應(yīng)模型、markov模型，部分匹配預(yù)測(cè)模型等等解決這一問題?？偨Y(jié)Huffman需要知道信源的概率分布，這在實(shí)際中有時(shí)是比83D元Huffman編碼共有K個(gè)符號(hào)，概率最小的R個(gè)符號(hào)碼長(zhǎng)最長(zhǎng)K+B=D+m(D-1)注意B<D-1K-2=m(D-1)+D-2-BB個(gè)R個(gè)B=D-2-((K-2)mod(D-1))R=2+((K-2)mod(D-1))D元Huffman編碼共有K個(gè)符號(hào)，概率最小的R個(gè)符號(hào)碼長(zhǎng)最84Shannon-Fano-Elias編碼累計(jì)分布函數(shù)修正累計(jì)分布函數(shù)Shannon-Fano-Elias編碼累計(jì)分布函數(shù)修正累計(jì)85Shannon-Fano-Elias編碼采用的數(shù)值作為ak的碼字碼長(zhǎng)Shannon-Fano-Elias編碼采用86Shannon-Fano-Elias編碼Shannon-Fano-Elias編碼87Shannon-Fano-Elias編碼信源符號(hào)P(ak)F(ak)修正值二進(jìn)制碼長(zhǎng)碼字a10.250.250.1250.0013001a20.50.750.50.10210a30.1250.8750.81250.110141101a40.1251.00.93750.111141111Shannon-Fano-Elias編碼信源符號(hào)P(ak)F88算術(shù)碼應(yīng)用于JPEG2000,H.263等圖像壓縮標(biāo)準(zhǔn)算術(shù)碼應(yīng)用于JPEG2000,H.263等圖像壓縮標(biāo)準(zhǔn)89算術(shù)碼信源序列(u1u2…un)的累計(jì)分布算術(shù)編碼是計(jì)算序列的累計(jì)分布，用累計(jì)分布值表示序列，所以稱為算術(shù)編碼以二元信源輸出序列的編碼為例01110P(0)P(1)F(0)F(1)01算術(shù)碼信源序列(u1u2…un)的累計(jì)分布P(0)P(1)F90算術(shù)碼P(00)P(01)F(0)F(01)F(1)P(010)P(011)F(011)P(0110)P(0111)F(0111)P(01110)P(01111)F(01111)算