搜索
第9章差错控制编码差错控制编码，又称信道编码、可靠性编码、抗干扰编码或纠错码，它是提高数字信号传输可靠性的有效方法之一。它产生于20世纪50年代初，发展到70年代趋向成熟。本章将主要分析差错控制的基本方法及纠错编码的基本原理、常用的检错码、线性分组码及卷积码的构造原理及其应用。第一节概述一、差错控制编码的作用在数字通信中，根据不同的目的，编码可分为信源编码和信道编码。信源编码是为了提高数字通信的有效性以及使模拟信号数字化而采取的编码技术。信道编码是为了降低误码率，提高数字通信的可靠性而采取的编码。数字信号在传输过程中，加性噪声、码间串扰等都可能引起误码。为了提高系统的抗干扰性能，可以加大发送功率，降低接收设备本身的噪声，以及合理选择调制、解调方法等。此外，还可以采用信道编码技术。正如第一章在通信系统模型中所述，信源编码是降低信源的冗余度；而信道编码按一定的规则人为引入冗余度。具体地讲，信道编码就是在发送端的信息码元序列中，以某种确定的编码规则，加入监督码元，在接收端再利用该规则进行检查识别，从而发现错误、纠正错误。二进制数字信号在传输中发生的错误，主要有两种类型：随机错误和突发错误。随机错误的特点是码元间的错误互相独立，即每个码元的错误概率与它前后码元的错误与否是无关的。突发错误则不然，一个码元的错误往往影响前后码元的错误概率。或者说，一个码元产生错误，则后面几个码元都可能发生错误。在实际信道中，上述两种错误形式往往兼而有之。移动通信的传输信道属于变参信道，它不仅会引起随机错误，而更重要的是造成突发错误。能发现错误的编码叫检错码；能纠正错误的编码叫纠错码。一般说来，纠错码一定能检错。反过来，检错码不一定能纠错。或者说，同一个码，检错能力比纠错能力强。二、差错控制方式在数字通信系统中，利用纠错码或检错码进行差错控制的方式有3种：检错重发、前向纠错和混合纠错，它们的系统构成如图9-1所示，图中有斜线的方框图表示在该端检出错误。1．检错控制方式检错重发又称自动请求重传方式，记作ARQ(AutomaticRepeatRequest)。发送端发出能够发现（检测）错误的码，接收端收到通过信道传来的码后，在译码器根据该码的编码规则，判决收到的码序列中有无错误产生，如果发现错误，则通过反向信道把这一判决结果反馈给发端。然后，发端根据这些判决信号，把接收端认为有错误的信息再次传送，直到接收端认为正确接收为止。从上可知，应用ARQ方式必须有一反馈信道，一般较适用于一个用户对一个用户（点对点）的通信，且要求信源能够控制，系统收发两端必须互相配合、密切协作。由于反馈重发的次数与信道干扰情况有关，若信道干扰很频繁，则系统经常处于重发消息的状态，因此这种方式传送消息的连贯性和实时性较差。该方式的优点是：编译码设备简单；在一定的多余度码元下，检错码的检错能力比纠错码的纠错能力要高得多，因此这种系统的适应性很强，特别适应于短波、散射、有线等干扰情况特别复杂的信道中。2．前向纠错方式前向纠错方式记作FEC（ForwordError-Correction)。发送端发送能够被纠错的码，接收端收到这些码后，通过纠错译码器不仅能够自动地发现错误，而且能自动地纠正接受码字传输中的错误。这种方式的优点是不需要反馈信道，能进行一个用户对多个用户的同播通信，译码实时性较好。其缺点是译码设备比较复杂，所选用的纠错码必须与信道的干扰情况相匹配，因此对信道的适应性较差。编码效率低。但由于这种方式能同播，特别适用于军用通信。3．混合纠错方式混合纠错方式记作HEC(HybridError-Correction)是FEC和ARQ方式的结合，这种方式是发送端发送的码不仅能够被检测出错误，而且还具有一定的纠错能力。接收端收到码后，首先检查差错情况，如果在纠错码的纠错能力范围以内，则自动纠错，如果错误过多，超过了码的纠错能力，但能检测出来，则接收端通过反馈信道，要求发端重新传送有错的消息。这种方式具有自动纠错和检错重发的优点，并可达到较低的误码率。因此，在实际中的应用越来越广。在移动通信系统中，几乎都采用前向纠错的差错控制方式。除了上述三种主要方式以外，还有所谓狭义信息反馈系统（IRQ—InformationRepeatRequest）。这种方式是接收端把收到的消息原封不动地通过反馈信道送回发送端，发送端比较发送的与反馈回来的消息，从而发现错误，并且把传错部分对应的原消息再次传送，最后达到使对方正确接收消息的目的。三、纠错码的分类１.线性码与非线性码根据纠错码各码组信息和监督元的函数关系，可分为线性码和非线性码。如果函数关系是线性的，即满足一组线性方程式，则称为线性码，否则为非线性码。线性码集合中的所有码字在加法和乘法运算时是封闭的，而非线性码则不封闭。换言之，线性码实际上就是n维线性空间的一个k（kn）维子空间。目前大量使用的均为线性码。２．分组码与卷积码根据码组中监督码元与信息码元相互关联的长度，可分为分组码和卷积码。分组码的各码元仅与本组的信息元有关；卷积码中的码元不仅与本组的信息元有关，而且还与前面若干组的信息元有关。分组码把信息序列以k个码元分组，通过编码器将每组的k元信息按一定规律产生r个多余码元（称为校验元或监督元）输出长为n=k+r的一个码字（码组）。因此，每一码组的r个校验元仅与本组的信息元有关而与别组无关。分组码用(n，k)表示，n为码长，k表示信息位数目。卷积码将信息序列以k0个码元分段，通过编码器输出长为n0的一段码组。但是该码的n0-k0个校验元不仅与本段的信息源有关，而且也与其前m段的信息源有关，故卷积码用（n0，k0，m0）表示。３．检错码和纠错码根据码的用途，可分为检错码和纠错码。检错码以检错为目的，不一定能纠错；而纠错码以纠错为目的，一定能检错。另外，在分组码中按照码的结构特点，可以分为循环码和非循环码；根据纠（检）错误的类型来分，可以分为纠正随机错误的码、纠正突发错误的码和纠正同步错误的码；根据码元取值的进制来分，可分为二进制码和多进制码；等等，这里不一一赘述。四、纠错编码的基本原理下面以分组码为例来说明纠错码检错和纠错的基本原理。1．分组码分组码一般可用（n，k）表示。其中，k是每个码组二进制信息码元的数目，n是编码组的码元总位数，又称为码组长度，简称码长。n-k=r为每个码组中的监督码元数目。简单地说，分组码是对每段k位长的信息组以一定的规则增加r个监督元，组成长为n的码字。在二进制情况下，共有2k个不同的信息组，相应地可得到2k个不同的码字，称为许用码组。其余2n-2k个码未被选用，称为禁用码组。两个等长码组之间相应位取值不同的数目称为这两个码组的汉明（Hamming）距离，简称码距。例如11000与10011之间的距离d=3。码组集合中任意两个码字之间距离的最小值称为码的最小距离，用d0表示。最小码距是码的一个重要参数，它是衡量码检错、纠错能力的依据。在分组码中，非零码元的数目称为码字的汉明重量，简称码重。例如，码字10110，码重w=3。2．检错和纠错能力我们以重复码为例，说明为什么纠错码能够检错或纠错。若分组码码字中的监督元在信息元之后，而且是信息元的简单重复，则称该分组码为重复码。它是一种简单实用的检错码，并有一定的纠错能力。例如（2，1）重复码，两个许用码组是00与11，d0=2，收端译码，出现01、10禁用码组时，可以发现传输中的一位错误。如果是（3，1）重复码，两个许用码为000、111，d0=3；当收端出现两个或三个1时，判为1，否则判为0。此时，可以纠正一个错误，或者该码可以检出两个错误。从上面的例子中，可以看出：码的最小距离d0直接关系着码的检错和纠错能力；任一（n，k）分组码，若要在码字内检测e个随机错误，则要求码的最小距离：d0≥e+1要纠正t个随机错误，则要求码的最小距离：d0≥2t+1要纠正t个错误同时检测e个错误（e≥t），则要求码的最小距离：d0≥t+e+13．编码效率采用差错控制编码是提高了通信系统的可靠性，但是以降低有效性为代价换来的。通常定义编码效率R来衡量有效性：R=k/n其中，k是一个码组中信息元的个数，n为码长。对纠错码的基本要求是：检错和纠错能力尽量强；编码效率尽量高；编码规律尽量简单。实际中要根据具体指标要求，保证有一定纠、检错能力和编码效率，并且易于实现。第二节常用的几种简单分组码纠错编码的种类很多，较早出现的、应用较多的大多属于分组码。本节仅介绍其中一些较为常用的简单编码。一、奇偶监督码奇偶监督码是在原信息码后面附加一个监督元，使得码组中“1”的个数是奇数或偶数。或者说，它是含一个监督元，码重为奇数或偶数的（n，n-1）系统分组码。奇偶监督码又分为奇监督码和偶监督码。设码字A=〔an-1，an-2，a1，a0〕，对偶监督码有(9-1)式中an-1，an-2，…a1为信息元，a0为监督元。由于该码的每一个码字均按同一规则构成式（9-1），故又称为一致监督码。接收端译码时，按式（9-1）将码组中的码元模二相加，若结果为“0”就认为无错（包括有偶数个错误）；结果为“1”，就可断定该码组经传输后有奇数个错误。奇监督码情况相似，只是码组中“1”的数目为奇数，即满足条件而检错能力与偶监督码相同。奇偶监督码的编码效率为R=（n-1）/n，奇偶校验码的编码率是最高的。00121aaaann10121aaaann二维奇偶监督码把上述奇偶监督码的若干码组排列成矩阵，每一码组写成一行，然后再按列的方向增加第二维监督位，设a01a02××××××a0m为m行奇偶监督位；cn-1cn-2××××××c0为按列进行第二次编码所增加的监督位，它们构成了一监督位行。由此组成的二维奇偶监督码阵如下：二、二维奇偶监督码an-11an-11…a11a01an-12an-12…a12a02…………………an-1man-1m…a1ma0mcn-1cn-2…c1c0这种码有可能检测偶数个错误。因为每行的监督位虽然不能用于检测本行中的偶数个错误，但按列的方向有可能由cn-1、cn-2××××××、c0等监督位检测出来。有一些偶数错码不可能检测出，例如，构成矩形的四个错码就检测不出来,比如阵列中的an-22,a12,an-2m,a1m。这种二维奇偶监督码适于检测突发错误。前述的一维奇偶监督码一般只适于检测随机错误。二维奇偶监督码不仅可用来检错，还可以用于纠错。例如，当码组中仅在一行中有奇数个错误时，则能够确定错码的位置，从而纠正它。an-11an-11…a11a01an-12an-12…a12a02…………………an-1man-1m…a1ma0mcn-1cn-2…c1c0三、恒比码码字中1的数目与0的数目保持恒定比例的码称为恒比码。由于恒比码中，每个码组均含有相同数目的1和0，因此恒比码又称等重码，定1码。这种码在检测时，通过计算接收码元中1的数目是否正确，就知道有无错误。目前我国电传通信中普遍采用3：2码，又称“5中取3”的恒比码，即每个码组长度为5，其中3个“1”。这时可能编成的不同码组数目等于从5中取3的组合数10，这10个许用码组恰好可表示10个阿拉伯数字，如表7-1所示。而每个汉字又是以四位十进制数来代表的。实践证明，采用这种码后，我国汉字电报的差错率大为降低。目前国际上通用的ARQ电报通信系统中，采用3：4码，即“7中取3”的恒比码。100119011108111007101016001115110104101103110012010111011010码字数字表9-13：2恆比码第三节线性分组码一、基本概念线性分组码在所有可能的分组码（BlockCode）中只占很少的一部分，然而，它却几乎是惟一具有实际价值的分组码。线性分组码是所有纠错编码中最基本最容易研究的一类码，它概念清楚，易于理解，而且能方便地反映出各类编码中广为使用的一些基本参数和名称，因此，线性分组码就成了讨论其他各类码的基础。在（n，k）分组码中，若每一个监督元都是码组中某些信息元按模2和得到的，即监督元是信息元按线性关系