Бесплатно скачать, заказать диплом, курсовую, диссертацию Синтез, надежность и сложность скем из ненадежный функциональный элементов

У нас уже 176407 рефератов, курсовых и дипломных работ

Сделать закладку на сайт

Заказать диплом, курсовую, диссертацию

Быстрый переход к готовым работам

Мнение посетителей:

Книга жалоб
и предложений

Название	Синтез, надежность и сложность скем из ненадежный функциональный элементов

Количество страниц	165

ВУЗ	МГИУ

Год сдачи	2010

Бесплатно Скачать	23608.doc

Содержание	Содержание Введение 6 Глава 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. Базис {^,1} 39 2.2.9. Базис {0,&,1} 39 2.2.10. Базис {~,&,0} 39 2.2.11. Базис {->f} 39 2.2.12. Базис {->,0} 40 2.2.13. Базис {->,0} 40 2.2.14. Базис {V,^ 40 2.2.15. Базис {~,V,0} 43 2.2.16. Базис {~, V, е} 45 2.2.17. Базис {e,V,l} 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,©} 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. Базис {-)',7^} 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. Базис {-,©} 78 3.1.14. Базис {V,-} 80 3.1.15. Базис {~,V,0} 82 3.1.16. Базис {~,V,©} 84 3.1.17. Базис {®,V,1} 86 3.1.18. Базис {&,V,~} 86 3.2. Нижние оценки ненадежности схем при неисправностях на выходах элементов 87 3.2.1. Базис {/} 88 3.2.2. Базис {\|} 88 3.2.3. Базис {/>,~} 89 3.2.4. Базис {/> "} 90 3.2.5. Базис {-»,/>} 91 3.2.6. Базис {&,"} 92 3.2.7. Базис {~,&,ф} 93 3.2.8. Базис {-/М} Ю 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. Базис {0,V,1} 110 3.2.18. Базис {&, V,"} НО Глава 4. Сложность надежных схем 112 4.1. Синтез и сложность надежных схем из ненадежных элементов х/у 112 4.2. Сложность надежных схем при однотипных константных неисправностях на выходах элементов 117 4.2.1. Базис {/} 117 4.2.2. Базис {\|} 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. Базис {e,V,l} 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. Базис {/>,} 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, ф} 153 4.3.17. Базис {ф, V, 1} 154 4.3.18. Базис {&,V,"} 155 Приложение 160 Литература 165 Введение Настоящая работа относится к одному из важнейших разделов математической кибернетики - теории синтеза, надежности и сложности управляющих систем. Актуальность исследований в этой области обусловлена важностью многочисленных приложений, возникающих в различных разделах науки и техники. К числу основных модельных объектов математической теории синтеза, сложности и надежности управляющих систем относятся схемы из ненадежных функциональных элементов, реализующие булевы функции. Проблема построения схем наилучших (асимптотически наилучших) по надежности из ненадежных элементов является одной из наиболее важных и в то же время трудных в теории надежности управляющих систем. Тем более значимым представляется ее решение с дополнительным требованием к сложности таких схем, которое состоит в том, чтобы сложность оптимальных (асимптотически оптимальных) по надежности схем по порядку равнялась сложности схем, построенных только из надежных элементов. Эта задача в предположении, что функциональные элементы подвержены однотипным константным неисправностям либо только на выходах, либо только на входах элементов, рассматривается в диссертации. Исторически сложилось так, что сначала исследовались инверсные неисправности. Первые существенные математические результаты, касающиеся синтеза надежных схем из ненадежных элементов получил Дж. Нейман [42]. Он предполагал, что элементы подвержены инверсным неисправностям, когда функциональный элемент Е с приписанной ему булевой функцией е(ж) в неисправном состоянии реализует ё{х). Эти же неисправности рассматривались затем в работах Р. Л. Добрушина, С. И. Ортюкова, Д. Улига и некоторых других авторов [30, 31,35,36,37,43,44], причем главное внимание уделялось сложности схем (задача синтеза схем, наилучших или асимптотически наилучших по надежности, не ставилась). Речь идет о реализации булевых функций схемами из ненадежных элементов в произвольном конечном базисе Б = {ei,...,em}, т ? N [38]. Множество всех функциональных элементов Е^ функции которых е* принадлежат базису Б, будем также называть базисом Б [34]. Каждому элементу Ei базиса приписано положительное число v(Ei) - вес данного элемента Е{. Сложность схемы S определяется как сумма весов всех входящих в нее элементов и обозначается L{S). Предполагается, что все элементы схемы независимо друг от друга с вероятностью е подвержены инверсным неисправностям. Пусть Pjtu\(S,a) — вероятность появления значения /(а) на выходе схемы 5, реализующей булеву функцию /(ж), при входном наборе а = (<2i, ...,а„). Пусть P(S) — максимальное из чисел Pf(5)(?, *) ПРИ всевозможных входных наборах а. Назовем величину P(S) ненадежностью схемы S. Вводится функция Шеннона Lp^(n) = max minL(5), где минимум берется по всем схемам 5 из ненадежных элементов, реализующим функцию f{x 1,...,жп) с ненадежностью P(S) < р, а максимум - по всем булевым функциям f от п переменных. Нетрудно проверить, что для любой схемы S, содержащей хотя бы один элемент, при ? < 1/2 верно неравенство P(S) > e. Пусть р = minv(Ei)/(n(Ei) — 1), где минимум берется по всем элементам Ei базиса, для которых n(Ei) > 1, а п(Е{) - число существенных переменных функции е,-, реализуемой элементом Е^ г = 1,2,..., т. Для схем, реализующих булевы функции и состоящих только из надежных элементов (т.е. е = 0,р = 0), О. Б. Лупанов [33] показал, что Lofi(n) ~ р2п/п. Для построения надежных схем из ненадежных элементов, подверженных инверсным неисправностям с вероятностью е (0 < е < 1/6), Дж. Нейман [42] предложил итерационный метод реализации булевых функций. С помощью этого метода произвольную булеву функцию можно реализовать схемой, вероятность ошибки на выходе которой при любом входном наборе значений переменных не превосходит с - е (с - некоторая, зависящая лишь от базиса Б, константа), т. е. ненадежность схемы по порядку равна ненадежности одного элемента (такие схемы в теории надежности управляющих систем принято называть надежными). Сложность схемы с ростом числа итераций увеличивается экспоненциально. Любой метод синтеза схем из ненадежных элементов характеризуется двумя важными параметрами: вероятностью ошибки на выходе схемы (ненадежностью) и сложностью схемы. Оптимизация этих величин, т. е. построение наилучших по надежности и (или) сложности схем - цель исследований в теории синтеза, надежности и сложности управляющих систем. Поэтому наряду со сложностью надежных схем, которой уделялось главное внимание в работах ряда авторов, важным представляется ответ на вопрос: какова максимальная надежность схем, построенных из ненадежных элементов, подверженных тем или иным неисправностям? Задача синтеза схем, максимально высокой надежности, или схем, надежность которых близка к максимальной надежности, ни Дж. Нейманом, ни другими исследователями не рассматривалась. С. И. Ортюков [36] показал, что асимптотика функции Шеннона сохраняется для схем из ненадежных элементов при степенном убывании вероятности сбоев с ростом п, а именно, если последовательности рп и еп таковы, что QLg?n < рп < 1/2, 0 < еп < 1/2 и еп = о(1/п2), где Q > 1, Lg - минимальная сложность схемы из надежных элементов в рассматриваемом базисе, реализующей функцию голосования g{x\,X2,x$) = V х\х$ V а?2Я?з, то Из результатов Н. Пиппенджера [43] следует, что при инверсных неисправностях с вероятностью ошибки е < 1/200 любую булеву функцию от п переменных в базисе {&,V,"} можно реализовать такой схемой 5, что P(S) < 18г, L(S) ~ 170 • 2п/п. СИ. Ортюкову [37] удалось заменить требование еп = о(1/п2) условием еп < ?о, где ?q - некоторая константа. Сформулируем полученный им результат: если 0 < е < ?о, Lg'q(e) < р < 1/2, где q(e) = e+3e2-{-o(e2) при е —> 0, то существует такая функция р(е) —? р при е —> 0, что LP,?(n) ~ Р(е) • 2»/п. Д. Улиг [44] для инверсных неисправностей с вероятностью ошибки не более е доказал, что для любых с, b(c, b > 0) существует ? (е' 6 (0,1/2)) такое, что при любом ?, 0 < ? < е', и любом р, (1 + b)?Lg < р < 1/2 (точнее при любом р, q(?)Lg Lp,?(n) ^ (1 + с)р2п/п. С. И. Ортюков и Д. Улиг для инверсных неисправностей нашли методы синтеза схем оптимальных по сложности схем, функционирующих с некоторым уровнем надежности. Инверсные неисправности, о которых до сих пор шла речь, достаточно удобны для использования математического аппарата теории вероятностей. Однако реальные неисправности элементов более точно отражают другие математические модели неисправностей. Основной из них являются однотипные константные неисправности на выходах и на входах элементов. Однотипные константные неисправности на выходах элементов впервые исследовались в кандидатской диссертации автора [4]. Там же впервые был получен ответ на вопрос о надежности асимптотически наилучших (по надежности) схем, построенных из ненадежных элементов. Тог- да задачу построения схем, асимптотически наилучших по надежности, удалось решить лишь в четырех базисах из двухвходовых элементов. Вопрос о возможности построения асимптотически наилучших по надежности схем в других базисах, а также при других неисправностях элементов (опять же-таки однотипных константных неисправностях, но уже на входах элементов) оставался открытым. Прежде чем перейти к изложению материала настоящей диссертации, отметим еще две важные задачи из теории синтеза, надежности и сложности управляющих систем. С. В. Яблонский [41] рассматривал задачу синтеза надежных схем для случая, когда наряду с ненадежными конъюнктором, дизъюнктором, инвертором (е - максимум вероятностей их повреждений, 0 < е < 1/2) базис Б содержит абсолютно надежный элемент, реализующий функцию голосования д(х\,Х2,хз) = х\Х2 V х\х% V жг^з* Им доказано, что для любого р > О существует алгоритм, который для каждой булевой функции /(xi,..., хп) строит схему S так, что P(S) <ри L(S) ~ 2n~1/n (сложность схемы здесь и далее - число функциональных элементов в ней). Задача построения схем сколь угодно высокой надежности (когда P(S) -> 0) рассматривалась В. В. Тарасовым [39]. Для базисов из ненадежных функциональных элементов с двумя входами и одним выходом выявлены необходимые и достаточные условия, при которых произвольные булевы функции можно реализовать схемами сколь угодно высокой надежности. Из полученных Тарасовым результатов для базисов из двухвходовых функциональных элементов следует невозможность построения сколь угодно надежных схем для произвольных функций как при инверсных неисправностях, так и при однотипных константных неисправностях, которые определены ниже. В настоящей диссертации решается задача реализации булевых функций асимптотически наилучшими по надежности схемами во всех базисах из двухвходовых функциональных элементов при однотипных константных неисправностях только на выходах или только на входах элементов. Существенное внимание уделяется сложности схем. Введем необходимые понятия и определения* Рассматривается реализация булевых функций схемами из ненадежных функциональных элементов в конечном базисе Б [38]. Схема реализует функцию /(a?i,...,arn), если она реализует ее при отсутствии неисправностей в схеме. Предполагается, что каждый элемент схемы независимо от состояний других элементов может перейти в неисправное состояние. Определим однотипные константные неисправности на выходах элементов и на входах элементов. Если неисправность такова, что элемент (реализующий в исправном состоянии приписанную ему булеву функцию) в неисправном состоянии, в которое переходит с вероятностью 7 (7 < 1/2)» реализует константу О, будем называть ее неисправностью типа 0 на выходе элемента. Если же элемент в неисправном состоянии реализует константу 1, будем называть эту неисправность неисправностью типа 1 на выходе элемента. Если неисправность элемента такова, что поступающий на его вход нуль не искажается, а поступающая на его вход единица с вероятностью 7 (7 < 1/2) может превратиться в нуль, будем называть ее неисправностью типа 0 на входе элемента. Если же неисправность элемента такова, что поступающая на его вход единица не искажается, а — нуль с вероятностью 7 может превратиться в единицу, будем называть ее неисправностью типа 1 на входе элемента. Ненадежность P(S) схемы 5, реализующей /(ж), для указанных неисправностей определяется так же, как и для инверсных неисправностей, т. е. где Pf^(Syd) - вероятность появления значения /(о) на выходе схемы S при входном (произвольном) наборе а. Надежность схемы равна 1 — P{S). Обозначим P{f) = inf P(S), где S - схема из ненадежных элементов, реализующая булеву функцию /(ж1,...,жп). Схему А из ненадежных элементов, реализующую булеву функцию /(ж), будем называть асимптотически наилучшей (асимптотически оптимальной) по надежности, если Р(А) ~ P(f) при 7 —* 0, т. е. Р(А) , Будем считать веса всех элементов равными единице, и тогда сложность L(S) схемы S - число функциональных элементов в ней. Введем базисы { БА = ЬМ, Бъ = = {->,0}, Бп =¦{->. ©}i Бы = {V,l, ^is = {~,V,0}, ?i6 = {-,V,®}, При перечислении базисов использованы обозначения: х/у = хУ у, х 1у = хк.у, х ~ у = х&у V г&у, х ф у = xSzy V x$zy> х —> у = г V 2/, х -/* у = xSzy. Известно, что любой другой базис в Рг> содержащий функции не более чем двух переменных, например, базис Б^ = {&,V,~}, получается добавлением одной или нескольких функций к одному из базисов Б\ — Впервые задача синтеза схем, обладающих асимптотически (по 7) наилучшей надежностью, рассматривалась и была решена в кандидатской диссертации [4] и статьях автора [1, 3, 5] лишь для четырех базисов Б\, f>2, ?б> Б\8 при однотипных константных неисправностях на выходах элементов. В дальнейших исследованиях автора выяснялись возможности построения асимптотически наилучших по надежности схем в других базисах, а также при других неисправностях элементов (опять же-таки однотипных константных неисправностях, но уже на входах элементов). Существенное внимание в этих исследованиях уделялось и сложности надежных схем. Ответы на вопросы "Какова цена (стоимость) реализации функции схемой, асимптотически оптимальной по надежности? Как увеличится сложность такой схемы по сравнению со сложностью схемы, построенной только из надежных элементов?" были также впервые получены в статье [2] и кандидатской диссертации [4] автора для четырех вышеназванных базисов. Оказалось, что построение асимптотически наилучших по надежности схем возможно со сложностью, по порядку равной сложности схем, построенных только из надежных элементов. В настоящей диссертации задача синтеза схем, асимптотически наилучших по надежности, решена во всех базисах из двухвходовых функциональных элементов, за исключением ?7, ?g, Бю и Бп, при однотипных константных неисправностях на выходах элементов, и во всех базисах из двухвходовых функциональных элементов, за исключением Бд, Б^ и Бц, при однотипных константных неисправностях на входах элементов. Поскольку ненадежности двойственных схем равны (теорема 1.4, следствие 1.2), утверждения, доказанные в данном базисе Б для функции / при неисправностях типа 0 на выходах (входах) элементов, справедливы в двойственном базисе Б* для двойственной функции /* при неисправностях типа 1 на выходах (входах) элементов. Поэтому далее будем рассматривать только неисправности типа 0. Пусть Б - один из базисов Б\ - Бц, а в схемах возникают неисправности на выходах элементов. Теорема 1. Если 7 < d, то любую булеву функцию /(xi,__, хп) можно реализовать схемой S над Б, для которой P(S) < ay + by2, L(S) ~ с • 2n/n, где a, b, с, d - некоторые, зависящие лишь от базиса Б, константы, a ? {1,2,3,4}. Оценки теоремы 1 установлены конструктивно, т. е. представлены методы синтеза схем 5, удовлетворяющих указанным оценкам по надежности и сложности. Теорема 2. Базису Б можно сопоставить некоторый класс К булевых функций от переменных х\,..., хп и константы fc, h такие, что для любой функции / из К и для любой схемы 5, реализующей /, при ~f < г выполняется неравенство P(S) > ку -+- h'y2. Отвечающие базисам Б\ — Бц константы а, Ь, с, d, к, /i, r и классы К приведены в таблице 1. Константа г в некоторых случаях (их большинство) зависит лишь от базиса и типа неисправностей, а в других — еще и от схемы. В последнем случае соответствующее ей место в таблице содержит прочерк. Таблица 1 Б а Ь с d У к h г К Бх = {/} 2 98 224 1/600 11 672 2 -3 1/4 К2 Б2 = {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 к2 ?5 = {-»,А} 2 392 448 1/1200 12 1344 2 — — К3 Д? = {&Л 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 ?9 = {Ф,&,1} 3 966 672 1/1800 44 2016 1 0 1/2 Кх Б10 = {~,&,0} 3 390 672 1/1200 22 2016 1 0 1/2 Кг ^11 = {^Л 2 476 448 1/1200 28 1344 2 -4 1/6 к± ?i2 = {->,0} 2 476 672 1/1200 28 2016 2 -4 1/6 к2 ^13={-^,Ф} 2 476 448 1/1200 28 1344 2 — — Къ ^14 = {V,-} 2 506 448 1/1200 34 1344 2 — 1/4 к6 ?is = {~,v,o} 2 506 672 1/1200 34 2016 2 — Кгг ^16 = {~,V,®} 2 506 672 1/1200 34 2016 2 — — Кгг 5l7={©,V,l} 4 1137 672 1/1800 107 2016 1-й 0 1/2 Кг б18 = {&, v Л 1 7 40 1/125 — ¦ — 1 0 1/2 Кг Установлено, что при неисправностях на выходах элементов для всех базисов Бг — i>is, исключая i>7,i>9,i>io и Бп, константы а и к равны. Это свидетельствует о том, что соответствующие методы синтеза позволяют строить асимптотически (по 7) наилучшие по надежности схемы для почти всех булевых функций (при растущем п) в базисах Бг — 2>4> ?б> Бъ, Бгг, Бгг, Бг^—Бгъ и Бгъ со сложностью, по порядку равной слож- ности схем, построенных только из надежных элементов, и для некоторых классов булевых функций в базисах Б> и Бц. Таким образом, из теорем 1 и 2 следует Теорема 3. Схемы, построенные в теореме 1, являются асимптотически наилучшими по надежности для почти всех функций в базисах Б\ — .?>4, ?б9 #8> Бц, -^12» Б14 — Бы и Б\% (сложность этих схем по порядку равна сложности схем, построенных только из надежных элементов) и для некоторых функций в базисах Б$ и 2>1з. Константы Ъ и с не являются единственной парой, для которой теорема 1 справедлива. Их можно заменить константами Ъ' и d соответственно. Заметим, что "улучшая" одну из констант (например, Ь', что соответствует повышению надежности схемы), "ухудшаем" другую — с' (увеличивая сложность схемы). Опишим фигурирующие в таблицах 1 и 2 классы К\{п) — К\2{п). = Р2(п) \ ({0,1} U (U?=1 Xi))V = {/(a?i,..., хп) : / нельзя представить в виде f = (х{кд(хи...,хп))а}; Ki(n) = L(n) \ ({0,1} U (U?=1 х{) U (U?=1 Si)); K±{ri) = {/(a?!,... ,xn) : /нельзя представить в виде / = (я? V Кь(п) = {/(жх,.. .,жп) : /линейная функция, существенно зависящая не менее чем от трех переменных }; К(,{п) = {/(xi,..., хп) : / нельзя представить в виде Ki{n) = {/(a?i,..., хп) : f нельзя представить в виде / = (г,-V0(si,...,„))•};¦ К&(п) = Р2(п) \ ({0,1} U (иГ=1 Xi) U (и?=1 х{)); Кд(п) = {/(a?i,...,:?„) ::/ нельзя представить ни в одном из видов V х{]., V x{j) V Xi, V V xipi V х{. V V xip, V xit V V x{j V V xip; j=i i=i i=i p=i i=i p=i =i i=i p=i Х10(п) = {/(^i,..., xn) : / нельзя представить ни в виде / = ж? V^(ajb...,«„), ни в виде / = яг^ V р(жь... ,агп)}; = {/(a?i,...,жп) : / нельзя представить в виде yil) V ... V (arifc ~ 2/п))а, где 2/im G {xim,0,1}; К\г(п) = {/(aJi,..., хп) : / нельзя представить в виде / = (К ~ 2/н)а" V ... V К - З/н)0')0, где 2/im G {ximi 0,1}. Используемые обозначения имеют следующий смысл: / - булева функция от п переменных ari,... ,агп; -Рг^) (?(n)) ~ множество всех (соответственно всех линейных) булевых функций от п переменных; д — произвольная булева функция от п переменных; i,j,/,s,r,ii,ifc,ij,г/,гр,гУ Е {1,..., п}; о, oi,..., щ - булевы константы. При достаточно больших п классы К\{п) — Ki2(n), исключая К%{п) и Кь{п), содержат почти все булевы функции. Пусть теперь Б — опять же один из базисов Б\ — Бц, но в схемах возникают однотипные константные неисправности на входах элементов. Теорема 4. Если 7 < с/, то любую булеву функцию /(xi,..., яп) можно реализовать схемой 5 над 2>, для которой P(S) < cry* + &У+1> L(5) ~ с • 2п/п, где а, Ь, с, d, ? - некоторые, зависящие лишь от базиса 2>, константы, а € {1,2,4}, ? 6 {1,2}. Доказательство теоремы 4, также как и теоремы 1 - конструктивное. Теорема 5. Базису Б можно сопоставить некоторый класс К булевых функций от переменных х\,...,хп и константы k, Л,, t такие, что для любой функции / из К и для любой схемы 5, реализующей /, при 7 < г выполняется неравенство P(S) > куг + hyt+1. Фигурирующие в теоремах 4 и 5 константы и классы К приведены в таблице 2. Таблица 2 Б a 6 t с d V e к h r К Б, = {/} 2 392 1 224 1/1200 13 672 2 -1 1/4 Кг Б2 = Ш 2 9 2 2016 1/600 — — 2 -3 1/6 K7 ?з = {А,~} 1 144 1 448 1/600 15 1344 1 0 1/4 Кг Б, = {/Si 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 к8 ?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 ?9 = {e,&,i} 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 ^12 = {-+,0} 2 420 1 672 1/1200 18 2016 2 -4 1/8 Кго ?i3 = {-+,e} 2 923 1 448 1/1800 20 1344 1 0 1/2 Кг Би = {V,l 2 506 1 448 1/1200 34 1344 2 — 1/2 к9 ?i5 = {~,v,o} 2 447 1 672 1/1200 22 2016 2 — — к9 ^i6 = {-,v,e} 2 1680 1 672 1/2400 31 2016 2 — — к9 ^i7 = {e,v,i} 4 1050 1 672 1/1800 85 2016 1 0 1/2 Кг 5i8 = {&,v,-} 1 3.13 2 504 1/450 — — 1 0 1/2 Кг В каждом базисе константа t в теоремах 4 и 5 одна и та же. Константа г в некоторых случаях (их большинство) зависит лишь от базиса и типа неисправностей, а в других — еще и от схемы. В последнем слу- чае соответствующее ей место в таблице содержит прочерк. Теорема 4 будет справедлива, если константы Ъ и с заменить константами У и с' соответственно. Установлено, что для всех базисов Б\ — Бц, исключая Б$,Б\з и БпУ константы а и к равны. Это свидетельствует о том, что соответствующие методы синтеза позволяют строить схемы, асимптотически (по 7) наилучшие по надежности, для почти всех булевых функций (при растущем п) в названных базисах, причем сложность предлагаемых схем по порядку равна сложности схем, построенных только из надежных элементов. Таким образом, из теорем 4 и 5 следует Теорема 6. Схемы, построенные в теореме 4, являются асимптотически наилучшими по надежности для почти всех функций в базисах Бх — Б^, 2>ю — Бы, Бц — Б\ъ и Б^, причем сложность этих схем по порядку равна сложности схем, построенных только из надежных элементов. Напомним, что константа t равна двум только в базисах Бч и Б\% и — единице в остальных случаях. При t = 1 ненадежность схемы сверху и снизу оценивается функцией, по порядку равной j при 7 —> 0. Точнее, произвольную функцию можно реализовать схемой (см. теоремы 1 и 4), ненадежность которой асимптотически не больше ау (7 —>• 0). Если же функция / 6 if, то ненадежность любой схемы, ее реализующей (см. теоремы 2 и 5), асимптотически не меньше ку (7 —> 0). В том случае, когда а = к, схема S (см. табл. 1 и 2) для функции / 6 К имеет ненадежность, асимптотически равную а1 (7 ~ 0)» и является асимптотически наилучшей. При t = 2 имеем качественно другой результат. Ненадежность схемы оценивается (сверху и снизу) функцией, по порядку равной 72 при 7 —> • 0. Точнее, в базисе Бч произвольную функцию можно реализовать схемой (см. теорему 4), ненадежность которой асимптотически не больше 272 (7 ~^ 0)* Если же функция / ? Кт^ то ненадежность любой схемы, ее реализующей (см. теорему 5), асимптотически не меньше 272 (7 —>••()). Следовательно, схема 5, удовлетворяющая условиям теоремы 4, для функции / € .KV имеет ненадежность, асимптотически равную 272 (7 ~* 0)» и является асимптотически наилучшей по надежности. Аналогично, в базисе Б\ъ произвольную функцию можно реализовать схемой (см. теорему 4), ненадежность которой асимптотически не больше 72 (7 -* • 0).. Если же функция / G К\, то ненадежность любой схемы, ее реализующей (см. теорему 5), асимптотически не меньше 72 (7 ~~^ 0).-Следовательно, схема, удовлетворяющая условиям теоремы 4, для функции / G К1 имеет ненадежность, асимптотически равную 72 (7 ~* 0)» и является асимптотически наилучшей по надежности. Диссертация состоит из введения, четырех глав и списка литературы, содержащего 44 названия. Общий объем работы — 169 страниц, в работе содержатся 11 рисунков (они приведены в приложении) и 5 таблиц. Нумерация таблиц и рисунков - сквозная. В первой главе диссертации развита некоторая техника, используемая в дальнейшем для получения верхней и нижней оценок надежности схем, приведены необходимые определения и обозначения. Отметим наиболее важные утверждения. В теореме 1.2 показано, что ненадежность схемы оценивается снизу наименьшими вероятностями ошибок подсхемы, содержащей выход схемы. Эта теорема используется при доказательствах нижних оценок ненадежности схем. Теорема 1.4 утверждает, для двойственных схем на противоположных входных наборах вероятности ошибок равны. Следовательно (следствие 1.2), равны ненадежности двойственных схем. Поэтому утверждение о надежности, доказанное для функции / в данном базисе и при данном типе неисправностей, верно для двойственной функции /* в двойственном базисе и противоположном типе неисправностей. Во второй главе описываются методы синтеза надежных схем, с помощью которых получены верхние оценки ненадежности схем. В разделе 2.1 описывается метод синтеза надежных схем в базисе Б = {х/у}, который играет основополагающую роль, поскольку полученные для него результаты переносятся в другие базисы из двухвходовых функциональных элементов. Применение описанного метода приводит к построению надежных схем, которые, как будет показано в третьей главе, являются не просто надежными, а асимптотически наилучшими по надежности. В разделе 2.2 описаны методы синтеза надежных схем при неисправностях на выходах элементов. А именно, доказано, что в каждом из базисов Б\ — Б\$ при 7 < d! произвольную булеву функцию можно реализовать схемой, ненадежность которой не более 07 + У'у2. Константы о, Ь", d! — положительны, зависят от базиса и типа неисправностей, а €{1,2,3,4}. Нижние оценки надежности схем получаются из верхних оценок ненадежности сразу по определению надежности. В разделе 2.3 описаны методы синтеза надежных схем при неисправностях на входах элементов. А именно, доказано, что в каждом из базисов Б\ — Бц при j < d! произвольную булеву функцию можно pea- лизовать схемой, ненадежность которой не более ay-\-b" у1. Константы а, Ь", cFy.t — положительны, зависят от базиса и типа неисправностей, а €{1,2,4}, t€{l,2}. Нижние оценки надежности схем получаются из верхних оценок ненадежности сразу по определению надежности. Третья глава диссертации посвящена нижним оценкам ненадежности схем. Доказано, что надежные схемы, построенные во второй главе, являются асимптотически наилучшими по надежности во всех базисах, кроме 1>7> ^9> ?ю и Бп при неисправностях на выходах элементов, и i>9,i>i3 и Бц при неисправностях на входах элементов. Для получения нижних оценок ненадежности схем в базисе Б как при неисправностях на выходах элементов, так и при неисправностях на входах элементов используются следующие методы. 1. В схеме ?, реализующей функцию / 6 К(п), выделяется подсхема, содержащая выход схемы и обладающая тем свойством, что ее ненадежность не больше ненадежности схемы S и не меньше kyl + hyt+1 ПРИ 7 < т. Оценки для вероятностей ошибок на выходе схем и подсхем получены с помощью лемм 1.1 - 1.18 и теорем 1.1 - 1.3 первой главы. 2. Для схемы S, реализующей функцию / Е if(n), указывается набор значений входных переменных, на котором вероятность ошибки на выходе схемы не меньше ку + hyt+1 при у < г. В разделе 3.1 доказаны нижние оценки ненадежности схем в случае неисправностей на выходах элементов (см. теорему 2). Показано, что базису Б можно сопоставить некоторый класс К{п) булевых функций от переменных ж 1,...,жп и константы /г, h такие, что для любой функции / из К и для любой схемы S, реализующей /, при у < г выполняется неравенство P(S) > ky -\- hy2. Константы &, h, r {k ? {1,2,3}) приведены в таблице 1. Классы К(п) булевых функций f(x\,... ,жп) явно найдены и описаны. Эти классы, исключая Kz(n) и К^п), при больших п содержат почти все булевы функции. Установлено, что для всех базисов, за исключением Ej^Eq, Бю и Бп, константы a vi k равны. Это свидетельствует о том, что соответствующие методы синтеза позволяют строить асимптотически наилучшие по надежности схемы для почти всех булевых функций в базисах 2>i — Б4, i>6, i>8> Бц, ?i2, ?14 — ?16 и ^18 и Для некоторых классов булевых функций в базисах Б$ и Б^. Верхние оценки надежности схем получаются из нижних оценок не-

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

Цена, в рублях: (при оплате в другой валюте, пересчет по курсу центрального банка на день оплаты)	1425

Скачать бесплатно	23608.doc

Найти готовую работу

ЗАКАЗАТЬ

Обратная связь:

Связаться

Вход для партнеров

Регистрация

Восстановить доступ

Материал для курсовых и дипломных работ

15.04.24 Задачи, условия и этапы организации экспериментальной работы

15.04.24 Критерии качества преподавания

15.04.24 Категория нормы в обучающей деятельности

Архив материала для курсовых и дипломных работ

Ссылки:

Счетчики:

© 2006-2022. Все права защищены.
Выполнение уникальных качественных работ - от эссе и реферата до диссертации. Заказ готовых, сдававшихся ранее работ.