山农―范诺编码实验报告(完整版)

计算机科学与工程系一、实验名称：山农—范诺编码二、实验环境软件环境：Windows2000，MicrosoftVisualC++6.0硬件环境：P4，2.4GHz，256内存，IBM-PC及兼容机三、实验目的掌握山农—范诺编码、译码原理，并能够通过程序模拟山农—范诺编码、译码功能。四、实验原理1、首先把消息按概率不同由大到小的次序重新排列；2、把这个概率序列分成尽可能相等的两组，对每一组又同样分成概率尽可能相等的两组，如此下去，直至每个消息都被分出来为止；3、在每一次划分中，所有第一组的消息均以符号0表示，而第二组的消息则以1表示。五、实验过程与实验结果源程序：#includemath.h#includeiostream#includestringusingnamespacestd;staticintMessage_Num=0;typedefstructMessage{charMessage_Char;//消息字符名称doubleP;//消息字符对应的概率doubleSum_P;//消息字符对应的累加概率stringCode_Str;//消息字符对应的码字doubleCode_Length;//消息字符对应的码长}Message,*Message_P;//数据定义Message_P*Message_Source;/**********************初始化模块**********************///对输入的字符进行检验intInput_Char_Check(){intflag=1;intj;for(inti=0;iMessage_Num-1&&flag;i++){for(j=i+1;jMessage_Num;j++)if(Message_Source[j]-Message_Char==Message_Source[i]-Message_Char){计算机科学与工程系2flag=0;break;}}returnflag;}//对输入的概率进行检测intInput_P_Check(){intflag=1;for(inti=0;iMessage_Num;i++){if(!(Message_Source[i]-P0&&Message_Source[i]-P1))//概率越界{flag=0;break;}}returnflag;}//初始化voidInit_Message_Source(){Message_Source=newMessage_P[];/*一个信源可以包含多个字符，由于每个字符用一个结构体描述，故信源则需用结构体数组来描述*/Message_Ptemp;I:doublen=0;//n=1intflag_n=1;if(Message_Num){//若Message_Num非零则将其置为零Message_Num=0;}cout请输入信源发出的消息字符及相应概率（各字符与概率之间用空格隔开）:endl;do{temp=newMessage;cintemp-Message_Chartemp-P;n+=temp-P;//概率累加if(n1){flag_n=0;break;}temp-Sum_P=0.0;temp-Code_Length=0;temp-Code_Str=;Message_Source[Message_Num]=temp;计算机科学与工程系3Message_Num++;//消息字符数加1}while(n1);if(!flag_n){cout概率之和超过1，输入错误，请重新输入!endl;gotoI;}intflag1=Input_Char_Check();//检测输入的字符是否重复intflag2=Input_P_Check();//检测输入的概率是否越界if(!flag1&&flag2){cout出现相同字符，输入错误，请重新输入!endl;gotoI;}if(!flag2&&flag1){cout概率越界，输入错误，请重新输入!endl;gotoI;}if(!flag1&&!flag2){cout出现相同字符且概率越界，输入错误，请重新输入!endl;gotoI;}}/**********************山农—范诺最佳编码模块**********************///要进行编码，首先根据各消息的概率由大到小排序voidBubble_Message(){Message_Ptemp;for(inti=0;iMessage_Num-1;i++)for(intj=i+1;jMessage_Num;j++)if(Message_Source[i]-PMessage_Source[j]-P){temp=Message_Source[i];Message_Source[i]=Message_Source[j];Message_Source[j]=temp;}}//局部概率累加函数voidSum_P_Function(intstart,intend){Message_Source[start]-Sum_P=Message_Source[start]-P;for(inti=start+1;i=end;i++)计算机科学与工程系4Message_Source[i]-Sum_P=Message_Source[i]-P+Message_Source[i-1]-Sum_P;}//根据待分组的各消息的累加概率，找出分组边界intFind_Boundary(intstart,intend){/*思路：找出与（待分组的所有消息的概率和的一半最接近的）累加概率相对应的编号*/intboundary;doubletag=Message_Source[end]-Sum_P/2;for(inti=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(intj=start+1;j=end;j++)if(Message_Source[j]-Sum_PMessage_Source[boundary]-Sum_P)boundary=j;returnboundary;}//对所给消息进行编码voidSet_Code(intstart,intend){intboundary;Bubble_Message();//由已知概率求累加概率Sum_P_Function(start,end);//找出分组边界boundary=Find_Boundary(start,end);for(inti=start;i=boundary;i++)//上半组编码为0Message_Source[i]-Code_Str+=0;for(intj=boundary+1;j=end;j++)//下半组编码为1Message_Source[j]-Code_Str+=1;for(intm=start;m=end;m++)Message_Source[m]-Code_Length+=1;//此次分组中的各消息码长加1if(start!=boundary)//上半组包含一个以上消息，仍需进一步分组编码Set_Code(start,boundary);//递归实现对上半组进一步分组编码if(boundary+1!=end)//下半组包含一个以上消息，仍需进一步分组编码Set_Code(boundary+1,end);//递归实现对下半组进一步分组编码}/**********************编码效率分析模块**********************///求平均编码长度doubleAve_Code_Length()计算机科学与工程系5{doubleAve_L=0.0;for(inti=0;iMessage_Num;i++)Ave_L+=Message_Source[i]-Code_Length*Message_Source[i]-P;returnAve_L;}//求信源熵doubleTo_Get_H(){doubleH=0.0;for(inti=0;iMessage_Num;i++)H+=-1*Message_Source[i]-P*log(Message_Source[i]-P)/log(2);returnH;}//求编码效率doubleTo_Get_Code_Efficiency(){doubleH2,H,Ave_L;H=To_Get_H();Ave_L=Ave_Code_Length();H2=H/Ave_L;returnH2;}//分析结果输出voidOutput(){doubleH2,H,Ave_L;H=To_Get_H();Ave_L=Ave_Code_Length();H2=To_Get_Code_Efficiency();cout山农—范诺编码结果如下:（消息字符——码长——码字）endl;for(inti=0;iMessage_Num;i++)coutMessage_Source[i]-Message_Char——Message_Source[i]-Code_Length——Message_Source[i]-Code_Strendl;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;}/**********************编码模块**********************///字符合理性检测计算机科学与工程系6intMessage_Str_Check(stringtemp){intflag=1;//先假设输入的消息串不含非法字符intj;for(inti=0;temp[i]!='\0';i++){for(j=0;jMessage_Num;j++){if(temp[i]==Message_Source[j]-Message_Char)break;}if(j==Message_Num)//表示出现非法字符{flag=0;break;}}returnflag;}//获取信源发出的消息字符并整合成字符串stringGet_Message_Source_str(){inti;stringMessage_Source_str=;for(i=0;iMessage_Num;i++){Message_Source_str+=Message_Source[i]-Message_Char;}returnMessage_Source_str;}//获取待编码消息串stringGet_Message_Str(){stringtemp;intflag;stringMessage_Source_str=Get_Message_Source_str();A:cout输入待编码的消息串(只含Message_Source_str):\n;cintemp;flag=Message_Str_Check(temp);if(flag==0)//输入的消息串含非法字符{cout