[优秀毕业论文]（128120）扩展汉民循环码的原理及实现

本科生毕业论文（设计） 题 目 （128，120）扩展汉民循环码的原理及实现 学生姓名 _ _指导教师 _ _学 院 _信息科学与工程_ 专业班级 _通信工程2003级01班完成日期 2007.3-2007.6 目 录摘 要IIIABSTRACTIV第一章 概论11.1对课题研究的意义11.2差错控制编码技术理论研究21.2.1差错控制编码技术的概念21.2.2差错控制的基本方式21.2.3差错控制编码的分类31.2.4差错控制编码技术的应用31.3几种主要的差错控制编码5第二章 循环码的理论研究82.1线性分组码82.1.1线性分组码的基本概念82.1.2线性分组码的构成原理82.2循环码92.2.1循环码的基本概念102.2.2循环码的生成多项式102.2.3循环码的生成矩阵102.2.4循环码的编码方法112.2.5循环码的译码方法122.3汉民码基本理论122.3.1汉民码及其特点122.3.2汉民码的编码原理122.3.3汉民码的译码原理132.4扩展汉民循环码的理论研究142.4.1扩展汉民循环码的纠、检错译码方法142.4.2汉民循环码的扩展方案14第三章(128，120)扩展汉民循环码的编、译码电路设计与实现163.1(128，120)扩展汉民循环码的编码电路方案设计163.2(128，120)扩展汉民循环码的译码电路方案设计173.3(128，120)扩展汉民循环码的编、译码电路的具体实现183.3.1(128，120)扩展汉民循环码的编码电路183.3.2(128，120)扩展汉民循环码的译码电路22第四章(128，120)扩展汉民循环码的软件实现254.1软件实现工具的选择254.1.1matlab语言简介254.1.2汇编语言简介254.2(128，120)扩展汉民循环码编码过程的实现264.2.1余式表TAB1的设计264.2.2编码过程284.3(128，120)扩展汉民循环码解码过程的实现294.3.1纠错表TAB2的设计294.3.2解码过程31第五章毕业设计总结325.1总结325.2设计有待改进之处32致谢33参考文献34摘 要文章首先简要论述了差错控制编码技术的概念及其基本原理和工作方式，探讨了差错控制编码技术在蓝牙通信中所能解决的问题及其应用。简单介绍了几种常见的差错控制编码，其中重点介绍了循环码。循环码是线性分组码，它的最大特点就是可以用简单的电路来实现编解码。汉明循环码是一种能纠一位错的线性分组码，它的编译码简单，最小码距为3，可以纠正1位错误，但对于2位错不能检测，还可能会造成误纠，因此需要对其进行扩展。文章给出了扩展汉民循环码的一种实现方案,它的特点是在编译码时都把循环码和奇偶校验位分开处理, 使得能用比较简单的电路实现纠正1位错同时检测2位错的译码要求，并给出了编、译码电路的具体设计方法。本文还讨论了扩展汉民循环码的软件实现方法。在软件无线电系统等场合用软件实现差错控制编码是必要的，对于不同长度的扩展汉民循环码，虽然原理相同，但是软件设计会有很大区别，本文对编码效率较高，程序较简单的（128，120）扩展汉民循环码的软件实现方法进行了研究。关键词: 差错控制编码，循环码，扩展汉民码，电路设计ABSTRACTThe concept of error-control coding is simply described. At the basis of this point, introduces the error-correction techniques basic principle and its working method. Finally, mentions how the error-control technique solve problems and its application in Bluetooth. The article also simply introduced some simple error-control coding, especially cyclic code. Cyclic code is a linear code, its biggest feature is that it can use a simple electric circuit to realize coding and decoding. Hamming cyclic code is 1-error correcting linear code, whose coding and decoding is simple and minimum distance is 3, it can correct 1 error, but cant check 2 errors, so its necessary to be expended.This paper presents a realization scheme for expended hamming cyclic code, its characteristic is that the cyclic code and parity check bit are treated with separately both in coding and decoding, so the decode request to correct 1 error and find out 2 errors can be realized with quite simple electric circuits, and the design method is given out for the code and decode electric circuits. In this article it is also discussed how to realize the method of expended hamming cyclic code with software. Its necessary to realize error-control coding with software in software radio systems and other occasions. For different length of the expended hamming cyclic code, although the principium is same, the software design is different, in this paper, the software solutions of (128,120) expended hamming cyclic code are studied, which have great coding efficiency and simple programme.KEY WORDS: error-control coding, cyclic code, expended hamming code,Circuit designIII(128,120)扩展汉民循环码的原理及实现 第一章 概论第一章 概论1.1对课题研究的意义汉明码是在原编码的基础上附加一部分代码，使其满足纠错码的条件。它属于线性分组码， 由于线性码的编码和译码容易实现，至今仍是应用最广泛的一类码。汉明码的抗干扰能力较强，但付出的代价也很大，比如8比特汉明码有效信息只有总编码长度的一半，可以纠正1个差错发现2个差错。在实际应用中常常存在各种突发干扰，使连续多位数据发生差错。为了纠正3个以上的差错，就要加大码距，使代码冗余度大大增加，通信效率下降。本文所介绍的方法，就可以在不加大码距的同时， 提高汉明码对突发干扰所产生差错的纠错能力，纠正多位连续的差错。汉明码的码距为3，可以纠正一位错误或者检2位错。如果按照纠正1位错的要求设计译码器，当一个码字中出现2位错误是，就会发生译码错误，降低了系统可靠性。如果按照检测2位错的要求设计译码器，只要码字中出现1位错误就得进行重发，又降低了系统的效率。所以把系统的差错控制能力从“纠正1位错”提高到“纠正1位错同时检测2位错”是很有意义的。使用扩展汉民码可以明显改善通信系统的性能。例如某一监控系统，需要把远端的数据发给管理微机，传输误码率为，进行差错控制编码，每个码字中的信息位为120比特每100个码字为一组，只要其中有一个码字发生了错误，就要对该组数据进行重发。如果采用(127,120)汉民循环码，则数据组重发的概率为。如果采用(128,120)扩展汉民循环码，按“纠1检2”方式进行译码，则数据重发的概率为，可见使用扩展汉民码对减少随机性误码的影响有明显效果。当然，是否需要进行纠错译码取决于信道传输的误码率Pe，如果Pe很小(数据组出错的概率也很小)，就可以考虑采用检错错误重发的方案，这时可以在CCITT推荐的几种CRC码中选用。针对突发性错误，还可以把扩展汉民码与CRC编码相结合(为每组数据再加CRC编码)，以进一步提高系统的可靠性。在不能进行数据重发的单向传输系统(比如数字广播系统)中，使用扩展汉民码对提高系统的传输质量可发挥更大作用。1.2差错控制编码技术理论研究1.2.1差错控制编码技术的概念信道干扰源可分为无源干扰和有源干扰。前者引起的差错是一种随机差错，即某个码元的出错具有独立性，与前后码元无关。而后者是由短暂原因如突然施加干扰源引起的，差错是成群的，其差错持续时间称为突发错的长度。在信息传输中，二者均有可能被引人。根据具体情况而选定合适的差错控制编码可以发现并纠正这些错。差错控制编码也称为纠错编码。在实际信道上传输数字信号时，由于信道传输特性不理想及加性噪声的影响，接收端所收到的数字信号不可避免地会发生错误。为了在已知信噪比情况下达到一定的比特误码率指标，首先应该合理设计基带信号，选择调制解调方式，采用时域、频域均衡，使比特误码率尽可能降。但实际上，在许多通信系统中的比特误码率并不能满足实际的需求。此时则必须采用信道编码(即差错控制编码)才能将比特误码率进一步降低，以满足系统指标要求。差错控制随着差错控制编码理论的完善和数字电路技术的飞速发展，信道编码已经成功地应用于各种通信系统中，并且在计算机、磁记录与各种存储器中也得到日益广泛的应。差错控制编码的基本实现方法是在发送端将被传输的信息附上一些监督码元，这些多余的码元与信息码元之间以某种确定的规则相互关联(约束)。接收端按照既定的规则校验信息码元与监督码元之间的关系，一旦传输发生差错，则信息码元与监督码元的关系就受到破坏，从而接收端可以发现错误乃至纠正错误。1.2.2差错控制的基本方式(1)反馈纠错ARQ反馈纠是在信源端采用能发现一定程度传输差错的简单编码方法对所传信息进行编码(加入少量监督码元)，在信宿端根据编码规则对收到的编码信号进行检查，一旦检测出误码，即向信源端发出信号要求重发。信源端收到信号后，立即重发已发生传输差错的那部分信息，直到正确收到为止。这种方法只能发现接收码元中的一个或一些错误，但无法确定误码的准确位置，较适合于双向数据通信，要求信源端有数据存储装置。(2)前向纠错FEC前向纠错是信源端采用在解码时能纠正一定程度传输差错的较复杂的编码方法，使信宿端在收到码元后不仅能发现错码，还能够纠正错码。采用前向纠错方式时，不需要反馈信道，也无需反复重发而延误传输时间，对实时传输有利。但是纠错装置比较复杂。此方法可用于没有反馈通道的单向数字信号的传输。(3)混合纠错HEC混合纠错即在接收端自动纠正少量差错，当误码严重超出其自行纠正能力时，就向信源端发出询问信号，要求重发，是反馈纠错和前向纠错的混合形式。1.2.3差错控制编码的分类差错控制编码按照差错控制的不同方式，可分为检错码、纠错码和纠删码等；按照误码产生的原因不同，可分为纠正随机错误码与纠正突发性错误码；按照信息码元与附加的监督码元之间的检验关系，可分为线性码与非线性码；按照信息码元与附加监督码元之间的约束方式不同，可以分为分组码与卷积码；按照信息码元在编码之后是否保持原来的形式不变，可分为系统码与非系统码。按照每个码元的取值不同，可以分为二进制码和多进制码。1.2.4差错控制编码技术的应用差错控制随着差错控制编码理论的完善和数字电路技术的飞速发展，信道编码已经成功地应用于各种通信系统中。下面简单介绍下差错控制编码在蓝牙技术中的应用蓝牙(bluetooth)是一种开放的短距离无线通信技术规，利用它可以在世界上的任何地方实现短距离的无线语音和数据通信.蓝牙系统工作在2.400一2.4835 GHz的ISM (Industrial Scientific and Medical)频段.由于ISM频带对公众开放，无需特许，因此使用其中的任何一个频带都有可能遇到不可预知的干扰源，如某些家电、无绳电话、微波炉等都可能产生干扰.如何降低通信中的误码率、提高通信的质量便是蓝牙系统中一个必须重视的问题，而差错控制编码则是解决这一问题的关键技术。由于对语音、数据和控制信息所要求的误码率不同，蓝牙系统中采用了4种不同的差错控制方案:码率为1/3的FEC码率为2/3的FEC混合ARQFEC/ARQ自适应差错控制方式(1)码率为1/3的FEC方案此方案采用码长为3的重复码，传输时每比特连续发送3次，接收端用大数判决法译码，接收时即使三位中错了一位，也可以自动纠正过来，故有很强的纠错能力。该方案在蓝牙系统中用于报头纠错及HV1包的语音段。(2)码率为2/3的FEC方案此方案采用(15,10)缩短汉明码，其生成多项式为: ，该码可纠正一个码字中所发生的所有单个错误，或检查出任意两个错误。此方案适用的包格式有:DM (包括DM1,DM3, DM5)包、HV2包、DV包的数据段，以及FHS包。(3)ARQ方ARQ通常用于传输信令和控制报文等重要的数据帧。现有的无线数据网标准如CDPD, GSMData,GPRS、WCDMA和cdma2000等，都提供了ARQ选项.ARQ工作在数据链路层。发信端将按组分成若干个数据帧进行传输，并启动计时器以防数据帧丢失。接收端在收到数据帧后需要立即回送ACK(AC-Knowledgement)确认帧，发现数据帧出错或丢失，则回送NACK (Negative AC-Knowledgement)确认帧。源端在收到NACK或者计时器超时后，会重传丢失的数据帧。收端将数据帧排序并还原成原始的分组，提交给高层(TCP)协议。ARQ的按序提交机制确保分组提交给高层，不会因重传而打乱。这一点非常重要，否则尽管丢失的分组已经被BS重传了，但分组的失序通过TCP确认反馈到源端，仍然会使TCP源端降低发送速率。(4)FEC/ARQ自适应差错控制方式ARQ方式由于其工作可靠性高、实现简单，在蓝牙系统中得到了广泛的应用。但当信道干扰严重时，由于误码率较高，ARQ将反复请求重传，从而导致传信率极低。针对这一情况，提出一种新的解决方案：采用FEC与ARQ相结合的自适应差错控制方式。自适应差错系统采用(2,1,4X+2)扩散卷积码(X为扩散度)。卷积码的保护长度随着扩散度的增大而增大。扩散度越大，器件的运算量就越大，对系统传输效率的影响也就越大。器件的运行速度限制了扩散度的大小，所以应根据信道的误码情况选择合适的扩散度。系统将扩散度分为5档，分别为32, 64, 96, 128及160.信道 的 干 扰状况由误帧率来反映，误帧率的计算依据为(帧长400比特时)：发送端每发送30帧(包括重发帧)计算一下有效发送帧数。如果有效发送帧数大于27帧，则说明信道条件好，接受端向发送端发送一特殊帧，通知发送端不使用纠错码，工作于ARQ方式。如果有效发送帧数小于27帧，则通知发送端采用纠错码，工作于FEC/ARQ方式。当工作在FEC/ARQ方式时，首先选择扩散度为32，如果重发30帧(包括重发帧)，有效发送帧数仍小于27帧，则扩散度选大一档，即X=64，再重新统计；如果有效发送帧大于27帧，则保持此档扩散度，如连续900帧的有效传帧率为100%，则将扩散度选小一档，再依此进行统计、判决，从而实现对扩散度的动态调整。至于有效传送帧数门限值的选择取决于系统的总体要求，可依照情况将门限值27帧改为26, 28帧或其它帧数。模拟实验表明:当信源码率为64Kb/s，信道存在能引起差错率的干扰时，FEC/ARQ自适应差错控制方式可大大减少重传的次数，提高信息的传输速率。随着科学技术特别是信息技术的发展，差错控制编码在数据通信领域中发挥着越来越重要的作用，它是解决数据通信领域中相关问题的有力工具。由于差错控制编码解决问题的思路和方法非常独特、新颖和有效。越来越广泛地应用到各个领域当中，并且显示出他的勃勃生机和不可估量的发展前。1.3几种主要的差错控制编码(1)奇偶监督奇偶校验码也称奇偶监督码，它是一种最简单的线性分组检错编码方式。其方法是首先把信源编码后的信息数据流分成等长码组 ，在每一信息码组之后加入一位(1比特)监督码元作为奇偶检验位，使得总码长n(包括信息位k和监督位1)中的码重为偶数(称为偶校验码)或为奇数(称为奇校验码)。如果在传输过程中任何一个码组发生一位(或奇数位)错误，则收到的码组必然不再符合奇偶校验的规律，因此可以发现误码。奇校验和偶校验两者具有完全相同的工作原理和检错能力，原则上采用任一种都是可以的。奇偶监督码常用于反馈纠错法。(2)重复码 由通过重发每个信息码元来提高抗干扰能力，这就构成了重复码。重复码可看作(n,1)分组码。例如信息码元为0或1，可分别重复一次，即为00或11，这样就构成双重复码。双重复码可以发先1位错误。若采用三次重发，即用000代替0，用111代替1，则具有更高的抗干扰能力，能够检出两位错误，或者可以自动纠正一位错误。随着n的增加，重复码集中只有两个码长为n的许用码组(码子)，余下的个为禁用码组。在其检纠能力增强的同时，其编码效率将降低。(3)行列监督码 行列监督码是二维的奇偶监督码，又称为矩阵码，这种码可以克服奇偶监督码不能发现偶数个差错的缺点，并且是一种用以纠正突发差错的简单纠正编码。 其基本原理与简单的奇偶监督码相似，不同的是每个码元要受到纵和横的两次监督。具体编码方法如下：将若干个所要传送的码组编成一个矩阵，矩阵中每一行为一码组，每行的最后 加上 一个监督码元，进行奇偶监督，矩阵中的每一列则由不同码组相同位置的码元组成，在每列最后也加上一个监督码元，进行奇偶监督。矩阵码发现错码的能力是十分强的，它的编码效率当然比奇偶监督码要低。(4)等比码 等比码又称为等重码。在等比码中，每个码组“1”和“0”都保持固定的比例故得此名。 这种码在检测时，只要计算接收到的码组中“1”的数目是否对就知道有无错误。在我国用电传机传输汉字时，只使用阿拉伯数字代表汉字。这时采用的所谓“保护电码”就 是“32”或称“5中取3”的等比码，即每个码组的长度为5，其中“1”的个数总是3，而 “0”的个数总是2。这类码比奇偶监督码更加严格，除了“1错成0”或“0错成1”的成对的偶数错误外，其它错误也能检测出来，因此它的检错能力很强。(5)循环码循环码是一种重要的线性码，它有三个主要数学特征:循环码具有循环性，即循环码中任一码组循环一位(将最右端的码移至左端)以后，仍为 该码中的一个码组。循环码组中任两个码组之和(模2)必定为该码组集合中的一个码组。循环码每个码组中，各码元之间还存在一个循环依赖关系，b代表码元，则有 有关循环码将在第二章详细讲述。(6)卷积码分组码是把k个信息比特的序列编成n个比特的码组，每个码组的n-k个校验位仅与本码组的k个信息位有关，而与其他码组无关。为了达到一定的纠错能力和编码效率，分组码的码组长度一般都比较大。编译码时必须把整个信息码组存储起来，由此产生的译码延时随n的增加而增加。卷积码与分组码不同，它将信息比特分成长度为的一个子组，长为的每个子组码字(叫做子码)，包括个信息位和个监督位。这个监督元不仅与本子码的个信息位有关，也与前面(N-1)个子码有关，这里N为分段数。整个编码过程是一环扣一环连续地进行下去，故称为连环码。因为其编码器的输出可以看成是输入信息比特与编码器响应函数的卷积，故有名卷积码。通常较小，特别适合于以串行形式传输的信息，其时延很小。又由于它充分利用了各子码之间的相关性，故卷积码的纠错能力随着N的增加而增大，而差错率随着N的增加而指数下降。(7)RSRS码是Reed-Solomon 码（理德所罗门码）的简称，它是一类非二进制BCH码，在(n,k)RS码中，输入信号分成km比特一组，每组包括k个符号，每个符号由m个比特组成，而不是前面所述的二进制码由一个比特组成。一个纠t个符号错误的RS码有如下参数:码长:符号，或比特；信息段：k符号，或mk；监督段：n-k=2t符号，或m(n-k)；最小码距：d=2t+1符号，或m(2t+1)。(8)群计数码 奇偶校验码中对每个码字中1码的个数进行奇偶监督，因而其检错能力有限。如果能对码字中1码的数量进行监督，那么检测能力显然会加强。群计数码在编码时，首先计算信息码字中1码的个数，然后用二进制数代表这个数目，作为监督位附在信息位后面。例如要传送的信息码时11101，那么监督位应该是100(10进制的4)，编出的群计数码为1110100。显然，这种码除了能发现奇数个错码外，还可以发现一些偶数个错码。在信息位里，除了0变1和1变0成对地出现外，所有其它形式的错码都会使信息位里1码的数目与监督位的二进制数字不符，所以这类码的检错能力是有限的。33(128,120)扩展汉民循环码的原理及实现 第二章 循环码的理论研究第二章 循环码的理论研究2.1线性分组码2.1.1线性分组码的基本概念将信息序列中每k个码元分成一组，然后由这k个码元按一定的规则产生r个监督码元，两者再组成长度为n=k+r的码字，这样就构成的分组码。当分组码中监督码元与信息码元满足模2加代数方程时，就可称为(n,k)线性分组码。线性分组码具有如下性质(n，k)的性质：1、封闭性。任意两个码组的和还是许用的码组。2、码的最小距离等于非零码的最小码重。2.1.2线性分组码的构成原理对于码组长度为n、信息码元为k位、监督码元为rnk位的线性分组码，常记作(n，k)线性分组码，如果满足2r1n，则有可能构造出纠正一位或一位以上错误的线性分组码。下面我们通过(7，4)分组码的例子来说明如何具体构造这种线性码。设分组码(n，k)中，k = 4，为能纠正一位误码，要求r3。现取r3，则nkr7。我们用表示这7个码元，用、表示由三个监督方程式计算得到的校正，并假设三位、校正子码组与误码位置的对应关系如表2.1所示。表 2.1 校正子码组与误码位置的对应关系表误码位置误码位置001101010110100111011000无错由表2.1可知，当误码位置在、时，校正子1；否则0。因此有，同理有和。在编码时、为信息码元，、为监督码元。则监督码元可由以下监督方程唯一确定。 即由上面方程可得到表2.2所示的16个许用码组。在接收端收到每个码组后，计算出、如果不全为0，则表示存在错误，可以由表2.1确定错误位置并予以纠正。例如收到码组为0000011，可算出=011,由表2.1可知在上有一误码。通过观察可以看出，上述(7，4)码的最小码距为3，它能纠正一个误码或检测两个误码。如果超出纠错能力则反而会因“乱纠”出现新的误码。表 2.2 许用码组表信息位监督位信息位监督位00000001001000110100010101100111000011101110110101011000100010011010101111001101111011111111000100010010101001112.2循环码循环码是线性分组码中最重要的一种子类，是目前研究得比较成熟的一类码。循环码具有许多特殊的代数性质，这些性质有助于按照要求的纠错能力系统地构造这类码，并且简化译码算法，并且目前发现的大部分线性码与循环码有密切关系。循环码还有易于实现的特点，很容易用带反馈的移位寄存器实现其硬件。正是由于循环码具有码的代数结构清晰、性能较好、编译码简单和易于实现的特点，因此在目前的计算机纠错系统中所使用的线性分组码几乎都是循环码。它不仅可以用于纠正独立的随机错误，而且也可以用于纠正突发错误。2.2.1循环码的基本概念循环码是一种线性分组码(n,k),循环码的前k位是信息码元，后r位为监督码元，它除了具有线性分组码的封闭性之外，还具有循环性。所谓循环性是指循环码中任一码字(许用码组)经过循环移位后所得的码组仍为一许用码组(码字)，即()是一个码字，则同样也是一个码。2.2.2循环码的生成多项式由于循环码的全部码字由生成多项式g(x)决定，因此寻找一个(n,k)循环码生成多项式是循环码编码的关键。任一循环码的码多项式A(x)都是g(x)的倍式，故可以写成 A(x)=h(x)g(x) 公式 (2.1)而生成多项式g(x)本身也是一个码字，即有因为g(x)是一个(n-k)次多项式，故为一n次多项式，在模运算下亦为一个码字，有 公式 (2.2)上式左端分子和分母都是n次多项式，故Q(x)=1，上式又可以写成 或 公式 (2.3)上式表明，生成多项式g(x)应该是的一个因式，即循环码的生成多项式应该是的一个n-k次因式。2.2.3循环码的生成矩阵对于(n,k)线性分组码，有了生成矩阵G，就可以有k个信息码元得到全部码字。生成矩阵G的每一行都是一个码字，若能找到k个线性无关的已知码字，就能构成生成矩阵G。在循环码中，一个(n,k)分组码有个不同的码字，若用g(x)表示其中前(k-1)位皆为“0”的码字，都是码字，可以证明这k个码字是线性无关的，因此可以用它们来构成此循环码的生成矩阵G。这样，循环码的生成矩阵G可以写成需要说明的是，在循环码中除全“0”码组之外，再没有连续k位均为“0”的码组。即连“0”的长度最多只能有(k-1)位。否则经过若干次循环移位后会得到一个k位信息位全是“0”，而监督位不是全“0”的码字，这在线性码中是不可能的，因为线性码的监督位是信息位的线性组合。所以g(x)必须是一个常数项不为“0”的(n-k)次多项式，而且这个g(x)还是这种(n,k)循环码中次数为(n-k)的唯一一个多项式。因为，如果这样的(n-k)次多项式有两个，由码的封闭性克制，把这两个码组相加，得到的也应该是一个码字，而此多项式的次数必然小于(n-k),即连“0”的个数多于(k-1)个。显然这是不可能的，我们称这唯一的(n-k)次多项式g(x)为码字多项式。一旦确定了g(x)，则整个(n,k)循环码就被确定了。2.2.4循环码的编码方法已知输入的信息码元和生成多项式g(x)，就可以构成循环码，对应的码多项式为式中，M(x)称为信息码多项式。但是用这种相乘方法得到循环码不是系统码，信息码和监督码不容易区分。在系统码中，码字最左边的k位是信息码元，随后的n-k位是监督码元，这时码多项式可以写为 公式 (2.4)这里称为监督码多项式，它的次数小于(n-k),其监督码元为。由以上两式可以得到 公式 (2.5)或写成也就是模g(x)上式告诉我们，构造系统循环码时，只需用信息码多项式乘以，也就是将M(x)移位(n-k)次，然后用g(x)去除，所得的余式r(x)即为监督码多项式。因此系统循环码的编码过程就变成用除法求余的过程。2.2.5循环码的译码方法接收端译码的目的有两个：检错和纠错。以检错为目的的译码十分简单，由于循环码的码多项式能够被g(x)整除，所以在接受端可以将接收码组B(x)用原码生成多项式去g(x)去除。当在传输中未发生错误时，接收码组B(x)与发送码组A(x)相同，即有B(x)= A(x)，故B(x)必定能被g(x)整除；若接收码组发生错误时，即B(x)A(x)，B(x)不能被g(x)整除，会产生余项，即有。因此，我们可以利用余项是否为0来判断接收码组B(x) 中是否有错误。接收端在检出错误之后，可以向发送端发出指令，请求重发出错码组，直到接收到正确码组为止。2.3汉民码基本理论2.3.1汉民码及其特点汉明码是能够纠正一个错误的同时对监督位利用最充分的线性分组码，是汉明继香农编码定理提出后最早发明的一种高效编。它的编译码规则都很简单。汉明码实际上是线性码，其校验行为m行，共有列，任一列都不为0且两两互不相等，因此能纠正任何单个错误。汉明码有以下特点：对于任一整数m，；监督码元数目： r=m；码长： ；信息码元数目： ；最小距离： ；纠错能力： t=1。2.3.2汉民码的编码原理汉明码是在原编码的基础上附加一部分代码，使其满足纠错码的条件。它属于线性分组码，由于汉明码的抗干扰能力较强，至今仍是应用比较广泛的一类码。在(n,k)汉明码中，(n-k)个附加的监督码元是由信息码元的线性运算产生的。码长为n，信息元长度为k,个码字构成n维线性空间中的一个k维子空间，编码的实质就是要在n维空间中，找出一组长为n的k个线性无关的矢量，使得每个码字C都可以表示为k个矢量的线性组合，即 公式 (2.6)其中，,i=0,1,k-1.将上式写成矩阵形式 公式 (2.7)由此是带编码信息的信息组，G是一个nk阶矩阵，G称为(n,k)汉明码的生成矩阵。当G确定以后，编码的问题也就解决了2.3.3汉民码的译码原理由公式(2.7)可得到监督方程，从而得到监督矩阵H，或H称为监督矩阵，是一个(n-k)k矩阵。H的后n-k列组成一个(n-k)(n-k)阶单位子阵。这种H称为监督矩阵的标准形式，一般形式的H可以通过行列的初等变换得到。发送码组C在传输过程中可能发生误码，设接收到的码组为则收发码组之差为，其中 i=1,2,n-1上式也可写作R=C=E在接受端计算由于，所以S称为接收码组R的校验子或伴随式。由矩阵H进行译码，根据所得的伴随式就可判断码字中哪一位码元发生了错误，就可纠正一位随机错误。伴随式只与错误图样E有关，可以用S作为判别错误的参量，如果S=0，则接收到的是正确码字；若S0，则说明R中存在着差错。2.4扩展汉民循环码的理论研究2.4.1扩展汉民循环码的纠、检错译码方法汉民码的码距为3,可以纠正4位错,或者检测2位错。如果按照纠正1位错误的要求来设计译码器,当一个码字出现2 位错误时,就会发生错误的纠正动作。在许多情况下,传输系统的可靠性显得不够高。如果按照检测2位错误的要求设计译码器, 只要码字中出现了1位错误就得进行重发,又会降低系统的传输效率。由于纠正多位错的编码(如BCH 码)的纠错方法和译码电路都相当复杂,在码字长度不变情况下,监督位数也会大大增加(大约是汉民码的两倍),编码效率明显降低。所以如果能够把系统的差错控制能力从“纠正1位错”,提高到“纠正1位错误同时检测2位错误”是很有意义。就一般的线性分组码而言,为了达到能够“纠正1位错误同时检出2位错误”的要求,只要在汉民码的后面再加一个奇偶校验位就行了,这种编码称为扩展汉民码。例如一个(7,4)汉民码的校验矩阵为H,则对应的(8,4)扩展汉民码的校验矩阵为：H= = 只要先在H阵的最右边加一个全0列,再在最下边加一个全1行,就得到了阵。阵的最后一行用于全码字的奇偶校验, 其余各行则是对汉民码的校验。扩展汉民码的码距为4,可以检测3位错误,或纠正1位错误同时检测出2位错误。纠、检错译码的方是(假定码字中最多只有2位错误)。把接收码字C与校验矩阵进行运算,得到余式。如果S=0,则码字没有错误;如果S等于的某一列,则表示码字的对应比特发生了错误,可以纠正；如果S非0,但是最后一个比特为0, 则表示码字有两个错误, 不能够纠正。虽然矩阵容易写出,但要用电路来实现纠、检错译码(以及编码)却并不容易。所以对于实际应用,更有意义的还是对汉民循环码进行扩展。2.4.2汉民循环码的扩展方案扩展汉民循环码有两种方案, 一种是把汉民循环码的生成多项式g(x)改为,码字长度不变。用产生的码字,不是在用g(x)产生的循环码字后面增加一个奇偶校验位,而是减少了一位信息码,再增加一个校验位。这种方法的好处是编码仍然具有循环性, 编码及检错译码电路比较简单, 但是纠一位错同时检2 位错的译码电路设计有困难, 而且编码效率较前述的扩展汉民码低一些。这种扩展方法适用于只需要进行检错译码的场合, 比如在数据通信网中广泛使用的用于长数据包或文件检错的CRC(循环冗余校验)码。另外一种方案是把循环码的生成多项式乘上一个(x+1)因式,从而得到(n+1,k)的扩展码。此种扩展码相当于在汉民码上加上一个全校验位,但就整个码字而言编码已不再具有循环。这种扩展汉民循环码的译码电路(纠正1位错误同时检测2位错误)如何设计是一个值得讨论的问题。(128,120)扩展汉民循环码的原理及实现 第三章 (128,120)扩展汉民循环码的编、译码电路设计与实现 第三章(128，120)扩展汉民循环码的编、译码电路设计与实现这里给出一种扩展汉民循环码的实现方案,其特点是把循环码和奇偶校验位分开处理, 以便于用比较简单的电路来实现纠错同时检错的译码要求。3.1(128，120)扩展汉民循环码的编码电路方案设计取(127,120)汉民循环码的生成多项式为,则扩展汉民循环码为(128,120)码,其编码电路框图如图3.1所示:图3.1中用移位寄存器构成多项式除法器,反馈通路由除式g(x)确定。由或门输出的循环码前面120bit是信息码, 后面7bit是监督位。设信息多项式为m(x),除法器的初始状态为零,在120个信息位到齐后, 的状态就对应的余式s(x)，经7次移位由输出。循环码字为。偶效验编码电路的作用是在循环码后面再加上一个偶校验位。在输出校验位的一个节拍中除法器电路被清零。显然输出码字的前面127比特就是原汉民循环码, 最后一比特是附加的全校验位。码字120个1+0000000120个1+0000000=信息比特120个0+1111111偶校验编码器图 3.1 (127,120)汉民循环码的编码电路框图3.2(128，120)扩展汉民循环码的译码电路方案设计上述(128，120)扩展汉民循环码的译码电路框图如图3.2所示:A接收码字译码输出127bit移位寄存器128bit偶校验电路校验输出BBA逻辑判决报警C图 3.2 (128，120)扩展汉民循环码的译码电路框图电路分析： (1)127bit移位寄存器用来暂存一个码字(128bit全部到齐后才能进行纠错并输出)；(2)移位寄存器构成除法器，接收码字(前127比特)多项式被生成多项式除，余式即为伴随式；(3)移位寄存器构成纠错移位器，在一个码字的128bit都到齐后，伴随式移进到，经过移位处理，在错码位置上与门输出1是误码取反，实现纠错。纠、检码过程如下：被接收码字的前面127比特进入由组成的除法器1,计算得到循环码的余式。如果它是0,则或门的输出A=0；否则A=1。码字的128比特全都要进入偶校验电路, 如果码字有1位误,B=1;如果有2位错误,B=0。在码字的第128比特,余式进入由组成的除法器2,在以后的节拍中对余式进行循环移位, 在适当的时刻由与门输出纠错信号对127bit移位寄存器的输出进行纠错(实际只需要对码字前面120位信息码进行纠错输出)；逻辑判决电路根据A和B决定是否发出2位错误报警信号C。检、纠错判决逻辑如下(假定只发生1个或2个错误):如果A=0,B=0,则接收码字没有错误,信息码将直接输出；如果A=0,B0,则循环码没有错误,校验位发生了错误,信息码也直接输出；如果A0,B0,则循环码有1位错误,校验位正确,信息码将被纠错后输出；如果A0,B=0,则码字中有2位错误,不能纠错,只能报警。总之, 只有A0,B=0才需要发出2位错误报警,即。纠码过程举例：设发送的信息码为，接收到的码字为，即信息比特的第2位发生了错误。设误码多项式为，所以伴随式为。在码字到齐后，伴随式移进，即的状态为1000100,经1次移位后成为0100010，与门输入为1111111，输出为1，使接收码字的第2bit(此时已移到了127bit移位寄存器的最后一位)的输出由1变为0，即实现了纠错。3.3(128，120)扩展汉民循环码的编、译码电路的具体实现3.3.1(128，120)扩展汉民循环码的编码电路(1)移位寄存器：编码和译码电路中用到的移位寄存器都是由七个D触发器构成的七位移位寄存器。为了简单起见，这里以四个D触发器构成的四位移位寄存器为例，如图3.3，简单介绍一下移位寄存器的构成原理。图3.3 由D触发器构成的移位寄存器码字从第一个D触发器的D端输入，后面各触发器的输入为前一个触发器的输出Q。CD端联在一起作为复位端。当此端输入一个负向脉冲时，各触发器的状态全复成0。码字从 端逐个输入，在时钟(这里称作移位脉冲)的作用下逐个地将码字往右移，这样就构成了右移移位寄存器。(2)计数器：D触发器的特征方程为。如果将D触发器的端和D端相连，则D触发器的特征方程变为，这样就构成了一个二进制计数器。这里要注意的是由于维持-阻塞D触发器是由时钟脉冲的上升边沿触发的，这里采用从端进位，就构成一个递增计数器。如果采用从Q端进位，它将成为递减计数器。编码电路如图3.4所示：工作原理：信息比特进入由IC1、IC2、IC3、IC4：A(74LS74，双D触发器)和IC5(74LS283，四位并行进位全加器)够成的除法器，除法器的初始状态为零，在120个信息位到齐后，除法器的状态就是余式，也就是经编码产生的监督比特。监督比特与信息比特经过IC8：A(74LS32，四2输入或门)后输出的就是编码后的汉民循环码(注意此时产生的汉民循环码只有127bit，没有校验位)。要想得到加了校验位的(128，120)扩展汉民循环码，就必须再加一个偶效验编码电路。偶效验编码电路的作用是在循环码后面再加上一个偶校验位，显然输出码字的前面127比特就是原汉民循环码, 最后一比特是附加的全校验位。这样最后输出的码字就是编码后的(128，120)汉民循环码。偶校验编码电路如图3.5所示图 3.5 偶校验编码器工作原理：码字首先进入IC4：B(由D触发器够成的一个二进制计数器，注意是从CLK端输入，而不是D端)，此时码字就相当与计数器的脉冲信号，每到来一个脉冲1(相当于码字中的比特1)计数器的输出状态就会反转一次(由1变为0或由0变为1)，相当于计数一次。如果码字中有奇数个1，那么计数器的最终输出就是1。这样最后经过IC8：B(74LS32，四2输入或门)和原先的码字或，最后输出的码字就是加了偶检验位的(128，120)扩展汉民循环码。图 3.4 (128，120)扩展汉民循环码的编码电路图3.3.2(128，120)扩展汉民循环码的译码电路译码电路图如图3.6、3.7所示：工作原理：被接收码字的前面127比特进入由IC1、IC2、IC3、IC4：A(74LS74，双D触发器)组成的除法器1，计算得到循环码的余式，如果它是0，则经过IC14、IC15：A、IC15：B(74LS32，四2输入或门)后的输出A=0，否则A=1；码字的全部128比特全都要进入由IC8：A(由D触发器构成的一个二进制计数器具体电路如图3.5)，如果码字有1位错，B=1，如果有2位错误，B=0；假设只有1位错误发生，在码字的第128比特，余式进入(并行输入)由IC5、IC6、IC7、IC4：B(74LS74，双D触发器)组成的除法器2，经过移位处理(串行输入，为解决并行输入和串行输入的问题，需在IC5、IC6、IC7和IC4：B的输入端加上IC9和IC10(74LS157, 同相输出四2选1数据选择器) 上面有个控制信号，高电平时为串行输入，低电平时为并行输入)，在错码位置上经过IC13(74LS30，8输入与非门)，再经过IC12：F(74LS04，六反相器)(其实两者合起来相当与一个8输入与门)后输出为1；在接收码字进入第一个除法器的同时，它也同时进入由IC18IC33(74LS164，八位并行输出串行输入移位寄存器)组成的127bit移位寄存器，在8输入与门输出1的时刻，误码比特经过同样的移位也刚好到了127bit移位寄存器的最后1比特，此时两者经过IC11：D(74LS86，四2输入异或门)异或后使误码取反，实现纠错。最后A和B进入逻辑判决电路(B要先进入IC17：A(74LS04，六反相器)取反后和A一起进入IC16：A(74LS08,四2输入与门)进行逻辑判断)产生信号C，再根据C的值决定是否发出2位错误报警信号(具体的判决逻辑见3.2)。图 3.6 (128，120)扩展汉民循环码的译码电路(一)图 3.7 (128，120)扩展汉民循环码的译码电路(二)(128,120)扩展汉民循环码的原理及实现 第四章 (128,120)扩展汉民循环码的软件实现 第四章(128，120)扩展汉民循环码的软件实现4.1软件实现工具的选择软件设计包括包括两个数据表的设计和编解码程序设计两部分，数据表设计是事前进行的，可以使用高级编程语言，在这里用的是matlab语言；编解码程序需实时进行，应采用系统CPU的汇编语言编程，以求减少程序执行时间和提高硬件使用效率。4.1.1matlab语言简介matlab是由美国Mathworks公司于1984年正式推出的，是“矩阵实验室” (matrix laboratoy)的缩写，它是一种以矩阵运算为基础的交互式程序语言，这种针对科学计算、工程计算和绘图的需求。与其他计算机语言相比，其特点是见解和智能化，适应科技专业人员的思维方式和书写习惯，使得编程和调试效率大大提高。它用解释方式工作，键入程序立即得出结果，人机交互性能好，为科技人员所乐于接受。特别是它可适用于多种平台，并且随计算机硬、软件的更新而及时升级。因此，MATLAB语言在国内外的大学工学院中，特别是数值计算用的最频繁的电子信息类学科中，已成为每个学生都应掌握的工具了。它大大提高了课程教学、接解题作业、分析研究的效。4.1.2汇编语言简介汇编语言(Assembly Language)是面向机器的程序设计语言。在汇编语言中，用助记符(Memoni)代替操作码，用地址符号(Symbol)或标号(Label)代替地址妈。这样用符号代替机器语盲的二进制码，就把机器语音变成了汇编语言，于是汇编语言亦称为符号语言。使用汇编语言编写的程序，机器不能直接识别，要由一种程序将汇编语言翻译成机器语言，这种起翻译作用的程序叫汇编程序，汇编程序是系统软件中语言处理系统软件。汇编语言把汇编程序翻译成机器语言的过程称为汇编。汇编语言比机器语言易于读写、易于调试和修改，同时也具有机器语言执行速度快，占内存空间少等优点，但在编写复杂程序时具有明显的局限性，汇编语言依赖于具体的机型，不能通用，也不能在不同机型之间移植。汇编语言的特：汇编语言由于采用了助记符号来编写程序，比用机器语言的二进制代码编程要方便些，在一定程度上简化了编程过程。汇编语言的特点是用符号代替了机器指令代码，而且助记符与指令代码一一对应，基本保留了机器语言的灵活性。使用汇编语言能面向机器并较好地发挥机器的特性，得到质量较高的程序。汇编语言是面向具体机型的，它离不开具体计算机的指令系统，因此，对于不同型号的计算机，有着不同的结构的汇编语言，而且，对于同一问题所编制的汇编语言程序在不同种类的计算机间是互不相通的。汇编语言中由于使用了助记符号，用汇编语言编制的程序输入计算机，计算机不能象用机器语言编写的程序一样直接识别和执行，必须通过预先放入计算机的汇编程序的加工和翻译，才能变成能够被计算机识别和处理的二进制代码程序。用汇编语言等非机器语言书写好的符号程序称为源程序，运行时汇编程序要将源程序翻译成目标程序。目标程序是机器语言程序，它一经被安置在内存的预定位置上，就能被计算机的CPU处理和执行。汇编语言像机器指令一样，是硬件操作的控制信息，因而仍然是面向机器的语言，使用起来还是比较繁琐费时，通用性也差。但是，汇编语言用来编制系统软件和过程控制软件，其目标程序占用内存空间少，运行速度快，有着高级语言不可替代的用途。4.2(128，120)扩展汉民循环码编码过程的实现取(127，120)汉民循环码的生