About basises whose unreliability coefficient equals 1.pdf Рассматривается реализация булевых функций схемами [1] из ненадёжных функциональных элементов в произвольном полном конечном базисе B. Предполагаем, что все элементы схемы независимо друг от друга с вероятностью е £ (0,1/2) подвержены инверсным неисправностям на выходах. Эти неисправности характеризуются тем, что в исправном состоянии функциональный элемент реализует приписанную ему булеву функцию ф, а в неисправном — функцию ф. Считаем, что схема S из ненадёжных элементов реализует булеву функцию f (xi, x2,..., xn), если при поступлении на входы схемы двоичного набора a = (a\, a2,... , an) при отсутствии неисправностей на выходе схемы S появляется значение f (a). Ненадёжностью P(S) схемы S назовем максимальную вероятность ошибки на выходе схемы S при всевозможных входных наборах схемы. Надёжность схемы S равна 1 —P(S). Пусть P£(f) = inf P(S), где инфимум берется по всем схемам S из ненадёжных элементов, реализующим булеву функцию /(xi ,x2,... ,xn). Схема A из ненадёжных элементов, реализующая функцию /, называется асимптотически оптимальной (асимптотически наилучшей) по надёжности, если P(A) — P£(/) при e ^ 0. Число к будем называть коэффициентом ненадёжности базиса, если все функции в этом базисе можно реализовать схемами с ненадёжностью, асимптотически не больше ke (при e ^ 0), и найдётся функция /, которую нельзя реализовать схемой с ненадёжностью, асимптотически меньше чем ke (при e ^ 0). Задача построения асимптотически оптимальных по надёжности схем при инверсных неисправностях на выходах элементов в полных базисах из трёхвходовых элементов решена в [2]. В этой работе найден широкий класс базисов, для которых к =1. Обозначим через K множество функций, для которых асимптотически оптимальные по надёжности схемы в базисе B функционируют с ненадёжностью, асимптотически равной ke (при e ^ 0), где к — коэффициент ненадёжности базиса B. Нетрудно проверить, что при инверсных неисправностях на выходах элементов в любом базисе ненадёжность любой схемы, содержащей хотя бы один элемент, не меньше e. Поэтому коэффициент ненадёжности любого базиса не меньше 1. Для реализации любой функции, отличной от xi (i = 1, 2,... , n), требуется не менее одного функционального элемента. Обозначим через K(n) множество булевых функ- |K (n)| ций K(n) = P2\{xi : i = 1,...,n}. Очевидно, что ——— ^ 1 при n ^ то. Тогда 22 оо в случае к =1 множество K равно K = Р| K (n). г=1 Замечание 1. Для любой булевой функции / Е K верно P£(/) ^ e. Опишем множество G функций ^(x1,... ,xr), обладающих свойством повышения надёжности. Пусть e1, e2,... , er Е {0,1}r, где вг — вектор, имеющий ровно одну ненулевую компоненту на i-м месте, i = 1, 2,...,r. Зададим множество Ek, состоящее из r векторов г—1 е1, е2,..., er Е {0,1}r, следующим образом: 1) ег = вг, i =1, 2,..., к; 2) ег = вг + Е Ayej, j=1 где Aj Е {0,1}, i = к + 1, к + 2,... , r. Пусть ^(x1, x2,... , xr) Е G0, если существуют такие двоичные наборы

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