The reliability of circuits in the basis of unreliable and absolutely reliable gates.pdf Рассматривается реализация булевых функций схемами в стандартном базисе |xi&x2,xi VX2,Xi}. Предполагается, что некоторые из базисных элементов абсолютно надёжны, а остальные - ненадёжные, с вероятностью е £ (0,1/2) подвержены инверсным неисправностям на выходах. Эти неисправности характеризуются тем, что в исправном состоянии базисный элемент реализует приписанную ему булеву функцию а в неисправном - функцию (/?. Считаем, что схема S, содержащая ненадёжные элементы, реализует булеву функцию f (x1,..., ), если при поступлении на входы схемы двоичного набора a при отсутствии неисправностей в схеме S на её выходе появляется значение f (a). Предполагается, что все ненадёжные элементы схемы переходят в неисправные состояния независимо друг от друга. Впервые задачу синтеза надёжных схем из ненадёжных функциональных элементов рассматривал Дж. фон Нейман [1]. Он также предполагал, что все базисные элементы с вероятностью е £ (0; 1/2) подвержены инверсным неисправностям на выходах и переходят в неисправные состояния независимо друг от друга. Дж. фон Нейман с помощью итерационного метода установил, что любую булеву функцию можно реализовать схемой, вероятность ошибки на выходе которой не больше се (с - положительная, зависящая от рассматриваемого базиса константа). Для повышения надёжности некоторой исходной схемы путём многократного дублирования он использовал схему, реализующую функцию голосования g(x1, x2, x3) = x1x2 V x1 x3 V x2x3. Число P(S), равное максимальной вероятности ошибки на выходе схемы S при всевозможных входных наборах схемы, назовем ненадёжностью схемы S; надёжность схемы S равна 1 - P (S). С. В. Яблонский [2] рассматривал задачу синтеза надёжных схем в базисе {x1&x2, x1 V x2, Х1, g(x1, x2, x3)}. Он предполагал, что элемент, реализующий функцию голосования g, абсолютно надёжный, а конъюнктор, дизъюнктор и инвертор - ненадёжные, подвержены произвольным неисправностям, ненадёжность каждого из них не больше е. Им доказано, что для любого p > 0 существует алгоритм, который для каждой булевой функции f (x1,x2,... , xn) для любого n строит такую схему S, что сложность схемы L(S) < 2n-1/n, а P(S) ^ p (т. е. ненадёжность схемы сколь угодно мала). Такие схемы называют схемами сколь угодно высокой надёжности. В отличие от С. В. Яблонского, А. В. Васин [3] предполагал, что все элементы базиса |xi&x2,xi V X2,Xi} ненадёжны, с вероятностью е подвержены инверсным неисправностям на выходах, и доказал, что любую функцию можно реализовать такой схемой S, что P(S) ^ 3е + 32е2 при всех е Е (0,1/128]. В этой работе (в зависимости от того, какие базисные элементы ненадёжны) получены следующие результаты. Теорема 1. Пусть конъюнктор и дизъюнктор абсолютно надёжны, а инвертор ненадёжный. Тогда любую функцию можно реализовать такой схемой что P(S) ^ 4(10е2)к при всех е Е (0,1/128], k Е N. Из теоремы 1 следует, что любую функцию можно реализовать схемой сколь угодно высокой надёжности. Кроме того, любая неконстантная монотонная функция f Е [xi&x2,xi Vx2], т.е. может быть представлена в виде ДНФ, в которой нет отрицаний. Поэтому такую функцию f можно реализовать абсолютно надёжно. Теорема 2. Пусть конъюнктор абсолютно надёжный, а инвертор и дизъюнктор ненадёжные; или дизъюнктор абсолютно надёжный, а инвертор и конъюнктор ненадёжные. Тогда любую функцию можно реализовать такой схемой S, что P(S) ^ е+10е2 при всех е Е (0, 1/128]. Теорема 3. Пусть инвертор абсолютно надёжный, а конъюнктор и дизъюнк-тор ненадёжные. Тогда любую функцию можно реализовать такой схемой S, что P(S) ^ 3е + 32е2 при всех е е (0,1/128]. Теорема 4. Пусть конъюнктор и инвертор абсолютно надёжные, а дизъюнктор ненадёжный; или дизъюнктор и инвертор абсолютно надёжные, а конъюнктор ненадёжный. Тогда любую функцию можно реализовать абсолютно надёжной схемой.

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