|
|
Дискретный анализ и исследование операций, 2008, том 15, выпуск 6, страницы 63–89
(Mi da558)
|
|
|
|
О реализациях булевых функций асимптотически оптимальными по надёжности схемами
В. В. Чугунова Пензенский государственный университет
Аннотация:
В работе решены две задачи.
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.
Ключевые слова:
булевы функции, асимптотически оптимальные по надежности схемы.
Статья поступила: 19.02.2008 Переработанный вариант: 14.07.2008
Образец цитирования:
В. В. Чугунова, “О реализациях булевых функций асимптотически оптимальными по надёжности схемами”, Дискретн. анализ и исслед. опер., 15:6 (2008), 63–89
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/da558 https://www.mathnet.ru/rus/da/v15/i6/p63
|
|