一種結構化LDPC碼的部分并行譯碼器設計

蘇悅 王建輝

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

一種結構化LDPC碼的部分并行譯碼器設計

蘇悅1王建輝2

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

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

CCSDS標準；LDPC碼；部分并行譯碼器

1 引言

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

本文提出了一種針對CCSDS推薦的用于深空通信的1/2碼率LDPC碼的譯碼器結構，該譯碼器能夠實現并行度較高的部分并行譯碼，便于工程實現時在譯碼時延和實現復雜度之間折中。本文提出的譯碼器結構可為譯碼器的工程實現提供更大的靈活性。

2 AR4JA碼

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

(1)

圖1 LDPC碼的Tanner圖表示

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

(2)

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

(3)

式中：θw和φw(·)為CCSDS標準中給出的確定分塊矩陣相對于單位矩陣的循環右移值的兩個參數，其值可通過查表得到，當M的值為512時，θw和φw(·)的值如表1所示。

表1 AR4JA LDPC碼參數表

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

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

(4)

由上式可得三個校驗位矢量的表達式為

(5)

(6)

(7)

由上述表達式可求得校驗位，完成編碼后校驗位矢量p3被打孔。

4 AR4JA碼的部分并行譯碼器設計

4.1校驗矩陣的拆分

CCSDS中的AR4JA碼的校驗矩陣由三行五列維數為M×M的子矩陣組成，若每個非零子矩陣的每行、每列均只包含一個‘1’，則將校驗節點和變量節點存儲器按子矩陣的行和列進行適當劃分后，可以實行同時對M個變量節點或校驗節點的更新。將AR4JA碼的校驗矩陣拆分為3個矩陣的和后，可確保每個非零子矩陣的每行、每列均只包含一個‘1’。拆分后的矩陣如下式所示，每個矩陣均由M×M的子矩陣構成，且每個非零子矩陣的每行、每列均只包含一個‘1’。設計譯碼器時，分別按照3個矩陣讀入校驗節點或變量節點軟信息可實現部分并行譯碼。

(8)

(9)

(10)

4.2部分并行譯碼器結構

本文譯碼算法采用傳統的歸一化最小和算法，譯碼器工作時逐個更新校驗節點和變量節點，每次譯碼的最大迭代次數為100次。

最小和算法的計算步驟如下：

1)初始化

(11)

(12)

2)校驗節點更新

(13)

式中：λ為歸一化系數。

3)變量節點更新

(14)

4)l次迭代后進行檢測

若輸出結果滿足校驗矩陣，則輸出信息位

(15)

將校驗矩陣拆分為3個矩陣的和后，分別按照3個矩陣的結構讀取變量節點和校驗節點軟信息可以實現部分并行譯碼，但讀完整個校驗矩陣需要3次讀取過程。若同時更新的節點數量為M1變量節點與校驗節點軟信息存儲結構如下：與同一個子矩陣的第i個M1列對應的變量節點軟信息分別存儲在M1個不同的存儲器中，與同一個子矩陣的第i個M1行對應的校驗節點軟信息分別存儲在M1個不同的存儲器中。為了便于實現，設M1為M的因子，M的值為512時，M1可取的值為：20、21、22、23、24、25、26、27、28、29。可根據對譯碼時延的要求選擇譯碼器部分并行的倍數。每個變量節點軟信息存儲器的大小為5M/M1，每個校驗節點軟信息存儲器的大小為3M/M1。變量節點和校驗節點軟信息存儲器的數量均為M1個。部分并行譯碼器的結構如圖2所示。

采用本文提出的校驗矩陣拆分方法將CCSDS中的AR4JA碼校驗矩陣分解為3個矩陣的和后，每個分解后的矩陣中包含的非零子矩陣的列重均為1。采用常規準循環譯碼器的軟信息存儲結構，分別按照分解后的3個矩陣讀取信息時，不會存在寄存器的訪問沖突，可以實現部分并行讀寫操作。

圖2 部分并行譯碼器結構圖

5 結束語

CCSDS推薦的LDPC碼適用于衛星通信等領域，該碼具有準循環結構，其校驗矩陣由循環矩陣陣列構成，這為譯碼器的設計提供了更大的靈活性。但CCSDS標準中給出的LDPC碼校驗矩陣中，非零子矩陣的列重不同，這為部分并行譯碼器的設計帶來困難，若直接套用常規的部分并行譯碼器結構，將使得列重不為1的子矩陣對應的軟信息不能同時更新。本文通過矩陣拆分實現部分并行譯碼的方法，解決了分塊矩陣列重不同時部分并行譯碼器難以實現的問題。

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

蘇悅，女，碩士，工程師，從事北斗導航設備整機研發與軟件研制。Email：suyue@beiyun.cc。

TN911.22

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