О базисах, в которых асимптотически оптимальные схемы функционируют с ненадежностью 5[эпсилон]
Рассматривается реализация булевых функций схемами из ненадежных элементов в полном базисе B B[3] (B[3] - множество всех булевых функций, зависящих от переменных x[1], x[2], x[3]). Предполагается, что все элементы схемы независимо друг от друга с вероятностью [эпсилон] ([эпсилон] (0, 1/2) ) подвержены инверсным неисправностям на выходах. Найдены базисы, в которых почти булевы функции можно реализовать асимптотически оптимальными по надежности схемами, функционирующими с ненадежностью 5[эпсилон] при [эпсилон] [стремящемуся к] 0. Других таких базисов B B[3], в которых почти булевы функции можно реализовать асимптотически оптимальными по надежности схемами, функционирующими с ненадежностью 5[эпсилон], нет.
Авторы
Тэги
Тематические рубрики
Предметные рубрики
В этом же номере:
Резюме по документу**
А. В. Васин
О БАЗИСАХ, В КОТОРЫХ АСИМПТОТИЧЕСКИ
ОПТИМАЛЬНЫЕ СХЕМЫ ФУНКЦИОНИРУЮТ
С НЕНАДЕЖНОСТЬЮ 5
Аннотация. <...> Рассматривается реализация булевых функций схемами из ненадежных
элементов в полном базисе
BB 3 ( 3B – множество всех булевых
(0,1/ 2) ) подфункций,
зависящих от переменных 12 3,,x xx ). <...> Ключевые слова: ненадежные функциональные элементы, асимптотически оптимальные
по надежности схемы, инверсные неисправности на выходах элементов,
синтез схем из ненадежных элементов. <...> 1) каждому истоку (полюсу) приписана некоторая переменная, причем
разным истокам приписаны разные переменные (истоки при этом называются
входами схемы, а приписанные им переменные – входными переменными); <...> 64
k 1 дуг, приписана булева
функция из базиса B, существенно зависящая от k переменных (вершина
с приписанной функцией при этом называется функциональным элементом); <...> С. И. Аксеновым [1] получена верхняя оценка ненадежности схем
в произвольном полном конечном базисе при инверсных неисправностях на
выходах элементов. <...> Пусть в схеме, реализующей булеву функцию, отличную от константы,
выделена подсхема A, имеющая один вход, содержащая выход схемы. <...> Обозначим
через S подсхему, получаемую из схемы S удалением подсхемы A. <...> Если выполнено неравенство () ( )
PS P S
, то будем говорить, что схема S
надежнее схемы S и получается из S удалением подсхемы S . <...> Так как схема S реализует функцию, отличную от константы, схема A
реализует либо тождественную функцию, либо инверсию. <...> Схема S, реализующая функцию f, отличную от константы, является
bc-схемой, если из нее нельзя получить более надежную схему, реализующую
f или f , удалением подсхемы, реализующей тождественную функцию или
инверсию. <...> Если в схеме S можно выделить
связную подсхему A, функционирующую с ненадежностью
PA ,
() 5 (1 ) 4
состоящую хотя бы из пяти элементов, имеющую один вход и содержащую
выход схемы, то схема S не является bc-схемой. <...> Пусть A – связная подсхема схемы S, состоящая хотя бы из одного <...>
** - вычисляется автоматически, возможны погрешности
Похожие документы: