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

汪毅峰，潘 濤

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

0 引言

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

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

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

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

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

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

圖1 行列變換后的校驗(yàn)矩陣

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

式中：I為單位矩陣。

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

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

基于如上分析和推導(dǎo)，假設(shè)在NR的物理層數(shù)據(jù)信道[9,10]采用QC-LDPC對(duì)數(shù)據(jù)進(jìn)行編碼，編碼速率R=5/6，碼長(zhǎng)為576 bits，即72 Bytes，公共因子Zf=24。設(shè)碼字校驗(yàn)矩陣為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生成校驗(yàn)矩陣H的規(guī)則為：

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

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

簡(jiǎn)便起見做如下約定：

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

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

式（11）即可作為L(zhǎng)DPC的編碼校驗(yàn)矩陣。

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

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

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

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

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

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

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

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

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

3 結(jié)語(yǔ)

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