О ненадежности схем из функциональных элементов, подверженных двум типам неисправностей

Актуальность и цели. В современной математике и технике теория синтеза схем из ненадежных функциональных элементов занимает важное место. До сих пор (насколько известно авторам) решались задачи реализации булевых функций надежными схемами в предположении, что функциональные элементы подвержены только одному типу неисправностей (например, инверсные неисправности на выходах элементов или константные неисправности на входах элементов). Эта работа - одна из первых работ, в которой подробно, со всеми доказательствами рассматривается задача синтеза надежных схем с элементами, подверженными неисправностям двух типов. Предполагается, что базисным элементам приписана функция штрих Шеффера (антиконъюнкция) и базисные элементы в неисправные состояния переходят независимо друг от друга. Первый тип неисправностей характеризуется тем, что при любом входном наборе базисного элемента на его выходе с некоторой вероятностью появляется значение, протиповоположное конъюнкции входных значений (т.е. имеем инверсные неисправности на выходах). Второй тип неисправностей появляется также на любом входном наборе элемента с некоторой (возможно, отличной от инверсной неисправности) вероятностью и характеризуется тем, что на выходе элемента появляется неопределенность. Отметим также, что в каждый такт работы базисный элемент подвержен только одной из двух названных неисправностей. Цель данной работы: исследовать возможность построения надежных схем, найти метод синтеза надежных схем, получить нетривиальные верхние и нижние оценки ненадежности схем. Результаты. Предложен метод повышения надежности схем при описанных неисправностях элементов, доказано, что, во-первых, любую булеву функцию можно реализовать схемой, ненадежность которой асимптотически не больше чем в три раза ненадежности базисного элемента; во-вторых, почти для всех функций (обозначим их множество через K) эта оценка ненадежности не улучшаема, т.е. ненадежность любой схемы, реализующей функцию из множества K, асимптотически меньше чем в три раза ненадежности базисного элемента. Функции множества K описаны явно. Выводы. Установлена возможность построения надежных схем при названных неисправностях элементов. Кроме того, найден метод повышения надежности схем и получены верхние и нижние оценки ненадежности схем. Эти оценки оказались асимптотически равными для функций множества K, т.е. почти для всех булевых функций.