信息论与编码-第8章-第15讲-信道编码-循环码1概要课件.ppt

1、第六章 信道编码2022/10/271第六章 信道编码2022/10/2726.3.1 循环码的多项式描述循环码的多项式描述6.3.2 循环码的生成多项式循环码的生成多项式6.3.3 系统循环码系统循环码6.3.4 多项式运算电路多项式运算电路6.3.5 循环码的编码电路循环码的编码电路6.3.6 循环码的译码循环码的译码6.3.7 循环汉明码循环汉明码6.3.8 缩短循环码缩短循环码6.3 循环码循环码第六章 信道编码2022/10/273(1)循环码的性质循环码的性质循环码是线性分组码的一个重要子类；循环码是线性分组码的一个重要子类；循环码具有循环码具有优良的代数结构优良的代数结构。在结构

2、上在结构上，它的循环性使，它的循环性使得更容易用数学语言来描述；得更容易用数学语言来描述；在性能上在性能上，具有明确的纠、，具有明确的纠、检错能力，对于给定的码长检错能力，对于给定的码长n和信息位数和信息位数k，已提出的各，已提出的各类循环码都有确定的纠、检错能力的理论计算值；类循环码都有确定的纠、检错能力的理论计算值；在实在实现上现上，编码和译码都可以通过简单的反馈移位寄存器来，编码和译码都可以通过简单的反馈移位寄存器来完成完成,并可使用多种简单而有效的译码方法。并可使用多种简单而有效的译码方法。循环码是研究最循环码是研究最深入深入、理论最、理论最成熟成熟、应用最、应用最广泛广泛的一类的一类

3、线性分组码。线性分组码。6.3.1 循环码的多项式描述循环码的多项式描述6.3循循环环码码第六章 信道编码2022/10/274(2)循环码的定义循环码的定义循环码循环码：如果：如果(n,k)线性分组码的任意码矢线性分组码的任意码矢C C=(C Cn1,C Cn2,C C0)的的 i 次循环移位，所得矢量次循环移位，所得矢量C C(i)=(C Cn1i,C Cn2i,C C0,C Cn1,C Cni)仍是一个码矢，则称此线性码为仍是一个码矢，则称此线性码为(n,k)循环码。循环码。6.3.1 循环码的多项式描述循环码的多项式描述6.3循循环环码码第六章 信道编码2022/10/2756.3.1

4、 循环码的多项式描述循环码的多项式描述6.3循循环环码码第六章 信道编码2022/10/276(3)码多项式码多项式码多项式码多项式：为了运算的方便，将码矢的各分量作为多：为了运算的方便，将码矢的各分量作为多项式的系数，把码矢表示成多项式，称为码多项式。项式的系数，把码矢表示成多项式，称为码多项式。其一般表示式为其一般表示式为C C(x)=Cn1xn1+Cn2xn2+C0码多项式码多项式 i 次循环移位的表示方法次循环移位的表示方法 记码多项式记码多项式C C(x)的一次左移循环为的一次左移循环为 C C(1)(x)，i 次左移循次左移循环为环为 C C(i)(x)6.3.1 循环码的多项式描

5、述循环码的多项式描述6.3循循环环码码ininiinininininnnnnnnnnnCxCxCxCxCxxCxCxCxCxCxCxCx1102211)(1103322)1(02211)()()(CCC第六章 信道编码2022/10/277码多项式的模码多项式的模(xn+1)运算运算0和和1两个元素模两个元素模2运算下构成域。运算下构成域。6.3.1 循环码的多项式描述循环码的多项式描述6.3循循环环码码第六章 信道编码2022/10/278若若 p 为素数，则整数全体在模为素数，则整数全体在模 p 运算下的剩余类全运算下的剩余类全体体 在模在模 p 下构成域。下构成域。以以 p=3 为模的剩

6、余类全体为模的剩余类全体 模模3运算的规则如下：运算的规则如下：1,3,2,1,0p6.3.1 循环码的多项式描述循环码的多项式描述6.3循循环环码码120221010000210102202112100210构成域。2,1,0第六章 信道编码2022/10/279码矢码矢 C C 循环循环 i 次所得码矢的码多项式次所得码矢的码多项式 C C(x)乘以乘以 x，再除以，再除以(xn+1)，得，得6.3.1 循环码的多项式描述循环码的多项式描述6.3循循环环码码ininiinininininnnnCxCxCxCxCxCxCxCx1102211)(02211)()(CC1)(11)()1(110

7、2123121nnnnnnnnnnxxCxCxCxCxCxCCxxxCC第六章 信道编码2022/10/2710上式表明上式表明：码矢循环一次的码多项式：码矢循环一次的码多项式 C C(1)(x)是原码是原码多项式多项式 C C(x)乘以乘以 x 除以除以(xn+1)的余式。写作的余式。写作因此，因此，C C(x)的的 i 次循环移位次循环移位 C C(i)(x)是是 C C(x)乘以乘以 xi 除除以以(xn+1)的余式，即的余式，即结论结论：循环码的码矢的：循环码的码矢的 i 次循环移位等效于将码多次循环移位等效于将码多项式乘项式乘 xi 后再模后再模(xn+1)。)1()()()1(nx

8、xxx模CC6.3.1 循环码的多项式描述循环码的多项式描述6.3循循环环码码)1()()()(niixxxx模CC第六章 信道编码2022/10/2711(4)举例：举例：(7,3)循环码，循环码，可由任一个码矢，比如可由任一个码矢，比如(0011101)经过循环移位，经过循环移位，得到其它得到其它6个非个非0 0码矢；码矢；也可由相应的码多项式也可由相应的码多项式(x4+x3+x2+1)，乘以，乘以xi(i=1,2,6)，再模，再模(x7+1)运算得到其它运算得到其它6个非个非0 0码多码多项式。移位过程和相应的多项式运算如表项式。移位过程和相应的多项式运算如表6.3.1所示。所示。6.3

9、.1 循环码的多项式描述循环码的多项式描述6.3循循环环码码第六章 信道编码2022/10/27126.3.1 循环码的多项式描述循环码的多项式描述6.3循循环环码码第六章 信道编码2022/10/2713(1)循环码的生成矩阵循环码的生成矩阵根据循环码的循环特性，可由一个码字的循环移位得根据循环码的循环特性，可由一个码字的循环移位得到其它的非到其它的非0 0码字。在码字。在(n,k)循环码的循环码的 2k 个码字中，取个码字中，取前前(k1)位皆为位皆为0的码字的码字 g g(x)（其次数（其次数r=nk），再），再经经(k1)次循环移位，共得到次循环移位，共得到 k 个码字：个码字：g g

10、(x),xg g(x),xk1 g g(x)6.3.2 循环码的生成多项式循环码的生成多项式6.3循循环环码码)()()()()(21xxxxxxxxkkggggG 这这 k 个码字显然是相互个码字显然是相互独立的，可作为码生成矩独立的，可作为码生成矩阵的阵的 k 行，于是得到行，于是得到循环循环码的生成矩阵码的生成矩阵 GG(x)第六章 信道编码2022/10/2714(2)循环码的生成多项式循环码的生成多项式码的生成矩阵一旦确定，码就确定了；码的生成矩阵一旦确定，码就确定了；这就说明：这就说明：(n,k)循环码可由它的一个循环码可由它的一个(nk)次码多次码多项式项式 g g(x)来确定；

11、来确定；所以说所以说 g g(x)生成了生成了(n,k)循环码，因此循环码，因此称称 g g(x)为码的为码的生成多项式生成多项式。6.3.2 循环码的生成多项式循环码的生成多项式6.3循循环环码码多项式。次首是一个1)()()(0111knxxxxxknknknggggg第六章 信道编码2022/10/2715(3)生成多项式生成多项式和和码多项式码多项式的关系的关系定理定理6.3.16.3.1：在在(n,k)循环码中，生成多项式循环码中，生成多项式 g g(x)是惟是惟一的一的(nk)次码多项式，且次数是最低的次码多项式，且次数是最低的。证明证明：先证在先证在(n,k)循环码系统中存在循环

12、码系统中存在(nk)次码多项式。次码多项式。因为在因为在 2k 个信息组中，有一个信息组为个信息组中，有一个信息组为 ，它的对，它的对应码多项式的次数为应码多项式的次数为n1(k1)=nk(nk)次码多项式是最低次码多项式。次码多项式是最低次码多项式。l若若 g g(x)不是最低次码多项式，那么设更低次的码多项式不是最低次码多项式，那么设更低次的码多项式为为g g(x)，其次数为，其次数为(nk1)。g g(x)的前面的前面 k 位为位为0，即，即 k个信息位全为个信息位全为0，而监督位不为，而监督位不为0，这对线性码来说是不，这对线性码来说是不可能的，因此可能的，因此 g g(x)是最低次的

13、码多项式，即是最低次的码多项式，即 gnk 必为必为1。6.3.2 循环码的生成多项式循环码的生成多项式6.3循循环环码码10001个k第六章 信道编码2022/10/2716lg0=1，否则经，否则经(n1)次左移循环后将得到低于次左移循环后将得到低于(nk)次次的码多项式。的码多项式。g g(x)是惟一的是惟一的(nk)次多项式。次多项式。如果存在另一个如果存在另一个(nk)次码多项式，设为次码多项式，设为 g g(x)，根据线性，根据线性码的封闭性，则码的封闭性，则 g g(x)+g g(x)也必为一个码多项式。由于也必为一个码多项式。由于 g g(x)和和 g g(x)的次数相同，它们

14、的和式的的次数相同，它们的和式的(nk)次项系数为次项系数为0，那么那么 g g(x)+g g(x)是一个次数低于是一个次数低于(nk)次的码多项式，前次的码多项式，前面已证明面已证明 g g(x)的次数是最低的，因此的次数是最低的，因此 g g(x)不能存在，所以不能存在，所以 g g(x)是惟一的是惟一的(nk)次码多项式。次码多项式。6.3.2 循环码的生成多项式循环码的生成多项式6.3循循环环码码第六章 信道编码2022/10/2717令令 是是(n,k)循环码循环码C中中最低次数的非零码多项式，则常数项最低次数的非零码多项式，则常数项g0必为必为1。设设g0=0 则则n将将g(x)循

15、环右移循环右移1位或循环左移位或循环左移n 1位，记为位，记为 有有n它是一个次数小于它是一个次数小于r的非零码多项式，与的非零码多项式，与g(x)是最低次数的非零是最低次数的非零码多项式的假设相矛盾，故码多项式的假设相矛盾，故g0必为必为1。因此。因此 n证毕。证毕。（实质上是论证了生成多项式必有常数项）（实质上是论证了生成多项式必有常数项）11101211()()rrrrrrg xxgxg xgx xgxg6.3.2 循环码的生成多项式循环码的生成多项式6.3循循环环码码(1)1211()rrrgxxgxg111()1rrrg xxgxg x1110()rrrg xxgxg xg(1)()

16、gx第六章 信道编码2022/10/2718定理定理6.3.26.3.2：在：在(n,k)循环码中，每个码多项式循环码中，每个码多项式 C C(x)都都是是 g g(x)的倍式；而每个为的倍式；而每个为 g g(x)倍式且次数小于或等倍式且次数小于或等于于(n1)的多项式，必是一个码多项式的多项式，必是一个码多项式。证明证明：设设 mm=(mk1,mk2,m0)为任一信息组，为任一信息组，GG(x)为该为该(n,k)循环循环码码的生成矩阵，则相应的码多项式为的生成矩阵，则相应的码多项式为6.3.2 循环码的生成多项式循环码的生成多项式6.3循循环环码码)()()()()()(),()()()(

17、0221121021xmxmxmxxxxxxxmmmxxxkkkkkkkkgggggCGmC第六章 信道编码2022/10/2719上式表明：循环码的任一码多项式为上式表明：循环码的任一码多项式为 g g(x)的倍式。的倍式。显然，凡是为显然，凡是为 g g(x)的倍式且次数小于或等于的倍式且次数小于或等于(n1)的多项式，的多项式，一定能分解成上式的形式，因而它就是信息多项式一定能分解成上式的形式，因而它就是信息多项式 mm(x)=(mk1xk1+mk2 xk2+m0)并由生成矩阵并由生成矩阵 GG(x)所生成所生成的码多项式。的码多项式。定理定理6.3.36.3.3(定理定理6.3.2的逆

18、定理的逆定理)：在一个在一个(n,k)线性码中，线性码中，如果全部码多项式都是最低次的如果全部码多项式都是最低次的(nk)次码多项式的倍次码多项式的倍式，则此线性码为一个式，则此线性码为一个(n,k)循环码循环码。注注：一般说来，这种循环码仍具有把：一般说来，这种循环码仍具有把(n,k)线性码码中任一非线性码码中任一非0 0码矢循环移位必为一码矢的循环特性，但从一个非码矢循环移位必为一码矢的循环特性，但从一个非0 0码矢出发，进码矢出发，进行循环移位，就未必能得到码的所有非行循环移位，就未必能得到码的所有非0 0码矢了。所以称这种循环码矢了。所以称这种循环码为码为推广循环码推广循环码。6.3.

19、2 循环码的生成多项式循环码的生成多项式6.3循循环环码码第六章 信道编码2022/10/2720码字循环关系图码字循环关系图单纯循环码的单纯循环码的码字循环图：码字循环图：(7,3)循环码循环码6.3.2 循环码的生成多项式循环码的生成多项式6.3循循环环码码第六章 信道编码2022/10/2721推广循环码的推广循环码的码字循环图：码字循环图：(6,3)循环码循环码6.3.2 循环码的生成多项式循环码的生成多项式6.3循循环环码码第六章 信道编码2022/10/2722(4)如何寻找一个合适的生成多项式如何寻找一个合适的生成多项式由下面式子可知：循环码的多项式等于信息多项式乘由下面式子可知

20、：循环码的多项式等于信息多项式乘以生成多项式。以生成多项式。这说明这说明：对一个循环码只要生成多项式一旦确定，码就确定了，：对一个循环码只要生成多项式一旦确定，码就确定了，编码问题就解决了。编码问题就解决了。所以所以：作一循环码的关键，就在于寻找一个适当的生成多项式作一循环码的关键，就在于寻找一个适当的生成多项式。6.3.2 循环码的生成多项式循环码的生成多项式6.3循循环环码码)()()()()()(),()(0221121021xmxmxmxxxxxxxmmmxkkkkkkkkgggggC第六章 信道编码2022/10/2723定理定理6.3.46.3.4：(n,k)循环码的生成多项式循环

21、码的生成多项式 g g(x)是是(xn+1)的因式，即的因式，即 xn+1=h h(x)g g(x)。证明证明：由于由于 xk g g(x)是是 n 次多项式，可表示为次多项式，可表示为xk g g(x)=1(xn+1)+g g(k)(x)(6.3.1)式中式中 g g(k)(x)是码多项式是码多项式 g g(x)乘以乘以 xk 除以除以(xn+1)的余式。的余式。根据循环码的移位关系，它是根据循环码的移位关系，它是 g g(x)循环移位循环移位 k 次所得到的码次所得到的码多项式，因而多项式，因而 g g(k)(x)是是 g g(x)的倍式。的倍式。设设 g g(k)(x)=mm(x)g g

22、(x)代入式代入式(6.3.1)得得(xn+1)=xk+mm(x)g g(x)上式表明：上式表明：g g(x)是是(xn+1)的因式。的因式。6.3.2 循环码的生成多项式循环码的生成多项式6.3循循环环码码第六章 信道编码2022/10/2724定理定理6.3.56.3.5：若：若 g g(x)是一个是一个(nk)次次 多项式，且为多项式，且为(xn+1)的因式，则的因式，则 g g(x)生成一个生成一个(n,k)循环码。循环码。证明证明：由于由于 g g(x)是一个是一个(nk)次多项式，且为次多项式，且为(xn+1)的因式，所的因式，所以以 g g(x),x g g(x),xk1 g g

23、(x)是是 k 个次数小于个次数小于 n，并且彼此，并且彼此独立的多项式；独立的多项式；6.3.2 循环码的生成多项式循环码的生成多项式6.3循循环环码码)()()()()(21xxxxxxxxkkggggG 将此多项式用作码的生成将此多项式用作码的生成矩阵的矩阵的 k 行，得到行，得到(n,k)线线性码的生成矩阵；性码的生成矩阵；第六章 信道编码2022/10/2725设信息组设信息组 mm=(mk1,mk2,m0)，则相应的码字为，则相应的码字为 C C(x)=mm GG(x)=(mk1xk1+mk2 1xk2+m0)g g(x)=mm(x)g g(x)lC C(x)n1；lmm(x)是是

24、 2k 个信息多项式的表示式；个信息多项式的表示式；l所以所以 C C(x)即为相应即为相应 2k 个码多项式的表示式。个码多项式的表示式。因此，因此，g g(x)生成一个生成一个(n,k)线性码。线性码。C C(x)是是(nk)次多项式次多项式 g g(x)的倍式，所以的倍式，所以 g g(x)生成一个生成一个(n,k)循环码。循环码。结论结论：当求作一个当求作一个(n,k)循环码时，只要分解多项式循环码时，只要分解多项式(xn+1)，从中取出，从中取出(nk)次因式作生成多项式即可次因式作生成多项式即可。6.3.2 循环码的生成多项式循环码的生成多项式6.3循循环环码码第六章 信道编码20

25、22/10/2726举例：求举例：求(7,3)循环码的生成多项式。循环码的生成多项式。解解：分解多项式分解多项式 xn+1，取其，取其4次因式作生成多项式次因式作生成多项式x7+1=(x+1)(x3+x2+1)(x3+x+1)可将一次和任一个三次因式的乘积作为生成多项式，可将一次和任一个三次因式的乘积作为生成多项式，因而可取因而可取 g g1(x)=(x+1)(x3+x2+1)=x4+x2+x+1 或或 g g2(x)=(x+1)(x3+x+1)=x4+x3+x2+16.3.2 循环码的生成多项式循环码的生成多项式6.3循循环环码码第六章 信道编码2022/10/27276.3.2 循环码的生

26、成多项式循环码的生成多项式6.3循循环环码码第六章 信道编码2022/10/2728 试构造试构造n=10和和n=15时可能的二进制循环码。时可能的二进制循环码。对各种可能的对各种可能的k值求出其对应的生成多项式。值求出其对应的生成多项式。对于对于n=10的情况，求的情况，求k=1,2,8,9时对应的生成多时对应的生成多项式，就是求项式，就是求x10+1的各的各(10 k)次因式；次因式；对于对于n=15的情况，求的情况，求k=1,2,13,14时对应的生成时对应的生成多项式，就是求多项式，就是求x15+1的各的各(15 k)次因式。次因式。两种情况的计算结果如下表所示，表中给出了两种情况的计

27、算结果如下表所示，表中给出了g(x)以及对应的汉明距离，其中以及对应的汉明距离，其中g(x)用其系数表示，例用其系数表示，例如如110101代表代表x5+x4+x2+1。6.3.2 循环码的生成多项式循环码的生成多项式6.3循循环环码码第六章 信道编码2022/10/27296.3.2 循环码的生成多项式循环码的生成多项式6.3循循环环码码第六章 信道编码2022/10/2730由上表可见，由上表可见，x10+1不含有不含有(10,3)、(10,7)循环码，因循环码，因为它没有为它没有7次和次和3次因式；而对于次因式；而对于k=5,6,8,9，其距离，其距离都是都是2，故它们的纠、检错能力是一

28、样的，但编码效率，故它们的纠、检错能力是一样的，但编码效率显然大不一样，说明同是循环码，性能却有所不同，显然大不一样，说明同是循环码，性能却有所不同，这就提出了所谓搜索好码的问题。这就提出了所谓搜索好码的问题。n=15情况，情况，x15+1有有1,14区间的各次因式，但有超区间的各次因式，但有超过一半的过一半的k值有值有2个同次因式，对应的情况就可以构造个同次因式，对应的情况就可以构造出出2个循环码，但注意到对应的个循环码，但注意到对应的dmin值就会发现，有的值就会发现，有的情况却不相等，这说明注入同样的冗余度得到的效果情况却不相等，这说明注入同样的冗余度得到的效果却不一样，同样说明寻找性能

29、好的循环码的重要性。却不一样，同样说明寻找性能好的循环码的重要性。6.3.2 循环码的生成多项式循环码的生成多项式6.3循循环环码码第六章 信道编码2022/10/27316.3.2 循环码的生成多项式循环码的生成多项式6.3循循环环码码第六章 信道编码2022/10/2732(5)循环码的监督多项式和监督矩阵循环码的监督多项式和监督矩阵循环码的监督多项式循环码的监督多项式：设：设 g g(x)为为(n,k)循环码的生成循环码的生成多项式，必为多项式，必为(xn+1)的因式，则有的因式，则有 xn+1=h h(x)g g(x)，式中式中h h(x)为为 k 次多项式，称为次多项式，称为(n,k

30、)循环码的监督多项循环码的监督多项式。式。(n,k)循环码也可由其监督多项式完全确定。循环码也可由其监督多项式完全确定。举例举例：(7,3)循环码循环码 x7+1=(x3+x+1)(x4+x2+x+1)l4次多项式为生成多项式次多项式为生成多项式g g(x)=x4+x2+x+1=g4x4+g3x3+g2x2+g1x+g0l3次多项式是监督多项式次多项式是监督多项式h h(x)=x3+x+1=h3x3+h2x2+h1x+h06.3.2 循环码的生成多项式循环码的生成多项式6.3循循环环码码第六章 信道编码2022/10/2733循环码的监督矩阵循环码的监督矩阵由等式由等式 x7+1=h h(x)

31、g g(x)两端同次项系数相等得两端同次项系数相等得将上面的方程组将上面的方程组 写成矩阵形式写成矩阵形式0000332463223145312213044302112033hghgxhghghgxhghghghgxhghghghgx的系数的系数的系数的系数6.3.2 循环码的生成多项式循环码的生成多项式6.3循循环环码码Tggggghhhhhhhhhhhhhhhh001234321032103210321000000000000000第六章 信道编码2022/10/2734上式中，列阵的元素是生成多项式上式中，列阵的元素是生成多项式 g g(x)的系数，是一个码字，的系数，是一个码字，那么第

32、一个矩阵则为那么第一个矩阵则为(7,3)循环码的循环码的监督矩阵监督矩阵，即，即6.3.2 循环码的生成多项式循环码的生成多项式6.3循循环环码码)2.3.6(0000000000003210321032103210)3,7(hhhhhhhhhhhhhhhhH第六章 信道编码2022/10/2735循环码监督矩阵的构成循环码监督矩阵的构成由式由式(6.3.2)可见，监督矩阵的第一行是码的监督多项式可见，监督矩阵的第一行是码的监督多项式 h h(x)的系数的的系数的反序排列反序排列，第二、三、四行是第一行的移位；，第二、三、四行是第一行的移位；可用监督多项式的系数来构成监督矩阵可用监督多项式的系

33、数来构成监督矩阵6.3.2 循环码的生成多项式循环码的生成多项式6.3循循环环码码的反多项式。表示其中)()()3.3.6(0001011001011001011001011000)()()()(*3*2*)3,7(xxxxxxxxxhhhhhhH第六章 信道编码2022/10/2736(n,k)循环码的监督矩阵循环码的监督矩阵对偶问题对偶问题如果如果 xn+1=h h(x)g g(x)，其中，其中 g g(x)为为(nk)次多项式，以次多项式，以 g g(x)为生成多项式，则生成一个为生成多项式，则生成一个(n,k)循环码；循环码；以以 h h(x)为生成多项式，则生成为生成多项式，则生成(

34、n,nk)循环码；循环码；这两个循环码互为对偶码。这两个循环码互为对偶码。*11*11(,)111*110011h()0110h()H11100h()kkn kkn kkhhxhhxxhhhhxx 6.3.2 循环码的生成多项式循环码的生成多项式6.3循循环环码码第六章 信道编码2022/10/2737(1)系统循环码构成系统循环码构成设信息向量设信息向量 mm=(mk1,mk2,m0)信息多项式信息多项式 mm(x)=mk1xk1+mk2 xk2+m0 码多项式码多项式的高次幂部分等于的高次幂部分等于mm(x)，即，即 C C(x)=cn1xn1+cnkxnk+cnk1xnk1+c1x+c0

35、 =xnk mm(x)+q q(x)q q(x)的次数的次数nk校验位多项式校验位多项式 q q(x)由于码多项式是生成多项式的倍式，所以由于码多项式是生成多项式的倍式，所以C C(x)=xnkmm(x)+q q(x)=a a(x)g g(x)0 0(mod g g(x)q q(x)=C C(x)+xnkmm(x)xnkmm(x)(mod g g(x)因此，因此，循环码的系统码形式为循环码的系统码形式为C C(x)=xnkmm(x)+(xnkmm(x)mod g g(x)6.3.3 系统循环码系统循环码6.3循循环环码码第六章 信道编码2022/10/2738系统循环码构造过程步骤系统循环码构

36、造过程步骤信息多项式乘信息多项式乘 xnk：xnkmm(x)对对 xnkmm(x)求余式：求余式：q q(x)xnkmm(x)(mod g g(x)求码多项式：求码多项式：C C(x)=xnkmm(x)+(xnkmm(x)mod g g(x)=xnkmm(x)+q q(x)对所有的对所有的 i=0,1,2,k1，用生成多项式用生成多项式g(x)除除xnk+i（即令即令mm(x)为单项式）为单项式）xnk+i=a a(x)g g(x)+q qi(x)，q qi(x)的次数的次数nk因此因此xn-k+i+q qi(x)是是g(x)的倍式，即码多项式的倍式，即码多项式C Ci(x)=xnk+i+q

37、qi(x)可见：可见：C Ci(x)对应的向量对应的向量C Ci，i=0,1,2,k1是线性无关的，从是线性无关的，从而得到循环码系统码的生成矩阵而得到循环码系统码的生成矩阵 GGs 为为6.3.3 系统循环码系统循环码6.3循循环环码码第六章 信道编码2022/10/27396.3.3 系统循环码系统循环码6.3循循环环码码1,01,00,01,21,20,21,11,10,1021100010001100010001knknkkkknkkkkksqqqqqqqqqqqqG第六章 信道编码2022/10/2740(2)举例举例例例6.3.5：(7,4)循环码循环码 g g(x)=x3+x+1

38、，x6=(x3+x2+1)g g(x)+(x2+1)q q3(x)=(x2+1)C C3(x)=x6+x2+1 x5=(x2+1)g g(x)+(x2+x+1)q q2(x)=(x2+x+1)C C2(x)=x5+x2+x+1 x4=xg g(x)+(x2+x)q q1(x)=(x2+x)C C1(x)=x4+x2+xx3=g g(x)+(x+1)q q0(x)=(x+1)C C0(x)=x3+x+1 6.3.3 系统循环码系统循环码6.3循循环环码码)()()()1()()1(1101000011010011100101010001223xxxxxxxxsggggG第六章 信道编码2022/

39、10/2741(1)多项式加法电路多项式加法电路多项式多项式 a a(x)=anxn+an1xn1+a1x+a0 表示的是时间表示的是时间序列序列 a a=(an,an1,a1,a0)，因此多项式的计算表现为，因此多项式的计算表现为对时间序列的操作；对时间序列的操作；6.3.4 多项式运算电路多项式运算电路6.3循循环环码码 对二进制多项式系数的基对二进制多项式系数的基 本操作为本操作为模模2加加和和模模2乘乘；电路图运算符号的意义：电路图运算符号的意义：第六章 信道编码2022/10/2742a a(x)与与 b b(x)的相加电路。如图的相加电路。如图6.3.3。6.3.4 多项式运算电路

40、多项式运算电路6.3循循环环码码第六章 信道编码2022/10/2743(2)多项式乘法电路多项式乘法电路多项式乘以多项式乘以 x 等价为时间序列等价为时间序列 a a 延迟一位；延迟一位；多项式与多项式的乘等价为的不同位移后的相加：多项式与多项式的乘等价为的不同位移后的相加：a a(x)g g(x)=a a(x)(g g1(x)+g g2(x)=a a(x)g g1(x)+a a(x)g g2(x)多项式乘法电路如图多项式乘法电路如图6.3.4。假设多项式的低位在前，电路中所有。假设多项式的低位在前，电路中所有寄存器初态为寄存器初态为0。6.3.4 多项式运算电路多项式运算电路6.3循循环环

41、码码第六章 信道编码2022/10/2744图图6.3.5表示了多项式表示了多项式乘法电路。乘法电路。6.3.4 多项式运算电路多项式运算电路6.3循循环环码码第六章 信道编码2022/10/2745(3)多项式除法电路多项式除法电路当当 g g(x)=1,多项式多项式 a a(x)模模 g g(x)的余式为的余式为0,电路如图电路如图6.3.7所示。所示。6.3.4 多项式运算电路多项式运算电路6.3循循环环码码第六章 信道编码2022/10/2746当当 g g(x)是单项式是单项式 g g(x)=xk，a a(x)模模 g g(x)的余式的次数的余式的次数小于小于 k，进入电路的输入顺序

42、为，进入电路的输入顺序为 an,an1,a1,a0。a a(x)ak1xk1+ak2xk2+a1x+a0 (mod xk)运算电路如图运算电路如图6.3.8所示。所示。6.3.4 多项式运算电路多项式运算电路6.3循循环环码码第六章 信道编码2022/10/2747由于由于 xk1 mod(x+1),i=0,1,2,。若。若 a a(x)的次数为的次数为 n，则则 a a(x)mod(x+1)an1+an2+a1+a0=q0(mod 2)运算电路如图运算电路如图6.3.9所示。所示。6.3.4 多项式运算电路多项式运算电路6.3循循环环码码第六章 信道编码2022/10/2748同样由长除法得

43、同样由长除法得 运算电路如图运算电路如图6.3.10所示。所示。6.3.4 多项式运算电路多项式运算电路6.3循循环环码码niiiniiiniiiniiiaqaqxqqaax5,3,114,2,002105,3,14,2,0)1(mod()(其中a第六章 信道编码2022/10/2749类似地：多项式类似地：多项式a a(x)模模(x2+x+1)的运算电路如图的运算电路如图6.3.11所示。所示。6.3.4 多项式运算电路多项式运算电路6.3循循环环码码第六章 信道编码2022/10/2750一般的多项式模一般的多项式模 g g(x)=grxr+gr1xr1+g1x+g0 的运算电路如图的运算

44、电路如图6.3.12所示。所示。移位寄存器初态全为移位寄存器初态全为0；当当 a a(x)输入完后，移位寄存器内容输入完后，移位寄存器内容(qr1,q1,q0)就是余式就是余式q q(x)=pr1xr1+pr2xr2+p1x+p0 a a(x)(mod g g(x)6.3.4 多项式运算电路多项式运算电路6.3循循环环码码第六章 信道编码2022/10/2751多项式除法电路的构造多项式除法电路的构造多项式除法电路是一个由除式多项式除法电路是一个由除式(这里就是生成多项式这里就是生成多项式g g(x)g g(x)=gnkxnk+gnk1xnk1+g1x+g0 所确定的所确定的反馈移位反馈移位寄

45、存器寄存器。除法电路的构造方法除法电路的构造方法移位寄存器的级数等于除式的次数移位寄存器的级数等于除式的次数 nk；移位寄存器的反馈抽头，由除式的各项系数移位寄存器的反馈抽头，由除式的各项系数 gi(i=0,1,nk)决定：决定：p当某个抽头当某个抽头=0时，对应的反馈断开；时，对应的反馈断开；p当某个抽头当某个抽头=1时，对应的反馈接通。时，对应的反馈接通。完成除法所需的移位次数等于被除式的次数加完成除法所需的移位次数等于被除式的次数加1。6.3循循环环码码6.3.4 多项式运算电路多项式运算电路第六章 信道编码2022/10/2752多项式除法电路举例多项式除法电路举例利用除法电路完成两个

46、多项式除法运算，求其余式的过程利用除法电路完成两个多项式除法运算，求其余式的过程和将两个多项式进行长除运算是完全一致的；和将两个多项式进行长除运算是完全一致的；例如例如 (x5+x2)(x4+x3+x+1)的长除运算过程如下：的长除运算过程如下：6.3循循环环码码)(11)()()()(1133442452534第二余式第一余式除式被除式商式xxxxxxxxxxxxxxxx6.3.4 多项式运算电路多项式运算电路第六章 信道编码2022/10/2753每做一次除法运算，被除式每做一次除法运算，被除式(或前次除法的余式或前次除法的余式)的首的首项被抵消，因而除法电路中每做一次除法运算，最高项被抵

47、消，因而除法电路中每做一次除法运算，最高项就移到寄存器之外而丢掉；项就移到寄存器之外而丢掉；除式除首项外的其它各项系数都要加到被除式或前次除式除首项外的其它各项系数都要加到被除式或前次运算的余式中去，而除法电路的反馈正是按除式的规运算的余式中去，而除法电路的反馈正是按除式的规律连接的，恰好完成所需的加法运算。律连接的，恰好完成所需的加法运算。6.3循循环环码码6.3.4 多项式运算电路多项式运算电路第六章 信道编码2022/10/2754例如例如 (x5+x2)(x4+x3+x+1)的除法电路运算过程如下：的除法电路运算过程如下：在各级预先清零的条件下，被除式系数由移位寄存器在各级预先清零的条

48、件下，被除式系数由移位寄存器第一级输入，经第一级输入，经4次移位后，最高项的系数到达移位次移位后，最高项的系数到达移位寄存器右端出现反馈信号；寄存器右端出现反馈信号；第一次对被除式作除法，下一个移位脉冲加入时，被第一次对被除式作除法，下一个移位脉冲加入时，被除式首项除式首项 x5 移出寄存器，相当于首项被抵消，而反移出寄存器，相当于首项被抵消，而反馈信号按除式规律与被除式相应项进行模馈信号按除式规律与被除式相应项进行模2加，移位加，移位寄存器新的内容即为第一余式；寄存器新的内容即为第一余式；6.3循循环环码码6.3.4 多项式运算电路多项式运算电路第六章 信道编码2022/10/2755 第一

49、余式的首项第一余式的首项 x4 的系数到达电路的末级，出现反馈的系数到达电路的末级，出现反馈信号，准备作第二次除法，当下一个移位脉冲加入时，信号，准备作第二次除法，当下一个移位脉冲加入时，第一余式的首项移出寄存器被丢掉，反馈信号又把除式第一余式的首项移出寄存器被丢掉，反馈信号又把除式(除首项外除首项外)加到第一余式，得到第二余式，即所求余式；加到第一余式，得到第二余式，即所求余式；为了使被除式全部移入寄存器，除法求余所需要的移位为了使被除式全部移入寄存器，除法求余所需要的移位次数等于被除式次数加次数等于被除式次数加1。6.3循循环环码码6.3.4 多项式运算电路多项式运算电路第六章 信道编码2022/10/2756表表6.3.3列出了电路的运算过程。列出了电路的运算过程。6.3循循环环码码6.3.4 多项式运算电路多项式运算电路第六章 信道编码2022/10/2757