On length, height and reliability of circuits realizing selection function
We consider planar (flat) circuits realizing the selection function v n = \Jxi x 2 ... xn y|i|, where n is an even integer; o i e {0,1}, x" = x i a n if Oi = 1 and xi = xi if Oi = 0, i = 1, 2,..., n; |a| e {0,1,..., 2 - 1} and |a| = E Oi2 . i=1 It is assumed that the switching elements are absolutely reliable, functional elements are subject to inversion failures on its outputs and independently pass into defective states. Some relations for the length and height, as well as an estimate of the unreliability of such circuits are found.
Keywords
булевы функции,
клеточные (плоские) схемы,
инверсные неисправности функциональных элементов,
ненадёжность схемы,
функция выбора,
Boolean functions,
planar circuits,
inversion failures,
unreliability of circuit,
function of selectionAuthors
| Rybakov A. V. | Penza State University | anajrov@gmail.com |
Всего: 1
References
Рыбаков А. В. Сложность асимптотически оптимальных по надежности клеточных схем // Сб. статей XVIII Междунар. науч.-методич. конф. «Университетское образование (МКУО-2014)», Пенза, 10-11 апреля 2014г. Пенза: Изд-во Пенз. ун-та, 2014. С. 310-311.
Улесова А. Ю. Сложность реализации булевых функций в некоторых моделях клеточных схем: дипломная работа. М.: МГУ им. Ломоносова, фак-т ВМиК, каф. математической кибернетики, 2010.
Кравцов С. С. О реализации функций алгебры логики в одном классе схем из функциональных и коммутационных элементов // Проблемы кибернетики. 1967. Вып. 19. С.285-292.
Алехина М. А., Аксенов С. И. О сложности надежных схем при инверсных неисправностях // Материалы IX Междунар. семинара «Дискретная математика и её приложения», посвящённого 75-летию со дня рождения О. Б. Лупанова (Москва, 18-23 июня 2007г.). М.: Изд-во мех.-мат. фак-та МГУ, 2007. С. 56-59.
Васин А. В. Об асимптотически оптимальных схемах в базисе {&, V,~} при инверсных неисправностях на выходах элементов // Известия высших учебных заведений. Поволжский регион. Физико-математические науки. 2008. № 4. С. 3-17.
Uhlig D. Reliable networks from unreliable gates with almost minimal complexity // LNCS. 1987. V. 278. P. 462-469.
Ортюков С. И. Об избыточности реализации булевых функций схемами из ненадежных элементов // Труды семинара по дискретной математике и её приложениям (Москва, 27-29 января 1987г.). М.: Изд-во МГУ, 1989. С. 166-168.
Von Neuman J. Probabilistic logics and the synthesis of reliable organisms from unreliable components // Automata Studies. C.Shannon, J. Mc. Carthy (eds). Princeton University Press, 1956. (Рус. пер.: Автоматы. М.: ИЛ, 1956. С. 68-139.)
