纠错编码简介

纠错编码简介

        我们知道，在计算机中和数据通信中，经常需要将二进制数字信号进行传递，这种传递的距离近则数米、数毫米，远则超过数千公里。在传递信息过程中，由于存在着各种干扰，可能会使二进制信号产生失真现象，即在传递过程中二进制信号0可能会变成1，1可能会变成0。试想一个二进制信号传递的简单模型，它有一个发送端和一个接收端，二进制信号串X = x1x2…xn从发送端发出经传输介质而至接收端。由于存在着干扰对传输介质的影响，因而接收端收到的二进制信号串X' = x'1x'2…x'n中的x'i可能不一定就与xi相等，从而产生了二进制信号的传递错误。
        由于在计算机中和数据通信系统中的信号传递是非常的频繁与广泛，因此，如何防止传输错误就变得相当重要了，当然，要解决这个问题可以有不同的途径。人们所想到的第一个途径是提高设备的抗干扰能力和信号的抗干扰能力。但是，大家都知道，这种从物理角度去提高抗干扰能力并不能完全消除错误的出现。第二个途径就是我们所要谈到的采用纠错码（Error Correcting Code）的方法以提高抗干扰能力。这种纠错码的方法是从编码上下功夫，使得二进制数码在传递过程中一旦出错，在接收端的纠错码装置就能立刻发现错误，并将其纠正。由于这种方法简单易行，因此目前在计算机中和数据通信系统中被广泛采用。采用这种方法后，二进制信号传递模型就可以变为纠错码模型了。
        纠错码模型可以想到，当二进制信号串从发送端发送时，需按规定转换成具有抗干扰能力的纠错码，然后才发送出去。在接收端，当接收到二进制信号串后立即对收到的纠错码进行检查，查对在途中是否失真，如失真则负责纠正。
        模型的一个典型实现，就是在远程数据传输系统中具有纠错能力的数据传输装置,二进制信号发生器发出信号（二进制信号发生器可以是计算机，或者是由人控制的某些装置如终端），经差错控制器形成纠错码，然后经调制器使二进制信号变成为适宜于信道传播的电信号，这种信号通过信道传输至接收端，首先通过解调器将其还原为原来的二进制信号，再经差错控制器检验经信道传输后是否产生失真，并采取措施进行纠正。经纠正后的二进制信号送入二进制信号接收器，从而完成整个传输过程。二进制信号接收器可以是计算机，或其他接收装置如终端等。
        但是，为什么纠错码具有发现错误、纠正错误的能力呢？纠错码又是按什么样的原理去编的呢？为了说明这些问题，我们首先介绍一些基本概念: 由0和1组成的串称为字（Word），一些字的集合称为码（Code）。码中的字称为码字（Code Word）。不在码中的字称为废码（Invalid Code）。码中的每个二进制信号0或1称为码元（Code Letter）。
        我们下面举出几个关于纠错码的例子。设有长度为2的字，它们一共可有2x2 = 4个，它们所组成的字集S2 = {00,01,10,11}。当选取编码为S2时，这种编码不具有抗干扰能力。因为当S2中的一个字如10，在传递过程中其第一个码元1变为0，因而整个字成为00时，由于00也是S2中的字，故我们不能发现传递中是否出错。但是，当我们选取S2的一个子集如C2 = {00,11}作为编码时就会发生另一种完全不同的情况。因为此时01和10均为废码，而当11在传递过程中第一个码元由1变为0，即整个字成为01时，由于01是废码，因而我们发现传递过程中出现了错误。对00也有同样的情况。但是，这种编码有一个缺点，即它只能发现错误而不能纠正错误，因此我们还需要选择另一种能纠错的编码。现在我们考虑长度为3的字，它们一共可有2x3 = 8个，它们所组成的字集S3 = {000,001,010,011,100,101,110,111}中我们选取编码C3 = {001,110}。利用此编码我们不仅能发现错误而且能纠正错误。因为码字001出现错误后将变为：000,011,101，而码字110出现错误后将变为：111,100,010。故如码字001在传递过程中任何一个码元出现了错误，整个码字只会变为101、011或000，但是都可知其原码为001。对于码字110也有类似的情况。故对编码C3，我们不仅能发现错误而且能纠正错误。当然，上述编码还有一个缺点，就是它只能发现并纠正单个错误。当错误超过两个码元时，它就既不能发现错误，更无法纠正了。

深圳市安美通科技有限公司   工程部