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]