0 引言

    基于固定比率編碼技術(shù)和請求重傳機(jī)制的信道糾錯技術(shù)已經(jīng)很難滿足下一代互聯(lián)網(wǎng)日益增長的需求，因此無碼率碼被提了出來，它可以根據(jù)信道狀態(tài)自適應(yīng)調(diào)整碼率，提高了信息傳輸?shù)挠行?。無碼率碼用一系列信息碼生成一串無限長的編碼位，接收端收集到一定數(shù)量的編碼位后（原則上至少等于信息位數(shù)量）開始譯碼過程。如果不能從這些編碼位中恢復(fù)出所有信息位，接收端就會收集更多的編碼位再試。接收端持續(xù)這種方式直到所有的m個信息位得到恢復(fù)。如果在接收到n=m(1+O)個編碼位后譯碼成功，則這個編碼的譯碼開銷為O。這樣的方案被稱為無碼率，因為碼率并不能預(yù)先固定，碼率r=(1-ε)/(1+O)(ε為信道刪除率)，它會根據(jù)信道情況在0～1之間變化。無碼率碼非常適合于信息同時從一個發(fā)送端到多接收端的情況。

    第一個實現(xiàn)無碼率的是由LUBY M提出的LT碼^[1]：選擇度值d(d的產(chǎn)生由給定的度分布函數(shù)決定)，然后隨機(jī)從K個信息位中選擇d個信息位進(jìn)行模二加，就可以生成一個編碼位。譯碼端用低密度置信傳播Belief Propagation(BP)算法恢復(fù)信息位。

    AREF V等人提出了一種將空間耦合概念用于LT碼的新的無碼率碼結(jié)構(gòu)——空間耦合LT碼Spatially Coupled LT(SC-LT)^[2]，并針對二進(jìn)制無記憶對稱信道(BMS)用密度演進(jìn)來研究它的性能。在BMS信道此編碼獲得信道容量的一些必需條件也被推導(dǎo)出來。加入了預(yù)編碼后的空間耦合無碼率編碼的性能也被大量研究^[3-5]。大量的結(jié)果表明這些編碼可以獲得BEC信道的容量。這個結(jié)論也被文獻(xiàn)[6]證明了。相比于傳統(tǒng)LT碼，SC-LT碼要達(dá)到信道容量只需用非常簡單的度分布(規(guī)則分布就足夠了)^[7]。

    本文研究了SC-LT碼在規(guī)則度分布、不規(guī)則度分布下的漸近性能以及有限信息長度下的性能，對兩種度分布下的譯碼錯誤率以及譯碼復(fù)雜度進(jìn)行比較。

1 基本概念

1.1 LT碼

    作為第一個實際可行的噴泉編碼方案，LT碼具有簡單的編譯碼方法以及較小的譯碼開銷和編譯碼復(fù)雜度，為噴泉碼的發(fā)展奠定了基礎(chǔ)。假設(shè)信源有K個信息位，編碼過程如下：

    (1)根據(jù)度分布隨機(jī)的選擇一個度值d，其中1≤d≤K。

    (2)隨機(jī)的從信息序列中選擇d個信息位。

    (3)假設(shè)M_i是信息序列的第i個信息位，那么編碼符號輸出為其中{i₁，i₂，…，i_d}表示從信息序列中隨機(jī)選擇的信息位的下標(biāo)。

    這個過程持續(xù)進(jìn)行，直到接收的編碼包數(shù)量能夠使信息序列得到正確的譯碼。編碼過程如圖1所示。

1.2 SC-LT碼

    SC-LT碼對LT碼的編碼過程進(jìn)行了改進(jìn)，編碼之前將K個信息位分割成L個信息集合，每個集合有m個信息位K=Lm。定義一個平滑參數(shù)ω，編碼位被分成L+ω-1個集合。編碼過程如下：

    (1)隨機(jī)選擇一個整數(shù)j作為編碼位的集合位置，j∈[1，L+ω-1]。

    (2)從度分布R(x)中隨機(jī)的選擇一個度值d，其中1≤d≤mω。

    (3)在信息集合[j-ω+1，j]中mω個信息位中隨機(jī)選擇d個信息位。

    (4)將這d個信息位模二加就得到了編碼位。

    編碼過程如圖2所示。

    這里要注意：對于位于編碼集合[1，ω-1]∪[L+1，L+ω-1]的編碼位來說，如果選擇的信息位不在[1，L]范圍內(nèi)，編碼器就認(rèn)為該信息位無效（或者認(rèn)為信息位的值為0）。

    原則上，由這些mL信息位可以生成一串無限長的編碼位。假設(shè)信息在一個刪除率為ε的BEC信道上傳輸，用BEC(ε)來表示。接收端收集了一定數(shù)量的沒有被刪除的編碼位后，(至少與信息位數(shù)目相等)開始用BP算法進(jìn)行譯碼過程。如果收集到的編碼位無法恢復(fù)所有信息位，則繼續(xù)收集更多的編碼位重試，直至譯碼成功。

    隨著收到的編碼位數(shù)目的增多，每個編碼所在集合的數(shù)目趨于預(yù)期估計值。因此可以假設(shè)他們的數(shù)目是一樣的，用數(shù)字n來代表每個集合中的編碼位數(shù)。但是這里需要注意，在屬于編碼位集合[1，ω-1]∪[L+1，L+ω-1]中的編碼位數(shù)比n少。因為在編碼過程中，屬于這些集合中的部分編碼位不與任何有效的信息位(即選擇的信息位集合在[1，L]范圍之外)相聯(lián)系，這些編碼位視為無效，被忽略。用o_un表示每個集合的平均開銷：

2 SC-LT碼漸近性能比較

    用BP譯碼算法譯碼時，可以用密度演進(jìn)density evolution（DE）來研究SC-LT碼在信息位無限長時的漸近性能^[9-10]。

2.1 規(guī)則度分布的漸近性能

    文獻(xiàn)[7]中證明了在BEC信道下使用規(guī)則度分布的SC-LT碼隨著度值的增大可以接近信道的容量。規(guī)則度分布指的是度值選擇一個固定值。顯然度值的選擇必須大于1，但度值的選擇不宜過大，因為隨著度值的增大，編碼復(fù)雜度也會增大。

    假設(shè)選擇的規(guī)則度分布度值為d，SC-LT碼的總開銷為^[5]：

    對于BP譯碼算法，編碼位的度值等于1是非常有必要的。使用固定的度值，除邊界集([1，ω-1]∪[L+1，L+ω-1])中的編碼位外，其他編碼位集合中的編碼位都有一個固定的度。一個足夠大的?棕使得有效數(shù)目的度1編碼位在邊界集中。

    由式(4)和式(6)即可計算出規(guī)則度分布的SC-LT碼的譯碼性能。圖3為規(guī)則度分布的SC-LT碼在二進(jìn)制刪除信道下的性能展示。參數(shù)設(shè)置：L=256，ω=3，d=5。

2.2 不規(guī)則度分布的漸近性能

    假設(shè)不規(guī)則度分布為R(x)，SC-LT碼的總開銷由式（2）可推導(dǎo)為式（7）：

    由式(8)和式(6)即可計算出不規(guī)則度分布的SC-LT碼的譯碼性能。圖4為不規(guī)則度分布的SC-LT碼在二進(jìn)制刪除信道下的性能展示。參數(shù)設(shè)置：L=256，ω=3。不規(guī)則度分布采用文獻(xiàn)[8]中介紹的。由圖4可以發(fā)現(xiàn)使用不規(guī)則度分布有良好的性能，具有極低的譯碼錯誤率。

2.3 不同度分布的漸進(jìn)性能比較

    為了研究選擇不同度分布對SC-LT碼的性能的影響，下面在譯碼錯誤率和譯碼速度兩方面進(jìn)行比較。圖5為譯碼錯誤率方面的比較。因為采用的不規(guī)則度分布的平均度值為5.87，所以將其與度值為5和6的規(guī)則度分布進(jìn)行比較。

    表1比較使用兩種度分布時的譯碼速度，顯示使用不同度分布的SC-LT碼在不同開銷下譯碼所需迭代次數(shù)。

    由圖5和表1可以發(fā)現(xiàn)，使用不規(guī)則的度分布不會增加譯碼錯誤率，但是可以減少迭代次數(shù)，大大提升譯碼速度。

    為了更直觀地比較規(guī)則度分布與不規(guī)則度分布在譯碼速度和錯誤率方面的性能，在其他參數(shù)相同的情況下，令規(guī)則度分布的度值等于不規(guī)則度分布的平均度值5.87（當(dāng)然在實際應(yīng)用中規(guī)則度分布的取值不可能為小數(shù)，這里只是為了使比較更加直觀）。

    由圖6和表2可以明顯的發(fā)現(xiàn)，使用不規(guī)則的度分布與使用規(guī)則度分布相比譯碼錯誤率相差無幾，但是前者有更快的譯碼速度。

    通過比較信息位無限長時兩種不同度分布的漸近性能，發(fā)現(xiàn)使用不規(guī)則度分布具有更快的譯碼速度。

3 SC-LT碼有限長性能比較

    本小節(jié)研究SC-LT碼在有限長度下使用兩種度分布的性能比較。

3.1 有限長信息位性能分析

    圖7展示了在信息集合中的信息位個數(shù)m不同時，規(guī)則度分布SC-LT碼的譯碼錯誤率比較，參數(shù)設(shè)置：L=256，ω=3，d=5。

    由圖7可以發(fā)現(xiàn)，隨著m的增長，SC-LT碼以更快的速度接近漸近性能，那么當(dāng)編碼時信息集合中的信息位越多，就越能在低開銷時獲得低譯碼錯誤率。

    此規(guī)律同樣也適用于使用不規(guī)則度分布的SC-LT碼。由圖8可以看出，隨著開銷的增大，有限長性能總會接近漸近性能。此外，由3.2節(jié)的結(jié)論可知，使用不規(guī)則度分布的SC-LT碼不會帶來譯碼錯誤率的升高。

3.2 不同的度分布的有限長性能比較

    為了比較使用規(guī)則度分布和不規(guī)則度分布在信息位有限長時的性能，在信息位等長的情況下將平均度值為5.87的不規(guī)則度分布與度值為5、6的規(guī)則度分布進(jìn)行對比，參數(shù)設(shè)置：L=32，ω=3。

    圖9表明，不論無限長還是有限長信息位，不規(guī)則度分布都比規(guī)則度分布具有更快的譯碼錯誤率下降速度。并且在有限長信息位時不規(guī)則度分布能以更快的速度接近漸近性能。

4 總結(jié)

    本文研究了SC-LT碼在兩種度分布下的性能，分別在信息位無限長與有限長時進(jìn)行比較，得出結(jié)論：(1)無論使用哪種度分布，編碼時信息位集合中的信息位越多越能在低開銷時獲得低譯碼錯誤率，都以更快的速度接近漸近性能。(2)使用不規(guī)則的度分布后譯碼速度加快很多。而且在有限長信息位時能以更快的速度接近漸近性能。綜合考慮譯碼錯誤率、譯碼速度以及譯碼開銷，不規(guī)則度分布與規(guī)則度分布在譯碼錯誤率相差無幾的情況下，前者能以更低譯碼開銷接近漸近性能，并且具有更快的譯碼速度，優(yōu)勢明顯，應(yīng)用前景廣闊。

參考文獻(xiàn)

[1] LUBY M.LT codes[C].43rd Annual IEEE Symposium on Foundations of Computer Science，2002：271-280.

[2] AREF V，URBANKE R L.Universal rateless codes from coupled LT codes[C].2011 IEEE Information Theory Workshop(ITW)，2011：277-281.

[3] SAKATA K，KASAI K，SAKANIWA K.Spatially-coupled precoded rateless codes[C].2013 IEEE International Symposium on Information Theory Proceedings(ISIT)，2013：2438-2442.

[4] HUSSAIN I，XIAO M，RASMUSSEN L K.Design of spatially-coupled rateless codes[C].2012 IEEE International Symposium on Personal Indoor and Mobile Radio Communications(PIMRC)，2012：1913-1918.

[5] AREF V.Spatially coupled codes for channel and source coding[D].Ph.D.dissertation，EPFL，Switzerland，2014.

[6] SAKATA K，KASAI K，SAKANIWA K.Spatially-coupled precoded rateless codes with bounded degree achieve the capacity of BEC under BP decoding[C].2014 IEEE International Symposium on Information Theory(ISIT)，2014：521-525.

[7] AREF V.Rateless codes from spatially coupled regular-LT codes[C].2015 Iran Workshop on Communication and Information Theory(IWCIT)，2015：1-6.

[8] SHOKROLLAHI A.Raptor codes[J].IEEE Transactions on Information Theory，2006，52(6)：2551-2567.

[9] RICHARDSON T，URBANKE R.Modern coding theory[M]，2008.

[10] KUDEKAR S，RICHARDSON T J，URBANKE R L.Threshold saturation via spatial coupling：why convolutional LDPC ensembles perform so well over the BEC[J].IEEE Transactions on Information Theory，2011，57(2)：803-834.

作者信息：

陳  朝，毛明慧，陳  彬，趙卓亞

（中國地質(zhì)大學(xué)（武漢） 通信工程系，湖北 武漢430074）