第六章信道编码

（1）信道编码目的：提高通信系统传输的可靠性；（2）目标：寻找具体构造编码的理论与方法；只要当实际传信率R<C（信道容量），无差错的信道编、译码是存在的。（3）信道编码原理：根据一定的规律在待发送的信息码元中人为的加入一定的多余码元，以保证在传输中，发送码元的可靠性。（4）信道编码任务：就是构造出以最小冗余度代价换取最大抗干扰性能的好的码字第六章信道编码§6.1概述信道编码又称纠错编码，是提高数字传输可靠性的一种技术一.有扰离散信道的信道编码定理(香农第二定理)在信息传输速率小于信道容量的条件下，可通过增加代码组长度m的编码方法，使得接收端恢复消息的误码率小于任意给定的小数ε。反之，若信息传输速率大于信道容量时，则误码率为一固定值，即使增加代码组长度m也不能使误码率任意小该定理也就是说，只要R<C，就存在速率为R的纠错码收端结论：不重复，方法简单，但没有任何抗干扰能力，既不能发现，更不能纠正错误。—不重复时例：简单的信道编码（重复码）—重复一次：发端收端能发现一个错结论：重发一次，效率降低一倍。可以换取在传输过程中允许产生一个错误（收端能发现它），但不能纠正。—重复二次：发端收端能纠正一个错或发现两个错结论：重发二次，效率降低二倍，但换取了可纠正一个差错或发现两个差错的性能改善。说明：由此可见，纠错编码之所以具有检错和纠错能力，是因为在信息码之外附加了校验码（监督码）。校验码不荷载信息，它的作用是用来监督信息码在传输中有无差错，对用户来说是多余的，最终也不传送给用户，但它提高了传输的可靠性。校验码的引入，降低了信道的传输效率。一般来说，引入校验码元越多，码的检错、纠错能力越强，但信道的传输效率下降也越多。人们研究的目标是寻找一种编码方法使所加的校验码元最少,而检错、纠错能力又高且又便于实现。

二.通信系统三.错误的种类若发送码字v＝(11000)接收矢量r＝(10001)由于噪声，出现两个错误设v＝(v1，v2，v3，…，vn)r＝(r1，r2，r3，…，rn)e＝v+r＝(v1+r1，v2+r2，v3+r3，…，vn+rn)

若ei＝vi+ri＝1，则表示码字中第i位受到干扰，出现错误错误类型先检错，后纠错

检错码——有发现错误能力的码。通常用检错码的通信系统必须具有反馈信道。当发现收到消息有错误时，接收端通过反馈信道发出一个信号，要求发送端把消息再次发送，直到接收端认为正确为止。

纠错码——有发现并纠正错误能力的码随机错误——由随机噪声引起的(各码元是否发生错误是相互独立的，不会成片的出现错误)突发错误——由突发噪声引起的(各码元是否发生错误存在相关性，错误成片出现)

四.纠错码的分类校验位与信息位的关系线性码——校验位与信息位之间呈线性关系非线性码——校验位与信息位之间不存在线性关系对信息位处理方法分组码——如码组长度为n位，信息位数为k，则每一码组

的(n－k)个校验位与本码组的k个信息位有关卷积码——如码段长度为n0位，该段有k0个信息位，则该

码一个码段的(n0－k0)个校验位不仅与本段的

k0个信息位有关，而且与前m段的信息位有关码字之间的关系循环码非循环码按纠错码的类型纠随机错误码纠突发错误码纠随机与突发错误码(n,k)编码后信息码元是否保持原样系统码非系统码1）域：域是由一些元素所构成的集合，在集合里，可以定义任意两个元素在某种意义上的加法和乘法，则这个集合称为域。记做：F。F中的成员叫做元素或简称元。域中任意两个元素的和、积仍是域中的元素，并且满足交换律和分配律。常用的有F2常用的运算包括：模2加2）阶：域F中元素的个数叫做F的阶.基本概念3）有限域：如果F的阶是有限的，就把F叫做有限域。也称伽罗华域4）线性无关：对于域F上的若干矢量，若满足（非零系数）：则称V1,V2,…,Vi矢量线性相关，否则称线性无关。码重是指码字中所含“1”的数目，比如：

（5）码重汉明重量

设码字v＝(v0，v1，v2，…，vn-1)∈Vn(F2)，令w(v)为码字v中那些不为0的码元个数，即则称w(v)是码字v的汉明重量，简称重量而称C中那些不等于0的码字的重量的最小值wmin(v)为C的最小重量

任一码字的汉明重量都可以看作是该码字与0码字间的汉明距离若v＝(0111000)则w(v)＝3；u＝(1000111)则w(u)＝4

（6）码距：码距是指两个码字Ci与Cj中相应码元不相同的数目。比如：（2，1）重复码（1，1）重复码（3，1）重复码

汉明距离设a和b是集合Vn(F2)中的任意两个码字，令a＝(a0，a1，a2，…，an-1)b＝(b0，b1，b2，…，bn-1)

并规定d(a，b)表示a和b的各相应码元之间不相同的个数，即我们把d(a，b)称为a和b之间的汉明距离，简称距离性质1.自反性对任意a∈Vn(F2)d(a，a)＝02.对称性对任意a，b∈Vn(F2)d(a，b)＝d(b，a)3.三角不等式对任意a，b，c∈Vn(F2)d(a，b)+d(b，c)＝d(a，c)

例：u＝（10010110001）v＝（11001010101）d(u，v)＝5

①纠随机错误码设码字间的最小距离为dmin，则该码的纠错能力t(即具有纠t个随机错误的能力)可用下式表示：该码的检错能力t，可用下式表示：dmin是指在某码范围内，所有可能的汉明距离中的最小数值②纠突发错误码设n为码字的位数，k为信息位数，该码的纠错能力(能纠正长l位的突发错误)可用下式表示：

③纠随机与突发错误码以交错码为例，如能把纠t个错误的(n，k)码中λ个码字作为矩阵的λ行，然后按列发送，就可构成(λn，λk)交错码。即构成即能纠t个随机错误，又能纠t个长为λ的突发错误码为什么要引入线性码发现或构造好码是信道编码研究的主要问题编码方案太多，以至全局搜索是不可能的，现实的做法是对编码方案加以一定的约束，在一个子集中寻找局部最优。这种约束即要能包含尽可能好的码，又要便于分析，便于译码。目前对线性系统的研究远比非线性系统充分假设有M个等概率出现的消息，长度都为k位，存在M＝2k加上r个多余位，每个码字长度k+r＝n位。这就使n位的二进制数字序列共有2n个，但可能的消息数只有2k个，故只能有2k个码字（即(2n－2k)个n位序列不是码字）§6.2线性分组码

线性特性——码组内校验码与信息码间为线性关系分组特性——每码组内的校验码只与本组信息码有关，与其他码组无关。表示——(n,k)线性分组码信息码k位，码组n位

此时的码字形式为：m1m2…mkp1p2…pr，mi表示第i个信息位，pj表示第j个校验位。各个校验位，可从下列线性方程组求得：

式中hij是常数，等于0或1。式中每个方程都代表校验位(p1p2…pr)和信息位(m1m2…mk)之间的线性关系一、线性分组码数字结构（1）校验矩阵

从方程组可写成校验矩阵：该矩阵具有r行，n列，是码的一种数学结构若把码字写成行向量，有：v＝（m1m2…mkp1p2…pr）则方程组可写成：vHT＝0或HvT＝0此式中设v为发送矢量，若信道无干扰，接收矢量r就是vrHT≠0发生错误（≥1个）

rHT＝0无错误错误太大，无法检出错误

纠正错误的方法设发送矢量为v，接收矢量为r，出现的信道错误为e，则有下列关系式：r＝v+e为了纠错，必须知道r中哪些位上存在错误，这可由校正子(伴随式)s来确定s＝rHT＝eHT+vHT＝eHT令设r第i位是错误的，因此错误图样为e＝(00…010…0)（第i位为1）

例：设要把16个等概率出现的消息构造成线性分组码，设信息位为k，校验位为r,码子长度为n=k+r。解：从题意可知，16＝2k，k＝4。为了纠正一个错误，r＝2，即n＝4+2＝6。这种编码方式不行，校验矩阵H只有2行，6列，无法排出各不相同的6列。6列各不相同，主要目的是使校正子s能定出错误位置进行纠正（即存在相同列时，无法判断到底哪一列出错！）若r＝3，可排出（7，4）分组码的校验矩阵H：

如消息为1010，则从上列关系可得出：即可得码字为1010010该码编码方法如下：下表列出了（7，4）码的24＝16个码字对于纠错，从表中看出最小汉明距离dmin＝3故根据式，该码能纠正个错误如接收矢量r＝(1010111)，则由s可知，发送矢量应为(1000111)

生成矩阵G是码的另一种数学结构，它是k行，n列的矩阵

(n，k)线性码的码字都可由G中各行的线性组合生成，即码字＝(消息组)×(生成矩阵)线性分组码数字结构（2）：生成矩阵

生成矩阵与校验矩阵之间可以相互转换

式中PT为P的转置矩阵，Ir×r和Ik×k为单位矩阵例：例：若校验矩阵H为

则生成矩阵G为用生成矩阵G也可求得码字，若m1m2m3m4＝1010

生成矩阵G和校验矩阵H的关系生成矩阵G一般用于发端编码，而检验矩阵H则一般用于接收端的译码。由于生成矩阵G中的每一行及其线性组合都是线性（n,k）码的码组（字），所以根据公式H·vT=OT(v=m×G)有H·GT=OT它说明矩阵G与H互为零空间由线性空间理论，一个n维的线性空间Vn可以分解为一对互为对偶的正交子空间Vk与Vn-k。即：

互为对偶码可构成(7,3)线性分组码可构成(7,4)线性分组码显然有：(7,3)码的生成矩阵G3就是(7,4)码校验矩阵H’3，(7,3)码的校验矩阵H4就是(7,4)码的生成矩阵G’4可构成(n,k)线性分组码可构成(n,n-k)线性分组码互为对偶码结合上面n=7的例子,则有二、线性分组码及其检、纠错能力的获得一般来说，编码器将k位消息u=（u0,u1,…,uk-1)映射成n位数字组v=(v0,v1,…,vn-1)所依据的规则不外乎是一组函数关系或一种对应关系例：设一个（6，3）分组码的编码规则为如果把分组消息序列(u0，u1，u2)映射成码序列(v0，v1，…，v5)的关系用矩阵表示，有：此例中v0，v1，v2是消息位，v3，v4，v5是校验位写成齐次，以矩阵表示：例：设一个原始数字消息为u0，其编码规则为：它是一个(n，1)线性分组码，是一个重复码例：它是一个(n，n－1)线性码，是奇偶校验码。

此例中所定义的每个码字中，1的个数一定是偶数，当接收到一个码字中1的个数若不是偶数，可确定它不是码字，它只能检出单个或奇数个错误，但不能发现偶数个错误重复码——编码效率η＝1/n，这是长为n的分组码中效率最低的，纠错能力强奇偶校验码——编码效率η＝n-1/n，这是长为n的分组码中效率最高的，纠错能力低

纠错编码的中心任务——要在这两个极端类型的码之间寻找一些性能良好的码，使我们可根据不同干扰特性的信道，设计出编码效率高、抗干扰能力好而编译码设备又简单的码这两种编码方式是线性分组码的两个极端类型先引入信道错误图样的概念。所谓信道错误图样，就是长为n的二元序列：如果其中某个元的数字为1，则表示该位出现错误。序列中1的个数称为错误图样的错误重数，但重数为t时，就称该图样为t重错误。在引入错误图样的概念后，任何由码字出现错误而得到的接收字都可以表示为码字和错误图样的模2加。码字C在传输过程中受到各种干扰，接收端的收码r不一定等于发码，两者之间的差异定义为差错e。e=r－C对于二进制，模2减等于模2加，所以：e=r＋Cr=C+e又有CHT＝0收码无误收码有误定义S=rHT的运算结果为伴随式。译码过程如下图所示计算SC=r+e计算eCer输出可知，这是n=2的重复码，也是（2，1）奇偶校验码，所以它只能发现一个错误，但无法纠正。①在集合{ei+vj,i=1,2,…,6}(j=1,2)中，设有vj(j=1,2)，因而当信道出现错误ei，i=1,2,…,6时，可以发现此时的接收字是错误的，从而可以检出所有不多于二个的错误；②在集合{ei+v1,i=1,2,3}和集合{ei+v2,i=1,2,3}中没有码字v1/v2，而且它们之间也没有公共的接收字。因此，可以将接收字ei+vj（i=1,2,3）判定为vj，从而可以纠正所有单重错误的错误图样e1，e2和e3；③但是，这个码并不兼有能纠正所有单重错误并检出所有二重错误的能力。例如：如有e4+v1＝e3+v2，就可能将e4+v1误认为v2。(1)要使码具有检、纠错能力，必须附加多余的码元，即增加消息的冗余度，这相当于n>k。而且一般来说，码的冗余度越大，检、纠错能力就越强；(2)任何一种检错或纠错码都不可能检出或纠正所有的错误。事实上，如果码中至少有两个码字v1和v2。则错误图样e=v1+v2，就不能够被检出或纠正；(3)如果错误图样集{ei,i=1,2,..,l}使得每个码字vj(j=1,2,…,m)变成的接收字集{ei＋vj}中不包含码字vj，则这个码就可以检出所有的错误图样ei；(4)如果错误图样集{ei,i=1,2,..,l}使得任一对码字vj，vk变成的接收字集{ei＋vj}和{ei＋vk}之间无公共的接收字，而且不含任一码字，那么就只需要把ei＋vj判为vj；(5)如果错误图样集可以分为无公共部分的集{ei,i=1,2,..,l}和集{e’i,i=1,2,..,l’}，而且码字集{vj,j=1,2,…,m}对于{ei,i=1,2,..,l}满足第4点，则该码可以纠正所有ei，并且对集{e’i,i=1,2,..,l’}有如下的性质：任一码字vj的相应接收字集{e’i＋vj}中都不含{ei＋vr}（r≠j）中的接收字以及vr，则此码可兼有纠正所有的错误图样ei和检出所有的错误图样e’i三、线性分组码的检、纠错能力最小距离dmin与码率R是码的两个最主要参数，dmin表示了码的纠错能力。用（n，k，d）表示距离为d，码率R＝k／n的线性分组码。纠错码的基本任务之一就是构造出R一定且dmin尽可能大的码，或dmin一定且R尽可能大的码。检测e个错误，则要求最小码距：dmin≥e＋1编码的最小码距为dmin，则最多能检出（dmin-1）个错误。e+1eC1(a)纠正t个错码，则要求最小码距为：

dmin≥2t＋12t+11ttC1C2纠正t个错码，同时能检测e(e>t)个错码，则要求最小码距为dmin≥e＋t＋1,e>te+t+11etC1C2定理：线性分组码的最小距离等于码中码字的最小重量。定理：(n，k，d)线性分组码有最小距离dmin的充要条件是H矩阵中任意d－1列线性无关，存在d列线性相关。推论：(n，k，d)线性分组码的最小距离dmin≤n－k＋1。若系统码的最小距离dmin＝n－k＋1，则称此码为极大最小距离可分码，简称MDS码。定理：设C是个线性分组码，H是它的校验矩阵，那么C是可以纠正单个错误的纠错码的充要条件是H中没有元素全为0的列矢量，且H的任意两个列矢量都不相同定义：令H是个二元r×(2r-1)矩阵，这个矩阵的列是Vm(F2)中按某种次序排列的2r-1个非零矢量。那么，定义为F2上的n＝2r-1，k＝2r-1-r的线性分组码(其校验矩阵为H)，就称为长2r-1的汉明码设线性码的校验矩阵四.常用线性分组码-------汉明码汉明最早提出的一类能纠正单个错误的纠错码如果接收矢量r＝(101000101)，根据s＝rHT有s＝(1100)，即r中第五位数出错，经纠错后r＝(101010101)如果接收矢量r＝(001000101),根据s＝rHT有s＝(1101)，s不等于H中任意一列，实际上该码有两个错误定理：二元(2r-1，2r-1-r)汉明码是能纠正所有单个错误的线性码，而且是校验位数为r的所有二元线性码中编码效率最高的码,它的最小重量为3汉明码是一种特殊的(n，k，d)线性分组码，在多进制（m进制）中，它的参数n，k和d分别为:构造一个二元的（7，4，3）汉明码。根据已知条件知，r＝n－k＝3，所以有23＝8个元素，除全0以外的所有其余7个元素，均可作为校验矩阵Ｈ的列，所以该码的校验矩阵为：求三进制r＝3的汉明码的参数及H矩阵和G矩阵。n=13，k=10汉明码dmin＝3，只要任意两列线性无关就行，所以可以直接写出H矩阵(不是惟一的)：循环码是线性分组码中最主要，最有适用价值的一类，它是1957年由Prange首先提出。在循环码中BCH码是其中最主要的一大类。汉明码、R―M码、Golay码、RS码等均可变换成或纳入循环码内，1970年发现的Goppa码类中有一子类也属于循环码。§6.3循环码

基本定义：一个（n,k）线性分组码，若满足循环移位特性：码集C中任何一个码字循环移位后仍是码字，则称它为循环码主要特点1）理论成熟：可利用成熟的代数结构深入探讨其性质；2）实现简单；可利用循环移位特性在工程上进行编，译码；3）循环码的描述方式有很多，但在工程上可采用最有用的多项式的描述方法。一一对应：

n元码组(字)n阶(含0阶)码多项式

有限域多项式域模运算码组模2运算多项式乘积运算循环码（续）—个n维码字C＝(cn－1，cn－2，…，c1,c0)的分量循环右移一位就可以得到：RC(1)＝(c0，cn－1,cn－2,…，c2,c1)将矢量C循环左移1位后就得到：SC（i）＝(cn－2，cn－3,…，c1,c0，cn－1)RC（n-i）＝SC（i）循环码（续）在多项式描述中，我们可以将“同余”（模）运算推广到多项式中。即循环码（续）例：则有下列多项式除法:循环码（续）（7，3）码循环移位特性根据循环码的循环特性，可由一个码字的循环移位得到其他非0码字。在(n，k)循环码的2k个码多项式中，取前k-1位皆为0的码多项式g(x)(其次数r＝n-k)，再经k-1次循环移位，共得到k个码多项式:g(x)，xg(x)，…,xk-1g(x)。这k个码多项式显然是相互独立的，可作为码生成矩阵的k行。于是得到(n，k)循环码的生成矩阵G(x)为：（n,k)循环码可由一个(n-k)次码多项式g(x)来确定，所以称g(x)为生成多项式。例:设(7,4)循环码生成多项式为

，求其生成矩阵和