journal.isu.ru

Начальная страница

Конечная страница

УДК

Раздел
     

Файл
Скачать Изменить файл

Название RU

Авторы RU

Аннотация RU
<p>В работе исследуется сложность представления булевых функций в классе полиномиальных нормальных форм, которая определяется по числу слагаемых в минимальном полиноме. Рассматривается класс булевых функций, которые имеют наибольшую сложность среди всех функций от 6 переменных и менее. Получено точное значение сложности функций этого класса, зависящих от 7 переменных.</p>

Ключевые слова RU

Литература RU
1. Балюк А. С. Нижняя оценка сложности одной последовательности булевых функций в классе полиномиальных нормальных форм / А. С. Балюк // Синтез и сложность управляющих систем : материалы XII междунар. шк.-семинара. – М. : Изд-во ЦПИ при мех.-мат. фак. МГУ, 2001. – Ч. 1. – С. 18–21. 2. Винокуров С. Ф. Перечисление операторных классов булевых функций / С. Ф. Винокуров, А. С. Казимиров// Изв. Иркут. гос. ун-та. Сер.: Математика. – 2009. – Т. 2, № 2. – С. 40–55. 3. Кириченко К. Д. Верхняя оценка сложности полиномиальных нормальных форм булевых функций / К. Д. Кириченко // Синтез и сложность управляющих систем : материалы XII междунар. шк.-семинара. – М. : Изд-во ЦПИ при мех.-мат. фак. МГУ, 2001. – Ч. 1. – С. 115–120. 4. Рябец Л. В. Нахождение минимальных полиномов булевых функций с использованием специальной операторной формы / Л. В. Рябец // Технологии Microsoft в теории и практике программирования. – Новосибирск, 2006. – С. 215–217. 5. Even S. On minimal modulo 2 sums of products for switching function / S. Even, I. Kohavi, A. Paz // IEEE Trans. Elect. Comput. – 1967. – P. 671–674. 6. Gaidukov A. Algorithm to derive minimum ESOPs for 6-variable functions / A. Gaidukov // Proceedings of the 5th International Workshop on Boolean Problems 2002, Freiberg, Germany, Sept. 19–20, 2002. – P. 141–148. 7. Koda N. An Upper Bound on the Number of Products in Minimum ESOPs / N. Koda, T. Sasao // Workshop in Application of the Reed-Muller Expansion Apllication in Circuit Design. – Japan, 1995. – P. 94–101.

Название EN

Авторы EN

Аннотация EN
<p>This paper concerns complexity of polynomial forms (exor-sum-of-pro-ducts) representing Boolean functions. Complexity is defined as a minimal number of summands in exor-sum-of-products for a given function. A class of Boolean functions being the most complex among Boolean functions having 6 or less arguments is considered. The exact complexity for functions of described class having 7 agruments is obtained.</p>

Ключевые слова EN

Литература EN