信息編碼之M進(jìn)制的哈弗曼編碼1

1、青島農(nóng)業(yè)大學(xué)課 程 論 文（設(shè)計(jì)） 題 目： M進(jìn)制哈夫曼編碼的分析與實(shí)現(xiàn) 姓 名： 學(xué) 院： 理學(xué)與信息科學(xué)學(xué)院 專 業(yè)： 信息與計(jì)算科學(xué)專業(yè) 班 級(jí)： 學(xué) 號(hào)： 指導(dǎo)教師： 2014年 6 月26 日目 錄摘要1Abstract2引言31 課題描述32 信源編碼的基本概念42.1 通信系統(tǒng)的模塊42.2 信息的度量與編碼42.3 無失真編碼算法63 信源最佳化84 哈夫曼編碼特點(diǎn)及應(yīng)用95 編碼 105.1 二元哈夫曼編碼規(guī)則 105.2 M進(jìn)制哈夫曼編碼115.3 C+程序146 總結(jié) 19參考文獻(xiàn) 20M進(jìn)制哈夫曼編碼的分析與實(shí)現(xiàn) 信息與計(jì)算科學(xué) 李棟 指導(dǎo)教師 吳慧摘要：哈夫曼編碼(

2、Huffman Coding)是一種編碼方式，也是可變字長(zhǎng)編碼(VLC)的一種。這種方法完全依據(jù)字符出現(xiàn)的概率來構(gòu)造異字頭的平均長(zhǎng)度最短的碼字，有時(shí)稱之為最佳編碼，一般就叫作哈夫曼編碼。對(duì)于M進(jìn)制哈弗曼編碼，為了提高編碼效率，就要使長(zhǎng)碼的符號(hào)數(shù)量盡量少、概率盡量小，所以應(yīng)使合并的信源符號(hào)位于縮減信源序列盡可能高的位置上，以減少再次合并的次數(shù)，充分利用短碼。本文將采用三進(jìn)制哈夫曼編碼作為例子來詮釋M進(jìn)制哈夫曼編碼。在三進(jìn)制哈夫曼編碼中，得出碼字、平均碼長(zhǎng)和編碼效率，構(gòu)造哈夫曼樹，沿著根節(jié)點(diǎn)到葉節(jié)點(diǎn)從左到右依次為0、1、2，保證平均碼長(zhǎng)最小。在本文中采用Visual C+6.0進(jìn)行編程，此程序中具

3、有輸入字符集大小和權(quán)值大小，構(gòu)造哈夫曼樹，并對(duì)用戶輸入的字符串進(jìn)行編碼等功能。關(guān)鍵詞：哈弗曼編碼；信源；哈夫曼樹；Visual C+6.0；Analysis and implementation of M binary Huffman codingStudent majoring in Information and Computing Sciences Li DongTutor Wu HuiAbstract：The Huffman code (Huffman Coding) is a kind of encoding, and variable length coding(VLC) is a

4、 kind of. The average length of this method on the basis of fully probabilisticcharacter appears to construct different prefix the shortest codeword, sometimes called the best code, generally known as Huffman coding. For the M systemHavermann coding, in order to improve the coding efficiency, it is

5、necessary to makethe number of long code symbols as little as possible, probability as small as possible,so should make the source symbols in the source sequence with reduced as far as possible the high position, to reduce the number of merged again, make full use of short code.This paper will use t

6、he three binary Huffman coding as an example to explain the Mbinary Huffman coding.In the three binary Huffman coding, the code word, the average code length and coding efficiency, Huffman tree structure, along the root node to the leaf nodes from left to right: 0, 1, 2, the average code length mini

7、mum. In this paper by using VisualC+6.0 programming, the input character set size and weight with this program,Huffman tree structure, and code functions for string input by the user.Key words: The Hoffman code;Source;Huffman tree;Visual C+6.0引言在這個(gè)信息量爆炸的時(shí)代，凡是能載荷一定信息量，且碼字的平均長(zhǎng)度最短，可分離的變長(zhǎng)碼的碼字集合稱為最佳變長(zhǎng)碼。為

8、此，必須將概率大的信息符號(hào)編以短的碼字，概率小的符號(hào)編以長(zhǎng)的碼字，使得平均碼字最短。能獲得最佳碼的編碼方法主要有：香農(nóng)（Shannon）、費(fèi)諾（Fano）、哈夫曼（Huffman）編碼等。哈夫曼(Huffman)編碼是一種常用的壓縮編碼方法，是Huffman于1952年為壓縮文本文件建立的。它的基本原理是頻繁使用的數(shù)據(jù)用較短的代碼代替，較少使用的數(shù)據(jù)用較長(zhǎng)的代碼代替，每個(gè)數(shù)據(jù)的代碼各不相同。哈夫曼壓縮是個(gè)無損的壓縮算法，一般用來壓縮文本和程序文件。哈夫曼壓縮屬于可變代碼長(zhǎng)度算法一族。意思是個(gè)體符號(hào)用一個(gè)特定長(zhǎng)度的位序列替代。因此，在文件中出現(xiàn)頻率高的符號(hào)，使用短的位序列，而那些很少出現(xiàn)的符號(hào)，

9、則用較長(zhǎng)的位序列。哈夫曼編碼是哈夫曼樹的一個(gè)應(yīng)用，是一種最優(yōu)的前綴技術(shù)，然而其存在的不足卻制約了它的直接應(yīng)用。首先，其解碼時(shí)間為O(lavg)，其中l(wèi)avg為碼字的平均長(zhǎng)度；其次，更為重要的是，解碼器需要知道哈夫曼編碼樹的結(jié)構(gòu)，因而編碼器必須為解碼器保存或傳輸哈夫曼編碼樹。對(duì)于小量數(shù)據(jù)的壓縮而言，這是很大的開銷。因而，應(yīng)用哈夫曼編碼的關(guān)鍵是如何降低哈夫曼編碼樹的存儲(chǔ)空間。目前流行的很多壓縮方法都是用了該技術(shù)，如GZIB、ZLIB、PNC等。1 課題描述在通信的數(shù)字化過程中，對(duì)于時(shí)間連續(xù)和取值連續(xù)的原始語音和圖像等模擬信號(hào)來說，如果要以數(shù)字方式進(jìn)行傳輸，在發(fā)送端必須首先進(jìn)行模/數(shù)(A/D)變換，

10、將原始信號(hào)轉(zhuǎn)換為時(shí)間離散和取值離散的數(shù)字信號(hào)。模擬信號(hào)數(shù)字化之后一般會(huì)導(dǎo)致傳輸信號(hào)的帶寬明顯增加，這樣就會(huì)占用更多的信道資源，使得傳輸效率降低，或者無法實(shí)現(xiàn)實(shí)時(shí)傳輸。為了提高傳輸效率，一方面需要采用壓縮編碼技術(shù)，在保證一定信號(hào)質(zhì)量的前提下，盡可能地去除信號(hào)中的冗余信息，從而減少信號(hào)速率和傳輸所用帶寬。另一方面，即使是原本就以數(shù)字形式存在的數(shù)據(jù)和文字信息，也同樣存在一個(gè)需要通過壓縮編碼降低信息冗余提高傳輸效率的問題。由于這些處理都是針對(duì)信源發(fā)送信息所進(jìn)行的，因此一般將其稱為信源編碼。信源編碼的基本目的是提高碼字序列中碼元的平均信息量，那么，一切旨在減少剩余度而對(duì)信源輸出符號(hào)序列所施行的變換或處理

11、，都可以在這種意義下歸入信源編碼的范疇，例如過濾、預(yù)測(cè)、域變換和數(shù)據(jù)壓縮等。作為現(xiàn)代數(shù)據(jù)無損壓縮的靈魂算法，哈夫曼編碼正廣泛應(yīng)用于各種圖像、音頻、視頻及各種多媒體信息的壓縮環(huán)境中。2 信源編碼的基本概念2.1 通信系統(tǒng)的模塊信源信源編碼信道編碼信道信道譯碼信源譯碼信宿噪聲2.2 信息的度量與編碼信息是指消息中包含的有效內(nèi)容，度量信息量的原則首先是能度量任何消息并與消息的種類無關(guān)，其次度量方法應(yīng)該與消息的重要程度無關(guān)，最后消息中所含信息量和消息內(nèi)容的不確定性有關(guān)。信息熵的輸出可以用隨機(jī)過程來描述。對(duì)于一個(gè)離散無記憶平穩(wěn)隨機(jī)過程，其信息量（熵）定義為： 其中X表示信源取值集合，p(x)是信源取值x

12、的概率。 信源編碼是數(shù)字通信中的重要環(huán)節(jié)，它的主要目的是減少冗余，提高編碼效率。信源編碼可分為兩類：無失真編碼和有失真編碼。無失真編碼只對(duì)信源冗余度進(jìn)行壓縮，不會(huì)改變信源的熵，又稱冗余度壓縮編碼，它能保證碼元序列經(jīng)譯碼后能無失真的恢復(fù)成信源符號(hào)序列，如哈夫曼編碼，香農(nóng)編碼。有失真編碼在允許的失真范圍內(nèi)把編碼后的信息率壓縮到最小，有失真信源編碼的失真范圍受限，所以又稱為限失真信源編碼。信源編碼就是把信源符號(hào)序列變換到碼符號(hào)序列的一種映射。若要實(shí)現(xiàn)無失真編碼，那么這種映射必須是一一對(duì)應(yīng)的、可逆的。一般來說，人們總希望把信源所有的信息毫無保留的傳遞到接受端，即實(shí)現(xiàn)無失真?zhèn)鬏?，所以首先要?duì)信源實(shí)現(xiàn)無失

13、真編碼。信源編碼有以下三種主要方法： （1）匹配編碼根據(jù)信源符號(hào)的概率不同，編碼的碼長(zhǎng)不同,這樣使平均碼長(zhǎng)最短。將要講到的哈夫曼編碼就是概率匹配編碼。 （2）變換編碼先對(duì)信號(hào)進(jìn)行變換，從一種信號(hào)空間變換為另一種信號(hào)空間，然后針對(duì)變換后的信號(hào)進(jìn)行編碼。一般是把分布在時(shí)空域的信號(hào)（如時(shí)域的語音信號(hào)和平面空間的圖像信號(hào)）映射到變換域（如頻域的頻譜信號(hào)和其他正交矢量空間域），原來相關(guān)性很強(qiáng)的原始信號(hào)經(jīng)過變換后，得到的變換域系數(shù)相互獨(dú)立，并且能量集中在少數(shù)低序系數(shù)上，這樣只需對(duì)少量的變換域的系數(shù)進(jìn)行編碼，達(dá)到數(shù)據(jù)壓縮的目的。常用的變換編碼有DFT、沃爾什變換、小波變換等。 (3)識(shí)別編碼識(shí)別編碼主要用于

14、印刷或打字機(jī)等有標(biāo)準(zhǔn)形狀的文字、符號(hào)和數(shù)據(jù)的編碼，比如中文文字和語音的識(shí)別。后兩種信源編碼均為有失真的信源編碼。最原始的信源編碼就是莫爾斯電碼，另外還有ASCII碼和電報(bào)碼都是信源編碼。但現(xiàn)代通信應(yīng)用中常見的信源編碼方式有：哈夫曼編碼、算術(shù)編碼、L-Z編碼，這三種都是無損編碼。而哈夫曼編碼作為變長(zhǎng)碼滿足變長(zhǎng)信源編碼定理。該編碼定理是香農(nóng)信息論中非常重要的一個(gè)定理，它指出，要做到無失真的信源編碼，信源每個(gè)符號(hào)所需要的平均碼元數(shù)就是信源的熵值，如果小于這個(gè)值，則唯一可譯碼不存在，可見，熵是無失真信源編碼的極限值。定理還指出，通過對(duì)擴(kuò)展信源進(jìn)行編碼，當(dāng)N趨向于無窮時(shí)，平均碼長(zhǎng)可以趨進(jìn)該極限值。還可以

15、證明，如果我們不確切知道信源的概率分布，我們用估計(jì)的概率分布去進(jìn)行編碼時(shí)，平均碼長(zhǎng)會(huì)加長(zhǎng)，但是如果估計(jì)的偏差不大的話，平均碼長(zhǎng)也不會(huì)增加太多。2.3 無失真編碼算法編碼器：編碼器可以看作這樣一個(gè)系統(tǒng)，它的輸入端為原始信源S，其符號(hào)集為S,而信道所能傳輸?shù)姆?hào)集為X，編碼器的功能是用符號(hào)集X中的元素，將原始信源的符號(hào)Si變換為相應(yīng)的碼字符號(hào)Wi,編碼器輸出端得符號(hào)集為C。 編碼器X S C 奇異碼與非奇異碼若一種分組碼中所有碼字都不相等，則稱分組碼為非奇異碼，否則為奇異碼。唯一可譯碼與非唯一可譯碼任意有限長(zhǎng)碼元序列，如果只能唯一分割成一個(gè)個(gè)碼字便稱為唯一可譯碼。唯一可譯碼得物理意義是指不僅要求不

16、同的碼字表示不同的信源符號(hào)，而且還要求對(duì)由信源符號(hào)構(gòu)成的符號(hào)序列進(jìn)行編碼時(shí)，在接受端仍能正確譯碼而不發(fā)生混淆。唯一可譯碼首先是非奇異碼且任意有限長(zhǎng)的碼字序列不會(huì)雷同。即時(shí)碼與非即時(shí)碼無需考慮后續(xù)的碼符號(hào)就可以從碼符號(hào)序列中譯出碼字，這樣的唯一可譯碼稱為即時(shí)碼變長(zhǎng)碼及變長(zhǎng)編碼定理信源符號(hào)數(shù)、碼符號(hào)數(shù)、碼字長(zhǎng)度之間滿足什么條件才可以構(gòu)成即時(shí)碼和唯一可譯碼呢？Kraft不等式和McMillan不等式回答了這個(gè)問題。這兩個(gè)不等式在形式上是完全一樣的。設(shè)信源符號(hào)集為，碼符號(hào)集為，對(duì)信源進(jìn)行編碼，得到的碼為，碼長(zhǎng)分別為。即時(shí)碼存在的充要條件是： 這稱為Kraft不等式。由上式可知，給定r和q，只要允許碼字

17、長(zhǎng)度可以足夠長(zhǎng)，則碼長(zhǎng)總可以滿足Kraft不等式而得到即時(shí)碼，Kraft不等式指出了即時(shí)碼的碼長(zhǎng)必須滿足的條件。后來McMillan證明對(duì)于唯一可譯碼得碼長(zhǎng)也必須滿足此不等式。在碼長(zhǎng)的選擇上唯一可譯碼并不比即時(shí)碼有更寬松的條件。對(duì)于唯一可譯碼，該不等式又稱為McMillan不等式。唯一可譯碼存在的充要條件是： 其中r為碼符號(hào)個(gè)數(shù)，為碼字長(zhǎng)度，q為信源符號(hào)個(gè)數(shù)無失真變長(zhǎng)信源編碼定理離散無記憶信源S的N次擴(kuò)展信源，其熵為，并且編碼器的碼元符號(hào)集為A：對(duì)信源進(jìn)行編碼，總可以找到一種編碼方法，構(gòu)成唯一可譯碼，使信源S中每個(gè)符號(hào)所需要的平均碼長(zhǎng)滿足當(dāng)時(shí)則有式中，其中是擴(kuò)展信源的信源符號(hào)所對(duì)應(yīng)的碼字長(zhǎng)度，

18、因此是擴(kuò)展信源中每個(gè)符號(hào)的平均碼長(zhǎng)，而是信源S中單個(gè)信源符號(hào)所需的平均碼長(zhǎng)。這里要注意與的區(qū)別：它們都是單個(gè)信源符號(hào)所需的碼符號(hào)的平均數(shù)，但是的含義是，為了得到這個(gè)平均值，不是對(duì)單個(gè)信源符號(hào)進(jìn)行編碼，而是對(duì)N個(gè)信源符號(hào)序列進(jìn)行編碼，然后對(duì)N求平均。該定理指出，要做到無失真信源編碼，每個(gè)信源符號(hào)平均所需最少的r元碼元數(shù)就是信源的熵值。若編碼的平均碼長(zhǎng)小于信源的熵值，則唯一可譯碼不存在，在譯碼或反變換時(shí)必然要帶來失真或差錯(cuò)，同時(shí)定理還指出，通過對(duì)擴(kuò)展信源進(jìn)行變長(zhǎng)編碼，當(dāng)時(shí)，平均碼長(zhǎng)可達(dá)到這個(gè)極限值?？梢?，信源的信息熵H(S)是無失真信源編碼碼長(zhǎng)的極限值，也可認(rèn)為信源熵是表示每個(gè)信源符號(hào)平均所需最少

19、的碼元符號(hào)數(shù)。3 信源最佳化通信系統(tǒng)的傳輸效率就是指給定信道的信道容量利用率，它表示信道的實(shí)際傳信率與信道容量的比值，可以寫成： =R/C可見要提高傳輸效率，基本任務(wù)就是要改造信源，使其熵值最大化，此時(shí)趨于1，而這個(gè)過程就是信源最佳化得過程。信源熵H(X)最大化實(shí)質(zhì)上就是尋求一種最佳的概率分布。根據(jù)熵函數(shù)的性質(zhì)，在離散信源情況下，當(dāng)各個(gè)符號(hào)間彼此獨(dú)立而出現(xiàn)的概率相等時(shí)，信源熵達(dá)到最大值。因此，一般的熵值最大化應(yīng)當(dāng)包括兩個(gè)步驟：1、符號(hào)獨(dú)立化，解除符號(hào)間的相關(guān)性；2、各符號(hào)概率均勻化。為了衡量各種編碼是否已達(dá)到極限情況，我們定義變長(zhǎng)碼的編碼效率。設(shè)對(duì)信源S進(jìn)行無失真編碼所得到的平均碼長(zhǎng)為,則,定

20、義 為編碼效率，我們可以采用聲碼器技術(shù)，模式識(shí)別技術(shù)，變換編碼技術(shù)以及相關(guān)編碼技術(shù)等近幾年來發(fā)展起來的效率較好的壓縮信源方法來解除關(guān)聯(lián)、壓縮信源和提高傳輸效率。經(jīng)過解除相關(guān)性之后，如果再使各符號(hào)的概率均勻化，就能進(jìn)一步改造有剩余信源的輸出，去掉冗余度，提高熵速率，使傳輸率接近信道容量進(jìn)而使傳輸效率接近1。如香農(nóng)-范諾編碼，哈夫曼編碼。這列編碼的基本思想就是使各符號(hào)的概率均勻化，即出現(xiàn)概率大的符號(hào)編成短碼，出現(xiàn)概率較小的符號(hào)編成長(zhǎng)碼，只是由于具體方法不同，得到的效果也不同。4 哈夫曼編碼特點(diǎn)及應(yīng)用哈夫曼編碼是真正意義上的最佳編碼。首先編碼是非續(xù)長(zhǎng)碼，哈夫曼編碼實(shí)際上構(gòu)造了一個(gè)碼樹，碼樹從最上面的

21、端點(diǎn)開始構(gòu)造，直到樹根結(jié)束，最后得到一個(gè)橫放的碼樹。其次，其編碼的平均碼長(zhǎng)最小，哈夫曼編碼采用概率匹配的方法來決定各碼字的碼長(zhǎng)，概率大的符號(hào)對(duì)應(yīng)于短碼，概率小的符號(hào)對(duì)應(yīng)于長(zhǎng)碼。最后，哈夫曼編碼的碼字并不唯一，每次對(duì)概率最小的兩個(gè)符號(hào)求概率之和形成縮減信源時(shí)，就構(gòu)造出兩個(gè)樹枝，由于對(duì)兩個(gè)樹枝附碼元時(shí)是任意的，所以碼字不唯一。另外在哈夫曼編碼過程中，對(duì)縮減信源符號(hào)按概率由大到小的順序排列時(shí)應(yīng)使合并后的新符號(hào)盡可能的排在靠前的位置，這樣可使合并后的新符號(hào)重新編碼次數(shù)減少，使短碼得到充分利用。 在實(shí)際應(yīng)用中，首先每個(gè)信源符號(hào)所對(duì)應(yīng)的碼長(zhǎng)不同，一般情況下，信源符號(hào)以勻速輸出，信道也是勻速傳輸?shù)?。通過哈夫

22、曼編碼后，會(huì)造成編碼輸出的信息速率不是常量，因而不能直接由信道來傳送。為了適應(yīng)信道，必須增加緩沖寄存器，將編碼輸出暫存在緩沖器中，然后再勻速向信道輸出。但當(dāng)緩沖器容量有限時(shí)，會(huì)出現(xiàn)緩沖器溢出或取空的現(xiàn)象。所以一般變長(zhǎng)碼只適用于有限長(zhǎng)的信息傳輸，或者在輸出一批消息后能暫停一下。其次，差錯(cuò)擴(kuò)散的問題。變長(zhǎng)碼得一個(gè)的差錯(cuò)可能造成譯碼錯(cuò)誤，并且還會(huì)造成同步錯(cuò)誤，結(jié)果后面一系列碼字也會(huì)譯錯(cuò)。最后，哈夫曼碼的編譯碼需要用查表的方法來進(jìn)行。在信息傳輸過程中必須先存儲(chǔ)與傳輸這一哈夫曼編碼表。這會(huì)影響信息的傳輸效率，特別是當(dāng)N增大時(shí)，所需存儲(chǔ)的碼表也增大，使得設(shè)備復(fù)雜化，且查表搜索的開銷增大。我們還須根據(jù)信源的

23、統(tǒng)計(jì)特性，事先建立哈夫曼編碼表，因此這種方法只適用于已知其統(tǒng)計(jì)特性的信源。盡管如此，哈夫曼方法還是一種有效的無失真信源編碼方法，它便于硬件實(shí)現(xiàn)和計(jì)算機(jī)上的軟件實(shí)現(xiàn)，適用于文件傳真、語音處理和圖像處理的數(shù)據(jù)壓縮。在新世紀(jì)，廣播電視數(shù)字化興起，有線電視、衛(wèi)星電視和地面無線廣播電視的數(shù)字化都發(fā)展很快，有線數(shù)字電視的另一個(gè)發(fā)展趨勢(shì)是利用IP技術(shù)的IPTV，數(shù)字電視地面無線廣播技術(shù)新的應(yīng)用領(lǐng)域是手機(jī)電視。我國(guó)數(shù)字電視地面無線廣播系統(tǒng)技術(shù)研究較早，提出了多種方案，其中采用偽隨機(jī)序列（PN）的時(shí)域同步頻域處理技術(shù)等構(gòu)成了基礎(chǔ)性發(fā)明專利，所實(shí)現(xiàn)的性能優(yōu)于按照ITU已有的三項(xiàng)國(guó)際標(biāo)準(zhǔn)實(shí)現(xiàn)的系統(tǒng)。不僅在信道處理技

24、術(shù)上而且在信源編碼技術(shù)上我國(guó)也有可喜的創(chuàng)新，我國(guó)發(fā)布了AVS音視頻編碼標(biāo)準(zhǔn)，它的壓縮效率與國(guó)際標(biāo)準(zhǔn)MPEG4/AVC相當(dāng)，但復(fù)雜度低，AVS的部分技術(shù)已被吸納進(jìn)相應(yīng)的國(guó)際標(biāo)準(zhǔn)。5 編碼5.1 二元哈夫曼編碼規(guī)則哈夫曼編碼的步驟如下： 將信源消息符號(hào)按其出現(xiàn)的概率大小依次排列 取兩個(gè)概率最小的字母分別配以0和1兩碼元,并將這兩個(gè)概率相加作為一個(gè)新字母的概率,與未分配的二進(jìn)符號(hào)的字母重新排隊(duì)。 對(duì)重排后的兩個(gè)概率最小符號(hào)重復(fù)步驟的過程。 不斷繼續(xù)上述過程,直到最后兩個(gè)符號(hào)配以0和1為止。 從最后一級(jí)開始,向前返回得到各個(gè)信源符號(hào)所對(duì)應(yīng)的碼元序列,即相應(yīng)的碼字。5.2 M進(jìn)制哈夫曼編碼 在編m進(jìn)制哈

25、夫曼碼時(shí)為了使平均碼長(zhǎng)最短,必須使最后一步縮減信源有m個(gè)信源符號(hào)。 對(duì)于m進(jìn)制編碼,若所有碼字構(gòu)成全樹,可分離的碼字?jǐn)?shù)必為：非全樹時(shí)，有s個(gè)碼字不用： 第一次對(duì)最小概率符號(hào)分配碼元時(shí)只取(ms)個(gè),分別配以0,1,m-s-1,把這些符號(hào)的概率相加作為一個(gè)新符號(hào)的概率,與其它符號(hào)一起重新排列,以后每次取m個(gè)符號(hào),分別配以0,1,m-1；如此下去,直至所有概率相加得1為止,即得到各符號(hào)的m進(jìn)制碼字。 例:對(duì)如下單符號(hào)離散無記憶信源編三進(jìn)制哈夫曼碼 這里：m =3，n =8 令k=3，m+k(m1)=9，則 s = 9n = 98 =1 所以第一次取ms=2個(gè)符號(hào)進(jìn)行編碼。 以m =3為例，平均碼長(zhǎng)

26、為 信息率為編碼效率為例： 已知離散無記憶信源（1）分別求信源輸出進(jìn)行其三進(jìn)制和四進(jìn)制哈夫曼碼編碼（2）分別求出兩種編碼的平均碼長(zhǎng)和編碼效率解：（1）三進(jìn)制哈夫曼編碼：四進(jìn)制哈夫曼編碼：（2） 兩種編碼的平均碼長(zhǎng)分別為：信息熵： 兩種編碼的編碼效率分別為 5.3 C+程序void Huffmancoding(Huffmantree HT,Huffmancode HC,float w,int n) int i,m,c,s1,s2,start,f,k20,a,b,d,s3,s4,q,flase=0;float H=0.0,K=0.0,G;/char cd;Huffmantree p;if(n<

27、;=1) printf("無法構(gòu)成樹！n");exit(0); m=n+4; HT=(Huffmantree)malloc(m+1) sizeof(HTnode); /0號(hào)單元未用for(p= HT+1,i=1;i<=n;i+,+p ) ( p).weight =wi; ( p).lchild =0; ( p).mchild =0; ( p).parent =0; ( p).rchild =0;for(;i<=m;i+,+p) ( p).weight =0; ( p).lchild =0; ( p).parent =0; ( p).mchild =0; ( p)

28、.rchild =0;a=1;b=n,d=1;while(b-a)>0) b=b-a; a=a 3; d+; s3=3+d (3-1); / s4=s3-n; /不用的碼字?jǐn)?shù) q=3-s4; /第一次取符號(hào)數(shù)編碼 if(q=1) flase=1; select1( HT,n,&s1); ( HT)s1.parent =n+1;( HT)i.rchild =s1; ( HT)i.weight =( HT)s1.weight; else if(q=2) flase=1; select2( HT,n,&s1,&s2); ( HT)s1.parent =n+1; ( HT

29、)s2.parent =n+1; if( HT)s1.weight=( HT)s2.weight) ( HT)n+1.mchild =s2; ( HT)n+1.rchild =s1; else ( HT)n+1.mchild =s1; ( HT)n+1.rchild =s2; ( HT)n+1.weight =( HT)s1.weight+( HT)s2.weight; if(flase=1) for(i=n+2;i<=m;i+)select3( HT,i-1,&s1,&s2,&s3); ( HT)s1.parent =i; ( HT)s2.parent =i;(

30、 HT)s3.parent =i; ( HT)i.lchild =s1;( HT)i.mchild=s2;( HT)i.rchild=s3; ( HT)i.weight =( HT)s1.weight+( HT)s2.weight+( HT)s3.weight; else for(i=n+1;i<=m;i+) select3( HT,i-1,&s1,&s2,&s3); ( HT)s1.parent =i; ( HT)s2.parent =i;( HT)s3.parent =i; ( HT)i.lchild =s1;( HT)i.mchild=s2;( HT)i.r

31、child=s3; ( HT)i.weight =( HT)s1.weight+( HT)s2.weight+( HT)s3.weight; HC=(Huffmancode)malloc(n+1) sizeof(char ); char cd; cd=(char )malloc(n sizeof(char); cdn-1='0' printf("信源哈夫曼編碼如下:n"); for(i=1;i<=n;+i) start=n-1;ki=0; for(c=i,f=( HT)i.parent;f!=0;c=f,f=( HT)f.parent) ki+; if( HT)f.lchild=c) cd-start='2' else if( HT)f.mchild=c) cd-start='1' else cd-start='0' ( HC)i=(char )malloc(n-start) sizeof(char); strcpy( HC)i,&cdstart); printf("x%d=%f 的哈夫曼編碼是 %st碼長(zhǎng)是 %dn",i,( HT)i.weight,( HC)i,ki); for(i=1;i<=n;