При условии, что $х$ представляет собой последовательность $л$ биты и $0 \le n < l$, позволять $R(x, n)$ обозначают результат левого побитового поворота $х$ к $n$ биты.Например, если $х = 0100110001110000$, тогда $$\begin{массив}{л}
R (х, 0) = {\ rm {0100110001110000}}, \
R(x,1) = {\rm{1001100011100000}},\
R(x,2) = {\rm{0011000111000001}},\
\ldots\
R(x,15) = {\rm{0010011000111000}}.
\end{массив}$$
Позволять $A\oплюс B$ обозначают результат операции XOR для двух последовательностей $л$ биты. Например, $$0100110001110000 \oplus 1010010001000010 = 1110100000110010.$$
Позволять $Ч(х)$ обозначают количество ненулевых битов в $х$ (т.е. Вес Хэмминга из $х$).
При условии, что $х$ и $у$ это две битовые строки одинаковой длины $л$, позволять $f(х, у)$ обозначим минимальный элемент (наименьшее число) в кортеже $$\begin{массив}{л}
(Н(х\oплюс у),\
Н(х\оплюс R(у,1)),\
Н(х\оплюс R(у,2)),\
\ldots\
H(x \oplus R(y,l - 1))).
\end{массив}$$
Предположим, что у нас есть TRNG, который генерирует последовательности случайных битов. Сгенерировать последовательность $L = k \times l$ биты. Разделите эту последовательность на $к$ слов (поэтому длина каждого слова равна $л$): $w_0, w_1, \ldots, w_{k-1}$. Затем вычислите следующий кортеж $Т$ числа:
$$\begin{массив}{л}
(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{массив}$$
Другими словами, для Любые пара слов $(w_i, w_j)$ такой, что $i \neqj$, вычислить соответствующий $f({w_i},{w_j})$.
Вопрос 1: дано $к$ и $л$, как рассчитать ожидал стоимость минимальный количество $M_T$ в $Т$?
Вопрос 2: дано $к$ и $л$, как рассчитать ожидал стоимость средний количество $A_T$ в $Т$? Здесь число $A_T$ вычисляется следующим образом: суммируйте все элементы $Т$, затем разделите сумму на общее количество элементов в $Т$.
ожидал число здесь подразумевает число с максимальной вероятностью.Например, ожидаемое количество нулевых битов в последовательности $л$ случайные биты $1/2$.
