LDPC編碼中大矩陣求逆及存儲的一些方法*

許幫保 ，劉春江，郭沛宇，王 昱

（1.國家廣播電影電視總局 廣播科學(xué)研究院，北京 100866；2.海軍91917部隊 海軍指揮自動化機(jī)房，北京 100000）

1 引言

近年來前向糾錯功能優(yōu)越的低密度奇偶校驗（LDPC）碼[1-4]在 CMMB[5]、地面數(shù)字電視國標(biāo)、DVB-S2[6]等標(biāo)準(zhǔn)中得到成功應(yīng)用。由于LDPC碼的優(yōu)勢在碼長較長（數(shù)以千比特）時才較明顯[3]，所以實用LDPC碼的碼長多數(shù)在10000 bit左右。加上要滿足多種碼率的要求，LDPC編碼會遇到大矩陣求逆及存儲方面的問題。

若LDPC編碼器將長度為k的信息比特 m=（m0，m1，m2，…，mk-1）編碼為一個長度為n的LDPC碼字C=（m，p）＝（m0，m1，m2，…，mk-1，p0，p1，p2，…，pn-k-1），其中 p 為校驗位，設(shè)LDPC碼的奇偶校驗矩陣為H=[H1H2]，其中，H1子矩陣包括H矩陣中的前k列，H2子矩陣包括H 矩陣中的后（n－k）列，則可得校驗位：

編碼過程中，最大的運(yùn)算量發(fā)生在H2的求逆（或線性方程組求解）過程中，雖然H是稀疏矩陣，但是一般不再稀疏，這會帶來矩陣存儲量大、占用存儲資源較多的問題，在存儲資源非常緊張的嵌入式應(yīng)用和終端產(chǎn)品中非常難以實現(xiàn)。

2 LDPC編碼中大矩陣的求逆及存儲

2.1 設(shè)計特定結(jié)構(gòu)的矩陣H2使具有規(guī)則的結(jié)構(gòu)

進(jìn)行LDPC編碼時，通過行列變換等矩陣的初等運(yùn)算使矩陣H2及具有特定的規(guī)則的結(jié)構(gòu)，便于存儲和計算。例：當(dāng)碼長為15360 bit=1920 byte，碼率為3/4時，H2的階為3840。設(shè)

式中：I表示256階的單位陣，O表示256階的零陣，256階的矩陣A和B定義為

A，B的定義中I表示32階單位陣，O表示32階零陣，R表示32階單位陣的1位循環(huán)右移陣。A和B仍為行重及列重均為1的可逆陣，且B=A2。H2前256列的列重為 3，后256×14（即 3584）列的列重為 2。 此處 H2的結(jié)構(gòu)是DVB-S2[7]中所采用的LDPC校驗矩陣H2部分的改進(jìn)，經(jīng)過改進(jìn)之后原有的一列列重為1的列變?yōu)榱兄貫?，255列列重為2的列變?yōu)榱兄貫?，提高了LDPC碼的糾錯效率。

因為 R-1=RT，所以 B-1=BT=A-2。 設(shè) C=I+R-1+R-2，則 C可逆。設(shè)D=I+A-1+A-2，可求得

則可用消元法求得H2的逆，及 I+B-1D-1構(gòu)成，=矩陣1+矩陣2，其中矩陣1為15×15的分塊陣，上8行的每個元素均為B-1D-1，下7行的每個元素均為D-1；矩陣］，其中 Δ1是 8×8的分塊下三角陣，下三角元素（不含對角線）均為256階單位陣，Δ2是7×7的分塊上三角陣，上三角元素（含對角線）均為256階單位陣。

首先計算u=H1mT，信息向量mT為11520維列向量，H1為 3840×11520 的稀疏矩陣，u=H1mT為 3840維列向量。 設(shè)，u1，u2，…，u15均為 256維列向量，最后得到pT=。

對 應(yīng) 碼 率 r=1/4，2/5，1/2，3/5，2/3，3/4，4/5，5/6，13/15，9/10，碼長為N=1920×8=15360的校驗矩陣H中，H2為階為 M=（1-r）×N=256×m 的方陣，m 分別為45，36，30，24，20，15，12，10，8，6。 此處略去其他碼率對應(yīng)的H2，及p的計算。由于各碼率對應(yīng)的共用 D-1，B-1D-1，因而多碼率的實現(xiàn)并沒增加多少存儲負(fù)擔(dān)。

由循環(huán)右移1位的32階矩陣R的特性，使硬件實現(xiàn)QC-LDPC編碼[8]更方便。列重為3的H2可類似構(gòu)造使仍具一定的結(jié)構(gòu)。當(dāng)然，必須考慮LDPC解碼糾錯效率，不能出現(xiàn)Tanner圖中圍長為4的情形。設(shè)

以上列重為3的H2的逆的LU分解形式為

對應(yīng)碼率r為0.1～0.9之間間隔0.05的所有值，碼長為15360的LDPC編碼中的均有類似結(jié)構(gòu)。

2.2 Richardson和Urbanke的方法（RU Alogrithm）

Richardson和 Urbanke[4，9]指出通過對 LDPC的校驗矩陣進(jìn)行一定規(guī)則的線性操作即預(yù)編碼的算法（RU Alogrithm），可以使LDPC編碼器的復(fù)雜度控制在與碼長成線性關(guān)系。

設(shè)碼字矢量 x=（s，p1，p2）， 其中 s 為信息位，p1與 p2合起來表示校驗位，利用校驗方程Hx′=0來計算p1和p2。RU算法主要包括離線預(yù)處理和實際在線編碼兩個步驟。預(yù)處理通過行列置換把校驗矩陣H轉(zhuǎn)化為近似的下三角陣形式H′，預(yù)處理只需執(zhí)行一次，可以在軟件中離線預(yù)先處理。然后把H′分成6個稀疏矩陣，通過分步計算求得 p1和 p2，其中 p1復(fù)雜度為 O（N+g2），p2的計算復(fù)雜度為O（N）。圖1為H經(jīng)預(yù)處理后的近似下三角陣形式 H′。

對H的行變換不影響LDPC編碼。列的置換對應(yīng)碼元的比特影射。經(jīng)行變換及列置換可使矩陣T的階盡可能地大，矩陣D的階盡可能地小。

文獻(xiàn)[4]中對列重為3，行重為6的H預(yù)處理后所得D的階g可小到碼長N的0.017倍。這為碼長近10萬的LDPC碼編碼提供了可行的方法。列重為3的H經(jīng)預(yù)處理后所得最小的g為2。當(dāng)g很小時，LDPC編碼具有近似線性復(fù)雜度。

2.3 H經(jīng)行（列）置換后T雖不為下三角陣但T-1易求且稀疏

以CMMB中碼率為3/4的LDPC編碼為例，碼字比特影射向量對應(yīng)校驗矩陣的列置換，設(shè)經(jīng)列置換后的校驗矩陣為H=（H2H1），僅對H作適當(dāng)?shù)男械奈恢米儞Q后，H就可化為其中A，B，C，D，E，X1，X2，X3均為稀疏矩陣。 A，E 的行重不過11，B 的行重不過 6，X1的行重不過 1，X2的行重為 1，X3的行重不過 3，各矩陣的列重不過 3。 I1393，I54，I43，I122分別表示階為1393，54，43，122的單位矩陣。T為1612階方陣，相應(yīng)的A為1612×6912稀疏陣，B為1612×692稀疏陣，C為692×6912稀疏陣，D為692×692稀疏方陣，E為692×1612稀疏陣。雖然此處T不為下三角矩陣，但易知T-1為

因 X2X1=0，X3X1（行重不過 3）仍為稀疏矩陣，故T-1（行重不過7）仍為稀疏矩陣。ET-1B，ET-1A仍為稀疏。離線計算稀疏陣D+ET-1B，稀疏陣C+ET-1A和（D+ET-1B）-1（該逆陣的元素量約為的 9%）。 在線計算（C+ET-1A）s，在線計算得

與RU算法相比，這樣可減少在線計算從而減小編碼延時，但需要適當(dāng)增加存儲（如果考慮列的置換及行消元，可使T的階增大，D的階減?。?/p>

2.4 對H2進(jìn)行LU分解后再迭代求解

采用優(yōu)化的部分主元法對H2進(jìn)行LU分解所得下三角陣L及上三角陣U可能是稀疏的，從而僅需較小的存儲空間[10]。文獻(xiàn)[10]中L和U的非零元總數(shù)只約占元素總數(shù)的0.25%，再經(jīng)在線前向和后向迭代運(yùn)算得校驗比特向量。

3 結(jié)論

[1]GALLAGER R G.Low-density parity-check codes[M].Cambridge，Massachusetts：M.I.T.Press，1963.

[2]MACKAY D J C.Good error correcting codes based on very sparse matrices[J].IEEE Trans.Inform.Theory，1999，45：399-431.

[3]RICHARDSON T J，SHOKROLLAHI M A，URBANKE R L.Design of capacity-approaching irregular low-density parity-check codes[J].IEEE Trans.Inform.Theory，2001，47（2）：619-637.

[4]RICHARDSON T，URBANKE R.Efficient encoding of low-density parity-check codes[J].IEEE Trans.Inform.Theory，2001，47 （2）：638-656.

[5]GY/T220.1-2006，移動多媒體廣播 第1部分：廣播信道幀結(jié)構(gòu)、信道編碼和調(diào)制[S].2006.

[6]Digital Video Broadcasting（DVB）.ETSI EN 302307 v1.1.1（2004-06），Second generation framing structure，channel coding and modulation for broadcasting，interactive services，news gathering and other broadband satellite applications[S].2004.

[7]Digital Video Broadcasting（DVB）.ETSI TR 102307 v1.1.1（2005-02），Annex A，A.1，Second generation framing structure，channel coding and modulation for broadcasting，interactive services，news gathering and other broadband satellite applications[S].2005.

[8]劉春江，吳智勇，于新，等.一類準(zhǔn)循環(huán)LDPC碼的快速編碼方法[J].電視技術(shù)，2007，31（6）：11-13.

[9]袁東風(fēng)，張海剛.LDPC碼理論與應(yīng)用 [M].北京：人民郵電出版社，2008.

[10]黃荔杰，唐曉晟.CMMB系統(tǒng)中HS-LDPC編碼的實現(xiàn)[EB/OL].（2009-07-10）[2009-10-07].http：//www.paper.edu.cn/index.php/default/releasepaper/content/33773.