The unreliability of logic circuits of unreliable functional elements.pdf Пусть n E n, P2 - множество всех булевых функций, т.е. функций f (x1,... ,) : {0,1}n ^ {0,1}. Рассмотрим реализацию булевых функций схемами из ненадёжных функциональных элементов в полном конечном базисе B = {e1,..., eq} С P2 (q E n). Обозначим через E, базисный элемент с функцией e, (i G {1,... , q}). Предполагается, что неисправности элементов произвольные [1, с. 480] и статистически независимые, т. е. элементы схемы переходят в неисправные состояния независимо друг от друга. Пусть f (Xn) (Xn = (x1,... ,xn)) -произвольная функция, а S - любая схема, реализующая её в базисе B. Ненадёжность P (S) схемы S определяется как максимальная из вероятностей ошибок на выходе схемы S [2]. Надёжность схемы равна 1 - P(S). При построении схемы (неветвящейся программы) высокой надёжности, реализующей f (Xn), в заданном базисе B при заданных неисправностях элементов приходится использовать итерационный метод, применяя его к некоторой исходной схеме (неветвящейся программе), реализующей f (Xn) (см., например, [3-6]). При этом нужно знать верхнюю оценку ненадёжности исходной схемы, которая зависит от базиса и типа неисправностей. Конечно, можно было бы использовать тривиальную верхнюю оценку ненадёжности исходной схемы (неветвящейся программы), которая равна произведению числа функциональных элементов схемы на максимальную ненадёжность базисного элемента. Но чтобы число итераций при построении схемы (неветвящейся программы) высокой надёжности было, по возможности, небольшим (поскольку с каждым шагом итерации увеличивается сложность схемы (неветвящейся программы)), а вероятность неисправности была сверху ограничена константой, желательно в качестве исходной схемы брать схему с достаточно «хорошей» надёжностью. До настоящего времени в произвольном полном конечном базисе подобные оценки ненадёжности схем были известны лишь при инверсных неисправностях на выходах элементов [7, 8] и при однотипных константных неисправностях на выходах элементов [9]. Нетривиальная универсальная (пригодная для любого полного конечного базиса и любых неисправностей элементов) оценка ненадёжности исходной схемы (неветвящей-ся программы) приведена в теореме 1. Теорема 1. Пусть B - произвольный полный конечный базис, P(B) = max{P(E1), ... , P(Eq)}. Тогда любую булеву функцию f можно реализовать схемой S в базисе B, ненадёжность которой P(S) ^ 5P(B) + 162P2(B) при P(B) ^ 1/960. Следствие 1. Пусть B - произвольный полный конечный базис, P(B) = = max{P(E1),...,P(Eq)}. Тогда любую булеву функцию f можно реализовать схемой S в базисе B, ненадёжность которой P(S) ^ 5,17P(B) при P(B) ^ 1/960. Таким образом, произвольную булеву функцию можно реализовать схемой, ненадёжность которой не больше 5,17P(B), а надёжность - не меньше 1 - 5,17P(B), где P(B) - ненадёжность «худшего» из базисных элементов. Покажем, как, используя теорему 1 и следствие из неё, можно в произвольном полном конечном базисе получить верхнюю оценку ненадёжности схем, например, при инверсных неисправностях на входах элементов. Пример. Пусть элементы полного базиса B = {ei,... , eq} (q G N) с вероятностью £ подвержены инверсным неисправностям на входах, причём каждый из входов любого элемента Ej (с функцией ej, j G {1,... , q}) схемы переходит в неисправное состояние независимо от других входов этого элемента и входов других элементов схемы. Пусть m ^ 2 - такое наименьшее натуральное число, при котором B С P2(m), т.е. каждая из базисных функций ej зависит не более чем от m переменных. Тогда P(B) ^ m£. По следствию 1 произвольную булеву функцию можно реализовать схемой, ненадёжность которой не больше 5,17m£ при всех £ ^ 1/(960m).

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