EN|RU

Том 22, номер 1, 2015 г., Стр. 5-18.

УДК 519.718
А. В. Васин
О широком классе базисов с коэффициентом ненадёжности, равным единице

Аннотация:
Рассматривается реализация булевых функций схемами из ненадёжных функциональных элементов в полном базисе B. Предполагается, что базисные элементы подвержены инверсным неисправностям на выходах и переходят в неисправные состояния независимо друг от друга с вероятностью ε (0, 1/2). Найдено множество функций G, и доказано, что коэффициент ненадёжности базиса B, содержащего функции множества G, равен 1.
Ил. 3, библиогр. 13.

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

DOI: 10.17377/daio.2015.22.435

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

Статья поступила 27 декабря 2013 г.
Исправленный вариант — 24 апреля 2014 г.

Литература

[1] Аксёнов С. И. О надёжности схем над произвольной полной системой функций при инверсных неисправностях на выходах элементов // Изв. вузов. Поволж. регион. Естеств. науки. 2005. №6. C. 42–55.

[2] Алексеев В. Б. Лекции по дискретной математике. М.: Изд. отдел фак-та ВМиК МГУ, 2004. 76 c.

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

[4] Алёхина М. А., Аксёнов С. И., Васин А. В. О функциях и схемах, применяемых для повышения надёжности схем // Изв. вузов. Поволж. регион. Физ.-мат. науки. 2008. №3. C. 30–38.

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


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

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


[8] Лупанов О. Б. Асимптотические оценки сложности управляющих систем. М.: Изд-во МГУ, 1984. 138 c.

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


[10] Ортюков С. И. Об избыточности реализации булевых функций схемами из ненадёжных элементов // Тр. семинара по дискретной математике и её приложениям (Москва, 27–29 января 1987 г.). М.: Изд-во МГУ, 1989. С. 166–168.

[11] Чугунова В. В. Синтез асимптотически оптимальных по надёжности схем при инверсных неисправностях на входах элементов // Дис. . . . канд. физ.-мат. наук: 01.01.09. Пенза, 2007. 110 c.

[12] Яблонский С. Асимптотически наилучший метод синтеза надежных схем из ненадежных элементов // Banach Center Publ. 1982. Vol. 7. P. 11–19.


[13] Uhlig D. Reliable networks from unreliable gates with almost minimal complexity // Fundamentals of Computation Theory. Proc. Int. Conf. FCT’87 (Kazan, June, 1987). Berlin: Springer-Verl., 1987. P. 462–469. (Lect. Notes Comput. Sci.; Vol. 278).

 © Институт математики им. С. Л. Соболева, 2015