idnits 2.17.1 draft-ietf-rmt-bb-fec-raptorq-06.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. 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 694 has weird spacing: '... K'_max denot...' -- The document date (May 5, 2011) is 4734 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 424, but not defined == Missing Reference: 'J' is mentioned on line 424, but not defined == Missing Reference: 'Kt' is mentioned on line 435, but not defined == Missing Reference: 'Z' is mentioned on line 435, but not defined -- Looks like a reference, but probably isn't: '2' on line 2839 -- Looks like a reference, but probably isn't: '256' on line 552 == Missing Reference: 'A' is mentioned on line 679, but not defined -- Looks like a reference, but probably isn't: '0' on line 2966 -- Looks like a reference, but probably isn't: '1' on line 2839 == Missing Reference: 'L-1' is mentioned on line 1431, but not defined -- Looks like a reference, but probably isn't: '255' on line 733 == Missing Reference: 'X' is mentioned on line 1369, but not defined == Missing Reference: 'K' is mentioned on line 963, but not defined == Missing Reference: 'B-1' is mentioned on line 1048, but not defined == Missing Reference: 'B' is mentioned on line 1049, but not defined == Missing Reference: 'W' is mentioned on line 1049, but not defined == Missing Reference: 'L-H' is mentioned on line 1008, but not defined == Missing Reference: 'S-1' is mentioned on line 1015, but not defined -- Looks like a reference, but probably isn't: '3' on line 2839 -- Looks like a reference, but probably isn't: '4' on line 2839 == Missing Reference: 'P1-1' is mentioned on line 1367, but not defined -- Looks like a reference, but probably isn't: '5' on line 2839 == Missing Reference: 'P1' is mentioned on line 1369, but not defined == Missing Reference: 'M-1' is mentioned on line 1432, but not defined -- Looks like a reference, but probably isn't: '7' on line 2839 -- Looks like a reference, but probably isn't: '6' on line 2839 == Missing Reference: 'T-1' is mentioned on line 2966, but not defined ** Downref: Normative reference to an Informational RFC: RFC 4082 Summary: 1 error (**), 0 flaws (~~), 19 warnings (==), 11 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 Incorporated 4 Intended status: Standards Track A. Shokrollahi 5 Expires: November 6, 2011 EPFL 6 M. Watson 7 Netflix Inc. 8 T. Stockhammer 9 Nomor Research 10 L. Minder 11 Qualcomm Incorporated 12 May 5, 2011 14 RaptorQ Forward Error Correction Scheme for Object Delivery 15 draft-ietf-rmt-bb-fec-raptorq-06 17 Abstract 19 This document describes a Fully-Specified FEC scheme, corresponding 20 to FEC Encoding ID 6 (to be confirmed (tbc)), for the RaptorQ forward 21 error correction code and its application to reliable delivery of 22 data objects. 24 RaptorQ codes are a new family of codes that provide superior 25 flexibility, support for larger source block sizes and better coding 26 efficiency than Raptor codes in RFC5053. RaptorQ is also a fountain 27 code, i.e., as many encoding symbols as needed can be generated by 28 the encoder on-the-fly from the source symbols of a source block of 29 data. The decoder is able to recover the source block from any set 30 of encoding symbols for most cases equal to the number of source 31 symbols and in rare cases with slightly more than the number of 32 source symbols. 34 The RaptorQ code described here is a systematic code, meaning that 35 all the source symbols are among the encoding symbols that can be 36 generated. 38 Status of this Memo 40 This Internet-Draft is submitted in full conformance with the 41 provisions of BCP 78 and BCP 79. 43 Internet-Drafts are working documents of the Internet Engineering 44 Task Force (IETF). Note that other groups may also distribute 45 working documents as Internet-Drafts. The list of current Internet- 46 Drafts is at http://datatracker.ietf.org/drafts/current/. 48 Internet-Drafts are draft documents valid for a maximum of six months 49 and may be updated, replaced, or obsoleted by other documents at any 50 time. It is inappropriate to use Internet-Drafts as reference 51 material or to cite them other than as "work in progress." 53 This Internet-Draft will expire on November 6, 2011. 55 Copyright Notice 57 Copyright (c) 2011 IETF Trust and the persons identified as the 58 document authors. All rights reserved. 60 This document is subject to BCP 78 and the IETF Trust's Legal 61 Provisions Relating to IETF Documents 62 (http://trustee.ietf.org/license-info) in effect on the date of 63 publication of this document. Please review these documents 64 carefully, as they describe your rights and restrictions with respect 65 to this document. Code Components extracted from this document must 66 include Simplified BSD License text as described in Section 4.e of 67 the Trust Legal Provisions and are provided without warranty as 68 described in the Simplified BSD License. 70 Table of Contents 72 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 5 73 2. Requirements notation . . . . . . . . . . . . . . . . . . . . 5 74 3. Formats and Codes . . . . . . . . . . . . . . . . . . . . . . 5 75 3.1. Introduction . . . . . . . . . . . . . . . . . . . . . . . 5 76 3.2. FEC Payload IDs . . . . . . . . . . . . . . . . . . . . . 6 77 3.3. FEC Object Transmission Information . . . . . . . . . . . 6 78 3.3.1. Mandatory . . . . . . . . . . . . . . . . . . . . . . 6 79 3.3.2. Common . . . . . . . . . . . . . . . . . . . . . . . . 6 80 3.3.3. Scheme-Specific . . . . . . . . . . . . . . . . . . . 7 81 4. Procedures . . . . . . . . . . . . . . . . . . . . . . . . . . 8 82 4.1. Introduction . . . . . . . . . . . . . . . . . . . . . . . 8 83 4.2. Content Delivery Protocol Requirements . . . . . . . . . . 8 84 4.3. Example Parameter Derivation Algorithm . . . . . . . . . . 8 85 4.4. Object Delivery . . . . . . . . . . . . . . . . . . . . . 10 86 4.4.1. Source block construction . . . . . . . . . . . . . . 10 87 4.4.2. Encoding packet construction . . . . . . . . . . . . . 12 88 4.4.3. Example receiver recovery strategies . . . . . . . . . 13 89 5. RaptorQ FEC Code Specification . . . . . . . . . . . . . . . . 13 90 5.1. Background . . . . . . . . . . . . . . . . . . . . . . . . 13 91 5.1.1. Definitions . . . . . . . . . . . . . . . . . . . . . 14 92 5.1.2. Symbols . . . . . . . . . . . . . . . . . . . . . . . 15 93 5.2. Overview . . . . . . . . . . . . . . . . . . . . . . . . . 18 94 5.3. Systematic RaptorQ encoder . . . . . . . . . . . . . . . . 19 95 5.3.1. Introduction . . . . . . . . . . . . . . . . . . . . . 19 96 5.3.2. Encoding overview . . . . . . . . . . . . . . . . . . 20 97 5.3.3. First encoding step: Intermediate Symbol Generation . 22 98 5.3.4. Second encoding step: Encoding . . . . . . . . . . . . 28 99 5.3.5. Generators . . . . . . . . . . . . . . . . . . . . . . 28 100 5.4. Example FEC decoder . . . . . . . . . . . . . . . . . . . 31 101 5.4.1. General . . . . . . . . . . . . . . . . . . . . . . . 31 102 5.4.2. Decoding an extended source block . . . . . . . . . . 32 103 5.5. Random Numbers . . . . . . . . . . . . . . . . . . . . . . 37 104 5.5.1. The table V0 . . . . . . . . . . . . . . . . . . . . . 37 105 5.5.2. The table V1 . . . . . . . . . . . . . . . . . . . . . 38 106 5.5.3. The table V2 . . . . . . . . . . . . . . . . . . . . . 39 107 5.5.4. The table V3 . . . . . . . . . . . . . . . . . . . . . 40 108 5.6. Systematic indices and other parameters . . . . . . . . . 41 109 5.7. Operating with Octets, Symbols and Matrices . . . . . . . 62 110 5.7.1. General . . . . . . . . . . . . . . . . . . . . . . . 62 111 5.7.2. Arithmetic Operations on Octets . . . . . . . . . . . 62 112 5.7.3. The table OCT_EXP . . . . . . . . . . . . . . . . . . 63 113 5.7.4. The table OCT_LOG . . . . . . . . . . . . . . . . . . 64 114 5.7.5. Operations on Symbols . . . . . . . . . . . . . . . . 65 115 5.7.6. Operations on Matrices . . . . . . . . . . . . . . . . 65 116 5.8. Requirements for a Compliant Decoder . . . . . . . . . . . 65 117 6. Security Considerations . . . . . . . . . . . . . . . . . . . 66 118 7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 67 119 8. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 67 120 9. References . . . . . . . . . . . . . . . . . . . . . . . . . . 67 121 9.1. Normative references . . . . . . . . . . . . . . . . . . . 67 122 9.2. Informative references . . . . . . . . . . . . . . . . . . 67 123 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 68 125 1. Introduction 127 This document specifies an FEC Scheme for the RaptorQ forward error 128 correction code for object delivery applications. The concept of an 129 FEC Scheme is defined in RFC5052 [RFC5052] and this document follows 130 the format prescribed there and uses the terminology of that 131 document. The RaptorQ code described herein is a next generation of 132 the Raptor code described in RFC5053 [RFC5053]. The RaptorQ code 133 provides superior reliability, better coding efficiency, and support 134 for larger source block sizes than the Raptor code of RFC5053 135 [RFC5053]. These improvements simplify the usage of the RaptorQ code 136 in an object delivery Content Delivery Protocol compared to RFC5053 137 [RFC5053]. 139 The RaptorQ FEC Scheme is a Fully-Specified FEC Scheme corresponding 140 to FEC Encoding ID 6 (tbc). 142 Editor's Note: The finalized FEC encoding ID is still to be 143 defined, but '6 (tbc)' is used as temporary value in this Internet 144 Draft expecting sequential use of FEC encoding IDs in the IANA 145 registration process. 147 RaptorQ is a fountain code, i.e., as many encoding symbols as needed 148 can be generated by the encoder on-the-fly from the source symbols of 149 a block. The decoder is able to recover the source block from any 150 set of encoding symbols only slightly more in number than the number 151 of source symbols. 153 The code described in this document is a systematic code, that is, 154 the original source symbols can be sent unmodified from sender to 155 receiver, as well as a number of repair symbols. For more backgound 156 on the use of Forward Error Correction codes in reliable multicast, 157 see [RFC3453]. 159 2. Requirements notation 161 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 162 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 163 document are to be interpreted as described in [RFC2119]. 165 3. Formats and Codes 167 3.1. Introduction 169 The octet order of all fields is network byte order, i.e., big- 170 endian. 172 3.2. FEC Payload IDs 174 The FEC Payload ID MUST be a 4-octet field defined as follows: 176 0 1 2 3 177 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 178 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 179 | SBN | Encoding Symbol ID | 180 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 182 Figure 1: FEC Payload ID format 184 o Source Block Number (SBN), (8 bits, unsigned integer): A non- 185 negative integer identifier for the source block that the encoding 186 symbols within the packet relate to. 188 o Encoding Symbol ID (ESI), (24 bits, unsigned integer): A non- 189 negative integer identifier for the encoding symbols within the 190 packet. 192 The interpretation of the Source Block Number and Encoding Symbol 193 Identifier is defined in Section 4. 195 3.3. FEC Object Transmission Information 197 3.3.1. Mandatory 199 The value of the FEC Encoding ID MUST be 6, as assigned by IANA (see 200 Section 7). 202 3.3.2. Common 204 The Common FEC Object Transmission Information elements used by this 205 FEC Scheme are: 207 o Transfer Length (F), (40 bits, unsigned integer): A non-negative 208 integer that is at most 946270874880. This is the transfer length 209 of the object in units of octets. 211 o Symbol Size (T), (16 bits, unsigned integer): A positive integer 212 that is less than 2^^16. This is the size of a symbol in units of 213 octets. 215 The encoded Common FEC Object Transmission Information format is 216 shown in Figure 2. 218 0 1 2 3 219 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 220 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 221 | Transfer Length (F) | 222 + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 223 | | Reserved | Symbol Size (T) | 224 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 226 Figure 2: Encoded Common FEC OTI for RaptorQ FEC Scheme 228 NOTE 1: The limit of 946270874880 on the transfer length is a 229 consequence of the limitation on the symbol size to 2^^16-1, the 230 limitation on the number of symbols in a source block to 56403 and 231 the limitation on the number of source blocks to 2^^8. 233 3.3.3. Scheme-Specific 235 The following parameters are carried in the Scheme-Specific FEC 236 Object Transmission Information element for this FEC Scheme: 238 o The number of source blocks (Z) (8 bits, unsigned integer) 240 o The number of sub-blocks (N) (16 bits, unsigned integer) 242 o A symbol alignment parameter (Al) (8 bits, unsigned integer) 244 These parameters are all positive integers. The encoded Scheme- 245 specific Object Transmission Information is a 4-octet field 246 consisting of the parameters Z, N and Al as shown in Figure 3. 248 0 1 2 3 249 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 250 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 251 | Z | N | Al | 252 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 254 Figure 3: Encoded Scheme-specific FEC Object Transmission Information 256 The encoded FEC Object Transmission Information is a 12-octet field 257 consisting of the concatenation of the encoded Common FEC Object 258 Transmission Information and the encoded Scheme-specific FEC Object 259 Transmission Information. 261 These three parameters define the source block partitioning as 262 described in Section 4.4.1.2 264 4. Procedures 266 4.1. Introduction 268 For any undefined symbols or functions used in this section, in 269 particular the functions "ceil" and "floor", refer to Section 5.1. 271 4.2. Content Delivery Protocol Requirements 273 This section describes the information exchange between the RaptorQ 274 FEC Scheme and any Content Delivery Protocol (CDP) that makes use of 275 the RaptorQ FEC Scheme for object delivery. 277 The RaptorQ encoder scheme and RaptorQ decoder scheme for object 278 delivery require the following information from the CDP: 280 o The transfer length of the object, F, in octets 282 o A symbol alignment parameter, Al 284 o The symbol size, T, in octets, which MUST be a multiple of Al 286 o The number of source blocks, Z 288 o The number of sub-blocks in each source block, N 290 The RaptorQ encoder scheme for object delivery additionally requires: 292 - the object to be encoded, F octets 294 The RaptorQ encoder scheme supplies the CDP with the following 295 information for each packet to be sent: 297 o Source Block Number (SBN) 299 o Encoding Symbol ID (ESI) 301 o Encoding symbol(s) 303 The CDP MUST communicate this information to the receiver. 305 4.3. Example Parameter Derivation Algorithm 307 This section provides recommendations for the derivation of the three 308 transport parameters, T, Z and N. This recommendation is based on the 309 following input parameters: 311 o F the transfer length of the object, in octets 313 o WS the maximum size block that is decodable in working memory, in 314 octets 316 o P' the maximum payload size in octets, which is assumed to be a 317 multiple of Al 319 o Al the symbol alignment parameter, in octets 321 o SS a parameter where the desired lower bound on the sub-symbol 322 size is SS*Al 324 o K'_max the maximum number of source symbols per source block. 326 Note: Section 5.1.2 defines K'_max to be 56403. 328 Based on the above inputs, the transport parameters T, Z and N are 329 calculated as follows: 331 Let, 333 o T = P' 335 o Kt = ceil(F/T) 337 o N_max = floor(T/(SS*Al)) 339 o for all n=1, ..., N_max 341 * KL(n) is the maximum K' value in Table 2 in Section 5.6 such 342 that 344 K' <= WS/(Al*(ceil(T/(Al*n)))) 346 o Z = ceil(Kt/KL(N_max)) 348 o N is the minimum n=1, ..., N_max such that ceil(Kt/Z) <= KL(n) 350 It is RECOMMENDED that each packet contains exactly one symbol. 351 However, receivers SHALL support the reception of packets that 352 contain multiple symbols. 354 The value Kt is the total number of symbols required to represent the 355 source data of the object. 357 The algorithm above and that defined in Section 4.4.1.2 ensure that 358 the sub-symbol sizes are a multiple of the symbol alignment 359 parameter, Al. This is useful because the sum operations used for 360 encoding and decoding are generally performed several octets at a 361 time, for example at least 4 octets at a time on a 32 bit processor. 362 Thus the encoding and decoding can be performed faster if the sub- 363 symbol sizes are a multiple of this number of octets. 365 The recommended setting for the input parameter Al is 4. 367 The parameter WS can be used to generate encoded data which can be 368 decoded efficiently with limited working memory at the decoder. Note 369 that the actual maximum decoder memory requirement for a given value 370 of WS depends on the implementation, but it is possible to implement 371 decoding using working memory only slightly larger than WS. 373 4.4. Object Delivery 375 4.4.1. Source block construction 377 4.4.1.1. General 379 In order to apply the RaptorQ encoder to a source object, the object 380 may be broken into Z >= 1 blocks, known as source blocks. The 381 RaptorQ encoder is applied independently to each source block. Each 382 source block is identified by a unique Source Block Number (SBN), 383 where the first source block has SBN zero, the second has SBN one, 384 etc. Each source block is divided into a number, K, of source 385 symbols of size T octets each. Each source symbol is identified by a 386 unique Encoding Symbol Identifier (ESI), where the first source 387 symbol of a source block has ESI zero, the second has ESI one, etc. 389 Each source block with K source symbols is divided into N >= 1 sub- 390 blocks, which are small enough to be decoded in the working memory. 391 Each sub-block is divided into K sub-symbols of size T'. 393 Note that the value of K is not necessarily the same for each source 394 block of an object and the value of T' may not necessarily be the 395 same for each sub-block of a source block. However, the symbol size 396 T is the same for all source blocks of an object and the number of 397 symbols, K is the same for every sub-block of a source block. Exact 398 partitioning of the object into source blocks and sub-blocks is 399 described in Section 4.4.1.2 below. 401 4.4.1.2. Source block and sub-block partitioning 403 The construction of source blocks and sub-blocks is determined based 404 on five input parameters, F, Al, T, Z and N and a function 405 Partition[]. The five input parameters are defined as follows: 407 o F the transfer length of the object, in octets 409 o Al a symbol alignment parameter, in octets 411 o T the symbol size, in octets, which MUST be a multiple of Al 413 o Z the number of source blocks 415 o N the number of sub-blocks in each source block 417 These parameters MUST be set so that ceil(ceil(F/T)/Z) <= K'_max. 418 Recommendations for derivation of these parameters are provided in 419 Section 4.3. 421 The function Partition[I,J] derives parameters for partitioning a 422 block of size I into J approximately equal sized blocks, and more 423 specifically partitions I into JL blocks of length IL and JS blocks 424 of length IS. Specifically, the output of Partition[I, J] is the 425 sequence (IL, IS, JL, JS), where IL = ceil(I/J), IS = floor(I/J), JL 426 = I - IS * J and JS = J - JL. 428 The source object MUST be partitioned into source blocks and sub- 429 blocks as follows: 431 Let 433 o Kt = ceil(F/T), 435 o (KL, KS, ZL, ZS) = Partition[Kt, Z], 437 o (TL, TS, NL, NS) = Partition[T/Al, N]. 439 Then, the object MUST be partitioned into Z = ZL + ZS contiguous 440 source blocks, the first ZL source blocks each having KL*T octets, 441 i.e. KL source symbols of T octets each, and the remaining ZS source 442 blocks each having KS*T octets, i.e. KS source symbols of T octets 443 each. 445 If Kt*T > F then for encoding purposes, the last symbol of the last 446 source block MUST be padded at the end with Kt*T-F zero octets. 448 Next, each source block with K source symbols MUST be divided into N 449 = NL + NS contiguous sub-blocks, the first NL sub-blocks each 450 consisting of K contiguous sub-symbols of size of TL*Al octets and 451 the remaining NS sub-blocks each consisting of K contiguous sub- 452 symbols of size of TS*Al octets. The symbol alignment parameter Al 453 ensures that sub-symbols are always a multiple of Al octets. 455 Finally, the m-th symbol of a source block consists of the 456 concatenation of the m-th sub-symbol from each of the N sub-blocks. 457 Note that this implies that when N > 1 then a symbol is NOT a 458 contiguous portion of the object. 460 4.4.2. Encoding packet construction 462 Each encoding packet contains the following information: 464 o Source Block Number (SBN) 466 o Encoding Symbol ID (ESI) 468 o encoding symbol(s) 470 Each source block is encoded independently of the others. Each 471 encoding packet contains encoding symbols generated from the one 472 source block identified by the SBN carried in the encoding packet. 473 Source blocks are numbered consecutively from zero. 475 Encoding Symbol ID values from 0 to K-1 identify the source symbols 476 of a source block in sequential order, where K is the number of 477 source symbols in the source block. Encoding Symbol IDs K onwards 478 identify repair symbols generated from the source symbols using the 479 RaptorQ encoder. 481 Each encoding packet either contains only source symbols (source 482 packet) or contains only repair symbols (repair packet). A packet 483 may contain any number of symbols from the same source block. In the 484 case that the last source symbol in a source packet includes padding 485 octets added for FEC encoding purposes then these octet need not be 486 included in the packet. Otherwise, each packet MUST contain only 487 whole symbols. 489 The Encoding Symbol ID, X, carried in each source packet is the 490 Encoding Symbol ID of the first source symbol carried in that packet. 491 The subsequent source symbols in the packet have Encoding Symbol IDs, 492 X+1 to X+G-1, in sequential order, where G is the number of symbols 493 in the packet. 495 Similarly, the Encoding Symbol ID, X, placed into a repair packet is 496 the Encoding Symbol ID of the first repair symbol in the repair 497 packet and the subsequent repair symbols in the packet have Encoding 498 Symbol IDs X+1 to X+G-1 in sequential order, where G is the number of 499 symbols in the packet. 501 Note that it is not necessary for the receiver to know the total 502 number of repair packets. 504 4.4.3. Example receiver recovery strategies 506 A receiver can use the received encoding symbols for each source 507 block of an object to recover the source symbols for that source 508 block independently of all other source blocks. 510 If there is one sub-block per source block, i.e., N = 1, then the 511 portion of the data in the original object in its original order 512 associated with a source block consists of the concatenation of the 513 source symbols of a source block in consecutive ESI order. 515 If there are multiple sub-blocks per source block, i.e., if N > 1, 516 then the portion of the data in the original object in its original 517 order associated with a source block consists of the concatenation of 518 the sub-blocks associated with the source block, where sub-symbols 519 within each sub-block are in consecutive ESI order. In this case, 520 there are different receiver source block recovery strategies worth 521 considering depending on the available amount of Random Access Memory 522 (RAM) at the receiver, as outlined below. 524 One strategy is to recover the source symbols of a source block using 525 the decoding procedures applied to the received symbols for the 526 source block to recover the source symbols as described in Section 5, 527 and then to reorder the sub-symbols of the source symbols so that all 528 consecutive sub-symbols of the first sub-block are first, followed by 529 all consecutive sub-symbols of the second sub-block, etc., followed 530 by all consecutive sub-symbols of the Nth sub-block. This strategy 531 is especially applicable if the receiver has enough RAM to decode an 532 entire source block. 534 Another strategy is to separately recover the sub-blocks of a source 535 block. For example, a receiver may de-multiplex and store sub- 536 symbols associated with each sub-block separately as packets 537 containing encoding symbols arrive, and then use the stored sub- 538 symbols received for a sub-block to recover that sub-block using the 539 decoding procedures described in Section 5. This strategy is 540 especially applicable if the receiver has enough RAM to decode only 541 one subblock at a time. 543 5. RaptorQ FEC Code Specification 545 5.1. Background 547 For the purpose of the RaptorQ FEC code specification in this 548 section, the following definitions, symbols and abbreviations apply. 549 A basic understanding of linear algebra, matrix operations, and 550 finite fields is assumed in this section. In particular, matrix 551 multiplication and matrix inversion operations over a mixture of the 552 finite fields GF[2] and GF[256] are used. A basic familiarity with 553 sparse linear equations, and efficient implementations of algorithms 554 that take advantage of sparse linear equations, is also quite 555 beneficial to an implementer of this specification. 557 5.1.1. Definitions 559 o Source block: a block of K source symbols which are considered 560 together for RaptorQ encoding and decoding purposes. 562 o Extended Source Block: a block of K' source symbols, where K' >= K 563 constructed from a source block and zero or more padding symbols. 565 o Symbol: a unit of data. The size, in octets, of a symbol is known 566 as the symbol size. The symbol size is always a positive integer. 568 o Source symbol: the smallest unit of data used during the encoding 569 process. All source symbols within a source block have the same 570 size. 572 o Padding symbol: a symbol with all zero bits that is added to the 573 source block to form the extended source block. 575 o Encoding symbol: a symbol that can be sent as part of the encoding 576 of a source block. The encoding symbols of a source block consist 577 of the source symbols of the source block and the repair symbols 578 generated from the source block. Repair symbols generated from a 579 source block have the same size as the source symbols of that 580 source block. 582 o Repair symbol: the encoding symbols of a source block that are not 583 source symbols. The repair symbols are generated based on the 584 source symbols of a source block. 586 o Intermediate symbols: symbols generated from the source symbols 587 using an inverse encoding process based on pre-coding 588 relationships. The repair symbols are then generated directly 589 from the intermediate symbols. The encoding symbols do not 590 include the intermediate symbols, i.e., intermediate symbols are 591 not sent as part of the encoding of a source block. The 592 intermediate symbols are partitioned into LT symbols and PI 593 symbols for the purposes of the encoding process. 595 o LT symbols: A process similar to that described in [LTCodes] is 596 used to generate part of the contribution to each generated 597 encoding symbol from the portion of the intermediate symbols 598 designated as LT symbols. 600 o PI symbols: A process even simpler than that described in 601 [LTCodes] is used to generate the other part of the contribution 602 to each generated encoding symbol from the portion of the 603 intermediate symbols designated as PI symbols. In the decoding 604 algorithm suggested in Section 5.4, the PI symbols are inactivated 605 at the start, i.e., are placed into the matrix U at the beginning 606 of the first phase of the decoding algorithm. Because the symbols 607 corresponding to the columns of U are sometimes called the 608 "inactivated" symbols, and since the PI symbols are inactivated at 609 the beginning, they are considered "permanently inactivated". 611 o HDPC symbols: There is a small subset of the intermediate symbols 612 that are HDPC symbols. Each HDPC symbol has a pre-coding 613 relationship with a large fraction of the other intermediate 614 symbols. HDPC means "High Density Parity Check". 616 o LDPC symbols: There is a moderate-sized subset of the intermediate 617 symbols that are LDPC symbols. Each LDPC symbol has a pre-coding 618 relationship with a small fraction of the other intermediate 619 symbols. LDPC means "Low Density Parity Check". 621 o Systematic code: a code in which all source symbols are included 622 as part of the encoding symbols of a source block. The RaptorQ 623 code as described herein is a systematic code. 625 o Encoding Symbol ID (ESI): information that uniquely identifies 626 each encoding symbol associated with a source block for sending 627 and receiving purposes. 629 o Internal Symbol ID (ISI): information that uniquely identifies 630 each symbol associated with an extended source block for encoding 631 and decoding purposes. 633 o Arithmetic operations on octets and symbols and matrices: The 634 operations that are used to produce encoding symbols from source 635 symbols and vice-versa. See Section 5.7. 637 5.1.2. Symbols 639 i, j, u, v, h, d, a, b, d1, a1, b1, v, m, x, y represent values or 640 variables of one type or another, depending on the context. 642 X denotes a non-negative integer value that is either an ISI value 643 or an ESI value, depending on the context. 645 ceil(x) denotes the smallest integer which is greater than or equal 646 to x, where x is a real value. 648 floor(x) denotes the largest integer which is less than or equal to 649 x, where x is a real value. 651 min(x,y) denotes the minimum value of the values x and y, and in 652 general the minimum value of all the argument values. 654 max(x,y) denotes the maximum value of the values x and y, and in 655 general the maximum value of all the argument values. 657 i % j denotes i modulo j. 659 i + j denotes the sum of i and j. If i and j are octets, 660 respectively symbols, this designates the arithmetic on octets, 661 respectively symbols, as defined in Section 5.7. If i and j are 662 integers, then it denotes the usual integer addition. 664 i * j denotes the product of i and j. If i and j are octets, this 665 designates the arithmetic on octets, as defined in Section 5.7. 666 If i is an octet and j is a symbol, this denotes the 667 multiplication of a symbol by an octet, as also defined in 668 Section 5.7. Finally, if i and j are integers, i * j denotes 669 the usual product of integers. 671 a ^^ b denotes the operation a raised to the power b. If a is an 672 octet and b is a non-negative integer, this is understood to 673 mean a*a*...*a (b terms), with '*' being the octet product as 674 defined in Section 5.7. 676 u ^ v denotes, for equal-length bit strings u and v, the bitwise 677 exclusive-or of u and v. 679 Transpose[A] denotes the transposed matrix of matrix A. In this 680 specification, all matrices have entries that are octets. 682 A^^-1 denotes the inverse matrix of matrix A. In this specification, 683 all the matrices have octets as entries, so it is understood 684 that the operations of the matrix entries are to be done as 685 stated in Section 5.7 and A^^-1 is the matrix inverse of A with 686 respect to octet arithmetic. 688 K denotes the number of symbols in a single source block. 690 K' denotes the number of source plus padding symbols in an extended 691 source block. For the majority of this specification, the 692 padding symbols are considered to be additional source symbols. 694 K'_max denotes the maximum number of source symbols that can be in a 695 single source block. Set to 56403. 697 L denotes the number of intermediate symbols for a single extended 698 source block. 700 S denotes the number of LDPC symbols for a single extended source 701 block. These are LT symbols. For each value of K' shown in 702 Table 2 in Section 5.6, the corresponding value of S is a prime 703 number. 705 H denotes the number of HDPC symbols for a single extended source 706 block. These are PI symbols. 708 B denotes the number of intermediate symbols that are LT symbols 709 excluding the LDPC symbols. 711 W denotes the number of intermediate symbols that are LT symbols. 712 For each value of K' in Table 2 shown in Section 5.6, the 713 corresponding value of W is a prime number. 715 P denotes the number of intermediate symbols that are PI symbols. 716 These contain all HDPC symbols. 718 P1 denotes the smallest prime number greater than or equal to P. 720 U denotes the number of non-HDPC intermediate symbols that are PI 721 symbols. 723 C denotes an array of intermediate symbols, C[0], C[1], C[2],..., 724 C[L-1]. 726 C' denotes an array of the symbols of the extended source block, 727 where C'[0], C'[1], C'[2],..., C'[K-1] are the source symbols of 728 the source block and C'[K], C'[K+1],..., C'[K'-1] are padding 729 symbols. 731 V0, V1, V2, V3 denote four arrays of 32-bit unsigned integers, 732 V0[0], V0[1],..., V0[255] ; V1[0], V1[1],..., V1[255]; V2[0], 733 V2[1],..., V2[255]; and V3[0], V3[1],..., V3[255] as shown in 734 Section 5.5. 736 Rand[y, i, m] denotes a pseudo-random number generator 738 Deg[v] denotes a degree generator 740 Enc[K', C ,(d, a, b, d1, a1, b1)] denotes an encoding symbol 741 generator 743 Tuple[K', X] denotes a tuple generator function 745 T denotes the symbol size in octets. 747 J(K') denotes the systematic index associated with K'. 749 G denotes any generator matrix. 751 I_S denotes the SxS identity matrix. 753 5.2. Overview 755 This section defines the systematic RaptorQ FEC code. 757 Symbols are the fundamental data units of the encoding and decoding 758 process. For each source block all symbols are the same size, 759 referred to as the symbol size T. The atomic operations performed on 760 symbols for both encoding and decoding are the arithmetic operations 761 defined in Section 5.7. 763 The basic encoder is described in Section 5.3. The encoder first 764 derives a block of intermediate symbols from the source symbols of a 765 source block. This intermediate block has the property that both 766 source and repair symbols can be generated from it using the same 767 process. The encoder produces repair symbols from the intermediate 768 block using an efficient process, where each such repair symbol is 769 the exclusive OR of a small number of intermediate symbols from the 770 block. Source symbols can also be reproduced from the intermediate 771 block using the same process. The encoding symbols are the 772 combination of the source and repair symbols. 774 An example of a decoder is described in Section 5.4. The process for 775 producing source and repair symbols from the intermediate block is 776 designed so that the intermediate block can be recovered from any 777 sufficiently large set of encoding symbols, independent of the mix of 778 source and repair symbols in the set. Once the intermediate block is 779 recovered, missing source symbols of the source block can be 780 recovered using the encoding process. 782 Requirements for a RaptorQ compliant decoder are provided in 783 Section 5.8. A number of decoding algorithms are possible to achieve 784 these requirements. An efficient decoding algorithm to achieve these 785 requirements is provided in Section 5.4. 787 The construction of the intermediate and repair symbols is based in 788 part on a pseudo-random number generator described in Section 5.3. 789 This generator is based on a fixed set of 1024 random numbers which 790 must be available to both sender and receiver. These numbers are 791 provided in Section 5.5. Encoding and decoding operations for 792 RaptorQ use operations on octets. Section 5.7 describes how to 793 perform these operations. 795 Finally, the construction of the intermediate symbols from the source 796 symbols is governed by "systematic indices", values of which are 797 provided in Section 5.6 for specific extended source block sizes 798 between 6 and K'_max = 56403 source symbols. Thus, the RaptorQ code 799 supports source blocks with between 1 and 56403 source symbols. 801 5.3. Systematic RaptorQ encoder 803 5.3.1. Introduction 805 For a given source block of K source symbols, for encoding and 806 decoding purposes the source block is augmented with K'-K additional 807 padding symbols, where K' is the smallest value that is at least K in 808 the systematic index Table 2 of Section 5.6. The reason for padding 809 out a source block to a multiple of K' is to enable faster encoding 810 and decoding, and to minimize the amount of table information that 811 needs to be stored in the encoder and decoder. 813 For purposes of transmitting and receiving data, the value of K is 814 used to determine the number of source symbols in a source block, and 815 thus K needs to be known at the sender and the receiver. In this 816 case the sender and receiver can compute K' from K and the K'-K 817 padding symbols can be automatically added to the source block 818 without any additional communication. The encoding symbol ID (ESI) 819 is used by a sender and receiver to identify the encoding symbols of 820 a source block, where the encoding symbols of a source block consist 821 of the source symbols and the repair symbols associated with the 822 source block. For a source block with K source symbols, the ESIs for 823 the source symbols are 0,1,2,...,K-1 and the ESIs for the repair 824 symbols are K, K+1, K+2,... . Using the ESI for identifying encoding 825 symbols in transport ensures that the ESI values continue 826 consecutively between the source and repair symbols. 828 For purposes of encoding and decoding data, the value of K' derived 829 from K is used as the number of source symbols of the extended source 830 block upon which encoding and decoding operations are performed, 831 where the K' source symbols consist of the original K source symbols 832 and an additional K'-K padding symbols. The internal symbol ID (ISI) 833 is used by the encoder and decoder to identify the symbols associated 834 with the extended source block, i.e., for generating encoding symbols 835 and for decoding. For a source block with K original source symbols, 836 the ISIs for the original source symbols are 0,1,2,...,K-1, the ISIs 837 for the K'-K padding symbols are K, K+1, K+2,..., K'-1, and the ISIs 838 for the repair symbols are K', K'+1, K'+2,... . Using the ISI for 839 encoding and decoding allows the padding symbols of the extended 840 source block to be treated the same way as other source symbols of 841 the extended source block, and that a given prefix of repair symbols 842 are generated in a consistent way for a given number K' of source 843 symbols in the extended source block independent of K. 845 The relationship between the ESIs and the ISIs is simple: the ESIs 846 and the ISIs for the original K source symbols are the same, the K'-K 847 padding symbols have an ISI but do not have a corresponding ESI 848 (since they are symbols that are neither sent nor received), and a 849 repair symbol ISI is simply the repair symbol ESI plus K'-K. The 850 translation between ESIs used to identify encoding symbols sent and 851 received and the corresponding ISIs used for encoding and decoding, 852 and the proper padding of the extended source block with padding 853 symbols used for encoding and decoding, is the responsibility of the 854 padding function in the RaptorQ encoder/decoder. 856 5.3.2. Encoding overview 858 The systematic RaptorQ encoder is used to generate any number of 859 repair symbols from a source block that consists of K source symbols 860 placed into an extended source block C'. Figure 4 shows the encoding 861 overview. 863 The first step of encoding is to construct an extended source block 864 by adding zero or more padding symbols such that the total number of 865 symbols, K', is one of the values listed in Section 5.6. Each 866 padding symbol consists of T octets where the value of each octet is 867 zero. K' MUST be selected as the smallest value of K' from the table 868 of Section 5.6 which is greater than or equal to K. 870 -----------------------------------------------------------+ 871 | | 872 | +-----------+ +--------------+ +-------------+ | 873 C' | | | C' | Intermediate | C | | | 874 ----+--->| Padding |--->| Symbol |--->| Encoding |--+--> 875 K | | | K' | Generation | L | | | 876 | +-----------+ +--------------+ +-------------+ | 877 | | (d,a,b, ^ | 878 | | d1,a1,b1)| | 879 | | +------------+ | 880 | | K' | Tuple | | 881 | +----------------------------->| | | 882 | | Generation | | 883 | +------------+ | 884 | ^ | 885 +-------------------------------------------------+--------+ 886 | 887 ISI X 889 Figure 4: Encoding Overview 891 Let C'[0], ..., C'[K-1] denote the K source symbols. 893 Let C'[K], ..., C'[K'-1] denote the K'-K padding symbols, which are 894 all set to zero bits. Then, C'[0],..., C'[K'-1] are the symbols of 895 the extended source block upon which encoding and decoding are 896 performed. 898 In the remainder of this description these padding symbols will be 899 considered as additional source symbols and referred to as such. 900 However, these padding symbols are not part of the encoding symbols, 901 i.e., they are not sent as part of the encoding. At a receiver, the 902 value of K' can be computed based on K, then the receiver can insert 903 K'-K padding symbols at the end of a source block of K' source 904 symbols and recover the remaining K source symbols of the source 905 block from received encoding symbols. 907 The second step of encoding is to generate a number, L > K', of 908 intermediate symbols from the K' source symbols. In this step, K' 909 source tuples (d[0], a[0], b[0], d1[0], a1[0], b1[0]), ..., (d[K'-1], 910 a[K'-1], b[K'-1], d1[K'-1], a1[K'-1], b1[K'-1]) are generated using 911 the Tuple[] generator as described in Section 5.3.5.4. The K' source 912 tuples and the ISIs associated with the K' source symbols are used to 913 determine L intermediate symbols C[0],..., C[L-1] from the source 914 symbols using an inverse encoding process. This process can be 915 realized by a RaptorQ decoding process. 917 Certain "pre-coding relationships" must hold within the L 918 intermediate symbols. Section 5.3.3.3 describes these relationships. 919 Section 5.3.3.4 describes how the intermediate symbols are generated 920 from the source symbols. 922 Once the intermediate symbols have been generated, repair symbols can 923 be produced. For a repair symbol with ISI X>K', the tuple of non- 924 negative integers, (d, a, b, d1, a1, b1) can be generated, using the 925 Tuple[] generator as described in Section 5.3.5.4. Then, the (d, a, 926 b, d1, a1, b1)-tuple and the ISI X is used to generate the 927 corresponding repair symbol from the intermediate symbols using the 928 Enc[] generator described in Section 5.3.5.3. The corresponding ESI 929 for this repair symbol is then X-(K'-K). Note that source symbols of 930 the extended source block can also be generated using the same 931 process, i.e., for any X < K', the symbol generated using this 932 process has the same value as C'[X]. 934 5.3.3. First encoding step: Intermediate Symbol Generation 936 5.3.3.1. General 938 This encoding step is a pre-coding step to generate the L 939 intermediate symbols C[0], ..., C[L-1] from the source symbols C'[0], 940 ..., C'[K'-1], , where L > K' is defined in Section 5.3.3.3. The 941 intermediate symbols are uniquely defined by two sets of constraints: 943 1. The intermediate symbols are related to the source symbols by a 944 set of source symbol tuples and by the ISIs of the source 945 symbols. The generation of the source symbol tuples is defined 946 in Section 5.3.3.2 using the the Tuple[] generator as described 947 in Section 5.3.5.4. 949 2. A number of pre-coding relationships hold within the intermediate 950 symbols themselves. These are defined in Section 5.3.3.3 952 The generation of the L intermediate symbols is then defined in 953 Section 5.3.3.4. 955 5.3.3.2. Source symbol tuples 957 Each of the K' source symbols is associated with a source symbol 958 tuple (d[X], a[X], b[X], d1[X], a1[X], b1[X]) for 0 <= X < K'. The 959 source symbol tuples are determined using the Tuple generator defined 960 in Section 5.3.5.4 as: 962 For each X, 0 <= X < K' 963 (d[X], a[X], b[X], d1[X], a1[X], b1[X]) = Tuple[K, X] 965 5.3.3.3. Pre-coding relationships 967 The pre-coding relationships amongst the L intermediate symbols are 968 defined by requiring that a set of S+H linear combinations of the 969 intermediate symbols evaluate to zero. There are S LDPC and H HDPC 970 symbols, and thus L = K'+S+H. Another partition of the L intermediate 971 symbols is into two sets, one set of W LT symbols and another set of 972 P PI symbols, and thus it is also the case that L = W+P. The P PI 973 symbols are treated differently than the W LT symbols in the encoding 974 process. The P PI symbols consist of the H HDPC symbols together 975 with a set of U = P-H of the other K' intermediate symbols. The W LT 976 symbols consist of the S LDPC symbols together with W-S of the other 977 K' intermediate symbols. The values of these parameters are 978 determined from K' as described below where H(K'), S(K'), and W(K') 979 are derived from Table 2 in Section 5.6. 981 Let 983 o S = S(K') 985 o H = H(K') 987 o W = W(K') 989 o L = K' + S + H 991 o P = L - W 993 o P1 denote the smallest prime number greater than or equal to P 995 o U = P - H 997 o B = W - S 999 o C[0], ..., C[B-1] denote the intermediate symbols that are LT 1000 symbols but not LDPC symbols. 1002 o C[B], ..., C[B+S-1] denote the S LDPC symbols that are also LT 1003 symbols. 1005 o C[W], ..., C[W+U-1] denote the intermediate symbols that are PI 1006 symbols but not HDPC symbols. 1008 o C[L-H], ..., C[L-1] denote the H HDPC symbols that are also PI 1009 symbols. 1011 The first set of pre-coding relations, called LDPC relations, is 1012 described below and requires that at the end of this process the set 1013 of symbols D[0] , ..., D[S-1] are all zero: 1015 o Initialize the symbols D[0] = C[B], ..., D[S-1] = C[B+S-1]. 1017 o For i = 0, ..., B-1 do 1019 * a = 1 + floor(i/S) 1021 * b = i % S 1023 * D[b] = D[b] + C[i] 1025 * b = (b + a) % S 1027 * D[b] = D[b] + C[i] 1029 * b = (b + a) % S 1031 * D[b] = D[b] + C[i] 1033 o For i = 0, ..., S-1 do 1035 * a = i % P 1037 * b = (i+1) % P 1039 * D[i] = D[i] + C[W+a] + C[W+b] 1041 Recall that the addition of symbols is to be carried out as specified 1042 in Section 5.7. 1044 Note that the LDPC relations as defined in the algorithm above are 1045 linear, so there exists an S x B matrix G_LDPC,1 and an S x P matrix 1046 G_LDPC,2 such that 1048 G_LDPC,1 * Transpose[(C[0],...., C[B-1])] + G_LDPC,2 * 1049 Transpose(C[W], ..., C[W+P-1]) + Transpose[(C[B], ..., C[B+S-1])] 1050 = 0 1052 (The matrix G_LDPC,1 is defined by the first loop in the above 1053 algorithm, and G_LDPC,2 can be deduced from the second loop.) 1055 The second set of relations among the intermediate symbols C[0], ..., 1056 C[L-1] are the HDPC relations and they are defined as follows: 1058 Let 1059 o alpha denote the octet represented by integer 2 as defined in 1060 Section 5.7. 1062 o MT denote an H x (K' + S) matrix of octets, where for 1063 j=0,...,K'+S-2 the entry MT[i,j] is the octet represented by the 1064 integer 1 if i= Rand[j+1,6,H] or i = (Rand[j+1,6,H] + Rand[j+ 1065 1,7,H-1] + 1) % H and MT[i,j] is the zero element for all other 1066 values of i, and for j=K'+S-1, MT[i,j] = alpha^^i for i=0,...,H-1. 1068 o GAMMA denote a (K'+S ) x (K'+S ) matrix of octets, where 1070 GAMMA[i,j] = 1072 alpha ^^ (i-j) for i >= j, 1074 0 otherwise. 1076 Then the relationship between the first K'+S intermediate symbols 1077 C[0], ..., C[K'+S-1] and the H HDPC symbols C[K'+S], ..., C[K'+S+H-1] 1078 is given by: 1080 Transpose[C[K'+S], ..., C[K'+S+H-1]] + MT * GAMMA * 1081 Transpose[C[0], ..., C[K'+S-1]] = 0, 1083 where '*' represents standard matrix multiplication utilizing the 1084 octet multiplication to define the multiplication between a matrix of 1085 octets and a matrix of symbols (in particular the column vector of 1086 symbols) and '+' denotes addition over octet vectors. 1088 5.3.3.4. Intermediate symbols 1090 5.3.3.4.1. Definition 1092 Given the K' source symbols C'[0], C'[1],..., C'[K'-1] the L 1093 intermediate symbols C[0], C[1],..., C[L-1] are the uniquely defined 1094 symbol values that satisfy the following conditions: 1096 1. The K' source symbols C'[0], C'[1],..., C'[K'-1] satisfy the K' 1097 constraints 1099 C'[X] = Enc[K', (C[0],..., C[L-1]), (d[X], a[X], b[X], d1[X], 1100 a1[X], b1[X])], for all X, 0 <= X < K', 1102 where (d[X], a[X], b[X], d1[X], a1[X], b1[X])) = Tuple[K',X], 1103 Tuple[] is defined in Section 5.3.5.4 and Enc[] is described in 1104 Section 5.3.5.3. 1106 2. The L intermediate symbols C[0], C[1],..., C[L-1] satisfy the 1107 pre-coding relationships defined in Section 5.3.3.3 1109 5.3.3.4.2. Example method for calculation of intermediate symbols 1111 This section describes a possible method for calculation of the L 1112 intermediate symbols C[0], C[1],..., C[L-1] satisfying the 1113 constraints in Section 5.3.3.4.1 1115 The L intermediate symbols can be calculated as follows: 1117 Let 1119 o C denote the column vector of the L intermediate symbols, C[0], 1120 C[1],..., C[L-1]. 1122 o D denote the column vector consisting of S+H zero symbols followed 1123 by the K' source symbols C'[0], C'[1], ..., C'[K'-1]. 1125 Then the above constraints define an L x L matrix A of octets such 1126 that: 1128 A*C = D 1130 The matrix A can be constructed as follows: 1132 Let: 1134 o G_LDPC,1 and G_LDPC,2 be S x B and S x P matrices as defined in 1135 Section 5.3.3.3. 1137 o G_HDPC be the H x (K'+S) matrix such that 1139 G_HDPC * Transpose(C[0], ..., C[K'+S-1]) = Transpose(C[K'+S], 1140 ..., C[L-1]), 1142 i.e. G_HDPC = MT*GAMMA 1144 o I_S be the S x S identity matrix 1146 o I_H be the H x H identity matrix 1148 o G_ENC be the K' x L matrix such that 1150 G_ENC * Transpose[(C[0], ..., C[L-1])] = 1151 Transpose[(C'[0],C'[1],...,C'[K'-1])], 1152 i.e. G_ENC[i,j] = 1 if and only if C[j] is included in the 1153 symbols which are summed to produce Enc[K', (C[0], ..., 1154 C[L-1]), (d[i], a[i], b[i], d1[i], a1[i], b1[i])] and 1155 G_ENC[i,j] = 0 otherwise. 1157 Then: 1159 o The first S rows of A are equal to G_LDPC,1 | I_S | G_LDPC,2. 1161 o The next H rows of A are equal to G_HDPC | I_H. 1163 o The remaining K' rows of A are equal to G_ENC. 1165 The matrix A is depicted in Figure (Figure 5) below: 1167 B S U H 1168 +-----------------------+-------+------------------+ 1169 | | | | 1170 S | G_LDPC,1 | I_S | G_LDPC,2 | 1171 | | | | 1172 +-----------------------+-------+----------+-------+ 1173 | | | 1174 H | G_HDPC | I_H | 1175 | | | 1176 +------------------------------------------+-------+ 1177 | | 1178 | | 1179 K' | G_ENC | 1180 | | 1181 | | 1182 +--------------------------------------------------+ 1184 Figure 5: The matrix A 1186 The intermediate symbols can then be calculated as: 1188 C = (A^^-1)*D 1190 The source tuples are generated such that for any K' matrix A has 1191 full rank and is therefore invertible. This calculation can be 1192 realized by applying a RaptorQ decoding process to the K' source 1193 symbols C'[0], C'[1],..., C'[K'-1] to produce the L intermediate 1194 symbols C[0], C[1],..., C[L-1]. 1196 To efficiently generate the intermediate symbols from the source 1197 symbols, it is recommended that an efficient decoder implementation 1198 such as that described in Section 5.4 be used. 1200 5.3.4. Second encoding step: Encoding 1202 In the second encoding step, the repair symbol with ISI X (X >= K') 1203 is generated by applying the generator Enc[K', (C[0], C[1],..., 1204 C[L-1]), (d, a, b, d1, a1, b1)] defined in Section 5.3.5.3 to the L 1205 intermediate symbols C[0], C[1],..., C[L-1] using the tuple (d, a, b, 1206 d1, a1, b1)=Tuple[K',X]. 1208 5.3.5. Generators 1210 5.3.5.1. Random Number Generator 1212 The random number generator Rand[y, i, m] is defined as follows, 1213 where y is a non-negative integer, i is a non-negative integer less 1214 than 256, and m is a positive integer and the value produced is an 1215 integer between 0 and m-1. Let V0, V1, V2 and V3 be the arrays 1216 provided in Section 5.5. 1218 Let 1220 o x0 = (y + i) mod 2^^8 1222 o x1 = (floor(y / 2^^8) + i) mod 2^^8 1224 o x2 = (floor(y / 2^^16) + i) mod 2^^8 1226 o x3 = (floor(y / 2^^24) + i) mod 2^^8 1228 Then 1230 Rand[y, i, m] = (V0[x0] ^ V1[x1] ^ V2[x2] ^ V3[x3]) % m 1232 5.3.5.2. Degree Generator 1234 The degree generator Deg[v] is defined as follows, where v is a non- 1235 negative integer that is less than 2^^20 = 1048576. Given v, find 1236 index d in Table 1 such that f[d-1] <= v < f[d], and set Deg[v] = 1237 min(d, W-2). ). Recall that W is derived from K' as described in 1238 Section 5.3.3.3. 1240 +---------+---------+---------+---------+ 1241 | Index d | f[d] | Index d | f[d] | 1242 +---------+---------+---------+---------+ 1243 | 0 | 0 | 1 | 5243 | 1244 +---------+---------+---------+---------+ 1245 | 2 | 529531 | 3 | 704294 | 1246 +---------+---------+---------+---------+ 1247 | 4 | 791675 | 5 | 844104 | 1248 +---------+---------+---------+---------+ 1249 | 6 | 879057 | 7 | 904023 | 1250 +---------+---------+---------+---------+ 1251 | 8 | 922747 | 9 | 937311 | 1252 +---------+---------+---------+---------+ 1253 | 10 | 948962 | 11 | 958494 | 1254 +---------+---------+---------+---------+ 1255 | 12 | 966438 | 13 | 973160 | 1256 +---------+---------+---------+---------+ 1257 | 14 | 978921 | 15 | 983914 | 1258 +---------+---------+---------+---------+ 1259 | 16 | 988283 | 17 | 992138 | 1260 +---------+---------+---------+---------+ 1261 | 18 | 995565 | 19 | 998631 | 1262 +---------+---------+---------+---------+ 1263 | 20 | 1001391 | 21 | 1003887 | 1264 +---------+---------+---------+---------+ 1265 | 22 | 1006157 | 23 | 1008229 | 1266 +---------+---------+---------+---------+ 1267 | 24 | 1010129 | 25 | 1011876 | 1268 +---------+---------+---------+---------+ 1269 | 26 | 1013490 | 27 | 1014983 | 1270 +---------+---------+---------+---------+ 1271 | 28 | 1016370 | 29 | 1017662 | 1272 +---------+---------+---------+---------+ 1273 | 30 | 1048576 | | | 1274 +---------+---------+---------+---------+ 1276 Table 1: Defines the degree distribution for encoding symbols 1278 5.3.5.3. Encoding Symbol Generator 1280 The encoding symbol generator Enc[K', (C[0], C[1],..., C[L-1]), (d, 1281 a, b, d1, a1, b1)] takes the following inputs: 1283 o K' is the number of source symbols for the extended source block. 1284 Let L, W, B, S, P and P1 be derived from K' as described in 1285 Section 5.3.3.3. 1287 o (C[0], C[1],..., C[L-1]) is the array of L intermediate symbols 1288 (sub-symbols) generated as described in Section 5.3.3.4 1290 o (d, a, b, d1, a1, b1) is a source tuple determined from ISI X 1291 using the Tuple generator defined in Section 5.3.5.4, whereby 1293 * d is a positive integer denoting an encoding symbol LT degree 1295 * a is a positive integer between 1 and W-1 inclusive 1297 * b is a non-negative integer between 0 and W-1 inclusive 1299 * d1 is a positive integer that has value either 2 or 3 inclusive 1300 denoting an encoding symbol PI degree 1302 * a1 is a positive integer between 1 and P1-1 inclusive 1304 * b1 is a non-negative integer between 0 and P1-1 inclusive 1306 The encoding symbol generator produces a single encoding symbol as 1307 output (referred to as result), according to the following algorithm: 1309 o result = C[b] 1311 o For j = 1, ..., d-1 do 1313 * b = (b + a) % W 1315 * result = result + C[b] 1317 o While (b1 >= P) do b1 = (b1+a1) % P1 1319 o result = result + C[W+b1] 1321 o For j = 1, ..., d1-1 do 1323 * b1 = (b1 + a1) % P1 1325 * While (b1 >= P) do b1 = (b1+a1) % P1 1327 * result = result + C[W+b1] 1329 o Return result 1331 5.3.5.4. Tuple generator 1333 The tuple generator Tuple[K',X] takes the following inputs: 1335 o K' - The number of source symbols in the extended source block 1337 o X - An ISI 1339 Let 1341 o L be determined from K' as described in Section 5.3.3.3 1343 o J=J(K') be the systematic index associated with K', as defined in 1344 Table 2 inSection 5.6 1346 The output of tuple generator is a tuple, (d, a, b, d1, a1, b1), 1347 determined as follows: 1349 o A = 53591 + J*997 1351 o if (A % 2 == 0) { A = A + 1 } 1353 o B = 10267*(J+1) 1355 o y = (B + X*A) % 2^^32 1357 o v = Rand[y, 0, 2^^20] 1359 o d = Deg[v] 1361 o a = 1 + Rand[y, 1, W-1] 1363 o b = Rand[y, 2, W] 1365 o If (d<4) { d1 = 2 + Rand[X, 3, 2] } else { d1 = 2 } 1367 o a1 = 1 + Rand[X, 4, P1-1] 1369 o b1 = Rand[X, 5, P1] 1371 5.4. Example FEC decoder 1373 5.4.1. General 1375 This section describes an efficient decoding algorithm for the 1376 RaptorQ code introduced in this specification. Note that each 1377 received encoding symbol is a known linear combination of the 1378 intermediate symbols. So each received encoding symbol provides a 1379 linear equation among the intermediate symbols, which, together with 1380 the known linear pre-coding relationships amongst the intermediate 1381 symbols gives a system of linear equations. Thus, any algorithm for 1382 solving systems of linear equations can successfully decode the 1383 intermediate symbols and hence the source symbols. However, the 1384 algorithm chosen has a major effect on the computational efficiency 1385 of the decoding. 1387 5.4.2. Decoding an extended source block 1389 5.4.2.1. General 1391 It is assumed that the decoder knows the structure of the source 1392 block it is to decode, including the symbol size, T, and the number K 1393 of symbols in the source block and the number K' of source symbols in 1394 the extended source block. 1396 From the algorithms described in Section 5.3, the RaptorQ decoder can 1397 calculate the total number L = K'+S+H of intermediate symbols and 1398 determine how they were generated from the extended source block to 1399 be decoded. In this description it is assumed that the received 1400 encoding symbols for the extended source block to be decoded are 1401 passed to the decoder. Furthermore, for each such encoding symbol it 1402 is assumed that the number and set of intermediate symbols whose sum 1403 is equal to the encoding symbol are passed to the decoder. In the 1404 case of source symbols, including padding symbols, the source symbol 1405 tuples described in Section 5.3.3.2 indicate the number and set of 1406 intermediate symbols which sum to give each source symbol. 1408 Let N >= K' be the number of received encoding symbols to be used for 1409 decoding, including padding symbols for an extended source block and 1410 let M = S+H+N. Then with the notation of Section 5.3.3.4.2 we have 1411 A*C=D. 1413 Decoding an extended source block is equivalent to decoding C from 1414 known A and D. It is clear that C can be decoded if and only if the 1415 rank of A is L. Once C has been decoded, missing source symbols can 1416 be obtained by using the source symbol tuples to determine the number 1417 and set of intermediate symbols which must be summed to obtain each 1418 missing source symbol. 1420 The first step in decoding C is to form a decoding schedule. In this 1421 step A is converted, using Gaussian elimination (using row operations 1422 and row and column reorderings) and after discarding M - L rows, into 1423 the L by L identity matrix. The decoding schedule consists of the 1424 sequence of row operations and row and column re-orderings during the 1425 Gaussian elimination process, and only depends on A and not on D. The 1426 decoding of C from D can take place concurrently with the forming of 1427 the decoding schedule, or the decoding can take place afterwards 1428 based on the decoding schedule. 1430 The correspondence between the decoding schedule and the decoding of 1431 C is as follows. Let c[0] = 0, c[1] = 1, ..., c[L-1] = L-1 and d[0] 1432 = 0, d[1] = 1, ..., d[M-1] = M-1 initially. 1434 o Each time a multiple, beta, of row i of A is added to row i' in 1435 the decoding schedule then in the decoding process the symbol 1436 beta*D[d[i]] is added to symbol D[d[i']] . 1438 o Each time a row i of A is multiplied by an octet beta, then in the 1439 decoding process the symbol D[d[i]] is also multiplied by beta. 1441 o Each time row i is exchanged with row i' in the decoding schedule 1442 then in the decoding process the value of d[i] is exchanged with 1443 the value of d[i']. 1445 o Each time column j is exchanged with column j' in the decoding 1446 schedule then in the decoding process the value of c[j] is 1447 exchanged with the value of c[j']. 1449 From this correspondence it is clear that the total number of 1450 operations on symbols in the decoding of the extended source block is 1451 the number of row operations (not exchanges) in the Gaussian 1452 elimination. Since A is the L by L identity matrix after the 1453 Gaussian elimination and after discarding the last M - L rows, it is 1454 clear at the end of successful decoding that the L symbols D[d[0]], 1455 D[d[1]],..., D[d[L-1]] are the values of the L symbols C[c[0]], 1456 C[c[1]],..., C[c[L-1]]. 1458 The order in which Gaussian elimination is performed to form the 1459 decoding schedule has no bearing on whether or not the decoding is 1460 successful. However, the speed of the decoding depends heavily on 1461 the order in which Gaussian elimination is performed. (Furthermore, 1462 maintaining a sparse representation of A is crucial, although this is 1463 not described here). The remainder of this section describes an 1464 order in which Gaussian elimination could be performed that is 1465 relatively efficient. 1467 5.4.2.2. First Phase 1469 In the first phase of the Gaussian elimination the matrix A is 1470 conceptually partitioned into submatrices and additionally, a matrix 1471 X is created. This matrix has as many rows and columns as A, and it 1472 will be a lower triangular matrix throughout the first phase. At the 1473 beginning of this phase, the matrix A is copied into the matrix X. 1474 The submatrix sizes are parameterized by non-negative integers i and 1475 u which are initialized to 0 and P, the number of PI symbols, 1476 respectively. The submatrices of A are: 1478 1. The submatrix I defined by the intersection of the first i rows 1479 and first i columns. This is the identity matrix at the end of 1480 each step in the phase. 1482 2. The submatrix defined by the intersection of the first i rows and 1483 all but the first i columns and last u columns. All entries of 1484 this submatrix are zero. 1486 3. The submatrix defined by the intersection of the first i columns 1487 and all but the first i rows. All entries of this submatrix are 1488 zero. 1490 4. The submatrix U defined by the intersection of all the rows and 1491 the last u columns. 1493 5. The submatrix V formed by the intersection of all but the first i 1494 columns and the last u columns and all but the first i rows. 1496 Figure 6 illustrates the submatrices of A. At the beginning of the 1497 first phase V consists of the first L-P columns of A and U consists 1498 of the last P columns corresponding to the PI symbols. In each step, 1499 a row of A is chosen. 1501 +-----------+-----------------+---------+ 1502 | | | | 1503 | I | All Zeros | 1504 | | | | 1505 +-----------+-----------------+ U | 1506 | | | | 1507 | | | | 1508 | All Zeros | V | | 1509 | | | | 1510 | | | | 1511 +-----------+-----------------+---------+ 1513 Figure 6: Submatrices of A in the first phase 1515 The following graph defined by the structure of V is used in 1516 determining which row of A is chosen. The columns that intersect V 1517 are the nodes in the graph, and the rows that have exactly 2 non-zero 1518 entries in V and are not HDPC rows are the edges of the graph that 1519 connect the two columns (nodes) in the positions of the two ones. A 1520 component in this graph is a maximal set of nodes (columns) and edges 1521 (rows) such that there is a path between each pair of nodes/edges in 1522 the graph. The size of a component is the number of nodes (columns) 1523 in the component. 1525 There are at most L steps in the first phase. The phase ends 1526 successfully when i + u = L, i.e., when V and the all zeroes 1527 submatrix above V have disappeared and A consists of I, the all 1528 zeroes submatrix below I, and U. The phase ends unsuccessfully in 1529 decoding failure if at some step before V disappears there is no non- 1530 zero row in V to choose in that step. In each step, a row of A is 1531 chosen as follows: 1533 o If all entries of V are zero then no row is chosen and decoding 1534 fails. 1536 o Let r be the minimum integer such that at least one row of A has 1537 exactly r non-zeroes in V. 1539 * If r != 2 then choose a row with exactly r non-zeroes in V with 1540 minimum original degree among all such rows, except that HDPC 1541 rows should not be chosen until all non-HDPC rows have been 1542 processed. 1544 * If r = 2 and there is a row with exactly 2 ones in V then 1545 choose any row with exactly 2 ones in V that is part of a 1546 maximum size component in the graph described above that is 1547 defined by V. 1549 * If r = 2 and there is no row with exactly 2 ones in V then 1550 choose any row with exactly 2 non-zeroes in V. 1552 After the row is chosen in this step the first row of A that 1553 intersects V is exchanged with the chosen row so that the chosen row 1554 is the first row that intersects V. The columns of A among those that 1555 intersect V are reordered so that one of the r non-zeroes in the 1556 chosen row appears in the first column of V and so that the remaining 1557 r-1 non-zeroes appear in the last columns of V. The same row and 1558 column operations are also performed on the matrix X. Then, an 1559 appropriate multiple of the chosen row is added to all the other rows 1560 of A below the chosen row that have a non-zero entry in the first 1561 column of V. Specifically, if a row below the chosen row has entry 1562 beta in the first column of V, and the chosen row has entry alpha in 1563 the first column of V, then beta/alpha multiplied by the chosen row 1564 is added to this row to leave a zero value in the first column of V. 1565 Finally, i is incremented by 1 and u is incremented by r-1, which 1566 completes the step. 1568 Note that efficiency can be improved if the row operations identified 1569 above are not actually performed until the affected row is itself 1570 chosen during the decoding process. This avoids processing of row 1571 operations for rows which are not eventually used in the decoding 1572 process and in particular avoid those rows for which beta!=1 until 1573 they are actually required. Furthermore, the row operations required 1574 for the HDPC rows may be performed for all such rows in one process, 1575 by using the algorithm described in Section 5.3.3.3. 1577 5.4.2.3. Second Phase 1579 At this point, all the entries of X outside the first i rows and i 1580 columns are discarded, so that X has lower triangular form. The last 1581 i rows and columns of X are discarded, so that X now has i rows i 1582 columns. The submatrix U is further partitioned into the first i 1583 rows, U_upper, and the remaining M - i rows, U_lower. Gaussian 1584 elimination is performed in the second phase on U_lower to either 1585 determine that its rank is less than u (decoding failure) or to 1586 convert it into a matrix where the first u rows is the identity 1587 matrix (success of the second phase). Call this u by u identity 1588 matrix I_u. The M - L rows of A that intersect U_lower - I_u are 1589 discarded. After this phase A has L rows and L columns. 1591 5.4.2.4. Third Phase 1593 After the second phase the only portion of A which needs to be zeroed 1594 out to finish converting A into the L by L identity matrix is 1595 U_upper. The number of rows i of the submatrix U_upper is generally 1596 much larger than the number of columns u of U_upper. Moreover, at 1597 this time, the matrix U_upper is typically dense, i.e., the number of 1598 nonzero entries of this matrix is large. To reduce this matrix to a 1599 sparse form, the sequence of operations performed to obtain the 1600 matrix U_lower needs to be inverted. To this end, the matrix X is 1601 multiplied with the submatrix of A consisting of the first i rows of 1602 A. After this operation the submatrix of A consisting of the 1603 intersection of the first i rows and columns equals to X, whereas the 1604 matrix U_upper is transformed to a sparse form. 1606 5.4.2.5. Fourth Phase 1608 For each of the first i rows of U_upper do the following: if the row 1609 has a nonzero entry at position j, and if the value of that nonzero 1610 entry is b, then add to this row b times row j of I_u. After this 1611 step, the submatrix of A consisting of the intersection of the first 1612 i rows and columns is equal to X, the submatrix U_upper consists of 1613 zeros, the submatrix consisting of the intersection of the last u 1614 rows and the first i columns consists of zeros, and the submatrix 1615 consisting of the last u rows and columns is is the matrix I_u. 1617 5.4.2.6. Fifth Phase 1619 For j from 1 to i perform the following operations: 1621 1. if A[j,j] is not one, then divide row j of A by A[j,j]. 1623 2. For l from 1 to j-1, if A[j,l] is nonzero, then add A[j,l] 1624 multiplied with row l of A to row j of A. 1626 After this phase A is the L by L identity matrix and a complete 1627 decoding schedule has been successfully formed. Then, the 1628 corresponding decoding consisting of summing known encoding symbols 1629 can be executed to recover the intermediate symbols based on the 1630 decoding schedule. The tuples associated with all source symbols are 1631 computed according to Section 5.3.3.2. The tuples for received 1632 source symbols are used in the decoding. The tuples for missing 1633 source symbols are used to determine which intermediate symbols need 1634 to be summed to recover the missing source symbols. 1636 5.5. Random Numbers 1638 The four arrays V0, V1, V2 and V3 used in Section 5.3.5.1 are 1639 provided below. There are 256 entries in each of the four arrays. 1640 The indexing into each array starts at 0, and the entries are 32-bit 1641 unsigned integers. 1643 5.5.1. The table V0 1645 251291136, 3952231631, 3370958628, 4070167936, 123631495, 3351110283, 1646 3218676425, 2011642291, 774603218, 2402805061, 1004366930, 1647 1843948209, 428891132, 3746331984, 1591258008, 3067016507, 1648 1433388735, 504005498, 2032657933, 3419319784, 2805686246, 1649 3102436986, 3808671154, 2501582075, 3978944421, 246043949, 1650 4016898363, 649743608, 1974987508, 2651273766, 2357956801, 689605112, 1651 715807172, 2722736134, 191939188, 3535520147, 3277019569, 1470435941, 1652 3763101702, 3232409631, 122701163, 3920852693, 782246947, 372121310, 1653 2995604341, 2045698575, 2332962102, 4005368743, 218596347, 1654 3415381967, 4207612806, 861117671, 3676575285, 2581671944, 1655 3312220480, 681232419, 307306866, 4112503940, 1158111502, 709227802, 1656 2724140433, 4201101115, 4215970289, 4048876515, 3031661061, 1657 1909085522, 510985033, 1361682810, 129243379, 3142379587, 2569842483, 1658 3033268270, 1658118006, 932109358, 1982290045, 2983082771, 1659 3007670818, 3448104768, 683749698, 778296777, 1399125101, 1939403708, 1660 1692176003, 3868299200, 1422476658, 593093658, 1878973865, 1661 2526292949, 1591602827, 3986158854, 3964389521, 2695031039, 1662 1942050155, 424618399, 1347204291, 2669179716, 2434425874, 1663 2540801947, 1384069776, 4123580443, 1523670218, 2708475297, 1664 1046771089, 2229796016, 1255426612, 4213663089, 1521339547, 1665 3041843489, 420130494, 10677091, 515623176, 3457502702, 2115821274, 1666 2720124766, 3242576090, 854310108, 425973987, 325832382, 1796851292, 1667 2462744411, 1976681690, 1408671665, 1228817808, 3917210003, 1668 263976645, 2593736473, 2471651269, 4291353919, 650792940, 1191583883, 1669 3046561335, 2466530435, 2545983082, 969168436, 2019348792, 1670 2268075521, 1169345068, 3250240009, 3963499681, 2560755113, 1671 911182396, 760842409, 3569308693, 2687243553, 381854665, 2613828404, 1672 2761078866, 1456668111, 883760091, 3294951678, 1604598575, 1673 1985308198, 1014570543, 2724959607, 3062518035, 3115293053, 1674 138853680, 4160398285, 3322241130, 2068983570, 2247491078, 1675 3669524410, 1575146607, 828029864, 3732001371, 3422026452, 1676 3370954177, 4006626915, 543812220, 1243116171, 3928372514, 1677 2791443445, 4081325272, 2280435605, 885616073, 616452097, 3188863436, 1678 2780382310, 2340014831, 1208439576, 258356309, 3837963200, 1679 2075009450, 3214181212, 3303882142, 880813252, 1355575717, 207231484, 1680 2420803184, 358923368, 1617557768, 3272161958, 1771154147, 1681 2842106362, 1751209208, 1421030790, 658316681, 194065839, 3241510581, 1682 38625260, 301875395, 4176141739, 297312930, 2137802113, 1502984205, 1683 3669376622, 3728477036, 234652930, 2213589897, 2734638932, 1684 1129721478, 3187422815, 2859178611, 3284308411, 3819792700, 1685 3557526733, 451874476, 1740576081, 3592838701, 1709429513, 1686 3702918379, 3533351328, 1641660745, 179350258, 2380520112, 1687 3936163904, 3685256204, 3156252216, 1854258901, 2861641019, 1688 3176611298, 834787554, 331353807, 517858103, 3010168884, 4012642001, 1689 2217188075, 3756943137, 3077882590, 2054995199, 3081443129, 1690 3895398812, 1141097543, 2376261053, 2626898255, 2554703076, 1691 401233789, 1460049922, 678083952, 1064990737, 940909784, 1673396780, 1692 528881783, 1712547446, 3629685652, 1358307511 1694 5.5.2. The table V1 1696 807385413, 2043073223, 3336749796, 1302105833, 2278607931, 541015020, 1697 1684564270, 372709334, 3508252125, 1768346005, 1270451292, 1698 2603029534, 2049387273, 3891424859, 2152948345, 4114760273, 1699 915180310, 3754787998, 700503826, 2131559305, 1308908630, 224437350, 1700 4065424007, 3638665944, 1679385496, 3431345226, 1779595665, 1701 3068494238, 1424062773, 1033448464, 4050396853, 3302235057, 1702 420600373, 2868446243, 311689386, 259047959, 4057180909, 1575367248, 1703 4151214153, 110249784, 3006865921, 4293710613, 3501256572, 998007483, 1704 499288295, 1205710710, 2997199489, 640417429, 3044194711, 486690751, 1705 2686640734, 2394526209, 2521660077, 49993987, 3843885867, 4201106668, 1706 415906198, 19296841, 2402488407, 2137119134, 1744097284, 579965637, 1707 2037662632, 852173610, 2681403713, 1047144830, 2982173936, 910285038, 1708 4187576520, 2589870048, 989448887, 3292758024, 506322719, 176010738, 1709 1865471968, 2619324712, 564829442, 1996870325, 339697593, 4071072948, 1710 3618966336, 2111320126, 1093955153, 957978696, 892010560, 1854601078, 1711 1873407527, 2498544695, 2694156259, 1927339682, 1650555729, 1712 183933047, 3061444337, 2067387204, 228962564, 3904109414, 1595995433, 1713 1780701372, 2463145963, 307281463, 3237929991, 3852995239, 1714 2398693510, 3754138664, 522074127, 146352474, 4104915256, 3029415884, 1715 3545667983, 332038910, 976628269, 3123492423, 3041418372, 2258059298, 1716 2139377204, 3243642973, 3226247917, 3674004636, 2698992189, 1717 3453843574, 1963216666, 3509855005, 2358481858, 747331248, 1718 1957348676, 1097574450, 2435697214, 3870972145, 1888833893, 1719 2914085525, 4161315584, 1273113343, 3269644828, 3681293816, 1720 412536684, 1156034077, 3823026442, 1066971017, 3598330293, 1721 1979273937, 2079029895, 1195045909, 1071986421, 2712821515, 1722 3377754595, 2184151095, 750918864, 2585729879, 4249895712, 1723 1832579367, 1192240192, 946734366, 31230688, 3174399083, 3549375728, 1724 1642430184, 1904857554, 861877404, 3277825584, 4267074718, 1725 3122860549, 666423581, 644189126, 226475395, 307789415, 1196105631, 1726 3191691839, 782852669, 1608507813, 1847685900, 4069766876, 1727 3931548641, 2526471011, 766865139, 2115084288, 4259411376, 1728 3323683436, 568512177, 3736601419, 1800276898, 4012458395, 1823982, 1729 27980198, 2023839966, 869505096, 431161506, 1024804023, 1853869307, 1730 3393537983, 1500703614, 3019471560, 1351086955, 3096933631, 1731 3034634988, 2544598006, 1230942551, 3362230798, 159984793, 491590373, 1732 3993872886, 3681855622, 903593547, 3535062472, 1799803217, 772984149, 1733 895863112, 1899036275, 4187322100, 101856048, 234650315, 3183125617, 1734 3190039692, 525584357, 1286834489, 455810374, 1869181575, 922673938, 1735 3877430102, 3422391938, 1414347295, 1971054608, 3061798054, 1736 830555096, 2822905141, 167033190, 1079139428, 4210126723, 3593797804, 1737 429192890, 372093950, 1779187770, 3312189287, 204349348, 452421568, 1738 2800540462, 3733109044, 1235082423, 1765319556, 3174729780, 1739 3762994475, 3171962488, 442160826, 198349622, 45942637, 1324086311, 1740 2901868599, 678860040, 3812229107, 19936821, 1119590141, 3640121682, 1741 3545931032, 2102949142, 2828208598, 3603378023, 4135048896 1743 5.5.3. The table V2 1745 1629829892, 282540176, 2794583710, 496504798, 2990494426, 3070701851, 1746 2575963183, 4094823972, 2775723650, 4079480416, 176028725, 1747 2246241423, 3732217647, 2196843075, 1306949278, 4170992780, 1748 4039345809, 3209664269, 3387499533, 293063229, 3660290503, 1749 2648440860, 2531406539, 3537879412, 773374739, 4184691853, 1750 1804207821, 3347126643, 3479377103, 3970515774, 1891731298, 1751 2368003842, 3537588307, 2969158410, 4230745262, 831906319, 1752 2935838131, 264029468, 120852739, 3200326460, 355445271, 2296305141, 1753 1566296040, 1760127056, 20073893, 3427103620, 2866979760, 2359075957, 1754 2025314291, 1725696734, 3346087406, 2690756527, 99815156, 4248519977, 1755 2253762642, 3274144518, 598024568, 3299672435, 556579346, 4121041856, 1756 2896948975, 3620123492, 918453629, 3249461198, 2231414958, 1757 3803272287, 3657597946, 2588911389, 242262274, 1725007475, 1758 2026427718, 46776484, 2873281403, 2919275846, 3177933051, 1918859160, 1759 2517854537, 1857818511, 3234262050, 479353687, 200201308, 2801945841, 1760 1621715769, 483977159, 423502325, 3689396064, 1850168397, 3359959416, 1761 3459831930, 841488699, 3570506095, 930267420, 1564520841, 2505122797, 1762 593824107, 1116572080, 819179184, 3139123629, 1414339336, 1076360795, 1763 512403845, 177759256, 1701060666, 2239736419, 515179302, 2935012727, 1764 3821357612, 1376520851, 2700745271, 966853647, 1041862223, 715860553, 1765 171592961, 1607044257, 1227236688, 3647136358, 1417559141, 1766 4087067551, 2241705880, 4194136288, 1439041934, 20464430, 119668151, 1767 2021257232, 2551262694, 1381539058, 4082839035, 498179069, 311508499, 1768 3580908637, 2889149671, 142719814, 1232184754, 3356662582, 1769 2973775623, 1469897084, 1728205304, 1415793613, 50111003, 3133413359, 1770 4074115275, 2710540611, 2700083070, 2457757663, 2612845330, 1771 3775943755, 2469309260, 2560142753, 3020996369, 1691667711, 1772 4219602776, 1687672168, 1017921622, 2307642321, 368711460, 1773 3282925988, 213208029, 4150757489, 3443211944, 2846101972, 1774 4106826684, 4272438675, 2199416468, 3710621281, 497564971, 285138276, 1775 765042313, 916220877, 3402623607, 2768784621, 1722849097, 3386397442, 1776 487920061, 3569027007, 3424544196, 217781973, 2356938519, 3252429414, 1777 145109750, 2692588106, 2454747135, 1299493354, 4120241887, 1778 2088917094, 932304329, 1442609203, 952586974, 3509186750, 753369054, 1779 854421006, 1954046388, 2708927882, 4047539230, 3048925996, 1780 1667505809, 805166441, 1182069088, 4265546268, 4215029527, 1781 3374748959, 373532666, 2454243090, 2371530493, 3651087521, 1782 2619878153, 1651809518, 1553646893, 1227452842, 703887512, 1783 3696674163, 2552507603, 2635912901, 895130484, 3287782244, 1784 3098973502, 990078774, 3780326506, 2290845203, 41729428, 1949580860, 1785 2283959805, 1036946170, 1694887523, 4880696, 466000198, 2765355283, 1786 3318686998, 1266458025, 3919578154, 3545413527, 2627009988, 1787 3744680394, 1696890173, 3250684705, 4142417708, 915739411, 1788 3308488877, 1289361460, 2942552331, 1169105979, 3342228712, 1789 698560958, 1356041230, 2401944293, 107705232, 3701895363, 903928723, 1790 3646581385, 844950914, 1944371367, 3863894844, 2946773319, 1791 1972431613, 1706989237, 29917467, 3497665928 1793 5.5.4. The table V3 1795 1191369816, 744902811, 2539772235, 3213192037, 3286061266, 1796 1200571165, 2463281260, 754888894, 714651270, 1968220972, 3628497775, 1797 1277626456, 1493398934, 364289757, 2055487592, 3913468088, 1798 2930259465, 902504567, 3967050355, 2056499403, 692132390, 186386657, 1799 832834706, 859795816, 1283120926, 2253183716, 3003475205, 1755803552, 1800 2239315142, 4271056352, 2184848469, 769228092, 1249230754, 1801 1193269205, 2660094102, 642979613, 1687087994, 2726106182, 446402913, 1802 4122186606, 3771347282, 37667136, 192775425, 3578702187, 1952659096, 1803 3989584400, 3069013882, 2900516158, 4045316336, 3057163251, 1804 1702104819, 4116613420, 3575472384, 2674023117, 1409126723, 1805 3215095429, 1430726429, 2544497368, 1029565676, 1855801827, 1806 4262184627, 1854326881, 2906728593, 3277836557, 2787697002, 1807 2787333385, 3105430738, 2477073192, 748038573, 1088396515, 1808 1611204853, 201964005, 3745818380, 3654683549, 3816120877, 1809 3915783622, 2563198722, 1181149055, 33158084, 3723047845, 3790270906, 1810 3832415204, 2959617497, 372900708, 1286738499, 1932439099, 1811 3677748309, 2454711182, 2757856469, 2134027055, 2780052465, 1812 3190347618, 3758510138, 3626329451, 1120743107, 1623585693, 1813 1389834102, 2719230375, 3038609003, 462617590, 260254189, 3706349764, 1814 2556762744, 2874272296, 2502399286, 4216263978, 2683431180, 1815 2168560535, 3561507175, 668095726, 680412330, 3726693946, 4180630637, 1816 3335170953, 942140968, 2711851085, 2059233412, 4265696278, 1817 3204373534, 232855056, 881788313, 2258252172, 2043595984, 3758795150, 1818 3615341325, 2138837681, 1351208537, 2923692473, 3402482785, 1819 2105383425, 2346772751, 499245323, 3417846006, 2366116814, 1820 2543090583, 1828551634, 3148696244, 3853884867, 1364737681, 1821 2200687771, 2689775688, 232720625, 4071657318, 2671968983, 1822 3531415031, 1212852141, 867923311, 3740109711, 1923146533, 1823 3237071777, 3100729255, 3247856816, 906742566, 4047640575, 1824 4007211572, 3495700105, 1171285262, 2835682655, 1634301229, 1825 3115169925, 2289874706, 2252450179, 944880097, 371933491, 1649074501, 1826 2208617414, 2524305981, 2496569844, 2667037160, 1257550794, 1827 3399219045, 3194894295, 1643249887, 342911473, 891025733, 3146861835, 1828 3789181526, 938847812, 1854580183, 2112653794, 2960702988, 1829 1238603378, 2205280635, 1666784014, 2520274614, 3355493726, 1830 2310872278, 3153920489, 2745882591, 1200203158, 3033612415, 1831 2311650167, 1048129133, 4206710184, 4209176741, 2640950279, 1832 2096382177, 4116899089, 3631017851, 4104488173, 1857650503, 1833 3801102932, 445806934, 3055654640, 897898279, 3234007399, 1325494930, 1834 2982247189, 1619020475, 2720040856, 885096170, 3485255499, 1835 2983202469, 3891011124, 546522756, 1524439205, 2644317889, 1836 2170076800, 2969618716, 961183518, 1081831074, 1037015347, 1837 3289016286, 2331748669, 620887395, 303042654, 3990027945, 1562756376, 1838 3413341792, 2059647769, 2823844432, 674595301, 2457639984, 1839 4076754716, 2447737904, 1583323324, 625627134, 3076006391, 345777990, 1840 1684954145, 879227329, 3436182180, 1522273219, 3802543817, 1841 1456017040, 1897819847, 2970081129, 1382576028, 3820044861, 1842 1044428167, 612252599, 3340478395, 2150613904, 3397625662, 1843 3573635640, 3432275192 1845 5.6. Systematic indices and other parameters 1847 Table 2 below specifies the supported values of K'. The table also 1848 specifies for each supported value of K' the systematic index J(K'), 1849 the number H(K') of HDPC symbols, the number S(K') of LDPC symbols, 1850 and the number W(K') of LT symbols. For each value of K', the 1851 corresponding values of S(K') and W(K') are prime numbers. 1853 The systematic index J(K') is designed to have the property that the 1854 set of source symbol tuples (d[0], a[0], b[0], d1[0], a1[0], b1[0]), 1855 ..., (d[K'-1], a[K'-1], b[K'-1], d1[K'-1], a1[K'-1], b1[K'-1]) are 1856 such that the L intermediate symbols are uniquely defined, i.e., the 1857 matrix A in Figure 6 has full rank and is therefore invertible. 1859 +-------+-------+-------+-------+-------+ 1860 | K' | J(K') | S(K') | H(K') | W(K') | 1861 +-------+-------+-------+-------+-------+ 1862 | 10 | 254 | 7 | 10 | 17 | 1863 +-------+-------+-------+-------+-------+ 1864 | 12 | 630 | 7 | 10 | 19 | 1865 +-------+-------+-------+-------+-------+ 1866 | 18 | 682 | 11 | 10 | 29 | 1867 +-------+-------+-------+-------+-------+ 1868 | 20 | 293 | 11 | 10 | 31 | 1869 +-------+-------+-------+-------+-------+ 1870 | 26 | 80 | 11 | 10 | 37 | 1871 +-------+-------+-------+-------+-------+ 1872 | 30 | 566 | 11 | 10 | 41 | 1873 +-------+-------+-------+-------+-------+ 1874 | 32 | 860 | 11 | 10 | 43 | 1875 +-------+-------+-------+-------+-------+ 1876 | 36 | 267 | 11 | 10 | 47 | 1877 +-------+-------+-------+-------+-------+ 1878 | 42 | 822 | 11 | 10 | 53 | 1879 +-------+-------+-------+-------+-------+ 1880 | 46 | 506 | 13 | 10 | 59 | 1881 +-------+-------+-------+-------+-------+ 1882 | 48 | 589 | 13 | 10 | 61 | 1883 +-------+-------+-------+-------+-------+ 1884 | 49 | 87 | 13 | 10 | 61 | 1885 +-------+-------+-------+-------+-------+ 1886 | 55 | 520 | 13 | 10 | 67 | 1887 +-------+-------+-------+-------+-------+ 1888 | 60 | 159 | 13 | 10 | 71 | 1889 +-------+-------+-------+-------+-------+ 1890 | 62 | 235 | 13 | 10 | 73 | 1891 +-------+-------+-------+-------+-------+ 1892 | 69 | 157 | 13 | 10 | 79 | 1893 +-------+-------+-------+-------+-------+ 1894 | 75 | 502 | 17 | 10 | 89 | 1895 +-------+-------+-------+-------+-------+ 1896 | 84 | 334 | 17 | 10 | 97 | 1897 +-------+-------+-------+-------+-------+ 1898 | 88 | 583 | 17 | 10 | 101 | 1899 +-------+-------+-------+-------+-------+ 1900 | 91 | 66 | 17 | 10 | 103 | 1901 +-------+-------+-------+-------+-------+ 1902 | 95 | 352 | 17 | 10 | 107 | 1903 +-------+-------+-------+-------+-------+ 1904 | 97 | 365 | 17 | 10 | 109 | 1905 | 101 | 562 | 17 | 10 | 113 | 1906 +-------+-------+-------+-------+-------+ 1907 | 114 | 5 | 19 | 10 | 127 | 1908 +-------+-------+-------+-------+-------+ 1909 | 119 | 603 | 19 | 10 | 131 | 1910 +-------+-------+-------+-------+-------+ 1911 | 125 | 721 | 19 | 10 | 137 | 1912 +-------+-------+-------+-------+-------+ 1913 | 127 | 28 | 19 | 10 | 139 | 1914 +-------+-------+-------+-------+-------+ 1915 | 138 | 660 | 19 | 10 | 149 | 1916 +-------+-------+-------+-------+-------+ 1917 | 140 | 829 | 19 | 10 | 151 | 1918 +-------+-------+-------+-------+-------+ 1919 | 149 | 900 | 23 | 10 | 163 | 1920 +-------+-------+-------+-------+-------+ 1921 | 153 | 930 | 23 | 10 | 167 | 1922 +-------+-------+-------+-------+-------+ 1923 | 160 | 814 | 23 | 10 | 173 | 1924 +-------+-------+-------+-------+-------+ 1925 | 166 | 661 | 23 | 10 | 179 | 1926 +-------+-------+-------+-------+-------+ 1927 | 168 | 693 | 23 | 10 | 181 | 1928 +-------+-------+-------+-------+-------+ 1929 | 179 | 780 | 23 | 10 | 191 | 1930 +-------+-------+-------+-------+-------+ 1931 | 181 | 605 | 23 | 10 | 193 | 1932 +-------+-------+-------+-------+-------+ 1933 | 185 | 551 | 23 | 10 | 197 | 1934 +-------+-------+-------+-------+-------+ 1935 | 187 | 777 | 23 | 10 | 199 | 1936 +-------+-------+-------+-------+-------+ 1937 | 200 | 491 | 23 | 10 | 211 | 1938 +-------+-------+-------+-------+-------+ 1939 | 213 | 396 | 23 | 10 | 223 | 1940 +-------+-------+-------+-------+-------+ 1941 | 217 | 764 | 29 | 10 | 233 | 1942 +-------+-------+-------+-------+-------+ 1943 | 225 | 843 | 29 | 10 | 241 | 1944 +-------+-------+-------+-------+-------+ 1945 | 236 | 646 | 29 | 10 | 251 | 1946 +-------+-------+-------+-------+-------+ 1947 | 242 | 557 | 29 | 10 | 257 | 1948 +-------+-------+-------+-------+-------+ 1949 | 248 | 608 | 29 | 10 | 263 | 1950 +-------+-------+-------+-------+-------+ 1951 | 257 | 265 | 29 | 10 | 271 | 1952 +-------+-------+-------+-------+-------+ 1953 +-------+-------+-------+-------+-------+ 1954 | 263 | 505 | 29 | 10 | 277 | 1955 +-------+-------+-------+-------+-------+ 1956 | 269 | 722 | 29 | 10 | 283 | 1957 +-------+-------+-------+-------+-------+ 1958 | 280 | 263 | 29 | 10 | 293 | 1959 +-------+-------+-------+-------+-------+ 1960 | 295 | 999 | 29 | 10 | 307 | 1961 +-------+-------+-------+-------+-------+ 1962 | 301 | 874 | 29 | 10 | 313 | 1963 +-------+-------+-------+-------+-------+ 1964 | 305 | 160 | 29 | 10 | 317 | 1965 +-------+-------+-------+-------+-------+ 1966 | 324 | 575 | 31 | 10 | 337 | 1967 +-------+-------+-------+-------+-------+ 1968 | 337 | 210 | 31 | 10 | 349 | 1969 +-------+-------+-------+-------+-------+ 1970 | 341 | 513 | 31 | 10 | 353 | 1971 +-------+-------+-------+-------+-------+ 1972 | 347 | 503 | 31 | 10 | 359 | 1973 +-------+-------+-------+-------+-------+ 1974 | 355 | 558 | 31 | 10 | 367 | 1975 +-------+-------+-------+-------+-------+ 1976 | 362 | 932 | 31 | 10 | 373 | 1977 +-------+-------+-------+-------+-------+ 1978 | 368 | 404 | 31 | 10 | 379 | 1979 +-------+-------+-------+-------+-------+ 1980 | 372 | 520 | 37 | 10 | 389 | 1981 +-------+-------+-------+-------+-------+ 1982 | 380 | 846 | 37 | 10 | 397 | 1983 +-------+-------+-------+-------+-------+ 1984 | 385 | 485 | 37 | 10 | 401 | 1985 +-------+-------+-------+-------+-------+ 1986 | 393 | 728 | 37 | 10 | 409 | 1987 +-------+-------+-------+-------+-------+ 1988 | 405 | 554 | 37 | 10 | 421 | 1989 +-------+-------+-------+-------+-------+ 1990 | 418 | 471 | 37 | 10 | 433 | 1991 +-------+-------+-------+-------+-------+ 1992 | 428 | 641 | 37 | 10 | 443 | 1993 +-------+-------+-------+-------+-------+ 1994 | 434 | 732 | 37 | 10 | 449 | 1995 +-------+-------+-------+-------+-------+ 1996 | 447 | 193 | 37 | 10 | 461 | 1997 +-------+-------+-------+-------+-------+ 1998 | 453 | 934 | 37 | 10 | 467 | 1999 +-------+-------+-------+-------+-------+ 2000 | 466 | 864 | 37 | 10 | 479 | 2001 | 478 | 790 | 37 | 10 | 491 | 2002 +-------+-------+-------+-------+-------+ 2003 | 486 | 912 | 37 | 10 | 499 | 2004 +-------+-------+-------+-------+-------+ 2005 | 491 | 617 | 37 | 10 | 503 | 2006 +-------+-------+-------+-------+-------+ 2007 | 497 | 587 | 37 | 10 | 509 | 2008 +-------+-------+-------+-------+-------+ 2009 | 511 | 800 | 37 | 10 | 523 | 2010 +-------+-------+-------+-------+-------+ 2011 | 526 | 923 | 41 | 10 | 541 | 2012 +-------+-------+-------+-------+-------+ 2013 | 532 | 998 | 41 | 10 | 547 | 2014 +-------+-------+-------+-------+-------+ 2015 | 542 | 92 | 41 | 10 | 557 | 2016 +-------+-------+-------+-------+-------+ 2017 | 549 | 497 | 41 | 10 | 563 | 2018 +-------+-------+-------+-------+-------+ 2019 | 557 | 559 | 41 | 10 | 571 | 2020 +-------+-------+-------+-------+-------+ 2021 | 563 | 667 | 41 | 10 | 577 | 2022 +-------+-------+-------+-------+-------+ 2023 | 573 | 912 | 41 | 10 | 587 | 2024 +-------+-------+-------+-------+-------+ 2025 | 580 | 262 | 41 | 10 | 593 | 2026 +-------+-------+-------+-------+-------+ 2027 | 588 | 152 | 41 | 10 | 601 | 2028 +-------+-------+-------+-------+-------+ 2029 | 594 | 526 | 41 | 10 | 607 | 2030 +-------+-------+-------+-------+-------+ 2031 | 600 | 268 | 41 | 10 | 613 | 2032 +-------+-------+-------+-------+-------+ 2033 | 606 | 212 | 41 | 10 | 619 | 2034 +-------+-------+-------+-------+-------+ 2035 | 619 | 45 | 41 | 10 | 631 | 2036 +-------+-------+-------+-------+-------+ 2037 | 633 | 898 | 43 | 10 | 647 | 2038 +-------+-------+-------+-------+-------+ 2039 | 640 | 527 | 43 | 10 | 653 | 2040 +-------+-------+-------+-------+-------+ 2041 | 648 | 558 | 43 | 10 | 661 | 2042 +-------+-------+-------+-------+-------+ 2043 | 666 | 460 | 47 | 10 | 683 | 2044 +-------+-------+-------+-------+-------+ 2045 | 675 | 5 | 47 | 10 | 691 | 2046 +-------+-------+-------+-------+-------+ 2047 | 685 | 895 | 47 | 10 | 701 | 2048 +-------+-------+-------+-------+-------+ 2049 +-------+-------+-------+-------+-------+ 2050 | 693 | 996 | 47 | 10 | 709 | 2051 +-------+-------+-------+-------+-------+ 2052 | 703 | 282 | 47 | 10 | 719 | 2053 +-------+-------+-------+-------+-------+ 2054 | 718 | 513 | 47 | 10 | 733 | 2055 +-------+-------+-------+-------+-------+ 2056 | 728 | 865 | 47 | 10 | 743 | 2057 +-------+-------+-------+-------+-------+ 2058 | 736 | 870 | 47 | 10 | 751 | 2059 +-------+-------+-------+-------+-------+ 2060 | 747 | 239 | 47 | 10 | 761 | 2061 +-------+-------+-------+-------+-------+ 2062 | 759 | 452 | 47 | 10 | 773 | 2063 +-------+-------+-------+-------+-------+ 2064 | 778 | 862 | 53 | 10 | 797 | 2065 +-------+-------+-------+-------+-------+ 2066 | 792 | 852 | 53 | 10 | 811 | 2067 +-------+-------+-------+-------+-------+ 2068 | 802 | 643 | 53 | 10 | 821 | 2069 +-------+-------+-------+-------+-------+ 2070 | 811 | 543 | 53 | 10 | 829 | 2071 +-------+-------+-------+-------+-------+ 2072 | 821 | 447 | 53 | 10 | 839 | 2073 +-------+-------+-------+-------+-------+ 2074 | 835 | 321 | 53 | 10 | 853 | 2075 +-------+-------+-------+-------+-------+ 2076 | 845 | 287 | 53 | 10 | 863 | 2077 +-------+-------+-------+-------+-------+ 2078 | 860 | 12 | 53 | 10 | 877 | 2079 +-------+-------+-------+-------+-------+ 2080 | 870 | 251 | 53 | 10 | 887 | 2081 +-------+-------+-------+-------+-------+ 2082 | 891 | 30 | 53 | 10 | 907 | 2083 +-------+-------+-------+-------+-------+ 2084 | 903 | 621 | 53 | 10 | 919 | 2085 +-------+-------+-------+-------+-------+ 2086 | 913 | 555 | 53 | 10 | 929 | 2087 +-------+-------+-------+-------+-------+ 2088 | 926 | 127 | 53 | 10 | 941 | 2089 +-------+-------+-------+-------+-------+ 2090 | 938 | 400 | 53 | 10 | 953 | 2091 +-------+-------+-------+-------+-------+ 2092 | 950 | 91 | 59 | 10 | 971 | 2093 +-------+-------+-------+-------+-------+ 2094 | 963 | 916 | 59 | 10 | 983 | 2095 +-------+-------+-------+-------+-------+ 2096 | 977 | 935 | 59 | 10 | 997 | 2097 | 989 | 691 | 59 | 10 | 1009 | 2098 +-------+-------+-------+-------+-------+ 2099 | 1002 | 299 | 59 | 10 | 1021 | 2100 +-------+-------+-------+-------+-------+ 2101 | 1020 | 282 | 59 | 10 | 1039 | 2102 +-------+-------+-------+-------+-------+ 2103 | 1032 | 824 | 59 | 10 | 1051 | 2104 +-------+-------+-------+-------+-------+ 2105 | 1050 | 536 | 59 | 11 | 1069 | 2106 +-------+-------+-------+-------+-------+ 2107 | 1074 | 596 | 59 | 11 | 1093 | 2108 +-------+-------+-------+-------+-------+ 2109 | 1085 | 28 | 59 | 11 | 1103 | 2110 +-------+-------+-------+-------+-------+ 2111 | 1099 | 947 | 59 | 11 | 1117 | 2112 +-------+-------+-------+-------+-------+ 2113 | 1111 | 162 | 59 | 11 | 1129 | 2114 +-------+-------+-------+-------+-------+ 2115 | 1136 | 536 | 59 | 11 | 1153 | 2116 +-------+-------+-------+-------+-------+ 2117 | 1152 | 1000 | 61 | 11 | 1171 | 2118 +-------+-------+-------+-------+-------+ 2119 | 1169 | 251 | 61 | 11 | 1187 | 2120 +-------+-------+-------+-------+-------+ 2121 | 1183 | 673 | 61 | 11 | 1201 | 2122 +-------+-------+-------+-------+-------+ 2123 | 1205 | 559 | 61 | 11 | 1223 | 2124 +-------+-------+-------+-------+-------+ 2125 | 1220 | 923 | 61 | 11 | 1237 | 2126 +-------+-------+-------+-------+-------+ 2127 | 1236 | 81 | 67 | 11 | 1259 | 2128 +-------+-------+-------+-------+-------+ 2129 | 1255 | 478 | 67 | 11 | 1277 | 2130 +-------+-------+-------+-------+-------+ 2131 | 1269 | 198 | 67 | 11 | 1291 | 2132 +-------+-------+-------+-------+-------+ 2133 | 1285 | 137 | 67 | 11 | 1307 | 2134 +-------+-------+-------+-------+-------+ 2135 | 1306 | 75 | 67 | 11 | 1327 | 2136 +-------+-------+-------+-------+-------+ 2137 | 1347 | 29 | 67 | 11 | 1367 | 2138 +-------+-------+-------+-------+-------+ 2139 | 1361 | 231 | 67 | 11 | 1381 | 2140 +-------+-------+-------+-------+-------+ 2141 | 1389 | 532 | 67 | 11 | 1409 | 2142 +-------+-------+-------+-------+-------+ 2143 | 1404 | 58 | 67 | 11 | 1423 | 2144 +-------+-------+-------+-------+-------+ 2145 +-------+-------+-------+-------+-------+ 2146 | 1420 | 60 | 67 | 11 | 1439 | 2147 +-------+-------+-------+-------+-------+ 2148 | 1436 | 964 | 71 | 11 | 1459 | 2149 +-------+-------+-------+-------+-------+ 2150 | 1461 | 624 | 71 | 11 | 1483 | 2151 +-------+-------+-------+-------+-------+ 2152 | 1477 | 502 | 71 | 11 | 1499 | 2153 +-------+-------+-------+-------+-------+ 2154 | 1502 | 636 | 71 | 11 | 1523 | 2155 +-------+-------+-------+-------+-------+ 2156 | 1522 | 986 | 71 | 11 | 1543 | 2157 +-------+-------+-------+-------+-------+ 2158 | 1539 | 950 | 71 | 11 | 1559 | 2159 +-------+-------+-------+-------+-------+ 2160 | 1561 | 735 | 73 | 11 | 1583 | 2161 +-------+-------+-------+-------+-------+ 2162 | 1579 | 866 | 73 | 11 | 1601 | 2163 +-------+-------+-------+-------+-------+ 2164 | 1600 | 203 | 73 | 11 | 1621 | 2165 +-------+-------+-------+-------+-------+ 2166 | 1616 | 83 | 73 | 11 | 1637 | 2167 +-------+-------+-------+-------+-------+ 2168 | 1649 | 14 | 73 | 11 | 1669 | 2169 +-------+-------+-------+-------+-------+ 2170 | 1673 | 522 | 79 | 11 | 1699 | 2171 +-------+-------+-------+-------+-------+ 2172 | 1698 | 226 | 79 | 11 | 1723 | 2173 +-------+-------+-------+-------+-------+ 2174 | 1716 | 282 | 79 | 11 | 1741 | 2175 +-------+-------+-------+-------+-------+ 2176 | 1734 | 88 | 79 | 11 | 1759 | 2177 +-------+-------+-------+-------+-------+ 2178 | 1759 | 636 | 79 | 11 | 1783 | 2179 +-------+-------+-------+-------+-------+ 2180 | 1777 | 860 | 79 | 11 | 1801 | 2181 +-------+-------+-------+-------+-------+ 2182 | 1800 | 324 | 79 | 11 | 1823 | 2183 +-------+-------+-------+-------+-------+ 2184 | 1824 | 424 | 79 | 11 | 1847 | 2185 +-------+-------+-------+-------+-------+ 2186 | 1844 | 999 | 79 | 11 | 1867 | 2187 +-------+-------+-------+-------+-------+ 2188 | 1863 | 682 | 83 | 11 | 1889 | 2189 +-------+-------+-------+-------+-------+ 2190 | 1887 | 814 | 83 | 11 | 1913 | 2191 +-------+-------+-------+-------+-------+ 2192 | 1906 | 979 | 83 | 11 | 1931 | 2193 | 1926 | 538 | 83 | 11 | 1951 | 2194 +-------+-------+-------+-------+-------+ 2195 | 1954 | 278 | 83 | 11 | 1979 | 2196 +-------+-------+-------+-------+-------+ 2197 | 1979 | 580 | 83 | 11 | 2003 | 2198 +-------+-------+-------+-------+-------+ 2199 | 2005 | 773 | 83 | 11 | 2029 | 2200 +-------+-------+-------+-------+-------+ 2201 | 2040 | 911 | 89 | 11 | 2069 | 2202 +-------+-------+-------+-------+-------+ 2203 | 2070 | 506 | 89 | 11 | 2099 | 2204 +-------+-------+-------+-------+-------+ 2205 | 2103 | 628 | 89 | 11 | 2131 | 2206 +-------+-------+-------+-------+-------+ 2207 | 2125 | 282 | 89 | 11 | 2153 | 2208 +-------+-------+-------+-------+-------+ 2209 | 2152 | 309 | 89 | 11 | 2179 | 2210 +-------+-------+-------+-------+-------+ 2211 | 2195 | 858 | 89 | 11 | 2221 | 2212 +-------+-------+-------+-------+-------+ 2213 | 2217 | 442 | 89 | 11 | 2243 | 2214 +-------+-------+-------+-------+-------+ 2215 | 2247 | 654 | 89 | 11 | 2273 | 2216 +-------+-------+-------+-------+-------+ 2217 | 2278 | 82 | 97 | 11 | 2311 | 2218 +-------+-------+-------+-------+-------+ 2219 | 2315 | 428 | 97 | 11 | 2347 | 2220 +-------+-------+-------+-------+-------+ 2221 | 2339 | 442 | 97 | 11 | 2371 | 2222 +-------+-------+-------+-------+-------+ 2223 | 2367 | 283 | 97 | 11 | 2399 | 2224 +-------+-------+-------+-------+-------+ 2225 | 2392 | 538 | 97 | 11 | 2423 | 2226 +-------+-------+-------+-------+-------+ 2227 | 2416 | 189 | 97 | 11 | 2447 | 2228 +-------+-------+-------+-------+-------+ 2229 | 2447 | 438 | 97 | 11 | 2477 | 2230 +-------+-------+-------+-------+-------+ 2231 | 2473 | 912 | 97 | 11 | 2503 | 2232 +-------+-------+-------+-------+-------+ 2233 | 2502 | 1 | 97 | 11 | 2531 | 2234 +-------+-------+-------+-------+-------+ 2235 | 2528 | 167 | 97 | 11 | 2557 | 2236 +-------+-------+-------+-------+-------+ 2237 | 2565 | 272 | 97 | 11 | 2593 | 2238 +-------+-------+-------+-------+-------+ 2239 | 2601 | 209 | 101 | 11 | 2633 | 2240 +-------+-------+-------+-------+-------+ 2241 +-------+-------+-------+-------+-------+ 2242 | 2640 | 927 | 101 | 11 | 2671 | 2243 +-------+-------+-------+-------+-------+ 2244 | 2668 | 386 | 101 | 11 | 2699 | 2245 +-------+-------+-------+-------+-------+ 2246 | 2701 | 653 | 101 | 11 | 2731 | 2247 +-------+-------+-------+-------+-------+ 2248 | 2737 | 669 | 101 | 11 | 2767 | 2249 +-------+-------+-------+-------+-------+ 2250 | 2772 | 431 | 101 | 11 | 2801 | 2251 +-------+-------+-------+-------+-------+ 2252 | 2802 | 793 | 103 | 11 | 2833 | 2253 +-------+-------+-------+-------+-------+ 2254 | 2831 | 588 | 103 | 11 | 2861 | 2255 +-------+-------+-------+-------+-------+ 2256 | 2875 | 777 | 107 | 11 | 2909 | 2257 +-------+-------+-------+-------+-------+ 2258 | 2906 | 939 | 107 | 11 | 2939 | 2259 +-------+-------+-------+-------+-------+ 2260 | 2938 | 864 | 107 | 11 | 2971 | 2261 +-------+-------+-------+-------+-------+ 2262 | 2979 | 627 | 107 | 11 | 3011 | 2263 +-------+-------+-------+-------+-------+ 2264 | 3015 | 265 | 109 | 11 | 3049 | 2265 +-------+-------+-------+-------+-------+ 2266 | 3056 | 976 | 109 | 11 | 3089 | 2267 +-------+-------+-------+-------+-------+ 2268 | 3101 | 988 | 113 | 11 | 3137 | 2269 +-------+-------+-------+-------+-------+ 2270 | 3151 | 507 | 113 | 11 | 3187 | 2271 +-------+-------+-------+-------+-------+ 2272 | 3186 | 640 | 113 | 11 | 3221 | 2273 +-------+-------+-------+-------+-------+ 2274 | 3224 | 15 | 113 | 11 | 3259 | 2275 +-------+-------+-------+-------+-------+ 2276 | 3265 | 667 | 113 | 11 | 3299 | 2277 +-------+-------+-------+-------+-------+ 2278 | 3299 | 24 | 127 | 11 | 3347 | 2279 +-------+-------+-------+-------+-------+ 2280 | 3344 | 877 | 127 | 11 | 3391 | 2281 +-------+-------+-------+-------+-------+ 2282 | 3387 | 240 | 127 | 11 | 3433 | 2283 +-------+-------+-------+-------+-------+ 2284 | 3423 | 720 | 127 | 11 | 3469 | 2285 +-------+-------+-------+-------+-------+ 2286 | 3466 | 93 | 127 | 11 | 3511 | 2287 +-------+-------+-------+-------+-------+ 2288 | 3502 | 919 | 127 | 11 | 3547 | 2289 | 3539 | 635 | 127 | 11 | 3583 | 2290 +-------+-------+-------+-------+-------+ 2291 | 3579 | 174 | 127 | 11 | 3623 | 2292 +-------+-------+-------+-------+-------+ 2293 | 3616 | 647 | 127 | 11 | 3659 | 2294 +-------+-------+-------+-------+-------+ 2295 | 3658 | 820 | 127 | 11 | 3701 | 2296 +-------+-------+-------+-------+-------+ 2297 | 3697 | 56 | 127 | 11 | 3739 | 2298 +-------+-------+-------+-------+-------+ 2299 | 3751 | 485 | 127 | 11 | 3793 | 2300 +-------+-------+-------+-------+-------+ 2301 | 3792 | 210 | 127 | 11 | 3833 | 2302 +-------+-------+-------+-------+-------+ 2303 | 3840 | 124 | 127 | 11 | 3881 | 2304 +-------+-------+-------+-------+-------+ 2305 | 3883 | 546 | 127 | 11 | 3923 | 2306 +-------+-------+-------+-------+-------+ 2307 | 3924 | 954 | 131 | 11 | 3967 | 2308 +-------+-------+-------+-------+-------+ 2309 | 3970 | 262 | 131 | 11 | 4013 | 2310 +-------+-------+-------+-------+-------+ 2311 | 4015 | 927 | 131 | 11 | 4057 | 2312 +-------+-------+-------+-------+-------+ 2313 | 4069 | 957 | 131 | 11 | 4111 | 2314 +-------+-------+-------+-------+-------+ 2315 | 4112 | 726 | 137 | 11 | 4159 | 2316 +-------+-------+-------+-------+-------+ 2317 | 4165 | 583 | 137 | 11 | 4211 | 2318 +-------+-------+-------+-------+-------+ 2319 | 4207 | 782 | 137 | 11 | 4253 | 2320 +-------+-------+-------+-------+-------+ 2321 | 4252 | 37 | 137 | 11 | 4297 | 2322 +-------+-------+-------+-------+-------+ 2323 | 4318 | 758 | 137 | 11 | 4363 | 2324 +-------+-------+-------+-------+-------+ 2325 | 4365 | 777 | 137 | 11 | 4409 | 2326 +-------+-------+-------+-------+-------+ 2327 | 4418 | 104 | 139 | 11 | 4463 | 2328 +-------+-------+-------+-------+-------+ 2329 | 4468 | 476 | 139 | 11 | 4513 | 2330 +-------+-------+-------+-------+-------+ 2331 | 4513 | 113 | 149 | 11 | 4567 | 2332 +-------+-------+-------+-------+-------+ 2333 | 4567 | 313 | 149 | 11 | 4621 | 2334 +-------+-------+-------+-------+-------+ 2335 | 4626 | 102 | 149 | 11 | 4679 | 2336 +-------+-------+-------+-------+-------+ 2337 +-------+-------+-------+-------+-------+ 2338 | 4681 | 501 | 149 | 11 | 4733 | 2339 +-------+-------+-------+-------+-------+ 2340 | 4731 | 332 | 149 | 11 | 4783 | 2341 +-------+-------+-------+-------+-------+ 2342 | 4780 | 786 | 149 | 11 | 4831 | 2343 +-------+-------+-------+-------+-------+ 2344 | 4838 | 99 | 149 | 11 | 4889 | 2345 +-------+-------+-------+-------+-------+ 2346 | 4901 | 658 | 149 | 11 | 4951 | 2347 +-------+-------+-------+-------+-------+ 2348 | 4954 | 794 | 149 | 11 | 5003 | 2349 +-------+-------+-------+-------+-------+ 2350 | 5008 | 37 | 151 | 11 | 5059 | 2351 +-------+-------+-------+-------+-------+ 2352 | 5063 | 471 | 151 | 11 | 5113 | 2353 +-------+-------+-------+-------+-------+ 2354 | 5116 | 94 | 157 | 11 | 5171 | 2355 +-------+-------+-------+-------+-------+ 2356 | 5172 | 873 | 157 | 11 | 5227 | 2357 +-------+-------+-------+-------+-------+ 2358 | 5225 | 918 | 157 | 11 | 5279 | 2359 +-------+-------+-------+-------+-------+ 2360 | 5279 | 945 | 157 | 11 | 5333 | 2361 +-------+-------+-------+-------+-------+ 2362 | 5334 | 211 | 157 | 11 | 5387 | 2363 +-------+-------+-------+-------+-------+ 2364 | 5391 | 341 | 157 | 11 | 5443 | 2365 +-------+-------+-------+-------+-------+ 2366 | 5449 | 11 | 163 | 11 | 5507 | 2367 +-------+-------+-------+-------+-------+ 2368 | 5506 | 578 | 163 | 11 | 5563 | 2369 +-------+-------+-------+-------+-------+ 2370 | 5566 | 494 | 163 | 11 | 5623 | 2371 +-------+-------+-------+-------+-------+ 2372 | 5637 | 694 | 163 | 11 | 5693 | 2373 +-------+-------+-------+-------+-------+ 2374 | 5694 | 252 | 163 | 11 | 5749 | 2375 +-------+-------+-------+-------+-------+ 2376 | 5763 | 451 | 167 | 11 | 5821 | 2377 +-------+-------+-------+-------+-------+ 2378 | 5823 | 83 | 167 | 11 | 5881 | 2379 +-------+-------+-------+-------+-------+ 2380 | 5896 | 689 | 167 | 11 | 5953 | 2381 +-------+-------+-------+-------+-------+ 2382 | 5975 | 488 | 173 | 11 | 6037 | 2383 +-------+-------+-------+-------+-------+ 2384 | 6039 | 214 | 173 | 11 | 6101 | 2385 | 6102 | 17 | 173 | 11 | 6163 | 2386 +-------+-------+-------+-------+-------+ 2387 | 6169 | 469 | 173 | 11 | 6229 | 2388 +-------+-------+-------+-------+-------+ 2389 | 6233 | 263 | 179 | 11 | 6299 | 2390 +-------+-------+-------+-------+-------+ 2391 | 6296 | 309 | 179 | 11 | 6361 | 2392 +-------+-------+-------+-------+-------+ 2393 | 6363 | 984 | 179 | 11 | 6427 | 2394 +-------+-------+-------+-------+-------+ 2395 | 6427 | 123 | 179 | 11 | 6491 | 2396 +-------+-------+-------+-------+-------+ 2397 | 6518 | 360 | 179 | 11 | 6581 | 2398 +-------+-------+-------+-------+-------+ 2399 | 6589 | 863 | 181 | 11 | 6653 | 2400 +-------+-------+-------+-------+-------+ 2401 | 6655 | 122 | 181 | 11 | 6719 | 2402 +-------+-------+-------+-------+-------+ 2403 | 6730 | 522 | 191 | 11 | 6803 | 2404 +-------+-------+-------+-------+-------+ 2405 | 6799 | 539 | 191 | 11 | 6871 | 2406 +-------+-------+-------+-------+-------+ 2407 | 6878 | 181 | 191 | 11 | 6949 | 2408 +-------+-------+-------+-------+-------+ 2409 | 6956 | 64 | 191 | 11 | 7027 | 2410 +-------+-------+-------+-------+-------+ 2411 | 7033 | 387 | 191 | 11 | 7103 | 2412 +-------+-------+-------+-------+-------+ 2413 | 7108 | 967 | 191 | 11 | 7177 | 2414 +-------+-------+-------+-------+-------+ 2415 | 7185 | 843 | 191 | 11 | 7253 | 2416 +-------+-------+-------+-------+-------+ 2417 | 7281 | 999 | 193 | 11 | 7351 | 2418 +-------+-------+-------+-------+-------+ 2419 | 7360 | 76 | 197 | 11 | 7433 | 2420 +-------+-------+-------+-------+-------+ 2421 | 7445 | 142 | 197 | 11 | 7517 | 2422 +-------+-------+-------+-------+-------+ 2423 | 7520 | 599 | 197 | 11 | 7591 | 2424 +-------+-------+-------+-------+-------+ 2425 | 7596 | 576 | 199 | 11 | 7669 | 2426 +-------+-------+-------+-------+-------+ 2427 | 7675 | 176 | 211 | 11 | 7759 | 2428 +-------+-------+-------+-------+-------+ 2429 | 7770 | 392 | 211 | 11 | 7853 | 2430 +-------+-------+-------+-------+-------+ 2431 | 7855 | 332 | 211 | 11 | 7937 | 2432 +-------+-------+-------+-------+-------+ 2433 +-------+-------+-------+-------+-------+ 2434 | 7935 | 291 | 211 | 11 | 8017 | 2435 +-------+-------+-------+-------+-------+ 2436 | 8030 | 913 | 211 | 11 | 8111 | 2437 +-------+-------+-------+-------+-------+ 2438 | 8111 | 608 | 211 | 11 | 8191 | 2439 +-------+-------+-------+-------+-------+ 2440 | 8194 | 212 | 211 | 11 | 8273 | 2441 +-------+-------+-------+-------+-------+ 2442 | 8290 | 696 | 211 | 11 | 8369 | 2443 +-------+-------+-------+-------+-------+ 2444 | 8377 | 931 | 223 | 11 | 8467 | 2445 +-------+-------+-------+-------+-------+ 2446 | 8474 | 326 | 223 | 11 | 8563 | 2447 +-------+-------+-------+-------+-------+ 2448 | 8559 | 228 | 223 | 11 | 8647 | 2449 +-------+-------+-------+-------+-------+ 2450 | 8654 | 706 | 223 | 11 | 8741 | 2451 +-------+-------+-------+-------+-------+ 2452 | 8744 | 144 | 223 | 11 | 8831 | 2453 +-------+-------+-------+-------+-------+ 2454 | 8837 | 83 | 223 | 11 | 8923 | 2455 +-------+-------+-------+-------+-------+ 2456 | 8928 | 743 | 223 | 11 | 9013 | 2457 +-------+-------+-------+-------+-------+ 2458 | 9019 | 187 | 223 | 11 | 9103 | 2459 +-------+-------+-------+-------+-------+ 2460 | 9111 | 654 | 227 | 11 | 9199 | 2461 +-------+-------+-------+-------+-------+ 2462 | 9206 | 359 | 227 | 11 | 9293 | 2463 +-------+-------+-------+-------+-------+ 2464 | 9303 | 493 | 229 | 11 | 9391 | 2465 +-------+-------+-------+-------+-------+ 2466 | 9400 | 369 | 233 | 11 | 9491 | 2467 +-------+-------+-------+-------+-------+ 2468 | 9497 | 981 | 233 | 11 | 9587 | 2469 +-------+-------+-------+-------+-------+ 2470 | 9601 | 276 | 239 | 11 | 9697 | 2471 +-------+-------+-------+-------+-------+ 2472 | 9708 | 647 | 239 | 11 | 9803 | 2473 +-------+-------+-------+-------+-------+ 2474 | 9813 | 389 | 239 | 11 | 9907 | 2475 +-------+-------+-------+-------+-------+ 2476 | 9916 | 80 | 239 | 11 | 10009 | 2477 +-------+-------+-------+-------+-------+ 2478 | 10017 | 396 | 241 | 11 | 10111 | 2479 +-------+-------+-------+-------+-------+ 2480 | 10120 | 580 | 251 | 11 | 10223 | 2481 | 10241 | 873 | 251 | 11 | 10343 | 2482 +-------+-------+-------+-------+-------+ 2483 | 10351 | 15 | 251 | 11 | 10453 | 2484 +-------+-------+-------+-------+-------+ 2485 | 10458 | 976 | 251 | 11 | 10559 | 2486 +-------+-------+-------+-------+-------+ 2487 | 10567 | 584 | 251 | 11 | 10667 | 2488 +-------+-------+-------+-------+-------+ 2489 | 10676 | 267 | 257 | 11 | 10781 | 2490 +-------+-------+-------+-------+-------+ 2491 | 10787 | 876 | 257 | 11 | 10891 | 2492 +-------+-------+-------+-------+-------+ 2493 | 10899 | 642 | 257 | 12 | 11003 | 2494 +-------+-------+-------+-------+-------+ 2495 | 11015 | 794 | 257 | 12 | 11119 | 2496 +-------+-------+-------+-------+-------+ 2497 | 11130 | 78 | 263 | 12 | 11239 | 2498 +-------+-------+-------+-------+-------+ 2499 | 11245 | 736 | 263 | 12 | 11353 | 2500 +-------+-------+-------+-------+-------+ 2501 | 11358 | 882 | 269 | 12 | 11471 | 2502 +-------+-------+-------+-------+-------+ 2503 | 11475 | 251 | 269 | 12 | 11587 | 2504 +-------+-------+-------+-------+-------+ 2505 | 11590 | 434 | 269 | 12 | 11701 | 2506 +-------+-------+-------+-------+-------+ 2507 | 11711 | 204 | 269 | 12 | 11821 | 2508 +-------+-------+-------+-------+-------+ 2509 | 11829 | 256 | 271 | 12 | 11941 | 2510 +-------+-------+-------+-------+-------+ 2511 | 11956 | 106 | 277 | 12 | 12073 | 2512 +-------+-------+-------+-------+-------+ 2513 | 12087 | 375 | 277 | 12 | 12203 | 2514 +-------+-------+-------+-------+-------+ 2515 | 12208 | 148 | 277 | 12 | 12323 | 2516 +-------+-------+-------+-------+-------+ 2517 | 12333 | 496 | 281 | 12 | 12451 | 2518 +-------+-------+-------+-------+-------+ 2519 | 12460 | 88 | 281 | 12 | 12577 | 2520 +-------+-------+-------+-------+-------+ 2521 | 12593 | 826 | 293 | 12 | 12721 | 2522 +-------+-------+-------+-------+-------+ 2523 | 12726 | 71 | 293 | 12 | 12853 | 2524 +-------+-------+-------+-------+-------+ 2525 | 12857 | 925 | 293 | 12 | 12983 | 2526 +-------+-------+-------+-------+-------+ 2527 | 13002 | 760 | 293 | 12 | 13127 | 2528 +-------+-------+-------+-------+-------+ 2529 +-------+-------+-------+-------+-------+ 2530 | 13143 | 130 | 293 | 12 | 13267 | 2531 +-------+-------+-------+-------+-------+ 2532 | 13284 | 641 | 307 | 12 | 13421 | 2533 +-------+-------+-------+-------+-------+ 2534 | 13417 | 400 | 307 | 12 | 13553 | 2535 +-------+-------+-------+-------+-------+ 2536 | 13558 | 480 | 307 | 12 | 13693 | 2537 +-------+-------+-------+-------+-------+ 2538 | 13695 | 76 | 307 | 12 | 13829 | 2539 +-------+-------+-------+-------+-------+ 2540 | 13833 | 665 | 307 | 12 | 13967 | 2541 +-------+-------+-------+-------+-------+ 2542 | 13974 | 910 | 307 | 12 | 14107 | 2543 +-------+-------+-------+-------+-------+ 2544 | 14115 | 467 | 311 | 12 | 14251 | 2545 +-------+-------+-------+-------+-------+ 2546 | 14272 | 964 | 311 | 12 | 14407 | 2547 +-------+-------+-------+-------+-------+ 2548 | 14415 | 625 | 313 | 12 | 14551 | 2549 +-------+-------+-------+-------+-------+ 2550 | 14560 | 362 | 317 | 12 | 14699 | 2551 +-------+-------+-------+-------+-------+ 2552 | 14713 | 759 | 317 | 12 | 14851 | 2553 +-------+-------+-------+-------+-------+ 2554 | 14862 | 728 | 331 | 12 | 15013 | 2555 +-------+-------+-------+-------+-------+ 2556 | 15011 | 343 | 331 | 12 | 15161 | 2557 +-------+-------+-------+-------+-------+ 2558 | 15170 | 113 | 331 | 12 | 15319 | 2559 +-------+-------+-------+-------+-------+ 2560 | 15325 | 137 | 331 | 12 | 15473 | 2561 +-------+-------+-------+-------+-------+ 2562 | 15496 | 308 | 331 | 12 | 15643 | 2563 +-------+-------+-------+-------+-------+ 2564 | 15651 | 800 | 337 | 12 | 15803 | 2565 +-------+-------+-------+-------+-------+ 2566 | 15808 | 177 | 337 | 12 | 15959 | 2567 +-------+-------+-------+-------+-------+ 2568 | 15977 | 961 | 337 | 12 | 16127 | 2569 +-------+-------+-------+-------+-------+ 2570 | 16161 | 958 | 347 | 12 | 16319 | 2571 +-------+-------+-------+-------+-------+ 2572 | 16336 | 72 | 347 | 12 | 16493 | 2573 +-------+-------+-------+-------+-------+ 2574 | 16505 | 732 | 347 | 12 | 16661 | 2575 +-------+-------+-------+-------+-------+ 2576 | 16674 | 145 | 349 | 12 | 16831 | 2577 | 16851 | 577 | 353 | 12 | 17011 | 2578 +-------+-------+-------+-------+-------+ 2579 | 17024 | 305 | 353 | 12 | 17183 | 2580 +-------+-------+-------+-------+-------+ 2581 | 17195 | 50 | 359 | 12 | 17359 | 2582 +-------+-------+-------+-------+-------+ 2583 | 17376 | 351 | 359 | 12 | 17539 | 2584 +-------+-------+-------+-------+-------+ 2585 | 17559 | 175 | 367 | 12 | 17729 | 2586 +-------+-------+-------+-------+-------+ 2587 | 17742 | 727 | 367 | 12 | 17911 | 2588 +-------+-------+-------+-------+-------+ 2589 | 17929 | 902 | 367 | 12 | 18097 | 2590 +-------+-------+-------+-------+-------+ 2591 | 18116 | 409 | 373 | 12 | 18289 | 2592 +-------+-------+-------+-------+-------+ 2593 | 18309 | 776 | 373 | 12 | 18481 | 2594 +-------+-------+-------+-------+-------+ 2595 | 18503 | 586 | 379 | 12 | 18679 | 2596 +-------+-------+-------+-------+-------+ 2597 | 18694 | 451 | 379 | 12 | 18869 | 2598 +-------+-------+-------+-------+-------+ 2599 | 18909 | 287 | 383 | 12 | 19087 | 2600 +-------+-------+-------+-------+-------+ 2601 | 19126 | 246 | 389 | 12 | 19309 | 2602 +-------+-------+-------+-------+-------+ 2603 | 19325 | 222 | 389 | 12 | 19507 | 2604 +-------+-------+-------+-------+-------+ 2605 | 19539 | 563 | 397 | 12 | 19727 | 2606 +-------+-------+-------+-------+-------+ 2607 | 19740 | 839 | 397 | 12 | 19927 | 2608 +-------+-------+-------+-------+-------+ 2609 | 19939 | 897 | 401 | 12 | 20129 | 2610 +-------+-------+-------+-------+-------+ 2611 | 20152 | 409 | 401 | 12 | 20341 | 2612 +-------+-------+-------+-------+-------+ 2613 | 20355 | 618 | 409 | 12 | 20551 | 2614 +-------+-------+-------+-------+-------+ 2615 | 20564 | 439 | 409 | 12 | 20759 | 2616 +-------+-------+-------+-------+-------+ 2617 | 20778 | 95 | 419 | 13 | 20983 | 2618 +-------+-------+-------+-------+-------+ 2619 | 20988 | 448 | 419 | 13 | 21191 | 2620 +-------+-------+-------+-------+-------+ 2621 | 21199 | 133 | 419 | 13 | 21401 | 2622 +-------+-------+-------+-------+-------+ 2623 | 21412 | 938 | 419 | 13 | 21613 | 2624 +-------+-------+-------+-------+-------+ 2625 +-------+-------+-------+-------+-------+ 2626 | 21629 | 423 | 431 | 13 | 21841 | 2627 +-------+-------+-------+-------+-------+ 2628 | 21852 | 90 | 431 | 13 | 22063 | 2629 +-------+-------+-------+-------+-------+ 2630 | 22073 | 640 | 431 | 13 | 22283 | 2631 +-------+-------+-------+-------+-------+ 2632 | 22301 | 922 | 433 | 13 | 22511 | 2633 +-------+-------+-------+-------+-------+ 2634 | 22536 | 250 | 439 | 13 | 22751 | 2635 +-------+-------+-------+-------+-------+ 2636 | 22779 | 367 | 439 | 13 | 22993 | 2637 +-------+-------+-------+-------+-------+ 2638 | 23010 | 447 | 443 | 13 | 23227 | 2639 +-------+-------+-------+-------+-------+ 2640 | 23252 | 559 | 449 | 13 | 23473 | 2641 +-------+-------+-------+-------+-------+ 2642 | 23491 | 121 | 457 | 13 | 23719 | 2643 +-------+-------+-------+-------+-------+ 2644 | 23730 | 623 | 457 | 13 | 23957 | 2645 +-------+-------+-------+-------+-------+ 2646 | 23971 | 450 | 457 | 13 | 24197 | 2647 +-------+-------+-------+-------+-------+ 2648 | 24215 | 253 | 461 | 13 | 24443 | 2649 +-------+-------+-------+-------+-------+ 2650 | 24476 | 106 | 467 | 13 | 24709 | 2651 +-------+-------+-------+-------+-------+ 2652 | 24721 | 863 | 467 | 13 | 24953 | 2653 +-------+-------+-------+-------+-------+ 2654 | 24976 | 148 | 479 | 13 | 25219 | 2655 +-------+-------+-------+-------+-------+ 2656 | 25230 | 427 | 479 | 13 | 25471 | 2657 +-------+-------+-------+-------+-------+ 2658 | 25493 | 138 | 479 | 13 | 25733 | 2659 +-------+-------+-------+-------+-------+ 2660 | 25756 | 794 | 487 | 13 | 26003 | 2661 +-------+-------+-------+-------+-------+ 2662 | 26022 | 247 | 487 | 13 | 26267 | 2663 +-------+-------+-------+-------+-------+ 2664 | 26291 | 562 | 491 | 13 | 26539 | 2665 +-------+-------+-------+-------+-------+ 2666 | 26566 | 53 | 499 | 13 | 26821 | 2667 +-------+-------+-------+-------+-------+ 2668 | 26838 | 135 | 499 | 13 | 27091 | 2669 +-------+-------+-------+-------+-------+ 2670 | 27111 | 21 | 503 | 13 | 27367 | 2671 +-------+-------+-------+-------+-------+ 2672 | 27392 | 201 | 509 | 13 | 27653 | 2673 | 27682 | 169 | 521 | 13 | 27953 | 2674 +-------+-------+-------+-------+-------+ 2675 | 27959 | 70 | 521 | 13 | 28229 | 2676 +-------+-------+-------+-------+-------+ 2677 | 28248 | 386 | 521 | 13 | 28517 | 2678 +-------+-------+-------+-------+-------+ 2679 | 28548 | 226 | 523 | 13 | 28817 | 2680 +-------+-------+-------+-------+-------+ 2681 | 28845 | 3 | 541 | 13 | 29131 | 2682 +-------+-------+-------+-------+-------+ 2683 | 29138 | 769 | 541 | 13 | 29423 | 2684 +-------+-------+-------+-------+-------+ 2685 | 29434 | 590 | 541 | 13 | 29717 | 2686 +-------+-------+-------+-------+-------+ 2687 | 29731 | 672 | 541 | 13 | 30013 | 2688 +-------+-------+-------+-------+-------+ 2689 | 30037 | 713 | 547 | 13 | 30323 | 2690 +-------+-------+-------+-------+-------+ 2691 | 30346 | 967 | 547 | 13 | 30631 | 2692 +-------+-------+-------+-------+-------+ 2693 | 30654 | 368 | 557 | 14 | 30949 | 2694 +-------+-------+-------+-------+-------+ 2695 | 30974 | 348 | 557 | 14 | 31267 | 2696 +-------+-------+-------+-------+-------+ 2697 | 31285 | 119 | 563 | 14 | 31583 | 2698 +-------+-------+-------+-------+-------+ 2699 | 31605 | 503 | 569 | 14 | 31907 | 2700 +-------+-------+-------+-------+-------+ 2701 | 31948 | 181 | 571 | 14 | 32251 | 2702 +-------+-------+-------+-------+-------+ 2703 | 32272 | 394 | 577 | 14 | 32579 | 2704 +-------+-------+-------+-------+-------+ 2705 | 32601 | 189 | 587 | 14 | 32917 | 2706 +-------+-------+-------+-------+-------+ 2707 | 32932 | 210 | 587 | 14 | 33247 | 2708 +-------+-------+-------+-------+-------+ 2709 | 33282 | 62 | 593 | 14 | 33601 | 2710 +-------+-------+-------+-------+-------+ 2711 | 33623 | 273 | 593 | 14 | 33941 | 2712 +-------+-------+-------+-------+-------+ 2713 | 33961 | 554 | 599 | 14 | 34283 | 2714 +-------+-------+-------+-------+-------+ 2715 | 34302 | 936 | 607 | 14 | 34631 | 2716 +-------+-------+-------+-------+-------+ 2717 | 34654 | 483 | 607 | 14 | 34981 | 2718 +-------+-------+-------+-------+-------+ 2719 | 35031 | 397 | 613 | 14 | 35363 | 2720 +-------+-------+-------+-------+-------+ 2721 +-------+-------+-------+-------+-------+ 2722 | 35395 | 241 | 619 | 14 | 35731 | 2723 +-------+-------+-------+-------+-------+ 2724 | 35750 | 500 | 631 | 14 | 36097 | 2725 +-------+-------+-------+-------+-------+ 2726 | 36112 | 12 | 631 | 14 | 36457 | 2727 +-------+-------+-------+-------+-------+ 2728 | 36479 | 958 | 641 | 14 | 36833 | 2729 +-------+-------+-------+-------+-------+ 2730 | 36849 | 524 | 641 | 14 | 37201 | 2731 +-------+-------+-------+-------+-------+ 2732 | 37227 | 8 | 643 | 14 | 37579 | 2733 +-------+-------+-------+-------+-------+ 2734 | 37606 | 100 | 653 | 14 | 37967 | 2735 +-------+-------+-------+-------+-------+ 2736 | 37992 | 339 | 653 | 14 | 38351 | 2737 +-------+-------+-------+-------+-------+ 2738 | 38385 | 804 | 659 | 14 | 38749 | 2739 +-------+-------+-------+-------+-------+ 2740 | 38787 | 510 | 673 | 14 | 39163 | 2741 +-------+-------+-------+-------+-------+ 2742 | 39176 | 18 | 673 | 14 | 39551 | 2743 +-------+-------+-------+-------+-------+ 2744 | 39576 | 412 | 677 | 14 | 39953 | 2745 +-------+-------+-------+-------+-------+ 2746 | 39980 | 394 | 683 | 14 | 40361 | 2747 +-------+-------+-------+-------+-------+ 2748 | 40398 | 830 | 691 | 15 | 40787 | 2749 +-------+-------+-------+-------+-------+ 2750 | 40816 | 535 | 701 | 15 | 41213 | 2751 +-------+-------+-------+-------+-------+ 2752 | 41226 | 199 | 701 | 15 | 41621 | 2753 +-------+-------+-------+-------+-------+ 2754 | 41641 | 27 | 709 | 15 | 42043 | 2755 +-------+-------+-------+-------+-------+ 2756 | 42067 | 298 | 709 | 15 | 42467 | 2757 +-------+-------+-------+-------+-------+ 2758 | 42490 | 368 | 719 | 15 | 42899 | 2759 +-------+-------+-------+-------+-------+ 2760 | 42916 | 755 | 727 | 15 | 43331 | 2761 +-------+-------+-------+-------+-------+ 2762 | 43388 | 379 | 727 | 15 | 43801 | 2763 +-------+-------+-------+-------+-------+ 2764 | 43840 | 73 | 733 | 15 | 44257 | 2765 +-------+-------+-------+-------+-------+ 2766 | 44279 | 387 | 739 | 15 | 44701 | 2767 +-------+-------+-------+-------+-------+ 2768 | 44729 | 457 | 751 | 15 | 45161 | 2769 | 45183 | 761 | 751 | 15 | 45613 | 2770 +-------+-------+-------+-------+-------+ 2771 | 45638 | 855 | 757 | 15 | 46073 | 2772 +-------+-------+-------+-------+-------+ 2773 | 46104 | 370 | 769 | 15 | 46549 | 2774 +-------+-------+-------+-------+-------+ 2775 | 46574 | 261 | 769 | 15 | 47017 | 2776 +-------+-------+-------+-------+-------+ 2777 | 47047 | 299 | 787 | 15 | 47507 | 2778 +-------+-------+-------+-------+-------+ 2779 | 47523 | 920 | 787 | 15 | 47981 | 2780 +-------+-------+-------+-------+-------+ 2781 | 48007 | 269 | 787 | 15 | 48463 | 2782 +-------+-------+-------+-------+-------+ 2783 | 48489 | 862 | 797 | 15 | 48953 | 2784 +-------+-------+-------+-------+-------+ 2785 | 48976 | 349 | 809 | 15 | 49451 | 2786 +-------+-------+-------+-------+-------+ 2787 | 49470 | 103 | 809 | 15 | 49943 | 2788 +-------+-------+-------+-------+-------+ 2789 | 49978 | 115 | 821 | 15 | 50461 | 2790 +-------+-------+-------+-------+-------+ 2791 | 50511 | 93 | 821 | 16 | 50993 | 2792 +-------+-------+-------+-------+-------+ 2793 | 51017 | 982 | 827 | 16 | 51503 | 2794 +-------+-------+-------+-------+-------+ 2795 | 51530 | 432 | 839 | 16 | 52027 | 2796 +-------+-------+-------+-------+-------+ 2797 | 52062 | 340 | 853 | 16 | 52571 | 2798 +-------+-------+-------+-------+-------+ 2799 | 52586 | 173 | 853 | 16 | 53093 | 2800 +-------+-------+-------+-------+-------+ 2801 | 53114 | 421 | 857 | 16 | 53623 | 2802 +-------+-------+-------+-------+-------+ 2803 | 53650 | 330 | 863 | 16 | 54163 | 2804 +-------+-------+-------+-------+-------+ 2805 | 54188 | 624 | 877 | 16 | 54713 | 2806 +-------+-------+-------+-------+-------+ 2807 | 54735 | 233 | 877 | 16 | 55259 | 2808 +-------+-------+-------+-------+-------+ 2809 | 55289 | 362 | 883 | 16 | 55817 | 2810 +-------+-------+-------+-------+-------+ 2811 | 55843 | 963 | 907 | 16 | 56393 | 2812 +-------+-------+-------+-------+-------+ 2813 | 56403 | 471 | 907 | 16 | 56951 | 2814 +-------+-------+-------+-------+-------+ 2816 Table 2: Systematic indices and other parameters 2818 5.7. Operating with Octets, Symbols and Matrices 2820 5.7.1. General 2822 This remainder of this section describes the arithmetic operations 2823 that are used to generate encoding symbols from source symbols and to 2824 generate source symbols from encoding symbols. Mathematically, 2825 octets can be thought of as elements of a finite field, i.e., the 2826 finite field GF(256) with 256 elements, and thus the addition and 2827 multiplication operations and identity elements and inverses over 2828 both operations are defined. Matrix operations and symbol operations 2829 are defined based on the arithmetic operations on octets. This 2830 allows a full implementation of these arithmetic operations without 2831 having to understand the underlying mathematics of finite fields. 2833 5.7.2. Arithmetic Operations on Octets 2835 Octets are mapped to non-negative integers in the range 0 through 255 2836 in the usual way: A single octet of data from a symbol, 2837 B[7],B[6],B[5],B[4],B[3],B[2],B[1],B[0], where B[7] is the highest 2838 order bit and B[0] is the lowest order bit, is mapped to the integer 2839 i=B[7]*128+B[6]*64+B[5]*32+B[4]*16+B[3]*8+B[2]*4+B[1]*2+B[0]. 2841 The addition of two octets u and v defined as the XOR operation, 2842 i.e., 2844 u + v = u ^ v. 2846 Subtraction is defined in the same way, so we also have 2848 u - v = u ^ v. 2850 The zero element (additive identity) is the octet represented by the 2851 integer 0. The additive inverse of u is simply u, i.e., 2853 u + u = 0. 2855 The multiplication of two octets is defined with the help of two 2856 tables OCT_EXP and OCT_LOG, which are given in Section 5.7.3 and 2857 Section 5.7.4, respectively. The table OCT_LOG maps octets (other 2858 than the zero element) to non-negative integers, and OCT_EXP maps 2859 non-negative integers to octets. For two octets u and v, we define 2861 u * v = 2863 0, if either u or v are 0, 2864 OCT_EXP[OCT_LOG[u] + OCT_LOG[v]] otherwise. 2866 Note that the '+' on the right hand side of the above is the usual 2867 integer addition, since its arguments are ordinary integers. 2869 The division u / v of two octets u and v, and where v != 0, is 2870 defined as follows: 2872 u / v = 2874 0, if u == 0, 2876 OCT_EXP[OCT_LOG[u] - OCT_LOG[v] + 255] otherwise. 2878 The one element (multiplicative identity) is the octet represented by 2879 the integer 1. For an octet u that is not the zero element, i.e., 2880 the multiplicative inverse of u is 2882 OCT_EXP[255 - OCT_LOG[u]]. 2884 The octet denoted by alpha is the octet with the integer 2885 representation 2. If i is a non-negative integer 0 <= i < 256, we 2886 have 2888 alpha^^i = OCT_EXP[i]. 2890 5.7.3. The table OCT_EXP 2892 The table OCT_EXP contains 510 octets. The indexing starts at 0 and 2893 ranges up to 509, and the entries are the octets with the following 2894 positive integer representation: 2896 1, 2, 4, 8, 16, 32, 64, 128, 29, 58, 116, 232, 205, 135, 19, 38, 76, 2897 152, 45, 90, 180, 117, 234, 201, 143, 3, 6, 12, 24, 48, 96, 192, 157, 2898 39, 78, 156, 37, 74, 148, 53, 106, 212, 181, 119, 238, 193, 159, 35, 2899 70, 140, 5, 10, 20, 40, 80, 160, 93, 186, 105, 210, 185, 111, 222, 2900 161, 95, 190, 97, 194, 153, 47, 94, 188, 101, 202, 137, 15, 30, 60, 2901 120, 240, 253, 231, 211, 187, 107, 214, 177, 127, 254, 225, 223, 163, 2902 91, 182, 113, 226, 217, 175, 67, 134, 17, 34, 68, 136, 13, 26, 52, 2903 104, 208, 189, 103, 206, 129, 31, 62, 124, 248, 237, 199, 147, 59, 2904 118, 236, 197, 151, 51, 102, 204, 133, 23, 46, 92, 184, 109, 218, 2905 169, 79, 158, 33, 66, 132, 21, 42, 84, 168, 77, 154, 41, 82, 164, 85, 2906 170, 73, 146, 57, 114, 228, 213, 183, 115, 230, 209, 191, 99, 198, 2907 145, 63, 126, 252, 229, 215, 179, 123, 246, 241, 255, 227, 219, 171, 2908 75, 150, 49, 98, 196, 149, 55, 110, 220, 165, 87, 174, 65, 130, 25, 2909 50, 100, 200, 141, 7, 14, 28, 56, 112, 224, 221, 167, 83, 166, 81, 2910 162, 89, 178, 121, 242, 249, 239, 195, 155, 43, 86, 172, 69, 138, 9, 2911 18, 36, 72, 144, 61, 122, 244, 245, 247, 243, 251, 235, 203, 139, 11, 2912 22, 44, 88, 176, 125, 250, 233, 207, 131, 27, 54, 108, 216, 173, 71, 2913 142, 1, 2, 4, 8, 16, 32, 64, 128, 29, 58, 116, 232, 205, 135, 19, 38, 2914 76, 152, 45, 90, 180, 117, 234, 201, 143, 3, 6, 12, 24, 48, 96, 192, 2915 157, 39, 78, 156, 37, 74, 148, 53, 106, 212, 181, 119, 238, 193, 159, 2916 35, 70, 140, 5, 10, 20, 40, 80, 160, 93, 186, 105, 210, 185, 111, 2917 222, 161, 95, 190, 97, 194, 153, 47, 94, 188, 101, 202, 137, 15, 30, 2918 60, 120, 240, 253, 231, 211, 187, 107, 214, 177, 127, 254, 225, 223, 2919 163, 91, 182, 113, 226, 217, 175, 67, 134, 17, 34, 68, 136, 13, 26, 2920 52, 104, 208, 189, 103, 206, 129, 31, 62, 124, 248, 237, 199, 147, 2921 59, 118, 236, 197, 151, 51, 102, 204, 133, 23, 46, 92, 184, 109, 218, 2922 169, 79, 158, 33, 66, 132, 21, 42, 84, 168, 77, 154, 41, 82, 164, 85, 2923 170, 73, 146, 57, 114, 228, 213, 183, 115, 230, 209, 191, 99, 198, 2924 145, 63, 126, 252, 229, 215, 179, 123, 246, 241, 255, 227, 219, 171, 2925 75, 150, 49, 98, 196, 149, 55, 110, 220, 165, 87, 174, 65, 130, 25, 2926 50, 100, 200, 141, 7, 14, 28, 56, 112, 224, 221, 167, 83, 166, 81, 2927 162, 89, 178, 121, 242, 249, 239, 195, 155, 43, 86, 172, 69, 138, 9, 2928 18, 36, 72, 144, 61, 122, 244, 245, 247, 243, 251, 235, 203, 139, 11, 2929 22, 44, 88, 176, 125, 250, 233, 207, 131, 27, 54, 108, 216, 173, 71, 2930 142 2932 5.7.4. The table OCT_LOG 2934 The table OCT_LOG contains 255 non-negative integers. The table is 2935 indexed by octets interpreted as integers. The octet corresponding 2936 to the zero element, which is represented by the integer 0, is 2937 excluded as an index, and thus indexing starts at 1 and ranges up to 2938 255, and the entries are the following: 2940 0, 1, 25, 2, 50, 26, 198, 3, 223, 51, 238, 27, 104, 199, 75, 4, 100, 2941 224, 14, 52, 141, 239, 129, 28, 193, 105, 248, 200, 8, 76, 113, 5, 2942 138, 101, 47, 225, 36, 15, 33, 53, 147, 142, 218, 240, 18, 130, 69, 2943 29, 181, 194, 125, 106, 39, 249, 185, 201, 154, 9, 120, 77, 228, 114, 2944 166, 6, 191, 139, 98, 102, 221, 48, 253, 226, 152, 37, 179, 16, 145, 2945 34, 136, 54, 208, 148, 206, 143, 150, 219, 189, 241, 210, 19, 92, 2946 131, 56, 70, 64, 30, 66, 182, 163, 195, 72, 126, 110, 107, 58, 40, 2947 84, 250, 133, 186, 61, 202, 94, 155, 159, 10, 21, 121, 43, 78, 212, 2948 229, 172, 115, 243, 167, 87, 7, 112, 192, 247, 140, 128, 99, 13, 103, 2949 74, 222, 237, 49, 197, 254, 24, 227, 165, 153, 119, 38, 184, 180, 2950 124, 17, 68, 146, 217, 35, 32, 137, 46, 55, 63, 209, 91, 149, 188, 2951 207, 205, 144, 135, 151, 178, 220, 252, 190, 97, 242, 86, 211, 171, 2952 20, 42, 93, 158, 132, 60, 57, 83, 71, 109, 65, 162, 31, 45, 67, 216, 2953 183, 123, 164, 118, 196, 23, 73, 236, 127, 12, 111, 246, 108, 161, 2954 59, 82, 41, 157, 85, 170, 251, 96, 134, 177, 187, 204, 62, 90, 203, 2955 89, 95, 176, 156, 169, 160, 81, 11, 245, 22, 235, 122, 117, 44, 215, 2956 79, 174, 213, 233, 230, 231, 173, 232, 116, 214, 244, 234, 168, 80, 2957 88, 175 2959 5.7.5. Operations on Symbols 2961 Operations on symbols have the same semantics as operations on 2962 vectors of octets of length T in this specification. Thus, if U and 2963 V are two symbols formed by the octets u[0], ..., u[T-1] and v[0], 2964 ..., v[T-1], respectively, the sum of symbols U + V is defined to be 2965 the component-wise sum of octets, i.e., equal to the symbol D formed 2966 by the octets d[0], ..., d[T-1], such that 2968 d[i] = u[i] + v[i], 0 <= i < T. 2970 Furthermore, if beta is an octet, the product beta*U is defined to be 2971 the symbol D obtained by multiplying each octet of U by beta, i.e., 2973 d[i] = beta*u[i], 0 <= i < T. 2975 5.7.6. Operations on Matrices 2977 All matrices in this specification have entries that are octets, and 2978 thus matrix operations and definitions are defined in terms of the 2979 underlying octet arithmetic, e.g., operations on a matrix, matrix 2980 rank and matrix inversion. 2982 5.8. Requirements for a Compliant Decoder 2984 If a RaptorQ compliant decoder receives a mathematically sufficient 2985 set of encoding symbols generated according to the encoder 2986 specification in Section 5.3 for reconstruction of a source block 2987 then such a decoder SHOULD recover the entire source block. 2989 A RaptorQ compliant decoder SHALL have the following recovery 2990 properties for source blocks with K' source symbols for all values of 2991 K' in Table 2 of Section 5.6. 2993 1. If the decoder receives K' encoding symbols generated according 2994 to the encoder specification in Section 5.3 with corresponding 2995 ESIs chosen independently and uniformly at random from the range 2996 of possible ESIs then on average the decoder will fail to recover 2997 the entire source block at most 1 out of 100 times. 2999 2. If the decoder receives K'+1 encoding symbols generated according 3000 to the encoder specification in Section 5.3 with corresponding 3001 ESIs chosen independently and uniformly at random from the range 3002 of possible ESIs then on average the decoder will fail to recover 3003 the entire source block at most 1 out of 10,000 times. 3005 3. If the decoder receives K'+2 encoding symbols generated according 3006 to the encoder specification in Section 5.3 with corresponding 3007 ESIs chosen independently and uniformly at random from the range 3008 of possible ESIs then on average the decoder will fail to recover 3009 the entire source block at most 1 out of 1,000,000 times. 3011 Note that the Example FEC Decoder specified in Section 5.4 fulfills 3012 both requirements, i.e. 3014 1. it can reconstruct a source block as long as it receives a 3015 mathematically sufficient set of encoding symbols generated 3016 according to the encoder specification in Section 5.3; 3018 2. it fulfills the mandatory recovery properties from above. 3020 6. Security Considerations 3022 Data delivery can be subject to denial-of-service attacks by 3023 attackers which send corrupted packets that are accepted as 3024 legitimate by receivers. This is particularly a concern for 3025 multicast delivery because a corrupted packet may be injected into 3026 the session close to the root of the multicast tree, in which case 3027 the corrupted packet will arrive at many receivers. This is 3028 particularly a concern when the code described in this document is 3029 used because the use of even one corrupted packet containing encoding 3030 data may result in the decoding of an object that is completely 3031 corrupted and unusable. It is thus RECOMMENDED that source 3032 authentication and integrity checking are applied to decoded objects 3033 before delivering objects to an application. For example, a SHA-256 3034 hash [FIPS.180-3.2008] of an object may be appended before 3035 transmission, and the SHA-256 hash is computed and checked after the 3036 object is decoded but before it is delivered to an application. 3037 Source authentication SHOULD be provided, for example by including a 3038 digital signature verifiable by the receiver computed on top of the 3039 hash value. It is also RECOMMENDED that a packet authentication 3040 protocol such as TESLA [RFC4082] be used to detect and discard 3041 corrupted packets upon arrival. This method may also be used to 3042 provide source authentication. Furthermore, it is RECOMMENDED that 3043 Reverse Path Forwarding checks be enabled in all network routers and 3044 switches along the path from the sender to receivers to limit the 3045 possibility of a bad agent successfully injecting a corrupted packet 3046 into the multicast tree data path. 3048 Another security concern is that some FEC information may be obtained 3049 by receivers out-of-band in a session description, and if the session 3050 description is forged or corrupted then the receivers will not use 3051 the correct protocol for decoding content from received packets. To 3052 avoid these problems, it is RECOMMENDED that measures be taken to 3053 prevent receivers from accepting incorrect session descriptions, 3054 e.g., by using source authentication to ensure that receivers only 3055 accept legitimate session descriptions from authorized senders. 3057 7. IANA Considerations 3059 Values of FEC Encoding IDs and FEC Instance IDs are subject to IANA 3060 registration. For general guidelines on IANA considerations as they 3061 apply to this document, see [RFC5052]. IANA is requested to assign a 3062 value under the ietf:rmt:fec:encoding name-space to "RaptorQ Code" as 3063 the Fully-Specified FEC Encoding ID value associated with this 3064 specification, preferably the value 6. 3066 8. Acknowledgements 3068 Thanks are due to Ranganathan (Ranga) Krishnan. Ranga Krishnan has 3069 been very supportive in finding and resolving implementation details 3070 and in finding the systematic indices. In addition, Habeeb Mohiuddin 3071 Mohammed and Antonios Pitarokoilis, both from the Munich University 3072 of Technology (TUM) and Alan Shinsato have done two independent 3073 implementations of the RaptorQ encoder/decoder that have helped to 3074 clarify and to resolve issues with this specification. 3076 9. References 3078 9.1. Normative references 3080 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 3081 Requirement Levels", BCP 14, RFC 2119, March 1997. 3083 [RFC4082] Perrig, A., Song, D., Canetti, R., Tygar, J., and B. 3084 Briscoe, "Timed Efficient Stream Loss-Tolerant 3085 Authentication (TESLA): Multicast Source Authentication 3086 Transform Introduction", RFC 4082, June 2005. 3088 [FIPS.180-3.2008] 3089 "Secure Hash Standard", National Institute of Standards 3090 and Technology FIPS PUB 180-3, October 2008. 3092 [RFC5052] Watson, M., Luby, M., and L. Vicisano, "Forward Error 3093 Correction (FEC) Building Block", RFC 5052, August 2007. 3095 9.2. Informative references 3097 [RFC3453] Luby, M., Vicisano, L., Gemmell, J., Rizzo, L., Handley, 3098 M., and J. Crowcroft, "The Use of Forward Error Correction 3099 (FEC) in Reliable Multicast", RFC 3453, December 2002. 3101 [RFC5053] Luby, M., Shokrollahi, A., Watson, M., and T. Stockhammer, 3102 "Raptor Forward Error Correction Scheme for Object 3103 Delivery", RFC 5053, October 2007. 3105 [LTCodes] Luby, "LT codes, Annual IEEE Symposium on Foundations of 3106 Computer Science, pp. 271 -- 280, 2002.", November 2002. 3108 Authors' Addresses 3110 Michael Luby 3111 Qualcomm Incorporated 3112 3165 Kifer Road 3113 Santa Clara, CA 95051 3114 U.S.A. 3116 Email: luby@qualcomm.com 3118 Amin Shokrollahi 3119 EPFL 3120 Laboratoire d'algorithmique 3121 EPFL 3122 Station 14 3123 Batiment BC 3124 Lausanne 1015 3125 Switzerland 3127 Email: amin.shokrollahi@epfl.ch 3129 Mark Watson 3130 Netflix Inc. 3131 100 Winchester Circle 3132 Los Gatos, CA 95032 3133 U.S.A. 3135 Email: watsonm@netflix.com 3136 Thomas Stockhammer 3137 Nomor Research 3138 Brecherspitzstrasse 8 3139 Munich 81541 3140 Germany 3142 Email: stockhammer@nomor.de 3144 Lorenz Minder 3145 Qualcomm Incorporated 3146 3165 Kifer Road 3147 Santa Clara, CA 95051 3148 U.S.A. 3150 Email: lminder@qualcomm.com