Giả sử rằng $x$ là một dãy $l$ bit và $0 \le n < l$, để cho $R(x, n)$ biểu thị kết quả của phép quay bit trái của $x$ qua $n$ chút ít.Ví dụ, nếu $x = 0100110001110000$, sau đó $$\begin{array}{l}
R(x,0) = {\rm{0100110001110000}},\
R(x,1) = {\rm{1001100011100000}},\
R(x,2) = {\rm{0011000111000001}},\
\ldots \
R(x,15) = {\rm{0010011000111000}}.
\end{mảng}$$
Để cho $A \oplus B$ biểu thị kết quả của phép toán XOR cho hai chuỗi $l$ chút ít. Ví dụ, $$0100110001110000 \oplus 1010010001000010 = 1110100000110010.$$
Để cho $H(x)$ biểu thị số lượng bit khác không trong $x$ (tức là trọng lượng hamming của $x$).
Giả sử rằng $x$ và $y$ là hai chuỗi bit có cùng độ dài $l$, để cho $f(x, y)$ biểu thị phần tử tối thiểu (số nhỏ nhất) trong bộ dữ liệu $$\begin{array}{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{mảng}$$
Giả sử rằng chúng ta có một TRNG tạo ra các chuỗi bit ngẫu nhiên. Tạo ra một chuỗi các $L = k \times l$ chút ít. Chia chuỗi này thành $k$ từ (vì vậy độ dài của mỗi từ là $l$): $w_0, w_1, \ldots, w_{k-1}$. Sau đó tính toán bộ dữ liệu sau $T$ số:
$$\begin{array}{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{mảng}$$
Nói cách khác, đối với không tí nào cặp từ $(w_i, w_j)$ như vậy mà $i \neq j$, tính toán tương ứng $f({w_i},{w_j})$.
Câu 1: đã cho $k$ và $l$, cách tính hy vọng giá trị của tối thiểu con số $M_T$ Trong $T$?
Câu 2: đã cho $k$ và $l$, cách tính hy vọng giá trị của trung bình con số $A_T$ Trong $T$? Đây là số $A_T$ được tính như sau: tính tổng tất cả các phần tử của $T$, sau đó chia tổng cho tổng số phần tử trong $T$.
Các hy vọng số ở đây hàm ý số có xác suất lớn nhất.Ví dụ, số bit 0 dự kiến trong một chuỗi $l$ bit ngẫu nhiên là $l/2$.
