循环码I.ppt

循 环 码 （I）,内容,循环码的定义 循环码的生成多项式和校验多项式 循环码的生成矩阵和校验矩阵 循环码的系统码形式 特殊的循环码,定义,设CH是一个n.k线性分组码，C1是其中的一个码字，若C1的左(右)循环移位得到的n维向量也是CH中的一个码字，则称CH是循环码。 (alternative)设 是n维空间的一个k维子空间，若对任一 恒有 则称Vn,k为循环子空间或循环码,Example,Example: 7, 4Hamming码的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)的剩余类构成一个多项式剩余类环Fpx/F(x)，若在环中再定义一个数乘运算，即 则模F(x)的剩余类构成一个n维线性空间，定义为剩余类结合代数。 （思考：模一个什么样的多项式 F(x) 能够循环子空间？）,问题一转化为 如何从模多项式xn-1的剩余类结合代数中寻找循环子空间？,循环码的构造,定理：以多项式xn-1为模的剩余类线性结合代数中，其一个子空间Vn, k为循环子空间(或循环码)的充要条件是：Vn,k是一个理想。 循环码是模xn-1的剩余类线性结合代数中的一个理想。反之，其中的一个理想必是循环码。 （定理 5.1.1 pp.146）,问题二 如何从多项式剩余类环中 寻找理想？,多项式剩余类环中任何一个理想都是主理想主理想中的所有元素可由某一个元素的倍式构成 在主理想的所有元素中，至少可找到一个次数最低的首一多项式g(x),即生成多项式,循环码的构造,问题三 如何寻找生成多项式g(x)？,循环码,模多项式xn-1剩余类线性结合代数中的理想,生成多项式,循环码的构造,两个定理,定理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)必是一个码多项式,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)的系数即可构成相应的校验矩阵,Example,在GF(2)上，求7, 4Hamming码 n-k=3;,Example (Continued),循环码的系统码,m(x): 信息多项式；r(x): 校验位多项式 首先将信息组乘以xn-k变成xn-km(x)；然后，用g(x)除，得到余式r(x) ；再将其各项系数取加法逆元，就得到了所要求的校验位,由于生成矩阵G中的k行要求线性无关，因此在求余式时，可选择k个线性无关的信息组 (1,0,0,0) xk-1 (0,1,0,0,0) xk-2 (0,0,0,0,1) 1,循环码的系统码,表示ri(x)的系数,循环码的系统码,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）,