Введение к работе
Актуальность проблемы. Тестирование дискретных устройств занимает важное место при их проектировании, производстве и эксплуатации. В процессе тестирования на устройство подают специальные входные воздействия, называемые тестами. При построении тестов устройство обычно рассматривается на уровне математической модели -логической схемы.
Моделирование является одним из основных средств построения тестов для логических схем, особенно для схем с памятью. Под моделированием понимается получение выходной реакции схемы на заданную входную последовательность. Задача моделирования схемы при неизвестных значениях некоторых компонент векторов входной последовательности и вектора, представляющего начальное состояние (для синхронной последовательностной схемы), является недостаточно исследованной. Для решения этой задачи применяются методы, которые либо являются неточными, либо достаточно трудоемкими. Речь идет о методах троичного моделирования логических схем. При реализации неточного метода моделирования может быть вычислено значение х, интерпретируемое как «неизвестно 0 или 1», в то время, как на всех последовательностях булевых векторов, полученных из рассматриваемой троичной последовательности, вычисляется значение 1(0). Неточность моделирования ведет к увеличению длины тестовой последовательности, построенной на основе такого моделирования.
В настоящее время широко применяется вероятностное тестирование дискретных устройств. При вероятностном тестировании возникает задача определения длины случайного теста, обеспечивающего обнаружение неисправностей из рассматриваемого класса с заданной вероятностью. Оценка длины теста, как правило, выполняется с применением вероятностей обнаружения неисправностей из этого класса. Если длина случайного теста, обеспечивающего обнаружение неисправностей из класса, больше заданной величины, то схему считают не тесто пригодной. Одним из подходов к обеспечению тестопригодности является введение дополнительных контрольных точек в схему. Для определения необходимых контрольных точек вычисляются управляемости и наблюдаемости полюсов схемы. Вероятности обнаружения неисправностей, а также управляемости и наблюдаемости полюсов схемы
называют мерами тестопригодности.
В литературе уделено достаточно большое внимание различным методам вычисления мер тестопригодности, большинство предложенных методов являются приближенными. Известные точные методы либо ориентированы на ограниченный класс схем, либо являются достаточно трудоемкими.
Вышеизложенное показывает, что актуальность темы определяется:
трудоемкостью известных методов точного моделирования комбинационной схемы при неизвестных значениях некоторых компонент входного вектора;
отсутствием практически применимых точных методов моделирования синхронной последовательностной схемы при неизвестных значениях некоторых компонент векторов входной последовательности и вектора начального состояния;
трудоемкостью известных методов точного вычисления мер тестопригодности схемы.
Цель работы. Целью работы является разработка методов точного моделирования комбинационных и синхронных последователыюстных схем при неизвестных значениях некоторых компонент входных векторов и вектора начального состояния (для синхронной последовательностной схемы), то есть методов точного троичного моделирования, а также разработка эффективных методов точного вычисления мер тестопригодности для комбинационных схем.
Методы исследования. В работе применяется аппарат дискретной математики, а именно: теория логических сетей, теория автоматов, теория булевых функций, теория ірафов. В работе также использовались компьютерные эксперименты для оценки эффективности разработанных методов.
Научная новизна. Разработаны методы точного троичного моделирования. Предложен метод точного моделирования комбинационных схем при неизвестных значениях некоторых компонент входных векторов. Метод основан на представлении булевых функций, реализуемых схемой, в виде ортогональных ДНФ (ОДНФ) или BDD-графов (Binary Decision Diagram), являющихся компактным описанием ОДНФ. Такое описание проще ранее применяемых для решения задачи функциональных описаний. Для синхронных поелсдовательностных схем
предложено два метода точного моделирования на последовательностях произвольной длины при неизвестных значениях некоторых компонент входных векторов и вектора начального состояния. Первый метод основан на представлении функций переходов-выходов схемы в виде ОДНФ, второй - на представлении системы канонических уравнений схемы в специальном виде, где каждому состоянию схемы сопоставлена своя внутренняя переменная. В работе также предложены эффективные методы точного вычисления мер тестопригодности для комбинационных схем.
Достоверность полученных результатов. Все научные результаты и выводы, содержащиеся в диссертации, обоснованы с помощью доказательств, выполненных с использованием аппарата дискретной математики. Работоспособность предложенных в диссертационной работе методов моделирования схем и методов вычисления мер тестопригодности подтверждена компьютерными экспериментами.
Практическая ценность. Предложенные методы точного троичного моделирования схем позволяют строить тесты более высокого качества. Методы точного вычисления мер тестопригодности позволяют сократить время, затрачиваемое на анализ схем с целью определения длины случайного теста или определения необходимых для обеспечения тестопригодности дополнительных контрольных точек.
Реализация полученных результатов. Исследования выполнялись в рамках работ по госбюджетной тематике Сибирского физико-технического института при Томском государственном университете (ТГУ), программа 1995-2000 гг. «Исследование и разработка новых методов электромагнитного контроля и диагностики материалов, сред и технических систем»; министерства образования по разделу «Автоматика и телемеханика», направление - «Элементы, узлы и устройства автоматики, телемеханики и вычислительной техники» (1996-1997гг. «Исследование проблемы повышения качества тестирования и коитролепригодпого проектирования»; 1998-2000 гг. «Исследование проблемы синтеза самотестируемых устройств и проблемы повышения качества тестирования»); ФЦП «Интеграция», раздел «Прикладная дискретная математика». Предложенные методы моделирования логических схем были реализованы в виде пакета прикладных программ в
рамках исследований по Минвузовской научно-технической программе
«Конверсия и высокие технологии. 1997-2000 гг.» (проект №95-1-21
«Информационные компьютерные технологии дискретного
математического моделирования, анализа, синтеза и тестирования сверхскоростных интегральных схем логического управления»). Теоретические результаты работы внедрены в учебный процесс на факультете прикладной математики и кибернетики Томского государственного университета: используются в курсе лекций «Диагностика дискретных устройств».
Апробация работы. Научные результаты диссертационной работы докладывались и обсуждались на заседаниях объединенного семинара кафедры математической логики и проектирования радиофизического факультета ТГУ, кафедры программирования факультета прикладной математики и кибернетики ТГУ и лаборатории синтеза дискретных автоматов Сибирского физико-технического института при ТГУ, а также на 3-ей международной научно-технической конференции «Актуальные проблемы электронного приборостроения» (Новосибирск, 1996), IEEE European Test Workshop 1997 (Italy, Cagliari, 1997), международной конференции «Всесибирские чтения по математике и механике» (Томск, 1997), международной конференции «Сибирская конференция по исследованию операций» (Новосибирск, 1998), 3-м международном симпозиуме «Application of the Conversion Research Results for International Cooperation» (Томск, 1999), 3-й международной конференции «Автоматизация проектирования дискретных систем» (Минск, 1999).
Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения и списка используемой литературы. Объем диссертации составляет //?* страниц, в том числе: титульный лист -1 стр., оглавление - 2 стр., основной текст - /^7/стр., список литературы из 81 наименования - 8 стр., приложение - 5 стр.