偏置自糾錯(cuò)最小和譯碼算法

周志偉，孫發(fā)魚，白瑞青

(西安機(jī)電信息技術(shù)研究所，陜西 西安 710065)

0 引言

信道編碼是為了克服信息在信道傳輸過(guò)程中受到干擾和噪聲，保證通信系統(tǒng)的傳輸可靠性而設(shè)計(jì)的一類抗干擾的技術(shù)。目前PCM/FM遙測(cè)系統(tǒng)中較多采用的是多符號(hào)檢測(cè)和Turbo乘積碼技術(shù)[1-2]。相比于Turbo碼，LDPC碼有更加優(yōu)異的譯碼性能，低的譯碼復(fù)雜度和高度并行化帶來(lái)較短的譯碼時(shí)延，在高碼率時(shí)的優(yōu)勢(shì)更加明顯[3]。好的譯碼算法應(yīng)該可以在保證性能的基礎(chǔ)上降低譯碼的復(fù)雜度。目前LDPC譯碼主要采用置信傳播譯碼，通過(guò)該譯碼算法可以得到與最大似然譯碼一樣優(yōu)異的性能，但是也導(dǎo)致算法的復(fù)雜度過(guò)高，尤其在碼長(zhǎng)過(guò)長(zhǎng)時(shí)，譯碼的復(fù)雜度往往隨著碼長(zhǎng)的增加呈指數(shù)型增長(zhǎng)。為了降低譯碼的復(fù)雜度，研究人員對(duì)其進(jìn)行了深入的探索與改進(jìn)，之后提出了最小和譯碼算法，該算法是將對(duì)數(shù)似然比算法中的對(duì)數(shù)運(yùn)算簡(jiǎn)化為比較運(yùn)算，極大地降低了譯碼復(fù)雜度，但是性能上帶來(lái)了一定的損失[4]。針對(duì)置信傳播譯碼復(fù)雜度高以及最小和算法性能不佳的問(wèn)題，本文提出偏置自糾錯(cuò)最小和譯碼算法。

1 LDPC碼譯碼算法

1.1 LDPC表示方法

LDPC碼是一種(n,k)線性分組碼，其中碼長(zhǎng)為n，信息序列長(zhǎng)度為k，由m×(n-k)校驗(yàn)矩陣H唯一決定。H的每一個(gè)列向量對(duì)應(yīng)一個(gè)碼字，每一個(gè)行向量對(duì)應(yīng)一個(gè)校驗(yàn)方程[5]。 其中LDPC碼校驗(yàn)矩陣H包含大量的零元素，只有少量的非零元素，這種稀疏特性大大降低了譯碼復(fù)雜度。

一般校驗(yàn)矩陣H以矩陣和Tanner圖兩種形式來(lái)表示，下面給出了一個(gè)5行10列行重為4列重為2的校驗(yàn)方程和校驗(yàn)矩陣。

(1)

(2)

該LDPC碼Tanner圖如圖1所示，圖中a為校驗(yàn)節(jié)點(diǎn),b為變量節(jié)點(diǎn)。通過(guò)Tanner圖可以直觀地展現(xiàn)迭代譯碼的過(guò)程?？梢钥闯?Tanner圖是雙向圖,可以用G={(V,E)}表示，其中V表示節(jié)點(diǎn)的集合，V=Va∪Vb。若校驗(yàn)矩陣H維度為m×n，則變量節(jié)點(diǎn)數(shù)量有n個(gè)，以Vb=(b1b2…bn)表示,每個(gè)Vb中元素對(duì)應(yīng)H的一列或一個(gè)碼字。校驗(yàn)節(jié)點(diǎn)數(shù)量有m個(gè),以Va=(a1a2…an)表示,每個(gè)Va中元素對(duì)應(yīng)一行。所有邊的集合用E屬于Vb∪Va來(lái)表示,同種節(jié)點(diǎn)間無(wú)相連邊。校驗(yàn)矩陣每有一個(gè)非零元素,校驗(yàn)節(jié)點(diǎn)和變量節(jié)點(diǎn)間就會(huì)存在一條邊進(jìn)行連接。

圖1 Tanner圖Fig.1 Tanner

1.2 LDPC譯碼

譯碼算法的選取直接決定了是否能激發(fā)出碼本身具有的潛在優(yōu)勢(shì)，特別是在譯較長(zhǎng)碼的時(shí)候，譯碼復(fù)雜度往往伴隨碼長(zhǎng)的增加呈指數(shù)型增長(zhǎng)，因此選取好的譯碼算法可以在保證性能的基礎(chǔ)上減小譯碼的復(fù)雜度，易于硬件實(shí)現(xiàn)[6]。

LDPC碼有很多種譯碼方法，本質(zhì)上都是基于Tanner圖的消息迭代譯碼算法。

置信傳播譯碼是根據(jù)軟迭代信息進(jìn)行概率譯碼，每一輪迭代都需要對(duì)碼字中的各個(gè)碼字關(guān)于接收碼字和信道參數(shù)的后驗(yàn)概率進(jìn)行估算，因此置信傳播譯碼算法是一種逐比特最大后驗(yàn)概率算法，所有迭代過(guò)程可以看作有校驗(yàn)矩陣決定的Tanner圖上進(jìn)行消息傳遞的過(guò)程[7]。在討論算法前，先介紹算法符號(hào)代表的含義：

a∈{1,2,3，…，M}，校驗(yàn)矩陣的第a個(gè)校驗(yàn)節(jié)點(diǎn)；

v∈{1,2,3，…，N}，校驗(yàn)矩陣的第v個(gè)變量節(jié)點(diǎn)；

s表示算法的迭代次數(shù)；

S(s)(Qv)迭代次數(shù)為s時(shí)第v個(gè)變量的后驗(yàn)概率；

M(a)表示與校驗(yàn)節(jié)點(diǎn)a連接的變量節(jié)點(diǎn)的集合；

N(v)表示與變量節(jié)點(diǎn)v連接的校驗(yàn)節(jié)點(diǎn)的集合；

a′∈M(a)/v表示與第a個(gè)校驗(yàn)節(jié)點(diǎn)相連的除去第v個(gè)變量節(jié)點(diǎn)的其他變量節(jié)點(diǎn)的集合；

v′∈N(v)/a表示與第v個(gè)變量節(jié)點(diǎn)相連的除去第a個(gè)校驗(yàn)節(jié)點(diǎn)的其他變量節(jié)點(diǎn)的集合；

S(s)(Ra，v)在第s次迭代過(guò)程中，由第a個(gè)校驗(yàn)節(jié)點(diǎn)傳遞給第v個(gè)變量節(jié)點(diǎn)的信息；

S(s)(Qv，a)在第s次迭代過(guò)程中，由第v個(gè)變量節(jié)點(diǎn)傳遞給第a個(gè)校驗(yàn)節(jié)點(diǎn)的信息。

1.2.1 置信傳播算法

設(shè)編碼器輸出的碼字為ci，在AWGN信道下進(jìn)行BPSK，輸出為xi(xi=2ci-1)；經(jīng)過(guò)信道后，譯碼器接收變量為yi，其中yi=xi+n，n服從高斯分布N(0，σ2)。

1) 初始化

根據(jù)接收變量yi，來(lái)計(jì)算ci=1的條件概率：

令P(xi=1)=P(xi=-1)=1/2，則：

從定義可知，Pv1是接收變量yi得到關(guān)于ci=1的消息。

根據(jù)校驗(yàn)矩陣H，若hij=1,則變量節(jié)點(diǎn)vi與校驗(yàn)節(jié)點(diǎn)ai連接，定義變量消息：

迭代過(guò)程主要由兩個(gè)更新步驟組成，執(zhí)行迭代這兩個(gè)步驟，對(duì)每一比特的后驗(yàn)概率進(jìn)行準(zhǔn)確的估算。

2) 校驗(yàn)節(jié)點(diǎn)更新：對(duì)變量消息進(jìn)行計(jì)算得到新的校驗(yàn)消息。

在二進(jìn)制M維序列中，如果任意的一位ai(i=1,2,3，…，M)的概率為P(ai=1)=Pi，則該序列中含有偶數(shù)個(gè)1的概率為：

含有奇數(shù)個(gè)1的概率為：

3) 變量節(jié)點(diǎn)更新：對(duì)校驗(yàn)消息進(jìn)行計(jì)算得到新的變量消息。

(1)

4) 譯碼判決

每一輪迭代完成后，對(duì)每個(gè)信息比特xi(i=1,2,3，…，n)計(jì)算其后驗(yàn)概率：

最后可以得出對(duì)發(fā)送碼字的一個(gè)估計(jì)c′=[c1,c2,c3,…,cn]。計(jì)算其伴隨式S=cHT,如果S=0，則譯碼成功，結(jié)束其迭代；否則繼續(xù)迭代，若迭代次數(shù)達(dá)到預(yù)先設(shè)定的最大值仍未成功，則失敗，結(jié)束迭代。

1.2.2 最小和算法

置信傳播算法中含有大量的乘除運(yùn)算，不利于硬件實(shí)現(xiàn)，對(duì)于硬件開(kāi)發(fā)而言，實(shí)現(xiàn)乘法運(yùn)算消耗的資源比加法運(yùn)算和比較運(yùn)算大的多，時(shí)延大。除此之外，在實(shí)際應(yīng)用中，由于噪聲方差σ2需要通過(guò)信道估計(jì)獲取的準(zhǔn)確度沒(méi)有辦法保證，所以迭代信息不易獲取，因此提出了最小和譯碼算法[8]。

1) 初始化

將初始信道信息傳遞給變量節(jié)點(diǎn)作為初始信息：

2) 校驗(yàn)節(jié)點(diǎn)更新

3) 變量節(jié)點(diǎn)更新

4) 計(jì)算后驗(yàn)概率

5) 譯碼判決

該算法在校驗(yàn)節(jié)點(diǎn)的更新中運(yùn)用了符號(hào)運(yùn)算與比較運(yùn)算代替了乘積運(yùn)算，極大地降低了運(yùn)算的復(fù)雜度，并且在迭代中使用的初始信息2yi/σ2簡(jiǎn)化為yi，極大地減小了獲取信息的復(fù)雜度。但是由于最小和算法是對(duì)校驗(yàn)節(jié)點(diǎn)更新的簡(jiǎn)化，因此降低譯碼復(fù)雜度的同時(shí)也使譯碼性能下降，本文提出偏置自糾錯(cuò)最小和譯碼算法，引進(jìn)在校驗(yàn)節(jié)點(diǎn)的更新過(guò)程中加入偏置系數(shù)α，同時(shí)改變其變量節(jié)點(diǎn)的更新過(guò)程，刪除變量節(jié)點(diǎn)更新過(guò)程中的不可靠信息。

2 偏置自糾錯(cuò)最小和算法

1) 初始化

將初始信道信息傳遞給變量節(jié)點(diǎn)作為初始信息：

2) 校驗(yàn)節(jié)點(diǎn)更新

3) 計(jì)算后驗(yàn)概率

4) 變量節(jié)點(diǎn)更新

L(l)(Qa,v)=

6) 譯碼判決

偏置自糾錯(cuò)算法通過(guò)在校驗(yàn)節(jié)點(diǎn)的更新過(guò)程中引入偏置系數(shù)，彌補(bǔ)了最小和算法近似運(yùn)算帶來(lái)的損失，同時(shí)改變其變量節(jié)點(diǎn)更新過(guò)程，在連續(xù)兩次迭代中，如果變量節(jié)點(diǎn)更新結(jié)果符號(hào)相異，就把變量節(jié)點(diǎn)的更新結(jié)果取零，刪除了變量節(jié)點(diǎn)更新過(guò)程中的不確定信息，使譯碼性能得到提高。這種算法只是增加了加法運(yùn)算與比較運(yùn)算，相比于傳統(tǒng)的置信傳播算法的乘積運(yùn)算的復(fù)雜程度可以忽略不計(jì)，更加容易硬件實(shí)現(xiàn)。相比于最小和算法，只是加入一點(diǎn)代價(jià)就極大提高譯碼的性能。

3 算法仿真

3.1 算法復(fù)雜度分析

表1列出了置信傳播算法、最小和算法、偏置自糾錯(cuò)算法3種算法節(jié)點(diǎn)更新所需要的乘法、加法、比較及其他運(yùn)算的次數(shù)，其中da表示校驗(yàn)節(jié)點(diǎn)的度，dv表示變量節(jié)點(diǎn)的度。

偏置自糾錯(cuò)最小和算法存在加法運(yùn)算、比較運(yùn)算以及極少數(shù)的乘法運(yùn)算，而置信傳播算法中存在著大量的乘法運(yùn)算，隨著碼長(zhǎng)的增加，其計(jì)算復(fù)雜度呈指數(shù)型增加。相對(duì)于置信傳播算法，偏置自糾錯(cuò)算法大大節(jié)省了計(jì)算量，更容易硬件實(shí)現(xiàn)，同時(shí)相比于最小和算法，本文提出的偏置自糾錯(cuò)算法在只增加加法運(yùn)算及比較運(yùn)算的前提下，極大地提高了譯碼性能。

表1 算法次數(shù)Tab.1 Number of algorithms

3.2 仿真結(jié)果及分析

偏置自糾錯(cuò)算法中的偏置因子α，是影響譯碼性能的關(guān)鍵因數(shù)之一，若是偏置因子選取合適，則可以使偏置自糾錯(cuò)算法在性能上逼近置信傳播算法。本文給出了4種偏置因子α的性能曲線，如圖2所示。

圖2 偏置自糾錯(cuò)最小和算法在不同偏置系數(shù)下的性能Fig.2 The performance of the bias selfcorrecting minimum sum algorithm under different bias coefficients

從圖2可以得到，當(dāng)偏置系數(shù)α=0.1 時(shí)，該算法譯碼性能最佳，同時(shí)在硬件實(shí)現(xiàn)上比較簡(jiǎn)單，只需通過(guò)加法器與比較器就可以實(shí)現(xiàn)。通過(guò)以上分析，本文選取α=0.1 為該算法的偏置因子。

為了充分衡量偏置自糾錯(cuò)最小和譯碼的性能，在AWGN信道下，采用了BPSK調(diào)試的方式，分別對(duì)硬判決、置信傳播、最小和以及本文所提出的偏置自糾錯(cuò)最小和譯碼算法進(jìn)行了仿真分析。LDPC碼采用碼長(zhǎng)為1 024的規(guī)則碼，碼率為1/2，最大迭代次數(shù)為30次。

圖3給出了不同譯碼算法的誤碼率與信噪比曲線的仿真結(jié)果圖。通過(guò)曲線可以看出置信傳播算法的性能最好，硬判決譯碼的性能最差，當(dāng)誤碼率為10-5時(shí)，置信傳播算法與偏置自糾錯(cuò)算法算法相比有0.1 dB的增益，但是置信傳播算法的譯碼復(fù)雜度相比于偏置自糾錯(cuò)算法要高，隨著碼長(zhǎng)的增加和迭代次數(shù)的變大，譯碼復(fù)雜度會(huì)越來(lái)越高。同時(shí)由于最小和算法采用了近似的方法損失了部分的性能，偏置自糾錯(cuò)算法引入偏置因子，改變了變量節(jié)點(diǎn)的更新過(guò)程，刪除了變量節(jié)點(diǎn)更新過(guò)程中的不可靠信息，彌補(bǔ)了最小和算法帶來(lái)的損耗，使其性能逼近置信傳播算法。

圖3 不同譯碼算法性能比較Fig.3 Performance comparison of different decoding algorithms

4 結(jié)論

本文提出偏置自糾錯(cuò)最小和譯碼算法，該算法的主要思想是通過(guò)添加偏置系數(shù)，改變其變量節(jié)點(diǎn)的更新過(guò)程，刪除變量節(jié)點(diǎn)更新過(guò)程中的不可靠信息，彌補(bǔ)了最小和算法由于近似運(yùn)算帶來(lái)的損耗，使其性能逼近置信傳播算法。仿真結(jié)果表明，本文提出的偏置自糾錯(cuò)最小和算法，相較于置信傳播算法，運(yùn)算復(fù)雜度降低，擁有較小的時(shí)延，性能優(yōu)于最小和算法，易于硬件實(shí)現(xiàn)，具有一定的研究和應(yīng)用價(jià)值。

雖然初步完成所需工作，但是如何找出適用于偏置自糾錯(cuò)最小和譯碼算法的最優(yōu)性能參數(shù)，還需要做大量工作。