基于MATLAB的霍夫曼編碼仿真

1、河南大學(xué)民生學(xué)院本科畢業(yè)論文目錄0 前言21 信源編碼的基本概念2 1.1 通信系統(tǒng)的模塊仿真2 1.2 信息的度量與編碼3 1.3 無失真編碼算法42 信源最佳化63 霍夫曼編碼特點及應(yīng)用64 編碼規(guī)則7 4.1 二元霍夫曼編碼規(guī)則7 4.2 多元霍夫曼編碼規(guī)則8 4.3 擴(kuò)展信源霍夫曼編碼85 MATLAB性能仿真8 5.1 二元霍夫曼編碼仿真9 5.2 三元霍夫曼編碼仿真11 5.3 擴(kuò)展信源編碼仿真136 結(jié)論15參考文獻(xiàn)16基于MATLAB的霍夫曼編碼仿真李長江（河南大學(xué)物民生學(xué)院，河南 開封，475004）摘 要： 通信的數(shù)字化是它能與計算機(jī)技術(shù)和數(shù)字信號處理技術(shù)相結(jié)合的基礎(chǔ)，而實

2、現(xiàn)通信數(shù)字化的前提是信源能提供的各種用于傳遞的消息，例如語音、圖像、數(shù)據(jù)、文字等都必須以數(shù)字化形式表示。而信源編碼是數(shù)字通信系統(tǒng)中的重要組成部分，他是保證信號有效傳輸?shù)囊环N重要方式。霍夫曼編碼依據(jù)字符出現(xiàn)的概率來構(gòu)造異字頭的平均長度最短的碼字，有時稱之為最佳編碼，其優(yōu)越的性能被廣泛使用在數(shù)字通信系統(tǒng)中?；舴蚵幋a已經(jīng)成為數(shù)據(jù)壓縮的靈魂算法。本文介紹了無失真編碼算法的構(gòu)造，霍夫曼編碼的規(guī)則和特點，同時分析了對信源進(jìn)行優(yōu)化的方法，最后通過MATLAB仿真來討論比較二元霍夫曼編碼、三元霍夫曼編碼以及信源擴(kuò)展編碼的效率，來實現(xiàn)霍夫曼碼的優(yōu)化構(gòu)造。關(guān)鍵詞： Matlab，霍夫曼編碼，仿真,二元霍夫曼編碼

3、，三元霍夫曼編碼，擴(kuò)展信源編碼Huffman Codes And Matlab SimulationLi changjiang(School of min sheng, Henan University, Henan Kaifeng 475004, China)Abstract: Digital communication is the basis which can combine computer technology and digital signal processing technology.But the premise for digital communication is

4、that the source can provide a variety of message for transmission.For example voice,images,data,text.And the messages can be expressed in digital form.Source coding is the important part in the digital communication system.It is also a way to ensure the effectiveness of the transmission in this syst

5、em.Huffman coding based on the probability to construct a character different prefix length of the shortest average code word .Sometimes it is called the optimal coding. Huffman code is widely used in the digital communication system by the ascendant performance .Huffman coding has become data compr

6、ession soul algorithm.This article describes the construction of lossless coding algorithm .It also introduces the rules and the characteristics of Huffman coding.It also analyzes the method of source optimization.Finally,we discuss the comparison of binary Huffman coding,ternary Huffman coding and

7、extended source coding based on MATLAB.We are thus to achieve optimal Huffman code constructed.Key words: MATLAB； huffman code； binary Huffman coding; ternary Huffman coding ; extended source coding 0 前言在通信的數(shù)字化過程中，對于時間連續(xù)和取值連續(xù)的原始語音和圖像等模擬信號來說，如果要以數(shù)字方式進(jìn)行傳輸，在發(fā)送端必須首先進(jìn)行模/數(shù)(A/D)變換，將原始信號轉(zhuǎn)換為時間離散和取值離散的數(shù)字信號。模擬

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

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

10、信源（比如語音、圖像）最開始都是模擬信號，為了將信源輸出數(shù)字化，信源必須量化為確定數(shù)目的級數(shù)。量化方案可劃分為標(biāo)量量化和矢量量化兩種。在標(biāo)量量化中每個信源輸出都分別被量化，標(biāo)量量化可進(jìn)一步分為均勻量化和非均勻量化。在均勻量化中量化區(qū)域是等長的；在非均勻量化中量化區(qū)域可以是不等長的。矢量量化是對信源輸出組合進(jìn)行整體量化。 在標(biāo)量量化中，隨機(jī)標(biāo)量X的定義域被劃分成N個互不重疊的區(qū)域Ri，1 iN , Ri被稱為量化間隔，且在每個區(qū)域內(nèi)選擇一個點作量化級數(shù)。這樣落在區(qū)域Ri內(nèi)的隨機(jī)變量的所有值都被量化為第i個量化級數(shù)，用來表示，這就意味著： 易見，這類量化引入了失真，其均方誤差為： 其中f(x)是信

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

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

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

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

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

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

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

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

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

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

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

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

23、TU已有的三項國際標(biāo)準(zhǔn)實現(xiàn)的系統(tǒng)。不僅在信道處理技術(shù)上而且在信源編碼技術(shù)上我國也有可喜的創(chuàng)新，我國發(fā)布了AVS音視頻編碼標(biāo)準(zhǔn)，它的壓縮效率與國際標(biāo)準(zhǔn)MPEG4/AVC相當(dāng)，但復(fù)雜度低，AVS的部分技術(shù)已被吸納進(jìn)相應(yīng)的國際標(biāo)準(zhǔn)。4 編碼規(guī)則4.1 二元霍夫曼編碼規(guī)則 （1）將信源符號按概率從大到小的順序排列。 （2）給兩個概率最小的信源符號各分配一個碼位“0”和“1”，將兩個信源符號合并成一個新符號，并用這兩個最小的概率之和作為新符號的概率，結(jié)果得到一個只包含（n-1）個信源符號的新信源。稱為信源的第一次縮減信源，用s1表示。 （3）將縮減信源s1的符號仍按概率從大到小順序排列，重復(fù)步驟二，得到

24、只含（n-2）個符號的縮減信源s2。 （4）重復(fù)上述步驟，直至縮減信源只剩兩個符號為止，此時所剩兩個符號的概率之和必為1，然后從最后一級縮減信源開始，依編碼路徑向前返回，就得到各信源符號所對應(yīng)的碼字。4.2 多元霍夫曼編碼規(guī)則由二進(jìn)制霍夫曼編碼的方法很容易推廣到r進(jìn)制的情況，只是編碼的過程中構(gòu)成縮減信源時，每次都是將r個概率最小的信源符號合并，然后分別用碼符號0,1，.,(r-1)表示。為了充分利用短碼，使霍夫曼碼的平均碼長最短，必須使最后一個縮減信源恰好有r個信源符號，因此對于r元霍夫曼碼，信源S符號個數(shù)q必須滿足 其中表示信源縮減次數(shù)。如果不滿足上式，則可以在最后增補一些概率為零的信源符號

25、，因此上式又可以寫成 為增加的信源符號數(shù)，并且是滿足上式的最小正整數(shù)或0。這樣處理后得到的r元霍夫曼碼可充分利用短碼，一定是緊致碼。4.3 擴(kuò)展信源霍夫曼編碼對離散無記憶信源的N次擴(kuò)展信源進(jìn)行編碼便得到N次擴(kuò)展碼。采用霍夫曼編碼法能夠使碼的平均長度最短，信息的冗余量最小。然而這種編碼方法所形成的碼字很不規(guī)整，這樣不利于硬件的譯碼。在很多處理機(jī)中，我們采用一種新的折中的方法，稱為擴(kuò)展編碼法。這種方法是由定長編碼與霍夫曼編碼法相結(jié)合形成的。有等長擴(kuò)展法和不等長擴(kuò)展編碼方法，為了便于實現(xiàn)分級譯碼，我們一般采用等長擴(kuò)展編碼法，當(dāng)然，也可以根據(jù)具體需要采用每次擴(kuò)展位數(shù)不等的不等長擴(kuò)展法。5 MATLAB

26、性能仿真Problem 1:對信源S編碼，其中現(xiàn)對該離散無記憶平穩(wěn)信源進(jìn)行霍夫曼編碼。對應(yīng)霍夫曼編碼求熵仿真如下:function h=entropy(p)%H=ENTROPY(P) returns the entropy function of%the probability vector p.p=0.4,0.2,0.2,0.1,0.1,if length(find(p10e-10,error(Not a prob. vector, components do not add up to 1)endh=sum(-p.*log2(p);程序運行結(jié)果顯示：p = 0.4000 0.2000 0.

27、2000 0.1000 0.1000ans = 2.12195.1 二元霍夫曼編碼仿真(1) 對problem 1進(jìn)行二元霍夫曼編碼程序如下:function h,l=huffmancode(P)P=input(輸入概率:);n=length(P);for i=1:n-1 for j=i+1:n if P(i)=P(j) p=P(i); P(i)=P(j); P(j)=p; end endenddisp(概率分布);Q=P;m=zeros(n-1,n);for i=1:n-1 Q,b=sort(Q);%sort函數(shù)是對Q進(jìn)行升序排列，返回值l顯示排序后位置的變動信息 m(i,:)=b(1:n-

28、i+1),zeros(1,i-1); Q=Q(1)+Q(2),Q(3:n),1;endfor i=1:n-1 c(i,:)=blanks(n*n);%blanks是空格函數(shù)end% 以下計算各個元素碼字c(n-1,n)=1;c(n-1,2*n)=0;for i=2:n-1 c(n-i,1:n-1)=c(n-i+1,n*(find(m(n-i+1,:)=1)-(n-2):n*(find(m(n-i+1,:)=1); c(n-i,n)=1; c(n-i,n+1:2*n-1)=c(n-i,1:n-1); c(n-i,2*n)=0; for j=1:i-1 c(n-i,(j+1)*n+1:(j+2)*

29、n)=c(n-i+1,n*(find(m(n-i+1,:)=j+1)-1)+1:n*find(m(n-i+1,:)=j+1); endendfor i=1:n h(i,1:n)=c(1,n*(find(m(1,:)=i)-1)+1:find(m(1,:)=i)*n); ll(i)=length(find(abs(h(i,:)=32);%碼長endl=sum(P.*ll);%平均碼長h1=-log2(P);%自信息量H=P*(h1);%熵Hdisp(二元霍夫曼編碼平均碼長)ldisp(編碼效率)G=H/ldisp(二元霍夫曼編碼)(2） 運行結(jié)果為：輸入概率:0.4,0.2,0.2,0.1,0.

30、1概率分布H = 2.1219二元霍夫曼編碼平均碼長l = 2.2000編碼效率G = 0.9645二元霍夫曼編碼ans = 1 000 01 0011 00105.2 三元霍夫曼編碼仿真(1)對problem 1進(jìn)行三元霍夫曼編碼程序如下:function h,l=huffman(p);%HUFFMAN Huffman code generator% h,l=huffman(p), Huffman code generator% returns h the Huffman code matrix, and l the% average codeword length for a source

31、 with% probability vector p.S=input(輸入概率:);n=length(S);for i=1:n-1 for j=i+1:n if S(i)=S(j) s=S(i); S(i)=S(j); S(j)=s; end endenddisp(概率分布);Sp=S;N=length(p);r=3;q=p(1:N),zeros(1,ceil(N-r)/(r-1)*(r-1)+r-N); n=length(q);A=(n-r)/(r-1)+1;m=zeros(A,n);for i=1:A q,l=sort(q); m(i,:)=l(1:n-2*(i-1),zeros(1,2

32、*(i-1); q=sum(q(1:r),q(r+1:n),ones(1,r-1);end for i=1:A c(i,:)=blanks(n*n);endc(A,n)=0;c(A,2*n)=1;c(A,3*n)=2;for i=1:(A-1) c(A-i,1:n-1)=c(A-i+1,n*(find(m(A-i+1,:)=1). -(n-2):n*(find(m(A-i+1,:)=1); c(A-i,n)=0; c(A-i,n+1:2*n-1)=c(A-i,1:n-1); c(A-i,2*n)=1; c(A-i,2*n+1:3*n-1)=c(A-i,1:n-1); c(A-i,3*n)=2;

33、 for j=1:2*i c(A-i,(j+2)*n+1:(j+3)*n)=c(A-i+1,n*(find(m(A-i+1,:). =j+1)-1)+1:n*find(m(A-i+1,:)=j+1); endendfor i=1:N h(i,1:n)=c(1,n*(find(m(1,:)=i)-1)+1:find(m(1,:)=i)*n); ll(i)=length(find(abs(h(i,:)=32); endH=-sum(p.*log2(p);l=sum(p.*ll);Hdisp(三元霍夫曼編碼平均碼長)ldisp(編碼效率)G=H/(l*log2(r)disp(三元霍夫曼編碼)(2)運

34、行結(jié)果為：輸入概率:0.4,0.2,0.2,0.1,0.1H = 2.1219三元霍夫曼編碼平均碼長l = 1.4000編碼效率G = 0.9563三元霍夫曼編碼ans = 2 12 0 10 115.3 擴(kuò)展信源編碼仿真(1) 對problem 1進(jìn)行擴(kuò)展后霍夫曼編碼程序如下: function h,l=huffman(p);%HUFFMAN Huffman code generator% h,l=huffman(p), Huffman code generator% returns h the Huffman code matrix, and l the% average codeword

35、 length for a source with% probability vector p.disp(概率分布為)a=0.4,0.2,0.2,0.1,0.1,H=sum(-a.*log2(a);A = 0.16; B = 0.08; C = 0.08;D = 0.04; E = 0.04; F = 0.08;G = 0.04; Z = 0.04; I = 0.02;J = 0.02; K = 0.08; L = 0.04;M = 0.04; N = 0.02; O = 0.02;P = 0.04; Q = 0.02; R = 0.02;S = 0.01; T = 0.01; U = 0.0

36、4;V = 0.02; W = 0.02; X = 0.01;Y = 0.01; p = A B C D E F G Z I J K L M N O P Q R S T U V W X Y;n=length(p);q=p;m=zeros(n-1,n);for i=1:n-1q,l=sort(q);m(i,:)=l(1:n-i+1),zeros(1,i-1);q=q(1)+q(2),q(3:n),1; endfor i=1:n-1c(i,:)=blanks(n*n);endc(n-1,n)=0;c(n-1,2*n)=1;for i=2:n-1c(n-i,1:n-1)=c(n-i+1,n*(fin

37、d(m(n-i+1,:)=1).-(n-2):n*(find(m(n-i+1,:)=1);c(n-i,n)=0; c(n-i,n+1:2*n-1)=c(n-i,1:n-1);c(n-i,2*n)=1;for j=1:i-1c(n-i,(j+1)*n+1:(j+2)*n)=c(n-i+1,.n*(find(m(n-i+1,:)=j+1)-1)+1:n*find(m(n-i+1,:)=j+1);endendfor i=1:n h(i,1:n)=c(1,n*(find(m(1,:)=i)-1)+1:find(m(1,:)=i)*n);l1(i)=length(find(abs(h(i,:)=32);endl=sum(p.*l1);disp(信源熵)Hdisp(擴(kuò)展信源平均碼長)ldisp(擴(kuò)展信源編碼效率)G=2*H/ldisp(擴(kuò)展信源編碼)（