Оптимизация количества выходных полюсов комбинационных устройств на основе диагностической информации Гольдштейн Виталий 5 курс 511 группа КНиИТ Научный руководитель: Миронов С.В.

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

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

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

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

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

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

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

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

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

Алгоритм распознавания Будем последовательно добавлять столбцы (тесты) в ТС и элементы в множество S, а рассматривать отличимость только на добавленных столбцах. То есть после добавления r столбцов и добавления некоторых элементов в множество S будем считать строки различимыми, если выполнено условие:

Добавление первого столбца Изначально положим множество S пустым. При пустом S все строки неотличимы. В ТС изначально не будет ни одного столбца. Добавим первый столбец. Рассмотрим два случая: 1. Все элементы столбца одинаковые и равны a. Тогда добавление числа a в множество S не изменит ситуации, при которой все строки неотличимы. 2. В столбце есть хотя бы два разных числа. В этом случае добавим все различные числа в множество. Это приведет к разбиению наших строк на несколько классов. Количество классов будет равно количеству различных чисел в первом столбце.

Добавление очередного столбца Выпишем все числа, стоящие в i-ом столбце и строках, соответствующих классу. Аналогично первому столбцу, рассмотрим два случая: 1. Выписанные числа одинаковые и равны. Тогда добавление числа в множество не приведет к разбиению рассматриваемого класса. Поэтому не будем добавлять это число в множество. 2. Среди выписанных чисел есть хотя бы два разных числа. В этом случае добавим все различные числа в множество. Это приведет к разбиению выбранного класса на несколько.

Оценка эффективности алгоритма Алгоритм распознавания позволяет получить схему с не более, чем выходными полюсами. Алгоритм распознавания работает за время O(NK) и требует O(N) памяти.

Примеры N Измененная ТС f(a) = a mod 2 Пример с одним выходным полюсом Пример с одним тестом

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

Сведение к раскраске графа Достаточным условием того, что диагностическая f функция, является Рассмотрим неориентированный граф, в котором вершинами являются элементы множества S. Ребрами соединены такие вершины a и b, что по условию. Задача сводится к раскраске графа, а функция является f функцией Гранди. Таблицей может быть задан граф любой структуры, в котором не более 2N вершин и не более ребер.

Апробация Названи е схемы Перену мерация Распозн авание Раскраск а графа c17333 c c c c c c c Назван ие схемы Количес тво выходов Перен умера ция Распо знава ние Раскр аска графа c c c c c c c c Количество выходных полюсовМаксимальное значение функции

Время работы Название схемы Перенум ерация Распозна вание Раскраска графа c17000 c c c c c c c