РУсскоязычный Архив Электронных СТатей периодических изданий
Известия высших учебных заведений. Поволжский регион. Физико-математические науки/2010/№ 4/

Об асимптотически оптимальных по надежности схемах в некоторых специальных базисах

Рассматривается реализация булевых функций схемами из ненадежных функциональных элементов в полном конечном базисе B, содержащем специальные функции. Предполагается, что все элементы схемы независимо друг от друга с вероятностью [эпсилон] (0, 1/2) подвержены неисправностям типа 0 на выходах. Доказано, что почти для всех булевых функций асимптотически оптимальные по надежности схемы функционируют с ненадежностью, асимптотически равной [эпсилон] при [эпсилон] [стрелка вправо] 0. Эта оценка ненадежности в два раза меньше, чем в случае инверсных неисправностей на выходах элементов в соответствующих базисах.

Авторы
Тэги
Тематические рубрики
Предметные рубрики
В этом же номере:
Резюме по документу**
М. А. Алехина, Д. М. Клянчина ОБ АСИМПТОТИЧЕСКИ ОПТИМАЛЬНЫХ ПО НАДЕЖНОСТИ СХЕМАХ В НЕКОТОРЫХ СПЕЦИАЛЬНЫХ БАЗИСАХ1 Аннотация. <...> Рассматривается реализация булевых функций схемами из ненадежных функциональных элементов в полном конечном базисе B, содержащем специальные функции. <...> Предполагается, что все элементы схемы независимо друг от друга с вероятностью ε (0,1/2) подвержены неисправностям типа 0 на выходах. <...> Эта оценка ненадежности в два раза меньше, чем в случае инверсных неисправностей на выходах элементов в соответствующих базисах. <...> Поволжский регион зует функцию f 12, ,..., nxx x , если при поступлении на входы схемы набора при отсутствии неисправностей на выходе схемы появляется значение f a . <...> Ненадежность P(S) схемы S определяется как максимальное из чисел PS a fa ()(, ) при всевозможных входных наборах a . <...> В случае инверсных неисправностей на выходах элементов доказано [2], что если полный конечный базис B содержит некоторую функцию множества G, то любую функцию f в этом базисе B можно реализовать схемой A с ненадежностью P(A) ε + 200ε2 при всех ε(0,1/960]. <...> Последнее утверждение верно и в случае неисправностей типа 0 на выходах элементов [3–5]. <...> Учитывая, что при неисправностях типа 0 на выходах элементов любая схема, содержащая хотя бы один функциональный элемент и реализующая отличную от константы 0 функцию, имеет ненадежность не менее ε [3], получаем следующий результат: если полный конечный базис B содержит некоторую функцию множества G, то для почти всех функций асимптотически оптимальные по надежности схемы функционируют с ненадежностью, асимптотически равной ε при ε 0. <...> В работе [6] доказано, 4 Pf inf P S , где S схема из ненадежных элементов, реализующая булеву функцию f . <...> Схему A из ненадежных элементов, реализующую булеву функцию f , назовем асимптотически оптимальной по на 4 (16), 2010 <...>
** - вычисляется автоматически, возможны погрешности

Похожие документы: