Том 20, номер 6, 2013 г., Стр. 3-15

УДК 519.718
Васин А. В.
Асимптотически оптимальные по надёжности схемы в некоторых базисах

Аннотация:
Рассматривается реализация булевых функций схемами из ненадёжных элементов в полном базисе $B\subset B_3$ ($B_3$ – множество всех булевых функций, зависящих от переменных $x_1,x_2,x_3$). Предполагается, что все элементы схемы независимо друг от друга с вероятностью $\varepsilon\in(0,1/2)$ подвержены инверсным неисправностям на выходах. Найдены все базисы, в которых почти все булевы функции можно реализовать асимптотически оптимальными по надёжности схемами, функционирующими с ненадёжностью $3\varepsilon$ при $\varepsilon\to0$. Доказано, что других таких базисов $B\subset B_3$ нет.
Библиогр. 9.

Ключевые слова: ненадёжный функциональный элемент, асимптотически оптимальная по надёжности схема, инверсная неисправность на выходах элементов, синтез схемы из ненадёжных элементов.

Васин Алексей Валерьевич ¹
1. Пензенский гос. университет,
ул. Красная, 40, 440026 Пенза, Россия
е-mail: alvarvasin@mail.ru

Статья поступила 12 апреля 2010 г.
Исправленный вариант — 17 января 2013 г.

Литература

[1] Алёхина М. А. Синтез асимптотически оптимальных по надёжности схем из ненадёжных элементов. - Пенза: ИИЦ ПГУ, 2006. - 156 c.

[2] Алёхина М. А. О надёжности и сложности схем в базисе {x|y} при инверсных неисправностях элементов. // Дискрет. анализ и исслед. операций. Сер. 1. - 2005. - Том 12, № 2. - C. 3–11.

[3] Алёхина М. А., Васин А. В. О надёжности схем в базисах, содержащих функции не более чем трёх переменных // Уч. зап. Казан. гос. ун-та. Сер. Физ-мат. науки. - 2009. - Т. 151, № 2. - C. 25–35.

[4] Алёхина М. А., Васин А. В. Достаточные условия реализации булевых функций асимптотически оптимальными схемами с ненадёжностью 2ε // Изв. вузов. Математика. - 2010. - № 5. - C. 79–82.

[5] Алёхина М. А., Пичугина П. Г. О надёжности двойственных схем в полном конечном базисе // Мат. XVIII междунар. шк.–семинара «Синтез и сложность управляющих систем» (г. Пенза, 28 сентября–3 октября 2009 г.). - М.: Изд-во мех.-мат. фак-та МГУ, 2009. - С. 10–13.

[6] Васин А. В. О функциях специального вида // Тр. VIII междунар. конф. «Дискретные модели в теории управляющих систем» (Лесной городок, Моск. обл., 6–9 апреля 2009 г.). - М.: МАКС Пресс, 2009. - C. 43–47.

[7] Васин А. В. Необходимые и достаточные условия реализации булевых функций асимптотически оптимальными схемами с ненадёжностью 2ε // Мат. X междунар. семинара «Дискретная математика и её приложения» (Москва, 1–6 февраля 2010 г.). - М.: Изд-во мех.-мат. фак-та МГУ, 2010. - C. 94–97.

[8] Васин А. В. Об асимптотически оптимальных схемах в базисе $\{\&,\lnot\}$ при инверсных неисправностях на выходах элементов // Дискрет. анализ и исслед. операций. - 2009. - Т. 16, № 6. - C. 12–22.

[9] Нейман Дж. Автоматы. - М.: Изд-во иностр. лит., 1956. - С. 68–139.