基于ACE的準循環LDPC碼構造

李繼龍

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

責任編輯:哈宏疆

1 引言

低密度奇偶校驗（Low Density Parity Check，LDPC）碼以其優秀的性能受到學術界的關注與廣泛研究。目前在DVB-S2、IEEE802.16e以及中國的數字電視地面廣播、數字電視衛星廣播、移動多媒體廣播等標準中，都采用了LDPC碼。

LDPC碼的性能與碼長息息相關，碼長越長，其性能越好。但是在實際應用中，為降低硬件實現復雜度和成本，碼長可能受到限制。密度進化可得到非規則LDPC碼的最優度序列的設計，獲得最大譯碼器閾值，從而得到最佳譯碼性能。但是僅僅基于最優度分布設計的有限碼長LDPC碼的性能并不理想。LDPC碼設計中要最大化圍長，短的圍長會惡化迭代譯碼的性能。在有限碼長LDPC中，由于碼長平均環長和碼長成對數關系，圍長長度將受限于碼長。LDPC碼設計中的另外一種設計思路是減少對應雙向圖中小的停止集。小停止集對二進制刪除信道（BEC）中的迭代譯碼是有損害的。在高斯信道中減少小停止集可以達到同樣的效果[1]。

本文首先分析了LDPC碼的結構類型和譯碼實現，確定采用QC-LDPC碼作為糾錯編碼，利于實現時采用半并行結構。然后分析了LDPC碼的性能限制因素，著重分析了停止集對誤碼性能的影響。之后，提出基于ACE（Approximate Cycle EMD）的準循環LDPC碼構造算法。最后，通過仿真分析驗證了本文所提算法的有效性。

2 LDPC碼結構類型和譯碼實現分析

采用隨機LDPC碼可獲得良好的編碼增益，長的隨機LDPC碼的性能接近香農限[2]。但是隨機LDPC碼沒有結構化LDPC碼的結構特點，其編碼需要的硬件比結構化LDPC碼的編碼遠為復雜；多進制LDPC碼的優異性能改善是以增加譯碼復雜度為代價，譯碼復雜度相當高，不利于硬件的實現；準循環LDPC碼可用簡單線性移位寄存器完成編碼，準循環的特點使其能節約存儲空間，可以采用分層譯碼的方式，進行并行譯碼，減少了譯碼時延，硬件實現復雜度低[3-6]。

在碼構造時必須考慮利于譯碼實現，LDPC譯碼器主要有3種實現結構:完全并行結構、串行結構和部分并行結構。完全并行的譯碼結構中所有的變量節點和校驗節點的更新處理在一次迭代過程中完成，具有很高的吞吐量，但是占用的資源會隨著數據塊長度的增加而快速增加；串行譯碼結構一次迭代只處理一個變量節點和一個校驗節點處的概率更新，因而占用的資源很少，但是數據吞吐量非常低；部分并行譯碼結構要求校驗矩陣具有一定的規律性，功能單元通過時分復用來減少資源面積的耗用，每次迭代處理一定數目的比特節點和一定數目的校驗節點處的概率更新。半并行結構可平衡譯碼的復雜度和處理時延，是譯碼實現的最佳結構。QC-LDPC碼的結構特點適合于半并行結構的實現。

QC-LDPC碼可以通過緊湊的指數矩陣M（H）來表示，其大小為 m×n，其中 n×p是 LDPC碼的碼長，m×p是校驗位數，p是循環移位矩陣的大小。指數矩陣表示為

校驗矩陣H可以由指數矩陣M（H）擴展得到，將[-1，p-1]內的循環移位值 Pi，j擴展為擴展陣 QPi，j。 擴展陣QPi，j表示一個p×p的循環置換矩陣，它是由單位矩陣的每一行循環右移位Pi，j位得到的。

3 LDPC構造分析

LDPC碼糾錯性能的約束條件包括了4個方面:1）碼長越長，性能越好；2）非規則碼的節點度數分布優化；3）盡量減少碼中的短循環；4）雙向圖中連接的伸展性。其中碼長與實際應用有關，而節點度數分布通過密度進化得到。

LDPC碼在實際應用中，碼長可能受限。中短碼長的LDPC碼由于碼長限制，短環出現的幾率更大[3]。LDPC碼的消息傳遞譯碼算法假定變量節點是相互獨立的，短環的存在必然破壞了獨立性的假設，使得譯碼性能明顯下降。短環的存在使得變量節點在迭代譯碼的過程中頻繁給自己傳遞正反饋信息，這對于迭代譯碼而言是不希望出現的。因此，一般的碼構造方法都盡量避免短環的存在。

PEG基于環的算法以增長LDPC碼環長為目標。但是校驗矩陣雙向圖中的短環對誤碼性能的影響并不一致，并不是環長越小對譯碼性能的影響就越大。環長稍長但與剩余圖連通性較差的環對譯碼性能的影響比環長稍短但與剩余圖連通性較好的環大，這是由于雙向圖中連接性高的環中的信息節點在錯誤接收時通過迭代譯碼過程易于被相鄰節點校正，從而降低錯誤信息的迭代譯碼過程中的傳播，使之能夠被正確譯碼。

研究分析表明，LDPC碼在高信噪比時，誤碼平臺產生的主要原因是BP譯碼算法作用在雙向圖中的某種拓撲結構而產生了無法自糾正的錯誤——停止集。停止集中的校驗節點連接至停止集內的變量節點集至少2次。當停止集中的變量節點處于錯誤狀態時，這些錯誤將會在接下來的迭代譯碼過程中傳播，若停止集內校驗節點數量少，則返回的信息中沒有新的信息，不足以糾正變量節點的錯誤時，譯碼器就始終陷于一個錯誤的狀態，無法自糾正。分析表明LDPC碼的誤碼平臺主要由停止集的大小和分布決定，為降低誤碼平臺，需要構造好的拓撲結構，避免停止集的出現。中短碼長的LDPC碼短環出現的幾率更大，因而中短LDPC碼中小停止集出現的幾率更大，從而影響誤碼平臺。

通過避免小的停止集可有效提高不規則LDPC碼的糾錯性能，但是在構造過程中直接搜索并減少小停止集的方法不易實現。一種簡便的方法是使變量節點集有更多的外部節點，從而可避免碼中的小停止集。變量節點集的外信息度（Extrinsic Message Degree，EMD）是該變量節點集中外來約束節點的數目。EMD描述了環和雙向圖中其他節點的連接性。

傳統的構造算法通過增大環長減少了小停止集，有兩個原因。首先，較長的環必然包含許多變量節點，因而相應停止集較大。其次，若連通圖無短環，則其EMD也較大。但是對于有限碼長LDPC，由于不能消除所有短環，需要通過增大碼中的EMD來排除連接性小的短環，從而增大最小停止集。在高信噪比時，這樣的結構對糾錯非常重要。

在計算環的EMD時，要判定相鄰節點是否在停止集中其他任意環內，這就需要耗時的計算判定。如果忽略上述共享的約束節點的限制，得到了EMD的近似值，即近似環 EMD（Approximate Cycle EMD，ACE）。

當環中沒有子環出現的時候，環中變量節點集的EMD與ACE是相等的，否則，ACE成為EMD的上限。為了簡單起見，構造算法中的參數是ACE而不是EMD。度數低的變量節點的ACE值小。相對的，度數低的變量節點容易形成環，ACE值較小的環與圖中其他節點的連接也較少，而連接較少的子圖容易受到噪聲的影響。ACE算法可以較好地解決這個問題，它的基本思想是:構造LDPC碼時，保證所有環長小于一定值的環都有一定的ACE值[2]。

上述基于ACE的算法使得具有高連接性的短環被保留，但低連接性的長環被消除。采用這樣的方法可有效降低不規則LDPC碼的錯誤平底。將準循環碼的限制加入到ACE算法中，可以獲得準循環碼的校驗矩陣。

4 基于ACE的構造算法

結合上述基于ACE的算法，這里給出一種結構化LDPC碼的構造方法。指數矩陣中非零節點數通過密度進化的方法獲得。算法中逐次檢驗圍長和節點的連接性，據此更新檢驗矩陣的循環值。根據前面的分析，構造過程總結如下:

1）根據碼率和碼長確定指數矩陣大小m，n和循環值p；

2）根據密度進化來生成指定碼率的最優度分布，并根據矩陣大小對度分布修改，確定各指數矩陣中的非零元素的分布；

3）確定指數矩陣中的非零元素取值，將對應的信息節點逐次與所有校驗節點相連，并比較[0，p-1]內所有循環值，根據相應的環長和連接性，ACE選擇最優的連接和循環值；

4）將步驟3）的循環值加入指數矩陣，重復步驟4），直至指數矩陣所有非零元的循環值被確定。

本算法中對每個非零元采用迭代賦值算法，通過最大化局部圍長和ACE，減少了小的陷阱集。算法中逐步檢查每個比特節點并按照下述條件更新循環值。根據當前循環移位值檢查環長和連接性，將其和前一個循環移位值的對應環長和連接性比較。如果條件滿足，則將循環移位值更新為當前值。第一個條件是當前環長大于此前的環長，第二個條件是當前連接性不低于此前連接性。

指數矩陣各元素的取值為位于該位置的塊矩陣的循環移位值，其取值范圍為[0，p-1]。根據密度進化計算得到最優度分布，計算得到各信息節點連接的校驗節點個數，然后逐次將信息節點連接到校驗節點，通過最大化環長和連接性的方法，選擇能夠保證環長和連接性最大化的校驗節點連接。對于指定節點度分布的Tanner圖，逐次將每個變量節點連接到不同的校驗節點，在建立連接的過程中，將[0，p-1]內所有可能的循環值逐次加入到指數矩陣的當前位置。對每個循環值，計算出相應的環長和環的外在連接性ACE值，若當前循環值對應的環長和ACE值均大于此前計算循環值的對應值，則將循環值更新為當前循環值，否則保留原循環值；若當前環長小于此前的環長，則保留原循環值；若當前環長等于此前環長，則比較兩個循環值對應的局部環長和，取局部環長和較大的循環值。此處局部環長和為經過指數矩陣中已經賦值部分的各元素所形成的環長總和。

算法通過信息節點對應的校驗節點和非零元素循環值的遍歷，保證了指數矩陣在可能的范圍內能夠取最大化環長和連接性。經過若干次的替換過程以后，各個元素對應的循環移位值都使得通過對應節點形成的環長最長且連接性最大，此時得到最終的指數矩陣。該算法可使得每個循環偏移在當前指數矩陣中形成最大的環長和連接性ACE，減少了停止集對碼性能的影響；在最大化環長和連接性的條件下，同時盡量保證獲得最大局部環長，從而保證碼的整體環長性能。本算法對每個元素考慮了各種循環值，但是算法的復雜度并不高，因為算法中是對循環移位矩陣的指數矩陣來進行賦值處理的。綜上分析，本算法所構造的碼具有較好的糾錯性能。

5 仿真與分析

對所提算法進行仿真，采用了BPSK調制，通過加性高斯白噪聲信道傳輸，采用置信傳播算法進行譯碼，最大迭代次數為 100。選取了（576，288）與（1056，528）兩種碼，根據同樣的度分布用PEG算法和ACE算法生成兩組碼，編碼碼率均為1/2，對誤碼性能進行了對比，結果見圖1和圖2。

圖1中，碼長為576的仿真中顯著地降低了誤碼平臺，圖2中碼長為1056的仿真中瀑布區域的誤碼下降更陡峭。由圖可見，根據基于ACE的算法設計的QCLDPC碼在高信噪比時表現出更好的誤碼性能。

6 結論

筆者通過碼型結構和譯碼實現的分析確定了構造準循環LDPC碼，通過分析LDPC碼的性能限制因素，給出基于外信息度的LDPC碼構造算法。該算法采用基于ACE的方法來構造準循環LDPC碼的指數矩陣，通過最大化環長和連接性ACE，減少了陷阱集對碼性能的影響；在最大化環長和連接性的條件下，盡量保證獲得最大局部環長，從而保證碼的整體環長性能。

筆者所提出的QC－LDPC碼構造方法，不僅能夠構造具有較大最小停止集的QC－LDPC碼，而且設計靈活，適用于正則和非正則QC－LDPC碼的構造，是一種有效的構造方法。仿真分析也驗證了此方法的有效性。

[1]TIAN T，JOHNS C，VILLASENOR J D，et al.Selective avoidance of cycles in irregular LDPC code construction[J].IEEE Trans.Commun.，2004，52（8）:1242－1248.

[2]SHANNON C E.The mathematicaltheory ofcommunication[M].Urbana，IL:University of Illinois Press，1998.

[3]VUKOBRATOVIC D，SENK V.Evaluation and design of irregular LDPC codes using ACE spectrum[J].IEEE Trans.Commun.，2009，57（8）:2272－2279.

[4]KANG Jingyu，FAN Pingyi，CAO Zhigang.An iterative scheme of stopping set enlargement in the design of short－length irregular LDPC codes[C]//Proc. 3rd International Conference: Science of Electronic，Technologies of Information and Telecommunications.Susa，Tunisia:[s.n.]，2005[2009－11－01].http://www.setit.rnu.tn/last_edition/setit2005/reseau/217.pdf.

[5]朱慧琳，宋健，彭克武.基于代數構造和矩陣變換的準循環LDPC碼組設計[J].電視技術，2009，33（S2）:36－39.

[6]HE Huan，XU Youyun，CAI Yueming.Irregular quasi－cyclic LDPC codesdesign with generalized ACEconstraint[C]//Proc.2009 International Conference on Communications and Mobile Computing. Kunming，China:[s.n.]，2009:196－199.