面向新一代数字通信系统的LDPC码的译码算法研究

李彦婷，司璐

(1.工业和信息化部电信研究院规划设计研究所，北京 100037；2.中国传媒大学广播电视数字化教育部工程研究中心，北京 100024)

面向新一代数字通信系统的LDPC码的译码算法研究

李彦婷1，司璐2

(1.工业和信息化部电信研究院规划设计研究所，北京 100037；2.中国传媒大学广播电视数字化教育部工程研究中心，北京 100024)

低密度奇偶校验(Low Density Parity Check，LDPC)码是第四代移动通信的关键技术之一，DMB-TH/T-MMB标准都将其列入信道编码方案。本文对LDPC码几种译码算法做了深入研究，并在仿真各种算法的基础上，比较其优缺点。

LDPC码；译码器；BP算法；T-MMB

1 概述

低密度奇偶校验码(Low Density Parity Code，LDPC)是一种具有稀疏校验矩阵的线性分组码，其奇偶校验矩阵中只有极少数目的非0元素(对于二进制码，非0元素即为1)，其他元素都为0，最早由文献[1]提出。LDPC码采用迭代译码算法，具有能够逼近Shannon限的性能特性，并被证明与Turbo码的性能相当甚至更优；同时由于校验矩阵的稀疏性，其译码难度大大小于后者。译码算法本质上是并行算法，利于实现高速译码，符合手机电视要求高速实时的要求。我国的数字电视地面广播标准DMB-TH[2]、地面移动多媒体广播系统T-MMB[3]均采用LDPC码作为信道编码。

LDPC码具有良好性能的重要原因之一是：它采用了基于置信传播BP(Belief Propogation)的迭代译码算法，这是一种迭代概率译码方法，是LDPC码与传统纠错码的重要区别所在。基于软信息迭代的算法都是以置信传播算法为基础的，并通过对算法某些部分的改进达到降低复杂度或提高性能的目的。

DMB-TH、T-MMB中提出的LDPC码都是QC-LDPC码，具有线性分组的、系统的、准循环的特性。

2 QC-LDPC码

QC-LDPC码[4]是近年来研究得最多的一类LDPC码。以T-MMB系统中的LDPC码为例[3]，其校验矩阵H表示为如下形式

(1)

其中Hi，j是一个行重量为ωi，j的t×t循环矩阵，该矩阵的每行皆由其上一行循环右移一位得到，其中第一行由最后一行循环右移一位得到。Hi=[Hi，0，Hi，1…，Hi，c-1](i=0，1，…，ρ-1)的第一行称为H的第i+1个行生成器，则H共有ρ个行生成器，详见[3]。矩阵H表征的分组码称为(NL，KL)准循环LDPC码，其中NL=c×t为码长，KL=(c-ρ)×t为编码信息比特的长度。

表1 T-MMB中LDPC编码参数

3 LLR BP算法

根据消息的表示形式，BP译码可以分为概率BP算法和LLR BP算法。概率BP算法的消息是用概率形式表示，是BP算法的通用形式。消息也可表示为对数似然比形式，相应的译码算法称为LLR BP算法。概率BP算法采用较多相乘运算，需耗费较多运算时间和硬件资源，不利于硬件实现。采用对数似然比后，BP算法会有一个非常简洁的表达形式。

3.1 LLR BP算法基本步骤

首先进行参数设置：

Fn：比特节点n对应的LLR通过接收符号值得到，初始化为(4/N0)y0。

Lmn：由校验节点m传递给比特节点n的LLR。

zmn：由比特节点n传递给校验节点m的LLR。

zn：比特节点n的后验LLR信息，包含来自所有相关校验节点的信息，用于每个循环后对整个码字进行硬判决，判断是否得到一个有效码字，从而决定是否应该中断译码迭代过程。

初始化：设置(4/N0)y0。

迭代过程：每次迭代都按照如下步骤进行。

① 水平步骤(校验节点消息处理)

对于每一组m和n，

(2)

(3)

② 垂直步骤(变量节点消息处理)

对于每一组m和n，更新zmn

(4)

对于每一个n，更新zn

(5)

③译码判决

3.2 LLR BP算法仿真性能分析

以T-MMB标准中的LDPC码为例，在AWGN信道上，采用BPSK调制，分别用Matlab和C语言进行LLR BP算法仿真，结果如图1所示。

图1 LLR BP算法性能

4 UMP BP-Based算法

标准BP算法中，校验节点的处理相对复杂，进一步降低校验节点处理的复杂度，可得UMP BP-Based算法[5]。

4.1 UMP BP-Based算法基本步骤

初始化：设置(4/N0)y0。

迭代：① 水平步骤(校验节点消息处理)：

(6)

②，③步骤与LLR BP算法相同，与LLR BP算法相比，它的优点在于校验节点的处理只有求最小值运算，而不需要相乘运算，大大降低了运算量。

4.2 UMP BP-Based算法仿真性能分析

图2 UMP BP-Based算法和LLR BP算法的性能比较

依然以T-MMB标准中的LDPC码为例，在AWGN信道、BPSK调制环境下，比较以上2种译码算法的性能，由仿真结果可以看出，采用简化算法，在复杂度降低的同时，抗干扰能力较标准BP算法会有所降低，在BER=10-4时比BP算法有约0.5dB的损失。

UMP BP-Based算法的译码过程中只有加法和比较运算，特别适合硬件实现。但同时，其译码性能有所降低。一般情况下，给定码长的码字，行重与列重越大，性能降低越严重；给定行重和列重，码长越长，性能降低越严重。

5 Normalized BP-Based算法和Offset BP-Based算法

5.1 UMP-BP与BP算法校验节点处理的比较

将BP算法中校验节点消息的更新表示为符号和幅度相乘的形式，符号用来进行译码判决，而判决的置信度或可靠性由幅度表示。在幅度的计算中只取对结果影响最大的最小值，得到了BP-Based算法。下面比较两种算法中校验节点输出消息的不同，用L1、L2可以得到以下两个结论[6]：

①L1、L2具有相同的符号，即sgn(L1)=sgn(L2)

(7)

②L2的幅度大于L1的幅度，即|L2|>|L1|

(8)

因此，两种算法相比，在输入到校验节点的消息相同的情况下，输出消息的符号是相同的，但是幅度不同，进而可靠性不同。BP-Based算法与BP算法相比高估计了输出校验消息的幅度，如果能采取措施降低消息的幅度，则可以更接近BP算法，提高译码性能。

5.2 Normalized BP-Based算法和Offset BP-Based算法

根据以上结论，要降低L2的幅度，可以将其除以一个尺度因子，即校验消息表示为

(9)

其中α>1称为校正因子。此时改进算法称为Normalized BP-Based算法。

或者将原来的校验消息减去一个数值来降低，即

Lmn←sgn(Lmn)·max(|Lmn|-β，0)

(10)

其中β称为偏移因子。此时改进算法称为Offset BP-Based算法。将所有小于β的校验消息设为0，它们对变量节点消息的计算没有影响。

两种算法的性能与α、β的取值直接相关，α、β取值不合适，性能会很差。可以用密度进化法来计算其值，本次设计采用一种简单的方法计算α的值[6]。直观地，可以通过计算的均值来求校正因子α，即

(11)

由于第一次迭代时校验节点输出的消息不仅影响第二次迭代的准确性，而且对整个译码过程的错误概率有很大影响。因此，计算α时要利用第一次迭代时校验节点输出的消息。为简化运算，在所有迭代过程中采用同一α值；但如果根据迭代次数和SNR改变α的值，可以进一步提高性能。与校正因子类似，也可采用统计平均的方法来粗略计算偏移因子的数值。

将Normalized BP-Based算法中的校正因子α分别取1.10到1.40进行了仿真，α的取值与译码BER的关系如下左图所示。可见α在1.35附近，可以达到最佳性能。类似地，将Offset BP-Based算法中偏移因子分别取0.35到0.55进行了仿真，β的取值与译码BER的关系如下右图所示。可见β在0.45附近，可以达到最佳性能。

图3 两种算法中的校正因子α、偏移因子β对BER性能的影响

5.3 Normalized BP-Based算法和Offset BP-Based算法仿真性能分析

图4是分别采用BP、BP-Based、α=1.35的Normalized BP-Based算法和β=0.45的Offset BP-Based算法进行LDPC译码时的性能比较。

图4 各种译码算法的性能比较

由图可以看出，只要选定合适的译码参数α和β，Normalized BP-Based算法和Offset BP-Based算法都能在增加很少复杂度的情况下，获得接近BP算法的性能，具有一定的应用价值。

[1]R G Gallager. Low Density Parity-Check Codes[J]. IRE Transaction on .Information.Theory，1962，8(1)： 21-28.

[2]GB 20600-2006，中国数字电视地面广播标准[S].

[3]手机电视/移动多媒体 广播传输系统帧结构、信道编码、调制及复用[S]. 征求意见稿V4.0.

[4]M Fossorier. Quasicyclic Low Density Parity Check Codes[J]. Information Theory，2003，9(15)，150.

[5]M Fossorier，M Mihaljevic，H Imai. Reduced Complexity Iterative Decoding of Low Density Parity-Check Codes Based on Belief Paopagation[J]. IEEE Transactions on Communications，1999，47： 673-680.

[6]Jinghu Chen，M Fossorier. Near Optimun Universal Belief Propagation Based Decoding of Low Density Parity Check Codes[J]. IEEE Transactions on Communications，2002，50(3)，406-414.

ResearchofLDPCDecodingAlgorithmsforNew-generationDigitalCommunicationSystem

LI Yan-ting1，SI Lu2

(1.Institute of Planning and Designing Research，China Academy of Telecommunication Research of MIIT，Beijing 100037，China
2.ECDAV，Communication University of China，Beijing 100024，China)

LDPC(Low Density Parity Check) codes is one of the key technologies of the fourth-generation mobile communication. Both DMB-TH and T-MMB have LDPC codes included in channel coding program. Several LDPC decoding algorithms have been studied in depth in the paper，and their merits and drawbacks have been compared based on the simulation results.

LDPC codes; decoder; BP algorithm; T-MMB

2010-03-23

李彦婷(1986-)，女(汉族)，云南昭通人，中国传媒大学08级硕士研究生. E-mail： ytl.xdt@gmail.com

TN911.22

A

1673-4793(2013)01-0068-04

(责任编辑：宋金宝)