郭軍軍，白碩棟，慕建君，荊 心，肖 鋒

(1. 西安工業(yè)大學 計算機學院, 陜西 西安 710021；2. 西安電子科技大學 計算機學院，陜西 西安 710071)

低密度奇偶校驗(Low-Density Parity-Check, LDPC)碼是文獻[1]在1962年提出的一種現(xiàn)代糾錯編碼技術．因具有簡單的編譯碼方法和可逼近香農容量限的譯碼性能，LDPC碼已經(jīng)成為當今工業(yè)界和學術界的研究熱點之一．但是，當采用消息傳遞迭代譯碼算法時，LDPC碼在高信噪比區(qū)域存在錯誤平臺現(xiàn)象．而低重量偽碼字(Pseudo-codeword)是造成LDPC碼譯碼錯誤平臺問題的主要原因之一．因此，研究LDPC碼低重量偽碼字的有效搜索方法是評估和改進其譯碼性能的關鍵．

搜索LDPC碼的偽碼字是一個非確定多項式(Non-deterministic Polynomial，NP)難問題[2]．國內外目前關于這方面的研究方法可概括為兩大類:Tanner子圖枚舉法．根據(jù)Tanner圖結構來搜索停止集(Stopping Set)和陷阱集(Trapping Set)等有害子圖，從而確定LDPC碼的偽碼字．由于規(guī)則LDPC碼的陷阱集是由短環(huán)以及與短環(huán)相連的路徑組成的[3]，文獻[4]中提出了基于短環(huán)的路徑擴展法可以有效地找出陷阱集，再通過偏置陷阱集噪聲來搜索規(guī)則LDPC碼線性規(guī)劃譯碼的偽碼字． 文獻[5]提出了非規(guī)則LDPC碼陷阱集的一種窮舉搜索方法． 該方法的基本思路是首先從Tanner圖中找出一個短環(huán)或度數(shù)較小的變量節(jié)點作為基礎，然后通過單邊、路徑或棒棒糖(lollipop)子圖方式進行擴展來找到非規(guī)則LDPC碼消息傳遞譯碼的陷阱集，從而確定對應的偽碼字[5]．但是，這類偽碼字搜索算法屬于一種窮舉算法，隨著碼長和陷阱集尺寸增大，其效率變得越來越差．隨機噪聲輸入驗證法．該類方法首先產生隨機噪聲輸入向量，然后經(jīng)多輪迭代促使譯碼器譯碼失敗而產生偽碼字． 文獻[6]提出的基于快平直方圖(Fast Flat Histogram，F(xiàn)FH)的搜索方法可以有效地找到加性高斯白噪聲(Additive White Gaussian Noise，AWGN)信道下置信傳播(Belief Propagation，BP)譯碼時LDPC碼的偽碼字[6]．通過構造隨機信道噪聲，文獻[7-8]中提出的瞬子搜索算法(Instanton Search Algorithm，ISA)可在有限次迭代后找到LDPC碼線性規(guī)劃偽碼字．然而，譯碼器輸入的隨機性導致這類偽碼字搜索方法的效率較低．

針對上述方法的不足，筆者提出了針對二元對稱信道(Binary Symmetric Channel， BSC)下LDPC碼的一種線性規(guī)劃譯碼的偽碼字搜索算法．仿真實驗結果表明，與現(xiàn)有偽碼字搜索算法相比，所提算法能夠更準確地找到中短碼長規(guī)則和非規(guī)則LDPC碼的低重量偽碼字．

1 相關術語及定義

令G=(V∪C，E)是LDPC碼Θ的Tanner圖．Tanner圖G是一種特殊的二部圖，其頂點是由變量節(jié)點和校驗節(jié)點組成的，變量節(jié)點集V= {v1，v2，…，vn}，校驗節(jié)點集C= {c1，c2，…，cm}，n和m分別表示變量節(jié)點數(shù)和校驗節(jié)點數(shù)，E是校驗節(jié)點與變量節(jié)點之間相連的邊集，即E= {v，c:v∈V，c∈C}．與變量節(jié)點v相連的校驗節(jié)點集記作N(v)= {c:c∈C，v，c∈E}，相應地，與校驗節(jié)點c相連的鄰居變量集記為N(c)= {v:v∈V，v，c∈E}．由于LDPC碼的校驗矩陣具有稀疏性特點，故圖G的邊數(shù)較少．若碼Θ的Tanner圖中所有變量節(jié)點和校驗節(jié)點的度分布相同，則稱該碼為規(guī)則LDPC碼；否則，稱之為非規(guī)則LDPC碼．

定義1 實數(shù)集上的向量u的支持集fsupp(u)定義為u的非零分量的位置下標集合[7]，即fsupp(u)= {i:ui∈u}．

定義2 二元LDPC碼校驗多胞體(Check Polytope)定義為所有長度為d的校驗行組合向量構成的凸包，并且每個行向量x中有偶數(shù)個1，即Pd=fconv({x∈ {0，1}d|x中含有偶數(shù)個1})[9]．

定義3 設一個LDPC碼Θ的校驗矩陣為H，則線性規(guī)劃譯碼時Θ的偽碼字p定義為H所對應的松弛校驗多胞體上的非整數(shù)頂點．

(1)

在式(1)中，其增廣拉格朗日函數(shù)為

(2)

其中，yj為拉格朗日乘子；υ>0，為懲罰參數(shù)．在ADMM迭代處理中，x、z和y的更新規(guī)則為

其中，函數(shù)ΠPdj(v)表示向量v在校驗多胞體Pdj上的歐幾里德投影．

(6)

2 偽碼字搜索算法

2.1 算法的提出

在二元對稱信道下，LDPC碼線性規(guī)劃譯碼失敗時輸出為非整數(shù)偽碼字．而低重量偽碼字是造成錯誤平臺現(xiàn)象的最直接原因之一．通過大量觀察分析可知，有害的Tanner子圖中變量節(jié)點的位置恰好與偽碼字向量中非整數(shù)位置重合．對于規(guī)則LDPC碼，這些偽碼字僅僅與Tanner圖中短環(huán)結構有關，而對于非規(guī)則LDPC碼，偽碼字還與Tanner子圖中含有度數(shù)較低的變量節(jié)點有關．特別地，非規(guī)則LDPC碼的偽碼字與變量節(jié)點度數(shù)為2的Tanner子圖結構密切相關．度數(shù)為2的節(jié)點可以抑制短環(huán)的出現(xiàn)，同時使得碼的漢明距離變小，這就降低了譯碼性能．因此，在搜索非規(guī)則LDPC碼的低重量偽碼字時，應考慮短環(huán)和與度數(shù)為2的變量節(jié)點相關的有害Tanner子圖結構．典型的有害Tanner子圖主要包括線性、樹狀和環(huán)形結構三大類，如圖1所示．

圖1 典型的有害Tanner子圖結構(○表示變量節(jié)點，□表示校驗節(jié)點)

受到基于Tanner圖搜索陷阱集和瞬子搜索算法的啟發(fā)，文中提出了一個以Tanner子圖為基礎的低重量偽碼字搜索(Low-Weight Pseudo-Codewords Search， LW-PCS)算法．該算法的基本思想是首先枚舉有害的Tanner子圖結構；其次選擇全零碼字作為譯碼器的輸入，并疊加隨機產生的足夠大的信道噪聲而導致譯碼器輸出偽碼字，確保有害Tanner子圖中變量節(jié)點對應位置的輸入碼字存在噪聲；最后借助ISA搜索算法，找到該噪聲結構對應的所有低重量偽碼字．

2.2 算法的描述

設一個LDPC碼的有害Tanner子圖集為S，相應的偽碼字集為P，二元對稱信道下LDPC碼ADMM線性規(guī)劃譯碼時的LW-PCS低重量偽碼字搜索算法如下:

(1) 初始化，令P←{?}．

(2) 從S中取出一個Tanner子圖s，并構造s中變量節(jié)點集合V．

(3) 對于全零向量r，隨機產生不少于|V|個擾動噪聲來翻轉r中對應位置的比特信息，并確保r中對應集合V的所有分量的比特值為1，從而得到向量r′．

(4) 令k←1，并對輸入向量r′進行ADMM線性規(guī)劃譯碼得到輸出偽碼字pk．

(8) 對于任意it∈fsupp(M(pk))(1≤t≤|fsupp(M(pk))|)，令rit是一個具有fsupp(M(pk))it支持集的向量，pit為不同的rit進行ADMM線性規(guī)劃譯碼后得到的偽碼字向量．

圖2 輸入向量r的ADMM線性規(guī)劃譯碼偽碼字收斂過程

LW-PCS算法中符號|V|表示集合V的分量的個數(shù)．在步驟(2)中，構造包含度為2的變量節(jié)點Tanner子圖時節(jié)點的數(shù)量應不少于分數(shù)距離的一半; 步驟(3)中增加過多擾動隨機噪聲會影響譯碼算法的收斂速度，因此，擾動噪聲的數(shù)目通常不超過碼長的 1/2．

3 仿真實驗及分析

為驗證文中所提出偽碼字搜索算法的準確性，選擇了一個典型的規(guī)則Tanner碼[11]和一個非規(guī)則的PEG碼進行數(shù)值仿真．

例1 (155，64)Tanner碼．Tanner碼是一個碼長為155的規(guī)則LDPC碼．該碼的校驗行數(shù)為93，分數(shù)距離為 8.349 8．Tanner碼的偽碼字最低重量wmin≈ 16.404．首先，采用文獻[12]方法找出長度為8、12、14和16的所有短環(huán)，然后利用文中提出的算法搜索偽碼字時，僅經(jīng)過 3 700 次的嘗試即可得到155個低重量偽碼字．然而，利用現(xiàn)有的ISA搜索算法必須進行 112 320 次搜索嘗試才能夠找到這155個低重量偽碼字(如表1所示)．

表1 兩種偽碼字搜索算法偽碼字搜索次數(shù)比較

例2 PEG構造的非規(guī)則LDPC碼．本實驗中選擇了一個PEG算法構造的碼長為504的PEGirReg 252× 504碼．該碼中變量節(jié)點度為2的節(jié)點約占全部變量節(jié)點的32%．由于PEGirReg252×504碼是非規(guī)則LDPC碼，因此筆者在構造LW-PCS算法的輸入集時，充分考慮了含有短環(huán)的Tanner子圖以及度為2的變量節(jié)點所構成的子圖結構對偽碼字搜索算法的影響．采用LW-PCS算法需要 598 289 次搜索即可找到該碼的291個低重量偽碼字．但是，采用現(xiàn)有的ISA搜索算法必須進行106次嘗試才僅僅能夠找到232個低重量偽碼字，如表1所示．

由此可見，與傳統(tǒng)的ISA搜索算法相比較，文中提出的LW-PCS搜索算法能夠通過較少的嘗試次數(shù)即可快速準確地找到LDPC碼的主要低重量偽碼字．

4 結 束 語

筆者針對二元對稱信道下LDPC碼線性規(guī)劃譯碼，提出了一種基于Tanner子圖知識的低重量偽碼字搜索算法．仿真結果表明，與現(xiàn)有偽碼字搜索算法相比，所提出的LW-PCS搜索算法能夠準確地找出中短長度的規(guī)則和非規(guī)則LDPC碼的偽碼字．雖然筆者提出的搜索算法可以找到許多低重量偽碼字，但并不能保證該算法能夠找到全部低重量偽碼字．因此，如何設計更加高效的偽碼字搜索算法有待于進一步研究．