基于IEEE 802.16e標準的與CRC結(jié)合的LDPC編譯碼算法研究

王熙，陳雨

（四川大學電子信息學院，成都 610065）

0 引言

LDPC（Low Density Parity Check Code），即低密度校驗碼，是由Robert G.Gallager于1962年在他的博士論文中提出[1]。早先由于硬件計算能力和運算速度有限等原因，LDPC碼沉寂了幾十年，但是在1997年左右，D.MacKay、M.Sipser、Felstrom、Zigangirov 等相繼對LDPC碼重新進行研究，發(fā)現(xiàn)LDPC碼十分逼近香農(nóng)極限。隨后LDPC碼開始廣泛應(yīng)用于DVB-S2、光纖通信、深空通信等多種通信領(lǐng)域，在2016年的3GPP會議中，高通公司以LDPC碼成為了5G通信數(shù)據(jù)傳輸長碼和短碼的編碼標準。

LDPC碼所具有的優(yōu)勢和性能，使其廣泛應(yīng)用于通信領(lǐng)域的各個方向，例如802.16無線城域網(wǎng)，廣泛應(yīng)用于高速、可移動的語音、視頻等業(yè)務(wù)。為了降低LDPC編碼的復(fù)雜度，IEEE 802.16e標準中提出了一種快速編碼方法，本文的研究主要內(nèi)容是結(jié)合CRC的LDPC編譯碼方法，這種方法進一步提高了LDPC編譯碼的準確度和可靠性。

1 LDPC編碼算法

傳統(tǒng)的LDPC碼的編碼算法是高斯消元法，主要算法流程是先利用校驗矩陣H得到生成矩陣G，再將信息源碼與G相乘得到與之對應(yīng)的碼字。這種方法的缺點是需要做的高斯消元法的次數(shù)過多、運算量和存儲量過大，而且按照計算方式可能會得到不止一個G，這樣的結(jié)果并不適合應(yīng)用于硬件實現(xiàn)。

Efficient編碼算法[2]主要是利用校驗矩陣H的近三角形矩陣，可以將校驗矩陣H表示為分塊矩陣的形式，H是m×n維矩陣，m表示校驗位的位數(shù)，n表示碼長的位數(shù)。

其中 A 是（m-g）×（n-m）矩陣，B 是（m-g）×g矩陣，T 是（m-g）×（m-g）下三角形矩陣，C 是 g×（n-m）矩陣，D 是 g×g矩陣，E 是 g×（m-g）矩陣。

在校驗矩陣H上左乘滿秩矩F得到H：

假設(shè)編碼后的碼字C=（S,P1,P2）,其中S為信息位，P1和P2是校驗位。由于碼字Code滿 CT=0T，因此可以得到公式（4-5）。

令φ=-ET-1B+D，有P1T和P2T的表達式：

這樣，通過矩陣j和信息位S計算出校驗位P1和P2,從而得到整個碼字C。這種編碼算法可以達到線性編碼的時間性要求，復(fù)雜度得以降低。

IEEE 802.16e中定義的LDPC碼的H完全由循環(huán)移位單位陣和零矩陣構(gòu)成，屬于準循環(huán)碼，于是可以利用校驗矩陣的稀疏性來完成編碼。在IEEE 802.16e標準中已經(jīng)給出了LDPC碼的基校驗矩陣Hb。

對于各種碼長和碼率的檢驗矩陣H都可以通過基校驗矩陣Hb按照擴展因子為zf=n/24（其中n為碼長）的方式擴展得到。其擴展規(guī)則為：

（1）Hb中 Pi,j=-1 的位置擴展為 zf×zf的零矩陣；

（2）Hb中 Pi,j=0 的位置擴展為 zf×zf的單位矩陣；

（3）Hb中除了-1 和 0 以外的值，擴展為 zf×zf的單位矩陣經(jīng)過p（f,i,j）次循環(huán)右移獲得的矩陣，其中p（f,i,j）由式（9）確定。

當碼率為1/2，碼率為3/4的A、B碼，碼率為2/3的 B 碼和碼率為5/6的碼式p（f,i,j）由式（9）確定,其中z0=2304/24=96。

碼率為 2/3的 A 碼，p（f,i,j）由式（10）確定。

Hb經(jīng)過擴展之后得到的校驗矩陣H。H可以寫成式（11）：

其中0表示0矩陣，-1表示單位矩陣，1表示循環(huán)位移1的單位矩陣，矩陣均為zf×zf維。

假設(shè)編碼后的碼字C=（S,P）,S為信息序列，將S分為k組，其中k=n-m,每組的比特數(shù)為zf。則C可以表示成式（12）。

由式（13）可以得到式（14）。

得到p0后可以依次迭代得到pi（i屬于0到m-1）,進而得到碼字C。

2 CRC

CRC（全稱為循環(huán)冗余校驗碼），它的編碼方式簡單并且誤判概率低。CRC能夠以百分之百的概率檢測出突發(fā)錯誤長度小于等于R（R為CRC的生成多項式g（x）階數(shù)）和錯誤數(shù)為奇數(shù)的隨機錯誤。CRC校驗的基本原理：假設(shè)信息長度是K位，添加R位的校驗碼后，則得到N=K+R位信息總長度，此時將發(fā)送信息用多項式C(x)表示，將C(x)左移R位，左移R位的位置即校驗碼的位置，用信息多項式除以生成多項式得到的余數(shù)即校驗碼。在本文中采用CRC12先對數(shù)據(jù)信息進行編碼，然后使用IEEE 802.16e的快速編碼算法進行LDPC編碼，其中CRC12的生成多項式為式（15）。

3 LDPC譯碼算法

LDPC碼譯碼算法一般采用基于Tanner圖的置信傳播（Belief Propagation,BP），對數(shù)域置信傳播算法將概率消息用似然比（LLR-BP）表示，大量的乘法運算可以變?yōu)榧臃ㄟ\算減少運算時間。在二進制調(diào)制下和置信傳播是等效的。

LLR-BP算法的算法流程如下：

圖1 算法流程

①初始化節(jié)點。計算信道傳遞給變量節(jié)點的初始概率似然比消息L(Pi)，i=1,2,…,n。然后對每一個變量節(jié)點i和與其相鄰的校驗節(jié)點 j∈C(i)，設(shè)定變量節(jié)點傳向校驗節(jié)點的初始消息。

②將信息從比特節(jié)點傳到校驗節(jié)點（校驗節(jié)點消息處理）。對所有的校驗節(jié)點j和與其相鄰的變量節(jié)點i∈R(j)，第l次迭代時，計算變量節(jié)點傳向校驗節(jié)點的消息。

③將信息從校驗節(jié)點傳回比特節(jié)點（變量節(jié)點消息處理）。對所有的消息節(jié)點i和與其相鄰的校驗節(jié)點j∈C()i，第l次迭代時，計算校驗節(jié)點傳向變量節(jié)點的消息。

④對所有變量節(jié)點計算硬判決消息

⑤譯碼判決

若L(l)(qi)>0 ，則 c?(i)=0 ，否則 c?(i)=1。

⑥停止條件

如果 c?HT=0（其中 c?是 n維的行向量）或者 l=max_iter（最大迭代次數(shù)）就終止，否則繼續(xù)返回到過程B迭代。

在結(jié)合CRC的LDPC的譯碼過程中，首先對信道接收到的信息進行LLR-BP譯碼，然后在譯碼結(jié)束的時候?qū)υ诰幋a前加入的檢驗位進行CRC校驗，如果校驗正確或滿足停止條件，就繼續(xù)執(zhí)行下面的譯碼，若檢驗過程中發(fā)現(xiàn)有錯誤，就將錯誤的碼字收集起來，并停止迭代，以減少不必要的迭代，然后將錯誤碼字的似然值進行翻轉(zhuǎn)并重新進行譯碼。

4 仿真結(jié)果

為了驗證算法的有效性，在MATLAB中采用碼率為0.5，碼長為1024的IEEE 802.16e標準的LDPC碼結(jié)合上CRC，經(jīng)過AWGN信道，在不同譯碼方法下運行，可以得到圖2所示的性能對比圖。從圖2可以看出，CRC-LLRBP比起LLP-BP和BP算法，在相同的誤碼率情況下，它具有更高的信噪比，或者說在相同的信噪比情況下，CRC-LLRBP降低了LDPC碼的錯誤平層，獲得了更低的誤碼率。

圖2 不同算法下的性能對比圖

5 結(jié)語

本文給出的結(jié)合CRC的LDPC的編譯碼方法，在編碼中使用CRC結(jié)合LDPC快速編碼算法，在譯碼過程中使用LLR-BP結(jié)合CRC后處理算法，這種算法能夠快速地定位錯誤的碼字并翻轉(zhuǎn)其似然值進行再次譯碼，這樣可以明顯減少無法譯碼的信息位，降低其錯誤平層。