第9章 信道(纠错)编码

第9章信道（纠错）编码信息传输要通过各种物理信道，由于干扰、设备故障等影响，被传送的信源符号可能会发生失真，使有用信息遭受损坏，接收信号造成误判。这种在接收端错误地确定所接收的信号叫做差错。为了提高信息传输的准确性，使其具有较好的抵抗信道中噪声干扰的能力，在通信系统中需要采用专门的检、纠错误方法，即差错控制。

9.1信道编码的概念

差错控制的任务是发现所产生的错误、并指出发生错误的信号或者校正错误，差错控制是采用可靠、有效的信道编码方法来实现的。

信道编码器要对信源编码输出的符号进行变换，使其尽量少受噪声干扰的影响，减少传输差错，提高通信可靠性。进行信道编码是为了提高信号传输的可靠性，改善通信系统的传输质量，研究信道编码的目标是寻找具体构造编码的理论与方法。

与纠错编码有关的基本定义：(1)码长、码重和码距码字中码元的个数称为码字的长度，简称码长，用表示。码字中非“0”码元的个数称为码字的汉明重量(简称码重，记作)。对二进制码来说，码重就是码字中所含码元“1”的数目，例如码字“110000”，其码长码重两个等长码字之间对应码元不相同的数目称为这两个码组的汉明距离(简称码距)。例如码字“110000”与“100001”，它们的汉明距离。在某一码书中，任意两个码字之间汉明距离的最小值称为该码的最小距离，即：码组的最小码距从避免码字受干扰而出错的角度出发，总是希望码字间有尽可能大的距离，因为最小码距代表着一个码组中最不利的情况，应使用最小码距来分析码的检错纠错能力。最小码距是衡量该码纠错能力的依据，是非常重要。检错与纠错能力：定理：若纠错码的最小距离为，那么如下三个结论的任何一个结论独立成立：①若要发现个独立差错，则要求最小码距②若要纠正个独立差错，则要求最小码距③若要求发现e个同时又纠正t个独立差错，则；定理说明，码的最小距离越大，码的纠(检)错误的能力越强。但是，随着多余码元的增多，信息传输速率会降低得越多。通常用来表示码字中信息码元所占的比例，称为编码效率，简称码率，它是衡量码性能的又一个重要参数。码率越高，信息传输率就越高，但此时纠错能力要降低，若时就没有纠错能力了。可见，码率与纠错能力之间是有矛盾的。

(2)错误图样差错的形式也可以用二元序列来描述。设发送码字为，接收码字为，两者的差别:

称为错误图样。如错误图样中的第位为“1”()，则表明传输过程中第位发生了错误。例如：，而，则，可知接收的消息序列中的第“2”位和第“6”位出现了错误。

9.2信道编码的分类

有些实际信道既有独立随机差错也有突发性成串的差错，这种信道称混合差错信道，实际的移动信道属于此类信道。对应的信道编码可分为：以纠独立随机差错为主的信道编码、以纠突发差错为主的信道编码和纠混合差错的信道编码。从功能上看，信道编码可分为检错(可以发现错误)码与纠错(不仅能发现而且能自动纠正)码两类，纠错码一定能检错，检错码不一定能纠错，平常所说的纠错码是两者的统称。

根据信息码元与监督码元之间的关系，纠错码分为线性码和非线性码。线性码——信息码元与监督码元之间呈线性关系，关系可用一组线性代数方程联系起来。非线性码——信息码元与监督校元之间非线性关系。按照对信息码元处理的方法的不同，纠错码分为分组码和卷积码。分组码----把信息序列以每个码元分组，然后把每组个信息元按一定规律产生个多余的监督码元，输出序列每组长为，则每一码字的个校验元只与本码字的个信息位有关，与别的码字的信息位无关，通常记分组码为。

检错与纠错原理

检错、纠错的目的是要根据信道接收端接收到的信息序列来判断是否就是发送的序列，如果有错则尽可能纠正其中的错误。要纠正传输差错，首先必须检测出错误。而要检测出错误，常用的方法是将发送端要传送的信息序列(常为二进制序列)中截取出长度相等的码元进行分组，每组长度为k，组成k位码元信息序列 并根据某种编码算法以一定的规则在每个信息组的后面产生个冗余码元，由冗余码元和信息码元一起形成“位编码序列有，因而纠错编码是冗余编码，如图6.1所示。图6.1纠错编码通常，将分组码规定为具有如图6.2所示的结构。图中前面位()为信息位，后面附加个()校验位。图6.2检错与纠错方式和能力：图6.3所示为几种检错与纠错方式示意图。

图6.3ARQ方式：发送端用编码器对发送数据进行差错编码，通过正向信道送到接收端，而接收端经译码器处理后只是检测有无差错，不作自动纠正。如检测到差错，则利用反向信道反馈，请求发送端重发有错的数据单元，直到接收端检测不到差错为止。FEC方式：发送端用编码器对发送数据进行差错编码，在接收端用译码器对接收到的数据进行译码后检测有无差错，如检测到差错，则确定差错的具体位置和性质，自动加以纠正，故称为“前向纠错”。HEC方式：是检错重发和前向纠错两种方式的混合。发送端用编码器对发送数据进行便于检错和纠错的编码，通过正向信道送到接收端，接收端对少量的接收差错进行自动前向纠正，而对超出纠正能力的差错则通过反馈重发方式加以纠正，所以是一种纠检结合的混合方式。 前面已述信道编码的任务是构造出以最小多余度的代价换取最大抗干扰性的“好“码。下面，从直观概念出发，说明多余度与抗干扰性能的关系，介绍两种极端情况：一是高可靠性，低有效性的重复码；二是高有效性，低可靠性的奇偶校验码。重复码

构成重复码的方法是当发送某个信源符号时，不是只发一个，而是连续重发多个，连续重发的个数越多，重复码的抗干扰能力就越强，当然效率也越低。

9.3检重复码和奇偶校验码

不重复时为(1，1)重复码，如图6.4所示:图6.4发送码元不重复

对这种情况可得结论：不重复，方法简单，但没有任何抗干扰能力，既不能发现，更不能纠正错误。重复一次时为(2，1)重复码，如图6.5所示:图6.5发送码元重复一次

结论：重发一次，效率降低一倍，可以发现一个错误(收端能发现它)，但不能纠正这个错误。重复二次时为(3，1)重复码，(3，1)重复码用“000”来代表信息“0”，用“111”来代表信息“1”，显然，所增加的两位码元并不会增加信息，是多余的，因而使信息传输率降低。当信道上信噪比足够大时，我们可以认为码字中产生的错误一般不多于一个码元，那么，如果接收到“001”、“010”、“100”，我们就可判定实际传输的是“000”；同样，如接收到“011”、“101”、“110”，则可判定为“111”。因此多余码元使我们可检出一个错，并且还可纠正这个错误，这样就提高了信息传输的可靠性。结论：重发二次，效率降低二倍，但换取了可纠正一个差错或发现两个差错的性能改善。2)奇偶检验码

奇偶校验是一种最基本的校验方法。构成奇偶检验码的方法是在每个二进制信息位后加上一个奇(偶)监督位(或称校验位)，使码长，同时使码中“1”的个数恒为奇数(或偶数)，如图6.6所示。在奇偶校验码中，监督位，它是一种码重为奇数(或偶数)的系统分组码。如图6.6奇偶校验又可以分为奇校验和偶校验。其规则如下：奇校验----如果信息码元中“1”值的个数为奇数个，则校验码元值为“0”；如果信息码元中“1”值的个数为偶数个，则校验码元值为“1”。即所有信息码元与校验码元的模二和等于“1”。

偶校验----如果信息码元中“1”值的个数为偶数个，则校验码元值为“0”；如果信息码元中“1”值的个数为奇数个，则校验码元值为“1”。即所有信息码元与校验码元的模二和等于“0”。根据奇偶校验的规则，校验位值的确定方法如表6.1所示。

表6.1奇偶校验规则表

校验方式信息位中“1”值的个数校验位值奇校验奇数个0偶数个1偶校验偶数个0奇数个1例如，在七位信息码中，字符A的代码为1000001，其中有两位码元值为“1”。若采用奇校验编码，由于这个字符的七位代码中有偶数个“1”，所以校验位的值应为“l”，其8位组合代码为：10000011，前7位是信息位，最右边的1位是校验位。同理，若采用偶校验，可得奇偶校验位的值为“0”，其8位组合代码为：10000010。这样在接收端对码字中“1”的个数进行检验，如有不符，就可断定发生了差错。在接收端进行校验时，如采用奇校验编码，当接收到的字符经检测其八位代码“l”的个数为奇个数时，则被认为传输正确；否则就被认为传输中出现差错。然而，如果在传输中有偶数位出现差错，用此方法就检测不出来了。所以，奇偶校验方式只能检测出位代码中出现的任意奇数个错误，如果代码中错码数为偶数个，则奇偶校验不能奏效。由于奇偶校验码容易实现，所以当信道干扰不太严重以及码长不很长时很有用，特别是在计算机通信网的数据传送中经常应用这种检错码。9.3线性分组码

线性分组码是纠错码中非常重要的一类码，虽然对于同样码长的非线性码来说线性码可用码字较少，但由于线性码的编码和译码容易实现，而且是讨论其他各类码的基础，至今仍是广泛应用的一类码。9.3.1线性分组码的基本概念

定义：对信源编码器输出的二进制序列进行分组，设分组长度为，相应的码字表示为：

信道编码(纠错编码)的目的是将信息码字进行变换，使其成为以下形式：

其中：，我们称全体码字的集合为分组码。若由到之间的变换为线性变换，则称全体码字的集合为线性分组码，常用线性分组码表示全体码字的集合.例1设信源编码器输出的信息序列为，其中是二进制数。信道编码器输出的码字，其中也是二进制数。若从到的变换规则为：由于从到的变换是一种线性变换，所以全体的集合构成了一种线性分组码。

由本例可以看出，变换后码字集合中每一个码字的所有码元之和为：因为假设了码为二进制码，上述码元的和是模2和。因此，变换后将每一个码字的码元全部加起来，它的模2和为“0”，即每一个码字中“1”的个数为偶数个，所以这种码为偶校验码。

6.3.2校验矩阵和生成矩阵例2分组码，按以下的规则(校验方程)可得到四个校验元：式中：是三个信息码元，方程中的加运算均为模2加。由此可得到分组码的八个码字，列于表6.2中。由校验方程看到，信息码元与校验码元满足线性关系，因此是线性码。

生成矩阵:线性分组码校验方程可写成矩阵形式。式中G称线性分组码的生成矩阵。

表9.2：例2编出的线性码的码字与信息码元的对应关系

信息码元码字00000000000010011101010010011101101110101001001110101101001111011010011111110100一致校验矩阵由校验码元与信息码元的关系，可得：即：易得：

由此关系可知，

这说明，的第一行就是的第一列，的第二行就是的第二列，……，因此，矩阵一旦确定，则矩阵也就确定，反之亦然。=对偶码

我们已经讨论了线性分组码的生成矩阵与其对应的一致校验矩阵，如果把码的一致校验矩阵看成是码的生成矩阵，将码的生成矩阵看成是码的一致校验矩阵，则称这两种码互为对偶码。

例3求例2所述码的对偶码。显然，码的对偶码应是码，由对偶码的定义得：码的矩阵就是码的矩阵，将其化成标准形式后即可得到码的对偶码码，如表9.3所示。表9.3信息码元码字信息码元码字000000000001000100010100010001011100110011100010001011010101010011001100111011011101100001000100111110011000100101010110011011101001011001100011110111010001110111010111111111119.3.3线性分组码的译码

只要找到矩阵或矩阵，便解决了编码问题。经编码后发送的码字，由于信道干扰可能出错，接收方怎样发现或纠正错误呢，这就是译码要解决的问题。定义——设码的一致校验矩阵为，是发送码字为时接收序列，为接收序列的伴随式或校正子。伴随式是一致校验矩阵的线性组合，如果错误图样中有一些分量不为“0”，则在中正好就是中不为“0”的那几列组合而成。由上面的分析，可得如下结论：①从式(6.2.7)可知伴随式仅与错误图样有关，它充分反映了信道受干扰的情况，而与发送的是什么码字无关。②伴随式是是否有错的判别式，若，则判没有出错；若，则判有错。③不同的错误图样具有不同的伴随式，它们是一一对应的，对二元码来说，伴随式即为矩阵中与错误图样对应的各列之和。注意，如果错误图样本身就是一个码字，即，那么计算伴随式得到的结果必为“0”，此时的错误不能发现，也无法纠正，因而这样的错误图样称为不可检错误图样。

例3计算例2所述码

一致校验矩阵为：接收（1010011）伴随式为

因此，译码器判别接收序列无错，传输中没有发生错误。当（1110011）接收时，接收端译码器根据接收序列计算的伴随式为:

由于，所以译码器判别接收序列有错，传输中有错误发生。码是纠正单个错误的码，观察即为的第二列，因此可判定接收序列的第二位发生了错误。由于接收序列中错误个数与码的纠错能力相符，所以可正确译码，发送码字应为当接收时，接收端译码器根据接收序列计算的伴随式为：，但与的任何一列都不相同，无法判别错误发生在哪些位上，此时只能发现有错。例题：已知：求H、纠错能力。9.4卷积码卷积码由埃利