Об асимптотически оптимальных По надежности схемах в некоторых специальных базисах

Тип работы:
Реферат
Предмет:
Кибернетика


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

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

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

МАТЕМАТИКА
УДК 519. 718
М. А. Алехина, Д. М. Клянчина
ОБ АСИМПТОТИЧЕСКИ ОПТИМАЛЬНЫХ ПО НАДЕЖНОСТИ СХЕМАХ В НЕКОТОРЫХ СПЕЦИАЛЬНЫХ БАЗИСАХ1
Аннотация. Рассматривается реализация булевых функций схемами из ненадежных функциональных элементов в полном конечном базисе B, содержащем специальные функции. Предполагается, что все элементы схемы независимо друг от друга с вероятностью е е (0,½) подвержены неисправностям типа 0 на выходах. Доказано, что почти для всех булевых функций асимптотически оптимальные по надежности схемы функционируют с ненадежностью, асимптотически равной е при е ^ 0. Эта оценка ненадежности в два раза меньше, чем в случае инверсных неисправностей на выходах элементов в соответствующих базисах.
Ключевые слова: булевы функции, функциональные элементы, асимптотически оптимальный, надежность.
Abstract. An article examines an implementation of the Boolean functions in the circuits with unreliable functional elements in complete finite B basic sets, containing special functions. It is assumed that all the circuit elements irrespective of each other are subject to 0 type failures at the outputs with the probability е е (0,½). The article proves that the circuits with asymptotically optimum reliability implement Boolean functions with the value of unreliability being equal е when е^-0. The present value of unreliability is twice lower in comparison with inverse failures at the outputs of the relevant basic sets' elements.
Keywords: Boolean functions, functional elements, asymptotically optimum reliability.
Введение
Введем множества булевых функций:
M1 = { x1 (v X3),) (v X3), x1 (v X3),) v X2X3, X1 v x2X3, X1 v x2X3 }-
M2 = { (v X2 jx v X2 v X3), (X1 vX2)(vX2 vX3 j,
(X1 v X2)(v X2 v X3), (v X2 v X3)& amp- (v X2 v X3)& amp- & amp- (v X? v X3),
(1 v X2 v X3) (v X2 v X3) (v X2 v X3) }-M3 = {(xi v X2)(x1 v X2 v X3)}.
Рассмотрим реализацию булевых функций схемами из ненадежных функциональных элементов [1] в полном конечном базисе B, содержащем некоторую функцию из множества M = MinM2nM3. Считаем, что схема реали-
1 Работа выполнена при финансовой поддержке РГНФ, номер проекта 09−06−28 615а/В.
зует функцию /(, Х2,…, хп), если при поступлении на входы схемы набора, а = (,°2,.., ап) при отсутствии неисправностей на выходе схемы появляется значение / (а). Допустим, что все элементы схемы независимо друг от
друга с вероятностью е (ее (0,½)) переходят в неисправные состояния типа 0 на выходах. Эти неисправности характеризуются тем, что в исправном состоянии функциональный элемент реализует приписанную ему булеву функцию, а в неисправном — константу 0.
Пусть (& amp-, а) — вероятность появления /(а) на выходе схемы S,
реализующей булеву функцию /(Х), при входном наборе а. Ненадежность Р (5) схемы & amp- определяется как максимальное из чисел (& amp-, а) при всевозможных входных наборах а. Надежность схемы & amp- равна (1 — Р (5)).
Пусть Ре (/) = т? Р (& amp-), где & amp- - схема из ненадежных элементов, реализующая булеву функцию /. Схему, А из ненадежных элементов, реализующую булеву функцию /, назовем асимптотически оптимальной по на,, ,, Р (А)
дежности, если Р (А)~Ре (/) при е0, т. е. Пт---^ = 1.
е^° Ре (/)
Пусть В3 — множество всех булевых функций, зависящих от трех переменных х1, х2, х3.
В работе [2] введены множества функций G1, G2, G3, G4, где G1 — множество функций, конгруэнтных функциям ха ха V ха Хз°3 V ха Хз°3- G2 -множество булевых функций, зависящих от переменных х1, х2, х3 и конгруэнтных функциям ха ха © хз°3, аг- е{0,1}, г е{ 1,2,3} - G3 — множество функций,
конгруэнтных функциям ха1 ха2 V ха2 хзаз, а г е {0,1}, г е {1,2,3} - G4 — множество функций, зависящих от переменных х1, х2, х3, х4 и конгруэнтных функциям ха1 ха2 V ха3 ха4 или (ха1 V ха2х ха3 V ха4), где, а е{0,1}, г е{ 1,2,3,4}.
Обозначим G = G1nG2nG3 (|G| = 56). В случае инверсных неисправностей на выходах элементов доказано [2], что если полный конечный базис В содержит некоторую функцию множества G, то любую функцию / в этом базисе В можно реализовать схемой, А с ненадежностью Р (А) & lt- е + 200е2 при всех ее (0,1/960]. Последнее утверждение верно и в случае неисправностей типа 0 на выходах элементов [3−5]. Учитывая, что при неисправностях типа 0 на выходах элементов любая схема, содержащая хотя бы один функциональный элемент и реализующая отличную от константы 0 функцию, имеет ненадежность не менее е [3], получаем следующий результат: если полный конечный базис В содержит некоторую функцию множества G, то для почти всех функций асимптотически оптимальные по надежности схемы функционируют с ненадежностью, асимптотически равной е при е ^ 0. Это свойство базиса будем называть е-свойством.
Множество G является критериальным (исчерпывающим) [2], если базис В содержит только функции трех переменных, т. е. В с В3, а его элементы подвержены инверсным неисправностям на выходах. В работе [6] доказано,
что функции множества О не являются исчерпывающими, если базис В с В3, а базисные элементы подвержены неисправностям типа 0 на выходах. В работе [6] найдено такое множество М * функций трех переменных, что если полный конечный базис В содержит некоторую функцию множества М *, то базис В обладает е-свойством. Ответ на вопрос «Является ли множество М * пО исчерпывающим, если полный конечный базис В с В3, а его элементы подвержены неисправностям типа 0 на выходах?» получен в этой работе. Ответ отрицательный, далее будет доказано, что множество О не является исчерпывающим в случае неисправностей типа 0 на выходах элементов и В с В3.
Функции множества М исследовал А. В. Васин [7]. Для инверсных неисправностей на выходах элементов он доказал, что:
1) если полный конечный базис В содержит некоторую функцию множества М, то любую функцию / в этом базисе можно реализовать схемой, А с ненадежностью Р (А) & lt- 2е + 204е2 при всех е є (0,1/960]-
2) если базис В с В3О и ВиМФ 0, то в базисе В почти для всех функций асимптотически оптимальные по надежности схемы функционируют с ненадежностью, асимптотически равной 2е при е ^ 0. Эта асимптотическая оценка ненадежности в два раза хуже аналогичной оценки при неисправностях типа 0 на выходах элементов, полученной в этой работе.
Вспомогательные ранее известные результаты
Обозначим через /а функцию /, если ст = 1, и функцию /, если
ст = 0, а схему, реализующую функцию /а (ає {0,1}), будем обозначать? а.
Пусть схема? я реализует функцию g є О4 (напомним, что
g = ха ха V ха х?4, или g = (ха V х2)(ха V х^), а* є {0,1}, іє {1, 2, 3, 4}).
Возьмем схему? а'-, реализующую функцию /, схему? а2, реализующую функцию /°2, схему? а3, реализующую функцию /°3, и схему? а4, реализующую функцию /°4. Используя схемы? г, ?, ?°2, ?°3 и ?°4, построим схему (рис. 1), которую также обозначим Ф (?, 5°). Нетрудно проверить, что и в этом случае схема Ф (?, ?0) реализует функцию / Всюду далее схему ?1 будем обозначать ?.
Пусть схема Sg реализует функцию g є Оі (т.е. функция g имеет вид
g = хах2°2 V х1 х3 V х^2х3, аі є {0,1}, і є {1, 2, 3}). Возьмем схему ?°1, реализующую функцию /а1, схему ?°2, реализующую функцию /°2, и схему ?°3, реализующую функцию /°3. Используя схемы? я, ?а1, ?°2 и
?°3, построим схему Ф (?0, ?1) (рис. 2). Нетрудно проверить, что схема Ф (?", ?1) реализует функцию /
Операция Ф (рис. 1, 2) по схемам? и ?0, реализующим булевы функции /и / соответственно, строит схему Ф (?, ?0), реализующую функцию/ Результат п -кратного применения (п є N) операции Ф к схемам? и? будем обозначать Фп (?, ?0). Применение операции Ф к некоторым схемам? и? при некоторых условиях на их ненадежности Р (?) и Р (?0) приводит к схемам,
имеющим более высокую надежность, чем исходная схема ?. В том случае, когда операция Ф применяется только к схемам? (т.е. когда все числа Сі = 1), результат ее применения будем обозначать Ф (?). Если же операция Ф применяется только к схемам? (т.е. когда все числа ^ = 0), результат ее применения будем обозначать Ф (?0).
Рис. 1
Рис. 2
Лемма 1 [3]. Допустим, что произвольную функцию /можно реализо-
вать схемой? с ненадежностью не больше р (р & lt- ½). Пусть? — схема, лизующая функцию g є О1 и О4 с ненадежностью Р (?ё) (Р (?8) & lt- ½), причем
у0 и у1 — вероятности ошибок схемы? ё на наборах (с^, а2, 03,04) и
02,03,04) соответственно, если g зависит от четырех переменных, и
на наборах (а, а2, 03) и (а, О2,03) соответственно, если g зависит от
трех переменных. Тогда схема Ф (?, ?0) реализует функцию / с ненадежностью
Р (Ф (?, ?0)) & lt- шах{у0, ^} + 4р • Р?) + 6р2, если g є О4 (рис. 1),
Р (Ф (?, ?0)) & lt- шах{у0, ^} + 3р • P (?g) + 3р2, если gє О1 (рис. 2).
Лемма 2 [8]. В произвольном полном конечном базисе В любую булеву функцию /можно реализовать такой схемой ?, что при всех е є (0, 1/960] ее ненадежность Р (?) & lt- 5,2е.
Лемма 3 [6]. Пусть схема? ь реализует функцию Н (х1,х2,х3) =
= хС1 хС2 © х3С3, аі є {0,1}, і є {1,2,3} с ненадежностью Р (?и), причем w1 -вероятности ошибок схемы? на наборах (С1, О2, 0), (О1, О2, 1). Тогда можно построить такую схему ?8, реализующую функцию g (х1,х2,х3) =
= (х1 х^ V х1×3 V х2×3)°3, что P (?g) & lt- Р (?ъ) + 2 р© (р (c) — максимальная из ненадежностей схем, реализующих функции х1 © х2 и х1 © х2 © 1 в рассматриваемом базисе), а для вероятностей ошибок у1 и у0 схемы? на наборах
2
(0,0,0) и (1,1,1) выполняются нераєенс^тєа: У1, У0 & lt-ш. ах{^0, ^1} + 2 р©.
и
Основные результаты Лемма 4. Пусть ф (х1,х2,х3) є М1иВ, тогда в базисе В функцию g є О4 можно реализовать такой схемой? что при єє(0−½) ее ненадежность Р?) & lt- 2є, а вероятности ошибок у0 и у1 схемы? g на наборах
(а, а2,03,а4) и (, а2, С3,04) соответственно удовлетворяют неравенствам у0 & lt- е и у1 & lt- е.
Доказательство. Пусть базис В содержит функцию из множества М1. Возможны следующие варианты:
1. ф (, х2, х3) = х1 (2 V х3), тогда из нее подстановкой ^ вместо х1 и
подстановкой 22 вместо х2 и х3 получим функцию Ф1 = ^12. Тогда g =ф (Ф1 (ъг2), х2, х3) = (V ^2)(х V х3)є О4, причем а1 = 1, а2 = 1, а3 = 0, а4 = 0. Схему из двух элементов, реализующую функцию g, обозначим? g. Вычислим вероятность ошибки у0 на выходе схемы? g на наборе
(1, а2, а3, а4)=(1, 1, 0, 0) и получим у0 = ?. Вычислим вероятность ошибки у1 на выходе схемы? g на наборе (1, а2, С3, а4)=(0, 0, 1, 1) и получим У1 = 0.
2. ф (, х2, х3) = х (х2 V х3), тогда из нее подстановкой 21 вместо х1 и подстановкой 22 вместо х2 и х3 получим функцию Ф1 = 22. Тогда g =ф (Ф1 (21,22), х2, х3) = (21 V 22)(^2 V х3) є О4, причем а1 = 1, а2 = 1, а3 = 0, а4 = 1. Схему из двух элементов, реализующую функцию g, обозначим? g. Вычислим вероятность ошибки у0 на выходе схемы? g на наборе
(1, а2, а3, а4)=(1, 1, 0, 1) и получим У0 = є. Вычислим вероятность ошибки у1 на выходе схемы? g на наборе (1, а2, а3, а4)=(0, 0, 1, 0) и получим
у1 = 0.
3. ф (, х2, х3) = х ((2 V х3), тогда из нее подстановкой 21 вместо х1 и х3, подстановкой 22 вместо х2 получим функцию Ф2 = 2122. Тогда g = Ф (Ф2 (21,22), х2, х3) = (21 V 22)(^2 V х3), причем а1 = 1, а2 = 1, а3 = 0, а4 = 1. Схему из двух элементов, реализующую функцию g, обозначим? g. Вычислим вероятность ошибки у0 на выходе схемы? g на наборе (1, а2, а3, а4)=(1, 1, 0, 1) и получим У0 = ?. Вычислим вероятность ошибки у1 на выходе схемы? g на наборе (1, а2, С3, а4)=(0, 0, 1, 0) и получим
у1 = 0.
Функция х (х2 V х3) конгруэнтна функции ф (х1, х2, х3) = х ((2 V х3), рассмотренной в п. 3, следовательно, для нее утверждение леммы верно.
4. ф (, х2, х3) = х V %2×3, тогда из нее подстановкой 21 вместо х1 и
подстановкой 22 вместо х2 и х3 получим Ф1 = 2 V 22. Тогда
g = ф ((21,22), х2, х3) = 2122 V х2×3 є 04, причем а1 = 1, а2 = 1, а3 = 0, а4 = 0. Схему из двух элементов, реализующую функцию g, обозначим? g. Вычислим вероятность ошибки у0 на выходе схемы? g на наборе
(1, а2, а3, а4) =(1, 1, 0, 0) и получим у0 = ?. Вычислим вероятность ошибки у1 на выходе схемы? g на наборе (1, О2, С3, а4) = (0, 0, 1, 1) и получим у =? .
5. ф (, х2, х3) = х V х2×3, тогда из нее подстановкой 21 вместо х1 и подстановкой 22 вместо х2 и х3 получим Ф1 = 21V 22. Тогда
g = ф (Ф1 (21,22), х2, х3) = 2122 V х2×3 є О4, причем а1 = 1, а2 = 0, а3 = 1,
а4 = 1. Схему из двух элементов, реализующую функцию g, обозначим? g. Вычислим вероятность ошибки у0 на выходе схемы? g на наборе
(1, а2, а3, а4) = (1, 0, 1, 1) и получим у0 = ?. Вычислим вероятность ошибки у1 на выходе схемы? g на наборе (1, О2, О3, О4)=(0, 1, 0, 0) и получим у =? .
6. ф (, х2, х3) = х V %2×3, тогда из нее подстановкой 21 вместо х1 и
х3, подстановкой 22 вместо х2 получим функцию Ф2 = 21V 22. Тогда g =ф (Ф2 (21,22), х2, х3) = 2122 VX2х3 є О4, причем а1 = 1, а2 = 1, а3 = 0,
а4 = 1. Схему из двух элементов, реализующую функцию g, обозначим? g. Вычислим вероятность ошибки у0 на выходе схемы? g на наборе
(1, а2, а3, а4) =(1, 1, 0, 1) и получим у0 =?. Вычислим вероятность ошибки у1 на выходе схемы? g на наборе (1, О2, О3, О4)=(0, 0, 1, 0) и получим у =? .
Отметим, что функция х V х2×3 конгруэнтна функции х V х2×3, рассмотренной в п. 6, следовательно, для нее утверждение леммы верно.
Лемма 4 доказана.
Теорема 1. Пусть полный конечный базис В содержит функцию фє М1. Тогда любую булеву функцию/в базисе В можно реализовать такой схемой А, что при всех е є (0, 1/960] верно неравенство Р (А) & lt- е+15е2.
Доказательство. Пусть ф (х1, х2, х3) єМ1иВ. По лемме 4 функцию
gЄ О4 (т.е. g = хС1 х2 V х3 х4 или g = (хС1 V хС2)(хС3 V х4), Оі є {0,1}, іє {1, 2, 3, 4}) в базисе В можно реализовать такой схемой? я, что Р (?я) & lt- 2е, а вероятности ошибок у0 и у1 на наборах (1,02,03,04) и (1,02,03,04) удовлетворяют неравенствам у0 & lt-?, у1 & lt-?. Следовательно, шах{у0, у1}& lt- ?.
Пусть /- произвольная булева функция. По лемме 2 функции /и / можно так реализовать схемами? и? соответственно, что Р (?) & lt- 5,2е и
Р (?")& lt- 5,2е. Используя схему? я, а также схемы ?01, ?°2, ?°3 и ?°4, построим схему Ф (?, ?0), реализующую функцию/(рис. 1). По лемме 1 оценим
ненадежность построенной схемы Ф (?, ?0), полагая р = 5,2е. Получаем неравенство
Р (Ф (?, ?0)) & lt- шах{у0, у1} + 4р • Р (?я) + 6р2 & lt- є + 4 • 5,2е • 2е + 6 • (5,2е)2 & lt-
& lt- е + 204е2 & lt- 1,3е при? є (0−1/960].
По схеме Ф (?, ?0) построим схему Ф2(?, ?0) и снова применим лемму 1 для оценки ненадежности схемы Ф2(?, ?0), полагая р = 1,3е. Получаем неравенство
Р (Ф2(?, ?)) & lt- шах{у0, у1} + 4р • P (?g) + 6р2 & lt- е + 4 • 1,2е • 2е + 6 • (1,2е)2 & lt-
& lt- е + 19е2 & lt- 1,02е при? є (0- 1/960].
По схеме Ф2(?, ?0) построим схему Ф3(?, ?0) и по лемме 1 оценим ненадежность схемы Ф3(?, ?0), полагаяр = 1,02е:
Р (Ф3(?, ?0)) & lt- шах{у0, у1} + 4р • P (?g) + 6р 2 & lt-
& lt- е + 4 • 1,02е• 2е + 6 • (1,02е)2 & lt- е+15е2.
Схема Ф3(?, ?0) = А — искомая.
Теорема 1 доказана.
Лемма 5. Пусть ф (х1,х2,х3)є М2иВ, тогда в базисе В функцию Нє02
(т.е. Н (х1,х2,х3) = хО1×02 © х03, Оі є {0,1},іє{1, 2, 3}) можно реализовать
такой схемой? Н что Р (?Н) & lt- 2е, а вероятности ошибок0, w1 на выходе схемы? и на наборах (01,02,1), (01,02,0) соотвественно удовлетворяют неравенствам & lt- е, w1 & lt- е.
Доказательство. Проверим верность леммы для функций множестваМ2.
1. Пусть ф (х1,х2,х3) = (х1 V х2)((V х? V Ї3). Тогда Н (х1,х2,х3) =
= ф (ф (х1,х1,х2), х3, х3) = х^ © х3, т. е. о1 = 1, о2 = 0, о3 = 1. Поскольку для реализации функции Н двух элементов достаточно, верно неравенство Р (?Н) & lt- 2е. Вычислим вероятность ошибки на выходе схемы? Н на наборе (01,02,1) = = (0,1,1) и получим0 = е. Вычислим вероятность ошибки w1 на выходе схемы? Н на наборе (01,02,0) = (0,1,0) и получим w1 = 0.
2. Пусть ф (х1,х2,х3)= (21 V х?)(V х2 V х3). Тогда Н (х1,х2,х3) =
= ф (ф (х1,х2, х1), х3, х1) = х1×2 © х3, т. е. о1 = 1, о2 = 1, о3 = 0. Поскольку для реализации функции Н двух элементов достаточно, верно неравенство Р (?Н) & lt- 2е. Вычислим вероятность ошибки на выходе схемы? Н на наборе (01,02,1) = = (0,0,1) и получим0 = е. Вычислим вероятность ошибки w1 на выходе схемы? Н на наборе (01,02,0) = (0,0,0) и получим w1 = е.
3. Пусть ф (х1,х2,х3) = ((V х2)(V х2 V х3). Тогда Н (х1,х2,х3) =
ф (ф (х1,х1,х2), х3, х3) = хх © х3, т. е. о1 = 0, о2 = 1, о3 = 1. Поскольку для реализации функции Н двух элементов достаточно, верно неравенство Р (?Н) & lt- 2е. Вычислим вероятность ошибки на выходе схемы? И на наборе (01,02,1) = = (1,0,1) и получим0 = е. Вычислим вероятность ошибки w1 на выходе схемы? Н на наборе (01,02,0) = (1,0,0) и получим w1 = 0.
4. Пусть ф (х1,х2,х3)= (х1 V х2 V х3)(V х2 V х3)(V х2 V х3). Тогда Н (х1,х2,х3) = ф (ф (х1,х1,х2), х1, х3) = хх © х3, т. е. о1 = 1, о2 = 0, о3 = 1. Поскольку для реализации функции Н двух элементов достаточно, верно неравенство Р (?Н) & lt- 2е. Вычислим вероятность ошибки0 на выходе схемы? Н на наборе (0Ь02,1) = (0,1,1) и получим0 = е. Вычислим вероятность ошибки w1 на выходе схемы? Н на наборе (01,02,0) = (0,1,0) и получим w1 = е.
5. Пусть ф (х1,х2,х3) = (V х2 V х3)((V х2 V Ї3)(V х2 V Ї3). Тогда Н (х1,х2,х3) = ф (ф (х1,х1,х2), х1, х3) = х1×2 © х3, т. е. о1 = 1, о2 = 1, о3 = 0. Поскольку для реализации функции Н двух элементов достаточно, верно неравенство Р (?Н) & lt- 2е. Вычислим вероятность ошибки0 на выходе схемы? Н на наборе (01,02,1) = (0,0,1) и получим0 = е. Вычислим вероятность ошибки w1 на выходе схемы? Н на наборе (01,02,0) = (0,0,0) и получим w1 = е.
Лемма 5 доказана.
Теорема 2. Пусть полный базис В содержит функцию ф (, х2, х3)є є М2. Тогда любую булеву функцию /в базисе В можно реализовать схемой, А так, что при всех еє (0, 1/960] верно неравенство Р (А) & lt- е + 100е2.
Доказательство. Пусть ф (х1, х2, х3) єМ2иВ. Применима лемма 5, согласно которой в базисе В некоторую функцию Нє 02, т. е. функцию вида Н (х1, х2, х3) = хС1×02 © х03, а і є {0,1}, іє{1, 2, 3}, можно реализовать такой схемой? Н, что Р (?Н) & lt- 2е, а вероятности ошибок0, w1 на выходе схемы? Н на наборах (01,02,1), (01,02,0) соотвественно удовлетворяют неравенствам0 & lt- е, w1 & lt- е.
По лемме 2 функции х1 © х2 и х1 © х2 © 1 можно реализовать схемами ?1 и ?2 соответственно так, что Р (?1) & lt- 5,2е и Р (?2) & lt- 5,2е. Следовательно, р© =шах{Р (?1), Р (?2)} & lt- 5,2е.
По лемме 3, используя схему? н, построим такую схему? g, реализующую функцию g (х1, х2, х3) — (х2 V х1×3 V х2×3) 3, что Р (?^ & lt- Р (?н) + 2 р© & lt-
& lt- 2е + 2 • 5,2е & lt- 12,4е, а для вероятностей ошибок у1 и у0 схемы? на наборах
2
(0,0,0) и (1,1,1) выполняются неравенства: у1, у0 & lt- шах{^0, ^1} + 2 р© & lt-
& lt- е + 2(5,2е)2 & lt- е + 54,1 е2 при еє (0, 1/960].
Пусть / - произвольная булева функция.
Если 03 = 1, то возьмем три экземпляра схемы ?, реализующей функцию / с ненадежностью Р (?) & lt- 5,2е (по лемме 2 это возможно), а также один экземпляр схемы? г и построим схему Ф (?) (рис. 2), реализующую функцию /. По лемме 1 оценим ненадежность построенной схемы Ф (?): Р (Ф (?)) & lt-
& lt- е + 54,1 е2 + 3 ¦ 5,2е ¦ 12,4е + 3 ¦ (5,2е)2 & lt- е +328,7е2 & lt- 1,35е при е є (0, 1/960]. По схеме Ф (?) построим схему Ф2(?). Применим лемму 1 и получим: Р (Ф2(?)) & lt-
& lt- е + 54,1 е2 + 3 ¦ 1,35е ¦ 12,4е +3-(1,35е)2 & lt- е + 110е2 & lt- 1,115е при е є (0, 1/960]. По схеме Ф2(?) построим схему Ф3(?). Применим лемму 1 и получим: Р (Ф3(?)) & lt- е + 54,1 е2 + 3 ¦ 1,115е ¦ 12,4е + 3 ¦ (1,115е)2 & lt- е + 100е2. Схема Ф3(?) = А — искомая.
Если 03 = 0, то возьмем три экземпляра схемы ?0, реализующей функцию / с ненадежностью Р (?0) & lt- 5,2е (по лемме 2 это возможно), а также
один экземпляр схемы? я и построим схему Ф (?0) (рис. 2), реализующую функцию /. По лемме 1 оценим ненадежность построенной схемы Ф (?0): Р (Ф (?0)) & lt- е + 54,1 е2 + 3 ¦ 5,2е ¦ 12,4е + 3 ¦ (5,2е)2 & lt- е + 328,7е2 & lt- 1,35е при е є (0, 1/960]. По схеме Ф (?0) построим схему Ф2(?0). Применим лемму 1 и получим: Р (Ф2(?0)) & lt- е + 54,1е2 + 3 ¦ 1,35е ¦ 12,4е + 3 ¦ (1,35е)2 & lt- е + 110е2 & lt-
& lt- 1,1 15е при е є (0, 1/960]. По схеме Ф2(?0) построим схему Ф3(?0). Применим лемму 1 и получим: Р (Ф3(?0)) & lt- е + 54,1е2 + 3 ¦ 1,115е ¦ 12,4е + 3 ¦ (1,115е)2 & lt-
& lt- е + 100е2. Схема Ф3(?0) = А — искомая.
Теорема 2 доказана.
Лемма 6. Пусть ф (х1,х2,х3)= (х1 V х2)(5с1 V х2 V х3) (т.е. ф (х1,х2,х3) є М3), содержится в базисе В, тогда в базисе В можно построить такую схему ?# реализующую функцию g (х1, х2, х3) = х1×2 V х1×3 V х2×3, что Р?) & lt- 4е, а вероятности ошибок у1 и у0 схемы? на наборах (0,0,0) и (1,1,1) равны: у1 = 0, у0 = е.
Доказательство. Пусть ф (х1, х2, х3) = (х1 V х2)((V х? V х3) содержится в базисе В. Тогда функция ф (ф (х2, х3, х2), х2, х1) = хх V х2×3 = т (х1, х2, х3)є О3, причем о1 = 1, о2 = 1, о3 = 1. Поскольку для реализации функции т двух элементов достаточно, верно неравенство Р (?т) & lt- 2е. Вычислим вероятность ошибки Р0(?т, (1,1,1)) схемы? т на наборе (1,1,1) и получим Р0(?т, (1,1,1)) = е. Вычислим вероятность ошибки Р1(?т, (0,0,0)) схемы? т на наборе (0,0,0) и получим Р1(?т, (0,0,0)) = 0.
Моделируя формулу т (, т (, х2, х3), х3), построим схему? г, состоящую из четырех элементов и реализующую функцию g (х1, х2, х3) =
= х1×2 V х1×3 V х2×3. Тогда Р?) & lt- 4е. Вычислим вероятность ошибки у1 схемы? на наборе (0,0,0) и получим у1 = 0. Вычислим вероятность ошибки у0 схемы ?8 на наборе (1,1,1) и получим у0 = е.
Лемма 6 доказана.
Теорема 3. Пусть полный базис В содержит функцию ф (, х2, х3)є М3. Тогда любую булеву функцию/в базисе В можно реализовать схемой, А так, что при всех е є (0, 1/960] верно неравенство Р (А) & lt-
& lt- е + 16е2.
Доказательство. Пусть ф (х1, х2, х3) = (21 V х2) (Зеї V х2 V х3) єМ3иВ.
Тогда по лемме 6 функцию g (х1, х2, х3) = х1×2 V х1×3 V х2×3 можно реализовать такой схемой? я, что Р?) & lt- 4е, а вероятности ошибок у1 и у0 схемы? на наборах (0,0,0) и (1,1,1) соответственно равны у1 = 0, у0 = е.
Пусть /- произвольная булева функция. Возьмем три экземпляра схемы ?, реализующей функцию / с ненадежностью Р (?) & lt- 5,2е (по лемме 2 это возможно), а также один экземпляр схемы? я и построим схему Ф (?) (рис. 2), реализующую функцию /. По лемме 1 оценим ненадежность построенной схемы Ф (?): Р (Ф (?)) & lt- е + 3 ¦ 4е ¦ 5,2е + 3 ¦ (5,2е)2 & lt- е + 143,5е2 & lt- 1,2е при е є (0, 1/960]. По схеме Ф (?) построим схему Ф2(?). По лемме 1 оценим ненадежность схемы Ф2(?) и получим Р (Ф2(?)) & lt- е + 3 ¦ 4е ¦ 1,2е + 3 ¦ (1,2е)2 & lt-
& lt- е + 18,72е2 & lt- 1,2е при е є (0, 1/960]. По схеме Ф2(?) построим схему Ф3(?).
По лемме 1 оценим ненадежность схемы Ф3(?) и получим. Р (Ф3(?)) & lt-8 + + 3 • 48 • 1,028 +3 • (1,028)2 & lt- 8 + 1682. Схема Ф3(?) = А — искомая.
Теорема 3 доказана.
Выводы
1. Если полный конечный базис В содержит функцию ф (, Х2, Х3) е М,
то любую булеву функцию /в базисе В можно реализовать схемой, А так, что при всех 8 е (0, 1/960] верно неравенство Р (А) & lt- 8 + 10 082.
2. При неисправностях типа 0 на выходах элементов функции множества Мобладают тем же свойством, что и функции множества М * п О, т. е. наличие их в полном конечном базисе В гарантирует реализацию почти всех булевых функций асимптотически оптимальными по надежности схемами, функционирующими с ненадежностью, асимптотически равной 8 при 8 ^ 0.
В заключение укажем известные [3−6] на момент написания статьи функции ф (х1,Х2,Х3) такие, что если полный конечный базис содержит
функцию ф, то он обладает 8-свойством.
Булевы функции Л и /2 назовем конгруэнтными, если одна из них может быть получена из другой заменой переменных (без отождествления). Пусть ХсВ3. Обозначим Со^г (Х) — множество всех функций, зависящих от переменных х1, х2, х3, каждая из которых конгруэнтна некоторой функции множества X. Например, Со^г{1, хь Х1& amp- х2}={1, хь х2, х3, Х1& amp-Х2, х2& amp-х3, Х1& amp-Х3}.
Обозначим О * = О п Congr{ М *} п Со^г{М):
О * =О1пО2пО3 и Сощг{ Х1Х2 V Х1Х2Х3, Х1Х2 V Х1Х2Х3, Х1Х2 V Х1Х2Х3,
Х1Х2 V Х1Х2 Х3, Х1Х2 Х3 V Х1Х2 Х3 V Х1Х2 Х3, Х1Х2 Х3 V ХХ Х3 V Х1Х2 Х3,
Х1Х2Х3 V Х1Х2Х3, Х1Х2Х3 V Х1Х2Х3, Х1 X V Х3), Х1 X V Х3 | ,
Х1 X V Х3),) V Х2 Х3, Х1 V Х2 Х3, Х1 V Х2 Х3, (Х1 V Х2)(3с1 V Х2 V Х3) ,
X X V Х2)(V Х2 V Х3), (V Х2)(V Х2 V Х3),
(V Х2 V Х3) (V Х2 V Х3) (V Х2 V Х3),
(V Х2)(V Х2 V Х3), ((V Х2 V Х3) (V Х2 V Х3) (1 V Х2 V Х3) },
| О * |= 116, в то время как |О| = 56.
Вопрос «Является ли множество О * исчерпывающим, если базис В с В3, а базисные элементы подвержены неисправностям типа 0 на выходах?» остается открытым.
Цель дальнейших исследований авторов — найти и описать все функции ф (х1, Х2, Х3), наличие которых в полном конечном базисе В гарантирует реализацию почти всех булевых функций асимптотически оптимальными по надежности схемами, функционирующими с ненадежностью, асимптотически равной 8 при 8 ^ 0.
Список литературы
1. Редькин, Н. П. Надежность и диагностика схем / Н. П. Редькин. — М.: Изд-во МГУ, 1992.
2. Алехина, М. А. О надежности схем в базисах, содержащих функции не более чем трех переменных / М. А. Алехина, А. В. Васин // Ученые записки Казанского государственного университета. — 2009. — Т. 151. — Кн. 2. — С. 25−35. — (Физикоматематические науки).
3. Алехина, М. А. Синтез асимптотически оптимальных по надежности схем / М. А. Алехина. — Пенза: Информац. -издат. центр ПГУ, 2006. — 156 с.
4. Алехина, М. А. О надежности схем в одном базисе / М. А. Алехина // Проблемы автоматизации и управления в технических системах: труды Междунар. конф. (г. Пенза, 20−23 октября 2009 г.). — Пенза: Изд-во ПГУ, 2009. — С. 43−44.
5. Пичугина, П. Г. Оптимальные схемы в специальном базисе / П. Г. Пичугина // Проблемы автоматизации и управления в технических системах: труды Междунар. конф. (г. Пенза, 20−23 октября 2009 г.). — Пенза: Изд-во ПГУ, 2009. -С. 82−85.
6. Алехина, М. А. Достаточные условия реализации булевых функций асимптотически оптимальными схемами с тривиальной оценкой ненадежности / М. А. Алехина, Д. М. Клянчина // Надежность и качество: труды Междунар. симпозиума (Пенза, 24−31 мая 2010 г.). — Пенза: Изд-во ПГУ, 2010. — Т. 1. — С. 229−232.
7. Васин, А. В. Необходимые и достаточные условия реализации булевых функций асимптотически оптимальными схемами с ненадежностью 2е / А. В. Васин // Дискретная математика и ее приложения: материалы X Международного семинара (г. Москва, 1−6 февраля 2010 г.). — М.: Изд-во мех. -мат. фак. МГУ, 2010. — С. 94−97.
8. Алехина, М. А. О надежности схем в базисах, содержащих медиану / М. А. Алехина // Дискретные модели в теории управляющих систем: труды VIII Междунар. конф. — М.: Издательский отдел ф-та ВМиК МГУ им. М. В. Ломоносова — МАКС Пресс, 2009. — С. 13−17.
Алехина Марина Анатольевна
доктор физико-математических наук, профессор, заведующая кафедрой дискретной математики, Пензенский государственный университет
E-mail: dm@pnzgu. ru
Клянчина Дарья Михайловна аспирант, Пензенский государственный университет
E-mail: dm@pnzgu. ru
Alekhina Marina Anatolyevna Doctor of physical and mathematical sciences, professor, head of sub-department of discrete mathematics,
Penza State University
Klyanchina Darya Mikhaylovna Postgraduate student,
Penza State University
УДК 519. 718 Алехина, М. А.
Об асимптотически оптимальных по надежности схемах в некоторых специальных базисах / М. А. Алехина, Д. М. Клянчина // Известия высших учебных заведений. Поволжский регион. Физико-математические науки. — 2010. — № 4 (16). — С. 3−13.

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