RUS  ENG
Полная версия
ЖУРНАЛЫ // Дискретный анализ и исследование операций // Архив

Дискретн. анализ и исслед. опер., 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.

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

УДК: 519.718

Статья поступила: 19.02.2008
Переработанный вариант: 14.07.2008



Реферативные базы данных:


© МИАН, 2024