Алгоритм вычисления понижающих пар для булевых функций без запрета от четырех переменных

Промышленные АСУ и контроллеры. 2015. № 6. С. 48–54.

Рожков М. И., Хрусталев С. С.

Понижающие пары (натуральных чисел (h,t), h>t) для функций без запрета f=f(x1,x2,…,xk)  изучались ранее в связи с построением биективных отображений 

Bf,L:(F2)n®(F2)n,

набор координатных функций которых задается преобразованием регистра сдвига длины n с функцией обратной связи L, существенно зависящей от ограниченного числа s(1) начальных и s(2) конечных аргументов, и  нелинейной функцией съема f=f(x1,x2,…,xk)  от k аргументов (k<<n). Наличие у функции f понижающей пары (h,t) сводит исходную задачу проверки биективности отображения Вf,L при больших значениях длины регистра n к проверке биективности соответствующих отображений применительно к регистрам сдвига ограниченной длины

n=n0Î{t+s(1)+s(2)-1,t+s(1)+s(2),…,h+s(1)+s(2)-2},

что позволяет эффективно использовать для ее решения вычислительную технику. Ранее понижающие пары были найдены для большинства булевых функций без запрета от четырех переменных. При этом для функций нелинейных по крайним переменным использовались алгоритмы, сложность реализации которых оценивается величиной O(2h+t),   позволяющие эффективно вычислять пары (h,t) при (h+t) )»40. При (h+t) )> 40 вычислительная сложность указанных алгоритмов становится неприемлемо высокой.  В настоящей работе исследован  новый алгоритм, позволивший найти понижающие пары для всех функций без запрета от четырех переменных.

Ключевые слова: ортогональные системы функций, регистр сдвига, orthogonal system of Boolean functions, feedback shift register, filter generator, restrictive multitude, фильтрующий генератор, lowering pairs, понижающая пара