第九章循环码.ppt

例如，以GF(23)上的三次本原多项式为生成多项式，可生成一个（7，4）循环Hamming码，其生成多项式g(x)＝x3＋x＋1。 设?是GF(23)上的本原元，则码的校验矩阵 ?循环码是线性分组码中一个重要的子类，由于这种码的代数结构完全建立在有限域基础上，它是目前理论上最为成熟的一类码。本章的主要内容有： 本 章 小 结 （2）循环码的性质：循环码的生成多项式，生成多项式的重要性质，由生成多项式构造生成矩阵。 （1）循环码的定义及多项式描述：循环码的循环特性，循 环码的码字多项式，循环码是多项式剩余类环的一个 主理想子环。 （5）循环Hamming码和BCH码：用g(x)的根定义循环码，建立在有限域扩域上的BCH码。 （4）循环码的译码：伴随式的计算电路，自发运算电路，Meggit译码器。 （3）循环码的编码：用生成多项式编码的理论，除法电路，循环码的编码电路。 人有了知识，就会具备各种分析能力， 明辨是非的能力。 所以我们要勤恳读书，广泛阅读， 古人说“书中自有黄金屋。 ”通过阅读科技书籍，我们能丰富知识， 培养逻辑思维能力； 通过阅读文学作品，我们能提高文学鉴赏水平， 培养文学情趣； 通过阅读报刊，我们能增长见识，扩大自己的知识面。 有许多书籍还能培养我们的道德情操， 给我们巨大的精神力量， 鼓舞我们前进。 * 第九章 循环码 第九章 循环码 内容提要 循环码是线性分组码中一个重要的子类。本章首先提出了循环码的定义以及循环码的多项式描述方法，论述了循环码构成的有关重要定理；接着讨论了循环码的编译码方法及其实现电路，最后介绍了已获得广泛应用的循环汉明码等。 9.1.1 循环码的定义 将任一码字中的7个码元排在一个圆周上，则从圆周的任一码元开始，按顺时针方向移动一周，都将构成该码的一个码字。这就是循环码的由来。（见图9.1） 9.1 循环码的一般概念 定义9.1 一个线性分组码，若具有下列特性，称为循环码。设码字 c＝（cn-1，cn-2，…，c1，c0） 若将码元左移一位，得 c (1)＝（cn-2，…，c1，c0，cn-1） c (1)也是一个码字。 表 8-2 (7,4)码的码字表 图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.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