Том 12, серия 1, номер 2, 2005 г., Стр. 3-11
УДК 519.718
М. А. Алехина
О надежности и сложности схем в базисе ${x | y}$ при инверсных неисправностях элементов
Аннотация:
Показано, что в базисе$\{x|y\}$ при инверсных неисправностях элементов схем почти все булевы функции можно реализовать асимптотически наилучшими по надежности схемами, функционирующими с ненадежностью, асимптотически равной$3\varepsilon$ ($\varepsilon$ – вероятность неисправности элемента) при$3\varepsilon\to 0$ , причем сложность этих схем по порядку равна сложности минимальных схем, построенных только из надежных элементов.
Алехина М. А. 1
1. Пензенский государственный университет, каф. математики и математического моделирования,
ул. Красная, д. 40, 440026 Пенза, Россия
е-mail: ama@sura.ru
Статья поступила 13 сентября 2004 г.
Исправленный вариант — 11 января 2005 г.
