М. А. Алехина, С. И. Аксенов, А. В. Васин
О ФУНКЦИЯХ И СХЕМАХ, ПРИМЕНЯЕМЫХ
ДЛЯ ПОВЫШЕНИЯ НАДЕЖНОСТИ СХЕМ
Найден широкий класс булевых функций, способных повышать надежность схем. <...> Доказано, что при инверсных неисправностях на выходах элементов наличие функции из предлагаемого класса в заданном базисе гарантирует
реализацию произвольной булевой функции асимптотически оптимальной по
надежности схемой. <...> Впервые задачу синтеза надежных схем из ненадежных элементов рассматривал Дж. фон Нейман [1]. <...> Он предполагал, что все элементы схемы независимо друг от друга подвержены с вероятностью ( 0 1/ 2 ) инверсным
неисправностям на выходах, когда функциональный элемент с приписанной
ему функцией ( x ) в неисправном состоянии реализует функцию ( x ) . <...> Дж. фон Нейман предложил итерационный метод, позволяющий при
0 1/ 6 произвольную булеву функцию реализовать схемой, ненадежность которой асимптотически не больше при условии, что в рассматриваемом базисе содержится функция голосования g ( x1 , x2 , x3 ) x1x2 x1x3 x2 x3 . <...> Метод дает экспоненциальное увеличение сложности схемы (примерно в 3k
раз, где k – используемое число итераций). <...> Схема из ненадежных элементов имеет две важные характеристики:
вероятность ошибки на выходе схемы (ненадежность) и сложность схемы. <...> Оптимизации сложности схем уделялось главное внимание в работах <...> Задача построения асимптотически оптимальных по надежности схем из ненадежных
элементов решалась М. А. Алехиной [4]. <...> Рассматривается реализация булевых функций схемами из ненадежных
элементов над конечным полным базисом B {e1 , ..., em } [5]. <...> Множество всех
функциональных элементов Ei , функции которых ei принадлежат базису B,
будем также называть базисом B [6]. <...> Схема из ненадежных функциональных
элементов реализует булеву функцию f ( x1 , ..., xn ) , если при поступлении на
вход схемы двоичного набора a (a1 , ..., an ) при отсутствии неисправностей на
выходе схемы появляется значение f (a ) . <...> Каждому <...>