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

На правах рукописи

Миронов Сергей Владимирович

РАЗРАБОТКА МЕТОДОВ СОКРАЩЕНИЯ ДИАГНОСТИЧЕСКОЙ ИНФОРМАЦИИ

01.01.09 — дискретная математика и математическая кибернетика

Автореферат диссертации на соискание учёной степени кандидата физико-математических наук

□0345ЬЬ га

г\ О

Саратов - 2008

003455679

Работа выполнена на кафедре математической кибернетики и компьютерных паук ГОУ ВПО «Саратовский государственный университет им. Н. Г. Чернышевского».

Научный руководитель: доктор технических наук,

профессор

Сперанский Дмитрий Васильевич

Официальные оппоненты: доктор технических наук,

профессор

Твердохлебов Владимир Александрович

кандидат физико-математических паук, доцент

Богомолов Алексей Сергеевич Ведущая организация: Институт проблем управления РАН

Защита состоится «25» декабря 2008 в 16 ч. 30 мин. на заседании диссертационного совета ДМ212.243.15 при Саратовском государственном университете им. Н. Г Чернышевского по адресу: 410012, г. Саратов, ул. Астраханская 83. IX корп.

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

Автореферат разослан « » ¿-сО-и 2008 г.

Учёный секретарь диссертационного совета кандидат физико-математических паук, доцент В. В. Корпев

■¿у, В.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

Одно из перспективных направлений существенного сокращения временных затрат на диагностику изделия с высокой точностью локализации неисправностей связано с использованием предварительно подготовленной диагностической информацией (ДИ) в виде так называемых словарей неисправностей. Различные варианты построения таких словарей были предложены в работах таких отечественных и зарубежных ученых как Шаршу-нов С. Г., Чипулис В. П., Тулосс Р. Э., Райан П. Г., Фукс В. К., Померанц И., Редди С. М., Ларраби Т. и другие.

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

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

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

Из сказанного выше вытекает необходимость разработки эффективных подходов к поиску единых и индивидуальных масок, с использованием которых создаются соответствующие словари неисправностей. Данной проблеме были посвящены работы Вознесенского С. С., Малышенко Ю. В., Раздобреева А. X., Сперанского Д. В., Шатохиной Н. К.

Отметим, что для решения проблемы сокращения ДИ очень хорошо зарекомендовало себя использование сигнатурных анализаторов, которые используются в основном при контроле систем. Теоретическое обоснование применения таких анализаторов и описание процесса диагностирования с их использованием было осуществлено в работах Фрооверка Р. А., Смирнова Н. И., Смита Дж. Э., Сагаловича Ю. Л., Ярмолика В. Н., Столова Е. Л., Иоффе М. И. и других. Основным достоинством таких анализаторов является простота их схемной реализации и, как следствие, высокая скорость работы. Указанные достоинства делают весьма привлекательной возможность использования сигнатурных анализаторов для решения задач локализации неисправностей. Более того, речь идет о разработке анализаторов, пригодных для получения компактных словарей неисправностей, обладающих такой же разрешающей способностью, что и исходная полная ДИ.

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

Цель работы — разработка методов сокращения ДИ, представленной в виде словарей неисправностей.

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

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

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

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

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

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

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

• разработан жадный алгоритм для поиска единой маски, который применим как для решения задачи минимизации ДИ, так и для решения задачи оптимизации ДИ;

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

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

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

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

Исследования по диссертационной работе проводились в соответствии с планами научных исследований кафедры математической кибернетики и компьютерных наук Саратовского государственного университета, в том числе по разделу «Разработка методов сокращения диагностической информации (ДИ) при тестировании дискретных устройств» темы «Разработка и применение фундаментальных методов исследования задач математического анализа, дифференциальных уравнений, дискретной математики, теории упругости и газодинамики» (шифр "Интеграл") (тем. план НИР СГУ, выполняемый по ЕЗН), теме «Исследование проблем анализа, синтеза и диагностик дискретных систем с использованием моделей конечных автомато в и графов» (тем. план НИР, выполняемый по §47), теме

«Разработка методов обеспечения отказоустойчивости и построение тестов для дискретных технических систем при наличии внешних возмущений и неопределенности в задании параметров» (грант РФФИ №05-08-18082).

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

Апробация результатов. Результаты работы докладывались и обсуждались на:

• Школе-семинаре «Перспективные системы управления на железнодорожном, промышленном и городском транспорте» (Алушта, 2006);

• Второй Международной научно-технической конференции «Dependable Systems, Services & Technologies» (Кировоград, 2007);

• Международной научной конференции «Компьютерные науки и информационные технологии», посвященной памяти профессора А. М. Богомолова (Саратов, 2007);

• Международной конференции «Крымская осенняя математическая школа-симпозиум» (Симферополь — Севастополь, 2007, 2008);

• Пятом Международном симпозиуме «East-West Design & Test Symposium» (Ереван, 2007);

• Шестой Международной конференции «Computer-Aided Design of Discrete Devices» (Минск, 2007).

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

• генетический алгоритм для решения задач минимизации и оптимизации ДИ с помощью единой маски;

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

• жадный алгоритм для поиска единой маски;

• жадный алгоритм поиска совокупности индивидуальных масок;

• метод сокращения ДИ с помощью хеш-функций.

Структура и объем диссертации. Работа состоит из введения, пяти глав, заключения и библиографии, включающей 87 наименований. Диссертация изложена на 113 страницах.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

Первая глава диссертации посвящена обзору работ по общим методам сокращения ДИ, а также методов, ориентированных на применение специальной аппаратуры. В пункте 1.1 приводится описание состава полной диагностической информации при тестовом диагностировании и рассматриваются аспекты ее использования, детально рассматривается представление ДИ в виде таблицы функций неисправностей (ТФН), описывается принцип организации словаря полной реакции (СПР). Отмечается необходимость сокращения объема полной ДИ и рассматриваются основные технологии, направленные на достижение такого сокращения. Одна из технологий, представляющая собой совокупность методов сокращения ДИ, связанных, в основном, с проектированием систем встроенного тестирования, — методов компактного тестирования, более детально рассматривается в п. 1.2.

Вторая глава диссертации содержит описание способов представления ДИ в виде различных типов словарей неисправностей и их применения при диагностировании ЦУ. Так, рассмотрены принципы построения словарей неисправностей, предложенных Тулоссом Р. Э., Ларраби Т., Боп-пана В., Фуксом В. К., Померанцем И. и др., в которых уменьшение объема достигается вследствие специальной организации информации, представленной СПР. Проведено исследование словарей неисправностей, предложенных Шаршуновым С. Г., Чипулисом В. П., Лаво Д., Арсланом Б., Ораилоглу А. и др., в которых происходит дополнительное сокращение информации за счет частичной потери диагностического разрешения. Здесь также описывается метод сокращения диагностической информации, предложенный Чипулисом В. П., базирующийся на использовании масок. Напомним основные аспекты данного метода.

Назовем точкой проверки пару

(номер тестового воздействия}:(выход).

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

образом. Каждая строка таблицы соответствует техническому состоянию. Содержимое строки таблицы, соответствующей состоянию«, € будут составлять значения точек проверки из Ь,3, взятые из строки СПР, соответствующей в порядке их следования в СПР. Построенную таким образом таблицу будем называть СПРя, что означает «словарь полной реакции, построенный по маскам из Я». Маску /г3 будем называть индивидуальной маской для каждого состояния из Б], а множество Н — множеством индивидуальных масок. Если |Я| = 1 и Л € Я, то маску к называют единой маской.

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

В п. 3.1 рассмотрены задачи, касающиеся сокращения ДИ с помощью масок:

1. Для каждого технического состояния з, найти такую индивидуальную маску Л, (единую маску К), чтобы объем СПРя был минимальным и разрешающая способность диагностирования с помощью СПРя не изменялась по сравнению с разрешающей способностью диагностирования с помощью СПР.

2. Для каждого технического состояния в, найти такую индивидуальную маску Л, (единую маску Л), чтобы объем СПРя не превышал заданной величины 2 и изменение разрешающей способности диагностирования с помощью СПРя по отношению к разрешающей способности диагностирования с использованием СПР было минимальным.

Первую из этих задач называют задачей минимизации ДИ при помощи масок, вторую — задачей оптимизации ДИ при помощи масок.

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

Введем следующие обозначения. Пусть К — число этапов эволюции, реализуемых ГА, М — число особей в популяции, У/ — объем памяти (в битах) для хранения одной особи. Тогда справедлив следующий результат.

Теорема 1. Алгоритмическая сложность одного запуска предложенного генетического aлгopumмapaвнaO(KM■(W•\S\+logM)), а объем памяти, необходимой для работы генетического алгоритма, равенО{2М\¥).

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

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

На втором этапе ГА, связанном с подбором (селекцией) особей для скрещивания, были опробованы различные методы: турнирный отбор, отбор отсечением, пропорциональный отбор, а также отбор линейным и экспоненциальным ранжированием.

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

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

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

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

Так, в табл. 1 приводятся данные об эффективности применения разработанного простого ГА для минимизации ДИ при помощи единой маски. Эти данные были получены на PC Pentium III, 1024 MHz, 256 MB RAM, при использовании оператора отбора линейным ранжированием и оператора булева скрещивания. В первых слева трех столбцах этой таблицы

Таблица 1. Результат поиска единой маски с помощью ГА

\S\ Объем полной реакции, бит Объем ДИ, бит Объем маски, бит Время работы ПГА Доля сокращенной ДИ от полной ДИ

127 40 5 080 9 48 сек 22.5%

511 256 130 816 12 6 мин 4.68%

1023 512 523 776 18 12 мин 3.51%

2047 1024 2 096 128 19 2 час 7 мин 1.85%

4095 1024 4 192 256 24 15 час 2.34%

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

Величина V(h) в последнем столбце табл. 1 показывает долю объема сокращенной ДИ от объема исходной ДИ.

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

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

В п. 3.2.2 рассматриваются возможности распараллеливания генетического алгоритма. Наиболее трудоемким этапом в ПГА для поиска маски является получение результата фитнес-функции для каждой хромосомы. В проведенных нами экспериментах была сделана попытка достичь простого ускорения этого этапа, производя вычисления фитнес-функции одновременно для нескольких хромосом. На первом этапе были проведены исследования ускорения ГА при использовании многопроцессорных ЭВМ. Результаты, приведенные в табл. 2, были получены на ЭВМ с ЦП Intel Core2Duo 2,ЗЗГГц, 2 Гб ОЗУ. Эксперименты проводились для ДИ полученной для ДУ из каталога ISCAS'85 и ISCAS'89 при моделировании одиночных неисправностей с помощью тестовых последовательностей HITEC. Была взята численность популяции — 900 особей, а процесс эволюции прерывался при достижении 300 поколений.

Таблица 2. Ускорение работы генетического алгоритма при использовании двух процессоров

Схема Объем ДИ, бит Время работы алгоритма с использованием одного процессора Время работы алгоритма с использованием двух процессоров

S298 343896 7 мин 16 с 4 мин 03 с

S344 336677 17 мин 11 с 9 мин 44 с

S526 1883172 23 мин 30 с 14 мин 03 с

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

Также были поставлены эксперименты по поиску масок с помощью ГА на многомашинных системах. В экспериментах использовались 4 базовых ЭВМ со следующими характеристиками: ЦП Intel Pentium D 2.8 ГГц (2 ядра), 1 ГБ ОЗУ, которые были объединены в локальную вычислительную сеть с пропускной способностью 100 Мбит/сек. Результаты этих экспериментов приведены в табл. 3. Данные из этих таблиц были получены при количестве этапов эволюции — 300 поколений и численности популяции:

Таблица 3. "Ускорение работы генетического алгоритма на многомашинных системах

Схема Объем ДИ, бит Время работы алгоритма с использовал нем одной двухпроцессорной малшны Время работы алгоритма с на четырех двухпроцессорных машинах Ускорение

31488 30232800 4 час 10 мин 1 час 14 мин 57 с 3,33

С499 5799680 53 мин 17 с 17 мин 41 с 3,01

С1355 12843072 5 час 15 мин 50 с 1 час 21 мин 42 с 3,86

С2670 58705080 13 час 57 мин 3 час 43 мин 15 с 3,74

для схемы С2670 — 100 особей, для всех остальных ДУ — 500 особей.

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

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

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

Теорема 2. Объем маски, полученной с помощью алгоритма 1, не превышает величину

|5|1О82|5Г

+ Ы 2

где М — объем минимальной маски заданного СПР.

Теорема 3. Пусть для СПР существует оптимальная маска к объема г, а р — величина диагностического разрешения при диагностировании с

использованием СПРТогда, если к — маска объема г, найденная с помощью алгоритма 1, и р — диагностическое разрешение при диагностировании с помощью СПРь,, то справедливо следующее неравенство

1-1).

Теорема 4. Вычислительная сложность алгоритма 1 оценивается величиной 0(|5|2т|т|). Величина необходимого для функционирования алгоритма дополнительного объема памяти равна 0(|5'|).

Численные эксперименты показали высокую эффективность предложенного алгоритма для решения как задачи минимизации, так и задачи оптимизации ДИ. Так, в табл. 4 приводятся результаты применения алгоритма 1 для решения задачи минимизации ДИ, полученной с помощью тестовых последовательностей Н1ТЕС для некоторых дискретных устройств из каталога ШСАЗ'вЭ (их названия приведены в 1-ом столбце таблицы).

Таблица 4. Результаты поиска индивидуальной маски с помощью алгоритма 1

Схема Объем ДИ, бит Объем маски, бит Объем сокращенной ДИ, бит Доля сокращенной ДИ от полной ДИ Время работы алгоритма, сек

8298 343896 61 10797 3,16% 1,464

Б444 25804ВО 60 11460 0,45% 10,224

Б526 1883172 38 5244 0,28% 5,784

8832 15554160 253 181907 1,17% 324,432

Б953 105294 91 29666 28,26% 0,648

31423 220500 93 27249 12,40% 1,368

81488 30232800 384 521856 1,73% 1300,056

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

Теорема 5. Суммарный объем совокупности индивидуальных масок, полученной с помощью алгоритма 2, не превышает величины

М • (1 + 1п(|£| — 1)),

где М — суммарный объем совокупности минимальных индивидуальных масок заданного СПР.

Теорема 6. Вршенная сложность алгоритма 2 составляетО(\3\3т\т1). Объем дополнительной памяти, необходимой для функционирования алгоритма 2 оценивается величиной 0(|5'|2).

В табл. 5 приведены результаты работы алгоритма 2 на ДИ, составленной для ДУ из каталога ШСАЭ'вЗ.

Таблица 5. Результаты поиска совокупности индивидуальных масок с помощью алгоритма 2

Схема Объем ДИ, биг Объем совокупности масок, бит Объем максимальной маски, бит Средний объем маски, бит Объем сюваря неисправностей, бит Доля сокращенной ДИ от полной ДИ Время работы алгоритма, сек

Б298 343836 477 33 2.68 6732 1.96% 1.758

Б444 2580480 527 40 2.74 9005 0.35% 12.402

Б526 1883172 367 17 2.64 6286 0.33% 4.851

Б832 15354160 2155 197 2.99 40230 0.26% 172 272

Б1423 220500 960 57 3.27 12399 5.62% 0.438

81488 30232500 4334 313 3.19 80473 0.27% 1017.504

Из сравнения объемов словарей неисправностей, полученных в результате сокращения ДИ с помощью единой маски и набора индивидуальных масок (табл. 4 и табл. 5, соответственно), можно сделать вывод, что сокращение информации с помощью индивидуальных масок в большинстве случаев происходит значительно эффективнее.

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

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

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

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

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

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

Эксперименты показали, что объем сокращенной с помощью хеш-функций ДИ в большинстве случаев составляет менее процента от исходного объема. С точки зрения числа подходов к подбору хеш-функции наиболее привлекательной является функция, порожденная одновходным сигнатурным анализатором. Средние значения результатов такого подбора для некоторых ЦУ из каталога ¡ЭСЛЗ'вО приведены в табл. 6.

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

да Объем ДИ, бит г Объем сокращенной ДИ, бит Доля сокращенной ДИ от полной ДИ Время подбора /г, мс

Б298 343896 13,3 2367,4 0,69% 231,24

Б344 336677 14,2 3422,2 1,02% 265,98

Б444 2580480 14,1 2707,2 0,10% 1944,69

Б526 1883172 12,8 1779,2 0,09% 1440,39

8832 15554160 17,6 12672,0 0,08% 17568,15

81423 220500 14,9 4380,6 1,99% 164,58

81488 30232800 19,1 25976.0 0,09% 40219,38

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

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

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

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

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

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

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

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

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

СПИСОК ОПУБЛИКОВАННЫХ РАБОТ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

(первые три опубликованы в журналах. входящих в перечень ВАК РФ)

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

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

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

\s

\ J

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

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

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

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

[8] Миронов, С. В. Генетические алгоритмы для сокращения диагностической информации / С. В. Миронов, Д. В. Сперанский // Компьютерные науки и информационные технологии. Тезисы докладов Международной научной конференции, посвященной памяти профессора А. М. Богомолова. - Саратов: 2007. — С. 82-83.

[9] Mironov, S. V. One approach to fault dictionary size reduction / S. V. Mironov, D. V. Speranskiy // Proceedings of IEEE East-West Design & Test International Symposium (EWDTS'07). - Lviv: 2008. - Pp. 295-300.

Подписано в печать 19.11.08. Формат 60х 84 1/16. Бумага офсетная. Гарнитура Компьютер Модерн. Печать офсетная. Усл. печ. л. 1,0. Тираж 100. Заказ

Типография Издательства Саратовского университета. 410012, Саратов, Астраханская, 83.

Введение

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].

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

Заключение

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

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

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

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

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

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.