第十二章电子讲义差错控制编码

1、第十二章 差错控制编码知识结构- 差错控制的主要方式- 检、纠错编码的基本概念和基本原理- 常用的简单的检、纠错编码- 线性分组码- 卷积码教学目的- 了解纠错编码的基本原理- 了解几种常用编码：奇偶校验码、正反码等，线性分组码、循环码、卷积码的编解码原理教学重点- 重点掌握线性分组码、循环码、卷积码的编解码原理。教学难点- 生成矩阵和生成多项式教学方法及课时- 多媒体授课（8学时）（分4个单元）备注 单元二十八（2学时）12.1 引言（差错控制的作用和方式的分类）知识要点：信源编码与信道编码的基本概念、相互关系及区别 差错控制的主要3种方式12.1.1 信源编码与信道编码的基本概念设计通信系

2、统的目的就是把信源产生的信息有效可靠地传送到目的地。在数字通信系统中，为了提高数字信号传输的有效性而采取的编码称为信源编码；为了提高数字通信的可靠性而采取的编码称为信道编码。信源编码信源可以有各种不同的形式，例如在无线广播中，信源一般是一个语音源（话音或音乐）；在电视广播中，信源主要是活动图像的视频信号源。这些信源的输出都是模拟信号，所以称之为模拟源。而数字通信系统是设计来传送数字形式的信息，所以，这些模拟源如果想利用数字通信系统进行传输，就需要将模拟信息源的输出转化为数字信号，而这个转化构成就称为信源编码。对于信源编码的研究，在通信领域受到了人们的广泛关注。特别在移动通信系统中，信源编码（语

3、音编码）决定了接收到的语音的质量和系统容量。因为在移动通信系统中，带宽是很珍贵的，所以，如何在有限的可分配的带宽内容纳更多的用户，已经成为经营者最为关心的问题。而低比特率语音编码提供了解决该问题的一种方法。在编码器能够传送高质量语音的前提下，如果比特率越低，就可以在一定的带宽内能容纳更多的语音通道。因此，生产商和服务提供商不断地寻求新的编码方法，以便在低比特率条件下提供高质量的语音。语音编码的目的就是在保持一定算法复杂程度和通信时延的前提下，运用尽可能少的信道容量，传送尽可能高的语音质量。目前较为常用的语音编码形式有：脉冲编码调制（PCM）、差分脉冲编码调制（DPCM）、自适应差分脉冲编码调制

4、（ADPCM）、增量调制（DM）、连续可变斜率增量调制（CVSDM）、自适应预测编码（APC）、自带编码（SBC）、码激励线性预测编码等等。信道编码（差错控制编码）在实际信道传输数字信号的过程中，引起传输差错的根本原因在于信道内存在的噪声以及信道传输特性不理想所造成的码间串扰。为了提高数字传输系统的可靠性，降低信息传输的差错率，可以利用均衡技术消除码间串扰，利用增大发射功率、降低接收设备本身的噪声、选择好的调制制度和解调方法、加强天线的方向性等措施，提高数字传输系统的抗噪性能，但上述措施也只能将传输差错减小到一定程度。要进一步提高数字传输系统的可靠性，就需要采用差错控制编码，对可能或已经出现的

5、差错进行控制。差错控制编码是在信息序列上附加上一些监督码元，利用这些冗余的码元，使原来不规律的或规律性不强的原始数字信号变为有规律的数字信号；差错控制译码则利用这些规律性来鉴别传输过程是否发生错误，或进而纠正错误。原始数字信号是分组传输的，例如每k个二进制码元为一组（称为信息组），经信道编码后转换为每n个码元一组的码字（码组），这里nk，分组码通常表示为（n，k）。可见，信道编码是用增加数码，利用“冗余”来提高抗干扰能力的，也就是以降低信息传输速率为代价来减少错误的，或者说是用削弱有效性来增强可靠性的。本章首先给出了差错控制编码的基本概念，介绍了几种常用简单分组码，在此基础上，对分组码、循环码

6、和卷积码基本原理和性能进行了研究分析。12.1.2 纠错编码的分类在差错控制系统中，信道编码存在着多种实现方式，同时信道编码也有多种分类方法。（）按照信道编码的不同功能，可以将它分为检错码和纠错码。检错码仅能检测误码，例如，在计算机串口通信中常用到的奇偶校验码等；纠错码可以纠正误码，当然同时具有检错的能力，当发现不可纠正的错误时可以发出出错指示。（）按照信息码元和监督码元之间的检验关系，可以将它分为线性和非线性码。若信息码元与监督码元之间的关系为线性关系，即满足一组线性方程式，称为线性码；否则，称为非线性码。（）按照信息码元和监督码元之间的约束方式不同，可以将它分为分组码和卷积码。在分组码中，

7、编码后的码元序列每n位分为一组，其中k位信息码元，r个监督位，r = n-k。监督码元仅与本码字的信息码元有关。卷积码则不同，监督码元不但与本信息码元有关，而且与前面码字的信息码元也有约束关系。（）按照信息码元在编码后是否保持原来的形式，可以将它分为系统码和非系统码。在系统码中，编码后的信息码元保持原样不变，而非系统码中的信息码元则发生了变化。除了个别情况，系统码的性能大体上与非系统码相同，但是非系统码的译码较为复杂，因此，系统码得到了广泛的应用。（）按照纠正错误的类型不同，可以将它分为纠正随机错误码和纠正突发错误码两种。前者主要用于发生零星独立错误的信道，而后者用于对付以突发错误为主的信道。

8、（）按照信道编码所采用的数学方法不同，可以将它分为代数码、几何码和算术码。其中代数码是目前发展最为完善的编码，线性码就是代数码的一个重要的分支。除上述信道编码的分类方法以外，还可以将它分为二进制信道编码和多进制信道编码等等。同时，随着数字通信系统的发展，可以将信道编码器和调制器统一起来综合设计，这就是所谓的网格编码调制（TCM Trellis Coded Modulation）。12.1.3 差错控制方式常用的差错控制方式主要有三种：前向纠错（简称FEC）、检错重发（简称ARQ）和混合纠错（简称HEC），它们的结构如图12-1所示。图中有斜线的方框图表示在该端进行错误的检测。前向纠错系统中，发

9、送端经信道编码后可以发出具有纠错能力的码字；接收端译码后不仅可以发现错误码，而且可以判断错误码的位置并予以自动纠正。然而，前向纠错编码需要附加较多的冗余码元，影响数据传输效率，同时其编译码设备比较复杂。但是由于不需要反馈信道，实时性较好，因此，这种技术在单工信道中普遍采用，例如无线电寻呼系统中采用的POGSAG编码等。图12-1差错控制方式检错重发方式中，发送端经信道编码后可以发出能够检测出错误能力的码字；接收端收到后经检测如果发现传输中有错误，则通过反馈信道把这一判断结果反馈给发送端。然后，发送端把前面发出的信息重新传送一次，直到接收端认为已经正确后为止。典型系统检错重发方式的原理方框图如图

10、12-2所示：常用的检错重发系统有三种，即停发等候重发、返回重发和选择重发。图12-2ARQ系统组成方框图在返回重发系统中，发送端无停顿的送出一个又一个码字，不再等待ACK信号，一旦接收端发现错误并发回NAK信号，则发送端从下一个码字开始重发前一段N组信号，N的大小取决于信号传递及处理所带来的延迟，这种系统比停发等候重发系统有很大的改进，在许多数据传输系统中得到应用。在选择重发系统中，发送端也是连续不断地发送码字，接收端发现错误发回NAK信号。与返回重发系统不同的是，发送端不是重发前面的所有码字，而是只重发有错误的那一组。显然，这种选择重发系统传输效率最高，但控制最为复杂。此外，返回重发系统和

11、选择重发系统都需要全双工的链路，而停发等候重发系统只需要半双工的链路。基于上述分析，检错重发（ARQ）的优点主要表现在：（1）只需要少量的冗余码，就可以得到极低的输出误码率；（2）使用的检错码基本上与信道的统计特性无关，有一定的自适应能力；（3）与FEC相比，信道编译码器的复杂性要低得多。同时它也存在某些不足，主要表现在：（1）需要反向信道，故不能用于单向传输系统，并且实现重发控制比较复杂；（2）当信道干扰增大时，整个系统有可能处在重发循环当中，因而通信效率低，不大适合于严格实时传输系统。混合纠错方式是前向纠错方式和检错重发方式的结合。在这种系统中发送端不但具有纠正错误的能力，而且对超出纠错能

12、力的错误有检测能力。遇到后一种情况时，系统可以通过反馈信道要求发送端重发一遍。混和纠错方式在实时性和译码复杂性方面是前向纠错和检错重发方式的折衷。在实际应用中，上述几种差错控制方式应根据具体情况合理选用。12.1.4 纠错编码的基本原理信道编码的基本思想就是在被传送的信息中附加一些监督码元，在收和发之间建立某种校验关系，当这种校验关系因传输错误而受到破坏时，可以被发现甚至纠正错误，这种检错与纠错能力是用信息量的冗余度来换取的。下面将介绍几个与信道编码有关的基本概念：码长：码字中码元的数目；码重：码字中非0数字的数目；对于二进制码来讲，码重W就是码元中1的数目，例如码字10100，码长n = 5

13、，码重W = 2。码距：两个等长码字之间对应位不同的数目，有时也称作这两个码字的汉明距离，例如码字10100与11000之间的码距d = 2。最小码距：在码字集合中全体码字之间距离的最小数值。对于二进制码字而言，两个码字之间的模二相加，其不同的对应位必为1，相同的对应位必为0。因此，两个码字之间模二相加得到的码重就是这两个码字之间的距离。以二进制分组码的纠错过程为例，可以较为详细地说明纠错码检错和纠错的基本原理。分组码对于数字序列是分段进行处理的，设每一段有k个码元组成（称作长度为k的信息组），由于每个码元有0或1两种值，故共有个不同的状态。每段长为k的信息组，以一定的规则增加r个多余度码元（

14、称为监督元），监督这k个信息元，这样就组成长度为n k+r的码字（又称n重）。共可以得到个长度为n码字，它们通常被称为许用码字。而长度为n的数字序列共有2n种可能的组合，其中 -个长度为n码字未被选用，故称它们为禁用码字。上述个长度为n的许用码字的集合称为分组码。分组码能够检错或纠错的原因是存在 -多余度码字，或者说在 码字中有禁用码字存在。下面就举一个具体的例子：设发送端发送A和B两个消息，分别用一位码元来表示，1代表A，0代表B。如果这两个信息组在传输中产生了错误，那么就会使0错成了1或1错成了0，而接收端不能发现这种错误，更谈不上纠正错误了。若在每个一位长的信息组中加上一个监督元（r1）

15、，其规则是与信息元重复，这样编出的两个长度为n2的码字，它们分别为11（代表A）和00（代表B）。这时11、00就是许用码字，这两个码字组成一个（2，1）分组码，其特点是各码字的码元是重复的，故又称为重复码。而01、10就是禁用码字。设发送11经信道传输错了一位，变成01或10，收端译码器根据重复码的规则，能发现有一位错误，但不能指明错在哪一位，也就是不能作出发送的消息是A（11）还是B（00）的判决。若信道干扰严重，使发送码字的两位都产生错误，从而使11错成了00，收端译码器根据重复码的规则检验，不认为有错，并且判决为消息B，造成了错判。这时可以发现：这种码距为2的（2，1）重复码能确定一个

16、码元的错误，不能确定二个码元的错误，也不能纠正错误。若仍按重复码的规则，再加一个监督码元，得到（3，1）重复码，它的两个码字分别为111和000，其码距为3。这样其余六个码字（001、010、100、110、101、011）为禁用码字。设发送111（代表消息A），如果译码器收到的3重为110，根据重复码的规则，发现有错，并且当采用最大似然法译码时，把与发送码字最相似的码字认为就是发送码字。而110与111只有一位不同，与000有两位不同，故判决为111。事实上，在一般情况下，错一位的可能性比错二位的可能性要大得多，从统计的观点看，这样判决是正确的。因此，这种（3，1）码能够纠正一个错误，但不能

17、纠正两个错误，因为若发送111，收到100时，根据译码规则将译为000，这就判错了。类似于前面的分析，这种码若用来检错，它可以发现两个错误，但不能发现三个错误。当然，还可以选用码字更长的重复码进行信道编码，随着码字的增长，重复码的检错和纠错能力会变得更强。上述例子表明：纠错码的抗干扰能力完全取决于许用码字之间的距离，码的最小距离越大，说明码字间的最小差别越大，抗干扰能力就越强。因此，码字之间的最小距离是衡量该码字检错和纠错能力的重要依据，最小码距是信道编码的一个重要的参数。在一般情况下，分组码的最小汉明距离与检错和纠错能力之间满足下列关系：（1）当码字用于检测错误时，如果要检测e个错误，则（1

18、2-1）图12-3纠（检）错能力的几何解释这个关系可以利用图12-3（a）予以说明。在图中用A和B分别表示两个码距为d0的码字，若A发生e个错误，则A就变成以A为球心，e为半径的球面上的码字，为了能将这些码字分辩出来，它们必须距离其最近的码字B有一位的差别，即A和B之间最小距离为。（2）当码字用于纠正错误时，如果要纠正t个错误，则（12-2）这个关系可以利用图12-3（b）予以说明。在图中用A和B分别表示两个码距为的码字，若A发生t个错误，则A就变成以A为球心，t为半径的球面上的码字；B发生t个错误，则B就变成以B为球心，t为半径的球面上的码字。为了在出现t个错误之后，仍能够分辩出A和B来，那

19、么，A和B之间距离应大于2t，最小距离也应当使两球体表面相距为1，即满足不等式（12-2）。（3）若码字用于纠t个错误，同时检e个错误时（et），则（12-3）这个关系可以利用图12-3(c)予以说明。在图中用A和B分别表示两个码距为的码字，当码字出现t个或小于t个错误时，系统按照纠错方式工作；当码字出现大于t个而小于e个错误时，系统按照检错方式工作；若A发生t个错误，B发生e个错误时，既要纠A的错，又要检B的错，则A和B之间距离应大于t+e，也就是满足式（12-3）。通常，在信道编码过程中，监督位越多纠错能力就越强，但编码效率就越低。若码字中信息位数为k，监督位数为r，码长n = k+r。则

20、编码效率Rc可以用下式表示： （12-4）信道编码的任务就是要根据不同的干扰特性，设计出编码效率高、纠错能力强的编码。在实际设计过程中，需要根据具体指标要求，尽量简化编码实现的复杂度，节省设计费用。12.2 常用的简单的检、纠错编码知识要点：奇偶监督 恒比码 正反码本节介绍几种简单的检错码，这些信道编码很简单，但有一定的检错能力，且易于实现，因此得到广泛应用。12.2.1 奇偶监督码奇偶监督码是奇监督码和偶监督码的统称，是一种最基本的检错码。它是由n-1位信息元和1位监督元组成，可以表示成为（n，n-1）。如果是奇监督码，在附加上一个监督元以后，码长为n的码字中“1”的个数为奇数个；如果是偶监

21、督码，在附加上一个监督元以后，码长为n的码字中“1”的个数为偶数个。设：如果一个偶监督码的码字用A=表示，则：=0（12-5）式中为监督元，“+”为模二和（以后也这样表示，请注意）。式（12-5）通常被称为监督方程。利用式（12-5），由信息元即可求出监督元。另外，如果发生单个（或奇数个）错误，就会破坏这个关系式，因此通过该式能检测码字中是否发生了单个或奇数个错误。奇偶监督码是一种有效地检测单个错误的方法，之所以将注意力集中在检（或纠）单个错，这主要是因为码字中发生单个错误的概率要比发生2个或多个错误的概率大得多。例如，n = 5的码字，如果码字中各码元的错误是互相独立，误码率为10-4，则错

22、1、2、3、4和5位的概率分别为：5、和。由此可见，要检（或纠）错误，首先要解决单个错误，这样才抓住了主要矛盾。一般情况下用上述偶监督码来检出单个错误，检错效果是令人满意的，不仅如此，奇偶监督码的编码效率很高，随n增大而趋近于l。下面就给出以码长n5为例，利用表12-1列出全部偶监督码字：表12-1码长5的偶监督码字序号码字序号码字信息码元a4a3a2a1监督字a0信息码元a4a3a2a1监督字a0000000810001100011910010200101101010030011011101114010011211000501010131101160110014111017011111511

23、110在数字信息传输中，奇偶监督码的编码可以用软件实现，也可用硬件电路实现。图12-4(a)就是码长为5的偶监督码编码器。从图中可以看到，4位码元长的信息组，串行送入四级移位寄存器（输入定时缓冲器），同时经模二运算得到监督元，存入输出缓冲器末级，编码完成即可输出码字。图12-4奇偶监督码的硬件实现12.2.2 行列监督码行列监督码又称水平垂直一致监督码或二维奇偶监督码，有时还被称为矩阵码。它不仅对水平（行）方向的码元，而且还对垂直（列）方向的码元实施奇偶监督。一般Lm个信息元，附加L+m+1个监督元，由L+1行，m+1列组成一个（Lm+L+m+1，Lm）行列监督码的码字。表12-2就是（66，

24、50）行列监督码的一个码字（L5，M10），它的各行和各列对l的数目都实行偶数监督。可以逐行传输，也可以逐列传输。译码时分别检查各行、各列的监督关系，判断是否有错。表12-2（66，50）行列监督码的一个码字1 1 0 0 1 0 1 0 0 00 1 0 0 0 0 1 1 0 10 1 1 1 1 000011 0 0 1 1 100001 0 1 0 1 01010001011 1 0 0 0 111100这种码有可能检测偶数个错误。因为每行的监督位虽然不能用于检测本行中的偶数个错码，但按列的方向就有可能检测出来。可是也有一些偶数错码不可能检测出，例如，构成矩形的四个错码就检测不出来。这

25、种二维奇偶监督码适于检测突发错码。因为这种突发错码常常成串出现，随后有较长一段无错区间，所以在某一行中出现多个奇数或偶数错码的机会较多，这种方阵码适于检测这类错码。前述的一维奇偶监督码一般只适于检测随机错误。由于方阵码只对构成矩形四角的错码无法检测，故其检错能力较强。一些试验测量表明，这种码可使误码率降至原误码率的百分之一到万分之一。二维奇偶监督码不仅可用来检错，还可用来纠正一些错码。例如，当码组中仅在一行中有奇数个错误时，则能够确定错码位置，从而纠正它。12.2.3 恒比码恒比码又称等重码,这种码的码子中1和0的位数保持恒定比例。由于每个码字的长度是相同的，若1、0恒比，则码字必等重。若码长

26、为n，码重为w，则此码的码字个数为，禁用码字数为。该码的检错能力较强，除对换差错（1和0成对的产生错误）不能发现外，其它各种错误均能发现。目前我国电传通信中普遍采用3：2码，该码共有个许用码字，用来传送10个阿拉伯数字，如表12-3所示。这种码又称为5中取3数字保护码。因为每个汉字是以四位十进制数来代表的，所以提高十进制数字传输的可靠性，就等于提高汉字传输的可靠性。实践证明，采用这种码后，我国汉字电报的差错串大为降低。表12-3 3:2数字保护码数字码字012345678901101010111100110110110100011110101111000111010011目前国际上通用的ARQ

27、电报通信系统中，采用3：4码即7中取3码，这种码共有个许用码字，93个禁用码字。35个许用码字用来代表不同的字母和符号。实践证明，应用这种码，使国际电报通信的误码率保持在以下。 单元二十九（2学时）12.3 线性分组码知识要点：分组码 线性分组码 线性分组码的性质 线性分组码的构造 监督矩阵H 生成矩阵G 校验子 汉明码12.3.1 分组码的基本概念分组码是一组固定长度的码组，可表示为（n , k），通常它用于前向纠错。在分组码中，监督位被加到信息位之后，形成新的码。在编码时，k个信息位被编为n位码组长度，而n-k个监督位的作用就是实现检错与纠错。当分组码的信息码元与监督码元之间的关系为线性关

28、系时，这种分组码就称为线性分组码。对于长度为n的二进制线性分组码，它有种可能的码组，从种码组中，可以选择M=个码组（kn）组成一种码。这样，一个k比特信息的线性分组码可以映射到一个长度为n码组上，该码组是从M=个码组构成的码集中选出来的，这样剩下的码组就可以对这个分组码进行检错或纠错。线性分组码是建立在代数群论基础之上的，各许用码的集合构成了代数学中的群，它们的主要性质如下：（1）任意两许用码之和（对于二进制码这个和的含义是模二和）仍为一许用码，也就是说，线性分组码具有封闭性；（2）码组间的最小码距等于非零码的最小码重。在12.2.1节中介绍的奇偶监督码，就是一种最简单的线性分组码，由于只有一

29、位监督位通常可以表示为（n,n-1），式（12-5）表示采用偶校验时的监督关系。在接收端解码时，实际上就是在计算：（12-6）其中， 表示接收到的信息位，表示接收到的监督位，若S0，就认为无错；若S1就认为有错。式（12-6）被称为监督关系式，S是校正子。由于校正子S的取值只有“0”和“1”两种状态，因此，它只能表示有错和无错这两种信息，而不能指出错码的位置。设想如果监督位增加一位，即变成两位，则能增加一个类似于式（12-6）的监督关系式，计算出两个校正子和，而共有4种组合：00，01，10，11，可以表示4种不同的信息。除了用00表示无错以外，其余3种状态就可用于指示3种不同的误码图样。同理

30、，由r个监督方程式计算得到的校正子有r位，可以用来指示-1种误码图样。对于一位误码来说，就可以指示-1个误码位置。对于码组长度为n、信息码元为k位、监督码元为rn - k位的分组码（常记作（n，k）码），如果希望用r个监督位构造出r个监督关系式来指示一位错码的n种可能，则要求：（12-7)下面通过一个例子来说明线性分组码是如何构造的。设分组码（n , k）中k = 4，为了能够纠正一位错误，由式（12-7）可以看到，要求r 3，若取r = 3，则n = k+r = 7。因此，可以用表示这7个码元，用、表示利用三个监督方程，通过计算得到的校正子，并且假设、三位校正字码组与误码位置的关系如表12-

31、4（当然，也可以规定成另一种对应关系，这并不影响讨论的一般性）：表12-4校正字与误码位置S1S2S3误码位置S1S2S3误码位置001010100011a0a1a2a3101110111000a4a5a6无错由表中规定可已看到，仅当一错码位置在时，校正子为1；否则为0。这就意味着四个码元构成偶数监督关系：(12-8a）同理，构成偶数监督关系：（12-8b）以及构成有数监督关系： （12-8c）在发送端编码时是信息码元，它们的值取决于输入信号，因此是随机的。是监督码元，它们的取值由监督关系来确定，即监督位应使式（12-8）的三个表达式中的、和的值为零（表示编成的码组中应无错码），这样式（8-8

32、）的三个表达式可以表示成下面的方程组形式：（12-9）由上式经移项运算，接出监督位（12-10）根据上面两个线性关系，可以得到16个许用码组如表12-5所示：表12-5 （7,4）分组码的所有许用码组信息位监督位信息位监督位信息位监督位信息位监督位a6a5a4a3a2a1a0a6a5a4a3a2a1a0a6a5a4a3a2a1a0a6a5a4a3a2a1a00000000100100011000011101110010001010100011111010101100010001001101010111111000100011100110111001111001010100111接收端收到每个码

33、组后，计算出、和，如不全为0，则可按表12-4确定误码的位置，然后予以纠正。例如，接收码组为，可算出011，由表12-4可知在位置上有一误码。不难看出，上述（7，4）码的最小码距，因此，它能纠正一个误码或检测两个误码。如超出纠错能力，则反而会因“乱纠”而增加新的误码。（说明此类码不适合误码较大的信道！）12.3.2 监督矩阵H和生成矩阵G式（12-9）所述（7，4）码的三个监督方程式可以重新改写为如下形式：（12-11）对于式（12-11）可以用矩阵形式来表示：（12-12）上式可以记作：或，其中（12-13a）（12-13b）（12-13c）通常H称为监督矩阵，A称为信道编码得到的码字。在这

34、个例子中H为rn阶矩阵，P为rk阶矩阵，Ir为rr阶单位矩阵，具有这种特性的H矩阵称为典型监督矩阵，这是一种较为简单的信道编译码方式。典型形式的监督矩阵各行是线性无关的，非典型形式的监督矩阵可以经过行或列的运算化为典型形式。对于式（12-10）也可以用矩阵形式来表示：或者（12-14）比较式（12-13a）和式（12-14）可以看到，如果在Q矩阵的左边在加上一个kk的单位矩阵，就形成了一个新矩阵G：（12-15）这里G称为生成矩阵，利用它可以产生整个码组（12-16）由式（12-15）表示的生成矩阵形式称为典型生成矩阵，利用式（8-16）产生的分组码必为系统码，也就是信息码元保持不变，监督码元

35、附加在其后。12.3.3 校验子S在发送端信息码元M利用式（12-16），实现信道编码，产生线性分组码A；在传输过程中有可能出现误码，设接收到的码组为B。则收发码组之差为：（12-17）这里，表示i位有错，表示i位无错。基于这样的原则接收端利用接收到的码组B计算校正子：（12-18）因此，校正子仅与E有关，即错误图样与校正子之间有确定的关系。对于上述（7，4）码，校正子S与错误图样的对应关系可由式（12-18）求得，其计算结果见表12-6所示。在接收端的译码器中有专门的校正子计算电路，从而实现检错和纠错。表12-6（7，4）码校正子与错误图样的对应关系序号错误码位ESe6 e5 e4 e3 e

36、2 e1 e0S3S2S101234567/b0b1b2b3b4b5b60000000000000100000100000100000100000100000100000100000000000101010001110111011112.3.4 汉明码汉明码是一种能够纠正单个错误的线性分组码。它有以下特点：（1）最小码距，可以纠正一位错误；（2）码长n与监督元个数r之间满足关系式：。如果要产生一个系统汉明码，可以将矩阵H转换成典型形式的监督矩阵，进一步利用Q = PT的关系，得到相应的生成矩阵G。通常二进制汉明码可以表示为：（12-19）根据上述汉明码定义可以看到，12.3.1构造的（7，4）

37、线性分组码实际上就是一个汉明码，它满足汉明码的两个特点。图12-5中给出（7，4）系统汉明码的编码器和译码器电路。（a）发端编码器（b）收端译编码器图12-5（7，4）汉明码的编译码器 单元三十（2学时）12.4 循环码知识要点：码多项式 循环码的生成多项式及其特征循环码是线性分组码的一个重要子集，是目前研究得最成熟的一类码。它有许多特殊的代数性质，这些性质有助于按所要求的纠错能力系统地构造这类码，且易于实现；同时循环码的性能也较好，具有较强的检错和纠错能力。12.4.1 循环码的特点循环码最大的特点就是码字的循环特性，所谓循环特性是指：循环码中任一许用码组经过循环移位后，所得到的码组仍然是许

38、用码组。若（ ）为一循环码组，则（）、（ ）、还是许用码组。也就是说，不论是左移还是右移，也不论移多少位，仍然是许用的循环码组。表12-7给出了一种（7，3）循环码的全部码字。由此表可以直观地看出这种码的循环特性。例如，表中的第2码字向右移一位，即得到第5码字；第6码字组向右移一位，即得到第3码字。表12-7一种（7，3）循环码的全部码字序号码字序号码字信息位a6 a5 a4监督位a3 a2 a1 a0信息位a6 a5 a4监督位a3 a2 a1 a01000000051001011200101116101110030101110711001014011100181110010为了利用代数理论

39、研究循环码，可以将码组用代数多项是来表示，这个多项式被称为码多项式，对于许用循环码A=( )，可以将它的码多项式表示为：（12-20）对于二进制码组，多项式的每个系数不是0就是1，x仅是码元位置的标志。因此，这里并不关心x的取值。而表12-7中的任一码组可以表示为：（12-20）对于二进制码组，多项式的每个系数不是0就是1，x仅是码元位置的标志。因此，这里并不关心x的取值。而表12-7中的任一码组可以表示为：（12-21）例如，表中的第7码字可以表示为： （12-22）在整数运算中，有模n运算。例如，在模2运算中，有1+120（模2），1+231（模2），2360（模2）等。因此，若一个整数m

40、可以表示为:（12-23）则在模n运算下，有mp（模n），也就是说，在模n运算下，一整数m等于其被n除所得的余数。在码多项式运算中也有类似的按模运算法则。若一任意多项式F(x)被一个n次多项式N(x)除，得到商式Q(x)和一个次数小于n的余式R(x)，也就是：（12-24）则可以写为：F(x)R(x)（模N(x)）。这时，码多项式系数仍按模2运算，即只取值0和1，假设：计算x4+x2+1除以x3+1的值可得：（12-25）注意，在上述运算中，由于是模2运算，因此，加法和减法是等价的，在式子中通常用加法运算符，具体模2运算的规则定义如下：模2加0 + 0 = 00 + 1 = 11 + 0 =

41、11 + 1 = 0模2乘00 = 001 = 010 = 011 = 1这样式（12-25）也可以表示为：(12-26)在循环码中，若A(x)是一个长为n的许用码组，则在按模运算下，亦是一个许用码组，也就是假如：（模），可以证明亦是一个许用码组，并且，正是A(x)代表的码组向左循环移位i次的结果。例如，由式（12-22）表示的循环码，其码长n7，现给定i3，则：（12-27）其对应的码组为，它正是表12-7中第3码字。通过上述分析和演算可以得到了一个重要的结论：一个长度为n的循环码，它必为按模（）运算的一个余式。12.4.2 循环码的生成多项式和生成矩阵前k-1位为0的码组（全0码字除外）对

42、应的多项式称为生成多项式，用g(x)表示。可以证明生成多项式g(x)具有以下特性：（1）g(x)是一个常数项为1的r=n-k次多项式；（2）g(x)是的一个因式；（3）该循环码中其它码多项式都是g(x)的倍式。为了保证构成的生成矩阵G的各行线性不相关，通常用g(x)来构造生成矩阵，这时，生成矩阵G(x)可以表示成为：（12-28）其中，因此，一旦生成多项式g(x)确定以后，该循环码的生成矩阵就可以确定，进而该循环码的所有码字就可以确定。显然，式（12-28）不符合形式，所以此生成矩阵不是典型形式，不过，可以通过简单的代数变换将它变成典型矩阵。现在以表12-7的（7，3）循环码为例，来构造它的生

43、成矩阵和生成多项式，这个循环码主要参数为，n7，k3，r4。从表中可以看到，其生成多项式可以用第1码字构造：（12-29）（12-30）在上面的例子中，是利用表12-7给出的（7，3）循环码的所有码字，构造了它的生成多项式和生成矩阵。但在实际循环码设计过程中，通常只给出码长和信息位数，这就需要设计生成多项式和生成矩阵，这时可以利用g(x)所具有基本特性进行设计。首先，生成多项式g(x)是的一个因式，其次g(x)是一个r次因式。因此，就可以先对进行因式分解，找到它的r次因式。下面仍以（7，3）循环码为例进行分析。第一步：对进行因式分解得：（12-31）第二步：构造生成多项式g（x）为了求（7，3

44、）循环码的生成多项式g(x)，要从式（8-31）中找到r=n-k次的因子。不难看出，这样的因子有两个，即：(12-32) (12-33)以上两式都可作为生成多项式用。不过，选用的生成多项式不同，产生出的循环码码组就不同。用式（12-32）作为生成多项式产生的循环码即为表12-7所列。当然，在利用式（12-30）得到生成矩阵G以后，可以通过线性变化，使之成为典型矩阵，这时就可以采用类似式（12-13a）和式（12-15）方法，得到监督矩阵H。除此之外，还可以利用循环码的特点来确定监督矩阵H。由于（n,k）循环码中g(x)是的因式，因此可令：(12-34)这里h（x）称为监督多项式。与式（12-2

45、8）所表示的G(x)相对应，监督矩阵表示为：(12-35)其中是逆多项式。（12-36）对于表12-7中的（7,3）循环码，则：12.4.3 循环码的编、译码方法1.编码过程在编码时，首先需要根据给定循环码的参数确定生成多项式g(x)，也就是从的因子中选一个（n-k）次多项式作为g(x)；然后，利用循环码的编码特点，即所有循环码多项式A(x)都可以被g(x)整除，来定义生成多项式g(x)。根据上述原理可以得到一个较简单的系统循环码编码方法：设要产生（n,k）循环码，m(x)表示信息多项式，则其次数必小于k，而m(x)的次数必小于n，用m(x)除以g(x)，可得余数r(x)，r(x)的次数必小于

46、（n-k），将r(x)加到信息位后作监督位，就得到了系统循环码。下面就将以上各步处理加以解释。（1）用乘m(x)。这一运算实际上是把信息码后附加上（n-k）个“0”。例如，信息码为110，它相当于m(x)+x。当n-k7-34时，m（x）+，它相当于。而希望的到得系统循环码多项式应当是A(x) = m(x) + r(x)。（2）求r(x)。由于循环码多项式A(x)都可以被g(x)整除，也就是：（12-37）因此，用m(x)除以g(x)，就得到商Q(x)和余式r(x)，即（12-38）这样就得到了r(x)。（3）编码输出系统循环码多项式A(x)为：（12-39）例如，对于（7，3）循环码，若选用

47、，信息码110时，则：（12-40）上式相当于：这时的编码输出为：。上述三步编码过程，在硬件实现时，可以利用除法电路来实现，这里的除法电路采用一些移位寄存器和模2加法器来构成。下面将以（7,3）循环码为例，来说明其具体实现过程。设该（7,3）循环码的生成多项式为：，则构成的系统循环码编码器如图12-6所示，图中有4个移位寄存器，一个双刀双掷开关。当信息位输入时，开关位置接“2”，输入的信息码一方面送到除法器进行运算，一方面直接输出；当信息位全部输出后，开关位置接“1”，这时输出端接到移位寄存器的输出，这时除法的余项，也就是监督位依次输出。当信息码为110时，编码器的工作过程如表12-8：图12

48、-6（7，3）循环码编码器顺便指出，由于数字信号处理器（DSP）和大规模可编程逻辑器件（CPLD和FPGA）的广泛应用，目前已多采用这些先进器件和相应的软件来实现上述编码。表12-8 编码器工作过程输入 (m)移位寄存器 (abcd)反馈 (e) 输出 (f) 000000011011101001101011111000000101001000010000010101012.译码过程对于接收端译码的要求通常有两个：检错与纠错。达到检错目的的译码十分简单，可以由式（12-37），通过判断接收到的码组多项式B(x)是否能被生成多项式g(x)整除作为依据。当传输中未发生错误时，也就是接收的码组与发送

49、的码组相同，即A(x)=B(x)，则接收的码组B(x)必能被g(x)整除；若传输中发生了错误，则A(x)B(x)，B(x)不能被g(x)整除。因此，可以根据余项是否为零来判断码组中有无错码。需要指出的是，有错码的接收码组也有可能被g(x)整除，这时的错码就不能检出了。这种错误被称为不可检错误，不可检错误中的错码数必将超过这种编码的检错能力。在接收端为纠错而采用的译码方法自然比检错要复杂许多，因此，对纠错码的研究大都集中在译码算法上。我们知道，校正子与错误图样之间存在某种对应关系。如同其它线性分组码，循环码的译码可以分三步进行：（1）由接收到的码多项式B(x)计算校正子（伴随式）多项式S(x)；

50、（2）由校正子S(x)确定错误图样E(x)；（3）将错误图样E(x)与B(x)相加，纠正错误。上述第（1）步运算和检错译码类似，也就是求解B(x)整除g(x)的余式，第（3）步也很简单。因此，纠错码译码器的复杂性主要取决于译码过程的第（2）步。基于错误图样识别的译码器称为梅吉特译码器，它的原理图如图12-7所示。错误图样识别器是一个具有（n-k）个输入端的逻辑电路，原则上可以采用查表的方法，根据校正子找到错误图样，利用循环码的上述特性可以简化识别电路。梅吉特译码器特别适合于纠正2个以下的随机独立错误。图12-7梅吉特译码器原理图12-7中k级缓存器用于存储系统循环码的信息码元，模2加电路用于纠正错误。当校正子为0时，模2加来自错误图样识别电路的输入端为0，输出缓存器的内容；当校正子不为0时，模2加来自错误图样识别电路的输入端在第i位输出为1，它可以使缓存器输出取补，即纠正错误。循环码的译码