循环码BCH码卷积码

*,*,单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,10.6,循环码,10.6.1 循环码的概念：,循环性是指任一码组循环一位后仍然是该编码中的一个码组。,例：一种(7,3)循环码的全部码组如下,表中第2码组向右移一位即得到第5码组；第5码组向右移一位即得到第7码组。,码组编号,信息位,监督位,码组编号,信息位,监督位,A,6,a,5,a,4,a,3,a,2,a,1,a,0,a,6,a,5,a,4,A,3,a,2,a,1,a,0,1,000,0000,5,100,1011,2,001,0111,6,101,1100,3,010,1110,7,110,0101,4,011,1001,8,111,0010,1,一般情况,若(,a,n,-1,a,n,-2,a,0,)是循环码的一个码组，则循环移位后的码组：(,a,n,-2,a,n,-3,a,0,a,n,-1,),(,a,n,-3,a,n,-4,a,n,-1,a,n,-2,),(,a,0,a,n,-1,a,2,a,1,),仍然是该编码中的码组。,多项式表示法,一个长度为,n,的码组(,a,n,-1,a,n,-2,a,0,)可以表示成,上式中,x,的值没有任何意义，仅用它的幂代表码元的位置。,例：码组1 1 0 0 1 0 1可以表示为,2,10.6.2 循环码的运算,整数的按模运算,在整数运算中，有模,n,运算。例如，在模2运算中，有,1+1=2,0(模2)，1+2=3,1(模2)，2,3=6,0(模2),等等。,一般说来，若一个整数,m,可以表示为,式中，,Q,为整数，则在模,n,运算下，有,m,p,(模,n,),所以，在模,n,运算下，一个整数,m,等于它被,n,除得的余数。,3,码多项式的按模运算,若任意一个多项式,F,(,x,)被一个,n,次多项式,N,(,x,)除，得到商式,Q,(,x,)和一个次数小于,n,的余式,R,(,x,)，即,则在按模,N,(,x,)运算下，有,这时，码多项式系数仍按模2运算。,例1：x,3,被(x,3,+1)除，得到余项1，即,例2：,因为,x,x,3,+1,x,4,+,x,2,+1,x,4,+,x,x,2,+,x,+1,在模2运算中加法和减法一样。,4,循环码的数学表示法,在循环码中，设T(,x,)是一个长度为,n,的码组，若,则,T,(,x,)也是该编码中的一个码组。,上式中的,T,(,x,)正是码组,T,(,x,)向左循环移位,i,次的结果。,例：一循环码为1100101，即,若给定,i,=3，则有,上式对应的码组为0101110，它正是,T,(,x,)向左移3位的结果。,结论：一个长为,n,的循环码必定为按模(,x,n,+1)运算的一个余式。,5,循环码的生成,有了生成矩阵,G,，就可以由,k,个信息位得出整个码组：,例：,式中，,生成矩阵,G,的每一行都是一个码组。,因此，若能找到,k,个已知的码组，就能构成矩阵,G,。如前所述，这,k,个已知码组必须是线性不相关的。,在循环码中，一个(,n,k,)码有2,k,个不同的码组。若用,g,(,x,)表示其中前(,k,-1)位皆为“0”的码组，则,g,(,x,)，,x g,(,x,)，,x,2,g,(,x,)，,，,x,k-1,g,(,x,)都是码组，而且这,k,个码组是线性无关的。因此它们可以用来构成此循环码的生成矩阵,G,。,6,在循环码中除全“0”码组外，再没有连续,k,位均为“0”的码组。否则，在经过若干次循环移位后将得到,k,位信息位全为“0”，但监督位不全为“0”的一个码组。这在线性码中显然是不可能的。,因此，,g,(,x,)必须是一个常数项不为“0”的(,n,-,k,)次多项式，而且这个,g,(,x,)还是这种(,n,k,)码中次数为(,n,k,)的唯一一个多项式。因为如果有两个，则由码的封闭性，把这两个相加也应该是一个码组，且此码组多项式的次数将小于(,n,k,)，即连续“0”的个数多于(,k,1)。显然，这是与前面的结论矛盾的。,我们称这唯一的(,n,k,)次多项式,g,(,x,)为码的,生成多项式,。一旦确定了,g,(,x,)，则整个(,n,k,)循环码就被确定了。,7,生多项式的性质：,（1）g(x)是一(n-k)次多项式；,（2）g(x)的常数项不为0；,（3）g(x)必须是（x,n,+1）的一个因子。,8,因此，循环码的生成矩阵,G,可以写成,例：,上表中的编码为(7,3)循环码，,n,=7,k,=3,n,k,=4，其中唯一的一个(,n,k,)=4次码多项式代表的码组是第二码组0010111，与它对应的码多项式，即生成多项式，为,g,(,x,)=,x,4+,x,2+,x,+1。,码组编号,信息位,监督位,码组编号,信息位,监督位,A,6,a,5,a,4,a,3,a,2,a,1,a,0,a,6,a,5,a,4,A,3,a,2,a,1,a,0,1,000,0000,5,100,1011,2,001,0111,6,101,1100,3,010,1110,7,110,0101,4,011,1001,8,111,0010,9,g,(,x,)=,x,4+,x,2+,x,+1 即 “1 0 1 1 1”,将此,g,(,x,)代入上矩阵，得到,或,上式不符合,G,=,I,k,Q,形式，所以它不是典型生成矩阵。但它经过线性变换后，不难化成典型阵。,此循环码组的多项式表示式,T,(,x,)：,上式表明，所有码多项式,T,(,x,)都能够被,g,(,x,)整除，而且任意一个次数不大于(,k,1)的多项式乘,g,(,x,)都是码多项式。,10,寻求码生成多项式,因为任意一个循环码,T,(,x,)都是,g,(,x,)的倍式，故它可以写成,T,(,x,)=,h,(,x,),g,(,x,),而生成多项式g(x)本身也是一个码组，即有,T,(,x,)=,g,(,x,),由于码组,T,(,x,)是一个(,n,k,)次多项式，故,x,k,T,(,x,)是一个,n,次多项式。由,可知，x,k,T,(,x,)在模(x,n,+1)运算下也是一个码组，所以有,上式左端分子和分母都是,n,次多项式，故相除的商式,Q,(,x,)=1。因此，上式可以写成,11,将,T,(,x,)=,h,(,x,),g,(,x,)和,T,(,x,)=,g,(,x,)代入,化简后，得到,上式表明，生成多项式,g,(,x,)应该是(,x,n,+1)的一个因子。,例：(,x,7,+1)可以分解为,为了求出(7,3)循环码的生成多项式,g,(,x,)，需要从上式中找到一个(,n k,)=4次的因子。这样的因子有两个，即,以上两式都可以作为生成多项式。,选用的生成多项式不同，产生出的循环码码组也不同。,12,10.6.3 循环码的编码方法,用,x,n-k,乘,m,(,x,)。这一运算实际上是在信息码后附加上(,n,k,)个“0”。例如，信息码为110，它写成多项式为,m,(,x,)=,x,2,+,x,。当,n,k,=7 3=4时，,x,n-k,m,(,x,)=,x,4,(,x,2,+,x,)=,x,6,+,x,5,，它表示码组1100000。,用,g,(,x,)除,x,n-k,m,(,x,)，得到商,Q,(,x,)和余式,r,(,x,)，即有,例：若选定,g,(,x,)=,x,4,+,x,2,+,x,+1，则有,上式是用码多项式表示的运算。它和下式等效：,编出的码组,T,(,x,)为：,T,(,x,)=,x,n-k,m,(,x,)+,r,(,x,),在上例中，,T,(,x,)=1100000+101=1100101,13,10.6.4 循环码的解码方法,在检错时：当接收码组没有错码时，接收码组,R,(,x,)必定能被,g,(,x,)整除，即下式,中余项,r,(,x,)应为零；否则，有误码。,当接收码组中的错码数量过多，超出了编码的检错能力时，有错码的接收码组也可能被,g,(,x,)整除。这时，错码就不能检出了。,在纠错时：,用生成多项式,g,(,x,)除接收码组,R,(,x,)，得出余式,r,(,x,)。,按照余式,r,(,x,)，用查表的方法或计算方法得出错误图样,E,(,x,)。,从R(,x,)中减去,E,(,x,)，便得到已经纠正错码的原发送码组,T,(,x,)。,14,.BCH码,BCH码是具有纠正多个随机差错功能的循环码，它是循环码的一个重要子类。这种码是建立在现代代数理论基础之上的，数学结构严谨，在译码同步等方面有许多独特的优点，故在数字微波以及数字卫星传输设备中常使用这种能纠正多重错误的BCH,码来降低传输误码率。,BCH码可分为两类，一类是原本BCH码，另一类是非原本BCH码。原本BCH,码的特点是码长为,2 m1(m为正整数)，其生成多项式是由若干最高次数为m的因式相乘构成的，且具有如下形式：,15,(2-5),其中，,t,为纠错个数，,m,i,(,t,)为最小多项式，LCM,代表最小公倍式。,具有上述特点的循环码就是BCH,码，,其最小码距,d,2,t,1(在一种编码中，任意两个许用码组之间的对应位上所具有的最小不同二进制码元数，称为最小码距)。由此可见，一个(2,m,1,，,k,)循环码的2,m,1,k,阶生成多项式必定是由,x,2m1,1的全部或部分因式组成的。而非原本BCH,码的生成多项式中却不包含这种原本,多项式，并且码长,n,是2,m,1的一个因子，即2,m,1一定是码长,n,的倍数。,16,下面以码长为15的BCH,码为例来进行说明。,可见此时,m,=4(2,4,115)，即表示最高次数为4。由,x,n,1的因式分解可知：,17,其中，,m,7,(,x,)是,m,1,(,x,)的反多项式(若有限域上的,m,次多项式为,则,称为,f,(,x,)的反多项式)。对于(15，5)BCH,码的生成多项式为,18,可见它能纠正3(由2,t,1=5得到)个随机差错。,19,BCH码是能够纠正多个随机错码的循环码。,BCH码分为两类：本原BCH码和非本原BCH码。,本原BCH码：码长,n,=2,m,1(,m,3，任意正整数)，它的生成多项式,g,(,x,)中含有最高次数为,m,次的本原多项式；,非本原BCH码：码长,n,是(2,m,1)的一个因子，它的生成多项式,g,(,x,)中不含有最高次数为,m,的本原多项式。,BCH码的工程设计：可以用查表法找到所需的生成多项式。,例：二进制非本原BCH码的生成多项式系数,表中,g,(,x,)是用8进制数字表示的；,t,为纠错能力。,n,k,t,g,(,x,),n,k,t,g,(,x,),17,21,23,33,41,9,12,12,22,21,2,2,3,2,4,727,1663,5343,5145,6647133,47,65,65,73,24,53,40,46,5,2,4,4,43073357,10761,354300067,1717773537,20,常用BCH码：,戈莱(Golay)码：,(23,12)非本原BCH码，它能纠正3个随机错码，并且容易解码。,扩展BCH码(,n,+1,k,)：,BCH码的长度为奇数。在应用中，为了得到偶数长度的码，并增大检错能力，可以在BCH码生成多项式中乘上一个因式(,x,+1)，从而得到扩展BCH码(,n,+1,k,)。,扩展BCH码已经不再具有循环性。,扩展戈莱码(24,12)：,其最小码距为8，码率为1/2，能够纠正3个错码和检测4个错码,。,21,前面所介绍的BCH码都是二进制的，即BCH码的每一个码元(元素)的取值为0或1。如果BCH中的每一个元素用多进制表示的话，例如2,m,进制，那么BCH,中的每个元素就可以用一个,m位的二进制码组表示，我们称这种多进制的BCH码为RS码。例如对于其信息位为10011的(15，5)BCH码序列是。如果进行RS,编码，,取,m,=2，即每一位将用一个2位的二进制码表示(若用01代表“0”码，用10代表“1”码)，那么输出的RS,码就是,。可见，当