Автоматизированное формирование тестов при характеризации цифровых ячеек с использованием веб - доступа Лялинский Алексей Анатольевич ИППМ РАН Лялинский Алексей Анатольевич ИППМ РАН МЭС Подмосковье 8-12 октября 1

Область применения разработанного ПО МЭС Подмосковье 8-12 октября Аналоговые схемы 2

Постановка задачи МЭС Подмосковье 8-12 октября & Все возможные переходы состояний ячейки NAND2 Оптимальный набор переходов для построения входной тестовой последовательности f=!(a&b) 3

Введем ограничения на рассматриваемые переходы МЭС Подмосковье 8-12 октября & a) Выход ячейки при переходе должен переключаться

Обоснование : в противном случае имеем экспоненциальный рост количества отслеживаемых состояний ; реально только один сигнал приводит к переключению. Обоснование : в противном случае имеем экспоненциальный рост количества отслеживаемых состояний ; реально только один сигнал приводит к переключению. Введем ограничения на рассматриваемые переходы МЭС Подмосковье 8-12 октября & b) Только один вход ячейки может переключиться

Если все же выходов больше одного (n – число выходов ), то : Разбиваем схему на n подсхем, имеющих одинаковый набор входов и единственную логическую функцию выхода. Далее здесь возможна оптимизация полученных тестовых воздействий. Если все же выходов больше одного (n – число выходов ), то : Разбиваем схему на n подсхем, имеющих одинаковый набор входов и единственную логическую функцию выхода. Далее здесь возможна оптимизация полученных тестовых воздействий. Введем ограничения на рассматриваемые переходы МЭС Подмосковье 8-12 октября c) Ячейка может иметь только один выход … … Что дает : Существенное упрощение решения поставленной задачи, не изменяя при этом ее сути. Что дает : Существенное упрощение решения поставленной задачи, не изменяя при этом ее сути. 6

Математическая основа – граф состояний МЭС Подмосковье 8-12 октября Может состоять более чем из одного подграфа. Ориентированность графа. Степень любой вершины - четная Может состоять более чем из одного подграфа. Ориентированность графа. Степень любой вершины - четная Особенности графа : Входы Выход Переходы между состояниями Состояние 7

Цель – найти Эйлеров путь графа МЭС Подмосковье 8-12 октября Обеспечивает проверку всех возможных переходов входных сигналов. Гарантирует их минимальное количество в тестовой последовательности. Обеспечивает проверку всех возможных переходов входных сигналов. Гарантирует их минимальное количество в тестовой последовательности. Что это дает : Эйлеров путь графа проходит через ВСЕ ребра графа и притом только по ОДНОМУ разу. 8

Условия построения Эйлерова графа МЭС Подмосковье 8-12 октября Согласно теореме Эйлера граф является Эйлеровым ( то есть содержит Эйлеров цикл ) тогда и только тогда, когда он связен, и все его локальные степени четны. Связность графа в целом гарантировать нельзя ( пример : f = a&b|c), поэтому разбиваем граф на локально связанные подграфы. Четность вытекает из комбинационного характера схемы – перейдя из одного состояния в другое мы можем сразу же вернуться обратно. 9

4 Последовательность действий МЭС Подмосковье 8-12 октября A.Создание графа ( или несвязанных между собой подграфов ) на основе множества состояний, удовлетворяющих ранее сформулированным условиям. B.Для каждого подграфа : выбирается стартовая вершина строится Эйлеров путь. C.Соединяем подграфы между собой дополнительно введенными ребрами

A. Разбиение графа на подграфы МЭС Подмосковье 8-12 октября На основе алгоритма Флойда – Уоршелла строится матрица достижимости на основе предварительно построенной матрицы инцидентности графа. Анализ структуры полученной матрицы достижимости позволяет легко выделить блоки связанных между собой вершин, составляющих отдельные подграфы. Сложность алгоритма оценивается как O(n 3 ), где n – число вершин графа, в нашем случае – количество состояний усеченного графа. Быстроту вычислений на данном этапе обеспечивает то, что основными операциями при работе данного алгоритма являются две простейших логических операции дизъюнкции и конъюнкции. abcdefg a1 b1 c11 d1 e11 f11 g1 abcdefg a11 b11 c11111 d11111 e11111 f11111 g

B. Выбор стартовой вершины МЭС Подмосковье 8-12 октября Выходной бит стартовой вершины данного подграфа должен иметь то же значение, что и выходной бит конечной вершины предыдущего подграфа. Для построения Эйлерова пути это не имеет никакого значения подграф n подграф n+1 Поэтому стартовая вершина выбирается из следующих условий : подграф n подграф n+1 Количество переключений входных битов должно отличаться на 1. 12

C. Построение Эйлерова пути МЭС Подмосковье 8-12 октября Волновой алгоритм – неудачен, так приходится хранить огромное количество промежуточных результатов. Проверены два алгоритма : Алгоритм поиска в глубину – оптимален, так как неудачные варианты сразу отбрасываются. 13

Практическая реализация МЭС Подмосковье 8-12 октября Алгоритм реализован на скриптовом языке PHP и размещен на серверной части Клиент Сайт Программа на сервере a&b|c запрос рез - ты Пользователь имеет интерактивный доступ к данной программе. разработанного сайта. специально 14

Сайт программы 15 МЭС Подмосковье 8-12 октября

Тестирование программы СхемаВыражениеКоличество входных переменных Количество переходов Количество «холостых» переходов nor2~(a|b) 240 and3a&b&c 360 and6a&b&c&d&e&~f 6120 and9~((~(a&b&c))|(~(d&e&f))|(~(g &h&i))) 9180 ao211(a&b)|c|d 4171 ao21i1(a&b)|~c|~d 4262 ao221(a&b)|(c&d)|e 5453 exnor2((a&b)|(~a&~b)) 240 mux2(d0&~sl0)|(d1&sl0) 3131 mux4(d0&~sl0&~sl1)|(d1&sl0&~sl1) |(d2&~sl0&sl1)|(d3&sl0&sl1) 6953 mx4(sl0&d0)|(sl1&d1)|(sl2&d2)|(sl3 &d3) half_sum_sa&~b&~ci|~a&b&~ci|~a&~b&c i|a&b&ci 3111 half_sum_coa&b&~ci|~a&b&ci|a&~b&ci|a& b&ci МЭС Подмосковье 8-12 октября

Схема and9 МЭС Подмосковье 8-12 октября 17

Схема a^~b&c МЭС Подмосковье 8-12 октября 18

Схема ao21i1 МЭС Подмосковье 8-12 октября 19

Выводы МЭС Подмосковье 8-12 октября Разработано математическое и программное обеспечение системы автоматизированного формирования входных тестовых воздействий, используемых при характеризации цифровых комбинационных ячеек. Показана высокая эффективность ее работы. Веб - доступ к системе можно получить на сайте 20

Спасибо за внимание ! МЭС Подмосковье 8-12 октября 21