Порядок виконання практичної роботи.
Ознайомитись з теоретичними відомостями.
Для комбінаційної схеми з додатку А, згідно варіанта, отримати у викладача дві точки для яких необхідно побудувати тестову послідовність.
Окремо для кожної точки ("константний 0" та "константну 1") побудувати тестові послідовності за допомогою методу з використанням -алгоритму.
Проаналізувати отримані результати та зробити висновки про повноту отриманого тесту та ефективність методу для великих комбінаційних схем.
Питання для самоконтролю.
1. Які основні етапи побудови тестів методом активізації багатомірного шляху?
2. Що таке сингулярний куб логічного елементу?
3. Правила побудови сингулярних та -кубів?
4. Що є ознакою завершення етапу -розповсюдження?
5. Які існують обмеження на застосовність методу активізації багатомірного шляху?
Практична робота №6
Побудова перевіряючих тестів для комбінаційних логічних схем.
Дослідження особливостей побудови тестів
за допомогою методу PODEM.
Мета: Навчитися формувати тести для діагностування комбінаційних схем із застосуванням методу PODEM.
Теоретичні відомості
Як і
-алгоритм,
цей метод використовує той самий
шестизначний алфавіт
,
але в ньому застосовується інша стратегія
пошуку тестового набору. Відмітимо, що
метою будь-якого алгоритму побудови
теста для заданої несправності є вхідний
двійковий вектор, який перевіряє цю
несправність. Таким чином, шуканий тест
належить простору всіх можливих двійкових
вхідних наборів. Однак простором пошуку
в
-
алгоритмі є множина всіх можливих (в
тому числі і кратних)
шляхів в схемі від місця несправності
до будь-якого зовнішнього виходу, де
- кількість елементів. В методі PODEM
простором пошуку є безпосередньо множина
всіх можливих вхідних наборів, потужність
якого
зазвичай менше
,
оскільки, як правило,
це дозволяє значно прискорити процес
відшукання необхідного тестового
вектора.
Основні відмінності методу PODEM від - алгоритму наступні:
1) інша процедура -розповсюдження;
2) відмінна процедура довизначення;
3) виконується тільки пряма імплікація (від зовнішніх входів до виходів);
4) інша стратегія пошуку рішень та обробка ситуацій з протиріччям.
-розповсюдження в методі PODEM виконується покроково. В -границі обирається в якості "цілі" найбільш перспективний елемент (найближчий до зовнішнього виходу чи той, який має ліпші показники спостереженності) і надалі відразу, за допомогою інших процедур (в першу чергу процедури просування назад) знаходиться вхідний набір, що забезпечує досягнення поставленої локальної цілі - -розповсюдження через даний елемент. Нагадаємо, що в -алгоритмі -розповсюдження виконується до зовнішнього виходу, а далі проводиться довизначення.
Алгоритм вибору
цілі для константної несправності
вентиля
представлено наступним псевдокодом:
Ціль (
)
// ціль несправність
{
if (значення
невизначене)
then return(
);
Вибір елемента
з
-границі;
Вибір не визначеного
входу
елемента
;
"домінуюче
значення"
;
return (
);
}
Тут вибір елемента в -границі проводиться по кращому показнику спостереженності (в найпростішому випадку обирається елемент, найближчий до одного із зовнішніх виходів).
Довизначення проводиться за допомогою двох основних процедур – розповсюдження назад та імплікації. Ефективність методу PODEM багато в чому визначається процедурою просування назад. Оскільки метод розроблено для схем, що описані на рівні найпростіших логічних елементів "ТА", "АБО", "НІ", "ТА-НІ", "АБО-НІ", то процедура достатньо проста. Починаючи з елемента обраного в якості "цілі", по мірі просування до зовнішніх виходів, процедура для кожного логічного елемента по заданому значенню одного виходу визначає значення тільки одного входу. Її результатом є присвоєння визначеного значення (0 чи 1) одному зовнішньому входу схеми в результаті проходження одного шляху від "цільового елемента" до цього зовнішнього входу.
Нехай ціллю
процедури є встановлення значення
на лінії
.
Тоді значення зовнішнього входу
визначається парністю кількості
елементів інвертуючого типу
вздовж обраного шляху (при проходженні
через елементи "НІ", "ТА-НІ",
"АБО-НІ" значення сигналу
інвертується). Процедура просування
назад для внутрішньої лінії (
,
)
знаходить зовнішній вхід (
).
При цьому
,
де
- парність шляху від
до
.
Слід відзначити, що значення присвоюється
тільки одному зовнішньому входу.
Внутрішні лінії зберігають при цьому
свої старі значення (як правило,
невизначені значення -
).
Псевдокод процедури просування назад
наступний:
Просування назад ( , )
// присвоєння значень одному зовнішньому входу
{
;
while ( є виходом елемента)
{
інверсія
;
вибір_входу_елемента( );
;
;
}// -зовнішній вход
return(
,
);
повернення зовнішнього входу
зі значенням
}
вибір_входу_елемента( );
{
if (встановлення виходу вимагає встановлення значень всіх входів)
вибір невизначеного входу з гіршою керованістю для ;
else
вибір невизначеного входу з кращою керованістю для ;
return( )
}
Окремо слід відзначити правила вибору входу елемента. Тут, перш за все, визначається: наявний один чи кілька варіантів присвоєння значень входів логічного елемента, при яких на його виході встановлюється необхідне значення. У випадку кількох варіантів (наприклад, 0 на виході логічного елемента "ТА" може бути отриманий в результаті встановлення 0 на будь якому вході; аналогічно 1 на виході логічного елемента "АБО" можна отримати присвоєнням 1 довільному з його входів) обирається вхід елемента, найближчий до зовнішнього входу чи той, який має найкращий показник керованості. Тобто в цьому випадку ми обираємо найперспективніший шлях. Якщо є тільки один варіант, то обирається вхід, найбільш віддалений від зовнішніх входів чи той, що має найгірший показник керованості. Це робиться з метою найбільш швидкого віднаходження ситуацій з протиріччям, якщо вона можлива в наслідок даного присвоєння.
Після того, як
зовнішній вхід в результаті цієї
процедури отримав визначенні значення,
виконується пряма імплікація шляхом
моделювання в алфавіті
.
Якщо в результаті імплікації ціль
досягнуто, то виконується наступний
крок
-розповсюдження.
У протилежному випадку виконується
процедура просування назад для елементів
записаних в стек на попередньому кроці,
до тих пір поки не буде досягнуто
поставленої мети. Пряма імплікація
виконується шляхом моделювання в
алфавіті
,
як правило за допомогою таблиць для
логічних елементів, від зовнішніх входів
до виходів.
У випадку виникнення протиріч на етапі імплікації починається перебирання значень зовнішніх входів, що до цього моменту отримали певні значення. Після виконання процедури просування назад кожне знову отримане двійкове значення зовнішнього входу заноситься у стек. У випадку виникнення протиріччя значення зовнішнього входу, що записане в стек останнім, замінюється на протилежне. Далі знову виконується імплікація. Якщо в цьому випадку виникає протиріччя, то замінюється на протилежне значення наступного зовнішнього входу у стеці. Процес пошуку припиняється, якщо досягнуто мети або всі варіанти вичерпані (теста не існує). Псевдо код методу PODEM має вигляд:
PODEM(
)
{
while(несправність не проявилася на зовнішньому виході)
{
if(перевірка_ _шляху( -границя))
// якщо існує вагомий шлях від -границі до виходу
{
(
)=Ціль(
);
// встановлення цілі
(
)=просування_назад(
);
імплікація( );
if (PODEM( )=УСПІХ) then return (УСПІХ);
Імплікація(
);
// відмічаємо вхід як невизначений
Return(НЕВДАЧА);
}
else if (стек імплікації пустий)
return(НЕВДАЧА);
else просування назад();
}
return(УСПІХ);
}
В якості прикладу
розглянемо побудову теста для несправності
в схемі рис. 6.1.
Рис. 6.1. Комбінаційна схем для ілюстрації методу PODEM
В таблиці 6.1 наведено
результати основних етапів генерації
теста для цієї несправності. Тут для
кожного етапу приведені значення цілі,
зовнішніх входів, стан
-границі.
Відповідно на рисунку 6.2 наведено дерево
рішень для цього прикладу. Оскільки при
пошуку тестового набору рішення полягає
у виборі одного з двох двійкових значень
(0 чи 1) для зовнішнього входу, то дерево
є двійковим. Тут кожен вузол відповідає
зовнішньому входу, який приймає двійкове
значення при побудові тесту;
та
(в квадраті) – відповідно успіх та
невдача при даному виборі.
Метод PODEM значно простіше в програмній реалізації ніж -алгоритм та довів свою ефективність при застосуванні до великих комбінаційних схем об‘ємом до кількох тисяч логічних елементів.
Таблиця 6.1. Основні етапи процесу генерації тесту методом PODEM
Ціль |
Зовнішні входи |
Імплікація |
-розповсю-дження |
Невдача |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Повернення |
|
|
|
|
Рис. 6.2 Дерево рішень при пошуку теста методом PODEM