Unreliability of circuits in case of constant failures on inputs and outputs of gates.pdf Впервые задачу синтеза надёжных схем из ненадёжных функциональных элементов рассматривал Дж. фон Нейман [1]. Он также предполагал, что все базисные элементы подвержены инверсным неисправностям на выходах и переходят в неисправные состояния независимо друг от друга. Задача синтеза надёжных схем при константных неисправностях одного типа (например, только типа 0 на входах элементов) решена в базисах из двухвходовых элементов [2]. В [3] приведены результаты о ненадёжности схем при инверсных неисправностях и отказах элементов. В этой работе впервые исследуется модель, в которой каждый элемент схемы может быть подвержен константным неисправностям четырёх типов: типа 0 или типа 1 на входах или выходах (с различными вероятностями). Заметим также, что инверсные неисправности элементов являются частным случаем в рассматриваемой модели неисправностей. Рассмотрим реализацию булевых функций схемами из ненадёжных функциональных элементов в базисе {x\y} (где x\y = x&y - штрих Шеффера). Схема из ненадёжных элементов реализует функцию f(xi,... , xn) (n E N), если при поступлении на входы схемы набора ага = (а1,... , an) при отсутствии неисправностей в схеме на её выходе появляется значение f (an). Предполагаем, что в каждый такт работы схемы на любом из входов и выходе любого из её элементов независимым образом могут происходить константные неисправности: типа 0 на входах с вероятностью y0 E (0,1/8), или типа 1 на входах с вероятностью y1 E (0, 1 /4), или типа 0 на выходах с вероятностью е0 E (0,1/4), или типа 1 на выходах с вероятностью е1 E (0,1/4). Неисправности типа 0 на входах элементов характеризуются тем, что в исправном состоянии функциональный элемент реализует функцию x\y, а в неисправном поступающий на его вход нуль не искажается, а поступающая на вход единица с вероятностью Yo может превратиться в нуль. Аналогично определяются неисправности типа 1 на входах. Неисправности типа 0 на выходах элементов характеризуются тем, что в исправном состоянии функциональный элемент реализует функцию x|y, а в неисправном - с вероятностью eo константу 0. Аналогично определяются неисправности типа 1 на выходах. Пусть схема S реализует булеву функцию f (Xn). Обозначим через Pf(an)(S, an) вероятность появления значения f (an) на выходе схемы S при входном наборе an. Ненадёжность P(S) схемы S определяется как максимальное из чисел Pjjan)(S, an) по всем входным наборам an схемы S. Надёжность схемы S равна 1 - P(S). Учитывая характер рассматриваемых неисправностей, вычислим вероятности появления ошибок на выходе базисного элемента E при всех входных наборах этого элемента: Po(E, (00)) = y2(1 - £i) + (1 - Y^o, Po(E, (01)) = Po(E, (10)) = Yi(1 - Yo)(1 - - ei) + (1 - Yi(1 - Yo))£o, Pi(E, (11)) = (1 - Yo)2ei + (2yo - Yo2)(1 - eo). Замечание 1. Отметим, что 1) если Yo = Yi = ei = 0, то получим неисправности типа 0 на выходах элементов с вероятностью eo; 2) если Yo = Yi = eo = 0, то получим неисправности типа 1 на выходах элементов с вероятностью ei; 3) если Yi = ei = = eo = 0, то получим неисправности типа 0 на входах элементов с вероятностью Yo; 4) если Yo = ei = eo = 0, то получим неисправности типа 1 на входах элементов с вероятностью Yi; кроме того 5) если Yo = Yi = 0 и eo = ei, то получим инверсные неисправности на выходах элементов с вероятностью eo; 6) если Yo = Yi и eo = ei = 0, то получим инверсные неисправности на входах элементов с вероятностью Yo. Обозначим Po(E, (00)),Po(E, (01)),Po(E, (10)),Pi(E, (11)) через а,в,8,т соответственно. Поскольку в нашем случае в = 8, ненадёжность элемента E равна P(E) = = max{a, в, т} ^ max{Yi + eo, 2yo + ei}. Обозначим через e = max{Yi + eo, 2yo + ei}. Очевидно, что P(E) ^ e. Справедлива теорема 1 об асимптотической верхней оценке ненадёжности схем. Теорема 1. Любую булеву функцию можно реализовать схемой, ненадёжность которой асимптотически не больше, чем 2eo + 2y2 + 2yo + ei при yo, Yi, eo, ei ^ 0. Доказательство такое же, как и в случае, когда базисный элемент подвержен только одному типу неисправностей. Пусть h(Xn) -произвольная булева функция, а K(n) -множество булевых функций вида f (Xn) = (Xj V h(Xn))a, где i G {1,... , n}; a G {0,1}. Нетрудно проверить, что число функций в классе K(n) не больше 2n22" , что мало по сравнению с общим чисоо лом 22 булевых функций от n переменных. Обозначим K = (J K(n). Справедлива n=i теорема 2 об асимптотической нижней оценке ненадёжности схем. Теорема 2. Если функция f G K, а S - любая схема, реализующая f, то ненадёжность P(S) схемы S асимптотически не меньше, чем 2eo + 2yo + ei + 2y2 при Yo, Yi,eo,ei ^ 0. Доказательство такое же, как и в случае, когда базисный элемент подвержен только одному типу неисправностей. Выводы: 1) любую булеву функцию можно реализовать схемой, ненадёжность которой асимптотически не больше 2eo + 2yo + ei + 2y2 при yo, Yi, eo, ei ^ 0; 2) для почти любой функции f (f E K) такая схема функционирует с ненадёжностью, асимптотически равной 2е0 + 2y0 + е1 + 2y2 при y0, Y1 ,е0,е1 ^ 0, т.е. оценку 2е0 + 2y0 + е1 + 2y2 нельзя понизить для функций f E K.

Скачать электронную версию публикации