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

王熙，陳雨

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

0 引言

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

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

1 LDPC編碼算法

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

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

其中 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：

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

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

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

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

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

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

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

（3）Hb中除了-1 和 0 以外的值，擴展為 zf×zf的單位矩陣經過p（f,i,j）次循環右移獲得的矩陣，其中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經過擴展之后得到的校驗矩陣H。H可以寫成式（11）：

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

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

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

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

2 CRC

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

3 LDPC譯碼算法

LDPC碼譯碼算法一般采用基于Tanner圖的置信傳播（Belief Propagation,BP），對數域置信傳播算法將概率消息用似然比（LLR-BP）表示，大量的乘法運算可以變為加法運算減少運算時間。在二進制調制下和置信傳播是等效的。

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

圖1 算法流程

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

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

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

④對所有變量節點計算硬判決消息

⑤譯碼判決

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

⑥停止條件

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

在結合CRC的LDPC的譯碼過程中，首先對信道接收到的信息進行LLR-BP譯碼，然后在譯碼結束的時候對在編碼前加入的檢驗位進行CRC校驗，如果校驗正確或滿足停止條件，就繼續執行下面的譯碼，若檢驗過程中發現有錯誤，就將錯誤的碼字收集起來，并停止迭代，以減少不必要的迭代，然后將錯誤碼字的似然值進行翻轉并重新進行譯碼。

4 仿真結果

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

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

5 結語

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