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

ДОНЕЦКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

ИВАНОВ ДМИТРИЙ ЕВГЕНЬЕВИЧ

;Тб 0.1

^ УДК681.518:681.326.7

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

Специальность 05.13.13 - "Вычислительные машины, системы и сети"

АВТОРЕФЕРАТ диссертации на соискание учёной степени кандидата технических наук

Донецк-2000

Диссертацией является рукопись.

Работа выполнена в Институте прикладной математики и механики HAH Украины, г. Донецк.

Научный руководитель: д.т.н., доцент

Скобцов Юрий Александрович,

зав. отделом теории управляющих систем, Институт прикладной математики и механики HAH Украины, г.Донецк.

Официальные оппоненты: д.т.н., профессор

Баркалов Александр Александрович,

зав. кафедрой международной экономики, Донецкий государственный технический университет;

к.т.н., доцент

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

Ведущая организация: Харьковский государственный технический

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

Защита состоится « 27 » июня 2000г. в 14 час. на заседании специализированного учёного совета К.11.052.03 в Донецком государственном техническом университете по адресу: 83000, г. Донецк, ул. Артёма, 58, уч. корпус 1, ауд. 201.

С диссертацией можно ознакомиться в библиотеке Донецкого государственного технического университета по адресу: 83000, г. Донецк, ул. Артёма, 58, уч. корпус 2.

Автореферат разослан « » jlсйД 2000 г.

Учёный секретарь специализированного учёного совета К11.052.03, кандидат технических наук, доцент

Г.В. Мокрый

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

В настоящее время существует ряд эффективных алгоритмов моделирования и генерации тестов для комбинационных схем. Однако в связи с резким скачком сложности проектируемых цифровых устройств (ЦУ) применение уже существующих подходов существенно увеличивает стоимость процесса диагностирования, требуя чрезмерных затрат временных ресурсов и памяти. Задача разработки алгоритмов моделирования и построения тестов для последователь-ностных схем исследована значительно хуже вследствие неопределённости начального состояния и явления состязаний сигналов. В настоящее время не существует эффективных методов генерации тестов для сложных цифровых схем с памятью.

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

Связь работы с научными программами, планами, темами. Тема данной диссертационной работы, а также её результаты связаны с выполнением НИР №0194и022560 «Разработка основ теории и прикладного программного обеспечения идентификации дискретных систем», НИР №0199и001612 «Исследование актуальных проблем моделирования, управления и идентификации дискретных систем», а также комплексной программой HAH Украины "Техническая диагностика и неразрушающий контроль" пункт "Система автоматического моделирования и диагностирования (АСМИД) дискретных устройств".

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

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

вания; применении генетических алгоритмов (ГА) совместно с многозначным моделированием для построения тестовых наборов больших схем.

Задачи работы. Для достижения указанной цели решаются следующие задачи:

1) разработка событийного алгоритма параллельного логического моделирования неисправных комбинационных и последовательностных ЦУ с высокой степенью адекватности;

2) разработка алгоритма событийного моделирования последовательностных ЦУ с функциональными неисправностями;

3) разработка методов повышения быстродействия алгоритмов моделирования ЦУ с неисправностями;

4) разработка алгоритма генерации тестов для сложных последовательностных ЦУ с высокой полнотой получаемых тестовых наборов.

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

Практическое значение полученных в диссертационной работе результатов состоит в разработке и программной реализации новых алгоритмов моделирования исправных и неисправных ЦУ и генерации тестов ЦУ в виде автоматизированной системы моделирования и диагностики АСМИД-Е. Разработанная система позволяет повысить качество генерируемых тестовых наборов, адекватность процесса моделирования, уменьшить затраты памяти и времени. Апробация системы проводилась на схемах из каталогов 18СА8-85 и 18СА8-89, на которых по международным стандартам принято проверять эффективность новых программ моделирования и генерации тестов. По результатам машинных экспериментов на контрольных схемах временные характеристики в среднем улучшены на 45-50%.

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

На защиту выносятся:

1) Алгоритм событийного параллельного по неисправностям моделирования неисправных комбинационных и синхронных последовательностных схем, который для повышения адекватности процесса моделирования использует 16-значную логическую систему.

2) Алгоритм параллельного моделирования неисправных синхронных последовательностных ЦУ, использующий функциональную модель неисправности одиночного перехода конечных автоматов, что позволяет соединить преимущества структурных и функциональных подходов в моделировании ЦУ.

3) Методы повышения быстродействия за счёт статической и динамической сортировки списка неисправностей для стратегии параллельного моделирования, совмещённого с одиночным распространением неисправностей.

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

Обоснованность и достоверность полученных в диссертационной работе результатов подтверждается корректным использованием математического аппарата теории булевых функций, конечных автоматов, переключательных схем; проведёнными машинными экспериментами, показывающими, что применение предложенных методов ускорения процесса моделирования существенно повышает его скорость; практическим использованием разработанной системы моделирования и генерации тестов АСМИД-Е на производстве в ОАО «Авто-матгормаш» при проектировании и диагностировании схем шахтной автоматики.

Апробация работы. Основные научные результаты работы докладывались и обсуждались на:

- XIV Международной межвузовской школе-семинаре «Методы и средства технической диагностики», Ивано-Франковск, 1997;

- Международной конференции «Математика в индустрии», Таганрог, 1998;

- 1-й Международной конференции «Современные технологии ресурсо-энергосбережения», Партенид, 1997;

- областных семинарах «Актуальные проблемы компьютерных наук», Донецк;

- семинарах отдела теории управляющих систем Института прикладной математики и механики HAH Украины.

Публикации. По теме диссертационной работы опубликовано 8 печатных работ: 5 статей в научных изданиях, 3 статьи в трудах международных конференций.

Реализация результатов работы. Разработанная система АСМИД-Е использовалась при проектировании и диагностировании цифровых схем шахтной автоматики в АО «Автоматгормаш» (г. Донецк), а также в учебном процессе при проведении лекций и лабораторных занятий в курсе «Основы автоматизации и проектирования средств вычислительной техники» кафедры автоматизированных систем управления Донецкого государственного технического университета.

Структура и объём работы. Диссертационная работа на 151 странице состоит из введения, 5 разделов, выводов и содержит 26 рисунков, 23 таблицы, список использованных источников из 127 наименований.

ОСНОВНОЕ СОДЕРЖАНИЕ Во введении обоснована актуальность темы, сформулированы цель и задачи исследования, изложены основные научные и практические результаты, полученные в работе, сведения об апробации работы, а также основные положения, которые выносятся на защиту.

Раздел 1 содержит три подраздела. В первом проведён обзор основных математических моделей ЦУ и многозначных алфавитов, используемых в логиче-

ском моделировании. Во втором подразделе проведён анализ точных методов моделирования ЦУ с неисправностями: параллельного, дедуктивного и конкурентного, а также некоторых приближённых методов. В третьем подразделе проводится анализ методов построения проверяющих тестов для ЦУ на структурном и автоматном уровнях. Методы структурного уровня делятся на три основные группы: методы, основанные на псевдослучайной генерации с последующей модификацией полученных наборов, детерминированные структурные методы и методы, основанные на моделировании.

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

В разделе 2 разработаны алгоритмы моделирования ЦУ с неисправностями в многозначных алфавитах, использующие стратегию параллельного по неисправностям моделирования.

Одним из основных критериев эффективности процесса логического моделирования ЦУ является адекватность, т.е. степень соответствия результатов моделирования реальному поведению ЦУ. Повышение адекватности процесса моделирования достигается за счёт применения многозначной логики. В качестве базовой математической модели сигналов во всех разработанных методах используется универсальный 1б-значный алфавит 516 = (0,1, £>, G\,D',Fl,D*,Dl,0,C,FQ,H,GO,E,DO,u) и его подмножества. Алфавит В16 является множеством всех подмножеств алфавита В\ --{0,D',D,\}. Существенным моментом является кодирование элементов алфавита и построение на его основе многозначных функций. Для этого используются четыре характеристические переменные кодирования х", х0', х°, х!, с помощью которых символы алфавита В16 кодируются следующим образом: 0 = {ОООО}, 1 = {0001}, D = {0010}, Gl = {0011}, Z)'={0100}, Fl = {0101}, £>'={0110}, ¿51 = {Oil 1}, 0 = {1000}, C = {1001}, F0 = {1010}, Я = {1011}, GO = {1100}, £ = {1101}, DO = {1110}, к = {1111}. Тогда, поведение многозначной функции задаётся с помощью четырёх характеристических булевых функций: f\x°,xD' ,xD ,*'), /c'(x°,*D>D,*1), fD(x\xD\xD ,х>), /'xD',x°,x'). Для основных логических вентилей они имеют вид: / = я-6:

/о =aVvaD'iD vaDbD' ,fD =aD'bl va]bD' vaV,/° ra^'vaVvaV,/1 =a'i'; f = avb:

f =aV,/D' = a"V va'b0' vaD'bD',fD =aDb° v a°bD v aDbD,/' =aV vaD'bD vaDbD'; / = a:

f" =a1,/0' =aD ,fD =a°.

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

Логическое моделирование ЦУ представляет итеративный процесс моделирования отдельных элементов. Он состоит из подачи на внешние входы модели ЦУ входных воздействий и последовательного, от входов к выходам схемы, вычисления значений выходов логических элементов и получении таким образом выходной реакции.

Моделирование работы синхронной последовательностной схемы выполняется её преобразованием в комбинационный эквивалент путём обрыва обратных связей (на рис.1 -места обрыва отмечены *). Таким образом моделируется один такт работы схемы. Для моделирования нескольких тактов работы производится разворачивание комбинационных эквивалентов в комбинационную итеративную схему (рис.2).

Рис.1 Пример последовательностной схемы.

*2ДХи

*гл 41 ,

*гг »и , , *а*ч

{Ъ

адтао

2п-

СИ

Цо™ У

Рис.2 Разворачивание комбинационных эквивалентов в итеративную комбинационную схему.

В данном разделе разработано два алгоритма моделирования ЦУ с неисправностями. Первый алгоритм для повышения адекватности процесса моделирования использует универсальный 16-значный алфавит В,6, а для повышения быстродействия - параллельное по разрядам машинного слова моделирование. При этом каждой линии схемы соответствует четыре машинных слова х°, х1, а каждая неисправная схема моделируется в отдельном разряде машинного слова. Множество неисправностей разбивается на группы по 32 неисправности в соответствии с разрядностью инструментальной ЭВМ. Таким образом за один проход моделируется 32 неисправности. При моделировании ЦУ с неисправностями необходима разработка методов внесения влияния неисправно-

стей в 16-значном алфавите. Если неисправность моделируется в .¡-м разряде машинного слова, то для внесения влияния неисправности сопвЮ для данного способа кодирования алфавита Ви необходимо реализовать следующие операции:

х°=х°&М0[)], х°=хс ух°&М1[]], хо=х°&М0Ш, х'^х'ух^М! [¡] и для неисправности сопбИ :

х0=х°ух°'&М1[)], х°=хп&М0[]]> хР^яРух'&ШШ, х^х^МОЦ]

(1)

(2)

где М0(М1) - массив 0(1)-масок, содержащий 1(0) во всех позициях, кроме >й.

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

Второй алгоритм также использует параллельное моделирование и в нём впервые применяется функциональная модель неисправности одиночного перехода конечного автомата. Такой неисправности соответствует переброска дуги графа переходов автомата, реализуемого исправной схемой, из одного состояния в другое (как показано на рис.3). Она задаётся тройкой: (э^ х£, б м), где ^ - начальное состояние перехода, XI -вход, активизирующий неисправный переход, б1+1 - конечное состояние неисправного перехода. Всевозможные двоичные наборы на линиях обратных связей в последовательностной

схеме соответствуют множеству Б состояний автомата.

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

В разделе 3 разработан эффективный алгоритм моделирования ЦУ с неисправностями, использующий стратегию параллельного по неисправностям моделирования со сжатием списка неисправностей. Его отличие от алгоритма, предложенного в разделе 2, заключается в следующем. В алгоритме раздела 2 после формирования группы неисправностей производится их моделирование на всех входных наборах независимо от проверяемости. Если при этом некоторая неисправность / проверяется на к -ом наборе, то дальнейшее моделирова-

а) исправный автомат б) неисправный автомат Рис.3 Неисправность одиночного перехода.

ние для неё производится вхолостую. Алгоритм параллельного по неисправностям моделирования с сжатием списка неисправностей использует другую стратегию. После ввода очередного тестового вектора производится моделирование на нём всех непроверенных на данный момент неисправностей. Если данный входной вектор обнаруживает какую либо неисправность /, то она удаляется из списка и не вносится на моделирование на следующих входных наборах. Такая стратегия называется параллельным по неисправностям моделированием, совмещённым с одиночным распространением неисправностей.

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

Предлагаемый метод статической сортировки неисправностей основан на предположении, что все неисправности одно-выходной подсхемы без разветвлений оказывают влияние на значения сигналов вне подсхемы через её выход. Поэтому желательно такие неисправности включать при моделировании в одну группу. Однако при используемых ранее методах сортировки это условие не выполняется. Новый метод статической сортировки заключается в следующем: 1) схема разбивается на одно-выходные подсхемы, не содержащие разветвлений (как показано на рис.4), и создаётся список их выходов; 2) список выходов этих подсхем сортируется методом «от внешних выходов в глубину»; 3) затем в отсортированный список вместо выходов подсхем подставляются полные их списки неисправностей. Такой подход позволяет включать неисправности одно-выходных подсхем, в присутствии которых возникают одинаковые события, в одну группу и сократить число событий процесса моделирования.

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

Рис.4 Выделение максимальных одно-выхолных подсхем.

группа А

разделитель | группа Б

ч ... \

Рис.5 Динамическая сортировка неисппавностей.

ности) следует отделить от остальных. Предлагается использовать два вида динамической сортировки. В первом методе активные неисправности смещаются в конец списка (как показано на рис.5). Таким образом, активные неисправности образуют компактную группу Б, что ведёт к существенному уменьшению числа событий. При этом активными считаются условно-проверяемые неисправности, дающие неопределённое значение сигнала и е й16 на каком-либо внешнем выходе схемы. Во втором методе высокоактивные неисправности предлагается моделировать параллельно с исправной схемой до входа в основной цикл по неисправностям. На основании машинных экспериментов предложен эвристический критерий высокой активности неисправности: неисправность считается высокоактивной, если в её присутствии значения сигналов в исправной и неисправной схемах отличаются более чем на 5% триггеров.

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

Машинные эксперименты, проведённые с программной реализацией алгоритма и методами повышения быстродействия за счёт сортировок и метода внесения влияния неисправностей, показывают уменьшение времени моделирования и числа событий на 45-50%, причём для больших схем эти преимущества проявляются сильнее.

В разделе 4 предложен алгоритм построения проверяющих тестов для синхронных последовательностных ЦУ, основанный на генетическом алгоритме. Недостатком существующих структурных методов построения тестов является то, что они дают практически неприемлемые результаты при работе с

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

Генетические алгоритмы - современная математическая модель адаптивных методов поиска, которая в последнее время часто используется для решения комбинаторных задач. Термин «генетический алгоритм» применяют для обозначения любой основанной на популяциях математической модели, которая использует операции селекции и рекомбинации для построения новой выборки точек в пространстве поиска. Его суть заключается в попытке повторить природный путь улучшения характеристик живых организмов.

Решение комбинаторной задачи с помощью ГА предполагает, что любая точка в пространстве решений задачи может быть закодирована двоичным вектором х, называемым особью. Произвольный набор особей называется популяцией. Близость точки х к оптимальному решению вычисляется с помощью оценочной функции /(х). Процесс поиска решения сводится к итеративному построению новой популяции из текущей. На основании вычисленных оценок всех особей популяции принимается решение о выживании особей (переходе их в следующее поколение). Дополнительно к лучшим особям применяются трансформирующие операции: скрещивание - обмен битами в особях с порождением новых особей (рис.6); мутация - случайное изменение битов в особях. Цель операции скрещивания - передать особям-потомкам лучшие черты особей-родителей, а операции мутации - ввести в рассмотрение новые особи. Таким образом производится более широкий перебор вариантов в пространстве поиска и предотвращается схождение процесса к локальным максимумам.

При генерации тестов предлагается в качестве особи выбирать одиночную тестовую последовательность, которая состоит из входных векторов. Длина последовательности заранее не ограничена и не известна (рис.7а). Популяция представляет собой набор из и произвольных особей (рис.7б).

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

а) одноместное

Рис.6 Операции скрещивания.

б) двухместное

последовательность какую либо неисправность /. Если да, то эта неисправность / выбирается в качестве целевой для фазы 2 алгоритма.

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

Для построения новой популяции необходимо оценить каждую особь. Вычисление оценочных функций особей популяции базируется на моделировании ЦУ с неисправностями и основано на предположении, что чем выше активность заданной неисправности / в схеме (число рассогласований значений сигнэлое в исправной и неисправной схемах), тем больше вероятность достижения этими рассогласованиями внешних выходов.

После моделирования очередного входного вектора вычисляется его оценочная функция:

= ХгЫ) (3)

где: V - текущий входной набор; / - неисправность; с„оря - константа нормирования, равная отношению числа вентилей схемы к числу триггеров; ■ взвешенное число линий с различными значениями сигналов в исправной и неисправной схемах; g2(v,f) - взвешенное число триггеров с различными значениями сигналов в исправной и неисправной схемах. В качестве веса используется наблюдаемость элементов схемы.

Оценочная функция всей входной последовательности имеет следующий

вид:

входы

моменты времени

1 1 0 1 0

0 1 1 0 1

0 1 0 1 0

1 0 0 0

0 1 1 0 1

1 1 0 1 0

\ вектор

5И loionmi 1

/ In 0 1 ol 1 0 0 1 0 1 1 0

0 OHIO 1 0 0 1 0 1

0 0 1 0 1 0

1 0 1 0 0 0

1 1 0 1 0 1

0 1 1 0 1 0

1 0 0 0 1 t

0 1 1 0 1 ■]

1 1 0 1 0

а) особь б) популяция

Рис.7 Особи и популяции в генетическом алгоритме.

£(*,/)= 1С'*ф„/) (4)

1=1

где ^ - заданная последовательность, / - неисправность, V - 1-й вектор последовательности х, 0<С<1 - предварительно заданная константа, благодаря которой предпочтение отдаётся более коротким последовательностям. Для эффективного вычисления оценочных функций особей популяции предложен новый алгоритм параллельного по тестовым наборам моделирования. Суть его заключается в том, что в каждом разряде машинного слова моделируется одна и та же целевая неисправность /, но тестовые последовательности, подаваемые на каждый разряд, различны, и соответствуют особям популяции. Таким образом за один проход моделирования производится вычисление оценочных функций сразу для всех особей популяции.

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

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

1-й потомок

а) горизонтальное б)вертикальное

Рис.8 Операции горизонтального и вертикального скрещивания.

После этого к новым особям применяется один из трёх видов мутации:

- удаление вектора из случайной позиции (если данный вектор был несущественным, то оценка последовательности не должна уменьшиться);

- добавление вектора в случайную позицию, что позволяет вводить и рассматривать последовательности с большей длиной;

- мутация битов (любой бит в последовательности может изменить своё значение с вероятностью 0.005).

В фазе 3 алгоритма для построенной последовательности производится проверка обнаружения оставшихся неисправностей (кроме целевой). Это осуществляется с помощью алгоритма параллельного по неисправностям моделирования со сжатием списка неисправностей (раздел 3). Все обнаруженные неисправности удаляются из списка.

Эта итерация (фазы 1-3) повторяется до тех пор, пока не будет достигнута желаемая полнота теста, либо будет достигнуто заранее установленное число итераций Мтах.

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

В разделе 5 описана новая версия автоматизированной системы моделирования и диагностики цифровых схем АСМИД-Е. Все предложенные методы реализованы программно и позволяют существенно сократить время моделирования и построения тестов для цифровых схем. На их основе в Институте прикладной математики и механики НАН Украины разработана новая версия данной системы. Она предназначена для моделирования, контроля и диагностирования цифровых устройств, которые могут содержать как комбинационные элементы, так и элементы с памятью. Количество элементов и глобальных обратных связей в моделируемых схемах не ограничивается. Также предусмотрена возможность обработки схем, построенных с применением различных схемотехнических решений: монтажная логика, схемы с тристабильными элементами и т.д.

Рассматриваемая система может быть использована при автоматизированном контроле и диагностировании ЦУ на всех этапах "жизненного цикла": при проектировании, изготовлении, вводе в эксплуатацию, входном контроле и сопровождении. Она выполняет следующие функции:

- графический или текстовый ввод описания моделируемого устройства;

- синтаксический анализ описания, необходимый для выявления ошибок подготовки данных;

- трансляция описания ЦУ во внутреннюю структуру данных;

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

- генерация проверяющих тестов;

- логическое моделирование неисправных ЦУ с целью анализа полноты тестовых наборов и определения списка непроверяемых неисправностей.

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

ЗАКЛЮЧЕНИЕ

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

Основные научные и практические результаты заключаются в следующем:

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

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

3. Для стратегии параллельного моделирования, совмещённого с одиночным распространением неисправностей, предложены новые методы статической и динамической сортировки неисправностей, за счёт чего достигается существенное уменьшение времени моделирования.

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

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

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

7. Все предложенные методы реализованы программно и вошли в новую вер сию автоматизированной системы моделирования и генерации тесто] АСМИД-Е, предназначенной для контроля качества цифровых схем на все: этапах жизненного цикла: проектировании, производстве и сопровождения.

ПУБЛИКАЦИИ АВТОРА

1. Иванов Д.Е., Скобцов Ю.А Параллельное моделирование функциональны: неисправностей // Техническая диагностика и неразрушающий контроль. -1998. -№3.-С.43-47.

2. Иванов Д.Е. Параллельное моделирование функциональных неисправностей одного перехода II Труды института прикладной математики и механик! HAH Украины. - т2. - Донецк, ИПММ. - 1998. - С.72-78.

3. Иванов Д.Е., Скобцов Ю.А. Параллельное моделирование константных i функциональных неисправностей в многозначных алфавитах // Сборищ трудов межвузовской школы-семинара «Методы и средства технической ди агностики». - Киев. - 1999. - С.69-73.

4. Иванов Д.Е., Скобцов Ю.А. Параллельное моделирование неисправносте! для последовательностных схем // Искусственный интеллект. - 1999. - №1. -С.44-50.

5. Иванов Д.Е., Скобцов Ю.А. Система моделирования и генерации тесто! цифровых схем // HayKOBi пращ Донецького державного техшчногс ушверситету, сер1я "Обчислювальна техшка та автоматизащя», випуск 12. -Донецьк. - 1999. - С.143-150.

6. Иванов Д.Е., Скобцов Ю.А. Генерация тестов цифровых устройств с исполь зованием генетических алгоритмов // Труды института прикладной матема тики и механики HAH Украины. - Т.4. - Донецк, ИПММ. - 1999. - С.82-88.

7. Иванов Д.Е., Садымак Р.И., Скобцов Ю.А. Генерация проверяющих тестов i моделирование одиночных неисправностей переходов // Труды 1-й между народной конференции «Современные технологии ресурсо-энергосбережения», книга 2. - Киев. - 1997. - С.111-113.

8. Иванов Д.Е., Садымак Р.И. Параллельное моделирование и тестирован!« функциональных неисправностей 11 Труды международной конференцит «Математика в индустрии». - Таганрог. - 1998. - С.151-153.

Личный вклад соискателя. В совместных работах автору принадлежат [1-2,7-8] - алгоритм параллельного моделирования функциональных неисправностей одиночного перехода на структурном уровне, методы представления таких неисправностей и методы внесения их влияния; [3] - алгоритм параллель ного моделирования неисправных ЦУ в многозначных алфавитах; методь представления и внесения влияния константных неисправностей в 16-значно\ алфавите; [4] - методы уменьшения числа событий при моделировании: статическая и динамическая сортировка списка неисправностей; метод функционального внесения влияния неисправностей; [5] - новая программная реализа ция автоматизированной системы моделирования и генерации тестов АСМИД-

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

АНОТАЦ1Я

Гванов Дмитро евгеншович. Розробка метод1в моделювання \ тестування пошкоджених цифрових пристрохв у багатозначних алфавггах,- Рукопис.

Дисертац1я на здобуття наукового ступеня кандидата техшчних наук за спещальшстто 05.13.13 - "Обчислювальш машини, системи та мережГ'.-Донецький державний техтчний ушверситет, Донецьк, 2000.

Дисертацш присвячено задачам розробки метод1в моделювання 1 тестування цифрових пристрош. Запропоновано ефективш метода моделювання константних i функцюнальних пошкоджень, в яких для шдвищення адекватное« використовуеться ушверсальна 16-значна лопка, а для шдвищення швидкосл - паралельне за пошкодженнями моделювання. Для стратеги паралельного моделювання, сумщеного ¡з одиночним розповсюдженням пошкоджень, запропоновано нов1 метода шдвищення швидкосп: зменшення числа подш за рахунок статичного та динам1чного сортування, новий структурний функцюнальшй споЫб внесения ди пошкоджень. Розроблено алгоритм побудови тестових послщовностей, який базуеться на генетичному алгоритм!, що дозволяв будувати тести прийнятно! якосп для великих схем. Запропоноваш алгоритми реатзоваш програмно 1 впроваджет в автоматизовану систему моделювання \ д1агностики АСМ1Д-Е, яка використовувалася при проектуванш реальних цифрових пристрош. Ключов1 слова: цифровий пристрш, пошкодження, лопчне моделювання, генетичний алгоритм, генеращя теспв.

АННОТАЦИЯ

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

Диссертация на соискание учёной степени кандидата технических наук по специальности 05.13.13 - "Вычислительные машины, системы и сети".-Донецкий государственный технический университет, Донецк, 2000.

На основе теоретических и экспериментальных исследований в диссертационной работе предложено новое решение актуальных задач

моделирования с неисправностями и построения проверяющих тестов ЦУ являющихся центральными в технической диагностике.

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

В работе решены следующие задачи:

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

2. Впервые предложен алгоритм параллельного моделирования неисправных синхронных последовательностных ЦУ, использующий функциональнук модель неисправности одиночного перехода конечных автоматов, что позволяет соединить преимущества структурных и функциональных подходов в моделировании ЦУ.

3. Для стратегии параллельного моделирования, совмещённого с одиночным распространением неисправностей, разработаны новые методы повышени; быстродействия: статическая и динамическая сортировка списка неисправностей, структурный функциональный метод внесения неисправностей.

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

Практическое значение работы состоит в том, что все предложенные в ра боте алгоритмы и методы реализованы программно в виде автоматизированное системы моделирования и диагностирования АСМИД-Е. Данная система по зволяет повысить качество генерируемых тестовых наборов, адекватность процесса моделирования, уменьшить затраты памяти и времени. Апробация системы проводилась на схемах из международных каталогов 1БСА8-85 и 18СА8-89 на которых по международным стандартам принято проверять эффективносп новых программ моделирования и генерации тестов. По результатам машинны> экспериментов на контрольных схемах временные характеристики за счёт при менения новых методов в среднем улучшены на 45-50%. Ключевые слова: цифровое устройство, неисправность, логическое моделиро вание, генетический алгоритм, генерация проверяющих тестов.

ANNOTATION

Ivanov D.E. The development of the fault simulation and test generation methods of the digital circuits in multivalued alphabets.- Manuscript.

Thesis on reception of a scientific degree of the candidate of the technical sciences on speciality 05.13.13 - "Computers, systems and networks".- Donetsk state technical university, Donetsk, 2000.

The dissertation is devoted to the problem of the development of the fault simulation and test generation methods of the digital devices. An effective methods of stuck-at and functional faults simulation are proposed, that used parallel fault simulation for the speed up of the simulation and 16-valued logic for the rise of the adequacy. For parallel fault simulation combined with single fault propagation it is proposed the new speed-up methods: static and dynamic fault ordering, new structural functional fault injection method. An algorithm of test generation is developed, that based on the genetic approach. It allows to build test sets for circuits of large scale integration with appropriate fault coverage. The program implementation of the proposed algorithms are incorporated in automatic simulation and test generation system ASMID-E, which used for the development of the real digital devices.

Key words: digital device, fault, logic simulation, genetic algorithm, test generation.