蘇悅 王建輝

(1 湖南北云科技有限公司, 長(zhǎng)沙 410073)(2 國防科技大學(xué), 長(zhǎng)沙 410073)

一種結(jié)構(gòu)化LDPC碼的部分并行譯碼器設(shè)計(jì)

蘇悅1王建輝2

(1 湖南北云科技有限公司, 長(zhǎng)沙 410073)(2 國防科技大學(xué), 長(zhǎng)沙 410073)

CCSDS標(biāo)準(zhǔn)給出的低密度奇偶校驗(yàn)碼(Low Density Parity Check，LDPC)其子矩陣具有不同的列重，這給部分并行譯碼器的設(shè)計(jì)帶來困難。本文針對(duì)如何高效實(shí)現(xiàn)CCSDS中LDPC碼部分并行譯碼的問題，根據(jù)該類碼的準(zhǔn)循環(huán)特性，將碼的校驗(yàn)矩陣分解成3個(gè)矩陣的和，提出了一種能夠部分并行譯碼的譯碼器結(jié)構(gòu)。利用本文提出的方法設(shè)計(jì)譯碼器時(shí)可以在譯碼時(shí)延和譯碼復(fù)雜度之間進(jìn)行折中。

CCSDS標(biāo)準(zhǔn)；LDPC碼；部分并行譯碼器

1 引言

低密度奇偶校驗(yàn)碼(Low Density Parity Check，LDPC)由Gallager于1962年提出[1]，但受限于當(dāng)時(shí)的技術(shù)條件并沒有引起人們的重視。直到1996年，Mackay等人重新發(fā)現(xiàn)LDPC碼的優(yōu)異性能[2]，該類碼才受到研究人員的關(guān)注，并得到越來越廣泛的應(yīng)用。LDPC碼按校驗(yàn)矩陣的構(gòu)造方法可分為隨機(jī)構(gòu)造的LDPC碼和結(jié)構(gòu)化LDPC碼。比特填充(Bit-filling)[3]算法和PEG算法[4]均為隨機(jī)LDPC碼構(gòu)造方法。隨機(jī)LDPC碼一般而言性能優(yōu)異，但編譯碼復(fù)雜度較大。結(jié)構(gòu)化LDPC碼構(gòu)造法包括有限幾何構(gòu)造法[4-5]、基于循環(huán)置換矩陣的構(gòu)造法[6]、原模圖法[7]等，設(shè)計(jì)優(yōu)良的結(jié)構(gòu)化LDPC碼不但性能優(yōu)異，而且編譯碼復(fù)雜度低，實(shí)用性強(qiáng)。近年來，LDPC碼得到了廣泛的應(yīng)用，空間數(shù)據(jù)系統(tǒng)咨詢委員會(huì)(CCSDS)已經(jīng)將一類LDPC碼，即四次重復(fù)鋸齒累積 (Accumulate Repeat-4 Jagged Accumulate，AR4JA)碼[8-9]推薦為深空通信和近地通信的標(biāo)準(zhǔn)。該類碼具有準(zhǔn)循環(huán)結(jié)構(gòu)，編譯碼器設(shè)計(jì)比隨機(jī)構(gòu)造的碼簡(jiǎn)單。但該類碼具有多種不同列重的子矩陣，不利于譯碼器的工程實(shí)現(xiàn)。

本文提出了一種針對(duì)CCSDS推薦的用于深空通信的1/2碼率LDPC碼的譯碼器結(jié)構(gòu)，該譯碼器能夠?qū)崿F(xiàn)并行度較高的部分并行譯碼，便于工程實(shí)現(xiàn)時(shí)在譯碼時(shí)延和實(shí)現(xiàn)復(fù)雜度之間折中。本文提出的譯碼器結(jié)構(gòu)可為譯碼器的工程實(shí)現(xiàn)提供更大的靈活性。

2 AR4JA碼

LDPC碼為線性分組碼，可以由校驗(yàn)矩陣表示。1981年，Tanner就已經(jīng)提出線性分組碼的圖模型表示法[10]，描述了碼字比特與約束它們的校驗(yàn)和之間的對(duì)應(yīng)關(guān)系，奠定了LDPC碼和其他基于圖的碼的研究基礎(chǔ)。式(1)和圖1分別為一個(gè)LDPC碼的校驗(yàn)矩陣及其Tanner圖表示方法。Tanner圖中圓形與方形分別與校驗(yàn)矩陣的列和行一一對(duì)應(yīng)，分別稱為變量接點(diǎn)和校驗(yàn)節(jié)點(diǎn)。Tanner圖為二分圖，其頂點(diǎn)集可以劃分成兩個(gè)子集VS和VC，使得每條邊的一個(gè)端點(diǎn)在VS中，另一個(gè)端點(diǎn)在VC中，子集VS與VC中各自內(nèi)部的節(jié)點(diǎn)互不相連。假設(shè)子集VS中的節(jié)點(diǎn)對(duì)應(yīng)碼字比特的n個(gè)變量節(jié)點(diǎn)(圓形)集合(s1,s1…sn)，子集VC中的節(jié)點(diǎn)對(duì)應(yīng)校驗(yàn)約束關(guān)系中的m個(gè)校驗(yàn)節(jié)點(diǎn)(方形)集合(c1,c2,…cm)，當(dāng)且僅當(dāng)?shù)趗個(gè)碼字比特參與了第v個(gè)奇偶校驗(yàn)約束時(shí)，變量節(jié)點(diǎn)su和校驗(yàn)節(jié)點(diǎn)cv之間才有一條邊(su,cv)相連，即Tanner圖中對(duì)應(yīng)的節(jié)點(diǎn)之間建立一條邊。在Tanner圖中定義一個(gè)節(jié)點(diǎn)度數(shù)為與此節(jié)點(diǎn)相連的邊的數(shù)量。因此，變量節(jié)點(diǎn)的度數(shù)等于包含該變量節(jié)點(diǎn)的校驗(yàn)約束關(guān)系的個(gè)數(shù)或H矩陣中對(duì)應(yīng)行的重量；校驗(yàn)節(jié)點(diǎn)的度數(shù)等于被該校驗(yàn)約束關(guān)系控制的變量節(jié)點(diǎn)的個(gè)數(shù)或H矩陣中對(duì)應(yīng)列的重量。

(1)

圖1 LDPC碼的Tanner圖表示

AR4JA碼為CCSDS中推薦用于深空和近地通信的LDPC碼，該類碼具有準(zhǔn)循環(huán)結(jié)構(gòu)，但其部分子矩陣中每一列包含‘1’的數(shù)量較多，這給部分并行譯碼器的設(shè)計(jì)帶來了困難，本文主要針對(duì)該問題展開研究。AR4JA 碼的校驗(yàn)矩陣如式(2)所示，完成編碼后與校驗(yàn)矩陣最后M列對(duì)應(yīng)的校驗(yàn)位被打孔，該碼的碼率為1/2。

(2)

式中：每個(gè)分塊矩陣均為M×M的矩陣。0M表示全零矩陣；IM表示單位矩陣。Πw(1≤w≤8)表示單位矩陣的置換矩陣，該矩陣只有在第x行第πk(x)列不為零，其他位置全為零。πk(x)的表達(dá)式為

(3)

式中：θw和φw(·)為CCSDS標(biāo)準(zhǔn)中給出的確定分塊矩陣相對(duì)于單位矩陣的循環(huán)右移值的兩個(gè)參數(shù)，其值可通過查表得到，當(dāng)M的值為512時(shí)，θw和φw(·)的值如表1所示。

表1 AR4JA LDPC碼參數(shù)表

3 CCSDS中1/2碼率LDPC碼的編碼器

編碼之前的信息位矢量記為[s1s2]，s1和s2分別為信息位的前M位和后M位。記與校驗(yàn)矩陣的后三列子矩陣對(duì)應(yīng)的校驗(yàn)位矢量分別為p1、p2和p3，由碼字和校驗(yàn)矩陣的關(guān)系可得

(4)

由上式可得三個(gè)校驗(yàn)位矢量的表達(dá)式為

(5)

(6)

(7)

由上述表達(dá)式可求得校驗(yàn)位，完成編碼后校驗(yàn)位矢量p3被打孔。

4 AR4JA碼的部分并行譯碼器設(shè)計(jì)

4.1校驗(yàn)矩陣的拆分

CCSDS中的AR4JA碼的校驗(yàn)矩陣由三行五列維數(shù)為M×M的子矩陣組成，若每個(gè)非零子矩陣的每行、每列均只包含一個(gè)‘1’，則將校驗(yàn)節(jié)點(diǎn)和變量節(jié)點(diǎn)存儲(chǔ)器按子矩陣的行和列進(jìn)行適當(dāng)劃分后，可以實(shí)行同時(shí)對(duì)M個(gè)變量節(jié)點(diǎn)或校驗(yàn)節(jié)點(diǎn)的更新。將AR4JA碼的校驗(yàn)矩陣拆分為3個(gè)矩陣的和后，可確保每個(gè)非零子矩陣的每行、每列均只包含一個(gè)‘1’。拆分后的矩陣如下式所示，每個(gè)矩陣均由M×M的子矩陣構(gòu)成，且每個(gè)非零子矩陣的每行、每列均只包含一個(gè)‘1’。設(shè)計(jì)譯碼器時(shí)，分別按照3個(gè)矩陣讀入校驗(yàn)節(jié)點(diǎn)或變量節(jié)點(diǎn)軟信息可實(shí)現(xiàn)部分并行譯碼。

(8)

(9)

(10)

4.2部分并行譯碼器結(jié)構(gòu)

本文譯碼算法采用傳統(tǒng)的歸一化最小和算法，譯碼器工作時(shí)逐個(gè)更新校驗(yàn)節(jié)點(diǎn)和變量節(jié)點(diǎn)，每次譯碼的最大迭代次數(shù)為100次。

最小和算法的計(jì)算步驟如下：

1)初始化

(11)

(12)

2)校驗(yàn)節(jié)點(diǎn)更新

(13)

式中：λ為歸一化系數(shù)。

3)變量節(jié)點(diǎn)更新

(14)

4)l次迭代后進(jìn)行檢測(cè)

若輸出結(jié)果滿足校驗(yàn)矩陣，則輸出信息位

(15)

將校驗(yàn)矩陣拆分為3個(gè)矩陣的和后，分別按照3個(gè)矩陣的結(jié)構(gòu)讀取變量節(jié)點(diǎn)和校驗(yàn)節(jié)點(diǎn)軟信息可以實(shí)現(xiàn)部分并行譯碼，但讀完整個(gè)校驗(yàn)矩陣需要3次讀取過程。若同時(shí)更新的節(jié)點(diǎn)數(shù)量為M1變量節(jié)點(diǎn)與校驗(yàn)節(jié)點(diǎn)軟信息存儲(chǔ)結(jié)構(gòu)如下：與同一個(gè)子矩陣的第i個(gè)M1列對(duì)應(yīng)的變量節(jié)點(diǎn)軟信息分別存儲(chǔ)在M1個(gè)不同的存儲(chǔ)器中，與同一個(gè)子矩陣的第i個(gè)M1行對(duì)應(yīng)的校驗(yàn)節(jié)點(diǎn)軟信息分別存儲(chǔ)在M1個(gè)不同的存儲(chǔ)器中。為了便于實(shí)現(xiàn)，設(shè)M1為M的因子，M的值為512時(shí)，M1可取的值為：20、21、22、23、24、25、26、27、28、29?？筛鶕?jù)對(duì)譯碼時(shí)延的要求選擇譯碼器部分并行的倍數(shù)。每個(gè)變量節(jié)點(diǎn)軟信息存儲(chǔ)器的大小為5M/M1，每個(gè)校驗(yàn)節(jié)點(diǎn)軟信息存儲(chǔ)器的大小為3M/M1。變量節(jié)點(diǎn)和校驗(yàn)節(jié)點(diǎn)軟信息存儲(chǔ)器的數(shù)量均為M1個(gè)。部分并行譯碼器的結(jié)構(gòu)如圖2所示。

采用本文提出的校驗(yàn)矩陣拆分方法將CCSDS中的AR4JA碼校驗(yàn)矩陣分解為3個(gè)矩陣的和后，每個(gè)分解后的矩陣中包含的非零子矩陣的列重均為1。采用常規(guī)準(zhǔn)循環(huán)譯碼器的軟信息存儲(chǔ)結(jié)構(gòu)，分別按照分解后的3個(gè)矩陣讀取信息時(shí)，不會(huì)存在寄存器的訪問沖突，可以實(shí)現(xiàn)部分并行讀寫操作。

圖2 部分并行譯碼器結(jié)構(gòu)圖

5 結(jié)束語

CCSDS推薦的LDPC碼適用于衛(wèi)星通信等領(lǐng)域，該碼具有準(zhǔn)循環(huán)結(jié)構(gòu)，其校驗(yàn)矩陣由循環(huán)矩陣陣列構(gòu)成，這為譯碼器的設(shè)計(jì)提供了更大的靈活性。但CCSDS標(biāo)準(zhǔn)中給出的LDPC碼校驗(yàn)矩陣中，非零子矩陣的列重不同，這為部分并行譯碼器的設(shè)計(jì)帶來困難，若直接套用常規(guī)的部分并行譯碼器結(jié)構(gòu)，將使得列重不為1的子矩陣對(duì)應(yīng)的軟信息不能同時(shí)更新。本文通過矩陣拆分實(shí)現(xiàn)部分并行譯碼的方法，解決了分塊矩陣列重不同時(shí)部分并行譯碼器難以實(shí)現(xiàn)的問題。

References)

[1]R G Gallager. Low-density parity-check codes[M]. Cambridge, MA: MIT Press, 1963

[2]D J C Mackay, R M Neal. Near Shannon-limit performance of low-density parity-check codes[J]. Electron. Lett., 1996, 32(16): 1645-1646

[3]J Campello, D S Modha, S Rajagopalan. Designing LDPC codes using bit-filling[C]// IEEE International Conference on Communications. New York: IEEE, 2001:55-59

[4]Shu Lin, Daniel J, Costello Jr. Error control coding[M]. Upper Saddle River, New Jersey: Prentice Hall, 2004

[5]Kou Yu, S Lin, M P C Fossorier. Low-density parity-check codes based on finite geometries: a rediscovery and new results[J]. IEEE Trans. Inf. Theory, 2001, 47(7): 2711-2736

[6]M Fossorier. Quasi-cyclic low-density parity-check codes from circulant permutation matrices[J]. IEEE Trans. Inf. Theory, 2004, 50(8): 1788-1793

[7]Jeremy Thorpe. Low density parity check (LDPC) codes constructed from protographs[R]. Pasadena: JPL, 2003

[8]Andrews K, Divsalar D, Dolinar S. The development of turbo and LDPC codes for deep space applications[J]. IEEE special Issue on Technical Advances in Deep Space Communication and Tracking, 2007: 2142-2156

[9]Andrews K, Divsalar D, Dolinar S. Design and standardization of low-density parity-check codes for space applications[C]// SpaceOps 2008 Conference. Heidelberg: American Institute of Aeronautics and Astronautics, 2008: 1-12

[10]R M Tanner. A recursive approach to low complexity codes[J]. IEEE Trans. Inform. Theory, 1981, 27(9):533-547

(編輯：張小琳)

A Partially Parallel Decoder Design of Structured LDPC Codes

SU Yue1WANG Jianhui2

(1 Hunan Beiyun Technology Co. Ltd., Changsha 410073, China)

(2 National University of Defense Technology, Changsha 410073, China)

Some LDPC codes with different rates for deep space communication are provided in CCSDS standard. These codes have quasi-cyclic structure, and can afford high coding gain and implementation flexibility of encoder and decoder for satellite crosslink system of COMPASS. But the column weight of sub-matrices of the code are different, which makes the implementation of parallel decoder of the code difficult. Based on the quasi-cyclic characteristic, the parity check matrix of each code is decomposed into three-matrice sum, and a decoder structure which can be implemented in a partially parallel way is presented in this paper. Tradeoff can be made between decoding delay and implementation complexity with the presented method.

CCSDS standard; LDPC code; partially parallel decoder

2014-03-25；

：2014-05-07

蘇悅，女，碩士，工程師，從事北斗導(dǎo)航設(shè)備整機(jī)研發(fā)與軟件研制。Email：suyue@beiyun.cc。

TN911.22

：ADOI：10.3969/j.issn.1673-8748.2014.03.014