digital communicaiton_6_信道编码II.ppt

第6章 信道编码II I 代数初步 一、同余和剩余类 同余：若整数a和b被同一正整数m除时，有相同的余数，则称a、b关于模m同余，记为 二、群(Group)的定义 设G是一个非空集合，并在G内定义了一种代数运算 “ 。”，若满足： 三、有关群的几个概念 群的阶(Order of a Group) 群中元素的个数称为群的阶 有限群(Finite Group) 有限阶的群称为有限群 无限群(Infinite Group) 无限阶的群称为无限群 加群、乘群 阿贝尔群(Abelian Group) (满足交换律) 半群(Semigroup)(满足前两个条件，封闭性和结合律) 弱群(Monoid)(满足前三个条件，封闭性、结合律且有恒等元) 置换群(Permutation Group) 对称群(Symmetric Group) 格(Lattice)——是一类加群，集合中的元素是欧氏空间中的离散点 四、子群的定义 子群：若G为运算 下的一个群，H为G的一个非空子集，若满足 H在运算 下是封闭的； H中的任意元素的逆元仍在H中， 则称H为G的子群 五、陪集的概念 陪集：设H是在运算 下的群G的一个子群，a是群G的一个元素，则 五、陪集的概念 六、环(Ring)的定义 非空集合R中，若定义了两种代数运算加和乘，且满足： 1) 集合R在加法运算下构成阿贝尔群 2) 乘法有封闭性 3) 乘法结合律成立，且加和乘之间有分配律 七、域(Field)的定义 非空集合F，若F中定义了加和乘两种运算，且满足： 1) F关于加法构成阿贝尔群，加法恒等元记为0 2) F中所有非零元素对乘法构成阿贝尔群，乘法恒等元记为1 3) 加法和乘法之间满足分配律 置换群(1) 置换：有限集合A到自身的一一映射 置换群(2) 对称群 对称群：由n个元素构成的集合A到自身的所有n!个置换构成的集合在置换运算下构成对称群。 有零因子环 对于环中的两个非零元素 a和b，若它们在环上定义的乘法运算下为零，即ab=0，则a、b为零因子，对应的环为有零因子环。 II 线性分组码 定义1(线性空间)：如果域F上的n重元素集合V满足下述条件，称V是域F上的一个n维线性空间： 1) V 关于加法构成阿贝尔群 2) 对于V中的任意元素v和F中任意元素c(纯量或标量)，cv一定属于集合V(数乘运算) 3) 分配律成立 c(u+v)=cu+cv,(c+d)v=cv+dv 4) 结合律成立 (cd)v=c(dv) 定义2(域F上的线性组合) 定义3(线性相关和线性无关) 定义4(张成)：给定线性空间V和V中的一个子集S，若V中的任意一个矢量均可用S中的矢量线性组合生成，则称S张成了矢量空间V。 定义5(基底和维数)：给定线性空间V，能张成该空间的线性独立矢量的集合称为V的基底，而线性独立矢量的数目称为V的维数 零空间：若V1是n维空间V的子空间，则和V1中每一个n维矢量均正交的所有矢量，构成V的另一个子空间V2，称V2为V1的零空间。 若n维空间V的子空间V1的维数为k，则V1的零空间的维数为n-k。 二、线性分组码的定义 定义3.1.1 ［n， k］线性分组码是GF(q )上的n维线性空间Vn中的一个k维子空间Vn,k。 由于该线性子空间在加法运算下构成阿贝尔群， 所以线性分组码又称为群码。 用(cn-1， cn-2， …， c1， c0)表示［n， k］码的一码字， 其中每一分量ci∈GF(q)。 如果一个线性分组码的码字可分成消息部分和冗余部分，其中消息部分是k个未经处理的原始消息，冗余部分是产生的校验位，则该类码称为线性系统分组码 注： 生成矩阵G中的每一行都是一个码字 任意k个线性独立的码字都可以作为生成矩阵 给定一个[n,k,d]线性分组码，其生成矩阵可有多个 四、线性分组码的校验矩阵 ［n ， k ， d］分组码的编码问题就是在n 维线性空间Vn 中， 如何找出满足一定要求的， 有2k 个矢量组成的k 维线性子空间Vn， k 。 或者说， 在满足给定条件(码的最小距离d或码率R)下， 如何从已知的k 个信息元求得r=n -k 个校验元。 若用矩阵形式，这些线性方程组可表示为： 称上式中的4行7列矩阵为［7， 3， 4］码的一致校验矩阵， 通常用H 表示， 该码的 线性分组码的校验矩阵是一个(n -k )