IEEE802.11ac中LDPC译码性能测试

伍永锋，马思根

（贵州财经大学信息学院，贵州 贵阳 550004）

0 引 言

信道编码技术历经几十年的发展历程，从早期的线性分组码、BCH码、卷积码，到后来的RS码、级联码、代数几何码、Turbo码和LDPC码；从原来的代数译码方法，到后面的门限译码、Viterbi译码、迭代译码、软判决译码等概率译码以及软输入输出译码。Gallager[1]于1962年提出低密度奇偶校验码（low density parity check code，LDPC），并证明 LDPC 码是一种性能接近香农极限的编码方案。然而由于受到当时计算机发展水平的限制，要实现这种迭代算法十分的困难。1981年，Tanner生成出了LDPC码，并且用图论的方式将码字表示出来，现在这种图示的方式叫做Tanner[2]图。采用Tanner图构造的LDPC码，通过并行译码可以显著地降低译码复杂度。本文首先介绍下一代无线局域网IEEE802.11ac中LDPC的编码参数，随后分析了典型的LDPC译码算法，并利用Matlab搭建IEEE802.11ac仿真系统，最终得到适合ASIC实现的译码算法与参数。

1 IEEE802.11ac协议中的LDPC码

802.11 ac中，LDPC支持的编码速率、信息块的长度以及编码块的长度如表1所示。

该协议规定的LDPC码为系统码，一个长度为n的码字，包括了k个信息比特，另外加上n-k个校验比特，以使码字满足：H×CT=0，H 为一个（n-k）×n的校验矩阵。每个校验矩阵可以分为大小为Z×Z的子矩阵，这些子矩阵为单位矩阵的循环矩阵或者零矩阵。

2 典型LDPC译码算法

对于LDPC码而言，译码算法是决定该码字性能和应用前景的一个重要因素，而对于译码算法的评价一般包括性能和复杂度两个方面。Gallager在1962年提出LDPC码的同时给出了两种译码算法：基于硬判决的译码算法（bit flipping，BF）和基于软判决的译码算法（probabilistic decoding）。BF译码算法运算量小，复杂度低，适合校验集比较小的情况，但是没有充分发挥LDPC码的性能；Gallager首先在译码领域引入了软输入、软输出的译码思想，但是在当时计算机水平发展相对较低，基于软判决的译码算法难以实现。随着计算机水平的不断提高，在1992年由 Mackay 和 Neal[3]提出的 BP（belief-propagation）迭代译码算法正是基于该思想，BP算法也就成为一种兼顾性能和复杂度的译码算法，在没有环的情况下，BP算法等价于最大似然译码。虽然现在的计算机技术可以实现BP算法，但是BP算法仍然是一种复杂度相当高的算法。在随后的研究中，如何尽量保持BP算法的纠错性能的同时如何降低译码的复杂度，成为20世纪90年代LDPC码的一个重要研究热点，从而产生了最小和（MS）算法。

由于BP算法中有大量的乘法运算，在实现时会有相当大的复杂度，而且在大量的乘法下会损失精度。基于对数域的BP译码算法，将乘法运算变为简单的加减法运算，简化了硬件实现的难度。但是在其校验信息比特的更新中设计大量的双曲函数和反双曲函数，需要消耗大量的存储器资源，且会带来量化精度的损失，同样不利用硬件实现。由此出现了对校验信息比特表达式的进一步简化，提出了MS算法，以及修正的MS[4-5]算法，在MS算法上仅仅增加很少的复杂度来达到与BP算法十分接近的性能。

在对降低BP算法复杂度研究的同时，在BP算法基础上寻找更好的译码算法也是大家努力的方向。特别是考虑到译码器硬件实现时迭代次数是有限的，加快BP算法的译码收敛速度将会提升译码吞吐量。一种分层的BP算法[6-7]应运而生，通过对LDPC码校验矩阵进行分层，相应的对BP算法的比特节点更新公式进行修改，使得信息在比特节点和校验节点之间的传播速度加快，从而可以减少迭代次数而达到和BP算法性能相同。

改进的MS算法是对BP算法的校验节点计算公式进行的修改，而分层的BP算法则是对BP算法的比特节点计算公式进行的修改；因此，将这两种改进算法的思想结合起来，能够得到一种性能好、复杂度低和收敛速度快的分层修正MS译码算法，目前已经成为LDPC码译码器设计采用最多的译码算法。

3 译码算法性能分析

用于仿真的系统模型如图1所示。本文将对不同的译码算法、不同的译码迭代次数、不同的归一化因子，在图示仿真系统中进行性能分析，确定ASIC实现方案。

图1 LDPC编译码系统仿真环境

3.1 各种译码算法误码性能测试

由于802.11ac协议中的LDPC码校验矩阵具有近似下三角矩阵的结构，故在编码过程使用RU编码方法，迭代次数为20次。仿真中采用蒙特卡洛方法进行误码率统计，图中BP代表BP算法，Log-BP代表对数BP算法，Min-sum代表最小和译码算法，Layer-modify-MS代表修正的MS分层算法。

通过仿真图2可以看出，最小和译码算法译码性能最差；修正的MS分层算法译码性能接近BP译码算法，但收敛时间更少，其复杂度高于最小和译码算法；从性能和复杂度综合来看，分层修正MS译码算法最适于ASIC实现。故将采用分层修正的MS译码算法作为LDPC实现的译码算法。

3.2 译码迭代次数的选择

译码迭代次数是影响LDPC码译码性能的重要指标，图3是不同迭代次数下的译码性能仿真图。译码的迭代次数影响着系统的吞吐量和解码延迟等系统的关键指标。如果译码迭代次数太小，会严重影响译码性能。但是译码性能也并不是随着迭代次数成正比增加的，在迭代次数达到一个值时，译码次数增加所换来的性能增加并不明显。相比增加迭代次数所带来的实现复杂度，译码性能的提高是微不足道的。所以在保证译码性能的情况下，应尽量减少迭代次数，减少硬件实现的复杂度。为了确定适合802.11ac系统中的LDPC码硬件实现的译码迭代次数，选取码长为1944，码率为1/2，归一化因子为0.8进行仿真。由图3可知，在相同信噪比下，迭代次数越大译码性能越好。当迭代次数为20，30，40次时的译码性能非常接近，考虑到较大的迭代次数会带来较大的解码延迟，硬件设计中建议采用20次为最大迭代次数。

3.3 归一化因子的选择

图4 LDPC码在不同归一化因子下的性能仿真

本文选用了分层修正的MS译码算法，在计算比特节点时，引入了归一化因子，加快其收敛。为了找到合适的归一化因子，本文对不同的归一化因子进行了仿真。图4是不同归一化系数下的译码性能仿真图，码长为1944，最大迭代次数为20，在加性高斯白噪声信道下（信噪比为1dB）的仿真。可以看出，当归一化因子在0.8时，表现出了很好的性能，当归一化因子为0.75时也接近0.8的性能，为了方便硬件实现以0.75作为归一化因子。

4 结束语

本文分析了IEEE802.11ac系统中的LDPC译码算法，通过Matlab仿真平台测试了BP算法、对数BP算法、最小和译码算法、分层修正MS译码算法的性能，结果表明分层修正译码算法适合硬件实现，同时给出了硬件实现时的译码参数。

[1]Gallager R G.Low-density parity-check codes[J].IEEE Transactions on Information Theory，1962：21-28.

[2]Tanner R M.A recursive approach to low complexity codes[J].IEEE Trans Inform Theory，1981，27（5）：533-547.

[3]Mackay D J C，Neal R M.Near shannon limit performance of low density parity check codes[J].IEEE Electronic Letters，1996，32（18）：1645-1646.

[4]Zarkeshvari F，Banihashemi A H.On implementation of min-sum algorithm for decoding low-density paritycheck （LDPC）codes[C]∥ Global Telecommunications Conference.Taipei，Taiwan：2002（2）：17-21.

[5]Howard S L，Gaudet V C，Schlegel C.Soft-bit decoding of regular low-density parity-check codes[J].IEEE Transactions on Circuits and Systems II，2005（99）：1-2.

[6]Li Z W，Chen L，Zeng L G，et al.Efficient encoding of quasi-cyclic low-density parity-check codes[J].IEEE Trans Commun，2006，51（1）：71-81.

[7]Kang S H，Park I C.Loosely coupled memory-based decoding architecture for low density parity check codes[J].IEEE Teans Circuits Syst I，2006，53（5）：1045-1056.