idnits 2.17.1 draft-luby-rmt-bb-fec-raptorg-object-01.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** The document seems to lack a License Notice according IETF Trust Provisions of 28 Dec 2009, Section 6.b.ii or Provisions of 12 Sep 2009 Section 6.b -- however, there's a paragraph with a matching beginning. Boilerplate error? (You're using the IETF Trust Provisions' Section 6.b License Notice from 12 Feb 2009 rather than one of the newer Notices. See https://trustee.ietf.org/license-info/.) Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year == Line 559 has weird spacing: '... K'_max denot...' -- The document date (November 10, 2009) is 5278 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) == Missing Reference: 'I' is mentioned on line 380, but not defined == Missing Reference: 'J' is mentioned on line 380, but not defined == Missing Reference: 'Kt' is mentioned on line 393, but not defined == Missing Reference: 'Z' is mentioned on line 393, but not defined == Missing Reference: 'A' is mentioned on line 549, but not defined -- Looks like a reference, but probably isn't: '0' on line 1814 -- Looks like a reference, but probably isn't: '1' on line 1398 -- Looks like a reference, but probably isn't: '2' on line 588 == Missing Reference: 'L-1' is mentioned on line 1397, but not defined -- Looks like a reference, but probably isn't: '255' on line 598 == Missing Reference: 'X' is mentioned on line 1056, but not defined == Missing Reference: 'K' is mentioned on line 858, but not defined == Missing Reference: 'B-1' is mentioned on line 1097, but not defined == Missing Reference: 'B' is mentioned on line 1098, but not defined == Missing Reference: 'W' is mentioned on line 1098, but not defined == Missing Reference: 'L-H' is mentioned on line 902, but not defined == Missing Reference: 'S-1' is mentioned on line 909, but not defined == Missing Reference: 'T-1' is mentioned on line 973, but not defined == Missing Reference: 'S' is mentioned on line 1021, but not defined == Missing Reference: 'M-1' is mentioned on line 1398, but not defined ** Downref: Normative reference to an Informational RFC: RFC 4082 -- Possible downref: Non-RFC (?) normative reference: ref. 'SHA1' Summary: 2 errors (**), 0 flaws (~~), 18 warnings (==), 6 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Reliable Multicast Transport M. Luby 3 Internet-Draft Qualcomm, Inc. 4 Intended status: Standards Track A. Shokrollahi 5 Expires: May 14, 2010 EPFL 6 M. Watson 7 Qualcomm, Inc. 8 T. Stockhammer 9 Nomor Research 10 November 10, 2009 12 RaptorG Forward Error Correction Scheme for Object Delivery 13 draft-luby-rmt-bb-fec-raptorg-object-01 15 Abstract 17 This document describes a Fully-Specified FEC scheme, corresponding 18 to FEC Encoding ID XXX, for the RaptorG forward error correction code 19 and its application to reliable delivery of data objects. 21 RaptorG codes are a new family of codes to provide superior 22 flexibility, larger source block sizes and better coding efficiency 23 than Raptor codes in RFC5053. RaptorG is also a fountain code, i.e., 24 as many encoding symbols as needed can be generated by the encoder 25 on-the-fly from the source symbols of a source block of data. The 26 decoder is able to recover the source block from any set of encoding 27 symbols for most cases equal to the number of source symbols and in 28 rare cases with slightly more than the number of source symbols. 30 The RaptorG code described here is a systematic code, meaning that 31 all the source symbols are among the encoding symbols that can be 32 generated. 34 Status of this Memo 36 This Internet-Draft is submitted to IETF in full conformance with the 37 provisions of BCP 78 and BCP 79. 39 Internet-Drafts are working documents of the Internet Engineering 40 Task Force (IETF), its areas, and its working groups. Note that 41 other groups may also distribute working documents as Internet- 42 Drafts. 44 Internet-Drafts are draft documents valid for a maximum of six months 45 and may be updated, replaced, or obsoleted by other documents at any 46 time. It is inappropriate to use Internet-Drafts as reference 47 material or to cite them other than as "work in progress." 48 The list of current Internet-Drafts can be accessed at 49 http://www.ietf.org/ietf/1id-abstracts.txt. 51 The list of Internet-Draft Shadow Directories can be accessed at 52 http://www.ietf.org/shadow.html. 54 This Internet-Draft will expire on May 14, 2010. 56 Copyright Notice 58 Copyright (c) 2009 IETF Trust and the persons identified as the 59 document authors. All rights reserved. 61 This document is subject to BCP 78 and the IETF Trust's Legal 62 Provisions Relating to IETF Documents in effect on the date of 63 publication of this document (http://trustee.ietf.org/license-info). 64 Please review these documents carefully, as they describe your rights 65 and restrictions with respect to this document. 67 Table of Contents 69 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 70 2. Requirements notation . . . . . . . . . . . . . . . . . . . . . 4 71 3. Formats and Codes . . . . . . . . . . . . . . . . . . . . . . . 5 72 3.1. FEC Payload IDs . . . . . . . . . . . . . . . . . . . . . . 5 73 3.2. FEC Object Transmission Information . . . . . . . . . . . . 5 74 4. Procedures . . . . . . . . . . . . . . . . . . . . . . . . . . 8 75 4.1. Content Delivery Protocol Requirements . . . . . . . . . . 8 76 4.2. Example parameter derivation algorithm . . . . . . . . . . 8 77 4.3. Object delivery . . . . . . . . . . . . . . . . . . . . . 10 78 5. RaptorG FEC code specification . . . . . . . . . . . . . . . 13 79 5.1. Definitions, Symbols and abbreviations . . . . . . . . . 13 80 5.2. Overview . . . . . . . . . . . . . . . . . . . . . . . . 16 81 5.3. Systematic RaptorG encoder . . . . . . . . . . . . . . . 18 82 5.4. Example FEC decoder . . . . . . . . . . . . . . . . . . . 31 83 5.5. Random Numbers . . . . . . . . . . . . . . . . . . . . . 37 84 5.6. Systematic indices and other parameters . . . . . . . . . 41 85 5.7. Arithmetic in GF(256) . . . . . . . . . . . . . . . . . . 45 86 6. Security Considerations . . . . . . . . . . . . . . . . . . . 47 87 7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 48 88 8. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 49 89 9. References . . . . . . . . . . . . . . . . . . . . . . . . . 50 90 9.1. Normative references . . . . . . . . . . . . . . . . . . 50 91 9.2. Informative references . . . . . . . . . . . . . . . . . 50 92 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 51 94 1. Introduction 96 This document specifies an FEC Scheme for the RaptorG forward error 97 correction code for object delivery applications. The concept of an 98 FEC Scheme is defined in RFC5052 [RFC5052] and this document follows 99 the format prescribed there and uses the terminology of that 100 document. An initial version of a Raptor code was introduced in 101 RFC5053 [RFC5053]. The RaptorG code described herein is a next 102 generation of Raptor code with superior reliability, better coding 103 efficiency, and support for larger source block sizes than the Raptor 104 code of RFC5053 [RFC5053]. These improvements simplify the usage of 105 the RaptorG code in an object delivery Content Delivery Protocol 106 compared to RFC5053 [RFC5053]. 108 The RaptorG FEC Scheme is a Fully-Specified FEC Scheme corresponding 109 to FEC Encoding ID XXX. 111 RaptorG is a fountain code, i.e., as many encoding symbols as needed 112 can be generated by the encoder on-the-fly from the source symbols of 113 a block. The decoder is able to recover the source block from any 114 set of encoding symbols only slightly more in number than the number 115 of source symbols. 117 The code described in this document is a systematic code, that is, 118 the original source symbols can be sent unmodified from sender to 119 receiver, as well as a number of repair symbols. For more backgound 120 on the use of Forward Error Correction codes in reliable multicast, 121 see [RFC3453]. 123 2. Requirements notation 125 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 126 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 127 document are to be interpreted as described in [RFC2119]. 129 3. Formats and Codes 131 3.1. FEC Payload IDs 133 The FEC Payload ID MUST be a 4 octet field defined as follows: 135 0 1 2 3 136 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 137 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 138 | SBN | Encoding Symbol ID | 139 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 141 Figure 1: FEC Payload ID format 143 Source Block Number (SBN), (8 bits): An integer identifier for the 144 source block that the encoding symbols within the packet relate 145 to. 147 Encoding Symbol ID (ESI), (24 bits): An integer identifier for the 148 encoding symbols within the packet. 150 The interpretation of the Source Block Number and Encoding Symbol 151 Identifier is defined in Section 5. 153 3.2. FEC Object Transmission Information 155 3.2.1. Mandatory 157 The value of the FEC Encoding ID MUST be XXX, as assigned by IANA 158 (see Section 7). 160 3.2.2. Common 162 The Common FEC Object Transmission Information elements used by this 163 FEC Scheme are: 165 - Transfer Length (F) 167 - Symbol Size (T) 169 The Transfer Length is a non-negative integer that is at most 170 946287651840, which can be represented by 40 bits. The Symbol Size 171 is a non-negative integer less than 2^^16. 173 The Transfer Length is a field of 40 bits in its definition, and the 174 Symbol Size field is 16 bits, and both length units are bytes. 176 The encoded Common FEC Object Transmission Information format is 177 shown in Figure 2. 179 0 1 2 3 180 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 181 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 182 | Transfer Length (F) | 183 + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 184 | | Reserved | Symbol Size (T) | 185 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 187 Figure 2: Encoded Common FEC OTI for RaptorG FEC Scheme 189 NOTE 1: The limit of 946287651840 on the transfer length is a 190 consequence of the limitation on the symbol size to 2^^16-1, the 191 limitation on the number of symbols in a source block to 56404 and 192 the limitation on the number of source blocks to 2^^8. 194 3.2.3. Scheme-Specific 196 The following parameters are carried in the Scheme-Specific FEC 197 Object Transmission Information element for this FEC Scheme: 199 o The number of source blocks (Z) 201 o The number of sub-blocks (N) 203 o A symbol alignment parameter (Al) 205 These parameters are all non-negative integers. The encoded Scheme- 206 specific Object Transmission Information is a 4-octet field 207 consisting of the parameters Z (12 bits), N (12 bits) and Al (8 bits) 208 as shown in Figure 3. 210 0 1 2 3 211 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 212 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 213 | Z | N | Al | 214 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 216 Figure 3: Encoded Scheme-specific FEC Object Transmission Information 218 The encoded FEC Object Transmission Information is a 14 octet field 219 consisting of the concatenation of the encoded Common FEC Object 220 Transmission Information and the encoded Scheme-specific FEC Object 221 Transmission Information. 223 These three parameters define the source block partitioning as 224 described in Section 4.3.1.2 226 4. Procedures 228 4.1. Content Delivery Protocol Requirements 230 This section describes the information exchange between the RaptorG 231 FEC Scheme and any Content Delivery Protocol (CDP) that makes use of 232 the RaptorG FEC Scheme for object delivery. 234 The RaptorG encoder scheme and RaptorG decoder scheme for object 235 delivery require the following information from the CDP: 237 o The transfer length of the object, F, in bytes 239 o A symbol alignment parameter, Al 241 o The symbol size, T, in bytes, which MUST be a multiple of Al 243 o The number of source blocks, Z 245 o The number of sub-blocks in each source block, N 247 The RaptorG encoder scheme for object delivery additionally requires: 249 - the object to be encoded, F bytes 251 The RaptorG encoder scheme supplies the CDP with the following 252 information for each packet to be sent: 254 o Source Block Number (SBN) 256 o Encoding Symbol ID (ESI) 258 o Encoding symbol(s) 260 The CDP MUST communicate this information to the receiver. 262 4.2. Example parameter derivation algorithm 264 This section provides recommendations for the derivation of the three 265 transport parameters, T, Z and N. This recommendation is based on the 266 following input parameters: 268 o F the transfer length of the object, in bytes 270 o WS the maximum size block that is decodable in working memory, in 271 bytes 273 o P' the maximum payload size in bytes, which is assumed to be a 274 multiple of Al 276 o Al the symbol alignment parameter, in bytes 278 o SS a parameter where the desired lower bound on the sub-symbol 279 size is SS*Al 281 o K'_max the maximum number of source symbols per source block. 283 Note: Section 5.1.2 defines K'_max to be 56404 285 Based on the above inputs, the transport parameters T, Z and N are 286 calculated as follows: 288 Let, 290 o T = P' 292 o Kt = ceil(F/T) 294 o N_max = floor(T/(SS*Al)) 296 o for all n=1, ..., N_max 298 * KL(n) is the maximum K' value in Table 2 in Section 5.6 such 299 that 301 K' <= floor (WS/(Al*(ceil(T/(Al*n))))) 303 o Z = ceil(Kt/KL(N_max)) 305 o N is the minimum n=1, ..., N_max such that ceil (Kt/Z) <= KL(n) 307 It is RECOMMENDED that each packet contains exactly one symbol. 308 However, receivers SHALL support the reception of packets that 309 contain multiple symbols. 311 The value Kt is the total number of symbols required to represent the 312 source data of the object. 314 The algorithm above and that defined in Section 4.3.1.2 ensure that 315 the sub-symbol sizes are a multiple of the symbol alignment 316 parameter, Al. This is useful because the XOR operations used for 317 encoding and decoding are generally performed several bytes at a 318 time, for example at least 4 bytes at a time on a 32 bit processor. 319 Thus the encoding and decoding can be performed faster if the sub- 320 symbol sizes are a multiple of this number of bytes. 322 The recommended settings for the input parameter Al is 4. 324 The parameter WS can be used to generate encoded data which can be 325 decoded efficiently with limited working memory at the decoder. Note 326 that the actual maximum decoder memory requirement for a given value 327 of WS depends on the implementation, but it is possible to implement 328 decoding using working memory only slightly larger than WS. 330 4.3. Object delivery 332 4.3.1. Source block construction 334 4.3.1.1. General 336 In order to apply the RaptorG encoder to a source object, the object 337 may be broken into Z >= 1 blocks, known as source blocks. The 338 RaptorG encoder is applied independently to each source block. Each 339 source block is identified by a unique integer Source Block Number 340 (SBN), where the first source block has SBN zero, the second has SBN 341 one, etc. Each source block is divided into a number, K, of source 342 symbols of size T bytes each. Each source symbol is identified by a 343 unique integer Encoding Symbol Identifier (ESI), where the first 344 source symbol of a source block has ESI zero, the second has ESI one, 345 etc. 347 Each source block with K source symbols is divided into N >= 1 sub- 348 blocks, which are small enough to be decoded in the working memory. 349 Each sub-block is divided into K sub-symbols of size T'. 351 Note that the value of K is not necessarily the same for each source 352 block of a object and the value of T' may not necessarily be the same 353 for each sub-block of a source block. However, the symbol size T is 354 the same for all source blocks of an object and the number of 355 symbols, K is the same for every sub-block of a source block. Exact 356 partitioning of the object into source blocks and sub-blocks is 357 described in Section 4.3.1.2 below. 359 4.3.1.2. Source block and sub-block partitioning 361 The construction of source blocks and sub-blocks is determined based 362 on five input parameters, F, Al, T, Z and N and a function 363 Partition[]. The five input parameters are defined as follows: 365 o F the transfer length of the object, in bytes 367 o Al a symbol alignment parameter, in bytes 368 o T the symbol size, in bytes, which MUST be a multiple of Al 370 o Z the number of source blocks 372 o N the number of sub-blocks in each source block 374 These parameters MUST be set so that ceil(ceil(F/T)/Z) <= K'_max. 375 Recommendations for derivation of these parameters are provided in 376 Section 4.2. 378 The function Partition[] takes a pair of integers (I, J) as input and 379 derives four integers (IL, IS, JL, JS) as output. Specifically, the 380 value of Partition[I, J] is a sequence of four integers (IL, IS, JL, 381 JS), where IL = ceil(I/J), IS = floor(I/J), JL = I - IS * J and JS = 382 J - JL. Partition[] derives parameters for partitioning a block of 383 size I into J approximately equal sized blocks. Specifically, JL 384 blocks of length IL and JS blocks of length IS. 386 The source object MUST be partitioned into source blocks and sub- 387 blocks as follows: 389 Let, 391 o Kt = ceil(F/T) 393 o (KL, KS, ZL, ZS) = Partition[Kt, Z] 395 o (TL, TS, NL, NS) = Partition[T/Al, N] 397 Then, the object MUST be partitioned into Z = ZL + ZS contiguous 398 source blocks, the first ZL source blocks each having KL*T bytes, 399 i.e. KL source symbols of T bytes each, and the remaining ZS source 400 blocks each having KS*T bytes, i.e. KS source symbols of T bytes 401 each. 403 If Kt*T > F then for encoding purposes, the last symbol of the last 404 source block MUST be padded at the end with Kt*T-F zero bytes. 406 Next, each source block with K source symbols MUST be divided into N 407 = NL + NS contiguous sub-blocks, the first NL sub-blocks each 408 consisting of K contiguous sub-symbols of size of TL*Al bytes and the 409 remaining NS sub-blocks each consisting of K contiguous sub-symbols 410 of size of TS*Al bytes. The symbol alignment parameter Al ensures 411 that sub-symbols are always a multiple of Al bytes. 413 Finally, the m-th symbol of a source block consists of the 414 concatenation of the m-th sub-symbol from each of the N sub-blocks. 415 Note that this implies that when N > 1 then a symbol is NOT a 416 contiguous portion of the object. 418 4.3.2. Encoding packet construction 420 Each encoding packet contains the following information: 422 o Source Block Number (SBN) 424 o Encoding Symbol ID (ESI) 426 o encoding symbol(s) 428 Each source block is encoded independently of the others. Source 429 blocks are numbered consecutively from zero. 431 Encoding Symbol ID values from 0 to K-1 identify the source symbols 432 of a source block in sequential order, where K is the number of 433 source symbols in the source block. Encoding Symbol IDs K onwards 434 identify repair symbols generated from the source symbols using the 435 RaptorG encoder. 437 Each encoding packet either consists entirely of source symbols 438 (source packet) or entirely of repair symbols (repair packet). A 439 packet may contain any number of symbols from the same source block. 440 In the case that the last source symbol in a source packet includes 441 padding bytes added for FEC encoding purposes then these bytes need 442 not be included in the packet. Otherwise, only whole symbols MUST be 443 included. 445 The Encoding Symbol ID, X, carried in each source packet is the 446 Encoding Symbol ID of the first source symbol carried in that packet. 447 The subsequent source symbols in the packet have Encoding Symbol IDs, 448 X+1 to X+G-1, in sequential order, where G is the number of symbols 449 in the packet. 451 Similarly, the Encoding Symbol ID, X, placed into a repair packet is 452 the Encoding Symbol ID of the first repair symbol in the repair 453 packet and the subsequent repair symbols in the packet have Encoding 454 Symbol IDs X+1 to X+G-1 in sequential order, where G is the number of 455 symbols in the packet. 457 Note that it is not necessary for the receiver to know the total 458 number of repair packets. 460 5. RaptorG FEC code specification 462 5.1. Definitions, Symbols and abbreviations 464 For the purpose of the RaptorG FEC code specification in this 465 section, the following definitions, symbols and abbreviations apply. 467 5.1.1. Definitions 469 o Source block: a block of K source symbols which are considered 470 together for RaptorG encoding and decoding purposes. 472 o Extended Source Block: a block of K' source symbols, where K' >= K 473 constructed from a source block and zero or more padding symbols. 475 o Symbol: a unit of data. The size, in bytes, of a symbol is known 476 as the symbol size. The symbol size is always an integer. 478 o Source symbol: the smallest unit of data used during the encoding 479 process. All source symbols within a source block have the same 480 size. 482 o Padding symbol: a symbol with all zero bits that is added to the 483 source block to form the extended source block. 485 o Encoding symbol: a symbol that can be sent as part of the encoding 486 of a source block. The encoding symbols of a source block consist 487 of the source symbols of the source block and the repair symbols 488 generated from the source block. Repair symbols generated from a 489 source block have the same size as the source symbols of that 490 source block. 492 o Repair symbol: the encoding symbols of a source block that are not 493 source symbols. The repair symbols are generated based on the 494 source symbols of a source block. 496 o Intermediate symbols: symbols generated from the source symbols 497 using an inverse encoding process. The repair symbols are then 498 generated directly from the intermediate symbols. The encoding 499 symbols do not include the intermediate symbols, i.e., 500 intermediate symbols are not sent as part of the encoding of a 501 source block. The intermediate symbols are partitioned into LT 502 symbols and PI symbols. 504 o LT symbols: The subset of the intermediate symbols that can be LT 505 neighbors of an encoding symbol. 507 o PI symbols: The subset of the intermediate symbols that can be PI 508 neighbors of an encoding symbol. 510 o Systematic code: a code in which all source symbols are included 511 as part of the encoding symbols of a source block. The RaptorG 512 code as described herein is a systematic code. 514 o Encoding Symbol ID: information that uniquely identifies each 515 encoding symbol associated with a source block for sending and 516 receiving purposes. 518 o Internal Symbol ID: information that uniquely identifies each 519 symbol associated with an extended source block for encoding and 520 decoding purposes. 522 5.1.2. Symbols 524 i, j, u, v, h, d, a, b, d1, a1, b1, v, m, x, y represent values or 525 variables of one type or another, depending on the context. 527 X denotes a non-negative integer value that is either an ISI value 528 or an ESI value, depending on the context. 530 ceil(x) denotes the smallest integer which is greater than or equal 531 to x, where x is a real value. 533 floor(x) denotes the largest positive integer which is less than or 534 equal to x, where x is a real value. 536 min(x,y) denotes the minimum value of the values x and y, and in 537 general the minimum value of all the argument values. 539 max(x,y) denotes the maximum vaue of the values x and y, and in 540 general the maximum value of all the argument values. 542 i % j denotes i modulo j. 544 u ^ v denotes, for equal-length bit strings u and v, the bitwise 545 exclusive-or of u and v. 547 A denotes a matrix A. 549 Transpose[A] denotes the transposed matrix of matrix A. 551 A^^-1 denotes the inverse matrix of matrix A. 553 K denotes the number of symbols in a single source block. 555 K' denotes the number of source plus padding symbols in an extended 556 source block. For the majority of this specification, the 557 padding symbols are considered to be additional source symbols. 559 K'_max denotes the maximum number of source symbols that can be in a 560 single source block. Set to 56404. 562 L denotes the number of intermediate symbols for a single extended 563 source block. 565 S denotes the number of LDPC symbols for a single extended source 566 block. These are LT symbols. For each value of K' shown in 567 Table 2 in Section 5.6, the corresponding value of S is a prime 568 number. 570 H denotes the number of HDPC symbols for a single extended source 571 block. These are PI symbols. 573 B denotes the number of intermediate symbols that are LT symbols 574 excluding the LDPC symbols. 576 W denotes the number of intermediate symbols that are LT symbols. 577 For each value of K' in Table 2 shown in Section 5.6, the 578 corresponding value of W is a prime number. 580 P denotes the number of intermediate symbols that are PI symbols. 581 These contain all HDPC symbols. 583 P1 denotes the smallest prime number greater than or equal to P. 585 U denotes the number of non-HDPC intermediate symbols that are PI 586 symbols. 588 C denotes an array of intermediate symbols, C[0], C[1], C[2],..., 589 C[L-1]. 591 C' denotes an array of the symbols of the extended source block, 592 where C'[0], C'[1], C'[2],..., C'[K-1] are the source symbols of 593 the source block and C'[K], C'[K+1],..., C'[K'-1] are padding 594 symbols. 596 V0, V1, V2, V3 denote four arrays of 4-byte integers, V0[0], 597 V0[1],..., V0[255] ; V1[0], V1[1],..., V1[255]; V2[0], 598 V2[1],..., V2[255]; and V3[0], V3[1],..., V3[255] as shown in 599 Section 5.5. 601 Rand[y, i, m] a pseudo-random number generator 603 Deg[v] a degree generator 605 Enc[K', C ,(d, a, b, d1, a1, b1)] an encoding symbol generator 607 Tuple[K', X] a tuple generator function 609 GF(n) denotes the Galois field with n elements. 611 T denotes the symbol size in bytes. 613 Q Q = 4294967291, i.e., Q is the largest prime smaller than 2^^32. 615 J(K') denotes the systematic index associated with K'. 617 G denotes any generator matrix. 619 I_S denotes the SxS identity matrix. 621 a ^^ b denotes the operation a raised to the power b. 623 5.1.3. Abbreviations 625 ESI Encoding Symbol ID 627 GF Galois Field 629 HDPC High Density Parity Check 631 ISI Internal Symbol ID 633 LDPC Low Density Parity Check 635 LT Luby Transform 637 PI Permanently Interactive 639 SBN Source Block Number 641 SBL Source Block Length (in units of symbols) 643 5.2. Overview 645 This section defines the systematic RaptorG FEC code. 647 Symbols are the fundamental data units of the encoding and decoding 648 process. For each source block all symbols are the same size, 649 referred to as the symbol size T. The atomic operations performed on 650 symbols for both encoding and decoding are the exclusive-or operation 651 between symbols and an operation of the elements of the finite field 652 GF(256) upon symbols. 654 The basic encoder is described in Section 5.3. The encoder first 655 derives a block of intermediate symbols from the source symbols of a 656 source block. This intermediate block has the property that both 657 source and repair symbols can be generated from it using the same 658 process. The encoder produces repair symbols from the intermediate 659 block using an efficient process, where each such repair symbol is 660 the exclusive OR of a small number of intermediate symbols from the 661 block. Source symbols can also be reproduced from the intermediate 662 block using the same process. The encoding symbols are the 663 combination of the source and repair symbols. 665 An example of a decoder is described in Section 5.4. The process for 666 producing source and repair symbols from the intermediate block is 667 designed so that the intermediate block can be recovered from any 668 sufficiently large set of encoding symbols, independent of the mix of 669 source and repair symbols in the set. Once the intermediate block is 670 recovered, missing source symbols of the source block can be 671 recovered using the encoding process. 673 If a RaptorG compliant decoding algorithm receives a mathematically 674 sufficient set of encoding symbols generated according to the encoder 675 specification in Section 5.3 for reconstruction of a source block 676 then such a decoder SHALL recover the entire source block. A number 677 of decoding algorithms are possible to achieve this optimal behavior. 678 An efficient decoding algorithm to achieve this is provided in 679 Section 5.4. 681 The construction of the intermediate and repair symbols is based in 682 part on a pseudo-random number generator described in Section 5.3. 683 This generator is based on a fixed set of 1024 random numbers which 684 must be available to both sender and receiver. These numbers are 685 provided in Section 5.5. Encoding and decoding operations for 686 RaptorG use operations in the field GF(256). Section 5.7 provides a 687 recommended way to perform these operations. 689 Finally, the construction of the intermediate symbols from the source 690 symbols is governed by "systematic indices", values of which are 691 provided in Section 5.6 for specific extended source block sizes 692 between 6 and K'_max = 56404 source symbols. Thus, the RaptorG code 693 supports source blocks with between 1 and 56404 source symbols. 695 5.3. Systematic RaptorG encoder 697 5.3.1. Introduction 699 For a given source block of K source symbols, for encoding and 700 decoding purposes the source block is augmented with K'-K additional 701 padding symbols, where K' is the smallest value that is at least K in 702 the systematic index Table 2 of Section 5.6. The reason for padding 703 out a source block to a multiple of K' is to enable faster encoding 704 and decoding, and to minimize the amount of table information that 705 needs to be stored in the encoder and decoder. 707 For purposes of transmitting and receiving data, the value of K is 708 used to determine the number of source symbols in a source block, and 709 thus K needs to be known at the sender and the receiver. In this 710 case the sender and receiver can compute K' from K and the K'-K 711 padding symbols can be automatically added to the source block 712 without any additional communication. The encoding symbol ID (ESI) 713 is used by a sender and receiver to identify the encoding symbols of 714 a source block, where the encoding symbols of a source block consist 715 of the source symbols and the repair symbols associated with the 716 source block. For a source block with K source symbols, the ESIs for 717 the source symbols are 0,1,2,...,K-1 and the ESIs for the repair 718 symbols are K, K+1, K+2,... . Using the ESI for identifying encoding 719 symbols in transport ensures that the ESI values continue 720 consecutively between the source and repair symbols. 722 For purposes of encoding and decoding data, the value of K' derived 723 from K is used as the number of source symbols of the extended source 724 block upon which encoding and decoding operations are performed, 725 where the K' source symbols consist of the original K source symbols 726 and an additional K'-K padding symbols. The internal symbol ID (ISI) 727 is used by the encoder and decoder to identify the symbols associated 728 with the extended source block, i.e., for generating encoding symbols 729 and for decoding. For a source block with K original source symbols, 730 the ISIs for the original source symbols are 0,1,2,...,K-1, the ISIs 731 for the K'-K padding symbols are K, K+1, K+2,..., K'-1, and the ISIs 732 for the repair symbols are K', K'+1, K'+2,... . Using the ISI for 733 encoding and decoding allows the padding symbols of the extended 734 source block to be treated the same way as other source symbols of 735 the extended source block, and that a given prefix of repair symbols 736 are generated in a consistent way for a given number K' of source 737 symbols in the extended source block independent of K. 739 The relationship between the ESIs and the ISIs is simple: the ESIs 740 and the ISIs for the original K source symbols are the same, the K'-K 741 padding symbols have an ISI but do not have a corresponding ESI 742 (since they are symbols that are neither sent nor received), and a 743 repair symbol ISI is simply the repair symbol ESI plus K'-K. The 744 translation between ESIs used to identify encoding symbols sent and 745 received and the corresponding ISIs used for encoding and decoding, 746 and the proper padding of the extended source block with padding 747 symbols used for encoding and decoding, is the responsibility of the 748 padding function in the RaptorG encoder/decoder. 750 5.3.2. Encoding overview 752 The systematic RaptorG encoder is used to generate any number of 753 repair symbols from a source block that consists of K source symbols 754 placed into an extended source block C'. Figure 4 shows the encoding 755 overview. 757 The first step of encoding is to construct an extended source block 758 by adding zero or more padding symbols such that the total number of 759 symbols, K', is one of the values listed in Section 5.6. Each 760 padding symbol consists of T bytes where the value of each byte is 761 zero. K' MUST be selected as the smallest value of K' from the table 762 of Section 5.6 which is greater than or equal to K. 764 -----------------------------------------------------------+ 765 | | 766 | +-----------+ +--------------+ +-------------+ | 767 C' | | | C' | Intermediate | C | | | 768 ----+--->| Padding |--->| Symbol |--->| Encoding |--+--> 769 K | | | K' | Generation | L | | | 770 | +-----------+ +--------------+ +-------------+ | 771 | | (d,a,b, ^ | 772 | | d1,a1,b1)| | 773 | | +------------+ | 774 | | K' | Tuple | | 775 | +----------------------------->| | | 776 | | Generation | | 777 | +------------+ | 778 | ^ | 779 +-------------------------------------------------+--------+ 780 | 781 ISI X 783 Figure 4: Encoding Overview 785 Let C'[0],..., C'[K-1] denote the K source symbols. 787 Let C'[K], ..., C'[K'-1] denote the K'-K padding symbols, which are 788 all set to zero bits. Then, C'[0],..., C'[K'-1] are the symbols of 789 the extended source block upon which encoding and decoding are 790 performed. 792 In the remainder of this description these padding symbols will be 793 considered as additional source symbols and referred to as such. 794 However, these padding symbols are not part of the encoding symbols, 795 i.e., they are not sent as part of the encoding. At a receiver, the 796 value of K' can be computed based on K, then the receiver can insert 797 K'-K padding symbols at the end of a source block of K' source 798 symbols and recover the remaining K source symbols of the source 799 block from received encoding symbols. 801 The second step of encoding is to generate a number, L > K', of 802 intermediate symbols from the K' source symbols. In this step, K' 803 source tuples (d[0], a[0], b[0], d1[0], a1[0], b1[0]), ..., (d[K'-1], 804 a[K'-1], b[K'-1], d1[K'-1], a1[K'-1], b1[K'-1]) are generated using 805 the Tuple[] generator as described in Section 5.3.5.4. The K' source 806 tuples and the ISIs associated with the K' source symbols are used to 807 determine L intermediate symbols C[0],..., C[L-1] from the source 808 symbols using an inverse encoding process. This process can be 809 realized by a RaptorG decoding process. 811 Certain "pre-coding relationships" must hold within the L 812 intermediate symbols. Section 5.3.3.3 describes these relationships. 813 Section 5.3.3.4 describes how the intermediate symbols are generated 814 from the source symbols. 816 Once the intermediate symbols have been generated, repair symbols can 817 be produced. For a repair symbol with ISI X>K', the tuple of 818 integers, (d, a, b, d1, a1, b1) can be generated, using the Tuple[] 819 generator as described in Section 5.3.5.4. Then, the (d, a, b, d1, 820 a1, b1)-tuple and the ISI X is used to generate the corresponding 821 repair symbol from the intermediate symbols using the Enc[] generator 822 described in Section 5.3.5.3. The corresponding ESI for this repair 823 symbol is then X-(K'-K). Note that source symbols of the extended 824 source block can also be generated using the same process, i.e., for 825 any X < K', the symbol generated using this process has the same 826 value as C'(X). 828 5.3.3. First encoding step: Intermediate Symbol Generation 830 5.3.3.1. General 832 This encoding step is a pre-coding step to generate the L 833 intermediate symbols C[0], ..., C[L-1] from the source symbols C'[0], 834 ..., C'[K'-1], , where L > K is defined in Section 5.3.3.3. The 835 intermediate symbols are uniquely defined by two sets of constraints: 837 1. The intermediate symbols are related to the source symbols by a 838 set of source symbol tuples and by the ISIs of the source 839 symbols. The generation of the source symbol tuples is defined 840 in Section 5.3.3.2 using the the Tuple[] generator as described 841 in Section 5.3.5.4. 843 2. A set of pre-coding relationships hold within the intermediate 844 symbols themselves. These are defined in Section 5.3.3.3 846 The generation of the L intermediate symbols is then defined in 847 Section 5.3.3.4 849 5.3.3.2. Source symbol tuples 851 Each of the K' source symbols is associated with a source symbol 852 tuple (d[X], a[X], b[X], d1[X], a1[X], b1[X]) for 0 <= X < K'. The 853 source symbol tuples are determined using the Tuple generator defined 854 in Section 5.3.5.4 as: 856 For each X, 0 <= X < K' 858 (d[X], a[X], b[X], d1[X], a1[X], b1[X]) = Tuple[K, X] 860 5.3.3.3. Pre-coding relationships 862 The pre-coding relationships amongst the L intermediate symbols are 863 defined by requiring that a set of S+H linear combinations of the 864 intermediate symbols evaluate to zero. There are S LDPC and H HDPC 865 symbols, and thus L = K'+S+H. Another partition of the L intermediate 866 symbols is into two sets, one set of W LT symbols and another set of 867 P PI symbols, and thus it is also the case that L = W+P. The P PI 868 symbols are treated differently than the W LT symbols in the encoding 869 process. The P PI symbols consist of the H HDPC symbols together 870 with a set of U = P-H of the other K' intermediate symbols. The W LT 871 symbols consist of the S LDPC symbols together with W-S of the other 872 K' intermediate symbols. The values of these parameters are 873 determined from K' as described below where H(K'), S(K'), and W(K') 874 are derived from Table 2 in Section 5.6. 876 Let 878 o S = S(K') 880 o H = H(K') 882 o W = W(K') 883 o L = K' + S + H 885 o P = L - W 887 o P1 denote the smallest prime number greater than or equal to P 889 o U =P - H 891 o B = W - S 893 o C[0], ..., C[B-1] denote the intermediate symbols that are LT 894 symbols but not LDPC symbols. 896 o C[B], ..., C[B+S-1] denote the S LDPC symbols that are also LT 897 symbols. 899 o C[W], ..., C[W+U-1] denote the intermediate symbols that are PI 900 symbols but not HDPC symbols. 902 o C[L-H], ..., C[L-1] denote the H HDPC symbols that are also PI 903 symbols. 905 The first set of pre-coding relations, called LDPC relations, is 906 described below and requires that at the end of this process the set 907 of symbols D[0] , ..., D[S-1] are all zero: 909 o Initialize the symbols D[0] = C[B], ... , D[S-1] = C[B+S-1]. 911 o For i = 0, ..., B-1 do 913 * a = 1 + (floor(i/S) % (S-1)) 915 * b = i % S 917 * D[b] = D[b] ^ C[i] 919 * b = (b + a) % S 921 * D[b] = D[b] ^ C[i] 923 * b = (b + a) % S 925 * D[b] = D[b] ^ C[i] 927 o For i = 0, ..., B-1 do 929 * a = i % P 930 * b = (i+1) % P 932 * D[i] = D[i] ^ C[W+a] ^ C[W+b] 934 The second set of relations, called HDPC relations, is obtained by 935 considering each intermediate symbol as a sequence of elements from 936 the finite field GF(256). We represent elements of GF(256) in the 937 usual way as polynomials in one variable, x, with coefficients from 938 the finite field GF(2) modulo an irreducible polynomial f(x). A 939 single byte of data from a symbol, b7,b6,b5,b4,b3,b2,b1,b0, where b7 940 is the highest order bit and b0 is the lowest order bit, corresponds 941 to the finite field element 943 b7 x^^7 + b6 x^^6 + b5 x^^5 + b4 x^^4 + b3 x^^3 + b2 x^^2 + b1 x + 944 b0 mod f(x) 946 The irreducible polynomial f(x) is defined to be: 948 f(x) = x^^8 + x^^4 + x^^3 + x^^2 + 1. 950 We then define the operation of elements of GF(256) on symbols as 951 follows: 953 Let 955 o beta denote an element of GF(256). 957 o C denote a symbol of length T bytes. 959 o c[0], ..., c[T-1] denote the bytes of C. 961 o gamma[0], ..., gamma[T-1] denote the elements of GF(256) 962 corresponding to c[0], ..., c[T-1] respectively. 964 Then we define 966 delta[i] = beta*gamma[i] for i=0, ..., T-1 968 where '*' represents the usual multiplication operation in GF(256). 969 A multiplication table for GF(256) and a recommended way to perform 970 calculations in GF(256) is provided in Section 5.7. Then the 971 operation of beta on C is defined as follows: 973 beta*C = d[0], ..., d[T-1] 975 where d[i] is the byte value corresponding to delta[i] for i=0,..., 976 T-1. 978 The set of HDPC relations among the intermediate symbols C[0], ..., 979 C[K'+S+H-1] is defined as follows: 981 Let 983 o alpha denote a generator element of GF(256), specifically the 984 element represented by the polynomial x mod f(x). 986 o T denote an H x (K' +S ) matrix with elements from GF(256), where 987 for j=0,...,K'+S-2 the entry T[i,j] is the identity element if i= 988 Rand[j,6,H] or i = (Rand[j,6,H] + Rand[j,7,H-1] + 1) % H and 989 T[i,j] is the zero element for all other values of i, and for 990 j=K'+S-1, T[i,j] = alpha^^i for i=0,...,H-1. 992 o GAMMA denote a (K'+S ) x (K'+S ) matrix with elements from 993 GF(256), where 995 o 997 GAMMA[i,j] = 999 alpha ^^ (i-j) for i <= j 1001 0 otherwise 1003 Then the relationship between the first K'+S intermediate symbols 1004 C[0], ..., C[K'+S-1] and the H HDPC symbols C[K'+S], ..., C[K'+S+H-1] 1005 is given by: 1007 Transpose[C[K'+S], ..., C[K'+S+H-1]] + T* GAMMA * Transpose[C[0], 1008 ..., C[K'+S-1]] = 0 1010 where '*' represents standard matrix multiplication utilizing the 1011 above defined operation to define the multiplication between a matrix 1012 over GF(256) and a matrix of symbols (in particular the column vector 1013 of symbols). 1015 The H HDPC relations may be conveniently described using the 1016 following algorithm, where u is a working register containing a 1017 single symbol. These relations require that the values of the 1018 symbols D[S], ..., D[S+H-1] are zero at the end of the following 1019 process. 1021 o Initialize the symbols D[S] = C[K'+S], ..., D[S+H-1] = C[K'+S+H-1] 1023 o u = C[0] 1024 o For j = 1, ..., K'+S-1 do 1026 * pos1 = Rand[j,6,H] 1028 * pos2 = (pos1 + Rand[j,7,H-1] + 1) % H 1030 * D[S+pos1] = D[S+pos1] ^ u 1032 * D[S+pos2] = D[S+pos2] ^ u 1034 * u = (alpha*u) ^ C[j] 1036 o For i = 0, ..., H-1 1038 * D[S+i] = D[S+i] ^ u 1040 * u = (alpha*u) 1042 5.3.3.4. Intermediate symbols 1044 5.3.3.4.1. Definition 1046 Given the K' source symbols C'[0], C'[1],..., C'[K'-1] the L 1047 intermediate symbols C[0], C[1],..., C[L-1] are the uniquely defined 1048 symbol values that satisfy the following conditions: 1050 1. The K' source symbols C'[0], C'[1],..., C'[K'-1] satisfy the K' 1051 constraints 1053 C'[X] = Enc[K', (C[0],..., C[L-1]), (d[X], a[X], b[X], d1[X], 1054 a1[X], b1[X])], for all X, 0 <= X < K', 1056 where (d[X], a[X], b[X], d1[X], a1[X], b1[X])) = Tuple[K',X], 1057 Tuple[] is defined in Section 5.3.5.4 and Enc[] is described in 1058 Section 5.3.5.3. 1060 2. The L intermediate symbols C[0], C[1],..., C[L-1] satisfy the 1061 pre-coding relationships defined in Section 5.3.3.3 1063 5.3.3.4.2. Example method for calculation of intermediate symbols 1065 This section describes a possible method for calculation of the L 1066 intermediate symbols C[0], C[1],..., C[L-1] satisfying the 1067 constraints in Section 5.3.3.4.1 1069 The generator matrix G for a code which generates n output symbols 1070 from k input symbols is an n x k matrix over GF(256), where each row 1071 corresponds to one of the output symbols and each column to one of 1072 the input symbols and where the i-th output symbol is equal to the 1073 sum of the product of each input symbol with the corresponding entry 1074 in row i. 1076 Then, the L intermediate symbols can be calculated as follows: 1078 Let 1080 o C denote the column vector of the L intermediate symbols, C[0], 1081 C[1],..., C[L-1]. 1083 o D denote the column vector consisting of S+H zero symbols followed 1084 by the K' source symbols C'[0], C'[1], ..., C'[K'-1]. 1086 Then the above constraints define an L x L matrix A over GF(256) such 1087 that: 1089 A*C = D 1091 The matrix A can be constructed as follows: 1093 Let: 1095 o G_LDPC,1 and G_LDPC,2 be S x B and S x P matrices such that 1097 G_LDPC,1 * Transpose[(C[0],...., C[B-1])] + G_LDPC,2 * 1098 Transpose(C[W], ..., C[W+U-1]) + Transpose[(C[B], ..., 1099 C[B+S-1])] = 0 1101 and "+" is the component-wise XOR of the vectors involved. 1103 o G_HDPC be the H x (K'+S) generator matrix of the HDPC symbols, So, 1105 G_HDPC * Transpose(C[0], ..., C[K'+S-1]) = Transpose(C[K'+S], 1106 ..., C[L-1]), 1108 i.e. G_HDPC = H*GAMMA 1110 o I_S be the S x S identity matrix 1112 o I_H be the H x H identity matrix 1114 o G_ENC be the K'x L generator matrix of the encoding symbols 1115 generated by the Encoder. So, 1117 G_ENC * Transpose[(C[0], ..., C[L-1])] = 1118 Transpose[(C'[0],C'[1],...,C'[K'-1])], 1119 i.e. G_ENC[i,j] = 1 if and only if C[j] is included in the 1120 symbols which are XORed to produce Enc[K', (C[0], ..., C[L-1]), 1121 (d[i], a[i], b[i], d1[i], a1[i], b1[i])] and G_ENC[i,j] = 0 1122 otherwise. 1124 Then: 1126 o The first S rows of A are equal to G_LDPC,1 | I_S | G_LDPC,2. 1128 o The next H rows of A are equal to G_HDPC | I_H. 1130 o The remaining K' rows of A are equal to G_ENC. 1132 The matrix A is depicted in Figure (Figure 5) below: 1134 B S U H 1135 +-----------------------+-------+------------------+ 1136 | | | | 1137 S | G_LDPC,1 | I_S | G_LDPC,2 | 1138 | | | | 1139 +-----------------------+-------+----------+-------+ 1140 | | | 1141 H | G_HDPC | I_H | 1142 | | | 1143 +------------------------------------------+-------+ 1144 | | 1145 | | 1146 K' | G_LT | 1147 | | 1148 | | 1149 +--------------------------------------------------+ 1151 Figure 5: The matrix A 1153 The intermediate symbols can then be calculated as: 1155 C = (A^^-1)*D 1157 The source tuples are generated such that for any K' matrix A has 1158 full rank and is therefore invertible. This calculation can be 1159 realized by applying a RaptorG decoding process to the K' source 1160 symbols C'[0], C'[1],..., C'[K'-1] to produce the L intermediate 1161 symbols C[0], C[1],..., C[L-1]. 1163 To efficiently generate the intermediate symbols from the source 1164 symbols, it is recommended that an efficient decoder implementation 1165 such as that described in Section 5.4 be used. 1167 5.3.4. Second encoding step: Encoding 1169 In the second encoding step, the repair symbol with ISI X (X >= K') 1170 is generated by applying the generator LTEnc[K', (C[0], C[1],..., 1171 C[L-1]), (d, a, b, d1, a1, b1)] defined in Section 5.3.5.3 to the L 1172 intermediate symbols C[0], C[1],..., C[L-1] using the tuple (d, a, b, 1173 d1, a1, b1)=Tuple[K',X]. 1175 5.3.5. Generators 1177 5.3.5.1. Random Generator 1179 The random number generator Rand[y, i, m] is defined as follows, 1180 where y is a non-negative integer, i is a non-negative integer less 1181 than 256, and m is a positive integer and the value produced is an 1182 integer between 0 and m-1. Let V0, V1, V2 and V3 be arrays of 256 1183 entries each, where each entry is a 4-byte unsigned integer. These 1184 arrays are provided in Section 5.5. 1186 Let 1188 o x0 = (y + i) mod 2^^8 1190 o x1 = (floor(y / 2^^8) + i) mod 2^^8 1192 o x2 = (floor(y / 2^^16) + i) mod 2^^8 1194 o x3 = (floor(y / 2^^24) + i) mod 2^^8 1196 Then, 1198 Rand[y, i, m] = (V0[x0] ^ V1[x1] ^ V2[x2] ^ V3[x3]) % m 1200 5.3.5.2. Degree Generator 1202 The degree generator Deg[v] is defined as follows, where v is an 1203 integer that is at least 0 and less than 2^^20 = 1048576. Given v, 1204 find index d in Table 1 such that f[d-1] <= v < f[d], and set Deg[v] 1205 = min(d, W-2). 1207 +---------+---------+---------+---------+ 1208 | Index d | f[d] | Index d | f[d] | 1209 +---------+---------+---------+---------+ 1210 | 0 | 0 | 1 | 5243 | 1211 +---------+---------+---------+---------+ 1212 | 2 | 529531 | 3 | 704294 | 1213 +---------+---------+---------+---------+ 1214 | 4 | 791675 | 5 | 844104 | 1215 +---------+---------+---------+---------+ 1216 | 6 | 879057 | 7 | 904023 | 1217 +---------+---------+---------+---------+ 1218 | 8 | 922747 | 9 | 937311 | 1219 +---------+---------+---------+---------+ 1220 | 10 | 948962 | 11 | 958494 | 1221 +---------+---------+---------+---------+ 1222 | 12 | 966438 | 13 | 973160 | 1223 +---------+---------+---------+---------+ 1224 | 14 | 978921 | 15 | 983914 | 1225 +---------+---------+---------+---------+ 1226 | 16 | 988283 | 17 | 992138 | 1227 +---------+---------+---------+---------+ 1228 | 18 | 995565 | 19 | 998631 | 1229 +---------+---------+---------+---------+ 1230 | 20 | 1001391 | 21 | 1003887 | 1231 +---------+---------+---------+---------+ 1232 | 22 | 1006157 | 23 | 1008229 | 1233 +---------+---------+---------+---------+ 1234 | 24 | 1010129 | 25 | 1011876 | 1235 +---------+---------+---------+---------+ 1236 | 26 | 1013490 | 27 | 1014983 | 1237 +---------+---------+---------+---------+ 1238 | 28 | 1016370 | 29 | 1017662 | 1239 +---------+---------+---------+---------+ 1240 | 30 | 1048576 | | | 1241 +---------+---------+---------+---------+ 1243 Table 1: Defines the degree distribution for encoding symbols 1245 5.3.5.3. Encoding Symbol Generator 1247 The encoding symbol generator Enc[K', (C[0], C[1],..., C[L-1]), (d, 1248 a, b, d1, a1, b1)] takes the following inputs: 1250 o K' is the number of source symbols for the extended source block. 1251 Let L, W, B, S, and P be derived from K' as described in 1252 Section 5.3.3.3. 1254 o (C[0], C[1],..., C[L-1]) is the array of L intermediate symbols 1255 (sub-symbols) generated as described in Section 5.3.3.4 1257 o (d, a, b, d1, a1, b1) is a source tuple determined from ISI X 1258 using the Tuple generator defined in Section 5.3.5.4, whereby 1260 * d is an integer denoting an encoding symbol LT degree 1262 * a is an integer between 1 and W-1 inclusive 1264 * b is an integer between 0 and W-1 inclusive 1266 * d1 is an integer between 2 and 3 inclusive denoting an encoding 1267 symbol PI degree 1269 * a1 is an integer between 1 and P1-1 inclusive 1271 * b1 is an integer between 0 and P1-1 inclusive 1273 The encoding symbol generator produces a single encoding symbol as 1274 output, according to the following algorithm: 1276 o result = C[b]. 1278 o For j = 1, ..., d-1 do 1280 * b = (b + a) % W 1282 * result = result ^ C[b] 1284 o while (b1 >= P) do b1 = (b1+a1) % P1 1286 o result = result ^ C[W+b1] 1288 o For j = 1, ..., d1-1 do 1290 * b1 = (b1 + a1) % P1 1292 * while (b1 >= P) do b1 = (b1+a1) % P1 1294 * result = result ^ C[W+b1] 1296 o Return result 1298 5.3.5.4. Tuple generator 1300 The tuple generator Tuple[K',X] takes the following inputs: 1302 o K' - The number of source symbols in the extended source block 1304 o X - An Intermediate symbol ID (ISI) 1306 Let 1308 o L be determined from K' as described in Section 5.3.3.3 1310 o Q = 4294967291, the largest prime smaller than 2^^32. 1312 o J=J(K') be the systematic index associated with K', as defined 1313 inTable 2 inSection 5.6 1315 The output of the source symbol tuple generator is a tuple, (d, a, b, 1316 d1, a1, b1) determined as follows: 1318 o A = 1 + (53591 + J*997) % Q 1320 o B = 10267*(J+1) % Q 1322 o y = (B + X*A) % Q 1324 o v = Rand[y, 0, 2^^20] 1326 o d = Deg[v] 1328 o a = 1 + Rand[y, 1, W-1] 1330 o b = Rand[y, 2, W] 1332 o if (d<4) { d1 = 2 + Rand[y, 3, 2] } else { d1 = 2 } 1334 o a1 = 1 + Rand[y, 4, P1-1] 1336 o d1 = Rand[y, 5, P1] 1338 5.4. Example FEC decoder 1340 5.4.1. General 1342 This section describes an efficient decoding algorithm for the 1343 RaptorG code introduced in this specification. Note that each 1344 received encoding symbol can be considered as the value of an 1345 equation amongst the intermediate symbols. From these simultaneous 1346 equations, and the known pre-coding relationships amongst the 1347 intermediate symbols, any algorithm for solving simultaneous 1348 equations can successfully decode the intermediate symbols and hence 1349 the source symbols. However, the algorithm chosen has a major effect 1350 on the computational efficiency of the decoding. 1352 5.4.2. Decoding an extended source block 1354 5.4.2.1. General 1356 It is assumed that the decoder knows the structure of the source 1357 block it is to decode, including the symbol size, T, and the number K 1358 of symbols in the source block and the number K' of source symbols in 1359 the extended source block. 1361 From the algorithms described in Sections Section 5.3, the RaptorG 1362 decoder can calculate the total number L = K'+S+H of intermediate 1363 symbols and determine how they were generated from the extended 1364 source block to be decoded. In this description it is assumed that 1365 the received encoding symbols for the extended source block to be 1366 decoded are passed to the decoder. Furthermore, for each such 1367 encoding symbol it is assumed that the number and set of intermediate 1368 symbols whose exclusive-or is equal to the encoding symbol is passed 1369 to the decoder. In the case of source symbols, including padding 1370 symbols, the source symbol tuples described in Section 5.3.3.2 1371 indicate the number and set of intermediate symbols which sum to give 1372 each source symbol. 1374 Let N >= K' be the number of received encoding symbols to be used for 1375 decoding, including padding symbols for an extended source block and 1376 let M = S+H+N. Then with the notation of Section 5.3.3.4.2 we have 1377 A*C=D. 1379 Decoding an extended source block is equivalent to decoding C from 1380 known A and D. It is clear that C can be decoded if and only if the 1381 rank of A is L. Once C has been decoded, missing source symbols can 1382 be obtained by using the source symbol tuples to determine the number 1383 and set of intermediate symbols which must be exclusive-ORed to 1384 obtain each missing source symbol. 1386 The first step in decoding C is to form a decoding schedule. In this 1387 step A is converted, using Gaussian elimination (using row operations 1388 and row and column reorderings) and after discarding M - L rows, into 1389 the L by L identity matrix. The decoding schedule consists of the 1390 sequence of row operations and row and column re-orderings during the 1391 Gaussian elimination process, and only depends on A and not on D. The 1392 decoding of C from D can take place concurrently with the forming of 1393 the decoding schedule, or the decoding can take place afterwards 1394 based on the decoding schedule. 1396 The correspondence between the decoding schedule and the decoding of 1397 C is as follows. Let c[0] = 0, c[1] = 1...,c[L-1] = L-1 and d[0] = 1398 0, d[1] = 1...,d[M-1] = M-1 initially. 1400 o Each time a multiple, beta, of row i of A is added to row i' in 1401 the decoding schedule then in the decoding process the symbol 1402 beta*D[d[i]] is added to symbol D[d[i']] . 1404 o Each time a row i of A is multiplied by a field element beta, then 1405 in the decoding process the symbol D[d[i]] is also multiplied by 1406 beta. 1408 o Each time row i is exchanged with row i' in the decoding schedule 1409 then in the decoding process the value of d[i] is exchanged with 1410 the value of d[i']. 1412 o Each time column j is exchanged with column j' in the decoding 1413 schedule then in the decoding process the value of c[j] is 1414 exchanged with the value of c[j']. 1416 From this correspondence it is clear that the total number of 1417 operations on symbols in the decoding of the extended source block is 1418 the number of row operations (not exchanges) in the Gaussian 1419 elimination. Since A is the L by L identity matrix after the 1420 Gaussian elimination and after discarding the last M - L rows, it is 1421 clear at the end of successful decoding that the L symbols D[d[0]], 1422 D[d[1]],..., D[d[L-1]] are the values of the L symbols C[c[0]], 1423 C[c[1]],..., C[c[L-1]]. 1425 The order in which Gaussian elimination is performed to form the 1426 decoding schedule has no bearing on whether or not the decoding is 1427 successful. However, the speed of the decoding depends heavily on 1428 the order in which Gaussian elimination is performed. (Furthermore, 1429 maintaining a sparse representation of A is crucial, although this is 1430 not described here). The remainder of this section describes an 1431 order in which Gaussian elimination could be performed that is 1432 relatively efficient. 1434 5.4.2.2. First Phase 1436 The first phase of the Gaussian elimination the matrix A is 1437 conceptually partitioned into submatrices and additionally, a matrix 1438 X is created. This matrix has as many rows and columns as A, and it 1439 will be a lower triangular matrix throughout the first phase. At the 1440 beginning of this phase, the matrix A is copied into the matrix X. 1441 The submatrix sizes are parameterized by non-negative integers i and 1442 u which are initialized to 0 and P, the number of PI symbols, 1443 respectively. The submatrices of A are: 1445 1. The submatrix I defined by the intersection of the first i rows 1446 and first i columns. This is the identity matrix at the end of 1447 each step in the phase. 1449 2. The submatrix defined by the intersection of the first i rows and 1450 all but the first i columns and last u columns. All entries of 1451 this submatrix are zero. 1453 3. The submatrix defined by the intersection of the first i columns 1454 and all but the first i rows. All entries of this submatrix are 1455 zero. 1457 4. The submatrix U defined by the intersection of all the rows and 1458 the last u columns. 1460 5. The submatrix V formed by the intersection of all but the first i 1461 columns and the last u columns and all but the first i rows. 1463 Figure 6 illustrates the submatrices of A. At the beginning of the 1464 first phase V = A. In each step, a row of A is chosen. 1466 +-----------+-----------------+---------+ 1467 | | | | 1468 | I | All Zeros | | 1469 | | | | 1470 +-----------+-----------------+ U | 1471 | | | | 1472 | | | | 1473 | All Zeros | V | | 1474 | | | | 1475 | | | | 1476 +-----------+-----------------+---------+ 1478 Figure 6: Submatrices of A in the first phase 1480 The following graph defined by the structure of V is used in 1481 determining which row of A is chosen. The columns that intersect V 1482 are the nodes in the graph, and the rows that have exactly 2 non-zero 1483 entries in V and are not HDPC rows are the edges of the graph that 1484 connect the two columns (nodes) in the positions of the two ones. A 1485 component in this graph is a maximal set of nodes (columns) and edges 1486 (rows) such that there is a path between each pair of nodes/edges in 1487 the graph. The size of a component is the number of nodes (columns) 1488 in the component. 1490 There are at most L steps in the first phase. The phase ends 1491 successfully when i + u = L, i.e., when V and the all zeroes 1492 submatrix above V have disappeared and A consists of I, the all 1493 zeroes submatrix below I, and U. The phase ends unsuccessfully in 1494 decoding failure if at some step before V disappears there is no non- 1495 zero row in V to choose in that step. In each step, a row of A is 1496 chosen as follows: 1498 o If all entries of V are zero then no row is chosen and decoding 1499 fails. 1501 o Let r be the minimum integer such that at least one row of A has 1502 exactly r ones in V. 1504 * If r != 2 then choose a row with exactly r ones in V with 1505 minimum original degree among all such rows, except that HDPC 1506 rows should not be chosen until all non-HDPC rows have been 1507 processed. 1509 * If r = 2 then choose any row with exactly 2 ones in V that is 1510 part of a maximum size component in the graph described above 1511 which is defined by V. 1513 After the row is chosen in this step the first row of A that 1514 intersects V is exchanged with the chosen row so that the chosen row 1515 is the first row that intersects V. The columns of A among those that 1516 intersect V are reordered so that one of the r ones in the chosen row 1517 appears in the first column of V and so that the remaining r-1 ones 1518 appear in the last columns of V. The same row and column operations 1519 are also performed on the matrix X. Then, an appropriate multiple of 1520 the chosen row is added to all the other rows of A below the chosen 1521 row that have a non-zero entry in the first column of V. 1522 Specifically, if a row below the chosen row has entry beta in the 1523 first column of V, and the chosen row has entry alpha in the first 1524 column of V, then beta/alpha multiplied by the chosen row is added to 1525 this row to leave a zero value in the first column of V. Finally, i 1526 is incremented by 1 and u is incremented by r-1, which completes the 1527 step. 1529 Note that efficiency can be improved if the row operations identified 1530 above are not actually performed until the affected row is itself 1531 chosen during the decoding process. This avoids processing of row 1532 operations for rows which are not eventually used in the decoding 1533 process and in particular avoid those rows for which beta!=1 until 1534 they are actually required. Furthermore, the row operations required 1535 for the HDPC rows may be performed for all such rows in one process, 1536 by using the algorithm described in Section 5.3.3.3. 1538 5.4.2.3. Second Phase 1540 At this point, all the entries of X outside the first i rows and i 1541 columns are discarded, so that X has lower triangular form. The last 1542 i rows and columns of X are discarded, so that X now has i rows i 1543 columns. The submatrix U is further partitioned into the first i 1544 rows, U_upper, and the remaining M - i rows, Ulower. Gaussian 1545 elimination is performed in the second phase on U_lower to either 1546 determine that its rank is less than u (decoding failure) or to 1547 convert it into a matrix where the first u rows is the identity 1548 matrix (success of the second phase). Call this u by u identity 1549 matrix I_u. The M - L rows of A that intersect U_lower - I_u are 1550 discarded. After this phase A has L rows and L columns. 1552 5.4.2.4. Third Phase 1554 After the second phase the only portion of A which needs to be zeroed 1555 out to finish converting A into the L by L identity matrix is 1556 U_upper. The number of rows i of the submatrix U_upper is generally 1557 much larger than the number of columns u of U_upper. Moreover, at 1558 this time, the matrix U_upper is typically dense, i.e., the number of 1559 nonzero entries of this matrix is large. To reduce this matrix to a 1560 sparse form, the sequence of operations performed to obtain the 1561 matrix U_lower needs to be inverted. To this end, the matrix X is 1562 multiplied with the submatrix of A consisting of the first i rows of 1563 A. After this operation the submatrix of A consisting of the 1564 intersection of the first i rows and columns equals to X, whereas the 1565 matrix U_upper is transformed to a sparse form. 1567 5.4.2.5. Fourth Phase 1569 For each of the first i rows of U_upper do the following: if the row 1570 has a nonzero entry at position j, and if the value of that nonzero 1571 entry is b, then add to this row b times row j of I_u. After this 1572 step, the submatrix of A consisting of the intersection of the first 1573 i rows and columns is equal to X, the submatrix U_upper consists of 1574 zeros, the submatrix consisting of the intersection of the last u 1575 rows and the first i columns consists of zeros, and the submatrix 1576 consisting of the last u rows and columns is is the matrix I_u. 1578 5.4.2.6. Fifth Phase 1580 For j from 1 to i perform the following operations: 1582 1. if A[j,j] is not one, then divide row j of A by A[j,j]. 1584 2. For l from 1 to j-1, if A[j,l] is nonzero, then add A[j,l] 1585 multiplied with row l of A to row j of A. 1587 After this phase A is the L by L identity matrix and a complete 1588 decoding schedule has been successfully formed. Then, the 1589 corresponding decoding consisting of exclusive-ORing known encoding 1590 symbols can be executed to recover the intermediate symbols based on 1591 the decoding schedule. The tuples associated with all source symbols 1592 are computed according to Section 5.3.3.2. The tuples for received 1593 source symbols are used in the decoding. The tuples for missing 1594 source symbols are used to determine which intermediate symbols need 1595 to be exclusive-ORed to recover the missing source symbols. 1597 5.5. Random Numbers 1599 The four tables V0, V1, V2 and V3 described in Section 5.3.5.1 are 1600 given below. Each entry is a 32-bit integer in decimal 1601 representation. 1603 5.5.1. The table V0 1605 251291136, 3952231631, 3370958628, 4070167936, 123631495, 3351110283, 1606 3218676425, 2011642291, 774603218, 2402805061, 1004366930, 1607 1843948209, 428891132, 3746331984, 1591258008, 3067016507, 1608 1433388735, 504005498, 2032657933, 3419319784, 2805686246, 1609 3102436986, 3808671154, 2501582075, 3978944421, 246043949, 1610 4016898363, 649743608, 1974987508, 2651273766, 2357956801, 689605112, 1611 715807172, 2722736134, 191939188, 3535520147, 3277019569, 1470435941, 1612 3763101702, 3232409631, 122701163, 3920852693, 782246947, 372121310, 1613 2995604341, 2045698575, 2332962102, 4005368743, 218596347, 1614 3415381967, 4207612806, 861117671, 3676575285, 2581671944, 1615 3312220480, 681232419, 307306866, 4112503940, 1158111502, 709227802, 1616 2724140433, 4201101115, 4215970289, 4048876515, 3031661061, 1617 1909085522, 510985033, 1361682810, 129243379, 3142379587, 2569842483, 1618 3033268270, 1658118006, 932109358, 1982290045, 2983082771, 1619 3007670818, 3448104768, 683749698, 778296777, 1399125101, 1939403708, 1620 1692176003, 3868299200, 1422476658, 593093658, 1878973865, 1621 2526292949, 1591602827, 3986158854, 3964389521, 2695031039, 1622 1942050155, 424618399, 1347204291, 2669179716, 2434425874, 1623 2540801947, 1384069776, 4123580443, 1523670218, 2708475297, 1624 1046771089, 2229796016, 1255426612, 4213663089, 1521339547, 1625 3041843489, 420130494, 10677091, 515623176, 3457502702, 2115821274, 1626 2720124766, 3242576090, 854310108, 425973987, 325832382, 1796851292, 1627 2462744411, 1976681690, 1408671665, 1228817808, 3917210003, 1628 263976645, 2593736473, 2471651269, 4291353919, 650792940, 1191583883, 1629 3046561335, 2466530435, 2545983082, 969168436, 2019348792, 1630 2268075521, 1169345068, 3250240009, 3963499681, 2560755113, 1631 911182396, 760842409, 3569308693, 2687243553, 381854665, 2613828404, 1632 2761078866, 1456668111, 883760091, 3294951678, 1604598575, 1633 1985308198, 1014570543, 2724959607, 3062518035, 3115293053, 1634 138853680, 4160398285, 3322241130, 2068983570, 2247491078, 1635 3669524410, 1575146607, 828029864, 3732001371, 3422026452, 1636 3370954177, 4006626915, 543812220, 1243116171, 3928372514, 1637 2791443445, 4081325272, 2280435605, 885616073, 616452097, 3188863436, 1638 2780382310, 2340014831, 1208439576, 258356309, 3837963200, 1639 2075009450, 3214181212, 3303882142, 880813252, 1355575717, 207231484, 1640 2420803184, 358923368, 1617557768, 3272161958, 1771154147, 1641 2842106362, 1751209208, 1421030790, 658316681, 194065839, 3241510581, 1642 38625260, 301875395, 4176141739, 297312930, 2137802113, 1502984205, 1643 3669376622, 3728477036, 234652930, 2213589897, 2734638932, 1644 1129721478, 3187422815, 2859178611, 3284308411, 3819792700, 1645 3557526733, 451874476, 1740576081, 3592838701, 1709429513, 1646 3702918379, 3533351328, 1641660745, 179350258, 2380520112, 1647 3936163904, 3685256204, 3156252216, 1854258901, 2861641019, 1648 3176611298, 834787554, 331353807, 517858103, 3010168884, 4012642001, 1649 2217188075, 3756943137, 3077882590, 2054995199, 3081443129, 1650 3895398812, 1141097543, 2376261053, 2626898255, 2554703076, 1651 401233789, 1460049922, 678083952, 1064990737, 940909784, 1673396780, 1652 528881783, 1712547446, 3629685652, 1358307511 1654 5.5.2. The table V1 1656 807385413, 2043073223, 3336749796, 1302105833, 2278607931, 541015020, 1657 1684564270, 372709334, 3508252125, 1768346005, 1270451292, 1658 2603029534, 2049387273, 3891424859, 2152948345, 4114760273, 1659 915180310, 3754787998, 700503826, 2131559305, 1308908630, 224437350, 1660 4065424007, 3638665944, 1679385496, 3431345226, 1779595665, 1661 3068494238, 1424062773, 1033448464, 4050396853, 3302235057, 1662 420600373, 2868446243, 311689386, 259047959, 4057180909, 1575367248, 1663 4151214153, 110249784, 3006865921, 4293710613, 3501256572, 998007483, 1664 499288295, 1205710710, 2997199489, 640417429, 3044194711, 486690751, 1665 2686640734, 2394526209, 2521660077, 49993987, 3843885867, 4201106668, 1666 415906198, 19296841, 2402488407, 2137119134, 1744097284, 579965637, 1667 2037662632, 852173610, 2681403713, 1047144830, 2982173936, 910285038, 1668 4187576520, 2589870048, 989448887, 3292758024, 506322719, 176010738, 1669 1865471968, 2619324712, 564829442, 1996870325, 339697593, 4071072948, 1670 3618966336, 2111320126, 1093955153, 957978696, 892010560, 1854601078, 1671 1873407527, 2498544695, 2694156259, 1927339682, 1650555729, 1672 183933047, 3061444337, 2067387204, 228962564, 3904109414, 1595995433, 1673 1780701372, 2463145963, 307281463, 3237929991, 3852995239, 1674 2398693510, 3754138664, 522074127, 146352474, 4104915256, 3029415884, 1675 3545667983, 332038910, 976628269, 3123492423, 3041418372, 2258059298, 1676 2139377204, 3243642973, 3226247917, 3674004636, 2698992189, 1677 3453843574, 1963216666, 3509855005, 2358481858, 747331248, 1678 1957348676, 1097574450, 2435697214, 3870972145, 1888833893, 1679 2914085525, 4161315584, 1273113343, 3269644828, 3681293816, 1680 412536684, 1156034077, 3823026442, 1066971017, 3598330293, 1681 1979273937, 2079029895, 1195045909, 1071986421, 2712821515, 1682 3377754595, 2184151095, 750918864, 2585729879, 4249895712, 1683 1832579367, 1192240192, 946734366, 31230688, 3174399083, 3549375728, 1684 1642430184, 1904857554, 861877404, 3277825584, 4267074718, 1685 3122860549, 666423581, 644189126, 226475395, 307789415, 1196105631, 1686 3191691839, 782852669, 1608507813, 1847685900, 4069766876, 1687 3931548641, 2526471011, 766865139, 2115084288, 4259411376, 1688 3323683436, 568512177, 3736601419, 1800276898, 4012458395, 1823982, 1689 27980198, 2023839966, 869505096, 431161506, 1024804023, 1853869307, 1690 3393537983, 1500703614, 3019471560, 1351086955, 3096933631, 1691 3034634988, 2544598006, 1230942551, 3362230798, 159984793, 491590373, 1692 3993872886, 3681855622, 903593547, 3535062472, 1799803217, 772984149, 1693 895863112, 1899036275, 4187322100, 101856048, 234650315, 3183125617, 1694 3190039692, 525584357, 1286834489, 455810374, 1869181575, 922673938, 1695 3877430102, 3422391938, 1414347295, 1971054608, 3061798054, 1696 830555096, 2822905141, 167033190, 1079139428, 4210126723, 3593797804, 1697 429192890, 372093950, 1779187770, 3312189287, 204349348, 452421568, 1698 2800540462, 3733109044, 1235082423, 1765319556, 3174729780, 1699 3762994475, 3171962488, 442160826, 198349622, 45942637, 1324086311, 1700 2901868599, 678860040, 3812229107, 19936821, 1119590141, 3640121682, 1701 3545931032, 2102949142, 2828208598, 3603378023, 4135048896 1703 5.5.3. The table V2 1705 1629829892, 282540176, 2794583710, 496504798, 2990494426, 3070701851, 1706 2575963183, 4094823972, 2775723650, 4079480416, 176028725, 1707 2246241423, 3732217647, 2196843075, 1306949278, 4170992780, 1708 4039345809, 3209664269, 3387499533, 293063229, 3660290503, 1709 2648440860, 2531406539, 3537879412, 773374739, 4184691853, 1710 1804207821, 3347126643, 3479377103, 3970515774, 1891731298, 1711 2368003842, 3537588307, 2969158410, 4230745262, 831906319, 1712 2935838131, 264029468, 120852739, 3200326460, 355445271, 2296305141, 1713 1566296040, 1760127056, 20073893, 3427103620, 2866979760, 2359075957, 1714 2025314291, 1725696734, 3346087406, 2690756527, 99815156, 4248519977, 1715 2253762642, 3274144518, 598024568, 3299672435, 556579346, 4121041856, 1716 2896948975, 3620123492, 918453629, 3249461198, 2231414958, 1717 3803272287, 3657597946, 2588911389, 242262274, 1725007475, 1718 2026427718, 46776484, 2873281403, 2919275846, 3177933051, 1918859160, 1719 2517854537, 1857818511, 3234262050, 479353687, 200201308, 2801945841, 1720 1621715769, 483977159, 423502325, 3689396064, 1850168397, 3359959416, 1721 3459831930, 841488699, 3570506095, 930267420, 1564520841, 2505122797, 1722 593824107, 1116572080, 819179184, 3139123629, 1414339336, 1076360795, 1723 512403845, 177759256, 1701060666, 2239736419, 515179302, 2935012727, 1724 3821357612, 1376520851, 2700745271, 966853647, 1041862223, 715860553, 1725 171592961, 1607044257, 1227236688, 3647136358, 1417559141, 1726 4087067551, 2241705880, 4194136288, 1439041934, 20464430, 119668151, 1727 2021257232, 2551262694, 1381539058, 4082839035, 498179069, 311508499, 1728 3580908637, 2889149671, 142719814, 1232184754, 3356662582, 1729 2973775623, 1469897084, 1728205304, 1415793613, 50111003, 3133413359, 1730 4074115275, 2710540611, 2700083070, 2457757663, 2612845330, 1731 3775943755, 2469309260, 2560142753, 3020996369, 1691667711, 1732 4219602776, 1687672168, 1017921622, 2307642321, 368711460, 1733 3282925988, 213208029, 4150757489, 3443211944, 2846101972, 1734 4106826684, 4272438675, 2199416468, 3710621281, 497564971, 285138276, 1735 765042313, 916220877, 3402623607, 2768784621, 1722849097, 3386397442, 1736 487920061, 3569027007, 3424544196, 217781973, 2356938519, 3252429414, 1737 145109750, 2692588106, 2454747135, 1299493354, 4120241887, 1738 2088917094, 932304329, 1442609203, 952586974, 3509186750, 753369054, 1739 854421006, 1954046388, 2708927882, 4047539230, 3048925996, 1740 1667505809, 805166441, 1182069088, 4265546268, 4215029527, 1741 3374748959, 373532666, 2454243090, 2371530493, 3651087521, 1742 2619878153, 1651809518, 1553646893, 1227452842, 703887512, 1743 3696674163, 2552507603, 2635912901, 895130484, 3287782244, 1744 3098973502, 990078774, 3780326506, 2290845203, 41729428, 1949580860, 1745 2283959805, 1036946170, 1694887523, 4880696, 466000198, 2765355283, 1746 3318686998, 1266458025, 3919578154, 3545413527, 2627009988, 1747 3744680394, 1696890173, 3250684705, 4142417708, 915739411, 1748 3308488877, 1289361460, 2942552331, 1169105979, 3342228712, 1749 698560958, 1356041230, 2401944293, 107705232, 3701895363, 903928723, 1750 3646581385, 844950914, 1944371367, 3863894844, 2946773319, 1751 1972431613, 1706989237, 29917467, 3497665928 1753 5.5.4. The table V3 1755 1191369816, 744902811, 2539772235, 3213192037, 3286061266, 1756 1200571165, 2463281260, 754888894, 714651270, 1968220972, 3628497775, 1757 1277626456, 1493398934, 364289757, 2055487592, 3913468088, 1758 2930259465, 902504567, 3967050355, 2056499403, 692132390, 186386657, 1759 832834706, 859795816, 1283120926, 2253183716, 3003475205, 1755803552, 1760 2239315142, 4271056352, 2184848469, 769228092, 1249230754, 1761 1193269205, 2660094102, 642979613, 1687087994, 2726106182, 446402913, 1762 4122186606, 3771347282, 37667136, 192775425, 3578702187, 1952659096, 1763 3989584400, 3069013882, 2900516158, 4045316336, 3057163251, 1764 1702104819, 4116613420, 3575472384, 2674023117, 1409126723, 1765 3215095429, 1430726429, 2544497368, 1029565676, 1855801827, 1766 4262184627, 1854326881, 2906728593, 3277836557, 2787697002, 1767 2787333385, 3105430738, 2477073192, 748038573, 1088396515, 1768 1611204853, 201964005, 3745818380, 3654683549, 3816120877, 1769 3915783622, 2563198722, 1181149055, 33158084, 3723047845, 3790270906, 1770 3832415204, 2959617497, 372900708, 1286738499, 1932439099, 1771 3677748309, 2454711182, 2757856469, 2134027055, 2780052465, 1772 3190347618, 3758510138, 3626329451, 1120743107, 1623585693, 1773 1389834102, 2719230375, 3038609003, 462617590, 260254189, 3706349764, 1774 2556762744, 2874272296, 2502399286, 4216263978, 2683431180, 1775 2168560535, 3561507175, 668095726, 680412330, 3726693946, 4180630637, 1776 3335170953, 942140968, 2711851085, 2059233412, 4265696278, 1777 3204373534, 232855056, 881788313, 2258252172, 2043595984, 3758795150, 1778 3615341325, 2138837681, 1351208537, 2923692473, 3402482785, 1779 2105383425, 2346772751, 499245323, 3417846006, 2366116814, 1780 2543090583, 1828551634, 3148696244, 3853884867, 1364737681, 1781 2200687771, 2689775688, 232720625, 4071657318, 2671968983, 1782 3531415031, 1212852141, 867923311, 3740109711, 1923146533, 1783 3237071777, 3100729255, 3247856816, 906742566, 4047640575, 1784 4007211572, 3495700105, 1171285262, 2835682655, 1634301229, 1785 3115169925, 2289874706, 2252450179, 944880097, 371933491, 1649074501, 1786 2208617414, 2524305981, 2496569844, 2667037160, 1257550794, 1787 3399219045, 3194894295, 1643249887, 342911473, 891025733, 3146861835, 1788 3789181526, 938847812, 1854580183, 2112653794, 2960702988, 1789 1238603378, 2205280635, 1666784014, 2520274614, 3355493726, 1790 2310872278, 3153920489, 2745882591, 1200203158, 3033612415, 1791 2311650167, 1048129133, 4206710184, 4209176741, 2640950279, 1792 2096382177, 4116899089, 3631017851, 4104488173, 1857650503, 1793 3801102932, 445806934, 3055654640, 897898279, 3234007399, 1325494930, 1794 2982247189, 1619020475, 2720040856, 885096170, 3485255499, 1795 2983202469, 3891011124, 546522756, 1524439205, 2644317889, 1796 2170076800, 2969618716, 961183518, 1081831074, 1037015347, 1797 3289016286, 2331748669, 620887395, 303042654, 3990027945, 1562756376, 1798 3413341792, 2059647769, 2823844432, 674595301, 2457639984, 1799 4076754716, 2447737904, 1583323324, 625627134, 3076006391, 345777990, 1800 1684954145, 879227329, 3436182180, 1522273219, 3802543817, 1801 1456017040, 1897819847, 2970081129, 1382576028, 3820044861, 1802 1044428167, 612252599, 3340478395, 2150613904, 3397625662, 1803 3573635640, 3432275192 1805 5.6. Systematic indices and other parameters 1807 Table 2 below specifies the supported values of K'. The table also 1808 specifies for each supported value of K' the systematic index J(K'), 1809 the number H(K') of HDPC symbols, the number S(K') of LDPC symbols, 1810 and the number W(K') of LT symbols. For each value of K', the 1811 corresponding values of S(K') and W(K') are prime numbers. 1813 The systematic index J(K') is designed to have the property that the 1814 set of source symbol tuples (d[0], a[0], b[0], d1[0], a1[0], b1[0]), 1815 ..., (d[K'-1], a[K'-1], b[K'-1], d1[K'-1], a1[K'-1], b1[K'-1]) are 1816 such that the L intermediate symbols are uniquely defined, i.e., the 1817 matrix A in Figure 6 has full rank and is therefore invertible. 1819 +-------+-------+-------+-------+-------+ 1820 | K' | J(K') | S(K') | H(K') | W(K') | 1821 +-------+-------+-------+-------+-------+ 1822 | 6 | 3 | 5 | 10 | 11 | 1823 +-------+-------+-------+-------+-------+ 1824 | 12 | 57 | 7 | 10 | 19 | 1825 +-------+-------+-------+-------+-------+ 1826 | 18 | 27 | 11 | 10 | 29 | 1827 | 26 | 96 | 11 | 10 | 37 | 1828 +-------+-------+-------+-------+-------+ 1829 | 32 | 959 | 11 | 10 | 43 | 1830 +-------+-------+-------+-------+-------+ 1831 | 36 | 564 | 11 | 10 | 47 | 1832 +-------+-------+-------+-------+-------+ 1833 | 42 | 39 | 11 | 10 | 53 | 1834 +-------+-------+-------+-------+-------+ 1835 | 48 | 10 | 13 | 10 | 61 | 1836 +-------+-------+-------+-------+-------+ 1837 | 55 | 531 | 13 | 10 | 67 | 1838 +-------+-------+-------+-------+-------+ 1839 | 62 | 55 | 13 | 10 | 73 | 1840 +-------+-------+-------+-------+-------+ 1841 | 69 | 235 | 13 | 10 | 79 | 1842 +-------+-------+-------+-------+-------+ 1843 | 75 | 234 | 17 | 10 | 89 | 1844 +-------+-------+-------+-------+-------+ 1845 | 88 | 113 | 17 | 10 | 101 | 1846 +-------+-------+-------+-------+-------+ 1847 | 101 | 8 | 17 | 10 | 113 | 1848 +-------+-------+-------+-------+-------+ 1849 | 114 | 8 | 19 | 10 | 127 | 1850 +-------+-------+-------+-------+-------+ 1851 | 127 | 184 | 19 | 10 | 139 | 1852 +-------+-------+-------+-------+-------+ 1853 | 140 | 7 | 19 | 10 | 151 | 1854 +-------+-------+-------+-------+-------+ 1855 | 160 | 39 | 23 | 10 | 173 | 1856 +-------+-------+-------+-------+-------+ 1857 | 185 | 751 | 23 | 10 | 197 | 1858 +-------+-------+-------+-------+-------+ 1859 | 213 | 1 | 23 | 10 | 223 | 1860 +-------+-------+-------+-------+-------+ 1861 | 242 | 10 | 29 | 10 | 257 | 1862 +-------+-------+-------+-------+-------+ 1863 | 267 | 195 | 29 | 10 | 281 | 1864 +-------+-------+-------+-------+-------+ 1865 | 295 | 572 | 29 | 10 | 307 | 1866 +-------+-------+-------+-------+-------+ 1867 | 324 | 447 | 31 | 10 | 337 | 1868 +-------+-------+-------+-------+-------+ 1869 | 362 | 751 | 31 | 10 | 373 | 1870 +-------+-------+-------+-------+-------+ 1871 | 403 | 234 | 37 | 10 | 419 | 1872 +-------+-------+-------+-------+-------+ 1873 | 443 | 974 | 37 | 10 | 457 | 1874 +-------+-------+-------+-------+-------+ 1875 +-------+-------+-------+-------+-------+ 1876 | 497 | 115 | 37 | 10 | 509 | 1877 +-------+-------+-------+-------+-------+ 1878 | 555 | 17 | 41 | 10 | 569 | 1879 +-------+-------+-------+-------+-------+ 1880 | 619 | 75 | 41 | 10 | 631 | 1881 +-------+-------+-------+-------+-------+ 1882 | 685 | 476 | 47 | 10 | 701 | 1883 +-------+-------+-------+-------+-------+ 1884 | 759 | 112 | 47 | 10 | 773 | 1885 +-------+-------+-------+-------+-------+ 1886 | 839 | 454 | 53 | 10 | 857 | 1887 +-------+-------+-------+-------+-------+ 1888 | 932 | 424 | 53 | 10 | 947 | 1889 +-------+-------+-------+-------+-------+ 1890 | 1032 | 34 | 59 | 10 | 1051 | 1891 +-------+-------+-------+-------+-------+ 1892 | 1144 | 600 | 61 | 11 | 1163 | 1893 +-------+-------+-------+-------+-------+ 1894 | 1281 | 75 | 67 | 11 | 1303 | 1895 +-------+-------+-------+-------+-------+ 1896 | 1420 | 726 | 67 | 11 | 1439 | 1897 +-------+-------+-------+-------+-------+ 1898 | 1575 | 39 | 73 | 11 | 1597 | 1899 +-------+-------+-------+-------+-------+ 1900 | 1734 | 83 | 79 | 11 | 1759 | 1901 +-------+-------+-------+-------+-------+ 1902 | 1906 | 394 | 83 | 11 | 1931 | 1903 +-------+-------+-------+-------+-------+ 1904 | 2103 | 75 | 89 | 11 | 2131 | 1905 +-------+-------+-------+-------+-------+ 1906 | 2315 | 772 | 97 | 11 | 2347 | 1907 +-------+-------+-------+-------+-------+ 1908 | 2550 | 726 | 97 | 11 | 2579 | 1909 +-------+-------+-------+-------+-------+ 1910 | 2812 | 683 | 103 | 11 | 2843 | 1911 +-------+-------+-------+-------+-------+ 1912 | 3101 | 512 | 113 | 11 | 3137 | 1913 +-------+-------+-------+-------+-------+ 1914 | 3411 | 650 | 127 | 11 | 3457 | 1915 +-------+-------+-------+-------+-------+ 1916 | 3751 | 838 | 127 | 11 | 3793 | 1917 +-------+-------+-------+-------+-------+ 1918 | 4086 | 547 | 131 | 11 | 4127 | 1919 +-------+-------+-------+-------+-------+ 1920 | 4436 | 305 | 139 | 11 | 4481 | 1921 +-------+-------+-------+-------+-------+ 1922 | 4780 | 3 | 149 | 11 | 4831 | 1923 | 5134 | 518 | 157 | 11 | 5189 | 1924 +-------+-------+-------+-------+-------+ 1925 | 5512 | 229 | 163 | 11 | 5569 | 1926 +-------+-------+-------+-------+-------+ 1927 | 6070 | 980 | 173 | 11 | 6131 | 1928 +-------+-------+-------+-------+-------+ 1929 | 6688 | 596 | 191 | 11 | 6761 | 1930 +-------+-------+-------+-------+-------+ 1931 | 7360 | 960 | 197 | 11 | 7433 | 1932 +-------+-------+-------+-------+-------+ 1933 | 8087 | 85 | 211 | 11 | 8167 | 1934 +-------+-------+-------+-------+-------+ 1935 | 8886 | 479 | 223 | 11 | 8971 | 1936 +-------+-------+-------+-------+-------+ 1937 | 9793 | 200 | 239 | 11 | 9887 | 1938 +-------+-------+-------+-------+-------+ 1939 | 10779 | 290 | 257 | 11 | 10883 | 1940 +-------+-------+-------+-------+-------+ 1941 | 11864 | 543 | 277 | 12 | 11981 | 1942 +-------+-------+-------+-------+-------+ 1943 | 13046 | 893 | 293 | 12 | 13171 | 1944 +-------+-------+-------+-------+-------+ 1945 | 14355 | 527 | 311 | 12 | 14489 | 1946 +-------+-------+-------+-------+-------+ 1947 | 15786 | 601 | 337 | 12 | 15937 | 1948 +-------+-------+-------+-------+-------+ 1949 | 17376 | 479 | 359 | 12 | 17539 | 1950 +-------+-------+-------+-------+-------+ 1951 | 19126 | 518 | 389 | 12 | 19309 | 1952 +-------+-------+-------+-------+-------+ 1953 | 21044 | 933 | 419 | 13 | 21247 | 1954 +-------+-------+-------+-------+-------+ 1955 | 23177 | 85 | 449 | 13 | 23399 | 1956 +-------+-------+-------+-------+-------+ 1957 | 25491 | 710 | 479 | 13 | 25733 | 1958 +-------+-------+-------+-------+-------+ 1959 | 28035 | 11 | 521 | 13 | 28319 | 1960 +-------+-------+-------+-------+-------+ 1961 | 30898 | 738 | 557 | 14 | 31219 | 1962 +-------+-------+-------+-------+-------+ 1963 | 33988 | 602 | 599 | 14 | 34351 | 1964 +-------+-------+-------+-------+-------+ 1965 | 37372 | 545 | 647 | 14 | 37783 | 1966 +-------+-------+-------+-------+-------+ 1967 | 41127 | 11 | 701 | 15 | 41593 | 1968 +-------+-------+-------+-------+-------+ 1969 | 45245 | 639 | 757 | 15 | 45767 | 1970 +-------+-------+-------+-------+-------+ 1971 +-------+-------+-------+-------+-------+ 1972 | 49791 | 249 | 821 | 15 | 50377 | 1973 +-------+-------+-------+-------+-------+ 1974 | 54768 | 300 | 877 | 16 | 55411 | 1975 +-------+-------+-------+-------+-------+ 1976 | 56404 | 733 | 907 | 16 | 57077 | 1977 +-------+-------+-------+-------+-------+ 1979 Table 2: Systematic indices and other parameters 1981 5.7. Arithmetic in GF(256) 1983 5.7.1. Introduction 1985 Elements of GF(256) are represented by bytes. In this section, we 1986 opt to represent them by integers in the range 0 through 255. For 1987 ease of exposition, operations in GF(256) are facilitated by two 1988 tables: GF256_EXP, and GF256_LOG. GF256_EXP has 512 entries, whereas 1989 GF256_LOG has 256 entries. For an integer i between 0 and 511, 1990 GF256_EXP[i] is the binary value of the polynomial x^^i modulo x^^8 + 1991 x^^4 + x^^3 + x^^2 + 1, whereas for i between 1 and 255 the value of 1992 GF256_LOG[i] is the integer j such that the binary value of x^^j 1993 modulo x^^8 + x^^4 + x^^3 + x^^2 + 1 is i. In this representation we 1994 have 1996 i + j = i ^ j, and 1998 i * j = 2000 0, if either i or j are 0, 2002 GF256_EXP[GF256_LOG[i] + GF256_LOG[j]] otherwise 2004 5.7.2. The table GF256_EXP 2006 1, 2, 4, 8, 16, 32, 64, 128, 29, 58, 116, 232, 205, 135, 19, 38, 76, 2007 152, 45, 90, 180, 117, 234, 201, 143, 3, 6, 12, 24, 48, 96, 192, 157, 2008 39, 78, 156, 37, 74, 148, 53, 106, 212, 181, 119, 238, 193, 159, 35, 2009 70, 140, 5, 10, 20, 40, 80, 160, 93, 186, 105, 210, 185, 111, 222, 2010 161, 95, 190, 97, 194, 153, 47, 94, 188, 101, 202, 137, 15, 30, 60, 2011 120, 240, 253, 231, 211, 187, 107, 214, 177, 127, 254, 225, 223, 163, 2012 91, 182, 113, 226, 217, 175, 67, 134, 17, 34, 68, 136, 13, 26, 52, 2013 104, 208, 189, 103, 206, 129, 31, 62, 124, 248, 237, 199, 147, 59, 2014 118, 236, 197, 151, 51, 102, 204, 133, 23, 46, 92, 184, 109, 218, 2015 169, 79, 158, 33, 66, 132, 21, 42, 84, 168, 77, 154, 41, 82, 164, 85, 2016 170, 73, 146, 57, 114, 228, 213, 183, 115, 230, 209, 191, 99, 198, 2017 145, 63, 126, 252, 229, 215, 179, 123, 246, 241, 255, 227, 219, 171, 2018 75, 150, 49, 98, 196, 149, 55, 110, 220, 165, 87, 174, 65, 130, 25, 2019 50, 100, 200, 141, 7, 14, 28, 56, 112, 224, 221, 167, 83, 166, 81, 2020 162, 89, 178, 121, 242, 249, 239, 195, 155, 43, 86, 172, 69, 138, 9, 2021 18, 36, 72, 144, 61, 122, 244, 245, 247, 243, 251, 235, 203, 139, 11, 2022 22, 44, 88, 176, 125, 250, 233, 207, 131, 27, 54, 108, 216, 173, 71, 2023 142, 1, 2, 4, 8, 16, 32, 64, 128, 29, 58, 116, 232, 205, 135, 19, 38, 2024 76, 152, 45, 90, 180, 117, 234, 201, 143, 3, 6, 12, 24, 48, 96, 192, 2025 157, 39, 78, 156, 37, 74, 148, 53, 106, 212, 181, 119, 238, 193, 159, 2026 35, 70, 140, 5, 10, 20, 40, 80, 160, 93, 186, 105, 210, 185, 111, 2027 222, 161, 95, 190, 97, 194, 153, 47, 94, 188, 101, 202, 137, 15, 30, 2028 60, 120, 240, 253, 231, 211, 187, 107, 214, 177, 127, 254, 225, 223, 2029 163, 91, 182, 113, 226, 217, 175, 67, 134, 17, 34, 68, 136, 13, 26, 2030 52, 104, 208, 189, 103, 206, 129, 31, 62, 124, 248, 237, 199, 147, 2031 59, 118, 236, 197, 151, 51, 102, 204, 133, 23, 46, 92, 184, 109, 218, 2032 169, 79, 158, 33, 66, 132, 21, 42, 84, 168, 77, 154, 41, 82, 164, 85, 2033 170, 73, 146, 57, 114, 228, 213, 183, 115, 230, 209, 191, 99, 198, 2034 145, 63, 126, 252, 229, 215, 179, 123, 246, 241, 255, 227, 219, 171, 2035 75, 150, 49, 98, 196, 149, 55, 110, 220, 165, 87, 174, 65, 130, 25, 2036 50, 100, 200, 141, 7, 14, 28, 56, 112, 224, 221, 167, 83, 166, 81, 2037 162, 89, 178, 121, 242, 249, 239, 195, 155, 43, 86, 172, 69, 138, 9, 2038 18, 36, 72, 144, 61, 122, 244, 245, 247, 243, 251, 235, 203, 139, 11, 2039 22, 44, 88, 176, 125, 250, 233, 207, 131, 27, 54, 108, 216, 173, 71, 2040 142, 1, 2 2042 5.7.3. The table GF256_LOG 2044 255, 0, 1, 25, 2, 50, 26, 198, 3, 223, 51, 238, 27, 104, 199, 75, 4, 2045 100, 224, 14, 52, 141, 239, 129, 28, 193, 105, 248, 200, 8, 76, 113, 2046 5, 138, 101, 47, 225, 36, 15, 33, 53, 147, 142, 218, 240, 18, 130, 2047 69, 29, 181, 194, 125, 106, 39, 249, 185, 201, 154, 9, 120, 77, 228, 2048 114, 166, 6, 191, 139, 98, 102, 221, 48, 253, 226, 152, 37, 179, 16, 2049 145, 34, 136, 54, 208, 148, 206, 143, 150, 219, 189, 241, 210, 19, 2050 92, 131, 56, 70, 64, 30, 66, 182, 163, 195, 72, 126, 110, 107, 58, 2051 40, 84, 250, 133, 186, 61, 202, 94, 155, 159, 10, 21, 121, 43, 78, 2052 212, 229, 172, 115, 243, 167, 87, 7, 112, 192, 247, 140, 128, 99, 13, 2053 103, 74, 222, 237, 49, 197, 254, 24, 227, 165, 153, 119, 38, 184, 2054 180, 124, 17, 68, 146, 217, 35, 32, 137, 46, 55, 63, 209, 91, 149, 2055 188, 207, 205, 144, 135, 151, 178, 220, 252, 190, 97, 242, 86, 211, 2056 171, 20, 42, 93, 158, 132, 60, 57, 83, 71, 109, 65, 162, 31, 45, 67, 2057 216, 183, 123, 164, 118, 196, 23, 73, 236, 127, 12, 111, 246, 108, 2058 161, 59, 82, 41, 157, 85, 170, 251, 96, 134, 177, 187, 204, 62, 90, 2059 203, 89, 95, 176, 156, 169, 160, 81, 11, 245, 22, 235, 122, 117, 44, 2060 215, 79, 174, 213, 233, 230, 231, 173, 232, 116, 214, 244, 234, 168, 2061 80, 88, 175 2063 6. Security Considerations 2065 Data delivery can be subject to denial-of-service attacks by 2066 attackers which send corrupted packets that are accepted as 2067 legitimate by receivers. This is particularly a concern for 2068 multicast delivery because a corrupted packet may be injected into 2069 the session close to the root of the multicast tree, in which case 2070 the corrupted packet will arrive at many receivers. This is 2071 particularly a concern when the code described in this document is 2072 used because the use of even one corrupted packet containing encoding 2073 data may result in the decoding of an object that is completely 2074 corrupted and unusable. It is thus RECOMMENDED that source 2075 authentication and integrity checking are applied to decoded objects 2076 before delivering objects to an application. For example, a SHA-1 2077 hash [SHA1] of an object may be appended before transmission, and the 2078 SHA-1 hash is computed and checked after the object is decoded but 2079 before it is delivered to an application. Source authentication 2080 SHOULD be provided, for example by including a digital signature 2081 verifiable by the receiver computed on top of the hash value. It is 2082 also RECOMMENDED that a packet authentication protocol such as TESLA 2083 [RFC4082] be used to detect and discard corrupted packets upon 2084 arrival. This method may also be used to provide source 2085 authentication. Furthermore, it is RECOMMENDED that Reverse Path 2086 Forwarding checks be enabled in all network routers and switches 2087 along the path from the sender to receivers to limit the possibility 2088 of a bad agent successfully injecting a corrupted packet into the 2089 multicast tree data path. 2091 Another security concern is that some FEC information may be obtained 2092 by receivers out-of-band in a session description, and if the session 2093 description is forged or corrupted then the receivers will not use 2094 the correct protocol for decoding content from received packets. To 2095 avoid these problems, it is RECOMMENDED that measures be taken to 2096 prevent receivers from accepting incorrect session descriptions, 2097 e.g., by using source authentication to ensure that receivers only 2098 accept legitimate session descriptions from authorized senders. 2100 7. IANA Considerations 2102 Values of FEC Encoding IDs and FEC Instance IDs are subject to IANA 2103 registration. For general guidelines on IANA considerations as they 2104 apply to this document, see [RFC5052]. This document assigns the 2105 Fully-Specified FEC Encoding ID XXX under the ietf:rmt:fec:encoding 2106 name-space to "RaptorG Code". 2108 8. Acknowledgements 2110 Thanks are due to Lorenz Minder and Ranganathan (Ranga) Krishnan. 2111 Lorenz Minder did the original implementation of RaptorG, supervised 2112 by Amin Shokrollahi. Ranga Krishnan has been very supportive in 2113 finding and resolving implementation details and in finding the 2114 systematic indices. 2116 9. References 2118 9.1. Normative references 2120 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 2121 Requirement Levels", BCP 14, RFC 2119, March 1997. 2123 [RFC4082] Perrig, A., Song, D., Canetti, R., Tygar, J., and B. 2124 Briscoe, "Timed Efficient Stream Loss-Tolerant 2125 Authentication (TESLA): Multicast Source Authentication 2126 Transform Introduction", RFC 4082, June 2005. 2128 [SHA1] "Secure Hash Standard", Federal Information Processing 2129 Standards Publication (FIPS PUB) 180-1, 2130 April 2005. 2132 [RFC5052] Watson, M., Luby, M., and L. Vicisano, "Forward Error 2133 Correction (FEC) Building Block", RFC 5052, August 2007. 2135 [RFC5053] Luby, M., Shokrollahi, A., Watson, M., and T. Stockhammer, 2136 "Raptor Forward Error Correction Scheme for Object 2137 Delivery", RFC 5053, October 2007. 2139 9.2. Informative references 2141 [RFC3453] Luby, M., Vicisano, L., Gemmell, J., Rizzo, L., Handley, 2142 M., and J. Crowcroft, "The Use of Forward Error Correction 2143 (FEC) in Reliable Multicast", RFC 3453, December 2002. 2145 Authors' Addresses 2147 Michael Luby 2148 Qualcomm, Inc. 2149 3165 Kifer Road 2150 Santa Clara, 95051 94538 2151 U.S.A. 2153 Email: luby@qualcomm.com 2155 Amin Shokrollahi 2156 EPFL 2157 Laboratoire d'algorithmique 2158 EPFL 2159 Station 14 2160 Batiment BC 2161 Lausanne 1015 2162 Switzerland 2164 Email: amin.shokrollahi@epfl.ch 2166 Mark Watson 2167 Qualcomm, Inc. 2168 3165 Kifer Road 2169 Santa Clara, CA 95051 2170 U.S.A. 2172 Email: watson@qualcomm.com 2174 Thomas Stockhammer 2175 Nomor Research 2176 Brecherspitzstrasse 8 2177 Munich 81541 2178 Germany 2180 Email: stockhammer@nomor.de