draft-ietf-tsvwg-rlc-fec-scheme-04.txt   draft-ietf-tsvwg-rlc-fec-scheme-05.txt 
TSVWG V. Roca TSVWG V. Roca
Internet-Draft B. Teibi Internet-Draft B. Teibi
Intended status: Standards Track INRIA Intended status: Standards Track INRIA
Expires: November 18, 2018 May 17, 2018 Expires: November 24, 2018 May 23, 2018
Sliding Window Random Linear Code (RLC) Forward Erasure Correction (FEC) Sliding Window Random Linear Code (RLC) Forward Erasure Correction (FEC)
Schemes for FECFRAME Schemes for FECFRAME
draft-ietf-tsvwg-rlc-fec-scheme-04 draft-ietf-tsvwg-rlc-fec-scheme-05
Abstract Abstract
This document describes two fully-specified Forward Erasure This document describes two fully-specified Forward Erasure
Correction (FEC) Schemes for Sliding Window Random Linear Codes Correction (FEC) Schemes for Sliding Window Random Linear Codes
(RLC), one for RLC over GF(2) (binary case), a second one for RLC (RLC), one for RLC over GF(2) (binary case), a second one for RLC
over GF(2^^8), both of them with the possibility of controlling the over GF(2^^8), both of them with the possibility of controlling the
code density. They can protect arbitrary media streams along the code density. They can protect arbitrary media streams along the
lines defined by FECFRAME extended to sliding window FEC codes. lines defined by FECFRAME extended to sliding window FEC codes.
These sliding window FEC codes rely on an encoding window that slides These sliding window FEC codes rely on an encoding window that slides
skipping to change at page 1, line 42 skipping to change at page 1, line 42
Internet-Drafts are working documents of the Internet Engineering Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet- working documents as Internet-Drafts. The list of current Internet-
Drafts is at https://datatracker.ietf.org/drafts/current/. Drafts is at https://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months Internet-Drafts are draft documents valid for a maximum of six months
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."
This Internet-Draft will expire on November 18, 2018. This Internet-Draft will expire on November 24, 2018.
Copyright Notice Copyright Notice
Copyright (c) 2018 IETF Trust and the persons identified as the Copyright (c) 2018 IETF Trust and the persons identified as the
document authors. All rights reserved. document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents Provisions Relating to IETF Documents
(https://trustee.ietf.org/license-info) in effect on the date of (https://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents publication of this document. Please review these documents
skipping to change at page 2, line 31 skipping to change at page 2, line 31
1.3. Small Transmission Overheads with the Sliding Window RLC 1.3. Small Transmission Overheads with the Sliding Window RLC
FEC Scheme . . . . . . . . . . . . . . . . . . . . . . . 5 FEC Scheme . . . . . . . . . . . . . . . . . . . . . . . 5
1.4. Document Organization . . . . . . . . . . . . . . . . . . 6 1.4. Document Organization . . . . . . . . . . . . . . . . . . 6
2. Definitions and Abbreviations . . . . . . . . . . . . . . . . 6 2. Definitions and Abbreviations . . . . . . . . . . . . . . . . 6
3. Procedures . . . . . . . . . . . . . . . . . . . . . . . . . 7 3. Procedures . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.1. Possible Parameter Derivations . . . . . . . . . . . . . 7 3.1. Possible Parameter Derivations . . . . . . . . . . . . . 7
3.1.1. Case of a CBR Real-Time Flow . . . . . . . . . . . . 8 3.1.1. Case of a CBR Real-Time Flow . . . . . . . . . . . . 8
3.1.2. Other Types of Real-Time Flow . . . . . . . . . . . . 10 3.1.2. Other Types of Real-Time Flow . . . . . . . . . . . . 10
3.1.3. Case of a Non Real-Time Flow . . . . . . . . . . . . 11 3.1.3. Case of a Non Real-Time Flow . . . . . . . . . . . . 11
3.2. ADU, ADUI and Source Symbols Mappings . . . . . . . . . . 11 3.2. ADU, ADUI and Source Symbols Mappings . . . . . . . . . . 11
3.3. Encoding Window Management . . . . . . . . . . . . . . . 12 3.3. Encoding Window Management . . . . . . . . . . . . . . . 13
3.4. Pseudo-Random Number Generator . . . . . . . . . . . . . 13 3.4. Pseudo-Random Number Generator (PRNG) . . . . . . . . . . 13
3.5. Coding Coefficients Generation Function . . . . . . . . . 14 3.5. Coding Coefficients Generation Function . . . . . . . . . 14
3.6. Finite Fields Operations . . . . . . . . . . . . . . . . 17 3.6. Finite Fields Operations . . . . . . . . . . . . . . . . 17
3.6.1. Linear Combination of Source Symbols Computation . . 17 3.6.1. Finite Field Definitions . . . . . . . . . . . . . . 17
3.6.2. Linear Combination of Source Symbols Computation . . 17
4. Sliding Window RLC FEC Scheme over GF(2^^8) for Arbitrary ADU 4. Sliding Window RLC FEC Scheme over GF(2^^8) for Arbitrary ADU
Flows . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 Flows . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
4.1. Formats and Codes . . . . . . . . . . . . . . . . . . . . 18 4.1. Formats and Codes . . . . . . . . . . . . . . . . . . . . 18
4.1.1. FEC Framework Configuration Information . . . . . . . 18 4.1.1. FEC Framework Configuration Information . . . . . . . 18
4.1.2. Explicit Source FEC Payload ID . . . . . . . . . . . 19 4.1.2. Explicit Source FEC Payload ID . . . . . . . . . . . 19
4.1.3. Repair FEC Payload ID . . . . . . . . . . . . . . . . 20 4.1.3. Repair FEC Payload ID . . . . . . . . . . . . . . . . 20
4.1.4. Additional Procedures . . . . . . . . . . . . . . . . 21 4.1.4. Additional Procedures . . . . . . . . . . . . . . . . 21
5. Sliding Window RLC FEC Scheme over GF(2) for Arbitrary ADU 5. Sliding Window RLC FEC Scheme over GF(2) for Arbitrary ADU
Flows . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 Flows . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
5.1. Formats and Codes . . . . . . . . . . . . . . . . . . . . 22 5.1. Formats and Codes . . . . . . . . . . . . . . . . . . . . 21
5.1.1. FEC Framework Configuration Information . . . . . . . 22 5.1.1. FEC Framework Configuration Information . . . . . . . 21
5.1.2. Explicit Source FEC Payload ID . . . . . . . . . . . 22 5.1.2. Explicit Source FEC Payload ID . . . . . . . . . . . 22
5.1.3. Repair FEC Payload ID . . . . . . . . . . . . . . . . 22 5.1.3. Repair FEC Payload ID . . . . . . . . . . . . . . . . 22
5.1.4. Additional Procedures . . . . . . . . . . . . . . . . 22 5.1.4. Additional Procedures . . . . . . . . . . . . . . . . 22
6. FEC Code Specification . . . . . . . . . . . . . . . . . . . 22 6. FEC Code Specification . . . . . . . . . . . . . . . . . . . 22
6.1. Encoding Side . . . . . . . . . . . . . . . . . . . . . . 22 6.1. Encoding Side . . . . . . . . . . . . . . . . . . . . . . 22
6.2. Decoding Side . . . . . . . . . . . . . . . . . . . . . . 23 6.2. Decoding Side . . . . . . . . . . . . . . . . . . . . . . 23
7. Implementation Status . . . . . . . . . . . . . . . . . . . . 24 7. Implementation Status . . . . . . . . . . . . . . . . . . . . 24
8. Security Considerations . . . . . . . . . . . . . . . . . . . 24 8. Security Considerations . . . . . . . . . . . . . . . . . . . 24
8.1. Attacks Against the Data Flow . . . . . . . . . . . . . . 24 8.1. Attacks Against the Data Flow . . . . . . . . . . . . . . 24
8.1.1. Access to Confidential Content . . . . . . . . . . . 24 8.1.1. Access to Confidential Content . . . . . . . . . . . 24
8.1.2. Content Corruption . . . . . . . . . . . . . . . . . 25 8.1.2. Content Corruption . . . . . . . . . . . . . . . . . 24
8.2. Attacks Against the FEC Parameters . . . . . . . . . . . 25 8.2. Attacks Against the FEC Parameters . . . . . . . . . . . 25
8.3. When Several Source Flows are to be Protected Together . 25 8.3. When Several Source Flows are to be Protected Together . 25
8.4. Baseline Secure FEC Framework Operation . . . . . . . . . 25 8.4. Baseline Secure FEC Framework Operation . . . . . . . . . 25
9. Operations and Management Considerations . . . . . . . . . . 26 9. Operations and Management Considerations . . . . . . . . . . 25
9.1. Operational Recommendations: Finite Field GF(2) Versus 9.1. Operational Recommendations: Finite Field GF(2) Versus
GF(2^^8) . . . . . . . . . . . . . . . . . . . . . . . . 26 GF(2^^8) . . . . . . . . . . . . . . . . . . . . . . . . 26
9.2. Operational Recommendations: Coding Coefficients Density 9.2. Operational Recommendations: Coding Coefficients Density
Threshold . . . . . . . . . . . . . . . . . . . . . . . . 26 Threshold . . . . . . . . . . . . . . . . . . . . . . . . 26
10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 27 10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 26
11. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 27 11. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 27
12. References . . . . . . . . . . . . . . . . . . . . . . . . . 27 12. References . . . . . . . . . . . . . . . . . . . . . . . . . 27
12.1. Normative References . . . . . . . . . . . . . . . . . . 27 12.1. Normative References . . . . . . . . . . . . . . . . . . 27
12.2. Informative References . . . . . . . . . . . . . . . . . 28 12.2. Informative References . . . . . . . . . . . . . . . . . 27
Appendix A. Decoding Beyond Maximum Latency Optimization . . . . 30 Appendix A. TinyMT32 Pseudo-Random Number Generator . . . . . . 29
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 31 Appendix B. Decoding Beyond Maximum Latency Optimization . . . . 32
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 33
1. Introduction 1. Introduction
Application-Level Forward Erasure Correction (AL-FEC) codes, or Application-Level Forward Erasure Correction (AL-FEC) codes, or
simply FEC codes, are a key element of communication systems. They simply FEC codes, are a key element of communication systems. They
are used to recover from packet losses (or erasures) during content are used to recover from packet losses (or erasures) during content
delivery sessions to a large number of receivers (multicast/broadcast delivery sessions to a large number of receivers (multicast/broadcast
transmissions). This is the case with the FLUTE/ALC protocol transmissions). This is the case with the FLUTE/ALC protocol
[RFC6726] when used for reliable file transfers over lossy networks, [RFC6726] when used for reliable file transfers over lossy networks,
and the FECFRAME protocol when used for reliable continuous media and the FECFRAME protocol when used for reliable continuous media
skipping to change at page 4, line 47 skipping to change at page 4, line 49
(symbols) are generated on-the-fly, computing a random linear (symbols) are generated on-the-fly, computing a random linear
combination of the source symbols present in the current encoding combination of the source symbols present in the current encoding
window, and passed to the transport layer. window, and passed to the transport layer.
At the receiver, a linear system is managed from the set of received At the receiver, a linear system is managed from the set of received
source and repair packets. New variables (representing source source and repair packets. New variables (representing source
symbols) and equations (representing the linear combination of each symbols) and equations (representing the linear combination of each
repair symbol received) are added upon receiving new packets. repair symbol received) are added upon receiving new packets.
Variables are removed when they are too old with respect to their Variables are removed when they are too old with respect to their
validity period (real-time constraints), as well as the associated validity period (real-time constraints), as well as the associated
equations they are involved in (Appendix A introduces an optimization equations they are involved in (Appendix B introduces an optimization
that extends the time a variable is considered in the system). Lost that extends the time a variable is considered in the system). Lost
source symbols are then recovered thanks to this linear system source symbols are then recovered thanks to this linear system
whenever its rank permits it. whenever its rank permits it.
With RLC codes (more generally with sliding window codes), the With RLC codes (more generally with sliding window codes), the
protection of a multicast/broadcast session also needs to be protection of a multicast/broadcast session also needs to be
dimensioned by considering the worst communication conditions one dimensioned by considering the worst communication conditions one
wants to support. However the receivers experiencing a good to wants to support. However the receivers experiencing a good to
medium communication quality will observe a reduced FEC-related medium communication quality will observe a reduced FEC-related
latency compared to block codes [Roca17] since an isolated lost latency compared to block codes [Roca17] since an isolated lost
skipping to change at page 7, line 4 skipping to change at page 7, line 7
assumed fixed (in bits/s) assumed fixed (in bits/s)
max_lat: maximum FEC-related latency within FECFRAME (in seconds) max_lat: maximum FEC-related latency within FECFRAME (in seconds)
cr: RLC coding rate, ratio between the total number of source cr: RLC coding rate, ratio between the total number of source
symbols and the total number of source plus repair symbols symbols and the total number of source plus repair symbols
ew_size: encoding window current size at a sender (in symbols) ew_size: encoding window current size at a sender (in symbols)
ew_max_size: encoding window maximum size at a sender (in symbols) ew_max_size: encoding window maximum size at a sender (in symbols)
dw_max_size: decoding window maximum size at a receiver (in symbols) dw_max_size: decoding window maximum size at a receiver (in symbols)
ls_max_size: linear system maximum size (or width) at a receiver (in ls_max_size: linear system maximum size (or width) at a receiver (in
symbols) symbols)
PRNG: pseudo-random number generator PRNG: pseudo-random number generator
pmms_rand(maxv): PRNG defined in Section 3.4 and used in this tinymt32_rand(maxv): PRNG defined in Section 3.4 and used in this
specification, that returns a new random integer in [0; maxv-1] specification, that returns a new random integer in [0; maxv-1]
DT: coding coefficients density threshold, an integer between 0 and DT: coding coefficients density threshold, an integer between 0 and
15 (inclusive) the controls the fraction of coefficients that are 15 (inclusive) the controls the fraction of coefficients that are
non zero non zero
3. Procedures 3. Procedures
This section introduces the procedures that are used by these FEC This section introduces the procedures that are used by these FEC
Schemes. Schemes.
skipping to change at page 8, line 11 skipping to change at page 8, line 17
or lost source symbols that are still within their latency budget; or lost source symbols that are still within their latency budget;
Linear system maximum size, ls_max_size (in symbols): at a FECFRAME Linear system maximum size, ls_max_size (in symbols): at a FECFRAME
receiver, the linear system maximum size, ls_max_size, is the receiver, the linear system maximum size, ls_max_size, is the
maximum number of received or lost source symbols in the linear maximum number of received or lost source symbols in the linear
system (i.e., the variables). It SHOULD NOT be smaller than system (i.e., the variables). It SHOULD NOT be smaller than
dw_max_size since it would mean that, even after receiving a dw_max_size since it would mean that, even after receiving a
sufficient number of FEC Repair Packets, a lost ADU may not be sufficient number of FEC Repair Packets, a lost ADU may not be
recovered just because the associated source symbols have been recovered just because the associated source symbols have been
prematurely removed from the linear system, which is usually prematurely removed from the linear system, which is usually
counter-productive. On the opposite, the linear system MAY grow counter-productive. On the opposite, the linear system MAY grow
beyond the dw_max_size (Appendix A); beyond the dw_max_size (Appendix B);
Symbol size, E (in bytes): the E parameter determines the source and Symbol size, E (in bytes): the E parameter determines the source and
repair symbol sizes (necessarily equal). This is an input repair symbol sizes (necessarily equal). This is an input
parameter that enables a FECFRAME sender to derive other internal parameter that enables a FECFRAME sender to derive other internal
parameters, as explained below. An implementation at a sender parameters, as explained below. An implementation at a sender
SHOULD fix the E parameter and communicate it as part of the FEC SHOULD fix the E parameter and communicate it as part of the FEC
Scheme-Specific Information (Section 4.1.1.2). Scheme-Specific Information (Section 4.1.1.2).
Code rate, cr: The code rate parameter determines the amount of Code rate, cr: The code rate parameter determines the amount of
redundancy added to the flow. More precisely the cr is the ratio redundancy added to the flow. More precisely the cr is the ratio
between the total number of source symbols and the total number of between the total number of source symbols and the total number of
source plus repair symbols and by definition: 0 < cr <= 1. This source plus repair symbols and by definition: 0 < cr <= 1. This
skipping to change at page 9, line 43 skipping to change at page 9, line 48
received FEC Repair Packets (Section 4.1.3). A receiver can then received FEC Repair Packets (Section 4.1.3). A receiver can then
easily compute dw_max_size: easily compute dw_max_size:
dw_max_size = max_NSS_observed / 0.75 dw_max_size = max_NSS_observed / 0.75
A receiver can then chose an appropriate linear system maximum size: A receiver can then chose an appropriate linear system maximum size:
ls_max_size >= dw_max_size ls_max_size >= dw_max_size
It is good practice to use a larger value for ls_max_size as It is good practice to use a larger value for ls_max_size as
explained in Appendix A, which does not impact maximum latency nor explained in Appendix B, which does not impact maximum latency nor
interoperability. However the linear system size should not be too interoperability. However the linear system size should not be too
large for practical reasons (e.g., in order to limit computation large for practical reasons (e.g., in order to limit computation
complexity). complexity).
The particular case of session start needs to be managed The particular case of session start needs to be managed
appropriately. Here ew_size increases each time a new source ADU is appropriately. Here ew_size increases each time a new source ADU is
received by the FECFRAME sender, until it reaches the ew_max_size received by the FECFRAME sender, until it reaches the ew_max_size
value. A FECFRAME receiver SHOULD continuously observe the received value. A FECFRAME receiver SHOULD continuously observe the received
FEC Repair Packets, since the NSS value carried in the Repair FEC FEC Repair Packets, since the NSS value carried in the Repair FEC
Payload ID will increase too, and adjust its ls_max_size accordingly Payload ID will increase too, and adjust its ls_max_size accordingly
skipping to change at page 10, line 49 skipping to change at page 11, line 7
With both approaches, and no matter the choice of the FECFRAME With both approaches, and no matter the choice of the FECFRAME
sender, a FECFRAME receiver can still easily evaluate the ew_max_size sender, a FECFRAME receiver can still easily evaluate the ew_max_size
by observing the maximum Number of Source Symbols (NSS) value by observing the maximum Number of Source Symbols (NSS) value
contained in the Repair FEC Payload ID of received FEC Repair contained in the Repair FEC Payload ID of received FEC Repair
Packets. A receiver can then compute dw_max_size and derive an Packets. A receiver can then compute dw_max_size and derive an
appropriate ls_max_size as explained in Section 3.1.1. appropriate ls_max_size as explained in Section 3.1.1.
When the observed NSS fluctuates significantly, a FECFRAME receiver When the observed NSS fluctuates significantly, a FECFRAME receiver
may want to adapt its ls_max_size accordingly. In particular when may want to adapt its ls_max_size accordingly. In particular when
the NSS is significanlty reduced, a FECFRAME receiver may want to the NSS is significantly reduced, a FECFRAME receiver may want to
reduce the ls_max_size too in order to limit computation complexity. reduce the ls_max_size too in order to limit computation complexity.
However it is usually preferable to use a ls_max_size "too large" However it is usually preferable to use a ls_max_size "too large"
(which can increase computation complexity and memory requirements) (which can increase computation complexity and memory requirements)
than the opposite (which can reduce recovery performance). than the opposite (which can reduce recovery performance).
Beyond these general guidelines, the details of how to manage these Beyond these general guidelines, the details of how to manage these
situations at a FECFRAME sender and receiver can depend on additional situations at a FECFRAME sender and receiver can depend on additional
considerations that are out of scope of this document. considerations that are out of scope of this document.
3.1.3. Case of a Non Real-Time Flow 3.1.3. Case of a Non Real-Time Flow
skipping to change at page 13, line 28 skipping to change at page 13, line 33
ew_size, is updated after adding new source symbols. This process ew_size, is updated after adding new source symbols. This process
may require to remove old source symbols so that: ew_size <= may require to remove old source symbols so that: ew_size <=
ew_max_size. ew_max_size.
Note that a FEC codec may feature practical limits in the number of Note that a FEC codec may feature practical limits in the number of
source symbols in the encoding window (e.g., for computational source symbols in the encoding window (e.g., for computational
complexity reasons). This factor may further limit the ew_max_size complexity reasons). This factor may further limit the ew_max_size
value, in addition to the maximum FEC-related latency budget value, in addition to the maximum FEC-related latency budget
(Section 3.1). (Section 3.1).
3.4. Pseudo-Random Number Generator 3.4. Pseudo-Random Number Generator (PRNG)
The RLC codes rely on the following Pseudo-Random Number Generator
(PRNG), identical to the PRNG used with LDPC-Staircase codes
([RFC5170], section 5.7).
The Park-Miler "minimal standard" PRNG [PM88] MUST be used. It The RLC FEC Schemes defined in this document rely on the TinyMT32
defines a simple multiplicative congruential algorithm: Ij+1 = A * Ij PRNG, a small-sized variant of the Mersenne Twister PRNG, as defined
(modulo M), with the following choices: A = 7^^5 = 16807 and M = in the reference implementation version 1.1 (2015/04/24) by Mutsuo
2^^31 - 1 = 2147483647. A validation criteria of such a PRNG is the Saito (Hiroshima University) and Makoto Matsumoto (The University of
following: if seed = 1, then the 10,000th value returned MUST be Tokyo).
equal to 1043618065.
Several implementations of this PRNG are known and discussed in the o Official web site: <http://www.math.sci.hiroshima-u.ac.jp/~m-
literature. An optimized implementation of this algorithm, using mat/MT/TINYMT/>
only 32-bit mathematics, and which does not require any division, can o Official github site and reference implementation:
be found in [rand31pmc]. It uses the Park and Miller algorithm <https://github.com/MersenneTwister-Lab/TinyMT>
[PM88] with the optimization suggested by D. Carta in [CA90]. The
history behind this algorithm is detailed in [WI08].
This PRNG produces, natively, a 31-bit value between 1 and 0x7FFFFFFE For the RLC FEC Schemes defined in this document, the tinymt32 32-bit
(2^^31-2) inclusive. Since it is desired to scale the pseudo-random version (rather than the 64-bit version) MUST be used. This PRNG
number between 0 and maxv-1 inclusive, one must keep the most requires a parameter set that needs to be pre-calculated. For the
significant bits of the value returned by the PRNG (the least RLC FEC Schemes defined in this document, the following parameter set
significant bits are known to be less random, and modulo-based MUST be used:
solutions should be avoided [PTVF92]). The following algorithm MUST
be used:
Input: o mat1 = 0x8f7011ee = 2406486510;
o mat2 = 0xfc78ff1f = 4235788063;
o tmat = 0x3793fdff = 932445695.
raw_value: random integer generated by the inner PRNG algorithm, This parameter set is the first entry of the precalculated parameter
between 1 and 0x7FFFFFFE (2^^31-2) inclusive. sets in file tinymt32dc.0.1048576.txt, by Kenji Rikitake, and
maxv: upper bound used during the scaling operation. available at:
Output: o <https://github.com/jj1bdx/tinymtdc-
longbatch/blob/master/tinymt32dc/tinymt32dc.0.1048576.txt>.
scaled_value: random integer between 0 and maxv-1 inclusive. This is also the parameter set used in [KR12].
Algorithm: The PRNG reference implementation is distributed under a BSD license
and excerpts of it are reproduced in Appendix A. In order to
validate an implementation of this PRNG, using seed 1, the 10,000th
value returned by: tinymt32_rand(s, 0xffff) MUST be equal to 0x7c37.
scaled_value = (unsigned long) ((double)maxv * (double)raw_value / This PRNG MUST first be initialized with a 32-bit unsigned integer,
(double)0x7FFFFFFF); used as a seed. The following function is used to this purpose:
(NB: the above C type casting to unsigned long is equivalent to
using floor() with positive floating point values.)
In this document, pmms_rand(maxv) denotes the PRNG function that void tinymt32_init (tinymt32_t * s, uint32_t seed);
implements the Park-Miller "minimal standard" algorithm, defined
above, and that scales the raw value between 0 and maxv-1 inclusive,
using the above scaling algorithm.
Additionally, the pmms_srand(seed) function must be provided to With the FEC Schemes defined in this document, the seed is in
enable the initialization of the PRNG with a seed before calling practice restricted to a value between 0 and 0xFFFF inclusive (note
pmms_rand(maxv) the first time. The seed is a 31-bit integer between that this PRNG accepts a seed equal to 0), since this is the
1 and 0x7FFFFFFE inclusive. In this specification, the seed is
restricted to a value between 1 and 0xFFFF inclusive, as this is the
Repair_Key 16-bit field value of the Repair FEC Payload ID Repair_Key 16-bit field value of the Repair FEC Payload ID
(Section 4.1.3). (Section 4.1.3). In addition to the seed, this function takes as
parameter a pointer to an instance of a tinymt32_t structure that is
used to keep the internal state of the PRNG.
Then, each time a new pseudo-random integer between 0 and maxv-1
inclusive is needed, the following function is used:
uint32_t tinymt32_rand (tinymt32_t * s, uint32_t maxv);
This function takes as parameter both a pointer to the same
tinymt32_t structure (that needs to be left unchanged between
successive calls to the function) and the maxv value.
3.5. Coding Coefficients Generation Function 3.5. Coding Coefficients Generation Function
The coding coefficients, used during the encoding process, are The coding coefficients, used during the encoding process, are
generated at the RLC encoder by the generate_coding_coefficients() generated at the RLC encoder by the generate_coding_coefficients()
function each time a new repair symbol needs to be produced. The function each time a new repair symbol needs to be produced. The
fraction of coefficients that are non zero (i.e., the density) is fraction of coefficients that are non zero (i.e., the density) is
controlled by the DT (Density Threshold) parameter. When DT equals controlled by the DT (Density Threshold) parameter. When DT equals
15, the maximum value, the function guaranties that all coefficients 15, the maximum value, the function guaranties that all coefficients
are non zero (i.e., maximum density). When DT is between 0 (minimum are non zero (i.e., maximum density). When DT is between 0 (minimum
skipping to change at page 15, line 32 skipping to change at page 15, line 36
* (in) dt integer between 0 and 15 (inclusive) that * (in) dt integer between 0 and 15 (inclusive) that
* controls the density. With value 15, all * controls the density. With value 15, all
* coefficients are guaranteed to be non zero * coefficients are guaranteed to be non zero
* (i.e. equal to 1 with GF(2) and equal to a * (i.e. equal to 1 with GF(2) and equal to a
* value in {1,... 255} with GF(2^^8)), otherwise * value in {1,... 255} with GF(2^^8)), otherwise
* a fraction of them will be 0. * a fraction of them will be 0.
* (in) m Finite Field GF(2^^m) parameter. In this * (in) m Finite Field GF(2^^m) parameter. In this
* document only values 1 and 8 are considered. * document only values 1 and 8 are considered.
* (out) returns an error code * (out) returns an error code
*/ */
int generate_coding_coefficients (UINT16 repair_key, int generate_coding_coefficients (uint16_t repair_key,
UINT8 cc_tab[], uint8_t cc_tab[],
UINT16 cc_nb, uint16_t cc_nb,
UINT8 dt, uint8_t dt,
UINT8 m) uint8_t m)
{ {
UINT32 i; uint32_t i;
tinymt32_t s; /* PRNG internal state */
if (dt > 15) { if (dt > 15) {
return SOMETHING_WENT_WRONG; /* bad dt parameter */ return SOMETHING_WENT_WRONG; /* bad dt parameter */
} }
switch (m) { switch (m) {
case 1: case 1:
if (dt == 15) { if (dt == 15) {
/* all coefficients are 1 */ /* all coefficients are 1 */
memset(cc_tab, 1, cc_nb); memset(cc_tab, 1, cc_nb);
} else { } else {
/* here coefficients are either 0 or 1 */ /* here coefficients are either 0 or 1 */
if (repair_key == 0) { tinymt32_init(&s, repair_key);
return SOMETHING_WENT_WRONG; /* bad repair_key */
}
pmms_srand(repair_key);
pmms_rand(16); /* skip the first PRNG value */
for (i = 0 ; i < cc_nb ; i++) { for (i = 0 ; i < cc_nb ; i++) {
if (pmms_rand(16) <= dt) { if (tinymt32_rand(&s, 16) <= dt) {
cc_tab[i] = (UINT8) 1; cc_tab[i] = (uint8_t) 1;
} else { } else {
cc_tab[i] = (UINT8) 0; cc_tab[i] = (uint8_t) 0;
} }
} }
} }
break; break;
case 8: case 8:
if (repair_key == 0) { tinymt32_init(&s, repair_key);
return SOMETHING_WENT_WRONG; /* bad repair_key */
}
pmms_srand(repair_key);
pmms_rand(256); /* skip the first PRNG value */
if (dt == 15) { if (dt == 15) {
/* coefficient 0 is avoided here in order to include /* coefficient 0 is avoided here in order to include
* all the source symbols */ * all the source symbols */
for (i = 0 ; i < cc_nb ; i++) { for (i = 0 ; i < cc_nb ; i++) {
do { do {
cc_tab[i] = (UINT8) pmms_rand(256); cc_tab[i] = (uint8_t) tinymt32_rand(&s, 256);
} while (cc_tab[i] == 0); } while (cc_tab[i] == 0);
} }
} else { } else {
/* here a certain fraction of coefficients should be 0 */ /* here a certain fraction of coefficients should be 0 */
for (i = 0 ; i < cc_nb ; i++) { for (i = 0 ; i < cc_nb ; i++) {
if (pmms_rand(16) <= dt) { if (tinymt32_rand(&s, 16) <= dt) {
do { do {
cc_tab[i] = (UINT8) pmms_rand(256); cc_tab[i] = (uint8_t) tinymt32_rand(&s, 256);
} while (cc_tab[i] == 0); } while (cc_tab[i] == 0);
} else { } else {
cc_tab[i] = 0; cc_tab[i] = 0;
} }
} }
} }
break; break;
default: default:
/* bad parameter m */ /* bad parameter m */
return SOMETHING_WENT_WRONG; return SOMETHING_WENT_WRONG;
} }
return EVERYTHING_IS_OKAY; return EVERYTHING_IS_OKAY;
} }
<CODE ENDS> <CODE ENDS>
Figure 2: Coding Coefficients Generation Function pseudo-code
One can note in the above function that each call to pmms_srand() Figure 2: Coding Coefficients Generation Function pseudo-code
(PRNG initialisation) is immediately followed by a call to
pmms_rand() whose return value is ignored. This extra call is
motivated by a possible bias in the first value generated depending
on the way the repair key is managed by a FECFRAME implementation.
Indeed, the PRNG sequences produced by two seeds in sequence have a
high probability of starting with the same value since I1 = A * seed
(modulo M) which is further scaled to a small range (either {0, ...
15} or {0, ... 255}). Producing several times the same first coding
coefficient could reduce the protection of the first source symbol if
multiple repair symbols are produced with the same coding window's
left edge. The extra call avoids such side effects.
3.6. Finite Fields Operations 3.6. Finite Fields Operations
3.6.1. Finite Field Definitions
The two RLC FEC Schemes specified in this document reuse the Finite The two RLC FEC Schemes specified in this document reuse the Finite
Fields defined in [RFC5510], section 8.1. More specifically, the Fields defined in [RFC5510], section 8.1. More specifically, the
elements of the field GF(2^^m) are represented by polynomials with elements of the field GF(2^^m) are represented by polynomials with
binary coefficients (i.e., over GF(2)) and degree lower or equal to binary coefficients (i.e., over GF(2)) and degree lower or equal to
m-1. The addition between two elements is defined as the addition of m-1. The addition between two elements is defined as the addition of
binary polynomials in GF(2), which is equivalent to a bitwise XOR binary polynomials in GF(2), which is equivalent to a bitwise XOR
operation on the binary representation of these elements. operation on the binary representation of these elements.
With GF(2^^8), multiplication between two elements is the With GF(2^^8), multiplication between two elements is the
multiplication modulo a given irreducible polynomial of degree 8. multiplication modulo a given irreducible polynomial of degree 8.
The following irreducible polynomial MUST be used for GF(2^^8): The following irreducible polynomial MUST be used for GF(2^^8):
x^^8 + x^^4 + x^^3 + x^^2 + 1 x^^8 + x^^4 + x^^3 + x^^2 + 1
With GF(2), multiplication corresponds to a logical AND operation. With GF(2), multiplication corresponds to a logical AND operation.
3.6.1. Linear Combination of Source Symbols Computation 3.6.2. Linear Combination of Source Symbols Computation
The two RLC FEC Schemes require the computation of a linear The two RLC FEC Schemes require the computation of a linear
combination of source symbols, using the coding coefficients produced combination of source symbols, using the coding coefficients produced
by the generate_coding_coefficients() function and stored in the by the generate_coding_coefficients() function and stored in the
cc_tab[] array. cc_tab[] array.
With the RLC over GF(2^^8) FEC Scheme, a linear combination of the With the RLC over GF(2^^8) FEC Scheme, a linear combination of the
ew_size source symbol present in the encoding window, say src_0 to ew_size source symbol present in the encoding window, say src_0 to
src_ew_size_1, in order to generate a repair symbol, is computed as src_ew_size_1, in order to generate a repair symbol, is computed as
follows. For each byte of position i in each source and the repair follows. For each byte of position i in each source and the repair
skipping to change at page 20, line 51 skipping to change at page 20, line 37
+--------------------------------+ +--------------------------------+
Figure 6: Structure of an FEC Repair Packet with the Repair FEC Figure 6: Structure of an FEC Repair Packet with the Repair FEC
Payload ID Payload ID
More precisely, the Repair FEC Payload ID is composed of the More precisely, the Repair FEC Payload ID is composed of the
following fields (Figure 7): following fields (Figure 7):
Repair_Key (16-bit field): this unsigned integer is used as a seed Repair_Key (16-bit field): this unsigned integer is used as a seed
by the coefficient generation function (Section 3.5) in order to by the coefficient generation function (Section 3.5) in order to
generate the desired number of coding coefficients. Value 0 MUST generate the desired number of coding coefficients. When a FEC
NOT be used. When a FEC Repair Packet contains several repair Repair Packet contains several repair symbols, this repair key
symbols, this repair key value is that of the first repair symbol. value is that of the first repair symbol. The remaining repair
The remaining repair keys can be deduced by incrementing by 1 this keys can be deduced by incrementing by 1 this value, up to a
value, up to a maximum value of 65535 after which it loops back to maximum value of 65535 after which it loops back to 0.
1 (note that 0 is not a valid value).
Density Threshold for the coding coefficients, DT (4-bit field): Density Threshold for the coding coefficients, DT (4-bit field):
this unsigned integer carries the Density Threshold (DT) used by this unsigned integer carries the Density Threshold (DT) used by
the coding coefficient generation function Section 3.5. More the coding coefficient generation function Section 3.5. More
precisely, it controls the probability of having a non zero coding precisely, it controls the probability of having a non zero coding
coefficient, which equals (DT+1) / 16. When a FEC Repair Packet coefficient, which equals (DT+1) / 16. When a FEC Repair Packet
contains several repair symbols, the DT value applies to all of contains several repair symbols, the DT value applies to all of
them; them;
Number of Source Symbols in the encoding window, NSS (12-bit field): Number of Source Symbols in the encoding window, NSS (12-bit field):
this unsigned integer indicates the number of source symbols in this unsigned integer indicates the number of source symbols in
skipping to change at page 22, line 47 skipping to change at page 22, line 35
6. FEC Code Specification 6. FEC Code Specification
6.1. Encoding Side 6.1. Encoding Side
This section provides a high level description of a Sliding Window This section provides a high level description of a Sliding Window
RLC encoder. RLC encoder.
Whenever a new FEC Repair Packet is needed, the RLC encoder instance Whenever a new FEC Repair Packet is needed, the RLC encoder instance
first gathers the ew_size source symbols currently in the sliding first gathers the ew_size source symbols currently in the sliding
encoding window. Then it chooses a repair key, which can be a non encoding window. Then it chooses a repair key, which can be a
zero monotonically increasing integer value, incremented for each monotonically increasing integer value, incremented for each repair
repair symbol up to a maximum value of 65535 (as it is carried within symbol up to a maximum value of 65535 (as it is carried within a
a 16-bit field) after which it loops back to 1 (indeed, being used as 16-bit field) after which it loops back to 0. This repair key is
a PRNG seed, value 0 is prohibited). This repair key is communicated communicated to the coefficient generation function (Section 3.5) in
to the coefficient generation function (Section Section 3.5) in order order to generate ew_size coding coefficients. Finally, the FECFRAME
to generate ew_size coding coefficients. Finally, the FECFRAME
sender computes the repair symbol as a linear combination of the sender computes the repair symbol as a linear combination of the
ew_size source symbols using the ew_size coding coefficients. When E ew_size source symbols using the ew_size coding coefficients
is small and when there is an incentive to pack several repair (Section 3.6). When E is small and when there is an incentive to
symbols within the same FEC Repair Packet, the appropriate number of pack several repair symbols within the same FEC Repair Packet, the
repair symbols are computed. In that case the repair key for each of appropriate number of repair symbols are computed. In that case the
them MUST be incremented by 1, keeping the same ew_size source repair key for each of them MUST be incremented by 1, keeping the
symbols, since only the first repair key will be carried in the same ew_size source symbols, since only the first repair key will be
Repair FEC Payload ID. The FEC Repair Packet can then be passed to carried in the Repair FEC Payload ID. The FEC Repair Packet can then
the transport layer for transmission. The source versus repair FEC be passed to the transport layer for transmission. The source versus
packet transmission order is out of scope of this document and repair FEC packet transmission order is out of scope of this document
several approaches exist that are implementation specific. and several approaches exist that are implementation specific.
Other solutions are possible to select a repair key value when a new Other solutions are possible to select a repair key value when a new
FEC Repair Packet is needed, for instance by choosing a random FEC Repair Packet is needed, for instance by choosing a random
integer between 1 and 65535. However, selecting the same repair key integer between 0 and 65535. However, selecting the same repair key
as before (which may happen in case of a random process) is only as before (which may happen in case of a random process) is only
meaningful if the encoding window has changed, otherwise the same FEC meaningful if the encoding window has changed, otherwise the same FEC
Repair Packet will be generated. Repair Packet will be generated.
6.2. Decoding Side 6.2. Decoding Side
This section provides a high level description of a Sliding Window This section provides a high level description of a Sliding Window
RLC decoder. RLC decoder.
A FECFRAME receiver needs to maintain a linear system whose variables A FECFRAME receiver needs to maintain a linear system whose variables
skipping to change at page 24, line 14 skipping to change at page 23, line 49
With real-time flows, a lost ADU that is decoded after the maximum With real-time flows, a lost ADU that is decoded after the maximum
latency or an ADU received after this delay has no value to the latency or an ADU received after this delay has no value to the
application. This raises the question of deciding whether or not an application. This raises the question of deciding whether or not an
ADU is late. This decision MAY be taken within the FECFRAME receiver ADU is late. This decision MAY be taken within the FECFRAME receiver
(e.g., using the decoding window, see Section 3.1) or within the (e.g., using the decoding window, see Section 3.1) or within the
application (e.g., using RTP timestamps within the ADU). Deciding application (e.g., using RTP timestamps within the ADU). Deciding
which option to follow and whether or not to pass all ADUs, including which option to follow and whether or not to pass all ADUs, including
those assumed late, to the application are operational decisions that those assumed late, to the application are operational decisions that
depend on the application and are therefore out of scope of this depend on the application and are therefore out of scope of this
document. Additionally, Appendix A discusses a backward compatible document. Additionally, Appendix B discusses a backward compatible
optimization whereby late source symbols MAY still be used within the optimization whereby late source symbols MAY still be used within the
FECFRAME receiver in order to improve the global robustness. FECFRAME receiver in order to improve transmission robustness.
7. Implementation Status 7. Implementation Status
Editor's notes: RFC Editor, please remove this section motivated by Editor's notes: RFC Editor, please remove this section motivated by
RFC 6982 before publishing the RFC. Thanks. RFC 6982 before publishing the RFC. Thanks.
An implementation of the Sliding Window RLC FEC Scheme for FECFRAME An implementation of the Sliding Window RLC FEC Scheme for FECFRAME
exists: exists:
o Organisation: Inria o Organisation: Inria
skipping to change at page 28, line 7 skipping to change at page 27, line 47
DOI 10.17487/RFC6363, October 2011, DOI 10.17487/RFC6363, October 2011,
<https://www.rfc-editor.org/info/rfc6363>. <https://www.rfc-editor.org/info/rfc6363>.
[RFC6364] Begen, A., "Session Description Protocol Elements for the [RFC6364] Begen, A., "Session Description Protocol Elements for the
Forward Error Correction (FEC) Framework", RFC 6364, Forward Error Correction (FEC) Framework", RFC 6364,
DOI 10.17487/RFC6364, October 2011, DOI 10.17487/RFC6364, October 2011,
<https://www.rfc-editor.org/info/rfc6364>. <https://www.rfc-editor.org/info/rfc6364>.
12.2. Informative References 12.2. Informative References
[CA90] Carta, D., "Two Fast Implementations of the Minimal [KR12] Rikitake, K., "TinyMT Pseudo Random Number Generator for
Standard Random Number Generator", Communications of the Erlang", ACM 11th SIGPLAN Erlang Workshop (Erlang'12),
ACM, Vol. 33, No. 1, pp.87-88, January 1990. September 14, 2012, Copenhagen, Denmark, DOI:
http://dx.doi.org/10.1145/2364489.2364504, September 2012.
[PGM13] Plank, J., Greenan, K., and E. Miller, "A Complete [PGM13] Plank, J., Greenan, K., and E. Miller, "A Complete
Treatment of Software Implementations of Finite Field Treatment of Software Implementations of Finite Field
Arithmetic for Erasure Coding Applications", University of Arithmetic for Erasure Coding Applications", University of
Tennessee Technical Report UT-CS-13-717, Tennessee Technical Report UT-CS-13-717,
http://web.eecs.utk.edu/~plank/plank/papers/ http://web.eecs.utk.edu/~plank/plank/papers/
UT-CS-13-717.html, October 2013, UT-CS-13-717.html, October 2013,
<http://web.eecs.utk.edu/~plank/plank/papers/ <http://web.eecs.utk.edu/~plank/plank/papers/
UT-CS-13-717.html>. UT-CS-13-717.html>.
[PM88] 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.
[PTVF92] Press, W., Teukolsky, S., Vetterling, W., and B. Flannery,
"Numerical Recipies in C; Second Edition", Cambridge
University Press, ISBN: 0-521-43108-5, 1992.
[rand31pmc]
Whittle, R., "31 bit pseudo-random number generator",
September 2005, <http://www.firstpr.com.au/dsp/rand31/
rand31-park-miller-carta.cc.txt>.
[RFC5170] Roca, V., Neumann, C., and D. Furodet, "Low Density Parity
Check (LDPC) Staircase and Triangle Forward Error
Correction (FEC) Schemes", RFC 5170, DOI 10.17487/RFC5170,
June 2008, <https://www.rfc-editor.org/info/rfc5170>.
[RFC5510] Lacan, J., Roca, V., Peltotalo, J., and S. Peltotalo, [RFC5510] Lacan, J., Roca, V., Peltotalo, J., and S. Peltotalo,
"Reed-Solomon Forward Error Correction (FEC) Schemes", "Reed-Solomon Forward Error Correction (FEC) Schemes",
RFC 5510, DOI 10.17487/RFC5510, April 2009, RFC 5510, DOI 10.17487/RFC5510, April 2009,
<https://www.rfc-editor.org/info/rfc5510>. <https://www.rfc-editor.org/info/rfc5510>.
[RFC6726] Paila, T., Walsh, R., Luby, M., Roca, V., and R. Lehtonen, [RFC6726] Paila, T., Walsh, R., Luby, M., Roca, V., and R. Lehtonen,
"FLUTE - File Delivery over Unidirectional Transport", "FLUTE - File Delivery over Unidirectional Transport",
RFC 6726, DOI 10.17487/RFC6726, November 2012, RFC 6726, DOI 10.17487/RFC6726, November 2012,
<https://www.rfc-editor.org/info/rfc6726>. <https://www.rfc-editor.org/info/rfc6726>.
skipping to change at page 29, line 27 skipping to change at page 29, line 5
[Roca17] Roca, V., Teibi, B., Burdinat, C., Tran, T., and C. [Roca17] Roca, V., Teibi, B., Burdinat, C., Tran, T., and C.
Thienot, "Less Latency and Better Protection with AL-FEC Thienot, "Less Latency and Better Protection with AL-FEC
Sliding Window Codes: a Robust Multimedia CBR Broadcast Sliding Window Codes: a Robust Multimedia CBR Broadcast
Case Study", 13th IEEE International Conference on Case Study", 13th IEEE International Conference on
Wireless and Mobile Computing, Networking and Wireless and Mobile Computing, Networking and
Communications (WiMob17), October Communications (WiMob17), October
2017 https://hal.inria.fr/hal-01571609v1/en/, October 2017 https://hal.inria.fr/hal-01571609v1/en/, October
2017, <https://hal.inria.fr/hal-01571609v1/en/>. 2017, <https://hal.inria.fr/hal-01571609v1/en/>.
[WI08] Whittle, R., "Park-Miller-Carta Pseudo-Random Number Appendix A. TinyMT32 Pseudo-Random Number Generator
Generator", http://www.firstpr.com.au/dsp/rand31/,
January 2008, <http://www.firstpr.com.au/dsp/rand31/>.
Appendix A. Decoding Beyond Maximum Latency Optimization The TinyMT32 PRNG reference implementation is distributed under a BSD
license by the authors and excerpts of it are reproduced in Figure 8.
Differences with respect to the original source code are the
following:
o unused parts of the original source code have been removed;
o the appropriate parameter set has been added to the initialisation
function;
o function tinymt32_rand() has been added;
o function order has been changed;
o certain internal variables have been renamed for compactness
purposes.
<CODE BEGINS>
/**
* Tiny Mersenne Twister only 127 bit internal state
*
* Authors : Mutsuo Saito (Hiroshima University)
* Makoto Matsumoto (University of Tokyo)
*
* Copyright (c) 2011, 2013 Mutsuo Saito, Makoto Matsumoto,
* Hiroshima University and The University of Tokyo.
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* - Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* - Redistributions in binary form must reproduce the above
* copyright notice, this list of conditions and the following
* disclaimer in the documentation and/or other materials
* provided with the distribution.
* - Neither the name of the Hiroshima University nor the names of
* its contributors may be used to endorse or promote products
* derived from this software without specific prior written
* permission.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
* CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
* INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
* MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
* DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS
* BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
* EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
* TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
* ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR
* TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF
* THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
* SUCH DAMAGE.
*/
/**
* tinymt32 internal state vector and parameters
*/
typedef struct {
uint32_t status[4];
uint32_t mat1;
uint32_t mat2;
uint32_t tmat;
} tinymt32_t;
static void tinymt32_next_state (tinymt32_t * s);
static uint32_t tinymt32_temper (tinymt32_t * s);
static double tinymt32_generate_32double (tinymt32_t * s);
/**
* Parameter set to use for RLC FEC Schemes. Do not change.
*/
#define TINYMT32_MAT1_PARAM 0x8f7011ee
#define TINYMT32_MAT2_PARAM 0xfc78ff1f
#define TINYMT32_TMAT_PARAM 0x3793fdff
/**
* This function initializes the internal state array with a 32-bit
* unsigned integer seed.
* @param s tinymt state vector.
* @param seed a 32-bit unsigned integer used as a seed.
*/
void tinymt32_init (tinymt32_t * s, uint32_t seed)
{
#define MIN_LOOP 8
#define PRE_LOOP 8
s->status[0] = seed;
s->status[1] = s->mat1 = TINYMT32_MAT1_PARAM;
s->status[2] = s->mat2 = TINYMT32_MAT2_PARAM;
s->status[3] = s->tmat = TINYMT32_TMAT_PARAM;
for (int i = 1; i < MIN_LOOP; i++) {
s->status[i & 3] ^= i + UINT32_C(1812433253)
* (s->status[(i - 1) & 3]
^ (s->status[(i - 1) & 3] >> 30));
}
for (int i = 0; i < PRE_LOOP; i++) {
tinymt32_next_state(s);
}
}
/**
* This function outputs an integer in the [0 .. maxv-1] range.
* @param s tinymt internal status
* @return floating point number r (0.0 <= r < 1.0)
*/
uint32_t tinymt32_rand (tinymt32_t * s, uint32_t maxv)
{
return (uint32_t)(tinymt32_generate_32double(s) * (double)maxv);
}
/**
* Internal tinymt32 constants and functions.
* Users should not call these functions directly.
*/
#define TINYMT32_MEXP 127
#define TINYMT32_SH0 1
#define TINYMT32_SH1 10
#define TINYMT32_SH8 8
#define TINYMT32_MASK UINT32_C(0x7fffffff)
#define TINYMT32_MUL (1.0f / 16777216.0f)
/**
* This function changes internal state of tinymt32.
* @param s tinymt internal status
*/
static void tinymt32_next_state (tinymt32_t * s)
{
uint32_t x;
uint32_t y;
y = s->status[3];
x = (s->status[0] & TINYMT32_MASK)
^ s->status[1]
^ s->status[2];
x ^= (x << TINYMT32_SH0);
y ^= (y >> TINYMT32_SH0) ^ x;
s->status[0] = s->status[1];
s->status[1] = s->status[2];
s->status[2] = x ^ (y << TINYMT32_SH1);
s->status[3] = y;
s->status[1] ^= -((int32_t)(y & 1)) & s->mat1;
s->status[2] ^= -((int32_t)(y & 1)) & s->mat2;
}
/**
* This function outputs 32-bit unsigned integer from internal state.
* @param s tinymt internal status
* @return 32-bit unsigned pseudos number
*/
static uint32_t tinymt32_temper (tinymt32_t * s)
{
uint32_t t0, t1;
t0 = s->status[3];
t1 = s->status[0] + (s->status[2] >> TINYMT32_SH8);
t0 ^= t1;
t0 ^= -((int32_t)(t1 & 1)) & s->tmat;
return t0;
}
/**
* This function outputs double precision floating point number from
* internal state. The returned value has 32-bit precision.
* In other words, this function makes one double precision floating
* point number from one 32-bit unsigned integer.
* @param s tinymt internal status
* @return floating point number r (0.0 <= r < 1.0)
*/
static double tinymt32_generate_32double (tinymt32_t * s)
{
tinymt32_next_state(s);
return (double)tinymt32_temper(s) * (1.0 / 4294967296.0);
}
<CODE ENDS>
Figure 8: TinyMT32 pseudo-code
Appendix B. Decoding Beyond Maximum Latency Optimization
This annex introduces non normative considerations. They are This annex introduces non normative considerations. They are
provided as suggestions, without any impact on interoperability. For provided as suggestions, without any impact on interoperability. For
more information see [Roca16]. more information see [Roca16].
With a real-time source ADU flow, it is possible to improve the With a real-time source ADU flow, it is possible to improve the
decoding performance of sliding window codes without impacting decoding performance of sliding window codes without impacting
maximum latency, at the cost of extra CPU overhead. The optimization maximum latency, at the cost of extra CPU overhead. The optimization
consists, for a FECFRAME receiver, to extend the linear system beyond consists, for a FECFRAME receiver, to extend the linear system beyond
the decoding window maximum size, by keeping a certain number of old the decoding window maximum size, by keeping a certain number of old
skipping to change at page 30, line 46 skipping to change at page 33, line 33
without relying on this optimization. without relying on this optimization.
ls_max_size ls_max_size
/---------------------------------^-------------------------------\ /---------------------------------^-------------------------------\
late source symbols late source symbols
(pot. decoded but not delivered) dw_max_size (pot. decoded but not delivered) dw_max_size
/--------------^-----------------\ /--------------^---------------\ /--------------^-----------------\ /--------------^---------------\
src0 src1 src2 src3 src4 src5 src6 src7 src8 src9 src10 src11 src12 src0 src1 src2 src3 src4 src5 src6 src7 src8 src9 src10 src11 src12
Figure 8: Relationship between parameters to decode beyond maximum Figure 9: Relationship between parameters to decode beyond maximum
latency. latency.
It means that source symbols, and therefore ADUs, may be decoded even It means that source symbols, and therefore ADUs, may be decoded even
if the added latency exceeds the maximum value permitted by the if the added latency exceeds the maximum value permitted by the
application. It follows that the corresponding ADUs will not be application. It follows that the corresponding ADUs will not be
useful to the application. However, decoding these "late symbols" useful to the application. However, decoding these "late symbols"
significantly improves the global robustness in bad reception significantly improves the global robustness in bad reception
conditions and is therefore recommended for receivers experiencing conditions and is therefore recommended for receivers experiencing
bad communication conditions [Roca16]. In any case whether or not to bad communication conditions [Roca16]. In any case whether or not to
use this optimization and what exact value to use for the ls_max_size use this optimization and what exact value to use for the ls_max_size
 End of changes. 53 change blocks. 
153 lines changed or deleted 293 lines changed or added

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