Порядок виконання практичної роботи.

1. Ознайомитись з теоретичними відомостями.

2. Для комбінаційної схеми з додатку А, згідно варіанта побудувати:

• таблицю інцедентності;

• мережу Петрі для елементів всіх типів, що представлені на заданій схемі;

• мережу Петрі, що є структурно-логічною моделлю всієї запропонованої схеми, та виділити на ній зв'язки, якими розповсюджуються сигнали довільного вхідного вектора;

• графічне представлення заданої схеми у відповідності до стандарту міжнародного каталогу ISCAS-89;

• опис схеми на спеціалізованій мові з каталогу

ISCAS-89.

3. Визначити чи є необхідність в заданій схемі використовувати "монтажну логіку".

4. Проаналізувати отримані результати та зробити висновки про зручність представлення схем відповідними структурними моделями.

Питання для самоконтролю.

1. Чим відрізняються струкурно-логічні та функційно-логічні моделі?

2. Які основні типи структурних моделей вам відомі?

3. Що таке мережа Петрі? Як вона описується формально?

4. Яким чином будується матриця інцедентності для заданої схеми?

5. Наведіть приклад опису довільного логічного елементу мережею Петрі.

6. Яким чином описують цифрові схеми за допомогою спеціалізованих мов?

7. Яка структура тексту опису цифрової схеми спеціалізованою мовою з міжнародного каталогу ISCAS-89?

8. Які основні типи логічних елементів та як саме описуються в спеціалізованій мові опису цифрових схем?

9. Що таке монтажна логіка?

10. Основне призначення монтажної логіки, та особливості її використання при побудові моделей цифрових схем.

Практична робота №3 Побудова перевіряючих тестів для комбінаційних логічних схем. Метод критичних шляхів.

Мета: Ознайомитись з видами побудови перевіряючих тестів. Навчитися генерувати тести за допомогою методу критичних шляхів.

Теоретичні відомості

Побудова тестів для комбінаційних логічних схем

Генерація перевіряючих тестів навіть для комбінаційних схем цифрових систем є важкою як в математичному, так і в технічному плані проблемою. Її найважливішими аспектами є:

1) вартість генерації тестів;

2) якість тестів що генеруються;

3) вартість тестування схеми за допомогою побудованих вхід-вихідних послідовностей.

В теоретичному аспекті генерація тестів відноситься до класу NP-повних проблем (перебірного типу), для яких не існує алгоритмів вирішення поліноміальної складності. В практичному аспекті складність її вирішення залежить від алгоритму генерації тестів, що застосовується. Ефективність алгоритмів, що розробляються прийнято перевіряти на схемах з різним міжнародних каталогів: ISCAS-85, ISCAS-89, ITC-99 та інших. Псевдовипадкові методи генерації тестів мають низьку складність алгоритму, але дають довгі тестові послідовності та невисоку повноту. Детерміновані методи генерації дають тести кращої якості, але їх алгоритми мають високу складність. Якість побудови тестів визначається, як правило, за допомогою програм моделювання несправних схем. Безпосередньо процес тестування проводиться на спеціалізованому устаткуванні – тестерах, які забезпечують подання вхідних сигналів на вхід схеми, зняття вихідних сигналів та їх порівняння з етелонними значеннями. Найважливішими характеристиками тестерів є тактова частотата об‘єм пам‘яті для зберігання тестових впливів.

Перш за все слід розрізняти функційні та структурні тести. Алгоритми побудови функційних тестів генерують повну множину можливих тестових наборів, які дозволяють повністю перевірити функцію, яку реалізує дана схема. Наприклад, для комбінаційної схеми з входами та одним виходом функційним тестом є множина всіх можливих тестових двійкових послідовностей, що дозволяє відновити булеву функцію, яка реалізується схемою, що тестується. Очовидно, що для схеми великої розмірності такий підхід не завжди прийнятний.

З іншого боку, структурні тести перевіряють тільки мінімально необхідну множину несправностей (як правило, поодиноких константних несправностей).

Детерміновані методи генерації тестів поділяються на два класи:

1) побудова тесту для схеми в цілому безвідносно до конкретної несправності;

2) побудова тесту для конкретної заданої несправності.

Метод критичних шляхів

Із структурних методів на початковому етапі добре зарекомендували себе на практиці алгоритми, що базуються на методі критичних шляхів. Вони дають непогану повноту теста і відносно прості в реалізації. Метод базується на тому, що половина поодиноких константних несправностей на критичних (активізованих) шляхах перевіряється тестом. Тому, бажано будувати тести, що породжують як можна більше критичних шляхів, на яких зміна сигнала на будьякій лінії схеми, що входить до такого шляху, викликає зміну сигналу на виході схеми. Такі тести будуються з використанням так званих критичних кубів логічних елементів схеми. Починаючи з виходу, де значення приймається 0* або 1* (зірочкою позначається критичність), критичні шляхи будуються в напрямі входів схеми. Для кожного логічного елемента, вихід якого отримав критичне значення, виконується вибір критичного куба – його входам надаються такі значення, щоб один або кілька входів були критичними, тобто, щоб при зміні значення на вході змінювалося значення сигналу на виході елемента. Наприклад, якщо логічний елемент "ТА-НІ" з входами має значення на виході , то значення на його входах критичні по відношенню до . Аналогічно вхідні значення критичні по відношенню до . Набір не має критичних значень, так як зміна або на одиницю не викликає змін виходу логічного елемента . Якщо вихід логічного елемента , то набір критичний по відношенню до обох входів. Суть методу полягає в тому, що необхідно намагатися розповсюдити критичне значення від виходу схеми до її входів за допомогою критичних кубів елементів. Перш ніж формально описати алгоритм генерації тестів методом критичних шляхів, розглянемо його на невеликому прикладі схеми, приведеної на рис. 3.1.

Вибираємо початкове значення виходу схеми . З таблиці 3.1 критичних кубів для логічного елемента "ТА" видно, що існує два критичних куби зі значеннями на виході 0*10* та 10*0* (тут значення записані в порядку ). Вибравши перший з них, отримуємо . З таблиці 3.1 обираємо єдиний для логічного елемента "ТА-НІ" зі значенням 0* на виході критичний куб 1*1*0*. Що б отримати значення , з трьох можливих комбінацій значень входів обираємо .

а)	в)
б)	г)

Рис. 3.1. Ілюстрація методу критичних шляхів

Таблиця 3.1. Критичні куби для логічних елементів з двома входами

Функція				Аналітичний запис куба
1	2	3	4	5
1	2	3	4	5
		-
		-

Таким чином отримали тестовий набір , , , . Очовидно, що цей набір перевіряє поодинокі константні несправності, протележні критичним значенням, тобто, якщо лінія помічена 1*, то перевіряється несправність const0 на цій лінії. Якщо вона відмічена як 0*, то перевіряється несправність const1. На рисунку 3.1 приведені ще три набори, які побудовані аналогічним чином і разом з першим складають повний перевіряючий тест на поодинокі константні несправності для схеми що розглядалась.

Поняття критичних кубів вперше було введене для логічного елемента "ТА-НІ" та використовувалось при генерації тестів в системі LASAR. Надалі це поняття було розповсюджено на основні логічні елементи. При цьому критичні куби для простих логічних елементів "ТА", "АБО", "НІ", "ТА-НІ", "АБО-НІ" у всіх роботах однакові та однак не завжди трактуються так само.

Для комбінаційних цифрових схем основний алгоритм генерації тестів методом критичних шляхів можна сформулювати наступним чином.

1. Обрати зовнішній вихід схеми та присвоїти йому критичне значення 0*.

2. Для елемента, що має критичне значення на виході, обираючи відповідні критичні куби з таблиці *-кубів його типу, розповсюдити значення на входи елементу.

3. Присвоїти відповідні значення виходам елементів, які з‘єднані з входами, що отримали нові значення в п.2. Виконати операцію імплікації для всіх таких виходів.

4. Якщо імплікація дає несумісність отриманих значень зі старими, перейти до п.5, інакше до п.6.

5. Повернутися до останього обраного критичного куба. Якщо вибору немає (всі варіанти розповсюдження критичних значень розглянуті), то перейти до п.7, інакше обрати *-куб та перейти к п.3.

6. Обрати "необроблений" елементз критичним виходом та повернутися до п.2. Якщо таких елементів немає то перейти до п.8.

7. Для розглянутого критичного значення на зовнішньому виході не існує вихідного набору з критичними шляхами. Якщо це був 0*, то зовнішньому виходу присвоїти 1* та повернутися до п.2, якщо – 1*, то у випадку наявності "неопрацьованих" зовнішніх виходів схеми повернутися до п.1. Якщо всі виходи оброблені, то кінець.

8. Виконати процедуру доопрацювання для некритичних значень на виходах елементів, що залишились невизначиними.

9. Якщо це неможливо в наслідок несумісності отриманих значень зі старими, то повернутися до п.5. В протележному випадку (якщо набір побудований) повернутися до п.1; якщо на зовнішньому виході був 0*, то присвоїти цьому виходу значення 1* та перейти до п.2.

Наведений алгоритм породжує в найкращому випадку по два набори для кожного виходу схеми. Для більшої повноти теста можна отримати додаткові критичні шляхи (відповідно набори теста) за допомогою того ж алгоритму, відпрацьовуючи в процесі генерації теста всі можливі варіанти критичних кубів, як це було показано для схеми на рисунку 3.1.

Слід відзначити, що в процесі реалізації для пришвидшення генерації тестів є сенс використовувати певні евристичні шляхи. Наприклад, при обранні *-куба необхідно брати куб з критичними значеннями для несправностей, не перевірених до поточного моменту часу. При генерації нового набору теста для того ж критичного значення виходу доцільно починати не з самого початку, а з місця останнього вибору варіанта, зберігаючи частково значення сигналів на лініях схеми, які отримані на попередньому наборі. Слід відзначити, що там, де генерація теста потребує багатомірної активізації шляхів, цей метод не гарантує побудови теста.

Після виконання початкового етапу генерації теста одним з приведених методів виконується моделювання схеми з несправностями, визначається повнота теста та список несправностей, що не можуть бути перевіреними. Надалі для несправностей що не можуть бути перевіреними використовують методи генерації тестів для конкретної несправності.