西电纠错码课件---第四章 多项式环及循环码.pptVIP

第四章 多项式环与循环码 一种特殊的线性分组码 循环算子L：对n重码字A=(an-1, an-2, an-3, … , a2, a1, a0)，有B = L(A) = (bn-1, bn-2, bn-3, … , b2, b1, b0) = (an-2, an-3, … , a2, a1, a0, an-1) 循环特性：对任意许用码字C，则L(C)也是许用码字 循环码： 一个 (n,k )线性码C，如果每个码字的循环移位仍是一个码字,称该码为循环码。 循环码的描述 问题：如何构造和描述一个循环码？满足什么样条件的循环码可以有较好的距离特性？ 多项式的引入 如果将码字描述成n阶多项式的形式，A(x)= an-1xn-1+an-2xn-2 +an-3xn-3+ … +a2x2+a1,x+a0，则循环算法就可以描述为L(A(x))=xA(x) mod (xn-1) 便于描述：对任何一个多项式D(x)，有D(x)A(x) mod (xn-1)为许用码字，这里并没有限定D(x)的幂次，但可以肯定的一点是不同的D(x)A(x) mod (xn-1)是有限的，其个数由A(x)决定，这也决定了码集的冗余度和纠错能力，什么样的A(x)可以得到什么样的冗余度？哪些A(x)是等价的？ 第一节 多项式与多项式环 要求掌握的内容 多项式剩余类环 循环群 一、复习几个概念 同余、剩余类 群 环 域 同余和剩余类(p23) 同余：若整数a和b被同一正整数m除时，有相同的余数，则称a、b关于模m同余，记为 群(Group)的定义(p26) 设G是一个非空集合，并在G内定义了一种代数运算 “ 。”，若满足： 环(Ring)的定义(p30) 非空集合R中，若定义了两种代数运算加和乘，且满足： 1) 集合R在加法运算下构成阿贝尔群 2) 乘法有封闭性 3) 乘法结合律成立，且加和乘之间有分配律 二、多项式剩余类环(P103) 有关多项式的几个概念 多项式的加法和乘法 多项式剩余类环的定义 多项式 f(x)=fnxn+ fn-1xn-1+…+ f1x+f0 f(x)=fnxn+ fn-1xn-1+…+ f1x+f0 定义：以一个Fp上的多项式f(x)=fnxn+ fn-1xn-1+…+ f1x+f0为模的剩余类全体构成一个多项式剩余类环 Fp上的所有次数小于n-1的多项式构成n次多项式的剩余类全体 1、GF(2)上的多项式 f(x)=x2+1的剩余类全体为： 两个结论 多项式环Fp[x]的一切理想均是主理想 多项式剩余类环Fp[x]/f(x)中的每一个理想都是主理想。 第2节 循环码的描述 要求掌握的内容 定义 循环码的代数性质 循环码的生成多项式和校验多项式 循环码的生成矩阵和校验矩阵 循环码的系统码形式 定义1：设CH是一个[n.k]线性分组码，C1是其中的一个码字，若C1的左(右)循环移位得到的n维向量也是CH中的一个码字，则称CH是循环码。 将码字 看成如下多项式的系数: 二、循环码的代数性质 二、循环码的代数性质 二、循环码的代数性质 二、循环码的代数性质 由定理4.2可知，次数最低的非零码多项式具有如下形式 问题：如何寻找生成多项式g(x)？ 三、生成多项式 结论1:找一个[n,k]循环码，即是找一个n-k次首一多项式g(x)，且g(x)必是xn-1的因式。 Examples GF(2)上，x7-1=(x+1)(x3+x+1)(x3+x2+1) 试求一个[7,4]循环码。 循环码的编码原理(1) 循环码的编码原理(2) 第3节 循环码的编码电路(P165,174) 多项式乘法和除法电路 循环码的编码电路(乘法和除法) 一、多项式乘法和除法电路 二、循环码编码电路(P174) n-k 级编码器 n-k级乘法电路(非系统码形式) n-k级乘法电路(非系统码形式) n-k级除法电路(系统码形式) n-k级除法电路(系统码形式) n-k级除法电路(系统码形式) n-k级除法电路(系统码形式) k 级编码器 k 级编码器 k 级编码器 k 级编码器 作 业 第四节 几类特殊的循环码 最小循环码：一个理想中不再含有任何的非零理想，此理想对应的循环码是最小循环码(p158) 缩短循环码：对循环码缩短得到的码(p159) 准循环码 双环循环码 第五节 用生成多项式的根定义循环码(p152) 研究表明，生成多项式有重根的码一般都要比无重根的码差，因此只考虑无重根的码，或构造无重根的多项式。 循环码的编码问题转化为：如何由给定的根来得到生成多项式g(x)? GF(q)上多项式xn-1无重根的充要条件是n与q