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

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

Седов Юрий Владимирович

ОБЕСПЕЧЕНИЕ РАБОТОСПОСОБНОСТИ СИСТЕМ С ПРОИЗВОЛЬНЫМ ДОСТУПОМ И САМОПРОВЕРЯЕМОСТИ ЛОГИЧЕСКИХ СХЕМ

05.13.01-"Системный анализ, управление и обработка информации (в отраслях информатики, вычислительной техники и автоматизации)"

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

Томск-2004

Работа выполнена в Томском государственном университете.

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

доктор технических наук, профессор

Матросова Анжела Юрьевна

Официальные оппоненты:

доктор технических наук, профессор

Евтушенко Нина Владимировна

кандидат технических наук, доцент

Салит Владимир Викторович

Ведущая организация:

Томский государственный Университет Систем Управления и Радиоэлектроники (ТУСУР), г. Томск.

Защита состоится:

29 апреля 2004 г. в 1030 на заседании диссертационного совета Д 212.267.12 при Томском государственном университете по адресу: 634050, г. Томск, пр. Ленина, 36.

С диссертацией можно ознакомиться

В научной библиотеке Томского государственного университета

Автореферат разослан: «_25_» марта 2004 г.

Ученый секретарь

диссертационного совета, д.т.н., профессор

Общая характеристика работы

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

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

Задача увеличения выпуска исправных микросхем известна как задача повышения процента выхода годных микросхем. Один из путей ее решения - разработка логической структуры СБИС, позволяющей использовать часть устройства, оставшуюся исправной. Разработка таких структур, как правило, выполняется для некоторого заданного класса устройств и позволяет уменьшить стоимость производимых СБИС путем увеличения процента выхода годных микросхем.

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

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

Цель работы.

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

Методика исследования.

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

Научная новизна.

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

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

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

Достоверность полученных результатов.

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

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

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

2. Предлагаемый в работе метод обеспечения самопроверяемости синхронных последовательностных схем хорошо сочетается с широко распространенными в САПР методами синтеза дискретных устройств. Это позволяет воспользоваться существующими САПР для разработки самопроверяемых дискретных устройств.

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

Реализация и внедрение полученных результатов.

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

1. Госбюджетная тема Сибирского физико-технического института при ТГУ (СФТИ), программа "Исследование и разработка новых методов электромагнитного контроля и диагностики материалов, сред и

технических систем", 1995-2000 гг., раздел "Разработка методик и аппаратуры исследований".

2. Межвузовская научно-техническая программа "Конверсия и высокие технологии. 1994-2000 гг.", проект №95-1-21 и №59-1-7 "Информационные компьютерные технологии дискретного математического моделирования, анализа, синтеза и тестирования сверхскоростных интегральных схем логического управления".

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

4. Проекты министерства образования по разделу "Автоматика и телемеханика":

"Элементы, узлы и устройства автоматики, телемеханики и вычислительной техники", 1995-1996 гг.;

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

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

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

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

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

1. Международная конференция "Всесибирские чтения по математике и механике" (Россия, Томск, 1997).

2. III Международная конференция "Новые информационные технологии в исследовании сложных структур", (Россия, Томск, 2000).

3. 8-th IEEE International On-Line Testing Workshop, (Bendor, France, July 2002).

4. IV Всероссийская конференция с международным участием "Новые информационные технологии в исследовании сложных структур", (Россия, Томск, 2002).

Структура и объем диссертации.

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

числе: титульный лист - 1 стр., оглавление - 2 стр., основной текст - 92 стр., библиография из 95 наименования - 10 стр., заключение - 1 стр.

Содержание работы

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

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

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

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

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

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

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

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

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

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

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

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

Пусть адресное пространство устройства, образует булево пространство В" (назовем его полным адресным пространством) и пусть Е

- множество адресов неисправных элементов устройства, тогда ЕР—Е= Е

- множество адресов исправных элементов. Пусть т — ] [. Назовем

булево пространство сокращенным адресным пространством.

Предлагаемый метод частичного восстановления работоспособности устройства состоит в выборе исправных элементов с адресами из Е (образующими подмножество Е' С Е ) и отображении адресов сокращенного адресного пространства на множество т.е.

Вт Е'. Отображение может быть задано в виде пары двоичных матриц, где построчно перечислены (в виде булевых векторов) адреса из сокращенного адресного пространства Д"7 и адреса множества Е'. Такое

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

Поскольку для каждого из С^ подмножеств Е'с1Е возможно 2т!

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

В' качестве элементного базиса предлагается использовать программируемые логические матрицы (ПЛМ). Каждая ПЛМ характеризуется числом входов, числом выходов и числом промежуточных шин и позволяет реализовать систему ДНФ с соответствующим числом входных переменных, функций и различных конъюнкций. Число используемых входов определяется размерностью сокращенного адресного пространства, число используемых выходов -размерностью полного, а число задействованных промежуточных шин определяется числом конъюнкций в системе ДНФ булевых функций.

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

есть систему, содержащую наименьшее число конъюнкций.

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

громадного числа отображений, перебрать которые не представляется возможным;

сложности представления < самого отображения при больших значениях размерности т сокращенного адресного пространства (а именно такие ситуации интересны на практике);

поиска кратчайших систем ДНФ для заданных отображений.

Вот почему предлагается от рассмотрения всевозможных

отображений пе рейти к рассмотрению отображений, имеющих

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

В этом случае задача может быть поставлена следующим образом. Среди всех разбиений всех подмножеств Е' на интервалы требуется найти разбиение /? = {/(,..на минимальное числ^^нтервалов

(назовем его минимальным разбиением) и отображение Р минимального разбиения Я на множество гДе Q = \J\^•••^Jк\ ' разбиение булева

пространства ЕС на к интервалов, такое что |/,| = , »=1,к. Введенное отображение Р '.К-^О, будем называть интервальным, а задачу поиска минимального разбиения Я - задачей его минимизации.

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

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

Теорема 1

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

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

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

На этом основан алгоритм поиска минимального интервального отображения.

Запишем функцию /ц, принимающую значение 1 на множестве адресов неисправных элементов системы, в виде совершенной ДНФ Инверсия ДНФ позволяет найти множество максимальных интервалов

не содержащих адресов неисправных элементов устройства в виде сокращенной ДНФ функции /¡¡.

Рис.1 Представление интервального отображения дихотомическим

деревом

Алгоритм поиска минимального интервального отображения - Пусть S-множество максимальных интервалов функции представляющей адреса исправных элементов, и=1.

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

2. Размечаем дерево произвольным образом. Разметка, образует разбиение Q булева пространства ¡Г.

3. Пробуем найти в систему интервалов Я, эквивалентную Q. Если это удалось, то кратчайшая система интервалов построена и представляется парой систем Иначе, переходим к п.2.

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

Алгоритм построения минимизированного интервального отображения

1. Находим инверсию ДНФ ЕУ^ в виде безызбыточной ортогональной ДНФ. S-набор интервалов, соответствующих конъюнкциям ДНФ.

2. Начинаем построение с дерева, состоящего из единственной корневой вершины.

3. На каждом ярусе, стараемся приписать концевой вершине интервал из 5". Приписанные интервалы из вычеркиваются.

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

Сравнение алгоритмов показало, что среднее число интервалов в разбиениях, построенных приближенным методом на 10-20% больше среднего числа интервалов в разбиениях, найденных точным методом. В то же время, использование точного метода на больших размерностях и при большом количестве неисправных элементов требует больших вычислительных затрат.

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

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

При проектировании самопроверяемых устройств стремятся минимизировать аппаратурные затраты как на самопроверяемое устройство, так и на детектор кодов.

Синхронное последовательностное устройство будем представлять в виде, изображенном на рис.2. Здесь X = {х|,...хл}- переменные,

сопоставляемые входам,

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

выходах комбинационной схемы К.

Рис.2. Представление синхронного последовательностного устройства

Комбинационная схема К реализует систему Р\Х, 2) ИЗ (т+р) булевых функций от (л+р) переменных. В присутствии существенной неисправности V, уеК,ГДе К—предполагаемое множество структурных неисправностей схемы, комбинационная схема К реализует систему

Fv(л^.z),такую, что р{х,г)*Р*{х,г).

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

Определение!. Будем говорить, что вектор а предшествует вектору Р (ар), а =а1,...а„, Р = Р],...Р„, если выполняется условие

Определение 2. Множество булевых векторов называется неупорядоченным кодом, если для любой пары векторов а, Р из этого множества выполняется условие: либо а < р, либо а < Р.

Определение 3. Система булевых функций Ж монотонна, если для любой пары булевых векторов- а,Р длины п, таких, ЧТО а^Р выполняется условие

Рассмотрим различные системы булевых функций с

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

Определение 4. Если для любого а, Р|=Л(а), Р2=Л[а), Р| £ Рз, тогда р]<р2,р! поглощаетсяР^.

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

Пусть Л"* является подмножеством булевых переменных

булевы векторы размерности

Определение 5. Если для любой компоненты / соответствующей переменной а по остальным компонентам векторы не

отличаются тогда,

Определение 6. Система Ж частично монотонна на множестве

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

выполняется условие На основе этих определений вводится понятие функциональной А,Б-неисправности.

Рассмотрим систему булевых функций Ж частично монотонную по переменным, сопоставляемых линиям обратных связей (переменным множества Ъ), и некоторую неисправность V. Пусть V - система, соответствующая неисправности и также частично монотонна по переменным множества Ъ.

Определение 7. Если /•**</** (р ПОГЛОЩает /•*), то назовем неисправность v А-неисправностью. Если /•" > ^ (/•* поглощает Г), то назовем неисправность v Б-неисправностью.

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

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

В результате получаем систему Ж булевых функций, частично монотонную по переменным множества Z.

В работе показывается, что структурные неисправности схемы, реализующей систему F, проявляют себя как А,Б-неисправности, при условии, что к системе применен широко распространенный метод многоуровневого синтеза.

Определенне 8. Представление ДНФ И В виде .0 = V , где остаток от деления, называется

делением ДНФ Б.

Если ДНФ В нельзя представить в виде: Л = где К -

элементарная конъюнкция, то говорят, что В не разложима по конъюнкциям.

Определение 9. Главные делители ДНФ /) есть такие ДНФ что . .........Я = и Д,...„А, не

разложимы по конъюнкциям.

Главные делители Оц,.../^, ДНФ D называются ядрами этой ДНФ, а соответствующие им частные (конъюнкции) — соядрами.

Процедура многоуровневого синтеза состоит из следующих шагов:

Шаг1. Факторизационная минимизация исходной системы

ДНФ.

В качестве факторов системы рассматриваются ядра или соядра системы, при этом, некоторый фактор С порождает новую систему ДНФ после замены фактора С переменной и в ДНФ системы и введения в систему нового уравнения сопоставляемая фактору ДНФ.

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

Шаг 2. Построение схемы в промежуточном базисе по

минимизированной системе ДНФ.

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

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

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

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

Теорема 2. Одиночная константная неисправность полюса схемы в реальном базисе есть А,Б-неисправность.

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

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

Допускаются следующие неисправности синхронной

последовательностной схемы: одиночные константные неисправности на полюсах базисных элементов комбинационной схемы К (комбинационной составляющей синхронной последовательностной схемы) и одиночные константные неисправности на полюсах триггеров в линиях обратных связей. Последние также являются А,Б-неисправностями.

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

установочным сигналом. Элементы у|.....у* этой последовательности

порождают последовательность векторов, представляющих

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

Комбинационная схема К (Рис.2) реализует систему из (т+р)

булевых функций (п+р) аргументов. /7"(А',2) — аналогичная система, реализуемая схемой в присутствии неисправности V, то есть схемой ¡С.

Пусть а" -последовательность, порождаемая схемой К1".

Теорема 3.. Для А (Б)-неисправности аУ<а (а^а*).

Выделим из системы F подсистему ф, реализуемую на выходах синхронной последовательностной схемы.

Теорема 4. Для А,(Б)- неисправности ф^а"^ ф(а) (ф(а)< (ф"(аУ)).

Следствие. А,Б-неисправность либо не проявляется на выходах синхронной последовательностной схемы, либо проявляется на выходах монотонно.

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

Рис.3. Самопроверяемое последовательностное устройство с наблюдением за выходами

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

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

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

неисправность из V. Обозначим через V" кратную неисправность, образованную добавлением систему булевых функций,

реализуемую схемой К в присутствии неисправности V.

Теорема 5. Если добавляемая к У неисправность v является А (Б)-неисправностью, то фГ (а'^ф (а) ((р (а)<фК"(а'')).

Следствие. Неисправность V" либо не проявляется на выходах синхронной последовательностной схемы, либо проявляется на выходах монотонно.

Заключение

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

На защиту выносятся:

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

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

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

4. Метод обеспечения самопроверяемости синхронных последовательностных схем, хорошо сочетаемый с широко распространенными в САПР методами синтеза дискретных устройств. Это позволяет использовать существующие САПР для разработки самопроверяемых синхронных последовательностных устройств.

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

Список публикаций автора по теме диссертации

1. Матросова А.Ю., Седов Ю.В. Способ восстановления микросхем памяти с произвольным доступом // Доклады всероссийской конференции "Новые информационные технологии в исследовании дискретных структур". Екатеринбург, 1996.-С. 131-137.

2. Matrosova A. Yu., Ostanin S. A., Sedov Yu. V. Functional Properties of Faults on Self-checking FSM Design with Observing only FSM Outputs // Proc. of the 3d International Conference "Computer-Aided Technologies in Applied Discrete Mathematics", September 2000, Tomsk. - P.209-215.

3. АЛО. Матросова, Ю.В. Седов О свойствах неисправностей, порожденных многоуровневыми методами синтеза, примененными к частично монотонным системам булевых функций // Материалы 4й Всероссийской конференции с международным участием "Новые информационные технологии в исследовании сложных структур", Томск, Сентябрь, 2002. - С.287-292.

4. Ю.В. Седов К проблемам частичного восстановления работоспособности дискретных систем с произвольным доступом // Вестник ТГУ, 2002. - С.91-95.

5. A.Matrosova, V.Andreeva, Yu.Sedov Survivable Discrete Circuits Design // Proc. of 8-th ШЕЕ International On-Line Testing Workshop, Bendor, France, July 2002. -P.6-9.

6. Матросова А. Ю., Андреева В. В., Останин С. А., Седов Ю. В. Автоматизированный синтез самопроверяемых синхронных последовательностных схем (синхронных автоматов) // Сборник докладов международной конференции «Идентификация систем и задачи управления» (SICPRO'03), 29-31 января 2003, Москва, Россия. -С.1756-1767.

7. Matrosova A., Andreeva V., Goloubeva О., Nikitin К., Ostanin S., Sedov Yu. Self-Checking and Fail-Safe Synchronous Sequential Circuit Design // Радиоэлектроника и информатика, №3,2003, - C.I07-112.

К» - 5909

Тираж ПО. Заказ 233. Томский государственный университет систем управления и радиоэлектроники пр. Ленина, 40

ВВЕДЕНИЕ.

1. ОБЗОР МЕТОДОВ ОБЕСПЕЧЕНИЯ РАБОТОСПОСОБНОСТИ СИСТЕМ С ПРОИЗВОЛЬНЫМ ДОСТУПОМ и САМОПРОВЕРЯЕМОСТИ ЛОГИЧЕСКИХ СХЕМ.

1.1. Введение.

1.2. Обзор методов восстановления поврежденных систем с произвольным доступом.

1.2.1. Статическое резервирование.

1.2.2. Динамическое резервирование.

1.2.3. Гибридная избыточность.

1.2.4. Использование резервирования для восстановления поврежденных систем с произвольным доступом.

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

1.3.1. Самотестируемые схемы.

1.3.2. Самопроверяемые схемы.

1.4. Выводы.

2.ЧАСТИЧНОЕ ВОССТАНОВЛЕНИЕ РАБОТОСПОСОБНОСТИ ДИСКРЕТНЫХ СИСТЕМ С ПРОИЗВОЛЬНЫМ ДОСТУПОМ.

2.1. Введение.

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

2.3. Минимизация отображения Р.

2.3.1. Точный метод.

2.3.2. Построение минимизированного отображения Р.

2.3.3. Сравнение алгоритмов.

2.4. Выводы.

3. ЧАСТИЧНО МОНОТОННЫЕ СИСТЕМЫ И А ,Б-НЕИСПРАВНОСТИ.

3.1. Введение.

3.2. Монотонные и частично монотонные системы.

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

3.4. Многоуровневые методы синтеза.

3.5. Выводы.

4. ПРОЯВЛЕНИЕ А,Б-НЕИСПРАВНОСТЕЙ В СИНХРОННЫХ ПОСЛЕДОВАТЕЛЬНОСТНЫХ УСТРОЙСТВАХ.

4.1. Введение.

4.2. Проявление А,Б-неисправностей в самопроверяемых синхронных последовательностных схемах.

4.3. Выводы.

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

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

Задача увеличения выпуска исправных микросхем известна как задача повышения процента выхода годных микросхем. Один из путей ее решения -разработка логической структуры СБИС, позволяющей использовать часть устройства, оставшуюся исправной. Разработка таких структур, как правило, выполняется для некоторого заданного класса устройств и позволяет уменьшить стоимость производимых СБИС путем увеличения процента выхода годных микросхем.

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

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

Цель работы

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

Методы исследования

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

Научная новизна

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

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

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

Достоверность полученных результатов

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

Практическая ценность

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

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

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

Реализация полученных результатов

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

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

2. Межвузовская научно-техническая программа "Конверсия и высокие технологии. 1994-2000 гг.", проект №95-1-21 и №59-1-7 "Информационные компьютерные технологии дискретного математического моделирования, анализа, синтеза и тестирования сверхскоростных интегральных схем логического управления".

3. Федеральная целевая программа "Интеграция". Раздел "Прикладная дискретная математика".

4. Проекты министерства образования по разделу "Автоматика и телемеханика":

Элементы, узлы и устройства автоматики, телемеханики и вычислительной техники", 1995-1996 гг.;

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

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

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

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

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

1. Международная конференция "Всесибирские чтения по математике и механике" (Россия, Томск, 1997);

2. III Международная конференция "Новые информационные технологии в исследовании сложных структур" (Россия, Томск, 2000).

3. 8-th IEEE International On-Line Testing Workshop (Bendor, France,

2002).

4. IV Всероссийская конференция с международным участием "Новые информационные технологии в исследовании сложных структур" (Россия, Томск, 2002).

Структура и объем диссертации

Диссертация состоит из введения, 4 глав, заключения и списка используемой литературы. Диссертация содержит 18 рисунков и 8 таблиц. Объем диссертации составляет 117 стр., в том числе: титульный лист - 1 стр., оглавление — 2 стр., основной текст — 92 стр., библиография из 95 наименования - 10 стр., заключение - 1 стр.

4.3. Выводы

1. Установлено, что А,Б-неисправности могут проявляться на выходах синхронной последовательностной схемы только как монотонные неисправности.

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

3. Если структурные неисправности самопроверяемой синхронной последовательностной схемы являются А,Б-неисправностями, достаточно подключать детектор кодов только к выходам схемы, а не к выходам и линиям обратных связей, как это обычно делается. Такая возможность позволяет применять более простые детекторы кодов и, следовательно, сокращать аппаратурные затраты в системе: самопроверяемая схема, детектор кодов.

1. Обеспечение качества микроэлектронных устройств // Радиоэлектроника (состояние и тенденции развития) обзор по материалам зарубежной печати, ч.1,2, 1983.

2. Zorian Y. Yield Improvement and Repair Trade-Off for Large Embedded Memories // Design, Automation and Test in Europe.- March 27, 2000. pp. 69-72.

3. Stapper С. H., McLaren A. N., Dreckmann M. Yield Model for Productivity Optimization of VLSI Memory Chips with Redundancy and Partially Good Product // IBM Journal of Research and Development, 1980, v.24, N 3, pp.398410

4. Schuster S.E. Multiple word/bit line redundancy for semiconductor memories // IEEE Journal of Solid-State Circuits, 1978, v.SC-13, N 5, pp.698-703

5. Blanks H. S. The temperature dependence of component failure rate // Microelectronics and Reliability, 1980, v.20, N 3, pp.297-307

6. Bossen D. C., Hsiao M. Y. A System Solution to the Memory Soft Error Problem // IBM Journal of Research and Development, 1980, v.24, N 3, pp.390-398

7. Anderson A., Lee P. Fault tolerance: Principles and Practice. Prentice Hall, 1980.

8. Davies D., Wakerley J.F. Synchronization and matching in redundant systems // IEEE Trans. Computers, C-27 June 1978 - pp.531-539.th

9. Lewis D.W. A fault tolerant clock using stand-by sparing // Proc. 9 Int. Symp. Fault-Tolerant Computing, 1979, pp.33-40.

10. FTSC. The fault-tolerant spaceborne computer. Digest 6th Int. Symp. Fault-Tolerant Computing, 1976, pp. 129-147.

11. Ball M., Hardie H. Majority voter design considerations for TMR computers // Computer Design, April, 1969, pp. 100-104.

12. Васильев Н.П. и др. Самовосстанавливаемая управляющая ВС // В книге "III Всесоюзное совещание по технической диагностике". М., Наука, 1975.

13. Pradah D.K. Redundancy schemes for Recovery. Univ. of Massachusetts, 1989.

14. Веселовский Г.Г., Каравай М.Ф., Кузнечик С.И. Коммутационные сети в МВС с общим управлением (анализ современного состояния) // Автоматика и телемеханика, N2, 1988 г.

15. Toy W.N. Fault-tolerant design of local ESS processors. // Proc. IEEE 66, October 1978, pp.1126-1145.16.1hara H., Fukuoka K., Kubo Y., Yokota S. Fault-tolerant computer system with three symmetric computers // Proc. IEEE 66, October 1978, pp.1160-1177

16. Katsman J.A. A fault-tolerant computing system // Proc. 11th Int. Conf on Syst. Sciences, Hawaii, Jan.1978, 85-102.

17. Cochi В., Reliabilty modeling and analysis of hybrid redundancy // Proc. 5th Int. Symp. Fault-Tolerant Computing, 1975, 569-577.

18. Siewiorek D.P., McCluskey E.J. An iterative cell switch design for hybrid redundancy // IEEE Trans. Computers, C-22, March 1973 pp.290-297.

19. Mathur F.P. On reliability modelling and analysis of ultra-reliable fault-tolerant systems. // IEEE Trans. Computers, C-20, November 1971 pp.1376-1382.

20. Patent N 4047163 USA / Fault-tolerant cell addressable array.-September 6, 1977

21. Patent N 4748597 USA / Semiconductor memory device with redundancy circuits.- May 31, 1988

22. Patent N 6484271 USA / Memory redundancy techniques.- November 19, 2002

23. Patent N 5889711 USA / Memory redundancy for high density memory.- March 30, 1999

24. Patent N 5313424 USA / Module level electronic redundancy.-May 17, 1994

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

26. Lala, Parag К. Self-checking digital design // Academic press 2001.

27. McCluskey E. J. Built-in Self-Test Structures// IEEE Design & Test of Computers. -April 1985. -Pp. 21-36.

28. Agrawal V. D., Kime C. R., Saluja К. K. A Tutorial on Built-In-Self-Test, Part 1: Principles// IEEE Design & Test of Computers. -Vol.10, -№1. -1993. -Pp. 73-82.

29. Agrawal V. D., Kime C. R., Saluja К. K. A Tutorial on Built-In-Self-Test, Part 2: Applications//IEEE Design & Test of Computers. -Vol.10, -№2. -1993. Pp. 69-77.

30. Horwarth J. Checking Sequential Logic Circuits/ US PS 4556976, G06F 11/00. -1985.

31. Siewiorek D. P., Schwarz R. S. The Theory and Practice of Reliable System Design. -Bedford: Digital Press. -1982.

32. Sellers F. F., Hsiao M. J., Bearnson L. W. Error Detecting Logic for Digital Computers. -New York: McGraw-Hill. -1968.

33. Betrand J. C., Gambiasi N., Mercier J. J. Totally Self-Checking Sequential Circuits// Proc. Int. Sympos. «Discrete Systems». -Riga: Zinatne. -Bd. 2. -1974. -pp. 36-44.

34. Carter W. C., Schneider P. R. Design of Dynamically Checked Computers// JFIP Congress. -1968. -pp. 878-883.

35. Согомонян E. С. Построение дискретных устройств с диагностикой в процессе функционирования// Автоматика и телемеханика. -№11. -1970. -с. 153-160.

36. Аксенова Г. П., Согомонян Е. С. Синтез схем встроенного контроля для автоматов с памятью// Автоматика и телемеханика. -№9. -1971. -с. 170-179.

37. Lala, Parag К. Self-checking digital design // Academic press 2001.

38. Anderson D.A., G.Metze Design of totally self-checking check circuits for m-out-of-n codes // IEEE Trans.Comput., pp 263-269, March 1973.

39. Marouf M.A., Friedman A.D. Efficient design of self-checking checker for any m-out-of-n code // IEEE Trans. Comput., pp 482-490, June 1978.

40. Mak G.P., Abraham J.A., Davidson E.S. The design of PLAs with concurrent error detection // Proc. 12th Int. Symp. on Fault-Tolerant Computing, Milan, Italy, 1982, pp.202-210.

41. Goessel M., Sogomonyan E. S. Code Disjoint Self-Parity Combinational Circuits for Self-Testing, Concurrent Fault Detection and Parity Scan Design// 12th IEEE VLSI Test Symp. -1994. -p. 151-157.

42. Gossel M., Sogomonyan E. S. Self-Parity Combinational Circuits for Self-Testing, Concurrent Fault Detection and Parity Scan Design// Procceedings VLSI 93. -1993.- pp. 311-318.

43. Wong C.Y., Fuchs W.S., Abraham J.A., Davidson E.S. The design of a microprogram control unit with concurrent error detection // Proc. of 12th Int. Symp. on Fault-Tolerant Computing, Milan, Italy, 1982, pp.476-482.

44. Bose В., Rao T.R.N. Theory of unidirectional error correcting/detecting code // IEEE Trans .Computers, C-31, N6 1982 - pp.521-530.

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

46. Berger J. М. A Note on Error Detection Codes for Asymmetric Channels, Inform. Contr., -vol.4, -March, -1961, -pp. 68-73.

47. Каравай М.Ф., Согомонян E.C., Шагаев И.А. Отказоустойчивые вычислительные системы // Журнал "Успехи наук", 1990, N26.

48. M.Choi, N-J.Park Optimal Spare Utilization in Repairable and Reliable Memory Cores // Proc. of the 2003 Int. Workshop on Memory Technology, Design and Testing.

49. Subhasish Mitra, Edward J. McCluskey Design Diversity for Concurrent Error Detection in Sequential Logic Circuts // 19th IEEE VLSI Test Symposium, April 2001.

50. Tohma Y., Ohyama Y. Realization of fail-safe sequential machines by using a k-out-of-n code // IEEE Trans. Сотр. -1971, pp. 1270-1275.

51. Bolchini C., Montandon R., Salice F., Sciuto D. Self-Checking FSMs Based on a Constant instance State Encoding// Int. Symp. on Defects on Fault Tolerance in VLSI Systems. -1998, November.

52. Bolchini, C., Montandon R., Salince F., Sciuto D. Design of VHDL-Based Totally Self-Checking Finite State Machines and Data-Path Descriptions // IEEE Transaction on VLSI Systems, v.8, No. 1, 2000.

53. Diaz M., Geffroy J.C., CourvoisierM. On-Set Realization of Fail-Safe Sequential Machines // IEEE Trans, on Сотр., v.C-23, pp. 133-138, Feb. 1974.

54. Diaz M. Design of Totally Self-Checking and Fail-safe Sequential Machines // Proc. 4th Int. Fault Tolerant Computing Symposium, Urbana, IL, 1974.

55. Лосев B.B., Конопелько B.K., Урбанович П.П. Системы памяти на базе запоминающих устройств с дефектными элементами // Зарубежная электронная техника, N9, 1982, сс.3-33.

56. Touba, N.A., McCluskey E.J. Logic Synthesis of Multilevel Circuits with Concurrent Error Detection // IEEE Transactions on Computer-Aided Design, v. 16, N 7, pp. 783-789, July 199764.3акревский А.Д. Логический синтез каскадных схем. M.: Наука 1981 г.

57. Баранов С.И., Скляров В.А. Цифровые устройства на программируемых БИС с матричной структурой. М.: Радио и связь 1986 г.бб.Закревский А.Д., Балаклей Л.И., Елисеева H.A. и др. Синтез асинхронных автоматов на ЭВМ. -Минск: Наука и техника, -1975.

58. R.Murgai, R. Brayton, A. Sangiovanni-Vincentelli. Logic Synthesis for Field Programmable Gate Arrays. Cluver Academic Publishers, 1995, 425p.

59. Яблонский C.B., Гаврилов Г.П., Кудрявцев В.Б. Функции алгебры логики и классы Поста. М.: Наука 1966 г.

60. Нигматуллин Р.Г. Сложность булевых функций. М.: Наука 1991 г.

61. Матросова А.Ю. Алгоритмические методы синтеза тестов. Издательство ТГУ.- 1990 г.

62. Матросова А. Ю., Останин С. А. К синтезу самопроверяемых комбинационных схем// Международная конференция «Всесибирские чтения по математике и механике», Россия, Томск, Тезисы докладов том 1 «Математика», -1997. -160-161 с .

63. Матросова А. Ю., Останин С. А. К синтезу самопроверяемых комбинационных схем// Международная конференция «Всесибирские чтения по математике и механике», Россия, Томск, Избранные доклады том 1 «Математика», -1997. -179-185 с .

64. Горяшко А.П. Синтез диагностируемых схем вычислительных устройств // М.: Наука 1987.

65. Матросова А.Ю., Останин С.А., Паршина Н.А. К синтезу контролепригодных комбинационных устройств// Автоматика и телемеханика. -№2. -1999. -С. 129-137.

66. Prabhu A.M. LOGOPT a multi-level logic synthesis and optimization system // Custom Integrated Circuit Conference, 1989.

67. R.Murgai, Y.Nishizaki, R. Brayton, A. Sangiovanni-Vincentelli. Logic Synthesis for Programmable Gate Arrays // 27th ACM/IEEE Design Automation Conference 1990 - pp.620-625.

68. Матросова А.Ю., Останин C.A. Синтез самопроверяемых синхронных последовательностных устройств// Материалы международной сибирской конференции по исследованию операций, Новосибирск, 22-27 июня, -1998. -132 с.

69. Матросова А.Ю., Останин С.А. Синтез самопроверяемых синхронных автоматов// Труды международной конференции «Новые информационные технологии в науке, образовании, телекоммуникации и бизнесе», часть 2, Украина, Крым, Ялта-Гурзуф, 15-24 мая. -1998.

70. Matrosova A.Yu., Ostanin S.A. Self-Checking Synchronous Sequential Circuit Design for Unidirectional Error// Compendium of papers. IEEE European Test Workshop 1998, May 27-29, -1998, Sitges, Barcelona, Spain.

71. Matrosova A. Yu., Ostanin S.A. Self-Checking Synchronous FSM Network Design// Compendium of papers. 4th IEEE International On-Line Testing Workshop, July 6-8, 1998, Capri, Italy.

72. Levin I., Matrosova A. Yu., Sinelnikov V., Ostanin S. A. Totally Self-Checking FPGA based FSM //5th IEEE Intl. On-Line Testing Workshop, Rhodes, Greece, July 1999.

73. Матросова А.Ю., Останин С.А. Синтез самопроверяемых синхронных устройств и сетей из них// Материалы конференции "Новые информационные технологии в исследовании дискретных структур", Екатеринбург, -1998, -173-179 с.

74. Matrosova A. Yu., Levin I., Ostanin S. A. Self-Checking Synchronous FSM Network Design with Low Overhead// Journal of VLSI Design.-Overseas Publishers Assocoation. volOO, -.№00, -2000, -L-L2p.

75. J.A.Abraham. Challenges in Fault Detection // 9th IEEE Int. On-Line Testing Symp. July 2003.

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

77. Ball М., Hardie F. Effects and detection of intermitten faults in digital systems. // Proc. Fall Joint Computer Conf., 1978, pp.329-335.

78. Tasar O., Tasar V. A study of intermitten faults in digital computers // AFIPS Conf. Proc. 1977, pp.807-811.

79. Lala P.K., Missen J.I. Method for the diagnosis of a single intermitten fault in combinatorial logic circuits // IEEE Jour. Computers and Digital Techniques, October 1979, pp.187-190.

80. Malaiya Y.K., S.Y.H.Su A survey of methods for intermitten faults analysis. // Proc. Nat. Сотр. Conf., 1979, pp.577-584.

81. Ю.В. Седов К проблемам частичного восстановления работоспособности дискретных систем с произвольным доступом // Вестник ТГУ, 2002

82. A.Matrosova, V.Andreeva, Yu.Sedov Survivable Discrete Circuits Design // Proc. of 8-th IEEE International On-Line Testing Workshop, Bendor, France, July 2002

83. Matrosova A., Andreeva V., Goloubeva О., Nikitin К., Ostanin S., Sedov Yu. Self-Checking and Fail-Safe Synchronous Sequential Circuit Design. // Радиоэлектроника и информатика, №3, 2003, -С. 107-112.1. ЗАКЛЮЧЕНИЕ