计算机软件及应用6信道编码1

第6章信道编码参考：信息处理与编码吴伟陵人民邮电出版社抽象的信息必须依附于具体的物理信号进行传输。信道编码是以信息在信道上的正确传输为目标的编码，可分为两个层次上的问题：〔1〕物理信号的层次：如何正确接收载有信息的信号〔如曼彻斯特编码〕 －－线路编码〔2〕信息层次：如何防止少量过失信号对信息内容的影响〔如奇偶校验、CRC〕 －－过失控制编码，或纠错编码6.1信道编码的根本概念信道编码的目的是为了改善数字通信系统的传输质量。由于实际信道存在噪声和干扰的影响，使得发送的码字与经信道传输后所接收的码字之间存在差异，我们称这种差异为过失。一般，信道噪声/干扰越大，码字产生过失的概率也就越大。1.过失符号与过失比特信号过失与信息过失既有联系又有区别，分别用过失符号与过失比特来描述。过失符号：由符号发生过失引起，也叫信号过失，信号过失概率通常用符号过失概率〔误码元率〕表示。过失比特：由信息比特发生过失引起，也叫信息过失，信息过失概率用误比特率表示。对于二进制传输系统，符号过失等效于比特过失。对于多进制系统，一个符号过失到底对应多少比特过失却难以确定。因为一个符号由多个比特组成。例：参见教材P110〔8进制编码：一个符号对应3个bit信息〕。为了定量地描述信号的过失，定义收、发码之“差〞为：过失图样E=发码C－收码R(模M)。例：8进制(M=8)码元，假设发码 C=(0,2,5,4,7,5,2)收码变为R=(0,1,5,4,7,5,4)过失图样E=C-R=(0,1,0,0,0,0,6)(模8)二进制码最常用的二进制码是一个特例。过失图样可以既可以采用上述定义“模2减〞：E=发码C－收码R(模M)；也可以直接定义为“模2加〞：E=C⊕R或C=R⊕E；或者定义为“异或〞运算。对于二进制码，由于加、减法都是以2为模，所以，加、减、异或等价，也可以称为“无进位/按位〞加、减。在二元码中，过失图样中的“1〞的个数叫汉明距离。理解：如果没有出错，那么过失图样中“1〞的个数为0；如果出错：出错的码元越多，“1〞的个数越多！对于接收者而言，收码R，只要设法找出过失图样E，就可以估算出发码C。2.过失图样类型在无记忆信道中，噪声独立、随机地影响着每个传输码元，因此接收的码元序列中的错误是独立随机出现的。随机过失：过失图样上各码位的取值既与前后位置无关又与时间无关，即过失始终以相等的概率独立发生于各码字、各码元、各比特；以高斯白噪声为主体的信道属于这类独立随机过失信道。双绞线、同轴电缆、光缆信道、太空信道、卫星信道以及大多数微波接力信道，均属于这一类型信道。在有记忆信道中，噪声、干扰的影响往往是前后相关的，错误是成串出现的。突发过失：前后相关、成堆出现。突发过失总是以过失码元开头、以过失码元结尾，头尾之间并不是每个码元都错，而是码元过失概率超过了某个额定值。通常称这类信道为突发过失信道。实际的衰落信道、码间干扰信道均属于这类信道。典型的有短波信道、移动通信信道、散射信道以及受大的脉冲干扰和串话影响的明线和电缆信道，甚至还包括在磁记录中，划痕、涂层缺损将造成成串的过失。有些实际信道既有独立随机过失也有突发性成串过失，称它为混合信道。对不同类型的信道，要对症下药，设计不同类型的信道编码，才能收到良好效果。所以按照信道特性和设计的码字类型进行划分，信道编码可分为纠独立随机过失码、纠突发过失码和纠混合过失码。3.纠错码分类自1948年香农的两篇有关“通信的数字理论〞的文章发表后，很长一段时间内人们都在探寻其编、译码均简单有效的好码，由此形成了一整套纠错码理论。纠错编码的方法是引入冗余度，即在传输的信息码元后增加一些冗余的码元(称为校验码元，或监督码元)，以使受损或出错的信息仍能在接收端恢复。信道编码的输入：称为信息码元，通常是信道编码的输出码元；信道编码的输出：信息码元＋校验码元〔监督码元〕，本章提及的各种码通常是指信道编码的输出码字。从不同的角度出发，纠错编码可有不同的分类方法。检错码与纠错码按码组的功能分，有检错码和纠错码。纠错码与检错码在理论上没有本质区别，一般所说的纠错码包含检错码。分组码与卷积码对信息码元序列的不同处理方法，可以分为：分组码、卷积码。所谓分组码是将k个信息码元划分为1组，然后由这k个码元按照一定的规那么〔固定的映射关系〕产生r个监督码元，从而组成长度n=k+r的码组。在分组码中，监督码元仅监督本码组中的信息码元。分组码一般用符号(n，k)表示，并且将分组码的结构规定为前面k位为信息位，后面附加r(=n-k)个监督位。分组间无关。分组码又可分为循环码和非循环码两种类型。循环码的特点是，假设将其全部码字分成假设干组，那么每组中任一码字的码元循环移位后仍是这组的码字。非循环码是任意1个码字中码元循环移位后不一定再是该码书中的码字。在卷积码中，每组的监督码元不但与本码组的信息码元有关，而且还与前面假设干组信息码元有关，即不是分组监督，而是每个监督码元对它的前后码元都实行监督，前后相关，因此有时也称为连环码。线性码与非线性码按原始信息码元与监督码元之间的关系分，有线性码和非线性码。线性码是指监督码元与信息码元之间的关系是线性关系，即它们的关系可用一组线性代数方程联系起来；非线性码是指二者具有非线性关系。线性、分组码在构造时，将输入信息分成k位一组进行编码，并按照一定线性规律加上人为多余的码元，构成n(n＞k)位一组的输出，故一般可采用符号(n，k)表示，其中n表示输出的码组长度，k表示输入信息分组，即输出码组中信息码位数，显然余下的r=n-k位码元那么表示在编码过程中按照一定线性规律人为参加的多余码元。纠随机过失与突发过失码按照纠正过失类型可分为纠随机过失码、纠突发过失码、介于中间的纠随机/突发过失(混合过失)码等。一般来说，针对随机错误的编码方法与设备比较简单，本钱较低，而效果较显著；而纠正突发错误的编码方法和设备较复杂，本钱较高，效果不如前者显著。因此，要根据错误的性质设计编码方案和选择过失控制的方式。构码数学理论构码理论：代数码、几何码、算术码、组合码等。码元取值按照每个码元取值来分，可分为二元码与多元码，也称为二进制码与多进制码。目前传输系统或存储系统大都采用二进制的数字系统，所以一般提到的纠错码都是指二元码。系统码与非系统码按照信息码元在编码后是否保持原来的形式不变，可划分为系统码和非系统码。在过失控制编码中，通常信息码元和监督码元在分组内有确定的位置。在系统码中，编码后的信息码元保持原样不变，而非系统码中信息码元那么改变了原来的信号形式。系统码的性能大体上与非系统码的相同，但是在某些卷积码中非系统码的性能优于系统码。由于非系统码中的信息位已经改变了原有的信号形式，这对观察和译码都带来麻烦，因此很少应用，而系统码的编码和译码相比照较简单，所以得到广泛的应用。以上分类只是针对某个特定的角度进行的，实际上的某种码可能同时又是分组码、循环码、线性码、二元码等等。4.过失控制系统分类在通信系统中，过失控制方式一般可以分为以下几种类型。前向纠错(FEC)：发端信息经纠错编码后传送，收端通过纠错译码自动纠正传递过程中的过失。反响重发(ARQ)：收端通过检测接收码是否符合编码规律来判断，如判定码组有错，那么通过反向信道通知发端重发该码。混合纠错(HEC)：前向纠错和反响重发的结合，发端发送的码兼有检错和纠错两种能力。前向纠错前向纠错也称为自动纠错。发端发送具有一定纠错能力的码，收端译码时，假设传输中产生过失的数目在码的纠错能力之内译码器可以对过失进行定位并自动加以纠正。反之，假设过失数目大于纠错能力那么无能为力。前向纠错FEC方式的主要优点是不需要反响信道并能自动纠正过失，所以它比较适合于实时传输系统。本章主要介绍应用最广的前向纠错，又称纠错编码。6.1.3随机编码编码的分析、设计的途径：一、根据特定的数学理论，分析和设计一种特定的编码方法。二、不涉及具体编码方法的设计，运用概率统计方法在特定信道条件下对编码信号的性能作出统计分析，求出过失概率的上、下限边界，其中最优码所能到达的过失概率上界称作随机码界。用这种方法不能得知最优码是如何具体编出来的，却能得知最优码可以好到什么程度，并进而推导出有扰离散信道的编码定理，对指导编码技术具有特别重要的理论价值。6.1.4信道编码定理(正定理)从文字描述的内涵是：只要传信率R小于信道容量C，总存在一种信道码(及解码器)，可以以所要求的任意小的过失概率实现可靠的通信。香农的信道编码定理指出，对于一个给定的有干扰信道，如信道容量为C，只要发送端以低于C的速率R发送信息(R为编码器输入的二元码元速率)，那么一定存在一种编码方法，使编码错误概率p随着码长n的增加，下降到任意小的值。这就是说，可以通过编码使通信过程实际上不发生错误，或者使错误控制在允许的数值之下。香农这一理论为通信过失控制奠定了理论根底。逆定理：信道容量C是可靠通信系统传信率R的上边界，如果R>C，就不可能有任何一种编码能使过失概率任意小。采用纠错编码提高可靠性的根本思路：〔P121〕1、增大信道容量；2、减小信息速率〔降低编码效率〕；3、增大〔信道编码输出〕码长。信道编码的根本方法信道编码的根本原理是：根据一定的规律，在待发送的信息码中附加一些人为引入的、多余的码元(称为校验码元，或监督码元)，以保证传输过程的可靠性。监督码元与信息(数据)码元之间以某种确定的规那么相互关联着。接收端根据既定的规那么检验信息码元与监督码元之间的这种关系，如传输过程中发生过失，那么信息码元与监督码元之间的这一关系将受到破坏，从而使接收端可以发现传输中的错误，乃至纠正错误。信道编码的任务就是构造出最小冗余度代价换取最大抗干扰性能的“好〞码。具体来说，码的检错和纠错能力是用信息量的冗余度来换取的。最大似然译码最大似然译码：对接收的错误结果进行纠错译码时，选择可能性最大的情况作为译码的结果。在通信过程中总是假设通信干扰较小，因此：总是选择过失最小的可能作为译码的结果。前面已经介绍：在二元码中，过失图样中的“1〞的个数叫汉明距离。最大似然译码原理可以根据过失图样中的汉明距离大小进行译码，即：汉明距离译码：汉明距离越小，说明过失越少。简单的例子一般信息源发出的任何消息都可以通过二元码信息编码的方式，用二元信号“0〞和“1〞来表示。考察最简单的冗余情况。1.不重复2.重复一次3.重复两次1、不重复例如，要传送A和B两个消息，可以用“0〞码代表A，用“1〞码表示B。在这种情况下，假设传输中产生错码，即“0〞错成“1〞，或“1〞错成“0〞，接收端都无从发现，因此，这种编码没有检错和纠错能力。2、重复一次如果分别在“0〞和“1〞后面附加一个“0〞和“1〞，变为“00〞和“11〞(本例中分别表示消息A和B)。这时，在传输“00〞和“11〞时，如果发生一位错码，那么变成“01〞或“10〞，译码器将可判决为有错，因为没有规定使用“01〞或“10〞码字。这说明在附加一位监督码元以后,码字具有了检出一位错码的能力。但因译码器可以检错。如果一定要纠错，那么对、错概率各为1/2。因此，实际上不能纠错。注意：本例中“01〞和“10〞称为禁用码字，而“00〞和“11〞称为许用码字。3、重复两次进一步，假设在信息码之后附加两位监督码，即用“000〞代表消息A，“111〞表示B。这时，码组成为长度为3的二元编码，而3位的二元码有23=8种组合，本例中选择“000〞和“111〞为许用码字，余下的6组001、010、100、011、101、110均为禁用码字。此时，如果传输中产生了错误，收端将收到禁用码字，因此收端可以判决传输有错、可纠错。例如，接收到一个禁用码字011，判断出错：有可能是000错误2个码元所得，也有可能是111错误一个码元所得。根据似然译码原理，总是认为出错概率较小，因此判断为111出错所得。从而可以纠正一个错误。当然，实际上有可能是000错误所得，因此：译码是存在误差的，但选择最大的正确可能。实际通信系统中，假设：出错的概率小于正确传输的概率。如果接收到的3位码字中如有2个或3个“0〞,判其为“000〞码字(消息A)；如有2个或3个“1〞,判其为“111〞码(消息B)，所以，此时可以纠正一位错码。这种方法即是所谓的最大似然译码原理；也可以根据过失图样中的汉明距离大小进行译码，即：汉明距离译码。如果在传输中产生两位错码，也将变为上述的禁用码字，译码器仍可判为有错并试图纠正，但纠正的结果是错误的、即：不能正确纠错。这说明本例中的码可以检出两位和两位以下的错码以及纠正一位错码的能力。由此可见，纠错编码之所以具有检错和纠错能力，是因为在信息码之外附加了监督码。监督码不荷载信息，它的作用是用来监督信息码在传输中有无过失，对用户来说是多余的，最终也不传送给用户，但它提高了传输的可靠性。监督码的引入，降低了信道的传输效率。一般来说，引入监督码元越多，码的检错、纠错能力越强，但信道的传输效率下降也越多。人们研究的目标是寻找一种编码方法使所加的监督码元最少,而检错、纠错能力又高且又便于实现。6.1.2矢量空间与码空间最根本的纠错码是(n，k)线性分组码、又叫块码，可以采用矢量空间进行分析和理解。F表示码元所在的数域，对于二进制码，F代表二元域{0,1}。码字矢量可以表示为码矢的运算法那么遵从矢量运算法那么。P113~114。设n重有序元素〔n重矢量〕的集合V={Vi}，假设满足条件：(1)V中矢量元素在矢量加运算下构成加群〔加法的封闭性〕；(2)V中矢量元素与数域F元素的标乘封闭在V中〔乘法的封闭性〕；(3)分配律、结合律成立；那么称集合V是数域F上的n维矢量空间，或称n维线性空间，n维矢量又称n重(n-tuples)矢量。码字又称码矢、n重、码多项式。矢量空间中矢量的关系对于域F上的假设干矢量线性组合：

线性相关：

线性相关的矢量集合中：至少存在一个矢量可表示为其它矢量的线性组合。线性无关或线性独立：一组矢量中的任意一个都不可能用其它矢量的线性组合来代替。矢量空间中矢量的关系：(1)线性组合、线性相关：一组矢量中的某一个可表示为其它矢量的线性组合(2)线性无关、线性独立：一组矢量中的任意一个都不可能用其它矢量的线性组合来代替。矢量空间：如果存在一组线性无关的矢量Vi，线性组合的集合就构成了一个矢量空间V，这组矢量就是这个矢量空间的基底。n维矢量空间应包含n个基底。因此：n个基底可以“张成〞一个n维空间。基底不是唯一的，例：线性无关的两个矢量(1,0)和(0,1)以及(-1,0)和(0,-1)可张成同一个两维空间。自然基底。二元域GF(2)上三重矢量空间子空间：一个矢量空间的子空间。例6-1：P114。以(100)为基底可张成一维三重子空间V1，含21=2个元素，即V1 ={(000),(100)}以(010)(001)为基底可张成二维三重子空间V2，含22=4个元素，即V2 ={(000),(001),(010),(011)}以(100)(010)(001)为基底可张成三维三重空间V,含23=8个元素，V1和V2都是V的子空间。矢量空间每个矢量空间或子空间中必然包含零矢量！重数：构成矢量的有序元素的个数。子空间的维数：矢量空间的基底的个数。维数不可能大于重数：对于n维n重空间，维数等于重数；对于一个k维n重子空间，必有维数k小于重数n。两个矢量正交：V1*V2=0(矢量乘是标量。)两个矢量空间正交：某矢量空间中的任意矢量与另一矢量空间中的任意矢量正交。假设两个空间的基底正交，那么两个空间必然正交。〔*理解：空间中任何一个向量可以表示为其基底的线性组合！〕正交的两个子空间V1、V2互为对偶空间(DualSpace)，其中一个空间是另一个空间的零空间(nullspace，也称零化空间)。理解：由n重n维空间的n个自然基底中分割得到的互斥的两组基底构成的两个子空间必然正交。理由：自然基底必然正交；来自于同一个n重n维空间的两个互斥的子空间中的任何一个向量分别可以表示为两组相互独立的自然基底的线性组合，由于同一个原始线性空间满足分配律和结合律，故上述结论成立。码字的矢量空间

消息k长 (n,k)码字n长

qk

种分组编码器qn种

k维k重矢量n维n重矢量码字的矢量空间消息k长qk

种k维k重矢量 码字n长qn种n维n重矢量

通常qn>>qk，分组编码的任务是要在n维n重矢量空间的qn种可能组合中选择其中的qk个码字的集合，并构成一个子空间－－码空间，其元素就是许用码字的码字集合。一般情况下，从n维n重矢量空间的qn种可能组合中选择个矢量构成的码集不一定能构成一个子空间。注意：对于线性分组码而言，码集一定是一个k维n重子空间。这是由编码方法决定的！分组编码的任务选择一个k维n重子空间作为一个码字空间。确定由k维k重信息空间到k维n重码空间的映射方法。码空间的不同构成集合，以及信息组与码组的不同映射算法，就构成了不同的分组码。6.3线性分组码由2k个信息码组所编成的2k个n重码字集合，即为分组码。分组码的编码方法包括两个根本步骤：一、把信源的输出码元序列按一定长度分成假设干个信息码组(信息组、消息组、消息或信息码元)，每组由相继的k位信息码元组成；二、信道编码器按照一定的编码规那么(例如，可以根据线性方程组来规定监督码元)，把k长的信息码组变换成n个码元构成的n重(n>k)码字，即(n，k)分组码。其中(n-k)个监督码元是由在信息码元的根底上运算产生的。

消息m (n,k)码字c

m=(mk-1,…,m1,m0)

分组编码器c=(cn-1,…,c1,c0)qk<qn码集C能否构成n维n重矢量空间的一个k维n重子空间？如何寻找最正确的码空间？qk个信息元组以什么算法一一对应映射到码空间。线性分组码中的线性是指：码字中信息码元与监督码元之间的约束关系是线性的。分组那么是对编码方法而言，即编码时将每k个信息位分为一组进行独立处理，变换成长度为n(n＞k)的二进制码组。空间：满足一定条件的码字的集合。在2k个码字中只有k个是线性独立的。如前所述，一般分组码的码集未必能构成n维n重矢量空间的k维n重子空间。线性分组码那么一定能！因为构造线性分组码的构造方法就是构造子空间的过程。方法：从n维n重空间的n个基底中选择k个基底作为码字空间的基底，由这k个基底张成的空间就是k维n重子空间，也即码字集合。所以，线性分组码的码字集合必然是一个线性子空间。可见，一个线性分组编码f是一个从矢量空间GF(2k)到另一个矢量空间GF(2n)上的一组线性变换。它可应用线性代数理论中有限维的矩阵来描述。一个n重的码字，C可以用矢量来表示：C=(cn-1,cn-2,…,c1,c0)，所以码字又称为码矢、码组。在矩阵运算中，以下术语等价：n重矢量、1×n矩阵、行向量。编码效率对于(n，k)线性码，用Rc=k/n表示码字中信息位所占的比重，叫做编码效率，简称码率。编码效率表征了信道的利用效率。R越大，码的效率越高，R是衡量码性能的一个重要参数。线性分组码的引入如果码的数域为GF(2)，即每一个码元可能有2种取值，那么信源可发出2k种不同的消息组。为使接收端对码字惟一可译(即从n位长的码字中译出k位的消息)，消息组与许用码字之间应有一一对应关系，所以编码器需要存贮2k个码字才能实现消息到码字的变换。〔编码器容量为2k*n〕当k比较大时，这种编码器将显得不切实际。为了压缩编码器的存贮容量，通常对编码器附加了一个线性约束条件，使得线性码的监督位与信息位之间呈线性关系，对于二元码，(n，k)线性分组码(简称(n，k)码)共有2k个码字。它们构成k维子空间。在(n,k)分组码中，只有2k个才是许用码字，这些许用码字构成k维n重子空间，该空间中基底矢量只有k个，许用码字是基底的线性组合，通过这k个基底矢量的线性组合就可得到2k个两两互异的全部许用码字。因此，线性分组码的编码器不再需要存储2k个码字，而只要存储k个线性独立的基底码字即可。当(n，k)码的n、k都比较大时，存储容量从2k个n重降到k个n重。〔编码器容量为k*n〕这就是施加线性约束的好处！6.3.1生成矩阵和校验矩阵例：(7,3)码的方程组构造线性分组码可以通过线性方程组来实现。例：假设一种编码方法，信息分组长度k=3，在每一信息组后加上4个监督码元，构成(7,3)线性分组码的系统码。设该码的码字为(c6,c5,c4,c3,c2,c1,c0)，其中c6,c5,c4为信息码元；c3,c2,c1,c0为监督码元，每个码元取值为“0〞或“1〞，即ci∈GF(2)。监督码元可按下面方程组计算：c3=c6+c4c2=c6+c5+c4c1=c6+c5c0=c5+c4这个线性方程组确定了由信息码元生成监督码元的规那么，所以称为〔一致〕校验方程组或〔一致〕监督方程组。所得到的冗余码元称为〔一致〕校验码元或〔一致〕监督码元。由于一致校验方程是线性的，亦即监督码元和信息元间是线性运算关系，所以由线性校验方程所确定的分组码是线性分组码。利用上式，每给出一个3位的信息组，就可编出一个码字，如表所示。表(7,3)分组码编码表6.3.1生成矩阵和校验矩阵由于线性分组码的码字集合构成一个空间，因此码空间的所有元素(即许用码字)都可以写成k个、n重基底向量gi的线性组合。即有：c=mk-1gk-1+…+m1g1+m0g0生成矩阵把上述表达式写出矩阵形式，那么有c＝m*G1*n1*kk*n码字消息生成矩阵即：G＝[gk-1…g1g0]T，有k个线性无关的(1*n)行矢量〔即K个n重基底向量〕。对于输入的一个确定的信息码组，输出的码字仅由G矩阵决定，因此我们称这k×n矩阵G为该(n,k)线性分组码的生成矩阵。在(n，k)线性分组码中，n表示码长，k表示信息位的长度，也就是子空间的维数。设M=(m1，m2，…，mk)是输入编码器的一个信息码组，那么由纠错码编码器输出的对应码字C为C1×n=M1×k*Gk×nG为该线性分组码(n，k)码的生成矩阵，即生成矩阵的特点由于(n,k)线性分组码能够构成k维n重子空间，所以：G的k个行矢量gk-1,…,g1,g0必须线性无关！由于k个基底即G的k个行矢量线性无关，矩阵G的秩一定等于k。通过生成矩阵G建立了消息码组与码字之间的一一对应关系，起着编码器的变换作用。因此C的每一个码元的取值都是消息码字的线性组合。应该指出，由于一个子空间的基底矢量的选择不是惟一的，因此：生成矩阵G不是惟一的。但是，不同的基底却有可能生成相同的码字集合。所以，不同形式的生成矩阵仅表示消息与码字之间不同的一一映射关系，但2k个消息的集合却对应着同一个(n，k)码的码字空间。因为编码方法同时涉及码字集合和映射方法两个因素，虽然码集一样而映射方法不同也不能说是同样的码。生成矩阵的系统形式(n,k)码的任何生成矩阵都可以通过行运算(以及列置换)简化成所谓的“系统形式〞。Gk×n=[IkP]=Ik是k×k单位矩阵，P是k×(n-k)矩阵。系统码显然，利用上述系统形式的生成矩阵获得的输出码字C=(cn-1,cn-2,…,c1,c0)中：前k位(cn-1,…,cn-k)=(mk-1,…,m0)是信息位；后n-k位(cn-k-1,…,c0)称为码字的监督位。前k位由单位矩阵Ik决定，等于把信息组m原封不动搬到编码器输出码字的前k位！其余的n-k位即冗余位或一致校验位，是前k个信息位的线性组合。这样生成的(n,k)码叫做系统码。假设生成矩阵G不具备系统形式，那么生成的码叫做非系统码。系统化非系统码的G可通过系统化(行初等变换和列置换)转变为系统码的G。假设通过行运算和列置换能将两个生成矩阵G互等，那么称这两个G等价。等价的两个G生成的两个(n,k)线性码也是等价的。任何一个(n,k)线性分组码都等价于一个系统码。例：系统化例：对于生成距阵，求非系统码的等价系统码。(参考教材：P250)方法：行初等变换、列交换。只要码率R和码长n相同，最正确系统码和最正确线性分组码具有相同的译码错误概率。例：不同的(6，3)码不同形式的生成矩阵仅表示消息与码字之间不同的一一映射关系！但2k个消息的集合却对应着相同的码字空间〔集合〕。如下图的G1和G2码的生成矩阵，所对应的码字如表所示。上表所示的码，虽然用了不同形式的生成矩阵，但都属于同一个(n，k)码的码字空间，因此它们的检错和纠错能力是一样的。理解：系统化不改变码集，只是改变了映射规那么。系统码与非系统码的主要区别在于选择了不同的基底向量、即：生成矩阵。系统码与非系统码的区别系统码的编码器仅需存储k×(n-k)个码元数字(非系统码要存储k×n个数字)，译码时仅需对前k个信息位纠错即可恢复消息。由于系统码的编码和译码比较简单，而性能与非系统码一样，所以系统码得到了十分广泛的应用。空间构成(参见P127)n维n重空间存在相互正交的n个基底。选择k个基底构成码空间C。选择另外的(n-k)个基底构成空间H。GHT=0，C和H是对偶的！且：CHT＝0，或HCT=0TCT、0T或HT分别为C、0、H的转置矩阵。

n维n重空间V

k维k重k维n重n-k维信息组码空间n重H

空间mC校验矩阵在n重空间中，将空间其他的n-k个基底排列起来可构成一个(n-k)×n矩阵，称为校验矩阵H。G是(n,k)码的生成矩阵，H是校验矩阵。对一个(n，k)线性码C，HGT=0T。CT、0T或HT分别为C、0、H的转置矩阵。对偶码D如果以G作校验矩阵，而以H作生成矩阵，可构造另一个码D。码D是一个(n,n-k)线性码，称为原码C的对偶码。H是(n,n-k)对偶码的生成矩阵，它的每一行是(n,n-k)码的一个基底。G那么是它的校验矩阵。线性码的生成矩阵G和校验矩阵H的行矢量彼此正交。即：GHT=0！由于对偶码是原码的生成矩阵和校验矩阵互换后所构成的码，所以对偶码D的任意码矢与原码C的码矢彼此正交，码C生成矩阵的行矢量张成的k维子空间和由码C校验矩阵行矢量张成的n-k维子空间互为零空间。来自于n维n重空间：k个基底←→另外n-k个基底(n，k)码←→(n，n-k)码码字空间C←→对偶码、对偶空间D(n，k)码生成矩阵G←→(n，n-k)码校验矩阵(n，k)码校验矩阵H←→(n，n-k)码生成矩阵校验矩阵的作用(n，k)码字空间C与(n，n-k)码字空间D的基底正交，那么空间正交、互为对偶空间、互为零空间。因此：(n，k)码的任意许用码字一定正交于对偶码D的任意码字、也正交于D的生成矩阵H中任一基底向量，即：C1*nHTn*(n-k)=01*(n-k)或：H(n-k)*n*CTn*1=0T(n-k)*1〔所以：校验矩阵H可以用来校验一个接收到的码字R是否是C的许用码字！〕如前所述：系统码的生成矩阵G可用分块矩阵表示为Gk×n=［Ik

P］式中：Ik——k×k阶单位方阵；

P——k×(n-k)阶阵。对校验矩阵H各行实行初等变换，可以将后〔n-k〕列化为单位子阵，那么：H=［Q|In-k］把变换所得的，其后n-k列是一单位子阵的校验矩阵H，称为校验矩阵H的系统/标准形式。H阵的一般形式可通过行的线性变换化成标准形式。利用标准形式的H阵进行编、译码是方便的，所以H阵的系统形式是一种常用形式。H的标准形式还说明了相应的监督码元是由哪些信息元决定的，校验矩阵H(n-k)*n的n-k行代表了n-k个校验方程。也表示由H所确定的码的码字有n-k个监督码元。那么为了得到确定的码，n-k个校验方程(或H阵的n-k行)必须是线性独立的，这要求H阵的秩为n-k。假设把H阵化成标准形式，只要检查单位子阵的秩，就能方便地确定H阵本身的秩。前面讨论了线性分组码的生成矩阵和校验矩阵，二者之间有无联系呢？(P128)答复是肯定的，(n，k)线性码的G和H之间有非常密切的关系！由于生成矩阵G的每一行〔基底向量〕都是一个码字，所以G的每行都满足HCT=0T，且C=MG，那么有：HGTMT=0T所以，HGT=0T或GHT=0。H为(n-k)×n矩阵，HT为n×(n-k)矩阵。理解：事实上，G、H本来就是针对同一种线性约束关系而来的，当然存在本质联系。可以证明：

P=QT

或

PT=Q由此可得：G=［IkP］=［IkQT］或

H=［QIn-k］=［PTIn-k］上式：可以用来方便地在系统码的G、H之间相互直接转换。例如，(7，4)线性系统码的校验矩阵为可直接写出它的生成矩阵为同理，(7,4)线性码的对偶码是(7,3)码，那么(7,3)码的校验矩阵H(7，3)是(7,4)码的生成矩阵G(7,4)，即而(7，3)码的生成矩阵G(7，3)是(7，4)码的校验矩阵H(7，4)，即初等交换化成标准形式例:二元线性分组码编码器例6-2(P128)：(6,3)线性分组码，其生成矩阵是G=求：(1)计算码集，列出信息组与码字的映射关系。(2)将该码系统化处理后，计算系统码码集并列出映射关系。(3)计算系统码的校验矩阵H。假设收码r=[100110],检验它是否码字？(4)根据系统码生成矩阵画出编码器电原理图。111010①110001②011101③信息码字系统码字000000000000000001 011101 001011010 110001 010110011 101100 011101100 111010 100111101 100111 101100110 001011 110001111 010110 111010

m0

m1

m2

输入 输出

c0

c1

c2例:(7,3)线性分组码下面利用校验矩阵来构造(7，3)线性分组码的编码电路。设二元码字矢量为C=(c6,c5,c4,c3,c2,c1,c0)，而码的校验矩阵为由HCT=0T得：c3=c6+c4c2=c6+c5+c4c1=c6+c5c0=c5+c4根据上式可直接画出(7,3)码的并行编码电路和串行编码电路，如图3所示。类似地，也可以利用生成矩阵来编码。设信息组为M=(m2,m1,m0)，生成矩阵为根据C=(c6,c5,c4,c3,c2,c1,c0)=MG，将M和G代入得：c6=m2c5=m1c4=m0c3=m2+m0=c6+c4c2=m2+m1+m0=c6+c5+c4c1=m2+m1=c6+c5c0=m1+m0=c5+c4

图3线性系统码编码电路(a)并行编码电路；(b)串行编码电路综上所述，线性分组码完全可以由生成矩阵G或校验矩阵H所决定。一般地，在讨论编码时，通常采用生成矩阵G；讨论译码问题时，通常采用校验矩阵H。6.3.2线性分组码的译码1.译码准那么如果只考虑信道编码，那么数字通信系统模型可归结成如图5-3所示。图5-3纠错码通信系统模型图5-3中的信源包括信息的发出者、信源编码器和加密器，信道包括传输媒介及调制解调器，信宿包括解密器、信源译码器及信息的接收者。设：发送码字C=(cn-1,cn-2,…,c0)〔对于接收端未知〕，接收码字R=(rn-1,rn-2,…,r0)。译码器根据编码规那么和信道特性，对接收码字R作出判断，此判决过程称为译码。mC=(cn-1,…,c1,c0)R=(rn-1,…,r1,r0)(n,k)信道定义过失图案EE＝(en-1,…,e1,e0)＝R-C＝(rn-1-cn-1,…,r1-c1,r0-c0)二进制码中模2加与模2减是等同的，因此有 E=R＋C及 R=C＋E 伴随式S的定义通常，采用生成矩阵进行编码，采用校验矩阵实现译码。当收到一个接收码字R后，可用校验矩阵H来检验R是否满足校验方程，即HRT=0T是否成立。假设关系式成立，那么认为R是一个码字，否那么认为码字在传输中发生了错误。因此，HRT的值是否为0是检验码字出错与否的依据。伴随式S的定义设发送码字C=(cn-1，cn-2，…，c0)，信道的过失图样为E=(en-1，en-2，…，e0)。因为CHT=0，所以：RHT＝(C＋E)HT＝CHT＋EHT=EHT如果收码无误：必有R＝C即E＝0，那么EHT=0→RHT=0。如果收码有误：即E0，那么RHT=EHT0。伴随式S的定义可见，在HT固定的前提下，RHT仅仅与过失图案E有关，而与发送码C无关。从物理意义上看，伴随式S并不反映发送的码字是什么，而只是反映信道对码字造成怎样的干扰。所以，定义伴随式(或监督子，或校验子)：S=(sn-k-1,…,s1,s0)=RHT=EHT，或ST=HRT=HET。[例](7,3)码的译码[例]设(7，3)码的校验矩阵为下所示。通过计算(7，3)码接收码字R的伴随式进行译码。注意：二元码伴随式S是H阵中与错误码元对应的列之和。(1)接收码字R=(1010011)，接收端译码器根据接收码字R的计算伴随式为因此，译码器判断接收字即为发送码字C=(1010011)，认为传输中没有出错。(2)接收字中有一位错误：设接收码字R=(1110011)，其伴随式为由于ST≠0，译码器判为有错，即传输中有错误发生。(7，3)码是纠单个错误的码，且ST等于H的第二列，因此判定接收码字R的第二位是错的。由于接收字中错误码元数与码的纠错能力相符，所以译码正确。(3)当码元错误多于1个时：设接收码字R=(0011011)，其伴随式为ST是H阵第一列和第四列之和，也等于第二和第三列之和，不等于0，但与H阵的任何一列都不相同，无法判定错误出在哪些位上，即此时只能发现有错。伴随式的计算可用(译码)电路来实现，仍以(7，3)码为例，设接收码字R=(r6,r5,r4,r3,r2,r1,r0)，那么伴随式为图(7，3)码伴随式计算电路例2：参见参考教材：P253针对过失图样，采用最小汉明距离译码，也就是最大似然译码。由上面分析得到如下结论：(1)伴随式仅与过失图样E有关，而与发送的具体码字无关，即伴随式仅由过失图样决定。(2)伴随式是错误的判别式：假设S=0，那么判没有出错，接收字是一个码字，假设S≠0，那么判有错。(3)针对接收的一个码字R具有唯一的伴随式，但是：同一个伴随式可能对应着不同的过失图样。伴随式S的意义接收端收到R后，由于HT，可求出S＝RHT；如果能知道对应的E，那么通过C=R＋E而求得C。RHT=S???C=R＋ERSEC只要E正确，译出的码也就是正确的。过失图案E是n重矢量，共有2n个可能的组合，而伴随式S是(n-k)重矢量，只有2n-k个可能的组合，因此，同一个伴随式可能对应着多个不同的过失图案。关键：根据S获取E！过失图案E的求解(1)可以通过解线性方程求解E：

S=(sn-k-1,…,s1,s0)=EHT

=(en-1,…e1,e0)得到线性方程组：

sn-k-1=en-1h(n-k-1)(n-1)+…+e1h(n-k-1)1+e0h(n-k-1)0

。。。。。。 s1=en-1h1(n-1)+…+e1h11+e0h10 s0=en-1h0(n-1)+…+e1h01+e0h00上述方程组中有n个未知数en-1,…e1,e0，却只有n-k个方程，可知方程组有多解。在有理数或实数域中，少一个方程就可能导致无限多个解，而在二元域中，少一个方程导致两个解，少两个方程四个解，以此类推，少n-(n-k)=k个方程导致每个未知数有2k个解。因此，根据一个特定的S、由上述方程组解出的E可以有2k个解。过失图案E的求解(2)到底取哪一个作为附加在收码R上的过失图案E的估值呢？最大似然译码：把所有2k个解的汉明重量(过失图案E中1的个数)作比较，选择其中最轻者作为E的估值。依据：假设BSC信道的过失概率是p，那么长度n的码中错误概率：0个错1个错2个错…n个错(1-p)np(1-p)n-1p2(1-p)n-2pn由于p<<1,>>>>>>…>>出错越少的情况，发生概率越大，E的重量越轻，所以该译码方法实际上表达了最小距离译码准那么，即最大似然译码。标准阵列译码表上述的概率译码方法：每次接收一个码字R那么计算S、解线性方程组估算求E，概念上很简单，但实际应用太麻烦。在实际应用中，往往采用标准阵列译码表的方法。根本思路：由于伴随式S的数目总共是2n-k个，如果n-k不太大，我们可以预先把所有的、每一个S对应的方程组解出来〔把各种情况下的最大概率译码的E〕，再根据E＋R＝C，所有C输出列成一个码表。实际译码时，直接查表即可。表中：一个特定的S→惟一的E。译码过程：一个码R→一个S→→惟一的E→一个C。这样，在实时译码时就不必再去解方程，而只要象查字典那样查一下码表就可以了。这样构造的表格叫做标准阵列译码表。标准阵列译码表的构造过程1标准阵列译码表的构造过程(P130~131)：1、针对S的所有可能取值的每一个：计算得到所有的重量最轻的E；于是：2n-k个S，总共求出2n-k个E作为第一列的元素；注意：排列顺序按照过失图样的重量(也即：概率大小)依次排列，直至构成2n-k行为止。2、第一行为许用码字，故该表有2k列；〔其中：第一行第一列的元素为全0元素：表示许用码字为全0、且过失图样重量为0！即：无过失的码字0；〕3、表中元素总数为2n-k*2k=2n个。表中第j行、第i列的元素为Ci+Ej。标准阵列译码表的构造过程2对给定的(n，k)线性码，将2n个n重矢量划分为2k个子集的方法就是构造所谓的“标准阵列〞。主要步骤如下：先将2k个码字排成一行，作为“标准阵列〞的第一行，并将全0码字C1＝(0,0,…,0)放在最左面的位置上；然后在剩下的2n-2k个n重矢量中选取一个重量最轻的n重E2放在全0码字C1的下面〔第1列〕，再将E2分别和码字C2，C3，…，C2k相加，放在对应码字下面构成阵列第二行，在第二次剩下的n重矢量中，继续选取重量最轻的n重E3，放在E2下面，并将E3分别加到第一行各码字上，得到第三行……，继续这样做下去，直到全部n重矢量用完为止，按上述方法构造的标准阵列如表所示。表中所列码字是接收到的码字R、包含了n重码字的所有可能；将没有任何过失时的收码R放在第一行，此时收码等于发码R=C(CCi,i=0,1,…2k-1),过失图案为全零E0=(0,0…0)，伴随式为全零S0=(0,0…0)。由于有2k个码字，码表有2k列。在第2到第n+1的n行中过失图案的所有重量为1(共n个)。如果(1+n)<2n-k，再在下面行写出全部带有2个过失的图案(共个)。如果总行数(1+n+)仍然小于2n-k，再列出带有3个过失的图案，以此类推，直到放满2n-k行，每行一个Ej,对应一个不同的伴随式Sj。这样，表的行数2n-k正好等于伴随式的数目。标准阵列译码表的构造过程3表(n，k)线性码的标准阵列S0E0S1E1

…SjEj

…E0+C0=0+0=0E0+C1=C1E0+Ci=CiE1+C0=E1

E1+CiEj+C0=EjEj+C1Ej+Ci

E1+C1

标准阵列译码表陪集和子集译码表中有2n-k行，每行称为一个陪集，每陪集的第一个元素(位于第一列)称为陪集首。同一陪集(同一行)中的所有元素对应共同的一个伴随式。第一行陪集的陪集首是全零伴随式S0所对应的全零过失图案E0(无过失)，而第j行陪集的陪集首是伴随式Sj所对应的重量最小的过失图案Ej(C0=0,Rj=Ej)。译码表中有2n/2n-k＝2k列，每列包含2n-k个元素，称为一个子集，每子集的第一个元素(位于第一行)称为子集头。同一子集(同一列)中的所有元素对应同一个码字，第一列子集的子集头是全零码字C0，而第i列子集的子集头是许用码字Ci(E0=0,Ri=Ci)。标准阵列译码表中包含2k列(和码字数相等)，2n/2k＝2n-k行，且任何两列和两行都没有相同的元素，即列和行都不相交。定理：在标准阵列表的同一行中没有相同的码字，而且2n个n重码字中任一个n重码字在阵列中必出现一次且仅出现一次。证明：因为阵列中任一行都是由所选出某一n重码字分别与2k个码字相加构成的，而2k码字互不相同，它们与所选码字的和也不可能相同，所以在同一行中没有相同的码字。在构造标准阵列时，是用完全部n重码字为止，因而每个n重码字必出现一次。另外，假定某一n重码字X出现在第y行第i列，那么X＝Ey＋Ci，又假设X出现在第m行第j列，那么有X＝Em＋Cj，y<m。因此Ey＋Ci＝Em＋Cj，移项得Em＝Ey＋Ci＋Cj，而Ci＋Cj也是一个码字，设为Cs，于是Em＝Ey＋Cs，这意味着Em是第y行中的一个码字，但Em是第m行(m>y)的第一个元素，而按阵列构造规那么：后面行的第一个元素是前面行中未曾出现过的元素，这就和阵列构造规那么相矛盾。因而任何n重不可能在阵列中出现两次。例6-3(P131)一个(5,2)系统线性码的生成矩阵是G=构造标准阵列译码表。设收码R=(10101)，译出发码的估值解：(1)构造标准阵列译码表。分别以信息组m=(00)、(01)、(10)、(11)及的G求得4个许用码字为C1=(00000)、C2=(10111)、C3=(01101)、C4=(11010)。求出校验矩阵：H=[PTI3]=列出方程组：例6-3译码表的构成伴随式有2n-k＝23＝8种组合，过失图案中代表无过失的有一种，代表一个过失的图案有种，于是总共已有6种。代表两个过失的图案有种。只需挑选其中的两个，挑选方法可有假设干种，不是唯一的。先将Ej=(00000)、(10000)、(01000)、(00100)、(00010)、(00001)代入上面的线性方程组，解得对应的Sj分别是(000)、(111)、(101)、(100)、(010)、(001)。剩下的伴随式中，(011)所对应的过失图案是2k个即(00011)、(10100)、(01110)、(11001)，其中(00011)和(10100)并列重量最轻，任选其中一个如(00011)。同样，可得伴随式(110)所对应的最轻过失图案之一是(00110)。S0=000E0+C0=00000C1=10111C2=01101C3=11010S1=111E1=10000001111110101010S2=101E2=01000111110010110010S3=100E3=00100100110100111110S4=010E4=00010101010111111000S5=001E5=00001101100110011011S6=011E6=00011101000111011001S7=110E7=00110100010101111100例6-3标准阵列译码表例6-3对接收码R＝10101译码可选以下三种方法之一译码：1、直接搜索码表，查得(10101)所在列的子集头是(10111)，因此译码输出取为(10111)。2、先求伴随式RHT=(10101)HT=(010)=S4，确定S4所在行，再沿着行对码表作一维搜索找到(10101),最后顺着所在列向上找出码字(10111)。3、先求出伴随式RHT=(010)=S4并确定S4所对应的陪集首(过失图案)E4=(00010)，再将陪集首与收码相加得到码字C=R+E4=(10101)+(00010)=(10111)。上述三种方法由上而下，查表的时间下降而所需计算量增大，实际使用时可针对不同情况选用。该(5,2)码的最小距离dmin=3。纠错能力是t=INT[(3-1)/2]=1。可以看出，译码阵列中只有前6行具有唯一性、可靠性，真正表达了最大似然译码准那么。而第7、8行的过失图案(00011)和(00110)中包含两个“1〞，已超出了t=1的纠错能力，译码已不可靠。比方，当收码R＝(10100)时，根据码表译出的码字是(10111)，与收码R的汉明距离是2，然而收码R与全零码字(00000)的汉明距离也是2，为什么不能译成(00000)呢？事实上，码表的第7、8行本身就不是唯一的。注意在码表计算过程中，伴随式(011)所对应的4个过失图案中有两个并列重量最轻，如果当时选的不是(00011)而是(10100)，那么码表第7行就不是现在这样了。因此：伴随式的个数与n、k，n、k与纠错能力t之间存在一定的数字关系！[例]二元(4，2)系统码C，生成矩阵与一致校验矩阵分别为其标准阵列如表所示。该阵列的第一行是4个码字，其中零码字排在左边，然后在剩下的12个码字中，挑选一个重量最小的码字，例如(1000)，作为第二行的陪集首。将(1000)与第一行中所有的码字相加，就得到第二行。接着，在剩下的8个矢量中选取(0100)为第三行的陪集首，等等。在这个例子中，陪集首重量皆为1的码字，但对于其他的码，陪集首的重量可能为2，3，4，……。表(4，2)线性码的标准阵列假定接收码字R＝(1010)，在表中的第3行第4列中找到了它，于是就可以把R译成位于第4列的码字M＝(1110)。显然，位于第3行的陪集首(0100)是过失图样E，表示信道第2位有错。由此可见，能否正确译码的关键在于信道过失图样是否是陪集首。因为将R译为与它最接近的码字M，所以符合最大似然译码准那么。又例，设(6，3)码的生成矩阵为表(6，3)线性码的标准阵列用表中的标准阵列译码，可纠正一位过失的全部过失图样和一种两位过失的过失图样。如发送码字为C＝(101011)，E＝(010000)，那么接收码字R＝C＋E＝(111011)。查看标准阵列可知它所在子集的估值＝(101011)，因此译码正确。又如同一码字，但它的过失图样为E＝(001100)它不在陪集首，由于R＝(101011)＋(001100)＝(100111)，与此R对应的＝(100110)≠C，属于错误译码。标准阵列译码的简化原那么上讲，用标准阵列译码要存储2n个n重码字。当n很大时，这是不实际的。如当C为码长100的二元码时，C的标准阵列由2100个阵元组成，译码器必须存储它们，译码时还必须从中搜索接收码字R，这在工程实践上是很难实现的。然而标准阵列的以下性质可使译码过程简化。定理：在标准阵列中，一个陪集(表中一行)的所有2k个n重码字有相同的伴随式，不同陪集的伴随式互不相同。于是，任意n重码字的伴随式取决于它在标准阵列中所在陪集的陪集首；标准阵列的陪集首和伴随式是一一对应的，因而码的可纠过失图样和伴随式是一一对应的。因此：实际译码器只需要存储陪集首集合即可。证明设H为给定(n，k)线性码的校验矩阵，在陪集首为Ey的陪集中的任意码字R为R＝Ey＋Ci，i＝1，2，…，2k其伴随式为S＝RHT＝(Ey＋Ci)HT＝EyHT＋CiHT＝EyHT上式说明，陪集中任意码字的伴随式等于陪集首的伴随式。因此，同一陪集中所有矢量的伴随式相同。不同陪集中，由于陪集首不同，所以伴随式也不同。标准阵列译码的步骤应用此对应关系可以构成比标准阵列简单得多的译码表，从而得到(n，k)线性码的一般译码步骤：(1)计算接收码字R的伴随式ST＝HRT。(2)根据伴随式和最大似然译码原那么下的过失图样一一对应的关系，利用伴随式译码表，由伴随式译出R的过失图样E。(3)将接收码字减过失图样，得发送码字的估值。上述译码法称为伴随式译码法或查表译码法。这种查表译码法具有最小的译码延迟和最小的译码错误概率。这种方法原那么上可用于任何(n，k)线性码。实际上，实现译码的关键是第2步－求过失图样上，一般要用组合逻辑电路。当n-k较大时，组合逻辑电路将变得很复杂，甚至不切实际。参见参考教材P254例结论：实际译码器只需要存储陪集首集合即可。6.3.3码距、纠错能力、MDC码及重量谱N重码矢c=(cn-1,cn-2,…c1,c0)可与N维矢量空间XN中的一个点对应，全体码字所对应的点构成矢量空间里的一个子集；发码一定在这个子集里，传输无误时的收码也一定位于该子集〔许用码字〕；当出现过失时，接收的N重矢量：对应到子集外空间某一点对应到该子集，却对应到该子集的另一点上集合的观点设(n，k)线性码用来纠错，发送码字取自于2k个码字集合{Ci}。码字经信道传输后，接收码字R可以是2n个n重矢量中任一个矢量。任何译码方法，都是把2n个n重矢量划分为2k个互不相交的子集D1，D2，…，Ｄ2k，使得在每个子集中仅含一个码字。根据码字和子集的一一对应关系，假设接收码字Rx落在子集Dx中，就把Rx译为子集Dx含有的码字Cx。所以，当接收码字R与实际发送码字在同一子集中时，译码就是正确的。汉明重量在信道编码中，定义码字中非零码元(“1〞)的数目为码字的汉明(Hamming)重量，或码组/码字重量，简称重。显然，不同码字的汉明重量是不同的。例如“010〞码字的码重为1，“011〞码字的码重为2。非零码字中，重量最小者称为该码的最小汉明重量。汉明距离把两个码字中对应码元位置上具有不同码元的位数定义为两个码字之间的汉明(Hamming)距离，或码字〔组〕距离，简称码距。在一种编码中，任意两个合法码字(许用码字)间距离的最小值，即码字集合中任意两码字间的最小距离，称为这一编码的最小汉明距离，以dmin表示。td=7dmin=3d=5C1C2C3C4C5码集各码字间的距离是不同的，码距最小者决定码的特性，即：最小码字距离dmin。用d(C1，C2)表示两个n重C1、C2之间的汉明距离，那么汉明距离有以下三个性质：(1)对称性：d(C1，C2)=d(C2，C1)；(2)非负性：d(C1，C2)≥0；(3)满足距离三角不等式：d(C1，C2)≤d(C1，C3)+d(C3，C2)。逐一计算各个码字之间的汉明距离是非常麻烦的。由于线性分组码的各个码字之和满足封闭性，因此，两个码字之间汉明距离即为某一个〔单个〕码字的汉明重量！定理6.2线性分组码的最小距离等于码集中非零码字的最小重量：dmin=min{w(Ci)} CiC及Ci0定理6.1任何最小距离dmin的线性分组码，其最大检错能力为(dmin-1)，最大纠错能力t为在一般情况下，线性分组码的检错、纠错能力与最小码距的数量关系有以下结论：(1)检测e个错码，那么要求最小码距：dmin－1≥e或者说：假设一种编码的最小距离为dmin，那么它最多能检出(dmin-1)个错码。(2)纠正t个错码，那么要求最小码距为：〔dmin－1〕/2≥t或者说：假设一种编码的最小码距为dmin，那么它最多能纠正(dmin-1)/2个错码。(3)纠正t个错码，同时能检测e(e>t)个错码，那么要求最小码距为dmin≥e+t+1,e>t这里所述能纠正t个错码，同时能检测e个错码的含义，是指：当错码不超过t个时错码能自动予以纠正，而当错码超过t个时，那么不可能纠正错误，但仍可检测e个错码，这正是混合检错、纠错的控制方式。例如，在3位二元码字中：如果8种码字都作为许用码字时，任两组码间的最小距离dmin=1；如果只选4种码组为许用码字时，最小码距dmin=2，假设选用两种许用码字时，dmin=3。参见教材前面的例子P132：dmin=3，纠错能力是1，检错能力是2。最小距离dmin与码率R是码的两个最主要参数，dmin表示了码的纠错能力。可以用(n，k，d)表示最小距离为d，码率R=k/n的线性分组码。纠错码的根本任务之一就是构造出R一定且dmin尽可能大的码，或dmin一定且R尽可能大的码。定理6.3(n,k)线性分组码最小距离等于dmin的充要条件是：校验矩阵H中有(dmin-1)列线性无关。定理6.4(n,k