计算机网络课程设计报告-海明码实现

湖南涉外经济学院计算机科学与技术学部《计算机网络原理与应用》课程设计报告湖南涉外经济学院计算机网络原理与应用课程设计报告学部：计算机学部专业名称：计算机科学与技术课程名称：计算机网络原理设计题目：海明码的实现学生姓名：余文浩,付庆宇,陈杰指导教师：安莹时间：题目海明码的实现目录一、课程设计目的 31.1海明码的介绍 31.2海明码的应用 31.3算法实现的目的 3二、课程设计题目任务描述和要求 42.1任务描述 42.2要求 4三、设计方案 53.1需求分析 53.2海明码校验原理分析 53.2.1海明码编码的原理分析 53.2.2海明码纠错原理分析 73.3概要设计 73.4详细设计 83.4.3程序流程图 9四、心得体会 11五、参考资料 12(要求：给出一级目录，宋体加粗，四号字,1.5倍行距。)一、课程设计目的（大标题均为四号，黑体） 1.1海明码的介绍 是在电信领域的一种线性调试码，以发明者RichardHamming的名字命名。汉明码在传输的信息流中插入验证码，以侦测并更正单一比特错误。由于简单的汉明编码，它们被广泛应用于内存(RAM)。其SECDED(singleerrorcorrection,doubleerrordetection)版本另外加入一检测比特，可以侦测两个以下同时发生的比特错误，并能够更正单一比特的错误。因此，当传送端与接收端的比特样式的汉明距离(Hammingdistance)小于或等于1时（仅有1bit发生错误），可实现可靠的通信。相对的，简单的奇偶检验码除了不能纠正错误之外，也只能侦测出奇数个的错误。1.2海明码的应用 海明码主要应用于计算机网络中。在数据链路层中，数据的传输很容易出现错误，这时就需要纠错机制来进行纠错，海明码就是一种纠错编码方案。1.3算法实现的目的来实现海明码生成和纠错，可以使我们更加深刻的了解海明校验机制的。二、课程设计题目任务描述和要求2.1任务描述用MicrosoftVisualC++6.0工具，VisualC++MFC编程实现海明码的编码和验证过程。即，输入给定长度的二进制数据，输出相应的完整海明编码形式；同时，输入任意编码能验证其正确性，一位错时，能显示出错的比特，并予以纠正2.2要求 输入任意长度的二进制数据串，通过算法是生成完整的海明码，

三、设计方案3.1需求分析（1）海明码编码：

输入：一串二进制数据串

输出：插入海明码后的二进制数据串（2）海明码纠错：

输入：一串含海明码的二进制数据串

输出：通过海明码校验，检查该二进制串是否有错，若有错误，则对错误位进行纠错，将纠错后的二进制串输出。(3)海明码译码：输入：一串以纠错的二进制数据传输出：源二进制串数据3.2海明码校验原理分析这里我们仅从编程实现的角度分析海明码的编码及纠错的实现算法，书本上采用的是矩阵相乘的方法，但矩阵相乘的方法程序执行效率不高，故通过在网上的搜索及自己的总结，得出如下的程序实现算法。3.2.1海明码编码的原理分析编码步骤

（1）根据信息位数，确定校验位数。

k—信息位数

r—校验位数

求出满足不等式的最小r，即为校验位数。

（2）计算校验位公式

特别注意：

校验位rn所在位数为，其余由信息位填充。

位数和信息位由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一直写到对应的第三位。

校验位rn由前面位数写成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、添入表格

得海明码10101013.2.2海明码纠错原理分析

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

如有已经编码的数据110010010111，则可以根据上表得到编码的信息为：11000011;校验位为：1011。

(2)接收端对校验位进行验证

Sn=rn(校验)+rn(接收)

(3)判断校正因子是否有错，并改正。

SnSn-1Sn-2……S0二进制对应的是那位就是那位出错，将其改正完成纠错。如1001为第九位，将第九位1变0(或0变1)即可。3.3概要设计基于以上原理，我们对软件进行了初步的规划和设计：（1）为了提供友好的用户界面，我们采用VisualC++的MFC框架构建应用程序，使用一个简单的对话框程序，包含两个部分，一部分为海明码编码部分，另一部分为海明码纠错部分。

（2）由于本程序仅仅是海明码原理性的验证性程序，故只设计了对最长8位数据的海明码的编码，以及最长12位的海明码校验。

（3）从上述原理可知，海明码的编码和纠错可以使用如上所述的公式进行，故数据结构只需要采用一个vector容器存放相应的数据即可，不需要其他负责的数据结构。3.4详细设计

3.4.1数据结构的设计

定义五个bool型的容器，vector<bool>，分别代表：输入串寄存器、海明编码寄存器、海明码检错寄存器、海明码检错数据寄存器、海明码检错校验值寄存器

其中：

输入串寄存器：用于存放用户输入的二进制串

海明编码寄存器：存放加入海明码校验码后的二进制串海明码检错寄存器：存放需要纠错的二进制串

海明码检错数据寄存器：存放需要纠错的二进制串的数据部分

海明码检错校验值寄存器：存放需要纠错的二进制串的校验码部分

3.4.2模块划分

模块功能概述：

（1）海明码编码

输入模块：获取用户的输入二进制串，并判断输入的正确性

寄存器初始化模块：将用户的输入字符串转化成0、1形式的数字串存放到输入串寄存器中，并且将数据依次存放到海明编码寄存器，存放时将2的幂次的位置空出来（置0）作为存放校验码。

校验码计算模块：根据上面描述的编码算法对校验码的值进行计算并存储在对应的位置。

显示模块：将海明编码寄存器中的二进制串转化成字符串的形式以供输出。

（2）海明码纠错

输入模块：获取用户的输入二进制串，并判断输入的正确性

寄存器初始化模块：将用户的输入字符串转化成0、1形式的数字串存放到检错寄存器中，根据当前位置是否为2的幂次将二进制串分为数据和校验码分别存放到检错数据寄存器和检错校验值寄存器

海明码纠错模块：根据上面描述的纠错算法对数据进行校验，并纠错。

显示模块：将检错寄存器中正确的二进制码转化成字符串的形式以供输出。3.4.3程序流程图四、心得体会通过对这次课程设计让我对计算机的组成原理有了更深层次的理解，把平时学习中学到的知识运用了到其中。同时也加深了我对平时学习中所没有接触过的知识的一个了解。从而提升了自己各方面的能力,特别是对数据在内存单元以及寄存器中的存储原理和操作数走向问题。并且让我对海明码有了认识和了解，能够更加熟练的运用海明码。再次明白到各个学科紧密相关，组成原理与微机原理知识的相互应用，硬件与编程之间密切联系，程序最终依靠硬件实现，并依靠硬件编程，硬件为其提供一个平台，二者缺一不可，通过这样的学习加深理解，提供综合能力。本次设计是使用C++语言做的，通过这次课程设计，也加深了我对C++的理解和熟练程度。最后，通过这次课程设计，不仅增长了我的知识，同时也锻炼了我的动手能力，和解决问题的能力。……（正文部分一律用小四号字，宋体，1.