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

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

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

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

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

1 相關(guān)術(shù)語(yǔ)及定義

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

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

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

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

(1)

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

(2)

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

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

(6)

2 偽碼字搜索算法

2.1 算法的提出

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

圖1 典型的有害Tanner子圖結(jié)構(gòu)(○表示變量節(jié)點(diǎn)，□表示校驗(yàn)節(jié)點(diǎn))

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

2.2 算法的描述

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

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

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

(3) 對(duì)于全零向量r，隨機(jī)產(chǎn)生不少于|V|個(gè)擾動(dòng)噪聲來(lái)翻轉(zhuǎn)r中對(duì)應(yīng)位置的比特信息，并確保r中對(duì)應(yīng)集合V的所有分量的比特值為1，從而得到向量r′．

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

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

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

LW-PCS算法中符號(hào)|V|表示集合V的分量的個(gè)數(shù)．在步驟(2)中，構(gòu)造包含度為2的變量節(jié)點(diǎn)Tanner子圖時(shí)節(jié)點(diǎn)的數(shù)量應(yīng)不少于分?jǐn)?shù)距離的一半; 步驟(3)中增加過(guò)多擾動(dòng)隨機(jī)噪聲會(huì)影響譯碼算法的收斂速度，因此，擾動(dòng)噪聲的數(shù)目通常不超過(guò)碼長(zhǎng)的 1/2．

3 仿真實(shí)驗(yàn)及分析

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

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

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

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

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

4 結(jié) 束 語(yǔ)

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