О реализациях булевых функций асимптотически оптимальными по надёжности схемами
В. В. Чугунова Пензенский государственный университет
Аннотация:
В работе решены две задачи.
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.
Ключевые слова:
булевы функции, асимптотически оптимальные по надежности схемы.
УДК:
519.718 Статья поступила: 19.02.2008
Переработанный вариант: 14.07.2008