[信息与通信]7循环码A.pdf

编码理论 循环码 一种特殊的线性分组码 • 循环算子L ：对n重码字A=(a , a , a , … , a , a , a ) ，有 n-1 n-2 n-3 2 1 0 B = L(A) = (b , b , b , … , b , b , b ) = (a , a , … , a , n-1 n-2 n-3 2 1 0 n-2 n-3 2 a , a , a ) 1 0 n-1 • 循环码：一个(n,k )线性码C，如果每个码字的循环移位 L(C)仍是一个码字,称该码为循环码。 循环码的描述 • 问题：如何构造和描述一个循环码？满足什么样 条件的循环码可以有较好的距离特性？ 多项式的引入 • 如果将码字描述成n阶多项式的形式， n-1 n-2 n-3 2 A(x)= a x +a x +a x + … +a x +a ,x+a n-1 n-2 n-3 2 1 0 n 则循环算法就可以描述为L(A(x))=xA(x) mod (x -1) 便于描述：对任何一个多项式D(x) ，有D(x)A(x) n mod (x -1)为许用码字，这里并没有限定D(x) 的幂次， n 但可以肯定的一点是不同的D(x)A(x) mod (x -1)是有 限的，其个数由A(x)决定，这也决定了码集的纠错 能力。 什么样的A(x)可以得到什么样的纠错能力？ 哪些A(x)是等价的？ 第一节多项式与多项式环 要求掌握的内容 • 多项式剩余类环 • 循环群 一、复习几个概念 • 同余、剩余类 • 群 • 环 • 域 环(Ring)的定义 • 非空集合R中，若定义了两种代数运算加和 乘，且满足： 1) 集合R在加法运算下构成阿贝尔群 2) 乘法有封闭性 3) 乘法结合律成立，且加和乘之间有分配 律 子环、理想和主理想 子环：若环R中的子集S，在环R中的定义的代数运算也构 成环，则称S为R的子环。 理想：S是R的一个子环，若S 中的元素由某几个元素及其 所有可能的倍数构成，则S是一个理想 主理想：若理想中的元素由一个元素的所有倍数及其线性 组合生成，则称这个理想为主理想。 二、多项式剩余类环 • 有关多项式的几个概念 • 多项式的加法和乘法 • 多项式剩余类环的定义 有关多项式的几个概念 • 多项式 n n-1 f (x)=f x + f x +…+ f x+f n n-1 1 0 其中f i Fp i=0,1,…n，该多项式称为域F 上的多项式 p • 多项式次数degf(x) 系数不为零的x 的最高次数称为多项式f(x)的次数 • 首一多项式 最高次数的系数为1的多项式