Разработка и исследование методов и алгоритмов построения тестов последовательностных схем на основе непрерывного подхода

• Автор: Данилов, Сергей Олегович
• Шифр специальности: 05.13.01
• Научная степень: Кандидатская
• Год защиты: 2004
• Место защиты: Нижний Новгород
• Количество страниц: 158 с. : ил.

СОДЕРЖАНИЕ
ВВЕДЕНИЕ.

ГЛАВА 1. АНАЛИЗ ПРОБЛЕМЫ ГЕНЕРАЦИИ ТЕСТОВ ДЛЯ СИНХРОННЫХ ПОСЛЕДОВАТЕЛЬНОСТНЫХ СХЕМ

1.1. Виды неисправностей логических схем

1.2. Существующие методы и алгоритмы тестирования последовательностных схем.

1.2.1. Функциональные подходы.

1.2.2. Эвристические методы.

1.2.3. Подходы, подразумевающие известное начальное состояние схемы.

1.2.4. Контролепригодный сканируемый дизайн схемы.

1.2.5. Методы высших уровней абстракции.

1.3. Сложность проблемы генерации тестов

Выводы и постановка задачи
ГЛАВА 2. РАЗРАБОТКА НЕПРЕРЫВНОГО ПОДХОДА К ТЕСТИРОВАНИЮ СИНХРОИЫХ ПОСЛЕДОВАТЕЛЬНОСТНЫХ СХЕМ
2.1. Общая структура взаимодействия разработанных алгоритмов
2.2. Необходимые определения
2.3. Алгоритмы преобразования последовательностной схемы в итеративный логический массив.
2.4. Используемая в работе модель неисправностей
2.5. Подход к поиску тестовых последовательностей путем поиска максимума построенной непрерывной целевой функции.
2.6. Непрерывная целевая функция для задачи поиска тестовой
последовательности
2.7. Сложность целевой функции.
Выводы.
ГЛАВА 3. ИССЛЕДОВАНИЕ ЭФФЕКТИВНОСТИ МЕТОДОВ ЛОКАЛЬНОЙ ОПТИМИЗАЦИИ ПРИМЕНИТЕЛЬНО К ЗАДАЧАМ ПОИСКА ТЕСТОВ.
3.1. Объект и методы исследования
3.2. Исследование алгоритмов на примере схемы э
3.3. Исследование алгоритмов на примере схемы э4.
3.4. Исследование алгоритмов на примере схемы
ГЛАВА 4. МЕТОДЫ ПОВЫШЕНИЯ ЭФФЕКТИВНОСТИ ПОИСКА ТЕСТОВ
4.1. Вычисление количества предваряющих и замыкающих временных кадров.
4.2. Сортировка неисправностей в списке.
4.3. Заморозка схемы
4.4. Анализ нетестируемых неисправностей
4.5. Алгоритмы моделирования неисправностей.
4.5.1. Моделирование неисправностей на очувствленном пути
4.5.2. Полное моделирование неисправностей
4.5.3. Моделирование с доопределением значений
4.5.4. Адаптивное моделирование неисправностей
4.6. Пакетное тестирование
4.7. Адаптивное изменение величины начального шага
4.8. Фантомные мнимые первичные входы.
4.9. Контроль первого вектора
4 Исследование зависимости покрытия и быстродействия алгоритма от значения неопределенного сигнала на линии.
4 Сравнение алгоритма с существующими алгоритмами 6 Выводы.
ЗАКЛЮЧЕНИЕ
БИБЛИОГРАФИЧЕСКИЙ СПИСОК.
СПИСОК СОКРАЩЕНИЙ
ПРИЛОЖЕНИЕ. ГРАММАТИКА ДЛЯ ФАЙЛОВ ОПИСАНИЯ СХЕМЫ И НЕИСПРАВНОСТЕЙ.
ВВЕДЕНИЕ
Актуальность


Рассматриваются эффективные алгоритмы обработки непрерывной целевой функции. В третьей главе проводится экспериментальное сравнение эффективности методов Розенброка, Хука-Дживса, Нелдера-Мида и покоординатного подъема в области поиска максимума непрерывной целевой функции для вычисления тестовой последовательности векторов. Приводятся экспериментальные результаты эффективности данных алгоритмов и их сравнение между собой. Также приводятся результаты серии экспериментов, направленных на исследование эффективности разработанных алгоритмов в зависимости от величины, выбранной в качестве значения неопределенного сигнала на линии. В приложении приводятся грамматики для файлов описания схем и неисправностей в формате СА8’, приводится описание простейшей схемы из тестового набора СА8’ и ее графическое представление. ГЛАВА 1. Свыше трех десятилетий тому назад автоматические генераторы тестовых векторов впервые построили тестовые наборы для цифровых систем. В то время большинство систем состояло из дискретных компонентов, и еще только начиналась эра первых коммерческих интегральных микросхем. Для тех первоначальных интегральных схем построение тестовых векторов проводилось вручную, так что для автоматического генератора тестов проблема построения тестовых векторов для всей схемы не представляла никакой сложности. Тем не менее, в связи с большим числом интегральных схем, составляющих систему, была актуальна проблема поиска тестовых наборов для всей системы. Еще в г. П. Пархоменко: «Одним из необходимых путей поддержания требуемого уровня надежности устройств в процессе их эксплуатации или хранения является контроль работоспособности и поиск неисправностей в них». Он отмечал, что «внедрение в инженерную практику формальных методов определения совокупностей воздействий имеет большое значение». Основная цель технической диагностики состоит в определении технического состояния различных, в первую очередь очень сложных изделий, устройств и систем. Техническую диагностику можно определить как совокупность идей, связанных с организацией оптимальных процедур проверки технического состояния сложных объектов, постановок возникающих при этом проблем и задач, методов и средств решения этих проблем и задач, а также методов и средств технической реализации указанных процедур []. С момента изобретения интегральной схемы в г. В настоящее время количество вентилей в интегральной микросхеме достигает значения нескольких миллионов. В связи с этим, автоматические генераторы тестовых векторов являются необходимым инструментом для построения тестов на уровне микросхемы, а задача построения тестов для всей системы является практически неосуществимой. К сожалению, проблема генерации тестов для логических схем является NP-полной проблемой []. Тем не менее, на протяжении многих лет делаются многочисленные попытки найти практические решения данной проблемы. Проблема генерации тестовых последовательностей для последовательностных схем является особенно трудной в связи с недостатком контролируемости и наблюдаемости состояний внутри схемы [7]. В связи с этим, генерация тестовых последовательностей для последовательностных схем на протяжении нескольких десятилетий была ограничена рассмотрением только небольших схем, имеющих заранее определенные характеристики. Такие схемы были простыми для тестирования. Данные ограничения на вид и строение схем привели к развитию целого направления в тестировании, подкрепленного требованиями к проектированию схем - т. Последовательное сканирование переводит последовательностную схему на время тестирования в комбинационный вид для того, чтобы упростить задачу поиска и приложения тестов к данной схеме. Это позволило разработать реально работающие на больших последовательностных схемах алгоритмы поиска тестов. В связи с этим, значительно вырос интерес к более эффективным алгоритмам генерации тестов для комбинационных схем. Со времен создания первого автоматического генератора тестов было разработано много алгоритмов и инструментов для тестирования.