, А. В. Васин
СИНТЕЗ АСИМПТОТИЧЕСКИ
ОПТИМАЛЬНЫХ ПО НАДЕЖНОСТИ СХЕМ
Аннотация. <...> Рассматривается задача синтеза асимптотически оптимальных по
надежности схем, реализующих булевы функции, при инверсных неисправностях на выходах элементов в некоторых полных неприводимых базисах из
двухвходовых функциональных элементов. <...> Доказано, что в рассматриваемых
базисах все булевы функции можно реализовать асимптотически оптимальными по надежности схемами, причем почти для всех функций эти схемы
функционируют с ненадежностью, асимптотически равной 2ε при ε→0 (ε – вероятность инверсной неисправности на выходе базисного элемента). <...> Сложность этих схем асимптотически не больше чем в три раза превышает сложность минимальных схем, построенных из абсолютно надежных элементов. <...> Ключевые слова: надежные схемы, ненадежные элементы, инверсные неисправности, синтез схем, булевы функции. <...> Впервые задачу синтеза надежных комбинационных схем из ненадежных функциональных элементов (ФЭ) рассматривал Дж. фон Нейман [1]. <...> Он
предполагал, что все элементы схемы независимо друг от друга с вероятностью (0; 1/2) подвержены инверсным неисправностям на выходах. <...> С помощью итерационного метода Дж. фон Нейман
48
№ 2 (10), 2009
Технические науки. <...> Информатика, вычислительная техника
установил, что в произвольном полном базисе при (0; 1/6) любую булеву
функцию можно реализовать схемой, вероятность ошибки на выходе которой
при любом входном наборе значений переменных не превосходит c1 (c1 –
некоторая константа, зависящая от базиса). <...> В частности, если базис содержит функцию голосования g ( x1 , x2 , x3 ) x1 x2 x1 x3 x2 x3 , то произвольную
булеву функцию можно реализовать схемой, вероятность ошибки на выходе которой при любом входном наборе значений переменных не превосходит + c2ε2 при c3 , где c2, c3 – некоторые константы. <...> Основной недостаток метода Дж. фон Неймана в том, что сложность схемы с ростом числа
итераций увеличивается экспоненциально <...>