信息论与编码8线性分组码.pptVIP

第*页; 第8章 线性分组码; 8.1 一般概念; 8.1 一般概念; 第8章 线性分组码;本节仅介绍与线性分组码的编码有直接关系的必要的代数基础，主要涉及群、子群、陪集和线性空间等。;有关群的几个概念;8.plus 线性分组码的代数结构;【例】：对集合G = (0, 1,?2,?3,?4,?5,?6,?7,?8, 9)定义模10加法运算。请问G是否为模10加法运算的交换群？如果是，则群的恒等元素是多少？每个元素的逆元素分别是多少？;（1）证封闭性： （2）证结合律： （3）证恒等元素e 因为0 ?{0,1}，且有 所以集合{0,1}中的恒等元素e=0 （4）证逆元素 因为： 所以0和1都存在逆元素，0的逆元素是0本身；1的逆元素是1 本身。 所以集合{0,1}是运算符号 的一个群;（5）又因为： 满足交换律 按定义，集合{0,1}是运算符号 的一个交换群。 ;2 子群;8.plus 线性分组码的代数结构;定理：有限群的子群的阶一定整除群的阶。 ;设集合H:{e,h2,h3,…,h2k}是运算法则*的一个群G:{g1,g2,g3,…,g2n}的一个子群，gi是群G中的一个元素，但gi不是子群H中的一个元素，即gi ?G, gi ? H，则： gi *H={gi *e, gi *h2, gi *h3,…, gi * h2k} 称为子群H在群G中的一个左陪集。 H* gi ={e*gi, h2*gi, h3*gi,…, h2k *gi} 称为子群H在群G中的一个右陪集。 gi *e= e*gi =gi，称为陪集首。 如群G是运算法则*的交换群，则左、右陪集一定相同，则gi *H= H* gi 这时，左陪集和右陪集通称为陪集。 ;对集合G :{0, 1,?2,?3,?4,?5,?6,?7,?8, 9}定义模10加法运算，运算符号用 * 表示，G是*一个交换群，0为加法恒等元。集合H:{0,2,4,6,8}为G的一个子群。 令gi =3，则 3?G, 3? H 则3*H={3*0, 3*2, 3*4, 3*6, 3*8}={3,5,7,9,1}为子群H在G中的一个左陪集。 H*3 :{0*3, 2*3, 4*3, 6*3, 8*3} ={3,5,7,9,1}为子群H在G中的一个右陪集。 3*0=0*3=3为陪集首 因为gi *H= H* gi ，所以左陪集和右陪集通称为陪集。;定理8.7?（完备性）：运算法则*的群G中的所有元素，均可由其子群H中的所有元素及其子群H的若干个陪集表示。 群G :{0, 1,?2,?3,?4,?5,?6,?7,?8, 9}，子群H:{0,2,4,6,8}，陪集{3,5,7,9,1} 定理8.8：群G中的两个元素g1和g2在子群H的同一陪集中的充分必要条件是 g1-1* g2 ?H 令g1 =3，g2 =9，则g1-1* g2 ?H 定理8.9（正交性）：设H是群G的子群，H的两个不同的陪集一定不相交。 如gi*H和gj*H是H的两个不同的陪集，则这两个陪集中没有共同的元素；否则gi*H和gj*H 是相同的陪集。 令g1 =3，g2 =9， g1的陪集g1*H为{3,5,7,9,1}， g2 的陪集g2*H为{9,1,3,5,7}，是 同一陪集。 ;（1）若 ，则 ； （2）若 ，则 （空集）。;若在非空集合F中，规定“+”和“?”两种运算符，且： （1）非空集合F构成运算法则“+”的交换群； （2）非空集合F构成运算法则“?”的交换群； （3）对两种运算法则“+”和“?”，非空集合F中的元素满足分配率。 则非空集合F构成一个域。 域中含有元素的个数称为域的阶。 如含有有限个元素，则称为“伽罗华域”，记作GF。 如域中含有二个元素，记作GF(2)。 定理8.10：非空集合{0,1}是两种运算法则 和 的一个二元域GF(2)。 证明：（1）前面已经证明集合{0,1}是运算符号 的一个交换群。 （2）类似可以证明，集合{0,1}也是运算符号 的一个交换群。;;8.plus 线性分组码的代数结构;对线性空间作定义后，设N是由GF(2):{0,1}中的元素0和1作为码符号构成的二进制码字集合，若V1和V2是集合N中任意两个元素，则V1和V2可表示为： 若规定“+”运算法则为： 设c ?GF(2):{0,1}，规定“