Разработка и исследование методов моделирования и оценки мер тестопригодности логических схем тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат технических наук Голубева, Ольга Ивановна

• Голубева, Ольга Ивановна
• кандидат технических наук
• 2000

Оглавление диссертации кандидат технических наук Голубева, Ольга Ивановна

ВВЕДЕНИЕ.

ГЛАВА 1. ОПРЕДЕЛЕНИЯ, ОБОЗНАЧЕНИЯ, ПОСТАНОВКА ЗАДАЧ И

ОБЗОР МЕТОДОВ ИХ РЕШЕНИЯ.

1.1. Булевы функции и их интервальные расширения.

1.1.1. Булевы и троичные функции.

1.1.2. Интервальные расширения булевых функций.

1.2. Абстрактные автоматы, логические автоматы и их интервальные расширения.

1.2.1. Понятие абстрактного конечного автомата.

1.2.2. Интервальное расширение логического автомата.

1.3. Моделирование логических схем.

1.3.1. Логические схемы.

1.3.2. Постановка задачи моделирования.

1.4. Обзор методов моделирования.

1.5. Обзор методов вычисления мер тестопригодности для комбинационных схем.Т.

1.6. Задачи исследования.

ГЛАВА 2. МОДЕЛИРОВАНИЕ КОМБИНАЦИОННЫХ И СИНХРОННЫХ

ПОСЛЕДОВАТЕЛЬНОСТНЫХ СХЕМ, ОСНОВАННОЕ НА ОДНФ-ПРЕДСТАВЛЕНИИ БУЛЕВЫХ ФУНКЦИЙ.

Введение.

2.1. Вычисление значения интервального расширения булевой функции, представленной в виде ОДНФ.

2.2. Вычисление реакции интервального расширения автомата на входную последовательность произвольной длины.

2.3. Моделирование логических схем.

2.4. Результаты экспериментов.

Введение диссертации (часть автореферата) на тему «Разработка и исследование методов моделирования и оценки мер тестопригодности логических схем»

3.1. Постановка задачи. .61

3.2. Вычисление реакции интервального расширения логического автомата.63

3.2.1. Вычисление состояния интервального расширения автомата, соответствующего входной последовательности длины один.63

3.2.2. Вычисление выходных значений интервального расширения автомата на входной последовательности длины один.66

3.2.3. Вычисление реакции интервального расширения автомата на входную последовательность произвольной длины.67

3.3. Троичное моделирование синхронной последовательностной схемы.69

3.3.1. Троичное моделирование синхронной последовательностной схемы, заданной функционально. .69

3.3.2. Троичное моделирование синхронной последовательностной схемы, заданной структурно.74

3.4. Результаты экспериментов.75

3.5. Основные выводы по главе.76

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

СХЕМ.78

Введение.78

4.1. Постановка задачи.79

4.2. Оценка наблюдаемости.82

4.2.1. ОДНФ-представление функции наблюдаемости.82

4.2.2. ВБО-представление функции наблюдаемости.88

4.3. Оценка вероятности обнаружения неисправности.92

4.3.1. Получение функции обнаружения неисправности. .92

4.3.2. Вычисление вероятности обнаружения неисправности. .94

4.4. Результаты экспериментов.99

4.5. Основные выводы по главе.100

ЗАКЛЮЧЕНИЕ.102

СПИСОК ЛИТЕРАТУРЫ.104

ПРИЛОЖЕНИЕ.112

ВВЕДЕНИЕ

Актуальность проблемы.

Диагностирование дискретных устройств занимает важное место при их проектировании, производстве и эксплуатации. Несмотря на значительные теоретические и практические достижения в области технической диагностики дискретных устройств [1-8], постоянный рост их сложности требует дальнейшего исследования проблем диагностирования.

В технической диагностике выделяют два основных типа систем диагностирования: функциональные и тестовые [1]. В системах первого типа процесс диагностирования осуществляется во время выполнения устройством алгоритма функционирования. В системах второго типа устройство в процессе диагностирования не применяется по его прямому назначению, и на него подают специальные входные воздействия. Эти воздействия называют тестовыми, а процесс диагностирования с использованием тестовых воздействий - тестированием.

При построении тестов дискретное устройство, как правило, рассматривается на уровне математической модели. В настоящее время широко применяется построение тестов на основе структурной модели устройства - логической схемы. Неисправность в логической схеме является моделью неисправности в дискретном устройстве. При построении тестов выделяют класс рассматриваемых неисправностей.

Входная последовательность называется тестом для некоторой неисправности в схеме, если реакции на эту последовательность исправной и неисправной схем отличаются. Для комбинационной схемы вместо последовательности рассматривается входной набор.

Проверяющим тестом для схемы называется входная последовательность, которая является тестом для всякой неисправности из рассматриваемого класса, не являющейся необнаружимой.

Построение тестов, как правило, выполняется с применением процедуры моделирования схем [9-21]. Под моделированием понимается получение выходной реакции схемы на заданное входное воздействие. Моделирование является одним из основных средств при построении тестов для схем с памятью.

Идея построения тестов с помощью моделирования заключается в следующем [19]. На заданной входной последовательности выполняется моделирование схем с неисправностями из рассматриваемого класса. Получаемые выходные последовательности сравниваются с эталонной последовательностью, которая является реакцией исправной схемы на входную последовательность. Если некоторая выходная последовательность отличается от эталонной, то соответствующая неисправность считается обнаруженной, и она исключается из дальнейшего рассмотрения. Входные наборы, составляющие тест, могут генерироваться случайным образом либо предлагаться разработчиком схем. Для большей эффективности моделирование сочетается с регулярными методами построения тестов, которые позволяют строить тесты для труднообнаружимых неисправностей схемы (неисправностей, имеющих малую долю тестов среди всевозможных входных наборов). Сочетание регулярных методов с моделированием дает возможность эффективно строить тесты для схем большой сложности. Регулярным методам построения тестов посвящена обширная литература [2237].

При моделировании последовательностных схем на входной последовательности начальное состояние схемы может быть неизвестным, источником неизвестных значений в компонентах входных векторов могут являться неуправляемые входы схемы. Задача моделирования схемы при неизвестных значениях некоторых компонент входных векторов и вектора начального состояния (для синхронной последовательностной схемы) является недостаточно исследованной. На практике, обычно применяется моделирование по правилам троичной логики [6,18] (троичное моделирование), которое в общем случае не дает точных результатов. Имеется ввиду, что результатом троичного моделирования на некотором выходе моделируемой схемы может быть значение х, интерпретируемое как «неизвестно 0 или 1», в то время как при моделировании соответствующих двоичных последовательностей для каждой из них на рассматриваемом выходе достигается значение 1 (значение 0). Неточность моделирования ведет к ухудшению качества тестовой последовательности, построенной на основе такого моделирования, то есть к увеличению ее длины или, при фиксированной длине тестовой последовательности, - к снижению ее полноты относительно рассматриваемого класса неисправностей. Для комбинационных схем известны методы точного троичного моделирования, но они требуют громоздких функциональных описаний схем. Для синхронных последовательностных схем специальных методов точного троичного моделирования на входных последовательностях произвольной длины не известно. Применение точных методов троичного моделирования, предложенных для комбинационных схем, в синхронных последовательностных схемах, хотя и возможно теоретически, практически приемлемо лишь для получения точных результатов на одном шаге моделирования, но не на последовательности в целом.

В настоящее время широко применяется вероятностное тестирование дискретных устройств [21,40-43]. Идея метода заключается в подаче на входы устройства случайных наборов и последующем сравнении полученного на выходе результата с эталонным значением.

При вероятностном тестировании возникает задача определения длины теста, обеспечивающего обнаружение неисправностей из рассматриваемого класса с заданной вероятностью. Оценка длины теста, как правило, выполняется с применением вероятностей обнаружения неисправностей из рассматриваемого класса [21].

Если длина случайного теста, обеспечивающего обнаружение неисправностей из рассматриваемого класса, больше заданной величины, то схему считают не тестопригодной.

В этом случае возникает задача обеспечения тестопригодности схемы. Одним из подходов к обеспечению тестопригодности является введение дополнительных контрольных точек в схему [2,21]. Для определения необходимых контрольных точек вычисляются управляемости и наблюдаемости внутренних полюсов схемы.

Вероятности обнаружения одиночных константных неисправностей, а также управляемости и наблюдаемости внутренних полюсов схемы называют мерами тестопригодности схемы.

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

Вышеизложенное показывает, что актуальность темы определяется:

• трудоемкостью известных методов точного троичного моделирования комбинационных схем при неизвестных значениях некоторых компонент входных векторов;

• отсутствием практически применимых точных методов троичного моделирования синхронных последовательностных схем при неизвестных значениях некоторых компонент входных векторов и вектора начального состояния;

• трудоемкостью известных методов точного вычисления мер тестопригодности схем.

Целью работы является

1. Разработка методов точного троичного моделирования комбинационных схем при неизвестных значениях некоторых компонент входных векторов, менее трудоемких, чем ранее предложенные методы.

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

3. Разработка эффективных методов точного вычисления мер тестопригодности для комбинационных схем.

Методы исследования. В работе использовались методы дискретной математики, а именно: теория логических сетей, теория автоматов, теория булевых функций, теория графов.

Научную новизну полученных в работе результатов определяют:

• Метод точного троичного моделирования комбинационных схем при неизвестных значениях некоторых компонент входных векторов. Метод основан на представлении булевых функций, реализуемых схемой, в виде ортогональных ДНФ (ОДНФ) или ВБО-графов, являющихся компактным описанием ОДНФ.

• Методы точного троичного моделирования синхронных последовательностных схем на последовательностях произвольной длины при неизвестных значениях некоторых компонент входных векторов и вектора начального состояния.

Первый из предложенных методов основан на представлении функций переходов-выходов схемы в виде ОДНФ, второй - на представлении этих функций в специальном виде, где каждому состоянию схемы сопоставлена своя внутренняя переменная.

• Эффективные методы точного вычисления мер тестопригодности для комбинационных схем.

Практическая значимость работы.

Моделирование применяется при построении тестов, при этом важными характеристиками моделирования являются скорость и точность. Чем выше скорость моделирования, тем меньше время построения тестовой последовательности. Чем точнее моделирование, тем выше качество тестов, построенных на основе моделирования.

Предложенные методы точного троичного моделирования комбинационных схем при неизвестных значениях некоторых компонент входных векторов являются менее трудоемкими по сравнению с ранее известными методами, так как выполняются по более простому функциональному описанию и, следовательно, позволяют повысить скорость моделирования.

Предложенные методы точного троичного моделирования синхронных последовательностных схем на последовательностях произвольной длины при неизвестных значениях некоторых компонент входных векторов и вектора начального состояния позволяют повысить точность моделирования, и, следовательно, качество тестов.

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

Внедрение результатов.

Работа выполнялась в рамках проектов:

1. Госбюджетная тема Сибирского физико-технического института при Томском государственном университете (ТГУ), программа «Исследование и разработка новых методов электромагнитного контроля и диагностики материалов, сред и технических систем», 1995-2000 гг., шифр «Диаконт», раздел «Разработка методик и аппаратуры исследований».

2. ФЦП «Интеграция». Раздел «Прикладная дискретная математика».

3. Министерства образования по разделу "Автоматика и телемеханика", направление - "Элементы, узлы и устройства автоматики, телемеханики и вычислительной техники":

• 1996-1997гг. "Исследование проблемы повышения качества тестирования и контролепригодного проектирования",

• 1998-1999гг: "Исследование проблемы синтеза самотестируемых устройств и проблемы повышения качества тестирования".

Предложенные методы моделирования логических схем были реализованы в виде пакета прикладных программ в работах по межвузовской научно-технической программе «Конверсия и высокие технологии. 1997-2000 годы» (проект №95-1-21 «Информационные компьютерные технологии дискретного математического моделирования, анализа, синтеза и тестирования сверхскоростных интегральных схем логического управления»).

Теоретические результаты работы внедрены в учебный процесс на факультете прикладной математики и кибернетики Томского государственного университета: используются в курсе лекций «Диагностика дискретных устройств».

Апробация работы.

Научные результаты диссертационной работы докладывались и обсуждались на заседаниях объединенного семинара кафедры математической логики и проектирования радиофизического факультета ТГУ, кафедры программирования факультета прикладной математики и кибернетики ТГУ и лаборатории синтеза дискретных автоматов Сибирского физико-технического института при ТГУ, а также на следующих научных конференциях:

1. Третья международная научно-техническая конференция «Актуальные проблемы электронного приборостроения» . Новосибирск, 1996.

2. ШЕЕ European Test Workshop 1997. Italy, Cagliari, 1997.

3. Международная конференция «Всесибирские чтения по математике и механике. Томск, 1997.

4. Международная конференция «Сибирская конференция по исследованию операций». Новосибирск, 1998.

5. Третий международный симпозиум «Application of the Conversion Research Results for International Cooperation». Томск, 1999.

6. Третья международная конференция «Автоматизация проектирования дискретных систем». Минск, 1999.

Публикации.

По тематике диссертации опубликовано 10 печатных научных работ, в том числе: 1 статья, 5 докладов (из них 3 в рецензируемых материалах конференций) и 4 тезисов докладов в трудах всероссийских и международных конференций. Структура и объем работы.

Работа состоит из введения, четырех глав и заключения. Объем работы составляет 117 с. Список литературы включает 81 наименование. Личный вклад.

Основные результаты работы получены лично автором. Краткое изложение основного содержания работы.

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

Во второй главе предлагаются: метод точного троичного моделирования комбинационной схемы на входном троичном векторе и метод точного троичного моделирования синхронной последовательностной схемы на входной троичной последовательности произвольной длины и троичном векторе начального состояния.

Методы основаны на сведении задачи вычисления значения интервального расширения булевой функции к вычислению вероятности единичного значения булевой функции при заданном распределении вероятностей значений ее аргументов. Метод моделирования комбинационной схемы применяется к булевым функциям, реализуемым схемой, представленным в виде ОДНФ. Метод моделирования синхронной схемы применяется к функциям переходов-выходов схемы (функциям комбинационного эквивалента длины один), представленным в виде ОДНФ.

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

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

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

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

Получена формула для функции обнаружения неисправности, позволяющая совместно решать задачи вычисления наблюдаемости и вероятности обнаружения неисправностей константа 1 и константа 0.

Проведены компьютерные эксперименты, оценивающие эффективность предложенных методов.

В заключении перечисляются основные полученные в работе результаты.

14

Основные положения, выносимые на защиту.

1. Метод точного троичного моделирования комбинационной схемы при неизвестных значениях некоторых компонент входных векторов, основанный на представлении булевых функций, реализуемых схемой, в виде ОДНФ.

2. Два метода точного троичного моделирования синхронной последовательностной схемы при неизвестных значениях некоторых компонент входных векторов и вектора начального состояния на входных последовательностях произвольной длины. Один из методов является более быстродействующим, второй применим к более широкому классу синхронных последовательностных схем.

3. Эффективные методы точного вычисления мер тестопригодности для комбинационных схем.

Заключение диссертации по теме «Системный анализ, управление и обработка информации (по отраслям)», Голубева, Ольга Ивановна

4.5. Основные выводы по главе

В данной главе предлагаются методы точного вычисления мер тестопригодности (управляемости, наблюдаемости, вероятности обнаружения неисправности), основанные на ВОБ и ОДНФ представлениях функций 1(0)-управляемости - С1 (С0), наблюдаемости - В(Х), обнаружения неисправности константа 1(0) - 1)1( В{)).

1. Предложены формулы для получения в виде ОДНФ функции наблюдаемости на /-ом выходе схемы, позволяющие в несколько раз сократить число перемножаемых конъюнкций по сравнению с известной процедурой по

101 строения ОДНФ этой функции.

2. Предложен метод построения BDD-представления функции наблюдаемости полюса схемы на ее i-ом выходе, сводящийся к упрощению BDD-представления фрагмента исправной схемы, сопоставляемого этому выходу и полюсу.

3. Получена формула для функции обнаружения неисправности. Эта формула позволяет совместно решать задачи вычисления наблюдаемости, вероятности обнаружения неисправности константа 1 и константа 0.

4. Предложен ряд способов дополнительного сокращения времени вычисления вероятности обнаружения неисправности в некоторых частных случаях: при вычислении вероятности обнаружения неисправности для единственного распределения Р(Х) и при выяснении достижения этой мерой тес-топригодности пороговой величины.

5. Проведены эксперименты, подтверждающие эффективность предложенных методов построения функций В(Х) и D] (D°).

ЗАКЛЮЧЕНИЕ

В соответствии с поставленными целями исследования в диссертационной работе получены следующие результаты:

1. Разработан метод точного троичного моделирования комбинационной схемы при неизвестных значениях некоторых компонент входных векторов. Метод основан на сведении задачи к задаче вычисления вероятности единичного значения булевой функции при заданном распределении вероятностей ее аргументов. Для реализации метода функции, реализуемые схемой, должны быть представлена в виде ОДНФ или ВШ)-графов, компактно представляющих ОДНФ.

2. Разработан метод точного троичного моделирования синхронной последовательностной схемы на входных последовательностях произвольной длины при неизвестных значениях некоторых компонент входных векторов и вектора начального состояния. Для реализации метода функции переходов-выходов схемы (функции системы канонических уравнений) должны быть представлена в виде ОДНФ.

Предложены методы сокращения вычислений при реализации метода точного моделирования синхронной последовательностной схемы, основанные на использовании результатов более простых в реализации неточных методов троичного моделирования и оценке получаемых в процессе вычислений промежуточных значений.

3. Разработан метод точного троичного моделирования синхронной последовательностной схемы на входных последовательностях произвольной длины при неизвестных значениях некоторых компонент входных векторов и вектора начального состояния. Для реализации метода используется система канонических уравнений схемы специального вида, где каждому состоянию моделируемой схемы сопоставлена своя внутренняя переменная. Метод моделирования является пошаговым, на каждом шаге предлагается простая

103 процедура вычислений.

4. Разработаны эффективные методы точного вычисления мер тестопригодности для комбинационных схем.

5. Предложенные в работе методы программно реализованы. Проведены эксперименты, подтверждающие работоспособность и эффективность предложенных методов.

Список литературы диссертационного исследования кандидат технических наук Голубева, Ольга Ивановна, 2000 год

1. Основы технической диагностики / В.В. Карибский, П.П. Пархоменко, Е.С. Согомонян, В.Ф. Халчев; Под ред. П.П. Пархоменко. М.: Энергия, 1976.-462 с.

2. Методы и средства диагностирования КМОП БИС: Учеб. пособие для вузов / С.Е. Артамонов, В.М. Кривошапко, Д.О. Левицкий и др.; Под ред.

3. B.М. Кривошапко. М.: Радио и связь, 1993. - 240 с.

4. Пархоменко П.П., Согомонян Е.С. Основы технической диагностики. -М.: Энергия, 1981. Ч. 2. - 320 с.

5. Автоматизированное проектирование цифровых устройств / Под ред.

6. C.С. Бадулина. М.: Радио и связь, 1981. - 235 с.

7. Abramovici M., Breuer М.А., Friedman A.D. Digital Systems Testing and Testable Design. New York: Computer Science Press, 1990.

8. Гольдман P.C., Чипулис В.П. Техническая диагностика цифровых устройств. М.: Энергия, 1976. - 224 с.

9. Казначеев В.И. Диагностика неисправностей цифровых автоматов. М.: Сов. радио, 1975. - 256 с.

10. Williams T.W. VLSI Testing. Slivier Science Publishers. - New York, 1986. -248 p.

11. Чжен Г., Мэннинг E., Метц Г. Диагностика отказов цифровых вычислительных систем: Пер. с англ. / Под ред. И.Б. Михайлова. М.: Мир, 1972.-232 с.

12. Гурвич Е.И., Куликовская Т.П. Метод анализа тестов цифровых устройств с помощью логического моделирования // Применение вычислительных машин для проектирования цифровых устройств. М.: Советское радио, 1968. - С. 81-98.

13. Hardie Т.М., Syhocki R.J. Design and Use of Fault Simulation for Saturn Computer Design // IEEE Trans. On Electronic Computers. 1967. - Vol. EC16, N4. P. 412-429.

14. Киносида К., Осада К., Карацу О. Логическое проектирование СБИС. -М.: Мир, 1988.-308 с.

15. Биргер А.Г., Бояршинов А.В., Гурвич Е.Т. и др. Автоматизированная система контроля и диагностики цифровых ячеек // Обмен опытом в радиопромышленности. 1978. - Вып. 4-5. - С. 40-46.

16. Биргер А.Г. Применение моделирования в автоматизированной системе построения тестов // Обмен опытом в радиопромышленности. 1978. -Вып. 4-5.-С. 97-101.

17. Seshu S., Freeman D.N. The Diagnosis of Asynchronous Sequential Switching Systems // IEEE Trans. On Electronic Computers. 1962. - Vol. EC-11, N 4. -P. 459-465.

18. Seshu S. On an Improved Diagnosis Program // IEEE Trans. On Electronic Computers. 1965. - Vol. EC-14, N 1. - P. 76-79.

19. Cheng. K.-T. Recent Advances in Sequential Test Generation // IEEE VLSI Test Symposium. 1992. - P. 241-246.

20. Breuer M.A. A Note on Three-Valued Logic Simulation // IEEE Trans, on Computers. 1972. - Vol. C-21, N 4. - P. 399-402.

21. Уткин А.А. Анализ логических сетей и техника булевых вычислений. -Минск: Наука и техника, 1979. 152 с.

22. Armstrong D.B. A Deductive Method for simulating faults in logical circuits // IEEE Trans, on Computers 1972. - Vol. C-21, N 5.

23. Bardell P., McAnney W., Savir J. Built-in Test for VLSI: Pseudo-random Techniques. New York: John Wiley & Sons, 1987. - 353 p.

24. Poage J.F. Derivation of Optimal Tests to Detect Faults in Combinational Circuits // Proc. Symp. On Mathematical Theoiy of Automata. Brooklyn: Polytechnic Press, 1963. - N 4. - P. 483-528.

25. Roth J.P. Diagnosis of Automata Failures: A Calculus and a Method // IBM

26. Journal of Research and Development. 1966. - Vol. 10, - N 4, - P. 278-291.

27. Armstrong D.B. On Finding of Nearly Minimal Set of Fault Detection Tests for Combinational Logical Nets // IEEE Trans. On Electronic Computers. 1966. -Vol. EC-15, N 1. - P. 66-73.

28. Amar V., Condulmari N. Diagnosis of Large Combinational Networks // IEEE Trans. On Electronic Computers. 1967. - Vol. EC-16, N 5. - P. 675-680.

29. Roth J.P., Bouricius W. G., Schneider P.R. Programmed Algorithm of Computer Tests to Detect and Distinguish between Failures in Logical Circuits // IEEE Trans. On Electronic Computers. 1967. - Vol. EC-16, N 5. - P. 567580.

30. Marinos P.N. Derivation on Minimal Complete Set of Test-Input Sequences Using Boolean Differences // IEEE Trans, on Computers. 1971. - Vol. C-20, Nl.-P. 25-32.

31. Chiang A.C.L., Reed I.S., Banes A.V. Path sensitization, partial Boolean difference, and automated fault diagnosis // IEEE Trans, on Computers. 1972. -Vol. C-21, N 2.

32. I. Berger, E. Kohavi. Fault Detection in Fanout-Free Combinational Networks // IEEE Trans, on Computers. 1973. - Vol. C-22, N 10. - P. 908-914.

33. Карепов C.A., Липский В.Б., Матросова А.Ю., Сергеева Л.Ф. Применение методов решения булевых уравнений в диагностике неисправностей комбинационных сетей // Тр. междунар. симпозиума «Дискретные системы». Рига: Изд-во «Зинатне», 1974. - С. 151-159.

34. Матросова А.Ю. Метод обнаружения неисправности в синхронном устройстве // Автоматика и телемеханика. 1977. - № 12. - С. 129-137.

35. Кузнецов С.С. Реализация алгоритма построения тестов для схем с памятью с использованием комбинационных моделей различной адекватности // Обмен опытом в радиопромышленности. 1978. - Вып. 45. - С. 92-97.

36. Roth P. Computer Logic. Testing and Verification. Philadelphia: Computer Science Press, 1980. - 176 p.

37. Goel P. An Implicit Enumeration Algorithm to Generate Tests for Combinational Logical Circuits // IEEE Trans. On Electronic Computers. -1981.-Vol. C-30(3).-P. 215-222.

38. Fujiwara H., Shimono T. On the Acceleration of Test Generation Algorithms // 13th Annual Fault-Tolerant Computing Symposium. Milan, Italy. June, 1983. -P. 98-105.

39. Su S. Y., Cutler M., Wang M. Test Generation by Critical Backtracing with time Reducing Heuristics // Int. Test. Conf. Washington D.C. - 1987. - P. Ю35-1044.

40. Матросова А.Ю. Алгоритмические методы синтеза тестов. Томск: Изд-во Том. ун-та, 1990. 207 с.

41. Биргер Г., Бояршинов А.В., Винокур М.Ю. и др. Кондиция -автоматизированная система контроля и диагностирования цифровых ячеек // Электронное моделирование. 1980. - N 4. - С. 58-63.

42. Матросова А.Ю., Г.А. Реморенко. Уточнение результатов моделирования в алфавите С // Алгоритмы решения задач дискретной математики, вып. 2. Томск: Изд-во Томского ун-та, 1987. - 203 с.

43. Убар P.P. Проектирование контролепригодных дискретных систем: Учебное пособие. Таллин: Таллинский политехнический институт, 1988. - 68 с.

44. Ярмолик В.Н., Демиденко С.Н. Генерирование и применение псевдослучайных сигналов в системах испытаний и контроля. Минск: Наука и техника, 1986. - 198 с.

45. Agrawal V. When to Use Random Testing // IEEE Trans. On Сотр. 1978. -Vol. C-27, № 11. - P. 1054-1055.

46. Wagner K.D., Chin C.K., McCluskey E.J. Pseudorandom Testing // IEEE

47. Trans. On Сотр. 1987. - Vol. C-36, № 3, P. 332-343.

48. Яблонский C.B. Введение в дискретную математику. М.: Наука, 1979. -272 с.

49. Eichelberger Е. В. Hazard Detection in Combinational and Sequential Switching Circuits // IBM Journal of Research and Development. 1965. - Vol. 9, N2.-P. 90-99.

50. Кудрявцев В.Б., Алешин C.B., Подколзин A.C. Элементы теории автоматов: Учебное пособие. М.: Изд-во Моск. ун-та, 1978. - 216 с.

51. Агибалов Г.П., Оранов A.M. Лекции по теории конечных автоматов: Учебное пособие. Томск: Изд-во Томск, ун-та, 1984. - 186 с.

52. Закревский А.Д. Алгоритмы синтеза дискретных автоматов. М.: Наука, 1971. -512 с.

53. Keim М., Becker В., Stenner В. On the (Non-)Resetability of Synchronous Sequential Circuits II 14th VLSI Test Symposium. 1996. - P. 240-245.

54. Stephenson J.E., Grason J.A Testability Measure for Register Transfer Level Digital Circuits It 6th Annual Fault-Tolerant Computing Symposium. Pittsburg, PA. June 1976. P. 101-107.

55. Grason J. TMEAS, A Testability Measurement Program // 16th Design Automation Conference. San Diego, CA. June, 1979. P. 156-161.

56. Goldstein L.H. Controllability/Observability Analysis of Digital Circuits // IEEE Trans. Circuits Systems. 1979. - CAS-26(9). - P. 685-693.

57. Goldstein L.H., Thigpen E.L. SCOAP: Sandia Controllability/Observability Analysis Program // 17th АСМЛЕЕЕ Design Automation Conference. Minneapolis, MN. June, 1980. P. 190-196.

58. Ratiu I.M., Sangiovanni-Vincentelli A., Pederson D.O. VICTOR: A Fast VLSI Testability Analysis Program // 1982 International Test Conference. Philadelphia, PA. November, 1982. P. 397-401.

59. Jain S. K., Agrawal V. D. Statistical Fault Analysis // IEEE Design Test Сотр.- 1985.-Vol. 2, № 1. P. 38-44.

60. Simeu E., Puissochet A., Rainard J.L., Tagant A.M., Poize M. A New Tool for Random Testability Evaluation Using Simulation and Formal Proof // IEEE VLSI Test Symposium. 1992. - P. 321-326.

61. Seth S.C., Pan L., Agrawal V.D. PREDICT-Probabilistic Estimation of Digital Circuits Testability // 15th Annual Fault-Tolerant Computing Symposium. Ann Arbor, MI. June, 1985. P. 220-225.

62. Brglez F., Pwnall P., Hum R. Application of Testability Analysis: from ATPG to Critical Delay Path Tracing // Proceedings of IEEE International Test Conference. Philadelphia, PA. October, 1984. P. 705-712.

63. Savir J., Ditlow G.S., Bardell P.H. Random Pattern Testability // IEEE Trans. On Сотр. 1984. - Vol. C-33, № 1. - P. 79-90.

64. Savir J. Improved Cutting Algorithm // IBM Journal of Research and Development. 1990. - V. 34, № 2/3. - P. 49-75.

65. Markowsky G. Bounding Signal Probability in Combinational Circuits // IEEE Transactions on Computers. 1987. - V. C-36, № 10. - P. 1247-1251.

66. Krishnamurthy В., Tollis I. Improved Techniques for Estimating Signal Probabilities // IEEE Trans. On Computers. 1989. - V. 38(7). - P. 1041-1045.

67. Wunderlich H.J. PROTEST: A Tool for Probabilistic Testability Analysis // Proc. Of the 22nd Design Automation Conf. 1985. - P. 204-211.

68. Евтушенко H.B., Матросова А.Ю. О вероятностном подходе к вычислению оценок управляемости и наблюдаемости узла дискретного устройства // Автоматика и телемеханика. 1993. - № 11. - С. 152-160.

69. Matrosova A., Bochun Т. Verification of the Test Quality // Baltic Electronics Conference. Tallinn Technical University. Tallinn. 1996.

70. Krieger R., Becker В., Okrnen C. OBDD-based Optimization of Input Probabilities for Weighted Random Pattern Generation // Fault Tolerant Computing Conference. 1995. - P. 120 - 129.

71. Bryant R.E. Graph-Based Algorithms for Boolean Function Manipulation // IEEE Trans, on Сотр. 1986. - Vol. C-35, № 8. - P. 677-691.

72. A. Matrosova, O. Golubeva, S. Tsurikov. On Correction of the Results of a Ternary Simulation // Compendium of Papers of IEEE European Test Workshop 1997. Italy. Cagliari. May 28-30 1997. 2 p.

73. Мерекин Ю.В. Решение задач вероятностного расчета однотактных схем методом ортогонализации // Вычислительные системы. 1963. - Вып. 5. -С. 10-21.

74. Голубева О.И. Троичное моделирование синхронных последовательностных схем // Математическое моделирование. Кибернетика. Информатика. Томск: Изд-во ТГУ, 1999. - С. 53-59.

75. Матросова А.Ю. О вероятностном моделировании дискретных устройств // Автоматика и телемеханика. 1995. - С. 156-164.

76. Brglez F., Bryan D., Kozminski К. Combinational Profiles of Sequential Benchmark Circuits // Proc. International Symposium on Circuits and Systems.-1989. P. 1929-1934.

77. Радюк JI.E., Терпугов А.Ф. Теория вероятностей и случайных процессов: Учебное пособие. Томск: Изд-во ТГУ, 1988. - 174 с.•siой -оо \ Щ, Ло <1. ЧЛ 'У

78. УТВЕРЖДАЮ» Проректор по учебной работе ТГУпрофе<?со|Ц^^7~^ Ревушкин А. С.2S~ » мая 2000 г.1. АКТо внедрении результатов диссертации Голубевой О.И. в учебный процесс ТГУ

79. Декан факультете прикладной математики и кибернетики ТГУпрофессор/ШГорцев A.M.

80. Зав. кафедрой программирования ФПМК, профессор /^Uo^h-^ Матросова А.Ю.1. УТВЕРЖДАЮ»сфти при тгу1. Колесник А.Г.1. ЩЦ—*//« » мая 2000 г.-1. СПРАВКА

81. Научный руководитель раздела, Евтушенко Н.В.1. Заведующий отделом 102профессор1. Семенов В.С.профессор15 » мая 2000 г.1. СПРАВКА