信息论与编码补充循环码.ppt

《信息论与编码补充循环码.ppt》由会员分享，可在线阅读，更多相关《信息论与编码补充循环码.ppt（60页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、信息论与编码补充循环码1现在学习的是第1页，共60页内容提要循环码是线性分组码中一个重要的子类。将介绍循环码的基本概念以及循环码的多项式描述方法；循环码的基本定理及其矩阵描述；简单的循环码的编译码方法及其实现电路。 2现在学习的是第2页，共60页多项式的引入多项式的引入 如果将码字描述成n阶多项式的形式，A(x)= an-1xn-1+an-2xn-2 +an-3xn-3+ +a2x2+a1,x+a0，则循环算法就可以描述为L(A(x)=xA(x) mod (xn-1) 便于描述：对任何一个多项式D(x)，有D(x)A(x) mod (xn-1)为许用码字，这里并没有限定D(x)的幂次，但可以肯

2、定的一点是不同的D(x)A(x) mod (xn-1)是有限的，其个数由A(x)决定，这也决定了码集的冗余度和纠错能力，什么样的A(x)可以得到什么样的冗余度？哪些A(x)是等价的？ 复习几个概念复习几个概念:同余、剩余类同余、剩余类;群群;环环;域域现在学习的是第3页，共60页同余和剩余类同余同余：若整数a和b被同一正整数m除时，有相同的余数，则称a、b关于模m同余，记为)(mod mba 剩余类(Residue)：给定正整数m，可将全体整数按余数相同进行分类，可获得m个剩余类，分别用1, 1 , 0mbabababa,现在学习的是第4页，共60页群(Group)的定义 设设G是一个非空集合

3、，并在是一个非空集合，并在G内定义了一种代数内定义了一种代数运算运算 “ 。”，若满足：，若满足：Gba,1) 封闭性。对任意，恒有GbaGcba,2) 结合律。对任意，恒有cbacba3) G中存在一恒等元e,对任意Ga，使aaeea4) 对任意Gaeaaaa11，存在a的逆元Ga1，使则称G构成一个群。若加法，恒等元用0表示，若为乘法，恒等元称为单位元现在学习的是第5页，共60页环环(Ring)的定义的定义 非空集合非空集合R中，若定义了两种代数运算加和乘，中，若定义了两种代数运算加和乘，且满足：且满足： 1) 集合集合R在加法运算下构成阿贝尔群在加法运算下构成阿贝尔群 2) 乘法有封闭性

4、乘法有封闭性 3) 乘法结合律成立，且加和乘之间有分配律乘法结合律成立，且加和乘之间有分配律阿贝尔群，又称交换群或可交换群，是这样一类群 (G, *)：对任意 a，b 属于 G，满足 a * b = b * a。阿贝尔群以挪威数学家尼尔斯阿贝尔命名。现在学习的是第6页，共60页子环、理想和主理想子环：若环R中的子集S，在环R中的定义的代数运算也构成环，则称S为R的子环。 理想：S是R的一个子环，若S中的元素由某几个元素及其所有可能的倍数构成，则S是一个理想. 主理想：若理想中的元素由一个元素的所有倍数及其线性组合生成，则称这个理想为主理想。现在学习的是第7页，共60页 多项式多项式 f(x)=

5、fnxn+ fn-1xn-1+ f1x+f0piFf 其中i=0,1,n，该多项式称为域Fp上的多项式 多项式次数 degf(x) 系数不为零的x的最高次数称为多项式f(x)的次数 首一多项式 最高次数的系数为1的多项式有关多项式的几个概念现在学习的是第8页，共60页 既约多项式 设f(x)是次数大于零的多项式，若除常数和常数与本身的乘积以外，再不能被域Fp上的其他多项式整除，则称f(x)为域Fp上的既约多项式 多项式的因式分解问题、根的问题有关多项式的几个概念现在学习的是第9页，共60页f(x)=fnxn+ fn-1xn-1+ f1x+f0piFf g(x)=gnxn+ gn-1xn-1+

6、g1x+g0piFg 若对所有i, fi=gi, 则f(x)=g(x)多项式加法f(x)+g(x)=(fn + gn)xn+ (fn-1 + gn-1)xn-1+ (f1 + g1)x+(f0 + g0)多项式乘法结论：按上述定义的加法和乘法运算，Fpx构成一个具有单位元、无零因子的可换环.多项式的加法和乘法现在学习的是第10页，共60页定义定义：以一个Fp上的多项式f(x)=fnxn+ fn-1xn-1+ f1x+f0为模的剩余类全体构成一个多项式剩余类环 Fp上的所有次数小于n-1的多项式构成n次多项式的剩余类全体 xbxaxbxa xbxaxbxa剩余类之间的加法和乘法运算规则多项式剩余

7、类环现在学习的是第11页，共60页有限域GF(2)上的运算定义12现在学习的是第12页，共60页 1、GF(2)上的多项式 f(x)=x2+1的剩余类全体为： 1, 1 , 0 xx 2、GF(2)上的多项式 f(x)=x2+x+1的剩余类全体为： 1, 1 , 0 xx对所定义的加法和乘法运算，前者构成剩余类环，后者构成域.结论：若n次首一多项式f(x)在域Fp上既约，则f(x)的剩余类环构成一个有pn个元素的有限域.Examples现在学习的是第13页，共60页两个结论两个结论 多项式环多项式环Fpx的一切理想均是主理想的一切理想均是主理想 多项式剩余类环多项式剩余类环Fpx/f(x)中的

8、每一个理想都是中的每一个理想都是主理想。主理想。现在学习的是第14页，共60页设一个（n，k）线性分组码C，如果它的任一码字的每一次循环移位都还是C的一个码字，则称C是循环码。011(1)102(2)213:(,)(,)(,)nnnnnnvvvvCvvvvvvvvC由于循环码是线性分组码，所有这些具有循环关系的码字的全体构成了n维矢量空间中具有循环特性的k维子空间。15现在学习的是第15页，共60页 将任一码字中的7个码元排在一个圆周上，则从圆周的任一码元开始，按顺时针方向移动一周，都将构成该码的一个码字。这就是循环码的由来。（见图） 16图 （7，4）汉明码的码字循环图1001110:010

9、0111:1010011:1101001:1110100:0111010:0011101:141312111098c cc cc cc cc cc cc c第二循环1000101:1100010:0110001:1011000:0101100:0010110:0001011:7654321c cc cc cc cc cc cc c0000000:15c c第一循环1111111:16c c16现在学习的是第16页，共60页1循环码的特点：（1）它是线性分组码，其数学模型应具有线性特性；（2）具有循环特性。故循环码的数学模型必须能兼具线性和循环特性多项式描述。2线性分组码的多项式描述字：1110

10、110)(),(nnnxrxrrxrrrrr字多项式码字：1011011(,)( )nnnvv vvv xvv xvx码字多项式对于线性分组码C，可以表示成码字多项式构成的集合：1011011( )(,)nnnCC xvv xvxv vvC17现在学习的是第17页，共60页3循环特性的表示以前面的（7，3）循环码为例：（任取一码字）4211110100 xxx移一位移两位移三位)1 (011101042532xxxxxxxx)1 (00111014226432xxxxxxxx7543423543)1 (11001110 xxxxxxxxxxx此时：7 n-1 = 6，超出了n=7的矢量空间。要

11、求：75435431xxxxxxx则： ，即017x17x18现在学习的是第18页，共60页下面用 去除 ，得余17x7543xxxx5431xxx对于上面第三次移位结果，可重新表示如下：) 1mod()1 (110011107423543xxxxxxxx) 1mod()1 (01001117424654xxxxxxxxx) 1mod()1 (110100117425652xxxxxxxx) 1mod()1 (11101001742663xxxxxxxx) 1mod()1 (11110100742742xxxxxxxx结论：如果将一个循环码的某一非零码字用码多项式表示出来，那么其他的非零码字多

12、项式就可以用这个码字多项式（或码字多项式的和）乘上x的一个幂，再求（xn+1）的余得到 。说明：一个码字的移位最多能得到n个码字，因此“循环码字的循环仍是码字”并不意味着循环码集可以从一个码字循环而得，还应包含码字的一些线性组合。19现在学习的是第19页，共60页 设c（cn-1 cn-2 c1 c0）是（n，k）循环码的一个码字，则与其对应的多项式 c (x)cn-1xn-1cn-2xn-2c1xc0 称为码字c的码字多项式（或码多项式）。 如果c（cn-1 cn-2 c1 c0）是（n，k）循环码的一个码字，则c (1)（cn-2 c1 c0 cn-1）也是该循环码的一个码字。这就是说c

13、(x)cn-1xn-1cn-2xn-2c1xc0 和 c (1) (x)cn-2xn-1c1x2c0 xcn-1都是（n，k）循环码的码字多项式。 循环码的多项式描述20现在学习的是第20页，共60页比较c(x)和c (1) (x)后可得c (1) (x)x c (x), mod xn1 以及 c(i) (x)xic (x) （i1,2,n1）, mod xn+1 定理 在以多项式xn+1为模的剩余类全体所构成的n维线性空间Vn中，其一个子空间Vn,k是一个循环子空间（循环码）的充要条件是：Vn,k是一个理想。 一个（n，k）循环码的码字多项式都是模xn+1运算下多项式剩余类环中的一个理想，而

14、且一定是一个主理想子环。反之，多项式剩余类环的一个主理想子环也一定生成一个循环码。 21现在学习的是第21页，共60页1定义：若g(x)是一个(n-k)次多项式，且是(xn+1)的因式，则由g(x)可以生成一个（n，k）循环码，g(x)称为该循环码的生成多项式。（1）GF(2)上的（n，k）循环码中，存在着一个次数为(n-k)的首一码多项式g(x)（首一：多项式最高幂次项系数 gn-k=1 ） knknxgxgxggxg2210)(（gn-k=1）使得所有码多项式都是g(x)的倍式，即：( )( )( )v xu xg x且所有小于n次的g(x)的倍式都是码多项式。故循环码完全由它的生成多项式

15、确定。22现在学习的是第22页，共60页（2）（n，k）循环码的生成多项式g(x)一定是(xn+1)的因子，即) 1()(nxxg)()(1xhxgxn或写成相反，如果g(x)是xn+1的n-k次因子，则g(x)一定是（n，k）循环码的生成多项式。生成多项式不唯一。2（n，k）循环码的构造（1）对(x n + 1)做因式分解，找出(n k)次因式；（2）以该(n k)次因式为生成多项式g(x)与不高于k 1次信息多项式u(x)相乘，即得到对应消息序列的码多项式。 23现在学习的是第23页，共60页【例】一个长度n = 7的循环码的构造方法。（1）对x 7 + 1作因式分解) 1)(1)(1(1

16、3237xxxxxx故x 7 + 1有如下因式：一次因式：x1三次因式：3321,1xxxx四次因式：六次因式：432342321)1)(1 (1)1)(1 (xxxxxxxxxxxx654323321)1)(1 (xxxxxxxxxx（一个）（两个）（一个）（两个）24现在学习的是第24页，共60页n k = 1，k = 6，生成一种（7，6）循环码；n k = 3，k = 4，生成两种（7，4）循环码；n k = 4，k = 3，生成两种（7，3）循环码；n k = 6，k = 1，生成一种（7，1）循环码；例：要得到一（7，4）循环码，可选n k = 3次多项式1 + x2 + x3或1

17、 + x +x3 为生成多项式：以g（x）= 1 + x2 + x3为例，（信息位长度为4）设信息多项式为：332210)(xuxuxuuxu则：循环码编码后的码多项式为：23230123( )( ) ( )()(1)v xu x g xuu xu xu xxx（2）若以n - k次因式作为生成多项式，可供选择的有25现在学习的是第25页，共60页例：2)()0110(xxxuu223235( )( ) ( )()(1)(0111010)v xu x g xxxxxxxxxv对于上述（7，4）循环码，有4个信息位，对应有16个信息序列，利用16个信息序列多项式与生成多项式的乘法运算，可得全部（

18、7，4）循环码得16个码字，如表： 信息位码字信息位码字信息位码字信息位码字00010010010010000111111010110001011001011001011001011000011000111000101000101001101101100111110010101101000111010111010111010011010011010011010011110011100000000000011011111111循环组1循环组2循环组3循环组426现在学习的是第26页，共60页任何码字的循环移位仍是码字，并非由一个码字循环移位可以得到所有码字，上述（7，4）码的码集由4组码字循环构

19、成。 27现在学习的是第27页，共60页（n，k）循环码是n维线性空间一个具有循环特性的k维的子空间，故（n，k）循环码的生成矩阵可用码空间中任一组k个线性无关的码字构成，即k个线性无关的码字构成（n，k）循环码的基底，基底不唯一。 如何得到k个线性无关的码字？方法：当循环码的生成多项式g（x）给定后，可以取g（x）本身加上移位k 1次所得到的k 1码字作为k个基底，即：)(,),(),(1xgxxxgxgk构成基底若：knknxgxgxggxg2210)(则：112110124231202132210)()()(nknkkkkknknknknxgxgxgxgxgxxgxgxgxgxgxxgx

20、gxgxgxxg28现在学习的是第28页，共60页各多项式对应的矢量分别为：个kgggxgxgggxxggggxgknkknkn), 0, 0, 0()()0, 0, 0()()0, 0, 0,()(1011010这k个矢量是线性无关的，且由g（x）循环移位得到，故都是码字，由它们构成一个kn的矩阵，它们就是循环码的生成矩阵。 knknkngggggggggG10101000000000029现在学习的是第29页，共60页【例】（7，4）循环码：4,1)(3kxxxg当一个循环码的生成矩阵确定后，其编码规则为：vu G11010000110100(1010)(1010)(1110010)001

21、10100001101uv如：)0001101()()0011010()()0110100()()1101000()(32xgxxgxxxgxg0001101001101001101001101000G30现在学习的是第30页，共60页11011( )( ) ( )( )n kn kn knkxu xu xu xuxa x g xb x 1)(onxuxknknxg)(o1)(oknxbo（ 次数）设：1110)(knknxbxbbxb则：111101110)()()()(nkknknknknknxuxuxuxbxbbxuxxbxgxa由上述方法作出的生成矩阵所编出的码不是系统形式，如何得到系

22、统形式的循环码？ 1系统循环码的编码：设1110)(kkxuxuuxu用x n k 和u（x）相乘，再除以g (x)31现在学习的是第31页，共60页a(x)g(x)是g(x)的一个倍式，则它是一个码多项式，对应的码矢量为：011011(,)n kkvbbbuuu 111101110)()()()(nkknknknknknxuxuxuxbxbbxuxxbxgxa码矢量为系统形式的码字，信息位在尾部。 系统码的编码步骤： (1) 将k个消息位按升幂排列的次序写成消息多项式 u（x） ； (2) 用x n k 乘以u（x）得到一个次数 的多项式； (3) 用生成多项式g（x）除x n k u（x）

23、得余 b（x）（一致校验元）； (4) 联合b( x )和x n k u( x )得到系统码多项式 v(x)= b( x )+ x n k u( x )； (5) 将码多项式转换为码字。(1)n32现在学习的是第32页，共60页【例】（7，4）循环码：31)(xxxg求的系统码字。)1010(u，【解】21)(xxu，n7，k4（1）5323)1 ()(xxxxxuxkn（2）2)(xxb232235( )( )( )(1)n kv xb xxu xxxxxxx（3）(001 1010 )v （4）33现在学习的是第33页，共60页2系统码的生成矩阵（1）由生成矩阵做初等行变换，将其变为 形式

24、，即为系统形式的生成矩阵（单位阵在后，信息位在尾部）。kknkIP,，求系统形式的生成矩阵。 【例】（7，4）循环码：31)(xxxg 000110100101110100011100011001011100010111010001110001101101000101000101000111000110241413rrrrrrG（2）分别求g（x）除 的余式（记为） ，由余式对应的矢量作行矢量构成的kn-k的分块矩阵 P 联合kk的单位阵 I 就构成系统形式的生成矩阵： 1,kknknknxxxxx)(,),(),(110 xpxpxpkkknkknkkkknknIPpppppppppG,10

25、00100011, 11 , 10 , 11, 11 , 10, 11, 01 , 00 , 034现在学习的是第34页，共60页，求系统形式的生成矩阵。 【例】（7，4）循环码：31)(xxxg2322210233322232331)(1)()(1)()1 ()() 1()1 ()() 1()()()1 ()(xxpxxxpxxxpxxpxxgxxxxxxxgxxxxxxxgxxxxgx0001101001011101000111000110G35现在学习的是第35页，共60页一般情况下，多项式xn+1可因式分解为xn+1 = g (x) h (x)g (x) （n，k）循环码的生成多项式，

26、knxg)(oh (x) （n，k）循环码的一致校验多项式，kxh)(o在因式分解中，g (x)和h (x)处于同等地位，既可以用g (x)去生成一个循环码，也可以用h (x)去生成一个循环码。 设由g (x)生成的码为C，在由h (x)生成的码就是C的对偶码C。循环码C的对偶码C的基底由)(,),(),(1xhxxxhxhkn构成。36现在学习的是第36页，共60页设kkxhxhxhhxh2210)(则：个knhhhxhxhhhxxhhhhxhkknkk), 0, 0, 0()()0, 0, 0()()0, 0, 0,()(1011010将上述矢量按逆序排列作为一个（n-k）n矩阵的行矢量，

27、则该矩阵就是码C的校验矩阵。)()(0000000001010101xhxhxhhhhhhhhhHknkkkkkk37现在学习的是第37页，共60页【例】（7，4）循环码：)1)(1 (14237xxxxxx4231)(,1)(xxxxhxxxg则：C的基底（n-k-1=2）6432253242)()(1)(xxxxxhxxxxxxxhxxxxh111010001110100011101H38现在学习的是第38页，共60页 系统形式的校验矩阵（1）对非系统形式的校验矩阵作初等行变换，变成 I n-k，PT 的形式；（2）分别求h（x）除 的余式（记为） ，由余式对应的逆矢量可得到系统形式的校验

28、矩阵：kkknkknxxxxx,21)(,),(),(021xrxrxrknkn0, 02, 01, 00, 22, 21, 20, 12, 11, 1100010001rrrrrrrrrHkkknkknkknknkknkkn（3）T,PIHIPGknkknk39现在学习的是第39页，共60页【例】（7，4）循环码：)1)(1 (14237xxxxxx4231)(,1)(xxxxhxxxg 11101000111010110100111101000111010001110131 rrH（1）（2）k = 4，n k 1 = 2（3）1000101010011100101100001011101

29、1000010110000101100001011214, 13rrrrrG)1 ()()()()1 ()()1 (243243242xxxhxxxxxxhxxxxxhxxx111010001110101101001H40现在学习的是第40页，共60页 循环码是线性分组码的一个子类，因此循环码可以按一般线性分组码利用常用的组合逻辑电路来实现编码。但对于线性分组码，当其信息位分组长度较长，编码位数较多时，其编码电路非常复杂。 由于循环码具有循环特性，其编码器通常用简单的具有反馈连接的移位寄存器就可以实现，大大简化了编码器的复杂度。 利用具有反馈连接的移位寄存器实现的循环码编码电路，实际上是多项式

30、运算电路。首先研究多项式运算电路。 41现在学习的是第41页，共60页 设0111)(axaxaxaxakkkk0111)(bxbxbxbxbrrrr)()()()(xrxbxqxa（被除式）（除式）q(x) 商，r(x) 余除法电路：42现在学习的是第42页，共60页（1）除法电路的结构由除式b（x）决定；（2）组成：由r个存储单元组成r级移位寄存器（D0Dr-1） bi：常乘器，（bi = 1，输出输入；bi = 0，输出0） 当bi = 1，对应支路连通（直通）； 当bi = 0，对应支路断开，对应的模2加法器可去掉。 故：电路有r个移位寄存器，最多r+1个常乘器，最多r个模2加法器。说

31、明：43现在学习的是第43页，共60页（3）工作原理简述： 电路清零，被除式系数按高次到低次依次进入电路（ak首先进入），r次移位后，移存器自右至左内容为：（a k，a k-1，.，a k-r+1） 第 r + 1次移位后，输出商的最高次位的系数（a k b r 或a k b r-1），并反馈到前面作模2加运算后存入各级寄存器中，以后每次移位输出商的对应次位的系数并反馈回去。 依次类推，经过 k + 1次移位后，完成整个除法运算，最后输出商常数项系数，此时移存器中的内容就是余式r（x）各次项对应的系数（高位寄存器对应高次项系数）。 44现在学习的是第44页，共60页1)(34xxxa1)(3x

32、xxb【例】134 xx13 xxxxx241x123xxx13 xx)(2xrx 工作过程: (r=3)节拍输入D0D1D2输出清零010000111000201100r次300110r1次411111（x）k1次5-0011（x0）1)( xxq2)(xxr45现在学习的是第45页，共60页1基于生成多项式g（x）的编码器（nk级编码器）编码器电路的结构由生成多项式决定，生成多项式g（x）的最高次数为n-k，故编码器有n-k级移存器，故称n-k级编码器。对于循环码的系统编码，首先要得到u(x) xn-k 除以g(x)的余式p(x)，再组合成系统码，即：( )( ) ( )( )( )( )

33、( )n kn ku x xq x g xp xv xp xu x x对于除法电路：一方面我们可以得到商，还可以得到余式。对于系统码编码我们可以先输出信息位，再输出余式（校验位）就可以得到系统码，另外由于被除式为u(x)x n-k，u(x)应从n-k级移存器的最前端输入。 46现在学习的是第46页，共60页编码过程：（1）门打开，k接“1”，消息数据u k-1 , . u0移入电路，并同时送入信道，一旦k个消息全部移入电路，移存器中的n - k个数据就构成了余式的系数；（2）门关，断开反馈连接，k接“2”；（3）移出移存器中的数据 (校验元)，并送入信道，与k个信息位组成码字。47现在学习的是

34、第47页，共60页【例】（7，4）循环码，31)(xxxg若：233323323356(1011)( )1( )(1)(1) ( )1( )1( )1(1001011)uu xxxu x xxxxxxxg xv xx g xxxxv 48现在学习的是第48页，共60页编码过程：（k4）节拍输入D0D1D2输出门开，k10100011110120101131100041001门关，k250100600107000149现在学习的是第49页，共60页2基于校验多项式h（x）的编码器（k级编码器）编码器电路的结构由校验多项式决定，生成多项式h(x)的最高次数为k，故编码器有k级移存器，故称 k级编码

35、器。编码器电路编码过程（1）门1打开，门2关闭，k位消息数据u0，u1，. ，uk-1移入电路，并同时送入信道；（2）k位消息全部移入，门1关，门2开； （3）以后的每次移位产生一个校验元并送入信道，直到nk个校验元全部产生并送入信道为止。然后门2关，门1开，准备下一组消息编码；50现在学习的是第50页，共60页【例】（7，4）循环码，31)(xxxg421)(xxxxhk4级编码器编码过程输入节拍D0D1D2D3输出门1开，门2关100000111000102010001310101411011门1关，门2开50110060011070001051现在学习的是第51页，共60页3两种编码器的

36、比较（1）基于g（x）的编码器为nk级编码器，需要nk级移存器； 基于h（x）的编码器为k级编码器，需要k级移存器。（2）当nk k时，采用k级编码器需要资源少。 52现在学习的是第52页，共60页和线性分组码一样，循环码译码步骤分三步：（1）计算接收多项式r (x)的伴随多项式s (x)；（2）根据s (x)找出相应错误图样多项式e (x)；（3）将e (x)和r (x)模2加，得到译码输出v (x) 。 1伴随式及计算设接收多项式为r (x)，码多项式为v (x)，错误图样多项式为e (x)，则( )( )( )r xv xe x用生成多项式g（x）除r（x），得( )( )( ) ( )

37、 ( )( ) ( )g xg xg xr xv xe xe x（求余运算）53现在学习的是第53页，共60页【定理】设g (x)是(n，k)系统循环码的生成多项式，接收字多项式为 r (x)，对应错误图样为e (x), 则)()()()(xgxgxexr且它们的系数就是该接收字的伴随式。即)()()()()(xgxgxexrxss可见，循环码的伴随式计算电路就是一个接收多项式 r (x) 除以生成多项式g（x）的除法电路。电路初始状态为0，当r (x)全部移入后，移存器中的内容为伴随式多项式s (x)。54现在学习的是第54页，共60页2伴随式计算电路的性质由于码的循环结构，伴随式有个重要的

38、性质，用定理描述。【定理】设s (x)是r (x)的伴随式，则r (x)的循环移位 x r (x)的伴随式s(1) (x)是s (x)在伴随式计算电路中无输入时右移一位的结果，即： )(mod)()()1(xgxxsxs【推论】用生成多项式g (x)除x i s (x)所得余式s(i) (x)是r (x)经 i 次移位后r (i) (x)的伴随式。)(mod)()(i(i)xgxsxxs说明：把含有s (x)的伴随式移存器的输入门断开，移位一次就得到r (1) (x)的伴随式s (1) (x)，移位 i 次，就得到r (i) (x)的伴随式s (i) (x) 。 55现在学习的是第55页，共6

39、0页31)(xxxg)0010110(r)0001011()1(r【例】（7，4）循环码，计算对应的伴随式。伴随式计算电路计算过程：（开始时，移存器清零）节拍 输入S0S1S2节拍 输入S0S1S210000601112110070101s311108100s(1)400119010s(2)51011)100()0001011()101()0010110()1()1(srsr56现在学习的是第56页，共60页)()()(xgxrxs由356)1()1(245)()0001011()()0010110(xxxxrrxxxxrr245xxx13 xx12 xx34xx xxx241)()101(2

40、xxs235xxxxxx2313 xx356xxx13 xx123xxx45xx 235xxx)()100()1(xs346xxx234xxxxxx24xx 313 xx1计算电路性质的意义：对于在同一循环组中的接收字，只需计算一个接收字的伴随式，即可以通过移位来计算其他接收字的伴随式。57现在学习的是第57页，共60页普通(n,k)线性分组码的译码电路框图58现在学习的是第58页，共60页1组成：（三部分）（梅吉特：Meggit通用译码器）（1）一个n位的缓冲寄存器（2）组合逻辑电路（3）一个r位的伴随式计算电路2错误纠正过程（1）开始译码时，门开，移存器和伴随式计算电路清零，接收字r（x）

41、一方面送入n级缓存，一方面送入伴随式计算电路，形成伴随式。当n位数据接收完后，门关，禁止输入。59现在学习的是第59页，共60页（2）将伴随式输入错误图样检测电路，找出对应的错误图样。方法：当且仅当缓存器中最高位出错时，组合逻辑电路输出才为“1”，即，若检测电路输出为“1”，说明缓存中最高位的数据是错误的，需要纠正。这时输出的“1”同时反馈到伴随式计算电路，对伴随式进行修正，消除该错误对伴随式的影响（修正后为高位无错对应的伴随式）。（3）如高位无错误，组合电路输出“0”，高位无需纠正，然后，伴随式计算电路和缓存各移位一次，这是高位输出。同时，接收字第二位移到缓存最高位，而伴随式计算电路得到此高位伴随式，用来检测接收字的次高位，即缓存最右一位是否有错。如有错，组合电路输出“1”与缓存输出相加，完成第二个码元的纠错，如无错，则重复上述过程，一直译完一个码字为止。 60现在学习的是第60页，共60页