噴泉碼
在編碼理論中，噴泉碼（也稱為無碼率抹除碼）是一類抹除碼，這種編碼能夠從一組給定的源符號序列中產生一串不限長度的編碼符號序列，在理想情況下，從編碼符號序列中獲得大小和源符號相同或稍大的任意子集，便可恢復源符號。術語「噴泉」或「無碼率」是指此類編碼不表現出固定的編碼率。
最優的噴泉碼應當能夠從任意k個編碼符號中恢復出k個源符號。噴泉碼被認為具有高效的編解碼算法，能以高概率從任意k』個編碼符號恢復k個源符號（k』僅稍大於k）。
LT碼是第一種實際可用的噴泉碼。隨後提出的Raptor碼和在線碼加入了輸入符號的預編碼階段，從而實現了編解碼的線性時間複雜度。
應用
[編輯]噴泉碼可靈活適用於固定編碼率或無法先驗確定出固定編碼率的地方，及需要高效編解碼大量數據之處。
一個示例是數據輪播，其上會連續廣播一些大文件到一組接收器中[1]。採用固定碼率的抹除碼，丟失源符號（由於傳輸錯誤）的接收器將面臨贈券收集問題：它必須成功接收它還沒有的編碼符號。當使用傳統的短長度抹除碼，因為文件必須被分成幾個區塊，每一個都單獨編碼，問題變得更加明顯：接收器現在必須為「每個」區塊收集指定數量的缺失編碼符號。使用噴泉碼，接收器只需檢索比源符號集稍大的「任何」編碼符號子集就足夠了。（實際應用中，通常基於網絡特性、接收器和所需的遞送可靠性，由操作者設定廣播頻率，因此噴泉碼碼率會在文件安排廣播時動態確定。）
另一種應用是在可靠多播中的混合ARQ：一個接收器請求的奇偶校驗信息可能會對多播組中的「所有」接收器有用。
標準中的噴泉碼
[編輯]目前最高效的噴泉碼為Raptor碼[2]，有着非常高效的線性時間編解碼算法，編解碼時每生成一個符號只需要很少的常數次XOR運算[3]。IETF RFC 5053 中詳細規定了系統Raptor碼，其已為IETF之外的多個標準所採用，如用於廣播文件傳遞和流服務的3GPP MBMS標準、用於在DVB網絡中提供IP服務的DVB-H IPDC標準和用於在IP網絡中提供商用電視服務的DVB-IPTV標準。這種編碼支持最多8192個源符號的源區塊，每個源區塊能生成多達65536個編碼符號。當源區塊有1000個源符號時，該編碼的平均相對接收開銷為0.2%，而相對接收開銷小於2%的概率為99.9999%[4]。相對接收開銷定義為在恢復原始源數據時，所需的超出源數據長度的編碼數據，表示為源數據大小的百分比。例如，如果相對接收開銷為0.2%，那麼這意味着，大小為1 MB的源數據可以從1.002 MB的編碼數據中恢復。
更高級的Raptor碼靈活性更強，接收開銷更少，稱為RaptorQ，已被IETF接受[5]。這種編碼支持最多56403個源符號的源區塊，每個源區塊能生成多達16777216個編碼符號。該編碼有很高的概率，能從任何一組等於源區塊中源符號數量的編碼符號中恢復源區塊，而在罕見情況下，只比源區塊中源符號數量稍多。
數據存儲中的噴泉碼
[編輯]抹除碼在數據存儲應用中有使用，因其在給定級別的冗餘和可靠性下，能節省大量的存儲單元。用於數據存儲的抹除碼，特別是在分布式存儲應用中，相比用於通信或數據流時，其設計要求有很大不同。用於數據存儲系統中的編碼，要求之一是系統形式，即，原始消息符號是編碼符號的一部分。系統形式使消息關閉符號能直接讀取，而不必從存儲單元中解碼。此外，由於存儲節點之間的帶寬和通信負載可能會成為瓶頸，允許最小通信的編碼會非常有幫助，特別是當一個節點發生故障，且需要進行系統重建以恢復冗餘到初始水平時。在這方面，會希望故障發生時，噴泉碼能高效地執行修復過程：當丟失單個編碼符號時，要找回它，不應有太多關於其他編碼符號的通信和計算。事實上，修復的延遲有時可能比節省存儲空間更重要。可修復噴泉碼[6]預計將能完成噴泉碼在存儲系統的設計目標。關於噴泉碼的詳細調查及其應用，可以在此找到[7]。
參見
[編輯]注釋
[編輯]- ^ J. Byers, M. Luby, M. Mitzenmacher, A. Rege. A Digital Fountain Approach to Reliable Distribution of Bulk Data (PDF). 1998 [2015-02-18]. （原始內容存檔 (PDF)於2012-05-23）.
- ^ Qualcomm Raptor Technology - Forward Error Correction. [2015-02-18]. （原始內容存檔於2010-12-29）.
- ^ (Shokrollahi 2006)
- ^ T. Stockhammer, A. Shokrollahi, M. Watson, M. Luby, T. Gasiba. Furht, B.; Ahson, S. , 編. Application Layer Forward Error Correction for Mobile Multimedia Broadcasting. Handbook of Mobile Broadcasting: DVB-H, DMB, ISDB-T and Media FLO (CRC Press). March 2008.
- ^ (Luby et al. 2010)
- ^ M. Asteris and A. G. Dimakis,. "Repairable Fountain Codes", In Proc. of 2012 IEEE International Symposium on Information Theory (PDF). 2012 [2015-02-18]. （原始內容存檔 (PDF)於2016-07-01）.
- ^ Suayb S. Arslan,. Incremental Redundancy, Fountain Codes and Advanced Topics (PDF). 2014 [2015-02-18]. （原始內容存檔 (PDF)於2020-01-09）.
參考
[編輯]- M. Luby. LT Codes. Proceedings of the IEEE Symposium on the Foundations of Computer Science. 2002: 271–280.
- A. Shokrollahi, Raptor Codes (PDF), Transactions on Information Theory (IEEE), 2006, 52 (6): 2551–2567.
- P. Maymounkov. Online Codes (PDF). (Technical Report). November 2002 [2015-02-18]. （原始內容存檔 (PDF)於2014-02-23）.
- David J. C. MacKay. Information Theory, Inference, and Learning Algorithms. Cambridge University Press. 2003 [2015-02-18]. ISBN 0-521-64298-1. （原始內容存檔於2016-02-17）.
- M. Luby, A. Shokrollahi, M. Watson, T. Stockhammer, Raptor Forward Error Correction Scheme for Object Delivery, RFC 5053 (IETF), October 2007.
- M. Luby, A. Shokrollahi, M. Watson, T. Stockhammer, L. Minder, RaptorQ Forward Error Correction Scheme for Object Delivery, IETF, May 2011 [2015-02-18], （原始內容存檔於2017-07-02）.