Рассматривается реализация булевых функций схемами из ненадёжных функциональных элементов в полном конечном базисе. Предполагается, что все функциональные элементы независимо друг от друга с вероятностью ε ∈ (0, 1/2) переходят в неисправные состояния типа 0 на выходах элементов. Найдены и дополнены ранее известные условия на функции базиса, при выполнении которых почти любую булеву функцию можно реализовать асимптотически оптимальной по надёжности схемой, функционирующей с ненадёжностью, асимптотически равной ε при ε → 0 .
Скачать электронную версию публикации
Загружен, раз: 92
- Title Достаточные условия реализации булевых функций асимптотически оптимальными по надёжности схемами с тривиальной оценкой ненадёжности при неисправностях типа 0 на выходах элементов
- Headline Достаточные условия реализации булевых функций асимптотически оптимальными по надёжности схемами с тривиальной оценкой ненадёжности при неисправностях типа 0 на выходах элементов
- Publesher
Tomsk State University - Issue Прикладная дискретная математика 45
- Date:
- DOI 10.17223/20710410/45/5
Ключевые слова
схема, неисправности типа 0 на выходах элементов, ненадёжность, асимптотически оптимальная по надёжности схема, булева функция, circuit, faults of type 0 at the element outputs, unreliability, asymptotically optimal on reliability circuit, Boolean functionАвторы
Ссылки
Von Neumann J. Probabilistic logics and the synthesis of reliable organisms from unreliable components // Automata studies / eds. C. Shannon and J. McCarthy. Princeton University Press, 1956. P. 43-98
Добрушин Р. Л., Ортюков С. И. Верхняя оценка для избыточности самокорректирующихся схем из ненадежных функциональных элементов // Пробл. передачи информ. 1977. Т. 13. № 3. С. 56-76
Ортюков С. И. Об избыточности реализации булевых функций схемами из ненадежных элементов // Труды семинара по дискретной математике и её приложениям (Москва, 27-29 января 1987 г.). М.: Изд-во Моск. ун-та, 1989. С. 166-168
Uhlig D. Reliable networks from unreliable gates with almost minimal complexity // LNCS. 1987. V. 278. P. 462-469
Pippenger N. On networks of noisy gates // 26th Ann. Symp. Foundations of Computer Science. Portland, 21-23 Oct. 1985. P. 30-38
Яблонский C. В. Асимптотически наилучший метод синтеза надежных схем из ненадежных элементов // Banach Center Publ. 1982. V. 7. No. 1. P. 11-19
Тарасов В. В. К синтезу надежных схем из ненадежных элементов // Матем. заметки. 1976. T. 20. № 3. C. 391-400
Алехина М. А. О синтезе надежных схем из функциональных элементов x/y при однотипных константных неисправностях на выходах элементов // Вест. Моск. ун-та. Матем. Механ. 1991. № 5. С. 80-83
Алехина М. А. Синтез асимптотически оптимальных по надежности схем. Пенза: ИИЦ ПГУ, 2006. 156 с
Васин А. В. Асимптотически оптимальные по надежности схемы в полных базисах из трехвходовых элементов. Пенза: ИИЦ ПГУ, 2010. 100 с
Алехина М. А., Клянчина Д. М. Достаточные условия реализации булевых функций асимптотически оптимальными схемами с тривиальной оценкой ненадежности // Междунар. симп. «Надежность и качество, 2010» (Пенза, 24-31 мая 2010). Пенза: ИИЦ ПГУ, 2010. Т. 1. С. 229-232
Алехина М. А., Клянчина Д. М. Об асимптотически оптимальных по надежности схемах в некоторых специальных базисах // Известия высших учебных заведений. Поволжский регион. Физико-математические науки. 2010. №4 (16). С. 3-13
Алехина М. А., Клянчина Д. М. Об асимптотически оптимальных по надежности схемах в базисах, содержащих существенную линейную функцию и функцию вида x1a&xb2 // Материалы XVI Междунар. конф. «Проблемы теоретической кибернетики» (Нижний Новгород, 20-25 июня 2011). Н. Новгород: Изд-во Нижегород. ун-та, 2011. С. 33-37
Гаврилов Г. П., Сапоженко А. А. Задачи и упражнения по дискретной математике: учеб. пособие. 3-е изд., перераб. М.: Физматлит, 2006. 416 с
Алехина М. А., Васин А. В. О базисах с коэффициентом ненадежности 2 // Матем. заметки. 2014. Т. 95. № 2. С. 170-201
Алехина М. А., Гусынина Ю. С., Шорникова Т. А. Верхняя оценка ненадежности схем в полном конечном базисе (в P2) при произвольных неисправностях элементов // Изв. вузов. Математика. 2017. № 12. С. 8-83
Алехина М. А. О надежности схем в полном конечном базисе, содержащем линейную функцию двух переменных и обобщенную дизъюнкцию // Известия высших учебных заведений. Поволжский регион. Физико-математические науки. 2019. №1. С. 64-73.
Алехина М. А., Гусынина Ю. С., Шорникова Т. А. О надежности схем при неисправностях типа 0 на выходах элементов в полном конечном базисе, содержащем особенную функцию // Изв. вузов. Математика. 2019. № 6. С. 85-88
Алехина М. А., Пичугина П. Г. О надежности двойственных схем в полном конечном базисе // XVIII Междунар. школа-семинар «Синтез и сложность управляющих систем» (Пенза, 28 сентября-3 октября 2009). М.: Изд-во мех.-мат. ф-та МГУ, 2009. С. 10-13
Достаточные условия реализации булевых функций асимптотически оптимальными по надёжности схемами с тривиальной оценкой ненадёжности при неисправностях типа 0 на выходах элементов | Прикладная дискретная математика. 2019. № 45. DOI: 10.17223/20710410/45/5
Скачать полнотекстовую версию
Загружен, раз: 385