一組高效LDPC碼空間通信方案設(shè)計(jì)與實(shí)現(xiàn)

馬明曉 ， 安軍社

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

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

已被應(yīng)用于多個領(lǐng)域的LDPC碼因其性能優(yōu)異，為很多協(xié)議所采用，其中 CCSDS（空間數(shù)據(jù)系統(tǒng)咨詢委員會）于2006年和2007年分別發(fā)表了文檔號CCSDS 131.1-O-1的白皮書和文檔號CCSDS131.1-O-2的橙皮書，二者的編碼矩陣有所差別，但均為準(zhǔn)循環(huán)碼。在2011年8月CCSDS發(fā)表了文檔號CCSDS 131.0-B-2的藍(lán)皮書中，確定了一套分別適用于近地和深空通信的編碼標(biāo)準(zhǔn)協(xié)議。這一系列協(xié)議都預(yù)示著LDPC碼在未來的空間通信領(lǐng)域?qū)缪莞鼮橹匾慕巧?/p>

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

1 基于歐氏幾何的QC-LDPC碼的構(gòu)造

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

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

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

1.1 校驗(yàn)矩陣H的建立

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

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

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

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

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

于是便形成了如下由511×511循環(huán)方陣構(gòu)成的2×16陣列：

1.2 生成矩陣G的建立

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

其與Hqc有著相同的秩cb，假設(shè) Hqc的前（t-c）b列對應(yīng)于（t-c）b個信息位，則我們需要構(gòu)造Cqc的生成矩陣具有如下結(jié)構(gòu)：

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

Gqc成為Cqc的生成矩陣的充分必要條件為[O]，其中[O]為 cb×（t-c）b 的全零矩陣。 對于 1≤i≤t-c 及 1≤j≤c，令 gi，j為循 環(huán) 方 陣 Gi，j的 首 行 （或 首 列 ），一 旦 gi，j確 定 ，則 Gi，j可通過由 gi，j循環(huán)移 位的方式 得 到 ， 故稱 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 可得如下方程：

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

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

2 性能測試

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

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

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

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

3 QC-LDPC碼的FPGA實(shí)現(xiàn)及航天應(yīng)用方案

當(dāng)今的飛行器和地面系統(tǒng)只能處理32-bit倍數(shù)結(jié)構(gòu)的數(shù)據(jù)，顯然（8176，7154）碼并不滿足這個條件。為了在實(shí)際的空間通信系統(tǒng)中獲得應(yīng)用，需將（8176，7154）碼縮短和修整為（8160，7136）碼并在編碼時進(jìn)行擾碼、添加幀頭[9]等操作，之后才能進(jìn)入調(diào)制等之后的環(huán)節(jié)。

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

圖3 編碼器設(shè)計(jì)圖Fig.3 The encoder design

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

3.1 編碼電路原理

根據(jù)Gqc中P矩陣的循環(huán)結(jié)構(gòu)設(shè)計(jì)編碼電路單元。設(shè)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 所對應(yīng)的碼字為 v=aGqc且 v 為系統(tǒng)形式 v=（a，p1，p2，…，pc），其中對于 1≤j≤c，pj=（pj，1，pj，2，…，pj，b）為一段b位的校驗(yàn)位序列。對于1≤j≤c，由v=aGqc可知：

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

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

3.2 串行編碼方案

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

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

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

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

3.3 并行編碼方案

為滿足圖像傳輸?shù)雀咚贁?shù)據(jù)通信場合，還可用SRAA電路構(gòu)建并行編碼器。其基本思想是同時用（t-c）個SRAA電路完成式（17）中（t-c）個被加項(xiàng)的計(jì)算，如此只需b個時鐘周期就能得到pj。用c組這樣的并行SRAA電路，便能同時計(jì)算所有校驗(yàn)位，并行編碼器結(jié)構(gòu)圖如圖6所示。

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

4 結(jié)束語

文中對一類基于歐氏幾何的QC-LDPC碼的數(shù)學(xué)基礎(chǔ)及性能進(jìn)行了分析，提出了該類碼的普適性構(gòu)造方法。并結(jié)合CCSDS 所推薦的（8 176，7 154）碼和（8 160，7 136）碼，對此類QC-LDPC碼的硬件實(shí)現(xiàn)展開研究，采用SRAA電路單元分別設(shè)計(jì)了串、并行編碼方案，并使用FPGA進(jìn)行了實(shí)現(xiàn)，達(dá)到了很高的碼速率，具有相當(dāng)高的應(yīng)用價值，適用于資源、功耗、碼速率要求嚴(yán)格的空間通信系統(tǒng)。

[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，F(xiàn)ossorier 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.