第八章-循环码课件.ppt

1、第八章第八章 循循 环环 码码2内容提要内容提要循环码是线性分组码中一个重要的子类。循环码是线性分组码中一个重要的子类。本章将介绍循环码的基本概念以及循环码的多项本章将介绍循环码的基本概念以及循环码的多项式描述方法；循环码的基本定理及其矩阵描述式描述方法；循环码的基本定理及其矩阵描述；简单；简单的循环码的编译码方法及其实现电路。的循环码的编译码方法及其实现电路。3设一个（设一个（n，k）线性分组码）线性分组码C，如果它的任一码字的每，如果它的任一码字的每一次循环移位都还是一次循环移位都还是C的一个码字，则称的一个码字，则称C是是循环码循环码。011(1)102(2)213:(,)(,)(,)n

2、nnnnnvvvvCvvvvvvvvC由于循环码是线性分组码，所有这些具有循环关系的码由于循环码是线性分组码，所有这些具有循环关系的码字的全体构成了字的全体构成了n维矢量空间中具有循环特性的维矢量空间中具有循环特性的k维子空间维子空间。4【例】（【例】（7，3）线性分组码）线性分组码1000110010001100101110001101H101110011100100111001G由：由：得得vu G由两组码字循环构成的循环码由两组码字循环构成的循环码。51循环码的特点：循环码的特点：（1）它是线性分组码，其数学模型应具有线性特性；）它是线性分组码，其数学模型应具有线性特性；（2）具有循环特

3、性。）具有循环特性。故循环码的数学模型必须能兼具线性和循环特性故循环码的数学模型必须能兼具线性和循环特性多项式描述。多项式描述。2线性分组码的多项式描述线性分组码的多项式描述字：字：1110110)(),(nnnxrxrrxrrrrr字多项式字多项式码字：码字：1011011(,)()nnnvv vvv xvv xvx码字多项式码字多项式对于线性分组码对于线性分组码C，可以表示成码字多项式构成的集合：，可以表示成码字多项式构成的集合：1011011()(,)nnnCC xvv xvxv vvC63循环特性的表示循环特性的表示以前面的（以前面的（7，3）循环码为例：（任取一码字）循环码为例：（任

4、取一码字）4211110100 xxx移一位移一位移两位移两位移三位移三位)1(011101042532xxxxxxxx)1(00111014226432xxxxxxxx7543423543)1(11001110 xxxxxxxxxxx此时：此时：7 n-1=6，超出了，超出了n=7的矢量空间。的矢量空间。要求：要求：75435431xxxxxxx则：则：，即，即017x17x7下面用下面用 去除去除 ，得余，得余17x7543xxxx5431xxx对于上面第三次移位结果，可重新表示如下：对于上面第三次移位结果，可重新表示如下：)1mod()1(110011107423543xxxxxxxx)

5、1mod()1(01001117424654xxxxxxxxx)1mod()1(110100117425652xxxxxxxx)1mod()1(11101001742663xxxxxxxx)1mod()1(11110100742742xxxxxxxx结论：结论：如果将一个循环码的某一非零码字用码多项式表示出来，那么其他如果将一个循环码的某一非零码字用码多项式表示出来，那么其他的非零码字多项式就可以用这个码字多项式（或码字多项式的和）的非零码字多项式就可以用这个码字多项式（或码字多项式的和）乘上乘上x的一个幂，再求（的一个幂，再求（xn+1）的余得到）的余得到。说明：说明：一个码字的移位最多能得

6、到一个码字的移位最多能得到n个码字，因此个码字，因此“循环码字的循环仍是循环码字的循环仍是码字码字”并不意味着循环码集可以从一个码字循环而得，还应包含码并不意味着循环码集可以从一个码字循环而得，还应包含码字的一些线性组合。字的一些线性组合。81定义：定义：若若g(x)是一个是一个(n-k)次多项式，且是次多项式，且是(x xn n+1)+1)的因式，则由的因式，则由g(x)g(x)可以可以生成生成一个（一个（n n，k k）循环码，）循环码，g(x)称称为该循环码的为该循环码的生成多项式生成多项式。（1）GF(2)上的（上的（n，k）循环码中，存在着一个次数为）循环码中，存在着一个次数为(n-

7、k)的首一码多项的首一码多项式式g(x)（首一：多项式最高幂次项系数首一：多项式最高幂次项系数 gn-k=1）knknxgxgxggxg2210)(（gn-k=1）使得所有码多项式都是使得所有码多项式都是g(x)的倍式，即：的倍式，即：()()()v xu xg x且所有小于且所有小于n n次的次的g(g(x x)的倍式都是码多项式。的倍式都是码多项式。故循环码完全由它的生成多项式确定。故循环码完全由它的生成多项式确定。9（2）（）（n，k）循环码的生成多项式）循环码的生成多项式g(x)一定是一定是(xn+1)的因子，即的因子，即)1()(nxxg)()(1xhxgxn或写成或写成相反，如果相

8、反，如果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)相相乘，即得到对应消息序列的码多项式。乘，即得到对应消息序列的码多项式。10【例】一个长度【例】一个长度n=7的循环码的构造方法。的循环码的构造方法。（1）对）对x 7+1作因式分解作因

9、式分解)1)(1)(1(13237xxxxxx故故x 7+1有如下因式：有如下因式：一次因式：一次因式：x1三次因式：三次因式：3321,1xxxx四次因式：四次因式：六次因式：六次因式：432342321)1)(1(1)1)(1(xxxxxxxxxxxx654323321)1)(1(xxxxxxxxxx（一个）（一个）（两个）（两个）（一个）（一个）（两个）（两个）11n 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，生

10、成一种（，生成一种（7，1）循环码；）循环码；例：例：要得到一（要得到一（7，4）循环码，可选）循环码，可选n k=3次多项式次多项式1+x2+x3或或1+x+x3 为生成多项式：为生成多项式：以以g（x）=1+x2+x3为例，（信息位长度为为例，（信息位长度为4）设信息多项式为：设信息多项式为：332210)(xuxuxuuxu则：循环码编码后的码多项式为：则：循环码编码后的码多项式为：23230123()()()()(1)v xu x g xuu xu xu xxx（2）若以）若以n-k次因式作为生成多项式，可供选择的有次因式作为生成多项式，可供选择的有12例：例：2)()0110(xxx

11、uu223235()()()()(1)(0111010)v xu x g xxxxxxxxxv对于上述（对于上述（7，4）循环码，有）循环码，有4个信息位，对应有个信息位，对应有16个信息序列，利用个信息序列，利用16个信息序列多项式与生成多项式的乘法运算，可得全部（个信息序列多项式与生成多项式的乘法运算，可得全部（7，4）循环码）循环码得得16个码字，如表：个码字，如表：信息位信息位码字码字信息位信息位码字码字信息位信息位码字码字信息位信息位码字码字000100100100100001111110101100010110010110010110010110000110001110001010

12、00101001101101100111110010101101000111010111010111010011010011010011010011110011100000000000011011111111循环组循环组1循环组循环组2循环组循环组3循环组循环组4任何码字的循环移位仍是码字，并非由一个码字循环移位可以得到所有任何码字的循环移位仍是码字，并非由一个码字循环移位可以得到所有码字，上述（码字，上述（7，4）码的码集由）码的码集由4组码字循环构成。组码字循环构成。13（n，k）循环码是）循环码是n维线性空间一个具有循环特性的维线性空间一个具有循环特性的k维的子空间，故维的子空间，故（n

13、，k）循环码的生成矩阵可用码空间中任一组）循环码的生成矩阵可用码空间中任一组k个线性无关的码字构成，个线性无关的码字构成，即即k个线性无关的码字构成（个线性无关的码字构成（n，k）循环码的基底，基底不唯一。）循环码的基底，基底不唯一。如何得到如何得到k个线性无关的码字？个线性无关的码字？方法：当循环码的生成多项式方法：当循环码的生成多项式g（x）给定后，可以取）给定后，可以取g（x）本身加上移位）本身加上移位k 1次所得到的次所得到的k 1码字作为码字作为k个基底，即：个基底，即：)(,),(),(1xgxxxgxgk构成基底构成基底若：若：knknxgxgxggxg2210)(则：则：112

14、110124231202132210)()()(nknkkkkknknknknxgxgxgxgxgxxgxgxgxgxgxxgxgxgxgxxg14各多项式对应的矢量分别为：各多项式对应的矢量分别为：个kgggxgxgggxxggggxgknkknkn),0,0,0()()0,0,0()()0,0,0,()(1011010这这k个矢量是线性无关的，且由个矢量是线性无关的，且由g（x）循环移位得到，故都是码字，由）循环移位得到，故都是码字，由它们构成一个它们构成一个kn的矩阵，它们就是循环码的生成矩阵。的矩阵，它们就是循环码的生成矩阵。knknkngggggggggG10101000000000

15、015【例【例】（7，4）循环码：）循环码：4,1)(3kxxxg当一个循环码的生成矩阵确定后，其编码规则为：当一个循环码的生成矩阵确定后，其编码规则为：vu G11010000110100(1010)(1010)(1110010)00110100001101uv如：如：)0001101()()0011010()()0110100()()1101000()(32xgxxgxxxgxg0001101001101001101001101000G1611011()()()()n kn kn knkxu xu xu xuxa x g xb x 1)(onxuxknknxg)(o1)(oknxbo（次数

16、）次数）设：设：1110)(knknxbxbbxb则：则：111101110)()()()(nkknknknknknxuxuxuxbxbbxuxxbxgxa由上述方法作出的生成矩阵所编出的码不是系统形式，如何得到系统形由上述方法作出的生成矩阵所编出的码不是系统形式，如何得到系统形式的循环码？式的循环码？1系统循环码的编码：系统循环码的编码：设设1110)(kkxuxuuxu用用x n k 和和u（x）相乘，再除以）相乘，再除以g(x)17a(x)g(x)是是g(x)的一个倍式，则它是一个码多项式，对应的码矢量为：的一个倍式，则它是一个码多项式，对应的码矢量为：011011(,)n kkvbbb

17、uuu 111101110)()()()(nkknknknknknxuxuxuxbxbbxuxxbxgxa码矢量为系统形式的码字，信息位在尾部。码矢量为系统形式的码字，信息位在尾部。系统码的编码步骤：系统码的编码步骤：(1)将将k个消息位按升幂排列的次序写成消息多项式个消息位按升幂排列的次序写成消息多项式 u（x）；(2)用用x n k 乘以乘以u（x）得到一个次数）得到一个次数 的多项式；的多项式；(3)用生成多项式用生成多项式g（x）除）除x n k u（x）得余）得余 b（x）（一致校验元）；）（一致校验元）；(4)联合联合b(x)和和x n k u(x)得到系统码多项式得到系统码多项式

18、 v(x)=b(x)+x n k u(x)；(5)将码多项式转换为码字。将码多项式转换为码字。(1)n18【例【例】（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）192系统码的生成矩阵系统码的生成矩阵（1）由生成矩阵做初等行变换，将其变为）由生成矩阵做初等行变换，将其变为 形式，即为系统形形式，即为系统形式的生成矩阵（单位阵在后，信息位在尾部）。式的生成矩阵

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

20、knknxxxxx)(,),(),(110 xpxpxpkkknkknkkkknknIPpppppppppG,1000100011,11,10,11,11,10,11,01,00,020，求系统形式的生成矩阵。，求系统形式的生成矩阵。【例【例】（7，4）循环码：）循环码：31)(xxxg2322210233322232331)(1)()(1)()1()()1()1()()1()()()1()(xxpxxxpxxxpxxpxxgxxxxxxxgxxxxxxxgxxxxgx0001101001011101000111000110G21一般情况下，多项式一般情况下，多项式xn+1可因式分解为可因式分

21、解为xn+1=g(x)h(x)g(x)（n，k）循环码的生成多项式，）循环码的生成多项式，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构成。构成。22设设kkxh

22、xhxhhxh2210)(则：则：个knhhhxhxhhhxxhhhhxhkknkk),0,0,0()()0,0,0()()0,0,0,()(1011010将上述矢量按将上述矢量按逆序逆序排列作为一个（排列作为一个（n-k）n矩阵的行矢量，则该矩矩阵的行矢量，则该矩阵就是码阵就是码C的校验矩阵。的校验矩阵。)()(0000000001010101xhxhxhhhhhhhhhHknkkkkkk23【例【例】（7，4）循环码：）循环码：)1)(1(14237xxxxxx4231)(,1)(xxxxhxxxg则：则：C的基底（的基底（n-k-1=2）6432253242)()(1)(xxxxxhxx

23、xxxxxhxxxxh111010001110100011101H24 系统形式的校验矩阵系统形式的校验矩阵（1）对非系统形式的校验矩阵作初等行变换，变成）对非系统形式的校验矩阵作初等行变换，变成 I n-k，PT 的形式；的形式；（2）分别求）分别求h（x）除）除 的余式（记的余式（记为）为），由余式对应的逆矢量可得到系统，由余式对应的逆矢量可得到系统形式的校验矩阵：形式的校验矩阵：kkknkknxxxxx,21)(,),(),(021xrxrxrknkn0,02,01,00,22,21,20,12,11,1100010001rrrrrrrrrHkkknkknkknknkknkkn（3）T,

24、PIHIPGknkknk25【例【例】（7，4）循环码：）循环码：)1)(1(14237xxxxxx4231)(,1)(xxxxhxxxg 11101000111010110100111101000111010001110131 rrH（1）（2）k=4，n k 1=2（3）10001010100111001011000010111011000010110000101100001011214,13rrrrrG)1()()()()1()()1(243243242xxxhxxxxxxhxxxxxhxxx111010001110101101001H26 循环码是线性分组码的一个子类，因此循环码可以按

25、一般线循环码是线性分组码的一个子类，因此循环码可以按一般线性分组码利用常用的组合逻辑电路来实现编码。但对于线性分组性分组码利用常用的组合逻辑电路来实现编码。但对于线性分组码，当其信息位分组长度较长，编码位数较多时，其编码电路非码，当其信息位分组长度较长，编码位数较多时，其编码电路非常复杂。常复杂。由于循环码具有循环特性，其编码器通常用简单的具有反馈由于循环码具有循环特性，其编码器通常用简单的具有反馈连接的移位寄存器就可以实现，大大简化了编码器的复杂度。连接的移位寄存器就可以实现，大大简化了编码器的复杂度。利用具有反馈连接的移位寄存器实现的循环码编码电路，实利用具有反馈连接的移位寄存器实现的循环

26、码编码电路，实际上是多项式运算电路。首先研究多项式运算电路。际上是多项式运算电路。首先研究多项式运算电路。27 设设0111)(axaxaxaxakkkk0111)(bxbxbxbxbrrrr)()()()(xrxbxqxa（被除式）（被除式）（除式）（除式）q(x)商，商，r(x)余余除法电路：除法电路：28（1）除法电路的结构由除式）除法电路的结构由除式b（x）决定；）决定；（2）组成：由）组成：由r个存储单元组成个存储单元组成r级移位寄存器（级移位寄存器（D0Dr-1）bi：常乘器，（：常乘器，（bi=1，输出输入；，输出输入；bi=0，输出，输出0）当当bi=1，对应支路连通（直通）；

27、，对应支路连通（直通）；当当bi=0，对应支路断开，对应的模，对应支路断开，对应的模2加法器可去掉。加法器可去掉。故：电路有故：电路有r个移位寄存器，最多个移位寄存器，最多r+1个常乘器，最多个常乘器，最多r个模个模2加法器。加法器。说明说明：29（3）工作原理简述：）工作原理简述：电路清零，被除式系数按高次到低次依次进入电路（电路清零，被除式系数按高次到低次依次进入电路（ak首先进入），首先进入），r次移位后，移存器自右至左内容为：（次移位后，移存器自右至左内容为：（a k，a k-1，.，a k-r+1）第第 r+1次移位后，输出商的最高次位的系数（次移位后，输出商的最高次位的系数（a k

28、 b r 或或a k b r-1），并），并反馈到前面作模反馈到前面作模2加运算后存入各级寄存器中，以后每次移位输出商的加运算后存入各级寄存器中，以后每次移位输出商的对应次位的系数并反馈回去。对应次位的系数并反馈回去。依次类推，经过依次类推，经过 k+1次移位后，完成整个除法运算，最后输出商常数次移位后，完成整个除法运算，最后输出商常数项系数，此时移存器中的内容就是余式项系数，此时移存器中的内容就是余式r（x）各次项对应的系数（高）各次项对应的系数（高位寄存器对应高次项系数）。位寄存器对应高次项系数）。301)(34xxxa1)(3xxxb【例【例】工作过程工作过程:(r=3)节拍节拍 输入输

29、入D0D1D2输出输出清零清零010000111000201100r次次300110r1次次411111（x）k1次次5-0011（x0）1)(xxq2)(xxr311基于生成多项式基于生成多项式g（x）的编码器（）的编码器（nk级编码器级编码器）编码器电路的结构由生成多项式决定，生成多项式编码器电路的结构由生成多项式决定，生成多项式g（x）的最高次数为）的最高次数为n-k，故编码器有，故编码器有n-k级移存器，故称级移存器，故称n-k级编码器级编码器。对于循环码的系统编码，首先要得到对于循环码的系统编码，首先要得到u(x)xn-k 除以除以g(x)的余式的余式p(x)，再组，再组合成系统码，

30、即：合成系统码，即：()()()()()()()n kn ku x xq x g xp xv xp xu x x对于除法电路：一方面我们可以得到商，还可以得到余式。对于系统对于除法电路：一方面我们可以得到商，还可以得到余式。对于系统码编码我们可以先输出信息位，再输出余式（校验位）就可以得到系统码，码编码我们可以先输出信息位，再输出余式（校验位）就可以得到系统码，另外由于被除式为另外由于被除式为u(x)x n-k，u(x)应从应从n-k级移存器的最前端输入。级移存器的最前端输入。32编码过程：编码过程：（1）门打开，）门打开，k接接“1”，消息数据，消息数据u k-1,.u0移入电路，并同时送入

31、信道，一旦移入电路，并同时送入信道，一旦k个消息全部移入电路，移存器中的个消息全部移入电路，移存器中的n-k个数据就构成了余式的系数；个数据就构成了余式的系数；（2）门关，断开反馈连接，）门关，断开反馈连接，k接接“2”；（3）移出移存器中的数据）移出移存器中的数据(校验元校验元)，并送入信道，与，并送入信道，与k个信息位组成码字。个信息位组成码字。33【例【例】（7，4）循环码，）循环码，31)(xxxg若：若：233323323356(1011)()1()(1)(1)()1()1()1(1001011)uu xxxu x xxxxxxxg xv xx g xxxxv 34编码过程：（编码过

32、程：（k4）节拍节拍输入输入D0D1D2输出输出门开，门开，k10100011110120101131100041001门关，门关，k2501006001070001352基于校验多项式基于校验多项式h（x）的编码器（）的编码器（k级编码器级编码器）编码器电路的结构由校验多项式决定，生成多项式编码器电路的结构由校验多项式决定，生成多项式h(x)的最高次数为的最高次数为k，故编码器有故编码器有k级移存器，故称级移存器，故称 k级编码器级编码器。编码器电路编码器电路编码过程编码过程（1）门）门1打开，门打开，门2关闭，关闭，k位消息数据位消息数据u0，u1，.，uk-1移入电路，并移入电路，并同时

33、送入信道；同时送入信道；（2）k位消息全部移入，门位消息全部移入，门1关，门关，门2开；开；（3）以后的每次移位产生一个校验元并送入信道，直到）以后的每次移位产生一个校验元并送入信道，直到nk个校验个校验元全部产生并送入信道为止。然后门元全部产生并送入信道为止。然后门2关，门关，门1开，准备下一组开，准备下一组消息编码；消息编码；36【例【例】（7，4）循环码，）循环码，31)(xxxg421)(xxxxhk4级编码器级编码器编码过程编码过程输入输入节拍节拍D0D1D2D3输出输出门门1开，门开，门2关关100000111000102010001310101411011门门1关，门关，门2开开

34、501100600110700010373两种编码器的比较两种编码器的比较（1）基于）基于g（x）的编码器为）的编码器为nk级编码器，需要级编码器，需要nk级移存器；级移存器；基于基于h（x）的编码器为）的编码器为k级编码器，需要级编码器，需要k级移存器。级移存器。（2）当）当nk k时，采用时，采用k级编码器需要资源少。级编码器需要资源少。38和线性分组码一样，循环码译码步骤分三步：和线性分组码一样，循环码译码步骤分三步：（1）计算接收多项式）计算接收多项式r(x)的伴随多项式的伴随多项式s(x)；（2）根据）根据s(x)找出相应错误图样多项式找出相应错误图样多项式e(x)；（3）将）将e(

35、x)和和r(x)模模2加，得到译码输出加，得到译码输出v(x)。1伴随式及计算伴随式及计算设接收多项式为设接收多项式为r(x)，码多项式为，码多项式为v(x)，错误图样多项式为，错误图样多项式为e(x)，则，则()()()r xv xe x用生成多项式用生成多项式g（x）除）除r（x），得），得()()()()()()()g xg xg xr xv xe xe x（求余运算）（求余运算）39【定理【定理】设设g(x)是是(n，k)系统循环码的生成多项式，接收字多项式为系统循环码的生成多项式，接收字多项式为 r(x)，对应，对应错误图样为错误图样为e(x),则则)()()()(xgxgxexr且

36、它们的系数就是该接收字的伴随式。即且它们的系数就是该接收字的伴随式。即)()()()()(xgxgxexrxss可见，循环码的伴随式计算电路就是一个接收多项式可见，循环码的伴随式计算电路就是一个接收多项式 r(x)除以生成多项式除以生成多项式g（x）的除法电路。）的除法电路。电路初始状态为电路初始状态为0，当，当r(x)全部移入后，移存器中的内容为伴随式多项式全部移入后，移存器中的内容为伴随式多项式s(x)。402伴随式计算电路的性质伴随式计算电路的性质由于码的循环结构，伴随式有个重要的性质，用定理描述。由于码的循环结构，伴随式有个重要的性质，用定理描述。【定理【定理】设设s(x)是是r(x)

37、的伴随式，则的伴随式，则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)

38、(x)，移位，移位 i 次，就得到次，就得到r(i)(x)的伴随式的伴随式s(i)(x)。4131)(xxxg)0010110(r)0001011()1(r【例【例】（7，4）循环码，）循环码，计算计算对应的伴随式。对应的伴随式。伴随式计算电路伴随式计算电路计算过程：（开始时，移存器清零）计算过程：（开始时，移存器清零）节拍节拍 输入输入S0S1S2节拍节拍 输入输入S0S1S210000601112110070101s311108100s(1)400119010s(2)51011)100()0001011()101()0010110()1()1(srsr42)()()(xgxrxs由由356

39、)1()1(245)()0001011()()0010110(xxxxrrxxxxrr计算电路性质的意义：计算电路性质的意义：对于在同一循环组中的接收字，只需计算一个接收字的对于在同一循环组中的接收字，只需计算一个接收字的伴随式，即可以通过移位来计算其他接收字的伴随式。伴随式，即可以通过移位来计算其他接收字的伴随式。43普通普通(n,k)(n,k)线性分组码的译码电路框图线性分组码的译码电路框图441组成：组成：（三部分）（梅吉特：（三部分）（梅吉特：Meggit通用译码器）通用译码器）（1）一个）一个n位的缓冲寄存器位的缓冲寄存器（2）组合逻辑电路）组合逻辑电路（3）一个）一个r位的伴随式计

40、算电路位的伴随式计算电路2错误纠正过程错误纠正过程（1）开始译码时，门开，移存器和伴随式计算电路清零，接收字）开始译码时，门开，移存器和伴随式计算电路清零，接收字r（x）一方面送入一方面送入n级缓存，一方面送入伴随式计算电路，形成伴随式。当级缓存，一方面送入伴随式计算电路，形成伴随式。当n位数据接收完后，门关，禁止输入。位数据接收完后，门关，禁止输入。45（2）将伴随式输入错误图样检测电路，）将伴随式输入错误图样检测电路，找出对应的错误图样。找出对应的错误图样。方法：当且仅当缓存器中最高位出错方法：当且仅当缓存器中最高位出错时，组合逻辑电路输出才为时，组合逻辑电路输出才为“1”，即，若检测电路

41、输出为，即，若检测电路输出为“1”，说明缓存中最高位的数据是错误的，需要纠正。这时输出，说明缓存中最高位的数据是错误的，需要纠正。这时输出的的“1”同时反馈到伴随式计算电路，对伴随式进行修正，消除该同时反馈到伴随式计算电路，对伴随式进行修正，消除该错误对伴随式的影响（修正后为高位无错对应的伴随式）。错误对伴随式的影响（修正后为高位无错对应的伴随式）。（3）如高位无错误，组合电路输出）如高位无错误，组合电路输出“0”，高位无需纠正，然后，伴随式，高位无需纠正，然后，伴随式计算电路和缓存各移位一次，这是高位输出。同时，接收字第二位移计算电路和缓存各移位一次，这是高位输出。同时，接收字第二位移到缓存

42、最高位，而伴随式计算电路得到此高位伴随式，用来检测接收到缓存最高位，而伴随式计算电路得到此高位伴随式，用来检测接收字的次高位，即缓存最右一位是否有错。如有错，组合电路输出字的次高位，即缓存最右一位是否有错。如有错，组合电路输出“1”与缓存输出相加，完成第二个码元的纠错，如无错，则重复上述过程，与缓存输出相加，完成第二个码元的纠错，如无错，则重复上述过程，一直译完一个码字为止。一直译完一个码字为止。4631)(xxxg【例【例】（7，4）循环码，）循环码，1110100011101011010010000101010011100101100001011HGdmin(C)=3，可以纠正一个错误。，

43、可以纠正一个错误。所有单重错误的错误图样：所有单重错误的错误图样：错误图样错误图样伴随式伴随式对应对应H的列的列（0000001）e6(x)=x61+x21017（0000010）e5(x)=x51+x+x21116（0000100）e4(x)=x4x+x20115（0001000）e3(x)=x31+x1104（0010000）e2(x)=x2x20013（0100000）e1(x)=xx0102（1000000）e0(x)=11100147由上表可知：最高位由上表可知：最高位x6出错的伴随式为出错的伴随式为1+x2，因此，识别最高位，因此，识别最高位x6是否出错，是否出错，只要识别所对应的

44、伴随式是否为只要识别所对应的伴随式是否为1+x2。译码电路如下：。译码电路如下：)1110011(1)(654xxxxxr552)()()(1)()(xxexexxxrxsxg46()()()1(1100101)v xr xe xxxx 设设错误图样错误图样伴随式伴随式（0000001）e6(x)=x61+x2101（0000010）e5(x)=x51+x+x2111（0000100）e4(x)=x4x+x2011（0001000）e3(x)=x31+x110（0010000）e2(x)=x2x2001（0100000）e1(x)=xx010（1000000）e0(x)=1110031)(xx

45、xg48译码过程：（译码过程：（1100111）节拍节拍 输入输入S0S1S2与门输出与门输出缓存内容缓存内容译码输出译码输出（门（门1、2开，开，3关）关）00000111000211100311110401010501000611100711110（门（门1、2关，关，3开）开）81010110011119000111100110100000011100111101011100012001011100130001011111401001011131)(xxxg49 8.5 8.5 一些重要的循环码一些重要的循环码一一.循环循环HammingHamming码码定义定义9.39.3 设设 是是

46、GF(2m)GF(2m)上的一个本原元，则以上的一个本原元，则以 的本原多项式为生成的本原多项式为生成多项式的（多项式的（2m2m1 1，2m2m1 1m m）Hamming码是循环码。码是循环码。码的校验矩阵为码的校验矩阵为 121nnH H本原元本原元 在在GFGF(q q)中，某一元素中，某一元素 的阶为的阶为q q-1-1，即，即 q q-1-1=e e (q q 1 1 是使等式成立的最小正整数是使等式成立的最小正整数)，则称，则称 为为本原元本原元。本原元多项式本原元多项式 是以本原元为根的即约多项式。是以本原元为根的即约多项式。即约多项式即约多项式 阶大于阶大于0 0且在给定集合且在给定集合F F上除了常数和常数与本身的上除了常数和常数与本身的乘积外，不能被其它多项式除尽的多项式乘积外，不能被其它多项式除尽的多项式