The encoding process produces n-k repair symbols of size S m-bit elements, the k source symbols being also part of the n encoding symbols (Figure4 (Packet encoding scheme)). The location of the erased symbols in the sequence of symbols must be known. Scheme-Specific Elements 4.2.4. For instance, when m = 8 (default): max1_B = 2^^8 - 1 = 255 Additionally, a codec MAY impose other limitations on the maximum block size.

TOC 4.2.4.Encoding Format This section shows two possible encoding formats of the above FEC OTI. For example, the vector (11001) represents the polynomial 1 + x + x^^4. The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html. This document assigns the Fully-Specified FEC Encoding ID XX under the ietf:rmt:fec:encoding name-space to "Reed-Solomon Codes".

n denotes the encoding block length, i.e. Procedures 5.1. E denotes the encoding symbol length in bytes. Stockhammer, “Raptor Forward Error Correction Scheme,” Internet Draftdraft-ietf-rmt-bb-fec-raptor-object-03 (work in progress), October2005. [7] Roca, V., Neumann, C., and D.

Table of Contents 1. Informative References § Authors' Addresses § Intellectual Property and Copyright Statements TOC 1.Introduction The use of Forward Error Correction (FEC) codes is a classical solution to improve the reliability of multicast Another solution consists in fragmenting large objects into smaller objects, each of them complying with the above limits. TOC 9.Acknowledgments The authors want to thank Luigi Rizzo for comments on the subject and for the design of the reference Reed-Solomon codec.

Additionally, it uses the following definitions: Source symbol: unit of data used during the encoding process. Definitions Notations and Abbreviations 3.1. m defines the length of the elements in the finite field, in bits. There are a maximum of 2^^(32-m) blocks per object.

de l'Europe Zirst; Montbonnot ST ISMIER cedex 38334 France Email: [email protected] URI: http://planete.inrialpes.fr/~roca/ Jani Peltotalo Tampere University of Technology P.O. a^^-1 denotes the inverse of a. TOC 6.3.2.Decoding Complexity The decoding algorithm described previously includes the matrix inversion and the vector-matrix multiplication. When m = 8, then S and E are equal.

G denotes the number of encoding symbols per group, i.e. The IETF invites any interested party to bring to its attention any copyrights, patents or patent applications, or other proprietary rights that may cover technology that may be required to implement Formats and Codes 4.1. This document is subject to the rights, licenses and restrictions contained in BCP78, and except as set forth therein, the authors retain all their rights.

Vicisano, “Forward Error Correction (FEC) Building Block,” draft-ietf-rmt-fec-bb-revised-03.txt (work in progress), January2006. [3] Luby, M., Vicisano, L., Gemmell, J., Rizzo, L., Handley, M., and J. Vicisano, “Asynchronous Layered Coding (ALC) Protocol Instantiation,” draft-ietf-rmt-pi-alc-revised-03.txt (work in progress), April2006. [9] Adamson, B., Bormann, C., Handley, M., and J. Stockhammer, “Raptor Forward Error Correction Scheme,” October2005.) and [7] (Roca, V., Neumann, C., and D. max_n denotes the maximum number of encoding symbols generated for any source block.

It is expressed as a floating point value. Macker, “Negative-acknowledgment (NACK)-Oriented Reliable Multicast (NORM) Protocol,” March2006.) protocols). 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 FEC Payload ID 4.2. Even if the encoding/decoding complexity is larger than that of [6] (Luby, M., Shokrollahi, A., Watson, M., and T.

Section5 (Procedures) explains how to derive the values of each of these elements. a^^b denotes a raised to the power b. When no G parameter is communicated to the decoder, then this latter MUST assume that G = 1. More specifically, the j-th source vector is composed of the j-th element of each of the source symbols.

Source Packet: a data packet containing only source symbols. However, this MDS code is not systematic, which is a problem for many networking applications. Furodet, “Low Density Parity Check (LDPC) Forward Error Correction,” March2006.), this family of codes is very useful. TOC 6.Reed-Solomon Codes Specification for the Erasure Channel Reed-Solomon (RS) codes are linear block codes.

Symbols (max_n) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure3: EXT_FTI Header Format TOC 4.2.4.2.Using the FDT Instance (FLUTE specific) When it is desired that the FEC OTI be carried in the FDT Instance of a For larger objects, another FEC scheme, with a larger Source Block Number field in the FEC Payload ID, could be defined. Abstract This document describes a Fully-Specified FEC scheme for the Reed-Solomon forward error correction code and its application to the reliable delivery of data objects on the packet erasure channel. Output: max_n: Maximum number of encoding symbols generated for any source block n: Number of encoding symbols generated for this source block Algorithm: max_n = floor(B / rate); if (max_n >

Stockhammer, “Raptor Forward Error Correction Scheme,” October2005.) or [7] (Roca, V., Neumann, C., and D. TOC Authors' Addresses Jerome Lacan ENSICA/LAAS-CNRS 1, place Emile Blouin Toulouse 31056 France Email: [email protected] URI: http://dmi.ensica.fr/auteur.php3?id_auteur=5 Vincent Roca INRIA 655, av. There MUST be exactly one FEC Payload ID per source or repair packet. The multiplication by a Vandermonde matrix, known as the multipoint evaluation problem, requires O((n-k) * log(k)) by using Fast Fourier Transform, as explained in [11] (Gohberg, I.

Finite Field 6.2. Copyright Statement Copyright © The Internet Society (2006). Therefore, the generator matrix of the code considered in this document is: GM = (V_{k,k}^^-1) * V_{k,n} Note that, in practice, the [n,k]-RS code can be shortened to a [n',k]-RS code, Roca INRIA J.

Vicisano, “Forward Error Correction (FEC) Building Block,” January2006.) document describes a general framework to use FEC in Content Delivery Protocols (CDP). TOC Reliable Multicast TransportJ. If some of the source symbols contain less than S elements, they are virtually padded with zero elements (it can be the case for the last symbol of the last block Therefore the receiver part of the "n-algorithm" is not necessary from the Reed-Solomon decoder point of view.

Encoding-Symbol-Length (E): a non-negative integer indicating the length of each encoding symbol in bytes.