|
摘 要：本文概述了LDPC码的编译码原理，重点论述在TI公司的DSP(TMS320C6416)上的(512,256)LDPC编译码器的算法实现，并给出其与(2,1,7)卷积码在AWGN信道条件下的纠错性能对比。对比表明(512,256)LDPC码比(2,1,7)软判决的卷积码在误码率为10－4时可具有1.5 dB的编码增益。
关键词：LDPC码；编码；译码；DSP；优化；实现
DSP Implementation of LDPC Codes
CUI Han-ming，LIU Hui-jie，LIANG Xu-wen，YANG Gen-qing
(Micro-satellite State Key Joint Laboratory, Chinese Academy of Science, Shanghai 200050,China)
Ａｂｓｔｒａｃｔ：This paper firstly introduces the principles of Low Density Parity Check (LDPC) coding and decoding,then describes how to implement it on the TI fixed point DSP(TMS320C6416).Finally,it gives the performance comparison between the (512,256) LDPC and (2,1,7)convolutional codes over the AWGN channel. The result indicates that at a bit error rate of 10-4, LDPC codes can offer more than 1.5 dB gain compared with the convolutional codes.
Ｋｅｙｗｏｒｄｓ：LDPC；Coding;Decoding;DSP；Optimize；Implementation
一、引言
LDPC（Low Density Parity Check）码是一种性能很出色的线性分组纠错码,在用非常稀疏的校验矩阵与基于BP（Belief－Propagation）的译码算法的条件下具有逼近Shannon限的性能。与当前流行的Turbo码相比，有以下优势：理论上的性能优于Turbo码，译码复杂度较低。它的译码可以完全并行操作，适合硬件实现。LDPC码这种优异的纠错性能，特别适合于卫星通信、光磁记录系统等。在Gallager提出LDPC码及其解码算法后，新近的研究又提出很多低复杂度的算法。通过DSP可实现这些简化算法。在本文中所使用的仿真算法是基于TI的C6416实现的。
二、LDPC码的编、解码方法
1.编码
LDPC的编码主要是要寻找一种合适的方法产生稀疏校验矩阵。用一个M×N的校验矩阵H来描述LDPC码（M是校验位长，N是码长,K=N-M是信息位长,码率为K/N）,该矩阵可以用最大长度线性同余序列（Maximal-Length Linear Congruential Sequence）产生。
2.LDPC译码
LDPC的译码算法有多种,本文采用的是Log域的Message Passing算法(Log-MP)。该算法复杂度适中,解码性能也较好,比较适合于DSP实现。该算法的关键是迭代计算后验概率(APP)。
定义
式中pi表示接收为yi时发送为1的概率,qij为比特bi的更新值，传递给校验cj，rji为校验cj的更新值，传递给比特bi。
为L(qij)的绝对值。
具体译码算法如下：
(1)初始化
对于高斯噪声信道，初始化比特点:
（2）迭代
1）校验点更新
式中rj表示与第j个check节点相连的bit节点的集合，i′∈rj＼i表示该集合中不包含第i个bit节点的其它元素。
2)比特点更新
式中ci表示与第i个bit节点相连的check节点的集合，j′∈ci＼j表示该集合中不包含第j个check节点的其它元素，其中
3) 判决
①软判决
②硬判决
三、DSP实现及复杂度分析
LDPC码的译码时除了(x)函数的计算外，主要是加法（模2加）运算。使用定点的DSP即可以较低成本获得较好的性能。仿真中选用的是TI的TMS320C6416芯片。该芯片具有超长指令字处理能力，内部有8个并行的功能单元，其中6个ALU，2个乘法器。每个乘法器可在一个时钟周期内运行两个16 bit×16 bit或者4个8 bit×8 bit的运算。两组寄存器组(每组32个32 bit的寄存器)主频可达1 GHz以上，峰值运算速度达到8 000 MIPS。片上集成了一级程序缓存和一级数据缓存各16 kbyte。1 Mbyte的二级缓存可用于RAM或CACHE。两个EMIF端口用于连接各种异步或同步外设。32 bit宽HPI口用于与外部主机通信,采用532针的BGA封装,非常适合于运用在诸如信道编解码、时域均衡、图像处理等需要大量运算的场合。TI提供了集成开发环境CCS。
C6000的软件开发流程一般分3步完成：开发C代码、优化C代码、编写线性汇编代码。在开发C代码后，评估各段代码的执行效率，找出最耗时的部分，对其进行优化，最终使得整个LDPC码的编解码达到可以接受的效率。在上述的解码方案中，(x)函数直接计算不容易实现，可用查表法实现。
LDPC码译码器的空间复杂度相对卷积码的Viterbi译码器要高不少,其所需存储器大小与码长成正比。在实现时，采用了稀疏矩阵压缩存储来减少所需的存储量，本文中的(512，256)LDPC码约使用10 kbyte来存放各种中间结果。系统中不需使用慢速的外部存储器，消除了可能的瓶颈。
由于选用了(512,256)的大稀疏校验矩阵，在解码时存在大量的循环。校验点更新时，共有256×6×6=9 216次循环；比特点更新时，共有512×3×3＝4 608次循环。编程时要充分利用C64软件流水的特点，提高并行度，使得每个指令周期尽可能多的使用各并行单元。软件实现时使用了C语言开发，通过编译器自身的优化,从生成的.asm文件中检查软件流水的情况,对不符合软件流水或效率低下的部分进行反复地修改，直至最终达到比较满意的运算性能。
C64代码优化时主要从以下几方面着手：
(1)为了软件流水，循环体内不能有函数调用，所以要把循环体内函数展开;
(2)循环体内尽量不要有if语句，if语句使得代码执行不连续，会使得流水效率低下或者无法实现软件流水;
(3)循环展开要适度,展开后需要的寄存器个数不能超过C64的寄存器个数;
(4)能用编译器提供的内联函数完成就不要自己编写复杂的C代码，这样可以快速优化C代码。
以本文中的解码算法为例，代码优化前后的性能差异可达数十倍。以下是校验点更新部分的代码：
E：校验矩阵中每行1的数目，仿真中取6
alpha,beta：对应译码算法中的定义。
Lq,Lr：稀疏矩阵L(qij),L(rji)对应的压缩
存取矩阵
)
优化过程如下：
(1)直接根据算法写出上述C代码，其中含有函数调用，循环体无法软件流水，故所耗指令数非常大，约需60万cycles。
(2)将phi－dat()函数去掉，直接使用数组查表，此时在循环体内无函数调用，可以使用软件流水，但由于存在if判断语句，软件流水效率较低，从生成的.asm中可以看出流水的情况:
编译器只能对最里层的循环进行排流水，效率也不高。经过这样的优化，完成校验点更新约需12万cycles。
(3)重新改变软件结构，去除if判断语句。代码改变如下：
在上述代码中，先将(j＝＝k)的情况计入，再在循环外减去,可以消除第一个if语句。同时通过累加符号位得出共有奇数或偶数个负数，而不使用第二个if语句。在优化的过程中，也使用了内联函数(如－extu,－abs等)来实现一些复杂的运算。经过上述优化，该段代码所耗的指令数大大减少，约为2万cycles。从生成的.asm文件也可以看出流水效率大大提高，流水是在第二层循环开始：
对比经过以上三步所得的优化结果，如表1所示。
限于篇幅，仅以校验点更新部分的优化对比为例，可以看出效率相差近30倍。由此可见，对象C64这样的DSP编程与普通的编程不同，要充分利用它的特点，力争最大程度地利用其并行性，增加其软件流水的效率，这样才能充分发挥其能力，达到实用的目的。
在CCS2.0的simulator中进行完整的译码运算性能评估显示：一次解码迭代约需4万cycles。按15次迭代上限计算，解码256个信息比特最多需0.6 MCycles。考虑到编码及其它开销，一个720 MHz的C6416约可以达到250 kbps的吞吐量。实际译码时，迭代次数随着信噪比的增加而迅速减小，在Eb/N0＝2 dB处平均迭代12次，到达3 dB时，平均迭代次数已经降为4次。迭代次数的下降非常有利于降低DSP的功耗。
四、仿真结果
仿真环境如图1所示。
利用图1所示的仿真环境，改变AWGN的信道Eb/N0参数，可得LDPC码在不同Eb/N0时的BER性能；同样将上述环境中的LDPC码改为卷积码，分别使用硬判决和软判决，得到卷积码在不同Eb/N0时的BER性能，结果对比如图2所示。
从图中可以明显地看出相对于(2,1,7)的卷积码，(512,256)这样并不长的LDPC码已经有比较大的纠错性能优势。(512,256)LDPC码比(2,1,7)软判决的卷积码在误码率为10－4时可具有1.5 dB的编码增益。
五、结束语
LDPC码以其优良的纠错性能和相对低的实现难度，日益成为一个研究热点。随着研究的深入，其在卫星通信、移动和固定无线通信、电缆调制/解调器、数字用户环路、光磁存储等方面都有很多的成果。LDPC的编译码有多种方法，在选取时要在复杂度和纠错性能中进行折衷。仿真表明，使用通用DSP实现LDPC的编解码是一个可行、高效的方法。
参考文献
［1］Robert G Gallager.Low density parity check codes［M］. MA:MIT Press, 1963.
［2］Abhiram Prabhakar，Krishna Narayanan.Pseudorandom construction of Low-Density Parity-Check Codes Using Linear Congruential Sequences［J］.IEEE TRANSACTIONS ON COMMUNICATIONS, 2002,50(9).
［3］MACKAY D J C ,NEAL R M. Near Shannon limit performance of low density parity check codes［J］.Electronic Letters , 1996 , 32 :1645～1646.
［4］Jian Sun.An Introduction to Low Density Parity Check (LDPC) Codes［R］.Wireless Communication Research Laboratory，Dept. of Comp. Sci. and Elec. Engr.，West Virginia University.
［5］David J C MacKay.Good Error-Correcting Codes Based on Very Sparse Matrices［J］.IEEE TRANSACTIONS ON INFORMATION THEORY, 1999,45(2).
［6］Hisashi Futaki，Tomoaki Ohtsuki.Low-Density Parity-Check(LDPC)Coded OFDM Systems［Z］.Graduate School of Science and Technology,Science University of Tokyo,Faculty of Science and Technology,Science University of Tokyo.
［7］Texas Instruments.TMS320C6000 Optimizing C Compiler User's Guide(literature number SPRU187）［J］. February 1998.
［8］Texas Instruments.TMS320C6000 CPU and Instruction Set Reference Guide(Literature Number: SPRU189F)［Z］.October 2000.
［9］Texas Instruments.Code Composer Studio User's Guide（Literature Number: SPRU328)［Z］.May 1999.
［10］Texas Instruments.TMS320C62x/C67x Programmer's Guide（Literature Number: SPRU198B)［Z］.February 1998.
［11］ Texas Instruments.TMS320C64x Technical Overview（ Literature Number: SPRU395B)［Z］.January 2001.
［12］王新梅，肖国镇.纠错码－原理与方法［Ｍ］.西安：西安电子科技大学出版社，2001.
［13］Bernard Sklar.数字通信－基础与应用［Ｍ］.第二版.徐平平，宋铁成，叶芝慧,等译.北京：电子工业出版社，2002.
［14］李方慧，王飞，何佩琨.TMS320C6000系列DSPs原理与应用［Ｍ］.第二版.北京：电子工业出版社，2003.
|
