多碼率多邊類型LDPC碼譯碼器的設(shè)計(jì)與實(shí)現(xiàn)

甘永銀，胡文江，黃 睿，謝東福

（1.重慶郵電大學(xué) 重慶市移動(dòng)通信重點(diǎn)實(shí)驗(yàn)室，重慶 400065；2.重慶郵電大學(xué) 通信與信息工程學(xué)院，重慶 400065；3.重慶電子工程職業(yè)學(xué)院 軟件工程系，重慶 401331；4.廈門大學(xué) 寬帶無(wú)線通信實(shí)驗(yàn)室，福建 廈門 361005）

0 引言

LDPC碼以其接近香農(nóng)極限的糾錯(cuò)性能，近年來(lái)受到越來(lái)越多的關(guān)注。目前，LDPC碼已經(jīng)被廣泛應(yīng)用于多種通信標(biāo)準(zhǔn)中，如802.11n，DVB-S2，802.15.3c（WPAN）和802.16e（WiMAX）。而多邊LDPC碼相對(duì)于傳統(tǒng)的LD?PC碼具有更好的糾錯(cuò)性能[1-2]，它可視為由多個(gè)子碼所構(gòu)成的級(jí)聯(lián)碼。通過(guò)在多個(gè)子碼之間分層迭代譯碼，相較其他的LDPC碼碼型，多邊類型LDPC碼（multi-edge-type LDPC codes）具有較為明顯的性能優(yōu)勢(shì)。

目前LDPC碼譯碼器的架構(gòu)比較多，實(shí)現(xiàn)的吞吐量也比較大，如文獻(xiàn)[3]中實(shí)現(xiàn)了碼長(zhǎng)為1024 bit，碼率為0.5，吞吐量為1 Gbit/s的譯碼器。然而在無(wú)線通信中，信道通常是時(shí)變的，為了適應(yīng)信道的這一特性，多碼率LDPC碼的研究成為一個(gè)熱點(diǎn)。目前，文獻(xiàn)[4]已經(jīng)在硬件上實(shí)現(xiàn)了支持碼長(zhǎng)為360～4200 bit，碼率為1/4～9/10的LDPC碼譯碼器。文獻(xiàn)[5]也在FPGA上實(shí)現(xiàn)了碼長(zhǎng)為10000 bit，碼率分別為1/2，5/8和7/8的LDPC譯碼器。而在這些譯碼器中，對(duì)固定碼長(zhǎng)的多碼率LDPC碼譯碼器的研究和實(shí)現(xiàn)都較少。本文研究的多邊類型LDPC碼譯碼器是一種固定碼長(zhǎng)的多碼率譯碼器，它通過(guò)對(duì)不同邊上的校驗(yàn)信息的刪余實(shí)現(xiàn)多碼率譯碼。

本文提出了一種實(shí)現(xiàn)多邊LDPC碼碼率變化的間隔刪余算法，簡(jiǎn)化了硬件實(shí)現(xiàn)的復(fù)雜度。設(shè)計(jì)了一種固定碼長(zhǎng)不同碼率共用相同存儲(chǔ)單元的存儲(chǔ)資源利用結(jié)構(gòu)和半并行的譯碼結(jié)構(gòu)，并根據(jù)多邊子碼分層譯碼的特點(diǎn)對(duì)譯碼器中的變量點(diǎn)和校驗(yàn)點(diǎn)采用分時(shí)運(yùn)算，降低了計(jì)算單元的資源消耗。

1 多邊類型的LDPC碼

1.1 多邊類型的LDPC碼

多邊LDPC碼是由Tom Richardson和Rudiger Urban?ke提出，這種碼型概括為規(guī)則的和不規(guī)則的LDPC碼[1],比如級(jí)聯(lián)樹(shù)碼（CT）、不規(guī)則重復(fù)累積碼（IRA）、低密度產(chǎn)生矩陣碼（LDGM）和傳統(tǒng)的LDPC碼都可以視為多邊類型的LDPC碼的特殊情況。

多邊類型的LDPC碼變量點(diǎn)和校驗(yàn)點(diǎn)表示為

式中：d=(d1,d2,…,dn)表示多邊類型的度，其中n為邊類型的數(shù)量；x=(x1,x2,…,xn)表示變量點(diǎn)；xd表示為表示接收的度；r=(r,r,…,r)12t表示與變量點(diǎn)相應(yīng)的接收分配的度，其中t為不同接收分配類型的數(shù)量。假設(shè)多邊類型的LDPC碼的碼長(zhǎng)為N，因此，變量點(diǎn)類型的數(shù)量為v(b,d)N，同理校驗(yàn)點(diǎn)類型的數(shù)量為μdN。

1.2 多邊LDPC碼的多碼率算法

本節(jié)將介紹一種適合多邊LDPC碼的多碼率算法。由于多邊LDPC碼的碼型結(jié)構(gòu)優(yōu)于傳統(tǒng)的LDPC碼，因此可以通過(guò)對(duì)母碼的刪余處理獲得碼率的調(diào)整。為了克服短碼的隨機(jī)刪余，J.Ha提出了采用分組和排序法（GS）的思想[6]。在此基礎(chǔ)上一種簡(jiǎn)化的GS算法[2]更適合多邊LDPC碼。通過(guò)對(duì)度為1和度為2的校驗(yàn)位進(jìn)行刪余實(shí)現(xiàn)多碼率的譯碼。

1）通過(guò)式（2）計(jì)算出刪余的位數(shù)Npunc，通過(guò)式（3）計(jì)算出度為2時(shí)的最大插入刪余比特?cái)?shù)Nim。

其中：N為碼字長(zhǎng)度；k為信息比特長(zhǎng)度；Rt為目標(biāo)碼率。

2）如果None≥Npunc，轉(zhuǎn)到步驟3），如果None≤Npunc，轉(zhuǎn)到步驟4）。

3）對(duì)度為1的校驗(yàn)點(diǎn)根據(jù)上面的分析隨機(jī)選擇Npunc進(jìn)行刪余。

4）對(duì)于度為2的校驗(yàn)位，在每2個(gè)未刪余節(jié)點(diǎn)間刪余的校驗(yàn)位為隨機(jī)產(chǎn)生的1個(gè)不大于Nim的任意整數(shù)None-(Npunc-None)-1。如ti進(jìn)行刪余，標(biāo)注ti作為第i個(gè)整數(shù)，并在第i個(gè)和（i+1）個(gè)未被刪余的度為2的校驗(yàn)位中插入ti個(gè)刪余校驗(yàn)位。

5）如果刪余位等于Npunc，就停止。

在None≥Npunc的時(shí)候，根據(jù)母碼特殊碼型的特點(diǎn)直接對(duì)度為1的校驗(yàn)位進(jìn)行簡(jiǎn)單的隨機(jī)刪余達(dá)到目標(biāo)碼率。在None≤Npunc時(shí)，對(duì)度2的校驗(yàn)位進(jìn)行刪余，由于兩個(gè)為刪余節(jié)點(diǎn)間的刪余個(gè)數(shù)是隨機(jī)產(chǎn)生的不易于硬件的實(shí)現(xiàn)，所以下節(jié)中提出一種適合硬件實(shí)現(xiàn)的刪余算法，即間隔刪余算法。

2 間隔刪余算法

提出一種實(shí)現(xiàn)多碼率的間隔刪余算法，并通過(guò)實(shí)現(xiàn)分析了間隔刪余算法與GS算法的資源消耗。本文是以碼長(zhǎng)為640 bit、碼率為0.5的多邊類型的LDPC碼為母碼，利用其多邊LDPC碼優(yōu)越的碼型結(jié)構(gòu)，根據(jù)間隔刪余算法對(duì)該碼的校驗(yàn)位進(jìn)行刪余調(diào)整來(lái)達(dá)到多碼率的要求。

度為2的信息節(jié)點(diǎn)是由重復(fù)累積碼產(chǎn)生的，刪余節(jié)點(diǎn)的似然信息通過(guò)前向似然信息和后向似然信息進(jìn)行更新。以圖1為例，在圖1中，與刪余變量點(diǎn)相連的、至少一個(gè)校驗(yàn)點(diǎn)與相鄰的、所有變量點(diǎn)都不被刪余的定義為一步恢復(fù)點(diǎn)（1SR）。在這種情況下，這個(gè)校驗(yàn)叫作生存校驗(yàn)。同理，k步恢復(fù)點(diǎn)（kSR）定義為刪余變量點(diǎn)相連至少1個(gè)生存校驗(yàn)點(diǎn)，而這個(gè)校驗(yàn)點(diǎn)又至少相連一個(gè)（k-1）步恢復(fù)點(diǎn)和一些m步恢復(fù)點(diǎn)，其中0＜m≤k-1。圖1中的刪余節(jié)點(diǎn)的恢復(fù)步驟都是兩步恢復(fù)的，這樣每個(gè)刪余校驗(yàn)點(diǎn)的前向和后向似然信息都沒(méi)有被刪余，能為刪余節(jié)點(diǎn)提供信息進(jìn)行更新，這樣提高了信息恢復(fù)的準(zhǔn)確度。間隔刪余算法的步驟為：

1）計(jì)算出總的刪余位數(shù)Npunc，公式為

2）如果None≥Npunc，轉(zhuǎn)到步驟3），如果None≤Npunc，轉(zhuǎn)到步驟4）。

3）對(duì)度為1的校驗(yàn)位隨機(jī)選擇Npunc進(jìn)行刪余。

4）對(duì)度為2的校驗(yàn)位的偶數(shù)位依次進(jìn)行刪余，刪余數(shù)為Ntwo=Npunc-None。

5）如果刪余總位數(shù)等于Npunc，就停止。

度為2的校驗(yàn)比特的刪余處理如圖1所示。

根據(jù)間隔刪余的算法，以MET-LDPC碼為母碼，碼率為0.5，碼長(zhǎng)640 bit在高斯信道下進(jìn)行性能仿真。仿真結(jié)果與同在高斯信道下碼長(zhǎng)600 bit的RC irregular LDPC碼[7]進(jìn)行比較，如圖2所示。從圖2中可以得到間隔刪余的MET-LDPC碼比RC irregular LDPC碼有0.2 dB的增益。

選用了Xilinx公司的Virtex4 xc4vlx15仿真環(huán)境為modelsim SE6.5E，表1給出了刪余模塊在2種算法下的占用資源情況。由于間隔刪余算法簡(jiǎn)單，所以硬件實(shí)現(xiàn)時(shí)資源占用較少。

3 多碼率多邊LDPC碼譯碼器結(jié)構(gòu)

3.1 譯碼器結(jié)構(gòu)

表1 刪余模塊資源對(duì)比

通常LDPC碼譯碼器有并行譯碼結(jié)構(gòu)、串行譯碼結(jié)構(gòu)和部分譯碼結(jié)構(gòu)。并行譯碼結(jié)構(gòu)能實(shí)現(xiàn)很高的吞吐量，但計(jì)算單元的并行運(yùn)用消耗了大量的資源，復(fù)雜的互聯(lián)網(wǎng)絡(luò)增加了硬件實(shí)現(xiàn)的復(fù)雜度，如文獻(xiàn)[8]實(shí)現(xiàn)的并行譯碼器吞吐量達(dá)到了100 Gbit/s。串行譯碼器即只有1個(gè)校驗(yàn)點(diǎn)計(jì)算單元CNU和1個(gè)變量點(diǎn)計(jì)算單元VNU，它能實(shí)現(xiàn)最小的硬件資源的消耗，由于其吞吐量太低，不適合實(shí)際用途，文獻(xiàn)[9]采用的是分段譯碼的串行譯碼架構(gòu)實(shí)現(xiàn)。

本文根據(jù)多邊LDPC碼碼型結(jié)構(gòu)的特點(diǎn)，提出了一種適合多邊多碼率的LDPC碼的部分并行譯碼器結(jié)構(gòu)如圖3。該結(jié)構(gòu)由變量點(diǎn)計(jì)算單元VNU、校驗(yàn)點(diǎn)計(jì)算單元CNU、交織器、前后向信息運(yùn)算單元ANU和存儲(chǔ)陣列RAM等部分組成。本文多邊LDPC碼譯碼器是通過(guò)各個(gè)子碼分層譯碼實(shí)現(xiàn)的，因此本結(jié)構(gòu)采用子碼間循環(huán)譯碼的方法進(jìn)行更新譯碼信息。不同子碼采用不同的交織器以提高譯碼性能。譯碼器每次只能譯碼一幀的信息，即每一幀的信息只有在各個(gè)子碼分層譯碼成功后才能繼續(xù)譯碼下一幀的信息。在圖3的譯碼結(jié)構(gòu)中，最頂層是信道信息的存儲(chǔ)陣列，該信息是信道傳給譯碼器進(jìn)行譯碼的似然信息。最下面一部分是內(nèi)碼譯碼結(jié)構(gòu)，其中該部分的最后一層是信道傳給內(nèi)碼譯碼的校驗(yàn)信息的存儲(chǔ)陣列，通過(guò)對(duì)該層接收到信息的刪余，達(dá)到對(duì)碼率的調(diào)整。而中間則是SPC碼、IRA碼上支路和IRA碼下支路幾個(gè)分層譯碼部分。其中，SPC碼和IRA碼由于不同節(jié)點(diǎn)連接不同類型的邊，因此每種類型的邊的交織器不同。準(zhǔn)循環(huán)交織器能實(shí)現(xiàn)無(wú)時(shí)延的并行交織，所以在每個(gè)子層很容易實(shí)現(xiàn)流水線操作。根據(jù)對(duì)計(jì)算單元VNU，CNU，ANU等個(gè)數(shù)為1～k的選擇，可以對(duì)譯碼器部分并行譯碼的度進(jìn)行配置。本文在資源消耗和譯碼吞吐量上進(jìn)行折中，選擇并行譯碼度為8，此時(shí)譯碼復(fù)雜度和吞吐量能達(dá)到一個(gè)比較平衡的點(diǎn)。

3.2 交織網(wǎng)分析

隨機(jī)交織器由于其隨機(jī)性的任意排列，在硬件實(shí)現(xiàn)時(shí)將很難避免并列訪問(wèn)相同的內(nèi)存，而導(dǎo)致訪問(wèn)沖突。在圖3的多邊類型的LDPC碼譯碼器結(jié)構(gòu)中，選擇準(zhǔn)循環(huán)交織器作為譯碼器的交織器。準(zhǔn)循環(huán)交織器在性能上比隨機(jī)交織器好，而且硬件實(shí)現(xiàn)較簡(jiǎn)單。對(duì)于一個(gè)度為j的節(jié)點(diǎn)，j點(diǎn)位置的連續(xù)信息都必須分配在1個(gè)RAM中。因此，存儲(chǔ)器RAM與計(jì)算單元互相對(duì)應(yīng)。

通過(guò)Matlab仿真可知，一個(gè)度為P的信息通過(guò)準(zhǔn)循環(huán)交織器是可以無(wú)時(shí)延地存儲(chǔ)到P個(gè)RAM中的。例如圖4就是1個(gè)碼長(zhǎng)25，并行度P=5的循環(huán)交織過(guò)程。5個(gè)變量點(diǎn)計(jì)算的信息通過(guò)5個(gè)多路選擇器可以無(wú)沖突地同時(shí)存儲(chǔ)到5個(gè)RAM中。在本文的碼型長(zhǎng)度中經(jīng)過(guò)Matlab仿真分析，所需要的碼型長(zhǎng)度在P=4或者P=8時(shí)都能無(wú)時(shí)延地進(jìn)行交織。

3.3 實(shí)驗(yàn)結(jié)果

本文采用輸入軟信息5 bit均勻量化，譯碼外信息6 bit均勻量化的方式，在Xilinx Virtex4 xc4vlx100，仿真環(huán)境為modelsim SE 6.5c，在140 MHz的時(shí)鐘上實(shí)現(xiàn)了碼長(zhǎng)為640 bit，碼率為0.5～0.8的多碼率多邊LDPC碼譯碼器。表2給出了整個(gè)譯碼器的占用資源情況，其中百分?jǐn)?shù)表示所消耗資源占FPGA總資源的比例。

表2 譯碼器整體資源

4 結(jié)論

本文先介紹了一種多碼率多邊類型的LDPC碼，隨后提出一種間隔刪余算法，設(shè)計(jì)了一種多碼率多邊類型的LDPC碼譯碼器架構(gòu)，該架構(gòu)采用部分并行譯碼結(jié)構(gòu)，能實(shí)現(xiàn)固定碼長(zhǎng)不同碼率共用相同的存儲(chǔ)資源。基于該架構(gòu)在Xilinx Virtex4 xc4vlx100芯片上實(shí)現(xiàn)了碼長(zhǎng)為640 bit，碼率為0.5～0.8的多碼率多邊類型的LDPC碼譯碼器。實(shí)驗(yàn)結(jié)果表明，該譯碼器的平均吞吐量能達(dá)到10 Mbit/s。

[1]RICHARDSON T J，URBANKE R L.Multi-edge type LDPC codes[EB/OL].[2010-09-25].http：//lthcwww.epfl.ch/papers/multiedge.ps.

[2]YOU Ying，XIAO Min，WANG Lin.The rate-compatible multi-edge type LDPC codes with short block length[C]//Proc.IEEE WICOM.[S.l.]：IEEE Press，2009：770-773.

[3]BLANKSBY A J，HOWLAND C J.A 690-mW 1-Gb/s 1024-b，rate-1/2 low-density parity-check code decoder[J].IEEE Journal of Solid-State Circuits，2002，37（3）：404-412.

[4]SUN Yang，KARKOOTI M，JOSEPH R.VLSI decoder architecture for high throughput,variable block-size and multi-rate LDPC codes[C]//Proc.IEEE International Symposium on Circuits and Systems，2007.[S.l.]：IEEE Press，2007：2104-2107.

[5]YANG Lei，SHEN Manyuan，LIU Hui，et al.An FPGA implementation of low-density parity-check code decoder with multi-rate capability[EB/OL].[2010-09-25].http：//ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=1466451.

[6]HA J，KIM J，KLINC D，et al.Rate-compatible punctured low-density parity-check codes with short block lengths[J].IEEE Trans.Inf.Theory，2006，52（2）：728-738.

[7]YANG M，RYAN W E，LI Y.Design of efficiently encodable moderatelength high-rate irregular LDPC codes[J].IEEE Trans.Commun.，2004，52（4）：564-571.

[8]SELVARATHINAM A，CHOI G，NARAYANAN K，et al.A massively scaleable decoder architecture for low-density parity-check codes[C]//Proc.the 2003 International Symposium on Circuits and Systems.[S.l.]：IEEE Press，2003，2：25-28.

[9]YEO E，PAKZAD P，NIKOLIC B，et al.High throughput low-density parity-check decoder architectures[C]//Proc.IEEE Global Telecommunications Conference.[S.l.]：IEEE Press，2001，5：3019-3024.