On the reliability of circuits in some full bases (in P₃) with inverse faults at the gate outputs.pdf Пусть n Е n, E3 = {0,1, 2}, P3 -множество всех функций трёхзначной логики, т. е. функций f (xi,... , xn) : (E3)n ^ E3. Рассмотрим реализацию функций из множества P3 схемами из ненадёжных функциональных элементов в полном конечном базисе B. Так же, как в работах [1-5], введём необходимые понятия и определения. Считаем, что схема из ненадёжных элементов реализует функцию f (Xn) (Xn = = (x1,... , xn)), если при поступлении на входы схемы набора ап при отсутствии неисправностей в схеме на её выходе появляется значение f (an). Пусть схема S реализует функцию /(Xn), йга - произвольный входной набор схемы S, /(ага) = т. Обозначим через Pj(S, йга) вероятность появления значения i (i е E3) на выходе схемы S при входном наборе йга, а через Pf (an)=T (S, йга) -вероятность появления ошибки на выходе схемы S при входном наборе ага. Ясно, что Pf(a«)=T (S, an) = = PT+1(S, an) + PT+2(S, an). (В выражениях т +1, т + 2 сложение осуществляется по mod 3.) Ненадёжностью схемы S, реализующей функцию /(Xn), будем называть число P(S), равное наибольшей из вероятностей появления ошибки на выходе схемы S. Надёжность схемы S равна 1 - P(S). Предполагается, что элементы схемы независимо друг от друга с вероятностью е (0 < е < 1/4) подвержены инверсным неисправностям на выходах, т.е. каждый базисный элемент с функцией ^(Xm) (m е n) на любом входном наборе am, таком, что ^(am) = т, с вероятностью е выдаёт любое из значений а = т и с вероятностью 1 - 2е - значение т. Очевидно, что ненадёжность любого базисного элемента равна 2е, а надёжность - 1 - 2е. Пусть P£(/) = inf P(S), где инфимум берется по всем схемам S из ненадёжных элементов, реализующим функцию /(Xn). Схему A, реализующую /, назовём асимптотически оптимальной по надёжности, если P(A) ~ P£(/) при е ^ 0. Справедливы теоремы об оценках ненадёжности схем и классе функций, для схем которых нижняя оценка ненадёжности верна. 1. Базис B1 = {0,1, 2, J0*(x1), J"1*(x1), J2*(x1), min{x1, x2}, max{x1, x2}}. Обозначим x1&x2 = min{x1, x2}, x1 V x2 = max{x1,x2}, а также Теорема 1. Любую функцию / е P3 можно реализовать такой схемой S в базисе B1, что P(S) ^ 6е + 126е2 при всех е е (0,1/1000]. Обозначим через K1(n) множество таких трёхзначных функций, зависящих от переменных x1,... , (n ^ 3), что каждая из этих функций принимает все три значения 0,1, 2 и не представима ни в виде V h(Xn), ни в виде & h(Xn) (k е {1, 2,... , n}, оо h(Xn) -произвольная функция трёхзначной логики). Пусть K1 = (J K1(n). n=3 Теорема 2. Для произвольной функции / е K1 любая схема S в базисе B1, реализующая /, функционирует с ненадёжностью P(S) ^ 6е - 16е2 + 12е3 при е е (0,1/1000]. Замечание 1. Нетрудно проверить, что класс K1(n) содержит почти все функции из P3(n). Таким образом, из теорем 1 и 2 в базисе B1 получаем следующие результаты: 1) любую функцию из P3 можно реализовать схемой, ненадёжность которой асимптотически (при е ^ 0) не больше 6е; 2) для почти любой функции такая схема является асимптотически оптимальной по надёжности и функционирует с ненадёжностью, асимптотически равной 6е при е ^ 0. 2. Базис B2 = {x1&x2 + 2}. Теорема 3. Любую функцию / е P3 можно реализовать такой схемой S в базисе B2, что P(S) ^ 8е + 268е2 при всех е е (0,1/104]. Пусть K2(n) -множество функций трёхзначной логики, каждая из которых зависит от переменных x1,... , (n ^ 3), принимает все три значения 0,1, 2 и не пред-ставима в виде min{xk, h(Xn)} + c (k E {1, 2,... , n}, c E {0,1, 2}, h(Xn) - произвольная oo функция трёхзначной логики). Пусть K2 = (J K2(n). n=3 Теорема 4. Для произвольной функции f E K2 любая схема S в базисе B2, реализующая f, функционирует с ненадёжностью P(S) ^ бе - 10е2 + 6е3 при е E (0,1/104]. Замечание 2. Нетрудно проверить, что класс K2(n) содержит почти все функции из P3(n). Таким образом, из теорем 3 и 4 в базисе B2 получаем следующие результаты: почти любую функцию трёхзначной логики можно реализовать надёжной схемой, функционирующей с ненадёжностью, асимптотически не больше 8е и асимптотически не меньше бе при е ^ 0.

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