1toX v1.61 serial key or number

[Docs] [txt|pdf] [draft-ietf-rmt] [Tracker] [Diff1] [Diff2] [IPR]

PROPOSED STANDARD

Network Working Group M. Luby Request for Comments: Digital Fountain Category: Standards Track A. Shokrollahi EPFL M. Watson Digital Fountain T. Stockhammer Nomor Research October Raptor Forward Error Correction Scheme for Object Delivery Status of This Memo This document specifies an Internet standards track protocol for the Internet community, and requests discussion and suggestions for improvements. Please refer to the current edition of the "Internet Official Protocol Standards" (STD 1) for the standardization state and status of this protocol. Distribution of this memo is unlimited. Abstract This document describes a Fully-Specified Forward Error Correction (FEC) scheme, corresponding to FEC Encoding ID 1, for the Raptor forward error correction code and its application to reliable delivery of data objects. Raptor is a fountain code, i.e., as many encoding symbols as needed can be generated by the encoder on-the-fly from the source symbols of a source block of data. The decoder is able to recover the source block from any set of encoding symbols only slightly more in number than the number of source symbols. The Raptor code described here is a systematic code, meaning that all the source symbols are among the encoding symbols that can be generated. Luby, et al. Standards Track [Page 1]

---

RFC Raptor FEC Scheme October Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . Requirements Notation . . . . . . . . . . . . . . . . . . . . Formats and Codes . . . . . . . . . . . . . . . . . . . . . . FEC Payload IDs . . . . . . . . . . . . . . . . . . . . . FEC Object Transmission Information (OTI) . . . . . . . . Mandatory . . . . . . . . . . . . . . . . . . . . . . Common . . . . . . . . . . . . . . . . . . . . . . . . Scheme-Specific . . . . . . . . . . . . . . . . . . . Procedures . . . . . . . . . . . . . . . . . . . . . . . . . . Content Delivery Protocol Requirements . . . . . . . . . . Example Parameter Derivation Algorithm . . . . . . . . . . Raptor FEC Code Specification . . . . . . . . . . . . . . . . Definitions, Symbols, and Abbreviations . . . . . . . . . Definitions . . . . . . . . . . . . . . . . . . . . . Symbols . . . . . . . . . . . . . . . . . . . . . . . Abbreviations . . . . . . . . . . . . . . . . . . . . Overview . . . . . . . . . . . . . . . . . . . . . . . . . Object Delivery . . . . . . . . . . . . . . . . . . . . . Source Block Construction . . . . . . . . . . . . . . Encoding Packet Construction . . . . . . . . . . . . . Systematic Raptor Encoder . . . . . . . . . . . . . . . . Encoding Overview . . . . . . . . . . . . . . . . . . 15 First Encoding Step: Intermediate Symbol Generation . 16 Second Encoding Step: LT Encoding . . . . . . . . . . Generators . . . . . . . . . . . . . . . . . . . . . . Example FEC Decoder . . . . . . . . . . . . . . . . . . . General . . . . . . . . . . . . . . . . . . . . . . . Decoding a Source Block . . . . . . . . . . . . . . . Random Numbers . . . . . . . . . . . . . . . . . . . . . . The Table V0 . . . . . . . . . . . . . . . . . . . . . The Table V1 . . . . . . . . . . . . . . . . . . . . . Systematic Indices J(K) . . . . . . . . . . . . . . . . . Security Considerations . . . . . . . . . . . . . . . . . . . IANA Considerations . . . . . . . . . . . . . . . . . . . . . Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . References . . . . . . . . . . . . . . . . . . . . . . . . . . Normative References . . . . . . . . . . . . . . . . . . . Informative References . . . . . . . . . . . . . . . . . . 44Luby, et al. Standards Track [Page 2]

---

RFC Raptor FEC Scheme October Introduction This document specifies an FEC Scheme for the Raptor forward error correction code for object delivery applications. The concept of an FEC Scheme is defined in [RFC] and this document follows the format prescribed there and uses the terminology of that document. Raptor Codes were introduced in [Raptor]. For an overview, see, for example, [CCNC]. The Raptor FEC Scheme is a Fully-Specified FEC Scheme corresponding to FEC Encoding ID 1. Raptor is a fountain code, i.e., as many encoding symbols as needed can be generated by the encoder on-the-fly from the source symbols of a block. The decoder is able to recover the source block from any set of encoding symbols only slightly more in number than the number of source symbols. The code described in this document is a systematic code, that is, the original source symbols can be sent unmodified from sender to receiver, as well as a number of repair symbols. For more background on the use of Forward Error Correction codes in reliable multicast, see [RFC]. The code described here is identical to that described in [MBMS]. 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 [RFC]. 3. Formats and Codes 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Source Block Number | Encoding Symbol ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 1: FEC Payload ID format Luby, et al. Standards Track [Page 3]

---

RFC Raptor FEC Scheme October Source Block Number (SBN), (16 bits): An integer identifier for the source block that the encoding symbols within the packet relate to. Encoding Symbol ID (ESI), (16 bits): An integer identifier for the encoding symbols within the packet. The interpretation of the Source Block Number and Encoding Symbol Identifier is defined in Section 5. FEC Object Transmission Information (OTI) Mandatory The value of the FEC Encoding ID MUST be 1 (one), as assigned by IANA (see Section 7). Common The Common FEC Object Transmission Information elements used by this FEC Scheme are: - Transfer Length (F) - Encoding Symbol Length (T) The Transfer Length is a non-negative integer less than 2^^ The Encoding Symbol Length is a non-negative integer less than 2^^ The encoded Common FEC Object Transmission Information 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 | + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | Reserved | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Encoding Symbol Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 2: Encoded Common FEC OTI for Raptor FEC Scheme NOTE 1: The limit of 2^^45 on the transfer length is a consequence of the limitation on the symbol size to 2^^, the limitation on the number of symbols in a source block to 2^^13, and the Luby, et al. Standards Track [Page 4]

---

RFC Raptor FEC Scheme October limitation on the number of source blocks to 2^^ However, the Transfer Length is encoded as a bit field for simplicity. Scheme-Specific The following parameters are carried in the Scheme-Specific FEC Object Transmission Information element for this FEC Scheme: - The number of source blocks (Z) - The number of sub-blocks (N) - A symbol alignment parameter (Al) These parameters are all non-negative integers. The encoded Scheme- specific Object Transmission Information is a 4-octet field consisting of the parameters Z (2 octets), N (1 octet), and Al (1 octet) 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 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. Procedures Content Delivery Protocol Requirements This section describes the information exchange between the Raptor FEC Scheme and any Content Delivery Protocol (CDP) that makes use of the Raptor FEC Scheme for object delivery. The Raptor encoder and decoder for object delivery require the following information from the CDP: - The transfer length of the object, F, in bytes Luby, et al. Standards Track [Page 5]

---

RFC Raptor FEC Scheme October - A symbol alignment parameter, Al - The symbol size, T, in bytes, which MUST be a multiple of Al - The number of source blocks, Z - The number of sub-blocks in each source block, N The Raptor encoder for object delivery additionally requires: - the object to be encoded, F bytes The Raptor encoder supplies the CDP with the following information for each packet to be sent: - Source Block Number (SBN) - Encoding Symbol ID (ESI) - Encoding symbol(s) The CDP MUST communicate this information to the receiver. 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: - F the transfer length of the object, in bytes - W a target on the sub-block size, in bytes - P the maximum packet payload size, in bytes, which is assumed to be a multiple of Al - Al the symbol alignment parameter, in bytes - Kmax the maximum number of source symbols per source block. Note: Section defines Kmax to be - Kmin a minimum target on the number of symbols per source block - Gmax a maximum target number of symbols per packet Luby, et al. Standards Track [Page 6]

---

RFC Raptor FEC Scheme October Based on the above inputs, the transport parameters T, Z, and N are calculated as follows: Let G = min{ceil(P*Kmin/F), P/Al, Gmax} T = floor(P/(Al*G))*Al Kt = ceil(F/T) Z = ceil(Kt/Kmax) N = min{ceil(ceil(Kt/Z)*T/W), T/Al} The value G represents the maximum number of symbols to be transported in a single packet. The value Kt is the total number of symbols required to represent the source data of the object. The values of G and N derived above should be considered as lower bounds. It may be advantageous to increase these values, for example, to the nearest power of two. In particular, the above algorithm does not guarantee that the symbol size, T, divides the maximum packet size, P, and so it may not be possible to use the packets of size exactly P. If, instead, G is chosen to be a value that divides P/Al, then the symbol size, T, will be a divisor of P and packets of size P can be used. The algorithm above and that defined in Section ensure that the sub-symbol sizes are a multiple of the symbol alignment parameter, Al. This is useful because the XOR operations used for encoding and decoding are generally performed several bytes at a time, for example, at least 4 bytes at a time on a bit processor. Thus, the encoding and decoding can be performed faster if the sub- symbol sizes are a multiple of this number of bytes. Recommended settings for the input parameters, Al, Kmin, and Gmax are as follows: Al = 4, Kmin = , Gmax = The parameter W 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 W depends on the implementation, but it is possible to implement decoding using working memory only slightly larger than W. Luby, et al. Standards Track [Page 7]

---

RFC Raptor FEC Scheme October Raptor FEC Code Specification Definitions, Symbols, and Abbreviations Definitions For the purposes of this specification, the following terms and definitions apply. Source block: a block of K source symbols that are considered together for Raptor encoding purposes. Source symbol: the smallest unit of data used during the encoding process. All source symbols within a source block have the same size. Encoding symbol: a symbol that is included in a data packet. The encoding symbols consist of the source symbols and the repair symbols. Repair symbols generated from a source block have the same size as the source symbols of that source block. Systematic code: a code in which all the source symbols may be included as part of the encoding symbols sent for a source block. Repair symbol: the encoding symbols sent for a source block that are not the source symbols. The repair symbols are generated based on the source symbols. Intermediate symbols: symbols generated from the source symbols using an inverse encoding process . 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 included in data packets. Symbol: a unit of data. The size, in bytes, of a symbol is known as the symbol size. Encoding symbol group: a group of encoding symbols that are sent together, i.e., within the same packet whose relationship to the source symbols can be derived from a single Encoding Symbol ID. Encoding Symbol ID: information that defines the relationship between the symbols of an encoding symbol group and the source symbols. Encoding packet: data packets that contain encoding symbols Luby, et al. Standards Track [Page 8]

---

RFC Raptor FEC Scheme October Sub-block: a source block is sometimes broken into sub-blocks, each of which is sufficiently small to be decoded in working memory. For a source block consisting of K source symbols, each sub-block consists of K sub-symbols, each symbol of the source block being composed of one sub-symbol from each sub-block. Sub-symbol: part of a symbol. Each source symbol is composed of as many sub-symbols as there are sub-blocks in the source block. Source packet: data packets that contain source symbols. Repair packet: data packets that contain repair symbols. Symbols i, j, x, h, a, b, d, v, m represent positive integers. ceil(x) denotes the smallest positive integer that is greater than or equal to x. choose(i,j) denotes the number of ways j objects can be chosen from among i objects without repetition. floor(x) denotes the largest positive integer that is less than or equal to x. i % j denotes i modulo j. X ^ Y denotes, for equal-length bit strings X and Y, the bitwise exclusive-or of X and Y. Al denotes a symbol alignment parameter. Symbol and sub-symbol sizes are restricted to be multiples of Al. A denotes a matrix over GF(2). Transpose[A] denotes the transposed matrix of matrix A. A^^-1 denotes the inverse matrix of matrix A. K denotes the number of symbols in a single source block. Kmax denotes the maximum number of source symbols that can be in a single source block. Set to L denotes the number of pre-coding symbols for a single source block. Luby, et al. Standards Track [Page 9]

---

RFC Raptor FEC Scheme October S denotes the number of LDPC symbols for a single source block. H denotes the number of Half symbols for a single source block. C denotes an array of intermediate symbols, C[0], C[1], C[2],, C[L-1]. C' denotes an array of source symbols, C'[0], C'[1], C'[2],, C'[K-1]. X a non-negative integer value V0, V1 two arrays of 4-byte integers, V0[0], V0[1],, V0[] and V1[0], V1[1],, V1[] Rand[X, i, m] a pseudo-random number generator Deg[v] a degree generator LTEnc[K, C ,(d, a, b)] a LT encoding symbol generator Trip[K, X] a triple generator function G the number of symbols within an encoding symbol group GF(n) the Galois field with n elements. N the number of sub-blocks within a source block T the symbol size in bytes. If the source block is partitioned into sub-blocks, then T = T'*N. T' the sub-symbol size, in bytes. If the source block is not partitioned into sub-blocks, then T' is not relevant. F the transfer length of an object, in bytes I the sub-block size in bytes P for object delivery, the payload size of each packet, in bytes, that is used in the recommended derivation of the object delivery transport parameters. Q Q = , i.e., Q is the largest prime smaller than 2^^16 Z the number of source blocks, for object delivery J(K) the systematic index associated with K Luby, et al. Standards Track [Page 10]

---

RFC Raptor FEC Scheme October I_S denotes the SxS identity matrix. 0_SxH denotes the SxH zero matrix. a ^^ b a raised to the power b Abbreviations For the purposes of the present document, the following abbreviations apply: ESI Encoding Symbol ID LDPC Low Density Parity Check LT Luby Transform SBN Source Block Number SBL Source Block Length (in units of symbols) Overview The principal component of the systematic Raptor code is the basic encoder described in Section First, it is described how to derive values for a set of intermediate symbols from the original source symbols such that knowledge of the intermediate symbols is sufficient to reconstruct the source symbols. Secondly, the encoder produces repair symbols, which are each the exclusive OR of a number of the intermediate symbols. The encoding symbols are the combination of the source and repair symbols. The repair symbols are produced in such a way that the intermediate symbols, and therefore also the source symbols, can be recovered from any sufficiently large set of encoding symbols. This document specifies the systematic Raptor code encoder. A number of possible decoding algorithms are possible. An efficient decoding algorithm is provided in Section The construction of the intermediate and repair symbols is based in part on a pseudo-random number generator described in Section This generator is based on a fixed set of random numbers that MUST be available to both sender and receiver. These are provided in Section Luby, et al. Standards Track [Page 11]

---

RFC Raptor FEC Scheme October Finally, the construction of the intermediate symbols from the source symbols is governed by a 'systematic index', values of which are provided in Section for source block sizes from 4 source symbols to Kmax = source symbols. Object Delivery Source Block Construction General In order to apply the Raptor encoder to a source object, the object may be broken into Z >= 1 blocks, known as source blocks. The Raptor encoder is applied independently to each source block. Each source block is identified by a unique integer 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 bytes each. Each source symbol is identified by a unique integer 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 below. 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: - F the transfer length of the object, in bytes - Al a symbol alignment parameter, in bytes - T the symbol size, in bytes, which MUST be a multiple of Al - Z the number of source blocks Luby, et al. Standards Track [Page 12]

---

RFC Raptor FEC Scheme October - N the number of sub-blocks in each source block These parameters MUST be set so that ceil(ceil(F/T)/Z) <= Kmax. Recommendations for derivation of these parameters are provided in Section The function Partition[] takes a pair of integers (I, J) as input and derives four integers (IL, IS, JL, JS) as output. Specifically, the value of Partition[I, J] is a sequence of four integers (IL, IS, JL, JS), where IL = ceil(I/J), IS = floor(I/J), JL = I - IS * J, and JS = J - JL. Partition[] derives parameters for partitioning a block of size I into J approximately equal-sized blocks. Specifically, JL blocks of length IL and JS blocks of length IS. The source object MUST be partitioned into source blocks and sub- blocks as follows: Let Kt = ceil(F/T) (KL, KS, ZL, ZS) = Partition[Kt, Z] (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 length KL*T bytes, and the remaining ZS source blocks each having KS*T bytes. If Kt*T > F, then for encoding purposes, the last symbol MUST be padded at the end with Kt*T - F zero bytes. Next, each source block 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 and the remaining NS sub-blocks each consisting of K contiguous sub-symbols of size of TS*Al. The symbol alignment parameter Al ensures that sub-symbols are always a multiple of Al bytes. Finally, the m-th symbol of a source block consists of the concatenation of the m-th sub-symbol from each of the N sub-blocks. Note that this implies that when N > 1, then a symbol is NOT a contiguous portion of the object. Luby, et al. Standards Track [Page 13]

---

RFC Raptor FEC Scheme October Encoding Packet Construction Each encoding packet contains the following information: - Source Block Number (SBN) - Encoding Symbol ID (ESI) - encoding symbol(s) Each source block is encoded independently of the others. 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 symbols in the source block. Encoding Symbol IDs from K onwards identify repair symbols. Each encoding packet either consists entirely of source symbols (source packet) or entirely of 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 bytes added for FEC encoding purposes, then these bytes need not be included in the packet. Otherwise, only whole symbols MUST be included. 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. Associated with each symbol is a triple of integers (d, a, b). The G repair symbol triples (d[0], a[0], b[0]),, (d[G-1], a[G-1], b[G-1]) for the repair symbols placed into a repair packet with ESI X are computed using the Triple generator defined in Section as follows: Luby, et al. Standards Track [Page 14]

---

RFC Raptor FEC Scheme October For each i = 0, , G-1, (d[i], a[i], b[i]) = Trip[K,X+i] The G repair symbols to be placed in repair packet with ESI X are calculated based on the repair symbol triples, as described in Section , using the intermediate symbols C and the LT encoder LTEnc[K, C, (d[i], a[i], b[i])]. Systematic Raptor Encoder Encoding Overview The systematic Raptor encoder is used to generate repair symbols from a source block that consists of K source symbols. Symbols are the fundamental data units of the encoding and decoding process. For each source block (sub-block), all symbols (sub- symbols) are the same size. The atomic operation performed on symbols (sub-symbols) for both encoding and decoding is the exclusive-or operation. Let C'[0],, C'[K-1] denote the K source symbols. Let C[0],, C[L-1] denote L intermediate symbols. The first step of encoding is to generate a number, L > K, of intermediate symbols from the K source symbols. In this step, K source symbol triples (d[0], a[0], b[0]), , (d[K-1], a[K-1], b[K-1]) are generated using the Trip[] generator as described in Section The K source symbol triples are associated with the K source symbols and are then used to determine the L intermediate symbols C[0],, C[L-1] from the source symbols using an inverse encoding process. This process can be realized by a Raptor decoding process. Certain "pre-coding relationships" MUST hold within the L intermediate symbols. Section describes these relationships and how the intermediate symbols are generated from the source symbols. Once the intermediate symbols have been generated, repair symbols are produced and one or more repair symbols are placed as a group into a single data packet. Each repair symbol group is associated with an Encoding Symbol ID (ESI) and a number, G, of repair symbols. The ESI is used to generate a triple of three integers, (d, a, b) for each repair symbol, again using the Trip[] generator as described in Section Then, each (d,a,b)-triple is used to generate the Luby, et al. Standards Track [Page 15]

---

RFC Raptor FEC Scheme October corresponding repair symbol from the intermediate symbols using the LTEnc[K, C[0],, C[L-1], (d,a,b)] generator described in Section First Encoding Step: Intermediate Symbol Generation General The first 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]. 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 triples. The generation of the source symbol triples is defined in Section using the Trip[] generator described in Section 2. A set of pre-coding relationships hold within the intermediate symbols themselves. These are defined in Section The generation of the L intermediate symbols is then defined in Section Source Symbol Triples Each of the K source symbols is associated with a triple (d[i], a[i], b[i]) for 0 <= i < K. The source symbol triples are determined using the Triple generator defined in Section as: For each i, 0 <= i < K (d[i], a[i], b[i]) = Trip[K, i] Pre-Coding Relationships The pre-coding relationships amongst the L intermediate symbols are defined by expressing the last L-K intermediate symbols in terms of the first K intermediate symbols. The last L-K intermediate symbols C[K],,C[L-1] consist of S LDPC symbols and H Half symbols The values of S and H are determined from K as described below. Then L = K+S+H. Luby, et al. Standards Track [Page 16]

---

RFC Raptor FEC Scheme October Let X be the smallest positive integer such that X*(X-1) >= 2*K. S be the smallest prime integer such that S >= ceil(*K) + X H be the smallest integer such that choose(H,ceil(H/2)) >= K + S H' = ceil(H/2) L = K+S+H C[0],,C[K-1] denote the first K intermediate symbols C[K],,C[K+S-1] denote the S LDPC symbols, initialised to zero C[K+S],,C[L-1] denote the H Half symbols, initialised to zero The S LDPC symbols are defined to be the values of C[K],,C[K+S-1] at the end of the following process: For i = 0,,K-1 do a = 1 + (floor(i/S) % (S-1)) b = i % S C[K + b] = C[K + b] ^ C[i] b = (b + a) % S C[K + b] = C[K + b] ^ C[i] b = (b + a) % S C[K + b] = C[K + b] ^ C[i] The H Half symbols are defined as follows: Let g[i] = i ^ (floor(i/2)) for all positive integers i Note: g[i] is the Gray sequence, in which each element differs from the previous one in a single bit position m[k] denote the subsequence of g[.] whose elements have exactly k non-zero bits in their binary representation. Luby, et al. Standards Track [Page 17]

---

RFC Raptor FEC Scheme October m[j,k] denote the jth element of the sequence m[k], where j=0, 1, 2, Then, the Half symbols are defined as the values of C[K+S],,C[L-1] after the following process: For h = 0,,H-1 do For j = 0,,K+S-1 do If bit h of m[j,H'] is equal to 1 then C[h+K+S] = C[h+K+S] ^ C[j]. Intermediate Symbols 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'[i] = LTEnc[K, (C[0],, C[L-1]), (d[i], a[i], b[i])], for all i, 0 <= i < K. 2. The L intermediate symbols C[0], C[1],, C[L-1] satisfy the pre-coding relationships defined in Section Example Method for Calculation of Intermediate Symbols This subsection describes a possible method for calculation of the L intermediate symbols C[0], C[1],, C[L-1] satisfying the constraints in Section The 'generator matrix' for a code that generates N output symbols from K input symbols is an NxK matrix over GF(2), where each row corresponds to one of the output symbols and each column to one of the input symbols and where the ith output symbol is equal to the sum of those input symbols whose column contains a non-zero entry in row i. Luby, et al. Standards Track [Page 18]

---

RFC Raptor FEC Scheme October Then, the L intermediate symbols can be calculated as follows: Let C denote the column vector of the L intermediate symbols, C[0], C[1],, C[L-1]. 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 LxL matrix over GF(2), A, such that: A*C = D The matrix A can be constructed as follows: Let: G_LDPC be the S x K generator matrix of the LDPC symbols. So, G_LDPC * Transpose[(C[0],, C[K-1])] = Transpose[(C[K], , C[K+S-1])] G_Half be the H x (K+S) generator matrix of the Half symbols, So, G_Half * Transpose[(C[0], , C[S+K-1])] = Transpose[(C[K+S], , C[K+S+H-1])] I_S be the S x S identity matrix I_H be the H x H identity matrix 0_SxH be the S x H zero matrix G_LT be the KxL generator matrix of the encoding symbols generated by the LT Encoder. So, G_LT * Transpose[(C[0], , C[L-1])] = Transpose[(C'[0],C'[1],,C'[K-1])] i.e., G_LT(i,j) = 1 if and only if C[j] is included in the symbols that are XORed to produce LTEnc[K, (C[0], , C[L-1]), (d[i], a[i], b[i])]. Then: The first S rows of A are equal to G_LDPC | I_S | 0_SxH. Luby, et al. Standards Track [Page 19]

---

RFC Raptor FEC Scheme October The next H rows of A are equal to G_Half | I_H. The remaining K rows of A are equal to G_LT. This calculation can be realized by applying a Raptor 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 be used. The source symbol triples are designed to facilitate efficient decoding of the source symbols using that algorithm. Second Encoding Step: LT Encoding In the second encoding step, the repair symbol with ESI X is generated by applying the generator LTEnc[K, (C[0], C[1],, C[L-1]), (d, a, b)] defined in Section to the L intermediate symbols C[0], C[1],, C[L-1] using the triple (d, a, b)=Trip[K,X] generated according to Section Luby, et al. Standards Track [Page 20]

---

RFC Raptor FEC Scheme October Generators Random Generator The random number generator Rand[X, i, m] is defined as follows, where X is a non-negative integer, i is a non-negative integer, and m is a positive integer and the value produced is an integer between 0 and m Let V0 and V1 be arrays of entries each, where each entry is a 4-byte unsigned integer. These arrays are provided in Section Then, Rand[X, i, m] = (V0[(X + i) % ] ^ V1[(floor(X/)+ i) % ]) % m Degree Generator The degree generator Deg[v] is defined as follows, where v is an integer that is at least 0 and less than 2^^20 = In Table 1, find the index j such that f[j-1] <= v < f[j] Then, Deg[v] = d[j] ++++ | Index j | f[j] | d[j] | ++++ | 0 | 0 | -- | | 1 | | 1 | | 2 | | 2 | | 3 | | 3 | | 4 | | 4 | | 5 | | 10 | | 6 | | 11 | | 7 | | 40 | ++++ Table 1: Defines the degree distribution for encoding symbols LT Encoding Symbol Generator The encoding symbol generator LTEnc[K, (C[0], C[1],, C[L-1]), (d, a, b)] takes the following inputs: Luby, et al. Standards Track [Page 21]

---

RFC Raptor FEC Scheme October K is the number of source symbols (or sub-symbols) for the source block (sub-block). Let L be derived from K as described in Section , and let L' be the smallest prime integer greater than or equal to L. (C[0], C[1],, C[L-1]) is the array of L intermediate symbols (sub-symbols) generated as described in Section (d, a, b) is a source triple determined using the Triple generator defined in Section , whereby d is an integer denoting an encoding symbol degree a is an integer between 1 and L'-1 inclusive b is an integer between 0 and L'-1 inclusive The encoding symbol generator produces a single encoding symbol as output, according to the following algorithm: While (b >= L) do b = (b + a) % L' Let result = C[b]. For j = 1,,min(d-1,L-1) do b = (b + a) % L' While (b >= L) do b = (b + a) % L' result = result ^ C[b] Return result Triple Generator The triple generator Trip[K,X] takes the following inputs: K - The number of source symbols X - An encoding symbol ID Let L be determined from K as described in Section L' be the smallest prime that is greater than or equal to L Luby, et al. Standards Track [Page 22]

---

RFC Raptor FEC Scheme October Q = , the largest prime smaller than 2^^ J(K) be the systematic index associated with K, as defined in Section The output of the triple generator is a triple, (d, a, b) determined as follows: A = ( + J(K)*) % Q B = *(J(K)+1) % Q Y = (B + X*A) % Q v = Rand[Y, 0, 2^^20] d = Deg[v] a = 1 + Rand[Y, 1, L'-1] b = Rand[Y, 2, L'] Example FEC Decoder General This section describes an efficient decoding algorithm for the Raptor codes described in this specification. Note that each received encoding symbol can be considered as the value of an equation amongst the intermediate symbols. From these simultaneous equations, and the known pre-coding relationships amongst the intermediate symbols, any algorithm for solving simultaneous 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. Decoding a Source Block 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. From the algorithms described in Section , the Raptor decoder can calculate the total number L = K+S+H of pre-coding symbols and determine how they were generated from the source block to be decoded. In this description, it is assumed that the received Luby, et al. Standards Track [Page 23]

---

RFC Raptor FEC Scheme October encoding symbols for the source block to be decoded are passed to the decoder. Note that, as described in Section , the last source symbol of a source packet may have included padding bytes added for FEC encoding purposes. These padding bytes may not be actually included in the packet sent and so must be reinserted at the received before passing the symbol to the decoder. For each such encoding symbol, it is assumed that the number and set of intermediate symbols whose exclusive-or is equal to the encoding symbol is also passed to the decoder. In the case of source symbols, the source symbol triples described in Section 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 for a source block and let M = S+H+N. The following M by L bit matrix A can be derived from the information passed to the decoder for the source block to be decoded. Let C be the column vector of the L intermediate symbols, and let D be the column vector of M symbols with values known to the receiver, where the first S+H of the M symbols are zero-valued symbols that correspond to LDPC and Half symbols (these are check symbols for the LDPC and Half symbols, and not the LDPC and Half symbols themselves), and the remaining N of the M symbols are the received encoding symbols for the source block. Then, A is the bit matrix that satisfies A*C = D, where here * denotes matrix multiplication over GF[2]. In particular, A[i,j] = 1 if the intermediate symbol corresponding to index j is exclusive-ORed into the LDPC, Half, or encoding symbol corresponding to index i in the encoding, or if index i corresponds to a LDPC or Half symbol and index j corresponds to the same LDPC or Half symbol. For all other i and j, A[i,j] = 0. Decoding a 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 over GF[2] is L. Once C has been decoded, missing source symbols can be obtained by using the source symbol triples to determine the number and set of intermediate symbols that MUST be exclusive-ORed 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 by L identity matrix. The decoding schedule consists of the sequence of row operations and row and column reorderings during the Gaussian elimination process, and only depends on A and not on D. 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. Luby, et al. Standards Track [Page 24]

---

RFC Raptor FEC Scheme October 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. - Each time row i of A is exclusive-ORed into row i' in the decoding schedule, then in the decoding process, symbol D[d[i]] is exclusive-ORed into symbol D[d[i']]. - 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']. - 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 exclusive-ORs of symbols in the decoding of the source block is the number of row operations (not exchanges) in the Gaussian elimination. Since A is the L by 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. First Phase The first phase of the Gaussian elimination, the matrix A, is conceptually partitioned into submatrices. The submatrix sizes are parameterized by non-negative integers i and u, which are initialized to 0. 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. Luby, et al. Standards Track [Page 25]

---

RFC Raptor FEC Scheme October (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 5 illustrates the submatrices of A. At the beginning of the first phase, V = A. In each step, a row of A is chosen. ++++ | | | | | I | All Zeros | | | | | | +++ U | | | | | | | | | | All Zeros | V | | | | | | | | | | ++++ Figure 5: 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 ones in V 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 (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-zeroes submatrix above V have disappeared and A consists of I, the all zeroes submatrix below I, and U. The phase ends unsuccessfully in decoding failure if, at some step before V disappears, there is no non-zero row in V to choose in that step. Whenever there are non- zero rows in V, then the next step starts by choosing a row of A as follows: Luby, et al. Standards Track [Page 26]

---

RFC Raptor FEC Scheme October o Let r be the minimum integer such that at least one row of A has exactly r ones in V. * If r != 2, then choose a row with exactly r ones in V with minimum original degree among all such rows. * If r = 2, then choose any row with exactly 2 ones in V that is part of a maximum size component in the graph defined by 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 ones in the chosen row appears in the first column of V and so that the remaining r-1 ones appear in the last columns of V. Then, the chosen row is exclusive-ORed into all the other rows of A below the chosen row that have a one in the first column of V. Finally, i is incremented by 1 and u is incremented by r-1, which completes the step. Second Phase 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 to either 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 by 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. Third Phase After the second phase, the only portion of A that needs to be zeroed out to finish converting A into the L by 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. To zero out U_upper efficiently, the following precomputation matrix U' is computed based on I_u in the third phase and then U' is used in the fourth phase to zero out U_upper. The u rows of Iu are partitioned into ceil(u/8) groups of 8 rows each. Then, for each group of 8 rows, all non-zero combinations of the 8 rows are computed, resulting in 2^^8 - 1 = rows (this can be done with 2^^ = exclusive-ors of rows per group, since the combinations of Hamming weight one that appear in I_u do not need to be recomputed). Thus, the resulting precomputation matrix U' has ceil(u/8)* rows and u columns. Note that U' is not formally a part of matrix A, but will be used in the fourth phase to zero out U_upper. Luby, et al. Standards Track [Page 27]

---

RFC Raptor FEC Scheme October Fourth Phase For each of the first i rows of A, for each group of 8 columns in the U_upper submatrix of this row, if the set of 8 column entries in U_upper are not all zero, then the row of the precomputation matrix U' that matches the pattern in the 8 columns is exclusive-ORed into the row, thus zeroing out those 8 columns in the row at the cost of exclusive-ORing one row of U' into the row. After this phase, A is the L by L identity matrix and a complete decoding schedule has been successfully formed. Then, as explained in Section , the corresponding decoding consisting of exclusive-ORing known encoding symbols can be executed to recover the intermediate symbols based on the decoding schedule. The triples associated with all source symbols are computed according to Section The triples for received source symbols are used in the decoding. The triples for missing source symbols are used to determine which intermediate symbols need to be exclusive-ORed to recover the missing source symbols. Random Numbers The two tables V0 and V1 described in Section are given below. Each entry is a bit integer in decimal representation. The Table V0Luby, et al. Standards Track [Page 28]

---

RFC Raptor FEC Scheme October The Table V1Luby, et al. Standards Track [Page 29]

---

RFC Raptor FEC Scheme October Systematic Indices J(K) For each value of K, the systematic index J(K) is designed to have the property that the set of source symbol triples (d[0], a[0], b[0]), , (d[L-1], a[L-1], b[L-1]) are such that the L intermediate symbols are uniquely defined, i.e., the matrix A in Section has full rank and is therefore invertible. The following is the list of the systematic indices for values of K between 4 and inclusive. 18, 14, 61, 46, 14, 22, 20, 40, 48, 1, 29, 40, 43, 46, 18, 8, 20, 2, 61, 26, 13, 29, 36, 19, 58, 5, 58, 0, 54, 56, 24, 14, 5, 67, 39, 31, 25, 29, 24, 19, 14, 56, 49, 49, 63, 30, 4, 39, 2, 1, 20, 19, 61, 4, 54, 70, 25, 52, 9, 26, 55, 69, 27, 68, 75, 19, 64, 57, 45, 3, 37, 31, , 41, 25, 41, 53, 23, 9, 31, 26, 30, 30, 46, 90, 50, 13, 90, 77, 61, 31, 54, 54, 3, 21, 66, 21, 11, 23, 11, 29, 21, 7, 1, 27, 4, 34, 17, 85, 69, 17, 75, 93, 57, 0, 53, 71, 88, , 88, 90, 22, 0, 58, 41, 22, 96, 26, 79, , 19, 3, 81, 72, 50, 0, 32, 79, 28, 25, 12, Luby, et al. Standards Track [Page 30]

---

RFC Raptor FEC Scheme October Luby, et al. Standards Track [Page 31]

---

RFC Raptor FEC Scheme October Luby, et al. Standards Track [Page 32]

---

RFC Raptor FEC Scheme October Luby, et al. Standards Track [Page 33]

---

RFC Raptor FEC Scheme October Luby, et al. Standards Track [Page 34]

---

RFC Raptor FEC Scheme October Luby, et al. Standards Track [Page 35]

---

RFC Raptor FEC Scheme October

[Docs] [txt|pdf] [draft-ietf-rmt] [Tracker] [Diff1] [Diff2] [IPR] [Errata]

PROPOSED STANDARD
Errata Exist
Internet Engineering Task Force (IETF) M. Luby Request for Comments: Qualcomm Incorporated Category: Standards Track A. Shokrollahi ISSN: EPFL M. Watson Netflix Inc. T. Stockhammer Nomor Research L. Minder Qualcomm Incorporated August 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 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 Luby, et al. Standards Track [Page 1]

---

RFC RaptorQ FEC Scheme August Information about the current status of this document, any errata, and how to provide feedback on it may be obtained at manicapital.com Copyright Notice Copyright (c) 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 (manicapital.com) 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 RaptorQ FEC Scheme August Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . Requirements Notation . . . . . . . . . . . . . . . . . . . . Formats and Codes . . . . . . . . . . . . . . . . . . . . . . Introduction . . . . . . . . . . . . . . . . . . . . . . . FEC Payload IDs . . . . . . . . . . . . . . . . . . . . . FEC Object Transmission Information . . . . . . . . . . . Mandatory . . . . . . . . . . . . . . . . . . . . . . Common . . . . . . . . . . . . . . . . . . . . . . . . Scheme-Specific . . . . . . . . . . . . . . . . . . . Procedures . . . . . . . . . . . . . . . . . . . . . . . . . . Introduction . . . . . . . . . . . . . . . . . . . . . . . Content Delivery Protocol Requirements . . . . . . . . . . Example Parameter Derivation Algorithm . . . . . . . . . . Object Delivery . . . . . . . . . . . . . . . . . . . . . Source Block Construction . . . . . . . . . . . . . . Encoding Packet Construction . . . . . . . . . . . . . Example Receiver Recovery Strategies . . . . . . . . . RaptorQ FEC Code Specification . . . . . . . . . . . . . . . . Background . . . . . . . . . . . . . . . . . . . . . . . . Definitions . . . . . . . . . . . . . . . . . . . . . Symbols . . . . . . . . . . . . . . . . . . . . . . . Overview . . . . . . . . . . . . . . . . . . . . . . . . . Systematic RaptorQ Encoder . . . . . . . . . . . . . . . . Introduction . . . . . . . . . . . . . . . . . . . . . Encoding Overview . . . . . . . . . . . . . . . . . . 19 First Encoding Step: Intermediate Symbol Generation . 21 Second Encoding Step: Encoding . . . . . . . . . . . . Generators . . . . . . . . . . . . . . . . . . . . . . Example FEC Decoder . . . . . . . . . . . . . . . . . . . General . . . . . . . . . . . . . . . . . . . . . . . Decoding an Extended Source Block . . . . . . . . . . Random Numbers . . . . . . . . . . . . . . . . . . . . . . The Table V0 . . . . . . . . . . . . . . . . . . . . . The Table V1 . . . . . . . . . . . . . . . . . . . . . The Table V2 . . . . . . . . . . . . . . . . . . . . . The Table V3 . . . . . . . . . . . . . . . . . . . . . Systematic Indices and Other Parameters . . . . . . . . . Operating with Octets, Symbols, and Matrices . . . . . . . General . . . . . . . . . . . . . . . . . . . . . . . Arithmetic Operations on Octets . . . . . . . . . . . The Table OCT_EXP . . . . . . . . . . . . . . . . . . The Table OCT_LOG . . . . . . . . . . . . . . . . . . Operations on Symbols . . . . . . . . . . . . . . . . Operations on Matrices . . . . . . . . . . . . . . . . Requirements for a Compliant Decoder . . . . . . . . . . . Security Considerations . . . . . . . . . . . . . . . . . . . 66Luby, et al. Standards Track [Page 3]

---

RFC RaptorQ FEC Scheme August IANA Considerations . . . . . . . . . . . . . . . . . . . . . Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . References . . . . . . . . . . . . . . . . . . . . . . . . . . Normative References . . . . . . . . . . . . . . . . . . . Informative References . . . . . . . . . . . . . . . . . . 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 [RFC], 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 [RFC]. The RaptorQ code provides superior reliability, better coding efficiency, and support for larger source block sizes than the Raptor code of RFC [RFC]. These improvements simplify the usage of the RaptorQ code in an object delivery Content Delivery Protocol compared to RFC RFC [RFC]. 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 [RFC]. 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 [RFC]. Luby, et al. Standards Track [Page 4]

---

RFC RaptorQ FEC Scheme August Formats and Codes Introduction The octet order of all fields is network byte order, i.e., big- endian. 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): 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. FEC Object Transmission Information Mandatory The value of the FEC Encoding ID MUST be 6, as assigned by IANA (see Section 7). Common The Common FEC Object Transmission Information elements used by this FEC scheme are: o Transfer Length (F): bit unsigned integer. A non-negative integer that is at most This is the transfer length of the object in units of octets. o Symbol Size (T): bit unsigned integer. A positive integer that is less than 2^^ This is the size of a symbol in units of octets. Luby, et al. Standards Track [Page 5]

---

RFC RaptorQ FEC Scheme August 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 on the transfer length is a consequence of the limitation on the symbol size to 2^^, the limitation on the number of symbols in a source block to , and the limitation on the number of source blocks to 2^^8. 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): 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 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 Luby, et al. Standards Track [Page 6]

---

RFC RaptorQ FEC Scheme August Procedures Introduction For any undefined symbols or functions used in this section, in particular the functions "ceil" and "floor", refer to Section 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: - 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. 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 RaptorQ FEC Scheme August 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 defines K'_max to be 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 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 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 RaptorQ FEC Scheme August time, for example, at least 4 octets at a time on a 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. Object Delivery Source Block Construction 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 below. 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 RaptorQ FEC Scheme August 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 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 RaptorQ FEC Scheme August 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. 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 RaptorQ FEC Scheme August 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 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 RaptorQ FEC Scheme August finite fields GF[2] and GF[] 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. 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 RaptorQ FEC Scheme August 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 , 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 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 RaptorQ FEC Scheme August 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 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 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 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 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 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 Luby, et al. Standards Track [Page 15]

---

RFC RaptorQ FEC Scheme August 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 , 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 , 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 bit unsigned integers, V0[0], V0[1], , V0[]; V1[0], V1[1], , V1[]; V2[0], V2[1], , V2[]; and V3[0], V3[1], , V3[] as shown in Section 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 RaptorQ FEC Scheme August 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. 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 The basic encoder is described in Section 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 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 A number of decoding algorithms are possible to achieve these requirements. An efficient decoding algorithm to achieve these requirements is provided in Section The construction of the intermediate and repair symbols is based in part on a pseudo-random number generator described in Section This generator is based on a fixed set of random numbers that must be available to both sender and receiver. These numbers are Luby, et al. Standards Track [Page 17]

---

RFC RaptorQ FEC Scheme August provided in Section Encoding and decoding operations for RaptorQ use operations on octets. Section 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 for specific extended source block sizes between 6 and K'_max = source symbols. Thus, the RaptorQ code supports source blocks with between 1 and source symbols. Systematic RaptorQ Encoder 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 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 RaptorQ FEC Scheme August 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. 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 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 that is greater than or equal to K. Luby, et al. Standards Track [Page 19]

---

RFC RaptorQ FEC Scheme August , 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 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 RaptorQ FEC Scheme August Certain "pre-coding relationships" must hold within the L intermediate symbols. Section describes these relationships. Section 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 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 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]. First Encoding Step: Intermediate Symbol Generation 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 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 using the Tuple[] generator as described in Section 2. A number of pre-coding relationships hold within the intermediate symbols themselves. These are defined in Section The generation of the L intermediate symbols is then defined in Section 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 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 RaptorQ FEC Scheme August 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 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 RaptorQ FEC Scheme August 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 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 RaptorQ FEC Scheme August Let o alpha denote the octet represented by integer 2 as defined in Section 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 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. Intermediate Symbols 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 , and Enc[] is described in Section Luby, et al. Standards Track [Page 24]

---

RFC RaptorQ FEC Scheme August 2. The L intermediate symbols C[0], C[1], , C[L-1] satisfy the pre-coding relationships defined in Section 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 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 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 RaptorQ FEC Scheme August 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. 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 be used. Luby, et al. Standards Track [Page 26]

---

RFC RaptorQ FEC Scheme August 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 to the L intermediate symbols C[0], C[1], , C[L-1] using the tuple (d, a, b, d1, a1, b1)=Tuple[K',X]. Generators 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 , and m is a positive integer, and the value produced is an integer between 0 and m Let V0, V1, V2, and V3 be the arrays provided in Section 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 Degree Generator The degree generator Deg[v] is defined as follows, where v is a non- negative integer that is less than 2^^20 = 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 Luby, et al. Standards Track [Page 27]

---

RFC RaptorQ FEC Scheme August 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 Luby, et al. Standards Track [Page 28]

---

RFC RaptorQ FEC Scheme August o (C[0], C[1], , C[L-1]) is the array of L intermediate symbols (sub-symbols) generated as described in Section o (d, a, b, d1, a1, b1) is a source tuple determined from ISI X using the Tuple[] generator defined in Section , 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 P inclusive * b1 is a non-negative integer between 0 and P 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, , d 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 RaptorQ FEC Scheme August 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 o J = J(K') be the systematic index associated with K', as defined in Table 2 in Section The output of the tuple generator is a tuple, (d, a, b, d1, a1, b1), determined as follows: o A = + J* o if (A % 2 == 0) { A = A + 1 } o B = *(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, P] o b1 = Rand[X, 5, P1] Example FEC Decoder 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 RaptorQ FEC Scheme August 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. Decoding an Extended Source Block 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 , 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 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 , 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 RaptorQ FEC Scheme August 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. 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 RaptorQ FEC Scheme August 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 RaptorQ FEC Scheme August (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 RaptorQ FEC Scheme August 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 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. 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. 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 RaptorQ FEC Scheme August 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 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. Random Numbers The four arrays V0, V1, V2, and V3 used in Section are provided below. There are entries in each of the four arrays. The indexing into each array starts at 0, and the entries are bit unsigned integers. The Table V0Luby, et al. Standards Track [Page 36]

---

RFC RaptorQ FEC Scheme August The Table V1