王熙，陳雨

（四川大學(xué)電子信息學(xué)院，成都 610065）

0 引言

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

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

1 LDPC編碼算法

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

Efficient編碼算法[2]主要是利用校驗(yàn)矩陣H的近三角形矩陣，可以將校驗(yàn)矩陣H表示為分塊矩陣的形式，H是m×n維矩陣，m表示校驗(yàn)位的位數(shù)，n表示碼長(zhǎng)的位數(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）矩陣。

在校驗(yàn)矩陣H上左乘滿秩矩F得到H：

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

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

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

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

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

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

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

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

當(dāng)碼率為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)過(guò)擴(kuò)展之后得到的校驗(yàn)矩陣H。H可以寫成式（11）：

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

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

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

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

2 CRC

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

3 LDPC譯碼算法

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

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

圖1 算法流程

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

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

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

④對(duì)所有變量節(jié)點(diǎn)計(jì)算硬判決消息

⑤譯碼判決

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

⑥停止條件

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

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

4 仿真結(jié)果

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

圖2 不同算法下的性能對(duì)比圖

5 結(jié)語(yǔ)

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