|
Побудова мінімальних перевіряючих тестів (МПТ) та ⇐ ПредыдущаяСтр 2 из 2 Мінімальних тестів пошуку несправностей (МТПН)
Побудова мінімальних перевіряючих тестів (МПТ)
Мінімальний перевіряючий тест будується в два етапа: 1. будується усічена ТФН, в яку входять тільки рядки, які відповідають перевіркам вихідних елементів; 2. в МПТ включається мінімальна кількість перевірок вихідних елементів ОД, рядки яких спільно покривають нулями всі стовпчики несправних станів ОД. В прикладі, що розглядається вихідними є елементи 4 і 5. Усічена ТФН для них має такий вигляд (таблиця 2.2):
Таблиця 1.2
Перевірка π5 покриває нулями всі стовпці несправних станів ОД, тому в МПТ входить тільки ця перевірка. Це означає, що для визначення справного чи несправного стану ОД достатньо виконати тільки одну перевірку π5.
Побудова мінімального тесту пошуку несправностей (МТПН) Побудова мінімального тесту пошуку несправностей (МТПН) будується в чотири етапи: 1. визначення множини обов’язкових перевірок; 2. побудова усіченої ТФН для множини обов’язкових перевірок; 3. побудова таблиці перекриттів; 4. визначення множини додаткових перевірок.
1. Визначення множини обов’язкових перевірок. В склад обов’язкових перевірок включаються: – Перевірки вихідних елементів, які увійшли в МПТ; – Перевірки інших елементів, які визначаються наступним чином. Якщо в ЛМ ОД є два елементи i та j та вихід елемента i з’єднаний тільки з входом елемента j, то перевірка πі включається в число обов’язкових, в протилежному випадку перевірка πі в число обов’язкових не включається. Для прикладу, що розглядається в МПТ включається перевірка тільки одного вихідного елемента, перевірка π5, яка повинна бути включена в множину обов’язкових перевірок Поб. З перевірок елементів ОД які не є вихідними, в число обов’язкових включаються перевірки π1,2 та π3, так як вихід елемента 12 з’єднаний тільки з входом елемента 3, а вихід елемента 3 – тільки з входом елемента 5. Перевірки елементів 11 та 2 не включаються в число обов’язкових, тому що виходи цих елементів з’єднані з входами двох елементів. Таким чином,
2. Побудова усіченої ТФН. Наступним етапом побудови МТПН є побудова усіченої ТФН, в яку включаються тільки рядки обов’язкових перевірок (табл. 2.3)
Таблиця 1.3
З аналізу таблиці 2.3 випливає, що в усіченій ТФН для множини Поб існують дві пари нерозрізнених стани: 3.1 Побудова таблиці покриттів. Для розрізнення пар нерозрізнених станів будується таблиця покриттів і визначається множина додаткових перевірок Пдод. Таблиця покриттів це прямокутна матриця (див. табл. 2.4), число стовпців якої дорівнює числу пар нерозрізнених станів, а число рядків дорівнює числу перевірок які не увійшли в число обов’язкових. В клітинах таблиці записується символ 1, якщо перевірки πі розрізнюють стани, які увійшли в ту чи іншу пару станів, і символ 0 – в протилежному випадку. Таблиця 1.4
3.2 Визначення множини додаткових перевірок. В множину додаткових включається мінімальна сукупність перевірок елементів, які не увійшли в число обов’язкових і які спільно покривають одиницями всі стовпці таблиці покриттів. Для прикладу, що розглядається можливі дві додаткові перевірки: Якщо в усіченій ТФН є декілька однакових стовпців несправних станів sі, sj та sk то стовпці таблиці покриттів позначуються всіма можливими сполученнями пар станів, тобто парами станів 4 Визначення МТПН. Мінімальний тест пошуку несправностей визначається шляхом об’єднання множини обов’язкових і додаткових перевірок МТПН Поб і Пдод. Для прикладу, що розглядається, можливі дві множини додаткових перевірок, тому існують два МТПН:
Побудова раціональних умовних алгоритмів Пошуку несправностей
При умовних алгоритмах пошуку несправностей (АПН) вибір кожної наступної перевірки виконується із врахуванням результату попередньої перевірки. Найбільш зручною і наочною формою представлення умовних АПН є направлений граф, вершини якого відповідають станам процесу пошуку несправностей, а дуги показують, в якому стані в залежності від результатів перевірок здійснюється перехід на даному кроці процесу пошуку. Для одного ОД існує багато умовних АПН, серед яких існує оптимальний, який забезпечує в середньому мінімальний час пошуку несправностей. Однак для побудови оптимального умовного АПН необхідний перебір великої кількості можливих АПН. Тому на практиці використовуються так звані раціональні умовні алгоритми АПН, які дозволяють отримати результати, що близькі до оптимальних. Раціональні умовні алгоритми пошуку несправностей (РУАПН) засновані на правилі (критерії), за допомогою якого вибирається наступна перевірка на кожному кроці процесу пошуку несправностей. Критерії вибору перевірок, що використовуються в РУАПН можуть бути різними в залежності від особливостей ОД чи від повноти інформації об ОД. Звичайно вважається, що при побудові РУАПН існує наступна інформація об ОД: - логічна модель чи ТФН ОД; - множина перевірок П={ πі }, що є тестом пошуку несправностей ОД (не обов’язково мінімальним); - множина Т={ tі } значення затрат часу на виконування кожної з перевірок πіÎП; - множина Q ={ qі }значень ймовірностей несправних станів елементів ОД. В якості критеріїв вибору перевірок РУАПН використовуються наступні критерії: 1. Якщо відомі значення ймовірностей несправних станів елементів ОД, використовується критерій:
де:
Цей критерій забезпечує побудову РУАПН в середньому за мінімальну кількість кроків (перевірок).
Для того щоб забезпечити мінімальний середній час відшукання несправності використовуємо критерій виду:
де tі – середня тривалість перевірки pі. Якщо припустити, що ймовірності несправних станів елементів ОД однакові чи інформація про ці ймовірності відсутня, можна використати критерій:
чи
де
3. Приклад побудови раціонального умовного алгоритму Пошуку несправностей
Нехай для прикладу, що розглядається вище дані наступні значення ймовірностей несправних станів: q1=0.4, q2=0.15, q3=0.1, q4=0.2, q5=0.15, а також наступні значення затрат часу на виконання перевірок елементів ОД: t1=20 хв, t2=30 хв, t3=40 хв, t4=50 хв, t5=60 хв. У якості тесту пошуку несправностей виберемо раніше отриманий
РУАПН будується в наступній послідовності: 1. Побудувати усічену ТФН для множини перевірок, що є тестом пошуку несправностей. В якості такого тесту вибираємо тест Таблиця 3.1
2. Побудуємо таблицю розрахунку РУАПН (див. табл. 3.2), в першому стовпці якої записуємо множину 3. Використовуя ЗТФН (табл. 3.1) визначити множину перевірок, придатних до множини S. Придатними до множини S називаються перевірки πі, які виділяють на множині S непусті підмножини Наприклад, перевіркою π1,2 на множині Всі придатні перевірки записують в стовпці 2 таблиці 3.1, а підмножини в стовпцях 3 і 4. 4. Для кожної з перевірок Вважаємо що
Для перевірки π1,2 отримаємо:
Для перевірки π2 маємо: Для перевірки π3 отримаємо: Таблиця 3.2
В якості оптимальної вибирається перевірка, для якої значення розрахованого критерію мінімально. Такою перевіркою є перевірка 5. Відповідні оптимальній перевірці 6. Якщо в стовпчику 1 табл. 3.2 є підмножини, для яких оптимальні перевірки не визначені, прийняти цю підмножину в якості множини S і для кожної з цих підмножин виконати п.п. 3...5 даного алгоритму. В противному випадку перейти до виконання наступного пункту. Виконаємо п.п. 3...5 алгоритму для підмножини
Розрахуємо значення критерію для цих перевірок: Для перевірки
Для перевірки В якості оптимальної вибираємо перевірку Використання для підмножин У відповідності з п.3 алгоритму визначаємо придатні перевірки для цих підмножин. Для кожної з зазначених підмножин існує єдина придатна перевірка В результаті виконання перевірки 7. Побудувати граф отриманого РУАПН, який має вигляд, приведений на рисунку 3. Аналогічним чином виконується побудова РУАПН, якщо для розрахунку критерію вибору перевірок використовуються формули (2), (3) і (4).
Рисунок 3 4. Вироджене покриття Одержимо вироджене покриття і d-куби, наприклад логічної функції трьох аргументів Перевести десяткове число 206 в двійкову систему числення:
Навести таблицю істинності функції Таблиця 4.1
Одержати мінімальну диз’юктивну нормальну форму заданої функції Використовуючи діаграму Дейча маємо:
Рисунок 4. Діаграми Дейча функцій Записати одиничні та нульові куби виродженого покриття, виходячі з мінімальної ДНФ функцій
Таблиця 4.2
Одержати d-куби функції шляхом порозрядного перетину одиничних та нульових кубів виродженого покриття:
![]() ![]() ![]() ![]() ![]() Привести умовне графічне позначення логічного елемента, який реалізує функцію
Рисунок 5. Функціональна схема та умовне графічне позначення елемента
5. Визначення вхідного набору 1. Вивчити сутність операції просування вектору стану схеми ДП до входів і виходів [1], стор.32-36. 2. Вивчити алгоритм визначення вхідного тестового набору, який виявляє задану несправність [1], підрозділ 4.2. 3. Розв’язати задачу 5 згідно заданому варіанту. 4. Розглянемо методику розв’язання задачі 5 на прикладі схеми дискретного пристрою, наведеної на наступному рисунку. Рисунок 6. Функціональна схема дискретного пристрою Послідовність розв’язування задачі наступна: 1. Виконати ранжування елементів схеми, тобто пронумерувати елементи схеми наступним чином: - входам ДП присвоїти молодші номери 1, 2 і 3 (цифри в дужках на рисунку), а виходам логічних елементів (ЛЕ) присвоїти наступні номери – 4, 5,...,9. 2. Визначити d-куб заданої несправності Виконати перетин цього набору при умові, що несправність має місце з тестовим набором справного елементу. Одержимо наступний d-куб заданої несправності:
![]() 3. Побудувати таблицю для визначення тестового набору (таблиця 5.1). Записати в таблицю d-покриття схеми, яке являє собою сукупність d-кубів елементів схеми (рядки 1...13 таблиці). Таблиця 5.1
4. В стовпці „Входи ДП” і „Логічні елементи” таблиці записати початковий вектор стану схеми Активізовані шляхи починаються з несправного елемента, тому в стовпець „ Активність” записується 4, а в стовпець „d-розгалуження”- номери елементів 6 і 7 (рядок 14 таблиці). 5. Здійснити спробу просування заданої несправності на виходи схеми через елементи, які входять в d-розгалуження. Для цього виконати перетин поточного вектора стану схеми з усіма d-кубами елементів d-розгалуження. В результаті перетину вектора Перетин 4-х розрядів вектора ![]() ЧТО И КАК ПИСАЛИ О МОДЕ В ЖУРНАЛАХ НАЧАЛА XX ВЕКА Первый номер журнала «Аполлон» за 1909 г. начинался, по сути, с программного заявления редакции журнала... ![]() Что делает отдел по эксплуатации и сопровождению ИС? Отвечает за сохранность данных (расписания копирования, копирование и пр.)... ![]() Система охраняемых территорий в США Изучение особо охраняемых природных территорий(ООПТ) США представляет особый интерес по многим причинам... ![]() Что будет с Землей, если ось ее сместится на 6666 км? Что будет с Землей? - задался я вопросом... Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:
|