喬越，伏玉筍，原牧云，唐金輝

綜述

無速率編碼中度分布的研究和發(fā)展

喬越1,2，伏玉筍2,3,4，原牧云1,2，唐金輝2

（1. 上海交通大學(xué)寧波人工智能研究院，浙江 寧波 315000；2. 上海交通大學(xué)電子信息與電氣工程學(xué)院，上海 200240；3. 系統(tǒng)控制與信息處理教育部重點實驗室，上海 200240；4. 上海工業(yè)智能管控工程技術(shù)研究中心，上海 200240）

無速率編碼作為一種糾刪碼，在減少反饋重傳的同時也具有碼率靈活、編譯碼簡單的特性，在許多領(lǐng)域都有廣闊的應(yīng)用前景。度分布作為無速率編碼設(shè)計的基礎(chǔ)，對無速率編碼的性能有至關(guān)重要的影響。隨著無速率編碼的廣泛應(yīng)用，度分布的設(shè)計也需要隨著場景和需求的變化進行優(yōu)化。首先論述了無速率編碼的發(fā)展與應(yīng)用，從幾種經(jīng)典的無速率編碼和度分布開始，詳細地從應(yīng)用場景、優(yōu)化目標(biāo)以及現(xiàn)有優(yōu)化方法3個角度，對目前無速率編碼中度分布的研究和發(fā)展進行了總結(jié)與分析。最后，對無速率編碼和度分布的發(fā)展應(yīng)用趨勢進行了分析與展望。

無速率編碼；噴泉碼；度分布；網(wǎng)絡(luò)編碼；多路徑

0 引言

隨著網(wǎng)絡(luò)的發(fā)展，人與人、人與物、物與物之間的連接越來越緊密，隨之而來的就是海量的信息傳輸，這對通信技術(shù)提出了更高的要求，同時推動了通信技術(shù)的快速發(fā)展。

在網(wǎng)絡(luò)數(shù)據(jù)傳輸中，傳輸控制協(xié)議是常見的用來保證信息可靠傳輸?shù)耐ㄐ艆f(xié)議，在正確接收到每個包后，接收端會通過反饋信道向發(fā)送端發(fā)送確認信息。如果發(fā)送端接收到重傳的請求，或者發(fā)送端并未接收到確認信息，就需要重新發(fā)送這個數(shù)據(jù)包，直到接收到確認信息。這種傳輸機制固然會使信息的傳輸變得可靠，但同時也會帶來一些弊端，例如，當(dāng)發(fā)送端和接收端距離較遠時，發(fā)送端需要長時間接收來自接收端的反饋信息，在此期間發(fā)送端不能再進行發(fā)送，導(dǎo)致較大的傳輸時延。同時，當(dāng)信道情況較差時，接收端很難正確接收信息，會不斷請求發(fā)送端重傳信息，形成“反饋風(fēng)暴”，導(dǎo)致大量的資源浪費在反饋和重傳上。

為了應(yīng)對這一問題，一種不需要反饋重傳的編碼技術(shù)應(yīng)運而生，即糾刪碼技術(shù)。在糾刪碼中，發(fā)送端先對原始信息進行編碼，在信道傳輸中可能會丟失部分的碼字，但是在接收端仍然可以根據(jù)接收到的部分碼字恢復(fù)全部信息。這樣就在沒有反饋重傳的情況下實現(xiàn)了可靠傳輸，避免了“反饋風(fēng)暴”的產(chǎn)生，但是這種糾刪碼仍然存在不足之處，比如在信道狀態(tài)不斷變化的情況下，固定的編碼速率難以保持良好的通信，同時編譯碼速度慢，導(dǎo)致時延增加。因此，一種無速率的、編譯碼簡單的糾刪碼技術(shù)——無速率編碼，產(chǎn)生了。

無速率編碼也叫數(shù)字噴泉碼，采用數(shù)字噴泉編碼的網(wǎng)絡(luò)，發(fā)送端將信息像噴泉一樣源源不斷地發(fā)出，數(shù)字噴泉碼示意圖如圖1所示，水滴就是發(fā)送出去的編碼符號，接收端則像一個在噴泉下接水的杯子，只要杯子裝滿了水，不管裝的是哪些水滴，都代表接收到足夠的編碼符號來譯碼出原始信息。這正是數(shù)字噴泉碼名稱的由來。數(shù)字噴泉編碼具有無碼率的特性，可以按照某個概率分布產(chǎn)生任意數(shù)量的碼字，因此可以通過自適應(yīng)信道狀態(tài)來改變碼率，而這個概率分布就是本文重點研究的度分布。

圖1 數(shù)字噴泉碼示意圖

無速率編碼自提出以來就受到了廣泛的關(guān)注。自2002年Luby[1]提出第一種可以實際使用的無速率編碼——盧比變換（Luby transform，LT）碼以來，多種無速率編碼在此基礎(chǔ)上被提出，主要有Raptor碼[2]、模擬噴泉碼[3]、分批稀疏（batched sparse，BATS）碼[4]以及在線噴泉碼（online fountain code，OFC）[5]等。它們或是在編碼結(jié)構(gòu)上加以組合擴展，或是在編碼方法上進行改造，從而提升無速率編碼的譯碼成功率。無速率編碼由于具有復(fù)雜度低、碼率靈活等特性，擁有十分廣泛的應(yīng)用場景，比如存儲、廣播通信和無線傳感器等。目前，無速率編碼已經(jīng)被寫入第三代合作伙伴計劃（3rd Generation Partnership Project，3GPP）、手持數(shù)字視頻廣播（digital video broadcasting-handheld，DVB-H）等國際標(biāo)準(zhǔn)，同時也正在參與其他多項國際標(biāo)準(zhǔn)的制定，擁有廣闊的應(yīng)用前景。度分布的設(shè)計是無速率編碼中非常重要的一環(huán)，度分布的好壞直接影響噴泉碼的性能。一個優(yōu)秀的度分布需要能在盡可能少地接收編碼符號的同時保證較高的譯碼成功率，而且保持較低的編譯碼復(fù)雜度。隨著無速率編碼的應(yīng)用逐漸廣泛，度分布也有了各種發(fā)展，比如不同應(yīng)用場景下的度分布、不同優(yōu)化目標(biāo)的度分布等。盡管目前已經(jīng)有一些關(guān)于數(shù)字噴泉碼和度分布的綜述性論文[6-8]，但是這些論文中都缺少對度分布全面詳細的介紹，比如聯(lián)合度分布和針對碼長問題的度分布，也缺少對度分布的研究整合，比如對度分布的優(yōu)化目標(biāo)的總結(jié)。因此本文希望能夠從多個角度對度分布的研究進行分析總結(jié)，從而為無速率編碼度分布的設(shè)計和優(yōu)化提供參考。

1 無速率編碼發(fā)展與應(yīng)用總結(jié)

如前所述，無速率編碼也被稱作數(shù)字噴泉碼，能夠不受固定碼長的限制，產(chǎn)生任意多的編碼符號[9]。同時它只需接收一定數(shù)量的編碼符號就可以完成譯碼，對符號的接收順序并沒有要求。

輸入符號和輸出符號之間的關(guān)系可以用二分圖表示[11]，這種用二分圖表示輸入輸出符號之間關(guān)系的方法由Tanner提出，因此也叫Tanner圖，此處不再對Tanner圖展開介紹。

目前的無速率編碼主要有LT碼、Raptor碼、模擬噴泉碼、BATS碼、OFC等。下面對這些無速率編碼的特點和優(yōu)勢進行簡單的介紹。

（1）LT碼

（2）Raptor碼

LT碼的編譯碼方法復(fù)雜度較低，但其復(fù)雜度并非線性的，而且存在“錯誤平底”現(xiàn)象[10]，因此有人提出一種新的無速率編碼——Raptor碼[2]。復(fù)雜度是指完成編碼或者完成譯碼所需要的符號操作數(shù)，Raptor碼的編譯碼復(fù)雜度均與源符號數(shù)呈線性關(guān)系，低于LT碼的復(fù)雜度。Raptor碼是對LT碼的直接改進，首先通過低密度奇偶校驗（low density parity check，LDPC）碼對信源符號進行預(yù)編碼，生成中間符號，再對中間符號用LT碼進行編碼，得到編碼符號。在譯碼時，首先對LT碼進行譯碼，再對恢復(fù)出的中間符號進行LDPC碼譯碼，即便在LT碼譯碼時丟失少量中間符號，還是有大概率可以在之后的LDPC碼譯碼中恢復(fù)出所有的信源符號。目前最新的Raptor碼——RaptorQ碼的國際標(biāo)準(zhǔn)于2011年8月發(fā)布的RFC6330標(biāo)準(zhǔn)中闡述。

（3）模擬噴泉碼

模擬噴泉碼最早由Shirvanimoghaddam等[3]在2013年提出，它為各個變量節(jié)點分配權(quán)重，最終使編碼分布能夠服從高斯分布，以此適用于無線信道的傳輸，它被證明在無線信道下能夠具有接近信道容量的性能。在編碼過程中，首先要對數(shù)據(jù)包進行二進制相移鍵控調(diào)制，再通過度分布函數(shù)采樣得到度數(shù)，之后選取個信息符號和權(quán)重系數(shù)，組合得到編碼符號。在譯碼方面，采用壓縮感知置信傳播譯碼算法，與BP譯碼不同的是，BP譯碼在變量節(jié)點和校驗節(jié)點之間傳遞信息，而壓縮感知置信傳播譯碼在變量節(jié)點和約束節(jié)點之間傳遞信息。

（4）BATS碼

BATS碼是Yang等[4]在2014年提出的一種將噴泉碼和隨機網(wǎng)絡(luò)編碼結(jié)合的新型無速率編碼，它在具有噴泉碼無速率、低編譯碼復(fù)雜度等特性的同時，還擁有網(wǎng)絡(luò)編碼的吞吐量增益。BATS碼的所有操作均為線性操作，因此它對丟包網(wǎng)絡(luò)以及動態(tài)網(wǎng)絡(luò)拓撲具有很好的魯棒性。

BATS碼在編碼時，其度分布以及編碼參數(shù)會根據(jù)傳輸文件大小、信道狀況等信息來選擇，首先對信源符號進行LT碼編碼，生成不同批次的編碼包，之后在中間節(jié)點對同一批次的編碼包進行隨機網(wǎng)絡(luò)編碼，生成BATS碼。在接收端接收了足夠數(shù)量的編碼包之后，就可以進行譯碼，目前BATS碼常用的譯碼算法包括置信度傳播譯碼算法、高斯消元譯碼算法以及基于這兩者的一些改進算法。

（5）OFC

OFC[5]是一種新型無速率編碼，本質(zhì)上是一種利用了反饋信息的LT碼，但是OFC可監(jiān)控性更高。OFC的發(fā)送端可以根據(jù)接收端反饋得到的實時譯碼狀態(tài)尋找最優(yōu)的編碼策略，是一種具有實時性的編碼，而且相比其他實時性編碼，OFC具有更小的譯碼開銷。

OFC的編譯碼方法和LT碼類似，但OFC在譯碼時只接收兩種情況的編碼符號：只包含一個接收端未知信源符號的編碼符號和只包含兩個接收端未知信源符號的編碼符號。其他編碼符號則會被直接丟棄。

最初無速率編碼的設(shè)計目標(biāo)為在廣播和數(shù)據(jù)分發(fā)場景下的應(yīng)用。而無速率編碼的編譯碼復(fù)雜度較低，而且碼率靈活，因此其在水中通信、汽車通信、存儲和計算、無線傳感器網(wǎng)絡(luò)等應(yīng)用中也有很大的潛力。無速率編碼技術(shù)以及應(yīng)用場景見表1。

表1 無速率編碼技術(shù)以及應(yīng)用場景

度分布在噴泉碼中用于指導(dǎo)編碼器按要求生成編碼信息。找到一個合適的度分布是設(shè)計噴泉碼的基礎(chǔ)，噴泉碼的效果在很大程度上是由度分布決定的。

2 經(jīng)典度分布

（3）重復(fù)以上步驟，直到完成譯碼。

2.1 理想孤波分布

ISD是一種理想狀態(tài)下的度分布，分布函數(shù)為：

一般將已經(jīng)確定而未處理的輸入符號的集合稱為可譯集，那么在某一時刻這些輸入符號的數(shù)量就是可譯集的大小。隨著譯碼過程的進行，度為1的輸出符號被釋放，越來越多的輸入符號被確定，此時可譯集的大小就會增加；而隨著輸入符號的處理，可譯集又開始減小，但同時可能會產(chǎn)生下一個能夠被釋放的輸出符號，由此生成循環(huán)。

2.2 魯棒孤波分布

除了ISD和RSD，還有多種經(jīng)典度分布函數(shù)，比如二進制指數(shù)分布（binary exponential distribution，BED）[31]、泊松分布（Poisson distribution，PD）等，許多研究都在此基礎(chǔ)上展開，此處不針對這些經(jīng)典度分布進行詳細說明，后面會對基于經(jīng)典度分布的改進進行介紹。

參考以上ISD和RSD的設(shè)計理念，可以看出度分布對無速率編碼的影響主要在于編譯碼的復(fù)雜度以及譯碼成功率，二者都是常用的度分布評價指標(biāo)。首先，當(dāng)高度值的編碼符號較多時，只需要較少的編碼符號即可覆蓋所有輸入符號，但是由于缺少低度值的編碼符號，BP譯碼很難順利進行，因此BP譯碼成功率降低，而使用GE方法進行譯碼又會增加譯碼的復(fù)雜度；當(dāng)?shù)投戎档木幋a符號較多時，固然譯碼成功率會提高，但是需要更多的編碼符號來覆蓋輸入符號，導(dǎo)致編碼復(fù)雜度較高。對噴泉碼的期望是更低的編譯碼復(fù)雜度、更高的譯碼成功率。而這些期望反映在可譯集上，即希望可譯集盡量小，但是又能以較高的概率使可譯集的大小大于或等于1。對應(yīng)到ISD和RSD上，ISD有著較低的編譯碼復(fù)雜度，而在實際應(yīng)用中的譯碼成功率卻不夠高，RSD針對可譯集大小進行了優(yōu)化，在略微提升復(fù)雜度的同時提高了譯碼成功率。后續(xù)的度分布優(yōu)化研究同樣大多致力于降低復(fù)雜度，或者提升譯碼成功率。

3 度分布設(shè)計與優(yōu)化

3.1 不同場景下的度分布

自第一個無速率編碼——LT碼以及RSD產(chǎn)生之后，由于其復(fù)雜度低、碼率靈活等特性，無速率編碼受到了越來越多的研究和關(guān)注。而隨著無速率編碼廣泛應(yīng)用于多種不同的場景，度分布的設(shè)計也由于不同場景下信道模型的差異性而發(fā)生變化，常見的有刪除信道、無線信道、分布式場景等。本節(jié)會介紹不同場景下度分布的設(shè)計與優(yōu)化方案。

3.1.1 刪除信道下的度分布

式（8）被稱為刪除信道下LT碼的密度演化方程，通常被用來對LT碼進行理論分析，也是無速率編碼度分布設(shè)計與優(yōu)化的重要工具。

根據(jù)式（8），Sejdinovic等[32]給出了刪除信道下LT碼的兩種等價的度分布線性優(yōu)化方案。這兩種優(yōu)化方案分別以最小復(fù)雜度和最小開銷為優(yōu)化目標(biāo)。Zeng等[33]研究了嚴重刪除信道下的度分布設(shè)計問題，并且提出了一種以最大平均恢復(fù)概率為目標(biāo)的度分布優(yōu)化方法。Tsai等[34]提出了新的密度演化方程來分析LT碼的漸進性能，并進行度分布優(yōu)化設(shè)計。

系統(tǒng)形式的碼字通常比非系統(tǒng)形式的碼字有更優(yōu)異的性能，而現(xiàn)有針對系統(tǒng)碼的無速率編碼度分布優(yōu)化工作比較少。Nguyen等[35]提出了系統(tǒng)LT（systematic Luby transform，SLT）碼，并給出了一種能夠在SLT碼中提供與RSD相近性能的截短度分布。同樣利用與或樹分析，可以推出SLT碼在刪除信道下的漸進性能遞推式。

3.1.2 無線信道下的度分布

最初的噴泉碼是針對刪除信道提出的，但是隨著對噴泉碼研究的深入，發(fā)現(xiàn)在噪聲信道中的噴泉碼仍然有很好的性能，這里的噪聲信道包括加性白高斯噪聲（additive white Gaussian noise，AWGN）信道以及衰落信道。因此噴泉碼也開始被應(yīng)用于無線信道中。在研究無線信道下的噴泉碼密度演化時，也可以采用類似LDPC碼的方法，但是一般會較為復(fù)雜，因此大多采用簡化后的方法，比如高斯近似方法。

Etasami等[10]利用式（10）和式（11）提出噪聲信道下噴泉碼的度分布優(yōu)化模型。

在此基礎(chǔ)上，徐大專等[6]提出了AWGN信道下SLT碼的度分布優(yōu)化模型。

除了在AWGN信道上的研究，Paul等[37]還研究和分析了LT碼在瑞利衰落（Rayleigh fading）和萊斯衰落（Rician fading）等信道中的適用性，提出了一種改進的度分布方法，以優(yōu)化衰落信道下LT碼的時延和誤碼率。Paul等[3]主要討論了改變度為1的編碼符號的比例對LT碼時延和誤碼率的影響。結(jié)果表明，在瑞利衰落信道中，基于改進度分布的LT碼在誤碼率和編譯碼時延方面有顯著的改善。

3.1.3 分布式場景下的度分布

無速率編碼以其優(yōu)良的特性受到了越來越多的關(guān)注，而隨著研究的深入，人們開始向無速率編碼引入分布式研究。當(dāng)把LT碼應(yīng)用于多信源單中繼的網(wǎng)絡(luò)，中繼節(jié)點的異或操作會使接收端收到的度分布和原始編碼器的度分布產(chǎn)生差異，最終導(dǎo)致BP算法難以有效地譯碼，產(chǎn)生較高的錯誤率。而如果在這種情況下使用GE算法，則會增加譯碼復(fù)雜度。

根據(jù)此密度演化方程可以指導(dǎo)度分布的優(yōu)化。文獻[38]提出類孤子分布無速率碼用于無速率編碼和網(wǎng)絡(luò)編碼的結(jié)合，而文獻[39]在此基礎(chǔ)上做了改進，形成了新的度分布。此類分布式下的噴泉碼以及度分布的研究還有很多，然而它們都只適用于某種特殊情況，如兩信源或四信源，并沒有對信源和中繼網(wǎng)絡(luò)做整體優(yōu)化。

根據(jù)各信源是否具有相同的度分布或者相同的接入信道容量，可以將多信源單中繼網(wǎng)絡(luò)分為同構(gòu)網(wǎng)絡(luò)和異構(gòu)網(wǎng)絡(luò)兩種模型。同構(gòu)網(wǎng)絡(luò)可以看作異構(gòu)網(wǎng)絡(luò)的特例。為了將分布式噴泉碼的度分布設(shè)計方案推廣到一般的異構(gòu)網(wǎng)絡(luò)中，文獻[40]提出了針對一般的多信源單中繼網(wǎng)絡(luò)的廣義分布式噴泉碼，并給出了總體的編碼方案。異構(gòu)網(wǎng)絡(luò)中不同信源的譯碼失敗率是不同的，因此在這種模型中網(wǎng)絡(luò)噴泉碼的度分布函數(shù)將不能使用形如點對點通信中數(shù)字噴泉碼的一元度分布函數(shù)來表示，便提出了異構(gòu)網(wǎng)絡(luò)中多元度分布函數(shù)的概念，即：

在異構(gòu)網(wǎng)絡(luò)中，信源和中繼的度分布都會影響最終無速率編碼的性能，因此可以采用分布聯(lián)合設(shè)計的方法。根據(jù)式（17）中的多元密度演化方程組，可以給出異構(gòu)網(wǎng)絡(luò)的兩步聯(lián)合優(yōu)化模型[40]。

中繼度分布優(yōu)化模型為：

信源度分布優(yōu)化模型為：

s.t.式（23）、式（24）

3.1.4 多路徑場景與融合網(wǎng)絡(luò)編碼的度分布

由于噴泉碼的無速率特性，噴泉碼和多路徑、噴泉碼和網(wǎng)絡(luò)編碼結(jié)合的研究逐漸增多。然而在這些情況下，網(wǎng)絡(luò)編碼會對節(jié)點的度分布產(chǎn)生影響，導(dǎo)致接收端收到的符號度分布與原始信息度分布不同，降低譯碼成功率。因此，結(jié)合噴泉碼與多路徑或者網(wǎng)絡(luò)編碼時，可以考慮對度分布進行重新設(shè)計。

針對高時延高損耗的子流嚴重影響其他子流導(dǎo)致顯著降低吞吐量的問題，提出簡單的基于噴泉碼的多路徑結(jié)構(gòu)[41]，如圖2所示。利用噴泉碼的靈活性，緩解了異構(gòu)路徑帶來的負面影響。此外，文獻[41]也基于噴泉碼的特性進行了數(shù)據(jù)分配方案的優(yōu)化設(shè)計。

圖2 基于噴泉碼的多路徑結(jié)構(gòu)

圖3 結(jié)合噴泉碼的蝶形網(wǎng)絡(luò)編碼

同時文獻[43]也考慮了Raptor碼經(jīng)網(wǎng)絡(luò)編碼之后節(jié)點的度分布發(fā)生改變的問題。針對這個問題，文獻[43]提出一個通過幾何規(guī)劃確定正則網(wǎng)絡(luò)拓撲中適當(dāng)?shù)脑炊确植嫉耐ㄓ脙?yōu)化問題，在設(shè)定完最終希望接收到的度分布函數(shù)后，反向推理出此時的原始節(jié)點度分布，即改進的度分布函數(shù)。最終仿真結(jié)果表明，該碼的譯碼概率和3GPP中典型的Raptor碼相近。在無速率編碼中，如果對時延沒有限制，譯碼中斷概率會趨近于0，因此設(shè)計出無速率編碼和網(wǎng)絡(luò)編碼的結(jié)合方法[44]，并以吞吐量而不是中斷概率進行性能評估，最終實現(xiàn)機器與演進型基站之間的可靠通信。

3.2 不同優(yōu)化目標(biāo)的度分布

3.2.1 復(fù)雜度

度分布的優(yōu)化可以將最小復(fù)雜度作為目標(biāo)，這里的復(fù)雜度表示輸出節(jié)點的平均度數(shù)。復(fù)雜度越高，譯碼時需要的譯碼操作數(shù)就越多，對時間以及資源的耗費就越大，因此通常會追求較低的譯碼復(fù)雜度。文獻[32]提出了一種刪除信道下的度分布優(yōu)化模型，將最小化輸出節(jié)點平均度數(shù)作為優(yōu)化目標(biāo)，將密度演化方程中每次迭代時無碼率降低作為約束條件。

3.2.2 開銷

同樣地，針對SLT碼在刪除信道以及AWGN信道下的優(yōu)化問題，根據(jù)SLT碼在兩種信道下的密度演化方程（即式（9）和式（12）～式（13）），分別給出兩種信道下以最小開銷為目標(biāo)的優(yōu)化模型[6]。兩種模型均只改變式（32）～式（34）中關(guān)于密度演化方程的約束條件，其中刪除信道下的式（33）變?yōu)椋?/p>

另外，開銷和復(fù)雜度這兩種優(yōu)化目標(biāo)均將密度演化方程推導(dǎo)出的譯碼成功率作為約束，求出最小開銷或者最小復(fù)雜度的度分布函數(shù)。相反地，將約束和目標(biāo)函數(shù)置換，就會很容易地得到另一種優(yōu)化模型：將開銷或者復(fù)雜度作為約束條件，求取能夠達到最大譯碼成功率的度分布函數(shù)。例如，文獻[45]中給出了短碼長下以最大譯碼成功率為目標(biāo)的度分布優(yōu)化模型。因為只需要將約束條件和目標(biāo)函數(shù)進行置換就可得到這樣的優(yōu)化模型，所以這里不展開介紹。

3.2.3 可譯集大小

由于無速率編碼的復(fù)雜度和開銷嚴重影響編譯碼和傳輸?shù)臅r間、資源消耗，無速率編碼受到了廣泛關(guān)注，被普遍作為度分布優(yōu)化模型的優(yōu)化標(biāo)準(zhǔn)。而除了這兩個物理量，可譯集大小的取值與波動情況也可以反映譯碼情況，因此也被當(dāng)作度分布優(yōu)化模型的優(yōu)化標(biāo)準(zhǔn)。關(guān)于可譯集的定義，在Luby[1]對LT碼的介紹中有如下說明：如果信源符號已經(jīng)被“釋放”的編碼符號恢復(fù)，但是這個信源符號還沒有被“處理”，即這個信源符號還沒有和相連的編碼符號進行異或操作，則意味著此符號可譯，稱這類符號的集合為可譯集。部分研究中也有提到輸出可譯集的概念，指在譯碼時度為1且還未“釋放”的編碼符號的集合。這兩種概念雖然具體指代的內(nèi)容不完全相同，但是其對譯碼過程的影響是大致相同的。無論是可譯集還是輸出可譯集，當(dāng)其大小在譯碼過程中變?yōu)?時，就表示BP算法失敗，此時必須采用復(fù)雜度更高的GE算法。因此需要在譯碼過程中，保證可譯集大小的均值以及方差，因此有了以可譯集大小為優(yōu)化目標(biāo)的度分布優(yōu)化模型。

從最早LT碼中RSD的研究開始[1]，針對可譯集的度分布優(yōu)化就開始了，文獻[46]給出了計算可譯集大小的方法，為了獲得更好的噴泉碼性能，文獻[47]基于可譯集大小調(diào)整了個別度值的概率，文獻[48]將可譯集大小作為優(yōu)化目標(biāo)，求解了聯(lián)合度分布的最佳比例。針對隨機圖法構(gòu)造的LT碼在中高碼長下容易譯碼失敗的問題，文獻[49]基于可譯集大小進行了優(yōu)化，提出了改進的累積邊增加法，提高了譯碼成功率。

對可譯集大小的研究是從很早就開始的，最早的RSD也可以理解為一種以可譯集大小為優(yōu)化目標(biāo)的度分布優(yōu)化模型[1]。除了Luby認為的，譯碼過程中應(yīng)保證可譯集大小不變這一觀點[1]，也有學(xué)者認為，為了減少不必要的開銷，可譯集大小應(yīng)該隨著譯碼的進行逐漸減小[50]。文獻[50]提出了一種能夠讓可譯集大小遞減的設(shè)計程序，所提方法在平均開銷和錯誤率方面的性能都有顯著提高。

其中，

基于輸出可譯集調(diào)整了編碼時度為1、度為2和最大度值的概率，提出了改進的魯棒孤波分布（modified robust soliton distribution，MRSD）[47]。文獻[47]將增大可譯集大小的均值、降低其方差轉(zhuǎn)化為一個最大化問題，同時也引入序列二次規(guī)劃算法來求解目標(biāo)函數(shù)。結(jié)果表明，通過選擇參數(shù)，MRSD比RSD有更高的譯碼成功率。此外，與其他優(yōu)化分布相比，應(yīng)用了MRSD的無速率編碼，要么有較低的輸出符號平均度數(shù)，要么需要更少的譯碼開銷。文獻[52]也通過類似方法優(yōu)化可譯集大小，進而優(yōu)化度分布函數(shù)，對取得特定度值的概率進行修改，最終得到的度分布在短碼長時也有較好的性能。

由于可譯集大小的均值和方差可以表示無速率編碼編譯碼時的性能，基于這一特性設(shè)計了度分布的優(yōu)化算法[48]。以可譯集大小的均值和方差為優(yōu)化標(biāo)準(zhǔn)，求解一種PD和RSD結(jié)合的聯(lián)合度分布的最優(yōu)比例。針對在中高碼率下使用隨機圖法構(gòu)造的LT碼有一定概率譯碼失敗的缺點，提出一種改進的累積邊增加法，能夠通過控制可譯集大小保證譯碼成功率[49]。文獻[49]分析了可譯集大小和度分布的關(guān)系，并基于此對原始方法進行改進，實驗結(jié)果表明，與傳統(tǒng)隨機圖法構(gòu)造的LT碼相比，經(jīng)過改進的LT碼性能得到了顯著提高。

3.3 度分布優(yōu)化方法分析總結(jié)

3.3.1 針對單一度分布應(yīng)用問題的度分布優(yōu)化

LT碼下，ISD在實際應(yīng)用中很容易出現(xiàn)譯碼失敗的情況，而RSD有更高的容錯率，在碼長較長時具有較理想的性能，一直被當(dāng)作理論研究的對象，但是其只能生成少量的小度值的編碼分組，隨著碼長的降低，RSD的性能下降非常明顯，采用BP譯碼很容易譯碼失敗。針對RSD的這一不足，Agha等[31]提出了BED。和RSD相比，BED增加了生成小度值編碼分組的概率，但是降低了大度值編碼分組的數(shù)量，提高了源數(shù)據(jù)不能得到良好的覆蓋從而被遺露的可能。類似的還有泊松分布，通過對PD中參數(shù)的設(shè)定，理論上PD在小度值的性能方面比BED更好，但是PD有著和BED同樣的問題，即生成了過多小度值編碼分組，而大度值編碼分組數(shù)量不足，從而遺露部分源數(shù)據(jù)。

除了針對單一度分布的處理優(yōu)化，研究人員也嘗試將性能互補的度分布結(jié)合，以提升噴泉碼的編譯碼性能。于是有了兩種結(jié)合不同度分布優(yōu)點的新的度分布——開關(guān)度分布以及聯(lián)合度分布。這兩種度分布都由多種經(jīng)典度分布的結(jié)合產(chǎn)生，開關(guān)度分布中存在開關(guān)點，通過判斷是否達到開關(guān)點來切換編碼時服從的度分布；聯(lián)合度分布將多種度分布進行求和，用比例系數(shù)控制各個度分布在整個聯(lián)合度分布中的占比。相比基于單一度分布的噴泉碼，基于開關(guān)度分布或聯(lián)合度分布的噴泉碼有更好的編譯碼性能。常見的度分布的結(jié)合有BED和RSD[52-55]、PD和RSD[48, 56]等。

針對譯碼初期由于小度值編碼分組過少而容易譯碼中斷的問題，文獻[53]給出了一種結(jié)合BED和RSD的開關(guān)度分布。這種度分布集成了BED和RSD的優(yōu)點，在編碼時，會生成較多小度值編碼數(shù)據(jù)包，便于接收端更順利地進行譯碼初期的任務(wù)。另外，采用這種開關(guān)度分布后只需要很少的編碼包就可以完成譯碼。這種開關(guān)度分布的計算式為：

同樣地，文獻[54]先對BED和RSD兩種度分布進行處理，再將兩者以開關(guān)度分布的形式結(jié)合，以實現(xiàn)度分布的優(yōu)化。文獻[52]也是先對BED進行調(diào)整，然后結(jié)合RSD，再通過優(yōu)化譯碼時的可譯集大小來優(yōu)化度分布函數(shù)，最終得到一種在短碼長下也有較好性能的度分布。文獻[57]引入改進后的冪律分布，將其與RSD結(jié)合，采用文獻[47]提出的方法求解結(jié)合比例。文獻[55]通過一種仿生算法在BED和RSD之間隨機游走，尋找更優(yōu)的度分布概率取值。

為了引入PD，文獻[56]將調(diào)整后的PD與RSD直接相加并歸一化，最終得到一個新的聯(lián)合度分布，新的度分布彌補了RSD生成小度值編碼包概率偏低的問題，提高了譯碼成功率；基于輸出可譯集的特性，文獻[48]設(shè)計了優(yōu)化算法用于求解PD和RSD結(jié)合的最優(yōu)比例，得到新的度分布。仿真結(jié)果表明，相較于RSD，采用優(yōu)化后的度分布的噴泉碼性能顯著提升。

3.3.2 針對碼長問題的度分布優(yōu)化

早期的度分布研究大多是在長碼長的情況下進行的，然而在某些實際的應(yīng)用場合中碼長是會不斷變化的，這會對噴泉碼的編譯碼產(chǎn)生影響。而且實際中大多是短碼長，而許多度分布在短碼長下性能下降十分明顯。例如當(dāng)碼長較短時，RSD雖然能生成很多大度值的編碼分組，但是由于小度值的編碼分組過少，用BP譯碼很容易失敗，而再使用GE譯碼會有巨大的開銷。因此，考慮到實際應(yīng)用中不同碼長信息對噴泉碼的需求，設(shè)計了截短度分布、固定度分布以及其他一些針對碼長問題的度分布。

在實際應(yīng)用中，噴泉碼的碼長是會發(fā)生變化的，這會對編譯碼的復(fù)雜度產(chǎn)生影響，例如當(dāng)RSD應(yīng)用在LT碼中，隨著碼長的增加，RSD生成編碼分組的平均度值增大，從而使編譯碼復(fù)雜度提高。針對這一問題，在長期的工程應(yīng)用實踐中，人們總結(jié)出一類有很強實用性的、與碼長無關(guān)的度分布函數(shù)，稱之為固定度分布。固定度分布的平均度值固定不變，不會因為碼長的變化而變化。比如泊松分布就是一類固定度分布：

這種度分布應(yīng)用在LT碼中時，平均度值固定為5.870 3，其編譯碼的復(fù)雜度與碼長呈線性關(guān)系。這樣的固定度分布同樣適用于長碼長，消除了碼長變化對編譯碼復(fù)雜度造成的影響，但是當(dāng)碼長太短時，仍然容易出現(xiàn)譯碼失敗的情況。

針對噴泉碼在短碼長下的應(yīng)用問題，許多學(xué)者提出了自己的優(yōu)化方法。例如，用一種開關(guān)度分布解決短碼長下噴泉碼譯碼成功率降低的問題[58]；提出性能模型，并采用了3種進化策略[59]；對截短度分布進行改進[60]；提出一種擴展窗-噴泉碼的方案[61]。

文獻[58]首先針對采用RSD、固定度分布和截短度分布的噴泉碼進行了性能分析和仿真，得到了不同碼長下這幾種度分布的性能情況。之后改進了一種適用于短碼長的度分布，這一度分布實際上是一種開關(guān)度分布，當(dāng)未譯碼符號數(shù)低于某個閾值時，度分布就會由原本的RSD轉(zhuǎn)變?yōu)槲墨I[58]中設(shè)計的與未譯碼符號數(shù)相關(guān)的新的度分布。實驗結(jié)果表明，在相同的譯碼開銷下，相比傳統(tǒng)的截短度分布，改進后的度分布應(yīng)用在短碼長時譯碼成功率會有很大的提升。

Zao等[59]構(gòu)建了一種新的性能模型，并提出了度分布優(yōu)化方案，該模型考慮了編碼開銷、未覆蓋符號比率和譯碼失敗率3種因素。在優(yōu)化時，提供3種已知的進化策略尋求最優(yōu)度分布，最終優(yōu)化短碼長下噴泉碼的性能。實驗結(jié)果表明，3種進化策略都能得到最優(yōu)的度分布。

李杰[60]采用與傳統(tǒng)截短度分布不同的方式進行截短。ISD和RSD的度值序列根據(jù)引入的兩個門限值以及權(quán)重進行截短，根據(jù)優(yōu)化算法，求出度分布函數(shù)中每個度值的最優(yōu)概率，得到最優(yōu)度分布，提高了譯碼性能。

文獻[61]給出了一種擴展窗-噴泉碼的方案，提出Raptor的外碼采用低碼率的LDPC碼和度分布，這樣在短碼長的情況下會比高碼率的外碼有更低的譯碼開銷。同時介紹了碼長不同時，如何為預(yù)編碼選擇合適的度分布以及碼率。

3.3.3 基于部分信息的度分布優(yōu)化

噴泉碼的出現(xiàn)是為了減少反饋重傳，從而有效降低時延，減少資源消耗，防止“反饋風(fēng)暴”的發(fā)生。然而從信息論的角度來看，噴泉碼接收端的反饋信息的確可以給編碼進行輔助，有利于提高噴泉碼的性能?，F(xiàn)有噴泉碼和理想中的噴泉碼相比，有著較大的譯碼開銷，仍然有待改進。為了對現(xiàn)有噴泉碼進行優(yōu)化，一些學(xué)者提出基于反饋信息的噴泉碼，在噴泉碼編碼時利用少量反饋信息，以此降低譯碼開銷。

為了在噴泉碼中有效地利用反饋信息，文 獻[62]提出基于反饋的實時糾錯方法，分析表明，利用反饋信息的噴泉碼可以有效降低噴泉碼的譯碼開銷。也有學(xué)者提出根據(jù)可譯集大小調(diào)整反饋信息，以此修正度分布函數(shù)，減少譯碼開銷[50,63]。文獻[64]提出有多次反饋的噴泉碼，根據(jù)接收到的編碼符號平均度發(fā)送反饋信息，以此修正度分布函數(shù)。

文獻[65]提出一種基于部分信息的噴泉碼，發(fā)送端根據(jù)接收端已知的信源符號數(shù)對RSD進行調(diào)整，以此減少譯碼開銷。文獻[65]將修正后的RSD稱為轉(zhuǎn)移RSD（shifted robust soliton distribution，SRSD）。

3.3.4 未知先驗信息的度分布優(yōu)化

不同的應(yīng)用環(huán)境對度分布有不同的需求，在設(shè)計度分布時，往往需要知道關(guān)于環(huán)境的先驗知識，然而當(dāng)環(huán)境信息（如碼長、信道信息等）難以獲取時，就難以針對性地設(shè)計出合適的度分布。針對這一問題，Savchenko等[67]提出用深度強化學(xué)習(xí)來近似/學(xué)習(xí)基于LT碼的最優(yōu)度分布的優(yōu)化方法。該方法在其意義上是簡單的，不需要復(fù)雜的分析，它能夠通過輸入符號的數(shù)量和預(yù)期接收開銷來參數(shù)化度分布，這里的預(yù)期接收開銷不一定是實際接收開銷。實驗結(jié)果表明，采用該方法學(xué)習(xí)的度分布的LT碼在譯碼效率和編譯碼復(fù)雜度方面均優(yōu)于其他方法。與其他優(yōu)化方法相比，基于深度強化學(xué)習(xí)的優(yōu)化方法有幾個優(yōu)點，比如能夠泛化到不可見的數(shù)據(jù)，以及近似復(fù)雜非線性映射的能力。該方法不需要任何關(guān)于應(yīng)用環(huán)境的先驗知識，因此，它可以直接應(yīng)用于任何基于LT碼的版本，具有很好的泛化性。文獻[68]使用強化學(xué)習(xí)的方法對一般的糾錯編碼進行設(shè)計，其中涉及線性分組碼和極化碼，但是并未對LT碼、Raptor碼等噴泉碼進行深入探討。目前在未知先驗信息的度分布優(yōu)化上的研究還相對較少，有待更深入的研究。

3.4 度分布研究的挑戰(zhàn)與展望

目前來看，對度分布的設(shè)計與優(yōu)化已經(jīng)較為系統(tǒng)，對多種信道場景和優(yōu)化目標(biāo)均有討論研究，但是仍然存在一些不足，還有許多理論和技術(shù)問題亟待解決。

（1）無速率編碼的譯碼成功率和度分布存在對應(yīng)關(guān)系，理論上存在譯碼成功率和度分布之間的換算，但是目前尚未找到計量精確且計算量低的計算方法。因此，對譯碼成功率和度分布之間關(guān)系的建模仍有待深入研究。

（2）目前的度分布優(yōu)化方法大多建立在密度演化的漸進性能分析上，然而這種方法并不能很好地適配有限長碼字的情況。雖然當(dāng)前已經(jīng)有針對短碼長下度分布的優(yōu)化，但是整體的效果仍有待提高。因此需要找到一種新的針對有限長碼字的性能分析方法，針對短碼長下的度分布進行系統(tǒng)性的優(yōu)化。

（3）隨著無速率編碼的廣泛應(yīng)用，度分布也勢必需要適配各種場景與需求。例如，針對不等差錯保護的無速率編碼研究[69]，以及無速率編碼在物聯(lián)網(wǎng)中的應(yīng)用，文獻[29]介紹了針對物聯(lián)網(wǎng)的應(yīng)用層編碼有哪些優(yōu)勢以及限制；而針對工業(yè)控制系統(tǒng)中有界時延的問題，文獻[30]對多種噴泉碼進行了對比實驗，分析發(fā)現(xiàn)噴泉碼的性能在有界時延和無時延要求下有很大的不同。同時，無速率編碼在各種場景下的具體應(yīng)用，都會對度分布產(chǎn)生新的要求，因此在更廣泛、更具體的應(yīng)用場景下，如何針對性地進行度分布的設(shè)計與優(yōu)化，仍需要持續(xù)地研究與探索。深度學(xué)習(xí)和度分布的結(jié)合也為度分布的優(yōu)化提供了新思路，當(dāng)應(yīng)用場景和需求變化時，可以很快地適配新的環(huán)境，也值得進一步的研究。

4 結(jié)束語

從無速率編碼首次提出至今，研究成果豐碩。從最初的LT碼、Raptor碼，到當(dāng)前的OFC和BATS碼，無速率編碼的性能逐漸提高，應(yīng)用領(lǐng)域也逐漸擴展，其在廣播通信、車聯(lián)網(wǎng)、分布式計算等場景中都有很大的應(yīng)用潛力。而隨著應(yīng)用場景的變化，對無速率編碼的需求也不盡相同，此時度分布也需要做出改進。本文從無速率編碼的發(fā)展和應(yīng)用開始，介紹了各種無速率編碼的特點和優(yōu)勢，總結(jié)了不同技術(shù)在多個領(lǐng)域的應(yīng)用。針對度分布的設(shè)計與優(yōu)化問題，首先從刪除信道、無線信道等不同場景進行分類介紹，之后從復(fù)雜度、開銷、可譯集大小3個方面介紹度分布的優(yōu)化目標(biāo)，最后，從無速率編碼實際應(yīng)用中可能存在的問題出發(fā)，包括單一度分布存在的問題、碼長問題、未知先驗信息的問題等，對目前已有的解決方法做出總結(jié)和分析。希望能從整體對度分布有什么問題、優(yōu)化什么、如何優(yōu)化進行探討，為相關(guān)研究人員提供借鑒。隨著無速率編碼的廣泛應(yīng)用，對度分布的研究也需要與時俱進，需要與具體的應(yīng)用環(huán)境和需求相適配，比如在工業(yè)控制環(huán)境以及物聯(lián)網(wǎng)下的應(yīng)用等，因此，后續(xù)仍然需要對度分布進行更深入的研究。

[1] LUBY M G. LT codes[C]//Proceedings of 43rd Annual IEEE Symposium on Foundations of Computer Science. Piscataway: IEEE Press, 2002: 271-280.

[2] SHOKROLLAHI A. Raptor codes[J]. IEEE Transactions on Information Theory, 2006, 52(6): 2551-2567.

[3] SHIRVANIMOGHADDAM M, LI Y H, VUCETIC B. Adaptive analog fountain for wireless channels[C]//Proceedings of 2013 IEEE Wireless Communications and Networking Conference. Piscataway: IEEE Press, 2013: 2783-2788.

[4] YANG S H, YEUNG R W. Batched sparse codes[J]. IEEE Transactions on Information Theory, 2014, 60(9): 5322-5346.

[5] LáZARO F, LIVA G, BAUCH G. Inactivation decoding of LT and raptor codes: analysis and code design[J]. IEEE Transactions on Communications, 2017, 65(10): 4114-4127.

[6] 徐大專, 許生凱, 華潔, 等. 數(shù)字噴泉碼度分布優(yōu)化設(shè)計的最新研究進展[J]. 數(shù)據(jù)采集與處理, 2015, 30(4): 733-746.

XU D Z, XU S K, HUA J, et al. Recent progress on optimization design of degree distributions in digital fountain codes[J]. Journal of Data Acquisition and Processing, 2015, 30(4): 733-746.

[7] MACKAY D J C. Fountain codes[J]. IEE Proceedings - Communications, 2005, 152(6): 1062.

[8] 黃靖軒, 費澤松, 李歡. 無速率編碼及其應(yīng)用綜述[J]. 無線電通信技術(shù), 2020, 46(1): 44-54.

HUANG J X, FEI Z S, LI H. Overview of rateless codes and their applications[J]. Radio Communications Technology, 2020, 46(1): 44-54.

[9] LUBY M G, MITZENMACHER M, SHOKROLLAHI M A. Analysis of random processes via AND-OR tree evaluation[C]//Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms. [S.l.:s.n.], 1998.

[10] ETESAMI O, SHOKROLLAHI A. Raptor codes on binary memoryless symmetric channels[J]. IEEE Transactions on Information Theory, 2006, 52(5): 2033-2051.

[11] TANNER R. A recursive approach to low complexity codes[J]. IEEE Transactions on Information Theory, 1981, 27(5): 533-547.

[12] 3GPP. Multimedia broadcast/multicast service(MBMS); protocols and codecs: TS 26. 346 V7. 2. 0[S]. 2006.

[13] ETSI T S. IP datacast over DVB-H: content delivery protocols: 102 472 v1. 2. 1[S]. 2006.

[14] JEON S Y, AHN J H, LEE T J. Reliable broadcast using limited LT coding in wireless networks[J]. IEEE Communications Letters, 2016, 20(6): 1187-1190.

[15] BORKOTOKY S S, PURSLEY M B. Fountain-coded broadcast distribution in multiple-hop packet radio networks[J]. IEEE/ACM Transactions on Networking, 2019, 27(1): 29-41.

[16] PALMA V, MAMMI E, VEGNI A M, et al. A fountain codes-based data dissemination technique in vehicular Ad-hoc networks[C]//Proceedings of 2011 11th International Conference on ITS Telecommunications. Piscataway: IEEE Press, 2011: 750-755.

[17] ABDULLAH N F, DOUFEXI A, PIECHOCKI R J. Raptor codes-aided relaying for vehicular infotainment applications[J]. IET Communications2013, 7(18): 2064-2073.

[18] GAO Y M, XU X L, GUAN Y L, et al. V2X content distribution based on batched network coding with distributed scheduling[J]. IEEE Access, 2017(6): 59449-59461.

[19] ANGLANO C, GAETA R, GRANGETTO M. Exploiting rateless codes in cloud storage systems[J]. IEEE Transactions on Parallel and Distributed Systems, 2015, 26(5): 1313-1322.

[20] LU H F, FOH C H, WEN Y G, et al. Delay-optimized file retrieval under LT-based cloud storage[J]. IEEE Transactions on Cloud Computing, 2017, 5(4): 656-666.

[21] OKPOTSE T, YOUSEFI S. Systematic fountain codes for massive storage using the truncated Poisson distribution[J]. IEEE Transactions on Communications, 2019, 67(2): 943-954.

[22] 段文雪, 胡銘, 周瓊, 等. 云計算系統(tǒng)可靠性研究綜述[J]. 計算機研究與發(fā)展, 2020, 57(1): 102-123.

DUAN W X, HU M, ZHOU Q, et al. Reliability in cloud computing system: a review[J]. Journal of Computer Research and Development, 2020, 57(1): 102-123.

[23] PUDUCHERI S, KLIEWER J, FUJA T E. The design and performance of distributed LT codes[J]. IEEE Transactions on Information Theory, 2007, 53(10): 3740-3754.

[24] HUSSAIN I, XIAO M, RASMUSSEN L K. Buffer-based distributed LT codes[J]. IEEE Transactions on Communications2014, 62(11): 3725-3739.

[25] SUN L, REN P Y, DU Q H, et al. Fountain-coding aided strategy for secure cooperative transmission in industrial wireless sensor networks[J]. IEEE Transactions on Industrial Informatics, 2016, 12(1): 291-300.

[26] YI B S, XIANG M, HUANG T Q, et al. Data gathering with distributed rateless coding based on enhanced online fountain codes over wireless sensor networks[J]. AEU - International Journal of Electronics and Communications, 2018, 92: 86-92.

[27] YUE J, XIAO M, PANG Z B. Distributed fog computing based on batched sparse codes for industrial control[J]. IEEE Transactions on Industrial Informatics, 2018, 14(10): 4683-4691.

[28] SEVERINSON A, AMAT A G I, ROSNES E. Block-diagonal and LT codes for distributed computing with straggling servers[J]. IEEE Transactions on Communications, 2019, 67(3): 1739-1753.

[29] SANDELL M, RAZA U. Application layer coding for IoT: benefits, limitations, and implementation aspects[J]. IEEE Systems Journal, 2019, 13(1): 554-561.

[30] YUAN M Y, FU Y S, QIAO Y, et al. Rateless codes for reliable and secure packet transmission in industrial control systems[C]//Proceedings of 2021 China Automation Congress (CAC). Piscataway: IEEE Press, 2021: 6376-6381.

[31] AGHA K A, KADI N, STOJMENOVIC I. Fountain codes with XOR of encoded packets for broadcasting and source independent backbone in multi-hop networks using network coding[C]//Proceedings of IEEE 69th Vehicular Technology Conference. Piscataway: IEEE Press, 2009: 1-5.

[32] SEJDINOVIC D, PIECHOCKI R J, DOUFEXI A. AND-OR tree analysis of distributed LT codes[C]//Proceedings of 2009 IEEE Information Theory Workshop on Networking and Information Theory. Piscataway: IEEE Press, 2009: 261-265.

[33] ZENG M, CALDERBANK R, CUI S G. On design of rateless codes over dying binary erasure channel[J]. IEEE Transactions on Communications, 2012, 60(4): 889-894.

[34] TSAI P C, CHEN C M, CHEN Y P. A novel evaluation function for LT codes degree distribution optimization[C]//Proceedings of 2014 IEEE Congress on Evolutionary Computation. Piscataway: IEEE Press, 2014: 3030-3035.

[35] NGUYEN T D, YANG L L, HANZO L. Systematic Luby transform codes and their soft decoding[C]//Proceedings of 2007 IEEE Workshop on Signal Processing Systems. Piscataway: IEEE Press, 2007: 67-72.

[36] WIBERG N . Codes and decoding on general graphs[D]. Linkoping: Linkoping University, 1996.

[37] PAUL I J L, RADHA S, RAJA J. Studies on the suitability of LT codes with modified degree distribution (MDD) for fading channels[C]//Proceedings of 2014 International Conference on Advances in Computing, Communications and Informatics (ICACCI). Piscataway: IEEE Press, 2014: 1764-1769.

[38] LIAU A, YOUSEFI S, KIM I M. Binary soliton-like rateless coding for the Y-network[J]. IEEE Transactions on Communications, 2011, 59(12): 3217-3222.

[39] LIAU A, KIM I M, YOUSEFI S. Improved low-complexity soliton-like network coding for a resource-limited relay[J]. IEEE Transactions on Communications, 2013, 61(8): 3327-3335.

[40] SHAO H Q, XU D Z, ZHANG X F. Asymptotic analysis and optimization for generalized distributed fountain codes[J]. IEEE Communications Letters, 2013, 17(5): 988-991.

[41] CUI Y, WANG L, WANG X, et al. FMTCP: a fountain code-based multipath transmission control protocol[J]. IEEE/ACM Transactions on Networking, 2015, 23(2): 465-478.

[42] LIMMANEE A, HENKEL W. A cooperative scheme for shaping degree distribution of LT-coded symbols in network coding multicast[C]//Proceedings of 2010 International ITG Conference on Source and Channel Coding (SCC). Piscataway: IEEE Press, 2010: 1-6.

[43] THOMOS N, FROSSARD P. Degree distribution optimization in Raptor network coding[C]//Proceedings of 2011 IEEE International Symposium on Information Theory Proceedings. Piscataway: IEEE Press, 2011: 2736-2740.

[44] NESSA A, KADOCH M. Joint network channel fountain schemes for machine-type communications over LTE-advanced[J]. IEEE Internet of Things Journal, 2016, 3(3): 418-427.

[45] HYYTIA E, TIRRONEN T, VIRTAMO J. Optimal degree distribution for LT codes with small message length[C]//Proceedings of IEEE INFOCOM 2007 - 26th IEEE International Conference on Computer Communications. Piscataway: IEEE Press, 2007: 2576-2580.

[46] MAATOUK G, SHOKROLLAHI A. Analysis of the second moment of the LT decoder[C]//Proceedings of 2009 IEEE International Symposium on Information Theory. Piscataway: IEEE Press, 2009: 2326-2330.

[47] YEN K K, LIAO Y C, CHEN C L, et al. Modified robust soliton distribution (MRSD) with improved ripple size for LT codes[J]. IEEE Communications Letters, 2013, 17(5): 976-979.

[48] 戴新穎, 王建萍. 基于輸出可譯集的LT碼聯(lián)合度分布優(yōu)化[J].系統(tǒng)工程與電子技術(shù), 2020, 42(3): 727-732.

DAI X Y, WANG J P. Optimization of combined degree distribution of LT codes based on output ripple size[J]. Systems Engineering and Electronics, 2020, 42(3): 727-732.

[49] 鄭志國, 侯登峰. 基于可譯集大小的LT碼編碼算法的改進[J]. 電視技術(shù), 2011, 35(5): 13-16.

ZHENG Z G, HOU D F. Improvement of LT encoding algorithm based on ripple size[J]. Video Engineering, 2011, 35(5): 13-16.

[50] RENSEN J H S, POPOVSKI P, OSTERGAARD J. Design and analysis of LT codes with decreasing ripple size[J]. IEEE Transactions on Communications, 2012, 60(11): 3191-3197.

[51] YEN K K, LIAO Y C, CHANG H C. Design of LT code degree distribution with profiled output ripple size[C]//Proceedings of 2015 IEEE Workshop on Signal Processing Systems (SiPS). Piscataway: IEEE Press, 2015: 1-6.

[52] 雷維嘉, 張夢, 謝顯中. 基于度分布合并和可譯集優(yōu)化的LT碼度分布設(shè)計方案[J]. 電子學(xué)報, 2015, 43(4): 800-805.

LEI W J, ZHANG M, XIE X Z. A design scheme for LT codes degree distribution by combining degree distributions and optimizing ripple size[J]. Acta Electronica Sinica, 2015, 43(4): 800-805.

[53] ZHANG M, LEI W J, XIE X Z. Combined degree distribution: a simple method to design the degree distribution of fountain codes[C]//Proceedings of 2013 IEEE Third International Conference on Information Science and Technology. Piscataway: IEEE Press, 2013: 1089-1092.

[54] 任鵬, 相征. LT碼中一種新的開關(guān)度分布[J]. 西安電子科技大學(xué)學(xué)報, 2015, 42(5): 43-47.

REN P, XIANG Z. New switch degree distribution for the LT code[J]. Journal of Xidian University, 2015, 42(5): 43-47.

[55] 姚渭箐, 胡凡. 基于IBED和仿生算法的LT碼度分布設(shè)計[J]. 電子學(xué)報, 2019, 47(2): 428-433.

YAO W Q, HU F. The design of degree distribution for LT codes based on IBED and bionic algorithm[J]. Acta Electronica Sinica, 2019, 47(2): 428-433.

[56] YAO W Q, YI B S, HUANG T Q, et al. Poisson robust soliton distribution for LT codes[J]. IEEE Communications Letters, 2016, 20(8): 1499-1502.

[57] 龔赟, 王俊義. 一種用于LT碼的新型聯(lián)合度分布設(shè)計方法[J]. 桂林電子科技大學(xué)學(xué)報, 2017, 37(5): 355-360.

GONG Y, WANG J Y. A design method of novel combined degree distribution for LT code[J]. Journal of Guilin University of Electronic Technology, 2017, 37(5): 355-360.

[58] 敖珺, 盧亞軍, 馬春波. 基于短碼長的噴泉碼度分布設(shè)計[J]. 計算機與數(shù)字工程, 2015, 43(12): 2101-2105.

AO J, LU Y J, MA C B. Fountain codes degree distribution design based on short code length[J]. Computer & Digital Engineering, 2015, 43(12): 2101-2105.

[59] ZAO J K, HORNANSKY M, DIAO P L. Design of optimal short-length LT codes using evolution strategies[C]//Proceedings of 2012 IEEE Congress on Evolutionary Computation. Piscataway: IEEE Press, 2012: 1-9.

[60] 李杰. 無線傳輸中短碼長噴泉碼的度分布優(yōu)化算法[J]. 電訊技術(shù), 2016, 56(8): 900-905.

LI J. A degree distribution optimization algorithm for small size fountain codes in wireless transmission[J]. Telecommunication Engineering, 2016, 56(8): 900-905.

[61] YUAN L, DENG K Y, LI H A. Design of finite-length precoded EWF codes for scalable video streaming[J]. Wireless Personal Communications, 2017, 97(3): 4111-4128.

[62] BEIMEL A, DOLEV S, SINGER N. RT oblivious erasure correcting[J]. IEEE/ACM Transactions on Networking, 2007, 15(6): 1321-1332.

[63] JIA D, FEI Z S, SHANGGUAN C L, et al. LT codes with limited feedback[C]//Proceedings of 2014 IEEE International Conference on Computer and Information Technology. Piscataway: IEEE Press, 2014: 669-673.

[64] HAGEDORN A, AGARWAL S, STAROBINSKI D, et al. Rateless coding with feedback[C]//Proceedings of IEEE INFOCOM 2009. Piscataway: IEEE Press, 2009: 1791-1799.

[65] AGARWAL S, HAGEDORN A, TRACHTENBERG A. Adaptive rateless coding under partial information[C]//Proceedings of 2008 Information Theory and Applications Workshop. Piscataway: IEEE Press, 2008: 5-11.

[66] 牛芳琳, 李寶明, 陳付亮, 等. 一種改進的基于部分信息噴泉碼度分布設(shè)計[J]. 電子學(xué)報, 2016, 44(2): 295-300.

NIU F L, LI B M, CHEN F L, et al. The improved degree distribution for rateless code under partial information[J]. Acta Electronica Sinica, 2016, 44(2): 295-300.

[67] SAVCHENKO Y, LIU Y. Optimizing degree distributions of LT-based codes with deep reinforcement learning[C]//Proceedings of IEEE INFOCOM 2019 - IEEE Conference on Computer Communications Workshops. Piscataway: IEEE Press, 2019: 228-233.

[68] HUANG L C, ZHANG H Z, LI R, et al. AI coding: learning to construct error correction codes[J]. IEEE Transactions on Communications, 2020, 68(1): 26-39.

[69] 宋鑫, 倪淑燕, 張喆, 等. 面向不等差錯保護的低誤碼平臺LT編碼算法[J]. 通信學(xué)報, 2022, 43(6): 85-97.

SONG X, NI S Y, ZHANG Z, et al. Low error floor LT coding algorithm for unequal error protection[J]. Journal on Communications, 2022, 43(6): 85-97.

Research and development of degree distribution in the rateless code

QIAO Yue1,2, FU Yusun2,3,4, YUAN Muyun1,2, TANG Jinhui2

1. Ningbo Artificial Intelligence Institute of Shanghai Jiao Tong University, Ningbo 315000, China 2. School of Electronic Information and Electrical Engineering, Shanghai Jiao Tong University, Shanghai 200240, China 3. Key Laboratory of System Control and Information Processing, Ministry of Education of China, Shanghai 200240, China 4. Shanghai Engineering Research Center of Intelligent Control and Management, Shanghai 200240, China

As a kind of deletion coding technology, the rateless code reduces feedback retransmission and has the characteristics of flexible bit rate and simple compilation code, which has broad application prospects in many fields. As the basis of rateless code design, degree distribution has a crucial impact on the performance of the rateless code With the wide application of the rateless code, the design of degree distribution also needs to change with changes in scenarios and needs. Firstly, the development and application of the rateless code were discussed. Starting with several classical rateless codes and degree distributions, the current research and development of the degree distribution were summarized and analyzed from three perspectives of application scenarios, optimization targets and existing optimization methods. Finally, the development and application trend of rateless codes and degree distribution were discussed.

rateless code, fountain code, degree distribution, network coding, multipath

TN911

A

10.11959/j.issn.1000?0801.2022268

2022?04?26；

2022?10?08

伏玉筍，fu_yusun@sina.com

國家重點研發(fā)計劃項目（No.2019YFB1705703）；寧波市重大科技任務(wù)攻關(guān)項目（No.2021Z022）

The National Key Research and Development Program of China (No.2019YFB1705703), The Major Scientific and Technological Research Program of Ningbo (No.2021Z022)

喬越（1999? ），男，上海交通大學(xué)碩士生，主要研究方向為無速率編碼、網(wǎng)絡(luò)編碼及其在工業(yè)中的應(yīng)用等。

伏玉筍（1972? ），男，博士，上海交通大學(xué)助理研究員，主要研究方向為無線通信與系統(tǒng)、無線網(wǎng)聯(lián)智能系統(tǒng)、工業(yè)互聯(lián)網(wǎng)與安全可信、智能制造等。

原牧云（1997? ），男，上海交通大學(xué)碩士生，主要研究方向為無速率編碼、網(wǎng)絡(luò)編碼及其在工業(yè)中的應(yīng)用等。

唐金輝（1999? ），男，上海交通大學(xué)碩士生，主要研究方向為工業(yè)通信系統(tǒng)與安全可信。