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

Автори:А.Н. Алексейчук, О.Н. Кулинич, В.В. Сокур, С.Н. Конюшок

Канонические поляризованные полиномы (КПП) образуют специальный класс полиномиальных форм, интерес к исследованию которых обусловлен как традиционными задачами анализа сложности и классификации булевых функций (БФ) [1 – 4], так и вопросами, связанными с их реализацией на основе современных интегральных микросхем (программируемых логических матриц (ПЛМ) типа "и-исключающее или" [5]). Известно [1], что основу логического проектирования стандартных ПЛМ составляют традиционные алгоритмы минимизации дизъюнктивных нормальных форм (ДНФ) булевых функций. С другой стороны, многие функции, имеющие большую сложность в классе ДНФ, могут быть достаточно просто представлены в полиномиальном виде. Поэтому ПЛМ, содержащие в своем составе логические элементы "сложение по модулю 2", в ряде случаев обладают определенными преимуществами [5].

Постоению алгоритмов минимизации и анализу сложности БФ в классе КПП посвящены работы [5 – 9] и другие. В настоящей статье получены новые границы функции Шеннона для сложности представления каноническими поляризованными полиномами n-местных БФ, имеющих степень нелинейности не более r. Указанные границы уточняют результаты [6, 7] и могут быть непосредственно использованы при оценке сложности БФ, принадлежащих некоторым другим классам. Предложен рекурсивный алгоритм вычисления коэффициентов всех КПП булевой функции f по вектору Tf ее значений, вычислительная сложность которого совпадает со сложностью алгоритма, описанного в [8]. На основе результатов [9] получена нижняя оценка сложности оптимальной схемы вычисления КПП произвольной БФ f, заданной вектором значений Tf.

References
  1. Сэвидж Дж.Э. Сложность вычислений: Пер. с англ. – М.: Факториал, 1998. – 368 с.
  2. Ященко В.В. О критерии распространения булевых функций и бент-функциях // Проблемы передачи информации. – 1997. – Т. 33. – В. 1. – С. 75-86.
  3. Xiao G.Z., Massey J.L. A special characterization of correlation-immune combining functions // IEEE Trans. Inform. Theory. – 1988. – 34, № 3. – P. 569-571.
  4. Tsai C., Marek-Sadovska M. Boolean functions classification via fixed polarity Reed-Muller forms // IEEE Trans. on Comput. – 1997. – 46, № 2. – P. 173-186.
  5. Sasao T., Besslich P. On the complexity of mod-2 sum PLA’s // IEEE Trans. on Comput. – 1990. – 39, № 2. – P. 262-266.
  6. Перязев Н.А. Сложность булевых функций в классе полиномиальных поляризованных форм // Алгебра и логика. – 1995. – 34., № 3. – С. 323-326.
  7. Алексейчук А.Н. О сложности булевых функций в классе канонических поляризованных полиномов // Кибернетика и системный анализ. – 2000. –   № 3. – С. 179-183.
  8. Авгуль Л.В. Полиномиальное разложение булевых функций методом “тройного треугольника” // Автоматика и вычисл. техника. – 1996. – № 2. – С. 12-24.
  9. Алексейчук А.Н. О сложности вычисления значений частных производных булевых функций, реализованных полиномами Жегалкина // Кибернетика и системный анализ. – 2001. –   № 5. – С. 30-37.
  10. Бохман Д., Постхоф Х. Двоичные динамические системы: Пер. с нем. – М.: Энергоатомиздат, 1986. – 401 с.