автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.12, диссертация на тему:Методы и алгоритмы оценки тестопригодности цифровых устройств на этапе проектирования

МІНІСТЕРСТВО ОСВІТИ ТА НАУКИ УКРАЇНИ

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

Аль Матарнех Рамі

УДК 681.32:519.713

МЕТОДИ І АЛГОРИТМИ ОЦІНКИ ТЕСТОПРИДАТИОСТІ ЦИФРОВИХ ПРИСТРОЇВ НА ЕТАПІ ПРОЕКТУВАННЯ

05.13.12 - системи автоматизації проектувальних робіт

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

Харків — 2000

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

Робота виконана в Харківському державному технічному університеті радіоелектроніки Міністерства освіти та науки України

Науковий керівник: доктор технічних наук, професор

КРИВУЛЯ ГЕННАДІЙ ФЕДОРОВИЧ

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

Офіційні опоненти:

доктор технічних наук, професор ТУПКАЛО Віталій Миколайович Науковий метрологічний центр Міноброни України, вчений секретар, проф. кафедри комплексів управління космічними системами;

кандидат технічних наук, ЛИТВШОВА Євгенія Іванівна Харківський державний технічний університет радіоелектроніки, доц. кафедри проектування і експлуатації електронних апаратів.

Провідна установа Харківський державний політехнічний університет Міністерства освіти та науки України, кафедра обчислювальної техніки.

Захист відбудеться “ *2-5 " /C-&7/J? 2000 р. в '/-? ~~на

засіданні спеціалізованої вченої ради Д 64.052.02 в Харківському державному технічному університеті радіоелектроніки за адресою:

61166, м. Харкін. пр. Леніна. 14. fax: (0572) 40-91-13.

З дисертацією можна ознайомитися в бібліотеці Харківського державного технічного університету радіоелектроніки. м. Харків, пр. Леніна. 14.

Автореферат розісланий “ $ ____2000 р.

Вчений секретар спеціалізованої вченої ради

1__: Бсікоровайшій В. В.

І

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

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

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

Зв’язок роботи і паукоішми програмами, планами, темами. Реалізація результатів роботи здійснювалася відповідно до координаційних планів НАН України, Міністерства освіти:

"Програма науково-дослідних і організаційно-методичних робіт по інформаційно-методичному забезпеченню вищої освіти в умовах багато-ступінчастостГ, наказу Мінвуза України № 68 від Зіберезня 1992р.;

держбюджетних НДР: 234-1 “Програмно-інформаційне, методичне забезпече-ния підготовки бакалавра”, 453-1 '‘Дослідження і розробка перспективних засобів проектування і діагностики електронних систем із застосуванням їх в учбовому процесі по комп'ютернії! інженерії”.

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

Для досягнення поставленої мети в роботі розв’язані задачі:, .

— запропоновані методи і алгоритми, що реалізують оцінки тестопридатності;

— розроблені методи і алгоритми, що забезпечують отримання оцінок тестопридатності в САПР діагностичного забезпечення (ДЗ):

— запропоновані процедури отримання кількісних оцінок діагностеваносгі ЗОА на структурному та схемотехнічному рівнях.

Наукова пошана одержаних результатів.

— Сформульовані задачі тсстопридатного проектування і запропонована

струкіура системи тестопридатної автоматизації проекіувальних робіт (СТАПР) як частина системи автоматизованого проектування діагностичного забезпечення (САПР ДЗ). * . .

— Запропоновані умови і методика забезпечення діагностованості пристроїв на струкіурному рівні.

— Введені функції часових і апаратурних витрат на діагносту вання ЕОА і сформульовані дві задачі оптимізації витрат.

— Запропоновані кількісні показники діагностованості ЕОА на структурному рівні на моделюючих графах.

— Зроблені вибір і обчислення оцінок тестопридатності цифрового пристрою на схемотехнічному рівні.

— Запропонований метод оцінки тестопридатності по таблицях функціонування при неповному числі вхідних наборів.

Практичне значення одержаних результатів.

— Основні результати дисертаційної роботи впроваджені в учбовий процес кафедри АПОТ. Розроблені методи, що рекомендуються в дисертаційній роботі, і алгоритми зведені до пакету' прикладних програм “РАМКА”, який має зручний інтерфейс користувача в системі \Vindows: електронний варіант дисертаційної роботи використовується в курсовому і дипломному проектуванні студентів по спеціальності кафедри, а також в учбовій дисципліні “Основи теорії і проектування спеціалізованих комп’ютерних систем”:

— ряд результатів дисертаційної роботи впроваджено в підрозділах

з

знергоремонта підприємств;] Харьківенергоремонт. Зокрема, впроваджені програмиранжування і оптимального покриття, що вирішують задачі паралельного проведення ремонтних робіт і складання графіків профілактичних робіт (програма RANG), і оптимального покриття, що зменшує час тесту вання комп'ютерних енергетичних пристроїв (програма POKR). За результатами рекомендацій дисертаційної роботи розроблений бізнес-план створення САПР діагностичного забезпечення проведення ремонтних робіт “Діагностична експертна система фреймового типу", що охоплює і систематизує прикладне програмне забезпечення підприємства.

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

у 12] алгоритм визначення ціни досяжності вузлів графа для оцінки керованості та спостережності, а також кількісне обчислення діагностованості;

у [ЗІ основні ідеї діагностики з застосуванням математичного апарату теорії нечітких множин (fuzzy sets), показ його доцільності на початковому етапі низхідного проектування у вигляді експертної системи фреймового типу:

у [4] вибір значності багатозначної моделі цифрових пристроїв та фреймової структу ри станів автомату;

у [5} розроблено табличне подання моделей цифрових пристроїв. Апробацій результатів досліджень. Дана робота заслуховувалася на засіданні кафедри АПОТ, об’єднаному засіданні кафедр АПОТ і ЕОМ (1999 р. пр. № 1), університетських конференціях 1998, 1999 років (окремі розділи), на науково-методичній конференції “Використання комп'ютерних технологій в учбовому процесі” (м. Харків, 1997 p.), на міждунар. конференції “Математичне моделювання і інформаційні технології"’ (м. Бєлгород, 1998 р.)[5|.

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

Структура і об’єм дисертації. Дисертатція містить 193 сторінки, 20 малюнків, 13 таблиць, об’єднаних в структуру, що включає: вступ. 4 розділи, 14 підрозділів, висновки, список використаних джерел з 153 найменувнь. 4 додатки.

ЗМІСТ РОБОТИ

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

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

У другому' підрозділі з "і розглянутих методів оцінки тестопридатності вибрані два: оцінка тестопридатності детермінованим тестом і пошук дільниць схеми, що важко тестуються з метою їх подальшої модифікації. Наведена аналітика отримання оцінок -і-естопридатності і їх застосування в САПР. Підрозділ завершується класифікацією задач тестопридатності по рівнях проектування в САПР діагностичного забезпечення (табл. 1).

Таблиця 1 - Задачі тестопридатності вбудованого тестування

Рівень проектування Задачі, що вирішуються но забезпеченню тестопридатності

Архітектурний Задання вимог і обмежень тестопридатності

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

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

Логічний Реалізація функціональних блоків з урахуванням вимог поліпшення тестопридатності; оцінка додаткових апаратурних витрат на тестування.

Схемний Розробка топології кристалу; оцінка площі кристалу, потрібної для додаткових засобів тестування.

Треті й підрозділ описує структуру експертної системи фреймового типу

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

:тлпр~!

СЛПР

/ \

РКТ

Рис. 1 Структура системи тестопридатного автоматизованого проектування (СТАПР) як доповнення САПР ДЗ.

Тут блоки: РГІТГТ- розподілу параметрів тсстопридатності, АТ-аналізу тестопрндатності. РКК - розміщення контрольних крапок, ВВТ - вибору вбудованих тестів і АГТ - автоматичної генерації тестів. Обгрунтовується необхідність створення експертної системи фреймового типу з нечіткою логікою ] 31. де в кожному блоці (фреймі) за допомогою нечіткого правила, записаного в базу знань експертом, обирається певний параметр тсстопридатності. При такому підході виявляється цілком реальним використати майже всю існуючу бібліотеку методів і алгоритмів обчислення параметрів тсстопридатності, що забезпечтггь системі досить великий життєвий цикл. Запозичений з Іпісте? exe-файл для використання при роботі СТАГІР з нечіткими множинами і алгоритмами (наведено у додатку В).

Третій розділ. Чотири йош підрозділи присвячені методам і алгоритмам забезпечення оцінок тсстопридатності в САПР ДЗ. Так. в першому підрозділі розглянуті топологічні умови забезпечення тсстопридатності на структурному рівні для визначення бази і антибази гра(}кі і введені сумарні витрати при підключенні технічних засобів діагностування по формулі:

^Сі+ІС,

.1 Н

(1)

РИТИ

де С - об’єм витрат, необхідний для підключення засобів діагностування до активної контрольної крапки (КК) структури; причому і=1„.„ т; т - число активних КК;

С - об'єм схемних витрат для підключення к.-ой пасивної КК, 3=1,.., п; її

- число пасивних КК. Виходячи з вище наведених співвідношень для оцінки апаратурних^ і часових витрэт, сформульовано дві задачі оптимізації даних витрат.

- задача мінімізації апаратурних засобів діагностування.

Знайти

М IV!

іпіпС = ЕС1гЩг(\') +ХС]Г,ц]<,(\). (2)

і,і .,-і

де н.и=1? якщо \/ієВ( і 0 в іншому випадку. Вг - одна з баз числа Я баз графа;|ль=1, якщо V єВ5 і 0 в іншому випадку; Вч - одна з антибаз всіх антибаз Б графа;

- Друга задача пов’язана з мінімізацією часових витрат на діагностування ЕОА і формулюється таким чином.

Знайти

пііііТ8 = £ї>и(\0ік, (3)

к-1Ь1

де цы(У)=]. якщо Ук належить 1-тому шляху; і 0 в іншому випадку

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

2. коли на порядок опитання вузлів не накладається обмежень і він може бути довільшім.

У третьому підрозділі описується метод і ревізуючий його алгоритм узагальненого ранжування. Метод ранжування полягає в привласненні рангів як вершинам, так і з’єднуючим їх дугам. Це дозволяє провести часткове упорядкування елементів (вершин) графа з урахуванням як вимог розробника, так і особливостей структури графа. Мета ранжирування - пришіаснити ранг р кожній вершині гра(}>у Обмеження: - число рангів не більше за число вершин р<га; - вихідні дуги не можуть з'єднуватися в одну, так як при цьому утвориться безінерційний вентиль. Початкові умови - ранги дуг і вершин про-індексовані, але не визначені, тобто (рп)=(ро)=(). Алгоритм виконується в загальному випадку в 4 етапи:

1. Перший стіш. Вхідним дугам привласнюється перший ранг

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

вже відмінними від нуля значенням (тобто призначеними рангами), то ранг їх обчислюється за формулою:

ри=гшх(р„), Ур„*0 (4)

ІР<т)

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

Р„ = тах (р,л) + 1, Ури ф 0. (5)

ІРтп)

Якщо граф має контур зворотнього зв’язку, то алгоритм переходить до етапів 3 і 4, які мають назву пошук контура зворотнього зв'язку і обрив ланцюга зворотнього зв’язку відповідно.

3. Пошук контура зворотнього зв'язку (КЗЗ) проводиться методом

проходу від виходу вершини графа з кульовим рангом до входу із запам’я-

товуванням її індексу в списку вершин. Контур зворотнього зв'язку з на іі деннії. якщо будь-який індекс списку, що вносяться в ході пошуку вершин, повториться.

4. Обрив ланцюга контура зворотнього зв’язку проводиться на будь-якій одній з вершин з привласненням входу вершини першого рангу. Після виконання 4-го етапу алгоритм переходить до другого етапу, на якому' закінчується ранжування (див. рис. 2).

а) б)

РАНГИ- 1 2 3 4

Рис. 2 Графи: до а) та після ранжування б).

Четвертий підрозділ описує метод і відповідний йому алгоритм оптимального покриття, заснований на використанні міжгсстової семантики. Цінність цього алгоритму передусім в тому, що він дозволяє з безлічі тестів, розроблених для пристрою, що діагностується, визначити їх мінімальний набір, що скорочує час і трудомісткість тестування. Задача ставиться таким чином. Складається тестова матриця, стовпцями якої є об’єкти діагностування (несправності), а рядками заздалегідь розроблені тести, кожний з яких, як відомо, покриває декілька несправностей пристрою. Елементом такої матриці є булевий елемент, тобто

нуль або одиниця. Якщо тест-рядок виявляє несправність, закодовану номером стовпця, то на перетині рядка і стовпця ставиться 1 і нуль в іншому випадку':

1, якщо несправність ф виявлється і строюю тесту;

0, у зворотньому випадку

Отже, дана булева матриця 0(і,ср). така, що множина рядків {і,ер} неодноразово покриває яку сь частину стовпців {ф}. Потрібно знайти {к}с{1} такс, що к‘= тіп, тобто

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

де 0Т- транспонована матриця,, з іншого.

Оскільки відмінності існують як по рядках, так і по стовпцях, то процедуру аналізу можна зробити повною і замість (7) написати

Отримані при цьому матриці квадратні і симетричні відносно головної діагоналі, що характерно для коваріаційних матриць. Розмірність її, рівна числу рядків, Р2 - числу стовпців. Привласнимо тому першій матриці ім’я (тобто рядків), а другий - ^ (стовпців). Назвемо всі елементи головної діагоналі власними частотами / (і,ср), / (і,ф), а всі недіагональні елементи матриць -взаємними частотами / (і,ф). Аналіз матриць проводиться з метою вибору з матриці 0 її підмножин шляхом стиснення початкової матриці як по рядках, так і по стовпцях. Якщо зажадати, щоб матриця результату формувалася окремо, то задача зводиться до отримання з початкової матриці - матриці нульової розмірності. Аналіз починається з пошуку' умови для стиснення, яка виглядає так:

к = тіп к < і ,

(6)

(7)

Г, = 0 • 9х ; ]■'. =0т-0.

. . /(1,0 = Лі, Ф) (9)

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

Основою для прийняття рішення про стиснення є порівняння двох власних частот головної діагоналі, на яго,' проектується задовольняюча рівнянню (9) взаємна частота /(і,ф) як по вертикалі, так і по горизонталі Р: .

/(і,і)іН/(ф,ф), и

де *Л - вирішальне правило.

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

Щ =/0,0>/(Ф,Ф) у • (10)

Для F стовпців справедливе протилежне правило:

9t: = /(і, О < /(ф, ф) U . (II)

Знак І) означає видалення рядка або стовпця відповідно. Процедура пошуку рядків, що видаляються і стовпців початкової матриці повторюється доти, доки не наступить ситуація: 1. умов для стиснення по F, (рядків) немає; 2. умов для стиснення по Р2(стовиців) немає: 3. матриця 0 - не нульова. У цьому випадку алгоритм приступає до “зважування” всіх рядків, що залишилися в матриці. Вага кожного з радив, що залишилися з первинними індексами, підраховується по форму лі

■ Р(0=Е7тЦ-. (12)

■ ПО І 7'( ф )

де Е - сума дробів, що дорівнює числу одиниць в рядку;

2(ф) - цс сума одиниць в стовпці, що має одиницю у зважуваному рядку.

Рядок з максимальною вагою виноситься в ре:іультат. що формально описується так:

Л* = max Р(і) її . (13)

ПО RCIX І

При наявності декількох рядків з однаковою вагою в результат виноситься тільки одна. Матриця при цьому стискується як за рахунок винесеного в

результат рядка, так і за рахунок видалення тих стовпців, в яких цей рядок має одиниці. Лістішг програми наведений в додатку Б.

У четвертому розділі наводяться кількісні оцінки діагностованості ЕОА на структурному [2] і схемотехнічному 11] рівнях автоматизованого проектування.

У першому підрозділі розглядаються кількісні показники діагностованості ЕОА на структурному рівні. Припустимо, що маємо граф С(У. Е) структури ЕОА з т активними і п пасивними контрольними крапками (рис. 3).

Число внутрішніх вузлів графа, безпосередньо не пов'язаних з системою діагностування шляхами одиничної довжини, дорівнює К=|У|-(т+п). Для внутрішніх К вузлів графа ціна досяжності може бути визначена як сума

(і = Гк), (14)

І Г-1

де Бі - ціна досяжності і-го вузла графа;

Б) - власна діагностованість пристрою, відповідного і- му вузлу граф;).

З у рахуванням ціни досяжності Б, для кожного вузла структури ЕОА можна визначити струкіурну діагностованість вузла як:

(і = Гш). (15)

Результати розрахунку' діагностованості наведені в таблиці 2.

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

V і 2 3 4 5 6 7 8

А 0,8 0.75 0.8 0,75 0,8 0,75 0.8 0,75

& о; 1 0,8 0.72 0,54 0.8 0.64 0,72 0.54 0,53 0.424 0.556 б~4 17 ~ 0,59 0,472' 0,438 0.329

У другому підрозділі наводяться кількісні оцінки тсстопридатності цифрових пристроїв на схемотехнічному' рівні. Розглянутий вибір і обчислення оцінок тсстопридатності для цифрового пристрою, які характеризують витрати на побудову діагностичного забезпечення і дозволяють визначити дільниці схеми, що викликають труднощі при цифровому діагностуванні детермінованими методами. Моделлю пристрою при обчисленні таких оцінок є граф, вузлами якого є найпростіші елементи (НЕ) пристрою, а дугами - функціональні зв’язки між ними. Для кожного НЕ задаються кубічне та О-локрнття. Для обчислення оцінок тсстопридатності цифрового пристрою введена низка коефіцієнтів, що характеризують НЕ: \У- коефіцієнт абсолютної складності НЕ. який для одновьіходо-вьгх НЕ відноситься до самого елемента, а для багато в ьіходов ьтх - до його виходу, V- коефіцієнт складності транспортування сигналу через НЕ, який визначає витрати на просування сигналу від зовнішнього входу елемента до його виходів з урахуванням складності НЕ. Вказані коефіцієнти більш точно характеризують витрати на побудову ДЗ детермінованими методами і вимагають менших витрат на підрахунок, ніж відомі керованість та спостережність. Пов'язаний з кількістю рядків в покритті та кількістю істотних змінних в кубах, він може бути підрахований за формулою:

т

\У=£РіТі, (16)

і 1

де Р; - щільність і- го кубу (кількість вхідних змінних НЕ. не рівних х); Т.

- кількість двійкових тактів, що реалізуються кубом покриття; ні кількість кубів в покритті. Визначимо витрати на транспортування сигналу через НЕ по певному ]-му входу (і= 1. п). п кількість зовнішніх входів схеми, за наступною формулою:

ІГгРіл-Гз-Ті.,. (17)

' її м

де В - кількість кубів в 1- ій умові транспортування; в кількість умов транспортування; Г Г2 - нормуючі коефіцієнти, задаючі співвідношення між ціною витрат машинного часу і оперативної пам'яті при реалізації детермінованого алгоритму активізації шляхів в схемі. Складність транспортування для]- ой лінії схеми обчислюється таким чином

С;

■ піт

і---]

:ію

де га - число істотних входів НЕ.

Для знаходження оптимальної стратегії обирається мінімум або максимум альтернативи для НЕ:

С3 - орі С'• . (19)

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

\у(р,) = 'ю-,,<‘1"-11») + тах<<!'-‘1;). (20)

к

де К - число наборів на даному кроці визначення важливості ознаки Р; д00 кількість наборів, в яких Р.= 0,/(х)= 0: с^1 те ж для Р=0,,/(х)=1; q10 тс ж для Р= 1../(х)= 0; с],' те ж для Р= І,у(х.)=І.

Таблиця 3 - Скорочена таблиця істинності у вигляді к\бічного покриття.

Р| І>, 1>, І’і №

X X X ~х~ 0 ...... () ”1 ~ 0 .....

X 0 1 (! 1

X 0 1 1 1

0 1 1 0 1

1 1 1 0 0

0 1 ] ] 1 і 1 “ПТ 1 .......

Рис. 4 Схема цифрового пристрою

Рис. 5 Розпізнаюче дерево

ВИСНОВКИ

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

2. Сформульовані задачі тсстопридатного проектування і запропонована структура системи тестопридатной автоматизації проектних робіт (СТАПР) як частина САПР ЗД.

3. Запропоновані умови і методика забезпечення діагностованості пристроїв на структурному рівні.

4. Введені функції часових і апаратурних витрат на діагностування ЕОА і вирішені задачі оптимізації витрат.

5. Запропоновані кількісні показники діагностованості ЕОА на структурному рівні для моделюючих графів.

6. Зроблені вибір і обчислення оцінок тсстопридатності цифрового пристрою на схемотехнічному рівні.

7. Запропонований метод оцінки тсстопридатності по таблицях функціонування при неповному числі вхідних наборів.

Таким чином, був зроблений конкретний внесок в розв’язання су часних проблем технічної діагностики. Подальші роботи повинні вестися у напрямі интелекгуалізації ЕОМ і в тісному зв’язку' з потребами практики.

СПИСОК ОПУБЛІКОВАНИХ ПРАЦЬ ПО ТЕМІ ДИСЕРТАЦІЇ

1. Аль Матарнех Р. Дж.. Кривуля Г. Ф., Шкиль А. С. Количественные опенки тсстопригодности цифровых устройств на схемотехническом уровне //

Радиоэлектроника и информатика.- 1998. - №4 - С. 77-81.

2. Аль Матарнех Р. Дж., Дуби не ка я Н.Г. Количественные показатели диагностируемое™ ЭВА на структурном уровне // Информационно-управляющис системы на железнодорожном транспорте. - 1998. - №6. - С. 60-63.

3. Matarnah R. J., Kriuilia G. F Expert systems using fu/./.y logic // Радиоэлектроника и информатика. - 1998. - №1(02) - С. 53-56.

4. Аль Матарнех I3. Дж., Кривуля Г. Ф.. Хаханов В.И. Многозначные модели цифровых устройств // Труды междунар. Конф. Математическое моделирование и информационные технологии. Том 8. - Белгород.- 1998. - С. 72-79.

5. Matarnah R. J., Hahanov V. I., Krivulia G. F. Multivalued models of digital circuts // Proc. International conf. Mathematical modeling and information technologies MMIT-97. Vol. 1. Belgorod (Russyia). - 1997. - P. 15-16.

АНОТАЦІЯ

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

Дисертація на здобуття наукового ступеня кандидата технічних наук з спеціальності 05.13.12 - системи автоматизації проектувальних робіт. Харківський державний технічний університет радіоелектроніки, Харків, 2000.

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

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

АННОТАЦИЯ

Аль Матарнех Рами Дж. Методы и алгоритмы оценки тсстопрпгод-ноети цифровых устройств на этапе проектировании. - рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.12 - системы автоматизации проектных работ. - Харьковский государственный технический университет радиоэлектроники. Харьков, 2000. *

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

ссшитики структуры. Предлагается формирование САПР диагностического обеспечения на основе экспертной системы фреймового типа с элементами нечеткой логики.

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

ABSTRACT

Rami J. О. Al-Matarnch Methods and algorithms for the estimation of testability for the digital devices on the stage of design. - Manuscript.

Disscrtalionfora Ph.D. degree of engineering science by a specialty 05.13.13

- computer-aided design system. - Kharkov state technical university of a radioclectronics engineering, Kharkov. 2000,

The purpose of this dissertaion is the development of methods and algorithms, w hich arc capable to produce an objective estimation of testability for the diagnosed object. For this aim the concern devoted to obtain the necessary relations and procedures of the testability's estimation at the main stages of descending computer-aided design.

The growth of complexity of modern computer and devices sharply was raised the requirements to qualitative diagnostic support for the microelectronic apparatus. During the last years the development of methods of teclmical diagnostics lagged behind the intensively progressing of elemental base of computers. Each of qualitative changes of element base connected with transition from valves to mcdium-scale integrated circuit, and then to large-scale integrated circuit and very large-scale integrated circuit, more and more aggravated lag. augmenting a rupture between complexity of modern computer and the possibility of their technical diagnosing, ft reduced in steady growth of expenditures on creation diagnostic support for such devices. The overcoming of available lag is possible only on the basis of the accelcrated development and implantation of the automized design techniques of diagnostic support, and also resources of diagnosing as the constituents of technological processes. For micro-electronic controlled digital devices, traditional methods of construction of diagnostic support grounded on the digital gate or medium-scale integrated circuit for the representation of the objcct of diagnosing, the absences of datas about an exact gate equivalent, inadequate mapping really originating defects by model of constant faults are unsuitable becausc of the large dimension of diagnostic support model. The overcoming of the indicated difficulties is possible in two directions: at first, development of new formal methods of construction of diagnostic support (firstly test generation) and, secondly, by support high testability on design stages. Within the framework of the first direction the greatest interest is represented

by the methods of functional construction of the tests, based on the functional description of the diagnostic support. But such methods difficultly give in lo automation, require large expenditures of memory- to save of the tests, I hey are suitable only for programmed or micro-programmed accessible resources.

Increasing problems of construction of diagnostic support, connected to growth of integrations, which is forcc the developers to take into account such problems of testability, as time of construction of diagnostic support, time of testing, entirety detection of defects already on tlie design stages of the object. The purpose of testability designing, are such changes of the initial project, at which the preset parameters of testability will be provided at minimum additional expenditures.

In this dissertation, for the first time arc formulated the requirements of an estimation testability for a modelled 'site of computing structure (differential) and for the device as a whole (integral); formulated the tasks of testability of designing and offered the structure of the testability's automation system of design operations as a part of a CAD; offered the conditions and technique of support of diagnostic of devices at a structural level; entered the functions of temporary and instrument expenditures on diagnosing microelectronic devices and solved the tasks of optimization of expenditures; offered the quantitative metrics diagnostic at a structural level under the simulating graphs: produced choice and calculation of estimations of testability of the digital device on schematic and structural level; offered at deficient number of dialingins the method of an estimation testability by the tables functional.

In this research received further development in the methods of testability estimation for computer re.sourccs . The proposed algorithms increase the quality and the efficiency of testability estimation with the help of using semantics structure. Suggested built CAD on the basis of the expert systems using the elements of the fuzzy- logic.

Keywords: testability, logical circuit, computer system, graph, matrix, built-in lest, semantics, fuzzy logic, procedure.