draft-ietf-rmt-bb-fec-ldpc-03.txt   draft-ietf-rmt-bb-fec-ldpc-04.txt 
RMT V. Roca RMT V. Roca
Internet-Draft INRIA Internet-Draft INRIA
Expires: January 19, 2007 C. Neumann Intended status: Experimental C. Neumann
Thomson Research Expires: June 25, 2007 Thomson Research
D. Furodet D. Furodet
STMicroelectronics STMicroelectronics
July 18, 2006 December 22, 2006
Low Density Parity Check (LDPC) Staircase and Triangle Forward Error Low Density Parity Check (LDPC) Staircase and Triangle Forward Error
Correction (FEC) Schemes Correction (FEC) Schemes
draft-ietf-rmt-bb-fec-ldpc-03.txt draft-ietf-rmt-bb-fec-ldpc-04.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 January 19, 2007. 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 two Fully-Specified FEC Schemes, LDPC- This document describes two Fully-Specified FEC Schemes, LDPC-
Staircase and LDPC-Triangle, and their application to the reliable Staircase and LDPC-Triangle, and their application to the reliable
delivery of objects on packet erasure channels. These systematic FEC delivery of objects on packet erasure channels. These systematic FEC
codes belong to the well known class of ``Low Density Parity Check'' codes belong to the well known class of ``Low Density Parity Check''
(LDPC) codes, and are large block FEC codes in these sense of (LDPC) codes, and are large block FEC codes in these sense of
RFC3453. RFC3453.
Table of Contents Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4
2. Requirements notation . . . . . . . . . . . . . . . . . . . . 4 2. Requirements notation . . . . . . . . . . . . . . . . . . . . 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 IDs . . . . . . . . . . . . . . . . . . . . . 7 4.1. FEC Payload IDs . . . . . . . . . . . . . . . . . . . . . 8
4.2. FEC Object Transmission Information . . . . . . . . . . . 7 4.2. FEC Object Transmission Information . . . . . . . . . . . 8
4.2.1. Mandatory Element . . . . . . . . . . . . . . . . . . 7 4.2.1. Mandatory Element . . . . . . . . . . . . . . . . . . 8
4.2.2. Common Elements . . . . . . . . . . . . . . . . . . . 7 4.2.2. Common Elements . . . . . . . . . . . . . . . . . . . 8
4.2.3. Scheme-Specific Elements . . . . . . . . . . . . . . . 8 4.2.3. Scheme-Specific Elements . . . . . . . . . . . . . . . 9
4.2.4. Encoding Format . . . . . . . . . . . . . . . . . . . 8 4.2.4. Encoding Format . . . . . . . . . . . . . . . . . . . 9
5. Procedures . . . . . . . . . . . . . . . . . . . . . . . . . . 11 5. Procedures . . . . . . . . . . . . . . . . . . . . . . . . . . 12
5.1. General . . . . . . . . . . . . . . . . . . . . . . . . . 11 5.1. General . . . . . . . . . . . . . . . . . . . . . . . . . 12
5.2. Determining the Maximum Source Block Length (B) . . . . . 12 5.2. Determining the Maximum Source Block Length (B) . . . . . 13
5.3. Determining the Encoding Symbol Length (E) and Number 5.3. Determining the Encoding Symbol Length (E) and Number
of Encoding Symbols per Group (G) . . . . . . . . . . . . 12 of Encoding Symbols per Group (G) . . . . . . . . . . . . 13
5.4. Determining the Number of Encoding Symbols of a Block . . 13 5.4. Determining the Number of Encoding Symbols of a Block . . 15
5.5. Identifying the Symbols of an Encoding Symbol Group . . . 15 5.5. Identifying the Symbols of an Encoding Symbol Group . . . 16
5.6. Pseudo Random Number Generator . . . . . . . . . . . . . . 18 5.6. Pseudo Random Number Generator . . . . . . . . . . . . . . 19
6. Full Specification of the LDPC-Staircase Scheme . . . . . . . 20 6. Full Specification of the LDPC-Staircase Scheme . . . . . . . 21
6.1. General . . . . . . . . . . . . . . . . . . . . . . . . . 20 6.1. General . . . . . . . . . . . . . . . . . . . . . . . . . 21
6.2. Parity Check Matrix Creation . . . . . . . . . . . . . . . 20 6.2. Parity Check Matrix Creation . . . . . . . . . . . . . . . 21
6.3. Encoding . . . . . . . . . . . . . . . . . . . . . . . . . 22 6.3. Encoding . . . . . . . . . . . . . . . . . . . . . . . . . 23
6.4. Decoding . . . . . . . . . . . . . . . . . . . . . . . . . 22 6.4. Decoding . . . . . . . . . . . . . . . . . . . . . . . . . 23
7. Full Specification of the LDPC-Triangle Scheme . . . . . . . . 24 7. Full Specification of the LDPC-Triangle Scheme . . . . . . . . 25
7.1. General . . . . . . . . . . . . . . . . . . . . . . . . . 24 7.1. General . . . . . . . . . . . . . . . . . . . . . . . . . 25
7.2. Parity Check Matrix Creation . . . . . . . . . . . . . . . 24 7.2. Parity Check Matrix Creation . . . . . . . . . . . . . . . 25
7.3. Encoding . . . . . . . . . . . . . . . . . . . . . . . . . 24 7.3. Encoding . . . . . . . . . . . . . . . . . . . . . . . . . 25
7.4. Decoding . . . . . . . . . . . . . . . . . . . . . . . . . 25 7.4. Decoding . . . . . . . . . . . . . . . . . . . . . . . . . 26
8. Security Considerations . . . . . . . . . . . . . . . . . . . 26 8. Security Considerations . . . . . . . . . . . . . . . . . . . 27
9. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 27 9. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 28
10. References . . . . . . . . . . . . . . . . . . . . . . . . . . 28 10. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 29
10.1. Normative References . . . . . . . . . . . . . . . . . . . 28 11. References . . . . . . . . . . . . . . . . . . . . . . . . . . 30
10.2. Informative References . . . . . . . . . . . . . . . . . . 28 11.1. Normative References . . . . . . . . . . . . . . . . . . . 30
Appendix A. Trivial Decoding Algorithm (Informative Only) . . . . 30 11.2. Informative References . . . . . . . . . . . . . . . . . . 30
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 32 Appendix A. Trivial Decoding Algorithm (Informative Only) . . . . 32
Intellectual Property and Copyright Statements . . . . . . . . . . 33 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 34
Intellectual Property and Copyright Statements . . . . . . . . . . 35
1. Introduction 1. Introduction
RFC 3453 [3] introduces large block FEC codes as an alternative to RFC 3453 [3] introduces large block FEC codes as an alternative to
small block FEC codes like Reed-Solomon. The main advantage of such small block FEC codes like Reed-Solomon. The main advantage of such
large block codes is the possibility to operate efficiently on source large block codes is the possibility to operate efficiently on source
blocks of size several tens of thousands (or more) source symbols. blocks of size several tens of thousands (or more) source symbols.
The present document introduces the Fully-Specified FEC Encoding ID The present document introduces the Fully-Specified FEC Encoding ID 3
XX that is intended to be used with the LDPC-Staircase FEC codes, and that is intended to be used with the LDPC-Staircase FEC codes, and
the Fully-Specified FEC Encoding ID YY that is intended to be used the Fully-Specified FEC Encoding ID 4 that is intended to be used
with the LDPC-Triangle FEC codes [4][7]. Both schemes belong to the with the LDPC-Triangle FEC codes [4][7]. Both schemes belong to the
broad class of large block codes. broad class of large block codes.
-- editor's note: This document makes use of the FEC Encoding ID
values XX and YY that will be specified after IANA assignment --
LDPC codes rely on a dedicated matrix, called a "Parity Check LDPC codes rely on a dedicated matrix, called a "Parity Check
Matrix", at the encoding and decoding ends. The parity check matrix Matrix", at the encoding and decoding ends. The parity check matrix
defines relationships (or constraints) between the various encoding defines relationships (or constraints) between the various encoding
symbols (i.e. source symbols and repair symbols), that are later used symbols (i.e. source symbols and repair symbols), that are later used
by the decoder to reconstruct the original k source symbols if some by the decoder to reconstruct the original k source symbols if some
of them are missing. These codes are systematic, in the sense that of them are missing. These codes are systematic, in the sense that
the encoding symbols include the source symbols in addition to the the encoding symbols include the source symbols in addition to the
repair symbols. repair symbols.
Since the encoder and decoder must operate on the same parity check Since the encoder and decoder must operate on the same parity check
skipping to change at page 7, line 35 skipping to change at page 8, line 35
same packet, the FEC Payload ID refers to the first symbol of the same packet, the FEC Payload ID refers to the first symbol of the
packet. The other symbols can be deduced from the ESI of the first packet. The other symbols can be deduced from the ESI of the first
symbol thanks to a dedicated function, as explained in Section 5.5 symbol thanks to a dedicated function, as explained in Section 5.5
0 1 2 3 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 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 (20 bits) | | Source Block Number | Encoding Symbol ID (20 bits) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 1: FEC Payload ID encoding format for FEC Encoding ID XX and Figure 1: FEC Payload ID encoding format for FEC Encoding ID 3 and 4
YY
4.2. FEC Object Transmission Information 4.2. FEC Object Transmission Information
4.2.1. Mandatory Element 4.2.1. Mandatory Element
o FEC Encoding ID: the LDPC-Staircase and LDPC-Triangle Fully- o FEC Encoding ID: the LDPC-Staircase and LDPC-Triangle Fully-
Specified FEC Schemes use respectively the FEC Encoding ID XX Specified FEC Schemes use respectively the FEC Encoding ID 3
(Staircase) and YY (Triangle). (Staircase) and 4 (Triangle).
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:
maximum transfer length = 2^^12 * B * E maximum transfer length = 2^^12 * B * E
skipping to change at page 9, line 24 skipping to change at page 10, line 24
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +
| Transfer-Length (L) | | Transfer-Length (L) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Encoding Symbol Length (E) | G | B (MSB) | | Encoding Symbol Length (E) | G | B (MSB) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| B (LSB) | Max Nb of Enc. Symbols (max_n) | | B (LSB) | Max Nb of Enc. Symbols (max_n) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
. Optional PRNG seed . . Optional PRNG seed .
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 2: EXT_FTI Header for FEC Encoding ID 132
In particular: In particular:
o The HEL (Header Extension Length) indicates whether the optional o The HEL (Header Extension Length) indicates whether the optional
PRNG seed is present (HEL=5) or not (HEL=4). PRNG seed is present (HEL=5) or not (HEL=4).
o The Transfer-Length (L) field size (48 bits) is larger than the o The Transfer-Length (L) field size (48 bits) is larger than the
size required to store the maximum transfer length (Section 4.2.2) size required to store the maximum transfer length (Section 4.2.2)
for field alignment purposes. for field alignment purposes.
o The Maximum-Source-Block-Length (B) field (20 bits) is split into o The Maximum-Source-Block-Length (B) field (20 bits) is split into
two parts: the 8 most significant bits (MSB) are in the third 32- two parts: the 8 most significant bits (MSB) are in the third 32-
bit word of the EXT_FTI, and the remaining 12 least significant bit word of the EXT_FTI, and the remaining 12 least significant
bits (LSB) are in fourth 32-bit word. bits (LSB) are in fourth 32-bit word.
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 [12], the following XML elements must be described a FLUTE session [12], the following XML attributes must be described
for the associated object: for the associated object:
o FEC-OTI-FEC-Encoding-ID
o FEC-OTI-Transfer-length o FEC-OTI-Transfer-length
o FEC-OTI-Encoding-Symbol-Length o FEC-OTI-Encoding-Symbol-Length
o FEC-OTI-Maximum-Source-Block-Length o FEC-OTI-Maximum-Source-Block-Length
o FEC-OTI-Max-Number-of-Encoding-Symbols o FEC-OTI-Max-Number-of-Encoding-Symbols
o FEC-OTI-Number-Encoding-Symbols-per-Group
o FEC-OTI-PRNG-seed (optional) o FEC-OTI-Scheme-Specific-Info
When no PRNG seed is to be carried in the FEC OTI, the sender simply The FEC-OTI-Scheme-Specific-Info contains the string resulting from
omits the FEC-OTI-PRNG-seed element. the Base64 encoding (in the XML Schema xs:base64Binary sense) of the
following value:
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| PRNG seed |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| G |
+-+-+-+-+-+-+-+-+
Figure 3: FEC OTI Scheme Specific Information to be Included in the
FDT Instance
When no PRNG seed is to be carried in the FEC OTI, the seed field is
set to 0 (which is not a valid seed value). Otherwise the seed field
contains a valid value as explained in Section 4.2.3.
After Base64 encoding, the 5 bytes of the FEC OTI Scheme Specific
Information are transformed into a string of 8 printable characters
(in the 64-character alphabet) and added to the FEC-OTI-Scheme-
Specific-Info attribute.
5. Procedures 5. Procedures
This section defines procedures that are common to FEC Encoding IDs This section defines procedures that are common to FEC Encoding IDs 3
XX and YY. and 4.
5.1. General 5.1. General
The B (maximum source block length in symbols) and E (encoding symbol The B (maximum source block length in symbols) and E (encoding symbol
length in bytes) parameters are first determined, as explained in the length in bytes) parameters are first determined, as explained in the
following sections. following sections.
The source object is then partitioned using the block partitioning The source object is then partitioned using the block partitioning
algorithm specified in [2]. To that purpose, the B, L (object algorithm specified in [2]. To that purpose, the B, L (object
transfer length in bytes), and E arguments are provided. As a transfer length in bytes), and E arguments are provided. As a
skipping to change at page 20, line 10 skipping to change at page 21, line 10
* than most significant bits [Numerical Recipies in C] */ * than most significant bits [Numerical Recipies in C] */
return ((unsigned long) return ((unsigned long)
((double)seed * (double)maxv / (double)0x7FFFFFFF)); ((double)seed * (double)maxv / (double)0x7FFFFFFF));
} }
6. Full Specification of the LDPC-Staircase Scheme 6. Full Specification of the LDPC-Staircase Scheme
6.1. General 6.1. General
The LDPC-Staircase scheme is identified by the Fully-Specified FEC The LDPC-Staircase scheme is identified by the Fully-Specified FEC
Encoding ID XX. Encoding ID 3.
The PRNG used by the LDPC-Staircase scheme must be initialized by a The PRNG used by the LDPC-Staircase scheme must be initialized by a
seed. This PRNG seed is an optional instance-specific FEC OTI seed. This PRNG seed is an optional instance-specific FEC OTI
element (Section 4.2.3). When this PRNG seed is not carried within attribute (Section 4.2.3). When this PRNG seed is not carried within
the FEC OTI, it is assumed that encoder and decoders either use the FEC OTI, it is assumed that encoder and decoders either use
another way to communicate the seed value or use a fixed, predefined another way to communicate the seed value or use a fixed, predefined
value. value.
6.2. Parity Check Matrix Creation 6.2. Parity Check Matrix Creation
The LDPC-Staircase matrix can be divided into two parts: the left The LDPC-Staircase matrix can be divided into two parts: the left
side of the matrix defines in which equations the source symbols are side of the matrix defines in which equations the source symbols are
involved; the right side of the matrix defines in which equations the involved; the right side of the matrix defines in which equations the
repair symbols are involved. repair symbols are involved.
skipping to change at page 23, line 9 skipping to change at page 24, line 9
another possible decoding technique. Hybrid solutions that start by another possible decoding technique. Hybrid solutions that start by
using the trivial algorithm above and finish with a Gauss elimination using the trivial algorithm above and finish with a Gauss elimination
are also possible. are also possible.
Because interoperability does not depend on the decoding algorithm Because interoperability does not depend on the decoding algorithm
used, the current document does not recommend any particular used, the current document does not recommend any particular
technique. This choice is left to the codec developer. technique. This choice is left to the codec developer.
Yet choosing a decoding technique will have great practical impacts. Yet choosing a decoding technique will have great practical impacts.
It will impact the erasure capabilities: a Gauss elimination It will impact the erasure capabilities: a Gauss elimination
technique enables to solve the system with a smaller number of technique enables to solve the system with a smaller number of known
symbols compared to the trivial technique. It will also impact the symbols compared to the trivial technique. It will also impact the
CPU load: a Gauss elimination technique requires much more processing CPU load: a Gauss elimination technique requires much more processing
than the trivial technique. Depending on the target use case, the than the trivial technique. Depending on the target use case, the
codec developer will favor one feature or the other. codec developer will favor one feature or the other.
7. Full Specification of the LDPC-Triangle Scheme 7. Full Specification of the LDPC-Triangle Scheme
7.1. General 7.1. General
LDPC-Triangle is identified by the Fully-Specified FEC Encoding ID LDPC-Triangle is identified by the Fully-Specified FEC Encoding ID 4.
YY.
The PRNG used by the LDPC-Triangle scheme must be initialized by a The PRNG used by the LDPC-Triangle scheme must be initialized by a
seed. This PRNG seed is an optional instance-specific FEC OTI seed. This PRNG seed is an optional instance-specific FEC OTI
element (Section 4.2.3). When this PRNG seed is not carried within attribute (Section 4.2.3). When this PRNG seed is not carried within
the FEC OTI, it is assumed that encoder and decoders either use the FEC OTI, it is assumed that encoder and decoders either use
another way to communicate the seed value or use a fixed, predefined another way to communicate the seed value or use a fixed, predefined
value. value.
7.2. Parity Check Matrix Creation 7.2. Parity Check Matrix Creation
The LDPC-Triangle matrix can be divided into two parts: the left side The LDPC-Triangle matrix can be divided into two parts: the left side
of the matrix defines in which equations the source symbols are of the matrix defines in which equations the source symbols are
involved; the right side of the matrix defines in which equations the involved; the right side of the matrix defines in which equations the
repair symbols are involved. repair symbols are involved.
skipping to change at page 27, line 5 skipping to change at page 28, line 5
Because interoperability does not depend on the decoding algorithm Because interoperability does not depend on the decoding algorithm
used, the current document does not recommend any particular used, the current document does not recommend any particular
technique. This choice is left to the codec implementer. technique. This choice is left to the codec implementer.
8. Security Considerations 8. 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].
9. Acknowledgments 9. IANA Considerations
Values of FEC Encoding IDs and FEC Instance IDs are subject to IANA
registration. For general guidelines on IANA considerations as they
apply to this document, see [2]. This document assigns the Fully-
Specified FEC Encoding ID 3 under the ietf:rmt:fec:encoding name-
space to "LDPC Staircase Codes", and the Fully-Specified FEC Encoding
ID 4 under the ietf:rmt:fec:encoding name-space to "LDPC Triangle
Codes".
10. Acknowledgments
Section 5.4 is derived from a previous Internet-Draft, and we would Section 5.4 is derived from a previous Internet-Draft, and we would
like to thank S. Peltotalo and J. Peltotalo for their contribution. like to thank S. Peltotalo and J. Peltotalo for their contribution.
We would also like to thank Pascal Moniot, Laurent Fazio, Aurelien We would also like to thank Pascal Moniot, Laurent Fazio, Aurelien
Francillon and Shao Wenjian for their comments. Francillon and Shao Wenjian for their comments.
10. References 11. References
10.1. Normative References 11.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, BCP 14, March 1997. Levels", RFC 2119, BCP 14, March 1997.
[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 11.2. Informative References
[4] Roca, V. and C. Neumann, "Design, Evaluation and Comparison of [4] Roca, V. and C. Neumann, "Design, Evaluation and Comparison of
Four Large Block FEC Codecs: LDPC, LDGM, LDGM-Staircase and Four Large Block FEC Codecs: LDPC, LDGM, LDGM-Staircase and
LDGM-Triangle, Plus a Reed-Solomon Small Block FEC Codec", LDGM-Triangle, Plus a Reed-Solomon Small Block FEC Codec",
INRIA Research Report RR-5225, June 2004. INRIA Research Report RR-5225, June 2004.
[5] Neumann, C., Roca, V., Francillon, A., and D. Furodet, "Impacts [5] Neumann, C., Roca, V., Francillon, A., and D. Furodet, "Impacts
of Packet Scheduling and Packet Loss Distribution on FEC of Packet Scheduling and Packet Loss Distribution on FEC
Performances: Observations and Recommendations", ACM CoNEXT'05 Performances: Observations and Recommendations", ACM CoNEXT'05
Conference, Toulouse, France (an extended version is available Conference, Toulouse, France (an extended version is available
skipping to change at page 29, line 13 skipping to change at page 31, line 14
from Problemy Peredachi Informatsii, Vol.10, No. 1, pp.15-28, from Problemy Peredachi Informatsii, Vol.10, No. 1, pp.15-28,
January-March 1974. January-March 1974.
[11] Luby, M., Watson, M., and L. Vicisano, "Asynchronous Layered [11] 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.
[12] Paila, T., Walsh, R., Luby, M., Lehtonen, R., and V. Roca, [12] 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.
[13] Adamson, B., Bormann, C., Handley, M., and J. Macker, [13] 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-02.txt (work (NORM) Protocol", draft-ietf-rmt-pi-norm-revised-03.txt (work
in progress), June 2006. in progress), September 2006.
Appendix A. Trivial Decoding Algorithm (Informative Only) Appendix A. Trivial Decoding Algorithm (Informative Only)
A trivial decoding algorithm is sketched below (please see [6] for A trivial decoding algorithm is sketched below (please see [6] for
the details omitted here): the details omitted here):
Initialization: allocate a table partial_sum[n-k] of buffers, each Initialization: allocate a table partial_sum[n-k] of buffers, each
buffer being of size the symbol size. There's one buffer being of size the symbol size. There's one
entry per equation since the buffers are meant to entry per equation since the buffers are meant to
store the partial sum of each equation; Reset all store the partial sum of each equation; Reset all
skipping to change at page 33, line 5 skipping to change at page 35, line 5
David Furodet David Furodet
STMicroelectronics STMicroelectronics
12, Rue Jules Horowitz 12, Rue Jules Horowitz
BP217 BP217
Grenoble Cedex 38019 Grenoble Cedex 38019
France France
Email: david.furodet@st.com Email: david.furodet@st.com
URI: http://www.st.com/ URI: http://www.st.com/
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 33, line 29 skipping to change at page 35, 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. 35 change blocks. 
98 lines changed or deleted 128 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/