article

Raptor codes

Author:

Amin ShokrollahiAuthors Info & Claims

IEEE/ACM Transactions on Networking (TON), Volume 14, Issue SI

Pages 2551 - 2567

https://doi.org/10.1109/TIT.2006.874390

Published: 01 June 2006 Publication History

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 ε > 0, Raptor codes in this class produce a potentially infinite stream of symbols such that any subset of symbols of size k(1 + ε) is sufficient to recover the original k symbols with high probability. Each output symbol is generated using O(log(1/ ε)) operations, and the original symbols are recovered from the collected ones with O(k log(1/ε)) 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.

References

[1]

{1} P. Elias, "Coding for two noisy channels," in Proc. 3rd London Symp. Information Theory, London, U.K., 1955, pp. 61-76.]]

[2]

{2} M. Luby, M. Mitzenmacher, A. Shokrollahi, and D. Spielman, "Efficient erasure correcting codes," IEEE Trans. Inf. Theory, vol. 47, no. 2, pp. 569-584, Feb. 2001.]]

[3]

{3} R. G. Gallager, Low Density Parity-Check Codes. Cambridge, MA: MIT Press, 1963.]]

[4]

{4} J. Byers, M. Luby, M. Mitzenmacher, and A. Rege, "A digital fountain approach to reliable distribution of bulk data," in Proc. ACM SIGCOMM '98, Vancouver, BC, Canada, Jan. 1998, pp. 56-67.]]

[5]

{5} M. Luby, "Information Additive Code Generator and Decoder for Communication Systems," U.S. Patent 6,307,487, Oct. 23, 2001.]]

[6]

{6} M. Luby, "Information Additive Code Generator and Decoder for Communication Systems," U.S. Patent 6,373,406, Apr. 16, 2002.]]

[7]

{7} M. Luby, "LT-codes," in Proc. 43rd Annu. IEEE Symp. Foundations of Computer Science (FOCS), Vancouver, BC, Canada, Nov. 2002, pp. 271-280.]]

[8]

{8} A. Shokrollahi, S. Lassen, and M. Luby, "Multi-Stage Code Generator and Decoder for Communication Systems," U.S. Patent Application 20030058958, Dec. 2001.]]

[9]

{9} P. Maymounkov, "Online Codes," Preprint, 2002.]]

[10]

{10} "Technical Specification Group Services and System Aspects; Multi-media Broadcast/Multicast Services (MBMS); Protocols and Codecs (Release 6)," 3rd Generation Partnership Project (3GPP), Tech. Rep. 3GPP TS 26.346 V6.3.0, 3GPP, 2005.]]

[11]

{11} R. Karp, M. Luby, and A. Shokrollahi, "Finite length analysis of LT codes," in Proc. IEEE Int. Symp. Information Theory, Chicago, IL, Jun./Jul. 2004, p. 39.]]

[12]

{12} H. Jin, A. Khandekar, and R. McEliece, "Irregular repeat-accumulate codes," in Proc. 2nd Int. Symp. Turbo Codes, Brest, France, Sep. 2000, pp. 1-8.]]

[13]

{13} H. Pfister, I. Sason, and R. Urbanke, "Capacity-achieving ensembles for the binary erasure channel with bounded complexity," IEEE Trans. Inf. Theory, vol. 51, no. 7, pp. 2352-2379, Jul. 2005.]]

[14]

{14} M. Luby, M. Mitzenmacher, A. Shokrollahi, and D. Spielman, "Improved low-density parity-check codes using irregular graphs," IEEE Trans. Inf. Theory, vol. 47, no. 2, pp. 585-598, Feb. 2001.]]

[15]

{15} A. Shokrollahi, "New sequences of linear time erasure codes approaching the channel capacity," in Proc. 13th Int. Symp. Applied Algebra, Algebraic Algorithms, and Error-Correcting Codes (Lecture Notes in Computer Science), M. Fossorier, H. Imai, S. Lin, and A. Poli, Eds. Berlin, Germany: Springer-Verlag, 1999, vol. 1719, pp. 65-76.]]

[16]

{16} P. Oswald and A. Shokrollahi, "Capacity-achieving sequences for the erasure channel," IEEE Trans. Inf. Theory, vol. 48, no. 12, pp. 3017-3028, Dec. 2002.]]

[17]

{17} A. Shokrollahi and R. Urbanke, "Finite Length Analysis of a Certain Class of LDPC Codes," Preprint, 2001.]]

[18]

{18} M. Luby, M. Mitzenmacher, and A. Shokrollahi, "Analysis of random processes via and-or tree evaluation," in Proc. 9th Annu. ACM-SIAM Symp. Discrete Algorithms, San Francisco, CA, Jan. 1998, pp. 364-373.]]

[19]

{19} M. Luby, "A note on the design of degree distributions," unpublished, 2001 Private communication.]]

[20]

{20} C. Di, D. Proietti, I. E. Telatar, T. Richardson, and R. Urbanke, "Finite-length analysis of low-density parity-check codes on the binary erasure channel," IEEE Trans. Inf. Theory, vol. 48, no. 6, pp. 1570-1579, Jun. 2002.]]

[21]

{21} A. Shokrollahi, S. Lassen, and R. Karp, "Systems and Processes for Decoding Chain Reaction Codes Through Inactivation," U.S. Patent 6,856,263, Feb. 15, 2005.]]

[22]

{22} A. Shokrollahi and M. Luby, "Systematic Encoding and Decoding of Chain Reaction Codes," U.S. Patent 6,909,383, Jun. 21, 2005.]]

Cited By

Wang WLyu MNiu TLi QXu LXu Y(2025)Fast Acceleration Strategies for XOR-Based Erasure CodesIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2024.343264844:1(331-344)Online publication date: 1-Jan-2025
https://dl.acm.org/doi/10.1109/TCAD.2024.3432648
Zhao YZhang YLau FYu HZhu ZZhang B(2024)Expanding-Window Zigzag Decodable Fountain Codes for Scalable Multimedia TransmissionACM Transactions on Multimedia Computing, Communications, and Applications10.1145/366461020:8(1-24)Online publication date: 11-May-2024
https://dl.acm.org/doi/10.1145/3664610
Shi SLing NJiang ZHuang XHe YZhao XYang BBian CXia JYan ZYeung RXing GGanesan DShi W(2024)Soar: Design and Deployment of A Smart Roadside Infrastructure System for Autonomous DrivingProceedings of the 30th Annual International Conference on Mobile Computing and Networking10.1145/3636534.3649352(139-154)Online publication date: 29-May-2024
https://dl.acm.org/doi/10.1145/3636534.3649352
Show More Cited By

Index Terms

Raptor codes

Recommendations

Raptor codes on binary memoryless symmetric channels

In this paper, we will investigate the performance of Raptor codes on arbitrary binary input memoryless symmetric channels (BIMSCs). In doing so, we generalize some of the results that were proved before for the erasure channel. We will generalize the ...
Bounds on rates of LDPC codes for BEC with varying erasure rate

A binary erasure channel with erasure probability which can take one of two values is considered. Transmission is done by using a low density parity-check code under the requirement that completely successful decoding is possible when the channel is in ...
Doubly-generalized LDPC codes: stability bound over the BEC

The iterative decoding threshold of low-density parity-check (LDPC) codes over the binary erasure channel (BEC) fulfills an upper bound depending only on the variable and check nodes with minimum distance 2. This bound is a consequence of the stability ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking

IEEE/ACM Transactions on Networking Volume 14, Issue SI

Special issue on networking and information theory

June 2006

475 pages

ISSN:1063-6692

Issue’s Table of Contents

Publisher

IEEE Press

Publication History

Published: 01 June 2006

Published in TON Volume 14, Issue SI

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

387
Total Citations
View Citations
2,564
Total Downloads

Downloads (Last 12 months)36
Downloads (Last 6 weeks)7

Reflects downloads up to 17 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Wang WLyu MNiu TLi QXu LXu Y(2025)Fast Acceleration Strategies for XOR-Based Erasure CodesIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2024.343264844:1(331-344)Online publication date: 1-Jan-2025
https://dl.acm.org/doi/10.1109/TCAD.2024.3432648
Zhao YZhang YLau FYu HZhu ZZhang B(2024)Expanding-Window Zigzag Decodable Fountain Codes for Scalable Multimedia TransmissionACM Transactions on Multimedia Computing, Communications, and Applications10.1145/366461020:8(1-24)Online publication date: 11-May-2024
https://dl.acm.org/doi/10.1145/3664610
Shi SLing NJiang ZHuang XHe YZhao XYang BBian CXia JYan ZYeung RXing GGanesan DShi W(2024)Soar: Design and Deployment of A Smart Roadside Infrastructure System for Autonomous DrivingProceedings of the 30th Annual International Conference on Mobile Computing and Networking10.1145/3636534.3649352(139-154)Online publication date: 29-May-2024
https://dl.acm.org/doi/10.1145/3636534.3649352
Jiang ZChen QDeng ZZhang H(2024)LRB: Locally Repairable Blockchain for IoT IntegrationIEEE Transactions on Network and Service Management10.1109/TNSM.2024.346281321:6(6233-6247)Online publication date: 1-Dec-2024
https://dl.acm.org/doi/10.1109/TNSM.2024.3462813
Cho IChen CBaek S(2024)Optimal Scheduling for Uncoded and Coded Multicast in Millimeter Wave Networks Leveraging Directionality and ReflectionsIEEE Transactions on Mobile Computing10.1109/TMC.2024.335552623:9(8869-8885)Online publication date: 1-Sep-2024
https://dl.acm.org/doi/10.1109/TMC.2024.3355526
Langberg MSabag O(2024)Competitive Channel-CapacityIEEE Transactions on Information Theory10.1109/TIT.2024.339414970:7(4585-4598)Online publication date: 26-Apr-2024
https://dl.acm.org/doi/10.1109/TIT.2024.3394149
Zhang YZhen ZZhao YLau FMa BZhang BYu HZhu Z(2024)Online fountain code with an improved caching mechanismIET Communications10.1049/cmu2.1286818:20(1813-1825)Online publication date: 18-Dec-2024
https://dl.acm.org/doi/10.1049/cmu2.12868
Lajam OMohammed S(2024)Optimizing efficiency of P2P content distribution with network codingJournal of Network and Computer Applications10.1016/j.jnca.2024.103825223:COnline publication date: 1-Mar-2024
https://dl.acm.org/doi/10.1016/j.jnca.2024.103825
Liu ZDong FLiu CDeng XYang TZhao YLi JCui BZhang G(2024)WavingSketch: an unbiased and generic sketch for finding top-k items in data streamsThe VLDB Journal — The International Journal on Very Large Data Bases10.1007/s00778-024-00869-633:5(1697-1722)Online publication date: 1-Sep-2024
https://dl.acm.org/doi/10.1007/s00778-024-00869-6
Zhang ZZhao LBai J(2023)A Decoding Algorithm for Spinal Codes over Fading ChannelProceedings of the 2023 9th International Conference on Communication and Information Processing10.1145/3638884.3638948(415-419)Online publication date: 14-Dec-2023
https://dl.acm.org/doi/10.1145/3638884.3638948
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents