Выборка из выходной последовательности

Рассмотрим задач)' классификации функциональной схемы по вероятностям выходных s-грамм в выборке с фиксированным шагом п — /?, 0 < h < п. При этом выходная последовательность у_г, г — 1,2,… получается из неизвестной случайной входной последовательности Xi, г = 1,2,… с помощью неизвестной (ключевой) функции усложнения /: F? -" F2 по следующему правилу:

Отметим, что два любых соседних знака выхода как функции от входа имеют ровно h общих переменных.

Введем следующие обозначения. Пусть / = f (x 1,… , х*), t 5= п, — произвольная функция, отображающая F2 в F2. Под матрицей Ah{f) понимаем квадратную матрицу размера 2^h х 2^h, которая задается следующим образом:

где

при этом суммирование ведется по множеству W всех векторов X — (х, Х2,? ??, Xt), у которых.

Полагаем а_а^ = 0 при пустом множестве W.

Для заданной функции / от п аргументов и натуральном т через f[m} обозначим следующую функцию от т+п— 1 аргументов:

Если / ~ ip, то при любых га выполнено равенство.

при этом.

Кроме того, эти соотношения являются необходимыми и достаточными для статистической неотличимости при h ^ п/2, а также для статистической неотличимости относительно распределения вероятностей суммы т подряд идущих знаков выходной гаммы 71 + 72 + • • • + 7 т.

Теорема 6.8. Для функций /ь /2: F₂ ->? ^2 равенства (6.10) выполняются при любых натуральных т тогда и только тогда, когда они выполняются для т = 1,2,d -М2, где ф — степень минимального многочлена матрицы Ah (fi), г = 1,2.

Доказательство. Обозначим через 9i (z) = с*, о + Ci_tz Н——-1;

Cidi Ф 0, г = 1,2, минимальный многочлен матрицы Ah (fi). Учитывая равенства (6.10), получаем соотношение.

Отсюда следует, что при любом фиксированном г Е {1,2} последовательность А (/г[1]), А (/г[2]),… является линейной рекуррентной последовательностью с аннулирующим многочленом 0i (z). Значит, многочлен 0(z) = O (z)02(z) является аннулирующим для каждой из этих последовательностей, что и доказывает теорему. ?

Следствие 1. Для функций /1./2: Щ —> F2 равенства (6.10) выполняются при любых натуральных т тогда и только тогда, когда они выполняются для т = 1,2,…, 2 h + 1.

Справедливость следствия вытекает из теоремы 6.8 с учетом того, что степень минимального многочлена матрицы Ah (fi) не превосходит величины 2 .

Утверждение 6.15. Если 2h ^ п, то функции /ь/2: F? -> F₂ обладают равными вероятностями т-грамм в выборке с шагом n—h при любых т = 1,2,… тогда и только тогда, когда они имеют равные вероятности т-грамм при т = 1,2,…, min{diМ2,2^Л+1 — 1}, где ф — степень минимального многочлена матрицы Л/*(/*), г = 1,2.

По аналогии с теоремой 6.8 доказывается следующее утверждение.

Теорема 6.9. Пусть d — степень минимального многочлена матрицы Ah{f)_y f : —)• F2. Если A (/[s]) = 0 для s = 1,2, …, d, то

A (/[,]) = 0 при всех натуральных s.

Следствие 1. Если A (/[.s]) = 0 при s = 1,2,…, 2^/l, то A (/[.s]) = 0 при всех натуральных s.

Замечание. Теорема 6.9 и следствие к ней касаются важного случая равновероятности функций f[s], s = 1,2…, т. е равновероятности суммы последовательных знаков в выборке (с шагом п — h) из выходной последовательности фильтрующей схемы. При этом отметим, что в случае 2h < п равновероятность функций f[s], s = 1,2,…, равносильна равновероятности выходных m-грамм в соответствующей выборке из выходной последовательности фильтрующей схемы.

Теорема 6.10. Пусть Mi, М2,…, — разбиение булевых функций

от п переменных на классы статистической эквивалентности относительно вероятностей т-грамм в выборке с шагом п — 1г, 2h ^ п. Тогда для числа классов справедлива оценка сверху

Доказательство. С учетом (6.10) число классов не превосходит числа различных матриц.

Число элементов в матрице равно 2^21г, причем для любого из них справедлива оценка.

Осталось заметить, что для любых целых a_Q^ в указанных пределах найдется функция /, для которой АД/) — (а_п, Д. ?

Теорема 6.11. В условиях теоремы 6.10 для среднего значения мощности классов эквивалентности справедлива оценка:

где и: — общее число рассматриваемых функций, т = (2″ ^2h + 1)^22,‘.

Доказательство. Пусть M_r, г = 1.2… А' - классы неотличимости, на которые распадается рассматриваемое множество булевых функций от п переменных. При aj — Mj, bj = 1, j = 1,2,…, k, из неравенства Коши-Буняковского

получаем:

С учетом теоремы 6.11 отсюда и получаем требуемую оценку.

Замечание. Соотношения (6.10) сводят задачу описания классов неотличимых функций /: Fg —> F2 (по вероятностям ттг-грамм в выборке с фиксированным шагом п — h, 2h ^ п) к классификации множества соответствующих матриц Ah (f). При этом в случае п = 2h мощность множества А = {Л/,(/)|/: Fg —> F2} совпадает с числом всех функций /, и оценки теорем 6.10 — 6.11 становятся тривиальными. Вместе с тем, при п > 2h мощность множества А может быть существенно меньше числа рассматриваемых функций /.