許夢楠，吳雅婷，施文明，張鐘浩

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

0 引 言

空間耦合低密度奇偶校驗(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表示每符號含有的比特數(shù)[5]。SC-LDPC碼相比LDPC碼存在閾值飽和現(xiàn)象，即BP閾值飽和于最大后驗(Maximum A Posteriori,MAP)閾值[6-7]。已經(jīng)證明二元SC-LDPC碼在二進制擦除信道(Binary Erasure Channel,BEC)上存在閾值飽和現(xiàn)象[8]。對于多元SC-LDPC碼，可以借助勢函數(shù)證明在BEC上閾值飽和[9]。

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

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

1 耦合DE算法

1.1 符號和定義

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

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

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

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

1.2 BP譯碼算法中消息密度

將在BEC上傳輸?shù)南⒎植挤Q為密度，本文分析BP譯碼算法中多元SC-LDPC碼的密度演進(Density Evolution,DE)。在BP譯碼算法中VN和CN間交換的消息是非負向量r=(r0,r1,…,ri)，其中ri表示碼字符號x為xi的后驗概率。例如m=2，有四種可能的碼字符號，即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譯碼算法中跟蹤密度很困難，因為每個碼字符號有2m種可能值。幸運的是，在BEC上，BP譯碼性能不依賴具體的傳輸碼字，因此假如全為零的碼字傳輸。這樣在BEC上，消息等價于GF(2m)的一個子空間。跟蹤密度轉(zhuǎn)化為跟蹤消息的維數(shù)。消息維數(shù)為k指的是有2k非零元素?；诖耍芏妊葸M簡化為長度為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，表明碼字符號可以無錯地從傳輸?shù)南⒅凶g碼。

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

(1)

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

1.3 熵函數(shù)

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

(2)

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

1.4 多元LDPC(λ,ρ,m)

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

(3)

(4)

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

(5)

(6)

高斯二項式系數(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)

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

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

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

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

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

(13)

用S={(xi,yi)}，i∈IS表示經(jīng)過擾動擦除初始化的FP的集合，IS={0,1,…,NS-1}。經(jīng)過擾動擦除初始化的FP是嚴格按照退化排列。分析發(fā)現(xiàn)，多元SC-LDPC碼的譯碼波動態(tài)特性可以用非耦合DE遞歸式的穩(wěn)定的FP來表征。本文提出的內(nèi)插DE算法中，若FP按照嚴格的退化排列，則DP也具有單調(diào)性，所以本文提到的FP都是經(jī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ù)條件下的情形，對應(yīng)的Tanner圖，底層集成沿著耦合鏈以連續(xù)的方式放置，位置索引為連續(xù)的變量t∈R∪{±∞}。位置t處的變量節(jié)點的邊均勻隨機地連接到位置為[t,t+1)的校驗節(jié)點；同樣地，位置t處的校驗節(jié)點的邊均勻隨機地連接到位置為(t-1,t]的變量節(jié)點。令t=i/w，式(14)轉(zhuǎn)化為式(17)：

(17)

定義9將DP初始化：

(18)

這樣有

(19)

2 非耦合DE遞歸式FP和DP

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

(20)

(21)

利用單個過渡區(qū)間移動速度的正負性可預(yù)測過渡區(qū)間的收斂性，例如兩個相鄰非跳動FP{x0,x1}構(gòu)成的過渡區(qū)間τ1=τ(x0,x1,l)，如果過渡區(qū)間的移動速度v1>0，那么DP將收斂于FPx0；如果v1<0，DP將收斂于FPx1。因此，BP閾值對應(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)造兩個轉(zhuǎn)移函數(shù)來更新內(nèi)插函數(shù),如公式(23)所示:

(23)

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

(24)

(25)

(26)

(27)

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

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

(28)

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

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

(29)

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

(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 仿真分析

下面通過仿真來驗證內(nèi)插DE算法的性能，并與傳統(tǒng)的耦合DE算法進行對比。仿真采用有一個過渡區(qū)間τ1的DP，過渡區(qū)間τ1=τ(x0,x1,l)位于兩個相鄰非跳動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閾值增大且越來越接近香農(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時耦合DE算法與內(nèi)插DE算法的BP閾值比較，可以看出，耦合DE算法的BP閾值與內(nèi)插DE算法的BP閾值相等。

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

4.2 計算復(fù)雜度

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

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

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時不同信道刪除概率下得到的譯碼波速度值，橫坐標表示信道刪除概率，縱坐標表示譯碼波速度，圓圈和點分別表示內(nèi)插DE算法和耦合DE算法在不同信道刪除概率下測得的速度值。當m為1時，內(nèi)插DE算法測得的速度與耦合DE算法測得的速度相等；當m分別為3、5、8時，內(nèi)插DE算法測得的速度與耦合DE算法測得的速度很接近，誤差在[0,0.05]范圍內(nèi)，特別是在信道刪除概率為BP閾值時，兩者相等?？梢?，內(nèi)插DE算法可對BEC上多元SC-LDPC碼譯碼波速度起到很好的預(yù)測作用。

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

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

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

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

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

5 結(jié)束語

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