About basises with unreliability coefficient 5.pdf Рассматривается реализация булевых функций схемами [1] из ненадёжных функциональных элементов в произвольном полном конечном базисе B. Предполагаем, что все элементы схемы независимо друг от друга с вероятностью е G (0,1/2) подвержены инверсным неисправностям на выходах. Эти неисправности характеризуются тем, что в исправном состоянии функциональный элемент реализует приписанную ему булеву функцию 0, а в неисправном - функцию 0. Считаем, что схема S из ненадёжных элементов реализует булеву функцию /(xi, x2,..., xn), если при поступлении на входы схемы двоичного набора a = (a1, a2,... , an) при отсутствии неисправностей на выходе схемы S появляется значение /(a). Ненадёжностью P(S) схемы S назовем максимальную вероятность ошибки на выходе схемы S при всевозможных входных наборах схемы. Надёжность схемы S равна 1 - P(S). Пусть P£(/) = inf P(S), где инфимум берется по всем схемам S из ненадёжных элементов, реализующим булеву функцию /(x1 , x2, . . . , xn ) . Схема A из ненадёжных элементов, реализующая функцию /, называется асимптотически оптимальной (асимптотически наилучшей) по надёжности, если P(A) ~ P£(/) при е ^ 0. Число k будем называть коэффициентом ненадёжности полного базиса, если все функции в этом базисе можно реализовать схемами с ненадёжностью, асимптотически не больше ke (при е ^ 0), и найдётся функция /, которую нельзя реализовать схемой с ненадёжностью, асимптотически меньше чем ke (при е ^ 0). В [2] обосновано, что k G {1, 2, 3, 4, 5}. Эта работа посвящена полным базисам с коэффициентом ненадёжности k = 5. Пусть оо k Ф1 = {0,1,xi}U U{ & xi}, k=2 i=1 оо k оо k k Ф2 = {0,1}UU{ & xi}uUU{x,- ■ & xi}, k=2 i=1 k=1 j=1 i=1,i=J оо k Ф1 = {0,1,x1}U (J{V xi}, k=2 i=1 оо k оо k k Ф2 = {0,1}u(j{V xi}uUU{x,- v V xi}. k=2 i=1 k=1 j=1 i=1,i=j С. И. Аксенов сформулировал следующую теорему. Теорема 1 [3]. Пусть B - полный базис и B £ Ф*, B £ Ф2, B £ Ф£, B £ Ф2. Тогда любую булеву функцию f можно реализовать схемой S над B с ненадёжностью P(S) ^ 4е + се2 при е Е (0,е0], где константы с > 0, е0 Е (0,1/2) зависят от базиса. Из теоремы 1 следует: если полный базис B удовлетворяет условиям B £ Ф*, B £ Ф 2, B £ Ф*, B £ Ф2, то его коэффициент ненадёжности k Е {1, 2, 3, 4}. Однако теорема 1 - только верхняя оценка ненадёжности, которая не дает представления о коэффициенте ненадёжности базисов B, удовлетворяющих B С Ф*, или B С Ф2, или B С Ф*, или B С Ф2. С. И. Аксеновым в [4] получена верхняя оценка ненадёжности схем в произвольном полном конечном базисе при инверсных неисправностях на выходах элементов. Он доказал, что существуют такие константы е0 Е (0,1/2) и d > 0, зависящие от базиса, что любую булеву функцию f можно реализовать схемой S с ненадёжностью P(S) ^ 5е + de2 при е Е (0, ео]. В работе [5] явно найдены константы d, е0 и доказана теорема 2. Теорема 2 [5]. В произвольном полном конечном базисе B любую булеву функцию f можно реализовать схемой A с ненадёжностью P(A) ^ 5е + 182е2 при е ^ 1/960. Теорема 2 справедлива и для базисов B, удовлетворяющих условию B С Ф*, или B С Ф2, или B С Ф*, или B С Ф2. Автором в [2] решена задача построения асимптотически оптимальных по надёжности схем при инверсных неисправностях на выходах элементов в полных базисах из трёхвходовых элементов, доказаны нижние оценки ненадёжности для базисов B С {0,1,x*,Ж1&Ж2,Ж1&Ж2&Ж3}, B С {0,1, x*&x2, x*&x2&x3, x*&x2, x*&x2&x3}, B С {0,1, x*, x* V x2, x* V x2 V x3}, B С {0,1, x* V x2, x* V x2 V x3, x* V x2, x* V x2 V x3} и показано, что коэффициент ненадёжности указанных базисов равен 5. Нетрудно видеть, что эти базисы являются подмножествами множеств Ф*, Ф2, Ф*, Ф^. Поэтому можно предположить, что в базисах B, удовлетворяющих условию B С Ф*, или B С Ф2, или B С Ф*, или B С Ф2, коэффициент ненадёжности базиса также равен 5. Для проверки справедливости последней гипотезы необходимо доказать нижние оценки ненадёжности для этих базисов. Обозначим K(n) -множество булевых функций f, зависящих от переменных x*, x2,..., xn, не представимых в виде (x"&g(x))b, где i = 1, 2, ...,n, a,b Е {0,1}, x = (x*,x2,...,xn), и сформулируем теорему о нижних оценках ненадёжности для названных базисов. Теорема 3. Пусть B - полный конечный базис и B С Ф*, или B С Ф2, или B С Ф*, или B С Ф2. Пусть функция f Е K(n) и S - любая схема, реализующая f. Тогда P(S) ^ 5е(1 - е)4 при е Е (0,1/960]. Из теорем 2 и 3 следует, что в любом из полных базисов B, таких, что B С Ф*, B С Ф2, B С Ф*, B С Ф2, для почти всех функций асимптотически оптимальные по надёжности схемы функционируют с ненадёжностью, асимптотически равной 5е при е ^ 0. Следовательно, коэффициент ненадёжности базисов B, удовлетворяющих условию B С Ф*, или B С Ф2, или B С Ф*, или B С Ф2, равен 5. Таким образом, если учесть теоремы 2 и 3 и добавить теорему С. И. Аксенова из работы [3], то получим теорему 4. Теорема 4. Коэффициент ненадёжности полного базиса B равен 5 тогда и только тогда, когда B С Фь или B С Ф2, или B С ФЦ, или B С Ф£.

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