基于欧氏几何的Gallager_LDPC码的构造.ppt

基于欧氏几何的Gallager LDPC码的构造 何仙姑 2011.12.27 LDPC编译码概述 简化的BP算法：BP-based、 Normalized BP-Based、 offset BP-based 改进BF算法的有效方案：加权的BF算法（WBF）及其改进形式（LP-WBF、 MWBF等） 典型的随机构造法：Gallager构造法、Mackay构造法、Davey构造法、 比特填充及扩展的比特填充方法、girth分布构造法、 PEG方法 按照Gallager方法构造出的规则LDPC码的校验矩阵 Gallager构造的LDPC码具有的特点： 1、H（尺寸为 )的行重和列重固定且 2、H的行被平分为 块，每一块有 行 3、子矩阵中每列只有1个“1”，第一个子矩阵中第 行只有从第 列到第 列的元素为“1” 4、其余各块根据第一块按列进行随机置换得到 Gallager码存在的3个问题 1、由于随机构造的原因，在码长较短时二分图中可能会出现较短的环，影响码的性能，不过随着码长得增加，短环出现的概率变小【阐述原因】 2、此方法构造的H为奇异，无法得到同样尺寸的生成矩阵【阐述原因】 3、此方法构造的H和G不具备准循环特性，使得编译码复杂，难以应用。 【阐述原因】 H1 的列置换 H1 的列置换 Gallager构造一类LDPC码的方法，但Gallager并没有提供H1 的列置换的特定方法，需要计算机搜索。 计算机搜索需满足的要求： 1、 个置换必须使得有 生成的码具有很好的最小距离性能。 【阐述原因】 2、泰纳图中不包含长度很短的环，尤其不能包含长度为4的环。 【阐述原因】 是一个 的子矩阵 H1 HGA 基于欧氏几何中线的平行结构构造Gallager码 m维向量 a = (a0,a1,…,am-1)称为EG(m,ps)中的一个点，其分量ai属于伽罗华域GF(2s)。因此总共有2ms个点。全零向量a = (0,0,…,0)称为几何EG(m,ps)中的原点。 设a，a0为EG(m,ps)两个线性独立的点，2s个点的集合{a0 +?a}构成EG(m,ps)中一条通过点a0的直线。直线{?a} 和直线{a0 +?a}不存在任何公共点【阐述原因】 ，因此互为平行线。 a为EG(m,ps) 中的一个非原点的点（即a?0 ）， 那么2s个点{?a: ?? GF(2s)}称为EG(m,2s)的一条直线或一维平面 ，用{?a} 代表这条直线，该直线通过原点。 令a1，a2为EG(m,ps)两个线性独立的点，直线{a0 +?a1} 和直线{a0 +?a2}只有一个公共点【阐述原因】，而且他们均通过a0 ，因此该两直线在点a0相交。 有限几何法构造校验矩阵是基于有限几何中的线和点来进行的。欧氏几何G具有n个点和J条线，满足以下4个条件： （1）每条线有ps个点； （2）任何两个点之间有且只有一条线； 【阐述原因】 （3）每个点只能落在q条线上； （4）两条线或是平行或有且只有一个交点。 点 线 a1 a0 a3 a2 a5 a4 a7 a6 a9 a8 a11 a10 EG(m,ps) 中 共有的点数：pms 一条直线上的点数：ps 一个平行簇内共有的直线数：pms/ ps= ps(m-1) 【阐述原因】 交于a0的直线个数（平行线簇个数） ： pms-1/ ps-1 【阐述原因】 直线总数： ps(m-1)（pms-1）/ ps-1 【注】：在每个平行线簇中，平行线包含了EG(m,ps)中的所有 pms个点，且每个点在且仅在这些平行线中的一条上。 校验矩阵的行对应欧氏几何里的线， 列对用于欧氏几何里的点 矩阵的元素对应欧氏几何里点线的关联向量值 HEG的行数：p(m-1)s(pms-1)/(ps-1) （即直线总数） HEG的列数：pms （即所有的点数） 行重：?=ps （由于每条直线只有ps个点） 列重： ?＝(pms-1)/(ps-1) （交于a0的直线个数即平行线簇个数） 密度r= ?/n=ps/pms=p-(m-1)s =?/ p(m-1)s(pms-1)/(ps-1) =p-(m-1)s 线 Hij