Asumand $x$ este o succesiune de $l$ biți și $0 \le n < l$, lăsa $R(x, n)$ denotă rezultatul rotației pe biți stânga a $x$ de $n$ biți.De exemplu, dacă $x = 0100110001110000$, atunci $$\begin{matrice}{l}
R(x,0) = {\rm{0100110001110000}},\
R(x,1) = {\rm{1001100011100000}},\
R(x,2) = {\rm{0011000111000001}},\
\ldots \
R(x,15) = {\rm{0010011000111000}}.
\end{matrice}$$
Lăsa $A \oplus B$ notează rezultatul operației XOR pentru două secvențe de $l$ biți. De exemplu, $$0100110001110000 \oplus 1010010001000010 = 1110100000110010.$$
Lăsa $H(x)$ indică numărul de biți diferit de zero în $x$ (adică, Greutate Hamming de $x$).
Asumand $x$ și $y$ sunt două șiruri de biți de aceeași lungime $l$, lăsa $f(x, y)$ notează elementul minim (cel mai mic număr) din tuplu $$\begin{matrice}{l}
(H(x \oplus y),\
H(x \oplus R(y,1)),\
H(x \oplus R(y,2)),\
\ldots \
H(x \oplus R(y,l - 1))).
\end{matrice}$$
Să presupunem că avem un TRNG care generează secvențe de biți aleatori. Generați o secvență de $L = k \times l$ biți. Împărțiți această secvență în $k$ cuvinte (deci lungimea fiecărui cuvânt este $l$): $w_0, w_1, \ldots, w_{k-1}$. Apoi calculați următorul tuplu $T$ de numere:
$$\begin{matrice}{l}
(f({w_0},{w_1}),\
f({w_0},{w_2}),\
\ldots \
f({w_0},{w_{k - 1}}),\
f({w_1},{w_2}),\
f({w_1},{w_3}),\
\ldots \
f({w_1},{w_{k - 1}}),\
f({w_2},{w_3}),\
\ldots \
f({w_{k - 2}},{w_{k - 1}})).
\end{matrice}$$
Cu alte cuvinte, pentru orice pereche de cuvinte $(w_i, w_j)$ astfel încât $i \neq j$, calculați corespunzătoare $f({w_i},{w_j})$.
Întrebarea 1: dat $k$ și $l$, cum se calculează așteptat valoarea a minim număr $M_T$ în $T$?
Întrebarea 2: dat $k$ și $l$, cum se calculează așteptat valoarea a in medie număr $A_T$ în $T$? Iată numărul $A_T$ se calculează astfel: se însumează toate elementele din $T$, apoi împărțiți suma la numărul total de elemente în $T$.
The așteptat număr aici implică numărul cu probabilitatea maximă.De exemplu, numărul așteptat de zero biți într-o secvență de $l$ biți aleatori este $l/2$.
