差错控制编码

第3章 信道编码................................................................................................................................................. 2 3.1 差错控制方式 ............................................................................................................................................. 2 3.2 信道编码 ..................................................................................................................................................... 3 3.2.1 差错控制编码的基本原理 .................................................................................................................. 3 3.2.2 差错控制编码的分类 .......................................................................................................................... 4 3.2.3 差错控制编码的基本概念 .................................................................................................................. 5 3.3 常见的几种检错码 ..................................................................................................................................... 7 3.3.1 奇偶校验码 .......................................................................................................................................... 7 3.3.2 水平奇偶校验码 .................................................................................................................................. 8 3.3.3 水平垂直奇偶校验码 .......................................................................................................................... 9 3.3.4 恒比码 .................................................................................................................................................. 9 3.3.5群计数码 ............................................................................................................................................. 10 3.4 线性分组码 ................................................................................................................................................. 11 3.4.1 基本概念 ............................................................................................................................................. 11 3.4.2 线性分组码的编码 ............................................................................................................................ 12 3.4.3 线性分组码的译码 ............................................................................................................................ 16 3.5 循环码 ........................................................................................................................................................ 18 3.5.1 基本概念 ............................................................................................................................................ 18 3.5.2 循环码的编码 .................................................................................................................................... 25 3.5.3 循环码的译码 .................................................................................................................................... 27 3.5.4 常见的几种循环码 ............................................................................................................................ 29 3.6 BCH码 ....................................................................................................................................................... 30 3.7 RS码 ........................................................................................................................................................... 33 3.7.1 RS码的编码 ..................................................................................................................................... 34 3.7.2 RS码的译码 ..................................................................................................................................... 35 3.8 卷积码 ........................................................................................................................................................ 36 3.8.1 基本概念 ............................................................................................................................................ 36 3.8.2 卷积码的图解表示 ............................................................................................................................ 38 3.8.3 卷积码的译码 .................................................................................................................................... 40 3.9 几种新的编码方法 .................................................................................................................................... 42 3.9.1 网格编码调制（TCM） .................................................................................................................... 42 3.9.2 TURBO码 ........................................................................................................................................... 47 8.9.3 LDPC码 .......................................................................................................................................... 49 3.9.4喷泉码 ................................................................................................................................................. 51

本章小结 ...................................................................................................................................................... 56 习 题 .......................................................................................................................................................... 57

1

第3章 信道编码

在数字通信系统中，干扰会使信号产生变形，致使接收端产生误码，这将严重影响数字通信系统的可靠性。为了提高数字通信系统的可靠性，除了可采用均衡技术来消除乘性干扰引起的码间串扰外，还可以通过对所传数字信息进行特殊的处理（即信道编码）对误码进行检错和纠错，进一步降低误码率，以满足通信的传输要求。因此，信道编码是提高数字通信系统可靠性的有效措施之一，能提高传输质量1~2个数量级。信道编码的目的就是通过加入冗余码来减小误码，进而提高数字通信的可靠性。

香农第二定理指出：对于一个给定的有扰信道，若该信道容量为C，则只要信道中的信息传输速率R小于C，就一定存在一种编码方式，使编码后的误码率随着码长n的增加而按指数下降到任意小的值。或者说只要R?C，就存在传输速率为R的纠错码。该定理虽然没有明确指出如何对数据信息进行纠错编码，也没有给出这种具有纠错能力通信系统的具体实现方法，但它奠定了信道编码的理论基础，并为人们从理论上指出了信道编码的努力方向。信道编码的基本思想就是在数字信号序列中加入一些冗余码元，这些冗余码元不含有通信信息，但与信号序列中的信息码元有着某种制约关系，这种关系在一定程度上可以帮助人们发现或纠正在信息序列中出现的错误（也就是误码），从而起到降低误码率的作用。

本章主要分析差错控制编码的基本方法和纠错编码的基本原理，以及常用检错码、线性分组码和卷积码的构造原理等。

3.1 差错控制方式

目前常见的差错控制方式主要有：前向纠错（FEC）、检错重发（ARQ）、混合纠错（HEC）、信息反馈（IF）和检错删除（deletion）等。几种差错控制方式的原理如图3-1所示。

（1）前向纠错(FEC)：发端除了发送信息码元外，还发送加入的差错控制码元。接收端根据接收到的这些码组后，并利用加入的差错控制码元不但能够发现错码，而且还能自动纠正这些错码。如图3-1（a）所示。前向纠错方式只要求单向信道，因此特别适合于只能提供单向信道的场合，同时也适合一点发送多点接收的广播方式。因为不需要对发信端反馈信息，所以接收信号的延时小、实时性好。这种纠错系统的缺点是设备复杂、成本高，且纠错能力愈强，编译码设备就愈复杂。

（2）检错重发(ARQ)：发端将信息码编成能够检错的码组发送到信道，收端接收到一个码组后进行检验，并将检验结果通过反向信道反馈给发端。发端根据收到的应答信号重新发送有错误的码元，直到接收端能够正确接收为止。如图3-1（b）所示。其优点是译码设备不会太复杂，对突发错误特别有效，但需要双向信道。

（3）混合纠错（HFC）：混合纠错方式是前向纠错方式和检错重发方式的结合。如图3―1（c）所示。其内层采用FEC方式，纠正部分差错；外层采用ARQ方式，重传那些虽已检出但未纠正的差错。混合纠错方式在实时性和译码复杂性方面是前向纠错和检错重发方式的折衷，较适合于环路延迟大的高速数据传输系统。

（4）信息反馈（IF）：前三种方式都是在收端识别有无错码，而信息反馈是接收端接收到的消息原封不动的发回发端，由发端将反馈信息和原发送信息进行比较。当发现错误时进行重发。如图3-1（d）所示。该方法的优点是原理和设备简单，且无须纠检错编译码系统。缺点是需要双向信道，而且传输效率较低，实时性较差。

2

发送端信息码可纠正错误的码接收端信息码信道编码器（a） 前向纠错（FEC）示意图信道译码器发送端信息码能够发现错误的码接收端信息码信道编码器应答信号信道译码器（b） 检错重发（ARQ）示意图发送端信息码能够发现并纠正错误的码接收端信息码信道编码器应答信号信道译码器（c） 混合纠错（HEC）示意图信息码信息码信息码发送端反馈信号（信息码）收收端（d) 信息反馈（IF）示意图

图 3-1 差错控制的工作方式

（5）检错删除（deletion）：它和检错重发的区别在于，当接收端发现错误时，立即将其删除，不要求重发。这种方法只适用于少数特定系统中，在那里发送的码元中有大量多余度，删除部分接收码后不影响其应用。

3.2 信道编码

3.2.1 差错控制编码的基本原理

信道编码就是在信息码序列中加入冗余码（即监督码元），接收端利用监督码与信息码之间的某种特殊关系加以校验，以实现检错和纠错功能。下面我们以重复码为例详细介绍检错和纠错的基本原理。

假设要发送一组具有两种状态的数据信息（比如，A和B）。我们首先要用二进制码对数据信息进行编码，显然，用1位二进制码就可完成。编码表如表3―1所示。

假设不经信道编码，在信道中直接传输按表中编码规则得到的0、1数字序列，则在理想情况下，收信端收到“0”就认为是A，收到“1”就是B，如此可完全了解发端传过来的信息。而在实际通信中由于干扰（噪声）的影响，会使信息码元发生错误从而出现误码（比如码元“0”变成“1”、或“1”变成“0”）。从上表可见，任何一组码只要发生错误，都会使该码组变成另外一组信息码，从而引起信息传输错误。 因此，这种编码不具备检错和纠错的能力。

表3-1 编码表

3

A重复码(1,1)码(2,1)码(3,1)码(4,1)码B信息位监督位信息位监督位00 00 000 00011 11 111 111检错个数0123纠错个数0111

当增加1位冗余码，即采用重复码（2，1）。其中，码长为2位，信息位为1位。如用“00”表示A，用“11”表示B。当传输过程中发生1位错误时，码字就会变为“10”或“01”。当接收端接收到“10”或“01”时，只能检测到错误，而不能自动纠正错误。这是因为存在着不准使用的码字“10”和“01”的缘故，即存在禁用码组。相对于禁用码组而言，把允许使用的码组称为许用码组。这表明在信息码元后面附加一位监督码元后，当只发生一位错码时，码字具有检错能力。但由于不能判决是哪一位发生了错码，所以没有纠错能力。

当增加2位冗余码，即采用重复码（3，1）。如用“000”表示A，用“111”表示B。此时的禁用码组为“100”、“010”、“001”、“011”、“101”和“110”。当传输过程中发生1位错误时，码字就会变为“100”、“010”、“001”、“011”、“101”或“110”。例如，当接收端收到“100”时，收端就会按照“大数法则”自动恢复为“000”，认为信息发生了1位错码。此时接收端不仅能检测到1位错误，而且还能自动纠正该错误。但是当出现2位错误时，例如，“000”会错成“100”、“010”或“001”，当接收端收到这三种码时，就会认为信息有错，但不知是那位错了，此时只能检测到2位错。如果在传输过程中发生了3位错，接收端收到的是许用码组，此时不再具有检错能力。因此，这时的信道编码具有检出两位错和两位以下错码的能力，或者具有纠正一位错码的能力。

当增加3位冗余码，即采用重复码（4，1）。如用“0000”表示A，用“1111”表示B。此时接收端能纠正1位错误，用于检错时能检测3位错误。

由此可见，增加冗余码的个数就能增加纠检错能力。

3.2.2 差错控制编码的分类

根据编码方式和不同的衡量标准，差错控制编码有多种形式和类别。下面我们简单地介绍几种主要分类。

(1)根据编码功能可分为检错码、纠错码和纠删码三种类型，只能完成检错功能的码叫检错码；具有纠错能力的码叫纠错码；而纠删码既可检错也可纠错。

(2)按照信息码元和附加的监督码元之间的检验关系可以分为线性码和非线性码。若信息码元与监督码元之间的关系为线性关系，即监督码元是信息码元的线性组合，则称为线性码。反之，若两者不存在线性关系，则称为非线性码。

(3)按照信息码元和监督码元之间的约束方式可分为分组码和卷积码。在分组码中，编码前先把信息序列分为k位一组，然后用一定规则附加m位监督码元，形成n?k?m位的码组。监督码元仅与本码组的信息码元有关，而与其它码组的信息码元无关。但在卷积码中，码组中的监督码元不但与本组信息码元有关，而且与前面码组的信息码元也有约束关系，就像链条那样一环扣—环；所以卷积码又称连环码或链码。

(4)系统码与非系统码。在线性分组码中所有码组的k位信息码元在编码前后保持原

4

来形式的码叫系统码，反之就是非系统码。系统码与非系统码在性能上大致相同，而且系统码的编、译码都相对比较简单，因此得到广泛应用。

(5)纠正随机错误码和纠正突发错误码。顾名思义，前者用于纠正因信道中出现的随机独立干扰引起的误码，后者主要对付信道中出现的突发错误。

从上述分类中可以看到，一种编码可以具有多样性，本章主要介绍纠正随机错误的二进制线性分组码。

3.2.3 差错控制编码的基本概念

1、码长、码重、码距和编码效率

码组又称码字或码矢。码组中编码的总位数称为码组的长度，简称为码长。如，码组 “11001”的码长为5，码组 “110001”的码长为6。

码组中非“0”元的数目（即“1”码元的个数）称为码组的重量，简称码重。常用W表示。如，码组 “11001”的码重为W?3，码组 “110001”的码重也为W?3。它反映一个码组中“0”和“1”的“比重”。

所谓码元距离就是两个等长码组之间对应码位上码元不同的个数，简称码距（也称汉明距）。码距反映的是码组之间的差异程度，比如，00和01两组码的码距为1；011和100的码距为3。那么，多个码组之间相互比较，可能会有不同的码距，其中的最小值被称为最小码距（用d0表示）。它是衡量编码纠/检错能力的重要依据。比如，000、001、110三个码组相比较，码距有1和2两个值，则最小码距为d0?1。

......r个监督位an?1an?2arar?1a0k个信息位码长n?k?r3-2 分组码的结构图

在一个码长为n的编码序列中，信息位为k位，它表示所传递的信息；监督位为r位，它表示增加的冗余位。分组码一般可表示为(n,k)，其中，r?n?k。具体形式如图3-2所示。图中前k位(an?1,an?2,?,ar)为信息位，后面r位(ar?1,ar?2,?,a0)为监督位。则其编码效率Rc可定义为

Rc?kn （3.1）

而其监督元个数r和信息元个数k之比定义为冗余度。因为k?n，所以，Rc?1。显然，编码的冗余度越大，编码效率越低。也就是说，通信系统可靠性的提高是以降低有效性（即编码效率）来换取的。差错控制编码的关键之一就是寻找一种好的编码方法，即在一定的差错控制能力的要求下，使得编码效率尽可能的高，同时译码方法尽可能的简单。

5

2、抗干扰能力与最小码距的关系

最小码距d0与纠/检错能力间有着密切的关系，它们之间的关系为：

AA1eAt1tBd0(a)d0(b)te1td0(c)图3-3 码距与检错和纠错能力间的关系

（1）检测e个随机错误，要求最小码距d0为：

d0?e?1 （3.2）

可用几何图形简要证明（3.2）式。设一个码组A位于O点。若码组A中发生一个错码，则可认为A的位置将移动至以O点为圆心，以1为半径的圆上某点，但其位置不会超出此圆。若码组A中发生两位错码，则其位置不会超出以O点为圆心，以2为半径的圆。依此类推，若码组A中发生e位错码，则其位置不会超出以O点为圆心，以如图3-3（a）所示，若要检测e位错码，则最小码距d0至少应不小于e?1，e为半径的圆。

即d0?e?1。因为d0?e?1时，码组集合中的其它码字均在以A为圆心、以e为半径的圆外，所以就能和错码区别开。

（2）在一个码组内要想纠正t位误码，要求最小码距d0为

d0?2t?1 （3.3）

此式可以用图3-3（b）来说明。图中码组A和B间的距离为d0。码组A或B若发生不多于t位错码时，则其位置均不会超出以t为半径，以原位置为圆心的圆。只要这两

圆不相交，则就不会发生混淆，码字落在那个圆内就可判为对应码字，所以它能够纠正

6

错码。此时，两圆不相交的最小距离为2t?1，故最小码距d0应大于等于2t?1，即

d0?2t?1。

（3）在一个码组内要想纠正t位误码，同时检测出e位误码（e?t）,要求最小码距

d0为

d0?t?e?1 （3.4）

在这种情况下，若接收码组与某一许用码组间的距离在纠错能力t范围内，则将按纠错方式工作；若与任何许用码组间的距离都超过t，则按检错方式工作。可用图3-3（c）来说明。若设检错能力为e，则当码组A中存在e个错码时，该码组与任一许用码组的距离至少应有t?1，否则将进入许用码组B的纠错能力范围内，而被纠为B。

综上所述，要提高编码的纠、检错能力，不能仅靠简单地增加监督码元位数（即冗余度），更重要的是要加大最小码距（即码组之间的差异程度），而最小码距的大小与编码的冗余度是有关的，最小码距增大，码元的冗余度就增大。但当码元的冗余度增大时，最小码距不一定增大。因此，一种编码方式具有检错和纠错能力的必要条件是信息编码必须有冗余，而充分条件是码元之间要有一定的码距。另外，检错要求的冗余度比纠错要低。

信道编码中两个最主要的参数是最小码距d0与编码效率Rc。一般说来，这两个参数是相互矛盾的，编码的检、纠错能力越强，最小码距d0就越大，而编码效率Rc就越小。所以，纠错编码的任务就是构造出编码效率Rc一定时，最小码距d0尽可能大的码；或最小码距d0一定时，而编码效率Rc尽可能大的码。

3.3 常见的几种检错码

3.3.1 奇偶校验码

奇偶校验码是数据通信中最常见的一种简单检错码，它分为奇数校验码和偶数校验码。虽然有两种编码方式，但其编码原理是相同的。其编码规则是：把信息码先分组，形成多个许用码组，在每一个许用码组最后（最低位）加上一位监督码元即可。加上监督码元后使该码组中1的数目为奇数的编码称为奇校验码，为偶数的编码称为偶校验码。根据编码分类，可知奇偶校验码属于一种检错、线性、分组系统码。

奇偶校验码的监督关系可以用以下公式进行表述。假设一个码组的长度为n(在计算机通信中，常为一个字节)，表示为A?(an?1,an?2,?,a0)，其中前n?1位是信息码，最后一位a0为校验位（或监督位），那么，对于偶校验码必须保证

an?1?an?2?an?3???a0?0 （3.5）

7

校验码元（或监督码元）a0的取值（0或1）可由下式决定：

a0?an?1?an?2?an?3???a1 （3.6）

对于奇校验码而言，要求必须保证

an?1?an?2?an?3???a0?1 （3.7）

校验码元a0的取值（0或1）可由下式决定：

a0?an?1?an?2?an?3???a1?1 （3.8）

根据奇偶校验的规则我们可以看到，当码组中的误码为偶数时，校验失效。比如有两位发生错误，会有这样几种情况：00变成11、11变成00、01变成10、10变成01，可见无论哪种情况出现都不会改变码组的奇偶性，偶校验码中1的个数仍为偶数，奇校验码中1的个数仍为奇数。

下面我们讨论奇偶校检码的码距问题。假设两个码组同为奇数（或偶数）码组，如果两组码只有1位不同，则它们的奇偶性就不同，这与假设相矛盾；如果两组码有2位不同，则它们的奇偶性不变。换句话说，构造不出码距为1的奇偶校检码，所以奇偶校验码的最小码距为2。因此，简单的奇偶校验码只能检测出单个或奇数个位发生错误的码组。其检错能力低，但编码效率Rc?n?1n会随着n的增加而增加。因奇偶校验码编码方式较为简单，所以在计算机通信中得到了较为广泛的应用。例如在传递标准ASCII码时，通常采用7比特码元128种字符，在传输时再加1位奇偶校验位，成为8位码组，收端根据是否满足奇偶校验的条件来判断传输过程是否发生错误。

3.3.2 水平奇偶校验码

表3-2 水平奇偶校验码

信 息 码 元0 1 0 1 1 0 1 1 0 0 0 1 0 1 0 1 0 0 1 00 0 1 1 0 0 0 0 1 11 1 0 0 0 1 1 1 0 00 0 1 1 1 1 1 1 1 10 0 0 1 0 0 1 1 1 11 1 1 0 1 1 0 0 0 0监 督 码 元1001011

奇偶校验码检错能力低且不能检测突发错误，为了克服这个缺点，对奇偶校验码进行改进，得到了水平奇偶监督码。其基本原理是先将经过简单奇偶校验编码的码组按行排列成方阵，每一行是一个码组，若有n个码组则方阵就有n行。比如，有经过奇偶校验编码的7个码组01011011001、01010100100、00110000110、11000111001、00111111110、00010011111、11101100001排成方阵共有7行（见表3―2）。传输时发端按列进行传输，

8

即000100111010010010101…1001011。收端按列接收后再按行还原成发端的方阵，然后按行进行奇偶校验，则纠错情况就会发生变化。观察该表可见，因为是逐列发送，在一列中不管出现几个误码（偶数个或奇数个），对应在每一行都只是一位误码，所以都可以通过水平奇偶校验检验出来；但对于每一行（一个码组）而言仍然只能检出所有奇数个错误。与简单奇偶校验编码相比，它除了具备奇偶校验码的检错能力外，还可以检出所有长度小于行数（码组数）的突发错误。

3.3.3 水平垂直奇偶校验码

在上述水平奇偶校验编码的基础上，若再加上垂直奇偶校验编码就构成水平垂直奇偶校验码。比如对表3―2的7个码组再加上一行就构成水平垂直奇偶校验码，如表3―3所示。 水平垂直奇偶校验码在发送时仍按列发送，收端顺序接收后仍还原成表3-3的方阵形式。这种码既可以逐行传输，也可以逐列传输。水平垂直奇偶校验码比简单奇偶校验码多了个列校验，因此，其检错能力有所提高。除了检出行中的所有奇数个误码及长度不大于行数的突发性错误外，还可检出列中的所有奇数个误码及长度不大于列数的突发性错误。同时还能检出码组中大多数出现偶数个错误的情况，比如，在码组1中，头两位发生错误，从01变成10，则第1列的1就变成3个，第2列的1也变成3个，而两列的校验码元都是0，所以可以查出这两列有错误。也就是说，码组中出现了2位（偶数位）误码，但具体是哪一个码组（那一行）出现误码还无法判断。

表3-3 水平垂直奇偶校验码

信 息 码 元0 1 0 1 1 0 1 1 0 0 0 1 0 1 0 1 0 0 1 00 0 1 1 0 0 0 0 1 11 1 0 0 0 1 1 1 0 00 0 1 1 1 1 1 1 1 10 0 0 1 0 0 1 1 1 11 1 1 0 1 1 0 0 0 00 0 1 1 1 0 0 0 0 1监 督 码 元10010110

3.3.4 恒比码

恒比码是码组中1的数目与0 的数目保持恒定比例的一种码。由于恒比码中每个码组均含有相同数目的1和0，因此恒比码又称为等重码或定1码。这种码通过计算接收码组中“1”的数目是否正确，就可检测出有无错误。表3-4是我国邮电部门在国内通信中采用的五单位数字保护电码，它是一种五中取三的恒比码，也称作为3:2恒比码。

9

每个码组的长度为5，其中“1”的个数为3，每个许用码组中“1”和“0”个数的比值

3恒为3/2。许用码组的个数就是5中取3的组合数，即C5?5?42?10，正好可以表示10

个阿拉伯数字。实践证明，采用这种码后，我国汉字电报的差错概率大为降低。不难看出这种码的最小码距是2，它能够检出码组中所有奇数个错误和部分偶数个错误。该码也是非线性分组码，但不是系统码，其主要优点是简单，适用于对电传机或其它键盘设备产生的字母和符号进行编码。

表3-4 3:2恒比码

数 字码 字 数 字码 字 0 0 1 1 0 11 0 1 0 1 12 1 1 0 0 13 1 0 1 1 04 1 1 0 1 05 0 0 1 1 16 1 0 1 0 17 1 1 1 0 08 0 1 1 1 09 1 0 0 1 1

另外，目前国际上的ARQ电报通信系统中采用的3:4码也是一种恒比码，又称为“7”

3中取“3”码。它的码组数量为C7?7?6?53?2?35，代表26个英文字母和其它符号。实践

证明，这种码使通信的误码率保持在10?6以下。

3.3.5群计数码

在奇偶校验码中，我们通过添加监督位将码组的码重配成奇数或偶数。而群计数码就是先将信息码元分组后，计算出信息码组的码重（即码组中“1”的个数），然后用二进制计数法表示并作为监督码元添加到信息码组的后面。比如表3-3中的7个信息码组变成群计数码后的形式见表3-5。收端只要检测监督码元所表示的“1”的个数与信息码元中“1”的个数是否相同来判断错误与否。

表3-5 群计数码

信 息 码 元0 1 0 1 1 0 1 1 0 0 0 1 0 1 0 1 0 0 1 00 0 1 1 0 0 0 0 1 11 1 0 0 0 1 1 1 0 00 0 1 1 1 1 1 1 1 10 0 0 1 0 0 1 1 1 11 1 1 0 1 1 0 0 0 0

监 督 码 元0 1 0 10 1 0 00 1 0 00 1 0 11 0 0 00 1 0 10 1 0 1

10

这种码属于非线性分组系统码，检错能力很强，除了能检出码组中奇数个错误之外，还能检出偶数个1变0或0变1的错误，但对1变0和0变1成对出现的误码无能为力。可以验证，除了无法检出1变0和0变1成对出现的误码外，这种码可以检出其它所有形式的错误。

3.4 线性分组码

在计算机通信中，信源输出的是由“0”和“1”组成的二进制序列，在分组码中，该二元信息序列被分成码元个数固定的一组组信息，每组信息的码元由k位二进制码元组成，则共有2k个不同的组合，即不同的信息。信道编码器就是要对这2k个不同的信息用2k个不同的码组（或码字）表示，2k个码组的位数是一样的。假设为n，且n>k，则这2k个码组的集合就被称作为分组码。简单地说，将信息码进行分组，然后为每组信息码附加若干位监督码元的编码方法得到的码集合称为分组码。为讨论方便，我们把由k位二进制码元构成2k个信息码组用矩阵D表示，则由n位二进制码元组成的分组码中就必须有2k个不同的码组才能代表2k个信息，把这2k个不同的码组用矩阵C表示，则D和C必须一一对应。因为n>k，所以，在一个n位码组中，有n-k个不代表信息的码元，这些码元被称为监督码元或校验码元。显然，如果上述分组码每个码组之间没有关系的话（彼此独立），则对于大的k值或n值（信息码或分组码的码长很大），编码设备会极为复杂，因为编码设备必须储存2k个码长为n的码组。因此，我们需要构造码组之间有某种关系的分组码，以降低编码的复杂性，线性分组码就是满足这一条件的一种分组码。

3.4.1 基本概念

所谓线性分组码就是一种长度为n，其中2k个许用码组（代表信息的码组）中的任意两个码组的模2和仍为一个许用码组的分组码。或者说，可用线性方程组表述码规律性的分组码。这种长度为n，有2k个码组的线性分组码我们称为线性（n，k）码（或（n，k）线性码）。分组码中的每个码组可用向量来表示，即A?(an?1,an?2,?,a0)，其中前k位为信息位，后r位为监督位。其结构如图3-2所示。

线性分组码是一种群码，对于模2加运算具有以下性质：

（1）满足封闭性：即任意两个许用码组之和仍为一许用码组，这种性质也成为自闭率；

（2）有零元：所有信息元和监督元均为零的码组，称为零码，即A0??00?0?。任一码组与零码相运算其值不变，即，Ai?Ai?A0

11

（3）有负元：线性分组码中的任一码组即是它自身的负元，即Ai?Ai?Ai。 （4）满足结合律：即(A1?A2)?A3?A1?(A2?A3)。 （5）满足交换律：A1?A2?A2?A1。

（6）线性分组码的最小码距等于非零码的最小码重，即

d0?minW(Ai) （3.9）

Ai?[n,k]在线性分组码还具有以下特点： （1）d0(A1,A2)?W(A1)?W(A2)； （2）d0(A1,A2)?d0(A2,A3)?d0(A1,A3)；

（3）码字的重量或全部为偶数，或奇数重量的码字数等于偶数重量的码字数。

3.4.2 线性分组码的编码

对于线性分组码而言，信息元与监督元之间的关系可以用一组线性方程来表示。设线性分组码的码字为A?(an?1,an?2,?,a0)，其中前k位为信息位，后r位为监督位。下面以（7，3）码为例来描述线性分组码的编码原理。

在（7，3）线性分组码中，码长n?7，信息元的个数k?3，则监督元的个数r?4。（7，3）码的每一个码组可写成A?(a6,a5,a4,a3,a2,a1,a0)，其中a6,a5,a4为信息位，

a3,a2,a1,a0为监督位。它们之间的监督关系可用线性方程组描述为：

?a3?a6?a5?a4?a?a?a?264 （3.10） ??a1?a5?a4??a0?a6?a5表3-6 （7，3）线性分组码

码 元序 号信息元监督元序 号信息元监督元4 100 11105 101 00116 110 10017 111 0100码 元0 000 00001 001 11012 010 01113 011 1010

因为信息元个数k?3，所以只有8种许用码组。可由监督方程（3.10）写出许用码

12

组，如表3-6所示。 1 生成矩阵

对（3.10）式进行改写，各位码元与信息位a6,a5,a4之间的关系为：

?a6?a6?a?a5?5?a4?a4??a3?a6?a5?a4 （3.11） ?a?a?a64?2?a1?a5?a4?a?a?a65?0将式（3.11）用矩阵表示

?a6??1?a??0?5???a4??0????a3???1?a2??1????a1??0?a??1?0??或 ?a6记A??a6a5a4a3a2a1a0???a600?10??01??a6??? （3.12） a11???5??01???a4???11?10???1001101?? （3.13） a4???0101011????0011110??a5a5a4a3a2a1a0?，M??a6a5a4?，

?1001?101???IG??0101?011???3??0011?110??Q? （3.14）

则式（3.12）和（3.13）分别可简记为

AT?GT?MT （3.15）

A?M?G （3.16）

其中，G称为生成矩阵，是一个3?7阶的矩阵。G的行数是信息元的个数，列数是码长。

I3为3?3阶的单位方阵，其行数是信息元的个数；Q为3?4阶的矩阵，其行数是信息元的个数，列数是元的个数。根据（3.16）式，由信息位和生成矩阵G就可以产生全部码组。

可将其理论推广到任意线性分组码。对于一个(n,k)线性分组码而言，生成矩阵G是

13

一个k?n阶的矩阵，也可分为两部分，即

G??Ik其中，

?q11?qQ??21????qk1Q? （3.17）

q12q22?qk2?q1r??q2r?? （3.18） ?????qkr?Q是一个k?r阶矩阵；Ik为k阶单位方阵。把具有?IkQ?形式的生成矩阵称为典型生

成矩阵。非典型形式的生成矩阵经过运算一定能化为典型矩阵。

（n，k）线性分组码完全由生成矩阵G的k行元素决定，即任意一个分组码码组都是G的线性组合。而（n，k）线性码中的任何k个线性无关的码组都可用来构成生成矩阵，所以，生成矩阵G的各行都线性无关。如果各行之间是线性相关的，就不可能由G生成2k个不同的码组了。其实，G的各行本身就是一个码组。如果已有k个线性无关的码组，则可用其直接构成G矩阵，并由此生成其余码组。

综上所述，由于可以用一个k×n阶矩阵G生成2k个不同的码组，因此，编码器只需储存G矩阵的k行元素（而不是一般分组码的2k码组），就可根据信息向量构造出相应的一个分组码码组（或根据信息码矩阵构造出相应的一个分组码矩阵），从而降低了编码的复杂性，并提高了编码效率。 2 监督矩阵

将方程（3.10）式移项，可得到四个相互独立的监督方程组：

?0?a6?a5?a4?a3?a?a4?a2?0?6 （3.19） ?a?a?a?0541???a0?0?a6?a5将式（3.19）可用矩阵表示为

?1?1??0??111101111000010010000?a6??a?50????0??a4???0????a3???0??OT （3.20） 0????0???a2???1????0??a1??a??0?或

14

?a6a5a4a3a2a1?1?1??1?a0???1?0??0?0?101010001?11??10??00???0000??O （3.21） 00??10?01??记A??a6a5a4a3a2a1a0?，O??0000?，OT为O的转置，

?1?1H???0??110111110????1000010000100?0????PI4? （3.22） 0??1?则式（3.20）可简记为

H?AT?OT （3.23）

或

A?HT?O （3.24）

其中，HT表示H的转置。H被称为监督矩阵，或校验矩阵。只要监督矩阵H给定，编码时监督位和信息位的关系就完全确定了。由（3.22）式可看出，H的行数就是监督关系式的数目，它等于监督位（监督元）的数目4，列数是码长7。监督矩阵H的每行中“1”的位置表示相应码元之间存在的监督关系。例如，H的第一行1111000表示监督位a3是由信息位a6a5a4之和决定的。式（3.22）中的H矩阵可以分成P和I4两部分。其中，P是一个4?3阶矩阵； I4为4阶单位方阵；3表示信息位（信息元）个数，4表示监督位（监督元）个数。（3.24）式说明线性分组码中任一码组与校验矩阵H的转置相乘，其结果为r位全零向量，因此，用校验矩阵检查二元序列是不是给定分组码中的码组非常方便，“校验”之名由此而来。

可将其理论推广到任意线性分组码。对于一个(n,k)线性分组码而言，监督矩阵H是一个r?n阶的矩阵，也可分为两部分，即

H??PIr? （3.25）

其中，

?p11?pP??21????pr1

p12?q22???pr2?p1k?p2k?? （3.26） ???prk?15

P是一个r?k阶矩阵；Ir为r阶单位方阵。把具有?PIr?形式的监督矩阵称为典型监督

矩阵。根据典型监督矩阵和信息码元很容易算出各监督码元。非典型形式的监督矩阵经过运算一定能化为典型矩阵。

由代数理论可知，监督矩阵H的各行应该是线性无关的，否则将得不到r个线性无关的监督关系式，也得不到r个独立的监督位。若一矩阵能写成典型阵形式?PIr?，那么其各行一定是线性无关的。 3 监督矩阵和生成矩阵间的关系

由上面的推导可知，生成矩阵G与监督矩阵H之间有一一对应关系。由于G的每一行都是码字，因此它必然满足公式（3.23），即

H?AT?OT

所以，

?PIn?k???Ik?I?TQ???PIn?k???kT??Q?T???PI?IQkn?k?? （3.27） T???P?Q???OT其中，O为k?r阶零矩阵；?为模2加。只有当P?QT时，式（3.27）才为零。因此，生成矩阵可以写成

G??IkH??PQ????IkPT?? （3.28） In?k?? （3.29）

TIn?k???Q?由此可见，只要知道生成矩阵G，就可以得到监督矩阵H，反之也亦然。所以线性分组

码由生成矩阵或监督矩阵来完全确定。

3.4.3 线性分组码的译码

由前面的讨论可以看出，若某一码字为许用码组，则必然满足式（3.24）。利用这一关系，接收端就可以用接收到的码组和事先与发端约定好的监督矩阵相乘，看是否为零。若满足条件，则认为接收正确；反之，则认为传输过程中发生了错误，进而设法确定错误的数目和位置。

假设发送码组为A?(an?1,an?2,?,a0)，接收码组为B?(bn?1,bn?2,?,b0)。由于发送码组在传输的过程中会受到干扰，致使接收码组与发送码组不一定相同。因此，定义发送码组和接收码组之差为

B?A?E(模2和) （3.30）

E是传输中产生的错码行矩阵，即

16

E??e1e2?e0? （3.31）

其中，

?0当bi?aiei?? （3.32）

?1当bi?ai若ei?0，表示该位接收码元无误；若ei?1，则表示该位接收码元有误。E是一个由“1”和“0”组成的行矩阵，它反映误码状况，被称为错误图样。例如，若发送码组

A??1001101?，接收码组B??1001001?，显然B中有一个错误。由（3.30）可得错误图样为E??0000100?。可见，E的码重就是误码的个数，因此E的码重越小越好。另外，式（3.30）也可以改写为

B?A?E （3.33）

当接收端接收到码组B时，可用监督矩阵H进行校验，即将接收码组B代入式（3.24）进行验证。若接收码组中无错码，即E?O，则B?A?E?A。即把B代入式（3.24）后该式仍然成立，则有

B?HT?O （3.34）

当接收码组有误时，即E?O，则B?A?E。即把B代入式（3.24）后该式不成立，则有B?HT?O。我们定义

B?HT?S （3.35）

将B?A?E代入式（3.35）中，可得

S?B?HT?(A?E)?HT （3.36） TT?A?H?E?H?E?HT其中，S是一个r维的行向量，被称为校正子，或伴随式。式（3.36）标明伴随式S与错误图样E之间有确定的线性变换关系，而与发送码组A无关。所以，可以采用伴随式S来判断传输中是否发生了错误。若伴随式S与错误图样E之间一一对应，则伴随式S将能代表错码发生的位置。例如，A??1001101?，B??1001001?，则E??0000100?，把（3.22）式的H代入（3.35）式，可得S??0100?。 为了进一步分析码组中不同码元发生一位错码的情况，仍以表3-6中的（7，3）线性分组码为例，来描述伴随式与错误图样之间的对应关系。如表3-7所示。

从表3-7可以看出：发生一位错误时，ST与监督矩阵H的列一一对应。如b0发生错误，则ST与监督矩阵H的最后一列相同；b1发生错误，则ST与监督矩阵H的倒数第二列相同，以此类推。故接收端可以根据这种关系纠正一位错误。对于(n,k)线性分组

17

码，S有2r中不同的形式，可代表2r?1种错误图样。为了指明单个错误的位置，必须要求：

表3-7 伴随式与错误图样的对应关系

编 号 错码位置ES1 0000001 0001b0b12 0000010 00103 0000100 0100b2b34 0001000 10005 0010000 1110b46 0100000 1011b5b67 1000000 1101

2r?1?n （3.37）

注意：若传输过程中错码的位置不止一位时，S可能与表3-7中所列的任意一种都

不同，这时系统只能检错而不能纠错，并根据不同系统的要求将该码组丢弃或重发。此时，S也有可能正好与发生一位错误时的某种伴随式相同，这样经纠错后反而“越纠越错”。在传输过程中，发送码组的某几位发生错误后成为另一许用码组，这种情况接收端无法检测，称这种为不可检测的错误。不过从统计学的观点来看，这种情况出现的概率要小得多，可忽略。

从以上分析可以得到线性分组码的译码过程为： （1）根据接收码组B计算其伴随式S；

（2）根据伴随式S找出对应的错误图样E，并确定误码位置； （3）根据错误图样E和A?B?E得到正确的码组A。

3.5 循环码

循环码是线性分组码的一个重要分支。循环码有许多特殊的代数性质，基于这些性质，循环码有较强的纠错能力（即它既能纠正独立的随机错误又能纠正突出错误），而且其编码和译码电路很容易用移位寄存器实现，因而在FEC系统中得到了广泛的应用。

3.5.1 基本概念

循环码可定义为：对于一个（n，k）线性分组码，若其中的任一码组向左或向右循环移动任意位后仍是码组集合中的一个码组，则称其为循环码。循环码是一种分组码，前k位为信息码元，后r位为监督码元。它除了具有线性分组码的性质之外，还具有一个独特的性质即循环性。所谓循环性，是指任一许用码组经过循环移位后所得到的码组仍为一许用码组。

若A?(an?1,an?2,?,a0)是循环码中的一个许用码组，对它左循环移位一次，得到移位i次得到Ai?(ai?1,ai?2,?,a0,an?1,ai)还是许A1?(an?2,?,a0,an?1)也是一个许用码组，

18

用码组。不论右移或左移，移位位数多少，其结果均为循环码组。以（7，3）循环码和（6，3）循环码为例，其全部码组见表3-8。

表3-8 （7，3）循环码和（6，3）循环码的全部码组

编 号（7，3）循环码（6，3）循环码1 0 0 0 0 0 0 0 0 0 0 0 0 02 0 0 1 1 1 0 1 0 0 1 0 0 13 0 1 0 0 1 1 1 0 1 0 0 1 04 0 1 1 1 0 1 0 0 1 1 0 1 15 1 0 0 1 1 1 0 1 0 0 1 0 06 1 0 1 0 0 1 1 1 0 1 1 0 17 1 1 0 1 0 0 1 1 1 0 1 1 08 1 1 1 0 1 0 0 1 1 1 1 1 1

由表3-8可看出：（7，3）循环码有两个循环圈，如图3-4（a）所示。其中，编号为1的全零码组自成循环圈，其码重为W?0；另一个是剩余码组组成的循环圈，其码重为W?4。（6，3）循环码的循环圈有四个，如图3-4（b）所示。（6，3）循环码构成了码重分别为0、2、4和6的循环圈。由图3-4可得，同一循环圈上的码字具有相同的码重。

左移左移2W=053W=46487 图3-4（a） （7，3）循环码的循环圈

左移左移左移左移2W=01W=6838W=2564W=47 图3-4 (b) （6，3）循环码的循环圈

为了便于用代数理论分析循环码，可以将循环码的码字用代数多项式来表示，把这

19

个表示码字的代数多项式称为码多项式。把码长n的码组A?(an?1,an?2,?,a0)可表示为

T(x)?an?1xn?1?an?2xn?2???a1x?a0 （3.38）

例如，若码字为1110100，则其对应的码多项式为

T(x)?1?x6?1?x5?1?x4?0?x3?1?x2?0?x?0 （3.39） 6542?x?x?x?x在码多项式中，变量x称为元素，其幂次对应元素的位置，它的系数即为元素的取值（我们不关心x本身的取值），系数之间的加法和乘法仍服从模2规则。如式（3.39）中 1仅表示码元出现在a6、a5、a4和a2位上，其余均为0。 1 码多项式的按模运算

下面我们来介绍多项式的按模运算。如果一个多项式F(x)被另一个n次多项式

N(x)

除，得到一个商式Q(x)和一个次数小于n的余式R(x)，即

F(x)?N(x)Q(x)?R(x) （3.40）

可记作为：

F(x)?R(x)则称作为在模N(x)运算下，F(x)?R(x)。

[modN(x)] （3.41）

x2例如 ，x?1被x?1除时，由于x?1?x?3，所以

x?15352x5?1?x2[mod(x3?1)]

注意：在模2计算中，系数只能为“0”或“1”，故在多项式的余式中是x?1，而不是?x?1。

将式(3.38)乘以x，再除以(xn?1)，则可得：

an?2xn?1?an?3xn?2???a1x2?a0x?an?1xT(x)?an?1? （3.42） nnx?1x?1式（3.42）表明：码多项式T(x)乘以x再除以(xn?1)所得余式就是码组左循环一次的码多项式。由此可知，循环码左循环移位i次后的码多项式就是将xiT(x)按模(xn?1)做运算后所得的余式。

2 循环码的生成多项式和生成矩阵

我们在前面已经讲过，循环码属于线性分组码，它除了具有循环特性外，还具有线

20

xn?k?m(x)r(x) （3.60） ?Q(x)?g(x)g(x)例如，选定g(x)?x4?x3?x2?1，则

xn?k?m(x)x6?x5x3?12 （3.61） ?4?(x?1)?43232g(x)x?x?x?1x?x?x?1则上式相当于

11000001001?101? （3.62）

1110111101（5）编出的码字T(x)为

T(x)?xn?k?m(x)?r(x) （3.63）

在上例中的码字为T(x)?1100000?1001?1101001，它就是表3-8中第7码组。 上述几个编码步骤可以用除法电路来实现。除法电路由(n?k)个移位寄存器、多个模2加法器和一个双刀双掷开关K构成。假设生成多项式为：

g(x）?gn?kxn?k?gn?k?1xn?k?1???g1x?g0 （3.64）

如果gi?1，说明对应的移位寄存器的输出端有一个模2加法器（即有连线）；如果gi?0，说明对应的移位寄存器的输出端没有一个模2加法器（即无连线）。

下面以（7,3）循环码为例，设其生成多项式为g(x)?x4?x3?x2?1。（7,3）系统循环码的编码器原理如图3-5所示。在该循环码中，除法电路由四级移位寄存器“D0D1D2D3”以及模2加法器构成，反馈线的连接与g(x)的非0系数相对应。

1-3拍与门24-7拍D0D1D2输入信息组D3与门1输出码字

图3-5 （7,3）系统循环码的编码器原理

首先，在编每组码之前，四级移位寄存器先清0。当三位信息码元输入时，门

1断开，门2关闭，三位信息码元按节拍直接由“或”门输出，三拍过后移位寄存器中保留了除法运算求出的余数(监督码元)。从第4拍开始、门1断开，门2关闭。移位寄存器中的除法余项依次输出，连同前面已送出的信息组一起组成一个码字。

26

移位四次后，移位寄存器中的内容已全部送完。编码器的工作过程见表3-10。

表 3-10 （7,3）循环码的编码过程

移位次序输 入门1门2移位寄存器D0 D1 D2 D3输 出0 / 0 0 0 0 /断接1 11 0 1 1 1 2 10 1 0 1 1开通3 01 0 0 1 04 05 06 07 0接通断 开0 1 0 0 10 0 1 0 00 0 0 1 00 0 0 0 1

3.5.3 循环码的译码

根据接收端译码目的的不同（检错还是纠错），循环码的译码原理与实现方法有所不同。纠错码的译码是该码能否得到实际应用的关键问题，因为译码器通常要比编码器复杂得多。因此，对纠错码的研究大都集中在译码的算法上。

在循环码中，由于任一发送码组多项式都能被生成多项式g(x)整除，因此可以利用接收码组能否被g(x)所整除来判断接收码组R(x)是否出差错。当传输中未发生错误时，接收码组与发送码组相同，即R(x)?T(x)，接收码组R(x)必定能被g(x)整除；若码组在传输中发生错误，则R(x)?T(x)，R(x)被g(x)除时可能除不尽。可见，循环码译码器的核心仍是一个除法电路和缓冲移位寄存器，其检错译码原理框图如图3-6所示。图中的除法电路与编码器中的除法电路相同。在此除法电路中进行了

R(x)运算。若余数g(x)为0，表示R(x)中无错误，此时就将暂存在缓冲寄存器中的接收信息码组送至输出端；若余数不为零，则表示R(x)中有错误，此时可将缓冲寄存器中的接收码组删除，并向发端发送重传指令，要求将该码重传。

缓存移位寄存器输入码组除法电路反相器重发指令余式=0，输出0；余式≠0,输出1。与信息码门

图3-6 检错译码器原理框图

27

另外，需要指出的是，当接收码组中有错码时，也有可能被g(x)所整除，但这时的错码就不能被检出了，这种错误被称为不可检错误。不可检错误中的错码数必定超过了这种编码的检错能力。

在接收端为纠错而采用的译码方法比检错时复杂。为了能够纠错，要求每个可纠正的错误图样必须与一个特定余式有一一对应关系。只有这样，才可能从余式中唯一地决定错误图样，从而纠正错码。因此，纠错可按下述步骤进行：

（1） 用生成多项式g(x)除接收码组R(x)?T(x)?E(x)，得出余式r(x)； （2） 按余式r(x)用查表法，或由接收到的码多项式R(x)计算伴随式S(x)； （3） 由校正子S(x)确定其错误图样E(x)，这样就可确定错码的位置。 （4） 利用T(x)?R(x)?E(x)可得到纠正错误后的原发送码组T(x)。

上述（1）、（2）步运算较为简单，与检错码时的运算相同。第（4）步也较为简单。因而，纠错译码器的复杂性主要取决于第（3）步。

由（3.57）式可知，用接收码多项式R(x)除以生成多项式g(x)得到的余式，就是循环码的伴随式S(x)，这就可以简化伴随式的计算。同时，由于循环码的伴随式S(x))与循环码—样，也具有循环移位特性(即某码组循环移位i次的伴随式，等于原码组伴随式在除法电路中循环移位i次所得到的结果)。因此，对于只纠正—位错误码元的译码器而言，可以针对接收码组中单个错误出现在首位的错误图样及其相应的伴随式来设计组合逻辑电路。然后利用除法电路中移位寄存器的循环移位去纠正任何位置上的单个错误。

下面以（7,3）循环码为例，设计一个能够纠正一位错误的循环码译码电路。设其生成多项式为g(x)?x4?x3?x2?1。

假设（7,3）循环码译码器按错误图样（1000000）来设计，于是

S(x)?e(x)?x6?x3?x2?x即 S?[111(模g(x))(模g(x))

，则其译码电路如图3-7所示。 0]D0D1D2D3与门反相M=1信号使各存储单元清零7级移位寄存器输入接收码组输出码字

图3-7 （7,3）循环码的译码电路

28

设发送的码字A?[0111010]，接收码组B?[1111010]，其译码过程见表3-11。清零后在第1~7拍，接收码字B一方面被送入移位寄存器，一方面被送入g(x)除法电路计算伴随式，在第7拍结束时得到S?[1110]。随后与门呈开的状态并输出纠错信号M?1，对接收码字B的第一位实施纠错，同时M?1信号使D0~D3清零。第8~14拍移位寄存器中内容依次输出，由于错误码元已被纠正，输出

A?[0111010]。

表 3-11 （7,3）循环码译码过程

节拍0 1 234567891011121314BM移 位 寄 存器状态x0 x1 x2 x3 x4 x5 x60 0 0 0 0 0 0伴 随 式 状 态D0 D1 D2 D30 0 0 01 0 0 01 1 0 01 1 1 01 1 1 11 1 0 01 1 1 00 1 1 10 0 0 00 0 0 00 0 0 00 0 0 00 0 0 00 0 0 00 0 0 0纠正后的码组1111010000000010000001 0 0 0 0 0 01 1 0 0 0 0 01 1 1 0 0 0 01 1 1 1 0 0 00 1 1 1 1 0 01 0 1 1 1 1 00 1 0 1 1 1 10 0 1 0 1 1 10 0 0 1 0 1 10 0 0 0 1 0 10 0 0 0 0 1 00 0 0 0 0 0 10 0 0 0 0 0 00 0 0 0 0 0 00111010

在实际中，常用循环码的译码方法主要还有梅吉特译码、捕错译码和大数逻辑译码等。感兴趣者可参阅有关信道编码技术的专著。另外，循环码的译码除采用硬件法外，还可以按照循环冗余校验原理用软件手段，即软件法来实现。

3.5.4 常见的几种循环码

循环码具有检错能力强（即它对随机错误和突发错误都能以较低冗余度进行严格检

29

验），且实现编码和检错电路相对简单，故在计算机通信中得到了广泛应用。 CRC用于检错，一般能检测如下错误； (1)突发长度l?n?k的突发错误；

(2)大部分突发长度l?n?k?1的错误(不可检测的这类错误只占2?(n?k?1)； (3)大部分突发长度l?n?k?1的错误(不可检测的这类错误只占2?(n?k)； (4)所有与许用码组的距离小于dmin的错误；

(5)所有奇数个随机错误；

用于进行CRC除法的码多项式（即生成多项式）有多种，在计算机通信中广泛使用的有以下四种：

（1） CRC_12型码

这种码用于长度为6bit的同步系统，检验码组长为12位，其生成多项式为

g(x)?x12?x11?x3?x2?x?1 （3.65）

它能检测出长度在12位以内的突发错误。

（2） CRC_16型码

这种码用于长度为8bit的同步系统，检验码组长为16位，其生成多项式为

g(x)?x16?x15?x2?1 （3.66）

它能检测全部16位以下和16位长的突发错误以及99%的长度大于16位的突发错误。。

（3） CRC_CCITT型码

这种码也用于长度为8bit的同步系统，检验码组长为16位，其生成多项式为

g(x)?x16?x12?x5?1 （3.67）

它的检测能力同CRC_16型码。

（4） CRC_32型码

这种码用于用于长度为8bit的同步系统，检验码组长为12位，其生成多项式为

g(x)?x32?x26?x23?x22?x16?x12?x11?x10?x8?x7?x5?x4?x2?x?1 （3.68）

3.6 BCH码

BCH码是一类纠正多个随机错误的循环码，是以3个发现者————博斯(Bose)、查德胡里(Chaudhuri）和霍昆格姆(Hocquenghem)姓氏的字头命名的。这是迄今为止发现的最好的线性分组码之一。BCH码的重要性在于它解决了生成多项式与最小码距之间的关系问题。该码的纠错能力很强，且构造简便。在译码、同步等方面有许多独特的优点，已被许多实际系统所采用，这里只作简单的介绍。

首先引入本原多项式的概念。若一个n次多项式f(x)满足下列条件： （1）f(x)为既约多项式(即不能分解因式的多项式)； （2）f(x)可整除xn?1，其中n?2m?1；

30

(2) 由伴随式求出错误位置多项式；

(3) 由错误位置多项式求出错误位置值； (4) 由错误位置值求出对应的错误值； (5) 求出错误图样，纠错成功。

相对于RS码单一的编码方法，RS的译码算法有许多种，主要是频域译码和时域译码方法，其中错误多项式的计算是问题的重点和难点，相对应的算法也有许多，主要有BM算法，FONEY算法，由于篇幅的限制，感兴趣者可参阅相关资料。

3.8 卷积码

卷积码是由伊利亚斯提出，与前面所介绍的分组码有很大不同。通常情况下，为了达到一定的纠/检错能力和编码效率，分组码的码长较大。而译码时须把整个码组接收后方可进行，因此而产生的时延会随码长的增加而线性增长。对于卷积码而言，其信息码个数和码长通常较小，故时延小，特别适合于以串行形式传输的场合。另外，与分组码相比，卷积码在任何一个码组中的监督码元都不仅与本码组的信息码元有关，而且还与前面若干个码组的信息码元有关，其纠错能力随着前面若干个码组数的增加而增加。故在实际应用中，卷积码的性能优于分组码，而且设备简单。

正因为卷积码的许多优良性能，使它得到了广泛的研究和应用。但目前尚未找到较严密的数学手段，能将纠／检错能力与码的构成十分有规律地联系起来，一般采用计算机搜索来寻找合适码组，其译码算法也有待于进一步研究与完善。本节从实例人手，分析和讨论卷积码的基本性能。

3.8.1 基本概念

121 2 ? k1 2 ? kN1 2 ? k?1 2 ? k输入序列输入序列1 2 ? n

图3-9 卷积码编码器的一般形式

卷积码编码器的一般形式如图3-9所示。它主要由移位寄存器和加法器组成。输入移位寄存器包括(m?1)段，每段有k级，共(m?1)k位寄存器，负责存储每段的k个信息元；各信息码元通过n个模2加法器相加，产生每个输出码组的n个码元，并寄存在一个n级的移位寄存器中输出。整个编码过程可以看成是将输入信息序列与由移位寄存器和模2加法器之间连接所决定的另一个序列的卷积，卷积码由此而得名。卷积码通常记为（n,k,m），其中，m为子码个数；n为码长；k为码组中的信息码元的个数。在卷积

36

码的译码过程中，不但从该时刻收到的码组中提取信息，还可以利用以后的(m?1)个子码来提取信息。

输入S1m1S2m1S3C1输出C2图3-10 （2,1,2）卷积码编码器

下面以（2,1,2）卷积码为例加以说明。图3-10该卷积码的编码器，它由移位寄存器、模2加法器及开关电路组成。在起始状态时各级移位寄存器清零，即s1s2s3为000。当第1个输入比特为0时，输出比特为00；若输入比特为1时，则输出比特为11。在第二个比特输入时，第一个比特右移一位，则输出比特同时受当前输入比特和前一个输入比特的影响。（2,1,2）卷积码的输出码字C为

c1?s1?s2?s3 （3.75） c2?s1?s3 （3.76）

表3-14 （2,1,2）编码器的工作过程

S1S1S210011a10101b01101d11000c00110b01011c00000a00000aC1C2状态 当输入数据为11010时，输出码字可由（3.75）和（3.76）计算出来。表3-14列出了所有数据输入后的输出码字。为了使全部数移出，数据位需加3个0。

由上表计算过程可推知，（n,k,m）卷积码编码器的每1位输入比特会影响(m?1)个输出码字，故称(m?1)为编码约束度。每个子码有n个码元，则在卷积码中有约束关系的最大码元长度为(m?1)n，称为编码约束长度。（2,1,2）卷积码的编码约束度为3，编码约束长度为6。当有k位数据输入时，输出码字序列共有

N?(k?m+1)n （3.77）

卷积码的编码效率为

37

R?kk （3.78） ?N(k?m?1)n若卷积码子码中前k位码元是信息码元的重现，则该卷积码称为系统卷积码，否则称为非系统卷积码。图3-10编码器产生的(2，1，2)码是非系统码。

3.8.2 卷积码的图解表示

0000aa=00状b=01态c=10d=11a11b00a1011cb010信息起点ad11110c0011abb0101d10dc信息 1 1 0 1图3-11 （2,1,2）卷积码的树状图

描述卷积码的方法主要有图解表示法和解析表示法两类。对卷积码虽然可以用矩阵方法描述，但比较抽象，对初学者一时难于掌握。图解方法对编码过程的描述比较直观，初学者容易掌握。常用的图解法有3种：树状图、状态图和网格图。 1 树状图

树状图描述的是在任何数据序列输入时，码字所有可能的输出。对应于图3-10所示的(2，1，2)卷积码的编码电路，其树图如图3-11所示。

在树状图3-11中，从节点a开始，此时移位寄存器状态为00。用a、b、c、d表示s3s2的四种可能状态00、01、10和11。从a点出发分为两条支路。若第1位数据s1?1时，码字c1c2为11，从起点通过下支路到达状态b，即s3s2为01；若第1位数据s1?0时，

38

??111001110001100011100111000110bcdabcdabcdabcd00a上半部下半部

码字c1c2为00，从起点通过下支路到达状态a，即s3s2为00。输入第2个比特时，移位寄存器右移1位，以此类推，便可求得整个树状图。图3-11可见，从第3条支路起，树状图呈现出重复性，即图中表明的上、下半部是相同的。这说明从第4位输入起，输出码字已与第1位数据无关了，从中阐明前述编码约束度为3的含义。当输入信息为11010时，在树状图中用点线标出其轨迹，并得到输出码字为11010100??，与表3-14所列的结果相一致。 2 状态图

观察图3-11树状图的重复性，可把当前状态和下一状态之间的码变换关系用更为紧凑的图形表示，即还可以用状态图来描述。图3-12就是该(2,1,2)卷积码的状态图。

当前状态a=00b=01c=1001d=1110(a)d=11c(b)输出001111000110c=101101下一状态a=0011b=0100a0010d10b01

2)图3-12 (2,1,卷积码的状态图

在状态图中，把树状图中具有相同状态的节点合并在一起。实线表示数据为0的路

径；虚线表示数据为1的路径，并在路径上写出相应的输出码字，即为图3-12（a）的状态图。再把目前状态与下一行状态重叠起来，即可得到图3-12（b）所示的反映状态转移的状态图。图(b)中的4个节点分别表示a、b、c、d，对应取值与图（a）相同。每个节点有二条弧线离开该节点，弧线旁的数字即为输出码字。当输入信息为11010时，状态转移过程为a?b?d?c?b，则可读出输出的码序列为11010100??，与表3-14所列的结果相一致。

状态a=000011b=01001100111110100010110000110011111000c=100101010101d=111001100110

2)图 3-13 (2,1,卷积码的网格图

39

3 网格图

将状态图在时间上展开，便得到第三种图解方法即网格图，或称笆篱图，如图3-13、3-14所示。网格图中支路上标明的码元为输出比特，自上而下4行节点表示a、b、c、d四种状态。图3-13画出了所有可能数据输入时状态转移的全部可能轨迹。实线表示数据为0；虚线表示数据为1，线条旁边数字为输出码字，各节点表是相应的状态。图3-14画出了当输入信息为11010时的过程轨迹。

a11b0100c01db10c11a

2)图 3-14 (2,1,卷积码的过程轨迹

通常，对于有m个互相约束的子码（段）的卷积码，它应有2m?1种可能状态（节点），从第m节点（从左向右计数）开始，网格图形开始重复而完全相同。

上述三种图解方法，不但有助于求解输出码序列，且可直观地了解其编码过程。

3.8.3 卷积码的译码

卷积码的译码可分为代数译码和概率译码两大类。在卷积码发展过程中早期普遍采用代数译码。代数译码利用生成矩阵和监督矩阵来译码，该方法的硬件实现简单，但性能较差。最主要的方法是大数逻辑译码或门限译码。现在，概率译码越来越受到重视，已成为卷积码最主要的译码方法。概率译码中比较实用的有两种：维特比译码和序列译码。这里将简要讨论这几种译码方法 1 维特比译码

维特比译码是一种最大似然译码算法。最大似然译码算法的基本思路是，把接收码字与所有可能的码字比较，选择一种码距最小的码字作为译码输出。对于（n,k,m）卷积码而言，发k位数据，则它有2k种可能码字，计算机应存储这些码字，以便于比较。当k较大时，由于存储量太大，应用受到限制。由于接收序列通常很长，所以维特比译码是最大似然译码算法的简化。简化的方法是：它把接收码字分段处理，每接收一段码字，计算、比较—次，保留码距最小的路径，直至译完整个序列。

现以上述(2,1,2)码为例说明维持比译码过程。当发端的信息数据为11010时，为使全部信息能通过编码器，在其后加上000，此时的全部数据为11010000，如表3-14所列，编出的码字为1101010010110000，移位寄存器的状态转移路线为：a?b?d?c?b?c?a?a。发送的信息通过信道传至对方，设接收码字有差错，码字序列变成0101011010010010，有4位码元差错。下面参照图3-13的网格图来说明译码过程。

40

本文来源：https://www.bwwdw.com/article/yie7.html