利用軟解調(diào)序列的LDPC 碼閉集識別方法*

包 昕，王 達，劉婉月

(1.盲信號處理重點實驗室，成都610041;2.北京大學(xué) 信息科學(xué)技術(shù)學(xué)院，北京100871)

1 引 言

信道編碼識別，即是根據(jù)解調(diào)序列，辨識出所采用的編碼類型及對應(yīng)參數(shù)，廣義來說，還包括對交織器和擾碼的識別。它主要應(yīng)用于ACM 協(xié)作通信以及通信偵察、電子對抗領(lǐng)域。

以分組碼為例:Valembois［1］、Chabot［2］、Barbier［3］、Cluzeau［4－5］等人從代數(shù)、矩陣、優(yōu)化等思路出發(fā)，將編碼識別等價為尋找對偶空間基和低碼重碼字的問題;Houcke［6］和Finiasz［7］致力于解決碼組起點和碼長的判定;昝俊軍［8］、張永光［9］分別引入新的判決統(tǒng)計量，將碼重和二元域上的秩作為分類器;借助于傳統(tǒng)分組碼嚴格的代數(shù)結(jié)構(gòu)特征，域上輾轉(zhuǎn)相除［10］、遍歷生成多項式碼根［11］以及GFFT［12］等策略也較為有效;實際工程實現(xiàn)時，Walsh－Hadamard變換［13］也被廣地應(yīng)用于各種約束關(guān)系窮舉搜索算法中。對于本文所關(guān)注的低密度奇偶校驗(Low Density Parity Check，LDPC)碼，識別案例極少。

需要明確的是，編碼識別可分為開集識別與閉集識別兩種應(yīng)用場景。前者難度較大，即在全盲環(huán)境下，實現(xiàn)編碼參數(shù)的分析與求取;而在實際工程應(yīng)用中，基于前者開集識別工作的廣泛積累，往往已對偵察目標(biāo)的涵蓋范圍有了基本限定，故此時編碼識別工作等價于實現(xiàn)信號在有限閉集內(nèi)的模式匹配，稱為閉集識別。

無論開集還是閉集識別，傳統(tǒng)編碼識別手段均針對硬解調(diào)序列展開。眾所周知，為充分利用信道輸出信息，基于軟解調(diào)序列的各種譯碼算法已被人們廣泛研究和應(yīng)用。同理，若能將軟解調(diào)序列引入編碼識別問題，理應(yīng)獲得客觀的識別增益。于沛東［14］及Tian Xia［15］先后提出了該思想，前者測試了該方法在短碼時的識別潛力，后者將其引入LDPC碼的識別問題。本文將LDPC 碼的閉集識別作為研究背景，通過計算后驗概率對數(shù)似然比(LLR)，建立與完善了軟解調(diào)序列與編碼校驗關(guān)系的約束模型，推導(dǎo)并量化了其統(tǒng)計學(xué)特征，并最終設(shè)計和實現(xiàn)了相應(yīng)簡化算法。仿真結(jié)果顯示，算法尤其適用于以LDPC 為代表的稀疏幾何編碼，較傳統(tǒng)基于硬解調(diào)序列的識別算法識別性能更優(yōu)。

2 問題描述

本節(jié)描述基于軟解調(diào)序列的閉集識別模型?？紤]如圖1所示的二進制高斯信道(BIAWGN):符號取自{0，1}的信息m1×k經(jīng)編碼后得c1×n，BPSK 調(diào)制后向量s1×n再經(jīng)AWGN 信道傳輸，接收方獲得符號取自實數(shù)域R 的含噪序列r1×n。

圖1 BIAWGN 下閉集識別處理模型Fig.1 The finite set recognition model in BIAWGN

對于正常接收方來說，快速、準(zhǔn)確地完成解調(diào)和譯碼，獲得向量c'1×n和m'1×n，是其關(guān)注的焦點。而對于非合作接收方來說，并不確認通信環(huán)節(jié)中的各個細節(jié)，需要引入信道編碼識別過程。

從應(yīng)用模式考慮，本文側(cè)重于研究在接收端存在一先驗編碼集合Γ 的條件下如何實現(xiàn)信號的準(zhǔn)確匹配;從方法實現(xiàn)上考慮，本文將嘗試在保持解調(diào)序列實數(shù)域設(shè)定的基礎(chǔ)上直接利用軟解調(diào)序列對LDPC 碼展開識別。

3 基于硬解調(diào)序列的傳統(tǒng)識別策略

基于硬解調(diào)序列的傳統(tǒng)識別策略原則上適用于所有分組碼。對于任意分組碼向量c，普遍存在校驗關(guān)系

顯然，通過考查硬解調(diào)向量c'是否依然遵循式(1)，即可形成一種編碼識別策略。其中c'與c 一樣，元素均取自二元域{0，1}。

定義2:對于n 維向量c = [c0，c1，…，cn－1]，給定關(guān)于校驗向量h 的集合L，存在運算

式中，參量u 稱作校正子。用向量乘積表示

稱作校驗方程。

顯然，u=chT恒等于0。而對于包含誤碼的硬解調(diào)序列c'，Chabot［2］給出了如下結(jié)論:

定理1:已知c 所對應(yīng)的校驗向量為h，現(xiàn)有硬解調(diào)向量c'，則

(1)若c'來自于c，

(2)若c'并非來自于c，

式中，pe為信道轉(zhuǎn)移概率。

傳統(tǒng)基于硬解調(diào)序列的閉集識別策略正是以定理1 為基礎(chǔ)，假定存在一先驗編碼集合Γ，Γ 中存儲各已知規(guī)格編碼的校驗向量h 或矩陣H。通過衡量接收序列與Γ 內(nèi)元素運算后所產(chǎn)生的大量校正子的統(tǒng)計特性，實現(xiàn)參數(shù)辨識，完成閉集識別，這一思想在實際工程實現(xiàn)中極為常見。

4 基于軟解調(diào)序列的新識別策略

由于硬解調(diào)過程采用門限判決方式，實數(shù)域接收序列r 映射為二元域序列c'后，必然造成信息丟失。本節(jié)討論如何直接利用映射為實數(shù)域的軟解調(diào)序列r 展開編碼識別。

已知軟解調(diào)向量r = [r0，r1，…，rn－1]，其元素ri取自實數(shù)域R。

(1)概率pxi=P (ci=x，x∈{0 ，1 }|r)表示直接通過對r 的觀測所得的關(guān)于ci=x 的概率，其對數(shù)似然比稱為后驗對數(shù)似然比(LLR)，記作

(2)關(guān)于運算u=cl1⊕cl2⊕…⊕clw存在概率podd=P (u=1|r)和peven=P (u=0|r)，其對數(shù)似然比稱為校驗關(guān)系對數(shù)似然比(CLLR)，記作

借鑒BP 譯碼算法［16］可得:

定理2:λi與λ存在以下關(guān)系:

式中，tanh 為雙曲正切函數(shù)。

反之，若h∈H，則有

因此，參數(shù)λ具有辨識當(dāng)前h 是否屬于解調(diào)向量r 所對應(yīng)的校驗矩陣H 的能力。改寫公式(8)得

設(shè)AWGN 信道下ri=si+ni，其中ni是均值為0、方差為σ2的高斯白噪聲序列。依據(jù)統(tǒng)計獨立性，

因此

故

代入式(11)，則

此式恰恰描述了軟解調(diào)序列r 與校驗對數(shù)似然比λ的一種約束關(guān)系。

以IEEE 802.16e 中碼率1/2、碼長576 的LDPC碼進行仿真。BPSK 調(diào)制下添加SNR =0 dB的高斯噪聲后，分別使用向量h 和h'進行CLLR 統(tǒng)計，累積概率分布如圖2所示，其中h 取自H288×576，而h'為一隨機向量。

圖2 CLLR 蒙特卡洛累積概率分布Fig.2 The cumulative probability distribution with Monte Carlo

可見，不同校驗向量CLLR 值明顯遵從不同的概率分布。因此，基于軟解調(diào)序列的LDPC 編碼識別問題等價于針對CLLR 統(tǒng)計結(jié)果的模式識別問題。

5 算法實現(xiàn)及仿真

5.1 統(tǒng)計特征分析

借助假設(shè)檢驗理論，如果能夠求得CLLR 概率分布關(guān)于校驗向量h、噪聲等參量的具體形式，則可以通過設(shè)定漏警、虛警概率實現(xiàn)精確的門限判決。然而，由于tanh()x 及artanh()x 計算復(fù)雜，難以推導(dǎo)統(tǒng)計特性。為此，首先簡化式(15)［15］為

依據(jù)此式，計算CLLR 僅需考查向量r 中絕對值最小的那一個分量。圖3給出了使用式(15)和簡化式(16)在不同信噪比下CLLR 的分布情況，可見，隨著噪聲水平增大，簡化結(jié)果與實際結(jié)果更為接近。

圖3 CLLR 原始及簡化計算方法比較Fig.3 Comparison between two calculation methods

接著推導(dǎo)λ的均值E ( λ):

依據(jù)噪聲水平不同，概率密度曲線如圖4所示。

圖4 p(|x|)的概率密度曲線Fig.4 Probability of p(|x|)

其中，

故

可見，當(dāng)h∈H 時，E ( λ)的數(shù)值計算雖仍較為復(fù)雜，但足以與hH 時的期望值進行區(qū)分。

5.2 算法實現(xiàn)與仿真

由以上討論，我們嘗試利用CLLR 的統(tǒng)計均值

來刻畫h 與校驗矩陣H 的歸屬關(guān)系。

設(shè)存在碼率1/2 的5 種LDPC 碼，校驗矩陣依次記為H1/2、H2/3A、H2/3B、H3/4A、H3/4B，分別統(tǒng)計不同噪聲水平下的平均CLLR，如圖5所示。

圖5 不同噪聲水平下Average－CLLR 曲線Fig.5 Curve of Average－CLLR in different noise

圖5中，h∈H1/2所對應(yīng)的平均CLLR 值明顯小于hH1/2所對對應(yīng)的平均CLLR 值，且隨著噪聲的增大，該差異進一步加大。因此，若以CLLR 的均值作為統(tǒng)計量，的確可在一定程度上表征h 與H 的隸屬關(guān)系，進而實現(xiàn)識別。相應(yīng)算法如下:

已知:待識別編碼集合Γ= { H1，H2，… };

M 個軟解調(diào)序列r= [r1，r2，…，rn]，ri∈R。

輸出:編碼序號ζ

算法中，我們以Average－CLLR 最小值作為輸出。

設(shè)存在大小為5 的LDPC 碼先驗集合Γ，所含校驗矩陣H 全部取自IEEE 802.16 標(biāo)準(zhǔn)?，F(xiàn)嘗試識別碼率1/2、碼長576 的LDPC 編碼，分別采用硬解調(diào)序列和軟解調(diào)序列作為測試對象，先后使用基于硬解調(diào)序列的傳統(tǒng)識別算法和本文提出的Average－CLLR 識別算法進行對比測試，繪制識別成功率曲線如圖6所示，其中仿真次數(shù)2000次，每次參與實驗的解調(diào)碼組共100 個。

圖6 基于軟/硬解調(diào)序列的識別率對比Fig.6 Recognition probability based on soft/hard demodulation sequence

可見，本文算法明顯優(yōu)于基于硬解調(diào)序列的傳統(tǒng)識別算法，特別是在低信噪比環(huán)境下，識別增益達到2～6 dB。圖中同時給出了利用CLLR 簡化算法所得的檢測結(jié)果。

6 校驗向量漢明重量對算法的影響

校驗關(guān)系c·hT=0 適用于所有編碼方式，本節(jié)將討論校驗向量漢明重量對算法適用性的影響。

已知c'=c+e，c'中元素取自二元域

且p ei()=1 =pe。顯然，當(dāng)且僅當(dāng)e 在h 中w 個非零元素處取偶數(shù)個1，式(26)方成立，即

設(shè)存在多項式 f ( t)= (1－p+p)w和 g ( t)=(1－p－p)w，分別二項展開:

容易看出，

圖7給出了不同w 下的概率變化曲線。

圖7 不同w 下式(29)的曲線Fig.7 Curves of Formula(29)with different w

可見，w 越小，c'hT=0 仍然成立的概率越大。因此，在從校驗矩陣H 中選定校驗向量h 參與識別的過程中，應(yīng)盡量選擇漢明重量w 較小的那些h。盡管該結(jié)論由硬解調(diào)序列c'推導(dǎo)得出，但其指導(dǎo)意義顯然同樣適用于本文提出的基于軟解調(diào)序列s 的識別策略。因此，以LDPC 為代表的一類稀疏幾何編碼，由于天然具備極稀疏的校驗向量h，故相較于傳統(tǒng)分組碼尤其適用于本文算法。

7 結(jié)束語

傳統(tǒng)信道編碼識別方法均基于硬解調(diào)序列，以校驗關(guān)系成立個數(shù)作為統(tǒng)計對象展開識別。本文通過引入后驗校驗對數(shù)似然比(CLLR)這一統(tǒng)計量，推導(dǎo)了符號取自實數(shù)域軟解調(diào)序列與編碼校驗約束關(guān)系的數(shù)學(xué)形式。利用此結(jié)論，在限定閉集應(yīng)用背景的條件下，設(shè)計并簡化識別模型，最終設(shè)計了相應(yīng)算法。對比仿真及理論推導(dǎo)顯示，本文較傳統(tǒng)基于硬解調(diào)序列的識別算法明顯占優(yōu)，并尤其適用于以LDPC 為代表的稀疏類編碼，在低信噪比環(huán)境下識別增益達到2～6 dB，現(xiàn)已應(yīng)用于工程實踐。

［1］ Valembois A.Detection and recognition of a binary linear code［J］. Discrete Applied Mathematics，2001，111(1):199－218.

［2］ Chabot C. Recognition of a code in a noisy environment［C］ //Proceedings of 2007 IEEE Symposium on Information Theory.Nice，F(xiàn)rance:IEEE，2007:2210－2215.

［3］ Barbier J，Sicot G，Houcke S.Algebraic Approach for the Reconstruction of Linear and Convolutional Error Correcting Codes［J］. International Journal of Mathematical and Computer Science，2006，2(3):113－118.

［4］ Cluzeau M，Tillich J. On the code reverse engineering problem［C］//Proceedings of 2008 International Symposium on Information Theory. Toronto，ON:IEEE，2008:634－638.

［5］ Cluzeau M.Block code reconstruction using iterative decoding techniques［C］//Proceedings of 2006 IEEE International Symposium on Information Theory. Seattle，WA:IEEE，2006:2269－2273.

［6］ Houcke S，Sicot G.Blind frame synchronization for block code［C］//Proceedings of 2006 EUSIPCO.Florence，Italy:IEEE，2006:1－5.

［7］ Cluzeau M，F(xiàn)iniasz M. Recovering a code＇s length and synchronization from a noisy intercepted bitstream［C］//Proceedings of 2009 International Symposium on Information Theory.Seoul:IEEE，2009:2737－2741.

［8］ 昝俊軍，李艷斌. 低碼率二進制線性分組碼的盲識別［J］.無線電工程，2009，39(1):19－24.ZAN Junjun，LI Yanbin.Blind Recognition of Low Coderate Binary Linear Block Codes［J］. Radio Engineering，2009，39(1):19－24.(in Chinese)

［9］ 張永光.信道編碼及其識別分析［M］.北京:電子工業(yè)出版社，2010.ZHANG Yongguang.Recognition and analysis of Channel Coding［M］. Beijing:Publishing House of Electronic Industry，2010.(in Chinese)

［10］ 劉玉君.有限域上RS 碼特征的研究［J］.信息工程大學(xué)學(xué)報，2007，8(1):64－67.LIU Yujun.Studies on the Features of RS Codes over Finite Fields［J］. Journal of Information Engineering University，2007，8(1):64－67.(in Chinese)

［11］ 劉健.RS 碼的盲識別方法［J］. 電子科技大學(xué)學(xué)報，2009，38(3):363－367.LIU Jian. Blind Recognition Method of RS Coding［J］.Journal of University of Electronic Science and Technology of China，2009，38(3):363－367.(in Chinese).

［12］ 李燦，張?zhí)扃?，劉? 基于伽羅華域高斯列消元法的RS 碼盲識別［J］.電訊技術(shù)，2014，54(7):926－931.LI Can，ZHANG Tianqi，LIU Yu. Blind Recognition of RS Codes Based on Galois Field Columns Gaussian Elimination［J］. Telecommunication Engineering，2014.54(7):926－931.(in Chinese)

［13］ 游凌.Walsh 函數(shù)在解二元域方程組上的應(yīng)用［J］.信號處理，2000，16(S1):27－30.YOU Ling.The Application of Walsh Function in Resolving of F(2)equations［J］. Signal Processing，2000，16(S1):27－30.(in Chinese)

［14］ 于沛東. 一種利用軟判決的信道編碼識別新算法［J］.電子學(xué)報，2013(2):301－306.YU Peidong. A NoreI Algorithm for ChanneI Coding Recognition Using Soft.Decision［J］. ACTA Electronica Sinica，2013(2):301－306.(in Chinese)

［15］ Xia T，Wu H C.Novel blind identification of LDPC codes using average LLR of syndrome a posteriori probability［J］.IEEE Transactions on Signal Processing，2013，62(3):632－640.

［16］ Gallager. Low Density Parity Check Codes［D］. Cambridge，MA:MIT Press，1963.