一類適用于衛星回傳系統的LDPC碼的構造方法

劉春江，施玉海，吳力夫，裴育杰

（國家廣播電影電視總局廣播科學研究院，北京 100866）

責任編輯:哈宏疆

0 引言

在傳統的衛星雙向通信系統中，通常采用Turbo碼作為衛星回傳信道的編碼糾錯方案[1]，并且常采用對重要的控制字段使用碼率較低的編碼方案而對有效數據載荷采用碼率較高的編碼方案兼顧數據傳輸的有效性和可靠性。由Berru等學者提出的Turbo碼具有較強的糾錯能力，在特定參數的設置下可以達到接近Shannon限的性能[2]，然而，Turbo的譯碼復雜度較高，隨著碼長的增加呈指數關系增長，并且由于Turbo碼自身的特性具有較高的誤碼平底，嚴重影響了傳輸性能，因此在一些新的衛星回傳傳輸方案中采用低密度奇偶校驗（Low Density Parity Check，LDPC）碼作為前向糾錯編碼方案[3-4]。

LDPC碼是由Gallager于1962年首先提出的[5]。近年來，在Mackay等人的研究中發現LDPC碼在編譯碼復雜度較低的情況下其糾錯能力具有接近并有可能超越Turbo碼的優點[6]，掀起了人們對LDPC碼的研究熱潮。LDPC碼主要分為兩類:一類是隨機構造的LDPC碼，該類碼在長碼時具有很好的糾錯能力，但編碼過于復雜、難以用硬件實現，編碼時間過長也不利于硬件的實時應用；另一類是結構碼，它由幾何、代數和組合設計等方法構造。大多數LDPC結構碼是循環或準循環結構，準循環碼在中短碼時具有相當強的糾錯能力，性能接近隨機構造的最優LDPC碼[7-8]，又因其硬件實現極其簡單，因此具有很好的應用前景[9]。

LDPC碼的應用中需要重點解決兩方面問題，一是LDPC碼的構造問題，二是確定適用高效的編解碼算法及其具體實現的問題，前者是基礎和前提，本文在探討總結LDPC碼常用構造方法的基礎上，提出一種可用于衛星回傳的LDPC碼的構造方法，并使用仿真工具軟件對其糾錯性能加以仿真分析。

1 LDPC碼常用構造方法

LDPC碼是基于稀疏校驗矩陣的線性分組碼，通常由它的校驗矩陣H來定義，設編碼后的碼長為N，信息位的長度為K，校驗位的長度M=N-K，碼率R=K/N，則校驗矩陣H是一個M×N的矩陣，構造LDPC碼實際上就是構造一個稀疏的校驗矩陣H。LDPC碼的常用構造方法及其特點主要有[10]:

1）LDPC碼最早的構造方法是由其發明者Gallager提出的，其構造的是規則LDPC碼，該碼的檢驗矩陣H具有如下特性:每行有k個“1”；每列有 j個“1”；記λ為任意兩列具有相同“1”的個數，則λ不大于1；k和j與H中的長度和行數相比是很小的。Gallager構造方法的特點是校驗矩陣H在水平方向上分為j個子矩陣，每個子矩陣中每列含有單個“1”，第一個矩陣按某種預先決定的方式構造，隨后的子矩陣是第一個子矩陣的隨機置換。

2）1996年對LDPC碼進行再發現的MacKay等人提出了MacKay構造法，該方法是在Tanner引入線性分組碼的圖形表示法（Tanner圖）后基于對圖的分析等而設計得出的，又分為兩種略有不同的構造法:第一種構造法的特點是每列有固定的列重，隨機構造矩陣使其行重分布盡量均勻，且任意兩列的重疊不大于1；第二種構造法與第一種類似，但是重量為2的列數最多為M/2。

3）在MacKay構造法的基礎上推廣獲得了UL-A和UL-B構造法:UL-A的構造方法是先是2個（M/2）×（M/2）的單位陣重疊，再是（M/4）×（M/4）的單位陣重疊，依次類推，最終最多M個重量為2的列；UL-B的構造方法與UL-A類似，只是左邊部分行重最多為2。

4）Kou和Lin等人從幾何的觀點研究LDPC碼的代數構造方法，提出了基于有限幾何的點、線構造LDPC碼的有限幾何構造法，分別稱為有限歐幾里德幾何（Euclid?ean Geometries，EG）構造法和投影幾何（Projection Geom?etries，PG）構造法，這兩類構造法構造的LDPC碼是循環和準循環的，具有較好的約束參數和最小碼距，這類碼一般是規則碼，和隨機構造的規則LDPC碼相比性能上有些損失，但具有更低的誤碼平底和更低的編碼譯碼復雜度。

5）LuBy等人證明了經過仔細構造的非規則二進制LDPC碼性能優于規則碼，由此產生了一類統稱為非規則構造法的LDPC碼構造方法。非規則碼校驗矩陣中每行重量和每列重量都是非均勻分布的，構造過程中需要先確定每一重量的列期望個數和每一重量的行期望個數，然后尋找性能好的度數分布，最后構造出具有不均勻誤碼保護能力的非規則LDPC碼。

此外還有將校驗矩陣H中元素的取值范圍由GF(2)改為GF(q)的非二進制構造，由于非二進制構造的LDPC碼譯碼復雜度極高，目前實際應用較少。

2 新的LDPC碼構造方法

本文提出將LDPC碼用作衛星回傳的糾錯編碼方案，考慮到衛星回傳通信中數據幀的長度一般都較短的情況，所采用的LDPC碼碼長不能太長，但糾錯性能卻必須要高，同時為了降低譯碼復雜度以利于降低硬件成本，因此采用完全隨機構造的非規則LDPC碼和性能有所損失的有限幾何構造法或Gallager構造法構造的規則LD?PC碼都有不小的缺陷，綜合考慮常用的LDPC碼構造方法及其特點，提出一種偽規則LDPC碼的構造方法。

在闡述該構造方法之前，首先對涉及到的字母的含義進行說明:H代表校驗矩陣，Hx代表校驗矩陣的子矩陣x，N代表編碼后的碼長，K代表編碼前的碼長，即信息位長度，M代表校驗位的長度，R代表編碼碼率，m為K的一個約數，用于控制分塊的大小，m越大，將H分塊數量越少。構造LDPC碼時，首先生成一個M行N列的全“0”元素矩陣H，然后根據參數m對校驗矩陣H進行分塊，將校驗矩陣拆分為M行M列的子矩陣H0和M行K/m列的子矩陣H1，H2，…，Hm，如圖1所示。

隨后按照以下步驟逐步構造LDPC碼的校驗矩陣:1）將H0中主對角線和主對角線下方次對角線所在的位置填充為1，將作為子矩陣下標的變量b初始值設置為1；2）嘗試填充子矩陣Hb，b=1，2，…，m，該子矩陣的列重為dv（b），不同的子矩陣具有不同的列重，下述表述中省略參數b；3）生成dv維隨機向量V，該隨機向量的每個元素vi互不相等，且滿足1≤vi≤M；4）在子矩陣內，先填充該子矩陣的第1列，在第一列的填充位置標記為v1，v2，…，vi；5）確定上述子矩陣內第j列的填充位置為（vi+j×m）mod M，其中i=1，2，…，dv；6）驗證由H0，H1，H2，…，Hb構成的矩陣內是否存在短環，如果存在短環，那么將最新填充的Hb清零，重新回到步驟2，如果不存在短環，繼續步驟7）；7）如果b=m，那么構造過程結束，否則將b增加1后繼續從步驟2）執行。

上述LDPC碼的構造過程可歸結為圖2所示流程。

3 仿真分析及結論

采用上述LDPC碼構造方法設計構造了一個用于衛星回傳通信的碼長為2112、碼率為0.5的LDPC碼型，使用Matlab仿真軟件，對所設計的LDPC碼和相近長度的Turbo碼在AWGN信道條件下進行誤碼率仿真分析，獲得如圖3所示的誤碼率曲線示意圖。

由圖可見，采用該方法構造的LDPC碼具有與同等長度的Turbo碼相近的誤碼率性能，但是卻具有更低的誤碼平底，更加適合于衛星回傳信道的數據傳輸。

另外，該LDPC碼的構造方法能夠適用于碼長為從1000左右的短碼到碼長為十幾萬的長碼，構造的校驗矩陣具有一定的循環性，能夠極大地降低校驗矩陣的存儲空間，此外，采用本文所述方案構造的LDPC碼的性能接近隨機構造的LDPC碼的性能，提高了LDPC校驗矩陣的性能，在通信系統中具有較強的實用性。

[1]DVB.ETSIEN 301790，V1.2.2，Interaction channelfor satellite distribution systems[S].2000.

[2]BERRU C，GLAVIEUX A，THITIMAJSHIMA P.Near Shannon limit error-correcting coding and decoding:Turbo-codes[C]//Proc.of IEEE ICC’93.[S.l.]:IEEE Press，1993:1064-1070.

[3]ETSIEN 302307 v1.1.1（2005-03）[S/OL].[2010-04-01].http://www.dvb.org/documents//en302307.v1.1.1.draft.pdf.

[4]ETSIEN 302307 V1.1.2（2006-06）[S/OL].[2010-04-01].http://www.s2licensing.com/assets/documents/DVS2standard.pdf.

[5]GALLAGER R G.Low-density parity-check codes[J].IRE Trans.Information Theory，1962（8）:21-28.

[6]MACKAY D J C.Good error correcting codes based on very sparse matrices[J].IEEE Trans.Inform.Theory，1999，45（3）:399–431.

[7]BRESNAN R.Novel code construction and decoding techniques for LDPC codes[D].Cork，Ireland:Dept.ofElec.Eng.，UCC，2004:128-148.

[8]TANNER R M.Spectralgraphs for quasi-cyclic LDPC codes[C]//Proc.2001 IEEE InternationalSymposium on Information Theory，Washingtion DC:IEEE Press，2001.

[9]劉春江，吳智勇，于新，等.一類準循環LDPC碼的快速編碼方法[J].電視技術，2007，31（6）:11-13.

[10]張忠培，史治平，王傳丹.現代編碼理論與應用[M].北京:國防工業出版社，2007.