面向新一代數(shù)字通信系統(tǒng)的LDPC碼的譯碼算法研究

李彥婷，司璐

(1.工業(yè)和信息化部電信研究院規(guī)劃設(shè)計(jì)研究所，北京 100037；2.中國(guó)傳媒大學(xué)廣播電視數(shù)字化教育部工程研究中心，北京 100024)

面向新一代數(shù)字通信系統(tǒng)的LDPC碼的譯碼算法研究

李彥婷1，司璐2

(1.工業(yè)和信息化部電信研究院規(guī)劃設(shè)計(jì)研究所，北京 100037；2.中國(guó)傳媒大學(xué)廣播電視數(shù)字化教育部工程研究中心，北京 100024)

低密度奇偶校驗(yàn)(Low Density Parity Check，LDPC)碼是第四代移動(dòng)通信的關(guān)鍵技術(shù)之一，DMB-TH/T-MMB標(biāo)準(zhǔn)都將其列入信道編碼方案。本文對(duì)LDPC碼幾種譯碼算法做了深入研究，并在仿真各種算法的基礎(chǔ)上，比較其優(yōu)缺點(diǎn)。

LDPC碼；譯碼器；BP算法；T-MMB

1 概述

低密度奇偶校驗(yàn)碼(Low Density Parity Code，LDPC)是一種具有稀疏校驗(yàn)矩陣的線性分組碼，其奇偶校驗(yàn)矩陣中只有極少數(shù)目的非0元素(對(duì)于二進(jìn)制碼，非0元素即為1)，其他元素都為0，最早由文獻(xiàn)[1]提出。LDPC碼采用迭代譯碼算法，具有能夠逼近Shannon限的性能特性，并被證明與Turbo碼的性能相當(dāng)甚至更優(yōu)；同時(shí)由于校驗(yàn)矩陣的稀疏性，其譯碼難度大大小于后者。譯碼算法本質(zhì)上是并行算法，利于實(shí)現(xiàn)高速譯碼，符合手機(jī)電視要求高速實(shí)時(shí)的要求。我國(guó)的數(shù)字電視地面廣播標(biāo)準(zhǔn)DMB-TH[2]、地面移動(dòng)多媒體廣播系統(tǒng)T-MMB[3]均采用LDPC碼作為信道編碼。

LDPC碼具有良好性能的重要原因之一是：它采用了基于置信傳播BP(Belief Propogation)的迭代譯碼算法，這是一種迭代概率譯碼方法，是LDPC碼與傳統(tǒng)糾錯(cuò)碼的重要區(qū)別所在。基于軟信息迭代的算法都是以置信傳播算法為基礎(chǔ)的，并通過(guò)對(duì)算法某些部分的改進(jìn)達(dá)到降低復(fù)雜度或提高性能的目的。

DMB-TH、T-MMB中提出的LDPC碼都是QC-LDPC碼，具有線性分組的、系統(tǒng)的、準(zhǔn)循環(huán)的特性。

2 QC-LDPC碼

QC-LDPC碼[4]是近年來(lái)研究得最多的一類(lèi)LDPC碼。以T-MMB系統(tǒng)中的LDPC碼為例[3]，其校驗(yàn)矩陣H表示為如下形式

(1)

其中Hi，j是一個(gè)行重量為ωi，j的t×t循環(huán)矩陣，該矩陣的每行皆由其上一行循環(huán)右移一位得到，其中第一行由最后一行循環(huán)右移一位得到。Hi=[Hi，0，Hi，1…，Hi，c-1](i=0，1，…，ρ-1)的第一行稱(chēng)為H的第i+1個(gè)行生成器，則H共有ρ個(gè)行生成器，詳見(jiàn)[3]。矩陣H表征的分組碼稱(chēng)為(NL，KL)準(zhǔn)循環(huán)LDPC碼，其中NL=c×t為碼長(zhǎng)，KL=(c-ρ)×t為編碼信息比特的長(zhǎng)度。

表1 T-MMB中LDPC編碼參數(shù)

3 LLR BP算法

根據(jù)消息的表示形式，BP譯碼可以分為概率BP算法和LLR BP算法。概率BP算法的消息是用概率形式表示，是BP算法的通用形式。消息也可表示為對(duì)數(shù)似然比形式，相應(yīng)的譯碼算法稱(chēng)為L(zhǎng)LR BP算法。概率BP算法采用較多相乘運(yùn)算，需耗費(fèi)較多運(yùn)算時(shí)間和硬件資源，不利于硬件實(shí)現(xiàn)。采用對(duì)數(shù)似然比后，BP算法會(huì)有一個(gè)非常簡(jiǎn)潔的表達(dá)形式。

3.1 LLR BP算法基本步驟

首先進(jìn)行參數(shù)設(shè)置：

Fn：比特節(jié)點(diǎn)n對(duì)應(yīng)的LLR通過(guò)接收符號(hào)值得到，初始化為(4/N0)y0。

Lmn：由校驗(yàn)節(jié)點(diǎn)m傳遞給比特節(jié)點(diǎn)n的LLR。

zmn：由比特節(jié)點(diǎn)n傳遞給校驗(yàn)節(jié)點(diǎn)m的LLR。

zn：比特節(jié)點(diǎn)n的后驗(yàn)LLR信息，包含來(lái)自所有相關(guān)校驗(yàn)節(jié)點(diǎn)的信息，用于每個(gè)循環(huán)后對(duì)整個(gè)碼字進(jìn)行硬判決，判斷是否得到一個(gè)有效碼字，從而決定是否應(yīng)該中斷譯碼迭代過(guò)程。

初始化：設(shè)置(4/N0)y0。

迭代過(guò)程：每次迭代都按照如下步驟進(jìn)行。

① 水平步驟(校驗(yàn)節(jié)點(diǎn)消息處理)

對(duì)于每一組m和n，

(2)

(3)

② 垂直步驟(變量節(jié)點(diǎn)消息處理)

對(duì)于每一組m和n，更新zmn

(4)

對(duì)于每一個(gè)n，更新zn

(5)

③譯碼判決

3.2 LLR BP算法仿真性能分析

以T-MMB標(biāo)準(zhǔn)中的LDPC碼為例，在AWGN信道上，采用BPSK調(diào)制，分別用Matlab和C語(yǔ)言進(jìn)行LLR BP算法仿真，結(jié)果如圖1所示。

圖1 LLR BP算法性能

4 UMP BP-Based算法

標(biāo)準(zhǔn)BP算法中，校驗(yàn)節(jié)點(diǎn)的處理相對(duì)復(fù)雜，進(jìn)一步降低校驗(yàn)節(jié)點(diǎn)處理的復(fù)雜度，可得UMP BP-Based算法[5]。

4.1 UMP BP-Based算法基本步驟

初始化：設(shè)置(4/N0)y0。

迭代：① 水平步驟(校驗(yàn)節(jié)點(diǎn)消息處理)：

(6)

②，③步驟與LLR BP算法相同，與LLR BP算法相比，它的優(yōu)點(diǎn)在于校驗(yàn)節(jié)點(diǎn)的處理只有求最小值運(yùn)算，而不需要相乘運(yùn)算，大大降低了運(yùn)算量。

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

圖2 UMP BP-Based算法和LLR BP算法的性能比較

依然以T-MMB標(biāo)準(zhǔn)中的LDPC碼為例，在AWGN信道、BPSK調(diào)制環(huán)境下，比較以上2種譯碼算法的性能，由仿真結(jié)果可以看出，采用簡(jiǎn)化算法，在復(fù)雜度降低的同時(shí)，抗干擾能力較標(biāo)準(zhǔn)BP算法會(huì)有所降低，在BER=10-4時(shí)比BP算法有約0.5dB的損失。

UMP BP-Based算法的譯碼過(guò)程中只有加法和比較運(yùn)算，特別適合硬件實(shí)現(xiàn)。但同時(shí)，其譯碼性能有所降低。一般情況下，給定碼長(zhǎng)的碼字，行重與列重越大，性能降低越嚴(yán)重；給定行重和列重，碼長(zhǎng)越長(zhǎng)，性能降低越嚴(yán)重。

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

5.1 UMP-BP與BP算法校驗(yàn)節(jié)點(diǎn)處理的比較

將BP算法中校驗(yàn)節(jié)點(diǎn)消息的更新表示為符號(hào)和幅度相乘的形式，符號(hào)用來(lái)進(jìn)行譯碼判決，而判決的置信度或可靠性由幅度表示。在幅度的計(jì)算中只取對(duì)結(jié)果影響最大的最小值，得到了BP-Based算法。下面比較兩種算法中校驗(yàn)節(jié)點(diǎn)輸出消息的不同，用L1、L2可以得到以下兩個(gè)結(jié)論[6]：

①L1、L2具有相同的符號(hào)，即sgn(L1)=sgn(L2)

(7)

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

(8)

因此，兩種算法相比，在輸入到校驗(yàn)節(jié)點(diǎn)的消息相同的情況下，輸出消息的符號(hào)是相同的，但是幅度不同，進(jìn)而可靠性不同。BP-Based算法與BP算法相比高估計(jì)了輸出校驗(yàn)消息的幅度，如果能采取措施降低消息的幅度，則可以更接近BP算法，提高譯碼性能。

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

根據(jù)以上結(jié)論，要降低L2的幅度，可以將其除以一個(gè)尺度因子，即校驗(yàn)消息表示為

(9)

其中α>1稱(chēng)為校正因子。此時(shí)改進(jìn)算法稱(chēng)為Normalized BP-Based算法。

或者將原來(lái)的校驗(yàn)消息減去一個(gè)數(shù)值來(lái)降低，即

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

(10)

其中β稱(chēng)為偏移因子。此時(shí)改進(jìn)算法稱(chēng)為Offset BP-Based算法。將所有小于β的校驗(yàn)消息設(shè)為0，它們對(duì)變量節(jié)點(diǎn)消息的計(jì)算沒(méi)有影響。

兩種算法的性能與α、β的取值直接相關(guān)，α、β取值不合適，性能會(huì)很差。可以用密度進(jìn)化法來(lái)計(jì)算其值，本次設(shè)計(jì)采用一種簡(jiǎn)單的方法計(jì)算α的值[6]。直觀地，可以通過(guò)計(jì)算的均值來(lái)求校正因子α，即

(11)

由于第一次迭代時(shí)校驗(yàn)節(jié)點(diǎn)輸出的消息不僅影響第二次迭代的準(zhǔn)確性，而且對(duì)整個(gè)譯碼過(guò)程的錯(cuò)誤概率有很大影響。因此，計(jì)算α?xí)r要利用第一次迭代時(shí)校驗(yàn)節(jié)點(diǎn)輸出的消息。為簡(jiǎn)化運(yùn)算，在所有迭代過(guò)程中采用同一α值；但如果根據(jù)迭代次數(shù)和SNR改變?chǔ)恋闹担梢赃M(jìn)一步提高性能。與校正因子類(lèi)似，也可采用統(tǒng)計(jì)平均的方法來(lái)粗略計(jì)算偏移因子的數(shù)值。

將Normalized BP-Based算法中的校正因子α分別取1.10到1.40進(jìn)行了仿真，α的取值與譯碼BER的關(guān)系如下左圖所示。可見(jiàn)α在1.35附近，可以達(dá)到最佳性能。類(lèi)似地，將Offset BP-Based算法中偏移因子分別取0.35到0.55進(jìn)行了仿真，β的取值與譯碼BER的關(guān)系如下右圖所示。可見(jiàn)β在0.45附近，可以達(dá)到最佳性能。

圖3 兩種算法中的校正因子α、偏移因子β對(duì)BER性能的影響

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

圖4是分別采用BP、BP-Based、α=1.35的Normalized BP-Based算法和β=0.45的Offset BP-Based算法進(jìn)行LDPC譯碼時(shí)的性能比較。

圖4 各種譯碼算法的性能比較

由圖可以看出，只要選定合適的譯碼參數(shù)α和β，Normalized BP-Based算法和Offset BP-Based算法都能在增加很少?gòu)?fù)雜度的情況下，獲得接近BP算法的性能，具有一定的應(yīng)用價(jià)值。

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

[2]GB 20600-2006，中國(guó)數(shù)字電視地面廣播標(biāo)準(zhǔn)[S].

[3]手機(jī)電視/移動(dòng)多媒體 廣播傳輸系統(tǒng)幀結(jié)構(gòu)、信道編碼、調(diào)制及復(fù)用[S]. 征求意見(jiàn)稿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-)，女(漢族)，云南昭通人，中國(guó)傳媒大學(xué)08級(jí)碩士研究生. E-mail： ytl.xdt@gmail.com

TN911.22

A

1673-4793(2013)01-0068-04

(責(zé)任編輯：宋金寶)