Разработка методов сокращения диагностической информации тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат физико-математических наук Миронов, Сергей Владимирович

• Миронов, Сергей Владимирович
• кандидат физико-математических наук
• 2008

Оглавление диссертации кандидат физико-математических наук Миронов, Сергей Владимирович

Введение

1 Методы сокращения диагностической информации

1.1 ДИ при тестовом диагностировании.

1.2 Методы компактного тестирования.

2 Словари неисправностей и способы их организации

2.1 Классические словари неисправностей.

2.2 Таблицы неисправностей

2.3 Словарь с использованием компактных сверток по выходу

2.4 Компактный словарь неисправностей.

2.5 Представление словаря неисправностей в виде дерева

2.6 Словарь неисправностей с организацией по выходам.

2.7 Сокращение СПР при помощи масок.

2.8 Словарь неисправностей на основе таблицы неисправностей

2.9 Нерешенные задачи.

3 Алгоритмы сокращения ДИ с помощью масок

3.1 Оптимизационные задачи связанные с поиском масок

3.2 Генетические алгоритмы для поиска маски.

3.2.1 Описание генетического алгоритма для поиска маски

3.2.2 Параллельная реализация генетических алгоритмов для поиска маски.

3.2.3 Экспериментальные результаты

4 Жадные алгоритмы поиска маски

4.1 Алгоритм поиска единой маски.

4.2 Алгоритм поиска совокупности индивидуальных масок

4.3 Экспериментальные результаты

5 Сокращение ДИ с использованием хеш-функций

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

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

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

Научно-технический прогресс рубежа XX-XXI столетий характеризуется дальнейшим проникновением ЦУ и систем практически во все области современной жизни. В настоящее время трудно представить области науки или техники, в которых не используют такие системы. Схемотехника лежит в основе дальнейшего развития важнейших направлений научно-технического прогресса, обеспечивающего перевод экономики на инновационный путь развития.

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

Развитие технологий производства элементной базы ЦУ приводит к увеличению сложности этих устройств с целью расширения функциональных возможностей. Одновременно с этим возрастают требования к качеству и эффективности их производства. Сложная система должна работать долго и надежно, только в этом случае она экономически целесообразна. Обеспечение работоспособного состояния системы — одна из основных функциональных задач технической эксплуатации, которая представляет собой многоуровневый и многофакторный процесс, требующий научной и инженерно-технической поддержки.

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

Под термином «техническое диагностирование» понимают процесс определения технического состояния устройства с определенной степенью точности [63]. Этот процесс реализуется в системе технического диагностирования (СТД), представляющей совокупность средств, объекта диагностирования (устройства) и исполнителей.

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

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

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

Если устройство находится в одном из неисправных состояний, то может возникнуть другая задача технического диагностирования — локализация неисправностей, т. е. поиск в объекте неисправного элемента (некорректной связи между элементами) или множества элементов, среди которых находится неисправный элемент.

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

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

Задачи контроля исправности устройства и поиска неисправностей обычно решаются системами тестового диагностирования.

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

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

Входные и внутренние параметры объекта диагностирования называют входными и соответственно внутренними переменными, а выходные параметры — выходными функциями. Заметим, что входные переменные и выходные функции могут быть сопоставлены соответственно входам и выходам объекта. Обозначим символом /о исправный объект диагностирования (эталонный объект). Пусть X — n-мерный вектор, компонентами которого являются значения п входных переменных Х\,Х2,хп. Аналогично У0 является /г-мерным вектором значений к внутренних переменных Уъ У2-> • • •' Ук> а — m-мерным вектором значений т выходных функций z®, г!},., zЗапись

Z° = t) (0.1) будем рассматривать как некоторую аналитическую, векторную, графическую, табличную или другую формы представления системы передаточных функций объекта /о, отражающих зависимость реализуемых выходных функций Zq от его входных переменных X, начального значения внутренних переменных и от времени t. Система (0.1) является математической моделью исправного объекта.

Дискретные системы делят на два класса в зависимости от состава аргументов передаточной функции Ф°. Система называется комбинационной, если результат функции в любой момент времени зависит только от значений переменных X поступивших на входы в этот момент времени. Т. е. для комбинационных систем запись (0.1) принимает вид

Z0 = Ф°(Х).

Пример логической схемы комбинационного устройства приведен на рис. 0.1

Последовательностные системы — системы, в которых значения выходных параметров в некоторый момент времени t зависят не только от текущих входных значений, но также и от значений, поступавших на входы системы до этого момента времени. Из-за своей зависимости от прошлых входов последовательностные устройства должны содержать элементы памяти, значения которых в каждый момент времени и представлены вектором Y в (0.1). На рис. 0.2 приведен пример логической схемы последо1 doDo

ED О-6

0o-□oli

19

23

022 -о

023

-о

Рис. 0.1. Комбинационная схема С17 из каталога ISCAS'85

G3

GO G14

G16

G8

G9

G15

Gil

G1 G12

G2

G13 G7

D Set Q > Rst Q" I

GIO

G5

D Set Q Rst Q* jG6

G17 0G17

Х-ЧЭ

D Set Q > Rst Q'

Рис. 0.2. Последовательностная схема S27 из каталога ISCAS'89 вательностного устройства, в котором роль элементов памяти выполняют D-триггеры (блоки G5, G6, G7).

Диагностика неисправностей начинается с выбора модели неисправностей, описывающей характер дефекта в объекте диагностирования.

Неисправности цифровых схем появляются в результате применения неисправных составных компонентов, таких, как логические элементы, реализующие простейшие логические функции, элементы памяти и др. Кроме того, причиной неисправностей могут быть возникновение разрывов или коротких замыканий в межкомпонентных соединениях, нарушение условий эксплуатации схемы, наличие ошибок при проектировании и производстве и ряд других факторов [2,28,33,51,60,63,74].

Из множества различных видов неисправностей выделяется класс логических неисправностей, которые изменяют логические функции элементов цифровой схемы. Указанный класс неисправностей занимает доминирующее место среди неисправностей цифровых схем. Для их описания в большинстве случаев используются следующие математические модели [28,33,87]: константные неисправности, неисправности типа «короткое замыкание», инверсные неисправности и неисправности типа «перепутыва-ние».

Наиболее общей и часто применяемой моделью логических неисправностей являются константные неисправности: константный нуль и константная единица, что означает наличие постоянного уровня логического нуля или логической единицы на входах или выходе неисправного логического элемента. Такая модель неисправностей часто называется классической [87] и широко используется для описания других типов неисправностей.

Неисправности типа «короткое замыкание» (мостиковые неисправности) появляются при коротком замыкании входов и выходов логических элементов.

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

Неисправности типа «перепутывание» заключаются в перепутывании связей цифровой схемы и вызываются ошибками, возникающими при проектировании и производстве цифровых схем, которые изменяют функции,, выполняемые схемой.

Особенности физических неисправностей СБИС и их математические модели даны в работах [1,11].

Выделим для рассмотрения конечное множество возможных неисправностей объекта. Принято различать одиночные и кратные неисправности. Под одиночной понимается неисправность, принимаемая в качестве элементарной, т. е. такой, которая не может быть представлена совокупностью нескольких других неисправностей. Кратная неисправность является совокупностью одновременно существующих двух или большего числа одиночных неисправностей. Символом F будем обозначать множество всех рассматриваемых (не обязательно всех возможных) одиночных и кратных неисправностей объекта. Будем говорить, что при наличии в объекте неисправности fi £ F, 1 ^ i ^ \F\ (здесь и далее запись \Х\ для множества X означает количество элементов в этом множестве), он находится в г-м неисправном состоянии. Объект диагностирования, находящийся в г-м неисправном состоянии, реализует систему передаточных функций

0-2) представленных в той же форме, что и передаточные функции (0.1). Заметим, что начальное значение Y*a4 внутренних переменных объекта fi может не совпадать с начальным значением У^°ач в исправном объекте /о. Система (0.2) для фиксированного i, 1 ^ i ^ |F|, является математической моделью г-ой неисправности. Совокупность систем (0.1) и (0.2) для всех fi, 0 ^ г ^ |F|, образует явную модель объекта диагностирования.

Основным понятием, используемым при решении задач построения и реализации алгоритмов диагностирования, является элементарная проверка объекта. Рассмотрим вопросы задания моделей объектов диагностирования в терминах элементарных проверок объекта и их результатов.

Обозначим символом П множество всех допустимых элементарных проверок 1Tj, 1 ^ j ^ |П|, объекта, т. е. таких его проверок, которые физически осуществимы в конкретных условиях проведения процесса диагностирования. Каждая элементарная проверка, по определению, характеризуется значением воздействия, подаваемого на объект при реализации элементарной проверки, и реакцией объекта на это воздействие. Значение otj воздействия в элементарной проверке тгу е П определяется составом входных переменных и последовательностью во времени t их значений Xj, а также начальным значением Y£a4j внутренних переменных. Ответ объекта в элементарной проверке тгj характеризуется составом {7}^ контрольных точек и значением (результатом элементарной проверки) Rij, зависящим от технического состояния объекта.

Таким образом, результат Rij элементарной проверки представляется в общем случае последовательностью |{7};-|-мерных векторов и является функцией значения aj воздействия:

Вместо этой записи условимся применять более короткую:

Rij = Фг'(7Г,). (0.3)

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

Описанию фактического поведения объекта при элементарной проверке 7i-j соответствует запись

Щ = Щщ). (0-4)

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

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

Описание методов диагностирования с использованием словарей неисправностей может быть найдено, в частности, в [2,38,41,43,45,52,53].

Обозначим через S — множество технических состояний объекта диагностирования. Пусть so Е S обозначает исправное состояние объекта, а' Si 6 S — его г-е неисправное состояние. Каждому г-му неисправному состоянию соответствует неисправность fi из множества F и наоборот.

Результатом работы системы тестового диагностирования является сообщение о том, что объект диагностирования исправен, или, в случае наличия в объекте неисправности, — список подозреваемых неисправностей (СПН) Sj С S — набор технических состояний объекта диагностирования неотличимых между собой алгоритмом диагностирования. СПН порождается неисправностью, присутствующей в объекте диагностирования, и алгоритмом диагностирования. Число всевозможных СПН, которые могут возникнуть в результате алгоритма диагностирования, и число входящих в них неисправностей определяют достигаемую при диагностировании степень детализации мест и состава имеющихся (или подозреваемых на наличие) в объекте неисправностей. Эту степень детализации принято называть глубиной диагностирования.

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

Предположим, что объект диагностирования может находиться в техническом состоянии Si Е S с вероятностью где i—0

Термином «разрешающая способность диагностирования» [86] называют величину

Sj S{ fzSj

Заметим, что эта величина представляет собой математическое ожидание значения величин \Sj\. Следовательно, р\ есть средняя длина возможных СПН. Из последнего факта вытекает, что глубина диагностирования будет тем лучше, чем меньше величина р\. Если разрешающая способность диагностирования равна единице, то очевидно, что все возможные СПН представляют из себя одноэлементные множества, и следовательно, все технические состояния объекта диагностирования отличны друг от друга.

Вычисление оценки (0.5) затруднительно вследствие сложности (а по-' рой и невозможности) вычисления вероятностей pi. Поэтому, вместо величины pi в большинстве случаев (например, [15,83,84]) используют оценку

•5? которую называют ожидаемой глубиной диагностирования [26,44]. Ясно, что величина р2 получается из р\ если принять все технические состояния объекта диагностирования равновероятными.

В работах [27,42] предложена еще одна оценка глубины диагностирования — «диагностическое разрешение». Эта величина определяется как отношение количества различимых между собой пар технических состояний к общему числу пар состояний. Обозначим эту оценку через рз. Легко проверить, что

W-EI^-I2 |с|

S* = 151 ~ (0 7\

Рз |5|2-|5| \S\-1' 14

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

Другие способы оценки глубины диагностирования описаны в работах [26,57,77,79].

Процесс диагностирования ЦУ требует использования так называемой диагностической информации (ДИ), о которой более подробно будем говорить далее. Сейчас же отметим важный факт — очень большой объем ДИ для реальных ЦУ, который порождает значительные трудности при обнаружении и локализации их неисправностей.

Решению проблемы сокращения ДИ посвящено много работ российских и зарубежных ученых, в которых были предложены различные подходы и методы. Следует отметить, что «проклятие размерности», как это происходит и в других предметных областях, не удается «ликвидировать» неким универсальным способом. По этой причине были сделаны попытки создания приемлемых по эффективности методов сокращения ДИ с использованием различных средств, включая, например, специальные методы проектирования ЦУ, особую организацию самой ДИ, специализированную аппаратуру и т. п. Каждый из перечисленных подходов имеет свои достоинства и недостатки и ограниченную сферу применения. Следует отметить, что несмотря на большое число работ в этой области, в целом проблема сокращения ДИ остается открытой до сегодняшнего дня.

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

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

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

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

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

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

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

Заключение диссертации по теме «Дискретная математика и математическая кибернетика», Миронов, Сергей Владимирович

Основные результаты диссертации опубликованы в работах [34,50,59, -71].

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

Заключение

Основным итогом диссертационной работы является решение проблемы, связанной с разработкой эффективных методов сокращения ДИ, представленной в виде словарей неисправностей.

Для достижения указанной цели были поставлены и решены следующие задачи:

• разработка эффективных подходов к поиску единых и индивидуальных масок, с использованием которых создаются соответствующие словари неисправностей;

• разработка новых методов, позволяющих производить максимальное сокращение ДИ без потери разрешающей способности;

• оценка эффективности и быстродействия предложенных методов и алгоритмов сокращения ДИ для реальных цифровых устройств.

Список литературы диссертационного исследования кандидат физико-математических наук Миронов, Сергей Владимирович, 2008 год

1. Abraham, J. A. Fault and error models for VLS1./ J. A. Abraham, W. K. Fuchs // Proceedings of the IEEE. - 1986. - Vol. 74, no. 5. - Pp. 639-654.

2. Abramovici, M. Digital Systems Testing and Testable Design / M. Abramovici, M. A. Breuer, A. D. Friedman. — IEEE Press, 1990.

3. Arslan, B. Fault dictionary size reduction through test response superposition / B. Arslan, A. Orailoglu // Proceedings of 2002 IEEE International Conference on Computer Design: VLSI in Computers (ICCD'02).— Freiburg, Germany: 2002. — Pp. 480-485.

4. Barzilai, Z. The weighted syndrome sums approach to VLSI testing / Z. Barzilai, J. Savir, G. Markowsky, M. G. Smith // IEEE Transactions on Computers. 1981.- Vol. C-30, no. 12.- Pp. 996-1000.

5. Benowitz, N. An advanced fault isolation system for digital logic / N. Benowitz, D. F. Calhoun, G. E. Alderson, J. E. Bauer, С. T. Joeck-el // IEEE Transactions on Computers.— 1975.— Vol. C-24, no. 5.— Pp. 489-497.

6. Blicke, T. A comparison of selection schemes used in genetic algorithms: Tech. Rep. 11 / T. Blicke, L. Thiele. — Zurich: Swiss Federal Institute of Technology, December 1995.

7. Boppana, V. Fault dictionary compaction by output sequence removal / V. Boppana, W. K. Fuchs // Proceedings of 1994 IEEE/ACM international conference on Computer-aided design (ICCAD '94). — San Jose, CA, USA: 1994. Pp. 576-579.

8. Boppana, V. Full fault dictionary storage based on labeled tree encoding / V. Boppana, I. Hartanto, W. K. Fuchs // Proceedings of 14th VLSI Test Symposium. Princeton, NJ, USA: 1996.- Pp. 174-179.

9. Brglez, F. Combinational profiles of sequential benchmark circuits / F. Br-glez, D. Bryan, K. Kozminski // Proceedings of 1989 International Symposium on Circuits and Systems. — Portland, OR, USA: 1989.— Pp. 19291934.

10. Brglez, F. A neutral netlist of 10 combinational benchmark circuits and a target translator in fortran / F. Brglez, H. Fujiwara // Proceedings of 1985 International Symposium on Circuits and Systems. — Kyoto, Japan: June 1985.

11. Bushnell, M. L. Essentials of electronic testing for digital, memory and mixed-signal VLSI circuits / M. L. Bushnell, V. D. Agrawal. — Kluwer academic publishers, 2001.

12. Carter, W. C. Signature testing with guaranteed bounds for fault coverage / W. C. Carter // Digest of Papers 1982 International Test Conference. Philadelphia, PA, USA: 1982. - Pp. 75-82.

13. Carter, W. C. The ubiquitous parity bit / W. C. Carter // Digest of Papers 12th Annual International Symposium Fault-Tolerant Computing. — Santa Monica, CA, USA: 1982. Pp. 289-296.

14. Chakravarty, S. Techniques to encode and compress fault dictionaries / S. Chakravarty, V. Gopal // Proceedings of the 1999 17TH IEEE VLSI Test Symposium (VTS '99).- Washington, DC, USA: IEEE Computer Society, 1999. P. 195.

15. Chess, B. Creating small fault dictionaries / B. Chess, T. Larrabee // IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. 1999. - Vol. 18, no. 3. - Pp. 346-356.

16. Chvatal, V. A greedy heuristic for the set-covering problem / V. Chvatal // Mathematics of operations research. — 1979. — Vol. 4, no. 3. — Pp. 233-235.

17. David, R. Signature analysis of multi-output circuits / R. David j j Digest of Papers 14th Annual International Symposium Fault-Tolerant Computing.- 1984.- Pp. 366-371.

18. Frohwerk, R. A. Signature analysis: A new digital field service technique / R. A. Frohwerk // Hewlett-Packard Journal — 1977.— Vol. 29, no. 9.— Pp. 2-8.

19. Fujiwara, H. Logic Testing and Design for testability / H. Fujiwara. — MIT Press, 1985.

20. Fujiwara, H. Testing logic circuit with compressed data / H. Fujiwara, K. Kinoshita // Proceedings of 1978 IEEE Intl. Fault Tolerant Computing Symp. Pittsburgh, PA, USA: June 1978. - Pp. 88-92.

21. Goldberg, D. E. Genetic Algorithms in Search, Optimization, and Machine Learning / D. E. Goldberg. — New-York: Addison Wesley, 1989.

22. Gordon, G. Hexadecimal signatures identify troublespots in micro processor systems / G. Gordon, H. Nadig // Electronics. — 1977. —■ Vol. 50, no. 5. — Pp. 89-96.

23. Hassan, S. Z. Parallel signature analyzers — detection capability and extensions / S. Z. Hassan, D. J. Lu, E. J. McCluskey // Proceedings of 1983 IEEE Computer Society International Conference COMPCON. — San Francisco. CA, USA: 1983. Pp. 440-445.

24. Hayes, J. P. Check-sum test methods / J. P. Hayes j j Proceedings of 1976 IEEE International Fault Tolerant Computing Symposium. — Pittsburgh, PA, USA: June 1976. Pp. 114-119.

25. Hayes, J. P. Transition count testing of combinational logic circuits / J. P. Hayes // IEEE Transactions on Computers. — June 1976.— Pp. 613-620.

26. Jha, N. K. Testing of Digital Systems / N. K. Jha, S. Gupta. New York, NY, USA: Cambridge University Press, 2002.

27. Kubiak, K. Exact evaluation of diagnostic test resolution / K. Kubiak, S. Parkes, W. K. Fuchs, R. Saleh // Proceedings of 1992 ACM/IEEE Design Automation Conference. — Anaheim, CA, USA: 1992. — Pp. 347-352.

28. Lala, P. K. Fault tolerant and fault testable hardware design / P. K. Lala. — London, 1985.

29. Lavo, David B. Making cause-effect cost effective: low-resolution fault dictionaries / David B. Lavo, Tracy Larrabee // Proceedings of 2001 IEEE International Test Conference. — Washington, DC, USA: IEEE Computer Society, 2001,- Pp. 278-286.

30. Liu, C. Compact dictionaries for fault diagnosis in bist / C. Liu, K. Chakrabarty // Proceedings of the 4th International Symposium on Quality Electronic Design (ISQED '03).- Washington, DC, USA: IEEE Computer Society, 2003.- P. 105.

31. Liu, С. Compact dictionaries for fault diagnosis in scan-bist / C. Liu, K. Chakrabarty // IEEE Transactions on Computers. — 2004. — Vol. 53, no. 6. Pp. 775-780.

32. Markowsky, G. Syndrome-testability can be achieved by circuit modification / G. Markowsky // IEEE Transactions on Computers. — 1981.— Vol. C-30, no. 8.- Pp. 604-606.

33. Miczo, A. Digital Logic Tesing and Simulation / A. Miczo. — Hoboken, New Jersey: John Wiley &: Sons, Inc., 2003.

34. Mironov, S. V. One approach to fault dictionary size reduction / S. V. Mironov, D. V. Speranskiy // Proceedings of 2008 6th East-West Design & Test International Symposium (EWDTS'08). Lviv: 2008. - Pp. 295-300.

35. Niermann, Т. M. HITEC: A Test Generation Package for Sequential Circuits / Т. M. Niermann, J. H. Patel // Proceedings of the European Design Automation Conference (EDAC). 1991. - Pp. 214-218.

36. Pomeranz, I. On the generation of small dictionaries for fault location / I. Pomeranz, S. M. Reddy // Proceedings of 1992 IEEE/ACM international conference on Computer-aided design (ICCAD '92).— Santa Clara, CA, USA: 1992. Pp. 272-279.

37. Quinlan, J. R. C4.5: programs for machine learning / J. R. Quinlan. — San Francisco. CA, USA: Morgan Kaufmann Publishers Inc., 1993.

38. Ratford, V. Integrated guided probe and fault dictionary / V. Ratford, P. Keating // Proceedings of 1986 International Test Conference. — Washington, DC, USA: 1986.- Pp. 304-311.

39. Read, R. S. The coding of various kinds of unlabeled trees / R. S. Read // Graph Theory and Computing. — NY: Academic Press, 1972. — Pp. 153— 182.

40. Reddy, S. M. A note on testing logic circuits by transition counting / S. M. Reddy // IEEE Transactions on Computers. — 1977. — Vol. 26, no. 3. — Pp. 313-314.

41. Richman, J. The modern fault dictionary / J. Richman, K. R. Bowden j j Proceedings of 1985 International Test Conference.— Philadelphia, PA, USA: 1985. Pp. 696-702.

42. Rudnick, E. M. Diagnostic fault simulation of sequential circuit / E. M. Rudnick, W. K. Fuchs, J. H. Patel // Proceedings of 1992 International Test Conference. Baltimore, ML, USA: 1992. - Pp. 178-186.

43. Ryan, P. G. A case study of two-stage fault location / P. G. Ryan, K. Davis, Sh. Rawat // Proceedings of 1992 30th Annual International Reliability Physics Symposium 1992. San Diego, CA, USA: 1992. - Pp. 332-337.

44. Ryan, P. G. Fault dictionary and equivalence class computation for sequential circuits / P. G. Ryan, W. K. Fuchs, I. Pomeranz // Proceedings of 1993 International Test Conference. Washington, DC, USA: 1993. — Pp. 508-511.

45. Ryan, P. G. Two-stage fault location / P. G. Ryan, Sh. Rawat, W. K. Fuchs // Proceedings of 1991 International Test Conference. — Nashville, TN: 1991.-Pp. 963-968.

46. Savir, J. Syndrome-testable design of combinational circuits / J. Savir // Digest of Papers 9th Annual International Symposium Fault-Tolerant Computing. Madison, WI, USA: 1979. - Pp. 137-140.

47. Savir, J. Syndrome-testable design of combinational circuits / J. Savir // IEEE Transactions on Computers. 1980. - Vol. 29, no. 6. — Pp. 442-451.

48. Savir, J. On the masking probability with ones count and transition count / J. Savir, W. H. McAnney // Proceedings of 1985 IEEE International Conference on Computer-Aided Design (ICCAD'85). — Santa Clara, CA, USA: 1985. — Pp. 111-113.

49. Smith, J. E. Measures of the effectiveness of fault signature analysis / J. E. Smith // IEEE Transactions on Computers. — 1980. — Vol. C-29, no. 6. — Pp. 510-514.

50. Speranskiy, D. V. Genetic algorithms for fault dictionary size reduction / D. V. Speranskiy, S. V. Mironov // Proceedings of 2007 5th East-West Design & Test International Symposium (EWDTS'07).- Erevan: 2007.— Pp. 140-145.

51. Timoc, C. Logical models of physical failures / C. Timoc, M. Buehler, T. Griswold // Proceedings of 1983 International Test Conference. — Philadelphia, PA, USA: 1983. Pp. 546-553.

52. Tulloss, R. E. Size optimization of fault dictionaries / R. E. Tulloss // Proceedings of 1978 Semiconductor Test Conference. — Cherry Hill, NJ, USA: 1978. Pp. 264-265.

53. Tulloss, R. E. Fault dictionary compression: recognizing when a fault may unambiguously represented by a single failure detection / R. E. Tulloss // Proceedings of 1980 International Test Conference. — Philadelphia, PA, USA: 1980,- Pp. 368-370.

54. Tzidon, A. A practical approach to fault detection in combinational networks / A Tzidon, I. Berger, M. Yoeli // IEEE Transactions on Computers. 1978.- Vol. C-27, no. 10.- Pp. 968-971.

55. Барашко, А. С. Моделирование и тестирование дискретных устройств / А. С. Барашко, Ю. А. Скобцов, Д. В. Сперанский. — Киев: Наукова думка, 1992.

56. Богомолов, А. М. Аналитические методы в задачах контроля и анализа дискретных устройств / А. М. Богомолов, Д. В. Сперанский. — Саратов: Изд-во Саратовского ун-та, 1986.

57. Вознесенский, С. С. Трудоемкость поиска неисправностей как критерий качества при сокращении объема диагностической информации / С. С. Вознесенский, А. X. Раздобреев // Электронное моделирование. 1980. - № 4. - С. 83-86.

58. Гилл, А. Линейные последовательностные машины / А. Гилл. — Москва: Наука, 1974.

59. Гольдштейн, В. Б. Хеш-функции для сокращения диагностической информации / В. Б. Гольдштейн, С. В. Миронов // Известия Саратовского университета. Новая серия. Серия Математика. Механика. Информатика. — 2007. Т. 7, № 2. - С. 76-81.

60. Закревский, А. Д. Логический синтез каскадных схем / А. Д. Закрев-ский. — Москва: Наука, 1981.

61. Иоффе, М. И. Оценка способности сигнатурного анализа обнаруживать ошибки заданной кратности в двоичной последовательности / М. И. Иоффе // Автоматика и телемеханика. — 1984.— № 12.— С. 110118.

62. Казьмина, С. К. Компактное тестирование / С. К. Казьмина // Автоматика и телемеханика. — 1982. — № 3. — С. 173-189.

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

64. Кирьянов, К. Г. К теории сигнатурного анализа. Техника средств связи / К. Г. Кирьянов // Радиоизмерительная техника, — 1980. — С. 146.

65. Малышенко, Ю. В. Метод сокращения объема диагностической информации, используемой для поиска неисправностей / Ю. В. Малышенко, А. X. Раздобреев // Автоматика и телемеханика. — 1977. — № 4. — С. 160-164.

66. Миронов, С. В. Об одном алгоритме для поиска маски диагностической информации / С. В. Миронов // Известия Саратовского университета. Новая серия. Серия Математика. Механика. Информатика — 2008. Т. 8, № 2. - С. 77-84.

67. Миронов, С. В. Генетические алгоритмы в задачах сокращения диагностической информации / С. В. Миронов, Д. В. Сперанский // 1нформацШно-керуючг системи на залгзничному транспор-тг. - 2006. - 4. - С. 45-48.

68. Миронов, С. В. Деревья решений в задачах сокращения диагностической информации / С. В. Миронов, Д. В. Сперанский // Радгоэлектрот и комп'ютернии системи. — 2007. — №7.— С. 147-152.

69. Миронов, С. В. Сокращение диагностической информации при тестировании дискретных устройств / С. В. Миронов, Д. В. Сперанский // Proceedings of 2007 Computer-Aided Design of Discrete Devices (CAD DD'07).- Минск: 2007.- С. 198-206.

70. Миронов, С. В. Генетические алгоритмы для сокращения диагностической информации / С. В. Миронов, Д. В. Сперанский // Автоматика и телемеханика. — 2008. — № 7. — С. 146-156.

71. Пархоменко, П. П. Основы технической диагностики / П. П. Пархоменко, Е. С. Согомонян. — Москва: Энергоиздат, 1981.

72. Сагалович, Ю. Л. Алгебра, Коды, Диагностика / Ю. JI. Сагалович. — Москва: МЦНТИ РАН, Институт проблем передачи информации, 1993.

73. Скобцов, Ю. А. Логическое моделирование и тестирование цифровых устройств / Ю. А. Скобцов, В. Ю. Скобцов. — Донецк: ИПММ Украины, ДонНТУ, 2005.

74. Смирнов, Н. И. Диагностика неисправностей в цифровой радиоаппаратуре на БИС / Н. И. Смирнов, А. А. Стручков, В. А. Суровцев // Зарубежная радиоэлектроника. — 1979. — № 1. — С. 53-60.

75. Соловьев, Н. А. Тесты (теория, построение, применение) / Н. А. Соловьев. — Новосибирск: Наука, Сибирское отделение, 1978.

76. Сперанский, Д. В. Об одном подходе к решению задач сокращения объема диагностической информации / Д. В. Сперанский // Автоматика и телемеханика. — 1984. — № 3. — С. 151-160.

77. Сперанский, Д. В. Введение в генетические алгоритмы: Учеб.пособие / Д. В. Сперанский, В. Г. Самойлов, О. В. Емельянова; Под ред. Д. В. Сперанского. — Саратов: Изд-во Саратовского ун-та, 2006.

78. Сперанский, Д. В. Улучшение точности диагностирования дискретных устройств при использовании ограниченного числа дополнительных выходов / Д. В. Сперанский, Н. К. Шатохина // Электронное моделирование. — 1982. — № 1. — С. 64-68.

79. Сперанский, Д. В. Приближенные методы решения задач оптимизации глубины диагностирования дискретных устройств / Д. В. Сперанский, Н. К. Шатохина // Многопроцессорные вычислительные структуры. — Таганрог: Изд-во ТРТИ, 1985,- С. 70-72.

80. Сперанский, Д. В. Методы оптимизации диагностической информации / Д. В. Сперанский, Н. К. Шатохина // Теоретические проблемыкибернетики.— Саратов: Изд-во Саратовского ун-та, 1986.— С. 129— 132.

81. Столов, Е. Л. Методы компактного тестирования цифровых устройств / Е. JI. Столов. — Казань: Изд-во Казанского университета, 1993.

82. Чипулис, В. П. Использование диагностической информации при контроле и поиске неисправностей дискретных устройств с учетом возможной неопределенности значений сигналов / В. П. Чипулис // Автоматика и телемеханика. — 1975. — № 8. — С. 150-157.

83. Чипулис, В. П. Методы минимизации разрешающей способности и диагностической информации / В. П. Чипулис // Автоматика и телемеханика. 1975. — № 3. - С. 133-141.

84. Чипулис, В. П. Методы предварительной обработки и формы задания диагностической информации для поиска неисправностей дискретных устройств / В. П. Чипулис // Автоматика и телемеханика. — 1977. — № 4. С. 165-175.

85. Шаршунов, С. Г. Особенности диагноза технического состояния многовыходных объектов с использованием таблиц неисправностей / С. Г. Шаршунов // Автоматика и телемеханика. — 1973. — № 12. — С. 161168.

86. Ярмолик, В. Н. Контроль и диагностика цифровых узлов ЭВМ / В. Н. Ярмолик. — Минск: Наука и техника, 1988.