We consider the implementation of Boolean functions by circuits from unreliable functional elements in a complete basis containing functions of three variables. We suppose that the elements of the circuit pass to faulty states independently of each other, and they subject to the single-type constant faults of 0 type at outputs. For each complete basis, either the exact value of the coefficient of unreliability is found, or the upper estimate for this coefficient is calculated.
Download file
Counter downloads: 65
- Title About the reliability of logic circuits in all complete bases with three-input elements and failures of zero type on their outputs
- Headline About the reliability of logic circuits in all complete bases with three-input elements and failures of zero type on their outputs
- Publesher
Tomsk State University
- Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 49
- Date:
- DOI 10.17223/20710410/49/7
Keywords
ненадёжные функциональные элементы, надёжность и ненадёжность схемы, синтез схем из ненадёжных элементов, unreliable functional elements, reliability and unreliability of circuit, synthesis of circuits composed of unreliable elementsAuthors
References
Фон Нейман Дж. Вероятностная логика и синтез надежных организмов из ненадежных компонент // Автоматы. М.: ИЛ, 1956. С. 68-139.
Добрушин Р. Л., Ортюков С. И. Верхняя оценка для избыточности самокорректирующихся схем из ненадежных функциональных элементов // Проблемы передачи информации. 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. C. 80-83.
Алехина М. А. Синтез, надежность и сложность схем из ненадежных функциональных элементов: дис.. докт. физ.-мат. наук. М.: МГУ им. М.В. Ломоносова, 2004.
Васин А. В. Асимптотически оптимальные по надежности схемы в полных базисах из трехвходовых элементов: дис.. канд. физ.-мат. наук. Казань: Казанский (Приволжский) федеральный университет, 2010.
Алехина М. А., Гусынина Ю. С., Шорникова Т. А. О надежности схем при неисправностях типа 0 на выходах элементов в полном конечном базисе, содержащем особенную функцию // Изв. вузов. Математика. 2019. №6. С. 85-88.
Алехина М. А., Клянчина Д. М. Об асимптотически оптимальных по надежности схемах в базисах, содержащих существенную линейную функцию и функцию вида x<sup>a</sup><sub>1</sub>&x<sup>b</sup><sub>2</sub> // Материалы XVI Междунар. конф. «Проблемы теоретической кибернетики» (Нижний Новгород, 20-25 июня 2011 г.). Н. Новгород: Изд-во Нижегород. ун-та, 2011. С. 33-37.
Алехина М. А. О надежности схем в полном конечном базисе, содержащем линейную функцию двух переменных и обобщенную дизъюнкцию // Известия высших учебных заведений. Поволжский регион. Физико-математические науки. 2019. №1. С. 56-62.
Alekhina M. A., Barsukova O. Yu., and Shornikova T. A. On the reliability of circuits with type 0 faults at the outputs of the elements in the complete finite basis containing an essential linear function // Lobachevskii J. Mathematics. 2019. V.40. No. 12. P.2027-2033.
Алехина М. А., Грабовская С. М., Гусынина Ю. С. Достаточные условия реализации булевых функций асимптотически оптимальными по надежности схемами с тривиальной оценкой ненадежности при неисправностях типа 0 на выходах элементов // Прикладная дискретная математика. 2019. №45. С. 44-54.
Алехина М. А., Шорникова Т. А. О надежности схем при неисправностях типа 0 на выходах элементов в полном конечном базисе, содержащем некоторые пары функций // Изв. вузов. Математика (в печати).
Алехина М. А. О надежности схем в произвольном полном конечном базисе при однотипных константных неисправностях на выходах элементов // Дискретная математика. 2012. Т. 24. Вып.3. С. 17-24.
Алехина М. А., Пичугина П. Г. О надежности двойственных схем в полном конечном базисе // Материалы XVIII Междунар. школы-семинара «Синтез и сложность управляющих систем», Пенза, 28 сентября-3 октября 2009 г. М.: Изд-во мех.-мат. ф-та МГУ, 2009. С. 10-13.

About the reliability of logic circuits in all complete bases with three-input elements and failures of zero type on their outputs | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2020. № 49. DOI: 10.17223/20710410/49/7
Download full-text version
Counter downloads: 190