维普资讯 http://www.cqvip.com
。。：。鱼型 塑！。。。。。０。。。＿－＿－ ・ ：－ 。 ＿＿： ＿＿＿＿＿＿＿里 ＿＿＿＿＿＿＿＿＿＿箜 ＿＿＿。・＿＿＿＿－塑造方法章志敏等 ＿＿＿＿＿＿＿。・＿＿＿＿．＿＿＿＿＿＿＿＿＿＿＿＿＿－———————————————————————２００６年１２月第３７卷第４期（总筇１２５期） ’ ’’‘’ …。 ０ 、 …‘’ …， 不含短环的（ｎ，３，ｋ）ＬＤＰＣ码的几何构造方法 章志敏 ，陈卓 ，张霄晔， （１．空军驻上海地区军事代表局，上海２００２３３；２．海军驻上海地区航空军事代表室，上海２００２３３； ３．驻上海航空电子公司军代表室，上海２００２３３） ［摘 要】 提出了基于不含短环的（ ２．七）规则低密度奇偶校验（ＬＤＰＣ）码的一种最短环长为８的（ ，七） 规则ＬＤＰＣ码的几何构造方法。该方法简单直观而有效。仿真结果显示，在ＡＷＧＮ信道中该码具有明显优于 随机构造的规则ＬＤＰＣ码的性能。 ［关键词］ 低密度奇偶校验码；容许斜度对；环；和一积译码 ［中图分类号］ＴＮ９１９［文献标识码］Ａ［文章编号］１００６．１４１Ｘ（２００６）０４。００２３．０４ Ａｎ Ａｐｐｒｏａｃｈ ｔｏ ｔｈｅ Ｇｅｏｍｅｔｒｙ Ｃｏｎｓｔｒｕｃｔｉｏｎ ｏｆ ．３． ＬＤＰＣ Ｃｏｄｅｓ Ｗｉｔｈｏｕｔ Ｓｈｏｒｔ Ｃｙｃｌｅｓ ＺＨＡＮＧ Ｚｈｉ—ｒａｉｎ ，ＣＨＥＮ－Ｚｈｕｏ ，ＺＨＡＮＧ Ｘｉａｏ．ｙｅ’ （１．Ａｉｒ Ｆｏｒｃｅ Ｍｉｌｉｔａｒｙ Ｒｅｐｒｅｓｅｎｔａｔｉｖｅ Ｂｕｒｅａｕ Ｒｅｓｉｄｅｎｔ ｉｎ Ｓｈａｎｇｈａｉ Ｒｅｇｉｏｎ，Ｓｈａｎｇｈａｉ ２００２３３，Ｃｈｉｎａ； ２．Ａｅｒｏｎａｕｔｉｃａｌ Ｍｉｌｉｔａｒｙ Ｒｅｐｒｅｓｅｎｔａｔｉｖｅ Ｏｆｉｆｃｅ Ｒｅｓｉｄｅｎｔ ｉｎ Ｓｈａｎｇｈａｉ Ｒｅｇｉｏｎ ｆｏｒ Ｔｈｅ Ｎａｖａｌ Ｆｏｒｃｅ，Ｓｈａｎｇｈａｉ ２００２３３，Ｃｈｉｎａ；３．Ｒｅｐｒｅｓｅｎｔａｔｉｖｅ Ｏｆｉｆｃｅ ｏｆＡｉｒ Ｆｏｒｃｅ Ｒｅｓｉｄｅｎｔ ｉｎ ＳＡＶＩＣ，Ｓｈａｎｇｈａｉ ２００２３３，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ： Ｂａｓｅｄ ｏｎ（Ｆ／，２，七）ｒｅｇｕｌａｒ Ｌｏｗ Ｄｅｎｓｉｔｙ Ｐａｒｉｔｙ－Ｃｈｅｃｋ（ＬＤＰＣ）ｃｏｄｅｓ ｗｉｔｈｏｕｔ ｓｈｏｒｔ ｃｙｃｌｅｓ，ａｎ ａｐｐｒｏａｃｈ ｆｏｒ ｔｈｅ ｇｅｏｍｅｔｒｙ ｃｏｎｓｔｒｕｃｔｉｏｎ ｏｆ（ｎ，３，ｋ）ｒｅｇｕｌａｒ ＬＤＰＣ ｃｏｄｅｓ ｗｉｔｈ ８－ｇｉｒｔｈ ｉｓ ｐｒｏｐｏｓｅｄ ｉｎ ｔｈｉｓ ｐａｐｅｒ，ｗｈｉｃｈ ｉｓ ｓｉｍｐｌｅ， ｉｎｔｕｉｔｉｖｅ ａｎｄ ｅｆｆｅｃｔｉｖｅ．Ｓｉｍｕｌａｔｉｏｎ ｒｅｓｕｌｔｓ ｓｈｏｗ ｔｈｅｓｅ ｃｏｄｅｓ ａｃｈｉｅｖｅｄ ｐｒｏｐｅｒｔｉｅｓ ｍｕｃｈ ｂｅｔｔｅｒ ｔｈａｎ ｔｈｏｓｅ ０ｆ ｓｔｏｃｈａｓｔｉｃａｌ ｌｙ ｃｏｎｓｔｒｕｃｔｅｄ ｒｅｇｕｌａｒ ＬＤＰＣ ｃｏｄｅｓ ｉｎ ＡＷＧＮ ｃｈａｎｎｅ１． Ｋｅｙ ｗｏｒｄｓ：ＬＤＰＣ ｃｏｄｅｓ；ａｄｍｉｓｓｉｂｌｅ ｓｌｏｐｅ ｐａｉｒ；ｃｙｃｌｅ；ｓｕｍ－ｐｒｏｄｕｃｔ ｄｅｃｏｄｉｎｇ １ 引言 中提出了不含短环的（ｒ／，２， 规则ＬＤＰＣ码的构造 方法，但我们从其仿真结果发现，（ Ｚ 码性能较 １９６２年，Ｇａｌｌａｇｅｒ提出了一种基于稀疏校验矩 差，而（ ３，柚规则ＬＤＰＣ码则具有较优越的性能 阵的线性码，即低密度奇偶校验码【ｌＪ（ＬＤＰＣ）。 【６】，因此，本文在此基础上提出了不含短环的（ ，３， ＬＤＰＣ码通常采ｊ｝ｊ迭代译码算法 Ｊ，在此过程中 规则ＬＤＰＣ码的构造方法。采用该方法产生的 短环的存在使得节点传递出去的消息经过几轮迭代 （ ３．ｋ）ＬＤＰＣ码消除了其对应冈子图上长度为４和 后义传递同其本身，造成了信息的重复利用，降低 ６的环，性能明显优 （ ，２，缈吗利随机产生的ＬＤＰＣ 了译码性能。从代数构造法到启发式搜索法【 ｜４】， 码，更适于实际应用。 学者们提出了许多消除短环的方法。参考文献［５】 预备知识 】：设 为ＬＤＰＣ码的校验矩阵， 维普资讯 http://www.cqvip.com
Ｄｅｃｅｍｂｅｒ ２００６ Ｖｏ１．３７ Ｎｏ．４（ｓｅｒｉａｌ Ｎｏ．１ ２５） 航窄电子技术 ＡＶＩＯＮＩＣＳＴＥＣＨＮＯＬＯＧＹ 显然其有ｖ个校验方程，这些校验方程我们用具有 Ｖ１ Ｖ２ ｖ个校验节点的集合 表示。集合 中某两节点 Ｖ３ Ｖ４ 连线而成的边对应于校验矩阵某一列中两个“ｌ” Ｖ５ －ｑ６ 元素所连的边，这种由集合 中点相连而成的图 Ｖ７ 称为构造图（ｓｔｒｕｃｔｕｒｅ ｇｒａｐｈ）。图ｌ给出了一个６一 环的校验矩阵及其构造图。 令ｖ＝３Ｐ，ｖ为校验节点数量且为３的倍数。 将点集Ｘ＝｛ａ ．．，口Ｐ，ｂ ．．，ｂＰ，Ｃ ．．，ＣＰ）分成节 点数量同为Ｐ的三个子集ＸＩ＝｛ａ ．．，口 ）， ◆…… …‘１Ｉ ｖ６ ｖ４Ｘ２：｛ ．，ｂｐ）和Ｘ３ ｛Ｃｌ，．．．，ＣＰ），每个子集中 图１ ６．环的校验矩阵及其构造图 的点按垂直方向排列。 ｌ 定义１斜度：任取子集 ，， ， 中的两个 子集如 ，， ，， 则连接两个节点 ａ ∈Ｘ，，ｂ，∈Ｘ，的边的斜度定义为Ｓ＝，一ｆ。 Ⅲ１’ 甜私 舢都ｍ 定义２容许斜度对： 当且仅当 一ｆ 一 ．ｒ Ｓ ＝一ｓｇｎ（ｓ』）－（Ｐ—ＩＳｊＩ）时，一个斜度对（ ，，Ｓ，） ｌ ～Ｉ ｌ Ｉ 被称为“容许斜度对”。这里特别指出斜度Ｓ＝０ 一１ ．斜度对（０１ ，０】 斜度对（－Ｉ．６） 斜度对（－５，２） 一 ．ｌ ｌ 自身就构成了一个容许斜度对，相当于斜度对 Ｉ 一１ 一＿＿ｌ １ ＿． Ｉ 图２容许斜度集（（０，０），（・ｌ，６），（－５，２）） ＿： 一 （０，０）。 ● 一ｌ Ｉ 一，．．． ＿一＿＿１ｌ－ ＝一 ）、 ＝ ，．．． ）和 ＝ ，．．．，ｃｐ）， Ｉ — ｌ 一ｌ ｌ — 定义３容许斜度集：一个由斜度对构成的集 ｌ Ｉ 一＿＿ ，Ｉ■ 这样节点子集 ，、，●ｒ ，、 两两之间均构成一个 合，如果集合里所有斜度对都为容许斜度对，则该 ｌ ｌ ● 一 ｌ Ｉ — １ Ｉ 集合称为“容许斜度集”。图２给出了Ｐ＝７时的 容许斜度集。． ｌ 设 ，与 ，之间构成的容许斜度集为：Ｉ Ｉ Ｉ 一个容许斜度集｛（Ｏ，Ｏ），（－１，６），（－５，２））的例子。 Ｉ ｌ Ａ＝｛（ ｌ，ｌ，Ｓ１，２），．．．，（ １，２ｋ－Ｉ，Ｓ１，２ｋ））， ３与Ｘ１构 １ ＿． ．２ 矩阵方法 成的容许斜度集则为： 设要构造一个长度为 （ｎ＝ｋｐ，Ｐ∈Ｎ）的 Ｂ＝｛（ ２．１，Ｓ２，２），．．．，（ ２，２ｋ一１，Ｓ２，２七）），Ｘ３与 ２之 （３，ｋ）规则ＬＤＰＣ码，其校验矩阵 可以为 间构成的容许斜度集为： ３尼个Ｐ×Ｐ的子矩阵，即： Ｃ＝（ ３，ｌ，Ｓ３，２），．．．，（ ３，２ｋ一１， ３，２ ）｝。根据校验矩 Ｏ 日ＯＯ Ｈｏ１，Ｓ，，１阵部分子矩阵的选定，这里有：（ＳＩ．２）＝（０，０）， 一，，…Ｈｏ， １ Ｈ＝ １ ｌ，０ Ｈｉ１…Ｈｉ其中 １，２，３； 一Ｐ＜Ｓｌ２ｆ—ｌ＜Ｏ，－ｐ＜ ２２『＿ｌ＜０， ，，。，七一１ ２ Ｈ２０ Ｈ２１…Ｈ２其中，１ ７ ｋ，并且根据斜度的定义满足下列 。。，七一１ 其中， ｆ，（０ ｆ＜３，０ ＜ｋ）均是一个 关系式：Ｓ１２Ｉ，＝Ｐ＋Ｓ１，，２ 一１， ２，２／＝Ｐ＋Ｓ２．，２＿，～ｌ， ，Ｐ×Ｐ单位阵或单位阵的循环移位，为便于 卜文说 其中，１ ， ｋ：进一步观察我们发现，只要斜 明，此处可选定 ｏ，，（０ ＜ｋ）、Ｈｌｏ、Ｈ２ｏ为 度集 ，Ｂ确定，Ｃ也随之确定，并且满足下列关 ，。Ｐ×Ｐ的单位阵。 系式： ３，２ 一１ Ｓ２２ｊ一１一ＳＩ根据上一节介绍的校验矩阵 对应于校验节 ，，２ 一１’ 点集 ，则 ｏ， １， ２分别对应于三个节点子集 ， ＝一ｓｇｎ（ｓ３， 一１）・ —ｌ ，２ｌ，一ｌＩ），其中Ｊ１≤ 尼。 维普资讯 http://www.cqvip.com
禽短环的（ｎ，３，ｋ）ＬＤＰＣ码的几何构造方法章志敏等 ２００６年ｌ２月第３７卷第４期（总第１２５期） 卜面我们具体来说明如何利用构造图来选取 斜度集，以消除各种环的影响。 ３ 围长为６的（ ，３，七）ＬＤＰＣ码 参考文献［５】已证明了（ ，２，七）ＬＤＰＣ码即子集 Ｉ’ ２， １中的任意两个子集之间不存在 （４ｍ＋２）环，其中，ｍ＝１，２…。换句话说，任意 两子集之间只可能存在４．环、８．环和ｌ２・环（本文 最多考虑到ｌ２．环），而三个子集 １， ２， ３都经 过的最小环为６．环（三个子集中各取一个节点， Ｘｌ ● ａ６ 图３ ４．环构造图 Ｘ２■ ｂ６ ）（３ ● ｃ６ ● ａ５ ｆ－ ／ ｂ５ ● Ｃ５ 之间最少有三条边相连，即６．环），其次，还存在 ８。环、ｌＯ．环和ｌ２．环。 ● ， ［１４ ／ ～■ ｂ４ ～● Ｃ４ ～～点．．． ■ ｂ２ 是 。。。～１Ｉ Ｃ２ 因此，要得到围长为６的（ ，３，七）ＬＤＰＣ码， 只要消除 ｌ， ２， ３中的任意两个子集之间存在 的４．环即可。在构造图上４．环产生于两子集中的 两个节点之间有两条重叠的边相连，如图３所示： 而对应于斜度集每一个４．环可以表述为：在 Ｂ，Ｃ的任意一个斜度集中有相同的斜度存在。 ；乏．舶． ．¨ 舢． ． 所以（ ，３，七）ＬＤＰＣ码不含有长度为４的环，斜度 ，● ａ２ ● ａｌ ■ ｂｌ ● ｃＩ 斜度集需满足下列关系式： ２ ｍａ ｘ ｛Ｓｌ， ２（ 集需满足下列方程式： ／ 当ｆ毋，时， ， ≠ ，， ，，≠Ｉ Ｈ ＋ Ｉ＋Ｉ ： 一。 Ｉ＋Ｉ ， ，一。 ：Ｉ （１） ＝㈤ — ０ 其中，，＝１，２，３；２ ｆ ２ｋ，２ Ｊ ２ｋ。 １，２，Ｊ，＝１，２，ｚ＝１，２。 穗 基．Ｉｇ 只要斜度集的选取满足式（１）的不等约束， 那么，其相应的（ ，３，七）ＬＤＰＣ码的围长为６。 ４ 围长为８的（ ３，七）ＬＤＰＣ码 要得到围长为８的（ ，３，七）ＬＤＰＣ码，只需在 消除４．环的基础上继续消除６一环即可。而由上一 节我们知道，在构造图上６．环产生于对 ．， ，， 只要斜度集的选取满足式（１）和式（２）的 不等约束，那么，其相应的（ ，３，七）ＬＤＰＣ码的围 ５ 仿真与讨论 上文采用构造图的分析方法，具体给出了消 除４．环、６．环的（ ，３，七）ＬＤＰＣ码的不等约束式。 三个子集各取一个节点，三个点两两 根据式（１）和式（２），并通过计算机搜索，选取 了围长为８的（１００８，３，６）ＬＤＰＣ码的下述斜度集： Ａ＝｛㈣，（－７Ｓ９ｏ），（－１５：￣１５），（－３９，１２９），（－１４４２４），（－ｌ ｌｑ５固） ＝相连，从而形成如图４中的三角形结构。对应于斜 度集每一个６．环可以表述为：在 ，Ｂ，Ｃ中各取出 不对应（斜度集 ，Ｂ，Ｃ中分别取第ｆ，，，，个斜度 对，要求ｆ≠，≠，）的一个斜度对，再分别从这 三个斜度对中各取出一个斜度，取出的三个斜度中 最大的斜度绝对值等于较小的两个斜度绝对值之 和。所以（ ，３，七）ＬＤＰＣ码不含有长度为６的环， ｛㈣，（－１４９，１９），（— Ｚ８６），（一１６６，２），（－－６３，１０５），（－８９，７９）） 在高斯信道下，采用ＢＰＳＫ调制方式，迭代 译码次数为５Ｏ，我们应用和．积译码算法 对上面 选取的（１００８，３，６）ＬＤＰＣ码和随机构造的 （１００８，３，６）ＬＤＰＣ码进行了Ｍａｔｌａｂ软件仿真，给 出的性能曲线如图６所示。同时，为了便于说明本 维普资讯 http://www.cqvip.com
Ⅲ Ｄｅｃｅｍｂｅｒ ２００６ Ｖｏ１．３７ Ｎｏ．４（ｓｅｒｉａｌ Ｎｏ．１２５） 航空电子技术 ＡＶＩＯＮＩＣＳ ＴＥＣＨＮＯＬＯＧＹ 文所构造的（ ，３，ｋ）ＬＤＰＣ码的优越性能，特引用 参考文献【５】中围长为１６的（４３６８，２，４）ＬＤＰＣ码的 性能曲线（如图６）作为比较。 从图５和图６所示的两组性能曲线中，我们 可以得出以下结论： （１）从图５中我们可以看出，本文构造的ＬＤＰＣ 码与同条件下随机构造的ＬＤＰＣ码相比，性能上 有了显著提高，特别在高性噪比条件下，本文的 ＬＤＰＣ码在消除４、６环之后，达到了非常优越的 性能。 （２）比较图５和图６，我们发现，本文构造 图５随机与用长为８的（１００８，３，６）ＬＤＰＣ码性能比较 的（ｒ／，３，ｋ）ＬＤＰＣ码在相同码率、更短码长的条件 下性能仍明显优于参考文献【５】中构造的 （ ，２，ｋ）ＬＤＰＣ码，因此，本文的（ｒ／，３，七）码相对于 参考文献【５】的（ｒ／，２，ｋ）码在性能得到明显改善之 后，更适于工程应用的要求。 ６ 结束语 本文提出了一种围长为８的（ 幻规则ＬＤＰＣ 码的构造方法，在有效地消除了４、６环之后，性 能明显优于随机产生的规则ＬＤＰＣ码，在高信噪 比的前提下，码的性能是相当突出的。而如何利用 构造图的方法来产生性能更好的非规则ＬＤＰＣ码 图６随机 尉长为ｌ６的（４３６８，２，４）ＬＤＰＣ码性能比较 仍有待进一步的研究。 参考文献 Ｇａｌｌａｇｅｒ Ｒ．Ｇ，Ｌｏｗ－Ｄｅｎｓｉｔｙ Ｐ ｔｙ Ｃｈｅｃｋ Ｃｏｄｅｓ［Ｊ］．ＩＥＥＥ Ｔｒａｎｓ，ｏｎ Ｉｎｆｏｒｍａｔｉｏｎ Ｔｈｅｏｒｙ，１９６２，ＩＴ－８（３）：２０８—２２０． Ｈｕ Ｘｉａｏ－Ｙｕ，Ｅｌｅｆｔｈｅｒｉｏｕ Ｅｖａｎｇｅｌｏｓ，Ａｒｎｏｌｄ Ｄｉｅｔｅｒ Ｍｉｃｈａｅ１．ａｎｄ Ｄｈｏｌａｋｉａ Ａｊａｙ．Ｅｆｎｃｉｅｎｔ ｉｍｐｌｅｍｅｎｔｔａｉｏｎｓ ｏｆ ｔｈｅ ｓｕｍ．ｐｒｏｄｕｃｔ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｄｅｃｏｄｉｎｇ ＬＤＰＣ ｃｏｄｅｓ【Ｃ】．ＩＥＥＥ ＧＬＯＢＥＣＯＭ，Ｓａｎ Ａｎｔｏｎｉｏ．２００ ｌ。ｌ ０３６．１ ０３６． 刘斌。童胜。白宝明．不含小环的低密度校验码的代数构造方法【Ｊ】．电予与信息学报，２００４，２６（１ １）：Ｉ７７８．１７８２。 Ｙ．Ｍａｏ ａｎｄ Ａ．Ｈ．Ｂａｎｉｈａｓｈｅｍｉ．Ａ ｈｅｕｒｉｓｔｉｃ ｓｅａｒｃｈ ｆｏｒ ｇｏｏｄ ｌｏｗ－ｄｅｎｓｉｔｙ ｐａｒｉｔｙ—ｃｈｅｃｋ ｃｏｄｅｓ ａｔ ｓｈｏｒｔ ｂｌｏｃｋ ｌｅｎｇｔｈｓ［Ｃ］．Ｐｒｏｃ．ＩＣＣ ２００ｌ，Ｈｅｌｓｉｎｋｉ，Ｆｉｎｌａｎｄ，Ｊｕｎｅ ２００１．４ｌ－４４． Ｈａｏｔｉａｎ Ｚｈａｎｇ ａｎｄ Ｍｏｕｒａ Ｊｏｓ ｅ Ｍ Ｆ．Ｔｈｅ ｄｅｓｉｇｎ ｏｆ ｓｔｒｕｔｔｅｄ ｒｅｇｕｌａｒ ＬＤＰＣ ｃｏｄｅｓ ｗｉｔｈ ｌａｒｇｅ ｇｉｒｔｈ［Ｃ］．ＩＥＥＥ ＧＬＯＢＥＣＯＭ． ２００３．４０２２－４０２７． Ｓ．Ｙ．Ｃｈｕｎｇ，Ｔ．Ｊ．Ｒｉｃｈａｒｄｓｏｎ，ａｎｄ ＩＬＬ．Ｕｒｂａｎｋｅ．Ａｎａｌｙｓｉｓ ｏｆ Ｓｕｍ－Ｐｒｏｄｕｃｔ Ｄｅｃｏｄｉｎｇ ｏｆ Ｌｏｗ－Ｄｅｎｓｉｔｙ Ｐａｒｉｔｙ－Ｃｈｅｃｋ Ｃｏｄｅｓ Ｕｓｉｎｇ ａ Ｇａｕｓｓｉｎａ Ａｐｐｒｏｘｉｍａｔｉｏｎ［Ｊ］．ＩＥＥＥ’ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｆｏｒｍａｔｉｏｎ Ｔｈｅｏｒｙ，２００ｌ。４７（２）：６５７．６７０． ［收稿日期］２００６．０９．２８ ［作者简介］章志敏（１９７７－－），男，－Ｔ程师。主要研究方向：计算机网络，无线应用。 陈 （１９８１一），男，助理＿Ｅ程师。主要研究方向：计算机通讯。 张霄哗（１９７７一），女，会计师。主要研究方向：成本控制与研究。 ２６
