纠错编码又称之为信道编码,它已成功地应用于各种通信系统中,在图像通信中也得到日益广泛的应用。在数据传输中,主要有三种误码控制的方法,即自动请求重发(ARQ)、前向纠错(FEC)和混合纠错(HEC)方式。
原理
在传输过程中发生错误后能在收端自行发现或纠正的码。仅用来发现错误的码一般常称为
检错码。为使一种码具有检错或纠错能力,须对原码字增加多余的码元,以扩大码字之间的差别 ,即把原码字按某种规则变成有一定剩余度(见信源编码)的码字,并使每个码字的码之间有一定的关系。关系的建立称为编码。码字到达收端后,可以根据编码规则是否满足以判定有无错误。当不能满足时,按一定规则确定错误所在位置并予以纠正。纠错并恢复原码字的过程称为译码。检错码与其他手段结合使用,可以纠错。发表论文指出,只要采用适当的纠错码,就可在多类信道上传输消息。自仙农的论文发表以来,人们经过持续不懈的努力已经找到多种好码,可以满足许多实用要求。但在理论上,仍存在一些问题未能解决。纠错码能够检错或纠错,主要是靠码字之间有较大的差别。纠错码实现中最复杂的部分是译码,它是纠错码能否应用的关键。纠错码传输的都是数字信号。这既可用硬件实现,也可用软件实现。
纠错能力、编码效率和解码复杂性是衡量一个纠错码好坏的重要参数。
在构造纠错码时,将输入信息分成k位一组进行编码。若编出的n位长码仅与本组的位信息k位有关,则称这样的码为分组码。由于这时用n位符号传送了k位信息,所以编码效率(码率)为。若编出的位长码不仅与本组的个信息位有关,而且与其前面若干组的信息位有关,则称为网格码,这种码之所以称为网格码是因为用图形分析时其图形像网格或篱笆。线性网格码在编码运算时为卷积运算,所以又叫做卷积码。
分组码的码长和码字个数M是一个码的主要构造参数。码长为的码中所有码字的位数均为;若要用一个码传送比特信息,则码字的个数M必须满足。典型的分组码是由位信息位和r位监督位组成的,这样构成的码一般称为系统码。
分组码中应用最广的线性分组码。线性分组码中的M个码字之间具有一定线性约束关系,即这些码字总体构成了n维线性空间的一个k维子空间。称此k维子空间为(n,k)线性分组码。线性系统码的特点是每个码字的前k位均由这个码字所对应的信息位组成,并通过对这k位信息位的线性运算得到后面n—k是位监督位。
线性分组码中应用最广的是循环码,循环码的主要特征是任何码字在循环移位后个码字。循环码的优点在于其编码和解码手续比一般线性码简单,因而易于在设备上实现。在循环码中,码字可表示为多项式。循环码的码字多项式都可表示成为循环码的生成多项式与这个码字所代表的信息多项式的乘积,即,因此一个循环码可以通过给出其生成多项式来规定。常用的循环码有BCH码和RS码。
码率为1/2、包含四种状态的网格码的网格图
网格码有多种描述方法,网格图是常用方法之一,它能表示出编码过程。一个码率为1/2、包含四种状态的网格码的网格图如图所示。图中00,01,10,11表示编码器所具有的四种状态,以“·”示出,从每一状态出发都存在两条支路,位于上面的一条支路对应于编码器输入为“0”的情况,位于下面的一条支路对应于编码器输入为“1”的情况,而每一支路上所列出的两个二进位码则表示相应的编码输出。因而可知,编码输出不仅决定于编码器的当前输入,还决定于编码器的状态,例如在图中从“00”状态出发;,若输入的二进制数据序列为1011,则编码器的状态转移过程为00→01→10→01→11,而相应的编码输出序列为11010010。在网格图中任意两条从同一状态出发;,经不同的状态转移过程后又归于另一相同状态(该状态也可与初始状态相同)的路径间的距离的最小值称为码的自由距离。如该图中的为5。对于卷积码来说,的计算可简化为始于且终于零状态的非全零路径与全零路径间距离的最小值。是表征网格码纠错能力的重要参数。维特比算法是广泛采用的网格码的译码方法。由于网格码的状态越多,译码越复杂,所以状态个数是度量网格码译码复杂性的重要参数。一般说来可以通过增大译码复杂性来增加,从而提高码的纠错能力。
BCH码、网格码已被广泛地应用于移动通信、卫星通信和频带数据传输中。RS码也被广泛应用于光盘的存储中。
大多数纠错码是设计来纠随机误码的,可以通过交织的方法使它适用于对突发误码的纠错。交织是一种使得集中出现的突发误码在解码时进行分散化的措施,从而使其不超出纠错码的纠错能力范围。
分类
采用这种方法时,当接收端检测到所接收的信息有错以后,通过反向信道向发送端要求重发原信息,直到接收端认可为止,从而达到纠正误码的目的。这种方法的优点是纠错编解码设备简单,但需要具备反向信道,且实时性较差。
前向差错控制编码的基本做法是在发送端被传输的信息序列上附加一些监督码元,这些多余的监督码元与信息码元之间以某种确定的规则相互关联(约束)。接收端按照既定的关联规则检验信息码元与监督码元之间的关系,一旦传输过程中发生差错,则信息码元与监督码元之间的关系将受到破坏,从而可以发现错误,乃至纠正错误。具体说就是接收端对接收到的码字施加一定的算法,从而发现误码并予以纠正。这种方式的优点是不需要反向信道,纠错编解码的实时性较好。缺点是纠错编解码较复杂,且纠错能力有限。
该方式是前两种方式的结合。接收端对所接收的码流中少量的误码可通过前向纠错方式进行自动纠正;而对超过前向纠正能力的误码,但能检测出来,则接收端通过反向信道请求发端重发,以此对错码加以纠正。
以上三种差错控制方式可以用图1来概括。无论采用那种纠错方法,都要在原信息中插入冗余码才能实现纠错或检错。由于前向纠错方法简单,不需要反向信道,且能实时实现。因此在实时图像通信系统中,多采用前向纠错的方法来进行对图像信号和系统控制信号的差错控制。
实测表明,对图像信息进行了BCH(511,493)的纠错处理,通过增加4%的冗余度信息可以将信道误码率由10-6改善到10-9,从而确保了图像信息的可靠传输。
纠错码的实现框图如图2所示,图像数据首先被分成一个个的493比特的数据组,组与组之间空18比特,有待于插入校验位。图像数据组进入BCH纠错编码单元,按照上述的BCH(511,493)的算法,算出18位校验位。延时单元主要的目的就是补偿BCH编码所花费的时间,使得经编码输出的校验位和相应的数据刚好对齐,然后将两者复合起来形成一路经BCH纠错编码的图像信号送至多路复用单元和音频、数据信号进行多路复用。
图1差错控制方式
图2纠错编码框图
在接收端,解码器对图像进行BCH译码。在译码电路中,译码器根据18位校验信号对相应的493位图像信号进行验算,如果图像数据中有一位随机误码,则通过这样的校验可以将它们自动纠正。如果有2位,则可以将它检测出来。
5.比特交织
在实际应用中,还可以将比特交织和前向纠错相结合,以期进一步提高纠错能力,如图3所示。FEC和编码交织在分组前完成,在接收端通过反交织可以使突发错误分散开来,这样,具有纠随机错误能力的纠错码能纠突发错误,这在无线或分组视频通信中特别有效。
图3FEC和比特交织