喷泉码

在编码理论中，喷泉码（也称为无码率抹除码）是一类抹除码，这种编码能够从一组给定的源符号序列中产生一串不限长度的编码符号序列，在理想情况下，从编码符号序列中获得大小和源符号相同或稍大的任意子集，便可恢复源符号。术语“喷泉”或“无码率”是指此类编码不表现出固定的编码率。

最优的喷泉码应当能够从任意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]。

参见

  • 在线码
  • 线性网络编码
  • 秘密共享
  • 旋风码，喷泉码的前驱

注释

  1. ^ 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）. 
  2. ^ Qualcomm Raptor Technology - Forward Error Correction. [2015-02-18]. （原始内容存档于2010-12-29）. 
  3. ^ （Shokrollahi 2006）
  4. ^ 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. 
  5. ^ （Luby et al. 2010）
  6. ^ 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）. 
  7. ^ 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） .