纠错码课件5.ppt

循 环 码 （I） 内容 循环码的定义 循环码的生成多项式和校验多项式 循环码的生成矩阵和校验矩阵 循环码的系统码形式 特殊的循环码 定义 设CH是一个[n.k]线性分组码，C1是其中的一个码字，若C1的左(右)循环移位得到的n维向量也是CH中的一个码字，则称CH是循环码。 (alternative)设 是n维空间的一个k维子空间，若对任一 恒有 则称Vn,k为循环子空间或循环码 Example Example: [7, 4]Hamming码的H矩阵 其16个码字: 1000110, 0100011, 1010001, 1101000, 0110100, 0011010, 0001101; 1001011, 1100101, 1110010, 0111001, 1011100, 0101110, 0010111; 1111111; 0000000 问题一如何寻找k维循环子空间？如何设计[n, k]循环码？ —— 利用多项式和有限域的概念 循环码的构造 GF(p)上的n维向量与GF(p)上的多项式之间有一一对应的关系 模n 多项式F(x)的剩余类构成一个多项式剩余类环Fp[x]/F(x)，若在环中再定义一个数乘运算，即 则模F(x)的剩余类构成一个n维线性空间，定义为剩余类结合代数。 问题一转化为如何从模多项式xn-1的剩余类结合代数中寻找循环子空间？ 循环码的构造 定理：以多项式xn-1为模的剩余类线性结合代数中，其一个子空间Vn, k为循环子空间(或循环码)的充要条件是：Vn,k是一个理想。 循环码是模xn-1的剩余类线性结合代数中的一个理想。反之，其中的一个理想必是循环码。 问题二如何从多项式剩余类环中寻找理想？ 循环码的构造 多项式剩余类环中任何一个理想都是主理想——主理想中的所有元素可由某一个元素的倍式构成 在主理想的所有元素中，至少可找到一个次数最低的首一多项式g(x),即生成多项式 问题三如何寻找生成多项式g(x)？ 循环码的构造 循环码 两个定理 定理1：GF(q)(q为素数或素数的幂)上的[n, k]循环码中，存在唯一的n-k次首一多项式g(x)，每一个码多项式C(x)必是g(x)的倍式，每一个小于等于(n-1)次的g(x)的倍式一定是码多项式 定理2： GF(q)(q为素数或素数的幂)上[n,k]循环码的生成多项式g(x)一定是xn-1的n-k次因式： xn-1= g(x) h(x)。 反之，若g(x)为n-k次多项式，且xn-1能被g(x)整除，则g(x)一定能生成一个[n,k]循环码 两个结论 结论1: 找一个[n,k]循环码，即是找一个n-k次首一多项式g(x)，且g(x)必是xn-1的因式。由此作为生成元，生成一个主理想 结论2: 若C(x)是一个码多项式，则 反之，若 则C(x)必是一个码多项式 生成矩阵和校验矩阵 循环码的编码原理 Example 在GF(2)上，求[7, 4]Hamming码 n-k=3; Example (Continued) Example 二进制[7, 4]码的 ，求系统码的G和H矩阵 特殊的循环码 最小循环码 一个理想中不再含有任何的非零理想，此理想对应的循环码称为最小循环码或既约循环码 缩短循环码 对循环码缩短得到的码 取[n, k]循环码中前i位信息位为0的码字，得到一个[n-i, k-i]缩短循环码 准循环码 一个[mn0, mk0]线性分组码，若它的任一码字左移或右移循环移位n0次后，得到的码仍是该码的一个码字，则称这类码为准循环码 双环循环码 由两个循环矩阵Ik和P阵组成的G=[Ik P]生成的码 Example [8, 4]码双循环码形式 [8, 4]码准循环码形式（n0=2） * * State Key Laboratory of Integrated Services Networks 模多项式xn-1剩余类线性结合代数中的理想 生成多项式 g(x)决定生成矩阵，h(x)决定校验矩阵 生成矩阵 校验矩阵 基本步骤([n,k]) 1、分解多项式xn-1=g(x)h(x) 2、选择其中的n-k次多项式g(x)为生成多项式 3、由g(x)可得到k个多项式g(x), xg(x),…xk-1g(x) 4、取上述k个多项式的系数即可构成相应的生成矩阵 5、取h(x)的互反多项式h*(x),取h*( x), xh*( x),… xn-k-1 h*( x)的系数即可构成相应的校验矩阵 循环码的系统码