Об асимптотически оптимальных по надежности схемах в некоторых специальных базисах (90,00 руб.)

М. А. Алехина, Д. М. Клянчина ОБ АСИМПТОТИЧЕСКИ ОПТИМАЛЬНЫХ ПО НАДЕЖНОСТИ СХЕМАХ В НЕКОТОРЫХ СПЕЦИАЛЬНЫХ БАЗИСАХ1 Аннотация. <...> Рассматривается реализация булевых функций схемами из ненадежных функциональных элементов в полном конечном базисе B, содержащем специальные функции. <...> Предполагается, что все элементы схемы независимо друг от друга с вероятностью ε  (0,1/2) подвержены неисправностям типа 0 на выходах. <...> Эта оценка ненадежности в два раза меньше, чем в случае инверсных неисправностей на выходах элементов в соответствующих базисах. <...> Рассмотрим реализацию булевых функций схемами из ненадежных функциональных элементов [1] в полном конечном базисе B, содержащем некоторую функцию из множества M = M1M2M3. <...> Считаем, что схема реали1 Работа выполнена при финансовой поддержке РГНФ, номер проекта 09-0628615а/В. <...> Поволжский регион зует функцию f  x1 , x2 ,..., xn  , если при поступлении на входы схемы набора a   a1 , a2 ,..., an  при отсутствии неисправностей на выходе схемы появляет- ся значение f  a  . <...> Ненадежность P(S) схемы S определяется как максимальное из чисел Pf ( a ) ( S , a ) при всевозможных входных наборах a . <...> Пусть P  f   inf P  S  , где S  схема из ненадежных элементов, реализующая булеву функцию f . <...> Пусть B3 – множество всех булевых функций, зависящих от трех переменных x1, x2, x3. <...> В случае инверсных неисправностей на выходах элементов доказано [2], что если полный конечный базис B содержит некоторую функцию множества G, то любую функцию f в этом базисе B можно реализовать схемой A с ненадежностью P(A) ≤ ε + 200ε2 при всех ε(0,1/960]. <...> Последнее утверждение верно и в случае неисправностей типа 0 на выходах элементов [3–5]. <...> Учитывая, что при неисправностях типа 0 на выходах элементов любая схема, содержащая хотя бы один функциональный элемент и реализующая отличную от константы 0 функцию, имеет ненадежность не менее ε [3], получаем следующий результат: если полный конечный базис B содержит некоторую функцию множества G, то для почти <...>