編寫(xiě)matlab函數(shù)實(shí)現(xiàn)哈弗曼編碼算法(共10頁(yè))

1、精選優(yōu)質(zhì)文檔-傾情為你奉上西南科技大學(xué)課 程 設(shè) 計(jì) 報(bào) 告課程名稱(chēng)： 數(shù)字通信課程設(shè)計(jì) 設(shè)計(jì)名稱(chēng)：編寫(xiě)Matlab函數(shù)實(shí)現(xiàn)哈夫曼編碼的算法 姓 名： 林正紅 學(xué) 號(hào): 班 級(jí)： 通信0802 指導(dǎo)教師： 胥磊（老師） 起止日期： 2011.6.28-2011.7.4 西南科技大學(xué)信息工程學(xué)院制專(zhuān)心-專(zhuān)注-專(zhuān)業(yè)課 程 設(shè) 計(jì) 任 務(wù) 書(shū)學(xué)生班級(jí)： 通信0802 學(xué)生姓名： 林正紅 學(xué)號(hào)： 設(shè)計(jì)名稱(chēng)： 編寫(xiě)Matlab函數(shù)實(shí)現(xiàn)哈夫曼編碼的算法 起止日期： 2011.6.28-2011.7.4 指導(dǎo)教師： 胥磊（老師） 設(shè)計(jì)要求：1、理解無(wú)失真信源編碼的理論基礎(chǔ)，掌握無(wú)失真信源編碼的基本方法；2、

2、考慮一個(gè)有8種可能符號(hào)的信源，各種符號(hào)發(fā)生的概率分別為：0.30、0.16、0.14、0.12、0.11、0.09、0.06、0.04；3、根據(jù)Huffman編碼算法，得到碼樹(shù)和Huffman碼；4、編寫(xiě)M函數(shù)，以8個(gè)信源產(chǎn)生的概率向量為變量，返回Huffman編碼算法的編碼結(jié)果，返回信源熵和編碼的碼字長(zhǎng)度。課 程 設(shè) 計(jì) 學(xué) 生 日 志時(shí)間設(shè)計(jì)內(nèi)容2011.6.29-2011.6.30上網(wǎng)查詢(xún)相關(guān)知識(shí)點(diǎn)，并結(jié)合知識(shí)點(diǎn)看matlab、現(xiàn)代通信原理、數(shù)字電視原理等書(shū)籍。2011.6.30結(jié)合設(shè)計(jì)的具體要求，確定總體設(shè)計(jì)方案2011.7.1根據(jù)各個(gè)功能按模塊化格式編寫(xiě)小程序，并實(shí)現(xiàn)其部分功能。20

3、11.7.2整理程序，并調(diào)試。2011.7.3檢查各項(xiàng)指標(biāo)是否完成并修改程序，直到程序正確為止。2011.7.4最后完成報(bào)告的書(shū)寫(xiě)，準(zhǔn)備答辯。課 程 設(shè) 計(jì) 考 勤 表周星期一星期二星期三星期四星期五課 程 設(shè) 計(jì) 評(píng) 語(yǔ) 表指導(dǎo)教師評(píng)語(yǔ)： 成績(jī)： 指導(dǎo)教師： 年 月 日編寫(xiě)Matlab函數(shù)實(shí)現(xiàn)哈夫曼編碼的算法一、 設(shè)計(jì)目的和意義通過(guò)使用matlab編寫(xiě)哈夫曼編碼的算法 ，以及最終算法實(shí)現(xiàn)的整個(gè)過(guò)程中，讓我們學(xué)習(xí)Matlab 軟件的使用和編程；進(jìn)一步深入理解Huffman 編碼算法的原理；提高獨(dú)立進(jìn)行算法編程的能力。在此過(guò)程中，還需要用到數(shù)字電視原理里面的相關(guān)內(nèi)容。所以也能進(jìn)一步了解關(guān)于熵編碼

4、，前綴碼，信息量和信息熵，無(wú)失真信源編碼定理，變字長(zhǎng)編碼等概念有更清晰的認(rèn)識(shí)，也可以通過(guò)實(shí)驗(yàn)中的數(shù)據(jù)與等字長(zhǎng)編碼進(jìn)行比較，體現(xiàn)出來(lái)變字長(zhǎng)編碼的優(yōu)越性。二、 設(shè)計(jì)原理1、熵編碼熵編碼即編碼過(guò)程中按熵原理不丟失任何信息的編碼，解碼后能無(wú)失真地恢復(fù)原圖像。信息熵為信源的平均信息量。常見(jiàn)的熵編碼有：行程編碼(RLE)、LZW編碼、香農(nóng)(Shannon)編碼、哈夫曼(Huffman)編碼和算術(shù)編碼(arithmetic coding)。熵編碼的基本原理就是給出現(xiàn)概率較大的符號(hào)一個(gè)較短碼字，而給出現(xiàn)概率較小的符號(hào)2、哈夫曼編碼在計(jì)算機(jī)信息處理中，“哈夫曼編碼”是一種一致性編碼法（又稱(chēng)"熵編碼法&

5、quot;），用于數(shù)據(jù)的無(wú)損耗壓縮。這一術(shù)語(yǔ)是指使用一張?zhí)厥獾木幋a表將源字符（例如某文件中的一個(gè)符號(hào)）進(jìn)行編碼。這張編碼表的特殊之處在于，它是根據(jù)每一個(gè)源字符出現(xiàn)的估算概率而建立起來(lái)的（出現(xiàn)概率高的字符使用較短的編碼，反之出現(xiàn)概率低的則使用較長(zhǎng)的編碼，這便使編碼之后的字符串的平均期望長(zhǎng)度降低，從而達(dá)到無(wú)損壓縮數(shù)據(jù)的目的）。哈夫曼壓縮是個(gè)無(wú)損的壓縮算法，一般用來(lái)壓縮文本和程序文件。哈夫曼壓縮屬于可變代碼長(zhǎng)度算法一類(lèi)。意思是個(gè)體符號(hào)（例如，文本文件中的字符）用一個(gè)特定長(zhǎng)度的位序列替代。因此，在文件中出現(xiàn)頻率高的符號(hào)，使用短的位序列，而那些很少出現(xiàn)的符號(hào)，則用較長(zhǎng)的位序列。2.1 變字長(zhǎng)編碼定理:最

6、佳編碼定理 在變字長(zhǎng)編碼中，對(duì)于出現(xiàn)概率大的信息符號(hào)，編以短字長(zhǎng)的碼,對(duì)于出現(xiàn)概率小的信息符號(hào)編以長(zhǎng)字長(zhǎng)的碼，如果碼字長(zhǎng)度嚴(yán)格按照符號(hào)概率的大小的相反順序排列，則平均碼字長(zhǎng)一定小于按任何其他符號(hào)順序排列方式得到的碼字長(zhǎng)度。2.2 Huffman 編碼步驟1) 信源符號(hào)按概率大小順序排列，按逆次序分配碼字的長(zhǎng)度。2) 出現(xiàn)概率最小的兩個(gè)符號(hào)概率相加合成一個(gè)新概率。3) 將合成概率看成一個(gè)新組合符號(hào)概率，將新組合符號(hào)和其余符號(hào)一起重新按概率大小排序，再將最小概率的兩個(gè)符號(hào)組成一個(gè)新的組合符號(hào)概率，計(jì)算出其出現(xiàn)概率。重復(fù)上述做法，直到最后只剩下兩個(gè)符號(hào)概率，且這兩個(gè)概率相加等于1為止。4) 將上面得

7、到的各符號(hào)用線連接起來(lái)，得到一個(gè)前綴碼的碼樹(shù)。樹(shù)的端點(diǎn)對(duì)應(yīng)N個(gè)信源。每個(gè)節(jié)點(diǎn)的兩個(gè)分支用二進(jìn)制碼的兩個(gè)碼元符號(hào)“0”，“1”分別表示。從根節(jié)點(diǎn)開(kāi)始沿著相反的路徑，經(jīng)過(guò)一個(gè)或者幾個(gè)節(jié)點(diǎn)到達(dá)端點(diǎn)，將一路上遇到的二進(jìn)制碼元各符號(hào)順序連接起來(lái)，這就是這個(gè)端點(diǎn)對(duì)應(yīng)的信源符號(hào)的Huffman碼的碼字。 3、有關(guān)該信源編碼的計(jì)算設(shè)有N個(gè)碼元組成的離散，無(wú)記憶符號(hào)集（說(shuō)明：以下均以本設(shè)計(jì)中要求的8個(gè)碼元為例進(jìn)行說(shuō)明），其中每個(gè)符號(hào)由一個(gè)二進(jìn)制碼字（即代碼）表示，但是字長(zhǎng)不同。若各符號(hào)出現(xiàn)的概率分別為P(x1)，P(x2)，P(xn)，且各符號(hào)xi的以li個(gè)碼元編碼，則有如下結(jié)論：在變字長(zhǎng)編碼時(shí)每個(gè)符號(hào)的平均碼

8、長(zhǎng)為： 信源熵（信息熵：指一團(tuán)數(shù)據(jù)所帶的信息量，平均信息量就是信息熵（entropy）為： 三、 詳細(xì)設(shè)計(jì)步驟1、 設(shè)計(jì)流程的分析首先，通過(guò)自己前兩天翻閱的通信原理，軟件技術(shù)基礎(chǔ)，數(shù)字電視原理等資料中，正確理解馬夫曼的編碼原理及實(shí)現(xiàn)方法，并且理解平均碼長(zhǎng)及信息熵等概念。然后，按照題目所給的要求，通過(guò)自己計(jì)算得出題目中8個(gè)信源的編碼結(jié)果，以便與實(shí)驗(yàn)結(jié)果相比較，判斷實(shí)驗(yàn)中的結(jié)果是否正確。其中，8個(gè)符號(hào)發(fā)送的概率分別為：0.30、0.16、0.14、0.11、0.10、0.09、0.06、0.04；（注：題目中最開(kāi)始的0.11是0.12，但是為了滿(mǎn)足各符號(hào)概率相加必須為1的要求，我將題目中的0.12

9、改為了0.11）。通過(guò)自己分析，得到的編碼結(jié)果為：0.30【10】、0.16【111】、0.14【110】、0.11【011】、0.10【010】、0.09【000】、0.06【0011】、0.04【0010】然后，根據(jù)試驗(yàn)中的編碼結(jié)果得到各個(gè)碼長(zhǎng)，在按照實(shí)驗(yàn)原理中平均碼長(zhǎng)和信息熵的計(jì)算方法計(jì)算出平均碼長(zhǎng)及信息熵，以便與實(shí)驗(yàn)結(jié)果相對(duì)比。通過(guò)計(jì)算，得出信源熵為2.7656bit/符號(hào)，編碼的碼字長(zhǎng)度為2.8。2、試驗(yàn)程序的具體實(shí)現(xiàn)流程1) 程序的輸入：以一維數(shù)組的形式輸入要進(jìn)行huffman 編碼的信源符號(hào)概率，在運(yùn)行該程序前，顯示文字提示信息，提示所要輸入的概率矢量；然后對(duì)輸入的概率矢量進(jìn)行合

10、法性判斷，原則為：如果概率矢量中存在小于0 的項(xiàng)，則輸入不合法，提示重新輸入；如果概率矢量的求和大于1，則輸入也不合法，提示重新輸入。2) huffman 編碼具體實(shí)現(xiàn)原理：在輸入的概率矩陣p 正確的前提條件下,對(duì)p 進(jìn)行排序，并用矩陣L 記錄p 排序之前各元素的順序，然后將排序后的概率數(shù)組p 的前兩項(xiàng)，即概率最小的兩個(gè)數(shù)加和，得到新的一組概率序列，重復(fù)以上過(guò)程，最后得到一個(gè)記錄概率加和過(guò)程的矩陣p 以及每次排序之前概率順序的矩陣a。3) 新生成一個(gè)n-1 行n 列，并且每個(gè)元素含有n 個(gè)字符的空白矩陣，然后進(jìn)行huffman 編碼，具體分析如下：u 將c 矩陣的第n-1 行的第一和第二個(gè)元素

11、分別令為0 和1（表示在編碼時(shí)，根節(jié)點(diǎn)之下的概率較小的元素后補(bǔ)0，概率較大的元素后補(bǔ)1，后面的編碼都遵守這個(gè)原則）u 然后對(duì)n-i-1 的第一、二個(gè)元素進(jìn)行編碼，首先在矩陣a 中第n-i行找到值為1 所在的位置，然后在c 矩陣中第n-i 行中找到對(duì)應(yīng)位置的編碼（該編碼即為第n-i-1 行第一、二個(gè)元素的根節(jié)點(diǎn)），則矩陣c 的第n-i 行的第一、二個(gè)元素的n-1 的字符為以上求得的編碼值，根據(jù)之前的規(guī)則，第一個(gè)元素最后補(bǔ)0，第二個(gè)元素最后補(bǔ)1，則完成該行的第一二個(gè)元素的編碼，最后將該行的其他元素按照“矩陣c 中第n-i 行第j+1 列的值等于對(duì)應(yīng)于a 矩陣中第n-i+1 行中值為j+1 的前面一

12、個(gè)元素的位置在c 矩陣中的編碼值”的原則進(jìn)行賦值，重復(fù)以上過(guò)程即可完成huffman 編碼。4) 根據(jù)理論公式，并結(jié)合程序中的數(shù)據(jù)，計(jì)算信源熵和平均碼長(zhǎng)，其比值即為編碼密碼效率。5) 具體的實(shí)現(xiàn)程序參見(jiàn)附錄中的相關(guān)說(shuō)明。四、 設(shè)計(jì)結(jié)果及分析1、設(shè)計(jì)結(jié)果運(yùn)行程序之后，結(jié)果如下：Huffman編碼結(jié)果為:h = 10 111 110 011 010 000 0011 0010編碼的平均碼長(zhǎng)為: l = 2.8000信源熵為: hh =2.7656分析后得到的結(jié)論如下： 將實(shí)驗(yàn)結(jié)果與通過(guò)理論分析的結(jié)果相對(duì)比，發(fā)現(xiàn)完全相同，說(shuō)明實(shí)驗(yàn)程序是正確的，也說(shuō)明自己對(duì)哈弗曼編碼原理的理解是正確的。在分析結(jié)果的同

13、時(shí)，也得到了以下結(jié)論。2、設(shè)計(jì)結(jié)果的分析1) 在哈夫曼編碼過(guò)程中，對(duì)縮減信源符號(hào)按概率由大到小的順序重新排列時(shí)，應(yīng)使合并后的新符號(hào)盡可能排在靠前的位置，這樣可使合并后的新符號(hào)重復(fù)編碼次數(shù)減少，使短碼得到充分利用。2) 哈夫曼的編碼效率相當(dāng)高，對(duì)編碼器的要求也簡(jiǎn)單得多。3) 哈夫曼它保證了信源概率大的符號(hào)對(duì)應(yīng)于短碼，概率小的符號(hào)對(duì)應(yīng)于長(zhǎng)碼；每次縮減信源的最后兩個(gè)碼字總是最后一位碼元不同，前面的各位碼元都相同；每次縮減信源的最長(zhǎng)兩個(gè)碼字有相同的碼長(zhǎng)。4) 霍夫曼的編法并不一定是唯一的，具體原因如下： 每次對(duì)縮減信源兩個(gè)概率最小的符號(hào)分配“0”和“1”碼元是任意的，所以可得到不同的碼字。只要在各次縮

14、減中保持碼元分配的一致性，即能得到可分離碼字。 不同的碼元分配，得到的具體碼字不同，但碼長(zhǎng)li不變，平均碼長(zhǎng)也不變，所以沒(méi)有本質(zhì)區(qū)別； 縮減信源時(shí)，若合并后的新符號(hào)概率與其他符號(hào)概率相等，從編碼方法上來(lái)說(shuō)，這幾個(gè)符號(hào)的次序可任意排列，編出的碼都是正確的，但得到的碼字不相同。五、 體會(huì)1、 實(shí)驗(yàn)中遇到的問(wèn)題起初，對(duì)哈弗曼編碼確實(shí)不怎么懂，通過(guò)查了很多資料以后，自己再計(jì)算了很多次，才完全理解了哈弗曼編碼的原理。這樣也可以方便對(duì)程序的理解。這個(gè)實(shí)驗(yàn)程序不是完全自己寫(xiě)的，是通過(guò)網(wǎng)上的很多個(gè)程序的綜合分析最后選擇的一個(gè)相對(duì)簡(jiǎn)單的程序?qū)崿F(xiàn)方法，但是還遇到一個(gè)問(wèn)題，就是對(duì)哈弗曼編碼的原理懂了，可是還是看不懂

15、程序?qū)崿F(xiàn)中一些細(xì)節(jié)問(wèn)題。通過(guò)問(wèn)同學(xué)和老師之后，基本解決了這個(gè)問(wèn)題。2、 實(shí)驗(yàn)體會(huì)本次設(shè)計(jì)，首先針對(duì)題目進(jìn)行分析，將所涉及的知識(shí)點(diǎn)，及相關(guān)函數(shù)做了分析，大體能夠把握整體的設(shè)計(jì)流程及思路。再通過(guò)查閱相關(guān)資料，能對(duì)相關(guān)的知識(shí)做正確的記錄，以便隨時(shí)查看。但是，由于平時(shí)忽略了細(xì)節(jié)知識(shí)點(diǎn)的學(xué)習(xí)，在此次設(shè)計(jì)中但面對(duì)高斯白噪聲時(shí)便束手無(wú)措。后來(lái)經(jīng)過(guò)查找，發(fā)現(xiàn)從高斯分布中獲取采樣值時(shí)，采樣點(diǎn)所組成的隨機(jī)過(guò)程就是“高斯白噪聲”。在MATLAB中，使用函數(shù)randn()就可以產(chǎn)生這樣的噪聲。此外，在分析所設(shè)計(jì)的圖中，根據(jù)相關(guān)的通信原理，數(shù)字電視原理和計(jì)算機(jī)軟件技術(shù)基礎(chǔ)的知識(shí)可以對(duì)結(jié)果作出判斷，這樣就提高了自己的相關(guān)

16、知識(shí)，同時(shí)加深了對(duì)matlab的運(yùn)用。在這個(gè)課程設(shè)計(jì)過(guò)程中我遇到了很多困難，花了很多時(shí)間查閱資料，我們是學(xué)通信專(zhuān)業(yè)的，沒(méi)有數(shù)字電視處理這門(mén)課程，但是這個(gè)設(shè)計(jì)中的哈弗曼編碼原理在這門(mén)書(shū)上才有較詳細(xì)的說(shuō)明。所以我結(jié)合軟件技術(shù)基礎(chǔ)，通信原理及數(shù)字電視處理這三門(mén)課程之后，才把這個(gè)設(shè)計(jì)的原理理解清楚了。設(shè)計(jì)的過(guò)程中我也學(xué)到了東西，這些對(duì)以后的學(xué)習(xí)將有很大幫助。但是我知道自己做的還不夠，有些基本的設(shè)計(jì)要求我都沒(méi)達(dá)到，我只是做了我自己能做的。我也知道這樣的設(shè)計(jì)對(duì)我們是很有幫助的，但是由于我自己的能力有限我就只能做到這么多了，還請(qǐng)老師諒解，謝謝！由于本次設(shè)計(jì)運(yùn)用了不同的知識(shí)，這樣我就可以更好的將不同科目的知識(shí)

17、進(jìn)行聯(lián)系學(xué)習(xí)，對(duì)牢靠的學(xué)習(xí)有著巨大的支持，是一件非常有意義的事情。六、 參考文獻(xiàn)1 曹志剛，錢(qián)亞生. 現(xiàn)代通信原理 . 清華大學(xué)出版社，2009.9 2 張威. MATLAB基礎(chǔ)與編程入門(mén)（第二版）.西安電子科技大學(xué)出版社，2008.1 3 余兆明，余智數(shù)字電視原理西安電子科技大學(xué)出版社，2009.24 楊述斌，李永全. 數(shù)字信號(hào)處理實(shí)踐教程. 華中科技大學(xué)出版社，2007.15 程佩青，數(shù)字信號(hào)處理教程. 清華大學(xué)出版社，2010.5程序附錄：p=input('請(qǐng)輸入數(shù)據(jù):') %提示輸入界面 0.30,0.16,0.14,0.11,0.10,0.09,0.06,0.04n=

18、length(p);for i=1:n if p(i)<0 fprintf('n 提示：概率值不能小于0!n'); p=input('請(qǐng)重新輸入數(shù)據(jù):') endend if abs(sum(p)>1 fprintf('n 哈弗曼碼中概率總和不能大于1!n'); p=input('請(qǐng)重新輸入數(shù)據(jù):') endq=p;a=zeros(n-1,n); %生成一個(gè)n-1 行n 列的數(shù)組 for i=1:n-1 q,l=sort(q) a(i,:)=l(1:n-i+1),zeros(1,i-1) q=q(1)+q(2),q(3:n),1; end for i=1:n-1 c(i,1:n*n)=blanks(n*n); endc(n-1,n)='0' c(n-1,2*n)='1' for i=2:n-1c(n-i,1: