On the reliability of circuits in the rosser - tourkett basis (in P_k).pdf Пусть k, n Е N, k ^ 3, Ek = {0,1,... , k-1}, Pk - множество всех функций k-значной логики, т. е. функций /(x1,... , xn) : (E)n ^ Ek. Рассмотрим реализацию функций из множества Pk схемами из ненадёжных функциональных элементов в базисе Россера - Туркетта {0,1,..., k - 1, J0(x1), J1(x1),..., Jk-1(x1), min{x1, x2}, max{x1, x2}}. Будем считать, что схема из ненадёжных элементов реализует функцию /(xn) (xn = (x1,... ,xn)), если при поступлении на входы схемы набора an при отсутствии неисправностей в схеме на её выходе появляется значение /(йга). Пусть схема S реализует функцию /(xn), йга - произвольный входной набор схемы S, /(йга) = т. Обозначим через Pi(S, an) вероятность появления значения i Е Ek на выходе схемы S при входном наборе йга, а через Pf(an)=T(S, йга) -вероятность появления ошибки на выходе схемы S при входном наборе an. Ясно, что Pf(an)=T (S, ага) = = PT+1(S,an) + PT+2(S, an) + ... + PT+k-1 (S, an). В выражениях т +1, т + 2,..., т + k - 1 сложение осуществляется по mod k. Например, если входной набор йга схемы S такой, что /(йга) = 0, то вероятность появления ошибки на этом наборе равна Pf(an)=o(S, an) = P1(S, an) + P2(S, an) + ... + Pk-1(S, an) = £ Pi(S, an). i=1 Ненадёжностью схемы S, реализующей функцию /(xn), будем называть число P(S), равное наибольшей из вероятностей появления ошибки на выходе схемы S. Надёжность схемы S равна 1 - P(S). Предполагается, что элементы схемы независимо друг от друга с вероятностью е, 0 < е < 1/(2(k - 1)), подвержены инверсным неисправностям на выходах, т.е. каждый базисный элемент с функцией ^(xm), m Е N, на любом входном наборе am, таком, что ^(am) = т, с вероятностью е выдаёт любое из значений а, а = т (mod k). Поэтому вероятность ошибки на выходе любого базисного элемента равна (k - 1)е. Очевидно, что ненадёжность любого базисного элемента также равна (k - 1) е, а надёжность - 1 - (k - 1)е. Пусть P£(f) = inf P(S), где инфимум берется по всем схемам S из ненадёжных элементов, реализующим функцию f (xn). Схему A, реализующую f, назовем асимптотически оптимальной по надёжности, если P(A) ~ P£(f) при е ^ 0. Справедливы теоремы об оценках ненадёжности схем и классе функций, для схем которых нижняя оценка ненадёжности верна. Теорема 1. Любую функцию f Е Pk можно реализовать такой схемой S, что P(S) ^ 3(k - 1)е + 90k2е2 при всех е Е (0, l/(288k4)]. Обозначим через K(n) множество таких k-значных функций, зависящих от переменных xi,... ,xn (n ^ 3), что каждая из этих функций принимает все k значений и не представима ни в виде xk V h(xn), ни в виде xk&h(xn) (k Е {l, 2,... ,n}, h(xn) oo произвольная функция k-значной логики). Пусть K = У K(n). n=3 Теорема 2. |K(n)| ^ kk" - 2nk(k-i)kn-1 - k(k - l)k". Теорема 3. Пусть функция f Е K. Тогда для любой схемы S, реализующей f, при е Е (0, l/(288k4)] верно неравенство P(S) ^ 3(k - 1)е - (k - l)(3k - 1)е2 + k(k - 1)2е3. В заключение можно сделать следующие выводы: 1) Любую функцию из Pk можно реализовать схемой, функционирующей с ненадёжностью, асимптотически (при е ^ 0) не больше 3(k - l)e (теорема 1). 2) Любую функцию из класса K (содержащего почти все функции из Pk) нельзя реализовать схемой с ненадёжностью, асимптотически (при е ^ 0) меньше 3(k - ^е (теорема 3). 3) Схема, реализующая функцию f Е K и удовлетворяющая условиям теоремы 1, является асимптотически оптимальной по надёжности и функционирует с ненадёжностью, асимптотически равной 3(k - ^е при е ^ 0. Таким образом, в базисе Россера - Туркетта: 1) любую функцию k-значной логики можно реализовать схемой, ненадёжность которой асимптотически (при е ^ 0) не больше 3(k - ^е; 2) для почти любой функции такая схема является асимптотически оптимальной по надёжности и функционирует с ненадёжностью, асимптотически равной 3(k - ^е при е ^ 0. В списке литературы приведены работы, в которых получены результаты по надёжности и ненадёжности схем в базисе Россера - Туркетта при k = 3 [1-4] и k = 4 [5-8]. Результаты для произвольного k получены впервые.

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