摘要：利用切比雪夫多项式良好的逼近性，提出了基于切比雪夫多项式拟合的BP译码算法，并将该算法在FPGA上进行了实现.该算法利用切比雪夫多项式拟合算法对传统BP算法中的复杂函数进行拟合，用少量的乘法和加法运算代替传统BP算法中的复杂函数.此外，调整得到的多项式系数，使其便于硬件实现.同时，提出一种基于移位运算的切比雪夫结构，减小因乘法器的实现带来的复杂度；并提出基于流水线设计的半并行结构，设计并实现了低复杂度的BP译码器.实验结果表明，相比于相关工作，这种结构能有效减少硬件资源.
关键词：FPGA；LDPC（Low Density Parity Check）码；BP译码
中图分类号：TN47 文献标识码：A
A FPGA Design and Implementation
of Low-complexity Decoder for LDPC Code
SHI Shao-bo， QI Yue， WANG Qin
（School of Computer & Communication Engineering， Univ of Science & Technology Beijing， Beijing 100083， China）
Abstract： Taking advantage of the good approximation performance of Chebyshev polynomial， this paper proposed a BP algorithm based on Chebyshev polynomial fitting. And this method can transform the complicated index formula into polynomial， which can reduce the consumption of memory resources. At the same time， a Chebyshev structure with shift operation was proposed to reduce the complexity brought by multiplier； also a semi-parallel architecture with pipeline design was proposed to reduce the complexity of BP decoder. The experimental results show that such a structure can effectively reduce the hardware resources.
Key words： FPGA； LDPC code； BP decoding
1963年，Gallager提出了低密度奇偶校验（Low Density Parity Check， LDPC）码及其相应的译码算法[1].根据文献[2]中所述，在无记忆的高斯白噪声信道下，LDPC码的性能与香农极限仅有不到0.1 dB的差.由于其较高的译码性能，LDPC码被广泛应用于当前各种通信系统中.如DVB-S， WLAN以及WiMAX[3]等流行的无线通信系统.
置信传播（Belief Propagation， BP）译码算法被认为是最优的迭代译码算法[1].然而，BP算法中，大量使用了乘法和指数的运算，从而导致了LDPC码的实现复杂度较高，无法适用于高速通信系统中.目前，主要有两类方法来降低LDPC码的译码实现复杂度.第一类是通过对原始BP算法中的复杂公式进行变形，从而降低其实现复杂度.如文献[4]提出了最小和（Min-Sum）迭代译码算法.该算法利用简单的符号函数和加法运算来代替传统BP算法中的指数运算和乘法运算.最小和算法虽然使得LDPC码的译码实现复杂度得到了降低，但其性能与传统BP算法相比，降低了1 dB左右[5]；另一类是基于ROM查表方法[6].ROM查表法的实现结构简单，准确度较高，应用较广泛.但是，受到ROM容量的限制，性能的提高很有限.因此，需要寻找一种在不影响译码性能的前提下，能够有效地降低实现复杂度的译码算法.
本文提出了一种适合于VLSI实现的LDPC码译码算法.首先，使用切比雪夫多项式拟合的方法，对传统BP算法中的复杂函数进行拟合，使用少量的乘法运算和加法运算来代替传统BP算法中的复杂函数的运算.其次，对文献[7]中的半并行译码结构进行了改进，提出了对基于切比雪夫多项式拟合的LDPC译码算法的基于流水线半并行译码器结构设计，进一步提高了LDPC码的译码速度，从而提高了整个通信系统的实时性.
本文的结构安排如下：第1部分简要描述LDPC码的基本概念以及传统的BP算法.第2部分描述基于切比雪夫多项式拟合的LDPC译码算法.第3部分介绍基于切比雪夫多项式拟合的LDPC译码算法的硬件结构设计.第4部分给出基于切比雪夫多项式拟合的LDPC译码算法的性能分析与验证.第5部分给出本文的总结.
1 LDPC码及其BP译码算法
1.1 LDPC码简介
LDPC码是一种线性分组码，可以用Tanner图或校验矩阵H来表示.由于校验矩阵中的元素绝大部分为“0”，“1”的个数很少，因此LDPC码又称为稀疏图码，并且Tanner图与校验矩阵是相对应的，如图1所示.
1.2 BP译码算法
LDPC码的BP译码算法是基于Tanner图的消息迭代译码算法.该算法的理论依据是：1）贝叶斯准则，即：P（X|Y） = P（Y|X）P（X） / P（Y）；2）判决准则：如果 P（X=0|Y） >= P（X=1|Y） => X = 0；如果 P（X=0|Y） < P（X=1|Y） => X = 1.
