循环码的多项式描述ppt课件

1、1 、循环码的多项式描画2 、循环码的生成多项式3 、系统循环码4 、多项式运算电路5 、循环码的编码电路6 、循环码的译码7 、循环汉明码8 、缩短循环码循环码(1) 循环码的性质循环码是线性分组码的一个重要子类；由于循环码具有优良的代数构造，使得可用简单的反响移位存放器实现编码和伴随式计算，并可运用多种简单而有效的译码方法；循环码是研讨最深化、实际最成熟、运用最广泛的一类线性分组码。(2) 循环码的定义循环码：假设 (n,k) 线性分组码的恣意码矢C=(Cn1,Cn2,C0) 的 i 次循环移位，所得矢量C(i)=(Cn1i,Cn2i,C0,Cn1,Cni) 仍是一个码矢，那么称此线性码为

2、 (n,k) 循环码。(3) 码多项式码多项式：为了运算的方便，将码矢的各分量作为多项式的系数，把码矢表示成多项式，称为码多项式。其普通表示式为C(x)=Cn1xn1+Cn2xn2+C0)码多项式 i 次循环移位的表示方法 记码多项式C(x)的一次左移循环为 C(1)(x) ，i 次左移循环为 C(i)(x)ininiinininininnnnnnnnnnCxCxCxCxCxxCxCxCxCxCxCxCx1102211)(1103322)1(02211)()()(CCC码多项式的模 (xn+1) 运算0和1两个元素模2运算下构成域。码矢 C 循环 i 次所得码矢的码多项式 C(x) 乘以 x，

3、再除以 (xn+1)，得1)(11)()1(1102123121nnnnnnnnnnxxCxCxCxCxCxCCxxxCCininiinininininnnnCxCxCxCxCxCxCxCx1102211)(02211)()(CC上式阐明：码矢循环一次的码多项式 C(1)(x) 是原码多项式 C(x)乘以 x 除以 (xn+1) 的余式。写作因此， C(x) 的 i 次循环移位 C(i)(x) 是 C(x) 乘以 xi 除以 (xn+1) 的余式，即结论：循环码的码矢的 i 次循环移位等效于将码多项式乘 xi 后再模 (xn+1)。) 1()()()1(nxxxx模CC) 1()()()(ni

4、ixxxx模CC(4) 举例：(7,3) 循环码可由任一个码矢，比如 (0011101) 经过循环移位，得到其它6个非0码矢；也可由相应的码多项式(x4+x3+x2+1)，乘以xi(i=1,2,6)，再模(x7+1)运算得到其它6个非0码多项式。移位过程和相应的多项式运算如表6.3.1所示。(1) 循环码的生成矩阵根据循环码的循环特性，可由一个码字的循环移位得到其它的非0码字。在 (n,k) 循环码的 2k 个码字中，取前 (k1) 位皆为0的码字 g(x)其次数r=nk，再经 (k1) 次循环移位，共得到 k 个码字:g(x),xg(x),xk1 g(x) )()()()()(21xxxxx

5、xxxkkggggG 这 k 个码字显然是相互独立的，可作为码生成矩阵的 k 行，于是得到循环码的生成矩阵 G(x)(2) 循环码的生成多项式码的生成矩阵一旦确定，码就确定了；这就阐明： (n,k) 循环码可由它的一个 (nk) 次码多项式 g(x) 来确定；所以说 g(x) 生成了 (n,k) 循环码，因此称 g(x) 为码的生成多项式。多项式。次首是一个1)()()(0111knxxxxxknknknggggg(3) 生成多项式和码多项式的关系定理：在 (n,k) 循环码中，生成多项式 g(x) 是独一的 (nk) 次码多项式，且次数是最低的。定理：在 (n,k) 循环码中，每个码多项式

6、C(x) 都是 g(x) 的倍式；而每个为 g(x) 倍式且次数小于或等于 (n1) 的多项式，必是一个码多项式。 10001个k定理6.3.3(定理6.3.2的逆定理)：在一个 (n,k) 线性码中，假设全部码多项式都是最低次的 (nk) 次码多项式的倍式，那么此线性码为一个 (n,k) 循环码。 注：普通说来，这种循环码仍具有把 (n,k) 线性码码中任一非0码矢循环移位必为一码矢的循环特性，但从一个非0码矢出发，进展循环移位，就未必能得到码的一切非0码矢了。所以称这种循环码为推行循环码。码字循环关系图单纯循环码的码字循环图：(7,3)循环码推行循环码的码字循环图：(6,3)循环码(4)

7、如何寻觅一个适宜的生成多项式由下面式子可知：循环码的多项式等于信息多项式乘以生成多项式。 这阐明：对一个循环码只需生成多项式一旦确定，码就确定了，编码问题就处理了。 所以：作一循环码的关键，就在于寻觅一个适当的生成多项式。)()()()()()(),()(0221121021xmxmxmxxxxxxxmmmxkkkkkkkkgggggC定理：定理： (n,k) 循环码的生成多项式循环码的生成多项式 g(x) 是是 (xn+1)的因式，即的因式，即 xn+1=h(x)g(x)。定理：假设定理：假设 g(x) 是一个是一个 (nk) 次次 多项式，且多项式，且为为(xn+1) 的因式，那么的因式，

8、那么 g(x) 生成一个生成一个 (n,k) 循循环码。环码。结论：当求作一个结论：当求作一个(n,k)循环码时，只需分解多循环码时，只需分解多项式项式(xn+1) ，从中取出，从中取出(nk)次因式作生成多次因式作生成多项式即可。项式即可。举例：求 (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(5)

9、循环码的监视多项式和监视矩阵循环码的监视多项式：设 g(x) 为 (n,k) 循环码的生成多项式，必为 (xn+1) 的因式，那么有 xn+1=h(x)g(x)，式中h(x) 为 k 次多项式，称为 (n,k) 循环码的监视多项式。(n,k) 循环码也可由其监视多项式完全确定。举例： (7,3) 循环码 x7+1= (x3+x+1)(x4+x2+x+1)4次多项式为生成多项式g(x)=x4+x2+x+1=g4x4+g3x3+g2x2+g1x+g03次多项式是监视多项式h(x)=x3+x+1=h3x3+h2x2+h1x+h0循环码的监视矩阵由等式 x7+1= h(x)g(x) 两端同次项系数相等

10、得将上面的方程组 写成矩阵方式0000332463223145312213044302112033hghgxhghghgxhghghghgxhghghghgx的系数的系数的系数的系数Tggggghhhhhhhhhhhhhhhh001234321032103210321000000000000000上式中，列阵的元素是生成多项式 g(x) 的系数，是一个码字，那么第一个矩阵那么为(7,3)循环码的监视矩阵，即01230123(7,3)01230123000000H000000hhhhhhhhhhhhhhhh循环码监视矩阵的构成循环码监视矩阵的构成由式由式 (6.3.2) 可见，监视矩阵的第一行是

11、码的监可见，监视矩阵的第一行是码的监视多项式视多项式 h(x) 的系数的反序陈列，第二、三、的系数的反序陈列，第二、三、四行是第一行的移位；四行是第一行的移位；可用监视多项式的系数来构成监视矩阵可用监视多项式的系数来构成监视矩阵*(7,3)2*3*0001101h ( )0011010h ( )H0110100h ( )1101000h ( )h ( )h( )xxxxxxxxx其中表示的反多项式。(n,k) 循环码的监视矩阵对偶问题假设 xn+1=h(x)g(x)，其中 g(x) 为 (nk) 次多项式，以 g(x)为生成多项式，那么生成一个 (n,k) 循环码；以 h(x) 为生成多项式，

12、那么生成 (n,nk) 循环码；这两个循环码互为对偶码。0011101101100)()()(11111111*1*),(kkkkknknhhhhhhhhxxxxxhhhH线性码的译码是根据接纳字多项式的伴随式和可纠的错误图样间的一一对应关系，由伴随式得到错误图样；循环码是线性码的一个特殊子类，循环码的译码与线性码的译码步骤根本一致。不过由于循环码的循环特性，使它的译码更加简单易行；循环码的译码过程仍包括三个步骤：接纳多项式的伴随式计算；求伴随式对应的错误图样；用错误图样纠错。6.3.6 循环码的译码(1) 根据伴随式定义 ST=HRT 计算伴随式S设设的行矢量。表示其中HhhhhH)0 ,

13、2, 1(021knkniiknkn120111112222200000S(,)SHRhRhhhhhRRhhh Rn kn kTTTn kn kn knn kTn kn knn kTn kTSSSSRSRSR ，得到伴随式各分量的表示式这是前面引见过的由接纳矢量相应分量直接求和计算伴随式的方法，对一切线性码都适用。TTknknTknknSSSRhRhRh002211所以0123045156345634601234561000110010001100101110001101SSSSRRRRRRRRRRRRRRRRRRRRTTRHS)12. 2 . 6(rkknkQIG)11. 2 . 6(11nkknGmCkrTrkTkrrkrkrSrkkSPQPQIPHQIG)()(或(4) 接纳字循环移位的伴随式与伴随式循环移位的关系定理6.3