第三章 數(shù)據(jù)壓縮和信源編碼

1、8:1913.1 3.1 3.2 3.2 3.3 3.3 3.4 3.4 8:192 為了實現(xiàn)高質量、高效率的通信，引入了信為了實現(xiàn)高質量、高效率的通信，引入了信源編碼和信道編碼。信源編碼和信道編碼主要需源編碼和信道編碼。信源編碼和信道編碼主要需要解決以下兩個問題。要解決以下兩個問題。提高傳輸效率提高傳輸效率 增強通信的可靠性增強通信的可靠性 數(shù)據(jù)壓縮和信源編碼數(shù)據(jù)壓縮和信源編碼 8:193 編碼編碼：將一定的符號，數(shù)字或字母按一定的要求編：將一定的符號，數(shù)字或字母按一定的要求編成不同的序列，表示出一定的意義稱為編碼。成不同的序列，表示出一定的意義稱為編碼。編碼、信源編碼、信道編碼編碼、信源編

2、碼、信道編碼 編碼分為編碼分為信源編碼信源編碼和和信道編碼信道編碼，其中信源編碼又，其中信源編碼又分為分為無失真信源編碼無失真信源編碼和和限失真信源編碼限失真信源編碼。 無失真信源編碼無失真信源編碼：適用于離散信源或數(shù)字信號。：適用于離散信源或數(shù)字信號。 限失真信源編碼限失真信源編碼：主要用于連續(xù)信源或模擬信號，：主要用于連續(xù)信源或模擬信號，如語音、圖像等信號的數(shù)字處理。如語音、圖像等信號的數(shù)字處理。8:194第一極限定理第一極限定理: :無失真信源編碼定理無失真信源編碼定理. .第二極限定理第二極限定理: :信道編碼定理（包括離散和連信道編碼定理（包括離散和連 續(xù)信道）續(xù)信道）. .第三極限

3、定理第三極限定理: :限失真信源編碼定理限失真信源編碼定理. .香農信息論三大定理香農信息論三大定理 8:195 信源編碼的信源編碼的主要任務主要任務是什么是什么? ? 由于信源符號之間存在分布由于信源符號之間存在分布不均勻不均勻和和相關性相關性，使得信源存在冗余度，信源編碼的主要任務就是減使得信源存在冗余度，信源編碼的主要任務就是減少冗余，提高編碼效率。具體說，就是針對信源輸少冗余，提高編碼效率。具體說，就是針對信源輸出符號序列的統(tǒng)計特性，尋找一定的方法把信源輸出符號序列的統(tǒng)計特性，尋找一定的方法把信源輸出符號序列變換為最短的碼字序列。出符號序列變換為最短的碼字序列。 信源編碼信源編碼 8:

4、196 信源編碼的信源編碼的基本途徑基本途徑是什么是什么? ? 信源編碼的基本途徑有兩個，一是使序列中的信源編碼的基本途徑有兩個，一是使序列中的各個符號盡可能地互相獨立，即解除相關性；各個符號盡可能地互相獨立，即解除相關性；二是使編碼中各個符號出現(xiàn)的概率盡可能地相二是使編碼中各個符號出現(xiàn)的概率盡可能地相等，即概率均勻化。等，即概率均勻化。 信源編碼的信源編碼的基礎基礎是什么是什么? ? 信源編碼的信源編碼的基礎基礎是：兩個編碼定理，即是：兩個編碼定理，即無失真編碼定理和限失真編碼定理。無失真編碼定理和限失真編碼定理。信源編碼信源編碼 8:197信源編碼信源編碼：以以提高通信提高通信為目的為目的

5、, ,針對信源的編碼針對信源的編碼. .能更加有能更加有效地傳輸、存儲信息。效地傳輸、存儲信息。 在不失真或允許一定失真條件下在不失真或允許一定失真條件下 如何用盡可能如何用盡可能少的符號來傳送信源信息少的符號來傳送信源信息, ,以便提高信息傳輸率以便提高信息傳輸率。通通常通過壓縮信源的冗余度來實現(xiàn)。常通過壓縮信源的冗余度來實現(xiàn)。 采用的一般方法是采用的一般方法是壓縮每個信源符號的平均比特壓縮每個信源符號的平均比特數(shù)或信源的碼率。數(shù)或信源的碼率。即同樣多的信息用較少的碼率傳送即同樣多的信息用較少的碼率傳送, ,使單位時間內傳送的平均信息量增加使單位時間內傳送的平均信息量增加, ,從而提高通信從

6、而提高通信的有效性。的有效性。信源編碼信源編碼8:198 說明說明： （1 1）無失真編碼或可逆編碼只適用于離散信源。）無失真編碼或可逆編碼只適用于離散信源。 （2 2）對于連續(xù)信源，編成代碼后就無法無失真地）對于連續(xù)信源，編成代碼后就無法無失真地恢復原來的連續(xù)值，因為后者的取值可有無限多恢復原來的連續(xù)值，因為后者的取值可有無限多個。此時只能根據(jù)限失真編碼定理進行限失真編個。此時只能根據(jù)限失真編碼定理進行限失真編碼碼 。信源編碼信源編碼編碼定理證明：編碼定理證明：（1 1）必存在一種編碼方法，使代碼的平均長度可）必存在一種編碼方法，使代碼的平均長度可 任意接近但不能低于符號熵任意接近但不能低于

7、符號熵（2 2）達到這目標的途徑，就是使概率與碼長匹配。）達到這目標的途徑，就是使概率與碼長匹配。 8:199 信道編碼：信道編碼： 是以是以提高信息傳輸?shù)奶岣咝畔鬏數(shù)臑槟康牡木幋a。在信道為目的的編碼。在信道受干擾的情況下如何增加信號的受干擾的情況下如何增加信號的, ,同時同時又使得信息傳輸率最大。通常通過增加信源的冗余又使得信息傳輸率最大。通常通過增加信源的冗余度來實現(xiàn)。采用的一般方法是增大碼率度來實現(xiàn)。采用的一般方法是增大碼率/ /帶寬。與帶寬。與信源編碼正好相反。信源編碼正好相反。 密碼：密碼： 是以提高通信系統(tǒng)的是以提高通信系統(tǒng)的為目的的編碼。通常通為目的的編碼。通常通過加密和解密來

8、實現(xiàn)。從信息論的觀點出發(fā)過加密和解密來實現(xiàn)。從信息論的觀點出發(fā)“加密加密”可視為增熵的過程可視為增熵的過程, ,“解密解密”可視為減熵的過程?？梢暈闇p熵的過程。信道編碼、密碼信道編碼、密碼8:1910信源編碼包括兩個功能：信源編碼包括兩個功能： （1 1）將信源符號變換成適合信道傳輸?shù)姆?；）將信源符號變換成適合信道傳輸?shù)姆枺?（2 2） 壓縮信源冗余度，提高傳輸效率。壓縮信源冗余度，提高傳輸效率。 提高傳輸效率往往削弱了其抗干擾能力。提高傳輸效率往往削弱了其抗干擾能力。提高抗提高抗干擾能力往往是以降低信息傳輸效率為代價。干擾能力往往是以降低信息傳輸效率為代價。 8:1911l由信源的漸近等

9、分性導出了信源編碼定理：由信源的漸近等分性導出了信源編碼定理：只要只要編碼的碼率大于編碼的碼率大于信源的熵（或熵率），則必存在信源的熵（或熵率），則必存在編譯碼方案編譯碼方案, ,使當被編碼的信源分組長趨于無窮時使當被編碼的信源分組長趨于無窮時, ,譯譯碼誤差概率可以充分小碼誤差概率可以充分小, ,這解決了最優(yōu)碼的存在性問這解決了最優(yōu)碼的存在性問題。題。l怎樣構造最優(yōu)碼？怎樣構造最優(yōu)碼？信源編碼信源編碼8:1912信源編碼的分類：離散信源編碼、連續(xù)信源編碼和相信源編碼的分類：離散信源編碼、連續(xù)信源編碼和相關信源編碼三類關信源編碼三類離散信源編碼離散信源編碼：獨立信源編碼，可做到無失真編獨立信源

10、編碼，可做到無失真編碼；碼；連續(xù)信源編碼連續(xù)信源編碼：獨立信源編碼，只能做到限失真獨立信源編碼，只能做到限失真信源編碼信源編碼；相關信源編碼相關信源編碼：非獨立信源編碼。非獨立信源編碼。信源編碼的分類信源編碼的分類8:1913 冗余度壓縮編碼冗余度壓縮編碼: : 是可逆壓縮，經編譯碼后可以無失真地恢復。是可逆壓縮，經編譯碼后可以無失真地恢復。 基本途徑：基本途徑：壓縮信源的冗余度，即壓縮信源的冗余度，即 1) 1) 去除碼符號間的相關性；去除碼符號間的相關性； 2) 2) 使碼符號等概分布。使碼符號等概分布。信源編碼的分類信源編碼的分類8:1914熵壓縮編碼：是不可逆壓縮熵壓縮編碼：是不可逆壓

11、縮 壓縮超過一定限度，必然帶來失真壓縮超過一定限度，必然帶來失真, ,允許的失真允許的失真越大，壓縮的比例越大越大，壓縮的比例越大, ,譯碼時能按一定的失真容許譯碼時能按一定的失真容許度恢復，保留盡可能多的信息。度恢復，保留盡可能多的信息。信源編碼的分類信源編碼的分類8:1915l 信源編碼將信源編碼將信源符號序列信源符號序列按一定的數(shù)學規(guī)律映射成按一定的數(shù)學規(guī)律映射成碼碼符號序列符號序列。是從信源符號集到碼符號集的一種映射，它。是從信源符號集到碼符號集的一種映射，它把信源輸出的符號變換成碼元序列。把信源輸出的符號變換成碼元序列。信宿信宿信道信道信源信源編碼器編碼器譯碼器譯碼器 信源編碼器模型

12、信源編碼器模型 譯碼是從碼符號到信源符號的映射。若要實現(xiàn)無失譯碼是從碼符號到信源符號的映射。若要實現(xiàn)無失真編碼，這種映射必須是一一對應的、可逆的。真編碼，這種映射必須是一一對應的、可逆的。 信源編碼器模型信源編碼器模型8:1916編碼器編碼器12: ,.,DXx xx碼字碼字12,qXXXX12liiiiicx xx12 ,qCc ccl 將信源符號集中的符號將信源符號集中的符號 （或者長為（或者長為n的信源符號序的信源符號序列）映射成由碼符號列）映射成由碼符號 組成的長度為組成的長度為 的一一對應的的一一對應的碼符號序列碼符號序列 。ixiXilic信源編碼器的模型信源編碼器的模型8:191

13、7l編碼器輸出的碼符號序列編碼器輸出的碼符號序列 稱為稱為碼字碼字；長度；長度 稱為稱為碼字長度，簡稱碼字長度，簡稱碼長碼長；全體碼字的集合記為；全體碼字的集合記為C C。l將信源符號集中的每個信源符號將信源符號集中的每個信源符號 依照固定的碼表依照固定的碼表映射成某一個碼字映射成某一個碼字 ，這樣的碼稱為，這樣的碼稱為分組碼分組碼。l只有分組碼才有對應的碼表，而非分組碼中則不存在只有分組碼才有對應的碼表，而非分組碼中則不存在碼表。碼表。iciXicil對于同一個信源，編碼方法是多種的。對于同一個信源，編碼方法是多種的。分組碼分組碼8:1918 3. 變長碼變長碼若碼字集合若碼字集合C中的所有

14、碼字中的所有碼字cm (m = 1,2, ,M)，其碼長，其碼長不都相同不都相同，稱碼稱碼C為變長碼。為變長碼。 2. 等長碼等長碼在一組碼字集合在一組碼字集合C中的所有碼字中的所有碼字cm (m = 1,2, ,M)，其碼長，其碼長都相都相同同，則稱這組碼，則稱這組碼C為等長碼。為等長碼。 1. 二元碼二元碼若碼符號集為若碼符號集為0，1，則碼字就是二元序列，稱為二元碼，則碼字就是二元序列，稱為二元碼, ,二二元碼通過二進制信道傳輸，這是數(shù)字通信和計算機通信中最常元碼通過二進制信道傳輸，這是數(shù)字通信和計算機通信中最常見的一種碼。見的一種碼。碼的分類碼的分類8:1919 4.非奇異碼非奇異碼從

15、信源消息到碼字的映射從信源消息到碼字的映射是一一對應的是一一對應的，每一個不同的信源消，每一個不同的信源消息都用不同的碼字對其編碼。息都用不同的碼字對其編碼。非奇異碼非奇異碼碼中所有碼字互不相同碼中所有碼字互不相同. 5.奇異碼奇異碼從信源消息到碼字的映射從信源消息到碼字的映射不是一一對應的不是一一對應的。奇異碼不具備惟。奇異碼不具備惟一可譯性。一可譯性。原碼的原碼的N次擴展碼是將信源作次擴展碼是將信源作N次擴展得到的新信源符號序列次擴展得到的新信源符號序列u（N）=u1 uN = (u11 u12 u1L) (uN1 uN2 uNL)，對應碼符號序列對應碼符號序列c（N）=c1 cN = (

16、c11 c12 c1n) (cN1 cN2 cNn) ，記集合記集合 C (N) = c1(N), c2(N), 即原碼即原碼C的的N次擴展碼。次擴展碼。 6.原碼原碼C的的N次擴展碼次擴展碼8:1920對于等長碼，若原碼是惟一可譯碼，則它的對于等長碼，若原碼是惟一可譯碼，則它的N N次擴展碼也是次擴展碼也是惟一可譯的，而對于變長碼則不盡然。惟一可譯的，而對于變長碼則不盡然。 7.惟一可譯碼惟一可譯碼定義定義 若任意一串有限長的碼符號序列只能被惟一地譯為對若任意一串有限長的碼符號序列只能被惟一地譯為對應的信源符號序列，則稱此碼為應的信源符號序列，則稱此碼為惟一可譯碼惟一可譯碼。l 惟一可譯碼惟

17、一可譯碼應當滿足的條件應當滿足的條件(1,2,., )(1,2,., )iic iqX iq碼字與信源符號一一對應碼字與信源符號一一對應2) 不同的信源符號序列對應不同的碼字序列。不同的信源符號序列對應不同的碼字序列。1) 8:1921 8. 即時碼即時碼定義定義 對于碼字對于碼字c = c1 c2 cn, ,稱稱c、 = c1 c2 ci ( (i0，只要滿足，只要滿足 則當則當N足夠大時，可實現(xiàn)幾乎無失真編碼，即譯碼錯誤足夠大時，可實現(xiàn)幾乎無失真編碼，即譯碼錯誤概率概率 PE 為任意?。粸槿我庑?； （D進制）進制） 反之，如果反之，如果 則不可能實現(xiàn)無失真編碼，當則不可能實現(xiàn)無失真編碼，當

18、N足夠大時，譯碼錯誤概足夠大時，譯碼錯誤概率率 PE 為為1。()logkH XND()2logkH XNDNX等長編碼定理等長編碼定理8:1942等長編碼的等長編碼的效率效率 （D進制）進制）(),logH XLD 為使編碼真正有效，必須增大信源序列的分組長為使編碼真正有效，必須增大信源序列的分組長度度N，這就會使編、譯碼的延時增大，同時也會使編，這就會使編、譯碼的延時增大，同時也會使編、譯碼器的復雜程度增加，因此，等長編碼在冗余度、譯碼器的復雜程度增加，因此，等長編碼在冗余度壓縮編碼中的理論意義遠大于其實用價值。壓縮編碼中的理論意義遠大于其實用價值。1()qiiiLp X k等長編碼定理等

19、長編碼定理8:1943 如果無論怎樣編碼都是有錯編碼，但可以使如果無論怎樣編碼都是有錯編碼，但可以使當?shù)鼐幋a和譯碼使譯碼錯誤的概率當?shù)鼐幋a和譯碼使譯碼錯誤的概率pe任意小，這任意小，這就是所謂就是所謂“漸進無錯編碼漸進無錯編碼”。( , ) ( ().nnerfPPf xx一個編譯碼方案為概率的錯誤等長編碼定理等長編碼定理8:1944() 2,1log().nH XeDMPRMH Xn若用 進數(shù)字表出個碼字，要使譯碼錯誤概率只需碼率() 2,1loglog().knH XkDDMkRMDH Xnn若編碼成 長的 進碼字，則于是碼率等長編碼定理等長編碼定理8:1945( ),nnerPP xWn

20、由漸近等分性知這樣編碼的錯誤概率為當 充分大時成立。等長編碼定理等長編碼定理nn但在實際應用中， 不可能無限增大，這就要求我們在給定的有限 尋求盡可能好的編譯碼方案，使得碼率盡可能接近時,理論值。8:1946l等長編碼定理同樣也適用于離散平穩(wěn)有記憶信源，差等長編碼定理同樣也適用于離散平穩(wěn)有記憶信源，差別是要將信源熵別是要將信源熵 改為極限熵改為極限熵 。l可以驗證，對等長信源編碼來說，要想實現(xiàn)無失真信可以驗證，對等長信源編碼來說，要想實現(xiàn)無失真信源編碼，源編碼，N常常要取非常大的值常常要取非常大的值，這在實際應用中很，這在實際應用中很 難實現(xiàn)。難實現(xiàn)。()H XH 等長編碼在引入失真的前提下，

21、還需要取很長等長編碼在引入失真的前提下，還需要取很長的信源序列進行編碼，才能達到較高的編碼效率。的信源序列進行編碼，才能達到較高的編碼效率。既要不失真，又要很高的編碼效率，只能采用變長既要不失真，又要很高的編碼效率，只能采用變長編碼。編碼。等長編碼定理等長編碼定理8:1947 對等長碼的討論是在對等長碼的討論是在N足夠大的條件下得到的結足夠大的條件下得到的結論，論，當當N為有限值時，則總會帶來一定程度的失真。為有限值時，則總會帶來一定程度的失真。對于變長碼，往往在對于變長碼，往往在N不是很大的情況下不是很大的情況下就可編出高就可編出高效且無失真的碼。效且無失真的碼。 變長碼也要求原碼的變長碼也

22、要求原碼的任意任意N次擴展碼次擴展碼也是惟一可也是惟一可譯的。變長碼分為即時碼和延長碼，為保證即時譯碼，譯的。變長碼分為即時碼和延長碼，為保證即時譯碼，要求變長惟一可譯碼采用即時碼。對于變長碼，要求要求變長惟一可譯碼采用即時碼。對于變長碼，要求整個碼集的平均碼長力求最小，此時編碼效率最高。整個碼集的平均碼長力求最小，此時編碼效率最高。 當信源較復雜當信源較復雜, ,直接畫碼樹就比較復雜。針對這直接畫碼樹就比較復雜。針對這一問題，在數(shù)學上給出一個與碼樹等效的，表達碼字一問題，在數(shù)學上給出一個與碼樹等效的，表達碼字可分離的充要條件，即著名的克拉夫特不等式?？煞蛛x的充要條件，即著名的克拉夫特不等式。

23、變長編碼變長編碼8:1948 Kraft定理定理 即時碼存在的充要條件即時碼存在的充要條件是是 McMillan定理定理 惟一可譯碼存在的充要條件惟一可譯碼存在的充要條件是是12, ,.,1.ilmiDl llD碼字字母取值于 進字母集的即時碼，其碼字長分別為時必須滿足12, ,.,1.ilmiDl llD碼字字母取值于 進字母集的惟一可譯碼，其碼字長分別為時必須滿足Kraft不等式和不等式和McMillan不等式不等式8:1949l上述定理是上述定理是存在性定理存在性定理當滿足當滿足KraftKraft（或（或McMillanMcMillan）不等式時，必然可）不等式時，必然可以構造出即時碼

24、（或惟一可譯碼），否則不能構以構造出即時碼（或惟一可譯碼），否則不能構造出即時碼（或惟一可譯碼）。但滿足造出即時碼（或惟一可譯碼）。但滿足KraftKraft不等不等式的碼長集未必是最優(yōu)的，即它的平均碼長未必式的碼長集未必是最優(yōu)的，即它的平均碼長未必是最小的。是最小的。該定理該定理不能不能作為判斷一種碼是否是即時碼（或惟作為判斷一種碼是否是即時碼（或惟一可譯碼）的判斷依據(jù)。一可譯碼）的判斷依據(jù)。KraftKraft不等式和不等式和McMillanMcMillan不等式不等式8:19501( )qiiiLp x l碼符號碼符號/信源符號信源符號l 平均碼長平均碼長L 對于給定的信源和碼符號集，若

25、有一個惟一可譯碼，對于給定的信源和碼符號集，若有一個惟一可譯碼，其平均長度其平均長度 小于所有其它惟一可譯碼小于所有其它惟一可譯碼,則稱這種碼則稱這種碼為為最佳碼最佳碼或或緊致碼緊致碼。 所謂所謂最佳最佳：是指在所有可能的編碼方法中，：是指在所有可能的編碼方法中，其編其編碼得到的平均碼長最短碼得到的平均碼長最短。 8:1951()()1loglogNH XLH XDNDN香農第一定理香農第一定理 設離散無記憶信源的熵為設離散無記憶信源的熵為H H( (X X ) )，它的，它的N N 次擴展次擴展信源為信源為 ，對擴展信源，對擴展信源 進行編碼進行編碼（D D進制）進制），總，總可以找到一種編

26、碼方法，構成惟一可譯碼，使平均碼可以找到一種編碼方法，構成惟一可譯碼，使平均碼長滿足長滿足 NXNX 變長編碼不要求所有碼字長度相同變長編碼不要求所有碼字長度相同, ,但希望平均碼長最小但希望平均碼長最小, ,變長無失真信源編碼定理給出了在無失真編碼的前提下平均變長無失真信源編碼定理給出了在無失真編碼的前提下平均碼長的界限。碼長的界限。變長無失真信源編碼定理變長無失真信源編碼定理8:1952*(),().()()11.DLH XlHXHXH XLl 冗余度相 一個 進制惟一可譯碼的冗余度為其平均長度與信源熵的差，即余度或冗或對定義 變長編碼采用即時碼變長編碼采用即時碼,力求平均碼長最小力求平均

27、碼長最小,此時此時編碼效率最高，信源的冗余得到最大程度的壓縮。編碼效率最高，信源的冗余得到最大程度的壓縮。將概率大的信息符號編以短的碼字，概率小的符號將概率大的信息符號編以短的碼字，概率小的符號編以長的碼字，可使得平均碼字長度最短。編以長的碼字，可使得平均碼字長度最短。冗余度冗余度8:1953 對于同一種信源，對于同一種信源，香農編碼不能使平均碼長達到最小，因香農編碼不能使平均碼長達到最小，因此不是最佳編碼。三種編碼法中此不是最佳編碼。三種編碼法中,以以香香農編碼法的編碼效率最低農編碼法的編碼效率最低，法諾編碼法也不是一種最佳編碼法，但用這種方法有時候也，法諾編碼法也不是一種最佳編碼法，但用這

28、種方法有時候也能找到最優(yōu)碼。能找到最優(yōu)碼。 一般情況下一般情況下, ,哈夫曼編碼法得到的平均碼長哈夫曼編碼法得到的平均碼長 最短，即最短，即編編碼效率碼效率 最高。最高。()lo gHXLDL香農（香農（Shannon）編碼法）編碼法法諾法諾( (Fano) )編碼法編碼法哈夫曼哈夫曼( (Huffman) )編碼法編碼法變長編碼法變長編碼法變長碼的編碼方法變長碼的編碼方法8:1954香農碼編碼步驟：香農碼編碼步驟：1. 將信源符號按概率從大到小順序排列，方便起見，令將信源符號按概率從大到小順序排列，方便起見，令 2. 按下式計算第按下式計算第i個符號對應的碼字的碼長個符號對應的碼字的碼長3.

29、 計算第計算第i個符號的累加概率個符號的累加概率4. 將累加概率變換成將累加概率變換成二進制小數(shù)二進制小數(shù)，取小數(shù)點后，取小數(shù)點后li位位數(shù)作為數(shù)作為 第第i個符號的碼字。個符號的碼字。12()()()np xp xp x11()iikkPp x1log 1( )iilp x(1)(1)香農（香農（ShannonShannon）編碼）編碼8:19550.0171234567( )0.200.190.180.170.150.100.01XxxxxxxxP x例例 對如下信源進行對如下信源進行香農香農編碼編碼信源符號符號概率累加概率碼長碼字x10.2002.3430000.190.22.41300

30、10.180.392.483011x40.170.572.563100 x50.150.742.743101x60.100.893.3441110 x70.996.661111110iPix()ip xillog()ip xx2x38:1956 平均碼長平均碼長1( )3.14/qiiiLp x l碼元符號 信源符號信源熵信源熵1()( )log( )2.61/qiiiH Xp xp x 比特 信源符號結論：結論： 1) 2) 香農碼是即時碼，但冗余度稍大，不是最佳碼。香農碼是即時碼，但冗余度稍大，不是最佳碼。()() 1.H XLH X2.6183.1%3.14編碼效率編碼效率8:1957

31、在眾多變長碼中，哈夫曼碼是效率最高的變長在眾多變長碼中，哈夫曼碼是效率最高的變長無失真信源編碼方法，它是一種逐個符號的編碼方無失真信源編碼方法，它是一種逐個符號的編碼方法，是在編碼理論指導下法，是在編碼理論指導下平均碼長最短的碼平均碼長最短的碼。 原理：原理： 構造一個碼樹。構造一個碼樹。 (2)(2)哈夫曼哈夫曼(Huffman)(Huffman)編碼編碼8:19581.1. 將信源符號按概率從大到小的順序排列，令將信源符號按概率從大到小的順序排列，令2.2. 給兩個概率最小的信源符號給兩個概率最小的信源符號xn-1和和xn各分配一個碼元各分配一個碼元“0 0”和和“1 1”，并將這兩個信源

32、符號合并成一個新符，并將這兩個信源符號合并成一個新符號，并用這兩個最小的概率之和作為新符號的概率，號，并用這兩個最小的概率之和作為新符號的概率，結果得到一個只包含結果得到一個只包含n1個信源符號的新信源。稱個信源符號的新信源。稱為為信源的第一次縮減信源信源的第一次縮減信源，用，用X X1 1表示。表示。12( )()()np xp xp x哈夫曼碼編碼步驟：哈夫曼碼編碼步驟：(2)(2)哈夫曼哈夫曼(Huffman)(Huffman)編碼編碼8:1959 3. 3. 將縮減信源將縮減信源X1的符號仍按概率從大到小順序排的符號仍按概率從大到小順序排 列，列，重復步驟重復步驟2 2，得到只含，得到

33、只含n2個符號的縮減信源個符號的縮減信源X2。 4. 4. 重復上述步驟，直至縮減信源只剩兩個符號為重復上述步驟，直至縮減信源只剩兩個符號為止，此時所剩兩個符號的概率之和必為止，此時所剩兩個符號的概率之和必為1 1。然后從。然后從最后一級縮減信源開始，依編碼路徑向前返回，就最后一級縮減信源開始，依編碼路徑向前返回，就得到各信源符號所對應的碼字。得到各信源符號所對應的碼字。(2)(2)哈夫曼哈夫曼(Huffman)(Huffman)編碼編碼8:196012345:0.4:0.2:0.2:0.1:0.1xxxxx014 . 02 . 02 . 02 . 0014 . 04 . 02 . 0016

34、. 04 . 00111c 201c 3000c 40010c 50011c 1( )2.2qiiiLp x l碼符號碼符號/信源符號信源符號8:196112345:0.4:0.2:0.2:0.1:0.1xxxxx014 . 02 . 02 . 02 . 0014 . 04 . 02 . 0016 . 04 . 001100c 210c 311c 4010c 5011c 1( )2.2qiiiLp x l碼符號碼符號/信源符號信源符號8:1962討論：討論：1) 1) 兩種方法平均碼長相等。兩種方法平均碼長相等。2) 2) 計算兩種碼的碼長方差：計算兩種碼的碼長方差：52211( )()1.3

35、6iiip xlL52221( )()0.16iiip xlL第二種方法編出的碼碼字長度變化較小，便于實現(xiàn)。第二種方法編出的碼碼字長度變化較小，便于實現(xiàn)。8:19631234567( )0.200.190.180.170.150.100.01XxxxxxxxP x解解 哈夫曼編碼結果：哈夫曼編碼結果：12345671011000001 01001100111xxxxxxx信源符號碼字例例 對如下信源進行哈夫曼編碼對如下信源進行哈夫曼編碼8:1964l平均碼長為平均碼長為l信源熵為信源熵為l編碼效率為編碼效率為71( )2.72/iiiLp x l碼元符號 信源符號2.6196.0%2.7271

36、()( )log( )2.61/iiiH Xp xp x 比特 信源符號8:1965注：哈夫曼編碼后的碼字不是惟一的。注：哈夫曼編碼后的碼字不是惟一的。1 1）每次對縮減信源兩個概率最小的符號）每次對縮減信源兩個概率最小的符號分配分配“0 0”或或“1 1”碼元碼元是任意的是任意的，所以可得到不同的碼字。不同的碼元分配，得，所以可得到不同的碼字。不同的碼元分配，得到的具體碼字不同，但碼長不變，平均碼長也不變，所以到的具體碼字不同，但碼長不變，平均碼長也不變，所以沒有本質區(qū)別。沒有本質區(qū)別。2 2）縮減信源時，）縮減信源時，若合并后的概率與其它概率相等，這幾個概若合并后的概率與其它概率相等，這幾

37、個概率的次序可任意排列率的次序可任意排列，但得到的碼字不相同，但得到的碼字不相同, ,對應的碼長也對應的碼長也不相同不相同, ,但平均碼長不變。但平均碼長不變。哈夫曼編碼哈夫曼編碼8:1966 第一，哈夫曼編碼實際上構造了一個碼樹，碼第一，哈夫曼編碼實際上構造了一個碼樹，碼樹從最上層的端點開始構造，直到樹根結束，最后樹從最上層的端點開始構造，直到樹根結束，最后得到一個橫放的碼樹，因此，編出的碼是即時碼。得到一個橫放的碼樹，因此，編出的碼是即時碼。 第二，哈夫曼編碼采用概率匹配方法來決定各第二，哈夫曼編碼采用概率匹配方法來決定各碼字的碼長，概率大的符號對應于短碼，概率小的碼字的碼長，概率大的符號

38、對應于短碼，概率小的符號對應于長碼，從而使平均碼長最小。符號對應于長碼，從而使平均碼長最小。 第三，每次對概率最小的兩個符號求概率之和第三，每次對概率最小的兩個符號求概率之和形成縮減信源時形成縮減信源時,就構造出兩個樹枝，由于給兩個樹就構造出兩個樹枝，由于給兩個樹枝賦碼元時是任意的枝賦碼元時是任意的,因此編出的碼字并不惟一。因此編出的碼字并不惟一。哈夫曼編碼的基本特點哈夫曼編碼的基本特點8:1967 哈夫曼哈夫曼優(yōu)點：優(yōu)點：編碼方便易行，效率高編碼方便易行，效率高。 在哈夫曼編碼過程中，對縮減信源符號按概在哈夫曼編碼過程中，對縮減信源符號按概率由大到小的順序重新排列時，應使率由大到小的順序重新

39、排列時，應使合并后的新合并后的新符號盡可能排在靠前的位置符號盡可能排在靠前的位置，這樣可使合并后的，這樣可使合并后的新符號重復編碼次數(shù)減少新符號重復編碼次數(shù)減少, ,使短碼得到充分利用。使短碼得到充分利用。 通過最佳的信源編碼雖然可以消除信源的冗通過最佳的信源編碼雖然可以消除信源的冗余度，提高信息傳輸率，但結果卻使碼變得十分余度，提高信息傳輸率，但結果卻使碼變得十分“脆弱脆弱”，經不起信道中噪聲的干擾，容易造成，經不起信道中噪聲的干擾，容易造成譯碼錯誤。譯碼錯誤。哈夫曼編碼的優(yōu)點哈夫曼編碼的優(yōu)點8:1968 （1 1）如果對單個字母編碼時，平均碼字長與理論）如果對單個字母編碼時，平均碼字長與理

40、論上的最優(yōu)壓縮率可能還有一定距離（可能差上的最優(yōu)壓縮率可能還有一定距離（可能差1比比特）。特）。 當信源熵當信源熵H(X)很大時，這很大時，這1比特比特可能無關重要；可能無關重要；但當?shù)擧(X)本身就接近本身就接近1比特時，這額外的比特時，這額外的1比特可比特可能決定了編碼的碼率，這顯然不經濟，因此要進能決定了編碼的碼率，這顯然不經濟，因此要進一步提高編碼效率，使碼率盡可能接近信源熵，一步提高編碼效率，使碼率盡可能接近信源熵，則仍需則仍需對長的信源序列來編碼對長的信源序列來編碼。 哈夫曼編碼的缺點哈夫曼編碼的缺點8:1969（2 2）哈夫曼哈夫曼編碼算法是從下而上地構造碼樹編碼算法是從下而上

41、地構造碼樹, ,當信源字母集很大時當信源字母集很大時, ,這種算法甚為不便。另這種算法甚為不便。另外外, ,哈夫曼編碼需要知道信源的概率分布哈夫曼編碼需要知道信源的概率分布, ,這這在實際中有時是比較困難的。在實際中有時是比較困難的。哈夫曼編碼的缺點哈夫曼編碼的缺點8:1970(3)().()logkkkkkkxlxpLHXLlpHX 由哈夫曼編碼方法可以看到，當信源字母 對應的碼長與 的概率滿足關系時，編碼后的平均碼長 是理論上可達到的最短平均碼長，即信源的熵率如果不滿足該條件時（稱統(tǒng)計失配）， 與就有差距，這時編碼性能下降。哈夫曼編碼的缺點哈夫曼編碼的缺點8:1971 （4 4）從硬件實現(xiàn)

42、上來看，哈夫曼編碼有變長碼）從硬件實現(xiàn)上來看，哈夫曼編碼有變長碼的固有缺點：的固有缺點：需緩沖存儲器需緩沖存儲器。 因為一般信源和信道傳輸信號是恒速的，但因為一般信源和信道傳輸信號是恒速的，但經變長編碼后信源編碼的每秒輸出的比特數(shù)就不經變長編碼后信源編碼的每秒輸出的比特數(shù)就不是常量，不能直接用信道來傳輸，為適應信道必是常量，不能直接用信道來傳輸，為適應信道必須加緩沖設備，將編碼器輸出暫存在緩沖器中，須加緩沖設備，將編碼器輸出暫存在緩沖器中，然后再接到信道去傳送。然后再接到信道去傳送。 從理論上講當存儲器容量為無限時，信源輸從理論上講當存儲器容量為無限時，信源輸出與信道傳輸之間才能取得平衡，當存

43、儲器容量出與信道傳輸之間才能取得平衡，當存儲器容量有限時，這種平衡不一定能保持。有限時，這種平衡不一定能保持。哈夫曼編碼的缺點哈夫曼編碼的缺點8:1972 當信源連續(xù)輸出低概率符號，其對應的碼字較長，輸入當信源連續(xù)輸出低概率符號，其對應的碼字較長，輸入緩沖器的比特數(shù)大于信道能輸出的比特數(shù)，會造成存儲器溢緩沖器的比特數(shù)大于信道能輸出的比特數(shù)，會造成存儲器溢出。出。 反之，當信源連續(xù)輸出高概率符號，其對應的碼字較短，反之，當信源連續(xù)輸出高概率符號，其對應的碼字較短，輸入緩沖器的比特數(shù)小于信道能輸出的比特數(shù)，會造成存儲輸入緩沖器的比特數(shù)小于信道能輸出的比特數(shù)，會造成存儲器取空，信道上無信息可送，而使

44、信道上出現(xiàn)連個器取空，信道上無信息可送，而使信道上出現(xiàn)連個0 0或連個或連個1 1，導致誤譯。導致誤譯。 因此因此需設計適當?shù)拇鎯ζ魅萘啃柙O計適當?shù)拇鎯ζ魅萘浚ń档统杀?，增加容量），（降低成本，增加容量），并把信源發(fā)出的信息分段發(fā)送，或經常檢查存儲器，如有溢并把信源發(fā)出的信息分段發(fā)送，或經常檢查存儲器，如有溢出，就轉停，如有取空，則加入空間符號。出，就轉停，如有取空，則加入空間符號。 哈夫曼編碼的缺點哈夫曼編碼的缺點8:1973（5 5）差錯擴散）差錯擴散: : 對變長碼一旦產生誤碼對變長碼一旦產生誤碼, ,某個碼字的前綴某個碼字的前綴部分可能成為另一個碼字而發(fā)生錯譯部分可能成為另一個碼字而發(fā)

45、生錯譯, ,并可導并可導致錯誤后傳致錯誤后傳. .哈夫曼編碼的缺點哈夫曼編碼的缺點8:1974法諾法諾(Fano)(Fano)碼編碼步驟：碼編碼步驟：1.1. 將概率按從大到小的順序排列，令將概率按從大到小的順序排列，令2.2. 將依次排列的信源符號按概率分成兩組，使每組概率和盡可將依次排列的信源符號按概率分成兩組，使每組概率和盡可能接近或相等。能接近或相等。3.3. 給每一組分配一位碼元給每一組分配一位碼元“0 0”或或“1 1”。4.4. 將每一分組再按同樣方法劃分，重復步驟將每一分組再按同樣方法劃分，重復步驟2 2和和3 3，直至概率不，直至概率不再可分為止。由此即可構造一個碼樹，所有終

46、端節(jié)點上的碼再可分為止。由此即可構造一個碼樹，所有終端節(jié)點上的碼字組成法諾碼。字組成法諾碼。 原理原理：它是通過構造一個碼樹，編出的碼是即時碼，但不一定：它是通過構造一個碼樹，編出的碼是即時碼，但不一定是最佳碼。是最佳碼。12( )()()qp xp xp x(3)(3)法諾法諾(Fano)(Fano)編碼編碼8:1975解解信源符號符號概率第一次分組第二次分組第三次分組第四次分組碼字碼長0.20000020.191001030.18101130.17101020.151011030.1010111040.011111141x2x4x3x5x6x7x1234567( )0.200.190.18

47、0.170.150.100.01XxxxxxxxP x例例 對如下信源進行法諾編碼對如下信源進行法諾編碼8:1976l平均碼長為平均碼長為l信源熵為信源熵為l編碼效率為編碼效率為2.6195.3%2.7471()( )log( )2.61/iiiH Xp xp x 比特 信源符號71( )2.74/iiiLp x l碼元符號 信源符號8:1977 (1) (1) 法諾編碼在構造碼樹時，是從樹根開始到終端法諾編碼在構造碼樹時，是從樹根開始到終端節(jié)點結束，這節(jié)點結束，這與哈夫曼編碼相反與哈夫曼編碼相反； (2) (2) 由于賦碼元時的任意性，因此法諾編碼編出的由于賦碼元時的任意性，因此法諾編碼編出

48、的碼字碼字不惟一不惟一； (3) (3) 法諾編碼不全是按法諾編碼不全是按“概率大碼長小、概率小碼概率大碼長小、概率小碼長大長大”來決定碼長，有時會出現(xiàn)概率小碼長反而小來決定碼長，有時會出現(xiàn)概率小碼長反而小的情況，因此的情況，因此平均碼長一般不會最小平均碼長一般不會最小。法諾編碼法諾編碼的特點的特點8:1978l香農碼、法諾碼、哈夫曼碼都考慮了香農碼、法諾碼、哈夫曼碼都考慮了信源的統(tǒng)計特性信源的統(tǒng)計特性, ,使經常出現(xiàn)的信源符號對應較短的碼字使經常出現(xiàn)的信源符號對應較短的碼字, ,使信源的平均使信源的平均碼長縮短，從而實現(xiàn)了對信源的壓縮碼長縮短，從而實現(xiàn)了對信源的壓縮. .l香農編碼結果香農編

49、碼結果惟一惟一, ,但在很多情況下但在很多情況下編碼效率不高編碼效率不高. .l法諾碼和哈夫曼碼的編碼方法都法諾碼和哈夫曼碼的編碼方法都不惟一不惟一. .l法諾碼比較適合于對法諾碼比較適合于對分組概率相等或接近的信源編碼分組概率相等或接近的信源編碼. .l哈夫曼哈夫曼碼對信源的統(tǒng)計特性沒有特殊要求碼對信源的統(tǒng)計特性沒有特殊要求, ,編碼效率編碼效率比較高，對編碼設備的要求也比較簡單，因此比較高，對編碼設備的要求也比較簡單，因此綜合性綜合性能優(yōu)于香農碼和法諾碼能優(yōu)于香農碼和法諾碼. .三種三種編碼編碼方法的對比方法的對比8:1979 cabcedeacacdeddaaabaababaaabbac

50、debaceacabcedeacacdeddaaabaababaaabbacdebaceada da 共共4040個字母個字母 采用法諾編碼法采用法諾編碼法 頻度頻度a - 16a - 16，b - 7b - 7，c - 6c - 6，d - 6d - 6，e - 5 e - 5 1) 1) 將給定符號按照其頻率從大到小排序。將給定符號按照其頻率從大到小排序。a a 16 b - 7 c - 6 d - 6 e 16 b - 7 c - 6 d - 6 e 5 52) 2) 將序列分成左右兩部分，使得左部頻率總和將序列分成左右兩部分，使得左部頻率總和盡可能接近右部頻率總和。盡可能接近右部頻率總和。(a, b), (c