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

计算机科学与工程系

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

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

五、 实验过程与实验结果
源程序：
#include
#include
#include
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;iMessage_Char==Message_Source[i]->Message_Char)
{
flag=0;
break;
}
}
return flag;
}
//对输入的概率进行检测
int Input_P_Check(){
int flag=1;
for(int i=0;iP>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<<"请输入信源发出的消息字符及相应概率（各字符与概率之间用空格隔开）:"<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，输入错误，请重新输入!"<ut<<"出现相同字符且概率越界，输入错误，请重新输入!"<P>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_PSum_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;iCode_Length*Message_Source[i]->P;
return Ave_L;
}
//求信源熵
double To_Get_H()
{
double H=0.0;
for(int i=0;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<<"山农—范诺编码结果如下:（消息字符——码长——码字）"<Message_Char<<"——>"<Code_Length<<"——>"<Code_Str<码元/消息）"<p)
{
int flag=1;//先假设输入的消息串不含非法字符
int j;
for(int i=0;temp[i]!='\0';i++){
for(j=0;jMessage_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;iMessage_Char;
}
return Message_Source_str;
}
//获取待编码消息串
string Get_Message_Str()
{
string temp;
int flag;
string Message_Source_str=Get_Message_Source_str();
A: cout<<"输入待编码的消息串(只含"<>temp;
flag=Message_Str_Check(temp);
if(flag==0)//输入的消息串含非法字符
{
cout<<"输入的消息串含非法字符,请重新输入!"<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<<"该消息串对应的编码序列如下:"</
//检测输入的二进制序列是否含有非法字符
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<<"输入的二进制序列含非法字符,请重新输入!"< int j;
for(int i=0;Binary_Str[i]!='\0';i++){
temp+=Binary_Str[i];
for(j=0;jCode_Str==temp)
{
Original_Message_Str+=Message_Source[j]->Message_Char;
temp="";//重置temp
break;
}
}
}
if(temp!=""){
cout<<"您输入的二进制序列不可译，请重新输入!"<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<<"操作错误!请执行初始化操作后再进行本操作!"<'3')
{
if(!flag)
{
cout<<"操作错误!请执行初始化操作后再进行本操作!"<