|
Известия высших учебных заведений. Математика, 2010, номер 5, страницы 79–82
(Mi ivm6738)
|
|
|
|
Эта публикация цитируется в 10 научных статьях (всего в 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$.
Ключевые слова:
ненадежные функциональные элементы, асимптотически оптимальные по надежности схемы, инверсные неисправности на выходах элементов, синтез схем из ненадежных элементов.
Поступила: 10.11.2009
Образец цитирования:
М. А. Алехина, А. В. Васин, “Достаточные условия реализации булевых функций асимптотически оптимальными схемами с ненадежностью $2\varepsilon$”, Изв. вузов. Матем., 2010, № 5, 79–82; Russian Math. (Iz. VUZ), 54:5 (2010), 68–70
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/ivm6738 https://www.mathnet.ru/rus/ivm/y2010/i5/p79
|
Статистика просмотров: |
Страница аннотации: | 399 | PDF полного текста: | 60 | Список литературы: | 54 | Первая страница: | 4 |
|