Raptor codes Export

@article{Shokrollahi-2006-Raptor, abstract = {LT-codes are a new class of codes introduced by Luby for the purpose of scalable and fault-tolerant distribution of data over computer networks. In this paper, we introduce Raptor codes, an extension of LT-codes with linear time encoding and decoding. We will exhibit a class of universal Raptor codes: for a given integer k and any real /spl epsiv/>0, Raptor codes in this class produce a potentially infinite stream of symbols such that any subset of symbols of size k(1+/spl epsiv/) is sufficient to recover the original k symbols with high probability. Each output symbol is generated using O(log(1//spl epsiv/)) operations, and the original symbols are recovered from the collected ones with O(klog(1//spl epsiv/)) operations. We will also introduce novel techniques for the analysis of the error probability of the decoder for finite length Raptor codes. Moreover, we will introduce and analyze systematic versions of Raptor codes, i.e., versions in which the first output elements of the coding system coincide with the original k elements.}, author = {Shokrollahi, A.}, citeulike-article-id = {1219485}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=1148681}, citeulike-linkout-1 = {http://dx.doi.org/10.1109/TIT.2006.874390}, citeulike-linkout-2 = {http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1638543}, doi = {10.1109/TIT.2006.874390}, journal = {Information Theory, IEEE Transactions on}, keywords = {codes, erasure, error-correction, graphs, information, theory}, number = {6}, pages = {2551--2567}, posted-at = {2009-03-22 23:49:33}, priority = {0}, title = {Raptor codes}, url = {http://dx.doi.org/10.1109/TIT.2006.874390}, volume = {52}, year = {2006} }

TY - JOUR ID - Shokrollahi-2006-Raptor L3 - citeulike-article-id:1219485 N2 - LT-codes are a new class of codes introduced by Luby for the purpose of scalable and fault-tolerant distribution of data over computer networks. In this paper, we introduce Raptor codes, an extension of LT-codes with linear time encoding and decoding. We will exhibit a class of universal Raptor codes: for a given integer k and any real /spl epsiv/>0, Raptor codes in this class produce a potentially infinite stream of symbols such that any subset of symbols of size k(1+/spl epsiv/) is sufficient to recover the original k symbols with high probability. Each output symbol is generated using O(log(1//spl epsiv/)) operations, and the original symbols are recovered from the collected ones with O(klog(1//spl epsiv/)) operations. We will also introduce novel techniques for the analysis of the error probability of the decoder for finite length Raptor codes. Moreover, we will introduce and analyze systematic versions of Raptor codes, i.e., versions in which the first output elements of the coding system coincide with the original k elements. IS - 6 JF - Information Theory, IEEE Transactions on EP - 2567 TI - Raptor codes VL - 52 SP - 2551 KW - codes KW - erasure KW - error-correction KW - graphs KW - information KW - theory AU - Shokrollahi, A PY - 2006/// UR - http://dx.doi.org/10.1109/TIT.2006.874390 ER -