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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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