[数学]信息论与编码原理_第9章_循环码

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

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

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

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

5、(x)=cn 1xn 1+cn 2xn 2+c0 码多项式码多项式 i 次循环移位的表示方法次循环移位的表示方法 记码多项式记码多项式 C(x) 的一次左移循环为的一次左移循环为 C(1)(x) ，i 次左移循环为次左移循环为 C(i)(x) in i n iin in n in i n n n n n n n n n cxcxcxcxcxcxC cxcxcxcxcxC ccxcxcxC 1 10 1 1 2 2 1 1 )( 10 2 1 2 3 1 2 (1) 01 2 2 1 1 )( )( )( 第7页2021-7-13Department of Electronics and Inf

6、ormation, NCUT Song Peng (3) 码多项式码多项式 码多项式的模码多项式的模 (xn+1) 运算运算 q 0 和和 1 两个元素模两个元素模 2 运算下构成域。运算下构成域。 q 若若 p 为素数，则整数全体在模为素数，则整数全体在模 p 运算下的剩余类全体运算下的剩余类全体 在模在模 p 下构成域。下构成域。 1,3,2,1,0 p 101 000 10 011 100 10 第8页2021-7-13Department of Electronics and Information, NCUT Song Peng (3) 码多项式码多项式 码多项式的模码多项式的模 (

7、xn+1) 运算运算 q 以以 p=3 为模的剩余类全体为模的剩余类全体 q 模模 3 运算的规则如下：运算的规则如下： 1202 2101 0000 210 1022 0211 2100 210 第9页2021-7-13Department of Electronics and Information, NCUT Song Peng (3) 码多项式码多项式 码多项式的模码多项式的模 (xn+1) 运算运算 q 码字码字 C C 循环循环 i 次所得码字的码多项式：次所得码字的码多项式： q C(x) 乘以乘以 x，再除以，再除以 (xn+1)，得：，得： in i n in in n in

8、 i n n n n cxcxcxcxcxC cxcxcxC 1 10 2 2 1 1 )( 0 2 2 1 1 )( )( 1 )( 11 )( )1( 1 10 2 1 2 3 1 2 1 n n n n n n n n n n x xC c x cxcxcxcxc c x xxC 第10 页 2021-7-13Department of Electronics and Information, NCUT Song Peng (3) 码多项式码多项式 码多项式的模码多项式的模 (xn+1) 运算运算 q 上式表明：上式表明：码字循环一次的码多项式码字循环一次的码多项式 C(1)(x) 是原

9、码多项式是原码多项式 C(x) 乘以乘以 x 除以除以 (xn+1) 的余式。写作：的余式。写作： q C(x) 的的 i 次循环移位次循环移位 C(i)(x) 是是 C(x) 乘以乘以 xi 除以除以 (xn+1) 的余式，的余式， 即：即： q 结论：结论：循环码的码字的循环码的码字的 i 次循环移位等效于将码多项次循环移位等效于将码多项 式乘式乘 xi 后再模后再模 (xn+1)。 ）（模（模1)()( )1( n xxCxxC ）（模模1)()( )( nii xxCxxC 第11 页 2021-7-13Department of Electronics and Information

10、, NCUT Song Peng (4) 举例：举例：(7,3) 循环码循环码 可由任一个码字，比如可由任一个码字，比如 (0011101) 经过循环移位，得到经过循环移位，得到 其它其它 6 个非个非 0 0 码字；码字； 可由相应的码多项式可由相应的码多项式 (x4+x3+x2+1)，乘以，乘以 xi(i=1,2,6)， 再模再模 (x7+1) 运算得到其它运算得到其它 6 个非个非 0 0 码多项式。移位过码多项式。移位过 程和相应的多项式运算如表程和相应的多项式运算如表8.1所示。所示。 第12 页 2021-7-13Department of Electronics and Info

11、rmation, NCUT Song Peng (4) 举例：举例：(7,3) 循环码循环码 第13 页 2021-7-13Department of Electronics and Information, NCUT Song Peng (1) 循环码的生成矩阵循环码的生成矩阵 (2) 循环码的生成多项式循环码的生成多项式 (3) 生成多项式和码多项式的关系生成多项式和码多项式的关系 (4) 如何寻找一个合适的生成多项式如何寻找一个合适的生成多项式 (5) 循环码的监督多项式和监督矩阵循环码的监督多项式和监督矩阵 第14 页 2021-7-13Department of Electronic

12、s and Information, NCUT Song Peng (1) 循环码的生成矩阵循环码的生成矩阵 循环码的循环特性循环码的循环特性：可由一个码字的循环移位得到其它的非：可由一个码字的循环移位得到其它的非 0 0 码码 字。在字。在 (n,k) 循环码的循环码的 2k 个码字中，取前个码字中，取前 (k1) 位皆为位皆为 0 的码字的码字 g(x)（次数（次数 r=nk），再经），再经 (k1) 次循环移位，共得到次循环移位，共得到 k 个码字：个码字： g(x), xg(x), , xk 1g(x) 这这 k 个码字是相互独立的，可作为码生成矩阵的个码字是相互独立的，可作为码生成矩

13、阵的 k 行，得到行，得到循环循环 码的生成矩阵码的生成矩阵 G(x)。矩阵中的元素是多项式：矩阵中的元素是多项式： 01 0 2 1 1 1 01 1 2 1 )( )( )( )( )( gxgxg xgxgxg xgxgxg xg xxg xgx xgx xG kn kn kn kn kkn kn k k 第15 页 2021-7-13Department of Electronics and Information, NCUT Song Peng (1) 循环码的生成矩阵循环码的生成矩阵 将矩阵中的多项式改写成对应的将矩阵中的多项式改写成对应的 n 重矢量形式：重矢量形式： 01个个

14、k 01 01 01 01 000 000 000 00 ggg ggg ggg ggg kn kn kn kn GG 01个个 k 第16 页 2021-7-13Department of Electronics and Information, NCUT Song Peng (2) 循环码的生成多项式循环码的生成多项式 码的生成矩阵一旦确定，码就确定了；码的生成矩阵一旦确定，码就确定了； (n,k) 循环码可由它的一个循环码可由它的一个 (nk) 次码多项式次码多项式 g(x) 来确来确 定；定； g(x) 生成了生成了 (n,k) 循环码，循环码，称称 g(x) 为码的生成多项式。为码的

15、生成多项式。 g(x)是一个是一个(nk)次首次首1多项式多项式 01 1 1 )(gxgxgxxg kn kn kn 第17 页 2021-7-13Department of Electronics and Information, NCUT Song Peng (3) 生成多项式生成多项式和和码多项式码多项式的关系的关系 定理定理8.2.1：在在 (n,k) 循环码中，生成多项式循环码中，生成多项式 g(x)是惟一的是惟一的(nk)次码多次码多 项式项式,且次数是最低的。且次数是最低的。 证明证明： 先证先证在在 (n,k) 循环码系统中存在循环码系统中存在 (nk) 次码多项式。次码多项

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

17、码多项式，即即 gn k 必为 必为 1。 1000 1 个个 k 第18 页 2021-7-13Department of Electronics and Information, NCUT Song Peng (3) 生成多项式生成多项式和和码多项式码多项式的关系的关系 定理定理8.2.1：在在 (n,k) 循环码中，生成多项式循环码中，生成多项式 g(x)是惟一的是惟一的(nk)次码多次码多 项式项式,且次数是最低的。且次数是最低的。 证明证明： (nk) 次码多项式是最低次码多项式。次码多项式是最低次码多项式。 v g0=1，否则经，否则经 (n1) 次左移循环后将得到低于次左移循环后

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

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

20、明证明： 设设 mm=(mk 1,mk2,m0) 为任一信息组， 为任一信息组，G(x) 为该为该 (n,k) 循环码循环码的的 生成矩阵，则相应的码多项式为：生成矩阵，则相应的码多项式为：C(x)=mmG(x)： )()( )( )( )( )( ),()( 0 2 2 1 1 2 1 021 xgmxmxm xg xxg xgx xgx mmmxC k k k k k k kk 第20 页 2021-7-13Department of Electronics and Information, NCUT Song Peng (3) 生成多项式生成多项式和和码多项式码多项式的关系的关系 定理定

21、理8.2.2：在在 (n,k) 循环码中，每个码多项式循环码中，每个码多项式 C(x) 都是都是 g(x) 的倍式；的倍式； 而每个为而每个为 g(x) 倍式且次数小于或等于倍式且次数小于或等于 (n1) 的多项式，必是一个码的多项式，必是一个码 多项式。多项式。 证明证明： 循环码的任一码多项式为循环码的任一码多项式为 g(x) 的倍式。的倍式。 凡是为凡是为 g(x) 的倍式且次数小于或等于的倍式且次数小于或等于 (n1) 的多项式，一定能分的多项式，一定能分 解成上式的形式，因而它就是信息多项式：解成上式的形式，因而它就是信息多项式： m(x)=(mk 1xk 1+mk 2 1xk 2+

22、m0) 并由生成矩阵并由生成矩阵 G(x) 所生成的码多项式。所生成的码多项式。 第21 页 2021-7-13Department of Electronics and Information, NCUT Song Peng (3) 生成多项式生成多项式和和码多项式码多项式的关系的关系 定理定理8.2.3( (定理定理8.2.2的逆定理的逆定理) )：在一个在一个 (n,k) 线性码中，线性码中， 如果全部码多项式都是最低次的如果全部码多项式都是最低次的 (nk) 次码多项式的倍式，次码多项式的倍式， 则此线性码为一个则此线性码为一个 (n,k) 循环码。循环码。 注注：一般说来，这种循环码

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

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

25、适的生成多项式 循环码的码多项式等于信息多项式乘以生成多项式：循环码的码多项式等于信息多项式乘以生成多项式： 对一个循环码只要生成多项式一旦确定，码就确定了，编码问题对一个循环码只要生成多项式一旦确定，码就确定了，编码问题 就解决了。就解决了。 作一循环码的关键，就在于寻找一个适当的生成多项式。作一循环码的关键，就在于寻找一个适当的生成多项式。 )()( )( )( )( )( ),()( 0 2 2 1 1 2 1 021 xgmxmxm xg xxg xgx xgx mmmxC k k k k k k kk 第25 页 2021-7-13Department of Electronics

26、and Information, NCUT Song Peng (4) 如何寻找一个合适的生成多项式如何寻找一个合适的生成多项式 定理定理8.2.4： (n,k) 循环码的生成多项式循环码的生成多项式 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 根据循环码的移位关系，它是根据循环码

27、的移位关系，它是 g(x) 循环移位循环移位 k 次所得到的多项次所得到的多项 式，因而式，因而 g(k)(x) 是是 g(x) 的倍式。的倍式。 设：设：g(k)(x)=m(x)g(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-7-13Department of Electronics and Information, NCUT Song Peng (4) 如何寻找一个合适的生成多项式

28、如何寻找一个合适的生成多项式 定理定理8.2.5：若若 g(x) 是一个是一个 (nk) 次次 多项式，且为多项式，且为(xn+1) 的因式，则的因式，则 g(x) 生成一个生成一个 (n,k) 循环码。循环码。 证明证明： 由于由于 g(x) 是一个是一个 (nk) 次多项式，且为次多项式，且为 (xn+1) 的因式，所以：的因式，所以： g(x), x g(x), xk 1 g(x) 是 是 k 个次数小于个次数小于 n，并且彼此独立的多项，并且彼此独立的多项 式；式； )( )( )( )( )( 2 1 xg xxg xgx xgx xG k k 将此多项式用作码的生成矩阵的将此多项式

29、用作码的生成矩阵的 k 行，得到行，得到 (n,k) 线性码的生成矩阵；线性码的生成矩阵； 第27 页 2021-7-13Department of Electronics and Information, NCUT Song Peng (4) 如何寻找一个合适的生成多项式如何寻找一个合适的生成多项式 定理定理8.2.5：若若 g(x) 是一个是一个 (nk) 次次 多项式，且为多项式，且为(xn+1) 的因式，则的因式，则 g(x) 生生 成一个成一个 (n,k) 循环码。循环码。 证明证明： 设信息组设信息组 mm=(mk 1,mk2,m0)，则相应的码字为： ，则相应的码字为： C(x)

30、=m m G(x)=(mk 1xk 1+mk 2 1xk 2+m0) g(x)= m(x) g(x) v C(x) 的次数的次数n1； v m(x) 是是 2k 个信息多项式的表示式；个信息多项式的表示式； v 所以：所以：C(x) 即为相应即为相应 2k 个码多项式的表示式。个码多项式的表示式。 因此：因此：g(x) 生成一个生成一个 (n,k) 线性码。线性码。 C(x) 是是 (nk) 次多项式次多项式 g(x) 的倍式，所以的倍式，所以 g(x) 生成一个生成一个 (n,k)循环码。循环码。 第28 页 2021-7-13Department of Electronics and In

31、formation, NCUT Song Peng (4) 如何寻找一个合适的生成多项式如何寻找一个合适的生成多项式 定理定理8.2.5：若若 g(x) 是一个是一个 (nk) 次次 多项式，且为多项式，且为(xn+1) 的因式，则的因式，则 g(x) 生成一个生成一个 (n,k) 循环码。循环码。 结论：结论：求作一个求作一个 (n,k) 循环码时，只要分解多项式循环码时，只要分解多项式(xn+1) ，从中取出，从中取出(n k)次因式作生成多项式即可。次因式作生成多项式即可。 例：例：求求 (7,3) 循环码的生成多项式。循环码的生成多项式。 解解： v 分解多项式分解多项式 x7+1，取

32、其，取其 4 次因式作生成多项式：次因式作生成多项式： x7+1= (x+1) (x3+x2+1) (x3+x+1) v 可将一次和任一个三次因式的乘积作为生成多项式，可取：可将一次和任一个三次因式的乘积作为生成多项式，可取： g1(x)= (x+1) (x3+x2+1) = x4+x2+x+1 或或 g2(x)= (x+1) (x3+x+1) = x4+x3+x2+1 第29 页 2021-7-13Department of Electronics and Information, NCUT Song Peng (5) 循环码的监督多项式和监督矩阵循环码的监督多项式和监督矩阵 循环码的监督多

33、项式循环码的监督多项式：设设 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) q 4 次多项式为生成多项式：次多项式为生成多项式： g(x)=x4+x2+x+1=g4x4+g3x3+g2x2+g1x+g0 3

34、次多项式是监督多项式：次多项式是监督多项式：h(x)=x3+x+1=h3x3+h2x2+h1x+h0 第30 页 2021-7-13Department of Electronics and Information, NCUT Song Peng (5) 循环码的监督多项式和监督矩阵循环码的监督多项式和监督矩阵 循环码的监督矩阵循环码的监督矩阵 由等式由等式 x7+1= h(x) g(x) 两两 端同次项系数相等得：端同次项系数相等得： 将上面的方程组写成将上面的方程组写成 矩阵形式：矩阵形式： 0 0 0 0 3324 6 322314 5 31221304 4 30211203 3 hgh

35、gx hghghgx hghghghgx hghghghgx 的的系系数数： 的的系系数数： 的的系系数数： 的的系系数数： T g g g g g hhhh hhhh hhhh hhhh 0 0 0 1 2 3 4 3210 3210 3210 3210 0 0 000 000 000 000 01 2 2 3 3 3 1)(hxhxhxhxxxh 01 2 2 3 3 4 4 24 1)(gxgxgxgxgxxxxg 第31 页 2021-7-13Department of Electronics and Information, NCUT Song Peng (5) 循环码的监督多项式和

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

37、的监督多项式和监督矩阵循环码的监督多项式和监督矩阵 循环码监督矩阵的构成循环码监督矩阵的构成 由式由式 (8.2.2) 可见，监督矩阵的第一行是码的监督多项式可见，监督矩阵的第一行是码的监督多项式 h(x) 的系的系 数的数的反序排列，反序排列，第二、三、四行是第一行的移位；第二、三、四行是第一行的移位； 可用监督多项式的系数来构成监督矩阵：可用监督多项式的系数来构成监督矩阵： 其中其中h*(x) 表示表示 h(x) 的反多项式的反多项式 )3 . 2 . 8( 0001011 0010110 0101100 1011000 )( )( )( )( *3 *2 * * )3 , 7( xhx

38、xhx xxh xh HH 第33 页 2021-7-13Department of Electronics and Information, NCUT Song Peng (5) 循环码的监督多项式和监督矩阵循环码的监督多项式和监督矩阵 循环码监督矩阵的构成循环码监督矩阵的构成 (n,k) 循环码的监督矩阵：循环码的监督矩阵： 0011 1 0110 1100 )( )( )( 11 11 11 11 *1 * * ),( k k k k kn kn hh hh hh hh xhx xxh xh HH 第34 页 2021-7-13Department of Electronics and

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

40、Song Peng (1) 系统循环码构成系统循环码构成 信息向量信息向量：mm=(mk 1,mk2,m0) 信息多项式信息多项式：m(x)=mk 1xk 1+mk 2 xk 2+m0 码多项式码多项式的高次幂部分等于的高次幂部分等于 m(x)，即：，即： C(x)=cn 1xn 1+ cn kxn k+ cn k1xn k1 +c1x +c0 =xn k m(x)+q(x) （ （q(x)的次数的次数nk） 校验位多项式校验位多项式：q(x) 由于码多项式是生成多项式的倍式，所以：由于码多项式是生成多项式的倍式，所以： C(x)= xn km(x)+q(x)=a(x)g(x)0 （ （mod

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

42、式求码多项式：C(x)=xn km(x)+ ( xnkm(x) mod g(x) =xn km(x)+ q(x) 第37 页 2021-7-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 xxr xgxxxxxmx得得到到余余式式：，除除以以 于于是是码码多多项项式式为为： 1 )()()( 46

43、4 xxx xrxmxxC 第38 页 2021-7-13Department of Electronics and Information, NCUT Song Peng (1) 多项式加法电路多项式加法电路 (2) 多项式乘法电路多项式乘法电路 (3) 多项式除法电路多项式除法电路 第39 页 2021-7-13Department of Electronics and Information, NCUT Song Peng (1) 多项式加法电路多项式加法电路 多项式多项式 a(x)=anxn+an 1xn 1+a1x+a0 表示的是时间序列 表示的是时间序列a a=(an,an 1,a

44、1,a0)，因此多项式的计算表现为对时间序列的操作； ，因此多项式的计算表现为对时间序列的操作； 对二进制多项式系数的基对二进制多项式系数的基 本操作为模本操作为模 2 加和模加和模 2 乘；乘； 电路图运算符号的意义：电路图运算符号的意义： 第40 页 2021-7-13Department of Electronics and Information, NCUT Song Peng (1) 多项式加法电路多项式加法电路 A(x) 与与 B(x) 的相加电路的相加电路 第41 页 2021-7-13Department of Electronics and Information, NCUT

45、 Song Peng (2) 多项式乘法电路多项式乘法电路 多项式乘以多项式乘以 x 等价为时间序列等价为时间序列 a a 延迟一位；延迟一位； 多项式多项式 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-7-13Department of Electronics and Informa

46、tion, NCUT Song Peng (2) 多项式乘法电路多项式乘法电路 多项式多项式乘法电路：乘法电路： 第43 页 2021-7-13Department of Electronics and Information, NCUT Song Peng (3) 多项式除法电路多项式除法电路 当当 g(x) =1，多项式，多项式 a(x) 模模 g(x) 的余式为的余式为 0，电路如图所示。，电路如图所示。 第44 页 2021-7-13Department of Electronics and Information, NCUT Song Peng (3) 多项式除法电路多项式除法电路

47、当当 g(x)是单向式是单向式 g(x)=xk， a(x) 模模 g(x) 的余式的次数小于的余式的次数小于 k，进入，进入 电路的输入顺序为电路的输入顺序为 an,an 1,a1,a0。 。a(x)ak 1xk 1+ak 2xk 2+a1x+a0 (mod xk) 运算电路如图所示。运算电路如图所示。 第45 页 2021-7-13Department of Electronics and Information, NCUT Song Peng (3) 多项式除法电路多项式除法电路 由于由于 xk1 mod(x+1), k=0,1,2,。若。若 a(x) 的次数为的次数为 n，则：，则： a

48、(x) = an 1+an2+a1+a0（ （mod(x+1)） q0（mod 2） 运算电路如图所示：运算电路如图所示： 第46 页 2021-7-13Department of Electronics and Information, NCUT Song Peng (3) 多项式除法电路多项式除法电路 同样由长除法得：同样由长除法得： 运算电路如图所示：运算电路如图所示： ni i i ni i i ni i i ni i i aqaq xqqaaxa 5 , 3 , 1 1 4 , 2 , 0 0 2 10 5 , 3 , 14 , 2 , 0 )1(mod()( 其其中中： 第47 页

49、 2021-7-13Department of Electronics and Information, NCUT Song Peng (3) 多项式除法电路多项式除法电路 多项式多项式 a(x) 模模 (x2+x+1) 的运算电路如图所示：的运算电路如图所示： 第48 页 2021-7-13Department of Electronics and Information, NCUT Song Peng (3) 多项式除法电路多项式除法电路 一般的多项式模一般的多项式模 g(x)=grxr+gr 1xr 1+g1x+g0 的运算电路如图所 的运算电路如图所 示。示。 移位寄存器初态全为移位寄

50、存器初态全为0； 当当 a(x) 输入完后，移位寄存器内容输入完后，移位寄存器内容 (qr 1, , q1, q0) 就是余式： 就是余式： q(x)=qr 1xr 1+ qr 2xr 2+ +q1x+q0 a(x) (mod g(x) 第49 页 2021-7-13Department of Electronics and Information, NCUT Song Peng (3) 多项式除法电路多项式除法电路 多项式除法电路的构造多项式除法电路的构造 q 多项式除法电路是一个由除式（这里就是生成多项式多项式除法电路是一个由除式（这里就是生成多项式 g(x)） g(x)=gn kxn k

51、+gn k1xn k1+g1x+g0 所确定的 所确定的反馈移位寄存器。反馈移位寄存器。 q 除法电路的构造方法除法电路的构造方法 l 移位寄存器的级数等于除式的次数移位寄存器的级数等于除式的次数 nk； l 移位寄存器的反馈抽头，由除式的各项系数移位寄存器的反馈抽头，由除式的各项系数 gi(i=0,1,nk) 决定：决定： 当某个抽头当某个抽头=0时，对应的反馈断开；时，对应的反馈断开； 当某个抽头当某个抽头=1时，对应的反馈接通。时，对应的反馈接通。 完成除法所需的移位次数等于被除式的次数加完成除法所需的移位次数等于被除式的次数加1。 第50 页 2021-7-13Department o

52、f Electronics and Information, NCUT Song Peng (3) 多项式除法电路多项式除法电路 多项式除法电路举例多项式除法电路举例 q 利用除法电路完成两个多项式除法运算，求其余式的过程和将利用除法电路完成两个多项式除法运算，求其余式的过程和将 两个多项式进行长除运算是完全一致的；两个多项式进行长除运算是完全一致的； q (x5+x2)(x4+x3+x +1) 的长除运算过程：的长除运算过程： )(1 1 )( )( )( )(1 1 3 34 4 245 2534 第二余式第二余式 第一余式第一余式 除式除式 被除式被除式 商式商式 x xxx xx xx

53、xx x xxxxx 第51 页 2021-7-13Department of Electronics and Information, NCUT Song Peng (3) 多项式除法电路多项式除法电路 多项式除法电路举例多项式除法电路举例 q(x5+x2)(x4+x3+x +1) 的长除运算过程：的长除运算过程： l每做一次除法运算，被除式（或前次除法的余式）的首项被抵每做一次除法运算，被除式（或前次除法的余式）的首项被抵 消，因而除法电路中每做一次除法运算，最高项就移到寄存器消，因而除法电路中每做一次除法运算，最高项就移到寄存器 之外而丢掉；之外而丢掉； 除式除首项外的其它各项系数都要加

54、到被除式或前次运算的余除式除首项外的其它各项系数都要加到被除式或前次运算的余 式中去，而除法电路的反馈正是按除式的规律连接的，恰好完式中去，而除法电路的反馈正是按除式的规律连接的，恰好完 成所需的加法运算。成所需的加法运算。 第52 页 2021-7-13Department of Electronics and Information, NCUT Song Peng (3) 多项式除法电路多项式除法电路 多项式除法电路举例多项式除法电路举例 q (x5+x2)(x4+x3+x +1) 运算电路工作过程：运算电路工作过程： 各级预先清零，被除式系数由移位寄存器第一级输入，经各级预先清零，被除式

55、系数由移位寄存器第一级输入，经 4 次次 移位后，最高项的系数到达移位寄存器右端出现反馈信号；移位后，最高项的系数到达移位寄存器右端出现反馈信号； 第一次对被除式作除法，下一个移位脉冲加入时，被除式首项第一次对被除式作除法，下一个移位脉冲加入时，被除式首项 x5 移出寄存器，相当于首项被抵消，反馈信号按除式规律与被除移出寄存器，相当于首项被抵消，反馈信号按除式规律与被除 式相应项进行式相应项进行模模 2 加加，移位寄存器新的内容即为第一余式；，移位寄存器新的内容即为第一余式； 第53 页 2021-7-13Department of Electronics and Information, N

56、CUT Song Peng (3) 多项式除法电路多项式除法电路 多项式除法电路举例多项式除法电路举例 q (x5+x2)(x4+x3+x +1) 运算电路工作过程：运算电路工作过程： 第一余式的首项第一余式的首项 x4 的系数到达电路的末级，出现反馈信号，准的系数到达电路的末级，出现反馈信号，准 备作第二次除法，当下一个移位脉冲加入时，第一余式的首项移备作第二次除法，当下一个移位脉冲加入时，第一余式的首项移 出寄存器被丢掉，反馈信号又把除式出寄存器被丢掉，反馈信号又把除式(除首项外除首项外)加到第一余式，得加到第一余式，得 到第二余式（即所求余式）；到第二余式（即所求余式）； 为了使被除式全

57、部移入寄存器，除法求余所需要的移位次数等为了使被除式全部移入寄存器，除法求余所需要的移位次数等 于被除式次数加于被除式次数加 1。 第54 页 2021-7-13Department of Electronics and Information, NCUT Song Peng (3) 多项式除法电路多项式除法电路 多项式除法电路举例多项式除法电路举例 q 表表 8.4.1 列出了电路的运算过程列出了电路的运算过程 第55 页 2021-7-13Department of Electronics and Information, NCUT Song Peng 9.5.1 非系统码编码电路非系统码

58、编码电路 9.5.2 系统码编码电路系统码编码电路 (1) 系统码编码的基本原理系统码编码的基本原理 (2) 用用 (nk) 级移位寄存器实现的编码电路级移位寄存器实现的编码电路 (3) 用用 k 级移位寄存器实现的编码电路级移位寄存器实现的编码电路 第56 页 2021-7-13Department of Electronics and Information, NCUT Song Peng 循环码码多项式是生成多项式的倍式。循环码码多项式是生成多项式的倍式。 非系统编码电路非系统编码电路/循环码乘法编码电路循环码乘法编码电路 q 输入输入 a(x)=m(x)， m(x)的次数的次数 k q

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

60、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-7-13Department of Electronics and Informat