idnits 2.17.1 draft-ietf-rmt-bb-fec-rs-01.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 19. -- Found old boilerplate from RFC 3978, Section 5.5 on line 817. -- Found old boilerplate from RFC 3979, Section 5, paragraph 1 on line 794. -- Found old boilerplate from RFC 3979, Section 5, paragraph 2 on line 801. -- Found old boilerplate from RFC 3979, Section 5, paragraph 3 on line 807. ** 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 : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the RFC 3978 Section 5.4 Copyright Line does not match the current year == Line 254 has weird spacing: '...mat for m = 1...' -- 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 23, 2006) is 6516 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) == Outdated reference: A later version (-07) exists of draft-ietf-rmt-fec-bb-revised-03 ** Downref: Normative reference to an Informational RFC: RFC 3453 (ref. '3') == Outdated reference: A later version (-09) exists of draft-ietf-rmt-bb-fec-raptor-object-03 == Outdated reference: A later version (-08) exists of draft-ietf-rmt-bb-fec-ldpc-01 == Outdated reference: A later version (-10) exists of draft-ietf-rmt-pi-alc-revised-03 == Outdated reference: A later version (-14) exists of draft-ietf-rmt-pi-norm-revised-01 == Outdated reference: A later version (-16) exists of draft-ietf-rmt-flute-revised-01 Summary: 4 errors (**), 0 flaws (~~), 9 warnings (==), 7 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Reliable Multicast Transport J. Lacan 3 Internet-Draft ENSICA/LAAS-CNRS 4 Expires: December 25, 2006 V. Roca 5 INRIA 6 J. Peltotalo 7 S. Peltotalo 8 Tampere University of Technology 9 June 23, 2006 11 Reed-Solomon Forward Error Correction (FEC) 12 draft-ietf-rmt-bb-fec-rs-01.txt 14 Status of this Memo 16 By submitting this Internet-Draft, each author represents that any 17 applicable patent or other IPR claims of which he or she is aware 18 have been or will be disclosed, and any of which he or she becomes 19 aware will be disclosed, in accordance with Section 6 of BCP 79. 21 Internet-Drafts are working documents of the Internet Engineering 22 Task Force (IETF), its areas, and its working groups. Note that 23 other groups may also distribute working documents as Internet- 24 Drafts. 26 Internet-Drafts are draft documents valid for a maximum of six months 27 and may be updated, replaced, or obsoleted by other documents at any 28 time. It is inappropriate to use Internet-Drafts as reference 29 material or to cite them other than as "work in progress." 31 The list of current Internet-Drafts can be accessed at 32 http://www.ietf.org/ietf/1id-abstracts.txt. 34 The list of Internet-Draft Shadow Directories can be accessed at 35 http://www.ietf.org/shadow.html. 37 This Internet-Draft will expire on December 25, 2006. 39 Copyright Notice 41 Copyright (C) The Internet Society (2006). 43 Abstract 45 This document describes a Fully-Specified FEC scheme for the Reed- 46 Solomon forward error correction code and its application to the 47 reliable delivery of data objects on the packet erasure channel. 49 Reed-Solomon codes belong to the class of Maximum Distance Separable 50 (MDS) codes, i.e. they enable a receiver to recover the k source 51 symbols from any set of k received symbols. 53 The implementation described here is compatible with the 54 implementation from Luigi Rizzo. 56 Table of Contents 58 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 59 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 4 60 3. Definitions Notations and Abbreviations . . . . . . . . . . . 5 61 3.1. Definitions . . . . . . . . . . . . . . . . . . . . . . . 5 62 3.2. Notations . . . . . . . . . . . . . . . . . . . . . . . . 5 63 3.3. Abbreviations . . . . . . . . . . . . . . . . . . . . . . 6 64 4. Formats and Codes . . . . . . . . . . . . . . . . . . . . . . 7 65 4.1. FEC Payload ID . . . . . . . . . . . . . . . . . . . . . . 7 66 4.2. FEC Object Transmission Information . . . . . . . . . . . 8 67 4.2.1. Mandatory Elements . . . . . . . . . . . . . . . . . . 8 68 4.2.2. Common Elements . . . . . . . . . . . . . . . . . . . 8 69 4.2.3. Scheme-Specific Elements . . . . . . . . . . . . . . . 8 70 4.2.4. Encoding Format . . . . . . . . . . . . . . . . . . . 9 71 5. Procedures . . . . . . . . . . . . . . . . . . . . . . . . . . 11 72 5.1. Determining the Maximum Source Block Length (B) . . . . . 11 73 5.2. Determining the Number of Encoding Symbols of a Block . . 11 74 6. Reed-Solomon Codes Specification for the Erasure Channel . . . 13 75 6.1. Finite Field . . . . . . . . . . . . . . . . . . . . . . . 13 76 6.2. Reed-Solomon Encoding Algorithm . . . . . . . . . . . . . 14 77 6.2.1. Encoding Principles . . . . . . . . . . . . . . . . . 14 78 6.2.2. Encoding Complexity . . . . . . . . . . . . . . . . . 15 79 6.3. Reed-Solomon Decoding Algorithm . . . . . . . . . . . . . 15 80 6.3.1. Decoding Principles . . . . . . . . . . . . . . . . . 15 81 6.3.2. Decoding Complexity . . . . . . . . . . . . . . . . . 16 82 6.4. Implementation for the Packet Erasure Channel . . . . . . 16 83 7. Security Considerations . . . . . . . . . . . . . . . . . . . 18 84 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 19 85 9. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 20 86 10. References . . . . . . . . . . . . . . . . . . . . . . . . . . 21 87 10.1. Normative References . . . . . . . . . . . . . . . . . . . 21 88 10.2. Informative References . . . . . . . . . . . . . . . . . . 21 89 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 23 90 Intellectual Property and Copyright Statements . . . . . . . . . . 24 92 1. Introduction 94 The use of Forward Error Correction (FEC) codes is a classical 95 solution to improve the reliability of multicast and broadcast 96 transmissions. The [2] document describes a general framework to use 97 FEC in Content Delivery Protocols (CDP). The companion document [3] 98 describes some applications of FEC codes for content delivery. 100 Recent FEC schemes like [6] and [7] proposed erasure codes based on 101 sparse graphs/matrices. These codes are efficient in terms of 102 processing but not optimal in terms of correction capabilities when 103 dealing with "small" objects. 105 The FEC scheme described in this document belongs to the class of 106 Maximum Distance Separable codes that are optimal in terms of erasure 107 correction capability. In others words, it enables a receiver to 108 recover the k source symbols from any set of exactly k encoding 109 symbols. Even if the encoding/decoding complexity is larger than 110 that of [6] or [7], this family of codes is very useful. 112 Many applications dealing with content transmission or content 113 storage already rely on packet-based Reed-Solomon codes. In 114 particular, many of them use the Reed-Solomon codec of Luigi Rizzo 115 [4]. The goal of the present document to specify an implementation 116 of Reed-Solomon codes that is compatible with this codec. 118 2. Terminology 120 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 121 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 122 document are to be interpreted as described in RFC 2119 [1]. 124 3. Definitions Notations and Abbreviations 126 3.1. Definitions 128 This document uses the same terms and definitions as those specified 129 in [2]. Additionally, it uses the following definitions: 131 Source symbol: unit of data used during the encoding process. 133 Encoding symbol: unit of data generated by the encoding process. 135 Repair symbol: encoding symbol that is not a source symbol. 137 Systematic code: FEC code in which the source symbols are part of 138 the encoding symbols. 140 Source block: a block of k source symbols that are considered 141 together for the encoding. 143 Encoding Symbol Group: a group of encoding symbols that are sent 144 together within the same packet, and whose relationships to the 145 source block can be derived from a single Encoding Symbol ID. 147 Source Packet: a data packet containing only source symbols. 149 Repair Packet: a data packet containing only repair symbols. 151 3.2. Notations 153 This document uses the following notations: 155 L denotes the object transfer length in bytes. 157 k denotes the number of source symbols in a source block. 159 n_r denotes the number of repair symbols generated for a source 160 block. 162 n denotes the encoding block length, i.e. the number of encoding 163 symbols generated for a source block. Therefore: n = k + n_r. 165 max_n denotes the maximum number of encoding symbols generated for 166 any source block. 168 B denotes the maximum source block length in symbols, i.e. the 169 maximum number of source symbols per source block. 171 N denotes the number of source blocks into which the object shall 172 be partitioned. 174 E denotes the encoding symbol length in bytes. 176 S denotes the symbol size in units of m bit elements. When m = 8, 177 then S and E are equal. 179 m defines the length of the elements in the finite field, in bits. 181 q defines the number of elements in the finite field. We have: q 182 = 2^^m in this specification. 184 G denotes the number of encoding symbols per group, i.e. the 185 number of symbols sent in the same packet. 187 GM denotes the Generator Matrix of a Reed-Solomon code. 189 rate denotes the "code rate", i.e. the k/n ratio. 191 a^^b denotes a raised to the power b. 193 a^^-1 denotes the inverse of a. 195 I_k denotes the k*k identity matrix. 197 3.3. Abbreviations 199 This document uses the following abbreviations: 201 ESI stands for Encoding Symbol ID. 203 FEC OTI stands for FEC Object Transmission Information. 205 RS stands for Reed-Solomon. 207 MDS stands for Maximum Distance Separable code. 209 GF(q) denotes a finite field (A.K.A. Galois Field) with q 210 elements. We assume that q = 2^^m in this document. 212 4. Formats and Codes 214 4.1. FEC Payload ID 216 The FEC Payload ID is composed of the Source Block Number and the 217 Encoding Symbol ID. The length of these two fields depends on the 218 parameter m (which is transmitted in the FEC OTI) as follows : 220 o The Source Block Number (32-m bit field) identifies from which 221 source block of the object the encoding symbol(s) in the payload 222 is (are) generated. There are a maximum of 2^^(32-m) blocks per 223 object. 225 o The Encoding Symbol ID (m bit field) identifies which specific 226 encoding symbol(s) generated from the source block is(are) carried 227 in the packet payload. There are a maximum of 2^^m encoding 228 symbols per block. The first k values (0 to k - 1) identify 229 source symbols, the remaining n-k values identify repair symbols. 231 There MUST be exactly one FEC Payload ID per source or repair packet. 232 In case of an Encoding Symbol Group, when multiple encoding symbols 233 are sent in the same packet, the FEC Payload ID refers to the first 234 symbol of the packet. The other symbols can be deduced from the ESI 235 of the first symbol by incrementing sequentially the ESI. 237 The format of the FEC Payload ID for m = 8 and m = 16 is illustrated 238 in Figure 1 and Figure 2 respectively. 240 0 1 2 3 241 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 242 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 243 | Source Block Number (32-8=24 bits) | Enc. Symb. ID | 244 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 246 Figure 1: FEC Payload ID encoding format for m = 8 (default) 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 | Src Block Nb (32-16=16 bits) | Enc. Symbol ID (m=16 bits) | 252 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 254 Figure 2: FEC Payload ID encoding format for m = 16 256 4.2. FEC Object Transmission Information 258 4.2.1. Mandatory Elements 260 o FEC Encoding ID: the Fully-Specified FEC Scheme described in this 261 document uses FEC Encoding ID XX. 263 4.2.2. Common Elements 265 The following elements MUST be defined with the present FEC scheme: 267 o Transfer-Length (L): a non-negative integer indicating the length 268 of the object in bytes. There are some restrictions on the 269 maximum Transfer-Length that can be supported : 271 max_transfer_length = 2^^(32-m) * B * E 273 For instance, for m = 8, for B = 2^^8 - 1 (because the codec 274 operates on a finite field with 2^^8 elements) and if E = 1024 275 bytes, then the maximum transfer length is approximately equal to 276 2^^42 bytes (i.e. 4 Tera Bytes). Similarly, for m = 16, for B = 277 2^^16 - 1 and if E = 1024 bytes, then the maximum transfer length 278 is also approximately equal to 2^^42 bytes. For larger objects, 279 another FEC scheme, with a larger Source Block Number field in the 280 FEC Payload ID, could be defined. Another solution consists in 281 fragmenting large objects into smaller objects, each of them 282 complying with the above limits. 284 o Encoding-Symbol-Length (E): a non-negative integer indicating the 285 length of each encoding symbol in bytes. 287 o Maximum-Source-Block-Length (B): a non-negative integer indicating 288 the maximum number of source symbols in a source block. 290 o Max-Number-of-Encoding-Symbols (max_n): a non-negative integer 291 indicating the maximum number of encoding symbols generated for 292 any source block. 294 Section 5 explains how to derive the values of each of these 295 elements. 297 4.2.3. Scheme-Specific Elements 299 The following element MUST be defined with the present FEC Scheme. 300 It contains two distinct pieces of information: 302 o G: a non-negative integer indicating the number of encoding 303 symbols per group used for the object. The default value is 1, 304 meaning that each packet contains exactly one symbol. When no G 305 parameter is communicated to the decoder, then this latter MUST 306 assume that G = 1. 308 o Finite Field parameter, m: The m parameter is the length of the 309 finite field elements, in bits. It also characterizes the number 310 of elements in the finite field: q = 2^^m elements. The default 311 value is m = 8. When no finite field size parameter is 312 communicated to the decoder, then this latter MUST assume that m = 313 8. 315 4.2.4. Encoding Format 317 This section shows two possible encoding formats of the above FEC 318 OTI. The present document does not specify when one encoding format 319 or the other should be used. 321 4.2.4.1. Using the General EXT_FTI Format 323 The FEC OTI binary format is the following, when the EXT_FTI 324 mechanism is used (e.g. within the ALC [8] or NORM [9] protocols). 326 0 1 2 3 327 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 328 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 329 | HET = 64 | HEL | | 330 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + 331 | Transfer-Length (L) | 332 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 333 | m | G | Encoding Symbol Length (E) | 334 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 335 | Max Source Block Length (B) | Max Nb Enc. Symbols (max_n) | 336 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 338 Figure 3: EXT_FTI Header Format 340 4.2.4.2. Using the FDT Instance (FLUTE specific) 342 When it is desired that the FEC OTI be carried in the FDT Instance of 343 a FLUTE session [10], the following XML attributes must be described 344 for the associated object: 346 o FEC-OTI-Transfer-Length (L) 348 o FEC-OTI-Encoding-Symbol-Length (E) 349 o FEC-OTI-Maximum-Source-Block-Length (B) 351 o FEC-OTI-Max-Number-of-Encoding-Symbols (max_n) 353 o FEC-OTI-Number-of-Encoding-Symbols-per-Group (optional) (G) 355 o FEC-OTI-Finite-Field-Parameter (optional) (m) 357 When no G parameter is to be carried in the FEC OTI, the sender 358 simply omits the FEC-OTI-Number-of-Encoding-Symbols-per-Group 359 attribute. When no Finite Field parameter is to be carried in the 360 FEC OTI, the sender simply omits the FEC-OTI-Finite-Field-Parameter 361 attribute. 363 5. Procedures 365 5.1. Determining the Maximum Source Block Length (B) 367 The finite field size parameter, m, defines the number of non zero 368 elements in this field which is equal to: q - 1 = 2^^m - 1. Note 369 that q - 1 is also the theoretical maximum number of encoding symbols 370 that can be produced for a source block. For instance, when m = 8 371 (default): 373 max1_B = 2^^8 - 1 = 255 375 Additionally, a codec MAY impose other limitations on the maximum 376 block size. Yet it is not expected that such limits exist when using 377 the default m = 8 value. This decision SHOULD be clarified at 378 implementation time, when the target use case is known. This results 379 in a max2_B limitation. 381 Then, B is given by: 383 B = min(max1_B, max2_B) 385 Note that this calculation is only required at the coder, since the B 386 parameter is communicated to the decoder through the FEC OTI. 388 5.2. Determining the Number of Encoding Symbols of a Block 390 The following algorithm, also called "n-algorithm", explains how to 391 determine the actual number of encoding symbols for a given block. 393 AT A SENDER: 395 Input: 397 B: Maximum source block length, for any source block. Section 5.1 398 explains how to determine its value. 400 k: Current source block length. This parameter is given by the 401 block partitioning algorithm. 403 rate: FEC code rate, which is given by the user (e.g. when 404 starting a FLUTE sending application). It is expressed as a 405 floating point value. 407 Output: 409 max_n: Maximum number of encoding symbols generated for any source 410 block 411 n: Number of encoding symbols generated for this source block 413 Algorithm: 415 max_n = floor(B / rate); 417 if (max_n > 2^^m - 1) then return an error ("invalid code rate"); 419 n = floor(k * max_n / B); 421 AT A RECEIVER: 423 Input: 425 B: Extracted from the received FEC OTI 427 max_n: Extracted from the received FEC OTI 429 k: Given by the block partitioning algorithm 431 Output: 433 n 435 Algorithm: 437 n = floor(k * max_n / B); 439 Note that a Reed-Solomon decoder does not need to know the n value. 440 Therefore the receiver part of the "n-algorithm" is not necessary 441 from the Reed-Solomon decoder point of view. Yet a receiving 442 application using the Reed-Solomon FEC scheme will sometimes need to 443 know the value of n used by the sender, for instance for memory 444 management optimizations. To that purpose, the FEC OTI carries all 445 the parameters needed for a receiver to execute the above algorithm. 447 6. Reed-Solomon Codes Specification for the Erasure Channel 449 Reed-Solomon (RS) codes are linear block codes. They also belong to 450 the class of MDS codes. A [n,k]-RS code encodes a sequence of k 451 source elements defined over a finite field GF(q) into a sequence of 452 n encoding elements, where n is upper bounded by q - 1. The 453 implementation described in this document is based on a generator 454 matrix built from a Vandermonde matrix put into systematic form. 456 Section 6.1 to Section 6.3 specify the [n,k]-RS codes when applied to 457 m-bit elements, and Section 6.4 the use of [n,k]-RS codes when 458 applied to symbols composed of several m-bit elements, which is the 459 target of this specification. 461 6.1. Finite Field 463 A finite field GF(q) is defined as a finite set of q elements which 464 has a structure of field. It contains necessarily q = p^^m elements, 465 where p is a prime number. With packet erasure channels, p is always 466 set to 2. The elements of the field GF(2^^m) can be represented by 467 polynomials with binary coefficients (i.e. over GF(2)) of degree less 468 than m. The polynomials can be associated to binary vectors of 469 length m. For example, the vector (11001) represents the polynomial 470 1 + x + x^^4. This representation is often called polynomial 471 representation. The addition between two elements is defined as the 472 addition of binary polynomials in GF(2) and the multiplication is the 473 multiplication modulo a given irreducible polynomial over GF(2) of 474 degree m with coefficients in GF(2). Note that all the roots of this 475 polynomial are in GF(2^^m) but not in GF(2). 477 A finite field GF(2^^m) is completely characterized by the 478 irreducible polynomial. The following polynomials are chosen to 479 represent the field GF(2^^m), for m varying from 2 to 16: 481 m = 2, "111" (1+x+x^^2) 483 m = 3, "1101", (1+x+x^^3) 485 m = 4, "11001", (1+x+x^^4) 487 m = 5, "101001", (1+x^^2+x^^5) 489 m = 6, "1100001", (1+x+x^^6) 491 m = 7, "10010001", (1+x^^3+x^^7) 493 m = 8, "101110001", (1+x^^2+x^^3+x^^4+x^^8) 494 m = 9, "1000100001", (1+x^^4+x^^9) 496 m = 10, "10010000001", (1+x^^3+x^^10) 498 m = 11, "101000000001", (1+x^^2+x^^11) 500 m = 12, "1100101000001", (1+x+x^^4+x^^6+x^^12) 502 m = 13, "11011000000001", (1+x+x^^3+x^^4+x^^13) 504 m = 14, "110000100010001", (1+x+x^^6+x^^10+x^^14) 506 m = 15, "1100000000000001", (1+x+x^^15) 508 m = 16, "11010000000010001", (1+x+x^^3+x^^12+x^^16) 510 In order to facilitate the implementation, these polynomials are also 511 primitive. This means that any element of GF(2^^m) can be expressed 512 as a power of a given root of this polynomial. These polynomials are 513 also chosen so that they contain the minimum number of monomials. 515 6.2. Reed-Solomon Encoding Algorithm 517 6.2.1. Encoding Principles 519 Let s = (s_0, ..., s_{k-1}) be a source vector of k elements over 520 GF(2^^m). Let e = (e_0, ..., e_{n-1}) be the corresponding encoding 521 vector of n elements over GF(2^^m). Being a linear code, encoding is 522 performed by multiplying the source vector by a generator matrix, GM, 523 of k rows and n columns over GF(2^^m). Thus: 525 e = s * GM. 527 The definition of the generator matrix completely characterizes the 528 RS code. 530 Let us consider that: n = 2^^m - 1 and: 0 < k <= n. Let us denote 531 alpha the primitive element of GF(2^^m) chosen in the list of 532 Section 6.1 for the corresponding value of m. Let us consider a 533 Vandermonde matrix of k rows and n columns, denoted by V_{k,n}, and 534 built as follows: the {i, j} entry of V_{k,n} is v_{i,j} = 535 alpha^^(i*j), where 0 <= i <= k - 1 and 0 <= j <= n - 1. This matrix 536 generates a MDS code. However, this MDS code is not systematic, 537 which is a problem for many networking applications. To obtain a 538 systematic matrix (and code), the simplest solution consists in 539 considering the matrix V_{k,k} formed by the first k columns of 540 V_{k,n}, then to invert it and to multiply this inverse by V_{k,n}. 541 Clearly, the product V_{k,k}^^-1 * V_{k,n} contains the identity 542 matrix I_k on its first k columns, meaning that the first k encoding 543 elements are equal to source elements. Besides the associated code 544 keeps the MDS property. 546 Therefore, the generator matrix of the code considered in this 547 document is: 549 GM = (V_{k,k}^^-1) * V_{k,n} 551 Note that, in practice, the [n,k]-RS code can be shortened to a 552 [n',k]-RS code, where k <= n' < n, by considering the sub-matrix 553 formed by the n' first columns of GM. 555 6.2.2. Encoding Complexity 557 Encoding can be performed by first pre-computing GM and by 558 multiplying the source vector (k elements) by GM (k rows and n 559 columns). The complexity of the pre-computation of the generator 560 matrix can be estimated as the complexity of the multiplication of 561 the inverse of a Vandermonde matrix by n-k vectors (i.e. the last n-k 562 columns of V_{k,n}). Since the complexity of the inverse of a k*k- 563 Vandermonde matrix by a vector is O(k * log^^2(k)), the generator 564 matrix can be computed in 0((n-k)* k * log^^2(k)) operations. When 565 the genarator matrix is pre-computed, the encoding needs k operations 566 per repair element (vector-matrix multiplication). 568 Encoding can also be performed by first computing the product s * 569 V_{k,k}^^-1 and then by multiplying the result with V_{k,n}. The 570 multiplication by the inverse of a square Vandermonde matrix is known 571 as the interpolation problem and its complexity is O(k * log^^2 (k)). 572 The multiplication by a Vandermonde matrix, known as the multipoint 573 evaluation problem, requires O((n-k) * log(k)) by using Fast Fourier 574 Transform, as explained in [11]. The total complexity of this 575 encoding algorithm is then O((k/(n-k)) * log^^2(k) + log(k)) 576 operations per repair element. 578 6.3. Reed-Solomon Decoding Algorithm 580 6.3.1. Decoding Principles 582 The Reed-Solomon decoding algorithm for the erasure channel allows 583 the recovery of the k source elements from any set of k received 584 elements. It is based on the fundamental property of the generator 585 matrix which is such that any k*k-submatrix is invertible (see [5]). 586 The first step of the decoding consists in extracting the k*k 587 submatrix of the generator matrix obtained by considering the columns 588 corresponding to the received elements. Indeed, since any encoding 589 element is obtained by multiplying the source vector by one column of 590 the generator matrix, the received vector of k encoding elements can 591 be considered as the result of the multiplication of the source 592 vector by a k*k submatrix of the generator matrix. Since this 593 submatrix is invertible, the second step of the algorithm is to 594 invert this matrix and to multiply the received vector by the 595 obtained matrix to recover the source vector. 597 6.3.2. Decoding Complexity 599 The decoding algorithm described previously includes the matrix 600 inversion and the vector-matrix multiplication. With the classical 601 Gauss-Jordan algorithm, the matrix inversion requires O(k^^3) 602 operations and the vector-matrix multiplication is performed in 603 O(k^^2) operations. 605 This complexity can be improved by considering that the received 606 submatrix of GM is the product between the inverse of a Vandermonde 607 matrix (V_(k,k)^^-1) and another Vandermonde matrix (denoted by V' 608 which is a submatrix of V_(k,n)). The decoding can be done by 609 multiplying the received vector by V'^^-1 (interpolation problem with 610 complexity O( k * log^^2(k)) ) then by V_{k,k} (multipoint evaluation 611 with complexity O(k * log(k))). The global decoding complexity is 612 then O(log^^2(k)) operations per source element. 614 6.4. Implementation for the Packet Erasure Channel 616 In a packet erasure channel, each packet (and symbol(s) since packets 617 contain G >= 1 symbols) is either received correctly or erased. The 618 location of the erased symbols in the sequence of symbols must be 619 known. The following specification describes the use of Reed-Solomon 620 codes for generating redundant symbols from k source symbols and to 621 recover the source symbols from any set of k received symbols. 623 The k source symbols of a source block are assumed to be composed of 624 S m-bit elements. Each m-bit element is associated to an element of 625 the finite field GF(2^^m) through the polynomial representation 626 (Section 6.1). If some of the source symbols contain less than S 627 elements, they are virtually padded with zero elements (it can be the 628 case for the last symbol of the last block of the object). 630 The encoding process produces n-k repair symbols of size S m-bit 631 elements, the k source symbols being also part of the n encoding 632 symbols (Figure 4). These repair symbols are created m-bit element 633 per m-bit element. More specifically, the j-th source vector is 634 composed of the j-th element of each of the source symbols. 635 Similarly, the j-th encoding vector is composed of the j-th element 636 of each encoding symbol. 638 ------------ --------------- ------------------- 639 0 | | | | | | | | | | | | 640 | | | | | * | generator | = | | | | | 641 | | | | | | matrix | | | | | | 642 | | | | | | GM | | | | | | 643 source |--------------| | | |---------------------| 644 vector | | | | | | | --------------- ->| | | | | | | 645 j |--------------| / |---------------------| 646 | | | | | / | | | | | 647 | | | | | encoding | | | | | 648 | | | | | vector | | | | | 649 | | | | | j | | | | | 650 | | | | | | | | | | 651 S-1 | | | | | | | | | | 652 ------------ ------------------- 653 k source symbols n encoding symbols 654 (source + repair) 656 Figure 4: Packet encoding scheme 658 An asset of this scheme is that the loss of some encoding symbols 659 produces the same erasure pattern for each of the S encoding vectors. 660 It follows that the matrix inversion must be done only once and will 661 be used by all the S encoding vectors. For large S, this matrix 662 inversion cost becomes negligible in front of the S matrix-vector 663 multiplications. 665 Another asset is that the n-k repair symbols can be produced on 666 demand. For instance, a sender can start by producing a limited 667 number of repair symbols and later on, depending on the observed 668 erasures on the channel, decide to produce additional repair symbols, 669 up to the n-k upper limit. Indeed, to produce the repair symbol e_j, 670 where k <= j < n, it is sufficient to multiply the S source vectors 671 with column j of GM. 673 7. Security Considerations 675 The security considerations for this document are the same as that of 676 [2]. 678 8. IANA Considerations 680 Values of FEC Encoding IDs and FEC Instance IDs are subject to IANA 681 registration. For general guidelines on IANA considerations as they 682 apply to this document, see [2]. This document assigns the Fully- 683 Specified FEC Encoding ID XX under the ietf:rmt:fec:encoding name- 684 space to "Reed-Solomon Codes". 686 9. Acknowledgments 688 The authors want to thank Luigi Rizzo for comments on the subject and 689 for the design of the reference Reed-Solomon codec. 691 10. References 693 10.1. Normative References 695 [1] Bradner, S., "Key words for use in RFCs to Indicate Requirement 696 Levels", RFC 2119. 698 [2] Watson, M., Luby, M., and L. Vicisano, "Forward Error Correction 699 (FEC) Building Block", draft-ietf-rmt-fec-bb-revised-03.txt 700 (work in progress), January 2006. 702 [3] Luby, M., Vicisano, L., Gemmell, J., Rizzo, L., Handley, M., and 703 J. Crowcroft, "The Use of Forward Error Correction (FEC) in 704 Reliable Multicast", RFC 3453, December 2002. 706 10.2. Informative References 708 [4] Rizzo, L., "Reed-Solomon FEC codec (revised version of July 709 2nd, 1998), available at 710 http://info.iet.unipi.it/~luigi/vdm98/vdm980702.tgz", 711 July 1998. 713 [5] Mac Williams, F. and N. Sloane, "The Theory of Error Correcting 714 Codes", North Holland, 1977 . 716 [6] Luby, M., Shokrollahi, A., Watson, M., and T. Stockhammer, 717 "Raptor Forward Error Correction Scheme", Internet 718 Draft draft-ietf-rmt-bb-fec-raptor-object-03 (work in 719 progress), October 2005. 721 [7] Roca, V., Neumann, C., and D. Furodet, "Low Density Parity 722 Check (LDPC) Forward Error Correction", 723 draft-ietf-rmt-bb-fec-ldpc-01.txt (work in progress), 724 March 2006. 726 [8] Luby, M., Watson, M., and L. Vicisano, "Asynchronous Layered 727 Coding (ALC) Protocol Instantiation", 728 draft-ietf-rmt-pi-alc-revised-03.txt (work in progress), 729 April 2006. 731 [9] Adamson, B., Bormann, C., Handley, M., and J. Macker, 732 "Negative-acknowledgment (NACK)-Oriented Reliable Multicast 733 (NORM) Protocol", draft-ietf-rmt-pi-norm-revised-01.txt (work 734 in progress), March 2006. 736 [10] Paila, T., Walsh, R., Luby, M., Lehtonen, R., and V. Roca, 737 "FLUTE - File Delivery over Unidirectional Transport", 738 draft-ietf-rmt-flute-revised-01.txt (work in progress), 740 January 2006. 742 [11] Gohberg, I. and V. Olshevsky, "Fast algorithms with 743 preprocessing for matrix-vector multiplication problems", 744 Journal of Complexity, pp. 411-427, vol. 10, 1994 . 746 Authors' Addresses 748 Jerome Lacan 749 ENSICA/LAAS-CNRS 750 1, place Emile Blouin 751 Toulouse 31056 752 France 754 Email: jerome.lacan@ensica.fr 755 URI: http://dmi.ensica.fr/auteur.php3?id_auteur=5 757 Vincent Roca 758 INRIA 759 655, av. de l'Europe 760 Zirst; Montbonnot 761 ST ISMIER cedex 38334 762 France 764 Email: vincent.roca@inrialpes.fr 765 URI: http://planete.inrialpes.fr/~roca/ 767 Jani Peltotalo 768 Tampere University of Technology 769 P.O. Box 553 (Korkeakoulunkatu 1) 770 Tampere FIN-33101 771 Finland 773 Email: jani.peltotalo@tut.fi 774 URI: http://atm.tut.fi/mad 776 Sami Peltotalo 777 Tampere University of Technology 778 P.O. Box 553 (Korkeakoulunkatu 1) 779 Tampere FIN-33101 780 Finland 782 Email: sami.peltotalo@tut.fi 783 URI: http://atm.tut.fi/mad 785 Intellectual Property Statement 787 The IETF takes no position regarding the validity or scope of any 788 Intellectual Property Rights or other rights that might be claimed to 789 pertain to the implementation or use of the technology described in 790 this document or the extent to which any license under such rights 791 might or might not be available; nor does it represent that it has 792 made any independent effort to identify any such rights. Information 793 on the procedures with respect to rights in RFC documents can be 794 found in BCP 78 and BCP 79. 796 Copies of IPR disclosures made to the IETF Secretariat and any 797 assurances of licenses to be made available, or the result of an 798 attempt made to obtain a general license or permission for the use of 799 such proprietary rights by implementers or users of this 800 specification can be obtained from the IETF on-line IPR repository at 801 http://www.ietf.org/ipr. 803 The IETF invites any interested party to bring to its attention any 804 copyrights, patents or patent applications, or other proprietary 805 rights that may cover technology that may be required to implement 806 this standard. Please address the information to the IETF at 807 ietf-ipr@ietf.org. 809 Disclaimer of Validity 811 This document and the information contained herein are provided on an 812 "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS 813 OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET 814 ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, 815 INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE 816 INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED 817 WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 819 Copyright Statement 821 Copyright (C) The Internet Society (2006). This document is subject 822 to the rights, licenses and restrictions contained in BCP 78, and 823 except as set forth therein, the authors retain all their rights. 825 Acknowledgment 827 Funding for the RFC Editor function is currently provided by the 828 Internet Society.