教学课件第九章循环码.ppt

第九章第九章 循环码循环码第九章第九章 循环码循环码 内容提要循环码是线性分组码中一个重要的子类本章首先提出了循环码的定义以及循环码的多项式描述方法，论述了循环码构成的有关重要定理；接着讨论了循环码的编译码方法及其实现电路，最后介绍了已获得广泛应用的循环汉明码、BCH码等 9.1.1 循环码的定义循环码的定义 将任一码字中的7个码元排在一个圆周上，则从圆周的任一码元开始，按顺时针方向移动一周，都将构成该码的一个码字这就是循环码的由来见图9.1） 9.1 9.1 循环码的一般概念循环码的一般概念定义定义9.1 一个线性分组码，若具有下列特性，称为循环循环码码设码字c＝（cn-1，cn-2，…，c1，c0）若将码元左移一位，得c (1)＝（cn-2，…，c1，c0，cn-1）c (1)也是一个码字图9.1 （7，4）汉明码的码字循环图第二循环第一循环9.1.2 循环码的多项式描述循环码的多项式描述设c＝（cn-1 cn-2 … c1 c0）是（n，k）循环码的一个码字，则与其对应的多项式             c (x)＝cn-1xn-1＋cn-2xn-2＋…＋c1x＋c0 (9－1) 称为码字c的码字多项式码字多项式（或码多项式）。

  如果c＝（cn-1 cn-2 … c1 c0）是（n，k）循环码的一个码字，则c (1)＝（cn-2 …c1 c0 cn-1）也是该循环码的一个码字这就是说c (x)＝cn-1xn-1＋cn-2xn-2＋…＋c1x＋c0 和 c (1) (x)＝cn-2xn-1＋…＋c1x2＋c0x＋cn-1都是（n，k）循环码的码字多项式 比较c(x)和c (1) (x)后可得 c (1) (x)＝x c (x), mod xn－1                             (9－2)以及 c(i) (x)＝xic (x) （i＝1,2,…,n－1）, mod xn－1 (9－3) 定理定理9.1 在以多项式xn－1为模的剩余类全体所构成的n维线性空间Vn中，其一个子空间Vn,k是一个循环子空间（循环码）的充要条件是：Vn,k是一个理想 一个（n，k）循环码的码字多项式都是模xn－1运算下多项式剩余类环中的一个理想，而且一定是一个主理想子环。

反之，多项式剩余类环的一个主理想子环也一定生成一个循环码 9.1.3 9.1.3 循环码的生成多项式循环码的生成多项式定定理理9.2 GF(2)上的（n，k）循环码中，存在有唯一的n－k次首一多项式                g(x)＝xn-k ＋gn-k-1xn-k-1 ＋ … ＋ g1x＋g0使得每一个码多项式c (x)都是g(x)的倍式，且每一低于或等于n－1次的g(x)倍式，一定是码多项式 定理定理9.3 （n，k）循环码的生成多项式g(x)一定是xn－1的因式：xn－1＝g(x)h(x)反之，若g(x)为n－k次，且除尽xn－1，则此g(x)一定生成一个（n，k）循环码定义定义9.2 若一个循环码的所有码字多项式都是一个次数最低的非零首一多项式g(x)的倍式，则称g(x)生成该码，并称g(x)为该码的生成元或生成多项式定定理理9.4 若g(x)是（n，k）循环码的生成多项式，由xn－1＝g(x)h(x)，h(x)是k次多项式，称为校验多项式校验多项式令h(x)＝hkxk＋hk-1xk-1＋…＋h1x＋h0则 (9－5)为（n－k）n阶矩阵，称为码的校验矩阵校验矩阵。

①（n，k）循环码的生成多项式g(x)是一个次数最低的唯一的首一多项式，其次数r＝n－k正好是码字中校验元的数目；② 生成多项式g(x)是xn－1的因式要构造一个（n，k）循环码，就是要在xn－1的因式中找一个n－k次的首一多项式g(x)，它的一切倍式就构成一个（n，k）循环码反之，循环码的每一个码字多项式必是g(x)的倍式； 综上所述，有如下结论： ③ 由xn－1＝g(x)h(x)，h(x)称为校验多项式对于任意一个（n，k）循环码，必有g(x)h(x)＝0 mod xn－1及  G·H T＝ 0 循环码是线性分组码的一个子类因此，所有线性分组码的性质均适用于循环码 9.2 9.2 循环码的编码循环码的编码 9.2.1 9.2.1 利用生成多项式利用生成多项式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要编码成系统循环码形式，须用xn-k乘以m(x)，再加上校验元多项式r(x)，这样得到的码字多项式c(x)为： c(x)＝xn-k m(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)＝xn-km(x)， mod  g(x) (9－6)即r(x)必是x n-k m(x)除以g(x)的余式。

(9－6)式指出了系统循环码的编码方法：首先将信息元多项式m(x)乘以xn-k成为xn-km(x)；然后将xn-km(x)除以生成多项式g(x)得到余式r(x)，该余式就是校验元多项式，从而得到码字多项式c(x)＝xn-km(x)＋r(x)9.2.2 9.2.2 除法电路除法电路 设GF(2)上的二个多项式a(x)＝akxk＋ak-1xk-1＋…＋a1x＋a0b(x)＝brxr＋br-1xr-1＋…＋b1x＋b0a(x)是被除式，b(x)是除式用图9.2所示的电路完成a(x)除以b(x)的运算 图9.2 除法电路的一般形式 【例例9.2】设被除式a(x)＝x4＋x＋1，除式b(x)＝x3＋x2＋1，完成二个多项式相除的运算长除法： 多项式的系数运算 实现以上除法运算的除法电路如图9.3所示 图9.3 以b(x)＝x3＋x2＋1为除式的除法电路 9.2.3 编码电路编码电路    然后将xn-km(x)除以生成多项式g(x)得到余式r(x)，该余式就是校验元多项式，从而可得码字多项式c(x)＝xn-km(x)＋r(x) 系统循环码的编码方法是：  首先将信息元多项式m(x)乘以xn-k成为xn-km(x)；用电路实现编码时可采用以g(x)为除式的除法电路。

作为实例，图9.4示出了生成多项式g(x)＝x3＋x2＋1的（7，4）循环码的编码电路 图9.4 以g(x)＝x3＋x2＋1的（7，4）循环码编码器 9.3 9.3 循环码的译码循环码的译码 当码字c通过噪声信道传送时，会受到干扰而产生错误如信道产生的错误图样是e，译码器收到的n重接收矢量是y，则表示为y ＝ c ＋ e上式也可写成多项式形式： y(x)＝c(x)＋e(x) (9－7) 循环码的译码可按以下三个步骤进行：（２）（２）根据伴随式s(x)找出对应的估值错误图样 ；（３）（３）计算 ，得到估值码字 若，则译码正确，否则，若 ，则译码错误１）（１）由接收到的y(x)计算伴随式多项式s(x)；9.3.1 9.3.1 伴随式计算伴随式计算 对于（n，k）循环码，可以定义码的生成多项式g(x)除以接收码字多项式y(x)的余式为伴随式多项式s(x)，写 s(x)＝y(x) mod  g(x) (9－8)由于 y(x)＝c(x)＋e(x)而 c(x) mod  g(x)＝0于是 s(x)＝e(x) mod  g(x) (9－9) s(x)伴随式计算电路的一个重要性质：定定理理9.5 设s(x)是接收码字多项式r(x)的伴随式。

则y(x)的一次循环移位xy(x)（mod xn－1）的伴随式s(1)(x)，是s(x)在伴随式计算电路中无输入时，右移一位的结果（称为自发运算）： s(1)(x)＝xs(x) mod g(x) (9－11) 【例例9.3】以g(x)＝x4＋x3＋x2＋1为生成多项式的（7，3）循环码（示于表9.1），能纠正一个错误 设传送出现一个错，错误图样e＝（0 0 0 1 0 0 0），即e(x)＝x3，其伴随式 s(x)＝e(x) mod g(x)＝x3 mod (x4＋x3＋x2＋1)＝x3， 即s ＝（1 0 0 0）现设错误图样e1＝（0 0 1 0 0 0 0）,即e(1)(x)＝xe(x)＝x4，相应的伴随式s(1)(x)＝x4 mod (x4＋x3＋x2＋1)＝x3＋x2＋1,即s1＝（1 1 0 1）s1是s在图9.5所示的g(x)＝x4＋x3＋x2＋1除法电路中无输入时，右移一位的结果，也即自发运算的结果。

图9.5 （7，3）循环码的伴随式计算电路 9.3.2 循环码的译码循环码的译码 把某一可纠正的错误图样e(x)及其所有的小于等于n－1次的循环移位归成一类，用一个错误图样来代表译码时只要计算这个错误图样的伴随式，该类中其它错误图样的伴随式都可由该伴随式在g(x)除法电路中循环移位来得到       以（7，3）循环码为例： 当码字传送出现一个错误时，若用一般译码器需要识别如（0 0 0 0 0 0 1），（0 0 0 0 0 1 0），（0 0 0 0 1 0 0），（0 0 0 1 0 0 0），（0 0 1 0 0 0 0），（0 1 0 0 0 0 0），（1 0 0 0 0 0 0）等7个不同的错误图样，但对于按上述定理设计的循环码译码器来说，可以把这些错误图样归成一类，译码器只要识别其中的一个错误图样就可以了若（7，3）循环码译码器按错误图样（1 0 0 0 0 0 0）设计，于是s(x)＝e(x) mod g(x)＝x6 mod (x4＋x3＋x2＋1)＝x3＋x2＋x， 即s＝（1 1 1 0）其译码器电路示于图9.6。

图9.6 （7，3）循环码译码器 9.3.3 Meggit译码器译码器 循环码译码器的缺点无法对接收到的码字实现连续的译码输出改进的译码器称作Meggit通用译码器通用译码器，其结构如图9.7，可实现连续的译码输出 图9.7 Meggit通用译码器 9.4.1 循环循环Hamming码码 定义定义9.3 设是GF(2m)上的一个本原元，则以的本原多项式为生成多项式的（2m－1，2m－1－m）Hamming码是循环码 码的校验矩阵为 (9－13）  因码长n＝2m－1，H也可以表为 (9－14)9.4 9.4 一些重要的循环码一些重要的循环码例如，以GF(23)上的三次本原多项式为生成 多 项 式 ， 可 生 成 一 个 （ 7， 4） 循 环Hamming码，其生成多项式g(x)＝x3＋x＋1设是GF(23)上的本原元，则码的校验矩阵9.4.2 BCH码码定定义义9.49.4 设是GF(2m)上的一个本原元，t为整数，则以含有、2、……2t等共2t个根，其系数在GF(2)上的最低次多项式g(x)为生成多项式的循环码，叫做二元本原二元本原BCHBCH码码。

码长n＝2m－1校验位数r＝n－k  mt最小距离d  2t＋1纠错能力为t二元本原BCH码的参数为： (9－17) 【例例9.4】设m＝4，是GF(24)上的本原元，求码长n＝24－1＝15的二元本原BCH码 若t＝1，则码以为根，即以，2，4，8共轭根系为根， 最小多项式 m1(x)＝x4＋x＋1 生成多项式 g(x)＝m1(x)＝x4＋x＋1校验位数目n－k＝4 码的校验矩阵为若t＝2，则码以，3为根，即以，2，4，8共轭根系和3，6，12，24＝ 9共轭根系为根，最小多项式m3(x)＝x4＋x3＋x2＋x＋1生成多项式 g(x)＝m1(x)m3(x) ＝(x4＋x＋1)( x4＋x3＋x2＋x＋1)                                  ＝x8＋x7＋x6＋x4＋1校验位数目n－k＝8 ，其校验矩阵 ；若t＝3，则码以，3，5为根，即以，2，4，8共轭根系、3，6，12，24＝9共轭根系和5，10共轭根系为根，最小多项式m5(x)＝x2＋x＋1生成多项式 g(x)＝m1(x)m3(x)m5(x)                              ＝(x4＋x＋1)( x4＋x3＋x2＋x＋1)(x2＋x＋1)                              ＝x10＋x8＋x5＋x4＋x2＋x＋1校验位数目n－k＝10 ，其校验矩阵 循环码是线性分组码中一个重要的子类，由于这种码的代数结构完全建立在有限域基础上，它是目前理论上最为成熟的一类码。

本章的主要内容有：本本 章章 小小 结结（2）循环码的性质：循环码的生成多项式，生成多项式的重要性质，由生成多项式构造生成矩阵1）循环码的定义及多项式描述：循环码的循环特性，循 环码的码字多项式，循环码是多项式剩余类环的一个主理想子环（5）循环Hamming码和BCH码：用g(x)的根定义循环码，建立在有限域扩域上的BCH码4）循环码的译码：伴随式的计算电路，自发运算电路，Meggit译码器3）循环码的编码：用生成多项式编码的理论，除法电路，循环码的编码电路。