📄Работа №193948
Тема: ПРОВЕРКА ИСПРАВНОСТИ ЧАСТИЧНО ПОСТРОЕННОЙ СХЕМЫ ПУТЕМ ВЫПОЛНЕНИЯ ОПЕРАЦИЙ НАД ROBDD-ГРАФАМИ
Тип работы
Магистерская диссертация
Предмет
информатика
Объем:
61 листов
Год:
2024
Просмотров:
35
4850
руб.
🛒 Купить работу
Не подходит эта работа?
Закажите новую по вашим требованиям
Узнать цену на написание
Закажите новую по вашим требованиям
Представленный материал является образцом учебного исследования, примером структуры и содержания учебного исследования по заявленной теме. Размещён исключительно в информационных и ознакомительных целях.
Workspay.ru оказывает информационные услуги по сбору, обработке и структурированию материалов в соответствии с требованиями заказчика.
Размещение материала не означает публикацию произведения впервые и не предполагает передачу исключительных авторских прав третьим лицам.
Материал не предназначен для дословной сдачи в образовательные организации и требует самостоятельной переработки с соблюдением законодательства Российской Федерации об авторском праве и принципов академической добросовестности.
Авторские права на исходные материалы принадлежат их законным правообладателям. В случае возникновения вопросов, связанных с размещённым материалом, просим направить обращение через форму обратной связи.
Настоящий учебно-методический информационный материал размещён в ознакомительных и исследовательских целях и представляет собой пример учебного исследования. Не является готовым научным трудом и требует самостоятельной переработки.
📋 Содержание
ВВЕДЕНИЕ 3
1 Постановка задачи 4
2 Основные понятия и определения 6
3 Функция В. А. Провкина для многовыходной схемы и её представление
ROBDD-графом 11
4 Исследование операций над однокоренными графами В. А. Провкина и их
интерпретация 14
5 Операции над однокоренными графами В. А. Провкина для сложной
булевой функции 23
6 Алгоритм поиска неисправностей в частично построенной схеме 27
7 Использованные инструменты и технологии 31
8 Демонстрация алгоритма на примере небольшой схемы 36
ЗАКЛЮЧЕНИЕ 44
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ И ЛИТЕРАТУРЫ 45
ПРИЛОЖЕНИЕ А Файл tern_V_inputs_spec.pla 46
ПРИЛОЖЕНИЕ Б Файл spec_by_spec_outputs.pla 48
ПРИЛОЖЕНИЕ В Файл spec_by_real_outputs.pla 50
ПРИЛОЖЕНИЕ Г Файл tern_V_inputs_real.pla 52
ПРИЛОЖЕНИЕ Д Файл real_by_real_outputs.pla 54
ПРИЛОЖЕНИЕ Е Файл real_by_spec_outputs.pla
1 Постановка задачи 4
2 Основные понятия и определения 6
3 Функция В. А. Провкина для многовыходной схемы и её представление
ROBDD-графом 11
4 Исследование операций над однокоренными графами В. А. Провкина и их
интерпретация 14
5 Операции над однокоренными графами В. А. Провкина для сложной
булевой функции 23
6 Алгоритм поиска неисправностей в частично построенной схеме 27
7 Использованные инструменты и технологии 31
8 Демонстрация алгоритма на примере небольшой схемы 36
ЗАКЛЮЧЕНИЕ 44
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ И ЛИТЕРАТУРЫ 45
ПРИЛОЖЕНИЕ А Файл tern_V_inputs_spec.pla 46
ПРИЛОЖЕНИЕ Б Файл spec_by_spec_outputs.pla 48
ПРИЛОЖЕНИЕ В Файл spec_by_real_outputs.pla 50
ПРИЛОЖЕНИЕ Г Файл tern_V_inputs_real.pla 52
ПРИЛОЖЕНИЕ Д Файл real_by_real_outputs.pla 54
ПРИЛОЖЕНИЕ Е Файл real_by_spec_outputs.pla
📖 Введение
Традиционные подходы к тестированию неисправностей логических схем позволяют находить тестовые наборы для заданной неисправности многовыходной схемы в виде множества входных наборов схемы, при этом различия реакций исправной и неисправной схем на каждом из наборов могут быть установлены двоичным моделированием. В случае, когда находятся все тестовые наборы, и число их велико, выполнить двоичное моделирование для каждого из наборов практически невозможно, однако в то же время при решении ряда задач полезно иметь информацию о связи реакций схемы с тестовыми наборами, а также желательно представить эту информацию компактным образом.
В данной работе исследуется возможность поиска тестовых наборов с соответствующими им реакциями на основе представления исправной и неисправной схем однокоренными ROBDD-графами, предложенными В. А. Провкиным, а также излагается стратегия поиска тестовых наборов для частично построенной схемы с использованием данных графов. Предлагаемый в данной работе подход позволяет отказаться от использования Quantified Boolean Function (QBF) решателей или их модификаций, требующих, как правило, более сложных вычислений, чем операции над ROBDD-графами, характеризующиеся полиномиальной сложностью.
В данной работе исследуется возможность поиска тестовых наборов с соответствующими им реакциями на основе представления исправной и неисправной схем однокоренными ROBDD-графами, предложенными В. А. Провкиным, а также излагается стратегия поиска тестовых наборов для частично построенной схемы с использованием данных графов. Предлагаемый в данной работе подход позволяет отказаться от использования Quantified Boolean Function (QBF) решателей или их модификаций, требующих, как правило, более сложных вычислений, чем операции над ROBDD-графами, характеризующиеся полиномиальной сложностью.
✅ Заключение
В данной работе была рассмотрена проблема проверки частичной эквивалентности (the partial equivalence checking problem, PEC), то есть проверка исправности частично реализованной схемы, и изложен подход построения тестовых наборов для обнаружения неисправностей частично реализованной схемы с использованием графов В. А. Провкина.
Полученные экспериментальные результаты показали, что недостатком приведенной стратегии поиска тестовых наборов, несмотря на компактность представления систем булевых функций однокоренными графами В. А. Провкина, может быть большая ресурсоемкость, поскольку количество вершин в графах различий стремительно увеличивается за счет конъюнкции графов, зависящих от разных подмножеств переменных.
Однако исчерпывающее содержание информации о различиях реакций исправной и неисправной схем в виде полного множества тестовых наборов может быть использовано для анализа полученного множества входных векторов с целью установления места возникновения неисправности и дальнейшего её устранения, то есть для задачи дебаггинга.
Полученные экспериментальные результаты показали, что недостатком приведенной стратегии поиска тестовых наборов, несмотря на компактность представления систем булевых функций однокоренными графами В. А. Провкина, может быть большая ресурсоемкость, поскольку количество вершин в графах различий стремительно увеличивается за счет конъюнкции графов, зависящих от разных подмножеств переменных.
Однако исчерпывающее содержание информации о различиях реакций исправной и неисправной схем в виде полного множества тестовых наборов может быть использовано для анализа полученного множества входных векторов с целью установления места возникновения неисправности и дальнейшего её устранения, то есть для задачи дебаггинга.
ИЛИ
Поиск аналога
📕 Список литературы
🛒 Оформить заказ
⚡ Работу высылаем в течении 5 минут после оплаты.