基于修正函数线性拟合的Turbo码译码算法

Ｊｏｕｒｎａｌ　ｏｆ　Ｃｏｍｐｕｔｅｒ　Ａｐｐｌｉｃａｔｉｏｎｓ　计算机应用，２０１２，３２（８）：２１１３—２１１５，２１３２　ＩＳＳＮ　１００１．９０８１　

ＣＯＤＥＮ　ＪＹＩＩＤＵ　２０１２—０８．０１　

ｈｔｔｐ：／／ｗｗｗ．ｊｏｃａ．ｃｎ　

文章编号：１００１—９０８１（２０１２）０８—２１１３—０３　ｄｏｉ：１０．３７２４／ＳＰ．Ｊ．１０８７．２０１２．０２１　１３　

基于修正函数线性拟合的Ｔｕｒｂｏ码译码算法　

李政。，宋春林，赵运杰，吴朱佳　（同济大学电子与信息工程学院，上海２０１８０４）　（｝通信作者电子邮箱ｌｚ＿２３０＠１６３．ｃｏｍ）　摘要：新一代移动通信系统ＬＴＥ／ＬＴＥ—Ａ具有高吞吐率的突出特点和需求，但高速译码也对误码率和延时等提出　了更高的要求。现有的Ｔｕｒｂｏ码译码算法中，Ｌｏｇ—ＭＡＰ算法译码性能较好，但算法复杂度高，时延大；而Ｍａｘ—Ｌｏｇ－ＭＡＰ算　法虽然具有较低的复杂度，但译码性能较差。为此，提出一种基于修正函数线性拟合的Ｔｕｒｂｏ译码算法，该算法针对不　同刻度区间采用不同的拟合参数。实验仿真表明，该算法与现有算法比较，能够达到Ｌｏｇ—ＭＡＰ算法的译码性能，且避免　了Ｌｏｇ—ＭＡＰ的大量运算，从而在保证较好译码性能的基础上，有效地降低了译码延时，并且便于硬件实现。　关键词：Ｔｕｒｂｏ码；Ｌｏｇ—Ｍａｐ；Ｍａｘ—Ｌｏｇ－ＭＡＰ；译码延时；修正函数；线性拟合　中图分类号：ＴＮ９１１．２５４；ＴＮ９１９．３２　文献标志码：Ａ　

Ｔｕｒｂｏ　ｄｅｃｏｄｉｎｇ　ａｌｇｏｒｉｔｈｍ　ｂａｓｅｄ　ｏｎ　ｌｉｎｅａｒ　ａｐｐｒｏｘｉｍａｔｉｏｎ　ｏｆ　ｃｏｒｒｅｃｔｉｏｎ　ｆｕｎｃｔｉｏｎ　ＬＩ　Ｚｈｅｎｇ　，ＳＯＮＧ　Ｃｈｕｎ—ｌｉｎ，ＺＨＡＯ　Ｙｕｎ－ｊｉｅ，ＷＵ　Ｚｈｕ－ｊｉａ　（Ｃｏｌｌｅｇｅ　ｏｆＥｌｅｃｔｒｏｎｉｃｓ　ａｎｄ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｔｏｎｇｊｉ　Ｕｎｉｖｅｒｓｉｔｙ，Ｓｈａｎｇｈａｉ　２０１８０４，Ｃｈｉｎａ）　

Ａｂｓｔｒａｃｔ：Ａｓ　ｔｈｅ　ｎｅｗ　ｇｅｎｅｒａｔｉｏｎ　ｃｏｍｍｕｎｉｃａｔｉｏｎ　ｓｙｓｔｅｍ，ＬＴＥ／ＬＴＥ—Ａ　ｒｅｑｕｉｒｅｓ　ｒｅｌｉａｂｌｅ　ｃｏｍｍｕｎｉｃａｔｉｏｎ　ｏｆ　ｈｉｇｈｅｒ　ｓｔａｎｄａｒｄ　ｆ０ｒ　ｉｔｓ　ｈｉｇｈ—ｔｈｒｏｕｇｈｐｕｔ　ｃｈａｒａｃｔｅｒｉｓｔｉｃ．Ａｍｏｎｇ　ｔｈｏｓｅ　ｄｅｃｏｄｉｎｇ　ａｌｇｏｒｉｔｈｍｓ　ｏｆ　Ｔｕｒｂｏ．Ｌｏｇ—ＭＡＰ　ａｌｇｏｒｉｔｈｍ．ａｓ　ａ　ｓｉｍｐｌｉｆｉｅｄ　

ａｌｇｏｒｉｔｈｍ，ｈａｓ　ａ　ｇｏｏｄ　ｐｅｒｆｏｒｍａｎｃｅ，ｂｕｔ　ｉｔｓ　ｈｉｇｈ　ｃｏｍｐｌｅｘｉｔｙ　ａｎｄ　ｄｅｌａｙ　ｉｓ　ｓｔｉｌｌ　ａ　ｂｉｇ　ｐｒｏｂｌｅｍ；Ｍａｘ—Ｌｏｇ—ＭＡＰ　ａｌｇｏｒｉｔｈｍ　ｗｉｔｈ　ｌｏｗ　ｃｏｍｐｌｅｘｉｔｙ　ｃｏｕｌｄ　ｎｏｔ　ａｃｈｉｅｖｅ　ａ　ｇｏｏｄ　ｐｅｒｆｏｒｍａｎｃｅ　ａｓ　ｔｈｅ　Ｌｏｇ—ＭＡＰ　ａｌｇｏｒｉｔｈｍ．Ｔｈｉｓ　ｐａｐｅｒ　ｐｒｏｐｏｓｅｄ　ａｎ　ｉｍｐｒｏｖｅｄ　Ｔｕｒｂｏ　ｄｅｃｏｄｉｎｇ　ａｌｇｏｒｉｔｈｍ　ｂａｓｅｄ　ｏｎ　ａ　ｌｉｎｅａｒ　ａｐｐｒｏｘｉｍａｔｉｏｎ　ｏｆ　ｔｈｅ　ｃｏｒｒｅｃｔｉｏｎ　ｆｕｎｃｔｉｏｎ．Ｔｈｅ　ｉｍｐｒｏｖｅｄ　ａｌｇｏｒｉｔｈｍ　ａｄｏｐｔｅｄ　ｄｉｆｆｅｒｅｎｔ　ｃｏｒｒｅｃｔｉｏｎ　ｆｉｔｔｉｎｇ　ｐａｒａｍｅｔｅｒｓ　ｆｏｒ　ｄｉｆｆｅｒｅｎｔ　ｒｅｇｉｏｎｓ．Ｔｈｅ　ｓｉｍｕｌａｔｉｏｎ　ｒｅｓｕｌｔｓ　ｄｅｍｏｎｓｔｒａｔｅ　ｔｈａｔ，ｃｏｍｐａｒｅｄ　ｗｉｔｈ　ｔｈｅ　ｅｘｉｓｔｉｎｇ　ａｌｇｏｒｉｔｈｍｓ，ｔｈｉｓ　ｉｍｐｒｏｖｅｄ　ａｌｇｏｒｉｔｈｍ　ｃａｎ　ａｃｈｉｅｖｅ　ｔｈｅ　ｓａｍｅ　Ｂｉｔ　Ｅｒｒｏｒ　Ｒａｔｅ（ＢＥＲ）ｐｅｒｆｏｒｍａｎｃｅ　ａｓ　ｔｈｅ　Ｌｏｇ—ＭＡＰ　ａｌｇｏｒｉｔｈｍ　ａｎｄ　ｅｆｆｅｃｔｉｖｅｌｙ　ｒｅｄｕｃｅ　ｔｈｅ　ｄｅｃｏｄｉｎｇ　ｄｅｌａｙ．Ｍｏｒｅ　ｉｍｐｏｒｔａｎｔｌｙ，ｔｈｅ　ｐｒｏｐｏｓｅｄ　ａｌｇｏｒｉｔｈｍ　ｉｓ　ｂｅｔｔｅｒ　ｆｏｒ　ｉｍｐｌｅｍｅｎｔａｔｉｏｎ．　Ｋｅｙ　ｗｏｒｄｓ：Ｔｕｒｂｏ　ｃｏｄｅ；Ｌｏｇ－－Ｍａｐ；Ｍａｘ－・Ｌｏｇ－－ＭＡＰ；ｄｅｃｏｄｉｎｇ　ｄｅｌａｙ；ｃｏｒｒｅｃｔｉｏｎ　ｆｕｎｃｔｉｏｎ；ｌｉｎｅａｒ　ａｐｐｒｏｘｉｍａｔｉｏｎ　

０　引言　在一定参数条件下，Ｔｕｒｂｏ码…可以达到距离香农极限　仅差０．７　ｄＢ的优异性能，因此Ｔｕｒｂｏ码被应用于现代通信的　许多领域，如ＬＴＥ／ＬＴＥ—Ａ系统采用Ｔｕｒｂｏ码。　目前，Ｔｕｒｂｏ码有两种主要的译码算法：基于后验概率的　软输出译码算法即ＭＡＰ算法　和软输出Ｖｉｔｅｒｂｉ算法　即　ＳＯＶＡ算法。ＭＡＰ算法是一种计算最大后验概率的译码算　法，采用递推、迭代等方法，将最大对数似然比函数作为软输　出。但是，在此算法提出后的将近２０年的时间里，由于其大　计算量和硬件实现高复杂性而一直没有得到重视；直到１９９３　年Ｔｕｒｂｏ码的发明者在最初的译码方案中修正了ＭＡＰ算法，　人们才重新开始研究该算法，并证明它是实现Ｔｕｒｂｏ迭代译　码的次最优算法，相应的各种简化算法陆续提出。其中，由　ＭＡＰ算法衍生出的两种主要改进算法是Ｌｏｇ—ＭＡＰ算法和　Ｍａｘ—Ｌｏｇ—ＭＡＰ算法。　Ｌｏｇ—ＭＡＰ算法作为一种简化算法在性能上能达到ＭＡＰ　算法译码的性能，但是其修正函数中所含的指数和对数运算　却增加了译码器的复杂度，增大了译码延时，而且更不利于硬　件实现。而Ｍａｘ—Ｌｏｇ—ＭＡＰ虽然通过最大值运算降低了系统　的复杂度，但是因为其忽略了修正函数而降低了其译码性能。　

为了解决此问题　，国内外学者做了相关改进研究，其中典型代　表包括Ｉｍｐｒｏｖｅｄ　Ｍａｘ—Ｌｏｇ—ＭＡＰ　以及Ｓｉｍｐｌｉｆｉｅｄ　Ｍａｘ—Ｌｏｇ—ＭＡＰ　（简称ＳＦ—Ｍａｘ—Ｌｏｇ—ＭＡＰ）　一７ｊ算法。Ｉｍｐｒｏｖｅｄ　Ｍａｘ－Ｌｏｇ—ＭＡＰ　算法虽然在误码性能上较Ｍａｘ—Ｌｏｇ—ＭＡＰ算法有了较大的改　善，但是当信噪比（Ｓｉｇｎａｌ－ｔｏ—Ｎｏｉｓｅ　Ｒａｔｉｏ，ＳＮＲ）较小时相对　ＭＡＰ和Ｌｏｇ—ＭＡＰ算法仍有损失。而ＳＦ—Ｍａｘ—Ｌｏｇ—ＭＡＰ算法通　过对分量译码器的外信息输出进行衰减处理，可以获得更好　的译码性能，但是由于ＳＦ衰减因子的选择对性能影响较大，　很难找到一个合适的ＳＦ衰减因子使其性能达到最优。　综上所述，如何实现高吞吐率下的低误码率的Ｔｕｒｂｏ码　译码，是一个重要课题。基于此，本文提出了一种基于修正函　数线性拟合的Ｌｏｇ—ＭＡＰ类改进算法，该算法对修正函数进行　了拟合改进和优化，针对不同刻度区间采取不同的拟合修正　参数表。实验仿真表明，该算法与现有Ｌｏｇ—ＭＡＰ类算法比　较，在保证较好译码性能的基础上，有效地降低了译码延时，　并且便于硬件实现。　

１　Ｔｕｒｂｏ编码器与Ｔｕｒｂｏ码的译码　１．１　Ｔｕｒｂｏ编码器　Ｔｕｒｂｏ码的结构有并行级联卷积码（Ｐａｒａｌｌｅｌ　Ｃｏｎｃａｔｅｎａｔｅｄ　Ｃｏｎｖｏｌｕｔｉｏｎａｌ　Ｃｏｄｅ，ＰＣＣＣ）、串行级联卷积（Ｓｅｒｉａｌ　Ｃｏｎｃａｔｅｎａｔｅｄ　

收稿日期：２０１２—０２—１７；修回日期：２０１２—０３—２９。　基金项目：国家自然科学基金资助项目（６０９７００６２）；中央高校基本科研业务费专项资金资助项目（０８００２１９１７４）。　作者简介：李政（１９８７一），男，湖南吉首人，硕士研究生，主要研究方向：宽带无线通信；宋春林（１９７３一），男，湖北当阳人，副教授，博士，　主要研究方向：移动通信、数字图像处理；赵运杰（１９８８一），男，河南信阳人，硕士研究生，主要研究方向：宽带无线通信；　吴朱佳（１９８８一），　男，浙江嘉善人，硕士研究生，主要研究方向：嵌入式系统。　２１１４　计算机应用　第３２卷　Ｃｏｎｙｏｌｕｔｉｏｎａｌ　Ｃｏｄｅ，ＳＣＣＣ）和混合级联卷积码（Ｈｙｂｒｉｄ　Ｃｏｎｃａｔｅｎａｔｅｄ　Ｃｏｎｖｏｌｕｔｉｏｎａｌ　Ｃｏｄｅ．ＨＣＣＣ）三大类　。　。在　

ＬＴＥ／ＬＴＥ—Ａ系统中，采用的Ｔｕｒｂｏ码是ＰＣＣＣ。　对于ＬＴＥ系统，Ｔｕｒｂｏ码的ＲＳＣ编码器的结构如图１所　示，其由两个８状态的编码器和一个内交织器构成。　

一　

Ｉｎｐｕ　ｏｕｔ　Ｔｕｒｂｏ　ｃｏｄｅ　ｎｔｅｒｎａｌ　ｉｎｔｅｒｌｅａ　Ｖｅｒ　【　Ｏｕｔｐｌ　Ｉｔ　２ｎｄ　

一，Ｔ、：ｅｎｔ。“。。　１　ｚ　

ｃ　・Ｉ　，ｒ、ｌ～广　］　ｌ，厂　］　．广　］ｆ　、｝，一～　～，｝、～１　

图１编码器结构　１．２　Ｔｕｒｂｏ码的译码　１．２．１　Ｌｏｇ—ＭＡＰ算法　Ｌｏｇ．ＭＡＰ算法，即对数域算法，利用对数函数的单调性，　把ＭＡＰ算法中的变量都用对数的形式来表示，从而把相应变　量的乘法运算转换成加法运算，同时相应修正译码器的输入　输出，从而大大简化运算。同时，其误码率性能与ＭＡＰ算法　基本一致。定义　（ｓ）、　（ｓ）、　ｓ　，ｓ）　如下：　（５）＝Ｉｎ　Ｏｔ　（ｓ）　（１）　（ｓ）：ｌｎ　（Ｓ）　（２）　（ｓ　，５）＝Ｉｎ　（ｓ　，ｓ）　（３）　定义一个算子ｍａｘ　（・）如下：　ｍａｘ　（　））＝ｉｎ（∑ｅｘｐ（＿厂（　）））　（４）　对于两个变量的情况，算子可变形如下：　ｍａｘ’（　，Ｙ）＝ｉｎ（ｅｘｐ（　）＋ｅｘｐ（Ｙ））＝　ｍａｘ（ｘ，Ｙ）＋Ｉｎ（１＋ｅｘｐ（一Ｉ　一Ｙ　１））　（５）　得到：　占　（ｓ）＝Ｉｎ［∑　（ｓ　）ｙ　（ｓ　，ｓ）］＝　

ｍａｘ　［　一　（ｓ　）＋　（ｓ　，ｓ）］　（６）　（ｓ　）＝Ｉｎ［∑　（ｓ）ｙ　（ｓ　，ｓ）］＝　ｍａｘ　［　（　）＋　（　，　）］　（７）　最终，得到对数似然比如下：　Ｌ（　）＝Ｌｃｙ　＾＋　（　）＋　Ｓｔ＋　Ｙ　（２　１）＋　㈤】一　

ｒ）＋　以　（２ｚ　＿１）　㈠】（８）　其中外信息为　（　）＝　）＋　＿１）＋　㈦卜　

Ｉ）＋　Ｙ　（２　１）　㈠】（９）　根据式（５）可定义修正函数：　（　）＝Ｉｎ（１＋ｅｘｐ（一Ｉ　Ｉ））　（１０）　１．２．２　Ｍａｘ—Ｌｏｇ—ＭＡＰ算法　Ｍａｘ—Ｌｏｇ—ＭＡＰ算法，即最大值运算，Ｍａｘ—Ｌｏｇ—ＭＡＰ对　ＭＡＰ所做的修改是直接在对数域里进行的，计算省去了许多　

指数和对数运算，大大简化了运算量。但Ｍａｘ—Ｌｏｇ—ＭＡＰ忽视　了修正函数，从而在性能上比Ｌｏｇ—ＭＡＰ有一定损失。　１．２．３　Ｉｍｐｒｏｖｅｄ　Ｍａｘ—Ｌｏｇ－ＭＡＰ　通过应用麦克劳林技术展开，并将零阶项和一阶项作为　近似表达式可得　ｌｎ（１＋ｅｘｐ（一Ｉ　＋Ｙ　Ｉ））