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

Доклады Томского государственного университета систем управления и радиоэлектроники. 2014. № 2(32). С. 33–40.

Рожков М. И.

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

Bf,L:(F2)n®(F2)n, Вf,L(x)=(f(x),f(d(x)),…,f(dn-1(x)), xÎ(F2)n,

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

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