draft-ietf-rmt-bb-fec-ldpc-01.txt | draft-ietf-rmt-bb-fec-ldpc-02.txt | |||
---|---|---|---|---|

RMT V. Roca | RMT V. Roca | |||

Internet-Draft INRIA | Internet-Draft INRIA | |||

Expires: August 5, 2006 C. Neumann | Expires: December 23, 2006 C. Neumann | |||

Thomson Research | Thomson Research | |||

D. Furodet | D. Furodet | |||

STMicroelectronics | STMicroelectronics | |||

February 2006 | June 21, 2006 | |||

Low Density Parity Check (LDPC) Forward Error Correction | Low Density Parity Check (LDPC) Staircase and Triangle Forward Error | |||

draft-ietf-rmt-bb-fec-ldpc-01.txt | Correction (FEC) Schemes | |||

draft-ietf-rmt-bb-fec-ldpc-02.txt | ||||

Status of this Memo | Status of this Memo | |||

By submitting this Internet-Draft, each author represents that any | By submitting this Internet-Draft, each author represents that any | |||

applicable patent or other IPR claims of which he or she is aware | applicable patent or other IPR claims of which he or she is aware | |||

have been or will be disclosed, and any of which he or she becomes | have been or will be disclosed, and any of which he or she becomes | |||

aware will be disclosed, in accordance with Section 6 of BCP 79. | aware will be disclosed, in accordance with Section 6 of BCP 79. | |||

Internet-Drafts are working documents of the Internet Engineering | Internet-Drafts are working documents of the Internet Engineering | |||

Task Force (IETF), its areas, and its working groups. Note that | Task Force (IETF), its areas, and its working groups. Note that | |||

skipping to change at page 1, line 37 | 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 August 5, 2006. | This Internet-Draft will expire on December 23, 2006. | |||

Copyright Notice | Copyright Notice | |||

Copyright (C) The Internet Society (2006). | Copyright (C) The Internet Society (2006). | |||

Abstract | Abstract | |||

This document describes two Fully-Specified FEC Schemes, LDPC- | This document describes two Fully-Specified FEC Schemes, LDPC- | |||

Staircase and LDPC-Triangle, and their application to the reliable | Staircase and LDPC-Triangle, and their application to the reliable | |||

delivery of objects on packet erasure channels. These systematic FEC | delivery of objects on packet erasure channels. These systematic FEC | |||

skipping to change at page 2, line 40 | skipping to change at page 2, line 41 | |||

6.1. General . . . . . . . . . . . . . . . . . . . . . . . . . 20 | 6.1. General . . . . . . . . . . . . . . . . . . . . . . . . . 20 | |||

6.2. Parity Check Matrix Creation . . . . . . . . . . . . . . . 20 | 6.2. Parity Check Matrix Creation . . . . . . . . . . . . . . . 20 | |||

6.3. Encoding . . . . . . . . . . . . . . . . . . . . . . . . . 22 | 6.3. Encoding . . . . . . . . . . . . . . . . . . . . . . . . . 22 | |||

6.4. Decoding . . . . . . . . . . . . . . . . . . . . . . . . . 22 | 6.4. Decoding . . . . . . . . . . . . . . . . . . . . . . . . . 22 | |||

7. Full Specification of the LDPC-Triangle Scheme . . . . . . . . 24 | 7. Full Specification of the LDPC-Triangle Scheme . . . . . . . . 24 | |||

7.1. General . . . . . . . . . . . . . . . . . . . . . . . . . 24 | 7.1. General . . . . . . . . . . . . . . . . . . . . . . . . . 24 | |||

7.2. Parity Check Matrix Creation . . . . . . . . . . . . . . . 24 | 7.2. Parity Check Matrix Creation . . . . . . . . . . . . . . . 24 | |||

7.3. Encoding . . . . . . . . . . . . . . . . . . . . . . . . . 24 | 7.3. Encoding . . . . . . . . . . . . . . . . . . . . . . . . . 24 | |||

7.4. Decoding . . . . . . . . . . . . . . . . . . . . . . . . . 25 | 7.4. Decoding . . . . . . . . . . . . . . . . . . . . . . . . . 25 | |||

8. Security Considerations . . . . . . . . . . . . . . . . . . . 26 | 8. Security Considerations . . . . . . . . . . . . . . . . . . . 26 | |||

9. Intellectual Property . . . . . . . . . . . . . . . . . . . . 27 | 9. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 27 | |||

10. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 28 | 10. References . . . . . . . . . . . . . . . . . . . . . . . . . . 28 | |||

11. References . . . . . . . . . . . . . . . . . . . . . . . . . . 29 | 10.1. Normative References . . . . . . . . . . . . . . . . . . . 28 | |||

11.1. Normative References . . . . . . . . . . . . . . . . . . . 29 | 10.2. Informative References . . . . . . . . . . . . . . . . . . 28 | |||

11.2. Informative References . . . . . . . . . . . . . . . . . . 29 | Appendix A. Trivial Decoding Algorithm (Informative Only) . . . . 30 | |||

Appendix A. Trivial Decoding Algorithm (Informative Only) . . . . 31 | ||||

Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 32 | Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 32 | |||

Intellectual Property and Copyright Statements . . . . . . . . . . 33 | Intellectual Property and Copyright Statements . . . . . . . . . . 33 | |||

1. Introduction | 1. Introduction | |||

RFC 3453 [RFC3453] introduces large block FEC codes as an alternative | RFC 3453 [3] introduces large block FEC codes as an alternative to | |||

to small block FEC codes like Reed-Solomon. The main advantage of | small block FEC codes like Reed-Solomon. The main advantage of such | |||

such large block codes is the possibility to operate efficiently on | large block codes is the possibility to operate efficiently on source | |||

source blocks of size several tens of thousands (or more) source | blocks of size several tens of thousands (or more) source symbols. | |||

symbols. The present document introduces the Fully-Specified FEC | The present document introduces the Fully-Specified FEC Encoding ID | |||

Encoding ID XX that is intended to be used with the "Low Density | XX that is intended to be used with the "Low Density Parity Check" | |||

Parity Check" (LDPC) Staircase FEC codes, and the Fully-Specified FEC | (LDPC) Staircase FEC codes, and the Fully-Specified FEC Encoding ID | |||

Encoding ID YY that is intended to be used with the "Low Density | YY that is intended to be used with the "Low Density Parity Check" | |||

Parity Check" (LDPC)-Triangle FEC codes [Roca04][Mac03]. Both | (LDPC)-Triangle FEC codes [4][7]. Both schemes belong the broad | |||

schemes belong the broad class of large block codes. | class of large block codes. | |||

-- editor's note: This document makes use of the FEC Encoding ID | -- editor's note: This document makes use of the FEC Encoding ID | |||

values XX and YY that will be specified after IANA assignment -- | values XX and YY that will be specified after IANA assignment -- | |||

LDPC codes rely on a dedicated matrix, called a "Parity Check | LDPC codes rely on a dedicated matrix, called a "Parity Check | |||

Matrix", at the encoding and decoding ends. The parity check matrix | Matrix", at the encoding and decoding ends. The parity check matrix | |||

defines relationships (or constraints) between the various encoding | defines relationships (or constraints) between the various encoding | |||

symbols (i.e. source symbols and repair symbols), that are later used | symbols (i.e. source symbols and repair symbols), that are later used | |||

by the decoder to reconstruct the original k source symbols if some | by the decoder to reconstruct the original k source symbols if some | |||

of them are missing. These codes are systematic, in the sense that | of them are missing. These codes are systematic, in the sense that | |||

the encoding symbols include the source symbols in addition to the | the encoding symbols include the source symbols in addition to the | |||

redundant 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, some information must be communicated between them, as part | matrix, information must be communicated between them as part of the | |||

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 [LDPCrefimpl]. To | available and distributed under a GNU/LGPL license [6]. | |||

the best of our knowledge, there is no patent or patent application | ||||

identified as being used in the LDPC-Staircase and LDPC-Triangle FEC | ||||

schemes. | ||||

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 [RFC2119]. | 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 | |||

This document uses the same terms and definitions as those specified | This document uses the same terms and definitions as those specified | |||

in [fec-bb-revised]. Additionally, it uses the following | in [2]. Additionally, it uses the following definitions: | |||

definitions: | ||||

Encoding Symbol Group: a group of encoding symbols that are sent | Encoding Symbol Group: a group of encoding symbols that are sent | |||

together, within the same packet, and whose relationships to the | together, within the same packet, and whose relationships to the | |||

source object can be derived from a single Encoding Symbol ID. | source object can be derived from a single Encoding Symbol ID. | |||

Source Packet: a data packet containing only source symbols. | Source Packet: a data packet containing only source symbols. | |||

Repair Packet: a data packet containing only repair symbols. | Repair Packet: a data packet containing only repair symbols. | |||

3.2. Notations | 3.2. Notations | |||

skipping to change at page 5, line 44 | skipping to change at page 5, line 43 | |||

B denotes the maximum source block length in symbols, i.e. the | B denotes the maximum source block length in symbols, i.e. the | |||

maximum number of source symbols per source block | maximum number of source symbols per source block | |||

N denotes the number of source blocks into which the object shall | N denotes the number of source blocks into which the object shall | |||

be partitioned | be partitioned | |||

G denotes the number of encoding symbols per group, i.e. the | G denotes the number of encoding symbols per group, i.e. the | |||

number of symbols sent in the same packet | number of symbols sent in the same packet | |||

rate denotes the so-called "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 | max_n denotes the maximum number of encoding symbols generated for | |||

block | any source block | |||

srand(s) denotes the initialization function of the pseudo-random | srand(s) denotes the initialization function of the pseudo-random | |||

number generator, where s is the seed (s > 0) | number generator, where s is the seed (s > 0) | |||

rand(m) denotes a pseudo-random number generator, that returns a | rand(m) denotes a pseudo-random number generator, that returns a | |||

new random integer in [0; m-1] each time it is called | new random integer in [0; m-1] each time it is called | |||

3.3. Abbreviations | 3.3. Abbreviations | |||

This document uses the following abbreviations: | This document uses the following abbreviations: | |||

ESI: Encoding Symbol ID | ESI: Encoding Symbol ID | |||

FEC OTI: FEC Object Transmission Information | FEC OTI: FEC Object Transmission Information | |||

skipping to change at page 8, line 9 | skipping to change at page 8, line 9 | |||

The following elements MUST be defined with the present FEC Scheme: | The following elements MUST be defined with the present FEC Scheme: | |||

o Transfer-Length (L): a non-negative integer indicating the length | o Transfer-Length (L): a non-negative integer indicating the length | |||

of the object in bytes. There are some restrictions on the | of the object in bytes. There are some restrictions on the | |||

maximum Transfer-Length that can be supported: | maximum Transfer-Length that can be supported: | |||

maximum transfer length = 2^^12 * B * E | maximum transfer length = 2^^12 * B * E | |||

For instance, if B=2^^19 (because of a code rate of 1/2, | 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 | 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^^16-1 bytes and a code rate larger or equal to 1/2, amounts | ||||

to 2^^47 bytes (or 128 TB). | ||||

o Encoding-Symbol-Length (E): a non-negative integer indicating the | o Encoding-Symbol-Length (E): a non-negative integer indicating the | |||

length of each encoding symbol in bytes. | length of each encoding symbol in bytes. | |||

o Maximum-Source-Block-Length (B): a non-negative integer indicating | o Maximum-Source-Block-Length (B): a non-negative integer indicating | |||

the maximum number of source symbols in a source block. There are | the maximum number of source symbols in a source block. There are | |||

some restrictions on the maximum B value, as explained in | some restrictions on the maximum B value, as explained in | |||

Section 5.2. | Section 5.2. | |||

o Max-Number-of-Encoding-Symbols (max_n): a non-negative integer | o Max-Number-of-Encoding-Symbols (max_n): a non-negative integer | |||

skipping to change at page 8, line 37 | skipping to change at page 8, line 39 | |||

4.2.3. Scheme-Specific Element | 4.2.3. Scheme-Specific Element | |||

The following element MUST be defined with the present FEC Scheme. | The following element MUST be defined with the present FEC Scheme. | |||

It contains two distinct pieces of information: | It contains two distinct pieces of information: | |||

o G: a non-negative integer indicating the number of encoding | o G: a non-negative integer indicating the number of encoding | |||

symbols per group used for the object. The default value is 1, | symbols per group used for the object. The default value is 1, | |||

meaning that each packet contains exactly one symbol. Values | meaning that each packet contains exactly one symbol. Values | |||

greater than 1 can also be defined, as explained in Section 5.3. | 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 | o PRNG seed: The seed is a 32 bit unsigned integer between 1 and | |||

Pseudo Random Number Generator (defined in Section 5.6). This | 0x7FFFFFFE (i.e. 2^^31-2) 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 | 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 | appropriate mechanism (see Section 4.2.4). When the PRNG seed is | |||

not carried within the FEC OTI, it is assumed that encoder and | not carried within the FEC OTI, it is assumed that encoder and | |||

decoders use another way to communicate the information, or use a | decoders use another way to communicate the information, or use a | |||

fixed, predefined value. | fixed, predefined value. | |||

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. | |||

skipping to change at page 9, line 29 | skipping to change at page 9, line 30 | |||

| B (LSB) | Max Nb of Enc. Symbols (max_n) | | | B (LSB) | Max Nb of Enc. Symbols (max_n) | | |||

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | |||

. Optional PRNG seed . | . Optional PRNG seed . | |||

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | |||

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 Maximum-Source-Block-Length (B) is split into two parts: the 8 | o The Transfer-Length (L) field size (48 bits) is larger than the | |||

most significant bits (MSB) are in the third 32-bit word of the | size required to store the maximum transfer length (Section 4.2.2) | |||

EXT_FTI, and the remaining 12 least significant bits (LSB) are in | for field alignment purposes. | |||

fourth 32-bit word. | ||||

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- | ||||

bit word of the EXT_FTI, and the remaining 12 least significant | ||||

bits (LSB) are in fourth 32-bit word. | ||||

4.2.4.2. Using the FDT Instance (FLUTE specific) | 4.2.4.2. Using the FDT Instance (FLUTE specific) | |||

When it is desired that the FEC OTI be carried in the FDT Instance of | When it is desired that the FEC OTI be carried in the FDT Instance of | |||

a FLUTE session, the following XML elements must be described for the | a FLUTE session, the following XML elements must be described for the | |||

associated object: | associated object: | |||

o FEC-OTI-Transfer-length | o FEC-OTI-Transfer-length | |||

o FEC-OTI-Encoding-Symbol-Length | o FEC-OTI-Encoding-Symbol-Length | |||

skipping to change at page 11, line 17 | skipping to change at page 11, line 17 | |||

This section defines procedures that are common to FEC Encoding IDs | This section defines procedures that are common to FEC Encoding IDs | |||

XX and YY. | XX and YY. | |||

5.1. General | 5.1. General | |||

The B (maximum source block length in symbols) and E (encoding symbol | The B (maximum source block length in symbols) and E (encoding symbol | |||

length in bytes) parameters are first determined, as explained in the | length in bytes) parameters are first determined, as explained in the | |||

following sections. | following sections. | |||

The source object is then partitioned using the block partitioning | The source object is then partitioned using the block partitioning | |||

algorithm specified in [fec-bb-revised]. To that purpose, the B, L | algorithm specified in [2]. To that purpose, the B, L (object | |||

(object transfer length in bytes), and E arguments are provided. As | transfer length in bytes), and E arguments are provided. As a | |||

a result, the object is partitioned into N source blocks. These | result, the object is partitioned into N source blocks. These blocks | |||

blocks are numbered consecutively from 0 to N-1. The first I source | are numbered consecutively from 0 to N-1. The first I source blocks | |||

blocks consist of A_large source symbols, the remaining N-I source | consist of A_large source symbols, the remaining N-I source blocks | |||

blocks consist of A_small source symbols. Each source symbol is E | consist of A_small source symbols. Each source symbol is E bytes in | |||

bytes in length, except perhaps the last symbol which may be shorter. | length, except perhaps the last symbol which may be shorter. | |||

For each block the actual number of encoding symbols is determined, | For each block the actual number of encoding symbols is determined, | |||

as explained in the following section. | as explained in the following section. | |||

Then, FEC encoding and decoding can be done block per block, | Then, FEC encoding and decoding can be done block per block, | |||

independently. To that purpose, a parity check matrix is created, | independently. To that purpose, a parity check matrix is created, | |||

that forms a system of linear equations between the repair and source | that forms a system of linear equations between the repair and source | |||

symbols of a given block, where the basic operator is XOR. | symbols of a given block, where the basic operator is XOR. | |||

This parity check matrix is logically divided into two parts: the | This parity check matrix is logically divided into two parts: the | |||

skipping to change at page 11, line 48 | skipping to change at page 11, 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 [Neumann05]. | 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 Section 5.2, Section 5.3 and Section 5.4), | |||

how encoding symbol groups are created (Section 5.5), and finally | how encoding symbol groups are created (Section 5.5), and finally | |||

specify the PRNG (Section 5.6). | 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 12, line 32 | skipping to change at page 12, line 32 | |||

o 1 > rate >= 1/2: max1_B = 2 ^^ 19 = 524,288 symbols | 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/2 > rate >= 1/4: max1_B = 2 ^^ 18 = 262,144 symbols | |||

o 1/4 > rate >= 1/8: max1_B = 2 ^^ 17 = 131,072 symbols | o 1/4 > rate >= 1/8: 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 integers to store the Encoding Symbol ID, since it | 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. | 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 | In that case, if for instance 1 > rate >= 1/2, then the maximum block | |||

working memory size. This decision SHOULD be clarified at | size is 2^^15. Other limitations may also apply, for instance | |||

implementation time, when the target use case is known. This results | because of a limited working memory size. This decision MUST be | |||

in a max2_B limitation. | clarified at implementation time, when the target use case is known. | |||

This results in a max2_B limitation. | ||||

Then, B is given by: | Then, B is given by: | |||

B = min(max1_B, max2_B) | B = min(max1_B, max2_B) | |||

Note that this calculation is only required at the coder, since the B | Note that this calculation is only required at the coder, since the B | |||

parameter is communicated to the decoder through the FEC OTI. | parameter is communicated to the decoder through the FEC OTI. | |||

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) | |||

skipping to change at page 13, line 30 | skipping to change at page 13, line 31 | |||

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 size, pkt_sz (usually the PMTU minus | |||

the various protocol headers). The pkt_sz must be chosen in such a | 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 = | way that the symbol size is an integer. This can require that pkt_sz | |||

ceil(L / pkt_sz). Then, use the following table to find a possible G | be a multiple of 4, 8 or 16 (see the table below). Then calculate | |||

value. | 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 | | | 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 14, line 32 | skipping to change at page 14, line 34 | |||

block | block | |||

n: Number of encoding symbols generated for this source block | n: Number of encoding symbols generated for this source block | |||

Algorithm: | Algorithm: | |||

max_n = floor(B / rate); | max_n = floor(B / rate); | |||

if (max_n >= 2^^20) then return an error ("invalid code 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); | n = floor(k * max_n / B); | |||

AT A RECEIVER: | AT A RECEIVER: | |||

Input: | Input: | |||

B: Extracted from the received FEC OTI | B: Extracted from the received FEC OTI | |||

max_n: Extracted from the received FEC OTI | max_n: Extracted from the received FEC OTI | |||

skipping to change at page 18, line 37 | skipping to change at page 18, line 37 | |||

% (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 [Park88] is used. It | check matrix. The minimal standard generator [8] 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. Yet all of them provide the | known and discussed in the literature. All of them provide the same | |||

same sequence of pseudo random numbers. For instance, if seed = 1, | sequence of pseudo random numbers. A validation criteria of such a | |||

then the 10,000th value returned MUST be equal to 1043618065. The | PRNG is the following: if seed = 1, then the 10,000th value returned | |||

following implementation uses the Park and Miller algorithm with the | MUST be equal to 1043618065. | |||

optimization suggested by D. Carta in [Carta90]. | ||||

The following implementation uses the Park and Miller algorithm with | ||||

the optimization suggested by D. Carta in [9]. | ||||

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 19, line 37 | skipping to change at page 19, line 37 | |||

* 0x7FFFFFFE (2^^31-2) inclusive. | * 0x7FFFFFFE (2^^31-2) inclusive. | |||

* This value is then scaled between 0 and maxv-1 | * This value is then scaled between 0 and maxv-1 | |||

* inclusive. | * inclusive. | |||

*/ | */ | |||

unsigned long | unsigned long | |||

rand (unsigned long maxv) | rand (unsigned long maxv) | |||

{ | { | |||

unsigned long hi, lo; | unsigned long hi, lo; | |||

lo = 16807 * (seed & 0xFFFF); | lo = 16807 * (seed & 0xFFFF); | |||

hi = 16807 * (seed >> 16); | hi = 16807 * (seed >> 16); /* binary shift to right */ | |||

lo += (hi & 0x7FFF) << 16; | 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 Recipies in C] */ | |||

return ((unsigned long) | return ((unsigned long) | |||

((double)seed * (double)maxv / (double)0x7FFFFFFF)); | ((double)seed * (double)maxv / (double)0x7FFFFFFF)); | |||

} | } | |||

skipping to change at page 22, line 35 | skipping to change at page 22, line 35 | |||

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 source an repair symbols. Of | equations whose variables are the source an repair symbols. Of | |||

course, the final goal is to recover the value of source symbols | course, the final goal is to recover the value of source symbols | |||

only. | 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 [Zyablov74]: given a set of linear | following trivial algorithm [10]: given a set of linear equations, if | |||

equations, if one of them has only one remaining unknown variable, | one of them has only one remaining unknown variable, then the value | |||

then the value of this variable is that of the constant term. So, | of this variable is that of the constant term. So, replace this | |||

replace this variable by its value in all the remaining linear | variable by its value in all the remaining linear equations and | |||

equations and reiterate. The value of several variables can | reiterate. The value of several variables can therefore be found | |||

therefore be found recursively. Applied to LDPC FEC codes working | recursively. Applied to LDPC FEC codes working over an erasure | |||

over an erasure packet, the parity check matrix defines a set of | packet, the parity check matrix defines a set of linear equations | |||

linear equations whose variables are the source symbols and repair | whose variables are the source symbols and repair symbols. Receiving | |||

symbols. Receiving or decoding a symbol is equivalent to having the | or decoding a symbol is equivalent to having the value of a variable. | |||

value of a variable. Appendix A sketches a possible implementation | Appendix A sketches a possible implementation of this algorithm. | |||

of this algorithm. | ||||

The Gauss elimination technique (or any derivative) is another | The Gauss elimination technique (or any optimized derivative) is | |||

possible decoding technique. | 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 | Because interoperability does not depend on the decoding algorithm | |||

used, the current document does not recommend any particular | used, the current document does not recommend any particular | |||

technique. This choice is left to the codec developer. | technique. This choice is left to the codec developer. | |||

Yet choosing a decoding technique will have great practical impacts. | Yet choosing a decoding technique will have great practical impacts. | |||

It will impact the erasure capabilities: a Gauss elimination | It will impact the erasure capabilities: a Gauss elimination | |||

technique enables to solve the system with a smaller number of | technique enables to solve the system with a smaller number of | |||

symbols compared to the trivial technique. It will also impact the | symbols compared to the trivial technique. It will also impact the | |||

CPU load: a Gauss elimination technique requires much more processing | CPU load: a Gauss elimination technique requires much more processing | |||

skipping to change at page 26, line 8 | skipping to change at page 26, line 8 | |||

only. To that purpose, many techniques are possible, as explained in | only. To that purpose, many techniques are possible, as explained in | |||

Section 6.4. | 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 | The security considerations for this document are the same as that of | |||

[RFC3452]. | [2]. | |||

9. Intellectual Property | ||||

To the best of our knowledge, there is no patent or patent | ||||

application identified as being used in the LDPC-Staircase and LDPC- | ||||

Triangle FEC schemes. Yet other LDPC codes and associated techniques | ||||

MAY be covered by Intellectual Property Rights. | ||||

10. Acknowledgments | 9. 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 | 10. References | |||

11.1. Normative References | 10.1. Normative References | |||

[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate | [1] Bradner, S., "Key words for use in RFCs to Indicate Requirement | |||

Requirement Levels", RFC 2119, BCP 14, March 1997. | Levels", RFC 2119, BCP 14, March 1997. | |||

[RFC3452] Luby, M., Vicisano, L., Gemmell, J., Rizzo, L., Handley, | [2] Watson, M., Luby, M., and L. Vicisano, "Forward Error Correction | |||

M., and J. Crowcroft, "Forward Error Correction (FEC) | (FEC) Building Block", draft-ietf-rmt-fec-bb-revised-03.txt | |||

Building Block", RFC 3452, December 2002. | (work in progress), January 2006. | |||

[RFC3453] Luby, M., Vicisano, L., Gemmell, J., Rizzo, L., Handley, | [3] Luby, M., Vicisano, L., Gemmell, J., Rizzo, L., Handley, M., and | |||

M., and J. Crowcroft, "The Use of Forward Error Correction | J. Crowcroft, "The Use of Forward Error Correction (FEC) in | |||

(FEC) in Reliable Multicast", RFC 3453, December 2002. | Reliable Multicast", RFC 3453, December 2002. | |||

[fec-bb-revised] | 10.2. Informative References | |||

Watson, M., Luby, M., and L. Vicisano, "Forward Error | ||||

Correction (FEC) Building Block", | ||||

draft-ietf-rmt-fec-bb-revised-03.txt (work in progress), | ||||

January 2006. | ||||

11.2. Informative References | [4] Roca, V. and C. Neumann, "Design, Evaluation and Comparison of | |||

Four Large Block FEC Codecs: LDPC, LDGM, LDGM-Staircase and | ||||

LDGM-Triangle, Plus a Reed-Solomon Small Block FEC Codec", | ||||

INRIA Research Report RR-5225, June 2004. | ||||

[Carta90] Carta, D., "Two Fast Implementations of the Minimal | [5] Neumann, C., Roca, V., Francillon, A., and D. Furodet, "Impacts | |||

Standard Random Number Generator", Communications of the | of Packet Scheduling and Packet Loss Distribution on FEC | |||

ACM, Vol. 33, No. 1, pp.87-88, January 1990. | Performances: Observations and Recommendations", ACM CoNEXT'05 | |||

Conference, Toulouse, France (an extended version is available | ||||

as INRIA Research Report RR-5578), October 2005. | ||||

[LDPCrefimpl] | [6] Roca, V., Neumann, C., and J. Laboure, "LDPC-Staircase/ | |||

Roca, V., Neumann, C., and J. Laboure, "LDPC-Staircase/ | LDPC-Triangle Codec Reference Implementation", INRIA Rhone- | |||

LDPC-Triangle Codec Reference Implementation", PLANETE | Alpes and STMicroelectronics, | |||

Research Team, INRIA Rhone-Alpes, | http://planete-bcast.inrialpes.fr/. | |||

http://planete.inrialpes.fr/~roca/mcl/. | ||||

[Mac03] MacKay, D., "Information Theory, Inference and Learning | [7] MacKay, D., "Information Theory, Inference and Learning | |||

Algorithms", Cambridge University Press, ISBN: 0521642981, | Algorithms", Cambridge University Press, ISBN: 0521642981, | |||

2003. | 2003. | |||

[Neumann05] | [8] Park, S. and K. Miller, "Random Number Generators: Good Ones | |||

Neumann, C., Roca, V., Francillon, A., and D. Furodet, | are Hard to Find", Communications of the ACM, Vol. 31, No. 10, | |||

"Impacts of Packet Scheduling and Packet Loss Distribution | pp.1192-1201, 1988. | |||

on FEC Performances: Observations and Recommendations", | ||||

ACM CoNEXT'05 Conference, Toulouse, France (an extended | ||||

version is available as INRIA Research Report RR-5578), | ||||

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.1192-1201, 1988. | ||||

[Roca04] Roca, V. and C. Neumann, "Design, Evaluation and | [9] Carta, D., "Two Fast Implementations of the Minimal Standard | |||

Comparison of Four Large Block FEC Codecs: LDPC, LDGM, | Random Number Generator", Communications of the ACM, Vol. 33, | |||

LDGM-Staircase and LDGM-Triangle, Plus a Reed-Solomon | No. 1, pp.87-88, January 1990. | |||

Small Block FEC Codec", INRIA Research Report RR-5225, | ||||

June 2004. | ||||

[Zyablov74] | [10] Zyablov, V. and M. Pinsker, "Decoding Complexity of Low-Density | |||

Zyablov, V. and M. Pinsker, "Decoding Complexity of Low- | Codes for Transmission in a Channel with Erasures", Translated | |||

Density Codes for Tranmission in a Channel with Erasures", | from Problemy Peredachi Informatsii, Vol.10, No. 1, pp.15-28, | |||

Translated from Problemy Peredachi Informatsii, Vol.10, | January-March 1974. | |||

No. 1, pp.15-28, January-March 1974. | ||||

Appendix A. Trivial Decoding Algorithm (Informative Only) | 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 | Initialization: allocate a table of partial sum buffers: | |||

each line i, and reset it to 0. | partial_sum[n-k], 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; n-1] | ||||

* 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 | If (new_symb is the last missing source symbol) { | |||

immediately and do nothing. | 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 | * First add this new symbol to all partial sums of the | |||

(i.e. having s_i as a variable), do the following: | * 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 | If (degree of equation eq == 1) { | |||

new packet and have to remember the index of the equation | /* new symbol can be decoded, remember the equation */ | |||

in a list of indexes for newly decoded packets for step 4. | 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 | Authors' Addresses | |||

Vincent Roca | Vincent Roca | |||

INRIA | INRIA | |||

655, av. de l'Europe | 655, av. de l'Europe | |||

Zirst; Montbonnot | Zirst; Montbonnot | |||

ST ISMIER cedex 38334 | ST ISMIER cedex 38334 | |||

France | France | |||

Phone: | ||||

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 | |||

France | France | |||

Phone: | ||||

Email: christoph.neumann@thomson.net | Email: christoph.neumann@thomson.net | |||

URI: http://planete.inrialpes.fr/~chneuman/ | URI: http://planete.inrialpes.fr/~chneuman/ | |||

David Furodet | David Furodet | |||

STMicroelectronics | STMicroelectronics | |||

12, Rue Jules Horowitz | 12, Rue Jules Horowitz | |||

BP217 | BP217 | |||

Grenoble Cedex 38019 | Grenoble Cedex 38019 | |||

France | France | |||

Phone: | ||||

Email: david.furodet@st.com | Email: david.furodet@st.com | |||

URI: | URI: http://www.st.com/ | |||

Intellectual Property Statement | Intellectual Property Statement | |||

The IETF takes no position regarding the validity or scope of any | The IETF takes no position regarding the validity or scope of any | |||

Intellectual Property Rights or other rights that might be claimed to | Intellectual Property Rights or other rights that might be claimed to | |||

pertain to the implementation or use of the technology described in | pertain to the implementation or use of the technology described in | |||

this document or the extent to which any license under such rights | this document or the extent to which any license under such rights | |||

might or might not be available; nor does it represent that it has | might or might not be available; nor does it represent that it has | |||

made any independent effort to identify any such rights. Information | made any independent effort to identify any such rights. Information | |||

on the procedures with respect to rights in RFC documents can be | on the procedures with respect to rights in RFC documents can be | |||

End of changes. 60 change blocks. | ||||

156 lines changed or deleted | | 192 lines changed or added | ||

This html diff was produced by rfcdiff 1.32. The latest version is available from http://www.levkowetz.com/ietf/tools/rfcdiff/ |