信號理論與編碼：無失真信源編碼

實驗一無失真信源編碼

一、實驗?zāi)康呐c要求

1.理解并掌握無失真信源編碼定理的內(nèi)容及支撐理論；

2.掌握唯一可譯碼的含義及判斷方法；

3.掌握赫夫曼碼的數(shù)學(xué)基礎(chǔ)、編碼原理與實現(xiàn)技術(shù)；

4.掌握二進制、三進制赫夫曼碼的編碼方法與結(jié)果分析；

5.基于VisualC++環(huán)境使用面向?qū)ο蠓椒ㄔO(shè)計赫夫曼編碼軟件。

二、實驗儀器與設(shè)備

1.微型電子計算機80臺

2.Windows2000以上版本操作系統(tǒng)80套

3.VisualC++6.0開發(fā)系統(tǒng)80套

三、實驗內(nèi)容與步驟

(-)二進制赫夫曼編碼

使用以下兩種不同的方法編寫二進制赫夫曼碼：

?信源合并后的新符號排在其它相同概率的符號的前面；

?合并后的新符號排在其它相同概率的符號的后面。

具體要求：

1.使用VisualC++6.0開發(fā)環(huán)境，應(yīng)用面向?qū)ο蟮某绦蛟O(shè)計模式，編寫CHuffman_2類，并根

據(jù)具體要求，添加必須的數(shù)據(jù)成員和成員函數(shù)；

2.分別求出兩種編碼方法下的平均碼長、信息率和編碼效率，并分析實際中應(yīng)選擇哪種編碼

方法；

3.添加成員函數(shù)IsUniDecodableCdoe(),以判斷赫夫曼碼是否唯一可譯碼；

4.添加成員函數(shù)IsCodingwithoutDistoryion(),以判斷赫夫曼碼是否滿足無失真編碼定理；

5.用戶可以隨機輸入多個心愿符號信息，并在主函數(shù)中至少測試兩組數(shù)據(jù)，并顯示有關(guān)結(jié)果

信息。

(-)三進制赫夫曼編碼

與上述步驟類似，設(shè)計CHuffman_3類，編寫三進制赫夫曼碼。要求使用相同的測試數(shù)據(jù)，

并比較平均碼長、信息率及編碼效率等，給出自己的思考結(jié)論。

(三)m進制赫夫曼編碼

設(shè)計CHuffman_m類，編寫m進制赫夫曼碼。m在運行時由用戶輸入。其它要求同上。

綜合實驗代碼及分析：

#include<iostream.h>

#include<math.h>

#include<string.h>

#include<stdio.h>

#include<stdlib.h>

#include<vector>

usingnamespacestd;

#defineMAX10〃輸入進制，最多10進制

structHuffman_InformationSource〃信源類型

charInformationsign[10];〃信源符號

doubleProbability;〃概率

charCode[20];〃編碼結(jié)果

intCodeLength;〃碼長

)；

structHuffNode〃赫夫曼樹的節(jié)點類型

(

charInformationSign[10];

doubleProbability;

HuffNode*Subtree[MAX];〃子樹

HuffNode*Next;

charCode[20];

intCodeLength;

)；

classCHuffman_m//赫夫曼編碼

(

public:

CHuffman_m(intM)〃初始化

m=M;

ISNumber=0;

AvageCodeLength=0.0;

InformationRate=0.0;

CodeEfficiency=0.0;

)

-CHuffman_m()

//DestroyBTree(HuffTree);

)

voidHuffman_Input();〃輸入信息

voidHuffman_Sort();//排序

voidHuffman_Tree();//構(gòu)造赫夫曼樹

voidHuffman_Coding();〃生成赫夫曼編碼

voidHuffman_CodeAnalyzing();〃結(jié)果分析

voidHuffman_Display();〃顯示結(jié)果信息

voidDestroyBTree(HuffNode*TreePointer);〃釋放資源

private:

vector<Huffman_InformationSource>ISarray;〃聲明ISarray數(shù)組，初始時為空

intISNumber;〃符號個數(shù)

doubleAvageCodeLength;〃平均碼長

doubleInformationRate;//信息率

doubleCodeEfficiency;〃編碼效率

intm;//m進制

HuffNode*HuffTree;〃赫夫曼樹

private:

voidHuffman_Code(HuffNode*TreePointer);

)；//輸入信源信息

voidCHuffman_m::Huffman_Input()

{intn,i,j;

doublesum=0;

cout<<”請輸入信源符號個數(shù)：”；

cin?n;

cout〈<”請信源符號和概率：H?endl;

for(i=0;i<n;i+4-)

(

HuffmanJnformationSourcetemp;

cin?temp.InformationSign;

cin?temp.Probability;

strcpy(temp.Code,',u);

temp.CodeLength=0;

ISarray.push_back(temp);

ISNumber=ISarray.size();

)

fbr(j=0;j<ISarray.size();j4-+)

sum+=ISarray[j].Probability;

if(sum==l)

return;

else

(

cout?"\a\a\a概率和不為1!請重新輸入"<<endl;

ISarray.clear();

CHuffman_m::Huffman_Input();

)

)

〃按概率"從大到小"排序：

voidCHuffman_m::Huffman_Sort()

(

HuffmanJnformationSourcetemp;

inti,j;

for(i=0;i<ISNumber-1;i++)

for(j=i+l;j<ISNumber;j++)

if(ISaiTay[i].Probability<ISaiTayfj].Probability)

(

temp=ISaiTay[i];

ISarray[i]=ISarray[j];

ISarray[j]=temp;

〃基于ISarray數(shù)組構(gòu)造赫夫曼樹

voidCHuffman_m::Huffman_Tree()

inti,j;

HuffNode*ptrl,*ptr2;

//(1)：基于數(shù)組，創(chuàng)建單向鏈表

ptrl=newHuflNode;

strcpy(ptrl->InformationSign,ISarray[0].InformationSign);

ptrl->Probability=ISarray[0].Probability;

strcpy(ptrl->Code,ISarray[0].Code);

forG=0;j<m;j++)〃初始化子樹

ptrl->Subtree[j]=NULL;

ptrl->Next=NULL;

HuffTree=ptrl;〃賦給數(shù)據(jù)成員HuffTree

for(i=l;i<ISNumber;i++)

(

ptr2=newHuffNode;

strcpy(ptr2->InformationSign,ISarray(i].InfbrmationSign);

ptr2->Probability=ISarray[i].Probability;

strcpy(ptr2->Code,ISarray[i].Code);

for(j=0;j<m;j++)〃初始化子樹

ptr2->Subtree[j]=NULL;

plr2->Next=ptrl;

ptrl=ptr2;

)

〃結(jié)果：鏈表的表頭為數(shù)組的最小元素。

HuffTree=ptrl;〃使HuffTree指向鏈表頭

//(2)：基于鏈表，構(gòu)造赫夫曼樹

intk;〃樹的層次

ints;〃需要添加的無用符號的數(shù)目。參看教材P140/50。

k=ceil((double)(ISNumber-m)/(m-l));//"mn：表示m進制

//ceil函數(shù)：向上取整；

//floor函數(shù)：向下取整

s=m+k*(m-1)-ISNumber;

HuffNode*plr4,*templ,*temp2;

if(s!=0)〃第一次取m-s個符號

(

ptr4=newHuffNode;

strcpy(ptr4->InformationSign,n*u);〃新節(jié)點的符號為"*"

ptr2=ptrl;

ptr4->Probability=0;

for(j=0;j<m-s;j++)

ptr4->Probability+=ptr2->Probability;

ptr4->Subtree[m-s-j-1]=ptr2;//最小節(jié)點成為ptr4的"第m-s-1個子樹”，將

來賦予碼元“ms1”

ptr2=ptr2->Next;

)

for(j=m-s;j<m;j++)

ptr4->Subtree|j]=NULL;

strcpy(ptr4->Code,H;

HuffTree=ptr2;

〃重新排序：

templ=HuffTree;

while(templ&&(ptr4->Probability>templ->Probability))

(

temp2=templ;

temp1=temp1->Next;

)

ptr4->Next=templ;//插在當(dāng)前節(jié)點tempi之前

if(templ==HuffTree)

HuffTree=ptr4;

else

temp2?>Next=ptr4;〃插在temp2節(jié)點之后

ptrl=HufiTree;

)

while(ptrl->Next)

(

〃合并概率最小的m個節(jié)點，生成一個新節(jié)點ptr4：

ptr4=newHuffNode;

strcpy(ptr4->InformationSign,"**');〃新節(jié)點的符號為"”

ptr4->Probability=0;

ptr2=ptrl;

for(j=0;j<m;j++)

(

ptr4->Probability+=ptr2->Probability;

ptr4->Subtree[m-j-l]=ptr2;//最小節(jié)點成為ptr4的"第m-1個子樹”，將來

賦予碼元“m-1”

ptr2=ptr2->Next;

)

strcpy(ptr4->Code,;

HuffTree=ptr2;

〃重新排序：

tempi二HuffTree;

while(temp1&&(ptr4->Probability>templ->Probability))

temp2=templ;

temp1=temp1->Next;

)

ptr4->Next=temp1;〃插在當(dāng)前節(jié)點tempi之前

if(temp1==HuflTree)

HuffTree=ptr4;

else

temp2?>Next二ptr4;〃插在temp2節(jié)點之后

plrl=HuflTree;

)

//釋放：

ptrl=NULL;

ptr2=NULL;

ptr4=NULL;

templ=NULL;

temp2=NULL;

〃設(shè)置根節(jié)點：

strcpy(HuffTree->Code,'M,);

HuffTree->CodeLength=0;

)

〃生成赫夫曼碼：

voidCHuffman_m::Huffman_Code(HuffNode*TreePointer)

(

if(TreePointer==NULL)

return;

inti;

fbr(i=0;i<m;i++)

if(TreePointer->Subtree[i])

break;

if(i==m)//如果所有子樹均為NULL

(

for(inti=O;i<ISNumber;i++)

if(strcmp(ISarray[i].InformationSign,TreePointer->InformationSign)==0)

(

strcpy(ISarray[i].Code,TreePointer->Code);

ISarray[i].CodeLength=TreePointer->CodeLength;

return;

)

return;

)

fbr(i=0;i<m;i++)

(

if(TreePointer->Subtree[i])

〃生成子樹編碼:

chartempch[5],tempstrf10]='H,;

strcpy(tempstr,TreePointer->Code);

itoa(i,tempeh,10);〃將10進制整數(shù)i轉(zhuǎn)換為字符串，保存在tempeh中。

strcat(tempstr,tempeh);

strcpy(TreePointer->Subtree[i]->Code,tempstr);

TreePointer->Subtree[i]->CodeLength=TreePointer->CodeLength+l;

Huffman_Code(TreePointer->Subtree[i]);

)

)

)

voidCHuffman_m::Huffman_Coding()

(

Huffman_Code(HuffTree);

)

〃編碼結(jié)果分析

voidCHuffman_m::Huffman_CodeAnalyzing()

(

〃(1)：平均碼長

for(inti=0;i<ISNumber;i++)

AvageCodeLength+=ISarray[i].Probability*ISarray[i].CodeLength;

〃(2):信息率

intL=l;〃單符號時，L=1

InformationRate=AvageCodeLength/L*(log(m)/log(2));

〃(3):編碼效率

doubleHx=0;

for(intj=O;j<ISNumber;j++)〃求信源嫡

Hx+=-ISarray[j].Probability*log(ISarray[j].Probability)/log(2);

CodeEfficiency=Hx/InformationRate;

)

//顯示結(jié)果

voidCHuffman_m::Huffman_Display()

(

coutvv”編碼結(jié)果:"?endl;

for(inti=0;i<ISNumber;i++)

(

cout<<”\"'v<ISairay[i].InformationSign<<"\”'<<"：H?ISarray[i].Code?endl;

)

cout?endl;

cout?”平均碼長：n?AvageCodeLength?endl?endl;

cout<<"信息率：n?InformationRate<<endl?endl;

cout<<"編碼效率："v<CodeEfflciency<vendlv<endl;

〃釋放資源

voidCHuffman_m::DestroyBTree(HuffNode*TreePointer)

if(TreePointer!=NULL)

(

for(inti=0;i<m;i++)

if(TreePointer->Subtree[i])

DestroyBTree(TreePointer->Subtree[i]);

deleteTreePointer;

TreePointer=NULL;

)

)

〃主函數(shù)：

voidmain()

(

intm;

do{

cout<<”請輸入進制數(shù)m(2-9):”；

cin?m;

}while(m>9||m<2);

CHuffman_mYYY(m);

YYY.HuffmanJnput();

YYY.Huffman_Sort();

YYY.Huffman_Tree();

YYY.Huffman_Coding();

YYY.Huffman_CodeAnalyzing();

Y