The reliability of circuits in Rosser - Turkett basis (in P₃) with faults of type 0 at the outputs of gates.pdf Исторически сложилось так, что сначала при построении надёжных схем, состоящих из ненадёжных элементов и реализующих булевы функции, исследовались инверсные неисправности на выходах элементов. Позднее рассматривалась возможность реализации булевых функций схемами из ненадёжных элементов, подверженных однотипным константным неисправностям на выходах, в частности неисправностям типа 0 на выходах [1-3]. Решение задачи построения надёжных схем, реализующих функции трёхзначной логики, также сначала было получено при инверсных неисправностях на выходах элементов [4-8]. В этой работе решается задача построения асимптотически оптимальных по надёжности схем, реализующих функции трёхзначной логики и построенных из ненадёжных элементов, подверженных неисправностям типа 0 на выходах элементов. Пусть n £ n, E3 = {0,1,2}, P3 - множество всех функций трёхзначной логики, т.е. функций f(xi,...,xn) : E'3 ^ E3. Рассмотрим реализацию функций из множества P3 схемами из ненадёжных функциональных элементов в базисе Россе-ра -Туркетта B = {0,1, 2, J0(xi), Ji(xi), J2(xi), min{xi,x2}, max{xi,x2}}. Обозначим xi&x2 = min{xi,x2}, xi V x2 = max{xi,x2}, xn = (xi,..., xn). Определения вероятности ошибки на выходе схемы, ненадёжности и надёжности схемы, асимптотически оптимальной по надёжности схемы вводятся так же, как в работах [4-8]. Предполагается, что базисные элементы подвержены неисправностям типа 0 на выходах, причём переходят в неисправные состояния независимо друг от друга с вероятностью е (е < 1/2). Эти неисправности характеризуются тем, что на нулевых входных наборах функциональный элемент выдаёт правильное значение 0 с вероятностью 1, на остальных наборах - значение 0 с вероятностью е, а правильное значение с вероятностью 1 - е. Очевидно, что при неисправностях типа 0 на выходах элементов ненадёжность любого базисного элемента, кроме реализующего константу 0, равна е, а надёжность - 1 - е. Элемент, реализующий константу 0, функционирует абсолютно надёжно. Ясно также, что функции xi, i Е n, можно реализовать абсолютно надёжно, не используя функциональных элементов. Обозначим базисный элемент с функцией & через E&, а базисный элемент с функцией V - через Ev. Пусть f - произвольная функция из P3, S - любая схема, реализующая функцию f, P(S) -ненадёжность схемы S. По схеме S построим схему, которая реализует ту же функцию f, но, возможно (при некоторых условиях на P(S)), более надёжно. Для этого возьмём два экземпляра схемы S и один элемент E&, соединим выходы схем S со входами элемента E&. Построенную схему назовём D. Затем возьмём два экземпляра схемы D и один элемент Ev. Соединим выходы схем D со входами элемента Ev. Построенную схему назовем -0(S). В теореме 1 найдено рекуррентное соотношение для ненадёжностей схем S и ^(S). Теорема 1. Схема ^(S) реализует функцию f c ненадёжностью PC0(S)) ^ е + (е + 2P(S))2. С помощью теоремы 1 получим верхнюю оценку ненадёжности схем. Теорема 2. Любую функцию f Е P3 можно реализовать такой схемой S, что P(S) ^ е + 12е2 при всех е Е (0,1/300]. Пусть K(n) -множество функций трёхзначной логики, каждая из которых зависит от переменных xi,... , xn (n ^ 1), отлична от константы 0 и функций xi,... , xn. оо Обозначим K = U K(n). Очевидно, что |K(n)| = 33" - n - 1, а значит, класс K(n) n=1 содержит почти все функции из множества P3(n) (поскольку lim ---= 1 ). V га^о 33 / Справедлива теорема 3 о нижней оценке ненадёжности схем, каждая из которых реализует некоторую функцию из класса K. Теорема 3. Пусть функция f Е K. Тогда для любой схемы S, реализующей f, верно неравенство P(S) ^ е. Таким образом, в базисе Россера - Туркетта (в P3) при неисправностях типа 0 на выходах элементов: 1) любую функцию трёхзначной логики можно реализовать схемой, ненадёжность которой асимптотически (при е ^ 0) не больше е; 2) для любой функции f Е K такая схема является асимптотически оптимальной по надёжности и функционирует с ненадёжностью, асимптотически равной е при е ^ 0; 3) функцию f Е K можно реализовать абсолютно надёжно.

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