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

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

*' ; О --------------------------------------------------

/ Г) -»л«"; л

СКОБЦОВ ВАДИМ ЮРЬЕВИЧ

УДК 681.518:681.326.7

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

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

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

Донецк-1998г.

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

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

Научный руководитель - д. ф. -м. н,, старший научный сотрудник, Барапгко Анатолий Сергеевич,

Институт прикладной математики и механики HAH Украины, ведущий научный сотрудник. Официальные оппоненты: д.т.н., профессор,

Баркалов Александр Александрович, Донецкий государственный технический университет, профессор кафедры "Электронные вычислительные машины"; х.т.н., старший научный сотрудник, Андрюхин Александр Иванович,

Донецкий государственный институт искусственного интеллекта, проректор по научной работе.

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

Защита состоится _1998 г, в час, на заседании

специализированного ученого совета К. 11.052.03 в Донецком государственном

техническом университете по адресу:

340000, г.Донецк, ул.Артема, 58, уч. корп, 1, ауд. 201.

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

Автореферат разослан -Л- ¿г _1998 г.

Ученый секретарь

специализированного ученого совета, кандидат технических наук, доцент

Г.В.Мокрый

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

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

Исследованиям проблем диагностики и проектирования отказоустойчивых цифровых устройств (ЦУ) посвящены проводящиеся регулярно международные симпозиумы, конференции и школы-семииары: Всемирная конференция по тестированию (IEEE Test Conference), Европейская конференция по тестированию (Euro Test Conference) и др., межгосударственные (по странам СНГ) совещания в школы-семинары по технической диагностике ЦУ. Все это красноречиво говорит о чрезвычайной актуальности исследования проблем диагностики цифровых схем.

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

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

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

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

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

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

Цель и задачи исследования.

Целью работы является повышение эффективности автоматического диагностирования логических схем.

Основные задачи. Для достижения цели решаются следующие задачи:

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

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

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

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

Научная новизна полученных результатов заключается в следующем: 1) Разработан метод построения проверяющих тестов для комбинационных ЦУ, обладающий существенно улучшенными показателями быстродействия и полноты постро-

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

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

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

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

5) Предложен метод генерации тестов для последовательностных цифровых схем на основе предложенного символьного моделирования с неисправностями. Метод реализует возможности точных автоматных методов построения тестов на структурном уровне.

Практическая пенность результатов, полученных в диссертационной работе, состоит в разработке и программной реализации новых эффективных методов и алгоритмов построения тестов для комбинационных и последовательностных дискретных устройств. Эти методы позволяют увеличить полноту получаемых тестов на 20%, существенно сократил» их длину и сократить временные затраты на 30%.

Программные модули, полученные в результате реализации разработанных методов, обладают высокими эксплуатационными характеристиками: широкой областью применения, высокой производительностью. Они интегрированы в систему моделирования и диагностирования ЦУ АСМИД-П и апробированы при генерации тестов реальных цифровых схем международного каталога ISCAS85, ISCAS89, на которых принято по международных! стандартам проверять новые методы диагностики логических схем. Система АСМИД-П использовалась при проектировании и диагностировании цифровых схем шахтной автоматики в ОАО Автоматгормаш (г.Донецк).

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

Личиый вклад соискателя. В совместных работах "Система логического моделирования и генерации тестов на персональных компьютерах АСМИД-П" (в материалах XII Международной межвузовской школы-семинара "Методы и средства технической диагностики", 1995) и "Система логического моделирования и генерации тестов АСМИД-П" (в журнале "Управляющие системы и машины", 1996, №1,2) автором разработаны методы логического моделирования исправных и неисправных комбинационных логических схем с использованием 16-значного алфавита, детерминированный структурный метод построения проверяющих тестов в 16-значном алфавите для комбинационных цифровых устройств.

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

- XII МЬкяародтй м^жвуйвськш школ-ceMiHapi "Мсгоди i засоби техшчно! доагностики", 1вано-Фратавськ, 1995;

- 9th Conférence of the Européen Consortium for Malhcmatics in Idustry, Technical University of Denmark, Copenhagen, Denmark, 1996;

- XIII Международной межвузовской школе-семинаре "Методы и средства технической диагностики", Йошкар-Ола, 1996;

- 3-й Украшсысш конференцп з автоматичного херування "АВТОМАТИКА 96", Севастополь, 1996;

- 5th Biennial Baltic Electronics Conférence, Tallinn, Estonia, 1996;

- Международной конференции "Моделирование н исследование устойчивости систем", Киев, 1997;

- XIV Миснародшй мжвузшсьюй шкош-семшар1 "Метода i засоби техшчжи fliaraocnmi'S Гвано-Франивськ, 1997;

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

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

Структура и объем работы. Диссертационная работа на 142 страницах состоит и» введения, 4 разделов, выводов, изложенных на 133 страницах, содержит 22 рисунка, 14 таблиц, список использованных источников из 106 наименований на 9 страницах.

ОСНОВНОЕ СОДЕРЖАНИЕ

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

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

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

Практически все методы генерации тестов и логического моделирования основаны на использовании многозначных алфавитов. В основе математической модели, используемой нами во всех разработанных методах, лежит универсальный 16-значный алфавит Bi6={0,l,D,Gl,D\Fl,D*,Dl,O,C,FO,H,GO,E,DO,u}, являющийся множеством всех подмножеств базового алфавита B4={0,D',D,1}. Важным моментом при определе-

нии многозначной логики является способ кодирования элементов алфавита. Символы алфавита Bie кодируются при помощи четырех двоичных характеристических переменных х°, xD', xD, х': 0={0}(х°=О, xD'=0, xD-0, х'=0), 1={1}(0001), D={D}<0010), Gl={Dul}(0011), D'={D'}(0100), Fl={D'ul}(0101), D*={D'uD}(0110), Dl={D'uDul} (Olli), 0={0}(1000), C={0ul}(1001), F0={0uD}(101ö), Н={(ЫХЛ}(1011), G0= {OuD»} (1100), E=i0uD'ol}(1101), DO={OuD'uD}(1110), U={0uD'UIXJ1}(1111).

В работе применяется покомпонентный способ задания многозначных функций. Поведение логической многозначной функции f(X)=f(xi,X2,...,Xi^ описывается четырьмя булевыми характеристическими функциями f°(X°,XD ,Х°,Х'), fD (X°,XD .Х^.Х1), fD(X°,XD',XD,X1), f!(X0,XD',XDsX1). В Табл.1 представлены характеристические функции для базисных вентилей И,ИЛИ,НЕ.

Таблица 1 Характеристические функции для венгалсй И,ИЛИ,НЕ

f f p- P i»

ab a^vbOva^v аЕЪ! v a'b0' v aDb'va'bDv a'b1

aDbD' aDW aDbD

avb a°b° а°Ъ° va°bD'v a^b» v a°b° v a!vb'val>V>v

aD'bD' aDb° aDbD'

а a1 aD aD" a>

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

Во втором разделе разработаны методы генерации проверяющих тестов и логического моделирования для комбинационных логических схем.

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

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

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

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

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

ров в тесте, время генерации и т.п.). Для этих целей впервые разработан структурный детерминированный метод построения тестов, основанный на активизации путей в универсальном 16-значном алфавите. В начале процесса генерации теста предполагается, что на каждой линии устройства возможны любые комбинации значений сигналов исправного и неисправного ДУ. Поэтому на всех линиях схемы устанавливается неопределенное значение и. Затем, исходя из знания местоположения данной неисправности и структуры схемы, исключают ненужные или невозможные комбинации сигналов на линиях ДУ. Для этого применяется структурная импликация, которая использует только знание топологии схемы. Кроме этого используются свойства логических элементов с помощью процедур логической импликации. Для снятия неопределенности на выходах вентиля используют прямую логическую импликацию. Неопределенность на входах элемента сокращается при помощи обратной логической импликации. Процедура логической импликации выполняется после структурной импликации и в процессе генерации теста, когда надо снять неопределенность в результате выбора некоторого варианта в дереве решений. На рисунке 1 представлена схема с результатами генерации теста в алфавите В)«.

Рис.1

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

и моделирования с неисправностями для последоватеяьностных цифровых схем.

Как правило, в существующих структурных методах построения тестов и моделирования с неисправностями для последовательностных устройств используется одиночная стратегия наблюдения выходных реакций. При се применении в случае обнаруживаемое™ неисправности все пары начальных состояний должны различаться в один момент времени на одном внешнем выходе. При таком подходе некоторые неисправности могут быть объявлены нетестируемыми, в то время как они проверяются методами, основанными на использовании альтернативной стратегии кратного наблюдения. При ее применении дапная неисправность считается обнаруживаемой входной последовательностью, если для каждой пары начальных состояний исправного и неисправного ДУ существует некоторый момент времени г, в который на некотором внешнем выходе г реакции исправного и неисправного ДУ отличаются. Суть данной стратегии заключается в том, что различные пары начальных состояний исправной и неисправной схем могут различаться в различные моменты времена на разных внешних выходах.

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

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

метод на базе применения стратегии кратного наблюдения, введенных комбинированных характеристических переменных

х01 = = еВ16 Ох01=1еВ2, х" = х°' V*1:* = П еВ^ о хР1 = 1 еВ2,

х00 = х°' ух°:х = 00 еВ1б ох°° - 1 еВ2, х10 - х° ух°:х = ГО еВ1б охи = 1 еВ2 и сложных характеристические функций с линейной сложностью

(хгх2...,хп)° = У(хР. П*?1). (х,х2...,хп)с' = У(хР'. П*Р) 1-1 1-1 .Ил*«

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

1=1

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

к

УШ)-а(У).

1-1

где к - количество термов, С(Х) - часть терма, зависящая только от X, $(У) - часть терма, зависящая только от У. Если в конечном выражении найден терм, в котором g(Y)=l, то из {(X) определяется искомый тест. Это верно, так как §(У)=1 может был, представлено как

¡=1

что определяет все пары различаемых начальных состояний исправного и неисправного ДУ.

Различающая функция строится описанным способом сначала для итеративной схемы из одного комбинационного эквивалента (КЭ). Если из нее тест не найден, то строится функция дня итеративной схемы из двух КЭ. Из различающей функции для схемы из р й 1 КЭ определяются пары начальных состояний, различаемые в соответствии со стратегией одиночного наблюдения. Для определения пар состояний, различаемых в соответствии со стратегией кратного наблюдения, необходимо объединить все различающие функции для схем из одного КЭ, двух КЭ,..., р КЭ посредством дизъюнкции.

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

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

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

В начале процесса генерации на линиях допускается любая комбинация сигналов для исправной и неисправной схем. Поэтому на всех линиях ЦУ устанавливаем неопределенное значение и. Далее, исходя из знания расположения неисправности и топологии схемы, выполняется структурная импликация. При этом на линиях, соответствующих переменным состояния, и на их линиях-последователях сохраняется значение и. После выполняются процедуры прямой и обратной логической импликации с помощью прямых и обратных многозначных функций. Затем для итеративной комбинационной схемы иэ р > 1 КЭ выполняется обратное распространение критического значения В*(Г)' или О) с внешних выходов схемы. При этом применяется обратная логическая импликация. Тест найден, если для всех итеративных схем выполняется критерий

обнаруживаемости неисправности, основанный на кратной стратегии наблюдения

р

я

где у - характеристическая переменная, соответствующая значению сигнала на линии начального состояния у-а.

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

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

Поэтому разработан точный метод символьного моделирования последовательностных ЦУ с неисправностями. В начале процесса моделирования значения сигналов на линиях, соответствующих переменным состояния, полагаются равными символьным значениям Y=(yi, у2,..., Уп). На каждой j-й итерации для соответствующего входного набора из тестовой последовательности выводятся символьные выражения для внешних выходов схемы Z(Y) (Z-(zi, zi.....Zm)), зависящие от символьных значений переменных начального состояния V. Выражения вычисляются повентильно, используя логику и структуру схемы, на основе законов и свойств булевой алгебры. При выводе учитывается влияние неисправности. К выведенным выражениям Z(Y) применяется предложенный критерий обнаруживаемое™ неисправности, основанный на стратегии кратного наблюдения,

р ю г>- п dZ= у vz£)=l,

j=li=í

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

На основе символьного моделирования последовательностных ДУ с неисправностями разработан метод построения проверяющих тестов для последовательностных цифровых схем. При этом в начале процесса генерации теста имеется множество пар начальных состояний SI, для которых требуется построить различающую последовательность . Из данного множества выбирается пара состояний, для которой строится различающая последовательность Т. Для полученной входной последовательности Т выполняется символьное моделирование заданной неисправности. Если для последовательности Т выполняется критерий обнаруживаемое!!! неисправности, приведенный выше, то она является тестом неисправности. Иначе в результате символьного моделирования из выражения dZ критерия обнаруживаемогти неисправности определяется множество различаемых пар начальных состояний SD. Далее определяется новое множество пар начальных состояний SI=SI\SD. Из нее также выбирается пара начальных состояний, для которой строится различающая последовательность Т. При этом результирующая последовательности Т равна конкатенации ранее полученной послед о-

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

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

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

- графический и текстовый ввод описания ДУ и входных воздействий;

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

- логическое моделирование исправных ДУ на входных воздействиях, заданных пользователем;

- логическое моделирование неисправных ДУ с анализом полноты тестов и определением списка непроверяемых неисправностей;

- генерация проверяющих тестов псевдослучайными и детерминированными методами.

ВЫВОДЫ

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

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

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

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

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

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

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

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

6. Предложенные методы программно реализованы и позволяют существенно сократить время построения проверяющих тестов и повысить их полноту. Они использованы при создании автоматизированной системы моделирования и диагностирования дискретных устройств АСМИД-П, которая предназначена для использования при контроле и диагностировании ЦУ на этапах их проектирования, изготовления и эксплуатации.

Публикация автора

1.СкобцовВ.Ю. Символьно-аналитический метод генерации проверяющих тестов для

последовательностных цифровых устройств // Техническая диагностика и иеразру-шающий контроль. - 1997. - №3. - С.22-29.

2.Скобцов В.Ю. Символьное моделирование неисправностей последовательностных цифровых устройств Н Автоматика и вычислительная техника (Рига). - 1997. - №5, -С.40-50.

3 .Скобцов Ю.А., Скобцов В.Ю. Система логического моделирования и генерации тестов АСМИД-П II Управляющие системы и машины. - 1996. - №1,2. - С.39-45: Структурный детерминированный метод построения проверяющих тестов в 16-значном алфавите для комбинационных цифровых устройств, методы логического моделирования исправных и неисправных комбинационных логических схем с применением единой системы многозначных логик.

4.Skobtsov V, The application of composite multivalued functions in test generation // 9th Conference of the European Consortium for Mathematics in Industry. - Copenhagen (Denmark). - 1996. -P.179-183.

5,Skobtsov V. Structural test generation with employment of multiple observation time strategy // Proc. of 5th Biennial Baltic Electronics Conference. - Tallinn (Estonia). - 1996. -P. 299-302.

6.Скобцов Ю.А., Скобцов В.Ю. Система логического моделирования и генерации тестов на. персональных компьютерах АСМИД-П // Marepiaan XII МЬкнародноГ м1жвумвськ01 щколи-ссмшару "Метода i засоби техшчно! диагностики", - 1вано-Фрашавськ. - 1995. - С.62-65: Алгоритмы моделирования исправных и неисправных комбинационных логических схем с применением 16-значного алфавита, детерминированный структурный метод построения проверяюпщх тестов в 1б-значном алфавите для комбинационных цифровых устройств,

7.Скобцов В.Ю. Псевдо-случайная генерация тестов для последовательностных устройств, основанная на символьном моделировании // Материалы XIII Международной межвузовской школы-семинара "Методы и средства технической диагностики''. -Йошкар-Ола (Россия). -1996. - С.66-69.

в.Скобцов В.Ю. Моделирование с неисправностями и генерация проверяющих тестов для последовательностных цифровых устройств II Тези доповщей З-ï Украшско! конфе-

ренцц з автоматичного керування (АВТОМАТИКА 96), - Том 2, - Севастополь, -1996. -С. 145.

9.Скобцов В.Ю. Символьное моделирование с неисправностями последовательности* цифровых схем // Тезисы докладов Международной конференции "Моделирование и исследование устойчивости систем". - Киев. -1997, - С, 106,

Ю.Схобцов В.Ю. Моделирование в многозначных алфавитах II Сборник трудов победителей конкурса студенческих работ в области математики, механики и кибернетики. -Донецк: ИПММ. -1993. -С.34-43.

Н.Скобцов В.Ю, Структурно-аналитический метод генерации тестов II Дел. в ГНТБ Украины, - 20.12.95. - №76Ук.96.

АНОТАЩЯ

Скобцов Вадим ЮрШович. Розробка структурних методов побудови теспв для дискрепшх присгрохв и застосуванням багатозначних алфавшв. - Рукопис.

Дисертацм на здобуття наукового сгупеня кандидата тсхшчних наук за спещальшстю 05.13.13 - обчислювальш машини, системи i мереж!. - Донецький державний техшчний ушверситет, Донецьк, 1998.

Дисертацк присвячена проблем! розробки структурних методов побудови перев1ряючих теспв для цифрових пристрош. На ochobi застосування ушверсального 16-значного алфавиту i едино! системи багатозначних функщй розроблено сгруктурний детермшований метод побудови перев1ряючих теспв для комбшацшних цифрових схем, що дозволяе скоротити час генерацп тесту. Розроблено метода побудови перев1ряючих теспв i моделювання з пошкодженкями для послщовшсних схем, як! шдвшцують повноту теспв i реал1зують переваги методов побудови теспв, заснованих на теори експернменпв з автоматами, на лопчному piBtd. Основа результата програмно реалЬовано в автоматизованш систем! моделювання i генерацц теспв АСМ1Д-П, що застосовувалася при проектуванк та доагностувакщ реальних цифрових пристрош.

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

АННОТАЦИЯ

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

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

Диссертация посвящена проблеме разработки структурных методов построения проверяющих тестов для цифровых устройств. На основе применения универсального 16-значного алфавита и единой системы многозначных функций разработан структурный детерминированный метод построения проверяющих тестов для комбинационных цифровых схем, позволяющий сократить время генерации теста. Разработаны методы построения проверяющих тестов и моделирования с неисправностями для последова-тельностных схем, которые повышают полноту тестов и реализуют преимущества методов построения тестов, основанных на теории экспериментов с автоматами, на логическом уровне. Основные результаты программно реализованы в автоматизированной системе моделирования и генерации тестов АСМИД-П, которая применялась при проектировании и диагностировании реальных цифровых устройств.

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

ANNOTATION

Skobtsov V. Yu. The development of the structural test generation methods for discrete devices with employment of the multivalued alphabets. - Manuscript.

Thesis on reception of a scientific degree of the candidate of technical sciences by speciality 05.13,13 - computers, systems and networks. - Donetsk slate technical university, Donetsk, 1998.

The dissertation is devoted to the problem of development of the structural test generation methods for digital devices. It was developed structural deterministic test generation method for combinational digital circuits, based on the employment of 16-valued alphabet and unified system of multivalued functions, that allows to reduce test generation time. There were developed test generation and fault simulation methods for sequential circuits, that allow to increase test coverage. These methods implement at the gate level the advantages of the test generation methods, based on the theory of experiments on finite state machines. The main results were implemented as software in the automatic simulation and test generation system ASMID-P, that was employed for design and diagnosis of real digital devices.

Key words: digital device, logical circuit, fault, logical simulation, test generation.