《信息论与编码第四讲.ppt》由会员分享，可在线阅读，更多相关《信息论与编码第四讲.ppt（36页珍藏版）》请在三一办公上搜索。
1、第四讲,三、循环码,主要内容,1、循环码的定义2、循环码的多项式描述3、循环码编码方法4、循环码的译码,1957年美国人E.Prange提出循环码概念；1961年提出了一种译码器，主要用于检错；1960年前后提出了两类重要的循环码：BCH码和RS码。1965年和提出了有效的译码算法后，这种循环码才获得了实际应用。,3.1 循环码的定义一个线性分组码，若将其任意一个码字的码元向右或向左循环移一位，所得的仍然是码字，则称该码为循环码。例汉明循环码C的生成矩阵G和校验矩阵H 依次令m=(0000)(1111)代入方程CmG 可得16个码字。经分析，将16个码字归结为4个循环环 第一循环 第二循环 第
2、三循环 第四循环(1011000)(1110100)(0000000)(1111111)(0110001)(1101001)(1100010)(1010011)(1000101)(0100111)(0001011)(1001110)(0010110)(0011101)(0101100)(0111010),3.2 循环码的多项式描述GF(2)上n维矢量空间Vn中的任一矢量V=(vn-1,v1,v0)vi GF(2)可与GF(2)域上多项式V(x)一一对应如下：V=(vn-1,v1,v0)V(x)=vn-1 xn-1+v1 x+v0多项式的各系数就是矢量各元素的值，x的幂次指示对应元素所在位置。码
3、空间是矢量空间Vn的一个子空间，因此n重矢量不一定是码矢量，n次多项式不一定是码多项式。,码矢C0=(cn-1,c1,c0)右循环一位C1=(cn-2,c1,c0,cn-1,)也是码矢。它们各自对应的码多项式是:C0(x)=cn-1 xn-1+cn-2 xn-2+c1 x+c0C1(x)=cn-2 xn-1+cn-3 xn-2+c0 x+cn-1比较两者，可知C1(x)=xC0(x),mod(xn+1)(3-2)以此类推，循环码循环移2位、移3位、移n-1位后仍然应是码字,于是得到下面一系列等式：C2(x)=xC1(x)=x2C0(x),mod(xn+1)C3(x)=xC2(x)=x3C0(x
4、),mod(xn+1):C n-1(x)=xC n-2(x)=xn-1C0(x),mod(xn+1),由码空间的封闭性，可知码多项式C0(x),C n-1(x)的线性组合仍应是码多项式：C(x)=an-1xn-1C0(x)+an-2xn-2C0(x)+a1xC0(x)+a0C0(x)=(an-1 xn-1+an-2 xn-2+a1 x+a0)C0(x)=A(x)C0(x)mod(xn+1)(3-3)C0(x)是码多项式，A(x)是n-1次多项式，但不一定是码多项式。式(4-3)给出的结论是：码多项式与任意n-1次多项式作运算后，结果一定回落到码空间。,2.3 循环码生成多项式定理4.2 在一个
5、GF(2)域上的(n,k)循环码中，一定存在唯一的一个次数最低的(n-k)次首一码多项式g(x)=xn-k+gn-k-1 x n-k-1+g1 x+1使所有码多项式都是g(x)的倍式，且所有小于n次的g(x)的倍式都是码多项式。即 C(x)m(x)g(x)及 g(x)|C(x)“所有小于n次的g(x)的倍式都是码多项式”意味着m(x)g(x)一定是码字，其中m(x)是GF(2)上小于k次的任意多项式，以致它与(n-k)次的g(x)相乘后所得倍式的次数一定小于n次。,2.4 循环码编码方法2.4.1 编码原理 定理4.3：(n，k)循环码的生成多项式g(x)一定是(xn-1)的因式，即一定存在一
6、个多项式h(x)，满足：(xn-1)g(x)h(x)或 g(x)|(xn-1)反之，如果g(x)是(xn-1)的（n-k）次因式，g(x)一定是某(n，k)循环码的生成多项式。,上述定理告诉了构造(n，k)循环码的方法如下：对xn-1(在二元域中等效于对xn+1)实行因式分解,找出其中的（n-k）次因式。以找出的（n-k）次因式为循环码生成多项式g(x)，与信息多项式m(x)相乘，即得码多项式：C(x)=m(x)g(x)。,例3.1 分析码长n=7的所有可能二进制循环码解：将GF(2)上多项式(x71)因式分解，得：(x71)=(x1)(x3x1)(x3x21)因此(x71)因式的次数可以有以
7、下四种1次(x1)3次(x3x1)或(x3x21)4次(x1)(x3x1)或(x1)(x3x21)6次(x3x1)(x3x21)(n-k)可取1、3、4、6,因此断言：存在(7,6)，(7,4)，(7,3)，(7,1)循环码，而不存在(7,2)，(7,5)循环码。,要构成(7,3)循环码，(n-k)=4的因式有(x1)(x3x1)或(x1)(x3x21)两个，任选其中一个,比如g(x)=(x+1)(x3+x+1)=(x4+x3+x2+1)作生成多项式,令 C(x)=m(x)g(x)=(m2x2+m1x+m0)(x4+x3+x2+1)可产生循环码集。例如m=(011)即 m(x)=(x+1)时(
8、x+1)(x4x3x21)=x5+x2+x1+1 对应码矢C=(0100111)类推，得全部码集。经检验，符合“码字的循环仍是码字”,用上述方法可得循环码，但未必是系统的。若想得到系统循环码，即码字的前k位原封不动照搬信息位而后(n-k)位为校验位，具有如下形式 C(x)=xn-k m(x)+r(x)(3-5)r(x)是与码字中(n-k)个校验元相对应的(n-k-1)次多项式，可将式(4-5)写成 xn-k m(x)=C(x)+r(x)等式两边除以生成多项式g(x)，由于g(x)能整除C(x)，degr(x)degg(x),因此有 r(x)=xn-k m(x)mod g(x)即r(x)等于xn
9、-k m(x)除以g(x)的余式。,于是得到了产生系统循环码的具体方法.将信息多项式m(x)预乘xn-k,即右移（n-k）位。.将xn-km(x)除以g(x)，得余式r(x)。.系统循环码的码多项式可写成：C(x)=xn-km(x)+r(x),例3.2(7,3)循环码的生成多项式是g(x)=x4+x3+x2+1,用式(4-6)产生循环码集。解：当输入信息 m(011)即m(x)=(x+1)时，xn-km(x)=x4(x+1)=x5+x4(x5+x4)除以(x4+x3+x2+1)得余式(x3+x)C(x)=xn-km(x)+r(x)=(x5+x4)+(x3+x),对应码矢(0111010)依次将
10、(000)(111)代入可得表4-2。表4-1对比，码集未变(2个循环环)而映射规则变了。,根据定理4.3，应有 xn-1=g(x)h(x)(3-7)如果g(x)是循环码的生成多项式，那么h(x)一定就是循环码的校验多项式。这是因为对于任意一个码多项式C(x)，必有 C(x)h(x)=0 mod(xn-1)C(x)h(x)=m(x)g(x)h(x)=m(x)(xn-1)是(xn-1)的倍式，一定能被(xn-1)整除 mod(xn-1)运算后必定为零。,2.3.2 循环码的生成矩阵=mk-1 mk-2m0=mk-1 mk-2m0 其中，g(x)=gn-k xn-k+g1 x+g0,将矩阵中的多项
11、式改写成对应的n重矢量形式，得矢量的矩阵表达式：C=(cn-1,c1,c0)=mk-1,m1,m0=mG这里，定义(kn)矩阵G为循环码的生成矩阵。,生成矩阵G的每一行是n重空间的一个基底，也是k维n重码空间的一个基底。在一般线性分组码的生成矩阵中，这些基底除线性无关外没有什么特殊关系。然而从式(4-10)看到，循环码生成矩阵的k个基底，是一个基底(gn-k g1 g0 0 0)的循环移位得出的。因此只要知道一个基底，其它(k-1)个基底可通过循环移位得到。,循环码的(n-k)n阶的校验矩阵可写为：H=(3-13)循环码生成矩阵G与校验矩阵的乘积一定是的零阵。GHT0(3-14),例3.3 以
12、 x3+x+1为生成多项式生成一个（7,4）循环码,求此码的生成矩阵和校验矩阵。如果要求生成的（7,4）循环码是系统的，生成矩阵该作如何改变？解：可知 x7+1=(x+1)(x3+x2+1)(x3+x+1)本题n-k=7-4=3,因此生成多项式g(x)应是3次。(x7+1)有两个3次因式，取其中任意一个都能生成（7,4）循环码。现取g(x)=x3+x+1，则h(x)=(x+1)(x3+x2+1)=x4+x2+x+1。由式（3-10），（3-13）可得,1011000 1110100G=0101100 H=0111010 0010110 0011101 0001011对矩阵G的行进行运算，将第+
13、行作为第1行，第+行相加后作为第2行，得：1000101+1110100 G=0100111+H=0111010 0010110 1101001 0001011这就是系统循环码的生成矩阵和校验矩阵。,（1）第一种乘法器 对于C(x)=A(x)B(x)，多项式C(x)的最高次项系数是A(x)B(x)各自最高次项的乘积，C(x)的次高次项系数等于A(x)最高次项系数与B(x)次高次项系数之积加上B(x)最高次项系数与A(x)次高次项系数之积，以此类推，C(x)最低次的常数项等于A(x)常数项与B(x)常数项之积。由此想到，如果把A(x)、B(x)和C(x)的系数单独抽出来组成三个q进制序列A、B、
14、C。那么C恰好是A和B的卷积，体现这种关系的卷积电路也就是乘法电路。,2.4.3 循环码的编码电路,例3.4 求GF(2)上多项式A(x)=x3+x和B(x)=x3+x+1的乘积及相应的卷积型乘法电路。解：分别抽出系数，得到二元序列A=a3 a2 a1 a0=1010和 B=b3 b2 b1 b0=1011。根据序列卷积的运算规则，将A序列从右到左 a0 a1 a2 a3、B序列从左到右b3 b2 b1 b0排序。电路图如下 结果C(x)=x6+x3+x2+x,c0c1c5c6 out b3=1 b2=0 b1=1 b0=1ina0a1a2a3,D,D,D,（2）第二种乘法器 这种乘法器是根据
15、乘法竖式运算过程设计的。采用上例的多项式为例说明这种乘法器的工作原理。例4.12用第二种乘法器计算GF(2)上多项式A(x)=x3+x和B(x)=x3+x+1的乘积C(x)=A(x)B(x)解：将4位系数抽出，得A=(a0a1a2a3)=(0101)和B=(b0b1b2b3)=(1101),b0b1b2b3=1101a0a1a2a3=0101B a3=1101 Ba2=0000 0110Ba1=1101 1110Ba0 0000 0111结果1001110,c0c1c5c6 outb0=1 b1=1 b2=0 b3=1ina0a1a2a3 依次输入 B a3=1101 B a2=0000 B
16、a1=1101 B a0=0000,D,D,D,（3）多项式除法电路 GF(q)上的被除式A(x)和除式B(x)满足 A(x)=q(x)B(x)+r(x)(3-38)其中，q(x)是商，r(x)是余式，degr(x)B(x)。可以用长除法求q(x)和r(x)。为了便于计算，不妨把系数单独抽出来运算。例3.13 二元域多项式A(x)=x6+x4+x2+x+1 及 B(x)=x3+x+1，求：A(x)除以B(x)的余式r(x),1001(商式)1011 1010111 1011(第3拍)0011 0000 0111 0000 1111 1011(余式)100结果,余式r(x)=x2,k1 k2b0
17、=1 b1=1 b2=0 b3=1 r0=0 r1=0 r2=11110101(高位先)1001a0a1a2a3a4a5a6 q0q1q2q3 图4-6 除法电路,D1,D2,D3,（3）多项式乘除法电路例4.14 二元域多项式A(x)=a6x6+a5x5+a1x+a0B(x)=x3+x+1，G(x)=x5+x2+1，试画出A(x)B(x)/G(x)的乘除法电路。,g0=1 g1=0 g2=1 g3=0 g4=0 g5=1 b0=1 b1=1 b2=0 b3=1 输出输入a0a1a2a6图4-7 例4.14的二进制乘除法器(m l),D1,D2,D3,D4,D5,（4）多项式乘除法电路的系统循
18、环码编码器式(4-5)系统循环码C(x)=xn-k m(x)+r(x)中，xn-k m(x)=g(x)q(x)+r(x)，即 r(x)是m(x)乘以 xn-k除以g(x)所得余式。例：(7，4)系统循环汉明码 g(x)=x3+x+1。此时xn-k=x3，C(x)=x3 m(x)+r(x)。,k11 x k2 x3m0 m1 m2 m3前4拍k1合k2断，后3拍k1断k2合,D1,+,D2,D3,尽管可采用不同的理论分析方法寻出不同特性的循环码，然而各种循环码g(x)的外部形式相同，编码电路也一样易于实现。由编码理论推导出的循环码纠错能力只是理论值，在现实中能否达到这个理论值还与所用的译码方法有
19、关。一个好的译码方法，不仅使纠错能力能达到理论极限，而且应能高速度、低成本地实现。但译码电路通常要比编码电路复杂得多。因此理论的复杂性常体现在编码上，而工程的复杂性常体现在译码上。,3.5 循环码的译码,一般线性分组码的描述基于矩阵发码C=(cn-1,c1,c0)，收码R=(rn-1,r1,r0)差错图案E=(en-1,e1,e0)，伴随式S=(sn-k-1,s1,s0)及关系式 R=CE(3-14)S=RHT=EHT(3-15)循环码的描述基于多项式 码多项式C(x)=cn-1xn-1+cn-2xn-2+c1x+c0 收码 R(x)=rn-1xn-1+rn-2xn-2+r1x+r0 差错图案
20、E(x)=en-1xn-1+en-2xn-2+e1x+e0 及关系式：C(x)+E(x)=R(x)(3-17),定义：伴随式S(x)是收码R(x)除以生成多项式g(x)后的余式，即 S(x)=R(x)mod g(x)(3-44)这里S(x)=sn-k-1xn-k-1+sn-k-2xn-k-2+s1x+s0将式(4-42)代入(4-43)S(x)=R(x)=C(x)+E(x)=m(x)g(x)+E(x)=E(x)mod g(x)(3-45)伴随式与差错图案关系：伴随式S(x)等于模g(x)运算下的差错图案E(x)。,循环码译码可分成四步 由接收码R(x)计算伴随式S(x)。（用g(x)除法电路）
21、由伴随式S(x)求差错图案估计值E(x)。（用各种译码、模式识别方法）由差错图案估值E(x)译出码字C(x)。（用关系式C(x)=R(x)-E(x)）如果是非系统码，求与码字对应的信息组m(用关系式m(x)=C(x)/g(x)）,上面最困难的是第二步。因为S(x)至多是(n-k-1)次多项式,有2n-k种可能的组合，而E(x)最高为n-1次,有2n 种可能的组合。两多项式模g(x)相等并不能推断出两多项式全等。比如从 S(x)=0 mod g(x)并不能确定E(x)=0，因为E(x)可以等于任何a(x)g(x)(其中dega(x)=k1)。但是反过来，若E(x)=0 必有S(x)=0。因此，从伴随式S(x)到E(x)是一点对多点映射，从E(x)到S(x)是多点对一点映射；S(x)=0是无差错的必要条件而不是充分条件。由于从S(x)求E(x)是多解，必须借助最佳或最大似然译码准则使译码差错概率最小。,
