多码率多边类型LDPC码译码器的设计与实现
2011-06-07甘永银胡文江谢东福
甘永银,胡文江,黄 睿,谢东福
(1.重庆邮电大学 重庆市移动通信重点实验室,重庆 400065;2.重庆邮电大学 通信与信息工程学院,重庆 400065;3.重庆电子工程职业学院 软件工程系,重庆 401331;4.厦门大学 宽带无线通信实验室,福建 厦门 361005)
0 引言
LDPC码以其接近香农极限的纠错性能,近年来受到越来越多的关注。目前,LDPC码已经被广泛应用于多种通信标准中,如802.11n,DVB-S2,802.15.3c(WPAN)和802.16e(WiMAX)。而多边LDPC码相对于传统的LD⁃PC码具有更好的纠错性能[1-2],它可视为由多个子码所构成的级联码。通过在多个子码之间分层迭代译码,相较其他的LDPC码码型,多边类型LDPC码(multi-edge-type LDPC codes)具有较为明显的性能优势。
目前LDPC码译码器的架构比较多,实现的吞吐量也比较大,如文献[3]中实现了码长为1024 bit,码率为0.5,吞吐量为1 Gbit/s的译码器。然而在无线通信中,信道通常是时变的,为了适应信道的这一特性,多码率LDPC码的研究成为一个热点。目前,文献[4]已经在硬件上实现了支持码长为360~4200 bit,码率为1/4~9/10的LDPC码译码器。文献[5]也在FPGA上实现了码长为10000 bit,码率分别为1/2,5/8和7/8的LDPC译码器。而在这些译码器中,对固定码长的多码率LDPC码译码器的研究和实现都较少。本文研究的多边类型LDPC码译码器是一种固定码长的多码率译码器,它通过对不同边上的校验信息的删余实现多码率译码。
本文提出了一种实现多边LDPC码码率变化的间隔删余算法,简化了硬件实现的复杂度。设计了一种固定码长不同码率共用相同存储单元的存储资源利用结构和半并行的译码结构,并根据多边子码分层译码的特点对译码器中的变量点和校验点采用分时运算,降低了计算单元的资源消耗。
1 多边类型的LDPC码
1.1 多边类型的LDPC码
多边LDPC码是由Tom Richardson和Rudiger Urban⁃ke提出,这种码型概括为规则的和不规则的LDPC码[1],比如级联树码(CT)、不规则重复累积码(IRA)、低密度产生矩阵码(LDGM)和传统的LDPC码都可以视为多边类型的LDPC码的特殊情况。
多边类型的LDPC码变量点和校验点表示为
式中:d=(d1,d2,…,dn)表示多边类型的度,其中n为边类型的数量;x=(x1,x2,…,xn)表示变量点;xd表示为表示接收的度;r=(r,r,…,r)12t表示与变量点相应的接收分配的度,其中t为不同接收分配类型的数量。假设多边类型的LDPC码的码长为N,因此,变量点类型的数量为v(b,d)N,同理校验点类型的数量为μdN。
1.2 多边LDPC码的多码率算法
本节将介绍一种适合多边LDPC码的多码率算法。由于多边LDPC码的码型结构优于传统的LDPC码,因此可以通过对母码的删余处理获得码率的调整。为了克服短码的随机删余,J.Ha提出了采用分组和排序法(GS)的思想[6]。在此基础上一种简化的GS算法[2]更适合多边LDPC码。通过对度为1和度为2的校验位进行删余实现多码率的译码。
1)通过式(2)计算出删余的位数Npunc,通过式(3)计算出度为2时的最大插入删余比特数Nim。
其中:N为码字长度;k为信息比特长度;Rt为目标码率。
2)如果None≥Npunc,转到步骤3),如果None≤Npunc,转到步骤4)。
3)对度为1的校验点根据上面的分析随机选择Npunc进行删余。
4)对于度为2的校验位,在每2个未删余节点间删余的校验位为随机产生的1个不大于Nim的任意整数None-(Npunc-None)-1。如ti进行删余,标注ti作为第i个整数,并在第i个和(i+1)个未被删余的度为2的校验位中插入ti个删余校验位。
5)如果删余位等于Npunc,就停止。
在None≥Npunc的时候,根据母码特殊码型的特点直接对度为1的校验位进行简单的随机删余达到目标码率。在None≤Npunc时,对度2的校验位进行删余,由于两个为删余节点间的删余个数是随机产生的不易于硬件的实现,所以下节中提出一种适合硬件实现的删余算法,即间隔删余算法。
2 间隔删余算法
提出一种实现多码率的间隔删余算法,并通过实现分析了间隔删余算法与GS算法的资源消耗。本文是以码长为640 bit、码率为0.5的多边类型的LDPC码为母码,利用其多边LDPC码优越的码型结构,根据间隔删余算法对该码的校验位进行删余调整来达到多码率的要求。
度为2的信息节点是由重复累积码产生的,删余节点的似然信息通过前向似然信息和后向似然信息进行更新。以图1为例,在图1中,与删余变量点相连的、至少一个校验点与相邻的、所有变量点都不被删余的定义为一步恢复点(1SR)。在这种情况下,这个校验叫作生存校验。同理,k步恢复点(kSR)定义为删余变量点相连至少1个生存校验点,而这个校验点又至少相连一个(k-1)步恢复点和一些m步恢复点,其中0<m≤k-1。图1中的删余节点的恢复步骤都是两步恢复的,这样每个删余校验点的前向和后向似然信息都没有被删余,能为删余节点提供信息进行更新,这样提高了信息恢复的准确度。间隔删余算法的步骤为:
1)计算出总的删余位数Npunc,公式为
2)如果None≥Npunc,转到步骤3),如果None≤Npunc,转到步骤4)。
3)对度为1的校验位随机选择Npunc进行删余。
4)对度为2的校验位的偶数位依次进行删余,删余数为Ntwo=Npunc-None。
5)如果删余总位数等于Npunc,就停止。
度为2的校验比特的删余处理如图1所示。
根据间隔删余的算法,以MET-LDPC码为母码,码率为0.5,码长640 bit在高斯信道下进行性能仿真。仿真结果与同在高斯信道下码长600 bit的RC irregular LDPC码[7]进行比较,如图2所示。从图2中可以得到间隔删余的MET-LDPC码比RC irregular LDPC码有0.2 dB的增益。
选用了Xilinx公司的Virtex4 xc4vlx15仿真环境为modelsim SE6.5E,表1给出了删余模块在2种算法下的占用资源情况。由于间隔删余算法简单,所以硬件实现时资源占用较少。
3 多码率多边LDPC码译码器结构
3.1 译码器结构
表1 删余模块资源对比
通常LDPC码译码器有并行译码结构、串行译码结构和部分译码结构。并行译码结构能实现很高的吞吐量,但计算单元的并行运用消耗了大量的资源,复杂的互联网络增加了硬件实现的复杂度,如文献[8]实现的并行译码器吞吐量达到了100 Gbit/s。串行译码器即只有1个校验点计算单元CNU和1个变量点计算单元VNU,它能实现最小的硬件资源的消耗,由于其吞吐量太低,不适合实际用途,文献[9]采用的是分段译码的串行译码架构实现。
本文根据多边LDPC码码型结构的特点,提出了一种适合多边多码率的LDPC码的部分并行译码器结构如图3。该结构由变量点计算单元VNU、校验点计算单元CNU、交织器、前后向信息运算单元ANU和存储阵列RAM等部分组成。本文多边LDPC码译码器是通过各个子码分层译码实现的,因此本结构采用子码间循环译码的方法进行更新译码信息。不同子码采用不同的交织器以提高译码性能。译码器每次只能译码一帧的信息,即每一帧的信息只有在各个子码分层译码成功后才能继续译码下一帧的信息。在图3的译码结构中,最顶层是信道信息的存储阵列,该信息是信道传给译码器进行译码的似然信息。最下面一部分是内码译码结构,其中该部分的最后一层是信道传给内码译码的校验信息的存储阵列,通过对该层接收到信息的删余,达到对码率的调整。而中间则是SPC码、IRA码上支路和IRA码下支路几个分层译码部分。其中,SPC码和IRA码由于不同节点连接不同类型的边,因此每种类型的边的交织器不同。准循环交织器能实现无时延的并行交织,所以在每个子层很容易实现流水线操作。根据对计算单元VNU,CNU,ANU等个数为1~k的选择,可以对译码器部分并行译码的度进行配置。本文在资源消耗和译码吞吐量上进行折中,选择并行译码度为8,此时译码复杂度和吞吐量能达到一个比较平衡的点。
3.2 交织网分析
随机交织器由于其随机性的任意排列,在硬件实现时将很难避免并列访问相同的内存,而导致访问冲突。在图3的多边类型的LDPC码译码器结构中,选择准循环交织器作为译码器的交织器。准循环交织器在性能上比随机交织器好,而且硬件实现较简单。对于一个度为j的节点,j点位置的连续信息都必须分配在1个RAM中。因此,存储器RAM与计算单元互相对应。
通过Matlab仿真可知,一个度为P的信息通过准循环交织器是可以无时延地存储到P个RAM中的。例如图4就是1个码长25,并行度P=5的循环交织过程。5个变量点计算的信息通过5个多路选择器可以无冲突地同时存储到5个RAM中。在本文的码型长度中经过Matlab仿真分析,所需要的码型长度在P=4或者P=8时都能无时延地进行交织。
3.3 实验结果
本文采用输入软信息5 bit均匀量化,译码外信息6 bit均匀量化的方式,在Xilinx Virtex4 xc4vlx100,仿真环境为modelsim SE 6.5c,在140 MHz的时钟上实现了码长为640 bit,码率为0.5~0.8的多码率多边LDPC码译码器。表2给出了整个译码器的占用资源情况,其中百分数表示所消耗资源占FPGA总资源的比例。
表2 译码器整体资源
4 结论
本文先介绍了一种多码率多边类型的LDPC码,随后提出一种间隔删余算法,设计了一种多码率多边类型的LDPC码译码器架构,该架构采用部分并行译码结构,能实现固定码长不同码率共用相同的存储资源。基于该架构在Xilinx Virtex4 xc4vlx100芯片上实现了码长为640 bit,码率为0.5~0.8的多码率多边类型的LDPC码译码器。实验结果表明,该译码器的平均吞吐量能达到10 Mbit/s。
[1]RICHARDSON T J,URBANKE R L.Multi-edge type LDPC codes[EB/OL].[2010-09-25].http://lthcwww.epfl.ch/papers/multiedge.ps.
[2]YOU Ying,XIAO Min,WANG Lin.The rate-compatible multi-edge type LDPC codes with short block length[C]//Proc.IEEE WICOM.[S.l.]:IEEE Press,2009:770-773.
[3]BLANKSBY A J,HOWLAND C J.A 690-mW 1-Gb/s 1024-b,rate-1/2 low-density parity-check code decoder[J].IEEE Journal of Solid-State Circuits,2002,37(3):404-412.
[4]SUN Yang,KARKOOTI M,JOSEPH R.VLSI decoder architecture for high throughput,variable block-size and multi-rate LDPC codes[C]//Proc.IEEE International Symposium on Circuits and Systems,2007.[S.l.]:IEEE Press,2007:2104-2107.
[5]YANG Lei,SHEN Manyuan,LIU Hui,et al.An FPGA implementation of low-density parity-check code decoder with multi-rate capability[EB/OL].[2010-09-25].http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=1466451.
[6]HA J,KIM J,KLINC D,et al.Rate-compatible punctured low-density parity-check codes with short block lengths[J].IEEE Trans.Inf.Theory,2006,52(2):728-738.
[7]YANG M,RYAN W E,LI Y.Design of efficiently encodable moderatelength high-rate irregular LDPC codes[J].IEEE Trans.Commun.,2004,52(4):564-571.
[8]SELVARATHINAM A,CHOI G,NARAYANAN K,et al.A massively scaleable decoder architecture for low-density parity-check codes[C]//Proc.the 2003 International Symposium on Circuits and Systems.[S.l.]:IEEE Press,2003,2:25-28.
[9]YEO E,PAKZAD P,NIKOLIC B,et al.High throughput low-density parity-check decoder architectures[C]//Proc.IEEE Global Telecommunications Conference.[S.l.]:IEEE Press,2001,5:3019-3024.