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

Российская академия наук О^ена Ленина институт проблем управления

л . ■

• ' На правах рукописи

СКОБЦОВ Юрий Александрович

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

ДИСКРЕТНЫХ УСТРОЙСТВ

Специальность: 05.13.13. — Вычислительные машины,

комплексы, системы и сети

АВТОРЕФЕРАТ

диссертации на соискание ученой степени доктора технических наук

МОСКВА-1993

Работа выполнена в Институте прикладной математики и механики АН Украины

Научный консультант: доктор технических наук, профессор Д.В.Сперанский

Официальные ошонашггы: доктор технических наук, профессор А.И.Кострыкин; доктор технических наук, профессор Л.В.Дербудавич; доктор технических наук, профессор В.А.Твердохлэбов.

Ведущая организация: Институт проблем моделирования в энергетике АН Украины

Защита состоится _;1993г. в

час Л?*? " мин. на заседании Специализированного совета Д 002.68.01 Института проблем управления РАН по адресу: 117806,Москва.Профсоюзная ул.,65.

1 С диссертацией можно ознакомиться в библиотеке Институт« проблем управления РАН :

Автореферат разослан "_" _1993г.

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

Е.В.Еркевич

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

1.ВВЕДЙШВ

Актуальность.Мощным катализатором научно-технического прогресса во всех отраслях экономики является использование вычислительной техники. От ее качества и надежности в большой степени зависят эффективность современного производства.В связи с этим важнейшее значение имеет исследование й разработка новых Современных методов технической диагностики,надавленных на повышение надежности и эффективности использования ци|!ровых устройств.

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

Проведение Всемирных симпозиумов по отказоустойчивым вычислительным системам (FTCS) и тестированию (IEEE Teat Conference), Европейских конференций по системам автоматизированного проектирования (Euro САБ) и тестированию (Euro Test Conference),международных конференций " Системы , допускавдяе неисправностй , и диагностика" (?ISD),отечественных совещаний и школ-семинаров по технической диагностике ДУ также свидетельствует об актуальности исследования этих прбблем.

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

ДУ. Из этого следует актуальность разработки единого комплексно подхода к задачам моделирования и построения тестов.

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

Основные направления выполненных исследований следующие:

-разработка троичных моделей ДУ логического и функционального уровней;

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

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

-разработка 'методов и алгоритмов моделирования неисправных ДУ, направленных на повышение эффективности процедур анализа полноты тестов и распдарения класса диагностируемых устройств и неисправностей:

-исследование и разработка методов и алгоритмов построения тестов .наЬравленных на сокращение пере.бора при поиске тестовых наборов и расширение границ применимости структурных методов;

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

В основе решения многих задач технической диагностики ДУ лежит исследование различных логических зависимостей. Булеиы дтНиронци-

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

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

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

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

значного алфавита. Разработана единая система многозначных алфави тов.применяющихся в технической диагностике ДУ.Она включает в себй 3-,5-,6-,8-значнце алфавиты,используемые при моделировании ,и 6-., 10-,12-,16-значные алфавиты .применяемые при генерации тестов . На основе этой системы алфапитов впервые разработана универсальная математическая модель в виде многозначных функций,которая позволя-. ет решать основные задачи технической диагностики ДУ с использованием указанных многозначных алфавитов.Ыногозначше функции при этом представляются с помощью четырех двоичных (булевых) функций. Определены прямые и обратные многозначные функции. Установлена связь мезду многозначными функциями и булевыми дифференциальными операторами.Построены многозначные модели для ДУ с тристабильными элементами и МОП-схемами,Впервые разработаны многозначные модели на функциональном уровне.

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

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

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

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

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

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

Реализация результатов.Представленные в диссертации результаты проводились в рамках следующих госбвдкотных НИР Института прикладной математики и механики АН Украины:

"Разработать методы построения тестов для системы базовых ТЭЗов и модификации структуры ТЭЗов с целью улучшения их диагностируемое™ и выдать рекомендации организациям Минавиапрома по их использованию" (1979-1981,* Госрегистрации 79033304);

"Анализ непрерывных и дискретных систем с применением в задачах управления и оптимизации"(1982-1985,* Госрегистрации 01820073577); "Разработать математические методы оптимизации управления с приложением в технической диагностике,транспортных и .технологических процессах"(1986-1989,* Госрегистрации 01.860.042947); "Исследование математических вопросов теории цифровых устройств и создание программных систем их контроля и диагностирования"(1990-1993,* Госрегистрации 01.9.00.018.556). ••

Кроме этого разработка и внедрение результатов проводились при выполнении следующих хоздоговорных работ: "Разработка алгоритмов и системы математического обеспечения для моделирования и диагностики цифровых систем"(1982-1984,5420673. 06004-01), . •

"Внедрение алгоритмов и системы математического обеспечения для моделирования и диагностики цифровых устройств"(1984-1987,* Госро-гистрации 01840084752),

"Разработка модеЛей,алгоритмов и математического обеспечения диаг-

юстирования цифровых устройств" (I987-I989.J6 Госрегистрации 01.870. 055.678), заключенных между Саратовским производственным объединением им.С.Орджоникидзе и Специальным конструкторско-технологическим бюро систем управления ИШМ АН Украины;

"Исслодопшшо методов,алгоритмов п разработка программного обеспечения контроля и автоматизированного поиска неисправностей МСВТ" (1909-1990,.» Госрогистрации 5540107.00045).заключенного между Мос-копским НИИ Научный центр и Специальным конструкторско-технологи-ческим Oirpo систем управления ИПММ АН Украины.

На основе предложенных в диссертации методов и алгоритмов под руководством и непосредственном участии автора разработаны программные системы моделирования и генерации тестов.Первая автоматизированная система моделирования и диагностики (АСМИД) реализована на ЕС ЭВМ,вторая (АСМИД-П) на персональных компьютерах IBM PC/AT.Апробация и эксплуатация этих систем показала их высокую эффективность. Система АСМИД использовалась при построении тестов для нескольких сот цифровых плат устройств вычислительной и измерительной техники,бортовой,промышленной и шахтной автоматики в Саратовском производственном объединении юл.С.Орджоникидзе , НИИ Научный центр (Зеленоград) и некоторых других предприятиях.Экономический эффект от внедрения методов и алгоритмов,разработанных в диссертации составляет более 800 тыс.руб. в год.

Система моделирования АСМИД-П используется в Донецком государственном университете в учебном процессе.Научные и практические результата диссертации применяются при чтении автором курсов лекций в

С j

Донецком государственном университете "Моделирование вычислительных систем" и "Техническая диагностика цифровых систем ". Соответствующие документы о внедрении приложены к диссертационной работе.

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

были представлены на III,IV,VI,VII Всесоюзны* совещаниях по технической диагностике(Минск-1975г.,Черкассы-1979г. , Ростов-на-Дону-1987г., Саратов-1990г.) ; IV Всесоюзной конференции " Однородные вычислительные системы и среда"(Киев-1975г.); III,IV,VII,VIII,IX, XI.XII международных конференциях "Системы,допускающие неисправности" ("fault tolerant .systems and dlagnoa tlea":Катовице-1980г.,Ерно-1981г.,София-1984г.,Катовице-I985г.,Epíio-I986r.,3уль-1988г.,Прага-1989г.);Международной конференции "Макроэлектрош1ка-1984" ( Прага-1984)¡Всесоюзном семинаре "Контроль изделий микроэлектроники и применение микропроцессорных средств вычислительной техники "(Цахкад-зор-1984г.)¡Республиканской конференции "Проблемы диагностирования микропроцессорных систем"(Ужгород-1987г.)¡Республиканской конференции "Автоматизация контроля вычислительных устройств и систем"(Вин-ница-1988гК Всесоюзном семинаре по дискретной математике (Москва-1989г)¡Всесоюзной конференцшГ'Диагностирование,надежность,неразру-шающий контроль электронных устройств и систем" (Владавосток-1990г); XV Всесоюзной школе-семинаре по технической диагностике (Туапсе-1990г); XI Всесоюзной конференции "Проблемы теоретической кибернетики" (Волгоград-1990г.); Международной конференции но информатике ("InformatIk-Pachberlchte",S tut tgart-1990) ¡на общемосковском семинаре по технической диагностике¡научном семинаре лаборатории тех-, нической диагностики ИЛУ (Москва)¡семинаре "Техническая диагностика управляющих и вычислительных машин" Института проблем моделирования в энергетике АН Украины (Киев); семинаре " Методы и средства технической диагностики" СГУ (Саратов); семинаре "Дискретные системы и формальные языки" ЙПММ АН Украины (Донецк) , а также на ряде республиканских и.региональных конференций и.семинаров.

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

авторстве.

Объем работы.Диссертация.изложенная на 275 страницах .состоит из 9 разделов,спйска литературы из 178 наименований и приложения,в котором представлены акты о внедрении и использовании результатов.

Содержание работы.

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

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

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

При автоматизации проектирования и диагностирования ДУ в настоящее время широкое применение находит логическое моделирование. Сема возможность создания современных ЭВМ на БИС и.СБИС связана с возможностью их моделирования и устранения всех дефектов проекта до

изготовления опытного образца. Процесс логического моделирования состоит из подачи на внешние входы модели ДУ входных воздействий и последовательного,от входов схемы к ее выходам, вычисления значений выходов логических элементов и получения таким образом выходной реакции. Основными отличительными чертами логического моделирования является: модель сигнала.модель схемы в ЭВМ и организация распространения сигналов в модели ДУ. Моделью сигнала называют соответствие между символами алфавита модели и реальными сигналами.В зависимости от применяемых моделей сигналов методы логического моделирования делятся на двоичные и многозначные.Двоичный алфавит В2={0,1) достаточно точно отражает поведение ДУ в статике,но не позволяет моделировать переходные процессы и неопределенные начальные состояния элементов памяти.Поэтому для анализа состязаний используются многозначные алфавиты. Простейшим из них является троичный алфавит Еа= {0,1,и) , где символ и обозначает неопределенное значение сигнала (0 или 1,но неизвестно,что именно).

Используются также.алфавиты с большим числом символов,позволяющих уточнить характер переходных процессов, например, пятизначный ал}»вит В3={0,1 ,Е,Н,и> .где символы Ей В используются для обозначения передйего и заднего фронтов соответственно.Известны также алфавиты "большей значности.в которых используются дополнительные символы для представления статических и динамических состязаний . Для некоторых технологий, например таких как МОП-технология требуется вводить дополнительные символы для представления состояния высокого импеданса ,так называемой "логической силы" и т.п..В настоящее вре-- мя существует несколько десятков многозначных логик и число их продолжает расти.В основном эти логики получены эвристическими методами. Алфавит выбирается из физических соображений для отражения неопределенных значений, изменений сигналов при переходных процес-

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

Моделирование ДУ в коночном счете сводится к моделированию отдельных элементов.Чрезвычайно важной при разработке систем моделирования является задача построения многозначных моделей логических элементов.Здесь используются различные методы:табличные,компонентные , алгоритмические и другие.При компонентных моделях многозначный алфавит кодируется двоичными компонентами, принимающими значения {0,1>. Многозначная модель логического элемента при этом образуется с помощью нескольких двоичных компонент (булевых функций).

Моделирование в различных многозначных алфавитах,например, Еа и Ез,требует разработки различных многозначных моделей логических элементов .То есть для каждого алфавита (и даже его способа кодирования) надо иметь свои модели логических элементов.Если мы хотим иметь в системе программы моделирования в различных алфавитах (с различной степенью адекатности), то при таком подходе должны разработать для каздого ал1>авит8 свои модели всех логических элементов.Более того,если в система есть программы генерации тестов ,то они также требуют построения своих многозначных,моделой для исполь-пользуемых алфавитов,которые существенно отличаются от применяемых в моделировании.Это создает серьезные проблемы при разработке систем моделирования и генерации тестов. Поэтому желательно построить единую систему многозначных моделей,которая позволяла бы проводить

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

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

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

Наиболее сложной в математическом плане и трудоемкой по ресурсам при разработке автоматизированных систем диагностики является задача генерации тестов. За последние три десятилетия достигнуты определенные успеха в решении этой проблемы. Несмотря на это задача разработки методов генерации тестов остается актуальной даже для комбинационных устройств.Дело в том, что современная технология проектирования контролепригодных цифровых устройств,основанная на методах БСАМ-с1еэ1еп и других, сводит эту проблему к построению тестов для комбинационных схем ( как правило высокой

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

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

1)оСстракные,основанные на теории экспериментов с автоматами;

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

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

кратная булева производная -

а"г а" г а а , ад- . .

4 1 2 р

- 16 -

Л-оператор по переменным Х1=(х1х2...хр) € X =(х1Г2...хп)

лг аг ах а2х а2х а*г

ЛХ7 = 3x7 7 ЯГ" 4 ЗхТх2 7 Ш~ахзч- • -у Ях^ГТТТШГ" •

- 16 -

булева вариация-

ЛГ ^ бх „ ^ ох, р бхвхд __ ехбх ...ех

б1=ах; 1 7 ах; 4 у а^и^ттат 12 р -

булев дифференциал-(1Х Г=Г(Х1 )Ф1(Х1<к1Х1)=

[I т _ г- ^ ах ф*11 ах ф^1 ах г!х ф. . ,ф аР:Г ______ах ах,.. .ях .

лА-'^р ах, 1 ах2 2 ах^ 1 2 ахТах2...ахр 2 р

ориентированный булев дифференциал,характеризующий изменение функция Г(Х) из а в Ь (а,Ъ=0,1) -раЬх (Х)=[Г(Х)<шз [г (ХФах)ФЫ.

В третьей разделе "Троичные модели дискретных элементов" рас--С

сматриваются задачи построения моделей логических элементов в троичном алфавите Ез={0,1,и).Основополагающим понятием в троичном моделировании является троичная функция £*(Х*), которая определяется из исходной двоичной (Оулерой) функции 1(Х) следующим образом. Для определенности рассмотрим троичный набор переменных (и,Аг),где и-вектор из р неопределенных значений,а ¿2=(ар„1 ,ар>2,..,аг^.-вектор двоичных значений а^О.1 для 1=р+1,п.Тогда троичное значение Г*(Ц,А2) определяется исходя из значений булевой функции I на 2Р двоичных наборах,покрываемых троичным набором. Если на всех 2Р наборах 1=0(1),то X*(Ц,А2)=0(1).Если же найдутся двоичные набор!,на которых 1 принимает различные значения , то г*(и,Аг)=и , то есть I*(и,А2)=0(1),если и только если Г(Х2=А2 )=0(1) независимо от сна -

чений Х1 (Х2 = (хр^ ,хр42,.. ,хп) е X).В пропитом случав Г*(и,Аг)=и.

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

Здесь нпромошшо х1 .Охллогут принимать

' только двоичные значения.При этом тро-*

ичнш! нороменна'я х^=и .если и только пели Ох =1.Если Ох =0 ,то х*=х. .Могяо

I ^ * I I

сказать,что -двоичная компонента, а

Ох,- признак пеопроделенпости. .

В современных системах моделирования;как правило, компононты хранятся в различных машинных словах.Аналогично, поведение троичной функции I* может быть описано с помогаю двоичных функций 1 и ОГ. При используемом методе кодирования основная трудность разработки троичной модели состоит в построении по заданной двоичной функции 1 второй компонента - функции 0Г,с помощью которой вычисляется значение признака неопределенности.

Из определения следует.что значение троичной функции Г*(и,А?) определяется зависимостью :Г(Х2=А2) от порайонных Х4.Но зависимость 1(Х) от перомотшх Х4 определяется Д-опоратором А1/АХ .'Можно показать,что £(Х2=А2) зависит от переменных Х1, если и только если ДГ/АХ^ (Х2=А2 )=1. В противном случае Д1/ДХ1(Х2=А2)=0.Таким образом, I* (11,*А * )=и, если и только если ДГ/ДХ>(Х2=А2 )=1. Так как АГ/ЛХ1 но-дучаотся из 01 при 0х1=1 для х. еХ1 и 0х.=0 для х.еХ2, то отевда следует Теорема 3.1 1*(и,А2 )=и о 81 <вХ,=1 ,СХ2=0,Х2=А2 )=1.

X* Ох V

0 0 0

1 1 ■ 0

и 0 1.

1 1

Это обуславливает возможность применения булевой вариации в! для троичного моделирования ДУ.При рассматриваемом кодировании поведение функции Г* в троичном алфавите описывается булевой функцией I(двоичная компонента) и ее булевой вариацией (признак неопределенности). Таким образом, мы имеем аналитические формулы I и 61 для представления произвольной троичной функции Г* по заданной двоичной (булевой) функции. Полученное соотношение целесообразно использовать для построения троичных моделей цифровых микросхем малой и средней степени интеграции,а также логических операторов ЯРП, представленных в табл.2.

Кроме логических ЯРП имеют таюке отношения, арифметические и условные операторы.Для них разработаны троичные модели функционального уровня.Раосмотрим оператор А>В. Обобщая определение троичной функции для отношения А*>В*,можно выполнить оператор А>В для всевозможных двоичных операндов А й В .порождаемых троичными А* и В*, и затем сравнить результаты.Если для всех пар А>В,то Г^>в=1.Аналогично =0,если для всех пар А^В.Если же найдутся пары,для катала С

рых результаты различны (для одной пары А>В,а для другой АСБ) ,то 1*)В=и.При этом надо выполнить 2Р" операторов отношений,где р и г -число .неопределенных разрядов в А* и..В* соответственно.Очевидно, подобная схема вычислений значений троичной, функции является достаточно универсальной и справедлива не только для операторов отношений.Эта схема соответствует тривиальному методу вычисления значений троичной функции и часто применяется при троичном моделировании на на функциональном уровне .Платой за универсальность является высокая сложности вычислений г=2р". Используя свойства отношения А>В, можно получить алгоритм вычисления 0ГА>В .который требует выполнения всего двух операторов отношений дам экстремальных значений А и В и и представлен в табл.2. Аналогичные формулы получены для остальных

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

Таблица 2

Операторы 1 ОГ

Логические АВ А<^В0А^А0В

АОВ*ВбА*ОАбВ

А ЗВ ОА АСВ*В6АУ0А0В

АОВУВ^САОВ

АФВ 0А*0В

Ш {^ОВ

Отношения А>В

А<В [4"'\вя" )&(вт1"ата")

А=В <А",,,%вВ)=(В"",х«ОА)

А^В (А™°"хОВ) = (В""1^ОА)

А^В (А™1г|<втох )&(в"'1"ата")

АЗЗ (Ам1п«гВта* )&(В™1 п<Ат<"')

Арифмети- Б=А+В (З^^ФБ"""')

ческие Б=А-В вAvOBv(B™l,,<!>Dm")

ШСН(С,1),ПЕСН(С,1) (Ст1 "ФС"""* >

Условные Г? А ТЙЕМ 2<-В

ЕЬЗВ Z<-C

САБЕ А в»-1РГЛжА v0fдгд)cz 1,1 = 1 1 1

ониропашгах так и однокристальных).

Кроме рассмотренного вариационного метода кодирования подобные модели разработаны еще для трех применяемых на практике методов кодирования троичного алфавита,которые представлены в табл.3-5 соответственно .

Таблица 3 . Таблица 4 Таблица 5

X* х° X1

0 1 0

1 0 1

и 1 1

X* х° х1

0 1 0

1 0 1

и 0 0

X* х° X1

0 0 0

1 1 1

и 1 0

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

I*

деле .получены трехкомпонентные модели логического уровня.

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

Пусть А={а1,а2,...,ак}-н0которнй к-зиачный алфавит и ?=(Г1,

Г2.....Гт)-множество п-местных функций,каздая из которых является

отображением А"->А.Вместе А и ? образуют многозначную логику, которую мы будем обозначать (К,?). Существует два способа расширения многозначной логики (А,Р) на некоторую более мощную логику (А,?). Первый способ состоит в том, что новый алфавит получается как под-множпстпо декартового произведения исходного алфавита Ас А»А«... «А. Нппримор,алфавит В4={00,01,10,11} получен таким образом из исходного в^-аэ.п.

• г»

При втором способе расширения (А,?) новый алфавит А образуется как некоторое множество подмножеств исходного алфавита А с 2*. Каждое новое значение а. е А равно неупорядоченному подмножоству А вида а^а^и аги... и аа .где а^ е А.Например,троичный алфавит В3 может быть получен таким образом из двоичного алфавита В2. При этом неопределенное значение и=0 и 1.Таким же образом на базе рассмотренного алфавита В^=(00,01,10,11) можно получить алфавит Ез= С(00), (11), (0Ш01и11), (0Ш1СХ111 ), (0Ш0Ш1Ш11)}. При этом: 0=(00)-статический нуль, 1^(11)-статическая единица, Е=(0СШ1 и 11 )-изменение сигнала из 0 в 1 ,Н=(0Ш1СКЛ 1 )-изменеше из 1 в О, и=(0ОиО11ЛШ11 )-неопределенное значение сигнала.

Основной проблемой при расширении многозначной логики (А,?) па (А,Р) является построение многозначных функций ? в новом алфа-. вите. Кроме ранее существовавших табличных методов необходимы и другие ,более совершенные метода построения многозначных моделей логических элементов, которые позволяли бы выполнять моделирование

г-1 ■ -

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

В качестве базового мы принимаем 4-значннй алфавит Е?={00,01 ,

10,11). Элементы этого алфавита имеют следующую интерпретацию: 00 (11)-значения сигналов одинаковы, 01 (Ш)-значения сигналов отличны в различные моменты времени или в разных технических состояниях ду. Остальные алфавиты мы будем строить из базового с помощью двух приведенных способов расширения. Основным является 16-значшй алфа-алфавит В1Л.представленный в табл.6,который содержит всевозможные подмножества алфавита В*.

Таблица 6

Значение Символ - Кодирование

х°° X01 X"

0 0 (0) 0 0 0 0

I 1 {11} 0 0 0 1

2 в ПО) ' 0 0 1 0

3 01 С1Ш11) 0. 0 1 1

4 -Б' ' - <01 > 0 1 0 0

5 ?1 {0Ш11> .0 1 0 1

6 В* {01 ию) 0 1 1 0

7 Б1 {011Л0и11> • 0 .1 1 1

8 с 0 (00) 1 0 0 0

Э С «юи11> 1 0 0 1

10 РО <0СХЛ0> 1 0 1 0

II н {ООиюиП) 1 0 1 1

12 СО {00Ш1.) .1 1 0 0

13 в {ооишит • 1 1 о 1

и но {ООЮ1ШО) 1 1 1 0

15 и {00и01и1Ш11> 1 1 1 .1

Ассоциируем с каждом элементом нашего базового алфавита переменные хой,х01,*10.*11 соответственно.Поведение многозначной функции Г(Х) (где Х=(х1 ,ха....,хп)) может быть описано с помощью четырех булевых функций ^(Х^.Х01 .Х^.Х'1). Х01(Х00,Х°\Х,0.Х"), Г00(Х00,Х0,.Х,0,Х'1).Г0,(Х00.Х0,.Х,0.Х1').При рассматриваемом методе кодирования функции Г°°,£°1 .Г10, Г14 одинаковы для наиболее распространенных многозначных алфавитов,используемых при моделировании и генерации тестов. Компоненты Г00,!04,!10, Г" основных вентилей представлены в табл.7. Для произвольной булевой функции они могут быть получены с помощью ориентированных булевых дифференциалов.

Таблица 7

1 х01 X" Г"

аЬ а01Ь*°*а,0Ь01 а°'Ь01 а*°Ь,а

а*ь а00Ь°° „а.оо осхс а Ь »а о V а°'Ь01 „10. ОО а о «а ч> V а'°Ь1р „11 «,11 а ^ ь V а0,Ъ,0«а,0Ь0'

а а11 а01 а°°

а« 6 1 а VI) V а Ь ^а с) „«О.ОО „00.10 а и «а о -V „Ю. 1 о а Ь 1* .О О ОО^О! а Ъ «а Ч) V о г КС1 а Ь ОО. ОО а Ь

аЬ 1.И а Ь 10. 1 1 11.1 о а о va ъ V а 0 -С*. 1 1 11. 01 а Ь «а Ь V О 1 , О! а Ь ОО . ОО а ^ 01. Ю „Ю, О! а Ь ^а Ь

Полученная система функций Г°° ,1°'.Г10, X11 является универсальной и позволяет моделировать и строить тесты в основных многозначных алфавитах,применямых в технической диагностике ДУ.К ним от-

носятся прежде всего В.В, и алфавиты Н с в «В «В,, Н_ с В„«Е «В ,

9 3 о 2 Э 2 В 2 £> 2

которые применяются при анализе состязаний. Для схем , содержащих тристабильные элементы,используется алфавит С4={0,О,Г,и) , также являющийся подмножеством универсального алфавита В10 (символ 0 означает в нем состояние высокого импеданса ). Введение "логической силы" позволяет получить с помощью указанных конструкций более сложные алфавиты,применяемые для схем,выполнены! по МОП-технологии. Отметим,что используемые при генерации тестов алфавиты Та={0,О,1 Б',и) и Т1О={0,О,1 ,Б,В' ,Ю,Р1 ,С0,С1 .и).также являются подмножествами В1в.

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

Кроме рассмотренных моделей логического уровня разработаны также многозначные модели для основных операторов ЯРП функционального уровня.Они обладают линейной сложностью от числа разрядов в аргументах.

В пятом разделе "Моделирование неисправных устройств" не основе универсальной системы многозначных функций разработаны методы моделирования ДУ с неисправностями в многозначных алфавитах:парал-

лельный,дедуктивный и одиночное распространение неисправностей.

До настоящего времени в многозначных алфавитах (со значностью больше 4) параллельный метод распространения не получил, так как

Таблица 8

Г а01 а10 а11

¡11) Ь'^Ь" ) Х^Ь^Ь10)* ^(Ь01«!)") Х^Ь^ь"1Ь 1>0(Ь'%Ь") х01ь°1*х1,ь1'

а^-Ь А^.Гь0' Х,0(Ь°^Ь10К Г"(Ьс,УЬ" ) Х10(Ь^Ь,0К Х"(Ь°^Ь")

а г11 11° Xй0

а®Ь ГЬ00»!0^" Х'^'^Х'-Ь1' х^'^х01^1 x,1b00vx,0b0^

при увеличении значности алфавита розко падает скорость моделиро-ваш!я в виду сложности многозначных моделей логических элементов. Предложенные метод кодирования универсального алфавиту В1а и единая система моделей на базе четырех компонент Г00,!01,Х10,Х" позволяют существенно повысить скорость параллельного метода моделирования в многозначных алфавитах и сделать ее приемлемой для практического применения. При этйш каждой линии схемы ставится в соответствие 4 ■ машинных слова в соответствии с кодированием В1£>.Значения сигналов для каждого логического элемента вычисляются параллельно с помощью прямых многозначных функций.Учет свойств компонент Г0',!'0 позволя-

ет их вычислять только в том случае,когда компоненты входов а01,»1® И". Ь10 отличны от нуля. Это позволяет проводить моделирование в многозначных алфавитах,в основном,вычисляя две компоненты 1°°,Г11, • что существенно повышает скорость моделирования.

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

Дедуктивный метод основан на анализе •логической зависимости значений-сигналов на данном входном наборе от наличия неисправностей. Каждой линии 1 ДУ поставим в соответствие четыре переменные х°°,х°' .х'0,!*1.принимающие двоичные значения 0,1 и четыре списка неисправностей ^".Х^'Д^.Х*1 , связанные с этими Переменными.

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

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

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

нения неисправностей в многозначных алунитах. Суть метода очень проста. Сначала моделируется исправное устройство на данном входном наборе. Далее выбирается одна неисправность из множества непроверенных на текущий момент и вносится в модель схеш. Затем выполняется распространенно влияния этой неисправности на данном входном ноборо.Если влияние неисправности достигает одного из внешних выходов,то неисправность считается проверенной и удаляется из множества непроверенных. неисправностей. В противном случае эта 'Чюцпдурэ повторяется для следующих наборов с той же неисправностью до тех цор пока она не проверится или же будут обработаны все наборы теста. Ключевым' моментом для эффективности данного метода является организация параллельных вычислений в процессе прямой и обратной фаз. Решение этой задачи для прямой фазы хорошо обеспечивает единая система многозначных прямых функций.Аналогично , для решения задачи обратной фазы можно использовать обратные многозначные функции.

С внедрением КМОП-технологии возник новый класс физических неисправностей,которые проявляются в изменении времени распространения сигналов . Правильное функционирование цифрового устройства возможно только в том случае , если времена распространения сигналов вдоль путей логической схемы лежат в определенных пределах. Когда время распространения сигнала выходит за эти пределы,говорят, что имеет место неисправность типа изменения задержки сигнала. В подавляющем большинстве эти неисправности приводят к увеличению времени распространения сигналов. На основе универсальной, многозначной модели разработан новый метод моделирования неисправностей типа "задержка распространения сигналов". Он основан на моделировании ДУ в алфавите Ба={0,1 .F0.F1,11} .Метод позволяет выявить неисправности этого типа,проверяемые данной парой наборов..

В шестой разделе "Построение тестов для комбинационных уст-«

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

Разработано два метода построения тестов.применяемые на первом этапе. Первый из них строит соседние наборы,отличающиеся значенном одного входа. Соседние наборы эффективны для схем, выполненных по КМОП-технологии,при проверке неисправностей типа задержка распространения сигналов и "транзистор постоянно открыт" или "транзистор постоянно закрыт". Изменение только одной входной переменной повышает вероятность того,что данная пара наборов будет устойчивым тестом и свободной от состязаний.Соседние наборы обладают хорошими диагностическими свойствами. Суть метода заключается в следующем.. Программным способом генерируется псевдослучайный' двоичный нвбор. Далее,придавая по очереди каждому входу значение Б (если он в исходном наборе равен 1) или В'(если он равен 0),выполняем моделирование в алфавите В на полученном многозначном наборе. Значение входа, который дает лучшие результаты (по определенным критериям ) при моделировании, меняем не противоположное и получаем пары соседних наборов.

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

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

Задача построения проверяющего теста для данной неисправности может быть решена аналитически,если функционирование ДУ в исправном и неисправном состояниях задано с помощью аналитических выражений Функция выходов. Пусть 1(Х)-булева функция, реализуемая исправным комбинационным устройством,а ср(Х)-неисправным.Назовем разли-чащей функцией неисправности <р следующую функцию: Б(ф)=Г(Х) Ф ф(Х).

Очевидно,что наборы значений входашх переменных X, на которых В(ф)-=1. являются проверяющими тестами для данной неисправности ф. С использованием разложений булевых функций в ряды Тэйлора получен структурный метод построения тестов,основанный на вычислении булевых производных.Нахождение проверяющих наборов для заданной неисправности при достаточной глубине и малой разветвлешюсти схемы представлкьтся болев эффективным по сравнении с их поиском непосредственно по определению различающей-функции вследствие использования структурных свойств схемы. Однако для сложных ДУ аналитичес-ческие вычисления (и поиск решения) становятся очень трудоемким.

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

Большинство структурных методов построения тестов основаны на активизации путей в схеме с помощью многозначных алфавитов. Они позволяют с различной точностью описывать возможные комбинации значений сигналов в исправном и неисправном ДУ.Сначала предполагается,что на каждой линии устройства возможны любые комбинации значений сигналов:00,01,10,11.Поэтому всем линиям схемы присваивается неопределенное значение и алфавита В1о. Затем, используя свойства структуры схемы и знание местоположения данной неисправности,исключают ненужные (или невозможные) комбинации сигналов для линий ДУ.Очень важно, что исходной моделью структурных методов является непосредственно логическая схема ДУ (поэтому не нужны громоздкие алгебраические преобразования).

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

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

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

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

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

построения тестов для ДУ с памятью.Можно показать,что построение СП

длины Т сводится к поиску таких значений Х1,Х2,...,Хт,при которых все переменные состояния у**1 (У'.Х'.Х*,... ,ХТ) не зависят от значений У* начального состояния.

Но условием независимости булевой функции Г(Х,У) от переменных У=(у1Гу2,...,ут) является равенство -£у-=0. Поэтому построение СП длины Т сводится к решению уравнения

Лт/1*1

т ЛУ

V -=0.

^..ДУ1

Так как булева вариация является параметрической формой задания А-операторов, то это шсвивалентно решению следующего уравнения

т - » —» —> —»

V оу'^ех^о.бх^о,... ,ехТ=о,бУ1н ьо.

Очевидно,что СП является входной последовательностью, которая

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

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

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

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

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

На основе изложенных в диссертации методов разработаны две программные системы моделирования и генерации тестов для ДУ.Первая-автоматизированная система моделирования и диагностики (АСМИД) была реализована на ЕС ЭВМ и эксплуатировалась на ряде предприятий г.г.Саратова и Донецка.(с 1981 по 1939 г.г.) С помощью этой системы были построены тесты для нескольких сот цифровых плат устройств вычислительной техники,бортовой,промышленной и шахтной автоматики. В приложении приведены соответствующие документы , подтверждающие экономический эффокт от внедрения этой системы(более 800 тыс.руб. в год.)

Вторая система (АСМИД-П) реализована на персональных компьютерах IBM PC/AT (с 1990г. по настоящее время ) и продолжает развиваться. Ее назначение и состав представлены на рисунке,который фактически является копией главного меню системы.

Система апробирована на схемах международного каталога ICCAS85 и ICCAS89 и показала высокую эффективность.

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

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

Основные результаты работы.

Основной результат диссертационной работы заключается в еле-

АСМИД-П Институт прикладной математики и механики АН Украины, версия 1.0 отдел ТУС,г.Донецк,тел. (0622) .51-01-47,Скобцов Ю.А.

Текущий каталог: C:\ASI03) Имя схемы: с5147.оиЪ

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

При разработке указанного комплекса методов получены следующие результаты.

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

2.Предложена единая система многозначных алфавитов,которая включает все основные алфавиты,применяемые на практике,;! позволяет создавать новые алфавиты при исследовании проблем технической диагностики. На этой основе впервые разработана универсальная математическая модель в виде единой системы многозначных функций,которая позволяет решать основные задачи технической диагностики ДУ.Определены прямые и обратные многозначные функции,составляющие основу этой системы. Установлена связь между многозначными функциями и булевым дифференциальным исчислением.Разработаны единые многозначные модели для логических элементов,позволяющих работать с основными алфавитами,применяемыми на практике. Разработаны многозначные модели на функциональном уровне. (« • .

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

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

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

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

6.Разработанные в диссертации методы и алгоритмы реализованы при создании двух программных систем моделирования и генерации тестов

различных поколений.Перввя автоматизированная система моделирования и диагностики (АСМИД) реализована на ЕС ЭВМ, вторая (АСМИД-П)-на персональных компьютерах IBM PC/AT.Внедрение и эксплуатация на на ряде предприятий этих систом показало их высокую эффективность, обусловло1шую сокращением времени построения тестов..повышением их качества,снижением ручного труда и требований к уровню квалификации обслуживающего персонала.Экономический эффект от внедрения составил белое 800 тыс.руб в год. Научные и практические результаты диссертации использованы при подготовке учебно-методических материалов , лабораторных работ и введены в соответствующие курсы лекций.

Основные научные результаты опубликованы в следующих работах: 1.Скобцов D.A.0 применении кратных булевых производных в диагностике комбинациошшх схем //Материалы III Всесоюзного совещания по технической диагностике,Минск,1975.-М.:Наука,1975.-с.70-71.

2.Скобцов D.А.Представления тест-функций для кратных неисправностей в комбинациошшх схемах/материалы 1V Всесоюзной конференции "Однородные вычислительные системы и среды",часть З.Киев,1975. -Киев:Наукова думка,1975.-с.12-13. 3.Скобцов В.А.Построение множества проверяющих тестов для заданной неисправности в цифровых устройствах//Дискретные системы,формальные языки и сложность алгоритмов.-Киев: Изд. Ин-та кибернетики АН УССР,1977.-с.66-83.

4.Сперанский Д.В.^Скобцов В.А.Синтез, проверяющих последовательностей для дискретных устройств с памятью методом различающей функции//Автоматика и вычислительная техника,1978.-N3.-с.21-27. 5.Сперанский Д.В.,Скобцов D.А.Синтез синхронизирующих последовательностей для дискретных устройств с памятыо//Дискротныо сис-

- за -

темы,формальные языки и сложность алгоритмов.-Киев:Изд.Ин-та кибернетики АН УССР,1978.-с.84-94.

6.Скобцов D.А.,Сперанский Д.В.Структурно-аналитический подход в задачах диагностики синхронных последоветельностных схем//Мате-риалы VI Всесоюзного совещания по технической диагностике,Часть г.Черкассы 1979.-М.:Изд-во Инс-та проблем управления,1979.-

с.114-116.

7.Скобцов D. А.Применение булевых дифференциальных операторов при построении проверяющих последовательностей//Автоматика и теломо ханика,1979.-N9.-с.136-148.

8.Скобцов D.А.»Сперанский Д.В.Аналитический метод построения различающих последовательностей для дискретных устройств с памятью //Автоматика и телемеханика,1980.-N1.-с.122-130.

9.Скобцов ß.А..Сперанский Д.В.Структурно-аналитический подход в задачах диагностики синхронных последовательностных схем/электронное моделирование, 1980.-N4.-с.32-38.

Ю.Скобцов D.А.,Сперанский Д.В.Структурный метод построения диагностической последовательности для синхронных схем с памятью// Техническая диагностика,эксплуатация управляющих и вычислительных машин.-Киев:Наукова думка, 1980.-с.32-42.

H.Skobtsov Ju.A. .Spleranskiy D.V.Construction of all checking sequences for given fault in synchronous sequential circuit// Proc.of 11 Int.Conl.Fault-tolerant systems and.diagnoatlcs, Katowice,1980.-KatowlcerSITPH,1980.-p.79-85.

12.Скобцов D.А.Построение входной последовательности.проверяпцей заданную неисправность в схеме с памятью//Вопросы технической диагностики.-Ростов-на-Доду:Изд.РИСИ1980,с.62-65.

13.Скобцов Ю.А.Временные булевы.дифференциалы и их применение в диагностике последовательностях схем//Труды 4-й международной

конференции "Диагностика и обеспечение цифровых систем",Брно, 1981. -с. 138-141.

14.Скобцов Ю. А.'.Шатохин П.А.Вариационные логические модели цифровых микросхем//Труда международной конференции "Микроэлектроника -84 ",Прага,1984.-С.166-168. 15.Скобцев В.А..Шатохин П.А..Булавина Т.В.Функциональная троичная модель микропроцессора/ТМатериалы конференции"Контроль изделий микроэлектроники и применение микропроцессорных средств вычислительной техники",Цахквдзор. 1984.-с.63-64. 16.Skobtaov Ju. .A.Checklng test generatlon Юг asynchronoua clr-culta//Proc.or 7 Int.Coní.Fault-tolerant systems and.diagnostica .Sofía, 1984. -p. 141 -144. 17.Скобцов Ю.А.,Шатохин П.А.Логические модели арифметических функций в троичном алфавите//Труды 8-й международной конференции "Системы,допускащие неисправности и диагностика",Катовице,

1985.-с.167-173.

18.Skobtsov Ju.A.Boolean dlfferentlal calculas and teimry loglc// Proc.of 9 Int.Coní.Fault-tolerant systems and.dlagno3tlc3,Brno,

1986. .-p.148-153.' .

19.Скобцов D.А.,Шатохин П.А..Булавина Т.В.Построение функциональной' логической модели микропроцессора в троичном алфавите// Электронная техника.Сер.Управление качеством,стандартизация, метрологические испытания,1986,вып.2(119).-с.153-176. 2 0 ¿Богомолов А.М..Сперанский Д.В.Аналитические методы в задачах контроля и анализа дискретных устройств.-Саратов:Изд.Саратовского ун-та,1985.-240с. (гл.6 написана D.А.Скобцовым). 21.Скобцов D.А. .Шатохин П.А.Троичные логические модели МЕЮ на фун-кционалыюм уровне//Многопроцессорные вычислителыше структуры, Таганрог:Изд.ТРТИ,1986,вып.8{111).-с.61-63.

22.Скобцов 13.А.Модели основных операторов языков регистровых передач для различных методов кодирования троичного алфавита// Материалы VI Всесоюзною™ совещания по технической диагностике', Ростов-на-Дону,1987.-М.:Изд.Ин-та проблем управления,1987.-

с. 17.

23.Скобцов С.А.Троичные функции и булевы дифференциальные операто-ры//Теория управляющих систем.-Киев:Наукова думка,1987.-с Л26-140.

24.Скобцов Ю.А..Пономаренко Г.Г.,Шатохин П.А.и др.АСМВД-автомати-зированная система моделирования и диагностики цифровых блоков //Теория управляющих систем.-Киев:Наукова думка, 1987.-с. 140-157.

'25.Скобцов С.А.Многозначные логики в моделировании и построении тестов//Материалы республиканской научно-технической конференции "Проблемы диагностирования микропроцессорных систем", вып.1.Ужгород,1987.-с.9-11.

26.Скобцов В.А.,Шатохин П.А..Булавина Т.В.Функциональная троичная модель микропроцессора// Материалы республиканской научно-технической конференции "Проблемы диагностирования микропроцессорных систем",вып.1,Ужгород,1987.-с.8-9.

27.Скобцов Ю.А.Модели операторов языков регистровых передач для различных методов кодирования троичного влфавита//Автоматика и вычислительная техника,1988.-N1.-с.79-86.

28.Скобцов Ю.А.Применение многозначных алфавитов в моделировании и построении тестов//Методы и системы управления вычислительно-измерительными комплексами.-Саратов:Изд.Саратовского ун-та, 1988.ВЫП.9.-с.99-100.

29.Скобцов Ю.А..Пономаренко Г.Г..Шатохин П.А.и др.Система моделирования и построенеия тестов АСМИД// Метода и системы упряле-ния вычислителъно-измерительннми комплексами.-Саратов:Изд.

- 41 -

Саратовского ун-та,1988.вып.9.- с.137-138.

30.Скобцов D-А..Шатохии П.А.Троичные модели операторов языков регистровых передач//Автоматика и телемеханика,1988.-N2.-с.160-172.

31.Скобцов С.А..Пономаренко Г.Г.,Шатохип П.А.и др.Автоматизированная система моделирования и диагностики цифровых устройств//

Управляющие системы и машины, 1988.-N2.-c.11 -1 6.

!?.:>kol)tnov Yu.A.Ternary functional modela lor operators oî ге-Klaler-tranaler languages // Ргос.оГ 11 Int.Conr.?ault-tolerant аузtem3 and.dlagnostles,Suhl,1988,1988.-p.272-277.

.33.Скобцов П. А.Многозначные алфавиты в моделировании и построении тестов цифровых устройств//Электрошюе моделирование,1989.-N3.-с.54-60.

34.Скобцов Ю.А.Моделирование в многозначных алфавитах на функциональном уровне//. Материалы республиканской научно-технической конферешцш "Автоматизация контроля вычислительных устройств и систем",Винница,1988.-с.145-146.

35.Скобцов D.А.Единая система многозначных алфавитов для моделирования и генерации тестов цифровых устройств // Труда 12-ой международной конференции " Системы, допускающие неисправности и диагностика".Прага,1989.-с.360. .

36.Скобцов Ю.А. Приложение булевого диф1еренциалыюго исчисления к диагностике дискретных устройств // Труды семинара по дискретной математике и ее приложениям.-М.:Изд.МГУ,1989.-с.292.

37.Скобцов Ю.А.Единая система многозначных моделей для построения тостов и моделирования цифровых устройств//Мотоды и системы технической диагностики.-Саратов:Изд.Саратовского ун-та, 19'jO, вып. 1-1, часть 1. с.120-121. ■

38.Скобцов D. А.Булево дифференциальное исчисление и многозначные лопши//Теория и моделирование управляющих систем.-Киев:Наукова думка,1989.-с.56-65.

. 39.Скобцов D.A..Копытова О.М.,задорожная Л.В. Генерация тестов для комбинационных и последовательности схем. методом критических путей//Теория и моделирование управляющих систем.-Киев: Наукова думка,1989.-с.65-75.

40.Skobtsov Yu.A..Speranskiy D.V.Simulation of the digital devices for problems of' the tehnical diagnostic // G1-20. Tahrestagung I. Informatik auf dem lieg zum Anwender,Stuttgart,8-12,Oktober, 1990.-p.484-491. • *

41.Скобцов D.А.Моделирование и генерация тестов в многозначных алфавитах// Материалы Всесоюзной конференции " Диагностирование, неразрушающий контроль электронных устройств и .систем" , Владивосток, 1990.-с.73. .

42.Скобцов D.A. Построение тестов в многозначных алфавитах // Теория и моделирование управляющих систем.-Киев:Наукова думка, 1991 .-С.96-102 •....'

43.Барашко A.C..Скобцов Ю.А.,Сперанский Д.В.Моделирование и тестирование дискретных устройств.-Киев:Наукова думка, 1992.-28бс.

44.Скобцов D.А.Методические указания к проведению курса технической диагностики цифровых-систем-Донецк:Изд.Донецкого ун-та, 1992.-40с.

45.Скобцов.С.А.Генерация тестов в 16-значном алфавите//Методы и средства технической ди8гностики:Матерйалы Межвузовской школы-семинара ,Ивано-Франковск,1992.-с.58-61.

Личный вклад автора. В монографии [201 автором написана шестая глава(о Чем указано в предисловии). В монографии [43]-первая , вторая и третья глава.В работах [4,40] автору принадлежит доказательство части утверждений.В работах [24,29,31] автором разработана архитектура системы и основные методы моделирования . В других работах автору принадлежит математическая постановка,формулировка и основные идеи и доказательства методов и их решений,остальные результаты получены совместно.

Подписано в пвчатЬ 07.10.93.Формат 60184/16.Бумага типографская. -

Офсетная почать.Усл.п.л.2,0

Тираж 100 экз.Заказ .Босплатпо.

340114.г.Допецк.ул.Розы Лшсомбург.74

ДИАПП.340050.Доноцк,ул.Артема.ЭС