改進的非規則QC-LDPC譯碼算法和結構

陳發堂,王永航,張翰卿

(重慶郵電大學 通信與信息工程學院,重慶 400065)

0 引 言

低密度奇偶校驗(Low Density Parity Check, LDPC)碼是一種性能優異的線性分組碼[1]，其校驗矩陣有隨機和結構化兩種構造方式。準循環(Quasi-Cyclic, QC)-LDPC通過結構化方式完成編碼[2]，易于硬件實現，并于2016年成為5G 新空口(New Radio, NR) 的一種主要信道編碼方案[3]。

LDPC碼的譯碼算法都以置信傳播(Belief Propagation ,BP)算法為基礎[4-5]。其中最小和(Min-Sum, MS)算法是BP簡化后的譯碼方式，其運算方式簡單，但犧牲了一部分譯碼性能[6]。為彌補MS算法損失的性能，Chen等提出了歸一化最小和(Normalized Min-Sum, NMS)算法[7]，NMS算法可以提供更加接近BP算法的譯碼性能。密度演化最小和(Density Evolution Min-Sum，DE-MS)算法將前5次迭代的歸一化因子整合為一個值，使LDPC誤碼率(Bit-Error Rate, BER)再次降低[8]。QC-LDPC碼分為兩種譯碼結構：分層式和全并行。分層式結構實現復雜度低，譯碼迭代次數少，在現場可編程門陣列(Field Programmable Gate Array, FPGA)譯碼器中應用廣泛[9]。

以往算法使用一個歸一化因子完成譯碼，在一定程度上降低了譯碼性能。因此本文通過分析BP算法信息值隨度數變化的趨勢，并根據因子分布規律對度數分層，提出根據層數求歸一化因子算法，所得因子可提前存儲避免消耗多余計算資源。所提譯碼結構依據基礎矩陣對校驗節點分組，在每組中選擇合適子層完成迭代譯碼，各層節點度數分布不會因層數變化而改變，進而節點處理單元也無需調整。仿真結果和復雜度分析表明，基于度數歸一化最小和(Based-Degree Normalized Min-Sum,BD-NMS)算法譯碼性能和收斂速度優于其余算法；所提譯碼結構需要更少的存儲空間，對于5G 協議這種需改變提升值的情況，利用所提分層方法更易實現。

1 LDPC譯碼算法概述

1.1 譯碼迭代步驟

譯碼迭代信息包括變量節點傳向校驗節點的信息值(V2C)和校驗節點傳向變量節點的信息值(C2V)。譯碼過程中信息值在兩類節點之間迭代傳遞，利用BP傳播理論和校驗方程修正錯誤比特，譯碼共分為4個步驟：(1) 設置初始迭代信息；(2) 利用V2C更新C2V；(3) 利用C2V更新V2C和后驗信息；(4) 譯出碼字并判斷是否達到停止迭代條件。

1.2 MS和NMS算法

MS和NMS算法主要在校驗節點更新處對BP算法進行了改進，兩種算法信息值計算公式分別為

2 BD-NMS算法

2.1 最優歸一化因子分布

圖1 5G NR協議QC-LDPC碼的最優歸一化因子分布

2.2 各層α值計算

定義MS算法中Cmn為C1，BP算法中Cmn為C2，利用密度演化和泰勒公式得到的E(|C1|)和E(|C2|)[10]分別為

求各層歸一化因子的過程分為4步：

(1) 利用E(|C2|)/E(|C1|)求不同度數的歸一化因子αλ，λ為度數；

(2) 確定numλ，numλ為度數為λ的節點個數；

(3) 根據歸一化因子分布對度數分層并求取各層權值向量，第r層向量為

式中：λrζ為r層第ζ個度數的值；hr為r層所分得度數類型總量；

(4) 利用各層權值向量求對應歸一化因子，第r層因子為

文獻[8]中通過概率質量函數得到不同迭代次數下的歸一化因子，類似的方法能夠求出第r層前5次迭代的衰減因子：αr1、αr2、αr3、αr4和αr5，進而利用權值向量X=[0.25,0.25,0.20,0.20,0.10]得到第r層在前Z-5(Z為最大迭代次數)次迭代所需的衰減因子為

非規則LDPC碼由于本身特性，在NMS算法迭代過程中會進入一種穩定狀態，在這種狀態下錯誤比特數不再改變[11]，提高歸一化因子幅度能夠增加信息值的幅值，進而打破這種穩定狀態提高譯碼性能。在譯碼迭代過程中，歸一化因子隨著迭代次數呈上升趨勢，因此利用最后5次迭代歸一化因子和X得到第r層最后5次迭代所需衰減因子為

3 譯碼結構

結構化方式生成QC-LDPC碼校驗矩陣H需要確定3個參數：基礎矩陣BMS×D、循環轉移值Psd和提升值L，其中1≤s≤S，1≤d≤D。本文所提譯碼結構將校驗節點均分為S組，變量節點均分為D組。若基礎矩陣第t行第j列上的值Ptj不為負，則分配一個大小等于L的隨機存取存儲器(Ramdom Access Memory, RAM)來保存C2V，并使用t、j對此RAM進行標號，否則不分配。校驗節點各組節點個數等于L并再分為g個子層，g=[L/2]，前g-1個子層包含兩個校驗節點，第g個子層節點個數等于2～(L mod 2)。依據分層式譯碼結構，校驗節點信息更新時各組只有一個子層參與計算，并行度等于2S。圖2所示為第t組校驗節點更新結構，每個子層會輸出一個數值：子層號的2倍；多路選擇器(Multiplexer, MUX)根據當前譯碼進程選擇相應子層的輸出值；地址處理單元(Address Processing Unit,APU)將MUX輸出值v轉化為輸入至RAM的兩個地址，其中a0td=mod(v+Ptd,L)，a1td=mod(v+Ptd+1,L)；聯合轉換單元(Joint Conversion Unit, JCU)模塊的作用是將C2V轉化為對應的V2C；flag信號等于1表示子層中節點個數為1個，RAM需要忽略所收到的第2個地址；校驗節點處理單元完成最小值比較等過程。

圖2 校驗節點更新結構

圖3所示為變量節點后驗信息更新結構，D0i0,…和D1i0,…信息值來自第i組校驗節點處理單元；RAM0～RAMd的存儲空間為L，RAMd存放第d·L～(d+1)L-1個變量節點的后驗信息，存放地址與校驗節點更新過程中APU輸出值一致。

圖3 變量節點后驗信息更新結構

在上述譯碼結構的基礎上，擴大RAM數據端口的位寬能夠進一步增加并行度，提升譯碼速度。為降低復雜度，位寬擴大倍數應等于2τ，τ=0,1,2,…，同時子層數、地址和RAM的大小縮小1/2τ，flag位寬擴大2τ倍。

4 仿真結果與分析

4.1 仿真結果

仿真所使用碼字由5G協議中基準圖2構造[12]，共用到兩種碼字：(19 968,3 840)和(4 032,960)，碼率分別為1/5和1/4，加擾噪聲為加性高斯白噪聲，調試方式為二進制相移鍵控(Binary Phase Shift Keying, BPSK)：1→1,0→-1，信息序列由Matlab軟件隨機生成；對于信息序列長度K為3 840的碼字，仿真幀數為3 000，對于K為960的碼字，仿真幀數為12 000，以保證不同提升值情況下總信息序列長度一致；Z設為15。由圖1可知，所使用碼字分為3層，利用所提算法得到前10次迭代歸一化因子：0.879 5、0.487 0和0.027 0；后5次歸一化因子：0.970 3、0.894 9和0.577 2。LDPC譯碼器信息值小數部分通常使用3比特量化[13]，而上述6個因子無法用3比特精確表示，需要使用近似值，結果如表1所示。

表1 各層歸一化因子

圖4所示為兩種碼率下各個算法的譯碼性能，由圖可知，本文所提BD-NMS算法比其他算法擁有更好的譯碼性能。圖4(a)使用的碼字類型為(19 968,3 840)，在BER為10-6量級時，BD-NMS算法的譯碼性能比DE-NMS算法提高了0.19 dB左右；圖4(b)使用的碼字類型為(4 032,960)，在BER為10-6量級時，BD-NMS算法譯碼性能比DE-NMS算法大約提高了0.12 dB。

圖4 兩種碼率下各算法的譯碼性能

圖5所示為各個算法在不同信噪比下的平均迭代次數。仿真過程中，由于噪聲隨機性以及校驗矩陣短圈特性的影響，同一信噪比下迭代次數存在波動現象，故其平均值為小數。由圖可知，所提算法和結構下的譯碼收斂速率比其他算法更快，且在信噪比等于1.9 dB左右時迭代次數差值達到最大。

圖5 各算法在不同信噪比下的平均迭代次數

4.2 復雜度分析

表2所示為4種算法一次迭代所需總計算量。表中，ρj為第j個變量節點度數，λi為第i個校驗節點度數，M為H總行數，N為H總列數。由表可知，MS算法復雜度最低，NMS和DE-MS算法次之，BD-NMS算法復雜度比DE-MS和NMS算法多了M次比較運算，這是因為BD-NMS算法需要對度數大小進行判斷，從而選擇合適的歸一化因子，但譯碼性能比DE-NMS算法提高了接近0.2 dB。

表2 不同算法復雜度對比

所提譯碼結構將矩陣壓縮在L大小，且變量節點的位置與提升值和循環轉移值存在簡單的求模關系，利用基礎矩陣就可以得到節點索引，節省了存儲空間；利用分層譯碼思想，無需特定RAM存放V2C且提高了譯碼速度；層數變化通過調整各組子層標號完成，且子層變化范圍在L之內，在5G系統中，L需要根據實際情況改變大小，這種情況下，所提層數變化方式更容易實現譯碼過程；當基礎矩陣確定后，各組校驗節點處理單元也隨之確定，層數變化時，度數分布不變，校驗節點處理單元也無需做出調整，降低了實現復雜度和資源消耗。

5 結束語

本文通過分析非規則QC-LDPC碼不同度數下校驗節點信息值的差異性，提出了BD-NMS算法。該算法首先計算出最優歸一化因子的分布規律，并根據此規律對度數分層，進而聯合DE理論和加權向量求得各層的歸一化因子。針對非規則LDPC碼會陷入穩態的特性，在最后5次迭代中，使用更大的衰減因子完成譯碼，歸一化因子可提前存儲在寄存器中以避免多余資源消耗。此外本文還提出了一種譯碼結構，每層校驗節點變化范圍在提升值之內，有效降低了資源消耗和譯碼器實現難度。仿真結果與分析表明，所提BD-NMS算法與其他3種算法相比，復雜度的增加只存在于比較運算，譯碼性能和譯碼速度更為優異，可應用至工程中。