信息论第五章优秀课件.ppt

《信息论第五章优秀课件.ppt》由会员分享，可在线阅读，更多相关《信息论第五章优秀课件.ppt（28页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、信息论课件第五章第1页，本讲稿共28页(1)循环码的性质n循环码是线性分组码的一个重要子类；n由于循环码具有优良的代数结构，使得可用简单的反馈移位寄存器实现编码和伴随式计算，并可使用多种简单而有效的译码方法；n循环码是研究最深入、理论最成熟、应用最广泛的一类线性分组码。第2页，本讲稿共28页(2)循环码的定义n循环码：如果(n,k)线性分组码的任意码矢C=(Cn1,Cn2,C0)的 i 次循环移位，所得矢量C(i)=(Cn1i,Cn2i,C0,Cn1,Cni)仍是一个码矢，则称此线性码为(n,k)循环码。第3页，本讲稿共28页(3)码多项式n码多项式：为了运算的方便，将码矢的各分量作为多项式的

2、系数，把码矢表示成多项式，称为码多项式。其一般表示式为C(x)=Cn1xn1+Cn2xn2+C0)n码多项式 i 次循环移位的表示方法 记码多项式C(x)的一次左移循环为 C(1)(x)，i 次左移循环为 C(i)(x)第4页，本讲稿共28页n码多项式的模(xn+1)运算n0和1两个元素模2运算下构成域。第5页，本讲稿共28页n码矢 C 循环 i 次所得码矢的码多项式n C(x)乘以 x，再除以(xn+1)，得第6页，本讲稿共28页上式表明：码矢循环一次的码多项式 C(1)(x)是原码多项式 C(x)乘以 x 除以(xn+1)的余式。写作因此，因此，C(x)的 i 次循环移位 C(i)(x)是

3、 C(x)乘以 xi 除以(xn+1)的余式，即n结论：循环码的码矢的 i 次循环移位等效于将码多项式乘 xi 后再模(xn+1)。第7页，本讲稿共28页(4)举例：(7,3)循环码n可由任一个码矢，比如(0011101)经过循环移位，得到其它6个非0码矢；n也可由相应的码多项式(x4+x3+x2+1)，乘以xi(i=1,2,6)，再模(x7+1)运算得到其它6个非0码多项式。移位过程和相应的多项式运算如表6.3.1所示。第8页，本讲稿共28页第9页，本讲稿共28页(1)循环码的生成矩阵n根据循环码的循环特性，可由一个码字的循环移位得到其它的非0码字。在(n,k)循环码的 2k 个码字中，取前

4、(k1)位皆为0的码字 g(x)（其次数r=nk），再经(k1)次循环移位，共得到 k 个码字:g(x),xg(x),xk1 g(x)这 k 个码字显然是相互独立的，可作为码生成矩阵的 k 行，于是得到循环码的生成矩阵 G(x)第10页，本讲稿共28页(2)循环码的生成多项式n码的生成矩阵一旦确定，码就确定了；n这就说明：(n,k)循环码可由它的一个(nk)次码多项式 g(x)来确定；n所以说 g(x)生成了(n,k)循环码，因此称 g(x)为码的生成多项式。第11页，本讲稿共28页(3)生成多项式和码多项式的关系n定理定理：在(n,k)循环码中，生成多项式 g(x)是惟一的(nk)次码多项式

5、，且次数是最低的。n定理定理：在(n,k)循环码中，每个码多项式 C(x)都是 g(x)的倍式；而每个为 g(x)倍式且次数小于或等于(n1)的多项式，必是一个码多项式。第12页，本讲稿共28页n定理定理6.3.36.3.3(定理6.3.2的逆定理)：在一个(n,k)线性码中，如果全部码多项式都是最低次的(nk)次码多项式的倍式，则此线性码为一个(n,k)循环码。注注：一般说来，这种循环码仍具有把(n,k)线性码码中任一非0码矢循环移位必为一码矢的循环特性，但从一个非0码矢出发，进行循环移位，就未必能得到码的所有非0码矢了。所以称这种循环码为推广循环码。第13页，本讲稿共28页n码字循环关系图

6、n单纯循环码的码字循环图：(7,3)循环码第14页，本讲稿共28页n推广循环码的码字循环图：(6,3)循环码第15页，本讲稿共28页(4)如何寻找一个合适的生成多项式n由下面式子可知：循环码的多项式等于信息多项式乘以生成多项式。这说明：对一个循环码只要生成多项式一旦确定，码就确定了，编码问题就解决了。所以：作一循环码的关键，就在于寻找一个适当的生成多项式。第16页，本讲稿共28页n定理定理：(n,k)循环码的生成多项式 g(x)是(xn+1)的因式，即 xn+1=h(x)g(x)。n定理定理：若 g(x)是一个(nk)次 多项式，且为(xn+1)的因式，则 g(x)生成一个(n,k)循环码。结

7、论结论：当求作一个(n,k)循环码时，只要分解多项式(xn+1)，从中取出(nk)次因式作生成多项式即可。第17页，本讲稿共28页n举例：求(7,3)循环码的生成多项式。解：分解多项式 xn+1，取其4次因式作生成多项式x7+1=(x+1)(x3+x2+1)(x3+x+1)可将一次和任一个三次因式的乘积作为生成多项式，因而可取 g1(x)=(x+1)(x3+x2+1)=x4+x2+x+1 或 g2(x)=(x+1)(x3+x+1)=x4+x3+x2+1第18页，本讲稿共28页(5)循环码的监督多项式和监督矩阵n循环码的监督多项式：设 g(x)为(n,k)循环码的生成多项式，必为(xn+1)的因

8、式，则有 xn+1=h(x)g(x)，式中h(x)为 k 次多项式，称为(n,k)循环码的监督多项式。n(n,k)循环码也可由其监督多项式完全确定。n举例：(7,3)循环码 x7+1=(x3+x+1)(x4+x2+x+1)n4次多项式为生成多项式g(x)=x4+x2+x+1=g4x4+g3x3+g2x2+g1x+g0n3次多项式是监督多项式h(x)=x3+x+1=h3x3+h2x2+h1x+h0第19页，本讲稿共28页n循环码的监督矩阵n由等式 x7+1=h(x)g(x)两端同次项系数相等得n将上面的方程组 写成矩阵形式第20页，本讲稿共28页n上式中，列阵的元素是生成多项式 g(x)的系数，

9、是一个码字，那么第一个矩阵则为(7,3)循环码的监督矩阵监督矩阵，即第21页，本讲稿共28页n循环码监督矩阵的构成循环码监督矩阵的构成n由式(6.3.2)可见，监督矩阵的第一行是码的监督多项式 h(x)的系数的反序排列反序排列，第二、三、四行是第一行的移位；n可用监督多项式的系数来构成监督矩阵第22页，本讲稿共28页n(n,k)循环码的监督矩阵n对偶问题n如果 xn+1=h(x)g(x)，其中 g(x)为(nk)次多项式，以 g(x)为生成多项式，则生成一个(n,k)循环码；n以 h(x)为生成多项式，则生成(n,nk)循环码；n这两个循环码互为对偶码。第23页，本讲稿共28页线性码的译码是根

10、据接收字多项式的伴随式和可纠的错误图样间的一一对应关系，由伴随式得到错误图样；循环码是线性码的一个特殊子类，循环码的译码与线性码的译码步骤基本一致。不过由于循环码的循环特性，使它的译码更加简单易行；循环码的译码过程仍包括三个步骤：接收多项式的伴随式计算；求伴随式对应的错误图样；用错误图样纠错。6.3.6 循环码的译码第24页，本讲稿共28页(1)根据伴随式定义 ST=HRT 计算伴随式Sn设n设第25页，本讲稿共28页n这是前面介绍过的由接收矢量相应分量直接求和计算伴随式的方法，对所有线性码都适用。第26页，本讲稿共28页第27页，本讲稿共28页(4)接收字循环移位的伴随式与伴随式循环移位的关系n定理定理6.3.76.3.7：设 S(x)为接收矢量 R(x)的伴随式，则 R(x)的循环移位 xR(x)(mod(xn+1)的伴随式 S(1)(x)等于伴随式 S(x)的循环移位 xS(x)(mod g(x)，即S(1)(x)xS(x)(mod g(x)n上式说明上式说明：接收矢量的循环移位（mod(xn+1)运算下）与伴随式在模 g(x)运算下（即在除以 g(x)的伴随式计算电路中）的循环移位是一一对应的。第28页，本讲稿共28页