汉明码实验报告(内附C--源码).doc

计算机科学与工程系
一、 实验名称：汉明码
二、 实验环境
软件环境：Windows 2000，Microsoft Visual C++6.0
硬件环境：P4，2.4GHz，256内存，IBM-PC及兼容机
三、 实验目的
了解汉明码的编码原理，纠错原理，译码原理；给定汉明码的监督矩阵，能够写出生成矩阵，能够通过监督矩阵或生成矩阵进行编码，能够通过监督矩阵进行校码与译码，会计算汉明码的错误概率以及导出增余汉明码等相关知识。
四、 实验内容
在Microsoft Visual c++ 6.0软件环境下，编写一个程序，使之实现汉明码以及增余汉明码的编码、检码、译码过程。
1、通过对书本的学习，以及对课堂知识的掌握，了解汉明码的纠错原理，编写出汉明码的纠错程序。
2、基于汉明码的编写，进一步完成对检码译码及增余汉明码的实现。
3、实验验证程序的合理性，结果的正确性，和结构的完善性。
五、 实验过程与实验结果
源程序：
#include<iostream>
#include<string>
using namespace std;
#define Pe 0.0001
class HMCoding{
private:
int n,k,r;//汉明码参数
int i,j;//用于指示循环次数
int **H,*X,**G,**check_code;
string *H_Column,*H_Column_Z,code_str;
int code_num,code_num_z;
public:
void Initializing(int,int);
void Show_H(int,int);
void Get_G();
void Show_G(int,int);
void HM_Efficiency_Analysing();/*对汉明码进行编码效率分析*/
int Binary_Str_Check(string);
void Encoding();//汉明码编码
void Encoding_Z();//增余汉明码编码
void Decoding();//汉明码译码
void Decoding_Z();//增余汉明码译码
void Get_H_Column();//获取汉明码监督矩阵的每一列
void Get_H_Column_Z();//获取增余汉明码监督矩阵的每一列
void Get_Judge_Result();//获取汉明码校码结果
void Get_Judge_Result_Z();//获取增余汉明码校码结果
void Checking();//汉明码校码
void Checking_Z();//增余汉明码校码
void GOTO_HMCding_Z();
};
HMCoding hmcoding;//全局变量
/*********************************初始化模块*********************************/
void HMCoding::Initializing(int _n,int _k)
{
n=_n;
k=_k;
r=_n-_k;
cout<<"请给定（"<<n<<"，"<<k<<"）汉明码的监督矩阵H["<<r<<"]["<<n<<"]:"<<endl;
H=new int *[r+1];
//初始化(n,k)汉明码监督矩阵
for(i=0;i<r+1;i++)
H[i]=new int[n+1];
for(i=0;i<r;i++)
for(j=0;j<n;j++)
cin>>H[i][j];
//初始化增余项
for(j=0;j<n+1;j++)
H[r][j]=1;
for(i=0;i<r;i++)
H[i][n]=0;
//为X分配存储单元
X=new int[n+1];
for(j=0;j<n+1;j++)
X[j]=0;
Get_H_Column();//获取监督矩阵的每一列
Get_H_Column_Z();//进一步获取增余监督矩阵的每一列
}
//获取监督矩阵的每一列，用于汉明码校码
void HMCoding::Get_H_Column()
{
string temp;
H_Column=new string[n+1];
for(i=0;i<n;i++)
{
temp="";
for(j=0;j<r;j++)
{
if(!H[j][i])
temp+='0';
else
temp+='1';
}
H_Column[i]=temp;
}
H_Column[n]="000";
}
//获取增余监督矩阵的每一列，用于增余汉明码校码
void HMCoding::Get_H_Column_Z()
{
H_Column_Z=new string[n+2];
for(i=0;i<n+1;i++)
H_Column_Z[i]=H_Column[i]+'1';
H_Column_Z[n+1]="0000";
}
void HMCoding::Show_H(int x,int y)
{
for(i=0;i<x;i++)
{
for(j=0;j<y;j++)
cout<<H[i][j]<<" ";
cout<<endl;
}
}
void HMCoding::Get_G()
{
G=new int *[k];
for(i=0;i<k;i++)
G[i]=new int[n];
for(i=0;i<k;i++)
for(j=0;j<k;j++)
{
if(i==j)
G[i][j]=1;
else
G[i][j]=0;
}
for(i=0;i<r;i++)
for(j=0;j<k;j++)
G[j][i+k]=H[i][j];

}
void HMCoding::Show_G(int x,int y)
{
Get_G();
for(i=0;i<x;i++)
{
for(j=0;j<y;j++)
cout<<G[i][j]<<" ";
cout<<endl;
}
}
void HMCoding::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;
}
/*********************************编码模块*********************************/
//二进制序列合理性检测
int HMCoding::Binary_Str_Check(string temp)
{
int flag=1;//先假设输入的消息串不含除0、1外的字符
for(int i=0;temp[i]!='\0';i++)
{
if(!(temp[i]=='0'||temp[i]=='1'))
{
flag=0;
break;
}
}
return flag;
}
//汉明码编码
void HMCoding::Encoding()
{
A: string binary_str;
int flag;
int binary_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";
goto A;
}
if(binary_num%k!=0&&!flag)
{
cout<<"您输入的二进制序列存在冗余且含除0、1外的字符，请重新输入!\n";
goto A;
}
if(binary_num%k==0&&!flag)
{
cout<<"您输入的二进制序列含除0、1外的字符，请重新输入!\n";
goto A;
}
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;
else
X[j]=1;
}
int temp;
string partial_str="";
for(int t=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';
else
partial_str+='1';
}
code_str+=partial_str;
}
cout<<"进行（"<<n<<"，"<<k<<"）汉明码编码后的二进制序列为：\n"<<code_str<<endl;
}
//增余汉明码编码
void HMCoding::Encoding_Z()
{
code_str="";
A_Z:string binary_str;
int flag;
int binary_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";
goto A_Z;
}
if(binary_num%k!=0&&!flag)
{
cout<<"您输入的二进制序列存在冗余且含除0、1外的字符，请重新输入!\n";
goto A_Z;
}
if(binary_num%k==0&&!flag)
{
cout<<"您输入的二进制序列含除0、1外的字符，请重新输入!\n";
goto A_Z;
}
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;
else
X[j]=1;
}
int temp;
string partial_str="";
for(int t=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';
X[j+k]=0;
}
else{
partial_str+='1';
X[j+k]=1;
}

}
//生成增余汉明码最后一位
//监督规则：对原汉明码所有n个码元取模2和
int sum=0;
for(j=0;j<n;j++)
sum+=X[j];
if(sum%2==0)
partial_str+='0';
else
partial_str+='1';
code_str+=partial_str;
}
cout<<"进行（"<<n+1<<"，"<<k<<"）增余汉明码编码后的二进制序列为：\n"<<code_str<<endl;
}
/*********************************校码模块*********************************/
//利用汉明码校码
void HMCoding::Checking()
{
B: string binary_str;
int flag;
int binary_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";
goto B;
}
if(binary_num%n!=0&&!flag)
{
cout<<"您输入的二进制序列存在冗余且含除0、1外的字符，请重新输入!\n";
goto B;
}
if(binary_num%n==0&&!flag)
{
cout<<"您输入的二进制序列含除0、1外的字符，请重新输入!\n";
goto B;
}
code_num=binary_num/n;//统计n元码组的个数
check_code=new int*[code_num];
for(i=0;i<code_num;i++)
check_code[i]=new int[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();
}
//利用增余汉明码校码
void HMCoding::Checking_Z()
{
B_Z:string binary_str;
int flag;
int binary_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+1)!=0&&flag)/*序列所含码元个数不是n+1的整数倍，无法全部译码*/
{
cout<<"您输入的二进制序列存在冗余，请重新输入!\n";
goto B_Z;
}
if(binary_num%(n+1)!=0&&!flag)
{
cout<<"您输入的二进制序列存在冗余且含除0、1外的字符，请重新输入!\n";
goto B_Z;
}
if(binary_num%(n+1)==0&&!flag)
{
cout<<"您输入的二进制序列含除0、1外的字符，请重新输入!\n";
goto B_Z;
}
code_num_z=binary_num/(n+1);//统计n+1元码组的个数
check_code=new int*[code_num_z];
for(i=0;i<code_num_z;i++)
check_code[i]=new int[n+2];
for(i=0;i<code_num_z;i++)
{/*每次取n+1个码元进行校正*/
for(j=0;j<n+1;j++){
check_code[i][j]=binary_str[i*(n+1)+j]-'0';
}
}
Get_Judge_Result_Z();
}
//获取汉明码校码结果
void HMCoding::Get_Judge_Result()
{
int temp;
int flag;
string partial_str;
cout<<"（"<<n<<"，"<<k<<"）汉明码校码结果如下："<<endl;
cout<<"码组 状态 校正后"<<endl;
for(int t=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';
else
partial_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变1
for(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;
}
}
//获取增余汉明码校码结果
void HMCoding::Get_Judge_Result_Z()
{
int temp;
int flag;
string partial_str;
cout<<"（"<<n+1<<"，"<<k<<"）增余汉明码校码结果如下（注：* 表示无法识别的码元）："<<endl;
cout<<"码组 状态 校正后"<<endl;
for(int t=0;t<code_num_z;t++)
{
flag=0;
partial_str="";
for(i=0;i<r+1;i++)
{
temp=0;
for(j=0;j<n+1;j++)
temp+=H[i][j]*check_code[t][j];
if(temp%2==0)
partial_str+='0';
else
partial_str+='1';
}
//对partial_str进行判断
for(i=0;i<n+2;i++){
if(H_Column_Z[i]==partial_str)
{
flag=1;
break;
}
}
if(flag&&i<n+1)//表示第i个码元出错，将其改正
{
check_code[t][n+1]=1;//表示正确接收
for(j=0;j<n+1;j++)
cout<<check_code[t][j];
cout<<" 第"<<i+1<<"位错，可纠正 ";
check_code[t][i]=(check_code[t][i]+1)%2;//1变0，0变1
for(j=0;j<n+1;j++)
cout<<check_code[t][j];
}
if(flag&&i==n+1)//表示全对
{
check_code[t][n+1]=1;//表示正确接收
for(j=0;j<n+1;j++)
cout<<check_code[t][j];
cout<<" 全对 ";
for(j=0;j<n+1;j++)
cout<<check_code[t][j];
}
if(!flag)
{
check_code[t][n+1]=0;//表示两位出错并无法纠正
for(j=0;j<n+1;j++)
cout<<check_code[t][j];
cout<<" 某两位出错，无法纠正 ";
for(j=0;j<n+1;j++)
cout<<'*';//* 表示无法正确识别的码元
}
cout<<endl;
}
}
/*********************************译码模块*********************************/
//利用汉明码译码
void HMCoding::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;
}
//利用增余汉明码译码
void HMCoding::Decoding_Z()
{
cout<<"（"<<n+1<<"，"<<k<<"）增余汉明码译码结果为（注：* 表示无法识别的码元）："<<endl;
for(i=0;i<code_num_z;i++)
{
if(check_code[i][n+1]==1)
{
for(j=0;j<k;j++)
cout<<check_code[i][j];
}else
{
for(j=0;j<k;j++)
cout<<'*';
}
}
cout<<endl;
}
/*********************************主函数*********************************/
void HMCoding::GOTO_HMCding_Z()
{
char choice1=' ';
cout<<"\n ***************欢迎进入（"<<n+1<<","<<k<<"）增余汉明码编码/校码/译码系统****************\n";
cout<<"由汉明监督矩阵导出的增余监督矩阵H["<<r+1<<"]["<<n+1<<"]为："<<endl;
hmcoding.Show_H(r+1,n+1);
Z: cout<<"\n >>>>>>>>>>>>>>>>>>>>>（"<<n+1<<","<<k<<"）增余汉明码编码/校码/译码系统<<<<<<<<<<<<<<<<<<<<\n";
cout<<" "<<"E.增余汉明码编码"<<" "<<"D.增余汉明码校码/译码"<<" "<<"R.返回"<<" "<<"Q.退出"<<endl;
cout<<"请输入您要操作的步骤：";
cin>>choice1;
if(choice1=='E'||choice1=='e')//进行编码
{
hmcoding.Encoding_Z();
goto Z;
}
else if(choice1=='D'||choice1=='d')
{
hmcoding.Checking_Z();
hmcoding.Decoding_Z();
goto Z;
}
else if(choice1=='R'||choice1=='r')
return;
else if(choice1=='Q'||choice1=='q')//退出
{
exit(0);
}
else//如果选了选项之外的就让用户重新选择
{
cout<<"您没有输入正确的步骤，请重新输入！"<<endl;
goto Z;
}
cout<<endl;
}
void main()
{
char choice=' ';
//用于记录初始化情况
int flag=0;
int n,k;
cout<<"\n09计科二班信息论第二实验小组小组成员：学号——姓名"<<endl;
cout<<"20091883 潘柳燕"<<endl;
cout<<"20091888 李文超"<<endl;
cout<<"20091908 周发洪"<<endl;
cout<<"20091909 吴针朋"<<endl;
cout<<"20091911 张 丹（组长）"<<endl;
cout<<"\n *************************汉明码编码/校码/译码系统*************************\n";
cout<<"请输入汉明码的码长n=";
cin>>n;
cout<<"请输入汉明码的信息元个数k=";
cin>>k;
while(choice!='Q'&&choice!='q')//当choice的值不为q且不为Q时循环
{
C: cout<<"\n >>>>>>>>>>>>>>>>>>>>>>>（"<<n<<","<<k<<"）汉明码编码/校码/译码系统<<<<<<<<<<<<<<<<<<<<\n";
cout<<" "<<"I.输入建立"<<" "<<"E.汉明码编码"<<" "<<"D.汉明码校码/译码\n";
cout<<" "<<"Z.进入相应的增余汉明码系统"<<" "<<"Q.退出\n";
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();
}
else if(choice=='E'||choice=='e')//进行编码
{
if(!flag)
{
cout<<"操作错误!请执行输入建立操作后再进行本操作!"<<endl;
goto C;
}
hmcoding.Encoding();
}
else if(choice=='D'||choice=='d')//校码、译码
{
if(!flag)
{
cout<<"操作错误!请执行输入建立操作后再进行本操作!"<<endl;
goto C;
}
hmcoding.Checking();
hmcoding.Decoding();
}
else if(choice=='Z'||choice=='z')
{
if(!flag)
{
cout<<"操作错误!请执行输入建立操作后再进行本操作!"<<endl;
goto C;
}
//进入增余汉明码系统
hmcoding.GOTO_HMCding_Z();
}
else if(choice=='Q'||choice=='q')//退出
{
exit(0);
}
else//如果选了选项之外的就让用户重新选择
{
cout<<"您没有输入正确的步骤，请重新输入！"<<endl;
goto C;
}
cout<<endl;
}
}
运行结果：
1、 首先需输入建立（n，k）汉明码

2、 给定监督矩阵，导出相应的生成矩阵，显示出错误概率及编码效率

3、 汉明码编码
注：输入的信息序列应为k的整数倍，否则会报错。

正确编码：

4、 汉明码校码、译码
注：待译的二进制序列应为n的整倍数，否则报错。

演示：全对、1位错（可纠正）

5、 导出相应的增余汉明码

6、 增余汉明码编码
注：输入的信息序列应为k的整数倍，否则会报错。

7、 增余汉明码校码、译码
注：待译的二进制序列应为（n+1）的整倍数，否则报错。
演示：全对、1位错（可纠正）、2位错（不可纠正）

8、 退出系统

18