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

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

Метод коллокации для решения уравнения электрического поля, Параметрические комбинаторные задачи и методы их исследования, ...

М. А. Алехина, Д. М. Клянчина ОБ АСИМПТОТИЧЕСКИ ОПТИМАЛЬНЫХ ПО НАДЕЖНОСТИ СХЕМАХ В НЕКОТОРЫХ СПЕЦИАЛЬНЫХ БАЗИСАХ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 <...>

• Похожие документы из РУАЭСТ
• |
• Похожие документы из Руконт