李繼龍

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

責(zé)任編輯:哈宏疆

1 引言

低密度奇偶校驗（Low Density Parity Check，LDPC）碼以其優(yōu)秀的性能受到學(xué)術(shù)界的關(guān)注與廣泛研究。目前在DVB-S2、IEEE802.16e以及中國的數(shù)字電視地面廣播、數(shù)字電視衛(wèi)星廣播、移動多媒體廣播等標(biāo)準(zhǔn)中，都采用了LDPC碼。

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

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

2 LDPC碼結(jié)構(gòu)類型和譯碼實現(xiàn)分析

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

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

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

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

3 LDPC構(gòu)造分析

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

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

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

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

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

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

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

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

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

4 基于ACE的構(gòu)造算法

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

1）根據(jù)碼率和碼長確定指數(shù)矩陣大小m，n和循環(huán)值p；

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

3）確定指數(shù)矩陣中的非零元素取值，將對應(yīng)的信息節(jié)點逐次與所有校驗節(jié)點相連，并比較[0，p-1]內(nèi)所有循環(huán)值，根據(jù)相應(yīng)的環(huán)長和連接性，ACE選擇最優(yōu)的連接和循環(huán)值；

4）將步驟3）的循環(huán)值加入指數(shù)矩陣，重復(fù)步驟4），直至指數(shù)矩陣所有非零元的循環(huán)值被確定。

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

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

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

5 仿真與分析

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

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

6 結(jié)論

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

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

[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，F(xiàn)AN 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]朱慧琳，宋健，彭克武.基于代數(shù)構(gòu)造和矩陣變換的準(zhǔn)循環(huán)LDPC碼組設(shè)計[J].電視技術(shù)，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.