黃靖軒,費澤松,李 歡

(北京理工大學(xué) 信息與電子學(xué)院,北京 100091)

0 引言

無速率編碼是近十?dāng)?shù)年間興起的一種糾錯編碼方案,其概念首次由J. W. Byers 和M. Luby 等人于1998 年提出[1]。 其最基本的特點是可以對有限長的信源符號進行編碼,得到無限長的編碼符號;譯碼時,無論接收到的編碼符號是什么,只要編碼符號大于一定數(shù)量,即可完成譯碼。 這就好像用一只杯子從噴泉里接水,只要杯子滿了就行,而不用在意接了哪一滴水。 因此,無速率編碼也被稱為噴泉碼。第一種可以實際使用的無速率編碼由M. Luby 于2002 年提出,按其姓名命名為盧比變換(Luby Transform,LT)碼[2]。 隨后,A. Shokrollahi 在LT 碼的基礎(chǔ)上提出了Raptor 碼[3],通過低密度奇偶校驗(Low Density Parity Check,LDPC)碼與LT 碼的級聯(lián),降低了譯碼復(fù)雜度,并降低了錯誤平層。 此后,眾多學(xué)者針對LT 碼提出了各種改進方案,改進的手段包括優(yōu)化LT 碼編碼過程中的度分布、優(yōu)化譯碼算法以及利用反饋信道反饋譯碼狀態(tài)調(diào)整編碼策略等。

近些年來,LT 碼的一些改進思想被進一步加以研究和改進,產(chǎn)生了一些新型無速率碼。 與Raptor碼的級聯(lián)思想相似,S.Yang 等人將LT 碼和網(wǎng)絡(luò)編碼相級聯(lián),于2014 年提出了Batched Sparse (BATS) 碼[4]。 這種編碼保留了無速率碼的特性,同時降低了網(wǎng)絡(luò)編碼的復(fù)雜度。 A. Shokrollahi 和Y. Cassuto則發(fā)展了利用反饋的思想,于2015 年提出了在線噴泉碼(Online Fountain Codes,OFC)[5],將利用反饋信道的思想進行了延伸,其在線特性體現(xiàn)在接收端反饋譯碼狀態(tài),發(fā)送端根據(jù)反饋信息選擇最優(yōu)的編碼策略。 OFC 進一步簡化了LT 的編譯碼過程,利用反饋消除了錯誤平層,并且獲得了很好的部分譯碼能力和實時性。

無速率編碼不僅在理論上有了很多改進,更由于其自適應(yīng)信道質(zhì)量、編譯碼復(fù)雜度低以及性能優(yōu)異等特點,在很多場景都有很大的應(yīng)用潛力。 無速率編碼最為適合的應(yīng)用場景是廣播通信,Raptor 碼及其改進方案被廣泛用于各種廣播無線通信協(xié)議中。 此外,無速率碼低復(fù)雜度的特點非常適用于機器類通信和汽車通信等場景。 最后,在無線傳感器網(wǎng)絡(luò)、分布式存儲與計算等分布式系統(tǒng)中,由于其節(jié)點數(shù)量通常較多且不固定,也非常適合使用碼率不固定的無速率編碼。

1 LT 碼與Raptor 碼

LT 碼是最早出現(xiàn)的可實用的無速率編碼,也是被研究最多的一種無速率編碼。 Raptor 碼的出現(xiàn)時間和LT 碼相近,其基本構(gòu)造是將LT 碼與LDPC 碼級聯(lián),所以編譯碼方法和LT 碼也有很多相似之處,故本節(jié)將這2 種無速率編碼一起介紹。

1.1 LT 碼基本原理及其改進

LT 碼最早被設(shè)計用來解決二元刪除信道(Binary Erasure Channel,BEC)下的數(shù)據(jù)分發(fā)問題,傳統(tǒng)的LT 碼是一種數(shù)據(jù)包級別的編碼,工作在二元域上。 后文中,我們將編碼之前的數(shù)據(jù)統(tǒng)稱為信源符號,編碼后的數(shù)據(jù)稱為編碼符號。 LT 碼的性能主要受其編碼時的度分布函數(shù)影響,常用的譯碼算法為置信傳播(Belief Propagation,BP)算法。 在此,首先介紹LT 碼的編譯碼算法,然后介紹LT 碼的一些改進方案。

1.1.1 LT 碼編譯碼原理

(1) 編碼與RSD 分布

LT 碼的編碼過程比較簡單,即每次選擇數(shù)個信源符號進行模二和運算,計算的結(jié)果即為編碼符號。進行運算的信源符號數(shù)量稱為編碼符號的度(Degree),用d 表示。 每個編碼符號的度是隨機產(chǎn)生的,其概率由度分布函數(shù)ρ(d) 確定。 假設(shè)信源符號的數(shù)量為k,那么LT 碼的編碼過程可詳細描述如下：

① 對度分布函數(shù)ρ(d) 進行采樣,得到d;

② 從k 個信源符號中隨機選擇d 個信源符號;

③ 將所選的d 個信源符號進行模二和,得到編碼符號;

④ 重復(fù)步驟①～③,不斷生成編碼符號,直到接收端完成譯碼。

在LT 碼的編碼過程中,編碼性能主要由度分布函數(shù)確定。 M. Luby 在最早提出LT 碼時首先提出了理想孤子度分布(Ideal Soliton Distribution,ISD)：

式中,ρ(i) 是度為i 的概率。

ISD 僅僅是理論上最優(yōu)的度分布函數(shù),實際使用中性能極易受到影響,因此,M. Luby 提出了實用性更強的魯棒孤子度分布(Robust Soliton Distribution,RSD)。 首先定義τ(i) ：

(2) Tanner 圖

LT 碼本質(zhì)上是一種低密度生成矩陣(Low Density Generating Matrix,LDGM)碼,可以用Tanner 圖表示。 Tanner 圖又稱二分圖(Bi-partite Graph),如圖1 所示,圓形節(jié)點為變量節(jié)點(Variable Node),表示信源符號;矩形節(jié)點為校驗節(jié)點(Check Node),表示編碼符號。 校驗節(jié)點和變量節(jié)點以邊相連,表示該編碼符號由對應(yīng)的信源符號通過模二和運算得到。 以邊相連的2 個節(jié)點稱為相鄰節(jié)點。

圖1 LT 碼的Tanner 圖Fig.1 Tanner graph of LT codes

(3) BP 譯碼

譯碼算法主要有高斯消元法和BP 算法。 其中,高斯消元譯碼算法的性能較好,但復(fù)雜度較高;BP 算法大幅降低了復(fù)雜度,而且性能下降并不明顯。 在這里,結(jié)合Tanner 圖,介紹適用于BEC 下的BP 譯碼算法：

① 譯碼器查找d = 1 的編碼符號,如果找到則譯碼過程繼續(xù)進行,否則譯碼結(jié)束。 當(dāng)譯碼結(jié)束時,如果信源符號未能完全恢復(fù),則譯碼失敗,接收端繼續(xù)接收編碼符號,等待下次迭代譯碼。

② 譯碼器任選一個d = 1 的編碼符號,將這個編碼符號的值賦給對應(yīng)的信源符號,刪去這個編碼符號在特納圖上對應(yīng)的校驗節(jié)點及其與變量節(jié)點相連的邊。

③ 將上述信源符號對應(yīng)的變量節(jié)點與所有相鄰校驗節(jié)點對應(yīng)的編碼符號做一次模二和,其結(jié)果為相應(yīng)編碼符號的更新值;將所有相鄰編碼符號的度減1 作為度的更新值。 然后在圖上刪去這個變量節(jié)點和其所有邊。

④ 重復(fù)上述3 個步驟,直到完成譯碼或譯碼失敗。

1.1.2 LT 碼改進方案

LT 碼的性能受度分布函數(shù)的影響很大,一個更優(yōu)化的度分布函數(shù)可以帶來更好的性能;BP 譯碼算法以犧牲部分性能為代價降低了復(fù)雜度,相應(yīng)地提升部分復(fù)雜度可以獲得更好的譯碼性能。 因此,度分布函數(shù)優(yōu)化和譯碼算法改進是LT 碼改進方案的2 個主要方向。 接收端完成譯碼時,通常將一個ACK 信號反饋給發(fā)送端,通知其結(jié)束編碼流程,部分方案利用該反饋信道發(fā)送更多反饋以提高性能,這是LT 碼改進的另一個方向。

(1) 度分布

度分布是影響LT 碼性能的關(guān)鍵因素。 傳統(tǒng)的度分布設(shè)計是針對BP 譯碼算法進行的。 因為置信傳播譯碼算法從d=1 的編碼符號開始,這種編碼符號組成的集合稱為可譯集(Ripple)。 好的度分布首先必須保證BP 譯碼過程中d = 1 的編碼符號產(chǎn)生得足夠多。 提高度值較小出現(xiàn)的概率可以增加可譯集的大小,然而,如果度值較小出現(xiàn)的概率較大,則需要更多數(shù)量的編碼符號才能保證全部原始信息符號參與編碼。 一種好的度分布使接收端在使用置信傳播譯碼算法時,能以更小的譯碼開銷和更高的概率完成譯碼。

在ISD 中,可譯集大小的期望始終為1,即每次迭代中,從一個d = 1 的編碼符號開始譯碼,成功恢復(fù)一個信源符號,同時另一個編碼符號的度更新為d = 1。 ISD 理論上可以使譯碼開銷最小化,但是由于d = 1 的編碼符號數(shù)量太少,譯碼過程極易失敗。RSD 通過增加數(shù)值較小的度出現(xiàn)的概率增加了可譯集的大小,同時在i = k/R 處引入了一個峰值,以提高所有信源符號都參加編碼的概率,從而提高了對抗信道擦除的能力,增強了魯棒性。

此后,許多研究者對LT 碼的度分布做了進一步改進。 J.H. Sorensen[6]等人通過分析得出,可譯集大小應(yīng)該隨著譯碼進程的改變而減小,而非像ISD 與RSD 中一樣保持恒定,并且他們設(shè)計了相應(yīng)的度分布。 仿真結(jié)果表明,這種擁有不斷減小的可譯集大小的度分布相比RSD 有更小的譯碼開銷。此后,他們將相應(yīng)的結(jié)論推廣到了二元輸入AWGN(Binary Input AWGN,BIAWGN)信道[7],并通過仿真證明了這種優(yōu)化方法在BIAWGN 信道中可以在更小的信噪比下獲得更低的誤碼率。 K. K. Yen[8]等人針對短碼長可譯集變化較大、可能消失的特點,采取了另一種思路設(shè)計度分布函數(shù),即在提高可譯集均值的同時降低其方差。 通過這種方法優(yōu)化得到的LT 碼在短碼長下需要比RSD 更小的譯碼開銷。

以上研究主要針對編碼符號度分布函數(shù),對于信源符號采用隨機選擇的方式進行選取。 此時,如果定義信源符號的選擇次數(shù)為信源符號的度,則信源符號的度分布符合泊松分布。 在泊松分布中,d = 0 的概率總是存在的,而對于信源符號來說,d=0 意味著該符號未被選取參與編碼。 如果有符號未參與編碼,那么在譯碼時一定無法被恢復(fù)出來,因而無論度分布函數(shù)如何優(yōu)化,總有小概率出現(xiàn)信源符號未被選取導(dǎo)致譯碼失敗的情況。 對于這種情況,I.Hussain 和M. Xiao[9]等人記錄每個信源符號被選擇的次數(shù),并且優(yōu)先選擇被選擇次數(shù)最少的信源符號參與編碼,通過這種方式使LT 碼的錯誤平層得到了改善。 K. F. Hayajneh 等人同樣記錄每個信源符號的被選擇次數(shù)以改變信源符號度分布,但是他們選擇被選擇次數(shù)最多的信源符號作為d = 1的編碼符號,并通過分析證明這種選取方式降低了接收端的譯碼復(fù)雜度。 Luyao Shang 等人[10]在此基礎(chǔ)上又進行了改進,將非均勻選取拓展到了更多編碼符號中,進一步降低了接收端的譯碼復(fù)雜度。

(2) 譯碼

BP 譯碼算法是一種低復(fù)雜度的譯碼算法,這使得其譯碼性能有所下降。 最顯著的特點是,當(dāng)d = 1的編碼符號消失后,BP 譯碼將會停止,而只要編碼矩陣仍然滿秩,此時依然可以用更復(fù)雜的譯碼算法完成譯碼。 高斯消元譯碼是一種較為復(fù)雜的譯碼算法,這是一種最大似然譯碼算法,相當(dāng)于求解線性方程組。 然而,高斯消元法譯碼的復(fù)雜度太高,不太適合中長碼譯碼。 各種譯碼方案實際上是在復(fù)雜度和性能之間進行權(quán)衡。 一種比較直觀的改進方法是將BP 算法和高斯消元法結(jié)合,在BP 算法停止時使用高斯消元算法求解部分信源符號,使得可譯集重新出現(xiàn),BP 譯碼算法得以繼續(xù)。

C.Cao 等人[11]考慮了LT 碼作為數(shù)據(jù)包級別的編碼這一特點,設(shè)計了一種新的跨層譯碼算法。LT 碼在數(shù)據(jù)包間編碼之后,通常還需要在編碼符號(數(shù)據(jù)包)內(nèi)進行比特級編碼。 在BP 譯碼停止時,利用已經(jīng)恢復(fù)的數(shù)據(jù)包,可將比特級譯碼失敗的數(shù)據(jù)包重新進行最大比合并,從而增加比特級譯碼成功的數(shù)據(jù)包數(shù)量(即減小信道擦除概率),以期待BP 譯碼能夠繼續(xù)。 此外,也有學(xué)者改進了AWGN信道下的無速率碼譯碼算法。 L.He 等人[12]設(shè)計了一種擁有更快收斂速度的貪婪算法。 V. Bioglio[13]簡化了高斯譯碼算法的復(fù)雜度,并減小了譯碼時延。

(3) 反饋

在LT 碼編碼過程中,接收端通過反饋告知發(fā)送端停止發(fā)送。 既然反饋信道已經(jīng)建立,就可以更多地利用反饋信道,反饋更多的譯碼狀態(tài)信息,根據(jù)譯碼狀態(tài)信息調(diào)整編碼方式。

A.Beimel 等人[14]提出了實時(Real Time,RT)碼,這種編碼不再根據(jù)度分布隨機產(chǎn)生編碼符號的度值,而是按從小到大的順序確定編碼符號的度值,即先產(chǎn)生d = 1 的編碼符號,再產(chǎn)生d = 2 的編碼符號,直到d = k。 接收端統(tǒng)計譯碼情況,計算針對該恢復(fù)比例的最優(yōu)度值,然后通過反饋告知發(fā)送端如何改變編碼符號的度值。 對于RT 碼,接收端收到編碼符號后,立刻就能完成譯碼,而那些不能立刻譯碼的編碼符號會被丟棄,不參與后續(xù)譯碼。 與傳統(tǒng)LT 碼的“全或無”譯碼性能不同,通過這種改進,RT碼獲得了較好的實時性,即恢復(fù)出的信源符號數(shù)量隨著接收到的編碼符號數(shù)量呈近似線性上升。 但是,RT 碼需要更多的譯碼開銷。

A.Hagedorn 等人[15]基于LT 碼提出了另一種利用反饋的無速率碼方案,稱為Shifted LT(SLT)碼。 在此方案中,反饋用來告知已經(jīng)完成恢復(fù)的信源符號數(shù)量,發(fā)送端根據(jù)這數(shù)量調(diào)整LT 碼的度分布,即將編碼符號度的最小值提高。 通過這種方式,SLT 碼不具備RT 碼那么好的實時性,但是其譯碼開銷遠小于RT,且好于傳統(tǒng)LT 碼。

D.Jia 等人同樣基于LT 碼提出了另一種反饋無速率碼方案。 這種方案主要基于譯碼算法進行反饋。 具體的,當(dāng)BP 譯碼因為可譯集消失而停止時,接收端根據(jù)譯碼情況,通過反饋向發(fā)送端請求一個信源符號作為d=1 的編碼符號,從而譯碼過程可以繼續(xù)。 類似的,在LT-AF(LT Codes with Alternating Feedback)[16]方案中,ISD 中d = 1 的部分被取消了,接收通過反饋選擇一個最需要的信源符號作為d = 1 的編碼符號,而發(fā)送端通過發(fā)送這個d = 1 的編碼符號作為對接收端反饋的確認信號。 通過這種方式,LT-AF 進一步減小了譯碼開銷。

M.Hashemi 等人[17]提出了一種新的反饋方案,利用反饋信息調(diào)整信源符號的選取方式。 這種方案依然基于LT 碼的RSD 度分布,不同的是,發(fā)送端利用反饋信息可以估計每個信源符號的恢復(fù)情況。 在產(chǎn)生新的編碼符號時,發(fā)送端選擇d-1 個被估計為已恢復(fù)的信源符號和1 個被估計為未恢復(fù)的信源符號進行編碼。 通過這種方式,編碼的實時性得到了顯著提高,而譯碼開銷隨著反饋次數(shù)的增加而減小。

1.2 Raptor 碼基本原理及其改進

Raptor 碼是LT 碼的直接改進,因其優(yōu)異的性能被廣泛用于各種商用無線通信協(xié)議中,尤其是廣播通信協(xié)議。 本節(jié)簡要介紹Raptor 碼及其主要后續(xù)改進方案。

1.2.1 Raptor 碼基本原理

如前所述,LT 碼對信源符號的隨機選取不能保證所有信源符號都參與譯碼,因此不論使用何種譯碼方式,接收端都無法將他們恢復(fù)出來。 LT 碼通過提高信源符號的平均被選擇次數(shù)(即泊松分布的均值)來解決這個問題,但一方面,這導(dǎo)致了大部分信源符號被恢復(fù)出來之后,還需要一定數(shù)量的編碼符號才能完成全恢復(fù);另一方面,更高的平均被選擇次數(shù)意味著更多次的異或運算,從而導(dǎo)致編譯碼復(fù)雜度較高,為O(klog2(k)) 。

為了解決這個問題,A. Shokrollahi 使用了一個高碼率的LDPC 碼對信源符號進行預(yù)編碼,預(yù)編碼的輸出稱為中間符號,然后使用LT 碼對中間符號進行編碼,得到編碼符號。 在譯碼時,首先對LT 碼進行譯碼,這時會有少部分中間符號因為未被選擇參與LT 碼編碼,從而未能被恢復(fù);但是,再對恢復(fù)出的中間符號進行LDPC 碼譯碼,即便丟失少量中間符號,還是有大概率可以恢復(fù)出所有的信源符號。

由于存在一個高碼率的預(yù)編碼,LT 碼可以接受少部分中間符號不能恢復(fù),也就無需提高中間符號的平均被選擇次數(shù),所以在減少譯碼開銷的同時,譯碼復(fù)雜度降低到了O(k·log2(1/ε)) ,其中ε ＞0 是一個表示譯碼開銷的常量。

1.2.2 Raptor 碼改進方案

(1) 系統(tǒng)化

編碼符號包括信源符號的編碼方式稱為系統(tǒng)碼。如果用x1,…,xk表示信源符號,用y1,y2,…表示編碼符號,那么系統(tǒng)碼滿足xi= yi,i = 1,…,k。 將系統(tǒng)碼中非信源符號的部分稱為修復(fù)符號。 系統(tǒng)碼在很多應(yīng)用場景,特別是廣播場景中尤為重要。 廣播場景中可能存在大量異構(gòu)接收機,有些配有譯碼器,有些沒有譯碼器。 如果編碼方式不是系統(tǒng)碼,那么對這些不配有譯碼器的接收機來說,就需要額外發(fā)送未編碼的信息,從而降低系統(tǒng)吞吐量[18]。

系統(tǒng)化Raptor 碼的直接方案是先發(fā)送信源符號本身,然后發(fā)送Raptor 碼編碼符號作為修復(fù)符號[19]。 這種方案的問題是,其性能受到信源符號和修復(fù)符號的混合方式影響。 如果信源符號所占比重較大,則性能較好,反之較差。 這與無速率編碼“接收到足夠數(shù)量的編碼符號即可完成譯碼,而不關(guān)心接收到了哪些編碼符號”的基本思想是相悖的。

另一種方案[19]的主要思想是,假設(shè)信源符號本身是某些輸入符號通過Raptor 編碼得到的輸出符號,那么可以首先對信源符號進行譯碼得到輸入符號,再對輸入符號進行編碼,得到的輸出作為修復(fù)符號。 在譯碼時,首先對接收到的編碼符號進行譯碼得到輸入符號,再對輸入符號重新編碼得到信源符號。 這種方案的好處是,信源符號和修復(fù)符號是通過同一種Raptor 編碼規(guī)則得到的,因此信源符號和修復(fù)符號的混合方式不影響編碼性能。

(2) 失活譯碼

失活(Inactivation)譯碼算法[20]是一種結(jié)合BP譯碼和高斯消元譯碼的譯碼方式,結(jié)合了BP 譯碼低復(fù)雜度和高斯消元譯碼高可靠度的特點。 其譯碼分為3 個階段：第一階段為試譯碼,譯碼器首先尋找可以用BP 譯碼解出的中間符號,而非實際解出他們;每當(dāng)BP 譯碼因可譯集消失而停止,那么選擇一個中間符號假設(shè)其已經(jīng)被恢復(fù),稱之為被失活(Inactivated),BP 譯碼器可以將其當(dāng)做可譯集而繼續(xù)下去。 第二階段為高斯譯碼階段,即使用高斯消元算法將被失活的中間符號恢復(fù)出來。 第三階段為BP 譯碼階段,在被失活的中間符號恢復(fù)之后,BP 譯碼不會再因可譯集消失而停止,可以順利完成譯碼。

值得注意的是,雖然這種譯碼方式首先被設(shè)計用來提升Raptor 碼的譯碼性能,并被廣泛應(yīng)用在RaptorQ[21]碼中,但是這種譯碼方式本質(zhì)上是對Raptor 碼中LT 碼的部分進行譯碼,因此也可以直接用來提升LT 碼的譯碼性能[22]。

2 在線噴泉碼(OFC)

OFC 是一種新型無速率編碼,其特點是接收端可以將實時譯碼狀態(tài)反饋給發(fā)送端,發(fā)送端根據(jù)反饋得到的譯碼狀態(tài)尋找對應(yīng)的最優(yōu)編碼策略。 OFC本質(zhì)上是利用反饋的LT 碼,如RT 碼和SLT 碼的延續(xù),但是整個譯碼過程更加可監(jiān)可控,是一種全新的無速率編碼。 OFC 是一種具有實時性的編碼,同時相較其他具有實時性的編碼,其譯碼開銷更小。 本節(jié)介紹OFC 的編譯碼方法和研究現(xiàn)狀。

2.1 OFC 中的一部圖與編譯碼方法

OFC 同樣是一種面向BEC 的二元域無速率編碼,其編碼的編譯碼方法和LT 碼基本類似。 編碼時,同樣隨機選擇d 個信源符號通過模二和產(chǎn)生編碼符號;譯碼時,同樣將編碼符號與已恢復(fù)的信源符號模二和,得到未恢復(fù)的信源符號。 不同的是,OFC的譯碼算法進行了進一步簡化,只接收以下2 種情況的編碼符號：

① 編碼符號由m-1 個接收端已知的信源符號和1 個接收端未知的信源符號模二和得到;

② 編碼符號由m-2 個接收端已知的信源符號和2 個接收端未知的信源符號模二和得到。

其他情況的編碼符號將會被直接丟棄,不做處理。

譯碼器的接收規(guī)則決定了只存在最多2 個未知符號進行模二和的情況,因此,OFC 的譯碼狀態(tài)可以通過一種簡化的譯碼圖來表示,稱為一部圖(Uni-partite Graph)。 與特納圖不同,一部圖中只存在信源節(jié)點,不存在校驗節(jié)點。 如果節(jié)點為黑色,表示其在接收端已知;如果為白色,表示其在接收端未知。 節(jié)點之間如果以邊相連,表示對應(yīng)的信源符號之間進行過模二和。 所有連接在一起的白色節(jié)點組成一個集團(Component),集團中的節(jié)點數(shù)量稱為集團的大小(Size)。 一個不與任何其他節(jié)點相連的白色節(jié)點本身也是一個大小為1 的集團。 顯然,如果集團中的一個節(jié)點被接收端恢復(fù)出來,與之相連的白色節(jié)點就可以通過模二和得到,以此類推,整個集團都可以完成譯碼。 此時,將該集團中的所有邊刪去,其中的所有節(jié)點變?yōu)楹谏?/p>

圖2 Tanner 圖(左)和一部圖(右)的對比Fig.2 Uni-partite graph (right) and the corresponding Tanner Graph (left)

傳統(tǒng)OFC(Conventional Online Fountain Code,COFC)[23]的編碼過程可以分為建立階段(Build-up Phase)和完成階段(Completion Phase)。 假設(shè)信源符號數(shù)量為k,在線噴泉碼的編碼過程可以詳細描述如下：

① 建立階段：發(fā)送端隨機選取2 個信源符號進行模二和,產(chǎn)生一個d = 2 的編碼符號,直到接收端中最大集團的大小為kβ0,其中0 ＜β0＜1 為一個給定參數(shù)。 而后,接收端產(chǎn)生反饋給發(fā)送端,發(fā)送端改為發(fā)送一個隨機選取的信源符號作為d = 1 的編碼包,直到發(fā)送端中最大的集團被恢復(fù)出來。

② 完成階段：發(fā)送端通過反饋信息獲取接收端已恢復(fù)的編碼符號占全部編碼符號的比例β,根據(jù)下式計算當(dāng)前最優(yōu)的編碼符號度值,并隨機選擇m^ 個信源符號進行模二和,得到一個d =的編碼符號：

式中,P1(m,β) 是當(dāng)前恢復(fù)比例下度為m 的編碼符號符合情況①的概率,P2(m,β) 是度為m 的編碼符號符合情況②的概率,可分別用下式表示：

接收端接收符合規(guī)則的編碼符號并進行處理和統(tǒng)計恢復(fù)比例β,在β 值引起m^ 改變時給出反饋通知發(fā)送端。

在編碼過程中,建立階段d=2 的編碼符號可以在接收端的譯碼圖中增加邊,使譯碼圖中建立起數(shù)個集團。 根據(jù)隨機圖理論[24],這些集團會逐漸相連,形成一個較大的集團,而其他集團的大小將幾乎保持不變。 在完成階段,雖然所發(fā)送的編碼符號度值大于2,但是能被接收和處理的編碼符號在與所有已恢復(fù)的對應(yīng)信源符號模二和之后,依然是一個信源符號,或2 個未恢復(fù)的信源符號異或的結(jié)果。如果處理之后,該編碼符號包含一個信源符號,那么該符號可以使一個集團恢復(fù)出來。 如果是2 個信源符號的異或,那么該符號可以使2 個集團相連變成一個集團。 總之,被接收處理的編碼符號可以使譯碼圖中的集團數(shù)量減1。

通過接收端的反饋,具有較好的實時性,并且OFC 比RT 碼、LT 碼以及同樣具有實時性的Growth碼[25]需要更少的譯碼開銷。 同時,由于對接收的編碼符號做了限制,OFC 的接收端可以有更低的復(fù)雜度。 此外,在文獻[5]中,作者利用隨機圖理論給出了OFC 所需譯碼開銷的上界。

2.2 在線噴泉研究現(xiàn)狀

OFC 的提出時間不長,但是依然獲得了學(xué)者的關(guān)注,出現(xiàn)了較多的改進方案。

因為OFC 的編碼器同樣是隨機選取信源符號,所以同樣有LT 碼中信源符號未參加編碼的問題。T.Huang[26]等人著眼于信源符號的選取規(guī)則進行改進,并分析了改進方案的譯碼開銷。 與文獻[12]類似,改進方案中被選取次數(shù)最少的信源符號將在產(chǎn)生下一個編碼符號時優(yōu)先被選取。 通過這種方式,OFC 的譯碼開銷得到進一步減小,但實時性受到了一定的損失。

Y.Zhao 等人[27]針對OFC 譯碼器較為簡單、丟棄大量編碼符號這一問題進行了改進,將譯碼器可以接收并處理的編碼符號增加了一種情況,即編碼符號由m - 3 個接收端已知的信源符號和3 個接收端未知的信源符號模二和得到。 此外,最優(yōu)編碼符號度的計算方式也做了相應(yīng)的改變。 通過增加譯碼復(fù)雜度,減小了OFC 的譯碼開銷。 同時注意到由于COFC 中先發(fā)送d = 2 的編碼包,導(dǎo)致建立階段結(jié)束之前都不會有信源符號被恢復(fù)出來,使得譯碼的實時性很受影響,該方案還通過先發(fā)送度為1 的編碼符號提高了譯碼過程的實時性。

在文獻[28]中,一個新的理論分析框架被構(gòu)建起來。 該框架可以較為準(zhǔn)確地分析接收到的編碼符號個數(shù)與恢復(fù)出的信源符號個數(shù)之間的關(guān)系,精確度較文獻[5]有很大提高。 分析過程指出,建立階段中的編碼符號有更大概率被接收,因此改進方案通過類似系統(tǒng)化的方法提高了建立階段中d = 2 的編碼符號屬于情況①和情況②的比例,減小了完成階段需要的編碼符號數(shù)量。 其實時性比COFC 稍差,但好于文獻[26]。 其譯碼開銷和反饋數(shù)量小于COFC,但稍差于文獻[26]。 最后,通過仿真發(fā)現(xiàn),β0的取值最大不應(yīng)超過0.5。

3 BATS 碼

BATS 碼是一種新型無速率編碼。 與Raptor 碼類似,BATS 碼也是使用LT 碼與其他編碼級聯(lián)的方式提高編碼性能。 與Raptor 碼不同的是,Raptor 碼利用LDPC 碼進行預(yù)編碼,對LDPC 碼的輸出再進行LT 編碼,提高了LT 碼的全恢復(fù)能力,而BATS 碼使用LT 碼進行預(yù)編碼,對LT 碼的輸出進行隨機網(wǎng)絡(luò)編碼(Random Linear Network Coding,RLNC),在保留無速率特性的同時,降低了RLNC 的編譯碼復(fù)雜度。 本節(jié)介紹BATS 碼的編譯碼原理和研究現(xiàn)狀。

3.1 BATS 碼編譯碼原理

BATS 碼的輸入稱為輸入分組,每個分組含有T 個輸入符號。 假設(shè)有K 個輸入分組,則輸入分組構(gòu)成的矩陣表示為S=[S1,S2,…,SK] 。 編碼時,首先進行LT 碼編碼,通過度分布產(chǎn)生度值,然后隨機選擇輸入分組。 與LT 碼不同的是,這些輸入分組之間不是進行簡單的模二和,而是使用一個隨機矩陣作為生成矩陣進行編碼,得到輸出碼塊。 最后,在LT 碼輸出碼塊的內(nèi)部進行RLNC 編碼。 編碼流程可詳細表述如下：

① 根據(jù)度分布函數(shù)確定度值di;

② 從S 中隨機選取di個輸入分組生成矩陣Si;

③ 對S 中的輸入分組進行編碼,生成第i 個塊Ci,即Ci= Sigi,gi是di× M 維的隨機矩陣,在接收端已知;

④ 在Ci內(nèi)部進行RLNC 編碼, yi= CiHi=SigiHi,其中Hi是行數(shù)為M 的傳輸矩陣,在接收端已知。

在譯碼時,同樣可以使用高斯消元譯碼算法和BP 譯碼算法進行譯碼。 注意到gi和Hi在接收端已知,如果rank(giHi)=di,那么Si可以被恢復(fù)出來,后續(xù)譯碼過程和傳統(tǒng)LT 的BP 譯碼算法或高斯消元譯碼算法相同。

對于RLNC,編碼器的存儲開銷為K 個數(shù)據(jù)分組,編碼復(fù)雜度為O(TK) ;如果譯碼器采用高斯消元法,恢復(fù)出一個輸入分組的平均復(fù)雜度為O(K2+TK) 。 如果K 很大,那么RLNC 編譯碼復(fù)雜度相當(dāng)高。 使用LT 碼進行預(yù)編碼之后,RLNC 編譯碼需要處理的數(shù)據(jù)僅為某個編碼塊內(nèi)部的M 個分組,和K無關(guān),因此降低了編譯碼復(fù)雜度。

3.2 BATS 碼研究現(xiàn)狀

BATS 碼最早于2014 年由S.Yang 等人提出,此后得到了廣大學(xué)者的廣泛關(guān)注。 S. Yang 等人在2016 年又提出了BATS 碼的樹分析方法[29]。 X.Xu等人[30]研究了BATS 碼度分布與信道條件不匹配時的性能損失問題,提出了一種普適度分布,并提出了準(zhǔn)普適BATS(Quasi-universal BATS,QU-BATS)碼,可以更好地適應(yīng)信道狀態(tài)變化或未知的情況。H.Zhao[31]和S.Yang[32]等人隨后研究了BATS 碼在有限碼長下的性能分析問題。

4 無速率編碼的應(yīng)用

無速率碼最初的設(shè)計目標(biāo)是應(yīng)用在廣播和數(shù)據(jù)分發(fā)場景中,最廣泛的應(yīng)用也是在廣播場景中。 除了廣播之外,無速率編碼因為其編譯碼復(fù)雜度低、碼率可靈活調(diào)整等特點,在深空通信、水中通信、認知無線電網(wǎng)絡(luò)、汽車通信、無線傳感器網(wǎng)絡(luò)、存儲和計算等應(yīng)用中都有較大的應(yīng)用潛力。 本節(jié)介紹無速率編碼在廣播系統(tǒng)中的應(yīng)用,以及將無速率編碼應(yīng)用在汽車通信、無線傳感器網(wǎng)絡(luò)、存儲和分布式計算場景中的研究。

4.1 廣播通信與不等差保護

在廣播場景中,LT 碼的無速率特性只要求所有接收端在完成譯碼后反饋一個ACK 信號,沒有完成譯碼的接收機可以繼續(xù)接收更多的編碼符號,數(shù)量足夠時總能完成譯碼;發(fā)送端在所有接收機反饋ACK 信號后停止廣播。 通過這種方式,LT 碼避免了在廣播系統(tǒng)中使用ARQ/HARQ 可能存在的復(fù)雜反饋。

Raptor 碼及其改進方案作為性能更好的無速率編碼,被廣泛應(yīng)用在各種廣播通信的商用標(biāo)準(zhǔn)中,如蜂窩移動通信中的多媒體廣播與多播(Multimedia Broadcast Multicast Service,MBMS)[33]以及數(shù)字視頻廣播(Digital Video Broadcasting,DVB)系列標(biāo)準(zhǔn)中的手持設(shè)備標(biāo)準(zhǔn)DVB-H[34]。 Y.Suh 等人[35]研究了一種特殊場景下的廣播方案。 此場景關(guān)注第2 次廣播的情況,即接收端通過第1 次廣播已經(jīng)收到了一定數(shù)量的編碼符號,但是限于信道條件等因素不能完全恢復(fù)出全部的信源符號。 文中將這種接收端稱為中間狀態(tài)用戶(Intermediate-State Users)。 中間狀態(tài)用戶可以在第2 次廣播前通過反饋,將其狀態(tài)信息告知發(fā)送端。 該文針對這種情況設(shè)計了2 種度分布,獲得了比傳統(tǒng)LT 碼更好的恢復(fù)性能。 S. S.Borkotoky 等人[36]研究了無速率編碼在多跳無線網(wǎng)絡(luò)數(shù)據(jù)分發(fā)中的應(yīng)用。

在廣播場景,特別是多媒體廣播中,通常不同的信源符號有不同的優(yōu)先級。 如H.264 格式中,信源符號分為基本層和增強層,信道條件較差的用戶可以先恢復(fù)出基本層,播放分辨率較低的視頻,而信道條件較好的用戶可以同時恢復(fù)出基本層和增強層,播放分辨率較高的視頻。 這就需要糾錯編碼對信源符號進行不等差保護(Unequal Error Protection,UEP)。

對于LT 碼,最經(jīng)典的UEP 方法有權(quán)重選擇法[37]和擴展窗法[38]。 權(quán)重選擇法將不同優(yōu)先級的信源符號賦予不同權(quán)重,在選擇信源符號進行模二和產(chǎn)生編碼符號時,權(quán)重越高的信源符號更有可能被選擇。 擴展窗法將信源符號劃分為存在嵌套的窗。 以信源符號分為高優(yōu)先級和低優(yōu)先級2 層為例,擴展窗法將產(chǎn)生2 個窗：小窗對應(yīng)高優(yōu)先級信源,大窗對應(yīng)全部信源。 產(chǎn)生編碼符號時,首先確定在哪個窗內(nèi)進行選擇,然后再從該窗內(nèi)隨機選擇信源符號進行編碼。 此時,即使選擇2 個窗的概率相同,高優(yōu)先級的信源符號也有更高的概率被選擇參與編碼。 S. Ahmad 等人[39]提出了一種基于信源符號擴展的不等差保護方法,高優(yōu)先級的信源符號將被擴展更高的倍數(shù),以提高其被選擇的概率。 此外,擴展窗法和權(quán)重選擇法也被應(yīng)用于OFC[40-41]和BATS 碼[42]進行UEP。

4.2 汽車通信

汽車通信場景一方面對時延要求較高,而使用ARQ/HARQ 等傳統(tǒng)糾錯模式會使通信時延增加,而無速率碼可以部分代替ARQ/HARQ 機制,從而降低時延。 另一方面,汽車通信中的高移動性會使信道狀態(tài)不斷變化,獲取準(zhǔn)確的信道狀態(tài)信息較為困難,而無速率碼可以自適應(yīng)不同的信道狀態(tài),從而更好地應(yīng)對信道狀態(tài)不斷變化的情況。 因此,無速率編碼在汽車通信場景中有較好的應(yīng)用潛力。

在文獻[43]中,LT 碼被應(yīng)用在車載自組織網(wǎng)絡(luò)(Vehicular Ad-hoc NETworks,VANETs)中,以應(yīng)對VANETs 中網(wǎng)絡(luò)拓撲結(jié)構(gòu)變化較大、失聯(lián)情況時有發(fā)生的問題。 在文獻[44]中,作者用大量的仿真證實了在汽車通信場景中使用Raptor 碼比使用IEEE 802.11p 標(biāo)準(zhǔn)中的ARQ 機制性能更加優(yōu)異,可以大幅提升系統(tǒng)吞吐量,減少譯碼時延。 Y. Gao等人[45]將BATS 碼應(yīng)用在汽車通信中的數(shù)據(jù)分發(fā)中,并提出了一個新的系統(tǒng)模型。 在該模型中,首先由路邊單元(Roadside Unit,RSU)通過無速率編碼將數(shù)據(jù)分發(fā)給車輛,隨后車輛內(nèi)部進行汽車間通信,通過網(wǎng)絡(luò)編碼的方式完成數(shù)據(jù)分發(fā),從而降低傳輸時延。

4.3 無線傳感器網(wǎng)絡(luò)

在無線傳感器網(wǎng)絡(luò)中,多個分布式數(shù)據(jù)源通過一個或多個中繼將數(shù)據(jù)發(fā)送給接收端。 由于每個數(shù)據(jù)源的碼長較短,如果在每個數(shù)據(jù)源內(nèi)部進行單獨編碼,無速率碼的隨機性會導(dǎo)致編碼性能較差。 為解決這個問題,S. Puducheri 等人提出了分布式LT(Distributed LT,DLT)碼[46]。 DLT 通過將RSD 去卷積的方式使LT 碼分解,每個分布式信源通過DLT碼編碼后,編碼符號在中繼處再通過模二和組合起來,最終產(chǎn)生的編碼符號和對所有信源符號統(tǒng)一使用RSD 分布編碼得到的編碼符號相同,從而使編碼性能獲得提升。 在分布式信源數(shù)量較少的情況下,編碼符號的最大度值受到節(jié)點數(shù)量的限制,從而使性能受到影響。 I. Hussain 等人[47]利用緩存存儲部分之前接收到的符號參與當(dāng)前編碼,從而部分減輕了這種限制,并且在文獻[48]中分析并改善DLT 碼的錯誤平層。

此外,L.Sun 等人[49]利用無速率編碼實現(xiàn)了無線傳感器網(wǎng)絡(luò)中的安全協(xié)作傳輸。 H.U.Yildiz 在水下無線傳感器網(wǎng)絡(luò)中利用無速率編碼代替?zhèn)鹘y(tǒng)ARQ 機制,從而減少了能量消耗,提高了傳感器的使用壽命,并且文章通過大量的仿真比較了單純使用無速率編碼方案和使用無速率編碼-ARQ 混合方案的性能。 B.Yi 等人[50]將OFC 應(yīng)用在了無線傳感器網(wǎng)絡(luò)中進行數(shù)據(jù)收集。

4.4 存儲

由于其復(fù)雜度低、可以任意調(diào)整冗余數(shù)量的特點,無速率碼在存儲系統(tǒng)中也有較大的應(yīng)用潛力。C.Anglano 等人[51]考慮了LT 碼在云存儲系統(tǒng)中的應(yīng)用,發(fā)現(xiàn)基于LT 碼的云存儲系統(tǒng)在可靠性、安全性等方面相比傳統(tǒng)云存儲系統(tǒng)都存在較大優(yōu)勢。H.Lu 等人[52]研究了在基于LT 碼的存儲系統(tǒng)中如何優(yōu)化檢索方式以降低時延。 T.Okpotse 等人[53]研究了將系統(tǒng)LT 碼應(yīng)用在分布式存儲系統(tǒng)中的情況,并提出了一個截斷泊松分布作為LT 碼編碼符號的度分布,從而使用較低的譯碼開銷保證了低復(fù)雜度譯碼。

4.5 分布式計算

分布式計算系統(tǒng)中通常使用MapReduce 結(jié)構(gòu)[54],這種結(jié)構(gòu)分為3 個階段：映射(Map)、數(shù)據(jù)交換(Data Shuffling)和縮減(Reduce)。 在映射階段,分布式結(jié)算節(jié)點處理計算任務(wù),并根據(jù)其映射函數(shù)產(chǎn)生中間值。 在數(shù)據(jù)交換階段,不同計算節(jié)點之間交換中間值。 最后,在縮減階段,通過縮減函數(shù)對中間值進行計算得到最終輸出結(jié)果。 分布式計算中的編碼策略可以分為2 種：① 最小時延編碼(Minimum latency codes),通常使用糾錯編碼,通過引入冗余的計算節(jié)點,使得計算網(wǎng)絡(luò)對部分節(jié)點丟失不敏感,只要一定數(shù)量的節(jié)點完成了計算任務(wù),就可以得到最終計算結(jié)果,從而增強了網(wǎng)絡(luò)的可靠性,降低了時延;② 最小帶寬編碼(Minimum bandwidth codes),通常使用網(wǎng)絡(luò)編碼,通過在每個節(jié)點引入冗余計算量,減小每個節(jié)點在數(shù)據(jù)交換階段需要進行通信的數(shù)據(jù)量。

BATS 碼本身就是LT 碼(糾錯碼的一種)和網(wǎng)絡(luò)編碼的級聯(lián),因此非常適合分布式計算系統(tǒng)。J.Yue 等人將BATS 碼應(yīng)用在分布式計算系統(tǒng)中,并用于工業(yè)控制[55],同時減小了冗余計算量、通信數(shù)據(jù)量和計算時延。 A.Severinson 等人將使用失活譯碼器的LT 碼應(yīng)用在分布式計算系統(tǒng)中[56],以增加通信數(shù)據(jù)量為代價減小了計算時延,在計算時延存在限制的場景中獲得了良好的性能。

5 結(jié)束語

本文介紹了無速率編碼的編碼方案和發(fā)展過程,梳理了無速率編碼的發(fā)展脈絡(luò),并介紹了無速率編碼在不同場景中的應(yīng)用。 無速率編碼是一類編譯碼復(fù)雜度低、碼率靈活且性能優(yōu)異的糾錯編碼。 從LT 碼被提出后,廣大學(xué)者從級聯(lián)、度分布優(yōu)化、譯碼改進以及利用反饋4 個方面對其進行改進,并從級聯(lián)改進中衍生出Raptor 碼和BATS 碼,從反饋改進中衍生出OFC。 無速率編碼被廣泛應(yīng)用于廣播通信等經(jīng)典場景,并在車聯(lián)網(wǎng)、存儲系統(tǒng)、分布式計算網(wǎng)絡(luò)等新興應(yīng)用場景中有較大的應(yīng)用潛力。 隨著BATS 碼和OFC 兩種新型無速率編碼的發(fā)展,無速率編碼將會在更廣泛的場景中發(fā)揮更大的作用。