第5章〓信道编码
5．1信道编码的基本概念























在有噪信道上传输信号时，所收到的数据不可避免地会出现差错，所以在数字通信、数据传输、图像传输、计算机网络等数字信息交换和传输中所遇到的一个主要问题是可靠性问题。不同的用户对可靠性的要求是大相径庭的，例如： 对于普通电报，差错概率(误码率)在10-3 时是可以接受的； 而对导弹运行轨道数据的传输，如此高的差错率将使导弹偏离预定的轨道，这显然是不允许的。在数字通信系统中要从多种途径来研究提高系统可靠性的方法。首先要进行合理基带信号设计、选择合适调制解调方式以及采用匹配滤波、均衡等，这是降低差错的根本措施，其目的是改善信道特性，减少差错。在此基础之上利用纠错编码技术对差错进行控制，可大大提高系统的抗干扰能力，降低误码率，这是提高系统可靠性的一项极为有效的措施，也是我们后面要研究和解决的问题。

一个通信系统传输消息必须可靠、快速，如何合理解决可靠性和有效性这对矛盾是数字通信系统设计的一个关键问题。在香农之前，人们普遍认为在有噪信道进行信息传输时，要获得任意小的错误概率的唯一途径是不断减小传输速率，直至为零。1948年，香农在贝尔技术杂志上发表了奠基性文章《通信的数学理论》，标志着信息论与编码理论这一学科的创立。在文中香农提出了著名的有噪信道编码定理，该定理从理论上证明了通过信道编码技术可使信息传输率接近信道容量，同时系统的错误概率达到任意小，即实现可靠性和有效性的有机统一。编码定理及其证明虽然没有给出编码的具体设计方法，却指出了达到信道容量的编译码方法的方向和途径。此后，构造可逼近信道容量(香农限)的信道编码具体方法以及可实现的有效译码算法一直是信道编码理论和技术研究的中心任务，也是编码学者长期追求的目标。

5．1．1信道编码的一般方法

纠错编码又称信道编码或差错控制编码，它涉及很多理论问题和数学知识，本节先介绍基本的纠错编码方法和概念。

设信源编码器输出的二元数字信息序列为(001010110001…)，序列中每个数字都是一个信息元素。为了适应信道的最佳传输而进行编码，首先需要对信息序列进行分组。一般是以截取相同长度的码元进行分组，每组长度为k(含有k个信息元)，这种序列一般称为信息组或信息序列，例如上面的信息序列以k=1分组为0(代表“雨”)、1(代表“晴”)。如果将这样的信息组直接送入信道传输，它是没有任何抗干扰能力的，因为任意信息组中任意元素出错都会变成另一个信息组，如信息元(0)出错，变成(1)，而它们代表着不同的信息组，因此原本发送的气象信息在接收端就会判断错误(“雨”变成“晴”)。可见不管k的大小如何，若直接传输信息组是无任何抗干扰能力的。

如果在各个信息组后按一定规律人为地添上一些数字，如上例，在k=1的信息组后再添上两位数字，使每一组的长度变为3，这样的各组序列称为码字。码字长度记为n，本例中n=k+2。每个码字的前一个码元为原来的信息组，称为信息元，它主要用来携带要传输的信息内容。后两个新添的码元称为监督元(或校验元)，其作用是利用添加规则来监督传输是否出错。如果添监督元的规则为新添的每个监督元符号(0或1)与前面信息元符号(0或1)一样，那么这样的码字共有2k=21=2个，即{(000)，(111)}，它们组成了一个码字集合，称为(3,1)重复码，其每个码字分别代表一个不同的信息组。而在3位二进制序列(码组)中共有23=8个，除以上2个作为码字外，还有6个未被选中，即这6个码组不在发送之列，称为禁用码组，而被编码选中的n重码字称为许用码组。接收端接收序列不在码字集合中，说明不是发送端所发出的码字，从而确定传输有错。因此这种变换后的码字就具有一定的抗干扰能力。以二元对称信道BSC(0．01)为例，若直接传输信息元，接收端平均错误译码概率就等于信道的错误传输概率，即PE=10-2，而采用(3,1)重复码后，只有当码字中3位码元都出错才会误判(将发端传递的“雨”消息误判成“晴”或相反)，否则可以检出传输出错，此时系统错误译码概率PE=p3=10-6； 当传输中每个码字仅1位出错，接收端还能根据编码规律进行自动纠错，可计算出此时接收端平均错误译码概率： 
PE=p3+3(1-p)p2≈3×10-4
可见采用(3,1)重复码后，接收端无论采取检错方式还是纠错方式，系统的错误译码概率都会降低。

以上就是一种最简单的信道编码，在一位信息元之后添加了两位监督元，从而获得了抗干扰能力。一般来说，添加的监督元位数越多，码字的抗干扰能力就越强，不但能识别传输是否有错(检错)，还可以根据编码规则确定哪一位出错(即纠错)。因此，纠错编码的一般方法可归纳为： 在传输的信息码元之后按一定规律产生一些附加码元(图5．1．1)，经信道传输，在传输中若码字出现错误，接收端能利用编码规律发现码的内在相关性受到破坏，从而按一定译码规则自动纠正错误，降低误码率PE。



图5．1．1信道编码过程







通常按以下方式对纠错码进行分类。

（1） 按照对信息元处理方法分为分组码与卷积码两大类。

分组码是把信源输出的信息序列，以k个码元划分为一段，通过编码器把这段k个信息元按一定规则产生r个校验(监督)元，输出码长为n=k+r的一个码组。这种编码中每一码组的校验元仅与本组的信息元有关，而与别组无关。分组码用(n,k)表示，n表示码长，k表示信息位。

卷积码是把信源输出的信息序列，以k0个(通常k0<k)码元分为一段，通过编码器输出码长为n0(n0>k0)的码段，但是该码段的n0-k0个校验元不仅与本组的信息元有关，而且与其前m段的信息元有关，一般称m为编码存储，因此卷积码用(n0,k0,m)表示。

（2） 根据校验元与信息元之间的关系分为线性码与非线性码。

若校验元与信息元之间的关系是线性关系(满足线性叠加原理)，则称为线性码； 否则，称为非线性码。

目前实用的纠错码以线性码为主，且非线性码的分析比较困难，故本书仅讨论线性码。

（3） 按照所纠错误的类型可分为纠随机错误码、纠突发错误码以及既纠随机错误又纠突发错误码。

（4） 按照每个码元取值可分为二进制码与q进制码(q=pm，p为素数，m为正整数)。

（5） 按照对每个信息元保护能力是否相等可分为等保护纠错码与不等保护(UEP)纠错码。

除非特别说明，今后讨论的纠错码均指等保护能力的码。

此外，在分组码中按照码的结构特点又可分为循环码与非循环码。为了清晰起见，把上述分类用图5．1．2表示。



图5．1．2纠错码分类


为了今后学习的方便，除了上面讲到的基本概念外，还将介绍一些编码中常用的参数。

5．1．2信道编码的基本参数
1． 码率

一般把分组码记为(n,k)码，n为编码输出的码字长度，k为输入的信息组长度，在一个(n,k)码中，信息元位数k在码字长度n中所占的比重称为码率，用R表示。对于二元线性码，它可等效为编码效率，即
η=R=kn
码率是衡量所编的分组码有效性的一个基本参数，码率越大，表明信息传输的效率越高。但对编码来说，每个码字中所加进的监督元越多，码字内的相关性越强，码字的纠错能力越强。而监督元本身并不携带信息，单纯从信息传输的角度来说是多余的。一般地说，码字中冗余度越高，纠错能力越强，可靠性越高，而此时码的效率则降低了。所以信道编码必须注意综合考虑有效性与可靠性的问题，在满足一定纠错能力要求的情况下，总是力求设计码率尽可能高的编码。

2． 汉明距离与重量

定义5．1．1一个码字C中非零码元的个数称为该码字的(汉明)重量，简称码重，记为W(C)。

若码字C是一个二进制n重，则W(C)就是该码字中“1”码的个数。例如： 

若C1=(000)，则W(C1)=0； 

若C2=(011)，则W(C2)=2； 

若C3=(101)，则W(C3)=2； 

若C4=(110)，则W(C4)=2。

定义5．1．2两个长度相同的不同码字C和C′ 中对应位码元不同的码元数目称为这两个码字间的汉明距离，简称码距(或距离)，记为d(C； C′)。

例如上例中，d(C2； C3)=2。

在一个码集中，每个码字都有一个重量，每两个码字间都有一个码距，对于整个码集而言，还有以下两个定义。

定义5．1．3一个码集中非零码字的汉明重量的最小值称为该码的最小汉明重量，记为Wmin(C)。

定义5．1．4一个码集中任两个码字间的汉明距离的最小值称为该码的最小汉明距离，记为d0或dmin。 

例如上例中的(3,2)码的最小汉明距离为2。

对于二元编码，不难得出如下关系式： 
d(C1； C2)=W(C1C2) 
W(C1C2)=W(C1)+W(C2)-2W(C1⊙C2）（5.1.1）
式中，“”是模2加法运算； “⊙”是模2乘法运算。

例如，C1=(11001)，C2=(10111)，则有C3=C1C2=(01110)，d(C1； C2)=W(C3)=3； C1⊙C2=(10001)，W(C3)=3+4-2×2=3。

一个(n,k)分组码共含有2k个码字，每两个码字之间都有一个汉明距离d，因此要计算其最小距离，需比较计算2k-1(2k-1)次。当k较大时，计算量就很大。但对于5.3节将要介绍的(n,k)线性分组码具有以下特点： 任意两个码字之和仍是线性分组码中的一个码字，因此两个码字之间的距离d(Cl； C2)必等于其中某一个码字C3=C1+C2的重量。

定理5．1．1(n,k)线性分组码的最小距离等于非零码字的最小重量：
d0=minC,C′∈(n,k){d(C; C′)}=minCi∈(n,k)Ci≠0W(Ci)
该定理的证明见定理5.3.1。这样一来，(n,k)线性分组码的最小距离计算只需检查2k-1个非零码字的重量即可。

此外，码的距离和重量还满足三角不等式的关系：  
d(C1； C2)≤ d(C1； C3)+d(C3； C2)
W(C1+C2)≤ W(C1)+W(C2)
该性质在研究线性分组码的特性时常用到。一种码的d0值是一个重要参数，它决定了该码的纠错、检错能力。d0越大，抗干扰能力越好。






3． 码的纠、检错能力

定义5．1．5若一种码的任一码字在传输中出现了e个或e个以下的错误仍能自动发现，则称该码的检错能力为e。

定义5．1．6若一种码的任一码字在传输中出现t个或t个以下的错误仍能自动纠正，则称该码的纠错能力为t。

定义5．1．7若一种码的任一码字在传输中出现t个或t个以下的错误均能纠正，当出现多于t个而少于e+1个错误(e>t)时此码能检出而不造成译码错误，则称该码能纠正t个错误同时检测e个错误。

(n,k)分组码的纠、检错能力与其最小汉明距离d0有着密切的关系，一般有以下结论。

定理5．1．2若码的最小距离满足d0≥e+1，则码的检错能力为e。

定理5．1．3若码的最小距离满足d0≥2t+1，则码的纠错能力为t。

定理5．1．4若码的最小距离满足d0≥e+t+1(e>t)，则该码能纠正t个错误同时检测e个错误。

以上结论可以用图5．1．3所示的几何图加以说明。



图5．1．3码距与检错和纠错能力的关系


图5．1．3(a)中C1表示某一码字，当误码不超过e个时，该码字的位置移动将不超过以它为圆心、以e为半径的圆(实际上是一个多维球)，即该圆代表着码字在传输中出现e个以下误码的所有码组的集合。若码的最小距离满足d0≥e+1，则(n,k)分组码中除C这个码字外，其余码字均不在该圆中。这样当码字C在传输中出现e个以下误码时，接收码组必落在图5．1．3(a)的圆内，而该圆内除C1外均为禁用码组，从而可确定该接收码组有错。考虑到码字C的任意性，图5．1．3(a)说明，当d0≥e+1时任意码字传输误码在e个以下的接收码组均在以其发送码字为圆心、以e为半径的圆中，而不会和其他许用码组混淆，使接收端检出有错，即码的检错能力为e。

图5．1．3(b)中Cl、C2分别表示任意两个码字，当各自误码不超过t个时，发生误码后两码字的位置移动将各自不超过以Cl、C2为圆心、以t为半径的圆。若码的最小距离满足d0≥2t+1，则两圆不会相交(由图中可看出两圆至少有l位的差距)，设Cl传输出错误在t个以下变成C′l，其距离
d(Cl； C′1)≤t
根据距离的三角不等式可得
d(C′1； C2)≥t
即
d(C′1； C2)≥d(C1； C′1)
根据最大似然译码规则，将C′1 译为C1从而纠正了t个以下的错误。

定理5．1.4中“能纠正t个错误同时检测e个错误”是指当误码不超过t个时系统能自动予以纠正，而当误码大于t个而小于e个时则不能纠正但能检测出来。该定理的关系由图5．1．3(c)反映，其结论请读者自行证明。

以上三个定理是纠错编码理论中最重要的基本理论之一，它说明了码的最小距离d0与其纠、检错能力的关系，从d0中可反映码的性能强弱； 反过来也可根据以上定理的逆定理设计满足纠检错能力要求的(n,k)分组码。

定理5．1.5对于任一(n,k)分组码，若要求：

（1） 码的检错能力为e，则最小码距d0≥e+1； 

（2） 码的纠错能力为t，则最小码距d0≥2t+1； 

（3） 能纠t个误码同时检测e(e>t)个误码，则最小码距d0≥t+e+1。

5．1．3信道译码规则

已知信道编码器的框图如图5．1．1 信道编码过程所示，设任一个信息序列M是一个k位码元的序列，通过编码器按一定的规律(编码规则)产生若干监督元，形成一个长度为n的序列，即码字。每个信息序列将形成不同的码字与之对应，在二进制下，k维序列共有2k种组合，因此编码输出的码字集合共有Q=2k个码字，而二进制下的n重矢量共有2n种。显然，编码输出的码字仅是所有二进制n重中的一部分，编码实际上就是从这2n种不同的n重矢量中按一定规律(编码规则)选出2k个n重矢量(许用码字)代表2k个不同的信源信息序列。

数字通信系统简化模型如图5．1．4所示，设发送码字是码长为n的序列C： (cn-l，cn-2，…，c1，c0)，通过信道传输到达接收端的序列为R: (rn-1，rn-2，…，r1，r0)，由于信道中存在干扰，R序列中的某些码元可能与C序列中对应码元的值不同，即产生了错误。而二进制序列中的错误不外乎是1错成0或0错成1，因此，如果把信道中的干扰也用二进制序列E： (en-1，en-2，…，el，e0)表示，则相应有错误的各位ei取值为1，无错的各位取值为0，称E为信道的错误图样或错型，而R就是n维序列C与E模2相加的结果: 
R=CE
式中： “”为模2加法。



图5．1．4数字通信系统简化模型


经编码后产生的(n,k)码送信道传输，由于信道干扰的影响将不可避免地发生错误，这种错误有以下两种趋势。

（1） 许用码字变成禁用码组。这种错误一旦出现，由于接收到的码组不在编码器输出的码字集合中，译码时可以发现，所以这种错误模型是可检出的。

（2） 许用码字变成许用码字。即发端发生某一码字Ci经传输后错成码集中的另一码字Cj，这时收端无法确认是否出错，因此这是一种不可检出的错误模型。

可见，一个n重二进制码字C在传输中由于信道干扰的影响，到接收端可能变成2n种n重矢量中的任何一个，译码的任务就是将所有可能的接收矢量进行分类，同属一类的接收矢量译为同一个许用码字，将2n种不同的接收矢量还原为2k个许用码字或信息序列。为了能在接收端确认发送的是何种码字，就需要建立一定的判决规则以获得最佳译码。信道编译码过程如图5．1．5所示。








图5．1．5信道编译码过程


一般来说，译码器要完成比编码器更为复杂的运算，译码器性能的好坏、速度的快慢往往决定了整个差错控制系统的性能和成本。译码正确与否的概率主要取决于所使用的码、信道特征及译码算法。对特定码类如何寻找译码错误概率小、译码速度快、设备简单的译码算法，是纠错编码理论中一个重要而实际的课题。下面讨论当码类和信道给定时，应采用什么样的算法使译码错误概率最小。

由图5．1．4和图5．1．5可知，信道输出的R是一个二(或q)进制序列，而译码器的输出是一个信息序列M的估值序列M^。

译码器的基本任务就是根据接收序列R和信道特征，按照一套译码规则，由接收序列R给出与发送的信息序列M最接近的估值序列M^。由于M与码字C之间存在一一对应关系，所以这等价于译码器根据R产生一个C的估值序列C^。显然，当且仅当C^=C时，M^=M，这时译码器正确译码。如果译码器输出的C^≠C，那么译码器产生了错误译码。产生错误译码的原因有两个： 一是信道干扰很严重，超过了码本身的纠错能力； 二是译码设备的故障(这点本书不予讨论)。

当给定接收序列R时，译码器的条件译码错误概率定义为
P(E|R)=P(C^≠C|R)
所以译码器的错误译码概率为
PE=∑RP(E|R)P(R)
P(R)是接收序列R的概率，与译码方法无关，所以译码错误概率最小的最佳译码规则是使
minPE=minRP(E|R)=minRP(C^≠C|R)
=min1-∑P(R)P(C^=C|R)
进而得译码错误概率最小的最佳译码规则等价于使P(C^=C|R)最大化。

因此，若译码器对输入的R能在2k个码字中选择一个使P(C^i=C|R)(i=1，2，…，2k)最大的码字Ci作为C的估值序列C^，则这种译码规则一定使译码器输出错误概率最小，这种译码规则称为最大后验概率译码。

进一步，由贝叶斯公式
P(Ci|R)=P(Ci)P(R|Ci)P(R)
可知，若发端发送每个码字的概率P(Ci)均相同，且由于P(R)与译码方法无关，则有
maxi=1,2,…,2kP(Ci|R)maxi=1,2,…,2kP（R|Ci）（5.1.2）
对离散无记忆信道（DMC）而言，有
P(R|Ci)=∏nj=1P(rj|cij)（5.1.3）
式中
Ci=(ci1，ci2，…，cin)（i=1，2，…，2k）
一个译码器的译码规则若能在2k个码字C中选择某一个Ci并使式（5.1.2）最大，则这种译码规则称为最大似然译码(MLD)，P(R|C)称为似然函数。由于logbx与x是单调关系，因此式（5.1.2）与式（5.1.3）可写成
maxi=1，2，…，2klogbP(R|Ci)=maxi=1，2，…，2k ∑nj=1logbP(rj|cij)（5.1.4）
式中： logbP(R|C)为对数似然函数或似然函数。

对于DMC，当发端发送每一码字的概率P(Ci)(i=1，2，…，2k)均相等时，MLD是使译码错误概率最小的一种译码方法； 否则，MLD不是最佳的。因而，MLD算法是一种准最佳的译码算法。在以后的讨论中，都认为P(Ci)均近似相等。

例5．1．1一个码由00000，00111，11100与11011四个码字组成。每个码字可用来表示4种可能的信息之一。可以计算出该码的最小距离d0=3，由定理5．1 3可知，它可纠正在任何位上出现的单个误码。同时注意到，码长为5的二进制码组共有25=32种可能的序列，除了上述4个许用码字外，其余28个为禁用码组。为了对该码进行纠错处理，需将28种禁用码组的每一个与4种许用码字做“最邻近性”的比较。这种处理意味着要建立一个“译码表”，所以译码的本质就是对码组进行分类，即先将所有与每个许用码字有一位差错的各个可能接收序列列在该码字的下面，这样就得到表5．1．1中以虚线围起的部分。除了这一部分之外，应注意到尚有8个序列未被列入。这8个序列与每个码字至少差两位。但是，它们与上述序列不同，没有唯一的方法可把它们安排到表内。例如，既可将序列10001放在第4列，也可将它放在第1列。在译码过程中使用此表时，可将所接收序列与表内各列对照，当查到该序列时，将该列第一行的码字作为译码器的输出。



表5．1．14个码字的译码表




00000111000011111011

10000011001011101011

01000101000111110011

00100110000001111111

00010111100010111001
续表


00001111010011011010

10001011011011001010

10010011101010101001


用这种方式建立的表具有很大的优点。设信道误码率为pe，出现任何一种具有i个差错特定模式的概率是pie(1-pe)5-i。当pe<1/2，即信道的信噪比足够大时，可以看到：  
(1-pe)5>pe(1-pe)4>p2e-(1-pe)3>…
即不出错概率大于出错概率； 一个特定的单个差错模式要比一个特定的两个(或多个)差错模式更容易出现。因此，译码器将所收到的一个特定码组译为在汉明距离上最邻近的一个码字时，实际上是选择了最可能发送的那个码字(设各个码字的发送机会相同)。这就是MLD的具体应用，实际上它就是根据接收序列R在2k个码字集中寻找与R的汉明距离最小的码字Ci作为译码输出，因为它最可能是发送的码字。这种译码方法又称为最小汉明距离译码。执行这种译码规则的译码器称为最大似然译码器。在上述条件下，其序列差错概率最小。当用译码表进行译码时，为了实现最大似然译码，可用上述方法列表对码字进行分类。遗憾的是，译码表的大小随码组长度按指数关系增加，故对长码来说直接使用译码表是不切合实际的。但对说明分组码的某些重要性质而言，译码表仍是一种很有用的概念性工具。

总结而言，信道译码准则有以下几种。 

最小错误概率译码准则： F(Ri)=C*=arg minPE

最大联合概率译码准则： F(Ri)=C*=arg max［P(C*Ri)］

最大后验概率译码准则： F(Ri)=C*=arg max［P(C*|Ri)］

最大似然概率译码准则： F(Ri)=C*=arg max［P(Ri |C*)］

最小距离译码准则： F(Ri)=C*=arg min［d(C*； Ri)］

可以证明，最大联合概率译码和最大后验概率译码等价，都属于最小错误概率译码，可以得到最小平均译码概率PE，是性能最佳的译码准则。但这几类译码准则依赖发送码字的先验概率P(Ci)，计算复杂度大。最大似然译码或最小距离译码仅依赖信道转移概率或码距，译码相对简单，但最大似然译码只有在输入等概时才能得到最小平均译码错误概率，最小距离译码在传输错误概率较小时，等价于最大似然译码。






5．2有噪信道编码定理

5．2．1联合渐近等同分割性与联合典型序列

有噪信道编码定理又称香农第二定理，其基础依据是信道传输表现出联合渐近等同分割性（AEP）。

针对离散信源，AEP定理和ε典型序列说明离散信源的无记忆扩展信源随着序列X1，X2,X3,…,Xn的长度n无限加大，每个ε典型序列发生的概率约为2-nH(X)，这些典型序列的总数约为2nH(X)，这些ε典型序列为高概率事件。类似的结论对于离散信道也成立。以下讨论离散信道［X,P(y|x),Y］的n次无记忆扩展信道［Xn,P(y|x),Yn］，其中，x=(x1，x2，…，xn)（xi∈X）和y=(y1，y2，…，yn)（yi∈Y）分别表示n次无记忆扩展信道的输入和输出的n长随机序列。满足
P(y|x)=P(y1y2…yn|x1x2…xn)=∏ni=1P(yi|xi)
它们对应的信息熵和联合熵分别为H(X)、H(Y)和H(XY)。

定义5．2．1设(x,y)∈(Xn; Yn)是n长随机序列对，对于任意小的正数ε>0，存在足够大的n，若满足下列条件： 
1nlogP(x)+H(X)<ε
1nlogP(y)+H(Y)<ε
1nlogP(xy)+H(XY)<ε（5.2.1）
则称(x，y)为联合ε典型序列。

Gε(X)和Gε(Y) 分别表示Xn和Yn中的典型序列集，Gε(XY) 表示XnYn联合空间中的联合典型序列集。联合ε典型序列满足如下性质。

定理5．2．1(联合渐近等同分割性)对于任意小的ε>0，δ>0，当n足够大时，则有以下性质。

性质1典型序列x，y和联合典型序列(x，y)满足
2-n［H(X)+ε］≤P(x)≤2-n［H(X)-ε］2-n［H(Y)+ε］≤P(y)≤2-n［H(Y)-ε］2-n［H(XY)+ε］≤P(xy)≤2-n［H(XY)-ε］(5.2.2)
性质2典型序列集Gε(X)，Gε(Y)和联合典型序列集Gε(XY)满足
P(Gε(X))≥1-δP(Gε(Y))≥1-δP(Gε(XY))≥1-δ(5.2.3)
性质3以NG表示典型序列集中元素个数，则Gε(X)，Gε(Y)和Gε(XY)中序列个数满足
(1-δ)2n［H(X)-ε］≤NGx≤2n［H(X)+ε］(1-δ)2n［H(Y)-ε］≤NGy≤2n［H(Y)+ε］(1-δ)2n［H(XY)-ε］≤NGxy≤2n［H(XY)+ε］(5.2.4)
证明： 性质1是大数定律的直接结果，因1nlog1P(x)、1nlog1P(y)、1nlog1P(xy)分别依概率趋于其统计平均Elog1P(x)=H(X)、Elog1P(y)=H(Y)以及Elog1P(xy)=H(XY)。再根据联合ε典型序列定义式（5.2.1）整理即得性质1。

性质2的证明采用极限理论中εδ描述方法，对于任意小的正数ε>0，δ>0，存在正整数n0，使得对于所有n≥n0，有
P1nlog1P(x)-H(X)≤ε≥1-δ
P1nlog1P(y)-H(Y)≤ε≥1-δ
P1nlog1P(xy)-H(XY)≤ε≥1-δ
即得性质2。

最后证明性质3，结合概率满足完备性以及联合典型序列满足式（5.2.2），可得
1≥∑x∈Gε(X)P(x)>NGε(X)2-n［H(X)+δ］1≥∑y∈Gε(Y)P(y)>NGε(Y)2-n［H(Y)+δ］1≥∑xy∈Gε(XY)P(xy)>NGε(XY)2-n［H(XY)+δ］
NGε(X)2-n［H(X)-δ］>∑x∈Gε(X)P(x)>1-εNGε(Y)2-n［H(Y)-δ］>∑y∈Gε(Y)P(y)>1-εNGε(XY)2-n［H(XY)-δ］>∑xy∈Gε(XY)P(xy)>1-ε
两组公式整理即得性质3。［证毕］

定理5．2．1说明，在两个随机变量情况下，信源Xn、Yn和联合集(Xn Yn)也具有渐近等同分割性。联合ε典型序列对(x,y)是n次无记忆扩展联合空间中经常出现的高概率序列对。这些高概率序列对的出现概率几乎相等，即
P(x)≈2-nH(X),
P(y)≈2-nH(Y),
P(xy)≈2-nH(XY)
并且与典型序列一样，联合典型序列对(x,y)的概率和也是趋于1的。即随着n的增大，典型序列和联合典型序列属于高概率事件，各自占据了Xn、Yn、(Xn,Yn)的几乎全部概率组成。

那么联合ε典型序列对(x,y)是如何构成的？Xn是扩展信道的输入概率空间，Yn是扩展信道的输出概率空间。取Xn中典型序列x与Yn中典型序列y配对，同时满足式（5.2.2），则构成联合ε典型序列对(x,y)。典型序列x是输入端高概率出现的序列，典型序列y是输出端高概率出现的序列，而联合典型序列对(x,y)就是那些信道输入和输出之间密切关联、经常出现的序列对。

基于定理5．2．1中性质3可知，随着n的增大，典型序列和联合典型序列各自的数目大约为
NGε(X)≈2nH(X),
NGε(Y)≈2nH(Y),
NGε(XY)≈2nH(XY)

例5．2．1设信源为XP(x)=010．90．1，传输信道为BSC(0．2)的n次扩展信道，其输入和输出构成联合典型序列对(x,y)。存在一个长度n=100的联合典型序列对： 

x=11111111110000000000000000000000000000000000000000000000000000000000

00000000000000000000000000000000

y=00111111110000000000000000000000000000000000000000000000000000000000

00000000000000111111111111111111

可见，x是一个Xn集合的典型序列(满足I(x)/100=H(X))，序列y中有26个“1”，74个“0”，也是Yn中的典型序列，而x与y有20bit不同，即序列对(x，y)正是该信道的一个典型序列对(符合信道典型翻转的概率)。

进一步，可以证明联合ε典型序列还具有如下性质。

定理5．2．2对于任意小的正数ε>0，当n足够大时，有

性质1
2-n［H(Y|X)+2ε］≤P(y|x)≤2-n［H(Y|X)-2ε］
2-n［H(X|Y)+2ε］≤P(x|y)≤2-n［H(X|Y)-2ε］
式中： (x; y)∈Gε(XY)。

性质2

令Gε(X|y)={x: (x,y)∈Gε(XY)}，Gε(Y|x)={y: (x,y)∈Gε(XY)}，即Gε(X|y)表示在给定ε典型序列y条件下与y构成联合ε典型序列对的所有序列x的集合，Gε(Y|x)表示在给定ε典型序列x条件下与x构成联合ε典型序列对的所有典型序列y的集合。则有
NGε(X|y)≤2n［H(X|Y)+2ε］
NGε(Y|x)≤2n［H(Y|X)+2ε］
证明： (1) 令(x; y)∈Gε(XY)，对于任意x，y 满足
P(y|x)=P(xy)P(x)
根据式（5.2.2）可得
2-n［H(XY)+ε］×2n［H(X)-ε］≤P(y|x)≤2-n［H(XY)-ε］×2n［H(X)+ε］
2-n［H(XY)-H(X)+2ε］≤P(y|x)≤2-n［H(XY)-H(X)-2ε］
所以
2-n［H(Y|X)+2ε］≤P(y|x)≤2-n［H(Y|X)-2ε］
同理，可得
2-n［H(X|Y)+2ε］≤P(x|y)≤2-n［H(X|Y)-2ε］
(2) 假设序列y∈Gε(Y)，因为
1=∑XnP(x|y)=∑XnP(xy)P(y)≥∑x∈Gε(X|y)P(xy)P(y)
又因为y是典型序列，x与y构成联合典型序列对，即(x,y)∈Gε(XY)，根据式（5.2.2）可得
P(xy)>2-n［H(XY)+ε］P(y)<2-n［H(Y)-ε］
进而可得
1≥∑x∈Gε(X|y)2-n［H(XY)-H(Y)+2ε］=NGε(X|y)2-n［H(X|Y)+2ε］
移项后可得
NGε(X|y)≤2n［H(X|Y)+2ε］
同理，假设序列x∈Gε(X)，因为
1=∑YnP(y|x)=∑YnP(xy)P(x)≥∑y∈Gε(Y|x)P(xy)P(x)
又因为(x,y)∈Gε(XY)，根据式（5.2.2）可得
P(xy)>2-n［H(XY)+ε］P(x)<2-n［H(X)-ε］
进而可得
1≥∑y∈Gε(Y|x)2-n［H(XY)-H(X)+2ε］=NGε(Y|x)2-n［H(Y|X)+2ε］
移项后可得
NGε(Y|x)≤2n［H(Y|X)+2ε］
［证毕］

定理5．2．3若(x′,y′)是统计独立的随机联合典型序列对，并与P(xy)有相同的边缘分布，即(x′,y′)~P(x′)P(y′)=P(xy)，且对于任意正数δ>0，当n足够大时，有
(1-δ)2-N［I(X; Y)+3δ］≤P{(x′,y′)∈Gε(XY)}≤2-N［I(X; Y)-3δ］
证明： 因为(x′; y′)是统计独立且与P(xy)有相同的边缘分布，即
P(x′y′)=P(x)P(y)=P(xy)
因此可得
P{(x′; y′)∈Gε(XY)}=∑xy∈Gε(XY)P(x)P(y)
≤2n［H(XY)+ε］×2-n［H(X)-ε］×2-n［H(Y)-ε］
=2-n［H(X)+H(Y)-H(XY)-3ε］=2-n［I(X; Y)-3ε］
同理，当n足够大时，有
P{(x′,y′)∈Gε(XY)}=∑xy∈Gε(XY)P(x)P(y)
≥(1-δ)2n［H(XY)-ε］×2-n［H(X)+ε］×2-n［H(Y)+ε］
=(1-δ)2-n［H(X)+H(Y)-H(XY)+3ε］=(1-δ)2-n［I(X; Y)+3ε］
［证毕］

可以用图形进一步描述上述联合ε典型序列的一系列结论。将联合向量空间XnYn 中所有序列排成如图5．2．1所示的阵列。在联合向量空间中的全部序列对依据是否是典型序列x和典型序列y，可以划分为4部分。以Xn空间中的序列x为行，以Yn空间中的序列y为列，分别将属于ε典型序列的排列在前面，即前面近似2nH(X)行为典型序列x，前面约2nH(Y)列为典型序列y。那么，只有位于阵列左上角部分的序列对(x，y)属于联合ε典型序列的序列对，每个黑点对应一个联合典型序列对，共有2nH(XY)个黑点。根据定理5．2．2中(2)的结论，对于Xn中的每个ε典型序列xi，约有2nH(Y|X)个Yn中的ε典型序列yj与之配对，构成联合典型序列对，即每行有2nH(Y|X)个黑点，构成集合Gε(Y|xi)； 同理，对于Yn中的每个ε典型序列yj，约有2nH(X|Y)个Xn中的ε典型序列xi与之配对，构成联合典型序列对，即每列有2nH(X|Y)个黑点，构成集合Gε(X|yj)。



图5．2．1联合典型序列示意


又根据定理5．2．3，随机选择序列对是统计独立的联合典型序列对的概率约为2-nI(X; Y)。也就是说，在2nH(XY)个联合典型序列对中，x与y相互统计独立的序列对(x，y)只占一部分，约为2nI(X; Y)。因此，对于某一典型序列yj，可以认为与它统计独立的联合典型序列对可能有2nI(X; Y)个，这也提示我们在2nH(X)个X典型序列中有2nI(X; Y)个是可区分识别的典型序列xi。

由前面讨论可知，在n次无记忆扩展信道的输入和输出空间之间，联合ε典型序列对(x,y)是一些密切关联的序列对。也就是说，DMC经过足够多次扩展后会呈现出传输极化的特性，即当某一输入典型序列xi发送，转移到收端时，对应的接收序列高概率是能与xi构成联合ε典型序列对的那些典型序列yj。

如果把全部2nH(X)个输入ε典型序列xi都用于传送信息，每个xi将会高概率地转移为能与之构成联合典型序列对的那2nH(Y|X)个典型序列yj，势必会造成不同的xi对应(转移为)相同的yj，即图5．2．1左上角中同一列的黑点重复，这将会造成译码错误。为了避免这种情况，就要求Yn中与每个发送序列配对的典型序列集合不相交，即从Xn中选择若干(不是全部)典型序列xi，要求其在Yn中的联合典型序列集Gε(Y|xi)不相交，如图5．2．2所示。根据定理5．2．2和定理5．2．3，为使收端译码不出错，从编码角度而言，发送端需要从2nH(X)个X典型序列中选择一部分作为许用码字。选取原则是要求每个选出的许用码字xi所配对的2nH(Y|X)个Y典型序列和其他许用码字所对应的Y典型序列没有交集。那么，为保证译码无错，发送端编码最多能够选出的码字数目Q个为多少？对于X典型序列xi，传输后高概率转移为Gε(Y|xi)中的一个典型序列yj，由于每个Gε(Y|xi)中的Y典型序列数目约为2nH(Y|X)，Yn中的典型序列集Gε(Y)的总数约为2nH(Y)，所以要求
2nH(Y|X)Q≤2nH(Y)
即在不发生译码错误的要求下能够用于传输信息的输入典型序列xi的个数最多为
Q≤2nH(Y)2nH(Y|X)=2nI(X; Y)


图5．2．2n次扩展信道x与y的关系



信道编码需要从全部2nH(X)个n重矢量(输入典型序列)中选取Q(≤2nI(X; Y))个作为许用码字，用来传送消息，并保证这些输入典型序列所对应的输出典型序列彼此无重叠。定理5．2．3从理论上保证了在2nH(X)个X典型序列中可区分识别出2nI(X; Y)个典型序列，与它们配成联合典型序列对的Y典型序列集不重叠，相当于可以把输出典型序列集合划分2nI(X; Y)个不相交的子集，从而可保证译码无错，如图5．2．2所示。






5．2．2香农第二定理(有噪信道编码定理)

有噪信道编码定理又称为香农第二定理，是信息论的基本定理之一。

综合前面的分析，可以将信道编码理解为在编码时随机地选择输入端ε典型序列作为码字Ci，因为它们是在输入端Xn集中高概率出现的序列。n次无记忆扩展信道传输中具有联合渐近等同分割性，所发送的码字Ci与接收序列yj构成联合典型序列对的概率很高，它们之间是高概率密切相关的。因此译码可采取联合典型序列译码准则，即在译码时接收端Yn集中将接收序列yj译成与它构成联合典型序列对的那个码字。

下面给出香农第二定理的完整描述和证明。

定理5．2．4(有噪信道编码定理)设离散无记忆信道［X，P(y|x)，Y］的信道容量为C。当信息传输率R<C时，只要码长n足够长，总可以在输入X符号集中找到Q(=2nR)个码字组成的一组码和相应的译码规则，使译码的平均错误概率任意小(PE→0)。当R>C时，无论码长n多长，都找不到一种满足Q=2nR的编码方案使得PE→0。

证明： 设输入端有Q=2nR 个消息(信息序列)，用{1，2，…，Q}=［1，Q］ 表示消息的标号集。信道编码就是将Q个消息映射成Xn中不同的序列，即编码函数f:  {1，2，…，Q=2nR)→Xn，选出许用码字Ci=(xi1xi2…xiN)，组成有Q个码字的码集(或称为码书)C={C0C1…CQ-1}。现在采用随机编码： 在Xn中以信道输入概率分布P(x)随机地选取Ci=(xi1xi2…xiN)作为码字，设xi统计独立，且满足
P(xik)=P(x)（k=1，2，…，n）xik∈X={x1，x2，…，xr}
则码字Ci出现的概率为
P(Ci)=∏nk=1P(xik)
随机编码得到的某个码书C的出现概率为
P(C)=∏Q-1i=0P(Ci)=∏Q-1i=0∏nk=1P(xik)
码书C中每个码字都是以输入概率分布P(x)，按同一规则随机选取的，因此r元随机编码可以得到的所有码书数目为
S=rnQ=rn2nR

在接收端，接收到序列yj后要译成发送的码字，相应的译码函数g，Yn→{1，2，…，Q=2nR}即将Yn集映射到Q个消息集中。

设从码书C中任选一个码字w∈C被发送，相应接收到的序列为yj，根据译码函数
g(yj)=w∈C，为正确译码
g(yj)=w′∈C，w′≠w，为错误译码
则发送消息w，在接收端译码产生的错误概率为
Pew=P{g(yj)≠w|Cj=w}，w∈{C0,C1,…,CQ-1}
而该码书的平均错误概率
PE(C)=1Q∑Q-1j=0P(g(yj)≠w|w)=12nR∑Q-1i=1Pew(5.2.5)
由5．2．1节分析可知，对于n次扩展信道传输具有联合渐近等同分割性，发送的码字Ci时，其接收序列很高概率是与Ci构成联合典型序列对的Y典型序列，所以可选择联合典型序列译码准则作为译码规则。即对某接收序列yj，若存在w∈C，并且(w，yj)∈Gε(XY)，即yj与w构成联合典型序列对，则将yj译成w，即g(yj)=w∈C。不难看出联合典型序列译码准则本质就是最大似然译码准则。

因为随机编码选取出的码书C有很多种，因此为了计算随机编码总的平均错误概率，应基于式（5.2.4）的平均错误概率，对所有可能选取的码书进行统计平均，即
PEPr(E)=E所有码书［PE(C)］=∑SP(C)PE(C)=12nR∑Q-1i=1∑SP(C)Pew
另外，由随机编码的规则知，各码字生成方式一样，即选取的机会均等。因此，在所有码书上求平均的平均错误概率与发送码字w具体是哪个无关，即上式中∑SP(C)Pew不依赖发送码字w。为不失一般性，可以先某一码字，如令w=C0统一考虑，即∑SP(C)Pew=Pe0，进而可得
Pr(E)=12nR∑Q-1i=1Pe0=Pe0
=P{g(yj)≠C0|xi=C0}
当采用联合典型序列译码准则时，产生译码错误情况包括以下两种。

(1) 接收矢量yj与发送码字w不构成联合典型序列对，而可能是与其他许用码字w′≠w构成了联合典型序列对，即w∈C,w′∈C，w′≠w，(w,yj)Gε(XY)而(w′,yj)∈Gε(XY)。

(2) 接收矢量yj既与发送码字w构成联合典型序列对，也与其他许用码字w′≠w构成联合典型序列对，即w∈C,w′∈C，w′≠w，(w,yj)∈Gε(XY)且(w′,yj)∈Gε(XY)。

为方便计算，令事件Ei={(Ci,yj)∈Gε(XY)}（i=0，1，…，Q-1）;  表示第i个码字Ci与接收序列yj构成联合ε典型序列对，事件i表示发送的第i个码字Ci与接收序列yj不构成联合ε典型序列对，即事件i={(Ci,yj)Gε(XY)}（i=0，1，…，Q-1）。所以有
Pe0=P{g(yj)≠C0|xi=C0}
=P(0∪E1∪…∪EQ-1)
由集合论可得
P(∪ksk)≤∑kP(sk)
故而有
Pe0≤P(0)+∑Q-1i=1P(Ei)（5.2.6）
根据式（5.2.3）可得
P(Ei)≥1-δ
又
P(0)=1-P(E0)≤δ(n足够大)(5.2.7)
而因为信道编码是随机选择码字的，所以码字C0和Ci彼此是统计独立的，则序列yj与Ci(i≠0)也统计独立。由定理5．2．3可得
P(Ei)={P(Ci,yj)∈Gε(XY)}≤2-N［I(X; Y)-3δ］（5.2.8）
结合式（5.2.7）和式（5.2.8），式（5.2.6）可写为
Pe0≤δ+∑Q-1i=12-n［I(X; Y)-3δ］=δ+(2nR-1)2-n［I(X; Y)-3δ］
信道传递信息时，总希望传输率R尽可能大。在证明中可以选择P(x)是达到信道容量的最佳输入概率分布P*(x)，于是可达条件R<I(X; Y)成为R<C。因此，选择任意小正数δ 和ε，当R<C并且n 足够大时，Pe0为任意小。
Pe0≤δ+2-n［C-R-3δ］-2-n［C-3δ］≤δ+2-n［C-R-3δ］≤2δ
Pr(E)是对所有码书求统计平均，由此得当n足够大，R<C时，平均错误概率Pr(E)为任意小。因此，至少存在一种码书(Q=2nR,n)，其错误概率小于或等于平均值Pr(E)。由此证得定理。
［证毕］

总结： 有噪信道编码定理告诉人们，只要信息传输率不超过信道容量，即R<C,换句话说发送的码字数Q=2nR，只要码长n足够长，总可以在输入的符号集Xn中找到Q个许用码字和相应的译码规则，使得PE→0,从而实现信息的可靠传输。

其证明方法的基本思路如下。

(1) 连续使用信道多次，即在n次无记忆扩展信道中讨论，当n足够大时，大数定律有效。

(2) 采取随机编码，在Xn中以输入概率分布P(x)随机地选取符号序列，即经常出现的高概率典型序列作为码字。

(3) 采用联合典型序列译码准则，该准则等价于最大似然译码准则，即将接收序列译成传输模式中与最可能与之配对的那个码字。

(4) 考虑随机编码得到的所有码书结果，计算其平均错误概率，当n足够大时，此平均错误概率趋于零，由此证明得至少有一种好码存在。(定理的目标是证明存在一个码和相应的译码方法，具有很小的差错概率。但计算任意特定编码和译码系统的差错概率都是不容易的。香农的创新在于： 不是构造一个好的编码和译码系统并计算其差错概率，而是计算所有码的平均分组差错概率，并证明这个平均值很小。那么一定存在某些码具有很小的差错概率。)

以上证明是基于离散无记忆信道的，已有文献证明香农第二定理对连续信道和有记忆信道同样成立。因此，无论是离散信道还是连续信道，其信道容量C是可靠通信的最大信息传输率。要想使信道中信息传输率大于信道容量而又无错误地传输是不可能的。

香农第二定理指出，当R<C，n足够大时，存在信道编码，使平均错误概率趋于零。那么n有限时，PE有可能趋于0吗？

已有研究证明，对于DMC，PE趋于零的速度是与码长n呈指数关系。即当R<C时，平均错误概率为
PE≤exp{-nEr(R)}(5.2.9)
式中，Er(R)为随机编码指数，又称作DMC的可靠性函数，其表达式为
Er(R)=max0≤ρ≤1maxP(x){E0［ρ,P(x)］-ρR}
式中： ρ为修正系数，0≤ρ≤1。



图5．2．3DMC中Er(R)与R

的关系

可见可靠性函数与输入概率分布有关。一般Er(R)与R的关系如图5．2．3所示，是一条∪型凸函数曲线。从图中可以看出，在R< C的范围内Er(R)>0，式（5.2.9）表明PE随n增大以指数趋于零。由此可知实际编码的码长n不需选择得很大。


任何信道的信道容量是一个明确的分界点，当取分界点以下的信息传输率时，PE以指数趋于零； 当取分界点以上的信息传输率时，PE以指数趋于1。因此，在任何信道中信道容量是可达的、最大的可靠信息传输率。

香农第二定理也只是一个存在定理，它说明错误概率趋于零的好码是存在的，但并没有给出具体的编码方法。从实用观点来看，定理似乎不令人满意。为了证明该定理，香农提出了随机编码的方法，这种编码并不具有工程可操作性。为了使大数定律有效，要求码长n足够长，但这样得到的码集很大，通过搜索得到好码很难实现，而且即使通过随机编码的方法找到了好码，这种码的码字也是毫无结构的，这就意味着在接收端只能通过查找表的方法进行译码。当码长n很大时，这种查找表占用的存储空间将会是难以承受的，也就难以实用和实现。尽管如此，信道编码定理仍然具有根本性的重要意义。它有助于指导各种通信系统的设计，有助于评价各种通信系统及编码的效率。为此，在香农1948 年发表文章后，研究人员致力于研究实际信道中的各种易于实现的实际纠错编码方法，赋予码以各种形式的数学结构。这方面的研究非常活跃，出现了代数编码、卷积码、几何码等。至今已经发展有许多有趣和有效结构的码，并在实际通信系统中得到广泛应用。而且随着对信道编码研究的深入，关于随机编码的认识也更加深入，例如，1993年Turbo码的出现，使我们发现随机编码理论不仅是分析和证明编码定理的主要方法，其思想在构造码上也发挥重要作用。近代研究反映出随机码思想的回归，许多性能优异的编码都有向随机编码方向靠近的趋势，如Turbo码中交织器的设计，LDPC中稀疏校验矩阵的设计，这些为香农随机码理论的应用研究开启了新思路。






5．3线性分组码

线性分组码是纠错码中很重要的一类码，它也是讨论其他各类码的基础，这类码的原理虽然比较简单，但由此引入的一些概念非常重要，如码率、距离、重量等及其与纠检错能力的关系，以及码的生成矩阵G和一致校验矩阵H的表示及它们之间的关系，H与纠错能力之间的关系等，这些概念也广泛地应用于其他各类码。

5．3．1线性分组码的基本概念
5．3．1．1线性分组码的定义







将信源所给出的二元信息序列首先分成等长的各个信息组，每组信息位长度为k，记为
M=(mk-1，mk-2，…，m1，m0)
信息组M每一位上的信息元取0或1，共有2k种可能的取值。编码器根据某些规则将输入的信息序列编成码长为n的二元序列，即码字记为
C=(cn-1，cn-2，…，cn-k，cn-k-1，…，c1，c0)
码字中每一位数字称为码元，取值为0或1。如果码字的各监督元与信息元关系是线性的(可用一次线性方程来描述)，那么这样的码称为线性分组码，记为(n,k)码。

例5．3．1(7,3)分组码，按以下的规则(校验方程)可得到4个校验元c0c1c2c3： 
c3=c6+c4
c2=c6+c5+c4
c1=c6+c5
c0=c5+c4（5.3.1）
式中： c6、c5和c4是3个信息元。

由此可得到(7,3)分组码的8个码字。8个信息组与8个码字的对应关系列于表5．3．1中。式（5.3.1）中的加均为模2加。由此方程看到，信息元与校验元满足线性关系，因此该(7,3)码是线性码。



表5．3．1例5．3．1的(7,3)码的码字与信息组对应关系




信息组码字


0000000000

0010011101

0100100111

0110111010

1001001110

1011010011

1101101001

1111110100


为了深入理解线性分组码的概念，将其与线性空间联系起来。由于每个码字都是一个长为n的(二进制)数组，因此可将每个码字看成一个二进制n重数组，进而看成二进制n维线性空间Vn(F2)中的一个矢量。n长的二进制数组共有2n个，每个数组都称为一个二进制n重矢量。显然，所有2n个n维数组将组成一个n维线性空间Vn(F2)。

(n,k)分组码的2k个n重就是这个n维线性空间的一个子集，若它能构成一个k维线性子空间，则它就是一个(n,k)线性分组码，这点可由上面的例子得到验证。

长为7的二进制7重共有27=128个，显然这128个7重是GF(2)上的一个7维线性空间，而(7,3)码的8个码字，是从128个7重中按式（5.3.1）的规则挑出来的。可以验证，这8个码字对模2加法运算构成阿贝尔（Abel）群，即该码集是7维线性空间中的一个3维子空间。(n,k)线性分组码又可定义如下： 

定义5．3．1二进制(n,k)线性分组码是GF(2)域上的n维线性空间Vn中的一个k维子空间Vn,k。

因为线性空间在模2加运算下构成阿贝尔加群，所以又称线性分组码为群码。

从上面的讨论可知，线性分组码的编码问题就是如何从n维线性空间Vn中挑选出一个k维子空间Vn,k，而选择的规则完全由n-k个校验方程决定。由于线性分组码对模2加满足封闭性，就为其最小距离的计算带来方便，具体有如下定理。

定理5．3．1一个(n,k)线性分组码中非零码字的最小重量等于码字集合C中的最小距离d0。

证明： 设有任两个码字Ca，Cb∈C。根据线性分组码性质，有Ca+Cb=Cc∈C。而Cc的码重等于Ca与Cb的码距d(Ca ; Cb)，即
W(Cc)=W(Ca+Cb)=d(Ca ; Cb)
Ca和Cb是C中任意两个码字，所以
Wmin(Ca+Cb)=Wmin(Cc)=d0［证毕］
由表5．3．1中(7,3)码的8个码字可见，除全零码字外，其余7个码字最小重量Wmin=4，而其中任二码字之间的最小距离d0=4。

根据线性分组码的封闭性不难得出如下结论。

定理5．3．2任何一个二元线性分组码中要么所有码字的重量都是偶数，要么偶数重量码字与奇数重量码字的数目相等。

证明： 令C表示任何一个线性二元分组码，A表示所有偶数重量的码字集合，B表示所有奇数重量的码字集合，显然C=A∪B。根据线性分组码的特点，无论是A或B中码字两两相加，还是从A和B中各选一个码字相加，得到的和矢量仍为该线性分组码集中的码字。

若B为空集，则C=A，这时所有码字都是偶数重量。若B不为空集，则至少有一个奇数重量的码字b，构成
b+A={b+a|a∈A}
集合b+A表示由集合A中的码字与b相加后所得的码字全体。由式W(C1C2)=W(C1)+W(C2)-2W(C1⊙C2)可知，奇数重量的矢量与偶数重量矢量之和为奇数重量的矢量，因此A+b中所有码字的重量为奇数，而且A+b中的码字数与A中码字的数量相同(这也是陪集的性质)，可见偶数重量码字与奇数重量码字的数目相等。

下面再说明集合B中的所有码字都在集合A+b中。设b′为B中任取的一个码字，b′和 b都是奇数重量，同样由式(W(C1C2)=W(C1)+W(C2)-2W(C1⊙C2))可知，奇数重量的矢量与奇数重量矢量之和为偶数重量的矢量，B中码字两两相加的码字是偶数重量，所以存在一个a∈A使b′+b=a，那么
b′=a-b=a+b∈b+A
式中利用了“二元码加法与减法等价”的性质。可见，集合B中的所有码字都在集合A+b中。即若B中有一个奇数重码字，则C中奇数重码字数目与偶数重码字数相等。

［证毕］

5．3．1．2生成矩阵G与一致校验矩阵H

(n,k)线性分组码的编码问题就是如何在n维线性空间Vn(F2)中找出满足一定要求的由2k个矢量组成的k维线性子空间C的问题。或者说，在满足给定条件(码的最小距离d0或码率R)下，如何根据已知的k个信息元求得n-k个监督元。由于是线性码，这些监督元一定是由若干线性方程构成的一个方程组，若n-k个监督元是独立的，则该方程组由n-k个线性方程构成。

例5．3．1中的(7,3)码。若c6、c5、c4代表3个信息元，c3、c2、cl、c0代表4个监督元，可以由下列线性方程组建立它们之间的关系：
1·c3=1·c6+0·c5+1·c41·c2=1·c6+1·c5+1·c41·c1=1·c6+1·c5+0·c41·c0=0·c6+1·c5+1·c4(5.3.2)
上述运算均为模2加。在已知c6、c5、c4后，可立即求出c3、c2、c1、c0。例如，M=(101)，即c6=1，c5=0，c4=1，代入式（5.3.2），可得4个监督元为(0011)，进而得到码字为(1010011)。根据式（5.3.2）对不同信息组进行计算，即可得到全部(7,3)码字。可见式（5.3.2）对确定该(7,3)码是非常关键的。式（5.3.2）称为一致校验方程，它直接反映了码字中信息元与监督元之间的约束关系。不过，从编码的角度看，利用式（5.3.2）逐个计算得到全体码字是很麻烦的，还需进一步寻求其内在规律。

1．  生成矩阵

已知(n,k)线性分组码的2k个码字组成n维矢量空间的一个k维子空间，而线性空间可由其基底张成，因此(n,k)线性分组码的2k个码字完全可由k个独立的矢量所组成的基底张成。设k个矢量为
g1=(g11g12…g1kg1，k+1…g1n)
g2=(g21g22…g2kg2，k+1…g2n)

gk=(gk1gk2…gkkgk，k+1…gkn)
将它们写成矩阵形式： 
G=g11g12…g1kg1，k+1…g1n
g21g22…g2kg2，k+1…g2n
gk1gk2…gkkgk，k+1…gkn(5.3.3)

(n,k)码中的任何码字均可由这组基底的线性组合生成，即
C=MG=(mk-1mk-2…m0)g11g12…g1ng21g22…g2ngk1gk2…gkn（5.3.4）
式中： M=(mk-1mk-2…m0)是k个信息元组成的信息组。

这就是说，每给定一个信息组，通过式（5.3.4）可求得其相应的码字。故这个由k个线性无关矢量组成的基底所构成的k×n矩阵G称为(n,k)码的生成矩阵。

(7,3)码可以从表5．3．1中的8个码字中任意挑选出k=3个线性无关的码字(1001110)、(0100111)和(0011101)作为码的一组基底，由它们组成G的行，可得
G=100111001001110011101

若信息组Mi=(011)，则相应的码字为
Ci=(011)100111001001110011101=(0111010)
它是G矩阵后两行相加的结果。

值得注意的是，线性空间(或子空间)的基底可以不止一组，因此作为码的生成矩阵G也可以不止一种形式。但不论哪种形式，它们都生成相同的线性空间(或子空间)，即生成同一个(n,k)线性分组码。

实际上，码的生成矩阵还可由其编码方程直接得出。例如，例5．3．1的(7,3)码可将编码方程改写为
c6=c6
c5=c5
c4=c4
c3=c6+c4
c2=c6+c5+c4
c1=c6+c5
c0=c5+c4
写成矩阵形式，即
［c6c5c4c3c2c1c0］=c6c5c4c3c2c1c0T=c6c5c4c6+c4c6+c5+c4c6+c5c5+c4T
=［c6c5c4］100111001001110011101
=［c6c5c4］G
故(7,3)码的生成矩阵为
G=100111001001110011101
可见，生成矩阵可由编码方程的系数矩阵转置得到。

在线性分组码中经常用到一种特殊的结构，如上例(7,3)码的所有码字的前三位，都是与信息组相同，属于信息元，后四位是校验元。这种形式的码称为系统码。

定义5．3．2若信息组以不变的形式，在码字的任意k位中出现，则该码称为系统码； 否则，称为非系统码。

目前最流行的有两种形式的系统码： 一种是信息组排在码字(cn-1，cn-2，…，c0)的最左边k位，cn-1，cn-2，…，cn-k，如表5．3．1中所列出的码字就是这种形式； 另一种是信息组被安置在码字的最右边k位，ck-1，ck-2，…，c0。

若采用码字左边k位(前k位)是信息位的系统码形式(今后均采用此形式)，则式（5.3.3）所示的G矩阵左边k列应是一个k阶单位方阵Ik(gl,l=g2,2=…=gk,k=1，其余元素均为0)。因此，系统码的生成矩阵可表示成
G0=10…0g1，k+1…g1n01…0g2，k+1…g2n00…1gk，k+1…gkn=［IkP］
式中： P为k×(n-k)矩阵。

只有这种形式的生成矩阵才能生成(n,k)系统型线性分组码，即标准形式，因此，系统码的生成矩阵也是一个典型矩阵(或称标准阵)。考察典型矩阵，便于检查G的各行是否线性无关。如果G不具有标准型，虽能生成线性码，但码字不具备系统码的结构，此时可将G的非标准型经过行初等变换变成标准型G0。由于系统码的编码与译码较非系统码简单，而且对分组码而言，系统码与非系统码的抗干扰能力完全等价，故若无特别声明，仅讨论系统码。

2．  一致校验矩阵

前面介绍过，编码问题是在给定的d0或码率R下如何利用从已知的k个信息元求得r=n-k个校验元。例5．3．1中的(7,3)码的4个检验元由式（5.3.2）所示的线性方程组决定。为了更好地说明信息元与校验元的关系，现将式（5.3.2）填补系数并移项，变换为

1·c6+0·c5+1·c4+1·c3+0·c2+0·c1+0·c0=01·c6+1·c5+1·c4+0·c3+1·c2+0·c1+0·c0=01·c6+1·c5+0·c4+0·c3+0·c2+1·c1+0·c0=00·c6+1·c5+1·c4+0·c3+0·c2+0·c1+1·c0=0
用矩阵表示这些线性方程： 
1011000111010011000100110001=c6c5c4c3c2c1c0=0000=0T（5.3.5）
或
［c6c5c4c3c2c1c0］1110011111011000010000100001=［0000］=0（5.3.6）
将上面方程的系数矩阵用H表示： 
H=1011000111010011000100110001
式（5.3.5）或式（5.3.6）表明，C中的各码元是满足由H所确定的r(r=n-k)个线性方程的解，故C是一个码字； 若C中码元组成一个码字，则一定满足由H所确定的r个线性方程。故C是式（5.3.5）或式（5.3.6）解的集合。显而易见，H一定，便可由信息元求出校验元，编码问题迎刃而解； 或者说，要解决编码问题，只要找到H即可。由于H矩阵是一致校验方程组的系数矩阵，它也反映了码字中的约束关系，故称其为一致校验矩阵。按H所确定的规则也可求出(n,k)码的所有码字。

一般而言，(n,k)线性码有r(r=n-k)个校验元，若这些校验元是独立加入的，则一致校验方程必须有r个独立的线性方程。所以(n,k)线性码的H矩阵由r行和n列组成，可表示为
H=h1,n-1h1,n-2…h10h2,n-1h2,n-2…h20hr,n-1hr,n-2…hr0
这里hij中，i代表行号，j代表列号。因此，H是一个r行n列矩阵。由H矩阵可建立码的r个线性方程： 
h1,n-1h1,n-2…h10h2,n-1h2,n-2…h20hr,n-1hr,n-2…hr0cn-1cn-2c1c0=0T
简写为
HCT=0T（5.3.7）
或
CHT=0（5.3.8）
式中： C=［cn-1 cn-2… c1 c0］，CT是C的转置； 0是一个全为0的r重。

综上所述，将H矩阵的特点归纳如下。

（1） H矩阵的每一行代表一个线性方程的系数，它表示求一个校验元的线性方程。

（2） H矩阵每一列代表此码元与哪几个校验方程有关。

（3） 由此H矩阵得到的(n,k)分组码的每个码字Ci(i=1，2，…，2k)都必须满足由H矩阵行所确定的线性方程，即式（5.3.7）或式（5.3.8）。

（4） 若(n,k)码的r(r=n-k)个校验元是独立的，则H矩阵必须有r行，且各行之间线性无关，即H矩阵的秩为r。若将H的每一行看成一个矢量，则此r个矢量必然张成n维矢量空间中的一个r维子空间Vn，r。

（5） 考虑到生成矩阵G中的每一行及其线性组合都是(n,k)码中的一个码字，故有
GHT=0（5.3.9）
或
HGT=0T（5.3.10）
这说明由G和H的行生成的空间互为零空间。也就是说，H矩阵的每一行与由G矩阵行生成的分组码中每个码字内积均为零，即G和H彼此正交。

（6） 由上面的例子不难看出，(7,3)码的H矩阵右边4行4列为一个4阶单位方阵，一般而言，系统型(n,k)线性分组码的H矩阵右边r列组成一个单位方阵Ir，故有
H=［QIr］
式中： Q为r×k矩阵。

这种形式的矩阵称为典型阵或标准阵，采用典型阵形式的H矩阵更易于检查各行是否线性无关。

（7） 由式（5.3.10）可得
［QIr］［IkP］T=［QIr］IkPT=Q+PT=0T
这说明
P=QT
或
PT=Q
这就是说，P的第一行就是Q的第一列，P的第二行就是Q的第二列，……。因此，H一定，G也就一定； 反之亦然。

3．  对偶码

(n,k)码是n维矢量空间中的一个k维子空间Vn，k，可由一组基底即G的行张成。由式（5.3.9）可以看出，由H矩阵的行所张成的n维矢量空间中的一个r维子空间Vn，r是(n,k)码空间Vn，k的一个零空间。由线性代数知，Vn，r的零空间必是一个k维子空间，它正是(n,k)码的全体码字集合。若把(n,k)码的一致校验矩阵看成(n,r)码的生成矩阵，将(n,k)码的生成矩阵看成(n,r)码的一致校验矩阵，则称这两种码互为对偶码。相应地称Vn，k和Vn，r互为对偶空间。

例5．3．2求例5．3．1所述(7,3)码的对偶码。

显然，(7,3)码的对偶码应是(7,4)码，因此，(7,4)码的G矩阵就是(7,3)码的H矩阵： 
G(7，4)=H(7，3)=1011000111010011000100110001
由此可得出(7,4)码的码字如表5．3．2所示。



表5．3．2(7,4)线性分组码




信息元码字信息元码字


0 0 0 00 0 0 0 0 0 01 0 0 01 0 0 0 1 0 1

0 0 0 10 0 0 1 0 1 11 0 0 11 0 0 1 1 1 0

0 0 1 00 0 1 0 1 1 01 0 1 01 0 1 0 0 1 1

0 0 1 10 0 1 1 1 0 11 0 1 11 0 1 1 0 0 0

0 1 0 00 1 0 0 1 1 11 1 0 01 1 0 0 0 1 0

0 1 0 10 1 0 1 1 0 01 1 0 11 1 0 1 0 0 1

0 1 1 00 1 1 0 0 0 11 1 1 01 1 1 0 1 0 0

0 1 1 10 1 1 1 0 1 01 1 1 11 1 1 1 1 1 1


若一个码的对偶码就是它自己，则称该码为自对偶。自对偶码必是(2m,m)形式的分组码，(2,1)重复码就是一个自对偶码。











5．3．2线性分组码的译码方法

只要找到了H矩阵或G矩阵，便解决了编码问题。经编码后发送的码字，由于信道干扰可能出错，收方怎样发现或纠正错误？这就是译码要解决的问题。

设发送的码字C=(cn-1,cn-2，…，c1,c0)，信道产生的错误图样E=(en-1,en-2，…，el,e0)，而接收序列R=(rn-1,rn-2，…， rl,r0)，那么R=C+E，即有ri=ci+ei，其中ci，ri，ei∈GF(2)。译码的任务就是要从R中求出E，从而得到码字估值C=R-E。






5．3．2．1标准阵列译码

标准阵列译码法是对线性分组码进行译码最一般的方法，这种方法的原理也是对解释线性分组码概念最直接的描述。

在5．1．3节中已介绍，(n,k)码中任一码字C在有噪信道上传输，接收矢量R可以是n维线性空间Vn(F2)中任一矢量。收端译码有很多种，但其本质就是对码字进行分类，以便从接收矢量中确定发送码字的估值。

二元(n,k)码的2k个码字集合是n维矢量空间的一个k维子空间。如果将整个n维矢量空间的2n个矢量划分成2k个子集 1， 2，…， 2k，且这些子集不相交，即彼此不含有公共的矢量，每个子集 i包含且仅包含一个码字Ci(i=1，2，…，2k)，从而建立一一对应的关系：
C1 1，C2 2，…，C2k 2k

当发送一个码字Ci，而接收字为Ri，则Ri必属于且仅属于这些子集之一。若Ri落入 i中，则译码器可判断发送码字是Ci。

这样做的风险是： 如子集 i是对应原发送的码字，则译码正确； 若 i并不对应原发送的码字，则译码错误。当然，在有扰信道找到一个绝对无误的译码方案是不可能的，但可以找到一种使译码错误概率最小的方案。那么怎样才能将n维矢量空间划分成符合上述要求的2k个子集？最一般的方法是按下列方法制作一个表。先把2k个码矢量置于第一行，并以零码矢C1=(0,0,0,…,0)为最左面的元素，在其余2n-2k个n重中选择一个重量最轻的n重E2，并置E2于零码矢Cl的下面，于是表的第二行是E2和每个码矢Ci相加，并把E2+Ci置于Ci的下面即同一列，完成第二行。第三行是再从其余的n重中任选一个重量最轻的n重E3置于Ci的下面(第三行第一列)，同理将E3+Ci置于Ci之下完成第三行，以此类推，一直到全部n重用完为止。于是就得到表5．3．3。



表5．3．3标准阵译码表




码字C1(陪集首) C2…Ci…C2k


禁用码组
E2C2+E2…Ci+E2…C2k+E2

E3C2+E3…Ci+E3…C2k+E3



E2n-kC2+E2n-k…Ci+E2n-k…C2k+E2n-k


表5.3.3共有2n-k行2k列，其中每一列就是含有Ci的子集 i。从按照上述方法列出的表可以看出： 表中同一行中没有两个n重是相同的，也没有一个n重出现在不同行中，所以所划分的子集 i之间是互不相交的，即每个n重在此表中仅出现一次，这个表称为线性分组码的标准阵列。译码表或简称标准阵，而每一行称为一个陪集，每一行最左边的那个n重Ei称为陪集首。而表的第一行即为(n,k)分组码的全体，又称子群。

收到的n重R落在某一列中，则译码器就译成相应于该列最上面的码字。因此，若发送的码字码为Ci，收到的R=Ci+Ej(1≤j≤2n-k，E1是全0矢量)，则能正确译码。若收到的R=Cl+Ej(l≠i)，则产生了错误译码。现在的问题是如何划分陪集，使译码错误概率最小？这最终取决于如何挑选陪集首。因为一个陪集的划分主要取决于子群，而子群就是2k个码字，这已确定，因此余下的问题就是如何决定陪集首。

在信道误码率P<0．5的BSC中，传输出错情况应为少数，产生1个错误的概率比产生2个错误的大，产生2个错误的比3个错误的大……也就是说，错误图样重量越小，产生的可能性越大。因此，译码器必须首先保证能正确纠正这种出现可能性最大的错误图样，即重量最轻的错误图样。这相当于在构造译码表时要求挑选重量最轻的n重为陪集首，放在标准阵中的第一列，而以全0码字作为子群的陪集首。这样得到的标准阵能使译码错误概率最小。由于这样安排的译码表使得Ci+Ej与Ci的距离保证最小，因而也称为最小距离译码，在BSC下，它们等效于最大似然译码。

构造一般(n,k)码标准阵列的方法归纳如下。

（1） 将Vn，k的2k个码字作第一行，全零矢量作其陪集首，即作为E1。

（2） 在剩下的禁用码组中挑选重量最小的n重作第二行的陪集首，以E2表示，以此求出C2+E2，C3+E2，…，C2k+E2分别列于对应码字Ci所在列，从而构成第二行。

（3） 依方法（2）所述方法，直至将2n个矢量划分完毕。

这样就得到如表5．3．3所示的标准阵列。

从标准阵列可以看出，陪集首的集合就是一个可纠正错误图样Ei的集合，而各码字所对应的列就是该码字的正确接收区。因此，在BSC下，二元线性分组码正确译码概率为
Pc=∑2r-1j=0pW(j)(1-p)n-W(j)=∑ni=0Aipi(1-p)n-i
式中： r=n-k； W(j)为第j个陪集首的重量； Ai是重量为i的陪集首的个数； A=(A0A1 …An)是陪集首的重量分布矢量； p为信道误码率。

从几何的角度理解，码的陪集划分相当于把n维线性空间Vn 按照该线性分组码Vn,k划分。共有2k个码字，相当于有2k个互不相交的球，球的半径是陪集首中错误图样的最大码重，这2k个球把整个线性空间Vn充满，所有禁用码组将分别落在不同的球中。当发送某个码字时，如果错误图样的影响使接收序列位于发送码字的球内，这相当于错误图样出现在陪集首，错误图样中“1”的个数很少，错误不是太严重，则接收端可以根据标准阵正确译码； 如果错误图样的影响使接收码字序列落在其他许用码字的球内，这相当于错误很严重，错误图样中“1”的个数很多，错误图样不属于陪集首，则接收端根据标准阵译码就会产生译码错误。

结合这个几何解释可以分析线性分组码检错、纠错能力与最小码距d0之间的关系。

首先，为了能检测出一个码字中发生的全部e个错误，要求d0≥e+1。只有这样，该e个错误才不至于把一个许用码字变为另一个许用码字。其次，为了能纠正一个码字中发生的全部t个错误，要求d0≥2t+1，如图5．3．1所示。只有满足了这个条件才能保证这个t位错误引起的禁用码组仍位于以发送码字为球心的球内。最后，在一个码字中，为了能纠正所有t个错误； 并同时检测所有e个错误，要求d0≥t+e+1(t<e)。当误码数小于t时，能纠正所有t个错误; 当误码数在(t，t+e+1］ 时，能检测所有e个错误。这即是基于线性分组码对定理5．1.2~定理5．1.4的解释。



图5．3．1对线性分组码纠错能力的几何解释


例5．3．3以(6,3)码为例排列出它的标准阵列。对于(6,3)码，它的生成矩阵为
G=100011010101001110
此码共有8个码字








信息组码字

000000000

001001110

010010101

011011011

100100011

101101101

110110110

111111000


它的标准阵列如表5．3．4所示。



表5．3．4(6,3)码标准阵列




000000001110010101100011011011101101110110111000

000001001111010100100010011010101100110111111001

000010001100010111100001011001101111110100111010

000100001010010001100111011111101001110010111100
续表


001000000110011101101011010011100101111110110000

010000011110000101110011001011111101100110101000

100000101110110101000011111011001101010110011000

001001000111011100101010010010100100111111110001


由表5．3．4可以看到，用这种标准阵译码，需要把2n个n重存储在译码器中。所以采用这种译码方法的译码器的复杂性随n指数增长，很不实用。简化查表的步骤需引入伴随式的概念。













5．3．2．2伴随式译码

由于(n,k)码的任何一个码字C均满足式（5.3.9）或式（5.3.10），可将接收矢量R用两式中的一个进行检验。若
RHT=(C+E)HT=CHT+EHT
=EHT=0
则R满足校验关系，可认为它是一个码字； 反之，则R有错。

定义5．3．3设(n,k)码的一致校验矩阵为H，R是发送码字C的接收矢量，称 
S=RHT=EHT(5.3.11)
为接收矢量R的伴随式或校正子。

显然，若E=0，则S=0，那么R就是C； 若E≠0，则S≠0，如能从S得到E，则从C=R-E即可恢复发送的码字。可见，S仅与E有关，它充分反映了信道干扰的情况，而与发送的是什么码字无关。

将(n,k)码的一致校验矩阵写成列矢量的形式： 
H=［hn-1hn-2 …hn-i…h1h0］
=h1,n-1h1,n-2…h10h2,n-1h2,n-2…h20hr,n-1hr,n-2…hr0
式中: hn-i对应H矩阵的第i列，它是一个r=n-k重列矢量。

若码字传送发生t个错误，不失一般性，设码字的第i1，i2，…，it位有错误，则错误图样可表示成
E=(0…ei10…ei20…eit…0)
那么伴随式
S=EHT=［0…ei10…ei20…eit…0］hn-1hn-2hn-ih0
=ei1hn-i1+ei2hn-i2+…+eithn-it（5.3.12）
这说明,S是H矩阵中E不等于0的那几列hn-i的线性组合。因为hn-i是r重列矢量，所以S也是一个r重的矢量。当传输没有错误，即E的各位均为0时，S是一个r重全零矢量。

注意，若E本身就是一个码字，即E∈(n,k)码，则此时计算S必须等于0。此时的错误不能发现，也无法纠正，称为不可检错误图样。

伴随式在标准阵列中有如下性质。

定理5．3．3每个陪集全部2k个矢量都有相同的伴随式，而不同陪集有不同的伴随式。

证明： 如果第l行陪集首为El(看成错误图样)，那么第l行任意n重矢量的伴随式为
(El+Ci)HT=Sl（i=2，3，…，2k）
Sl=ElHT+CiHT=ElHT
可见,l陪集的伴随Sl与Ci无关，故同一陪集中的矢量其伴随式相同。若第l陪集和第t陪集(l<t)的伴随式是相同的，则有
Sl=ElHT
St=EtHT
Sl+St=(El+Et)HT=0
式中: El+Et是码字。

假如El+Et=Ci，则有
El=Et+Ci
那么El在第t个陪集中。这个结论和标准阵列的构成原则矛盾，故不同陪集的伴随式不可能相同。［证毕］

可见,陪集首和伴随式有一一对应的关系，实际上这些陪集首也就代表着可纠正的错误图样。根据这一关系可把上述标准阵译码表进行简化，得到一个简化译码表。

例5．3．4如例5.3.3中的(6,3)码标准阵，可简化为表5．3．5所示的译码表。译码器收到R后，与H矩阵进行运算得到伴随式S，由S查表得到错误图样E^，从而译出码字C^=R-E^。因此，这种译码器中不必存储所有2n个n重，而只存储错误图样E与2n-k个(n-k)重S。



表5．3．5(6,3)码简化译码表




错误图样000000100000010000001000000100000010000001001001

伴随式000011101110100010001111


综上所述，利用伴随式译码表译码的步骤如下。

(1) 计算接收矢量R的伴随式S=RHT。

(2) 根据计算出的伴随式找出对应的陪集首E^(这是根据S做出的E的估值)。

(3) 码字估值C^=R+E^被认为是发送码字，例如，设发送码字C4=(100011)，接收矢量R=(101011)(实际错误图样为E=(001000))，则R的伴随式为
S=RHT=(101011)011100101010110001T=(110)
从表5．3．5中找到与S=(110)相对应的陪集首为(001000)，于是译码输出为
C=(101011)+(001000)=(100011)
从表5．3．4可知，因为E^在陪集首中，所以译码正确。当信道错误图样E=(101000)时，同样的码字C=(100011)，经传输得R=(001011)，根据式（5.3.10）得S=(101)，再由表5．3．5求得E^=(010000)，这时认为C^=(001011)+(010000)=(011011)≠C，译码是错误的，原因是E不是标准阵列的陪集首。由表5．3．4可知，此矢量已在(010000)为陪集首的陪集中出现，不能作为陪集首，所以根据表5．3．5译码结果也是错的。原因是(6,3)码的dmin=3，它可纠正任何一位差错，而不能普遍地纠正两位差错。该码只能纠正一种有两位差错的信道错误图样，即
E=(001001)
总之，线性码正确译码的充要条件为信道实际错误图样是标准阵列的陪集首，这个结论对任何线性分组码的译码方法都适用。

根据上述，线性分组码的译码器应如图5．3．2所示。



图5．3．2线性分组码的译码器


简化译码表虽然把译码器的存储容量降低了很多，但由于(n,k)分组码的n、k通常比较大，即使用这种简化译码表，译码器的复杂性还是很高的。例如，一个［100，70］分组码，共有230≈109个伴随式及错误图样，译码器要存储如此多的图样和n-k重是不太可能的。因此，在线性分组码理论中，如何寻找简化译码器是最中心的研究课题之一。为了寻找更加简单的比较实用的译码方法，仅有线性特性是不够的，还需要附加一些其他特性，如循环特性。这就是5．4节要介绍的循环码。






5．3．3线性分组码的纠错能力
5．3．3．1一致校验矩阵与纠错能力

由5．1．2节的介绍可知，从一个码的最小距离中得出该码的纠检错能力，线性分组码同样满足定理5．1．2~定理5．1．5的结论。进一步考察线性分组码的一致校验矩阵，会发现它与纠错能力之间的关系。

定理5．3．4(n,k)线性分组码具有最小距离d的充分必要条件是H矩阵中任意d-1列线性无关,至少有一种d列线性相关。

证明： 设一致校验矩阵为H，用hj(j=1,2，…，n)表示H矩阵中n个列矢量，即
H=h1n-1h1n-2…h10hrn-1hrn-2…hr0r×n=［hn-1hn-2…h0］
则对于每个码字C=(cn-1cn-2…c0)，满足校验方程
CHT=0
该方程可以写为
∑n-1i=0cihTi=0
上式说明码字C中非零的码元位对应的H矩阵那些列的线性组合为0。于是，若一个二元码字重量为w，则H矩阵中与该码字中w个取值为“1”码元对应的列矢量线性相关。

一个二元线性码，如果它的最小汉明距离为d，即该码的最小汉明重量为d，则它的校验矩阵H中有d列矢量线性相关，而任意d-1个列矢量是线性独立的； 否则，就存在一个重量小于d的矢量C′，使C′HT=0。这与码的最小重量为d相矛盾。

［证毕］

因为一致校验矩阵H与最小距离d有明确的关系，所以研究中往往以一致校验矩阵H定义一个线性分组码，LDPC就是如此。

从式（5.3.12）中也可以看出，伴随式S是错误图样E中不为0的码元位所对应的H矩阵的列的线性组合。若一个(n,k)码要能纠正所有单个错误，则由所有单个错误的错误图样确定的S均不相同且不等于0，这意味着，H矩阵各列不为0且各不相同。那么，一个(n,k)码的H矩阵为怎样的形式才能纠正小于等于t个错误？这就必须要求小于或等于t个错误的所有可能组合的错误图样，都必须有不同的伴随式与之对应。因此，若有
E1=(0…0ei1…ei2…eit0…0)≠(0…0e′i1…e′i2…e′it0…0)=E2
则要求
ei1hn-i1+ei2hn-i2+…+eithn-it≠e′i1h′n-i1+e′i2h′n-i2+…+e′ith′n-it
ei1hn-i1+ei2hn-i2+…+eithn-it+e′i1h′n-i1+e′i2h′n-i2+…+e′ith′n-it≠0
这说明，(n,k)码要纠正小于或等于t个错误，其H矩阵中任意2t列须线性无关。由此得如下定理。

定理5．3．5任一(n,k)线性分组码若要纠正小于或等于t个错误，其充要条件是H矩阵中任何2t列线性无关。

定理5．3．4和定理5．3．5是构造任何类型线性分组码的基础，由此不难看出： 

（1） 根据这些定理，由H列的相关性就可以直接知道码的纠错、检错能力。

（2） 为了构造最小距离d≥e+1(为检测不大于e个错误)或d≥2t+1(为纠正不大于t个错误)的线性分组码，其充要条件是要求H中任意d-1(或2t)列线性无关。例如，要构造最小距离为3的码，则要求H任意3-1=2列线性无关。对于二元域上的码，要求H当且仅当满足无相同的列和无全0的列，就可纠正所有单个错误。

（3） 因为交换H矩阵的各列不会影响码的最小距离，所以所有列矢量相同但排列位置不同的H矩阵所对应的分组码，在纠错能力和码率上是等价的。






5．3．3．2码纠错能力限

基于上述定理不难得出几个关于码的纠错能力界限的结论。

定理5．3．6(Singleton限)任一线性分组码的最小距离(或最小重量)d0均满足
d0≤n-k+1
证明：  任何一个线性码可以变换成等价的系统码，则该码中至少有一个码字重量不大于 n-k+1。因为这个码中至少存在一个码字，它的信息位仅有一个“1”，校验位最多可能有n-k 个“1”，所以这个码字的最小汉明重量不大于n-k+1，因此这个线性码的最小汉明距离d0≤n-k+1。

［证毕］

满足d0=n-k+1的线性分组码称为极大最小距离可分（Maximum Distance Separable,MDS）码。在同样n、k下，由于d0最大，因此纠错能力更强，所以设计这种码是编码理论中人们感兴趣的一个课题。

下面一个定理将告诉我们，在已知信息位k的条件下，如何去确定监督位r=n-k，即确定码长，才能满足对纠错能力t的要求。这个问题在设计一个码组时是很重要的。

定理5．3．7(汉明限)若C是k维n重二元码，当已知k时，要使C能纠正t个错，则必须有不少于r个校验位，并且使r满足
2r-1≥∑ti=1Cin
证明： 假设C的一致校验矩阵为H，伴随式为
S=RHT，R∈Vn(F2)

C是k×n的，则H是r=n-k行n列，且在S的2r种状态除去全零状态，其余还有2r-1种非零状态。

另外，在一个n重矢量中，它们的错误图样也是n重。错误图样用矢量E代表，可计算W(E)=t的错误图样个数，有
W(E)=1的个数为C1n
W(E)=2的个数为C2n
W(E)=3的个数为C3n

W(E)=t的个数为Ctn
则错误码元不大于t个的错误图样共有∑ti=1Cin种。

若要能使C纠正t个错误，S的状态数要大于错误图样总数，只有满足以上条件才能建立起伴随式与错误图样的一一对应关系。因此有
2r-1≥∑ti=1Cin（5.3.13）
当满足2r-1=∑ti=1Cin时，这样的码称为完备码。这种码的校验元得到了最充分的利用。而式（5.3.13）给出的界限称为汉明限，它也可改写为
n-k≥log2∑ti=1Cin
上式给出在已知n、k和t时所需要的监督位数。该式又称为Hamming不等式。

迄今为止，已找到的完备码有Hamming码，(23,12)非本原BCH码(又称Golay码)及三进制的(11,6)码。














5．3．3．3示例： Hamming码

前面曾多次提到汉明距离、汉明重量等术语，都是为了纪念对纠错编码作出杰出贡献的科学家汉明而命名的。Hamming码的命名当然更直接，这种码是由汉明在1950年首先提出的。它有以下特征：
码长:n=2m-1
信息位数:k=2m-m-1
监督码位:r=n-k=m
最小距离:d=3
纠错能力:t=1
这里m为大于或等于2的正整数，给定m后，即可构造出具体的(n,k)Hamming码。这可以从建立一致校验矩阵着手。我们已经知道，H矩阵的列数就是码长n，行数等于m。如m=3，就可计算出n=7，k=4，因而是(7,4)线性码。其H矩阵正是用2r-1=7个非零3重作列矢量构成的，如下所示： 
H=000111101100111010101
这时H矩阵的对应列正好是十进制数1~7的二进制表示，对于纠1位差错来说，其伴随式的值就等于对应的H的列矢量，即错误位置。所以这种形式的H矩阵构成的码很便于纠错，但这是非系统的(7,4)Hamming码的一致校验矩阵。如果要得到系统码，可调整各列次序来实现：
H0=111010001110101101001=［QI3］（5.3.14）
有了H0，按照式（5.3.14）就可得到系统码的校验位，如其相应的生成矩阵为
G0=［I4QT］=1000101010011100101100001011
Hamming码的译码方法如5．3．2节中所述，可以采用计算伴随式，然后确定错误图样并加以纠正的方法。

值得一提的是，(7,4)Hamming码的H矩阵并非只有以上两种。原则上讲，(n,k)Hamming码的一致校验矩阵有n列m行，它的n列分别由除了全0之外的m位码组构成，每个码组只在某列中出现一次。而H矩阵各列的次序是可变的。

容易证明，Hamming码实际上是t=1的完备码。

Hamming码如果再加上一位对所有码元都进行校验的监督位，则监督码元由m增至m+1，信息位不变，码长由2m-1增至2m，通常把这种(2m，2m-1-m)码称为扩展Hamming码。扩展Hamming码的最小码距增加为4，能纠正1位错误同时检测2位错误，简称纠1检2错码。例如，(7,4)Hamming码可变成(8,4)扩展Hamming码(又称增余Hamming码)。(8,4)码的H矩阵如下：
H(8，4)=11111111111010000111010011010010
它的第一行为全1行，最后一列的列矢量为［1000］T，它的作用是使第8位成为偶校验位，而前7位码元同(7,4)码。这种H矩阵任何3列都是线性独立的，而只有4列才能线性相关，按照定理5．3．4可知它的dmin=4，可实现纠1检2错。













5．3．4线性分组码的派生与组合
5．3．4．1由一个已知码的派生

人们往往需要从一个已知的(n,k)线性码出发来构造一个新的线性分组码，使得某些参数能符合实际的需要。5．3．1．2节中介绍的对偶码就是其中的一种方法。下面再介绍几种对已知码的G或H矩阵进行适当修正和组合，以构造新码的方法。这些方法虽然很简单，但很实用，而且也是以后构造各种复合码的基础。

1．  扩展码

设C是一个(n，k，d)线性分组码，它的码字有奇数重量也有偶数重量。若对每个码字C=(cn-1,cn-2… c1,c0)增加一个全校验位c′0，满足以下校验关系：
cn-1+…+c0+c′0=0
这样得到的新码C′=［C|c′0］，是一个(n+1，k)线性码。若原来的一致校验矩阵为H，则C′的一致校验矩阵为
H′=1…110H0
由H矩阵列的相关性与码的最小距离的关系可得，若原码C的最小距离d是奇数，则C′的最小距离是偶数d+1。例如，前面介绍的(8,4)扩展Hamming码即是由(7,4)Hamming码扩展得到。

2．  凿孔码(删余码)

与扩展码(增加一位校验位)相对应的是凿孔码，它把(n，k)线性分组码C中码字的一些校验位删除(或者说进行凿孔)，从而得到一个新的线性码C′，这时码字长度会减少，但信息位数目不变，因此码率会更高。

凿孔码一般是在设计好一个线性分组码后，希望提升码率时采取的派生方法，在卷积码和Turbo码中也经常使用(一般会设计一个凿孔图案)。其中一个典型情况是删余码，即在原码基础上删除一位校验元。删余码的最小距离可能比原码小1。

3．  除删码(增余删信码)

在原码的基础上增加一些校验元，删去一些信息元，保持码长不改变，但明显码率会降低。一种典型的增余删信码是除删码，它是在原(n，k)码的基础上增加一位全校验元，删去一位信息元，得到(n，k-1)线性分组码，其一致校验矩阵H′是在原码的H矩阵下加一个全1行。因为有全1行，意味着所有码字的重量皆为偶数。这种除删码过程是在原码中挑选所有偶数重量的码字组成的新码，码字数目将少了一半。如果原来码字最小距离为奇数，则新的除删码的最小距离将增加1，成为偶数。

4．  增广码(增信删余码)

增广码Ca是在原码C的基础上，增加一个信息元，删去—个校验元得到的。因此,新码的码长与原码相同，但信息位长度加1。若二元(n，k，d)线性码中不包含分量为全“1”的码字，则可以把这个全“1”矢量1加入码C中，同时把全1码字与C中每个码字之和添加到原来码中，这样就构成了一个增广码Ca，即Ca=C∪(1+C)，则其生成矩阵之间的关系为
G(a)=1…1G
可见，Ca是一个(n，k+1，da)的线性分组码，其中
da=min{d,n-max(W(Ci))},Ci∈C
于是，增广码的最小距离一般是减小的。

5．  缩短码

在某些情况下，已设计好的编码不能满足实际应用对码长的要求，可以对原码进行缩短。缩短码去除了原来线性分组码中前i个信息位，具体做法是把原来(n，k)线性分组码C中前i位(cn-1~cn-i)为0的码字选取出来，再把这i个信息位删除掉，组成一个新的子集，这样构成的是一个(n-i，k-i)缩短码。由于缩短码是k维空间Vn,k(码C的全体码字集合)中取前i位均为0的码字组成的一个子集，显然该子集是Vn,k空间中的一个k-i维的子空间Vn,k-i。因为线性分组码的H矩阵列对应码字每一位码元的校验约束关系，因此缩短码的一致校验矩阵H′是删除原码的H矩阵前i列，而其生成矩阵G′则是去掉原码生成矩阵G中前i行前i列，可见缩短码的最小距离不会比原码的小，但码率会有所降低，即新码的码率
R′=k-in-i<kn
6．  延长码(增信码)

与缩短码相对应的是延长码。首先在原(n，k)线性码C的基础上通过增加一个全1码字来增广这个码集，然后增加一个全校验位来扩展它，这样构成一个(n+1，k+1)分组码。

图5．3．3中以Hamming码(2m-1，2m-1-m，3)为例说明构成新码的6种方法及相互关系。



图5．3．3Hamming码的各类派生码之间的关系图


5．3．4．2乘积码

1994年，Pyndiah提出Turbo乘积码(Turbo Product Code，TPC)及其单输入单输出（SISO）迭代译码方案，该码可以做到高码率、近信道容量时仍可保持较好性能。另外，TPC对于带宽应用是很具吸引力的，与串行TCMRS码比较，TPC能得到0．85dB的提高； 另外，TPC可以很容易地将最小距离保持在16、36或更大，从而避免“错误平层”效应； 此外，TPC的译码时延也可以通过将多个子译码器并行而大幅度减小。

由于TPC编码的优异性能，它在传统的国际卫星通信和区域卫星通信系统中有着广泛的应用前景。事实证明，TPC技术功能强大且具有灵活性，可为各行业的用户和卫星运营商带来明显的效益。另外，TPC增强的编码增益和带宽效率可以明显降低转发器成本，这一技术也可用来解决许多其他问题，如特小天线的通量密度降低问题。它同时可应用于微波、高清电视（HDTV）、光纤、数字视频广播（DVB）等。2001年9月IEEE公布了宽带无线接入系统的空中无线接口草案802．16中TPC被推荐为信道编码方式。

1．  TPC的构造

TPC用两个或两个以上的分组码构造较长的码，从而提高码的性能。以二维TPC为例，假设有两个线性分组码分别为C1(n1,k1,d1)、C2(n2,k2,d2)，其中，ni、ki、di(i=1,2)分别代表码长、信息位长、最小汉明距离。信息位以k1×k2的形式放入行列阵列中，先用码C2(n2,k2,d2) 对每行进行编码(共k1行)，再用码C1(n1,k1,d1)对每列进行编码(共n2列)，如图5．3．4(a)所示。此二维TPC可写成(n1,k1,d1)×(n2,k2,d2)，其码率为(k1×k2)/(n1×n2)。



图5．3．4TPC编码结构图


同样的方法可构造三维立体TPC。如图5．3．4(b)所示，首先构造k3个二维TPC(n1,k1,d1)×(n2,k2,d2)，然后在Z方向上进行C3(n3,k3,d3)线性分组编码，这就构成了三维立体TPC(n1,k1,d1)×(n2,k2,d2)×(n3,k3,d3)。其他多维的TPC也以类似的步骤来构造。对于多维TPC(假设为m维，m≥2)，其最小距离和码率分别为
d=d1×d2×d3×…×dm
R=k1n1×k2n2×k3n3×…×kmnm
作为TPC各维上的分量码通常为Hamming码、扩展Hamming码、奇偶校验码、BCH码和扩展BCH码，RS码和扩展RS码等线性分组码。目前国际上多采用前三种码型，其编译码相对较简单。TPC除分量码码型可变外，还可以进行一定的变型： 先对各维信息位缩短后再编码，可以得到缩短型TPC； 在对角线上加入奇偶校验形成“超轴”，可以得到增强型TPC，这为TPC提供了更多的灵活选择。在TPC中各维上分量码的不同，可得到不同的编码码率，这对IEEE 802．16宽带无线接入网中码率自适应是非常重要的。

2．  TPC迭代译码算法

若采用最大似然译码方法，性能可以达到最优，但随着码长的增加，复杂度指数倍增长。在性能和复杂性两方面综合考虑，可采用基于Chase2的次优译码算法。

算法描述如下。

假设发送端码字E=(e1,…,ei,…,en)，ei∈{+1,-1}，经过高斯白噪声信道(AWGN)，信道样值序列G=(g1,…,gi,…，gn)，标准方差为σ； 接收端序列R=E+G，其中R=(r1,…,ri，…,rn)。先对R进行硬判决，得到序列Y=(y1,…,yi,…,yn)，yi=0．5(1+syn(ri))，yi∈{0,1}，再进行三步chase2译码算法。

步骤一： 利用|ri|值确定Y序列中可信度最小的p=4个位置。

步骤二： 在最小可信度位置上分别取“0”“1”，其他位置取“0”，可得到q=2p个测试图样Tq。

步骤三： 生成测试序列Zq，Zq=YTq。对于Zq进行代数译码得到码集Cq。

随后采用欧几里得距离最小原则在码集Cq中寻找最佳码字D，并同时寻找竞争码字C(仅当前位与D不同)。按下式计算外信息参与下次迭代：
wj=|R-C|2-|R-D|24dj-rj(5.3.15)
式中： dj(j=1,2，…,n，dj∈D)为最佳码字的元素，wj为外信息。

若竞争码字无法寻找到，则使用可信度因子β来近似计算，即
wj=βdj-rj
3．  TPC的性能分析

TPC采用基于Chase2的次优译码算法，性能与码率、码型、信噪比、译码迭代次数有关。一般来说，迭代次数越大，性能越好，但译码时间越长。当迭代次数大于一定的值(大于6)时，性能改善不明显。下面以扩展Hamming码为分量码，迭代次数为6次，BPSK调制，AWGN下进行计算机仿真。



图5．3．5TPC性能图


从图5．3．5(a)中可以看出，(32,26)（32，26）码性能优势明显，在BER=10-5，与(8,4)（8，4）比较，编码增益多出近2dB； 与(16,11)(16,11)和(64,57)(64,57)码比较，多出约0．5dB。从趋势上看，(32,26)（32，26）码具有最为陡峭的“瀑布区”。图5．3．5(b)的三维码性能曲线中“瀑布区”较二维更为陡峭。

不同调制方式下性能比较也有差异，图5．3．6给出(32,26)(32,26)码在不同调制方式下的性能曲线。



图5．3．6(32,26)(32,26)码不同调制方式下的性能


在IEEE 802．16标准中采用的码型如表5．3．6所示。



表5．3．6IEEE 802．16标准中的TPC





TPC码率有效载荷大小

(39,32)(39,32)(下行链路)0．6731024bit

(53,46)(51,44)(下行链路)0．7493136bit

(30,24)(25,9)(上行链路)0．608456bit


目前，TPC技术相对较为成熟，一些芯片公司已有相应的芯片产品，这就进一步推动了其应用范围的扩展。在学术上，TPC技术的研究主要集中在其应用领域的革新。

5．3．4．3级联码

信道编码定理指出，随着码长n的增加，译码器错误概率按指数接近0。因此，性能较好的码码长一般较长。但是，随着码长的增加，在一个码组中要求纠错的数目相应增加，译码器的复杂性和计算量也相应增加以致难以实现。为了解决性能与设备复杂性的矛盾，1966年Forney提出了级联码的概念，把编制长码的过程分几级完成，通常分两级。

一种典型的方式如图5．3．7所示，假定在内信道上使用是码C1，称为内码，在外信道上使用的码C2，称为外码。所以这种码是(n1,n2,k1,k2)码，其中n1、k1和n2、k2分别是码C1和C2的长度和信息位数。而且，一般C2采用(n2,k2)的多进制码，而C1采用(n1,k1)的二元码。若内码和外码的最小距离分别为d1和d2，则它们级联后的最小距离至少为d1d2。这种单级级联码已广泛应用于通信和数据存储系统中。为获得较高的可靠性并减小译码复杂度，内码一般较短，使用软判决译码算法进行译码； 非二进制的外码一般较长，使用代数译码方法进行译码。编码时，先将k2k1个信息数字分成k2个k1重，这k2个k1重按C1码进行编码，将每个k1重转换成n1重。译码时，先对C1码译码，再对C2码译码。这种码如果遇上少量的随机错误，内码C1就可以纠正； 如果遇到较长的突发错误，内码则无能为力，则由纠密集型突发错误很强的外码纠正。另一种做法是，内码作检错码，外码作纠错码，使译码过程简化。若还要提高纠正突发错误能力，则可将交织技术用于级联码。



图5．3．7采用级联码的通信系统


将内码编码器、信道与内码译码器的组合称为超信道。将外码与内码编码器的组合称为超编码器，将外与内译码器的组合称为超译码器。可以看到，所得级联码码字的总长度N=n1n2bit； 其编码效率ηr=η1η2=k1k2/n1n2。虽然，码字的总长度为N，但由级联概念所提出的结构可以分别用两个长度为n1和n2的译码器来完成译码运算。故在相同的总差错率下这种方法比采用单级编码时所需的设备复杂程度要少得多。选用各种RS码作外码是最为适宜的，因为它们是极大最小距离码(d=n-k+1)，并易于实现。在二级编码方案中RS码是级联码中外码C2所常用的，而作为内码C1可以采用不同的线性分组码，如正交码、循环码等，当然也可以采用卷积码作为内码。为了进一步提高抗随机错误和突发错误的能力，还可以采用多级编码方案，同时交织码也可以结合到具体的多级编码方案中。多级编码方案的缺点是编码器相当复杂，同时增长了译码时延，在某些场合并不适合。

美国航空航天局（NASA）的跟踪和数据中继卫星系统(Tracking Data Relay Satellite System,TDRSS)中使用的差错控制编码方案采用级联卷积码编码系统。在该系统中，GF(28)上的(255，233,33)RS码被用作外码，由多项式g1(D)=1+D+D3+D4+D6和g2(D)=1+D3+D4+D5+D6生成的状态数为64、编码效率为1/2的卷积码被用作内码。卷积内码的自由距离dfree=10。系统的整体编码效率为0．437。该级联卷积编码系统性能如图5．3．8所示。从图5．3．8中可以看出，该级联卷积编码系统在信噪比2．53dB处，误码率达到10-6，可获得近8．5dB增益。



图5．3．8NASA的TDRSS中使用的差错控制编码方案的误码性能


同样，在微小卫星的链路中，采用国际空间数据系统咨询委员会(Consultative Committee on Space Data Systems，CCSDS)推荐的级联码(卷积码+RS码)，使用级联码是为了以少于单个编码操作所需的整体实现的复杂度，来获得较低的错误概率。






















5．4循环码的基本原理

循环码是线性分组码的一个重要子类，也是目前研究得最成熟的一类码。它有许多特殊的代数结构，这些性质有助于按照所要求的纠错能力系统地构造这类码，并且简化译码方法。循环码还有易于实现的特点，很容易用带反馈的移位寄存器实现，且性能较好，不但可用于纠正独立的随机错误，而且可以用于纠正突发错误。因此，目前在实际差错控制系统中所用的线性分组码大部分是循环码。

5．4．1基本概念
5．4．1．1循环码的定义

什么是循环码，它究竟与一般的(n,k)线性分组码有何不同？我们先看一个例子。

例5．4．1(7,4)Hamming码C的生成矩阵为
G=1000101010011100101100001011
由此可得到所有的24=16个码字是(1000101)、(0001011)、(0010110)、(0101100)、(1011000)、(0110001)、(1100010)、(0100111)、(1001110)、(0011101)、(0111010)、(1110100)、(1101001)、(1010011)、(1111111)、(0000000)。

由这些码字看出，如果Ci是C的码字，则它向左(或右)循环移位一次所得到的，也是C的码字。具有这种循环移位特性的线性分组码称为循环码。

把C码的任一码字中的7个码元排成一个圆环，如图5．4．1(a)~(d)所示。可以看到，从圆环的任一码元开始，按顺时针方向移动，得到的7重数组都是该码的一个码字，这就是循环码名字的由来。



图5．4．1(7,4)循环码的码字循环移位示意图


(n,k)线性分组码是n维线性空间Vn中的一个k维子空间Vn,k。在循环码中，该子空间中的元素(n重)具有循环移位特性，称为循环子空间。

定义5．4．1在任一个GF(q)(q为素数或素数幂)上的n维线性空间Vn中，一个n重子空间Vn,k∈Vn，若对任何一个Ci=(cn-1，cn-2，…，c0)∈Vn,k，恒有C′i=(cn-2 …c0cn-1)∈Vn,k，则称Vn,k是循环子空间或循环码。

可见GF(q)上的循环码是具有循环移位特性的线性分组码。

5．4．1．2循环码的多项式描述

为了用代数理论研究循环码，可将码组用多项式来表示，称为码多项式。设许用码组
C=(cn-1 cn-2…c1 c0)
对应的码多项式可表示为
C(x)=cn-1 xn-1+cn-2 xn-2+…+c1 x+c0（5.4.1）
其中ci∈GF(2)，则它们之间建立了一一对应关系，上述多项式也称为码字多项式，其中多项式的系数就是码字各分量的值，x为一个任意实变量，其幂次i代表该分量所在位置。

由循环码特性可知，若C=(cn-1cn-2…c1 c0)是循环码的一个码字，则C(1)=(cn-2 … c0 cn-1)也是该循环码的一个码字，它的码多项式为
C(1)(x)=cn-2 xn-1+…+c0 x+cn-1
与式（5.4.1）比较可知
C(1)(x)≡x C(x) mod(xn+1)
同样，xC(1)(x)对应的码字C(2)相当于将码字C(1)左移一位，即码字C左移两位，由此可得
C(2)(x)≡cn-3 xn-1+…+c0 x2+cn-1 x+cn-2
≡x C(1)(x) mod(xn+1)
≡x2 C(x) mod(xn+1)
以此类推，不难得出循环左移i位时，有
C(i)(x)≡xi C(x) mod(xn+1)(i=0，1，…，n-1)
可见，xiC(x)在模xn+1下的余式对应着将码字C左移i位的码字C(i)。

定理5．4．1若C(x)是n长循环码中的一个码多项式，则xiC(x)按模xn+1运算的余式必为循环码中另一码多项式。

为简便起见，上述中的mod(xn+1)在码多项式的表示中不一定写出，而通常用类似式（5.4.1）表示。

5．4．1．3生成多项式

观察循环码的所有码多项式不难发现，除全0码外，它存在着一个特殊的多项式，这个多项式在循环码的构成中具有十分重要的意义，它就是该码的最低次多项式。以下几个定理是关于它的特性的。

定理5．4．2一个二进制中(n,k)循环码中有唯一的非零最低次多项式g(x)，且其常数项为1。

证明： 设g(x)是码中次数最低的非零码多项式，具有如下形式： 
g(x)=xr+gr-1 xr-1+…+g1 x+g0
若g(x)不唯一，则必存在另一个次数最低的码多项式，例如g′(x)=xr+g′r-1 xr-1+…+g′1 x+g′0，因为循环码是线性分组码，所以g(x)+g′(x)=(gr-1+g′r-1)xr-1+…+(g1+g′1)x+(g0+g′0)是一个次数小于r的码多项式。若g(x)+g′(x)≠0，则g(x)+g′(x)是一个次数小于最低次数r的非零码多项式，这显然与r是最低次数相矛盾。因此，必有g(x)+g′(x)=0，即g(x)=g′(x)，也即g(x)是唯一的。

再证g0=1。

若g0=0，则有g(x)=xr+gr-1 xr-1+…+g2 x2+g1 x=x(xr-1+gr-1 xr-2+…+g2 x+g1)，因为g(x)是码多项式，则将其对应的码字右移一位后，得到一非零码多项式
xr-1+gr-1 xr-2+…+g2x+g1
也是循环码的码多项式，而它的次数小于r，这与g(x)是次数最低的非零码多项式的假设相矛盾，故g0=1。［证毕］ 

上例(7,4)循环码，只有一个最低次多项式x3+x+1，而码中所有码多项式都是它的倍式，即由x3+x+1可生成所有(7,4)循环码，把它称为(7,4)循环码的生成多项式。

定义5．4．2若一个码的所有码多项式都是多项式g(x)的倍式，则称g(x)生成该码，且称g(x)为该码的生成多项式，所对应的码字称为生成子或生成子序列。

定理5．4．3GF(2)上的(n,k)循环码中，存在有唯一的n-k次首1多项式
g(x)=xn-k+gn-k-1 xn-k-1+…+g1x+g0
使得每一码多项式C(x)都是g(x)的倍式，且每一小于或等于n-1次的g(x)的倍式一定是码多项式。

下面定理给出了循环码的生成多项式g(x)应满足的条件。

定理5．4．4设g(x)是(n,k)循环码［C(x)］中的一个次数最低的多项式(g(x)≠0)，则该循环码由g(x)生成，并且g(x) |(xn+1)。

综上所述，可得出生成多项式g(x)的性质： g(x)是循环码的码多项式中的一个唯一的最低次多项式，它具有首1末1的形式。该码集中任一码多项式都是它的倍式，它本身必是多项式xn+1的一个(n-k)次的因式，由它可生成2k个码字的循环码。

从以上讨论中，可得到以下重要结论。

（1） 在二元域GF(2)上找一个(n,k)循环码，就是找一个能除尽xn+1的n-k次首1多项式g(x)，为了寻找生成多项式，必须对xn+1进行因式分解，这可用计算机来完成。

对于某些n值xn+1只有很少的几个因式，因而码长为n的循环码不多。仅对于很少的几个n值才有较多的因式，在一些参考书上已将因式分解列成表格，有兴趣的读者可查阅有关书籍。

（2） 若C(x)是(n,k)码的一个码多项式，则g(x)一定除尽C(x)。若g(x)|C(x)，则次数小于或等于n-1的C(x)必是码的码多项式。也就是说若C(x)是码多项式，则
C(x)≡0modg(x)
上述所有结论虽然都在GF(2)上讨论的，但可以推广到GF(q)上。

例5．4．2GF(2)上多项式x7+1=(x+1)(x3+x+1)(x3+x2+1)，构造一个(7,3)循环码。

要构造一个(7,3)循环码，就是在x7+1中找一个n-k=4次的因式g(x)，作为码的生成多项式，由它的一切倍式就组成了(7,3)循环码。若选g(x)=(x3+x+1)(x+1)=x4+x3+x2+1，则(7,3)循环码的码多项式与码字列于表5．4．1中。由该表可知，该码的8个码字可由g(x)、xg(x)、x2g(x)的线性组合产生出来，而且这三个码多项式是线性无关的，它们构成一组基底。所以生成的循环子空间(循环码)是一个三维子空间V7，3，对应一个(7,3)循环码。



表5．4．1g(x)=x4+x3+x2+1生成的(7,3)循环码




码 多 项 式码字


g(x)=x4+x3+x2+1(0011101)

xg(x)=x5+x4+x3+x(0111010)

x2g(x)=x6+x5+x4+x2(1110100)

(1+x2)g(x)=x6+x5+x3+1(1101001)

(1+x+x2)g(x)=x6+x4+x+1(1010011)

(1+x)g(x)=x5+x2+x+1(0100111)

(x+x2)g(x)=x6+x3+x2+x(1001110)

0g(x)=0(0000000)


在x7+1=(x+1)(x3+x+1)(x3+x2+1)中，若选g(x)=(x+1)(x3+x2+1)=x4+x2+x+1，则生成另一个循环码。同理，在x7+1的因式中，若选g(x)=x3+x+1或g(x)=x3+x2+1，则可构造出两个不同的(7,4)循环码，若选g(x)=(x3+x+1)(x3+x2+1)，则可构造出一个(7,1)循环码，它就是重复码。由此可知，只要知道了xn+1的因式分解式，用它的各个因式的乘积，便能得到很多个不同的循环码。

循环码可由其生成多项式确定，一般用八进制数字表示g(x)。例如，八进制数13的二进制表示为001011，代表g(x)=x3+x+1。表5．4．2列出了几种不同长度下循环Hamming码的生成多项式。



表5．4．2循环Hamming码的生成多项式




mn=2m-1k=2m-m-1g(x)


374x3+x+1(13)

41511x4+x+1(23)

53126x5+x2+1(45)

66357x6+x+1(103)

7127120x7+x3+1(211)

8255247x8+x4+x3+x2+1(435)

9511502x9+x4+1(1021)

1010231013x10+x3+1(2011)

1120472036x11+x2+1(4005)

1240954083x12+x6+x4+x+1(10123)


5．4．1．4循环码的生成矩阵和一致校验矩阵

循环码的生成矩阵可以很容易地由生成多项式得到。由于g(x)为n-k阶多项式，以与此相对应的码字作为生成矩阵中的一行，则g(x)，x2g(x)，…，xk-1g(x)等多项式必定是线性无关的。把这k个多项式相对应的码字作为各行构成的矩阵即为生成矩阵，由各行的线性组合可以得到2k个循环码字。所以循环码的生成矩阵G可用以下方法得到。设
g(x)=gn-k xn-k+gn-k-1 xn-k-1+…+g1 x+g0
xg(x)=gn-k xn-k+1+gn-k-1 xn-k+…+g1x2+g0 x

xk-1 g(x)=gn-k xn-1+gn-k-1 xn-2+…+g1 xk+g0 xk-1
则码的生成矩阵以多项式形式表示为
G(x)=xk-1g(x)xk-2g(x)g(x)（5.4.2）
取其系数即得相应的生成矩阵为
G=gn-kgn-k-1…g1g000…0k-10gn-kgn-k-1…g1g00…0


0…0k-1gn-kgn-k-1…g1g0n-k+1
由式（5.3.3）可知，输入信息组为(mk-1，…，m0)时，相应的码多项式为
C(x)=(mk-l，mk-2，…，m0)G(x)
=(mk-l xk-1+mk-2 xk-2+…+m0)g(x)
这表明，所有码多项式一定是g(x)的倍式。

由式（5.4.2）所示生成矩阵得到的循环码并非系统码。在系统码中码的最左k位是信息码元，随后是n-k位校验码元。这相当于码多项式C(x)的第n-1次至n-k次的系数是信息位。其余的是校验位
C(x)=mk-1 xn-1+…+m0 xn-k+rn-k-1 xn-k-1+…+r0
=m(x)xn-k+r(x)≡0，mod g(x)（5.4.3）
式中： m(x)=mk-1xk-1+…+m1x+m0是信息多项式； r(x)=rn-k-1 xn-k-1+…+r1x+r0是校验元多项式，它的系数(rn-k-1，…，r1，r0)就是信息组(mk-1，…，m1，m0)的校验元。由式（5.4.3）可知
-r(x)=-C(x)+m(x)xn-k=m(x)xn-k，mod g(x)（5.4.4）
而-r(x)是r(x)中的每一个系数取加法逆元，在GF(2)中加法和减法等效，即
- ri=ri，-r(x)=r(x)
由上式可知，构造系统循环码时，只需将信息码多项式升n-k阶(乘以xn-k)，然后以g(x)为模，所得余式r(x)的系数即为校验元。因此，系统循环码的编码过程就变成用除法求余的问题。

系统码的生成矩阵必为典型形式G=［IkP］，与单位矩阵Ik每行对应的信息多项式为
mi(x)=mixk-i=xk-i（i=1，2，…，k）
由式（5.4.4）可得相应的校验多项式为
ri(x) ≡xk-i xn-k ≡xn-i mod g(x)（i=1，2，…，k）（5.4.5）
由此得到生成矩阵中每行的码多项式为
Ci(x)=xn-i+ri(x)（i=1，2，…，k）
因此，系统循环码生成矩阵多项式的一般表示为
G(x)=C1(x)C2(x)Ck(x)=xn-1+r1(x)xn-2+r2(x)xn-k+rk(x)(5.4.6)

例5．4．3已知(7,4)系统码的生成多项式为g(x)=x3+x2+1，求生成矩阵。

解： 由式（5.4.5）可得
r1(x)≡x6 ≡x2+xmod g(x)
r2(x)≡x5 ≡x+1mod g(x)
r3(x)≡x4 ≡x2+x+1mod g(x)
r4(x)≡x3 ≡x2+1mod g(x)
因此，生成矩阵多项式表示为
G(x)=x6+x2+xx5+x+1x4+x2+x+1x3+x2+1
由多项式系数得到的生成矩阵为
G=1000110010001100101110001101=［I4P］
由于g(x)能除尽xn+1，因此有
xn+1=g(x)h(x)
=(gn-k xn-k+…+g1x+g0)(hkxk+…+h1x+h0)
由此可推出循环码的一致校验矩阵，即
H=h0h1…hk0h0h1…hk0n-k-1h0h1…hkk+1
它完全由h(x)的系数决定，故称h(x)是循环码的校验多项式。

可以验证，有GHT=0。式中： 0是一个k×(n-k)零矩阵。

同理，以上H矩阵是非标准型的，若要得到标准型H矩阵，可利用H与G的关系。也可由式（5.4.6）得出
H=［PTIn-k］=［rT1rT2…rTkIn-k］
另外，可定义h(x)的互反多项式为
h*(x)=xk h(x-1)=h0 xk+h1 xk-1+…+hk
可见，H矩阵可由下述的多项式矩阵的系数构成，即由h(x)的互反多项式h*(x)循环移位得到的r组互不相关的多项式系数矢量构成。

仿照线性分组码，称H为循环码的一致校验矩阵： 
H(x)=xr-1h*(x)x2h*(x)x1h*(x)h*(x)
定义一个矩阵是生成矩阵还是校验矩阵，主要是看它们在编码过程中所起的作用。由于H矩阵与G矩阵彼此正交，所以两者的作用可以互换。若g(x)生成一(n,k)循环码，那么h*(x)可生成(n,n-k)循环码，h(x)也可作为生成多项式得到一(n,n-k)循环码。

定义5．4．3以g(x)作为生成多项式生成的(n,k)循环码和以h*(x)作为生成多项式生成的(n,n-k)循环码互为对偶码，而以g(x)作为生成多项式生成的(n,k)循环码和以h(x)作为生成多项生成的(n,n-k)循环码互为等效对偶码。

由G和H的正交性可以证明对偶码是互为正交的。而等效对偶码相互不满足正交性。













5．4．2循环码的编码及其实现

一旦确定了循环码的生成多项式g(x)，就完全确定了码。循环码的每个码多项式C(x)=g(x)m(x)都是g(x)的倍式。对系统码来说，就是已知信息多项式m(x)求m(x)xn-k被g(x)除以后的余式r(x)。所以，循环码的编码器就是m(x)乘g(x)的乘法器，或者是g(x)除法电路。另外，循环码的译码实际上也是用g(x)去除接收多项式R(x)，检测余式结果，因此，多项式乘法及除法是编译码的基本运算。本节首先介绍作为编译码电路核心的多项式除法电路，这里主要针对二进制编译码； 然后讨论编码电路，对于多进制循环码，即GF(q)上循环码的电路可以此类推。

5．4．2．1多项式除法运算电路

设GF(2)上两个多项式为
g(x)=gr xr+gr-1 xr-1+…+g1 x+g0，gr=1
A(x)=ak xk+ak-1xk-1+…+a1x+a0，k≥r
用g(x)去除任意多项式A(x)的电路即为g(x)除法电路，如图5．4．2所示。



图5．4．2g(x)除法电路


可以证明，用r次多项式g(x)去除任意k次多项式A(x)，经k+1拍各移位寄存器的存数即为余式，电路输出商比输入序列固定延迟r拍。

例5．4．4设被除式A(x)与除式B(x)都是GF(2)上的多项式，且
A(x)=x4+x3+1，B(x)=x3+x+1
完成除以B(x)=x3+x+1的电路示于图5．4．3中。GF(2)上多项式的系数仅取0和1，系数为1的逆元仍是1，相加和相减相同，所以当bi≠0时，b-1i与-bi均为一直线。



图5．4．3除B(x)=x3+x+1的电路


完成上述两个多项式相除的长除法算式如下： 
x4+x3+1=(x+1)(x3+x+1)+x2
这里商为x+1，余式为x2。表5．4．3给出了图5．4．3电路除x4+x3+1的运算过程，r+1=4次移位后得到商x项的系数，k+1=5次移位后，完成了整个除法运算，在移位寄存器中保存的数(001)，代表余式(x0 x1 x2)的系数。


表5．4．3B(x)除x4+x3+1的运算过程




节拍输入
移位寄存器内容
D0(x0)D1(x1)D2(x2)输出
000000
11（x4）1000
续表




节拍输入
移位寄存器内容
D0(x0)D1(x1)D2(x2)输出
21(x3)1100
30(x2)0110
40(x)1111(x)
51(x0)0011(x0)
余式商式



5．4．2．2循环码编码器

1． n-k级编码器


利用生成多项式g(x)实现编码是编码电路的常用方法。若已知信息位为k，纠错能力为t，则可以按循环码的性质设计一套循环码。

首先可以根据式
2r-1≥∑ti=1Cin
求出所需要的n，r=n-k。求出n以后，再从xn+1的因式中找出g(x)生成多项式。该多项式最高次数为n-k,记为0g(x)=n-k，由g(x)生成的码C就是满足要求的循环码。

现在的问题是给定g(x)以后，在电路上如何实现编码？下面研究这个问题。

n-k级编码器有两种： 一是g(x)的乘法电路； 二是g(x)的除法电路。前者主要利用方程式C(x)=m(x)g(x)进行编码，但这样编出的码为非系统码； 后者是系统码编码器中常用的电路。这里只介绍系统码的编码电路。

设从信源输入编码器的k位信息组多项式
m(x)=mk-1 xk-1+…+m1 x+m0
若要编出系统码的码字，则由式（5.4.3）和式（5.4.4）可知
C(x)=m(x)xn-k+r(x)
r(x)≡m(x)xn-kmod g(x)
系统码的编码器就是信息组m(x)乘xn-k，然后用g(x)除，求余式r(x)的电路。

下面以二进制(7,4)Hamming码为例说明。设码的生成多项式g(x)=x3+x+1，其系统码编码器示于图5．4．4。



图5．4．4（7，4）Hamming码三级除法编码器


编码过程如下。

（1） 三级移位寄存器初态全为0，门1断开，门2接通。信息组以高位先入的次序送入电路，一方面经或门输出，另一方面送入g(x)除法电路右端，这相应于完成xn-k m(x)的除法运算。

（2） 4次移位后，信息组全部通过或门输出，它就是系统码码字的前4个信息元，与此同时它也全部进入g(x)电路，完成除法。此时在移位寄存器中的存数就是余式r(x)的系数，也就是码字的校验元(c2，c1，c0)。

（3） 门1接通，门2断开，再经3次移位后，移存器中的校验元（c2，c1，c0）跟在信息组后面，形成一个码字(c6=m3，c5=m2，c4=m1，c3=m0，c2，c1，c0)从编码器输出。

（4） 门1断开，门2接通，送入第二组信息组，重复上述过程。

表5．4．4列出该编码器的工作过程。输入信息组是(1001)，7次移位后输出端得到了已编好的码字(1001110)。



表5．4．4(7,4)Hamming码编码的工作过程





节拍信息组
输入
移位寄存器内容

D0(x0)D1(x1)D2(x2)
输出


0000

111101

200110

301110


410111

50011

60001

70000


2．  k级编码器

编码问题就是已知信息元cn-1，cn-2，…，cn-k，如何唯一求出校验位cn-k-1，…，c0，上述提到的编码方式是利用生成多项式来确定校验位，那么另一种编码方法则是用校验多项式来确定校验位。

k级编码器是根据校验多项式
h(x)=hkxk+…+h1x+h0
构造的。其电路如图5．4．5所示。

如果移位寄存器初始状态从右至左是cn-1~cn-k的k个信息元，经过n拍就能输出cn-1~c0全部码元完成编码。此电路需要k级移位寄存器。

一般来说，当k>r时，使用第一种n-k级编码器较好(g(x)编码)； 当k<r时，使用第二种k级编码器较好(h(x)编码)。按上述条件设计的编码器可使用较少的移位寄存器。



图5．4．5循环码的k级编码


5．4．3循环码译码及其实现















当一个码矢量通过噪声信道传送时，会遇到噪声干扰而产生错码，即在接收端所收到的矢量R可能与发送端码字不同。已经分析过R与C有如下关系： 
R=C+E(5.4.7)
式中： E为错型矢量。

当然，式（5.4.7）也可以写成多项式的关系： 
R(x)=C(x)+E(x)(5.4.8)
式中
R(x)=rn-1 xn-1+rn-2 xn-2+…+r1 x+r0
C(x)=cn-1 xn-1+cn-2 xn-2+…+c1 x+c0
E(x)=en-1 xn-1+en-2 xn-2+…+e1 x+e0

从式（5.4.7）、式（5.4.8）中可以看到接收矢量含有码字矢量的信息和错误图样的信息。译码就是研究各种译码方法，选择和设计适当的译码电路，用于对R进行检错或纠错。

对于一组确定的循环码来说，从码字本身的代数结构来讲它的性质是确定的。即它的检错纠错能力是确定的。实际应用中由于采用不同的译码方法，实际达到的检、纠错能力并不等于码字所具有的能力。因此，衡量一种译码方法的优劣不单考虑检、纠错能力(当然这是最重要的指标)，还要考虑它的复杂程度和计算速度。下面就循环码译码的几种主要方法进行研究。

5．4．3．1伴随式的计算

设发送的码字C=(cn-1，cn-2，…，cl，c0)，其码字多项式C(x)=(cn-1xn-1+…+c1 x+c0)(以后不再严格区分码字与码多项式)，信道产生的错误图样E=(en-1，en-2，…，e1，e0)，译码器收到的n重
R=C+E
=(cn-l+en-1，cn-2+en-2，…，c1+el，c0+e0)
=(rn-1，rn-2，…，rl，r0)，ri=ci+ei
或
R(x)=C(x)+E(x)
=(rn-1xn-1+…+r1x+r0)，ri=ci+ei
相应的伴随式为
S=RHT=(C+E)HT=EHT

由此可知，伴随式S仅与错误图样有关，而与发送的码字无关，由它可计算出错误图样E。

设(n,k)循环码的生成多项式为g(x)，且xn+1=g(x)h(x)，0g(x)=n-k。该码的一致校验矩阵为
H=［x～n-1Tx～n-2T…x～Tl～T］ mod g(x)
式中： x～i≡xi mod g(x)（i=0,1,…,n-1）。

所以
S=RHT=(rn-1，rn-2，…，r1，r0)x～n-1x～n-2x～1x～0
=(cn-1，…，c1，c0) x～n-1x～n-2x～1x～0+(en-1，…，e1，e0)x～n-1x～n-2x～1x～0
由此式可知相应的多项式表示为
S(x)≡C(x)+E(x)≡R(x) ≡E(x) mod g(x)（5.4.9）
根据欧几里得除法，有
R(x)=Rg(x)+g(x)q(x)
E(x)=Eg(x)+g(x)q1(x)
因此式（5.4.9）又可表示为
S(x)=Rg(x)=Eg(x)(5.4.10)
式中： Rg(x)、Eg(x)分别是R(x)、E(x)被g(x)除后所得的余式。两式表明循环码的伴随式计算电路就是一个g(x)除法电路，伴随式S(x)就是g(x)除R(x)后所得的余式。如果接收的矢量R(x)没有错误，E(x)=0，则S(x)=0； 否则，S(x)≠0(在码的检错能力以内)。因此，循环码的检错电路非常简单，就是一个g(x)除法电路。收到R(x)后送入g(x)除法电路运算，若最后得到的余式为0，则说明E(x)=0，接收到的R(x)就是一个码字； 若不为0，则说明接收到的R(x)不是码字。

由式（5.4.9）或式（5.4.10）看出，若0E(x)<0g(x)=n-k，或E(i)(x)=xiE(x)，0E1(x)<0g(x)，则S(x)≠0(mod g(x))。这说明(n,k)循环码至多能检测长度等于n-k的突发错误，以及检测使S(x)≡E(x)≠0(mod g(x))的所有错误图样E(x)。

用g(x)除法电路计算伴随式的电路(伴随式计算电路)有如下几个很重要的特点。

定理5．4．5若S(x)是R(x)的伴随式，则R(x)的循环移位x R(x)(在模xn+1运算下)的伴随式S1(x)，是S(x)在伴随式计算电路中无输入时(自发运算)右移一位的结果，即
S1(x)≡xS(x)mod g(x)
证明： 由伴随式定义可知，xR(x)的伴随式为
S1(x)≡xR(x)mod g(x)
=x［Rg(x)+g(x)q(x)］mod g(x)
=xRg(x)mod g(x)
由式（5.4.10）可知
xS(x)=［xRg(x)+xq(x)g(x)］mod g(x)
两式相减可得
xS(x)-S1(x)=xq(x)g(x)≡0 mod g(x)
因此
S1(x) ≡xS(x) mod g(x)
5．4．3．2循环码的通用译码算法

循环码属于线性分组码，其基本的译码方法也是伴随式译码，只不过由于其具有循环移位特性，可以多项式进行表示和计算，故而循环码的伴随式译码是基于多项式计算，具体过程如下。

(1) 计算接收多项式R(x)对应的伴随式S(x)。

(2) 根据伴随式S(x)查表寻找对应的错误图样多项式(陪集首项)。

(3) 把接收多项式和错误图样多项式相加得到完成纠错的码字多项式。

循环码的通用译码器如图5．4．6所示。



图5．4．6循环码的通用译码器


译码之前首先把寄存器清零，接着接收多项式R(x)从高位到低位依次输入到“n比特缓冲寄存器”，把接收矢量保存起来； 同时接收多项式R(x)输入到伴随式计算电路，这是一个除法电路。当 R(x)全部进入伴随式计算电路后，在移位寄存器中存放的就是相应的伴随式。用r=n-k(bit)的伴随式作为地址去查找n(bit)的错误图样，把错误图样放在n比特错误形式寄存器中； 然后n比特缓冲寄存器中存放的接收矢量与n(bit)错误图样同步输出并相加，达到纠错的目的。

伴随式计算电路和缓冲寄存电路都比较容易实现，困难的是从伴随式去查找错误图样。对于一个(n,k)循环码来说伴随式长度为(n-k)，地址数目为2n-k，当n和k很大时，无法实现这样查表，所以要利用循环码的代数特征来简化查表复杂性。

5．4．3．3梅吉特译码器

定理5．4．6xjR(x)的伴随式Sj(x)≡xjS(x)mod g(x)，（j=0，1，…，n-1）。而任意多项式a(x)乘R(x)所对应的伴随式
Sa(x) ≡a(x)S(x)mod g(x)
伴随式计算电路的这些性质在循环码的译码运算中非常有用。若C(x)是循环码C的一个码字，则xC(x)∈C。因此，若S(x) ≡E(x)mod g(x)是R(x)=C(x)+E(x)的伴随式，则xS(x) ≡xE(x)mod g(x)就是xR(x)=xC(x)+x E(x)的伴随式。也就是说，若E(x)是一个可纠正的错误图样(陪集首)，则E(x)的循环移位xE(x)也是一个可纠正的错误图样。一般来说xjE(x)(1≤j≤n-1)也是可纠正的错误图样。可以根据这种循环关系划分错误图样，把任一特定的错误图样及其所有循环移位作为一类。例如，可将错误图样100…0，0100…0，0010…0，00…01作为一类，并将第一位开头为非零的错误图样100…0作为此类错误图样的代表。这时，对于二进制码，若码要纠正小于或等于t个错误，则错误图样代表共有
N1=∑tj=1Cj-1n-1(个)(5.4.11)
译码时，只要知道这些代表错误图样的伴随式，该类中其他错误图样的伴随式都可由此代表图样伴随式在伴随式计算电路中得到。这样，就使得循环码译码器的错误图样识别电路大为简化，由原来识别N2个图样减少到N1个。其中
N2=∑tj=1Cjn (个)(5.4.12)
例如，n=63，t=4，由式（5.4.11）和式（5.4.12）计算译码器所需识别的错误图样个数如表5．4．5所示。



表5．4．5N1，N2比较




t1234


N1163195439774

N263201641727637382


一般来说，纠错码译码设备的复杂性主要取决于伴随式找出错误图样的识别电路或组合逻辑电路的复杂性。由表5．4．5可知，虽然循环码识别错误图样的个数比一般非循环码大为减少，但随着n、t的加大，需要识别的错误代表个数N1仍增加很快，以致难以实现。因此，利用组合逻辑电路识别错误图样代表的方法仅适合于n、t较小的情况。若n、t都较大，则必须利用循环码的其他特点寻找更为简单和巧妙的译码方法，这就是纠错码理论研究和实际应用中引人注目的问题之一。

例5．4．5二进制(7,4)循环Hamming码，它的g(x)=x3+x+1，相应的校验矩阵为
H=［x～6Tx～5Tx～4Tx～3Tx～2Tx～1Tx～0T］mod g(x)=111010001110101101001
可见，该码的d0=3，可纠t=1位错码。由式（5.4.11）知，构造此译码器的错误图样识别电路时，只要识别一个图样E6=(1000000)就够了，该图样的伴随式就是H的第一列(101)。而E6错误图样的识别电路就是一个检测伴随式是否为(101)的电路。由此可得如图5．4．7所示的译码电路。图中的伴随式计算电路就是一个g(x)=x3+x+1的除法电路，而有3个输入端的与门和反相器，组成了识别(101)的伴随式识别器。译码器的译码过程如表5．4．6。



图5．4．7(7,4)循环Hamming码译码器




表5．4．6图5．4．7译码器的译码过程




节拍输入R(x)
伴随式计算电路

D0D1D2
与门输出缓存输出译码器输出


0000

11(x6)100

20(x5)010

30(x4)001

40(x3)110

50(x2)011

61(x)011

71(x0)011

811111

910100

10000101

1100000

1200000

1300011

1400011


具体过程如下。

（1） 开始译码时“门”接通，移位寄存器内容全为0。收到的R(x)=r6 x6+…+r0，以高次项系数(r6)至低次项系数的次序，一方面送入7级缓存器，另一方面送入g(x)除法电路计算伴随式。7次移位后，R(x)的系数全部存入缓存器，g(x)电路也得到了伴随式S0(x)，此时“门”断开，禁止输入。 

（2） 若S(x)≡1+x2≡x6(mod g(x))，说明E(x)=x6，r6位有错，伴随式计算(g(x)除法器)电路中的D0、D1、D2存储的值是(101)，这就是S0(x)=l+x2的系数。D1的0经反相后成了1，与门的3个输入端全为1，呈打开状态。这时译码器继续移位，r6从缓存器输出，与门也输出一个信号“1”与r6相加，使r6由原来的1变成0，或由0变成1，纠正了r6的错误： r6+1=c6+e6+1=c6+1+1=c6，得到原来发送的码元。此时与门的纠错信号“1”也反馈到伴随式计算电路输入端(图5．4．7虚线所示)，对伴随式进行修正，以消去该错误对伴随式的影响。

由于
R(x)=rn-lxn-1+…+r1 x+r0
相应的伴随式是S0(x)。纠错后R(x)成为
R′1(x)=(rn-1+1)xn-1+…+r1x+r0
与R′1(x)相应的伴随式
S′1(x)≡S0(x)+xn-1mod g(x)
因为纠错是在第n+1次移位进行的，所以R′1(x)成为
R1(x)=xR′1(x)≡rn-2xn-1+…+r0 x+rn-1+l mod(xn-1)
相应的伴随式
S1(x) ≡xS′1(x)=xS0(x)+xn≡xS0(x)+1 mod g(x)
由于S1(x)是xR′1(x)的伴随式，而xS0(x)是xR(x)的伴随式，也就是xE(x)的伴随式，因此为了得到真正的xR(x)的伴随式，就必须从S1(x)中消去“1”，也就是在伴随式计算电路输入端加1。

例如，第7次移位后，若S0=1+x2，说明r6有错，第8次移位时对r6进行纠错，纠错信号“1”输入到g(x)电路输入端，结果使g(x)移位寄存器中的内容成为(000)，消除了e6的影响。

（3） 若E(x)=x5，则S0(x)≡x5≡x2+x+1 mod g(x)，此时与门不打开，说明r6正确。这时伴随式计算电路和缓存器各移位一次，r6输出，r5移到缓存器最右一级，伴随式计算电路得到的伴随式为
S1(x) ≡xS0(x)≡xE(x)≡x2+l mod g(x)
因此再移动一次，与门输出的纠正信号“1”正好与缓存器输出的r5=c5+1相加，得到了c5，从而完成了纠错。若r5不错，则重复上述过程一直到译完一个码字为止。

已知R(x)=x6+x+1，E(x)=x4。由表5.4.6可知，到第10个节拍，与门输出一个“1”纠正r4，最后译码器输出码字(1010011)。

从上述译码过程可知，译一组码共需14(2n)个节拍，仅当第一组的R(x)移出7级缓存器后才能接收第二组的R(x)。为了使译码连续，必须再加一个伴随式计算电路，如图5．4．8所示。开始工作时，所有移存器的存数全为0，门l接通、门2断开。当k=4次移位后，4级缓存器接收了前面的4个信息位(对系统码而言)，此时门1断开，并使4级缓存器停止移位。再移动n-k=3次后，g(x)除法电路得到了伴随式S0(x)，此时门2接通，把上边g(x)除法电路得到的伴随式送到下面的伴随式计算电路中，随即门2断开，且上边g(x)除法电路立即清除为0。门1再次接通，4级缓存器一边送出第一组的信息，一边接收第二组R(x)的前k位信息组。与此同时，上边伴随式计算电路计算第二组R(x)的伴随式，而下边伴随式计算电路通过自发运算对第一组R(x)中的信息元进行纠错。



图5．4．8(7,4)码完整译码器


显然，上述译码电路仅适应于系统码。若为非系统码，k级缓存器必须变成n级，且需要从已纠错过的C^(x)中取出k个信息元m^(x)。对非系统码而言,由C(x)=m(x)g(x)可知,m^(x)=C^(x)g-1(x)。说明译码器输出C^(x)后，把C^(x)再通过g(x)除法电路，所得的商就是最终所需的估值信息组m^(x)。

由上述讨论可得出系统循环码的一般译码器，如图5．4．9所示，这种译码器也称梅吉特(Meggitt)译码器，它的复杂性由组合逻辑电路决定。



图5．4．9循环码的梅吉特译码器


下面，我们来分析缩短循环码的编译码问题。先以例5.4.5说明缩短循环码如何产生。

例5．4．6试构造一个(6,3)循环码。

需要构造一个(6,3)循环码，即n=6,k=3,r=3。不难发现，找不到一个三次多项式g(x)满足g(x)|(x6+1)。但g(x)=x3+x+1时，g(x)|(x7+1)，故可先构成(7,4)码，而后去掉一位信息元，共有24-1=8个码字，便得(6,3)码。具体做法是将(7,4)循环码中第一位为零的码字取出，去掉第一个零，即组成了(6,3)缩短码的全部码字： 
00000000000000001011010110011101100111101100110001111010
,,,,,,,,1000101，1001110，1010011,1011000,1100010,1101001,1110100,1111111，

注意，缩短循环码已不再具有循环移位的特点，不过它的每个码字多项式仍是原(n,k)码生成多项式g(x)的倍式。g(x)|(xn+1),但g(x)不能整除xn-i+1。

(n-i,k-i)缩短循环码的生成矩阵可以通过将原(n,k)码生成矩阵去掉前i行i列得到，而其一致校验矩阵则通过将原(n,k)码一致校验矩阵去掉前i列得到。例如，(6,3)码的生成矩阵和一致校验矩阵分别为
G7,4=1000101010011100101100001011去掉第一行、第一列G6,3=100111010110001011
H7,4=111010001110101101001去掉第一列H6,3=110100111010101001
尽管缩短循环码的码字已不再具有循环特性，但这并不影响其编、译码的简单实现，它仅需对原(n,k)循环码的编、译码稍作修正。

缩短循环码的编码器仍与原来循环码的编码器一样(因为去掉前i个为零的信息元，并不影响监督位的计算)，只是操作的总节拍少了i拍。译码时，只要在每个接收码组前加i个零，原循环码的译码器就可用来译缩短循环码。但为了节省资源也可不加i个零，而对伴随式寄存器的反馈连接进行修正。由于缩短了i位，相当于信息位也提前了i位，故需自动乘以xi，并可用Rg(x)［xi］电路实现。伴随式计算电路的输入应改为按下式的计算结果方式接入： 
Rg(x)［xi］=f(x)=xk+…+xm+xl
式中： 0≤k<…<m<l≤r-1,r为g(x)的次数，即接收码组R应从sk,…,sm,sl各级输入端同时接入。这时，伴随式计算电路的状态将为
S′i(x)=Rg(x)［f(x)k(x)］
而
f(x)=xi+g(x)q(x)
f(x)R(x)=xiR(x)+g(x)q(x)k(x)
故

S′i(x)=Rg(x)［xiR(x)］=Rg(x)［xiS(x)］=xiS(x)=Si(x)

这说明缩短i位的(n-i,k-i)码，除法运算可以提前i拍完成。经n-i拍后的伴随式状态S′i(x)等于R从S0输入端接入的情况下移位运算i拍后的状态Si(x)。因此，如果将接收码组R按f(x)的方式接入伴随式计算电路，同时将缓冲寄存器改为n-i级，那么原循环码的一般译码电路就可改成(n-i,k-i)缩短循环码译码电路。例如，(15,11)循环Hamming码缩短5位便得到了(10,6)码，其生成多项式为g(x)=x3+x+1，f(x)=Rg(x)［x5］=x2+x，图5．4．10是（10，6）缩短循环码的译码电路。



图5．4．10(10,6)缩短循环码的译码电路


总之，缩短循环码是在原循环码中选前i个信息位为0的码字组成。由于缩短的是信息元，缩短循环码的校验元数目与原循环码相同，因此缩短码的汉明距离和纠错能力不会低于原循环码，甚至会比原循环码更大些。

缩短循环码的译码器可在原(n,k)循环码译码器基础上做如下修正后使用。 

（1） k级缓存器改为k-i级(或n级缓存器改为n-i级)。

（2） 为了与（1）的改动相适应，R(x)应自动乘以xi，再输入伴随式计算电路。

例5．4．7试基于(7,4)循环Hamming码构造一个(7,3)删信码。

删信是信息位向校验位的变相转化，也就是说，保持长度n不变的情况下，维数k减小，奇偶校验符号的个数n-k增加。如果循环码的最小码距为奇数，生成子多项式乘以x+1会产生删信码、dmin增加1的效果。从表5．4．2中可查到(7,4)循环Hamming码的生成多项式为
g(x)=x3+x+1
则其(7,3)删信码的生成多项式为
g(x)(x+1)=x4+x3+x2+1
新的生成子的阶数增加了1，使得校验位数也增加了。然而，对于任意的n值，x+1是xn+1的因子，这样对于原始的n值来讲，新的生成子仍是xn+1的因子，因而码长不变。

新码中的任意码字都由原始码乘以x+1(也就是说，向左移位，然后与原始码相加)得到的码字构成。所得的结果一定是码重为偶数，因为相加的两个序列具有相同码重，模2加法运算不会将总体偶校验转变成奇校验。以码序列1000101为例，它向左移位后与其自身相加，即
1000101+0001011=1001110
相加的每个序列的码重都是3，但是加法运算导致码字中的两个1被取消，剩下一个重量为4的码字。

假设原始码的最小码距值为奇数，因此包含了奇数码重的码字，删除的码字就是原始码中码重为偶数的码字。术语“删信”的产生是因为所有码重为奇数的码字都被删除。结果就是最小码距成为某个偶数值。

在本例中，生成子x3+x+1被删除，成为x4+x3+x2+1，新的生成子码重为4，显然，新的dmin不能大于4。由于最小码距必然由它的原始值3增加到了某个偶数值，因此现在这个值是4。在其他删信Hamming码中，生成子的码重可能更高，但是仍然可以看到该码中包含码重为4的码字，所以删信操作后dmin=4。

删信码可以按照以新的生成子为基础的一般方法进行解码，但由于码字也是原始Hamming码的码字，因而可以根据以原始Hamming码生成子为除数和以x+1为除数两种情况来形成两个伴随式，如图5．4．11所示。如果两个伴随式都是0，那么说明无误码。如果两个伴随式都是非零的，那么可以假设存在单个比特的误码，并按照一般方法用汉明伴随式电路来对其纠错。如果一个伴随式是零，另外一个是非零，那么说明存在着不可纠正的误码。这种方法有助于对不可纠正的误码进行检测。



图5．4．11删信码伴随式的形成


存在以下3种情况。

（1） 接收序列0110010(单个错误)，伴随式为101和1(可纠正的误码)。

（2） 接收序列0110011(两个误码)，伴随式为110和0(不可纠正的误码)。

（3） 接收序列1011000(三个误码)，伴随式为000和1(不可纠正的误码)。

在第一种情况中，对第一个伴随式移位一次得到001、010、100，表明误码在第3比特。

5．4．3．4捕错译码

循环码译码器的复杂性主要取决于由伴随式确定错误图样的组合电路的简单与否，上节所述的梅吉特译码器对于纠错能力较小的循环码，这种组合电路可以做得比较简单，如循环Hamming码。对于纠大量错误的译码而言，梅吉特译码器中由伴随式求错误图样电路将很复杂。此外，对于某些码型，采用捕错译码方法也能够用较简单的组合逻辑电路实现译码，它特别适用于纠突发错误码、纠单个随机错误码，以及某些低码率和码长较短、纠错能力较弱的码。这种方法的错误图样生成电路更为简单，因而特别受到工程技术人员的欢迎，但这种译码方法对长码或高纠错能力的码来说效果还不理想。

捕错译码的基本原理如下。

设码字C(x)是某个纠t(t≤n-k)个错误的系统型(n，k)循环码的码字多项式，接收矢量多项式R(x)=C(x)+E(x)，通过译码电路可得伴随式为
S(x)≡E(x) mod g(x)

记E(x)=en-1xn-1+…+en-kxn-k+en-k-1xn-k-1+…+e0，EI(x)=en-1xn-1+…+en-kxn-k为信息位错误图样，EP(x)=en-k-1xn-k-1+…+e0为校验位错误图样，则有
S(x)EI(x)+EP(x) mod g(x)
若传输中恰好使一个码字的所有t个以内的错误都集中于校验位段，信息位无错，则有EI(x)=0，E(x)=EP(x)，再考虑到g(x)是n-k次的，所以有伴随式S(x)=EP(x) mod g(x)=EP(x)，这说明错误图样的后r(r=n-k)位就是伴随式S(x)的系数，而其前k位为0，这样只要译码器算出了伴随式S(x)，就意味着得到错误图样。纠错就只需用接收序列与伴随式右端对齐相减(二元码也可相加)。然而很遗憾，在实际情况中t个错误不会只出现在校验位上。所幸的是对于循环码，由于其循环移位特性使伴随式的“循环性”等价于错误图样在“循环”，因此只要传输中的错误集中在码字的任意r位码元段内，就可以通过伴随式计算电路自发运算若干次，将错误图样中的所有错误集中“捕获”到码字的后r位码元段，将此时的伴随式与移位后的接收矢量相减，完成纠错。

对于纠t个错误的循环码来说，必须使t个错误能连续地出现在n-k位以内，这等价于要求有连续k位码元无错，或错误图样中连续t位的值为0。由于t个错误均匀分布在n个码元中是最难满足连续t位无错这一要求，因此(n，k)循环码可以用捕错译码的条件如下： 
k<n/t或R<1/t
在译码过程中，如何判断经过循环移位，错误已全部集中在接收矢量的最低次的n-k位以内？对(n，k)循环码来说，下面定理给出了判断准则。

定理5．4．7对于纠正t个错误的(n，k)循环码，捕错译码过程中已把t个错误集中在矢量R(i)(x)的最低次n-k位以内的充要条件是此时的伴随式重量满足小于或等于t，即
W(Si(x))≤t
证明：  若经过i次循环移位后错误已集中在n-k位低次位码元段以内，则
Si(x)=xiE(x)=E(i)(x)=E(i)P(x) mod g(x)
Si(x)=E(i)P(x)
W(Si(x))=W(E(i)P(x))
因为码的纠错能力为t，若错误图样E(x)是一个可纠正的错误图样，则其中“1”码元的数目不大于t，即W(E(i)P(x))≤t，因而，当错误图样 E(x)经循环移位i次，错误已集中在n-k位低次位码元段以内时，对应E(i)(x)的重量也必小于或等于t，所以
W(Si(x))=W(E(i)(x))≤t
反之，若W(Si(x))≤t，则错误一定集中在n-k位低次位码元段内。设错误没有集中在该段以内，则
0E(i)(x)≥0g(x)
由此
E(i)(x)=q(x)g(x)+Si(x)
E(i)(x)-Si(x)=q(x)g(x)=C(i)(x)
C(i)(x)是g(x)的倍式，由循环码性质可知它必是(n，k)循环码中的一个码字。因此
W(E(i)(x)+(-Si(x))=W(C(i)(x))≥d=2t+1
由码重三角不等式可知
W(E(i)(x))+W(-Si(x))≥W(E(i)(x)+(-Si(x))≥2t+1
因为W(E(i)(x))≤t，所以W(-Si(x))≥2t+1-t=t+1>t

由于W(-Si(x))=W(Si(x))，因此上式与假设W(Si(x))≤t相矛盾。因而错误没有集中在n-k低次位以内的反证法假设不能成立，故错误集中在n-k低次位内。

［证毕］

捕错译码的基本流程如下。

(1) 计算接收多项式R(x)对应的伴随式S(x)。

(2) 计算S(x)的重量W(S(x))，并判断是否满足W(Si(x))≤t。若满足，说明错误已被集中捕获至n-k低次位以内，则令E(i)(x)=S(x)，R(i)(x)=R(x)，进入步骤(3)； 反之，把R(x)和相应的伴随式S(x)一起同时在译码器的各自移位寄存器中移位i次，使这些错误全部集中到xiR(x)的后n-k位上。

（3） C(i)(x)=R(i)(x)+E(i)(x)。

(4) 将已纠错的码字C(i)(x)再循环移位n-i次，恢复到原来的接收矢量中各码元的顺序关系，得到码字估值C(x)。

5．4．3．5大数逻辑译码

循环码译码器的复杂性主要取决于码的代数结构，梅吉特译码和捕错译码仅对部分循环码复杂度较低，但对绝大多数纠多个随机错误的循环码来说没有如此简单的译码方法。大数逻辑译码是1954年里德(Reed)在译里德穆勒(ReedMuller，RM)码时提出的一种较简单的译码方法，尽管对于一般码长而言，能用大数逻辑方法译码的大数逻辑可译码，其纠错能力和码率都稍次于有相同参数的其他码，如BCH码，但由于它的译码算法和设备均比相应的BCH码译码方法要简单，因此在实际中有一定的应用。

通过以下例子介绍二进制循环码的大数逻辑译码的基本思想。

例5．4．8(7,3,4)增余删信Hamming码的生成多项式g(x)=(x+1)(x3+x+1)=x4+x3+x2+1，一致校验矩阵为
H=1011000111010011000100110001
接收n重矢量R=C+E，发送码字和错误图样分别为C=(c6，…，c1，c0)和E=(e6，…，e1，e0)，相应的伴随式为
ST=s3s2s1s0=HET=1011000111010011000100110001e6e5e4e3e2e1e0
对伴随式的分量s3、s2和s1进行线性组合，也就是对H矩阵的行进行线性组合，得到以下一组新的校验方程组： 
A1=s3=e6+e4+e3
A2=s1=e6+e5+e1
A3=s2+s0=e6+e2+e0(5.4.13)
该方程组所对应的校验矩阵为
HG=101100011000101000101
由校验方程的定义可知，HG的行向量是H的行向量的线性组合，因为CHT=0，即许用码字C与一致校验矩阵H的各行正交，所以同样有许用码字C与校验矩阵HG的各行正交，即CHGT=0。

另外，观察校验方程组（5.4.13）可知，每个方程式中均包含e6，而e5，e4， …，e0仅出现在一个方程式中。具有这样特点的校验方程称为正交于e6的正交校验方程(或正交监督方程、正交一致校验和式)，该方程组的系数矩阵HG称为正交校验矩阵，e6称为正交码元位。

进一步观察例5．4．8中校验方程组（5.4.13）可以发现如下规律。

(1) 若错误图样发生一个错误，且在正交码元位上，即e6=1，则A1=1，A2=1，A3=1。

(2) 若错误图样发生一个错误，且不在正交码元位上，即e6=0，某个ei=1(i=0,1,2,3,4,5)，则A1、A2、A3有且只有一个为1。

(3) 若错误图样发生两个错误，一个在正交码元位上，一个不在正交码元位上，即e6=1，某个ei=1(i=0,1,2,3,4,5)，则在A1、A2、A3中有两个1、一个0。

(4) 若错误图样发生两个错误，都不在正交码元位上，则A1、A2、A3或者都为0，或者两个为1、一个为0。

不难分析该(7,3)码最小距离为4，其纠错能力为1，结合上述规律可知，当传输中只发生1位错误(码的纠错能力之内)时，可以根据和式Ai中取值为1的个数情况对正交位r6的传输情况进行判断和纠错。这就是大数逻辑译码的基本思想。

对于循环码不必分别建立正交于每个码元位的正交一致校验方程组，而只需根据其循环移位特性，在对r6进行正交校验后，仍基于式（5.4.13），依次将r5 ~r0循环移位至正交位，按照同样的方法进行校验。这种根据正交方程中取值为1的个数的多少进行译码的方法称为大数逻辑译码。由式（5.4.13）可见，正交和式Ai可以表示为伴随式各分量的线性组合，也可以表示为接收矢量(错误图样)各分量的线性组合，因此大数逻辑译码器可分为Ⅰ型和Ⅱ型，它们没有本质的区别。

可以证明，有J个正交校验和式的码能纠正t≤J/2个错误。当传输错误发生在正交位时，正交一致校验方程组中将有大于J/2个和式取值为1，因此可依据此对每位码元进行正交校验。例5．4．8中正交一致校验方程组仅对e6(即x6)码元位正交，因此只要用一次大数逻辑判决就能完成对该位的译码，故称之为一步大数逻辑译码。一步大数逻辑译码的方法虽然简单，但是此类码不多，且纠错能力也不高。为了提高大数逻辑译码的应用范围和改善码的纠错能力，可把对某一码元位正交的概念扩展至对某一码元位置集合正交，并逐次进行大数逻辑译码。这种需要L步大数逻辑译码才能最后译出一个码元的方法称为L步大数逻辑译码。

5．4．4BCH码与RS码
5．4．4．1BCH码

BCH码是最重要的一类循环码，BCH码分别由Hocquenghem在1959年，以及Bose和Chaudhuri在1960年独立提出。1960年Peterson对二进制BCH码提出一种有效的译码方法。从那时起编码领域的学者对BCH码的译码进行了深入研究。由于这些算法均需要应用许多复杂的代数理论知识，特别是有限域上的多项式知识，在此不做深入介绍，仅对BCH码的概念、构造及译码做简单介绍。

BCH码是一类纠正多个随机错误的循环码，它的参数可以在较大范围内变化，选用灵活，适用性强。最为常用的二元BCH码是本原BCH码，其参数及其关系式：  
码字长度：n=2m-1
校验位数目：n-k≤mt
最小距离：d≥2t+1(5.4.14)
式中： m为正整数，一般m≥3，纠错位数t<(2m-1)/2。

BCH码的构造是利用循环码生成多项式g(x)之根来研究的，其生成多项式可以按如下流程得到。

令α是GF(2m)的本原元，考虑α的连续幂序列
α，α2，α3，α4，…，α2t
令mi(t)是以αi为根的最小多项式，则满足式（5.4.14）所列参数要求的BCH码生成多项式为
g(x)=LCM［m1(x)，m2(x)，m3(x)，…，m2t(x)］
式中： LCM为最小公倍式。

利用共轭元具有相同最小多项式的特点，则生成多项式可以写成
g(x)=LCM［m1(x)，m3(x)，…，m2t-1(x)］

表5．4．7给出较小码长的BCH码相关参数和生成多项式。表中： n表示码长； k表示信息位长度； t表示码的纠错能力； 生成多项式g(x)栏下的数字表示其系数，如表中生成多项式为3551时，该多项式序列的二进制表示为(11101101001)，则其生成多项式为g(x)=x10+x9+x8+x6+x5+x3+1，构成一个能纠2个错误的(31,21)BCH码。



表5．4．7BCH码的参数和生成多项式




nktg(x)(八进制)


1572721

15532461

312123551

31163107657

311155423325

6351212471

634531701317

63394166623567

63306157464165547

127113241567

127106311554743

2552392267543

2552313156720665


例5．4．9在GF(24)上构造长度为2n-1=15的纠错能力为t的二元本原BCH码。

解： GF(24)如表5．4．8所示。



表5．4．8n=4，p(x)=x4+x+1的GF(24)的所有元素




α的幂α的多项式α的幂α的多项式


00α7α3+α+1

11α8α2+1

ααα9α3+α

α2α2α10α2+α+1

α3α3α11α3+α2+α

α4α+1α12α3+α2+α+1

α5α2+αα13α3+α2+1

α6α3+α2α14α3+1


(1)  设t=1。由定义该码的生成多项式以GF(24)本原元α和α2为根。考虑到共轭元素有相同最小多项式，所以生成多项式为
g(x)=LCM［m1(x)，m3(x)，…，m2t-1(x)］=m1(x)
=(x+α)(x+α2)(x+α4)(x+α8)=x4+x+1
该生成多项式系数矢量的八进制表示为“23”，它正是(15,11)Hamming码的生成多项式，它有4位校验位。该码的设计距离d=2t+1=3，可以求出该码的实际最小距离也是3，设计距离等于最小距离。

(2)  长度为24-1=15，能纠t=2位错误的BCH码的生成多项式以α、α2、α3、α4为根(α为GF(24)本原元)。考虑到α、α2、α4、α8和 α3、α6、α9、α12为两组共轭根，所以生成多项式为
g(x)=LCM［m1(x)，m3(x)，…，m2t-1(x)］=m1(x)m3(x)
=(x+α)(x+α2)(x+α4)(x+α8)(x+α3)(x+α6)(x+α9)(x+α12)
=(x4+x+1)(x4+x3+x2+x+1)
=x8+x7+x6+x4+1
这个生成多项式的八进制表示为“721”，它生成一个(15,7)BCH码，有8位校验位，能纠正任意两位错误。这个码的设计距离d=2t+l=5，可以求出这个码的实际最小距离也是5。

(3) 对于可以纠正t=3个错误的BCH码，有
g(x)=LCM［m1(x)，m3(x)，…，m2t-1(x)］=m1(x)m3(x)m5(x)
=(x+α)(x+α2)(x+α4)(x+α8)(x+α3)(x+α6)(x+α9)(x+α12)(x+α5)
(x+α10)
=(x4+x+1)(x4+x3+x2+x+1)(x2+x+1)
=x10+x8+x5+x4+x2+x+1
可见，r=0g(x)=10，这是一个(15，5)BCH码，该码的设计距离d=2t+l=7，与其实际最小距离相同。

(4) 当t=4时，有
g(x)=LCM［m1(x)，m3(x)，…，m2t-1(x)］=m1(x)m3(x)m5(x)m7(x)
=(x4+x+1)(x4+x3+x2+x+1)(x2+x+1)(x4+x3+1)
=x14+x13+x12+x11+x10+x9+x8+x7+x6+x5+x4+x3+x2+x+1
可见，该码为(15，1)BCH码，即(15,1)重复码。这个码只有两个码字，全0码字和全1码字，所以它的最小距离为15，然而这个码的设计距离d=2t+l=9。此时，实际最小距离大于设计距离。这个码实际可以纠正7个随机错误。

(5) 如果继续用上面的方法构造t为5、6、7的BCH码，将会发现得到的都是和上面同样的生成多项式：
g(x)=x14+x13+x12+x11+x10+x9+x8+x7+x6+x5+x4+x3+x2+x+1
因为(15，1)BCH码的纠错能力覆盖了t=4~7。可见按BCH码构造的生成多项式实际可达纠错能力大于或等于设计能力t。

(6) 如果要构造t=8的BCH码，就需要域元素α15的最小多项式m15(x)，这已经超出了扩域GF(24)的范畴，需要更大的扩域才能做到。可见，纠错能力更强的BCH码需要用域元素更多的扩域来构造。

对于BCH码来说，也可以生成多项式的根定义一致校验矩阵H。如果码字多项式C(x)有一个根β，即C(β)=0，也就是
cn-1βn-1+cn-2βn-2+…+c1β+c0=0
将上式写为矩阵形式，有
Cβn-1β1=0
式中： C=(cn-1,cn-2,…,c1,c0)是码字矢量。

因此，如果β1，β2，…，βj都是C(x)的根，则
Cβn-11βn-12…βn-1j

β1β2…βj
1111=0
由校验矩阵H的定义可得
CHT=0
因此可认为校验矩阵H为
(βn-11)T…(β1)T1T(βn-12)T…(β2)T1T(βn-1j)T…(βj)T1T
对于(15,11)Hamming码来说，若α为GF(24)上本原元，则有
H=［(α14)T,…,(α2)T,(α)T,1T］
本原元素α的各次幂正好是这个域的全部非零元。由表5．4．8可得相应的校验矩阵为
H=111101011001000011110101100100001111010110010111010110010001
同样，对于生成多项式为g(x)=x10+x8+x5+x4+x2+x+1的(15,7)BCH码，生成多项式的根中只有α、α3是独立的，所以校验矩阵为
H=(αn-1)T…(α2)T(α)T1T(α3n-3)T…(α6)T(α3)T1T
下面介绍BCH码的经典译码算法原理，是一种扩展Peterson算法(也称GorensteinZierler算法)。

在对BCH码进行译码时，如果发生v≤t个错误，那么一般要找出这v个错误的位置，同时要求出这些错误的值(错误大小)。一般可以从伴随式求得错误位置多项式。迭代算法的译码过程就是利用BCH码生成多项式的特点确定这两个信息的过程。当然，在二元码中因为出错位的取值总等于1，所以只需求出错误位置。

对于一个码长为n的BCH码，其纠错能力为t，考虑其错误图样多项式(简称错误多项式)： 
E(x)=en-1xn-1+en-2xn-2+…+e1x+e0
系数en-i(i=1~n-1)表示错误图样中相应码元的取值，最多有t个非零系数。假设实际发生了v(0≤v≤t)个错误，这些错误发生在位置j1，j2，…，jv，则可以把错误多项式改写为
E(x)=ejvxjv+…+ej2xj2+ej1xj1
E(x)=Yvxjv+…+Y2xj2+Y1xj1
式中： Yl为第l个错误的取值。

根据BCH码的定义，可把伴随式定义为接收矢量多项式在各个域元素处的值，如在域元素α处，伴随式为
S=s1s2s2tT
式中
si=E(αi)=R(αi)
=∑vl=1Yl(αi)jl=∑vl=1Yl(αjl)i（i=1,2,…,2t）（5.4.15）
令
αjlXl
则有
si=∑vl=1YlXil（i=1,2,…,2t）
式中： Yl表示错误大小； Xl表示错误位置。

于是上式展开为
s1=Y1X1+Y2X2+…+YvXv
s2=Y1X21+Y2X22+…+YvX2v

s2t=Y1X2t1+Y2X2t2+…+YvX2tv（5.4.16）
这是一个有2v个未知参量的方程组，包含错误大小Y1，Y2，…，Yv，错误位置X1，X2,…，Xv，再定义错误位置多项式为
σ(x)=(1-xX1)(1-xX2)…(1-xXt)
1+σ1x+σ2x2+…+σtxt
也就是说，错误位置的倒数x-1l是这个多项式的零点值。应用错误位置多项式可以把上面的方程组改写成矩阵形式:  
s1s2…svs2s3…sv+1svsv+1…s2v-1σvσv-1σ1=-sv+1sv+2s2v（5.4.17）
通过解这个方程组就可以求出错误位置多项式的所有系数σi的值。在解方程组过程中需要求伴随式矩阵的逆，所以要求伴随式矩阵是非奇异的。可以证明，当存在v个错误时，伴随式矩阵是非奇异的。由此可以从伴随式矩阵的奇异性中确定实际发生错误的个数v。

BCH码迭代法译码步骤具体如下。

(1) 设v=t，计算伴随式矩阵的行列式det(M)，其中，
M=s1s2…svs2s3…sv+1svsv+1…s2v-1
若det(M)=0，则说明伴随式矩阵是奇异的，接收码字中没有发生t个错误。

(2) 对矩阵M做降维处理，设v=t-1，重新计算det(M)。重复这个过程直到det(M)≠0，这时的v值就是实际发生错误的个数。

(3) 根据找到的v值，解方程式（5.4.17），得到错误位置多项式的所有系数σi的值。

(4) 解方程σ(x)=0，得到它的所有零点。这里可采用钱氏搜索(Chien search)算法进行穷举搜索，即把所有域元素α逐一代入σ(x)中进行检测，看方程σ(x)=0是否成立。得到它的所有零点后，其倒数也就是
σ(x)=(1-xX1)(1-xX2)…(1-xXt)
式中： X1，X2,…，Xv为错误位置。

对于二进制码来说，因为错误值只能是1，所以译码过程到这里就结束了。对于非二进制码，要求错误值Y1，Y2,…，Yv，再回到方程式（5.4.17），现在其中的错误位置X1，X2,…，Xv是已知的，解这个线性方程式，就可以得到所有错误值。

例5．4．10对于例5．4．9中构造的(15,7)BCH码，设收到矢量R=(100010111000101)。将其以多项式表示，根据式（5.4.15）计算出其伴随式(运算在GF(24)上进行)为s1=α14，s2=s21=α13，s3=α13，s4=s22=α11。代入方程式（5.4.17）可得
σ(x)=1+α14x+α2x2
=(1-xα-3)(1-xα-14)
试探可得α3和α10为错误位置多项式的根，故第12位和第5位出错，于是对应的码字C=(100000111001101)。

由上面的介绍可知，决定BCH译码器复杂度和速度的主要因素是求错误位置多项式σ(x)。1966年伯利坎普(Berlekamp)提出了迭代译码算法，1969年梅西(Massey)进行了改进，这种译码算法称为BM迭代译码算法，它大大节省了计算量，加快了译码速度，很好地解决了BCH码译码的实用问题。之后研究人员不断提出新的译码算法，如欧几里得算法、连分式算法、频域译码等。迭代算法的优点是使用的硬件资源相对较少，而且对错误位数不敏感，当错误位数较多时，迭代译码算法所使用的硬件资源与位数少的情况相差无几。另外，迭代译码算法的运算速度与码的纠错能力呈线性关系，当纠错能力大时，迭代次数也会相应增多。

5．4．4．2RS码

RS（ReedSolomon）码首先由里德(Reed)和索罗门(Solomon)于1960年构造，是一类具有很强纠错能力的非二进制BCH码，近年来在许多通信系统中获得了应用。RS码的码元符号取自有限域GF(q)，它的生成多项式的根也是GF(q)中的本原元，所以它的符号域和根域相同。由于RS码是以每符号m bit进行的多元符号编码，在编码方法上与二元(n,k)循环码不同。分组块长n=2m-1的码字比特数为m(2m-1)bit，当m=1时就是二元编码。RS码一般常用m=8bit，这类RS码具有很大应用价值。能纠正t个错误的RS码具有如下参数： 
码字长度： n=q-1(符号)
校验位数据： n-k=2t(符号)
最小距离： d=2t+1(符号)
由5．3．3节介绍的码的性能限可知，线性码的最大可能的最小距离为校验位数目加1，这就是Singleton限界，RS码正好达到此限。因此，RS码是一种MDS码，在同等码率下其纠错能力最强。

若取q=2m，则RS码的码元符号取自GF(2m)，码长n=2m-1。一个能纠正t位符号错误的RS码的生成多项式可表示为
g(x)=(x+α)(x+α2)(x+α3)…(x+α2t)
式中： α为GF(2m)上的本原元。

由于RS码实质是一类非二进制BCH码，因此其译码算法可以沿用BCH译码算法，只是它在纠错时除了要确定错误位置Yi外，还要求出相应的错误值Xi。

RS码在深空通信、移动通信、军用通信、光纤通信、磁盘阵列及光盘纠错等方面得到了广泛应用。例如，RS(255,223)码已成为美国国家航空航天局和欧洲空间站的深空通信系统中的标准信道编码，RS(31,15)码是军用通信中的首选信道编码，RSPC(182,172)(208,192)成为数字光盘(DVD)系统的纠错标准。

例5．4．11一个符号取自GF(23)，长度n=23-l=7，能纠正2个错误的RS码的生成多项式为
g(x)=(x+α)(x+α2)(x+α3)(x+α4)
根据表5．4．9所示的GF(23)域元素，可得
g(x)=x4+α3x3+x2+αx+α3
式中： α为本原多项式x3+x+1的根。这个RS码的校验位长n-k=4，因而是(7,3)RS码。

假设该(7,3)RS码经传输，在第2位出现值为α的错误，第6位出现 α2的错误，则错误多项式为
E(x)=α2x6+αx2
因此伴随矢量S=(s1,s2,s3,s4)(运算在GF(23)上进行)。为
s1=E(α)=α2α6+αα2=1s2=E(α2)=α2α12+αα4=α4s3=E(α3)=α2α18+αα6=α2s4=E(α4)=α2α24+αα8=α3




表5．4．9n=3，p(x)=x3+x+1的GF(23)的所有元素




α的幂α的多项式3重表示式


00000

11001

αα010

α2α2100

α3α+1011

α4α2+α110

α5α2+α+1111

α6α2+1101


于是，错误位置多项式σ(x)的系数σ1、σ2是下面方程组的解：
1α4α4α2σ2σ1=α2α3
由此得错误位置多项式为
σ(x)=σ2x2+σ1x+1=αx2+x+1
用钱氏搜索算法进行穷举搜索，把有限域GF(23)的元素逐个代入σ(x)=αx2+x+1试探，发现仅当x=α和x=α5时错误位置多项式σ(x)=αx2+x+1为零。所以错误位置为i1=7-5=2和i2=7-1=6，这正是所设的错误位置。

设β1=αi1=α2，β2=αi2=α6，于是错误值方程为
β1β2β21β22Y2Y1=s1s2
解此方程可得
Y2=α12+α10α14+α10=α
Y1=α6+α4α=α2
于是第2位出现值为α、第6位出现值为α2的错误，这正是题设所假设的错误值。






5．5卷积码

卷积码自1955年由Elias发明以来，从20世纪70年代开始被广泛应用于无线通信、深空通信及广播通信中，普及的原因是使用最大似然序列译码器进行译码时实现相对简单，以及与ReedSolomon码级联时表现出来的优异性能。从20世纪90年代初开始，由于在Turbo(或者类Turbo)码中级联多个卷积码所表现出来的有效性，这一类码又重新得到重视。本节从码的定义与表述、译码算法以及应用等方面介绍卷积码。

5．5．1卷积码的定义

卷积码是具有十分独特代数结构的线性码，虽然它们可以在基于分组的情况下使用，但是它们的编码器更多地被描述为面向数据流的形式。首先介绍四状态、码率为1/2的卷积码，它的编码器如图5．5．1所示。每一个信息比特进入编码器都会生成相应的两个编码比特，即k=1,n=2； 编码器中含有m=2个二进制记忆单元(寄存器)，其状态数目为2m=4，编码约束度为m+1=3。编码器的上下两部分像是运算在GF(2)域上的两个离散时间有限冲激响应滤波器。顶部滤波器的冲激响应是g(1)=［111］，而底部滤波器的冲激响应是g(2)=［101］。从这样的角度看，编码器的输出c(1)是输入u和冲激响应g(1)的卷积，编码器的输出c(2)也是如此，这就是卷积码的起源。卷积码通常用(n,k,m)，则图5．5．1表示(2,1,2)卷积码。这样的话，对于j=1,2，有
c(j)=u○ *g(j)
其中，○ *表示离散卷积，所有的运算都是模之和。

而且，时域里的卷积运算对应变换域里的乘积运算，这个方程还可以重新写成
c(j)(D)=u(D)g(j)(D)


图5．5．1一个四状态、码率为1/2的

卷积码编码器

其中，D的多项式系数是对应向量的元素，所以g(1)(D)=1+D+D2,g(2)(D)=1+D2。D在编码的文献里被广泛使用，它等价于单位离散时间延迟算子z-1。

上述编码过程可以描述为如下形式： 
［c(1)(D)c(2)(D)］=u(D)［g(1)(D)g(2)(D)］
=u(D)G(D)
式中： G(D)=［g(1)(D)g(2)(D)］是该码的生成矩阵，为1×2阶矩阵； g(j)(D)为生成多项式。

对于长为l的输入数据(u(D)的次数是l-1)，输出数据的长度为2l+4。为了使编码器状态归零，需使用额外的两个0，从而产生了4个额外编码比特。因此，实际上码率是l/(2l+4)，当l很大时码率接近1/2。由于信息数据和码字之间具有简单而高度结构化的关系，卷积码具有较低的编码复杂度和译码复杂度。






5．5．2卷积码的表示
5．5．2．1代数描述

定义一个二元卷积码C，码字c(D)∈C有如下的形式： 
c(D)=［c(1)(D)c(2)(D)…c(n)(D)］
式中： c(j)(D)=∑∞i=rc(j)iDi。

每一个c(D)∈C可以写成这个基向量{gi(D)}ki=1的线性组合：
c(D)=∑ki=1u(i)(D)gi(D)
式中： k是C的维数。

与线性分组码类似，上式可以重写为
c(D)=u(D)G(D)(5.5.1)
这里u(D)=［u(1)(D)u(2)(D)…u(k)(D)］，基向量gi(D)=［g(1)i(D)g(2)i(D)…g(n)i(D)］构成了k×n生成矩阵G(D)的行，所以G(D)中第i行第j列的元素是g(j)i(D)。

G(D)表示一般的生成矩阵，它可以是系统或者非系统形式。存在一个(n-k)×n校验矩阵H(D)，使得
c(D)HT(D)=0
同时
G(D)HT(D)=0
在前面的两个等式中的0分别表示1×(n-k)零向量和k×(n-k)零矩阵。对于线性分组码，G(D)和H(D)都有系统形式，即为G0(D)=［I|P(D)］和H0(D)=［PT(D)|I］，G0(D)是由G(D)通过行变换得到。卷积码也有类似的情况，通过例5．5．1来描述。

例5．5．1一个码率为2/3的卷积码的生成矩阵如下： 
G(D)=1+D1+D+D201+D111+DD1+D2(5.5.2)
如将矩阵的第一行乘以(1+D+D2)/(1+D)，把新得到的第一行加到第二行，把新得到的第二行乘以(1+D)，就可以得到系统形式
G0(D)=101+D+D2011+D3+D41+D(5.5.3)
基于式（5.5.2）、式（5.5.3）的编码器如图5.5.2所示。



图5.5.2例5.5.1中给出的2/3码率卷积码的编码器实现


由子矩阵P(D)(G0(D)的最右一列)可得
H0(D)=1+D+D21+D3+D41+D1
这是因为H0(D)=［PT(D)|I］。G(D)中元素分母的最小公倍式是(1+D+D2)(1+D2)，所以可得一个多项式形式的生成矩阵，用Gp(D)来表示： 
Gp(D)=(1+D)30(1+D+D2)(1+D)3(1+D+D2)(1+D2)(1+D+D2)(1+D)D(1+D+D2)
将H0(D)中的每个元素乘以1+D，可得
Hp(D)=［1+D31+D3+D41+D］
任意可实现的卷积码都必定存在一个多项式形式的生成矩阵和校验矩阵。需要强调的是，G(D)、G0(D)和Gp(D)都生成同一个码，即它们的行张成相同的子空间。类似线性分组码，卷积码的生成矩阵也可以写成码字的形式。

例5．5．2码率为1/2、生成矩阵是G(D)=［g(1)(D)g(2)(D)］=［1+D+D21+D2］的卷积码，g(1)=［g(1)0g(1)1g(1)2］=［111］,g(2)=［g(2)0g(2)1g(2)2］=［101］。对应复用码字的生成矩阵可写成如下形式：
G′=g(1)0g(2)0g(1)1g(2)1g(1)2g(2)2g(1)0g(2)0g(1)1g(2)1g(1)2g(2)2g(1)0g(2)0g(1)1g(2)1g(1)2g(2)2
=111011111011111011
与分组码不同，这是一个半无限长的生成矩阵。

一般来说，卷积码的参数n和k的典型值都非常小。如k=1,2,3和n=2,3,4，典型的码率如1/2、1/3、1/4、2/3和3/4，其中1/2是最常见的码率。更高的码率一般通过降低码率的卷积码进行凿孔实现，即将编码器输出的比特进行周期性地删除而不传输。例如，为了通过将1/2码率的卷积码进行凿孔来得到2/3码率的卷积码，只需要在每四个编码输出比特中删除一个。由于每组的四个码字比特是由两个信息比特产生的，但是四个里面只有三个被传输，于是就实现了码率2/3。因为编译码器的复杂度和性能，码率接近1(如0．95)的卷积码在实际中是不存在的，不管是否使用凿孔。卷积码译码器的复杂度正比于2μ，这里μ是编码器的记忆长度，即编码器记忆单元的个数。典型的μ值在10以下，工业标准中码率为1/2卷积码对应的μ=6，其生成多项式是g(1)(D)=1+D+D2+D3+D6 和g(2)(D)=1+D2+D3+D5+D6。常见的做法是用八进制数表示这些多项式，上述生成多项式可以表示成g(1)oct=117和g(2)oct=155。

5．5．2．2图表示

卷积码的代数描述有利于编码器的实现和分类。本节介绍的图表示方法则有利于卷积码的译码、设计、性能分析等。

下面以1/2码率的卷积码为例进行描述，其生成矩阵G(D)=［1+D+D21+D2］，编码器如图5．5．1所示。从图及状态的定义中可以得到状态转移表(表5．5．1)，按表可以画出这个码的有限状态转移图，如图5．5．3(a)所示。状态图对于通过分析确定卷积码的距离谱很有用，而且可以直接导出码的网格图，网格图是在水平方向上加上离散时间维度的状态图(图5．5．3(b))，编码器从00状态开始。值得注意的是，在i和i+1(i≥2)节之间的网格，本质上是状态图的完全复制。同时，任意给定长度的码序列表，可以通过追溯网格图上同样长度的所有可能路径，并在每条路径上截取标记每个分支(或边)的码符号得到。



表5．5．1状态转移表




输入ui当前状态ui-1ui-2下一状态uiui-1输出c(i)ic(2)i


0000000

1001011

0010011

1011000

0100110

1101101

0110101

1111110





图5．5．3有限状态转移图和编码器的网格图


考虑基于网格图译码的时候，将会发现，除非网格图的最后一个状态是已知的，否则得到的末尾几个译码比特(大概5μ比特)将有些不可靠。为了解决这种情况，系统设计者通常会将网格图终止在一个已知的状态里。很明显，这需要在信息序列后面再添加μ比特，这样做增加了编码开销(或者说降低了码率)。而一种能够保持网格图终止优势，同时可避免降低编码效率的办法是咬尾。对于咬尾卷积码，用信息序列的最后μ比特初始化编码器的状态，使得编码器的初始状态和最终状态都是一样的。






5．5．3卷积码的译码

目前卷积码有大数逻辑译码器、序列译码器、Viterbi 译码器和BCJR译码器，算法根据实际应用选择。通过Viterbi算法实现的最大似然序列译码器(MLSD)可最小化码字序列的错误概率，通过BCJR算法实现的逐比特最大化后验概率(MAP)译码器则可最小化信息误码率。一般来讲，这两种译码器的性能特性不管是从比特错误概率还是码字错误概率来讲都是相当接近的。但BCJR算法的译码复杂度约为Viterbi算法的3倍。本节主要讨论Viterbi译码算法。

我们关注的是二元对称信道(BSC)和二进制输入加性高斯白噪声信道(BIAWGNC)。为了满足统一的要求，对于两种信道用xi表示第i个输入，用yi表示第i个信道输出。给定信道输入xi=ci∈{0,1}和信道输出yi∈{0,1}，BSC的信道转移概率为
P(yi≠x|xi=x)=ε
P(yi=x|xi=x)=1-ε
式中： ε为交叉概率。

对于BIAWGNC，码字比特映射到信道输入是xi=(-1)ci∈{±1}。BIAWGNC的信道转移概率密度函数(PDF)为
p(yi|xi)=12πσexp［-(yi-xi)2/(2σ2)］
式中： σ2为零均值的高斯噪声采样ni的方差。

信道将ni直接加到传输值xi上(因此，yi=xi+ni)。首先考虑BSC，它的ML判决是
c^=arg maxc P(y|x)
可以化简成
c^=arg minc dH(y,x)
式中： dH(y,x)表示y和x之间的汉明距离(注意x=c)。

BIAWGNC的ML判决是
c^=arg maxc p(y|x)
可以简化成
c^=arg minc dE(y,x)
式中： dE(y,x)表示y和x之间的欧几里得距离(注意x=(-1)c)。

因此，对于BSC(BIAWGNC)，MLSD将会选择在汉明(欧几里得)距离的意义下最接近信道输出y的码字序列c。从理论上来说，由于网格图列举了所有的码字序列，因此可以用穷搜索的办法在网格图上寻找最接近y的序列。L条网格分支的计算：
ΓL=∑Ll=1λl(5.5.4)
式中： λl为第l个分支度量，且有
λl=∑nj=1dH(y(j)l,x(j)l)=∑nj=1y(j)lx(j)l（BSC）(5.5.5)
λl=∑nj=1d2E(y(j)l,x(j)l)=∑nj=1(y(j)l-x(j)l)2（BIAWGNC）(5.5.6)
在BSC下，x(j)l=c(j)l,而在BIAWGNC下，x(j)l=(-1)c(j)l。式（5.5.5）中的度量称为汉明度量，式（5.5.6）中的度量称为欧几里得度量。

很明显，arg minc dH(y,x)和arg minc dE(y,x)的计算量是非常庞大的，这是因为对于码率为k/（k+1）的码来说，网格图上L节意味着有2kL个码字序列。但是，Viterbi根据以下观察发现，在不损失性能的情况下这个复杂度可以降低到O(2μ)。考虑在图5．5．2(b)中以［000000］和［111011］开始的两个码字序列，它们对应的输入序列是［000…］和［100…］。观察到对应这两个序列的网格路径在状态0/时间0开始岔开，而在经过三个分支后(或者等效地说，经过网格图中的三节后)又汇聚到状态0。经过三节后汇合的重要性在于此后的网格中这两条路径有相同的扩展。因此，如果这两条路径其中一条在l=3时有着较大的累积度量，那么这条路径加上扩展以后也会拥有较大的累积度量。因此，从长远角度考虑可以把l=3时度量较大的路径移除。这条被保留的路径称为幸存路径。这样的做法将会应用到网格中所有汇聚路径，以及在l>3时每个网格节点拥有多于两条汇聚路径的网格中。这就引出了以下基于MLSD的Viterbi算法。







算法5．5．1Viterbi算法


定义

(1) λl(s′,s)是从l-1时刻状态s′转移到l时刻状态s的分支度量，这里s′,s∈{0,1,…,2μ-1}。

(2) Γl-1(s′)是在l-1时刻幸存状态s′的累积度量，即幸存路径的分支度量和。

(3) Γl(s′,s)是从l-1时刻状态s′延展到l时刻状态s路径的暂定累积度量，Γl(s′,s)=Γl-1(s′)+λl(s′,s)。

加比选(AddCompareSelect，ACS)迭代

初始化设定Γ0(0)=0和Γ0(s′)=-∞，对于所有s′∈{1,…,2μ-1}(编码器、网格被初始化为状态0)。

for l=1 to L

(1) 计算可能的分支度量λl(s′,s)。

(2) 对于在l-1时刻的每个状态s′和l时刻从状态s′出发所有可能到达的状态s，计算从状态s′延展到状态s路径的暂定累积度量Γl(s′,s)=Γl-1(s′)+λl(s′,s)。

(3) 对于在时刻l的每个状态s，从度量Γl(s′，s)选出并记录下具有最小度量的路径。这时状态s的累积度量是Γl(s)=mins′{Γl(s′,s)}

end


下面讨论几种选择最大似然码序列的方法。

面向分组的方法1： 假设一个信息序列长为kLbit，在经过L次加比选迭代后，选择具有最优累积度量的路径(若相同，则任意确定)，L在这里必须足够大，从而能充分发挥这个码的全部优势，一般有L>50μ。

面向分组的方法2： 假设一个非递归卷积码，在信息序列后面加上μ个0，使得网格在信息序列的末端可以回归0状态。在最后一次ACS迭代后，最大似然路径即是回归到状态0的幸存路径。同样，这里的L也必须足够大。

面向流的方法1： 这个方法利用了幸存路径都会有共同的“尾巴”这个特点。在第l次ACS迭代后，译码器将会沿着任意的幸存路径回溯δ个分支，然后将网格第l-δ节分支上的标记作为信息比特输出。这是一个很有效的滑动窗口译码器，其顺着网格的长度滑动，在δ节内存储和处理信息。译码延迟δ的值通常直接使用记忆长度的4倍或者5倍。然而，通过计算机仿真来确定这个值会更好，因为这个值是根据具体的码来确定的。也就是说，可以在码的网格图上使用计算机搜索算法，从在0状态/0时刻发散于全零路径、后来再聚合的最小重量码字序列中确定所需要的最大路径长度。δ可以设定成比这个最大路径长度稍微大一点的值。

面向流的方法2： 在第l次ACS迭代后，选择具有最优累积度量的网格路径，然后回溯δ个分支，选择网格第l-δ节中分支上所标记的比特作为对应的输出判决。

针对BIAWGNG的欧几里得距离度量(式5.5.6)可以做如下简化：
arg minc d2E(y,x)=arg minc ∑Ll=1∑nj=1(y(j)l-x(j)l)2
=arg minc∑Ll=1∑nj=1［(y(j)l)2+(x(j)l)2-2y(j)lx(j)l］
=arg maxc∑Ll=1∑nj=1y(j)lx(j)l
最后一行是因为第二行的平方项是独立于c的。因此，式（5.5.6）中的AWGN分支度量可以用下面的相关度量代替： 
λl=∑nj=1y(j)lx(j)l（5.5.7）

以上式子在BIAWGNC下成立。

图5．5．4展示了一个BSC上应用面向分组判决方法1的Viterbi译码例子。这里y=［00,01,00,01］，非幸存路径用“×”标示，累积度量在汇聚分支附近用粗体写出。例子中不存在彻底的最小距离路径，任一距离为2的路径与ML路径一样。



图5．5．4图5．5．3中的码在BSC上使用Viterbi译码的例子



图5．5．5展示了一个BIAWGNC上应用面向分组判决方法1和相关度量的Viterbi译码的例子。这里y=［-0．7,-0．5,-0．8,-0．6,-1．1,+0．4,+0．9,+0．8］，非幸存路径用“×”标示，累积度量在汇聚分支附近用粗体写出。ML路径就是累积度量为3．8的路径。



图5．5．5图5．5．3中的码在BIAWGNC上使用Viterbi译码的例子


5．5．4卷积码的应用
5．5．4．1IEEE 802．16中的卷积码

IEEE 802．16工作组专门开发宽带固定无线技术标准，IEEE 802．16标准的颁布推动了宽带无线接入的发展，是点对多点宽带固定无线接入系统的权威规范。在该标准的物理层规范中采用正交频分复用(OFDM)调制，信道编码分为扰码、前向纠错(FEC)和交织三步。

FEC包括级联的卷积码(内码)和RS码(外码)，编码过程是首先数据以块的形式经过RS编码器，然后经过0截止的卷积码编码器。RS码采用GF(28)中的(255，239，8)码，编码生成多项式为
g(x)=(x+α)(x+α2)…(x+α2t)，α=02HEX
域生成多项式为g(x)=x8+x4+x3+x2+1。码字可以缩短或打孔，以适应不同大小的数据块和不同的纠错能力。每个RS数据块进行卷积编码，采用(2,1,7)卷积码，生成多项式为G=［171,133］，如图5．5．6所示。



图5．5．6码率为1/2的卷积编码器


表5．5．2列出了为实现不同编码码率而使用的打孔模式和串联顺序，表中的“1”表示发送比特，“0”表示删除比特。



表5．5．2内卷积编码及配置




码率


Rate1/22/33/45/6

dfree10654

X11010110101

Y11111011010

XYX1Y1X1Y1Y2X1Y1Y2X3X1Y1Y2X3Y4X5


不同调制方式的块长度和码率见表5．5．3。



表5．5．3不同调制方式的块长度和码率




调制方式未编码块长度/字节编码块长度/字节总码率RS码率CC码率


BPSK12241/2(12,12,0)1/2

QPSK24481/2(32,24,4)2/3

QPSK36483/4(40,36,2)5/6

16QAM48961/2(64,48,8)2/3

16QAM72963/4(80,72,4)5/6

64QAM961442/3(108,96,6)3/4

64QAM1081443/4(120,108,6)5/6


5．5．4．2CCSDS中的卷积码

国际空间数据系统咨询委员会(CCSDS)标准是国际上广泛应用于深空通信领域的通信标准，该标准集合了目前在深空遥控、测控和通信标准等方面的最新研究成果，至今已发布了涵盖物理层调制解调、信道编译码、数据链路层协议和图像压缩等领域的众多标准，并为世界众多学术机构认可。CCSDS建议书最初针对民用目的而开发，因其具有卓越性能、良好经济效益和广泛适应性等特点，近年来越来越受到世界各国军事组织的关注，已逐步被世界各国应用于军用航天任务。

CCSDS建立了包括卷积码、RS码、级联码、Turbo码和LDPC码等信道码在内的一系列信道码标准。这些高增益信道编码通过优异的编译码算法设计获得可观的信道增益，有效降低信号解调阈值，进而抵消信号在长距离空间传播过程中带来的能量损失。其中，CCSDS标准推荐采用约束长度为7bit、码率为1/2的卷积码，通过打孔抽取可得到2/3、3/4、5/6和7/8，共4种码率。1/2编码器结构如图5．5．7所示，卷积码抽取参数如表5．5．4所示。



图5．5．71/2编码器结构




表5．5．4卷积码抽取参数




抽 取 样 式码率输出


C1: 10

C2: 112/3C1(1)C2(1)C2(2)…

C1: 101

C2: 1103/4C1(1)C2(1)C2(2)C1(3)…

C1: 10101

C2: 110105/6C1(1)C2(1)C2(2)C1(3)C2(4)C1(5)…

C1: 1000101

C2: 11110107/8C1(1)C2(1)C2(2)C2(3)C2(4)C1(5)C2(6)C1(7)…


5．5．4．3移动通信中的卷积码

WCDMA中有三种方式用于专用物理信道的编码，分别为卷积码(码率为1/2或1/3)、Turbo码(只有1/3码率)和没有信道编码。卷积编码主要用于误码率为10-3级别的业务，典型的有传统的话音业务和低速信令的传输。

WCDMA中定义的卷积编码器如图5．5．8所示，其约束长度K=9，码率为1/3或1/2。码率为1/3的编码器输出顺序为Output0,Output1,Output2,Output0,Output1，Output 2，Output 0，…，Output2。而码率为1/2的编码器输出顺序为Output 0，Output 1，Output 0，Output 1，Output 0，…，Output 1。移位寄存器的初始状态应为全“0”。因此，在编码前需要将8个0值尾比特添加到码块，以清零编码器。



图5．5．8码率为1/2和1/3的卷积编码器结构


从编码理论的角度考虑，卷积码性能主要与其编码效率、约束长度及自由距离有关。编码效率越小，编码冗余度就越大，纠错性能越好，占用带宽也越大； 约束长度越大，其纠错性能越好，但译码复杂度的指数增加，K=9是一个比较折中的方案。最后，在相同的编码效率和约束长度下，自由距离越大越好。K=9，编码效率为1/2、1/3的卷积码的最大自由距离为12和18，其生成多项式分别为(561)8、(753)8和(557)8、(663)8、(711)8。


图5．5．9给出了LTE系统中的咬尾卷积码编码器结构，其中寄存器的个数m=6，码率R=1/3，编码器输入的信息比特流为u，输出为(c(0),c(1),c(2))。



图5．5．9LTE系统中的咬尾卷积码编码器结构


咬尾卷积码已应用于4G 中的 LTE 系统中，并且成为5G 中超高可靠与低时延通信（URLLC）场景中的备选编码方案。LTE系统中的咬尾卷积码直接用信息序列的最后6个比特将编码寄存器初始化。这样全部编码后寄存器的结束状态将和编码前的起始状态相同，这样的编码方式没有传输额外的比特，从而提高了编码效率。

5．5．4．4卫星导航系统中的卷积码

全球卫星导航系统(Global Navigation Satellite System，GNSS)一般由空间星座、地面监控和用户设备三部分构成。空间星座是指GNSS中的导航卫星，该部分的作用是进行数据观测，并将接收的导航信息进行一定的处理后将其发送给地球用户。地面监控部分是整个GNSS 能否正常运行的保障，它主要的作用是对空间星座部分的卫星进行观测与跟踪，校对卫星的时钟、轨道等误差，使整个系统调整到正常运行状态。用户设备部分的功能是接收导航信息，并将接收到的信息进行各项处理(如数字化、功率放大、频率变换等)，从而得到有效的用户自身的时间、速度和位置等参数，以实现定位。导航电文是GNSS信号最主要的组成部分，它是导航卫星发送给接收机(用户)的描述卫星的各项运行状态参数的一段数据码信息。

导航电文的纠错编码作为导航电文设计的重要组成部分，为了保证GNSS导航电文传输的可靠性，越来越多的编译码方法运用到卫星导航系统中。目前 GNSS 中所涉及的电文编译码方法有Hamming 码，CRC 码、BCH 码、卷积码、LDPC和交织编码等。

在全球定位系统（GPS）及伽利略（Galileo）系统的导航电文中，均采用了(2,1,6)卷积码，其编码结构如图5．5．10所示。Galileo系统与GPS卷积码参数相同，区别在于GPS为无卷尾的卷积码，Galileo为有卷尾卷积码，即Galileo系统的卷积码在编码的尾部要添加“0”(卷尾)，使得卷积码从全“0”状态开始，最终编码结束状态又回到全“0”状态。



图5．5．10GPS(Galileo系统)中的卷积码结构


小结

纠错能力与最小距离d0的关系： 

对于(n,k)分组码，一般有以下结论。

若码的最小距离满足d0≥e+1，则码的检错能力为e。

若码的最小距离满足d0≥2t+1，则码的纠错能力为t。

若码的最小距离满足d0≥e+t+1(e>t)，则该码能纠正t个错误同时检测e个错误。

联合ε典型序列： 

设(x,y)∈(Xn; Yn)是n长随机序列对，对于任意小的正数ε>0，存在足够大的n，若满足下列条件，则称(x，y)为联合ε典型序列。
1nlogP(x)+H(X)<ε
1nlogP(y)+H(Y)<ε
1nlogP(xy)+H(XY)<ε
联合渐近等同分割性： 

对于任意小的ε>0，δ>0，当n足够大时，则有以下性质。

典型序列x、y和联合典型序列(x，y)满足
2-n［H(X)+ε］≤P(x)≤2-n［H(X)-ε］
2-n［H(Y)+ε］≤P(y)≤2-n［H(Y)-ε］
2-n［H(XY)+ε］≤P(xy)≤2-n［H(XY)-ε］
典型序列集Gε(X)、Gε(Y)和联合典型序列集Gε(XY)满足
P(Gε(X))≥1-δ
P(Gε(Y))≥1-δ
P(Gε(XY))≥1-δ
以NG表示典型序列集中元素个数，则Gε(X)、Gε(Y)和Gε(XY)中序列个数满足
(1-δ)2n［H(X)-ε］≤NGx≤2n［H(X)+ε］
(1-δ)2n［H(Y)-ε］≤NGy≤2n［H(Y)+ε］
(1-δ)2n［H(XY)-ε］≤NGxy≤2n［H(XY)+ε］
有噪信道编码定理： 有噪信道的信道容量为C，当信息传输率R<C，只要码长n足够长，总可以在输入Xn符号集中找出一组码(Q=2nR，n)和相应的译码规则，使译码错误概率任意小。

线性分组码： 

GF(2)域上的n维线性空间Vn中的一个k维子空间Vn,k。

一致校验矩阵H(r×n矩阵)满足
HCT=0T,CHT=0
生成矩阵G(k×n矩阵)满足
HGT=0T,GHT=0
标准生成矩阵和标准校验矩阵
G0=［IkP］，H0=［QIr］，且P=QT
标准阵列译码表见表5．3．3。

伴随式：
S=EHT=RHT
Hamming码: 
码长：n=2m-1
信息位数：k=2m-m-1
监督码位：r=n-k=m
最小距离：d=3
纠错能力：t=1
基本码限： 

Singleton限： 任一线性分组码的最小距离(或最小重量)d0均满足d0≤n-k+1。

Hamming限：  若C是k维n重二元码，已知k时，要使C能纠正t个错，则必须有不少于r个校验位，并且使r满足2r-1≥∑ti=1Cin。

循环码： 

在任一个GF(q)(q为素数或素数幂)上的n维线性空间Vn中，一个n重子空间Vn,k∈Vn，若对任何一个Ci=(cn-1，cn-2，…，c0)∈Vn,k，恒有C′i=(cn-2 …c0cn-1)∈Vn,k，则称Vn,k是循环子空间或循环码。

如果一个码的所有码多项式都是多项式g(x)的倍式，则称g(x)为生成该码，且称g(x)为该码的生成多项式，所对应的码字称为生成子或生成子序列。

BCH码： 

常用的二元BCH码是本原BCH码，其参数及其关系式：  
码字长度：n=2m-1
校验位数：n-k≤mt
最小距离：d≥2t+1

其中，m为正整数，一般m≥3，纠错位数t<(2m-1)/2。

RS码： 

RS码是一类具有很强纠错能力的非二进制BCH码，码元符号取自有限域GF（q）能纠正t个错误的RS码具有如下参数： 
码字长度：n=q-1(符号)
校验位数：n-k=2t(符号)
最小距离：d=2t+1(符号)
卷积码的定义： 编码器的输出c(j)是输入u和冲激响应g(j)的卷积，即有
c(j)=u○ *g(j)
时域里的卷积运算对应变换域里的乘积运算，上述方程还可以重新写成
c(j)(D)=u(D)g(j)(D)
其中，D的多项式系数是对应向量的元素，所以g(1)(D)=1+D+D2,g(2)(D)=1+D2，等价于单位离散时间延迟算子z-1。





卷积码的代数描述： 对于一个二元卷积码C，码字c(D)∈C有如下形式，即
c(D)=［c(1)(D)c(2)(D)…c(n)(D)］
式中： c(j)(D)=∑∞i=rc(j)iDi。

其编码过程可写为
c(D)=u(D)G(D)
其中，u(D)=［u(1)(D)u(2)(D)…u(k)(D)］，基向量gi(D)=［g(1)i(D)g(2)i(D)…g(n)i(D)］构成了k×n的生成矩阵G(D)的行，即G(D)中第i行第j列的元素是g(j)i(D)。

最大似然序列译码(MLSD)：

对于BSC(BIAWGNC)，MLSD将会选择在汉明(欧几里得)距离的意义下最接近信道输出y的码字序列c。从理论上来说，可以利用穷搜索的办法在网格图上寻找最接近y的序列。

维特比（Viterbi）译码： 基于幸存路径，开展加比选(AddCompare Select，ACS)迭代的译码算法(算法5．5．1)。

习题

5．1在一个p=0．05的BSC上，使用长度n=5的分组码，并希望接收端分组错误概率小于10-4，最大可能的码率为多少？


5．2已知一个(7,4)码的生成矩阵为
G0=1000111010010100100110001110
(1) 求该码的全部码字。

(2) 求该码的一致校验矩阵H0。

(3) 作出标准阵列译码表。

5．3一个(8,4)系统码，其信息序列为(m3m2m1m0)，码字序列为(c7c6c5c4c3c2clc0)，它的校验方程为
c3=m3+m1+m0
c2=m3+m2+m0
c1=m2+m1+m0
c0=m3+m2+m1
求该码的生成矩阵G0和一致校验矩阵H0，并证明该码最小重量为4。

5．4令H为某一(n,k)线性分组码的一致校验矩阵，其码的最小重量d0为奇数，现构造一个新码，其一致校验矩阵为


H′=H001…11




试证明： (1) 新码是一个(n+1,k)码。

(2) 新码中每个码字重量为偶数。

(3) 新码的最小重量为d0+1。

5．5对于一个码长为15的线性码，若允许纠正2个随机错误，需多少个不同的伴随式？至少要多少位校验元？

5．6令C1是最小距离为d1、生成矩阵为G1=［P1┊Ik］的(n1,k)线性系统码，C2是最小距离为d2、生成矩阵G2=［P2|Ik］的(n2,k)线性系统码。研究具有下述一致校验矩阵的线性码。
H=PT1In1+n2-kIkPT2

试求： (1) 码长及信息位长度。

(2) 证明此码的最小距离至少为d1+d2。

5．7研究一(n,k)线性码C，其生成矩阵G不包括零列。将C的所有码矢排列成2k×n的阵，试证明： (1)阵中不含有零列。

(2) 阵的每一列由2k-1个0和2k-1个1组成。

(3) 在特定分量上为0的所有码矢构成C的一个子空间，这个子空间的维数有多大？

5．8证明(n,k)线性码的最小距离d0满足下述不等式：
d0≤n·2k-12k-1
提示： 利用题5．7(2)的结果，上述界限称为普洛金(Plotkin)限。

5．9已知(7,4)码的全部码字为： 0000000，0001011，0010110，0011101，0100111，0101100，0110001，0111010，1000101，1010011，1011000，1100010，1101001，1110100，1111111，1001110。

(1) 该码是否为循环码？为什么？

(2) 写出该码的生成多项式g(x)及标准型的生成矩阵G0。

(3) 写出标准型的一致校验矩阵H0。

5．10证明x10+x8+x5+x4+x2+x+1为(15,5)循环码的生成多项式，并写出信息多项式为M(x)=x4+x+1时的码多项式(按系统码的形式)。

5．11一个(n,k)循环码，其生成多项式为g(x)。假设n为奇数，且x+1不是g(x)的因式，试证全1码组是其中的一个码字； 若(x+1)是g(x)的一个因式，证明全1的n重不是码字； 若n是偶数，证明全1的n重是一个码字。

5．12已知g1(x)=x3+x2+1，g2(x)=x3+x+1，g3(x)=x+1，试分别讨论： 

(1) g(x)=g1(x)g2(x)。

(2) g(x)=g3(x)g2(x)。

两种情况下，由g(x)生成的7位循环码能检测出哪些类型的单个错误和突发错误？

5．13令(15,11)循环码的生成多项式为g(x)=x4+x+1。

(1) 求此码的一致校验多项式。

(2) 求此码的标准型的生成矩阵和一致校验矩阵。

(3) 讨论其纠错能力。

(4) 若信息序列多项式为M(x)=x10+x8+1，求其编码后的系统型码字。

(5) 求接收码组R(x)=x14+x4+x+1的伴随式，并列表说明R(x)的译码过程。

5．14令g(x)是一个长为n的二元循环码的生成多项式。

(1) 若g(x)中有(x+1)因子，证明此码不含有奇数重量码字。

(2) 若n是g(x)除尽xn+1的最小整数，且n≥3，证明此码的重量至少为3。

5．15令Cl和C2分别是g1(x)和g2(x)生成的两个长为n的循环码，其最小距离分别为d1，d2，证明既属于Cl码又属于C2码的公共码多项式，形成了另一循环码C3，确定C3码的生成多项式，试讨论C3码的最小距离。

5．16扩展Hamming码扩展后的一致校验矩阵H′与原码H矩阵关系如下:

H′=0
0

0

 1111…1

  H

同样，删信Hamming码的一致校验矩阵H″与原码H矩阵关系如下


H″=

 11…1

H

计算这两类码的维数，证明dmin=4； 试说明扩展和删信Hamming码可以纠正单个错误同时检测2个错误。

5．17下列码中哪些与BCH码的规则一致？

(1) (32，21)dmin=5

(2) (63，45)dmin=7

(3) (63，36)dmin=11

(4) (127，103)dmin=7

5．18给出长度为15的可纠正3个错误的BCH码的生成子多项式。假设GF(24)是用本原多项式x4+x3+1构造的。

5．19构造一个GF(24)上n=15的纠正2个错误的RS码，找出它的生成多项式和k，并对接收矢量R(x)=αx3+α11x7进行译码。

5．20一个GF(2m)上的纠正t个错误的RS码，若它的生成多项式为
g(x)=(x+α)(x+α2)…(x+α2t) 
其中α∈GF(2m)是一个本原域元素，证明该码最小距离为2t+1。

5．21设(2,1,3)二元卷积码的生成多项式矩阵G(D)=［1+D2+D31+D+D2+D3］。

(1) 画出编码电路。

(2) 画出L=4的信息序列的网格图。

(3) 若通过转移概率p=0．01的BSC传送，收到的序列为11 10 00 01 10 00，求译码序列。

5．22考虑码率为2/3的卷积码，其校验矩阵为
H（D）=［h2(D)h1(D)h0(D)］
=［1+D1+D21+D+D2］
证明这个码的其中一个生成矩阵为
G（D）=h1(D)h2(D)0
0h0(D)h1(D)

5．23假设在BIAWGNC下，仿真码率为2/3的卷积码的Viterbi译码，其校验矩阵如下:
H（D）=［h2(D)h1(D)h0(D)］
=［1+D1+D21+D+D2］
画出Pb为10-1~10-6的误码率。