数字通信中的抗干扰编码技术.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,数字通信中的抗干扰编码,差错控制技术,数字通信中的抗干扰编码,抗干扰编码的基本原理,差错控制方式,奇偶校验码与校验和,循环码：,编译码原理,检错与纠错能力,编译码算法,抗干扰编码的基本原理,定义：,采用可靠、有效的编码以发现或纠正数字信号在传输过程中由于噪声干扰而造成的错码，称为抗干扰编码，又称信道编码。,实现方法：,对信源编码得到的信息序列，按照某种规律，添加一定的校验码元，构成一个具有抗干扰能力的码字。添加校验码元的规律或规则不同，形成不同的编码方法。,常用的编码方法,奇偶校验、校验和、循环冗余校验（,CRC,）。,信道编码的实现,对于长度为,k,的信息码元序列，按一定规律加入,r=,n-k,位监督码元，组成长度为,n,的码字，记作,(,n,k,),码。,若,r,位校验码只与本码字中的,k,位信息位相关，称为分组码,若,r,位校验码不仅与本码字中的,k,位信息位相关，还与前面若干个码字的信息元相关，称为卷积码,(,n,k,),码可能出现的码字为,2,k,种,长度为,n,的码元可能出现,2,n,种,信道译码,信道译码：,接收端收到一个码字后，判断它是否发端发来的码字，是哪个码字。,采用最大似然译码：,将接收到的码字与信道编码时可能输出的,2,k,个码字比较，将其中最相似的码字作为正确的接收码字。,码距与最小码距,两个长度相同的码字之间对应码位上不相同的码元的数目，称为这两个码字之间的距离，简称码距。,在一种码的所有码字集合中，任意两个码字之间的最小距离，称为这个码字集合的最小码距，记为,d,min,。,最大似然译码的实现,计算收到的码字与发端可能发送码字之间的码距，与哪个码字的码距最小，则判断接收码字就是这个发送码字。,最小码距,d,min,与检错能力与纠错能力的关系：,t,能纠正的错误个数,l,能检出的错误个数,对抗干扰编码的要求,编码效率：对于,(,n,k,),码，编码效率为：,编码性能（较好的检错与纠错能力）,编码易于实现,差错控制方式,循环传送检错,前向纠错,自动要求重传,返送重传,混合纠错,差错控制方式,循环传送检错,同一信息源的信息周期性地循环传送,发送端将有关的信息进行抗干扰编码后，发送出去。接收端经检错译码器判断有无错误，无错则数码可用，有错则丢弃不用。,传送方式简单，较易实现。,前向纠错(,FEC),发送端进行信息的纠错编码，并发送，接收端对其进行纠错译码,优点：不需反馈,缺点：译码器较复杂,差错控制方式,自动要求重传(,ARQ),发送端发送可检错的码字，接收端根据编码规则检错，并通过反馈信道将判决结果返送发送端，若有错则发送端重新发送，直到接收端确认无错为止。,性能：它要求一个反馈信道，若干扰严重，重传次数增加，通信连贯性差，效率低，但只用了检错方式，编码、译码器较简单，选用适当的编码规则，可使未检出错误的概率变的非常小。,返送重传,接收端将收到的信息原封不动地返送给发送端。,传输效率更低，可靠性提高。,差错控制方式,混合纠错(,HEC),发送端发送的码元不仅能检错，也有一定的纠错能力。接收端首先进行纠错，若能检出错误，但不能纠正，返回反馈信息要求发送端重新发送。,电力系统循环式远动中，遥测、遥信采用循环传送检错；问答式远动中，采用检错译码方式；对于遥控、遥调采用返送重传方式。,奇偶校验码,编码规则：,在,n-1,位信息元后面，添加一位码元，使码字中“,1”,的个数恒为奇数或偶数。,当“,1”,的个数恒为奇数时，称为奇校验码,当“,1”,的个数恒为偶数时，称为偶校验码,编码效率：,性能分析：,检错能力：可以检出奇数个错误,纠错能力：不能纠正错误,水平垂直奇偶校验码,水平和垂直两个方向的奇偶校验码，也称纵横奇偶校验码,构成如图所示,m,k-1,m,k-2,m,k-j,r,1(j+1),m,k-(j+1),m,k-(j+2),m,k-2j,r,2(j+1),m,j-1,m,j-2,m,0,r,i(j+1),r,(i+1)1,r,(i+1)2,r,(i+1)j,r,(i+1)(j+1),具有较强的检错能力,校验和,CS,（,Check Sum,）,把,m,个长为,l,的信息组作为二进制数相加，形成校验和，将校验和附在,m,个信息组之后一起传送。,接收端将收到的前面,m,个信息组以同样方式相加，得到的校验和，与收到的校验和相比，校验是否一致。,模,2,运算,在由元素,0,和,1,组成的二元域上定义模,2,运算：,模,2,加法运算：,0,0,0 1,0,1 0,1,1 1,1,0,模,2,减法运算规则与加法相同。,模,2,乘法运算：,00,0 10,0 01,0 11,1,码多项式及其运算,定义二元域上的多项式：,f(x,)=a,n-1,x,n-1,+a,n-2,x,n-2,+,a,1,x+a,0,其中，,a,i,=0,或,1,信道编码中，通常用多项式表示一个信息序列或码字，称为码多项式或信息多项式,信息多项式：,m(x,)=m,k-1,x,k-1,+m,k-2,x,k-2,+,m,1,x+m,0,码多项式：,c(x,)=c,n-1,x,n-1,+c,n-2,x,n-2,+,c,1,x+c,0,码多项式及其运算（二）,信息序列,1001011,可以用码多项式表示为：,x,6,+x,3,+x+1,对于,f(x,)=x,4,+x,3,+x,2,+1,，,g(x,)=x+1,f(x,),g(x,)=,f(x,),g(x,)=x,4,+x,3,+x,2,+x,f(x,),g(x,)=x,5,+x,2,+x+1,f(x,),g(x,)=x,3,+x+1,f(x)=x,4,+x,3,+x,2,+1,，,g(x,)=x+1,f(x),g(x,)=f(x),g(x,)=x,4,+x,3,+x,2,+x,f(x),g(x,)=x,5,+x,2,+x+1,f(x),g(x,)=x,3,+x+1,线性分组码,当分组码满足每个码字中的每一位校验码元，都是本码字中信息码元的线性模,2,和时，称为线性分组码。,例如，对于,(6,，,3),分组码，若每个码字的校验码与信息码有下列关系：,r,2,=m,2,+m,0,r,1,=m,2,+m,1,r,0,=m,1,+m,0,（,6,，,3,）线性分组码,信 息 元,码 字,m,2,m,1,m,0,m,2,m,1,m,0,r,2,r,1,r,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,1,0,1,0,1,0,0,1,0,0,1,1,0,1,1,0,1,1,1,1,0,1,0,0,1,0,0,1,1,0,1,0,1,1,0,1,0,1,1,1,1,0,1,1,0,1,0,1,1,1,1,1,1,1,0,0,0,线性分组码的生成矩阵,循环码,如果线性分组码中的任一个码字经过循环移位之后，仍可以得到该线性分组码中的码字，该线性分组码称为循环码。,设（,n,，,k,）循环码的码字为：,c=c,n-1,c,n-2,c,1,c,0,循环,1,次后得到的码字为：,c,(1),=c,n-2,c,n-3,c,0,c,n-1,循环,i,次后得到的码字为：,c,(,i,),=c,n-,i,-1,c,n,-i,-2,c,n-,i,+1,c,n-,i,循环码的性质,1.(,n,k,),循环码有且只有一个,n-k,次的码多项式,g(x,),：,g(x,)=,x,n-k,+g,n-k-1,x,n-k-1,+,g,1,x+1,g(x,),称为循环码的生成多项式。,2.(,n,k,),循环码中的任一个码多项式都是,g(x,),的倍式。,3.(,n,k,),循环码的生成多项式是,x,n,+1,的一个因式。,循环码的性质,性质,3,提供了一种确定生成多项式的方法：,若,g(x,),是一个,n-k,次多项式，且是,x,n,+1,的一个因式，则,g(x,),可以生成一个,(n,，,k),循环码。,例如：,X,7,+1=(x+1)(x,3,+x,2,+1)(x,3,+x+1),对于,(7,4),循环码，一个生成多项式为：,g(x,),x,3,+x+1,非系统循环码的计算,若已知循环码的生成多项式，根据性质,2,，可以将生成多项式与指定信息码相乘，计算出对应的码字。,非系统循环码的计算：,根据循环码的码长,n,和信息位,k,选定生成多项式,g,(,x,),，,完成,m,(,x,),g,(,x,),的乘法运算，得到信息多项式,m,(,x,),对应的码多项式,c,(,x,),。,由,g(x,)=x,3,+x+1,生成的,(7,4),非系统循环码,信息序列,码 多 项 式,码 字,m,3,m,2,m,1,m,0,c(x)=,m(x,),g(x,),c,6,c,5,c,4,c,3,c,2,c,1,c,0,0,0,0,0,0(X,3,+X+1)0,0,0,0,0,0,0,0,0,0,0,1,1(X,3,+X+1),X,3,+X+1,0,0,0,1,0,1,1,0,0,1,0,X (X,3,+X+1),X,4,+X,2,+X,0,0,1,0,1,1,0,0,0,1,1,(X+1)(X,3,+X+1)X,4,+X,3,+X,2,+1,0,0,1,1,1,0,1,0,1,0,0,X,2,(X,3,+X+1),X,5,+X,3,+X,2,0,1,0,1,1,0,0,0,1,0,1,(X,2,+1)(X,3,+X+1),X,5,+X,2,+X+1,0,1,0,0,1,1,1,0,1,1,0,(X,2,+X)(X,3,+X+1)X,5,+X,4,+X,3,+X,0,1,1,1,0,1,0,0,1,1,1,(X,2,+X+1)(X,3,+X+1),X,5,+X,4,+1,0,1,1,0,0,0,1,1,0,0,0,X,3,(X,3,+X+1),X,6,+X,4,+,X,3,1,0,1,1,0,0,0,1,0,0,1,(X,3,+1)(X,3,+X+1),X,6,+X,4,+X+1,1,0,1,0,0,1,1,1,0,1,0,(X,3,+X)(X,3,+X+1),X,6,+X,3,+X,2,+X,1,0,0,1,1,1,0,1,0,1,1,(X,3,+X+1)(X,3,+X+1),X,6,+X,2,+1,1,0,0,0,1,0,1,1,1,0,0,(X,3,+X,2,)(X,3,+X+1),X,6,+X,5,+X,4,+,X,2,1,1,1,0,1,0,0,1,1,0,1,(X,3,+X,2,+1)(X,3,+X+1),X,6,+X,5,+X,4,+X,3,+,X,2,+X+1,1,1,1,1,1,1,1,1,1,1,0,(X,3,+X,2,+X)(X,3,+X+1),X,6,+X,5,+X,1,1,0,0,0,1,0,1,1,1,1,(X,3,+X,2,+X+1)(X,3,+X+1),X,6,+X,5,+X,3,+1,1,1,0,1,0,0,1,系统循环码的计算,(n,，,k),系统码的编码过程：,信息多项式,m(x,),乘以,x,n-k,，,得到,x,n-k,m(x,),以生成多项式除,x,n-k,m(x,),，,若余式为,r(x,),，即,x,n-k,m(x,),g(x)q(x)+r(x,),对应的系统循环码字为：,c(x,)=x,n-k,m(x,)+,r(x,),由,g(x,)=x,3,+x+1,生成的,(7,4),系统循环码,信息序列,码 多 项 式,码 字,m,3,m,2,m,1,m,0,c(x)=,x,n-k,m(x,)+,r(x,),c,6,c,5,c,4,c,3,c,2,c,1,c,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,X,3,+X+1,0,0,0,1,0,1,1,0,0,1,0,X,4,+X,2,+X,0,0,1,0,1,1,0,0,0,1,1,X,4,+X,3,+X,2,+1,0,0,1,1,1,0,1,0,1,0,0,X,5,+X,3,+X,2,0,1,0,0,1,1,1,0,1,0,1,X,5,+X,4,+1,0,1,0,1,1,0,0,0,1,1,0,X,5,+X,4,+X,3,+X,0,1,1,0,0,0,1,0,1,1,1,X,5,+X,4,+1,0,1,1,1,0,1,0,1,0,0,0,X,6,+X,2,+,1,1,0,0,0,1,0,1,1,0,0,1,X,6,+X,3,+X,2,+X,1,0,0,1,1,1,0,1,0,1,0,X,6,+X,4,+X+1,1,0,1,0,0,1,1,1,0,1,1,X,6,+X,4,+X,3,1,0,1,1,0,0,0,1,1,0,0,X,6,+X,5,+X,1,1,0,0,0,1,0,1,1,0,1,X,6,+X,5,+X,3,+1,1,1,0,1,0,0,1,1,1,1,0,X,6,+X,5,+X,4,+X,2,1,1,1,0,1,0,0,1,1,1,1,X,6,+X,5,+X,4,+X,3,+,X,2,+X+1,1,1,1,1,1,1,1,伴随式,发送端发送的码字为,C(x,)=c,n-1,x,n-1,+c,n-2,x,n-2,+c,1,x+c,0,接收端收到的码字为：,R(x,)=r,n-1,x,n-1,+r,n-2,x,n-2,+r,1,x+r,0,R(x,),除以,g(x,),，,可得余式,s(x,),，,则,R(x,),p(x)g(x,),s(x,),多项式,s(x,),称为接收码字,R(x,),的伴随式。,若,S(x,),0,，,则认为无错码；,若,S(x)0,，,则认为有错码,伴随式与错误图样,接收端由于干扰而出现的错误图样为：,E(x,)=e,n-1,x,n-1,+e,n-2,x,n-2,+e,1,x+e,0,则,R(x,)=,C(x,),E(x,),R(x)/g(x,),C(x)/g(x,),E(x)/g(x,),由于,C(x,)=,g(x,)*,p(x,),则,E(x,)=,g(x,)*,p(x,),s(x,),结论：伴随式中包含有,E(x,),的信息。,伴随式与错误图样,接收码字,R(x,),的错误码元个数为,t,位，,当,t,(d,min,1)/2,时，,任何一个重量为,t,的错误图样对应一个伴随式,可以进行纠错,(,见下页表,),当,(,d,min,1)/2,t,d,min,1,时，,多个错误图样对应一个伴随式,不能进行纠错，但可以检出错误,当,t,d,min,时，,伴随式等于零,不能检出错误,伴随式不等于零,可以检出错误,伴随式与错误图样,错误图样,伴随式,e,6,e,5,e,4,e,3,e,2,e,1,e,0,s,2,s,1,s,0,0,0,0,0,0,0,1,0,0,1,0,0,0,0,0,1,0,0,1,0,0,0,0,0,1,0,0,1,0,0,0,0,0,1,0,0,0,0,1,1,0,0,1,0,0,0,0,1,1,0,0,1,0,0,0,0,0,1,1,1,1,0,0,0,0,0,0,1,0,1,循环码的检错能力,错误图样多项式,E(x,),，有,2,n,种排列，能够被,g(x,),除尽的属于不可检出的错误。,干扰为单个错位时，,E(x,),x,i,，,能够检查出来。,当,g(x,),满足，,g(x,)=(x+1)g,1,(x),时，可以检查出奇数个错误。,突发错误,突发错误：误码序列中的误码成串集中出现,突发长度：第一个错误码元与最后一个错误码元之间的长度,突发干扰的错误图样：,E(x,)=x,i,B(x),其中，,B(x,)=x,b-,1,+B,b-2,x,b-,2,+B,1,x+1,循环码的检错能力,由,n-k,次多项式,g(x,),生成的循环码，具有以下特性：,（,1,）可检出突发长度,b,不大于,n-k,的突发错误,（,2,）当突发长度,b,大于,n-k,时，不能检错出的错误占同样长度的可能的突发错误总数的百分比为：,当,b-1,n-k,时，,2,-(n-k),当,b-1=,n-k,时，,2,-(n-k-1),系统循环码的编译码电路,r,0,r,1,r,n-k-1,g,n-k,=1,g,0,=1,g,1,g,n-k-1,r,0,r,1,r,n-k-1,g,n-k,=1,g,0,=1,g,1,g,n-k-1,系统循环码的编译码电路,串口接口电路：,Z80-SIO,、,Intel8274,、,Intel8253,生成多项式：,g(x,),x,16,+x,12,+x,5,+1,r,0,r,1,r,n-k-1,g,n-k,=1,g,0,=1,g,1,g,n-k-1,g,1,g,n-k-1,系统循环码的编译码算法,m(x,)=m,39,x,39,m,38,x,38,m,1,x,m,0,=m,(x)x,32,+m,(x)x,24,+m,(x)x,16,+m,(x)x,8,+,m,(x,),=(m,(x)x,8,+m,(x)x,8,+m,(x)x,8,+m,(x)x,8,+m,(x),x,8,m(x)=(m,(x)x,8,+m,(x)x,8,+m,(x)x,8,+m,(x)x,8,+m,(x)x,8,系统循环码的编译码算法,设,k,位信息序列为：,m=m,k-1,m,k-2,m,1,m,0,(1),把信息序列分成长度为,n-k,位的,p,个信息段，记为,m=M,1,M,2,M,p,(2),第一个信息段,M,1,后面添加,n-k,个零，并除以生成多项式,g(x,),得余式,r1,，与第二个信息段,M,2,模,2,加得,M,2,(3)M,2,后面添加,n-k,个零，除以生成多项式,g(x,),得余式,r,2,，与第三个信息段,M,3,模,2,加得,M,3,(4),对,M,2,按上述步骤进行得,M,4,，直到对,M,p,，计算得到,r,p,，即为信息序列,m,编码的余数。,信息序列对应的码字是,c=M,1,M,2,M,p,r,p,软件表法,对于长度为,n-k,的二进制序列，最多有,2,n-k,种不同的取值，即被除数最多有,2,n-k,种不同取值。,事先对,2,n-k,个被除数进行对生成多项式的除法运算，将余数存放在内存中，建立中间余数表。,进行长度为,n-k,的进行编码除法运算时，只需查表即可得到对应的余式。,软件表法,当,n,-,k,较大时，软件表占用内存较多。,例如对于信息序列,m(x,)=m,15,x,15,+m,14,x,14,+m,1,x+m,0,和生成多项式,g(x,)=x,16,+g,15,x,15,+g,1,x+1,将,m(x,)=,m,(x,),m,(x,),m,(x,)=m,15,x,15,+m,14,x,14,+m,9,x,9,+m,8,x,8,m,(x,)=m,7,x,7,+m,6,x,6,+m,1,x+m,0,两段查表法,软件表法：,以内存空间的支出换取运算速度的提高,若内存较小时，可以使用两段查表法：,把一个信息段分成两部分，一段高半段取零，一段低半段取零，分段后的数据段分别建立中间余数表，可以进一步减小内存的占用,