信息论与编码第四讲.ppt

《信息论与编码第四讲.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四讲三、循环码主要内容1、循环码的定义2、循环码的多项式描述3、循环码编码方法4、循环码的译码1957年美国人E.Prange提出循环码概念；1961年J.E.Meggitt提出了一种译码器，主要用于检错；1960年前后提出了两类重要的循环码：BCH码和RS码。1965年E.R.Berlekamp和G.D.Forney提出了有效的译码算法后，这种循环码才获得了实际应用。3.1循环码的定义一个线性分组码，若将其任意一个码字的码元向右或向左循环移一位，所得的仍然是码字，则称该码为循环码。例4.1.1汉明循环码C的生成矩阵G和校验矩阵H依次令m=(0000)…(1111)代入方程C＝m

2、G可得16个码字。经分析，将16个码字归结为4个循环环第一循环第二循环第三循环第四循环(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-1xn

3、-1+…+v1x+v0多项式的各系数就是矢量各元素的值，x的幂次指示对应元素所在位置。码空间是矢量空间Vn的一个子空间，因此n重矢量不一定是码矢量，n次多项式不一定是码多项式。码矢C0=(cn-1,…,c1,c0)右循环一位C1=(cn-2,…,c1,c0,cn-1,)也是码矢。它们各自对应的码多项式是:C0(x)=cn-1xn-1+cn-2xn-2+…+c1x+c0C1(x)=cn-2xn-1+cn-3xn-2+…+c0x+cn-1比较两者，可知C1(x)=xC0(x),mod(xn+1)(3-2)以此类推，循环码循环移2位、移3位、移n-1位后仍然应是码字,于是得到下面一系列等

4、式：C2(x)=xC1(x)=x2C0(x),mod(xn+1)C3(x)=xC2(x)=x3C0(x),mod(xn+1)::Cn-1(x)=xCn-2(x)=xn-1C0(x),mod(xn+1)由码空间的封闭性，可知码多项式C0(x),…,Cn-1(x)的线性组合仍应是码多项式：C(x)=an-1xn-1C0(x)+an-2xn-2C0(x)+…+a1xC0(x)+a0C0(x)=(an-1xn-1+an-2xn-2+…+a1x+a0)C0(x)=A(x)C0(x)mod(xn+1)(3-3)C0(x)是码多项式，A(x)是n-1次多项式，但不一定是码多项式。式(4-3)给出

5、的结论是：码多项式与任意n-1次多项式作运算后，结果一定回落到码空间。2.3循环码生成多项式定理4.2在一个GF(2)域上的(n,k)循环码中，一定存在唯一的一个次数最低的(n-k)次首一码多项式g(x)=xn-k+gn-k-1xn-k-1+…+g1x+1使所有码多项式都是g(x)的倍式，且所有小于n次的g(x)的倍式都是码多项式。即C(x)＝m(x)g(x)及g(x)

6、C(x)“所有小于n次的g(x)的倍式都是码多项式”意味着m(x)g(x)一定是码字，其中m(x)是GF(2)上小于k次的任意多项式，以致它与(n-k)次的g(x)相乘后所得倍式的次数一定小于n次。2.4循环码编码

7、方法2.4.1编码原理定理4.3：(n，k)循环码的生成多项式g(x)一定是(xn-1)的因式，即一定存在一个多项式h(x)，满足：(xn-1)＝g(x)h(x)或g(x)

8、(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的所有可能二进制循环码解：将G

9、F(2)上多项式(x7＋1)因式分解，得：(x7＋1)=(x＋1)(x3＋x＋1)(x3＋x2＋1)因此(x7＋1)因式的次数可以有以下四种1次(x＋1)3次(x3＋x＋1)或(x3＋x2＋1)4次(x＋1)(x3＋x＋1)或(x＋1)(x3＋x2＋1)6次(x3＋x＋1)(x3＋x2＋1)(n-k)可取1、3、4、6,因此断言：存在(7,6)，(7,4)，(7,3)，(7,1)循环码，而不存在(7,2)，(7,5)循环码。要构成(7,3)循环码，(n-k)=4的因式