多元LDPC碼列分層DBC譯碼算法

陳紫強(qiáng)，邢 茜，謝躍雷，晉良念，劉慶華

(桂林電子科技大學(xué)無線寬帶通信與信號(hào)處理省部重點(diǎn)實(shí)驗(yàn)室，廣西桂林541004)

多元LDPC與二元LDPC碼相比具有更優(yōu)異的差錯(cuò)控制性能和更強(qiáng)的抗突發(fā)錯(cuò)誤能力，而實(shí)現(xiàn)復(fù)雜度高和收斂速度慢是制約多元LDPC碼發(fā)展的主要原因。1998年，Davey和MacKay首次提出了基于GF(q)的多元LDPC碼［1］，并給出了多元LDPC碼和積譯碼算法(Q-ary SPA)，但其運(yùn)算復(fù)雜度高達(dá)O(q2)。在2007年，Declercq和Fossorier提出了一種擴(kuò)展最小和(Extended Min Sum，EMS)譯碼算法［2］，將迭代消息長度由q截短為nm(nm?q)，極大地降低了譯碼算法復(fù)雜度。結(jié)合工程實(shí)現(xiàn)條件，國內(nèi)學(xué)者提出了很多改進(jìn)的EMS譯碼算法［3-10］，如動(dòng)態(tài)擴(kuò)展最小和(dynamic extended min-sum)算法［4］、基于 GF(q)域的 LDPC 碼隨機(jī)解碼算法［5］、多元簡化最小和算法(simplified min-sum algorithm)［6］、多元 LDPC 碼最小最大譯碼(Min-Max Decoding)算法［7］等，以上算法或是從硬件實(shí)現(xiàn)角度，或是從占用內(nèi)存角度，對(duì)EMS算法進(jìn)行了優(yōu)化。另一方面，因?yàn)镋MS算法校驗(yàn)節(jié)點(diǎn)更新步驟中存在大量的實(shí)數(shù)運(yùn)算，其總體運(yùn)算復(fù)雜度實(shí)際上為O(n2m)，Boutillon等針對(duì)EMS算法中實(shí)數(shù)比較運(yùn)算提出了檢泡(Bubble Check，BC)算法［11-12］，將多元 LDPC 碼譯碼復(fù)雜度降低為O(nm)。林偉等基于BC算法提出了動(dòng)態(tài)檢泡算法(Dynamic Bubble-Check，DBC)算法［13］，通過新增標(biāo)志矢量有效地降低了BC算法中的實(shí)數(shù)運(yùn)算。然而，DBC算法采用洪泛(Flooding)處理方式更新節(jié)點(diǎn)消息，存在譯碼收斂速度較慢的問題。

為了提高譯碼收斂速度，文獻(xiàn)［14］針對(duì)準(zhǔn)循環(huán)LDPC碼，提出了一種并行分層置信度傳播譯碼算法，該算法在不增加譯碼復(fù)雜度的前提下，將分層的節(jié)點(diǎn)更新機(jī)制擴(kuò)展至準(zhǔn)循環(huán)LDPC碼，實(shí)現(xiàn)了在提高系統(tǒng)誤碼性能的同時(shí)降低平均迭代次數(shù)。文獻(xiàn)［15-16］結(jié)合VLSI結(jié)構(gòu)，從實(shí)現(xiàn)角度進(jìn)一步簡化了分層譯碼算法。文獻(xiàn)［17］提出了一種基于網(wǎng)格分層譯碼高吞吐量多元Max-Log-QSPA算法，該算法中在給定誤碼性能的條件下采用分層譯碼來減少譯碼迭代次數(shù)。文獻(xiàn)［18］研究了多元LDPC碼準(zhǔn)循環(huán)列分層譯碼，提出根據(jù)準(zhǔn)循環(huán)校驗(yàn)矩陣中縱向特點(diǎn)對(duì)其進(jìn)行分層譯碼的方案。由此可見在譯碼算法中采用分層結(jié)構(gòu)可以有效加快譯碼收斂速度、減少譯碼迭代次數(shù)。

為了降低多元LDPC碼EMS算法的譯碼復(fù)雜度，同時(shí)提高譯碼收斂速度，本文提出一種基于列分層的DBC譯碼方法。首先對(duì)多元LDPC碼變量節(jié)點(diǎn)按照列重從大到小(置信度由高到低)順序依次排序分層。譯碼時(shí)先對(duì)列重較大分層的變量節(jié)點(diǎn)消息進(jìn)行更新，并將消息通過校驗(yàn)節(jié)點(diǎn)傳遞給列重較小的分層，通過串并結(jié)合的分層譯碼方式加快譯碼迭代次數(shù)。為了降低譯碼復(fù)雜度，在校驗(yàn)節(jié)點(diǎn)更新過程中，采用DBC算法降低EMS算法中校驗(yàn)節(jié)點(diǎn)消息的運(yùn)算量。仿真結(jié)果表明，誤碼率相同的條件下，本文所提出方法的平均最大迭代次數(shù)僅為EMS譯碼算法的50%，譯碼復(fù)雜度降低為EMS算法的50%。

1 多元LDPC碼EMS譯碼算法

有限域的多元LDPC碼性能要優(yōu)于二元LDPC碼，但這是以更大的譯碼復(fù)雜度換取的。通過分析發(fā)現(xiàn)，多元LDPC碼的譯碼復(fù)雜度主要集中在校驗(yàn)節(jié)點(diǎn)更新的計(jì)算，擴(kuò)展最小和(EMS)算法［2］能夠降低校驗(yàn)節(jié)點(diǎn)更新的計(jì)算復(fù)雜度。在EMS算法中，迭代消息對(duì)數(shù)似然值比(LLR)長度由q項(xiàng)截短為nm項(xiàng)，因此在算法中傳遞的消息向量不僅包含截短后的對(duì)數(shù)似然值，還需要包含似然值對(duì)應(yīng)的域元素。多元EMS算法的譯碼步驟與傳統(tǒng)的多元LDPC碼譯碼算法步驟相同，不同之處主要在于校驗(yàn)節(jié)點(diǎn)和變量節(jié)點(diǎn)更新的基本運(yùn)算。下面簡要介紹EMS算法的主要步驟。

譯碼過程中H表示校驗(yàn)矩陣，vm，n表示由校驗(yàn)節(jié)點(diǎn)m傳遞到變量節(jié)點(diǎn)n的LLR矢量，um，n表示由變量節(jié)點(diǎn)n傳遞到校驗(yàn)節(jié)點(diǎn)m的LLR矢量，M(n)表示連接到變量節(jié)點(diǎn)n的校驗(yàn)節(jié)點(diǎn)的集合，N(m)表示連接到校驗(yàn)節(jié)點(diǎn)m的變量節(jié)點(diǎn)的集合。hi，j是校驗(yàn)矩陣 H中的第 i行第 j列的元素取值。是滿足限制條件的域元素的集合。算法的初始化消息計(jì)算如下

式中:γn［a］表示迭代消息取值為a時(shí)的對(duì)數(shù)似然比。

1．1 EMS譯碼算法校驗(yàn)節(jié)點(diǎn)更新

EMS譯碼算法校驗(yàn)節(jié)點(diǎn)更新的公式如下

文獻(xiàn)［2］證明了EMS校驗(yàn)節(jié)點(diǎn)更新的可以分解為兩兩節(jié)點(diǎn)的單步運(yùn)算，這里只簡要介紹單步運(yùn)算處理過程，不再進(jìn)行分析證明。記校驗(yàn)節(jié)點(diǎn)基本步驟的輸入消息向量為A和I，輸出消息向量為Y，相應(yīng)的符號(hào)索引向量分別為Aq，Iq和Yq。定義集合 τ={T［k］，k∈［0，q-1］}，其中

式中:Tq［k］為T［k］對(duì)應(yīng)的 GF(q)索引符號(hào)，則輸出消息向量Y由τ中最大nm項(xiàng)按降序排列得到。單步運(yùn)算后，向量Y和Yq需要滿足的條件是

1．2 EMS譯碼算法變量節(jié)點(diǎn)更新

EMS譯碼算法的變量節(jié)點(diǎn)更新的公式如下

與校驗(yàn)節(jié)點(diǎn)更新過程相似，每一個(gè)變量節(jié)點(diǎn)的更新都涉及多個(gè)消息向量之間的互運(yùn)算，變量節(jié)點(diǎn)的更新也可分解成兩兩節(jié)點(diǎn)之間的單步運(yùn)算。設(shè)向量I和A為單步運(yùn)算的兩個(gè)輸入消息向量，輸出向量Y的長度為2nm，它們相對(duì)應(yīng)的域元素索引向量分別為Iq，Aq和Yq。變量節(jié)點(diǎn)更新中的單步運(yùn)算分為3個(gè)步驟完成:

1)遍歷向量 I和 Iq，得到 Y［k］=I［k］+X，其中

2)遍歷向量 A 和 Aq，若 Aq［l］?Iq，則計(jì)算 Y［nm+i］=A［i］+I［nm-1］，否則不做操作;

3)向量Y按照降序排列，將其中較大的nm項(xiàng)元素及其對(duì)應(yīng)的域元素作為單步運(yùn)算的結(jié)果。

2 多元LDPC碼列分層DBC譯碼算法

EMS算法校驗(yàn)節(jié)點(diǎn)更新步驟中存在大量的實(shí)數(shù)運(yùn)算，其總體運(yùn)算復(fù)雜度為O()。為了降低譯碼復(fù)雜度，在校驗(yàn)節(jié)點(diǎn)更新的單步運(yùn)算時(shí)采用動(dòng)態(tài)檢泡(Dynamic Bubble-Check，DBC)算法［13］進(jìn)行簡化。該方法首先對(duì)節(jié)點(diǎn)消息進(jìn)行降序排列，校驗(yàn)節(jié)點(diǎn)更新過程中僅對(duì)待比較的校驗(yàn)節(jié)點(diǎn)對(duì)數(shù)似然比向量(LLR)中當(dāng)前最大項(xiàng)進(jìn)行比較選取，避免EMS算法中校驗(yàn)節(jié)點(diǎn)之間的冗余比較。

為方便說明，引入虛擬方陣T={T［i，j］}，矩陣中的元素為 T［i，j］=A［i］+I［j］，0≤i，j≤nm-1，A，I向量即校驗(yàn)節(jié)點(diǎn)單步運(yùn)算過程中的輸入值。這個(gè)虛擬方陣中包含n2m項(xiàng)元素，單步運(yùn)算就是從虛擬方陣T中尋找滿足條件的值，記最終結(jié)果為Y，Yq。引入長度為nm的排序器S，因?yàn)槊看伪容^排序后得到的值不一定符合條件，所以要設(shè)定一個(gè)最大比較運(yùn)算次數(shù)nop。引入2個(gè)長為nm+1的標(biāo)志向量，若矩陣T中第i行包含一個(gè)比較項(xiàng)(比較泡)，則若矩陣T中第j列包含一個(gè)比較泡，則為了防止運(yùn)算中比較泡溢出T的行尾或列尾，規(guī)定。DBC算法的具體流程如下:

1)初始化

2)取值步驟

通過比較計(jì)算出S中最大值T［i，j］并將其從S中取出。若 Tq［i，j］未曾引入 Yq中，則將 T［i，j］讀入 Y;

4)判決:若k＜nop，置k=k+1，返回步驟2)，否則結(jié)束本次運(yùn)算。

圖1是DBC算法中第4步運(yùn)算的4種典型情況示意圖，其中黑色泡(項(xiàng))表示已經(jīng)比較過的項(xiàng)，白色泡(項(xiàng))表示已經(jīng)在比較器S中的值，虛線泡表示將要引入比較器S的值。如圖可見，DBC算法每一步運(yùn)算僅對(duì)當(dāng)前取最大值的比較泡(項(xiàng))進(jìn)行比較選取。

采用動(dòng)態(tài)檢泡算法(DBC)可以降低校驗(yàn)節(jié)點(diǎn)的運(yùn)算復(fù)雜度，然而該算法過低的收斂速度仍然沒有得到改善，本文將列分層譯碼算法引入到多元LDPC碼動(dòng)態(tài)檢泡算法中，采用串并結(jié)合的分層迭代譯碼方式加快多元LDPC碼收斂速度。校驗(yàn)矩陣H中列重越大該列所對(duì)應(yīng)的碼字的置信度越高，若每次迭代更新中，最先更新置信度較高的節(jié)點(diǎn)，則后續(xù)分層進(jìn)行更新時(shí)便可以得到置信度高的后驗(yàn)信息，進(jìn)而加快整體算法的收斂速度。利用校驗(yàn)矩陣的這一特點(diǎn)，將變量節(jié)點(diǎn)按照列重從大到小(置信度由高到低)順序分層。分層過程如下:1)統(tǒng)計(jì)校驗(yàn)矩陣H的不同列重個(gè)數(shù)，假設(shè)有W種不同列重;2)根據(jù)列重不同將H分為W層;3)對(duì)這W層按照列重不同進(jìn)行降序排列。

圖1 DBC算法第4步運(yùn)算的4種典型情況

校驗(yàn)矩陣H按照列重分層完畢后進(jìn)行迭代譯碼，譯碼過程中每一次迭代被分為W塊(層)進(jìn)行，按照列重由大到小逐層進(jìn)行譯碼，具體流程如下:

1)初始化

由于典型的太行山地質(zhì)構(gòu)造，受儲(chǔ)水層含水量的限制，和順縣境內(nèi)泉水出漏量較小，聯(lián)村集中供水工程不易采用泉水作為供水水源，而單村供水水源采用較多。主要優(yōu)點(diǎn)：（1）當(dāng)?shù)氐乃Y源達(dá)到充分利用，有效控制了地下水的開采量，使所屬區(qū)域的地下水得到充分涵養(yǎng)。（2）山泉水水質(zhì)優(yōu)良是很好的飲用水水源。（3）水源建設(shè)形式簡單，投資費(fèi)用較小，多數(shù)山泉水所處地形較高屬于高地泉，水借重力流向高位水塔，后期運(yùn)行費(fèi)用低。

(1)根據(jù)接收到信道消息計(jì)算n維LLR向量，對(duì)向量矩陣逐列進(jìn)行降序排序，記為L，Lq(Lq為索引值)。

(2)對(duì)L矩陣每一列整體減去各列最大值，結(jié)果記為L1。

(3)取L1中各列前nm(nm?q)項(xiàng)元素作為初值消息向量，記為γn;取Lq中各列前nm項(xiàng)作為初始索引值向量，記為γq;將γn和γq賦值給變量節(jié)點(diǎn)矩陣V及其索引值矩陣Vq。

2)列分層迭代譯碼

(1)置換步驟

式中:vq表示變量節(jié)點(diǎn)置換之前索引值向量，vzq表示變量節(jié)點(diǎn)置換之后的索引值向量。其中 a=hm，n［×］b，0≤hm，n，a，b≤q-1。符號(hào)“［×］”表示 GF(q)域上的乘法。

(2)進(jìn)行第r層(1≤r≤W)，第l次迭代校驗(yàn)節(jié)點(diǎn)更新

(3)逆置換步驟

式中:a=b［÷］hm，n，0≤hm，n，a，b≤q-1。符號(hào)“［÷ ］”表示GF(q)域上除法。

(4)進(jìn)行第r層，第l次迭代變量節(jié)點(diǎn)更新

當(dāng)完成所有的W層迭代后進(jìn)行譯碼判決。

3)譯碼判決

3 實(shí)驗(yàn)仿真結(jié)果

為了驗(yàn)證多元LDPC碼列分層DBC譯碼算法的收斂性和復(fù)雜度，對(duì)該算法和標(biāo)準(zhǔn)EMS［2］進(jìn)行相同條件下的軟件仿真。信道條件為高斯白噪聲(AWGN)信道，采用GF(16)域上碼率為0.5，碼長為1 056的多元LDPC碼，校驗(yàn)矩陣H按照列重分為3層，第一層列重為6，第二層列重為3，第三層列重為2。采用16QAM調(diào)制方式，設(shè)置仿真最小幀數(shù)為1 000幀，最小錯(cuò)誤幀數(shù)為20幀。在信噪比為5 dB和5.2 dB條件下，最大迭代次數(shù)不同時(shí)，分別對(duì)多元LDPC碼列分層DBC譯碼算法和標(biāo)準(zhǔn)EMS進(jìn)行仿真。仿真結(jié)果如圖2、圖3所示。

圖2 信噪比為5 dB時(shí)不同迭代次數(shù)下誤碼率比較

圖3 信噪比為5.2 dB時(shí)不同迭代次數(shù)下誤碼率比較

由圖2、圖3中可以看出，在相同誤碼率的條件下，列分層DBC譯碼算法進(jìn)行譯碼時(shí)所需要的最大迭代次數(shù)大致是EMS譯碼算法的一半。當(dāng)誤碼率為10-5時(shí)，列分層DBC譯碼算法所需要的迭代次數(shù)分別為5次，EMS譯碼算法所需要的最大迭代次數(shù)為10次。

從圖4、圖5中可以看出，在相同信噪比下，列分層DBC算法與EMS算法的性能幾乎沒有差別，而前者的迭代次數(shù)僅是后者的一半。由此可以得出，列分層DBC算法在幾乎不損失性能的前提下，可以將譯碼所需迭代次數(shù)降低到后者的50%。

圖4 EMS算法與分層DBC算法的誤碼率比較

圖5 EMS算法與分層DBC算法的誤幀率比較

這是由于列分層DBC算法中一次迭代譯碼被分為W層，并按照列重由大到小依次進(jìn)行分層譯碼。在每一層中完成局部校驗(yàn)節(jié)點(diǎn)與變量節(jié)點(diǎn)的交替更新。每次迭代更新中優(yōu)先處理列重較大(置信度較高)所對(duì)應(yīng)的節(jié)點(diǎn)，使得下一層(置信度較低)節(jié)點(diǎn)譯碼時(shí)可以及時(shí)獲得上一層(置信度高)節(jié)點(diǎn)更新后的最新消息，這樣就會(huì)加快迭代譯碼算法收斂速度。下面比較兩種算法的運(yùn)算量進(jìn)行分析。

標(biāo)準(zhǔn)EMS算法［2］校驗(yàn)節(jié)點(diǎn)基本步驟的運(yùn)算復(fù)雜度為。列分層DBC譯碼算法第k次比較中，考慮最壞情況下，比較器S中待比較泡的個(gè)數(shù)為nk，要滿足的條件為1+2+…+(nk-1)=k-1，解出 nk取其正整數(shù)解 nk=表示取整運(yùn)算。對(duì)于包含nop步運(yùn)算的DBC算法，設(shè)Navg為每步運(yùn)算時(shí)比較器S中比較泡的平均數(shù)目，則有

通常nop的取值與nm同數(shù)量級(jí)，上式進(jìn)一步近似為Navg≈該算法每個(gè)節(jié)點(diǎn)需要Navgnop次實(shí)數(shù)運(yùn)算(包括實(shí)數(shù)加法和實(shí)數(shù)比較)，即算法整體最終復(fù)雜度為。標(biāo)準(zhǔn)EMS譯碼算法中校驗(yàn)節(jié)點(diǎn)基本步驟的每一步比較均有nm項(xiàng)比較泡，而列分層DBC譯碼算法中每一步的平均比較泡數(shù)，因此列分層DBC譯碼算法的運(yùn)算復(fù)雜度為標(biāo)準(zhǔn)EMS算法的

4 小結(jié)

本文提出多元LDPC碼列分層DBC譯碼算法，該算法充分結(jié)合了DBC算法低復(fù)雜度和列分層譯碼算法快速收斂的優(yōu)勢(shì)，在提高多元LDPC碼譯碼算法收斂速度的同時(shí)降低了算法運(yùn)算復(fù)雜度。仿真結(jié)果表明，多元列分層DBC譯碼算法與多元EMS算法相比，在幾乎沒有性能損失的前提下，加快了譯碼的收斂速度，在誤碼率為10-5時(shí)，列分層DBC譯碼算法所需最大迭代次數(shù)僅為EMS算法50%。列分層DBC譯碼算法采用動(dòng)態(tài)檢泡法大幅降低了校驗(yàn)節(jié)點(diǎn)消息更新的運(yùn)算量，將算法復(fù)雜度降低為EMS算法的50%。

［1］ DAVEY M C，MACKAY D.Low-density parity check codesover GF(q)［J］.Communications Letters，1998，2(6):165-167.

［2］ DECLERCQ D，F(xiàn)OSSORIER M.Decoding algorithms for nonbinary LDPC codes over GF ［J］.IEEE Transactions on Communications，2007，55(4):633-643.

［3］ VOICILA A，DECLERCQ D，VERDIER F，et al.Low-complexity，low-memory EMS algorithm for non-binary LDPC codes［J］.IEEE Trans.Communications，2010，58(5):1365-1375.

［4］林偉，白寶明，王雪鵬.多元LDPC碼的動(dòng)態(tài)擴(kuò)展最小和譯碼算法［J］.西安電子科技大學(xué)學(xué)報(bào)，2012，39(2):59-65.

［5］ SARKIS G，HEMATI S，MANNOR S，et al.Stochastic decoding of LDPC codes over GF(q)［J］.IEEE Trans.Communications，2013，61(3):939-950.

［6］ WANG C L，CHEN X，LI Z，et al.A simplified min-sum decoding algorithm for non-binary LDPC codes［J］.IEEE Trans.Communications，2013，61(1):24-32.

［7］ YANG L，LIU F，LI H.Min – max decoding for non-binary LDPC codes［C］//Proc.the 2012 International Conference on Information Technology and Software Engineering，2013. ［S.l.］:IEEE Press，2003:960-964.

［8］ LACRUZ J O，GARCIA-HERRERO F，VALLS J，et al.One minimum only trellis decoder for non-binary low-density parity-check codes［J］.IEEE Trans.Circuits and Systems I:Regular Papers，2015，62(1):177-184.

［9］ CONDE-CANENCIA L，BOUTILLON E.Application of bubblecheck algorithm to non-binary LLR computation in QAM coded schemes［J］.Electronics Letters，2014，50(25):1937-1938.

［10］ KOBI M E，ZEIN M，GHOUWAYEL A C，et al.Decoding of short non-binary LDPC codes using a non iterative decoding algorithm［C］//Proc.2014 Third International Conference on the e-Technologies and Networks for Development(ICEND).［S.l.］:IEEE Press，2014:620-625.

［11］ BOUTILLON E，CONDE-CANENCIA.Simplified check node processing in nonbinary LDPC decoders［C］//Proc.2010 6th International Symposium on Turbo Codes and Iterative Information Processing.Brest，F(xiàn)rance:IEEE Press，2010:201-205.

［12］ BOUTILLON E，CONDE-CANENCIA L.Bubble check:a simplified algorithm for elementary check node processing in extended min-sum non-binary LDPC decoders［J］.Electronics Letters，2010，46(9):633-634.

［13］ WEI L，BAOMING B，XIAOM，et al.Dynamic bubble-check algorithm for check node processing in Q-Ary LDPC decoders［J］.IEICE Trans.Communications，2012，95(5):1815-1818.

［14］ ZHOU S，SHA J，LI L，et al.Layered decoding for non-binary LDPC codes［EB/OL］.［2014-12-23］.http://www.researchgate.net/publication/221375599_Layered_decoding_for_non-binary_LDPC_codes.

［15］ ZHANG X，CAI F.Reduced-complexity decoder architecture for non-binary LDPC codes［J］.IEEE Trans.Very Large Scale Integration(VLSI)Systems，2011，19(7):1229-1238.

［16］ CUIZ，WANG Z，ZHANGX.Reduced-complexity column-layered decoding and implementation for LDPC codes［J］.Communications IET，2011，5(15):2177-2186.

［17］ UENG Y L，LIAO K H，CHOU H C，et al.A high-throughput trellis-based layered decoding architecture for non-binary LDPC codes using Max-Log-QSPA［J］.IEEE Trans.Signal Processing，2013，61(11):2940-2951.

［18］ ZHANG Chuan，YOU Xiaohu，WANG Zhongfeng. Efficient column-layered decoders for single block-row quasi-cyclic LDPC codes［C］//Proc.2014 IEEE International Symposium on the Circuits and Systems.［S.l.］:Melhourne VIC，2014:413-416.