idnits 2.17.1 draft-roca-rmt-ldpc-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** It looks like you're using RFC 3978 boilerplate. You should update this to the boilerplate described in the IETF Trust License Policy document (see https://trustee.ietf.org/license-info), which is required now. -- Found old boilerplate from RFC 3978, Section 5.1 on line 17. -- Found old boilerplate from RFC 3978, Section 5.5 on line 740. -- Found old boilerplate from RFC 3979, Section 5, paragraph 1 on line 717. -- Found old boilerplate from RFC 3979, Section 5, paragraph 2 on line 724. -- Found old boilerplate from RFC 3979, Section 5, paragraph 3 on line 730. ** This document has an original RFC 3978 Section 5.4 Copyright Line, instead of the newer IETF Trust Copyright according to RFC 4748. ** This document has an original RFC 3978 Section 5.5 Disclaimer, instead of the newer disclaimer which includes the IETF Trust according to RFC 4748. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- == No 'Intended status' indicated for this document; assuming Proposed Standard Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) ** There are 19 instances of lines with control characters in the document. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the RFC 3978 Section 5.4 Copyright Line does not match the current year -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (June 28, 2005) is 6877 days in the past. Is this intentional? -- Found something which looks like a code comment -- if you have code sections in the document, please surround them with '' and '' lines. Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) ** Obsolete normative reference: RFC 3452 (Obsoleted by RFC 5052, RFC 5445) ** Downref: Normative reference to an Informational RFC: RFC 3453 Summary: 7 errors (**), 0 flaws (~~), 2 warnings (==), 8 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 RMT V. Roca 3 Internet-Draft C. Neumann 4 Expires: December 30, 2005 INRIA 5 D. Furodet 6 STMicroelectronics 7 June 28, 2005 9 Low Density Parity Check (LDPC) Forward Error Correction 10 draft-roca-rmt-ldpc-00.txt 12 Status of this Memo 14 By submitting this Internet-Draft, each author represents that any 15 applicable patent or other IPR claims of which he or she is aware 16 have been or will be disclosed, and any of which he or she becomes 17 aware will be disclosed, in accordance with Section 6 of BCP 79. 19 Internet-Drafts are working documents of the Internet Engineering 20 Task Force (IETF), its areas, and its working groups. Note that 21 other groups may also distribute working documents as Internet- 22 Drafts. 24 Internet-Drafts are draft documents valid for a maximum of six months 25 and may be updated, replaced, or obsoleted by other documents at any 26 time. It is inappropriate to use Internet-Drafts as reference 27 material or to cite them other than as "work in progress." 29 The list of current Internet-Drafts can be accessed at 30 http://www.ietf.org/ietf/1id-abstracts.txt. 32 The list of Internet-Draft Shadow Directories can be accessed at 33 http://www.ietf.org/shadow.html. 35 This Internet-Draft will expire on December 30, 2005. 37 Copyright Notice 39 Copyright (C) The Internet Society (2005). 41 Abstract 43 This document describes an Under-Specified FEC Scheme that can be 44 used with the broad class of Low Density Parity Check (LDPC) codes 45 and their application to the reliable delivery of objects on packet 46 erasure channels. Additionally, this document describes the LDPC- 47 Staircase and LDPC-Triangle Forward Error Correction codes, two 48 instances of the LDPC FEC Scheme, in a way that enables fully inter- 49 operable implementations. The LDPC codes belong to the class of 50 large block FEC codes, as defined in RFC3453, which enables them to 51 efficiently encode/decode large objects, in a single block. They 52 also enable a receiver to recover the k source symbols from any set 53 of a little bit more than k encoding symbols. 55 Table of Contents 57 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 58 2. Requirements notation . . . . . . . . . . . . . . . . . . . . 4 59 3. Definitions, Notations and Abbreviations . . . . . . . . . . . 5 60 3.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . 5 61 3.2 Notations . . . . . . . . . . . . . . . . . . . . . . . . 5 62 3.3 Abbreviations . . . . . . . . . . . . . . . . . . . . . . 6 63 4. Formats and Codes . . . . . . . . . . . . . . . . . . . . . . 7 64 4.1 FEC Payload IDs . . . . . . . . . . . . . . . . . . . . . 7 65 4.2 FEC Object Transmission Information . . . . . . . . . . . 7 66 4.2.1 Mandatory Elements . . . . . . . . . . . . . . . . . . 7 67 4.2.2 Common Elements . . . . . . . . . . . . . . . . . . . 7 68 4.2.3 Scheme-Specific Elements . . . . . . . . . . . . . . . 8 69 4.2.4 Encoding Format . . . . . . . . . . . . . . . . . . . 8 70 5. Procedures . . . . . . . . . . . . . . . . . . . . . . . . . . 9 71 5.1 General . . . . . . . . . . . . . . . . . . . . . . . . . 9 72 5.2 Parity Check Matrix . . . . . . . . . . . . . . . . . . . 10 73 5.3 Derivations and Interpretation of the Fields Provided 74 in the FPI and FEC OTI . . . . . . . . . . . . . . . . . . 10 75 5.4 Pseudo Random Number Generator . . . . . . . . . . . . . . 11 76 6. Full Specification of the LDPC-Staircase Scheme . . . . . . . 12 77 6.1 Instance Specific Parameters . . . . . . . . . . . . . . . 12 78 6.2 Parity Check Matrix Creation . . . . . . . . . . . . . . . 12 79 6.3 Encoding . . . . . . . . . . . . . . . . . . . . . . . . . 14 80 6.4 Decoding . . . . . . . . . . . . . . . . . . . . . . . . . 14 81 7. Full Specification of the LDPC-Triangle Scheme . . . . . . . . 15 82 7.1 Instance Specific Parameters . . . . . . . . . . . . . . . 15 83 7.2 Parity Check Matrix Creation . . . . . . . . . . . . . . . 15 84 7.3 Encoding . . . . . . . . . . . . . . . . . . . . . . . . . 15 85 7.4 Decoding . . . . . . . . . . . . . . . . . . . . . . . . . 16 86 8. Security Considerations . . . . . . . . . . . . . . . . . . . 17 87 9. Intellectual Property . . . . . . . . . . . . . . . . . . . . 18 88 10. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . 19 89 11. References . . . . . . . . . . . . . . . . . . . . . . . . . 20 90 11.1 Normative References . . . . . . . . . . . . . . . . . . . 20 91 11.2 Informative References . . . . . . . . . . . . . . . . . . 20 92 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . 21 93 A. Iterative Decoding Algorithm (Informative) . . . . . . . . . . 22 94 Intellectual Property and Copyright Statements . . . . . . . . 24 96 1. Introduction 98 RFC 3453 [RFC3453] introduces large block FEC codes as an alternative 99 to small block FEC codes like Reed-Solomon. The main advantage of 100 such large block codes is the possibility to operate efficiently on 101 source blocks of several tens of thousands (or more) source symbols 102 of size. 104 The present document introduces the Under-Specified FEC Encoding ID 105 132 that is intended to be used with the "Low Density Parity Check" 106 (LDPC) FEC codes, that belong the class of large block codes. LDPC 107 codes rely on a dedicated matrix, called a "Parity Check Matrix", at 108 the encoding and decoding ends. The parity check matrix defines 109 relationships (or constraints) between the various encoding symbols 110 (i.e. source symbols and repair symbols), that are later used by the 111 decoder to reconstruct the original k source symbols if some of them 112 are missing. These codes are systematic, in the sense that the 113 encoding symbols include the source symbols in addition to the 114 redundant symbols. 116 -- editor's note: This document makes use of the FEC Encoding ID 117 value 132, but this may change after IANA assignment -- 119 Since the encoder and decoder must operate on the same parity check 120 matrix, some information must be communicated between them, as part 121 of the FEC Object Transmission Information. Its content and the 122 associated EXT_FTI are fully described in Section 4.2. 124 The two variants specified in this document belong to this broad 125 class of LDPC codes. But other codes, existing or forthcoming, may 126 also be added in the future, taking advantage of the framework 127 provided by the Under-Specified FEC Encoding ID 132. More 128 specifically, this document reserves the FEC Instance ID value 0 for 129 the LDPC-Staircase codes [Roca04][Mac03] and reserves the FEC 130 Instance ID value 1 for the LDPC-Triangle codes [Roca04]. A publicly 131 available reference implementation of these codes is available and 132 distributed under a GNU/LGPL license [LDPCrefimpl]. 134 2. Requirements notation 136 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 137 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 138 document are to be interpreted as described in [RFC2119]. 140 3. Definitions, Notations and Abbreviations 142 3.1 Definitions 144 This document uses the same terms and definitions as those specified 145 in [fec-bb-revised]. Additionally, it uses the following 146 definitions: 148 Encoding Symbol Group: a group of encoding symbols that are sent 149 together, within the same packet, and whose relationships to the 150 source object can be derived from a single Encoding Symbol ID. 152 Source Packet a data packet containing only source symbols. 154 Repair Packet a data packet containing only repair symbols. 156 3.2 Notations 158 This document uses the following notations: 160 L denotes the object transfer length in bytes 162 k denotes the number of source symbols in a source block 164 n denotes the number of encoding symbols 166 E denotes the encoding symbol length in bytes 168 B denotes the maximum source block length in terms of symbols 170 N denotes the number of source blocks into which the object shall 171 be partitioned 173 G denotes the number of encoding symbols per group, i.e. the 174 number of symbols sent in the same packet 176 rate denotes the so-called "code rate", i.e. the k/n ratio 178 max_n Maximum Number of Encoding Symbols per encoding block. This 179 depends on FEC code rate. 181 rand(m) denotes a pseudo-random number generator, that returns a 182 new random integer in [0; m-1] each time it is called. 184 3.3 Abbreviations 186 This document uses the following abbreviations: 188 ESI Encoding Symbol ID 190 4. Formats and Codes 192 4.1 FEC Payload IDs 194 The FEC Payload ID is composed of the Source Block Number and the 195 Encoding Symbol ID: 197 The Source Block Number identifies from which source block of the 198 object the encoding symbol(s) in the payload is(are) generated. 200 The Encoding Symbol ID identifies which specific encoding symbol 201 generated from the source block is carried in the packet payload. 202 Each encoding symbol is either an original source symbol or a 203 redundant symbol generated by the encoder. 205 There MUST be exactly one FEC Payload ID per packet. When multiple 206 encoding symbols are sent in the same packet, the FEC Payload ID 207 refers to the first symbol of the packet. The other symbols can be 208 deduced as explained in Section 5.1 210 0 1 2 3 211 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 212 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 213 | Source Block Number | 214 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 215 | Encoding Symbol ID | 216 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 218 Figure 1: FEC Payload ID encoding format for FEC Encoding ID 132 220 4.2 FEC Object Transmission Information 222 4.2.1 Mandatory Elements 224 FEC Encoding ID: the Under-Specified FEC Scheme described in this 225 document uses the FEC Encoding ID 132. 227 FEC Instance ID: this document reserves the FEC Instance ID value 0 228 for the LDPC-Staircase codes (Section 6) and the FEC Instance ID 229 value 1 for the LDPC-Triangle codes (Section 7). 231 4.2.2 Common Elements 233 The following elements MUST be used with the present FEC Scheme: 235 Transfer-Length: a non-negative integer indicating the length of the 236 object in bytes. 238 Encoding-Symbol-Length: a non-negative integer indicating the length 239 of each encoding symbol in bytes. 241 Maximum-Source-Block-Length: a non-negative integer indicating the 242 maximum number of source symbols in a source block. 244 Max-Number-of-Encoding-Symbols: a non-negative integer indicating the 245 maximum number of encoding symbols (i.e. source plus repair symbols 246 in the case of a systematic code). 248 Section 5.3 describes how to derive the values of each of these 249 elements. 251 4.2.3 Scheme-Specific Elements 253 PRNG seed: Seed (a 32 bit value) used to initiate the Pseudo Random 254 Generator (defined in Section 5.4). This element is optional and may 255 be used by some specific Instance IDs. 257 Other elements MAY be defined for Instance-Specific needs. 259 4.2.4 Encoding Format 261 This section shows possible encoding formats of the above FEC OTI. 263 4.2.4.1 Using the General EXT_FTI Format 265 0 1 2 3 266 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 267 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 268 | HET = 64 | HEL | | 269 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + 270 | Transfer-Length (L) | 271 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 272 | FEC Instance ID | Encoding Symbol Length (E) | 273 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 274 | Max Source Block Length (B) | 275 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 276 | Max Nb of Enc. Symbols (max_n) | 277 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 278 .. Scheme Specific optional elements . 279 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 281 5. Procedures 283 This section defines procedures that are common to all FEC Instance 284 IDs scoped by FEC Encoding ID 132. 286 5.1 General 288 The source object is first partitioned into blocks, using the block 289 partitioning algorithm specified in [fec-bb-revised]. To that 290 purpose, the B (maximum source block length in symbols), L (object 291 transfer length in bytes), and E (encoding symbol length in bytes) 292 arguments are provided. As an output, the object is partitioned into 293 N source blocks. These blocks are numbered consecutively from 0 to 294 N-1. The first I source blocks consist of A_large source symbols, 295 the remaining N-I source blocks consist of A_small source symbols. 296 Each source symbol is E bytes in length, except perhaps the last 297 symbol which may be shorter as explained in [fec-bb-revised]. 299 FEC encoding and decoding is done block per block, independently. 301 When multiple encoding symbols are sent in the same packet, it MUST 302 be possible to identify each symbol from this single FEC Payload ID. 303 To that purpose, the symbols of an Encoding Symbol Group (i.e. 304 packet): 306 o MUST be in sequence, from ESI i to ESI i+G-1 (inclusive), 308 o MUST all be either source symbols, or repair symbols. Therefore, 309 only source packets and repair packets are permitted, not mixed 310 ones. 312 The FEC Payload ID information MUST refer to the first encoding 313 symbol of the packet. 315 This specification does not specify what value for B should be used. 316 This decision SHOULD be clarified either at implementation time, when 317 the target use case is known, or in the specification of a FEC 318 Instance ID, for instance to take into account some specificities of 319 a FEC scheme. 321 Similarly, this specification does not specify if and when Encoding 322 Symbol Groups should be used or not, i.e. if and when we have G>1. 323 This decision SHOULD be clarified either at implementation time, when 324 the target use case is known, or in the specification of a FEC 325 Instance ID, for instance to take into account some specificities of 326 a FEC scheme. 328 In both cases, a receiver can derive the B and G values from the 329 information it receives. 331 5.2 Parity Check Matrix 333 LDPC codes rely on a parity check matrix, which represents a linear 334 equation system between repair symbols and source symbols of a given 335 block. The basic operator is XOR and the matrix can only be filled 336 with 1s and 0s. 338 The parity check matrix is logically divided into two parts: the left 339 side (from column 0 to k-1) which describes the occurrence of each 340 source symbol in the equation system; and the right side (from column 341 k to n-1) which describes the occurrence of each repair symbol in the 342 equation system. 344 An entry (a "1") in the matrix at position (i,j), i.e. at row i and 345 column j, means that the symbol with ESI i appears in equation j. 347 5.3 Derivations and Interpretation of the Fields Provided in the FPI 348 and FEC OTI 350 The fields provided in the FEC OTI are derived using the 351 "n-algorithm", described below: 353 AT A SENDER: 355 Input: 357 B Maximum Source Block Length, i.e., the maximum number of source 358 symbols per source block. This is given by the FEC codec 359 specifications and/or the execution environment limitations. 361 k Source Block Length, i.e., the number of source symbols per 362 source block. This is given by source blocking algorithm. 364 rate or (k,n) FEC code rate, which is given by the user (e.g. when 365 starting a FLUTE sending application). It is expressed either as 366 a floating point value, R, or as a quotient k/n. The latter 367 option is RECOMMENDED for the integer math version of the 368 algorithm. 370 Output: 372 max_n Maximum Number of Encoding Symbols per encoding block. This 373 depends on FEC code rate. 375 n Encoding Block Length, i.e., the number of encoding symbols 376 generated for the source block. 378 Algorithm: 380 a. max_n = B / R rounded down to the nearest integer (max_n = (B * 381 b) div a) 383 b. n = k * max_n / B rounded down to the nearest integer (n = (k * 384 max_n) div B) 386 AT A RECEIVER: 388 Input: B, max_n, k 390 Output: n 392 Algorithm: 394 a. n = k * max_n / B rounded down to the nearest integer (n = (k * 395 max_n) div B) 397 Notes: (1) X div Y denotes the integer quotient of the division X/Y 399 The use of floating point arithmetic in the algorithm might lead to 400 erroneous results caused by rounding problems, depending on the 401 mathematical library used. These problems can be avoided by using 402 only integer math in all algorithm calculations. It is strongly 403 recommended not to use rounding functions, and how to do that is 404 presented in brackets 406 5.4 Pseudo Random Number Generator 408 The present FEC Encoding ID relies on a pseudo-random number 409 generator that must be fully specified in order to enable the 410 receivers and the senders to build the same parity check matrix. 412 -- editor's note: The PRNG to use is TBD. Current implementation 413 relies on the GNU C Library lrand48() function, but this may not 414 be the most appropriate choice. -- 416 6. Full Specification of the LDPC-Staircase Scheme 418 6.1 Instance Specific Parameters 420 LDPC-Staircase is identified by th Under-Specified FEC Encoding ID 421 132 and the the FEC Instance ID 0. 423 LDPC-Staircase is based on a pseudo-random number generator as 424 specified in Section 5.4. Therefore the seed used to initiate the 425 PRNG is an instance-specific FEC Object Transmission Information 426 element and MUST be transmitted within the FEC OTI, as specified in 427 Section 4.2. 429 6.2 Parity Check Matrix Creation 431 The matrix creation algorithm for LDPC Staircase is described in the 432 following. The algorithm can be divided into two parts: The left 433 side of the matrix where the occurrence of the source symbols in the 434 equations is described, and the right side of the matrix where repair 435 symbols are described. The left side is generated with the following 436 algorithm: 438 /* initialize a list of possible choices to 439 * guarantee a homogeneous "1" distribution */ 440 for(h = 3*k-1; h >= 0; h--) { 441 u[h] = h % (n-k); 442 } 443 /* left limit within the list of possible choices, u[] */ 444 t = 0; 446 for(j = 0; j < k; j++) { /* for each source symbol column */ 447 for(h = 0; h < 3; h++) { /* add 3 "1s" */ 448 /* check that valid available choices remain */ 449 for(i = t; i < 3*k && matrix_has_entry(u[i],j); i++); 451 if(i < 3*k) { 452 /* choose one index within the 453 * list of possible choices */ 454 do { 455 i = t + rand() % (3*k-t); 456 } while (matrix_has_entry(u[i],j)); 457 matrix_insert_entry(u[i],j); 459 /* replace with u[t] which has never been chosen */ 460 u[i] = u[t]; 461 t++; 462 } else { 463 /* no choice left, choose one randomly */ 464 do { 465 i = rand() % (n-k); 466 } while (matrix_has_entry(i,j)); 467 matrix_insert_entry(i,j); 468 } 469 } 470 } 472 /* Add extra bits to avoid rows with less than two checks. */ 473 for(i = 0; i < n-k; i++) { /* for each row */ 474 if(degree_of_row(i) == 0) { 475 j = rand() % k; 476 e = matrix_insert_entry(i,j); 477 } 478 if(degree_of_row(i) == 1) { 479 do { 480 j = rand()% k; 481 } while (matrix_has_entry(i,j)); 482 matrix_insert_entry(i,j); 483 } 484 } 486 The right side (the staircase) is generated with the following 487 algorithm: 489 for(i = 0; i < n-k; i++) { /* for each row */ 490 matrix_insert_entry(i,k+i); 491 if (i > 0) 492 matrix_insert_entry(i,k+i-1); 493 } 495 6.3 Encoding 497 Thanks to the staircase matrix, repair symbol creation is 498 straightforward: each repair symbol is equal to the sum of all source 499 symbols in the associated equation, plus the previous repair packet. 500 Therefore encoding should follow the natural repair symbol order, 501 i.e. generate repair symbol with ESI i before symbol ESI i+1. 503 6.4 Decoding 505 Decoding can be done using the general LDPC iterative decoding 506 algorithm as described in Appendix A. 508 Other techniques can be used, for instance solving th system of n-k 509 linear equations whose variables are the source an repair symbols 511 7. Full Specification of the LDPC-Triangle Scheme 513 7.1 Instance Specific Parameters 515 LDPC-Triangle is identified by th Under-Specified FEC Encoding ID 132 516 and the the FEC Instance ID 1. 518 LDPC-Triangle is based on a pseudo-random number generator as 519 specified in Section 5.4. Therefore the seed used to initiate the 520 PRNG is an instance-specific FEC Object Transmission Information 521 element, and MUST be transmitted within the FEC OTI, as specified in 522 Section 4.2. 524 7.2 Parity Check Matrix Creation 526 The matrix creation algorithm for LDPC Triangle is the following. 527 The left side is the same as for LDPC Staircase (see Section 6.2). 528 The right side (the triangle) is generated with the following 529 algorithm: 531 for(i = 0; i < n-k; i++) { /* for each row */ 532 /* create the identity */ 533 matrix_insert_entry(i,k+i); 534 if (i > 0) { 535 /* create the staircase */ 536 matrix_insert_entry(i,k+i-1); 538 /* fill the triangle */ 539 int j = i; 540 for (l = 0; l < j; l++) { 541 if (j != 0) { 542 temp = rand() % j; 543 matrix_insert_entry(pchkMatrix, i, k+j); 544 } 545 } 546 } 547 } 549 7.3 Encoding 551 Just like LDPC-Triangle repair symbol creation is straightforward: 552 each repair symbol is equal to the sum of all source symbols in the 553 associated equation, plus some previous repair packets specified in 554 the triangle. Encoding should follow the natural repair symbol 555 order, i.e. generate repair symbol with ESI i before symbol ESI i+1. 557 7.4 Decoding 559 Decoding can be done using the general LDPC iterative decoding 560 algorithm as described in Appendix A. 562 Other techniques can be used, for instance solving th system of n-k 563 linear equation whose variables are the source an repair symbols 565 8. Security Considerations 567 The security considerations for this document are the same as they 568 are for RFC 3452 [RFC3452]. 570 9. Intellectual Property 572 The authors are not aware of any intellectual property rights 573 associated to the two LDPC codes specified within this document. Yet 574 other LDPC codes and associated techniques MAY be covered by IPR. 576 10. Acknowledgments 578 Section 5.3 is derived from a previous Internet-Draft, and we would 579 like to thank S. Peltotalo and J. Peltotalo for their contribution. 581 We would also like to thank Pascal Moniot from STMicroelectronics for 582 his comments. 584 11. References 586 11.1 Normative References 588 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 589 Requirement Levels", RFC 2119, BCP 14, March 1997. 591 [RFC3452] Luby, M., Vicisano, L., Gemmell, J., Rizzo, L., Handley, 592 M., and J. Crowcroft, "Forward Error Correction (FEC) 593 Building Block", RFC 3452, December 2002. 595 [RFC3453] Luby, M., Vicisano, L., Gemmell, J., Rizzo, L., Handley, 596 M., and J. Crowcroft, "The Use of Forward Error Correction 597 (FEC) in Reliable Multicast", RFC 3453, December 2002. 599 [fec-bb-revised] 600 Watson, M., Luby, M., and L. Vicisano, "Forward Error 601 Correction (FEC) Building Block (revised)", draft-ietf- 602 rmt-fec-bb-revised-00.txt draft-ietf-rmt-fec-bb-revised- 603 00.txt, April 2005. 605 11.2 Informative References 607 [LDPCrefimpl] 608 Roca, V., Neumann, C., and J. Laboure, "LDPC-Staircase/ 609 LDPC-Triangle Codec Reference Implementation", MCLv3 610 project PLANETE Research Team, INRIA Rhone-Alpes, 611 June 2005. 613 [Mac03] MacKay, D., "Information Theory, Inference and Learning 614 Algorithms", Cambridge University Press, ISBN: 0521642981, 615 2003. 617 [Roca04] Roca, V. and C. Neumann, "Design, Evaluation and 618 Comparison of Four Large Block FEC Codecs: LDPC, LDGM, 619 LDGM Staircase and LDGM Triangle, Plus a Reed-Solomon 620 Small Block FEC Codec", INRIA Research Report RR-5225, 621 June 2004. 623 Authors' Addresses 625 Vincent Roca 626 INRIA 627 655, av. de l'Europe 628 Zirst; Montbonnot 629 ST ISMIER cedex 38334 630 France 632 Phone: 633 Email: vincent.roca@inrialpes.fr 634 URI: 636 Christoph Neumann 637 INRIA 638 655, av. de l'Europe 639 Zirst; Montbonnot 640 ST ISMIER cedex 38334 641 France 643 Phone: 644 Email: christoph.neumann@inrialpes.fr 645 URI: 647 David Furodet 648 STMicroelectronics 649 12, Rue Jules Horowitz 650 BP217 651 Grenoble Cedex 38019 652 France 654 Phone: 655 Email: david.furodet@st.com 656 URI: 658 Appendix A. Iterative Decoding Algorithm (Informative) 660 LDPC decoding over a packet erasure channel can be achieved through a 661 trivial iterative decoding algorithm. The underlying idea is the 662 following: 664 Given a set of linear equations, if one of them has only one 665 remaining unknown variable, then the value of this variable is 666 that of the constant term. So, replace this variable by its value 667 in all remaining linear equations, and reiterate. The value of 668 several variables can therefore be found by this recursive 669 algorithm. 671 Applied to LDPC FEC codes working over an erasure packet, the parity 672 check matrix defines a set of linear equations. The variables are 673 the source symbols and repair symbols. Of course, from a decoding 674 point of view, finding (i.e. decoding) all source symbols is the 675 target. Finding repair symbols is often required to that purpose, 676 but this is not the final goal. The iterative decoding algorithm is 677 the following: 679 Initialization: allocate a partial sum buffer partial_sum_i for 680 each line i: set it to 0. 682 For each newly received or decoded symbol s_i with ESI i: 684 1. If s_i is an already decoded or received symbol, return 685 immediately and do nothing. 687 2. If s_i is a source symbol, it is permanently stored in memory. 689 3. For each equation j having a degree greater than one (i.e. 690 more than one unknown variable), with an entry in column i 691 (i.e. having s_i as a variable), do the following: 693 + add s_i to partial_sum_i; 695 + remove the entry (j, i) of the H matrix. 697 + If the new degree of equation j is one, we have decoded a 698 new packet and have to remember the index of the equation 699 in a list of indexes for newly decoded packets for step 4. 701 4. For all newly generated packets in step 3: 703 + remove the last entry in equation j, 704 + move partial_sum_j into th buffer of symbol s_l, 706 + goto step 1 with the newly created symbol s_l 708 Intellectual Property Statement 710 The IETF takes no position regarding the validity or scope of any 711 Intellectual Property Rights or other rights that might be claimed to 712 pertain to the implementation or use of the technology described in 713 this document or the extent to which any license under such rights 714 might or might not be available; nor does it represent that it has 715 made any independent effort to identify any such rights. Information 716 on the procedures with respect to rights in RFC documents can be 717 found in BCP 78 and BCP 79. 719 Copies of IPR disclosures made to the IETF Secretariat and any 720 assurances of licenses to be made available, or the result of an 721 attempt made to obtain a general license or permission for the use of 722 such proprietary rights by implementers or users of this 723 specification can be obtained from the IETF on-line IPR repository at 724 http://www.ietf.org/ipr. 726 The IETF invites any interested party to bring to its attention any 727 copyrights, patents or patent applications, or other proprietary 728 rights that may cover technology that may be required to implement 729 this standard. Please address the information to the IETF at 730 ietf-ipr@ietf.org. 732 Disclaimer of Validity 734 This document and the information contained herein are provided on an 735 "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS 736 OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET 737 ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, 738 INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE 739 INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED 740 WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 742 Copyright Statement 744 Copyright (C) The Internet Society (2005). This document is subject 745 to the rights, licenses and restrictions contained in BCP 78, and 746 except as set forth therein, the authors retain all their rights. 748 Acknowledgment 750 Funding for the RFC Editor function is currently provided by the 751 Internet Society.