Lower bounds for unreliability of circuits in the rosser - tourkett basis.pdf Многозначная логика предоставляет широкие возможности для разработки различных алгоритмов во многих областях. Она позволяет уменьшить как вычислительную сложность, так и размеры, число соединений в различных арифметико-логических устройствах, повысить плотность размещения элементов на схемах, найти альтернативные методы решения задач. Уже сейчас многозначная логика с успехом применяется при решении многих задач и во множестве технических разработок. Среди них различные арифметические устройства, системы искусственного интеллекта и обработки данных, обработка сложных цифровых сигналов и т. д. В [1] описан функционально полный в P3 базис, в котором на компромиссной основе согласованы математические и технические (МДП-техники) требования и интересы, а также рассмотрены некоторые аспекты синтеза электронных схем в этом базисе. В [2] построен функционально полный в P4 базис, реализуемый в МОП-структурах. Таким образом, определённый интерес представляет задача исследования надёжности функционирования схем в полном конечном базисе из k-значных функций (k ^ 3). Задача построения надёжных схем в произвольном полном базисе из трёхзначных функций (k = 3) решена в [3]. В работе получена нижняя оценка ненадёжности схем в базисе Россера - Туркетта при k = 4. Нижняя оценка ненадёжности схем в том же базисе при k = 3 опубликована в [4]. Пусть n E N, а P4 - множество всех функций четырёхзначной логики, т. е. функций f (x1,...,xn) : {0,1, 2, 3}n ^ {0,1, 2, 3}. Рассмотрим реализацию функций из множества P4 схемами из ненадёжных функциональных элементов в базисе Россера - Тур-кетта {0,1, 2, 3, J0(x1), J1(x1), J2(x1), J3(x1), min{x1, x2},max{x1,x2}} (min{x1, x2} будем также обозначать через &, а max{x1,x2} -через V [1]). Будем считать, что схема из ненадёжных элементов реализует функцию f (xn) (xn = (x1,... ,xn)), если при поступлении на входы схемы набора ап при отсутствии неисправностей в схеме на её выходе появляется значение f (ап). Пусть схема S реализует функцию f (xn), an - произвольный входной набор схемы S, f (ап) = т. Обозначим через Pi(S, ап) вероятность появления значения i (i E G {0,1, 2, 3}) на выходе схемы S при входном наборе an, а через Pf(ап)=т(S, an) -вероятность появления ошибки на выходе схемы S при входном наборе an. Ясно, что Pf(й")=т(S,an) = PT+1(S, an) + PT+2(S,an) + PT+3(S, an). (В выражениях т +1, т + 2 и т + 3 сложение осуществляется по mod 4.) Например, если входной набор an схемы S такой, что f (an) = 0, то вероятность появления ошибки на этом наборе равна Pf (йп)=o(S, an) = P1(S, an) + P2(S, an) + P3(S, an). Ненадёжностью схемы S, реализующей функцию f (Xn), будем называть число P(S), равное наибольшей из вероятностей появления ошибки на выходе схемы S. Надёжность схемы S равна 1 - P(S). Предполагается, что элементы схемы независимо друг от друга с вероятностью e G (0,1/6) подвержены инверсным неисправностям на выходах, т.е. каждый базисный элемент с функцией >^(Xk) (k G {1, 2}) на любом входном наборе ak, таком, что ) = т, с вероятностью e выдаёт значение (т + 1) mod 4, с вероятностью e - значение (т + 2) mod 4 и с той же вероятностью - значение (т + 3) mod 4. Очевидно, что ненадёжность любого базисного элемента равна 3e, а надёжность равна 1 - 3e. Обозначим через K(n) множество таких функций четырёхзначной логики, зависящих от переменных x1 ,...,xn (n ^ 3), что каждая из этих функций принимает все четыре значения 0,1, 2, 3 и не представима ни в виде Xk V h(Xn), ни в виде xk&h(Xn) (k G {1, 2,...,n}, h(Xn) -произвольная функция четырёхзначной логики). оо Пусть K = U K (n). n=3 Теорема 1. |K(n)| ^ 44" - 2n434"-1 - 4 ■ 34". Доказательство проводится с использованием представления функции из класса K(n) в совершенной ДНФ. Из теоремы 1 следует, что класс K (n) содержит почти все функции четырёхзначной логики из P4(n), поскольку 2n434"-1 +4 ■ 34" -44"-= n^o 44 Справедлива теорема о нижней оценке ненадёжности схем, реализующих функции из класса K. Теорема 2. Пусть функция f G K. Тогда для любой схемы S, реализующей f, при e G (0,1/1000] верно неравенство P(S) ^ 9e - 33e2 + 36e3. Из теоремы 2 следует, что любая схема, реализующая функцию f G K, функционирует с ненадёжностью, которая асимптотически (при e ^ 0) не меньше 9e. Таким образом, функцию из класса K (содержащего почти все функции из P4) нельзя реализовать схемой с ненадёжностью, асимптотически (при e ^ 0) меньше 9e.

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