海明码校验程序设计

（1）海明码编码：
输入：一串二进制数据串
输出：插入海明码后的二进制数据串

（2）海明码纠错：
输入：一串含海明码的二进制数据串
输出：通过海明码校验，检查该二进制串是否有错，若有错误，则对错误位进行纠错，将纠错后的二进制串输出。

 

         这里我们仅从编程实现的角度分析海明码的编码及纠错的实现算法，书本上采用的是矩阵相乘的方法，但矩阵相乘的方法程序执行效率不高，故通过在网上的搜索及自己的总结，得出如下的程序实现算法。

 

2.1 海明码编码的原理分析

编码步骤
（1） 根据信息位数，确定校验位数。 
k—信息位数
r—校验位数
求出满足不等式的最小r，即为校验位数。
（2）计算校验位公式
 
特别注意：
校验位 r n所在位数为  2^n ，其余由信息位填充。
位数和信息位由1起始，而校验位由0起始。
将每个信息比特由位置对应的位数写成2的幂之和的形式。
例如I8对应的第十二位12=2^3+2^2 ，I7对应的第十一位11=2^3+2^1+2^0 ，I6对应的第十位10=2^3+2^1，I5对应的第九位9=2^3+2^0  一直写到对应的第三位。
校验位r n由前面位数写成2的幂之和中包含2 ^n的位数对应的信息为之和构成
例如r3=I8+I7+I6+I5
（3）求校验位。
根据计算公式求出各校验位。
（4） 求海明码
根据上面的表格填充后，写出海明码。
例 对一段信息1011，写出海明码。
根据上面步骤，解答如下
1、 2^r≥4+r+1,确定校验位位3位2^3≥4+3+1.
2、 根据步骤
 
7=2^2+2^1+2^0, 6=2^2+2^1, 5=2^2+2^0,3=2^1+2^0,
r2=I4+I3+I2
r1=I4+I3+I1
r0=I4+I2+I1
3、 根据公式的r2 = 0, r1 =0, r0 =1 
4、 添入表格   
 
得海明码1010101

2.2 海明码纠错原理分析
(1)根据海明码的信息位和校验位的分布规则，找出接收到的数据的信息位以及校验位。
　　

如有已经编码的数据 1100 1001 0111，则可以根据上表得到编码的信息为：1100 0011;校验位为：1011。 
(2)接收端对校验位进行验证
Sn= rn ( 校验)+ rn (接收)
(3)判断校正因子是否有错，并改正。
Sn Sn-1 Sn-2……S0二进制对应的是那位就是那位出错，将其改正完成纠错。如1001为第九位，将第九位1变0 (或0变1) 即可。

 

基于以上原理，我们对软件进行了初步的规划和设计：

（1） 为了提供友好的用户界面，我们采用Visual C++的MFC框架构建应用程序，使用一个简单的对话框程序，包含两个部分，一部分为海明码编码部分，另一部分为海明码纠错部分。
（2） 由于本程序仅仅是海明码原理性的验证性程序，故只设计了对最长8位数据的海明码的编码，以及最长12位的海明码校验。
（3） 从上述原理可知，海明码的编码和纠错可以使用如上所述的公式进行，故数据结构只需要采用一个vector容器存放相应的数据即可，不需要其他负责的数据结构。

 

4.1 数据结构的设计
定义五个bool型的容器，vector<bool>，分别代表：输入串寄存器、海明编码寄存器、海明码检错寄存器、海明码检错数据寄存器、海明码检错校验值寄存器
其中：
输入串寄存器：用于存放用户输入的二进制串
海明编码寄存器：存放加入海明码校验码后的二进制串

海明码检错寄存器：存放需要纠错的二进制串
海明码检错数据寄存器：存放需要纠错的二进制串的数据部分
海明码检错校验值寄存器：存放需要纠错的二进制串的校验码部分
4.2 模块划分
 
模块功能概述：
（1）海明码编码
输入模块：获取用户的输入二进制串，并判断输入的正确性
寄存器初始化模块：将用户的输入字符串转化成0、1形式的数字串存放到输入串寄存器中，并且将数据依次存放到海明编码寄存器，存放时将2的幂次的位置空出来（置0）作为存放校验码。
校验码计算模块：根据上面描述的编码算法对校验码的值进行计算并存储在对应的位置。 
显示模块：将海明编码寄存器中的二进制串转化成字符串的形式以供输出。
（2）海明码纠错
输入模块：获取用户的输入二进制串，并判断输入的正确性
寄存器初始化模块：将用户的输入字符串转化成0、1形式的数字串存放到检错寄存器中，根据当前位置是否为2的幂次将二进制串分为数据和校验码分别存放到检错数据寄存器和检错校验值寄存器
海明码纠错模块：根据上面描述的纠错算法对数据进行校验，并纠错。
显示模块：将检错寄存器中正确的二进制码转化成字符串的形式以供输出。

 

4.3 程序流程图

 

 

本文转自 Jhuster 51CTO博客，原文链接：http://blog.51cto.com/ticktick/167482，如需转载请自行联系原作者