汉明码编译码软件设计

./*******************实践教学*******************XX理工大学计算机与通信学院2012年秋季学期计算机通信课程设计题目：〔7,4汉明码编译码软件设计专业班级：姓名：学号：指导教师：成绩：摘要汉明码是一种能自动检错并纠正一位错码的线性纠错码,用于信道编码与译码中,高通信系统抗干扰的能力。本次课设主要是〔7,4汉明码的编译码软件设计,该软件可以对输入的多个四位信息码进行编码,对于接收的多个七位信息码可以进行译码,从而译出四位信息位.当接收到的信息码有一位错误时,可以纠正这一位错码,进而译出正确的信息码组,整个程序使用C语言编写.关键词：汉明码、编码、译码、检错、纠错.目录一、C语言简介11.1什么是C语言11.2C语言的特点11.3运行C程序的步骤与方法2二、汉明码编码42.1汉明码编码原理42.2监督矩阵62.3生成矩阵7三、汉明码纠错检错93.1汉明距离93.2汉明码纠错原理9四、汉明码编译码的实现过程104.1编码过程104.2译码过程10五、软件设计及测试分析125.1程序流程图125.1.2编码程序流程图125.1.3译码程序流程图135.2软件运行分析15主程序运行分析155.2.2编码运行分析175.2.3译码运行分析185.3软件分析19总结20参考文献21附录22.一、C语言简介1.1什么是C语言C语言是一种计算机程序设计语言。它既具有高级语言的特点,又具有汇编语言的特点。它由美国贝尔研究所的D.M.Ritchie于1972年推出。1978后,C语言已先后被移植到大、中、小及微型机上。它可以作为工作系统设计语言,编写系统应用程序,也可以作为应用程序设计语言,编写不依赖计算机硬件的应用程序。它的应用范围广泛,具备很强的数据处理能力,不仅仅是在软件开发上,而且各类科研都需要用到C语言,适于编写系统软件,三维,二维图形和动画。具体应用比如单片机以及嵌入式系统开发。1.2C语言的特点一种语言之所以能存在和发展,并具有较强的生命力,总是有不同于其他语言的特点。主要的优缺点介绍如下。优点简洁紧凑、灵活方便。C语言一共只有32个关键字,9种控制语句,程序书写形式自由,区分大小写。把高级语言的基本结构和语句与低级语言的实用性结合起来。C语言可以像汇编语言一样对位、字节和地址进行操作,而这三者是计算机最基本的工作单元。运算符丰富。C语言的运算符包含的范围很广泛,共有34种运算符。C语言把括号、赋值。强制类型转换等都作为运算符处理。从而使C语言的运算类型极其丰富,表达式类型多样化。灵活使用各种运算符可以实现在其它高级语言中难以实现的运算。数据类型丰富。C语言的数据类型有：整型、实型、字符型、数组类型、指针类型、结构体类型、共用体类型等。能用来实现各种复杂的数据结构运算。并引入了指针概念,使程序效率更高。另外C语言具有强大的图形功能,支持多种显示器和驱动器。且计算功能、逻辑判断功能强大。C是结构式语言。结构式语言的显著特点是代码及数据的分隔化,即程序的各个部分除了必要的信息交流外彼此独立。这种结构化方式可使程序层次清晰,便于使用、维护以及调试。C语言是以函数形式提供给用户的,这些函数可方便的调用,并具有多种循环、条件语句控制程序流向,从而使程序完全结构化。语法限制不太严格,程序设计自由度大。虽然C语言也是强类型语言,但它的语法比较灵活,允许程序编写者有较大的自由度。允许直接访问物理地址,对硬件进行操作。由于C语言允许直接访问物理地址,可以直接对硬件进行操作,因此它既具有高级语言的功能,又具有低级语言的许多功能,能够像汇编语言一样对位、字节和地址进行操作,而这三者是计算机最基本的工作单元,可用来写系统软件。生成目标代码质量高,程序执行效率高。一般只比汇编程序生成的目标代码效率低10へ20%。适用范围大,可移植性好。C语言有一个突出的优点就是适合于多种操作系统,如DOS、UNIX、windows98．windowsNT；也适用于多种机型。C语言具有强大的绘图能力,可移植性好,并具备很强的数据处理能力,因此适于编写系统软件,三维,二维图形和动画,它也是数值计算的高级语言。缺点C语言的缺点主要表现在数据的封装性上,这一点使得C在数据的安全性上有很大缺陷,这也是C和C++的一大区别。C语言的语法限制不太严格,对变量的类型约束不严格,影响程序的安全性,对数组下标越界不作检查等。从应用的角度,C语言比其他高级语言较难掌握。1.3运行C程序的步骤与方法为了使计算机能按照人的意志进行工作,必须根据问题的要求,编写出相应的程序。为了使计算机能执行高级语言源程序,必须先用一种称为"编译程序"的软件,把源程序翻译成二进制形式的"目标程序",然后再将该目标程序与系统的函数库以及其他目标程序连接起来,形成可执行的目标程序。在编好一个C源程序后如何上机运行呢？在纸上写好一个程序后,要经过这样几个步骤：上机输入与编辑源程序对源程序进行编译与库函数连接运行目标程序。以上过程如图2所示。图中实线表示操作流程,虚线表示文件的输入输出。例如,编辑后得到源程序文件f.c,然后在进行编译时再将源程序文件f.c输入,经过编译得到目标程序文件f.obj,再将目标程序f.obj输入内存,与系统提供的库函数等连接,得到可执行的目标程序f.exe,最后把f.exe调入内存再使之运行。图1C语言运行流程图二、汉明码编码2.1汉明码编码原理Hamming码中文称作汉明码。汉明码是由汉明于1950年提出的,具有纠正一位错误能力的线性分组码它的突出特点是：编译码电路简单,易于硬件实现；用软件实现编译码算法时,软件效率高；而且性能比较好.一般来说,若汉明码长为n,信息位数为k,则监督位数r=n-k。若希望用r个监督位构造出r个监督关系式来指示一位错码的n种可能位置,则要求或〔1下面以〔7,4汉明码为例说明原理：设汉明码〔n,k中k=4,为了纠正一位错码,由式〔1可知,要求监督位数r≥3。若取r=3,则n=k+r=7。我们用来表示这7个码元,用的值表示3个监督关系式中的校正子,则的值与错误码元位置的对应关系可以规定如表1所列。表1校正子和错码位置的关系错码位置错码位置001101010110100111011000无错码则由表1可得监督关系式：<2><3><4>在发送端编码时,信息位的值决定于输入信号,因此它们是随机的。监督位、、应根据信息位的取值按监督关系来确定,即监督位应使式〔2-式〔4中、、的值6为0〔表示编成的码组中应无错码〔5式〔5经过移项运算,接触监督位〔6由上面方程可得到表2所示的16个许用码组。在接收端收到每个码组后,计算出、、,如果不全为0,则表示存在错误,可以由表1确定错误位置并予以纠正。举个例子,假设收到码组为0000011,可算出,由表1可知在上有一误码。通过观察可以看出,上述〔7,4码的最小码距为,纠正一个误码或检测两个误码。如果超出纠错能力则反而会因"乱纠"出现新的误码.表2〔7,4汉明码的许用码组信息位监督位信息位监督位0000000100100011010001010110011100001110111011010101100010001001101010111100110111101111111100010001001010100111式〔5其等价形式为：〔7式〔6还可以简记为或〔8其中所以有〔9式〔6等价于〔10其中Q为P的转置,即〔11式〔10表示,信息位给定后,用信息位的行矩阵乘矩阵Q就产生出监督位。我们将Q的左边加上一个k×k阶单位方阵,就构成一个矩阵G〔12G称为生成矩阵,因为由它可以产生整个码组,即有〔13或者〔14式<13>即汉明码的编码原理2.2监督矩阵上面有提到过,线性码是指信息位和监督位满足一组线性代数方程的码:〔15我们可以将式〔15表示成如下的矩阵形式〔16式〔16还可以简记为或,其中,上角"T"表示将矩阵转置。例如HT是H的转置,即的第一行为H的第一列,第二行为第二列。我们将H称为监督矩阵<parity—checkmatrix>.只要监督矩阵H给定,编码时监督位和信息位的关系就完全确定了。由〔15和<16>都可以看出,H的行数就是监督关系式的数目r,H的每一行中的"1”〔17式中：P为阶矩阵；Ir为阶单位方阵。2.3生成矩阵由代数理论可知,H矩阵的的各行应该是线性无关的,否则将得不到r个线性无关的监督关系式,从而也得不到r个独立的监督位。若一矩阵可以写成的矩阵形式,则其各行一定是线性无关的。因为容易验证Ir的各行是线性无关的,故的各行也是线性无关的。类似于式〔5改成式〔16那样,式〔6可以改写成〔18或者〔19其中,Q为一个阶矩阵,它为P的转置,即〔20式〔19表示,在信息位给定后,用信息位的行矩阵乘矩阵Q就产生出监督位。我们将Q的左边加上一个阶单位方阵,就构成一个矩阵G〔21G称为生成矩阵〔generatormatrix,因为由它可产生整个码组,即有〔22因此,如果找到了码的生成矩阵G,则编码的方法就完全确定。具有形式的生成矩阵称为典型生成矩阵。由典型生成矩阵得出的码组A中,信息位不变,监督位附加于其后,这种码称为系统码。与H矩阵相似,也要求G矩阵的各行是线性无关的。因为由式〔22可以看出,任一码组A都是G的各行的线性组合。G共有K行,若它们线性无关,则可组合出种不同的码组A,它恰是有k为信息位的全部码组；若G的各行有线性相关的,则不可能由G生成种不同码组了。实际上,G的各行本身就是一个码组。因此,如果已有k个线性无关的码组,则可以用其作为生成矩阵G,并由它生成其余的码组。三、汉明码纠错检错3.1汉明距离两个码字之间,对应位取之不同的个数,称为汉明距离,用表示。一个码的最小距离定义为,两个码字之间的距离表示了它们之间差别的大小。3.2汉明码纠错原理一般来说接收码组与A不一定相同。若设接收码组为一n列的行矩阵B,即〔23则发送码组和接收码组之差为〔24E就是传输中产生的错码行矩阵〔25若,表示接收码元无错误,若,则表示该接收码元有错。式〔24可改写成〔26若E=0,即接收码组无错,则,将它代人式〔8,该是仍成立,即有〔27当接收码组有错时,,将B带入式〔26后,该式不一定成立。在未超过检错能力时,式〔27不成立。假设此时式〔26的右端为S,即〔28将代入式〔28,可得由式〔8可知,所以<29此处S与前面的有着一一对应关系,则S能代表错码位置。因此,纠错原理即,接收端收到码组后按式〔28计算出S,再根据表1判断错码情况,进行差错纠正。四、汉明码编译码的实现过程4.1编码过程由与的分块表示的矩阵形式<31>〔32〔33〔34则有或〔35已知生成矩阵:根据以上几式可求出监督矩阵:〔36最后可以根据输入的四位信息位和生成矩阵相乘得到编码矩阵。即〔37所有的编码情况如表1所示。4.2译码过程对于译码过程来说,同样由上知道监督矩阵H：根据监督矩阵,将矩阵的行和列调换,可求出监督矩阵的转置矩阵:再根据式〔28即求出伴随式,由伴随式式可以知道错码的位置及及纠正错码,具体的错码位置如表1所示。纠正了接收码后可以提取出其中的四位信息位.五、软件设计及测试分析5.1程序流程图主程序流程图主程序一开始就有欢迎界面,并对该编译器做了简单的介绍,同时为方便用户使用,对用户的操作也进行了补充说明,接着给用户显示出了选择提示语句,可以选择编码器、译码器、退出。当用户做出选择后便会进入各自的子程序,执行相应的功能,如果用户输入错误,还会给出错误提示。主程序的流程图如图3所示。图2主程序流程图编码程序流程图在程序进入编码子程序时,它首先提示用户输入需要编码的码组个数,根据用户选择的个数接着要求用户输入编码的信息码组,信息码组与生成矩阵相乘便会得到相应的编码,其流程图如图4所示图3编码程序流程图译码程序流程图对于译码程序,因为信息在传输过程中会遇到噪声干扰,所以接收码组会出现错码、丢码或多码现象。又因为很难判断丢码或多码的具体位置,所以这两种情况处理起来比较复杂,在这暂不进行译码,只做出判断。对于错码,可以纠正一位错误,发现两位错误。在译码的过程中,要用到监督矩阵的转置矩阵,所以先求生成矩阵对应的监督矩阵,再进行转置,然后提示输入接收码组,输入的接收码组中有可能丢失码位,故而先判断,再进行纠检错,输出正确的码组,最后提取出正确的信息组。其流程图如图5所示。图4译码程序流程图5.2软件运行分析主程序运行分析图5主界面运行图从程序一开始就运行主界面,主界面有对该软件的简单介绍,接着就给出了选择功能。用户输入不同的序号可以执行不同的功能,主界面仿真结果如图5所示。输入"1"后按回车键执行编码功能,如图6所示；输入"2"后按回车键执行译码功能,如图7所示；输入"3"后按回车键执行退出如图8所示；输入其它系统会显示错误提示信息,如图9所示。图6选择编码功能图7选择译码功能图8执行退出功能图9输入错误时错误提示编码运行分析10和图11所示。图10输入信息组数后系统界面图11编码后的系统界面由运行的界面可知,软件还可以持续操作,当用户再做出选择,可以执行相应的功能,整个体系就是按照这个思想联系在一起的。译码运行分析2所示；如果接收码组没有丢码,系统可以纠正一位错码,发现两位错码,例如输入上面编码后的4个接收码组,并故意输错第二个码组的位和第四个码组的位和3所示。为了体现软件的持续操作,我们从编码结束后再选择译码。图12输入有丢码的接收码组时系统运行界面图13译码运行界面5.3软件分析根据软件运行情况分析来看,该软件最终实现的功能有：〔1对数量不等的信息组编码；〔2对数量不等的接收码组纠正一位错误,发现两位错误；〔3对输入的接收码组判断是否有丢码；〔4循环使用编码器和译码器；〔5对操作失误做出提示。与最初的设计目标相比,该软件的不足方面有：〔1使用编码器的时候,如果输入有误,系统没有给出明确提示；〔2当接收码组中有丢失位时,不能译码；〔3显示界面不够人性化。总之,软件在可靠性方面已做出验证,达到了要求。C语言比起其它语言要难学,更稳定,C程序的稳定性就证明了该软件具有很好的稳定性。实用性方面,由于该软件只对四位信息组编码,编码后有七位；对七位接收码组译码,提取信息位后是四位。其它码并不适应该软件,所以它的适用范围受到了限制。总结通过这次为期两周的计算机通信课程设计,我的题目是〔7,4汉明码的编译码软件设计。汉明码是差错控制编码的重要一种。汉明码的编码与译码纠错能力较强,是实际应用中比较流行的差错控制编码方法之一。虽然课设刚开始我就要去实习,但是每天晚上回到宿舍我就开始做课设,因从我很及时的完成了课设,在这期间我查阅了许多的书籍以及网上的资料,通过这次课设,巩固了以前所学过的知识,而且学到了很多在书本上所没有学到过的知识。通过这次课程设计使我懂得了理论与实际相结合的必要性,只有理论知识是远远不够的,只有把所学的理论知识与实践相结合起来,从理论中得出结论,才能真正为社会服务,从而提高自己的实际动手能力和独立思考的能力。在设计中也得到很多见识,获得或理解知识时的欣喜与在一个问题上的纠结都是很宝贵的,在这种情绪的反复中,认识到学习就是这样一个过程。不管过程怎样,以小见大的反射出以后学习的态度。互相交流可以加深学习,找出问题,相互弥补不足,在资料的采集方面提高了不少效率,也提高的每个个体的兴奋度,真切体会集体学习给我们带来的益处,学习是快乐的。这次课程设计带给我的不仅仅是学识上的精进还有个人能力素养的提升,也督促培养了个人独立思考、善于查阅并应用相关资料书籍的能力。经过这次课程设计,我收获很多。我会在以后的学习生活中继续保持这种求真务实的精神,努力学好理论知识,更好的为实践服务。参考文献[1]潘新民编·计算机通信技术·电子工业出版社·2003,7[2]吴玲达、李国辉、杨冰等编·计算机通信原理与技术·国防科技大学出版社·2003,3[3]曹志刚、钱压生编·现代通信原理·清华大学出版社·1992,2[4]樊昌兴、通信原理[1]孙丽华编·信息论与纠错编码·电子工业出版社·2005,3编·国防工业出版社·1999,10[5]唐朝京著·信息论与编码基础·国防科技大学出版社·2003,1[6]宋祖顺著·现代通信原理[M]·电子工业出版·2001,2[7]傅祖芸著·信息论--基础理论与应用[M]·电子工业出版社·2002[8]谭浩强著·C程序设计〔第二版·清华大学出版社·1999,12[9]王连相著·C/C++程序设计教程·中国铁道出版社·2006,8附录〔7,4码编译器整体程序：#include<stdio.h>#include<math.h>intmain<> { /*G：生成矩阵H：监督矩阵HT：监督矩阵对应的转置矩阵*/ /*M：输入信息序列C：编码输出序列Input：输入接收码序列B：译码输出序列S：伴随式*/ intQ,N;/*定义开始*/ inti,j,s,r,k,t,p,u,m;intG[4][7]={{1,0,0,0,1,1,1},{0,1,0,0,1,1,0},{0,0,1,0,1,0,1},{0,0,0,1,0,1,1}}; intIR[3][3]={{1,0,0,},{0,1,0},{0,0,1}}; intH[3][7],C[10][7],M[10][4],B[20][7],Input[100],HT[7][3],P[10],S[100][3];/*定义结束*/ printf<"\n您好！欢迎使用汉明码编译器！\n">; printf<"\n\n本编译器针对〔7,4码,所采用的生成矩阵G=\n">; for<i=0;i<4;i++> { for<j=0;j<7;j++> printf<"%d",G[i][j]>; printf<"\n">; } printf<"编译码过程都是针对二进制码组,除了系统要求选择功能,其他情况下禁止输入除0,1以外的数。请在使用的过程中严格按照编译器要求的格式输入数据。\n\n">; printf<"现在请输入您所选择的编译器所对应的序号,按回车键继续:\n">; printf<"\n1.编码器2.译码器3.退出\n">; printf<"\n我选择：">; scanf<"%d",&Q>; if<Q==0> Q+=4; while<Q> { if<Q==1||Q==2||Q==3>break; else { printf<"对不起,您输入有误,请重新输入">; scanf<"%d",&Q>; } } while<Q==1||Q==2||Q==3> { if<Q==1>/*编码程序*/ {printf<"\n请输入您需要编码的信息组数">; scanf<"%d",&N>; printf<"\n\n请输入您需要编码的%d组四位二进制信息组,码组间用空格分开,按回车键确认。\n",N>;/*输入信息码*/ printf<"\n信息组m=">; for<i=0;i<N;i++> scanf<"%1d%1d%1d%1d",&M[i][3],&M[i][2],&M[i][1],&M[i][0]>;/*求监督码*/ for<i=0;i<N;i++> { C[i][2]=M[i][3]^M[i][2]^M[i][1]; C[i][1]=M[i][3]^M[i][2]^M[i][0]; C[i][0]=M[i][3]^M[i][1]^M[i][0]; } for<j=0;j<N;j++> for<i=6;i>2;i-->/*输出编码结果*/ C[j][i]=M[j][i-3]; printf<"\n您所输入的信息组编码结果c=">; for<j=0;j<N;j++> for<i=6;i>=0;i--> printf<"%d",C[j][i]>; printf<"\n\n">; printf<"\n接下来您想：\n\n">;/*选择功能*/ printf<"1.用编码器2.用译码器3.退出\n\n">; printf<"我想：">; scanf<"%d",&Q>; } elseif<Q==2>/*译码程序*/ { for<i=0;i<3;i++>/*求监督矩阵*/ { for<j=0;j<4;j++> H[i][j]=G[j][i+4]; for<j=4;j<7;j++> H[i][j]=IR[i][j-4]; } printf<"\n监督矩阵H=\n">;/*输出监督矩阵*/ for<i=0;i<3;i++> { for<j=0;j<7;j++> printf<"%d",H[i][j]>; printf<"\n">; } t=1; while<t!=2>/*输入接收码组*/ { p=1; printf<"\n请输入总位数为7的倍数的接收码组,每位用空格隔开,每组位数为7的倍数,以十进制2作为结束标志!按回车键确认\n">; while<p> { for<i=0;;i++> { scanf<"%d",&Input[i]>; if<Input[i]==2>break; } k=i%7; if<k==0>{p=0;t=2;} else { p=1; k=-k+7; printf<"您接收到的码组丢失了%d位,系统不能判断丢失位的具体位置,请重新输入\n",k>; } } } u=i/7; i=0; for<r=0;r<u;r++> { for<j=6;j>=0;j--,i++> B[r][j]=Input[i]; } printf<"\n将接收码组每七位分为一个码组,如下：\n">; for<i=0;i<u;i++> { for<j=0;j<7;j++> printf<"%1d",B[i][6-j]>; printf<"\n">; } for<i=0;i<3;i++>/*求监督矩阵H的转置矩阵*/ for<j=0;j<7;j++> HT[j][i]=H[i][j]; for<i=0;i<u;i++> { for<m=0;m<3;m++> { for<j=0;j<7;j++> { s+=<B[i][6-j]*HT[j][m]>; } if<s%2==1>s=1; else s=0; S[i][2-m]=s; s=0; } } printf<"\n\n伴随式S=\n">;/*输出伴随式*/ for<j=0;j<u;j++> {for<i=2;i>=0;i--> printf<"%1d",S[j][i]>; printf<"\n">;} printf<"\n">; for<i=0;i<u;i++> { P[i]=4*S[i][2]+2*S[i][1]+S[i][0]+1; switch<P[i]>/*根据伴随式判断接收码,并译码*/ { case1: { printf<"\n\n您所接收的第%d个码组正确,它是：",++i>; i--; for<j=6;j>=0;j--> printf<"%1d",B[i][j]>; printf<"请您再次确认！">; printf<"译出的信息序列为：">; for<j=6;j>2;j--> printf<"%d",B[i][j]>;break; } case2: { B[i][0]=1^B[i][0]; printf<"\n\n您接收的第%d个码组有错误,正确的码组应为：",++i>; i--; for<j=6;j>=0;j--> printf<"%1d",B[i][j]>; printf<"译出的信息序列为：">; for<j=6;j>2;j--> printf<"%d",B[i][j]>;break; } case3: { B[i][1]=1^B[i][1]; printf<"\n\n您接收的第%d个码组有错误,正确的码组应为：",++i>; i--; for<j=6;j>=0;j--> printf<"%1d",B[i][j]>; printf<"译出的信息序列为：">; for<j=6;j>2;j--> printf<"%d",B[i][j]>;break; } case4: { B[i][3]=1^B[i][3]; printf<"\n\n您接收的第%d个码组有错误,正确的码组应为：",++i>; i--; for<j=6;j>=0;j--> printf<"%1d",B[i][j]>; printf<"译出的信息序列为：">; for<j=6;j>2;j--> printf<"%d",B[i][j]>;break; } case5: { B[i][2]=1^B[i][2]; printf<"\n\n您接收的第%d个码组有错误,正确的