2017-03-15 15:38:17

纠错码 免费编辑 添加义项名

B 添加义项
?
义项指多义词的不同概念,如李娜的义项:网球运动员、歌手等;非诚勿扰的义项:冯小刚执导电影、江苏卫视交友节目等。 查看详细规范>>
所属类别 :
图书
图书
编辑分类
纠错码(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.普勒齐引入了循环码的概念。1959~1960年出现了BCH码,引进有限域的概念,解决了循环码的构造和性能估计等基本问题。后来成为线性分组码中最重要的一类码。它能纠正多个错误,且在实用范围内接近信道编码定理所指出的误码率值。但当n增大时,其误码率不能呈指数下降。BCH码的译码问题是W.W.彼得森解决的;钱天闻则提供了一种系统地搜索根的方法。1967年,E.R.伯利坎普提出一种迭代算法,大大简化了译码,使纠错码趋于实用。1970年В.Д.戈帕提出一种线性分组码的构造方法,原则上它可以达到吉尔伯特限,实现了理论上预期的目标。但至今仍未解决如何具体构造这种码的问题。

卷积码最早由P.伊莱亚斯于1955年提出。它的纠错能力较强,设备复杂程度与分组码大体相当。首先获得成功的译码方法是序列译码。1967年A.J.维特比提出的译码算法,能较好地按最大似然准则译码,且在许多领域中均可应用。卷积码还可用代数方法译码。它的设备虽较简单,但性能较差。卷积码在理论上不如分组码成熟,所用的工具也比较多样,尚缺乏系统的、统一的方法处理。

分组码和卷积码不但可以用来纠正独立错误,而且可以用来恢复删除错误和纠正突发错误。如分组码中有里德-索洛蒙码,法尔码等;卷积码中有岩垂码及扩散卷积码等。

为了实现低的误码率,根据式(1),要求码长n较大。但已知的大多数码,当n变大时不是性能欠佳或者难以构造,就是译码过分复杂,不容易实现。但是,可以利用好的码进行级连,以得到性能更好的码。级连码的内码和外码,用分组码和卷积码都可以。这在深空通信中应用较多。

折叠 编辑本段 基本原理

纠错码能够检错或纠错,主要是靠码字之间有较大的差别。这可用码字之间的汉明距离d(x,y)来衡量。它的定义为码字x与y之间的对应位取不同值的码元个数。一种纠错码的最小距离d定义为该种码中任两个码字之间的距离的最小值。一种码要能发现e个错误,它的最小距离d应不小于e+1。若要能纠正t个错误,则d应不小于2t+1。一个码字中非零码元的个数,称为此码字的汉明重量。一种码中非零码字的重量的最小值,称为该码的最小重量。对线性码来说,一种码的最小重量与其最小距离在数值上是相等的。

在构造线性码时,数字上是从n维空间中选一k维子空间,且使此子空间内各非零码字的重量尽可能大。当构造循环码时,可进一步将每一码字看成一多项式,将整个码看成是多项式环中的理想,这一理想是主理想,故可由生成多项式决定;而多项式完全可由它的根规定。这样,就容易对码进行构造和分析。这是BCH码等循环码构造的出发点。一般地说,构造一种码时,均设法将它与某种代数结构相联系,以便对它进行描述,进而推导它的性质,估计它的性能和给出它的译码方法。若一种码的码长为n,码字数为M,或信息位为h,以及最小距离为d,则可把此码记作【n,M,d】码。若此码为线性码,常简记作(n,k)或(n,k,d)码。人们还常用R=log2M/n表示码的信息率或简称码率,单位为比特/码元。R越大,则每个码元所携带的信息量越大,编码效率越高。

折叠 实现

纠错码实现中最复杂的部分是译码。它是纠错码能否应用的关键。根据式(1),采用的码长n越大,则误码率越小。但n越大,编译码设备也越复杂,且延迟也越大。人们希望找到的译码方法是:误码率随码长n的增加按指数规律下降;译码的复杂程度随码长n的增加接近线性地增加;译码的计算量则与码长n基本无关。可惜,已经找到的码能满足这样要求的很少。不过由于大规模集成电路的发展,即使应用比较复杂的但性能良好的码,成本也并不太高。因此,纠错码的应用越来越广泛。

纠错码传输的都是数字信号。这既可用硬件实现,也可用软件实现。前者主要用各种数字电路,主要是采用大规模集成电路。软件实现特别适合计算机通信网等场合。因为这时可以直接利用网中的计算机进行编码和译码,不需要另加专用设备。硬件实现的速度较高,比软件可快几个数量级。

在传信率一定的情况下,如果采用纠错码提高可靠性,要求信道的传输率增加,带宽加大。因此,纠错码主要用于功率受限制而带宽较大的信道,如卫星、散射等系统中。纠错码还用在一些可靠性要求较高,但设备或器件的可靠性较差,而余量较大的场合,如磁带、磁盘和半导体存储器等。

在分组码的研究中,谱分析的方法受到人们的重视。纠同步错误码、算术码、不对称码、不等错误纠正码等,也得到较多的研究。

折叠 分组码

分组码是对信源待发的信息序列进行分组(每组K位)编码,它的校验位仅同本组的信息位有关。自20世纪50年代分组码的理论获得发展以来,分组码在数字通信和数据存储系统中已被广泛应用。

折叠 卷积码

卷积码不对信息序列进行分组编码,它的校验元不仅与当前的信息元有关,而且同以前有限时间段上的信息元有关。卷积码在编码方法上尚未找到像分组码那样有效的数学工具和系统的理论。但在译码方面,不论在理论上还是实用上都超过了分组码,因而在差错控制和数据压缩系统中得到广泛应用。

阅读全文

热点资讯