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

РАДІОЕЛЕКТРОНІКИ

ХАК Х.М. ДЖАХІРУЛ

УДК 681.32:519.713

КУБІЧНЕ МОДЕЛЮВАННЯ НЕСПРАВНОСТЕЙ ДЛЯ АНАЛІЗУ ЯКОСТІ ТЕСТІВ ПРИ ПРОЕКТУВАННІ ЦИФРОВИХ СИСТЕМКУБІЧНЕ МОДЕЛЮВАННЯ НЕСПРАВНОСТЕЙ ДЛЯ АНАЛІЗУ ЯКОСТІ ТЕСТІВ ПРИ ПРОЕКТУВАННІ ЦИФРОВИХ СИСТЕМ

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

АВТОРЕФЕРАТ

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

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

Харків 2001

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

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

Науковий керівник доктор технічних наук, професор Хаханов Володимир Іванович,

Харківський державний технічний університет

радіоелектроніки, професор кафедри

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

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

Дербунович Леонід Вікторович,

Національний технічний університет “Харківський політехнічний інститут”, професор кафедри автоматики і управління в технічних системах.

кандидат технічних наук Литвинова Євгенія Іванівна,

Харківський державний технічний університет

радіоелектроніки, доцент кафедри проектування й експлуатації електронних апаратів

Провідна установа: Національний технічний університет України “КПІ”,

Міністерство освіти і науки України, м. Київ

Захист відбудеться 27 червня 2001 року о 14 годиі на засіданні спеціалізованої вченої ради Д 64.052.02 у Харківському державному технічному університеті радіоелектроніки за адресою: 61166, м. Харків, пр. Леніна, 14.

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

Автореферат розісланий 22 травня 2001 року

Вчений секретар

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

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

Розвиток нових технологій автоматизованого проектування і діагностики цифрових систем обумовлено: появою могутніх обчислювальних машин; мов опису апаратури високого рівня (VHDl, Verilog, System C, Abel, EDIF); компіляторів для створення систем верифікації і моделювання; необхідністю створення складних цифрових проектів на одному кристалі (System on Chip); технологічним проривом в області субмікронних технологій виготовлення мікросхем.

Реалізація цифрових систем на програмувальних логічних інтегральних схемах (ПЛІС) – Field Programable Gate Array (FPGA), Complex Programable Logic Device (CPLD) – гідно конкурує з проектами на основі використання базових матричних кристалів (БМК), сигнальних процесорів. Такий успіх визначається: –

застосуванням нових технологій розробки і реалізації цифрових систем на основі використання Hardware-Software Cooperation-Design; –

зменшенням часу проектування, верифікації і виготовлення складного обчислювального пристрою до 4-5 місяців; –

високою швидкодією виконання операцій у ПЛІС (до 500 Мгц); –

великим ступенем інтеграції елементів на кристалі (4 млн.).

Разом з перевагами цифрових проектів на ПЛІС існують і проблеми їхньої верифікації на всіх стадіях розробки аж до їхньої реалізації на кристалі з застосуванням високотехнологічних САПР (продукти фірм: Aldec, Altera, Cadence, Actel, Mentor Graphics, Xilinx, Sinopsys), для рішення яких необхідний розвиток таких методів, алгоритмів і програм, що повинні забезпечувати:

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

2) генерацію тестів у вигляді покриття одномірних шляхів активізації для перевірки одиночних константних несправностей (ОКН);

3) інваріантість стосовно рівнів опису цифрових проектів і прийнятна швидкодія алгоритмів моделювання несправностей для оцінки якості тестів і побудови процедур пошуку дефектів;

4) верифікацію і діагностування синтезованих цифрових пристроїв (ЦП) на основі FPGA, CPLD;

5) можливість рівнобіжного виконання векторних операцій логічного аналізу для генерації тестів і оцінки їхньої якості;

6) підтримку стандарту VHDL для опису ЦП і згенерованого тесту;

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

Вагомий внесок у розв,язок проблем верифікації і моделювання цифрових систем внесли вчені: J.P.Hayes, D.B.Armstrong, А.Г.Биргер, Y.H.Levendel, M.A.Breuer, M.Abramovici, П.П.Пархоменко, А.М.Романкевич, Д.В.Сперанський, Р.Й.Убар, Ю.А.Скобцов, Л.В.Дербунович, Ю.В.Малишенко, А.Э.Таргамадзе, В.Н.Ярмолик, В.П.Чипулис, В.А.Твердохлебов.

Актуальність теми. При рішенні практично всіх задач технічної діагностики основою є моделювання несправностей. Найбільш кращим по швидкодії є дедуктивний метод аналізу дефектів. Він дозволяє за одну ітерацію обробки схеми визначити всі константні несправності, що перевіряються на вхідному тестовому векторі. Але даний метод орієнтований на вентильний рівень опису цифрових схем, оскільки існує проблема генерування вихідних списків несправностей (output fault list generation) для примітивів функціонального і поведінкового рівнів. Для її рішення пропонуються моделі й алгоритми кубічного аналізу несправностей, що дозволяють обробляти цифрові схеми, описані на вентильному, функціональному й алгоритмічному рівнях з метою оцінки якості тестів, побудови таблиць несправностей для контролю і пошуку дефектів.

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

522-1 – “Розробка учбово-методичного забезпечення і програмно-апаратних засобів для нових навчальних дисциплін з комп’ютерних наук і комп’ютерної инженерії”, № гос. реєстрації 0197U012176.

102 – “Розробка основ нових інформаційних технологій в автоматизованому проектуванні, діагностиці засобів радіоелектронної апаратури й обчислювальної техніки”, № гос. реєстрації 0100U03417.

Університетська програма міжнародного співробітництва в області освіти, науки “Стратегічне партнерство” від 10.03.2000.

Договір про науково-технічне співробітництво з фірмою Аldес Inc. (Las-Vegas, Nevada, USA) від 6.06.1999 р.

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

Об’єкт дослідження – цифрові системи, що представлені на мовах опису апаратури високого увровня, орієнтовані на їхню реалізацію в кристалах FPGA, CPLD.

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

Методи дослідження представлені апаратами: булевой алгебри, теорії множин, кубічного числення – для опису функцій примітивних елементів; теорій автоматів, графів – для реалізації імплікативних процедур у цифрових системах; технічної діагностики, логічного моделювання – для розробки алгоритмів аналізу дискретних об’єктів.

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

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

модифікації автоматної моделі синхронного цифрового примітива, описаного двотактним кубічним покриттям (КП), що дозволяє виконувати подійний аналіз послідовностних асинхронних схем з метою моделювання справної поведінки і несправностей;–

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

розробки алгоритму кубічного моделювання несправностей, що дозволяє за одну ітерацію визначати всі дефекти, які перевіряються тест-вектором, шляхом теоретико-множинного аналізу кубічних покрить примітивних елементів (ПЭ);–

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

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

Наукова новизна отриманих результатів, що виносяться на захист:–

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

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

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

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

Практичне значення отриманих результатів визначається:–

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

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

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

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

Результати дисертації у вигляді програмних додатків використовуються на підприємствах; ТОВ НПП “Харьковэнергоремонт” (довідка про впровадження від 12.11.2000), ЗАТ “Енергозбереження”, Харків (довідка про упровадження від 27.02.2001); а також у навчальному процесі Харківського державного технічного університету радіоелектроніки (акт про впровадження від 11.03.2001) і Національного технічного університету “Харківський політехнічний інститут” (довідка про впровадження від 24.03.2001).

Особистий внесок здобувача. Всі основні результати отримані автором особисто. У роботах, опублікованих спільно, автору належать: [2] – моделі несправностей цифрових примітивів, форма, концепція, операції лолгичного аналізу; [3] – кубічний алгоритм моделювання дефектів для FPGA, аналітичні формули транспортування списків дефектів; [4] – аналіз несправностей і доповнень до станів автоматних змінних цифрових систем; [5] – реалізація моделювання дефектів цифрових систем на основі FPGA; [6-10] – моделі й алгоритми аналізу справної поведінки і несправностей для системи генерації тестів у САПР Active-HDL.

Апробація результатів наукових досліджень здійснювалася на: VI-th Conference CADSM “The Experience of Designing and Application of CAD System in Microelectroncs”, Lviv – Slavsko, 2001; конференції “Автоматика-97”, Черкаси, 1997; конференції “Автоматика-96”, Сімферополь, 1996; конференції “Утворення і віртуальність 2000”, Севастополь, 2000; IV міській науково-технічній конференції “Актуальні проблеми сучасної науки в дослідженнях молодих учених Харківщини”, Харків, 2001.

Публікації. Основні результати роботи опубліковані в 10 наукових працях, серед яких 5 статей у виданнях, що затверджені ВАК України, інші 5 є тезами доповідей на конференціях.

Структура й обсяг дисертації. Дисертаційна робота містить 173 сторінки, 20 рисунків (на 14 с.), 3 таблиці (на 2 с.). Її структура включає: вступ, 5 розділів, висновок, список використаних джерел з 131 назв (на 14 с.), 2 додатки (на 24 с.).

ЗМІСТ РОБОТИЗМІСТ РОБОТИ

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

Перший розділ присвячений аналізу опублікованих робіт в області технічної діагностики цифрових систем, реалізованих на кристалах ПЛІС. Відзначено, що високий рівень інтеграції еквівалентних вентилів, розмірність і складність цифрових систем привели до виникнення проблем, які пов’язані з верифікацією проектів на стадіях їхнього введення, синтезу й імплементації в кристалі. Для їхнього вирішення необхідні нові моделі, методи й алгоритми технічної діагностики, інваріантні до елементної бази, мовам опису апаратури високого рівня, розмірності і функціональній складності цифрових систем. Відзначено, що такими є:–

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

дедуктивні і спільні (concurrent) методи моделювання несправностей, що мають максимальну швидкодію облаботки схем, але мають недолік, пов’язаний зі складністю виконання процедур транспортування списків несправностей через примітивні елементи невентильного рівня зображення;–

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

Проведений аналіз публікацій за темою дисертації дозволив зробити висновок, що незважаючи на різноманіття моделей, методів і систем опису й аналізу цифрових пристроїв, їхнє застосування для проектування і верифікації високоінтегрованих систем на кристалах FPGA, CPLD, що складаються з мільйонів еквівалентних вентилів утруднено в зв’язку з існуванням проблем: 1) недостатньо високої швидкодії методів моделювання; 2) відсутності універсального підходу до аналізу несправностей цифрових систем невентильного рівня зображення об’єктів. Перша успішно вирішується використанням апаратурних симуляторів (Hardware Embedded Simulation). Розв,язанню другої проблеми, актуальність якої підкреслюється в багатьох публікаціях, присвячена дисертація.

В другому розділі представлена автоматна модель цифрової системи у вигляді структури взаємозалежних функціональних елементів, описаних кубічними покриттями в багатозначному алфавіті: A2={Q=00, E=01, H=10, J=11, O={Q,H}, I={E,J}, A={Q,E}, B={H,J}, S={Q,J}, P={E,H}, C={E,H,J}, F={Q,H,J}, L={Q,E,J}, V={Q,E,H}, Y={Q,E,H,J}, A1={0,1,X={0,1}}, (U)}, що призначена для вирішення задач: реалізації процедури прямої імплікації – справного моделювання невхідних ліній при заданих умовах у трійковому алфавіті на входах цифрового об’єкта; виконання процедури зворотної імплікації на основі застосування П-алгоритма з метою визначення вхідних умов, що задовольняють заданому стану вихідних (невхідних) змінних; моделювання одиночних константних несправностей, що задаються координатами кубічних покрить примітивних елементів цифрової структури.

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

Для виконання процедур аналізу КП вводяться векторні операції.

1) Перетинання одномірних векторів М и С у замкнутому теоретико-множинному алфавіті є непорожнім, якщо результуючий вектор не містить символів порожньої множини

2) Об’єднання векторів у замкнутому теоретико-множинному алфавіті буде непорожнім (порожнім), якщо кожний з них не містить символів (містить символи) порожньої множини

3) Непорожнє об’єднання несуперечливих результатів перетинань вхідного вектора з кубами покриття визначає стан всіх змінних цифрового автомата в замкнутому теоретико-множинному алфавіті

де E – вектор вхідних умов; C= {C1,C2, ... , Ci, ... ,Cn} – кубічне покриття.

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

1) Багатовиходовий комбінаційний чи послідовностний елемент, у якому кожен вихід функціонально залежить від усіх входів:

Для даного ПЕ визначається повне КП, що задає всі можливі переходи на просторі вхідних станів. Приклади ПЕ: логічні елементи, суматори, комутатори, дешифратори, перетворювачі кодів, тригери, лічильники, кінцеві автомати, що керують.

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

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

3) Багатовиходовий ПЕ, що має двонаправлені лінії, які повинні бути як входами, так і виходами при описі КП примітива:

4) Багатовиходовий примітив, що має неповне покриття, яке формує окремі функції ПЭ на векторі суттєвих змінних:

5) Структура елементів, що мають повні КП, навантажених на виходи одного потенціалу – монтажна логіка І (ЧИ):

6) Сукупність елементів з неповними КП (окремі операції ПЕ), що має виходи одного потенціалу – об’єднання виходів для визначення їхніх значень за допомогою аналізу всіх навантажених на них примітивів:

7) Функціонали, що реалізують арифметичні операції при використанні в якості входів і виходів ті ж самі лінії:

8) ПЕ, що мають на входах і виходах багаторозрядні шини і керують передачею інформації від A до B, і навпаки:

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

Розділ 3 присвячений розробці процедур і алгоритму кубічного моделювання несправностей, що є новою технологією обробки цифрових схем функціонального рівня зображення. Алгоритм дозволяє за одну ітерацію моделювати всі ОКН цифрового пристрою, що перевіряються тест-вектором. Його достоїнство полягає в інваріантості до рівнів (вентильного, функціонального, алгоритмічного) опису цифрових схем. Процедури аналізу кубічних покрить дають можливість: одержувати дедуктивні формули моделювання несправностей функціональних елементів; проектувати компілятивні симулятори для обробки ЦП довільного рівня опису; проектувати апаратурні швидкодіючі симулятори.

Концептуальна модель последовністного примітива, що входить до складу цифрового пристрою, має вигляд M=<X, Y, Z, f, g>, де X=(X1,X2,...,Xi,...,Xm), Y=(Y1,Y2,...,Yi,...,Xh), Z=(Z1,Z2,...,Zi,...,Zk) – множини вхідних, внутрішніх і вихідних автоматних змінних, відносини між якими описуються наступними характеристичними рівняннями: Y(t)=f[X(t-1), X(t), Y(t-1), Z(t-1)]; Z(t)=g[X(t-1), X(t), Y(t-1), Y(t), Z(t-1)]. Змінні Z(t) відрізняються від Y(t) тим, що перші можна спостерігати за вихідними лініями, а Y(t) у цьому сенсі є внутрішніми. Математичній моделі ставиться у відповідність її структурний еквівалент (рис. 1). Функціональний (последовністний) елемент задається у форматі наступних компонентів: F2 = < ( t-1, t), (X,Z,Y), {A2}>, де (t-1,t) – два автоматних сусідніх такти в описі функцій переходів-виходів; (X,Z,Y) – вектори вхідних, внутрішніх і вихідних змінних; {A2} – двотактний алфавіт опису станів (переходів) автоматних змінних.

Для багатовиходового функціонального елемента, заданого кубічним покриттям З, обчислення всіх 2m булевих похідних, що формують вихідний список несправностей Sr за виходом r, визначається виразом:

де Sj – список вхідних дефектів на лінії j; Tr, Tj – вихідна і вхідна координати вектора справного моделювання; – несправність виходу примітива, що є теоретико-множинним доповненням стосовно його справного стану; – вхідна і вихідна координати i-го куба покриття З, n – число кубів; m – кількість вхідних ліній; k – число вихідних ліній у примітиві.

Приклад. Задано кубічне покриття функції

Вхідні списки несправностей визначені підмножинами:

Визначити вихідний список несправностей для тест-вектора 1111.

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

де Si – частковий список, що формується кубом Ci; – список дефектів, що перевіряється тест-вектором T і одержується об’єднанням .

Для тест-вектора 0100 результат моделювання тих же несправностей дорівнює

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

Проблема моделювання цифрового пристрою формулюється в умовах невизначеності одного з компонентів моделі , де M – модель, що представлена кубічним покриттям C; L – кубічне покриття списків (що перевіряються) доповнень (КПСД) (Fault Lists Cubic Complement – FLCC), T – тест перевірки цифрового пристрою. Покриття доповнень для примітива чи цифрового пристрою задається в наступному вигляді: L= (L1, L2, ..., Li, ..., Ln), де Li = (Li1, Li2, ..., Lij, ..., Liq) – куб, що включає вхідні, внутрішні, вихідні координати: = , q=m+h+k; = {0, 1, X}; 0 – визначає вирахування списку ; 1 – задає перетинання ; X={0,1} – ідентифікує неістотність списку доповнень . Якщо – вихідна спостерігаєма змінна, то (0) 1 – є ідентифікатор (не-) перевірки доповнення куба на виході r, X={0,1} – задає невизначений стан вихідної координати , яке можна інтерпретувати як 0, так і 1.

Кубічне покриття списків доповнень, що перевіряються, L для вектора T і покриття примітива С обчислюється по лінійному алгебраїчному рівнянню

, (1)

де – координатна операція XOR, що визначає взаємодію компонентів T, C (L) у трійковому алфавіті:

Універсальна формула аналізу КПСД, отриманого в результаті застосування (1) до тест-вектора Т и покриття багатовиходового примітива С для визначення за виходом r списку доповнень, що перевіряються, Lr, має наступний вигляд:

(2)

де

– розглядається як список доповнень, що відноситься до j, який слід відраховувати з доповнень, що перевіряються за невихідними лініями примітива; – доповнення, які необхідно перетинати з невихідними списками. Якщо тест-вектор визначений у трійковому алфавіті , то після одержання покриття списків доповнень, кожен куб слід верифікувати за правилом Тут знак “–” еквівалентний теоретико-множинному вирахуванню; – вхідні координати куба покриття (), модифіковані для виконання прямої імплікації з метою визначення суттєвості координат вектора відносно стану виходу примітива r, за правилом

Відповідно до процедури (2) будується алгоритм кубічного моделювання доповнень до тесту цифрового пристрою (початкова установка номера вектора t=0):

1) Моделювання справної поведінки примітива на тест-векторі . Якщо – формується список L(T) перевірених доповнень на тесті T. Кінець моделювання. Інакше, – перехід до п.2.

2) Якщо всі елементи схеми оброблені , виконується порівняння векторів справних станів ліній у двох сусідніх ітераціях. Якщо вектори ідентичні , кінець моделювання і перехід до п. 3. Інакше – виконується перехід до пункту 1.

3) Визначення списків доповнень зовнішніх входів як . Для невхідних ліній пристрою виконується присвоювання для моменту часу t.

4) Моделювання доповнень примітива за процедурою (4.6). Додавання до отриманого списку доповнення до вихідної лінії примітива цифрового пристрою .

5) Якщо після обробки всіх примітивів у двох сусідніх ітераціях виконується умова , здійснюється перехід до п. 7.

6) Якщо при аналізі сусідніх ітерацій доповнення, що перевіряється, на лінії зникає, то його слід виключити з процедури моделювання поточного вектора

.

Перехід до пункту 4.

7) Формування списку доповнень, що перевіряються

за усіма виходами пристрою, які спостерігаються, і перехід до пункту 1.

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

де – число кубів і змінних у покритті , – середня довжина списку доповнень для кожної лінії схеми, Q – загальне число ліній у цифровій схемі; 2 і 3 – кількість ітерацій аналізу примітива і схеми відповідно.

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

Задачі, що розв’язуються за допомогою пакета моделювання дефектів: 1) Побудова тестів, що перевіряють, для цифрових пристроїв, заданих у формі булевих рівнянь. Мови опису: VHDL, Verilog. 2) Генерація тестів для цифрових проектів, заданих булевими рівняннями. Мова опису: VHDL. 3) Визначення якості тестів шляхом моделювання одиночних константних несправностей. Об’єкт діагностування – цифровий проект, орієнтований на його реалізацію в апаратурі FPGA, CPLD.

Система Active-HDL призначена для проектування цифрових систем і дозволяє виконувати їхній опис на мовах VHDL і Verilog, у графічних форматах змістовного графа автомата чи опису структури пристрою. До складу системи входять програми: керування проектом, введення проекту на мовах опису апаратури, введення графічного ієрархічного опису схеми, введення змістовного графа автомата, компіляції, логічного моделювання, перегляду часових діаграм, формування тестових впливів оператором, перегляду списків, інтегрованого налагодження з покроковим виконанням програми, генерації шаблонів і сервісу.

Базовий модуль Fault simulator призначений для моделювання ОКН цифрової схеми, описаної на функціональному рівні у вигляді кубічних покрить. Задачі, що розв’язуються програмою: 1) Моделювання ОКН за кубічними покриттями функціональних елементів. 2) Моделювання доповнень до стану ліній схеми за кубічними покриттями функціональних елементів. 3) Генерація алгоритмічних і псевдовипадкових тестів. 4) Мінімізація довжини тесту шляхом позитивного збільшення його якості. 5) Мінімізація кількості алгоритмічних генераторів шляхом вирішення задачі покриття.

При реалізації програми використовувався компілятор Microsoft Visual C++ 6.0 бібліотеки Objective Grid 7.0 (для візуального зображення даних і результатів у табличному вигляді) і mod.lib (бібліотека опису функцій примітивів). Для автоматичного занесення структури схеми використовується екземпляр класу CScheme, реалізований у бібліотеці ManipSch.lib, що інкапсулює файл формату sch.

Операційна система – Windows 95, 98, NT4.0. Інтегроване середовище проектування – Active-HDL 3.5, 3.6, 4.1, 4.2. Обсяг пам’яті для EXE-модуля – 300 Кбайт. Обсяг вихідного тексту мовою С – більш 300 Кбайт. Використовувані компілятори LCC-Win32 3.1, GCC 2.91.1, компілятор компіляторів PCCTS 1.13MR22. Кількість програмних модулів – 12. Середній час генерації тестів для реальних проєктів (3000 ліній)– 30 с. Час моделювання 100 наборів – 4 с. Інші результати моделювання базової і розробленої системи моделювання несправностей наведені на рис.2.

Рис.2. Порівняльний аналіз результатів моделювання

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

ВИСНОВКИВИСНОВКИ

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

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

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

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

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

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

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

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

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

1. Хак Х.М. Джахирул. Автоматные модели исправного поведения цифровых устройств.– АСУ и приборы автоматики.-– 2001.– Харьков: ХТУРЭ.– Вып. 114.– С. 72-80.

2. Хаханов В.И., Хак Х.М. Джахирул, Масуд М.Д. Мехеди. Модели анализа неисправностей цифровых систем на основе FPGA, CPLD // Технология и конструирование в электронной аппаратуре.–2001.– № 2.– С. 3-11.

3. Хаханов В.И., Ковалев Е.В., Масуд М.Д. Мехеди, Хак ХМ. Джахирул. Кубическое моделирование неисправностей цифровых систем на основе FPGA,CPLD //Радиоэлектроника и информатика. 1999. № 4. С. 64-71.

4. Хаханов В.И., Шкиль А.С., Бедратый Р.В., Хак Джахирул. Метод кубического моделирования неисправностей цифровых схем. АСУ и приборы автоматики.-– 2000.- Харьков: ХТУРЭ.– Вып. 111.– С. 72-84.

5. Хаханов В.И., Рустинов В.А., Горбунов Д.М., Ковалев Е.В., Масуд М.Д. Мехеди, Хак Х.М. Джахирул. Система генерации тестов цифровых проектов в среде Active-HDL // Радиоэлектроника и информатика.– 2000.– №3.– С. 92-101.

6. Рябцев В.Г., Хак Х.М. Джахирул. Особенности системы автоматизированного проектирования радиоэлектронной аппаратуры P-CAD.– Материалы конференции "Автоматика-96".– Симферополь.-– 1996.– С. 112-113.

7. Shkil Alexander, Skvortsova Olga, Masud M.D. Mehedy, Haque H.M. Jahirul.– Test Generation for Digital Device on FPGA, CPLD.– The Experience of Designing and Application of CAD System in Microelectroncs.– Proceeding of the VI-th Conference CADSM 2001.– Lviv – Slavsko.– P. 83-84.

8. Хаханов В.И., Шкиль А.С. Сысенко И.Ю., Хак Х.М. Джахирул. Дистанционное проектирование цифровых систем по технологии hardware-software co-operation. Образование и виртуальность –2000. Сборник научных трудов.– Севастополь.– 2000.– Харьков: ХТУРЭ.– 2000.– С. 169-173.

9. Скворцова О.Б., Пудов В.А., Хак Х.М. Джахирул, Масуд МД. Мехеди. Генерация тестов для последовательностных схем, имеющих триггерные структуры.– IV городская научно-техническая конференция “Актуальные проблемы современной науки в исследованиях молодых ученых Харьковщины”. Харьков: ХГУ.– 2001.– С.87-88.

10. Хак Х.М. Джахирул. Комплекс для проектирования и наладки цифровых устройств с помощью ПЭВМ.– Материалы конференции "Автоматика-97".– Черкасы: ЧИТИ.-– 1997.– С. 81.

АНОТАЦІЯАНОТАЦІЯ

Хак Х.М. Джахірул. Кубічне моделювання несправностей для аналізу якості тестів при проектуванні цифрових систем.– Рукопис.

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

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

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

АННОТАЦИЯАННОТАЦИЯ

Хак Х.М. Джахирул. Кубическое моделирование неисправностей для анализа качества тестов при проектировании цифровых систем.– Рукопись.

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

Цель диссертации – разработка структурно-функциональных моделей цифровых устройств, процедур и алгоритмов кубического анализа неисправностей при генерации тестов для уменьшения временных и материальных затрат, связанных с верификацией цифровых систем на стадии автоматизированного проектирования. В работе решениы задачи:–

модификации автоматной модели синхронного примитива, описанного двухтактным кубическим покрытием, которая позволяет выполнять анализ последовательностных цифровых асинхронных схем для целей моделирования исправного поведения и неисправностей в трех автоматных тактах, что уменьшает число псевдопеременных в модели;–

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

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

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

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

реализации экспериментов на моделях реальных проектов цифровых устройств и тестовых схем из каталогов ведущих фирм в области проектирования, а также из материалов конференций IEEE.–

внедрения теоретических результатов, моделей, алгоритмов и программных средств в учебный и технологический процессы в целях автоматизации проектирования, моделирования и верификации цифровых систем, реализуемых на основе FPGA, CPLD.

Программный продукт Fault simulator предназначен для моделирования ОКН цифровой схемы, описанной на функциональном уровне в виде кубических покрытий. Задачи, решаемые программой: 1) Моделирование ОКН по кубическим покрытиям функциональных элементов. 2) Моделирование дополнений к состоянию линий схемы по кубическим покрытиям функциональных элементов. 3) Генерация алгоритмических и псевдослучайных тестов. 4) Минимизация длины теста путем положительного приращения его качества. 5) Минимизация количества алгоритмических генераторов путем решения задачи покрытия.

При реализации программы использовался компилятор Microsoft Visual C++ 6.0 библиотеки Objective Grid 7.0 (для визуального представления данных и результатов в табличном виде) и mod.lib (библиотека описания функций примитивов). Для автоматического занесения структуры схемы используется экземпляр класса CScheme, реализованный в библиотеке ManipSch.lib, который инкапсулирует файл формата sch.

Операційна система – Windows 95, 98, NT4.0. Інтегроване середовище проектування – Active-HDL 3.5, 3.6, 4.1, 4.2. Обсяг пам’яті для EXE-модуля – 300 Кбайт. Обсяг вихідного тексту мовою С – більш 300 Кбайт. Використовувані компілятори LCC-Win32 3.1, GCC 2.91.1, компілятор компіляторів PCCTS 1.13MR22. Кількість програмних модулів – 12. Середній час генерації тестів для реальних об,єктов (3000 линий)– 30 с. Время моделювання 100 наборов 4 с.

Альфа-версия программмы моделирования неисправностей протестирована на 120 реальных схемах из списков конференций ISCAS, что подтвердило состоятельность алгоритма кубического моделирования и его приемлемое быстродействие.

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

ABSTRACTABSTRACT

Haque H.M. Jahirul. Cubic Fault Simulation for Fault Coverage Test Analisys on Digital System Design. – Manuscript.

Thesis for a candidate degree of technical sciences on speciality 05.13.12 – computer-aided design systems.– Kharkov state technical university of radio electronics, Kharkov, 2001.

The thesis is devoted to the development structural-functional models of digital devices, procedures and algorithms of cubic analysis of faults during test generation for decreasing time and material expenses, related to verification of digitals systems for computer-aided designing. During the period of research following problems were solved: modification of finite-state model of synchronous primitive, descripted by two-state cubic covering, which allows to analyze sequential digital asynchronous circuits on three automata frames, which decrease number of pseudo-variables; creation of cubic algorithm of deductive fault simulation on basis of analysis cubic coverings of primitives; development of program complex of fault simulation, that allows to define tests fault coverage, that generated for digital systems on chip.

Key words: Fault Simulation, Digital System, Cubic Covering, Fault Free Modeling.