0 引言

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

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

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

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

1 基本概念

1.1 LT碼

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

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

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

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

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

1.2 SC-LT碼

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

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

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

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

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

    編碼過(guò)程如圖2所示。

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

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

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

2 SC-LT碼漸近性能比較

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

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

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

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

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

    由式(4)和式(6)即可計(jì)算出規(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碼的總開(kāi)銷(xiāo)由式（2）可推導(dǎo)為式（7）：

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

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

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

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

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

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

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

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

3 SC-LT碼有限長(zhǎng)性能比較

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

3.1 有限長(zhǎng)信息位性能分析

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

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

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

3.2 不同的度分布的有限長(zhǎng)性能比較

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

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

4 總結(jié)

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

作者信息：

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

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