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

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

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

3、失真信源編碼定理限失真信源編碼定理. .香農(nóng)信息論三大定理香農(nóng)信息論三大定理 *5 信源編碼的信源編碼的主要任務(wù)主要任務(wù)是什么是什么? ? 由于信源符號(hào)之間存在分布由于信源符號(hào)之間存在分布不均勻不均勻和和相關(guān)性相關(guān)性，使得信源存在冗余度，信源編碼的主要任務(wù)就是減使得信源存在冗余度，信源編碼的主要任務(wù)就是減少冗余，提高編碼效率。具體說，就是針對(duì)信源輸少冗余，提高編碼效率。具體說，就是針對(duì)信源輸出符號(hào)序列的統(tǒng)計(jì)特性，尋找一定的方法把信源輸出符號(hào)序列的統(tǒng)計(jì)特性，尋找一定的方法把信源輸出符號(hào)序列變換為最短的碼字序列。出符號(hào)序列變換為最短的碼字序列。 信源編碼信源編碼 *6 信源編碼的信源編碼的基本途徑

4、基本途徑是什么是什么? ? 信源編碼的基本途徑有兩個(gè)，一是使序列中的信源編碼的基本途徑有兩個(gè)，一是使序列中的各個(gè)符號(hào)盡可能地互相獨(dú)立，即解除相關(guān)性；各個(gè)符號(hào)盡可能地互相獨(dú)立，即解除相關(guān)性；二是使編碼中各個(gè)符號(hào)出現(xiàn)的概率盡可能地相二是使編碼中各個(gè)符號(hào)出現(xiàn)的概率盡可能地相等，即概率均勻化。等，即概率均勻化。 信源編碼的信源編碼的基礎(chǔ)基礎(chǔ)是什么是什么? ? 信源編碼的信源編碼的基礎(chǔ)基礎(chǔ)是：兩個(gè)編碼定理，即是：兩個(gè)編碼定理，即無失真編碼定理和限失真編碼定理。無失真編碼定理和限失真編碼定理。信源編碼信源編碼 *7信源編碼信源編碼：以以提高通信提高通信為目的為目的, ,針對(duì)信源的編碼針對(duì)信源的編碼. .能

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

6、編碼*8 說明說明： （1 1）無失真編碼或可逆編碼只適用于離散信源。）無失真編碼或可逆編碼只適用于離散信源。 （2 2）對(duì)于連續(xù)信源，編成代碼后就無法無失真地）對(duì)于連續(xù)信源，編成代碼后就無法無失真地恢復(fù)原來的連續(xù)值，因?yàn)楹笳叩娜≈悼捎袩o限多恢復(fù)原來的連續(xù)值，因?yàn)楹笳叩娜≈悼捎袩o限多個(gè)。此時(shí)只能根據(jù)限失真編碼定理進(jìn)行限失真編個(gè)。此時(shí)只能根據(jù)限失真編碼定理進(jìn)行限失真編碼碼 。信源編碼信源編碼編碼定理證明：編碼定理證明：（1 1）必存在一種編碼方法，使代碼的平均長(zhǎng)度可）必存在一種編碼方法，使代碼的平均長(zhǎng)度可 任意接近但不能低于符號(hào)熵任意接近但不能低于符號(hào)熵（2 2）達(dá)到這目標(biāo)的途徑，就是使概率與碼

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

8、觀點(diǎn)出發(fā)“加密加密”可視為增熵的過程可視為增熵的過程, ,“解密解密”可視為減熵的過程。可視為減熵的過程。信道編碼、密碼信道編碼、密碼*10信源編碼包括兩個(gè)功能：信源編碼包括兩個(gè)功能： （1 1）將信源符號(hào)變換成適合信道傳輸?shù)姆?hào)；）將信源符號(hào)變換成適合信道傳輸?shù)姆?hào)； （2 2） 壓縮信源冗余度，提高傳輸效率。壓縮信源冗余度，提高傳輸效率。 提高傳輸效率往往削弱了其抗干擾能力。提高傳輸效率往往削弱了其抗干擾能力。提高抗提高抗干擾能力往往是以降低信息傳輸效率為代價(jià)。干擾能力往往是以降低信息傳輸效率為代價(jià)。 *11l由信源的漸近等分性導(dǎo)出了信源編碼定理：由信源的漸近等分性導(dǎo)出了信源編碼定理：只要

9、只要編碼的碼率大于編碼的碼率大于信源的熵（或熵率），則必存在信源的熵（或熵率），則必存在編譯碼方案編譯碼方案, ,使當(dāng)被編碼的信源分組長(zhǎng)趨于無窮時(shí)使當(dāng)被編碼的信源分組長(zhǎng)趨于無窮時(shí), ,譯譯碼誤差概率可以充分小碼誤差概率可以充分小, ,這解決了最優(yōu)碼的存在性問這解決了最優(yōu)碼的存在性問題。題。l怎樣構(gòu)造最優(yōu)碼？怎樣構(gòu)造最優(yōu)碼？信源編碼信源編碼*12信源編碼的分類：離散信源編碼、連續(xù)信源編碼和相信源編碼的分類：離散信源編碼、連續(xù)信源編碼和相關(guān)信源編碼三類關(guān)信源編碼三類離散信源編碼離散信源編碼：獨(dú)立信源編碼，可做到無失真編獨(dú)立信源編碼，可做到無失真編碼；碼；連續(xù)信源編碼連續(xù)信源編碼：獨(dú)立信源編碼，只能

10、做到限失真獨(dú)立信源編碼，只能做到限失真信源編碼信源編碼；相關(guān)信源編碼相關(guān)信源編碼：非獨(dú)立信源編碼。非獨(dú)立信源編碼。信源編碼的分類信源編碼的分類*13 冗余度壓縮編碼冗余度壓縮編碼: : 是可逆壓縮，經(jīng)編譯碼后可以無失真地恢復(fù)。是可逆壓縮，經(jīng)編譯碼后可以無失真地恢復(fù)。 基本途徑：基本途徑：壓縮信源的冗余度，即壓縮信源的冗余度，即 1) 1) 去除碼符號(hào)間的相關(guān)性；去除碼符號(hào)間的相關(guān)性； 2) 2) 使碼符號(hào)等概分布。使碼符號(hào)等概分布。信源編碼的分類信源編碼的分類*14熵壓縮編碼：是不可逆壓縮熵壓縮編碼：是不可逆壓縮 壓縮超過一定限度，必然帶來失真壓縮超過一定限度，必然帶來失真, ,允許的失真允許

11、的失真越大，壓縮的比例越大越大，壓縮的比例越大, ,譯碼時(shí)能按一定的失真容許譯碼時(shí)能按一定的失真容許度恢復(fù)，保留盡可能多的信息。度恢復(fù)，保留盡可能多的信息。信源編碼的分類信源編碼的分類*15l 信源編碼將信源編碼將信源符號(hào)序列信源符號(hào)序列按一定的數(shù)學(xué)規(guī)律映射成按一定的數(shù)學(xué)規(guī)律映射成碼碼符號(hào)序列符號(hào)序列。是從信源符號(hào)集到碼符號(hào)集的一種映射，它。是從信源符號(hào)集到碼符號(hào)集的一種映射，它把信源輸出的符號(hào)變換成碼元序列。把信源輸出的符號(hào)變換成碼元序列。信宿信宿信道信道信源信源編碼器編碼器譯碼器譯碼器 信源編碼器模型信源編碼器模型 譯碼是從碼符號(hào)到信源符號(hào)的映射。若要實(shí)現(xiàn)無失譯碼是從碼符號(hào)到信源符號(hào)的映射

12、。若要實(shí)現(xiàn)無失真編碼，這種映射必須是一一對(duì)應(yīng)的、可逆的。真編碼，這種映射必須是一一對(duì)應(yīng)的、可逆的。 信源編碼器模型信源編碼器模型*16編碼器編碼器12: ,.,DXx xx碼字碼字12,qXXXX12liiiiicx xx12 ,qCc ccl 將信源符號(hào)集中的符號(hào)將信源符號(hào)集中的符號(hào) （或者長(zhǎng)為（或者長(zhǎng)為n的信源符號(hào)序的信源符號(hào)序列）映射成由碼符號(hào)列）映射成由碼符號(hào) 組成的長(zhǎng)度為組成的長(zhǎng)度為 的一一對(duì)應(yīng)的的一一對(duì)應(yīng)的碼符號(hào)序列碼符號(hào)序列 。ixiXilic信源編碼器的模型信源編碼器的模型*17l編碼器輸出的碼符號(hào)序列編碼器輸出的碼符號(hào)序列 稱為稱為碼字碼字；長(zhǎng)度；長(zhǎng)度 稱為稱為碼字長(zhǎng)度，簡(jiǎn)稱

13、碼字長(zhǎng)度，簡(jiǎn)稱碼長(zhǎng)碼長(zhǎng)；全體碼字的集合記為；全體碼字的集合記為C C。l將信源符號(hào)集中的每個(gè)信源符號(hào)將信源符號(hào)集中的每個(gè)信源符號(hào) 依照固定的碼表依照固定的碼表映射成某一個(gè)碼字映射成某一個(gè)碼字 ，這樣的碼稱為，這樣的碼稱為分組碼分組碼。l只有分組碼才有對(duì)應(yīng)的碼表，而非分組碼中則不存在只有分組碼才有對(duì)應(yīng)的碼表，而非分組碼中則不存在碼表。碼表。iciXicil對(duì)于同一個(gè)信源，編碼方法是多種的。對(duì)于同一個(gè)信源，編碼方法是多種的。分組碼分組碼*18 3. 變長(zhǎng)碼變長(zhǎng)碼若碼字集合若碼字集合C中的所有碼字中的所有碼字cm (m = 1,2, ,M)，其碼長(zhǎng)，其碼長(zhǎng)不都相同不都相同，稱碼稱碼C為變長(zhǎng)碼。為變長(zhǎng)

14、碼。 2. 等長(zhǎng)碼等長(zhǎng)碼在一組碼字集合在一組碼字集合C中的所有碼字中的所有碼字cm (m = 1,2, ,M)，其碼長(zhǎng)，其碼長(zhǎng)都相都相同同，則稱這組碼，則稱這組碼C為等長(zhǎng)碼。為等長(zhǎng)碼。 1. 二元碼二元碼若碼符號(hào)集為若碼符號(hào)集為0，1，則碼字就是二元序列，稱為二元碼，則碼字就是二元序列，稱為二元碼, ,二二元碼通過二進(jìn)制信道傳輸，這是數(shù)字通信和計(jì)算機(jī)通信中最常元碼通過二進(jìn)制信道傳輸，這是數(shù)字通信和計(jì)算機(jī)通信中最常見的一種碼。見的一種碼。碼的分類碼的分類*19 4.非奇異碼非奇異碼從信源消息到碼字的映射從信源消息到碼字的映射是一一對(duì)應(yīng)的是一一對(duì)應(yīng)的，每一個(gè)不同的信源消，每一個(gè)不同的信源消息都用不

15、同的碼字對(duì)其編碼。息都用不同的碼字對(duì)其編碼。非奇異碼非奇異碼碼中所有碼字互不相同碼中所有碼字互不相同. 5.奇異碼奇異碼從信源消息到碼字的映射從信源消息到碼字的映射不是一一對(duì)應(yīng)的不是一一對(duì)應(yīng)的。奇異碼不具備惟。奇異碼不具備惟一可譯性。一可譯性。原碼的原碼的N次擴(kuò)展碼是將信源作次擴(kuò)展碼是將信源作N次擴(kuò)展得到的新信源符號(hào)序列次擴(kuò)展得到的新信源符號(hào)序列u（N）=u1 uN = (u11 u12 u1L) (uN1 uN2 uNL)，對(duì)應(yīng)碼符號(hào)序列對(duì)應(yīng)碼符號(hào)序列c（N）=c1 cN = (c11 c12 c1n) (cN1 cN2 cNn) ，記集合記集合 C (N) = c1(N), c2(N),

16、即原碼即原碼C的的N次擴(kuò)展碼。次擴(kuò)展碼。 6.原碼原碼C的的N次擴(kuò)展碼次擴(kuò)展碼*20對(duì)于等長(zhǎng)碼，若原碼是惟一可譯碼，則它的對(duì)于等長(zhǎng)碼，若原碼是惟一可譯碼，則它的N N次擴(kuò)展碼也是次擴(kuò)展碼也是惟一可譯的，而對(duì)于變長(zhǎng)碼則不盡然。惟一可譯的，而對(duì)于變長(zhǎng)碼則不盡然。 7.惟一可譯碼惟一可譯碼定義定義 若任意一串有限長(zhǎng)的碼符號(hào)序列只能被惟一地譯為對(duì)若任意一串有限長(zhǎng)的碼符號(hào)序列只能被惟一地譯為對(duì)應(yīng)的信源符號(hào)序列，則稱此碼為應(yīng)的信源符號(hào)序列，則稱此碼為惟一可譯碼惟一可譯碼。l 惟一可譯碼惟一可譯碼應(yīng)當(dāng)滿足的條件應(yīng)當(dāng)滿足的條件(1,2,., )(1,2,., )iic iqX iq碼字與信源符號(hào)一一對(duì)應(yīng)碼字與

17、信源符號(hào)一一對(duì)應(yīng)2) 不同的信源符號(hào)序列對(duì)應(yīng)不同的碼字序列。不同的信源符號(hào)序列對(duì)應(yīng)不同的碼字序列。1) *21 8. 即時(shí)碼即時(shí)碼定義定義 對(duì)于碼字對(duì)于碼字c = c1 c2 cn, ,稱稱c、 = c1 c2 ci ( (i0，只要滿足，只要滿足 則當(dāng)則當(dāng)N足夠大時(shí)，可實(shí)現(xiàn)幾乎無失真編碼，即譯碼錯(cuò)誤足夠大時(shí)，可實(shí)現(xiàn)幾乎無失真編碼，即譯碼錯(cuò)誤概率概率 PE 為任意??；為任意??； （D進(jìn)制）進(jìn)制） 反之，如果反之，如果 則不可能實(shí)現(xiàn)無失真編碼，當(dāng)則不可能實(shí)現(xiàn)無失真編碼，當(dāng)N足夠大時(shí)，譯碼錯(cuò)誤概足夠大時(shí)，譯碼錯(cuò)誤概率率 PE 為為1。()logkH XND()2logkH XNDNX等長(zhǎng)編碼定理等

18、長(zhǎng)編碼定理*42等長(zhǎng)編碼的等長(zhǎng)編碼的效率效率 （D進(jìn)制）進(jìn)制）(),logH XLD 為使編碼真正有效，必須增大信源序列的分組長(zhǎng)為使編碼真正有效，必須增大信源序列的分組長(zhǎng)度度N，這就會(huì)使編、譯碼的延時(shí)增大，同時(shí)也會(huì)使編，這就會(huì)使編、譯碼的延時(shí)增大，同時(shí)也會(huì)使編、譯碼器的復(fù)雜程度增加，因此，等長(zhǎng)編碼在冗余度、譯碼器的復(fù)雜程度增加，因此，等長(zhǎng)編碼在冗余度壓縮編碼中的理論意義遠(yuǎn)大于其實(shí)用價(jià)值。壓縮編碼中的理論意義遠(yuǎn)大于其實(shí)用價(jià)值。1()qiiiLp X k等長(zhǎng)編碼定理等長(zhǎng)編碼定理*43 如果無論怎樣編碼都是有錯(cuò)編碼，但可以使如果無論怎樣編碼都是有錯(cuò)編碼，但可以使當(dāng)?shù)鼐幋a和譯碼使譯碼錯(cuò)誤的概率當(dāng)?shù)鼐幋a

19、和譯碼使譯碼錯(cuò)誤的概率pe任意小，這任意小，這就是所謂就是所謂“漸進(jìn)無錯(cuò)編碼漸進(jìn)無錯(cuò)編碼”。( , ) ( ().nnerfPPf xx一個(gè)編譯碼方案為概率的錯(cuò)誤等長(zhǎng)編碼定理等長(zhǎng)編碼定理*44() 2,1log().nH XeDMPRMH Xn若用 進(jìn)數(shù)字表出個(gè)碼字，要使譯碼錯(cuò)誤概率只需碼率() 2,1loglog().knH XkDDMkRMDH Xnn若編碼成 長(zhǎng)的 進(jìn)碼字，則于是碼率等長(zhǎng)編碼定理等長(zhǎng)編碼定理*45( ),nnerPP xWn由漸近等分性知這樣編碼的錯(cuò)誤概率為當(dāng) 充分大時(shí)成立。等長(zhǎng)編碼定理等長(zhǎng)編碼定理nn但在實(shí)際應(yīng)用中， 不可能無限增大，這就要求我們?cè)诮o定的有限 尋求盡可能

20、好的編譯碼方案，使得碼率盡可能接近時(shí),理論值。*46l等長(zhǎng)編碼定理同樣也適用于離散平穩(wěn)有記憶信源，差等長(zhǎng)編碼定理同樣也適用于離散平穩(wěn)有記憶信源，差別是要將信源熵別是要將信源熵 改為極限熵改為極限熵 。l可以驗(yàn)證，對(duì)等長(zhǎng)信源編碼來說，要想實(shí)現(xiàn)無失真信可以驗(yàn)證，對(duì)等長(zhǎng)信源編碼來說，要想實(shí)現(xiàn)無失真信源編碼，源編碼，N常常要取非常大的值常常要取非常大的值，這在實(shí)際應(yīng)用中很，這在實(shí)際應(yīng)用中很 難實(shí)現(xiàn)。難實(shí)現(xiàn)。()H XH 等長(zhǎng)編碼在引入失真的前提下，還需要取很長(zhǎng)等長(zhǎng)編碼在引入失真的前提下，還需要取很長(zhǎng)的信源序列進(jìn)行編碼，才能達(dá)到較高的編碼效率。的信源序列進(jìn)行編碼，才能達(dá)到較高的編碼效率。既要不失真，又要

21、很高的編碼效率，只能采用變長(zhǎng)既要不失真，又要很高的編碼效率，只能采用變長(zhǎng)編碼。編碼。等長(zhǎng)編碼定理等長(zhǎng)編碼定理*47 對(duì)等長(zhǎng)碼的討論是在對(duì)等長(zhǎng)碼的討論是在N足夠大的條件下得到的結(jié)足夠大的條件下得到的結(jié)論，論，當(dāng)當(dāng)N為有限值時(shí)，則總會(huì)帶來一定程度的失真。為有限值時(shí)，則總會(huì)帶來一定程度的失真。對(duì)于變長(zhǎng)碼，往往在對(duì)于變長(zhǎng)碼，往往在N不是很大的情況下不是很大的情況下就可編出高就可編出高效且無失真的碼。效且無失真的碼。 變長(zhǎng)碼也要求原碼的變長(zhǎng)碼也要求原碼的任意任意N次擴(kuò)展碼次擴(kuò)展碼也是惟一可也是惟一可譯的。變長(zhǎng)碼分為即時(shí)碼和延長(zhǎng)碼，為保證即時(shí)譯碼，譯的。變長(zhǎng)碼分為即時(shí)碼和延長(zhǎng)碼，為保證即時(shí)譯碼，要求變長(zhǎng)惟

22、一可譯碼采用即時(shí)碼。對(duì)于變長(zhǎng)碼，要求要求變長(zhǎng)惟一可譯碼采用即時(shí)碼。對(duì)于變長(zhǎng)碼，要求整個(gè)碼集的平均碼長(zhǎng)力求最小，此時(shí)編碼效率最高。整個(gè)碼集的平均碼長(zhǎng)力求最小，此時(shí)編碼效率最高。 當(dāng)信源較復(fù)雜當(dāng)信源較復(fù)雜, ,直接畫碼樹就比較復(fù)雜。針對(duì)這直接畫碼樹就比較復(fù)雜。針對(duì)這一問題，在數(shù)學(xué)上給出一個(gè)與碼樹等效的，表達(dá)碼字一問題，在數(shù)學(xué)上給出一個(gè)與碼樹等效的，表達(dá)碼字可分離的充要條件，即著名的克拉夫特不等式?？煞蛛x的充要條件，即著名的克拉夫特不等式。變長(zhǎng)編碼變長(zhǎng)編碼*48 Kraft定理定理 即時(shí)碼存在的充要條件即時(shí)碼存在的充要條件是是 McMillan定理定理 惟一可譯碼存在的充要條件惟一可譯碼存在的充要條

23、件是是12, ,.,1.ilmiDl llD碼字字母取值于 進(jìn)字母集的即時(shí)碼，其碼字長(zhǎng)分別為時(shí)必須滿足12, ,.,1.ilmiDl llD碼字字母取值于 進(jìn)字母集的惟一可譯碼，其碼字長(zhǎng)分別為時(shí)必須滿足Kraft不等式和不等式和McMillan不等式不等式*49l上述定理是上述定理是存在性定理存在性定理當(dāng)滿足當(dāng)滿足KraftKraft（或（或McMillanMcMillan）不等式時(shí)，必然可）不等式時(shí)，必然可以構(gòu)造出即時(shí)碼（或惟一可譯碼），否則不能構(gòu)以構(gòu)造出即時(shí)碼（或惟一可譯碼），否則不能構(gòu)造出即時(shí)碼（或惟一可譯碼）。但滿足造出即時(shí)碼（或惟一可譯碼）。但滿足KraftKraft不等不等式的碼長(zhǎng)

24、集未必是最優(yōu)的，即它的平均碼長(zhǎng)未必式的碼長(zhǎng)集未必是最優(yōu)的，即它的平均碼長(zhǎng)未必是最小的。是最小的。該定理該定理不能不能作為判斷一種碼是否是即時(shí)碼（或惟作為判斷一種碼是否是即時(shí)碼（或惟一可譯碼）的判斷依據(jù)。一可譯碼）的判斷依據(jù)。KraftKraft不等式和不等式和McMillanMcMillan不等式不等式*501( )qiiiLp x l碼符號(hào)碼符號(hào)/信源符號(hào)信源符號(hào)l 平均碼長(zhǎng)平均碼長(zhǎng)L 對(duì)于給定的信源和碼符號(hào)集，若有一個(gè)惟一可譯碼，對(duì)于給定的信源和碼符號(hào)集，若有一個(gè)惟一可譯碼，其平均長(zhǎng)度其平均長(zhǎng)度 小于所有其它惟一可譯碼小于所有其它惟一可譯碼,則稱這種碼則稱這種碼為為最佳碼最佳碼或或緊致碼緊

25、致碼。 所謂所謂最佳最佳：是指在所有可能的編碼方法中，：是指在所有可能的編碼方法中，其編其編碼得到的平均碼長(zhǎng)最短碼得到的平均碼長(zhǎng)最短。 *51()()1loglogNH XLH XDNDN香農(nóng)第一定理香農(nóng)第一定理 設(shè)離散無記憶信源的熵為設(shè)離散無記憶信源的熵為H H( (X X ) )，它的，它的N N 次擴(kuò)展次擴(kuò)展信源為信源為 ，對(duì)擴(kuò)展信源，對(duì)擴(kuò)展信源 進(jìn)行編碼進(jìn)行編碼（D D進(jìn)制）進(jìn)制），總，總可以找到一種編碼方法，構(gòu)成惟一可譯碼，使平均碼可以找到一種編碼方法，構(gòu)成惟一可譯碼，使平均碼長(zhǎng)滿足長(zhǎng)滿足 NXNX 變長(zhǎng)編碼不要求所有碼字長(zhǎng)度相同變長(zhǎng)編碼不要求所有碼字長(zhǎng)度相同, ,但希望平均碼長(zhǎng)最小

26、但希望平均碼長(zhǎng)最小, ,變長(zhǎng)無失真信源編碼定理給出了在無失真編碼的前提下平均變長(zhǎng)無失真信源編碼定理給出了在無失真編碼的前提下平均碼長(zhǎng)的界限。碼長(zhǎng)的界限。變長(zhǎng)無失真信源編碼定理變長(zhǎng)無失真信源編碼定理*52*(),().()()11.DLH XlHXHXH XLl 冗余度相 一個(gè) 進(jìn)制惟一可譯碼的冗余度為其平均長(zhǎng)度與信源熵的差，即余度或冗或?qū)Χx 變長(zhǎng)編碼采用即時(shí)碼變長(zhǎng)編碼采用即時(shí)碼,力求平均碼長(zhǎng)最小力求平均碼長(zhǎng)最小,此時(shí)此時(shí)編碼效率最高，信源的冗余得到最大程度的壓縮。編碼效率最高，信源的冗余得到最大程度的壓縮。將概率大的信息符號(hào)編以短的碼字，概率小的符號(hào)將概率大的信息符號(hào)編以短的碼字，概率小的符

27、號(hào)編以長(zhǎng)的碼字，可使得平均碼字長(zhǎng)度最短。編以長(zhǎng)的碼字，可使得平均碼字長(zhǎng)度最短。冗余度冗余度*53 對(duì)于同一種信源，對(duì)于同一種信源，香農(nóng)編碼不能使平均碼長(zhǎng)達(dá)到最小，因香農(nóng)編碼不能使平均碼長(zhǎng)達(dá)到最小，因此不是最佳編碼。三種編碼法中此不是最佳編碼。三種編碼法中,以以香香農(nóng)編碼法的編碼效率最低農(nóng)編碼法的編碼效率最低，法諾編碼法也不是一種最佳編碼法，但用這種方法有時(shí)候也，法諾編碼法也不是一種最佳編碼法，但用這種方法有時(shí)候也能找到最優(yōu)碼。能找到最優(yōu)碼。 一般情況下一般情況下, ,哈夫曼編碼法得到的平均碼長(zhǎng)哈夫曼編碼法得到的平均碼長(zhǎng) 最短，即最短，即編編碼效率碼效率 最高。最高。()lo gHXLDL香農(nóng)（

28、香農(nóng)（Shannon）編碼法）編碼法法諾法諾( (Fano) )編碼法編碼法哈夫曼哈夫曼( (Huffman) )編碼法編碼法變長(zhǎng)編碼法變長(zhǎng)編碼法變長(zhǎng)碼的編碼方法變長(zhǎng)碼的編碼方法*54香農(nóng)碼編碼步驟：香農(nóng)碼編碼步驟：1. 將信源符號(hào)按概率從大到小順序排列，方便起見，令將信源符號(hào)按概率從大到小順序排列，方便起見，令 2. 按下式計(jì)算第按下式計(jì)算第i個(gè)符號(hào)對(duì)應(yīng)的碼字的碼長(zhǎng)個(gè)符號(hào)對(duì)應(yīng)的碼字的碼長(zhǎng)3. 計(jì)算第計(jì)算第i個(gè)符號(hào)的累加概率個(gè)符號(hào)的累加概率4. 將累加概率變換成將累加概率變換成二進(jìn)制小數(shù)二進(jìn)制小數(shù)，取小數(shù)點(diǎn)后，取小數(shù)點(diǎn)后li位位數(shù)作為數(shù)作為 第第i個(gè)符號(hào)的碼字。個(gè)符號(hào)的碼字。12()()()n

29、p xp xp x11()iikkPp x1log 1( )iilp x(1)(1)香農(nóng)（香農(nóng)（ShannonShannon）編碼）編碼*550.0171234567( )0.200.190.180.170.150.100.01XxxxxxxxP x例例 對(duì)如下信源進(jìn)行對(duì)如下信源進(jìn)行香農(nóng)香農(nóng)編碼編碼信源符號(hào)符號(hào)概率累加概率碼長(zhǎng)碼字x10.2002.3430000.190.22.4130010.180.392.483011x40.170.572.563100 x50.150.742.743101x60.100.893.3441110 x70.996.661111110iPix()ip xillo

30、g()ip xx2x3*56 平均碼長(zhǎng)平均碼長(zhǎng)1( )3.14/qiiiLp x l碼元符號(hào) 信源符號(hào)信源熵信源熵1()( )log( )2.61/qiiiH Xp xp x 比特 信源符號(hào)結(jié)論：結(jié)論： 1) 2) 香農(nóng)碼是即時(shí)碼，但冗余度稍大，不是最佳碼。香農(nóng)碼是即時(shí)碼，但冗余度稍大，不是最佳碼。()() 1.H XLH X2.6183.1%3.14編碼效率編碼效率*57 在眾多變長(zhǎng)碼中，哈夫曼碼是效率最高的變長(zhǎng)在眾多變長(zhǎng)碼中，哈夫曼碼是效率最高的變長(zhǎng)無失真信源編碼方法，它是一種逐個(gè)符號(hào)的編碼方無失真信源編碼方法，它是一種逐個(gè)符號(hào)的編碼方法，是在編碼理論指導(dǎo)下法，是在編碼理論指導(dǎo)下平均碼長(zhǎng)最

31、短的碼平均碼長(zhǎng)最短的碼。 原理：原理： 構(gòu)造一個(gè)碼樹。構(gòu)造一個(gè)碼樹。 (2)(2)哈夫曼哈夫曼(Huffman)(Huffman)編碼編碼*58 將信源符號(hào)按概率從大到小的順序排列，令將信源符號(hào)按概率從大到小的順序排列，令 給兩個(gè)概率最小的信源符號(hào)給兩個(gè)概率最小的信源符號(hào)xn-1和和xn各分配一個(gè)碼元各分配一個(gè)碼元“0 0”和和“1 1”，并將這兩個(gè)信源符號(hào)合并成一個(gè)新符，并將這兩個(gè)信源符號(hào)合并成一個(gè)新符號(hào)，并用這兩個(gè)最小的概率之和作為新符號(hào)的概率，號(hào)，并用這兩個(gè)最小的概率之和作為新符號(hào)的概率，結(jié)果得到一個(gè)只包含結(jié)果得到一個(gè)只包含n1個(gè)信源符號(hào)的新信源。稱個(gè)信源符號(hào)的新信源。稱為為信源的第一次

32、縮減信源信源的第一次縮減信源，用，用X X1 1表示。表示。12( )()()np xp xp x哈夫曼碼編碼步驟：哈夫曼碼編碼步驟：(2)(2)哈夫曼哈夫曼(Huffman)(Huffman)編碼編碼*59 3. 3. 將縮減信源將縮減信源X1的符號(hào)仍按概率從大到小順序排的符號(hào)仍按概率從大到小順序排 列，列，重復(fù)步驟重復(fù)步驟2 2，得到只含，得到只含n2個(gè)符號(hào)的縮減信源個(gè)符號(hào)的縮減信源X2。 4. 4. 重復(fù)上述步驟，直至縮減信源只剩兩個(gè)符號(hào)為重復(fù)上述步驟，直至縮減信源只剩兩個(gè)符號(hào)為止，此時(shí)所剩兩個(gè)符號(hào)的概率之和必為止，此時(shí)所剩兩個(gè)符號(hào)的概率之和必為1 1。然后從。然后從最后一級(jí)縮減信源開始

33、，依編碼路徑向前返回，就最后一級(jí)縮減信源開始，依編碼路徑向前返回，就得到各信源符號(hào)所對(duì)應(yīng)的碼字。得到各信源符號(hào)所對(duì)應(yīng)的碼字。(2)(2)哈夫曼哈夫曼(Huffman)(Huffman)編碼編碼*6012345:0.4:0.2:0.2:0.1:0.1xxxxx014 . 02 . 02 . 02 . 0014 . 04 . 02 . 0016 . 04 . 00111c 201c 3000c 40010c 50011c 1( )2.2qiiiLp x l碼符號(hào)碼符號(hào)/信源符號(hào)信源符號(hào)*6112345:0.4:0.2:0.2:0.1:0.1xxxxx014 . 02 . 02 . 02 . 001

34、4 . 04 . 02 . 0016 . 04 . 001100c 210c 311c 4010c 5011c 1( )2.2qiiiLp x l碼符號(hào)碼符號(hào)/信源符號(hào)信源符號(hào)*62討論：討論：1) 1) 兩種方法平均碼長(zhǎng)相等。兩種方法平均碼長(zhǎng)相等。2) 2) 計(jì)算兩種碼的碼長(zhǎng)方差：計(jì)算兩種碼的碼長(zhǎng)方差：52211( )()1.36iiip xlL52221( )()0.16iiip xlL第二種方法編出的碼碼字長(zhǎng)度變化較小，便于實(shí)現(xiàn)。第二種方法編出的碼碼字長(zhǎng)度變化較小，便于實(shí)現(xiàn)。*631234567( )0.200.190.180.170.150.100.01XxxxxxxxP x解解 哈夫

35、曼編碼結(jié)果：哈夫曼編碼結(jié)果：12345671011000001 01001100111xxxxxxx信源符號(hào)碼字例例 對(duì)如下信源進(jìn)行哈夫曼編碼對(duì)如下信源進(jìn)行哈夫曼編碼*64l平均碼長(zhǎng)為平均碼長(zhǎng)為l信源熵為信源熵為l編碼效率為編碼效率為71( )2.72/iiiLp x l碼元符號(hào) 信源符號(hào)2.6196.0%2.7271()( )log( )2.61/iiiH Xp xp x 比特 信源符號(hào)*65注：哈夫曼編碼后的碼字不是惟一的。注：哈夫曼編碼后的碼字不是惟一的。1 1）每次對(duì)縮減信源兩個(gè)概率最小的符號(hào)）每次對(duì)縮減信源兩個(gè)概率最小的符號(hào)分配分配“0 0”或或“1 1”碼元碼元是任意的是任意的，所

36、以可得到不同的碼字。不同的碼元分配，得，所以可得到不同的碼字。不同的碼元分配，得到的具體碼字不同，但碼長(zhǎng)不變，平均碼長(zhǎng)也不變，所以到的具體碼字不同，但碼長(zhǎng)不變，平均碼長(zhǎng)也不變，所以沒有本質(zhì)區(qū)別。沒有本質(zhì)區(qū)別。2 2）縮減信源時(shí)，）縮減信源時(shí)，若合并后的概率與其它概率相等，這幾個(gè)概若合并后的概率與其它概率相等，這幾個(gè)概率的次序可任意排列率的次序可任意排列，但得到的碼字不相同，但得到的碼字不相同, ,對(duì)應(yīng)的碼長(zhǎng)也對(duì)應(yīng)的碼長(zhǎng)也不相同不相同, ,但平均碼長(zhǎng)不變。但平均碼長(zhǎng)不變。哈夫曼編碼哈夫曼編碼*66 第一，哈夫曼編碼實(shí)際上構(gòu)造了一個(gè)碼樹，碼第一，哈夫曼編碼實(shí)際上構(gòu)造了一個(gè)碼樹，碼樹從最上層的端點(diǎn)開

37、始構(gòu)造，直到樹根結(jié)束，最后樹從最上層的端點(diǎn)開始構(gòu)造，直到樹根結(jié)束，最后得到一個(gè)橫放的碼樹，因此，編出的碼是即時(shí)碼。得到一個(gè)橫放的碼樹，因此，編出的碼是即時(shí)碼。 第二，哈夫曼編碼采用概率匹配方法來決定各第二，哈夫曼編碼采用概率匹配方法來決定各碼字的碼長(zhǎng)，概率大的符號(hào)對(duì)應(yīng)于短碼，概率小的碼字的碼長(zhǎng)，概率大的符號(hào)對(duì)應(yīng)于短碼，概率小的符號(hào)對(duì)應(yīng)于長(zhǎng)碼，從而使平均碼長(zhǎng)最小。符號(hào)對(duì)應(yīng)于長(zhǎng)碼，從而使平均碼長(zhǎng)最小。 第三，每次對(duì)概率最小的兩個(gè)符號(hào)求概率之和第三，每次對(duì)概率最小的兩個(gè)符號(hào)求概率之和形成縮減信源時(shí)形成縮減信源時(shí),就構(gòu)造出兩個(gè)樹枝，由于給兩個(gè)樹就構(gòu)造出兩個(gè)樹枝，由于給兩個(gè)樹枝賦碼元時(shí)是任意的枝賦碼元時(shí)

38、是任意的,因此編出的碼字并不惟一。因此編出的碼字并不惟一。哈夫曼編碼的基本特點(diǎn)哈夫曼編碼的基本特點(diǎn)*67 哈夫曼哈夫曼優(yōu)點(diǎn)：優(yōu)點(diǎn)：編碼方便易行，效率高編碼方便易行，效率高。 在哈夫曼編碼過程中，對(duì)縮減信源符號(hào)按概在哈夫曼編碼過程中，對(duì)縮減信源符號(hào)按概率由大到小的順序重新排列時(shí)，應(yīng)使率由大到小的順序重新排列時(shí)，應(yīng)使合并后的新合并后的新符號(hào)盡可能排在靠前的位置符號(hào)盡可能排在靠前的位置，這樣可使合并后的，這樣可使合并后的新符號(hào)重復(fù)編碼次數(shù)減少新符號(hào)重復(fù)編碼次數(shù)減少, ,使短碼得到充分利用。使短碼得到充分利用。 通過最佳的信源編碼雖然可以消除信源的冗通過最佳的信源編碼雖然可以消除信源的冗余度，提高信息

39、傳輸率，但結(jié)果卻使碼變得十分余度，提高信息傳輸率，但結(jié)果卻使碼變得十分“脆弱脆弱”，經(jīng)不起信道中噪聲的干擾，容易造成，經(jīng)不起信道中噪聲的干擾，容易造成譯碼錯(cuò)誤。譯碼錯(cuò)誤。哈夫曼編碼的優(yōu)點(diǎn)哈夫曼編碼的優(yōu)點(diǎn)*68 （1 1）如果對(duì)單個(gè)字母編碼時(shí)，平均碼字長(zhǎng)與理論）如果對(duì)單個(gè)字母編碼時(shí)，平均碼字長(zhǎng)與理論上的最優(yōu)壓縮率可能還有一定距離（可能差上的最優(yōu)壓縮率可能還有一定距離（可能差1比比特）。特）。 當(dāng)信源熵當(dāng)信源熵H(X)很大時(shí)，這很大時(shí)，這1比特比特可能無關(guān)重要；可能無關(guān)重要；但當(dāng)?shù)?dāng)H(X)本身就接近本身就接近1比特時(shí)，這額外的比特時(shí)，這額外的1比特可比特可能決定了編碼的碼率，這顯然不經(jīng)濟(jì)，因此要

40、進(jìn)能決定了編碼的碼率，這顯然不經(jīng)濟(jì)，因此要進(jìn)一步提高編碼效率，使碼率盡可能接近信源熵，一步提高編碼效率，使碼率盡可能接近信源熵，則仍需則仍需對(duì)長(zhǎng)的信源序列來編碼對(duì)長(zhǎng)的信源序列來編碼。 哈夫曼編碼的缺點(diǎn)哈夫曼編碼的缺點(diǎn)*69（2 2）哈夫曼哈夫曼編碼算法是從下而上地構(gòu)造碼樹編碼算法是從下而上地構(gòu)造碼樹, ,當(dāng)信源字母集很大時(shí)當(dāng)信源字母集很大時(shí), ,這種算法甚為不便。另這種算法甚為不便。另外外, ,哈夫曼編碼需要知道信源的概率分布哈夫曼編碼需要知道信源的概率分布, ,這這在實(shí)際中有時(shí)是比較困難的。在實(shí)際中有時(shí)是比較困難的。哈夫曼編碼的缺點(diǎn)哈夫曼編碼的缺點(diǎn)*70(3)().()logkkkkkkxl

41、xpLHXLlpHX 由哈夫曼編碼方法可以看到，當(dāng)信源字母 對(duì)應(yīng)的碼長(zhǎng)與 的概率滿足關(guān)系時(shí)，編碼后的平均碼長(zhǎng) 是理論上可達(dá)到的最短平均碼長(zhǎng)，即信源的熵率如果不滿足該條件時(shí)（稱統(tǒng)計(jì)失配）， 與就有差距，這時(shí)編碼性能下降。哈夫曼編碼的缺點(diǎn)哈夫曼編碼的缺點(diǎn)*71 （4 4）從硬件實(shí)現(xiàn)上來看，哈夫曼編碼有變長(zhǎng)碼）從硬件實(shí)現(xiàn)上來看，哈夫曼編碼有變長(zhǎng)碼的固有缺點(diǎn)：的固有缺點(diǎn)：需緩沖存儲(chǔ)器需緩沖存儲(chǔ)器。 因?yàn)橐话阈旁春托诺纻鬏斝盘?hào)是恒速的，但因?yàn)橐话阈旁春托诺纻鬏斝盘?hào)是恒速的，但經(jīng)變長(zhǎng)編碼后信源編碼的每秒輸出的比特?cái)?shù)就不經(jīng)變長(zhǎng)編碼后信源編碼的每秒輸出的比特?cái)?shù)就不是常量，不能直接用信道來傳輸，為適應(yīng)信道必是常

42、量，不能直接用信道來傳輸，為適應(yīng)信道必須加緩沖設(shè)備，將編碼器輸出暫存在緩沖器中，須加緩沖設(shè)備，將編碼器輸出暫存在緩沖器中，然后再接到信道去傳送。然后再接到信道去傳送。 從理論上講當(dāng)存儲(chǔ)器容量為無限時(shí)，信源輸從理論上講當(dāng)存儲(chǔ)器容量為無限時(shí)，信源輸出與信道傳輸之間才能取得平衡，當(dāng)存儲(chǔ)器容量出與信道傳輸之間才能取得平衡，當(dāng)存儲(chǔ)器容量有限時(shí)，這種平衡不一定能保持。有限時(shí)，這種平衡不一定能保持。哈夫曼編碼的缺點(diǎn)哈夫曼編碼的缺點(diǎn)*72 當(dāng)信源連續(xù)輸出低概率符號(hào)，其對(duì)應(yīng)的碼字較長(zhǎng)，輸入當(dāng)信源連續(xù)輸出低概率符號(hào)，其對(duì)應(yīng)的碼字較長(zhǎng)，輸入緩沖器的比特?cái)?shù)大于信道能輸出的比特?cái)?shù)，會(huì)造成存儲(chǔ)器溢緩沖器的比特?cái)?shù)大于信道能

43、輸出的比特?cái)?shù)，會(huì)造成存儲(chǔ)器溢出。出。 反之，當(dāng)信源連續(xù)輸出高概率符號(hào)，其對(duì)應(yīng)的碼字較短，反之，當(dāng)信源連續(xù)輸出高概率符號(hào)，其對(duì)應(yīng)的碼字較短，輸入緩沖器的比特?cái)?shù)小于信道能輸出的比特?cái)?shù)，會(huì)造成存儲(chǔ)輸入緩沖器的比特?cái)?shù)小于信道能輸出的比特?cái)?shù)，會(huì)造成存儲(chǔ)器取空，信道上無信息可送，而使信道上出現(xiàn)連個(gè)器取空，信道上無信息可送，而使信道上出現(xiàn)連個(gè)0 0或連個(gè)或連個(gè)1 1，導(dǎo)致誤譯。導(dǎo)致誤譯。 因此因此需設(shè)計(jì)適當(dāng)?shù)拇鎯?chǔ)器容量需設(shè)計(jì)適當(dāng)?shù)拇鎯?chǔ)器容量（降低成本，增加容量），（降低成本，增加容量），并把信源發(fā)出的信息分段發(fā)送，或經(jīng)常檢查存儲(chǔ)器，如有溢并把信源發(fā)出的信息分段發(fā)送，或經(jīng)常檢查存儲(chǔ)器，如有溢出，就轉(zhuǎn)停，如有取

44、空，則加入空間符號(hào)。出，就轉(zhuǎn)停，如有取空，則加入空間符號(hào)。 哈夫曼編碼的缺點(diǎn)哈夫曼編碼的缺點(diǎn)*73（5 5）差錯(cuò)擴(kuò)散）差錯(cuò)擴(kuò)散: : 對(duì)變長(zhǎng)碼一旦產(chǎn)生誤碼對(duì)變長(zhǎng)碼一旦產(chǎn)生誤碼, ,某個(gè)碼字的前綴某個(gè)碼字的前綴部分可能成為另一個(gè)碼字而發(fā)生錯(cuò)譯部分可能成為另一個(gè)碼字而發(fā)生錯(cuò)譯, ,并可導(dǎo)并可導(dǎo)致錯(cuò)誤后傳致錯(cuò)誤后傳. .哈夫曼編碼的缺點(diǎn)哈夫曼編碼的缺點(diǎn)*74法諾法諾(Fano)(Fano)碼編碼步驟：碼編碼步驟：將概率按從大到小的順序排列，令將概率按從大到小的順序排列，令將依次排列的信源符號(hào)按概率分成兩組，使每組概率和盡可將依次排列的信源符號(hào)按概率分成兩組，使每組概率和盡可能接近或相等。能接近或相等

45、。給每一組分配一位碼元給每一組分配一位碼元“0 0”或或“1 1”。將每一分組再按同樣方法劃分，重復(fù)步驟將每一分組再按同樣方法劃分，重復(fù)步驟2 2和和3 3，直至概率不，直至概率不再可分為止。由此即可構(gòu)造一個(gè)碼樹，所有終端節(jié)點(diǎn)上的碼再可分為止。由此即可構(gòu)造一個(gè)碼樹，所有終端節(jié)點(diǎn)上的碼字組成法諾碼。字組成法諾碼。 原理原理：它是通過構(gòu)造一個(gè)碼樹，編出的碼是即時(shí)碼，但不一定：它是通過構(gòu)造一個(gè)碼樹，編出的碼是即時(shí)碼，但不一定是最佳碼。是最佳碼。12( )()()qp xp xp x(3)(3)法諾法諾(Fano)(Fano)編碼編碼*75解解信源符號(hào)符號(hào)概率第一次分組第二次分組第三次分組第四次分組碼

46、字碼長(zhǎng)0.20000020.191001030.18101130.17101020.151011030.1010111040.011111141x2x4x3x5x6x7x1234567( )0.200.190.180.170.150.100.01XxxxxxxxP x例例 對(duì)如下信源進(jìn)行法諾編碼對(duì)如下信源進(jìn)行法諾編碼*76l平均碼長(zhǎng)為平均碼長(zhǎng)為l信源熵為信源熵為l編碼效率為編碼效率為2.6195.3%2.7471()( )log( )2.61/iiiH Xp xp x 比特 信源符號(hào)71( )2.74/iiiLp x l碼元符號(hào) 信源符號(hào)*77 (1) (1) 法諾編碼在構(gòu)造碼樹時(shí)，是從樹根開

47、始到終端法諾編碼在構(gòu)造碼樹時(shí)，是從樹根開始到終端節(jié)點(diǎn)結(jié)束，這節(jié)點(diǎn)結(jié)束，這與哈夫曼編碼相反與哈夫曼編碼相反； (2) (2) 由于賦碼元時(shí)的任意性，因此法諾編碼編出的由于賦碼元時(shí)的任意性，因此法諾編碼編出的碼字碼字不惟一不惟一； (3) (3) 法諾編碼不全是按法諾編碼不全是按“概率大碼長(zhǎng)小、概率小碼概率大碼長(zhǎng)小、概率小碼長(zhǎng)大長(zhǎng)大”來決定碼長(zhǎng)，有時(shí)會(huì)出現(xiàn)概率小碼長(zhǎng)反而小來決定碼長(zhǎng)，有時(shí)會(huì)出現(xiàn)概率小碼長(zhǎng)反而小的情況，因此的情況，因此平均碼長(zhǎng)一般不會(huì)最小平均碼長(zhǎng)一般不會(huì)最小。法諾編碼法諾編碼的特點(diǎn)的特點(diǎn)*78l香農(nóng)碼、法諾碼、哈夫曼碼都考慮了香農(nóng)碼、法諾碼、哈夫曼碼都考慮了信源的統(tǒng)計(jì)特性信源的統(tǒng)計(jì)特

48、性, ,使經(jīng)常出現(xiàn)的信源符號(hào)對(duì)應(yīng)較短的碼字使經(jīng)常出現(xiàn)的信源符號(hào)對(duì)應(yīng)較短的碼字, ,使信源的平均使信源的平均碼長(zhǎng)縮短，從而實(shí)現(xiàn)了對(duì)信源的壓縮碼長(zhǎng)縮短，從而實(shí)現(xiàn)了對(duì)信源的壓縮. .l香農(nóng)編碼結(jié)果香農(nóng)編碼結(jié)果惟一惟一, ,但在很多情況下但在很多情況下編碼效率不高編碼效率不高. .l法諾碼和哈夫曼碼的編碼方法都法諾碼和哈夫曼碼的編碼方法都不惟一不惟一. .l法諾碼比較適合于對(duì)法諾碼比較適合于對(duì)分組概率相等或接近的信源編碼分組概率相等或接近的信源編碼. .l哈夫曼哈夫曼碼對(duì)信源的統(tǒng)計(jì)特性沒有特殊要求碼對(duì)信源的統(tǒng)計(jì)特性沒有特殊要求, ,編碼效率編碼效率比較高，對(duì)編碼設(shè)備的要求也比較簡(jiǎn)單，因此比較高，對(duì)編碼

49、設(shè)備的要求也比較簡(jiǎn)單，因此綜合性綜合性能優(yōu)于香農(nóng)碼和法諾碼能優(yōu)于香農(nóng)碼和法諾碼. .三種三種編碼編碼方法的對(duì)比方法的對(duì)比*79 cabcedeacacdeddaaabaababaaabbacdebaceacabcedeacacdeddaaabaababaaabbacdebaceada da 共共4040個(gè)字母?jìng)€(gè)字母 采用法諾編碼法采用法諾編碼法 頻度頻度a - 16a - 16，b - 7b - 7，c - 6c - 6，d - 6d - 6，e - 5 e - 5 1) 1) 將給定符號(hào)按照其頻率從大到小排序。將給定符號(hào)按照其頻率從大到小排序。a a 16 b - 7 c - 6 d - 6 e 16 b - 7 c - 6 d - 6 e 5 52) 2) 將序列分成左右兩部分，使得左部頻率總和將序列分成左右兩部分，使得左部頻率總和盡可能接近右部頻率總和。盡可能接近右部頻率總和。(a, b), (