一種可節(jié)約RAM資源的準循環(huán)LDPC碼的編碼裝置

汪毅峰，潘 濤

（上海諾基亞貝爾股份有限公司，江蘇 南京 210037）

0 引言

通信系統(tǒng)設(shè)計的核心問題是如何克服通信信道中隨機噪聲的干擾，在盡可能少地影響信息傳輸效率的同時，減少信息的傳輸誤差，這種在傳輸?shù)男畔⒋a元后附加其他傳輸信息編碼方式叫作糾錯編碼。糾錯編碼按照實現(xiàn)方式可以分為非線性分組編碼和線性分組編碼，其中線性分組編碼根據(jù)校驗矩陣的類型可以細分為非循環(huán)碼和循環(huán)碼兩種方式。[1]

低密度奇偶校驗碼（Low-Density Parity-Check，LDPC）屬于線性分組糾錯碼，早在20世紀60年代，Gallager就在他的博士論文中提出了LDPC碼理論，但受限于當時的硬件計算能力，一直被人們所忽略。直到1995年MacKay和Neal等人提出了可行的譯碼算法后，人們發(fā)現(xiàn)LDPC碼具有極佳的性能，是一種接近香農(nóng)容量限的糾錯碼。隨著硬件計算能力的日漸提升，LDPC碼技術(shù)逐漸成為當前最炙手可熱的信道編碼技術(shù)。LDPC碼糾錯能力強、編碼效率高，而且碼率可從1/2至15/16中選擇，十分靈活。目前，LDPC碼的相關(guān)理論技術(shù)也日趨成熟，并且出現(xiàn)了很多成熟的研究成果，并逐漸進入了多項無線通信技術(shù)標準，例如數(shù)字廣播電視、WiMax和新無線（New Radio，NR）的物理層數(shù)據(jù)信道等標準都支持LDPC編碼，尤其是NR在標準討論之初，就明確了凡是物理層數(shù)據(jù)信道，編碼方案都使用LDPC碼[2-5]。

1 一種基于準循環(huán)LDPC編碼裝置

NR在物理數(shù)據(jù)信道，選擇使用LDPC編解碼方案，并且寫入了標準《3GPP TS 38.212 物理層復(fù)用和信道編碼協(xié)議》[6-8]。LDPC碼作為最具發(fā)展?jié)摿蛻?yīng)用前景的一類分組糾錯碼，其挑戰(zhàn)在于編碼復(fù)雜，且并行譯碼算法的硬件資源的開銷大。為充分發(fā)揮LDPC碼的性能優(yōu)勢，并合理控制硬件復(fù)雜度，通常尋求碼字校驗矩陣具有一定規(guī)律的LDPC編碼。然而，使用規(guī)則LDPC編碼方式時，其編碼性能明顯低于不規(guī)則LDPC編碼，特別是采用和積譯碼算法時性能損失大。此外，雖然循環(huán)碼具有簡單的編碼器，但遺憾的是，相比于其他性能優(yōu)異的編解碼方案，循環(huán)碼性能同樣有損失，而準循環(huán)碼卻具有更良好的性能。準循環(huán)碼可以用在規(guī)則LDPC編碼上，也可以用在非規(guī)則LDPC編碼上，同時具有相對較低復(fù)雜度的編碼結(jié)構(gòu)，所以應(yīng)用更廣泛，例如，WiMax標準中就支持非規(guī)則的LDPC準循環(huán)碼的編碼方案。FPGA是目前通用的邏輯器件，可以有效實現(xiàn)QC-LDPC碼的編碼以及相對應(yīng)的譯碼算法[6,8]。

假設(shè)QC-LDPC選擇的校驗矩陣H1是一個m行n列的矩陣，QC-LDPC步驟簡單闡述如下：

（1）對選擇的校驗矩陣H1進行線性變化得到一個如圖1所示的矩陣，可以看到原來的校驗矩陣H1被拆成A,B,T,C,D,E6個子矩陣。行列重排存在切分后，存在某個子矩陣列的維數(shù)和碼元比特輸出行的維數(shù)均為N-M，滿足矩陣相乘，這樣的矩陣切分可以大大減少運算量，其中N是校驗矩陣總行數(shù)，M是校驗矩陣全0行數(shù)，g是校驗矩陣除掉全0行數(shù)和對角矩陣后的剩余行數(shù)。

圖1 行列變換后的校驗矩陣

（2）對分解后的校驗矩陣H1進行矩陣變換，構(gòu)造矩陣如式（1），得到新的校驗矩陣H如式（2）所示。構(gòu)造的矩陣要避免生成的新校驗矩陣短環(huán)的問題，這是從LDPC角度考慮的，因為要保證LDPC迭代譯碼時，能充分利用碼字內(nèi)各比特的相關(guān)性，構(gòu)造矩陣：

式中：I為單位矩陣。

（3）設(shè)進入編碼器分為有效信息S和校驗信息P1和P2兩部分，有效信息的編碼長度為g，校驗信息的編碼長度為M-g，則得到：

（4）通過式（3）進行線性變換，找到校驗信息和有效信息之間的關(guān)系如式（4），注意到 -ET-1B+D要為一個非奇異矩陣，這是因為在約束校驗信息和有效信息之間需要對這個矩陣求逆，如果不能滿足非奇異特性，就不存在逆矩陣，所以在校驗矩陣分塊的時候也需要考慮到這一點。根據(jù)式（3）可以推導(dǎo)出：

基于如上分析和推導(dǎo)，假設(shè)在NR的物理層數(shù)據(jù)信道[9,10]采用QC-LDPC對數(shù)據(jù)進行編碼，編碼速率R=5/6，碼長為576 bits，即72 Bytes，公共因子Zf=24。設(shè)碼字校驗矩陣為H，如式（5）；H是96行576列的稀疏矩陣，并設(shè)其基矩陣為Hb，如式（6）。

式中：A為72行480列的矩陣；B為72行24列的矩陣；T為72行72列的矩陣；C為24行480列的矩陣；D為24行24列的矩陣；E為24行72列的矩陣。

基于矩陣Hb生成校驗矩陣H的規(guī)則為：

式中：p(i,j)為Hb的第i行第j列的元素；為向下取整運算；p(f,i,j)為運算結(jié)果。設(shè)I24為24階單位陣，當p(f,i,j)小于0時，相對的元素以24行24列0矩陣代替，當p(f,i,j)等于0時，相對的元素以I24代替，當p(f,i,j)大于0時，相對的元素以I24的向右循環(huán)移位矩陣代替，移位位數(shù)為p(f,i,j)。

LDPC碼也屬于分組碼的范疇，以組為單位對碼元進行編碼[4,5]，設(shè)碼元信息bit為uT，其中u為480列的行向量。設(shè)v為編碼的碼字，LDPC編碼結(jié)果v可以表示為：

簡便起見做如下約定：

令α=ET-1A+C，β=T-1(A+BET-1A+BC)，則α為24行480列的矩陣，β為72行480列的矩陣，式（8）可以簡寫為：

式中：I480為480階單位陣；α和β都是常數(shù)矩陣。

式（11）即可作為LDPC的編碼校驗矩陣。

2 簡化準循環(huán)LDPC編碼方法

由于α，β和u都是維數(shù)較大的矩陣或向量，如果直接這樣實現(xiàn)則需要較多的邏輯資源。為進一步簡化準循環(huán)LDPC碼的編碼復(fù)雜度，在編碼裝置設(shè)計中，充分發(fā)揮LDPC碼的最大特點，即校驗矩陣的稀疏特性，并且為了合理有效地利用FPGA資源，特別是減少FPGA硬件邏輯資源和RAM存儲資源，提出一種簡易的準循環(huán)碼編碼裝置。該裝置采取流水線的方式，利用移位寄存器來實現(xiàn)，即u以比特逐個進入，依次進行與運算并進行模2求和，一組信息全部完畢后再逐個輸出編碼碼字。編碼電路如圖2所示。

圖2 QC-LDPC編碼方案硬件電路

這樣的編碼方式仍然會耗費很多的FPGA的RAM資源，非常不經(jīng)濟，對此本文充分利用LDPC校驗矩陣的稀疏特性來簡化編碼裝置。經(jīng)計算，發(fā)現(xiàn)α和β同樣為稀疏矩陣，其中α的每行中有61個1，其余為0，而β的每行中，只可能是36個1或51個1或81個1，都遠小于其列數(shù)480。

以4字節(jié)（32 bits）表示α，β和u的行，則α變?yōu)?4行15列的矩陣，β為72行15列的矩陣，u變?yōu)殚L為15的行向量。這樣共需15次移位可完成整個運算。設(shè)α，β和u分別表示為：

式中：xij表示矩陣x的第i行32(j-1)+1位至第32j位bit中1所在的位置，有幾個1就有幾個值需要被表示。這樣u以32 bits為單位逐個表示，依次與ai，j和bi，j進行按位與運算，并對結(jié)果模2求和，一組信息全部完畢后再逐個輸出，得到編碼的碼字。編碼電路可改變?yōu)閳D3。

圖3 基于QC-LDPC的簡化編碼裝置結(jié)構(gòu)

由于每個元素ai，j和bi，j的位數(shù)均為32位，因此最多只需5 bits就能表示32位中任意一個bit的位置。例如，α1.1，即α第一行的前32列元素可表示為{10000 00000 00100 00100 00000 10000 10}，共有5個1，分別位于第0，12，17，25，30位，其余均為0。為節(jié)省存儲空間忽略元素0，只將元素1所在的位置表示出來，則α1.1=(0,12,17,15,30)，即α1.1可表示為{0 1100 10001 11001 11110}，共 20 bits，便可表示原來的32 bits校驗矩陣所要表示的信息。類似地，可得到其他ai，j和bi，j的位置表示。

經(jīng)計算，采用新的基于存儲有效信息地址的方式，最后可用22 234 bits表示α和β，而本來共需96×480=46 080 bits來表示，可見本編碼方案大大縮小了對RAM的需求，可節(jié)約一半左右的RAM的存儲空間資源。

3 結(jié)語

本文對QC-LDPC編碼提出的改進方式，可以使得LDPC編碼裝置更加合理有效地利用FPGA資源。本文方法以移位寄存器方式實現(xiàn)LDPC碼的編碼，采取流水線結(jié)構(gòu)來減少FPGA硬件邏輯資源，并通過矩陣變換，以非0元素的位置代替原稀疏矩陣的矩陣表示，從而大大降低了RAM存儲資源，節(jié)省了編碼器的硬件資源。