В.Б. Алексеев, А.А. Вороненко, С.А. Ложкин, Д.С. Романов и др. - Задачи по курсу «Основы кибернетики» (скан) (1132786), страница 6
Текст из файла (страница 6)
По умолчанию считается, что Й = Е. 6,1. Тесты для контактных схем 6,1. Построить все тупиковые диагностические тесты для КС на рис. 10 и источника неисправностей, допускающего обрыв одного из контактов вида х. х Ь Рис. 11 Рис. 10 у й х Ь х й Ь х У 2 а Ь а у у Рис. 12, Рис. 14. Рис. 13. 6.4. Построить все тупиковые а) проверяющие б) диагностические тесты для КС па рнс. 13 и источника неисправностей, допускающего одну из следующих неисправностей; обрыв контакта г, обрыв выделенного контакта з и замыкание выделенного контакта у. 6.5. Построить все тупиковые а) проверяющие б) диагностические 6.2. Построить все тупиковые а) проверяющие б) диагностические тесты для КС на рис.
11 и источника неисправностей, допускающего размыкание контактов вида Х, х, а также замыкание контакта вида у, причем общее число неисправных контактов не может быть больше 1. 6.3. Построить все тупиковые а) проверяющие б) диагностические тесты для КС на рис. 12 и источника неисправностей, допускающего обрыв одного контакта переменных х, г. 39 тесты для КС на рис.
14 с единичным источником неисправностей, допускающим обрыв контактов вила:, й или замыкание контакта вида р. 6.6. Построить все тупиковые диагностические тесты для КС на рис. 15 и источника неисправностей, допускающего замыкание одного из контактов вила х, р, р. Рис.
17. Рис. 16, Рис. 15. 6.7. Построить все тупиковые а) проверяющие б) диагностические тесты для КС на рис. 16 и источника неиспрввностей, допускающего замыкание одного контакта переменных у, г. 6.8. Построить все тупиковые а) нроверяющне б) диагностические тесты для КС на рис. 17 н источника неисправностей, допускающего размыкание одного контвкта вида х, у или 2. 6.9. Пусть в днухполюсной КС Е от переменных х1,..., хп для любого небора а = (о1,..., оп) из Д17 найдется единственная не содержащая контактов вида х1 ',..., х„" цепь С„, соединяющая полюса. Пусть источник неисправностей И допускает обрыв не более, чем одного из контактов к1,..., /г, ! КС Е и порождает при этом э отличимых состояний. 1) Доказать, что множество наборов Т, Т С В", образует проверяющий тест для (Е, И) тогда и только тогда, когда для каждого контакта Й,«! = 1в..., (э — 1), найдется цепь С„а 6 Т, проходящая через него.
2) Доказать, что множество наборов Т, Т С В", образует диагностический тест для (Е, И) тогда и только тогда, когда оно образует проверяющяй тест и для любых двух контактов Ц и Й!ч где 1 < ! ( у < (э-1), найдется такой набор а, а 6 Т, что цепь С проходит через один из этих контактов и не проходит через другой. и — г Хп-г — 1 Хп- Хп-г+1 Х«-г Хп-г 1 Хп-г Хп-в+1 Хп-г+2 Хп-«+1 Хп-г 2 Хп-2 Уп-! Хп-1 Хп ! Хп х„ ! х„ Рис. 18 х; а хг х Хв+1 хп! х Рис. 19 х Х2 а Хп «1 Х хг Хв Хп-1 Хп 1 Ь Хп Х«4.«-1 хп+в Х2«-2Х2п х; хп ! Рис. 20 6,10,' Рассматривается построенная но методу касквдов КС Я" (см. и рнс 18), реализующая элементарную симметрическую функцию от и переменных с рабочим числом г (т. е.
функци!о, принимающую значение 1 нв всех наборах из Вп и только на них), Ц Используя результат задачи 5.12, получить нижнюю оценку вида Ы' г! для длины единичного диагностического теста рвзмыкания данной схемы. 2) Показать, что для Я„" существует единичный диагностический тест раэмыкання длины, нс превосходящей 2п — 2. 6.11.
Найти длину минимального единпчного проверяющего теста для раэмыкания контактов в КС на рис. 19. 6,12. Рассматнвается КС на рис. 20. 1) Найти длину минимального единичного проверяющего теста для размыкания. 2) Построить такой единичный тест размыкания для контактов вида х1,..., хп, х1,.... хп, Длина котоРого не пРевосхоДит величины (!ойг и~!+ 2.
40 41 Йж ~ 2ь~ Рис. 21. 6.13. На основе контактного дерева построена КС для функции У(х!,..., хн) = х, !Э тз Я ... !Э х„. ДлЯ этой схемы найти ДлинУ ми- нимального единичного теста а) размыканпя, 6) земыкания, в) как рвзмыкания, так п замыкания. 6.14. Единичной с4срой с центром в точке а, а 6 В", называется множество всех наборов куба В", отличающихся от набора а только в одной координате. Докажите, что длина мииил!альиого единичного теста резмыкаиия для произвольной КС, реализующей характеристическую функцию единич- ной сферы куба В", не меньше п. Покажите, что указанная оценка да- ст!!Жима.
6.15.* Докажите, что для функции у(х!,..., х„) = х! 9 хе 9... Юх„не существует КС от и переменных, имеющей полный тест длины меньшей, чем 2". 6.16.' Рассматривается построенная по методу каскадов КС Е„, ре- ализующая линейную функцию х! 9 х2 Ю . 9 х„91 при п > 3 (см. рис.
21). 1) Докажите эквивалентность единичных замыканий одноименных . контактов. 2) Найдите длину минимального едииичиого проверяющего теста а) замыкания, 6) размыкаиия, в) как размыкаиия, так и замыкания. 3) Постройте асимптотически минимальный единичный тест замыка- ния.
4) Постройте единичный тест рвзмыкаиия, двина которого ие превос- ходит а) 2)обтп+7, б) 12!обтп+10. 6,17.' Доказать, что любую булеву функцию можно реализовать КС, допускающей единственный полный проверяющий тест, состоящий из всех набоРов 6.2. Тесты для схел! из функциональных элементов 6.18. 1) Построить минимальный единичный диагностический тест относительно константных неисправностей иа выходах ФЭ схемы иа рис. 22 а), 6)з и укнзать число таких тестов.
2) Построить минимальный единичный проверяющий тест относительно константных неисправностей на выходах ФЭ схемы на рис. 23 а). 3) Построить минимальный единичный проверяющий тест относительно константных неисправностей на выходах ФЭ схемы па рис. 24 а).
4) Построить мвнимальный проверяющий тест относительно константных неисправностей на выходах тех ФЭ схемы иа рис. 25, которые содержат входы схемы. 6.19. 1) Показать, что тест, проверяющий константные неисправности на выходах ФЭ, среди входов которых есть либо входы схемы, либо ветвящиеся выходы функциональных элементов, является проверяющим тестом для константных неисправностей иа выходах всех ФЭ схемы (при этом предполагается, что базис ие содержит ФЭ, реализующих константы). 'Прн изображении схем нз функциональных элел4ентов в настоящем пособии лействугот правила! 1) обе!ими точками проводников могут яшшться лишь точки выходов функциона4!ь. ных элементов, 2) входы каждою функционального элемента упорядочены слева наораво, 42 ге г~ г( те в) Рис.
22. Схема сумматора Е„ Схема Е„: хг У~ Яв Яч Уг 1Ь тс б) Рис. 23. а) Схема Е„: Е2 а а) Рис. 24. 2) Показать, что СФЭ на рис. 25 является примером схемы, для которой единичный тест, проверяющий константные неисправности на выходах лишь тех ФЭ, среди входов которых есть входы схемы, не является единичным проверяющим тестом для константных неисправностей на выходах всех ФЭ схемы.
6.20.' Реализовать линейную функцию х~ 9хт9...9х СФЭ в стандартном базисе, допускающей единичный тест из четырех наборов, проверяющий константные неисправности на выходах ФЭ схемы. 6.21.' 1) Доказать, что длина минимального единичного теста, диагностирующего конствлтные неисправности на выходах ФЭ схемы сумматора Е„при и > 3 (рис. 22 в)), равна 5.
2) Схема Е„на рис. 23 б) имеет сложность 4п — 3 и вычисляет старший разряд гс суммы лев~... г„двоичных чисел х~... х„и у~...у„(схема Е, представляет собой конъюнктор). Доказать, что длина минимального единичного теста, проверяющего константные неисправности на выходах ФЭ схемы Е„, равна 2п. 3) Построить единичный тест, проверяю- х~ хт ха ях щий константные неисправности на выходах ФЭ схемы Е„на рис.
24 б), имеющий длину не более 4. 6,22.' Показать существование такого базиса из ФЭ, в котором для любой булевой функции и переменных существует схема, допускающая единичный проверяющий константные неисправности на выходах ФЭ тест длины, не превосходящей п + 1. 6.23.' Доказать, что длина полного проверяющего теста для входов и-входовой схемы не превосходит 2п. Показать неулучша- ч емость предыдущей оценки для некоторой функции.
Рис. 25. 6.24.' Показать, что, начиная с некоторого и, любая булеза функция и переменных обладает схемой, допускающей нетривиальный единичный тест, диагностирующий константные неисправности на выходах ФЭ. 6.25. Покажите, что минимальный проверяющий единичные константные неисправности на выходах ФЭ тест для произвольного дешифратора (для произвольного универсального многополюсника) состоит из всех наборов, 7. Оценка надежности схем. Самокорректирующиеся схемы.
Для определения уровня надежности схемы часто применяется вероятностный подход (см., например, (6, 12)). Пусть М = (Е, И) — непа дежная схема Е от переменных хм ..,, я„, переходящая под действием источника неисправностей И в состояния Е = Е , Е ,..., Е ', в кото- 11) (2] ЕО) рых реазизуются функции г = г О]. г 1~],..., г О] соответственно, определенные на множестве наборов АГ = (Д,..., ]3р). Пусть дачее вероятность того, что схема Е находится в состоянии Ев],известна и равна яо где 1= 1,...,1, 0 < т, < 1 н ~,', щ = 1. Введем следующие величины, характеризующие ненадежность схемы Е в модели М: Е(М)= ') (6.1) Е(М,]1) = С (6.2) мам] и ие як~к~ где ]3 6 А", а затем положим г](М) = шах с(М,]у), (6.3) чм(з] х ) =ь(М (хм х )).
( -4) Заметим, что величина Е(М) (ЯМ,]1)) задаст вероятность того, что схема Е реализует функцию, нс равную Г (аютветственно не равную Р на наборе 6), и поэтому г](М) < Е(М) < рг](М), (6,5) откуда следует, в частности, что й(М) = 0 тогда и только тогда, ко- гда ((М) = О. Схема Е счнтается абсолюп]ио надежной в модели М, если ц(М) = 0 (или ((М) = О), Это означает, что все состояния схе- мы Е, имеющие положительную вероятность, эквивалентны Е. Функция йм(х],..., х„) называется функциеб вероятношпи неправильного сраба- шмеания схемы Е. В дальнейшем, при записи введенных величин вместо пары М = (Е, И) будем писать просто Е, если из контекста ясно, какой источник неисправностей имеется в виду, Рассмотрим вероятностный подход на примере ненадежных СФЭ над базисом В = (Е;Я „где ФЭ Е, реализует булеву функцию д(им..., иа).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
