draft-ietf-rmt-bb-fec-ldpc-04.txt   draft-ietf-rmt-bb-fec-ldpc-05.txt 
RMT V. Roca RMT V. Roca
Internet-Draft INRIA Internet-Draft INRIA
Intended status: Experimental C. Neumann Intended status: Experimental C. Neumann
Expires: June 25, 2007 Thomson Research Expires: September 30, 2007 Thomson Research
D. Furodet D. Furodet
STMicroelectronics STMicroelectronics
December 22, 2006 March 29, 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-04.txt draft-ietf-rmt-bb-fec-ldpc-05.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 June 25, 2007. This Internet-Draft will expire on September 30, 2007.
Copyright Notice Copyright Notice
Copyright (C) The IETF Trust (2006). 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 these sense of
RFC3453. RFC3453.
skipping to change at page 3, line 31 skipping to change at page 3, line 31
5.1. General . . . . . . . . . . . . . . . . . . . . . . . . . 12 5.1. General . . . . . . . . . . . . . . . . . . . . . . . . . 12
5.2. Determining the Maximum Source Block Length (B) . . . . . 13 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) . . . . . . . . . . . . 13 of Encoding Symbols per Group (G) . . . . . . . . . . . . 13
5.4. Determining the Number of Encoding Symbols of a Block . . 15 5.4. Determining the Number of Encoding Symbols of a Block . . 15
5.5. Identifying the Symbols of an Encoding Symbol Group . . . 16 5.5. Identifying the Symbols of an Encoding Symbol Group . . . 16
5.6. Pseudo Random Number Generator . . . . . . . . . . . . . . 19 5.6. Pseudo Random Number Generator . . . . . . . . . . . . . . 19
6. Full Specification of the LDPC-Staircase Scheme . . . . . . . 21 6. Full Specification of the LDPC-Staircase Scheme . . . . . . . 21
6.1. General . . . . . . . . . . . . . . . . . . . . . . . . . 21 6.1. General . . . . . . . . . . . . . . . . . . . . . . . . . 21
6.2. Parity Check Matrix Creation . . . . . . . . . . . . . . . 21 6.2. Parity Check Matrix Creation . . . . . . . . . . . . . . . 21
6.3. Encoding . . . . . . . . . . . . . . . . . . . . . . . . . 23 6.3. Encoding . . . . . . . . . . . . . . . . . . . . . . . . . 22
6.4. Decoding . . . . . . . . . . . . . . . . . . . . . . . . . 23 6.4. Decoding . . . . . . . . . . . . . . . . . . . . . . . . . 23
7. Full Specification of the LDPC-Triangle Scheme . . . . . . . . 25 7. Full Specification of the LDPC-Triangle Scheme . . . . . . . . 24
7.1. General . . . . . . . . . . . . . . . . . . . . . . . . . 25 7.1. General . . . . . . . . . . . . . . . . . . . . . . . . . 24
7.2. Parity Check Matrix Creation . . . . . . . . . . . . . . . 25 7.2. Parity Check Matrix Creation . . . . . . . . . . . . . . . 24
7.3. Encoding . . . . . . . . . . . . . . . . . . . . . . . . . 25 7.3. Encoding . . . . . . . . . . . . . . . . . . . . . . . . . 24
7.4. Decoding . . . . . . . . . . . . . . . . . . . . . . . . . 26 7.4. Decoding . . . . . . . . . . . . . . . . . . . . . . . . . 25
8. Security Considerations . . . . . . . . . . . . . . . . . . . 27 8. Security Considerations . . . . . . . . . . . . . . . . . . . 26
9. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 28 9. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 27
10. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 29 10. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 28
11. References . . . . . . . . . . . . . . . . . . . . . . . . . . 30 11. References . . . . . . . . . . . . . . . . . . . . . . . . . . 29
11.1. Normative References . . . . . . . . . . . . . . . . . . . 30 11.1. Normative References . . . . . . . . . . . . . . . . . . . 29
11.2. Informative References . . . . . . . . . . . . . . . . . . 30 11.2. Informative References . . . . . . . . . . . . . . . . . . 29
Appendix A. Trivial Decoding Algorithm (Informative Only) . . . . 32 Appendix A. Trivial Decoding Algorithm (Informative Only) . . . . 31
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 34 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 33
Intellectual Property and Copyright Statements . . . . . . . . . . 35 Intellectual Property and Copyright Statements . . . . . . . . . . 34
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
skipping to change at page 8, line 15 skipping to change at page 8, line 15
4. Formats and Codes 4. Formats and Codes
4.1. FEC Payload IDs 4.1. FEC Payload IDs
The FEC Payload ID is composed of the Source Block Number and the The FEC Payload ID is composed of the Source Block Number and the
Encoding Symbol ID: Encoding Symbol ID:
The Source Block Number (12 bit field) identifies from which The Source Block Number (12 bit field) identifies from which
source block of the object the encoding symbol(s) in the packet source block of the object the encoding symbol(s) in the packet
payload is(are) generated. There are a maximum of 2^^12 blocks payload is(are) generated. There are a maximum of 2^^12 blocks
per object. per object. Source block numbering starts at 0.
The Encoding Symbol ID (20 bit field) identifies which encoding The Encoding Symbol ID (20 bit field) identifies which encoding
symbol(s) generated from the source block is(are) carried in the symbol(s) generated from the source block is(are) carried in the
packet payload. There are a maximum of 2^^20 encoding symbols per packet payload. There are a maximum of 2^^20 encoding symbols per
block. The first k values (0 to k-1) identify source symbols, the block. The first k values (0 to k-1) identify source symbols, the
remaining n-k values (k to n-k-1) identify repair symbols. remaining n-k values (k to n-k-1) identify repair symbols.
There MUST be exactly one FEC Payload ID per packet. In case of an There MUST be exactly one FEC Payload ID per packet. In case of an
Encoding Symbol Group, when multiple encoding symbols are sent in the Encoding Symbol Group, when multiple encoding symbols are sent in the
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
skipping to change at page 10, 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 Figure 2: EXT_FTI Header for FEC Encoding ID 3 and 4.
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 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 [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-FEC-Encoding-ID
o FEC-OTI-Transfer-length o FEC-OTI-Transfer-length
skipping to change at page 11, line 23 skipping to change at page 11, line 23
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| PRNG seed | | PRNG seed |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| G | | G |
+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+
Figure 3: FEC OTI Scheme Specific Information to be Included in the Figure 3: FEC OTI Scheme Specific Information to be Included in the
FDT Instance FDT Instance for FEC Encoding ID 3 and 4.
When no PRNG seed is to be carried in the FEC OTI, the seed field is When no PRNG seed is to be carried in the FEC OTI, the seed field
set to 0 (which is not a valid seed value). Otherwise the seed field MUST be set to 0 (which is not a valid seed value). Otherwise the
contains a valid value as explained in Section 4.2.3. 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 After Base64 encoding, the 5 bytes of the FEC OTI Scheme Specific
Information are transformed into a string of 8 printable characters Information are transformed into a string of 8 printable characters
(in the 64-character alphabet) and added to the FEC-OTI-Scheme- (in the 64-character alphabet) and added to the FEC-OTI-Scheme-
Specific-Info attribute. Specific-Info attribute.
5. Procedures 5. Procedures
This section defines procedures that are common to FEC Encoding IDs 3 This section defines procedures that are common to FEC Encoding IDs 3
and 4. and 4.
skipping to change at page 12, line 51 skipping to change at page 12, line 51
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 [5].
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 Section 5.2, Section 5.3 and Section 5.4), determined (respectively in Section 5.2, Section 5.3 and
how encoding symbol groups are created (Section 5.5), and finally Section 5.4), how encoding symbol groups are created (Section 5.5),
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
field length of the FEC Payload ID (20 bits), as well as possible field length of the FEC Payload ID (20 bits), as well as possible
internal codec limitations. internal codec limitations.
The B parameter cannot be larger than the following values, derived The B parameter cannot be larger than the following values, derived
from the FEC Payload ID limitations, for a given code rate: from the FEC Payload ID limitations, for a given code rate:
max1_B = 2^^(20 - ceil(Log2(1/rate))) max1_B = 2^^(20 - ceil(Log2(1/rate)))
Some common max1_B values are: Some common max1_B values are:
o rate == 1 (no repair symbols): max1_B = 2^^20 = 1,048,576 o rate == 1 (no repair symbol): max1_B = 2^^20 = 1,048,576
o 1/2 <= rate < 1: max1_B = 2^^19 = 524,288 symbols o 1/2 <= rate < 1: max1_B = 2^^19 = 524,288 symbols
o 1/4 <= rate < 1/2: max1_B = 2^^18 = 262,144 symbols o 1/4 <= rate < 1/2: max1_B = 2^^18 = 262,144 symbols
o 1/8 <= rate < 1/4: max1_B = 2^^17 = 131,072 symbols o 1/8 <= rate < 1/4: max1_B = 2^^17 = 131,072 symbols
Additionally, a codec MAY impose other limitations on the maximum Additionally, a codec MAY impose other limitations on the maximum
block size. This is the case for instance when the codec uses block size. This is the case for instance when the codec uses
internally 16 bit unsigned integers to store the Encoding Symbol ID, internally 16 bit unsigned integers to store the Encoding Symbol ID,
skipping to change at page 14, line 7 skipping to change at page 14, line 7
5.3. Determining the Encoding Symbol Length (E) and Number of Encoding 5.3. Determining the Encoding Symbol Length (E) and Number of Encoding
Symbols per Group (G) Symbols per Group (G)
The E parameter usually depends on the maximum transmission unit on The E parameter usually depends on the maximum transmission unit on
the path (PMTU) from the source to the receivers. In order to the path (PMTU) from the source to the receivers. In order to
minimize the protocol header overhead (e.g. the LCT/UDP/IPv4 or IPv6 minimize the protocol header overhead (e.g. the LCT/UDP/IPv4 or IPv6
headers in case of ALC), E is chosen as large as possible. In that headers in case of ALC), E is chosen as large as possible. In that
case, E is chosen so that the size of a packet composed of a single case, E is chosen so that the size of a packet composed of a single
symbol (G=1) remains below but close to the PMTU. symbol (G=1) remains below but close to the PMTU.
Yet other considerations can exist. For instance, the E parameter However other considerations can exist. For instance, the E
can be made a function of the object transfer length. Indeed, LDPC parameter can be made a function of the object transfer length.
codes are known to offer better protection for large blocks. In case Indeed, LDPC codes are known to offer better protection for large
of small objects, it can be a good practice to reduce the encoding blocks. In case of small objects, it can be advantageous to reduce
symbol length (E) in order to artificially increase the number of the encoding symbol length (E) in order to artificially increase the
symbols, and therefore the block size. number of symbols, and therefore the block size.
In order to minimize the protocol header overhead, several symbols In order to minimize the protocol header overhead, several symbols
can be grouped in the same Encoding Symbol Group (i.e. G > 1). can be grouped in the same Encoding Symbol Group (i.e. G > 1).
Depending on how many symbols are grouped (G) and on the packet loss Depending on how many symbols are grouped (G) and on the packet loss
rate (G symbols are lost for each packet erasure), this strategy rate (G symbols are lost for each packet erasure), this strategy
might or might not be appropriate. A balance must therefore be might or might not be appropriate. A balance must therefore be
found. found.
The current specification does not mandate any value for either E or The current specification does not mandate any value for either E or
G. The current specification only provides an example of possible G. The current specification only provides an example of possible
choices for E and G. Note that this choice is done by the sender. 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 Then the E and G parameters are communicated to the receivers thanks
to the FEC OTI. to the FEC OTI.
Example: Example:
First define the target packet size, pkt_sz (usually the PMTU minus First define the target packet payload size, pkt_sz (at most equal to
the various protocol headers). The pkt_sz must be chosen in such a the PMTU minus the size of the various protocol headers). The pkt_sz
way that the symbol size is an integer. This can require that pkt_sz must be chosen in such a way that the symbol size is an integer.
be a multiple of 4, 8 or 16 (see the table below). Then calculate This can require that pkt_sz be a multiple of 4, 8 or 16 (see the
the number of packets: nb_pkts = ceil(L / pkt_sz). Finally use the table below). Then calculate the number of packets in the object:
nb_pkts = ceil(L / pkt_sz). Finally, thanks to nb_pkts, use the
following table to find a possible G value. following table to find a possible G value.
+------------------------+----+-------------+-------------------+ +------------------------+----+-------------+-------------------+
| Number of packets | G | Symbol size | k | | Number of packets | G | Symbol size | k |
+------------------------+----+-------------+-------------------+ +------------------------+----+-------------+-------------------+
| 4000 <= nb_pkts | 1 | pkt_sz | 4000 <= k | | 4000 <= nb_pkts | 1 | pkt_sz | 4000 <= k |
| | | | | | | | | |
| 1000 <= nb_pkts < 4000 | 4 | pkt_sz / 4 | 4000 <= k < 16000 | | 1000 <= nb_pkts < 4000 | 4 | pkt_sz / 4 | 4000 <= k < 16000 |
| | | | | | | | | |
| 500 <= nb_pkts < 1000 | 8 | pkt_sz / 8 | 4000 <= k < 8000 | | 500 <= nb_pkts < 1000 | 8 | pkt_sz / 8 | 4000 <= k < 8000 |
skipping to change at page 15, line 20 skipping to change at page 15, line 20
AT A SENDER: AT A SENDER:
Input: Input:
B: Maximum source block length, for any source block. Section 5.2 B: Maximum source block length, for any source block. Section 5.2
explains how to determine its value. explains how to determine its value.
k: Current source block length. This parameter is given by the k: Current source block length. This parameter is given by the
source blocking algorithm. source blocking algorithm.
rate: FEC code rate, which is provided by the user (e.g. when rate: FEC code rate. It is provided by the user, for instance
starting a FLUTE sending application). It is expressed as a when starting a FLUTE sending application. It is expressed as a
floating point value. The rate value must be such that the floating point value. The rate value must be such that the
resulting number of encoding symbols per block is at most equal to resulting number of encoding symbols per block is at most equal to
2^^20 (Section 4.1). 2^^20 (Section 4.1).
Output: Output:
max_n: Maximum number of encoding symbols generated for any source max_n: Maximum number of encoding symbols generated for any source
block block
n: Number of encoding symbols generated for this source block n: Number of encoding symbols generated for this source block
skipping to change at page 16, line 26 skipping to change at page 16, line 26
When multiple encoding symbols are sent in the same packet, the FEC When multiple encoding symbols are sent in the same packet, the FEC
Payload ID information of the packet MUST refer to the first encoding Payload ID information of the packet MUST refer to the first encoding
symbol. It MUST then be possible to identify each symbol from this symbol. It MUST then be possible to identify each symbol from this
single FEC Payload ID. To that purpose, the symbols of an Encoding single FEC Payload ID. To that purpose, the symbols of an Encoding
Symbol Group (i.e. packet): Symbol Group (i.e. packet):
o MUST all be either source symbols, or repair symbols. Therefore o MUST all be either source symbols, or repair symbols. Therefore
only source packets and repair packets are permitted, not mixed only source packets and repair packets are permitted, not mixed
ones. ones.
o are identified by a function, ESIs_of_group(), that takes as o are identified by a function, sender(resp.
argument: receiver)_find_ESIs_of_group(), that takes as argument:
* for a sender, the index of the Encoding Symbol Group (i.e. * for a sender, the index of the Encoding Symbol Group (i.e.
packet) that the application wants to create, packet) that the application wants to create,
* for a receiver, the ESI information contained in the FEC * for a receiver, the ESI information contained in the FEC
Payload ID. Payload ID.
and returns the list of G Encoding Symbol IDs that will be packed and returns a list of G Encoding Symbol IDs. In case of a source
together. In case of a source packet, the G source symbols are packet, the G Encoding Symbol IDs are chosen consecutively, by
taken consecutively. In case of a repair packet, the G repair incrementing the ESI. In case of a repair packet, the G repair
symbols are chosen randomly, as explained below. symbols are chosen randomly, as explained below.
o are stored in sequence in the packet, without any padding. In o are stored in sequence in the packet, without any padding. In
other words, the last byte of the symbol with ESI i (where i is other words, the last byte of the i-th symbol is immediately
the i-th ESI returned by the function ESIs_of_group()) is followed by the first byte of (i+1)-th symbol.
immediately followed by the first byte of symbol i+1.
The system must first be initialized by creating a random permutation The system must first be initialized by creating a random permutation
of the n-k indexes. This initialization function MUST be called of the n-k indexes. This initialization function MUST be called
immediately after creating the parity check matrix. More precisely, immediately after creating the parity check matrix. More precisely,
since the PRNG seed is not re-initialized, no call to the PRNG since the PRNG seed is not re-initialized, no call to the PRNG
function must have happened between the time the parity check matrix function must have happened between the time the parity check matrix
has been initialized and the time the following initialization has been initialized and the time the following initialization
function is called. This is true both at a sender and at a receiver. function is called. This is true both at a sender and at a receiver.
int *txseqToID; int *txseqToID;
skipping to change at page 22, line 5 skipping to change at page 21, line 28
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.
The left side is generated with the following algorithm: The left side is generated with the following algorithm:
/*
* Derived from: "Software for Low Density Parity Check Codes"
* Version of 2001-11-18, Radford M. Neal, Univ. of Toronto.
* Copyright (c) 1995, 1996, 2000, 2001 by Radford M. Neal
* http://www.cs.toronto.edu/~radford/ldpc.software.html
*/
/* initialize a list of all possible choices in order to /* initialize a list of all possible choices in order to
* guarantee a homogeneous "1" distribution */ * guarantee a homogeneous "1" distribution */
for (h = 3*k-1; h >= 0; h--) { for (h = 3*k-1; h >= 0; h--) {
u[h] = h % (n-k); u[h] = h % (n-k);
} }
/* left limit within the list of possible choices, u[] */ /* left limit within the list of possible choices, u[] */
t = 0; t = 0;
for (j = 0; j < k; j++) { /* for each source symbol column */ for (j = 0; j < k; j++) { /* for each source symbol column */
for (h = 0; h < 3; h++) { /* add 3 "1s" */ for (h = 0; h < 3; h++) { /* add 3 "1s" */
skipping to change at page 23, line 46 skipping to change at page 23, line 28
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.
The Gauss elimination technique (or any optimized derivative) is A Gaussian elimination (or any optimized derivative) is another
another possible decoding technique. Hybrid solutions that start by possible decoding technique. Hybrid solutions that start by using
using the trivial algorithm above and finish with a Gauss elimination the trivial algorithm above and finish with a Gaussian 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. However choosing a decoding technique will have great practical
It will impact the erasure capabilities: a Gauss elimination impacts. It will impact the erasure capabilities: a Gaussian
technique enables to solve the system with a smaller number of known elimination enables to solve the system with a smaller number of
symbols compared to the trivial technique. It will also impact the known symbols compared to the trivial technique. It will also impact
CPU load: a Gauss elimination technique requires much more processing the CPU load: a Gaussian elimination requires more processing than
than the trivial technique. Depending on the target use case, the the above trivial algorithm. 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 4. LDPC-Triangle is identified by the Fully-Specified FEC Encoding ID 4.
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
skipping to change at page 30, line 14 skipping to change at page 29, line 14
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-04.txt (work in progress), draft-ietf-rmt-fec-bb-revised-06.txt (work in progress),
September 2006. March 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.
11.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",
skipping to change at page 31, line 9 skipping to change at page 30, line 9
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 [10] 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 [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-04.txt (work in progress),
April 2006. February 2007.
[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-02.txt (work in progress), draft-ietf-rmt-flute-revised-03.txt (work in progress),
August 2006. January 2007.
[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-03.txt (work (NORM) Protocol", draft-ietf-rmt-pi-norm-revised-04.txt (work
in progress), September 2006. 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 [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
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
* in the decoding of the associated source block. * in the decoding of the associated source block.
* NB: in case of a symbol group (G>1), this function is called for * NB: in case of a symbol group (G>1), this function is called for
* each symbol of the received packet. * each symbol of the received packet.
* NB: a callback function indicates to the caller that new symbol(s)
* has(have) been decoded.
* new_esi (IN): ESI of the new symbol received or decoded * new_esi (IN): ESI of the new symbol received or decoded
* new_symb (IN): Buffer of the new symbol received or decoded * new_symb (IN): Buffer of the new symbol received or decoded
*/ */
void void
decoding_step(ESI_t new_esi, decoding_step(ESI_t new_esi,
symbol_t *new_symb) symbol_t *new_symb)
{ {
If (new_symb is an already decoded or received symbol) { If (new_symb is an already decoded or received symbol) {
Return; /* don't waste time with this symbol */ Return; /* don't waste time with this symbol */
} }
skipping to change at page 33, line 35 skipping to change at page 32, line 37
If ((degree of equation eq == 1) { If ((degree of equation eq == 1) {
Let dec_esi be the ESI of the newly decoded symbol in Let dec_esi be the ESI of the newly decoded symbol in
equation eq; equation eq;
Remove entry(eq, dec_esi); Remove entry(eq, dec_esi);
Allocate a buffer, dec_symb, for this symbol and Allocate a buffer, dec_symb, for this symbol and
copy partial_sum[eq] to dec_symb; copy partial_sum[eq] to dec_symb;
Inform the caller that a new symbol has been
decoded via a callback function;
/* finally, call this function recursively */ /* finally, call this function recursively */
decoding_step(dec_esi, dec_symb); decoding_step(dec_esi, dec_symb);
} }
} }
Free the list of equations having symbols decoded; Free the list of equations having symbols decoded;
Return; Return;
} }
Authors' Addresses Authors' Addresses
skipping to change at page 35, line 7 skipping to change at page 34, line 7
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/
Full Copyright Statement Full Copyright Statement
Copyright (C) The IETF Trust (2006). Copyright (C) The IETF Trust (2007).
This document is subject to the rights, licenses and restrictions This document is subject to the rights, licenses and restrictions
contained in BCP 78, and except as set forth therein, the authors contained in BCP 78, and except as set forth therein, the authors
retain all their rights. retain all their rights.
This document and the information contained herein are provided on an This document and the information contained herein are provided on an
"AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS
OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST AND OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST AND
THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS
OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF
 End of changes. 30 change blocks. 
70 lines changed or deleted 81 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/