Генерації тестів цифрових систем

Размещено на http://www.allbest.ru/

ДЕРЖАВНИЙ ВИЩИЙ НАВЧАЛЬНИЙ ЗАКЛАД

ДОНЕЦЬКИЙ НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ

УДК 681.518:681.326.7

Спеціальність 05.13.05 - Комп'ютерні системи і компоненти

АВТОРЕФЕРАТ

дисертації на здобуття наукового ступеня

кандидата технічних наук

ІЄРАРХІЧНІ ЕВОЛЮЦІЙНІ МЕТОДИ

ГЕНЕРАЦІЇ ТЕСТІВ ЦИФРОВИХ СИСТЕМ

Шукрі Насрі Алі Хінді

(ЙОРДАНІЯ)

Донецьк - 2010



Дисертацією є рукопис

Робота виконана в Державному вищому навчальному закладі “Донецький національний технічний університет ” Міністерства освіти і науки України.

Науковий керівник: доктор технічних наук, професор Скобцов Юрій Олександрович, ДВНЗ “Донецький національний технічний університет”, завідувач кафедри «Автоматизовані системи управління».

Офіційні опоненти: доктор технічних наук, професор, Кривуля Геннадій Федорович, завідувач кафедри «Автоматизація проектування обчислювальної техніки» Харківського національного університету радіоелектроніки;

кандидат технічних наук, доцент, Вороной Сергій Михайлович, завідувач кафедри «Системи штучного інтелекту» Державного університету інформатики і штучного інтелекту.

Захист відбудеться “03” 06 2010 р. о 14:00 на засіданні спеціалізованої вченої ради Д 11.052.03 Донецького національного технічного університету за адресою: 83001, м. Донецьк, вул. Артема, 58. ауд. 8.704.

З дисертацією можна ознайомитись в бібліотеці ДонНТУ (адреса: 83001, м. Донецьк, вул. Артема, 58, II нав. корп.)

Автореферат розісланий “ 28 ” 04 2010 р.

Вчений секретар спеціалізованої вченої ради Д 11.052.03 кандидат технічних наук, доцент Г.В. Мокрий



Загальна характеристика роботи

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

В даний час розроблено ряд ефективних методів генерації перевіряльних тестів для цифрових схем. Значний внесок у розвиток тестування цифрових систем внесли закордонні дослідники Roth J.P., Zorian Y, Agrawal V.D, Abramovici M., Fujivara H. а також вітчизняні вчені Пархоменко П.П., Убар Р.Р., Тоценко В.Г., Сперанський Д.В., Романкевич О.М., Дербунович Л.В., Кривуля Г.Ф., Скобцов Ю.О., Хаханов В.І. й інші. Однак існуючі методи не завжди дозволяють будувати тести високої повноти за прийнятний час. У першу чергу це відноситься до цифрових схем з пам'яттю. На сучасному етапі найбільш перспективними є еволюційні методи генерації перевіряльних тестів, у першу чергу, на основі генетичних алгоритмів.

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

Зв'язок роботи з науковими програмами, планами, темами.

Дисертаційна робота виконана протягом 2006-2009 рр. у рамках наукового напрямку кафедри автоматизованих систем управління Донецького національного технічного університету за темою Н-3-07 «Розробка наукових основ побудови комп'ютерних систем технічної і медичної діагностики».

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

Для досягнення поставленої мети в роботі сформульовані і вирішуються наступні задачі:

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

Розробка структурного методу побудови перевіряльних тестових послідовностей для схем із пам'яттю на основі кратної стратегії спостереження вихідних сигналів.

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

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

Розробка програмного забезпечення генерації перевіряльних тестових послідовностей на основі послідовних і ієрархічних генетичних алгоритмів.

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

Об'єкт дослідження - цифрові логічні системи, задані зв'язкам логічних елементів, входів і виходів спеціалізованою мовою.

Предмет дослідження - структурні еволюційні методи побудови перевіряльних тестів для цифрових логічних схем.

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

Наукова новизна отриманих результатів полягає в наступному:

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

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

Модифіковано методи багатозначного моделювання в 16-значному алфавіті, що дозволило підвищити ефективність використання кратної стратегії спостереження вихідних сигналів і прискорити генерацію тестів для схем з пам'яттю.

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

Практичне значення отриманих результатів полягає в тому, що:

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

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

Розроблені методи і програмне забезпечення використовуються в Інституті прикладної математики і механіки НАНУ у вигляді модуля системи моделювання і діагностики АСМІД, а також у навчальному процесі Донецького національного технічного університету в рамках курсу “Технічна діагностика цифрових систем”, у курсовому і дипломному проектуванні на кафедрі «Автоматизовані системи управління» ДонНТУ.

Особистий внесок здобувача. Всі основні положення і результати дисертаційної роботи, що виносяться на захист, отримані автором самостійно. У роботах, що виконані в співавторстві, автору належать: [1,3] - дворівневий генетичний алгоритм; [2] - дослідження різних стратегій спостереження вихідних сигналів; [4] - побудова характеристичних послідовностей; [5] - основний алгоритм побудови тестів на основі кратної стратегії спостереження вихідних сигналів; [6] - ієрархічний алгоритм генерації тестів; [7] - застосування кратної стратегії в побудові тестів; [8,9] - дворівневий алгоритм генерації перевіряльних тестів.

Апробація роботи. Основні наукові результати роботи доповідалися й обговорювалися на:

міжнародній конференції «Інтелектуальні системи в промисловості і освіті» (Суми, листопад 2007»;

III міжнародній науково-технічній конференції «Гарантоспроможні (надійні і безпечні) системи, сервіси і технології» (Україна, Кіровоград, квітень 2008 р.);

III Всеукраїнській конференції ”Сучасні тенденції розвитку інформаційних технологій в науці, освіті та економіці” (Луганськ, квітень 2008);

X international conference “The experience of designing and application of CAD systems in microelectronics”(Lviv-Polyana,Ukraine, february 2009).

10-й міжнародній науково-практичній конференції «Сучасні інформаційні й електронні технології» («СІЕТ-2009», Одеса).

Публікації. За темою дисертаційної роботи опубліковано 9 друкованих праць, з них 5 статей у виданнях, затверджених у ВАК України; 3 тези міжнародних конференцій.

Структура й обсяг дисертаційної роботи: дисертація складається зі вступу, чотирьох розділів, висновку, списку використаної літератури зі 102 найменувань. Загальний обсяг роботи 140 стор., ілюстрацій - 26 , таблиць -16., додатків 1.

Основний зміст роботи

У першому розділі “Аналіз методів моделювання і генерації тестів цифрових схем” уведені поняття, що визначають об'єкт дослідження: математичні моделі цифрових пристроїв і несправностей, визначення тестової послідовності. Розглянуто основні аспекти логічного моделювання несправних цифрових схем. Виконано аналіз основних методів моделювання несправностей цифрових схем: послідовного, паралельного, дедуктивного, конкурентного і розподіленого. Розглянуто питання підвищення швидкодії логічного моделювання несправних цифрових схем.

При розробці методів і алгоритмів побудови перевіряльних тестів і моделюванні несправностей використовується, в основному, структурна модель цифрового пристрою у вигляді правильної логічної мережі. Розглянуто основні аспекти генерації тестів для цифрових схем. Виконано аналіз існуючих методів побудови перевіряльних тестів для цифрових систем (ЦС) і використовуваних багатозначних алфавітів.

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

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

Нехай справна послідовнісна схема реалізує скінченний автомат A=(Y,X,Z,,), де Y, X, Z - скінченні множини станів, вхідних і вихідних сигналів відповідно; :YXY - функція переходів, що визначає наступний стан автомата; :YXZ - функція виходу, що визначає вихідний сигнал. Нехай несправність f перетворює автомат A в Af =(Y,X,Z,f,f), де функції f,f стану Yf і Zf визначаються в такий же спосіб.

На функціональному рівні несправність f називається перевіреною вхідною послідовністю X(1), X(2),..., X(p), якщо вихідні реакції на цю послідовність різні для кожної пари станів автоматів, що реалізуються справною і несправною схемою.

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

Відзначимо, що ітеративна комбінаційна схема в загальному випадку неадекватно відображає поведінку асинхронних послідовнісних схем. Ця неадекватність «провокує» різне трактування несправностей, які перевіряються, у послідовнісних схемах, що породжує масу проблем, подолання яких має багато нюансів. Різні методи (і автори) побудови тестів вирішують ці проблеми по-різному. При цьому фактично різні дослідники використовують різні визначення несправностей, які перевіряються, для схем із пам'яттю, що створює плутанину й утрудняє дослідження в даній області, що розглянуті нижче.

Визначення 1. Несправність f називається перевіреною в послідовнісній схемі вхідною послідовністю X(1), X(2),…,X(p) якщо:

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

Визначення 2. Несправність f називається умовно перевіреною в послідовнісній схемі вхідною послідовністю X(1), X…,X(p) якщо:

Відповідно до цього визначення несправність вважається перевіряною, якщо в деякий момент часу хоча б на одному виході сигнал справної схеми має визначене значення {0,1}, а несправної - невизначене значення u.

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

Визначення 3. Несправність f називається перевіреною в послідовнісній схемі вхідної послідовності X(1), X(2),…,X(p) відносно стратегії одиночного спостереження виходів (SOT), якщо

де r - початковий стан справної схеми і q - початковий стан несправної схеми. Це визначення говорить, що при даній стратегії несправність вважається перевіреною, якщо знайдеться (принаймні один) момент часу (такт) t такий, що для будь-якої пари станів (r,q) справної і несправної схем деякий j-й вихід zj має різні значення в справній і несправній схемах. Ключовим моментом є те, що будь-яка пара станів справної і несправної схем повинна видати різні вихідні реакції в той самий такт часу. Наприклад, несправність схеми рис.1 є перевіреною вхідною послідовністю відповідно до визначення 3, оскільки в першому ж такті справна і несправна схеми дають різні вихідні реакції z=0 і zf=1 відповідно.

З іншого боку, несправність вважається неперевіреною вхідною послідовністю при використанні стратегії одиночного спостереження, оскільки не існує такту (моменту часу), для якого всі пари станів справної і несправної схем дають різні вихідні сигнали. Це підтверджує табл.1, де наведені вихідні реакції для довільних початкових станів справної і несправної схем. При цьому справна і несправна схеми мають по 2 можливі стани, що дає 4 можливі пари станів .

Таблиця 1 - Вихідні реакції для довільних початкових станів.

Початкові стани	Входи Х1 Х2
	10	10
A(0)	0	0
B(1)	1	1
a(0)	1	0
b(1)	0	1

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

Визначення 4. Несправність f називається перевіреною в послідовній схемі вхідною послідовністю X(1), X(2),…,X(p) відносно стратегії кратного спостереження виходів (MOT) , якщо:

, (4)

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

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

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

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

Таким чином , використовувана стратегія спостережень вихідних сигналів впливає на постановку задачі побудови тестової перевірної послідовності. При побудові тесту для схем з пам'яттю необхідно знайти вхідну послідовність X(1), X(2),..., X(p), для якої виконується відповідна умова несправності, яка перевіряються, згідно ((1), (2), (3), чи (4)) в залежності від застосовуваної стратегії спостереження виходів.

Відзначимо, що відповідно до наведеного визначення несправності перевірюваності (4) необхідно розрізнити кожну пару станів справного і несправного автоматів. Тому за основу можна взяти вхідні послідовності, що розрізняють окремі пари станів справного і несправного автоматів.

На функціональному рівні, укрупнений алгоритм побудови перевірної послідовності T можна представити в такий спосіб.

Алгоритм 1.

Генерація тестової послідовності(схема)

{

T=, SI=;

while(є нерозрізнені пари станів)

{

Вибір пари станів (S,Q), що не покриваються на поточний момент SI;

if(нерозрізненої пари не існує)

then тест Т побудований: return;

Моделювання на вхідній послідовності Т із початковими станами (S,Q) поведінки автоматів A і Af ;

if (вихідні реакції Y, Yf різні)

then

пара станів (S,Q) розрізняється поточною послідовністю Т;

else

{

побудова розрізнювальної послідовності Ті (S,Q);

if(розрізнювальна послідовність Тi для (S,Q) не побудована)

then

поточна несправність неперевірена і виводиться з подальшого розгляду;

перехід на кінець алгоритму;

}

;

визначення нових розрізнюваних пар

станів ;

визначення всіх розрізнюваних пар

станів ;

}

}

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

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

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

У третьому розділі «Ієрархічний генетичний алгоритм побудови тестів для послідовних схем» досліджений дворівневий алгоритм побудови тестової послідовності. При цьому ГА першого нижнього рівня будує деякі характеристичні послідовності, що дозволяють встановлювати в справній чи несправній схемах деякі елементи пам'яті (змінні стану) у визначені стани чи розрізняти їх.

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

Для побудови тестів (на верхньому рівні) корисними є наступні вхідні характеристичні послідовності .

1) S-послідовності. Назвемо послідовністю Si, що встановлює i-й тригер, вхідну послідовність, що встановлює i-й тригер в одиничний стан.

2) R-послідовності. Аналогічно назвемо послідовністю Ri, що скидає (очищає) i-й тригер, вхідну послідовність, що скидає i-й тригер у нульовий стан.

Будемо називати послідовність Si (Ri), якщо вона дозволяє встановити (скинути) i-й тригер з цілком невизначеного стану, коли всі тригери мають невизначені значення.

3) Розрізнювальні D-послідовності. Розрізнювальна D-послідовність типу A для i-го тригера визначається як вхідна послідовність, що викликає різні вихідні реакції справної схеми для двох різних станів, що відрізняються значенням сигналу на i-му тригері при невизначених значеннях інших тригерів. Звичайно довжина цих вхідних послідовностей обмежується 4D, де D - структурна послідовна глибина.

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

Побудова послідовності Si, що встановлює i-й тригер в одиничний стан , довжини T, зводиться до пошуку таких значень , , …, , при яких змінна стану приймає значення незалежно від значень початкового стану. Умовою незалежності булевої функції від змінних є рівність . Тому побудова S-послідовності Si довжини T зводиться до рішення системи рівнянь:

де булів диференціальний -оператор.

Розроблено відповідні модифікації генетичного алгоритму побудови для характеристичних S-послідовностей і R-послідовностей. У запропонованих алгоритмах обчислення оцінювальної функції засновано на логічному моделюванні роботи справної схеми в багатозначному алфавіті.

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

У загальному вигляді алгоритм верхнього рівня для побудови тестової послідовності можна сформулювати у такий спосіб. Нехай T - формована вхідна тестова послідовність, а C - множина пар станів справної і несправної схем, що розрізняються поточною Т.

Алгоритм А2

Генерація тестової послідовності(схема)

{

T=, SI=;

while(є нерозрізнені пари станів)

{

Вибір пари (можливо не цілком визначених) станів (S,Q) () , що не покриваються на поточний момент SI;

if (нерозрізненої пари не існує)

then тест Т побудований: return;

Формування значень змінних станів в алфавіті B16;

логічне моделювання в алфавіті B16 на вхідній послідовності Т із початковими станами ;

if (значення D чи D' досягає зовнішнього виходу схеми)

then

пара станів (S,Q) розрізняється поточною послідовністю Т;

else

{

побудова розрізнювальної послідовності Т (S,Q);

if (розрізнювальна послідовність для (S,Q) не побудована)

then

{

поточна несправність неперевірена і видаляється з подальшого розгляду;

перехід на кінець алгоритму;

}

else

конкатенація поточного тесту і побудованої послідовності

T=T ·Т (S,Q);

}

Для пари станів

for j=1 to k do

;

логічне моделювання в B16;

if(T не розрізняє (S,Q))

then

відновлення попереднього значення ;

;

логічне моделювання в B16;

if(T не розрізняє (S,Q))

then

відновлення попереднього значення ;

end

визначення нових розрізнюваних пар

станів ;

визначення всіх розрізнюваних пар

станів ;

}

}

Цей алгоритм гарантує побудову тестової послідовності для ненадлишкової несправності в тому випадку, якщо на відповідному кроці гарантується побудова розрізнювальної вхідної послідовності Т (S,Q). У цілому процес побудови тестової послідовності дає значно кращі результати (за одержуваною повнотою тесту) у порівнянні з класичними алгоритмами, що використовують одиночну стратегію спостереження сигналів (SOT) і цілком невизначені початкові стани як справної, так і несправної схем.

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

Визначимо розрізнювальну функцію, для стратегії кратного спостереження в такий спосіб:

для кожної несправності f і вхідної послідовності X(1), X(2),…,X(p)... При цьому r=(r1,...,rk) і q=(q1,...,qk) позначають змінні станів, що представляють початкові стани справної r і несправної q схем. Дана розрізнювальна функція порівнює всі вихідні послідовності для справної і несправної схем одночасно.

Для заданої вхідної послідовності X спочатку виконується символьне моделювання справної схеми, що визначає для кожної лінії булеві вирази, що визначають залежність від змінних станів. Далі для кожної відібраної несправності (звичайно таких, що не виявляються з використанням трійкового моделювання) для кожного часового такту t і виходу j визначаються символьні вирази виходу zj(r,t), де r-стан справної схеми. При досягненні в процесі моделювання зовнішнього виходу j виконується перевірка розглянутої несправності відносно використовуваної стратегії спостереження вихідних сигналів. При використанні стратегії кратного спостереження вихідних сигналів для даного такту часу t обчислюються всі zjf(q,t), де q - стан несправної схеми. Далі обчислюється:

Розрізнювальна функція (6) визначає на кожному кроці пари станів справної і несправної схем, що перевіряються вхідною тестовою послідовністю. Можна показати, що несправність f є виявлюваною відносно стратегії кратного спостереження, якщо і тільки якщо для даної вхідної послідовності X. Якщо , то несправність позначається як перевірена і виключається з подальшого розгляду.

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

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

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

У четвертому розділі “Програмна реалізація, апробація і тестування ” представлені експериментальні дані апробації і тестування розробленого програмного забезпечення на основі запропонованих методів і алгоритмів. Програмні модулі, що реалізують розроблені методи, інтегровані в нову версію автоматизованої системи моделювання і діагностування цифрових схем АСМІД, що призначена для використання при контролі і діагностуванні ЦС на етапах їхнього проектування, виготовлення й експлуатації.

Розроблені в попередніх розділах методи й алгоритми генерації перевіряльних тестів реалізовані програмно і ввійшли до модулів Gen_MOT. Апробація функціонування програми виконувалася на схемах з міжнародних каталогів ISCAS89, на яких за міжнародними стандартами прийнято випробувати нові методи генерації тестів.

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

Тут у другому стовпці наведене F - загальне число модельованих одиночних константних несправностей, у третьому стовпці Fu - число несправностей, не перевірених із використанням трійкового логічного моделювання.

Таблиця 2 - Результати експериментів на псевдовипадкових послідовностях.

	Несправності	Виявлені несправності	Час моделювання (сек.)
Схема	F	Fu	SOT	MOT	SOT	MOT
s298	308	140	3	5	3.36	29.06
s344	342	51	3	5	14.34	162
s349	350	53	3	5	15.11	156
s386	384	205	0	0	0.28	0.40
S420	430	433	0	12	266	201
S510	564	564	391	528	251	293
s641	467	122	3	4	0.91	4.23
s713	581	164	3	4	1.05	5.49
S820	850	641	1	1	0.93	1.8
S832	870	635	1	1	0.97	2.02
S838	857	893	0	11	890	580
S953	1079	989	511	515	42.30	87
S1488	1486	666	1	2	1.33	5.02
S1494	1506	689	1	2	1.32	6.29
S5378	4603	2276	7	97	55	327

Далі в 4-5 стовпцях представлене число несправностей, що перевіряються з використанням відповідної стратегії спостереження вихідних сигналів (відповідно SOT, MOT). Аналогічно в 6-7 стовпцях наведений час моделювання несправностей (на випадкових вхідних послідовностях довжини 200) також із застосуванням цих стратегій. Аналіз результатів моделювання показує, що використання MOT стратегії дозволяє підвищити повноту покриття несправностей для 10 схем (з 15 розглянутих).

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

У 2-3 стовпцях представлені кращі результати для систем, де не застосовувалися генетичні алгоритми (в основному, це система HITEC, де для підвищення ефективності генерації тестів застосовувалися інші методи штучного інтелекту). Далі в 4-5 стовпцях наведені дані, отримані Rudnic зі співавторами в одній з найбільш відомих систем генерації тестів з використанням ГА. У наступних 6-7 стовпцях показані результати того ж колективу, отримані в системі, де використовувався комбінований підхід до побудови тестів, що містить генетичні алгоритми і детерміновані методи генерації тестів.

У табл.3 наведені експериментальні дані по генерації перевіряльних тестів того ж каталогу ISCAS89 з використанням дворівневого алгоритму.

Таблиця 3 - Експериментальні дані по генерації перевіряльних тестів.

	HITEC	GA Rudnic 1994	GA+det Rudnic 1995	Pomerance Reddy 1992	Keim ГА+ SOT 2002	ГА+MOT
Схема	FT	LT	FT	LT	FT	LT	FT	LT	FT	LT	FT	LT
s298	86.04	87	85.94	161	86.04	415	87.66	-	87.66	90	88.53	87
s344	96.20	86	96.20	95	95.51	169	97.66	-	97.37	56	97.41	57
s349	95.71	137	95.71	95	95.71	188	97.14	-	96.86	57	97.52	58
s386	81.77	294	76.88	154	81.77	359	-	-	81.77	160	81.77	160
S400	90.14	2424	85.70	280	81.32	704	-	-	92.22	655	93.41	706
S510	0.00	-	0.00	-	0.00	-	27.30	-	90.08	529	100.0	309
s641	85.51	166	86.51	139	86.51	292	87.15	-	87.37	64	87.35	65
s713	81.93	112	81.93	128	81.93	294	82.44	-	82.62	74	82.64	75
S820	95.76	590	60.76	146	95.76	1108	95.76	-	95.88	412	95.88	412
S832	94.02	701	61.95	150	94.02	1064	93.81	-	94.14	400	94.14	400
S953	8.87	20	-	-	-	-	19.65	-	99.07	196	99.07	188
S1488	97.17	317	93.67	243	97.17	1369	96.55	-	97.31	367	97.27	368
S1494	96.48	540	94.02	245	96.48	1224	-	-	96.61	305	96.63	306
S5378	79.06	11571	68.98	511	70.35	683	-	-	74.99	303	75.21	273
S35932	89.78	257	89.55	197	89.17	425	-	-	89.78	163	90.12	165

Тут представлені результати для кращих систем генерації перевіряльних тестів останніх 15 років. Після першого стовпця з ім'ям схеми йдуть парами стовпці з отриманою повнотою тесту і їх довжиною (числом двійкових наборів) для різних систем.

З приведених даних видно, що в цілому для багатьох схем каталогу ISCAS89 отримані гарні результати. Але для деяких схем використання класичної стратегії спостереження вихідних сигналів не дозволяє одержати прийнятну повноту тестів. До них відносяться, наприклад, схеми S510 і S953. І тільки застосування кратної стратегії спостереження вихідних сигналів (починаючи з робіт Pomerance Reddy) дозволило підвищити повноту тестів для таких схем (результати представлені в стовпцях 8-9). Далі в стовпцях 10-11 представлені кращі результати, отримані з використанням ГА і символьного моделювання. І, нарешті, в останніх стовпцях показані результати з застосуванням генетичних алгоритмів і кратної стратегії спостереження вихідних сигналів. Вони показують, що кратна стратегія спостереження дозволяє підвищити повноту перевіряльних тестів (у середньому на 15 %), а для деяких зазначених «важких схем» (наприклад, S510 і S953) на десятки відсотків. При цьому слід зазначити, що застосування кратної стратегії збільшує час побудови тестів на 140 %, але для деяких схем дозволяє істотно підвищити повноту тестів.

Ці дані показують, що використання кратної стратегії спостереження сигналів дозволяє істотно підвищити повноту перевіряльних тестів (у середньому на 15%)



Висновки

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

У процесі досліджень отримані наступні основні результати:

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

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

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

4. Для побудови тестових послідовностей схем з пам'яттю запропонований дворівневий ГА, де на першому нижньому рівні будуються характеристичні послідовності: S-послідовності, R-послідовності, розрізнювальні D-послідовності, що дозволяють встановлювати в справній чи несправній схемах деякі елементи пам'яті (змінні стану) у визначені стани або розрізняти їх. Побудовані характеристичні послідовності використовуються в ГА верхнього рівня. Отримав подальший розвиток еволюційний алгоритм побудови тестової послідовності верхнього рівня, де використовуються заготовлені заздалегідь на нижньому рівні характеристичні послідовності.

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

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

7. Програмно реалізовані модулі багатозначного моделювання і розроблених генетичних алгоритмів побудови тестів, що інтегровані в систему моделювання і генерації тестів АСМІД.

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



Список опублікованих робіт за темою дисертації

1. Ю.А.Скобцов. Иерархические эволюционные алгоритмы построения проверяющих тестов цифровых последовательностных схем / Ю.А.Скобцов, В.Ю. Скобцов,Ш.Н.Хинди // Радіоелектронні і комп'ютерні системи.-ХАІ:2008.-№6.- с.159 -163.

2. Ю.А.Скобцов. Символьное моделирование неисправных последовательностных схем на основе кратной стратегии наблюдения выходных сигналов / Ю.А.Скобцов, В.Ю.Скобцов, Ш.Н. Хинди// Наукові праці Донецького національного технічного університету.серія:”Обчислювальна техніка та автоматизація”, Донецьк:2008.- випуск 15(130).- С122 -127.

3. Ю.А.Скобцов. Построение тестов для схем с памятью на основе кратной стратегии наблюдения выходных сигналов / Ю.А.Скобцов, В.Ю.Скобцов, Ш.Н.Хинди // Проблеми інформаційних технологій.-2008; №2(004). - С.194 -201.

4. Ю.А.Скобцов. Генерация тестов для последовательностных схем с использованием кратной стратегии наблюдения выходных сигналов / Ю.А.Скобцов,В.Ю. Скобцов,Ш.Н. Хинди // Науковий вісник Чернівецького університету. 2008. Збірник наук. праць. Вип. 423: Фізика.Електроніка.: Тематичний випуск “Комп'ютерні системи та компоненти”. Частина І. - Чернівці:ЧНУ:2008. - С. 29-36.

5. Ю.А.Скобцов. Двухуровневый алгоритм генерации проверяющих тестов для схем с памятью / Ю.А.Скобцов, В.Ю.Скобцов, Ш.Н.Хинди // Радіоелектронні і комп'ютерні системи.-ХАІ:2009;-№7.- с.136 -140.

6. Ю.А.Скобцов Иерархические генетические алгоритмы в генерации тестов последовательностных схем. / Ю.А.Скобцов, Ш.Н.Хинди // Тези доповідей і міжнародної конференції «Інтелектуальні систем в промисловості і освіти. - Суми;.- 2007».- С.167-169.

7. Ю.А.Скобцов. Символьное моделирование неисправных схем с памятью / Ю.А.Скобцов, В.Ю.Скобцов, Ш.Н.Хинди // Тезисы ІІ всеукраинской конференции ”Сучасні тенденціїї розвитку інформаційних технологій в науці, освіті та економіці”.-Луганск; -2008.- С.92 - 94.

8. Yu.A. Skobtsov. Application of Multiple Observation Time Strategy in Test Generation of digital sequential circuits/ Yu.A.Skobtsov, V.Yu Skobtsov, S.N.Hindi // Proceedings of X the international conference “the experience of designing and application of cad systems in microelectronics”.-Lviv- Polyana, Ukraine.-23 - 30 February;- 2009.- P.357-360.

9. Ю.А.Скобцов. Иерархический эволюционный алгоритм построения тестов для последовательностных схем / Ю.А.Скобцов, В.Ю.Скобцов, Ш.Н.Хинди // Труды десятой международной научно-практической конференции «Современные информационные и электронные технологии» («СИЭТ-2009», Одесса).-Том 1.- С.178.

10. Особистий внесок здобувача в публікаціях: У роботах, що виконані в співавторстві, автору належать: [1,3] - дворівневий генетичний алгоритм; [2] - дослідження різних стратегій спостереження вихідних сигналів; [4] - побудова характеристичних послідовностей; [5] - основний алгоритм побудови тестів на основі кратної стратегії спостереження вихідних сигналів; [6] - ієрархічний алгоритм генерації тестів; [7] - застосування кратної стратегії в побудові тестів; [8,9] - дворівневий алгоритм генерації перевіряльних тестів.



Анотація

ШУКРІ НАСРІ АЛІ ХІНДІ. Ієрархічні еволюційні методи генерації тестів цифрових систем.-Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.05 - «Комп'ютерні системи і компоненти». Державний вищий навчальний заклад «Донецький національний технічний університет», Донецьк, 2010.

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

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

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

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

Ключові слова: цифрові системи, перевіряльні тести, технічна діагностика, еволюційні методи, генетичні алгоритми, логічне моделювання.



Аннотация

ШУКРИ НАСРИ АЛИ ХИНДИ. Иерархические эволюционные методы генерации тестов цифровых систем.-Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности - 05.13.05 - “Компьютерные системы и компоненты”,

-Государственное высшее учебное заведение «Донецкий национальный технический университет», Донецк, 2009.

Дисертация посвящена решению актуальной научно-технической задачи - повышению эффективности методов построения проверяющих тестов на основе эволюционного подхода.

Рассмотрены основные определения проверяемости неисправностей в последовательностных схемах. Показано, что постановка задачи построения проверяющего теста для заданной неисправности в схеме с памятью существенно зависит от применяемой стратегии наблюдения выходных сигналов. В отличие от большинства ранее разработанных методов, в данной работе используется кратная стратегия наблюдения выходных сигналов, при которой различные пары состояний исправной и неисправной схем могут различаться в различные моменты времени, что позволяет повысить полноту тестов, но требует больших вычислительных ресурсов. Получил дальнейшее развитие метод логического моделирования в многозначном алфавите, который позволяет сократить число различаемых пар состояний исправной и неисправной схем. Разработан метод построения входных последовательностей, различающих пару состояний исправной и неисправной последовательностных схем на основе модифицированного генетического алгоритма.

Разработан двухуровневый алгоритм построения тестовой последовательности. При этом ГА первого нижнего уровня строит некоторые характеристические последовательности, которые позволяют устанавливать в исправной или неисправной схемах некоторые элементы памяти (переменные состояния) в определенные состояния или различать их. Генетический алгоритм второго верхнего уровня при генерации тестов в качестве структурных блоков использует входные последовательностями и характеристические последовательности, построенные на нижнем уровне ГА, что делает эволюционный поиск более "направленным" и повышает его эффективность. Применение многозначных алфавитов моделирования в процессе их генерации позволяет повысить эффективность.

Получил дальнейшее развитее метод различающих функций, который обобщает понятие различающей функции для комбинационных схем на схемы с памятью на основе кратной стратегии наблюдения выходных сигналов, что позволяет повысить полноту проверяющих тестов. Исследована проблема выбора множества моментов времени наблюдения выходных сигналов в процессе тестирования на основе кратной стратегии наблюдения выходных сигналов и определения соответствующего множества эталонных выходных реакций исправной схемы, что позволяет сократить объемы хранимой информации (эталонных реакций) при тестировании.

Разработано алгоритмическое и программное обеспечение для генерации тестов, которое позволяет повысить полноту проверяющих тестов за счет использования эволюционных методов. Проведена апробация разработанных методов на схемах международных каталогов ISCAS89, которая показала увеличение полноты тестов на 15%.

Ключевые слова: цифровые системы, проверяющие тесты, техническая диагностика, эволюционные методы, генетические алгоритмы, логическое моделирование.



Abstract

SHUKRI NASRI ALI HINDI. The hierarchic evolutionary methods of test generation for digital systems. - Manuscript. Thesis on competition of a scientific degree of the candidate of technical sciences on a speciality 05.13.05 - Computer Systems and Components. - Donetsk national technical university, Donetsk, 2010.

Dissertation is devoted to solution of the topical scientific and technical problem - increase of efficiency of test generation methods at the base of evolutionary approach. Basic determinations of fault detection are considered for sequential circuits. It is shown that problem of test generation for given fault for circuit with memory depends on the applied strategy of observation of output signals. Unlike the most before developed methods, the multiple strategy of observation of output signals is used in this work, where the different pair of the states of in good and fault circuits can distinguish at different moments of time, that allows to increase the fault coverage of tests, but requires more computing resources. The method of test sequences generation is proposed, which distinguish the pair of the states of in good and fault circuits on the basis of the modified genetic algorithm is developed. The two-level evolutionary algorithm of test sequence generation is developed. At this genetic algorithm at the first lower level generates some characteristic sequences which allow to set in memory elements to the certain states or to distinguish them. Genetic algorithm of second top level during the generation of tests as structural blocks uses an input sequences and characteristic sequences, built at lower level, that does an evolutional search more "directed" and promotes his efficiency. Application of multi valued alphabets in test generation also increases its efficiency. The algorithms and software are elaborated for test generation that allow to increase the fault coverage and test generation speed. The obtained results are approbated at the circuits of catalog ISCAS89 and show the good characteristics. Key words: digital systems, fault simulation, test generation, genetic algorithms, distributed calculations.

Размещено на Allbest.ru