企业网站建设的目的有哪些,珠海服务好的网站建设,电脑怎么创建网站,祥云平台网站建设纠错码(error correcting code)#xff0c;在传输过程中发生错误后能在收端自行发现或纠正的码。仅用来发现错误的码一般常称为检错码。为使一种码具有检错或纠错能力#xff0c;须对原码字增加多余的码元#xff0c;以扩大码字之间的差别 #xff0c;即把原码字按某种规则…纠错码(error correcting code)在传输过程中发生错误后能在收端自行发现或纠正的码。仅用来发现错误的码一般常称为检错码。为使一种码具有检错或纠错能力须对原码字增加多余的码元以扩大码字之间的差别 即把原码字按某种规则变成有一定剩余度(见信源编码)的码字并使每个码字的码之间有一定的关系。关系的建立称为编码。码字到达收端后可以根据编码规则是否满足以判定有无错误。当不能满足时按一定规则确定错误所在位置并予以纠正。纠错并恢复原码字的过程称为译码。检错码与其他手段结合使用可以纠错。中文名纠错码外文名error correcting code实 质在收端自行发现或纠正的码别 名应用学科计算机、通信纠错码简介语音纠错码(error correcting code) 是在接收端能自动地纠正数据传输中所发生差错的码。纠错码的基本思路是在所有的由发送符号组成的序列中仅挑出其中一部分做为信息的代表向信道发送并使得所挑出的这些序列之间有尽可能多的差异。每个被挑出的允许发送的序列被称为一个码字而码字的总合称为码。在发送端把信息变换成码字的过程称为编码在接收端从接收到的信号判定所发码字、从而恢复信息的过程称为解码(或译码)。在解码时若收到的信号不是码中的一个码字则可以肯定在传输中出现了差错从而着手对差错进行纠正。纠错的方法是找到与接收到的信号最接近的码字并将其判定为发送信号。一般采用“距离”来度量信号间的接近程度一种常用的“距离”称为汉明距离它被定义为两码字间对应位不同的个数总和。一个给定码其全部码字两两之间距离的最小值被称为这个码的码距。码距是一个码纠错能力的重要参数例如在汉明距离下若接收到的信号出错的位数不多于码距的一半则接收端总能正确地恢复所发送的码字从而正确地恢复所发送的信息。纠错编码又称信道编码它与信源编码是信息传输的两个方面。它们之间存在对偶的关系。应用信道译码直接对一些自然信息进行处理可以去掉剩余度以达到压缩数据的目的。为了使一种码具有检错或纠错能力必须对原码字增加多余的码元以扩大码字之间的差别使一个码字在一定数目内的码元上发生错误时不致错成另一个码字。准确地说即把原码字按某种规则变成有一定剩余度的码字并使每个码字的码元间有一定的关系。关系的建立称为编码。码字到达收端后用编码时所用的规则去检验。如果没有错误则原规则一定满足否则就不满足。由此可以根据编码规则是否满足以判定有无错误。当不能满足时在可纠能力之内按一定的规则确定错误所在的位置并予以纠正。纠错并恢复原码字的过程称为译码码元间的关系为线性时称为线性码否则称为非线性码。检错码与其他手段结合使用可以纠错。检错反馈重发系统(ARQ系统)就是一例。在构造纠错码时将输入信息分成k位一组以进行编码。若编出的校验位仅与本组的信息位有关则称这样的码为分组码。若不仅与本组的k个信息位有关而且与前若干组的信息位有关则称为格码。这种码之所以称为格码是因为用图形分析时它象篱笆或格架。线性格码在运算时为卷积运算所以叫卷积码。纠错码发展过程C.E.仙农在1948年发表在《通信的数学理论》一文中的信道编码定理指出只要采用适当的纠错码就可在多类信道上传输消息其误码率pe可以任意小 (1)式中n为码长Er(R)为信息率R的函数,与信道有关。当R小于信道容量C时,Er(R)为正值。可惜的是这一定理仅仅指出理论上可以达到的目标而未能给出构造性的实现方法。自仙农的论文发表以来人们经过持续不懈的努力已找到多种好码可以满足许多实用要求。但在理论上仍存在一些问题未能解决。纠错码汉明码R.W.汉明于1950年首先给出可以纠正一个独立错误的线性分组码──汉明码。差不多与此同时E.戈雷给出一种可以纠正三个错误的完备码。完备码虽然十分罕见但有较大实用意义。1954年D.E.莫勒提出一种能纠正多个错误的码I.S.里德则立即给出它的译码方法用的是择多判决法这种码常称为RM码。1957年E.普勒齐引入了循环码的概念。19591960年出现了BCH码,引进有限域的概念解决了循环码的构造和性能估计等基本问题。后来成为线性分组码中最重要的一类码。它能纠正多个错误且在实用范围内接近信道编码定理所指出的误码率值。但当n增大时其误码率不能呈指数下降。BCH码的译码问题是W.W.彼得森解决的;钱天闻则提供了一种系统地搜索根的方法。1967年E.R.伯利坎普提出一种迭代算法大大简化了译码使纠错码趋于实用。1970年В.Д.戈帕提出一种线性分组码的构造方法原则上它可以达到吉尔伯特限实现了理论上预期的目标。但至今仍未解决如何具体构造这种码的问题。卷积码最早由P.伊莱亚斯于1955年提出。它的纠错能力较强设备复杂程度与分组码大体相当。首先获得成功的译码方法是序列译码。1967年A.J.维特比提出的译码算法能较好地按最大似然准则译码且在许多领域中均可应用。卷积码还可用代数方法译码。它的设备虽较简单但性能较差。卷积码在理论上不如分组码成熟所用的工具也比较多样尚缺乏系统的、统一的方法处理。分组码和卷积码不但可以用来纠正独立错误而且可以用来恢复删除错误和纠正突发错误。如分组码中有里德-索洛蒙码,法尔码等卷积码中有岩垂码及扩散卷积码等。为了实现低的误码率根据式(1)要求码长n较大。但已知的大多数码当n变大时不是性能欠佳或者难以构造就是译码过分复杂不容易实现。但是可以利用好的码进行级连以得到性能更好的码。级连码的内码和外码用分组码和卷积码都可以。这在深空通信中应用较多。纠错码基本原理和性能参数语音纠错码能够检错或纠错主要是靠码字之间有较大的差别。这可用码字之间的汉明距离d(xy)来衡量。它的定义为码字x与y之间的对应位取不同值的码元个数。一种纠错码的最小距离d定义为该种码中任两个码字之间的距离的最小值。一种码要能发现e个错误,它的最小距离d应不小于e1。若要能纠正t个错误则d应不小于2t1。一个码字中非零码元的个数称为此码字的汉明重量。一种码中非零码字的重量的最小值称为该码的最小重量。对线性码来说一种码的最小重量与其最小距离在数值上是相等的。在构造线性码时数字上是从n维空间中选一k维子空间且使此子空间内各非零码字的重量尽可能大。当构造循环码时,可进一步将每一码字看成一多项式,将整个码看成是多项式环中的理想,这一理想是主理想,故可由生成多项式决定而多项式完全可由它的根规定。这样,就容易对码进行构造和分析。这是BCH码等循环码构造的出发点。一般地说构造一种码时均设法将它与某种代数结构相联系以便对它进行描述进而推导它的性质估计它的性能和给出它的译码方法。若一种码的码长为n码字数为M,或信息位为h,以及最小距离为d则可把此码记作【n,M,d】码。若此码为线性码常简记作(nk)或(n,k,d)码。人们还常用Rlog2M/n表示码的信息率或简称码率,单位为比特/码元。R越大,则每个码元所携带的信息量越大编码效率越高。纠错码实现纠错码实现中最复杂的部分是译码。它是纠错码能否应用的关键。根据式(1),采用的码长n越大,则误码率越小。但n越大编译码设备也越复杂,且延迟也越大。人们希望找到的译码方法是:误码率随码长n的增加按指数规律下降;译码的复杂程度随码长n的增加接近线性地增加译码的计算量则与码长n基本无关。可惜已经找到的码能满足这样要求的很少。不过由于大规模集成电路的发展即使应用比较复杂的但性能良好的码成本也并不太高。因此纠错码的应用越来越广泛。纠错码传输的都是数字信号。这既可用硬件实现也可用软件实现。前者主要用各种数字电路主要是采用大规模集成电路。软件实现特别适合计算机通信网等场合。因为这时可以直接利用网中的计算机进行编码和译码不需要另加专用设备。硬件实现的速度较高比软件可快几个数量级。在传信率一定的情况下如果采用纠错码提高可靠性要求信道的传输率增加带宽加大。因此纠错码主要用于功率受限制而带宽较大的信道如卫星、散射等系统中。纠错码还用在一些可靠性要求较高但设备或器件的可靠性较差而余量较大的场合如磁带、磁盘和半导体存储器等。在分组码的研究中谱分析的方法受到人们的重视。纠同步错误码、算术码、不对称码、不等错误纠正码等也得到较多的研究。纠错码分组码分组码是对信源待发的信息序列进行分组(每组K位)编码它的校验位仅同本组的信息位有关。自20世纪50年代分组码的理论获得发展以来分组码在数字通信和数据存储系统中已被广泛应用。分组码的码长n和码字个数M是一个码的主要构造参数。码长为n的码中所有码字的位数均为n若要用一个码传送k比特信息则码字的个数M必须满足。典型的分组码是由k位信息位和r位监督位组成的这样构成的码一般称为系统码。分组码中应用最广的线性分组码。线性分组码中的M个码字之间具有一定线性约束关系即这些码字总体构成了n维线性空间的一个k维子空间。称此k维子空间为(nk)线性分组码。线性系统码的特点是每个码字的前k位均由这个码字所对应的信息位组成并通过对这k位信息位的线性运算得到后面n—k是位监督位。线性分组码中应用最广的是循环码循环码的主要特征是任何码字在循环移位后个码字。循环码的优点在于其编码和解码手续比一般线性码简单因而易于在设备上实现。在循环码中码字可表示为多项式。循环码的码字多项式都可表示成为循环码的生成多项式与这个码字所代表的信息多项式的乘积即因此一个循环码可以通过给出其生成多项式来规定。常用的循环码有BCH码和RS码。图1 码率为1/2、四种状态的网格码的网格图网格码有多种描述方法网格图是常用方法之一它能表示出编码过程。一个码率为1/2、包含四种状态的网格码的网格图如图所示。图1中00011011表示编码器所具有的四种状态以“·”示出从每一状态出发都存在两条支路位于上面的一条支路对应于编码器输入为“0”的情况位于下面的一条支路对应于编码器输入为“1”的情况而每一支路上所列出的两个二进位码则表示相应的编码输出。因而可知编码输出不仅决定于编码器的当前输入还决定于编码器的状态例如在图中从“00”状态出发若输入的二进制数据序列为1011则编码器的状态转移过程为00→01→10→01→11而相应的编码输出序列为11010010。在网格图中任意两条从同一状态出发经不同的状态转移过程后又归于另一相同状态(该状态也可与初始状态相同)的路径间的距离的最小值称为码的自由距离。如该图中的为5。对于卷积码来说的计算可简化为始于且终于零状态的非全零路径与全零路径间距离的最小值。是表征网格码纠错能力的重要参数。维特比算法是广泛采用的网格码的译码方法。由于网格码的状态越多译码越复杂所以状态个数是度量网格码译码复杂性的重要参数。一般说来可以通过增大译码复杂性来增加从而提高码的纠错能力。BCH码、网格码已被广泛地应用于移动通信、卫星通信和频带数据传输中。RS码也被广泛应用于光盘的存储中。大多数纠错码是设计来纠随机误码的可以通过交织的方法使它适用于对突发误码的纠错。交织是一种使得集中出现的突发误码在解码时进行分散化的措施从而使其不超出纠错码的纠错能力范围。纠错码卷积码卷积码不对信息序列进行分组编码它的校验元不仅与当前的信息元有关而且同以前有限时间段上的信息元有关。卷积码在编码方法上尚未找到像分组码那样有效的数学工具和系统的理论。但在译码方面不论在理论上还是实用上都超过了分组码因而在差错控制和数据压缩系统中得到广泛应用。
