信息论与编码原理_第9章_循环码

1、第1页2021-12-13Department of Electronics and Information, NCUT Song Peng第2页2021-12-13Department of Electronics and Information, NCUT Song Peng9.1 循环码的多项式描述循环码的多项式描述9.2 循环码的循环码的生成多项式生成多项式9.3 系统循环码系统循环码9.4 多项式运算电路多项式运算电路9.5 循环码的循环码的编码电路编码电路9.6 循环码的循环码的译码译码9.7 循环汉明码循环汉明码9.8 缩短循环码缩短循环码9.9 循环码的其它译码方法循环码的其它

2、译码方法9.10 BCH 码和码和 RS 码码第3页2021-12-13Department of Electronics and Information, NCUT Song Peng(1) 循环码的性质循环码的性质(2) 循环码的定义循环码的定义(3) 码多项式码多项式(4) 举例举例第4页2021-12-13Department of Electronics and Information, NCUT Song Peng(1) 循环码的性质循环码的性质 循环码是线性分组码的一个重要子类；循环码是线性分组码的一个重要子类； 由于循环码具有由于循环码具有优良的代数结构优良的代数结构，可用简单

3、的反馈移，可用简单的反馈移位寄存器实现编码和伴随式计算，并可使用多种简单而位寄存器实现编码和伴随式计算，并可使用多种简单而有效的译码方法；有效的译码方法； 循环码是研究最循环码是研究最深入深入、理论最、理论最成熟成熟、应用最、应用最广泛广泛的一的一类线性分组码。类线性分组码。第5页2021-12-13Department of Electronics and Information, NCUT Song Peng(2) 循环码的定义循环码的定义 循环码：循环码：如果如果 (n,k) 线性分组码的任意码字：线性分组码的任意码字：C C=(cn1,cn2,c0) 的的 i 次循环移位，所得矢量：次

4、循环移位，所得矢量：C C(i)=(cn1i,cn2i,c0,cn1,cni) 仍是一个码字，则称此线性码为仍是一个码字，则称此线性码为 (n,k) 循环码。循环码。第6页2021-12-13Department of Electronics and Information, NCUT Song Peng(3) 码多项式码多项式 码多项式：码多项式：为了运算的方便，将码字的各分量作为多项式的系数，为了运算的方便，将码字的各分量作为多项式的系数，把码字表示成多项式，称为码多项式。其一般表示式为：把码字表示成多项式，称为码多项式。其一般表示式为：C(x)=cn1xn1+cn2xn2+c0 码多项式

5、码多项式 i 次循环移位的表示方法次循环移位的表示方法 记码多项式记码多项式 C(x) 的一次左移循环为的一次左移循环为 C(1)(x) ，i 次左移循环为次左移循环为 C(i)(x) ininiininnininnnnnnnnncxcxcxcxcxcxCcxcxcxcxcxCccxcxcxC110112211)(10212312(1)012211)()()(第7页2021-12-13Department of Electronics and Information, NCUT Song Peng(3) 码多项式码多项式 码多项式的模码多项式的模 (xn+1) 运算运算q 0 和和 1 两个元

6、素模两个元素模 2 运算下构成域。运算下构成域。q 若若 p 为素数，则整数全体在模为素数，则整数全体在模 p 运算下的剩余类全体运算下的剩余类全体 在模在模 p 下构成域。下构成域。 1,3,2,1,0 p1010001001110010 第8页2021-12-13Department of Electronics and Information, NCUT Song Peng(3) 码多项式码多项式 码多项式的模码多项式的模 (xn+1) 运算运算q 以以 p=3 为模的剩余类全体为模的剩余类全体q 模模 3 运算的规则如下：运算的规则如下：120221010000210102202112

7、100210 第9页2021-12-13Department of Electronics and Information, NCUT Song Peng(3) 码多项式码多项式 码多项式的模码多项式的模 (xn+1) 运算运算q 码字码字 C C 循环循环 i 次所得码字的码多项式：次所得码字的码多项式：q C(x) 乘以乘以 x，再除以，再除以 (xn+1)，得：，得：ininininnininnnncxcxcxcxcxCcxcxcxC 1102211)(02211)()(1)(11)()1(1102123121 nnnnnnnnnnxxCcxcxcxcxcxccxxxC第10页2021-

8、12-13Department of Electronics and Information, NCUT Song Peng(3) 码多项式码多项式 码多项式的模码多项式的模 (xn+1) 运算运算q 上式表明：上式表明：码字循环一次的码多项式码字循环一次的码多项式 C(1)(x) 是原码多项式是原码多项式 C(x)乘以乘以 x 除以除以 (xn+1) 的余式。写作：的余式。写作：q C(x) 的的 i 次循环移位次循环移位 C(i)(x) 是是 C(x) 乘以乘以 xi 除以除以 (xn+1) 的余式，的余式，即：即：q 结论：结论：循环码的码字的循环码的码字的 i 次循环移位等效于将码多项

9、次循环移位等效于将码多项式乘式乘 xi 后再模后再模 (xn+1)。）（模（模1)()()1( nxxCxxC）（模模1)()()( niixxCxxC第11页2021-12-13Department of Electronics and Information, NCUT Song Peng(4) 举例：举例：(7,3) 循环码循环码可由任一个码字，比如可由任一个码字，比如 (0011101) 经过循环移位，得到经过循环移位，得到其它其它 6 个非个非 0 0 码字；码字；可由相应的码多项式可由相应的码多项式 (x4+x3+x2+1)，乘以，乘以 xi(i=1,2,6)，再模再模 (x7+1

10、) 运算得到其它运算得到其它 6 个非个非 0 0 码多项式。移位过码多项式。移位过程和相应的多项式运算如表程和相应的多项式运算如表8.1所示。所示。第12页2021-12-13Department of Electronics and Information, NCUT Song Peng(4) 举例：举例：(7,3) 循环码循环码第13页2021-12-13Department of Electronics and Information, NCUT Song Peng(1) 循环码的生成矩阵循环码的生成矩阵(2) 循环码的生成多项式循环码的生成多项式(3) 生成多项式和码多项式的关系生成

11、多项式和码多项式的关系(4) 如何寻找一个合适的生成多项式如何寻找一个合适的生成多项式(5) 循环码的监督多项式和监督矩阵循环码的监督多项式和监督矩阵第14页2021-12-13Department of Electronics and Information, NCUT Song Peng(1) 循环码的生成矩阵循环码的生成矩阵循环码的循环特性循环码的循环特性：可由一个码字的循环移位得到其它的非：可由一个码字的循环移位得到其它的非 0 0 码码字。在字。在 (n,k) 循环码的循环码的 2k 个码字中，取前个码字中，取前 (k1) 位皆为位皆为 0 的码字的码字 g(x)（次数（次数 r=n

12、k），再经），再经 (k1) 次循环移位，共得到次循环移位，共得到 k 个码字：个码字： g(x), xg(x), , xk1g(x) 这这 k 个码字是相互独立的，可作为码生成矩阵的个码字是相互独立的，可作为码生成矩阵的 k 行，得到行，得到循环循环码的生成矩阵码的生成矩阵 G(x)。矩阵中的元素是多项式：矩阵中的元素是多项式： 010211101121)()()()()(gxgxgxgxgxgxgxgxgxgxxgxgxxgxxGknknknknkknknkk第15页2021-12-13Department of Electronics and Information, NCUT Song

13、 Peng(1) 循环码的生成矩阵循环码的生成矩阵将矩阵中的多项式改写成对应的将矩阵中的多项式改写成对应的 n 重矢量形式：重矢量形式： 01个个 k 0101010100000000000ggggggggggggknknknknGG01个个 k第16页2021-12-13Department of Electronics and Information, NCUT Song Peng(2) 循环码的生成多项式循环码的生成多项式码的生成矩阵一旦确定，码就确定了；码的生成矩阵一旦确定，码就确定了；(n,k) 循环码可由它的一个循环码可由它的一个 (nk) 次码多项式次码多项式 g(x) 来确来确

14、定；定；g(x) 生成了生成了 (n,k) 循环码，循环码，称称 g(x) 为码的生成多项式。为码的生成多项式。 g(x)是一个是一个(nk)次首次首1多项式多项式0111)(gxgxgxxgknknkn 第17页2021-12-13Department of Electronics and Information, NCUT Song Peng(3) 生成多项式生成多项式和和码多项式码多项式的关系的关系定理定理8.2.1：在在 (n,k) 循环码中，生成多项式循环码中，生成多项式 g(x)是惟一的是惟一的(nk)次码多次码多项式项式,且次数是最低的。且次数是最低的。证明证明： 先证先证在在

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

16、性码来说是不可能的，因此 g(x) 是最低是最低次的码多项式，次的码多项式，即即 gnk 必为必为 1。10001个个 k第18页2021-12-13Department of Electronics and Information, NCUT Song Peng(3) 生成多项式生成多项式和和码多项式码多项式的关系的关系定理定理8.2.1：在在 (n,k) 循环码中，生成多项式循环码中，生成多项式 g(x)是惟一的是惟一的(nk)次码多次码多项式项式,且次数是最低的。且次数是最低的。证明证明： (nk) 次码多项式是最低次码多项式。次码多项式是最低次码多项式。v g0=1，否则经，否则经 (

17、n1) 次左移循环后将得到低于次左移循环后将得到低于 (nk) 次的码多项式。次的码多项式。v g(x) 是惟一的是惟一的 (nk) 次多项式。如果存在另一个次多项式。如果存在另一个 (nk) 次码多项式，次码多项式，设为设为 g(x) ，根据线性码的封闭性，则，根据线性码的封闭性，则 g(x) + g(x) 也必为一个码多项式。也必为一个码多项式。由于由于 g(x)和和 g(x) 的次数相同，它们的和式的的次数相同，它们的和式的 (nk) 次项系数为次项系数为0，那么，那么 g(x) + g(x) 是一个次数低于是一个次数低于 (nk) 次的码多项式，前面已证明次的码多项式，前面已证明 g(

18、x) 的次的次数是最低的，因此数是最低的，因此 g(x) 不能存在，所以不能存在，所以 g(x) 是惟一的是惟一的 (nk) 次码多项式。次码多项式。第19页2021-12-13Department of Electronics and Information, NCUT Song Peng(3) 生成多项式生成多项式和和码多项式码多项式的关系的关系定理定理8.2.2：在在 (n,k) 循环码中，每个码多项式循环码中，每个码多项式 C(x) 都是都是 g(x) 的倍式；的倍式；而每个为而每个为 g(x) 倍式且次数小于或等于倍式且次数小于或等于 (n1) 的多项式，必是一个码的多项式，必是一个

19、码多项式。多项式。证明证明： 设设 mm=(mk1,mk2,m0) 为任一信息组，为任一信息组，G(x) 为该为该 (n,k) 循环码循环码的的生成矩阵，则相应的码多项式为：生成矩阵，则相应的码多项式为：C(x)=mmG(x)：)()()()()()(),()(0221121021xgmxmxmxgxxgxgxxgxmmmxCkkkkkkkk 第20页2021-12-13Department of Electronics and Information, NCUT Song Peng(3) 生成多项式生成多项式和和码多项式码多项式的关系的关系定理定理8.2.2：在在 (n,k) 循环码中，每个

20、码多项式循环码中，每个码多项式 C(x) 都是都是 g(x) 的倍式；的倍式；而每个为而每个为 g(x) 倍式且次数小于或等于倍式且次数小于或等于 (n1) 的多项式，必是一个码的多项式，必是一个码多项式。多项式。证明证明： 循环码的任一码多项式为循环码的任一码多项式为 g(x) 的倍式。的倍式。 凡是为凡是为 g(x) 的倍式且次数小于或等于的倍式且次数小于或等于 (n1) 的多项式，一定能分的多项式，一定能分解成上式的形式，因而它就是信息多项式：解成上式的形式，因而它就是信息多项式：m(x)=(mk1xk1+mk2 1xk2+m0) 并由生成矩阵并由生成矩阵 G(x) 所生成的码多项式。所

21、生成的码多项式。第21页2021-12-13Department of Electronics and Information, NCUT Song Peng(3) 生成多项式生成多项式和和码多项式码多项式的关系的关系定理定理8.2.3( (定理定理8.2.2的逆定理的逆定理) )：在一个在一个 (n,k) 线性码中，线性码中，如果全部码多项式都是最低次的如果全部码多项式都是最低次的 (nk) 次码多项式的倍式，次码多项式的倍式，则此线性码为一个则此线性码为一个 (n,k) 循环码。循环码。注注：一般说来，这种循环码仍具有把一般说来，这种循环码仍具有把 (n,k) 线性码码中任线性码码中任一非

22、一非 0 0 码字循环移位必为一码字的循环特性，但从一个码字循环移位必为一码字的循环特性，但从一个非非 0 0 码字出发，进行循环移位，就未必能得到码的所有码字出发，进行循环移位，就未必能得到码的所有非非 0 0 码字了。所以称这种循环码为码字了。所以称这种循环码为推广循环码推广循环码。第22页2021-12-13Department of Electronics and Information, NCUT Song Peng(3) 生成多项式生成多项式和和码多项式码多项式的关系的关系 码字循环关系图码字循环关系图q 单纯循环码的单纯循环码的码字循环图：码字循环图：(7,3)循环码循环码第23

23、页2021-12-13Department of Electronics and Information, NCUT Song Peng(3) 生成多项式生成多项式和和码多项式码多项式的关系的关系 码字循环关系图码字循环关系图q 推广循环码的推广循环码的码字循环图：码字循环图： (6,3)循环码循环码第24页2021-12-13Department of Electronics and Information, NCUT Song Peng(4) 如何寻找一个合适的生成多项式如何寻找一个合适的生成多项式循环码的码多项式等于信息多项式乘以生成多项式：循环码的码多项式等于信息多项式乘以生成多项式：

24、对一个循环码只要生成多项式一旦确定，码就确定了，编码问题对一个循环码只要生成多项式一旦确定，码就确定了，编码问题就解决了。就解决了。作一循环码的关键，就在于寻找一个适当的生成多项式。作一循环码的关键，就在于寻找一个适当的生成多项式。)()()()()()(),()(0221121021xgmxmxmxgxxgxgxxgxmmmxCkkkkkkkk 第25页2021-12-13Department of Electronics and Information, NCUT Song Peng(4) 如何寻找一个合适的生成多项式如何寻找一个合适的生成多项式定理定理8.2.4： (n,k) 循环码的生

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

26、(x) 代入式代入式(8.2.1)得：得：(xn+1)=xk+m(x)g(x) 即：即：g(x) 是是 (xn+1) 的因式。的因式。欧几里德除法：设 b 是正整数，则任意正整数 a b 皆可惟一地表示成：a=qb+r 0r b第26页2021-12-13Department of Electronics and Information, NCUT Song Peng(4) 如何寻找一个合适的生成多项式如何寻找一个合适的生成多项式定理定理8.2.5：若若 g(x) 是一个是一个 (nk) 次次 多项式，且为多项式，且为(xn+1) 的因式，则的因式，则 g(x) 生成一个生成一个 (n,k)

27、循环码。循环码。证明证明：由于由于 g(x) 是一个是一个 (nk) 次多项式，且为次多项式，且为 (xn+1) 的因式，所以：的因式，所以：g(x), x g(x), xk1 g(x) 是是 k 个次数小于个次数小于 n，并且彼此独立的多项，并且彼此独立的多项式；式； )()()()()(21xgxxgxgxxgxxGkk将此多项式用作码的生成矩阵的将此多项式用作码的生成矩阵的 k 行，得到行，得到 (n,k) 线性码的生成矩阵；线性码的生成矩阵；第27页2021-12-13Department of Electronics and Information, NCUT Song Peng(4

28、) 如何寻找一个合适的生成多项式如何寻找一个合适的生成多项式定理定理8.2.5：若若 g(x) 是一个是一个 (nk) 次次 多项式，且为多项式，且为(xn+1) 的因式，则的因式，则 g(x) 生生成一个成一个 (n,k) 循环码。循环码。证明证明： 设信息组设信息组 mm=(mk1,mk2,m0)，则相应的码字为：，则相应的码字为： C(x)=m m G(x)=(mk1xk1+mk2 1xk2+m0) g(x)= m(x) g(x)v C(x) 的次数的次数n1；v m(x) 是是 2k 个信息多项式的表示式；个信息多项式的表示式；v 所以：所以：C(x) 即为相应即为相应 2k 个码多项

29、式的表示式。个码多项式的表示式。 因此：因此：g(x) 生成一个生成一个 (n,k) 线性码。线性码。 C(x) 是是 (nk) 次多项式次多项式 g(x) 的倍式，所以的倍式，所以 g(x) 生成一个生成一个 (n,k)循环码。循环码。第28页2021-12-13Department of Electronics and Information, NCUT Song Peng(4) 如何寻找一个合适的生成多项式如何寻找一个合适的生成多项式定理定理8.2.5：若若 g(x) 是一个是一个 (nk) 次次 多项式，且为多项式，且为(xn+1) 的因式，则的因式，则 g(x) 生成一个生成一个 (

30、n,k) 循环码。循环码。 结论：结论：求作一个求作一个 (n,k) 循环码时，只要分解多项式循环码时，只要分解多项式(xn+1) ，从中取出，从中取出(nk)次因式作生成多项式即可。次因式作生成多项式即可。 例：例：求求 (7,3) 循环码的生成多项式。循环码的生成多项式。解解：v 分解多项式分解多项式 x7+1，取其，取其 4 次因式作生成多项式：次因式作生成多项式：x7+1= (x+1) (x3+x2+1) (x3+x+1)v 可将一次和任一个三次因式的乘积作为生成多项式，可取：可将一次和任一个三次因式的乘积作为生成多项式，可取：g1(x)= (x+1) (x3+x2+1) = x4+x

31、2+x+1 或或 g2(x)= (x+1) (x3+x+1) = x4+x3+x2+1第29页2021-12-13Department of Electronics and Information, NCUT Song Peng(5) 循环码的监督多项式和监督矩阵循环码的监督多项式和监督矩阵 循环码的监督多项式循环码的监督多项式：设设 g(x) 为为 (n,k) 循环码的生成多项式，必为循环码的生成多项式，必为 (xn+1) 的因式，则有：的因式，则有：xn+1=h(x) g(x)，式中式中 h(x) 为为 k 次多项式，称次多项式，称为为 (n,k) 循环码的监督多项式。循环码的监督多项式。

32、 (n,k) 循环码也可由其监督多项式完全确定。循环码也可由其监督多项式完全确定。 举例举例：(7,3) 循环码：循环码：x7+1= (x3+x+1)(x4+x2+x+1)q 4 次多项式为生成多项式：次多项式为生成多项式：g(x)=x4+x2+x+1=g4x4+g3x3+g2x2+g1x+g0 3 次多项式是监督多项式：次多项式是监督多项式：h(x)=x3+x+1=h3x3+h2x2+h1x+h0第30页2021-12-13Department of Electronics and Information, NCUT Song Peng(5) 循环码的监督多项式和监督矩阵循环码的监督多项式和

33、监督矩阵 循环码的监督矩阵循环码的监督矩阵 由等式由等式 x7+1= h(x) g(x) 两两 端同次项系数相等得：端同次项系数相等得： 将上面的方程组写成将上面的方程组写成 矩阵形式：矩阵形式： 0000332463223145312213044302112033hghgxhghghgxhghghghgxhghghghgx的的系系数数：的的系系数数：的的系系数数：的的系系数数：Tggggghhhhhhhhhhhhhhhh0 0 0123432103210321032100000000000000001223331)(hxhxhxhxxxh 01223344241)(gxgxgxgxgxxxx

34、g 第31页2021-12-13Department of Electronics and Information, NCUT Song Peng(5) 循环码的监督多项式和监督矩阵循环码的监督多项式和监督矩阵 循环码的监督矩阵循环码的监督矩阵上式中，列阵的元素是生成多项式上式中，列阵的元素是生成多项式 g(x) 的系数，是一个码字，那的系数，是一个码字，那么第一个矩阵则为么第一个矩阵则为 (7,3) 循环码的循环码的监督矩阵，监督矩阵，即：即：)2 . 2 . 8(0000000000003210321032103210)3 , 7( hhhhhhhhhhhhhhhhHH第32页2021-1

35、2-13Department of Electronics and Information, NCUT Song Peng(5) 循环码的监督多项式和监督矩阵循环码的监督多项式和监督矩阵 循环码监督矩阵的构成循环码监督矩阵的构成由式由式 (8.2.2) 可见，监督矩阵的第一行是码的监督多项式可见，监督矩阵的第一行是码的监督多项式 h(x) 的系的系数的数的反序排列，反序排列，第二、三、四行是第一行的移位；第二、三、四行是第一行的移位；可用监督多项式的系数来构成监督矩阵：可用监督多项式的系数来构成监督矩阵： 其中其中h*(x) 表示表示 h(x) 的反多项式的反多项式)3 . 2 . 8(000

36、1011001011001011001011000)()()()(*3*2*)3 , 7( xhxxhxxxhxhHH第33页2021-12-13Department of Electronics and Information, NCUT Song Peng(5) 循环码的监督多项式和监督矩阵循环码的监督多项式和监督矩阵 循环码监督矩阵的构成循环码监督矩阵的构成(n,k) 循环码的监督矩阵：循环码的监督矩阵： 0011101101100)()()(11111111*1*),(kkkkknknhhhhhhhhxhxxxhxhHH第34页2021-12-13Department of Elect

37、ronics and Information, NCUT Song Peng(5) 循环码的监督多项式和监督矩阵循环码的监督多项式和监督矩阵 对偶问题对偶问题如果如果 xn+1=h(x) g(x)，其中，其中 g(x) 为为 (nk) 次多项式，以次多项式，以 g(x)为生成为生成多项式，则生成一个多项式，则生成一个 (n,k) 循环码；循环码；以以 h(x) 为生成多项式，则生成为生成多项式，则生成 (n,nk) 循环码；循环码；这两个循环码互为对偶码。这两个循环码互为对偶码。第35页2021-12-13Department of Electronics and Information, N

38、CUT Song Peng(1) 系统循环码构成系统循环码构成信息向量信息向量：mm=(mk1,mk2,m0)信息多项式信息多项式：m(x)=mk1xk1+mk2 xk2+m0 码多项式码多项式的高次幂部分等于的高次幂部分等于 m(x)，即：，即： C(x)=cn1xn1+ cnkxnk+ cnk1xnk1 +c1x +c0 =xnk m(x)+q(x) （q(x)的次数的次数nk）校验位多项式校验位多项式：q(x)由于码多项式是生成多项式的倍式，所以：由于码多项式是生成多项式的倍式，所以：C(x)= xnkm(x)+q(x)=a(x)g(x)0 （mod g(x)）q(x)=C(x)+ xn

39、km(x)xnkm(x) （mod g(x)）第36页2021-12-13Department of Electronics and Information, NCUT Song Peng(1) 系统循环码构成系统循环码构成 循环码的系统码形式为循环码的系统码形式为：C(x)= xnkm(x)+ (xnkm(x) mod g(x) 系统循环码构造过程步骤系统循环码构造过程步骤q 信息多项式乘信息多项式乘 xnk： xnkm(x)q 对对 xnkm(x) 求余式求余式：q(x)xnkm(x) (mod g(x)q 求码多项式求码多项式：C(x)=xnkm(x)+ ( xnkm(x) mod g(

40、x) =xnkm(x)+ q(x)第37页2021-12-13Department of Electronics and Information, NCUT Song Peng(2) 举例举例例例6.3.5：在由：在由 g(x)=x4+x3+x2+1生成的生成的 (7,3) 循环码中，求循环码中，求信息组信息组m=(101)的对应码多项式。的对应码多项式。1)()() 1()(462437 xxrxgxxxxxmx得得到到余余式式：，除除以以于于是是码码多多项项式式为为：1)()()(464 xxxxrxmxxC第38页2021-12-13Department of Electronics a

41、nd Information, NCUT Song Peng(1) 多项式加法电路多项式加法电路(2) 多项式乘法电路多项式乘法电路(3) 多项式除法电路多项式除法电路第39页2021-12-13Department of Electronics and Information, NCUT Song Peng(1) 多项式加法电路多项式加法电路多项式多项式 a(x)=anxn+an1xn1+a1x+a0 表示的是时间序列表示的是时间序列a a=(an,an1,a1,a0)，因此多项式的计算表现为对时间序列的操作；，因此多项式的计算表现为对时间序列的操作；对二进制多项式系数的基对二进制多项式系数

42、的基本操作为模本操作为模 2 加和模加和模 2 乘；乘；电路图运算符号的意义：电路图运算符号的意义：第40页2021-12-13Department of Electronics and Information, NCUT Song Peng(1) 多项式加法电路多项式加法电路 A(x) 与与 B(x) 的相加电路的相加电路第41页2021-12-13Department of Electronics and Information, NCUT Song Peng(2) 多项式乘法电路多项式乘法电路多项式乘以多项式乘以 x 等价为时间序列等价为时间序列 a a 延迟一位；延迟一位；多项式多项式

43、 a(x) 与多项式与多项式 g(x) 的乘等价为的乘等价为 a(x) 的不同位移后的相加：的不同位移后的相加：a(x)g(x)=a(x)(g1(x)+ g2(x)= a(x)g1(x)+ a(x)g2(x) 多项式乘法电路：多项式乘法电路：设多项式的低位在前，电路中所有寄存器初态设多项式的低位在前，电路中所有寄存器初态为为 0。第42页2021-12-13Department of Electronics and Information, NCUT Song Peng(2) 多项式乘法电路多项式乘法电路多项式多项式乘法电路：乘法电路：第43页2021-12-13Department of E

44、lectronics and Information, NCUT Song Peng(3) 多项式除法电路多项式除法电路当当 g(x) =1，多项式，多项式 a(x) 模模 g(x) 的余式为的余式为 0，电路如图所示。，电路如图所示。第44页2021-12-13Department of Electronics and Information, NCUT Song Peng(3) 多项式除法电路多项式除法电路当当 g(x)是单向式是单向式 g(x)=xk， a(x) 模模 g(x) 的余式的次数小于的余式的次数小于 k，进入，进入电路的输入顺序为电路的输入顺序为 an,an1,a1,a0。a

45、(x)ak1xk1+ak2xk2+a1x+a0 (mod xk) 运算电路如图所示。运算电路如图所示。第45页2021-12-13Department of Electronics and Information, NCUT Song Peng(3) 多项式除法电路多项式除法电路由于由于 xk1 mod(x+1), k=0,1,2,。若。若 a(x) 的次数为的次数为 n，则：，则：a(x) = an1+an2+a1+a0（mod(x+1)） q0（mod 2） 运算电路如图所示：运算电路如图所示：第46页2021-12-13Department of Electronics and Info

46、rmation, NCUT Song Peng(3) 多项式除法电路多项式除法电路同样由长除法得：同样由长除法得： 运算电路如图所示：运算电路如图所示： niiiniiiniiiniiiaqaqxqqaaxa5 , 3 , 114 , 2 , 002105 , 3 , 14 , 2 , 0)1(mod()(其其中中：第47页2021-12-13Department of Electronics and Information, NCUT Song Peng(3) 多项式除法电路多项式除法电路多项式多项式 a(x) 模模 (x2+x+1) 的运算电路如图所示：的运算电路如图所示：第48页2021

47、-12-13Department of Electronics and Information, NCUT Song Peng(3) 多项式除法电路多项式除法电路一般的多项式模一般的多项式模 g(x)=grxr+gr1xr1+g1x+g0 的运算电路如图所的运算电路如图所示。示。移位寄存器初态全为移位寄存器初态全为0；当当 a(x) 输入完后，移位寄存器内容输入完后，移位寄存器内容 (qr1, , q1, q0) 就是余式：就是余式：q(x)=qr1xr1+ qr2xr2+ +q1x+q0 a(x) (mod g(x)第49页2021-12-13Department of Electronic

48、s and Information, NCUT Song Peng(3) 多项式除法电路多项式除法电路 多项式除法电路的构造多项式除法电路的构造q 多项式除法电路是一个由除式（这里就是生成多项式多项式除法电路是一个由除式（这里就是生成多项式 g(x)） g(x)=gnkxnk+gnk1xnk1+g1x+g0 所确定的所确定的反馈移位寄存器。反馈移位寄存器。q 除法电路的构造方法除法电路的构造方法l 移位寄存器的级数等于除式的次数移位寄存器的级数等于除式的次数 nk；l 移位寄存器的反馈抽头，由除式的各项系数移位寄存器的反馈抽头，由除式的各项系数 gi(i=0,1,nk) 决定：决定： 当某个抽

49、头当某个抽头=0时，对应的反馈断开；时，对应的反馈断开； 当某个抽头当某个抽头=1时，对应的反馈接通。时，对应的反馈接通。 完成除法所需的移位次数等于被除式的次数加完成除法所需的移位次数等于被除式的次数加1。第50页2021-12-13Department of Electronics and Information, NCUT Song Peng(3) 多项式除法电路多项式除法电路 多项式除法电路举例多项式除法电路举例q 利用除法电路完成两个多项式除法运算，求其余式的过程和将利用除法电路完成两个多项式除法运算，求其余式的过程和将两个多项式进行长除运算是完全一致的；两个多项式进行长除运算是完全

50、一致的；q (x5+x2)(x4+x3+x +1) 的长除运算过程：的长除运算过程：)(11)()()()(1133442452534第二余式第二余式第一余式第一余式除式除式被除式被除式商式商式 xxxxxxxxxxxxxxxx第51页2021-12-13Department of Electronics and Information, NCUT Song Peng(3) 多项式除法电路多项式除法电路 多项式除法电路举例多项式除法电路举例q(x5+x2)(x4+x3+x +1) 的长除运算过程：的长除运算过程：l每做一次除法运算，被除式（或前次除法的余式）的首项被抵每做一次除法运算，被除式（

51、或前次除法的余式）的首项被抵消，因而除法电路中每做一次除法运算，最高项就移到寄存器消，因而除法电路中每做一次除法运算，最高项就移到寄存器之外而丢掉；之外而丢掉；除式除首项外的其它各项系数都要加到被除式或前次运算的余除式除首项外的其它各项系数都要加到被除式或前次运算的余式中去，而除法电路的反馈正是按除式的规律连接的，恰好完式中去，而除法电路的反馈正是按除式的规律连接的，恰好完成所需的加法运算。成所需的加法运算。第52页2021-12-13Department of Electronics and Information, NCUT Song Peng(3) 多项式除法电路多项式除法电路 多项式除

52、法电路举例多项式除法电路举例q (x5+x2)(x4+x3+x +1) 运算电路工作过程：运算电路工作过程： 各级预先清零，被除式系数由移位寄存器第一级输入，经各级预先清零，被除式系数由移位寄存器第一级输入，经 4 次次移位后，最高项的系数到达移位寄存器右端出现反馈信号；移位后，最高项的系数到达移位寄存器右端出现反馈信号； 第一次对被除式作除法，下一个移位脉冲加入时，被除式首项第一次对被除式作除法，下一个移位脉冲加入时，被除式首项 x5 移出寄存器，相当于首项被抵消，反馈信号按除式规律与被除移出寄存器，相当于首项被抵消，反馈信号按除式规律与被除式相应项进行式相应项进行模模 2 加加，移位寄存器

53、新的内容即为第一余式；，移位寄存器新的内容即为第一余式；第53页2021-12-13Department of Electronics and Information, NCUT Song Peng(3) 多项式除法电路多项式除法电路 多项式除法电路举例多项式除法电路举例q (x5+x2)(x4+x3+x +1) 运算电路工作过程：运算电路工作过程： 第一余式的首项第一余式的首项 x4 的系数到达电路的末级，出现反馈信号，准的系数到达电路的末级，出现反馈信号，准备作第二次除法，当下一个移位脉冲加入时，第一余式的首项移备作第二次除法，当下一个移位脉冲加入时，第一余式的首项移出寄存器被丢掉，反馈信

54、号又把除式出寄存器被丢掉，反馈信号又把除式(除首项外除首项外)加到第一余式，得加到第一余式，得到第二余式（即所求余式）；到第二余式（即所求余式）； 为了使被除式全部移入寄存器，除法求余所需要的移位次数等为了使被除式全部移入寄存器，除法求余所需要的移位次数等于被除式次数加于被除式次数加 1。第54页2021-12-13Department of Electronics and Information, NCUT Song Peng(3) 多项式除法电路多项式除法电路 多项式除法电路举例多项式除法电路举例q 表表 8.4.1 列出了电路的运算过程列出了电路的运算过程第55页2021-12-13De

55、partment of Electronics and Information, NCUT Song Peng9.5.1 非系统码编码电路非系统码编码电路9.5.2 系统码编码电路系统码编码电路(1) 系统码编码的基本原理系统码编码的基本原理(2) 用用 (nk) 级移位寄存器实现的编码电路级移位寄存器实现的编码电路(3) 用用 k 级移位寄存器实现的编码电路级移位寄存器实现的编码电路第56页2021-12-13Department of Electronics and Information, NCUT Song Peng 循环码码多项式是生成多项式的倍式。循环码码多项式是生成多项式的倍式。

56、 非系统编码电路非系统编码电路/循环码乘法编码电路循环码乘法编码电路q 输入输入 a(x)=m(x)， m(x)的次数的次数 kq 输出输出 a(x)g(x)=C(x)即是码式，即是码式，C(x)的次数的次数 n9.5循环码的编码电路第57页2021-12-13Department of Electronics and Information, NCUT Song Peng 举例：生成举例：生成 (7,4) 汉明码的生成多项式为汉明码的生成多项式为 g(x)=x3+ x2+1，非系统编，非系统编码电路如图所示。电路共工作码电路如图所示。电路共工作 7 个时钟节拍。个时钟节拍。9.5循环码的编码

57、电路第58页2021-12-13Department of Electronics and Information, NCUT Song Peng 举例：生成举例：生成 (7,4) 汉明码的生成多项式为汉明码的生成多项式为 g(x)=x3+ x2+1，非系统编，非系统编码电路如图所示。电路共工作码电路如图所示。电路共工作 7 个时钟节拍。个时钟节拍。 由表可见，当由表可见，当 m(x)=x3 + x时，非系统码字时，非系统码字 C(x) 为：为： C(x)= x6 + x5 +x4 + x =(x3+x)(x3 + x2 +1)9.5循环码的编码电路第59页2021-12-13Departme

58、nt of Electronics and Information, NCUT Song Peng(1) 系统码编码的基本原理系统码编码的基本原理 求生成多项式求生成多项式 g(x)：分解多项式分解多项式 (xn+1)，取，取 (nk)次次 因式作生成多因式作生成多项式项式 g(x)，一般可通过查表完成。，一般可通过查表完成。 利用利用 g(x) 实现编码实现编码q 设设信息多项式信息多项式为：为：m(x)=mk1xk1+mk2 xk2+m0q 设设监督多项式监督多项式为：为：q(x)=qr1xr1+qr2 xr2+q0q (n,k) 循环码的循环码的码多项式码多项式为：为： C(x)=cn1

59、xn1+cn2xn2+cnkxnk +cnk1xnk1+c1x+c0 前前 k 项系数为信息位，后项系数为信息位，后 r= nk 项为校验位。项为校验位。q 所以：所以：cn1xn1+cnkxnk=xnk(mk1xk1+m0)=xnkm(x) cnk1xnk1+c0=qr1xr1+q0=q(x)9.5循环码的编码电路第60页2021-12-13Department of Electronics and Information, NCUT Song Peng(2) 用用 (nk) 级移位寄存器实现的编码电路级移位寄存器实现的编码电路 循环码编码电路结构和工作原理循环码编码电路结构和工作原理q 工

60、作原理工作原理：二元二元 (n,k) 循环码的编码是将信息多项式循环码的编码是将信息多项式 m(x) 乘乘 xnk 后再除以生成多项式后再除以生成多项式 g(x) 求出它的余式，即为监督位多项式求出它的余式，即为监督位多项式 q(x)。C(x)= xnkm(x)+（xnkm(x) mod g(x)）q 二元二元 (n,k) 循环码的编码电路就是以循环码的编码电路就是以 g(x) 为除式的除法电路，而为除式的除法电路，而输入的被除式为输入的被除式为 xnkm(x) 。q 实际的编码电路如图实际的编码电路如图 8.5.3 所示。所示。 其级数等于其级数等于 g(x) 的次数的次数 (nk) ； 反