draft-ietf-rmt-bb-fec-ldpc-05.txt   draft-ietf-rmt-bb-fec-ldpc-06.txt 
RMT V. Roca RMT V. Roca
Internet-Draft INRIA Internet-Draft INRIA
Intended status: Experimental C. Neumann Intended status: Experimental C. Neumann
Expires: September 30, 2007 Thomson Research Expires: November 8, 2007 Thomson Research
D. Furodet D. Furodet
STMicroelectronics STMicroelectronics
March 29, 2007 May 7, 2007
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-05.txt draft-ietf-rmt-bb-fec-ldpc-06.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 September 30, 2007. This Internet-Draft will expire on November 8, 2007.
Copyright Notice Copyright Notice
Copyright (C) The IETF Trust (2007). Copyright (C) The IETF Trust (2007).
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 the sense of RFC3453.
RFC3453.
Table of Contents Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4
2. Requirements notation . . . . . . . . . . . . . . . . . . . . 5 2. Requirements notation . . . . . . . . . . . . . . . . . . . . 5
3. Definitions, Notations and Abbreviations . . . . . . . . . . . 6 3. Definitions, Notations and Abbreviations . . . . . . . . . . . 6
3.1. Definitions . . . . . . . . . . . . . . . . . . . . . . . 6 3.1. Definitions . . . . . . . . . . . . . . . . . . . . . . . 6
3.2. Notations . . . . . . . . . . . . . . . . . . . . . . . . 6 3.2. Notations . . . . . . . . . . . . . . . . . . . . . . . . 6
3.3. Abbreviations . . . . . . . . . . . . . . . . . . . . . . 7 3.3. Abbreviations . . . . . . . . . . . . . . . . . . . . . . 7
4. Formats and Codes . . . . . . . . . . . . . . . . . . . . . . 8 4. Formats and Codes . . . . . . . . . . . . . . . . . . . . . . 8
skipping to change at page 4, line 14 skipping to change at page 4, line 14
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 3 The present document introduces the Fully-Specified FEC Encoding ID 3
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 4 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 [6][9]. Both schemes belong to the
broad class of large block codes. broad class of large block codes.
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
matrix, information must be communicated between them as part of the matrix, information must be communicated between them as part of the
FEC Object Transmission Information. FEC Object Transmission Information.
A publicly available reference implementation of these codes is A publicly available reference implementation of these codes is
available and distributed under a GNU/LGPL license [6]. available and distributed under a GNU/LGPL license [8].
2. Requirements notation 2. Requirements notation
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in [1]. document are to be interpreted as described in [1].
3. Definitions, Notations and Abbreviations 3. Definitions, Notations and Abbreviations
3.1. Definitions 3.1. Definitions
skipping to change at page 10, line 8 skipping to change at page 10, line 8
4.2.4. Encoding Format 4.2.4. Encoding Format
This section shows two possible encoding formats of the above FEC This section shows two possible encoding formats of the above FEC
OTI. The present document does not specify when or how these OTI. The present document does not specify when or how these
encoding formats should be used. encoding formats should be used.
4.2.4.1. Using the General EXT_FTI Format 4.2.4.1. Using the General EXT_FTI Format
The FEC OTI binary format is the following, when the EXT_FTI The FEC OTI binary format is the following, when the EXT_FTI
mechanism is used (e.g. within the ALC [11] or NORM [13] protocols). mechanism is used (e.g. within the ALC [13] or NORM [15] protocols).
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| HET = 64 | HEL (=4 or 5) | | | HET = 64 | HEL (=4 or 5) | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +
| Transfer-Length (L) | | Transfer-Length (L) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Encoding Symbol Length (E) | G | B (MSB) | | Encoding Symbol Length (E) | G | B (MSB) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
skipping to change at page 10, line 43 skipping to change at page 10, line 43
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 the fourth 32-bit word. bits (LSB) are in the 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 attributes must be described a FLUTE session [14], the following XML attributes must be described
for the associated object: for the associated object:
o FEC-OTI-FEC-Encoding-ID 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
skipping to change at page 12, line 48 skipping to change at page 12, line 48
(i,j) (i.e. at row i and column j) means that the symbol with ESI i (i,j) (i.e. at row i and column j) means that the symbol with ESI i
appears in equation j of the system. The only difference between the appears in equation j of the system. The only difference between the
LDPC-Staircase and LDPC-Triangle schemes is the construction of the LDPC-Staircase and LDPC-Triangle schemes is the construction of the
right sub-matrix. right sub-matrix.
When the parity symbols have been created, the sender will transmit When the parity symbols have been created, the sender will transmit
source and parity symbols. The way this transmission occurs can source and parity symbols. The way this transmission occurs can
largely impact the erasure recovery capabilities of the LDPC-* FEC. largely impact the erasure recovery capabilities of the LDPC-* FEC.
In particular, sending parity symbols in sequence is suboptimal. In particular, sending parity symbols in sequence is suboptimal.
Instead it is usually recommended the shuffle these symbols. The Instead it is usually recommended the shuffle these symbols. The
interested reader will find more details in [5]. interested reader will find more details in [7].
The following sections detail how the B, E, and n parameters are The following sections detail how the B, E, and n parameters are
determined (respectively in Section 5.2, Section 5.3 and determined (respectively in Section 5.2, Section 5.3 and
Section 5.4), how encoding symbol groups are created (Section 5.5), Section 5.4), how encoding symbol groups are created (Section 5.5),
and finally specify the PRNG (Section 5.6). and finally specify the PRNG (Section 5.6).
5.2. Determining the Maximum Source Block Length (B) 5.2. Determining the Maximum Source Block Length (B)
The B parameter (maximum source block length in symbols) depends on The B parameter (maximum source block length in symbols) depends on
several parameters: the code rate (rate), the Encoding Symbol ID several parameters: the code rate (rate), the Encoding Symbol ID
skipping to change at page 19, line 39 skipping to change at page 19, line 39
% (n - k)]; % (n - k)];
} }
} }
} }
5.6. Pseudo Random Number Generator 5.6. Pseudo Random Number Generator
The present FEC Encoding ID relies on a pseudo-random number The present FEC Encoding ID relies on a pseudo-random number
generator (PRNG) that must be fully specified, in particular in order generator (PRNG) that must be fully specified, in particular in order
to enable the receivers and the senders to build the same parity to enable the receivers and the senders to build the same parity
check matrix. The minimal standard generator [8] is used. It check matrix. The minimal standard generator [10] is used. It
defines a simple multiplicative congruential algorithm: Ij+1 = A * Ij defines a simple multiplicative congruential algorithm: Ij+1 = A * Ij
(modulo M), with the following choices: A = 7^^5 = 16807 and M = (modulo M), with the following choices: A = 7^^5 = 16807 and M =
2^^31 - 1 = 2147483647. Several implementations of this PRNG are 2^^31 - 1 = 2147483647. Several implementations of this PRNG are
known and discussed in the literature. All of them provide the same known and discussed in the literature. All of them provide the same
sequence of pseudo random numbers. A validation criteria of such a sequence of pseudo random numbers. A validation criteria of such a
PRNG is the following: if seed = 1, then the 10,000th value returned PRNG is the following: if seed = 1, then the 10,000th value returned
MUST be equal to 1043618065. MUST be equal to 1043618065.
The following implementation uses the Park and Miller algorithm with The following implementation uses the Park and Miller algorithm with
the optimization suggested by D. Carta in [9]. the optimization suggested by D. Carta in [11].
unsigned long seed; unsigned long seed;
/* /*
* Initialize the PRNG with a seed between * Initialize the PRNG with a seed between
* 1 and 0x7FFFFFFE (i.e. 2^^31-2) inclusive. * 1 and 0x7FFFFFFE (i.e. 2^^31-2) inclusive.
*/ */
void srand (unsigned long s) void srand (unsigned long s)
{ {
if ((s > 0) && (s < 0x7FFFFFFF)) if ((s > 0) && (s < 0x7FFFFFFF))
skipping to change at page 20, line 44 skipping to change at page 20, line 44
unsigned long hi, lo; unsigned long hi, lo;
lo = 16807 * (seed & 0xFFFF); lo = 16807 * (seed & 0xFFFF);
hi = 16807 * (seed >> 16); /* binary shift to right */ hi = 16807 * (seed >> 16); /* binary shift to right */
lo += (hi & 0x7FFF) < < 16; /* binary shift to left */ lo += (hi & 0x7FFF) < < 16; /* binary shift to left */
lo += hi >> 15; lo += hi >> 15;
if (lo > 0x7FFFFFFF) if (lo > 0x7FFFFFFF)
lo -= 0x7FFFFFFF; lo -= 0x7FFFFFFF;
seed = (long)lo; seed = (long)lo;
/* don't use modulo, least significant bits are less random /* don't use modulo, least significant bits are less random
* than most significant bits [Numerical Recipies in C] */ * than most significant bits [Numerical Recipes 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 3. Encoding ID 3.
skipping to change at page 23, line 17 skipping to change at page 23, line 17
and generate repair symbol with ESI i before symbol ESI i+1. and generate repair symbol with ESI i before symbol ESI i+1.
6.4. Decoding 6.4. Decoding
Decoding basically consists in solving a system of n-k linear Decoding basically consists in solving a system of n-k linear
equations whose variables are the n source and repair symbols. Of equations whose variables are the n source and repair symbols. Of
course, the final goal is to recover the value of the k source course, the final goal is to recover the value of the k source
symbols only. symbols only.
To that purpose, many techniques are possible. One of them is the To that purpose, many techniques are possible. One of them is the
following trivial algorithm [10]: given a set of linear equations, if following trivial algorithm [12]: given a set of linear equations, if
one of them has only one remaining unknown variable, then the value one of them has only one remaining unknown variable, then the value
of this variable is that of the constant term. So, replace this of this variable is that of the constant term. So, replace this
variable by its value in all the remaining linear equations and variable by its value in all the remaining linear equations and
reiterate. The value of several variables can therefore be found reiterate. The value of several variables can therefore be found
recursively. Applied to LDPC FEC codes working over an erasure recursively. Applied to LDPC FEC codes working over an erasure
channel, the parity check matrix defines a set of linear equations channel, the parity check matrix defines a set of linear equations
whose variables are the source symbols and repair symbols. Receiving whose variables are the source symbols and repair symbols. Receiving
or decoding a symbol is equivalent to having the value of a variable. or decoding a symbol is equivalent to having the value of a variable.
Appendix A sketches a possible implementation of this algorithm. Appendix A sketches a possible implementation of this algorithm.
skipping to change at page 26, line 7 skipping to change at page 26, line 7
course, the final goal is to recover the value of the k source course, the final goal is to recover the value of the k source
symbols only. To that purpose, many techniques are possible, as symbols only. To that purpose, many techniques are possible, as
explained in Section 6.4. explained in Section 6.4.
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 Data delivery can be subject to denial-of-service attacks by
[2]. attackers which send corrupted packets that are accepted as
legitimate by receivers. This is particularly a concern for
multicast delivery because a corrupted packet may be injected into
the session close to the root of the multicast tree, in which case
the corrupted packet will arrive at many receivers. This is
particularly a concern for the FEC building block because the use of
even one corrupted packet containing encoding data may result in the
decoding of an object that is completely corrupted and unusable. It
is thus RECOMMENDED that source authentication and integrity checking
are applied to decoded objects before delivering objects to an
application. For example, a SHA-1 hash [4] of an object may be
appended before transmission, and the SHA-1 hash is computed and
checked after the object is decoded but before it is delivered to an
application. Source authentication SHOULD be provided, for example
by including a digital signature verifiable by the receiver computed
on top of the hash value. It is also RECOMMENDED that a packet
authentication protocol such as TESLA [5] be used to detect and
discard corrupted packets upon arrival. Furthermore, it is
RECOMMENDED that Reverse Path Forwarding checks be enabled in all
network routers and switches along the path from the sender to
receivers to limit the possibility of a bad agent successfully
injecting a corrupted packet into the multicast tree data path.
Another security concern is that some FEC information may be obtained
by receivers out-of-band in a session description, and if the session
description is forged or corrupted then the receivers will not use
the correct protocol for decoding content from received packets. To
avoid these problems, it is RECOMMENDED that measures be taken to
prevent receivers from accepting incorrect session descriptions,
e.g., by using source authentication to ensure that receivers only
accept legitimate session descriptions from authorized senders.
9. IANA Considerations 9. 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].
Specified FEC Encoding ID 3 under the ietf:rmt:fec:encoding name-
space to "LDPC Staircase Codes", and the Fully-Specified FEC Encoding This document assigns the Fully-Specified FEC Encoding ID 3 under the
ID 4 under the ietf:rmt:fec:encoding name-space to "LDPC Triangle "ietf:rmt:fec:encoding" name-space to "LDPC Staircase Codes".
Codes".
This document assigns the Fully-Specified FEC Encoding ID 4 under the
"ietf:rmt:fec:encoding" name-space to "LDPC Triangle Codes".
10. Acknowledgments 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.
11. References 11. References
11.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 [2] Watson, M., Luby, M., and L. Vicisano, "Forward Error
Correction (FEC) Building Block", Correction (FEC) Building Block",
draft-ietf-rmt-fec-bb-revised-06.txt (work in progress), draft-ietf-rmt-fec-bb-revised-07.txt (work in progress),
March 2007. April 2007.
[3] Luby, M., Vicisano, L., Gemmell, J., Rizzo, L., Handley, M., [3] Luby, M., Vicisano, L., Gemmell, J., Rizzo, L., Handley, M.,
and 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.
[4] "HMAC: Keyed-Hashing for Message Authentication", RFC 2104,
February 1997.
[5] "Timed Efficient Stream Loss-Tolerant Authentication (TESLA):
Multicast Source Authentication Transform Introduction",
RFC 4082, June 2005.
11.2. Informative References 11.2. Informative References
[4] Roca, V. and C. Neumann, "Design, Evaluation and Comparison of [6] 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 [7] 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
as INRIA Research Report RR-5578), October 2005. as INRIA Research Report RR-5578), October 2005.
[6] Roca, V., Neumann, C., and J. Laboure, "LDPC-Staircase/ [8] Roca, V., Neumann, C., and J. Laboure, "LDPC-Staircase/
LDPC-Triangle Codec Reference Implementation", INRIA Rhone- LDPC-Triangle Codec Reference Implementation", INRIA Rhone-
Alpes and STMicroelectronics, Alpes and STMicroelectronics,
http://planete-bcast.inrialpes.fr/. http://planete-bcast.inrialpes.fr/.
[7] MacKay, D., "Information Theory, Inference and Learning [9] MacKay, D., "Information Theory, Inference and Learning
Algorithms", Cambridge University Press, ISBN: 0521642981, Algorithms", Cambridge University Press, ISBN: 0521642981,
2003. 2003.
[8] Park, S. and K. Miller, "Random Number Generators: Good Ones [10] Park, S. and K. Miller, "Random Number Generators: Good Ones
are Hard to Find", Communications of the ACM, Vol. 31, No. 10, are Hard to Find", Communications of the ACM, Vol. 31, No. 10,
pp.1192-1201, 1988. pp.1192-1201, 1988.
[9] Carta, D., "Two Fast Implementations of the Minimal Standard [11] Carta, D., "Two Fast Implementations of the Minimal Standard
Random Number Generator", Communications of the ACM, Vol. 33, Random Number Generator", Communications of the ACM, Vol. 33,
No. 1, pp.87-88, January 1990. No. 1, pp.87-88, January 1990.
[10] Zyablov, V. and M. Pinsker, "Decoding Complexity of Low-Density [12] Zyablov, V. and M. Pinsker, "Decoding Complexity of Low-Density
Codes for Transmission in a Channel with Erasures", Translated Codes for Transmission in a Channel with Erasures", Translated
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 [13] Luby, M., Watson, M., and L. Vicisano, "Asynchronous Layered
Coding (ALC) Protocol Instantiation", Coding (ALC) Protocol Instantiation",
draft-ietf-rmt-pi-alc-revised-04.txt (work in progress), draft-ietf-rmt-pi-alc-revised-04.txt (work in progress),
February 2007. February 2007.
[12] Paila, T., Walsh, R., Luby, M., Lehtonen, R., and V. Roca, [14] 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-03.txt (work in progress), draft-ietf-rmt-flute-revised-03.txt (work in progress),
January 2007. January 2007.
[13] Adamson, B., Bormann, C., Handley, M., and J. Macker, [15] 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-04.txt (work (NORM) Protocol", draft-ietf-rmt-pi-norm-revised-04.txt (work
in progress), March 2007. in progress), March 2007.
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 [8] 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
the buffers to zero; the buffers to zero;
/* /*
* For each newly received or decoded symbol, try to make progress * For each newly received or decoded symbol, try to make progress
skipping to change at page 33, line 10 skipping to change at page 33, line 10
Free the list of equations having symbols decoded; Free the list of equations having symbols decoded;
Return; Return;
} }
Authors' Addresses Authors' Addresses
Vincent Roca Vincent Roca
INRIA INRIA
655, av. de l'Europe 655, av. de l'Europe
Zirst; Montbonnot Inovallee; Montbonnot
ST ISMIER cedex 38334 ST ISMIER cedex 38334
France France
Email: vincent.roca@inrialpes.fr Email: vincent.roca@inrialpes.fr
URI: http://planete.inrialpes.fr/~roca/ URI: http://planete.inrialpes.fr/~roca/
Christoph Neumann Christoph Neumann
Thomson Research Thomson Research
46, Quai A. Le Gallo 46, Quai A. Le Gallo
Boulogne Cedex 92648 Boulogne Cedex 92648
 End of changes. 30 change blocks. 
36 lines changed or deleted 74 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/