Raptor Forward Error Correction Scheme for Object Delivery
RFC 5053
|
| Document |
Type |
|
RFC - Proposed Standard
(October 2007; No errata)
|
|
Last updated |
|
2015-10-14
|
|
Stream |
|
IETF
|
|
Formats |
|
plain text
pdf
html
bibtex
|
| Stream |
WG state
|
|
(None)
|
|
Document shepherd |
|
No shepherd assigned
|
| IESG |
IESG state |
|
RFC 5053 (Proposed Standard)
|
|
Consensus Boilerplate |
|
Unknown
|
|
Telechat date |
|
|
|
Responsible AD |
|
Magnus Westerlund
|
|
Send notices to |
|
(None)
|
Network Working Group M. Luby
Request for Comments: 5053 Digital Fountain
Category: Standards Track A. Shokrollahi
EPFL
M. Watson
Digital Fountain
T. Stockhammer
Nomor Research
October 2007
Raptor Forward Error Correction Scheme for Object Delivery
Status of This Memo
This document specifies an Internet standards track protocol for the
Internet community, and requests discussion and suggestions for
improvements. Please refer to the current edition of the "Internet
Official Protocol Standards" (STD 1) for the standardization state
and status of this protocol. Distribution of this memo is unlimited.
Abstract
This document describes a Fully-Specified Forward Error Correction
(FEC) scheme, corresponding to FEC Encoding ID 1, for the Raptor
forward error correction code and its application to reliable
delivery of data objects.
Raptor is a fountain code, i.e., as many encoding symbols as needed
can be generated by the encoder on-the-fly from the source symbols of
a source block of data. The decoder is able to recover the source
block from any set of encoding symbols only slightly more in number
than the number of source symbols.
The Raptor code described here is a systematic code, meaning that all
the source symbols are among the encoding symbols that can be
generated.
Luby, et al. Standards Track [Page 1]
RFC 5053 Raptor FEC Scheme October 2007
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3
2. Requirements Notation . . . . . . . . . . . . . . . . . . . . 3
3. Formats and Codes . . . . . . . . . . . . . . . . . . . . . . 3
3.1. FEC Payload IDs . . . . . . . . . . . . . . . . . . . . . 3
3.2. FEC Object Transmission Information (OTI) . . . . . . . . 4
3.2.1. Mandatory . . . . . . . . . . . . . . . . . . . . . . 4
3.2.2. Common . . . . . . . . . . . . . . . . . . . . . . . . 4
3.2.3. Scheme-Specific . . . . . . . . . . . . . . . . . . . 5
4. Procedures . . . . . . . . . . . . . . . . . . . . . . . . . . 5
4.1. Content Delivery Protocol Requirements . . . . . . . . . . 5
4.2. Example Parameter Derivation Algorithm . . . . . . . . . . 6
5. Raptor FEC Code Specification . . . . . . . . . . . . . . . . 8
5.1. Definitions, Symbols, and Abbreviations . . . . . . . . . 8
5.1.1. Definitions . . . . . . . . . . . . . . . . . . . . . 8
5.1.2. Symbols . . . . . . . . . . . . . . . . . . . . . . . 9
5.1.3. Abbreviations . . . . . . . . . . . . . . . . . . . . 11
5.2. Overview . . . . . . . . . . . . . . . . . . . . . . . . . 11
5.3. Object Delivery . . . . . . . . . . . . . . . . . . . . . 12
5.3.1. Source Block Construction . . . . . . . . . . . . . . 12
5.3.2. Encoding Packet Construction . . . . . . . . . . . . . 14
5.4. Systematic Raptor Encoder . . . . . . . . . . . . . . . . 15
5.4.1. Encoding Overview . . . . . . . . . . . . . . . . . . 15
5.4.2. First Encoding Step: Intermediate Symbol Generation . 16
5.4.3. Second Encoding Step: LT Encoding . . . . . . . . . . 20
5.4.4. Generators . . . . . . . . . . . . . . . . . . . . . . 21
5.5. Example FEC Decoder . . . . . . . . . . . . . . . . . . . 23
5.5.1. General . . . . . . . . . . . . . . . . . . . . . . . 23
5.5.2. Decoding a Source Block . . . . . . . . . . . . . . . 23
5.6. Random Numbers . . . . . . . . . . . . . . . . . . . . . . 28
5.6.1. The Table V0 . . . . . . . . . . . . . . . . . . . . . 28
5.6.2. The Table V1 . . . . . . . . . . . . . . . . . . . . . 29
5.7. Systematic Indices J(K) . . . . . . . . . . . . . . . . . 30
6. Security Considerations . . . . . . . . . . . . . . . . . . . 43
7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 43
8. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 44
9. References . . . . . . . . . . . . . . . . . . . . . . . . . . 44
9.1. Normative References . . . . . . . . . . . . . . . . . . . 44
9.2. Informative References . . . . . . . . . . . . . . . . . . 44
Luby, et al. Standards Track [Page 2]
RFC 5053 Raptor FEC Scheme October 2007
Show full document text