通信原理-第11章差错控制编码附简介第10章

第十章 数字信号的最佳接收（自学）,自学指导：最佳接收准则：不同的通信系统，采用的最佳接收准则不同，如模拟通信系统，常用最小均方误差准则；数字通信系统，常用最小差错概率（误码率）准则等等。最佳接收是相对的，是在一定条件下，针对某种类型信号，根据某个准则得出的最佳。必须注意何种条件？何种准则？何种信号？,第十一章 差错控制编码 （纠错编码）,11.1 引言11.2 纠错编码的基本原理11.3 简单的实用编码11.4 线性分组码11.5 循环码11.6 卷积码,概述,信道分类：按照加性噪声造成误码的统计特性随机信道/误码：由随机噪声引起，它的出现是随机的，错误码元之间彼此独立，互不相关突发信道/误码：由突发噪声（干扰、快衰落等）引起，错误码元之间有很强的相关性，常常成片出现混合信道/误码：既存在随机错码又存在突发错码如何减少误码？从信源编码，误码引起的性能恶化尽可能小，采用容错技术。从传输系统，可采用抗干扰能力强的调制方式，信道特性不理想可采用均衡技术。数字通信中，特别需要差错控制技术，通常要求误码率10-8以下，必须采用差错控制方法。,信道编码（Channel Coding）：,信道编码是使无规律性或规律性不强的原始信号变换为有规律性或规律性加强的数字信号，信道译码器利用这些规律性来鉴别传输过程信号是否发生错误，甚至能够纠正错误。信道编码可分为纠错编码和正交编码两大类。纠错编码的规律性体现在各码组的码元之间；正交编码的规律性体现在码组之间的正交性。这两类编码关系密切，有些正交编码也是纠错编码。信道编码是以降低信息传输速率为代价来减少误码率，也可以说是降低系统的有效性来增强系统的可靠性。,信道由加性干扰引起的错码分类：,差错控制编码又称为信道编码，其目的是消除信息传输过程中由于信道噪声（加性干扰）引起的误码。随机信道（无记忆信道）：错码的发生是随机错误，发生的位置是随机的，且数字序列中前后之间发生的错误相互独立，多数情况下是独立的单个数据发生错误。这种以随机错误为主的信道称为随机信道，如白噪声引起的错码。突发信道（有记忆信道）：在某些时间区间内错误发生是突发出现的，而在其它时间区间内又存在较长的无错码区间。以这种突发错误为主的信道称为突发信道，产生突发错码的主要原因是脉冲干扰和信道中存在衰落现象。混合信道：同时存在随机错码和突发错码的信道。对于不同类型的信道，必须采用不同的信道编码技术。一般地，纠正随机差错的编译码方法和设备比较简单，成本较低，效果较显著；而纠正突发差错的编译码方法和设备比较复杂，成本较高，效果也不如前者显著。,差错控制方法：,检错重发法（ARQ：自动要求重发），反馈（判决）重发法：发送端发送检错码，接收端判决码组中有无错误，再把判决信号通过反馈信道送到发送端，若发现有错码时，则发送端重发，直到正确接收为止。需要反向通道，实时性差。前向纠错法（FEC），自动纠错法：接收端不仅能在收到的信码中发现错码，还能够确定错码位置，纠正错码。特点是实时性好，但译码方法和设备较复杂。信息反馈法（IF），反馈校验法：接收端将收到的信码原封不动地转发回发送端，发送端将其与原发送信码比较，如果发现错误，则重发。无需纠（检）错码，但需要反馈信道且传输速率低。混合纠错法（HEC）：是ARQ和FEC的混合。发送端发送纠（检）错码，接收端自动发出判决信号到发送端，若发现有错码时，则发送端仅重发有错码的信息，达到正确接收目的。,差错控制方法示意图：,差错控制方法应用：,检错重发法（ARQ）、前向纠错法（FEC）、信息反馈法（IF）和混合纠错法（HEC）都得到了广泛应用。当出现少量错码，且在接收端能够纠正时，往往采用前向纠错法（FEC）。当出现较多错码，但能够及时检测时，往往采用检错重发法（ARQ）或信息反馈法（IF）。在复杂的短波信道和散射信道中，常采用混合纠错法（HEC）。,自动要求重发系统ARQ系统：,（Automatic Report reQuest） 纠错编码虽然优点显著，但实现复杂；传输效率（有效性）低。检错编码原理简单，易于实现，已得到广泛应用，ARQ系统也称为检错重发法，可以达到纠错目的。,ARQ系统的工作过程：,图(a)为停发等候重发法；图(b)为返回重发法；图(c)为选择重发法。,ARQ系统的工作过程说明：,停止等待ARQ系统 数据分组发送。每发送一组数据后发送端等待接收端的确认(ACK)答复，然后再发送下一组数据。接收数据有误，接收端发回一个否认(NAK)答复。这时，发送端将重发数据。系统是工作在半双工状态，时间没有得到充分利用，传输效率较低。返回重发ARQ系统发送端连续发送数据组，接收端对于每个接收到的数据组都发回确认(ACK)或否认(NAK)答复。 如第2组接收数据有误，则在发送端收到第5组接收的否认答复后，从第2组开始重发数据组。在这种系统中需要对发送的数据组和答复进行编号，以便识别。显然，这种系统需要双工信道。,ARQ系统的工作过程说明：,选择重发ARQ系统它只重发出错的数据组，因此进一步提高了传输效率系统是工作在半双工状态，时间没有得到充分利用，传输效率较低。ARQ系统接收端仅当解码器认为接收信息码元正确时，才将信息码元送给收信者，否则在输出缓冲存储器中删除接收码元当解码器未发现错码时，经过反向信道发出不需重发指令。发送端收到此指令后，即继续发送后一码组，发送端的缓冲存储器中的内容也随之更新,ARQ系统特点：,主要优点：（1）只需要少量的冗余码，就可以得到极低的输出误码率，即码率较高； （2）检错的计算复杂度较低； （3）检错用的编码方法和加性干扰的统计特性基本无关，有一定的自适应能力 主要缺点：（1）需要反向信道，故不能用于单向传输系统，也不能用于一点到多点的通信系统，并且实现重发控制比较复杂； （2）通信效率低，不适合严格实时传输系统，如电话通信；（3）在信道干扰严重时，可能发生因不断反复重发而造成事实上的通信中断,差错控制编码（纠错编码）：,在信息码元序列中附加一些监督码元就称为差错控制编码，也称为纠错编码。 Shannon信道编码定理是其理论依据。这些监督码元与信息码元之间以某种确定的规则相互关联，接收端按照这种规则检验监督码元与信息码元间的关系，一旦传输过程发生错码，则监督码元与信息码元间的规则关系受到破坏，从而发现错码或给予纠正。不同的编码方法，有不同的检错或纠错能力。一般说来，编码中增加的监督码元越多，检（纠）错的能力就越强，但信道的传输速率会下降越多，即以有效性换取可靠性。,差错控制编码（纠错编码）分类：,根据监督码元与信息码元之间的函数关系，分为线性码和非线性码。根据监督码元与信息码元之间的约束关系，分为分组码和卷积码。根据差错控制编码的功能，分为检错码和纠错码。根据纠正差错的类型，分为纠（检）随机错误码和纠（检）突发错误码。根据码元取值，分为二进制码和多进制码。根据差错控制编码的数学方法，分为代数码、几何码和算术码。,差错控制编码（纠错编码）分类：,按照信息码元在编码后是否保持原来的形式，可以将它分为系统码和非系统码。 随着数字通信系统的发展，可以将信道编码器和调制器统一起来综合设计，这就是网格编码调制。能够节省发送功率和带宽。,11.2 纠错编码的基本原理,例11.2.1：,000(晴) 001(云) 010(阴) 011(雨) 100(雪) 101(霜) 110(雾) 111(雹)该编码无检错纠错能力,000(晴) 011(云) 101(阴) 110(雨)增加了一位冗余码元，编码具有检出一位错码的能力，但无纠错能力。,000(晴) 111(雨)增加两位冗余码元，编码具有检出一位错码及纠正一位错码的能力。,例：差错控制编码的基本原理说明,用三位二进制编码代表八个字母：000 A100E001 B101F010C110G011D111H不管哪一位发生错误，都会使传输字母错误用三位二进制编码代表四个字母：000 A011B101 C110D发生一位错误，准用码字将变成禁用码字，接收端就能知道出错，但是不能纠错。,例：差错控制编码的基本原理说明,如用三位二进制编码代表二个字母000 A111B检出三个错误（发生一位错误），同时纠正一个错误（发生一位错误） 。结论：具有检错或纠错的码组，其所用的比特位数必须大于信息码组原来的比特位数需要引入冗余度。,香农定理差错控制编码的理论基础：,香农定理（编码定理）：存在噪声干扰的信道，若信道容量为C，只要发送端以低于C的信息传输速率R发送信息，则一定存在一种编码方式，使编码的错误概率随着码长n的增加按指数下降到任何值。结论：如码长及发送信息速率一定，可以通过增大信道容量，使错误概率P减小。如在信道容量及发送信息速率一定，可以通过增加码长，使错误概率P下降。,纠错编码几个基本概念：,分组码：将信息码分组，为每组信息码附加若干监督码的编码集合。码长：一个码组中的码元数目。码重W（汉明重量）：一个码组中非零位的个数。码距d：两个等长码组之间对应位不同的个数。最小码距d0是码组集合中，所有码距的最小值。抗干扰能力与最小码距d0密切相关。即2个码组对应位模2的重量。分组码表示符号(n,k)：n是码组总位数，k是信息码位数。编码效率R： R=k/n,纠错编码基本概念说明：,在分组码中，把“1”的数目称为码组的重量（码重），而把两个码组对应位上数字不同的位数称为码组的距离，称为码距或汉明(Hamming)距离。某种编码中各个码组间距离的最小值称为最小码距（d0）。它直接关系到编码的检错和纠错能力，是信道编码一个重要参数。,编码效率R：,最小码距d0越大，码的抗干扰能力越强，即检（纠）错能力越强，但编码效率R越低。反之，编码效率R越高，检（纠）错能力就要降低。需要寻找有效的编码方案，不但希望抗干扰能力强，而且编码效率R高，具体设计需要全面考虑。,例：码重、码距的计算,两个码组的码重和码距（汉明距离）：10 1 1 0 码重：301 1 0 0 2 码组的码距=3码重(weight)一个码组中“1”的数目（二进制）码距(distance)两个码组之间对应位置上1、0不同的位数（汉明距离）。,分组码说明：,分组码一般用符号(n,k)表示，其中k是每组二进制信息码元的数目，n是编码组的总位数，又称为码组长度（码长），n-k=r为每码组中的监督码元数目，或称监督位数目。,an-1,an-2,ar,ar-1,a0,k个信息位,r个监督位,码长n=k+r,分组码的纠错和检错能力：,（1）为检测e个错码，要求最小码距 d0e+1（对应于ARQ）（2）为纠正t个错码，要求最小码距 d02t+1 （对应于FEC）（3）为纠正t个错码，同时检测e个错码，要求最小码距 d0e+t+1 （对应于HEC） 对例11.2.1中三位二进制码组，若8种码组均为有效（许用）码组时，d0=1；若选用4种码组为有效码组时，d0=2；若选用2种码组为有效码组时，d0=3。一种编码的最小码距d0的大小直接关系着这种编码的检错和纠错能力。,码距与检错、纠错能力的几何关系：,码距越大，说明码字间的最小差别越大，抗干扰能力就越强。,码距和检纠错能力关系说明：,为检测e个错码，要求最小码距 d0 e + 1证：设一个码组A位于O点。若码组A中发生一个错码，则可以认为A的位置将移动至以O点为圆心，以1为半径的圆上某点，但其位置不会超出此圆。 若码组A中发生两位错码，则其位置不会超出以O点为圆心，以2为半径的圆。因此，只要最小码距不小于3，码组A发生两位以下错码时，不可能变成另一个准用码组，因而能检测错码的位数等于2。同理，若一种编码的最小码距为d0，则将能检测(d0 - 1)个错码。反之，若要求检测e个错码，则最小码距d0至少应不小于( e + 1)。,码距和检纠错能力关系说明：,为了纠正t个错码，要求最小码距d0 2t + 1证：图中码组A和B的距离为5。码组A或B若发生不多于两位错码，则其位置均不会超出半径为2以原位置为圆心的圆。这两个圆是不重叠的。判决规则为：若接收码组落于以A为圆心的圆上就判决收到的是码组A，若落于以B为圆心的圆上就判决为码组B。这样，就能够纠正两位错码。若这种编码中除码组A和B外，还有许多种不同码组，但任两码组之间的码距均不小于5，则以各码组的位置为中心以2为半径画出之圆都不会互相重叠。这样，每种码组如果发生不超过两位错码都将能被纠正。因此，当最小码距d05时，能够纠正2个错码，且最多能纠正2个。若错码达到3个，就将落入另一圆上，从而发生错判。故一般说来，为纠正t个错码，最小码距应不小于(2t + 1) 。,码距和检纠错能力关系说明：,为纠正t个错码，同时检测e个错码，要求最小码距证：在解释此式之前，先来分析下图所示的例子。图中码组A和B之间距离为5。按照检错能力公式，最多能检测4个错码，即e = d0 1 = 5 1 = 4，按照纠错能力公式纠错时，能纠正2个错码。但是，不能同时作到两者，因为当错码位数超过纠错能力时，该码组立即进入另一码组的圆内而被错误地“纠正”了。例如，码组A若错了3位，就会被误认为码组B错了2位造成的结果，从而被错“纠”为B。这就是说，检错和纠错公式不能同时成立或同时运用。,码距和检纠错能力关系说明：,为了在可以纠正t个错码的同时，能够检测e个错码，如下图所示，使某一码组（如码组A）发生e个错误之后所处的位置，与其他码组（譬如码组B）的纠错圆圈至少距离等于1，不然将落在该纠错圆上从而发生错误地“纠正”。因此，由此图可以直观看出，要求最小码距这种纠错和检错结合的工作方式简称纠检结合。这种工作方式是自动在纠错和检错之间转换的。当错码数量少时，系统按前向纠错方式工作，以节省重发时间，提高传输效率；当错码数量多时，系统按反馈重发方式纠错，以降低系统的总误码率。所以，它适用于大多数时间中错码数量很少，少数时间中错码数量多的情况。,例：纠错编码的应用效果。,假设随机信道中发送“0”码与发送“1”码错误概率相等为Pe，且Pe1，则在码长为n的码组中发生r个错码的概率为 Pn(r) = Cnr Per(1- Pe)n-r n!/r!(n-r)! Per 当码长n=7，Pe=10-3时，则有 P7(1) 7Pe = 710-3 P7(2) 21Pe2 = 2.110-5 P7(3) 35Pe3 = 3.510-8 采用纠错编码后，即使仅能检测或纠正码组中12个错误，也能够使误码率下降几个数量级。即既使简单的纠错编码也具有较大的实用价值。,对纠错编码的基本要求：,最小码距d0越大，纠错编码的检错和纠错能力越强。随着监督码元（冗余码元）的增加，信息传输速率会大大降低。通常用编码效率R（码率）作为衡量信道编码又一个重要参数。它表示一个码组中信息位所占比重，R=k/n，其中k为信息码元数，n为码长。码率越高，传信率越高，但纠错能力降低。纠错编码的基本要求：检错和纠错能力尽量强，码率尽量高，码长尽量短，编码规律尽量简单。在实际应用中，需要根据系统具体指标，保证具有一定的纠错能力和码率时，经济且易于实现。,纠错编码的性能：,系统带宽和信噪比的矛盾：在发送信息码元序列中加入监督码元，则发送序列增长，冗余度增大。若仍须保持发送信息码元速率不变，则传输速率必须增大，因而增大了系统带宽。系统带宽的增大将引起系统中噪声功率增大，使信噪比下降。信噪比的下降反而又使系统接收码元序列中的错码增多。一般说来，采用纠错编码后，误码率总是能够得到很大改善的。改善的程度和所用的编码有关。,纠错编码的性能：,编码性能：未采用纠错编码时，若接收信噪比等于7dB，编码前误码率约为810-4，图中A点；在采用纠错编码后，误码率降至约410-5，图中B点。这样，不增大发送功率就能降低误码率约一个半数量级。,纠错编码的性能：,若保持误码率在10-5，未采用纠错编码时，图中C点约需要信噪比Eb / n0 = 9.5 dB（每比特码元能量Eb和噪声单边功率谱密度之比）采用纠错编码时，图中D点约需要信噪比7.5 dB。可以节省功率2 dB。通常称这2 dB为编码增益。付出的代价是带宽增大。,纠错编码的性能：,传输速率和Eb/n0的关系对于给定的传输系统式中RB为码元速率。若希望提高传输速率，由上式势必使信噪比下降，误码率增大。假设系统原来工作在图中C点，提高速率后由C点升到E点。但加用纠错编码后，仍可将误码率降到D点。付出的代价仍是带宽增大。,11.3 简单的实用编码,奇偶监督码二维奇偶监督码恒比码正反码,11.3.1 奇偶监督码（奇偶校验码）,奇偶监督码可分为奇监督码和偶监督码两种，两者的原理相同，是最简单的检错码。在偶（奇）数监督码中，无论信息位有多少 ，监督位只有一位，它使码组中“1”的个数为偶（奇）数，即满足： an-1 an-2 a0=0（或1） 其中a0为监督位，其它为信息位，为模2和。在接收端，将码组中各码元模2相加，若结果为1（或0）就说明存在错码，为0（或1）就认为无错。奇偶监督码只能够发现单个或奇数个误码，不能检测出偶数个误码，最小码距d0=2，检错能力有限。编码效率R高，属于线性分组码（系统码）。可以应用在以随机错误为主的计算机通信系统，但难于对付突发错误。,奇偶监督码的编码可以用软件实现，也可用硬件电路实现。 如果码组B无错，BA，则M0；如果码组B有单个（或奇数个）错误，则M1。,11.3.2 二维奇偶监督码（方阵码）,二维奇偶监督码又称方阵码。将若干码组排列成矩阵（方阵），每一码组写成一行，对每一行和每一列都进行奇偶校验。形成了一行监督位码和一列监督位码，即增加了一列监督位码，构成二维行列奇偶监督码。它能够发现每一行和每一列上的所有奇数个误码，也能够检测出大部分偶数个误码，检错能力明显增强。适用于检测突发错误，通常可使误码率降到原误码率的1%0.01%，但对于构成的四角错码无法检测。,二维奇偶监督码不仅可用来检错，它能够检测出不大于行数（或列数）的突发错误；同时还可以纠正一些错码。,11.3.3 恒比码（等重码，等比码）,在恒比码中，每个码组均含有相同数目的“1”（和“0”），即“1”的数目和“0”的数目之比保持恒定。这种码在检测时，只要计算接收码组中“1”的数目是否对，就知道有无错误。恒比码的主要优点是简单，适用于传输电传机或其它键盘设备产生的字母和符号，不适合使用在信源为二进制的随机数字序列。国际电报通信系统采用3个“1”4个“0”的恒比码（7中取3码；3：4码）， C73= C74= 35个码组表示26个大写字母和其它符号。,“5中取3”恒比码：,目前我国电报通信系统使用的“5中取3”恒比码（3个“1”2个“0”；3：2码），用C53= C52= 10个码组表示10个阿拉伯数字，每个汉字是以4位十进制表示的，提高十进制数字传输的可靠性，相当于提高汉字传输的可靠性，实践证明非常有效。,11.3.4 正反码,正反码是一种简单的能够纠正错码的编码。其监督位数目与信息位数目相同，监督码元与信息码元相同（是信息码的重复）或者相反（是信息码的），取决于信息码中“1”的个数（奇数或偶数） 。电报通信系统采用了长度为10的正反码，具有纠正一位错码的能力，并能检测全部两位以下的错码和大部分两位以上的错码。其编码规则为： 当码组中信息码元有奇数个“1”，监督码是信息码的重复；当码组中信息码元有偶数个“1”，监督码是信息码的反码。,电报通信采用的10位正反码：,码长n=10位，其中信息位k=5，监督位r=5。编码规则为：（1）当信息位中有奇数个“1”时，监督位是信息位的简单重复；（2）当信息位有偶数个“1”时，监督位是信息位的反码。解码方法：先将接收码组中信息位和监督位按位模2相加，得到一个5位的合成码组，然后，由此合成码组产生一校验码组。若接收码组的信息位中有奇数个“1”，则合成码组就是校验码组；若接收码组的信息位中有偶数个 “1”，则取合成码组的反码作为校验码组。最后，观察校验码组中“1”的个数，按规则进行判决及纠正可能发现的错码。,由校验码组判决错码及纠正规则：,例：发送码组为11001,11001,接收码组为11001,11001，合成码组为1100111001 =00000，由于接收码组信息位中有奇数个“1”，所以校验码组就是00000，无错码。接收码组为10001,11001，合成码组为10001 11001 =01000，由于接收码组中信息位有偶数个“1”，所以校验码组应取合成码组的反码，即10111，信息码第二位为错码（与第2种情况相同）。接收码组为11001,01001，则合成码组为10000，校验码组与第3种情况相同，监督位中第一位为错码。接收码组为10011,11001，则合成码组为01010，校验码组与第4种情况相同，信息码中错码多于1个。,例：ISBN：国际标准图书编号检错码,ISBN：国际标准图书编号(International Standard Book Number)，也是一种检错码。如ISBN 7-118-04607-8，第一部分：国家编码；第二部分：出版公司编码；第三部分：书名编码；最后第四部分：校验位（可用罗马字表示）。前九位数字依次分别乘以10到 2 ，将其乘积相加，11减去余数（模11运算）得到。,11.4 线性分组码（群码）,基本概念代数码：建立在代数学基础上的编码。线性码：按照一组线性方程构成的代数码。在线性码中信息位和监督位是由一些线性代数方程联系着的。线性分组码：按照一组线性方程构成的分组码 。,11.4 线性分组码（群码）,线性分组码：信息位和监督位满足一组线性方程，即其编码规则可用一组线性方程来描述的分组码，通常用于前向纠错。线性码是建立在数学群论基础上的，线性码中许多码组的集合构成群码。线性码具有一些重要性质： 封闭性：线性码中的任意两个码组之和（模2和）仍为该码中的一个码组。 两个码组间的码距必定是另一码组的码重。即最小码距（d0）=非零码组的最小码重。由此能够知道该码的纠（检）错能力。,例：奇偶监督码。,偶数监督码：an-1、 an-2 、a1为信息位， a0为监督位，则校正子 S = an-1 an-2 a1 an-1+ an-2 + a1 + a0 = 0（ “+”为模2加） 奇数监督码： an-1+ an-2 + a1 + a0 = 1上式满足线性方程式，故奇偶监督码属于线性分组码。,1 汉明码：,是能够纠正1位错码且编码效率最高的（n,k）线性分组码，d0具有最小值。汉明码的构造原理在偶数监督码中，由于使用了一位监督位a0，它和信息位an-1 a1一起构成一个代数式：在接收端解码时，实际上就是在计算若S = 0，就认为无错码；若S = 1，就认为有错码。则将上式称为监督关系式，S称为校正子。由于校正子S只有两种取值，故它只能代表有错和无错这两种信息，而不能指出错码的位置。,1 汉明码：,若监督位增加一位，即变成两位，则能增加一个类似的监督关系式。由于两个校正子的可能值有4中组合： 00，01，10，11，故能表示4种不同的信息。若用其中1种组合表示无错，则其余3种组合就有可能用来指示一个错码的3种不同位置。同理，r个监督关系式能指示1位错码的(2r 1)个可能位置。一般来说，若码长为n，信息位数为k，则监督位数rnk。如果希望用r个监督位构造出r个监督关系式来指示1位错码的n种可能位置，则要求如何具体构造这些监督关系式？,（7，4）汉明码：,例：设分组码(n, k)中k = 4，为了纠正1位错码，由上式可知，要求监督位数 r 3。若取 r = 3，则n = k + r = 7。我们用a6 a5 a0表示这7个码元，用S1、S2和S3表示3个监督关系式中的校正子，则S1、S2和S3的值与错码位置的对应关系可以规定如下表所列：,（7，4）汉明码的监督关系：,由表中规定可见，仅当一位错码的位置在a2 、a4、a5或a6时，校正子S1为1；否则S1为零。这就意味着a2 、a4、a5和a6四个码元构成偶数监督关系：S1= a6a5a4a2= a6+a5+a4+a2 = 0（ “+”为模2加 ）S2= a6a5a3a1= a6+a5+a3+a1 = 0S3= a6a4a3a0= a6+a4+a3+a0 = 0,（7，4）汉明码：,在发送端编码时，信息位a6、a5、a4和a3的值决定于输入信号，因此它们是随机的。监督位a2、a1和a0应根据信息位的取值按监督关系来确定，即监督位应使上3式中S1、S2和S3的值为0（表示编成的码组中应无错码），上式经过移项运算，解出监督位。编码记为a6a5a4a3a2a1a0，其中a6、a5 、a4、a3为信息位，a2 、a1 、a0为监督位， a2= a6 a5 a4 = a6+a5+a4 a1= a6 a5 a3 = a6+a5+a3 a0= a6 a4 a3 = a6+a4+a3给定信息位后，可以直接按上式算出监督位。,（7，4）汉明码编码表：n=7,k=4,r=3,（7，4）汉明码小结：,接收端收到每个码组后，先计算出S1、S2和S3，再查表判断错码情况。例如，若接收码组为0000011，按上述公式计算可得：S1 = 0，S2 = 1，S3 = 1。由于S1 S2 S3 等于011，故查表可知在a3位有1错码。按照上述方法构造的码称为汉明码。表中所列的(7, 4)汉明码的最小码距d0 = 3。因此，这种码能够纠正1个错码或检测2个错码。由于码率k/n = (n - r) /n =1 r/n，故当n很大和r很小时，码率接近1。可见，汉明码是一种高效码。汉明码是一种能够纠正1位错误且编码效率最高的线性分组码。 d0 = 3,汉明码的编码说明：,汉明码能纠正一个错码或检测两个错码，要求 2r-1n 或2rk+r+1汉明码的编码效率为 R= K/n=(2r-1-r)/(2r-1)=1-r/(2r-1)=1-r/n 对（7，4）汉明码，编码效率为4/757%，与相同码长，具有纠正一位错码的其他分组码相比，该码效率最高，且实现简单。n，R1，汉明码是一种高效码。其最小码距为3，能纠正一个错码或检测两个错码。若收到码组0000011，按监督方程计算可得：S1=0，S2=1，S3=1；再根据校正子S的组合与一位错码位置的对应关系，查表可知错码发生在a3位，可予以纠正。,（7，4）系统汉明码的编码器和译码器电路：,2 线性分组码的一般原理：,线性分组码的构造H矩阵上面(7, 4)汉明码的例子有现在将上面它改写为上式中已经将“”简写成“+”。,线性分组码的一般原理：,上式可以表示成如下矩阵形式：上式还可以简记为H AT = 0T 或A HT = 0,监督矩阵H ：,H AT = 0T 或A HT = 0式中A = a6 a5 a4 a3 a2 a1 a00 = 000HT是H的转置矩阵，将H称为监督矩阵。 只要监督矩阵H为r n阶矩阵给定，编码时监督位和信息位的关系就完全确定了。,监督矩阵H的性质：,1) H的行数就是监督关系式的数目，它等于监督位的数目r。H的每行中“1”的位置表示相应码元之间存在的监督关系。例如，H的第一行1110100表示监督位a2是由a6 a5 a4之和决定的。H矩阵可以分成两部分，例如 式中，P为r k阶矩阵，Ir为r r阶单位方阵。将具有P Ir形式的H矩阵称为典型阵。,H矩阵的性质：,2) 由代数理论可知，H矩阵的各行应该是线性无关的，否则将得不到 r个线性无关的监督关系式，从而也得不到 r个独立的监督位。若一矩阵能写成典型阵形式P Ir，则其各行一定是线性无关的。因为容易验证Ir的各行是线性无关的，故P Ir的各行也是线性无关的。G矩阵：上面汉明码例子中的监督位公式为也可以改写成矩阵形式：,生成矩阵G ：,或者写成式中Q为一个k r阶矩阵，它为P的转置，即 Q = PT 上式表示，在信息位给定后，用信息位的行矩阵乘矩阵Q就产生出监督位。,生成矩阵G ：,将Q的左边加上1个k k阶单位方阵，就构成矩阵G G称为生成矩阵，因为由它可以产生整个码组，即有或者因此，如果找到了码的生成矩阵G，则编码的方法就完全确定了。具有IkQ形式的生成矩阵称为典型生成矩阵。由典型生成矩阵得出的码组A中，信息位的位置不变，监督位附加于其后。这种形式的码称为系统码。 M为信息位矩阵。,生成矩阵G的性质：,1) G矩阵k n的各行是线性无关的。因为由上式看出，任一码组A都是G的各行的线性组合。G共有k行，若它们线性无关，则可以组合出2k种不同的码组A，它恰是有k位信息位的全部码组。若G的各行线性相关，则不可能由G生成2k种不同的码组了。2) 实际上，G的各行本身就是一个码组。因此，如果已有k个线性无关的码组，则可以用其作为生成矩阵G，并由它生成其余码组。,监督矩阵H说明：,监督矩阵是rn阶矩阵，描述了监督位和信息位的关系，只要监督矩阵H给定，编码时监督位和信息位的关系就完全确定了。H的行数就是监督关系式的数目，它等于监督位的数目r，H的每行中“1”的位置表示相应码元之间存在的监督关系。当H=PIr时，称H为典型监督矩阵。式中P为rk阶矩阵，Ir为rr阶单位方阵。H矩阵的各行线性无关。,生成矩阵G说明：,生成矩阵G是kn阶矩阵，它描述了编码的方法（监督码和信息码关系），由它可以产生整个码组。即 A=a6a5a4a3a2a1a0=a6a5a4a3G=MG若G=IkQ，则称G为典型生成矩阵。式中，Q=PT为kr阶矩阵，信息码组M为1k阶矩阵。由典型生成矩阵得出的码组中，信息位不变，监督位附加于其后，这种码称为系统码。G矩阵的各行线性无关，每行均为许用码组。Q=PT或P=QT表明了监督矩阵和生成矩阵间关系。,线性分组码的矩阵特性描述小结：,关系式A=MG或者HAT=0完全确定了编码规律，从这一意义上两者之间是互相等价的。实际上编码问题就变为选择构造一个G矩阵或H矩阵的问题。A为码组矩阵（包括信息位和监督位），M为信息位矩阵。由于G矩阵完全确定了线性分组码的编码规律，由G矩阵便可生成线性分组码的全部码组，所以称G为线性分组码的生成矩阵。所有许用码组构成的向量满足HAT=0，称H矩阵为线性分组码的监督（校验）矩阵。H矩阵、G矩阵各行应该是线性无关的。,错码矩阵和错误图样：,一般说来，A为一个n列的行矩阵。此矩阵的n个元素就是码组中的n个码元，所以发送的码组就是A。此码组在传输中可能由于干扰引入差错，故接收码组一般说来与A不一定相同。若设接收码组为一n列的行矩阵B，即则发送码组和接收码组之差为B A = E (模2)它就是传输中产生的错码行矩阵 式中,错码矩阵和错误图样：,因此，若ei = 0，表示该接收码元无错；若ei = 1，则表示该接收码元有错。 B A = E 可以改写成 B = A + E例如，若发送码组A = 1000111，错码矩阵E = 0000100，则接收码组B = 1000011。错码矩阵有时也称为错误图样。,校正子S:,当接收码组有错时，E 0，将B当作A代入公式(A H T = 0)后，该式不一定成立。在错码较多，已超过这种编码的检错能力时，B变为另一许用码组，则该式仍能成立。这样的错码是不可检测的。在未超过检错能力时，上式不成立，即其右端不等于0。假设这时该式的右端为S，即B H T = S将B = A + E代入上式，可得S = (A + E) H T = A H T + E H T由于A HT = 0，所以S = E H T式中S称为校正子。它能用来指示错码的位置。S和错码E之间有确定的线性变换关系。若S和E之间一一对应，则S将能代表错码的位置。,例：偶数监督码的矩阵形式,an-1 an-2 a0=an-1 an-2 a1 G= = H=1 1 1,1 0 0 0 10 1 0 0 10 0 0 1 1,1 11,In-1,1 0 0 0 10 1 0 0 10 0 0 1 1,例：（15，11）汉明码的校验矩阵,H=其校验方程为 a14+a13+a12+a11+a9+a8+a5+a3=0 a14+a13+a12+a10+a9+a6+a4+a2=0 a14+a13+a11+a10+a7+a6+a5+a1=0 a14+a12+a11+a10+a8+a7 +a4+a0=0,1 1 1 1 0 1 1 0 0 1 0 1 0 0 0 1 1 1 0 1 1 0 0 1 0 1 0 1 0 0 1 1 0 1 1 0 0 1 1 1 0 0 0 1 0 1 0 1 1 1 0 1 1 0 0 1 0 0 0 1,（15，11）汉明码的生成矩阵：,G=,1 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 1 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 1 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 1 1 0 0 0 0 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1,11.5 循环码,所谓循环码（Cyclic Code）就是任何一个码组经过循环移位后所得到的码组仍是一个许用码组，也就是说这个码组在循环位移运算下具有封闭性。除具有线性分组码的性质外，还具有循环特性。具有这种循环特性的子空间称为循环子空间。循环码是线性分组码的一个重要子类，是最成熟的一类线性分组码，且为系统码。通常循环码用多项式表示，该多项式称为码多项式，它是在严密的代数学基础上建立的。,循环码,循环码是（n，k）线性分组码的一个重要子类。循环码是线性分组码中最有理论意义和实用价值的一种编码，编译码设备简单，且检（纠）错能力较强。循环码具有RS、BCH等高效子码类，实际应用广泛。,例：（7，3）循环码：第2码组对应于生成多项式g(x) 。例如，表中的第2码组向右移一位即得到第5码组；第6码组向右移一位即得到第3码组。,（7，3）循环码：构成两个循环圈,00000000010111 100101111001011110010 01011101011100 0111001,循环码的码多项式描述：,设码组A =（a0 , a1 , , an-1），把码组中各码元当作是一个多项式的系数，即把一个长度为n的码组表示成相应的码多项式 A(x) = an-1xn-1 + an-2xn-2+ + a1x+ a0其中x为实变量， x仅是码元位置的标记。向量和多项式之间具有如下的一一映射关系： （ an-1, an-2 , , a0 ） an-1xn-1 + an-2 xn-2+ + a0因此可使用码向量和码多项式两种表达方式来描述同一个码组，仅是表示方法不同而已。幂次为移位次数；加和乘的运算规则按照模2运算规则。第7个码组可以表示为,码多项式的按模运算：,在整数运算中，有模n运算。如在模2运算中，1 + 1 = 2 0 (模2)，1 + 2 = 3 1 (模2)， 2 3 = 6 0 (模2)一般说来，若一个整数m可以表示为式中，Q 整数，则在模 n 运算下，有 m p (模n)即模 n 运算下，一个整数m等于它被 n 除得的余数。,循环码的码多项式模运算：,码多项式运算中也有类似的按模运算。若一任意多项式F(x)被一 n 次多项式N (x)除，得到商式Q(x)和一个次数小于n的余式R(x)，即则写为这时，码多项式系数仍按模2 运算，即系数只取 0 和1。例如，x3被(x3 + 1)除，得到余项1。所以有同理因为,应当注意，由于在模2运算中，用加法代替了减法，故余项不是x2 x + 1，而是x2 + x + 1。,循环码的码多项式模运算特性：,在循环码中，若A(x)是一个长为n的许用码组，则xiA(x)在按模xn+1运算下，也是一许用码组。即若 xiA(x)Ai(x) （模xn+1） 则Ai(x) 也是一许用码组，且为A(x)码组向左循环移位i次的结果。一个长为n的(n，k)循环码，它必为按模xn+1运算的一个余式。,循环码的码多项式模运算特性：,证明：因为若则 （模(xn + 1)）所以，这时有上式中Ai (x)正是A(x)代表的码组向左循环移位i次的结果。因为原已假定A(x)是循环码的一个码组，所以Ai (x) 也必为该码中一个码组。,循环码的生成多项式g(x) ：,有了生成矩阵G，就可以由k个信息位得出整个码组，而且生成矩阵G的每一行都是一个码组。例如，若a6a5a4a3 = 1000，则码组A就等于G的第一行；若a6a5a4a3 = 0100，则码组A就等于G的第二行；等等。由于G是k行n列的矩阵，因此若能找到k个已知码组，就能构成矩阵G。而且这k个已知码组必须是线性不相关的，否则给定的信息位与编出的码组就不是一一对应的。在循环码中，一个(n, k)码有2k个不同的码组。若用g(x)表示其中前(k-1)位皆为“0”的码组，则g(x)，x g(x)，x2 g(x)，xk-1 g(x)都是码组，而且这k个码组是线性无关的。因此它们可以用来构成此循环码的生成矩阵G。,循环码的生成多项式g(x) ：,在循环码中除全“0”码组外，再没有连续k位均为“0”的码组，即连“0”的长度最多只能有(k - 1)位。否则，在经过若干次循环移位后将得到一个k位信息位全为“0”，但监督位不全为“0”的一个码组。g(x)必须是一个常数项不为“0”的(n - k)次多项式，而且这个g(x)还是这种(n, k)码中次数为(n k)的唯一多项式。因为如果有两个，则由码的封闭性，把这两个相加也应该是一个码组，且此码组多项式的次数将小于(n k)，即连续“0”的个数多于(k 1)。显然，这是与前面的结论矛盾的，故是不可能的。这种唯一的(n k)次多项式g(x)为码的生成多项式。确定了g(x)，则整个(n, k)循环码就被确定了。,循环码的生成多项式g(x)特性： 循环码中次数最低的码多项式称为生成多项式g(x) 。可以证明生成多项式g(x)具有以下特性： （1） g(x)是一个常数项为1的 次多项式； （2） g(x)是 的一个因式； （3）该循环码中其它码多项式都是g(x)的倍式。,循环码的生成矩阵G与生成多项式g(x)：,寻找构成生成矩阵Gkn的k个线性无关的许用码组。由封闭性可知循环码中一定包含全0码组。于是（n，k）循环码中一定能找到这样一个码组：前面的k-1位都是0，而第k位及第n位为1，其它各位gi为0或1：（00001 gn-k-1gn-k-2 g2 g11) 其对应的码多项式为g(x)，且 g(x)一定是码中唯一的一个n-k次多项式，g(x)称为码的生成多项式。根据循环性，xg(x)，x2 g(x)， ，xk-1g(x)都是许用码组，连同g(x)共k个许用码组，彼此线性无关，从而构成循环码的生成矩阵G(x)。,循环码的生成矩阵Gkn：,由生成矩阵G可以产生整个码组，且生成矩阵G的每一行都是一个码组。在循环码中，一个（n，k）码共有2k个不同码组。若选用前述的g(x)作为码的生成多项式，则循环码的生成矩阵为 生成矩阵G并不是典型矩阵，但可通过线性变换变换成典型的生成矩阵IkQ，Q为kr阶矩阵。,例：（7，3）循环码的生成矩阵G。,唯一的一个前二位皆为“0”的码组是0010111，相对应的g(x)=x4+x2+x+1，则 G = = 进行线性变换后，得到典型生成矩阵为 G =,x2g(x)xg(x) g(x),1 0 1 1 1 0 0 0 1 0 1 1 1 0 0 0 1 0 1 1 1,1 0 0 1 0 1 1 0 1 0 1 1 1 0 0 0 1 0 1 1 1,行：1+3,求取循环码的生成多项式g(x) ：,由上式可知，任一循环码多项式T(x)都是g(x)的倍式，故它可以写成A(x) = h(x)g(x)而生成多项式g(x)本身也是一个码组，即有 A (x) = g(x)由于码组A (x)是一个(n k)次多项式，故xk A (x)是一个n次多项式。由下式可知，xk A (x)在模(xn + 1)运算下也是一个码组，故可以写成,求取循环码的生成多项式g(x) ：,上式左端分子和分母都是n次多项式，故商式Q(x) = 1。因此，上式可以化成将A(x)和A(x)表示式代入上式，经过化简后得到上式表明，生成多