郭軍軍,白碩棟,慕建君,荊 心,肖 鋒
(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碼的低重量偽碼字.
令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)
在二元對稱信道下,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搜索算法,找到該噪聲結構對應的所有低重量偽碼字.
設一個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.
為驗證文中所提出偽碼字搜索算法的準確性,選擇了一個典型的規(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碼的主要低重量偽碼字.
筆者針對二元對稱信道下LDPC碼線性規(guī)劃譯碼,提出了一種基于Tanner子圖知識的低重量偽碼字搜索算法.仿真結果表明,與現(xiàn)有偽碼字搜索算法相比,所提出的LW-PCS搜索算法能夠準確地找出中短長度的規(guī)則和非規(guī)則LDPC碼的偽碼字.雖然筆者提出的搜索算法可以找到許多低重量偽碼字,但并不能保證該算法能夠找到全部低重量偽碼字.因此,如何設計更加高效的偽碼字搜索算法有待于進一步研究.