机电技术 ２０１１年８月 一种改进的ＭＥＴ．ＬＤＰＣ码的译码算法 孙德红 肖曼 （１．闽南理工学院信息管理系，福建泉州３６２７００；２．厦门大学通信工程系，福建厦门３６１００５） 摘要：在迭代译码算法的基础上，进一步分析平均迭代译码算法，并将平均迭代译码算法用于ＭＥＴ－ＬＤＰＣ码型仿 真，改善了传统迭代译码算法的性能，起到了降低误码平台的作用，并对今后译码算法的研究提出了展望。 关键词：ＢＰ译码算法；平均ＢＰ译码算法；误码平台 中图分类号：ＴＮ９１８＿３ 文献标识码： Ａ 文章编号：１６７２—４８０１（２０１１）０４—０２４—０３ ＬＤＰＣ码以接近香农限的优越性能在信息可 行下一轮的计算，直到所有的校验方程都满足为 靠传输中的良好应用前景已经引起学术界和ＩＴ 止；借助于Ｔｕｒｂｏ码的迭代思想，９０年代出现了 业界的高度重视，成为当今信道编码领域最受瞩 ＬＤＰＣ码的现代译码方案，即ＢＰ译码算法。ＢＰ 目的研究热点之一。研究表明，被优化了的非规 译码算法与因子图密切联系，因子图中，校验节 则ＬＤＰＣ码在码长为１０ 、误比特率（ＢＥＲ）为 点对每一个相邻的变量节点根据其他相邻变量节 １０ 条件下，离香农限仅相差０．０４５ ｄＢ，这远远 点传递的消息并行求和计算边界消息，变量节点 超过了Ｔｕｒｂｏ码，成为最靠近香农限的码。同时， 对每一个相邻校验节点根据其他相邻校验节点传 ＬＤＰＣ码描述简单，对严格的理论分析具有可验 递的边界消息并行求积运算，乘积消息又将调整 证性；译码复杂度低于Ｔｕｒｂｏ码，且可实现完全 对应校验节点的边界计算。经过若干次迭代，最 的并行操作，适合硬件实现；吞吐量大，具有高 终完成因式分解，简单来说就是在因子图的变量 速译码潜力。在同样的码长和码率下，ＭＥＴ—ＬＤＰＣ 点和校验点之间进行消息传递和更新；Ｌｏｇ．ＢＰ译 码（Ｍｕｌｔｉ—Ｅｄｇｅ Ｔｙｐｅ ＬＤＰＣ Ｃｏｄｅ）的纠错性能 码算法把ＢＰ译码算法中的乘法运算转化为加法 优于二进制ＬＤＰＣ码，尤其是在突发信道， 运算，降低了译码复杂度。而最小和译码算法在此 ＭＥＴ—ＬＤＰＣ码纠错的能力甚至优于采用软判决译 基础上进行了进一步的简化，只需求最小值，因 码的ＲＳ码的性能，与二进制码相比，ＭＥＴ—ＬＤＰＣ 而更加易于硬件实现。 码更适合于高阶调制。 下面给出ＢＰ译码算法步骤，用 表示二元 ＬＤＰＣ码在低信噪比区具有优异的性能，ＢＥＲ ［ ，ｋ，ｄ］ＬＤＰＣ码Ｃ的奇偶校验矩阵； 可以随着信噪比的增加而指数下降，但是在高信 Ⅳ（ ）＝ ：Ｈｍ ＝１｝表示与校验点ｍ相邻的变量 噪比区，却呈现出了误码平台（ｅｒｒｏｒ ｌｆｏｏｒ）现象。 点集合； ）＝｛ ： ＝１｝表示与变量点ｎ相 误码平台的产生限制了ＬＤＰＣ码在通信系统中的 连的校验点集合； （ ）／ｍ表示除去校验点ｍ之 进一步应用。本文主要从改进译码算法的角度优 外所有其他与变量点 相连的校验点集合；ｇ… 化了ＭＥＴ－ＬＤＰＣ码的性能，一定程度上降低了 ＭＥＴ－ＬＤＰＣ码的误码平台。 表示变量点ｎ向校验点ｍ传递的消息是 的概 率；ｒｒｎ 表示校验点 向变量点ｎ ，＿～ ｍ ｎ 传递的消息，１迭代译码算法简介 即当变量点ｎ的值为 时，校验点ｍ被满足的概 Ｇａｌｌａｇｅｒ于１９６３年提出了两种古典译码方案 率；，表示迭代次数；则有： 硬判决位翻转译码和软判决位翻转译码，硬判决 （１）初始化：Ｐｎ ｏ，Ｐｎ，ｌ 表示采用 ＢＰＳＫ 调制，位位翻转译码算法可以看作是ＢＰ（信度传播）译 后得到的变量点的初始概率： 码算法的简化形式，可简单描述为：译码器输入为 硬判决获得的初始值ｌ或０，译码器计算所有校 ｑ ｏ＝ｐ（ｘ ＝０）＝Ｐｎ，ｏ； 验矩阵，如果某个参与的校验方程出现错误，并 ｇ １＝ｐ（ｘ ＝１）＝Ｐ¨＝ｌ—Ｐ 且数目超过一个预定值，就改变这个比特的值。计 （２）计算校验点到变量点的信息： 算完整个分组的所有比特后，再用改变后的值进 作者简介：孙德红（１９８３一），女，硕士，研究方向：信息安全与移动通信系统，高效纠错编码技术。 第４期 孙德红等：一种改进的ＭＥＴ－ＬＤＰＣ码的译码算法 ＝Ⅱ（（ｇ 一ｇ ）／（ 一 ｑｑ－，Ｏ，））； ｎ∈（Ⅳｆ删）／”） ｒ（ｔ）ｍ。＝ （１＋ ）； ｒ（ｍｔ） （１一 ）． （３）计算变量点到校验点的信息： 首先计算 为０或１的伪后验概率： ｇ ＝ Ｐ １７ 。； （Ｍ（ ）） ｇ ＝ａｍ…Ｐ。ｎ ． （肘（ ）） 其中 为归一化参数，使得 ｊ＋ ＝１。 然后进行判决，如果判决之为一个有效码字 或迭代次数达到最大，则算法停止，否则 ｇ…ｏ，ｑ ｌ计算如下： ｇ ，ｏ＝（ Ｐ ｔｔｎ， Ｏ ）、／，ｒｍｔ （）ｏ； ｇ ，。＝（ Ｐ ｇ ）／ ． 其中 为归一化参数，使得ｇ 。＋ｇ 。＝１。 ．．２改进的译码算法 迭代译码算法是一种次优算法，迭代译码算 法作用于ＬＤＰＣ码因子图的某种拓扑结构。产生了 陷阱集（ｔｒａｐｐｉｎｇ ｓｅｔｓ），从而使得ＢＥＲ在高信噪比 区难以随着信噪比的增加而显著下降，即呈现出 了误码平台现象。为了降低误码平台，Ｔ．Ｈｅｈｎ等 人提出了平均ＢＰ译码，并把它用于ＬＤＰＣ码，在一 定程度上降低了误码平台。对消息采取平均的方 式可以控制外信息在变量点之间传递的速度，从 而减慢错误的概率消息进出陷阱集变量点的速 度，也可以把消息平均视为在译码过程中增加了 “记忆”，使得下一步迭代中变量点信息更偏向于 正确值。在迭代过程中有时候会出现变量点信息 震荡的情形，这时采取平均则能对其进行有效阻 止。下面给出平均迭代译码的步骤，采用噪声方 差为（，Ｉ 的ＡＷＧＮ信道。 用 表示二元ｆ ，ｋ，ｄ１ ＬＤＰＣ码Ｃ的奇偶校 验矩阵；Ⅳ ）＝｛ ：Ｈ ＝１｝表示与校验点 相ｍ ｍ 邻的变量点集合； ）＝ ： ＝１）表示与变 量点ｎ相连的校验点集合； （ ）／ｍ表示除去校 验点ｍ之外所有其他与变量点ｎ相连的校验点集 合； 表示变量点ｎ向校验点ｍ传递的消息是 的概率；ｒｒａｎ，Ｌ表示校验点ｍ向变量点 传递的 消息，即当变量点 的值为 时，校验点ｍ被满足 的概率；，表示迭代次数；用－－ｇ （ｔ）利－ｇ－ （ｔ 表示第，次 迭代变量点ｎ的值为０和１的平均概率；从第 次迭代开始使用平均。 当， 时： 一ｑ ０＝ｇ 。 －ｇ（ ｇ ．１）１＝ ｇ ．ｉ 当 ＜，＜（ ＋ ）时，更新规则如下： －（１） ，－（Ｉ）－－（ｔ一１）－－（ｔ一２） －（Ｉｒｍ）、 ｇ ，０ ｇ（ｑ ０，ｇ 。０，ｇ ，０，…，ｇ ，０ Ｊ ，－（ｔ） ，－（１）－－（／一１）－－（ｔ一２） －（『ｍ ）、 ｇ ，１ ｇＬｇ ，ｌ，ｇ ，ｌ，ｇ ，１，…，口 ，１ Ｊ 当，≥（ ．ｍ＋ ）时，平均概率更新形式为： －（０ ，－（ｔ） －（ｔ一１） －（ｔ一２） －ｑ一 ＋】）、 ｇ ，０ ｇ（ｑ ，０，ｑＨ，０，ｑ ，０，…ｑ ，０ －（ｔ） ，－－（ｔ） －ｑ一１） －（１—２） －（ｔ一 ＋１）、 ｑ ，１ ｇ（ｑ ，１，ｇ １，ｑ ，１，…ｑ ，１ Ｊ ，每经过一次平均消息迭代后，平均概率－ｇ－ｑ枷）利－ｇ－ （ｔ 被送到校验点，更新如下： －ｇ（ｇ ｏ０ 。：（ （ 一Ｄ ｑ ０）／，Ｊ 。０ ｇ眠１ （６ ｇ ＝（ －ｇ（ ０１／．） 。，Ｊ Ｚ１ 其中 为归一化参数，使得－ｇ－（ １）。＋－ｇ－ （１）１＝１。 ．．平均Ｌｏｇ—ＢＰ译码算法和平均最小和算法中， 只需对相应的对数消息取平均即可。其中ｇ（）可 以取算术平均，几何平均或加权平均等。 ３ 迭代译码和平均迭代译码算法性能对 比分析 采用易于硬件实现的最小和译码算法与平均 最小和译码算法进行比较，这里对变量点的信息取 代数平均，码型选取ＭＥＴ－ＬＤＰＣ码。如图１所示。 图１ ＭＥＴ－ＬＤＰＣ码在最小和算法和 平均最小和算法情况下的性能 ２６ 机电技术 仿真图显示了迭代译码算法和平均迭代译码 ２０１１年８月 性与高速性的增长，信道纠错编译码技术在数字通 信中扮演着越来越重要的作用，而误码平台的产生 限制了性能优越的ＬＤＰＣ码的应用，译码算法在 误码平台中起着非常重要的作用，改进译码算法是 降低误码平台的一个重要研究方向，平均Ｍｉｎ．Ｓｕｍ 译码算法在一定程度上起到了降低误码平台的作 用，今后将继续研究平均迭代的思想，从理论上给 出证明。此外，仍需探寻更好的译码算法。 算法的性能，容易看出，平均迭代译码算法的性 能比迭代译码算法有了明显的改善，增益大约为 ０．５ｄＢ，因此平均Ｍｉｎ．Ｓｕｍ译码算法的性能改进 具有较大的实际应用价值。 ４结语 随着现代社会个人通信服务对传输速率多样 参考文献： ［１】Ｇａｌｌａｇｅｒ Ｒ Ｇ Ｌｏｗ－Ｄｅｎｓｉｔｙ Ｐａｒｉｙ・ｔＣｈｅｃｋ Ｃｏｄｅｓ［Ｍ］，Ｃａｍｂｒｉｄｇｅ，Ｍａｓｓ：ＭＩＴ Ｐｒｅｓｓ，１９６３． ［２】Ｍａｃｋａｙ Ｄ Ｊ Ｃ，Ｎｅａｌ Ｒ Ｍ．Ｎｅａｒ Ｓｈａｎｎｏｎ ｌｉｍｉｔ ｐｅｒｆｏｒｍａｎｃｅ ｏｆ ｌｏｗ ｄｅｎｓｉｙ ｐａｒｔｉｙ ｃｈｅｃｋ ｃｏｄｅｓ［ｔＪ］，Ｅｌｅｃｔｒｏｎｉｃｓ Ｌｅｔｔｅｒｓ，１９９６，３２（１８）：１６４５－１６４６． 【３】Ｔ．Ｈｅｈｎ，Ｓ．Ｌａｅｎｄｎｅｒ，Ｏ．Ｍｉｌｅｎｋｏｖｉｃ，ａｎｄ Ｊ．Ｂ．ＨｕｂｅＬ Ｔｗｏ Ｍｅｔｈｏｄｓ ｆｏｒ Ｒｅｄｕｃｉｎｇ ｔｈｅ Ｅｒｒｏｒ－Ｆｌｏｏｒ ｏｆ ＬＤＰＣ ｃｏｄｅｓ，ｐｒｅｐｒｉｎｔ， ａｖａｉｌａｂｌｅ ｏｎｌｉｎｅ ａｔ ｈｔｔｐ：／／ａｒｘｉｖ．ｏｒｇ／，２００６． ［４】孙德红，肖曼，王琳，曾吉文．ＬＤＰｃ误码平台研究进展［Ｊ］．信息技术，２００９（３）：２６—２９． ［５］％Ｒｉｃｈａｒｄｓｏｎ，Ｅｒｒｏｒ ｆｌｏｏｒｓ ｏｆ ＬＤＰＣ ｃｏｄｅｓ，ｉｎ Ｐｒｏｃ．ｏｆ ｈｅ ｔ４１ Ａｎｎｕａｌ Ａｌｌｅｒｔｏｎ ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍｍｕｎｉｃａｔｉｏｎ，ｃｏｎｔｒｏｌ ａｎｄ ｃｏｍｐｕｔｉｎｇ，Ｏｃｔ．２００３． ［６】Ｌａｒａ Ｄｏｌｅｃｅｋ，Ｚｈｅｎｇｙａ Ｚｈａｎｇ，Ｍａｒｔｉｎ Ｗａｉｎｗｒｉｇｈｔ，Ｖｅｎｋａｔ Ａｎａｎｔｈａｒａｍ，Ｂｏｒｉｖｏｊｅ Ｎｉｋｏｌｉ ，Ｅｖａｌｕａｔｉｏｎ ｏｆ ｈｅｔ Ｌｏｗ Ｆｒａｍｅ Ｅｒｒｏｒ Ｒａｔｅ Ｐｅｒｆｏｒｍａｎｃｅ ｏｆ ＬＤＰＣ Ｃｏｄｅｓ Ｕｓｉｎｇ Ｉｍｐｏｒｔａｎｃｅ Ｓａｍｐｌｉｎｇ［Ｃ］，ＩＴｗ ２００７，Ｌａｋｅ Ｔａｈｏｅ，Ｃａｌｉｆｏｒｎｉａ，Ｓｅｐｔｅｍｂｅｒ ２－ ６，２００７． ［７】Ｒ．Ｌｉｕ，Ｅ Ｓｐａｓｏｊｅｖｉｃ，ａｎｄ Ｅ．Ｓｏｌｊａｎｉｎ，“Ｐｕｎｃｔｕｒｅｄ ｔｕｒｂｏ ｃｏｄｅ ｅｎｓｅｍｂｌｅｓ，＂ｐｒｅｓｅｎｔｅｄ ｔａ ｈｅ ｔＩＥＥＥ Ｉｎｆ．ＴｈｅｏｒｙＷｏｒｋｓｈｏｐ，Ｐａｒｉｓ， Ｆｒａｎｃｅ，Ｍａｒ．２００３． ［８】 Ｊ．Ｒｉｃｈａｒｄｓｏｎ ｎｄ ａＲ．Ｌ．Ｕｒｂａｎｋｅ，“Ｍｕｌｔｉ・Ｅｄｇｅ Ｔｙｐｅ ＬＤＰＣ Ｃｏｄｅｓ，’＇ｈｔｔｐ：／／ｌｈｃｗｗｗ．ｔｅｐｆ１．ｃｈ／ｐａｐｅｒｓ／ｍｕｌｔｉｅｄｇｅ．ｐｓ． ［９】Ｒｉｃｈａｒｄｓｏｎ Ｔ Ｊ，Ｓｈｏｋｒｏｌｌａｈｉ Ｍ Ａ，Ｕｒｂａｎｋｅ Ｒ Ｌ．Ｄｅｓｉｇｎ ｏｆ ｃａｐａｃｉｙ－ｔａｐｐｒｏａｃｈｉｎｇ ｉｒｒｅｇｕｌａｒ ｌｏｗ－ｄｅｎｓｉｙ ｐａｔｒｉｙ‘ｔｃｈｅｃｋ ｃｏｄｅｓ［Ｊ］．ＩＥＥＥ Ｔｒａｎｓ．Ｉｎｆｏ．Ｔｈｅｏｒｙ，２００１，４７（２）：６１９－６３７． ［１０］Ｃｈｉｈ—Ｃｈｕｎ Ｗａｎｇ，Ｏｎ ｈｅ ｔＥｘｈａｕｓｉｔｏｎ ｎｄ ａＥｌｉｍｉｎａｔｉｏｎ ｏｆＴｒａｐｐｉｎｇ Ｓｅｔｓ：Ａｌｇｏｒｉｔｈｍｓ＆Ｔｈｅ Ｓｕｐｐｒｅｓｓｉｎｇ Ｅｆｆｅｃｔ［Ｃ】，ＩＳＩＴ２００７， Ｎｉｃｅ，Ｆｒａｎｃｅ，Ｊｕｎｅ ２４．Ｊｕｎｅ ２９，２００７．