《海明码的校验》由会员分享，可在线阅读，更多相关《海明码的校验（13页珍藏版）》请在金锄头文库上搜索。
1、计算机网络课程设计报告设计题目：海明码的校验2009年12月18日一需求分析二总体设计2. 1明码的概念2.2海明码的原理2.3海明码的编码规则2.4海明码的生成和接收三流程图四运行代码五运行界面与截图六总结七参考文献需求分析海明码是由R.Hamming在1950年提出的，是一种可以纠错的编码。用在海明码 中的全部传输码字是由原来的信息和附加的奇偶校验位组成的。每一个这种奇偶位被编 在传输码字的特定位置上。这个系统对于错误的数位无论是原有信息位中的，还是附加 校验位中的都能指示出来。海明码的纠错能力和最小码距有关。最终实现了数据包检错 和纠错主要功能，达到了预定要求，为网络传输尽量减少差错，创
2、造良好的传输环境。二总体设计2.1海明码的概念海明码是一种可以纠正一位差错的编码。它是利用在信息位为k位，增加r位冗余 位，构成一个n=k+r位的码字，然后用r个监督关系式产生的r个校正因子来区分无错和 在码字中的n个不同位置的一位错。它必需满足以下关系式：2人r=n+1 或 2Ar=k+r+1。海明码的编码效率为：R=k/(k+r)；式中k为信息位位数，r为增加冗余位位数，2.2海明码的原理在数据中间加入几个校验码，将玛距均匀拉大，将数据的每个二进制位分配在几个 奇偶校验组里，当某一位出错，会引起几个校验位的值发生变化。海明不等式：校验码个数为K，2的K次幕个信息，1个信息用来指出“没有错误
3、”，其余2K-1 个指出错误发生在那一位，但也可能是校验位错误，故有N1,3,5,7,9,11；B-2,3,6,7,10,11；C-4,5,6,7,12；(注 5=4+1； 6=4+2； 7=4+2+1； 12=8+4)D-8,9,10,11,12。3) 把线性码位的值的偶校验作为冗余码的值(设冗余码初值为0)：A=E(0,1,1,0,1,0)=1B=E(0,1,0,0,1,0)=0C=E(0,1,0,0,0) =1D=E(0,1,1,0,0) =04) 海明码为:1 0 1 1 1 0 0 0 1 1 0 02)海明码的接收。例4.已知：接收的码字为：1 0 0 1 1 0 0 0 1 1
4、0 0(k=8) 求：发送端的信息码。解：1)设错误累加器(err)初值=02)求出冗余码的偶校验和，并按码位累加到err中：A=E(1,0,1,0,1,0)=1 err=err+20=1B=E (0,0,0,0,1,0)=1 err=err+21=3C=E(1,1,0,0,0) =0 err=err+0 =3D=E(0,1,1,0,0) =0 err=err+0 =3由err#0可知接收码字有错，3) 码字的错误位置就是错误累加器(err)的值3。4) 纠错-对码字的第3位值取反得正确码字：1 0 1 1 1 0 0 0 1 1 0 05) 把位于2的k次方位的冗余码删除得信息码：1 1 0
5、 0 1 1 0 0三流程图四运行代码 编码(encode)和纠错(check)的相关程序。#include #include #include #define N 1270#define K 1200#define G 70/#define HAIMINGusing namespace std;int lenN;int i_2_r(int a) /求一个25 次方的数的幕int count=0;if(a=1)return 0;while(a1)a=a/2;count+;return count;void in_to_Group(int a,int b,int n) 添加到各组中int i;f
6、or(i=1;i= k+r+1int i,s = 1;for(i = 1;i = k+r+1)return 1;elsereturn 0;int is_i_2_r(int i) 判断 i 是否为 25 位if(i = 1)return 1;if(i%2 != 0)return 0;while(i%2 = 0 & i != 1)i=i/2;if(i=1)return 1;return 0;int int_to_invdec(int a,int n) 求一个整数的逆序的二进制码int i=1; /以计算校验位号while(n)ai+=n%2;n/=2;return i-1; 返回位数int cou
7、nt1(int a,int n) 计算 1 的个数int i,count = 0;for(i = 1;i = n;i+)if(ai = 1)count+;if(count%2 = 0)return 1;return 0;void main()#ifdef HAIMINGfreopen(海明码.txt,r,stdin);#endifint inforN,i,k,r,findr = 1;int groupGK,g,j; / group用于分组检测1的个数int aN,a_l;printf(n输入有效信息位位数k(0=k=1200):);scanf(%d,&k);i=2;while(findr) 找
8、所需检测位数r的值r=i;if(_2_r_gt_k_r(k,r)findr = 0;i+;printf(n需添加%d位检测位.n,r);printf(n 输入信息码:n);for(i = 1;i = k+r;i+)infori = -1;if(!is_i_2_r(i)scanf(%d,&infori);printf(n);for(i=1;i=r;i+)for(j=1;j=k;j+)groupij=-1; /*初始化各组为-1表示空信息for(i=1;i=k;i+)leni=0; /*初始化各组元素个数为0printf(海明码(偶校验)为:n);for(i=1;i=k+r;i+) /!*从添加检
9、测位后的第1位开始进行分组(关键)a_l=int_to_invdec(a,i); /*将位号转化为逆序的二进制数存入数组a中，返回数组 长度for(g=1;g=r;g+) /共分为 r 组for(j=1;j=a_l;j+)if(aj=1) /*查转化后a中为1的下标位(如为1则分给第1组，为2则分给第二 组等等)if(g=j) /若分组号与下标位相同，in_to_Group(groupg,infori,leng);/*将该信息码添加到第 g 小组中leng+; /*第g小组长度增1break;for(i=1;i=k+r;i+) /* 检测各小组中 1 的个数if(is_i_2_r(i)&count1(groupi_2_r(i)+1,leni_2_r(i)+1)/如果位号为 25 位即检测 位infori=0; /*且该小组中1的个数为偶数，则该检测位上添为0用以校验if(is_i_2_r(i)&!count1(groupi_2_r(i)+1,leni_2_r(i)+1)/如果位号为 25 位即检测 位infori=1; /*且该小组中1的个数为奇数，则该检测位上添为1用以校验for(i = 1;i = k+r;i+)coutvvinfori ; /输出编写好的海明码printf(n)
