信息論課程設計報告

本文格式為Word版，下載可任意編輯——信息論課程設計報告課程設計

目錄

一、概述1、設計目的2、設計任務3、所用軟件環(huán)境二、需求分析1、問題描述2、基本要求三、設計過程1、霍夫曼編碼2、費諾編碼3、游程編碼4、算術編碼

一、概述1設計目的

1.1深刻理解信源編碼的基本思想與目的；

1.2深刻理解并把握霍夫曼編碼譯碼、費諾編碼譯碼、游程編碼譯碼、算術編碼譯碼的原理與方法；

1.3提高綜合利用所學理論知識獨立分析和解決問題的能力，提高編程能力。

2設計任務

2.1對任意的字符分別進行2元霍夫曼編碼、2元費諾編碼、游程編碼和

算術編碼，并進行相應的譯碼；2.2注意編碼效率的計算.

3所用軟件環(huán)境

VisualC++6.0，簡稱VC或者VC6.0，是微軟推出的一款C++編譯器，將“高級語言〞翻譯為“機器語言（低級語言）〞的程序。VisualC++是一個功能強大的可視化軟件開發(fā)工具。自1993年Microsoft公司推出VisualC++1.0后，隨著其新版本的不斷問世，VisualC++已成為專業(yè)程序員進行軟件開發(fā)的首選工具。VisualC++6.0由Microsoft開發(fā),它不僅是一個C++編譯器，而且是一個基于Windows操作系統(tǒng)的可視化集成開發(fā)環(huán)境（integrateddevelopmentenvironment，IDE）。VisualC++6.0由大量組件組成，包括編輯器調試器以及程序向導AppWizard、類向導ClassWizard等開發(fā)工具。這些組件通過一個名為

DeveloperStudio的組件集成為和諧的開發(fā)環(huán)境Microsoft的主力軟件產(chǎn)品。VisualC++是一個功能強大的可視化軟件開發(fā)工具。

二、需求分析1問題描述

1.1霍夫曼編碼首先要解決的問題是給定一段字符串，如何建造霍夫曼樹；怎樣根據(jù)該樹求每個字符的編碼，并對該段字符串進行編碼；怎么樣將得到的編碼進行譯碼；怎么樣遍歷輸出樹中的葉子節(jié)點。1.2費諾編碼,給定一段字符串，如何排序；分治法編碼如何實現(xiàn)；如何計算頻率并求編碼效率。

1.3游程編碼，如何統(tǒng)計輸入的灰度值；灰度值如何編碼；解碼如何回溯；編碼效率與之前兩個的差異。

1.4算術編碼，如何計算精度；如何找到某字符落在哪一個頻率區(qū)間；反向解碼的難點。

2基本要求

2.1霍夫曼編碼要達到的要求：用戶從鍵盤隨機輸入一串字符串，程序讀入字符串，統(tǒng)計每個字符的頻率，建造霍夫曼樹，編碼譯碼，并根據(jù)統(tǒng)計的字符頻率求出根據(jù)公式求出編碼效率。

2.2費諾編碼要達到的要求：用戶從鍵盤隨機輸入一串字符串，程序讀入字符串，統(tǒng)計每個字符的頻率，將頻率按大小排序，用分治法編碼，譯碼，求編碼效率。

2.3游程編碼要達到的要求：輸入灰度值矩陣，進行編碼譯碼，求出編碼效率。

2.4算術編碼要達到的要求：輸入符號串，編碼譯碼，計算精度。

三、設計過程1、霍夫曼編碼1.1算法思想

哈夫曼樹又稱最優(yōu)二叉樹，是帶權路徑長度最小的二叉樹。設法讓出現(xiàn)次數(shù)多的字符二進制碼短些，而讓那些很少出現(xiàn)的字符二進制碼長一些。若對字符集進行不等長編碼，則要求字符集中任一字符的編碼都不是其它字符編碼的前綴。為了確保哈夫曼編碼的唯一性，我們可以對它的左右子樹的大小給予比較限定，如：左子樹的權值小于右子樹的權值。哈夫曼樹中的左右分支各代表‘0’和‘1’,則從根節(jié)點到葉子節(jié)點所經(jīng)歷的路徑分支的‘0’和‘1’組成的字符串，為該節(jié)點對應字符的哈夫曼編碼。

統(tǒng)計字符中每個字符在文件中出現(xiàn)的平均概率（概率越大，要求編碼

越短）。利用哈夫曼樹的特點：權越大的葉子離根越近，將每個字符的概率值作為權值，構造哈夫曼樹。則概率越大的節(jié)點，路徑越短。哈夫曼譯碼是從二進制序列的頭部開始，順序匹配成共的部分替換成相應的字符，直至二進制轉換為字符序列。

為了詳細說明這個問題，特以下面例子來說明：有四個葉子結點A,B,C,D,分別帶權為9,4,5,2，可以構成大量種不同的帶權二叉樹，但各個帶權二叉樹的WPL（樹的帶權路徑長度）不同，要想由n個帶權葉子結點所構成的二叉樹中，滿二叉樹或完全二叉樹不一定是最優(yōu)樹。權值越大的結點離根越近的二叉樹才是最優(yōu)二叉樹（huffman樹）。依照上面的算法，則可依照下面圖的構造過程生成huffman樹。Huffman樹產(chǎn)生流程:

1.2模塊劃分

（1）主程序模塊：

Intmain(){

初始化；輸入數(shù)據(jù)；執(zhí)行功能；

顯示結果；}

（2）各功能模塊

挑揀權值最小的兩個節(jié)點

voidselect(HuffmanTreeHT,intnode_num,int&a1,int&a2)建造霍夫曼樹

voidCreateTree(HuffmanTree&HT,HuffmanCode&HC,intcount[],charword[])編碼

voidEncodeHuffman(HuffmanTreeHT,HuffmanCodeHC)譯碼

voiddecode(HuffmanCodeHC,charchanged[],charoutput[])輸出二進制編碼

voidPrint(HuffmanCodeHC,charinput[],charafter[])輸入字符概率統(tǒng)計

intSta(char*input,intcount[],charword[])編碼效率計算

doubleRatio(charinput[],intcount[],HuffmanCodeHC)

各模塊的調用關系：主程序↓

各功能模塊

1.3測試狀況

2、費諾編碼2.1算法思想

將信源消息符號按其出現(xiàn)的概率大小依次排列排列：p1?p2???pn。在程序中由sort()函數(shù)處理，此函數(shù)是一個冒泡排序法。若想改進，可用其它的排序算法。

將依次排列的信源符號按概率值分為兩大組，使兩個組的概率之和近似一致，并且對各組賦予一個二進制碼元“0〞和“1〞。

將每一大組的信源符號再分成兩組，使劃分后的兩個組的概率之和近似一致，并且對各組賦予一個二進制符號“0〞和“1〞。

如此重復，直到每個組只剩下一個信源符號為止。在程序中本部分采用遞歸思想。

2.2模塊劃分

（1）主程序模塊：

Intmain(){

初始化；輸入數(shù)據(jù)；執(zhí)行功能；

顯示結果；

}

（2）各功能模塊

輸入字符的頻數(shù)統(tǒng)計

intSta(char*in,intcount[],charw[]){}為費諾結點分派具體數(shù)據(jù)值

voidFanoNode(charin[],intcount[],charw[]){}將費諾結點數(shù)組依照概率降序排列sort（begin，end，compare（））{}編碼

voidEncodeFano(FanoF[],floatpro,intbegin,intend){}譯碼

voiddecode(FanoF[],charafter[],charout[]){}計算編碼效率

doubleRatio(charin[],intcount[],FanoF[]){}

2.3測試狀況

3、游程編碼

3.1算法思想

用一個符號值或串長代替具有一致值的連續(xù)符號(連續(xù)符號構成了一段連續(xù)的\行程\。行程編碼因此而得名)，使符號長度少于原始數(shù)據(jù)的長度。只在各行或者各列數(shù)據(jù)的代碼發(fā)生變化時，一次記錄該代碼及一致代碼重復的個數(shù)，從而實現(xiàn)數(shù)據(jù)的壓縮。

首先,將其按行分別進行讀入和計數(shù),其次,對灰度值進行編碼,第三,對個數(shù)進行編碼,

過程:首先,我們以為例,對〞1〞我們用find函數(shù)(由于灰度級編碼時按順序存儲所以其算法通過二分法查找來實現(xiàn)的)找到其在信源符號編碼結果集中位置,然后將其碼字拷貝到存儲編碼結果的存儲結構中去.對于〞7〞則是在個數(shù)編碼結果集中去用同樣的方法進行查找,找到后也是用將其拷貝到編碼結果存儲結構中去.如此直到全部編碼終止為止.編碼的效率：

計算方法:設圖像的灰度級為M，一行的長度為N，則對每一行來說，游程數(shù)最少為1，最多為N。若將數(shù)對表示為（gk,lk）的序列，用普通二進制碼存放（gk,lk）序列，并設一行中的游程數(shù)為m，則描述一行像素的碼字長度為：m?log2M?log2N?bit.而直接存儲原圖像一行所需的位數(shù)為Nlog2Mbit。

效率P=1-?m?log2M?log2N?bit/（Nlog2Mbit*C）.(c為行數(shù))

0c3.2模塊劃分

（1）主程序模塊：

Intmain(){

初始化；輸入數(shù)據(jù)；執(zhí)行功能；

顯示結果；}

（2）各功能模塊求出編碼的長度intget_gd(intn)用于輸出編碼結果

voidprint(vectorvd)

輸出碼及其個數(shù)的組合

voidprint1(vectorre)輸出編,解碼結果

voidprint2(vectorcd,intn)讀入要編碼的灰度矩陣

boolread(vector&vr,inthd,int&cor,int&rows)用于讀取要解碼的序列

boolread1(vector&vc,intnum)

查找要編碼的灰度值是否在灰度級范圍內假使在返回相應碼在編碼序列中的位置

intfind(vectorvd,intx)

對灰度矩陣進行編碼操作成功則通過cd將其值代回

voidEncode(vectorvr,vectorvd,vectorvh,vector&cd)

對輸入要解碼的序列進行解碼操作

voidcoding(vectorvc,vector&vi,intgd,intgds)編碼效率

voidratio(intcl,intml,intcol,introw)

3.3測試狀況

4、算術編碼4.1算法思想

算術編碼是把一個信源表示為實軸上0和1之間的一個區(qū)間，信源集合中的每一個元素都用來縮短這個區(qū)間。

算法流程

1輸入信源符號個數(shù)，還有需要編碼的符號序列，計算信源概率分布

2根據(jù)概率可以算出初始編碼間隔，High——當前編碼的上限，Low——當前編碼的下限，high——中間變量，用來計算下一個編碼符號的當前間隔的上限，low——中間變量，用來計算下一個編碼符號的當前間

隔的下限，d——當前間隔之間的距離。

3掃描需編碼的符號序列，確定編碼空間第1個編碼符號的當前間隔為其初始的編碼間隔，第i個編碼符號的當前間隔為第i-1個編碼后的[Low，High），第i+1個編碼符號的當前間隔算法如下：high=Low+d*第i+1個初始編碼符號對應的上限，low=Low+d*第i+1個編碼符號對應的下限，然后H