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

信息论与编码第八章纠错编码第一页，共一百四十一页，2022年，8月28日内容提要一、纠错码的基本概念二、纠错编码的代数基础三、线性分组码四、循环码五、卷积码第二页，共一百四十一页，2022年，8月28日内容提要一、纠错码的基本概念二、纠错编码的代数基础三、线性分组码四、循环码五、卷积码第三页，共一百四十一页，2022年，8月28日1.信道纠错编码一、纠错码的基本概念第四页，共一百四十一页，2022年，8月28日2.差错控制系统模型及分类一、纠错码的基本概念第五页，共一百四十一页，2022年，8月28日2.差错控制系统模型及分类一、纠错码的基本概念第六页，共一百四十一页，2022年，8月28日2.差错控制系统模型及分类一、纠错码的基本概念第七页，共一百四十一页，2022年，8月28日2.差错控制系统模型及分类一、纠错码的基本概念第八页，共一百四十一页，2022年，8月28日2.差错控制系统模型及分类一、纠错码的基本概念第九页，共一百四十一页，2022年，8月28日3.差错类型一、纠错码的基本概念第十页，共一百四十一页，2022年，8月28日3.差错类型一、纠错码的基本概念第十一页，共一百四十一页，2022年，8月28日4.纠错码的分类一、纠错码的基本概念第十二页，共一百四十一页，2022年，8月28日4.纠错码的分类一、纠错码的基本概念第十三页，共一百四十一页，2022年，8月28日内容提要一、纠错码的基本概念二、纠错编码的代数基础三、线性分组码四、循环码五、卷积码第十四页，共一百四十一页，2022年，8月28日近世代数简介近世代数又称抽象代数，其研究对象是定义在某些运算下的集合，运算对象可以是数、多项式、矢量、矩阵、线性空间等。编码理论是建立在码的代数结构基础上的，为便于初学者理解，我们将简单介绍抽象代数中与编码直接相关的基础知识，主要涉及整数及多项式的一些基本概念及群、环、域的基本知识。二、纠错编码的代数基础第十五页，共一百四十一页，2022年，8月28日1.群二、纠错编码的代数基础整数的相关概念第十六页，共一百四十一页，2022年，8月28日1.群二、纠错编码的代数基础第十七页，共一百四十一页，2022年，8月28日1.群二、纠错编码的代数基础群的定义第十八页，共一百四十一页，2022年，8月28日1.群二、纠错编码的代数基础在实数加法下整数集是一个交换群。在这种情况下，整数0是单位元，整数-i是整数i的逆元。除去0的有理数集合在实数乘法下是交换群。整数1是关于实数乘法的单位元，有理数b/a是a/b的乘法逆元。第十九页，共一百四十一页，2022年，8月28日1.群这样的二元运算称为模2(modulo-2)加法。集合G={0,1}在模2加法下是一个群。由模2加法的定义，G在下是封闭的，同时满足交换律、结合律。元素0是单位元，0的逆元是它本身，1的逆元也是它本身。这样，定义了的G是一个交换群。二、纠错编码的代数基础模2加第二十页，共一百四十一页，2022年，8月28日1.群二、纠错编码的代数基础第二十一页，共一百四十一页，2022年，8月28日1.群二、纠错编码的代数基础第二十二页，共一百四十一页，2022年，8月28日1.群二、纠错编码的代数基础第二十三页，共一百四十一页，2022年，8月28日1.群令p为一个素数(例如p=2,3,5,7,11,…)二、纠错编码的代数基础模p乘易验证模p乘法满足交换律和结合律，其单位元是1。G中任何元素i关于模p乘法都有逆元。群G={1,2,3,…,p-1}在模p乘法下称为乘群(multiplicationgroup)第二十四页，共一百四十一页，2022年，8月28日1.群二、纠错编码的代数基础模p乘第二十五页，共一百四十一页，2022年，8月28日1.群二、纠错编码的代数基础群的同构第二十六页，共一百四十一页，2022年，8月28日1.群二、纠错编码的代数基础群的同构第二十七页，共一百四十一页，2022年，8月28日1.群二、纠错编码的代数基础子群第二十八页，共一百四十一页，2022年，8月28日1.群二、纠错编码的代数基础子群第二十九页，共一百四十一页，2022年，8月28日1.群二、纠错编码的代数基础群的陪集第三十页，共一百四十一页，2022年，8月28日1.群二、纠错编码的代数基础群的陪集分解第三十一页，共一百四十一页，2022年，8月28日1.群二、纠错编码的代数基础群的陪集分解第三十二页，共一百四十一页，2022年，8月28日2.域二、纠错编码的代数基础域的定义第三十三页，共一百四十一页，2022年，8月28日2.域二、纠错编码的代数基础群和域的区别需要指出群(G)与域(F)的区别：一个群只有规定的一种代数运算(加法或乘法)，而域是有两种代数运算(加法和乘法)的代数系统。第三十四页，共一百四十一页，2022年，8月28日2.域二、纠错编码的代数基础群和域的区别第三十五页，共一百四十一页，2022年，8月28日2.域二、纠错编码的代数基础素数域G(p)第三十六页，共一百四十一页，2022年，8月28日2.域二、纠错编码的代数基础素数域G(p)第三十七页，共一百四十一页，2022年，8月28日3.环二、纠错编码的代数基础多项式的相关概念第三十八页，共一百四十一页，2022年，8月28日3.环二、纠错编码的代数基础多项式的相关概念第三十九页，共一百四十一页，2022年，8月28日3.环二、纠错编码的代数基础环的定义第四十页，共一百四十一页，2022年，8月28日3.环二、纠错编码的代数基础整数剩余类环第四十一页，共一百四十一页，2022年，8月28日3.环二、纠错编码的代数基础多项式剩余类环第四十二页，共一百四十一页，2022年，8月28日3.环二、纠错编码的代数基础第四十三页，共一百四十一页，2022年，8月28日内容提要一、纠错码的基本概念二、纠错编码的代数基础三、线性分组码四、循环码五、卷积码第四十四页，共一百四十一页，2022年，8月28日1.分组码相关定义三、线性分组码假设信源信息是二进制数字序列，将信道编码器的输出序列构成长度为n的段，记为CC=[c1,c2,…,cn]

设有m个不同的信息序列，每个不同的序列由k(k<n)位相继的信息数字组成。由于每个信息序列组成k位二进制数字，则有2k个可能不同的信息序列，即m=2k，这2k个码字的集合称为(n,k)分组码。(n,k)分组码定义第四十五页，共一百四十一页，2022年，8月28日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校验位和信息位第四十六页，共一百四十一页，2022年，8月28日1.分组码相关定义若(n,k)分组码中k个信息位同原始k个信息位相同，且位于n长码字的前(或后)k位，而校验位位于其后(或前)，则称该分组码为系统码，否则为非系统码。右表所示为系统码。三、线性分组码消息序列码字00000000000010011101010010011101101110101001001110101101001111011010011111110100系统码与非系统码第四十七页，共一百四十一页，2022年，8月28日定义：[n,k]线性分组码是GF(q)上的n维线性空间中的一个k维子空间。2k2n2.线性分组码定义三、线性分组码第四十八页，共一百四十一页，2022年，8月28日2.线性分组码定义三、线性分组码也可以这样理解：n长码字C=[c1,c2,…,cn]中每一位同原始的k个信息位d=[d1,d2,…dk]之间满足一定的函数关系ci=f(d1,d2,…dk),(n=1,2,…,n)

若函数关系是线性的，则称该分组码为线性分组码，否则为非线性分组码。第四十九页，共一百四十一页，2022年，8月28日2.线性分组码定义三、线性分组码第五十页，共一百四十一页，2022年，8月28日2.线性分组码定义三、线性分组码第五十一页，共一百四十一页，2022年，8月28日2.线性分组码定义三、线性分组码第五十二页，共一百四十一页，2022年，8月28日容易验证C是线性的。假设消息序列与码字序列的映射关系为如下两种：第一种：映射关系为：第二种：映射关系与第一种截然不同。第五十三页，共一百四十一页，2022年，8月28日三、线性分组码2.线性分组码定义第五十四页，共一百四十一页，2022年，8月28日三、线性分组码3.线性分组码编码消息序列码字00000000000010011101010010011101101110101001001110101101001111011010011111110100第五十五页，共一百四十一页，2022年，8月28日三、线性分组码3.线性分组码编码由校验方程，可将n=7，k=3的线性分组码写成令则因此，C=mG且G=[IkPk*(n-k)]第五十六页，共一百四十一页，2022年，8月28日三、线性分组码3.线性分组码编码令则因此，C=mG第五十七页，共一百四十一页，2022年，8月28日三、线性分组码3.线性分组码编码第五十八页，共一百四十一页，2022年，8月28日三、线性分组码3.线性分组码编码第五十九页，共一百四十一页，2022年，8月28日三、线性分组码3.线性分组码编码消息序列码字00000000000010011101010010011101101110101001001110101101001111011010011111110100第六十页，共一百四十一页，2022年，8月28日三、线性分组码3.线性分组码编码生成矩阵和校验矩阵关系第六十一页，共一百四十一页，2022年，8月28日例题已知生成矩阵为求其校验矩阵H，如果将H作为生成矩阵，则所生成的码字是什么？由于G=[IkPk*(n-k)]则有又因为第六十二页，共一百四十一页，2022年，8月28日由生成矩阵生成的(7,3)码为：mC00000000000010011101010010011101101110101001001110101101001111011010011111110100第六十三页，共一百四十一页，2022年，8月28日把校验矩阵当作生成矩阵，mC00000000000000100010110010001011000110011101010001001110101010110001100110001011101110101000100010110011001110101010100111011101100011001100010110111010011110111010011111111111产生(7,4)码为：第六十四页，共一百四十一页，2022年，8月28日第六十五页，共一百四十一页，2022年，8月28日（n，k）线性分组码编码电路第六十六页，共一百四十一页，2022年，8月28日第六十七页，共一百四十一页，2022年，8月28日4.伴随式与译码第六十八页，共一百四十一页，2022年，8月28日4.伴随式与译码第六十九页，共一百四十一页，2022年，8月28日4.伴随式与译码证明：根据线性分组码的封闭性可知，任意两个码字的和应为一个码字。根据码字之间距离的定义可知，两个码字和的非零个数则与其距离相等，且又为新码字的重量。所以，不难理解，线性分组码的最小距离必定等于非零码字的最小重量。第七十页，共一百四十一页，2022年，8月28日4.伴随式与译码第七十一页，共一百四十一页，2022年，8月28日线性分组码的检、纠错能力与H矩阵的关系第七十二页，共一百四十一页，2022年，8月28日线性分组码的检、纠错能力与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个错误第七十三页，共一百四十一页，2022年，8月28日第七十四页，共一百四十一页，2022年，8月28日第七十五页，共一百四十一页，2022年，8月28日第七十六页，共一百四十一页，2022年，8月28日第七十七页，共一百四十一页，2022年，8月28日第七十八页，共一百四十一页，2022年，8月28日例：某一个(5,2)系统线性码的生成矩阵是设接收到码字是r=(10101)，先构造该码的标准阵列译码表，然后译出发码的估值C。第七十九页，共一百四十一页，2022年，8月28日(1)信息组：m=(00),(10),(01),(11)(2)求得4个许用码字C=mG为

C1=(00000),C2=(10111

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

第八十页，共一百四十一页，2022年，8月28日(4)求出伴随式第八十一页，共一百四十一页，2022年，8月28日(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第八十二页，共一百四十一页，2022年，8月28日【例】（7，3）线性分组码

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

第八十三页，共一百四十一页，2022年，8月28日如：（一个错）如两个错：

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

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

≠0）,不能判定由哪几位错误引起！第八十八页，共一百四十一页，2022年，8月28日一．基本概念汉明码：一类能纠单个错误的纠错码。

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

5.汉明码第八十九页，共一百四十一页，2022年，8月28日（1）H中列为非全零元素；

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

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

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

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

（1）第九十一页，共一百四十一页，2022年，8月28日伴随式对应于H中的第五列，故：

（2）H中无对应列与之对应，不能正确译码。第九十二页，共一百四十一页，2022年，8月28日结论：为了得到具有纠一个错误的二元（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}表示这个二元集。第九十三页，共一百四十一页，2022年，8月28日如：

的（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个错误的全部错误图样作为陪集首就能做成标准阵列，那么称这个码为完备码。

第九十四页，共一百四十一页，2022年，8月28日四.汉明码的编译码电路框图编码器设计例(7,4)汉明码

由，第九十五页，共一百四十一页，2022年，8月28日2.译码器设计令接收字为

伴随式为

由校验矩阵H，

令1101000000011010000011100100001010001000100000010001000000100010000001

第九十六页，共一百四十一页，2022年，8月28日汉明码的译码电路框图

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

第一百页，共一百四十一页，2022年，8月28日2.码字的多项式描述对于任意个长度为n的码字，可用下列多项式来描述：这里，把各码元当作多项式的系数；x及其幂次数仅是码元位置的标记，我们并不关心它的取值；称系数不为零的x的最高次数为多项式A(x)的次数，或称为多项式的阶数。第一百零一页，共一百四十一页，2022年，8月28日第一百零二页，共一百四十一页，2022年，8月28日多项式的模运算示例第一百零三页，共一百四十一页，2022年，8月28日

如果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

第一百零四页，共一百四十一页，2022年，8月28日循环多项式的模运算定理：对于(n,k)循环码，若A(x)对应码字，对应A(x)的i次左循环移位，则等于除以后的余式，即：

第一百零五页，共一百四十一页，2022年，8月28日例题：设循环码(7,4)中一个码字为[00001101]，则该循环码的所有码字及其码多项式如表所示。序号循环码左移位数i00011010001101010110100211010003101000140100011510001106第一百零六页，共一百四十一页，2022年，8月28日3.生成多项式和生成矩阵生成多项式记为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第一百零七页，共一百四十一页，2022年，8月28日由生成多项式g(x)容易得到生成矩阵。生成矩阵的每一行必定为线性无关的，且每行都是一个码字。g(x)为n-k阶多项式，则g(x),xg(x),x2g(x),…,xk-1g(x)必是线性无关的，将此对应的码字作为矩阵的每一行，得到生成矩阵。与生成矩阵对应的生成矩阵多项式G(x)可记作：3.生成多项式和生成矩阵第一百零八页，共一百四十一页，2022年，8月28日例题：已知循环码(7,4)的生成多项式g(x)有两种可能

x3+x+1或x3+x2+1，分别求其生成矩阵解：若生成多项式g(x)=x3+x+1,则生成矩阵多项式为：所对应的生成矩阵为：第一百零九页，共一百四十一页，2022年，8月28日例题：已知循环码(7,4)的生成多项式g(x)有两种可能

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

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