在編碼理論中，噴泉碼（也稱為無碼率抹除碼）是一類抹除碼，其有能力從一組給定的源符號中產生一串無限的編碼符號序列，而在理想情況下，只需獲得大小和源符號相同或稍大的任意編碼符號子集，便可恢復源符號。術語“噴泉”或“無碼率”是指這樣的事實：這些碼不顯示出固定的編碼率。 如果原始k個源符號可以從任意k個編碼符號中恢復，則該噴泉碼是最佳的。噴泉碼是高效的編解碼算法，因有很大概率能從任意k’個編碼符號恢復原始的k個源符號（k’僅稍大于k）而知名。 LT碼是第一種實際實現的噴泉碼。隨后提出的Raptor碼和在線碼加入了輸入符號的預編碼階段，實現線性時間的編解碼復雜度。 中文名噴泉碼外文名Fountain codes時 間1998年 目錄 1 抹除碼介紹 2 概念介紹 ? 原因 ? 發展歷史 ? 基本思想 ? 特點 ? 應用方向 ? 兩種噴泉碼 ? 技術發展 抹除碼介紹編輯 抹除碼是相對于復制而言的。使用復制的情況，我們對一個文件做幾個副本，放在不同的地方，再去管理它們。 抹除碼的思路，簡單來說，是將文件轉換成一個碎片集合，每一個碎片很小，碎片被打散分布到一組服務器資源池里。只要存留的碎片數量足夠，就可以合成為原本的文件。這可以在保持原本的數據健壯性的基礎上大大減少需要的存儲空間。 概念介紹編輯 原因 在傳統“抹除通道”上的傳輸，通常得仰賴發送端以及接收端持續性的雙向溝通：首先發送端的文件是以多個小數據包的形式進行傳輸的，一個文件被簡單粗暴地切割成k個數據包大小的片段，發送端對它們編碼后將這些帶有信息的封包發送到接收端。這些小的數據包如果在傳輸過程中產生錯誤，就會導致接收失敗，否則就能被成功接收。成功與否取決于接收端在收到每個封包時對其進行的評估，如果該封包可以被解碼，則傳送一個確認（ACK信息）給發送端；反之，丟棄毀壞的封包，并傳送請求讓發送端再次發送該封包。顯然，在這種通道上還會需要一個用于確定哪些數據包需要被重新傳送的反向通道（back channel）。該雙向溝通會持續進行直到所有信息的封包都被成功傳送且解碼為止。 [1] 隨著因特網的迅猛發展，人們在享受信息傳遞的方便與快捷的同時也對通信系統的服務能力和范圍提出了更高的要求，有限的網絡帶寬與迅速增長的網絡數據量和下載規模之間形成了一對亟需解決的矛盾。因特網中可靠的數據傳輸一直是許多研究的熱點。很多時候，可靠性是靠使用合適的協議來保證的。例如，普遍使用的TCP/IP用重傳機制來保證傳輸的可靠性。但是在很多情況下，TCP/IP協議并不適用，如點到多點傳輸，或在嚴重損壞的信道上進行傳輸（質量很差的無線或衛星鏈路）?；诜答佒貍鞯腡CP在傳輸距離太長的時候性能很差，因為長距離導致發送方等待反饋確認信息時的空閑時間太長。同時，單一刪余信道的模型不適用于數據從一個發送者同時發送到多個接收者的情況。在這種情況下，從發送者到多個接收者的刪余信道的刪余概率可能不同。當接收者數量很多時，不太可能估計每個信道的刪余率和丟包情況，因此，需要構造可靠的傳輸方案。 發展歷史 針對這一問題， John Byers及Michael Luby等人于1998年首次提出了數字噴泉（Digital Fountain）的概念，它是針對大規模數據分發和可靠廣播的應用特點而提出的一種理想的解決方案，但當時并未給出實用數字噴泉碼設計方案。2002年，Luby提出了第一種實用數字噴泉碼——LT碼。之后，Shokrollahi又提出了性能更佳的Raptor碼，實現了近乎理想的編譯碼性能。在學術理論日漸完善的同時，數字噴泉碼也日益受到產業界的關注，獲得了越來越多的應用[5]。1998年，M. Luby、A. Shokrollahi等人聯合創立了Digital Fountain公司（簡稱DF公司），以推廣數字噴泉概念的實際應用，很快便引起了包括MIT、UC Berkeley、紐約大學、多倫多大學、日本住友電工等機構和單位的關注。目前，已有越來越多的學者和機構開始致力于噴泉編碼的研究，數字噴泉在數據分發與廣播應用上也獲得了越來越多的支持與采納。 基本思想 所謂噴泉碼，是指這種編碼的發送端隨機編碼，由k個原始分組生成任意數量的編碼分組，源節點在不知道這些數據包是否被成功接收的情況下，持續發送數據包。而接收端只要收到k(1+ε)個編碼分組的任意子集，即收到一個稍微大于原來k值得N，就可通過譯碼以高概率（(和ε有關)）成功地恢復全部原始分組。 下面這個比喻形象地解釋了這個過程。 單個源節點S如同源源不斷產生水滴(編碼分組)的噴泉，不停地向周圍的多個桶K(表示多個接收端的緩存)發送"水滴"(表示數據包)，當一個桶里的水滿了以后(緩存滿)，它才向源節點發送一個反饋。每次發送的水滴是一幀里面隨機選擇的一些包組合起來的包，這種組合可以是線性的，也可以是非線性的，隨機選擇保證了每次發送的信息對接收節點是有用的。桶在裝滿水之后（接收足夠數量的水滴），即可達到飲用（成功譯碼）的目的，而不必關心具體是哪一滴水(編碼分組)流入桶中。當源節點收到所有桶的ACK以后，再發送新的一幀，否則繼續發送組合包。 這也是這種編碼方式被稱為噴泉碼( Fountain Codes)的原因。 特點 精心設計的數字噴泉碼不僅擁有很小的譯碼開銷ε，而且具有簡單的編譯碼方法和很小的編譯碼復雜度。同時噴泉碼還可以有效提高信道容量，使得網絡更加健壯。 應用方向 噴泉碼最初是為抹除信道設計的，其最大的特點就是碼率無關性，即編碼器可以生成的編碼符號的個數是無限且靈活的，譯碼器只需接收到任意足夠數目的編碼符號就能還原數據。因此不管抹除信道的抹除概率多大，編碼器能源源不斷地產生編碼符號直到譯碼器還原出源文件。正是由于涌泉碼的這個特性，使得涌泉碼在刪除信道中獲得了逼近香農限的性能。 后來，研究發現涌泉碼在二進制對稱信道(BSC)和加性高斯白噪聲(AWGN)等信道中同樣能獲得很好的性能。在此之后，LT碼的研究范圍不斷擴大，LT碼獨特的碼率無關性，特別適合無線通信中的廣播、多播業務，因此LT碼在無線廣播系統和協作中繼網絡中的應用成為近幾年的一個研究熱點。 噴泉碼的應用范主要可以概括為如下幾個方面： ①在廣域網、國際互聯網、衛星網上進行高速大文件傳輸。以RS為代表的前向糾錯編碼通過硬件實現，按照保護小塊數據的要求設計，主要是對受到破壞的多個比特或單個比特進行檢測和校正。而LT碼意在保護大型文件，而且這種技術以軟件方式實現，速度非?？臁Ｓ捎跊]有了TCP的網絡時延影響吞吐量，噴泉碼可以在互聯網，無線網，移動網及衛星網上提供接近網絡帶寬速度的大文件傳輸。 ②在無線網、移動網提供質量完善的流媒體點播或廣播。利用噴泉碼技術來處理Internet最為頭疼的流式視頻、音頻、視頻游戲、MP3文件等，可以提供質量完善的流媒體點播或廣播。 ③在3G移動網、數字電視廣播網、電信組播網及衛星廣播系統提供無需反饋信道的可靠性數據廣播。由于不需反饋，用戶數量的增長對于發送方來說沒有任何影響，發送方可以服務任意數量的用戶。 兩種噴泉碼 噴泉碼有兩類：LT碼和Raptor碼。LT碼是噴泉碼的第一次具體實現，是由Michael Luby 提出的，后來Amin Shokrollahi對LT碼做出了改進，提出了第二類噴泉碼，即Raptor碼。 1、LT碼（盧比變換碼） LT碼是第一類碼率不受限碼的實用實現，即其碼率不需要事先確定，同時它具有簡單的編譯碼方法以及較小的譯碼開銷和編譯碼復雜度，為數字噴泉碼的發展奠定了基礎。LT碼是通用的數字噴泉碼，也就是說對于具有不同刪除概率的各種刪除信道均是逼近最優的。 在數據傳輸時，將長為N的文件分割成k=N/ l個輸入符號(即每個輸入符號的長為l)，并稱每個數據包為輸入符號，稱每個編碼包為輸出符號。 定義：LT碼的度分布ρ( d)(d≥1)定義為一個輸出符號結點的度為d的概率。 LT碼生成每個編碼分組的過程如圖1所示： （1）將原始數據等分為k個數據分組，在1～k范圍內按某一分布Ω（稱為編碼度分布）隨機選取一個整數d，其中k稱為該碼的碼長，d稱為編碼分組的度； （2）在數據分組中均勻地隨機選取d個不同包； LT碼的譯碼采用一種迭代算法[3]。在譯碼的每一步，譯碼器都在編碼包集合中尋找度為1的包，這些包組成的集合稱為輸出可譯集。它們連接的數據包組成的集合稱為輸入可譯集。顯然，輸出可譯集中的元素與對應的相連的數據包取值相同，因此輸入可譯集中的所有數據包都能被直接譯出。在此之后，譯碼器將每一個譯出的數據包與跟它相連的所有編碼包分別進行異或，計算結果取代對應編碼包原來的值，完成之后刪去與它們之間的連接關系。重復上述過程直至不存在度為1的包為止。如果所有數據包都被恢復則譯碼成功，否則譯碼失敗。該算法即稱為噴泉碼的BP譯碼算法。圖2給出了一個譯碼實例。其算法過程具體為： （1）接收一定數量的編碼分組，根據編碼分組間的對應關系（可以通過分組頭部等方式顯式傳遞，也可以通過事先約定偽隨機序列等方式隱式傳遞）建立雙向圖。頂層節點代表原始分組，底層節點代表編碼分組，連接它們的邊代表該原始分組是該編碼分組的模二和分量。簡單實例如圖2(a)所示。 （2）任意選取一個度數為1的編碼分組。如果不存在，則譯碼停止；如果存在，則通過簡單的復制運算，即可恢復與之相連的唯一原始分組。簡單實例如圖2(b)所示。 （3）將已經恢復的原始分組模二和到與其相連的所有其他編碼分組中，消除其在這些編碼分組中的模二和分量。相應地，將雙向圖中對應的邊刪除，使得這些編碼分組的度數減1。簡單實例如圖2(c)所示。如果某個編碼分組的度數減小為1，則稱該編碼分組被“釋放”，如圖2(c)最右側的編碼分組。 （4）重復步驟（2）和（3），直至譯碼停止。如果所有原始分組都已經恢復，則譯碼成功；否則，譯碼失敗，必須接收更多的編碼分組才能繼續譯碼。如圖2(d)，2(e)，2(f)所示。 圖2 LT碼解碼示意 顯然，合理的度數分布是LT碼性能的關鍵。從LT碼編碼過程考慮，一方面應該使平均度數較小，這樣才可以減小生成每個編碼分組需要的運算量；另一方面又應該給予較大度數一定的選取概率，這樣才可以通過m≈k個編碼分組覆蓋所有的原始分組。從LT譯碼過程考慮，一方面應該使編碼分組保持一定的釋放速度，這樣才可以保證譯碼過程不會終止；另一方面又不能使編碼分組釋放過快，否則大量已經釋放的編碼分組將增加重復覆蓋的可能性，引入不必要的冗余[7]。正是基于以上考慮，Luby首先給出了理想Soliton分布，使得譯碼過程在期望意義下每步迭代恰好釋放一個編碼分組。之后Luby通過修正理想Soliton分布，給出了更加實用的魯棒Soliton分布。理論分析證明：在魯棒Soliton分布下，當受到k+O(k)個編碼分組后，譯碼器即可以高概率成功譯碼；以模二和運算的次數來衡量，生成每個編碼分組需要的運算量是O(logk)，而成功譯碼需要的運算量是O(klogk)。根據文獻報告的數據，在Digital Fountain公司設計的商用LT碼中，譯碼開銷ε不超過5%，而譯碼失敗概率可以低于10-8?？梢?，LT碼不僅編譯碼方法簡單直觀，而且性能相當優良。 2、Raptor碼 Raptor碼是LT碼的基礎上發展出來的改進版。它是基于這樣一個認識：LT碼生成的編碼包中有少量連接度很高的包，這些包的作用主要是保證對所有數據包的良好覆蓋，從而保證譯碼的完整性，然而這些高連接度包的存在消耗了很多編譯碼異或操作，同時也降低了低連接度包的比例，從而減小了譯碼過程中可譯集的大小，降低了譯碼成功率。如果能采用別的方法來代替高連接度包完成對數據包的良好覆蓋則可以有效地提高譯碼成功率并降低編譯碼復雜度。 基于這個思想，Raptor碼提出采用兩步編碼的方式。首先對原始信息用一個分組碼進行預編碼，然后采用一個弱化的LT碼對數據進行編碼并發送。所謂弱化的LT碼是指它生成的編碼包沒有高連接度包，無法完全譯出原始數據。Raptor碼譯碼時，首先用BP算法對數據進行正常譯碼。由于弱化LT碼能以很高的概率恢復出絕大多數的數據包，因此剩下未被譯碼的數據包所占的比例就被控制在一個很小的范圍以內，這些未被譯碼的數據不再通過高連接度的編碼包來保證覆蓋和恢復，而是利用預編碼的糾錯能力進行恢復。通過聯合優化弱化LT碼和預編碼的碼率和參數，Raptor可以獲得更低的編譯碼復雜度，而在相同譯碼開銷下能實現更高的譯碼成功率。 Raptor碼的編碼和譯碼均需O (kln(1/ε))次包異或操作，其中ε是譯碼開銷?？梢?，Raptor碼的編譯碼復雜度與碼長成線性關系，優于LT碼的對數關系。 [2] 技術發展 當噴泉碼被用于大規模的多媒體傳輸時，傳統的LT或者Raptor碼無法滿足實時組播應用中的非等重誤碼保護（unequal error protection ，UEP ）。Expanding Window Fountain(EWF) codes成為了一種實現這種需求的新方式。顯然，它是一種能夠在抹除信道中的無率（rateless）碼。 EWF碼使用了窗口技術，而不是通過不平等選擇輸入的符號來實現UEP。這種技術通過在UEP無率碼設計中添加附加參數以滿足不同標準的接收者接收，使得它比傳統加權的方式更為一般化并且更具靈活性。無論是理論研究還是實驗表明，這種窗口技術都使得UEP設計具有了更好的性能。音樂噴泉公司【熱線電話:13172194676】主要從事音樂噴泉工程、噴泉安裝調試工程，根據客戶的要求設計、施工音樂噴泉、程控噴泉、變頻噴泉、跑動噴泉、旱式噴泉、搖擺噴泉、漂浮噴泉、雕塑噴泉、超高噴泉、波光噴泉、水池噴泉、疊水噴泉、室內噴泉、奇特噴泉、瀑布水簾、冷霧噴泉、微型噴泉及各類控制系統等一體化服務。音樂噴泉公司_廣場噴泉_噴泉水景_程控噴泉_旱地噴泉施工設計公司城市導航：