В.Б. Алексеев, А.А. Вороненко, С.А. Ложкин, Д.С. Романов и др. - Задачи по курсу «Основы кибернетики» (скан) (1132786), страница 7
Текст из файла (страница 7)
Пусть для каждого г, 1 = 1,..., Ь, известно распределение реж боп]м ФЭ Е„то есть длЯ каждого У, У' = 1,..., 2г ', известна и равна веРоятность того, что ФЭ Е' Реачизует 2-ю булеву функцию от бу переменных им..., иь (ссли считать, что все булевы функции от переменных им..., иь упорядочены в соответствии с номерами их столбцов значений). При нахождении ненадежности схемы Е над базисом В будем считать, что все се ФЭ переходят в свои состояния независимо друг от друга и что любое состояние СФЭ Е определяется состояниями ФЭ Е (см.
э 5). В соответствии с этим на основе введенных выше соотношений (6.1)-(6.4) можно найти значения ненадежности Е(Е) и г](Е) для СФЭ Е, а также распределенно режимов ее работы и функцию дп(хм..., х„). Считается, что функция У(хм..., л„) допускает сколь угодно нас]еж'нрю реалпзацию в базисе В, если для любого г, г > О, сущсствуст СФЭ Е над В, которая реализует 1 и для которой Е(Е) < г.
Повышение на дежности при реализации ФАЛ Дхм..., х„) возможно, если в базисе В имеется абсолютно надежный ФЭ Е„реализующий функцию голосования т(зь хъ хз) = х|хгЧ х|хгм хгхг (см. (12)). Действительно, если СФЭ Е реализует У и г](Е) = г, то для кспадсжности СФЭ ЕО], показанной -на рис. 26 а), которая тоже реализует у, имеет место равенство г](Е( )) = Н(г) = Овг — 2гг (график функции т = Н(г) показан на рис. 26 6)). а) Рис. 26. цииН г стим "то Н(0) = О, Н (-') = -', что псрвыс две производные функ- Н(г) на отрезке г1О; -,] неотрицательны, причем Н'(0) = Н" (Ц = 0 и Н «01 > 0 и «то П(Е0)) < 4, если е < -,'. ПоэтомУ РекурсивРй но применяя укезаину езаиную процелуру повышения надежности к СФЭ Е результатом которо явл . торой является СФЭ Е)"4'), й = 1, 2, ..., построим последовательность СФЭ Е«').
Е)2).... Е("), ..., реализующих 1, для которой ц(Е[ )) = Н(«)(Е«" ц)) О. Заметим также, что СФЭ Е«") содержит 3 подсхем вида Е и 1+ 3+ Аналогнчиые построения и оценки применимы н для повышения Е- ненадежности СФЭ. 7 1. 1) Доказать, что 4(М) = «)(М) тогда и только тогда„когда для М существует проверяющий тест длины 1. 2) Доказать. что функция 1 допускает сколь угодно надежную реализацию в азисе базисе Б тогда и только тогда, когда для любого е, е > 0, гушесгвуег СФЭ Е над Б, которая реализует «и для которой «)(Е) < е, 3' Д, что для вычисления ненадежности г)(Е) в соответствии 3) Доказать, что для (6,3) " СФЭ Е над базисом Б достаточно знать ненедежностя вида ь' 4=1 ...
Ь. Е(Е„«У) для всех ФЭ Е, базиса Б и всех наборов р из В, 4' = 1,..., . 7.2. Ниже указана СФЭ Е и распределения режимов работы ее ненадежных ФЭ. Найти распределение режимов работы СФЭ Е, а затем вычислить Е(Е), «),'Е) и функцию «)н. 1) Š— СФЭ на рис. 22 а), где конъюнктор работает абсолютно надежно, а распределения режимов работы дизъюнктора и« ч иг и инвертора )«и, «иг и« 43и2 ) ( й, и« ) й, имеют, соответственно, внд 1 3 4 4 2) Š— СФЭ на рис.
23 а), где дпзъюнктор работает абсолютно надежно, а распределение режимов работы конъюнктора и«йиг имеет внд и«йиг й« 3) Š— СФЭ на рис. 24 а), где конъюнктор работает абсолютно надежно, а распределение режимов работы дизъюнктора и« ««иг имеет вид < и«)«иг и«4«иг 2 1 з з лютно 7.3. 1) Пусть в СФЭ Е на рис. 22 а) дизъюнктор работает абсолют надежно, а распределения режимов работы конъюнктора и«азиз и инвер) Известно, тора й« имеют, соответственно, вид «1 и з 1 . Изве 1 — РР-,4 что вероятность такого фУнкционирования схемы, при котором выходах схемы реализуются тождественные нули, равна -', Най „, 2) Пусть Распределен««я Режимов работы конъюнктора и«3«и и диз, юнктора и« '««иг в СФЭ Е на рис.
23 а) имеют впд «' и«йиг 1 ) — ) < , соответственно. Известно, что вероятность такого функ- и«'4 иг х 1 з з ционирования схемы, при котором на выходе Е реализуется тождественная единица, равна —. Найти р. 7,4, Пусть базис Б состоит из ФЭ, реализующего функцию голосования, который работает абсолютно надежно, и конъюнктора и«3«иг, рас/и«йиг 1~ пределение режимов работы которого нмеет вид « з з 1) Достаточно ли 40 функциональных элементов, чтобы реализовать функцию и«34иг с ненадежностью не более 0.1? 2) Достато пю ли 400 функциональных элементов, чтобы реализовать функцию и«3«иг с ненадежностью нс более 0.002? 7.6." Ниже приведены распределения режимов работы ФЭ Еп г = 1, ..., Ь, ненадежного базиса Б. Покажите, что в данном базисе возможна сколь угодно надежная реализация произвольной функции.
( и«9 из й« '«иг 1 — р 2) Ь = 3, Е«: ' , Ег: , Ез: Другой (так называемый логика-комбинаторный (12)) подход к определению уровня надежности схемы связан с понятием самокорректируемости. Схема Е называется сал«охаррехтирующейсл о«лнасительна источника неисправностей И, если в модели (Е, И) все состояния эквивалентны. Естественно считать, что чем больп«е неисправностей корректирует схема Е, тем выше уровень ее надежности. Задача синтеза самокорректиру«ощихся схем является важным частным случаем общей задача синтеза. Рассмотрим задачу синтеза контактных схем, которые являются самокорректирующимися относительно источника неисправностей И«и (см, 3 6) Простейший способ решения этой задачи связан с последовательным и (или) параллельным дублированием двухполюсной КС. Легко видеть, 2) гп = 1,1 = 7 Е: пб) 1 б) Рис, 27 3) гп = 1,1 = рй Е: , эсти гри этом взять 1 экземпляров самокорректирующейся относи„ьно Ц„КС Е и соединить их последовательно (параллельно), то полгчим эквивалентную Е КС Е', которая является самокорректирующей ся относительно Илл, где Я = г, Я = (э+ 1) 1 — 1 (соответственно В = (г + 1) 1 — 1, 5 = э).
Аналогичный результат дает указанное выше дублирование, если его применять к каждому контакту схемы (этот спо«сбом можно строить многополюсные самокорректирующиеся КС), Другой способ перехода от (многополюсной) КС Е к эквивалентной ей КС Е', которая является самокорректирующейся относительно И л „ гле о б (0.1), заключается в следующем. Разобьем КС Е на непере. сскающисся связные (многополюсные) подсхемы Е(,.... Е), каждел из которых состоит нз контактов одного типа, а затем заменим КС Е,, 1 = 1....,(, на КС Е'„состоящую из контактов того же типа, которая пРедсгавлает собой цикл, пРоходащий чсРнэ все веРшины и('),, ц(ь|) КС Е„если и = 1 (см.
Рис, 27 а)) и звезду с центром в новой вершине, соединеннойсовсемивершинамно,',...,и,', КСЕ„еслис =0(см.рис.276)). (() (() 7,6. 1) Доказать, что если функция х,, где 1 < 1 < и и и б (О, 1) может быть получена из функции 7'(х(, ..., х„) в результате некоторой подстановки констант вместо БП х„..., х; м хм м ..., х„, то в любой КС, реализующий 7" и корректирующей г обрывов (г замыканий), содержится не менее (г + 1) контактов х, . 2) Построить для функции х(Щхэ минимальную КС, корректирующую а) одно размыкание, б) одно замыкание.
7.7. По контактной схеме Е построить эквивалентную „ тную схему, корректируюшую замыкание т контактов и содержап0(ю не более 1 кон а 1) пт = 1,1 = 6 Е: у„8. По «онтактной схеме Е построить вквивалентнувз схему, коррек тнруаннувз размыкание (обрыв) тв контактов и содержащувз ие бои, контактов 1) нт = 1,1 = 10 Е: 2) тн = 1. 1 = 4 Е: 4) нт = 1, 1 = 8 Е: 5)та=1,1=4 Е: 6) тн = 1, 1 — 0 Е: т 9 Построить по КС Е эквивалентную ей КС Е', корректирующую ц одно размыкание 2) одно замыкание и такую, что а) цЕ ) < 30, соли Š— КС на рис. 28, б) цЕ ) < 23, если Š— КС на рнс, 29, в) ЦЕ') < 28, если Š— КС на рис. 30.
— 1,1=-10 Е: 8) тл = 1Л = " Е: Рис. 29. Рис, 28. х2 х4 х~ хз хг хэ х4 Рис, 31. Рис. 30. 7.10. Рассматривается КС на рис. 31. 1) Построить по этой схеме КС не более чем из 13 контактов, коррек- тирующую а) одно размыкание, б) одно замыкание, 2) Построить для функции, реализуемой этой схемой, минимальную КС, корректирующую а) одно размыкание, б) одно замыкание. Ь а Рис. 33. Рис.
32. Рис. 35. Рнс. 34. 88 пчгх х х ) = х.хз ггхгхз У хзхз построить КС 711 ° Для функции пз(хм м 3 сложности 8, корректирующую а) одно размыкание, б) одно замыкание. 2и 3( этих схем представлены на рис. 3 и 3 Указание. Каркасы эти отвеяно). 7.12.' Доказать, что минимальная корректирующ д р ая о но езмыкание КС для линейной булевой функции, существенно зависящ ися ей от всех своих и переменных, имеет сложность 4п (КС, реализующая эту функцию, представлена на рис. 21). 7.13. Рассматривается КС на рис. 34. Построить по этой схеме КС, ю сложность не более 16. корректирующую одно размыкание и имеющую 7,14.' Для элементарной симметрической функции тре Р ии т х переменных х Чх х хз построить срабочим числом два озз(хмхз,хз) = хгхзхзЧх~хзхз г з с КС. Указание. Каркас минимальную корректирующую одно размыкание КС.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
