《信息论与编码第三版 第8章讲解》由会员分享，可在线阅读，更多相关《信息论与编码第三版 第8章讲解（27页珍藏版）》请在金锄头文库上搜索。
1、第八章 循 环 码,内容提要,循环码是线性分组码中一个重要的子类。 本章将介绍循环码的基本概念以及循环码的多项式描述方法；循环码的基本定理及其矩阵描述 。,8.1循环码的概念,一定义,设一个（n，k）线性分组码C，如果它的任一码矢量的每一次循环移位都还是C的一个码字，则称C是循环码。,由于循环码是线性分组码，所有这些具有循环关系的码字的全体构成了n维矢量空间中具有循环特性的k维字空间。,【例】（7，3）线性分组码,由： 得,由两组码字循环构成的循环码。,二循环码的数学描述,1循环码的特点：,（1）它是线性分组码，其数学模型应具有线性特性；,（2）具有循环特性。,故循环码的数学模型必须能兼容线性
2、和循环特性多项式描述。,2线性分组码的多项式描述,对于线性分组码C，可以表示成码字多项式构成的集合：,3循环特性的表示,以前面的（7，3）循环码为例：（任取一码字）,下面用 去除 ，得余,对于上面第三次移位结果，可重新表示如下：,结论：如果把一个循环码得某一非零码字多项式表示出来后，那么其他的非零码字多项式就可以用这个码字多项式（或码字多项式的和）乘上x的一个幂，再求（xn+1）的余得到 。,说明：一个码字的移位最多能得到n个码字，因此“循环码字的循环仍是码字”并不意味着循环码集可以从一个码字循环而得，还应包含码字的一些线性组合。,8.2 循环码的基本定理及其矩阵描述,一循环码的生成多项式,1
3、定义：一个（n，k）循环码的所有码多项式都可以由其中一个码多项式的倍式组成，称该码多项式为对应循环码的生成多项式。生成多项式不是唯一的，但总有一个是次数最低的。,两个结论：,2（n，k）循环码的构造,（1）对x n + 1做因式分解，找出n - k次因式； （2）以该n - k次因式为生成多项式g(x)与不高于k 1次信息多项式u(x)相乘，即得到对应消息的码多项式。,【例】一个长度n = 7的循环码的构造方法。,（1）对x 7 + 1作因式分解,故x 7 + 1有如下因式：,n k = 1，k = 6，生成一种（7，6）循环码； n k = 3，k = 4，生成两种（7，4）循环码； n k
4、 = 4，k = 3，生成两种（7，3）循环码； n k = 6，k = 1，生成一种（7，1）循环码；,例：要得到一（7，4）循环码，可选n k = 3次多项式1 + x2 + x3或1 + x +x3 为生成多项式：,以g（x）= 1 + x2 + x3为例，（信息位长度为4）,设信息多项式为：,则：循环码编码后的码多项式为：,（2）若以n - k次因式作为生成多项式，可供选择的有,例：,对于上述（7，4）循环码，有4个信息位，对应有16个信息序列，利用16个信息序列多项式与生成多项式的乘法运算，可得全部（7，4）循环码得16个码字，如表：,二循环码的生成矩阵,（n，k）循环码是n维线性空
5、间一个具有循环特性的k维的子空间，故（n，k）循环码的生成矩阵可用码空间中任一组k个线性无关的码字构成，即k个线性无关的码字构成（n，k）循环码的基底，基底不唯一。,如何得到k个线性无关的码字？,方法：当循环码的生成多项式g（x）给定后，可以取g（x）本身加上移位k 1次所得到的k 1码字作为k个基底，即：,构成基底,若：,则：,各多项式对应的矢量分别为：,这k个矢量是线性无关的，且由g（x）循环移位得到，故都是码字，由它们构成一个kn的矩阵，它们就是循环码的生成矩阵。,【例】（7，4）循环码：,当一个循环码的生成矩阵确定后，其编码规则为：,如：,三循环码的系统码,由上述方法作出的生成矩阵所编
6、出的码不是系统形式，如何得到系统形式的循环码？,1系统循环码的编码：,设,用x n k 和u（x）相乘，再除以g (x),（ 次数）,设：,则：,a(x)g(x)是g(x)的一个倍式，则它是一个码多项式，对应的码矢量为：,码矢量为系统形式的码字，信息位在尾部。, 系统码的编码步骤：,（1）用x n k 乘以消息u（x）； （2）用生成多项式g（x）除x n k u（x）得余 b（x）（一致校验元）； （3）联合b( x )和x n k u( x )得到系统码多项式 c(x)= b( x )+ x n k u( x )； （4）将码多项式转换为码字。,（1）,（2）,（3）,（4）,2系统码的生
7、成矩阵,（1）由生成矩阵做初等行变换，将其变为 形式，即为系统形式的生成矩阵（单位阵在后，信息位在尾部）。,（2）分别求g（x）除 的余式（记为） ，由余式对应的矢量作行矢量构成的kn-k的分块矩阵 P 联合kk的单位阵 I 就构成系统形式的生成矩阵：,四循环码的校验矩阵,一般情况下，多项式xn+1可因式分解为xn+1 = g (x) h (x),g (x) （n，k）循环码的生成多项式，,h (x) （n，k）循环码的一致校验多项式，,在因式分解中，g (x)和h (x)处于同等地位，既可以用g (x)去生成一个循环码，也可以用h (x)去生成一个循环码。,设由g (x)生成的码为C，在由h
8、 (x)生成的码就是C的对偶码C。,设,则：,将上述矢量按逆序排列作为一个（n-k）n矩阵的行矢量，则该矩阵就是码C的校验矩阵。,【例】（7，4）循环码：,则：C的基底（n-k-1=2）, 系统形式的校验矩阵,（1）对非系统形式的校验矩阵作初等行变换，变成 I n-k，PT 的形式；,（2）分别求h（x）除 的余式（记为） ，由余式对应的逆矢量可得到系统形式的校验矩阵：,（3）,【例】（7，4）循环码：,（1）,（2）k = 4，n k 1 = 2,（3）, 8.4 循环码译码,一译码步骤：,和线性分组码一样，循环码译码步骤分三步： （1）计算接收多项式r（x）的伴随多项式s（x）； （2）根
9、据s（x）找出相应错误图样多项式e（x）； （3）将e（x）和r（x）模2加，得到译码输出c（x）。,二伴随式计算及错误检测,伴随式及计算,设接收多项式为r (x)，码多项式为c (x)，错误图样多项式为e (x)，则,用生成多项式g（x）除r（x），得,（求余运算）,【定理】设g (x)是(n，k)系统循环码的生成多项式，接收字多项式为 r (x)，对应错误图样为e（x），则,且它们的系数就是该系统码的伴随式。即,由于码的循环结构，伴随式有个重要的性质，用定理描述。,【定理】设s (x)是r (x)的伴随式，则r (x)的循环移位 x r (x)的伴随式s(1) (x)是s (x)在伴随式计算电路中无输入时右移一位的结果，即：,【推论】用生成多项式g (x)除x i s (x)所得余式s(i) (x)是r (x)经 i 次移位后r (i) (x)的伴随式。,
