原创一种新的前向纠错算法

 2008-11-22 00:02  4061 3 4 分类: 通信

一、纠错码的历史<?xml:namespace prefix = o ns = "urn:schemas-microsoft-com:office:office" />

自1948年香农首次阐明了在有扰信道中实现可靠通信的方法以来，纠错码已经有60年的历史，先后出现了线性分组码、循环码、卷积码等多种编码方法，相应地也提出了许多有效的译码方法：门限译码、迭代译码、软判决译码、Viterbi译码、Turbo码等，这些方法成功应用于很多领域，如通信、计算机、超大规模集成电路、加密、神经元网络、生物识别。可以说，随着科学的进步和实际需要，纠错码理论必将进一步发展，其应用范围必将进一步扩大。

二、差错控制系统和纠错码的分类

在数字通信系统中，利用纠错码或检错码进行差错控制的方式大致有以下几种：

反馈重传方式（ARQ）:发送端发出能够发现错误的码，接收端判决收到的码序列中有无错误产生，通过反馈新到将判决结果告诉发端。发端根据这些结果，重新发送接收端认为有错误的信息，直至接收端认为正确接收为止。

很明显，这种方式必须有一反馈通道，控制电路复杂，传输信息的连贯性和实时性较差。难以用于广播系统。当信道干扰增大时，整个系统可能处于重发的循环中，通信效率降低，甚至不能通信。不大适用于严格实时传输系统。

反馈校验方式（IRQ）：接收端将收到的信息原封不动地转发回发端，并与原发送码序列相比较，如果发现错误，则发端再进行重发。

这种方式也需要有一反馈通道。因为每一信息都发送至少两次，传输效率比较低。当信道干扰增大时，整个系统可能处于重发的循环中，通信效率降低，甚至不能通信。不大适用于严格实时传输系统。

前向纠错方式（FEC）：接收端不能能在收到的码序列中发现有错误，而且还能纠正。

这种方法不需要反向通道，也不存在由于反复重发而延误的时间，实时性好。能进行一一个用户对多个用户的广播通信，控制电路简单，但纠错设备比较复杂。

由于前向纠错算法的能力较强，特别适用于深空、军事、无线移动通信等恶劣环境下的应用。随着编码理论的发展和大规模集成电路成本的不断降低，译码设备可以做得成本越来越低，因而在实际的数字通信中逐渐得到广泛应用。惟思泰瑞公司就是顺应了这个趋势，提出了W算法理论，大大降低了前向纠错译码电路的成本，极大地提高了纠错能力，以期推进我国通信理论的发展。

混合纠错方式（HEC）：发送端发送的码不仅能够被检测出错误，而且还具有一定的纠错能力。接收端收到码序列后，首先检测错误情况，如果在纠错能力以内，则自动进行纠错。如果错误过多，超过了纠错能力，但能检测出来，则接收端通过反馈新到，要求发送端重新传送有错的码序列。

这种方式也需要反向通道，难以用于广播系统。当信道干扰增大时，整个系统可能处于重发的循环中，通信效率降低，甚至不能通信。不大适用于严格实时传输系统。

2.1线形分组码

若编码的规则仅仅局限于本码组之内，即本组码的监督元仅和本码组有关，则称之为分组码；若本组码的监督元不仅和本码组的信息元有关，而且还和相邻的前N-1个信息元有关，则这类码称为卷积码。

线性分组码的构成方式是把信息序列分成每k个码元一段，并由这k个码元按一定规则产生r 个校验位，组成长度为n=k+r的码字，用(n，k)表示。信息码元与校验位之间为线性关系。

在香农的信道编码定理中指出，仅当分组码的n趋于无穷大时，译码错误概率才能任意地接近于零。到目前为止，如何具体构造Shannon码仍是一个没有解决的问题。

2.2循环码

循环码是一类最重要的线性码。

循环码具有严谨的代数结构，其性能易于分析，特别是目前已发现的大部分线性码与循环码有密切关系，它们中的大部分码都可归结于循环码。

循环码具有循环特性，编译码电路，特别是编码电路易于实现。

BCH码是循环码中具有代表性的一类码。1959年由霍昆格姆等提出了纠正多个随机错误的循环码——BCH码的构造方法。BCH码是目前为止所发现的一类很好的线性纠错码。1960年彼得逊从理论上解决了二进制BCH码的译码算法。由于BCH码性能优良，译码设备也不太复杂，使得它在实际使用中受到工程技术人员的欢迎。得以广泛应用。

2.3卷积码

<?xml:namespace prefix = st1 ns = "urn:schemas-microsoft-com:office:smarttags" />2.3.1历史

卷积码是1955年由爱里斯提出的，从信道编码定理看，卷积码是一种非常有前途，能达到信道编码定理所提出的码类。由于卷积码各组之间相互有关，因此在卷积码的分析过程中，至今仍未找到有效的数学工具，以至于性能分析比较困难，1967年有Viterbi算法，这是基于码的网图基础上的一种最大似然译码算法，是一种很好的概率译码方法。

Shannon理论证明，随机码是好码，但是译码太复杂，直到1993年，Turbo码的发现，才较好的解决了这一问题。

目前Turbo码和Viterbi译码在前向纠错中应用最为广泛，已经成为3GPP的三个国际标准的传输信道的标准。

2.3.2译码算法种类

卷积译码的算法主要分为两大类：门限译码和概率译码。

2.3.2.1大数逻辑译码

大数逻辑译码是门限译码的一种，对于卷积码来说，大数逻辑译码是卷积码代数译码中最主要的译码方法。

2.3.2.2概率译码——序列译码、Viterbi(VB)译码、软译码、Turbo码

卷积码的概率译码最早始于1961年由苏联人乌曾格来夫提出的序列译码，1967年Viterbi提出了另一种概率译码算法——Viterbi算法，这是一种最大似然译码算法。在码的约束度比较小的时候，它比序列译码算法的效率更高，速度更快，译码器也更简单，因此，自VB算法提出以来得以及其迅速的发展，并广泛应用于各种数传系统，特别是卫星通信中。

VB译码器的复杂性随着mk指数增长，故不能适用于m太大的卷积码，从而限制了VB译码器输出误码率不能做得太，一般只能做到10^-5到10^-6量级。因而VB译码适用于误码率要求不高且功率受限的信道，如卫星和微波中继信道中。

另一方面，不论信道干扰情况如何，即使接收到的序列完全正确，VB译码器的每一个分支的计算量始终是不变的，所以当信道干扰很小是，译码器的平均计算量仍很大。

在高码速率的情况下，序列译码的输出误码率性能接近于最大似然译码的性能，而当信道误码率高于0.045时，序列译码器的计算量要趋于无穷大，从而无法实现。因此，序列译码的性能在输出误码率的性能方面要稍逊于VB算法。

Turbo码的平均译码错误概率上限为10^-6，且存在地板效应，即使接收的序列完全正确，Turbo码的译码错误依然为10^-6,

三、W算法的提出

以上提及的各种译码算法，都有各自的优势，都有一个共同的不足：都存在门限效应，不能做到精确、快速的译码。W算法是由唯思泰瑞公司的王继深总经理提出的一种新的卷积译码算法，其理论源自于并元论，既不是代数译码，也不是概率译码。

W算法最重要的特点就是精确译码，没有门限、流水线结构、结构非常简单、译码速度快、抗干扰能力强、无记忆效益、电路的复杂程度随着mk的增长成加性增长，而不是指数增长，因此W算法不但能适用于约束长度小的卷积码，也适用于约束长度大的卷积码。

3.1 W算法目前水平

信噪比为3dB时强干扰情况下实现精确的零误码译码效果。

运用目前低档的FPGA芯片EP1C6Q240C8N可实现33Mbps的译码速率，且资源开销仅仅只有442个逻辑单元。译码延时56个时钟周期。

运用4MHz主晶振的MSP430F169单片机可实现19200bps的译码速率，译码延时13个时钟周期。

3.2 W算法的特点