第３２卷第６期 飞行器测控学报 Ｊｏｕｒｎａｌ ｏｆ Ｓｐａｃｅｃｒａｆｔ ＴＴ＆Ｃ Ｔｅｃｈｎｏｌｏｇｙ Ｖｏ１．３２ Ｎｏ．６ Ｄｅｃ．２０１３ ２０１３年１２月 ＣＣＳＤＳ近地ＬＤＰＣ译码算法研究 李红梅 ，姚秀娟 （１．中国科学院空间科学与应用研究中心・北京・１００１９０；２．中国科学院大学・北京・１００１９０） 摘 要：针对ＣＣＳＤＳ（空间数据系统咨询委员会）推荐的近地ＬＤＰＣ（低密度奇偶校验）码技术进行了研究，建立了 和积译码算法、对数似然和积译码算法、最小和译码算法的数学模型，并对上述译码算法的译码复杂度和译码性能 进行了仿真分析。分析结果表明，和积译码算法与对数似然和积译码算法的译码性能距离香农限１．２ ｄＢ，最小和 译码算法的译码性能距离香农限１．４５ ｄＢ。因此，提出基于最小和译码算法的改进算法——偏移最小和译码算法 与归一化最小和译码算法，并分析了这２种译码算法的译码复杂度，同时进行了大量仿真实验。实验结果表明，当 偏移因子口：０．１５时，偏移最小和译码算法性能达到最优，译码性能距离香农限１．２５ ｄＢ；当归一化因子ａ一 ０．７４１ ２时，归一化译码算法的译码性能达到最优，译码性能距离香农限１．２ ｄＢ。归一化译码算法具有优异的译码 性能和合理的复杂度，可以遴选作为ＣＣＳＤＳ Ｉ ＤＰＣ的译码算法用于工程实现。此外，还研究了迭代次数对译码性 能的影响，结果表明，当迭代次数大于１ｏ次时，译码性能提升不再明显，故工程实现时迭代次数应设置为１Ｏ次。 关键词：空间数据系统咨询委员会（ＣＣＳＤＳ）；低密度奇偶校验（Ｉ ＤＰＣ）；最小和译码算法；改进最小和译码算法 中图分类号：ＴＮ９ｌ１．２２ 文献标志码：Ａ 文章编号：１６７４—５６２０（２０１３）０６—０５２４—０７ Ｄ０Ｉ：１０．７６４２／ｊ．ｉｓｓｎ．１６７４—５６２０．２０１３—０６—０５２４—０７ Ｒｅｓｅａｒｃｈ ｏｎ Ｎｅａｒ—Ｅａｒｔｈ ＬＤＰＣ Ｄｅｃｏｄｉｎｇ Ａｌｇｏｒｉｔｈｍｓ ｆｏｒ ＣＣＳＤＳ ｉ．ｉ Ｈｏｎｇｍｅｉ ，ＹＡＯ Ｘｉｕｉｕａｎ （１．Ｃｅｎｔｅｒ ｆｏｒ Ｓｐａｃｅ Ｓｃｉｅｎｃｅ ａｎｄ Ａｐｐｌｉｅｄ Ｒｅｓｅａｒｃｈ，Ｃｈｉｎｅｓｅ Ａｃａｄｅｍｙ ｏｆ Ｓｃｉｅｎｃｅｓ，Ｂｅｉｊｉｎｇ １００１９０； ２．Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｃｈｉｎｅｓｅ Ａｃａｄｅｍｙ ｏｆ Ｓｃｉｅｎｃｅｓ，Ｂｅｉｊｉｎｇ １００１９０） Ａｂｓｔｒａｃｔ：Ｒｅｓｅａｒｃｈ ｉｓ ｄｏｎｅ ｏｎ ＬＤＰＣ（Ｉ ｏｗ—Ｄｅｎｓｉｔｙ Ｐａｒｉｔｙ Ｃｈｅｃｋ Ｃｏｄｅ）ｒｅｃｏｍｍｅｎｄａｔｉｏｎｓ ｏｆ ＣＣＳＤＳ（Ｃｏｎｓｕｌｔａｔｉｖｅ Ｃｏｍｍｉｔｔｅｅ ｆｏｒ Ｓｐａｃｅ Ｄａｔａ Ｓｙｓｔｅｍｓ）ｆｏｒ ｎｅａｒ ｅａｒｔｈ ａｐｐｌｉｃａｔｉｏｎｓ．Ｍａｔｈｅｍａｔｉｃａｌ ｍｏｄｅｌｓ ａｒｅ ｃｏｎｓｔｒｕｃｔｅｄ ｆｏｒ ＢＰ ｄｅｃｏ— ｔｈｍ，ａｎｄ ｓｉｍｕｌａｔｉｏｎ ａｎｄ ａｎａｌｙｓｉｓ ｉｓ ｄｏｎｅ ｄｉｎｇ ａｌｇｏｒｉｔｈｍ，ＬＩ ＲＢＰ ｄｅｃｏｄｉｎｇ ａｌｇｏｒｉｔｈｍ ａｎｄ ｒａｉｎｓｕｍ ｄｅｃｏｄｉｎｇ ａｌｇｏｒｉ—ｏｎ ｔｈｅｉｒ ｃｏｍｐｌｅｘｉｔｙ ａｎｄ ｄｅｃｏｄｉｎｇ ｐｅｒｆｏｒｍａｎｃｅ．Ｔｈｅ ｒｅｓｕｌｔｓ ｓｈｏｗ，ｆｏｒ ｒａｔｅ ７／８ ＬＤＰＣ ｃｏｄｅ，ｔｈｅ ｐｅｒｆｏｒｍａｎｃｅ ｏｆ ＢＰ ｎｇ ａｌｇｏｒｉｔｈｍ ｈａｓ ａ ｔｈｒｅｓｈｏｌｄ ｗｉｔｈｉｎ １．２ ｄＢ ｏｆ ｔｈｅ Ｓｈａｎｎｏｎ ｌｉｍｉｔ ｏｆ ｔｈｅ ｂｉｎａｒｙ～ｉｎｐｕｔ ａｄ— ｄｅｃｏｄｉｎｇ ａｎｄ ＬＩ ＲＢＰ ｄｅｃｏｄｉｎｇ ａｌｇｏｒｉｔｈｍ ｈａｓ ａ ｔｈｒｅｓｈｏｌｄ ｗｉｔｈｉｎ １．４５ ｄＢ ｄｉｔｉｖｅ ｗｈｉｔｅ Ｇａｕｓｓｉａｎ ｎｏｉｓｅ ｃｈａｎｎｅｌ；ｔｈｅ ｐｅｒｆｏｒｍａｎｃｅ ｏｆ ｍｉｎｓｕｍ ｄｅｃｏｄｉｏｆ ｔｈｅ Ｓｈａｎｎｏｎ ｌｉｍｉｔ．Ｂａｓｅｄ ｏｎ ｍｉｎ ｓｕｍ ｄｅｃｏｄｉｎｇ ａｌｇｏｒｉｔｈｍ，ｔｗｏ ｉｍｐｒｏｖｅｄ ａｌｇｏｒｉｔｈｍｓ ｏｆｆｓｅｔ ｍｉｎｓｕｍ ｄｅｃｏｄｉｎｇ ａｌ ｔｈｍ—ａｒｅ ｐｒｏｐｏｓｅｄ．Ｄｅｃｏｄｉｎｇ ｃｏｍｐｌｅｘｉｔｙ ｏｆ ｔｈｅ ｔｗｏ ｄｅｃｏｄｉｎｇ ａｌｇｏ— ｇｏｒｉｔｈｍ ａｎｄ ｎｏｒｍａｌｉｚｅｄ ｍｉｎｓｕｍ ｄｅｃｏｄｉｎｇ ａｌｇｏｒｉｎｇ ａｌｇｏｒｉｔｈｍ ｒｅａｃｈｅｓ ｒｉｔｈｍｓ ａｒｅ ａｎａｌｙｚｅｄ ａｎｄ ｓｉｍｕｌａｔｅｄ。Ｗｈｅｎ ｔｈｅ ｏｆｆｓｅｔ ｆａｃｔｏｒ Ｇ一０．１５，ｔｈｅ ｏｆｆｓｅｔ ｍｉｎｓｕｍ ｄｅｃｏｄｉ—ａ ｔｈｒｅｓｈｏｌｄ ｗｉｔｈｉｎ １．２５ ｄＢ ｏｆ ｔｈｅ Ｓｈａｎｎｏｎ ｌｉｍｉｔ．Ｗｈｅｎ ｔｈｅ ｎｏｒｍａｌｉｚｅｄ ｆａｃｔｏｒ Ｑ＿－０．７４１ ２，ｔｈｅ ｎｏｒｍａｌｉｚｅｄ ｒａｉｎｓｕｍ ｄｅｃｏｄｉｎｇ ａｌｇｏｒｉｔｈｍ ｒｅａｃｈｅｓ ａ ｔｈｒｅｓｈｏｌｄ ｗｉｔｈｉｎ １．２ ｄＢ ｏｆ ｔｈｅ Ｓｈａｎｎｏｎ ｌｉｍｉｔ．Ｓｔｒｉｋｉｎｇ ａ ｇｏｏｄ ｂａｌａｎｃｅ ｂｅｔｗｅｅｎ ｄｅｃｏ ｄｉｎｇ ｐｅｒｆｏｒｍａｎｃｅ ａｎｄ ｃｏｍｐｌｅｘｉｔｙ，ｔｈｅ ｎｏｒｍａｌｉｚｅｄ ｄｅｃｏｄｉｎｇ ａｌｇｏｒｉｔｈｍ ｉｓ ａ ｇｏｏｄ ｃａｎｄｉｄａｔｅ ｆｏｒ ＬＤＰＣ ｏｆ ＣＣＳＤＳ ｆｏｒ ｅｎ— ｇｉｎｅｅｒｉｎｇ ｉｍｐｌｅｍｅｎｔａｔｉｏｎ．Ｔｈｅ ｉｎｆｌｕｅｎｃｅ ｏｆ ｔｈｅ ｎｕｍｂｅｒ ｏｆ ｉｔｅｒａｔｉｏｎｓ ｏｎ ｄｅｃｏｄｉｎｇ ｐｅｒｆｏｒｍａｎｃｅ ｉｓ ａｌｓｏ ａｎａｌｙｚｅｄ ａｎｄ ｔｈｅ ｒｅｓｕｌｔｓ ｓｈｏｗ ｔｈａｔ １０ ｉｔｅｒａｔｉｏｎｓ ｉｓ ｔｈｅ ｂｅｓｔ ｃｈｏｉｃｅ ｆｏｒ ｅｎｇｉｎｅｅｒｉｎｇ ｉｍｐｌｅｍｅｎｔａｔｉｏｎ． Ｋｅｙｗｏｒｄｓ：Ｃｏｎｓｕｌｔａｔｉｖｅ Ｃｏｍｍｉｔｔｅｅ ｆｏｒ Ｓｐａｃｅ Ｄａｔａ Ｓｙｓｔｅｍｓ（ＣＣＳＤＳ）；Ｌｏｗ－Ｄｅｎｓｉｔｙ Ｐａｒｉｔｙ Ｃｈｅｃｋ Ｃｏｄｅ（ＬＤＰＣ）； ｍｉｎ－ｓｕｍ ｄｅｃｏｄｉｎｇ ａｌｇｏｒｉｔｈｍ；ｉｍｐｒｏｖｅｄ ｒａｉｎ－ｓｕｍ ｄｅｃｏｄｉｎｇ ａｌｇｏｒｉｔｈｍ ＊收稿日期：２０１３－０７—０１；修回日期：２０１３—０８—０１；网络出版时间：２０１３—１１ ｌ３ １５：４７：３９ 网络出版地址；ｈｔｔｐ：∥ＷＷＷ．ｃｎｋｉ．ｎｅｔ／ｋｃｍｓ／ｄｅｔａｉｌ／１１．４２３０．ＴＶ．２０１３１１１３．１５４７．００７．ｈｔｍｌ 第一作者简介：李红梅（１９８７－－），女，硕士，主要研究方向为信号与信息处理；Ｅ—ｍａｉｌ：ｌｉｈｏｎｇｍｅｉ０７２９＠１６３．ｃｏｒｎ 第６期 李红梅，等：ＣＣＳＤＳ近地ＬＤＰＣ译码算法研究 ５２５ ０ 引 言 １）定义Ｄ一 的某一行元素； ＬＡ２ｌ５ ，Ａ１．１。］； ６ Ｊ Ａｚ１，信道编码技术是制约空间探测技术发展的关键 技术之一，在近地空间通信中，要实现几百Ｍｂｙｔｅ／ｓ ２）记Ｕ一（１ ０ … ０）为５１ｌ×５ｌｌ的单位阵 ３）定义ｚ 一（Ｇ Ｇ ），其中ｉ一（１２，…，１４） 甚至几千Ｍｂｙｔｅ／ｓ的数据传输速率需要编译码复 杂度较低且译码收敛速度快的信道编码技术，传统 的ＲＳ（里德一所罗门）＋卷积码的级联技术已经不能 ４）定义Ｍｉ＝『Ａ ］，由ＺｉＨ ＝＝：０，得到 ＬＡ２Ｊ ， 满足现代空间通信高码率、低功耗的需求；因此 Ｍ Ｕ、＋Ｄ 一０ ＣＣＳＤＳ（空间数据系统咨询委员会）推荐了适用于 近地空问通信的７／８码率的Ｉ ＤＰＣ（低密度奇偶校 验）码技术，并于２０１１年８月将ＬＤＰＣ编码技术写 入了ＴＭ（遥测）和ＡＯＳ（高级在轨系统）的下行信 道编码蓝皮书中，以满足空间通信高速、可靠、低功 耗的需求Ｉ】 ］。 ＬＤＰＣ编码技术是迄今最接近香农极限的编码 技术 ，其码字构造灵活，编码算法和译码算法种类 繁多，目前国内外研究的难点是寻找码字性能以及编 译码复杂度之间的平衡，以使算法能应用于工程实践。 本文在对ＣＣＳＤＳ推荐的近地７／８ ＬＤＰＣ码编 码原理研究的基础上，对ＢＰ（和积）译码算法、ＬＩ一一 ＢＰ（对数似然和积）译码算法以及最小和译码算法 等３种置信度传播迭代译码算法的性能以及复杂度 进行对比分析研究，并采用长（８１７６，７１５４）ＬＤＰＣ码 进行算法的仿真验证，建立译码迭代次数对译码性 能的影响关系模型，遴选出工程上适用的ＬＤＰＣ译 码算法。 １ ＣＣＳＤＳ推荐的７／８ ＬＤＰＣ码 ＣＣＳＤＳ推荐的７／８ ＬＤＰＣ是一类ＱＣ—ＬＤＰＣ （准循环ＬＤＰＣ码），该ＱＣ—ＬＤＰＣ码的校验矩阵由 ３２个５１１×５ｌｌ的循环阵组成Ⅲ３ Ｊ Ｈ—ｌＦＡ】 ＬＡ，１ Ａｌ，２ … Ａ１，ｌ４ Ａ１，１ ５ Ａｌ，１６］ Ａ２ ｌ２．１ Ａ２，２ … ，１４ Ａ２，１ ５ Ａ２，１ ６ Ｊ 每个Ａ 均是一个５１１×５１１的循环阵，矩阵的 行重与列重均为２。循环矩阵是指矩阵的每一行都 是由前一行向右循环一位得到的。该ＱＣ—ＬＤＰＣ的 生成矩阵具有如下形式 Ｇｌ ｊ Ｄ ０ Ｇ１，１ Ｇ１．２ Ｇ２ Ｄ Ｊ ０ Ｇｌ，２ Ｇ２，２ Ｇ ： ： ： ● ● ● Ｇ１４ Ｄ Ｄ Ｊ Ｇｌ４，ｌ Ｇ１４．２ 其中 Ｉ为５１１×５１１的单位矩阵，Ｇ 是５１１×５１１ 的循环矩阵。编码过程如下 ： 则可求出７／８ ＬＤＰＣ的生成矩阵，从而完成编码。 ２ ＬＤＰＣ置信度译码算法 ＬＤＰＣ的译码算法种类繁多，主要包括大数逻 辑、比特翻转、后验概率以及基于置信度传播的迭代 译码算法，其中置信度传播的迭代译码算法利用变 量节点与校验节点之问的消息传递来完成译码，性 能最优且能够接近香农极限＿５］。置信度算法包括 ＢＰ译码算法、ＬＬＲ—ＢＰ算法以及最小和译码算法， 本文主要对以上３种置信度传播迭代译码算法的性 能以及复杂度进行研究，并提出改进的译码算法。 译码所采用的信道模型如图１所示。 ＡｗＧＮ一加性高斯白噪声 图ｌ信道模型 Ｆｉｇ．１ Ｃｏｍｍｕｎｉｃａｔｉｏｎ ｃｈａｎｎｅｌ ｍｏｄｅｌ ２．１ ＢＰ译码算法 每个变量节点对应校验矩阵的一列，每个校验 节点对应校验矩阵的一行。假设在ＡＷＧＮ信道 中，Ｕ一（ １，Ｕ２，“３，…，“＾）表示信息序列，ｖ一（口１， ２， ３，…， ）表示编码后的序列，Ｘ一（ｚ１，ｚ２，ｌｚ３， …， ）表示经过ＢＰＳＫ（二相相移键控）调制后的序 列，将 加入高斯白噪声信道后，信道输出序列为 Ｙ一（ ， ｚ，Ｙ。，…，Ｙ ），再将Ｙ送入译码器进行译 码，得到估计序列五一（ ， 。， 。，…，Ｕ ）。 １）设Ｒ（． ）表示与校验节点Ｊ相连的所有变量 节点的集合，即Ｒ（ ）＝｛Ｊ：Ｈ 一１｝； ２）设Ｒ（ ）＼ｉ表示除ｉ以外与校验节点Ｊ相连 的变量节点的集合； ３）设Ｃ（ ）表示与变量节点ｉ相连的所有校验 节点的集合，即Ｃ（ ）一｛ｉ：Ｈｉ 一１）； ４）设Ｃ（ ）＼Ｊ表示去除Ｊ后与变量节点ｉ相连 的校验节点的集合； ５２６ 飞行器测控学报 第３２卷 ５）设 ，，表示变量节点ｉ传给校验节点 的外 部概率信息，即在得到除Ｊ以外的其他校验节点和 信道外部信息后，判断变量节点 一１的概率。 Ｒ ＝＝＝， Ｐ（ 一１ １ ３２ ｋ∈ｃ（ ）＼ ） 其中Ｒ 是校验节点Ｊ传给变量节点ｉ的外部概 率信息，即在给定信息位及其他信息位具有概 率分布条件下，校验方程Ｊ满足的概率。 类似地，Ｐ 一Ｐ，（ 一１ Ｊ Ｙ ）表示接收到Ｙ 后判 断发送比特 一１的后验概率。 假设存在一个二进制序列ａ：（ｎ ，ａ ，ａ。，…， ａ ），其中Ｐ（ａ＾＝＝＝１）一Ｐ 引理：一个的比特序列，其长度为ｍ，假设 第ｉ个比特为１的概率为Ｐ ，则整个序列中出现偶 数个１的概率为 专＋告Ⅱ（１ １ １—２ｐ ） ｉ一０ 出现奇数个１的概率为 １ １ ｍ 专一告Ⅱ（１—２ｐ ） ｉ一０ 这是信道编码领域中经常使用的一个定理，可直接 使用。 定理（Ｇａｌｌ ．ｏ．ｅｒ定理）：对于（ ，Ｊ， ）规则ＬＤＰＣ 码，Ｐ 代表第ｉ个校验方程中第ｚ个校验比特的值 为１的概率，则 ＰＬ 一０ ｌ Ｙ，ｓ］ 丽 其中 Ｐ［ｚ ＝０ＩＹ，ｓ］表示在校验方程组为ｓ，接收 序列为Ｙ的条件下，判断发送帧中的第ｉ个比特为０ 的概率；Ｐ［ｚ 一ｌ ｌ ，Ｓ］表示在校验方程组为ｓ，接 收序列为 的条件下，判断发送帧中的第ｉ个比特 为１的概率；Ｐ 表示发送序列的第 位为１的先验 概率，则南Ｇａｌｌａｇｅｒ定理可知 ｌ＝＝ １Ⅱ（１—２Ｐ ， ） ｕ ｉ ∈Ｒ（Ｊ）＼ Ｒ 一， 告＋告Ⅱ（１—２ Ｐ ， ） ｉ ＥＲ（ ）＼ｚ 则 Ｑ ， 一Ｐ ⅡＲ ， Ｑ 一（１一Ｐ ）ＩＩ Ｒｏ， 由上可以推出ＢＰ算法的译码步骤如下ｌ＿９。 ： １）初始化。 计算信道传递给变量节点的初始概率Ｐ （１）， Ｐ （０）一１一Ｐ （１），对每个变量节点ｉ和与其相连 的校验节点Ｊ的初始信息为 Ｑ： （０）一Ｐ （０） Ｑ （１）一Ｐ （１） ２）校验节点消息更新。 对所有的校验节点Ｊ和与其相邻的变量节点ｉ，Ｐ 在第ｍ次迭代时，消息更新如下 Ｒ （ｏ）一 １＋告ｌＩ（１～２Ⅱ Ｑ： ”（１） ｉ ∈Ｒ（ ）＼ Ｒ （１）一告 Ⅱ（１—２１ Ｑ （ —１ １）） ｉ ∈Ｒ（ｊ）＼ｉ ３）变量节点消息处理。 百 Ｑ （０）一ｋｕＰ （０）ⅡＲ； （０）Ｊ∈Ｃ（ｉ）＼ 、 一、 一一 Ｑ （１）一ｋｕＰ （１）ⅡＲ （１） ＪＥ（、（ｔ） 其中ｋ 是使Ｑ （０）＋ ’（１）一１的值。 ４）译码判决。 Ｑ ’（ｏ）一ｋｉＰ （０）ＩＩ Ｒ （ｏ） Ｅｃ（ｚ）、７ Ｑ （１）＝ｋｉＰ （１）ⅡＲ （１） ＪＥ（’（ｚ） 其中 志 是使Ｑ （０）＋Ｑ （１ 一１的值。若 （Ｏ）＞ （１），则判断第ｉ个变量节点 一０，否 则为１。 ５）停止译码。 计算伴随式ｚ Ｈ 一０则译码成功，否则继续迭 代直到预定的最大迭代次数。 ２．２ ＬＬＲ—ＢＰ译码算法 将ＢＰ算法从概率域转换到对数域中，定义变 量节点ｉ的先验概率似然比为 Ｌ（Ｐ ）＝＝＝Ｉｎ 校验节点Ｊ传向变量节点ｉ的消息为 ） 瓮 变量节点ｉ传向校验节点Ｊ的消息为 ｌｎ器 再由 ｔａｎｈ（÷ｌｎ（ 。／ｐｔ））一１—２ｐ１ 则校验节点的消息更新式为 Ｌ（ ｚ）一２ ｔａｎｈ－ （、 １ Ｒｉ Ｅ （Ｊ）＼ｚ７ ｔ ａｎｈ（＼ 丢Ｌ（Ｑｉ，ｊ））） 第６期 李红梅，等：ＣＣＳＤＳ近地ＬＤＰＣ译码算法研究 ＬＬＲ—ＢＰ译码算法译码步骤如下： １）初始化。 Ｌ（Ｑ ）一ｌｎ ２）校验节点消息更新。 ＪＬ Ｒｍ ）一２ ｔａｎｈ－ ∈Ｉ］７Ｒ（ｊ ｔｉｉＩ ）＼ 、ａｎｈｉ（ 专Ｌ（ ）） ３）变量节点消息更新。 ｇｍ…，）一Ｌ（Ｐ ）＋ Ｌ（Ｒ ｍ） ＪＥｃ（ｚ）＼７ ４）译码判决。 Ｌ（Ｑ ）一Ｌ（Ｐ ）＋ Ｌ（ＲＺ ） ｊ∈Ｃ（ｆ） ｆ １ Ｌ（Ｑ ）＜０ １ ０ Ｌ（Ｑｍ）≥０ ２．３最小和译码算法 最小和译码算法将ｔａｎｈ（－ｚ）做了近似，进一步 降低了译码算法的复杂度，其他步骤不变，则校验节 点消息更新变为 Ｌ（Ｒｚ ）一ＩＩ ｓｇｎ（Ｌ（￣ ））・ｍｉｎ（Ｉ Ｌ（Ｑ ）１） ｉ ∈Ｒ（Ｊ）＼ ３改进译码算法 ３．１偏移最小和译码算法 最小和译码算法在Ｌ（Ｒ ）取近似值时，其近似 值是高于实际信息值的，因此引入一个偏移量因子 』９，当近似值小于Ｊ９时，将信息值设置为０；当近似值 大于卢时，将信息值统一减去卢，使其更接近真实值， 校验节点消息更新式为 Ｌ（ＲＪ， ）一ＩＩ ｓｇｎ（Ｌ（Ｑ， ））・ｍａｘ｛ａｒｉｎｌ Ｌ（Ｑ． ）Ｉ—ｆｌ，ｏ｝ ∈Ｒ（ ） ３．２归一化最小和译码算法 归一化最小和算法通过将１个归一化因子，即 １个小于１的正常数ａ乘以水平运算中的结果，以 使修正后的值更加接近最小和近似前的值。校验节 点消息更新式变为 Ｌ（Ｒｊ， ）一口Ⅱｓｇｎ（Ｌ（Ｑ￣． ）・ｍｉ 胁 １ Ｌ（Ｑ， ）１ ｉ ∈Ｒ（Ｊ）＼ ４译码算法性能分析 ４．１译码复杂度分析 对于一个码率为１／２的（Ｎ，），，２７）ＬＤＰＣ码（）， 为列重，２ｙ为行重）进行译码复杂度分析。表１～５ 是针对ＢＰ译码算法、ＬＬＲ—ＢＰ译码算法、最小和译 码算法以及最小和译码算法的２种改进算法迭代一 次所需要的运算量，即运算复杂度的分析。 表１ ＢＰ算法一次迭代的译码复杂度 Ｔａｂ．１ Ｃｏｍｐｌｅｘｉｔｙ ｏｆ ＢＰ ｄｅｃｏｄｉｎｇ ａｌｇｏｒｉｔｈｍ 操作数 运算次数 Ｒ ， ２Ｎｙ 次加法，２Ｎｙ 次乘法 Ｒ ． Ｎｙ次加法 Ｑ ． ＮＴ（２＋ｙ）次乘法，Ｎ７次加法 Ｑ ． Ｎ７（１＋ｙ）次乘法 Ｑ？ Ｎｙ（２＋ｙ）次乘法，Ｎ次加法 Ｎ（２＋），）次乘法 表２ ＬＬＲ—ＢＰ译码算法一次迭代的译码复杂度 Ｔａｂ．２ Ｃｏｍｐｌｅｘｉｔｙ ｏｆ ＬＬＲＢＰ ｄｅｃｏｄｉｎｇ ａｌｇｏｒｉｔｈｍ 操作数 运算次数 ｔａｎｈ（ｚ）一鬲ｅＸ ｅ ｘ ２Ｎ），（２ｙ一１）次加法， Ｎｙ（２ｙ一１）次除法 ４Ｎ７（２），一１）次指数 Ｌ（Ｒ ） Ｎｒ次对数 Ｌ（Ｑ ） Ｍ 次加法 Ｌ（ＱＩ） Ｎ（１＋ｙ）次加法 表３最小和译码算法一次迭代的译码复杂度 Ｔａｂ．３ Ｃｏｍｐｌｅｘｉｔｙ ｏｆ ｍｉｎｓａｍ ｄｅｃｏｄｉｎｇ ａｌｇｏｒｉｔｈｍ ～操作数 运算次数 Ｌ（Ｒ…） Ｎ（２３，＋ｌ。ｇ ２），一２）次加法 Ｌ（Ｑ ） Ｎｒ 次加法 Ｌ（Ｑ，） Ｎ（１十 ）次加法 ｓｇｎ（Ｌ（Ｒ ）） Ｎｙ（），一１）次计算符号 表４偏移最小和译码算法一次迭代的译码复杂度 Ｔａｂ．４ Ｃｏｍｐｌｅｘｉｔｙ ｏｆ ｏｆｆｓｅｔ ｍｉｎｓｕｍ ｄｅｃｏｄｉｎｇ ａｌｇｏｒｉｔｈｍ 操作数 运算次数 （２ｙ＋ｌｏｇｚ２’，一２）次加法 Ｎｒ（７—１）次计算符号 Ｎｙ（），一１）次求最小值 Ｎ７（），一１）次求最大值 ＮＺ 次加法 Ｎ（１＋ｙ）次加法 ５２８ 飞行器测控学报 第３２卷 表５ 归一化最小和译码算法一次迭代的译码复杂度 Ｔａｂ．５ Ｃｏｍｐｌｅｘｉｔｙ ｏｆ ｎｏｒｍａｌｉｚｅｄ ｍｉｎｓｕｍ ｄｅｃｏｄｉｎｇ ａｌｇｏｒｉｔｈｍ 操作数 运算次数 Ｌ（Ｒ ） ￣－（２ｙ＋１。ｇｚ ２７—２）次加法 ｓｇｎ（Ｌ（Ｒ ）） Ｎｙ（ｙ一１）次计算符号 。Ⅱｓｇｎ（Ｌ（Ｑ；，，）） Ｎｙ（７—１）次乘法 ｉ ∈Ｒ（Ｊ）＼ Ｌ（Ｑ ） Ｎ７。次加法 Ｌ（Ｑ，） Ｎ（１＋），）次加法 从上述译码复杂度的表格可以看出，ＢＰ译码算 法、ＬＬＲ—ＢＰ译码算法以及最小和译码算法译码复 杂度依次降低；最小和译码算法的改进算法在最小 和译码算法的基础上加人了比较或乘积运算，但译 码复杂度并没有显著上升。 ４．２ ＣＣＳＤＳ近地ＬＤＰＣ标准数据帧格式 ＣＣＳＤＳ近地ＬＤＰＣ码的帧标准数据格式由帧 头１ＡＣＦＦＣ１Ｄ，７ １３６ ｂｉｔ信息位，１ ０２２ ｂｉｔ校验位 以及２ ｂｉｔ虚拟填充位组成（如图２所示）。 ３２ ｂｉＩ帧头 ８ １６０ ｂｉｔ码宁 帧头 Ｉ ７ １３６ ｂｉＩ信息位 。 ｉｔ校验位 ｉ 虚拟填充位 Ｉ Ｉ图２ ＣＣＳＤＳ近地ＬＤＰＣ标准传输帧格式 Ｆｉｇ．２ Ｔｒａｎｓｍｉｓｓｉｏｎ ｆｒａｍｅ ｏｆ ＣＣＳＤＳ ｎｅａｒ－ｅａｒｔｈ ＬＤＰＣ ４．３译码性能分析 基于对ＣＣＳＤＳ推荐的（８１７６，７１５４）ＬＤＰＣ码进 行准循环编码，并进行ＢＰＳＫ调制，在ＡｗＧＮ信道 中进行传输，分别采用ＢＰ算法、ＬＬＲ—ＢＰ算法、最 小和及其改进译码算法进行译码。分析译码参数对 译码算法性能的影响，并对以上几种译码算法的性 能进行对比，遴选出适用于近地Ｉ ＤＰＣ标准、可用 于工程实现的译码算法。仿真模型及译码流程分别 如图１和图３所示。 ４．３．１ 迭代次数对译码性能的影响 对（８１７６，７１５４）Ｉ ＤＰＣ码采用和积译码算法，最 大迭代次数分别设置为１、２、５、１０、１００，观察迭代次 数对译码性能的影响（见图４）。 仿真结果表明，在１Ｏ次以内增加迭代次数，译 码性能有显著提高；当迭代次数增加到１０次以上， 再增加迭代次数，译码性能提升不再显著，而译码复 杂度会随着迭代的次数增加而显著增加。 图３译码流程图 Ｆｉｇ．３ Ｄｅｃｏｄｉｎｇ ｆｌｏｗ ｃｈａｒｔ 留 信噪￣ＬｈｉＢ 图４迭代次数对性能的影响 Ｆｉｇ．４ Ｉｎｆｌｕｅｎｃｅ ｏｆ ｉｔｅｒａｔｉｏｎ ｔｉｍｅｓ ｏｎ ｐｅｒｆｏｒｍａｎｃｅ ４．３．２置信度译码算法的性能 采用近地Ｉ ＤＰＣ标准编码数据帧格式，数据量 １０ Ｍｂｙｔｅ，每帧１ ０２４ ｂｙｔｅ，经过ＢＰＳＫ调制、 ＡＷＧＮ信道传输，迭代次数设置为１ｏ次，分别采用 ＢＰ算法，ＬＩ Ｒ ＢＰ算法，最小和译码算法进行译码， 对比这几种译码算法的性能（见图５）。 第６期 李红梅，等：ＣＣＳＤＳ近地ＬＤＰＣ译码算法研究 ５２９ 图５译码算法的性能对比 Ｆｉｇ．５ Ｐｅｒｆｏｒｍａｎｃｅ ｏｆ ｔｈｒｅｅ ｄｅｃｏｄｉｎｇ ａｌｇｏｒｉｔｈｍｓ 译码结果表明，ＢＰ译码算法与ＬＬＲ—ＢＰ译码 算法的译码性能距离香农限相差１．２ ｄＢ，最小和译 码算法距香农限相差１．４５ ｄＢ，最小和译码算法牺 牲译码性能换取译码复杂度的降低。 ４．３．３改进译码算法的性能 １）偏移最小和译码性能。 采用与上述相同的数据帧格式，分别用最小和 译码算法及偏移最小和译码算法进行译码，当偏移 因子 ＝＝＝０．１５时，偏移最小和译码算法性能达到最 优，译码结果如图６所示。 图６偏移最小和译码算法性能 Ｆｉｇ．６ Ｐｅｒｆｏｒｍａｎｃｅ ｏｆ ｏｆｆｓｅｔ ｍｉｎｓｕｍ ｄｅｃｏｄｉｎｇ ａｌｇｏｒｉｔｈｍ 结果表明，偏移最小和的译码算法距离香农限 １．２５ ｄＢ，性能比最小和译码算法提高０．２ ｄＢ。 ２）归一化最小和译码算法。 采用与上述相同的数据帧格式，分别采用ＢＰ 译码算法及归一化最小和译码算法进行译码，当归 一化因子ａ一０．７４１ ２时，归一化译码算法的译码性 能达到最优。译码结果如图７所示。 结果表明，归一化最小和译码算法性能距离香 农限１．２ ｄＢ，比最小和译码算法提高０．２５ ｄＢ。 继 謇 图７ 归一化最小和译码算法性能 Ｆｉｇ．７ Ｐｅｒｆｏｒｍａｎｃｅ ｏｆ ｎｏｒｍａｌｉｚｅｄ ｍｉｎ—ｓｕｍ ｄｅｃｏｄｉｎｇ ａｌｇｏｒｉｔｈｍ ５ 结 论 本文对ＢＰ译码算法、ＬＬＲ—ＢＰ算法以及最小 和译码算法及最小和译码算法的改进算法进行了建 模与仿真分析。ＢＰ译码算法、ＬＬＲ～ＢＰ算法以及最 小和译码算法的译码复杂度依次降低，译码性能也 依次降低。ＬＬＲ—ＢＰ译码算法将乘法操作变为了加 法操作，但是引入了指数操作和对数操作，译码复杂 度仍然不适用于工程实现。最小和译码算法将ＢＰ 译码算法进行简化，只有实数加法操作，大大降低了 译码复杂度，但是译码性能也较ＢＰ译码算法下降 ０．２５ ｄＢ。 偏移最小和译码算法译码性能距离香农限 １．２５ ｄＢ，译码性能较最小和译码算法提高０．２ ｄＢ； 迭代一次，只在最小和译码算法的基础上增加 Ｎ７（７－－１）次求最大值操作，译码复杂度没有显著 上升。 归一化最小和译码算法译码性能距离香农限 １．２ ｄＢ，译码性能较最小和译码算法提高０．２５ ｄＢ； 迭代一次，只在最小和译码算法的基础上增加 Ｎ７（ｙ－－１）次乘法操作，译码复杂度也没有显著上 升。 综上，归一化最小和译码算法的译码性能最优， 且具有合理的译码复杂度，适用于ＣＣＳＤＳ近地 ＬＤＰＣ译码的工程实现。 参考文献（Ｒｅ｛ｅｒｅｎｃｅｓ） ［１］ ＣＣＳＤＳ １３１．卜Ｏ一２ Ｌｏｗｄｅｎｓｉｔｙ ｐａｒｌｔｙ ｃｈｅｃｋ ｃｏｄｅｓ｛ｏｒ ｕｓｅ ｉｎ ｎｅａｒ－ｅａｒｔｈ ａｎｄ ｄｅｅｐ—ｓｐａｃｅ ａｐｐｌｉｃａｔｉｏｎｓ：ｅａｒｔｈ ｓｔａｔｉｏｎｓ ａｎｄ ｓｐａｃｅｃｒａｆｔＩＳ￣．Ｗａｓｈｉｎｇｔｏｎ Ｄ．Ｃ．：ＣＣＳＤＳ Ｓｅｃｒｅｔａｒｉａｔ，２００７． ［２］ＣＣＳＤＳ ０．０－Ｏ－１ Ｌｏｗ Ｄｅｎｓｉｔｙ Ｐａｒｉｔｙ Ｃｈｅｃｋ Ｃｏｄｅ ｆｏｒ Ｒａｔｅ ７／８ ５３０ 飞行器测控学报 第３２卷 ［ｓ］．Ｗａｓｈｉｎｇｔｏｎ Ｄ．Ｃ．：ＣＣＳＤＳ Ｓｅｃｒｅｔａｒｉａｔ，２００５． ［３］ ＣＣＳＤＳ １ ３０．１－Ｇ一２ ＴＭ ｓｙｎｃｈｒｏｎｉｚａｔｉ０ｎ ａｎｄ ｃｈａｎｎｅｌ ｃｏｄｉｎｇ ［ｓ］．Ｗａｓｈｉｎｇｔｏｎ Ｄ．Ｃ．：ＣＣＳＤＳ Ｓｅｃｒｅｔａｒｉａｔ，２０１２． ［４］ ＣＣＳＤＳ １３１．０ １３－２ ＴＭ ｓｙｎｃｈ∞ｎｉｚａｔｉｏｎ ａｎｄ ｃｈａｎｎｅｌ ｃｏｄｉｎｇ ［ｓ］．Ｗａｓｈｉｎｇｔｏｎ Ｄ．Ｃ，：ＣＣＳＤＳ Ｓｅｃｒｅｔａｒｉａｔ，２０１１． ［５］Ｃｈｕｎｇ Ｓａｃ Ｙｏｕｎｇ．Ｏｎ ｔｈｅ ｄｅｓｉｇｎ ｏｆ ｌｏｗ—ｄｅｎｓｉｔｙ ｐａｒｉｔｙ ｃｈｅｃｋ ｃｏｄｅｓｗｉｔｈｉｎ ０．００４５ｄＢ ｏｆ ｔｈｅ Ｓｈａｎｎｏｎ ｌｉｍｉｔ［Ｊ］．ＩＥＥＥ Ｃｏｍ— ｍｕｎｉｃａｔｉｏｎｓ Ｉ ｅｔｔｅｒｓ，２００１．５（２）：５８－６Ｏ． ［６］Ｌｉ Ｚｏｎｇｗａｎｇ，Ｃｈｅｎ Ｌｅｉ，Ｌｉｎ Ｓｈｕ．Ｅｆｆｉｃｉｅｎｔ ｅｎｃｏｄｉｎｇ ｏｆ ｑｕａ— ｓｉ—ｃｙｃｌｉｃ ｌｏｗ—ｄｅｎｓｉｔｙ ｐａｒｉｔｙ—ｃｈｅｃｋ ｃｏｄｅｓ［Ｊ］．ＩＥＥＥ Ｔｒａｎｓａｃ— ｔｉｏｎｓ ｏｎ ＣｏｍｍｕｎｉｃａｔｉｏｎＳ，２００６，５４（１）：７卜８１． ［７］ Ｇａｌｌａｇｅｒ Ｒ Ｇ．Ｌｏｗ ｄｅｎｓｉｔｙ—ｐａｒｉｔｙ ｄｈｅｃｋ ｃｏｄｅｓ［Ｊ］．ＩＥＥＥ Ｔｒａｎｓａｅｔｉ０ｎ ｏｎ Ｉｎｆｏｒｍａｔｉｏｎ Ｔｈｅｏｒｙ，１９６２，８（１）：２１－２８． ［８］Ｔａｎｎｅｒ Ｒ Ｍ，Ｓｒｉｄｈａｒａ Ｄ，Ｓｒｉｄｈａｒａｎ Ａ，ｅｔ ａ１．ＬＤＰＣ ｂｌｏｃｋ ａｎｄ ｃｏｎｖｏｌｕｔｉｏｎａｌ ｃｏｄｅｓ ｂａｓｅｄ ｏｎ ｅｉｒｃｕｌａｎｔ ｍａｔｒｉｃｅｓ［Ｊ］．ＩＥＥＥ Ｔｒａｎｓ— ａｃｔｉｏｎｓ ｏｎ Ｉｎｆｏｒｍａｔｉｏｎ Ｔｈｅｏｒｙ，２００４，５０（１２）：２９６６—２９８４． ［９］Ｆｏｓｓｏｒｉｅｒ Ｍ Ｐ Ｃ．Ｑｕａｓｉ ｃｙｃｌｉｃ ｌｏｗ ｄｅｎｓｉｔＹ ｐａｒｉｔｙ ｃｈｅｃｋ ｃｏｄｅｓ ｆｒｏｍ ｃｉｒｃｕｌａｎｔ ｐｅｒｍｕｔａｔｉｏｎ ｍａｔｒｉｃｅｓ［Ｊ］．ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｆｏｒｍａｔｉｏｎ Ｔｈｅｏｒｙ，２００４，５０（８）：１７８８—１７９３． ［１Ｏ］ Ｌ ｎ ｓ，Ｃｏｓｔｅｌｌｏ Ｄ ｊ．差错控制编码［Ｍ］．晏坚，何元智，潘亚 汉，等，译．北京：机械工业出版社，２００７． Ｌｉｎ Ｓｈｕ，Ｃｏｓｔｅｌｌｏ Ｄ Ｊ Ｊｒ．Ｅｒｒｏｒ ｃｏｎｔｒｏｌ ｃｏｄｉｎｇ［Ｍ］，Ｔｒａｎｓｌａ— ｔｅｄ ｂｙ Ｙａｎ Ｊｉａｎ，Ｈｅ Ｙｕａｎｚｈｉ，Ｐａｎ Ｙａｈａｎ，ｅｔ ａ１．Ｂｅｉｊｉｎｇ： Ｃｈｉｎａ Ｍａｃｈｉｎｅ Ｐｒｅｓｓ，２００７（Ｉｎ Ｃｈｉｎｅｓｅ）． ［１１］ 贺鹤运．ＬＤＰＣ码基础与应用［Ｍ］．北京：人民邮电出版社， ２００９． Ｈｅ Ｈｅｙｕｎ．ＬＤＰＣ ｃｏｄｅｓ ｆｕｎｄａｍｅｎｔａｌｓ ａｎｄ ａｐｐｌｉｃａｔｉｏｎｓ［Ｍ］． Ｂｅｉｊｉｎｇ：Ｐｏｓｔ＆Ｔｅｌｅｃ０ｍ Ｐｒｅｓｓ．２００９（Ｉｎ Ｃｈｉｎｅｓｅ）． ［１２］ 王新梅，肖国镇．纠错码一原理与方法［Ｍ］．西安：西安电子 科技大学出版社，２００９． Ｗａｎｇ Ｘｉｎｍｅｉ，Ｘｉａｏ Ｇｕｏｚｈｅｎ．Ｅｒｒｏｒ ｃｏｒｒｅｃｔｉｎｇ ｃｏｄｅ－ｐｒｉｎｃｉ— ｐｉｅｓ ａｎｄ ｍｅｔｈｏｄｓ［Ｍ］．Ｘｉ’ａｎ：Ｘｉｄｉａｎ Ｕｎｉｖｅｒｓｉｔｙ Ｐｒｅｓｓ，２００９ （Ｉｎ Ｃｈｉｎｅｓｅ）． （本文编辑：姚旭）
