A lower bound for unreliability of circuits in the webb basis.pdf Пусть n E N, P3 -множество всех функций трёхзначной логики, т.е. функций f (x1,...,xn) : {0,1,2}n ^ {0,1,2}. Обозначим через x набор (x1,...,xn), тогда f (x1,...,xn) = f (x). Рассмотрим реализацию функций из множества P3 схемами из ненадёжных функциональных элементов в базисе, состоящем из функции Вебба V3(x1,x2) = = (max(x1,x2) + 1) mod 3. Будем считать, что схема из ненадёжных элементов реализует функцию f (x), если при поступлении на входы схемы набора а при отсутствии неисправностей в схеме на её выходе появляется значение f (а). Предполагается, что все базисные элементы ненадёжны, переходят в неисправные состояния независимо друг от друга, подвержены инверсным неисправностям на выходах. Эти неисправности характеризуются тем, что на произвольном входном наборе (а1,а2) базисного элемента, V3(a1,a2) = v, этот элемент с вероятностью 1 - 2е (е E (0,1/4)) выдаёт значение v, с вероятностью е - значение (v + 1) mod 3 и с вероятностью е - значение (v + 2) mod 3. Пусть схема S реализует функцию f (x), а - произвольный входной набор схемы S, f (а) = т. Обозначим через Pf(a)=T(S, а) вероятность появления ошибки на выходе схемы S при входном наборе а. Ясно, что Pf(a)=r(S, а) = PT+1(S, а) + PT+2(S, а). Например, если входной набор a схемы S такой, что f (a) = 0, то вероятность ошибки на этом наборе равна Pf(a)=o(S, a) = Pi(S, a) + P2(S, a). Ненадёжностью схемы S будем называть число P(S) = max{Pf(й)=т(S, a)}, где максимум берется по всем входным наборам aa схемы S. Надёжность схемы S равна 1 - P (S). Теорема 1 [1]. Любую функцию f G P3 можно реализовать такой схемой D, что P(D) ^ 8e + 268e2 при всех e G (0,1/104]. Из теоремы 1 следует, что любую функцию из P3 можно реализовать схемой, функционирующей с ненадёжностью, асимптотически (при e ^ 0) не больше 8e. Обозначим через K(n) множество функций трёхзначной логики, каждая из которых зависит от переменных x1,... ,xn (n ^ 3), принимает все три значения 0,1, 2 и не представима в виде max{xk ,h(Xn)} + c (k G {1, 2,...,n}, c G {0,1, 2}, h(Xn) - произвольная функция трёхзначной логики). оо Обозначим через K множество K = K(n). n=3 Справедлива теорема 2 о нижней оценке ненадёжности, доказательство которой аналогично доказательству теоремы о нижних оценках [2] (кратко в [3]). Теорема 2. Пусть функция f G K. Тогда для любой схемы S, реализующей f, при e G (0,1/104] верно неравенство P(S) ^ 6e - 16e2 + 12e3. Утверждение 1. |K(n)| ^ 33" - n31+2^-1 - 3 ■ 23". Из утверждения 1 следует, что класс K содержит почти все функции из P3, поскольку 33n - n31+2^3"-1 - 3 ■ 23" lim -оз"-= 1. n^O 33 Из теоремы 2 следует, что функцию из класса K (содержащего почти все функции множества P3) нельзя реализовать схемой с ненадёжностью, асимптотически (при e ^ 0) меньше 6e. Таким образом, получаем следующий результат: в базисе {v3(x1, x2)} почти любую функцию трёхзначной логики можно реализовать надёжной схемой, функционирующей с ненадёжностью, асимптотически не больше 8e и асимптотически не меньше 6e при e ^ 0.

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