А. В. Васин
О БАЗИСАХ, В КОТОРЫХ АСИМПТОТИЧЕСКИ
ОПТИМАЛЬНЫЕ СХЕМЫ ФУНКЦИОНИРУЮТ
С НЕНАДЕЖНОСТЬЮ 5
Аннотация. <...> Рассматривается реализация булевых функций схемами из ненадежных элементов в полном базисе B B3 ( B3 – множество всех булевых
функций, зависящих от переменных x1, x2 , x3 ). <...> Предполагается, что все элементы схемы независимо друг от друга с вероятностью ( (0,1/ 2) ) подвержены инверсным неисправностям на выходах. <...> Найдены базисы, в которых
почти булевы функции можно реализовать асимптотически оптимальными по
надежности схемами, функционирующими с ненадежностью 5 при 0 . <...> Ключевые слова: ненадежные функциональные элементы, асимптотически оптимальные по надежности схемы, инверсные неисправности на выходах элементов, синтез схем из ненадежных элементов. <...> We consider realization of Boolean functions by circuits composed of unreliable functional elements in some complete finite basis B B3 ( B3 is the set of
all Boolean functions of three variables x1, x2, and x3). <...> Схемой из функциональных элементов в базисе B будем называть
ациклический упорядоченный орграф, в котором: <...> 1) каждому истоку (полюсу) приписана некоторая переменная, причем
разным истокам приписаны разные переменные (истоки при этом называются
входами схемы, а приписанные им переменные – входными переменными); <...> 2) каждой вершине, в которую входят k 1 дуг, приписана булева
функция из базиса B, существенно зависящая от k переменных (вершина
с приписанной функцией при этом называется функциональным элементом); <...> Глубиной схемы будем называть длину максимального пути в ней. <...> Глубиной функционального элемента схемы будем называть длину максимального пути между ним и выходным элементом схемы. <...> Слоем глубины k (или k -м слоем) назовем множество всех функциональных элементов схемы глубины k . <...> Математика
Заметим, что из определения схемы следует, что функциональные элементы, реализующие константы, не имеют входов. <...> Предполагается, что все элементы схемы переходят в неисправные состояния независимо друг от друга с вероятностью (0 <...>