BEC上基于內(nèi)插算法的多元SC-LDPC碼BP譯碼波速度分析*

許夢(mèng)楠，吳雅婷，施文明，張鐘浩

(上海大學(xué) a.上海先進(jìn)通信與數(shù)據(jù)科學(xué)研究院；b.特種光纖與光接入網(wǎng)重點(diǎn)實(shí)驗(yàn)室；c.特種光纖與先進(jìn)通信國(guó)際合作聯(lián)合實(shí)驗(yàn)室，上海 200444)

0 引 言

空間耦合低密度奇偶校驗(yàn)(Spatially-Coupled Low-Density Parity-Check，SC-LDPC)碼[1]在置信傳播(Belief Propagation,BP)譯碼[2]下具有比底層碼更優(yōu)異的性能[3]。SC-LDPC碼的消息在耦合鏈的兩端產(chǎn)生，隨著迭代次數(shù)的增加，消息沿著耦合鏈向中間傳播，這就是SC-LDPC碼的譯碼波傳播[4]。多元LDPC碼定義在有限域GF(2m)上，m表示每符號(hào)含有的比特?cái)?shù)[5]。SC-LDPC碼相比LDPC碼存在閾值飽和現(xiàn)象，即BP閾值飽和于最大后驗(yàn)(Maximum A Posteriori,MAP)閾值[6-7]。已經(jīng)證明二元SC-LDPC碼在二進(jìn)制擦除信道(Binary Erasure Channel,BEC)上存在閾值飽和現(xiàn)象[8]。對(duì)于多元SC-LDPC碼，可以借助勢(shì)函數(shù)證明在BEC上閾值飽和[9]。

近些年來(lái)，譯碼波的速度分析引起了人們的廣泛關(guān)注：文獻(xiàn)[8]指出譯碼波速度會(huì)隨著迭代次數(shù)的增加而收斂；文獻(xiàn)[10]利用度分布和非耦合密度演進(jìn)(Density Evolution,DE)遞歸式的不動(dòng)點(diǎn)(Fixed Point,FP)可以計(jì)算譯碼波速度的臨界點(diǎn)；文獻(xiàn)[11]推導(dǎo)了譯碼波速度的表達(dá)式并推廣到一般的空間耦合系統(tǒng)；文獻(xiàn)[12]提出了插值密度演進(jìn)算法，利用此算法分析了二進(jìn)制無(wú)記憶對(duì)稱(chēng)信道(Binary Memoryless Symmetric Channel,BMSC)上二元SC-LDPC碼譯碼波的速度。

本文運(yùn)用內(nèi)插密度演進(jìn)(Density Evolution,DE)算法分析多元SC-LDPC碼在BEC上BP譯碼波速度。通過(guò)觀察譯碼波的密度演進(jìn)發(fā)現(xiàn)，輪廓譯碼(Decoding Profile,DP)可以看作一條通過(guò)非耦合DE遞歸式的不動(dòng)點(diǎn)的路徑。受此啟發(fā)，可以利用一維內(nèi)插函數(shù)在非耦合DE遞歸式的FP間插值密度來(lái)近似表示DP，這樣避免利用耦合DE遞歸式從而降低計(jì)算復(fù)雜度。在更新內(nèi)插函數(shù)時(shí)，將變量節(jié)點(diǎn)(Variable Node,VN)和校驗(yàn)節(jié)點(diǎn)(Check Node,CN)間的轉(zhuǎn)移函數(shù)進(jìn)一步簡(jiǎn)化來(lái)降低計(jì)算復(fù)雜度。仿真和分析結(jié)果表明，在相同的度分布和信道條件下，與耦合DE算法相比，本文提出的內(nèi)插DE算法在取得很好的性能同時(shí)降低了計(jì)算的復(fù)雜度。

1 耦合DE算法

1.1 符號(hào)和定義

多元LDPC碼定義在有限域GF(2m)上，m表示每符號(hào)含有的比特?cái)?shù)[4]，其中λ和ρ分別表示變量節(jié)點(diǎn)和校驗(yàn)節(jié)點(diǎn)的邊度分布。

多元SC-LDPC(λ,ρ,m,L,w)碼，其中L和w分別表示耦合長(zhǎng)度和寬度。SC-LDPC碼的構(gòu)造：首先將單個(gè)LDPC碼的原模圖復(fù)制L相同的副本，放置在位置{1,2,…,L}，用整數(shù)k表示位置的索引；然后在位置k處，將變量節(jié)點(diǎn)的邊均勻隨機(jī)地分成w組，依次與位置為{k,k+1,…,k+w-1}的校驗(yàn)節(jié)點(diǎn)相連；同樣地，將位置k處的校驗(yàn)節(jié)點(diǎn)的邊均勻隨機(jī)地分成w組，依次與位置為{k-w+1,k-w+2,…,k}的變量節(jié)點(diǎn)相連。

圖1給出了耦合寬度w為3的SC-LDPC碼的原模圖構(gòu)造過(guò)程。SC-LDPC碼的結(jié)構(gòu)導(dǎo)致了BP譯碼算法中譯碼波由耦合鏈的兩端產(chǎn)生然后向中間傳播。

圖1 SC-LDPC碼原模圖構(gòu)造過(guò)程

1.2 BP譯碼算法中消息密度

將在BEC上傳輸?shù)南⒎植挤Q(chēng)為密度，本文分析BP譯碼算法中多元SC-LDPC碼的密度演進(jìn)(Density Evolution,DE)。在BP譯碼算法中VN和CN間交換的消息是非負(fù)向量r=(r0,r1,…,ri)，其中ri表示碼字符號(hào)x為xi的后驗(yàn)概率。例如m=2，有四種可能的碼字符號(hào)，即x0=00,x1=01,x2=10,x3=11，消息r=(0.25,0.25,0.25,0.25)表示P(x=00)、P(x=01)、P(x=10)和P(x=11)都為0.25。在BP譯碼算法中跟蹤密度很困難，因?yàn)槊總€(gè)碼字符號(hào)有2m種可能值。幸運(yùn)的是，在BEC上，BP譯碼性能不依賴(lài)具體的傳輸碼字，因此假如全為零的碼字傳輸。這樣在BEC上，消息等價(jià)于GF(2m)的一個(gè)子空間。跟蹤密度轉(zhuǎn)化為跟蹤消息的維數(shù)。消息維數(shù)為k指的是有2k非零元素?；诖耍芏妊葸M(jìn)簡(jiǎn)化為長(zhǎng)度為m+1的消息交換。例如m=3，m+1維的消息向量a=(a0,a1,…,ai,…,am)=(1,0,0,0)，0≤i≤m，i=0，a0=1指消息維度為0的概率為1，也就是消息譯碼發(fā)生0比特翻轉(zhuǎn)的概率為1；同理，i=m，am=0指消息維度為m的概率為0，也就是消息譯碼發(fā)生m比特翻轉(zhuǎn)的概率為0，表明碼字符號(hào)可以無(wú)錯(cuò)地從傳輸?shù)南⒅凶g碼。

定義1BEC上BP譯碼算法中多元SC-LDPC碼的消息密度為長(zhǎng)度為m+1的概率向量。定義密度集合

(1)

其中有兩個(gè)極限密度，Δ0=(1,0,…,0,0)表示碼字符號(hào)可以無(wú)錯(cuò)地從傳輸?shù)南⒅凶g碼，Δm=(0,0,…,0,1)表示傳輸?shù)南](méi)有為譯碼提供任何信息。

1.3 熵函數(shù)

定義2對(duì)于任意的a∈χ，a=(a0,a1,…,am)，熵函數(shù)定義為

(2)

用熵函數(shù)來(lái)衡量消息的平均不確定度。

1.4 多元LDPC(λ,ρ,m)

定義3兩個(gè)維度為m+1的概率向量a和b，

(3)

(4)

k∈{0,1,2,…,m}，

(5)

(6)

高斯二項(xiàng)式系數(shù)

(7)

定義4多元LDPC(λ,ρ,m)在刪除概率為ε的BEC上傳輸，第l輪迭代的非耦合DE遞歸式為

(8)

x(l)=p(ε)λ(ρ(□×x(l-1))),?l>0。

(9)

式中：

λ(a)=∑iλia，

(10)

ρ□×(b)=∑jρjb□× j-1。

(11)

信道密度

(12)

特別地，當(dāng)x(∞)=(1,0,…,0)，表明成功譯碼。

定義5非耦合DE遞歸式(9)的不動(dòng)點(diǎn)指的是密度對(duì)(x,y)滿足y=ρ□×(x)，x=p(ε)λ(y)。

對(duì)每個(gè)FP，總存在一個(gè)初始密度x(0)，使非耦合DE遞歸式(9)收斂于這個(gè)FP。只要給定初始密度x(0)和信道密度p(ε)，運(yùn)行非耦合DE遞歸式(9)就可得到FP。用(x,y)=T非耦合DE(x(0),p(ε))表示FP。

定義6?ε1,ε2，0≤ε1<ε2≤1，對(duì)非耦合DE遞歸式(9)的FP進(jìn)行擾動(dòng)擦除初始化：

(x,y)=T非耦合DE(εΔm+(1-ε)Δ0,p(ε)),?ε∈[ε1,ε2]。

(13)

用S={(xi,yi)}，i∈IS表示經(jīng)過(guò)擾動(dòng)擦除初始化的FP的集合，IS={0,1,…,NS-1}。經(jīng)過(guò)擾動(dòng)擦除初始化的FP是嚴(yán)格按照退化排列。分析發(fā)現(xiàn)，多元SC-LDPC碼的譯碼波動(dòng)態(tài)特性可以用非耦合DE遞歸式的穩(wěn)定的FP來(lái)表征。本文提出的內(nèi)插DE算法中，若FP按照嚴(yán)格的退化排列，則DP也具有單調(diào)性，所以本文提到的FP都是經(jīng)過(guò)擾動(dòng)擦除初始化的FP。

1.5 多元SC-LDPC(λ,ρ,m,L,w)的耦合DE算法

定義7多元SC-LDPC(λ,ρ,m,L,w)在刪除概率ε的BEC上傳輸，第l輪迭代的耦合DE遞歸式為

(14)

(15)

1≤i≤L+w-1，

(16)

本文考慮L→∞和w→∞連續(xù)條件下的情形，對(duì)應(yīng)的Tanner圖，底層集成沿著耦合鏈以連續(xù)的方式放置，位置索引為連續(xù)的變量t∈R∪{±∞}。位置t處的變量節(jié)點(diǎn)的邊均勻隨機(jī)地連接到位置為[t,t+1)的校驗(yàn)節(jié)點(diǎn)；同樣地，位置t處的校驗(yàn)節(jié)點(diǎn)的邊均勻隨機(jī)地連接到位置為(t-1,t]的變量節(jié)點(diǎn)。令t=i/w，式(14)轉(zhuǎn)化為式(17)：

(17)

定義9將DP初始化：

(18)

這樣有

(19)

2 非耦合DE遞歸式FP和DP

DP可以看作是沿著耦合鏈包含F(xiàn)P的密度路徑。FP將DP分成一個(gè)或多個(gè)過(guò)渡區(qū)間，每個(gè)過(guò)渡區(qū)間有著自己的移動(dòng)速度。下面重點(diǎn)討論DP的動(dòng)態(tài)特性并為內(nèi)插DE算法的提出創(chuàng)造條件。

(20)

(21)

利用單個(gè)過(guò)渡區(qū)間移動(dòng)速度的正負(fù)性可預(yù)測(cè)過(guò)渡區(qū)間的收斂性，例如兩個(gè)相鄰非跳動(dòng)FP{x0,x1}構(gòu)成的過(guò)渡區(qū)間τ1=τ(x0,x1,l)，如果過(guò)渡區(qū)間的移動(dòng)速度v1>0，那么DP將收斂于FPx0；如果v1<0，DP將收斂于FPx1。因此，BP閾值對(duì)應(yīng)于v1=0。

圖2 采用耦合DE算法得到的熵函數(shù)

圖3 采用內(nèi)插DE算法得到的熵函數(shù)

3 內(nèi)插DE算法

3.1 內(nèi)插DE算法遞歸式

(22)

定義14內(nèi)插DE算法中構(gòu)造兩個(gè)轉(zhuǎn)移函數(shù)來(lái)更新內(nèi)插函數(shù),如公式(23)所示:

(23)

定義15第l輪迭代的內(nèi)插DE遞歸式為

(24)

(25)

(26)

(27)

3.2 簡(jiǎn)化轉(zhuǎn)移函數(shù)的計(jì)算

定義18本文討論具有一個(gè)過(guò)渡區(qū)間τ1的DP，過(guò)渡區(qū)間τ1=τ(x0,x1,l)位于兩個(gè)相鄰非跳動(dòng)FP{x0,x1}間，x0=Δ0=(1,0,…,0,0)。為減少卷積的計(jì)算，減少計(jì)算量，定義公式(28):

(28)

式中：s1,s2∈{0,1,…,dc}，q1,q2∈{0,1,…,dv}，dc和dv分別表示CN和VN的度。密度對(duì)(x0,y0)和(x1,y1)滿足x0=y0=Δ0=(1,0,…,0,0)，y1=ρ□×(x1)，x1=p(ε)λ(y1)。

兩個(gè)轉(zhuǎn)移函數(shù)(23)轉(zhuǎn)化為式(29)：

(29)

式(29)適合規(guī)則SC-LDPC碼，對(duì)于非規(guī)則SC-LDPC碼，需根據(jù)度分布表達(dá)式做適當(dāng)變換，由于篇幅限制，本文不予討論。

(30)

式中：αsoli,1(t1)<αsoli,1(t2),?t1

3.3 BP閾值分析

定義19多元SC-LDPC(λ,ρ,m,L,w)在刪除概率為ε的BEC上，耦合DE算法的BP閾值為

(31)

定義20多元SC-LDPC(λ,ρ,m,L,w)在刪除概率為ε的BEC上，內(nèi)插DE算法的BP閾值為

(32)

定理1多元SC-LDPC(λ,ρ,m,L,w)在刪除概率為ε的BEC上，基于假設(shè)1和假設(shè)2，耦合DE算法的BP閾值等于內(nèi)插DE算法的BP閾值。

4 仿真分析

下面通過(guò)仿真來(lái)驗(yàn)證內(nèi)插DE算法的性能，并與傳統(tǒng)的耦合DE算法進(jìn)行對(duì)比。仿真采用有一個(gè)過(guò)渡區(qū)間τ1的DP，過(guò)渡區(qū)間τ1=τ(x0,x1,l)位于兩個(gè)相鄰非跳動(dòng)FP{x0,x1}間，x0=Δ0=(1,0,…,0,0)。

4.1 BP閾值比較

表1給出了BEC上耦合寬度w為5，在不同度分布和m條件下，多元SC-LDPC碼的BP閾值比較結(jié)果。從表中發(fā)現(xiàn)，相同度分布的多元SC-LDPC碼，隨著m增大，BP閾值增大且越來(lái)越接近香農(nóng)限，尤其是從m=1到m=3，BP閾值變化很大。數(shù)值仿真角度體現(xiàn)了多元SC-LDPC碼的閾值飽和。

表1 不同度分布和m條件下多元SC-LDPC碼BP閾值比較

表2是在BEC上耦合寬度w為5的多元SC-LDPC(4,8)碼在m為1、3、5、8時(shí)耦合DE算法與內(nèi)插DE算法的BP閾值比較，可以看出，耦合DE算法的BP閾值與內(nèi)插DE算法的BP閾值相等。

表2 內(nèi)插DE算法與耦合DE算法的BP閾值比較

4.2 計(jì)算復(fù)雜度

表3比較了兩種算法在單次迭代計(jì)算過(guò)程中所需的計(jì)算量，其中w、L、m、dc和dv分別表示耦合寬度、耦合長(zhǎng)度、每符號(hào)含有的比特?cái)?shù)、校驗(yàn)節(jié)點(diǎn)的度和變量節(jié)點(diǎn)的度?？梢园l(fā)現(xiàn)，耦合DE算法由于迭代的是高維的DE遞歸式，因此耦合計(jì)算量與維度m有關(guān)，m增加，計(jì)算量增加。內(nèi)插DE算法迭代的是一維內(nèi)插函數(shù)，因此內(nèi)插計(jì)算量比耦合DE算法的計(jì)算量小，特別當(dāng)m很大時(shí)內(nèi)插DE算法的計(jì)算量比耦合DE算法的計(jì)算量小得多。例如，對(duì)于多元SC-LDPC(4,8),m為8，w為5，L為100，耦合DE算法需要加法運(yùn)算141 200次和乘法運(yùn)算297 200次，而內(nèi)插DE算法只需要加法運(yùn)算3 400次和乘法運(yùn)算8 400次。

表3 單次迭代過(guò)程內(nèi)插DE算法與耦合DE算法計(jì)算量比較

4.3 譯碼波速度

圖4(a)、(b)、(c)分別給出了在BEC上耦合寬度w為5的多元SC-LDPC(3,6)碼、(4,8)碼和(5,10)碼，利用內(nèi)插DE算法與耦合DE算法在m為1、3、5、8時(shí)不同信道刪除概率下得到的譯碼波速度值，橫坐標(biāo)表示信道刪除概率，縱坐標(biāo)表示譯碼波速度，圓圈和點(diǎn)分別表示內(nèi)插DE算法和耦合DE算法在不同信道刪除概率下測(cè)得的速度值。當(dāng)m為1時(shí)，內(nèi)插DE算法測(cè)得的速度與耦合DE算法測(cè)得的速度相等；當(dāng)m分別為3、5、8時(shí)，內(nèi)插DE算法測(cè)得的速度與耦合DE算法測(cè)得的速度很接近，誤差在[0,0.05]范圍內(nèi)，特別是在信道刪除概率為BP閾值時(shí)，兩者相等?？梢?jiàn)，內(nèi)插DE算法可對(duì)BEC上多元SC-LDPC碼譯碼波速度起到很好的預(yù)測(cè)作用。

(a)多元SC-LDPC(3,6)碼

(b)多元SC-LDPC(4,8)碼

(c)多元SC-LDPC(5,10)碼圖4 耦合DE算法與內(nèi)插DE算法測(cè)得譯碼波速度

4.4 仿真結(jié)果總結(jié)

總結(jié)分析仿真結(jié)果發(fā)現(xiàn)，與耦合DE算法相比，內(nèi)插DE算法可很好地預(yù)測(cè)BEC上多元SC-LDPC碼譯碼波速度，內(nèi)插DE算法與耦合DE算法的BP閾值相等，且內(nèi)插DE算法的計(jì)算復(fù)雜度要比耦合DE算法的計(jì)算復(fù)雜度小很多，尤其當(dāng)耦合DE遞歸式為高維時(shí)。綜上所述，內(nèi)插DE算法以較低的計(jì)算復(fù)雜度達(dá)到了耦合DE算法預(yù)測(cè)譯碼波速度的效果。

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

針對(duì)BEC上多元SC-LDPC碼BP譯碼算法中譯碼波速度分析復(fù)雜度高的問(wèn)題，本文采用內(nèi)插DE算法來(lái)達(dá)到既可以準(zhǔn)確計(jì)算譯碼波速度又能降低計(jì)算復(fù)雜度的目的。內(nèi)插DE算法利用一維內(nèi)插函數(shù)在兩個(gè)非跳動(dòng)FP間插值密度。構(gòu)造了兩個(gè)轉(zhuǎn)移函數(shù)來(lái)更新內(nèi)插函數(shù)，將轉(zhuǎn)移函數(shù)進(jìn)一步轉(zhuǎn)化來(lái)減少卷積運(yùn)算，降低了計(jì)算復(fù)雜度。譯碼波的速度分析可應(yīng)用于SC-LDPC碼的度分布最優(yōu)化設(shè)計(jì)、耦合方式設(shè)計(jì)等方面。下一步將構(gòu)造并分析介于一維內(nèi)插DE算法和m維耦合DE算法間的n維內(nèi)插函數(shù)(1