Содержание к диссертации
Введение
ГЛАВА I. ИССЛЕДОВАНИЕ МЕТОДОВ.СИНТЕЗА.ТЕСТОВ.ДЛЯ ЦИФРОВЫХ СХЕМ. 9
1.1. Основные понятия 9
1.2. Критический обзор существующих,методов.синтеза.тестов. .13
Выводы 24
ГЛАВА 2. ПРЕДСТАВЛЕНИЕ ОБЪЕКТА ДИАГНОСТИРОВАНИЯ МАТЕРНАТИВНЫМИ ГРАФАМИ 25
2.1. Понятие альтернативного графа 25
2.2. Синтез функциональных. АГ методом разложения. булевых функци 30
2.3. Структурный подход к синтезу АГ 31
2.4. Основные свойства модели АГ 35
2.4.1. Структурные свойства АГ 35
2.4.2. Эквивалентные преобразования АГ 36
2.4.3. Инвертирование АГ 41
2.5. Переход от модели САГ к модели ФАГ 42
2.6. Модель АГ для последовательностных схем 48
2.6.1. Представление временного параметра в АГ 48
2.6.2. Модель ЦУ с элементами памяти 49
2.6.3. Модель.ЦУ с обратными связями 52
Выводы 55
ГЛАВА 3. СИНТЕЗ ТЕСТОВ ЦИФРОВЫХ УСТРОЙСТВ НА МОДЕЛИ АЛЬТЕРНАТИВНЫХ. ГРАФОВ...56
3.1. Основы синтеза тестов на модели САГ 56
3.2. Активизация на ЦУ путей с различной.мерностью .59
3.3. Синтез тестов на системе САГ 64
3.4. Анализ компенсации неисправностей на АГ 68
3.5. Синтез тестов для последовательностных схем 79
З.б. Выявление, состязаний, на. АГ 85
Выводы 89
ГЛАВА 4. СИНТЕЗ ТЕЗТОВ МОДУЛЬНЫМ ПОДХОДОМ 90
4.1. Вопросы синтеза тестов модульным подходом ...90
4.2. Трансляция.выходных.реакций.многовыходного модуля на ТЗДГ 92
4.3. Синтез.локальных.тестов модуля при переходе от.САГ .
4.4. Групповая активизация.множества функционально зависимых выходов 105
Выводы 112
ГЛАВА 5. РЕАЛИЗАЦИЯ И ЭКСПЕРИМЕНТАЛЬНЫЕ ДАННЫЕ 113
5.1. Машинное представление и обработка модели АГ
5.2. Внедрение, и. экспериментальные данные
Выводы
ЗАКЛЮЧЕНИЕ
ЛИТЕРАТУРА
ПРИЛОЖЕНИЕ
- Критический обзор существующих,методов.синтеза.тестов.
- Понятие альтернативного графа
- Основы синтеза тестов на модели САГ
- Вопросы синтеза тестов модульным подходом
- Машинное представление и обработка модели АГ
Введение к работе
Актуальность, .темы. В настоящее время необходимым условием развития науки и ускорения технического прогресса является широкое внедрение вычислительной техники и других цифровых устройств (ЦУ) самого разнообразного назначения во все сферы народного хозяйства. Наряду с разработкой новых высокоэффективных ЦУ в этих условиях все большую актуальность приобре- , тают задачи их контроля и диагностирования, чтобы обеспечить высокий коэффициент их эксплуатационной готовности. Одним из путей решения этой важнейшей для эффективного использования дискретной техники задачи является разработка и применение автоматизированных систем тестового контроля и диагностирования, в которых по заданному формальному описанию устройства автоматически строятся наборы тестовых воздействий, а после подачи их на входы проверяемого устройства и снятия ответов определяется его техническое состояние и, в частности, место появления неисправности. Центральной и более трудоемкой задачей при разработке таких систем является решение задачи синтеза тестовых воздействий. Сложность этой задачи связана в основном с необходимостью обработки большого количества информации, объем которой постепенно возрастает в связи.с усложнением и повышением степени интеграции элементной базы ЦУ. В связи с этим большое значение имеет разработка новых методов, позволяющих строить тесты для современных ЦУ широкого класса с приемлемыми затратами ручного труда и машинных рессурсов. . Целью работы является разработка и исследование методов синтеза тестов ЦУ на основе модели альтернативных графов. Достижение поставленной цели требует решения следующих задач: - критическая оценка существующих методов синтеза тестов и определение перспективности синтеза тестов на основе модели альтернативных графов (АГ); разработка способов представления ЦУ в виде структурных и функциональных АГ (САГ и АГ) и определение области их применения ;в. задачах синтеха тестов} разработка методики синтеза тестов для проверки структуры ЦУ на „основе модели САГ; развитие методов синтеза тестов на основе принципов т.н. модульного подхода с разработкой способа перехода от структурной к функциональной модели АГ.
Основные методы исследования. При решении поставленных задач используется аппарат теории множеств, теории графов и дифференциального исчисления булевых функций.
Новые научные результаты: . I. Разработаны методы формального синтеза структурных и функциональных АГ на основе принципиальных схем ЦУ. Определены основные свойства структурной модели и предложен способ перехода от структурного альтернативного графа к функциональному.
2. Впервые поставлена и решена задача синтеза тестов для проверки структуры ЦУ на основе модели САГ.
, 3. Предложен алгоритм синтеза парных тестов ЦУ, при котором, в отличие от известных методов, активизация в схеме простых и сложных путей имеет примерно одинаковую сложность. Разработаны метод синтеза парных тестов, нечувствительных к компенсации неисправностей, а также способ выявления статических и динамических состязаний на модели САГ.
4. Разработаны методы решения задач обеспечения, синтеза локальных тестов и транспортировки, возникающих при модульном подходе, которые вместе со способом перехода от структурного АГ к функциональному создают условия построения тестов для сложных ЦУ путем комбинирования структурного и функционального подходов.
Предложена структура данных для машинного представления системы АГ в ЭВМ и организация ее обработки для реализации алгоритмов, синтеза тестов.
Апробировано применение разработанной в СКВ вычислительной техники Института кибернетики АН ЭССР системы синтеза тестов на основе предложенных методов. Установлено быстродействие синтеза тестов на основе модели АГ.
Практическая ценность работы состоит в разработке методики и алгоритмов синтеза тестов для проверки структуры ЦУ на основе модели САГ, а также в решении задач синтеза тестов модульным подходом на модели АГ. Характерными при синтезе тестов на модели альтернативных графов являются большая компактность модели и машиноориентированность ее обработки, что создают основу для разработки быстродействующих алгоритмов синтеза тестов. Апробация комплекса программ, разработанного в СКВ ВТ ИК АН ЭССР на основании созданной в рамках настоящей работы методики, подтвердила эффективность и быстродействие синтеза тестов на основе модели АГ.
Реализация результатов. Диссертационная работа выполнена в рамках направлении НИР Таллинского политехнического института по координационным планам республиканского комплекса научно- технического прогресса ЭР.05 "Микропроцессорные системы автоматизации и вычислительные средства" и Минвуза СССР "О совместных НИР в области вычислительной техники" (постановление АН СССР и MB СССР В 1473/146 от 29.12.80/31.12.80).
Научные результаты диссертационной работы использованы при разработке автоматизированной системы контроля цифровых схем в СКВ вычислительной техники Института кибернетики АН ЭССР в рамках выполнения договорных НИР ХО-403 "Разработка системы диагностических тестов для малой ЦВМ" от 1976-1980 и Х0-І0І "Исследо- вание и разработка методов технического диагностирования ЦУ, построенных на малых и средних ИС" от I98I-I983, заключенных между ОКБ ВТ ЙК АН ЭССР и Таллинским политехническим институтом. Общий экономический эффект от внедрения методики синтеза тестов в рамках названных НИР в 1976-1983 гг. составляет 233 тыс, рублей. Результаты диссертационной работы внедрены в Таллинском научно-учебном центре СНПО "Алгоритм" (установленный годовой экономический эффект составляет 37,4 тыс, рублей в год), а также используются в Таллинском политехническом институте в составе автоматизированной системы контроля цифровых схем в учебном процессе при проведении лабораторных работ. Соответствующие акты внедрения научных результатов приложены к диссертации.
Апробация работы. Основные положения диссертационной работы докладывались автором на: ... - Седьмом и восьмом.Всесоюзных совещаниях по проблемам управления (Минск, 1977 г., Таллин, 1980 г,);
24-ой Международной научной конференции Высшего технического училища г. Ильменау (ГДР, 1979 г.)}
Республиканской научно- технической конференции ЭРСП НТОРЭС им, Попова (Таллин, 1980 г.);
Постоянно действующем семинаре "Теория проектирования дискретных устройств" в ТПИ (Таллин, 1977-1984 гг.).
Публикации .По теме диссертации опубликовано 8 печатных работ.
Структура и объем работы. Диссертационная работа изложена на 138 страницах машинописного текста, иллюстрируется рисунками и таблицами на 20 страницах и состоит из введения, пяти глав, заключения, списка литературы из 85 наименований и приложения на 3 страницах.
Содержание работы, В первой главе вводится
8 основные понятия, дается критический обзор существующих методов синтеза тестов и обосновывается перспективность синтеза тестов.. на основе модели- альтернативных графов. Во второй главе излагаются методы построения.структурных и функциональных AF для представления заданного ЦУ. Определяются основные свойства структурной модели и предлагается способ перехода от структурного АГ к функциональному, В третьей главе предлагается представление неисправностей и разрабатывается принцип синтеза структурных тестов ЦУ на модели САГ, Предлагается алгоритм синтеза парных тестов ЦУ на модели САГ, при котором, в отличие от известных методов, активизация в схеме простых и сложных путей имеет примерно одинаковую сложность. Анализируются вопросы компенсации неисправностей и предлагается способ синтеза парных тестов, нечувствительных к компенсации неисправностей, а также способ выявления статических и динамических состязаний на модели САГ, В четвертой главе рассматриваются вопросы, связанные с применением т.н. модульного подхода к синтезу тестов ЦУ и предлагаются методы для решения этих задач, основывающиеся на разработанный способ перехода от структурного АГ к функциональному, что создает условия построения тестов для сложных ЦУ путем комбинирования структурного и функционального подходов. В пятой главе предложена структура данных для машинного представления системы АГ в ЭВМ и организация ее обработки для реализации алгоритмов синтеза тестов. Приводятся некоторые данные о реализации и практическом применении разработанной методики синтеза тестов. В приложении приведены акты о внедрении результатов настоящей диссертационной работы.
Диссертационная работа выполнена на кафедре ЭВМ Таллинского политехнического института под научным руководством академика ЭССР, профессора Б.Г. Тамм. Большую помощь при выполнении данной работы оказал также доцент кафедры ЭВМ к.т.н. P.P. Убар.
Критический обзор существующих,методов.синтеза.тестов
Техническая диагностика является отраслью знаний, включающей в себя теорию и методы организации процессов диагноза, а также принципы организации процессов диагноза для объектов технической природы Xl] Наиболее универсальной областью технической диагностики, предназначенной для диагностирования устройств разных видов, является тестовое диагностирование. В общих чертах тестовое диагностирование цифровых устройств (ЦУ), предназначенных для обработки дискретных сигналов, предполагает построение входных, т.н. тестовых воздействий, позволяющих обнаружить неисправности устройства, и последующую дешифрацию результатов, получаемых от устройства в ответ на тестовые воздействия. 3 настоящей работе рассматривается задача синтеза тестовых воздействий (далее тестов) для диагностирования ЦУ.
В зависимости от свойственного им закона функционирования цифровые схемы разделяют на комбинационные и последовательност-ные. Схема называется комбинационной (КС), если ее выходные переменные 5ЕК е ZBOX описываются булевыми функциями f e F только от входных переменных Не ZBX :
Самым простым видом КС являются бесповторные (древовидные) КС, где каждая переменная подается только на один вход какого-либо элемента ЦУ, а выход каждого элемента связан не более чем с одним входом другого элемента. Общим случаем КС являются КС с разветвлениями, где требования бесповторности не выполнены.
Понятие альтернативного графа
Доказательство. Установим соответствие между АГ GU CM , ) и некоторой булевой функцией Ягь-$к (ZK) путем сопоставления каждой вершине ht е Ми определенной булевой переменной 2-, ZK j называется весовой переменной вершины VnL , z(Vvu)-2j . Значение весовой переменной &(VY\L) є {0,4} рассматривается как параметр движения efi u) для выбора последователя Г( с)е вершины L . Значению еОп М условно сопоставляется дуга, исходящая из KVIC направо, а значению eOvO=0 _ дуга, исходящая из rvu вниз. Если все вершины с е М взвешены переменными 2j є ZV , то каждый набор однозначно определяет на ZK некоторый путь Гы е,-) , где nw - начальная вершина графа, \ (VnH)= 0 , а Є/ = = eC«rvtj) - направление выхода из конечной вершины этого пути tn-. , r 0nQj)ej = 0 , что соответствует выходу из графа. Если аналогично параметру движения выходу из графа направо сопоставить значение I, а выходу вниз - значение 0, то значение є,- = {0,1} является значением функции гк на этом наборе Z p . Определяя таким же образом значение 2К на всех наборах ZKP , можно найти булеву функцию, реализованную данным АГ при заданном взвешивании вершин АГ булевыми переменными.
АГ, содержащий q, вершин, по сути дела представляет Q. различных булевых функций одновременно, ибо выбор каждой из этих Cfy вершин в качестве новой начальной вершины т" сопровождается появлением новых функций. Описанное свойство АГ оказывается выгодным для сокращения объема модели при првдставлении ЦУ определенных типов, в частности, многовыходного функционального модуля [72J . В дальнейшем, если это не оговорено отдельно, под функцией, реализуемой некоторым АГ GK t понимается функция 2К= -fK (Z .) начинающаяся с начальной вершины АГ т4 , Г ЧЪУЛ ) = Для представления заданной булевой функции 2 - Jk f ZO , содержащей переменные с инверсией и без нее, необходимо установить соответствие между значением весовой переменной г (Vnc)є Є f 0,1} и параметром движения efrvO . Для этого к вершинам тс прикрепляется признак инвертирования 3( ) , определяемый следующим образом.
Основы синтеза тестов на модели САГ
Решением уравнения (3.2) определяются условия, при которых изменение значения переменной 25с влечет изменение значения функции 2к при неизменявщихся значениях остальных переменных. На АГ GK t представляющем функцию ZK , решение уравнения (3.2) выполняется активизацией Q относительно вершины KYH ,2(тс.)=2г. , Определение 3.1. Q«. называется активизированным относительно вершины шщ , если на QK активизированы начальный путь (VnH, mi) , I- конечный путь (Г(гщ)Л; 0 и 0- конечный путь
Набор значений переменных 2,- е ZK , активизирующий вышеприведенные пути, назовем активизирующим набором Zc$K)r - 0 .
Активизация GK относительно тс представлена на рис. 3.1. Здесь вершина hn может быть рассмотрена как переключатель: в зависимости от приписываемого Zc значения и исправности/ неисправности hnc "коммутируется" один из двух активизированных в разных направлениях конечных путей, а появляющееся в результате этого значение функции zK позволяет судить об исправности вершины тс .
Уравнение (3.2) описывает задачу синтеза как одиночного теста (если под 2с =1(0) понимается исправное, а под Zi =0(1) - неисправное значение переменной Zi ), так и парного теста ( Zc =1 и Нг =0 задают исправные значения переменных на двух последовательных наборах, а любая неисправность 2сн1 или 2с= 0 фиксирует на обоих тестовых наборах одинаковое значение 2Ks , o, ={CU} . Таким же образом активизацией АГ 3К относительно vr\i, может быть проведен синтез как одиночных, так и парных тестов. В настоящей работе далее особое внимание уделяется синтезу парных тестов TChnO , позволяющих определить исправность переменной 2(, [7б] .
Вопросы синтеза тестов модульным подходом
Рассмотрим задачу синтеза тестов ЦУ модульным подходом на схеме ЦУ, разделенной на ъ последовательно соединенных модулей (согласно [ві] , каждая схема ЦУ может быть преобразована в такой вид, в частности, добавлением транспортных фцнкций моду-лей). Каждый модуль Ні имеет множество входов мс =\т и мс/, 7Вх -_ ПВх у Вое где гСмс - множество первичных ВХОДОВ И Zvit, =ZMO множество псевдовходов модуля Мо .Ми реализует h6 выходных функций, ZMC =fec 2o2 , г :«0 , 2o =f ск (ZMC } ,
Общий принцип модульного подхода, направленного на расширение области схем, тесты для которых могут быть построены структурными методами, заключается в следующем. Для выделенного в схеме модуля Мс строится локальная тестовая последовательность W(ML)-WI(MC) , , Ws(Mc) независимо от остальной части схемы. Чтобы провести проверку модуля Мс в условиях доступности только первичных входов и выходов устройства, необходимо решить следующие задачи: I) задача обеспечения, позволяющая подавать на входы Мс набор 1л/р (Мс)є W(Mc) через первичные входы схемы, и 2) задача трансляции, позволяющая наблюдать выходные реакции модуля Иг на первичных выходах устройства.
Эти задачи могут быть выполнены как на моделях САГ, так и на ФАГ, ибо при их решении отсутствует необходимость представления в модели структурных неисправностей. Сказанное является основой предлагаемого в разделе 4.3 метода синтеза локальных структурных тестов модуля, выполняемого одновременно с переходом с модели САГ на модель ФАГ.
Машинное представление и обработка модели АГ
Система АГ представляется в виде двух символьных таблиц: таблицы графов (ТГ) и таблицы оглавления графов (ТОГ).
Для представления АГ Сдк СМк.Пс) в ЭВМ вершины АГ пронумеровываются таким образом, чтобы номер вершины иа не был меньшим, чем номера ее предшественников f CWO . Вершины АГ ысе G Ик представляются в ТГ в последовательности их порядковых номеров, и эти номера используются для ссылки на вершины АГ.
ТГ для представления АГ Gtc (Н Гк) состоит из К строк, где К ІМкІ . Каждой вершине Ьос соответствует определенная сторка с номером , ие{ к] 9 где - порядковый номер вершины \с в QK . В каждой строке и содержатся следующие данные:
1) ВЕРШ - весовая переменная (W\c) = c вершины с
с порядковым номером И
2) УКАЗ - указатель на строку ТОГ, соответствующую АГ ?с=(Мо,Гс) , если Zrc не является входным переменным схемы. В противном случае кодируется О.
3) НАПРАВО ОЛ - порядковый номер правого последователя вершины Нас ,
4) ВНИЗ Е 1 - порядковый номер нижнего последователя вершины hie , Г(і с)
5) ИНВ - признак инвертирования весовой переменной &і
б) ЗАЛ - признак запаздывания.:сигнала в вершине Илс (О, если значение 2с принимается на данном такте, и І, если значение 2-е принимается на предыдущем такте).
По необходимости в ТГ можно ввести дополнительные признаки для вершины іс (например, признаки для различных видов синхросигнала и т.д.).
По сути дела, структура ТГ для представления АГ соответствует структуре двоичного расширенного дерева Г83І , ибо каждая вершина с порядковым номером \г\ представлена триадой (ВЕРШ ьл 1 , НАПРАВО L ol , ВНИЗ СюД ), соответствующей заданию корневой вершины, правого и левого поддеревьев соответственно, и определенным расширением (УКАЗЕ Д , ИНВ L l , ЗАпЦиЗ ), задающим характеристику корневой вершины. Организованная указанным способом символьная таблица может быть произвольно расширена и является легко доступной для поиска, что в итоге увеличивает быстродействие алгоритмов обработки АГ, в частности алгоритмов синтеза тестов на модели АГ.
