Том 7, серия 1, номер 3, 2000 г., Стр. 17-44
УДК 519.71+519.218.82
А. Д. Коршунов, И. Шмулевич
Число специальных монотонных булевых функций и статистические свойства стековых фильтров
Аннотация:
Изучаются три множества специальных монотонных булевых функций от$n$ переменных: одно множество при четном$n$ и два множества при нечетном$n$ . Эти множества характеризуются тем, что нижние единицы любой функции из одного множества располагаются на трех фиксированных соседних слоях$n$ -мерного единичного куба и удовлетворяют некоторым дополнительным ограничениям. Находятся асимптотики для числа таких функций$f$ из каждого множества, что при фиксированных трех слоях функция$f$ имеет заданное число нижних единиц в нижнем слое, заданное число верхних нулей в верхнем слое и равна 1 на заданном числе наборов среднего слоя. Показано, что при любом$n\to\infty$ число всех монотонных булевых функций от$n$ переменных асимптотически совпадает с числом специальных функций от$n$ переменных. Полученные асимптотики используются для характеризации статистических свойств стековых фильтров.
Библиогр. 15.
Коршунов А. Д. 1
Шмулевич И. 2
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
2. Tampere International Center for Signal Processing, Tampere Univ. of Technology,
P. O. Box 553, 33101 Tampere, Finland
е-mail: korshun@math.nsc.ru, ilya@cs.tut.fi
Статья поступила 17 мая 2000 г.
