RUS  ENG
Полная версия
ЖУРНАЛЫ // Известия высших учебных заведений. Математика // Архив

Изв. вузов. Матем., 2010, номер 5, страницы 79–82 (Mi ivm6738)

Эта публикация цитируется в 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


 Англоязычная версия: Russian Mathematics (Izvestiya VUZ. Matematika), 2010, 54:5, 68–70

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


© МИАН, 2024