cout<<"还要继续解码吗?
(Y/N)";
cin>>q;
}while(q=='Y');
}
运行结果如下
先输入字符与权值,建立哈弗曼树结构,再进行编码,
实验二汉明码的编译码
一、实验目的
1、了解汉明码编码的原理。
2、能够建立生成矩阵,得到编码结果。
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 因此码字为:
011100101010
1、首先输入监督矩阵,之后求出生成矩阵。
2、输入四位的二进制代码序列与生成矩阵相乘得到编码结果。
#include
#include
usingnamespacestd;
#definePe0.0001
classHMCoding{
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<<"请给定("<"<H=newint*[r+1];
//初始化(n,k)汉明码监督矩阵
for(i=0;iH[i]=newint[n+1];
for(i=0;ifor(j=0;jcin>>H[i][j];
//获取监督矩阵的每一列,用于汉明码校码
voidHMCoding:
:
Get_H_Column()
{
stringtemp;
H_Column=newstring[n+1];
for(i=0;i{
temp="";
for(j=0;j{
if(!
H[j][i])
temp+='0';
else
temp+='1';
}
H_Column[i]=temp;
}
H_Column[n]="000";
}
voidHMCoding:
:
Show_G(intx,inty)
{
Get_G();
for(i=0;i{
for(j=0;jcout<cout<}
}
voidHMCoding:
:
HM_Efficiency_Analysing()
{
cout<<"对("<"<cout<<"("<cout<<"("<}
//二进制序列合理性检测
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<<"请输入待编码的二进制序列:
"<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{
for(j=0;j{
if(binary_str[i+j]=='0')
X[j]=0;
else
X[j]=1;
}
inttemp;
stringpartial_str="";
for(intt=0;t{/*用k位信息元组成的向量与生成矩阵作矩阵乘法,得到对应n元码组*/
temp=0;
for(j=0;jtemp+=X[j]*G[j][t];
if(temp%2==0)
partial_str+='0';
else
partial_str+='1';
}
code_str+=partial_str;
}
cout<<"进行("<\n"<}
//利用汉明码校码
voidHMCoding:
:
Checking()
{
B:
stringbinary_str;
intflag;
intbinary_num=0;
cout<<"请输入待译的二进制序列:
"<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;icheck_code[i]=newint[n];
for(i=0;i{/*每次取n个码元进行校正*/
for(j=0;jcheck_code[i][j]=binary_str[i*n+j]-'0';
}
}
Get_Judge_Result();
}
//获取汉明码校码结果
voidHMCoding:
:
Get_Judge_Result()
{
inttemp;
intflag;
stringpartial_str;
cout<<"("<"<cout<<"码组状态校正后"<for(intt=0;t{
flag=0;
partial_str="";
for(i=0;i{
temp=0;
for(j=0;jtemp+=H[i][j]*check_code[t][j];
if(temp%2==0)
partial_str+='0';
else
partial_str+='1';
}
//对partial_str进行判断
for(i=0;iif(H_Column[i]==partial_str)
{
flag=1;
break;
}
}
if(flag&&i{
for(j=0;jcout<cout<<"第"<
check_code[t][i]=(check_code[t][i]+1)%2;//1变0,0变1
for(j=0;jcout<}
if(flag&&i==n)//表示全对
{
for(j=0;jcout<cout<<"全对";
for(j=0;jcout<}
cout<}
}
}
//利用汉明码译码
voidHMCoding:
:
Decoding()
{
cout<<"("<"<for(i=0;i{
for(j=0;jcout<}
cout<}
/
voidHMCoding:
:
GOTO_HMCding_Z()
{
charchoice1='';
"<<"R.返回"<<""<<"Q.退出"<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<<"您没有输入正确的步骤,请重新输入!
"<gotoZ;
}
cout<}
voidmain()
{
charchoice='';
//用于记录初始化情况
intflag=0;
intn,k;
cout<<"\ncout<<"请输入汉明码的码长n=";
cin>>n;
cout<<"请输入汉明码的信息元个数k=";
cin>>k;
while(choice!
='Q'&&choice!
='q')//当choice的值不为q且不为Q时循环
{
C:
cout<<"\n;
cout<<""<<"I.输入建立"<<""<<"E.汉明码编码"<<""<<"D.汉明码校码/译码\n";
cout<<""<";
cin>>choice;
if(choice=='I'||choice=='i')//初始化
{
if(!
flag){//初次执行初始化操作
flag=1;
}
hmcoding.Initializing(n,k);
cout<<"您输入的监督矩阵H["<"<hmcoding.Show_H(n-k,n);
cout<<"该监督矩阵对应的生成矩阵G["<"<hmcoding.Show_G(k,n);
hmcoding.HM_Efficiency_Analysing();
}
elseif(choice=='E'||choice=='e')//进行编码
{
if(!
flag)
{
cout<<"操作错误!
请执行输入建立操作后再进行本操作!
"<gotoC;
}
hmcoding.Encoding();
}
elseif(choice=='D'||choice=='d')//校码、译码
{
if(!
flag)
{
cout<<