Reliable Multicast Transport M. Luby Internet-Draft Qualcomm, Inc. Intended status: Standards Track A. Shokrollahi Expires: February 25, 2010 EPFL M. Watson Qualcomm, Inc. T. Stockhammer Nomor Research August 24, 2009 RaptorG Forward Error Correction Scheme for Object Delivery draft-luby-rmt-bb-fec-raptorg-object-00 Status of this Memo This Internet-Draft is submitted to IETF in full conformance with the provisions of BCP 78 and BCP 79. This document may contain material from IETF Documents or IETF Contributions published or made publicly available before November 10, 2008. The person(s) controlling the copyright in some of this material may not have granted the IETF Trust the right to allow modifications of such material outside the IETF Standards Process. Without obtaining an adequate license from the person(s) controlling the copyright in such materials, this document may not be modified outside the IETF Standards Process, and derivative works of it may not be created outside the IETF Standards Process, except to format it for publication as an RFC or to translate it into languages other than English. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet- Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt. The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html. This Internet-Draft will expire on February 25, 2010. Copyright Notice Luby, et al. Expires February 25, 2010 [Page 1] Internet-Draft RaptorG FEC Scheme August 2009 Copyright (c) 2009 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 in effect on the date of publication of this document (http://trustee.ietf.org/license-info). Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Luby, et al. Expires February 25, 2010 [Page 2] Internet-Draft RaptorG FEC Scheme August 2009 Abstract This document describes a Fully-Specified FEC scheme, corresponding to FEC Encoding ID XXX, for the RaptorG forward error correction code and its application to reliable delivery of data objects. RaptorG codes are a new family of codes to provide superior flexibility, larger source block sizes and better coding efficiency than Raptor codes in RFC5053. RaptorG is also 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 for most cases equal to the number of source symbols and in rare cases with slightly more than the number of source symbols. The RaptorG 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. Expires February 25, 2010 [Page 3] Internet-Draft RaptorG FEC Scheme August 2009 Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4 2. Requirements notation . . . . . . . . . . . . . . . . . . . . . 5 3. Formats and Codes . . . . . . . . . . . . . . . . . . . . . . . 6 3.1. FEC Payload IDs . . . . . . . . . . . . . . . . . . . . . . 6 3.2. FEC Object Transmission Information . . . . . . . . . . . . 6 3.2.1. Mandatory . . . . . . . . . . . . . . . . . . . . . . . 6 3.2.2. Common . . . . . . . . . . . . . . . . . . . . . . . . 6 3.2.3. Scheme-Specific . . . . . . . . . . . . . . . . . . . . 7 4. Procedures . . . . . . . . . . . . . . . . . . . . . . . . . . 9 4.1. Content Delivery Protocol Requirements . . . . . . . . . . 9 4.2. Example parameter derivation algorithm . . . . . . . . . . 9 4.3. Object delivery . . . . . . . . . . . . . . . . . . . . . 10 4.3.1. Source block construction . . . . . . . . . . . . . . 10 4.3.2. Encoding packet construction . . . . . . . . . . . . 12 5. RaptorG FEC code specification . . . . . . . . . . . . . . . 14 5.1. Definitions, Symbols and abbreviations . . . . . . . . . 14 5.1.1. Definitions . . . . . . . . . . . . . . . . . . . . . 14 5.1.2. Symbols . . . . . . . . . . . . . . . . . . . . . . . 15 5.1.3. Abbreviations . . . . . . . . . . . . . . . . . . . . 17 5.2. Overview . . . . . . . . . . . . . . . . . . . . . . . . 17 5.3. Systematic RaptorG encoder . . . . . . . . . . . . . . . 18 5.3.1. Introduction . . . . . . . . . . . . . . . . . . . . 18 5.3.2. Encoding overview . . . . . . . . . . . . . . . . . . 20 5.3.3. First encoding step: Intermediate Symbol Generation . 20 5.3.4. Second encoding step: LT encoding . . . . . . . . . . 28 5.3.5. Generators . . . . . . . . . . . . . . . . . . . . . 28 5.4. Example FEC decoder . . . . . . . . . . . . . . . . . . . 32 5.4.1. General . . . . . . . . . . . . . . . . . . . . . . . 32 5.4.2. Decoding an extended source block . . . . . . . . . . 32 5.5. Random Numbers . . . . . . . . . . . . . . . . . . . . . 38 5.5.1. The table V0 . . . . . . . . . . . . . . . . . . . . 38 5.5.2. The table V1 . . . . . . . . . . . . . . . . . . . . 39 5.5.3. The table V2 . . . . . . . . . . . . . . . . . . . . 40 5.5.4. The table V3 . . . . . . . . . . . . . . . . . . . . 41 5.6. Systematic Indicies J(K') . . . . . . . . . . . . . . . . 42 5.7. Arithmetic in GF(256) . . . . . . . . . . . . . . . . . . 46 5.7.1. Introduction . . . . . . . . . . . . . . . . . . . . 46 5.7.2. The table GF256_EXP . . . . . . . . . . . . . . . . . 46 5.7.3. The table GF256_LOG . . . . . . . . . . . . . . . . . 47 6. Security Considerations . . . . . . . . . . . . . . . . . . . 48 7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 49 8. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 50 9. References . . . . . . . . . . . . . . . . . . . . . . . . . 51 9.1. Normative references . . . . . . . . . . . . . . . . . . 51 9.2. Informative references . . . . . . . . . . . . . . . . . 51 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 52 Luby, et al. Expires February 25, 2010 [Page 4] Internet-Draft RaptorG FEC Scheme August 2009 1. Introduction This document specifies an FEC Scheme for the RaptorG forward error correction code for object delivery applications. The concept of an FEC Scheme is defined in RFC5052 [RFC5052] and this document follows the format prescribed there and uses the terminology of that document. An initial version of a Raptor code was introduced in RFC5053 [RFC5053]. The RaptorG code described herein is a next generation of Raptor code with superior reliability, better coding efficiency, and support for larger source block sizes than the Raptor code of RFC5053 [RFC5053]. These improvements simplify the usage of the RaptorG code in an object delivery Content Delivery Protocol compared to RFC5053 [RFC5053]. The RaptorG FEC Scheme is a Fully-Specified FEC Scheme corresponding to FEC Encoding ID XXX. RaptorG 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 backgound on the use of Forward Error Correction codes in reliable multicast, see [RFC3453]. Luby, et al. Expires February 25, 2010 [Page 5] Internet-Draft RaptorG FEC Scheme August 2009 2. Requirements notation The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in [RFC2119]. Luby, et al. Expires February 25, 2010 [Page 6] Internet-Draft RaptorG FEC Scheme August 2009 3. Formats and Codes 3.1. 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 Source Block Number (SBN), (8 bits): An integer identifier for the source block that the encoding symbols within the packet relate to. Encoding Symbol ID (ESI), (24 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. 3.2. FEC Object Transmission Information 3.2.1. Mandatory The value of the FEC Encoding ID MUST be XXX, as assigned by IANA (see Section 7). 3.2.2. Common The Common FEC Object Transmission Information elements used by this FEC Scheme are: - Transfer Length (F) - Symbol Size (T) The Transfer Length is a non-negative integer that is at most 946287651840, which can be represented by 40 bits. The Symbol Size is a non-negative integer less than 2^^16. The Transfer Length is a field of 40 bits in its definition, and the Symbol Size field is 16 bits, and both length units are bytes. The encoded Common FEC Object Transmission Information format is Luby, et al. Expires February 25, 2010 [Page 7] Internet-Draft RaptorG FEC Scheme August 2009 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 RaptorG FEC Scheme NOTE 1: The limit of 946287651840 on the transfer length is a consequence of the limitation on the symbol size to 2^^16-1, the limitation on the number of symbols in a source block to 56404 and the limitation on the number of source blocks to 2^^8. 3.2.3. Scheme-Specific The following parameters are carried in the Scheme-Specific FEC Object Transmission Information element for this FEC Scheme: o The number of source blocks (Z) o The number of sub-blocks (N) o 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 (12 bits), N (12 bits) and Al (8 bits) 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 14 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 Luby, et al. Expires February 25, 2010 [Page 8] Internet-Draft RaptorG FEC Scheme August 2009 described in Section 4.3.1.2 Luby, et al. Expires February 25, 2010 [Page 9] Internet-Draft RaptorG FEC Scheme August 2009 4. Procedures 4.1. Content Delivery Protocol Requirements This section describes the information exchange between the RaptorG FEC Scheme and any Content Delivery Protocol (CDP) that makes use of the RaptorG FEC Scheme for object delivery. The RaptorG encoder scheme and RaptorG decoder scheme for object delivery require the following information from the CDP: - The transfer length of the object, F, in bytes - 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 RaptorG encoder scheme for object delivery additionally requires: - the object to be encoded, F bytes The RaptorG encoder scheme 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. 4.2. 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 payload size in bytes, which is assumed to be a multiple of Al Luby, et al. Expires February 25, 2010 [Page 10] Internet-Draft RaptorG FEC Scheme August 2009 - Al the symbol alignment parameter, in bytes - K'_max the maximum number of source symbols per source block. Note: Section 5.1.2 defines K'_max to be 56404 Based on the above inputs, the transport parameters T, Z and N are calculated as follows: Let, T = P' Kt = ceil(F/T) Z = ceil(Kt/K'_max) N = min{ceil(ceil(Kt/Z)*T/W), T/Al} It is RECOMMENDED that each packet contains exactly one symbol. However, receivers SHALL support the reception of packets that contain multiple symbols. The value Kt is the total number of symbols required to represent the source data of the object. The algorithm above and that defined in Section 4.3.1.2 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 32 bit processor. Thus the encoding and decoding can be performed faster if the sub- symbol sizes are a multiple of this number of bytes. The recommended settings for the input parameter Al is 4. The parameter W can be used to generate encoded data which 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. 4.3. Object delivery 4.3.1. Source block construction Luby, et al. Expires February 25, 2010 [Page 11] Internet-Draft RaptorG FEC Scheme August 2009 4.3.1.1. General In order to apply the RaptorG encoder to a source object, the object may be broken into Z >= 1 blocks, known as source blocks. The RaptorG 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 a object and the value of T' may not necessarily be the same for each sub-block of a source block. However, the symbol size T is the same for all source blocks of an object and the number of symbols, K is the same for every sub-block of a source block. Exact partitioning of the object into source blocks and sub-blocks is described in Section 4.3.1.2 below. 4.3.1.2. Source block and sub-block partitioning The construction of source blocks and sub-blocks is determined based on five input parameters, F, Al, T, Z and N and a function Partition[]. The five input parameters are defined as follows: - 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 - N the number of sub-blocks in each source block These parameters MUST be set so that ceil(ceil(F/T)/Z) <= K'_max. Recommendations for derivation of these parameters are provided in Section 4.2. 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, Luby, et al. Expires February 25, 2010 [Page 12] Internet-Draft RaptorG FEC Scheme August 2009 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 KL*T bytes, i.e. KL source symbols of T bytes each, and the remaining ZS source blocks each having KS*T bytes, i.e. KS source symbols of T bytes 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 bytes. 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 bytes and the remaining NS sub-blocks each consisting of K contiguous sub-symbols of size of TS*Al bytes. 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. 4.3.2. 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 Luby, et al. Expires February 25, 2010 [Page 13] Internet-Draft RaptorG FEC Scheme August 2009 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 RaptorG encoder. 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. Luby, et al. Expires February 25, 2010 [Page 14] Internet-Draft RaptorG FEC Scheme August 2009 5. RaptorG FEC code specification 5.1. Definitions, Symbols and abbreviations For the purpose of the RaptorG FEC code specification in this section, the following definitions, symbols and abbreviations apply. 5.1.1. Definitions Source block: a block of K source symbols which are considered together for RaptorG encoding and decoding purposes. Extended Source Block: a block of K' source symbols, where K' >= K constructed from a source block and zero or more padding symbols. Symbol: a unit of data. The size, in bytes, of a symbol is known as the symbol size. The symbol size is always an integer. Source symbol: the smallest unit of data used during the encoding process. All source symbols within a source block have the same size. Padding symbol: a symbol with all zero bits that is added to the source block to form the extended source block. 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. 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. 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 sent as part of the encoding of a source block. Systematic code: a code in which all source symbols are included as part of the encoding symbols of a source block. The RaptorG code as described herein is a systematic code. Luby, et al. Expires February 25, 2010 [Page 15] Internet-Draft RaptorG FEC Scheme August 2009 Encoding Symbol ID: information that uniquely identifies each encoding symbol associated with a source block for sending and receiving purposes. Internal Symbol ID: information that uniquely identifies each symbol associated with an extended source block for encoding and decoding purposes. 5.1.2. Symbols i, j, u, v, h, a, b, d, v, m represent either non-negative integers or bit strings, 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. x,y represent either real values, or variables, depending on the context. ceil(x) denotes the smallest integer which is greater than or equal to x, where x is a real value. floor(x) denotes the largest positive integer which 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 vaue of the values x and y, and in general the maximum value of all the argument values. i % j denotes i modulo j. u ^ v denotes, for equal-length bit strings u and v, the bitwise exclusive-or of u and v. A denotes a matrix A. 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. 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. Luby, et al. Expires February 25, 2010 [Page 16] Internet-Draft RaptorG FEC Scheme August 2009 K'_max denotes the maximum number of source symbols that can be in a single source block. Set to 56404. 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 not permanently inactive symbols. H denotes the number of HDPC symbols for a single extended source block. These are permanently inactive symbols. B denotes the number of intermediate symbols that are not permanently inactive symbols excluding the LDPC symbols. W denotes the number of intermediate symbols on which the LT encoding is applied. This is the number of intermediate symbols that are not permanently inactive symbols. For each value of K' in Table 2 shown in Section 5.6, the corresponding derived value of W is a prime number. P denotes the number of permanently inactive intermediate symbols. U denotes the number intermediate symbols that are permanently inactive symbols excluding the HDPC 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 4-byte integers, V0[0], V0[1],..., V0[255] ; V1[0], V1[1],..., V1[255]; V2[0], V2[1],..., V2[255]; and V3[0], V3[1],..., V3[255]. Rand[X, i, m] a pseudo-random number generator Deg[v] a degree generator LTEnc[K, C ,(d, a, b), X] a LT encoding symbol generator Trip[K, X] a triple generator function Luby, et al. Expires February 25, 2010 [Page 17] Internet-Draft RaptorG FEC Scheme August 2009 R(X) denotes the repair symbol with ISI X GF(n) denotes the Galois field with n elements. T denotes the symbol size in bytes. Q Q = 4294967291, i.e., Q is the largest prime smaller than 2^^32. J(K') denotes the systematic index associated with K'. G denotes any generator matrix. I_S denotes the SxS identity matrix. 0_SxH denotes the SxH zero matrix. a ^^ b denotes the operation a raised to the power b. 5.1.3. Abbreviations ESI Encoding Symbol ID GF Galois Field HDPC High Density Parity Check ISI Internal Symbol ID LDPC Low Density Parity Check LT Luby Transform SBN Source Block Number SBL Source Block Length (in units of symbols) 5.2. Overview This section defines the systematic RaptorG 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 exclusive-or operation between symbols and an operation of the elements of the finite field GF(256) upon symbols. The basic encoder is described in Section 5.3. The encoder first Luby, et al. Expires February 25, 2010 [Page 18] Internet-Draft RaptorG FEC Scheme August 2009 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 called LT encoding, 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 LT encoding process. The encoding symbols are the combination of the source and repair symbols. An example of a decoder is described in Section 5.4. The process for producing source and repair symbols from the intermediate block is designed so that the intermediate block can be recovered from any sufficiently large set of encoding symbols, independent of the mix of source and repair symbols in the set. Once the intermediate block is recovered, missing source symbols of the source block can be recovered using the LT encoding process. If a RaptorG compliant decoding algorithm receives a mathematically sufficient set of encoding symbols generated according to the encoder specification in Section 5.3 for reconstruction of a source block then such a decoder SHALL recover the entire source block. A number of decoding algorithms are possible to achieve this optimal behaviour. An efficient decoding algorithm to achieve this is provided in Section 5.4. The construction of the intermediate and repair symbols is based in part on a pseudo-random number generator described in Section 5.3. This generator is based on a fixed set of 1024 random numbers which must be available to both sender and receiver. These numbers are provided in Section 5.3.5.1. Encoding and decoding operations for RaptorG use operations in the field GF(256). Section 5.7 provides a recommended way to perform these operations. Finally, the construction of the intermediate symbols from the source symbols is governed by "systematic indices", values of which are provided in Section 5.6 for specific extended source block sizes between 6 and K'_max = 56404 source symbols. Thus, the RaptorG code supports source blocks with between 1 and 56404 source symbols. 5.3. Systematic RaptorG encoder 5.3.1. Introduction For a given source block of K source symbols, for encoding and decoding purposes the source block is augmented with K'-K additional padding symbols, where K' is the smallest value that is at least K in the systematic index Table 2 of Section 5.6. The reason for padding Luby, et al. Expires February 25, 2010 [Page 19] Internet-Draft RaptorG FEC Scheme August 2009 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 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 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, and 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, and the proper padding of the extended source block with padding symbols used for encoding and decoding, is the responsibility of the padding function in the RaptorG encoder/decoder. Luby, et al. Expires February 25, 2010 [Page 20] Internet-Draft RaptorG FEC Scheme August 2009 5.3.2. Encoding overview The systematic RaptorG encoder is used to generate any number of repair symbols from a source block that consists of K source symbols placed into an extended source block C'. Figure 4 shows the encoding overview. The first step of encoding is to construct an extended source block by adding zero or more padding symbols such that the total number of symbols, K', is one of the values listed in Section 5.6. Each padding symbol consists of T bytes where the value of each byte is zero. K' MUST be selected as the smallest value of K' from the table of Section 5.6 which is greater than or equal to K. -----------------------------------------------------------+ | | | +-----------+ +--------------+ +-------------+ | C' | | | C' | Intermediate | C | | | ----+--->| Padding |--->| Symbol |--->| LT encoding |--+--> K | | | K' | Generation | L | | | | +-----------+ +--------------+ +-------------+ | | | ^ | | | (d,a,b) | | | | +------------+ | | | K' | Triple | | | +----------------------------->| | | | | Generation | | | +------------+ | | ^ | +-------------------------------------------------+--------+ | ISI X Figure 4: Encoding Overview Let C' [0],..., C' [K-1] denote the K source symbols. Let C' [K], ..., C' [K'-1] denote the K'-K padding symbols, which are all set to zero bits. Then, C' [0],..., C'[K'-1] are the symbols of the extended source block upon which encoding and decoding are performed. In the remainder of this description these padding symbols will be considered as additional source symbols and referred to as such. However, these padding symbols are not part of the encoding symbols, Luby, et al. Expires February 25, 2010 [Page 21] Internet-Draft RaptorG FEC Scheme August 2009 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 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 5.3.5.4. The K' source triples 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 RaptorG decoding process. Certain "pre-coding relationships" must hold within the L intermediate symbols. Section 5.3.3.3 describes these relationships. Section 5.3.3.4 describes how the intermediate symbols are generated from the source symbols. Once the intermediate symbols have been generated, repair symbols can be produced. For a repair symbol with ISI X>K', the triple of integers, (d, a, b) can be generated, using the Trip[] generator as described in Section 5.3.5.4. Then, the (d,a,b)-triple and the ISI X is used to generate the corresponding repair symbol from the intermediate symbols using the LTEnc[] generator described in Section 5.3.5.3. The corresponding ESI for this repair symbol is then X-(K'-K). Note that source symbols of the extended source block can also be generated using the same process, i.e., for any X < K', the symbol generated using this process has the same value as C'(X). 5.3.3. First encoding step: Intermediate Symbol Generation 5.3.3.1. General This encoding step is a pre-coding step to generate the L intermediate symbols C[0], ..., C[L-1] from the source symbols C'[0], ..., C'[K'-1]. 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 and by the ISIs of the source symbols. The generation of the source symbol triples is defined in Section 5.3.3.2 using the the Trip[] generator as described in Section 5.3.5.4. 2. A set of pre-coding relationships hold within the intermediate symbols themselves. These are defined in Section 5.3.3.3 Luby, et al. Expires February 25, 2010 [Page 22] Internet-Draft RaptorG FEC Scheme August 2009 The generation of the L intermediate symbols is then defined in Section 5.3.3.4 5.3.3.2. Source symbol triples Each of the K' source symbols is associated with a triple (d[X], a[X], b[X]) for 0 <= X < K'. The source symbol triples are determined using the Triple generator defined in Section 5.3.5.4 as: For each X, 0 <= X < K' (d[X], a[X], b[X]) = Trip[K, X] 5.3.3.3. Pre-coding relationships The pre-coding relationships amongst the L intermediate symbols are defined by expressing L-K' intermediate symbols, consisting of LDPC and HDPC symbols, in terms of the other K' intermediate symbols. There are S LDPC and H HDPC symbols, and thus S+H = L-K'. A set of P of the intermediate symbols, denoted as permanently inactive symbols, are treated differently than the other intermediate symbols in the LT encoding process. The P permanently inactive symbols consist of the H HDPC symbols together with a set of U = P-H of the other K' intermediate symbols. The values of these parameters are determined from K' as described below. Let H = 10+ceil(5* (K'-P-1000)/49000) P = max(H, min(250, floor(K'/2), u)), where u is the largest integer such that u*u <= 2.5*K' U =P - H B = K'- U S be the smallest prime integer such that S >= ceil(0.01* B) + v, where v is the smallest positive integer such that v*(v-1) >= 2*B L = K'+S+H W = L-P (= B + S). (For each value of K' in Table 2 shown in Section 5.6, the corresponding derived value of W is a prime number). C[0],..., C[B-1] denote the intermediate symbols that are not permanently inactive and not LDPC symbols. Luby, et al. Expires February 25, 2010 [Page 23] Internet-Draft RaptorG FEC Scheme August 2009 C[B],..., C[B+S-1] denote the S LDPC symbols. These are not permanently inactive. C[W],...,C[W+U-1] denote the intermediate symbols that are permanently inactive and not HDPC symbols. C[L-H],..., C[L-1] denote the H HDPC symbols. These are permanently inactive. The S LDPC symbols are defined to be the values of C[B],..., C[B+S-1] at the end of the following process: Set the symbols C[B],...,C[B+S-1] to zero. For i = 0,..., B-1 do a = 1 + (floor(i/S) % (S-1)) b = i % S C[B + b] = C[B + b] ^ C[i] b = (b + a) % S C[B + b] = C[B + b] ^ C[i] b = (b + a) % S C[B + b] = C[B + b] ^ C[i] If U > 0 then For i=0,...,S-1 m = i % U C[i+B] = C[i+B]^C[m+W] The H HDPC symbols are defined by considering each intermediate symbol as a sequence of elements from the finite field GF(256). We represent elements of GF(256) in the usual way as polynomials in one variable, x, with coefficients from the finite field GF(2) modulo an irreducible polynomial f(x). A single byte of data from a symbol, b7,b6,b5,b4,b3,b2,b1,b0, where b7 is the highest order bit and b0 is the lowest order bit corresponds to the finite field element b7 x^^7 + b6 x^^6 + b5 x^^5 + b4 x^^4 + b3 x^^3 + b2 x^^2 + b1 x + b0 mod f(x) Luby, et al. Expires February 25, 2010 [Page 24] Internet-Draft RaptorG FEC Scheme August 2009 The irreducible polynomial f(x) is defined to be: f(x) = x^^8 + x^^4 + x^^3 + x^^2 + 1 We then define the operation of elements of GF(256) on symbols as follows: Let beta denote an element of GF(256). C denote a symbol of length T bytes. c[0], ..., c[T-1] denote the bytes of C. gamma[0], ..., gamma[T-1] denote the elements of GF(256) corresponding to c[0], ..., c[T-1] respectively. Then we define delta[i] = beta*gamma[i] for i=0, ..., T-1 where '*' represents the usual multiplication operation in GF(256). A multiplication table for GF(256) and a recommended way to perform calculations in GF(256) is provided in Section 5.7. Then the operation of beta on C is defined as follows: beta*C = d[0], ..., d[T-1] where d[i] is the byte value corresponding to delta[i] for i=0,..., T-1. The relationship between the first K'+S intermediate symbols and the H HDPC symbols is then defined as follows: Let alpha denote a generator element of GF(256), specifically the element represented by the polynomial x. H denote an H x (K' +S ) matrix with elements from GF(256), where for j=0,...,K'+S-2 the entry H[i,j] is the identity element if i= Rand(j,3,H) or i = (Rand(j,3,H) + Rand(j,4,H-1) + 1) % H and H[i,j] is the zero element for all other values of i, and for j=K'+S-1, H[i,j] = alpha^^i for i=0,...,H-1. GAMMA denote a (K'+S ) x (K'+S ) matrix with elements from GF(256), where Luby, et al. Expires February 25, 2010 [Page 25] Internet-Draft RaptorG FEC Scheme August 2009 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: Trans(C[K'+S], ..., C[K'+S+H-1] ) = H* GAMMA *Trans( C[0], ..., C[K'+S-1] ) where '*' represents standard matrix multiplication utilising the above defined operation to define the multiplication between a matrix over GF(256) and a matrix of symbols (in particular the column vector of symbols). The H HDPC symbols may be conveniently computed from the first K'+S intermediate symbols using the following algorithm, where u is a working register containing a single symbol: 1. Set the symbols C[K'+S], ..., C[K'+S+H-1] to zero 2. u = C[0] 3. For j = 1, ..., K'+S-1 do A. pos1 = Rand(j,3,H) B. pos2 = (pos1 + Rand(j,4,H-1) + 1) % H C. C[K'+S + pos1] = C[K'+S + pos1] ^ u D. C[K'+S + pos2] = C[K'+S + pos2] ^ u E. u = (alpha*u) ^ C[j] 4. For i = 0, ..., H-1 A. C[K'+S+i] = C[K'+S+i] ^ u B. u = (alpha*u) Luby, et al. Expires February 25, 2010 [Page 26] Internet-Draft RaptorG FEC Scheme August 2009 5.3.3.4. Intermediate symbols 5.3.3.4.1. Definition Given the K' source symbols C'[0], C'[1],..., C'[K'-1] the L intermediate symbols C[0], C[1],..., C[L-1] are the uniquely defined symbol values that satisfy the following conditions: 1. The K' source symbols C'[0], C'[1],..., C'[K'-1] satisfy the K' constraints 1. C'[X] = LTEnc[K', (C[0],..., C[L-1]), (d[X], a[X], b[X]), X], for all X, 0 <= X < K', where (d[X], a[X], b[X]) = Trip[K',X] and Trip[] is defined in Section 5.3.5.4. 2. The L intermediate symbols C[0], C[1],..., C[L-1] satisfy the pre-coding relationships defined in Section 5.3.3.3 5.3.3.4.2. Example method for calculation of intermediate symbols This section describes a possible method for calculation of the L intermediate symbols C[0], C[1],..., C[L-1] satisfying the constraints in Section 5.3.3.4.1 The generator matrix G for a code which generates n output symbols from k input symbols is an n x k matrix over GF(256), 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 the product of each input symbol with the corresponding entry in row i. 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(256), A, such that: A*C = D Luby, et al. Expires February 25, 2010 [Page 27] Internet-Draft RaptorG FEC Scheme August 2009 The matrix A can be constructed as follows: Let: G_LDPC,1 and G_LDPC,2 be S x B and S x U matrices such that G_LDPC,1 * Transpose[(C[0],...., C[B-1])] + G_LDPC,2 * Transpose(C[W], ..., C[W+U-1]) = Transpose[(C[B], ..., C[B+S-1])] and "+" is the component-wise XOR of the vectors involved. G_HDPC be the H x (K'+S) generator matrix of the HDPC symbols, So, G_HDPC * Transpose(C[0], ..., C[K'+S-1]) = Transpose(C[K'+S], ..., C[L-1]) i.e. G_HDPC = H*GAMMA 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 K' x L 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 which are XORed to produce LTEnc[K', (C[0], ..., C[L-1]), (d[i], a[i], b[i]), i] and G_LT[i,j] = 0 otherwise. Then: The first S rows of A are equal to G_LDPC,1 | I_S | G_LDPC,2 | 0_SxH. The next H rows of A are equal to G_HDPC | I_H. The remaining K' rows of A are equal to G_LT. The matrix A is depicted in Figure (Figure 5) below: Luby, et al. Expires February 25, 2010 [Page 28] Internet-Draft RaptorG FEC Scheme August 2009 B S U H +-----------------------+-------+----------+-------+ | | | | | S | G_LDPC,1 | I_S | G_LDPC,2 | 0_SxH | | | | | | +-----------------------+-------+----------+-------+ | | | H | G_HDPC | I_H | | | | +------------------------------------------+-------+ | | | | K' | G_LT | | | | | +--------------------------------------------------+ Figure 5: The matrix A The intermediate symbols can then be calculated as: C = (A^^-1)*D The source triples are generated such that for any K' matrix A has full rank and is therefore invertible. This calculation can be realized by applying a RaptorG decoding process to the K' source symbols C'[0], C'[1],..., C'[K'-1] to produce the L intermediate symbols C[0], C[1],..., C[L-1]. To efficiently generate the intermediate symbols from the source symbols, it is recommended that an efficient decoder implementation such as that described in Section 5.4 be used. 5.3.4. Second encoding step: LT encoding In the second encoding step, the repair symbol with ISI X (X >= K') is generated by applying the generator LTEnc[K', (C[0], C[1],..., C[L-1]), (d, a, b), X] defined in Section 5.3.5.3 to the L intermediate symbols C[0], C[1],..., C[L-1] using the triple (d, a, b)=Trip[K',X]. 5.3.5. Generators 5.3.5.1. 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 less than 256, and m is a positive integer and the value produced is an Luby, et al. Expires February 25, 2010 [Page 29] Internet-Draft RaptorG FEC Scheme August 2009 integer between 0 and m-1. Let V0, V1, V2 and V3 be arrays of 256 entries each, where each entry is a 4-byte unsigned integer. These arrays are provided in Section 5.5. Let x0 = (X + i) mod 2^^8 x1 = (floor(X / 2^^8) + i) mod 2^^8 x2 = (floor(X / 2^^16) + i) mod 2^^8 x3 = (floor(X / 2^^24) + i) mod 2^^8 Then, Rand[x, i, m] = (V0[x0] ^ V1[x1] ^ V2[x2] ^ V3[x3]) % m 5.3.5.2. Degree Generator The degree generator Deg[v] is defined as follows, where v is an integer that is at least 0 and less than 2^^20 = 1048576. Given v, find index d in Table 1 such that f[d-1] <= v < f[d], and set Deg[v] = d. Luby, et al. Expires February 25, 2010 [Page 30] Internet-Draft RaptorG FEC Scheme August 2009 +---------+---------+---------+---------+ | Index d | f[d] | Index d | f[d] | +---------+---------+---------+---------+ | 0 | 0 | 1 | 5243 | +---------+---------+---------+---------+ | 2 | 529531 | 3 | 704294 | +---------+---------+---------+---------+ | 4 | 791675 | 5 | 844104 | +---------+---------+---------+---------+ | 6 | 879057 | 7 | 904023 | +---------+---------+---------+---------+ | 8 | 922747 | 9 | 937311 | +---------+---------+---------+---------+ | 10 | 948962 | 11 | 958494 | +---------+---------+---------+---------+ | 12 | 966438 | 13 | 973160 | +---------+---------+---------+---------+ | 14 | 978921 | 15 | 983914 | +---------+---------+---------+---------+ | 16 | 988283 | 17 | 992138 | +---------+---------+---------+---------+ | 18 | 995565 | 19 | 998631 | +---------+---------+---------+---------+ | 20 | 1001391 | 21 | 1003887 | +---------+---------+---------+---------+ | 22 | 1006157 | 23 | 1008229 | +---------+---------+---------+---------+ | 24 | 1010129 | 25 | 1011876 | +---------+---------+---------+---------+ | 26 | 1013490 | 27 | 1014983 | +---------+---------+---------+---------+ | 28 | 1016370 | 29 | 1017662 | +---------+---------+---------+---------+ | 30 | 1048576 | | | +---------+---------+---------+---------+ Table 1: Defines the degree distribution for encoding symbols 5.3.5.3. LT Encoding Symbol Generator The encoding symbol generator LTEnc[K', (C[0], C[1],..., C[L-1]), (d, a, b), X] takes the following inputs: K' is the number of source symbols for the extended source block. Let L, W, B, S, and P be derived from K' as described in Section (Section 5.3.3.3). Luby, et al. Expires February 25, 2010 [Page 31] Internet-Draft RaptorG FEC Scheme August 2009 (C[0], C[1],..., C[L-1]) is the array of L intermediate symbols (sub-symbols) generated as described in Section 5.3.3.4 X is an ISI. (d, a, b) is a source triple determined from X using the Triple generator defined in Section 5.3.5.4, whereby d is an integer denoting an encoding symbol degree a is an integer between 1 and W-1 inclusive b is an integer between 0 and W-1 inclusive The encoding symbol generator produces a single encoding symbol as output, according to the following algorithm: result = C[b]. For j = 1,...,min(d-1,W-1) do b = (b + a) % W result = result ^ C[b] result = result ^ C[B+S+(X % P)] Return result 5.3.5.4. Triple generator The triple generator Trip[K',X] takes the following inputs: K' - The number of source symbols in the extended source block X - An Intermediate symbol ID (ISI) Let L be determined from K' as described in Section 5.3.3.3 Q = 4294967291, the largest prime smaller than 2^^32. J(K') be the systematic index associated with K', as defined in Section 5.6 The output of the triple generator is a triple, (d, a, b) determined as follows: Luby, et al. Expires February 25, 2010 [Page 32] Internet-Draft RaptorG FEC Scheme August 2009 1. A = 1 + (53591 + J(K')*997) % Q 2. B = 10267*(J(K')+1) % Q 3. y = (B + X*A) % Q 4. v = Rand[y, 0, 2^^20] 5. d = Deg[v] 6. a = 1 + Rand[y, 1, Z-1] 7. b = Rand[y, 2, Z] 5.4. Example FEC decoder 5.4.1. General This section describes an efficient decoding algorithm for the RaptorG code introduced 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. 5.4.2. Decoding an extended source block 5.4.2.1. General It is assumed that the decoder knows the structure of the source block it is to decode, including the symbol size, T, and the number K of symbols in the source block and the number K' of source symbols in the extended source block. From the algorithms described in Sections Section 5.3, the RaptorG 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 exclusive-or is equal to the encoding symbol is passed to the decoder. In the case of source symbols, including padding symbols, the source symbol triples described in Section 5.3.3.2 indicate the number and set of intermediate symbols which sum to give Luby, et al. Expires February 25, 2010 [Page 33] Internet-Draft RaptorG FEC Scheme August 2009 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. The following M by L matrix A with elements from GF(256) can be derived from the information passed to the decoder for the extended 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 H+S of the M symbols are zero-valued symbols that correspond to HDPC and LDPC symbols, respectively (these are check symbols for the LDPC and HDPC symbols, and not the LDPC and HDPC symbols themselves), and the remaining N of the M symbols are the received encoding symbols for the extended source block. Then, A is the matrix that satisfies A*C = D, where here * denotes matrix multiplication over GF(256). In particular, A[i,j] = 1 if the intermediate symbol corresponding to index j is exclusive-ORed into the LT dynamic symbol corresponding to index i in the encoding, or if index i corresponds to a LDPC or HDPC symbol and index j corresponds to the same LDPC or HDPC symbol. A[i,j] = (H* LAMDBDA)[i,j] if index i corresponds to an HDPC symbol (i.e. i