发布时间 : 星期日 文章循环码的编译码方法..更新完毕开始阅读f732a599db38376baf1ffc4ffe4733687e21fcf9
二 循环码编译码的基本原理
2.1循环码的简介
更好的设计和实现线性分组码的方法是引入特定的数学结构来界定某一类线性分组码。循环码即是采用循环移位特性界定的一类线性分组码。它是线性分组码的一种，所以它具有线性分组码的一般特性，此外还具有循环性。
循环码的编码和解码设备都不太复杂，检、纠错能力强，而且性能好。它不但可以检测随机的错误，还可以检测突发的错误。?n,k?循环码可以检测长为n?k或更短的任何突发错误，包括首尾相接突发错误。
循环码是一种无权码，循环码编排的特点是相邻两个数码之间符合卡诺图中的邻接条件，即相邻两个数码之间只有一位码元不同（码元就是组成数码的单元）。循环码的优点是没有瞬时错误，因为在数码变换过程中，在速度上会有快有慢，中间经过其它一些数码形式，称它们为瞬时错误。这在某些数字系统中是不允许的，为此希望相邻两个数码之间仅有一位码元不同，即满足邻接条件，这样就不会产生瞬时错误。循环码就是这样一种编码，它可以在卡诺图中依次循环得到。循环码又称格雷码（Gray Code）。 2.1.1循环码的定义
设C是某?n,k?线性分组码的码字集合，如果对任何
C?(cn?1,cn?2,?,c0)?C，它
(1)C?(cn?2,cn?3,?c0,cn?1)也属于C，则称该n,k码为循环码。 的循环移位??该码在结构上有另外的限制，即一个码字任意循环移位后的结果仍是一个有效码字。其特点是：可以用反馈移位寄存器很容易实现编码和伴随式的计算；由于循环码有很多固有的代数结构，从而可以找到各种简单使用的译码办法。
如果一个?n,k?线性码具有以下的属性，则称为循环码：如果n元组
c?{c0,c1,?,cn?1}(1)c?{cn?1,c0,?,cn?2}也同样是
是子空间S的一个码字，则经过循环移位之后得到的
子空间S中的一个码字；或者，一般来说，经过j次循环移位之后得到的
c(j)?{cn?j,cn?j?1,?,cn?1,c0,c1,?,cn?j?1}也是子空间S中的一个码字。
2
2.1.2线性分组码与循环码的区别
线性分组码是同时具有分组特性（码字和消息长度恒定）和线性特性（消息相加后的编码等于各自编码后相加）的纠错码。每个监督码元都是码组中某些信息码元的线性相加得到的。将q元符号按每k个分为一组．然后通过编码得到n-k个q元符号作为冗余校验符号，最后由校验符号和信息符号组成有n个q元符号的码字符号。得到的码字可以纠正t个错误，编码效率为k/n。两个属于该码的码字之和仍是一个属于该码的码字，全零码字总是一个码字，一个线性码的两个码字之间的最小距离等于任何非零码字的最小汉明重量。
循环码是采用循环移位特性界定的一类线性分组码。是线性分组码的一个重要子类；BCH码是其主要的一大类；汉明码、R-M码、RS码等可变换；纳入循环码内，Goppa码的一个子类也属于循环码；用反馈线性移位寄存器可容易的实现其编码和得到伴随式；由于数学上的特性，译码方法简单。循环码的特点有两点：一是封闭性（如果c1，c2，是与消息m1，m2对应的码字，则c1+c2必定是与m1+m2对应的码字）；二是循环性（任一许用码组经过循环移位后所得到的码组仍为该许用码组集合中的一个码组）。 2.1.3循环码的最小码距
对于分组码一般用符号（n，k）表示，其中n是码组的总位数，又称为码组的长度即码长，k是码组中信息码元的数目，n–k为码组中的监督码元数目，用字母r表示。分组码（n，k）当信息码元与监督码元之间的关系为线性关系时，这种分组码就称为线性分组码。
在分组码中，把码组中“1”的个数目称为码组的重量，简称码重。编码中所有码字重量的集合形成该码的重量分布。如果全部M个码字都具有相同的重量，这种码叫做固定重量码，或叫恒重码。把两个码组中对应位上数字不同的位数称为码组的距离，简称码距，码距又称汉明距离。
一般而言，对于任意一种编码，其中各个码组之间的距离不一定相等。这时，将其中最小的距离称为最小码距，用dmin来表示。 2.1.4循环码的检纠错能力
一种编码的纠错，检错能力决定于最小码距dmin的值。下面将用几何关系证明纠错，
3
检错能力和最小码距的关系。
为了能检测e个错码，要求最小码距：
dmin?e?1纠正t个错误，要求最小码距
(2-1)
dmin?2t?1为纠正t个错码，同时检测e个错码，则要求最小码距
(2-2)
dmin?e?t?1以出其纠检错能力，其最多可检4位错，可纠2位错。
(2-3)
本课程设计中采用（15,7）循环码由生成矩阵可得其最小码距dmin为5，由最小码距可
2.2 循环码编译码原理及过程
循环码是线性分组码的一个重要子集，是目前研究得最成熟的一类码，它有许多特殊的代数性质，这些性质有助于按所要求的纠错能力系统的构造这类码，且易于实现，所以循环码受到人类的高度重视，在前向纠错系统（FEC）中得到了广泛的应用。 2.2.1循环码的编译码原理
循环码最大的特点就是码字的循环特性，所谓循环特性是指：循环码中任一许用码组经过循环移位后，所得到的码组仍然是许用码组，也就是说，不论是左移还是右移，也不论移多少位，仍然是许用的循环码组。
?n,k?循环码的生成多项式写为g?x?,它是?n,k?循环码码集中唯一的，幂次为n?k的码多项式，则xkg?x?是一个幂次为n的码多项式。按模xn?1运算，此时：
xkg?x?R?x??Qx???n
xn?1x?1（2-4）
即xkg?x??R?x?，且因xkg?x?也是n次幂，故Q?x??1。由于它是循环码，故
xkg?x?按模xn?1运算后的“余式”也是循环码的一个码字，它必能被g?x?整除，即：
R(x)?F?x?
G(x)（2-5）
由以上两式可以得到：
4
xkg?x??Q?x??xn?1??R?x???xn?1??F?x?G?x?
xn?1??xk?F?x??G?x?
（2-6） （2-7）
从上式中可以看出，生成多项式g?x?应该是xn?1的一个因式，即循环码多项式应该是xn?1的一个n?k次因式。
由生成多项式可以得出相应的典型生成矩阵及标准监督矩阵：
?10??01G????00??bk?1,n?k?1??H???bk?1,1??bk?1,0000bbk?1,n?k?1k?2,n?k?1bbk?1,1k?2,1bbb0,n?k?1bb0,n?k?10,1??k?2,0?? ?b0,0??k?1,0（2-8）
bk?2,n?k?1100
bbk?2,1k?2,0bb0,10,000???10?
?01??3（2-9）
例如已知（7，4）循环码的生成多项式和校验多项式分别为：g?x??x?x?1，
h?x??x4?x2?x?1。写得其生成矩阵和校验矩阵分别为：
?1 0 1 1 0 0 0??0 1 0 1 1 0 0??G???0 0 1 0 1 1 0 ????0 0 0 1 0 1 1?
（2-10）
?1 1 1 0 1 0 0??H??0 1 1 1 0 1 0????0 0 1 1 0 0 1??
（2-11）
2.2.2 循环码编译码的
循环码的编译码过程如下： （1）编码过程
5