А. В. Васин
ОБ АСИМПТОТИЧЕСКИ ОПТИМАЛЬНЫХ СХЕМАХ В БАЗИСЕ
{x & y, x ∨ y , x } ПРИ ИНВЕРСНЫХ НЕИСПРАВНОСТЯХ
НА ВЫХОДАХ ЭЛЕМЕНТОВ
Рассматривается задача синтеза асимптотически оптимальных схем,
реализующих булевы функции, при инверсных неисправностях на выходах
элементов в базисе {x & y, x ∨ y, x } . <...> Доказано, что почти все булевы функции
можно реализовать асимптотически оптимальными по надежности схемами,
которые функционируют с ненадежностью, асимптотически равной 3ε при
ε→0, где ε – вероятность инверсной неисправности на выходе базисного элемента. <...> Сложность предлагаемых схем превышает сложность минимальных
схем, построенных только из надежных элементов, не более чем в 3 раза. <...> Введение
Впервые задачу синтеза надежных схем из ненадежных функциональных
элементов (ФЭ) рассматривал Дж. фон Нейман [1]. <...> Он предполагал, что все элементы схемы независимо друг от друга с вероятностью ε (ε∈(0; 1/2)) подвержены инверсным неисправностям на выходах. <...> Эти неисправности характеризуются
тем, что в исправном состоянии функциональный элемент реализует приписанную ему булеву функцию ϕ , а в неисправном – функцию ϕ . <...> С помощью итерационного метода Дж. фон Нейман установил, что в произвольном полном базисе
при ε∈(0; 1/6) любую булеву функцию можно реализовать схемой, на выходе
которой вероятность ошибки при любом входном наборе значений переменных
не превосходит c1ε (c1 – некоторая константа, зависящая от базиса). <...> Затем схемы с инверсными неисправностями на выходах элементов исследовались в работах Р. Л. Добрушина, С. И. Ортюкова, Д. <...> Улига [2–7] и некоторых других авторов, причем главное внимание уделялось сложности
схем (задача синтеза оптимальных по надежности схем до появления работ <...> Рассматривается реализация булевых функций схемами из ненадежных функциональных элементов в произвольном конечном полном базисе
B = {e1 , e2 , ..., em }, m ∈ N [8] (множество всех функциональных элементов Ei,
функции которых ei принадлежат базису В, будем <...>