Том 15, номер 6, 2008 г., Стр. 63-89

УДК 519.718
В. В. Чугунова
О реализациях булевых функций асимптотически оптимальными по надёжности схемами

Аннотация:
В работе решены две задачи.
1. Показано, что если к каждому из неприводимых полных базисов, содержащих функции, зависящие не более чем от двух переменных, добавить ровно одну неконстантную и не конгруэнтную базисным булеву функцию $\varphi(x_1,x_2)$, зависящую не более чем от двух переменных, то в большинстве полученных базисов оценка ненадёжности схем из функциональных элементов, подверженных инверсным неисправностям на входах элементов, понизится для почти всех функций.
2. Показано, что если к каждому из неприводимых полных базисов, содержащих функции, зависящие не более чем от двух переменных, добавить $k (k\ge3)$ неконстантных и не конгруэнтных базисным булевых функции, зависящих не более чем от двух переменных, то во всех полученных базисах оценка ненадёжности схем из функциональных элементов, подверженных инверсным неисправностям на входах элементов, асимптотически (при $\varepsilon\to0$) равна $2\varepsilon$ (т.е. становится тривиальной) для всех функций $f(x_1,x_2,\dots,x_n)$, исключая константы 0, 1 и функции $x_i,\ \overline x_i$, где $\varepsilon$ – вероятность ошибки на каждом входе функционального элемента, $i=\overline{1,n}$.
Показано также, что схемы, построенные при решении двух перечисленных задач, являются асимптотически оптимальными по надёжности при $\varepsilon\to0$.
Илл. 3, табл. 6, библиогр. 5.

Ключевые слова: булевы функции, асимптотически оптимальные по надежности схемы.

Чугунова Варвара Валерьевна ¹
1. Пензенский государственный университет,
ул. Красная, 40, 440026 Пенза, Россия
е-mail: burchug@sura.ru

Статья поступила 19 февраля 2008 г.
Исправленный вариант — 14 июля 2008 г.