循环码（9，3）码课程设计一、摘要：本报告详细给出了循环码的定义以及由生成多项式求解生成矩阵和系统生成矩阵的过程，并在Matlab 环境下写出了循环码的编码器和解码器代码，实现了编码和译码功能。

分析和讨论了此码发现错误、纠正错误的能力，并讨论了其与线性分组码、Hamming 码等信道编码的区别与联系。

二、关键字：循环码 编码 译码 检错 纠错 Matlab三、基本概念：更好的设计和实现线性分组码的方法是引入特定的数学结构来界定某一类线性分组码。

循环码即是采用循环移位特性界定的一类线性分组码。

循环码定义：设C 使某(n,k)线性分组码的码字集合，如果对任何C c c c C n n ∈=--),,,(021 ，它的循环移位),,,(1032)1(---=n n n c c c c C 也属于C ，则称该（n,k ）码为循环码。

该码在结构上有另外的限制，即一个码字任意循环移位的结果仍是一个有效码字。

其特点是：（1）可以用反馈移位寄存器很容易实现编码和伴随式的计算；（2）由于循环码有很多固有的代数结构，从而可以找到各种简单使用的译码办法。

如果一个（n,k ）线性码具有以下的属性，则称为循环码：如果n 元组},,,{110-=n c c c c 是子空间S 的一个码字，则经过循环移位得到的},,,{201)1(--=n n c c c c 也同样是S 中的一个码字；或者，一般来说，经过j次循环移位后得到的},,,,,,,{11011)(---+--=j n n j n j n j c c c c c c c 也是S 中的一个码字。

循环码的多项式描述：码字的多项式描述，一个n 元码字可以用一个次数不超过n-1的多项式唯一表示)(0121c c c c c n n --=0112211)(c x c x c x c x c n n n n ++++=----其中，我们不关心x 的具体位置，其次数只表示相应码元的位置。

称这样的c(x)为c 的码字多项式。

生成多项式g(x)及生成矩阵G ：如果一种码的所有码多项式都是多项式g(x)的倍式，则称g(x)为该码的生成多项式。

在循环码中，次数最低的多项式（0除外）就是生成多项式g(x)，其他码多项式都是其倍数。

且该g(x)的阶数为r=n-k ，常数项为1，是n x +1的一个因式。

为了寻求生成多项式，必须对nx +1进行因式分解。

循环码的生成矩阵多项式为：⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡=--)()()()()(21X g X Xg X g X X g X X G k k然后将系数提出就得到生成矩阵G 。

系统循环码：循环码也可以构成为系统循环码。

为方便系统码的构造，将消息多项式和码式都记为高位在前，即),,,,(0121m m m m m k k ⋅⋅⋅=--的消息多项式为m(x)，1110)(--+++=k k x m x m m x m又设码式的高幂次部分等于m(x)，即)()()(111110x p x m x x c x c x c x c c x c k n n n k n k n k n k n +⋅=++++++=---+-+--- k n r x p -=<∂)(其中p(x)称为校验位多项式，由于码式是生成式的倍式，所以))((mod 0)()()()(x g x g x a x m x x p k n ==+-))()(mod ()(x g x m x x p r ⋅-=因此循环码的系统码码式为))]((mod )([)()(x g x m x x m x x c rr-=将循环码的系统码构造步骤总结为多项式乘))(()(x m x x m x r r =多项式求模（余式）)())())(m od ((x p x g x m x r =多项式减)()())((x c x p x m x r =-如果令)(x m 为单项式1+r x ，1,,1,0-=k irx p x p x g x a x i i r <∂+=+)(),()()(1ir i i x x p x c ++=)()(那么容易看到，)(x c i 对应的向量ic ，1,,1,0-=k i 是线性无关的，从而得到循环码系统码的生成矩阵sG 为⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=------1000100011,11,10,11,111101,00100r k k k r r s p p p p p p p p p G循环码的编码：利用生成多项式g(x)实现编码：如上所述，但循环码的生成多项式g(x)确定时，码就完全确定了。

现在讨论生成多项式g(x)给定以后，如何实现循环码的编码问题。

若已知 g(x)=gn-kxn-k+gn-k-1xn-k-1+...g1x+g0 并设信息元多项式 m(x)=mk-1xk-1+mk-2xk-2+...m1x+m0要编码成系统循环码形式，即码字的最左边k 位是信息元，其余n-k 位是校验元，则要用xn-k 乘以m(x)，再加上校验元多项式r(x),这样得到的码字多项式c(x)为c(x)=xn-km(x)+r(x)=mk-1xn-1+mk-2xn-2+...m0xn-k+rn-k-1xn-k-1+...r1x+r0其中 r(x)=rn-k-1xn-k-1+...r1x+r0 c(x)一定是g(x)的倍式，即有c(x)=xn-km(x)+r(x)=q(x)g(x) c(x)=xn-km(x)+r(x)=0. mod g(x)注意到g(x)为n-k 次多项式，而r(x)最多为n-k-1次多项式，必有 r(x)=xm(x), mod g(x) （1） 即r(x)必是xn-km(x)除以g(x)的余式。

式(1)指出了系统循环码的编码方法：首先将信息元多项式m(x)乘以xn-k 成为xn-km(x)，然后将xn-km(x)除以生成多项式)(x g 得到余式r(x)，该余式就是校验元多项式，从而得到码字多项式)()()(x r x km xn x c +-=。

综上所述，系统循环码的编码问题，可以归结为两个多项式的除法运算，即将xn-km(x)除以生成多项式g(x)得到余式r(x)的运算，因此研究多项式除法的电路实现是必要的。

检错纠错能力：若纠错码的最小距离为min d ，那么如下三个结论的任何一个结论独立成立。

（1）可以检测出任意小于等于1dim -=d l 个差错； （2）可以纠正任意小于等于)]1(2/1[min -=d t 个差错；（3）可以检测出任意小于等于l 同时纠正小于等于t 个差错，其中l 和t 满足：11min -≤+d t 和1<t编码器·译码器 原理图： 编码器原理图：译码器原理图：输入R已知生成矩阵G 如下，列出S 与E 的对照表。

当收到码组[]001011001=B 时，解出对应的信息码组D⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡=100100100010010010001001001G⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡=100000100010000010001000001000100100000010010000001001H ⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡=100000010000001000000100000010000001100100010010001001T HS 有62种形式，相应的码重最小的E 矢量有62种。

S 与E 的对照表如下：[][]000010100000010000001000000100000010000001100000010010001001001011001=⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡==T BH S查表可知，E 矢量为：[]000010000=E所以正确的码组A 为：[]001001001=⊕=-=E B E B A 所以信息码组为：[]001001=S由生成多项式求解生成矩阵的过程：已知：（9，3）循环码的生成多项式为1)(36++=x x x G ,求生成矩阵及系统码生成矩阵。

解：由生成多项式可得生成矩阵为⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡=100100100010010010001001001G 则系统码生成矩阵为⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡=100100100010010010001001001s G发现错误能力及纠正错误能力。

由生成矩阵得纠错码的最小距离3min =d ，则： （1）可以检测出任意小于等于l=2个差错； （2）可以纠正任意小于等于t=1个差错；（3）可以检测出任意小于等于2同时纠正小于等于1个差错。

循环码和线性分组码、Hamming 码的区别、联系：线性分组码：是同时具有分组特性（码子和消息长度恒定）和线性特性（消息相加后的编码等于各自编码后相加）的纠错码。

每个监督码元都是码组中某些信息码元的线性相加得到的。

将q 元符号按每k 个分为一组．然后通过编码得到n-k 个q 元符号作为冗余校验符号，最后由校验符号和信息符号组成有n 个q 元符号的码字符号。

得到的码字可以纠正t 个错误，编码码率为为k/n 。

两个属于该码的码字的和仍是一个属于该码的码字，全零字总是一个码字，一个线性码的两个码字之间的最小距离等于任何非零码字的最小汉明重量。

循环码：是采用循环移位特性界定的一类线性分组码。

是线性分组码的一个重要子类；BCH 码是其主要的一大类；汉明码、R-M 码、Golay 码、RS 码等可变换；纳入循环码内，Goppa 码的一个子类也属于循环码；用反馈线性移位寄存器可以容易的实现其编码和得到伴随式；由于数学上的特性，译码方法简单。

设C 使某(n,k)线性分组码的码字集合，如果对任何C c c c C n n ∈=--),,,(021 ，它的循环移位),,,,(1032)1(---=n n n c c c c C 也属于C 。

该码在结构上有另外的限制，即一个码字任意循环移位的结果仍是一个有效码字。

Hamming 码：汉明码是一种能纠正一位错码的线性分组码且是一类高效率的纠错码。

当m=3时，n=7，k=4。

线性分组码中的(7,4)码就是汉明码。

汉明码的译码电路利用最小码重错误图样进行译码的电路实现；利用校正子与错码位置的对应关系，也可以使用地址译码器来帮助实现译码。

循环码的MATLAB 仿真编码器和译码器的MATLAB 编写1、编码器Matlab编写m=input('输入m矩阵')G=[1 0 0 1 0 0 1 0 0;0 1 0 0 1 0 0 1 0;0 0 1 0 0 1 0 0 1] c=m*Gmod(c,2)c1=[0 0 0]*Ga1=mod(c1,2)c2=[0 0 1]*Ga2=mod(c2,2)c3=[0 1 0]*Ga3=mod(c3,2)c4=[0 1 1]*Ga4=mod(c4,2)c5=[1 0 0]*Ga5=mod(c5,2)c6=[1 0 1]*Ga6=mod(c6,2)c7=[1 1 0]*Ga7=mod(c7,2)c8=[1 1 1]*Ga8=mod(c8,2)M=[a1;a2;a3;a4;a5;a6;a7;a8]2、译码器的Matlab编写R=input('请输入R矩阵')b1=mod(R+a1,2)k1=find(b1==1)y1=length(k1)b2=mod(R+a2,2)k2=find(b2==1)y2=length(k2)b3=mod(R+a3,2)k3=find(b3==1)y3=length(k3)b4=mod(R+a4,2)k4=find(b4==1)y4=length(k4)b5=mod(R+a5,2)k5=find(b5==1)y5=length(k5)b6=mod(R+a6,2)k6=find(b6==1)y6=length(k6)b7=mod(R+a7,2)k7=find(b7==1)y7=length(k7)b8=mod(R+a8,2)k8=find(b8==1)y8=length(k8)L=[y1 y2 y3 y4 y5 y6 y7 y8][g,n]=min(L)X=M(n,:)m1=X(:,1:3)运行结果：输入m矩阵[ 1 0 1 ]m =1 0 1ans =Columns 1 through 71 0 1 1 0 1 1Columns 8 through 90 1M =Columns 1 through 70 0 0 0 0 0 00 0 1 0 0 1 00 1 0 0 1 0 00 1 1 0 1 1 01 0 0 1 0 0 11 0 1 1 0 1 11 1 0 1 1 0 11 1 1 1 1 1 1Columns 8 through 90 00 11 01 10 00 11 01 1请输入R矩阵[ 0 0 1 0 0 1 0 0 1 ]R =Columns 1 through 70 0 1 0 0 1 0Columns 8 through 90 1L =Columns 1 through 73 0 6 3 6 3 9Column 86g =n =2X =Columns 1 through 70 0 1 0 0 1 0Columns 8 through 90 1m1 =0 0 1参考文献：陈运主编《信息论与编码》（第2版）——电子工业出版社参与人员：吕远李东廖东杨剑李泉源。