循环码学习教案

1、会计学1循环码循环码第一页，共51页。2设一个设一个(y )（n，k）线性分组码）线性分组码C，如果它的任一码字，如果它的任一码字的每一次循环移位都还是的每一次循环移位都还是C的一个的一个(y )码字，则称码字，则称C是循环码。是循环码。011(1)102(2)213:(,)(,)(,)nnnnnnvvvvCvvvvvvvvC由于循环码是线性分组码，所有这些具有循环关系的码字的全体由于循环码是线性分组码，所有这些具有循环关系的码字的全体构成了构成了n维矢量空间中具有循环特性的维矢量空间中具有循环特性的k维子空间维子空间。第2页/共51页第二页，共51页。3【例例】（7，3）线性分组码）线性分组

2、码1000110010001100101110001101H101110011100100111001G由：由： 得得vu G由两组码字循环由两组码字循环(xnhun)构成的循环构成的循环(xnhun)码。码。 第3页/共51页第三页，共51页。41循环码的特点循环码的特点(tdin)：（1）它是线性分组码，其数学模型应具有）它是线性分组码，其数学模型应具有(jyu)线性特性；线性特性；（2）具有循环特性。）具有循环特性。故循环码的数学模型必须能兼具线性和循环特性故循环码的数学模型必须能兼具线性和循环特性多项式描述。多项式描述。2线性分组码的多项式描述线性分组码的多项式描述字：字：111011

3、0)(),(nnnxrxrrxrrrrr字多项式字多项式码字：码字：1011011(,)( )nnnvv vvv xvv xvx码字多项式码字多项式对于线性分组码对于线性分组码C，可以表示成码字多项式构成的集合：，可以表示成码字多项式构成的集合：1011011( )(,)nnnCC xvv xvxv vvC第4页/共51页第四页，共51页。53循环特性循环特性(txng)的的表示表示以前面以前面(qin mian)的（的（7，3）循环码为例：（任取一码字）循环码为例：（任取一码字）4211110100 xxx移一位移一位移两位移两位移三位移三位)1 (011101042532xxxxxxxx)

4、1 (00111014226432xxxxxxxx7543423543)1 (11001110 xxxxxxxxxxx此时：此时：7 n-1 = 6，超出了，超出了n=7的矢量空间。的矢量空间。要求：要求：75435431xxxxxxx则：则： ，即，即017x17x第5页/共51页第五页，共51页。6下面用下面用 去除去除 ，得余，得余17x7543xxxx5431xxx对于上面第三次移位结果对于上面第三次移位结果(ji gu)，可重新表示如下：，可重新表示如下： ) 1mod()1 (110011107423543xxxxxxxx) 1mod()1 (01001117424654xxxxx

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

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

7、为(n-k)的首一码多项的首一码多项式式g(x)（首一：多项式最高幂次项系数首一：多项式最高幂次项系数 gn-k=1 ） knknxgxgxggxg2210)(（gn-k=1）使得所有码多项式都是使得所有码多项式都是g(x)的倍式，即：的倍式，即：( )( )( )v xu xg x且所有小于且所有小于n n次的次的g(g(x x) )的倍式都是码多项式。的倍式都是码多项式。故循环码完全由它的生成多项式确定。故循环码完全由它的生成多项式确定。第7页/共51页第七页，共51页。8（2）（）（n，k）循环码的生成多项式）循环码的生成多项式g(x)一定一定(ydng)是是(xn-1)的因子，即的因子

8、，即 ) 1()(nxxg)()(1xhxgxn或写成或写成相反相反(xingfn)，如果，如果g(x)是是xn-1的的n-k次因子，则次因子，则g(x)一定是（一定是（n，k）循环码的生成多项式。循环码的生成多项式。生成多项式不唯一。生成多项式不唯一。2（n，k）循环码的构造）循环码的构造(guzo)（1）对）对(x n - 1)做因式分解，找出做因式分解，找出(n k)次因式；次因式；（2）以该）以该(n k)次因式为生成多项式次因式为生成多项式g(x)与不高于与不高于k 1次信息多项式次信息多项式u(x)相乘，相乘，即得到对应消息序列的码多项式。即得到对应消息序列的码多项式。 第8页/共

9、51页第八页，共51页。9【例】一个【例】一个(y )长度长度n = 7的循环码的构造方法。的循环码的构造方法。（1）对）对x 7 - 1作因式分解作因式分解(yn sh fn ji) ) 1)(1)(1(13237xxxxxx故故x 7 - 1有如下有如下(rxi)因式：因式： 一次因式：一次因式：x1三次因式：三次因式：3321,1xxxx四次因式：四次因式：六次因式：六次因式：432342321)1)(1 (1)1)(1 (xxxxxxxxxxxx654323321)1)(1 (xxxxxxxxxx（一个）（一个）（两个）（两个）（一个）（一个）（两个）（两个）第9页/共51页第九页，共

10、51页。10n k = 1，k = 6，生成，生成(shn chn)一种（一种（7，6）循环）循环码；码；n k = 3，k = 4，生成，生成(shn chn)两种（两种（7，4）循环）循环码；码；n k = 4，k = 3，生成，生成(shn chn)两种（两种（7，3）循环）循环码；码；n k = 6，k = 1，生成，生成(shn chn)一种（一种（7，1）循环）循环码；码；例：要得到例：要得到(d do)一（一（7，4）循环码，可选）循环码，可选n k = 3次多项式次多项式1 + x2 + x3或或1 + x +x3 为生成多为生成多项式：项式： 以以g（x）= 1 + x2 +

11、 x3为例，（信息为例，（信息(xnx)位长度为位长度为4） 设信息多项式为：设信息多项式为：332210)(xuxuxuuxu则：循环码编码后的码多项式为：则：循环码编码后的码多项式为：23230123( )( ) ( )()(1)v xu x g xuu xu xu xxx（2）若以）若以n - k次因式作为生成多项式，可供选择的有次因式作为生成多项式，可供选择的有第10页/共51页第十页，共51页。11例：例：2)()0110(xxxuu223235( )( ) ( )()(1)(0111010)v xu x g xxxxxxxxxv对于上述（对于上述（7，4）循环码，有）循环码，有4个

12、信息位，对应有个信息位，对应有16个信息序列，利用个信息序列，利用(lyng)16个个信息序列多项式与生成多项式的乘法运算，可得全部（信息序列多项式与生成多项式的乘法运算，可得全部（7，4）循环码得）循环码得16个码字，如表：个码字，如表： 信息位信息位码字码字信息位信息位码字码字信息位信息位码字码字信息位信息位码字码字0001001001001000011111101011000101100101100101100101100001100011100010100010100110110110011111001010110100011101011101011101001101001101001

13、1010011110011100000000000011011111111循环组循环组1循环组循环组2循环组循环组3循环组循环组4任何码字的循环移位仍是码字，并非由一个码字循环移位可以得到所任何码字的循环移位仍是码字，并非由一个码字循环移位可以得到所有码字，上述（有码字，上述（7，4）码的码集由）码的码集由4组码字循环构成。组码字循环构成。 第11页/共51页第十一页，共51页。12（n，k）循环码是）循环码是n维线性空间一个具有循环特性的维线性空间一个具有循环特性的k维的子空间，故维的子空间，故（n，k）循环码的生成矩阵）循环码的生成矩阵(j zhn)可用码空间中任一组可用码空间中任一组k个

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

15、nknknxgxgxgxgxgxxgxgxgxgxgxxgxgxgxgxxg第12页/共51页第十二页，共51页。13各多项式对应各多项式对应(duyng)的矢量分别为：的矢量分别为： 个kgggxgxgggxxggggxgknkknkn), 0, 0, 0()()0, 0, 0()()0, 0, 0,()(1011010这这k个矢量是线性无关的，且由个矢量是线性无关的，且由g（x）循环移位得到，故都是码字，由它们构）循环移位得到，故都是码字，由它们构成一个成一个kn的矩阵，它们就是的矩阵，它们就是(jish)循环码的生成矩阵。循环码的生成矩阵。 knknkngggggggggG1010100

16、00000000第13页/共51页第十三页，共51页。14【例例】（7，4）循环码：）循环码：4,1)(3kxxxg当一个循环码的生成矩阵确定后，其编码规则为：当一个循环码的生成矩阵确定后，其编码规则为：vu G11010000110100(1010)(1010)(1110010)00110100001101uv如：如：)0001101()()0011010()()0110100()()1101000()(32xgxxgxxxgxg0001101001101001101001101000G第14页/共51页第十四页，共51页。1511011( )( ) ( )( )n kn kn knkxu

17、xu xu xuxa x g xb x 1)(onxuxknknxg)(o1)(oknxbo（ 次数）次数）设：设：1110)(knknxbxbbxb则：则：111101110)()()()(nkknknknknknxuxuxuxbxbbxuxxbxgxa由上述方法作出的生成矩阵所编出的码不是系统由上述方法作出的生成矩阵所编出的码不是系统(xtng)形式，如何得到系形式，如何得到系统统(xtng)形式的循环码？形式的循环码？ 1系统系统(xtng)循环码的编码：循环码的编码：设设1110)(kkxuxuuxu用用x n k 和和u（x）相乘，再除以）相乘，再除以g (x)第15页/共51页第十

18、五页，共51页。16a(x)g(x)是是g(x)的一个倍式，则它是一个码多项式，对应的码矢量为：的一个倍式，则它是一个码多项式，对应的码矢量为：011011(,)n kkvbbbuuu 111101110)()()()(nkknknknknknxuxuxuxbxbbxuxxbxgxa码矢量为系统形式码矢量为系统形式(xngsh)的码字，信息位在尾部。的码字，信息位在尾部。 系统码的编码系统码的编码(bin m)步骤：步骤： (1) 将将k个消息位按升幂排列的次序写成消息多项式个消息位按升幂排列的次序写成消息多项式 u（x） ； (2) 用用x n k 乘以乘以u（x）得到一个次数）得到一个次数

19、 的多项式；的多项式； (3) 用生成多项式用生成多项式g（x）除）除x n k u（x）得余）得余 b（x）（一致校验元）；）（一致校验元）； (4) 联合联合b( x )和和x n k u( x )得到系统码多项式得到系统码多项式 v(x)= b( x )+ x n k u( x )； (5) 将码多项式转换为码字。将码多项式转换为码字。(1)n第16页/共51页第十六页，共51页。17【例例】（7，4）循环码：）循环码：31)(xxxg求求的系统码字。的系统码字。)1010(u，【解解】21)(xxu，n7，k4（1）5323)1 ()(xxxxxuxkn（2）2)(xxb232235(

20、 )( )( )(1)n kv xb xxu xxxxxxx（3）(001 1010 )v （4）第17页/共51页第十七页，共51页。182系统码的生成系统码的生成(shn chn)矩阵矩阵（1）由生成矩阵做初等行变换，将其变为）由生成矩阵做初等行变换，将其变为 形式，即为系统形式，即为系统形式的生成矩阵（单位阵在后，信息位在尾部）。形式的生成矩阵（单位阵在后，信息位在尾部）。kknkIP,，求系统形式的生成矩阵。，求系统形式的生成矩阵。 【例例】（7，4）循环码：）循环码：31)(xxxg 00011010010111010001110001100101110001011101000111

21、0001101101000101000101000111000110241413rrrrrrG（2）分别求）分别求g（x）除）除 的余式（记为）的余式（记为） ，由余式对应的矢量作行矢量构成的，由余式对应的矢量作行矢量构成的kn-k的分块矩阵的分块矩阵 P 联合联合kk的单位阵的单位阵 I 就构成系统形式的生成矩阵：就构成系统形式的生成矩阵： 1,kknknknxxxxx)(,),(),(110 xpxpxpkkknkknkkkknknIPpppppppppG,1000100011, 11 , 10 , 11, 11 , 10 , 11, 01 , 00 , 0第18页/共51页第十八页，共5

22、1页。19，求系统形式的生成矩阵。，求系统形式的生成矩阵。 【例例】（7，4）循环码：）循环码：31)(xxxg2322210233322232331)(1)()(1)()1 ()() 1()1 ()() 1()()()1 ()(xxpxxxpxxxpxxpxxgxxxxxxxgxxxxxxxgxxxxgx0001101001011101000111000110G第19页/共51页第十九页，共51页。20一般情况一般情况(qngkung)下，多项式下，多项式xn-1可因式分解为可因式分解为xn-1 = g (x) h (x) g (x) （n，k）循环码的生成多项式，）循环码的生成多项式，kn

23、xg)(oh (x) （n，k）循环码的一致校验多项式，）循环码的一致校验多项式，kxh)(o在因式分解中，在因式分解中，g (x)和和h (x)处于同等地位，既可以处于同等地位，既可以(ky)用用g (x)去生去生成一个循环码，也可以成一个循环码，也可以(ky)用用h (x)去生成一个循环码。去生成一个循环码。 设由设由g (x)生成的码为生成的码为C，在由，在由h (x)生成的码就是生成的码就是C的对偶码的对偶码C。循环码循环码C的对偶码的对偶码C的基底由的基底由)(,),(),(1xhxxxhxhkn构成。构成。第20页/共51页第二十页，共51页。21设设kkxhxhxhhxh2210

24、)(则：则：个knhhhxhxhhhxxhhhhxhkknkk), 0, 0, 0()()0, 0, 0()()0, 0, 0,()(1011010将上述矢量按逆序排列将上述矢量按逆序排列(pili)作为一个（作为一个（n-k）n矩阵的行矢量，则该矩矩阵的行矢量，则该矩阵就是码阵就是码C的校验矩阵。的校验矩阵。)()(0000000001010101xhxhxhhhhhhhhhHknkkkkkk第21页/共51页第二十一页，共51页。22【例例】（7，4）循环码：）循环码：)1)(1 (14237xxxxxx4231)(,1)(xxxxhxxxg则：则：C的基底的基底(j d)（n-k-1=2

25、） 6432253242)()(1)(xxxxxhxxxxxxxhxxxxh111010001110100011101H第22页/共51页第二十二页，共51页。23 系统形式的校验系统形式的校验(xio yn)矩阵矩阵 （1）对非系统形式）对非系统形式(xngsh)的校验矩阵作初等行变换，变成的校验矩阵作初等行变换，变成 I n-k，PT 的形式的形式(xngsh)；（2）分别求）分别求h（x）除）除 的余式（记的余式（记为）为） ，由余式对应的，由余式对应的逆矢量逆矢量可得到系可得到系统形式的校验矩阵：统形式的校验矩阵：kkknkknxxxxx,21)(,),(),(021xrxrxrknk

26、n0 , 02, 01, 00 , 22, 21, 20 , 12, 11, 1100010001rrrrrrrrrHkkknkknkknknkknkkn（3）T,PIHIPGknkknk第23页/共51页第二十三页，共51页。24【例例】（7，4）循环码：）循环码：)1)(1 (14237xxxxxx4231)(,1)(xxxxhxxxg 11101000111010110100111101000111010001110131 rrH（1）（2）k = 4，n k 1 = 2（3）10001010100111001011000010111011000010110000101100001011

27、214, 13rrrrrG)1 ()()()()1 ()()1 (243243242xxxhxxxxxxhxxxxxhxxx111010001110101101001H第24页/共51页第二十四页，共51页。25 循环码是线性分组码的一个子类，因此循环码可以循环码是线性分组码的一个子类，因此循环码可以(ky)按一般线性分组按一般线性分组码利用常用的组合逻辑电路来实现编码。但对于线性分组码，当其信息位分码利用常用的组合逻辑电路来实现编码。但对于线性分组码，当其信息位分组长度较长，编码位数较多时，其编码电路非常复杂。组长度较长，编码位数较多时，其编码电路非常复杂。 由于循环码具有循环特性，其编码器

28、通常用简单的具有反馈连接的移位由于循环码具有循环特性，其编码器通常用简单的具有反馈连接的移位寄存器就可以寄存器就可以(ky)实现，大大简化了编码器的复杂度。实现，大大简化了编码器的复杂度。 利用具有反馈连接的移位寄存器实现的循环码编码电路，实际上是多项利用具有反馈连接的移位寄存器实现的循环码编码电路，实际上是多项式运算电路。首先研究多项式运算电路。式运算电路。首先研究多项式运算电路。 第25页/共51页第二十五页，共51页。26 设设0111)(axaxaxaxakkkk0111)(bxbxbxbxbrrrr)()()()(xrxbxqxa（被除式）（被除式）（除式）（除式）q(x) 商，商，

29、r(x) 余余除法除法(chf)电路：电路：第26页/共51页第二十六页，共51页。27（1）除法电路的结构由除式）除法电路的结构由除式b（x）决定）决定(judng)；（2）组成：由）组成：由r个存储单元组成个存储单元组成r级移位寄存器（级移位寄存器（D0Dr-1） bi：常乘器，（：常乘器，（bi = 1，输出输入；，输出输入；bi = 0，输出，输出0） 当当bi = 1，对应支路连通（直通）；，对应支路连通（直通）； 当当bi = 0，对应支路断开，对应的模，对应支路断开，对应的模2加法器可去掉。加法器可去掉。 故：电路有故：电路有r个移位寄存器，最多个移位寄存器，最多r+1个常乘器，

30、最多个常乘器，最多r个模个模2加法器。加法器。说明说明(shumng)：第27页/共51页第二十七页，共51页。28（3）工作原理简述：）工作原理简述： 电路清零，被除式系数按高次到低次依次进入电路（电路清零，被除式系数按高次到低次依次进入电路（ak首先进入），首先进入），r次移位后，次移位后，移存器自右至左内容为：（移存器自右至左内容为：（a k，a k-1，.，a k-r+1） 第第 r + 1次移位后，输出商的最高次位的系数（次移位后，输出商的最高次位的系数（a k b r 或或a k b r-1），并反馈到前），并反馈到前面作模面作模2加运算后存入各级加运算后存入各级( j)寄存器中，

31、以后每次移位输出商的对应次位寄存器中，以后每次移位输出商的对应次位的系数并反馈回去。的系数并反馈回去。 依次类推，经过依次类推，经过 k + 1次移位后，完成整个除法运算，最后输出商常数项系数，次移位后，完成整个除法运算，最后输出商常数项系数，此时移存器中的内容就是余式此时移存器中的内容就是余式r（x）各次项对应的系数（高位寄存器对应高）各次项对应的系数（高位寄存器对应高次项系数）。次项系数）。 第28页/共51页第二十八页，共51页。291)(34xxxa1)(3xxxb【例例】134 xx13 xxxxx241x123xxx13 xx)(2xrx 工作工作(gngzu)过程过程: (r=3

32、)节拍节拍 输入输入D0D1D2输出输出清零清零010000111000201100r次次300110r1次次411111（x）k1次次5-0011（x0）1)( xxq2)(xxr第29页/共51页第二十九页，共51页。301基于基于(jy)生成多项式生成多项式g（x）的编码器（）的编码器（nk级编码器）级编码器）编码器电路的结构由生成多项式决定编码器电路的结构由生成多项式决定(judng)，生成多项式，生成多项式g（x）的最高次数）的最高次数为为n-k，故编码器有，故编码器有n-k级移存器，故称级移存器，故称n-k级编码器。级编码器。对于循环码的系统编码，首先对于循环码的系统编码，首先(s

33、huxin)要得到要得到u(x) xn-k 除以除以g(x)的余式的余式p(x)，再组合成系统码，即：再组合成系统码，即：( )( ) ( )( )( )( )( )n kn ku x xq x g xp xv xp xu x x对于除法电路：一方面我们可以得到商，还可以得到余式。对于系统码编码我对于除法电路：一方面我们可以得到商，还可以得到余式。对于系统码编码我们可以先输出信息位，再输出余式（校验位）就可以得到系统码，另外由于被除式为们可以先输出信息位，再输出余式（校验位）就可以得到系统码，另外由于被除式为u(x)x n-k，u(x)应从应从n-k级移存器的最前端输入。级移存器的最前端输入。

34、 第30页/共51页第三十页，共51页。31编码编码(bin m)过程：过程：（1）门打开，）门打开，k接接“1”，消息数据，消息数据u k-1 , . u0移入电路，并同时送入信道移入电路，并同时送入信道(xn do)，一，一旦旦k个消息全部移入电路，移存器中的个消息全部移入电路，移存器中的n - k个数据就构成了余式的系数；个数据就构成了余式的系数；（2）门关，断开反馈连接，）门关，断开反馈连接，k接接“2”；（3）移出移存器中的数据）移出移存器中的数据 (校验元校验元)，并送入信道，并送入信道(xn do)，与，与k个信息位组成码字。个信息位组成码字。第31页/共51页第三十一页，共51

35、页。32【例例】（7，4）循环码，）循环码，31)(xxxg若：若：233323323356(1011)( )1( )(1)(1) ( )1( )1( )1(1001011)uu xxxu x xxxxxxxg xv xx g xxxxv 第32页/共51页第三十二页，共51页。33编码编码(bin m)过程：（过程：（k4）节拍节拍输入输入D0D1D2输出输出门开，门开，k10100011110120101131100041001门关，门关，k2501006001070001第33页/共51页第三十三页，共51页。若信息(xnx)序列 m=(m0, m1,mk-1)对应(duyng)的多项式

36、m(x)=mk-1xk-1+ mk-2xk-2+m02基于基于(jy)校验多项式校验多项式h（x）的编码器（）的编码器（k级编码器）级编码器）码多项式011102211)(cxcxcxmxmxmxcknknknnknk01112211cxcxcxcxcxcknknknknnnnn第34页/共51页第三十四页，共51页。由于(yuy)hk=1cn-1-k = - (h0 cn-1 +h1 cn-1-1 + +hk-1 cn-1-(k-1)cn-2-k = - (h0 cn-2 +h1 cn-2-1 + +hk-1 cn-k-1)cn-3-k = - (h0 cn-3 +h1 cn-3-1 + +

37、hk-1 cn-k-2)cn-k-(n-k) = - (h0 ck +h1 ck-1 + +hk-1 c1)第35页/共51页第三十五页，共51页。36编码器电路编码器电路(dinl)的结构由校验多项式决定，生成多项式的结构由校验多项式决定，生成多项式h(x)的最高次数为的最高次数为k，故编，故编码器有码器有k级移存器，故称级移存器，故称 k级编码器。级编码器。编码器电路编码器电路(dinl)编码编码(bin m)过程过程（1）门）门1打开，门打开，门2关闭，关闭，k位消息数据位消息数据u0，u1，. ，uk-1移入电路，并同时移入电路，并同时送入信道；送入信道；（2）k位消息全部移入，门位消

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

39、开501100600110700010第37页/共51页第三十七页，共51页。383两种编码器的比较两种编码器的比较(bjio)（1）基于）基于g（x）的编码器为）的编码器为nk级编码器，需要级编码器，需要nk级移存器；级移存器； 基于基于h（x）的编码器为）的编码器为k级编码器，需要级编码器，需要k级移存器。级移存器。（2）当）当nk k时，采用时，采用(ciyng)k级编码器需要资源少。级编码器需要资源少。 第38页/共51页第三十八页，共51页。39和线性分组码一样和线性分组码一样(yyng)，循环码译码步骤分三步：，循环码译码步骤分三步：（1）计算接收多项式）计算接收多项式r (x)的

40、伴随多项式的伴随多项式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），得），得( )( )( ) ( ) ( )( ) ( )g xg xg xr xv xe xe x（求余运算）（求余运算）第39页/共51页第三十九页，共51

41、页。40【定理】设【定理】设g (x)是是(n，k)系统循环码的生成多项式，接收字多项式为系统循环码的生成多项式，接收字多项式为 r (x)，对应错误，对应错误(cuw)图样为图样为e (x), 则则 )()()()(xgxgxexr且它们且它们(t men)的系数就是该接收字的伴随式。即的系数就是该接收字的伴随式。即 )()()()()(xgxgxexrxss可见，循环码的伴随式计算可见，循环码的伴随式计算(j sun)电路就是一个接收多项式电路就是一个接收多项式 r (x) 除以生成多项式除以生成多项式g（x）的除法电路。）的除法电路。电路初始状态为电路初始状态为0，当，当r (x)全部移

42、入后，移存器中的内容为伴随式多项式全部移入后，移存器中的内容为伴随式多项式s (x)。第40页/共51页第四十页，共51页。412伴随伴随(bn su)式计算电路的式计算电路的性质性质由于码的循环由于码的循环(xnhun)结构，伴随式有个重要的性质，用定理描述。结构，伴随式有个重要的性质，用定理描述。 【定理】设【定理】设s (x)是是r (x)的伴随式，则的伴随式，则r (x)的循环移位的循环移位 x r (x)的伴随式的伴随式s(1) (x)是是s (x)在伴随式计算电路中无输入时右移在伴随式计算电路中无输入时右移(yu y)一位的结果，一位的结果，即：即： )(mod)()()1(xgx

43、xsxs【推论推论】用生成多项式用生成多项式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) 。 第41页/共51页第四十一页，共51页。4231)(xxxg)0010110(r)0001011()1(r【

44、例例】（7，4）循环码，）循环码，计算计算对应的伴随式。对应的伴随式。伴随式计算伴随式计算(j sun)电路电路计算计算(j sun)过程：（开始时，移存器清零）过程：（开始时，移存器清零）节拍节拍 输入输入S0S1S2节拍节拍 输入输入S0S1S210000601112110070101s311108100s(1)400119010s(2)51011)100()0001011()101()0010110()1()1(srsr第42页/共51页第四十二页，共51页。43)()()(xgxrxs由由356)1()1(245)()0001011()()0010110(xxxxrrxxxxrr245

45、xxx13 xx12 xx34xx xxx241)()101(2xxs235xxxxxx2313 xx356xxx13 xx123xxx45xx 235xxx)()100()1(xs346xxx234xxxxxx24xx 313 xx1计算电路性质的意义：对于在同一循环组中的接收字，只需计算一个接收字的计算电路性质的意义：对于在同一循环组中的接收字，只需计算一个接收字的伴随伴随(bn su)式，即可以通过移位来计算其他接式，即可以通过移位来计算其他接收字的伴随收字的伴随(bn su)式。式。第43页/共51页第四十三页，共51页。44普通普通(ptng)(n,k)(ptng)(n,k)线性分组

46、码的译码电路线性分组码的译码电路框图框图第44页/共51页第四十四页，共51页。451组成组成(z chn)：（三部分）（梅吉特：（三部分）（梅吉特：Meggit通用译码器）通用译码器）（1）一个）一个n位的缓冲寄存器位的缓冲寄存器（2）组合逻辑电路）组合逻辑电路（3）一个）一个r位的伴随式计算位的伴随式计算(j sun)电路电路 2错误纠正过程错误纠正过程（1）开始译码时，门开，移存器和伴随式计算电路清零，接收字）开始译码时，门开，移存器和伴随式计算电路清零，接收字r（x）一方面）一方面送入送入n级缓存，一方面送入伴随式计算电路，形成伴随式。当级缓存，一方面送入伴随式计算电路，形成伴随式。当

47、n位数据接收完位数据接收完后，门关，禁止输入。后，门关，禁止输入。第45页/共51页第四十五页，共51页。46（2）将伴随式输入错误图样）将伴随式输入错误图样(tyng)检检测电路，找出对应的错误图样测电路，找出对应的错误图样(tyng)。 方法：当且仅当缓存器中最高位出方法：当且仅当缓存器中最高位出错时，组合逻辑电路输出错时，组合逻辑电路输出(shch)才为才为“1”，即，即，若检测电路输出若检测电路输出(shch)为为“1”，说明缓存中最高位，说明缓存中最高位(o wi)的数据是错误的，需要纠正。这时输出的的数据是错误的，需要纠正。这时输出的“1”同时反馈到伴随式计算电路，对伴随式进行修正

48、，消除该错误对伴随式的影响同时反馈到伴随式计算电路，对伴随式进行修正，消除该错误对伴随式的影响（修正后为高位（修正后为高位(o wi)无错对应的伴随式）。无错对应的伴随式）。（3）如高位无错误，组合电路输出）如高位无错误，组合电路输出“0”，高位无需纠正，然后，伴随式计算电路和，高位无需纠正，然后，伴随式计算电路和缓存各移位一次，这是高位输出。同时，接收字第二位移到缓存最高位，而伴随缓存各移位一次，这是高位输出。同时，接收字第二位移到缓存最高位，而伴随式计算电路得到此高位伴随式，用来检测接收字的次高位，即缓存最右一位是否式计算电路得到此高位伴随式，用来检测接收字的次高位，即缓存最右一位是否有错。如有错，组合电路输出有错。如有错，组合电路输出“1”与缓存输出相加，完成第二个码元的纠与缓存输出相加，完成第二个码元的纠错，如无错