GENWiki

Premier IT Outsourcing and Support Services within the UK

User Tools

Site Tools

Problem, Formatting or Query -  Send Feedback

Was this page helpful?-10+1


rfc:rfc6330

Internet Engineering Task Force (IETF) M. Luby Request for Comments: 6330 Qualcomm Incorporated Category: Standards Track A. Shokrollahi ISSN: 2070-1721 EPFL

                                                             M. Watson
                                                          Netflix Inc.
                                                        T. Stockhammer
                                                        Nomor Research
                                                             L. Minder
                                                 Qualcomm Incorporated
                                                           August 2011
    RaptorQ Forward Error Correction Scheme for Object Delivery

Abstract

 This document describes a Fully-Specified Forward Error Correction
 (FEC) scheme, corresponding to FEC Encoding ID 6, for the RaptorQ FEC
 code and its application to reliable delivery of data objects.
 RaptorQ codes are a new family of codes that provide superior
 flexibility, support for larger source block sizes, and better coding
 efficiency than Raptor codes in RFC 5053.  RaptorQ is also a fountain
 code, i.e., as many encoding symbols as needed can be generated on
 the fly by the encoder from the source symbols of a source block of
 data.  The decoder is able to recover the source block from almost
 any set of encoding symbols of sufficient cardinality -- in most
 cases, a set of cardinality equal to the number of source symbols is
 sufficient; in rare cases, a set of cardinality slightly more than
 the number of source symbols is required.
 The RaptorQ code described here is a systematic code, meaning that
 all the source symbols are among the encoding symbols that can be
 generated.

Status of This Memo

 This is an Internet Standards Track document.
 This document is a product of the Internet Engineering Task Force
 (IETF).  It represents the consensus of the IETF community.  It has
 received public review and has been approved for publication by the
 Internet Engineering Steering Group (IESG).  Further information on
 Internet Standards is available in Section 2 of RFC 5741.

Luby, et al. Standards Track [Page 1] RFC 6330 RaptorQ FEC Scheme August 2011

 Information about the current status of this document, any errata,
 and how to provide feedback on it may be obtained at
 http://www.rfc-editor.org/info/rfc6330.

Copyright Notice

 Copyright (c) 2011 IETF Trust and the persons identified as the
 document authors.  All rights reserved.
 This document is subject to BCP 78 and the IETF Trust's Legal
 Provisions Relating to IETF Documents
 (http://trustee.ietf.org/license-info) in effect on the date of
 publication of this document.  Please review these documents
 carefully, as they describe your rights and restrictions with respect
 to this document.  Code Components extracted from this document must
 include Simplified BSD License text as described in Section 4.e of
 the Trust Legal Provisions and are provided without warranty as
 described in the Simplified BSD License.

Luby, et al. Standards Track [Page 2] RFC 6330 RaptorQ FEC Scheme August 2011

Table of Contents

 1.  Introduction . . . . . . . . . . . . . . . . . . . . . . . . .  4
 2.  Requirements Notation  . . . . . . . . . . . . . . . . . . . .  4
 3.  Formats and Codes  . . . . . . . . . . . . . . . . . . . . . .  5
   3.1.  Introduction . . . . . . . . . . . . . . . . . . . . . . .  5
   3.2.  FEC Payload IDs  . . . . . . . . . . . . . . . . . . . . .  5
   3.3.  FEC Object Transmission Information  . . . . . . . . . . .  5
     3.3.1.  Mandatory  . . . . . . . . . . . . . . . . . . . . . .  5
     3.3.2.  Common . . . . . . . . . . . . . . . . . . . . . . . .  5
     3.3.3.  Scheme-Specific  . . . . . . . . . . . . . . . . . . .  6
 4.  Procedures . . . . . . . . . . . . . . . . . . . . . . . . . .  7
   4.1.  Introduction . . . . . . . . . . . . . . . . . . . . . . .  7
   4.2.  Content Delivery Protocol Requirements . . . . . . . . . .  7
   4.3.  Example Parameter Derivation Algorithm . . . . . . . . . .  7
   4.4.  Object Delivery  . . . . . . . . . . . . . . . . . . . . .  9
     4.4.1.  Source Block Construction  . . . . . . . . . . . . . .  9
     4.4.2.  Encoding Packet Construction . . . . . . . . . . . . . 11
     4.4.3.  Example Receiver Recovery Strategies . . . . . . . . . 12
 5.  RaptorQ FEC Code Specification . . . . . . . . . . . . . . . . 12
   5.1.  Background . . . . . . . . . . . . . . . . . . . . . . . . 12
     5.1.1.  Definitions  . . . . . . . . . . . . . . . . . . . . . 13
     5.1.2.  Symbols  . . . . . . . . . . . . . . . . . . . . . . . 14
   5.2.  Overview . . . . . . . . . . . . . . . . . . . . . . . . . 17
   5.3.  Systematic RaptorQ Encoder . . . . . . . . . . . . . . . . 18
     5.3.1.  Introduction . . . . . . . . . . . . . . . . . . . . . 18
     5.3.2.  Encoding Overview  . . . . . . . . . . . . . . . . . . 19
     5.3.3.  First Encoding Step: Intermediate Symbol Generation  . 21
     5.3.4.  Second Encoding Step: Encoding . . . . . . . . . . . . 27
     5.3.5.  Generators . . . . . . . . . . . . . . . . . . . . . . 27
   5.4.  Example FEC Decoder  . . . . . . . . . . . . . . . . . . . 30
     5.4.1.  General  . . . . . . . . . . . . . . . . . . . . . . . 30
     5.4.2.  Decoding an Extended Source Block  . . . . . . . . . . 31
   5.5.  Random Numbers . . . . . . . . . . . . . . . . . . . . . . 36
     5.5.1.  The Table V0 . . . . . . . . . . . . . . . . . . . . . 36
     5.5.2.  The Table V1 . . . . . . . . . . . . . . . . . . . . . 37
     5.5.3.  The Table V2 . . . . . . . . . . . . . . . . . . . . . 38
     5.5.4.  The Table V3 . . . . . . . . . . . . . . . . . . . . . 40
   5.6.  Systematic Indices and Other Parameters  . . . . . . . . . 41
   5.7.  Operating with Octets, Symbols, and Matrices . . . . . . . 62
     5.7.1.  General  . . . . . . . . . . . . . . . . . . . . . . . 62
     5.7.2.  Arithmetic Operations on Octets  . . . . . . . . . . . 62
     5.7.3.  The Table OCT_EXP  . . . . . . . . . . . . . . . . . . 63
     5.7.4.  The Table OCT_LOG  . . . . . . . . . . . . . . . . . . 64
     5.7.5.  Operations on Symbols  . . . . . . . . . . . . . . . . 65
     5.7.6.  Operations on Matrices . . . . . . . . . . . . . . . . 65
   5.8.  Requirements for a Compliant Decoder . . . . . . . . . . . 65
 6.  Security Considerations  . . . . . . . . . . . . . . . . . . . 66

Luby, et al. Standards Track [Page 3] RFC 6330 RaptorQ FEC Scheme August 2011

 7.  IANA Considerations  . . . . . . . . . . . . . . . . . . . . . 67
 8.  Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 67
 9.  References . . . . . . . . . . . . . . . . . . . . . . . . . . 67
   9.1.  Normative References . . . . . . . . . . . . . . . . . . . 67
   9.2.  Informative References . . . . . . . . . . . . . . . . . . 68

1. Introduction

 This document specifies an FEC scheme for the RaptorQ forward error
 correction code for object delivery applications.  The concept of an
 FEC scheme is defined in RFC 5052 [RFC5052], and this document
 follows the format prescribed there and uses the terminology of that
 document.  The RaptorQ code described herein is a next generation of
 the Raptor code described in RFC 5053 [RFC5053].  The RaptorQ code
 provides superior reliability, better coding efficiency, and support
 for larger source block sizes than the Raptor code of RFC 5053
 [RFC5053].  These improvements simplify the usage of the RaptorQ code
 in an object delivery Content Delivery Protocol compared to RFC 5053
 RFC 5053 [RFC5053].  A detailed mathematical design and analysis of
 the RaptorQ code together with extensive simulation results are
 provided in [RaptorCodes].
 The RaptorQ FEC scheme is a Fully-Specified FEC scheme corresponding
 to FEC Encoding ID 6.
 RaptorQ is a fountain code, i.e., as many encoding symbols as needed
 can be generated on the fly by the encoder from the source symbols of
 a block.  The decoder is able to recover the source block from almost
 any set of encoding symbols of cardinality only slightly larger than
 the number of source symbols.
 The code described in this document is a systematic code; that is,
 the original unmodified source symbols, as well as a number of repair
 symbols, can be sent from sender to receiver.  For more background on
 the use of Forward Error Correction codes in reliable multicast, see
 [RFC3453].

2. Requirements Notation

 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
 document are to be interpreted as described in [RFC2119].

Luby, et al. Standards Track [Page 4] RFC 6330 RaptorQ FEC Scheme August 2011

3. Formats and Codes

3.1. Introduction

 The octet order of all fields is network byte order, i.e., big-
 endian.

3.2. FEC Payload IDs

 The FEC Payload ID MUST be a 4-octet field defined as follows:
      0                   1                   2                   3
      0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |     SBN       |               Encoding Symbol ID              |
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
                    Figure 1: FEC Payload ID Format
 o  Source Block Number (SBN): 8-bit unsigned integer.  A non-negative
    integer identifier for the source block that the encoding symbols
    within the packet relate to.
 o  Encoding Symbol ID (ESI): 24-bit unsigned integer.  A non-negative
    integer identifier for the encoding symbols within the packet.
 The interpretation of the Source Block Number and Encoding Symbol
 Identifier is defined in Section 4.

3.3. FEC Object Transmission Information

3.3.1. Mandatory

 The value of the FEC Encoding ID MUST be 6, as assigned by IANA (see
 Section 7).

3.3.2. Common

 The Common FEC Object Transmission Information elements used by this
 FEC scheme are:
 o  Transfer Length (F): 40-bit unsigned integer.  A non-negative
    integer that is at most 946270874880.  This is the transfer length
    of the object in units of octets.
 o  Symbol Size (T): 16-bit unsigned integer.  A positive integer that
    is less than 2^^16.  This is the size of a symbol in units of
    octets.

Luby, et al. Standards Track [Page 5] RFC 6330 RaptorQ FEC Scheme August 2011

 The encoded Common FEC Object Transmission Information (OTI) format
 is shown in Figure 2.
     0                   1                   2                   3
     0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                      Transfer Length (F)                      |
    +               +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |               |    Reserved   |           Symbol Size (T)     |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        Figure 2: Encoded Common FEC OTI for RaptorQ FEC Scheme
    NOTE: The limit of 946270874880 on the transfer length is a
    consequence of the limitation on the symbol size to 2^^16-1, the
    limitation on the number of symbols in a source block to 56403,
    and the limitation on the number of source blocks to 2^^8.

3.3.3. Scheme-Specific

 The following parameters are carried in the Scheme-Specific FEC
 Object Transmission Information element for this FEC scheme:
 o  The number of source blocks (Z): 8-bit unsigned integer.
 o  The number of sub-blocks (N): 16-bit unsigned integer.
 o  A symbol alignment parameter (Al): 8-bit unsigned integer.
 These parameters are all positive integers.  The encoded Scheme-
 specific Object Transmission Information is a 4-octet field
 consisting of the parameters Z, N, and Al as shown in Figure 3.
      0                   1                   2                   3
      0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |       Z       |              N                |       Al      |
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 Figure 3: Encoded Scheme-Specific FEC Object Transmission Information
 The encoded FEC Object Transmission Information is a 12-octet field
 consisting of the concatenation of the encoded Common FEC Object
 Transmission Information and the encoded Scheme-specific FEC Object
 Transmission Information.
 These three parameters define the source block partitioning as
 described in Section 4.4.1.2.

Luby, et al. Standards Track [Page 6] RFC 6330 RaptorQ FEC Scheme August 2011

4. Procedures

4.1. Introduction

 For any undefined symbols or functions used in this section, in
 particular the functions "ceil" and "floor", refer to Section 5.1.

4.2. Content Delivery Protocol Requirements

 This section describes the information exchange between the RaptorQ
 FEC scheme and any Content Delivery Protocol (CDP) that makes use of
 the RaptorQ FEC scheme for object delivery.
 The RaptorQ encoder scheme and RaptorQ decoder scheme for object
 delivery require the following information from the CDP:
 o  F: the transfer length of the object, in octets
 o  Al: the symbol alignment parameter
 o  T: the symbol size in octets, which MUST be a multiple of Al
 o  Z: the number of source blocks
 o  N: the number of sub-blocks in each source block
 The RaptorQ encoder scheme for object delivery additionally requires:
  1. the object to be encoded, which is F octets long
 The RaptorQ encoder scheme supplies the CDP with the following
 information for each packet to be sent:
 o  Source Block Number (SBN)
 o  Encoding Symbol ID (ESI)
 o  Encoding symbol(s)
 The CDP MUST communicate this information to the receiver.

4.3. Example Parameter Derivation Algorithm

 This section provides recommendations for the derivation of the three
 transport parameters, T, Z, and N.  This recommendation is based on
 the following input parameters:
 o  F: the transfer length of the object, in octets

Luby, et al. Standards Track [Page 7] RFC 6330 RaptorQ FEC Scheme August 2011

 o  WS: the maximum size block that is decodable in working memory, in
    octets
 o  P': the maximum payload size in octets, which is assumed to be a
    multiple of Al
 o  Al: the symbol alignment parameter, in octets
 o  SS: a parameter where the desired lower bound on the sub-symbol
    size is SS*Al
 o  K'_max: the maximum number of source symbols per source block.
       Note: Section 5.1.2 defines K'_max to be 56403.
 Based on the above inputs, the transport parameters T, Z, and N are
 calculated as follows:
 Let
 o  T = P'
 o  Kt = ceil(F/T)
 o  N_max = floor(T/(SS*Al))
 o  for all n=1, ..., N_max
  • KL(n) is the maximum K' value in Table 2 in Section 5.6 such

that

          K' <= WS/(Al*(ceil(T/(Al*n))))
 o  Z = ceil(Kt/KL(N_max))
 o  N is the minimum n=1, ..., N_max such that ceil(Kt/Z) <= KL(n)
 It is RECOMMENDED that each packet contains exactly one symbol.
 However, receivers SHALL support the reception of packets that
 contain multiple symbols.
 The value Kt is the total number of symbols required to represent the
 source data of the object.
 The algorithm above and that defined in Section 4.4.1.2 ensure that
 the sub-symbol sizes are a multiple of the symbol alignment
 parameter, Al.  This is useful because the sum operations used for
 encoding and decoding are generally performed several octets at a

Luby, et al. Standards Track [Page 8] RFC 6330 RaptorQ FEC Scheme August 2011

 time, for example, at least 4 octets at a time on a 32-bit processor.
 Thus, the encoding and decoding can be performed faster if the sub-
 symbol sizes are a multiple of this number of octets.
 The recommended setting for the input parameter Al is 4.
 The parameter WS can be used to generate encoded data that can be
 decoded efficiently with limited working memory at the decoder.  Note
 that the actual maximum decoder memory requirement for a given value
 of WS depends on the implementation, but it is possible to implement
 decoding using working memory only slightly larger than WS.

4.4. Object Delivery

4.4.1. Source Block Construction

4.4.1.1. General

 In order to apply the RaptorQ encoder to a source object, the object
 may be broken into Z >= 1 blocks, known as source blocks.  The
 RaptorQ encoder is applied independently to each source block.  Each
 source block is identified by a unique Source Block Number (SBN),
 where the first source block has SBN zero, the second has SBN one,
 etc.  Each source block is divided into a number, K, of source
 symbols of size T octets each.  Each source symbol is identified by a
 unique Encoding Symbol Identifier (ESI), where the first source
 symbol of a source block has ESI zero, the second has ESI one, etc.
 Each source block with K source symbols is divided into N >= 1 sub-
 blocks, which are small enough to be decoded in the working memory.
 Each sub-block is divided into K sub-symbols of size T'.
 Note that the value of K is not necessarily the same for each source
 block of an object, and the value of T' may not necessarily be the
 same for each sub-block of a source block.  However, the symbol size
 T is the same for all source blocks of an object, and the number of
 symbols K is the same for every sub-block of a source block.  Exact
 partitioning of the object into source blocks and sub-blocks is
 described in Section 4.4.1.2 below.

4.4.1.2. Source Block and Sub-Block Partitioning

 The construction of source blocks and sub-blocks is determined based
 on five input parameters -- F, Al, T, Z, and N -- and a function
 Partition[].  The five input parameters are defined as follows:
 o  F: the transfer length of the object, in octets

Luby, et al. Standards Track [Page 9] RFC 6330 RaptorQ FEC Scheme August 2011

 o  Al: a symbol alignment parameter, in octets
 o  T: the symbol size, in octets, which MUST be a multiple of Al
 o  Z: the number of source blocks
 o  N: the number of sub-blocks in each source block
 These parameters MUST be set so that ceil(ceil(F/T)/Z) <= K'_max.
 Recommendations for derivation of these parameters are provided in
 Section 4.3.
 The function Partition[I,J] derives parameters for partitioning a
 block of size I into J approximately equal-sized blocks.  More
 specifically, it partitions I into JL blocks of length IL and JS
 blocks of length IS.  The output of Partition[I, J] is the sequence
 (IL, IS, JL, JS), where IL = ceil(I/J), IS = floor(I/J), JL = I - IS
 * J, and JS = J - JL.
 The source object MUST be partitioned into source blocks and sub-
 blocks as follows:
 Let
 o  Kt = ceil(F/T),
 o  (KL, KS, ZL, ZS) = Partition[Kt, Z],
 o  (TL, TS, NL, NS) = Partition[T/Al, N].
 Then, the object MUST be partitioned into Z = ZL + ZS contiguous
 source blocks, the first ZL source blocks each having KL*T octets,
 i.e., KL source symbols of T octets each, and the remaining ZS source
 blocks each having KS*T octets, i.e., KS source symbols of T octets
 each.
 If Kt*T > F, then, for encoding purposes, the last symbol of the last
 source block MUST be padded at the end with Kt*T-F zero octets.
 Next, each source block with K source symbols MUST be divided into N
 = NL + NS contiguous sub-blocks, the first NL sub-blocks each
 consisting of K contiguous sub-symbols of size of TL*Al octets and
 the remaining NS sub-blocks each consisting of K contiguous sub-
 symbols of size of TS*Al octets.  The symbol alignment parameter Al
 ensures that sub-symbols are always a multiple of Al octets.

Luby, et al. Standards Track [Page 10] RFC 6330 RaptorQ FEC Scheme August 2011

 Finally, the mth symbol of a source block consists of the
 concatenation of the mth sub-symbol from each of the N sub-blocks.
 Note that this implies that when N > 1, a symbol is NOT a contiguous
 portion of the object.

4.4.2. Encoding Packet Construction

 Each encoding packet contains the following information:
 o  Source Block Number (SBN)
 o  Encoding Symbol ID (ESI)
 o  encoding symbol(s)
 Each source block is encoded independently of the others.  Each
 encoding packet contains encoding symbols generated from the one
 source block identified by the SBN carried in the encoding packet.
 Source blocks are numbered consecutively from zero.
 Encoding Symbol ID values from 0 to K-1 identify the source symbols
 of a source block in sequential order, where K is the number of
 source symbols in the source block.  Encoding Symbol IDs K onwards
 identify repair symbols generated from the source symbols using the
 RaptorQ encoder.
 Each encoding packet either contains only source symbols (source
 packet) or contains only repair symbols (repair packet).  A packet
 may contain any number of symbols from the same source block.  In the
 case that the last source symbol in a source packet includes padding
 octets added for FEC encoding purposes, then these octets need not be
 included in the packet.  Otherwise, each packet MUST contain only
 whole symbols.
 The Encoding Symbol ID, X, carried in each source packet is the
 Encoding Symbol ID of the first source symbol carried in that packet.
 The subsequent source symbols in the packet have Encoding Symbol IDs
 X+1 to X+G-1 in sequential order, where G is the number of symbols in
 the packet.
 Similarly, the Encoding Symbol ID, X, placed into a repair packet is
 the Encoding Symbol ID of the first repair symbol in the repair
 packet, and the subsequent repair symbols in the packet have Encoding
 Symbol IDs X+1 to X+G-1 in sequential order, where G is the number of
 symbols in the packet.
 Note that it is not necessary for the receiver to know the total
 number of repair packets.

Luby, et al. Standards Track [Page 11] RFC 6330 RaptorQ FEC Scheme August 2011

4.4.3. Example Receiver Recovery Strategies

 A receiver can use the received encoding symbols for each source
 block of an object to recover the source symbols for that source
 block independently of all other source blocks.
 If there is one sub-block per source block, i.e., N = 1, then the
 portion of the data in the original object in its original order
 associated with a source block consists of the concatenation of the
 source symbols of a source block in consecutive ESI order.
 If there are multiple sub-blocks per source block, i.e., if N > 1,
 then the portion of the data in the original object in its original
 order associated with a source block consists of the concatenation of
 the sub-blocks associated with the source block, where sub-symbols
 within each sub-block are in consecutive ESI order.  In this case,
 there are different receiver source block recovery strategies worth
 considering depending on the available amount of Random Access Memory
 (RAM) at the receiver, as outlined below.
 One strategy is to recover the source symbols of a source block using
 the decoding procedures applied to the received symbols for the
 source block to recover the source symbols as described in Section 5,
 and then to reorder the sub-symbols of the source symbols so that all
 consecutive sub-symbols of the first sub-block are first, followed by
 all consecutive sub-symbols of the second sub-block, etc., followed
 by all consecutive sub-symbols of the Nth sub-block.  This strategy
 is especially applicable if the receiver has enough RAM to decode an
 entire source block.
 Another strategy is to separately recover the sub-blocks of a source
 block.  For example, a receiver may demultiplex and store sub-symbols
 associated with each sub-block separately as packets containing
 encoding symbols arrive, and then use the stored sub-symbols received
 for a sub-block to recover that sub-block using the decoding
 procedures described in Section 5.  This strategy is especially
 applicable if the receiver has enough RAM to decode only one sub-
 block at a time.

5. RaptorQ FEC Code Specification

5.1. Background

 For the purpose of the RaptorQ FEC code specification in this
 section, the following definitions, symbols, and abbreviations apply.
 A basic understanding of linear algebra, matrix operations, and
 finite fields is assumed in this section.  In particular, matrix
 multiplication and matrix inversion operations over a mixture of the

Luby, et al. Standards Track [Page 12] RFC 6330 RaptorQ FEC Scheme August 2011

 finite fields GF[2] and GF[256] are used.  A basic familiarity with
 sparse linear equations, and efficient implementations of algorithms
 that take advantage of sparse linear equations, is also quite
 beneficial to an implementer of this specification.

5.1.1. Definitions

 o  Source block: a block of K source symbols that are considered
    together for RaptorQ encoding and decoding purposes.
 o  Extended Source Block: a block of K' source symbols, where K' >=
    K, constructed from a source block and zero or more padding
    symbols.
 o  Symbol: a unit of data.  The size, in octets, of a symbol is known
    as the symbol size.  The symbol size is always a positive integer.
 o  Source symbol: the smallest unit of data used during the encoding
    process.  All source symbols within a source block have the same
    size.
 o  Padding symbol: a symbol with all zero bits that is added to the
    source block to form the extended source block.
 o  Encoding symbol: a symbol that can be sent as part of the encoding
    of a source block.  The encoding symbols of a source block consist
    of the source symbols of the source block and the repair symbols
    generated from the source block.  Repair symbols generated from a
    source block have the same size as the source symbols of that
    source block.
 o  Repair symbol: the encoding symbols of a source block that are not
    source symbols.  The repair symbols are generated based on the
    source symbols of a source block.
 o  Intermediate symbols: symbols generated from the source symbols
    using an inverse encoding process based on pre-coding
    relationships.  The repair symbols are then generated directly
    from the intermediate symbols.  The encoding symbols do not
    include the intermediate symbols, i.e., intermediate symbols are
    not sent as part of the encoding of a source block.  The
    intermediate symbols are partitioned into LT symbols and PI
    symbols for the purposes of the encoding process.
 o  LT symbols: a process similar to that described in [LTCodes] is
    used to generate part of the contribution to each generated
    encoding symbol from the portion of the intermediate symbols
    designated as LT symbols.

Luby, et al. Standards Track [Page 13] RFC 6330 RaptorQ FEC Scheme August 2011

 o  PI symbols: a process even simpler than that described in
    [LTCodes] is used to generate the other part of the contribution
    to each generated encoding symbol from the portion of the
    intermediate symbols designated as PI symbols.  In the decoding
    algorithm suggested in Section 5.4, the PI symbols are inactivated
    at the start, i.e., are placed into the matrix U at the beginning
    of the first phase of the decoding algorithm.  Because the symbols
    corresponding to the columns of U are sometimes called the
    "inactivated" symbols, and since the PI symbols are inactivated at
    the beginning, they are considered "permanently inactivated".
 o  HDPC symbols: there is a small subset of the intermediate symbols
    that are HDPC symbols.  Each HDPC symbol has a pre-coding
    relationship with a large fraction of the other intermediate
    symbols.  HDPC means "High Density Parity Check".
 o  LDPC symbols: there is a moderate-sized subset of the intermediate
    symbols that are LDPC symbols.  Each LDPC symbol has a pre-coding
    relationship with a small fraction of the other intermediate
    symbols.  LDPC means "Low Density Parity Check".
 o  Systematic code: a code in which all source symbols are included
    as part of the encoding symbols of a source block.  The RaptorQ
    code as described herein is a systematic code.
 o  Encoding Symbol ID (ESI): information that uniquely identifies
    each encoding symbol associated with a source block for sending
    and receiving purposes.
 o  Internal Symbol ID (ISI): information that uniquely identifies
    each symbol associated with an extended source block for encoding
    and decoding purposes.
 o  Arithmetic operations on octets and symbols and matrices: the
    operations that are used to produce encoding symbols from source
    symbols and vice versa.  See Section 5.7.

5.1.2. Symbols

 i, j, u, v, h, d, a, b, d1, a1, b1, v, m, x, y   represent values or
      variables of one type or another, depending on the context.
 X    denotes a non-negative integer value that is either an ISI value
      or an ESI value, depending on the context.
 ceil(x)  denotes the smallest integer that is greater than or equal
      to x, where x is a real value.

Luby, et al. Standards Track [Page 14] RFC 6330 RaptorQ FEC Scheme August 2011

 floor(x)  denotes the largest integer that is less than or equal to
      x, where x is a real value.
 min(x,y)  denotes the minimum value of the values x and y, and in
      general the minimum value of all the argument values.
 max(x,y)  denotes the maximum value of the values x and y, and in
      general the maximum value of all the argument values.
 i % j  denotes i modulo j.
 i + j  denotes the sum of i and j.  If i and j are octets or symbols,
      this designates the arithmetic on octets or symbols,
      respectively, as defined in Section 5.7.  If i and j are
      integers, then it denotes the usual integer addition.
 i * j  denotes the product of i and j.  If i and j are octets, this
      designates the arithmetic on octets, as defined in Section 5.7.
      If i is an octet and j is a symbol, this denotes the
      multiplication of a symbol by an octet, as also defined in
      Section 5.7.  Finally, if i and j are integers, i * j denotes
      the usual product of integers.
 a ^^ b  denotes the operation a raised to the power b.  If a is an
      octet and b is a non-negative integer, this is understood to
      mean a*a*...*a (b terms), with '*' being the octet product as
      defined in Section 5.7.
 u ^ v  denotes, for equal-length bit strings u and v, the bitwise
      exclusive-or of u and v.
 Transpose[A]  denotes the transposed matrix of matrix A.  In this
      specification, all matrices have entries that are octets.
 A^^-1  denotes the inverse matrix of matrix A.  In this
      specification, all the matrices have octets as entries, so it is
      understood that the operations of the matrix entries are to be
      done as stated in Section 5.7 and A^^-1 is the matrix inverse of
      A with respect to octet arithmetic.
 K    denotes the number of symbols in a single source block.
 K'   denotes the number of source plus padding symbols in an extended
      source block.  For the majority of this specification, the
      padding symbols are considered to be additional source symbols.
 K'_max  denotes the maximum number of source symbols that can be in a
      single source block.  Set to 56403.

Luby, et al. Standards Track [Page 15] RFC 6330 RaptorQ FEC Scheme August 2011

 L    denotes the number of intermediate symbols for a single extended
      source block.
 S    denotes the number of LDPC symbols for a single extended source
      block.  These are LT symbols.  For each value of K' shown in
      Table 2 in Section 5.6, the corresponding value of S is a prime
      number.
 H    denotes the number of HDPC symbols for a single extended source
      block.  These are PI symbols.
 B    denotes the number of intermediate symbols that are LT symbols
      excluding the LDPC symbols.
 W    denotes the number of intermediate symbols that are LT symbols.
      For each value of K' in Table 2 shown in Section 5.6, the
      corresponding value of W is a prime number.
 P    denotes the number of intermediate symbols that are PI symbols.
      These contain all HDPC symbols.
 P1   denotes the smallest prime number greater than or equal to P.
 U    denotes the number of non-HDPC intermediate symbols that are PI
      symbols.
 C    denotes an array of intermediate symbols, C[0], C[1], C[2], ...,
      C[L-1].
 C'   denotes an array of the symbols of the extended source block,
      where C'[0], C'[1], C'[2], ..., C'[K-1] are the source symbols
      of the source block and C'[K], C'[K+1], ..., C'[K'-1] are
      padding symbols.
 V0, V1, V2, V3  denote four arrays of 32-bit unsigned integers,
      V0[0], V0[1], ..., V0[255]; V1[0], V1[1], ..., V1[255]; V2[0],
      V2[1], ..., V2[255]; and V3[0], V3[1], ..., V3[255] as shown in
      Section 5.5.
 Rand[y, i, m]  denotes a pseudo-random number generator.
 Deg[v]  denotes a degree generator.
 Enc[K', C ,(d, a, b, d1, a1, b1)]  denotes an encoding symbol
      generator.
 Tuple[K', X]  denotes a tuple generator function.

Luby, et al. Standards Track [Page 16] RFC 6330 RaptorQ FEC Scheme August 2011

 T    denotes the symbol size in octets.
 J(K')  denotes the systematic index associated with K'.
 G    denotes any generator matrix.
 I_S  denotes the S x S identity matrix.

5.2. Overview

 This section defines the systematic RaptorQ FEC code.
 Symbols are the fundamental data units of the encoding and decoding
 process.  For each source block, all symbols are the same size,
 referred to as the symbol size T.  The atomic operations performed on
 symbols for both encoding and decoding are the arithmetic operations
 defined in Section 5.7.
 The basic encoder is described in Section 5.3.  The encoder first
 derives a block of intermediate symbols from the source symbols of a
 source block.  This intermediate block has the property that both
 source and repair symbols can be generated from it using the same
 process.  The encoder produces repair symbols from the intermediate
 block using an efficient process, where each such repair symbol is
 the exclusive-or of a small number of intermediate symbols from the
 block.  Source symbols can also be reproduced from the intermediate
 block using the same process.  The encoding symbols are the
 combination of the source and repair symbols.
 An example of a decoder is described in Section 5.4.  The process for
 producing source and repair symbols from the intermediate block is
 designed so that the intermediate block can be recovered from any
 sufficiently large set of encoding symbols, independent of the mix of
 source and repair symbols in the set.  Once the intermediate block is
 recovered, missing source symbols of the source block can be
 recovered using the encoding process.
 Requirements for a RaptorQ-compliant decoder are provided in
 Section 5.8.  A number of decoding algorithms are possible to achieve
 these requirements.  An efficient decoding algorithm to achieve these
 requirements is provided in Section 5.4.
 The construction of the intermediate and repair symbols is based in
 part on a pseudo-random number generator described in Section 5.3.
 This generator is based on a fixed set of 1024 random numbers that
 must be available to both sender and receiver.  These numbers are

Luby, et al. Standards Track [Page 17] RFC 6330 RaptorQ FEC Scheme August 2011

 provided in Section 5.5.  Encoding and decoding operations for
 RaptorQ use operations on octets.  Section 5.7 describes how to
 perform these operations.
 Finally, the construction of the intermediate symbols from the source
 symbols is governed by "systematic indices", values of which are
 provided in Section 5.6 for specific extended source block sizes
 between 6 and K'_max = 56403 source symbols.  Thus, the RaptorQ code
 supports source blocks with between 1 and 56403 source symbols.

5.3. Systematic RaptorQ Encoder

5.3.1. Introduction

 For a given source block of K source symbols, for encoding and
 decoding purposes, the source block is augmented with K'-K additional
 padding symbols, where K' is the smallest value that is at least K in
 the systematic index Table 2 of Section 5.6.  The reason for padding
 out a source block to a multiple of K' is to enable faster encoding
 and decoding and to minimize the amount of table information that
 needs to be stored in the encoder and decoder.
 For purposes of transmitting and receiving data, the value of K is
 used to determine the number of source symbols in a source block, and
 thus K needs to be known at the sender and the receiver.  In this
 case, the sender and receiver can compute K' from K and the K'-K
 padding symbols can be automatically added to the source block
 without any additional communication.  The encoding symbol ID (ESI)
 is used by a sender and receiver to identify the encoding symbols of
 a source block, where the encoding symbols of a source block consist
 of the source symbols and the repair symbols associated with the
 source block.  For a source block with K source symbols, the ESIs for
 the source symbols are 0, 1, 2, ..., K-1, and the ESIs for the repair
 symbols are K, K+1, K+2, ....  Using the ESI for identifying encoding
 symbols in transport ensures that the ESI values continue
 consecutively between the source and repair symbols.
 For purposes of encoding and decoding data, the value of K' derived
 from K is used as the number of source symbols of the extended source
 block upon which encoding and decoding operations are performed,
 where the K' source symbols consist of the original K source symbols
 and an additional K'-K padding symbols.  The Internal Symbol ID (ISI)
 is used by the encoder and decoder to identify the symbols associated
 with the extended source block, i.e., for generating encoding symbols
 and for decoding.  For a source block with K original source symbols,
 the ISIs for the original source symbols are 0, 1, 2, ..., K-1, the
 ISIs for the K'-K padding symbols are K, K+1, K+2, ..., K'-1, and the
 ISIs for the repair symbols are K', K'+1, K'+2, ....  Using the ISI

Luby, et al. Standards Track [Page 18] RFC 6330 RaptorQ FEC Scheme August 2011

 for encoding and decoding allows the padding symbols of the extended
 source block to be treated the same way as other source symbols of
 the extended source block.  Also, it ensures that a given prefix of
 repair symbols are generated in a consistent way for a given number
 K' of source symbols in the extended source block, independent of K.
 The relationship between the ESIs and the ISIs is simple: the ESIs
 and the ISIs for the original K source symbols are the same, the K'-K
 padding symbols have an ISI but do not have a corresponding ESI
 (since they are symbols that are neither sent nor received), and a
 repair symbol ISI is simply the repair symbol ESI plus K'-K.  The
 translation between ESIs (used to identify encoding symbols sent and
 received) and the corresponding ISIs (used for encoding and
 decoding), as well as determining the proper padding of the extended
 source block with padding symbols (used for encoding and decoding),
 is the internal responsibility of the RaptorQ encoder/decoder.

5.3.2. Encoding Overview

 The systematic RaptorQ encoder is used to generate any number of
 repair symbols from a source block that consists of K source symbols
 placed into an extended source block C'.  Figure 4 shows the encoding
 overview.
 The first step of encoding is to construct an extended source block
 by adding zero or more padding symbols such that the total number of
 symbols, K', is one of the values listed in Section 5.6.  Each
 padding symbol consists of T octets where the value of each octet is
 zero.  K' MUST be selected as the smallest value of K' from the table
 of Section 5.6 that is greater than or equal to K.

Luby, et al. Standards Track [Page 19] RFC 6330 RaptorQ FEC Scheme August 2011

  1. ———————————————————-+

| |

       |    +-----------+    +--------------+    +-------------+  |
    C' |    |           | C' | Intermediate | C  |             |  |
   ----+--->|  Padding  |--->|    Symbol    |--->|   Encoding  |--+-->
    K  |    |           | K' |  Generation  | L  |             |  |
       |    +-----------+    +--------------+    +-------------+  |
       |           |                             (d,a,b, ^        |
       |           |                            d1,a1,b1)|        |
       |           |                              +------------+  |
       |           |              K'              |   Tuple    |  |
       |           +----------------------------->|            |  |
       |                                          | Generation |  |
       |                                          +------------+  |
       |                                                 ^        |
       +-------------------------------------------------+--------+
                                                         |
                                                       ISI X
                      Figure 4: Encoding Overview
 Let C'[0], ..., C'[K-1] denote the K source symbols.
 Let C'[K], ..., C'[K'-1] denote the K'-K padding symbols, which are
 all set to zero bits.  Then, C'[0], ..., C'[K'-1] are the symbols of
 the extended source block upon which encoding and decoding are
 performed.
 In the remainder of this description, these padding symbols will be
 considered as additional source symbols and referred to as such.
 However, these padding symbols are not part of the encoding symbols,
 i.e., they are not sent as part of the encoding.  At a receiver, the
 value of K' can be computed based on K, then the receiver can insert
 K'-K padding symbols at the end of a source block of K' source
 symbols and recover the remaining K source symbols of the source
 block from received encoding symbols.
 The second step of encoding is to generate a number, L > K', of
 intermediate symbols from the K' source symbols.  In this step, K'
 source tuples (d[0], a[0], b[0], d1[0], a1[0], b1[0]), ..., (d[K'-1],
 a[K'-1], b[K'-1], d1[K'-1], a1[K'-1], b1[K'-1]) are generated using
 the Tuple[] generator as described in Section 5.3.5.4.  The K' source
 tuples and the ISIs associated with the K' source symbols are used to
 determine L intermediate symbols C[0], ..., C[L-1] from the source
 symbols using an inverse encoding process.  This process can be
 realized by a RaptorQ decoding process.

Luby, et al. Standards Track [Page 20] RFC 6330 RaptorQ FEC Scheme August 2011

 Certain "pre-coding relationships" must hold within the L
 intermediate symbols.  Section 5.3.3.3 describes these relationships.
 Section 5.3.3.4 describes how the intermediate symbols are generated
 from the source symbols.
 Once the intermediate symbols have been generated, repair symbols can
 be produced.  For a repair symbol with ISI X > K', the tuple of non-
 negative integers (d, a, b, d1, a1, b1) can be generated, using the
 Tuple[] generator as described in Section 5.3.5.4.  Then, the (d, a,
 b, d1, a1, b1) tuple and the ISI X are used to generate the
 corresponding repair symbol from the intermediate symbols using the
 Enc[] generator described in Section 5.3.5.3.  The corresponding ESI
 for this repair symbol is then X-(K'-K).  Note that source symbols of
 the extended source block can also be generated using the same
 process, i.e., for any X < K', the symbol generated using this
 process has the same value as C'[X].

5.3.3. First Encoding Step: Intermediate Symbol Generation

5.3.3.1. General

 This encoding step is a pre-coding step to generate the L
 intermediate symbols C[0], ..., C[L-1] from the source symbols C'[0],
 ..., C'[K'-1], where L > K' is defined in Section 5.3.3.3.  The
 intermediate symbols are uniquely defined by two sets of constraints:
 1.  The intermediate symbols are related to the source symbols by a
     set of source symbol tuples and by the ISIs of the source
     symbols.  The generation of the source symbol tuples is defined
     in Section 5.3.3.2 using the Tuple[] generator as described in
     Section 5.3.5.4.
 2.  A number of pre-coding relationships hold within the intermediate
     symbols themselves.  These are defined in Section 5.3.3.3.
 The generation of the L intermediate symbols is then defined in
 Section 5.3.3.4.

5.3.3.2. Source Symbol Tuples

 Each of the K' source symbols is associated with a source symbol
 tuple (d[X], a[X], b[X], d1[X], a1[X], b1[X]) for 0 <= X < K'.  The
 source symbol tuples are determined using the Tuple[] generator
 defined in Section 5.3.5.4 as:
    For each X, 0 <= X < K'
       (d[X], a[X], b[X], d1[X], a1[X], b1[X]) = Tuple[K, X]

Luby, et al. Standards Track [Page 21] RFC 6330 RaptorQ FEC Scheme August 2011

5.3.3.3. Pre-Coding Relationships

 The pre-coding relationships amongst the L intermediate symbols are
 defined by requiring that a set of S+H linear combinations of the
 intermediate symbols evaluate to zero.  There are S LDPC and H HDPC
 symbols, and thus L = K'+S+H.  Another partition of the L
 intermediate symbols is into two sets, one set of W LT symbols and
 another set of P PI symbols, and thus it is also the case that L =
 W+P.  The P PI symbols are treated differently than the W LT symbols
 in the encoding process.  The P PI symbols consist of the H HDPC
 symbols together with a set of U = P-H of the other K' intermediate
 symbols.  The W LT symbols consist of the S LDPC symbols together
 with W-S of the other K' intermediate symbols.  The values of these
 parameters are determined from K' as described below, where H(K'),
 S(K'), and W(K') are derived from Table 2 in Section 5.6.
 Let
 o  S = S(K')
 o  H = H(K')
 o  W = W(K')
 o  L = K' + S + H
 o  P = L - W
 o  P1 denote the smallest prime number greater than or equal to P.
 o  U = P - H
 o  B = W - S
 o  C[0], ..., C[B-1] denote the intermediate symbols that are LT
    symbols but not LDPC symbols.
 o  C[B], ..., C[B+S-1] denote the S LDPC symbols that are also LT
    symbols.
 o  C[W], ..., C[W+U-1] denote the intermediate symbols that are PI
    symbols but not HDPC symbols.
 o  C[L-H], ..., C[L-1] denote the H HDPC symbols that are also PI
    symbols.

Luby, et al. Standards Track [Page 22] RFC 6330 RaptorQ FEC Scheme August 2011

 The first set of pre-coding relations, called LDPC relations, is
 described below and requires that at the end of this process the set
 of symbols D[0] , ..., D[S-1] are all zero:
 o  Initialize the symbols D[0] = C[B], ..., D[S-1] = C[B+S-1].
 o  For i = 0, ..., B-1 do
  • a = 1 + floor(i/S)
  • b = i % S
  • D[b] = D[b] + C[i]
  • b = (b + a) % S
  • D[b] = D[b] + C[i]
  • b = (b + a) % S
  • D[b] = D[b] + C[i]
 o  For i = 0, ..., S-1 do
  • a = i % P
  • b = (i+1) % P
  • D[i] = D[i] + C[W+a] + C[W+b]
 Recall that the addition of symbols is to be carried out as specified
 in Section 5.7.
 Note that the LDPC relations as defined in the algorithm above are
 linear, so there exists an S x B matrix G_LDPC,1 and an S x P matrix
 G_LDPC,2 such that
    G_LDPC,1 * Transpose[(C[0], ..., C[B-1])] + G_LDPC,2 *
    Transpose(C[W], ..., C[W+P-1]) + Transpose[(C[B], ..., C[B+S-1])]
    = 0
 (The matrix G_LDPC,1 is defined by the first loop in the above
 algorithm, and G_LDPC,2 can be deduced from the second loop.)
 The second set of relations among the intermediate symbols C[0], ...,
 C[L-1] are the HDPC relations and they are defined as follows:

Luby, et al. Standards Track [Page 23] RFC 6330 RaptorQ FEC Scheme August 2011

 Let
 o  alpha denote the octet represented by integer 2 as defined in
    Section 5.7.
 o  MT denote an H x (K' + S) matrix of octets, where for j=0, ...,
    K'+S-2, the entry MT[i,j] is the octet represented by the integer
    1 if i= Rand[j+1,6,H] or i = (Rand[j+1,6,H] + Rand[j+1,7,H-1] + 1)
    % H, and MT[i,j] is the zero element for all other values of i,
    and for j=K'+S-1, MT[i,j] = alpha^^i for i=0, ..., H-1.
 o  GAMMA denote a (K'+S) x (K'+S) matrix of octets, where
       GAMMA[i,j] =
          alpha ^^ (i-j) for i >= j,
          0 otherwise.
 Then, the relationship between the first K'+S intermediate symbols
 C[0], ..., C[K'+S-1] and the H HDPC symbols C[K'+S], ..., C[K'+S+H-1]
 is given by:
    Transpose[C[K'+S], ..., C[K'+S+H-1]] + MT * GAMMA *
    Transpose[C[0], ..., C[K'+S-1]] = 0,
 where '*' represents standard matrix multiplication utilizing the
 octet multiplication to define the multiplication between a matrix of
 octets and a matrix of symbols (in particular, the column vector of
 symbols), and '+' denotes addition over octet vectors.

5.3.3.4. Intermediate Symbols

5.3.3.4.1. Definition

 Given the K' source symbols C'[0], C'[1], ..., C'[K'-1] the L
 intermediate symbols C[0], C[1], ..., C[L-1] are the uniquely defined
 symbol values that satisfy the following conditions:
 1.  The K' source symbols C'[0], C'[1], ..., C'[K'-1] satisfy the K'
     constraints
        C'[X] = Enc[K', (C[0], ..., C[L-1]), (d[X], a[X], b[X], d1[X],
        a1[X], b1[X])], for all X, 0 <= X < K',
     where (d[X], a[X], b[X], d1[X], a1[X], b1[X])) = Tuple[K',X],
     Tuple[] is defined in Section 5.3.5.4, and Enc[] is described in
     Section 5.3.5.3.

Luby, et al. Standards Track [Page 24] RFC 6330 RaptorQ FEC Scheme August 2011

 2.  The L intermediate symbols C[0], C[1], ..., C[L-1] satisfy the
     pre-coding relationships defined in Section 5.3.3.3.

5.3.3.4.2. Example Method for Calculation of Intermediate Symbols

 This section describes a possible method for calculation of the L
 intermediate symbols C[0], C[1], ..., C[L-1] satisfying the
 constraints in Section 5.3.3.4.1.
 The L intermediate symbols can be calculated as follows:
 Let
 o  C denote the column vector of the L intermediate symbols, C[0],
    C[1], ..., C[L-1].
 o  D denote the column vector consisting of S+H zero symbols followed
    by the K' source symbols C'[0], C'[1], ..., C'[K'-1].
 Then, the above constraints define an L x L matrix A of octets such
 that:
    A*C = D
 The matrix A can be constructed as follows:
 Let
 o  G_LDPC,1 and G_LDPC,2 be S x B and S x P matrices as defined in
    Section 5.3.3.3.
 o  G_HDPC be the H x (K'+S) matrix such that
       G_HDPC * Transpose(C[0], ..., C[K'+S-1]) = Transpose(C[K'+S],
       ..., C[L-1]),
       i.e., G_HDPC = MT*GAMMA
 o  I_S be the S x S identity matrix
 o  I_H be the H x H identity matrix
 o  G_ENC be the K' x L matrix such that
       G_ENC * Transpose[(C[0], ..., C[L-1])] =
       Transpose[(C'[0],C'[1], ...,C'[K'-1])],

Luby, et al. Standards Track [Page 25] RFC 6330 RaptorQ FEC Scheme August 2011

       i.e., G_ENC[i,j] = 1 if and only if C[j] is included in the
       symbols that are summed to produce Enc[K', (C[0], ..., C[L-1]),
       (d[i], a[i], b[i], d1[i], a1[i], b1[i])] and G_ENC[i,j] = 0
       otherwise.
 Then
 o  The first S rows of A are equal to G_LDPC,1 | I_S | G_LDPC,2.
 o  The next H rows of A are equal to G_HDPC | I_H.
 o  The remaining K' rows of A are equal to G_ENC.
 The matrix A is depicted in Figure 5 below:
                     B               S         U         H
          +-----------------------+-------+------------------+
          |                       |       |                  |
        S |        G_LDPC,1       |  I_S  |      G_LDPC,2    |
          |                       |       |                  |
          +-----------------------+-------+----------+-------+
          |                                          |       |
        H |                G_HDPC                    |  I_H  |
          |                                          |       |
          +------------------------------------------+-------+
          |                                                  |
          |                                                  |
       K' |                      G_ENC                       |
          |                                                  |
          |                                                  |
          +--------------------------------------------------+
                           Figure 5: The Matrix A
 The intermediate symbols can then be calculated as:
    C = (A^^-1)*D
 The source tuples are generated such that for any K' matrix A has
 full rank and is therefore invertible.  This calculation can be
 realized by applying a RaptorQ decoding process to the K' source
 symbols C'[0], C'[1], ..., C'[K'-1] to produce the L intermediate
 symbols C[0], C[1], ..., C[L-1].
 To efficiently generate the intermediate symbols from the source
 symbols, it is recommended that an efficient decoder implementation
 such as that described in Section 5.4 be used.

Luby, et al. Standards Track [Page 26] RFC 6330 RaptorQ FEC Scheme August 2011

5.3.4. Second Encoding Step: Encoding

 In the second encoding step, the repair symbol with ISI X (X >= K')
 is generated by applying the generator Enc[K', (C[0], C[1], ...,
 C[L-1]), (d, a, b, d1, a1, b1)] defined in Section 5.3.5.3 to the L
 intermediate symbols C[0], C[1], ..., C[L-1] using the tuple (d, a,
 b, d1, a1, b1)=Tuple[K',X].

5.3.5. Generators

5.3.5.1. Random Number Generator

 The random number generator Rand[y, i, m] is defined as follows,
 where y is a non-negative integer, i is a non-negative integer less
 than 256, and m is a positive integer, and the value produced is an
 integer between 0 and m-1.  Let V0, V1, V2, and V3 be the arrays
 provided in Section 5.5.
 Let
 o  x0 = (y + i) mod 2^^8
 o  x1 = (floor(y / 2^^8) + i) mod 2^^8
 o  x2 = (floor(y / 2^^16) + i) mod 2^^8
 o  x3 = (floor(y / 2^^24) + i) mod 2^^8
 Then
    Rand[y, i, m] = (V0[x0] ^ V1[x1] ^ V2[x2] ^ V3[x3]) % m

5.3.5.2. Degree Generator

 The degree generator Deg[v] is defined as follows, where v is a non-
 negative integer that is less than 2^^20 = 1048576.  Given v, find
 index d in Table 1 such that f[d-1] <= v < f[d], and set Deg[v] =
 min(d, W-2).  Recall that W is derived from K' as described in
 Section 5.3.3.3.

Luby, et al. Standards Track [Page 27] RFC 6330 RaptorQ FEC Scheme August 2011

               +---------+---------+---------+---------+
               | Index d | f[d]    | Index d | f[d]    |
               +---------+---------+---------+---------+
               | 0       | 0       | 1       | 5243    |
               +---------+---------+---------+---------+
               | 2       | 529531  | 3       | 704294  |
               +---------+---------+---------+---------+
               | 4       | 791675  | 5       | 844104  |
               +---------+---------+---------+---------+
               | 6       | 879057  | 7       | 904023  |
               +---------+---------+---------+---------+
               | 8       | 922747  | 9       | 937311  |
               +---------+---------+---------+---------+
               | 10      | 948962  | 11      | 958494  |
               +---------+---------+---------+---------+
               | 12      | 966438  | 13      | 973160  |
               +---------+---------+---------+---------+
               | 14      | 978921  | 15      | 983914  |
               +---------+---------+---------+---------+
               | 16      | 988283  | 17      | 992138  |
               +---------+---------+---------+---------+
               | 18      | 995565  | 19      | 998631  |
               +---------+---------+---------+---------+
               | 20      | 1001391 | 21      | 1003887 |
               +---------+---------+---------+---------+
               | 22      | 1006157 | 23      | 1008229 |
               +---------+---------+---------+---------+
               | 24      | 1010129 | 25      | 1011876 |
               +---------+---------+---------+---------+
               | 26      | 1013490 | 27      | 1014983 |
               +---------+---------+---------+---------+
               | 28      | 1016370 | 29      | 1017662 |
               +---------+---------+---------+---------+
               | 30      | 1048576 |         |         |
               +---------+---------+---------+---------+
     Table 1: Defines the Degree Distribution for Encoding Symbols

5.3.5.3. Encoding Symbol Generator

 The encoding symbol generator Enc[K', (C[0], C[1], ..., C[L-1]), (d,
 a, b, d1, a1, b1)] takes the following inputs:
 o  K' is the number of source symbols for the extended source block.
    Let L, W, B, S, P, and P1 be derived from K' as described in
    Section 5.3.3.3.

Luby, et al. Standards Track [Page 28] RFC 6330 RaptorQ FEC Scheme August 2011

 o  (C[0], C[1], ..., C[L-1]) is the array of L intermediate symbols
    (sub-symbols) generated as described in Section 5.3.3.4.
 o  (d, a, b, d1, a1, b1) is a source tuple determined from ISI X
    using the Tuple[] generator defined in Section 5.3.5.4, whereby
  • d is a positive integer denoting an encoding symbol LT degree
  • a is a positive integer between 1 and W-1 inclusive
  • b is a non-negative integer between 0 and W-1 inclusive
  • d1 is a positive integer that has value either 2 or 3 denoting

an encoding symbol PI degree

  • a1 is a positive integer between 1 and P1-1 inclusive
  • b1 is a non-negative integer between 0 and P1-1 inclusive
 The encoding symbol generator produces a single encoding symbol as
 output (referred to as result), according to the following algorithm:
 o  result = C[b]
 o  For j = 1, ..., d-1 do
  • b = (b + a) % W
  • result = result + C[b]
 o  While (b1 >= P) do b1 = (b1+a1) % P1
 o  result = result + C[W+b1]
 o  For j = 1, ..., d1-1 do
  • b1 = (b1 + a1) % P1
  • While (b1 >= P) do b1 = (b1+a1) % P1
  • result = result + C[W+b1]
 o  Return result

Luby, et al. Standards Track [Page 29] RFC 6330 RaptorQ FEC Scheme August 2011

5.3.5.4. Tuple Generator

 The tuple generator Tuple[K',X] takes the following inputs:
 o  K': the number of source symbols in the extended source block
 o  X: an ISI
 Let
 o  L be determined from K' as described in Section 5.3.3.3
 o  J = J(K') be the systematic index associated with K', as defined
    in Table 2 in Section 5.6
 The output of the tuple generator is a tuple, (d, a, b, d1, a1, b1),
 determined as follows:
 o  A = 53591 + J*997
 o  if (A % 2 == 0) { A = A + 1 }
 o  B = 10267*(J+1)
 o  y = (B + X*A) % 2^^32
 o  v = Rand[y, 0, 2^^20]
 o  d = Deg[v]
 o  a = 1 + Rand[y, 1, W-1]
 o  b = Rand[y, 2, W]
 o  If (d < 4) { d1 = 2 + Rand[X, 3, 2] } else { d1 = 2 }
 o  a1 = 1 + Rand[X, 4, P1-1]
 o  b1 = Rand[X, 5, P1]

5.4. Example FEC Decoder

5.4.1. General

 This section describes an efficient decoding algorithm for the
 RaptorQ code introduced in this specification.  Note that each
 received encoding symbol is a known linear combination of the
 intermediate symbols.  So, each received encoding symbol provides a

Luby, et al. Standards Track [Page 30] RFC 6330 RaptorQ FEC Scheme August 2011

 linear equation among the intermediate symbols, which, together with
 the known linear pre-coding relationships amongst the intermediate
 symbols, gives a system of linear equations.  Thus, any algorithm for
 solving systems of linear equations can successfully decode the
 intermediate symbols and hence the source symbols.  However, the
 algorithm chosen has a major effect on the computational efficiency
 of the decoding.

5.4.2. Decoding an Extended Source Block

5.4.2.1. General

 It is assumed that the decoder knows the structure of the source
 block it is to decode, including the symbol size, T, and the number K
 of symbols in the source block and the number K' of source symbols in
 the extended source block.
 From the algorithms described in Section 5.3, the RaptorQ decoder can
 calculate the total number L = K'+S+H of intermediate symbols and
 determine how they were generated from the extended source block to
 be decoded.  In this description, it is assumed that the received
 encoding symbols for the extended source block to be decoded are
 passed to the decoder.  Furthermore, for each such encoding symbol,
 it is assumed that the number and set of intermediate symbols whose
 sum is equal to the encoding symbol are passed to the decoder.  In
 the case of source symbols, including padding symbols, the source
 symbol tuples described in Section 5.3.3.2 indicate the number and
 set of intermediate symbols that sum to give each source symbol.
 Let N >= K' be the number of received encoding symbols to be used for
 decoding, including padding symbols for an extended source block, and
 let M = S+H+N.  Then, with the notation of Section 5.3.3.4.2, we have
 A*C = D.
 Decoding an extended source block is equivalent to decoding C from
 known A and D.  It is clear that C can be decoded if and only if the
 rank of A is L.  Once C has been decoded, missing source symbols can
 be obtained by using the source symbol tuples to determine the number
 and set of intermediate symbols that must be summed to obtain each
 missing source symbol.
 The first step in decoding C is to form a decoding schedule.  In this
 step, A is converted using Gaussian elimination (using row operations
 and row and column reorderings) and after discarding M - L rows, into
 the L x L identity matrix.  The decoding schedule consists of the
 sequence of row operations and row and column reorderings during the
 Gaussian elimination process, and it only depends on A and not on D.

Luby, et al. Standards Track [Page 31] RFC 6330 RaptorQ FEC Scheme August 2011

 The decoding of C from D can take place concurrently with the forming
 of the decoding schedule, or the decoding can take place afterwards
 based on the decoding schedule.
 The correspondence between the decoding schedule and the decoding of
 C is as follows.  Let c[0] = 0, c[1] = 1, ..., c[L-1] = L-1 and d[0]
 = 0, d[1] = 1, ..., d[M-1] = M-1 initially.
 o  Each time a multiple, beta, of row i of A is added to row i' in
    the decoding schedule, then in the decoding process the symbol
    beta*D[d[i]] is added to symbol D[d[i']].
 o  Each time a row i of A is multiplied by an octet beta, then in the
    decoding process the symbol D[d[i]] is also multiplied by beta.
 o  Each time row i is exchanged with row i' in the decoding schedule,
    then in the decoding process the value of d[i] is exchanged with
    the value of d[i'].
 o  Each time column j is exchanged with column j' in the decoding
    schedule, then in the decoding process the value of c[j] is
    exchanged with the value of c[j'].
 From this correspondence, it is clear that the total number of
 operations on symbols in the decoding of the extended source block is
 the number of row operations (not exchanges) in the Gaussian
 elimination.  Since A is the L x L identity matrix after the Gaussian
 elimination and after discarding the last M - L rows, it is clear at
 the end of successful decoding that the L symbols D[d[0]], D[d[1]],
 ..., D[d[L-1]] are the values of the L symbols C[c[0]], C[c[1]], ...,
 C[c[L-1]].
 The order in which Gaussian elimination is performed to form the
 decoding schedule has no bearing on whether or not the decoding is
 successful.  However, the speed of the decoding depends heavily on
 the order in which Gaussian elimination is performed.  (Furthermore,
 maintaining a sparse representation of A is crucial, although this is
 not described here.)  The remainder of this section describes an
 order in which Gaussian elimination could be performed that is
 relatively efficient.

5.4.2.2. First Phase

 In the first phase of the Gaussian elimination, the matrix A is
 conceptually partitioned into submatrices and, additionally, a matrix
 X is created.  This matrix has as many rows and columns as A, and it
 will be a lower triangular matrix throughout the first phase.  At the
 beginning of this phase, the matrix A is copied into the matrix X.

Luby, et al. Standards Track [Page 32] RFC 6330 RaptorQ FEC Scheme August 2011

 The submatrix sizes are parameterized by non-negative integers i and
 u, which are initialized to 0 and P, the number of PI symbols,
 respectively.  The submatrices of A are:
 1.  The submatrix I defined by the intersection of the first i rows
     and first i columns.  This is the identity matrix at the end of
     each step in the phase.
 2.  The submatrix defined by the intersection of the first i rows and
     all but the first i columns and last u columns.  All entries of
     this submatrix are zero.
 3.  The submatrix defined by the intersection of the first i columns
     and all but the first i rows.  All entries of this submatrix are
     zero.
 4.  The submatrix U defined by the intersection of all the rows and
     the last u columns.
 5.  The submatrix V formed by the intersection of all but the first i
     columns and the last u columns and all but the first i rows.
 Figure 6 illustrates the submatrices of A.  At the beginning of the
 first phase, V consists of the first L-P columns of A, and U consists
 of the last P columns corresponding to the PI symbols.  In each step,
 a row of A is chosen.
             +-----------+-----------------+---------+
             |           |                 |         |
             |     I     |    All Zeros    |         |
             |           |                 |         |
             +-----------+-----------------+    U    |
             |           |                 |         |
             |           |                 |         |
             | All Zeros |       V         |         |
             |           |                 |         |
             |           |                 |         |
             +-----------+-----------------+---------+
             Figure 6: Submatrices of A in the First Phase
 The following graph defined by the structure of V is used in
 determining which row of A is chosen.  The columns that intersect V
 are the nodes in the graph, and the rows that have exactly 2 nonzero
 entries in V and are not HDPC rows are the edges of the graph that
 connect the two columns (nodes) in the positions of the two ones.  A
 component in this graph is a maximal set of nodes (columns) and edges

Luby, et al. Standards Track [Page 33] RFC 6330 RaptorQ FEC Scheme August 2011

 (rows) such that there is a path between each pair of nodes/edges in
 the graph.  The size of a component is the number of nodes (columns)
 in the component.
 There are at most L steps in the first phase.  The phase ends
 successfully when i + u = L, i.e., when V and the all zeros submatrix
 above V have disappeared, and A consists of I, the all zeros
 submatrix below I, and U.  The phase ends unsuccessfully in decoding
 failure if at some step before V disappears there is no nonzero row
 in V to choose in that step.  In each step, a row of A is chosen as
 follows:
 o  If all entries of V are zero, then no row is chosen and decoding
    fails.
 o  Let r be the minimum integer such that at least one row of A has
    exactly r nonzeros in V.
  • If r != 2, then choose a row with exactly r nonzeros in V with

minimum original degree among all such rows, except that HDPC

       rows should not be chosen until all non-HDPC rows have been
       processed.
  • If r = 2 and there is a row with exactly 2 ones in V, then

choose any row with exactly 2 ones in V that is part of a

       maximum size component in the graph described above that is
       defined by V.
  • If r = 2 and there is no row with exactly 2 ones in V, then

choose any row with exactly 2 nonzeros in V.

 After the row is chosen in this step, the first row of A that
 intersects V is exchanged with the chosen row so that the chosen row
 is the first row that intersects V.  The columns of A among those
 that intersect V are reordered so that one of the r nonzeros in the
 chosen row appears in the first column of V and so that the remaining
 r-1 nonzeros appear in the last columns of V.  The same row and
 column operations are also performed on the matrix X.  Then, an
 appropriate multiple of the chosen row is added to all the other rows
 of A below the chosen row that have a nonzero entry in the first
 column of V.  Specifically, if a row below the chosen row has entry
 beta in the first column of V, and the chosen row has entry alpha in
 the first column of V, then beta/alpha multiplied by the chosen row
 is added to this row to leave a zero value in the first column of V.
  Finally, i is incremented by 1 and u is incremented by r-1, which
 completes the step.

Luby, et al. Standards Track [Page 34] RFC 6330 RaptorQ FEC Scheme August 2011

 Note that efficiency can be improved if the row operations identified
 above are not actually performed until the affected row is itself
 chosen during the decoding process.  This avoids processing of row
 operations for rows that are not eventually used in the decoding
 process, and in particular this avoids those rows for which beta!=1
 until they are actually required.  Furthermore, the row operations
 required for the HDPC rows may be performed for all such rows in one
 process, by using the algorithm described in Section 5.3.3.3.

5.4.2.3. Second Phase

 At this point, all the entries of X outside the first i rows and i
 columns are discarded, so that X has lower triangular form.  The last
 i rows and columns of X are discarded, so that X now has i rows and i
 columns.  The submatrix U is further partitioned into the first i
 rows, U_upper, and the remaining M - i rows, U_lower.  Gaussian
 elimination is performed in the second phase on U_lower either to
 determine that its rank is less than u (decoding failure) or to
 convert it into a matrix where the first u rows is the identity
 matrix (success of the second phase).  Call this u x u identity
 matrix I_u.  The M - L rows of A that intersect U_lower - I_u are
 discarded.  After this phase, A has L rows and L columns.

5.4.2.4. Third Phase

 After the second phase, the only portion of A that needs to be zeroed
 out to finish converting A into the L x L identity matrix is U_upper.
 The number of rows i of the submatrix U_upper is generally much
 larger than the number of columns u of U_upper.  Moreover, at this
 time, the matrix U_upper is typically dense, i.e., the number of
 nonzero entries of this matrix is large.  To reduce this matrix to a
 sparse form, the sequence of operations performed to obtain the
 matrix U_lower needs to be inverted.  To this end, the matrix X is
 multiplied with the submatrix of A consisting of the first i rows of
 A.  After this operation, the submatrix of A consisting of the
 intersection of the first i rows and columns equals to X, whereas the
 matrix U_upper is transformed to a sparse form.

5.4.2.5. Fourth Phase

 For each of the first i rows of U_upper, do the following: if the row
 has a nonzero entry at position j, and if the value of that nonzero
 entry is b, then add to this row b times row j of I_u.  After this
 step, the submatrix of A consisting of the intersection of the first
 i rows and columns is equal to X, the submatrix U_upper consists of
 zeros, the submatrix consisting of the intersection of the last u
 rows and the first i columns consists of zeros, and the submatrix
 consisting of the last u rows and columns is the matrix I_u.

Luby, et al. Standards Track [Page 35] RFC 6330 RaptorQ FEC Scheme August 2011

5.4.2.6. Fifth Phase

 For j from 1 to i, perform the following operations:
 1.  If A[j,j] is not one, then divide row j of A by A[j,j].
 2.  For l from 1 to j-1, if A[j,l] is nonzero, then add A[j,l]
     multiplied with row l of A to row j of A.
 After this phase, A is the L x L identity matrix and a complete
 decoding schedule has been successfully formed.  Then, the
 corresponding decoding consisting of summing known encoding symbols
 can be executed to recover the intermediate symbols based on the
 decoding schedule.  The tuples associated with all source symbols are
 computed according to Section 5.3.3.2.  The tuples for received
 source symbols are used in the decoding.  The tuples for missing
 source symbols are used to determine which intermediate symbols need
 to be summed to recover the missing source symbols.

5.5. Random Numbers

 The four arrays V0, V1, V2, and V3 used in Section 5.3.5.1 are
 provided below.  There are 256 entries in each of the four arrays.
 The indexing into each array starts at 0, and the entries are 32-bit
 unsigned integers.

5.5.1. The Table V0

    251291136, 3952231631, 3370958628, 4070167936, 123631495,
    3351110283, 3218676425, 2011642291, 774603218, 2402805061,
    1004366930, 1843948209, 428891132, 3746331984, 1591258008,
    3067016507, 1433388735, 504005498, 2032657933, 3419319784,
    2805686246, 3102436986, 3808671154, 2501582075, 3978944421,
    246043949, 4016898363, 649743608, 1974987508, 2651273766,
    2357956801, 689605112, 715807172, 2722736134, 191939188,
    3535520147, 3277019569, 1470435941, 3763101702, 3232409631,
    122701163, 3920852693, 782246947, 372121310, 2995604341,
    2045698575, 2332962102, 4005368743, 218596347, 3415381967,
    4207612806, 861117671, 3676575285, 2581671944, 3312220480,
    681232419, 307306866, 4112503940, 1158111502, 709227802,
    2724140433, 4201101115, 4215970289, 4048876515, 3031661061,
    1909085522, 510985033, 1361682810, 129243379, 3142379587,
    2569842483, 3033268270, 1658118006, 932109358, 1982290045,
    2983082771, 3007670818, 3448104768, 683749698, 778296777,
    1399125101, 1939403708, 1692176003, 3868299200, 1422476658,
    593093658, 1878973865, 2526292949, 1591602827, 3986158854,
    3964389521, 2695031039, 1942050155, 424618399, 1347204291,
    2669179716, 2434425874, 2540801947, 1384069776, 4123580443,

Luby, et al. Standards Track [Page 36] RFC 6330 RaptorQ FEC Scheme August 2011

    1523670218, 2708475297, 1046771089, 2229796016, 1255426612,
    4213663089, 1521339547, 3041843489, 420130494, 10677091,
    515623176, 3457502702, 2115821274, 2720124766, 3242576090,
    854310108, 425973987, 325832382, 1796851292, 2462744411,
    1976681690, 1408671665, 1228817808, 3917210003, 263976645,
    2593736473, 2471651269, 4291353919, 650792940, 1191583883,
    3046561335, 2466530435, 2545983082, 969168436, 2019348792,
    2268075521, 1169345068, 3250240009, 3963499681, 2560755113,
    911182396, 760842409, 3569308693, 2687243553, 381854665,
    2613828404, 2761078866, 1456668111, 883760091, 3294951678,
    1604598575, 1985308198, 1014570543, 2724959607, 3062518035,
    3115293053, 138853680, 4160398285, 3322241130, 2068983570,
    2247491078, 3669524410, 1575146607, 828029864, 3732001371,
    3422026452, 3370954177, 4006626915, 543812220, 1243116171,
    3928372514, 2791443445, 4081325272, 2280435605, 885616073,
    616452097, 3188863436, 2780382310, 2340014831, 1208439576,
    258356309, 3837963200, 2075009450, 3214181212, 3303882142,
    880813252, 1355575717, 207231484, 2420803184, 358923368,
    1617557768, 3272161958, 1771154147, 2842106362, 1751209208,
    1421030790, 658316681, 194065839, 3241510581, 38625260,
    301875395, 4176141739, 297312930, 2137802113, 1502984205,
    3669376622, 3728477036, 234652930, 2213589897, 2734638932,
    1129721478, 3187422815, 2859178611, 3284308411, 3819792700,
    3557526733, 451874476, 1740576081, 3592838701, 1709429513,
    3702918379, 3533351328, 1641660745, 179350258, 2380520112,
    3936163904, 3685256204, 3156252216, 1854258901, 2861641019,
    3176611298, 834787554, 331353807, 517858103, 3010168884,
    4012642001, 2217188075, 3756943137, 3077882590, 2054995199,
    3081443129, 3895398812, 1141097543, 2376261053, 2626898255,
    2554703076, 401233789, 1460049922, 678083952, 1064990737,
    940909784, 1673396780, 528881783, 1712547446, 3629685652,
    1358307511

5.5.2. The Table V1

    807385413, 2043073223, 3336749796, 1302105833, 2278607931,
    541015020, 1684564270, 372709334, 3508252125, 1768346005,
    1270451292, 2603029534, 2049387273, 3891424859, 2152948345,
    4114760273, 915180310, 3754787998, 700503826, 2131559305,
    1308908630, 224437350, 4065424007, 3638665944, 1679385496,
    3431345226, 1779595665, 3068494238, 1424062773, 1033448464,
    4050396853, 3302235057, 420600373, 2868446243, 311689386,
    259047959, 4057180909, 1575367248, 4151214153, 110249784,
    3006865921, 4293710613, 3501256572, 998007483, 499288295,
    1205710710, 2997199489, 640417429, 3044194711, 486690751,
    2686640734, 2394526209, 2521660077, 49993987, 3843885867,
    4201106668, 415906198, 19296841, 2402488407, 2137119134,
    1744097284, 579965637, 2037662632, 852173610, 2681403713,

Luby, et al. Standards Track [Page 37] RFC 6330 RaptorQ FEC Scheme August 2011

    1047144830, 2982173936, 910285038, 4187576520, 2589870048,
    989448887, 3292758024, 506322719, 176010738, 1865471968,
    2619324712, 564829442, 1996870325, 339697593, 4071072948,
    3618966336, 2111320126, 1093955153, 957978696, 892010560,
    1854601078, 1873407527, 2498544695, 2694156259, 1927339682,
    1650555729, 183933047, 3061444337, 2067387204, 228962564,
    3904109414, 1595995433, 1780701372, 2463145963, 307281463,
    3237929991, 3852995239, 2398693510, 3754138664, 522074127,
    146352474, 4104915256, 3029415884, 3545667983, 332038910,
    976628269, 3123492423, 3041418372, 2258059298, 2139377204,
    3243642973, 3226247917, 3674004636, 2698992189, 3453843574,
    1963216666, 3509855005, 2358481858, 747331248, 1957348676,
    1097574450, 2435697214, 3870972145, 1888833893, 2914085525,
    4161315584, 1273113343, 3269644828, 3681293816, 412536684,
    1156034077, 3823026442, 1066971017, 3598330293, 1979273937,
    2079029895, 1195045909, 1071986421, 2712821515, 3377754595,
    2184151095, 750918864, 2585729879, 4249895712, 1832579367,
    1192240192, 946734366, 31230688, 3174399083, 3549375728,
    1642430184, 1904857554, 861877404, 3277825584, 4267074718,
    3122860549, 666423581, 644189126, 226475395, 307789415,
    1196105631, 3191691839, 782852669, 1608507813, 1847685900,
    4069766876, 3931548641, 2526471011, 766865139, 2115084288,
    4259411376, 3323683436, 568512177, 3736601419, 1800276898,
    4012458395, 1823982, 27980198, 2023839966, 869505096,
    431161506, 1024804023, 1853869307, 3393537983, 1500703614,
    3019471560, 1351086955, 3096933631, 3034634988, 2544598006,
    1230942551, 3362230798, 159984793, 491590373, 3993872886,
    3681855622, 903593547, 3535062472, 1799803217, 772984149,
    895863112, 1899036275, 4187322100, 101856048, 234650315,
    3183125617, 3190039692, 525584357, 1286834489, 455810374,
    1869181575, 922673938, 3877430102, 3422391938, 1414347295,
    1971054608, 3061798054, 830555096, 2822905141, 167033190,
    1079139428, 4210126723, 3593797804, 429192890, 372093950,
    1779187770, 3312189287, 204349348, 452421568, 2800540462,
    3733109044, 1235082423, 1765319556, 3174729780, 3762994475,
    3171962488, 442160826, 198349622, 45942637, 1324086311,
    2901868599, 678860040, 3812229107, 19936821, 1119590141,
    3640121682, 3545931032, 2102949142, 2828208598, 3603378023,
    4135048896

5.5.3. The Table V2

    1629829892, 282540176, 2794583710, 496504798, 2990494426,
    3070701851, 2575963183, 4094823972, 2775723650, 4079480416,
    176028725, 2246241423, 3732217647, 2196843075, 1306949278,
    4170992780, 4039345809, 3209664269, 3387499533, 293063229,
    3660290503, 2648440860, 2531406539, 3537879412, 773374739,
    4184691853, 1804207821, 3347126643, 3479377103, 3970515774,

Luby, et al. Standards Track [Page 38] RFC 6330 RaptorQ FEC Scheme August 2011

    1891731298, 2368003842, 3537588307, 2969158410, 4230745262,
    831906319, 2935838131, 264029468, 120852739, 3200326460,
    355445271, 2296305141, 1566296040, 1760127056, 20073893,
    3427103620, 2866979760, 2359075957, 2025314291, 1725696734,
    3346087406, 2690756527, 99815156, 4248519977, 2253762642,
    3274144518, 598024568, 3299672435, 556579346, 4121041856,
    2896948975, 3620123492, 918453629, 3249461198, 2231414958,
    3803272287, 3657597946, 2588911389, 242262274, 1725007475,
    2026427718, 46776484, 2873281403, 2919275846, 3177933051,
    1918859160, 2517854537, 1857818511, 3234262050, 479353687,
    200201308, 2801945841, 1621715769, 483977159, 423502325,
    3689396064, 1850168397, 3359959416, 3459831930, 841488699,
    3570506095, 930267420, 1564520841, 2505122797, 593824107,
    1116572080, 819179184, 3139123629, 1414339336, 1076360795,
    512403845, 177759256, 1701060666, 2239736419, 515179302,
    2935012727, 3821357612, 1376520851, 2700745271, 966853647,
    1041862223, 715860553, 171592961, 1607044257, 1227236688,
    3647136358, 1417559141, 4087067551, 2241705880, 4194136288,
    1439041934, 20464430, 119668151, 2021257232, 2551262694,
    1381539058, 4082839035, 498179069, 311508499, 3580908637,
    2889149671, 142719814, 1232184754, 3356662582, 2973775623,
    1469897084, 1728205304, 1415793613, 50111003, 3133413359,
    4074115275, 2710540611, 2700083070, 2457757663, 2612845330,
    3775943755, 2469309260, 2560142753, 3020996369, 1691667711,
    4219602776, 1687672168, 1017921622, 2307642321, 368711460,
    3282925988, 213208029, 4150757489, 3443211944, 2846101972,
    4106826684, 4272438675, 2199416468, 3710621281, 497564971,
    285138276, 765042313, 916220877, 3402623607, 2768784621,
    1722849097, 3386397442, 487920061, 3569027007, 3424544196,
    217781973, 2356938519, 3252429414, 145109750, 2692588106,
    2454747135, 1299493354, 4120241887, 2088917094, 932304329,
    1442609203, 952586974, 3509186750, 753369054, 854421006,
    1954046388, 2708927882, 4047539230, 3048925996, 1667505809,
    805166441, 1182069088, 4265546268, 4215029527, 3374748959,
    373532666, 2454243090, 2371530493, 3651087521, 2619878153,
    1651809518, 1553646893, 1227452842, 703887512, 3696674163,
    2552507603, 2635912901, 895130484, 3287782244, 3098973502,
    990078774, 3780326506, 2290845203, 41729428, 1949580860,
    2283959805, 1036946170, 1694887523, 4880696, 466000198,
    2765355283, 3318686998, 1266458025, 3919578154, 3545413527,
    2627009988, 3744680394, 1696890173, 3250684705, 4142417708,
    915739411, 3308488877, 1289361460, 2942552331, 1169105979,
    3342228712, 698560958, 1356041230, 2401944293, 107705232,
    3701895363, 903928723, 3646581385, 844950914, 1944371367,
    3863894844, 2946773319, 1972431613, 1706989237, 29917467,
    3497665928

Luby, et al. Standards Track [Page 39] RFC 6330 RaptorQ FEC Scheme August 2011

5.5.4. The Table V3

    1191369816, 744902811, 2539772235, 3213192037, 3286061266,
    1200571165, 2463281260, 754888894, 714651270, 1968220972,
    3628497775, 1277626456, 1493398934, 364289757, 2055487592,
    3913468088, 2930259465, 902504567, 3967050355, 2056499403,
    692132390, 186386657, 832834706, 859795816, 1283120926,
    2253183716, 3003475205, 1755803552, 2239315142, 4271056352,
    2184848469, 769228092, 1249230754, 1193269205, 2660094102,
    642979613, 1687087994, 2726106182, 446402913, 4122186606,
    3771347282, 37667136, 192775425, 3578702187, 1952659096,
    3989584400, 3069013882, 2900516158, 4045316336, 3057163251,
    1702104819, 4116613420, 3575472384, 2674023117, 1409126723,
    3215095429, 1430726429, 2544497368, 1029565676, 1855801827,
    4262184627, 1854326881, 2906728593, 3277836557, 2787697002,
    2787333385, 3105430738, 2477073192, 748038573, 1088396515,
    1611204853, 201964005, 3745818380, 3654683549, 3816120877,
    3915783622, 2563198722, 1181149055, 33158084, 3723047845,
    3790270906, 3832415204, 2959617497, 372900708, 1286738499,
    1932439099, 3677748309, 2454711182, 2757856469, 2134027055,
    2780052465, 3190347618, 3758510138, 3626329451, 1120743107,
    1623585693, 1389834102, 2719230375, 3038609003, 462617590,
    260254189, 3706349764, 2556762744, 2874272296, 2502399286,
    4216263978, 2683431180, 2168560535, 3561507175, 668095726,
    680412330, 3726693946, 4180630637, 3335170953, 942140968,
    2711851085, 2059233412, 4265696278, 3204373534, 232855056,
    881788313, 2258252172, 2043595984, 3758795150, 3615341325,
    2138837681, 1351208537, 2923692473, 3402482785, 2105383425,
    2346772751, 499245323, 3417846006, 2366116814, 2543090583,
    1828551634, 3148696244, 3853884867, 1364737681, 2200687771,
    2689775688, 232720625, 4071657318, 2671968983, 3531415031,
    1212852141, 867923311, 3740109711, 1923146533, 3237071777,
    3100729255, 3247856816, 906742566, 4047640575, 4007211572,
    3495700105, 1171285262, 2835682655, 1634301229, 3115169925,
    2289874706, 2252450179, 944880097, 371933491, 1649074501,
    2208617414, 2524305981, 2496569844, 2667037160, 1257550794,
    3399219045, 3194894295, 1643249887, 342911473, 891025733,
    3146861835, 3789181526, 938847812, 1854580183, 2112653794,
    2960702988, 1238603378, 2205280635, 1666784014, 2520274614,
    3355493726, 2310872278, 3153920489, 2745882591, 1200203158,
    3033612415, 2311650167, 1048129133, 4206710184, 4209176741,
    2640950279, 2096382177, 4116899089, 3631017851, 4104488173,
    1857650503, 3801102932, 445806934, 3055654640, 897898279,
    3234007399, 1325494930, 2982247189, 1619020475, 2720040856,
    885096170, 3485255499, 2983202469, 3891011124, 546522756,
    1524439205, 2644317889, 2170076800, 2969618716, 961183518,
    1081831074, 1037015347, 3289016286, 2331748669, 620887395,
    303042654, 3990027945, 1562756376, 3413341792, 2059647769,

Luby, et al. Standards Track [Page 40] RFC 6330 RaptorQ FEC Scheme August 2011

    2823844432, 674595301, 2457639984, 4076754716, 2447737904,
    1583323324, 625627134, 3076006391, 345777990, 1684954145,
    879227329, 3436182180, 1522273219, 3802543817, 1456017040,
    1897819847, 2970081129, 1382576028, 3820044861, 1044428167,
    612252599, 3340478395, 2150613904, 3397625662, 3573635640,
    3432275192

5.6. Systematic Indices and Other Parameters

 Table 2 below specifies the supported values of K'.  The table also
 specifies for each supported value of K' the systematic index J(K'),
 the number H(K') of HDPC symbols, the number S(K') of LDPC symbols,
 and the number W(K') of LT symbols.  For each value of K', the
 corresponding values of S(K') and W(K') are prime numbers.
 The systematic index J(K') is designed to have the property that the
 set of source symbol tuples (d[0], a[0], b[0], d1[0], a1[0], b1[0]),
 ..., (d[K'-1], a[K'-1], b[K'-1], d1[K'-1], a1[K'-1], b1[K'-1]) are
 such that the L intermediate symbols are uniquely defined, i.e., the
 matrix A in Figure 6 has full rank and is therefore invertible.
               +-------+-------+-------+-------+-------+
               | K'    | J(K') | S(K') | H(K') | W(K') |
               +-------+-------+-------+-------+-------+
               | 10    | 254   | 7     | 10    | 17    |
               +-------+-------+-------+-------+-------+
               | 12    | 630   | 7     | 10    | 19    |
               +-------+-------+-------+-------+-------+
               | 18    | 682   | 11    | 10    | 29    |
               +-------+-------+-------+-------+-------+
               | 20    | 293   | 11    | 10    | 31    |
               +-------+-------+-------+-------+-------+
               | 26    | 80    | 11    | 10    | 37    |
               +-------+-------+-------+-------+-------+
               | 30    | 566   | 11    | 10    | 41    |
               +-------+-------+-------+-------+-------+
               | 32    | 860   | 11    | 10    | 43    |
               +-------+-------+-------+-------+-------+
               | 36    | 267   | 11    | 10    | 47    |
               +-------+-------+-------+-------+-------+
               | 42    | 822   | 11    | 10    | 53    |
               +-------+-------+-------+-------+-------+
               | 46    | 506   | 13    | 10    | 59    |
               +-------+-------+-------+-------+-------+
               | 48    | 589   | 13    | 10    | 61    |
               +-------+-------+-------+-------+-------+
               | 49    | 87    | 13    | 10    | 61    |
               +-------+-------+-------+-------+-------+

Luby, et al. Standards Track [Page 41] RFC 6330 RaptorQ FEC Scheme August 2011

               +-------+-------+-------+-------+-------+
               | 55    | 520   | 13    | 10    | 67    |
               +-------+-------+-------+-------+-------+
               | 60    | 159   | 13    | 10    | 71    |
               +-------+-------+-------+-------+-------+
               | 62    | 235   | 13    | 10    | 73    |
               +-------+-------+-------+-------+-------+
               | 69    | 157   | 13    | 10    | 79    |
               +-------+-------+-------+-------+-------+
               | 75    | 502   | 17    | 10    | 89    |
               +-------+-------+-------+-------+-------+
               | 84    | 334   | 17    | 10    | 97    |
               +-------+-------+-------+-------+-------+
               | 88    | 583   | 17    | 10    | 101   |
               +-------+-------+-------+-------+-------+
               | 91    | 66    | 17    | 10    | 103   |
               +-------+-------+-------+-------+-------+
               | 95    | 352   | 17    | 10    | 107   |
               +-------+-------+-------+-------+-------+
               | 97    | 365   | 17    | 10    | 109   |
               +-------+-------+-------+-------+-------+
               | 101   | 562   | 17    | 10    | 113   |
               +-------+-------+-------+-------+-------+
               | 114   | 5     | 19    | 10    | 127   |
               +-------+-------+-------+-------+-------+
               | 119   | 603   | 19    | 10    | 131   |
               +-------+-------+-------+-------+-------+
               | 125   | 721   | 19    | 10    | 137   |
               +-------+-------+-------+-------+-------+
               | 127   | 28    | 19    | 10    | 139   |
               +-------+-------+-------+-------+-------+
               | 138   | 660   | 19    | 10    | 149   |
               +-------+-------+-------+-------+-------+
               | 140   | 829   | 19    | 10    | 151   |
               +-------+-------+-------+-------+-------+
               | 149   | 900   | 23    | 10    | 163   |
               +-------+-------+-------+-------+-------+
               | 153   | 930   | 23    | 10    | 167   |
               +-------+-------+-------+-------+-------+
               | 160   | 814   | 23    | 10    | 173   |
               +-------+-------+-------+-------+-------+
               | 166   | 661   | 23    | 10    | 179   |
               +-------+-------+-------+-------+-------+
               | 168   | 693   | 23    | 10    | 181   |
               +-------+-------+-------+-------+-------+
               | 179   | 780   | 23    | 10    | 191   |
               +-------+-------+-------+-------+-------+

Luby, et al. Standards Track [Page 42] RFC 6330 RaptorQ FEC Scheme August 2011

               +-------+-------+-------+-------+-------+
               | 181   | 605   | 23    | 10    | 193   |
               +-------+-------+-------+-------+-------+
               | 185   | 551   | 23    | 10    | 197   |
               +-------+-------+-------+-------+-------+
               | 187   | 777   | 23    | 10    | 199   |
               +-------+-------+-------+-------+-------+
               | 200   | 491   | 23    | 10    | 211   |
               +-------+-------+-------+-------+-------+
               | 213   | 396   | 23    | 10    | 223   |
               +-------+-------+-------+-------+-------+
               | 217   | 764   | 29    | 10    | 233   |
               +-------+-------+-------+-------+-------+
               | 225   | 843   | 29    | 10    | 241   |
               +-------+-------+-------+-------+-------+
               | 236   | 646   | 29    | 10    | 251   |
               +-------+-------+-------+-------+-------+
               | 242   | 557   | 29    | 10    | 257   |
               +-------+-------+-------+-------+-------+
               | 248   | 608   | 29    | 10    | 263   |
               +-------+-------+-------+-------+-------+
               | 257   | 265   | 29    | 10    | 271   |
               +-------+-------+-------+-------+-------+
               | 263   | 505   | 29    | 10    | 277   |
               +-------+-------+-------+-------+-------+
               | 269   | 722   | 29    | 10    | 283   |
               +-------+-------+-------+-------+-------+
               | 280   | 263   | 29    | 10    | 293   |
               +-------+-------+-------+-------+-------+
               | 295   | 999   | 29    | 10    | 307   |
               +-------+-------+-------+-------+-------+
               | 301   | 874   | 29    | 10    | 313   |
               +-------+-------+-------+-------+-------+
               | 305   | 160   | 29    | 10    | 317   |
               +-------+-------+-------+-------+-------+
               | 324   | 575   | 31    | 10    | 337   |
               +-------+-------+-------+-------+-------+
               | 337   | 210   | 31    | 10    | 349   |
               +-------+-------+-------+-------+-------+
               | 341   | 513   | 31    | 10    | 353   |
               +-------+-------+-------+-------+-------+
               | 347   | 503   | 31    | 10    | 359   |
               +-------+-------+-------+-------+-------+
               | 355   | 558   | 31    | 10    | 367   |
               +-------+-------+-------+-------+-------+
               | 362   | 932   | 31    | 10    | 373   |
               +-------+-------+-------+-------+-------+

Luby, et al. Standards Track [Page 43] RFC 6330 RaptorQ FEC Scheme August 2011

               +-------+-------+-------+-------+-------+
               | 368   | 404   | 31    | 10    | 379   |
               +-------+-------+-------+-------+-------+
               | 372   | 520   | 37    | 10    | 389   |
               +-------+-------+-------+-------+-------+
               | 380   | 846   | 37    | 10    | 397   |
               +-------+-------+-------+-------+-------+
               | 385   | 485   | 37    | 10    | 401   |
               +-------+-------+-------+-------+-------+
               | 393   | 728   | 37    | 10    | 409   |
               +-------+-------+-------+-------+-------+
               | 405   | 554   | 37    | 10    | 421   |
               +-------+-------+-------+-------+-------+
               | 418   | 471   | 37    | 10    | 433   |
               +-------+-------+-------+-------+-------+
               | 428   | 641   | 37    | 10    | 443   |
               +-------+-------+-------+-------+-------+
               | 434   | 732   | 37    | 10    | 449   |
               +-------+-------+-------+-------+-------+
               | 447   | 193   | 37    | 10    | 461   |
               +-------+-------+-------+-------+-------+
               | 453   | 934   | 37    | 10    | 467   |
               +-------+-------+-------+-------+-------+
               | 466   | 864   | 37    | 10    | 479   |
               +-------+-------+-------+-------+-------+
               | 478   | 790   | 37    | 10    | 491   |
               +-------+-------+-------+-------+-------+
               | 486   | 912   | 37    | 10    | 499   |
               +-------+-------+-------+-------+-------+
               | 491   | 617   | 37    | 10    | 503   |
               +-------+-------+-------+-------+-------+
               | 497   | 587   | 37    | 10    | 509   |
               +-------+-------+-------+-------+-------+
               | 511   | 800   | 37    | 10    | 523   |
               +-------+-------+-------+-------+-------+
               | 526   | 923   | 41    | 10    | 541   |
               +-------+-------+-------+-------+-------+
               | 532   | 998   | 41    | 10    | 547   |
               +-------+-------+-------+-------+-------+
               | 542   | 92    | 41    | 10    | 557   |
               +-------+-------+-------+-------+-------+
               | 549   | 497   | 41    | 10    | 563   |
               +-------+-------+-------+-------+-------+
               | 557   | 559   | 41    | 10    | 571   |
               +-------+-------+-------+-------+-------+
               | 563   | 667   | 41    | 10    | 577   |
               +-------+-------+-------+-------+-------+

Luby, et al. Standards Track [Page 44] RFC 6330 RaptorQ FEC Scheme August 2011

               +-------+-------+-------+-------+-------+
               | 573   | 912   | 41    | 10    | 587   |
               +-------+-------+-------+-------+-------+
               | 580   | 262   | 41    | 10    | 593   |
               +-------+-------+-------+-------+-------+
               | 588   | 152   | 41    | 10    | 601   |
               +-------+-------+-------+-------+-------+
               | 594   | 526   | 41    | 10    | 607   |
               +-------+-------+-------+-------+-------+
               | 600   | 268   | 41    | 10    | 613   |
               +-------+-------+-------+-------+-------+
               | 606   | 212   | 41    | 10    | 619   |
               +-------+-------+-------+-------+-------+
               | 619   | 45    | 41    | 10    | 631   |
               +-------+-------+-------+-------+-------+
               | 633   | 898   | 43    | 10    | 647   |
               +-------+-------+-------+-------+-------+
               | 640   | 527   | 43    | 10    | 653   |
               +-------+-------+-------+-------+-------+
               | 648   | 558   | 43    | 10    | 661   |
               +-------+-------+-------+-------+-------+
               | 666   | 460   | 47    | 10    | 683   |
               +-------+-------+-------+-------+-------+
               | 675   | 5     | 47    | 10    | 691   |
               +-------+-------+-------+-------+-------+
               | 685   | 895   | 47    | 10    | 701   |
               +-------+-------+-------+-------+-------+
               | 693   | 996   | 47    | 10    | 709   |
               +-------+-------+-------+-------+-------+
               | 703   | 282   | 47    | 10    | 719   |
               +-------+-------+-------+-------+-------+
               | 718   | 513   | 47    | 10    | 733   |
               +-------+-------+-------+-------+-------+
               | 728   | 865   | 47    | 10    | 743   |
               +-------+-------+-------+-------+-------+
               | 736   | 870   | 47    | 10    | 751   |
               +-------+-------+-------+-------+-------+
               | 747   | 239   | 47    | 10    | 761   |
               +-------+-------+-------+-------+-------+
               | 759   | 452   | 47    | 10    | 773   |
               +-------+-------+-------+-------+-------+
               | 778   | 862   | 53    | 10    | 797   |
               +-------+-------+-------+-------+-------+
               | 792   | 852   | 53    | 10    | 811   |
               +-------+-------+-------+-------+-------+
               | 802   | 643   | 53    | 10    | 821   |
               +-------+-------+-------+-------+-------+

Luby, et al. Standards Track [Page 45] RFC 6330 RaptorQ FEC Scheme August 2011

               +-------+-------+-------+-------+-------+
               | 811   | 543   | 53    | 10    | 829   |
               +-------+-------+-------+-------+-------+
               | 821   | 447   | 53    | 10    | 839   |
               +-------+-------+-------+-------+-------+
               | 835   | 321   | 53    | 10    | 853   |
               +-------+-------+-------+-------+-------+
               | 845   | 287   | 53    | 10    | 863   |
               +-------+-------+-------+-------+-------+
               | 860   | 12    | 53    | 10    | 877   |
               +-------+-------+-------+-------+-------+
               | 870   | 251   | 53    | 10    | 887   |
               +-------+-------+-------+-------+-------+
               | 891   | 30    | 53    | 10    | 907   |
               +-------+-------+-------+-------+-------+
               | 903   | 621   | 53    | 10    | 919   |
               +-------+-------+-------+-------+-------+
               | 913   | 555   | 53    | 10    | 929   |
               +-------+-------+-------+-------+-------+
               | 926   | 127   | 53    | 10    | 941   |
               +-------+-------+-------+-------+-------+
               | 938   | 400   | 53    | 10    | 953   |
               +-------+-------+-------+-------+-------+
               | 950   | 91    | 59    | 10    | 971   |
               +-------+-------+-------+-------+-------+
               | 963   | 916   | 59    | 10    | 983   |
               +-------+-------+-------+-------+-------+
               | 977   | 935   | 59    | 10    | 997   |
               +-------+-------+-------+-------+-------+
               | 989   | 691   | 59    | 10    | 1009  |
               +-------+-------+-------+-------+-------+
               | 1002  | 299   | 59    | 10    | 1021  |
               +-------+-------+-------+-------+-------+
               | 1020  | 282   | 59    | 10    | 1039  |
               +-------+-------+-------+-------+-------+
               | 1032  | 824   | 59    | 10    | 1051  |
               +-------+-------+-------+-------+-------+
               | 1050  | 536   | 59    | 11    | 1069  |
               +-------+-------+-------+-------+-------+
               | 1074  | 596   | 59    | 11    | 1093  |
               +-------+-------+-------+-------+-------+
               | 1085  | 28    | 59    | 11    | 1103  |
               +-------+-------+-------+-------+-------+
               | 1099  | 947   | 59    | 11    | 1117  |
               +-------+-------+-------+-------+-------+
               | 1111  | 162   | 59    | 11    | 1129  |
               +-------+-------+-------+-------+-------+

Luby, et al. Standards Track [Page 46] RFC 6330 RaptorQ FEC Scheme August 2011

               +-------+-------+-------+-------+-------+
               | 1136  | 536   | 59    | 11    | 1153  |
               +-------+-------+-------+-------+-------+
               | 1152  | 1000  | 61    | 11    | 1171  |
               +-------+-------+-------+-------+-------+
               | 1169  | 251   | 61    | 11    | 1187  |
               +-------+-------+-------+-------+-------+
               | 1183  | 673   | 61    | 11    | 1201  |
               +-------+-------+-------+-------+-------+
               | 1205  | 559   | 61    | 11    | 1223  |
               +-------+-------+-------+-------+-------+
               | 1220  | 923   | 61    | 11    | 1237  |
               +-------+-------+-------+-------+-------+
               | 1236  | 81    | 67    | 11    | 1259  |
               +-------+-------+-------+-------+-------+
               | 1255  | 478   | 67    | 11    | 1277  |
               +-------+-------+-------+-------+-------+
               | 1269  | 198   | 67    | 11    | 1291  |
               +-------+-------+-------+-------+-------+
               | 1285  | 137   | 67    | 11    | 1307  |
               +-------+-------+-------+-------+-------+
               | 1306  | 75    | 67    | 11    | 1327  |
               +-------+-------+-------+-------+-------+
               | 1347  | 29    | 67    | 11    | 1367  |
               +-------+-------+-------+-------+-------+
               | 1361  | 231   | 67    | 11    | 1381  |
               +-------+-------+-------+-------+-------+
               | 1389  | 532   | 67    | 11    | 1409  |
               +-------+-------+-------+-------+-------+
               | 1404  | 58    | 67    | 11    | 1423  |
               +-------+-------+-------+-------+-------+
               | 1420  | 60    | 67    | 11    | 1439  |
               +-------+-------+-------+-------+-------+
               | 1436  | 964   | 71    | 11    | 1459  |
               +-------+-------+-------+-------+-------+
               | 1461  | 624   | 71    | 11    | 1483  |
               +-------+-------+-------+-------+-------+
               | 1477  | 502   | 71    | 11    | 1499  |
               +-------+-------+-------+-------+-------+
               | 1502  | 636   | 71    | 11    | 1523  |
               +-------+-------+-------+-------+-------+
               | 1522  | 986   | 71    | 11    | 1543  |
               +-------+-------+-------+-------+-------+
               | 1539  | 950   | 71    | 11    | 1559  |
               +-------+-------+-------+-------+-------+
               | 1561  | 735   | 73    | 11    | 1583  |
               +-------+-------+-------+-------+-------+

Luby, et al. Standards Track [Page 47] RFC 6330 RaptorQ FEC Scheme August 2011

               +-------+-------+-------+-------+-------+
               | 1579  | 866   | 73    | 11    | 1601  |
               +-------+-------+-------+-------+-------+
               | 1600  | 203   | 73    | 11    | 1621  |
               +-------+-------+-------+-------+-------+
               | 1616  | 83    | 73    | 11    | 1637  |
               +-------+-------+-------+-------+-------+
               | 1649  | 14    | 73    | 11    | 1669  |
               +-------+-------+-------+-------+-------+
               | 1673  | 522   | 79    | 11    | 1699  |
               +-------+-------+-------+-------+-------+
               | 1698  | 226   | 79    | 11    | 1723  |
               +-------+-------+-------+-------+-------+
               | 1716  | 282   | 79    | 11    | 1741  |
               +-------+-------+-------+-------+-------+
               | 1734  | 88    | 79    | 11    | 1759  |
               +-------+-------+-------+-------+-------+
               | 1759  | 636   | 79    | 11    | 1783  |
               +-------+-------+-------+-------+-------+
               | 1777  | 860   | 79    | 11    | 1801  |
               +-------+-------+-------+-------+-------+
               | 1800  | 324   | 79    | 11    | 1823  |
               +-------+-------+-------+-------+-------+
               | 1824  | 424   | 79    | 11    | 1847  |
               +-------+-------+-------+-------+-------+
               | 1844  | 999   | 79    | 11    | 1867  |
               +-------+-------+-------+-------+-------+
               | 1863  | 682   | 83    | 11    | 1889  |
               +-------+-------+-------+-------+-------+
               | 1887  | 814   | 83    | 11    | 1913  |
               +-------+-------+-------+-------+-------+
               | 1906  | 979   | 83    | 11    | 1931  |
               +-------+-------+-------+-------+-------+
               | 1926  | 538   | 83    | 11    | 1951  |
               +-------+-------+-------+-------+-------+
               | 1954  | 278   | 83    | 11    | 1979  |
               +-------+-------+-------+-------+-------+
               | 1979  | 580   | 83    | 11    | 2003  |
               +-------+-------+-------+-------+-------+
               | 2005  | 773   | 83    | 11    | 2029  |
               +-------+-------+-------+-------+-------+
               | 2040  | 911   | 89    | 11    | 2069  |
               +-------+-------+-------+-------+-------+
               | 2070  | 506   | 89    | 11    | 2099  |
               +-------+-------+-------+-------+-------+
               | 2103  | 628   | 89    | 11    | 2131  |
               +-------+-------+-------+-------+-------+

Luby, et al. Standards Track [Page 48] RFC 6330 RaptorQ FEC Scheme August 2011

               +-------+-------+-------+-------+-------+
               | 2125  | 282   | 89    | 11    | 2153  |
               +-------+-------+-------+-------+-------+
               | 2152  | 309   | 89    | 11    | 2179  |
               +-------+-------+-------+-------+-------+
               | 2195  | 858   | 89    | 11    | 2221  |
               +-------+-------+-------+-------+-------+
               | 2217  | 442   | 89    | 11    | 2243  |
               +-------+-------+-------+-------+-------+
               | 2247  | 654   | 89    | 11    | 2273  |
               +-------+-------+-------+-------+-------+
               | 2278  | 82    | 97    | 11    | 2311  |
               +-------+-------+-------+-------+-------+
               | 2315  | 428   | 97    | 11    | 2347  |
               +-------+-------+-------+-------+-------+
               | 2339  | 442   | 97    | 11    | 2371  |
               +-------+-------+-------+-------+-------+
               | 2367  | 283   | 97    | 11    | 2399  |
               +-------+-------+-------+-------+-------+
               | 2392  | 538   | 97    | 11    | 2423  |
               +-------+-------+-------+-------+-------+
               | 2416  | 189   | 97    | 11    | 2447  |
               +-------+-------+-------+-------+-------+
               | 2447  | 438   | 97    | 11    | 2477  |
               +-------+-------+-------+-------+-------+
               | 2473  | 912   | 97    | 11    | 2503  |
               +-------+-------+-------+-------+-------+
               | 2502  | 1     | 97    | 11    | 2531  |
               +-------+-------+-------+-------+-------+
               | 2528  | 167   | 97    | 11    | 2557  |
               +-------+-------+-------+-------+-------+
               | 2565  | 272   | 97    | 11    | 2593  |
               +-------+-------+-------+-------+-------+
               | 2601  | 209   | 101   | 11    | 2633  |
               +-------+-------+-------+-------+-------+
               | 2640  | 927   | 101   | 11    | 2671  |
               +-------+-------+-------+-------+-------+
               | 2668  | 386   | 101   | 11    | 2699  |
               +-------+-------+-------+-------+-------+
               | 2701  | 653   | 101   | 11    | 2731  |
               +-------+-------+-------+-------+-------+
               | 2737  | 669   | 101   | 11    | 2767  |
               +-------+-------+-------+-------+-------+
               | 2772  | 431   | 101   | 11    | 2801  |
               +-------+-------+-------+-------+-------+
               | 2802  | 793   | 103   | 11    | 2833  |
               +-------+-------+-------+-------+-------+

Luby, et al. Standards Track [Page 49] RFC 6330 RaptorQ FEC Scheme August 2011

               +-------+-------+-------+-------+-------+
               | 2831  | 588   | 103   | 11    | 2861  |
               +-------+-------+-------+-------+-------+
               | 2875  | 777   | 107   | 11    | 2909  |
               +-------+-------+-------+-------+-------+
               | 2906  | 939   | 107   | 11    | 2939  |
               +-------+-------+-------+-------+-------+
               | 2938  | 864   | 107   | 11    | 2971  |
               +-------+-------+-------+-------+-------+
               | 2979  | 627   | 107   | 11    | 3011  |
               +-------+-------+-------+-------+-------+
               | 3015  | 265   | 109   | 11    | 3049  |
               +-------+-------+-------+-------+-------+
               | 3056  | 976   | 109   | 11    | 3089  |
               +-------+-------+-------+-------+-------+
               | 3101  | 988   | 113   | 11    | 3137  |
               +-------+-------+-------+-------+-------+
               | 3151  | 507   | 113   | 11    | 3187  |
               +-------+-------+-------+-------+-------+
               | 3186  | 640   | 113   | 11    | 3221  |
               +-------+-------+-------+-------+-------+
               | 3224  | 15    | 113   | 11    | 3259  |
               +-------+-------+-------+-------+-------+
               | 3265  | 667   | 113   | 11    | 3299  |
               +-------+-------+-------+-------+-------+
               | 3299  | 24    | 127   | 11    | 3347  |
               +-------+-------+-------+-------+-------+
               | 3344  | 877   | 127   | 11    | 3391  |
               +-------+-------+-------+-------+-------+
               | 3387  | 240   | 127   | 11    | 3433  |
               +-------+-------+-------+-------+-------+
               | 3423  | 720   | 127   | 11    | 3469  |
               +-------+-------+-------+-------+-------+
               | 3466  | 93    | 127   | 11    | 3511  |
               +-------+-------+-------+-------+-------+
               | 3502  | 919   | 127   | 11    | 3547  |
               +-------+-------+-------+-------+-------+
               | 3539  | 635   | 127   | 11    | 3583  |
               +-------+-------+-------+-------+-------+
               | 3579  | 174   | 127   | 11    | 3623  |
               +-------+-------+-------+-------+-------+
               | 3616  | 647   | 127   | 11    | 3659  |
               +-------+-------+-------+-------+-------+
               | 3658  | 820   | 127   | 11    | 3701  |
               +-------+-------+-------+-------+-------+
               | 3697  | 56    | 127   | 11    | 3739  |
               +-------+-------+-------+-------+-------+

Luby, et al. Standards Track [Page 50] RFC 6330 RaptorQ FEC Scheme August 2011

               +-------+-------+-------+-------+-------+
               | 3751  | 485   | 127   | 11    | 3793  |
               +-------+-------+-------+-------+-------+
               | 3792  | 210   | 127   | 11    | 3833  |
               +-------+-------+-------+-------+-------+
               | 3840  | 124   | 127   | 11    | 3881  |
               +-------+-------+-------+-------+-------+
               | 3883  | 546   | 127   | 11    | 3923  |
               +-------+-------+-------+-------+-------+
               | 3924  | 954   | 131   | 11    | 3967  |
               +-------+-------+-------+-------+-------+
               | 3970  | 262   | 131   | 11    | 4013  |
               +-------+-------+-------+-------+-------+
               | 4015  | 927   | 131   | 11    | 4057  |
               +-------+-------+-------+-------+-------+
               | 4069  | 957   | 131   | 11    | 4111  |
               +-------+-------+-------+-------+-------+
               | 4112  | 726   | 137   | 11    | 4159  |
               +-------+-------+-------+-------+-------+
               | 4165  | 583   | 137   | 11    | 4211  |
               +-------+-------+-------+-------+-------+
               | 4207  | 782   | 137   | 11    | 4253  |
               +-------+-------+-------+-------+-------+
               | 4252  | 37    | 137   | 11    | 4297  |
               +-------+-------+-------+-------+-------+
               | 4318  | 758   | 137   | 11    | 4363  |
               +-------+-------+-------+-------+-------+
               | 4365  | 777   | 137   | 11    | 4409  |
               +-------+-------+-------+-------+-------+
               | 4418  | 104   | 139   | 11    | 4463  |
               +-------+-------+-------+-------+-------+
               | 4468  | 476   | 139   | 11    | 4513  |
               +-------+-------+-------+-------+-------+
               | 4513  | 113   | 149   | 11    | 4567  |
               +-------+-------+-------+-------+-------+
               | 4567  | 313   | 149   | 11    | 4621  |
               +-------+-------+-------+-------+-------+
               | 4626  | 102   | 149   | 11    | 4679  |
               +-------+-------+-------+-------+-------+
               | 4681  | 501   | 149   | 11    | 4733  |
               +-------+-------+-------+-------+-------+
               | 4731  | 332   | 149   | 11    | 4783  |
               +-------+-------+-------+-------+-------+
               | 4780  | 786   | 149   | 11    | 4831  |
               +-------+-------+-------+-------+-------+
               | 4838  | 99    | 149   | 11    | 4889  |
               +-------+-------+-------+-------+-------+

Luby, et al. Standards Track [Page 51] RFC 6330 RaptorQ FEC Scheme August 2011

               +-------+-------+-------+-------+-------+
               | 4901  | 658   | 149   | 11    | 4951  |
               +-------+-------+-------+-------+-------+
               | 4954  | 794   | 149   | 11    | 5003  |
               +-------+-------+-------+-------+-------+
               | 5008  | 37    | 151   | 11    | 5059  |
               +-------+-------+-------+-------+-------+
               | 5063  | 471   | 151   | 11    | 5113  |
               +-------+-------+-------+-------+-------+
               | 5116  | 94    | 157   | 11    | 5171  |
               +-------+-------+-------+-------+-------+
               | 5172  | 873   | 157   | 11    | 5227  |
               +-------+-------+-------+-------+-------+
               | 5225  | 918   | 157   | 11    | 5279  |
               +-------+-------+-------+-------+-------+
               | 5279  | 945   | 157   | 11    | 5333  |
               +-------+-------+-------+-------+-------+
               | 5334  | 211   | 157   | 11    | 5387  |
               +-------+-------+-------+-------+-------+
               | 5391  | 341   | 157   | 11    | 5443  |
               +-------+-------+-------+-------+-------+
               | 5449  | 11    | 163   | 11    | 5507  |
               +-------+-------+-------+-------+-------+
               | 5506  | 578   | 163   | 11    | 5563  |
               +-------+-------+-------+-------+-------+
               | 5566  | 494   | 163   | 11    | 5623  |
               +-------+-------+-------+-------+-------+
               | 5637  | 694   | 163   | 11    | 5693  |
               +-------+-------+-------+-------+-------+
               | 5694  | 252   | 163   | 11    | 5749  |
               +-------+-------+-------+-------+-------+
               | 5763  | 451   | 167   | 11    | 5821  |
               +-------+-------+-------+-------+-------+
               | 5823  | 83    | 167   | 11    | 5881  |
               +-------+-------+-------+-------+-------+
               | 5896  | 689   | 167   | 11    | 5953  |
               +-------+-------+-------+-------+-------+
               | 5975  | 488   | 173   | 11    | 6037  |
               +-------+-------+-------+-------+-------+
               | 6039  | 214   | 173   | 11    | 6101  |
               +-------+-------+-------+-------+-------+
               | 6102  | 17    | 173   | 11    | 6163  |
               +-------+-------+-------+-------+-------+
               | 6169  | 469   | 173   | 11    | 6229  |
               +-------+-------+-------+-------+-------+
               | 6233  | 263   | 179   | 11    | 6299  |
               +-------+-------+-------+-------+-------+

Luby, et al. Standards Track [Page 52] RFC 6330 RaptorQ FEC Scheme August 2011

               +-------+-------+-------+-------+-------+
               | 6296  | 309   | 179   | 11    | 6361  |
               +-------+-------+-------+-------+-------+
               | 6363  | 984   | 179   | 11    | 6427  |
               +-------+-------+-------+-------+-------+
               | 6427  | 123   | 179   | 11    | 6491  |
               +-------+-------+-------+-------+-------+
               | 6518  | 360   | 179   | 11    | 6581  |
               +-------+-------+-------+-------+-------+
               | 6589  | 863   | 181   | 11    | 6653  |
               +-------+-------+-------+-------+-------+
               | 6655  | 122   | 181   | 11    | 6719  |
               +-------+-------+-------+-------+-------+
               | 6730  | 522   | 191   | 11    | 6803  |
               +-------+-------+-------+-------+-------+
               | 6799  | 539   | 191   | 11    | 6871  |
               +-------+-------+-------+-------+-------+
               | 6878  | 181   | 191   | 11    | 6949  |
               +-------+-------+-------+-------+-------+
               | 6956  | 64    | 191   | 11    | 7027  |
               +-------+-------+-------+-------+-------+
               | 7033  | 387   | 191   | 11    | 7103  |
               +-------+-------+-------+-------+-------+
               | 7108  | 967   | 191   | 11    | 7177  |
               +-------+-------+-------+-------+-------+
               | 7185  | 843   | 191   | 11    | 7253  |
               +-------+-------+-------+-------+-------+
               | 7281  | 999   | 193   | 11    | 7351  |
               +-------+-------+-------+-------+-------+
               | 7360  | 76    | 197   | 11    | 7433  |
               +-------+-------+-------+-------+-------+
               | 7445  | 142   | 197   | 11    | 7517  |
               +-------+-------+-------+-------+-------+
               | 7520  | 599   | 197   | 11    | 7591  |
               +-------+-------+-------+-------+-------+
               | 7596  | 576   | 199   | 11    | 7669  |
               +-------+-------+-------+-------+-------+
               | 7675  | 176   | 211   | 11    | 7759  |
               +-------+-------+-------+-------+-------+
               | 7770  | 392   | 211   | 11    | 7853  |
               +-------+-------+-------+-------+-------+
               | 7855  | 332   | 211   | 11    | 7937  |
               +-------+-------+-------+-------+-------+
               | 7935  | 291   | 211   | 11    | 8017  |
               +-------+-------+-------+-------+-------+
               | 8030  | 913   | 211   | 11    | 8111  |
               +-------+-------+-------+-------+-------+

Luby, et al. Standards Track [Page 53] RFC 6330 RaptorQ FEC Scheme August 2011

               +-------+-------+-------+-------+-------+
               | 8111  | 608   | 211   | 11    | 8191  |
               +-------+-------+-------+-------+-------+
               | 8194  | 212   | 211   | 11    | 8273  |
               +-------+-------+-------+-------+-------+
               | 8290  | 696   | 211   | 11    | 8369  |
               +-------+-------+-------+-------+-------+
               | 8377  | 931   | 223   | 11    | 8467  |
               +-------+-------+-------+-------+-------+
               | 8474  | 326   | 223   | 11    | 8563  |
               +-------+-------+-------+-------+-------+
               | 8559  | 228   | 223   | 11    | 8647  |
               +-------+-------+-------+-------+-------+
               | 8654  | 706   | 223   | 11    | 8741  |
               +-------+-------+-------+-------+-------+
               | 8744  | 144   | 223   | 11    | 8831  |
               +-------+-------+-------+-------+-------+
               | 8837  | 83    | 223   | 11    | 8923  |
               +-------+-------+-------+-------+-------+
               | 8928  | 743   | 223   | 11    | 9013  |
               +-------+-------+-------+-------+-------+
               | 9019  | 187   | 223   | 11    | 9103  |
               +-------+-------+-------+-------+-------+
               | 9111  | 654   | 227   | 11    | 9199  |
               +-------+-------+-------+-------+-------+
               | 9206  | 359   | 227   | 11    | 9293  |
               +-------+-------+-------+-------+-------+
               | 9303  | 493   | 229   | 11    | 9391  |
               +-------+-------+-------+-------+-------+
               | 9400  | 369   | 233   | 11    | 9491  |
               +-------+-------+-------+-------+-------+
               | 9497  | 981   | 233   | 11    | 9587  |
               +-------+-------+-------+-------+-------+
               | 9601  | 276   | 239   | 11    | 9697  |
               +-------+-------+-------+-------+-------+
               | 9708  | 647   | 239   | 11    | 9803  |
               +-------+-------+-------+-------+-------+
               | 9813  | 389   | 239   | 11    | 9907  |
               +-------+-------+-------+-------+-------+
               | 9916  | 80    | 239   | 11    | 10009 |
               +-------+-------+-------+-------+-------+
               | 10017 | 396   | 241   | 11    | 10111 |
               +-------+-------+-------+-------+-------+
               | 10120 | 580   | 251   | 11    | 10223 |
               +-------+-------+-------+-------+-------+
               | 10241 | 873   | 251   | 11    | 10343 |
               +-------+-------+-------+-------+-------+

Luby, et al. Standards Track [Page 54] RFC 6330 RaptorQ FEC Scheme August 2011

               +-------+-------+-------+-------+-------+
               | 10351 | 15    | 251   | 11    | 10453 |
               +-------+-------+-------+-------+-------+
               | 10458 | 976   | 251   | 11    | 10559 |
               +-------+-------+-------+-------+-------+
               | 10567 | 584   | 251   | 11    | 10667 |
               +-------+-------+-------+-------+-------+
               | 10676 | 267   | 257   | 11    | 10781 |
               +-------+-------+-------+-------+-------+
               | 10787 | 876   | 257   | 11    | 10891 |
               +-------+-------+-------+-------+-------+
               | 10899 | 642   | 257   | 12    | 11003 |
               +-------+-------+-------+-------+-------+
               | 11015 | 794   | 257   | 12    | 11119 |
               +-------+-------+-------+-------+-------+
               | 11130 | 78    | 263   | 12    | 11239 |
               +-------+-------+-------+-------+-------+
               | 11245 | 736   | 263   | 12    | 11353 |
               +-------+-------+-------+-------+-------+
               | 11358 | 882   | 269   | 12    | 11471 |
               +-------+-------+-------+-------+-------+
               | 11475 | 251   | 269   | 12    | 11587 |
               +-------+-------+-------+-------+-------+
               | 11590 | 434   | 269   | 12    | 11701 |
               +-------+-------+-------+-------+-------+
               | 11711 | 204   | 269   | 12    | 11821 |
               +-------+-------+-------+-------+-------+
               | 11829 | 256   | 271   | 12    | 11941 |
               +-------+-------+-------+-------+-------+
               | 11956 | 106   | 277   | 12    | 12073 |
               +-------+-------+-------+-------+-------+
               | 12087 | 375   | 277   | 12    | 12203 |
               +-------+-------+-------+-------+-------+
               | 12208 | 148   | 277   | 12    | 12323 |
               +-------+-------+-------+-------+-------+
               | 12333 | 496   | 281   | 12    | 12451 |
               +-------+-------+-------+-------+-------+
               | 12460 | 88    | 281   | 12    | 12577 |
               +-------+-------+-------+-------+-------+
               | 12593 | 826   | 293   | 12    | 12721 |
               +-------+-------+-------+-------+-------+
               | 12726 | 71    | 293   | 12    | 12853 |
               +-------+-------+-------+-------+-------+
               | 12857 | 925   | 293   | 12    | 12983 |
               +-------+-------+-------+-------+-------+
               | 13002 | 760   | 293   | 12    | 13127 |
               +-------+-------+-------+-------+-------+

Luby, et al. Standards Track [Page 55] RFC 6330 RaptorQ FEC Scheme August 2011

               +-------+-------+-------+-------+-------+
               | 13143 | 130   | 293   | 12    | 13267 |
               +-------+-------+-------+-------+-------+
               | 13284 | 641   | 307   | 12    | 13421 |
               +-------+-------+-------+-------+-------+
               | 13417 | 400   | 307   | 12    | 13553 |
               +-------+-------+-------+-------+-------+
               | 13558 | 480   | 307   | 12    | 13693 |
               +-------+-------+-------+-------+-------+
               | 13695 | 76    | 307   | 12    | 13829 |
               +-------+-------+-------+-------+-------+
               | 13833 | 665   | 307   | 12    | 13967 |
               +-------+-------+-------+-------+-------+
               | 13974 | 910   | 307   | 12    | 14107 |
               +-------+-------+-------+-------+-------+
               | 14115 | 467   | 311   | 12    | 14251 |
               +-------+-------+-------+-------+-------+
               | 14272 | 964   | 311   | 12    | 14407 |
               +-------+-------+-------+-------+-------+
               | 14415 | 625   | 313   | 12    | 14551 |
               +-------+-------+-------+-------+-------+
               | 14560 | 362   | 317   | 12    | 14699 |
               +-------+-------+-------+-------+-------+
               | 14713 | 759   | 317   | 12    | 14851 |
               +-------+-------+-------+-------+-------+
               | 14862 | 728   | 331   | 12    | 15013 |
               +-------+-------+-------+-------+-------+
               | 15011 | 343   | 331   | 12    | 15161 |
               +-------+-------+-------+-------+-------+
               | 15170 | 113   | 331   | 12    | 15319 |
               +-------+-------+-------+-------+-------+
               | 15325 | 137   | 331   | 12    | 15473 |
               +-------+-------+-------+-------+-------+
               | 15496 | 308   | 331   | 12    | 15643 |
               +-------+-------+-------+-------+-------+
               | 15651 | 800   | 337   | 12    | 15803 |
               +-------+-------+-------+-------+-------+
               | 15808 | 177   | 337   | 12    | 15959 |
               +-------+-------+-------+-------+-------+
               | 15977 | 961   | 337   | 12    | 16127 |
               +-------+-------+-------+-------+-------+
               | 16161 | 958   | 347   | 12    | 16319 |
               +-------+-------+-------+-------+-------+
               | 16336 | 72    | 347   | 12    | 16493 |
               +-------+-------+-------+-------+-------+
               | 16505 | 732   | 347   | 12    | 16661 |
               +-------+-------+-------+-------+-------+

Luby, et al. Standards Track [Page 56] RFC 6330 RaptorQ FEC Scheme August 2011

               +-------+-------+-------+-------+-------+
               | 16674 | 145   | 349   | 12    | 16831 |
               +-------+-------+-------+-------+-------+
               | 16851 | 577   | 353   | 12    | 17011 |
               +-------+-------+-------+-------+-------+
               | 17024 | 305   | 353   | 12    | 17183 |
               +-------+-------+-------+-------+-------+
               | 17195 | 50    | 359   | 12    | 17359 |
               +-------+-------+-------+-------+-------+
               | 17376 | 351   | 359   | 12    | 17539 |
               +-------+-------+-------+-------+-------+
               | 17559 | 175   | 367   | 12    | 17729 |
               +-------+-------+-------+-------+-------+
               | 17742 | 727   | 367   | 12    | 17911 |
               +-------+-------+-------+-------+-------+
               | 17929 | 902   | 367   | 12    | 18097 |
               +-------+-------+-------+-------+-------+
               | 18116 | 409   | 373   | 12    | 18289 |
               +-------+-------+-------+-------+-------+
               | 18309 | 776   | 373   | 12    | 18481 |
               +-------+-------+-------+-------+-------+
               | 18503 | 586   | 379   | 12    | 18679 |
               +-------+-------+-------+-------+-------+
               | 18694 | 451   | 379   | 12    | 18869 |
               +-------+-------+-------+-------+-------+
               | 18909 | 287   | 383   | 12    | 19087 |
               +-------+-------+-------+-------+-------+
               | 19126 | 246   | 389   | 12    | 19309 |
               +-------+-------+-------+-------+-------+
               | 19325 | 222   | 389   | 12    | 19507 |
               +-------+-------+-------+-------+-------+
               | 19539 | 563   | 397   | 12    | 19727 |
               +-------+-------+-------+-------+-------+
               | 19740 | 839   | 397   | 12    | 19927 |
               +-------+-------+-------+-------+-------+
               | 19939 | 897   | 401   | 12    | 20129 |
               +-------+-------+-------+-------+-------+
               | 20152 | 409   | 401   | 12    | 20341 |
               +-------+-------+-------+-------+-------+
               | 20355 | 618   | 409   | 12    | 20551 |
               +-------+-------+-------+-------+-------+
               | 20564 | 439   | 409   | 12    | 20759 |
               +-------+-------+-------+-------+-------+
               | 20778 | 95    | 419   | 13    | 20983 |
               +-------+-------+-------+-------+-------+
               | 20988 | 448   | 419   | 13    | 21191 |
               +-------+-------+-------+-------+-------+

Luby, et al. Standards Track [Page 57] RFC 6330 RaptorQ FEC Scheme August 2011

               +-------+-------+-------+-------+-------+
               | 21199 | 133   | 419   | 13    | 21401 |
               +-------+-------+-------+-------+-------+
               | 21412 | 938   | 419   | 13    | 21613 |
               +-------+-------+-------+-------+-------+
               | 21629 | 423   | 431   | 13    | 21841 |
               +-------+-------+-------+-------+-------+
               | 21852 | 90    | 431   | 13    | 22063 |
               +-------+-------+-------+-------+-------+
               | 22073 | 640   | 431   | 13    | 22283 |
               +-------+-------+-------+-------+-------+
               | 22301 | 922   | 433   | 13    | 22511 |
               +-------+-------+-------+-------+-------+
               | 22536 | 250   | 439   | 13    | 22751 |
               +-------+-------+-------+-------+-------+
               | 22779 | 367   | 439   | 13    | 22993 |
               +-------+-------+-------+-------+-------+
               | 23010 | 447   | 443   | 13    | 23227 |
               +-------+-------+-------+-------+-------+
               | 23252 | 559   | 449   | 13    | 23473 |
               +-------+-------+-------+-------+-------+
               | 23491 | 121   | 457   | 13    | 23719 |
               +-------+-------+-------+-------+-------+
               | 23730 | 623   | 457   | 13    | 23957 |
               +-------+-------+-------+-------+-------+
               | 23971 | 450   | 457   | 13    | 24197 |
               +-------+-------+-------+-------+-------+
               | 24215 | 253   | 461   | 13    | 24443 |
               +-------+-------+-------+-------+-------+
               | 24476 | 106   | 467   | 13    | 24709 |
               +-------+-------+-------+-------+-------+
               | 24721 | 863   | 467   | 13    | 24953 |
               +-------+-------+-------+-------+-------+
               | 24976 | 148   | 479   | 13    | 25219 |
               +-------+-------+-------+-------+-------+
               | 25230 | 427   | 479   | 13    | 25471 |
               +-------+-------+-------+-------+-------+
               | 25493 | 138   | 479   | 13    | 25733 |
               +-------+-------+-------+-------+-------+
               | 25756 | 794   | 487   | 13    | 26003 |
               +-------+-------+-------+-------+-------+
               | 26022 | 247   | 487   | 13    | 26267 |
               +-------+-------+-------+-------+-------+
               | 26291 | 562   | 491   | 13    | 26539 |
               +-------+-------+-------+-------+-------+
               | 26566 | 53    | 499   | 13    | 26821 |
               +-------+-------+-------+-------+-------+

Luby, et al. Standards Track [Page 58] RFC 6330 RaptorQ FEC Scheme August 2011

               +-------+-------+-------+-------+-------+
               | 26838 | 135   | 499   | 13    | 27091 |
               +-------+-------+-------+-------+-------+
               | 27111 | 21    | 503   | 13    | 27367 |
               +-------+-------+-------+-------+-------+
               | 27392 | 201   | 509   | 13    | 27653 |
               +-------+-------+-------+-------+-------+
               | 27682 | 169   | 521   | 13    | 27953 |
               +-------+-------+-------+-------+-------+
               | 27959 | 70    | 521   | 13    | 28229 |
               +-------+-------+-------+-------+-------+
               | 28248 | 386   | 521   | 13    | 28517 |
               +-------+-------+-------+-------+-------+
               | 28548 | 226   | 523   | 13    | 28817 |
               +-------+-------+-------+-------+-------+
               | 28845 | 3     | 541   | 13    | 29131 |
               +-------+-------+-------+-------+-------+
               | 29138 | 769   | 541   | 13    | 29423 |
               +-------+-------+-------+-------+-------+
               | 29434 | 590   | 541   | 13    | 29717 |
               +-------+-------+-------+-------+-------+
               | 29731 | 672   | 541   | 13    | 30013 |
               +-------+-------+-------+-------+-------+
               | 30037 | 713   | 547   | 13    | 30323 |
               +-------+-------+-------+-------+-------+
               | 30346 | 967   | 547   | 13    | 30631 |
               +-------+-------+-------+-------+-------+
               | 30654 | 368   | 557   | 14    | 30949 |
               +-------+-------+-------+-------+-------+
               | 30974 | 348   | 557   | 14    | 31267 |
               +-------+-------+-------+-------+-------+
               | 31285 | 119   | 563   | 14    | 31583 |
               +-------+-------+-------+-------+-------+
               | 31605 | 503   | 569   | 14    | 31907 |
               +-------+-------+-------+-------+-------+
               | 31948 | 181   | 571   | 14    | 32251 |
               +-------+-------+-------+-------+-------+
               | 32272 | 394   | 577   | 14    | 32579 |
               +-------+-------+-------+-------+-------+
               | 32601 | 189   | 587   | 14    | 32917 |
               +-------+-------+-------+-------+-------+
               | 32932 | 210   | 587   | 14    | 33247 |
               +-------+-------+-------+-------+-------+
               | 33282 | 62    | 593   | 14    | 33601 |
               +-------+-------+-------+-------+-------+
               | 33623 | 273   | 593   | 14    | 33941 |
               +-------+-------+-------+-------+-------+

Luby, et al. Standards Track [Page 59] RFC 6330 RaptorQ FEC Scheme August 2011

               +-------+-------+-------+-------+-------+
               | 33961 | 554   | 599   | 14    | 34283 |
               +-------+-------+-------+-------+-------+
               | 34302 | 936   | 607   | 14    | 34631 |
               +-------+-------+-------+-------+-------+
               | 34654 | 483   | 607   | 14    | 34981 |
               +-------+-------+-------+-------+-------+
               | 35031 | 397   | 613   | 14    | 35363 |
               +-------+-------+-------+-------+-------+
               | 35395 | 241   | 619   | 14    | 35731 |
               +-------+-------+-------+-------+-------+
               | 35750 | 500   | 631   | 14    | 36097 |
               +-------+-------+-------+-------+-------+
               | 36112 | 12    | 631   | 14    | 36457 |
               +-------+-------+-------+-------+-------+
               | 36479 | 958   | 641   | 14    | 36833 |
               +-------+-------+-------+-------+-------+
               | 36849 | 524   | 641   | 14    | 37201 |
               +-------+-------+-------+-------+-------+
               | 37227 | 8     | 643   | 14    | 37579 |
               +-------+-------+-------+-------+-------+
               | 37606 | 100   | 653   | 14    | 37967 |
               +-------+-------+-------+-------+-------+
               | 37992 | 339   | 653   | 14    | 38351 |
               +-------+-------+-------+-------+-------+
               | 38385 | 804   | 659   | 14    | 38749 |
               +-------+-------+-------+-------+-------+
               | 38787 | 510   | 673   | 14    | 39163 |
               +-------+-------+-------+-------+-------+
               | 39176 | 18    | 673   | 14    | 39551 |
               +-------+-------+-------+-------+-------+
               | 39576 | 412   | 677   | 14    | 39953 |
               +-------+-------+-------+-------+-------+
               | 39980 | 394   | 683   | 14    | 40361 |
               +-------+-------+-------+-------+-------+
               | 40398 | 830   | 691   | 15    | 40787 |
               +-------+-------+-------+-------+-------+
               | 40816 | 535   | 701   | 15    | 41213 |
               +-------+-------+-------+-------+-------+
               | 41226 | 199   | 701   | 15    | 41621 |
               +-------+-------+-------+-------+-------+
               | 41641 | 27    | 709   | 15    | 42043 |
               +-------+-------+-------+-------+-------+
               | 42067 | 298   | 709   | 15    | 42467 |
               +-------+-------+-------+-------+-------+
               | 42490 | 368   | 719   | 15    | 42899 |
               +-------+-------+-------+-------+-------+

Luby, et al. Standards Track [Page 60] RFC 6330 RaptorQ FEC Scheme August 2011

               +-------+-------+-------+-------+-------+
               | 42916 | 755   | 727   | 15    | 43331 |
               +-------+-------+-------+-------+-------+
               | 43388 | 379   | 727   | 15    | 43801 |
               +-------+-------+-------+-------+-------+
               | 43840 | 73    | 733   | 15    | 44257 |
               +-------+-------+-------+-------+-------+
               | 44279 | 387   | 739   | 15    | 44701 |
               +-------+-------+-------+-------+-------+
               | 44729 | 457   | 751   | 15    | 45161 |
               +-------+-------+-------+-------+-------+
               | 45183 | 761   | 751   | 15    | 45613 |
               +-------+-------+-------+-------+-------+
               | 45638 | 855   | 757   | 15    | 46073 |
               +-------+-------+-------+-------+-------+
               | 46104 | 370   | 769   | 15    | 46549 |
               +-------+-------+-------+-------+-------+
               | 46574 | 261   | 769   | 15    | 47017 |
               +-------+-------+-------+-------+-------+
               | 47047 | 299   | 787   | 15    | 47507 |
               +-------+-------+-------+-------+-------+
               | 47523 | 920   | 787   | 15    | 47981 |
               +-------+-------+-------+-------+-------+
               | 48007 | 269   | 787   | 15    | 48463 |
               +-------+-------+-------+-------+-------+
               | 48489 | 862   | 797   | 15    | 48953 |
               +-------+-------+-------+-------+-------+
               | 48976 | 349   | 809   | 15    | 49451 |
               +-------+-------+-------+-------+-------+
               | 49470 | 103   | 809   | 15    | 49943 |
               +-------+-------+-------+-------+-------+
               | 49978 | 115   | 821   | 15    | 50461 |
               +-------+-------+-------+-------+-------+
               | 50511 | 93    | 821   | 16    | 50993 |
               +-------+-------+-------+-------+-------+
               | 51017 | 982   | 827   | 16    | 51503 |
               +-------+-------+-------+-------+-------+
               | 51530 | 432   | 839   | 16    | 52027 |
               +-------+-------+-------+-------+-------+
               | 52062 | 340   | 853   | 16    | 52571 |
               +-------+-------+-------+-------+-------+
               | 52586 | 173   | 853   | 16    | 53093 |
               +-------+-------+-------+-------+-------+
               | 53114 | 421   | 857   | 16    | 53623 |
               +-------+-------+-------+-------+-------+
               | 53650 | 330   | 863   | 16    | 54163 |
               +-------+-------+-------+-------+-------+

Luby, et al. Standards Track [Page 61] RFC 6330 RaptorQ FEC Scheme August 2011

               +-------+-------+-------+-------+-------+
               | 54188 | 624   | 877   | 16    | 54713 |
               +-------+-------+-------+-------+-------+
               | 54735 | 233   | 877   | 16    | 55259 |
               +-------+-------+-------+-------+-------+
               | 55289 | 362   | 883   | 16    | 55817 |
               +-------+-------+-------+-------+-------+
               | 55843 | 963   | 907   | 16    | 56393 |
               +-------+-------+-------+-------+-------+
               | 56403 | 471   | 907   | 16    | 56951 |
               +-------+-------+-------+-------+-------+
           Table 2: Systematic Indices and Other Parameters

5.7. Operating with Octets, Symbols, and Matrices

5.7.1. General

 The remainder of this section describes the arithmetic operations
 that are used to generate encoding symbols from source symbols and to
 generate source symbols from encoding symbols.  Mathematically,
 octets can be thought of as elements of a finite field, i.e., the
 finite field GF(256) with 256 elements, and thus the addition and
 multiplication operations and identity elements and inverses over
 both operations are defined.  Matrix operations and symbol operations
 are defined based on the arithmetic operations on octets.  This
 allows a full implementation of these arithmetic operations without
 having to understand the underlying mathematics of finite fields.

5.7.2. Arithmetic Operations on Octets

 Octets are mapped to non-negative integers in the range 0 through 255
 in the usual way: A single octet of data from a symbol,
 B[7],B[6],B[5],B[4],B[3],B[2],B[1],B[0], where B[7] is the highest
 order bit and B[0] is the lowest order bit, is mapped to the integer
 i=B[7]*128+B[6]*64+B[5]*32+B[4]*16+B[3]*8+B[2]*4+B[1]*2+B[0].
 The addition of two octets u and v is defined as the exclusive-or
 operation, i.e.,
    u + v = u ^ v.
 Subtraction is defined in the same way, so we also have
    u - v = u ^ v.

Luby, et al. Standards Track [Page 62] RFC 6330 RaptorQ FEC Scheme August 2011

 The zero element (additive identity) is the octet represented by the
 integer 0.  The additive inverse of u is simply u, i.e.,
    u + u = 0.
 The multiplication of two octets is defined with the help of two
 tables OCT_EXP and OCT_LOG, which are given in Section 5.7.3 and
 Section 5.7.4, respectively.  The table OCT_LOG maps octets (other
 than the zero element) to non-negative integers, and OCT_EXP maps
 non-negative integers to octets.  For two octets u and v, we define
    u * v =
       0, if either u or v are 0,
       OCT_EXP[OCT_LOG[u] + OCT_LOG[v]] otherwise.
 Note that the '+' on the right-hand side of the above is the usual
 integer addition, since its arguments are ordinary integers.
 The division u / v of two octets u and v, and where v != 0, is
 defined as follows:
    u / v =
       0, if u == 0,
       OCT_EXP[OCT_LOG[u] - OCT_LOG[v] + 255] otherwise.
 The one element (multiplicative identity) is the octet represented by
 the integer 1.  For an octet u that is not the zero element, i.e.,
 the multiplicative inverse of u is
    OCT_EXP[255 - OCT_LOG[u]].
 The octet denoted by alpha is the octet with the integer
 representation 2.  If i is a non-negative integer 0 <= i < 256, we
 have
    alpha^^i = OCT_EXP[i].

5.7.3. The Table OCT_EXP

 The table OCT_EXP contains 510 octets.  The indexing starts at 0 and
 ranges to 509, and the entries are the octets with the following
 positive integer representation:

Luby, et al. Standards Track [Page 63] RFC 6330 RaptorQ FEC Scheme August 2011

 1, 2, 4, 8, 16, 32, 64, 128, 29, 58, 116, 232, 205, 135, 19, 38, 76,
 152, 45, 90, 180, 117, 234, 201, 143, 3, 6, 12, 24, 48, 96, 192, 157,
 39, 78, 156, 37, 74, 148, 53, 106, 212, 181, 119, 238, 193, 159, 35,
 70, 140, 5, 10, 20, 40, 80, 160, 93, 186, 105, 210, 185, 111, 222,
 161, 95, 190, 97, 194, 153, 47, 94, 188, 101, 202, 137, 15, 30, 60,
 120, 240, 253, 231, 211, 187, 107, 214, 177, 127, 254, 225, 223, 163,
 91, 182, 113, 226, 217, 175, 67, 134, 17, 34, 68, 136, 13, 26, 52,
 104, 208, 189, 103, 206, 129, 31, 62, 124, 248, 237, 199, 147, 59,
 118, 236, 197, 151, 51, 102, 204, 133, 23, 46, 92, 184, 109, 218,
 169, 79, 158, 33, 66, 132, 21, 42, 84, 168, 77, 154, 41, 82, 164, 85,
 170, 73, 146, 57, 114, 228, 213, 183, 115, 230, 209, 191, 99, 198,
 145, 63, 126, 252, 229, 215, 179, 123, 246, 241, 255, 227, 219, 171,
 75, 150, 49, 98, 196, 149, 55, 110, 220, 165, 87, 174, 65, 130, 25,
 50, 100, 200, 141, 7, 14, 28, 56, 112, 224, 221, 167, 83, 166, 81,
 162, 89, 178, 121, 242, 249, 239, 195, 155, 43, 86, 172, 69, 138, 9,
 18, 36, 72, 144, 61, 122, 244, 245, 247, 243, 251, 235, 203, 139, 11,
 22, 44, 88, 176, 125, 250, 233, 207, 131, 27, 54, 108, 216, 173, 71,
 142, 1, 2, 4, 8, 16, 32, 64, 128, 29, 58, 116, 232, 205, 135, 19, 38,
 76, 152, 45, 90, 180, 117, 234, 201, 143, 3, 6, 12, 24, 48, 96, 192,
 157, 39, 78, 156, 37, 74, 148, 53, 106, 212, 181, 119, 238, 193, 159,
 35, 70, 140, 5, 10, 20, 40, 80, 160, 93, 186, 105, 210, 185, 111,
 222, 161, 95, 190, 97, 194, 153, 47, 94, 188, 101, 202, 137, 15, 30,
 60, 120, 240, 253, 231, 211, 187, 107, 214, 177, 127, 254, 225, 223,
 163, 91, 182, 113, 226, 217, 175, 67, 134, 17, 34, 68, 136, 13, 26,
 52, 104, 208, 189, 103, 206, 129, 31, 62, 124, 248, 237, 199, 147,
 59, 118, 236, 197, 151, 51, 102, 204, 133, 23, 46, 92, 184, 109, 218,
 169, 79, 158, 33, 66, 132, 21, 42, 84, 168, 77, 154, 41, 82, 164, 85,
 170, 73, 146, 57, 114, 228, 213, 183, 115, 230, 209, 191, 99, 198,
 145, 63, 126, 252, 229, 215, 179, 123, 246, 241, 255, 227, 219, 171,
 75, 150, 49, 98, 196, 149, 55, 110, 220, 165, 87, 174, 65, 130, 25,
 50, 100, 200, 141, 7, 14, 28, 56, 112, 224, 221, 167, 83, 166, 81,
 162, 89, 178, 121, 242, 249, 239, 195, 155, 43, 86, 172, 69, 138, 9,
 18, 36, 72, 144, 61, 122, 244, 245, 247, 243, 251, 235, 203, 139, 11,
 22, 44, 88, 176, 125, 250, 233, 207, 131, 27, 54, 108, 216, 173, 71,
 142

5.7.4. The Table OCT_LOG

 The table OCT_LOG contains 255 non-negative integers.  The table is
 indexed by octets interpreted as integers.  The octet corresponding
 to the zero element, which is represented by the integer 0, is
 excluded as an index, and thus indexing starts at 1 and ranges up to
 255, and the entries are the following:
 0, 1, 25, 2, 50, 26, 198, 3, 223, 51, 238, 27, 104, 199, 75, 4, 100,
 224, 14, 52, 141, 239, 129, 28, 193, 105, 248, 200, 8, 76, 113, 5,
 138, 101, 47, 225, 36, 15, 33, 53, 147, 142, 218, 240, 18, 130, 69,
 29, 181, 194, 125, 106, 39, 249, 185, 201, 154, 9, 120, 77, 228, 114,

Luby, et al. Standards Track [Page 64] RFC 6330 RaptorQ FEC Scheme August 2011

 166, 6, 191, 139, 98, 102, 221, 48, 253, 226, 152, 37, 179, 16, 145,
 34, 136, 54, 208, 148, 206, 143, 150, 219, 189, 241, 210, 19, 92,
 131, 56, 70, 64, 30, 66, 182, 163, 195, 72, 126, 110, 107, 58, 40,
 84, 250, 133, 186, 61, 202, 94, 155, 159, 10, 21, 121, 43, 78, 212,
 229, 172, 115, 243, 167, 87, 7, 112, 192, 247, 140, 128, 99, 13, 103,
 74, 222, 237, 49, 197, 254, 24, 227, 165, 153, 119, 38, 184, 180,
 124, 17, 68, 146, 217, 35, 32, 137, 46, 55, 63, 209, 91, 149, 188,
 207, 205, 144, 135, 151, 178, 220, 252, 190, 97, 242, 86, 211, 171,
 20, 42, 93, 158, 132, 60, 57, 83, 71, 109, 65, 162, 31, 45, 67, 216,
 183, 123, 164, 118, 196, 23, 73, 236, 127, 12, 111, 246, 108, 161,
 59, 82, 41, 157, 85, 170, 251, 96, 134, 177, 187, 204, 62, 90, 203,
 89, 95, 176, 156, 169, 160, 81, 11, 245, 22, 235, 122, 117, 44, 215,
 79, 174, 213, 233, 230, 231, 173, 232, 116, 214, 244, 234, 168, 80,
 88, 175

5.7.5. Operations on Symbols

 Operations on symbols have the same semantics as operations on
 vectors of octets of length T in this specification.  Thus, if U and
 V are two symbols formed by the octets u[0], ..., u[T-1] and v[0],
 ..., v[T-1], respectively, the sum of symbols U + V is defined to be
 the component-wise sum of octets, i.e., equal to the symbol D formed
 by the octets d[0], ..., d[T-1], such that
    d[i] = u[i] + v[i], 0 <= i < T.
 Furthermore, if beta is an octet, the product beta*U is defined to be
 the symbol D obtained by multiplying each octet of U by beta, i.e.,
    d[i] = beta*u[i], 0 <= i < T.

5.7.6. Operations on Matrices

 All matrices in this specification have entries that are octets, and
 thus matrix operations and definitions are defined in terms of the
 underlying octet arithmetic, e.g., operations on a matrix, matrix
 rank, and matrix inversion.

5.8. Requirements for a Compliant Decoder

 If a RaptorQ-compliant decoder receives a mathematically sufficient
 set of encoding symbols generated according to the encoder
 specification in Section 5.3 for reconstruction of a source block,
 then such a decoder SHOULD recover the entire source block.
 A RaptorQ-compliant decoder SHALL have the following recovery
 properties for source blocks with K' source symbols for all values of
 K' in Table 2 of Section 5.6.

Luby, et al. Standards Track [Page 65] RFC 6330 RaptorQ FEC Scheme August 2011

 1.  If the decoder receives K' encoding symbols generated according
     to the encoder specification in Section 5.3 with corresponding
     ESIs chosen independently and uniformly at random from the range
     of possible ESIs, then on average the decoder will fail to
     recover the entire source block at most 1 out of 100 times.
 2.  If the decoder receives K'+1 encoding symbols generated according
     to the encoder specification in Section 5.3 with corresponding
     ESIs chosen independently and uniformly at random from the range
     of possible ESIs, then on average the decoder will fail to
     recover the entire source block at most 1 out of 10,000 times.
 3.  If the decoder receives K'+2 encoding symbols generated according
     to the encoder specification in Section 5.3 with corresponding
     ESIs chosen independently and uniformly at random from the range
     of possible ESIs, then on average the decoder will fail to
     recover the entire source block at most 1 out of 1,000,000 times.
 Note that the Example FEC Decoder specified in Section 5.4 fulfills
 both requirements, i.e.,
 1.  it can reconstruct a source block as long as it receives a
     mathematically sufficient set of encoding symbols generated
     according to the encoder specification in Section 5.3, and
 2.  it fulfills the mandatory recovery properties from above.

6. Security Considerations

 Data delivery can be subject to denial-of-service attacks by
 attackers that send corrupted packets that are accepted as legitimate
 by receivers.  This is particularly a concern for multicast delivery
 because a corrupted packet may be injected into the session close to
 the root of the multicast tree, in which case the corrupted packet
 will arrive at many receivers.  The use of even one corrupted packet
 containing encoding data may result in the decoding of an object that
 is completely corrupted and unusable.  It is thus RECOMMENDED that
 source authentication and integrity checking are applied to decoded
 objects before delivering objects to an application.  For example, a
 SHA-256 hash [FIPS.180-3.2008] of an object may be appended before
 transmission, and the SHA-256 hash is computed and checked after the
 object is decoded but before it is delivered to an application.
 Source authentication SHOULD be provided, for example, by including a
 digital signature verifiable by the receiver computed on top of the
 hash value.  It is also RECOMMENDED that a packet authentication
 protocol such as TESLA [RFC4082] be used to detect and discard
 corrupted packets upon arrival.  This method may also be used to
 provide source authentication.  Furthermore, it is RECOMMENDED that

Luby, et al. Standards Track [Page 66] RFC 6330 RaptorQ FEC Scheme August 2011

 Reverse Path Forwarding checks be enabled in all network routers and
 switches along the path from the sender to receivers to limit the
 possibility of a bad agent successfully injecting a corrupted packet
 into the multicast tree data path.
 Another security concern is that some FEC information may be obtained
 by receivers out-of-band in a session description, and if the session
 description is forged or corrupted, then the receivers will not use
 the correct protocol for decoding content from received packets.  To
 avoid these problems, it is RECOMMENDED that measures be taken to
 prevent receivers from accepting incorrect session descriptions,
 e.g., by using source authentication to ensure that receivers only
 accept legitimate session descriptions from authorized senders.

7. IANA Considerations

 Values of FEC Encoding IDs and FEC Instance IDs are subject to IANA
 registration.  For general guidelines on IANA considerations as they
 apply to this document, see [RFC5052].  IANA has assigned the value 6
 under the ietf:rmt:fec:encoding registry to "RaptorQ Code" as the
 Fully-Specified FEC Encoding ID value associated with this
 specification.

8. Acknowledgements

 Thanks are due to Ranganathan (Ranga) Krishnan.  Ranga Krishnan has
 been very supportive in finding and resolving implementation details
 and in finding the systematic indices.  In addition, Habeeb Mohiuddin
 Mohammed and Antonios Pitarokoilis, both from the Munich University
 of Technology (TUM), and Alan Shinsato have done two independent
 implementations of the RaptorQ encoder/decoder that have helped to
 clarify and to resolve issues with this specification.

9. References

9.1. Normative References

 [FIPS.180-3.2008]
            National Institute of Standards and Technology, "Secure
            Hash Standard", FIPS PUB 180-3, October 2008.
 [RFC2119]  Bradner, S., "Key words for use in RFCs to Indicate
            Requirement Levels", BCP 14, RFC 2119, March 1997.
 [RFC4082]  Perrig, A., Song, D., Canetti, R., Tygar, J., and B.
            Briscoe, "Timed Efficient Stream Loss-Tolerant
            Authentication (TESLA): Multicast Source Authentication
            Transform Introduction", RFC 4082, June 2005.

Luby, et al. Standards Track [Page 67] RFC 6330 RaptorQ FEC Scheme August 2011

 [RFC5052]  Watson, M., Luby, M., and L. Vicisano, "Forward Error
            Correction (FEC) Building Block", RFC 5052, August 2007.

9.2. Informative References

 [LTCodes]  Luby, M., "LT codes", Annual IEEE Symposium on Foundations
            of Computer Science, pp. 271-280, November 2002.
 [RFC3453]  Luby, M., Vicisano, L., Gemmell, J., Rizzo, L., Handley,
            M., and J. Crowcroft, "The Use of Forward Error Correction
            (FEC) in Reliable Multicast", RFC 3453, December 2002.
 [RFC5053]  Luby, M., Shokrollahi, A., Watson, M., and T. Stockhammer,
            "Raptor Forward Error Correction Scheme for Object
            Delivery", RFC 5053, October 2007.
 [RaptorCodes]
            Shokrollahi, A. and M. Luby, "Raptor Codes", Foundations
            and Trends in Communications and Information Theory: Vol.
            6: No. 3-4, pp. 213-322, 2011.

Luby, et al. Standards Track [Page 68] RFC 6330 RaptorQ FEC Scheme August 2011

Authors' Addresses

 Michael Luby
 Qualcomm Incorporated
 3165 Kifer Road
 Santa Clara, CA  95051
 U.S.A.
 EMail: luby@qualcomm.com
 Amin Shokrollahi
 EPFL
 Laboratoire d'algorithmique
 Station 14
 Batiment BC
 Lausanne  1015
 Switzerland
 EMail: amin.shokrollahi@epfl.ch
 Mark Watson
 Netflix Inc.
 100 Winchester Circle
 Los Gatos, CA  95032
 U.S.A.
 EMail: watsonm@netflix.com
 Thomas Stockhammer
 Nomor Research
 Brecherspitzstrasse 8
 Munich  81541
 Germany
 EMail: stockhammer@nomor.de
 Lorenz Minder
 Qualcomm Incorporated
 3165 Kifer Road
 Santa Clara, CA  95051
 U.S.A.
 EMail: lminder@qualcomm.com

Luby, et al. Standards Track [Page 69]

/data/webs/external/dokuwiki/data/pages/rfc/rfc6330.txt · Last modified: 2011/08/12 23:36 (external edit)