楊 張，袁梅冷，雷海軍

(1.深圳職業(yè)技術(shù)學(xué)院，廣東 深圳 518055;2.深圳大學(xué)計算機與軟件學(xué)院廣東省普及型高性能計算機重點實驗室，廣東 深圳 518060)

責(zé)任編輯:時 雯

1 LDPC簡述

LDPC(Low Density Parity Check)碼即為低密度奇偶校驗碼，它是 Gallager［1－2］在1963 年提出的具有稀疏校驗矩陣的線性分組碼，Turbo碼的迭代譯碼思想在LDPC碼中的應(yīng)用使其對較長的LDPC碼在BPSK調(diào)制性能中接近AWGN信道下的Shannon限。LDPC碼的優(yōu)良性能已被公認(rèn)為將代替Turbo碼應(yīng)用在分布式視頻編碼(DVC)及下一代通信技術(shù)等領(lǐng)域。

目前，對于性能優(yōu)良的LDPC碼均采用隨機構(gòu)造方法，這種碼具有兩個缺點:碼字無規(guī)則，需要較大的存儲空間;隨機構(gòu)造方法在參數(shù)控制方面不是很靈活，必須在構(gòu)造出校驗矩陣后才可根據(jù)校驗矩陣計算碼長、碼率［3］。文獻(xiàn)［4］中PEG算法雖然可以使參數(shù)構(gòu)造方便靈活，并且可以在每次添加一條邊時使局部圈長都保持最大，但是PEG算法以及后來人們在其基礎(chǔ)上修改的其他算法都只考慮了圈長，忽視了小環(huán)的數(shù)目，如果小環(huán)的數(shù)目偏多，即使圈長較大，也將嚴(yán)重影響譯碼性能。文獻(xiàn)［5］為了實現(xiàn)LDPC部分并行譯碼的特點，以PEG算法為基礎(chǔ)引入了QC特性［6－7］，該方法構(gòu)造的LDPC碼可以保證局部圈長最大，并且準(zhǔn)循環(huán)特性可以減小存儲空間，同時可以實現(xiàn)工程上的部分并行譯碼性能，但是該方法在保證局部圈長最大情況下仍然沒有使小環(huán)數(shù)目最小。本文充分分析了構(gòu)造LDPC碼的校驗矩陣，得知各種算法存在的優(yōu)缺點，對文獻(xiàn)［6］使用的PEG算法采用PC標(biāo)記法修改，使PEG算法同時滿足局部圈長最大、小環(huán)數(shù)目最小，然后引入QC特性，在保證譯碼性能相當(dāng)?shù)那疤嵯聦崿F(xiàn)工程上的部分并行譯碼。

2 PC(Polynomial of Cycle)標(biāo)記法原理

PEG算法是一種逐邊增加的算法，每增加一條邊時按照 Tanner圖展開［8－9］，展開終止的條件為當(dāng)前校驗節(jié)點的集合的補集不為空集，再展開一步則校驗節(jié)點集合的補集為空集則終止，或者展開到校驗節(jié)點數(shù)目不再隨展開而增加時停止，這樣雖然可以保證每增加一條邊局部圈長最大，但是該構(gòu)造方法小環(huán)數(shù)目較多，較多的小環(huán)數(shù)目將嚴(yán)重影響譯碼性能，因此本文將引入一種PC標(biāo)記法減少小環(huán)的數(shù)目。

圖1是以變量節(jié)點Vi為根節(jié)點展開的樹形圖，具體PC標(biāo)記法描述如下。

圖1 樹形Tanner展開

定義一，初始化根節(jié)點Vi的PC值為1，若C2和C3是從Vi展開得到，Vi是父節(jié)點，C2和C3是子節(jié)點，在下一次展開式子節(jié)點必須排除父節(jié)點。

定義二，子節(jié)點的PC值等于父節(jié)點乘以x，所以C2和C3的PC值為x，如果一個子節(jié)點有兩個或者更多的父節(jié)點，則PC值計算如下:首先把所有父節(jié)點的PC值相加;然后把得到的值再乘以x，即為該子節(jié)點的PC值，例如C7有兩個父節(jié)點，則C7的值為2x3。

PC的表達(dá)式wxk中，w和k代表2個重要信息，k代表當(dāng)前展開節(jié)點的環(huán)長，w代表當(dāng)前展開節(jié)點的小環(huán)數(shù)目。若C5，C1和C4為集合中待選校驗節(jié)點，則此時可以根據(jù)計算得到的PC值選擇C5，從而保證小環(huán)的數(shù)目最小，因為C5有2個小環(huán)，C1有3個小環(huán)，C4有3個小環(huán)。

同一個校驗節(jié)點可能在展開的樹形圖中多次出現(xiàn)，則校驗節(jié)點Cj的PC多項式值可以表示為

式中:w1x2k－1表示添加w1條2k的環(huán);w2x2(k+1)－1表示添加w2條2(k+1)的環(huán)。如果校驗節(jié)點Cp在樹形圖中沒有出現(xiàn)，則Cp的環(huán)多項式為0，選擇Cp建立邊，那么將不會出現(xiàn)環(huán)長比2(l+1)短的環(huán)，l為樹形圖展開的最大層數(shù)。

最優(yōu)節(jié)點選擇方法:比較校驗節(jié)點的環(huán)多項式，選擇冪次最小的校驗節(jié)點，然后從冪次最小校驗節(jié)點集合中選擇冪次最大的，這樣可以保證該校驗節(jié)所形成的最小環(huán)最大，如果冪次最大的校驗節(jié)點不唯一，進(jìn)一步比較系數(shù)值，選擇系數(shù)值最小的可以保證該小環(huán)的數(shù)目最小。這里不直接在校驗節(jié)點環(huán)多項式中選擇冪次最大的理由在于:最大的冪次雖然保證了有較大的環(huán)，但是不能保證最小環(huán)的大小。

3 基于PC－PEG的QC－LDPC碼的構(gòu)造算法

PC－PEG算法是在PEG算法上基礎(chǔ)上改進(jìn)的，也是一種逐漸增加邊的算法，以變量節(jié)點按樹形圖展開，由于是要選擇最優(yōu)的校驗節(jié)點，所以按上述方法分別計算所有校驗節(jié)點的PC值wxk，k代表當(dāng)前展開的節(jié)點的環(huán)長，w代表當(dāng)前展開節(jié)點的小環(huán)數(shù)目，所以需要選擇k最大、w最小的校驗節(jié)點。由于LDPC譯碼算法本質(zhì)上是一種并行譯碼，可以通過構(gòu)造具有QC特性的LDPC碼使其實現(xiàn)工程上的部分并行譯碼，且可以節(jié)省存儲空間。

綜上所述，采用PC－PEG算法構(gòu)造具有準(zhǔn)循環(huán)特性的QC－LDPC碼，并對并行譯碼性能進(jìn)行分析。要構(gòu)造QC－LDPC碼首先要確定參數(shù):矩陣大小、循環(huán)移位矩陣、度分布。分析本文提出的PC－PEG算法并對QC－LDPC碼進(jìn)行構(gòu)成，具體過程如下:

1)構(gòu)造矩陣H，大小為m×n，循環(huán)移位矩陣Q，大小為L×L，確定基矩陣的大小c=m/L，t=n/L。

2)采用PC－PEG算法構(gòu)造基矩陣Hb，可以保證較大圈長的同時具有較少的小環(huán)數(shù)目。

對于每一個變量節(jié)點Vi(i=1，…，n)，有:

(1)為變量節(jié)點Vi添加第一條邊時，選擇度最小的校驗節(jié)點連接，其他邊時轉(zhuǎn)(2);

(2)變量節(jié)點和校驗節(jié)點PC值初始化;

①變量節(jié)點PC值初始化，即

②校驗節(jié)點PC值初始化，即

(3)按第1節(jié)的方法樹形展開，并逐層更新變量節(jié)點和校驗節(jié)點的PC值;

①若校驗節(jié)點Cj由變量節(jié)點Vi展開得到，校驗節(jié)點Cj的PC值更新為

②若變量節(jié)點Vq由校驗節(jié)點Cp展開得到，變量節(jié)點Vq的PC值更新為

(4)根據(jù)第1節(jié)介紹的最優(yōu)節(jié)點選擇方法尋找最優(yōu)校驗節(jié)點Ci建立邊，即

(5)返回(2)完成變量節(jié)點Vi其他邊的建立。

3)根據(jù)步驟2)構(gòu)造的基矩陣Hb采用式(7)計算得到循環(huán)移位參數(shù)矩陣P，即

式中，aij是已知的，z是一個從0開始的記號，它表示在基矩陣Hb中每一行1的相對位置，例如z=0每一行首先出現(xiàn)1的位置，z=1表示每一行其次出現(xiàn)1的位置。

4)根據(jù)步驟3)計算得到的循環(huán)移位參數(shù)矩陣P和循環(huán)移位矩陣Q，得到最終的校驗矩陣H。

4 實驗性能測試

4.1 實驗小環(huán)數(shù)目統(tǒng)計

實驗采用Mackay構(gòu)造算法、PEG構(gòu)造算法、基于PC的PEG算法(PC－PEG)。PEG算法構(gòu)造的QC－LDPC碼(PEG QC－LDPC)、改進(jìn) PEG算法構(gòu)造的 QC－LDPC碼(PC－PEG QC－LDPC)的校驗矩陣為256 ×512，變量節(jié)點的度為3，校驗節(jié)點的度為6(少數(shù)校驗節(jié)點的度為5或者7)，環(huán)的個數(shù)統(tǒng)計如表1所示?？梢钥闯霾捎肞C－PEG算法構(gòu)造的校驗矩陣中8環(huán)的數(shù)目為407，PEG算法構(gòu)造的校驗矩陣中8環(huán)個數(shù)為897，8環(huán)數(shù)目減少了54.6%。在引入QC特性后PEG QC－LDPC算法增加了6環(huán)數(shù)目(192個)，8環(huán)數(shù)目(1 304個)，雖然引入了QC特性有利于并行譯碼和存儲，但小環(huán)的加入必將影響其性能，所以必須減少小環(huán)的數(shù)目，本文采用的PC－PEG QC－LDPC算法比PEG QC－LDPC算法減少了6環(huán)數(shù)目103個(53.6%)，減少了8環(huán)數(shù)目711個(54.5%)，即使它與PEG算法相比還是有一定的小環(huán)，但它具有QC特性。

表1 變量節(jié)點環(huán)個數(shù)統(tǒng)計

4.2 并行譯碼性能分析

在并行譯碼方面，結(jié)合LDPC譯碼特點:信息在變量節(jié)點和校驗節(jié)點之間根據(jù)Tanner圖上的邊連接來回傳遞，可知LDPC在理論上是一種并行算法，但在工程運用中很難實現(xiàn)。若有多個CNU(Check Node Update)，VNU(Variable Node Update)計算節(jié)點，當(dāng)CNU更新時需要用到變量節(jié)點信息(Qij)，且當(dāng)需要的所有Qij都準(zhǔn)備好時才可以進(jìn)行運算，同理當(dāng)VNU進(jìn)行更新時需要校驗節(jié)點信息(Rij)，且當(dāng)所有校驗節(jié)點信息準(zhǔn)備好時才可以進(jìn)行計算，對于全部并行實現(xiàn)來說可以將每一個Qij和Rij都用一個寄存器來存儲，此時再對VNU或者CNU進(jìn)行運算時可以讀取所有數(shù)據(jù)，實現(xiàn)完全并行譯碼，但這種方法會耗費大量的存儲空間，在實際應(yīng)用中對于碼長較長的情況則不能實現(xiàn)。面對以上問題可以通過時分復(fù)用有限存儲空間，實現(xiàn)部分并行譯碼，但對于不規(guī)則的LDPC碼，在進(jìn)行VNU或者CNU計算時，可能讀取的Qij或Rij不在同一列或同一行上，從而導(dǎo)致大量節(jié)點運算處于等待狀態(tài)，并行譯碼效率也很低。當(dāng)引入QC特性后根據(jù)校驗矩陣分塊結(jié)構(gòu)的特點，Qij和Rij的信息可以根據(jù)分塊矩陣的結(jié)構(gòu)分別存儲在L×(n/L)個存儲空間上，每個時鐘可以讀取L×(n/L)個數(shù)據(jù)，從而也保證了讀取的數(shù)據(jù)剛好在L行或者m/L列上，使變量節(jié)點或者校驗節(jié)點的更新無須一直處于等待所需數(shù)據(jù)，再通過復(fù)用計算單元實現(xiàn)部分并行譯碼。

4.3 譯碼性能分析

本節(jié)實驗采用PEG算法、PEG QC－LDPC算法、PCPEG QC－LDPC算法構(gòu)造的校驗矩陣分別為(256，512)和(512，1 024)，循環(huán)移位矩陣大小為8×8和16×16，變量節(jié)點的度為3，校驗節(jié)點的度大多為6，只有少數(shù)分布為5和7。仿真條件采用BPSK調(diào)制、AWGN信道，采用對數(shù)域和積譯碼算法，最大迭代次數(shù)為50，每次測試至少收集到200個錯誤比特時停止仿真，分別計算在各個信噪比下的BER，如圖2～3所示。

圖2 (256，512)L=8在不同信噪比下的誤碼率

圖3 (512，1 024)L=16在不同信噪比下的誤碼率

從表1統(tǒng)計的小環(huán)數(shù)目可知PC－PEG QC－LDPC和PEG QC－LDPC相對于PEG算法都有小環(huán)(6環(huán))，分別為89個和192個，從而導(dǎo)致在相同信噪比下其誤碼率要高于PEG算法(見圖2、圖3)，但是其QC特性可使它在并行譯碼、存儲空間上發(fā)揮很大作用。PC－PEG QC－LDPC算法誤碼率要低于PEG QC－LDPC算法，因為其減少了6環(huán)數(shù)目103個(53.6%)，8環(huán)數(shù)目減少了711個(54.5%)。從圖3可知，當(dāng)碼長增加時PEG算法誤碼率要明顯低于PEG QC算法，但在高信噪比下PC－PEG QC算法的誤碼率接近PEG算法。

5 結(jié)論

本文提出的PC－PEG算法在保證Girth最大的條件下減少了小環(huán)的數(shù)目，實驗測得PC－PEG相比PEG算法在8環(huán)數(shù)目中減少了490個(54.6%)，并且引入了QC特性，雖然引入了QC特性增加了小環(huán)的數(shù)目，但是它使得LDPC部分并行譯碼得以實現(xiàn)，解決了工程上并行實現(xiàn)的問題，并且節(jié)省了很多的存儲空間，對于較長的LDPC碼可在工程中實現(xiàn)。由實驗可知，PC－PEG QC－LDPC比PEG QC－LDPC的譯碼性能好，當(dāng)碼長增加時，在高信噪比下，與PEG算法性能相當(dāng)。

［1］LI Z W，CHEN L，ZENG L Q，et al.Efficient encoding of quasi cyclic lowdensity parity－check codes［J］.IEEE Trans.Comm.，2006，54(1):7l－81.

［2］CHUNG S，F(xiàn)ORNEY G D，RICHARDSON T J.On the design of lowdensity parity－check codes with in 0.0045 dB of the shannon limit［J］.IEEE Communications Letters，2001，5(2):58－60.

［3］LEI J，WANG J H.Quasi－cyclic extension based on PEG algorithm for construction of LDPC codes［J］.Journal on Communications，2008，29(9):103－110.

［4］楊翔，王琳，黎勇.基于PEG算法的多進(jìn)制PCGC碼［J］.重慶郵電大學(xué)學(xué)報:自然科學(xué)版，2008，20(2)，139－142.

［5］VUKOBRATOVIC D，SENK V.Generalized ACE constrained progressive edge－growth LDPC code design［J］.IEEE Communication Letters，2008，12(1):32－34.

［6］劉星成，程浩輝.基于PEG算法的準(zhǔn)循環(huán)LDPC碼構(gòu)造方法研究［J］.電路與系統(tǒng)學(xué)報，2009，14(4):115－119.

［7］LIU X C，CHENG H H.Study on the construction method of Quasi－Cyclic LDPC codes based on progressive edge－growth algorithm［J］.Journal of Circuits and Systems，2009，14(4):115－119.

［8］林炳，姜明，趙春明.基于二維優(yōu)化的QC－LDPC碼構(gòu)造方法［J］.東南大學(xué)學(xué)報:自然科學(xué)版，2010，40(1):6－10.

［9］熊磊，姚冬萍，陳霞.基于環(huán)多項式的漸進(jìn)邊增長構(gòu)造算法［J］.北京交通大學(xué)學(xué)報，2010，34(2):20－23.