Порядок виконання лабораторної роботи. 1. Ознайомтеся з теоретичними відомостями

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

2 Побудуйте комбінаційну схему дешифратора, яка формує на виході високий рівень сигналу при встановленні на його входах значення NM у шістнадцятковій системі числення, де N – номер варіанта (порядковий номер за списком); М=16–N.

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

5. Проведіть тестування розробленої схеми із застосуванням тестів, отриманих згідно з методом активізації одновимірного шляху. Результати тестування оформіть у вигляді часових діаграм.

6. Проаналізуйте отримані результати і зробіть висновки про наявність чи відсутність несправностей, що перевіряються.

 

Питання та завдання

1. В чому полягає суть методу активізації одновимірного шляху?

2. В якій послідовності виконується процедура активізації?

3. Які несправності називаються константними?

4. Які Ви знаєте причини виникнення константних несправностей?

5. Скільки константних несправностей можна визначити однією тестовою комбінацією?

6. Що відбувається в прямій фазі методу активізації одновимірного шляху?

7. Що таке «зворотна фаза»?

8. Як визначається активність шляху?

Лабораторна робота № 4

Дослідження особливостей побудови тестів

Із застосуванням D-алгоритму

Мета: навчитися формувати тести для діагностування комбінаційних схем із застосування D-алгоритму.

Рекомендована література: [2, 9].

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

Метод активізації багатовимірного шляху (D-алгоритм), запропонований К.Ф. Ротом, – це перший алгоритмічний метод побудови тестів для беззалишкових комбінаційних схем. Іншими словами, цей алгоритм гарантує знаходження тесту для заданої несправності, якщо такий тест існує.

Алгоритм Рота ґрунтується на застосуванні кубічного опису булевих функцій, що є однією з можливих форм їхнього зображення. Серед кубічних зображень булевих функцій, що використовуються в зазначеному алгоритмі, перші – так звані сингулярні куби, сукупністю яких є сингулярні покриття схеми, що реалізують булеву функцію. Для зображення сингулярних кубів використовуються символи , , , де означає, що змінна по даній координаті може набувати як нульове, так і одиничне значення. Як приклад на рис. 4.1 наведена множина сингулярних кубів для елементів 2І–НЕ і 2АБО–НЕ.

Розглянуті сингулярні куби застосовуються для отримання d-кубів, при заданні яких використовуються символи , , , , . Символ d може позначати як , так і , а набуває значення, протилежне символу d. Для конкретної цифрової схеми всі символи d набувають те саме значення чи , а – відповідно чи .

 

а б

Рис. 4.1. Приклади вироджених покриттів для
елементів 2І–НЕ і 2АБО–НЕ

d-куб, що описує поводження цифрової схеми, виходить у результаті виконання покоординатної операції перетинання двох сингулярних кубів із сингулярного покриття схеми, що мають різне значення за вихідною координатою, на підставі таких співвідношень:

; ; .

Так, на підставі кубів і із сингулярного перетинання отримаємо d-куб і .

Для опису існування заданої несправності використовуються так звані примітивні d-куби несправності, які складаються із вхідного набору, що дозволяє спостерігати несправність по виходу елемента і символу чи у вихідній координаті. Для прикладу, наведеного на рис. 4.1, а, і несправності по виходу елемента 2І – НЕ відповідний примітивний d-куб набуде вигляду: . В даному випадку означає, що в справному стані по вихідній координаті повинний бути символ , а в несправному – . Водночас для кубів, що описують поведінку елемента 2АБО – НЕ, у випадку несправності (“константна ”) по його виходу, означає, що в справному стані на його виході повинний бути символ , а в несправному – : .

d-куб несправності порівняно легко будується для одного елемента схеми, на вході або на виході якого є наявна константна несправність. Однак основною задачею D-алгоритму є побудова d-куба несправності всієї розглянутої схеми. З цією метою використовується операція d-перетинання, введена Ротом для формалізації процедури активізації багатовимірного шляху. Покоординатна операція d-перетинання визначається згідно з табл. 4.1.

Таблиця 4.1

Покоординатна операція d-перетинання

			Х
Х	Ø Ψ φ	Ø Ψ Ψ	X	Ψ Ψ μ λ	φ Ψ λ μ

Результат d-перетинання двох d-кубів і визначається відповідно до співвідношення , де Ø, якщо хоча б для одного і Ø; – не визначено, якщо хоча б для одного і Ψ чи якщо хоча б для одного та одного , , але для будь-якого ; – в інших випадках. У свою чергу значення дорівнює , якщо або і – в інших випадках.

Стосовно d-алгоритму процедуру d-перетинання двох d-кубів А і В виконують відповідно до більш простих співвідношень по координатної операції d-перетинання, що визначається виразами:

, якщо ;

, якщо ;

Ø – в інших випадках.

Остаточно результатом d-перетинання двох кубів А і В буде куб , якщо для будь-якого , в іншому випадку – Ø.

Безпосередньо d-алгоритм складається з таких основних етапів:

1.Вибирається примітивний d-куб заданої несправності елемента цифрової схеми.

2.Активізуються можливі шляхи від елемента, що містить несправність, до виходу схеми. При цьому застосовується операція d-перетинання d-куба несправності з d-кубами елементів, послідовно з’єднаних між вихідним несправним елементом і виходами схеми. У результаті початкового перетинання d-куба несправності з d-кубом наступного елемента отримуємо d-куб заданої несправності, що описує поводження схеми з двох елементів.

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

3.Виконується зворотна фаза як процедура послідовного перетинання отриманого d-куба заданої несправності, що описує поводження несправності елемента, і елементів, які лежать на шляхах транспортування несправності із сингулярними кубами інших елементів.

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

Рис. 4.2. Комбінаційна схема

Спочатку побудуємо множину сингулярних кубів та d-кубів для 2АБО – НЕ і 4АБО – НЕ і примітивні d-куби несправності елемента 2АБО – НЕ, що необхідні для реалізації d-алгоритму.

Відповідно матимемо:

сингулярні куби

2АБО – НЕ	4АБО – НЕ

d-куби

2АБО – НЕ	4АБО – НЕ

примітивні d-куби несправності

2АБО – НЕ

Використовуючи отримані множини кубів, побудуємо тестовий набір для виявлення несправності комбінаційної схеми, наведеної на рис. 4.2. Для цього спочатку з множини примітивних d-кубів несправності елемента 2 (2АБО – НЕ) виберемо куб , що описує несправне поводження елемента при . Далі на першому кроці d-проходу виконаємо процедуру d-перетинання d-куба несправності із d-кубом , що описує елемент 5, і відповідно отримаємо (цифри 1-12 – номери полюсів схеми):

З огляду на те, що несправність може транспортуватися через елементи 5 і 6 схеми одночасно, перетинаємо отриманий куб із d-кубом, що описував елемент 6:

 

Куб перетинається з d-кубом елемента 4АБО – НЕ:

Поява символу d у вихідній координаті свідчить про закінчення d-проходу. Зворотна фаза d-алгоритму для розглянутого прикладу буде полягати в послідовному перетинанні куба із сингулярними кубами елементів 4 і 7. У результаті отримаємо:

Отже остаточно отримаємо куб , який показує, що при подачі на входи схеми (рис. 4.2) набору і наявності несправності на полюсі 6 схеми формується значення нуля, що буде зафіксовано і на вихідному полюсі 12 схеми. При відсутності зазначеної несправності на полюсі 12 схеми буде формуватися значення одиниці. Таким чином, вхідний набір є тестом для несправності .

Розглянутий d-алгоритм дозволяє побудувати тест для кожної несправності комбінаційної цифрової схеми, якщо такий тест існує. Крім того, даний алгоритм здатний ідентифікувати наявність надлишковості в цифровій схемі, вимагає порівняно невеликого обсягу пам’яті й відрізняється невисокою трудомісткістю, що дозволяє широко використовувати його в системах автоматичної генерації тестів.