论文研究-LDPC码构造理论的研究进展 .pdf

发布时间：2022-05-29 发布人：admin 分类：说明书资料大小：0.32M 资料格式：pdf 举报版权申诉

weixin_39840588-11611060-4744302543318073472.pdf-第1页.png

第1页 / 共12页

weixin_39840588-11611060-4744302543318073472.pdf-第2页.png

第2页 / 共12页

weixin_39840588-11611060-4744302543318073472.pdf-第3页.png

第3页 / 共12页

weixin_39840588-11611060-4744302543318073472.pdf-第4页.png

第4页 / 共12页

weixin_39840588-11611060-4744302543318073472.pdf-第5页.png

第5页 / 共12页

weixin_39840588-11611060-4744302543318073472.pdf-第6页.png

第6页 / 共12页

weixin_39840588-11611060-4744302543318073472.pdf-第7页.png

第7页 / 共12页

weixin_39840588-11611060-4744302543318073472.pdf-第8页.png

第8页 / 共12页

文本预览

中国科技论文在线 http://www.paper.edu.cn LDPC 码构造理论的研究进展张国华，杨洋，王新梅西安电子科技大学 ISN 国家重点实验室，西安（710071） E-mail:zhangghcast@163.com 摘要：LDPC 码是现代编码体系中的典型码类，在迭代译码算法下纠错性能接近理论极限，是最新数字通信、磁介质记录等应用系统的首选码型。本文首先概括了 LDPC 码的一般设计准则，总结了 LDPC 码的围长和最小距离的理论限，在此基础上对目前著名的结构化 LDPC 码构造方法和随机化 LDPC 码构造方法进行了综述。对于结构化 LDPC 码的构造方法，分析比较了平衡不完全区组设计（BIBD）、部分平衡不完全区组设计（PBIBD）、RS 码、有限域、正则图和群结构等方法；对于随机化 LDPC 码的构造方法，分析比较了 Gallager 构造法、 MacKay 构造法、基于 girth 分布的启发式搜索法、比特填充法、渐进边增长（PEG）法和分割－移位法等方法。文章最后简要概括了目前构造 LDPC 码的一些通用技巧，并指出了 LDPC 码构造今后的几个发展方向。关键词：LDPC 码;环;girth 中图分类号：TN911.22 1 LDPC 码及其设计准则诞生于 1962 年的 LDPC 码，在沉寂三十余年后成为目前编码理论的研究热点和工程应用的首选码型。LDPC 码的奇迹般复兴与现代计算机和集成电路技术的迅猛发展密切相关。 LDPC 码的魅力在于它（和 Turbo 码一起）出人意料地解决了困扰编码理论家和通信工程师长达半个世纪的 Shannon 难题：如何寻找 Shannon 所预期的好码，以及如何有效地译码。规则 LDPC 码的定义最早是由 R.G.Gallager 给出的[1]。如果校验矩阵 H 满足三个条件：(1)H 每行有ρ个“1”；(2)H 每列有个“1”；(3)与 H 矩阵的行数和列数相比，ρ和λ都很小，则 H 的零空间就是规则 LDPC 码。如果没有特别强调，文中的 LDPC 码均为二元情形。 ( ≥λλ )3 不同于经典码型（例如 RS 码，BCH 码），LDPC 码的本质属性只有校验矩阵的稀疏性。 LDPC 码近乎随意的定义，激发出各式各样的巧妙构造方法。这些方法可以按照不同设计准则分类。人们目前对和积算法（在有环图上）的性能还不够理解，只能根据大量实践经验总结出若干设计准则[2][3][4]：1）Tanner 图无短环（cycle）：为了保证迭代信息的独立性，Tanner 图的 girth 要尽可能大，或者具有良好的 girth 分布；2）最小距离不能太小：码距过小会使译码性能在高信噪比区出现错误平层（error floor）；3）Tanner 图直径（diameter）要小：为了使信息能够在 Tanner 图中迅速流动，Tanner 图的直径要小；4）无小的停止集（stopping sets）：码字在二进制删除信道上的迭代译码性能取决于停止集，人们猜测其他信道或许亦如此。5）伪码字（pseudo-codewords）的最小重量最大化：伪码字对于理解迭代译码至关重要； 6）不含小的诱捕集（trapping sets）：诱捕集对错误平层的开始位置和斜率有重大影响。7）编码复杂度较低；8）描述紧凑、参数灵活。目前应用最多的设计准则是(1)(2)(7)(8)，本文围绕这些设计准则对已有的典型构造方法进行评述。第 2 节介绍 LDPC 码的若干理论限；第 3 节和第 4 节分别介绍结构化和伪随机构造方法。结构化方法和伪随机方法的划分是相对的，因为多数情况下二者以不同程度相互渗透。第 5 节介绍一些通用技巧；第 6 节指出 LDPC 码构造方法的发展趋势。基金项目:973 项目（2010CB328300）、国家自然科学基金资助项目(U0635003)、111 基地项目（B08038）。 -1-

中国科技论文在线 2 LDPC 码的理论限 http://www.paper.edu.cn 理论限至少具有三方面意义：第一，否定特定 LDPC 码的存在性；第二，为 LDPC 码的某些目标参数提供最低保障；第三、为评价各种构造方法的性能提供判别标准。 2.1 girth 的上限 I 2000 年 P.O.Vontobel 考察 Tanner 图后，得到一个 girth 上限。定理 1[2][3]：若校验矩阵列数为 n ，行数为 m ，列重和行重分别为γ和ρ，则对应 Tanner g 则 log4 α 图的 girth g 满足以下不等式：若 ( 2=g (mod )1 )(1 ργα − − 2 ；其中 ,2( ρ －规则 LDPC 码的 girth 为 g，则 < + 引理 1[5]：设由定理 1 及引理 1 可以直接得到 )4 。 = n ) d min = g 2/ 。 ,2( ρ －规则 LDPC 码的距离上限，它与 R.G.Gallager ，则 g < log4 α m + 2 ；若 0=g (mod )4 ，给出的上限[1] d min 推论 1：对于 1 −+ ρ n 1 − ) ( ≤ 4 1 1 ρρ − − d ,2( ρ －规则 LDPC 码， ) log2 ) log ) 非常接近。 − n 1 log2 < ρ min + 1 。根据推论 1，在行重不变的条件下 ,2( ρ －规则 LDPC 码的最小距离与码长至多为对数关系。因此，R.G.Gallager 在定义中要求列重大于 2。对于多元 LDPC 码，列重大于 2 未必是最佳选择，事实上人们发现多元 LDPC 码在列重为 2 时性能可能更好[5][6][7]。 2.2 girth 的上限 II cNi ) ≤≤ iH j ),( iH j ),( 2006 年，Lu Jin 研究了一类特殊的校验矩阵 H 及其 girth 上限。定理 2[8]：若校验矩阵 H 完全由循环置换子矩阵或者全零子矩阵拼接而成，则 g CL 1,CC CL ) ((2 ( 是矩阵 S 中的任意两个满足 − ≤ + 1 1 1 C C (CL 表示环路C 的长度。 ) Φ≠∩ 2 这类校验矩阵 H 是一个 c NN × 的分块矩阵，其第 bNj 的回路，，其中 ≤≤ CL ( 行，第 1( 1( ∩ C )) 列 ) ) i j b 2 2 2 p 是的元素 p × 的循环置换子矩阵或全零子矩阵。若 iH p × 的单位阵循环右移 j ),( p 它可由是全零子矩阵，则记 is j 。 H 所对应的全体 jis , 构成一个表征移位次数的矩阵S 。S 中的回路是一条由水 ∗=),( 平线和垂直线交替组成的封闭道路，回路的顶点是S 中的非∗ 数值。由于很多经典方法构造出的校验矩阵都是这类矩阵的特例，因此该 girth 上限具有很强的通用性。是循环置换子矩阵，则次得到，若 0( < ≤ p s s ji , ji , ) 推论 2[8][9]：如果校验矩阵 H 完全由循环置换分块矩阵组成，则 ≤g )244(2 −+ = 12 。 2.2 最小距离的下限 I：最小距离在 LDPC 码设计中不是决定性指标，但是最小距离过小会使高信噪比区出现错误平层。因此对最小距离作较准确的估计很有价值。2003 年 Hu Xiao-Yu 得到一个最小距离与 girth 的一般关系，它可以看作是 1981 年 R.M.Tanner 结果的变体。定理 3[5][6]：设 3≥γ ，则 -2-

中国科技论文在线 http://www.paper.edu.cn 1 + ((γ − 1) ⎣ (g − 4/2) ⎦ − 1), 2g/ odd ⎧ ⎪⎪ ⎨ 1 ⎪ ⎪ ⎩ γ 2γ − 1) ⎣ − mind ≥ ⎦ − (g + 4/2) 1) ((γ (γ 1) −+− γ 2γ − 推论 3[5][10]：若。若 LDPC 码对应的 Tanner 图不含 4 环（即 +≥γ 6≥g +≥ γ ，则 min d d 1 4/2) ⎦ , 2g/ even (g- ⎣ 6≥g 1 ）则 LDPC 码可以看作自正交码；根。从定理 3 以理解人们追求高 girth 的一据 Messay 的一步大数逻辑译码[10]可知个重要原因：若列重不变，则 mind 与 girth 至少为指数关系。 min 2.3 最小距离的下限 II 定理 4[11]：设校验矩阵 H 的列数为 n ，列重和行重分别为γ和ρ，则最小距离满足： ≥ n ，其中 2µ 是将 H µγρρµργ 2 −−+ 2(2 ≥ n /{) 2( )} min − − 2 ( 2 − min µγρµγ 2 d 看作实矩阵时 THH 的次最大特征值。 /() ； d ) 2 定理 4 在最小距离估计方面的启示：次最大特征值越小，LDPC 码的最小距离越大。根据定理 4 和强规则图的特征值，S.J.Johnson 曾给出部分几何 LDPC 码的最小距离下界[12]。 2.4 最小距离的上限目前一般 LDPC 码的最小距离上限尚未建立，人们仅得到一些特殊 LDPC 码的最小距离上限。1999 年 D.J.C.MacKay 和 M.C.Davey 研究了一类特殊校验矩阵 1H ：由 ργ× 个置换子矩阵构成的分块矩阵。2004 年 Lu Jin 研究了一类更广泛的校验矩阵 2H ：由 c NN × 个 γ−cN 置换子矩阵或者全零子矩阵构成的分块矩阵，分块矩阵的每列由γ个置换子矩阵和个全零子矩阵构成。 b 定理 5[13]：若分块矩阵 2H 中存在 N c × ( N c + 的子网格，子网格中任意两个子矩阵可交换（即 = RR ij kl RR kl ij γ=cN ，则分块矩阵完全由置换子矩阵构成。根据定理 5 有），则 LDPC 码的最小距离 !)1 cN min + ≤ ( γγγ − cN 。令推论 4[13][14]：若分块矩阵 1H 中存在 ( + × γγ )!1 + ≤ γ 。交换，则 LDPC 码的最小距离 d ( min )1 的子网格，子网格中任意两个子矩阵可 )1 d 3 结构化 LDPC 码的构造研究进展与规则 LDPC 码的定义直接对应的数学对象是组合设计中的 BIBD 和 PBIBD。组合设计研究的内容是从给定集合中选择一组子集以满足特定的性质，它在自正交码构造中发挥过重要作用[15]，同样也是构造 LDPC 码的不竭源泉[16][17][18]。虽然所有规则 LDPC 码的校验矩阵可以统一看作是 PBIBD，但是如果这种统一观点不能导出有意义的结论，我们仍然按照原有名称分类。 3.1 基于 BIBD ,...,2,1{ V = 设 v } 集（区组）之集合，若V 中的点是包括v 个不同元素（点）的基集， bB ,..., } pVqp iBp ∈ ，则称 p 与区组 iB 关联。若对于任意 , ( 是V 的 −k 子 q ) ∈ BB=B 2 ,{ 1 ≠ -3-

中国科技论文在线 http://www.paper.edu.cn k ,( v ); ( BV , ) BIBD λ ，其中 k 称为区组长度。设都有λ个区组与 qp, 关联，则称为平衡不完全区组设计（BIBD），简称区组设计并，若V 中记作每点都正好与 P 中唯一一个区组关联，则称 P 为一个平行类；若 B 中全部区组能划分为 vλ ( BIBD λ 为可分解的并记作 k v );1,( k ,( 的关联矩阵作为 LDPC 码的校验矩阵，则校验矩阵 RBIBD λ 。 /()1 显然，如果将区组设计个平行类，则称此 BIBD ( BV 为 BIBD λ ， v ); k ,( B⊂P v ); k − )1 , ) v ); k ,( − RBIBD k v );1,( 对应的 Tanner 图 girth 为 6；如果将区组设计全部（或部分）平行类的关联矩阵作为 LDPC 码的校验矩阵，则 girth 为 6（或 girth 6≥ ）。已有的区组设计成果可以分为两类[15][16]：第一类针对特定的区组长度，例如 Steiner 三元系(STS)和 Kirkman 三元系（KTS）；另一类针对特定类型的区组长度，例如射影几何（PG）、欧氏几何（EG）、酉(Unital)、椭圆 (Oval)和 Denniston 设计。具体参数如表 1 所示[15][16]。表 1 特定类型区组长度的 BIBD v k );1,( 类型射影几何欧氏几何酉（Unital）椭圆（Oval） Denniston设计 k q+1 q q+1 q/2 q v (qn+1-1)/(q-1) qn q3+1 q(q-1)/2 q(2s+1)-2s 参数限制 q为素数方幂，n≥2 q为素数方幂，n≥2 q为素数方幂 q=2m q=2m,s>m≥2 根据表 1 和文献[19]，可以描绘出这些组合设计之间的相互关系，如图 1 所示。 BIBD(k,1;v) (v,k,1)-差族 Unital (v,k,1)-差集 SBIBD(n+1,1,n2+n+1) n阶有限射影平面 STS KTS RBIBD(n,1,n2) （n阶有限仿射平面） Oval RBIBD 正交拉丁方 PBIBD(k,{0,1},v) 图 1 一些组合设计对象的相互关系利用以上组合设计成果，人们设计出多种类型的 LDPC 码： 1）基于有限几何有限几何是构作组合设计的丰富源泉。有限几何满足以下性质[10]：1）每条线上有ρ个点；2）过任意两点有且仅有一条线；3）过每个点有γ条线；4）两条线平行或交于一点。基于有限域的射影几何和欧氏几何是两类最重要的有限几何。有限射影平面和有限仿射平面是二维情形下的特例，它们分别为 SBIBD 和 RBIBD 提供了最重要的例子[19]。2001 年 Kou Yu 利用射影几何和欧氏几何构造了 4 类性能优良并且易于编码的 LDPC 码[10]。基于有限几何的 LDPC 码是首次利用代数方法构造出的 LDPC 码类，它为人们提供了两点启示：第一，除了(伪)随机方法，代数方法也可以构造出性能接近理论限的 LDPC 码；第二、代数方法构造的 LDPC 码一般结构性较强，这对于简化编译码器的设计很有意义。这些启示激发起人们对有限几何方法进行深入研究的热情。2004 年 Chen Lei 利用欧氏几何并结合行列分割的通 -4-

中国科技论文在线 http://www.paper.edu.cn 用技巧构造了一类 LDPC 码[20]；2004 年、2005 年 Tang Heng 利用射影几何和欧氏几何构造了几类 LDPC 码[21][22]。2006 年 Tai Ying-Yu 利用欧氏几何构造了同时适于 AWGN 信道和删除信道的 LDPC 码[23]。码的码长 2）2003 年 S.R.Weller 和 S.J.Johnson 基于 Unital 和 Oval 构造了 LDPC 码[24][25]。Unital-LDPC 。Oval-LDPC /()1 ，直接利用 Oval 设计得到的 LDPC 码码率较高；，可以划分为 1+q 个平行类，因此选择部分平行类可以构造出较低 qq ( 2 q 2 − = ，码率很高约为 )}1 − vvn kk ( ( /{)1 − = − vvn kk ( ( /{)1 = − 码的码长为 RBIBD k v );1,( Oval 是码率的 LDPC 码。 = )}1 q/11− + 1 )1 + q 3 d min =+≥ 413 3）利用 BIBD 构造 LDPC 码的首次尝试是采用 STS[14]。根据推论 3，STS-LDPC 码的。1999 年 D.J.C.MacKay 指出，STS-LDPC 码的最小距离最小距离只能保证至多为 10[14]。利用无-pasch 配置的 STS[16]可以使 LDPC 码的最小距离不小于 6。2001 年 S.J.Johnson 和 S.R.Weller 研究了基于 KTS 的 LDPC 码[26]。由于 KTS 是，所以可以构造列重为 3，行重在一定范围任意取值的 LDPC 码。选取 KTS 的部分平行类作为校验矩阵，可以灵活地调整码率并且允许 girth 大于 6。 RBIBD v );1,3( 设 s 为正整数， S 为由 G 的 s 个子集任意非零元素 g 都恰好有 1 次表示为 4）差族是构作 BIBD 的最常用也是最有效的方法。设G 是 v 阶 Abel 群，其运算为加法， s 组成的子集族。若 G 中 jk , ，则称 S 为G 中 ≤ ≠ ,( kv )1, dd D d i { , , 1}, = ≤≤ 1 L i i ik i 2 d lj g d i s 1, 1, , − = ≤≤ ≤ ij 则称 S 为 G 中的 1=s －差族。特别地，若 Ggg 称为 D 的平移。 }, + ∈ －差集的v 次平移对应于一个 Tanner 图无 4 环的 vv × 方阵； ,( kv )1, 的 dDg { = + 1 ,( kv )1, －差集。集合 ,( kv dg , )1, L + + d g l , , il 2 k －差族的v v× 矩阵。利用差族构造 LDPC 码的前提是，确定是素数方幂，，若次平移对应于一个 Tanner 图无 4 环的 vs 特定参数下的差集是否存在。已经证明，对于 1 q q q = + ≠ = − + m (1 )1, 30 )61 kq ,( 差族；若 5,4,3=k kk )1 ( )1,6,(q 5,4,3=k 是素数方幂，则存在 m 差族。利用差族可则存在以构造出大量 LDPC 码。2003 年 S.J.Johnson 利用 Buratti 给出的差族构作法设计了 LDPC 码 [27]；对于，2004 年 B.Vasic 利用 Netto 和 Buratti 给出的差族构作法设计了 LDPC 码[16]。2004 年何善宝利用差集和通用的行列分割技术构造了 LDPC 码[28]。Bose 于 1939 年提出的对称重复差集（混差系统）是构作 BIBD 的有效方法，2004 年 B.Ammar 等人利用基于对称重复差集的 BIBD 构造了 LDPC 码[17]。由于差族仅在特殊参数配置下存在，因此构造 LDPC 码时不太灵活。1992 年陈志将差族的概念推广为不相交差集（DDS）[15]。将差族定义中的“任意非零元素 g 都恰好有 1 次”改为“任意非零元素 g 都至多有 1 次”，即可得到 skv ,( DDS 的定义。2004 年 Song Hong-Wei 等人基于 DDS 构造了适合于部分响应信道的 LDPC 码[29]。 −), 3.2 基于 RS 码 RS 码是非常重要的 MDS 码，。若 2=k ，即任意码字之间至多有一个符号相同。2003 年 I.Djurdjevic[30]首先将所有 RS 码字划分为若干陪集，使陪集中每列元素各不相同；然后通过定义位置向量建立了有的三个参数满足关系式 1−= n 1+−= kn dknMDS , ,( 则 d d ) -5-

中国科技论文在线 http://www.paper.edu.cn 限域中元素与重量为 1 的行向量的对应关系。这种方法可以构造规则 LDPC 码，但缺乏准循环结构，因而不利于编码器设计。2004 年 Chen Lei[31]提出基于 RS 码最小重量码字的构造方法。首先按照零元素在码字中的不同位置将全体最小重量码字划分为若干集合，使集合除全零列以外的每列元素各不相同；然后定义另一种位置向量：有限域中非零元素与重量为 1 的行向量一一对应，而零元素对应于一个全零向量。利用这种方法可以得到准循环 LDPC 码。利用相同思路，2005 年 Chen Lei[32]基于扩展 RS 码构造了另一类准循环 LDPC 码。 3.3 基于有限域虽然 LDPC 码的绝大多数构造方法在本质上都基于有限域，但它们依赖有限域的程度不同。有限域是构建 BIBD 及 RS 码的重要数学工具，因此很多基于 BIBD 和基于 RS 码的 LDPC 码都可以看作是间接使用有限域方法。2005 年 Lin Shu 的研究团队直接利用有限域提出了几种简单构造方法[33][34]。利用仿射变换和有限域中的各种群（包括乘法群的循环子群、加法群、乘法群），他们构造出几类不含 4 环的 LDPC 码。这些方法的共同特点是，首先在有限域上选择一组互异元素，然后实施一组仿射变换，因此根据文献[35]中的定理 2.3.2，这些方法本质上与基于 RS 码的构造方法相同，它们都是基于 MDS 码的构造方法。 3.4 基于正交拉丁方推广 BIBD 的定义可以得到 PBIBD。 ∈ pVqp , ( 定义：若对于任意 , 个区组与 qp, 关联，则 } ,{ mλλλ 1 ( BV 为部分平衡不完全区组设计（PBIBD）并记作 k PBIBD Λ ，其中 k 称为区组 v ,( ); 的关联矩阵可以直接作为校验矩阵。PBIBD 可以通过很多方 k v )};1,0{,( PBIBD =Λ∈ 都有 λ L ≠ q ) ) , 2 称长度。显然法得到，正交拉丁方（MOLS）是最重要的方法之一。 S 定义：集合 n }, ,2,1{ L= 丁方。在两个 n 阶拉丁方 A = ( 互异，则称 A 与 B 为一对 n 阶正交拉丁方（MOLS）。上的 n 阶方阵 A ，若每行每列元素均互异，则称 A 为 n 阶拉 , jia ) 迭合成的方阵中，若 2n 个有序对 ji b , ji , , B = ib ， a ) ( ( ) , j 正交拉丁方是构作 BIBD 和 PBIBD 的重要工具。如图 1 中虚线和粗实线所示，如果存在完备的正交拉丁方组（即包含 1−n 个 n 阶正交拉丁方），则存在射影平面和仿射平面[19]，因而存在 SBIBD 和 RBIBD；若不存在完备的正交拉丁方组，则一般情况下可以构作出 PBIBD。2002 年 B.Vasic 等人[36]基于正交拉丁方构造了 LDPC 码，并研究了它在垂直磁记录系统中的性能。 3.5 基于 k 正则图 ( ) 是以元素 2000 年 J.Rosenthal 和 R.O.Vontobel 基于两类 k 正则图构造出两类 LDPC 码[2][37]。第一 1−= S 之间有边当且仅当类 k 规则图基于 Margulis 于 1982 年构造的 Cayley 图。设G 是有限群， GS ⊂ 且满足 SGX , Cayley 图 gg S 1 ∈− 。基于 Cayley 图构造的校验矩阵行重为 6，列重为 3。已经证明，这种码对应的 1 nσlog 线性增长（其中σ为一个常数），根据定理 1 这是可以期望的最好 girth 下界可以按照情形。第二类 k 正则图基于 A.Lubotzky 等人于 1988 年构造的 Ramanujan 图。Ramanujan 图 −k 的 −k 正则图，这种图的 girth 超过了随机图的 Gg ∈ 为节点的图，节点是邻接矩阵的次最大特征值至多为 Ggg 1, ∈2 S 2 1 2 ， -6-

中国科技论文在线 http://www.paper.edu.cn girth 下界 girth 为 12 的 nk 1 −)6,3( log − ，其中 n 是节点数目。利用 Ramanujan 图 R.O.Vontobel 构造了码长为 4896、规则 LDPC 码。根据定理 1 该码的 girth 特性接近完美。 3.6 基于群结构 2001 年 R.M.Tanner 等人[38]利用素域 ( pGF 中乘法群的子群构造了一类 QC(3,5)-规则 LDPC 码,这类码的校验矩阵由若干单位阵经过循环移位构成。作为特例，得到了最小距离接近已知最好值的[155,64,20]码。仿真结果表明：使用和积算法译码，在短码长和中等码长（1055 以下）下，这类码的性能达到或超过随机生成的(3,5)-规则 LDPC 码。QC（3,5）LDPC 码的 girth 至少为 8，而且几乎所有码的 girth 都达到 QC-LDPC 码所能达到的最大值 12。 ) 3.7 基于部分几何和广义多边形 2004 年 S.J.Johnson[12]将部分几何（PG）设计引入 LDPC 的构造中，扩展了 LDPC 码的参数选取范围。部分几何是满足以下性质的点线关联结构： 1）过每个点 p 有 1+t 条线， ,( Lp ，每条线 L 上有 1+s 个点；2）任意两条线至多交于一点；3）对于任意无关联的点线对 ) 过 p 点并与 L 相交的线有α条；其中 α,,ts 是正整数。部分几何不仅包括 BIBD，而且包括广义四边形，Net、横截设计和常态部分几何，因此极大地丰富了 LDPC 码家族。在 girth 准则的基础上，人们希望能够兼顾其他准则，例如 Tanner 图的直径尽可能小。girth 与直径的比值存在上界 2，恰好达到该上界的图称为广义多边形[39]。非平凡的广义多边形直径只能取 3，4，6，8，分别对应于广义三角形、四边形、六边形和八边形。其中，广义三角形恰好是 2001 年 Kou Yu 研究的二维 PG－LDPC 码。2003 年 P. O. Vontobel[3]基于广义四边形构造了 LDPC 码，2005 年 Liu Zhen-Yu[39]基于四边形、六边形和八边形构造了 LDPC 码。P. O. Vontobel 指出[3]，广义三角形和四边形既属于部分几何也属于广义多边形。 3.8 基于其他方式以上构造方法采用了较难甚至非常艰深的数学知识，因此可以认为它们的理论意义远大于实用价值。对实用而言，构造方法满足简洁实用、性能优良就足够了。基于这种设计理念，人们采取了两种策略。第一种是结合随机搜索开发的结构化构造方法。2005 年，何善宝[40] 利用稀疏二进制序列构造出了 girth 为 8、码长为 1008 的规则 LDPC 码。2005 年，彭立[41]利用“皇后问题”构造出一类码长和码率较灵活的 LDPC 码。第二种策略是采用通信领域人们熟知的方法来构造 LDPC 码。2004 年文红[42]采用光正交码构造了 LDPC 码，光正交码可以通过差族、正交拉丁方等组合设计来构造，因此这种方法可以看作是一种间接构造方法。 4 伪随机 LDPC 码的构造研究进展 −)6,3( 结构化方法一般强烈依赖于已有数学对象，因此码长、码率、行重、列重等参数存在较多限制。应用伪随机方法，人们可以将独特的设计理念自由融入 LDPC 码的构造中。Gallager 构造法、MacKay 构造法、基于 girth 分布的启发式搜索法、比特填充法、PEG 法和分割－移位法是已知的几种典型伪随机方法。 4.1 Gallager 构造法 1962 年 R.G.Gallager 首次提出 LDPC 码的概念[1]，并且给出了一种伪随机构造方法。 -7-

中国科技论文在线 http://www.paper.edu.cn 行中的第列至第 ρi 列为 1，其余为零。其余子矩阵是由首个子矩阵经过随机列置换得到的。 ργ k k × 的校验矩阵由γ个子矩阵按列拼接而成。对于首个子矩阵，第 ( −i ρ)1 可见，R.G.Gallager 给出的 LDPC 码构造方法不能保证消除 4 环。 ≤≤ 1( k ) i i 4.2 MacKay 构造法 2/MN − 1996 年 D.J.C.MacKay 重新发现了 LDPC 码，并且给出了 LDPC 码的三种伪随机构造方 NM × 的矩阵 H，满足条件：列重为γ、行重尽量均匀，并且任意两法[43]：（1）随机产生列中 1 的重合次数至多为 1；（2）首先产生 2/M 个列重为 2 的列，这些列之间 1 的重合次数为 0。然后随机产生个列应该满足行重尽量均匀，并且保证整个矩阵中任意两列 1 的重合次数至多为 1。（3）与（1）和（2）基本相同; 不同之处在于，为了保证 Tanner 图的环长至少为某个长度l ， H 矩阵中的某些列被删除。以上三种方法一般情况下得到非规则 LDPC 码。对于构造法（2），MacKay 在 1999 年给出两点说明。第一，在构造方法中引入列重为 2 的列可能会使 LDPC 码的实际性能更好。第二、为了较容易地构造出性能较好的矩阵，列重为 2 的列不能超过 2/M 个，否则 LDPC 码很可能包含低重量码字。个列重为 3 的列；这 2/MN − 4.3 基于 girth 分布的启发式搜索法 2001 年 Mao Yong-Yi[44]将 girth 概念推广为 girth 分布，并设计了一种启发式搜索法。“符号节点 u 的 girth” 是指通过节点 u 的最短环的长度。 “girth 分布 ” 是一系列离散值 lg l 是 ),( ，其中 )(lg 代表 girth 取值为 l 的符号节点占总符号节点的比例， max ,...,6,4 l max = l Tanner 图中最长环的长度。“平均 girth”定义为 2/ ∑ = l max k 2 kg 2)2( ⋅ k 。首先，利用随机构造法构造一个 LDPC 码集合，集合中的码具有相同的码长和度分布；然后挑选“平均 girth”最大的 LDPC 码作为目标 LDPC 码。与集合中随机挑选的码相比，目标 LDPC 码没有错误平层现象，高信噪比区的性能显著提高。 4.4 比特填充法 2001 年 J.Campello 等人[45]提出一种构造 LDPC 码的启发式构造法－比特填充法及扩展比特填充法。扩展比特填充法的根本原则是，在设定的 girth 约束下将“1”逐个填入校验矩阵， girth 约束在算法执行过程中不断调整。算法开始时，girth 约束被设置为最大值 g ；当不降低 girth 约束算法就不能继续执行时，girth 约束减 2；然后算法在新的 girth 约束下继续执行。依此类推，当所有的“1”都成功地填入校验矩阵或者 girth 约束已经低于预设的最小值 g 时， } 算法停止。前一种情形表明校验矩阵构造成功，后一种情形表明构造失败。设 , aa L ,{ 1 2 Na 是校验矩阵 H 各列的列重，则在比特填充法。（扩展）比特填充法的研究停留在策略与仿真层次，几乎无理论结果。 g = ，且 L2 N = a 1 时扩展比特填充法退化为 = = = g a a a 4.5 渐进边增长法 2001 年 Hu Xiao-Yu[5][6]提出了 PEG（渐进边增长）算法，它的根本原则是首先寻找距离符号节点最远的校验节点，然后在符号节点和该校验节点之间放置一条边。这种策略能使符号节点在添加新边时保持其局部 girth 最大化。PEG 算法可以预先为 Tanner 图的 girth 提供 -8-

分享到：

赞收藏

资料库

论文研究-LDPC码构造理论的研究进展 .pdf

相关推荐

开发技术

热门标签

最新资料