龔楊陽，安軍社，朱 巖

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

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

龔楊陽1，2，安軍社1，朱 巖1

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

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

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

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

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

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

1 原模圖LDPC碼

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

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

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

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

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

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

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

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

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

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

表1 碼率與碼長

下面以1/2碼率為例來說明。當(dāng)碼率r=1/2時，校驗矩陣H1/2，由3×5個子循環(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行中的非零項的列序號為πk（i）表示，其中i∈1，…，M-1}。則πk（i）的計算公式見式（5）:

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

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

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

2）求解W=（P-1Q）T，其中矩陣運算在GF（2）中進行。

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

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

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

圖2 編碼器設(shè)計

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

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

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

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

表2 編碼器消耗的資源

4 仿真驗證

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

圖4 誤比特率性能曲線

圖5 誤幀率性能曲線

5 結(jié) 論

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

[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]肖揚.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]李忠亮,夏國江.原模圖LDPC碼的準(zhǔn)循環(huán)擴展和編碼算法[J].空間科學(xué)學(xué)報，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]郎寶華，單成剛，無刷直流電機的FPGA控制系統(tǒng)設(shè)計及仿真 [J].西安工業(yè)大學(xué)學(xué)報，2014（2）：160-166.

[17]嚴(yán)明，李斌康，郭明安，等.高速光電探測器陣列實時信號處理系統(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稿件編號：201603191

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