基于PC－PEG算法構造的QC－LDPC碼性能研究

楊 張，袁梅冷，雷海軍

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

責任編輯:時 雯

1 LDPC簡述

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

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

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

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

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

圖1 樹形Tanner展開

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

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

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

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

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

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

3 基于PC－PEG的QC－LDPC碼的構造算法

PC－PEG算法是在PEG算法上基礎上改進的，也是一種逐漸增加邊的算法，以變量節點按樹形圖展開，由于是要選擇最優的校驗節點，所以按上述方法分別計算所有校驗節點的PC值wxk，k代表當前展開的節點的環長，w代表當前展開節點的小環數目，所以需要選擇k最大、w最小的校驗節點。由于LDPC譯碼算法本質上是一種并行譯碼，可以通過構造具有QC特性的LDPC碼使其實現工程上的部分并行譯碼，且可以節省存儲空間。

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

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

2)采用PC－PEG算法構造基矩陣Hb，可以保證較大圈長的同時具有較少的小環數目。

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

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

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

①變量節點PC值初始化，即

②校驗節點PC值初始化，即

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

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

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

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

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

3)根據步驟2)構造的基矩陣Hb采用式(7)計算得到循環移位參數矩陣P，即

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

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

4 實驗性能測試

4.1 實驗小環數目統計

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

表1 變量節點環個數統計

4.2 并行譯碼性能分析

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

4.3 譯碼性能分析

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

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

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

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

5 結論

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

［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，FORNEY 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算法的多進制PCGC碼［J］.重慶郵電大學學報:自然科學版，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算法的準循環LDPC碼構造方法研究［J］.電路與系統學報，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］林炳，姜明，趙春明.基于二維優化的QC－LDPC碼構造方法［J］.東南大學學報:自然科學版，2010，40(1):6－10.

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