纠错算法

Ⅰ FEC的前向纠错

FEC：Forward Error Correction，前向纠错。
是一种数据编码技术，传输中检错由接收方进行验证，在FEC方式中，接收端不但能发现差错，而且能确定二进制码元发生错误的位置，从而加以纠正。FEC方式必须使用纠错码。发现错误无须通知发送方重发。区别于ARQ方式。
在目前的数字通信系统中，前向纠错技术FEC(Forward Error Correction)得到了广泛的应用。这一技术的产生和发展源于通信系统本身的需求，在工程实践中并不存在理想的数字信道，信号在各种媒体的传输过程中总会产生畸变和非等时时延，对数字信号来说就意味着产生误码和抖动，而抖动的最终效果也反映在系统的误码上。 FEC编解码可以用硬件实现也可用软件实现，采用FEC技术可较好地改善误码性能。
前向纠错是指信号在被传输之前预先对其进行按一定的格式处理，在接收端则按规定的算法进行解码以达到找出错码并纠错的目的。现代纠错码技术是由一些对通信系统感兴趣的数学家们和对数学有着深厚功底的工程师们在近50多年中发展起来的。1948年，法国数学家香农（Shannon）发表了现代信息理论奠基性的文章《通信系统数学理论》。汉明（Hamming）于1949年提出了可纠正单个随机差错的汉明码。普朗基（Prange）于1957年提出了循环码的概念，随后，Hoopueghem,Bose和Chaudhum于1960年发现了BCH码，稍后，里得(Reed)和所罗门(Solomon)提出了ReedSolomon(RS)编码，这实际上是一种改进了的BCH码，现代通信采用的各种新技术，如MMDS多点对多点分配业务、LMDS本地多点分配业务、蓝牙技术、高速DH等要求信道编码纠错能力更高效率、更高运算速度、更快，这就导致了各种动态编码方案的出现并在工程中得到广泛运用，时至今日，信息理论仍是当前最活跃的研究领域之一。

Ⅱ 纠错编码的分类

1．自动请求重发（ARQ）
采用这种方法时，当接收端检测到所接收的信息有错以后，通过反向信道向发送端要求重发原信息，直到接收端认可为止，从而达到纠正误码的目的。这种方法的优点是纠错编解码设备简单，但需要具备反向信道，且实时性较差。
2．前向纠错（FEC）
前向差错控制编码的基本做法是在发送端被传输的信息序列上附加一些监督码元，这些多余的监督码元与信息码元之间以某种确定的规则相互关联(约束)。接收端按照既定的关联规则检验信息码元与监督码元之间的关系，一旦传输过程中发生差错，则信息码元与监督码元之间的关系将受到破坏，从而可以发现错误，乃至纠正错误。具体说就是接收端对接收到的码字施加一定的算法，从而发现误码并予以纠正。这种方式的优点是不需要反向信道，纠错编解码的实时性较好。缺点是纠错编解码较复杂，且纠错能力有限。
3．混合纠错（HEC）
该方式是前两种方式的结合。接收端对所接收的码流中少量的误码可通过前向纠错方式进行自动纠正；而对超过前向纠正能力的误码，但能检测出来，则接收端通过反向信道请求发端重发，以此对错码加以纠正。
以上三种差错控制方式可以用图1来概括。无论采用那种纠错方法，都要在原信息中插入冗余码才能实现纠错或检错。由于前向纠错方法简单，不需要反向信道，且能实时实现。因此在实时图像通信系统中，多采用前向纠错的方法来进行对图像信号和系统控制信号的差错控制。
4．BCH纠错编码
实测表明，对图像信息进行了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和比特交织

Ⅲ 纠错码的基本原理和性能参数

纠错码能够检错或纠错，主要是靠码字之间有较大的差别。这可用码字之间的汉明距离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年代分组码的理论获得发展以来，分组码在数字通信和数据存储系统中已被广泛应用。
分组码的码长n和码字个数M是一个码的主要构造参数。码长为n的码中所有码字的位数均为n；若要用一个码传送k比特信息，则码字的个数M必须满足。典型的分组码是由k位信息位和r位监督位组成的，这样构成的码一般称为系统码。
分组码中应用最广的线性分组码。线性分组码中的M个码字之间具有一定线性约束关系，即这些码字总体构成了n维线性空间的一个k维子空间。称此k维子空间为（n，k）线性分组码。线性系统码的特点是每个码字的前k位均由这个码字所对应的信息位组成，并通过对这k位信息位的线性运算得到后面n—k是位监督位。
线性分组码中应用最广的是循环码，循环码的主要特征是任何码字在循环移位后个码字。循环码的优点在于其编码和解码手续比一般线性码简单，因而易于在设备上实现。在循环码中，码字可表示为多项式。循环码的码字多项式都可表示成为循环码的生成多项式与这个码字所代表的信息多项式的乘积，即，因此一个循环码可以通过给出其生成多项式来规定。常用的循环码有BCH码和RS码。
网格码有多种描述方法，网格图是常用方法之一，它能表示出编码过程。一个码率为1/2、包含四种状态的网格码的网格图如图所示。图1中00，01，10，11表示编码器所具有的四种状态，以“·”示出，从每一状态出发都存在两条支路，位于上面的一条支路对应于编码器输入为“0”的情况，位于下面的一条支路对应于编码器输入为“1”的情况，而每一支路上所列出的两个二进位码则表示相应的编码输出。因而可知，编码输出不仅决定于编码器的当前输入，还决定于编码器的状态，例如在图中从“00”状态出发；，若输入的二进制数据序列为1011，则编码器的状态转移过程为00→01→10→01→11，而相应的编码输出序列为11010010。在网格图中任意两条从同一状态出发；，经不同的状态转移过程后又归于另一相同状态（该状态也可与初始状态相同）的路径间的距离的最小值称为码的自由距离。如该图中的为5。对于卷积码来说，的计算可简化为始于且终于零状态的非全零路径与全零路径间距离的最小值。是表征网格码纠错能力的重要参数。维特比算法是广泛采用的网格码的译码方法。由于网格码的状态越多，译码越复杂，所以状态个数是度量网格码译码复杂性的重要参数。一般说来可以通过增大译码复杂性来增加，从而提高码的纠错能力。
BCH码、网格码已被广泛地应用于移动通信、卫星通信和频带数据传输中。RS码也被广泛应用于光盘的存储中。
大多数纠错码是设计来纠随机误码的，可以通过交织的方法使它适用于对突发误码的纠错。交织是一种使得集中出现的突发误码在解码时进行分散化的措施，从而使其不超出纠错码的纠错能力范围。 卷积码不对信息序列进行分组编码，它的校验元不仅与当前的信息元有关，而且同以前有限时间段上的信息元有关。卷积码在编码方法上尚未找到像分组码那样有效的数学工具和系统的理论。但在译码方面，不论在理论上还是实用上都超过了分组码，因而在差错控制和数据压缩系统中得到广泛应用。