Промышленные АСУ и контроллеры Аннотация к статье << Назад Алгоритм вычисления понижающих пар для булевых функций без запрета от четырех переменных М.И. Рожков, С.С. Хрусталев Понижающие пары (натуральных чисел (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< жающей пары (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 вычислительная сложность указанных алгоритмов становится неприемлемо высокой. В настоящей работе исследован новый алгоритм, позво- ливший найти понижающие пары для всех функций без запрета от четырех переменных. Ключевые слова: ортогональные системы функций; регистр сдвига; фильтрующий генератор; понижающая пара. Контактная информация: E-mail: rozhkov.m.i@yandex.ru, E-mail: sergeixr@mail.ru Стр. 48-54.