信息論課程設(shè)計(jì)報(bào)告

本文格式為Word版，下載可任意編輯——信息論課程設(shè)計(jì)報(bào)告課程設(shè)計(jì)

目錄

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

一、概述1設(shè)計(jì)目的

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

1.2深刻理解并把握霍夫曼編碼譯碼、費(fèi)諾編碼譯碼、游程編碼譯碼、算術(shù)編碼譯碼的原理與方法；

1.3提高綜合利用所學(xué)理論知識(shí)獨(dú)立分析和解決問題的能力，提高編程能力。

2設(shè)計(jì)任務(wù)

2.1對(duì)任意的字符分別進(jìn)行2元霍夫曼編碼、2元費(fèi)諾編碼、游程編碼和

算術(shù)編碼，并進(jìn)行相應(yīng)的譯碼；2.2注意編碼效率的計(jì)算.

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

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

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

二、需求分析1問題描述

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

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

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

2基本要求

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

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

2.3游程編碼要達(dá)到的要求：輸入灰度值矩陣，進(jìn)行編碼譯碼，求出編碼效率。

2.4算術(shù)編碼要達(dá)到的要求：輸入符號(hào)串，編碼譯碼，計(jì)算精度。

三、設(shè)計(jì)過程1、霍夫曼編碼1.1算法思想

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

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

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

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

1.2模塊劃分

（1）主程序模塊：

Intmain(){

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

顯示結(jié)果；}

（2）各功能模塊

挑揀權(quán)值最小的兩個(gè)節(jié)點(diǎn)

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

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

voidEncodeHuffman(HuffmanTreeHT,HuffmanCodeHC)譯碼

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

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

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

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

各模塊的調(diào)用關(guān)系：主程序↓

各功能模塊

1.3測(cè)試狀況

2、費(fèi)諾編碼2.1算法思想

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

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

將每一大組的信源符號(hào)再分成兩組，使劃分后的兩個(gè)組的概率之和近似一致，并且對(duì)各組賦予一個(gè)二進(jìn)制符號(hào)“0〞和“1〞。

如此重復(fù)，直到每個(gè)組只剩下一個(gè)信源符號(hào)為止。在程序中本部分采用遞歸思想。

2.2模塊劃分

（1）主程序模塊：

Intmain(){

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

顯示結(jié)果；

}

（2）各功能模塊

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

intSta(char*in,intcount[],charw[]){}為費(fèi)諾結(jié)點(diǎn)分派具體數(shù)據(jù)值

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

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

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

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

2.3測(cè)試狀況

3、游程編碼

3.1算法思想

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

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

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

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

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

0c3.2模塊劃分

（1）主程序模塊：

Intmain(){

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

顯示結(jié)果；}

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

voidprint(vectorvd)

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

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

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

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

boolread1(vector&vc,intnum)

查找要編碼的灰度值是否在灰度級(jí)范圍內(nèi)假使在返回相應(yīng)碼在編碼序列中的位置

intfind(vectorvd,intx)

對(duì)灰度矩陣進(jìn)行編碼操作成功則通過cd將其值代回

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

對(duì)輸入要解碼的序列進(jìn)行解碼操作

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

voidratio(intcl,intml,intcol,introw)

3.3測(cè)試狀況

4、算術(shù)編碼4.1算法思想

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

算法流程

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

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

隔的下限，d——當(dāng)前間隔之間的距離。

3掃描需編碼的符號(hào)序列，確定編碼空間第1個(gè)編碼符號(hào)的當(dāng)前間隔為其初始的編碼間隔，第i個(gè)編碼符號(hào)的當(dāng)前間隔為第i-1個(gè)編碼后的[Low，High），第i+1個(gè)編碼符號(hào)的當(dāng)前間隔算法如下：high=Low+d*第i+1個(gè)初始編碼符號(hào)對(duì)應(yīng)的上限，low=Low+d*第i+1個(gè)編碼符號(hào)對(duì)應(yīng)的下限，然后H