Математика/4. Прикладная математика

Д. ф.-м.н., проф. Алехина М.А., аспирант Барсукова О.Ю.

Пензенский государственный университет, Россия

О НЕНАДЕЖНОСТИ СХЕМ ПРИ ИНВЕРСНЫХ НЕИСПРАВНОСТЯХ И ОТКАЗАХ ФУНКЦИОНАЛЬНЫХ ЭЛЕМЕНТОВ

Введем обозначения:

Функции из называют двузначными (или булевыми) функциями. Функции из называют частичными двузначными (булевыми) функциями, трактуя значение как неопределенность.

Пусть и . Тогда формула задает функцию , которая определяется как обычно с дополнительным условием: если существует такое, что , то (Ï{0, 1}).

Рассмотрим реализацию функций из схемами из ненадежных функциональных элементов в полном базисе ().

Будем считать, что схема из ненадежных элементов реализует функцию , если при поступлении на входы схемы набора при отсутствии неисправностей в схеме на ее выходе появляется значение . Предполагается, что все элементы схемы независимо друг от друга переходят в неисправные состояния двух типов. Неисправность первого типа появляется на любом входном наборе элемента с вероятностью δ (δ<1/2) и характеризуется тем, что на выходе элемента появляется значение , после чего работа схемы прекращается, а значение на ее выходе неопределено. Неисправность второго типа появляется на любом входном наборе (a₁, a₂) элемента с вероятностью 1–ε (ε<1/2) на выходе элемента появляется значение , с вероятностью ε на выходе элемента появляется значение (т.е. имеем инверсные неисправности на выходах элемента).

Пусть схема S реализует функцию . Обозначим через и соответственно вероятность отказа схемы S и вероятность появления (ошибки) на выходе схемы S при входном наборе , на котором . Очевидно, что не зависит ни от входного набора , ни от структуры схемы S, а зависит только от числа m элементов в схеме S: = 1-(1-δ)^m. Поэтому далее вместо будем писать , называя вероятность вероятностью отказа схемы S.

Ненадежностью схемы S будем называть число , где максимум берется по всем входным наборам схемы S.

Функционирование базисного элемента с функцией в соответствии с введенными неисправностями можно задать табл. 1, где – вероятности появления 0, 1, соответственно на выходе элемента .

Таблица 1

0 0	1
0 1	0
1 0	0
1 1	0

Теорема 1. Пусть – произвольная булева функция, пусть схема S реализует c ненадежностью P(S). Тогда функцию можно реализовать схемой c ненадежностью

.

Доказательство. Построим схему (рис.1).

Пусть – входной набор функции . Предварительно по формуле полной вероятности вычислим вероятности ошибок на выходе схемы В . Если набор такой, что , то

Если набор такой, что , то

В схеме В заменим обе схемы S на В. Построенную схему обозначим . Тогда для вероятностей ошибок на выходе схемы , учитывая полученные выше оценки, имеем:

если набор такой, что , то

Таким образом,

Если набор такой, что , то

Следовательно,

Так как , то

Теорема доказана.

Теорема 2. Пусть , то любую булеву функцию можно реализовать схемой , ненадежность которой .

Доказательство производится индукцией по числу существенных переменных функций. Индуктивный переход выполняется следующим образом: сначала строится схема , реализующая на основе разложения функции :

, тогда

, где - двойственная функция к .

причем функции и , согласно индуктивному предположению, можно реализовать схемами, ненадежность которых не больше .

Обозначим через А подсхему схемы S, выход которой является выходом схемы S, а на входы подаются значения , и . Поскольку выделенная подсхема А состоит из четырех элементов, то ее ненадежность .

Если схема А исправна, то для реализации функции она использует выходное значение одной из схем, реализующих функции и , в зависимости от значения . Поэтому .

Уменьшим ненадежность схемы S,используя схему (см. теорему 1). Имеем

Поскольку , получаем

.

При справедливы неравенства

Поэтому , схема - искомая схема.Теорема доказана.

Теорема 3. Пусть , то любую булеву функцию можно реализовать схемой , ненадежность которой .

Доказательство. По теореме 2 любую булеву функцию можно реализовать схемой S с ненадежность . По схеме S построим схему и оценим ее ненадежность:

Теорема доказана.

Таким образом, представленный метод позволяет строить схемы, ненадежность которых меньше, чем ненадежность исходных схем.

К сожалению, при этом возрастает вероятность отказа схемы: для имеем , где - число элементов исходной схемы S.

Исследование выполнено при финансовой поддержке РФФИ, проекты 11-01-00212а , 12-01-31340.

Список литературы

1. Алехина М.А. Синтез асимптотически оптимальных по надежности схем. – Пенза: Информац.-издат.центр ПГУ, 2006.

2. Алексеев В. Б., Вороненко Л. Л.  О некоторых замкнутых классах в частичной двузначной логике. Дискретная математика, 1994, том 6, выпуск 4,С. 58–79 .