```
Figure 2: 4-bit and 8-bit mapping functions for TinyMT32
- Any implementation of this PRNG MUST fulfil three validation
- criteria, the one described in [tinymt32] (for the TinyMT32 32-bit
- unsigned integer generator) and the two ones detailed in Appendix A
- (for the mapping to 4-bit and 8-bit intervals). Because of the way
- the mapping functions work, it is unlikely that an implementation
- that fulfils the first criteria fails to fulfil the two additional
- ones.
+ Any implementation of this PRNG MUST fulfill three validation
+ criteria: the one described in [tinymt32] (for the TinyMT32 32-bit
+ unsigned integer generator), and the two others detailed in
+ Appendix A (for the mapping to 4-bit and 8-bit intervals). Because
+ of the way the mapping functions work, it is unlikely that an
+ implementation that fulfills the first criterion fails to fulfill the
+ two others.
3.6. Coding Coefficients Generation Function
The coding coefficients, used during the encoding process, are
generated at the RLC encoder by the generate_coding_coefficients()
function each time a new repair symbol needs to be produced. The
fraction of coefficients that are non zero (i.e., the density) is
controlled by the DT (Density Threshold) parameter. DT has values
between 0 (the minimum value) and 15 (the maximum value), and the
average probability of having a non zero coefficient equals (DT + 1)
@@ -1219,25 +1219,25 @@
o XXXX refers to the Sliding Window Random Linear Codes (RLC) over
GF(2^^8) FEC Scheme for Arbitrary Packet Flows, as defined in
Section 4 of this document.
11. Acknowledgments
The authors would like to thank the three TSVWG chairs, Wesley Eddy,
our shepherd, David Black and Gorry Fairhurst, as well as Spencer
Dawkins, our responsible AD, and all those who provided comments,
namely (alphabetical order) Alan DeKok, Jonathan Detchart, Russ
- Housley, Emmanuel Lochin, and Marie-Jose Montpetit. Last but not
- least, the authors are really grateful to the IESG members, in
- particular Benjamin Kaduk, Mirja Kuhlewind, Eric Rescorla, and Adam
- Roach for their highly valuable feedbacks that greatly contributed to
- improve this specification.
+ Housley, Emmanuel Lochin, Marie-Jose Montpetit, and Greg Skinner.
+ Last but not least, the authors are really grateful to the IESG
+ members, in particular Benjamin Kaduk, Mirja Kuhlewind, Eric
+ Rescorla, and Adam Roach for their highly valuable feedbacks that
+ greatly contributed to improve this specification.
12. References
12.1. Normative References
[fecframe-ext]
Roca, V. and A. Begen, "Forward Error Correction (FEC)
Framework Extension to Sliding Window Codes", Transport
Area Working Group (TSVWG) draft-ietf-tsvwg-fecframe-ext
(Work in Progress), January 2019,
@@ -1258,21 +1258,21 @@
Forward Error Correction (FEC) Framework", RFC 6364,
DOI 10.17487/RFC6364, October 2011,
```.
[RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC
2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174,
May 2017, .
[tinymt32]
Saito, M., Matsumoto, M., Roca, V., and E. Baccelli,
- "TinyMT32 PRNG">TinyMT32 Pseudo Random Number Generator",
+ "TinyMT32 Pseudo Random Number Generator (PRNG)",
Transport Area Working Group (TSVWG) draft-roca-tsvwg-
tinymt32 (Work in Progress), February 2019,
.
12.2. Informative References
[PGM13] Plank, J., Greenan, K., and E. Miller, "A Complete
Treatment of Software Implementations of Finite Field
Arithmetic for Erasure Coding Applications", University of
Tennessee Technical Report UT-CS-13-717,
@@ -1328,43 +1328,43 @@
Case Study", 13th IEEE International Conference on
Wireless and Mobile Computing, Networking and
Communications (WiMob17), October
2017 https://hal.inria.fr/hal-01571609v1/en/, October
2017, .
Appendix A. TinyMT32 Validation Criteria (Normative)
PRNG determinism, for a given seed, is a requirement. Consequently,
in order to validate an implementation of the TinyMT32 PRNG, the
- following criterias MUST be met.
+ following criteria MUST be met.
- The first criteria focusses on the tinymt32_rand256(), where the
+ The first criterion focusses on the tinymt32_rand256(), where the
32-bit integer of the core TinyMT32 PRNG is scaled down to an 8-bit
integer. Using a seed value of 1, the first 50 values returned by:
tinymt32_rand256() as 8-bit unsigned integers MUST be equal to values
provided in Figure 9.
37 225 177 176 21
246 54 139 168 237
211 187 62 190 104
135 210 99 176 11
207 35 40 113 179
214 254 101 212 211
226 41 234 232 203
29 194 211 112 107
217 104 197 135 23
89 210 252 109 166
Figure 9: First 50 decimal values returned by tinymt32_rand256() as
8-bit unsigned integers, with a seed value of 1.
- The second criteria focusses on the tinymt32_rand16(), where the
+ The second criterion focusses on the tinymt32_rand16(), where the
32-bit integer of the core TinyMT32 PRNG is scaled down to a 4-bit
integer. Using a seed value of 1, the first 50 values returned by:
tinymt32_rand16() as 4-bit unsigned integers MUST be equal to values
provided in Figure 10.
5 1 1 0 5
6 6 11 8 13
3 11 14 14 8
7 2 3 0 11
15 3 8 1 3
@@ -1378,22 +1378,22 @@
4-bit unsigned integers, with a seed value of 1.
Appendix B. Assessing the PRNG Adequacy (Informational)
This annex discusses the adequacy of the TinyMT32 PRNG and the
tinymt32_rand16() and tinymt32_rand256() functions, to the RLC FEC
Schemes. The goal is to assess the adequacy of these two functions
in producing coding coefficients that are sufficiently different from
one another, across various repair symbols with repair key values in
sequence (we can expect this approach to be commonly used by
- implementers Section 6.1). This section is purely informational and
- does not claim to be a solid evaluation.
+ implementers, see Section 6.1). This section is purely informational
+ and does not claim to be a solid evaluation.
The two RLC FEC Schemes use the PRNG to produce pseudo-random coding
coefficients (Section 3.6), each time a new repair symbol is needed.
A different repair key is used for each repair symbol, usually by
incrementing the repair key value (Section 6.1). For each repair
symbol, a limited number of pseudo-random numbers is needed,
depending on the DT and encoding window size (Section 3.6), using
either tinymt32_rand16() or tinymt32_rand256(). Therefore we are
more interested in the randomness of small sequences of random
numbers mapped to 4-bit or 8-bit integers, than in the randomness of
@@ -1426,22 +1426,22 @@
Figure 11: tinymt32_rand16(): occurrence statistics across a huge
number (1,000,000,000) of small sequences (20 pseudo-random numbers
per sequence), with 0 as the first PRNG seed.
The results (Figure 11) show that all possible values are almost
equally represented, or said differently, that the tinymt32_rand16()
output converges to a uniform distribution where each of the 16
possible value would appear exactly 1 / 16 * 100 = 6.25% of times.
Other types of biases may exist that may be visible with smaller
- tests (e.g., to evaluation the convergence speed to a uniform
- distribution). We therefore perform 200 tests, each of them
+ tests, for instance to evaluate the convergence speed to a uniform
+ distribution. We therefore perform 200 tests, each of them
consisting in producing 200 sequences, keeping only the first value
of each sequence. We use non overlapping repair keys for each
sequence, starting with value 0 and increasing it after each use.
value min occurrences max occurrences average occurrences
0 4 21 6.3675
1 4 22 6.0200
2 4 20 6.3125
3 5 23 6.1775
4 5 24 6.1000