draft-ietf-rmt-bb-fec-ldpc-07.txt | draft-ietf-rmt-bb-fec-ldpc-08.txt | |||
---|---|---|---|---|

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

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

Intended status: Standards Track C. Neumann | Intended status: Standards Track C. Neumann | |||

Expires: May 19, 2008 Thomson | Expires: July 26, 2008 Thomson | |||

D. Furodet | D. Furodet | |||

STMicroelectronics | STMicroelectronics | |||

November 16, 2007 | January 23, 2008 | |||

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-07.txt | draft-ietf-rmt-bb-fec-ldpc-08.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 May 19, 2008. | This Internet-Draft will expire on July 26, 2008. | |||

Copyright Notice | Copyright Notice | |||

Copyright (C) The IETF Trust (2007). | Copyright (C) The IETF Trust (2008). | |||

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 data objects on the packet erasure channel (i.e., a | delivery of data objects on the packet erasure channel (i.e., a | |||

communication path where packets are either received without any | communication path where packets are either received without any | |||

corruption or discarded during transmission). These systematic FEC | corruption or discarded during transmission). 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 the sense of RFC3453. | (LDPC) codes, and are large block FEC codes in the sense of RFC3453. | |||

Table of Contents | Table of Contents | |||

1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4 | 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 5 | |||

2. Requirements notation . . . . . . . . . . . . . . . . . . . . 5 | 2. Requirements notation . . . . . . . . . . . . . . . . . . . . 6 | |||

3. Definitions, Notations and Abbreviations . . . . . . . . . . . 6 | 3. Definitions, Notations and Abbreviations . . . . . . . . . . . 7 | |||

3.1. Definitions . . . . . . . . . . . . . . . . . . . . . . . 6 | 3.1. Definitions . . . . . . . . . . . . . . . . . . . . . . . 7 | |||

3.2. Notations . . . . . . . . . . . . . . . . . . . . . . . . 6 | 3.2. Notations . . . . . . . . . . . . . . . . . . . . . . . . 7 | |||

3.3. Abbreviations . . . . . . . . . . . . . . . . . . . . . . 7 | 3.3. Abbreviations . . . . . . . . . . . . . . . . . . . . . . 8 | |||

4. Formats and Codes . . . . . . . . . . . . . . . . . . . . . . 8 | 4. Formats and Codes . . . . . . . . . . . . . . . . . . . . . . 9 | |||

4.1. FEC Payload IDs . . . . . . . . . . . . . . . . . . . . . 8 | 4.1. FEC Payload IDs . . . . . . . . . . . . . . . . . . . . . 9 | |||

4.2. FEC Object Transmission Information . . . . . . . . . . . 8 | 4.2. FEC Object Transmission Information . . . . . . . . . . . 9 | |||

4.2.1. Mandatory Element . . . . . . . . . . . . . . . . . . 8 | 4.2.1. Mandatory Element . . . . . . . . . . . . . . . . . . 9 | |||

4.2.2. Common Elements . . . . . . . . . . . . . . . . . . . 8 | 4.2.2. Common Elements . . . . . . . . . . . . . . . . . . . 9 | |||

4.2.3. Scheme-Specific Elements . . . . . . . . . . . . . . . 9 | 4.2.3. Scheme-Specific Elements . . . . . . . . . . . . . . . 10 | |||

4.2.4. Encoding Format . . . . . . . . . . . . . . . . . . . 9 | 4.2.4. Encoding Format . . . . . . . . . . . . . . . . . . . 10 | |||

5. Procedures . . . . . . . . . . . . . . . . . . . . . . . . . . 12 | 5. Procedures . . . . . . . . . . . . . . . . . . . . . . . . . . 13 | |||

5.1. General . . . . . . . . . . . . . . . . . . . . . . . . . 12 | 5.1. General . . . . . . . . . . . . . . . . . . . . . . . . . 13 | |||

5.2. Determining the Maximum Source Block Length (B) . . . . . 13 | 5.2. Determining the Maximum Source Block Length (B) . . . . . 14 | |||

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) . . . . . . . . . . . . 14 | of Encoding Symbols per Group (G) . . . . . . . . . . . . 15 | |||

5.4. Determining the Maximum Number of Encoding Symbols | 5.4. Determining the Maximum Number of Encoding Symbols | |||

Generated for Any Source Block (max_n) . . . . . . . . . . 15 | Generated for Any Source Block (max_n) . . . . . . . . . . 16 | |||

5.5. Determining the Number of Encoding Symbols of a Block | 5.5. Determining the Number of Encoding Symbols of a Block | |||

(n) . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 | (n) . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 | |||

5.6. Identifying the G Symbols of an Encoding Symbol Group . . 16 | 5.6. Identifying the G Symbols of an Encoding Symbol Group . . 17 | |||

5.7. Pseudo Random Number Generator . . . . . . . . . . . . . . 20 | 5.7. Pseudo Random Number Generator . . . . . . . . . . . . . . 21 | |||

6. Full Specification of the LDPC-Staircase Scheme . . . . . . . 22 | 6. Full Specification of the LDPC-Staircase Scheme . . . . . . . 23 | |||

6.1. General . . . . . . . . . . . . . . . . . . . . . . . . . 22 | 6.1. General . . . . . . . . . . . . . . . . . . . . . . . . . 23 | |||

6.2. Parity Check Matrix Creation . . . . . . . . . . . . . . . 22 | 6.2. Parity Check Matrix Creation . . . . . . . . . . . . . . . 23 | |||

6.3. Encoding . . . . . . . . . . . . . . . . . . . . . . . . . 24 | 6.3. Encoding . . . . . . . . . . . . . . . . . . . . . . . . . 25 | |||

6.4. Decoding . . . . . . . . . . . . . . . . . . . . . . . . . 24 | 6.4. Decoding . . . . . . . . . . . . . . . . . . . . . . . . . 25 | |||

7. Full Specification of the LDPC-Triangle Scheme . . . . . . . . 26 | 7. Full Specification of the LDPC-Triangle Scheme . . . . . . . . 27 | |||

7.1. General . . . . . . . . . . . . . . . . . . . . . . . . . 26 | 7.1. General . . . . . . . . . . . . . . . . . . . . . . . . . 27 | |||

7.2. Parity Check Matrix Creation . . . . . . . . . . . . . . . 26 | 7.2. Parity Check Matrix Creation . . . . . . . . . . . . . . . 27 | |||

7.3. Encoding . . . . . . . . . . . . . . . . . . . . . . . . . 26 | 7.3. Encoding . . . . . . . . . . . . . . . . . . . . . . . . . 28 | |||

7.4. Decoding . . . . . . . . . . . . . . . . . . . . . . . . . 27 | 7.4. Decoding . . . . . . . . . . . . . . . . . . . . . . . . . 28 | |||

8. Security Considerations . . . . . . . . . . . . . . . . . . . 28 | 8. Security Considerations . . . . . . . . . . . . . . . . . . . 29 | |||

8.1. Problem Statement . . . . . . . . . . . . . . . . . . . . 28 | 8.1. Problem Statement . . . . . . . . . . . . . . . . . . . . 29 | |||

8.2. Attacks Against the Data Flow . . . . . . . . . . . . . . 28 | 8.2. Attacks Against the Data Flow . . . . . . . . . . . . . . 29 | |||

8.2.1. Access to Confidential Objects . . . . . . . . . . . . 28 | 8.2.1. Access to Confidential Objects . . . . . . . . . . . . 29 | |||

8.2.2. Content Corruption . . . . . . . . . . . . . . . . . . 29 | 8.2.2. Content Corruption . . . . . . . . . . . . . . . . . . 30 | |||

8.3. Attacks Against the FEC Parameters . . . . . . . . . . . . 30 | 8.3. Attacks Against the FEC Parameters . . . . . . . . . . . . 31 | |||

9. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 31 | 9. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 32 | |||

10. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 32 | 10. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 33 | |||

11. References . . . . . . . . . . . . . . . . . . . . . . . . . . 33 | 11. References . . . . . . . . . . . . . . . . . . . . . . . . . . 34 | |||

11.1. Normative References . . . . . . . . . . . . . . . . . . . 33 | 11.1. Normative References . . . . . . . . . . . . . . . . . . . 34 | |||

11.2. Informative References . . . . . . . . . . . . . . . . . . 33 | 11.2. Informative References . . . . . . . . . . . . . . . . . . 34 | |||

Appendix A. Pseudo Random Number Generator Example | Appendix A. Trivial Decoding Algorithm (Informative Only) . . . . 37 | |||

Implementation (Informative Only) . . . . . . . . . . 35 | ||||

Appendix B. Trivial Decoding Algorithm (Informative Only) . . . . 37 | ||||

Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 39 | Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 39 | |||

Intellectual Property and Copyright Statements . . . . . . . . . . 40 | Intellectual Property and Copyright Statements . . . . . . . . . . 40 | |||

1. Introduction | 1. Introduction | |||

[RFC3453] introduces large block FEC codes as an alternative to small | [RFC3453] introduces large block FEC codes as an alternative to small | |||

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

block codes is the possibility to operate efficiently on source | 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 | |||

skipping to change at page 4, line 33 | skipping to change at page 5, line 33 | |||

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

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

the repair symbols. | the repair symbols. | |||

Since the encoder and decoder must operate on the same parity check | Since the encoder and decoder must operate on the same parity check | |||

matrix, information must be communicated between them as part of the | matrix, information must be communicated between them as part of the | |||

FEC Object Transmission Information. | FEC Object Transmission Information. | |||

A publicly available reference implementation of these codes is | A publicly available reference implementation of these codes is | |||

available and distributed under a GNU/LGPL license [LDPC-codec]. | available and distributed under a GNU/LGPL license [LDPC-codec]. | |||

Besides, the code extracts included in this document (except | Besides, the code extracts included in this document are directly | |||

Appendix A that is only provided as an example) are directly | ||||

contributed to the IETF process by the authors of this document and | contributed to the IETF process by the authors of this document and | |||

by Radford M. Neal. | by Radford M. Neal. | |||

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

3. Definitions, Notations and Abbreviations | 3. Definitions, Notations and Abbreviations | |||

skipping to change at page 7, line 15 | skipping to change at page 8, line 15 | |||

symbols generated for a source block | symbols generated for a source block | |||

E denotes the encoding symbol length in bytes | E denotes the encoding symbol length in bytes | |||

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

CR denotes the "code rate", i.e., the k/n ratio | CR denotes the "code rate", i.e., the k/n ratio | |||

max_n denotes the maximum number of encoding symbols generated for | max_n denotes the maximum number of encoding symbols generated for | |||

any source block. This is in particular the number of encoding | any source block. This is in particular the number of encoding | |||

symbols generated for a source block of size B | symbols generated for a source block of size B | |||

H denotes the parity check matrix | H denotes the parity check matrix | |||

srand(s) denotes the initialization function of the pseudo-random | pmms_rand(m) denotes the pseudo-random number generator defined in | |||

number generator, where s is the seed (s > 0) | Section 5.7 that returns a new random integer in [0; m-1] each | |||

time it is called | ||||

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

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

FPI: FEC Payload ID | FPI: FEC Payload ID | |||

skipping to change at page 11, line 4 | skipping to change at page 12, line 4 | |||

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

o FEC-OTI-Maximum-Source-Block-Length | o FEC-OTI-Maximum-Source-Block-Length | |||

o FEC-OTI-Max-Number-of-Encoding-Symbols | o FEC-OTI-Max-Number-of-Encoding-Symbols | |||

o FEC-OTI-Scheme-Specific-Info | o FEC-OTI-Scheme-Specific-Info | |||

The FEC-OTI-Scheme-Specific-Info contains the string resulting from | The FEC-OTI-Scheme-Specific-Info contains the string resulting from | |||

the Base64 encoding (in the XML Schema xs:base64Binary sense) of the | the Base64 encoding (in the XML Schema xs:base64Binary sense) | |||

following value: | [RFC4648] of the following value: | |||

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

skipping to change at page 16, line 39 | skipping to change at page 17, line 39 | |||

Algorithm: | Algorithm: | |||

n = floor(k * max_n / B); | n = floor(k * max_n / B); | |||

5.6. Identifying the G Symbols of an Encoding Symbol Group | 5.6. Identifying the G Symbols of an Encoding Symbol Group | |||

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, sender(resp. | o are identified by a function, sender(resp. | |||

receiver)_find_ESIs_of_group(), that takes as 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, | |||

skipping to change at page 18, line 21 | skipping to change at page 19, line 21 | |||

*/ | */ | |||

void | void | |||

initialize_tables () | initialize_tables () | |||

{ | { | |||

int i; | int i; | |||

int randInd; | int randInd; | |||

int backup; | int backup; | |||

txseqToID = malloc((n-k) * sizeof(int)); | txseqToID = malloc((n-k) * sizeof(int)); | |||

IDtoTxseq = malloc((n-k) * sizeof(int)); | IDtoTxseq = malloc((n-k) * sizeof(int)); | |||

if (txseqToID == NULL || IDtoTxseq == NULL) | ||||

handle the malloc failures as appropriate... | ||||

/* initialize the two tables that map ID | /* initialize the two tables that map ID | |||

* (i.e., ESI-k) to/from TxSequence. */ | * (i.e., ESI-k) to/from TxSequence. */ | |||

for (i = 0; i < n - k; i++) { | for (i = 0; i < n - k; i++) { | |||

IDtoTxseq[i] = i; | IDtoTxseq[i] = i; | |||

txseqToID[i] = i; | txseqToID[i] = i; | |||

} | } | |||

/* now randomize everything */ | /* now randomize everything */ | |||

for (i = 0; i < n - k; i++) { | for (i = 0; i < n - k; i++) { | |||

randInd = rand(n - k); | randInd = pmms_rand(n - k); | |||

backup = IDtoTxseq[i]; | backup = IDtoTxseq[i]; | |||

IDtoTxseq[i] = IDtoTxseq[randInd]; | IDtoTxseq[i] = IDtoTxseq[randInd]; | |||

IDtoTxseq[randInd] = backup; | IDtoTxseq[randInd] = backup; | |||

txseqToID[IDtoTxseq[i]] = i; | txseqToID[IDtoTxseq[i]] = i; | |||

txseqToID[IDtoTxseq[randInd]] = randInd; | txseqToID[IDtoTxseq[randInd]] = randInd; | |||

} | } | |||

return; | return; | |||

} | } | |||

It is then possible, at the sender, to determine the sequence of G | It is then possible, at the sender, to determine the sequence of G | |||

skipping to change at page 20, line 40 | skipping to change at page 21, line 40 | |||

} | } | |||

} | } | |||

} | } | |||

5.7. Pseudo Random Number Generator | 5.7. Pseudo Random Number Generator | |||

The FEC Encoding IDs 3 and 4 rely on a pseudo-random number generator | The FEC Encoding IDs 3 and 4 rely on a pseudo-random number generator | |||

(PRNG) that must be fully specified, in particular in order to enable | (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 receivers and the senders to build the same parity check matrix. | |||

The minimal standard generator [PM88] MUST be used. It defines a | The Park-Miler "minimal standard" PRNG [PM88] MUST be used. It | |||

simple multiplicative congruential algorithm: Ij+1 = A * Ij (modulo | defines a simple multiplicative congruential algorithm: Ij+1 = A * Ij | |||

M), with the following choices: A = 7^^5 = 16807 and M = 2^^31 - 1 = | (modulo M), with the following choices: A = 7^^5 = 16807 and M = | |||

2147483647. Several implementations of this PRNG are known and | 2^^31 - 1 = 2147483647. A validation criteria of such a PRNG is the | |||

discussed in the literature. All of them provide the same sequence | following: if seed = 1, then the 10,000th value returned MUST be | |||

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. | equal to 1043618065. | |||

An optimized implementation of this algorithm, using only 32 bit | Several implementations of this PRNG are known and discussed in the | |||

mathematics which does not require any division, is provided, as an | literature. An optimized implementation of this algorithm, using | |||

example, in Appendix A. Yet any other implementation of the PRNG | only 32 bit mathematics and which does not require any division, can | |||

algorithm that matches the above validation criteria is appropriate. | be found in [rand31pmc]. It uses the Park and Miller algorithm | |||

[PM88] with the optimization suggested by D. Carta in [CA90]. The | ||||

history behind this algorithm is detailed in [WI08]. Yet any other | ||||

implementation of the PRNG algorithm that matches the above | ||||

validation criteria, like the ones detailed in [PM88], is | ||||

appropriate. | ||||

This PRNG produces a 31 bit value between 1 and 0x7FFFFFFE (2^^31-2) | This PRNG produces natively a 31 bit value between 1 and 0x7FFFFFFE | |||

inclusive. When it is desired to scale the pseudo random number | (2^^31-2) inclusive. Since it is desired to scale the pseudo random | |||

between 0 and maxv-1 inclusive, one must keep the most significant | number between 0 and maxv-1 inclusive, one must keep the most | |||

bits of the value returned by the PRNG (the least significant bits | significant bits of the value returned by the PRNG (the least | |||

are known to be less random and modulo based solutions should be | significant bits are known to be less random and modulo based | |||

avoided [PTVF92]). The following algorithm MUST be used: | solutions should be avoided [PTVF92]). The following algorithm MUST | |||

be used: | ||||

Input: | Input: | |||

raw_value: random integer generated by the inner PRNG algorithm, | raw_value: random integer generated by the inner PRNG algorithm, | |||

between 1 and 0x7FFFFFFE (2^^31-2) inclusive. | between 1 and 0x7FFFFFFE (2^^31-2) inclusive. | |||

maxv: upper bound used during the scaling operation. | maxv: upper bound used during the scaling operation. | |||

Output: | Output: | |||

scaled_value: random integer between 0 and maxv-1 inclusive. | scaled_value: random integer between 0 and maxv-1 inclusive. | |||

Algorithm: | Algorithm: | |||

scaled_value = (unsigned long) ((double)maxv * (double)raw_value / | scaled_value = (unsigned long) ((double)maxv * (double)raw_value / | |||

(double)0x7FFFFFFF); | (double)0x7FFFFFFF); | |||

(NB: the above C type casting to unsigned long is equivalent to | (NB: the above C type casting to unsigned long is equivalent to | |||

using floor() with positive floating point values) | using floor() with positive floating point values) | |||

In this document, pmms_rand(maxv) denotes the PRNG function that | ||||

implements the Park-Miller "minimal standard" algorithm defined above | ||||

and that scales the raw value between 1 and maxv-1 inclusive, using | ||||

the above scaling algorithm. Additionally, a function should be | ||||

provided to enable the initialization of the PRNG with a seed (i.e., | ||||

a 31 bit interger between 1 and 0x7FFFFFFE inclusive) before calling | ||||

pmms_rand(maxv) the first time. | ||||

6. Full Specification of the LDPC-Staircase Scheme | 6. Full Specification of the LDPC-Staircase Scheme | |||

6.1. General | 6.1. General | |||

The LDPC-Staircase scheme is identified by the Fully-Specified FEC | The LDPC-Staircase scheme is identified by the Fully-Specified FEC | |||

Encoding ID 3. | Encoding ID 3. | |||

The PRNG used by the LDPC-Staircase scheme must be initialized by a | The PRNG used by the LDPC-Staircase scheme must be initialized by a | |||

seed. This PRNG seed is an instance-specific FEC OTI attribute | seed. This PRNG seed is an instance-specific FEC OTI attribute | |||

(Section 4.2.3). | (Section 4.2.3). | |||

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 MUST be generated by using the following function: | |||

/* initialize a list of all possible choices in order to | /* | |||

* Initialize the left side of the parity check matrix. | ||||

* This function assumes that an empty matrix of size n-k * k has | ||||

* previously been allocated/reset and that the matrix_has_entry(), | ||||

* matrix_insert_entry() and degree_of_row() functions can access it. | ||||

* (IN): the k and n parameters. | ||||

*/ | ||||

void left_matrix_init (int k, int n) | ||||

{ | ||||

int i; /* row index or temporary variable */ | ||||

int j; /* column index */ | ||||

int h; | ||||

int t; /* left limit within the list of possible choices u[] */ | ||||

int u[3*MAX_K]; /* table used to have a homogeneous 1 distrib. */ | ||||

/* 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[] */ | ||||

t = 0; | ||||

/* Initialize the matrix with 3 "1s" per column, homogeneously */ | ||||

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" */ | |||

/* check that valid available choices remain */ | /* check that valid available choices remain */ | |||

for (i = t; i < 3*k && matrix_has_entry(u[i], j); i++); | for (i = t; i < 3*k && matrix_has_entry(u[i], j); i++); | |||

if (i < 3*k) { | if (i < 3*k) { | |||

/* choose one index within the list of possible | /* choose one index within the list of possible | |||

* choices */ | * choices */ | |||

do { | do { | |||

i = t + rand(3*k-t); | i = t + pmms_rand(3*k-t); | |||

} while (matrix_has_entry(u[i], j)); | } while (matrix_has_entry(u[i], j)); | |||

matrix_insert_entry(u[i], j); | matrix_insert_entry(u[i], j); | |||

/* replace with u[t] which has never been chosen */ | /* replace with u[t] which has never been chosen */ | |||

u[i] = u[t]; | u[i] = u[t]; | |||

t++; | t++; | |||

} else { | } else { | |||

/* no choice left, choose one randomly */ | /* no choice left, choose one randomly */ | |||

do { | do { | |||

i = rand(n-k); | i = pmms_rand(n-k); | |||

} while (matrix_has_entry(i, j)); | } while (matrix_has_entry(i, j)); | |||

matrix_insert_entry(i, j); | matrix_insert_entry(i, j); | |||

} | } | |||

} | } | |||

} | } | |||

/* Add extra bits to avoid rows with less than two "1s". | /* Add extra bits to avoid rows with less than two "1s". | |||

* This is needed when the code rate is smaller than 2/5. */ | * This is needed when the code rate is smaller than 2/5. */ | |||

for (i = 0; i < n-k; i++) { /* for each row */ | for (i = 0; i < n-k; i++) { /* for each row */ | |||

if (degree_of_row(i) == 0) { | if (degree_of_row(i) == 0) { | |||

j = rand(k); | j = pmms_rand(k); | |||

matrix_insert_entry(i, j); | matrix_insert_entry(i, j); | |||

} | } | |||

if (degree_of_row(i) == 1) { | if (degree_of_row(i) == 1) { | |||

do { | do { | |||

j = rand(k); | j = pmms_rand(k); | |||

} while (matrix_has_entry(i, j)); | } while (matrix_has_entry(i, j)); | |||

matrix_insert_entry(i, j); | matrix_insert_entry(i, j); | |||

} | } | |||

} | } | |||

The right side (the staircase) is generated by the following | } | |||

algorithm: | ||||

The right side (the staircase) MUST be generated by using the | ||||

following function: | ||||

/* | ||||

* Initialize the right side of the parity check matrix with a | ||||

* staircase structure. | ||||

* (IN): the k and n parameters. | ||||

*/ | ||||

void right_matrix_staircase_init (int k, int n) | ||||

{ | ||||

int i; /* row index */ | ||||

matrix_insert_entry(0, k); /* first row */ | matrix_insert_entry(0, k); /* first row */ | |||

for (i = 1; i < n-k; i++) { /* for the following rows */ | for (i = 1; i < n-k; i++) { /* for the following rows */ | |||

matrix_insert_entry(i, k+i); /* identity */ | matrix_insert_entry(i, k+i); /* identity */ | |||

matrix_insert_entry(i, k+i-1); /* staircase */ | matrix_insert_entry(i, k+i-1); /* staircase */ | |||

} | } | |||

} | ||||

Note that just after creating this parity check matrix, when encoding | Note that just after creating this parity check matrix, when encoding | |||

symbol groups are used (i.e., G > 1), the function initializing the | symbol groups are used (i.e., G > 1), the function initializing the | |||

two random permutation tables (Section 5.6) MUST be called. This is | two random permutation tables (Section 5.6) MUST be called. This is | |||

true both at a sender and at a receiver. | true both at a sender and at a receiver. | |||

6.3. Encoding | 6.3. Encoding | |||

Thanks to the staircase matrix, repair symbol creation is | Thanks to the staircase matrix, repair symbol creation is | |||

straightforward: each repair symbol is equal to the sum of all source | straightforward: each repair symbol is equal to the sum of all source | |||

skipping to change at page 24, line 44 | skipping to change at page 25, line 52 | |||

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 [ZP74]: given a set of linear equations, | following trivial algorithm [ZP74]: given a set of linear equations, | |||

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

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

this variable by its value in all the remaining linear equations and | this 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 B sketches a possible implementation of this algorithm. | Appendix A sketches a possible implementation of this algorithm. | |||

A Gaussian elimination (or any optimized derivative) is another | A Gaussian elimination (or any optimized derivative) is another | |||

possible decoding technique. Hybrid solutions that start by using | possible decoding technique. Hybrid solutions that start by using | |||

the trivial algorithm above and finish with a Gaussian 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. | |||

skipping to change at page 26, line 22 | skipping to change at page 27, line 22 | |||

seed. This PRNG seed is an instance-specific FEC OTI attribute | seed. This PRNG seed is an instance-specific FEC OTI attribute | |||

(Section 4.2.3). | (Section 4.2.3). | |||

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

The LDPC-Triangle matrix can be divided into two parts: the left side | The LDPC-Triangle matrix can be divided into two parts: the left side | |||

of the matrix defines in which equations the source symbols are | of the matrix defines in which equations the source symbols are | |||

involved; the right side of the matrix defines in which equations the | involved; the right side of the matrix defines in which equations the | |||

repair symbols are involved. | repair symbols are involved. | |||

The left side is generated with the same algorithm as that of LDPC- | The left side MUST be generated by using the same left_matrix_init() | |||

Staircase (Section 6.2). | function as with LDPC-Staircase (Section 6.2). | |||

The right side (the triangle) is generated with the following | The right side (the triangle) MUST be generated by using the | |||

algorithm: | following function: | |||

/* | ||||

* Initialize the right side of the parity check matrix with a | ||||

* triangle structure. | ||||

* (IN): the k and n parameters. | ||||

*/ | ||||

void right_matrix_staircase_init (int k, int n) | ||||

{ | ||||

int i; /* row index */ | ||||

int j; /* randomly chosen column indexes in 0..n-k-2 */ | ||||

int l; /* limitation of the # of "1s" added per row */ | ||||

matrix_insert_entry(0, k); /* first row */ | matrix_insert_entry(0, k); /* first row */ | |||

for (i = 1; i < n-k; i++) { /* for the following rows */ | for (i = 1; i < n-k; i++) { /* for the following rows */ | |||

matrix_insert_entry(i, k+i); /* identity */ | matrix_insert_entry(i, k+i); /* identity */ | |||

matrix_insert_entry(i, k+i-1); /* staircase */ | matrix_insert_entry(i, k+i-1); /* staircase */ | |||

/* now fill the triangle */ | /* now fill the triangle */ | |||

j = i-1; | j = i-1; | |||

for (l = 0; l < j; l++) { /* limit the # of "1s" added */ | for (l = 0; l < j; l++) { /* limit the # of "1s" added */ | |||

j = rand(j); | j = pmms_rand(j); | |||

matrix_insert_entry(i, k+j); | matrix_insert_entry(i, k+j); | |||

} | } | |||

} | } | |||

} | ||||

Note that just after creating this parity check matrix, when encoding | Note that just after creating this parity check matrix, when encoding | |||

symbol groups are used (i.e., G > 1), the function initializing the | symbol groups are used (i.e., G > 1), the function initializing the | |||

two random permutation tables (Section 5.6) MUST be called. This is | two random permutation tables (Section 5.6) MUST be called. This is | |||

true both at a sender and at a receiver. | true both at a sender and at a receiver. | |||

7.3. Encoding | 7.3. Encoding | |||

Here also repair symbol creation is straightforward: each repair | Here also repair symbol creation is straightforward: each repair | |||

symbol of ESI i is equal to the sum of all source and repair symbols | symbol of ESI i is equal to the sum of all source and repair symbols | |||

skipping to change at page 28, line 43 | skipping to change at page 29, line 43 | |||

(e.g., by sending forged symbols) or against the FEC parameters that | (e.g., by sending forged symbols) or against the FEC parameters that | |||

are sent either in-band (e.g., in an EXT_FTI or FDT Instance) or out- | are sent either in-band (e.g., in an EXT_FTI or FDT Instance) or out- | |||

of-band (e.g., in a session description). | of-band (e.g., in a session description). | |||

8.2. Attacks Against the Data Flow | 8.2. Attacks Against the Data Flow | |||

First of all, let us consider the attacks against the data flow. | First of all, let us consider the attacks against the data flow. | |||

8.2.1. Access to Confidential Objects | 8.2.1. Access to Confidential Objects | |||

Access control to the object being transmitted is typically provided | Access control to a confidential object being transmitted is | |||

by means of encryption. This encryption can be done over the whole | typically provided by means of encryption. This encryption can be | |||

object (e.g., by the content provider, before the FEC encoding | done over the whole object (e.g., by the content provider, before the | |||

process), or be done on a packet per packet basis (e.g., when IPSec/ | FEC encoding process), or be done on a packet per packet basis (e.g., | |||

ESP is used [RFC4303]). If access control is a concern, it is | when IPsec/ESP is used [RFC4303]). If confidentiality is a concern, | |||

RECOMMENDED that one of these solutions be used. Even if we mention | it is RECOMMENDED that one of these solutions be used. Even if we | |||

these attacks here, they are not related nor facilitated by the use | mention these attacks here, they are not related nor facilitated by | |||

of FEC. | the use of FEC. | |||

8.2.2. Content Corruption | 8.2.2. Content Corruption | |||

Protection against corruptions (e.g., after sending forged packets) | Protection against corruptions (e.g., after sending forged packets) | |||

is achieved by means of a content integrity verification/sender | is achieved by means of a content integrity verification/sender | |||

authentication scheme. This service can be provided at the object | authentication scheme. This service can be provided at the object | |||

level, but in that case a receiver has no way to identify which | level, but in that case a receiver has no way to identify which | |||

symbol(s) is(are) corrupted if the object is detected as corrupted. | symbol(s) is(are) corrupted if the object is detected as corrupted. | |||

This service can also be provided at the packet level. In this case, | This service can also be provided at the packet level. In this case, | |||

after removing all forged packets, the object may be in some case | after removing all forged packets, the object may be in some case | |||

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

o at the object level, the object MAY be digitally signed (with | o at the object level, the object MAY be digitally signed (with | |||

public key cryptography), for instance by using RSASSA-PKCS1-v1_5 | public key cryptography), for instance by using RSASSA-PKCS1-v1_5 | |||

[RFC3447]. This signature enables a receiver to check the object | [RFC3447]. This signature enables a receiver to check the object | |||

integrity, once this latter has been fully decoded. Even if | integrity, once this latter has been fully decoded. Even if | |||

digital signatures are computationally expensive, this calculation | digital signatures are computationally expensive, this calculation | |||

occurs only once per object, which is usually acceptable; | occurs only once per object, which is usually acceptable; | |||

o at the packet level, each packet can be digitally signed. A major | o at the packet level, each packet can be digitally signed. A major | |||

limitation is the high computational and transmission overheads | limitation is the high computational and transmission overheads | |||

that this solution requires (unless Elliptic Curve Cryptography | that this solution requires (unless perhaps if Elliptic Curve | |||

(ECC) is used). To avoid this problem, the signature may span a | Cryptography (ECC) is used). To avoid this problem, the signature | |||

set of symbols (instead of a single one) in order to amortize the | may span a set of symbols (instead of a single one) in order to | |||

signature calculation. But if a single symbol is missing, the | amortize the signature calculation. But if a single symbol is | |||

integrity of the whole set cannot be checked; | missing, the integrity of the whole set cannot be checked; | |||

o at the packet level, a Group Message Authentication Code (MAC) | o at the packet level, a Group Message Authentication Code (MAC) | |||

[RFC2104] scheme can be used, for instance by using HMAC-SHA-1 | [RFC2104] scheme can be used, for instance by using HMAC-SHA-1 | |||

with a secret key shared by all the group members, senders and | with a secret key shared by all the group members, senders and | |||

receivers. This technique creates a cryptographically secured | receivers. This technique creates a cryptographically secured | |||

(thanks to the secret key) digest of a packet that is sent along | (thanks to the secret key) digest of a packet that is sent along | |||

with the packet. The Group MAC scheme does not create prohibitive | with the packet. The Group MAC scheme does not create prohibitive | |||

processing load nor transmission overhead, but it has a major | processing load nor transmission overhead, but it has a major | |||

limitation: it only provides a group authentication/integrity | limitation: it only provides a group authentication/integrity | |||

service since all group members share the same secret group key, | service since all group members share the same secret group key, | |||

which means that each member can send a forged packet. It is | which means that each member can send a forged packet. It is | |||

therefore restricted to situations where group members are fully | therefore restricted to situations where group members are fully | |||

trusted (or in association with another technique as a pre-check); | trusted (or in association with another technique as a pre-check); | |||

o at the packet level, TESLA [RFC4082] is a very attractive and | o at the packet level, TESLA [RFC4082] is an attractive solution | |||

efficient solution that is robust to losses, provides a true | that is robust to losses, provides a true authentication/integrity | |||

authentication/integrity service, and does not create any | service, and does not create any prohibitive processing load or | |||

prohibitive processing load or transmission overhead. Yet | transmission overhead. Yet checking a packet requires a small | |||

checking a packet requires a small delay (a second or more) after | delay (a second or more) after its reception; | |||

its reception; | ||||

Techniques relying on public key cryptography (digital signatures and | Techniques relying on public key cryptography (digital signatures and | |||

TESLA during the bootstrap process, when used) require that public | TESLA during the bootstrap process, when used) require that public | |||

keys be securely associated to the entities. This can be achieved by | keys be securely associated to the entities. This can be achieved by | |||

a Public Key Infrastructure (PKI), or by a PGP Web of Trust, or by | a Public Key Infrastructure (PKI), or by a PGP Web of Trust, or by | |||

pre-distributing the public keys of each group member. | pre-distributing the public keys of each group member. | |||

Techniques relying on symmetric key cryptography (group MAC) require | Techniques relying on symmetric key cryptography (group MAC) require | |||

that a secret key be shared by all group members. This can be | that a secret key be shared by all group members. This can be | |||

achieved by means of a group key management protocol, or simply by | achieved by means of a group key management protocol, or simply by | |||

pre-distributing the secret key (but this manual solution has many | pre-distributing the secret key (but this manual solution has many | |||

limitations). | limitations). | |||

It is up to the developer and deployer, who know the security | It is up to the CDP developer, who knows the security requirements | |||

requirements and features of the target application area, to define | and features of the target application area, to define which solution | |||

which solution is the most appropriate. Nonetheless, in case there | is the most appropriate. Nonetheless, in case there is any concern | |||

is any concern of the threat of object corruption, it is RECOMMENDED | of the threat of object corruption, it is RECOMMENDED that at least | |||

that at least one of these techniques be used. | one of these techniques be used. | |||

8.3. Attacks Against the FEC Parameters | 8.3. Attacks Against the FEC Parameters | |||

Let us now consider attacks against the FEC parameters (or FEC OTI). | Let us now consider attacks against the FEC parameters (or FEC OTI). | |||

The FEC OTI can either be sent in-band (i.e., in an EXT_FTI or in an | The FEC OTI can either be sent in-band (i.e., in an EXT_FTI or in an | |||

FDT Instance containing FEC OTI for the object) or out-of-band (e.g., | FDT Instance containing FEC OTI for the object) or out-of-band (e.g., | |||

in a session description). Attacks on these FEC parameters can | in a session description). Attacks on these FEC parameters can | |||

prevent the decoding of the associated object: for instance modifying | prevent the decoding of the associated object: for instance modifying | |||

the B parameter will lead to a different block partitioning. | the B parameter will lead to a different block partitioning. | |||

It is therefore RECOMMENDED that security measures be taken to | It is therefore RECOMMENDED that security measures be taken to | |||

guarantee the FEC OTI integrity. To that purpose, the packets | guarantee the FEC OTI integrity. To that purpose, the packets | |||

carrying the FEC parameters sent in-band in an EXT_FTI header | carrying the FEC parameters sent in-band in an EXT_FTI header | |||

extension SHOULD be protected by one of the per-packet techniques | extension SHOULD be protected by one of the per-packet techniques | |||

described above: digital signature, group MAC, or TESLA. When FEC | described above: digital signature, group MAC, or TESLA. When FEC | |||

OTI is contained in an FDT Instance, this object SHOULD be protected, | OTI is contained in an FDT Instance, this object SHOULD be protected, | |||

for instance by digitally signing it with XML digital signatures | for instance by digitally signing it with XML digital signatures | |||

[RFC3275]. Finally, when FEC OTI is sent out-of-band (e.g., in a | [RFC3275]. Finally, when FEC OTI is sent out-of-band (e.g., in a | |||

session description) this latter SHOULD be protected, for instance by | session description) this latter SHOULD be protected, for instance by | |||

digitally signing it. | digitally signing it with [RFC3852]. | |||

The same considerations concerning the key management aspects apply | The same considerations concerning the key management aspects apply | |||

here also. | here also. | |||

9. IANA Considerations | 9. IANA Considerations | |||

Values of FEC Encoding IDs and FEC Instance IDs are subject to IANA | Values of FEC Encoding IDs and FEC Instance IDs are subject to IANA | |||

registration. For general guidelines on IANA considerations as they | registration. For general guidelines on IANA considerations as they | |||

apply to this document, see [RFC5052]. | apply to this document, see [RFC5052]. | |||

skipping to change at page 32, line 10 | skipping to change at page 33, line 10 | |||

"ietf:rmt:fec:encoding" name-space to "LDPC Staircase Codes". | "ietf:rmt:fec:encoding" name-space to "LDPC Staircase Codes". | |||

This document assigns the Fully-Specified FEC Encoding ID 4 under the | This document assigns the Fully-Specified FEC Encoding ID 4 under the | |||

"ietf:rmt:fec:encoding" name-space to "LDPC Triangle Codes". | "ietf:rmt:fec:encoding" name-space to "LDPC Triangle Codes". | |||

10. Acknowledgments | 10. Acknowledgments | |||

Section 5.5 is derived from a previous Internet-Draft, and we would | Section 5.5 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, Shao Wenjian, Brian Carpenter, Magnus Westerlund, and | Francillon, Shao Wenjian, Magnus Westerlund, Brian Carpenter, Tim | |||

Alfred Hoenes for their comments. | Polk, Jari Arkko, Chris Newman, Robin Whittle and Alfred Hoenes for | |||

their comments. | ||||

Last but not least, the authors are grateful to Radford M. Neal | Last but not least, the authors are grateful to Radford M. Neal | |||

(University of Toronto) whose LDPC software | (University of Toronto) whose LDPC software | |||

(http://www.cs.toronto.edu/~radford/ldpc.software.html) inspired this | (http://www.cs.toronto.edu/~radford/ldpc.software.html) inspired this | |||

work. | work. | |||

11. References | 11. References | |||

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

skipping to change at page 34, line 9 | skipping to change at page 35, line 9 | |||

64298-1, 2003. | 64298-1, 2003. | |||

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

Ones are Hard to Find", Communications of the ACM, Vol. | Ones are Hard to Find", Communications of the ACM, Vol. | |||

31, No. 10, pp.1192-1201, 1988. | 31, No. 10, pp.1192-1201, 1988. | |||

[CA90] Carta, D., "Two Fast Implementations of the Minimal | [CA90] Carta, D., "Two Fast Implementations of the Minimal | |||

Standard Random Number Generator", Communications of the | Standard Random Number Generator", Communications of the | |||

ACM, Vol. 33, No. 1, pp.87-88, January 1990. | ACM, Vol. 33, No. 1, pp.87-88, January 1990. | |||

[WI08] Whittle, R., "Park-Miller-Carta Pseudo-Random Number | ||||

Generator", http://www.firstpr.com.au/dsp/rand31/, | ||||

January 2008. | ||||

[rand31pmc] | ||||

Whittle, R., "31 bit pseudo-random number generator", htt | ||||

p://www.firstpr.com.au/dsp/rand31/ | ||||

rand31-park-miller-carta.cc.txt, September 2005. | ||||

[PTVF92] Press, W., Teukolsky, S., Vetterling, W., and B. Flannery, | [PTVF92] Press, W., Teukolsky, S., Vetterling, W., and B. Flannery, | |||

"Numerical Recipies in C; Second Edition", Cambridge | "Numerical Recipies in C; Second Edition", Cambridge | |||

University Press, ISBN: 0-521-43108-5, 1992. | University Press, ISBN: 0-521-43108-5, 1992. | |||

[draft-ietf-rmt-pi-alc-revised] | [draft-ietf-rmt-pi-alc-revised] | |||

Luby, M., Watson, M., and L. Vicisano, "Asynchronous | Luby, M., Watson, M., and L. Vicisano, "Asynchronous | |||

Layered Coding (ALC) Protocol Instantiation", | Layered Coding (ALC) Protocol Instantiation", | |||

draft-ietf-rmt-pi-alc-revised-04.txt (work in progress), | draft-ietf-rmt-pi-alc-revised-04.txt (work in progress), | |||

February 2007. | February 2007. | |||

skipping to change at page 35, line 5 | skipping to change at page 36, line 10 | |||

RFC 2104, February 1997. | RFC 2104, February 1997. | |||

[RFC4082] "Timed Efficient Stream Loss-Tolerant Authentication | [RFC4082] "Timed Efficient Stream Loss-Tolerant Authentication | |||

(TESLA): Multicast Source Authentication Transform | (TESLA): Multicast Source Authentication Transform | |||

Introduction", RFC 4082, June 2005. | Introduction", RFC 4082, June 2005. | |||

[RFC3275] Eastlake, D., Reagle, J., and D. Solo, "(Extensible Markup | [RFC3275] Eastlake, D., Reagle, J., and D. Solo, "(Extensible Markup | |||

Language) XML-Signature Syntax and Processing", RFC 3275, | Language) XML-Signature Syntax and Processing", RFC 3275, | |||

March 2002. | March 2002. | |||

Appendix A. Pseudo Random Number Generator Example Implementation | [RFC3852] Housley, R., "Cryptographic Message Syntax (CMS)", | |||

(Informative Only) | RFC 3852, July 2004. | |||

The following is an implementation of the minimal standard generator | ||||

defined in Section 5.7 that scales the result between 0 and maxv-1 | ||||

inclusive. It uses the Park and Miller algorithm [PM88] with the | ||||

optimization suggested by D. Carta in [CA90]. The inner algorithm | ||||

relies on 32 bit mathematics only and does not require any division. | ||||

unsigned long seed; | ||||

/* | ||||

* Initialize the PRNG with a seed between | ||||

* 1 and 0x7FFFFFFE (i.e., 2^^31-2) inclusive. | ||||

*/ | ||||

void srand (unsigned long s) | ||||

{ | ||||

if ((s > 0) && (s < 0x7FFFFFFF)) | ||||

seed = s; | ||||

else | ||||

exit(-1); | ||||

} | ||||

/* | ||||

* Returns a random integer in [0; maxv-1] | ||||

* Derived from rand31pmc, Robin Whittle, | ||||

* September 20th, 2005. | ||||

* http://www.firstpr.com.au/dsp/rand31/ | ||||

* 16807 multiplier constant (7^^5) | ||||

* 0x7FFFFFFF modulo constant (2^^31-1) | ||||

* The inner PRNG produces a value between 1 and | ||||

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

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

* inclusive. | ||||

*/ | ||||

unsigned long | ||||

rand (unsigned long maxv) | ||||

{ | ||||

unsigned long hi, lo; | ||||

lo = 16807 * (seed & 0xFFFF); | [RFC4648] Josefsson, S., "The Base16, Base32, and Base64 Data | |||

hi = 16807 * (seed >> 16); /* binary shift to right */ | Encodings", RFC 4648, October 2006. | |||

lo += (hi & 0x7FFF) << 16; /* binary shift to left */ | ||||

lo += hi >> 15; | ||||

if (lo > 0x7FFFFFFF) | ||||

lo -= 0x7FFFFFFF; | ||||

seed = lo; | ||||

/* don't use modulo, least significant bits are less random | ||||

* than most significant bits [PTVF92] */ | ||||

return ((unsigned long) | ||||

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

} | ||||

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

A trivial decoding algorithm is sketched below (please see | A trivial decoding algorithm is sketched below (please see | |||

[LDPC-codec] for the details omitted here): | [LDPC-codec] for 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; | |||

skipping to change at page 40, line 7 | skipping to change at page 40, 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 (2007). | Copyright (C) The IETF Trust (2008). | |||

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. 47 change blocks. | ||||

176 lines changed or deleted | | 185 lines changed or added | ||

This html diff was produced by rfcdiff 1.34. The latest version is available from http://tools.ietf.org/tools/rfcdiff/ |