draft-ietf-rmt-bb-fec-rs-01.txt   draft-ietf-rmt-bb-fec-rs-02.txt 
Reliable Multicast Transport J. Lacan Reliable Multicast Transport J. Lacan
Internet-Draft ENSICA/LAAS-CNRS Internet-Draft ENSICA/LAAS-CNRS
Expires: December 25, 2006 V. Roca Intended status: Experimental V. Roca
INRIA Expires: June 25, 2007 INRIA
J. Peltotalo J. Peltotalo
S. Peltotalo S. Peltotalo
Tampere University of Technology Tampere University of Technology
June 23, 2006 December 22, 2006
Reed-Solomon Forward Error Correction (FEC) Reed-Solomon Forward Error Correction (FEC)
draft-ietf-rmt-bb-fec-rs-01.txt draft-ietf-rmt-bb-fec-rs-02.txt
Status of this Memo Status of this Memo
By submitting this Internet-Draft, each author represents that any By submitting this Internet-Draft, each author represents that any
applicable patent or other IPR claims of which he or she is aware applicable patent or other IPR claims of which he or she is aware
have been or will be disclosed, and any of which he or she becomes have been or will be disclosed, and any of which he or she becomes
aware will be disclosed, in accordance with Section 6 of BCP 79. aware will be disclosed, in accordance with Section 6 of BCP 79.
Internet-Drafts are working documents of the Internet Engineering Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that Task Force (IETF), its areas, and its working groups. Note that
skipping to change at page 1, line 38 skipping to change at page 1, line 38
and may be updated, replaced, or obsoleted by other documents at any and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress." material or to cite them other than as "work in progress."
The list of current Internet-Drafts can be accessed at The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt. http://www.ietf.org/ietf/1id-abstracts.txt.
The list of Internet-Draft Shadow Directories can be accessed at The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html. http://www.ietf.org/shadow.html.
This Internet-Draft will expire on December 25, 2006. This Internet-Draft will expire on June 25, 2007.
Copyright Notice Copyright Notice
Copyright (C) The Internet Society (2006). Copyright (C) The IETF Trust (2006).
Abstract Abstract
This document describes a Fully-Specified FEC scheme for the Reed- This document describes a Fully-Specified FEC scheme for the Reed-
Solomon forward error correction code and its application to the Solomon forward error correction code and its application to the
reliable delivery of data objects on the packet erasure channel. reliable delivery of data objects on the packet erasure channel.
Reed-Solomon codes belong to the class of Maximum Distance Separable Reed-Solomon codes belong to the class of Maximum Distance Separable
(MDS) codes, i.e. they enable a receiver to recover the k source (MDS) codes, i.e. they enable a receiver to recover the k source
symbols from any set of k received symbols. symbols from any set of k received symbols.
The implementation described here is compatible with the The implementation described here is compatible with the
implementation from Luigi Rizzo. implementation from Luigi Rizzo.
Table of Contents Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4
2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 4 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 5
3. Definitions Notations and Abbreviations . . . . . . . . . . . 5 3. Definitions Notations and Abbreviations . . . . . . . . . . . 6
3.1. Definitions . . . . . . . . . . . . . . . . . . . . . . . 5 3.1. Definitions . . . . . . . . . . . . . . . . . . . . . . . 6
3.2. Notations . . . . . . . . . . . . . . . . . . . . . . . . 5 3.2. Notations . . . . . . . . . . . . . . . . . . . . . . . . 6
3.3. Abbreviations . . . . . . . . . . . . . . . . . . . . . . 6 3.3. Abbreviations . . . . . . . . . . . . . . . . . . . . . . 7
4. Formats and Codes . . . . . . . . . . . . . . . . . . . . . . 7 4. Formats and Codes . . . . . . . . . . . . . . . . . . . . . . 8
4.1. FEC Payload ID . . . . . . . . . . . . . . . . . . . . . . 7 4.1. FEC Payload ID . . . . . . . . . . . . . . . . . . . . . . 8
4.2. FEC Object Transmission Information . . . . . . . . . . . 8 4.2. FEC Object Transmission Information . . . . . . . . . . . 9
4.2.1. Mandatory Elements . . . . . . . . . . . . . . . . . . 8 4.2.1. Mandatory Elements . . . . . . . . . . . . . . . . . . 9
4.2.2. Common Elements . . . . . . . . . . . . . . . . . . . 8 4.2.2. Common Elements . . . . . . . . . . . . . . . . . . . 9
4.2.3. Scheme-Specific Elements . . . . . . . . . . . . . . . 8 4.2.3. Scheme-Specific Elements . . . . . . . . . . . . . . . 9
4.2.4. Encoding Format . . . . . . . . . . . . . . . . . . . 9 4.2.4. Encoding Format . . . . . . . . . . . . . . . . . . . 10
5. Procedures . . . . . . . . . . . . . . . . . . . . . . . . . . 11 5. Procedures . . . . . . . . . . . . . . . . . . . . . . . . . . 12
5.1. Determining the Maximum Source Block Length (B) . . . . . 11 5.1. Determining the Maximum Source Block Length (B) . . . . . 12
5.2. Determining the Number of Encoding Symbols of a Block . . 11 5.2. Determining the Number of Encoding Symbols of a Block . . 12
6. Reed-Solomon Codes Specification for the Erasure Channel . . . 13 6. Reed-Solomon Codes Specification for the Erasure Channel . . . 14
6.1. Finite Field . . . . . . . . . . . . . . . . . . . . . . . 13 6.1. Finite Field . . . . . . . . . . . . . . . . . . . . . . . 14
6.2. Reed-Solomon Encoding Algorithm . . . . . . . . . . . . . 14 6.2. Reed-Solomon Encoding Algorithm . . . . . . . . . . . . . 15
6.2.1. Encoding Principles . . . . . . . . . . . . . . . . . 14 6.2.1. Encoding Principles . . . . . . . . . . . . . . . . . 15
6.2.2. Encoding Complexity . . . . . . . . . . . . . . . . . 15 6.2.2. Encoding Complexity . . . . . . . . . . . . . . . . . 16
6.3. Reed-Solomon Decoding Algorithm . . . . . . . . . . . . . 15 6.3. Reed-Solomon Decoding Algorithm . . . . . . . . . . . . . 16
6.3.1. Decoding Principles . . . . . . . . . . . . . . . . . 15 6.3.1. Decoding Principles . . . . . . . . . . . . . . . . . 16
6.3.2. Decoding Complexity . . . . . . . . . . . . . . . . . 16 6.3.2. Decoding Complexity . . . . . . . . . . . . . . . . . 17
6.4. Implementation for the Packet Erasure Channel . . . . . . 16 6.4. Implementation for the Packet Erasure Channel . . . . . . 17
7. Security Considerations . . . . . . . . . . . . . . . . . . . 18 7. Security Considerations . . . . . . . . . . . . . . . . . . . 19
8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 19 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 20
9. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 20 9. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 21
10. References . . . . . . . . . . . . . . . . . . . . . . . . . . 21 10. References . . . . . . . . . . . . . . . . . . . . . . . . . . 22
10.1. Normative References . . . . . . . . . . . . . . . . . . . 21 10.1. Normative References . . . . . . . . . . . . . . . . . . . 22
10.2. Informative References . . . . . . . . . . . . . . . . . . 21 10.2. Informative References . . . . . . . . . . . . . . . . . . 22
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 23 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 24
Intellectual Property and Copyright Statements . . . . . . . . . . 24 Intellectual Property and Copyright Statements . . . . . . . . . . 25
1. Introduction 1. Introduction
The use of Forward Error Correction (FEC) codes is a classical The use of Forward Error Correction (FEC) codes is a classical
solution to improve the reliability of multicast and broadcast solution to improve the reliability of multicast and broadcast
transmissions. The [2] document describes a general framework to use transmissions. The [2] document describes a general framework to use
FEC in Content Delivery Protocols (CDP). The companion document [3] FEC in Content Delivery Protocols (CDP). The companion document [3]
describes some applications of FEC codes for content delivery. describes some applications of FEC codes for content delivery.
Recent FEC schemes like [6] and [7] proposed erasure codes based on Recent FEC schemes like [6] and [7] proposed erasure codes based on
skipping to change at page 6, line 10 skipping to change at page 7, line 10
any source block. any source block.
B denotes the maximum source block length in symbols, i.e. the B denotes the maximum source block length in symbols, i.e. the
maximum number of source symbols per source block. maximum number of source symbols per source block.
N denotes the number of source blocks into which the object shall N denotes the number of source blocks into which the object shall
be partitioned. be partitioned.
E denotes the encoding symbol length in bytes. E denotes the encoding symbol length in bytes.
S denotes the symbol size in units of m bit elements. When m = 8, S denotes the symbol size in units of m-bit elements. When m = 8,
then S and E are equal. then S and E are equal.
m defines the length of the elements in the finite field, in bits. m defines the length of the elements in the finite field, in bits.
q defines the number of elements in the finite field. We have: q q defines the number of elements in the finite field. We have: q
= 2^^m in this specification. = 2^^m in this specification.
G denotes the number of encoding symbols per group, i.e. the G denotes the number of encoding symbols per group, i.e. the
number of symbols sent in the same packet. number of symbols sent in the same packet.
skipping to change at page 7, line 13 skipping to change at page 8, line 13
elements. We assume that q = 2^^m in this document. elements. We assume that q = 2^^m in this document.
4. Formats and Codes 4. Formats and Codes
4.1. FEC Payload ID 4.1. FEC Payload ID
The FEC Payload ID is composed of the Source Block Number and the The FEC Payload ID is composed of the Source Block Number and the
Encoding Symbol ID. The length of these two fields depends on the Encoding Symbol ID. The length of these two fields depends on the
parameter m (which is transmitted in the FEC OTI) as follows : parameter m (which is transmitted in the FEC OTI) as follows :
o The Source Block Number (32-m bit field) identifies from which o The Source Block Number (field of size 32-m bits) identifies from
source block of the object the encoding symbol(s) in the payload which source block of the object the encoding symbol(s) in the
is (are) generated. There are a maximum of 2^^(32-m) blocks per payload is (are) generated. There are a maximum of 2^^(32-m)
object. blocks per object.
o The Encoding Symbol ID (m bit field) identifies which specific o The Encoding Symbol ID (field of size m bits) identifies which
encoding symbol(s) generated from the source block is(are) carried specific encoding symbol(s) generated from the source block
in the packet payload. There are a maximum of 2^^m encoding is(are) carried in the packet payload. There are a maximum of
symbols per block. The first k values (0 to k - 1) identify 2^^m encoding symbols per block. The first k values (0 to k - 1)
source symbols, the remaining n-k values identify repair symbols. identify source symbols, the remaining n-k values identify repair
symbols.
There MUST be exactly one FEC Payload ID per source or repair packet. There MUST be exactly one FEC Payload ID per source or repair packet.
In case of an Encoding Symbol Group, when multiple encoding symbols In case of an Encoding Symbol Group, when multiple encoding symbols
are sent in the same packet, the FEC Payload ID refers to the first are sent in the same packet, the FEC Payload ID refers to the first
symbol of the packet. The other symbols can be deduced from the ESI symbol of the packet. The other symbols can be deduced from the ESI
of the first symbol by incrementing sequentially the ESI. of the first symbol by incrementing sequentially the ESI.
The format of the FEC Payload ID for m = 8 and m = 16 is illustrated The format of the FEC Payload ID for m = 8 and m = 16 is illustrated
in Figure 1 and Figure 2 respectively. in Figure 1 and Figure 2 respectively.
skipping to change at page 8, line 10 skipping to change at page 9, line 10
| Src Block Nb (32-16=16 bits) | Enc. Symbol ID (m=16 bits) | | Src Block Nb (32-16=16 bits) | Enc. Symbol ID (m=16 bits) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 2: FEC Payload ID encoding format for m = 16 Figure 2: FEC Payload ID encoding format for m = 16
4.2. FEC Object Transmission Information 4.2. FEC Object Transmission Information
4.2.1. Mandatory Elements 4.2.1. Mandatory Elements
o FEC Encoding ID: the Fully-Specified FEC Scheme described in this o FEC Encoding ID: the Fully-Specified FEC Scheme described in this
document uses FEC Encoding ID XX. document uses FEC Encoding ID 2.
4.2.2. Common Elements 4.2.2. Common Elements
The following elements MUST be defined with the present FEC scheme: The following elements MUST be defined with the present FEC scheme:
o Transfer-Length (L): a non-negative integer indicating the length o Transfer-Length (L): a non-negative integer indicating the length
of the object in bytes. There are some restrictions on the of the object in bytes. There are some restrictions on the
maximum Transfer-Length that can be supported : maximum Transfer-Length that can be supported :
max_transfer_length = 2^^(32-m) * B * E max_transfer_length = 2^^(32-m) * B * E
skipping to change at page 9, line 49 skipping to change at page 10, line 49
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 3: EXT_FTI Header Format Figure 3: EXT_FTI Header Format
4.2.4.2. Using the FDT Instance (FLUTE specific) 4.2.4.2. Using the FDT Instance (FLUTE specific)
When it is desired that the FEC OTI be carried in the FDT Instance of When it is desired that the FEC OTI be carried in the FDT Instance of
a FLUTE session [10], the following XML attributes must be described a FLUTE session [10], the following XML attributes must be described
for the associated object: for the associated object:
o FEC-OTI-Transfer-Length (L) o FEC-OTI-FEC-Encoding-ID
o FEC-OTI-Transfer-Length (L)
o FEC-OTI-Encoding-Symbol-Length (E) o FEC-OTI-Encoding-Symbol-Length (E)
o FEC-OTI-Maximum-Source-Block-Length (B) o FEC-OTI-Maximum-Source-Block-Length (B)
o FEC-OTI-Max-Number-of-Encoding-Symbols (max_n) o FEC-OTI-Max-Number-of-Encoding-Symbols (max_n)
o FEC-OTI-Number-of-Encoding-Symbols-per-Group (optional) (G) o FEC-OTI-Scheme-Specific-Info
o FEC-OTI-Finite-Field-Parameter (optional) (m) The FEC-OTI-Scheme-Specific-Info contains the string resulting from
the Base64 encoding (in the XML Schema xs:base64Binary sense) of the
following value:
When no G parameter is to be carried in the FEC OTI, the sender 0 1
simply omits the FEC-OTI-Number-of-Encoding-Symbols-per-Group 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
attribute. When no Finite Field parameter is to be carried in the +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
FEC OTI, the sender simply omits the FEC-OTI-Finite-Field-Parameter | m | G |
attribute. +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 4: FEC OTI Scheme Specific Information to be Included in the
FDT Instance
When no m parameter is to be carried in the FEC OTI, the m field is
set to 0 (which is not a valid seed value). Otherwise the m field
contains a valid value as explained in Section 4.2.3. Similarly,
when no G parameter is to be carried in the FEC OTI, the G field is
set to 0 (which is not a valid seed value). Otherwise the G field
contains a valid value as explained in Section 4.2.3. When neither m
nor G are to be carried in the FEC OTI, then the sender simply omits
the FEC-OTI-Scheme-Specific-Info attribute.
After Base64 encoding, the 2 bytes of the FEC OTI Scheme Specific
Information are transformed into a string of 4 printable characters
(in the 64-character alphabet) and added to the FEC-OTI-Scheme-
Specific-Info attribute.
5. Procedures 5. Procedures
5.1. Determining the Maximum Source Block Length (B) 5.1. Determining the Maximum Source Block Length (B)
The finite field size parameter, m, defines the number of non zero The finite field size parameter, m, defines the number of non zero
elements in this field which is equal to: q - 1 = 2^^m - 1. Note elements in this field which is equal to: q - 1 = 2^^m - 1. Note
that q - 1 is also the theoretical maximum number of encoding symbols that q - 1 is also the theoretical maximum number of encoding symbols
that can be produced for a source block. For instance, when m = 8 that can be produced for a source block. For instance, when m = 8
(default): (default):
max1_B = 2^^8 - 1 = 255 max1_B = 2^^8 - 1 = 255
Additionally, a codec MAY impose other limitations on the maximum Additionally, a codec MAY impose other limitations on the maximum
block size. Yet it is not expected that such limits exist when using block size. Yet it is not expected that such limits exist when using
the default m = 8 value. This decision SHOULD be clarified at the default m = 8 value. This decision MUST be clarified at
implementation time, when the target use case is known. This results implementation time, when the target use case is known. This results
in a max2_B limitation. in a max2_B limitation.
Then, B is given by: Then, B is given by:
B = min(max1_B, max2_B) B = min(max1_B, max2_B)
Note that this calculation is only required at the coder, since the B Note that this calculation is only required at the coder, since the B
parameter is communicated to the decoder through the FEC OTI. parameter is communicated to the decoder through the FEC OTI.
skipping to change at page 12, line 36 skipping to change at page 13, line 36
n n
Algorithm: Algorithm:
n = floor(k * max_n / B); n = floor(k * max_n / B);
Note that a Reed-Solomon decoder does not need to know the n value. Note that a Reed-Solomon decoder does not need to know the n value.
Therefore the receiver part of the "n-algorithm" is not necessary Therefore the receiver part of the "n-algorithm" is not necessary
from the Reed-Solomon decoder point of view. Yet a receiving from the Reed-Solomon decoder point of view. Yet a receiving
application using the Reed-Solomon FEC scheme will sometimes need to application using the Reed-Solomon FEC scheme will sometimes need to
know the value of n used by the sender, for instance for memory know the n value used by the sender, for instance for memory
management optimizations. To that purpose, the FEC OTI carries all management optimizations. To that purpose, the FEC OTI carries all
the parameters needed for a receiver to execute the above algorithm. the parameters needed for a receiver to execute the above algorithm.
6. Reed-Solomon Codes Specification for the Erasure Channel 6. Reed-Solomon Codes Specification for the Erasure Channel
Reed-Solomon (RS) codes are linear block codes. They also belong to Reed-Solomon (RS) codes are linear block codes. They also belong to
the class of MDS codes. A [n,k]-RS code encodes a sequence of k the class of MDS codes. A [n,k]-RS code encodes a sequence of k
source elements defined over a finite field GF(q) into a sequence of source elements defined over a finite field GF(q) into a sequence of
n encoding elements, where n is upper bounded by q - 1. The n encoding elements, where n is upper bounded by q - 1. The
implementation described in this document is based on a generator implementation described in this document is based on a generator
skipping to change at page 13, line 25 skipping to change at page 14, line 25
m-bit elements, and Section 6.4 the use of [n,k]-RS codes when m-bit elements, and Section 6.4 the use of [n,k]-RS codes when
applied to symbols composed of several m-bit elements, which is the applied to symbols composed of several m-bit elements, which is the
target of this specification. target of this specification.
6.1. Finite Field 6.1. Finite Field
A finite field GF(q) is defined as a finite set of q elements which A finite field GF(q) is defined as a finite set of q elements which
has a structure of field. It contains necessarily q = p^^m elements, has a structure of field. It contains necessarily q = p^^m elements,
where p is a prime number. With packet erasure channels, p is always where p is a prime number. With packet erasure channels, p is always
set to 2. The elements of the field GF(2^^m) can be represented by set to 2. The elements of the field GF(2^^m) can be represented by
polynomials with binary coefficients (i.e. over GF(2)) of degree less polynomials with binary coefficients (i.e. over GF(2)) of degree
than m. The polynomials can be associated to binary vectors of lower or equal than m-1. The polynomials can be associated to binary
length m. For example, the vector (11001) represents the polynomial vectors of length m. For example, the vector (11001) represents the
1 + x + x^^4. This representation is often called polynomial polynomial 1 + x + x^^4. This representation is often called
representation. The addition between two elements is defined as the polynomial representation. The addition between two elements is
addition of binary polynomials in GF(2) and the multiplication is the defined as the addition of binary polynomials in GF(2) and the
multiplication modulo a given irreducible polynomial over GF(2) of multiplication is the multiplication modulo a given irreducible
degree m with coefficients in GF(2). Note that all the roots of this polynomial over GF(2) of degree m with coefficients in GF(2). Note
polynomial are in GF(2^^m) but not in GF(2). that all the roots of this polynomial are in GF(2^^m) but not in
GF(2).
A finite field GF(2^^m) is completely characterized by the A finite field GF(2^^m) is completely characterized by the
irreducible polynomial. The following polynomials are chosen to irreducible polynomial. The following polynomials are chosen to
represent the field GF(2^^m), for m varying from 2 to 16: represent the field GF(2^^m), for m varying from 2 to 16:
m = 2, "111" (1+x+x^^2) m = 2, "111" (1+x+x^^2)
m = 3, "1101", (1+x+x^^3) m = 3, "1101", (1+x+x^^3)
m = 4, "11001", (1+x+x^^4) m = 4, "11001", (1+x+x^^4)
skipping to change at page 14, line 40 skipping to change at page 15, line 42
GF(2^^m). Let e = (e_0, ..., e_{n-1}) be the corresponding encoding GF(2^^m). Let e = (e_0, ..., e_{n-1}) be the corresponding encoding
vector of n elements over GF(2^^m). Being a linear code, encoding is vector of n elements over GF(2^^m). Being a linear code, encoding is
performed by multiplying the source vector by a generator matrix, GM, performed by multiplying the source vector by a generator matrix, GM,
of k rows and n columns over GF(2^^m). Thus: of k rows and n columns over GF(2^^m). Thus:
e = s * GM. e = s * GM.
The definition of the generator matrix completely characterizes the The definition of the generator matrix completely characterizes the
RS code. RS code.
Let us consider that: n = 2^^m - 1 and: 0 < k <= n. Let us denote Let us consider that: n = 2^^m - 1 and: 0 < k <= n. Let us denote by
alpha the primitive element of GF(2^^m) chosen in the list of alpha the root of the primitive polynomial of degree m chosen in the
Section 6.1 for the corresponding value of m. Let us consider a list of Section 6.1 for the corresponding value of m. Let us
Vandermonde matrix of k rows and n columns, denoted by V_{k,n}, and consider a Vandermonde matrix of k rows and n columns, denoted by
built as follows: the {i, j} entry of V_{k,n} is v_{i,j} = V_{k,n}, and built as follows: the {i, j} entry of V_{k,n} is v_{i,j}
alpha^^(i*j), where 0 <= i <= k - 1 and 0 <= j <= n - 1. This matrix = alpha^^(i*j), where 0 <= i <= k - 1 and 0 <= j <= n - 1. This
generates a MDS code. However, this MDS code is not systematic, matrix generates a MDS code. However, this MDS code is not
which is a problem for many networking applications. To obtain a systematic, which is a problem for many networking applications. To
systematic matrix (and code), the simplest solution consists in obtain a systematic matrix (and code), the simplest solution consists
considering the matrix V_{k,k} formed by the first k columns of in considering the matrix V_{k,k} formed by the first k columns of
V_{k,n}, then to invert it and to multiply this inverse by V_{k,n}. V_{k,n}, then to invert it and to multiply this inverse by V_{k,n}.
Clearly, the product V_{k,k}^^-1 * V_{k,n} contains the identity Clearly, the product V_{k,k}^^-1 * V_{k,n} contains the identity
matrix I_k on its first k columns, meaning that the first k encoding matrix I_k on its first k columns, meaning that the first k encoding
elements are equal to source elements. Besides the associated code elements are equal to source elements. Besides the associated code
keeps the MDS property. keeps the MDS property.
Therefore, the generator matrix of the code considered in this Therefore, the generator matrix of the code considered in this
document is: document is:
GM = (V_{k,k}^^-1) * V_{k,n} GM = (V_{k,k}^^-1) * V_{k,n}
skipping to change at page 16, line 31 skipping to change at page 17, line 33
matrix (V_(k,k)^^-1) and another Vandermonde matrix (denoted by V' matrix (V_(k,k)^^-1) and another Vandermonde matrix (denoted by V'
which is a submatrix of V_(k,n)). The decoding can be done by which is a submatrix of V_(k,n)). The decoding can be done by
multiplying the received vector by V'^^-1 (interpolation problem with multiplying the received vector by V'^^-1 (interpolation problem with
complexity O( k * log^^2(k)) ) then by V_{k,k} (multipoint evaluation complexity O( k * log^^2(k)) ) then by V_{k,k} (multipoint evaluation
with complexity O(k * log(k))). The global decoding complexity is with complexity O(k * log(k))). The global decoding complexity is
then O(log^^2(k)) operations per source element. then O(log^^2(k)) operations per source element.
6.4. Implementation for the Packet Erasure Channel 6.4. Implementation for the Packet Erasure Channel
In a packet erasure channel, each packet (and symbol(s) since packets In a packet erasure channel, each packet (and symbol(s) since packets
contain G >= 1 symbols) is either received correctly or erased. The contain G >= 1 symbols) is either correctly received or erased. The
location of the erased symbols in the sequence of symbols must be location of the erased symbols in the sequence of symbols must be
known. The following specification describes the use of Reed-Solomon known. The following specification describes the use of Reed-Solomon
codes for generating redundant symbols from k source symbols and to codes for generating redundant symbols from the k source symbols and
recover the source symbols from any set of k received symbols. to recover the source symbols from any set of k received symbols.
The k source symbols of a source block are assumed to be composed of The k source symbols of a source block are assumed to be composed of
S m-bit elements. Each m-bit element is associated to an element of S m-bit elements. Each m-bit element is associated to an element of
the finite field GF(2^^m) through the polynomial representation the finite field GF(2^^m) through the polynomial representation
(Section 6.1). If some of the source symbols contain less than S (Section 6.1). If some of the source symbols contain less than S
elements, they are virtually padded with zero elements (it can be the elements, they are virtually padded with zero elements (it can be the
case for the last symbol of the last block of the object). case for the last symbol of the last block of the object).
The encoding process produces n-k repair symbols of size S m-bit The encoding process produces n-k repair symbols of size S m-bit
elements, the k source symbols being also part of the n encoding elements, the k source symbols being also part of the n encoding
symbols (Figure 4). These repair symbols are created m-bit element symbols (Figure 5). These repair symbols are created m-bit element
per m-bit element. More specifically, the j-th source vector is per m-bit element. More specifically, the j-th source vector is
composed of the j-th element of each of the source symbols. composed of the j-th element of each of the source symbols.
Similarly, the j-th encoding vector is composed of the j-th element Similarly, the j-th encoding vector is composed of the j-th element
of each encoding symbol. of each encoding symbol.
------------ --------------- ------------------- n
+-+-+----+-+ +---------------+ +-+-+-----------+-+
0 | | | | | | | | | | | | 0 | | | | | | | | | | | |
| | | | | * | generator | = | | | | | | | | | | * | generator | = | | | | |
| | | | | | matrix | | | | | | | | | | | | matrix | | | | | |
| | | | | | GM | | | | | | | | | | | | GM | | | | | |
source |--------------| | | |---------------------| source +--------------+ | (k x n) | +---------------------+
vector | | | | | | | --------------- ->| | | | | | | vector | | | | | | | +---------------+ ->| | | | | | |
j |--------------| / |---------------------| j +--------------+ / +---------------------+
| | | | | / | | | | | | | | | | / | | | | |
| | | | | encoding | | | | | | | | | | encoding | | | | |
| | | | | vector | | | | | | | | | | vector | | | | |
| | | | | j | | | | | | | | | | j | | | | |
| | | | | | | | | | | | | | | | | | | |
S-1 | | | | | | | | | | S-1 | | | | | | | | | |
------------ ------------------- +-+-+----+-+ +-+-+-----------+-+
k source symbols n encoding symbols k source symbols n encoding symbols
(source + repair) (source + repair)
Figure 4: Packet encoding scheme Figure 5: Packet encoding scheme
An asset of this scheme is that the loss of some encoding symbols An asset of this scheme is that the loss of some encoding symbols
produces the same erasure pattern for each of the S encoding vectors. produces the same erasure pattern for each of the S encoding vectors.
It follows that the matrix inversion must be done only once and will It follows that the matrix inversion must be done only once and will
be used by all the S encoding vectors. For large S, this matrix be used by all the S encoding vectors. For large S, this matrix
inversion cost becomes negligible in front of the S matrix-vector inversion cost becomes negligible in front of the S matrix-vector
multiplications. multiplications.
Another asset is that the n-k repair symbols can be produced on Another asset is that the n-k repair symbols can be produced on
demand. For instance, a sender can start by producing a limited demand. For instance, a sender can start by producing a limited
skipping to change at page 19, line 10 skipping to change at page 20, line 10
7. Security Considerations 7. Security Considerations
The security considerations for this document are the same as that of The security considerations for this document are the same as that of
[2]. [2].
8. IANA Considerations 8. IANA Considerations
Values of FEC Encoding IDs and FEC Instance IDs are subject to IANA Values of FEC Encoding IDs and FEC Instance IDs are subject to IANA
registration. For general guidelines on IANA considerations as they registration. For general guidelines on IANA considerations as they
apply to this document, see [2]. This document assigns the Fully- apply to this document, see [2]. This document assigns the Fully-
Specified FEC Encoding ID XX under the ietf:rmt:fec:encoding name- Specified FEC Encoding ID 2 under the ietf:rmt:fec:encoding name-
space to "Reed-Solomon Codes". space to "Reed-Solomon Codes".
9. Acknowledgments 9. Acknowledgments
The authors want to thank Luigi Rizzo for comments on the subject and The authors want to thank Luigi Rizzo for comments on the subject and
for the design of the reference Reed-Solomon codec. for the design of the reference Reed-Solomon codec.
10. References 10. References
10.1. Normative References 10.1. Normative References
[1] Bradner, S., "Key words for use in RFCs to Indicate Requirement [1] Bradner, S., "Key words for use in RFCs to Indicate Requirement
Levels", RFC 2119. Levels", RFC 2119.
[2] Watson, M., Luby, M., and L. Vicisano, "Forward Error Correction [2] Watson, M., Luby, M., and L. Vicisano, "Forward Error
(FEC) Building Block", draft-ietf-rmt-fec-bb-revised-03.txt Correction (FEC) Building Block",
(work in progress), January 2006. draft-ietf-rmt-fec-bb-revised-04.txt (work in progress),
September 2006.
[3] Luby, M., Vicisano, L., Gemmell, J., Rizzo, L., Handley, M., and [3] Luby, M., Vicisano, L., Gemmell, J., Rizzo, L., Handley, M.,
J. Crowcroft, "The Use of Forward Error Correction (FEC) in and J. Crowcroft, "The Use of Forward Error Correction (FEC) in
Reliable Multicast", RFC 3453, December 2002. Reliable Multicast", RFC 3453, December 2002.
10.2. Informative References 10.2. Informative References
[4] Rizzo, L., "Reed-Solomon FEC codec (revised version of July [4] Rizzo, L., "Reed-Solomon FEC codec (revised version of July
2nd, 1998), available at 2nd, 1998), available at
http://info.iet.unipi.it/~luigi/vdm98/vdm980702.tgz", http://info.iet.unipi.it/~luigi/vdm98/vdm980702.tgz",
July 1998. July 1998.
[5] Mac Williams, F. and N. Sloane, "The Theory of Error Correcting [5] Mac Williams, F. and N. Sloane, "The Theory of Error Correcting
Codes", North Holland, 1977 . Codes", North Holland, 1977 .
[6] Luby, M., Shokrollahi, A., Watson, M., and T. Stockhammer, [6] Luby, M., Shokrollahi, A., Watson, M., and T. Stockhammer,
"Raptor Forward Error Correction Scheme", Internet "Raptor Forward Error Correction Scheme", Internet
Draft draft-ietf-rmt-bb-fec-raptor-object-03 (work in Draft draft-ietf-rmt-bb-fec-raptor-object-04 (work in
progress), October 2005. progress), June 2006.
[7] Roca, V., Neumann, C., and D. Furodet, "Low Density Parity [7] Roca, V., Neumann, C., and D. Furodet, "Low Density Parity
Check (LDPC) Forward Error Correction", Check (LDPC) Forward Error Correction",
draft-ietf-rmt-bb-fec-ldpc-01.txt (work in progress), draft-ietf-rmt-bb-fec-ldpc-04.txt (work in progress),
March 2006. December 2006.
[8] Luby, M., Watson, M., and L. Vicisano, "Asynchronous Layered [8] Luby, M., Watson, M., and L. Vicisano, "Asynchronous Layered
Coding (ALC) Protocol Instantiation", Coding (ALC) Protocol Instantiation",
draft-ietf-rmt-pi-alc-revised-03.txt (work in progress), draft-ietf-rmt-pi-alc-revised-03.txt (work in progress),
April 2006. April 2006.
[9] Adamson, B., Bormann, C., Handley, M., and J. Macker, [9] Adamson, B., Bormann, C., Handley, M., and J. Macker,
"Negative-acknowledgment (NACK)-Oriented Reliable Multicast "Negative-acknowledgment (NACK)-Oriented Reliable Multicast
(NORM) Protocol", draft-ietf-rmt-pi-norm-revised-01.txt (work (NORM) Protocol", draft-ietf-rmt-pi-norm-revised-03.txt (work
in progress), March 2006. in progress), September 2006.
[10] Paila, T., Walsh, R., Luby, M., Lehtonen, R., and V. Roca, [10] Paila, T., Walsh, R., Luby, M., Lehtonen, R., and V. Roca,
"FLUTE - File Delivery over Unidirectional Transport", "FLUTE - File Delivery over Unidirectional Transport",
draft-ietf-rmt-flute-revised-01.txt (work in progress), draft-ietf-rmt-flute-revised-02.txt (work in progress),
January 2006. August 2006.
[11] Gohberg, I. and V. Olshevsky, "Fast algorithms with [11] Gohberg, I. and V. Olshevsky, "Fast algorithms with
preprocessing for matrix-vector multiplication problems", preprocessing for matrix-vector multiplication problems",
Journal of Complexity, pp. 411-427, vol. 10, 1994 . Journal of Complexity, pp. 411-427, vol. 10, 1994 .
Authors' Addresses Authors' Addresses
Jerome Lacan Jerome Lacan
ENSICA/LAAS-CNRS ENSICA/LAAS-CNRS
1, place Emile Blouin 1, place Emile Blouin
skipping to change at page 24, line 5 skipping to change at page 25, line 5
Sami Peltotalo Sami Peltotalo
Tampere University of Technology Tampere University of Technology
P.O. Box 553 (Korkeakoulunkatu 1) P.O. Box 553 (Korkeakoulunkatu 1)
Tampere FIN-33101 Tampere FIN-33101
Finland Finland
Email: sami.peltotalo@tut.fi Email: sami.peltotalo@tut.fi
URI: http://atm.tut.fi/mad URI: http://atm.tut.fi/mad
Intellectual Property Statement Full Copyright Statement
Copyright (C) The IETF Trust (2006).
This document is subject to the rights, licenses and restrictions
contained in BCP 78, and except as set forth therein, the authors
retain all their rights.
This document and the information contained herein are provided on an
"AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS
OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST AND
THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS
OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF
THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED
WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
Intellectual Property
The IETF takes no position regarding the validity or scope of any The IETF takes no position regarding the validity or scope of any
Intellectual Property Rights or other rights that might be claimed to Intellectual Property Rights or other rights that might be claimed to
pertain to the implementation or use of the technology described in pertain to the implementation or use of the technology described in
this document or the extent to which any license under such rights this document or the extent to which any license under such rights
might or might not be available; nor does it represent that it has might or might not be available; nor does it represent that it has
made any independent effort to identify any such rights. Information made any independent effort to identify any such rights. Information
on the procedures with respect to rights in RFC documents can be on the procedures with respect to rights in RFC documents can be
found in BCP 78 and BCP 79. found in BCP 78 and BCP 79.
skipping to change at page 24, line 29 skipping to change at page 25, line 45
such proprietary rights by implementers or users of this such proprietary rights by implementers or users of this
specification can be obtained from the IETF on-line IPR repository at specification can be obtained from the IETF on-line IPR repository at
http://www.ietf.org/ipr. http://www.ietf.org/ipr.
The IETF invites any interested party to bring to its attention any The IETF invites any interested party to bring to its attention any
copyrights, patents or patent applications, or other proprietary copyrights, patents or patent applications, or other proprietary
rights that may cover technology that may be required to implement rights that may cover technology that may be required to implement
this standard. Please address the information to the IETF at this standard. Please address the information to the IETF at
ietf-ipr@ietf.org. ietf-ipr@ietf.org.
Disclaimer of Validity
This document and the information contained herein are provided on an
"AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS
OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET
ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED,
INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE
INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED
WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
Copyright Statement
Copyright (C) The Internet Society (2006). This document is subject
to the rights, licenses and restrictions contained in BCP 78, and
except as set forth therein, the authors retain all their rights.
Acknowledgment Acknowledgment
Funding for the RFC Editor function is currently provided by the Funding for the RFC Editor function is provided by the IETF
Internet Society. Administrative Support Activity (IASA).
 End of changes. 37 change blocks. 
120 lines changed or deleted 145 lines changed or added

This html diff was produced by rfcdiff 1.33. The latest version is available from http://tools.ietf.org/tools/rfcdiff/