Raptor Forward Error Correction Scheme for Object Delivery
RFC 5053

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