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

陳紫強，邢 茜，謝躍雷，晉良念，劉慶華

(桂林電子科技大學無線寬帶通信與信號處理省部重點實驗室，廣西桂林541004)

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

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

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

1 多元LDPC碼EMS譯碼算法

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

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

式中:γn［a］表示迭代消息取值為a時的對數似然比。

1．1 EMS譯碼算法校驗節點更新

EMS譯碼算法校驗節點更新的公式如下

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

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

1．2 EMS譯碼算法變量節點更新

EMS譯碼算法的變量節點更新的公式如下

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

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

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

3)向量Y按照降序排列，將其中較大的nm項元素及其對應的域元素作為單步運算的結果。

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

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

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

1)初始化

2)取值步驟

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

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

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

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

圖1 DBC算法第4步運算的4種典型情況

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

1)初始化

由于典型的太行山地質構造，受儲水層含水量的限制，和順縣境內泉水出漏量較小，聯村集中供水工程不易采用泉水作為供水水源，而單村供水水源采用較多。主要優點：（1）當地的水資源達到充分利用，有效控制了地下水的開采量，使所屬區域的地下水得到充分涵養。（2）山泉水水質優良是很好的飲用水水源。（3）水源建設形式簡單，投資費用較小，多數山泉水所處地形較高屬于高地泉，水借重力流向高位水塔，后期運行費用低。

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

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

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

2)列分層迭代譯碼

(1)置換步驟

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

(2)進行第r層(1≤r≤W)，第l次迭代校驗節點更新

(3)逆置換步驟

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

(4)進行第r層，第l次迭代變量節點更新

當完成所有的W層迭代后進行譯碼判決。

3)譯碼判決

3 實驗仿真結果

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

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

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

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

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

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

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

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

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

通常nop的取值與nm同數量級，上式進一步近似為Navg≈該算法每個節點需要Navgnop次實數運算(包括實數加法和實數比較)，即算法整體最終復雜度為。標準EMS譯碼算法中校驗節點基本步驟的每一步比較均有nm項比較泡，而列分層DBC譯碼算法中每一步的平均比較泡數，因此列分層DBC譯碼算法的運算復雜度為標準EMS算法的

4 小結

本文提出多元LDPC碼列分層DBC譯碼算法，該算法充分結合了DBC算法低復雜度和列分層譯碼算法快速收斂的優勢，在提高多元LDPC碼譯碼算法收斂速度的同時降低了算法運算復雜度。仿真結果表明，多元列分層DBC譯碼算法與多元EMS算法相比，在幾乎沒有性能損失的前提下，加快了譯碼的收斂速度，在誤碼率為10-5時，列分層DBC譯碼算法所需最大迭代次數僅為EMS算法50%。列分層DBC譯碼算法采用動態檢泡法大幅降低了校驗節點消息更新的運算量，將算法復雜度降低為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，FOSSORIER 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碼的動態擴展最小和譯碼算法［J］.西安電子科技大學學報，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，France: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.