Содержание к диссертации
Введение
1. Некоторые свойства схем из ненадежных элементов 20
2. Верхние оценки ненадежности схем 31
2.1. Верхние оценки ненадежности схем из ненадежных элементов х/у 31
2.2. Верхние оценки ненадежности схем при неисправностях на выходах элементов 35
2.2.1. Базис {/} 36
2.2.2. Базис {|} 36
2.2.3. Базис {:Д,~} 37
2.2.4. Базис {-/>'} 37
2.2.5. Базис {->,/>} 38
2.2.6. Базис {&,"} 38
2.2.7. Базис {~,&,Є} 38
2.2.8. Базис ЬМ} 39
2.2.9. Базис {Є,&Д} 39
2.2.10. Базис {~,&,0} 39
2.2.11. Базис {-+/} 39
2.2.12. Базис {->,0} 40
2.2.13. Базис {->,ф} 40
2.2.14. Базис {V/} 40
2.2.15. Базис {~,V,0} 43
2.2.16. Базис {~,V,e} 45
2.2.17. Базис {,V,1} 46
2.2.18. Базис {&,V}~} 49
2.3. Верхние оценки ненадежности схем при неисправностях на входах элементов 50
2.3.1. Базис {/} 50
2.3.2. Базис {1} 50
2.3.3. Базис {/>,~} 51
2.3.4. Базис {/>,"} 51
2.3.5. Базис {-*,/>} 51
2.3.6. Базис {&,"} 52
2.3.7. Базис {~,&,Є} 52
2.3.8. Базис {^, 1} 53
2.3.9. Базис {Є,&,1} 53
2.3.10. Базис {~,&,0} 54
2.3.11. Базис {-»,-} 54
2.3.12. Базис {->,0} 55
2.3.13. Базис {->,ф} 55
2.3.14. Базис {V,-} 55
2.3.15. Базис {~,V,0} 59
2.3.16. Базис {~,V,e} 59
2.3.17. Базис {,V,1} 60
2.3.18. Базис {&, V,"} 61
3. Нижние оценки ненадежности схем 63
3.1. Нижние оценки ненадежности схем при неисправностях на выходах элементов 63
3.1.1. Базис {/} 63
3.1.2. Базис {1} 64
3.1.3. Базис {уА>~} 65
3.1.4. Базис {-ДГ} 66
3.1.5. Базис {-*,-/*} 67
3.1.6. Базис {&,"} 69
3.1.7. Базис {~,&,е} 72
3.1.8. Базис ЬМ} 72
3.1.9. Базис {Ф,&,1} 74
3.1.10. Базис {~,&,0} 74
3.1.11. Базис {—>,"} 74
3.1.12. Базис {->,0} 76
3.1.13. Базис {-*,0} 78
3.1.14. Базис {V,-} 80
3.1.15. Базис {~,V,0} 82
3.1.16. Базис {~,V,e} 84
3.1.17. Базис {Ф,У,1} 86
3.1.18. Базис {&,V,~} 86
3.2. Нижние оценки ненадежности схем при неисправностях на выходах элементов 87
3.2.1. Базис {/} 88
3.2.2. Базис {1} 88
3.2.3. Базис {т^,~} 89
3.2.4. Базис {-/>'} 90
3.2.5. Базис {->, -/>} 91
3.2.6. Базис {&,"} 92
3.2.7. Базис {~,&,ф} 93
3.2.8. Базис {/>, 1} 10
3.2.9. Базис {ф,&,1} 101
3.2.10. Базис {~, &, 0} 101
3.2.11. Базис {-,-} 104
3.2.12. Базис {-»,0} 105
3.2.13. Базис {-+, ф} 106
3.2.14. Базис {V,"} 107
3.2.15. Базис {~,V,0} 109
3.2.16. Базис {~, V, ф} 109
3.2.17. Базис {ф, V, 1} 110
3.2.18. Базис {&,V,~} 110
4. Сложность надежных схем 112
4.1. Синтез и сложность надежных схем из ненадежных элементов х/у 112
4.2. Сложность надежных схем при однотипных константных неисправностях на выходах элементов 117
4.2.1. Базис {/} 117
4.2.2. Базис {1} 118
4.2.3. Базис {-/>, ~} 120
4.2.4. Базис {у^/} 121
4.2.5. Базис {-», -/>} 122
4.2.6. Базис {&,"} 123
4.2.7. Базис {~,&,ф} 124
4.2.8. Базис {уМ} 125
4.2.9. Базис {ф,&,1} 126
4.2.10. Базис {~,&,0} 127
4.2.11. Базис {->,"} 128
4.2.12. Базис {->,0} 129
4.2.13. Базис {->,ф} 129
4.2.14. Базис {V,-} 130
4.2.15. Базис {~,V,0} 131
4.2.16. Базис {~, V, ф} 132
4.2.17. Базис {ф, V, 1} 132
4.2.18. Базис {&,V,-} 133
4.3. Сложность надежных схем при однотипных константных неисправностях на входах элементов 137
4.3.1. Базис {/} 137
4.3.2. Базис {1} 139
4.3.3. Базис {yi, ~} 140
4.3.4. Базис {TV} 141
4.3.5. Базис {-», />} 142
4.3.6. Базис {&,"} 143
4.3.7. Базис {~,&,е} 144
4.3.8. Базис ЬМ} 145
4.3.9. Базис {ф,&,1} 146
4.3.10. Базис {~,&,0} 147
4.3.11. Базис {—»,*} 148
4.3.12. Базис {-»,0} 150
4.3.13. Базис {-»,ф} 150
4.3.14. Базис {V/} 151
4.3.15. Базис {~,V,0} 152
4.3.16. Базис {~,V,0} 153
4.3.17. Базис {e,V,l} 154
4.3.18. Базис {&, V,"} 155
Приложение 160
- Верхние оценки ненадежности схем при неисправностях на выходах элементов
- Верхние оценки ненадежности схем при неисправностях на входах элементов
- Нижние оценки ненадежности схем при неисправностях на выходах элементов
- Сложность надежных схем при однотипных константных неисправностях на выходах элементов
Введение к работе
Настоящая работа относится к одному из важнейших разделов математической кибернетики - теории синтеза, надежности и сложности управляющих систем. Актуальность исследований в этой области обусловлена важностью многочисленных приложений, возникающих в различных разделах науки и техники.
К числу основных модельных объектов математической теории синтеза, сложности и надежности управляющих систем относятся схемы из ненадежных функциональных элементов, реализующие булевы функции. Проблема построения схем наилучших (асимптотически наилучших) по надежности из ненадежных элементов является одной из наиболее важных и в то же время трудных в теории надежности управляющих систем. Тем более значимым представляется ее решение с дополнительным требованием к сложности таких схем, которое состоит в том, чтобы сложность оптимальных (асимптотически оптимальных) по надежности схем по порядку равнялась сложности схем, построенных только из надежных элементов. Эта задача в предположении, что функциональные элементы подвержены однотипным константным неисправностям либо только на выходах, либо только на входах элементов, рассматривается в диссертации.
Исторически сложилось так, что сначала исследовались инверсные неисправности. Первые существенные математические результаты, касающиеся синтеза надежных схем из ненадежных элементов получил Дж. Нейман [42]. Он предполагал, что элементы подвержены инверсным неисправностям, когда функциональный элемент Е с приписанной ему булевой функцией е{х) в неисправном состоянии реализует ё(х). Эти же неисправности рассматривались затем в работах Р. Л. Добрушина, С. И. Ортюкова, Д. Улига и некоторых других авторов [30, 31,35,36,37,43,44], причем главное внимание уделялось сложности схем (задача синтеза схем, наилучших или асимптотически наилучших по надежности, не ставилась). Речь идет о реализации булевых функций схемами из ненадежных элементов в произвольном конечном базисе Б = {ei,... ,em}, т Є N [38]. Множество всех функциональных элементов ЕІ, функции которых Є{ принадлежат базису Б, будем также называть базисом Б [34]. Каждому элементу Е{ базиса приписано положительное число v(Ei) — вес данного элемента ЕІ. Сложность схемы S определяется как сумма весов всех входящих в нее элементов и обозначается L(S). Предполагается, что все элементы схемы независимо друг от друга с вероятностью є подвержены инверсным неисправностям. Пусть Pf/uJS,a) — вероятность появления значения /(а) на выходе схемы 5, реализующей булеву функцию /(5), при входном наборе a = (ai,...,an). Пусть P(S) — максимальное из чисел Pf(a)(S я) при всевозможных входных наборах а. Назовем величину P(S) ненадежностью схемы S. Вводится функция Шеннона LPi(n) = max mm L(S), f s где минимум берется по всем схемам S из ненадежных элементов, реализующим функцию /(жі, ...,жп) с ненадежностью P(S) р а максимум - по всем булевым функциям f от п переменных. Нетрудно проверить, что для любой схемы S, содержащей хотя бы один элемент, при є 1/2 верно неравенство P(S) є.
Пусть р = minv(Ei)/(n(Ei) — 1), где минимум берется по всем элементам ЕІ базиса, для которых п(ЕЇ) 1, а П(ЕІ) - число существенных переменных функции е,-, реализуемой элементом Е{, і = 1,2,...,771. Для схем, реализующих булевы функции и состоящих только из надежных элементов (т.е. є = 0,р = 0), О. Б. Лупанов [33] показал, что Lo,o(n) р2п/п.
Для построения надежных схем из ненадежных элементов, подверженных инверсным неисправностям с вероятностью є (0 є 1/6), Дж. Нейман [42] предложил итерационный метод реализации булевых функций. С помощью этого метода произвольную булеву функцию можно реализовать схемой, вероятность ошибки на выходе которой при любом входном наборе значений переменных не превосходит с - є (с - некоторая, зависящая лишь от базиса Б, константа), т. е. ненадежность схемы по порядку равна ненадежности одного элемента (такие схемы в теории надежности управляющих систем принято называть надежными). Сложность схемы с ростом числа итераций увеличивается экспоненциально.
Любой метод синтеза схем из ненадежных элементов характеризуется двумя важными параметрами: вероятностью ошибки на выходе схемы (ненадежностью) и сложностью схемы. Оптимизация этих величин, т. е. построение наилучших по надежности и (или) сложности схем - цель исследований в теории синтеза, надежности и сложности управляющих систем. Поэтому наряду со сложностью надежных схем, которой уделялось главное внимание в работах ряда авторов, важным представляется ответ на вопрос: какова максимальная надежность схем, построенных из ненадежных элементов, подверженных тем или иным неисправностям?
Задача синтеза схем, максимально высокой надежности, или схем, надежность которых близка к максимальной надежности, ни Дж. Нейманом, ни другими исследователями не рассматривалась.
С. И. Ортюков [36] показал, что асимптотика функции Шеннона сохраняется для схем из ненадежных элементов при степенном убывании вероятности сбоев с ростом п, а именно, если последовательности рп и єп таковы, что QLgen рп 1/2, 0 еп 1/2 и єп = о(1/п2), где Q 1, Lg - минимальная сложность схемы из надежных элементов в рассматриваемом базисе, реализующей функцию голосования д(жі,2?2 яз) =
ЖіЖ2 V Xl#3 V Ж2Ж3, то
Из результатов Н. Пиппенджера [43] следует, что при инверсных неисправностях с вероятностью ошибки є 1/200 любую булеву функцию от п переменных в базисе {&,V,"} можно реализовать такой схемой S, что P(S) 185, L(S) 170 - 2n/n.
СИ. Ортюкову [37] удалось заменить требование єп = о(1/п2) условием єп Єо, где єо - некоторая константа. Сформулируем полученный им результат: если 0 є Єо, д Я(є) Р 1/2, где q(e) = є+Зє2 + о(є2) при є — 0, то существует такая функция р{е) — р при є • — 0, что Lp,(n)Zp(e).2n/n.
Д. Улиг [44] для инверсных неисправностей с вероятностью ошибки не более є доказал, что для любых с, b (с, Ь 0) существует є {є1 Є (0,1/2)) такое, что при любом є, 0 є є , и любом р, (1 + Ь)єЬд р 1/2 (точнее при любом р, q(e)Lg р 1/2), выполнено соотношение Lp,(n)(l + c)p27n.
С. И. Ортюков и Д. Улиг для инверсных неисправностей нашли методы синтеза схем оптимальных по сложности схем, функционирующих с некоторым уровнем надежности.
Инверсные неисправности, о которых до сих пор шла речь, достаточно удобны для использования математического аппарата теории вероятностей. Однако реальные неисправности элементов более точно отражают другие математические модели неисправностей. Основной из них являются однотипные константные неисправности на выходах и на входах элементов.
Однотипные константные неисправности на выходах элементов впервые исследовались в кандидатской диссертации автора [4]. Там же впервые был получен ответ на вопрос о надежности асимптотически наилучших (по надежности) схем, построенных из ненадежных элементов. Тог да задачу построения схем, асимптотически наилучших по надежности, удалось решить лишь в четырех базисах из двухвходовых элементов.
Вопрос о возможности построения асимптотически наилучших по надежности схем в других базисах, а также при других неисправностях элементов (опять же-таки однотипных константных неисправностях, но уже на входах элементов) оставался открытым.
Прежде чем перейти к изложению материала настоящей диссертации, отметим еще две важные задачи из теории синтеза, надежности и сложности управляющих систем.
С. В. Яблонский [41] рассматривал задачу синтеза надежных схем для случая, когда наряду с ненадежными конъюнктором, дизъюнктором, инвертором (е - максимум вероятностей их повреждений, 0 є 1/2) базис Б содержит абсолютно надежный элемент, реализующий функцию голосования д(хі,Х2,хз) = х\Хч V х\х% V жг з Им доказано, что для любого р О существует алгоритм, который для каждой булевой функции /(хі,..., хп) строит схему S так, что P(S) р и L(S) 2п-1/п (сложность схемы здесь и далее - число функциональных элементов в ней).
Задача построения схем сколь угодно высокой надежности (когда P(S) - 0) рассматривалась В. В. Тарасовым [39]. Для базисов из ненадежных функциональных элементов с двумя входами и одним выходом выявлены необходимые и достаточные условия, при которых произвольные булевы функции можно реализовать схемами сколь угодно высокой надежности. Из полученных Тарасовым результатов для базисов из двухвходовых функциональных элементов следует невозможность построения сколь угодно надежных схем для произвольных функций как при инверсных неисправностях, так и при однотипных константных неисправностях, которые определены ниже.
В настоящей диссертации решается задача реализации булевых функций асимптотически наилучшими по надежности схемами во всех базисах из двухвходовых функциональных элементов при однотипных константных неисправностях только на выходах или только на входах элементов. Существенное внимание уделяется сложности схем. Введем необходимые понятия и определения.
Рассматривается реализация булевых функций схемами из ненадежных функциональных элементов в конечном базисе Б [38]. Схема реализует функцию /(xi,.. .,агп), если она реализует ее при отсутствии неисправностей в схеме. Предполагается, что каждый элемент схемы независимо от состояний других элементов может перейти в неисправное состояние.
Определим однотипные константные неисправности на выходах элементов и на входах элементов.
Если неисправность такова, что элемент (реализующий в исправном состоянии приписанную ему булеву функцию) в неисправном состоянии, в которое переходит с вероятностью 7 (т 1/2) j реализует константу 0, будем называть ее неисправностью типа 0 на выходе элемента. Если же элемент в неисправном состоянии реализует константу 1, будем называть эту неисправность неисправностью типа 1 на выходе элемента.
Если неисправность элемента такова, что поступающий на его вход нуль не искажается, а поступающая на его вход единица с вероятностью 7 (7 1/2) может превратиться в нуль, будем называть ее неисправностью типа 0 на входе элемента. Если же неисправность элемента такова, что поступающая на его вход единица не искажается, а - нуль с вероятностью 7 может превратиться в единицу, будем называть ее неисправностью типа 1 на входе элемента.
Ненадежность P(S) схемы 5, реализующей /(5), для указанных неисправностей определяется так же, как и для инверсных неисправностей, т. е.
P(5)=m#«P/(s)(S,a),
где Pf,d\(S,a) - вероятность появления значения /(а) на выходе схемы S при входном (произвольном) наборе а.
Надежность схемы равна 1 — P{S).
Обозначим P(f) = inf P(S), где S - схема из ненадежных элементов, реализующая булеву функцию /(жі,...,а;п).
Схему А из ненадежных элементов, реализующую булеву функцию /(), будем называть асимптотически наилучшей (асимптотически оптимальной) по надежности, если Р(А) P(f) при 7 — 0, т. е.
7-Ю Р(/)
Будем считать веса всех элементов равными единице, и тогда сложность L(S) схемы S - число функциональных элементов в ней. Введем базисы Si = {/},ft = Ш,.3 = {А, } 4 = {АЛ, Д = {- , А}, Д» = {&Л, Б7 = { ,&,Є}, 8 = {АД}, Бд = {Є,&,1}, щ = { ,&,0}, Бп ={- ,!, Бп = {-», }, Sis ={- ©}. Би = {V,"}, Б15 = { ,V,0}, Б16 = { , V,©}, Si7 = {e,V,l}. При перечислении базисов использованы обозначения: х/у = xV у, х 1у = х&су, х у = х&су V &у, х@у = х&у V х&2/, x —ї у = xV y x у = xSzy.
Известно, что любой другой базис в Рг, содержащий функции не более чем двух переменных, например, базис Бц = {&, V,"}, получается добавлением одной или нескольких функций к одному из базисов Б\ -Бц.
Впервые задача синтеза схем, обладающих асимптотически (по 7) наилучшей надежностью, рассматривалась и была решена в кандидатской диссертации [4] и статьях автора [1, 3, 5] лишь для четырех базисов f?i, і 2, Бь, Б\$ ПРИ однотипных константных неисправностях на выходах элементов. В дальнейших исследованиях автора выяснялись возможности построения асимптотически наилучших по надежности схем в других базисах, а также при других неисправностях элементов (опять же-таки однотипных константных неисправностях, но уже на входах элементов). Существенное внимание в этих исследованиях уделялось и сложности надежных схем. Ответы на вопросы "Какова цена (стоимость) реализации функции схемой, асимптотически оптимальной по надежности? Как увеличится сложность такой схемы по сравнению со сложностью схемы, построенной только из надежных элементов?" были также впервые получены в статье [2] и кандидатской диссертации [4] автора для четырех вышеназванных базисов. Оказалось, что построение асимптотически наилучших по надежности схем возможно со сложностью, по порядку равной сложности схем, построенных только из надежных элементов.
В настоящей диссертации задача синтеза схем, асимптотически наилучших по надежности, решена во всех базисах из двухвходовых функциональных элементов, за исключением 7, i g, 2 ю и I?i7, при однотипных константных неисправностях на выходах элементов, и во всех базисах из двухвходовых функциональных элементов, за исключением Бд, Z 13 И 1 17, при однотипных константных неисправностях на входах элементов.
Поскольку ненадежности двойственных схем равны (теорема 1.4, следствие 1.2), утверждения, доказанные в данном базисе Б для функции / при неисправностях типа 0 на выходах (входах) элементов, справедливы в двойственном базисе Б для двойственной функции / при неисправностях типа 1 на выходах (входах) элементов. Поэтому далее будем рассматривать только неисправности типа 0.
Пусть Б - один из базисов Б\ - Б\ъ, а в схемах возникают неисправности на выходах элементов.
Теорема 1. Если у с?, то любую булеву функцию /(xi, , хп) можно реализовать схемой S над Б, для которой P(S) ay + by2, L(S) с • 2n/n, где а, Ь, с, d - некоторые, зависящие лишь от базиса Б, константы, а Є {1,2,3,4}.
Оценки теоремы 1 установлены конструктивно, т. е. представлены методы синтеза схем 5, удовлетворяющих указанным оценкам по надежности и сложности.
Теорема 2. Базису Б можно сопоставить некоторый класс К булевых функций от переменных хі,... ,я?п и константы k, h такие, что для любой функции / из К и для любой схемы 5, реализующей /, при 7 т выполняется неравенство P(S) к у + hy2.
Отвечающие базисам Б\ — Б\$ константы а, Ь, с, dy к, Ті, ги классы К приведены в таблице 1. Константа г в некоторых случаях (их большинство) зависит лишь от базиса и типа неисправностей, а в других — еще и от схемы. В последнем случае соответствующее ей место в таблице содержит прочерк.
Таблица 1
Б a b с d У d к h r К
Бх = {/} 2 98 224 1/600 11 672 2 -3 1/4 K2 = {1} 1 98 224 1/600 4 672 1 0 1/2 Кг
з = {А } 1 122 448 1/600 6 1344 1 0 1/2 Кг
Б = {тМ 2 391 448 1/1200 12 1344 2 -3 1/4 K2
5 = {-»,7 } 2 392 448 1/1200 12 1344 2 — — Кг
Б6 = {&,"} 3 390 448 1/1200 22 1344 3 -9 1/8 к2
7 = { ,&,е} 3 390 672 1/1800 22 2016 1 0 1/2 Кг
8 = {/М} 3 880 672 1/1800 26 2016 3 -9 1/8 к2 = {Є,&,1} 3 966 672 1/1800 44 2016 1 0 1/2 Кг
ю = { ,&,0} 3 390 672 1/1200 22 2016 1 0 1/2 Кг
Би = {-,"} 2 476 448 1/1200 28 1344 2 -4 1/6 кА
5і2 = {- ,0} 2 476 672 1/1200 28 2016 2 -4 1/6 к2
із = {- ,0} 2 476 448 1/1200 28 1344 2 — — Кь = {V,l 2 506 448 1/1200 34 1344 2 — 1/4 к,
l5 = { ,V,0} 2 506 672 1/1200 34 2016 2 — — Кгг
i6 = { ,V,e} 2 506 672 1/1200 34 2016 2 — — Кгч
i7 = {e,V,l} 4 1137 672 1/1800 107 2016 1 0 1/2 Кг
18 = {&, v,l 1 7 40 1/125 — — 1 0 1/2 Кг
Установлено, что при неисправностях на выходах элементов для всех базисов Бг — i i8, исключая Бт,Б9,Бго и 17, константы а и к равны. Это свидетельствует о том, что соответствующие методы синтеза позволяют строить асимптотически (по 7) наилучшие по надежности схемы для почти всех булевых функций (при растущем п) в базисах Бг — Z 4, б -) 11» Бг2, Бг±—Бгъ и Бц со сложностью, по порядку равной слож ности схем, построенных только из надежных элементов, и для некоторых классов булевых функций в базисах Б$ и 2. Таким образом, из теорем 1 и 2 следует
Теорема 3. Схемы, построенные в теореме 1, являются асимптотически наилучіпими по надежности для почти всех функций в базисах Б\ — 2 4,1 б, 2 8 Бц, Біг, Би — 5іб и і і8 (сложность этих схем по порядку равна сложности схем, построенных только из надежных элементов) и для некоторых функций в базисах 2 и 2.
Константы Ьи сне являются единственной парой, для которой теорема 1 справедлива. Их можно заменить константами Ъ и V соответственно. Заметим, что "улучшая" одну из констант (например, Ь , что соответствует повышению надежности схемы), "ухудшаем" другую — с (увеличивая сложность схемы).
Опишим фигурирующие в таблицах 1 и 2 классы К\{п) — Kufo).
Щи) = Р2(п) \ ({о, 1} и (и?=1 «));•
i 2(n) = {/( 1,..., хп) : / нельзя представить в виде f = (х{кд(хи...,хп))а};
К3(п) = L(n) \ ({О,1} U (U?=1 х{) U (U?=1 а ));
К (п) = {/(жі,... ,жп) : /нельзя представить в виде / = (a? V a ,..., „))«};
Кь{п) — {f(xU "ixn) • /линейная функция, существенно зависящая не менее чем от трех переменных };
К&{п) = {/(xi,...,arn) : / нельзя представить в виде
/ = ( v... )•};.
Kj(n) = {/(а?і,... ,хп) : f нельзя представить в виде / = (z,-V#(a;i,...,ajn))0};
К8(п) = Р2(п) \ ({О,1} U (U?=1 ХІ) U (U?=1 ХІ));
Кд(п) = {/(a?i,....,a;n) : / нельзя представить ни в одном из видов
V xip V xin V ач, V V xipi V x{ V V ХІ,,. V xit V V x{j V V xipy
,=i 3 ,=i ,=i P=i p ,-=i. P=i p t=i j=i P=i p
iif10(n) = {/(яі,..., жп) :/ нельзя представить ни в виде / = х? Vp(jci,...,a;n), ни в виде / = аг» V p(arb... ,я„)};
-Кп(?г) = {/( i,. ..,ajn) :/ нельзя представить в виде / = ({xh Уіі) v...v{xik yik))a, где yim Є {ягга,0,1};
-Кіг(га) = {/(ЖЬ • • •» жп) : / нельзя представить в виде / = (( - ) .. ( -Уі У, где уіт Є{хіті0,1}.
Используемые обозначения имеют следующий смысл: / - булева функция от п переменных x\t..., хп] Р2{п) {L(n)) - множество всех (соответственно всех линейных) булевых функций от п переменных; g - произвольная булева функция от п переменных; z\j\/,s,г,iijijfe, г,-, г7 2р г Є
{1,..., n}; a, ai,..., сц - булевы константы.
При достаточно больших п классы К\(п) — К п), исключая Кз{п) и Кь{п), содержат почти все булевы функции.
Пусть теперь Б — опять же один из базисов Бг — 1 і8, но в схемах возникают однотипные константные неисправности на входах элементов.
Теорема 4. Если 7 d, то любую булеву функцию /(a?i,..., хп) можно реализовать схемой S над 2 , для которой P(S) ay + ЬУ+1» L(5) с • 2n/n, где a,. b, с, d, t — некоторые, зависящие лишь от базиса i , константы, а Є {1,2,4}, t Є {1,2}.
Доказательство теоремы 4, также как и теоремы 1 - конструктивное.
Теорема 5. Базису Б можно сопоставить некоторый класс К булевых функций от переменных а?і,...,я;п и константы /г, /i, t такие, что для любой функции / из К и для любой схемы 5, реализующей /, при 7 г выполняется неравенство P(S) krf + hyi+1.
Фигурирующие в теоремах 4 и 5 константы и классы К приведены в таблице 2.
Таблица 2
Б a 6 t с d b d к h r К
= {/ 2 392 1 224 1/1200 13 672 2 -1 1/4 Кг
2 = {1} 2 9 2 2016 1/600 — — 2 -3 1/6 K7
з = {А, } 1 144 1 448 1/600 15 1344 1 0 1/4 Кг
4 = {/ Л 1 11 1 1344 1/600 — — 1 0 1/2 Кг
Д. = {- ,У } 1 480 1 448 1/1200 18 1344 1 0 1/2 Кг = {&Г} 2 967 1 448 1/1800 28 1344 2 -1 1/6 к 7 = { ,&,Є} 2 449 1 896 1/1200 24 2688 2. -5 — к 8 = {/Ы} 2 449 1 672 1/1200 24 2016 2 -3 1/4 к2 = {Є,&,1} 4 1794 1 672 1/2400 93 2016 1 0 1/2 Кг
ю = {-,&,0} 2 967 1 672 1/1800 28 2016 2 -4 — к7 = {- ,-} 2 420 1 448 1/1200 18 1344 2 -4 1/6 к7 = {- ,0} 2 420 1 672 1/1200 18 2016 2 -4 1/8 Кго
із = {- ,Є} 2 923 1 448 1/1800 20 1344 1 0 1/2 Кг
Б14 = {v,l 2 506 1 448 1/1200 34 1344 2 — 1/2 к9 = { ,V,0} 2 447 1 672 1/1200 22 2016 2 — — к9
i6 = {-,V,e} 2 1680 1 672 1/2400 31 2016 2 — — к9
5i7 = {e,V,l} 4 1050 1 672 1/1800 85 2016 1 0 1/2 Кг
Б18 = {&,У,"} 1 3.13 2 504 1/450 — — 1 0 1/2 Кг
В каждом базисе константа t в теоремах 4 и 5 одна и та же. Константа г в некоторых случаях (их большинство) зависит лишь от базиса и типа неисправностей, а в других - еще и от схемы. В последнем слу чае соответствующее ей место в таблице содержит прочерк. Теорема 4 будет справедлива, если константы Ъ и с заменить константами У и с соответственно.
Установлено, что для всех базисов Б\ — Б\%, исключая Бд Бц и Бц, константы а и к равны. Это свидетельствует о том, что соответствующие методы синтеза позволяют строить схемы, асимптотически (по 7) наилучшие по надежности, для почти всех булевых функций (при растущем п) в названных базисах, причем сложность предлагаемых схем по порядку равна сложности схем, построенных только из надежных элементов. Таким образом, из теорем 4 и 5 следует
Теорема 6. Схемы, построенные в теореме 4, являются асимптотически наилучшими по надежности для почти всех функций в базисах Бі — Б$, Бю — і і2, Б\4 — 1 іб и І і8, причем сложность этих схем по порядку равна сложности схем, построенных только из надежных элементов.
Напомним, что константа t равна двум только в базисах Бі и Б\% и — единице в остальных случаях.
При t = 1 ненадежность схемы сверху и снизу оценивается функцией, по порядку равной 7 при 7 -+ О- Точнее, произвольную функцию можно реализовать схемой (см. теоремы 1 и 4), ненадежность которой асимптотически не больше ау (7 - 0). Если же функция / Є К, то ненадежность любой схемы, ее реализующей (см. теоремы 2 и 5), асимптотически не меньше ку (7 —У 0). В том случае, когда а = к, схема S (см. табл. 1 и 2) для функции / Є К имеет ненадежность, асимптотически равную ау (у —ї 0), и является асимптотически наилучшей.
При t = 2 имеем качественно другой результат. Ненадежность схемы оценивается (сверху и снизу) функцией, по порядку равной у2 при 7 — • 0. Точнее, в базисе Бъ произвольную функцию можно реализовать схемой (см. теорему 4), ненадежность которой асимптотически не больше 272 (7 - 0)- Если же функция / Є Kft то ненадежность любой схемы, ее реализующей (см. теорему 5), асимптотически не меньше 272 (7 - 0). Следовательно, схема 5, удовлетворяющая условиям теоремы 4, для функции / Є К7 имеет ненадежность, асимптотически равную 272 (7 — 0)і и является асимптотически наилучшей по надежности. Аналогично, в базисе Б\$ произвольную функцию можно реализовать схемой (см. теорему 4), ненадежность которой асимптотически не больше 72 (7 — •()).. Если же функция / Є if і, то ненадежность любой схемы, ее реализующей (см. теорему 5), асимптотически не меньше 72 (7 0)«-Следовательно, схема, удовлетворяющая условиям теоремы 4, для функции / Є К\ имеет ненадежность, асимптотически равную 72 (т 0)» и является асимптотически наилучшей по надежности.
Диссертация состоит из введения, четырех глав и списка литературы, содержащего 44 названия. Общий объем работы - 169 страниц, в работе содержатся 11 рисунков (они приведены в приложении) и 5 таблиц. Нумерация таблиц и рисунков — сквозная.
В первой главе диссертации развита некоторая техника, используемая в дальнейшем для получения верхней и нижней оценок надежности схем, приведены необходимые определения и обозначения. Отметим наиболее важные утверждения.
В теореме 1.2 показано, что ненадежность схемы оценивается снизу наименьшими вероятностями ошибок подсхемы, содержащей выход схемы. Эта теорема используется при доказательствах нижних оценок ненадежности схем.
Теорема 1.4 утверждает, для двойственных схем на противоположных входных наборах вероятности ошибок равны. Следовательно (следствие 1.2), равны ненадежности двойственных схем. Поэтому утверждение о надежности, доказанное для функции / в данном базисе и при данном типе неисправностей, верно для двойственной функции / в двойственном базисе и противоположном типе неисправностей.
Во второй главе описываются методы синтеза надежных схем, с помощью которых получены верхние оценки ненадежности схем.
В разделе 2.1 описывается метод синтеза надежных схем в базисе Б = {x/j/}, который играет основополагающую роль, поскольку полученные для него результаты переносятся в другие базисы из двухвходовых функциональных элементов. Применение описанного метода приводит к построению надежных схем, которые, как будет показано в третьей главе, являются не просто надежными, а асимптотически наилучшими по надежности.
В разделе 2.2 описаны методы синтеза надежных схем при неисправностях на выходах элементов. А именно, доказано, что в каждом из базисов Б\ — Б\$ при "i d произвольную булеву функцию можно реализовать схемой, ненадежность которой не более aj + b" f2. Константы а, Ь", d! - положительны, зависят от базиса и типа неисправностей, а Є {1,2,3,4}.
Нижние оценки надежности схем получаются из верхних оценок ненадежности сразу по определению надежности.
В разделе 2.3 описаны методы синтеза надежных схем при неисправностях на входах элементов. А именно, доказано, что в каждом из базисов Б\ — Бц при j d! произвольную булеву функцию можно pea лизовать схемой, ненадежность которой не более a f -\-b" t+1. Константы а, Ь", d y t - положительны, зависят от базиса и типа неисправностей, а Є {1,2,4}, t Є {1,2}.
Нижние оценки надежности схем получаются из верхних оценок ненадежности сразу по определению надежности.
Третья глава диссертации посвящена нижним оценкам ненадежности схем. Доказано, что надежные схемы, построенные во второй главе, являются асимптотически наилучшими по надежности во всех базисах, кроме Бт)Б ь, Б\о и Бп при неисправностях на выходах элементов, и і?9, із и Бп при неисправностях на входах элементов.
Для получения нижних оценок ненадежности схем в базисе Б как при неисправностях на выходах элементов, так и при неисправностях на входах элементов используются следующие методы.
1. В схеме 5, реализующей функцию / Є К{п), выделяется подсхема, содержащая выход схемы и обладающая тем свойством, что ее ненадежность не больше ненадежности схемы 5 и не меньше krf + /ry +1 при 7 т.
Оценки для вероятностей ошибок на выходе схем и подсхем получены с помощью лемм 1.1 - 1.18 и теорем 1.1 - 1.3 первой главы.
2. Для схемы Sy реализующей функцию / Є K(n), указывается набор значений входных переменных, на котором вероятность ошибки на выходе схемы не меньше &7 + /i7 +1 при 7 т..
В разделе 3.1 доказаны нижние оценки ненадежности схем в случае неисправностей на выходах элементов (см. теорему 2). Показано, что базису Б можно сопоставить некоторый класс К{п) булевых функций от переменных 2?i,.. .,#п и константы k, h такие, что для любой функции / из К и для любой схемы S, реализующей /, при 7 т выполняется неравенство P(S) ку + hj2.
Константы к, ht г (к Є {1,2,3}) приведены в таблице 1. Классы К(п) булевых функций /(ari,.. . ,жп) явно найдены и описаны. Эти классы, исключая К$(п) и К п), при больших п содержат почти все булевы функции.
Установлено, что для всех базисов, за исключением Бт,Б$,Бщ и Бп, константы а и к равны. Это свидетельствует о том, что соответствующие методы синтеза позволяют строить асимптотически наилучшие по надежности схемы для почти всех булевых функций в базисах Б\ — Z 4, 6, в Б\и - 12) 14 — іб и - 18 и Для некоторых классов булевых функций в базисах Б$ и Б .
Верхние оценки надежности схем получаются из нижних оценок не надежности по определению надежности.
В разделе 3.2 доказаны нижние оценки ненадежности схем в случае неисправностей на входах элементов (см. теорему 5). Показано, что базису Б можно сопоставить некоторый класс К булевых функций от переменных ari,...,a;n и константы ky.h,.t такие, что для любой функции /из К и для любой схемы S, реализующей /, при у г выполняется неравенство P(S) куг + hyt+1.
Классы К(п) булевых функций /(a?i,..., хп) явно найдены и описаны. Константы /г, h, , г (k,t 6 {1,2}) приведены в таблице 2.
Установлено, что для всех базисов, за исключением i g, Біз и Бп, константы а и к равны. Это свидетельствует о том, что соответствующие методы синтеза для почти всех булевых функций позволяют строить асимптотически наилучшие по надежности схемы.
Верхние оценки надежности схем получаются из нижних оценок ненадежности по определению надежности.
Четвертая глава диссертации посвящена сложности асимптотически наилучших по надежности схем. Доказано, что сложность асимптотически наилучших по надежности схем как при неисправностях на выходах, так и при неисправностях на входах элементов по порядку равна сложности схем, построенных только из надежных элементов.
В разделе 4.1 излагается метод синтеза надежных схем в базисе Б = {аг/у}, причем главное внимание уделяется сложности построенных схем. Этот базис играет основополагающую роль, поскольку полученные для него результаты переносятся в другие базисы из двухвходовых функциональных элементов, а их применение приводит к построению асимптотически наилучших по надежности схем, причем сложность этих схем по порядку равна сложности схем, построенных только из надежных элементов.
В разделе 4.2 описываются методы синтеза схем, асимптотически наилучших по надежности, при неисправностях на выходах элементов. Показано (см. теорему 1), что в базисе Б при у 5: d любую булеву функцию /( 1,.. .,жп) можно реализовать схемой S, для которой P(S) ay + by2, L(S) с • 2n/n, где а, Ь, с, d - некоторые, зависящие лишь от базиса Б, константы, а Є {1,2,3,4}.
Оценки теоремы 4.2 установлены конструктивно, т. е. представлены методы схем 5, удовлетворяющих указанным оценкам по надежности и сложности. Константы, фигурирующие в формулировке теоремы, приведены в таблице 1.
В разделе 4.3 описываются методы синтеза схем, асимптотичес ки наилучших по надежности, при неисправностях на входах элементов. Показано (см. теорему 4), что в базисе Б при 1 d любую булеву функцию /(жі,.. .,жп) можно реализовать схемой , для которой P(S) arf + &7 +1 L(S) с • 2п/п, где а, 6, с, d, t - некоторые, зависящие лишь от базиса Б, константы, а Є {1,2,4}, t Є {1,2}.
Оценки теоремы 4.3 установлены конструктивно, т. е. представлены методы схем 5, удовлетворяющих указанным оценкам по надежности и сложности. Константы, фигурирующие в формулировке теоремы, приведены в таблице 2.
Установлено, что во всех базисах, исключая 1 9, Бц и Бп, предлагаемые методы синтеза позволяют строить (при растущем п) для почти всех функций асимптотически (по 7) наилучшие по надежности схемы со сложностью, по порядку равной сложности схем, построенных только из надежных элементов.
Основные результаты диссертации изложены в [6 - 29].
Автор глубоко признателен своему научному консультанту профессору Н. П. Редькину за постоянное внимание к работе, поддержку и ценные советы.
Верхние оценки ненадежности схем при неисправностях на выходах элементов
Рассматривается реализация булевых функций схемами из ненадежных функциональных элементов в базисах из двухвходовых функциональных элементов [38]. Все элементы схемы независимо друг от друга с вероятностью 7 (т 1/2) подвержены однотипным константным неисправностям на выходах элементов. Напомним, что неисправности типа 0 на выходах элементов характеризуются тем, что в исправном состоянии функциональный элемент реализует приписанную ему булеву функцию, а в неисправном - константу 0. Аналогично определяются неисправности типа 1 на выходах функциональных элементов. Поскольку (следствие 1.2) утверждение, доказанное для функции в некотором базисе при неисправностях типа 0 (1), справедливо для двойственной функции в двойственном базисе при неисправностях типа 1 (0), далее будем предполагать, что все базисные элементы подвержены неисправностям типа 0 на выходах. 2.2.1. Базис Бі = {/}. При неисправностях типа 0 на выходе функ ционального элемента х /у имеем a = P = 8 = jtr = 01a,/j, = y. Возьмем в качестве схемы S/ на рис. 1 базисный элемент х/у. Тогда соотношение (2.1.1) для ненадежностеи P(S) и Р(0(5)) схем S и ф(Э) принимает вид: Теорема 2.2.1.1. При 7 1/70 любую булеву функцию можно реализовать схемой А такой, что Доказательство. Пусть / - произвольная булева функция. По теореме 2.1.5 ее можно реализовать схемой 5, ненадежность которой P(S) Зу. По схеме S построим схемы ф(Б) и 2(5). Используя соотношение 2.2.1, при 7 .1/70 имеем Схема 02(5) - искомая. Теорема доказана. Заметим, что детально повторяя доказательства теорем 2.1.1 и 2.1.2, можно получить более точное и лучшее соотношение для ненадежностеи P(S) и Р(0(5)) схем S и ф(8): а также доказать следующее утверждение. Теорема 2.2.1.2 [4]. При 7 1/50 любую булеву функцию можно реализовать схемой S такой, что Р(5) 27 + 872 + 15773. 2.2.2. Базис Бг = {4}. Базисный элемент х 4- у функционирует с ве роятностями ошибок ро(00) = 7 .Pi(01) = Pi(10) = pi(ll) = 0. На рис. 1 заменим схему 5/ базисным элементом с функцией х у, которая двойст венна функции х/у. Поскольку ненадежности двойственных схем равны, можно воспользоваться результатами раздела 2.1 при подходящем обо значении вероятностей ошибок. Полагаем а = /3 = = 0, т = 7« Тогда \х = 7, а соотношение (2.1.1) для ненадежностеи Р(5) и Р(0(5)) схем S и 0( S) принимает вид: Далее в этой главе при построении схемы, реализующей функцию х і у, будем опускать рассуждения о надежности двойственных схем и сразу указывать значения для а, /3,5, т. Теорема 2.2.2.1. При 7 1/160 любую булеву функцию можно реализовать схемой А такой, что Доказательство. Пусть / - произвольная булева функция.
По теореме 2.1.2 ее можно реализовать схемой 5, ненадежность которой P(S) 4 у. По схеме S построим схемы 4 (S) и (j 2(S). Используя соотношение 2.2.2, при у 1/160 имеем Схема 02(5) - искомая. Теорема доказана. Заметим, что детально повторяя доказательства теорем 2.1.1 и 2.1.2 и делая, по возможности, более точные оценки ненадежности, получим следующее утверждение. Теорема 2.2.2.2 [4]. При 7 1/50 любую булеву функцию можно реализовать схемой S такой, что P(S) 7 + 272 + 3573- 2.2.3. Базис Бз = {т } Моделируя формулу (х -ft- у) у, постро им схему, реализующую функцию х 4- у с вероятностями ошибок Ро(00) = 7, Pi(01) = 0,Pi(10) = 7(1-7)»Pi(H) = 0. Поскольку ненадежности двой ственных схем равны, считаем а = 0, /3 = 7(1 — 7)» = 0, г = у. Тогда /2 = 7J а соотношение (2.1.1) для ненадежностей P(S) и P((f (S)) схем S и / () принимает вид: Теорема 2.2.3.1. При у 1/160 любую булеву функцию можно реализовать схемой А такой, что Доказательство. Пусть / - произвольная булева функция. По теореме 2.1.2 ее можно реализовать схемой 5, ненадежность которой P(S) 4у. По схеме S построим схемы ф(Б) и / 2(5). Используя соотношение 1.1.6 при 7 1/160 имеем Схема ф2(в) - искомая. Теорема доказана. 2.2.4. Базис Б4 = {-ftf}» Построим схему С, реализующую х 4- у, мо делируя формулу х -/ у. Вероятности ошибок для нее равны Схема С имеет тот же набор вероятностей ошибок, что и функциональный элемент х I у, переходящий в неисправное состояние с вероятностью 27 — 72- Тогда соотношение (2.1.1) для ненадежностей P(S) и Р( (5)) схем S и ф(3) принимает вид: Из теоремы 2.2.2.1 следует Теорема 2.2.4.1. При 7 1/320 любую булеву функцию можно реализовать такой схемой 5", что Из теоремы 2.2.2.2 следует Теорема 2.2.4.2. При 7 1/100 любую булеву функцию можно реализовать такой схемой S, что 2.2.5. Базис Б5 = {- , / } Построим схему, реализующую х ± У-, мо делируя формулу (х — (я у ж)) тА у. Вероятности ошибок для нее те же, что для схемы С из п. 2.2.4, поэтому справедливы следующие теоремы. Теорема 2.2.5.1. При у 1/320 любую булеву функцию можно реализовать такой схемой S, что Теорема 2.2.5.2. При 7 1/100 любую булеву функцию можно реализовать такой схемой S, что 2.2.6. Базис Бе = {&,"}. Построим схему D, реализующую х I у, моделируя формулу x&zy. Вычислим вероятности ошибок для схемы/?: Ро — З7 З72 + 73 ПРИ входном наборе (00), Pi = 0 при входных наборах (01), (10), (11). Схема D имеет тот же набор вероятностей ошибок, что и функциональный элемент х \, у, переходящий в неисправное состояние с вероятностью З7 — З72 + 73- Поэтому соотношение (2.1.1) для ненадежностей P(S) и P( j (S)) схем S и 4 (S) принимает вид:
Учитывая сказанное и используя теоремы 2.2.2.1 и 2.2.2.2, получаем следующие теоремы. Теорема 2.2.6.1. При 7 1/480 любую булеву функцию можно реализовать такой схемой 5, что Теорема 2.2.6.2 [4]. При 7 1/150 любую булеву функцию можно реализовать такой схемой 5, 2.2.7. Базис 67 = { ,&:,ф}. Построим схему из четырех функцио Построенная схема имеет тот же набор вероятностей ошибок, что и схема D из п. 2.2.6, реализующая х \. у. Поэтому применимы теоремы 2.2.2.1 и 2.2.2.2. Теорема 2.2.7.1. При 7 1/480 любую булеву функцию можно реализовать такой схемой 5, что Теорема 2.2.7.2. При 7 1/150 любую булеву функцию можно реализовать такой схемой S, что 2.2.8. Базис Bg = {7 , 1}. Построим схему, реализующую х I у, мо делируя формулу (1 / х) / у. Построенная схема имеет тот же набор вероятностей ошибок, что и схема D из п. 2.2.6, реализующая х \, у. Поэтому в рассматриваемом базисе справедливы теоремы. Теорема 2.2.8.1. При 7 1/480 любую булеву функцию можно реализовать такой схемой 5, что Теорема 2.2.8.2. При 7 1/150 любую булеву функцию можно реализовать такой схемой 5, что 2.2.9. Базис Б9 = {ф,&,1}. Построим схему из четырех функцио нальных элементов, реализующую функцию х 4- У і моделируя форму строенной схемы: Р0(00) = 37 - З72 + 73 -Pi(01) = 7(1 - і)2,Рі(Щ = 7(1 - 7)3»-Pi(ll) = 72(1 - if- Поскольку ненадежности двойственных схем равны, считаем а = 72(1 — 7)2 Р = 7(1 — 7)2 = 7(1 — 7)3 т = З7 — З72 + 73» J1 — З7 З72 + 73 Тогда соотношение (2.1.1) для ненадеж ностей P(S) и P( f)(S)) схем 5 и 0(5) принимает вид: Теорема 2.2.9.1. При 7 1/480 любую булеву функцию /можно реализовать такой схемой Л, что Доказательство. Пусть / - произвольная булева функция. По теореме 2.1.2 ее можно реализовать схемой 5, ненадежность которой P(S) I27. По схеме 5 построим схемы 0(5) и 02(5). Используя соотношение 2.2.9, при 7 1/480 имеем Схема 02(5) - искомая. Теорема доказана. 2.2.10. Базис Бю = { ,&, 0}. Построим схему, реализующую х 4- у, моделируя формулу (ж 0)&(у 0). Построенная схема имеет тот же набор вероятностей ошибок, что и схема D из п. 2.2.6, реализующая х I у. Поэтому справедливы теоремы. Теорема 2.2.10.1. При 7 1/480 любую булеву функцию можно реализовать такой схемой 5, что Теорема 2.2.10.2. При у 1/150 любую булеву функцию можно реализовать такой схемой 5, что 2.2.11. Базис Бц = {— ,"}. Построим схему Р, реализующую аг/у, моделируя формулу х — у.
Верхние оценки ненадежности схем при неисправностях на входах элементов
Рассматривается реализация булевых функций схемами из ненадежных функциональных элементов в базисах из двухвходовых функциональных элементов [38]. Все элементы схемы независимо друг от друга переходят в неисправные состояния типа 0 на входах. Напомним, что неисправности типа 0 на входах элементов характеризуются тем, что в исправном состоянии функциональный элемент реализует приписанную ему булеву функцию, а в неисправном.— поступающий на его вход нуль не искажается, а поступающая на его вход единица с вероятностью 7 (7 1/2) может превратиться в нуль. 2.3.1. Базис Б і = {/}. Вероятности ошибок на выходе функциональ ного элемента х/у равны а = 0, (3 — 0,8 = 0, г = 27—72« Тогда // = 27—72- Соотношение (2.1.1) для ненадежностей P(S) и?( (5)) схем 5 и 0(5) принимает вид: Теорема 2.3.1. При 7 1/320 любую булеву функцию можно реализовать схемой А такой, что Доказательство. Пусть / - произвольная булева функция. По теореме 2.1.2 ее можно реализовать схемой 5, ненадежность которой P(S) 87-По схеме 5 построим схемы 0(5), 02(5) и 03(5). Используя соотношение (2.3.1), при 7 1/320 имеем P{(f (S)) 2у + 12772 2.47, Ptf2(S)) 27 +1772, P&3(S)) 27 + 972. Схема 03(5) - искомая. Теорема доказана. 2.3.2. Базис Б2 = {4-}- Вероятности ошибок на выходе функциональ ного элемента равны Р0(00) = 0, Р0(01) = Ро(Щ = 7 А(П) = 72- Поскольку ненадежности двойственных схем равны, считаем а = 72?/5 = 8 = 7, г = 0. Тогда fi — 7, а соотношение (2.1.1) для ненадежностей P(S) и Р(ф(8)) схем 5 и 0(5) принимает вид: Теорема 2.3.2. При 7 1/70 любую булеву функцию можно реализовать схемой А такой, что Доказательство. Пусть / - произвольная булева функция. По теореме 2.1.5 ее можно реализовать схемой 5, ненадежность которой P(S) З7. По схеме 5" построим схемы 0(5), 02(5) и 03(5). Используя соотношение (2.3.2), при 7 1/70 имеем P(V(5)) 4972, Р(02(5)) 672, Р(ф3(8)) 2 )2 + 2673- Схема 03(5) - искомая. Теорема доказана. Моделируя формулу ((ж -/+ х) х) / у, построим схему из трех элементов, реализующую х \.у. Вероятности ошибок для нее равны: г = 7, 5 = 7(1-7), /3 = 7(1-7)(2-47 + 572-273), а = 72(1 7)(2-47 + 573 — 273). Тогда соотношение (2.1.1) для ненадежностей P(S) и Р(ф(Б)) схем 5 и 0(5) принимает вид: Теорема 2.3.3. При у 1/160 любую булеву функцию можно реализовать схемой А такой, что Доказательство.
Моделируя формулу {х у) / у, построим схему, реализующую х \. у. Вероятности ошибок для нее равны: г = 7» S = 72(1 — 7) Р — 7(1 7)» а — 7 72 + 473 — 274- Тогда А = 7- По теореме 2.1.2 при 7 1/160 любую булеву функцию можно реализовать такой схемой 5, что P(S) 47. По схеме 5 построим схемы 0(5) и 02(5). Используя соотношение (2.3.3) при 7 1/160 имеем P( f (S)) 7 + 6О72, P{(j 2(S)) 7 + 1472-Схема 02(5) - искомая. Теорема доказана. 2.3.4. Базис Б4 = {/ ,"} Моделируя формулу x j/, построим схему, реализующую х \. у. Вероятности ошибок для нее равны: г = 7 = /3 = 7(1 — 7)? = 72(1 — 7)« Тогда JJL = 7 а соотношение (2.1.1) для ненадежностей P(S) и Р( (5)) схем 5 и 0(5) принимает вид: Теорема 2.3.4. При 7 1/160 любую булеву функцию можно реализовать схемой А такой, что Доказательство. Пусть / - произвольная булева функция. По теореме 2.1.2 ее можно реализовать схемой 5, ненадежность которой P(S) 4у. По схеме 5 построим схемы 0(5) и 02(5). Используя соотношение (2.3.4), при 7 1/160 имеем Р(0(5)) 7 + Ь0у2у P( t 2(S)) 7 + 1І72-Схема 02(5) - искомая. Теорема доказана. 2.3.5. Базис Б5 = {— ,-/ } Моделируя формулу (х — (х / х)) -fa у, построим схему, реализующую х \, у. Вероятности ошибок для нее равны: соотношение (2.1.1) для ненадежностей P(S) и Р(0(5)) схем 5 и 0(5) принимает вид: Теорема 2.3.5. При у 1/320 любую булеву функцию можно реализовать схемой А такой, что Доказательство. Пусть / - произвольная булева функция. По теореме 2.1.2 ее можно реализовать схемой 5, ненадежность которой P(S) 87-По схеме 5 построим схемы 0(5) и 02(5). Используя соотношение (2.3.5), при 7 1/320 имеем Р(0(5)) у + I8O72, Р(02(5)) у + 1972. Схема 02(5) - искомая. Теорема доказана. 2.3.6. Базис Бе = {&,"} Моделируя формулу ж&ф, построим схему, реализующую х I у. Вероятности ошибок для этой схемы равны: т = 2т—72 S = /3 = 7(1— l)2i а — 72(1 7)2« Тогда ц = 2у—72, а соотношение (2.1.1) для ненадежностей P(S) и Р(0(5)) схем 5 и 0(5) принимает вид: Теорема 2.3.6. При у 1/320 любую булеву функцию можно реализовать схемой А такой, что Доказательство. Пусть / - произвольная булева функция. По теореме 2.1.2 ее можно реализовать схемой 5, ненадежность которой P(S) 87. По схеме 5 построим схемы 0(5), 02(5) и 03(5). Используя соотношение (2.3.6), при 7 1/320 имеем Р(0(5)) 27 + I6I72, -Р(02(5)) 27 + 3372, P( f 3(S)) 27 + 1772. Схема 03(5) - искомая. Теорема доказана. 2.3.7. Базис Б7 = { ,&,Ф}. Константу 0 можно реализовать сколь угодно надежно. Действительно, моделируя формулу х ф ж, построим схему, реализующую константу 0 с вероятностями ошибок pi = 0 при х = 0, р\ = 27(1 — 7) ПРИ х = 1. Разветвим выход построенной схемы, соединив со входами элемента с функцией ф, построим схему, реализующую константу 0 с вероятностями ошибок pi = 0 при х = 0, pi = (27(1 — 7))2 ПРИ х — 1- После к шагов итерации имеем схему SQ, реализующую константу 0 с вероятностями ошибок pi = 0 при х = 0, pi = (27(1 — 7)) ПРИ х — 1 Очевидно, сложность схемы SQ равна к, а ненадежность — стремится к нулю с ростом числа итераций к. Константу 1 также можно реализовать сколь угодно надежно. Для этого используем схему SQ И функциональный элемент, которому приписана эквивалентность.
Моделируя формулу 0 0, построим схему 5i, реализующую константу 1 с вероятностями ошибок р=0 при х = 0, р0 = (27(1 — 7))fe+1 ПРИ х = 1- Очевидно, сложность схемы Si равна /s + 1, а ненадежность - стремится к нулю с ростом числа к. Используя одну схему 5о, конъюнктор и два элемента, реализующих , построим схему, реализующую х \. у. Для этого промоделируем формулу (ж 0)&(у 0). Вероятности ошибок для этой схемы: 7+272) 72(1-7)2 + (27) (1-7) +3. Полагаем к = 4, тогда а 72 М 27, а соотношение (2.1.1) для ненадежностей P(S) и P((f)(S)) схем 5 и f (S) принимает вид: Теорема 2.3.7. При 7 1/320 любую булеву функцию можно реализовать схемой А такой, что Доказательство. Пусть / — произвольная булева функция. По теореме 2.1.2 ее можно реализовать схемой 5, ненадежность которой P(S) 87. По схеме 5 построим схемы 4 (S) и 02(5). Используя соотношение (2.3.7), при 7 1/320 имеем Р( / (5)) 27 + I6I72, P{(f 2(S)) 27 + 2472. Схема ф2(в) - искомая. Теорема доказана. 2.3.8. Базис Б = {/, 1}. Моделируя формулу (1 / х) -/ у, постро им схему, реализующую х \.у. Вероятности ошибок для этой схемы рав ны: т = 27 — 72 5 = {З = 7(1 — 7)2 а = 72(1 — 7)2- Тогда /х = 27 — 72 а соотношение (2.1.1) для ненадежностей P(S) и Р(ф(8)) схем 5 и 0(5) принимает вид: Теорема 2.3.8. При 7 1/320 любую булеву функцию можно реализовать схемой А такой, что Доказательство. Пусть / - произвольная булева функция. По теореме 2.1.2 ее можно реализовать схемой 5, ненадежность которой Р(5) 87. По схеме 5 построим схемы 0(5) и 02(5). Используя соотношение (2.3.8), при 7 1/320 имеем Pty(S)) 2-у + I6I72, Р(Ф2(в)) 2 + 2472. Схема 02(5) - искомая. Теорема доказана. строим схему, реализующую х \. у. Вероятности опіибок для для нее равны: г = 47-б72 + 473 —74» = Р = 27(1 — 7)4» а — 472(1 7)4 Тогда р = 47 — 672 + 473 — 74» а соотношение (2.1.1) для ненадежностей P(S) и Р(Ф{3)) схем 5 и 0(5) принимает вид: (2.3.9) Теорема 2.3.9. При 7 1/640 любую булеву функцию можно реализовать схемой А такой, что Р(А) 47 + 7072. Доказательство. Пусть / - произвольная булева функция. По теореме 2.1.2 ее можно реализовать схемой 5, ненадежность которой P(S) I67. По схеме 5 построим схемы 0(5), 02(5) и 03(5). Используя соотнопіение (2.3.9), при 7 1/640 имеем Р(0(5)) 47 + 64272, Р(Ф2{3)) 4у + 9372, P((f 3(S)) 47 + 7072. Схема 03(5) - искомая. Теорема доказана. Очевидно, функции жі,...,хп и константу 1 можно реализовать абсолютно надежно. В 2.3.7 показано, что, используя только сумматор, константу 0 можно реализовать сколь угодно надежно. Нетрудно проверить, что функции, конгруэнтные хі ф #2, жі&Ж2, ah, можно реализовать схемами, с ненадежностью не более 27, а функции, конгруэнтные х\ ф Х2 ф жз, ari&(a;2 Ф яз), хі ф жг Ф 1 - с ненадежностью не более З7. 2.3.10. Базис Бю = { ,&,0}. Моделируя формулу (х 0)&(у 0), построим схему, реализующую х \,у. Вероятности ошибок для нее равны:
Нижние оценки ненадежности схем при неисправностях на выходах элементов
Рассматривается реализация булевых функций схемами из ненадежных элементов в базисах из двухвходовых функциональных элементов [38]. Предполагается, что все элементы схемы независимо друг от друга переходят в неисправные состояния типа 0 (1) на входах. Поскольку утверждение, доказанное для функции в некотором базисе при неисправностях типа 0 (1) на входах элементов, справедливо для двойственной функции в двойственном базисе при неисправностях типа 1 (0) на входах элементов, далее будем предполагать, что базисные элементы подвержены неисправностям типа 0 на входах. Напомним, что неисправности типа 0 на входах элементов характеризуются тем, что в исправном состоянии функциональный элемент реализует приписанную ему булеву функцию, а в неисправном - поступающий на его вход нуль не искажается, поступающая на его вход единица с вероятностью у (7 1/2) может превратиться в нуль. 3.2.1. Базис Бг = {/}. Теорема 3.2.1. Пусть функция / Є Ki(n) U {0}, S - любая схема, реализующая /.Тогда при 7 1/4 верно неравенство P(S) 2у — у2. Доказательство такое же как в теореме 3.1.2. Из теоремы 3.2.1. следует, что при малых значениях 7 функции из / Є К\ (n) U {0} нельзя реализовать схемами, ненадежность которых асимптотически меньше 27. Поэтому любая схема, удовлетворяющая условиям теоремы 2.3.1 и реализующая булеву функцию / Є К\{п) U {0}, является асимптотически наилучшей по надежности для / и функционирует с ненадежностью, асимптотически равной 27 при 7 - 0- Пример 3.2.1. Моделируя формулу (х/х)/х, построим схему, реализующую константу 1 с ненадежностью (27—72)(1 l)2- которая при 7 0 меньше 27 — 72- Очевидно, функции х\,...хп можно реализовать абсолютно надежно. Таким образом, при неисправностях типа 0 на входах элементов х/у почти все булевы функции можно реализовать схемами, асимптотически наилучшими по надежности. Приведенные утверждения справедливы (следствие 1.2) для функций / Є К\(п) U {1} в базисе {х \, у} при неисправностях типа 1 на входах элементов. Пусть д(х) - произвольная булева функция (ж = (х1,Х2,...,хп)). Напомним, что Кі(п) - множество булевых функций, которые нельзя представить в виде /(5) = (х{ V р(ж))а, где і Є {1,..., п},а Є {0,1}. Теорема 3.2.2. Пусть функция jЄ Ki(n), S - любая схема, реализующая /, и 7 1/6. Тогда P(S) Доказательство. Пусть функция / Є К п)у S — любая схема, реализующая /. В схеме S выделим элемент Еі, содержащий выход схемы S. Входы элемента Еі не могут быть соединены с полюсами или склеены (это противоречит выбору функции /).
Поэтому они соединены с выходами некоторых элементов Еги з- 1. Пусть элементы i?2 и Е% различны. Тогда, учитывая результат задачи 1.1, по лемме 1.15 вероятность ошибки на выходе подсхемы, состоящей из элементов JSi, 2 и 3) на единичных входных наборах функции / удовлетворяет неравенству Ро (1 - 7)(272 - 74(1 - 7) = (1 - 72)(272 - 273 + 74)-Рассматриваемая подсхема состоит из трех элементов, поэтому ее ненадежность не больше З7 1/2, так как 7 1/6. По следствию 1.1 имеем 2. Пусть элементы 1 и Е$ совпадают, причем входы элемента J5 2 склеены. Поскольку / Є Кі(п), входы 2% соединены с выходом некоторого элемента Е$. Вероятности ошибок на выходе элемента Е\ следующие: Ро = 0) Pi J2- Вероятности ошибок на выходе схемы, состоящей из элементов 1 и Еь, по лемме 1.16 удовлетворяют неравенствам ро 72(1 — 72)» Pi = 72 Применяя лемму 1.16, оценим вероятности ошибок на выходе схемы, состоящей из элементов Е\,Еъ и Е±: PQ = у2(1 . — у2), Pi 72 + 72(1 — 72)2 (1 — 72)(272 — 73 + 74) Рассматриваемая подсхема состоит из трех элементов, поэтому ее ненадежность не больше З7 1/2, так как 7 1/6. По следствию 1.1 имеем P(S) (1 - 72)(272 - 273 + 74)- 3. Пусть элементы Е-1 и Е$ совпадают, но входы элемента Е-i соединены с выходами различных элементов Е и i% (но не с полюсами, это противоречит выбору функции /). Применяя лемму 1.16 и используя результаты п. 1 доказательства, получим, что вероятность ошибки на выходе подсхемы, состоящей из элементов Е\, Е2, Е4 и Е$ при нулевых входных наборах функции / удовлетворяет неравенству: Pi = 72+Ро(1—72) 72+(1—72)2(272 — 273+74) Ненадежность выделенной подсхемы не больше З7 1/2, так как 7 1/6. По следствию 1.1 имеем P(S) (1 - 72)(272 273 + 74)- Теорема доказана. Из теоремы 3.2.2 следует, что при малых значениях 7 функции из класса К-?(п) нельзя реализовать схемами, ненадежность которых асимптотически меньше 272. Поэтому любая схема, удовлетворяющая условиям теоремы 2.3.2 и реализующая булеву функцию / Є K-j{n), является асимптотически наилучшей по надежности для / и функционирует с ненадежностью, асимптотически равной 272 при у - 0. Число функций / 0 Kj(n) не больше 2n22" , что мало по сравнению с общим числом 22" булевых функций от п переменных. Таким образом, при неисправностях типа 0 на входах элементов х J, у почти все булевы функции можно реализовать схемами, ненадежность которых асимптотически равна 272 при 7 — 0. С точки зрения надежности функционирования эти схемы являются асимптотически наилучшими для функций / Є Ki{n). Приведенные утверждения справедливы для функций / Є К2(п) в базисе {х/у} при неисправностях типа 1 на входах элементов (следствие 1.2). Очевидно, что функции Хі,...,хп можно реализовать абсолютно на- дежно. Константы 0 и 1 можно реализовать сколь угодно надежно.
Действительно, моделируя формулу х -/+ х, построим схему, реализующую константу 0 с вероятностями ошибок р\ = 0 при х = 0, р\ = 7(1— 7) при х = 1. Моделируя формулу 0 0, построим схему, реализующую константу 0 с вероятностями ошибок р\ = 0 при х = 0, р\ = (7(1 — 7))2 при х = 1. После к шагов итерации построим схему 5о, реализующую константу 0 с вероятностями ошибок р\ = 0 при х = 0, р\ = (7(1 — 7)) при а? = 1. Очевидно, что с ростом числа к ненадежность схемы SQ стремится к 0. Для построения схемы 5i, реализующей константу 1 сколь угодно надежно, возьмем схему SQ и соединим ее выход со входами элемента, которому приписана эквивалентность ( ). Вероятности ошибок на выходе схемы 5i равныро = 0 при ж = 0, pi = 27(1 — 7)(7(1 —7)) = 2(7(1 —7))fc+1 при х = 1.. Очевидно, что с ростом числа к ненадежность схемы Si стремится к Теорема 3.2.3. Пусть функция / Є К\(п), S - любая схема, реализующая /, и) 1/4. Тогда P(S) 7. Доказтельство такое же как в теореме 3.1.2. Из теоремы 3.2.3 следует, что при малых значениях 7 функции из класса К\{п) нельзя реализовать схемами, ненадежность которых асимптотически меньше 7- Поэтому любая схема, удовлетворяющая условиям теоремы 2.3.3 и реализующая булеву функцию / Є ifi(n), является асимптотически наилучшей по надежности для / и функционирует с ненадежностью, асимптотически равной 7 при 7 - 0. Таким образом, при неисправностях типа 0 на входах элементов х -/ у и х у показано, что все булевы функции, исключая, жі,...,а:п и константы, можно реализовать схемами, ненадежность которых асимптотически равна 7 при у — 0. С точки зрения надежности функционирования эти схемы являются асимптотически наилучшими для всех функций Приведенные утверждения справедливы для функций / 6 К\(п) в базисе {х —У у, х ф у} при неисправностях типа 1 на входах элементов (следствие 1.2). Очевидно, что функции хi,...,2?n можно реализовать абсолютно надежно. Нетрудно проверить, что константы 0 и 1 (как и в разделе 3.2.3) можно реализовать сколь угодно надежно.. Теорема 3.2.4. Пусть функция / Є -K"i(n), S - любая схема, реализующая /, и 7 1/2. Тогда P(S) Доказательство. Пусть функция / Є К\{п) реализуется некоторой схемой S. Выделим в ней функциональный элемент Е, содержащий выход схемы S. Если элемент Е - инвертор, то вероятность ошибки на выходе схемы S при входном наборе а таком, что /(а) = 0, равна Р\ = (1 — p)j + р = 7 + РО- — 72) 7 гДе Р вероятность появления значения 0 на входе инвертора Е. Следовательно, P{S) 7- Если элементу Е приписана / то вероятность ошибки на выходе схемы S при входном наборе а таком, что /(а) = 1, равна PQ — (1— p)y+p(l — 7 + 72) = 7+Р(1— і)2 7 гДе 1— Р есть вероятность появления набора (10) на входах элемента Е. Следовательно, P(S) 7» Теорема доказана.
Сложность надежных схем при однотипных константных неисправностях на выходах элементов
Пусть базис Б состоит из одной функции х/у. Пусть ро и р\ - вероятности появления 0 и 1 на выходе элемента (а,/3,8,т 1/2), тогда функционирование базисного элемента описывается таблицей 3. Во всех дальнейших рассуждениях базис х/у будет играть основополагающую роль, а именно, все другие базисы, рассматриваемые здесь, при синтезе схем более высокой надежности будут редуцироваться именно к нему. При этом в синтезе схем с интересующими нас свойствами особое место будет отведено двум операциям над схемами (одна из них -ф - введена во 2-ой главе, а другая - использует схему G, реализующую функцию голосования д(хі,Х2,хз) = х\Х2 V х\Хъ V агг з). Выбор схемы G обусловлен базисом и типом неисправностей, пока же важно только, что схема G реализует функцию голосования д{хиХ2,х$). Напомним, операция ф по произвольной схеме S, реализующей булеву функцию /, строит схему 0(5), представленную на рис. 1 (через S/ обозначена схема, реализующая функцию х/у). Операция -0 по произвольной схеме 5, реализующей булеву функцию /, строит схему rf(S), она приведена на рис. 4. Результат п-кратного применения (п Є N) операции яр к схеме S будем обозначать ipn(S). Очевидно, в результате применения (возможно, не однократного) операций фи ф к схеме 5, реализующей булеву функцию /, получаются схемы, реализующие ту же функцию /. Кроме того, применение этих операций к некоторым схемам S (при некоторых условиях на P(S)) приводит к схемам, имеющим более высокую надежность, чем исходная схема S. Далее будут рассмотрены некоторые вспомогательные утверждения. В этом разделе в качестве схемы 5/ на рис. 1 взят функциональный элемент х/у, функционирующий согласно таблице 3. Из соотношения (2.1.1) следует, что (4.1.1) где fi = max{a,/3,5, г} - ненадежность базисного элемента. Перейдем к изложению метода построения надежных схем из ненадежных элементов х/у, сложность которых имеет тот же порядок роста, что и сложность схем, построенных только из надежных элементов. Теорема 4.1.1. При \i 1/600 произвольную булеву функцию от п переменных можно реализовать схемой S, ненадежность и сложность которой удовлетворяют неравенствам Доказательству теоремы предпошлем несколько лемм. Лемма 4.1.1 [38]. Если схема 5 допускает разбиение на не имеющие общих функциональных элементов подсхемы S1i...,Sk (каждая из которых имеет один выход), в совокупности содержащие все элементы схемы Лемма 4.1.2. Любую булеву функцию, зависящую не более чем от одной переменной, можно реализовать схемой S такой, что L(S) 3, P(S) З/i. Действительно, для реализации константы 0 требуется три элемента, для реализации константы 1 - два элемента, для реализации х — один элемент, а для реализации х — нуль элементов. Тогда по лемме 4.1.1 утверждение верно. Замечание 4.1.1.
Для реализации функций, зависящих не более чем от одной переменной х (ж, ж, 0, 1), достаточно использовать 6 элементов. Лемма 4.1.3. Функцию голосования д{х\,Х2,х$) = x\Xi V x\x $ V Х2Х3 при р. 2/99 можно реализовать схемой G\ такой, что Доказательство. Схема Sg на рис. 5 реализует функцию д. Очевидно, что L(Sg) = 6, P(Sg) 6(1 (см. лемму 4.1.1). Применим к схеме Sg операцию ф (рис. 1). Ясно, что схема f (Sg) имеет сложность 27. Из (4.1.1) при // 2/99 следует, что P( f (Sg)) 3// + 96/А Схема (f (Sg) есть схема G\. Лемма доказана. Лемма АЛЛ. Пусть схема S реализует булеву функцию /, схема G -произвольная схема, реализующая функцию голосования д(хі,Х2,хз). Тогда Pty(S)) ЗР2(5) + P(G). Доказательство. Пусть а — произвольный входной набор схемы S. Пусть р — вероятность ошибки на выходе схемы 5 при входном наборе а. Оценим вероятность ошибки Р на выходе схемы ij (S) (рис. 4) на этом наборе: Р P(G)(l - p)z + SP(G)p(l - р)2 + Зр2(1 - р) + ръ = P(G)(1 - Следовательно, P(ip(S)) ЗР2(5) + P(G). Лемма доказана. Введем функции выбора (еще их называют селекторными функция ми): ( 1,32,-..,2 , 0,2/1)--,2/2 -1) = У-ЙГа()&г/а, (т.е. \а\ - число, двоичной записью которого является набор а). Поскольку Ка(Ь) обращается в нуль при а ф Ь и в единицу при а = 6, то при подстановке ai,...,a2i вместо переменных агі,...,Ж2і в функцию выбора эта функция обращается в ущ.. Лемма 4.1.5. Булеву функцию выбора г 2(жі,#2 2/(ь2/і 2/2)2/з) можно реализовать схемой выбораЛ такой, что () = 11, -Р( ) 8/х. Доказательство. Схема на рис. 6 реализует функцию V2. Разобьем эту схему на подсхемы А, В, С. Если подсхема С исправна, то при реализации функции V2 она использует выходное значение одной из схем А или В, Выбор схемы зависит от значения переменной а;і. Поэтому P(V2) Р(С) + шах{Р(А),Р(В)}.
