CCSDS標(biāo)準(zhǔn)下低碼率LDPC碼的編碼器設(shè)計(jì)

龔楊陽(yáng)，安軍社，朱 巖

（1.中國(guó)科學(xué)院國(guó)家空間科學(xué)中心 北京100190；2.中國(guó)科學(xué)院大學(xué) 北京100190）

CCSDS標(biāo)準(zhǔn)下低碼率LDPC碼的編碼器設(shè)計(jì)

龔楊陽(yáng)1，2，安軍社1，朱 巖1

（1.中國(guó)科學(xué)院國(guó)家空間科學(xué)中心 北京100190；2.中國(guó)科學(xué)院大學(xué) 北京100190）

基于空間咨詢委員會(huì)（CCSDS）推薦的深空通信標(biāo)準(zhǔn)，針對(duì)碼長(zhǎng)為4096，碼率為1/2、2/3、4/5的LDPC碼，提出了一種實(shí)現(xiàn)在FPGA的編碼器設(shè)計(jì)方法。根據(jù)生成矩陣的塊循環(huán)特性，使用移位累加寄存器來(lái)設(shè)計(jì)編碼器，3個(gè)碼率使用同一套觸發(fā)器，從而極大的節(jié)省了硬件消耗資源。

LDPC碼；原模圖；CCSDS標(biāo)準(zhǔn)；深空通信；移位累加寄存器

低密度奇偶校驗(yàn)（LDPC）碼是Gallager[1]博士在1961年提出的一種線性分組碼，采用迭代譯碼算法譯碼。近年來(lái)的很多研究表明，LDPC碼有著接近香農(nóng)極限的優(yōu)異性能，有著廣闊的應(yīng)用前景[2]?？臻g咨詢委員會(huì)（CCSDS）也將其推薦為應(yīng)用于深空通信的信道編碼方式[3]。

香農(nóng)指出，對(duì)于任何信道，只要采用隨機(jī)性編、譯碼方式，編碼長(zhǎng)度接近無(wú)限大，在其信息傳輸速率不超過(guò)信道容量時(shí)，采用最佳的似然譯碼方案，必然存在一種編碼方式的誤碼率可以任意小[4]。LDPC碼之所以有如此好的性能，就在于其編碼時(shí)引入交織器而實(shí)現(xiàn)了偽隨機(jī)性。并且，由于迭代譯碼算法的譯碼復(fù)雜度不會(huì)因碼長(zhǎng)的增加，使得LDPC碼在碼長(zhǎng)較長(zhǎng)的情況下也可以有很強(qiáng)的糾錯(cuò)能力，用較少的資源消耗獲得極高的吞吐量。

文中是基于CCSDS提出的131.1-O-2標(biāo)準(zhǔn)，實(shí)現(xiàn)了碼長(zhǎng)為4096，碼率為1/2、2/3、4/5的LDPC碼的編碼器設(shè)計(jì)。該編碼器硬件實(shí)現(xiàn)復(fù)雜度低，通過(guò)軟件仿真譯碼性能，與標(biāo)準(zhǔn)中給出的譯碼性能曲線進(jìn)行對(duì)比，保證編碼器編碼優(yōu)越性能。

1 原模圖LDPC碼

LDPC碼是一種有著稀疏校驗(yàn)矩陣的線性分組碼，校驗(yàn)矩陣的稀疏性讓LDPC碼與其他線性分組碼有著不同的譯碼算法，也保證了LDPC的譯碼低復(fù)雜度和較小的最小碼距。LDPC碼的設(shè)計(jì)也是從構(gòu)造一個(gè)稀疏的校驗(yàn)矩陣開(kāi)始的，然后再通過(guò)校驗(yàn)矩陣確定生成矩陣，從而進(jìn)行后續(xù)的編碼。所以構(gòu)造LDPC碼的本質(zhì)就是構(gòu)造一個(gè)稀疏的校驗(yàn)矩陣。構(gòu)造稀疏矩陣的方法有很多種，基本方法就是在全零矩陣中將少數(shù)的0置換為1。一個(gè)好的LDPC碼要滿足無(wú)短環(huán)、無(wú)低碼重碼字和碼間最小距離要盡可能大的條件[9]，因此我們要使用合理的構(gòu)造稀疏矩陣的方法。

2003年，J.Thorpe[5]提出了一種由原模圖構(gòu)造的LDPC碼的方法，我們稱(chēng)之為原模圖LDPC碼。原模圖是一種指節(jié)點(diǎn)數(shù)量相對(duì)較少的Tanner圖。精心設(shè)計(jì)的原模圖一般無(wú)四環(huán)，且構(gòu)造出來(lái)的稀疏矩陣一般是準(zhǔn)循環(huán)矩陣。

圖1 原模圖復(fù)制三次后置換

原模圖由校驗(yàn)節(jié)點(diǎn)C、變量節(jié)點(diǎn)V和邊E組成，邊連接校驗(yàn)節(jié)點(diǎn)和變量節(jié)點(diǎn)[6]。圖中1（a）是一個(gè)基本的原模圖，它由4個(gè)變量節(jié)點(diǎn)，3個(gè)校驗(yàn)節(jié)點(diǎn)和8條邊組成。此時(shí)原模圖校驗(yàn)矩陣Hs可以表示為

當(dāng)原模圖復(fù)制三次之后（如圖1（b）所示），此時(shí)得到的校驗(yàn)矩陣Hm表示為

其中I表示為3階單位矩陣，0表示三階全零矩陣。最后經(jīng)過(guò)節(jié)點(diǎn)置換后，可以得到一個(gè)派生圖（如圖1（c）所示）。對(duì)同類(lèi)節(jié)點(diǎn)邊置換相當(dāng)于在矩陣中的單位矩陣Hm進(jìn)行列置換，因此在式（2）的基礎(chǔ)上，派生圖的校驗(yàn)矩陣[7]可以表示為

其中，E1，1…，E3，4為三階置換矩陣。H就是最終原模圖LDPC碼的校驗(yàn)矩陣。

由式（3）我們可以知道，使用原模圖設(shè)計(jì)LDPC碼的難點(diǎn)就是設(shè)計(jì)置換矩陣。一般來(lái)說(shuō)，置換矩陣都會(huì)被設(shè)計(jì)為一個(gè)循環(huán)矩陣，這樣在存儲(chǔ)校驗(yàn)矩陣的時(shí)候就只需要存儲(chǔ)每一個(gè)置換矩陣的多項(xiàng)式，大大的降低了LDPC碼的編碼復(fù)雜度和譯碼復(fù)雜度。

2 CCSDS標(biāo)準(zhǔn)下的LDPC碼

CCSDS發(fā)布的131.1-O-2標(biāo)準(zhǔn)中，給出了兩種方法來(lái)設(shè)計(jì)LDPC碼，其中對(duì)于應(yīng)用于深空通信的LDPC碼，CCSDS標(biāo)準(zhǔn)使用的就是原模圖構(gòu)造方法[8]。在該標(biāo)準(zhǔn)中，一共定義了9種適用于深空的LDPC碼，碼長(zhǎng)為1024、4096、16384，碼率r為1/2、2/3、4/5[9]，這9種碼的參數(shù)如表1所示。

表1 碼率與碼長(zhǎng)

下面以1/2碼率為例來(lái)說(shuō)明。當(dāng)碼率r=1/2時(shí)，校驗(yàn)矩陣H1/2，由3×5個(gè)子循環(huán)矩陣構(gòu)成：

在（4）式中，∏1到∏8是M×M維置換矩陣。0M為M×M維全零矩陣，IM為M×M維單位矩陣，M的取值與（n，k）相關(guān)。

CCSDS標(biāo)準(zhǔn)中定義置換矩陣∏k，k∈{1，2，…，8}中的第i行中的非零項(xiàng)的列序號(hào)為πk（i）表示，其中i∈1，…，M-1}。則πk（i）的計(jì)算公式見(jiàn)式（5）:

最終我們可以求得原模圖LDPC碼的校驗(yàn)矩陣。接下來(lái)可以根據(jù)校驗(yàn)矩陣求得生成矩陣，最后使用生成矩陣完成編碼。由于校驗(yàn)矩陣H是一個(gè)準(zhǔn)循環(huán)矩陣，且生成矩陣G是校驗(yàn)矩陣H的逆矩陣，則生成矩陣G是分塊循環(huán)矩陣[10]。

具體的編碼方法如下[11]。

1）將校驗(yàn)矩陣H表示為H=[Q P]，其中P是H的后3M列，Q是H的前MK列。

2）求解W=（P-1Q）T，其中矩陣運(yùn)算在GF（2）中進(jìn)行。

3）得到生成矩陣G=[IMKW]，其中IMK是單位矩陣，W是稠密循環(huán)矩陣，大小可分塊表示為：

3 編碼電路FPGA實(shí)現(xiàn)

CCSDS標(biāo)準(zhǔn)將原模圖構(gòu)造的LDPC碼推薦為深空通信的信道編碼方式，在航天應(yīng)用中要求硬件資源消耗少，算法穩(wěn)定性高。針對(duì)以上要求，本文設(shè)計(jì)了如圖2的LDPC編碼器，對(duì)LDPC碼進(jìn)行分組，使用末位補(bǔ)零的方法提高編碼穩(wěn)定性，并將1/2、2/3、4/5 3種碼率使用同一套觸發(fā)器，極大的減少了資源消耗率。同時(shí)編碼后進(jìn)行擾碼和添加幀頭[12]的操作，極大的方便在實(shí)際空間通信系統(tǒng)中的使用。

圖2 編碼器設(shè)計(jì)

在CCSDS標(biāo)準(zhǔn)中我們選擇了碼長(zhǎng)為4096位的信息幀來(lái)做完成LDPC的編碼，首先我們需要將數(shù)據(jù)流進(jìn)行分組，每一幀碼長(zhǎng)為4096位。針對(duì)1/2、2/ 3、4/5這三種碼率，經(jīng)過(guò)LDPC碼編碼器之后分別得到碼長(zhǎng)為8192位、6144位、5120位。編碼器的輸入位數(shù)和輸出位數(shù)不一致，這樣容易造成內(nèi)存泄露。為了解決這個(gè)問(wèn)題，我們采用累加器來(lái)設(shè)計(jì)編碼器的核心結(jié)構(gòu)。當(dāng)信息碼字為0時(shí)，不影響累加器的結(jié)果。因此我們?cè)趯?duì)碼流進(jìn)行分組時(shí)，采用末位補(bǔ)零的方法，針對(duì)種碼率，將4096位信息位分別補(bǔ)零成為8192位、6144位、5120位，這樣編碼器的輸入位數(shù)和輸出位數(shù)一致，能更好的保障編碼器的穩(wěn)定性。

同時(shí)，由于LDPC碼的生成矩陣比較大[13]，如果直接存儲(chǔ)，會(huì)使用很多資源。因此，根據(jù)生成矩陣的塊循環(huán)特性，使用移位寄存器來(lái)設(shè)計(jì)編碼器。生成矩陣是由一個(gè)單位矩陣和一個(gè)稠密循環(huán)矩陣構(gòu)成。在編碼器設(shè)計(jì)中，核心是完成信息序列和矩陣乘法即可。由上節(jié)中的格式可知，每行有8個(gè)子循環(huán)矩陣，我們只需要存儲(chǔ)每個(gè)循環(huán)矩陣的第一行，通過(guò)移位的方法就可以完成乘法運(yùn)算，這極大的減少了所需存儲(chǔ)空間。將這8個(gè)循環(huán)移位寄存器并行設(shè)計(jì)，通過(guò)累加器來(lái)存儲(chǔ)運(yùn)算結(jié)果，既節(jié)省了資源，又提高了吞吐量。具體編碼方法見(jiàn)圖3所示。

圖3 使用反饋移位寄存器的準(zhǔn)循環(huán)編碼器

文中的LDPC碼編碼器設(shè)計(jì)了1/2、2/3、4/5這3種碼率，為了方便在航天應(yīng)用的具體使用，我們將這3種碼率的LDPC碼使用一套觸發(fā)器，以1/2碼率的LDPC碼編碼所需的觸發(fā)器長(zhǎng)度來(lái)設(shè)計(jì)編碼器，在FPGA實(shí)現(xiàn)時(shí)能更好的節(jié)省資源。根據(jù)上圖的編碼器結(jié)構(gòu)，我們?cè)赬ilinx公司的xc4vsx55-12ff1148上實(shí)現(xiàn)了碼長(zhǎng)為4096，碼率為1/2、3/4、4/5的LDPC編碼。表4是所消耗的硬件資源，從表中我們看到所占用的硬件資源相對(duì)較少，說(shuō)明該編碼器實(shí)現(xiàn)復(fù)雜度低，硬件資源消耗少。

表2 編碼器消耗的資源

4 仿真驗(yàn)證

為了驗(yàn)證編碼硬件實(shí)現(xiàn)的正確性，我們把編碼后的碼字序列，使用BPSK調(diào)制，加上高斯白噪聲，使用Matlab仿真譯碼，譯碼方法選用置信度傳播算法[14]，也稱(chēng)為和積算法，最大迭代次數(shù)設(shè)置為100。我們一般使用誤比特率和誤幀率來(lái)衡量信道編碼性能[15]。圖4和圖5分別是碼長(zhǎng)為4096，碼率為4/5的LDPC碼的誤比特率和誤幀率的性能曲線。在 CCSDS標(biāo)準(zhǔn)中，也給出了相應(yīng)的參考性能曲線，由此我們可知編碼算法和硬件實(shí)現(xiàn)都是正確的。從下面兩幅圖中，我們也可以看出CCSDS標(biāo)準(zhǔn)下的LDPC碼性能優(yōu)越，在誤碼率為10-5時(shí)，所需信噪比僅為3.35 dB。

圖4 誤比特率性能曲線

圖5 誤幀率性能曲線

5 結(jié) 論

文中主要討論了CCSDS標(biāo)準(zhǔn)中，使用原模圖構(gòu)造的低碼率LDPC的編碼方法和FPGA[16-17]的硬件實(shí)現(xiàn)。通過(guò)末位補(bǔ)零保障編碼器的穩(wěn)定性，3種碼率使用一套觸發(fā)器以更好的節(jié)省硬件資源，從實(shí)驗(yàn)結(jié)果可以看出，文中設(shè)計(jì)的編碼器具有高效的編碼增益性能，吞吐量高，糾錯(cuò)能力很強(qiáng)，消耗硬件資源少，非常適用于深空通信。

[1]R.G.Gallager.Low-Density Parity Check Codes [M].Cambridge，MA:MIT Press，1963.

[2]ETSI EN 302 307 V1.1.1,Digital Video BroadcastingSatelliteSecondGeneration[S].European，2004.

[3]CCSDS 131.1-0-2.Low density parity check codes for use in near-Earth and deep space applications [S].Washington DC,USA,2007.

[4]D.J.C.MacKay,R.M.Neal.Near Shannon limit performance of low density parity check codes[J].Electronics Letters,1997,33（6）:455-457.

[5]J.Thorpe.Low-density parity-check LDPC codes constructed from protographs[C]//IPN Progress Report,2003.

[6]D.Divsalar,S.Dolinar,C.Jones.Low-rate LDPC codes with simple protograph structure[J].IEEE ISIT[C].Adelaide,Australia,2005（9）:1622-1626.

[7]肖揚(yáng).Turbo與LDPC編解碼及其應(yīng)用[M].北京:人民郵電出版社,2011.

[8]Divsalar D，Dolinar S，Jones C.Construction of protographLDPC codeswith linearminimum distance[J].IEEE ISIT[C]//Seattle,USA,2006[T]:664-668.

[9]Abbasfar A，Divsalar D，Yao K.Accumulate Repeat Accumulate Codes[J].In Proceedings of the IEEE，2004（4）:509-513.

[10]Divsalar D，Dolinar S，Thorpe J，et al.Construction LDPC codes from simple loop-free encoding modules[J].In Proceedings of the IEEE International Symposium on Information Theory,2006（6）:664-668.

[11]李忠亮,夏國(guó)江.原模圖LDPC碼的準(zhǔn)循環(huán)擴(kuò)展和編碼算法[J].空間科學(xué)學(xué)報(bào)，2011，31（3）:406-411.

[12]CCSDS.1310-B-2.TM Synchronization and channel coding[S].Washington D.C.,USA,2011.

[13]Y.Kou,S Lin,M Fossorier.Low density parity check codes based on finite geometries:a rediscovery and new results[J].IEEE Transactions Information Theory，2001，47（10）:2711-2736.

[14]J.H.Chen，M.P.C.Fossorier.Near optimum universal belief propagation based decoding of lowdensity Parity check codes[J].IEEE Trans.Commun，2002，50（3）:406-414.

[15]袁東風(fēng)，張海剛.LDPC碼理論與應(yīng)用[M].北京:人民郵電出版社，2008.

[16]郎寶華，單成剛，無(wú)刷直流電機(jī)的FPGA控制系統(tǒng)設(shè)計(jì)及仿真 [J].西安工業(yè)大學(xué)學(xué)報(bào)，2014（2）：160-166.

[17]嚴(yán)明，李斌康，郭明安，等.高速光電探測(cè)器陣列實(shí)時(shí)信號(hào)處理系統(tǒng) [J].現(xiàn)代應(yīng)用物理，2014（4）：316-321.

An encoder architecture for low-rate LDPC codes based CCSDS standard

GONG Yang-yang1，2，AN Jun-she1，ZHU Yan1
（1.National Space Science Center of the Chinese Academy of Science Department of Space Technology，Beijing 100190，China；2.University of Chinese Academy of Sciences，Beijing 100190，China）

An encoder architecture is proposed to implement 1/2，2/3，4/5 rates LDPC codes based on the Consultative Committee for Space Data Systems standards.According to block cycle characteristics of the generation matrix，we used a feedback shift register design this encoder for saving hardware cost.And we add zeros at the end of information to ensure the stability of the LDPC code encoder.

LDPC codes；protograph；CCSDS standard；feedback shift registers；deep-space application

TN911.22

：A

：1674－6236（2017）05-0057-04

2016-03-15稿件編號(hào)：201603191

龔楊陽(yáng)（1991—），女，江西上饒人，碩士研究生。研究方向：數(shù)字信號(hào)與圖像處理。