第九章纠错编码

第9章纠错编码9.1差错控制5.2线性分组码9.3循环码9.4卷积码9.1差错控制9.1.1差错控制9.1.2码距与检纠错能力5.3.3最优译码与最大似然译码差错控制差错类型随机错误:数据流中发生的错误彼此无关,表现为错误之间的无相关性.突发错误:数据流中一个错误的发生,带来一连串错误的发生,表现为误错之间的相关性.差错控制差错控制系统前向纠错方式(FEC)：发送端发送具有纠错功能的码,接收端收到这些码后，通过译码器不仅能发现错误,而且能自行纠正错误。重传反馈方式(ARQ)：发送端发送具有检错功能的码,接收端收到这些码后，译码器对发送的码进行判决,接收端将判决的结果通过反馈信道告诉发送端,发送端将接收端认为有错的消息再次发送,直到接收端认为正确为止.发送接收可以纠正错误的码FEC发送接收可以纠正错误的码ARQ应答信号差错控制/差错控制系统狭义信息反馈系统(IRQ)：接收端将收到的消息原封不动地反馈到发送端,由发送端将反馈的消息比较,发现错误,再次发送。混合纠错方式(HEC)发送接收可以发现纠正错误的码HEC应答信号发送接收信息信号IRQ信息信号交织器交错（或称交织）-----针对突发错误带交错器的传输系统信道噪声造成的符号流中的突发差错，有可能被均化而转换为码流上随机的、可纠正的差错。差错控制纠错码的分类按译码器处理错误的性能分类能通过译码器自动发现错误的码称为检错码;纠正错误的码称为纠错码;纠正删除错误的码称为纠删码.按对信息位处理的方法分类分组码卷积码.差错控制/分类按校验位与信息位之间的关系分类线性码非线性码按能纠正错误的类型分类纠正随机(独立)错误的码;纠正突发错误的码;纠正同步错误的码;纠正随机错误与突发错误的码.码距与检纠错能力分组码分组码是信源输出的q进制的源数据码流按k个码元(信息位)划分为一段信息组m,通过编码器按一定规则产生r个校验(监督)元，输出长度n=k+r

个码元的q进制码字(码组、码矢)，此过程称为分组码编码。码距与检纠错能力/分组码相关概念源数据按k个信息位组成的不同信息组有:M=qk

组按n个的码元能组成的码字共有:N=qn

个在qn个码字中与信源符号组对应的qk个码字称为许用码字

,这qk个码字集合记为C,称为(n，k)分组码;而其余qn-qk个码字称为禁用码字。许用码字表示为Ci=(ci1,ci2,…,cin)i=1,2,…,M。其中ci1,ci2,…,cin为码元

,n为码字的长度。编码效率或码率：R=k/n表示信息位在码字中的比重,是衡量分组码有效性的一个基本参数。码距与检纠错能力码距定义：设Ci=(ci1,ci2,…,cin),Cj=(cj1,cj2,…,cjn)是码C的两个码字,Ci与Cj中cir≠cjr(r=1,2,…,n)的个数称为Ci与Cj的汉明距离

,简称码距，记为d(Ci,Cj)。定理：对于任意Ci,有d(Ci,Ci)=0对于任意Ci,Cj,有d(Ci,Cj)=d(Cj,Ci)

对于任意Ci,Cj,Cs,有d(Ci,Cj)+d(Cj,Cs)≥d(Ci,Cs)

码距与检纠错能力/码距定义：码C的任意两两码字的码距中最小的码距称为码C的最小距离

,记为dmin。推论1：若Ci,Cj

是码C的任意两个码字,则d(Ci,Cj)≥dmin推论2：设码C的最小距离为dmin,而Ci

是码C的任一码字，若有字R,当d(Ci,R

)<dmin

时,则R不是Ci

，就一定不是码C的码字。码距与检纠错能力检纠错能力将二进制源数据码流经过如下几种处理(编码)后,在BSC信道中传输。几种处理方法比较如下：不编码若其中有码元“0”错成“1”或“1”错成“0”。结论：接收端都无法检查出其错误。将码流中的码元“0”→(00),“1”→(11)无论若(00)或(11)错成(01)或(10),则接收端能检查出其错误;但不能确定是(00)还是(11)若(00)错成(11)或(11)错成(00),则接收端无法检出其错误。结论:能检测1个随机错误。码距与检纠错能力/检纠错能力/几种处理方法比较将码流中的码元“0”→(000),“1”→(111)无论(000)或(111)传输后有一个错误或有两个错误,接收端能检测其错误

;若(000)、(111)传输后只有一个错误,则接收端可将(001)、(010)、(100)译码为(000);将(011)、(101)、(110)译码为(111);若(000)、(111)传输后有两个以下错误,则接收端无法将(011)、(101)、(110)正确地译码;若传输后(000)错成(111)或(111)错成(000),则接收端无法检测其错误。结论:能检测2个随机错误,能纠正1个随机错误。

结论：1、最小距离为dmin的(n,k)分组码，能检测出dmin－1个差错。2、最小距离为dmin的(n,k)分组码，能纠正t=INI[(dmin-1)/2]个差错。3、纠错能力总小于检错能力。注意：上面是分组码单独考虑检错或纠错的情况。码距与检纠错能力/检纠错能力同时考虑检错和纠错结论：若最小距离为dmin的码同时能检ed个、纠ec个差错，则必有ed+ec≤dmin-1

及ec≤ed码距与检纠错能力纠错分组码中的两个重要参数编码效率:R=k/n码C最小距离:dmin

纠错码的基本任务是构造出当R一定,使得dmin

尽可能大的码;dmin

一定,R尽可能高的码。

9.2线性分组码9.2.1基本概念9.2.2近世代数初步9.2.3生成矩阵与校验矩阵9.2.4伴随式与译码基本概念模运算(对于整数)同余

a=b(modm):a除以m与b除以m(m>1)的余数相同，或称为a和b对于模m同余。最小非负剩余:a=r(modm);0≤r<m;r为模m最小非负剩余。模m运算:a,b∈{0,1,2,…,m-1}，r为最小非负剩余，将a+b=r(modm),a×b=r(modm)记为这种求a+b和a×b的模m最小非负剩余称为模m的加法运算和模m的乘法运算。为了简单起见,以后将运算符号简记为+和×。基本概念/模运算模2运算(二进制)

运算法则1+1=0,1+0=0+1=1,1+1+1=1,1+1+1+1=0,…1×0=0,0×1=0,0×0=0,1×1=10-1=1,1-0=1,1-1=0+01001110×01000101基本概念/模运算模q运算(q进制)例:模3运算+012001211202201×012000010122021基本概念线性分组码码字和：设Ci=(ci1,ci2,…,cin),Cj=(cj1,cj2,…,cjn)是二元码C的两个码字,则Ci

与Cj

的和为Ci

与Cj对应码元的模2运算;若Cs=(cs1,cs2,…,csn)且Cs=Ci+Cj即csr=cir+cjr(r=1,2,…,n)

。线性分组码：设(n,k)分组码C中的任意两个码字满足以下两个条件：C中有全0码元的码字;C中的任意两个码字和仍为码C的码字;则分组码C称为(n,k)线性分组码。推论：线性分组码任意两个以上码字的和仍为码C的码字。基本概念系统码若信息组m的k个码元以整体不变的形式,放在码字的任意位置中,该码为系统码。否则称为非系统码。系统码通常如下图将信息组放在码字的最左边或最右边。k位信息位n-k位校验位n-k位校验位k位信息位基本概念码字的重量定义：(n,k)码C的一个码字Ci中非零码元的个数称为码字Ci

的汉明重量

,简称码重

,记为W(Ci)。定义：(n,k)码C中所有非零码字的汉明重量的最小值称为码C的最小汉明重量

,或码C最小重量，记为Wmin。推论：设Ci,Cj为二元分组码C的任意两个码字,则W(Ci+Cj)=d(Ci,Cj)。定理：二元(n,k)线性分组码C的最小距离等于其最小重量。基本概念例：试构造(5,2)线性分组码,且dmin=3

信息组m：00011011

0000000001000100001100100001010011000111010000100101010010110110001101

01110

01111100001000110010100111010010101

10110

10111

1100011001

11010

11011

11100

11101

11110

111111组2组3组4组5组6组7组8组9组000000000000000000000000000000000000000000000010110101101011011010110101101011100111001110101011011010111100111011010111100111010110111111101110111100111101101111010111011100111001近世代数学初步群的概念定义1：G是一个非空集合，*是G中的一个代数运算，若1、封闭性：a,b∈G,有a*b∈G；2、结合律：a,b,c∈G,有(a*b)*c=a*(b*c)；3、存在单位元素e∈G,a∈G,有e*a=a*e=a；4、a∈G,存在逆元素a-1∈G,有a-1*a=a-1*a=e；5、交换律：a,b∈G,有a*b=b*a。如果这种运算*满足：条件1,2,3,4则G称对代数运算为一个群，或称G为一个非交换群；条件1,2,3,4,5则称G为一个交换群或Abel群。注意：上面的“*”代表某一种运算符号。近世代数学初步/群的概念若运算*是普通的加法“+”,则群称为加群。若运算*是普通的乘法“×”,则群称为乘群。定义2：若群G仅有有限个原素则称为有限群;否则为无限群。无限群的例子例1：整数集对加法构成Abel群，对乘法不是群。例2：有理数、实数、复数集对加法构成Abel群,不含0的有理数、实数、复数集对乘法构成Abel群。有限群的例子例1：数0对加法构成群,数1对乘法构成群.例2：集合{0,1,2,…,m-1}对模m加法运算构成Abel群，对乘法不是群。近世代数学初步域的概念定义1：F是一个非空集合，对于F的任意两个元素a和b，定义集合元素的加法运算,记作a＋b;乘法运算，记作ab;且有如下规则：加法运算1、a,b∈F,有a＋b∈F;2、a,b∈F,有a＋b=b＋a;3、a，b，c∈F,有(a＋b)＋c=a＋(b＋c);4、存在0∈F,a∈F,有a＋0=a；5、a∈F,存在-a∈F,有a＋(-a)=0;近世代数学初步/域的概念乘法运算1、a,b∈F,有ab∈F；2、a,b∈F,有ab=ba；3、a，b，c∈F,有(ab)c=a(bc)；4、存在e∈F,a∈F,有ae=a；5、a∈F，且a≠0,存在a-1∈F,有aa-1=e；乘法对加法的分配律：若a,b,c∈F,有a(b＋c)=ab＋ac以上运算规则都成立，则称F对于所规定的加法运算和乘法运算是一个域。近世代数学初步/域的概念定义2：设F是一个域,如果F中的元素个数无限,则F称为无限域。如果F中的元素个数有限,则F称为有限域，也称为迦罗华域，记作GF(q)。每个域必须有一个零元和一个单位元，最简单的就是二元域GF(2)。无限域的例子例：有理数、实数、复数集对加法,乘法构成域。有限域的例子例：集合{0,1,2,…,m-1}对模m加法,乘法运算构成域。生成矩阵与校验矩阵生成矩阵对于二进制线性分组码，编码运算可以用矩阵形式表示：

G称为该码的生成矩阵，是k×n(k行n列)矩阵：生成矩阵与校验矩阵/生成矩阵例：试构造(5,2)线性分组码,且dmin=3，m=(m1m2)=(00),(01),(10),(11)。生成矩阵为：Ci=(m1m2m1m2m1+m2)(00)→(00000)(01)→(01011)(10)→(10101)(11)→(11110)生成矩阵与校验矩阵/生成矩阵系统码：(n,k)码的任何生成矩阵G都可以通过行运算（以及列置换）简化成“系统形式”：编码时，信息组m乘以这种系统形式的生成矩阵G生成的(n,k)码，称为系统码。生成矩阵如不具备式所示的系统形式，则该码叫非系统码。系统码特点：前k位等于把信息组原封不动的搬到码字的前k位；其余的n-k位叫冗余比特或一致校验位，是前k个信息位的线性组合。生成矩阵与校验矩阵/生成矩阵生成矩阵的特点生成矩阵不是唯一的;生成矩阵的行矢量均为线性分组码的码字;生成矩阵的行矢量是模2运算下线性无关;线性分组码任一码字是行矢量模2运算下的线性组合。生成矩阵与校验矩阵/生成矩阵如何获得生成矩阵?例：试构造(7,4)线性分组码,且dmin=3。生成矩阵生成的线性分组码要有尽可能大的dmin；生成矩阵的行矢量中的“1”的个数≥dmin

；生成矩阵各行矢量(码字)的对应元素不相同的个数≥dmin。生成矩阵与校验矩阵校验矩阵(n,k)线性分组码为系统码

,则码字有(c1c2…ck

ck+1…cn)=(m1m2…mk

ck+1…cn)由生成矩阵G生成的码字(c1c2…ck

ck+1…cn)=(m1m2…mk

)G=(m1m2…mk

)[Ik

Pk×(n-k)]码字的校验位(

ck+1…cn)=(m1m2…mk

)

Pk×(n-k)=(c1c2…ck

)Pk×(n-k)(c1c2…ck

)Pk×(n-k)-(

ck+1…cn)=01×(n-k)(c1c2…ck

)Pk×(n-k)+(

ck+1…cn)I(n-k)=01×(n-k)生成矩阵与校验矩阵/校验矩阵一致校验矩阵H(简称校验矩阵)H=[PTI(n-k)](n-k)×n当系统码生成矩阵G确定后,校验矩阵H由生成矩阵中的分块矩阵Pk×(n-k)确定。由生成矩阵G生成的任一码字Ci

均满足下式,不是G生成码字则不满足下式CiHT=01×(n-k)

或HCiT=0(n-k)×1因此,校验矩阵H可以判断是否为码字。生成矩阵与校验矩阵/校验矩阵例：考虑一个(7,4)码，其生成矩阵是(1)对于信息组m=(1011)，编出的码字是什么？(2)若接收到一个7位码r=(1001101)，它是否是码字？生成矩阵与校验矩阵/校验矩阵/例解：(1)设输入4比特信息组m=(m1,m2,m3,m4)，码字为Ci=(ci1ci2ci3ci4ci5ci6ci7)，由Ci=mG得Ci=(m1m2m3m4ci5ci6ci7)ci5=m1+m2+m3=0ci6=m2+m3+m4=0ci7=m1+m2+m4=0于是码字C=(1011000)生成矩阵与校验矩阵/校验矩阵/例(2)H矩阵判断rHT是否等于0若r是某个码字C，必有rHT=0；若rHT≠0，则r必定不是码字。计算得rHT≠0，所以r不是码字。伴随式与译码差错图案线性分组码C的任一码字Ci=(ci1,ci2,…,cin)经信道传输后,接收到字R=(r1,r2,…,rn);令E=R-Ci=(r1-ci1,r2-ci2,…,rn-cin);这里称E为差错图案。根据模2运算的性质,E=R+Ci

信道译码器码字Ci接收码字RCi的估值干扰伴随式与译码/差错图案E=0则接收字R是码C的一码字;否则，不是码C的码字。对于二元(n,k)码,差错图案E的分量中“1”的个数即为接收字R差错的个数。差错图案出现t个差错的图案个数Cnt。伴随式与译码伴随式根据CiHT=01×(n-k)及R=Ci+E有RHT=(Ci+E)HT=CiHT+EHT=EHT

令S=RHT或S=EHT;这里S=(s1,s2,…,sn-k)这里称S为伴随式。伴随式S仅与接收字R或差错图案E有关,与码字Ci

无关。由于伴随式S是n-k维矢量,故不同S的个数只有2n-k

个；而接收字R或差错图案E有2n

个。因此,不同的接收字R或差错图案E有相同的伴随式S。伴随式与译码线性分组码的译码原理生成矩阵G或校验矩阵H确定后,就可以解决编码问题，码字经过信道传输后,接收端获得的只有R,而Ci

未知的，因此E也是未知的。如何根据H和R进行译码？伴随式与译码/译码原理如果接收字无差错,则R=Ci,则S=RHT=0；如果接收字有差错，当差错<dmin

时,则S=RHT≠0。当码字Ci

错为另一个码字时,则S=RHT=0。如果接收到字R,计算S=RHT。如果S≠0,则接收字有差错;如果S=0,不能肯定接收字无差错;在有扰信道情况下,找到一个绝对无错的译码方案是不可能的,只能选择一种译码错误概率最小的译码方案。无论S≠0或S=0,均按最小距离原理译码。伴随式与译码/译码原理理论根据：若BSC信道的差错概率是p(p<<1),码字的长度为n，则由上表中可以看出：差错位数12…nW(E)12…n出现概率p(1-p)n-1p2(1-p)n-2…pn伴随式与译码/译码原理出现差错位数越小，即差错图案E的重量越小，出现的概率就越大。也就是说S(或者Ci的估值)对应最小重量E的可能性最大。由于E=R+C，所以E的重量最小就等于d(R，C)最小。概率译码实际上体现了最小距离译码原则，也就是最大似然译码。伴随式与译码/译码步骤1、S=RHT→S2、EHT=S→E3、C=R+E说明：在第二步中，要求差错图案E，就要求解线性方程组。注意：n-k个方程求解n个未知数，多个解。解线性方程组很困难，实时性很困难，怎么办？伴随式与译码/译码步骤解决方法——构造标准阵列译码表。伴随式S的数目是有限的2n-k个，如果n-k不太大，可以预先把不同S下的方程组解出来，把各种情况下的最大概率译码输出列成一个码表——标准阵列译码表。伴随式与译码/译码步骤/标准阵列译码表一般构造标准阵列译码表的方法与步骤：将没有任何差错的收码R放在第1行，此时收码等于发码即R=C，差错图案E1=(0,0,…,0)，伴随式S1=(0,0,…,0)。在第2行到第n+1行中填上所有重量为1的差错图案(共n个)。如果(1+n)<2n-k，则在下面n(n-1)/2行写出全部带有2个差错的图案E(共n(n-1)/2个)。如果(1+n+n(n-1)/2)<2n-k，再列出带有3个差错的图案E，依此类推，直到放满2n-k行，每行一个Ej，对应一个不同的Sj。伴随式与译码/译码步骤/标准阵列译码表在码表中的第j行、第i列填入Cj+Ei。Cj表示第j个输入码字，所以该表共有2k列。如下表：Ej+CiEj+C2Ej+C1E2+CiE2+C2E2+C1E1+CiE1+C2E1+C1伴随式与译码/译码步骤/标准阵列译码表例：某一个(5,2)系统线性码的生成矩阵是设收码是R=(10101)，请先构造该码的标准阵列译码表，然后译出发码的估值C。解：(1)构造标准阵列译码表信息组m=(00),(01),(10),(11)。①根据公式C=mG可得到四个可用码字：C1=(00000),C2=(01101),C3=(10111),C4=(11010)伴随式与译码/译码步骤/标准阵列译码表/例②求校验矩阵H③根据S=EHT可得到④根据概率译码的规则选择合适的差错图案E伴随式有23=8种组合，而差错图案中，无差错的有1种，1个差错的5种，2个差错的有10种。伴随式与译码/译码步骤/标准阵列译码表/例要选择8个重量最轻的差错图案E与8个伴随式相对应。选择方法是：先选择1种无差错的图案和5种有1个差错的图案，再从10种有2个差错的图案中选择2个。E5=00010S5=010E6=00001S6=001E4=00100S4=100E3=01000S3=101E2=10000S2=111E1=00000S1=000差错图案E伴随式S先将无差错和只有1个差错的6种图案代入表达式，解得对应的伴随式，如右表所示：从表中可以看出，剩下的两个伴随式为：S7=(011)，S8=(110)伴随式与译码/译码步骤/标准阵列译码表/例从公式可以算出，伴随式S7(011)所对应的差错图案有(00011),(10100),(01110),(11001)。上述四个差错图案中，(00011)和(10100)并列重量最轻，任选其中一个，例如S7=(10100)。从公式可以算出，伴随式S8(110)所对应的差错图案有(11100),(00110),(01011),(10001)。上述四个差错图案中，(00110)和(10001)并列重量最轻，任选其中一个，例如S8=(10001)。伴随式与译码/译码步骤/标准阵列译码表/例⑤根据伴随式和与其对应的差错图案填写标准阵列译码表：S1=000E1+C1=00000C2=01101C3=10111C4=11010S2=111E2=10000111010011101010S3=101E3=01000001011111110010S4=100E4=00100010011001111110S5=010E5=00010011111010111000S6=001E6=00001011001011011011S7=011E7=10100110010001101110S8=110E8=10001111000011001011陪集陪集首子集子集头伴随式与译码/译码步骤/标准阵列译码表/例(2)对于收码R=(10101)，可有以下三种译码方法：①直接搜索码表，查得(10101)所在的子集头是(10111)，因此译码输出为(10111)。②可以先求出伴随式RHT=(10101)HT=(010)=S5，在搜索码表的第5行找到(10101)，最后找到子集头是(10111)，即为译码输出码字。③先求出伴随式RHT=(10101)HT=(010)=S5，再在表中查出对应的差错图案E5=(00010)，通过计算得到码字C=R+E5=(10101)+(00010)=(10111)。伴随式与译码/译码步骤/标准阵列译码表/例小结：(1)建立标准阵列译码表，实际上就是把最有可能产生差错的码字出现差错的可能情况全部列出来，供译码时直接查表。(2)可以看出该(5,2)系统线性码的码字dmin=3，纠错能力t=1，即译码表的最后两行的差错图案都是有2个错误的，超出了分组码的纠错能力，译码不可靠。(3)译码表的最后两行，差错图案的选择不是唯一的，就可能导致了译码的不可靠性。9.3循环码9.3.1GF(2)域上的多项式9.3.2多项式表示9.3.3生成多项式9.3.4生成矩阵循环码循环码是线性分组码的一个子集,循环码有更好的代数结构,其编码器和译码器可实现性好。循环码的数学基础主要是近世代数。码字的循环移位左循环移位右循环移位

(1011000)→(0110001)(1011000)→(0101100)

移位1次移位1次以后所指的码字循环移位均为左循环移位，简称循环移位，字长为n的码字循环移位n次后又回复到原码字。定义：一个(n,k)线性分组码C,若其任一码字的一个循环移位仍然是码C的一个码字,则码C是一个循环码。循环码例：(7,4)循环码按信息位排序

1

0000000020001011

(生成子序列)13001011024010110055101100011601100016711000101281000101890011101(序列2+序列3)3100111010711111010014121101001131310100111014010011141510011109161111111(序列2+序列11)15GF(2)域上的多项式

f(x)=a0xn

+a1xn-1+a2n-2xn-2+…an-1

x

+

an，其中ai∈{0,1},i=0,1,…,n。则称

f(x)

为GF(2)域上的多项式。GF(2)域上的多项式的运算规则f1(x)与f2(x)的加,减,乘运算与实数域上多项式运算规则相同，但其系数按模2运算。f1(x)与f2(x)的加,减,乘仍为GF(2)域上的多项式。注意：f(x)+f(x)=0GF(2)域上的多项式余式设a(x),m(x)为GF(2)域上的多项式，若a(x)=b(x)m(x)+r(x)r(x)的次数小于m(x)的次数，则称r(x)为a(x)除以m(x)的余式

,m(x)称模多项式。或记为：a(x)=r(x)mod

m(x)任意a(x)对于模m(x)的余式r(x)的集合称多项式剩余环。GF(2)域上的多项式/求余式求余式基本方法是长除法。例：用长除法求模xn+1的余式。x6+x3+x2+1modx4+1=x3+1GF(2)域上的多项式/求余式x8+x7+x5+x4+x2+x+1modx4+1=x3+x2+1多项式表示码多项式对于码长为n的二元循环码的任一码字，都可以用GF(2)域上的一个≤(n-1)次多项式表示。为了书写方便，以后将码C中的任意码字Ci

简写为C。定义：码长为n的码字C=(cn-1cn-2…c1c0)用如下n-1次多项式表示，则C(x)称循环码的码多项式。多项式表示/码多项式从定义可以看出：码多项式C(x)的系数与码字C的码元是一一对应的，因此码多项式C(x)与码字C也是一一对应的。循环码可以用一组码多项式描述。例：(0101100)→C(x)=x5+x3+x2

(1101001)→C(x)=x6+x5+x3+1

多项式表示码字循环移位的码多项式描述码字的循环移位可表示为与之对应的多项式变化为多项式表示/码字循环移位通过比较循环移位前后的形式和结果，可用多项式的运算来表示循环移位：多项式表示码多项式的性质性质1：循环码C任意两个或两个以上的码多项式之和仍是循环码C的码多项式。定义：循环码C的次数最低的非零码多项式记为g(x)。性质2：循环码C的码多项式g(x)是唯一的。性质3：循环码C的码多项式g(x)的常数项是1。性质4：多项式C(x)的次数≤(n-1)次,C(x)是码长为n的循环码C的码多项式的充要条件为C(x)=b(x)g(x)。这里b(x)=(b1xr-1+b2

xr-2+…+br)。

生成多项式以上性质4表明一个循环码可由次数最底的非零码多项式g(x)生成。对于(n,k)循环码,其信息位有k位m=(m1,m2,…,mk)，若有一个上述(n-k)次的g(x),将信息位表示为k-1次多项式,m(x)=mk-1

xk-1+mk-2

xk-

2+

…

+

m0

，则C(x)=m(x)g(x)=mk-1xk-1g(x)

+mk-2

xk-2g(x)+…+m0g(x)上式还可以写成显然xk-1g(x)

,

xk-2g(x),

…

,

g(x)是线性无关的,且其线性组合有2k

个次数≤(n-1)次的码多项式C(x),其中任意两个码多项式仍然是2k个码多项式中之一。(线性特性)这里将g(x)

称为(n,k)循环码的生成多项式。生成多项式两个定理：定理1：(n,k)循环码的生成多项式g(x)是xn

+1因式。定理2：若g(x)是n–k次多项式,且是xn

+1因式,则g(x)生成一个(n,k)循环码。生成多项式构造(n,k)循环码的步骤①对(xn+1)作因式分解，找出其中(n-k)次因式。②以该(n-k)次因式为生成多项式g(x)，与不高于(k-1)次的信息多项式m(x)相乘，即得到码多项式C(x)=m(x)g(x)，C(x)的次数不高于(k-1)+(n-k)=(n-1)次。说明：xn+1的因式如何求,是数学领域的一个问题。生成多项式例：研究一个长度n=7的循环码的构造方法x7+1

=(x+1

)(

x3+x2+1

)(

x3+x+1

)

1次因子有1个:x+1

3次因子有2个:x3+x2+1或x3+x+1

4次因子有2个:x4+x2+x+1

或x4+x3+x2+16次因子有1个:x6+x5+x4+x3+x2+x+1

∴生成多项式g(x)的n–k有6种选择。生成多项式例：x10+1=(x+1)(x+1)(x4+x3+x2+x+1)(x4+x3+x2+x+1)x+1x2+1

x4+

x3+x2+x+1x5+1

x6+

x5+x+1x8+x6+x4+x2+1x9+x8+x7+x6+x5+x4+x3+x2+x+1因子有1次,2次,4次,5次,6次,8次,9次生成多项式例：(7,4)循环码生成多项式g(x)可选n-k=7-4=3次多项式，即(x3+x2+1)或(x3+x+1)。选择g(x)=(x3+x2+1)，设信息多项式为m(x)=m3x3+m2x2+m1x+m0循环编码后所得到的码多项式为若m=(0110)，则代入上式得到生成多项式在GF(2)中，(m3m2m1m0)共有16种组合，对应16个码字，由上面公式可得到(7,4)循环码的码字如下表：信息比特码字信息比特码字信息比特码字000100011010011001011100000000000010001101001100101110101111111101000110100110010111001000110100001010111001110110100011010111001001110100011100111001011110100011011111001010可以看出：整个码集有4组码字循环。生成多项式几个相关性质一般情况下，xn+1=h(x)g(x)①最小多项式：在GF(2)上不能再分解的因式叫最小多项式。生成多项式g(x)可以是最小多项式，也可以不是最小多项式。②如果g(x)代表(n,k)循环码的生成多项式，则h(x)代表(n,k)循环码的一致校验多项式,其阶次为k。h(x)的校验作用：任何码多项式C(x)与h(x)的模xn+1乘积一定等于0，而非码多项式与h(x)的模xn+1乘积一定不等于0

。即生成多项式③g(x)和h(x)地位同等。可以用g(x)生成一个循环码，也可以用h(x)生成一个循环码，此时h(x)用作生成多项式，而g(x)用作一致校验多项式。由g(x)生成的(n,k)循环码和由h(x)生成的(n,n-k)循环码互为对偶码。④反多项式设f(x)是k次多项式，则f(x)的反多项式定义为结论：在二元域中，若f(x)是xn+1的一个因式，那么它的反多项式也是xn+1的一个因式。生成矩阵当循环码的生成多项式g(x)给定后，我们可用如下方法得到生成矩阵G。我们取g(x)本身和g(x)移位k-1次所得的k-1个码字作为k个基底，从而得到循环码的生成矩阵。若循环码生成多项式g(x)为g(x)左移k-1次得到生成矩阵写成矩阵形式为对于二进制而言，上面矩阵中的参数gi∈{0,1}，i=1,2,…,n-k-1。注意：通过这种方法得到的生成矩阵不是系统形式。生成矩阵例：g(x)=(x3+x2+1)，则生成矩阵G为g(x)所对应的矢量xg(x)所对应的矢量x3g(x)所对应的矢量x2g(x)所对应的矢量结论：生成矩阵G的k重列矢量是由g(x)所对应的矢量和其循环左移k-1次得到的k-1重列矢量组成。生成矩阵系统循环码设信息位多项式为m(x)=mk-1

xk-1+mk-2

xk-

2+…+m0

系统码的码多项式为C(x)=xn-km(x)+r(x)，r(x)是次数小于(n-k)的多项式。若C(x)是(n,