一組高效LDPC碼空間通信方案設計與實現

馬明曉 ， 安軍社

（1.中國科學院 國家空間科學中心，北京 100190；2.中國科學院大學 北京 100190）

Gallager[1]于1962年首次提出基于稀疏校驗矩陣的LDPC（低密度奇偶校驗）碼，但受限于當時的硬件實現水平和譯碼理論水平，并未得到足夠的重視。20世紀90年代之后，編碼界對置信傳播算法展開廣泛研究，LDPC碼的重要性被重新發現。Mackey[2]于1999年證明在采用基于置信傳播的迭代譯碼時，LDPC碼的性能逼近香農極限，隨后LDPC碼迅速成為各種研究的熱點。

已被應用于多個領域的LDPC碼因其性能優異，為很多協議所采用，其中 CCSDS（空間數據系統咨詢委員會）于2006年和2007年分別發表了文檔號CCSDS 131.1-O-1的白皮書和文檔號CCSDS131.1-O-2的橙皮書，二者的編碼矩陣有所差別，但均為準循環碼。在2011年8月CCSDS發表了文檔號CCSDS 131.0-B-2的藍皮書中，確定了一套分別適用于近地和深空通信的編碼標準協議。這一系列協議都預示著LDPC碼在未來的空間通信領域將扮演更為重要的角色。

文中主要結合CCSDS藍皮書推薦的（8160，7136）碼，從數學角度深入闡述基于歐氏幾何的LDPC碼的數學模型、建立過程及優異性能，提出了此類LDPC碼的普適性構造方法。同時，結合航天任務中對資源、功耗、碼速率的嚴格要求，提出適用于空間衛星通信的完備編碼方案，并使用FPGA進行了實現。

1 基于歐氏幾何的QC-LDPC碼的構造

不同LDPC碼的差異主要取決于其校驗矩陣H。QCLDPC碼可以由行列數相同的稀疏循環方陣陣列的零空間給出[3]。 若正整數 c 與 t滿足 c≤t，對于如下 c×t的 GF（2）上 b×b循環方陣陣列：

其有如下兩個結構特征：1）每個循環方陣Ai，j的重量相對于行列數b而言很小；2）Hqc中任意兩行（或列）相同位置是 1的數目不大于 1， 稱之為 “行列約束”（row-column constraint）[4]。特征1）決定了Hqc中的每個循環方陣都是稀疏矩陣，因此Hqc是稀疏矩陣。特征2）行列約束保證了Hqc任意一個子陣的4個角上不能同時為1。于是Hqc的零空間定義了長度n=tb的QC-LDPC碼Cqc，其Tanner圖不含有長度為4的環，圍長至少為6[5]。

而對于定義在GF（2）上的m維歐氏幾何空間EG（3，23），其共有（2ms-1）/（2s-1）個 1 維平行子空間集合，其中每個平行子空間集合由2（m-1）s條平行線構成。我們可以利用歐式空間上1維平行子空間集合構造QC-LDPC碼的校驗矩陣，進而構造出生成矩陣，建立QC-LDPC碼。

1.1 校驗矩陣H的建立

考慮定義在 GF（23）上的 3 維歐式空間 EG（3，23），該空間共含有512個點和4 672條線，每條線由8個點組成；其中，73條線通過空間原點，剩下的4 599條線不通過原點。

定義EG（3，23）上一條不經過原點的線L[6]的關聯向量為vL=（v1，v2，…，v511），其中，vL中的每一個元素與中除原點以外的點一一對應。EG（3，23）上不通過原點的4 599條線的關聯向量可以分為 9個循環族 Q1，Q2，Λ，Q9，其中每個族含有 511個關聯向量。每個族內的關聯向量可以由其中的任意一個關聯向量循環移位得到。 對于每個族 Qi（1≤i≤9），以 Qi中的關聯向量為行，可以得到一個 511×511的循環方陣 Z1，Z2，…，Z9。這樣便產生了9個行重與列重均為8的511×511循環方陣。由于歐氏幾何中的兩條線要么平行要么相交于一點，故它們的關聯向量中相同位置是1的數目不大于1。由于Z1，Z2，…，Z9中的各行與各列均為 EG（3，23）中線的關聯向量，因此循環方陣 Z1，Z2，…，Z9滿足成對行列約束，即兩個不同的循環方Zi陣Zj與，按行排列與按列排列均滿足行列約束。

對于 1≤i≤9，令fi為第 i個循環方陣Zi的第一列，將 fi分裂為 兩個長度 相同的新 列 fi，1和 fi，2，且 fi，1和 fi，2平 分 了 fi的重量，將 fi，1和 fi，2循環下行移位 510次，分別可以得到兩個新的 511×511 循環方陣 Ai，1和 Ai，2，每個行重與列重均為 4。 由此可得循環方陣陣列=[Ai，1，Ai，2]，稱之為 Zi的列分解[5]。 對于 1≤j≤2，令 qi，j為 Ai，j的 第一行 ，將 qi，j分 裂為 兩 個長度相同的新行平分了q i，j的重量，將循環右行移位510次，分別可以得到兩個新的511×511循環方陣，每個行重與列重均為2。由此得到的循環方陣陣列稱為Ai，j的行分解[5]。 對于j=1，2，將Z*i中的循環方陣Ai，j替換為其行分解，得到一個由4個511×511的循環方陣組成的2×2陣列：

Ji稱為 Zi的陣列分解[5，7]，Ji中的所有循環方陣都是 Zi的子陣。循環方陣Z1，Z2，…，Z9的陣列分解形成了一組循環陣列J={J1，J2，…，J9}。 由于 Z1，Z2，…，Z9滿足成對行列約束，它們的子陣也一定滿足成對行列約束。因此，J中的各陣列也一定滿足成對行列約束。基于J中的循環陣列可以構造（8176，7154）LDPC碼。

（8 176，7154）碼建立在 J 的前 8 個陣列 J1，J2，…，J8的基礎之上。陣列

于是便形成了如下由511×511循環方陣構成的2×16陣列：

1.2 生成矩陣G的建立

考慮（1）中給出的校驗矩陣 Hqc，具體形式已由上面式（5）得出。 設其秩為r=cb，令矩陣

其與Hqc有著相同的秩cb，假設 Hqc的前（t-c）b列對應于（t-c）b個信息位，則我們需要構造Cqc的生成矩陣具有如下結構：

其中，I為b×b單位矩陣，O為b×b全零矩陣且對于 1≤i≤t-c 及 1≤j≤c，Gi，j為 b×b 循環方陣。 這種形式的生成矩陣Gqc稱為系統循環形式（SCform），由左側的單位矩陣It-c，b和右側矩陣P構成。P為由b×b循環方陣組成的（t-c）×c陣列。這種結構允許使用簡單的移位寄存器對QC-LDPC編碼進行實現。

Gqc成為Cqc的生成矩陣的充分必要條件為[O]，其中[O]為 cb×（t-c）b 的全零矩陣。 對于 1≤i≤t-c 及 1≤j≤c，令 gi，j為循 環 方 陣 Gi，j的 首 行 （或 首 列 ），一 旦 gi，j確 定 ，則 Gi，j可通過由 gi，j循環移 位的方式 得 到 ， 故稱 gi，j為 Gi，j的生 成 矢量。 于是，只要 Gqc中各個 Gi，j的首行（或首列）確定了，Gqc便能完全確定。

令各含有 b 個元素的向量 u=（1，0，…，0）O，=（0，0，…，0），對于 1≤i≤t-c，子陣 Gi的首行為

其中，u位于gi的第i個位置上。若Gqc為Cqc的生成矩陣則對于 1≤i≤t-c，必有=0。 令 zi=（gi，1，gi，2，…，gi，c），那么由=0 可得如下方程：

因為D為滿秩的方陣，故D非奇異且有逆矩陣D-1，則由（9）式可得：

解（10）式，對于 1≤i≤t-c 可以得到 z1，z2，…，zt-c，由 z1，z2，…，zt-c進一步可以得到Gqc中個循環方陣的首行，進而Gqc可以被完全建立。

2 性能測試

對于由以上方法產生的（8 176，7 154）非規則QC-LDPC碼[8]，使用Matlab工具進行譯碼測試其誤碼性能，結果如下面兩幅圖所示。

圖1 誤比特率性能Fig.1 Bit-error-rate performance

圖2 誤分組率性能Fig.2 Frame-error-rate performance

以上結果均通過置信度傳播算法進行80次迭代譯碼得出。從圖1和圖2可以看出，基于歐氏幾何EG（3，23）構造的（8176，7154）碼在編碼增益、誤碼平臺等方面有著優異表現。

3 QC-LDPC碼的FPGA實現及航天應用方案

當今的飛行器和地面系統只能處理32-bit倍數結構的數據，顯然（8176，7154）碼并不滿足這個條件。為了在實際的空間通信系統中獲得應用，需將（8176，7154）碼縮短和修整為（8160，7136）碼并在編碼時進行擾碼、添加幀頭[9]等操作，之后才能進入調制等之后的環節。

針對以上要求，本文設計了如圖3所示的整合LDPC編碼器，將數據分組、LDPC編碼、擾碼、添加幀頭等操作整合到一個編碼器中實現，極大地提高了FPGA資源的利用率，這一點在航天任務中尤為重要。

圖3 編碼器設計圖Fig.3 The encoder design

圖4 移位寄存累加編碼單元Fig.4 Shift-register-adder-accumulator

3.1 編碼電路原理

根據Gqc中P矩陣的循環結構設計編碼電路單元。設a=（a1，a2，…，a（t-c）b）為待編碼的信息序列，將此序列分割為（t-c）個等長的序列 a=（a1，a2，…，at-c），其中，對 于1≤i≤t-c，ai=（a（i-1）b+1，a（i-1）b+2，…，aib）。 信息序列 a 所對應的碼字為 v=aGqc且 v 為系統形式 v=（a，p1，p2，…，pc），其中對于 1≤j≤c，pj=（pj，1，pj，2，…，pj，b）為一段b位的校驗位序列。對于1≤j≤c，由v=aGqc可知：

由（11）（12）可知，隨著信息序列a逐位進入編碼器，第j段校驗位序列pj可以逐步的算出。對于1≤k≤t-c，在第k步， 累加和 sk，j=a1G1，j+a2G2，j+…+akGk產生并且存儲于寄存器中。在第 k+1 步，部分和 ak+1Gk+1由（12）式算出并累加到 sk，j以形成下一個累加和 sk+1，j。 在（t-c）步結束后，由累加和 st-c，j便可得到第j段校驗位pj。

基于上述編碼過程，采用如圖4所示的移位寄存累加電路單元（shift-register-adder-accumulator， SRAA）[4]。 此移位寄存累加編碼單元中包括一個b比特的寄存器A，用于存儲異或運算的結果；一個b比特的循環移位寄存器B，用于存儲與生成循環子矩陣的行向量；b個兩輸入的與門和b個兩輸入的異或門。

3.2 串行編碼方案

對于串行編碼電路，其原理就是不斷輸入信息位，同時逐步計算校驗位，信息位完全輸入后，最終校驗位便也得到。由此串行計算方式得到所有的校驗位 p=（p1，p2，…，pc），共需c組SRAA電路，其原理圖如圖5所示。

對于由（8176，7154）碼縮短所得的（8160，7136）碼，采用Xilinx Virtex-4 FPGA進行調試，最高碼速率可達210 Mbps以上，能夠滿足空間通信要求。

圖5 串行編碼電路Fig.5 Serial-encoding circuit

圖6 并行編碼電路Fig.6 Parallel-encoding circuit

3.3 并行編碼方案

為滿足圖像傳輸等高速數據通信場合，還可用SRAA電路構建并行編碼器。其基本思想是同時用（t-c）個SRAA電路完成式（17）中（t-c）個被加項的計算，如此只需b個時鐘周期就能得到pj。用c組這樣的并行SRAA電路，便能同時計算所有校驗位，并行編碼器結構圖如圖6所示。

并行計算會用到（t-c）個不同位置上的輸入信息，因此需一組信息元完全輸入后方能開始編碼。另外，還需要一個碼字的延遲時間方能得到連續平穩的輸出碼流，因此并行編碼器的輸出延遲為兩個碼字。經硬件測試知并行編碼器最高輸出碼速率可達2 Gbps左右。與串行編碼器相比，其速率的提高與所耗費的硬件資源是成比例的。為在速度與硬件資源之間取得折中，還可以設計并行路數為1與（t-c）之間的部分并行編碼電路。

4 結束語

文中對一類基于歐氏幾何的QC-LDPC碼的數學基礎及性能進行了分析，提出了該類碼的普適性構造方法。并結合CCSDS 所推薦的（8 176，7 154）碼和（8 160，7 136）碼，對此類QC-LDPC碼的硬件實現展開研究，采用SRAA電路單元分別設計了串、并行編碼方案，并使用FPGA進行了實現，達到了很高的碼速率，具有相當高的應用價值，適用于資源、功耗、碼速率要求嚴格的空間通信系統。

[1]Gallager R G.Low density parity check codes[J].IRE Transactions on Information Theory，1962，8（1）:21-28

[2]Mackay D J C.Good Error-Correcting Codes Based on Very Sparce Matrice[J].IEEE Transactions on Information Theory，1999，45（2）:399-431.

[3]J.Xu， L.Chen，L.-Q.Zeng， L.Lan， S.Lin.Construction of low density parity-check codes by superposition [J].IEEE Transactions on Communications， 2005，53（2）:243-251

[4]Li Z， Chen L， Zeng L， S.Lin.Efficient Encoding of Quasi-Cyclic Low-Density Parity-Check Codes[J].IEEE Transactions on Communications，2006，54（1）:71-81.

[5]Yu K，Lin S，Fossorier M.Low density parity check codes based on finite geometries:A discovery and new results[J].IEEE Transactions on Information Theory，2001，47 （11）:2711-2736.

[6]Lin S，Daniel J.Costello J.Error Control Coding:Fundamentals and Applications， 2nd ed.[M].Upper Saddle River， NJ:Prentice-Hall，2004.

[7]L.Chen，J.Xu，S.Lin.Near Shannon Limit Quasi-Cyclic Low-Density Parity-Check Codes [J].IEEE Transactions on Communications，2004，52（7）:1038-1042.

[8]CCSDS 131.1-O-2.Low density parity check codes for use in near-earth and deep space applications[S].Washington D.C.，2007.

[9]CCSDS 131.0-B-2.TM synchronization and channel coding[S].Washington D.C.，2011.