Raptor Code，是Rapid tornado Code的縮寫，意為快速的旋風碼。
在計算機科學領域，Raptor Code是第一種已知的能線上性時間進行編碼和解碼的噴泉碼(fountain codes)。他們由Amin Shokrollahi於2000/2001年發明，並且在2004年以拓展抽象的方式出版。旋風碼是對LT碼的一種很重要的理論與實踐上的改進，其中，LT碼是噴泉碼的第一類有實用性質的套用。
基本介紹
- 中文名：快速旋風碼、速龍碼
- 外文名：Raptor Code
簡介,編碼,解碼,套用,計算複雜度,
簡介
就像通常的噴泉碼一樣，Raptor Code對一個給定的包含一系列標誌k進行編碼，將其編為一系列潛在的擁有無限序列的編碼符號，這樣對於任何已知的k和更多的編碼符號允許信息被某些非零機率事件所恢復。一旦接收到的符號數目略微超過k時，信息被恢復的機率將隨著接收到的符號的數目的增加而逐漸接近於1。舉個例子，根據旋風碼的最新版本--RaptorQ Codes，在接收到k個符號後，編碼的失敗率將低於1%；並且在收到k+2個符號後，編碼的失敗率將低於百萬分之一。一個符號可以是任意大小，從單個位元組到上千個位元組不等。
Raptor Code有系統性的版本以及非系統性的兩個版本。在系統性版本中，原始信息的符號被包含在解碼符號的集合中。一個系統化的旋風碼的例子是由3GPP(the 3rd Generation Partnership Project)定義的用於移動蜂窩無線廣播與多播的編碼，該編碼也被用於定義為手持設備的IP數據進行廣播的DVB-H標準。這些標準中的Raptor Code也被定義在IETF RFC 5053標準中。現在在實際使用中的最新版本的旋風碼是被定義在IETF RFC 6330標準中的RaptorQ。
Online Code就屬於Raptor Code的非系統性版本。
Raptor Code是基於這樣一個認識：LT碼生成的編碼包中有少量連線度很高的包，這些包的作用主要是保證對所有數據包的良好覆蓋，從而保證解碼的完整性，然而這些高連線度包的存在消耗了很多編解碼的異或操作，同時也降低了低連線度包的比例，從而減小了解碼過程中可譯集的大小，降低了解碼成功率。如果能採用別的方法來代替高連線度包完成對數據包的良好覆蓋則可以有效地提高解碼成功率並降低編解碼複雜度。
基於這個思想，Raptor Code提出採用兩步編碼的方式。首先對原始信息用一個分組碼進行預編碼(pre code)，然後採用一個弱化的LT碼對數據進行編碼並傳送。所謂弱化的LT碼是指它生成的編碼包沒有高連線度包，無法完全譯出原始數據。Raptor Code解碼時，首先用BP算法對數據進行正常解碼。由於弱化LT碼能以很高的機率恢復出絕大多數的數據包，因此剩下未被解碼的數據包所占的比例就被控制在一個很小的範圍以內，這些未被解碼的數據不再通過高連線度的編碼包來保證覆蓋和恢復，而是利用預編碼的糾錯能力進行恢復。通過聯合最佳化弱化LT碼和預編碼的碼率和參數，Raptor Code可以獲得更低的編解碼複雜度，而在相同解碼開銷下能實現更高的解碼成功率。
編碼
Raptor碼的主要思想是將待傳送的數據平均分成長度為k的n個分組，稱為k個輸入符號，每組符號長度可能為一到上千比特。Raptor碼的編碼過程由預編碼過程和LT碼的編碼過程組成，預編碼過程將原始輸入單元通過某種傳統的糾錯碼轉換為中間編碼校驗單元，然後將其作為LT碼的輸入單元進行編碼。
解碼
有兩種方法可以對Raptor Code進行解碼。
其一為在Raptor碼的解碼過程中利用LT碼技術解碼，只需要恢復固定比例的中間編碼校驗單元，再利用傳統糾錯碼的解碼性質就可以恢復所有的輸入單元。根據中間編碼校驗單元所處的層次可以劃分為單層校驗預編碼技術和多層校驗編碼技術。
在另一種較為綜合的方法中，定義在內碼和外碼中的符號間的關係被認為是一組可以用常規手段，尤其是高斯消元法求解的聯立方程。
多層校驗編碼
單層校驗編碼
多層校驗編碼單層校驗編碼套用
由於Raptor碼的設計和最佳化具有快速和高效率的特點。其編碼和解碼的速度夠快，因此Raptor碼在一些領域具有廣泛的套用。
Raptor碼在數據廣播分發系統中，使用單向的UDP進行可靠的傳輸，這樣就避免了TCP的弊端，在環境惡劣的網路上UDP比TCP傳輸要快7~8倍以上，還支持任何大小的檔案提供可靠的單向傳輸。
Raptor碼還在視頻分散式聯合信源信道編碼中有廣泛的套用，針對在擦除信道傳輸視頻數據包時，要進行視頻壓縮，我們考慮WZC編碼，與用兩種不同的信道編碼方法----一種是SWC用於WZC和另一種用於擦防寫，而我們可以僅用Raptor碼就足夠實現前面兩種編碼的目的。
Raptor碼在一些通信系統中也有廣泛套用。寬頻低壓電力線（BPL）通信是一種新的接入技術，他試圖利用低壓電力線網路作為高速傳輸通道來連線個人用戶到外部網路或不同的通信節點。經過LDPC預編碼的低密度碼Raptor碼，解決了解碼差錯門限問題，使平均度分布保持為常數，降低了編解碼複雜度。
計算複雜度
當輸入是一個系統的預代碼時，輸入符號後面附加多餘的符號。因為有了預編碼，適當的LT碼用於產生輸出符號，LT碼對編碼符號的度數總和klog2(k/d)的要求變寬了，其中d為錯誤機率，而只需要恢復一部分中間符號即可，再用傳統的糾刪碼來恢復所有的輸入符號，理論及試驗都證明只要選擇了適當的預編碼因子以及LT碼選擇了合適的度數分布r(d)，其中d為編碼符號度數，那么raptor碼就能達到以下效果：能夠從k(1+e)個編碼符號的任何子集中以1-d的機率恢復k個輸入符號，其編碼複雜度都為kln(1/e)。
