信息论与编码第八章 纠错编码

第八章纠错编码白慧慧办公地址：9号教学楼北605Email:hhbai@手机容提要一、纠错码的基本概念二、纠错编码的代数基础三、线性分组码四、循环码五、卷积码内容提要一、纠错码的基本概念二、纠错编码的代数基础三、线性分组码四、循环码五、卷积码1.信道纠错编码一、纠错码的基本概念2.差错控制系统模型及分类一、纠错码的基本概念2.差错控制系统模型及分类一、纠错码的基本概念2.差错控制系统模型及分类一、纠错码的基本概念2.差错控制系统模型及分类一、纠错码的基本概念2.差错控制系统模型及分类一、纠错码的基本概念3.差错类型一、纠错码的基本概念3.差错类型一、纠错码的基本概念4.纠错码的分类一、纠错码的基本概念4.纠错码的分类一、纠错码的基本概念内容提要一、纠错码的基本概念二、纠错编码的代数基础三、线性分组码四、循环码五、卷积码近世代数简介近世代数又称抽象代数，其研究对象是定义在某些运算下的集合，运算对象可以是数、多项式、矢量、矩阵、线性空间等。编码理论是建立在码的代数结构基础上的，为便于初学者理解，我们将简单介绍抽象代数中与编码直接相关的基础知识，主要涉及整数及多项式的一些基本概念及群、环、域的基本知识。二、纠错编码的代数基础1.群二、纠错编码的代数基础整数的相关概念1.群二、纠错编码的代数基础1.群二、纠错编码的代数基础群的定义1.群二、纠错编码的代数基础在实数加法下整数集是一个交换群。在这种情况下，整数0是单位元，整数-i是整数i的逆元。除去0的有理数集合在实数乘法下是交换群。整数1是关于实数乘法的单位元，有理数b/a是a/b的乘法逆元。1.群这样的二元运算称为模2(modulo-2)加法。集合G={0,1}在模2加法下是一个群。由模2加法的定义，G在下是封闭的，同时满足交换律、结合律。元素0是单位元，0的逆元是它本身，1的逆元也是它本身。这样，定义了的G是一个交换群。二、纠错编码的代数基础模2加1.群二、纠错编码的代数基础1.群二、纠错编码的代数基础1.群二、纠错编码的代数基础1.群令p为一个素数(例如p=2,3,5,7,11,…)二、纠错编码的代数基础模p乘易验证模p乘法满足交换律和结合律，其单位元是1。G中任何元素i关于模p乘法都有逆元。群G={1,2,3,…,p-1}在模p乘法下称为乘群(multiplicationgroup)1.群二、纠错编码的代数基础模p乘1.群二、纠错编码的代数基础群的同构1.群二、纠错编码的代数基础群的同构1.群二、纠错编码的代数基础子群1.群二、纠错编码的代数基础子群1.群二、纠错编码的代数基础群的陪集1.群二、纠错编码的代数基础群的陪集分解1.群二、纠错编码的代数基础群的陪集分解2.域二、纠错编码的代数基础域的定义2.域二、纠错编码的代数基础群和域的区别需要指出群(G)与域(F)的区别：一个群只有规定的一种代数运算(加法或乘法)，而域是有两种代数运算(加法和乘法)的代数系统。2.域二、纠错编码的代数基础群和域的区别2.域二、纠错编码的代数基础素数域G(p)2.域二、纠错编码的代数基础素数域G(p)3.环二、纠错编码的代数基础多项式的相关概念3.环二、纠错编码的代数基础多项式的相关概念3.环二、纠错编码的代数基础环的定义3.环二、纠错编码的代数基础整数剩余类环3.环二、纠错编码的代数基础多项式剩余类环3.环二、纠错编码的代数基础内容提要一、纠错码的基本概念二、纠错编码的代数基础三、线性分组码四、循环码五、卷积码1.分组码相关定义三、线性分组码假设信源信息是二进制数字序列，将信道编码器的输出序列构成长度为n的段，记为CC=[c1,c2,…,cn]设有m个不同的信息序列，每个不同的序列由k(k<n)位相继的信息数字组成。由于每个信息序列组成k位二进制数字，则有2k个可能不同的信息序列，即m=2k，这2k个码字的集合称为(n,k)分组码。(n,k)分组码定义1.分组码相关定义对于2k个n长码字全体构成的分组码，其码字中的k位称为信息位，n-k位称为校验位或监督位。例如，当k=3，n=7时，可能的消息序列数m=2k=8个，可能的长为n=7的预选序列有27=128个。具体如表：对于所选定的n长序列称为允许使用序列，即码字；而其他序列则是不允许使用的，即禁用序列。该例中，信息位为3，码长为7，监督位为4，如果用R=k/n表示码字中信息位所占比重，称为编码效率。表明了信道的利用率。三、线性分组码消息序列码字00000000000010011101010010011101101110101001001110101101001111011010011111110100校验位和信息位1.分组码相关定义若(n,k)分组码中k个信息位同原始k个信息位相同，且位于n长码字的前(或后)k位，而校验位位于其后(或前)，则称该分组码为系统码，否则为非系统码。右表所示为系统码。三、线性分组码消息序列码字00000000000010011101010010011101101110101001001110101101001111011010011111110100系统码与非系统码定义：[n,k]线性分组码是GF(q)上的n维线性空间中的一个k维子空间。2k2n2.线性分组码定义三、线性分组码2.线性分组码定义三、线性分组码也可以这样理解：n长码字C=[c1,c2,…,cn]中每一位同原始的k个信息位d=[d1,d2,…dk]之间满足一定的函数关系ci=f(d1,d2,…dk),(n=1,2,…,n)若函数关系是线性的，则称该分组码为线性分组码，否则为非线性分组码。2.线性分组码定义三、线性分组码2.线性分组码定义三、线性分组码2.线性分组码定义三、线性分组码容易验证C是线性的。假设消息序列与码字序列的映射关系为如下两种：第一种：映射关系为：第二种：映射关系与第一种截然不同。三、线性分组码2.线性分组码定义三、线性分组码3.线性分组码编码消息序列码字00000000000010011101010010011101101110101001001110101101001111011010011111110100三、线性分组码3.线性分组码编码由校验方程，可将n=7，k=3的线性分组码写成令则因此，C=mG且G=[IkPk*(n-k)]三、线性分组码3.线性分组码编码令则因此，C=mG三、线性分组码3.线性分组码编码三、线性分组码3.线性分组码编码三、线性分组码3.线性分组码编码消息序列码字00000000000010011101010010011101101110101001001110101101001111011010011111110100三、线性分组码3.线性分组码编码生成矩阵和校验矩阵关系例题已知生成矩阵为求其校验矩阵H，如果将H作为生成矩阵，则所生成的码字是什么？由于G=[IkPk*(n-k)]则有又因为由生成矩阵生成的(7,3)码为：mC00000000000010011101010010011101101110101001001110101101001111011010011111110100把校验矩阵当作生成矩阵，mC00000000000000100010110010001011000110011101010001001110101010110001100110001011101110101000100010110011001110101010100111011101100011001100010110111010011110111010011111111111产生(7,4)码为：（n，k）线性分组码编码电路4.伴随式与译码4.伴随式与译码4.伴随式与译码证明：根据线性分组码的封闭性可知，任意两个码字的和应为一个码字。根据码字之间距离的定义可知，两个码字和的非零个数则与其距离相等，且又为新码字的重量。所以，不难理解，线性分组码的最小距离必定等于非零码字的最小重量。4.伴随式与译码线性分组码的检、纠错能力与H矩阵的关系线性分组码的检、纠错能力与H矩阵的关系设C是线性分组码，H是它的校验矩阵，那么码C的最小重量就等于H中线性相关的最小列数。因此，如果H中的2t个和小于2t个列的任一子集都线性无关，而H中有2t+1个列线性相关，那么码C就是纠正t个错误的纠错码，或能检出2t个错误的检错码。【例】（7，4）线性分组码

H的前3列相加等于0，因此H线性相关的最小列数为3

故：wmin(C)=3

,能纠正1个错误或检出2个错误例：某一个(5,2)系统线性码的生成矩阵是设接收到码字是r=(10101)，先构造该码的标准阵列译码表，然后译出发码的估值C。(1)信息组：m=(00),(10),(01),(11)(2)求得4个许用码字C=mG为C1=(00000),C2=(10111

),C3=(01101),C4=(11010)(3)求出校验矩阵

(4)求出伴随式(5)标准阵列S1=000E1+C1=00000C2=10111C3=01101C4=11010S2=111E2=10000001111110101010S3=101E3=01000111110010110010S4=100E4=00100100110100111110S5=010E5=00010101010111111000S6=001E6=00001101100100111011S7=011E7=00011101000111011001S8=110E8=00110100010101111100选择重量最小的n重作为陪集首S=EHT【例】（7，3）线性分组码

能检出3重错误，纠正1重错误。

如：（一个错）如两个错：

，但无伴随式与之对应，不能纠正。

例已知（7，3）码的校验矩阵为若错误图样en=（0010000），则是H矩阵第三列！若错误图样中只有一个分量非零，则ST是H矩阵相应的列，因而能够纠正单个错误！若错误图样en=（0010100），则是H矩阵第三列与第五列之和！由定义可以求得，rn的伴随式：是H矩阵第一列与第二列之和！若发生两个错误，译码器只能判决传输有错（en

≠0）,不能判定由哪几位错误引起！一．基本概念汉明码：一类能纠单个错误的纠错码。

二．纠单个错误的线性分组码【例】（7，4）线性码

5.汉明码（1）H中列为非全零元素；

（2）H中任意两列都不相同，但存在相加等于0的三个列的子集。

H中线性相关的最小列数为3，故，该码是纠单个错误的码。定理：C是一个线性分组码，H是校验矩阵，C是可以纠单个错误的纠错码的充要条件：（1）H中没有元素全为0的列矢量；（2）H中任意两个列矢量都不相同。几个结论：对于具有纠单个错误能力的线性分组码。

（1）若接收矢量的伴随式，则译码器认为接收矢量没有错误；

（2）如果，且等于H矩阵中的某一列，则译码器纠认为接收矢量在该列对应校验矩阵中的位置出错，此时只需将接收字该位置的码元取反就能纠错；（3）若，但不等于H中的任一列，则错误不能纠正。【例】

（1）伴随式对应于H中的第五列，故：

（2）H中无对应列与之对应，不能正确译码。结论：为了得到具有纠一个错误的二元（n，n-m）线性码，（其中n-m=k，m为校验位的个数），只需从定义在F2上的m维非零列矢量中选取彼此不同的n个列矢量并依任意次序把它们排成一个m×n的矩阵：那么以H为校验矩阵的二元（n，n-m）线性码C就是一个可以纠正所有单个错误的的码。

三．汉明码：1．定义：设Vm(F2)是定义在F2上的一个m维的矢量空间

令H是二元m×（2m-1）矩阵，这个矩阵的列是Vm（F2）中按某种次序排列的2m-1个非零矢量，那么定义在F2上的n=2m-1，k=2m-1-m的线性分组码（校验矩阵为H）就称为长2m-1的汉明码。

设消息或数据以二进制形式表示，并以F2={0,1}表示这个二元集。如：

的（7，4）线性分组码就是汉明码

m=3，n=23-1=7，k=7-3=4

2．定理：二元（2m-1，2m-1-m）汉明码是能够纠单个错误的线性码，而且是校验位数为m的所有二元线性码种编码效率最高的码，其最小重量：wmin（C）=3。

3．完备码：设C是（n，k）线性分组码，其纠错能力为t，如果用且只用小于等于t个错误的全部错误图样作为陪集首就能做成标准阵列，那么称这个码为完备码。

四.汉明码的编译码电路框图编码器设计例(7,4)汉明码

由，2.译码器设计令接收字为

伴随式为

由校验矩阵H，

令1101000000011010000011100100001010001000100000010001000000100010000001

汉明码的译码电路框图

内容提要一、纠错码的基本概念二、纠错编码的代数基础三、线性分组码四、循环码五、卷积码1.循环码的定义定义一一个(n,k)线性分组码，如果每个码字经任意循环移位之后仍然在码字的集合中，那么就称此码是一个循环码。定义二设是某(n,k)线性分组码的码字集合，如果对于任何，它的循环移位，则称该码为循环码。这种循环性可以推广到任意次循环移位，记作：【例】（7，3）线性分组码由：得由两组码字循环构成的循环码。

2.码字的多项式描述对于任意个长度为n的码字，可用下列多项式来描述：这里，把各码元当作多项式的系数；x及其幂次数仅是码元位置的标记，我们并不关心它的取值；称系数不为零的x的最高次数为多项式A(x)的次数，或称为多项式的阶数。多项式的模运算示例如果A＝（an-1an-2

…a1a0）是（n，k）循环码的一个码字，则A(1)＝（an-2…a1a0an-1）也是该循环码的一个码字。这就是说A(x)＝an-1xn-1＋an-2xn-2＋…＋a1x＋a0和A

(1)(x)＝an-2xn-1＋…＋a1x2＋a0x＋an-1都是（n，k）循环码的码字多项式。循环多项式的模运算比较A(x)和A(1)(x)后可得

A

(1)(x)＝xA(x),modxn+1以及A(i)(x)＝xiA(x)（i＝1,2,…,n－1）,modxn+1

循环多项式的模运算定理：对于(n,k)循环码，若A(x)对应码字，对应A(x)的i次左循环移位，则等于除以后的余式，即：

例题：设循环码(7,4)中一个码字为[00001101]，则该循环码的所有码字及其码多项式如表所示。序号循环码左移位数i000110100011010101101002110100031010001401000115100011063.生成多项式和生成矩阵生成多项式记为g(x),所有循环码(n,k)的码多项式A(x)可由g(x)生成，即A(x)=m(x)g(x),式中，m(x)为消息多项式，它与消息位对应。生成多项式g(x)性质：循环码(n,k)的生成多项式是xn+1的一个因子，且最高次数为n-k。证明：由于A(x)=m(x)g(x),而m(x)最高次数为k-1，A(x)最高次数为n-1，所以g(x)最高次数为(n-1)-(k-1)=n-k。例：求循环码(7,4)的生成多项式g(x)解：将x7+1分解得x7+1=(x+1)(x3+x+1)(x3+x2+1)，因为g(x)最高次数为n-k=3，所以，其生成多项式有两种可能，即：x3+x+1或x3+x2+1由生成多项式g(x)容易得到生成矩阵。生成矩阵的每一行必定为线性无关的，且每行都是一个码字。g(x)为n-k阶多项式，则g(x),xg(x),x2g(x),…,xk-1g(x)必是线性无关的，将此对应的码字作为矩阵的每一行，得到生成矩阵。与生成矩阵对应的生成矩阵多项式G(x)可记作：3.生成多项式和生成矩阵例题：已知循环码(7,4)的生成多项式g(x)有两种可能

x3+x+1或x3+x2+1，分别求其生成矩阵解：若生成多项式g(x)=x3+x+1,则生成矩阵多项式为：所对应的生成矩阵为：例题：已知循环码(7,4)的生成多项式g(x)有两种可能

x3+x+1或x3+x2+1，分别求其生成矩阵解：若生成多项式g(x)=x3+x2+1,则生成矩阵多项式为：所对应的生成矩阵为：例题：如果循环码(7,4)的生成多项式g(x)=x3+x+1求对应的所有码字解：可得生成矩阵为16个码字构成4个循环组，前两组分别7个码字，后两组为自循环的单独码字。可见，循环码并不是只由一个码字循环就可以得到全部码字。将生成矩阵通过矩阵初等变换转换成[IkPk*r]的形式，即可得到系统生成矩阵。3.生成多项式和生成矩阵生成多项式g(x)生成矩阵多项式G(x)生成矩阵G系统生成矩阵G’解：可以先得到两个生成矩阵，后经过矩阵初等变换得到系统生成矩阵例题：已知循环码(7,4)的生成多项式g(x)有两种可能

x3+x+1或x3+x2+1，分别求其系统生成矩阵矩阵初等变换矩阵初等变换通过比较，可以发现，对于生成矩阵G1及系统生成矩阵G1’,最后所生成的码字相同，唯一不同的是消息位与码字的对应关系不同。由生成多项式g(x)直接产生系统循环码步骤：(1)将消息多项式m(x)乘以xn-k；(2)将xn-km(x)除以g(x)得到余式r(x)；(3)将r(x)加进xn-km(x)，得到系统码。解:(1)消息码为[1101]，所以消息多项式为m(x)=x3+x2+1，则xn-km(x)=x3m(x)=x6+x5+x3

(2)求余式

(3)求系统码多项式C(x)=xn-km(x)+r(x)=x6+x5+x3+1所以对应的系统循环码为[1101001]例题：如果循环码(7,4)的生成多项式g(x)=x3+x+1，消息码为[1101]，求对应的系统循环码4.校验多项式和校验矩阵4.校验多项式和校验矩阵4.校验多项式和校验矩阵5.伴随多项式和伴随矩阵伴随多项式S(x)与收到的码多项式R(x)同余伴随多项式S(x)与差错图样多项式E(x)之间也存在一一对应关系5.伴随多项式和伴随矩阵循环码译码步骤(1)利用，建立差错图样多项式E(x)和伴随多项式S(x)之间的映射表；(2)收到R(x)后，利用得到某个S(x)，然后利用步骤(1)中建立的映射表，即可查到所对应的差错多项式E(x);(3)将差错多项式E(x)与R(x)相加，即可得到经过纠错的C(x)。解，由得到例题：如果循环码(7,4)的生成多项式g(x)=x3+x+1，确定差错图样多项式与伴随多项式的映射表差错图样多项式E(x)伴随多项式S(x)0011xxx2x2x3x+1x4x2+xx5x2+x+1x6x2+1若已知伴随多项式S(x)，可以容易求得对应的伴随矩阵S。例如，S(x)=x2+x+1,则伴随矩阵S=[111]当然，由于循环码是线性分组码的子类，所以，伴随矩阵仍可以由S=RHT求得。5.伴随多项式和伴随矩阵6.BCH码和RS码BCH码是循环码中的一个大类，分为二进制BCH码和非二进制BCH码(例如RS码)。二进制BCH码可记为(2m-1,k)，其中m为正整数且，即码长n=2m-1，且(t为可纠正的差错数)，t由最小码距决定，即二进制BCH码的优点是，具有纠正多个随机差错的能力。具有严谨的代数结构，可以按照码长n和纠错能力t直接将BCH码构造出来。该特点优于一般线性分组码，一般线性分组码在设计出来之后，需要计算最小距离dmin，才能知道纠错能力。若不符合要求，还要重复设计过程。6.BCH码和RS码确定BCH码的生成多项式g(x)，取决于两方面：(1)g(x)是xn+1因式中最高阶为n-k的多项式，这是任何循环码都必须满足的条件。由于BCH码的码长n=2m-1，，所以其码长的取值只能是7,15,31,63,127,255,…当n较大时，xn+1的因式分解就只能用计算机来计算。(2)g(x)必须满足对纠错能力t的要求，即对最小码距的要求。实际应用中，将满足上述两个条件的系数整理成“BCH码生成多项式系数”表，以便查用。例题：求码长为15且能纠正3个差错的BCH码解：码长n=2m-1=15，所以m=4；纠错能力t=3；将x15+1因式分解后，得x15+1=(x+1)(x2+x+1)(x4+x+1)(x4+x3+1)(x4+x3+x2+x+1)查前述的“BCH码生成多项式系数”表，可得满足条件的BCH码为(15,5)，其相应的生成多项式的最高阶为n-k=10，则生成多项式为g(x)=(x2+x+1)(x4+x+1)(x4+x3+x2+x+1)=x10+x8+x5+x4+x2+x+16.BCH码和RS码RS(Reed-Solomn)码是一种非二进制BCH码。RS码是极大最小距离码(MDC码)。若某个码的最小距离dmin=n-k+1，则称线性分组码(n,k)为极大最小距离码。在(n,k)线性分组码中，极大最小距离码具有最大的检错、纠错能力。由于RS码是多进制，所以很容易与M进制调制技术相匹配；RS码特别适合纠正突发错误。内容提要一、纠错码的基本概念二、纠错编码的代数基础三、线性分组码四、循环码五、卷积码卷积码与线性分组码的比较卷积码线性分组码表示符号(n,k,K)，K为约束长度(n,k)记忆性有记忆，输出的n个比特不仅与当前输入的k比特有关，而且与以前输入的K个k比特有关无记忆，输出的n个比特仅与当前输入的k个比特有关(可视为K=0时的无记忆卷积码)代数结构无严格的代数结构，目前多采用计算机来搜索好码，缺乏有效的数学分析工具有严格的代数结构，借用数学工具研究较为透彻编码效率kk…kn…输入k位当前时间以前K个时间输入n位kn输入k位输入n位卷积码线性分组码1.卷积码的组织结构卷积码(n,k,K)与线性分组码(n,k)的重要区别在于，卷积码是有记忆的，并用约束长度表示记忆长度，记为K。输出的n位比特不仅与当前时间输入的k比特有关，还与以前时间输入的多个k比特有关，到底与以前多长时间有关，就由约束长度K来度量。卷积码可以视为多个线性分组码的线性叠加，只不过多个线性分组码是来源于同一个输入源的多个不同时间段(包括当前时间段和K个以前时间段)。显然，当K=0时，卷积码就退化为线性分组码。例题：设卷积码(2,1,2)，其组织结构如图(a)所示，假设输入序列为[1011]，通过求输出序列，来说明卷积码编码的全过程10011010011011011010011000010100000(a)(b)(c)(d)(e)(f)(g)从(a)到(d)依次输入[1011]，从(e)到(f)是为了清空K段缓存器，所以需要在输入序列后加K段0比特，称为“结尾清空处理”过程。另外，(g)中又输入0的目的是说明该时刻已完成“结尾清空处理”，即在该时刻可以输入新的消息。由上例中看到，当输入[1011]时，输出为110110100001，因此，该卷积码的编码效率为：对L段输入消息码进行编码，每段消息码长度为k比特，因此有效消息共Lk比特。经过编码后，产生了Ln个比特，但由于“结尾清空处理”额外输入的K段全“0”数据，因此总共产生的数据为(L+K)n比特。当K=0时，卷积码的编码效率为：与线性分组码一致。

2.卷积码的解析表示法(1)生成矩阵表示法(2)生成多项式表示法(3)冲激响应表示法(1)生成矩阵表示法卷积码为线性码，可通过