山农—范诺编码实验报告.doc

计算机科学与工程系

一、 实验名称：山农—范诺编码
二、 实验环境
软件环境：Windows 2000，Microsoft Visual C++6.0
硬件环境：P4，2.4GHz，256内存，IBM-PC及兼容机
三、 实验目的
掌握山农—范诺编码、译码原理，并能够通过程序模拟山农—范诺编码、译码功能。
四、 实验原理

1、 首先把消息按概率不同由大到小的次序重新排列；
2、 把这个概率序列分成尽可能相等的两组，对每一组又同样分成概率尽可能相等的两组，如此下去，直至每个消息都被分出来为止；
3、 在每一次划分中，所有第一组的消息均以符号0表示，而第二组的消息则以1表示。

五、 实验过程与实验结果
源程序：
#include<math.h>
#include<iostream>
#include<string>
using namespace std;
static int Message_Num=0;
typedef struct Message{
char Message_Char;//消息字符名称
double P;//消息字符对应的概率
double Sum_P;//消息字符对应的累加概率
string Code_Str;//消息字符对应的码字
double Code_Length;//消息字符对应的码长
}Message,* Message_P;
//数据定义
Message_P * Message_Source;
/**********************初始化模块**********************/
//对输入的字符进行检验
int Input_Char_Check()
{
int flag=1;
int j;
for(int i=0;i<Message_Num-1&&flag;i++)
{
for(j=i+1;j<Message_Num;j++)
if(Message_Source[j]->Message_Char==Message_Source[i]->Message_Char)
{
flag=0;
break;
}
}
return flag;
}
//对输入的概率进行检测
int Input_P_Check(){
int flag=1;
for(int i=0;i<Message_Num;i++)
{
if(!(Message_Source[i]->P>0&&Message_Source[i]->P<1))//概率越界
{
flag=0;
break;
}
}
return flag;
}
//初始化
void Init_Message_Source(){
Message_Source=new Message_P[];/*一个信源可以包含多个字符，
由于每个字符用一个结构体描述，故信源则需用结构体数组来描述*/
Message_P temp;
I: double n=0;//n<=1
int flag_n=1;
if(Message_Num){//若Message_Num非零则将其置为零
Message_Num=0;
}
cout<<"请输入信源发出的消息字符及相应概率（各字符与概率之间用空格隔开）:"<<endl;
do{
temp=new Message;
cin>>temp->Message_Char>>temp->P;
n+=temp->P;//概率累加
if(n>1)
{
flag_n=0;
break;
}
temp->Sum_P=0.0;
temp->Code_Length=0;
temp->Code_Str="";
Message_Source[Message_Num]=temp;
Message_Num++;//消息字符数加1
}while(n<1);
if(!flag_n)
{
cout<<"概率之和超过1，输入错误，请重新输入!"<<endl;
goto I;
}
int flag1=Input_Char_Check();//检测输入的字符是否重复
int flag2=Input_P_Check();//检测输入的概率是否越界
if(!flag1&&flag2)
{
cout<<"出现相同字符，输入错误，请重新输入!"<<endl;
goto I;
}
if(!flag2&&flag1)
{
cout<<"概率越界，输入错误，请重新输入!"<<endl;
goto I;
}
if(!flag1&&!flag2)
{
cout<<"出现相同字符且概率越界，输入错误，请重新输入!"<<endl;
goto I;
}
}
/**********************山农—范诺最佳编码模块**********************/
//要进行编码，首先根据各消息的概率由大到小排序
void Bubble_Message()
{
Message_P temp;
for(int i=0;i<Message_Num-1;i++)
for(int j=i+1;j<Message_Num;j++)
if(Message_Source[i]->P<Message_Source[j]->P)
{
temp=Message_Source[i];
Message_Source[i]=Message_Source[j];
Message_Source[j]=temp;
}
}
//局部概率累加函数
void Sum_P_Function(int start,int end){
Message_Source[start]->Sum_P=Message_Source[start]->P;
for(int i=start+1;i<=end;i++)
Message_Source[i]->Sum_P=Message_Source[i]->P+Message_Source[i-1]->Sum_P;
}
//根据待分组的各消息的累加概率，找出分组边界
int Find_Boundary(int start,int end)
{ /*思路：找出与（待分组的所有消息的概率和的一半最接近的）累加概率相对应的编号
*/
int boundary;
double tag=Message_Source[end]->Sum_P/2;
for(int i=start;i<=end;i++)
/*为避免浪费存储空间，可直接用Message_Source[i]->Sum_P
存放Message_Source[i]->Sum_P-tag的差的绝对值*/
Message_Source[i]->Sum_P=(double)fabs(Message_Source[i]->Sum_P-tag);
//找出Message_Source[i]->Sum_P的最小者的下标
boundary=start;
for(int j=start+1;j<=end;j++)
if(Message_Source[j]->Sum_P<Message_Source[boundary]->Sum_P)
boundary=j;
return boundary;
}
//对所给消息进行编码
void Set_Code(int start,int end){
int boundary;
Bubble_Message();
//由已知概率求累加概率
Sum_P_Function(start,end);
//找出分组边界
boundary=Find_Boundary(start,end);
for(int i=start;i<=boundary;i++)//上半组编码为0
Message_Source[i]->Code_Str+="0";
for(int j=boundary+1;j<=end;j++)//下半组编码为1
Message_Source[j]->Code_Str+="1";
for(int m=start;m<=end;m++)
Message_Source[m]->Code_Length+=1;//此次分组中的各消息码长加1
if(start!=boundary)//上半组包含一个以上消息，仍需进一步分组编码
Set_Code(start,boundary);//递归实现对上半组进一步分组编码
if(boundary+1!=end)//下半组包含一个以上消息，仍需进一步分组编码
Set_Code(boundary+1,end);//递归实现对下半组进一步分组编码
}
/**********************编码效率分析模块**********************/
//求平均编码长度
double Ave_Code_Length()
{
double Ave_L=0.0;
for(int i=0;i<Message_Num;i++)
Ave_L+=Message_Source[i]->Code_Length*Message_Source[i]->P;
return Ave_L;
}
//求信源熵
double To_Get_H()
{
double H=0.0;
for(int i=0;i<Message_Num;i++)
H+=-1*Message_Source[i]->P*log(Message_Source[i]->P)/log(2);
return H;
}
//求编码效率
double To_Get_Code_Efficiency()
{
double H2,H,Ave_L;
H=To_Get_H();
Ave_L=Ave_Code_Length();
H2=H/Ave_L;
return H2;
}
//分析结果输出
void Output()
{
double H2,H,Ave_L;
H=To_Get_H();
Ave_L=Ave_Code_Length();
H2=To_Get_Code_Efficiency();
cout<<"山农—范诺编码结果如下:（消息字符——码长——码字）"<<endl;
for(int i=0;i<Message_Num;i++)
cout<<Message_Source[i]->Message_Char<<"——>"<<Message_Source[i]->Code_Length<<"——>"<<Message_Source[i]->Code_Str<<endl;
cout<<"平均编码长度Ave_L=L1*p1+L2*p2+...+Ln*pn="<<Ave_L<<"（码元/消息）"<<endl;
cout<<"信源熵H=-（p1*log(p1)+p2*log(p2)+...+pn*log(pn)）/log(2)="<<H<<"（bit/消息）"<<endl;
cout<<"码元熵H2=H/Ave_L="<<H2<<"（bit/码元）"<<endl;
cout<<"编码效率E=（H2/H2max）*100%="<<H2*100<<"%"<<endl;
}
/**********************编码模块**********************/
//字符合理性检测
int Message_Str_Check(string temp)
{
int flag=1;//先假设输入的消息串不含非法字符
int j;
for(int i=0;temp[i]!='\0';i++){
for(j=0;j<Message_Num;j++)
{
if(temp[i]==Message_Source[j]->Message_Char)
break;
}
if(j==Message_Num)//表示出现非法字符
{
flag=0;
break;
}
}
return flag;
}
//获取信源发出的消息字符并整合成字符串
string Get_Message_Source_str()
{
int i;
string Message_Source_str="";
for(i=0;i<Message_Num;i++)
{
Message_Source_str+=Message_Source[i]->Message_Char;
}
return Message_Source_str;
}
//获取待编码消息串
string Get_Message_Str()
{
string temp;
int flag;
string Message_Source_str=Get_Message_Source_str();
A: cout<<"输入待编码的消息串(只含"<<Message_Source_str<<"):\n";
cin>>temp;
flag=Message_Str_Check(temp);
if(flag==0)//输入的消息串含非法字符
{
cout<<"输入的消息串含非法字符,请重新输入!"<<endl;
goto A;
}
return temp;
}
//对输入的消息串进行编码
string Get_All_Code_Str(string Message_Str)
{
string All_Code_Str="";
int j;
for(int i=0;Message_Str[i]!='\0';i++)
for(j=0;j<Message_Num;j++)
{
if(Message_Str[i]==Message_Source[j]->Message_Char)
{
All_Code_Str+=Message_Source[j]->Code_Str;
break;
}
}
return All_Code_Str;
}
//输出得到的二进制序列
void Output_All_Code_Str(string All_Code_Str)
{
cout<<"该消息串对应的编码序列如下:"<<endl;
cout<<All_Code_Str<<endl;
}
//编码
void Encoding()
{
string Message_Str,All_Code_Str;
Message_Str=Get_Message_Str();
All_Code_Str=Get_All_Code_Str(Message_Str);
Output_All_Code_Str(All_Code_Str);
}
/**********************译码模块**********************/
//检测输入的二进制序列是否含有非法字符
int Binary_Str_Check(string temp)
{
int flag=1;//假设不含非法字符
for(int i=0;temp[i]!='\0';i++)
{
if(!(temp[i]=='0'||temp[i]=='1'))
{
flag=0;
break;
}
}
return flag;
}
//获取待译的二进制序列
string Get_Binary_Str()
{
string temp;
int flag;
B: cout<<"输入待译的二进制序列:\n";
cin>>temp;
flag=Binary_Str_Check(temp);
if(flag==0)//输入的二进制序列含非法字符
{
cout<<"输入的二进制序列含非法字符,请重新输入!"<<endl;
goto B;
}
return temp;
}
//获取源码
string Get_Original_Message_Str(string Binary_Str,int *flag)
{
string temp="";
*flag=1;
string Original_Message_Str="";
int j;
for(int i=0;Binary_Str[i]!='\0';i++){
temp+=Binary_Str[i];
for(j=0;j<Message_Num;j++)
{
if(Message_Source[j]->Code_Str==temp)
{
Original_Message_Str+=Message_Source[j]->Message_Char;
temp="";//重置temp
break;
}
}
}
if(temp!=""){
cout<<"您输入的二进制序列不可译，请重新输入!"<<endl;
*flag=0;
}
return Original_Message_Str;
}
//输出得到的源码
void Output_Original_Message_Str(string Original_Message_Str)
{
cout<<"该二进制序列对应的源码如下:"<<endl;
cout<<Original_Message_Str<<endl;
}
//译码
void Decoding()
{
int flag;
string Binary_Str,Original_Message_Str;
D: Binary_Str=Get_Binary_Str();
Original_Message_Str=Get_Original_Message_Str(Binary_Str,&flag);
if(!flag)
goto D;
Output_Original_Message_Str(Original_Message_Str);
}
/**********************主函数**********************/
void main()
{
char choice=' ';
int flag=0;

cout<<"\n";
while(choice!='4')
{
C: cout<<" "<<"*************************山农—范诺编码/译码器*************************\n";
cout<<" "<<"1.初始化"<<" "<<"2.编码"<<" "<<"3.译码"<<" "<<"4.退出\n";
cout<<"请输入您要操作的步骤：";
cin>>choice;
if(choice=='1')
{
if(!flag){//初次执行初始化操作
flag=1;
}
//信源初始化
Init_Message_Source();
//获取消息字符码字
Set_Code(0,Message_Num-1);
//效率分析结果输出
Output();

}
else if(choice=='2')
{
if(!flag)
{
cout<<"操作错误!请执行初始化操作后再进行本操作!"<<endl;
goto C;
}
//编码
Encoding();
}
else if(choice=='3')
{
if(!flag)
{
cout<<"操作错误!请执行初始化操作后再进行本操作!"<<endl;
goto C;
}
//译码
Decoding();
}
else if(choice=='4')
{
exit(0);//退出
}
else//如果选了选项之外的就让用户重新选择
{
cout<<"您没有输入正确的步骤，请重新输入!"<<endl;
}
cout<<endl;
}
}

运行结果：
1、 输入消息及相应概率，建立编码/译码系统，并对此系统作出评价

2、 编码：输入的消息字符串中应只含信源能够发出的几个字符，否则，报错

3、 译码：注意区分可译序列和不可译序列

4、 退出系统

11