RMT                                                         J. Peltotalo
Internet-Draft                                              S. Peltotalo
Expires: December 13, 2004              Tampere University of Technology
                                                                 V. Roca
                                                       INRIA Rhone-Alpes
                                                           June 14, 2004



  Simple XOR, Reed-Solomon, and Parity Check Matrix-based FEC Schemes
             draft-peltotalo-rmt-bb-fec-supp-xor-pcm-rs-00


Status of this Memo


   This document is an Internet-Draft and is in full conformance with
   all provisions of Section 10 of RFC2026.


   Internet-Drafts are working documents of the Internet Engineering
   Task Force (IETF), its areas, and its working groups. Note that other
   groups may also distribute working documents as Internet-Drafts.


   Internet-Drafts are draft documents valid for a maximum of six months
   and may be updated, replaced, or obsoleted by other documents at any
   time. It is inappropriate to use Internet-Drafts as reference
   material or to cite them other than as "work in progress."


   The list of current Internet-Drafts can be accessed at http://
   www.ietf.org/ietf/1id-abstracts.txt.


   The list of Internet-Draft Shadow Directories can be accessed at
   http://www.ietf.org/shadow.html.


   This Internet-Draft will expire on December 13, 2004.


Copyright Notice


   Copyright (C) The Internet Society (2004). All Rights Reserved.


Abstract


   This document introduces several Forward Error Correction (FEC)
   schemes that supplement the FEC schemes described in RFC 3452 [5] and
   RFC 3695 [7].


   More specifically it describes the Fully-Specified FEC scheme
   corresponding to FEC Encoding ID 2, reserved to simple XOR FEC
   scheme, and the Under-Specified FEC scheme corresponding to FEC
   Encoding ID 132, reserved to parity check matrix-based FEC scheme.
   This document also specifies the FEC Instance IDs 0 and 1, scoped by
   the FEC Encoding ID 129 and reserved to Reed-Solomon FEC codes. It




Peltotalo, et al.      Expires December 13, 2004                [Page 1]
Internet-Draft    Simple XOR, Reed-Solomon, and Parity Check Matrix-based FEC Schemes                                            June 2004



   also specifies the FEC Instance ID 0, scoped by the FEC Encoding ID
   132 and reserved to LDGM-Staircase codes. Finally this document
   specifies two algorithms that MAY be used with all block FEC codes.


Table of Contents


   1.    Introduction . . . . . . . . . . . . . . . . . . . . . . . .  3
   1.1   Simple XOR FEC Scheme  . . . . . . . . . . . . . . . . . . .  3
   1.2   Reed-Solomon FEC Schemes . . . . . . . . . . . . . . . . . .  4
   1.3   Parity Check Matrix-based FEC Scheme . . . . . . . . . . . .  4
   2.    Conventions Used in This Document  . . . . . . . . . . . . .  6
   3.    Packet Header Fields . . . . . . . . . . . . . . . . . . . .  7
   3.1   FEC Payload ID for FEC Encoding IDs 2 and 132  . . . . . . .  7
   3.2   Simple XOR FEC Scheme  . . . . . . . . . . . . . . . . . . .  7
   3.3   Parity Check Matrix-based FEC Scheme . . . . . . . . . . . .  8
   3.4   Use of EXT_FTI to Deliver FEC Object Transmission
         Information  . . . . . . . . . . . . . . . . . . . . . . . .  9
   3.4.1 General EXT_FTI Format . . . . . . . . . . . . . . . . . . . 10
   3.4.2 FEC Encoding ID 2 Specific Format for EXT_FTI  . . . . . . . 11
   3.4.3 FEC Encoding ID 132 Specific Format for EXT_FTI  . . . . . . 11
   4.    Use of the Reed-Solomon FEC Codes with Well Known Block
         Structure  . . . . . . . . . . . . . . . . . . . . . . . . . 14
   5.    Use of the Reed-Solomon FEC Codes with Unknown Block
         Structure  . . . . . . . . . . . . . . . . . . . . . . . . . 16
   6.    Use of the FEC Encoding ID 132/FEC Instance ID 0 for
         LDGM-Staircase Codes . . . . . . . . . . . . . . . . . . . . 18
   7.    Algorithm for Computing the Source Block Structure . . . . . 19
   8.    Algorithm for Computing the Number of Encoding Symbols
         of a Block . . . . . . . . . . . . . . . . . . . . . . . . . 21
   9.    Security Considerations  . . . . . . . . . . . . . . . . . . 23
   10.   IANA Considerations  . . . . . . . . . . . . . . . . . . . . 24
   11.   Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 25
         Normative References . . . . . . . . . . . . . . . . . . . . 26
         Informative References . . . . . . . . . . . . . . . . . . . 27
         Authors' Addresses . . . . . . . . . . . . . . . . . . . . . 27
         Intellectual Property and Copyright Statements . . . . . . . 29
















Peltotalo, et al.      Expires December 13, 2004                [Page 2]
Internet-Draft    Simple XOR, Reed-Solomon, and Parity Check Matrix-based FEC Schemes                                            June 2004



1. Introduction


   This document describes two new Forward Error Correction (FEC)
   schemes corresponding to FEC Encoding IDs 2 and 132, which supplement
   the FEC schemes corresponding to FEC Encoding IDs 128 and 129
   described in the FEC Building Block [5].


   The two new FEC Encoding IDs 2 and 132 are described in Section 3,
   and this supplements Section 5 of the FEC Building Block [5]. Section
   1.1 of this document describes the Fully-Specified FEC scheme
   corresponding to the FEC Encoding ID 2. FEC scheme corresponding to
   the FEC Encoding ID 132 is Under-Specified.


   Sections 4 and 5 of this document specify the use of Reed-Solomon FEC
   codes, and Section 6 specifies the use of LDGM-Staircase FEC codes.
   This document also discusses the use of block FEC codes in general,
   and specifies two mathematical algorithms needed when using block FEC
   codes. First, source blocking algorithm, is specified in Section 7,
   and second, "n-algorithm", is specified in Section 8.


   This document inherits the context, language, declarations and
   restrictions of the FEC Building Block [5]. This document also uses
   the terminology of the companion document [6], which describes the
   use of FEC codes within the context of reliable IP multicast
   transport and provides an introduction to some commonly used FEC
   codes.


   Building blocks are defined in RFC 3048 [2]. This document follows
   the general guidelines provided in RFC 3269 [3].


1.1 Simple XOR FEC Scheme


   There are some very simple codes that are effective for repairing
   packet loss under very low loss conditions. The Simple XOR FEC scheme
   is designed to provide protection from a single loss by partitioning
   a source block into fixed size source symbols and then adding a
   redundant symbol that is the XOR sum of all the source symbols. This
   is (k+1, k) code, where k is the number of source symbols.


   For example if the source block consists of four source symbols
   (source symbol IDs from 0 to 3) that have values a, b, c and d, then
   the value of the redundant symbol is e = XOR(a,b,c,d). Then, the
   packets carrying these symbols look like:


   (0: a), (1: b), (2: c), (3: d), (4: e).


   In this example, any single source symbol of the source block can be
   recovered as the XOR sum of all the other symbols. For example, if




Peltotalo, et al.      Expires December 13, 2004                [Page 3]
Internet-Draft    Simple XOR, Reed-Solomon, and Parity Check Matrix-based FEC Schemes                                            June 2004



   packets


   (0: a), (1: b), (3: d), (4: e)


   are received then the missing source symbol value with source symbol
   ID = 2 can be recovered by computing c = XOR(a,b,d,e).


   In this context the source block length determines the percentage of
   FEC data added to the stream. If the source block length value is low
   there is naturally more FEC symbols than is when the value is high.
   (E.g. source blocks of length one source symbol result in 100%
   redundant parity data, or a 1:1 ratio; and source blocks of length
   100 source symbols result in 1% redundant parity data, or a 100:1
   ratio.)


1.2 Reed-Solomon FEC Schemes


   This document reserves two FEC Instance IDs, 0 and 1, for the
   Under-Specified FEC Encoding ID 129 name-space. Both of these FEC
   Instance IDs are for Reed-Solomon codes built on Vandermonde matrices
   [9]. A reference implementation for such codes can be obtained from
   the author of [9]. These FEC Instance IDs share the same FEC Payload
   ID and FEC Object Transmission Information extension (EXT_FTI)
   formats specified respectively in the FEC Building Block [5] and
   FLUTE [8] documents.


   Yet they differ in the way the source block structure is computed:
   FEC Instance ID 0 mandates the use of the algorithm defined in
   Section 7, while FEC Instance ID 1 leaves to the source the
   responsibility to define an appropriate source block structure.


   Sections 4 and 5 define these FEC Instance IDs with more details. The
   use of the 129/0 FEC scheme (rather than the 129/1 FEC scheme) is
   RECOMMENDED for ALC [4](and in particular FLUTE [8]) sessions using
   Reed-Solomon FEC. NORM [10] sessions, using Reed-Solomon FEC, MAY use
   either 129/0 or 129/1 FEC schemes and this decision is outside the
   scope of this document.


1.3 Parity Check Matrix-based FEC Scheme


   RFC 3453 [6] introduces large block FEC codes as an alternative to
   small block FEC codes like Reed-Solomon. The main advantage of such
   large block codes is the possibility to operate efficiently on source
   blocks of several tens of thousands (or more) source symbols of size.


   The present document introduces the Under-Specified FEC Encoding ID
   132 to enable the use of a subset of large block FEC codes. More
   specifically we consider here the large block FEC codes that rely on




Peltotalo, et al.      Expires December 13, 2004                [Page 4]
Internet-Draft    Simple XOR, Reed-Solomon, and Parity Check Matrix-based FEC Schemes                                            June 2004



   a dedicated matrix, named a "Parity Check Matrix", at the encoding
   and decoding ends. The parity check matrix defines relationships (or
   constraints) between the various encoding symbols (i.e. source
   symbols and redundant symbols), that are later used by the decoder to
   reconstruct the original k source symbols if some of them are
   missing. These codes are systematic, in the sense that the resulting
   encoding symbols, for delivery, include all the source symbols as
   well as redundant symbols.


   The LDPC (Low Density Parity Check) codes and the LDGM (Low Density
   Generator Matrix) variants [11] fall into this category, but other
   codes, existing or forthcoming, may also fall in this category.


   Since the encoder and decoder must operate on the same parity check
   matrix, some information must be communicated between them, as part
   of the FEC Object Transmission Information. Its content and the
   associated EXT_FTI are fully described in Sections 3.3 and 3.4
   respectively.


   This document also reserves the FEC Instance ID value 0 for the
   LDGM-Staircase codes [11], also called LDPC-Staircase in [13]. A
   publicly available reference implementation of these codes is
   available and distributed under a GNU LGPL license [12].





























Peltotalo, et al.      Expires December 13, 2004                [Page 5]
Internet-Draft    Simple XOR, Reed-Solomon, and Parity Check Matrix-based FEC Schemes                                            June 2004



2. Conventions Used in This Document


   The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
   "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
   document are to be interpreted as described in RFC 2119 [1].


   k: The number of source symbols per block (Source Block Length).


   n: The number of encoding symbols per block (Encoding Block Length).











































Peltotalo, et al.      Expires December 13, 2004                [Page 6]
Internet-Draft    Simple XOR, Reed-Solomon, and Parity Check Matrix-based FEC Schemes                                            June 2004



3. Packet Header Fields


   This section specifies FEC Encoding IDs 2 and 132 and the associated
   FEC Payload ID formats and the specific information in the
   corresponding FEC Object Transmission Information. The FEC scheme
   associated with FEC Encoding ID 2 is Fully-Specified, and the FEC
   scheme associated with FEC Encoding ID 132 is Under-Specified.


   FEC Encoding IDs 2 and 132 have the same FEC Payload ID format, which
   is described in Section 3.1. The FEC Object Transmission Information
   for FEC Encoding IDs 2 and 132 is described in Sections 3.2, 3.3 and
   3.4.


3.1 FEC Payload ID for FEC Encoding IDs 2 and 132


   FEC Encoding IDs 2 and 132 have the same FEC Payload ID format as
   that of FEC Encoding ID 128, which is specified in RFC 3452 [5].


   The FEC Payload ID for FEC Encoding IDs 2 and 132 is composed of the
   Source Block Number and the Encoding Symbol ID:


    0                   1                   2                   3
    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
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                     Source Block Number                       |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                     Encoding Symbol ID                        |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+


        Figure 1: FEC Payload ID for FEC Encoding IDs 2 and 132


   The Source Block Number identifies from which source block of the
   object the encoding symbol in the payload is generated. These blocks
   are numbered consecutively from 0 to N-1, where N is the number of
   source blocks in the object.


   The Encoding Symbol ID identifies which specific encoding symbol
   generated from the source block is carried in the packet payload.
   Each encoding symbol is either an original source symbol or a
   redundant symbol generated by the encoder.


3.2 Simple XOR FEC Scheme


   FEC Encoding ID 2 is reserved for the Simple XOR FEC scheme that is
   described in this section and in Section 1.1. This is a
   Fully-Specified FEC scheme that is primary intended to be used to
   protect against small transfer errors.





Peltotalo, et al.      Expires December 13, 2004                [Page 7]
Internet-Draft    Simple XOR, Reed-Solomon, and Parity Check Matrix-based FEC Schemes                                            June 2004



   The FEC Payload ID format for FEC Encoding ID 2 is described in
   Section 3.1. The FEC Object Transmission Information has the
   following specific information:


   o  The FEC Encoding ID 2.


   o  The total length of the object in bytes.


   o  The maximum number of source symbols that can compose any source
      block (Maximum Source Block Length). This field is provided to
      allow receivers to compute the source block structure of the
      object.


   o  The length in bytes of encoding symbols, common to all source
      blocks.


   The FEC Encoding ID 2 requires that an algorithm is known to both
   senders and receivers for determining the size of all source blocks
   of the transport object. Section 7 describes the blocking algorithm
   that MUST be used for this purpose.


   With FEC Encoding ID 2 there MUST be at most one symbol per packet.


3.3 Parity Check Matrix-based FEC Scheme


   FEC Encoding ID 132 is reserved for the Parity Check Matrix-based FEC
   scheme that is described in this section. This is an Under-Specified
   FEC scheme that is primarily intended to be used to protect against
   normal transfer errors.


   The FEC Instance ID value of 0, under the scope of FEC Encoding ID
   132, is reserved for the LDGM-Staircase codes.


   The FEC Payload ID format for FEC Encoding ID 132 is described in
   Section 3.1. The FEC Object Transmission Information has the
   following specific information:


   o  The FEC Encoding ID 132.


   o  The FEC Instance ID to be used. 0 is reserved for LDGM-Staircase
      codes.


   o  The total length of the object in bytes.


   o  The maximum number of source symbols that can compose any source
      block (Maximum Source Block Length). This field is provided to
      allow receivers to compute the source block structure of the
      object.




Peltotalo, et al.      Expires December 13, 2004                [Page 8]
Internet-Draft    Simple XOR, Reed-Solomon, and Parity Check Matrix-based FEC Schemes                                            June 2004



   o  The maximum number of encoding symbols that can be generated for
      any source block. This field is provided to allow receivers to
      compute the number of encoding symbols of an encoding block.


   o  The length in bytes of encoding symbols, common to all source
      blocks.


   o  A FEC Instance ID-Specific Information that is used, along with
      other information (in particular the (k, n) parameters of a
      block), to create the parity check matrix. For instance, with FEC
      Instance ID 0 (LDGM-Staircase), this Specific Information, when
      specified, is the seed of the pseudo random number generator used
      during the creation of the matrix. Other FEC Instance IDs may have
      other requirements (e.g. the number of constraints a source symbol
      is implied in, in case of a regular parity check matrix, MAY be
      required too). How this field should be interpreted will be
      defined in each FEC Instance ID scoped by FEC Encoding ID 132.


   FEC Encoding ID 132 requires that an algorithm is known to both
   senders and receivers for determining the size of all source blocks
   of the transport object. Section 7 describes the blocking algorithm
   that MUST be used for this purpose. Using this algorithm is required
   even in case of a large block FEC code, since the codec may have
   practical limits on the maximum block size it can accept, or the
   environment where this codec runs may impose its own practical limits
   on the block size (e.g. due to limited available memory constraints).
   Therefore a large object MAY have to be split into several blocks.
   Yet it is expected that each source block remains an order of
   magnitude larger than when using small block codes.


   This specification also requires that the "n-algorithm" of Section 8
   MUST be used by the senders and the receivers to determine the n
   parameter (Number of Encoding Symbols) associated to each source
   block of size k (Number of source symbols for this block), as defined
   by the Blocking algorithm of Section 7.


3.4 Use of EXT_FTI to Deliver FEC Object Transmission Information


   As specified by Asynchronous Layered Coding (ALC) [4], the EXT_FTI
   header extension is intended to carry the FEC Object Transmission
   Information for an object in-band with the object's delivery session.
   The receiver MUST support the discovery of FEC Object Transmission
   Information using the EXT_FTI header for FEC Encoding IDs 2 and 132.
   Out-of-band communication of this information is also possible, but
   it is outside the scope of this document. It is left up to individual
   implementations to decide how frequently and in which packets the
   EXT_FTI header extension is included. In environments with higher
   packet loss rate, the EXT_FTI might need to be included more




Peltotalo, et al.      Expires December 13, 2004                [Page 9]
Internet-Draft    Simple XOR, Reed-Solomon, and Parity Check Matrix-based FEC Schemes                                            June 2004



   frequently in packets than in environments with low error
   probability.


   The ALC specification does not define the format or the processing of
   the EXT_FTI header extension. The following sections specify EXT_FTI
   when used with FEC Encoding IDs 2 and 132.


   The general format of the EXT_FTI header is same than is specified by
   FLUTE [8].


   For FEC Encoding IDs 2 and 132, the FEC Encoding ID (8 bits) is
   carried in the Codepoint field of the ALC header when ALC is used,
   and in the fec_id field of the NORM header when NORM is used.


3.4.1 General EXT_FTI Format


   The general EXT_FTI format specifies the structure and those
   attributes of FEC Object Transmission Information that are applicable
   to any FEC Encoding ID.


    0                   1                   2                   3
    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
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |   HET = 64    |     HEL       |                               |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+                               +
   |                       Transfer Length                         |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |   FEC Instance ID             | FEC Enc. ID Specific Format   |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+


                    Figure 2: General EXT_FTI Header


   Header Extension Type (HET), 8 bits:


   64 as defined in RFC 3450 [4].


   Header Extension Length (HEL), 8 bits:


   The length of the whole Header Extension field, expressed in
   multiples of 32-bit words. This length includes the FEC Encoding ID
   specific format part.


   Transfer Length, 48 bits:


   The length of the transport object in bytes.


   FEC Instance ID, optional, 16 bits:





Peltotalo, et al.      Expires December 13, 2004               [Page 10]
Internet-Draft    Simple XOR, Reed-Solomon, and Parity Check Matrix-based FEC Schemes                                            June 2004



   This field is used for carrying the FEC Instance ID. It is only
   present if the value of FEC Encoding ID is in the range of 128-255.
   When the value of FEC Encoding ID is in the range of 0-127, this
   field is set to 0.


   FEC Encoding ID Specific Format:


   Different FEC encoding schemes will need different sets of encoding
   parameters. Thus, the structure and length of this field depends on
   FEC Encoding ID. The next sections specify structure of this field
   for FEC Encoding IDs 2 and 132.


3.4.2 FEC Encoding ID 2 Specific Format for EXT_FTI


   FEC Encoding ID 2 is for Simple XOR FEC. The FEC Encoding ID specific
   format of EXT_FTI is defined as follows.


    0                   1                   2                   3
    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
                                   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      General EXT_FTI format       |    Encoding Symbol Length     |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                  Maximum Source Block Length                  |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+


        Figure 3: Specific EXT_FTI Header for FEC Encoding ID 2


   Encoding Symbol Length, 16 bits:


   Length of Encoding Symbol in bytes.


   All Encoding Symbols of a transport object MUST be equal to this
   length, with the optional exception of the last source symbol of the
   last source block (so that redundant padding is not mandatory in this
   last symbol). This last source symbol MUST be logically padded out
   with zeroes when another Encoding Symbol is computed based on this
   source symbol to ensure the same interpretation of this Encoding
   Symbol value by the sender and receiver. However, this padding need
   not be actually sent with the data of the last source symbol.


   Maximum Source Block Length, 32 bits:


   The maximum number of source symbols per source block.


3.4.3 FEC Encoding ID 132 Specific Format for EXT_FTI


   FEC Encoding ID 132 is for Parity Check Matrix-based FEC. The FEC
   Encoding ID specific format of EXT_FTI is defined as follows.




Peltotalo, et al.      Expires December 13, 2004               [Page 11]
Internet-Draft    Simple XOR, Reed-Solomon, and Parity Check Matrix-based FEC Schemes                                            June 2004



    0                   1                   2                   3
    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
                                   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      General EXT_FTI format       |    Encoding Symbol Length     |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                Maximum Source Block Length                    |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                Maximum Number of Encoding Symbols             |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   .    FEC Instance ID-Specific Information (of variable size)    .
   .                                                               .
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+


       Figure 4: Specific EXT_FTI Header for FEC Encoding ID 132


   Encoding Symbol Length, 16 bits:


   Length of Encoding Symbol in bytes.


   All Encoding Symbols of a transport object MUST be equal to this
   length, with the optional exception of the last source symbol of the
   last source block (so that redundant padding is not mandatory in this
   last symbol). This last source symbol MUST be logically padded out
   with zeroes when another Encoding Symbol is computed based on this
   source symbol to ensure the same interpretation of this Encoding
   Symbol value by the sender and receiver. However, this padding need
   not be actually sent with the data of the last source symbol.


   Maximum Source Block Length, 32 bits:


   The maximum number of source symbols per source block.


   Maximum Number of Encoding Symbols, 32 bits:


   Maximum number of Encoding symbols that can be generated for a source
   block.


   FEC Instance ID-Specific Information, variable size (of size >= 0,
   multiple of four bytes):


   When present, this FEC Instance ID-Specific Information is used,
   along with other information, to create the parity check matrix. The
   exact size (which MUST be multiple of four bytes) and content of this
   field MUST be specified for each FEC Instance ID scoped by FEC
   Encoding ID 132. For some FEC Instance IDs, this field MAY also be
   optional. Upon receiving an EXT_FTI, the HEL field indicates if this
   field is present, and its size, after subtracting 5 (i.e. the size of
   the fixed part of EXT_FTI) to its value. Section 6 specifies the




Peltotalo, et al.      Expires December 13, 2004               [Page 12]
Internet-Draft    Simple XOR, Reed-Solomon, and Parity Check Matrix-based FEC Schemes                                            June 2004



   content of this field in the particular case of FEC Encoding ID 0.



















































Peltotalo, et al.      Expires December 13, 2004               [Page 13]
Internet-Draft    Simple XOR, Reed-Solomon, and Parity Check Matrix-based FEC Schemes                                            June 2004



4. Use of the Reed-Solomon FEC Codes with Well Known Block Structure


   The FEC Instance ID value of 0, for the Under-Specified FEC Encoding
   ID 129 name-space, is reserved and used as described in this section
   for Reed-Solomon FEC codes built on Vandermonde matrices [9], and
   used with the algorithm defined in Section 7. A reference
   implementation for such codes can be obtained from the author of [9].
   With this FEC Instance ID the block structure is known to both ends
   once the FEC Object Transmission Information and the algorithm of
   Section 7 have been used.


   Since this scheme does not make any assumption on the presence or not
   of feedback information from the set of receivers, it can be used
   with both ALC (and in particular FLUTE) and NORM sessions.


   The FEC Object Transmission Information has the following specific
   information:


   o  The FEC Encoding ID 129.


   o  The FEC Instance ID 0.


   o  The total length of the object in bytes.


   o  The maximum number of source symbols that can compose any source
      block (Maximum Source Block Length). This field is provided to
      allow receivers to compute the source block structure of the
      object. This field is also used when computing the number of
      encoding symbols of an encoding block.


   o  The maximum number of encoding symbols that can be generated for
      any source block. This field is provided to allow receivers to
      compute the number of encoding symbols of an encoding block.


   o  The length in bytes of encoding symbols, common to all source
      blocks.


   The receiver MUST support delivery of FEC Object Transmission
   Information using the EXT_FTI header for Reed-Solomon 129/0 FEC
   scheme. It is left up to individual implementations to decide how
   frequently and in which packets the EXT_FTI header extension is
   included. Out-of-band communication of this information is also
   possible, but it is outside the scope of this document.


   The format of the EXT_FTI header is same as is specified by FLUTE [8]
   for FEC Encoding ID 129.


   The FEC Encoding ID (8 bits) is carried in the Codepoint field of the




Peltotalo, et al.      Expires December 13, 2004               [Page 14]
Internet-Draft    Simple XOR, Reed-Solomon, and Parity Check Matrix-based FEC Schemes                                            June 2004



   ALC header when ALC is used, and in the fec_id field of the NORM
   header when NORM is used.


   With Reed-Solomon 129/0 FEC scheme there MUST be at most one symbol
   per packet.


   When using Reed-Solomon (n, k) FEC codes, the values for k and n have
   to be known for each block. These values are required both during the
   encoding and decoding phases.


   This specification requires that a sender MUST use both the algorithm
   for computing the source block structure described in Section 7 and
   the n-algorithm described in Section 8. The same Maximum Source Block
   Length (B) input value MUST be used by both algorithms, and the
   output value from the source blocking algorithm for k, for a given
   block, MUST be used as the input value for k in the n-algorithm for
   computing the associated n value.


   With FEC Encoding ID 129, the FEC Payload ID of each data packet
   contains a Source Block Length field for the source block
   corresponding to the encoding symbol the packet carries. This Source
   Block Length field MUST contain the actual source block length (k)
   calculated by the source blocking algorithm. The output max_n value
   of the n-algorithm MUST be used for the Maximum Number of Encoding
   Symbols field of the EXT_FTI (this max_n value does not depend on the
   k input parameter of the n-algorithm, and will be the same for all
   executions of the n-algorithm for the various blocks). The Maximum
   Source Block Length field MUST contain the input value specified for
   both algorithms.


   The receivers determine the k value for a given block either from the
   FEC Payload ID's Source Block Length field of an encoding symbol
   belonging to this block, or by computing it using the source blocking
   algorithm. In the latter case the Maximum Source Block Length is
   extracted from the EXT_FTI header field. The n value for this block
   is then determined by the n-algorithm, with the k value determined
   previously, and the  Maximum Source Block Length / Maximum Number of
   Encoding Symbols values extracted from the EXT_FTI header fields.














Peltotalo, et al.      Expires December 13, 2004               [Page 15]
Internet-Draft    Simple XOR, Reed-Solomon, and Parity Check Matrix-based FEC Schemes                                            June 2004



5. Use of the Reed-Solomon FEC Codes with Unknown Block Structure


   The FEC Instance ID value of 1 for the Under-Specified FEC Encoding
   ID 129 name-space, is reserved and used as described in this section
   for Reed-Solomon FEC codes built on Vandermonde matrices [9], and
   used with unknown block structure. A reference implementation for
   such codes can be obtained from the author of [9]. With this FEC
   Instance ID the block structure is communicated to the receiver(s)
   progressively, thanks to the Source Block Length field of the FEC
   Payload ID which specifies the size of this block. The block
   structure cannot be known until one packet for each block has been
   received.


   Motivation for this FEC mode is that sender can adapt to loss rates.
   This is done by reducing the number of source symbols (k) in order to
   increase the number of parity symbols (n-k), so that the number of
   encoding symbols (n) is kept the same. It is therefore well suited to
   NORM sessions.


   The FEC Object Transmission Information has the following specific
   information:


   o  The FEC Encoding ID 129.


   o  The FEC Instance ID 1.


   o  The total length of the object in bytes.


   o  The number of encoding symbols that can be generated for a source
      block.


   o  The length in bytes of encoding symbols, common to all source
      blocks.


   The receiver MUST support delivery of FEC Object Transmission
   Information using the EXT_FTI header for Reed-Solomon 129/1 FEC
   scheme. It is left up to individual implementations to decide how
   frequently and in which packets the EXT_FTI header extension is
   included. Out-of-band communication of this information is also
   possible, but it is outside the scope of this document.


   The format of the EXT_FTI header is same as is specified by FLUTE [8]
   for FEC Encoding ID 129.


   The FEC Encoding ID (8 bits) is carried in the Codepoint field of the
   ALC header when ALC is used, and in the fec_id field of the NORM
   header when NORM is used.





Peltotalo, et al.      Expires December 13, 2004               [Page 16]
Internet-Draft    Simple XOR, Reed-Solomon, and Parity Check Matrix-based FEC Schemes                                            June 2004



   With Reed-Solomon 129/1 FEC scheme there MUST be at most one symbol
   per packet.


   When using Reed-Solomon (n, k) FEC codes, the values for k and n have
   to be known for each block. These values are required both during the
   encoding and decoding phases.


   Here the receivers MUST get the value for k from the FEC Payload ID's
   Source Block Length field. The Maximum Number of Encoding Symbols
   field of the EXT_FTI header MUST be used as the n value for all
   blocks.









































Peltotalo, et al.      Expires December 13, 2004               [Page 17]
Internet-Draft    Simple XOR, Reed-Solomon, and Parity Check Matrix-based FEC Schemes                                            June 2004



6. Use of the FEC Encoding ID 132/FEC Instance ID 0 for LDGM-Staircase
   Codes


   The FEC Instance ID value of 0, for the Under-Specified FEC Encoding
   ID 132 name-space, is reserved and used as described in this section
   for LDGM-Staircase codes [11]. A publicly available reference
   implementation of these codes is available and distributed under a
   GNU LGPL license [12].


   This FEC Instance ID MUST use the FEC Payload ID and FEC Object
   Transmission Information extension (EXT_FTI) formats specified in
   Sections 3.1 and 3.4.


   The FEC Instance ID-Specific Information field of the EXT_FTI, if
   present, MUST contain a seed that is used by the pseudo random number
   generator during the creation of the matrix. Since different versions
   of pseudo-random number generator exist, requiring different seed
   sizes (e.g. srand assumes an "unsigned int", srand48 a "long int",
   and seed48 an array of three "unsigned short" elements, for a total
   of 48 bits), its length is variable. In some cases a fixed value, for
   instance defined at compilation time (or provided by an out-of-band
   mechanism) can be used, in which case no FEC Instance ID-Specific
   Information field is included in the EXT_FTI. Upon receiving an
   EXT_FTI, the HEL field indicates if this field is present and its
   size, after subtracting 5 (i.e. the size of the fixed part of
   EXT_FTI) to its value.


   With LDGM-Staircase 132/0 FEC scheme there MUST be at most one symbol
   per packet.


   The algorithm for computing the block structure, in Section 7, and
   the n-algorithm for computing the number of encoding symbols of a
   block, in Section 8, are both REQUIRED.



















Peltotalo, et al.      Expires December 13, 2004               [Page 18]
Internet-Draft    Simple XOR, Reed-Solomon, and Parity Check Matrix-based FEC Schemes                                            June 2004



7. Algorithm for Computing the Source Block Structure


   This algorithm is same as is specified by FLUTE [8].


   The algorithm does two things: (a) it tells the receiver the length
   of each particular source block as it is receiving packets for that
   source block and, (b) it provides the source block structure
   immediately to the receiver so that the receiver can determine where
   to save recovered source blocks at the beginning - this is an
   optimisation, which is essential for some implementations.


   This algorithm computes a source block structure so that all source
   blocks are as close to being equal length as possible. A first number
   of source blocks are of the same larger length, and the remaining
   second number of source blocks are sent of the same smaller length.
   The total number of source blocks (N), the first number of source
   blocks (I), the second number of source blocks (N-I), the larger
   length (A_large) and the smaller length (A_small) are calculated
   thus,


      Input:
         B -- Maximum Source Block Length, i.e., the maximum number of
              source symbols per source block. This is given by the FEC
              codec specifications and/or the execution environment
              limitations.
         L -- Transfer Length in bytes, i.e., the length of the
              transport object in bytes.
         E -- Encoding Symbol Length in bytes.


      Output:
         N -- The number of source blocks into which the transport
              object is partitioned.


         The number and lengths of source symbols in each of the N
         source blocks.


      Algorithm:
      (a) The number of source symbols in the transport object is
          computed as T = L/E rounded up to the nearest integer
          (if L mod E == 0 then T = L div E, otherwise T = L div E + 1)
      (b) The transport object is partitioned into N source blocks,
          where N = T/B rounded up to the nearest integer
          (if T mod B == 0 then N = T div B, otherwise N = T div B + 1)
      (c) A_large = T/N rounded up to the nearest integer
          (if T mod N == 0 then A_large = T div N, otherwise A_large =
          T div N + 1)
      (d) A_small = T/N rounded down to the nearest integer
          (A_small = T div N)




Peltotalo, et al.      Expires December 13, 2004               [Page 19]
Internet-Draft    Simple XOR, Reed-Solomon, and Parity Check Matrix-based FEC Schemes                                            June 2004



      (e) I = T mod N
          (I is an integer between 0 and N-1)
      (f) Each of the first I source blocks consists of A_large source
          symbols, each source symbol is E bytes in length. Each of the
          remaining N-I source blocks consist of A_small source symbols,
          each source symbol is E bytes in length except that the last
          source symbol of the last source block is L-(((L-1) div E))*E
          bytes in length.


      Notes:
      (1) X div Y denotes the integer quotient of the division X/Y
      (2) X mod Y denotes the integer remainder of the division X/Y
      (3) X div Y + 1 = (X div Y) + 1
      (4) T/N is the average length of the source block
      (5) If T mod N is zero then A_small = A_large


   The use of floating point arithmetic in the algorithm might lead to
   erroneous results caused by rounding problems, depending on the
   mathematical library used. These problems can be avoided by using
   only integer math in all algorithm calculations. It is strongly
   recommended not to use rounding functions, and the comments in
   brackets illustrate a method for this.






























Peltotalo, et al.      Expires December 13, 2004               [Page 20]
Internet-Draft    Simple XOR, Reed-Solomon, and Parity Check Matrix-based FEC Schemes                                            June 2004



8. Algorithm for Computing the Number of Encoding Symbols of a Block


   When using block (n, k) FEC codes, for example Reed-Solomon codes,
   values for k and n have to be known for each block. These values are
   required both in encoding and decoding phase.


   This section describes an algorithm, called the "n-algorithm" in this
   document, which can be used to compute the value of n based on the
   variables that are communicated to receivers using, for example, an
   EXT_FTI header.


   This algorithm is used to compute the value for n.


      AT A SENDER:


      Input:
         B     -- Maximum Source Block Length, i.e., the maximum number
                  of source symbols per source block. This is given by
                  the FEC codec specifications and/or the execution
                  environment limitations.
         k     -- Source Block Length, i.e., the number of source
                  symbols per source block. This is given by source
                  blocking algorithm.
         R or  -- FEC code rate, which is given by the user (e.g. when
         (a, b)   starting a FLUTE sending application). It is expressed
                  either as a floating point value, R, or as a quotient
                  a/b. The latter option is RECOMMENDED for the integer
                  math version of the algorithm. For instance, if we
                  consider a (n, k) systematic FEC code, then a=k,
                  number of source symbols after FEC encoding, and b=n,
                  number of encoding symbols, data plus parity. For
                  example R=1/2 means that 50 percent of the encoded
                  data is parity and 50 percent is original data.


      Output:
         max_n -- Maximum Number of Encoding Symbols per encoding block.
                  This depends on FEC code rate.
         n     -- Encoding Block Length, i.e., the number of encoding
                  symbols generated for the source block.


      Algorithm:
      (a) max_n = B / R rounded down to the nearest integer
          (max_n = (B * b) div a)
      (b) n = k * max_n / B rounded down to the nearest integer
          (n = (k * max_n) div B)


      AT A RECEIVER





Peltotalo, et al.      Expires December 13, 2004               [Page 21]
Internet-Draft    Simple XOR, Reed-Solomon, and Parity Check Matrix-based FEC Schemes                                            June 2004



      Input:
         B
         max_n
         k


      Output:
         n


      Algorithm:
      (a) n = k * max_n / B rounded down to the nearest integer
          (n = (k * max_n) div B)


      Notes:
      (1) X div Y denotes the integer quotient of the division X/Y


   The use of floating point arithmetic in the algorithm might lead to
   erroneous results caused by rounding problems, depending on the
   mathematical library used. These problems can be avoided by using
   only integer math in all algorithm calculations. It is strongly
   recommended not to use rounding functions, and how to do that is
   presented in brackets.































Peltotalo, et al.      Expires December 13, 2004               [Page 22]
Internet-Draft    Simple XOR, Reed-Solomon, and Parity Check Matrix-based FEC Schemes                                            June 2004



9. Security Considerations


   The security considerations for this document are the same as they
   are for RFC 3452 [5].
















































Peltotalo, et al.      Expires December 13, 2004               [Page 23]
Internet-Draft    Simple XOR, Reed-Solomon, and Parity Check Matrix-based FEC Schemes                                            June 2004



10. IANA Considerations


   Values of FEC Encoding IDs are subject to IANA registration. For
   general guidelines on IANA considerations as they apply to this
   document, see RFC 3452 [5].


   This document assigns the Fully-Specified FEC Encoding ID 2 under the
   ietf:rmt:fec:encoding name-space to "Simple XOR FEC". The FEC Payload
   ID format and corresponding FEC Object Transmission Information
   associated with FEC Encoding ID 2 is described in Sections 3.1 and
   3.2, and the corresponding FEC scheme is described in Section 1.1.


   This document assigns the Under-Specified FEC Encoding ID 132 under
   the ietf:rmt:fec:encoding name-space to "Parity Check Matrix-based
   FEC". The FEC Payload ID format and corresponding FEC Object
   Transmission Information associated with FEC Encoding ID 132 are
   described in Sections 3.1 and 3.3.


   As FEC Encoding ID 132 is Under-Specified, a new "FEC Instance ID"
   sub-name-space must be established, in accordance to RFC 3452. Hence
   this document also establishes a new "FEC Instance ID" registry named


   ietf:rmt:fec:encoding:instance:132


   and scoped by


   ietf:rmt:fec:encoding = 132 (Parity Check Matrix-based FEC)


   As per RFC 3452 [5], the values that can be assigned within
   ietf:rmt:fec:encoding:instance:132 are non-negative numeric indices.
   Assignment requests are granted on a "First Come First Served" basis.
   RFC 3452 [5] specifies additional criteria that MUST be met for the
   assignment within the generic ietf:rmt:fec:encoding:instance name-
   space. These criteria also apply to
   ietf:rmt:fec:encoding:instance:132.


   This document assigns the FEC Instance ID value 0 for the
   LDGM-Staircase codes [11] from scope ietf:rmt:fec:encoding = 132.


   This document assigns the FEC Instance ID value 0 for the
   Reed-Solomon 129/0 FEC scheme from scope ietf:rmt:fec:encoding = 129.


   This document assigns the FEC Instance ID value 1 for the
   Reed-Solomon 129/1 FEC scheme from scope ietf:rmt:fec:encoding = 129.








Peltotalo, et al.      Expires December 13, 2004               [Page 24]
Internet-Draft    Simple XOR, Reed-Solomon, and Parity Check Matrix-based FEC Schemes                                            June 2004



11. Acknowledgements


   The authors would like to thank all the people who gave feedback on
   this document.
















































Peltotalo, et al.      Expires December 13, 2004               [Page 25]
Internet-Draft    Simple XOR, Reed-Solomon, and Parity Check Matrix-based FEC Schemes                                            June 2004



Normative References


   [1]  Bradner, S., "Key words for use in RFCs to Indicate Requirement
        Levels", RFC 2119, BCP 14, March 1997.


   [2]  Whetten, B., Vicisano, L., Kermode, R., Handley, M., Floyd, S.
        and M. Luby, "Reliable Multicast Transport Building Blocks for
        One-to-Many  Bulk-Data Transfer", RFC 3048, January 2001.


   [3]  Kermode, R. and L. Vicisano, "Author Guidelines for Reliable
        Multicast Transport (RMT) Building  Blocks and Protocol
        Instantiation documents", RFC 3269, April 2002.


   [4]  Luby, M., Gemmell, J., Vicisano, L., Rizzo, L. and J. Crowcroft,
        "Asynchronous Layered Coding (ALC) Protocol Instantiation", RFC
        3450, December 2002.


   [5]  Luby, M., Vicisano, L., Gemmell, J., Rizzo, L., Handley, M. and
        J. Crowcroft, "Forward Error Correction (FEC) Building Block",
        RFC 3452, December 2002.


   [6]  Luby, M., Vicisano, L., Gemmell, J., Rizzo, L., Handley, M. and
        J. Crowcroft, "The Use of Forward Error Correction (FEC) in
        Reliable Multicast", RFC 3453, December 2002.


   [7]  Luby, M. and L. Vicisano, "Compact Forward Error Correction
        (FEC) Schemes", RFC 3695, February 2004.


   [8]  Paila, T., Luby, M., Lehtonen, R., Roca, V. and R. Walsh, "FLUTE
        - File Delivery over Unidirectional Transport",
        draft-ietf-rmt-flute-08 (work in progress), June 2004.





















Peltotalo, et al.      Expires December 13, 2004               [Page 26]
Internet-Draft    Simple XOR, Reed-Solomon, and Parity Check Matrix-based FEC Schemes                                            June 2004



Informative References


   [9]   Rizzo, L., "Effective Erasure Codes for Reliable Computer
         Communication Protocols", ACM SIGCOMM Computer Communication
         Review Vol.27, No.2, pp.24-36, April 1997.


   [10]  Adamson, B., Bormann, C., Handley, M. and J. Macker,
         "NACK-Oriented Reliable Multicast Protocol (NORM)",
         draft-ietf-rmt-pi-norm-09 (work in progress), January 2004.


   [11]  Roca, V. and C. Neumann, "Design, Evaluation and Comparison of
         Four Large Block FEC Codecs, LDPC, LDGM, LDGM Staircase and
         LDGM Triangle, Plus a Reed-Solomon Small Block FEC Codec",
         INRIA Research Report RR-5225, June 2004.


   [12]  Roca, V., Neumann, C., Laboure, J. and Z. Khallouf,
         "LDGM-staircase codec reference implementation", MCLv3 project
         PLANETE Research Team, INRIA Rhone-Alpes, April 2004.


   [13]  MacKay, D., "Information Theory, Inference and Learning
         Algorithms", Cambridge University Press, ISBN: 0521642981,
         2003.



Authors' Addresses


   Jani Peltotalo
   Tampere University of Technology
   P.O. Box 553 (Korkeakoulunkatu 1)
   Tampere  FIN-33101
   Finland


   EMail: jani.peltotalo@tut.fi



   Sami Peltotalo
   Tampere University of Technology
   P.O. Box 553 (Korkeakoulunkatu 1)
   Tampere  FIN-33101
   Finland


   EMail: sami.peltotalo@tut.fi










Peltotalo, et al.      Expires December 13, 2004               [Page 27]
Internet-Draft    Simple XOR, Reed-Solomon, and Parity Check Matrix-based FEC Schemes                                            June 2004



   Vincent Roca
   INRIA Rhone-Alpes
   655, av. de l'Europe
   Montbonnot  St Ismier cedex 38334
   France


   EMail: vincent.roca@inrialpes.fr













































Peltotalo, et al.      Expires December 13, 2004               [Page 28]
Internet-Draft    Simple XOR, Reed-Solomon, and Parity Check Matrix-based FEC Schemes                                            June 2004



Intellectual Property Statement


   The IETF takes no position regarding the validity or scope of any
   intellectual property or other rights that might be claimed to
   pertain to the implementation or use of the technology described in
   this document or the extent to which any license under such rights
   might or might not be available; neither does it represent that it
   has made any effort to identify any such rights. Information on the
   IETF's procedures with respect to rights in standards-track and
   standards-related documentation can be found in BCP-11. Copies of
   claims of rights made available for publication and any assurances of
   licenses to be made available, or the result of an attempt made to
   obtain a general license or permission for the use of such
   proprietary rights by implementors or users of this specification can
   be obtained from the IETF Secretariat.


   The IETF invites any interested party to bring to its attention any
   copyrights, patents or patent applications, or other proprietary
   rights which may cover technology that may be required to practice
   this standard. Please address the information to the IETF Executive
   Director.



Full Copyright Statement


   Copyright (C) The Internet Society (2004). All Rights Reserved.


   This document and translations of it may be copied and furnished to
   others, and derivative works that comment on or otherwise explain it
   or assist in its implementation may be prepared, copied, published
   and distributed, in whole or in part, without restriction of any
   kind, provided that the above copyright notice and this paragraph are
   included on all such copies and derivative works. However, this
   document itself may not be modified in any way, such as by removing
   the copyright notice or references to the Internet Society or other
   Internet organizations, except as needed for the purpose of
   developing Internet standards in which case the procedures for
   copyrights defined in the Internet Standards process must be
   followed, or as required to translate it into languages other than
   English.


   The limited permissions granted above are perpetual and will not be
   revoked by the Internet Society or its successors or assignees.


   This document and the information contained herein is provided on an
   "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING
   TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING
   BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION




Peltotalo, et al.      Expires December 13, 2004               [Page 29]
Internet-Draft    Simple XOR, Reed-Solomon, and Parity Check Matrix-based FEC Schemes                                            June 2004



   HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF
   MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.



Acknowledgment


   Funding for the RFC Editor function is currently provided by the
   Internet Society.












































Peltotalo, et al.      Expires December 13, 2004               [Page 30]