 1/draftietfrmtbbfecldpc01.txt 20060623 01:14:31.000000000 +0200
+++ 2/draftietfrmtbbfecldpc02.txt 20060623 01:14:31.000000000 +0200
@@ 1,21 +1,22 @@
RMT V. Roca
InternetDraft INRIA
Expires: August 5, 2006 C. Neumann
+Expires: December 23, 2006 C. Neumann
Thomson Research
D. Furodet
STMicroelectronics
 February 2006
+ June 21, 2006
 Low Density Parity Check (LDPC) Forward Error Correction
 draftietfrmtbbfecldpc01.txt
+ Low Density Parity Check (LDPC) Staircase and Triangle Forward Error
+ Correction (FEC) Schemes
+ draftietfrmtbbfecldpc02.txt
Status of this Memo
By submitting this InternetDraft, each author represents that any
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
aware will be disclosed, in accordance with Section 6 of BCP 79.
InternetDrafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that
@@ 26,21 +27,21 @@
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use InternetDrafts as reference
material or to cite them other than as "work in progress."
The list of current InternetDrafts can be accessed at
http://www.ietf.org/ietf/1idabstracts.txt.
The list of InternetDraft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html.
 This InternetDraft will expire on August 5, 2006.
+ This InternetDraft will expire on December 23, 2006.
Copyright Notice
Copyright (C) The Internet Society (2006).
Abstract
This document describes two FullySpecified FEC Schemes, LDPC
Staircase and LDPCTriangle, and their application to the reliable
delivery of objects on packet erasure channels. These systematic FEC
@@ 75,77 +76,72 @@
6.1. General . . . . . . . . . . . . . . . . . . . . . . . . . 20
6.2. Parity Check Matrix Creation . . . . . . . . . . . . . . . 20
6.3. Encoding . . . . . . . . . . . . . . . . . . . . . . . . . 22
6.4. Decoding . . . . . . . . . . . . . . . . . . . . . . . . . 22
7. Full Specification of the LDPCTriangle Scheme . . . . . . . . 24
7.1. General . . . . . . . . . . . . . . . . . . . . . . . . . 24
7.2. Parity Check Matrix Creation . . . . . . . . . . . . . . . 24
7.3. Encoding . . . . . . . . . . . . . . . . . . . . . . . . . 24
7.4. Decoding . . . . . . . . . . . . . . . . . . . . . . . . . 25
8. Security Considerations . . . . . . . . . . . . . . . . . . . 26
 9. Intellectual Property . . . . . . . . . . . . . . . . . . . . 27
 10. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 28
 11. References . . . . . . . . . . . . . . . . . . . . . . . . . . 29
 11.1. Normative References . . . . . . . . . . . . . . . . . . . 29
 11.2. Informative References . . . . . . . . . . . . . . . . . . 29
 Appendix A. Trivial Decoding Algorithm (Informative Only) . . . . 31
+ 9. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 27
+ 10. References . . . . . . . . . . . . . . . . . . . . . . . . . . 28
+ 10.1. Normative References . . . . . . . . . . . . . . . . . . . 28
+ 10.2. Informative References . . . . . . . . . . . . . . . . . . 28
+ Appendix A. Trivial Decoding Algorithm (Informative Only) . . . . 30
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 32
Intellectual Property and Copyright Statements . . . . . . . . . . 33
1. Introduction
 RFC 3453 [RFC3453] introduces large block FEC codes as an alternative
 to small block FEC codes like ReedSolomon. The main advantage of
 such large block codes is the possibility to operate efficiently on
 source blocks of size several tens of thousands (or more) source
 symbols. The present document introduces the FullySpecified FEC
 Encoding ID XX that is intended to be used with the "Low Density
 Parity Check" (LDPC) Staircase FEC codes, and the FullySpecified FEC
 Encoding ID YY that is intended to be used with the "Low Density
 Parity Check" (LDPC)Triangle FEC codes [Roca04][Mac03]. Both
 schemes belong the broad class of large block codes.
+ RFC 3453 [3] introduces large block FEC codes as an alternative to
+ small block FEC codes like ReedSolomon. The main advantage of such
+ large block codes is the possibility to operate efficiently on source
+ blocks of size several tens of thousands (or more) source symbols.
+ The present document introduces the FullySpecified FEC Encoding ID
+ XX that is intended to be used with the "Low Density Parity Check"
+ (LDPC) Staircase FEC codes, and the FullySpecified FEC Encoding ID
+ YY that is intended to be used with the "Low Density Parity Check"
+ (LDPC)Triangle FEC codes [4][7]. Both schemes belong the 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
Matrix", at the encoding and decoding ends. The parity check matrix
defines relationships (or constraints) between the various encoding
symbols (i.e. source symbols and repair symbols), that are later used
by the decoder to reconstruct the original k source symbols if some
of them are missing. These codes are systematic, in the sense that
the encoding symbols include the source symbols in addition to the
 redundant symbols.
+ repair symbols.
Since the encoder and decoder must operate on the same parity check
 matrix, some information must be communicated between them, as part
 of the FEC Object Transmission information.
+ matrix, information must be communicated between them as part of the
+ FEC Object Transmission information.
A publicly available reference implementation of these codes is
 available and distributed under a GNU/LGPL license [LDPCrefimpl]. To
 the best of our knowledge, there is no patent or patent application
 identified as being used in the LDPCStaircase and LDPCTriangle FEC
 schemes.
+ available and distributed under a GNU/LGPL license [6].
2. Requirements notation
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
 document are to be interpreted as described in [RFC2119].
+ document are to be interpreted as described in [1].
3. Definitions, Notations and Abbreviations
3.1. Definitions
This document uses the same terms and definitions as those specified
 in [fecbbrevised]. Additionally, it uses the following
 definitions:
+ in [2]. Additionally, it uses the following definitions:
Encoding Symbol Group: a group of encoding symbols that are sent
together, within the same packet, and whose relationships to the
source object can be derived from a single Encoding Symbol ID.
Source Packet: a data packet containing only source symbols.
Repair Packet: a data packet containing only repair symbols.
3.2. Notations
@@ 164,27 +160,28 @@
B denotes the maximum source block length in symbols, i.e. the
maximum number of source symbols per source block
N denotes the number of source blocks into which the object shall
be partitioned
G denotes the number of encoding symbols per group, i.e. the
number of symbols sent in the same packet
 rate denotes the socalled "code rate", i.e. the k/n ratio
+ rate denotes the "code rate", i.e. the k/n ratio
 max_n Maximum Number of Encoding Symbols generated for any source
 block
+ max_n denotes the maximum number of encoding symbols generated for
+ any source block
srand(s) denotes the initialization function of the pseudorandom
number generator, where s is the seed (s > 0)
+
rand(m) denotes a pseudorandom number generator, that returns a
new random integer in [0; m1] each time it is called
3.3. Abbreviations
This document uses the following abbreviations:
ESI: Encoding Symbol ID
FEC OTI: FEC Object Transmission Information
@@ 235,21 +232,23 @@
The following elements MUST be defined with the present FEC Scheme:
o TransferLength (L): a nonnegative integer indicating the length
of the object in bytes. There are some restrictions on the
maximum TransferLength that can be supported:
maximum transfer length = 2^^12 * B * E
For instance, if B=2^^19 (because of a code rate of 1/2,
Section 5.2), and if E=1024 bytes, then the maximum transfer
 length is 2^^41 bytes.
+ length is 2^^41 bytes (or 2 TB). The upper limit, with symbols of
+ size 2^^161 bytes and a code rate larger or equal to 1/2, amounts
+ to 2^^47 bytes (or 128 TB).
o EncodingSymbolLength (E): a nonnegative integer indicating the
length of each encoding symbol in bytes.
o MaximumSourceBlockLength (B): a nonnegative integer indicating
the maximum number of source symbols in a source block. There are
some restrictions on the maximum B value, as explained in
Section 5.2.
o MaxNumberofEncodingSymbols (max_n): a nonnegative integer
@@ 263,24 +262,25 @@
4.2.3. SchemeSpecific Element
The following element MUST be defined with the present FEC Scheme.
It contains two distinct pieces of information:
o G: a nonnegative integer indicating the number of encoding
symbols per group used for the object. The default value is 1,
meaning that each packet contains exactly one symbol. Values
greater than 1 can also be defined, as explained in Section 5.3.
 o PRNG seed: The seed is a 32 bit value used to initialize the
 Pseudo Random Number Generator (defined in Section 5.6). This
+ o PRNG seed: The seed is a 32 bit unsigned integer between 1 and
+ 0x7FFFFFFE (i.e. 2^^312) inclusive. This value is used to
+ initialize the Pseudo Random Number Generator (Section 5.6). This
element is optional. Whether or not it is present in the FEC OTI
 will be signaled in the associated encoding format through an
+ is signaled in the associated encoding format through an
appropriate mechanism (see Section 4.2.4). When the PRNG seed is
not carried within the FEC OTI, it is assumed that encoder and
decoders use another way to communicate the information, or use a
fixed, predefined value.
4.2.4. Encoding Format
This section shows two possible encoding formats of the above FEC
OTI. The present document does not specify when or how these
encoding formats should be used.
@@ 302,24 +302,28 @@
 B (LSB)  Max Nb of Enc. Symbols (max_n) 
+++++++++++++++++++++++++++++++++
. Optional PRNG seed .
+++++++++++++++++++++++++++++++++
In particular:
o The HEL (Header Extension Length) indicates whether the optional
PRNG seed is present (HEL=5) or not (HEL=4).
 o The MaximumSourceBlockLength (B) is split into two parts: the 8
 most significant bits (MSB) are in the third 32bit word of the
 EXT_FTI, and the remaining 12 least significant bits (LSB) are in
 fourth 32bit word.
+ o The TransferLength (L) field size (48 bits) is larger than the
+ size required to store the maximum transfer length (Section 4.2.2)
+ for field alignment purposes.
+
+ o The MaximumSourceBlockLength (B) field (20 bits) is split into
+ 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
+ bits (LSB) are in fourth 32bit word.
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
a FLUTE session, the following XML elements must be described for the
associated object:
o FECOTITransferlength
o FECOTIEncodingSymbolLength
@@ 340,27 +343,27 @@
This section defines procedures that are common to FEC Encoding IDs
XX and YY.
5.1. General
The B (maximum source block length in symbols) and E (encoding symbol
length in bytes) parameters are first determined, as explained in the
following sections.
The source object is then partitioned using the block partitioning
 algorithm specified in [fecbbrevised]. To that purpose, the B, L
 (object transfer length in bytes), and E arguments are provided. As
 a result, the object is partitioned into N source blocks. These
 blocks are numbered consecutively from 0 to N1. The first I source
 blocks consist of A_large source symbols, the remaining NI source
 blocks consist of A_small source symbols. Each source symbol is E
 bytes in length, except perhaps the last symbol which may be shorter.
+ algorithm specified in [2]. To that purpose, the B, L (object
+ transfer length in bytes), and E arguments are provided. As a
+ result, the object is partitioned into N source blocks. These blocks
+ are numbered consecutively from 0 to N1. The first I source blocks
+ consist of A_large source symbols, the remaining NI source blocks
+ consist of A_small source symbols. Each source symbol is E bytes in
+ length, except perhaps the last symbol which may be shorter.
For each block the actual number of encoding symbols is determined,
as explained in the following section.
Then, FEC encoding and decoding can be done block per block,
independently. To that purpose, a parity check matrix is created,
that forms a system of linear equations between the repair and source
symbols of a given block, where the basic operator is XOR.
This parity check matrix is logically divided into two parts: the
@@ 371,21 +374,21 @@
(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
LDPCStaircase and LDPCTriangle schemes is the construction of the
right submatrix.
When the parity symbols have been created, the sender will transmit
source and parity symbols. The way this transmission occurs can
largely impact the erasure recovery capabilities of the LDPC* FEC.
In particular, sending parity symbols in sequence is suboptimal.
Instead it is usually recommended the shuffle these symbols. The
 interested reader will find more details in [Neumann05].
+ interested reader will find more details in [5].
The following sections detail how the B, E, and n parameters are
determined (respectively Section 5.2, Section 5.3 and Section 5.4),
how encoding symbol groups are created (Section 5.5), and finally
specify the PRNG (Section 5.6).
5.2. Determining the Maximum Source Block Length (B)
The B parameter (maximum source block length in symbols) depends on
several parameters: the code rate (rate), the Encoding Symbol ID
@@ 404,24 +407,25 @@
o 1 > rate >= 1/2: max1_B = 2 ^^ 19 = 524,288 symbols
o 1/2 > rate >= 1/4: max1_B = 2 ^^ 18 = 262,144 symbols
o 1/4 > rate >= 1/8: max1_B = 2 ^^ 17 = 131,072 symbols
Additionally, a codec MAY impose other limitations on the maximum
block size. This is the case for instance when the codec uses
internally 16 bit integers to store the Encoding Symbol ID, since it
does not enable to store all the possible values of a 20 bit field.
 Other limitations may also apply, for instance because of a limited
 working memory size. This decision SHOULD be clarified at
 implementation time, when the target use case is known. This results
 in a max2_B limitation.
+ In that case, if for instance 1 > rate >= 1/2, then the maximum block
+ size is 2^^15. Other limitations may also apply, for instance
+ because of a limited working memory size. This decision MUST be
+ clarified at implementation time, when the target use case is known.
+ This results in a max2_B limitation.
Then, B is given by:
B = min(max1_B, max2_B)
Note that this calculation is only required at the coder, since the B
parameter is communicated to the decoder through the FEC OTI.
5.3. Determining the Encoding Symbol Length (E) and Number of Encoding
Symbols per Group (G)
@@ 450,23 +454,24 @@
The current specification does not mandate any value for either E or
G. The current specification only provides an example of possible
choices for E and G. Note that this choice is done by the sender.
Then the E and G parameters are communicated to the receivers thanks
to the FEC OTI.
Example:
First define the target packet size, pkt_sz (usually the PMTU minus
the various protocol headers). The pkt_sz must be chosen in such a
 way it is a multiple of G. Calculate the number of packets: nb_pkts =
 ceil(L / pkt_sz). Then, use the following table to find a possible G
 value.
+ way that the symbol size is an integer. This can require that pkt_sz
+ be a multiple of 4, 8 or 16 (see the table below). Then calculate
+ the number of packets: nb_pkts = ceil(L / pkt_sz). Finally use the
+ following table to find a possible G value.
+++++
 Number of packets  G  Symbol size  k 
+++++
 4000 <= nb_pkts  1  pkt_sz  4000 <= k 
    
 1000 <= nb_pkts < 4000  4  pkt_sz / 4  4000 <= k < 16000 
    
 500 <= nb_pkts < 1000  8  pkt_sz / 8  4000 <= k < 8000 
    
@@ 500,20 +505,23 @@
block
n: Number of encoding symbols generated for this source block
Algorithm:
max_n = floor(B / rate);
if (max_n >= 2^^20) then return an error ("invalid code rate");
+ (NB: if max_n has been defined as explained in Section 5.2, this
+ error should never happen)
+
n = floor(k * max_n / B);
AT A RECEIVER:
Input:
B: Extracted from the received FEC OTI
max_n: Extracted from the received FEC OTI
@@ 651,29 +659,31 @@
% (n  k)];
}
}
}
5.6. Pseudo Random Number Generator
The present FEC Encoding ID relies on a pseudorandom number
generator (PRNG) that must be fully specified, in particular in order
to enable the receivers and the senders to build the same parity
 check matrix. The minimal standard generator [Park88] is used. It
+ check matrix. The minimal standard generator [8] is used. It
defines a simple multiplicative congruential algorithm: Ij+1 = A * Ij
(modulo M), with the following choices: A = 7^^5 = 16807 and M =
2^^31  1 = 2147483647. Several implementations of this PRNG are
 known and discussed in the literature. Yet all of them provide the
 same sequence of pseudo random numbers. For instance, if seed = 1,
 then the 10,000th value returned MUST be equal to 1043618065. The
 following implementation uses the Park and Miller algorithm with the
 optimization suggested by D. Carta in [Carta90].
+ known and discussed in the literature. All of them provide the same
+ sequence of pseudo random numbers. A validation criteria of such a
+ PRNG is the following: if seed = 1, then the 10,000th value returned
+ MUST be equal to 1043618065.
+
+ The following implementation uses the Park and Miller algorithm with
+ the optimization suggested by D. Carta in [9].
unsigned long seed;
/*
* Initialize the PRNG with a seed between
* 1 and 0x7FFFFFFE (i.e. 2^^312) inclusive.
*/
void srand (unsigned long s)
{
if ((s > 0) && (s < 0x7FFFFFFF))
@@ 693,22 +703,22 @@
* 0x7FFFFFFE (2^^312) inclusive.
* This value is then scaled between 0 and maxv1
* inclusive.
*/
unsigned long
rand (unsigned long maxv)
{
unsigned long hi, lo;
lo = 16807 * (seed & 0xFFFF);
 hi = 16807 * (seed >> 16);
 lo += (hi & 0x7FFF) << 16;
+ hi = 16807 * (seed >> 16); /* binary shift to right */
+ lo += (hi & 0x7FFF) << 16; /* binary shift to left */
lo += hi >> 15;
if (lo > 0x7FFFFFFF)
lo = 0x7FFFFFFF;
seed = (long)lo;
/* don't use modulo, least significant bits are less random
* than most significant bits [Numerical Recipies in C] */
return ((unsigned long)
((double)seed * (double)maxv / (double)0x7FFFFFFF));
}
@@ 806,34 +816,35 @@
and generate repair symbol with ESI i before symbol ESI i+1.
6.4. Decoding
Decoding basically consists in solving a system of nk linear
equations whose variables are the source an repair symbols. Of
course, the final goal is to recover the value of source symbols
only.
To that purpose, many techniques are possible. One of them is the
 following trivial algorithm [Zyablov74]: given a set of linear
 equations, if one of them has only one remaining unknown variable,
 then the value of this variable is that of the constant term. So,
 replace this variable by its value in all the remaining linear
 equations and reiterate. The value of several variables can
 therefore be found recursively. Applied to LDPC FEC codes working
 over an erasure packet, the parity check matrix defines a set of
 linear equations whose variables are the source symbols and repair
 symbols. Receiving or decoding a symbol is equivalent to having the
 value of a variable. Appendix A sketches a possible implementation
 of this algorithm.
+ following trivial algorithm [10]: given a set of linear equations, if
+ one of them has only one remaining unknown variable, then the value
+ of this variable is that of the constant term. So, replace this
+ variable by its value in all the remaining linear equations and
+ reiterate. The value of several variables can therefore be found
+ recursively. Applied to LDPC FEC codes working over an erasure
+ packet, the parity check matrix defines a set of linear equations
+ whose variables are the source symbols and repair symbols. Receiving
+ or decoding a symbol is equivalent to having the value of a variable.
+ Appendix A sketches a possible implementation of this algorithm.
 The Gauss elimination technique (or any derivative) is another
 possible decoding technique.
+ The Gauss elimination technique (or any optimized derivative) is
+ another possible decoding technique. Hybrid solutions that start by
+ using the trivial algorithm above and finish with a Gauss elimination
+ are also possible.
Because interoperability does not depend on the decoding algorithm
used, the current document does not recommend any particular
technique. This choice is left to the codec developer.
Yet choosing a decoding technique will have great practical impacts.
It will impact the erasure capabilities: a Gauss elimination
technique enables to solve the system with a smaller number of
symbols compared to the trivial technique. It will also impact the
CPU load: a Gauss elimination technique requires much more processing
@@ 901,164 +912,188 @@
only. To that purpose, many techniques are possible, as explained in
Section 6.4.
Because interoperability does not depend on the decoding algorithm
used, the current document does not recommend any particular
technique. This choice is left to the codec implementer.
8. Security Considerations
The security considerations for this document are the same as that of
 [RFC3452].

9. Intellectual Property

 To the best of our knowledge, there is no patent or patent
 application identified as being used in the LDPCStaircase and LDPC
 Triangle FEC schemes. Yet other LDPC codes and associated techniques
 MAY be covered by Intellectual Property Rights.
+ [2].
10. Acknowledgments
+9. Acknowledgments
Section 5.4 is derived from a previous InternetDraft, and we would
like to thank S. Peltotalo and J. Peltotalo for their contribution.
We would also like to thank Pascal Moniot, Laurent Fazio, Aurelien
Francillon and Shao Wenjian for their comments.
11. References
+10. References
11.1. Normative References
+10.1. Normative References
 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
 Requirement Levels", RFC 2119, BCP 14, March 1997.
+ [1] Bradner, S., "Key words for use in RFCs to Indicate Requirement
+ Levels", RFC 2119, BCP 14, March 1997.
 [RFC3452] Luby, M., Vicisano, L., Gemmell, J., Rizzo, L., Handley,
 M., and J. Crowcroft, "Forward Error Correction (FEC)
 Building Block", RFC 3452, December 2002.
+ [2] Watson, M., Luby, M., and L. Vicisano, "Forward Error Correction
+ (FEC) Building Block", draftietfrmtfecbbrevised03.txt
+ (work in progress), January 2006.
 [RFC3453] Luby, M., Vicisano, L., Gemmell, J., Rizzo, L., Handley,
 M., and J. Crowcroft, "The Use of Forward Error Correction
 (FEC) in Reliable Multicast", RFC 3453, December 2002.
+ [3] Luby, M., Vicisano, L., Gemmell, J., Rizzo, L., Handley, M., and
+ J. Crowcroft, "The Use of Forward Error Correction (FEC) in
+ Reliable Multicast", RFC 3453, December 2002.
 [fecbbrevised]
 Watson, M., Luby, M., and L. Vicisano, "Forward Error
 Correction (FEC) Building Block",
 draftietfrmtfecbbrevised03.txt (work in progress),
 January 2006.
+10.2. Informative References
11.2. Informative References
+ [4] Roca, V. and C. Neumann, "Design, Evaluation and Comparison of
+ Four Large Block FEC Codecs: LDPC, LDGM, LDGMStaircase and
+ LDGMTriangle, Plus a ReedSolomon Small Block FEC Codec",
+ INRIA Research Report RR5225, June 2004.
 [Carta90] Carta, D., "Two Fast Implementations of the Minimal
 Standard Random Number Generator", Communications of the
 ACM, Vol. 33, No. 1, pp.8788, January 1990.
+ [5] Neumann, C., Roca, V., Francillon, A., and D. Furodet, "Impacts
+ of Packet Scheduling and Packet Loss Distribution on FEC
+ Performances: Observations and Recommendations", ACM CoNEXT'05
+ Conference, Toulouse, France (an extended version is available
+ as INRIA Research Report RR5578), October 2005.
 [LDPCrefimpl]
 Roca, V., Neumann, C., and J. Laboure, "LDPCStaircase/
 LDPCTriangle Codec Reference Implementation", PLANETE
 Research Team, INRIA RhoneAlpes,
 http://planete.inrialpes.fr/~roca/mcl/.
+ [6] Roca, V., Neumann, C., and J. Laboure, "LDPCStaircase/
+ LDPCTriangle Codec Reference Implementation", INRIA Rhone
+ Alpes and STMicroelectronics,
+ http://planetebcast.inrialpes.fr/.
 [Mac03] MacKay, D., "Information Theory, Inference and Learning
+ [7] MacKay, D., "Information Theory, Inference and Learning
Algorithms", Cambridge University Press, ISBN: 0521642981,
2003.
 [Neumann05]
 Neumann, C., Roca, V., Francillon, A., and D. Furodet,
 "Impacts of Packet Scheduling and Packet Loss Distribution
 on FEC Performances: Observations and Recommendations",
 ACM CoNEXT'05 Conference, Toulouse, France (an extended
 version is available as INRIA Research Report RR5578),
 October 2005.

 [Park88] Park, S. and K. Miller, "Random Number Generators: Good
 Ones are Hard to Find", Communications of the ACM, Vol.
 31, No. 10, pp.11921201, 1988.
+ [8] Park, S. and K. Miller, "Random Number Generators: Good Ones
+ are Hard to Find", Communications of the ACM, Vol. 31, No. 10,
+ pp.11921201, 1988.
 [Roca04] Roca, V. and C. Neumann, "Design, Evaluation and
 Comparison of Four Large Block FEC Codecs: LDPC, LDGM,
 LDGMStaircase and LDGMTriangle, Plus a ReedSolomon
 Small Block FEC Codec", INRIA Research Report RR5225,
 June 2004.
+ [9] Carta, D., "Two Fast Implementations of the Minimal Standard
+ Random Number Generator", Communications of the ACM, Vol. 33,
+ No. 1, pp.8788, January 1990.
 [Zyablov74]
 Zyablov, V. and M. Pinsker, "Decoding Complexity of Low
 Density Codes for Tranmission in a Channel with Erasures",
 Translated from Problemy Peredachi Informatsii, Vol.10,
 No. 1, pp.1528, JanuaryMarch 1974.
+ [10] Zyablov, V. and M. Pinsker, "Decoding Complexity of LowDensity
+ Codes for Transmission in a Channel with Erasures", Translated
+ from Problemy Peredachi Informatsii, Vol.10, No. 1, pp.1528,
+ JanuaryMarch 1974.
Appendix A. Trivial Decoding Algorithm (Informative Only)
 A trivial decoding algorithm is the following:
+ A trivial decoding algorithm is sketched below (please see [6] for
+ the details omitted here):
 Initialization: allocate a partial sum buffer, partial_sum_i, for
 each line i, and reset it to 0.
+ Initialization: allocate a table of partial sum buffers:
+ partial_sum[nk], one per equation;
+ Reset all the buffers to 0;
 For each newly received or decoded symbol s_i with ESI i:
+ /*
+ * For each newly received or decoded symbol, try to make progress
+ * in the decoding of the associated source block.
+ * new_esi (IN): ESI of the new symbol, which is also the index
+ * in [0; n1]
+ * new_symb (IN): New symbol received or decoded
+ */
+ void
+ decoding_step(ESI_t new_esi,
+ symbol_t *new_symb)
+ {
+ If (new_symb is an already decoded or received symbol) {
+ Return; /* don't waste time with this symbol */
+ }
 1. If s_i is an already decoded or received symbol, return
 immediately and do nothing.
+ If (new_symb is the last missing source symbol) {
+ Return; /* decoding is now finished */
+ }
 2. If s_i is a source symbol, it is permanently stored in memory.
+ Create an empty list of equations having symbols decoded during
+ this decoding step;
 3. For each equation j having a degree greater than one (i.e.
 more than one unknown variable), with an entry in column i
 (i.e. having s_i as a variable), do the following:
+ /*
+ * First add this new symbol to all partial sums of the
+ * associated equations.
+ */
+ For (each equation eq in which new_symb is a variable and
+ having more than one unknown variable) {
 + add s_i to partial_sum_i;
+ Add new_symb to partial_sum[eq];
 + remove the entry (j, i) of the H matrix.
+ Remove entry(eq, new_esi) from the H matrix;
 + If the new degree of equation j is one, we have decoded a
 new packet and have to remember the index of the equation
 in a list of indexes for newly decoded packets for step 4.
+ If (degree of equation eq == 1) {
+ /* new symbol can be decoded, remember the equation */
+ Append eq to the list of equations having symbols
+ decoded during this decoding step;
+ }
+ }
+ /*
+ * Then finish with recursive calls to decoding_step() for each
+ * newly decoded symbols.
+ */
+ For (each equation eq in the list of equations having symbols
+ decoded during this decoding step) {
 4. For all newly generated packets s_l in step 3:
+ /*
+ * Because of the recursion below, we need to check that
+ * decoding is not finished, and that the equation is
+ * __still__ of degree 1
+ */
+ If (decoding is finished) {
+ break; /* exit from the loop */
+ }
 + remove the last entry in equation j,
+ If ((degree of equation eq == 1) {
+ Let dec_esi be the ESI of the newly decoded symbol in
+ equation eq;
 + copy partial_sum_j to the buffer associate with symbol s_l,
+ Remove entry(eq, dec_esi);
 + goto step 1 with the newly created symbol s_l
+ Allocate a buffer, dec_symb, for this symbol, and
+ copy partial_sum[eq] to dec_symb;
+
+ /* finally, call this function recursively */
+ decoding_step(dec_esi, dec_symb);
+ }
+ }
+ }
Authors' Addresses
Vincent Roca
INRIA
655, av. de l'Europe
Zirst; Montbonnot
ST ISMIER cedex 38334
France
 Phone:
Email: vincent.roca@inrialpes.fr
URI: http://planete.inrialpes.fr/~roca/
Christoph Neumann
Thomson Research
46, Quai A. Le Gallo
Boulogne Cedex 92648
France
 Phone:
Email: christoph.neumann@thomson.net
URI: http://planete.inrialpes.fr/~chneuman/
David Furodet
STMicroelectronics
12, Rue Jules Horowitz
BP217
Grenoble Cedex 38019
France
 Phone:
Email: david.furodet@st.com
 URI:
+ URI: http://www.st.com/
Intellectual Property Statement
The IETF takes no position regarding the validity or scope of any
Intellectual Property Rights or other rights that might be claimed to
pertain to the implementation or use of the technology described in
this document or the extent to which any license under such rights
might or might not be available; nor does it represent that it has
made any independent effort to identify any such rights. Information
on the procedures with respect to rights in RFC documents can be