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

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

（1.重慶郵電大學 重慶市移動通信重點實驗室，重慶 400065；2.重慶郵電大學 通信與信息工程學院，重慶 400065；3.重慶電子工程職業(yè)學院 軟件工程系，重慶 401331；4.廈門大學 寬帶無線通信實驗室，福建 廈門 361005）

0 引言

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

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

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

1 多邊類型的LDPC碼

1.1 多邊類型的LDPC碼

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

多邊類型的LDPC碼變量點和校驗點表示為

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

1.2 多邊LDPC碼的多碼率算法

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

1）通過式（2）計算出刪余的位數(shù)Npunc，通過式（3）計算出度為2時的最大插入刪余比特數(shù)Nim。

其中：N為碼字長度；k為信息比特長度；Rt為目標碼率。

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

3）對度為1的校驗點根據(jù)上面的分析隨機選擇Npunc進行刪余。

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

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

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

2 間隔刪余算法

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

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

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

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

3）對度為1的校驗位隨機選擇Npunc進行刪余。

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

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

度為2的校驗比特的刪余處理如圖1所示。

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

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

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

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

表1 刪余模塊資源對比

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

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

3.2 交織網(wǎng)分析

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

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

3.3 實驗結(jié)果

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

表2 譯碼器整體資源

4 結(jié)論

本文先介紹了一種多碼率多邊類型的LDPC碼，隨后提出一種間隔刪余算法，設計了一種多碼率多邊類型的LDPC碼譯碼器架構(gòu)，該架構(gòu)采用部分并行譯碼結(jié)構(gòu)，能實現(xiàn)固定碼長不同碼率共用相同的存儲資源。基于該架構(gòu)在Xilinx Virtex4 xc4vlx100芯片上實現(xiàn)了碼長為640 bit，碼率為0.5～0.8的多碼率多邊類型的LDPC碼譯碼器。實驗結(jié)果表明，該譯碼器的平均吞吐量能達到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.