讲义62循环码

1、信息论讲义（第六章）6-2 循环码(Cyclic Code)循环码是线性分组码的最重要的一类码，它的结构完全建立在有限域多项式的基础上。它具有两个基本特点：一是编码电路与译码电路非常简单，易于实现；二是其代数性质好编码译码分析方便，有一些好的译码方法。6-2-1 循环码的描述循环码定义：一个(n,k)线性分组码C，如果码组中的一个码字的循环移位也是这个码组中的一个码字，则称C为循环码。C(0)=cn-1,cn-2,c1,c0 CC(1)=cn-2,cn-3,c0,cn-1 C称为具有循环自闭性。循环码的多项式描述：循环码可以用监督矩阵和生成矩阵描述，但更多地用域上多项式来描述，一个(n,k)循

2、环的码字矢量C(0)用一个n-1次多项式描述，可以表示为：C(x)= cn-1xn-1+cn-2xn-2+c1x+c0这个多项式称为码字多项式。码字矢量的循环移位可以用x乘上C(x)后的模xn-1(xn+1)来表示。xC(x)= x(cn-1xn-1+cn-2xn-2+c1x+c0) = cn-1xn+cn-2xn-1+c1x2+c0 x = cn-2xn-1+c1x2+c0 x+ cn-1 (模xn+1)模xn+1相当于xn+1=0；xn=1循环码举例：(7,4)系统循环码的编码及码字多项式如下表：信息码字循环码字码字多项式g(x)的倍式倍式编码00000000 00000000000010

3、001 011x3+x+11000100100010 110x4+x2+xx001000110011 101x4+x3+x2+1x+1001101000100 111x5+x2+x+1x2+1010101010101 100x5+x3+x2x2010001100110 001x5+x4+1x2+x+1011101110111 010x5+x4+x3+xx2+x011010001000 101x6+x2+1x3+x+1101110011001 110x6+x3+x2+xx3+x101010101010 011x6+x4+x+1x3+1100110111011 000x6+x4+x3x310001

4、1001100 010x6+x5+xx3+x2+x111011011101 001x6+x5+x3+1x3+x2+x+1111111101110 100x6+x5+x4+x2x3+x2110011111111 111x6+x5+x4+x3+x2+x+1x3+x2+11101可以看出：每个码字的循环移位仍然属于这个码组，注意：并不是说这个码组是由一个码字的循环移位构成的，本例中是由四个码字的循环移位构成的。生成多项式的定义：在一个(n,k)循环码中，有且仅有一个次数为n-k=r的码字多项式，记为：g(x)=xr+gr-1xr-1+g1x+1同时：每个码字多项式都是g(x)的倍式；每个次数小于等于

5、n-1的g(x)的倍式必为一个码字多项式。这时称g(x)的(n,k)码的生成多项式。从上面的例子可见，g(x)=x3+x+1为(7,4)循环码的生成多项式。生成多项式的性质：§ 循环码C中次数最低的非零码字多项式是唯一的，其次数为r=n-k。§ 令g(x)=xr+gr-1xr-1+g1x+g0为一个(n,k)循环码C中最低次数码字多项式，则其常数项必为g0=1。定理1：(n,k)循环码的生成多项式g(x)是xn+1的因式。证明：已知g(x)为一个n-k次多项式，则xkg(x)为一个n次多项式，则必有：因为xkg(x)是g(x)的循环移位，它也是一个码字多项式，所以一定为g(

6、x)的倍式，即有：g(k)(x)为g(x)的循环移位在模xn+1下的结果，因此有：g(k)(x)=q(x)g(x)，由上面的关系式可知：xkg(x)=(xn+1)+g(k)(x)xn+1=xkg(x)+q(x)g(x)=xk+q(x)g(x)因此，g(x)为xn+1的因式。定理2：若g(x)是一个n-k次多项式，且为xn+1的因式，则g(x)生成一个(n,k)循环码。这个定理说明：xn+1的次数为n-k的任何一个因式，均可以生成一个(n,k)循环码。对于较大的n，xn+1可以有多个n-k次多项式，产生不同的(n,k)循环码，但可能有好有坏。例如：多项式x7+1可以分解为：x7+1=(x3+x+

7、1)(x3+x2+1)(x+1)可以看出有两种(7,4)循环码的生成矩阵 g(x)= (x3+x+1)和g(x)= (x3+x2+1)。还可以产生一种(7,6)循环码，6-2-2 循环码的编码方法系统循环码的编码方法：已知循环码的生成矩阵可以按以下步骤产生系统循环码。首先定义以下多项式：m(x)=mk-1xk-1+mk-2xk-2+m1x+m0 为信息码字多项式；c(x)=cn-1xn-1+cn-2xn-2+c1x+c0 为循环码字多项式；g(x)=xr-1+gr-2xr-2+g1x+1 为生成多项式；系统码的编码分为三步：§ 用xn-k乘上m(x);§ 用g(x)除以xn

8、-km(x)，得到模g(x)的余式r(x)§ c(x)=xn-km(x)+r(x)为系统循环码的码字多项式。例题1：(7,4)循环码的生成多项式为g(x)=x3+x+1求m=1010的循环码。解：m(x)=x3+x, xn-k=x3;xn-km(x)=x3(x3+x)=x6+x4r(x)=x+1C(x)=xn-km(x)+r(x)=x6+x4+x+1C=1010 011例题2：(7,3)循环码的生成多项式为g(x)=x4+x3+x2+1=(x+1)(x3+x+1)求：m=010的循环码字C解：m(x)=x; xn-km(x)=x4x=x5C(x)=x5+x2+x+1C=010 011

9、1非系统循环码的编码方法：已知循环码的生成矩阵，可以方便的求出非系统循环码，C(x)=m(x)g(x)例如：m=1101 g(x)=x3+x+1C(x)=(x3+x2+1)(x3+x+1)=x6+x4+x3+x5+x3+x2+x3+x+1=x6+x5+x4+x3+x2+x+1C=1111111m=0101; c(x)=(x2+1)(x3+x+1)=x5+x3+x2+x3+x+1=x5+x2+x+1C=0100111循环码的生成矩阵：循环码可以用域上多项式描述，也可以用生成矩阵描述。已知g(x)为循环码C中的一个码字多项式，由循环码的循环特性可知，可以证明：在(n,k)循环码的码字多项式中，g(

10、x),xg(x),xk-1g(x)等k个码字多项式必是线性无关（相互独立的）的。根据线性空间的特性，可知，它们是一个k维子空间的基底，即由它们的线性组合可以生成这个k维子空间的2k个码字。再根据线性分组码生成矩阵的定义，它的行向量是由k个线性无关的码字构成的，可以得到(n,k)循环码的一个多项式矩阵为：G(x)=xk-1g(x)xk-2g(x)g(x)相应的生成矩阵为G=gn-kgn-k-1g1g00000gn-kgn-k-1g1g00000gn-kgn-k-1g1g0由这个基本关系式可以看出，当输入信息码字矢量为(mk-1,mk-2,m0)时，相应的码字多项式为：C(x)=(mk-1,mk-

11、2,m0)G(x) =(mk-1xk-1+mk-2xk-2+m0)g(x) =m(x)g(x)利用这种方法产生的循环码为非系统循环码，因为，G(x)为非标准型生成矩阵，（非典型生成矩阵）。这个非标准型生成矩阵可以通过矩阵的初等变换转换为标准型生成矩阵。可以通过以下例子说明。例题：已知(7,4)循环码的生成多项式为g(x)=x3+x+1，其非标准型生成矩阵为：G(x)=x3g(x)=x6+x4+x3=1011000x2g(x)x5+x3+x20101100xg(x)x4+x2+x0010110g(x)x3+x+10001011利用不同的矩阵变换可以得到不同的标准型生成矩阵。这种变换包括：

12、7; 列换位；§ 初等行变换；通过以上两种方法，可以得到标准型生成矩阵：G=1000111010010100101100001011只使用初等行变换可以得到标准生成矩阵：G=1000101010011100101100001011可知标准型生成矩阵是不唯一的。6-2-3 校验子与循环码的译码原理设发送的码字多项式位C(x)，错误图样多项式位E(x)，则接收码字多项式为：R(x)=C(x)+E(x)译码器的工作过程为：§ 由接收码字多项式R(x)计算校验子多项式S(x);§ 根据校验子多项式S(x)计算错误图样多项式E(x);§ 利用R(x)-E(x)=C

13、(x)计算译码器输出的估计值。发送码字多项式为：C(x)=cn-1xn-1+cn-2xn-2+c1x+c0接收码字多项式为；R(x)=rn-1xn-1+rn-2xn-2+r1x+r0校验子多项式为：E(x)=en-1xn-1+en-2xn-2+e1x+e0由R(x)=C(x)+E(x)可知：ri=ci+eI i=0,1,n-1这时定义校验子多项式为： 模g(x)即：S(x)E(x)R(x) 模g(x)也就是说，接收码字多项式除以g(x)的余式多项式为校验子多项式。如果：S(x)=0，表示接收码字无错；如果：S(x)0,表示接收码字有错；(n,k)循环码的校验子多项式的一般表达式为：S(x)=s

14、r-1xr-1+sr-2xr-2+s1x+s0即校验子多项式S(x)为一个r-1次多项式。其校验子矢量为：S=sr-1,sr-2,s1,s0它共有2r个状态，当2rn+1时，即可以纠一位错。例题：(7,4)循环码的校验子及译码，已知：(7,4)循环码的生成矩阵为g(x)=x3+x+1考虑接收码字不错或只错一位时的校验子多项式。发送码字多项式为：C(x)=cn-1xn-1+cn-2xn-2+c1x+c0接收码字多项式为；R(x)=rn-1xn-1+rn-2xn-2+r1x+r0校验子多项式为：E(x)=en-1xn-1+en-2xn-2+e1x+e0eiE(x)S(x)s2,s1,s0错误情况0

15、00000无错e0=111001r0e1=1xx010r1e2=1x2x2100r2e3=1x3x+1011r3e4=1x4x2+x110r4e5=1x5x2+x+1111r5e6=1x6x2+1101r6这个表给出了接收码字不出错或只错一位时校验子多项式和校验子矢量的结果。根据这个表可以进行译码。例如：发送码字为：C=0010110，接收码字为：R=0011110，表明r3错。接收码字多项式为：R(x)=x4+x3+x2+x, g(x)=x3+x+1，校验子多项式为： 模g(x)S(x)=x+1 s2,s1,s0=011 查表可知r3出错。已知(7,4)循环码的最小汉明距离dmin=3，只能

16、纠一位错，当接收码字出现两位错时将不能纠正。例如：发送码字为：C=0010111，接收码字为：R=0011111，表明r3和r0错。R(x)=x4+x3+x2+x+1S(x)=x; s2,s1,s0=010，根据校验子表可知，译码器判为r1错，这时产生译码错码。6-2-4 循环码的编码电路根据循环码的编码方法，可知编码电路应当是一个多项式的除法电路，它是码字多项式的循环一位后除以生成多项式。系统码编码器：为了构成系统码，可知C(x)=xn-km(x)+r(x)r(x)=xn-km(x)/g(x) 模g(x)以(7,4)汉明码为例：g(x)=x3+x+1编码器电路如图所示：它由n-k级移位寄存器

17、构成。门1门2D22D1D0或门C(x)C(x)输入m(x)这是一个由n-k=3级移位寄存器及加法器、或门和门控电路构成的。§ 移位寄存器的初始状态为全0，门1开，门2关。信息码元以m3,m2,m1,m0依次输入编码器。信息码元一方面通过或门输出，另一方面送入除法电路。在除法电路的右端输入m(x)相当于完成了循环移位n-k=3位。§ 四次移位后，信息码元已输出，形成了系统循环码的前四位信息位。同时寄存器中存放的就是余式多项式的系数，从右到左分别是(c2,c1,c0)。§ 门1关，门2开，经三次移位，这三个监督位从编码器输出。§ 门1开，门2关，进行第二个

18、码字的编码。m=1001, C=1001 110的编码过程如下表：时钟信息码字寄存器内容输出码字D0D1D20000111101200110301110410111500116000170000(7,3)循环码的生成矩阵为：g(x)=x4+x3+x2+1其编码电路为：门1D2D3D1门2D0或门C(x)输入m(x)由于n-k=r=4所以编码器有四级移位寄存器。非系统循环码编码电路：非系统循环码的产生为：C(x)=m(x)g(x),可知其编码器为如下：D0D1D2m(x)例如m=1110，编出的循环码字为：C=1100001C(x)=m(x)g(x)=(x3+x2+x)(x3+x+1)=x6+x

19、5+16-3 循环码的译码循环码的编码电路由n-k级移位寄存器构成，比较简单，但是循环码的译码电路就相对比较复杂。因此，循环码的译码方法是研究编码理论和编码技术的重要内容。线性分组码（不仅是循环码）的译码大体分为两类：一是利用码字的代数结构进行译码，称为代数译码方法。另一类不仅利用代数结构，而且还利用概率理论，称为概率译码。这里我们重点介绍代数译码方法，包括捕获（错）译码，大数逻辑译码。6-3-1 梅吉特(Meggit)译码器上面我们介绍了循环码的校验子（伴随式）译码的基本原理，已知：S(x)=R(x)/g(x) mod g(x)这里首先介绍一个有关校验子多项式的重要特性。定理：设S(x)是接

20、收码字多项式R(x)的校验子多项式，则R(x)的循环移位xR(x)mod xn+1的校验子S1(x)是S(x)在g(x)除法电路中无输入时右移一位的结果。S1(x)xS(x) mod g(x)证明：由校验子多项式的定义可知，S(x)R(x) mod g(x)，两边同时乘以x可得；xS(x)xR(x) mod g(x)这时如果定义S1(x)xR(x) mod g(x)显然有S1(x)xS(x) mod g(x)定理的推广：这个定理的结果可以推广为，对于任意给定的j=1,2,n-1，必有xjR(x)的校验子多项式为：Sj(x)=xjR(x)/g(x)xjS(x) mod g(x)同时有任意多项式a

21、(x)乘R(x)所对应的校验子多项式Sa(x)=a(x)R(x)/g(x)a(x)S(x) mod g(x)校验子多项式的这些性质，在循环码的译码中有重要作用。梅吉特译码原理：如果：C(x)为循环码C中的一个码字多项式，则xC(x)mod xn+1也是这个码组中的一个码字。如果：S(x)为R(x)=C(x)+E(x)的校验子多项式，则xS(x)也必然是xR(x)=xC(x)+xE(x)的校验子多项式。这表明：如果E(x)是一个译码器可以纠正的错误图样（相当于译码标准阵中的陪集首），则xE(x)也是一个可以纠正的错误图样，xjE(x) (j=1,2,n-1)也是可以纠正的错误图样。这样就可以根据

22、这种循环关系，对错误图样分类，将任一错误图样及其所有n-j次的循环移位归为一类。同一类的错误，可以使用同一个译码单元电路，可以简化译码器电路的复杂性。例如：可以将“只错一位”的错误图样(1000),(0100),(0001)归为一类，这样用一个错误图样(1000)的校验子S(x)代表这一类错误图样的校验子。这样可以大大减少译码器要识别的错误图样类别的个数：一个(n,k)循环码，要纠正t位错误，译码器要识别的错误图样总数为： 例如(7,4)循环码可以纠正一位错，n=7，t=1，Ne=C71=7。而通过分类后，译码器需要识别的错误图样的类别数为：例如(7,4)循环码的错误图样类别数为Ng=1。可以

23、看到通过分类识别，可以简化循环码译码器的复杂性。例题：(7,4)循环码的生成矩阵为g(x)=x3+x+1，通过前面分析可知，只要接收码字矢量只错一位，译码器总可以正确译码。在构造此译码器的错误图样识别电路时，只要识别一个错误图样例如，E6=1000000就可以了。这个错误图样对应的校验子矢量为S=101，由此可以得到一种译码器结构如图：D1D0D2r0 7级移位寄存器 r6门C(x)R(x)这个译码器上面是一个g(x)除法电路，下面是一个7级移位寄存器作为缓存器，中间的反相器和一个与门组成了(101)校验子识别电路。译码过程如下：§ 开始译码时门打开，移位寄存器内容位全0。收到的码字

24、多项式位R(x)=r6x6+r0 由高次到低次分别输入到7级缓存器和除法电路，7次移位后，缓存器存入整个码字，除法电路S(x)=E(x)/g(x), E(x)=x6得到校验子S0=s2,s1,s0。这时门关上，进行译码。§ 如果S0(x)=x6=x2+1mod g(x)，这时101识别电路输出为1，表明r6为有错。§ 这时译码器继续移位，通过101识别电路可以将r6位的错误纠正。§ 在纠错的同时，101识别电路的输出又反馈到除法电路的输入端，以消除错误码元对除法电路的下一个校验子计算的影响。校验子产生电路开始在无输入的情况下移位，相当以开始产生xjS(x)。本电路

25、中，第7次移位后产生了校验子S0，第8次移位时对r6进行纠正，同时将101识别电路的输出的1输入到除法电路的输入端，结果使除法电路的寄存器状态为000，消除了e6的影响。下面我们看一下，利用这个电路能否纠正其它错误图样的接收码字。§ 如果E(x)=x5, 表明e5=1或E=0100000，这时经过前7次移位后得到的校验子多项式为S0(x)=x5=x2+x+1mod g(x)，这时除法电路的移位寄存器状态为111，101识别电路的输出为0，说明r6正确，不必纠正。§ 第8次移位后，r5移位到缓存器的最右端。同时校验子除法电路的结果根据定理可知：（通过电路分析也可以看出）S1(

26、x)=xS0(x)=xE(x)=x6=x2+1 mod g(x) 产生101状态；这时101识别电路输出1，对r5进行纠正。可以看到，利用循环码的循环特性，可以简化译码器的复杂性。从上述译码过程中可以看到，(n,k)循环码的译码器译一个码字共需要2n次移位，不能实现连续译码，为了实现连续译码，可以再加一套除法电路，门14级缓存器门2其工作过程如下：§ 译码前两个移位寄存器为全0状态，门1开，门2关，当k=4次移位后，4级缓存器接收到码字的前4位信息位。§ 此时，门1关。再移位n-k=3次后，上面的除法电路得到校验子S0(x)，§ 这时门2开，将上面除法电路得到的校

27、验子送入下面的除法电路，随即门2关闭，且上面的除法电路清0。§ 门1再次打开，4级缓存器一边送出第一组信息，一边接收第二个码字的信息位，与此同时，上面的除法电路计算第二个码字的校验子，下面的除法电路对第一组码字进行纠错。§ 以上是对系统码而设计的电路，如果是非系统码，k级缓存器应改为n级，而且要在得到的码字中恢复信息位。根据m(x)=C(x)/g(x)，应再加一个除法电路。上面介绍的系统循环码的一般译码器称为梅吉特译码器。6-3-2 捕错译码循环码的译码器的复杂性主要取决于由校验子确定错误图样的组合逻辑电路的复杂性，另外一种译码方法称为捕错译码，其特点是适应于纠突发错误码。

28、工作原理：设C(x)是一个纠t位错误的(n,k)系统循环码的码字多项式，而相应的接收码字多项式为：R(x)=C(x)+E(x)，译码器得到的校验子多项式为：S(x)=R(x)/g(x)=E(x)/g(x)E(x) mod g(x) EI(x)+EP(x), mod g(x)其中：EI(x)=en-1xn-1+en-2xn-1+en-kxn-kEP(x)=en-k-1xn-k-1+e1x+e0EI(x)为k位信息位的错误图样，EP(x)是n-k=r位监督位的错误图样。这时可以看到：如果：错误图样多项式E(x)的次数=n-k-1=r-1， 即码字中的错误集中在n-k=r监督位上， 即en-1=en

29、-2=en-k=0；则：EI(x)=0，E(x)=EP(x)。又因为：生成多项式g(x)的次数位n-k=r，所以：校验子多项式S(x)=E(x)/g(x)=EP(x), mod g(x)得到的结论是：对于具有这样的错误图样的码字C(x)，经过循环移位后，可以使S(x)=E(x)，译码过程就可以变为：C(x)=R(x)-S(x)。(在GF(2)上，减法与加法一样)要使一个码字的错误码元全部集中在码字的后n-k=r位上，只要求错误码元集中在任意连续n-k位上即可。因为：码字多项式的循环移位和校验子多项式的循环移位有一一对应的关系。捕错译码的定义：若接收码字R(x)对应的校验子多项式为S0(x)，经

30、过i次循环移位后，xiR(x)=Ri(x)对应的校验子多项式为Si(x)。一旦检测出Si(x)的重量W(Si(x)t，就认为此时码字的错误码元已经全部集中在xiR(x)=Ri(x)的后n-k位以内了。这时可以由Ri(x)-Si(x)得到已经纠错的接收码字Ci(x)=xiC(x)，但码字顺序不对，将其再进行n-i次循环移位，即可得到:C(x)=xnC(x)=xn-ixiC(x) 从而纠正了错误，这种译码方法称为捕错译码。捕错译码的适应条件：§ 只有当所有小于等于t个错误全部集中再连续n-k=r位以内时，捕错译码才有效。§ 当码字的错误突发长度b小于等于(n-k)/2时，捕错译

31、码才有效。例如：(7,4)码，dmin=3, t=1, n=7, k=4, n-k=3 (n-k)/2=1.5 所以b=1(15,7)码，dmin=5, t=2, n-k=8, (n-k)/2=4 b=4,§ 如果一个(n,k)码可以纠正t位错，使用捕错译码的必要条件是：k<n/t或t<n/k；（这个条件不够充分）。定理：捕错译码的判别条件纠正t位错误的(n,k)二元循环码，捕错译码器已经把t个错误集中在Ri(x)的最低n-k位以内的充要条件，是此时的校验子矢量的汉明重量： W(Si(x)t证明：如果错误已经集中在最低n-k位以内，则Si(x)xiE(x)=Ei(x)=E

32、P(x) mod g(x)Si(x)=EP(x)由于这个(n,k)码只能纠t位错，所以，对于一个可纠正的错误图样，必有：W(E(x)t而E(x)的循环移位后，其矢量的汉明重量是不变的，则W(Si(x)=W(Ei(x)t这说明：只要能纠t位错的码已经把错误码元集中到最低n-k位上，公式W(Si(x)t就一定成立。反之；再证明：如果W(Si(x)t满足，则错误码元就一定集中在最低n-k位码元内了。利用反证法：§ 即当W(Si(x)t满足时，错误码元没有集中到码字的最低n-k位码元内，§ 则必有循环移位后的错误图样多项式Ei(x)的次数大于等于g(x)的次数。§ 进而有

33、：Ei(x)=q(x)g(x)+Si(x), 相应有：Ci(x)=Ei(x)+Si(x)=q(x)g(x)；这样组成的Ci(x)为g(x)的倍式，必然为一个码字多项式，§ 再由定理，线性分组码的最小码距等于非0码字的最小汉明重量，有：W(Ei(x)+Si(x)=W(Ci(x)d=2t+1 (已知码字可纠t位错)§ 由汉明三角不等式：对于一个(n,k)线性分组码C，C1,C2,C3为C中的三个码字，并为C3=C1+C2，这时有：d(C1,C2)d(C1,C3)+d(C3,C2)，或表示为W(C1+C2)W(C1)+W(C2)§ W(Ei(x)+W(Si(x)W(Ei

34、(x)+Si(x)d=2t+1§ 由已知W(Ei(x)t，所以得出W(Si(x)t+1>t；这与立题假设W(Si(x)t，矛盾，这说明当W(Si(x)t时，错误码元不可能不集中在码字的最低n-k位码元内。定理证毕。例题：已知二元(15,7)循环码，生成多项式g(x)=x8+x7+x6+x4+1，dmin=5，其纠错能力为t=2，可以纠两位错。由t=2<n/k=15/7，满足捕错译码的必要条件，可以用捕错译码方法进行译码。译码电路原理图如下：门1门2门58级缓存器7级缓存器门3门4W(Si(x)2检测电路译码过程如下：§ 译码前所有移位寄存器和缓存器都为全0状态，

35、门2，门3开，门1，门4，门5关。n=15次移位后，接收码字的R(x)的15个码元全部进入15级缓存器，信息元在前7级，监督元在后8级，同时进入除法电路，得到校验子多项式S0(x)。如果S0(x)=0，说明无错，打开门5，输出接收码字。如果S0(x)0，说明有错，进行以下各步。§ 此时门2关，门1开，如果W(S0(x)2，检测电路输出有效，把门4打开，把门3关闭，此时除法电路移位寄存器中的内容就是接收码字的后8位的错误图样，只要接收码字只错2位或2位以下，后8位错误图样就等于全部错误图样。这时移位15次，除法电路的状态S0(x)=EP(x)通过门4与接收码字的后8位逐次相加，完成纠错

36、。然后门1关，门5开，再移位15次，输出接收码字。§ 如果W(S0(x)>2，则15级缓存器和除法电路都循环移位一次，再次检测，若仍大于2，则继续移位，当移位I次后，检测到W(S0(x)2，则说明已经检测出错误图样已进入缓存器的后8位。这时门3关闭，门4打开，继续移位n-I次，进行纠错。最后门1关，门2，门5开，再移位15次输出正确的接收码字。从以上步骤中可以看出，译码器完成一个码字的译码，共需要3n次移位。这里介绍的是捕错译码器的基本原理，若要实现连续译码，还要进行一些改进，一方面力图使译码器电路简单化，另一方面提高译码速度，减少移位次数。6-3-3 大数逻辑译码循环码译码器

37、的复杂性取决于码的代数结构，对于一类循环码来说，有一种比较简单的译码方法称为大数逻辑译码，1954年由Reed提出。循环码的监督矩阵描述：前面我们介绍过，已知循环码的生成多项式g(x)，可以得到非系统循环码的生成矩阵。G(x)=xk-1g(x)xk-2g(x)g(x)相应的生成矩阵为：G=gn-kgn-k-1g1g0000gn-kgn-k-1g1g0000gn-kgn-k-1g1g0根据循环码的生成多项式一定为xn+1的因式，有xn+1=g(x)h(x)=(gn-kxn-k+g1x+g0)(hkxk+h1x+h0)根据这个关系可以看出：gn-khk=1g0h0=1而其它乘积项的系数为0。即g0

38、h1+g1h0=0g0h2+g1h1+g2h0=0gn-1h0+gn-2h1+gn-khk-1=0根据生成矩阵与监督矩阵的关系，可知H=h0h1hk0000h0h1hk00000h0h1hkH矩阵为n-k行n列。它完全由h(x)的系数决定的，h(x)称为循环码的校验多项式或称为监督多项式。生成矩阵与监督矩阵的关系为：GHT=0例如：(7,4)循环码的生成多项式g(x)=x3+x+1，而监督多项式为h(x)=x4+x2+x+1。相应的生成矩阵和监督矩阵分别为：G=1011000010110000101100001011H=111010001110100011101可以验证：GHT=0，还可以看出

39、，这个监督矩阵经过列变换可以变为系统码的监督矩阵，而且就是汉明码的一致监督矩阵。如果将这个码的生成矩阵当作另一个码的监督矩阵，而将这个码的监督矩阵当作另一个码的生成矩阵，这另一个码就是这个码的对偶码。例如：g(x)=x3+x2+1的(7,4)循环码，是g(x)=x4+x3+x2+1的(7,3)循环码的对偶码，g(x)=x3+x+1的(7,4)循环码，是g(x)=x4+x2+x+1的(7,3)循环码的对偶码。系统循环码的生成矩阵与监督矩阵：由于循环码的生成矩阵的每一行都为一个码字，系统循环码的生成矩阵的k个行向量分别为(100),(0100),.(0001)信息码对应的循环码字。因此，已知一个(

40、n,k)码的生成多项式，求出这些码字所对应的监督码元作为行向量的后r位，就可以得到生成矩阵的标准型。用多项式表示的生成多项式的标准型为：G(x)=xn-1r1(x)xn-2r2(x)xn-krk(x)其中r1(x)、r2(x)rk(x)分别为码字多项式xn-1，xn-2xn-k除以g(x)的余式多项式。生成矩阵标准型为：G=1 0 0r10 1 0r20 0 1rkr1 r2 rk分别为r1(x)、r2(x)rk(x)的向量形式。例如：二元(7,4)循环码的生成矩阵的标准型。由g(x)=x3+x+1r1(x)=xn-1/g(x)=x6/g(x)=x2+1 mod g(x) 对应矢量r1=101

41、。r2(x)=xn-2/g(x)=x5/g(x)=x2+x+1 mod g(x) 对应矢量r2=111。r3(x)=xn-3/g(x)=x4/g(x)=x2+x mod g(x) 对应矢量r3=110。r4(x)=xn-4/g(x)=x3/g(x)=x+1 mod g(x) 对应矢量r4=011。得到其生成矩阵的标准型为：G=1000101010011100101100001011看出G=Ik,Q，由GHT=0可得：系统循环码的监督矩阵为：H=111010001110101101001§ 到这里我们有两种办法得到系统线性分组码的生成矩阵标准型和监督矩阵；一种是上面介绍的已知g(x)的

42、方法，另一种是已知非标准型矩阵通过初等变换的方法。§ H矩阵通过列换位，可以变为标准型；§ G矩阵通过列换位和初等行变换，可以变为标准型。大数逻辑译码的原理：首先通过一个例子说明大数逻辑译码的基本思想。已知(7,3)线性分组码的生成多项式为：g(x)=x4+x3+x2+1，得到其监督矩阵为：H=1011000111010011000100110001设发送码字矢量为：C=(c6,c5,c4,c3,c2,c1,c0)，错误图样矢量为：E=(e6,e5,e4,e3,e2,e1,e0)，接收码字为R=C+E。相应的校验子为ST=HET=1011000e6=s31110100e5s

43、21100010s10110001e0s0利用这个方程组的线性组合（变换），得到另一组校验方程：A1=s3=e6+e4+e3A2=s1=e6+e5+e1A3=s2+s0=e6+e2+e0这三个方程组的系数构成三个矢量，(1011000),(1100010),(1000101)是H矩阵的行向量的线性组合，对于发送码字C，根据HCT=0，可知：A1CT=A2CT=A3CT=0，或c6=H0CT=01011000c511000101000101c1c0这样得到了一个新的校验方程：c6+c4+c3=0c6+c5+c1=0c6+c2+c0=0构造的这个监督方程组有这样一个特点：每个方程中都有c6，而c5,c4,c3,c2,c1,c0则在各方程中只出现一次。有这种特点的监督方程称为正交于c6的正交监督方程。其系数矩阵H0称为正交监督矩阵。H0=101100011000101000101定义：如果一个特定的码元(xn-i)出现在H0矩阵的每个行，而其它码元最多在其中一行中出现，则称H0为正交于码元(xn-i)的正交一致监督矩阵。(7,3)循环码能够纠正一位错，同时检出两位错。如果利用这个正交监督矩阵对接收码字进行校验，可以看到：§ 如果只发生一位错，且r6错，e6=1，则A1=A2=A3=1;§ 如果