Hamming汉明码课程设计教学提纲.doc

Good is good, but better carries it.精益求精，善益求善。Hamming汉明码课程设计-目录第一章数字通信中的编码原理41.1数字通信系统的组成41.2编码信道模型51.3信道编码概述7第二章线性分组码92.1线性分组码的基本概念92.2线性码的编码和译码102.2.1线性码的编码102.2.2线性码的译码112.3Hamming（汉明）码12第三章Hamming码的编程实现143.1VC+6.0开发环境143.2Hamming码编译码器的设计153.3编译结果17摘要在通信系统中，要提高信息传输的有效性，我们将信源的输出经过信源编码用较少的符号来表达信源消息，这些符号的冗余度很小，效率很高，但对噪声干扰的抵抗能力很弱。为了提高信息传输的准确性，我们引进了差错控制技术。而该技术采用可靠的，有效的信道编码方法来实现的。纠错码是一种差错控制技术，目前已广泛应用于各种通信系统和计算机系统中，纠错编码主要用于数字系统的差错控制，对于保证通信、存储、媒体播放和信息转移等数字传递过程的质量有着重要意义，是通信、信息类科知识结构中不可缺少的一部分。本文系统地介绍了纠错码在数字系统中的应用和发展，以及纠错码的基本原理和含义,常用纠错码的简介和分类,同时也介绍了Vc+6.0的基本知识，以及如何应用Vc+实现hamming码编码器和译码器。关键字：通信系统、信道编码、线性分组码、Hamming码AbstractInthecommunicationssystem,toenhancetheeffectivenessofinformationtransmission,wewillsourcetheoutputaftersourcecodingwithfewersymbolstoexpressthesourceofthenewsletter,theredundancyofthesesymbolsisverysmall,veryefficient,butthenoiseweakresistancetointerference.Inordertoimprovetheaccuracyofinformationtransmission,weintroduceerrorcontroltechniques.Thetechnologyusesareliableandeffectivemethodofchannelcodingtoachieve.Error-correctingcodeisanerrorcontroltechniqueshavebeenwidelyusedinvariouscommunicationssystemsandcomputersystems,mainlyusedforerror-correctingcodingerrorsindigitalcontrolsystems,toensurecommunication,storage,mediaplayersanddigitaltransmissionofinformationtransferthequalityoftheprocessofgreatsignificance,isthecommunications,information-typeknowledgestructureofsubjectsanindispensablepart.Thisarticleintroducesasystematicerror-correctingcodesindigitalsystemsintheuseanddevelopment,aswellasthebasicprinciplesoferror-correctingcodesandmeaningofcommonlyusederror-correctingcodesandclassifiedbriefings,aswellasVc+6.0,introducedthebasicknowledge,andhowVc+toachievetheapplicationofhammingcodeencoderanddecoder.Keywords:communicationsystem,channelcoding,linearblockcodes,Hammingcode第一章数字通信中的编码原理1.1数字通信系统的组成通信系统是传递信息所需的一切技术设备的总和，包括信息源、发送设备、传输介质、信息接收者和接收设备。数字通信系统传输的数据是数字化了的信息。简化的系统模型，如图1所示。信源MCRM信宿纠错码译码器信道纠错码编码器干扰图1简化的通信系统模型信息源中，模拟信息源（如模拟式电话机、电视摄像机）输出的是幅度连续变化的信号，离散信息源（如计算机）输出的是离散的符号序列或文字。通过采样和量化可以将模拟信息变换为离散信息。发送设备的基本功能是使不同种类和速率的信息源与传输媒介相匹配，通常是将信息源产生的信息经过编码，并变换为便于传送的信号形式，送往传输介质。编码包括信源编码与信道编码两部分。信源编码把连续消息变换为数字信号，信道编码则使数字信号与传输介质匹配，提高传输的可靠性和有效性。调制是多种变换方式中最常见的一种。发送设备还包括为达到某些特殊要求所进行的各种处理，如多路复用、保密处理、纠错编码处理等。传输介质是发送设备到接收设备之间信号传递所经过的媒介。例如：电磁波、红外线等无线传输介质，各种电缆、光缆、双绞线等有线传输介质。传输过程中必然会引入热噪声、衰减、脉冲等干扰。介质的固有特性和干扰特性直接关系到编码方式的选取。接收设备的基本功能是完成对发送的反变换（解调、译码、解密等），从带有干扰的信号中恢复出正确的原始信息；对于多路复用信号还包括解除多路复用和实现正确分路（或称输出扫描）。双向通信要求通信双方都有发送设备和接收设备，如果两个方向共用一个传输媒介，则必须采用分频或分时的办法。信息的传输系统和交换系统组成完整的通信系统，直至构成复杂的通信网络。1.2编码信道模型1、调制信道的模型在通信中，我们所关心的是已调信号经过信道后的结果，而不关心调制信道包括了什么样的转换器，也不管选用了什么样的传输媒质，以及发生了怎样的传输过程。也就是说，只关心调制信道的输入与输出。因此，可以用一个二端对网络表示调制信道。这个二端对网络包括了发，收转换器及传输媒质，然而，它具有什么性质呢？应注意，它相当于一个线性时变网络，如图2所示。时变线性网络图2调制信道模型其输入与输出的关系：式中：n(t)是信道内噪声，加性干扰。k(t)是乘性干扰(与ei(t)呈现非线性关系)。也可用多端对网络表示调制信道，如图3所示。图3调制信道模型恒参信道的定义：如果k(t)不随时间t变化或基本不变化,则称恒参信道;随参信道的定义：如果k(t)是随机快变化的,则称信道为随参信道。二、编码信道的模型由于编码信道传输的是编码后的数字信号，所以我们关心的是数字信号经信道传输后的差错情况，即误码特性，所以编码信道的模型用数字转移概率来表示。1.无记忆信道:(信道内只存在起伏噪声)特点：任意一个码元的差错与前后码元的差错不发生任何依赖关系。对于二进制码，模型如图4所示。图4二进制编码信道模型当P(1/0)P(0/1)1/2时，信道称为二元对称信道(BSC)。2.有记忆信道:(信道内除起伏噪声外,还存在衰落效应等)。特点：信号的传输与前后码元有依赖关系,需用马尔科夫链描述。1.3信道编码概述数字信号在传输中往往由于各种原因，使得在传送的数据流中产生误码，从而使接收端产生图象跳跃、不连续、出现马赛克等现象。所以通过信道编码这一环节，对数码流进行相应的处理，使系统具有一定的纠错能力和抗干扰能力，可极大地避免码流传送中误码的发生。误码的处理技术有纠错、交织、线性内插等。信道编码理论是指通过信道编码器和译码器实现的用于提高信道可靠性的理论和方法，是信息论的内容之一。提高数据传输效率，降低误码率是信道编码的任务。信道编码的本质是增加通信的可靠性。但信道编码会使有用的信息数据传输减少，信道编码的过程是在源数据码流中加插一些码元，从而达到在接收端进行判错和纠错的目的，这就是我们常常说的开销。这就好象我们运送一批玻璃杯一样，为了保证运送途中不出现打烂玻璃杯的情况，我们通常都用一些泡沫或海棉等物将玻璃杯包装起来，这种包装使玻璃杯所占的容积变大，原来一部车能装5000各玻璃杯的，包装后就只能装4000个了，显然包装的代价使运送玻璃杯的有效个数减少了。同样，在带宽固定的信道中，总的传送码率也是固定的，由于信道编码增加了数据量，其结果只能是以降低传送有用信息码率为代价了。将有用比特数除以总比特数就等于编码效率了，不同的编码方式，其编码效率有所不同。例如，数字电视中常用的纠错编码，通常采用两次附加纠错码的前向纠错（FEC）编码。前向纠错码（FEC）的码字是具有一定纠错能力的码型，它在接收端解码后，不仅可以发现错误，而且能够判断错误码元所在的位置，并自动纠错。这种纠错码信息不需要储存，不需要反馈，实时性好。所以在广播系统（单向传输系统）都采用这种信道编码方式。信道编码大致分为两类：信道编码定理，从理论上解决理想编码器、译码器的存在性问题，也就是解决信道能传送的最大信息率的可能性和超过这个最大值时的传输问题。构造性的编码方法以及这些方法能达到的性能界限。一方面，无线信道的恶劣性使接受信号展现出非常差的错误率，迫使译码器在非常低的信噪比下工作。另一方面，“频带”是无线通信系统宝贵而紧张的资源，尤其是在用户密集的闹市区和室内通信系统中。为此，对编译码器的设计提出了很高的要求，驱使译码要充分用到所以已知的信号特点；而且，会占用带宽信息的“冗余”必须谨慎使用。与此同时，集成电路技术的快速发展也使得信道编译码器四要素，即系统性能、宽带资源、传输约束条件和实现复杂度可以再更高层次上获得平衡，这促使了信道编译码技术应用于民用数字通信系统中，尤其是无线通信系统中。第二章线性分组码2.1线性分组码的基本概念通信的根本任务是远距离传递信息,因而如何准确地传输数字信息是数字通信的一个重要组成部分。而线性码具有纠错能力,目前已广泛用于各种通信系统和计算机系统中。线性分组码（n，k）中许用码字（组）为2k个。定义线性分组码的加法为模2和，乘法为二进制乘法。即1+1=0、1+0=1、0+1=1、0+0=0；1×1=1、1×0=0、0×0=0、0×1=0。且码字与码字的运算在各个相应比特位上符合上述二进制加法运算规则。线性分组码具有如下性质（n，k）的性质：1、封闭性。任意两个码组的和还是许用的码组。2、码的最小距离等于非零码的最小码重。对于码组长度为n、信息码元为k位、监督码元为rnk位的分组码，常记作（n，k）码，如果满足2r1n，则有可能构造出纠正一位或一位以上错误的线性码。一个编码系统中任意两个合法编码（码字）之间不同的二进数位（bit）数叫这两个码字的码距，而整个编码系统中任意两个码字的的最小距离就是该编码系统的码距。码距越大，纠错能力越强，但数据冗余也越大，即编码效率低了。所以，选择码距要取决于特定系统的参数。线性码具有很多优点。首先，线性码比非线性码更容易编码和译码。其次，线性码传送信息更快。而且码的所有码字可由它的基底表示，线性码的最小距离和它的最小重量相等。2.2线性码的编码和译码下面的图5叙述的是通信系统的一个基本模式，它表示了信道编码、译码的基本流程。图5信道编译码基本流程信息源的信息m1m2mk编码为码字c1c2cn,通过可能受到干扰的信道传送,这时收到的码字可能不是发送的码字,译码器将决定并尽可能纠正出现的错误,最后终端收到理想的结果。2.2.1线性码的编码在通信中信息一般是用一串长度固定的符号序列来表示的。编码就是把字符(letter)转变成数码。设长度为n,空间维数k的线性码,有生成矩阵G,则xG=x1g1+x2g2+xngn,其中G=,且例设C是长度5,空间维数3的线性码,其生成矩阵为设下列码字各表示一个字母000100010001110101011111ASTYEBHF将信息“SAFETY”编码为S(100)G=10110A(000)G=00000F(111)G=11000E(110)G=11101T(010)G=01011Y(001)G=00101于是所得的码为101100000011000111010101100101。2.2.2线性码的译码假设码字x=x1x2xn是沿着信道传送的码字,假如收到的字是y=y1y2yn。我们定义误差为e=y-x=e1e2en。这时编码器必须决定这里的y就是信源集发送的码字x。该过程在线性码的译码过程中，将完成如何把出现的误差化为零,或者说如何把码字y纠正为x。如图6所示。图6线性码通信模型例设C为一个4,2-code,其生成矩阵为事实上码C是线性码,于是可以找出它的基底就是1011,0101因此,易知码C为C=0000,1011,0101,1110。下面可以求码C的陪集a+C,即0000101101011110100000111101011001001111000110100010100101111100不难看出,第一行就是码C,第一列的选择是具有最小重量码字，称之为陪集首(cosetleader)。假设发送的信息为10，编码为x=1011,而通过信道传送接收的是y=1111,处在上面矩阵的第三行,于是译码器决定出现的错误是0100，与y具有相同的行,此时将收到y的被译码为x=y-e=1111-0100=1011,而它处在与y相同例的第一个元素。这个就是发送的信息,于是终端收到了理想的结果。因此,在线性码的译码过程中需要算出码C的陪集a+C,通常选0为码C的陪集首(cosetleader)。0+C作为上面表格的第一行,收到的码字从上面的表中查出所处的位置。2.3Hamming（汉明）码当计算机存储或移动数据时，可能会产生数据位错误，这时可以利用汉明码来检测并纠错，简单的说，汉明码是一个错误校验码码集，由Bell实验室的R.W.Hamming发明，因此定名为汉明码。以典型的4位数据编码为例，汉明码将加入3个校验码，从而使实际传输的数据位达到7个（位），如表1。表14位数据编码数据位1234567代码P1P2D8P3D4D2D1说明第1个汉明码第2个汉明码第1个数据码第3个汉明码第2个数据码第3个数据码第4个数据码注：Dx中的x是2的整数幂结果，多少幂取决于码位，D1是0次幂，D8是3次幂。现以数据码1101为例，阐述汉明码的编码原理。此时D8=1、D4=1、D2=0、D1=1。在P1编码时，先将D8、D4、D1的二进制码相加，结果为奇数3，汉明码对奇数结果编码为1，偶数结果为0，因此P1值为1。D8+D2+D1=2，为偶数，那么P2值为0。D4+D2+D1=2，为偶数，P3值为0。这样参照上文的位置表，汉明码处理的结果就是1010101。在这个4位数据码的例子中，我们可以发现每个汉明码都是以三个数据码为基准进行编码。它们的对应关系如表2所示。表2对应关系汉明码编码用的数据码P1D8、D4、D1P2D8、D2、D1P3D4、D2、D1从编码形式上，可以发现汉明码是一种校验很严谨的编码方式。在这个例子中，通过对4个数据位的3个位的3次组合检测，来达到具体码位的校验与修正目的。在校验时，则把每个汉明码与各自对应的数据位值相加，如果结果为偶数（纠错代码为0）就是正确，如果为奇数（纠错代码为1），则说明当前汉明码所对应的三个数据位中有错误，此时再通过其他两个汉明码各自的运算，来确定具体是哪个位出了问题。还是刚才的1101的例子，正确的编码应该是1010101，如果第三个数据位在传输途中因干扰而变成了1，就成了1010111。检测时，P1+D8+D4+D1的结果是偶数4，第一位纠错代码为0，正确。P1+D8+D2+D1的结果是奇数3，第二位纠错代码为1，有错误。P3+D4+D2+D1的结果是奇数3，第三位纠错代码代码为1，有错误。那么具体是哪个位有错误呢？三个纠错代码从高到低排列为二进制编码110，换算成十进制就是6，也就是说第6位数据错了，而数据第三位在汉明码编码后的位置正好是第6位。那么汉明码的数量与数据位的数量之间有何比例呢？上面的例子中数据位是4位，加上3位汉明码是7位，而2的3次幂是8。这其中就存在一个规律，即2PP+D+1，其中P代表汉明码的个数，D代表数据位的个数，比如4位数据，加上1就是5，而能大于5的2的幂数就是3（23=8，22=4）。这样，我们就能算出任何数据位时所需要的汉明码位数：7位数据时需要4位汉明码（244+7+1），64位数据时就需要7位汉明码（2764+7+1），可以依此推算。另外，汉明码加插的位置也是有规律的。以四位数据为例，第一个是汉明码是第一位，第二个是第二位，第三个是第四位，1、2、4都是2的整数幂结果，而这个幂次数是从0开始的整数。这样可以推断出来，汉明码的插入位置为1（20）、2（21）、4（22）、8（23）、16（24）、32（25）。第三章Hamming码的编程实现3.1VC+6.0开发环境C+是一种静态数据类型检查的，支持多重编程范式的通用程序设计语言。它支持过程化程序设计、数据抽象、面向对象程序设计、泛型程序设计等多种程序设计风格。严格的来说VC+不是门语言，虽然它和C+之间有密切的关系,如果形象点比喻的话，可以C+看作为一种”工业标准”，而VC+则是某种操作系统平台下的”厂商标准”,而”厂商标准”是在遵循”工业标准”的前提下扩展而来的。VC+是微软公司开发的一个IDE(集成开发环境),换句话说,就是使用c+的一个开发平台，是Windows平台上的C+编程环境。VisualC+6.0是微软公司推出的开发Win32应用程序（Windows95/98/2000/XP/NT）的、面向对象的可视化集成工具。它的最大优点就是提供了功能强大的MFC类库，MFC是一个很大的C+类层次结构，其中封装了大量的类及其函数，很多Windows程序所共有的标准内容可以由MFC的类来提供，MFC类为这些内容提供了用户接口的标准实现方法，程序员所要做的就是通过预定义的接口把具体应用程序特有的东西填入这个轮廓，这将简化编程工作，大大的减少程序员编写的代码数量，使编程工作变得更加轻松容易。VisualC+6.0开发环境如图7所示。代码编辑区工作区图7VisualC+6.0开发环境从主体上看VC+6.0可以分为三大部分DeveloperStudio、MFC、PlatformSDK。这是一个集成开发环境，我们日常工作的99%都是在它上面完成的。3.2Hamming码编译码器的设计首先构造最佳奇权码的校验矩阵即H矩阵，最佳奇权码的H矩阵应满足：(1)每列含有奇数个1，且无相同列；(2)总的1的个数少，所以校验位、伴随式生成表达式中的半加项数少，从而生成逻辑所需的半加器少，可以节约器材、降低成本和提高可靠性。(3)每行中1的个数尽量相等或接近某个平均值，这种决定了生成逻辑及其级数的一致性，不仅译码速度快，同时线路匀称。译码时把数据再次编码所得到的新校验位与原校验位模二加，便得到伴随式S，由其可判别错误类型。（1)若S0，则认为没有错误；(2)若S0，且S含有奇数个1，则认为产生了单位错；(3)若S0，且S含有偶数个1，则认为产生了两位错；其中的情况(2)中，根据错误图样可以确定错误位置，将其取反即可完成纠错因为对用户而言真正有用的是数据，校验位是无用的。为了节省时间和器材，只对数据纠错，而对校验位不进行纠错，纠错后的数据也不再写回存储器。hammingDlg.cpp部分代码如下：voidCHammingDlg:OnButtonEncode()UpdateData(true);inti;charstr="00000000000"for(i=0;i<7;i+)if(m_inputi='0')input6-i=0;elseinput6-i=1;encodeout2=input0;encodeout4=input1;encodeout5=input2;encodeout6=input3;encodeout8=input4;encodeout9=input5;encodeout10=input6;encodeout0=input0input1input3input4input6;encodeout1=input0input2input3input5input6;encodeout3=input1input2input3;encodeout7=input4input5input6;for(i=0;i<11;i+)if(encodeouti=0)str10-i='0'elsestr10-i='1'm_encodeout=str;UpdateData(false);voidCHammingDlg:OnButtonNoise()srand(unsigned)time(NULL);m_noisebit=rand()%11;encodeoutm_noisebit-1=encodeoutm_noisebit-11;UpdateData(false);voidCHammingDlg:OnButtonDecode()intoutput7;intN,check4;charstr="0000000"N=0;inti;output0=encodeout2;output1=encodeout4;output2=encodeout5;output3=encodeout6;output4=encodeout8;output5=encodeout9;output6=encodeout10;check0=encodeout2encodeout4encodeout6encodeout8encodeout10;check1=encodeout2encodeout5encodeout6encodeout9encodeout10;check2=encodeout4encodeout5encodeout6;check3=encodeout8encodeout9encodeout10;check0!=encodeout0?N=N+1:N=N;check1!=encodeout1?N=N+2:N=N;check2!=encodeout3?N=N+4:N=N;check3!=encodeout7?N=N+8:N=N;encodeoutN-1=encodeoutN-11;output0=encodeout2;output1=encodeout4;output2=encodeout5;output3=encodeout6;output4=encodeout8;output5=encodeout9;output6=encodeout10;m_errorbit=N;for(i=0;i<7;i+)if(outputi=0)str6-i='0'elsestr6-i='1'm_decodeout=str;UpdateData(false);3.3编译结果编译结果如图8所示。图8编译结果-参考文献1冯桂林其伟陈东华编著,信息论与编码技术.清华大学出版社2王琳徐位凯编著,高效信道编译码技术及其应用.人民邮电出版社3刘振安等编著，C+程序设计.机械工业出版社4(英)PeterSweeney著，俞越张丹译，差错控制编码.清华大学出版社