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

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

綜述

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

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

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

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

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

0 引言

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

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

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

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

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

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

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

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

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

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

（1）LT碼

（2）Raptor碼

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

（3）模擬噴泉碼

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

（4）BATS碼

BATS碼是Yang等[4]在2014年提出的一種將噴泉碼和隨機(jī)網(wǎng)絡(luò)編碼結(jié)合的新型無(wú)速率編碼，它在具有噴泉碼無(wú)速率、低編譯碼復(fù)雜度等特性的同時(shí)，還擁有網(wǎng)絡(luò)編碼的吞吐量增益。BATS碼的所有操作均為線性操作，因此它對(duì)丟包網(wǎng)絡(luò)以及動(dòng)態(tài)網(wǎng)絡(luò)拓?fù)渚哂泻芎玫聂敯粜浴?/p>

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

（5）OFC

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

OFC的編譯碼方法和LT碼類(lèi)似，但OFC在譯碼時(shí)只接收兩種情況的編碼符號(hào)：只包含一個(gè)接收端未知信源符號(hào)的編碼符號(hào)和只包含兩個(gè)接收端未知信源符號(hào)的編碼符號(hào)。其他編碼符號(hào)則會(huì)被直接丟棄。

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

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

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

2 經(jīng)典度分布

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

2.1 理想孤波分布

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

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

2.2 魯棒孤波分布

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

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

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

3.1 不同場(chǎng)景下的度分布

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

3.1.1 刪除信道下的度分布

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

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

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

3.1.2 無(wú)線信道下的度分布

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

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

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

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

3.1.3 分布式場(chǎng)景下的度分布

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

根據(jù)此密度演化方程可以指導(dǎo)度分布的優(yōu)化。文獻(xiàn)[38]提出類(lèi)孤子分布無(wú)速率碼用于無(wú)速率編碼和網(wǎng)絡(luò)編碼的結(jié)合，而文獻(xiàn)[39]在此基礎(chǔ)上做了改進(jìn)，形成了新的度分布。此類(lèi)分布式下的噴泉碼以及度分布的研究還有很多，然而它們都只適用于某種特殊情況，如兩信源或四信源，并沒(méi)有對(duì)信源和中繼網(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è)計(jì)方案推廣到一般的異構(gòu)網(wǎng)絡(luò)中，文獻(xiàn)[40]提出了針對(duì)一般的多信源單中繼網(wǎng)絡(luò)的廣義分布式噴泉碼，并給出了總體的編碼方案。異構(gòu)網(wǎng)絡(luò)中不同信源的譯碼失敗率是不同的，因此在這種模型中網(wǎng)絡(luò)噴泉碼的度分布函數(shù)將不能使用形如點(diǎn)對(duì)點(diǎn)通信中數(shù)字噴泉碼的一元度分布函數(shù)來(lái)表示，便提出了異構(gòu)網(wǎng)絡(luò)中多元度分布函數(shù)的概念，即：

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

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

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

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

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

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

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

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

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

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

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

3.2.1 復(fù)雜度

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

3.2.2 開(kāi)銷(xiāo)

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

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

3.2.3 可譯集大小

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

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

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

其中，

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

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

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

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

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

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

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

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

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

3.3.2 針對(duì)碼長(zhǎng)問(wèn)題的度分布優(yōu)化

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[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] 徐大專(zhuān), 許生凱, 華潔, 等. 數(shù)字噴泉碼度分布優(yōu)化設(shè)計(jì)的最新研究進(jìn)展[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] 黃靖軒, 費(fèi)澤松, 李歡. 無(wú)速率編碼及其應(yīng)用綜述[J]. 無(wú)線電通信技術(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] 段文雪, 胡銘, 周瓊, 等. 云計(jì)算系統(tǒng)可靠性研究綜述[J]. 計(jì)算機(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] 鄭志國(guó), 侯登峰. 基于可譯集大小的LT碼編碼算法的改進(jìn)[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] 雷維嘉, 張夢(mèng), 謝顯中. 基于度分布合并和可譯集優(yōu)化的LT碼度分布設(shè)計(jì)方案[J]. 電子學(xué)報(bào), 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碼中一種新的開(kāi)關(guān)度分布[J]. 西安電子科技大學(xué)學(xué)報(bào), 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ì)[J]. 電子學(xué)報(bào), 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ì)方法[J]. 桂林電子科技大學(xué)學(xué)報(bào), 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] 敖珺, 盧亞軍, 馬春波. 基于短碼長(zhǎng)的噴泉碼度分布設(shè)計(jì)[J]. 計(jì)算機(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] 李杰. 無(wú)線傳輸中短碼長(zhǎng)噴泉碼的度分布優(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] 牛芳琳, 李寶明, 陳付亮, 等. 一種改進(jìn)的基于部分信息噴泉碼度分布設(shè)計(jì)[J]. 電子學(xué)報(bào), 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] 宋鑫, 倪淑燕, 張喆, 等. 面向不等差錯(cuò)保護(hù)的低誤碼平臺(tái)LT編碼算法[J]. 通信學(xué)報(bào), 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

國(guó)家重點(diǎn)研發(fā)計(jì)劃項(xiàng)目（No.2019YFB1705703）；寧波市重大科技任務(wù)攻關(guān)項(xiàng)目（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é)碩士生，主要研究方向?yàn)闊o(wú)速率編碼、網(wǎng)絡(luò)編碼及其在工業(yè)中的應(yīng)用等。

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

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

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