汉明码编译码程序说明.docx

汉明码编译码程序说明汉明码编译码原理程序说明书 1、线性分组码 假设信源输出为一系列二进制数字0和1.在分组码中，这些二进制信息序列分成固定长度的消息分组。每个消息分组记为u，由k个信息位组成。因此共有2k种不同的消息。编码器按照一定的规则将输入的消息u转换为二进制n维向量v，这里n>k。此n维向量v就叫做消息u的码字或码向量。因此，对应于2种不同的消息，也有2种码字。这2个码字的集合就叫一个分组码。 一个长度为n，有2个码字的分组码，当且仅当其2个码字构成域GF上所有nkkkkk维向量空间的一个k维子空间时被称为线性码。 对于线性分组码，希望它具有相应的系统结构，其码字可分为消息部分和冗余校验部分两个部分。消息部分由k个未经改变的原始信息位构成，冗余校验部分则是n-k个奇偶校验位位，这些位是信息位的线性和。具有这样的结构的线性分组码被称为线性系统分组码。 本实验以汉明码的编译码来具体说明线性系统分组码的特性。 其主要参数如下： 码长：n=2-1 信息位：k=2-1-m 校验位：m=n-k，且m³3 最小距离： mmdmin=d0=3 由于一个的线性码C是所有二进制n维向量组成的向量空间Vn的一个k维子空间，则可以找到k个线性独立的码字，g0,g1,gk-1 ，使得C中的每个码字v都是这k个码字的一种线性组合。 汉明码的生成矩阵如下，前三位为冗余校验部分，后四位为消息部分。 ìg0üì1 1 0 1 0 0 0üïgïï0 1 1 0 1 0 0ïïïïïG=í1ý=íý g1 1 1 0 0 1 0ï2ïïïïî1 0 1 0 0 0 1ïþîg3ïþï如果u=(u0u1u2u3)是待编码的消息序列，则相应的码字可如下给出： ìg0üïgïïïv=ugG=(u0u1u2u3)gí1ý=u0g0+u1g1+u2g2+u3g3 ïg2ïïîg3ïþ编码结构即码字v=(v0v1v2v3v4v5v6)，对于线性分组码汉明码而言，v3,v4,v5,v6为所提供的消息序列，而v0=v3Åv5Åv，v1=v3Åv4Åv5，6v2=v4Åv5Åv6。 由以上关系可以得到汉明码的全部码字如下所示： k=4，n=7的线性分组码 消息 (0000) (1000) (0100) (1100) (0010) (1010) (0110) (1110) 码字 (0000000) (1101000) (0110100) (1011100) (1110010) (0011010) (1000110) (0101110) 消息 (0001) (1001) (0101) (1101) (0011) (1011) (0111) (1111) 码字 (1010001) (0111001) (1100101) (0001101) (0100011) (1001011) (0010111) (1111111) 2、用C+编写汉明码编译码程序的思路如下： 编码程序 循环输入待编码消息序列u=(u0u1u2u3),首先判断输入是否符合输入条件：输入必须是4位0，1序列，共有2种情况。 编码程序如下： for(j=0;j<7;j+) if(j=3) vj= u0; if(j=4) vj= u1; if(j=5) vj= u2; if(j=6) vj= u3; if(j=0) 4 vj= (u0u2)u3); /异或运算 if(j=1) vj= (u0u1)u2); /异或运算 if(j=2) vj= (u1u2)u3); /异或运算 cout << vj << " " cout<<endl; 编码的思想为： v3=u0 v4=u1 v5=u2 v0=v3Åv5Åv6 v1=v3Åv4Åv5 v2=v4Åv5Åv6 译码程序： 循环输入待译码的码字序列v=(v0v1v2v3v4v5v6),第一步判断输入是否符合输入条件：输入必须是7位0，1序列，共有2种情况。但是2种情况中只有2即16个有效码字，那么第二步则是要判断是否是2即16个有效码字，这也是编码的一个检错方式，利用其奇偶校验矩阵H，校正子s，接收到的码字序列为r，判断s=r*H是否等于0。若等于0，则证明是有效码字；若不等于0，则证明不属于16个有效码字的一个。 T4774Tì1001011üïïl 奇偶校验矩阵H=í0101110ý ï0010111ïîþì100üï010ïïïï001ïïïTl 奇偶校验矩阵H=í110ý ï011ïïïï111ïï101ïîþ以下为纠错的关键程序： for(j=0;j<3;j+) a=(v0*ht0j)(v1*ht1j)(v2*ht2j)(v3*ht3j)(v4*ht4j)(v5*ht5j)(v6*ht6j); result=result+a; if(result!=0) cout<<"输入的是无效的字码"<<endl; goto loop; else cout<<"输入字码有效"<<endl; cout<<"您所输入的待译码的码字序列为：" 接下来便是译码的两个主要方法： 第一个方法为查表法：程序中check_table函数便是查表法。 表格如下： k=4，n=7的线性分组码 消息 (0000) (1000) (0100) (1100) (0010) (1010) (0110) (1110) 码字 (0000000) (1101000) (0110100) (1011100) (1110010) (0011010) (1000110) (0101110) 消息 (0001) (1001) (0101) (1101) (0011) (1011) (0111) (1111) 码字 (1010001) (0111001) (1100101) (0001101) (0100011) (1001011) (0010111) (1111111) 第二个方法编码方法便是：系统码直接取信息位译码 程序如下： for(j=0;j<4;j+) if(j=0) uj= v3; if(j=1) uj= v4; if(j=2) uj= v5; if(j=3) uj= v6; cout << uj << " " 3、程序附录 /(7,4)编译码程序 #include <iostream> using namespace std; void check_table; /编码程序 int main int g47=1,1,0,1,0,0,0,0,1,1,0,1,0,0,1,1,1,0,0,1,0,1,0,1,0,0,0,1; /声明生成矩阵G,即4个线性独立的码字，可以使码本C中的码字v都是这k个码字的一种线性组合, int h37=1,0,0,1,0,1,1,0,1,0,1,1,1,0,0,0,1,0,1,1,1; /声明校验矩阵H， int ht73=1,0,0,0,1,0,0,0,1,1,1,0,0,1,1,1,1,1,1,0,1; /声明校验矩阵H的转置矩阵HT int u4; /声明待编码的消息序列,即未编码前的信息序列 int v7; /声明编码后的码字序列 /int s7; int i,j,k; /顺序输入待编码4位信息序列 lable: cout<<"请输入4位待编码消息序列："<<endl; for(i=0;i<4;i+) cin>>ui; /判断是否输入正确数据 for(i=0;i<4;i+) if(u0=0|u0=1)&(u1=0|u1=1)&(u2=0|u2=1)&(u3=0|u3=1) cout<<"您所输入的待编码消息序列为：" for(i=0;i<4;i+) cout<<ui; cout<<endl; else cout<<"输入错误！请输入正确的二进制4位0，1信息序列！"<<endl; goto lable; cout<<endl; /输出生成矩阵 cout <<"(7,4)汉明码的生成矩阵G为："<<endl; for(i=0;i<4;i+) for(j=0;j<7;j+) cout <<gij<< " " cout << endl; cout << endl; /编码程序 /码字的系统结构分为冗余校验部分和消息部分,结构形式：v(x)=v0,v1,v2,v3,v4,v5,v6 /编码序列中v3，v4，v5，v6均为所提供的消息序列,对于(7,4)汉明码: / v0=v3v5v6; / v1=v3v4v5; / v2=v4v5v6; cout<<" 等待编码中 "<<endl; cout<<"编码成功！编码后的码字序列为："<<" " for(j=0;j<7;j+) if(j=3) vj= u0; if(j=4) vj= u1; if(j=5) vj= u2; if(j=6) vj= u3; if(j=0) vj= (u0u2)u3); /异或运算 if(j=1) vj= (u0u1)u2); /异或运算 if(j=2) vj= (u1u2)u3); /异或运算 cout << vj << " " cout<<endl; /顺序输入7位待译码有效码字序列 loop: int a,result=0; cout<<"请输入7位待译码有效的消息序列："<<endl; for(i=0;i<7;i+) cin>>vi; cout<<endl; for(i=0;i<7;i+) cout<<vi; /1.判断是否输入正确0,1序列 if(v0=0|v0=1)&(v1=0|v1=1)&(v2=0|v2=1)&(v3=0|v3=1)&(v4=0|v4=1)&(v5=0|v5=1)&(v6=0|v6=1) cout<<"输入字码合法"<<endl; else cout<<"输入错误！请输入正确的二进制7位0，1码字序列！"<<endl; goto loop; /2.判断是否为有效码字 for(j=0;j<3;j+) a=(v0*ht0j)(v1*ht1j)(v2*ht2j)(v3*ht3j)(v4*ht4j)(v5*ht5j)(v6*ht6j); result=result+a; if(result!=0) cout<<"输入的是无效的字码"<<endl; goto loop; else cout<<"输入字码有效"<<endl; cout<<"您所输入的待译码的码字序列为：" for(i=0;i<7;i+) cout<<vi; cout<<endl; /输出校验矩阵H cout <<"(7,4)汉明码的校验矩阵H为："<<endl; for(i=0;i<3;i+) for(j=0;j<7;j+) cout <<hij<< " " cout << endl; cout << endl; /输出校验矩阵HT，目的是为了利用校正子进行编码检测s=r*HT; cout <<"(7,4)汉明码的校验矩阵H的转置矩阵为："<<endl; for(i=0;i<7;i+) for(j=0;j<3;j+) cout <<htij<< " " cout << endl; cout << endl; /检错算法 check_table;/查表法 cout<<"译码方法二：系统码直接取信息位译码 "<<endl; cout<<" 等待译码中 "<<endl; cout<<"译码成功！译码后的消息序列为："<<" " for(j=0;j<4;j+) if(j=0) uj= v3; if(j=1) uj= v4; if(j=2) uj= v5; if(j=3) uj= v6; cout << uj << " " cout<<endl; system("pause"); return 0; /查表法函数 void check_table cout<<"译码方法一：查表法"<<endl; cout<<" k=4,n=7的线性分组码的全部码字 "<<endl; cout<<" 消息 码字 | 消息 码字"<<endl; cout<<"(0000) (0000000) | (0001) (1010001)"<<endl; cout<<"(1000) (1101000) | (1001) (0111001)"<<endl; cout<<"(0100) (0110100) | (0101) (1100101)"<<endl; cout<<"(1100) (1011100) | (1101) (0001101)"<<endl; cout<<"(0010) (1110010) | (0011) (0100011)"<<endl; cout<<"(1010) (0011010) | (1011) (1001011)"<<endl; cout<<"(0110) (1000110) | (0111) (0010111)"<<endl; cout<<"(1110) (0101110) | (1111) (1111111)"<<endl; 运行结果如下： 编码结果为： 译码结果为：