第九章 循环码.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第九章,循环码,1,第九章 循环码,内容提要：,循环码是线性分组码中一个重要的子类。本章首先提出了循环码的定义以及循环码的多项式描述方法，论述了循环码构成的有关重要定理；接着讨论了循环码的编译码方法及其实现电路，最后介绍了已获得广泛应用的循环汉明码BCH,码等。,2,本章重点：,1.,循环码的基本概念；,2.,循环码的编码和译码方法；,3.BCH,码。,3,9.1.1 循环码的定义,将任一码字中的7个码元排在一个圆周上，则从圆周的任一码元开始，按顺时针方向移动一周，都将构成该码的一个码字。这就是循环码的由来。（见,图9.1,）,9.1 循环码的一般概念,4,图9.1 （7，4）汉明码的码字循环图,第二循环,第一循环,5,定义9.1,一个线性分组码，若具有下列特性，则称其为,循环码,。设码字,c,（,c,n-,1,，c,n-,2,，c,1,，c,0,）,若将码元循环左移一位，得,c,(1),（,c,n-,2,，c,1,，c,0,，c,n-,1,）,c,(1),也是一个码字。,6,9.1.2 循环码的多项式描述,设,c,（,c,n-,1,c,n-,2,c,1,c,0,）,是（,n，k,）,循环码的一个码字，则与其对应的多项式,c,(,x,),c,n-,1,x,n-,1,c,n-,2,x,n-,2,c,1,x,c,0,(91),称为码字,c,的,码字多项式,（或码多项式）。,如果,c,（,c,n-,1,c,n-,2,c,1,c,0,）,是（,n，k,）,循环码的一个码字，则,c,(1),（,c,n-,2,c,1,c,0,c,n-,1,）,也是该循环码的一个码字。这就是说,c,(,x,),c,n-,1,x,n-,1,c,n-,2x,n-,2,c,1,x,c,0,和,c,(1),(,x,),c,n-,2,x,n-,1,c,1,x,2,c,0,x,c,n-,1,都是（,n，k,）,循环码的码字多项式。,7,比较,c,(,x,),和,c,(1),(,x,),后可得,c,(1),(,x,),x c,(,x,),mod,x,n,1 (92),以及,c,(,i,),(,x,),x,i,c,(,x,)（,i,1,2,n,1）,mod,x,n,1,(93),定理9.1,在以多项式,x,n,1,为模的剩余类全体所构成的,n,维线性空间,V,n,中，其一个子空间,V,n,k,是一个循环子空间（循环码）的充要条件是：,V,n,k,是一个理想。,一个（,n，k,）,循环码的码字多项式都是模,x,n,1,运算下多项式剩余类环中的一个理想，而且一定是一个主理想子环。反之，多项式剩余类环的一个主理想子环也一定生成一个循环码。,8,9.1.3 循环码的生成多项式,定理9.2,GF(2),上的（,n，k,）,循环码中，存在有唯一的,n,k,次首一多项式,g,(,x,),x,n-k,g,n-k-,1,x,n-k-,1,g,1,x,g,0,使得每一个码多项式,c,(,x,),都是,g,(,x,),的倍式，且每一低于或等于,n,1,次的,g,(,x,),倍式，一定是码多项式。,定理9.3,（,n，k,）,循环码的生成多项式,g,(,x,),一定是,x,n,1,的因式：,x,n,1,g,(,x,),h,(,x,)。,反之，若,g,(,x,),为,n,k,次，且除尽,x,n,1，,则此,g,(,x,),一定生成一个（,n，k,）,循环码。,定义9.2,若一个循环码的所有码字多项式都是一个次数最低的非零首一多项式,g,(,x,),的倍式，则称,g,(,x,),生成该循环码，并称,g,(,x,),为该码的生成元或生成多项式。,9,定理9.4,若,g,(,x,),是（,n，k,）,循环码的生成多项式，由,x,n,1,g,(,x,),h,(,x,)，,h,(,x,),是,k,次多项式，称为,校验多项式,。令,h,(,x,),h,k,x,k,hk-,1,x,k,-1,h,1,x,h,0,则,(95),为（,nk,）,n,阶矩阵，称为码的,校验矩阵,。,10,（,n，k,）,循环码的生成多项式,g,(,x,),是一个次数最低的唯一的首一多项式，其次数,r,n,k,正好是码字中校验元的数目；,生成多项式,g,(,x,),是,x,n,1,的因式。要构造一个（,n，k,）,循环码，就是要在,x,n,1,的因式中找一个,n,k,次的首一多项式,g,(,x,)，,它的所有次数低于或等于,n,-1,的倍式就构成一个（,n，k,）,循环码。反之，循环码的每一个码字多项式必是,g,(,x,),的倍式；,综上所述，有如下结论：,由,x,n,1,g,(x,),h,(,x,)，,h,(,x,),称为校验多项式。对于任意一个（,n，k,）,循环码，必有,g,(,x,),h,(,x,)0 mod,x,n,1,及,G,H,T,0,循环码是线性分组码的一个子类。因此，所有线性分组码的性质均适用于循环码。,11,9.2 循环码的编码,9.2.1 利用生成多项式,g,(,x,),实现编码,若已知,g,(,x,),g,n-k,x,n-k,g,n-k-,1,x,n-k-,1,g,1,x,g,0,并设信息元多项式,m,(,x,),m,k-,1,x,k-,1,m,k-,2,x,k-,2,m,1,x,m,0,要编码成系统循环码形式，须用,x,n-k,乘以,m,(x,)，,再加上校验元多项式,r,(,x,)，,这样得到的码字多项式,c,(,x,),为：,c,(,x,),x,n-k,m,(,x,),r,(,x,),m,k-,1,x,n-,1,m,k-,2,x,n-,2,m,0,x,n-k,r,n-k-,1,x,n-k-,1,r,1,x,r,0,其中,r,(,x,),r,n-k-,1,x,n-k-,1,r,1,x,r,0,12,c,(,x,),一定是,g,(,x,),的倍式，即有,c,(,x,),x,n-k,m,(,x,),r,(,x,),q,(,x,),g,(,x,),或,c,(,x,),x,n-k,m,(,x,),r,(,x,)0，mod,g,(,x),注意到,g,(,x,),为,n,k,次多项式，而,r,(,x,),至多为,n,k,1,次多项式，必有,r,(,x,),x,n-k,m,(,x,)，mod,g,(,x,)(96),即,r,(,x,),必是,x,n-k,m,(,x,),除以,g,(,x,),的余式。,(96)式指出了系统循环码的编码方法：,首先将信息元多项式,m,(,x,),乘以,x,n-k,成为,x,n-k,m,(,x,)；,然后将,x,n-k,m,(,x,),除以生成多项式,g,(,x,),得到余式,r,(,x,)，,该余式就是校验元多项式，从而得到码字多项式,c,(,x,),x,n-k,m,(,x,),r,(,x,)。13,9.2.2 除法电路,设,GF,(2),上的两个多项式,a,(,x,),a,k,x,k,a,k-,1,x,k-,1,a,1,x,a,0,b,(,x,),b,r,x,r,b,r-,1,x,r-,1,b,1,x,b,0,a,(,x,),是被除式，,b,(,x,),是除式。用图9.2所示的电路完成,a,(,x,),除以,b,(,x,),的运算。,图9.2 除法电路的一般形式,14,【,例9.2,】设被除式,a,(,x,),x,4,x,1，,除式,b,(,x,),x,3,x,2,1，,完成二个多项式相除的运算。,长除法：,多项式的系数运算,15,实现以上除法运算的除法电路如图9.3所示,图9.3 以,b,(,x,),x,3,x,2,1,为除式的除法电路,16,9.2.3 编码电路,然后将,x,n-k,m,(,x,),除以生成多项式,g,(,x,),得到余式,r,(,x,)，,该余式就是校验元多项式，从而可得码字多项式,c,(,x,),x,n-k,m,(,x,),r,(,x,)。,系统循环码的编码方法是：,首先将信息元多项式,m,(,x,),乘以,x,n-k,成为,x,n-k,m,(,x,)；,17,用电路实现编码时可采用以,g,(,x,),为除式的除法电路。作为实例，图9.4示出了生成多项式,g,(,x,),x,3,x,2,1,的（7，4）循环码的编码电路。,图9.4 以,g,(,x,),x,3,x,2,1,的（7，4）循环码编码器,18,9.3 循环码的译码,当码字,c,通过噪声信道传送时，会受到干扰而产生错误。如信道产生的错误图样是,e,，,译码器收到的,n,重接收矢量是,y,，,则表示为,y,c,e,上式也可写成多项式形式：,y(x,),c,(,x,),e,(,x,)(97),译码器的任务就是如何从,y,(,x,),中找到错误图样多项式,，然后得到估计码字多项式 ，进而得到信息组 。,19,循环码的译码可按以下三个步骤进行：,（）,根据伴随式,s,(,x,),找出对应的估值错误图样 ；,（）,计算 ，得到估值码字 。若,，则译码正确，否则，若 ，则译码错误。,（）由接收到的,y,(,x,),计算伴随式多项式,s,(,x,)；,20,9.3.1 伴随式计算,对于（,n，k,）,循环码，可以定义码的生成多项式,g,(,x,),除以接收码字多项式,y,(,x,),的余式为伴随式多项式,s,(,x,)，,写成,s,(,x,),y,(,x,)mod,g,(,x,)(98),由于,y,(,x,),c,(,x,),e,(,x,),而,c,(,x,)mod,g,(,x,)0,于是,s,(,x,),e,(,x,)mod,g,(,x,)(99),s,(,x,),伴随式计算电路的一个重要性质：,定理9.5,设,s,(,x,),是接收码字多项式,r,(,x,),的伴随式，则y,(,x,),的一次循环移位,xy,(,x,)（mod,x,n,1）,的伴随式,s,(1),(,x,)，,是,s,(,x,),在伴随式计算电路中无输入时，右移一位的结果（称为自发运算）：,s,(1),(,x,),xs,(,x,)mod,g,(,x,),(911),21,【,例9.3,】以,g,(,x,),x,4,x,3,x,2,1,为生成多项式的（7，3）循环码（示于表9.1），能纠正一个错误。,设传送出现一个错，错误图样,e,（0 0 0 1 0 0 0），,即,e,(,x,),x,3,，,其伴随式,s,(,x,),e,(,x,)mod,g,(,x,),x,3,mod(,x,4,x,3,x,2,1),x,3,，,即,s,（1 0 0 0）,现设错误图样,e,1,（0 0 1 0 0 0 0）,即,e,(1),(,x,),xe,(,x,),x,4,，,相应的伴随式,s,(1),(,x,),x,4,mod(,x,4,x,3,x,2,1),x,3,x,2,1,即,s,1,（1 1 0 1）,s,1,是,s,在图9.5所示的,g,(,x,),x,4,x,3,x,2,1,除法电路中无输入时，右移一位的结果，也即自发运算的结果。,图9.5 （7，3）循环码的伴随式计算电路,22,9.3.2 循环码的译码,把某一可纠正的错误图样,e,(,x,),及其所有的小于等于,n,1,次的循环移位归成一类，用一个错误图样来代表。译码时只要计算这个错误图样的伴随式，该类中其它错误图样的伴随式都可由该伴随式在,g,(,x,),除法电路中循环移位来得到。,以（7，3）循环码为例：,当码字传送出现一个错误时，若用一般译码器需要识别如（0 0 0 0 0 0 1），（0 0 0 0 0 1 0），（0 0 0 0 1 0 0），（0 0 0 1 0 0 0），（0 0 1 0 0 0 0），（0 1 0 0 0 0 0），（1 0 0 0 0 0 0）等7个不同的错误图样，但对于按上述定理设计的循环码译码器来说，可以把这些错误图样归成一类，译码器只要识别其中的一个错误图样就可以了。,23,若（7，3循环码译码器按错误图样（1 0 0 0 0 0 0）设计，于是,s,(,x,),e,(,x,)mod,g,(,x,),x,6,mod(,x,4,x,3,x,2,1),x,3,x,2,x,，,即,s,（1 1 1 0）,其译码器电路示于图9.6。,图9.6 （7，3）循环码译码器,24,9.3.3,Meggit,译码器,循环码译码器的缺点无法对接收到的码字实现连续的译码输出。改进的译码器称作,Meggit,通用译码器,，其结构如图9.7，可实现连续的译码输出。,图9.7,Meggit,通用译码器,25,9.4.1 循环汉明码,定义9.3,设,是,GF(2,m,),上的一个本原元，则以,的本原多项式为生成多项式的（,2,m,1，2,m,1,m,）,汉明码是循环汉明码。,码的校验矩阵为,(913）,因码长,n,2,m,1，,H,也可以表为,(914),9.4 一些重要的循环码,26,例如，以,GF(2,3,),上的三次本原多项式为生成多项式，可生成一个（7，4）循环汉明码，其生成多项式,g,(,x,),x,3,x,1。,设,是,GF(2,3,),上的本原元，则码的校验矩阵,27,9.4.2,BCH,码,定义9.4,设,是,GF(2,m,),上的一个本原元，,t,为整数，则以含有,、,2,、,2,t,等共2,t,个根，其系数在,GF(2),上的最低次多项式,g,(,x,),为生成多项式的循环码，叫做,二元本原,BCH,码,。,码长,n,2,m,1,校验位数,r,n,k,mt,最小距离,d,2,t,1,纠错能力为,t,二元本原,BCH,码的参数为：,28,(917),【,例9.4,】设,m,4，,是,GF(2,4,),上的本原元，求码长,n,2,4,115,的二元本原,BCH,码。,若,t,1，,则码以,为根，即以,，,2,，,4,，,8,共轭根系为根，,最小多项式,m,1,(,x,),x,4,x,1,生成多项式,g(,x,),m,1,(,x,),x,4,x,1,校验位数目,n,k,4,码的,校验矩阵为,29,若,t,2，,则码以,，,3,为根，即以,，,2,，,4,，,8,共轭根系和,3,，,6,，,12,，,24,9,共轭根系为根，最小多项式,m,3,(,x,),x,4,x,3,x,2,x,1,生成多项式,g,(,x,),m,1,(,x,),m,3,(,x,),(,x,4,x,1)(,x,4,x,3,x,2,x,1),x,8,x,7,x,6,x,4,1,校验位数目,n,k,8,，,其校验矩阵,：,30,若,t,3，,则码以,，,3,，,5,为根，即以,，,2,，,4,，,8,共轭根系、,3,，,6,，,12,，,24,9,共轭根系和,5,，,10,共轭根系为根，最小多项式,m,5,(,x,),x,2,x,1,生成多项式,g,(,x,),m,1,(,x,),m,3x,),m,5,(,x,),(,x,4,x,1)(,x,4,x,3,x,2,x,1)(,x,2,x,1),x,10,x,8,x,5,x,4,x,2,x,1,校验位数目,n,k,10,，,其校验矩阵,31,循环码是线性分组码中一个重要的子类，由于这种码的代数结构完全建立在有限域基础上，它是目前理论上最为成熟的一类码。本章的主要内容有：,本,章,小,结,（2）循环码的性质：循环码的生成多项式，生成多项式的重要性质，由生成多项式构造生成矩阵。,（1）循环码的定义及多项式描述：循环码的循环特性，循 环码的码字多项式，循环码是多项式剩余类环的一个主理想子环。,32,（5）循环,Hamming,码和,BCH,码：用,g,(,x,),的根定义循环码，建立在有限域扩域上的,BCH,码。,（4）循环码的译码：伴随式的计算电路，自发运算电路，,Meggit,译码器。,（3）循环码的编码：用生成多项式编码的理论，除法电路，循环码的编码电路。,33,34,