В. В. Чугунова
АСИМПТОТИЧЕСКИЕ ОЦЕНКИ НЕНАДЕЖНОСТИ СХЕМ
ПРИ ИНВЕРСНЫХ НЕИСПРАВНОСТЯХ НА ВХОДАХ
Показано, что если к каждому из неприводимых полных базисов добавить еще три неконгруентные булевы функции, зависящие не более чем от
двух переменных, то в полученных базисах асимптотическая оценка ненадежности схем равна 2ε для почти всех функций. <...> Рассмотрим реализацию булевых функций схемами из ненадежных
двухвходовых функциональных элементов. <...> Схема реализует функцию f(x1, x2,
..., xn) = f ( x ) , если при поступлении на входы схемы набора a = (a1, a2, ...,
an) при отсутствии неисправностей на выходе схемы появляется значение
f (a ) . <...> Предполагается, что входы всех элементов схемы независимо друг от
друга с вероятностью ε (0 < ε < 1/2) подвержены инверсным неисправностям. <...> Эти неисправности характеризуются тем, что поступающее на вход элемента
значение a, (a ∈ {0, 1}) с вероятностью ε может превратиться в значение a . <...> Пусть Pf ( a ) ( S , a ) – вероятность появления значения f (a ) на выходе
схемы S, реализующей булеву функцию f ( x ) , при входном наборе a . <...> Ненадежность P(S) схемы S определяется как максимальное из чисел Pf ( a ) ( S , a )
при всевозможных входных наборах a . <...> Обозначим Pε ( f ) = inf P ( S ) , где S – схема из ненадежных элементов,
реализующая булеву функцию f. <...> Схему A из ненадежных элементов, реализующую булеву функцию f, назовем асимптотически оптимальной (наилучшей) по надежности, если P(A) ∼ Pε ( f ) при ε → 0. <...> Пусть B′ – это множество всех булевых функций, зависящих не более
чем от двух переменных. <...> Множество B ⊂ M(x1, x2) назовем неприводимым полным базисом
(в P2), если множество B полно и никакое его собственное подмножество
полным не является. <...> Поволжский регион
Любой другой базис, отличный от базисов B1–B17 (например, B18 =
= {x1 & x2, x1 ∨ x2, x1 }), можно получить переименованием переменных без
отождествления, а также добавлением одной или нескольких функций из
множества M(x1, x2) к некоторому базису из указанного списка. <...> Асимптотические оценки ненадежности схем из двухвходовых <...>