Эта публикация цитируется в
10 статьях
Краткие сообщения
Достаточные условия реализации булевых функций асимптотически оптимальными схемами с ненадежностью $2\varepsilon$
М. А. Алехина,
А. В. Васин Кафедра дискретной математики, Пензенский государственный университет, г. Пенза
Аннотация:
Рассматривается реализация булевых функций схемами из ненадежных функциональных элементов в полном конечном базисе
$B$. Предполагается, что все элементы схемы независимо друг от друга с вероятностью
$\varepsilon$ (
$\varepsilon\in(0;1/2)$) подвержены инверсным неисправностям на выходах.
Найдены булевы функции
$\varphi(x_1,x_2,x_3)$, наличие хотя бы одной из которых в рассматриваемом базисе
$B$ достаточно для реализации всех булевых функций схемами, функционирующими с ненадежностью не больше
$2\varepsilon+144\varepsilon^2$ при
$\varepsilon\le1/960$. Кроме того, если
$B\subset B_3\setminus G$ (
$B_3$ – множество всех булевых функций, зависящих от трех переменных
$x_1$,
$x_2$,
$x_3$,
$G$ – множество булевых функций, каждая из которых конгруэнтна либо $x_1^{\sigma_1}x_2^{\sigma_2}\vee x_1^{\sigma_1}x_3^{\sigma_3}\vee x_2^{\sigma_2}x_3^{\sigma_3}$, либо $x_1^{\sigma_1}x_2^{\sigma_2}\oplus x_3^{\sigma_3}$, либо $x_1^{\sigma _1}x_2^{\overline\sigma_2}\vee x_2^{\sigma _2}x_3^{\sigma_3}$ (
$\sigma_1,\sigma_2,\sigma_3\in\{0,1\}$)), то наличие хотя бы одной из функций
$\varphi(x_1,x_2,x_3)$ достаточно для реализации почти всех булевых функций асимптотически оптимальными по надежности схемами, функционирующими с ненадежностью
$2\varepsilon$ при
$\varepsilon\to0$.
Ключевые слова:
ненадежные функциональные элементы, асимптотически оптимальные по надежности схемы, инверсные неисправности на выходах элементов, синтез схем из ненадежных элементов.
УДК:
519.718 Поступила: 10.11.2009