劉婉月　包昕　王達(dá)　金野北京大學(xué)信息科學(xué)技術(shù)學(xué)院衛(wèi)星與無線通信實(shí)驗(yàn)室北京 100871； 通信作者E-mail：wangda_2014@126.com

?

基于后驗(yàn)概率的低密度奇偶校驗(yàn)碼逆向識別方法研究

劉婉月包昕王達(dá)?金野
北京大學(xué)信息科學(xué)技術(shù)學(xué)院衛(wèi)星與無線通信實(shí)驗(yàn)室北京 100871；? 通信作者E-mail：wangda_2014@126.com

提出一種基于后驗(yàn)概率對數(shù)似然比（LLR）均值的逆向識別低密度奇偶校驗(yàn)碼（LDPC）校驗(yàn)矩陣的方法。通過估計(jì)接收碼字的信道增益以及信道噪聲方差值得到后驗(yàn)概率對數(shù)似然比并依據(jù)后驗(yàn)概率對數(shù)似然比均值最大化原則成功實(shí)現(xiàn)對 LDPC 碼校驗(yàn)矩陣的逆向識別。仿真結(jié)果表明在加性高斯白噪聲信道條件下利用所提出的LDPC碼逆向識別技術(shù)接收方可準(zhǔn)確無誤地找到發(fā)送方使用的LDPC碼校驗(yàn)矩陣。

低密度奇偶校驗(yàn)碼（LDPC）；逆向識別；后驗(yàn)概率對數(shù)似然比（LLR）

北京大學(xué)學(xué)報（自然科學(xué)版） 第52卷 第3期 2016年5月

Acta Scientiarum Naturalium Universitatis PekinensisVol. 52No.3（May 2016）doi：10.13209/j.0479-8023.2016.055

低密度奇偶校驗(yàn)碼（low density parity check codeLDPC）最早見于 1962 年 Gallager［1］的博士學(xué)位論文但是限于當(dāng)時的仿真條件LDPC碼并沒有受到應(yīng)有的重視。1996年Mackay等［2］重新發(fā)現(xiàn)LDPC碼并指出它與 Turbo碼一樣具有逼近香農(nóng)極限的能力。隨著對LDPC碼研究的深入人們發(fā)現(xiàn)其優(yōu)越的譯碼性能并將LDPC碼應(yīng)用于更廣泛的場景之中。

信道編碼盲識別指接收端在對接收信息編碼方式未知的條件下實(shí)現(xiàn)對接收信息的譯碼。隨著信道編碼技術(shù)的廣泛使用信道編碼盲識別的應(yīng)用越來越多。例如在非協(xié)作通信領(lǐng)域可以為接收信息的譯碼提供可靠的技術(shù)支持；在協(xié)作通信領(lǐng)域當(dāng)訓(xùn)練信息不能準(zhǔn)確到達(dá)時接收端可以對傳輸信息進(jìn)行譯碼；在智能移動通信和多點(diǎn)廣播通信領(lǐng)域，當(dāng)發(fā)端采用自適應(yīng)編碼時接收端可以對信號內(nèi)容進(jìn)行識別和利用。

目前國內(nèi)外學(xué)者對線性碼提出幾種盲識別方案。針對線性分組碼Valembois［3］歸納為聯(lián)合判決問題提出基于校驗(yàn)向量的二元線性分組碼的盲識別方法；Mathieu［4］基于 Valembois 的思想通過生成一系列低碼重的碼字來實(shí)現(xiàn)迭代譯碼實(shí)現(xiàn)碼長較短且誤碼率低的線性分組碼的盲識別。上述兩種方法在LDPC碼長未知且碼字起點(diǎn)未同步的情況下并不適用。

針對未刪除卷積碼，有學(xué)者提出基于快速何沖算法［5］的盲識別方法和基于歐幾里得算法的盲識別［6］。針對刪除的卷積碼有學(xué)者提出基于生成多項(xiàng)式的盲識別方法和基于校驗(yàn)矩陣與生成矩陣正交關(guān)系的盲識別方法［7-8］。上述方法在 LDPC 碼字序列的起始位置未知時并不適用且計(jì)算量巨大。

可見已有的研究方法雖然對 LDPC 碼盲識別研究有一定的借鑒意義但不能解決在碼長未知且起點(diǎn)未知的情況下的逆向識別并且計(jì)算繁復(fù)。

本文利用校驗(yàn)關(guān)系和后驗(yàn)概率的對數(shù)似然比，對LDPC碼逆向識別技術(shù)進(jìn)行研究提出一種基于后驗(yàn)概率對數(shù)似然比（log likelihood ratioLLR）均值判斷校驗(yàn)矩陣的方法。我們假設(shè)接收到的信號樣本在統(tǒng)計(jì)學(xué)意義上彼此獨(dú)立通過期望值最大算法［9］（expectation-maximization algorithmEM）對噪聲參數(shù)進(jìn)行預(yù)測并確定合理的LLR均值判斷閾值實(shí)現(xiàn)碼字起始位置的準(zhǔn)確識別并從可選的LDPC碼校驗(yàn)矩陣集合中找到發(fā)送方編碼所使用的LDPC碼校驗(yàn)矩陣。

1　基于后驗(yàn)概率LLR的LDPC碼逆向識別算法原理

每一種 LDPC碼有唯一的校驗(yàn)矩陣因此如果將校驗(yàn)矩陣與接收碼字建立關(guān)系就能夠明確地找到編碼使用的校驗(yàn)矩陣 θ。本文首先計(jì)算 LLR，然后計(jì)算每個校驗(yàn)矩陣對應(yīng)的平均 LLR以此為依據(jù)選擇編碼矩陣。

1.1 對數(shù)似然比

即為 X取值為 0和 1概率比值的自然對數(shù)。對于給定的另外一個隨機(jī)變量 YX關(guān)于 Y的條件對數(shù)似然比可以表示為

根據(jù)貝葉斯公式可以得到以下關(guān)系式：

在以下的公式表達(dá)中本文對表達(dá)方式進(jìn)行簡化并且分別用 lX（x）lX|Y（x|y）和 lY|X（y|x）代替 l（x），l（x|y）和 l（y|x）用符號⊕表示有限域中的二進(jìn)制加法用*表示以下運(yùn)算法則：

1.2 LLR在LDPC碼逆向識別中的應(yīng)用

從編碼器集合 Θ 中選擇θ ′可以確切地知道此編碼器對應(yīng)的校驗(yàn)矩陣，

其中 n 表示碼字碼長k 表示信息位個數(shù)。由校驗(yàn)關(guān)系可知，=0當(dāng)且僅當(dāng)θ ′=θ 時成立其中表示發(fā)送端由校驗(yàn)矩陣 Hθ編碼得到的第 v 個 LDPC 碼字0是（n-k）×1的零向量［9］。

表示校驗(yàn)矩陣θ′H第 i行非零元素的位置Ni表示第 i行非零元素的總數(shù)。LDPC碼字表示為vθ= c ［cv，0cv，1…cv，n-1］T因此校驗(yàn)關(guān)系可以表示為，當(dāng)且僅當(dāng)θ ′=θ 時成立。

對于LDPC碼本文假設(shè)各發(fā)送信息的碼元是統(tǒng)計(jì)學(xué)意義上獨(dú)立同分布的。由于這一性質(zhì)接收到的信號的碼元也相互獨(dú)立。因此有

其中yv表示接收端收到的LDPC的碼字。

由于LDPC碼字中各碼元取0和1的概率相同因而發(fā)送端信息碼元的后驗(yàn)概率對數(shù)似然比為0。我們計(jì)算Hθ′中第 i 個校驗(yàn)關(guān)系對于第 v 個碼字的后驗(yàn)概率的對數(shù)似然比率公式如下：

根據(jù)對數(shù)似然比的定義以及校驗(yàn)關(guān)系可知：當(dāng)θ ′=θ 時對數(shù)似然比率一定為正對所有校驗(yàn)位的后驗(yàn)概率的對數(shù)似然比求平均取值也一定為正；當(dāng)θ ′≠θ 時每個校驗(yàn)位的后驗(yàn)概率對數(shù)似然比的正負(fù)是不確定的所以對所有校驗(yàn)位的后驗(yàn)概率LLR進(jìn)行平均值運(yùn)算時數(shù)值之間會相互抵消。

接收到的第v個碼字的平均LLR可以表示為

不同的校驗(yàn)矩陣有不同的 n 和 k 值因此n-k （即校驗(yàn)位的個數(shù)）的值顯然是不同的。對編碼矩陣的選擇可以表示為因此需要對編碼矩陣集合中的所有校驗(yàn)矩陣進(jìn)行計(jì)算。

為了加速逆向識別過程本文對前 h個校驗(yàn)位計(jì)算平均 LLR值如果此時可以判斷出編碼矩陣，則停止對其后的校驗(yàn)關(guān)系的計(jì)算；如果無法判斷，則再計(jì)算累加h個校驗(yàn)關(guān)系的平均LLR值。

通過對校驗(yàn)矩陣集合中每一個校驗(yàn)矩陣的平均LLR 值的計(jì)算選擇使得平均 LLR 值最大的校驗(yàn)矩陣為信息編碼矩陣實(shí)現(xiàn)對 LDPC 碼的閉集逆向識別。

2　基于后驗(yàn)概率LLR的LDPC碼逆向識別算法實(shí)現(xiàn)

從 LLR 計(jì)算公式可知需要知道信道對發(fā)送信號的影響（包括幅度增益和噪聲功率）因而首先對接收信號中信道的影響進(jìn)行估計(jì)。在仿真時假設(shè)碼長和碼字起點(diǎn)未知需要設(shè)計(jì)逆向搜程序找尋碼字起始位置。由于判決時選擇 LLR 均值作為指標(biāo)因而需要選取閾值作為判斷標(biāo)準(zhǔn)當(dāng) LLR 均值大于閾值時認(rèn)為此時進(jìn)行判決的校驗(yàn)矩陣即為接收信息對應(yīng)的正確矩陣。

2.1 EM算法對信道參數(shù)預(yù)測

EM 算法［10］中定義接收信息 y 是不完整數(shù)據(jù)，完整數(shù)據(jù)定義為cd=［yTaT］T即獲得的接收數(shù)據(jù)y以及各接收數(shù)據(jù)的正負(fù)符號組成的向量 a［10］。用Q（θi；θi-1）表示完整數(shù)據(jù)的似然函數(shù)的期望其中參數(shù)向量值θi與在接收信息y條件下的完整數(shù)據(jù)以及θi-1相關(guān)。

在此算法第 i次迭代中參數(shù) θi即為使得上述期望公式最大的值：

直到特定條件EM 算法會收斂到似然函數(shù)的一個極大值。

期望公式的推導(dǎo)如下：

其中 C是常數(shù)。定義第 n個信息位由在接收到的信息和第（i-1）次迭代參數(shù)向量計(jì)算出的期望值為

帶入Q的表達(dá)式中得到參數(shù)表達(dá)式：

最后得到的預(yù)測結(jié)果為

I是最終迭代次數(shù)由迭代終止條件決定。

對上述預(yù)測結(jié)果的偏差進(jìn)行處理其結(jié)果的表達(dá)式為

利用 EM 迭代方法可以獲得接收信號的幅度與噪聲方差的預(yù)測值即

2.2 仿真選碼準(zhǔn)則

LDPC碼具有近香農(nóng)極限的誤碼性能、無錯誤平層、譯碼速度快等優(yōu)點(diǎn)，但其校驗(yàn)矩陣具有隨機(jī)性編碼較為復(fù)雜。QC-LDPC碼是一種基于幾何構(gòu)造的LDPC碼，繼承了LDPC碼的優(yōu)點(diǎn)同時降低了編譯碼復(fù)雜度，可實(shí)現(xiàn)性強(qiáng)，被 IEEE802.11n （WLAN）IEEE802.16e（WiMAX）和 CCSDS 等多個通信標(biāo)準(zhǔn)采用，實(shí)際上，常用的 LDPC 碼多為 QCLDPC 碼或其變種。本文選用 QC-LDPC 碼進(jìn)行仿真，選擇的 2016 碼長和 1008 碼長的 QC-LDPC 碼的校驗(yàn)矩陣（均經(jīng)密度推演算法優(yōu)化）具有代表性和常用性。備選校驗(yàn)矩陣中的部分 QC-LDPC 校驗(yàn)矩陣在加性高斯白噪聲信道（AWGN）下的誤碼性能如圖1所示。

2.3 判斷閾值的確定

根據(jù)逆向識別原理可知，當(dāng)被檢測的校驗(yàn)矩陣即為編碼所用的校驗(yàn)矩陣時，利用接收到的 LDPC碼計(jì)算得到的平均 LLR 值一定為正；當(dāng)被檢測的校驗(yàn)矩陣不是編碼所用的校驗(yàn)矩陣時，單個校驗(yàn)方程計(jì)算的 LLR 值可正可負(fù)，因此所有校驗(yàn)方程計(jì)算的均值 LLR 也可正可負(fù)。為了區(qū)分上述兩種情況（平均 LLR 都為正），本文設(shè)定一個判決閾值。當(dāng)平均LLR大于判決閾值時，認(rèn)為當(dāng)前被檢測的校驗(yàn)矩陣即為發(fā)送端產(chǎn)生 LDPC 碼所使用的，反之，則放棄這個校驗(yàn)矩陣，對下一個校驗(yàn)矩陣進(jìn)行檢驗(yàn)［9-10］。

對上述閾值的選擇采用仿真來確定。仿真條件是，在信噪比為-2dB時，對2016碼長、5/8碼率的LDPC碼在每一個閾值仿真200次，統(tǒng)計(jì)選擇起始位置正確的概率結(jié)果如表1所示。

從圖 2可以看出，當(dāng)閾值在 29～35之間時，起點(diǎn)判斷正確率為100%。當(dāng)閾值設(shè)定小于29時，由于閾值較小，非對應(yīng)的校驗(yàn)矩陣的均值LLR也有可能會超過閾值，造成起點(diǎn)判斷錯誤。當(dāng)閾值選擇過大，如大于35時，不僅非對應(yīng)的校驗(yàn)矩陣的均值上相同。實(shí)際應(yīng)用中，不能因?yàn)樾旁氡鹊淖兓约靶ｒ?yàn)矩陣的不同而改變閾值，所以閾值與起點(diǎn)選擇準(zhǔn)確率關(guān)系的穩(wěn)定性很重要。LLR無法超過閾值，對應(yīng)的校驗(yàn)矩陣也可能小于閾值，造成無法選擇出起點(diǎn)位置，使得起點(diǎn)選擇的準(zhǔn)確率降低。

表1　2016碼長的LDPC碼閾值–起點(diǎn)選擇準(zhǔn)確率仿真結(jié)果Table1 Simulation results of threshold with LDPC code length of 2016

表2　1008碼長LDPC碼閾值–起點(diǎn)選擇準(zhǔn)確率仿真結(jié)果Table 2 Simulation results of threshold with LDPC code length of 1008

表 2 和圖3為在 -2 dB 信噪比下，對 1/2 碼率、1008碼長LDPC碼閾值確定的仿真結(jié)果。

對2016碼長和1008碼長的QC-LDPC，分別在信噪比為6和-2dB的起點(diǎn)選擇準(zhǔn)確率與閾值關(guān)系進(jìn)行仿真，結(jié)果如圖4所示。

從圖4和5的仿真結(jié)果可以看出，對于備選集合中的LDPC碼的校驗(yàn)矩陣其起點(diǎn)選擇準(zhǔn)確率與閾值的關(guān)系在信噪比［-26］dB 范圍內(nèi)的變化基本

2.4 逆向盲搜程序設(shè)計(jì)

接收端對收到的信息進(jìn)行逆向識別前，需要設(shè)計(jì)逆向盲搜程序來確定碼字的起始位置。

逆向盲搜程序的設(shè)計(jì)原則與逆向識別原則相同，都依賴于每個 LDPC 獨(dú)特的校驗(yàn)關(guān)系。如果LDPC 碼與校驗(yàn)矩陣匹配，則校驗(yàn)碼的平均后驗(yàn)概率 LLR 為正，本文設(shè)定了閾值，當(dāng)均值 LLR 大于此閾值時，認(rèn)為LDPC碼與校驗(yàn)矩陣匹配。

基于這一原則，以第一個碼元為起點(diǎn)，取連續(xù)n測LDPC，將其與給定的校驗(yàn)矩陣集中的每一個校驗(yàn)矩陣進(jìn)行運(yùn)算，計(jì)算平均LLR值。如果LLR值大于給定的判定閾值，即認(rèn)為該LDPC碼的第一個碼元的位置為碼字的起始位置；否則，以第二個碼元為起點(diǎn)，重復(fù)上述步驟。依此遞推，計(jì)算得到接收信號中碼字的起點(diǎn)。

為了驗(yàn)證找到的起點(diǎn)的正確性，仿真時發(fā)送端連續(xù)發(fā)送多個 LDPC 碼字（這樣仿真是合理的因?yàn)樵趯?shí)際通信中需要傳輸大量的信息，因而傳輸?shù)拇a字一定不只一個）。本文認(rèn)為在一次傳輸中采用同一個校驗(yàn)矩陣生成 LDPC 碼。在可能的起點(diǎn)后，連續(xù)取 5個 LDPC 碼進(jìn)行逆向識別檢驗(yàn)。如果這些碼字逆向識別得出的校驗(yàn)矩陣都相同，則認(rèn)為起點(diǎn)選擇準(zhǔn)確；如果不完全相同，則認(rèn)為起點(diǎn)選擇錯誤，從該起點(diǎn)的下一比特開始重新搜索。閉集逆向識別程序設(shè)計(jì)如圖6所示。

3 仿真分析

本文對碼長為2016bit的LDPC碼進(jìn)行仿真。備選矩陣集中，2016碼長矩陣有7個（碼率為1/4、3/8、1/2、5/8、7/8的矩陣各1個，碼率為3/4的矩陣有兩個）；碼長為1008的矩陣1個（碼率為1/2），即閉集集合規(guī)模為 8。加入不同碼長的校驗(yàn)矩陣實(shí)現(xiàn)未知碼長條件下的閉集識別在逆向識別中將閾值定為33。

仿真結(jié)果如表 3～5 所示其中SNR為信噪比，Ber為誤比特率，Suc_r 為逆向識別準(zhǔn)確率。

從表 3～5可以看出當(dāng)閾值為 33時，發(fā)送方無論選取何種碼率的 LDPC 碼進(jìn)行編碼，無論新信道質(zhì)量好壞接收方均可以 100%準(zhǔn)確地判斷發(fā)送方所使用的 LDPC 碼校驗(yàn)矩陣，因此，逆向識別準(zhǔn)確率可以達(dá)到100%。

4　結(jié)論

本文對 LDPC 碼逆向識別技術(shù)進(jìn)行研究利用后驗(yàn)概率 LLR 的均值對接收到的 LDPC 碼字的校驗(yàn)矩陣進(jìn)行逆向識別。通過對接收信噪比進(jìn)行估計(jì)實(shí)現(xiàn)對接收碼字的信道增益以及信道噪聲方差值的估計(jì)得到計(jì)算后驗(yàn)概率 LLR 所需要的信道增益和噪聲功率的估計(jì)值。通過盲搜程序?qū)崿F(xiàn)對碼字起始位置的查找。依據(jù)后驗(yàn)概率 LLR 均值最大化原則成功實(shí)現(xiàn)對 LDPC 碼字的逆向識別。本文對在不同閾值下校驗(yàn)矩陣和碼字起點(diǎn)確定的準(zhǔn)確率進(jìn)行仿真確定最優(yōu)閾值提高了盲識別判決準(zhǔn)確率。仿真結(jié)果表明在最優(yōu)閾值下接收方可以利用本文提出的 LDPC 碼逆向識別技術(shù)準(zhǔn)確無誤地實(shí)現(xiàn)LDPC碼校驗(yàn)矩陣的閉集逆向識別。

表3　LDPC碼碼率為3/8時仿真結(jié)果Table3Simulation results of LDPC code rate being 3/8

表4　LDPC碼碼率為1/2時仿真結(jié)果Table4 Simulation results of LDPC code rate being 1/2

表5　LDPC碼碼率為5/8時仿真結(jié)果Table5 Simulation results of LDPC code rate being 5/8

［1］ Gallager R G. Low-density parity-check codes. IRE Trans Info Theory19628（1）：21-28

［2］ MacKay D J CNeal R M. Near Shannon limit performance of low-density parity-check codes. Electron Lett199632：1645-1646

［3］ Valembois A. Detection and recognition of a binary linear code. Discrete Applied Mathematics2001111：199-218

［4］ Mathieu C. Block code reconstruction using interative decoding techniques // IEEE International Synmposium on Information Theory. Seattle2066：2269-2273

［5］ Lu P ZZou Y. Fast computation of Grobner basis of homogenous ideals of F［xy］. Science in China：Ser F200851（4）：368-380

［6］ 鄒艷陸佩忠. 關(guān)鍵方程的新推廣. 計(jì)算機(jī)學(xué)報，200629（5）：712-718

［7］ 柴先明黃知濤王豐華. 信道編碼盲識別問題研究. 通信對抗2008（2）：33-36

［8］ 黃知濤柴先明陸鳳波等. 一種（n-1）/n碼率的刪除卷積碼的盲識別方法：中國CN200810030735.3［P］. 2008

［9］ Wiesel AGoldberg JMesser H. Non-data-aided signal-to noise-ratio estimation // IEEE Proc IEEE International Conference on Communications. New York2002：197-201

［10］ Tian XWu H C. Novel blind identification of LDPC codes using average LLR of syndrome a probability. IEEE 12th International Conference on ITS Elecommunications201262（3）：632-640

Research on Low Density Parity Check Code Reverse Recognition Methods Based on Posterior Probability

LIU WanyueBAO XinWANG Da?JIN Ye
Satellite and Wireless Communication LaboratorySchool of Electronics and Computer SciencePeking University，Beijing 100871；? Corresponding authorE-mail：wangda_2014@126.com

This paper presents a method of the reverse recognition of the check matrix coded by low density parity check code （LDPC）which is based on the posterior probability log likelihood ration （LLR）. The posterior probability LLR was obtained by estimating the channel amplification and the variance of the noise in the received code. A reverse recognition of LDPC code check matrix was achieved following the LLR mean value maximization principle. Simulation results show that the receiver can precisely retrieve the LDPC check code used by the sender under different channel circumstances through the LDPC reverse recognition method.

low density parity check code （LDPC）；reverse recognition；posterior probability log likelihood ration （LLR）

TN911

2014-12-16；

2015-07-28；網(wǎng)絡(luò)出版日期：2016-05-17