О надёжности схем в базисе из ненадёжных и абсолютно надёжных элементов

Тип работы:
Реферат
Предмет:
Общие и комплексные проблемы естественных и точных наук


Узнать стоимость новой

Детальная информация о работе

Выдержка из работы

УДК 519. 718
О НАДЁЖНОСТИ СХЕМ В БАЗИСЕ ИЗ НЕНАДЁЖНЫХ И АБСОЛЮТНО НАДЁЖНЫХ ЭЛЕМЕНТОВ1
М. А. Алехина, А. Е. Лакомкина
Рассматривается реализация булевых функций схемами в стандартном базисе, содержащем конъюнкцию, дизъюнкцию и инверсию. Предполагается, что некоторые из базисных элементов (например, конъюнктор) абсолютно надёжны, а остальные (инвертор и дизъюнктор)-ненадёжные, с вероятностью е € (0,½) подвержены инверсным неисправностям на выходах. Предполагается, что все ненадёжные элементы схемы переходят в неисправные состояния независимо друг от друга. Получены ответы на вопросы: какова ненадёжность схем, если некоторые из базисных элементов абсолютно надёжны, а другие ненадёжны?
Ключевые слова: ненадёжные и абсолютно надёжные функциональные элементы, надёжность и ненадёжность схемы, инверсные неисправности на выходах элементов.
Рассматривается реализация булевых функций схемами в стандартном базисе {х1& amp-х2,х1 Vх2, Х]_}. Предполагается, что некоторые из базисных элементов абсолютно надёжны, а остальные — ненадёжные, с вероятностью е € (0,½) подвержены инверсным неисправностям на выходах. Эти неисправности характеризуются тем, что в исправном состоянии базисный элемент реализует приписанную ему булеву функцию & lt-^, а в неисправном — функцию (/?. Считаем, что схема Б, содержащая ненадёжные элементы, реализует булеву функцию f (х1,…, хп), если при поступлении на входы схемы двоичного набора, а при отсутствии неисправностей в схеме Б на её выходе появляется значение f (а). Предполагается, что все ненадёжные элементы схемы переходят в неисправные состояния независимо друг от друга.
Впервые задачу синтеза надёжных схем из ненадёжных функциональных элементов рассматривал Дж. фон Нейман [1]. Он также предполагал, что все базисные элементы с вероятностью е € (0- ½) подвержены инверсным неисправностям на выходах и переходят в неисправные состояния независимо друг от друга. Дж. фон Нейман с помощью итерационного метода установил, что любую булеву функцию можно реализовать схемой, вероятность ошибки на выходе которой не больше се (с — положительная, зависящая от рассматриваемого базиса константа). Для повышения надёжности некоторой исходной схемы путём многократного дублирования он использовал схему, реализующую функцию голосования д (х^х2,х3) = х1×2 V х1×3 V х2×3.
Число Р (Б), равное максимальной вероятности ошибки на выходе схемы Б при всевозможных входных наборах схемы, назовем ненадёжностью схемы Б- надёжность схемы Б равна 1 — Р (Б).
С. В. Яблонский [2] рассматривал задачу синтеза надёжных схем в базисе {х1& amp-х2, х1 V х2, х1, ^(х1, х2, х3)}. Он предполагал, что элемент, реализующий функцию голосования д, абсолютно надёжный, а конъюнктор, дизъюнктор и инвертор — ненадёжные, подвержены произвольным неисправностям, ненадёжность каждого из них не больше е. Им доказано, что для любого р & gt- 0 существует алгоритм, который для каждой булевой функции f (х1,х2,…, хп) для любого п строит такую схему Б, что сложность схемы Ь (Б) & lt- 2п-1/п, а Р (Б) ^ р (т. е. ненадёжность схемы сколь угодно мала). Такие схемы называют схемами сколь угодно высокой надёжности.
хРабота поддержана грантом РФФИ, проект № 14−01−273.
В отличие от С. В. Яблонского, А. В. Васин [3] предполагал, что все элементы базиса |xi& amp-x2,xi V X2, Xi} ненадёжны, с вероятностью е подвержены инверсным неисправностям на выходах, и доказал, что любую функцию можно реализовать такой схемой S, что P (S) ^ 3е + 32е2 при всех е G (0,1/128].
В этой работе (в зависимости от того, какие базисные элементы ненадёжны) получены следующие результаты.
Теорема 1. Пусть конъюнктор и дизъюнктор абсолютно надёжны, а инвертор ненадёжный. Тогда любую функцию можно реализовать такой схемой S (k), что P (S) ^ 4(10е2)к при всех е G (0,1/128], k G N.
Из теоремы 1 следует, что любую функцию можно реализовать схемой сколь угодно высокой надёжности. Кроме того, любая неконстантная монотонная функция f G [x1& amp-x2,x1 V x2], т. е. может быть представлена в виде ДНФ, в которой нет отрицаний. Поэтому такую функцию f можно реализовать абсолютно надёжно.
Теорема 2. Пусть конъюнктор абсолютно надёжный, а инвертор и дизъюнктор ненадёжные- или дизъюнктор абсолютно надёжный, а инвертор и конъюнктор ненадёжные. Тогда любую функцию можно реализовать такой схемой S, что P (S) ^ е+10е2 при всех е G (0,1/128].
Теорема 3. Пусть инвертор абсолютно надёжный, а конъюнктор и дизъюнк-тор ненадёжные. Тогда любую функцию можно реализовать такой схемой S, что P (S) ^ 3е + 32е2 при всех е G (0,1/128].
Теорема 4. Пусть конъюнктор и инвертор абсолютно надёжные, а дизъюнктор ненадёжный- или дизъюнктор и инвертор абсолютно надёжные, а конъюнктор ненадёжный. Тогда любую функцию можно реализовать абсолютно надёжной схемой.
ЛИТЕРАТУРА
1. Von Neuman J. Probabilistic logics and the synthesis of reliable organisms from unreliable components // Automata Studies / eds. C. Shannon and J. McCarthy. Princeton, NJ: Princeton University Press, 1956. P. 329−378. (Рус. пер.: Автоматы. М.: ИЛ, 1956. С. 68−139.)
2. Яблонский С. В. Асимптотически наилучший метод синтеза надежных схем из ненадежных элементов // Banach Center. 1982. No. 7. P. 11−19.
3. Васин А. В. Об асимптотически оптимальных схемах в базисе {x& amp-y, x V y, X} при инверсных неисправностях на выходах элементов // Изв. вузов. Поволжский регион. Физикоматематические науки. 2008. № 4. С. 3−17.

Показать Свернуть
Заполнить форму текущей работой