霍夫曼編碼及其應用

《霍夫曼編碼及其應用》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在學術(shù)論文-天天文庫。

1、畢業(yè)設(shè)計（論文）畢業(yè)設(shè)計（論文）題目：霍夫曼編碼及其應用學院：數(shù)理學院專業(yè)名稱：信息與計算科學學號：0741210246學生姓名：張浩指導教師：韓海清2011年4月20日30畢業(yè)設(shè)計（論文）摘要本文首先對二元霍夫曼編碼進行了細致研究，并對其算法進行擴展，得到了適用于多元霍夫曼編碼的算法。然后，對霍夫曼編碼的前綴性，最優(yōu)性進行了證明。最后實現(xiàn)了霍夫曼編碼在決策論中應用。關(guān)鍵詞碼；熵；霍夫曼編碼；決策樹30畢業(yè)設(shè)計（論文）ABSTRACTThispaperfirststudiedbinaryHuffmancoding,andconductedadetaile

2、dstudyonitsalgorithmsuitableforexpansion,getmultipleHuffmancodingalgorithm.Meanwhile,Huffmancodingprefixsex,optimalityproved.FinallyrealizedHuffmancodingappliedinrigorous.KEYWORDSTheCoding；TheEntropy；HuffmanCoding；Decisiontree30畢業(yè)設(shè)計（論文）目錄第一章引言4第二章主要概念52.1香農(nóng)三大定理52.1.1香農(nóng)第一定理(可變長無失真

3、信源編碼定理)52.1.2香農(nóng)第二定理（有噪信道編碼定理）52.1.3香農(nóng)第三定理（保失真度準則下的有失真信源編碼定理）52.2霍夫曼編碼6第三章二元霍夫曼編碼及其算法6第四章一般霍夫曼編碼及其算法8第五章霍夫曼編碼的性能分析125.1霍夫曼編碼的前綴性125.2霍夫曼編碼的最優(yōu)性定理13第六章霍夫曼編碼的應用13第七章總結(jié)與展望16參考文獻17附錄118致謝3030畢業(yè)設(shè)計（論文）第一章引言1948年，美國數(shù)學家香農(nóng)（C.E.Shannon）在《貝爾系統(tǒng)電話雜志》發(fā)表了題為“通信的數(shù)學理論”的長篇論文。這篇論文以概率論為工具，深刻闡述了通信工程的一系列

4、基本理論問題，給出了計算信源信息量和信道容量的方法和一般公式，得到了一組表征信息傳遞重要關(guān)系的編碼定理，從而創(chuàng)立了信息論。1959年，香農(nóng)在發(fā)表的“保真度準則下的離散信源編碼定理”（Codingtheoremsforadiscretesourceatthefidelitycriterion）一文中系統(tǒng)的提出了信息率失真理論（rate-distortiontheory）,為信源壓縮編碼的研究奠定了理論基礎(chǔ)。在信息傳輸過程中，信源序列通過信源編碼器實現(xiàn)對信源冗余度的壓縮，變成編碼序列，編碼序列通過信源譯碼器恢復成信源序列。根據(jù)恢復序列的效果，可把信源編譯器分

5、為兩類，即無失真信源編碼和限失真信源編碼。在無失真信源編碼的過程中，編、譯碼過程是可逆的，即信源符號可以通過編碼序列無差錯地恢復。為提高傳輸有效性，我們總是希望在保證無失真的條件下盡量壓縮碼率（編碼后傳輸每信源符號所需的二元碼符號數(shù)），但這種壓縮是否有限度是一個必須要解決的理論問題。香農(nóng)第一定理也就是無失真信源編碼定理對這個問題做了明確回答。定理指出，只要信源編碼碼率不小于信源的熵就存在無失真信源編碼，同時還指出如果信源編碼的碼率大于信源編碼的熵就不存在無失真信源編碼。同時，定理還給出了進行無失真信源編碼的理論極值，論證與指出了理想最佳信源編碼是存在的。

6、但是并沒有給出信源編碼的實際構(gòu)造方法和實用碼的結(jié)構(gòu)。編碼的目的就是為了優(yōu)化通信系統(tǒng)。一般來說，通信系統(tǒng)的性能指標是有效性、可靠性、安全性和經(jīng)濟性。隨著科學技術(shù)的發(fā)展和需求，人們廣泛致力于對各種文本、圖片、圖形、語言、聲音、活動圖像和影視信號等實際信源進行了實用壓縮方法和技術(shù)研究，使信源的數(shù)據(jù)壓縮技術(shù)得以蓬勃發(fā)展和逐漸走向成熟?；舴蚵?952年提出了一種構(gòu)造最佳碼得方法，我們稱之為霍夫曼編碼?；舴蚵幋a適用于多遠獨立信源，對于多元獨立信源來說它是最佳碼。它充分利用了信源概率分布的特性進行編碼，是一種最佳的逐個符號的編碼方法。30畢業(yè)設(shè)計（論文）第二章主要

7、概念香農(nóng)定理作為信息論的基礎(chǔ)理論，我們有必要對進行簡要介紹。下面我們給出香農(nóng)三大定理：2.1香農(nóng)三大定理香農(nóng)三大定理是信息論的基礎(chǔ)理論。香農(nóng)三大定理是存在性定理，雖然并沒有提供具體的編碼實現(xiàn)方法，但為通信信息的研究指明了方向。[4]香農(nóng)第一定理是可變長無失真信源編碼定理。香農(nóng)第二定理是有噪信道編碼定理。香農(nóng)第三定理是保失真度準則下的有失真信源編碼定理。具體如下:2.1.1香農(nóng)第一定理(可變長無失真信源編碼定理)[1]設(shè)信源S的熵H(S),無噪離散信道的信道容量為C,于是,信源的輸出可以進行這樣的編碼,使得信道上傳輸?shù)钠骄俾蕿槊棵雮€信源符號.其中a可以是

8、任意小的正數(shù),要使傳輸?shù)钠骄俾蚀笥谑遣豢赡艿摹?.1.2香農(nóng)第二定理（有噪信道