М. А. Алехина, О. Ю. Барсукова
О НЕНАДЕЖНОСТИ СХЕМ
ИЗ ФУНКЦИОНАЛЬНЫХ ЭЛЕМЕНТОВ,
ПОДВЕРЖЕННЫХ ДВУМ ТИПАМ НЕИСПРАВНОСТЕЙ
Аннотация. <...> В современной математике и технике теория синтеза схем из ненадежных функциональных элементов занимает важное
место. <...> До сих пор (насколько известно авторам) решались задачи реализации
булевых функций надежными схемами в предположении, что функциональные элементы подвержены только одному типу неисправностей (например,
инверсные неисправности на выходах элементов или константные неисправности на входах элементов). <...> Эта работа – одна из первых работ, в которой подробно, со всеми доказательствами рассматривается задача синтеза надежных
схем с элементами, подверженными неисправностям двух типов. <...> Предполагается, что базисным элементам приписана функция штрих Шеффера (антиконъюнкция) и базисные элементы в неисправные состояния переходят независимо друг от друга. <...> Первый тип неисправностей характеризуется тем, что
при любом входном наборе базисного элемента на его выходе с некоторой вероятностью появляется значение, протиповоположное конъюнкции входных
значений (т.е. имеем инверсные неисправности на выходах). <...> Второй тип неисправностей появляется также на любом входном наборе элемента с некоторой
(возможно, отличной от инверсной неисправности) вероятностью и характеризуется тем, что на выходе элемента появляется неопределенность. <...> Отметим
также, что в каждый такт работы базисный элемент подвержен только одной
из двух названных неисправностей. <...> Цель данной работы: исследовать возможность построения надежных схем, найти метод синтеза надежных схем, получить нетривиальные верхние и нижние оценки ненадежности схем. <...> Предложен метод повышения надежности схем при описанных неисправностях элементов, доказано, что, во-первых, любую булеву функцию можно
реализовать схемой, ненадежность которой асимптотически не больше чем в
три раза ненадежности базисного элемента <...>