Синтез асимптотически оптимальных по надежности неветвящихся программ в базисе {x[1]vx[2], x[1]&x[2], x{-}[1], stop}
Рассматривается задача синтеза асимптотически оптимальных по надежности неветвящихся программ с условной остановкой, реализующих булевы функции, при инверсных неисправностях на выходах операторов в базисе {x[1]? x[2], x[1]&x[2], x{-}[1], stop}. Доказано, что в рассматриваемом базисе все булевы функции f (x[1], x[2],..., x[n]) можно реализовать асимптотически оптимальными по надежности программами с условной остановкой, причем для функций x[i] (i принадлежит множеству {1, 2,..., n}) эти программы являются абсолютно надежными (не содержат операторов), а для остальных функций эти программы функционируют с ненадежностью, асимптотически равной ? при ? > 0 (? - вероятность инверсной неисправности на выходе оператора).
Авторы
Тэги
Тематические рубрики
Предметные рубрики
В этом же номере:
Резюме по документу**
, С. М. Зиновьева
СИНТЕЗ АСИМПТОТИЧЕСКИ ОПТИМАЛЬНЫХ
ПО НАДЕЖНОСТИ НЕВЕТВЯЩИХСЯ ПРОГРАММ
В БАЗИСЕ {x1x2, x1x2, 1x , stop}1
Аннотация. <...> Рассматривается задача синтеза асимптотически оптимальных по
надежности неветвящихся программ с условной остановкой, реализующих булевы
функции, при инверсных неисправностях на выходах операторов в базисе
{x1x2, x1x2, 1x , stop}. <...> Доказано, что в рассматриваемом базисе все булевы
функции f(x1, x2,…, xn) можно реализовать асимптотически оптимальными по
надежности программами с условной остановкой, причем для функций xi
(i {1, 2, …, n}) эти программы являются абсолютно надежными (не содержат
операторов), а для остальных функций эти программы функционируют с ненадежностью,
асимптотически равной ε при ε 0 (ε – вероятность инверсной
неисправности на выходе оператора). <...> Предполагается, что все операторы –
конъюнкторы, дизъюнкторы, инверторы и операторы условной остановки –
независимо друг от друга с вероятностью ε (ε (0; 1/2)) подвержены инверсным
неисправностям на выходах. <...> В неисправном
состоянии оператор условной остановки вместо единицы выдает нуль. <...> Считаем,
что программа Pr реализует функцию f(x1, x2, …, xn), если она реализует
ее при отсутствии неисправностей. <...> Ненадежностью N(Pr) программы Pr назовем максимальную вероятность
ошибки на всех выходах программы Pr при всевозможных входных
наборах. <...> Математика
Ненадежностью N(S) схемы S из функциональных элементов, подверженных
инверсным неисправностям на выходах, назовем максимальную вероятность
ошибки на выходе схемы S при всевозможных входных наборах. <...> Для неветвящихся программ с надежным оператором условной остановки
доказана теорема 3 [3]. <...> Докажем теорему о нижней оценке ненадежности программ с надежным
оператором условной остановки. <...> Если в программе fPr вход
ни одного оператора условной остановки не соединен с выходом никакого
функционального оператора (т.е. либо операторов остановки нет, либо все
они соединены с полюсами), то хотя бы <...>
** - вычисляется автоматически, возможны погрешности
Похожие документы: