第3章 無失真信源編碼

1、信信 息息 論論Information TheoryInformation Theory哈爾濱工程大學哈爾濱工程大學 2013 王逸林王逸林 Tel: 82519503E-mail: 第第3章章 無失真信源編碼無失真信源編碼o3.1 信源編碼相關概念信源編碼相關概念o3.2 等長碼及等長碼編碼定理等長碼及等長碼編碼定理o3.3 變長碼及變長碼編碼定理變長碼及變長碼編碼定理o3.4 變長編碼方法變長編碼方法o3.5 實用的無失真信源編碼方法實用的無失真信源編碼方法 信源信源對于信源來說有對于信源來說有3個重要的問題需要解決：個重要的問題需要解決：u 1、構造描述信源的模型；、構造描述信源的模型；

2、u 2、計算信源輸出的信息量、計算信源輸出的信息量/信源熵；信源熵；u 3、有效地描述信源輸出、有效地描述信源輸出信源壓縮編碼問題。信源壓縮編碼問題。 無失真信源編碼無失真信源編碼u 若要求能從經(jīng)過壓縮編碼后的碼字序列精確地、無差若要求能從經(jīng)過壓縮編碼后的碼字序列精確地、無差錯地恢復出原來信源的輸出消息，則稱這種編碼是無錯地恢復出原來信源的輸出消息，則稱這種編碼是無失真的，這時的信源編碼就是無失真信源編碼。失真的，這時的信源編碼就是無失真信源編碼。3.1信源編碼相關概念信源編碼相關概念信 源信源編碼信道編碼信 道信 宿信源譯碼信道譯碼編碼器編碼器編碼實質(zhì)上是對信源的原始符號按一定的數(shù)學編碼實質(zhì)

3、上是對信源的原始符號按一定的數(shù)學規(guī)則進行的一種變換！規(guī)則進行的一種變換！信源編碼信源編碼u當研究信源編碼時， 將信道編碼和譯碼看成是信道的一部分；u當研究信道編碼時， 將信源編碼和譯碼看成是信源和信宿的一部分.信源編碼信源編碼1. 信源適合信道傳輸2. 無失真?zhèn)鬏?. 提高傳輸效率減少信源的剩余度基本術語基本術語,.,:21nsssS,.,:21rxxxX,.,:21nWWWC信源輸入符號信源輸入符號碼符號集碼符號集碼字集合碼字集合 代碼組代碼組C碼符號集中的元素是適碼符號集中的元素是適合信道傳輸?shù)暮闲诺纻鬏數(shù)木幋a器,21nsssSLL=,21rxxxXLL=,21nWWWCLL=基本術語基本

4、術語信源符號信源符號 變換成由碼符號變換成由碼符號 組成組成的長度為的長度為 的一一對應的輸出符號的一一對應的輸出符號序列序列isjxiWilil),.2 , 1(),.2 , 1(.21iiiiiilkXxqixxxWkil=長度長度 稱為碼字長度或簡稱碼長稱為碼字長度或簡稱碼長 信源編碼就是從信源符號到輸出碼符號的一種映射信源編碼就是從信源符號到輸出碼符號的一種映射 若要實現(xiàn)無失真編碼，則這種映射必須是一一對應的、若要實現(xiàn)無失真編碼，則這種映射必須是一一對應的、可逆的可逆的1. 二元碼二元碼 碼的符號集為0和1，碼字都是一些二元序列，則稱為二元碼。2. 等長碼等長碼 一組碼中所有的碼字的碼

5、長都相同，則稱為等長碼3. 變長碼變長碼 一組碼中的碼字的碼長各不相同，則稱為變長碼有關碼的定義有關碼的定義4. 同價碼同價碼 若符號集中每個符號所占的傳輸時間都相同，所得的碼稱為同價碼5. 非奇異碼非奇異碼 組碼中所有的碼字都不相同，即所有的信源符號都映射到不同的碼符號序列。有關碼的定義有關碼的定義jijiWWss6. 奇異碼奇異碼 組碼中有相同的碼字。jijiWWss=7. 碼的碼的N次擴展碼次擴展碼),.,2 , 1(),.,2 , 1(qiwqisii=碼碼C C的的N N次擴展碼是次擴展碼是N N個碼字組成的碼字序列的集合個碼字組成的碼字序列的集合N次擴展碼：次擴展碼：NNiiiiq

6、iqiiiWWWBBN,.,2 , 1;, 2 , 1,.,).(2121=N次擴展碼次擴展碼B中，每個碼字中，每個碼字 與與N次擴展信源次擴展信源 中每個信中每個信源符號序列源符號序列 一一對應。一一對應。 iBNS),.,2 , 1;, 2 , 1,.,)(.(2121NNiiiiqiqiiisssN=8. 單義可譯（又稱惟一可譯碼）單義可譯（又稱惟一可譯碼）物理含義：若碼的任意一串有限長的碼符號序列只能被惟一地譯成若碼的任意一串有限長的碼符號序列只能被惟一地譯成所對應的信源符號序列，則此碼為惟一可譯碼。即：所對應的信源符號序列，則此碼為惟一可譯碼。即： 一個分組碼對于任意有限的整數(shù)一個分

7、組碼對于任意有限的整數(shù)NN，其，其NN階擴展碼均為階擴展碼均為非奇異的非奇異的不僅要求不同的碼字表示不同的信源符號，而且還進一不僅要求不同的碼字表示不同的信源符號，而且還進一步要求對由信源符號構成的消息序列進行編碼時，在接步要求對由信源符號構成的消息序列進行編碼時，在接收端仍能正確譯碼，而不發(fā)生混淆。收端仍能正確譯碼，而不發(fā)生混淆。9.即時碼（非繼長碼）即時碼（非繼長碼） 任何一個碼字不是另一個碼字的繼長。也就是說，不能再一個碼字后面加上一些碼元構成其他碼字。非繼長碼一定是單義可譯碼惟一可譯碼成為即時碼的惟一可譯碼成為即時碼的充要條件充要條件 是其中任何一個碼字都不是其他碼字的是其中任何一個碼

8、字都不是其他碼字的前綴前綴惟一可譯碼不一定是即時碼惟一可譯碼不一定是即時碼 即時碼一定是惟一可譯碼即時碼一定是惟一可譯碼10.樹碼樹碼 終端節(jié)點所對應的碼字由從根出發(fā)到終端節(jié)點走過的路徑所對應的碼符號組成。 樹碼一定是即時碼；任一即時碼都可用樹碼圖法來表示樹碼一定是即時碼；任一即時碼都可用樹碼圖法來表示樹枝數(shù)目等于碼符號數(shù)樹枝數(shù)目等于碼符號數(shù)r二元碼樹二元碼樹三元碼樹三元碼樹例1：1101104321ssss1s3s2s4s奇異碼奇異碼01001004321ssss非奇異碼非奇異碼0 1 0 0 0 0 1 014321sssss0 1 0 0 0 0 1 02334ssss例2：非惟一可譯碼

9、非惟一可譯碼例3：111001004321ssss等長碼等長碼非奇異碼非奇異碼0 0 0 1 1 0 1 14321ssss單義可譯單義可譯例4：10001001014321ssss非奇異碼非奇異碼1 1 0 1 0 0 1 0 0 0單義可譯單義可譯1 0?2s01不即時不即時任何一個碼字是其它碼字的延長或前綴任何一個碼字是其它碼字的延長或前綴?3s不即時不即時例5： 00010010114321ssss非奇異碼非奇異碼1 0 1 0 0 1 0 0 0 1單義可譯單義可譯0 12s即時任何一個碼字不是其它碼字的延長或前綴即即 時時 碼碼3.2 離散無記憶信源的離散無記憶信源的 等長編碼等長

10、編碼編碼定理編碼定理編碼定理研究的問題編碼定理研究的問題1為了不失真的恢復信源的信息，對理想信道所需的最小信息率是多少？ 信源編碼定理2為了不失真的恢復信源的信息，對給定信道容量，能夠傳輸?shù)淖畲笮畔⒙适嵌嗌伲?信道編碼定理無失真的信源編碼，所編的碼必須是一一對應的無失真的信源編碼，所編的碼必須是一一對應的 反變換正變換等長編碼等長編碼o 對于等長碼來說，若等長碼是非奇異碼，則它對于等長碼來說，若等長碼是非奇異碼，則它的任意有限長的任意有限長N N次擴展碼一定也是非奇異碼次擴展碼一定也是非奇異碼 等長非奇異碼一定是惟一可譯碼等長非奇異碼一定是惟一可譯碼信源信源S 存在惟一可譯等長碼的條件是：存在

11、惟一可譯等長碼的條件是： lrq q為信源為信源S的符號個數(shù)，的符號個數(shù)，r 是碼符號個數(shù)，是碼符號個數(shù)，l 是等長碼的碼長是等長碼的碼長 等長編碼等長編碼o 信源信源S 的的N 次擴展信源次擴展信源 進行等長編碼，存在進行等長編碼，存在惟一可譯碼的條件：惟一可譯碼的條件：lNrq取對數(shù)解得： NS碼符號序列數(shù)碼符號序列數(shù) 擴展信源符號數(shù)擴展信源符號數(shù) rqNlloglog平均每個信源符號所需要的碼符號個數(shù)平均每個信源符號所需要的碼符號個數(shù) 若若N=1 rqlloglog當當r=2 qNllogo 例1：英文電報有32個符號（26個英文字母加上6個標點符號），即q=32，若采用二元碼時，則r=

12、2。對信源S的逐個符號si，i=1，232進行二元等長無失真編碼，求碼長l。例例：設有一離散無記憶信源碼符號120.90.1Sssp=1 11 22 12 20.810.090.090.01Ss ss ss ss sp=1 1 11 2 12 1 12 2 11 1 21 2 22 1 22 2 20.7290.0810.0810.0090.0810.0090.0090.001Ss s ss s ss s ss s ss s ss s ss s ss s sp=漸近等分性o 當隨機變量的序列足夠長時，其中一部分序列就顯現(xiàn)出一種典型的性質(zhì)：這些序列中各個符號的出現(xiàn)頻率非常接近于各自的出現(xiàn)概率，而

13、這些序列的概率則趨近于相等，且它們的和非常接近于1，這些序列就稱為典型序列。o 其余的稱為非典型序列，其出現(xiàn)概率之和接近于零。o 序列的長度越長，典型序列的總概率越接近于1，它的各個序列的出現(xiàn)概率越趨于相等。非典型序列的出現(xiàn)概率之和越接近于零。漸近等分性即因此得名。 定理定理3.1 等長編碼定理等長編碼定理 o 一個熵為H(S)的離散無記憶信源，若對信源的N次擴展信源進行等長編碼，設碼字從r個字母的碼符號集中選取l 個碼元組成。只要滿足：0log)(任意rsHNl 則當N足夠大時，可以實現(xiàn)幾乎無失真的編碼，即譯碼錯誤概率能為任意小。反之，若0log2)(任意rsHNl 則不能實現(xiàn)無失真編碼，當

14、N為足夠大時，譯碼的錯誤概率近似等于1，不可能實現(xiàn)無失真編碼。定理給出了等長編碼時平均每個信源符號所需的碼符號的理論極限！定理給出了等長編碼時平均每個信源符號所需的碼符號的理論極限！ 定理定理3.1 等長編碼定理等長編碼定理 o 定理3.1改寫)(logSNHrl信源序列平均攜帶的信息量信源序列平均攜帶的信息量 只要碼字傳輸?shù)男畔⒘看笥谛旁葱蛄袛y帶的信息量，總可實現(xiàn)幾乎無失真編碼！只要碼字傳輸?shù)男畔⒘看笥谛旁葱蛄袛y帶的信息量，總可實現(xiàn)幾乎無失真編碼！ 長為長為l 的碼符號序列能載荷的最大信息量的碼符號序列能載荷的最大信息量 o 幾個基本概念幾個基本概念 （1）編碼信息率（信源輸出率）：符號比特

15、/log rNlR =。所能攜帶的最大信息量編碼后平均一個源字母能攜帶的信息量。編碼后平均一個源字所的信息量或平均一個碼字所能攜帶帶的信息量。平均一個碼字母所能攜:log:log:logNrlrlr)()(logSNHNSNHrl)(logXHrNl碼字能攜帶的信息量源字能攜帶的信息量注：實現(xiàn)無失真編碼注：實現(xiàn)無失真編碼（2）編碼效率： rNlSHRSHlog)()(=12)(),(NsIDNpiE= 理想的編碼器 ，代價！錯誤概率錯誤概率： 等長編碼效率：等長編碼效率： 0)()(=SHSH)(isID當自信息方差當自信息方差 和和 均為定值時，只要均為定值時，只要N N足夠大，錯誤概率就可

16、小于任一正數(shù)足夠大，錯誤概率就可小于任一正數(shù))(1SH=222)1 ()()(SHsIDNi=iiiiSHppsID)()(log)(22例：編碼效率為 若設譯碼差錯率為則 容許錯誤概率越小，編碼效率越高，容許錯誤概率越小，編碼效率越高，則信源序列長度則信源序列長度N必須越長必須越長 0)()(=SHSHo定長編碼的不足：要求定長編碼的不足：要求N很大，不實用很大，不實用=04. 005. 006. 007. 010. 010. 018. 040. 0)(87654321aaaaaaaaxpX28. 090. 0)()(=XHXH82. 7)(,/55. 2)(2=XbitXH符號810922

17、2107 . 9)1 ()()(XHxIDNi 存儲和處理難度大。存儲和處理難度大。 解決辦法：采用變長編碼。解決辦法：采用變長編碼。（3） 為性能極限)(SH：臨界狀態(tài)：不可能：無失真)()()()(SHRSHRSHRSHo 證明信源冗余度的可壓縮性無失真數(shù)據(jù)壓縮證明信源冗余度的可壓縮性無失真數(shù)據(jù)壓縮的理論的理論o 極限：信源的信息熵。壓縮到小于這個極限極限：信源的信息熵。壓縮到小于這個極限值，無失真做不到。值，無失真做不到。 定長編碼的意義定長編碼的意義3.3離散無記憶信源的變長編碼離散無記憶信源的變長編碼o 優(yōu)點：優(yōu)點：往往在N不很大的情況下就可以編出效率很高且無失真的信源編碼。o 變長

18、碼不但要求碼本身非奇異，其N次擴展也要是非奇異的，且為了即時進行譯碼，變長碼還必須是即時碼。離散無記憶信源的變長編碼信源編碼有以下3種主要方法：o 匹配編碼 根據(jù)編碼對象的概率分布，給予不同長度的代碼。o 變換編碼 從一種信號空間變換為另一種信號空間，然后針對變換后的信號進行編碼。o 識別編碼 主要用于印刷或打字機等有標準形狀的文字、符號和數(shù)據(jù)的編碼。唯一可譯定理（克拉夫特和麥克米倫不等式）定理定理：設信源S的符號集為S：s1,s2,sq，碼符號集X:x1,x2,xr，又設碼字為W:w1,w2,wq其碼長分別為l1,l2,lq。則存在存在即時碼即時碼（唯一可譯唯一可譯碼碼麥克米倫不等式麥克米倫

19、不等式）的充分必要條件是）的充分必要條件是：q，r，li(i=1,2,q)滿足Kraft不等式，即：=qilir11描述的是：關于信源符號數(shù)和碼字長度之間描述的是：關于信源符號數(shù)和碼字長度之間應滿足什么條件才能構成唯一可譯碼。應滿足什么條件才能構成唯一可譯碼。o 例3，設有信源S，符號數(shù)6，將此信源編碼為r元唯一可譯變長碼，其對應碼長為(l1,l2,l6)=(1,1,2,3,2,3),求r值的最小下限。=qilir11唯一可譯碼判斷準則o 由薩得納斯和彼得森于1957年設計出來的。d設S0為原始碼字集合。再構造一系列集合S1，S2，。若要構成S1，則分析S0 中所有碼字，若Wj 是Wi 前綴，

20、即Wi = Wj A ，則A為S1 中元素。d若要構成Sn，n1,則將S0與Sn-1進行比較，若碼字WS0，且W是USn-1的前綴，即U=WA，則取A為Sn中的元素。同樣，若有碼字USn-1是WS0的前綴，即W=UA，則后綴A亦為Sn中的元素。如此構成集合Sn。依次下去，直至集合為空或者沒有新的后綴產(chǎn)生為止。d一種碼是唯一可譯碼的條件是S1，S2，中沒有一個含有S0中的碼字。S0S1S2S3S4S5S6adebdebaddcbbcdebcdeadSn已沒有新的后綴（n5）abbcdebada bbcde badabb c deb ad abbbaddebbbcdeS0S1S2110001110

21、00010消息pABCDEFa11/2000000001a21/4001011010010100a31/160100111101101100101a41/160110111111011101101110a51/16100011111111010111110111a61/1610101111111111011011111011例例1：判斷下列各碼的類型。：判斷下列各碼的類型。 設 N 個碼字中的第 i個碼字的碼長為li，它所代表的編碼對象 si 的出現(xiàn)的概率為 p(si)，則碼字的平均長度為：變長編碼定理iqiilspL=1)(表示每個信源符號平均需要的碼符號個數(shù)。單位：碼符號/信源符號o 編碼

22、后平均每個碼元攜帶的信息量即信道為： 可見，平均碼長越短，R越大，信息傳輸率越高。 對于某一唯一可譯碼，若其平均碼長小于所有其它唯一可譯碼，則稱該碼為緊致碼緊致碼，或稱最佳碼最佳碼。無失真編碼的核心問題就是尋找緊致碼。 LSHXHR=比特/碼符號 定理3.4 對于熵為H(S)的離散無記憶信源若用具有r個碼元的碼符號集X對信源進行編碼，則一定存在一種無失真編碼方法，構成唯一可譯存在一種無失真編碼方法，構成唯一可譯碼，碼，使其平均碼長滿足： 該定理指出碼字的平均長度不能小于極限平均長度不能小于極限值，否則唯一可譯碼不存在值，否則唯一可譯碼不存在。同時也給出了平均碼長的上界，但不是說大于上界就不存在

23、唯一可譯碼了，只是我們希望找到的碼盡可能短。1log)(log)(rsHLrsH變長無失真編碼定理變長無失真編碼定理 一個熵為H(S)的離散無記憶信源，若對該信源的N次擴展信源用r進制的符號進行變長編碼，一定存在一種編碼方法，使信源S中的每個信源符號所需的平均碼長滿足下式： rsHNlNrsHNlog)(1log)(也稱為香農(nóng)第一定理變長無失真編碼定理變長無失真編碼定理 變長碼無失真編碼每個信源符號所需的最小碼長要大于等于信源熵（r進制）。也就是說1bit的碼最多攜帶1bit的信息)(log)(sHrsHNlrNN=：o 表示編碼后平均每個信源符號所能載荷的最大信息量。表示編碼后平均每個信源符

24、號所能載荷的最大信息量。于是定理3.5有可寫為：o 當平均碼長達到極限值 時，可得編碼后的信道為：o 可見此時信道的信息率等于無噪無損信道的信息傳輸率。信源編碼實質(zhì)是為了使信道信息傳輸率達到信道容量。 SHRSHrSHlog/ )( rLSHRlog=rLNrLRNloglog= 無失真信源編碼定理是為了在無失真意義下實在無失真意義下實現(xiàn)通信系統(tǒng)與信源統(tǒng)計特性相匹配現(xiàn)通信系統(tǒng)與信源統(tǒng)計特性相匹配：即當系統(tǒng)中編碼速率RH(s) (信源熵)時，最優(yōu)的信源編、譯碼存在；反之，當RH(s)時，最優(yōu)信源編、譯碼不存在。稱它為Shannon編碼第一定理。o 對信源S進行編碼，定義編碼效率：o 碼的剩余度：

25、o 信息傳輸率： LsHRsHr=/ )(=1 LsHR =對于無噪無損信道有=R指是數(shù)值相等，單位是不同的。例例2：設有一離散無記憶信源：其信源熵為： 用二元碼符號(0,1)來構造一個即時碼：S10，s21此時平均碼長為： 碼符號/信源符號則編碼效率為：信道傳輸率為：R=0.811比特/二元碼符號信源符號）/(811. 0log)(21bitppSHiii=4/14/321sspS1=L 811. 0=LsH為了提高傳輸效率，根據(jù)香農(nóng)第一定理的概念，對信源S的二次擴展信源S2進行編碼，即時碼如下：平均碼長 二元碼符號/二個信源符號信源中每單個符號的平均碼長為 二元碼符號/信源符號二次擴展信源

26、的信源符號概率p即時碼s1s19/161s1s23/1601s2s13/16001s2s21/16000162731693163216311692=L322722=LL則編碼效率為：信道傳輸率為：R=0.961比特/二元碼符號 961. 0=LsH定長編碼與變長編碼效率比較：| 相比： 同一個信源，當要求編碼效率達到96時，| 等長碼需要4100萬個信源符號聯(lián)合編碼；| 變長碼只需2個信源符號（二次擴展信源）聯(lián)合編碼；| 結(jié)論：采用變長編碼，平均碼長不需要很大就可以達到相當高的編碼效率，而且可以實現(xiàn)無失真編碼。且隨著平均碼長的增大，編碼效率越來越接近于1。最佳編碼凡是能載荷一定信息量， 平均碼

27、長最短， 可分離的， 變長碼的碼集o 可分離接收端能分開(即時碼)o 關鍵平均碼長最短o大概率短碼o小概率長碼o碼長信源統(tǒng)計特性匹配3.4變長編碼方法3.4變長編碼方法o 香農(nóng)編碼o 費諾編碼o 霍夫曼編碼香農(nóng)第一定理指出，選擇每個碼字長度 使之滿足：的整數(shù)，就可以得到唯一可譯碼，這種編碼方法稱為香農(nóng)編碼，它可使得平均碼長不超過上界，但不一定最短，即不一定是緊致碼。log( )log()1riirip slp s il1log)(log)(rSHLrSH編碼步驟如下：編碼步驟如下：將信源符號按概率從大到小順序排列，為方便起見，令將信源符號按概率從大到小順序排列，為方便起見，令 2. 按下式計算

28、第按下式計算第i個符號對應的碼字的碼長（要取整）個符號對應的碼字的碼長（要取整）3. 計算第計算第i個符號的累加概率個符號的累加概率4. 將累加概率變換成二進制小數(shù)，取小數(shù)點后將累加概率變換成二進制小數(shù)，取小數(shù)點后li位數(shù)作為第位數(shù)作為第i個符號的碼字。個符號的碼字。12( )()()qp sp sp sLlog( )log( )1iiip slp s 11()iikkPp s=1234567( )00.01SsssssssP S=信源符號信源符號 符號概率符號概率累加概率累加概率-p(si)碼長碼長碼字碼字S10.200.00002.323000

29、S20.190.2002.403001S30.180.3902.473011S40.170.5702.563100S50.150.7402.743101S60.100.8903.3241110S70.010.9906.6471111110香農(nóng)碼是即時碼，但冗余度稍大，不是最佳碼。log( )log( )1iiip slp s 平均碼長平均碼長1( )3.14/qiiiLp s l=碼元符號 信源符號信源熵信源熵1( )( )log( )2.61/qiiiH Sp sp s= =比特 信源符號結(jié)論：結(jié)論： 1) 2) 香農(nóng)碼是即時碼，但冗余度稍大，不是最佳碼。香農(nóng)碼是即時碼，但冗余度稍大，不是最

30、佳碼。( )( )1H SLH S2.6183.1%3.14=編碼效率編碼效率o 1、不用對信源符號按概率大小排序。o 2、直接計算修正的累加概率o 3、計算碼長 111( )()( )2iikikF sp sp s=log( )1iilp s= 編碼規(guī)則：一分為rd 將信源發(fā)出的q個符號按照其概率遞減的次序排列；d 將排列好的信源符號分r組，每組的概率盡量相等，并給每組賦予一個碼元；d 在對每組信號進一步分組，并賦予碼元；d 重復以上過程，直到不可再分為止；d 信源符號隨對應的碼元序列（從左向右）為費諾碼。例：對下述信源進行二進制費諾編碼。例：對下述信源進行二進制費諾編碼。 =04. 0,0

31、8. 0,16. 0,18. 0,22. 0,32. 0,)(654321sssssssPSio 該信源的熵為o 平均碼長為o 編碼效率為o 本例中費諾編碼有較高的編碼效率。費諾碼比較適合于每次分組概率都很接近的信源。特別是對每次分組概率都相等的信源進行編碼時，可達到理想的編碼效率。621()( )log( )2.35(/)iiiH Xp xp x= =比特 符號%.92974 . 2352=61( )2.4(/)iiiLp s l=比特 符號編碼規(guī)則：n A將信源消息按概率大小排序（由大至?。 B從最小兩個概率開始編碼，并賦予一定規(guī)則，如下支路小概率為“1”，上支路大概率為“0”。若兩支

32、路概率相等，仍為下支為“1”上支為“0”。n C 將已編碼兩支路概率合并，重新排隊，編碼。n D重復步驟C.直至合并概率歸一時為止。n E從概率歸一端沿樹圖路線逆行至對應消息編碼?；舴蚵幋a一定是緊致碼（最佳編碼，碼長最短）霍夫曼編碼一定是緊致碼（最佳編碼，碼長最短）例：對下述信源進行二進制霍夫曼編碼。 =1 . 0, 1 . 0, 2 . 0, 2 . 0, 4 . 0,)(54321ssssssPSi編碼方法1編碼方法2o 兩種方法的平均碼長o 編碼效率o 方差兩法平均碼長相同，因而信息率R、編碼效率相同但碼方差不同，碼方差越小越好符號碼元/2 . 2)(121=iqiilspLL %LS

33、H5 .96= 222221211.36,0.16qiiiiElLp slL=注意注意：霍夫曼編碼后的碼字不是惟一的。：霍夫曼編碼后的碼字不是惟一的。1）每次對縮減信源兩個概率最小的符號）每次對縮減信源兩個概率最小的符號分配分配“0”或或“1”碼元碼元是任意的是任意的，所以可得到不同的碼字。不同的碼元分配，得到，所以可得到不同的碼字。不同的碼元分配，得到的具體碼字不同，但碼長的具體碼字不同，但碼長li不變，平均碼長也不變，所以沒有不變，平均碼長也不變，所以沒有本質(zhì)區(qū)別；本質(zhì)區(qū)別；2）縮減信源時，）縮減信源時，若合并后的概率與其他概率相等，這幾個概率若合并后的概率與其他概率相等，這幾個概率的次序

34、可任意排列的次序可任意排列，但得到的碼字不相同，但得到的碼字不相同,對應的碼長也不相對應的碼長也不相同同,但平均碼長也不變。但平均碼長也不變。v 每次分配碼元的規(guī)律應一致，這樣才能得到可分離每次分配碼元的規(guī)律應一致，這樣才能得到可分離的碼字。的碼字。v 合并后的新的虛擬符號的概率若與其他符號的概率合并后的新的虛擬符號的概率若與其他符號的概率相等，則該虛擬符號應排在這些符號的前面，以便相等，則該虛擬符號應排在這些符號的前面，以便使碼方差最小。使碼方差最小。v 碼字排列一定要從樹根開始。碼字排列一定要從樹根開始?；舴蚵幋a的原則：霍夫曼編碼的特點：霍夫曼編碼的特點：o 霍夫曼碼的編碼方法保證了概率

35、大的符號對應于短碼，概率小的符號應用于長碼，而且所有的碼都得到了充分利用。o 每次縮減信源的最后二個碼字總是最后一位不同，前面各位相同?；舴蚵幋a一定是緊致碼例題對如下離散無記憶信源編三進制與四進制霍夫曼碼。123456789, ( )0.22,0.20,0.18,0.15,0.10,0.08, 0.05,0.01, 0.01iSsssssssssP s=r進制霍夫曼編碼三進制滿樹（等長碼）三進制全樹全樹定義碼樹中,所有中間節(jié)點的后續(xù)枝數(shù)都為。非全樹定義碼樹中,有些中間節(jié)點的后續(xù)枝數(shù)不足。三進制非全樹d 每次取最小的r個概率,分別賦以0,1,r-1；d 為使平均碼長最短，每次縮減(r-1)個符

36、號，因此信源符號數(shù)q需滿足：q= (r-1)+r 表示縮減次數(shù)。可見不是所有都能滿足上式。可見不是所有都能滿足上式。d 若q不滿足上式，則采用虛設的方法，增補一些概率為零的信源符號，即設一些信源符號：sq+1,sq+2, sq+t t= (r-1)+r-q, 并使他們的概率為零，即pq+1=pq+2= pq+t=0 使得q+t= (r-1)+r r進制霍夫曼編碼方法：其中：r=4，q=9令=2， r+ (r1) = 10，則 t=1 所以增加信源符號s10，概率p10=0例：對如下離散無記憶信源編四進制霍夫曼碼。123456789, ( )0.22,0.20,0.18,0.15,0.10,0.

37、08, 0.05,0.01, 0.01iSsssssssssP s=小結(jié)：小結(jié)： 香農(nóng)碼、費諾碼、霍夫曼碼都考慮了信源的統(tǒng)計特性，使經(jīng)香農(nóng)碼、費諾碼、霍夫曼碼都考慮了信源的統(tǒng)計特性，使經(jīng)常出現(xiàn)的信源符號對應較短的碼字，使信源的平均碼長縮短，常出現(xiàn)的信源符號對應較短的碼字，使信源的平均碼長縮短，從而實現(xiàn)了對信源的壓縮；從而實現(xiàn)了對信源的壓縮； 嚴格的香農(nóng)碼是有系統(tǒng)的、惟一的編碼方法，但在很多情況嚴格的香農(nóng)碼是有系統(tǒng)的、惟一的編碼方法，但在很多情況下編碼效率不是很高；下編碼效率不是很高； 費諾碼和霍夫曼碼的編碼方法都不惟一；費諾碼和霍夫曼碼的編碼方法都不惟一； 費諾碼比較適合于對分組概率相等或接近

38、的信源編碼；費諾碼比較適合于對分組概率相等或接近的信源編碼； 霍夫曼碼編碼效率比較高，且編出的碼一定是緊致碼，因此霍夫曼碼編碼效率比較高，且編出的碼一定是緊致碼，因此是一種最優(yōu)編碼方法，但具體實現(xiàn)設備較為復雜，且信源符是一種最優(yōu)編碼方法，但具體實現(xiàn)設備較為復雜，且信源符號與碼字之間不能用某種有規(guī)律的數(shù)學方法對應起來，只能號與碼字之間不能用某種有規(guī)律的數(shù)學方法對應起來，只能通過查表建立對應關系，因此編譯碼時搜索時間較長。通過查表建立對應關系，因此編譯碼時搜索時間較長。例題1o 設有一離散無記憶信源如下： 試求其費諾編碼和霍夫曼編碼，并求其編碼效率。=16116181412154321UUUUUP

39、U例題1o 霍夫曼編碼霍夫曼編碼1111113415123242481622888K = =815848321212)4(161)3(81)2(41) 1(21161log161161log16181log8141log4121log21)(22222=uH( )1H uK=例題1o 香農(nóng)編碼信源符號信源符號 符號概率符號概率累加概率累加概率-p(si)碼長碼長碼字碼字S11/20.0000110S21/40.5002210S31/80.75033110S41/160.875441110S51/160.9375441111( )1H uK=例題1o 費諾編碼( )1H uK=信源符號信源符號

40、符號概率符號概率碼字碼字S11/20 0S21/410 10S31/8110 110S41/1611101110S51/1611111111例題2o 已知符號集合X1,X2,X3為無限離散消息集合，它們的出現(xiàn)概率分別為.)(,.)(,)(21412211iixpxpxp=用香農(nóng)和費諾編碼方法寫出各個符號消息的代碼組。計算代碼組的平均信息傳輸速率；計算信源編碼效率例題2o 香農(nóng)編碼信源符號信源符號 符號概率符號概率累加概率累加概率-p(si)碼長碼長碼字碼字S11/20.0000110S21/40.5002210S31/80.75033110Si1/2i1-1/2i-1ii1110( )1H u

41、K=例題2o 費諾編碼( )1H uK=信源符號信源符號 符號概率符號概率碼字碼字S11/20 0S21/410 10S31/8110 110S51/2i1101110L例題3試求：1.信源符號熵H(U)2.求相應二元霍夫曼編碼及其編碼效率3.求相應三元霍夫曼編碼及其編碼效率4.若要求Pe=103,采用定長二元碼要求達到（2）中霍夫曼編碼效率時，估計要多少信源符號一起編才能實現(xiàn)。設有一離散無記憶信源如下：=01. 010. 015. 017. 018. 019. 020. 07654321UUUUUUUPU例題31.信源符號熵H(U)bituH61. 2)01. 0log01. 01 . 0l

42、og1 . 015. 0log15. 017. 0log17. 018. 0log18. 019. 0log19. 02 . 0log2 . 0()(2222222=例題32.求相應二元霍夫曼編碼及其編碼效率bitK72. 2401. 0410. 0315. 0317. 0318. 0219. 0220. 0=%96960. 0)(=KuH例題33.求相應三元霍夫曼編碼及其編碼效率8 . 101. 021 . 0215. 0217. 0218. 0219. 022 . 01=K1010log2( )( )2.61 0.6311.647log 3H uH u=%92)(=KuH例題34.若要求P

43、e=103,采用定長二元碼要求達到（2）中霍夫曼編碼效率時，估計要多少信源符號一起編才能實現(xiàn)。22221 () ( )7.0536.8120.241iDEH ubit=42.03 10約需個信源符號一起編碼。2242232DD0.2412.03 10100.109eePLLP=( )96%0.109( )H uH u=例題4o 設有一離散無記憶信源：試對下列三種情況將信源輸出進行二進制哈夫曼編碼，并求每個信源符號平均碼長和編碼效率。1. 對每個信源符號進行編碼；2. 對每兩個信源（二維擴展）符號進行編碼；3. 對每三個信源（三維擴展）符號進行編碼。=1 . 019 . 0021UUPU例題41

44、. 對每個信源符號進行編碼；11 . 009 . 0 .2211=pUpU111 . 019 . 01=K=214690. 01 . 0log1 . 09 . 0log9 . 0log)(iiibitppUH4690. 014690. 0)(11=KUH例題42. 對每兩個信源（二維擴展）符號進行編碼；645. 0)301. 0309. 0209. 0181. 0(2/12=K22( )0.46900.72710.645H UK=例題43. 對每三個信源（三維擴展）符號進行編碼。例題43. 對每三個信源（三維擴展）符號進行編碼。5327. 0)5001. 035009. 033081. 017

45、29. 0(3/13=K7386. 05327. 04690. 0)(33=KUH3.5 實用的無失真信源編碼方法實用的無失真信源編碼方法o 游程編碼o 算術編碼o LZW編碼3.5.1 游程編碼游程編碼o 游程編碼主要用于黑白二值文件、傳真的數(shù)據(jù)壓縮。 由于傳真文件中連“0”和連“1”較多這些連“0”或連“1”的字符串稱為游程對游程長度進行霍夫曼編碼或其他的編碼處理就可以達到壓縮數(shù)據(jù)的目的。o 下圖是一幅1050黑白二值圖像。 BBBBBBBBBBXXXXXXXXXAAAAAAUUUUUUUUUUUUU 符號碼標識碼游程長度編碼： B#10X#9A#6U#13 對于黑、白二值文件:1、黑白游

46、程總是交替出現(xiàn)，可以規(guī)定第一游程為白游程。2、不同游程長度出現(xiàn)的概率不同，對游程長度進行編碼采用霍夫曼編碼，概率大的編長碼，概率小的編短碼。MH編碼o Modified Huffman的簡稱，即改進的霍夫曼編碼，適用于傳真等黑白位圖圖像的壓縮，其基本的編碼規(guī)范為：o (1) 游程長度在063時，直接查表用相應的結(jié)尾碼作為碼字；o (2) 游程長度在641728范圍內(nèi)時，用組合碼加上結(jié)尾碼作為相應的碼字；o (3) 每行的第一個游程規(guī)定為白游程(長度可以為零)，每行用一個結(jié)束碼(EOL) 終止；o (4) 在傳輸時，每頁數(shù)據(jù)之前加一個結(jié)束碼，每頁尾部連續(xù)使用6個結(jié)束碼。l73白游程=64+9 ：1101110100l001101010100101101010110111101100001100110011000000000001 0白1黑15白4黑77白5黑 壓縮比=1728/47=36.7:1 結(jié)尾碼組合基干碼 A、 K星人與大不列顛百科全書星人與大不列顛百科全書o時間：xx年xx月xx日o地點：英國大不列顛博物館o人物：來自K星的王富貴o事件：王富貴試圖帶走百科全書，但是飛船空間受限，如何將信息全部帶走？o工具：無限精度的尺，飛船。1 Hello World-從小例子談起從