信息论实验教材

实验一哈夫曼的编码wc一、实验目的1、了解哈弗曼树编码与译码的原理2、能够建立哈弗曼树的结构，并对其进行正确的编码与译码实验内容1、根据输入的权值信息建立哈夫曼树输出各个叶子结点所表示字符的哈夫曼编码对给定的密码串进行解码三、原理（1）初始化，根据符号概率的大小按由大到小顺序对符号进行排序。

（2）把概率最小的两个符号组成一个新符号（节点），新符号的概率等于这两个符号概率（3）重复第2步，直到形成一个符号为止（树），其概率最后等于1。

（4）从编码树的根开始回溯到原始的符号，并将每一下分枝赋值为1，上分枝赋值为0。然后就可以对每一个符号进行编码了，四、代码如下#include<iostream.h>#include<string.h>constintMAX=20;structhuffnode{ intweight; intlchild,rchild,parent;};structhuffinit//输入的权值信息的结构{chardata;intweight;};structhuffcode//哈夫曼树编码的结构{chardata;charcode[MAX+1];};classHuffTree//哈夫曼树类的声明{public:HuffTree(huffinitw[],intn);~HuffTree(){}voidSelect(int&min1,int&min2,intm);voidOutput();//输出哈夫曼树最终状态（tree数组）voidEncode();//编码voidDecode(charcode[]);//解码private:huffnodetree[2*MAX-1];//存储哈夫曼树huffcodecd[MAX];//存储各个哈夫曼编码intsize;//哈夫曼树的叶子结点数};HuffTree::HuffTree(huffinitw[],intn){size=n; for(inti=0;i<2*n-1;i++) { tree[i].parent=-1; tree[i].lchild=-1; tree[i].rchild=-1; } for(i=0;i<n;i++) {tree[i].weight=w[i].weight; cd[i].data=w[i].data;} intmin1=-1; intmin2=-1; intm=size; for(intk=n;k<2*n-1;k++) { Select(min1,min2,m); tree[min1].parent=k; tree[min2].parent=k; tree[k].weight=tree[min1].weight+tree[min2].weight; tree[k].lchild=min1; tree[k].rchild=min2; m++; }}voidHuffTree::Select(int&min1,int&min2,intm)//选择两个权值最小的结点{inta=100; intb=100; for(inti=0;i<m;i++) { if(tree[i].weight<a&&tree[i].parent==-1) { a=tree[i].weight; min1=i; } } for(i=0;i<m;i++) { if(tree[i].weight<b&&tree[i].parent==-1&&i!=min1) { b=tree[i].weight; min2=i; }}}voidHuffTree::Output(){ for(inti=0;i<2*size-1;i++) { cout<<tree[i].weight<<""<<tree[i].parent<<""<<tree[i].lchild<<""<<tree[i].rchild<<endl; }}voidHuffTree::Encode()//编码{intm;inta;intj;charb[100];intk;for(inti=0;i<size;i++) {m=i;j=0; while(tree[m].parent!=-1) { a=m;m=tree[m].parent; if(tree[m].lchild==a) b[j++]='0'; else b[j++]='1'; }for(k=0,j=j-1;j>=0;j--)cd[i].code[k++]=b[j];cd[i].code[k]='\0';cout<<cd[i].data<<"--->"<<cd[i].code<<endl;;} }voidHuffTree::Decode(charcode[])//解码{intn=strlen(code);inta=2*size-2;//根节点的下标 for(inti=0;i<n;i++) { if(code[i]=='0') { a=tree[a].lchild; } if(code[i]=='1') a=tree[a].rchild;if(tree[a].lchild==-1&&tree[a].rchild==-1) {cout<<cd[a].data; a=2*size-2; } else if(code[i+1]=='\0') cout<<"error"; } cout<<endl;}voidmain(){huffinitw[20]; intn; chars[100]; cout<<"请输入字符个数："; cin>>n; for(inti=0;i<n;i++) { cout<<"请输入第"<<i+1<<"个字符及权值："; cin>>w[i].data; cin>>w[i].weight; }HuffTreeH(w,n); cout<<"已经建好的节点信息为"<<endl; H.Output(); cout<<"已经建好的节点编码信息为"<<endl; H.Encode(); charq;do { cout<<"请输入密码："; cin>>s; H.Decode(s); cout<<endl; cout<<"还要继续解码吗?(Y/N)"; cin>>q; }while(q=='Y');}运行结果如下先输入字符与权值，建立哈弗曼树结构，再进行编码，实验二汉明码的编译码一、实验目的1、了解汉明码编码的原理。2、能够建立生成矩阵，得到编码结果。实验原理海明码(HammingCode)编码的关键是使用多余的奇偶校验位来识别一位错误。码字(CodeWord)按如下方法构建：1、把所有2的幂次方的数据位标记为奇偶校验位(编号为1,2,4,8,16,32,64等的位置)2、其他数据位用于待编码数据.(编号为3,5,6,7,9,10,11,12,13,14,15,17等的位置)3、每个奇偶校验位的值代表了代码字中部分数据位的奇偶性，其所在位置决定了要校验和跳过的比特位顺序。位置1：校验1位，跳过1位，校验1位，跳过1位(1,3,5,7,9,11,13,15,…)位置2：校验2位，跳过2位，校验2位，跳过2位(2,3,6,7,10,11,14,15,…)位置4：校验4位，跳过4位，校验4位，跳过4位(4,5,6,7,12,13,14,15,20,21,22,23,…)位置8：校验8位，跳过8位，校验8位，跳过8位(8-15,24-31,40-47,…)…如果全部校验的位置中有奇数个1，把该奇偶校验位置为1；如果全部校验的位置中有偶数个1，把该奇偶校验位置为0.举例说明：一个字节的数据：10011010构造数据字(DataWord),对应的校验位留空__1_001_1010计算每个校验位的奇偶性(?代表要设置的比特位):位置1检查1,3,5,7,9,11:?_1_001_1010.偶数个1，因此位置1设为0，即:0_1_001_1010位置2检查2,3,6,7,10,11:0?1_001_1010.奇数个1，因此位置2设为1，即:011_001_1010位置4检查4,5,6,7,12:011?001_1010.奇数个1，因此位置4设为1，即:0111001_1010位置8检查8,9,10,11,12:0111001?1010.偶数个1，因此位置8设为0，即:011100101010因此码字为:0111001010101、首先输入监督矩阵，之后求出生成矩阵。2、输入四位的二进制代码序列与生成矩阵相乘得到编码结果。#include<iostream>#include<string>usingnamespacestd;#definePe0.0001classHMCoding{private:intn,k,r;//汉明码参数inti,j;//用于指示循环次数int**H,*X,**G,**check_code;string*H_Column,*H_Column_Z,code_str;intcode_num,code_num_z;public:voidInitializing(int,int);voidShow_H(int,int);voidGet_G();voidShow_G(int,int);voidHM_Efficiency_Analysing();/*对汉明码进行编码效率分析*/intBinary_Str_Check(string);voidEncoding();//汉明码编码voidDecoding();//汉明码译码voidGet_H_Column();//获取汉明码监督矩阵的每一列voidGet_Judge_Result();//获取汉明码校码结果voidChecking();//汉明码校码voidGOTO_HMCding_Z();};HMCodinghmcoding;//全局变量voidHMCoding::Initializing(int_n,int_k){n=_n;k=_k;r=_n-_k;cout<<"请给定（"<<n<<"，"<<k<<"）汉明码的监督矩阵H["<<r<<"]["<<n<<"]:"<<endl;H=newint*[r+1];//初始化(n,k)汉明码监督矩阵for(i=0;i<r+1;i++)H[i]=newint[n+1];for(i=0;i<r;i++)for(j=0;j<n;j++)cin>>H[i][j];//获取监督矩阵的每一列，用于汉明码校码voidHMCoding::Get_H_Column(){stringtemp;H_Column=newstring[n+1];for(i=0;i<n;i++){temp="";for(j=0;j<r;j++){if(!H[j][i])temp+='0';elsetemp+='1';}H_Column[i]=temp;}H_Column[n]="000";}voidHMCoding::Show_G(intx,inty){Get_G();for(i=0;i<x;i++){for(j=0;j<y;j++)cout<<G[i][j]<<"";cout<<endl;}}voidHMCoding::HM_Efficiency_Analysing(){cout<<"对（"<<n<<"，"<<k<<"）汉明码的评价如下："<<endl;cout<<"（"<<n<<"，"<<k<<"）汉明码的效率E=k/n*100%="<<k*1.0/n*100<<"%"<<endl;cout<<"（"<<n<<"，"<<k<<"）汉明码的错误概率P=n*(n-1)*Pe*Pe="<<n*(n-1)*Pe*Pe<<endl;}//二进制序列合理性检测intHMCoding::Binary_Str_Check(stringtemp){intflag=1;//先假设输入的消息串不含除0、1外的字符for(inti=0;temp[i]!='\0';i++){if(!(temp[i]=='0'||temp[i]=='1')){flag=0;break;}}returnflag;}//汉明码编码voidHMCoding::Encoding(){A: stringbinary_str;intflag;intbinary_num=0;cout<<"请输入待编码的二进制序列："<<endl;cin>>binary_str;flag=Binary_Str_Check(binary_str);while(binary_str[binary_num]!='\0')binary_num++;/*统计输入的二进制序列所含码元个数*/if(binary_num%k!=0&&flag)/*序列所含码元个数不是k的整数倍，无法全部编码*/{cout<<"您输入的二进制序列存在冗余，请重新输入!\n";gotoA;}if(binary_num%k!=0&&!flag){cout<<"您输入的二进制序列存在冗余且含除0、1外的字符，请重新输入!\n";gotoA;}if(binary_num%k==0&&!flag){cout<<"您输入的二进制序列含除0、1外的字符，请重新输入!\n";gotoA;}code_str="";for(i=0;i<binary_num;i=i+k){for(j=0;j<k;j++)/*获取k位信息元*/{if(binary_str[i+j]=='0')X[j]=0;elseX[j]=1;}inttemp;stringpartial_str="";for(intt=0;t<n;t++){/*用k位信息元组成的向量与生成矩阵作矩阵乘法，得到对应n元码组*/temp=0;for(j=0;j<k;j++)temp+=X[j]*G[j][t];if(temp%2==0)partial_str+='0';elsepartial_str+='1';}code_str+=partial_str;}cout<<"进行（"<<n<<"，"<<k<<"）汉明码编码后的二进制序列为：\n"<<code_str<<endl;}//利用汉明码校码voidHMCoding::Checking(){B: stringbinary_str;intflag;intbinary_num=0;cout<<"请输入待译的二进制序列："<<endl;cin>>binary_str;flag=Binary_Str_Check(binary_str);while(binary_str[binary_num]!='\0')binary_num++;/*统计输入的二进制序列所含码元个数*/if(binary_num%n!=0&&flag)/*序列所含码元个数不是n的整数倍，无法全部译码*/{cout<<"您输入的二进制序列存在冗余，请重新输入!\n";gotoB;}if(binary_num%n!=0&&!flag){cout<<"您输入的二进制序列存在冗余且含除0、1外的字符，请重新输入!\n";gotoB;}if(binary_num%n==0&&!flag){cout<<"您输入的二进制序列含除0、1外的字符，请重新输入!\n";gotoB;}code_num=binary_num/n;//统计n元码组的个数check_code=newint*[code_num];for(i=0;i<code_num;i++)check_code[i]=newint[n];for(i=0;i<code_num;i++){/*每次取n个码元进行校正*/for(j=0;j<n;j++){check_code[i][j]=binary_str[i*n+j]-'0';}}Get_Judge_Result();}//获取汉明码校码结果voidHMCoding::Get_Judge_Result(){inttemp;intflag;stringpartial_str;cout<<"（"<<n<<"，"<<k<<"）汉明码校码结果如下："<<endl;cout<<"码组状态校正后"<<endl;for(intt=0;t<code_num;t++){flag=0;partial_str="";for(i=0;i<r;i++){temp=0;for(j=0;j<n;j++)temp+=H[i][j]*check_code[t][j];if(temp%2==0)partial_str+='0';elsepartial_str+='1';}//对partial_str进行判断for(i=0;i<n+1;i++){if(H_Column[i]==partial_str){flag=1;break;}}if(flag&&i<n)//表示第i个码元出错，将其改正{for(j=0;j<n;j++)cout<<check_code[t][j];cout<<"第"<<i+1<<"位错，可纠正";check_code[t][i]=(check_code[t][i]+1)%2;//1变0，0变1for(j=0;j<n;j++)cout<<check_code[t][j];}if(flag&&i==n)//表示全对{for(j=0;j<n;j++)cout<<check_code[t][j];cout<<"全对";for(j=0;j<n;j++)cout<<check_code[t][j];}cout<<endl;}}}//利用汉明码译码voidHMCoding::Decoding(){cout<<"（"<<n<<"，"<<k<<"）汉明码译码结果为："<<endl;for(i=0;i<code_num;i++){for(j=0;j<k;j++)cout<<check_code[i][j];}cout<<endl;}/voidHMCoding::GOTO_HMCding_Z(){charchoice1='';"<<"R.返回"<<""<<"Q.退出"<<endl;cout<<"请输入您要操作的步骤：";cin>>choice1;if(choice1=='E'||choice1=='e')//进行编码{hmcoding.Encoding_Z();gotoZ;}elseif(choice1=='D'||choice1=='d'){hmcoding.Checking_Z();hmcoding.Decoding_Z();gotoZ;}elseif(choice1=='R'||choice1=='r')return;elseif(choice1=='Q'||choice1=='q')//退出{exit(0);}else//如果选了选项之外的就让用户重新选择{cout<<"您没有输入正确的步骤，请重新输入！"<<endl;gotoZ;}cout<<endl;}voidmain(){charchoice='';//用于记录初始化情况intflag=0;intn,k;cout<<"\n cout<<"请输入汉明码的码长n=";cin>>n;cout<<"请输入汉明码的信息元个数k=";cin>>k;while(choice!='Q'&&choice!='q')//当choice的值不为q且不为Q时循环{C: cout<<"\n;cout<<""<<"I.输入建立"<<""<<"E.汉明码编码"<<""<<"D.汉明码校码/译码\n";cout<<""<< cout<<"请输入您要操作的步骤：";cin>>choice;if(choice=='I'||choice=='i')//初始化{if(!flag){//初次执行初始化操作flag=1;}hmcoding.Initializing(n,k);cout<<"您输入的监督矩阵H["<<n-k<<"]["<<n<<"]为:"<<endl;hmcoding.Show_H(n-k,n);cout<<"该监督矩阵对应的生成矩阵G["<<k<<"]["<<n<<"]为:"<<endl;hmcoding.Show_G(k,n);hmcoding.HM_Efficiency_Analysing();}elseif(choice=='E'||choice=='e')//进行编码{if(!flag){cout<<"操作错误!请执行输入建立操作后再进行本操作!"<<endl;gotoC;}hmcoding.Encoding();}elseif(choice=='D'||choice=='d')//校码、译码{if(!flag){cout<<"操作错误!请执行输入建立操作后再进行本操作!"<<endl;gotoC;}hmcoding.Checking();hmcoding.Decoding();}elseif(choice=='Z'||choice=='z'){if(!flag){cout<<"操作错误!请执行输入建立操作后再进行本操作!"<<endl;gotoC;}}实验结果如下：实验三香农编码的编译码一、实验目的：了解香农编码的基本原理。了解香农编码的优点与缺点。二、实验原理：1、首先输入一个n值，确定编码的个数然后相应输出编码的概率。2、将这些概率用冒泡法从大到小进行排列。3、计算累加概率。4、根据每个码长长度在所对应的信息量与信息量之间，得出码长。5、将每一个码所对应的累加概率转化为二进制小数，编码为小数点后码长长度的序列。三、实现代码：#include<stdio.h>#include<math.h>#include<stdlib.h>#include<iostream.h>#defineN7voidmain(){ inti,j; doublep[N]={0},temp; doubleq[N]={0};//概率数组 doublejx[N]; intKL[N];//码字长度数组 doublek[N]={0},l[N]={0};//求码字长度的中间数组 inta[N][N]={0};//二进制存储数组 printf("请输入信源码的概率6ge：\n"); for(i=1;i<N;i++) scanf("%lf",&p[i]); //将概率进行排序操作 for(i=1;i<N;i++) { for(j=i+1;j<N;j++) { if(p[i]<p[j]) { temp=p[i]; p[i]=p[j]; p[j]=temp; } } } cout<<"从大到小排序：\n"; for(i=1;i<=6;i++) { printf("第%d个信源概率是：",i); cout<<p[i]<<endl; } //求累加概率 for(i=0;i<N;i++) { j=i+1; q[j]=q[i]+p[i]; jx[j]=q[j]; } //求码字长度 for(i=0,j=0;i<N;i++,j++) { k[j]=-log(p[i])/log(2); l[j]=1-log(p[i])/log(2); if(l[j]>(int)(k[j]+1)) KL[j]=l[j]; elseKL[j]=k[j]; }//求累加概率的二进制形式，即码字 for(i=1;i<N;i++) { for(j=1;j<=KL[i]+1;j++) { q[i]=q[i]*2; if(q[i]>=1) { q[i]=q[i]-1; a[i][j]=1; } elsea[i][j]=0; } }//输出码字 printf("码字为："); for(i=0;i<N;i++) { for(j=1;j<KL[i]+1;j++) printf("%d",a[i][j]);// if(i)// printf("(0.");// for(j=1;j<KL[i]+1;j++)// printf("%d",a[i][j]);// if(i)// printf(")2"); printf("\n"); } intw; doublesum=0; cout<<"\n请输入码长:"; cin>>w; doublem[10]; for(i=0;i<w;i++) cin>>m[i]; for(i=0;i<w;i++) { for(j=0;j<=i;j++) m[i]=m[i]/2; sum+=m[i]; } for(i=1;i<N;i++) if(sum>jx[i]) { printf("译码结果是：这是第%d个信源码\n",j+1); break; }}实验四循环码的编译码一、实验目的：1、了解循环码编码的基本原理。2、了解循环编码的优点与缺点。二．实验原理：循环码：无权码，每位代码无固定权值，任何相邻的两个码组中，仅有一位代码不同，（7，3）循环码由式x^7+1=（x+1）（x^3+x^2+1）（x^3+x+1）可以得出生成多项式g(x)=x^4+x^2+x+1或者为g(x)=x^4+x^3+x^2+1，拟定一个规则使得信号源用1到8这8组编码表达一定的含义并作为信号输出（当要表达的信号较为复杂情况下使用多个码组表示一个信号），在接收端对接受的信号应用公式：R(x)/g(x)=Q(x)+r(x)/g(x)看是否有余项，即以余项是否为零来判别接收的码组中有无错误。（7，3）循环码的码重为4，最小码距d也为4，由于一种编码的最小码距d的大小直接关系这种编码的检错和纠错能力，关系如下：1.为检测e个错码，de+1.2.为了纠正t个错码，d2t+1..3.为了纠正t个错码同时检测e个错码，de+t+1.所以（7，3）循环码可以单独检测3个错码，单独纠正1个错码，同时检测2个错码并纠正1个错码。对于（7，3）循环码的纠错，我们利用不同位置上错码导致R(x)/g(x)=Q(x)+r(x)/g(x)生成不同的r(x)来做出图表，我们可以发现对于上述同一组码组，无论编号是什么只要错码在相同位上得出的r(x)相同三、实验步骤：#include<stdio.h>#include<math.h>#include<stdlib.h>/*函数声明*/voidBegin();voidCode();voidDecoding();/*主函数*/main(){printf("\n(7,3)循环码的编码和译码\n");Begin();}/*进行编码*/voidCode(){intInput[3];intOutput[7];intreg[4]={0,0,0,0};inttemp,i,j,t;printf("请输入3位信息码（输入3次，一次一位）:");for(i=0;i<3;i++)scanf("%d",&Input[i]);/*输入3位信息码*/for(i=0;i<3;i++)/*进行除法操作*/{temp=reg[3]+Input[i];/*生成多项式为g(x)=x^4+x^3+x^2+1*/if(temp==2)temp=0;reg[3]=reg[2]+temp;if(reg[3]==2)reg[3]=0;reg[2]=reg[1]+temp;if(reg[2]==2)reg[2]=0;reg[1]=reg[0];reg[0]=temp;}for(i=0;i<3;i++)Output[i]=Input[i];/*进行编码操作*/for(i=3;i<7;i++){temp=reg[3];for(j=3;j>0;j--)reg[j]=reg[j-1];reg[0]=0;Output[i]=temp;}printf("________________________________________");printf("\n");printf("编码结果:\n");for(i=0;i<7;i++)printf("%d",Output[i]);/*输出编码结果*/printf("\n");printf("________________________________________");printf("\n");Begin();}/*译码并进行纠检错*/voidDecoding(){intInput[7],Output[7];intreg[4]={0,0,0,0,};inttemp,i,d,x,p;printf("\n请输入7位码字（一次一位，输入7次）:");for(i=0;i<7;i++)scanf("%d",&Input[i]);/*输入接受码组*/for(i=0;i<7;i++)/*进入除法电路*/{temp=reg[3]; /*计算伴随式S(x)*/reg[3]=reg[2]+temp;if(reg[3]==2)reg[3]=0;reg[2]=reg[1]+temp;if(reg[2]==2)reg[2]=0;reg[1]=reg[0];reg[0]=temp+Input[i];if(reg[0]==2)reg[0]=0;}p=reg[3]+2*reg[2]+4*reg[1]+8*reg[0];if(p!=1&&p!=2&&p!=3&&p!=7&&p!=8&&p!=13&&p!=14&&p!=0){ /*输入错误位数大于2位*/printf("\"Theerror>=2\"\n");getchar();exit(0);}printf("_________