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

□□34765Б6

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

Андреева Валентина Валерьевна

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

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

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Томск - 2009

7 ^Т'1

003476556

Работа выполнена на кафедре программирования ГОУ ВПО «Томский государственный университет»

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

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

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

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

кандидат технических наук, доцент Тюнина Людмила Васильевна

Ведущая организация: Институт вычислительного моделирования

СО РАН, г. Красноярск

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

8 октября 2009 г. в 10.30 час. на заседании диссертационного совета Д 212.267.12 при ГОУ ВПО «Томский государственный университет» по адресу: 634050, г. Томск, пр. Ленина, 36.

С диссертацией можно ознакомиться в Научной библиотеке ГОУ ВПО «Томский государственный университет» по адресу: 634050, г. Томск, пр. Ленина, 34а.

Автореферат разослан 4 сентября 2009 г.

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

диссертационного совета { л /¿и*-—^

доктор технических наук, В.И. Смагин

профессор

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

- Алгоритм минимизации частично монотонных (монотонных) реализаций частичных систем булевых функций.

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

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

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

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

- НИР «Разработка математических и программных средств обеспечения надежного и безопасного доступа к электронным ресурсам коллективного пользования», 2006-2007 гг.

Основные результаты диссертации внедрены в учебный процесс ТГУ.

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

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

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

2002).

2. The 8-th Biennial Baltic Electronic Conference (Tallinn, Estonia, 2002).

3. 2-ая Сибирская научная школа-семинар с международным участием «Проблемы компьютерной безопасности и криптографии» (Томск, Россия, 2003).

4. The 6th International Workshop on Boolean Problems (Freiberg, Germany, 2004).

5. 5-ая Всероссийская конференция с международным участием «Новые информационные технологии в исследовании сложных структур» (Томск, Россия, 2004).

6. 4-ая / 6-ая Сибирская научная школа-семинар с международным участием «Компьютерная безопасность и криптография» (Шушенское, Россия, 2006 / Горно-Алтайск, 2007).

7. 5-ая Международная конференция студентов и молодых ученых «Перспективы развития фундаментальных наук» (Томск, Россия, 2008)

8. The 7-th East-West Design & Test international Symposium (Львов, Украина, 2008).

Результаты диссертации опубликованы в 14 научных работах, одна из которых из перечня изданий, рекомендованных ВАК РФ.

Структура и объем диссертации. Диссертация состоит из введения, 4-х глав, заключения, приложения и списка используемой литературы, включающий 109 наименований. Общий объем диссертации составляет 128 страниц текста, включая 14 рисунков и 15 таблиц.

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

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

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

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

Рассмотрим систему частичных булевых функций F(X)={fx(X), ... , fm{X)}, Х= {х,,...^,,}, заданную множествами М]{/,), Ai°(/i). Здесь М]{[¡) - множество наборов (булевых векторов) значений переменных, на которых функция fi системы принимает единичное значение, a kP(f!) - множество наборов значений переменных, на которых функция fi принимает нулевое значение, т - число функций системы.

Определение 1. Интервал и булева пространства Еп является допустимым для функцииf, если и П М1(Л) Ф0,иг\ Д/°(/) = 0.

Определение 2. Допустимый интервал и является максимальным для функции/, если не существует допустимого интервала и', такого что u'z> и.

Обозначим через (и, h) допустимый интервал системы F (X). В паре (и, И) символом и обозначен интервал булева пространства £„, символом h -характеристика интервала. Интервал представляется троичным вектором, в характеристике перечисляются функции для каждой из которых

выполняется условие: и Л M\ f, ) ф 0, и П Л</°() = 0. Характеристика Л

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

Определение 3. Допустимый интервал (и, h) системы называется максимальным, если при сохранении характеристики h не существует интервала (и', И), такого что и' з и.

Обозначим через (у, g) элемент системы F. Здесь у - элемент булева пространства £„ , представляемый булевым вектором размерности я, g - характеристика элемента, задающая множество булевых функций {/7] ,•••>/; }

системы, принимающих единичное значение на этом элементе.

Определение 4. Будем говорить, что интервал (и, h) покрывает элемент (у, g) и обозначать это (у, g) €Е (и, И), если у е и,

{fh,-.fi, M/j,,:.,fL}m

Определение 5. Пусть характеристики подмножества элементов системы F{X), покрываемых некоторым интервалом (и, Л), одинаковы и представляются вектором h, тогда характеристика h интервала (и, И) системы F{X) является максимальной по мощности. Будем называть интервал (и, И) интервалом с максимальной характеристикой.

Рассмотрим некоторое множество W допустимых интервалов системы, lV={w1,\v2,...,ws}. Для каждой функции/системы F(X) выделим подмножество Wj, W,<iW, в характеристике каждого интервала этого подмножества содержится функция f. Представим элемент множества Л/'(/~) как элемент (у, g) системы F(X), в характеристике которого содержится единственная функция

Л

Определение 6. Назовем множество W реализацией системы F{X), если для каждого элемента (у, g) из выполняется условие: (у, g) покрывается интервалом из Wj, i = 1, ..., т.

Определение 7. Множество W максимальных интервалов системы F(X) является безызбьгточной реализацией, если из характеристик максимальных интервалов w, нельзя выбросить ни одной функции: выбрасывание функции f из характеристики приводит к тому, что некоторые элементы множества Al''(fJ) оказываются не покрытыми оставшимися интервалами.

Определение 8. Безызбыточную реализацию будем называть кратчайшей, если она состоит из наименьшего числа максимальных интервалов системы F{X).

Определение 9. Дискретный автомат-это пятерка объектов {X,Q,Y,y, ф), где X - входной алфавит, Y - выходной алфавит, Q - внутренний алфавит или множество состояний автомата, ц/ - функция переходов, <р - функция выходов.

Рассматривается STG (State Transition Graph)-onHcaHiie, позволяющее более компактно (по сравнению с таблицами переходов-выходов) представлять поведение дискретного автомата. В этом описании (таблица 1) символы входного и выходного алфавитов уже закодированы.

Таблица 1 Таблица 2

<7 Я У\УтУтУ& 5

0-- 1 1 00 0 1 0

-о - 1 1 00 0 1 0

11 - 1 2 10 0 10

--0 2 2 00110

--1 2 3 10 110

1 0 - 3 3 0 1000

0-- 3 4 11000

-1 - 3 4 11000

-- 0 4 4 0 1001

--1 4 1 11001

Z,Z,Z3Z4 Z,ZlZ3Z4 У\У2Уй>№

0-- 1000 1 о'оо 0 0 0 1 0

-0- 1000 1 000 000 1 0

11 - 1000 0 100 10 0 10

-- 0 0 100 0 100 0 0 110

--1 0 100 00 10 10 110

1 0 - 0 0 10 0010 0 10 00

0 -- 00 10 000 1 11000

-1 - 00 10 0 00 1 11000

--0 000 1 0 00 1 0 1001

--1 000 1 1 000 110 0 1

Здесь х2, - входные переменные, >Ч,...,}Ч - выходные переменные, в столбце q указаны состояния, относящиеся к моменту времени /, а в столбце (/' - состояния, относящиеся к моменту времени 1+1.

Выполнив кодирование состояний для такого описания, получим систему ^(^Очастичных булевых функций (таблица 2). Строка таблицы 2 представляет допустимый интервал (и, h)i этой системы. Интервал и, задается первыми двумя столбцами таблицы, а его характеристика И, -оставшимися столбцами. Единичные компоненты вектора /г, перечисляют функции, которые принимают единичное значение на всех элементах интервала и,.

Теорема 1. Интервал (и, к), является допустимым для системы Ь\Х) частичных булевых функций.

Теорема 2. Интервал (и, А), системы !'(Х) частичных булевых функций имеет максимальную характеристику.

Обозначим через IV множество всех допустимых интервалов (и, И),,

А),}.

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

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

Определение 10. Векторы аь а2 сравнимы, если один из них предшествует другому, иначе они не сравнимы. Например, векторы 0100110, 1110110 сравнимы, а векторы 0100110, 1100001 не сравнимы.

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

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

Определение 12. Булевы векторы являются инверсно 2-ортогональными, если в одном из них ¡'-я компонента принимает значение 1, а в другом - ¡'-я компонента принимает значение 0, в то время каку-я компонента первого вектора принимает значение 0, а у-я компонента второго вектора принимает значение 1.

Несравнимые векторы инверсно 2-ортогональны.

Вернемся к БТО-описанию поведения синхронного автомата (таблица 2). В ней состояния таблицы 1 закодированы равновесными кодами, а коды выходных символов не являются ни равновесными, ни кодами Бергера. Добавим две переменные у6, у7, сделав коды выходных символов автомата равновесными. В результате получаем таблицу 3.

Таблица 3 представляет систему частичных функций F(X), соответствующее ей множество IV, IV = {(и, А),} является реализацией системы, то есть множество IV можно рассматривать как задание на синтез самопроверяемого синхронного последовательностного устройства. Его монотонно проявляющиеся неисправности будут обнаружены детектором равновесных кодов, подключенным к выходам и линиям обратных связей устройства (рис. 1).

Таблица 3

2\2->21,2 4 У1У2УзУ4У5.У(,У7

0-- 10 0 0 100 0 0 0 0 1 0 1 1

-01 1 - 10 00 100 0^ 0 0 0 1 0 1 1

10 0 0 0 10 0 10 0 10 10

--0 0 100 0 10 0 0011010

--1 0 100 0 0 10 10 110 0 0

1 0- 00 10 0 0 10 0 10 0 0 11

0-- 00 10 0 00 1 1 1 0 0 0 1 0

-1 - 00 10 0 0 0 1 110 0 0 10

--0 0 0 0 1 0 0 0 1 0 10 0 110

--1 0 0 0 1 100 0 110 0 10 0

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

Здесь К - комбинационная составляющая самопроверяемого последо-вательностного синхронного устройства, с1\, ...,йр, ¿/-триггеры, включенные в линии обратных связей, Дк — детектор кодов, подключенный к выходам и линиям обратных связей.

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

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

Таблица 4

Х\Х7Х-1 У.УзУ^УгУбУ?

0-- 1 ... 100 0 0 0 0 10 11

- 0 - 1 ... 1000 0 0 0 10 11

1 1 - 1 ... 0 10 0 1001010

--0 . ) .. 0 100 0 0 110 10

-- 1 - 1 -- 0 0 10 [10 110 0 0

1 0- -- 1 - (НОЮ 0 10 0011

0-- . _ I . 0 00 1 110 0 0 10

- 1 - -- 1 - 0 0 0 1 110 0010

--0 0 0 0 1 0 10 0 110

- 1 ... 1 1000 110 0 10 0

Каждой строке таблицы сопоставим интервал (и, /г),. Единичные компоненты вектора И, перечисляют функции, которые принимают значение 1 на всех элементах интервала и,.

Теорема 3. Интервал (и, К)' является допустимым для системы Г(Х) частичных булевых функций, полученной кодированием состояний неупорядоченными кодами.

Теорема 4. Интервал (г/, И)'-допустимый интервал системы Р(Х) с максимальной характеристикой.

Пусть = {(к, /г),"}-

Теорема 5. IV" является реализацией системы НХ).

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

Определение 13. Длиной реализации системы Р(Х) будем называть число интервалов реализации.

Определение 14. Кратчайшей реализацией системы Р{Х) будем называть реализацию из максимальных интервалов наименьшей длины.

Алгоритм нестроения кратчайшей частично монотонной реализации из максимальных интервалов с максимальными характеристиками

Вход: Система Р(Х) частичных булевых функций, допускающих частично монотонную реализацию.

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

Ш.1. Строим всевозможные расширения интервалов множества IV* без изменения их характеристик. В результате для каждого интервала из !V* получаем звезду максимальных интервалов. Множество всех максимальных интервалов обозначаем IV*.

Ш.2. Разбиваем множество^*на подмножества максимальных интервалов (Л,) с одинаковыми характеристиками.

Ш.З. Находим кратчайшую реализацию подсистемы F(X), представленной интервалами с одной и той же характеристикой А„ используя интервалы множества IV* (А,-). Обозначаем множество интервалов полученной реализации через IV* (/¡,).

Ш.4. Объединяем полученные для каждой характеристики А/ реализации IV* (И,), находим кратчайшую реализацию 1Укр*.

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

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

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

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

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

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

Таблица 5

В таблице 5 введены следующие обозначения: КП - контрольные примеры: 1 -beecount, 2 - bbsse, 3 -bbara, 4 - ese, 5 -donfile, 6 - planet, 7 -exl, 8 - sef, 9 - sand; / -число входов; о - число выходов; W- частично монотонная реализация; W*6- безызбыточная частично монотонная реализация, построенная предложенным алгоритмом; W*0'- безызбыточная частично монотонная реализация, построенная алгоритмом А.Д. Закревского; Р - число конъюнкций в системе F(X); L -число букв в системе FQC).

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

КП i о Частично монотонные системы

W' W'6 W6'

Р L Р L Р L

1 9 10 28 152 19 76 20 78

2 13 16 56 249 38 197 41 206

3 10 9 60 350 47 208 50 210

4 13 16 91 540 78 452 89 482

5 9 8 96 576 94 464 112 514

6 15 36 115 653 115 634 123 657

7 15 34 138 947 119 760 131 799

8 37 79 166 1145 166 941 191 1012

9 19 22 184 1439 121 660 127 678

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

Одиночные константные неисправности на входах синхронного последовательное! кого устройства при использовании частично монотонных реализаций и тех же методов синтеза мо1ут не проявляться монотонно. Для обеспечения их монотонного проявления необходимо расширить множество входов последовательностного устройства. В работе Matrosova A. Yu., Levin I., Ostanin S. A. «Self-Checking Synchronous FSM Network Design with Low Overhead» (Journal of VLSI Design. - 2000. - Vol. 11, № 1. - P. 47-58) предлагается ввести дополнительные входы, так что интервалы с различными характеристиками и не отличающиеся по значениям внутренних переменных становятся инверсно 2-ортогональными. В этом случае задание па синтез самопроверяемого последовательностного устройства может быть представлено полностью монотонной реализацией. Теоретические результаты и алгоритм минимизации частичных систем булевых функций в классе частично монотонных реализаций распространяются в диссертационной работе на полностью монотонные реализации.

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

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

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

Пусть ДНФ D = K\V, ..., V Ks состоит из простых импликант.

Определение 15. ДНФ D, в которой нельзя удалить ни одну конъюнкцию Kh называется безызбыточной ДНФ.

Определение 16. Система ДНФ называется системой БДНФ, если каждая ДНФ D) системы есть БДНФ.

Рассмотрим модели неисправностей БДНФ D, введенные в работе I. Kohavi, Z. Kohavi. «Detection of multiple faults in combinational logic networks», IEEE Trans. Comput.1975. VC-20. №6. P. 556-568. В ней выделены два типа неисправностей: а-неисправности и ¿-неисправности. Исчезновение некоторой конъюнкции из D называется а-неисправностью, исчезновение некоторой буквы из некоторой конъюнкции называется ¿-неисправностью. Наборы, обнаруживающие такие неисправности, будем называть а,Ь-тестовыми наборами, соответственно.

В работе «А./О. Матросова. «Построение полного теста для схем, синтезированных методом факторизации», Автоматика и вычислительная техника 1978 №5 С. 42-46, предложены специальные алгоритмы построения а,Ь-тестовых наборов. Для их описания введем ряд определений.

Определение 17. Конъюнкцию К (х,), полученную из К путем замены знака переменной xt на инверсный, будем называть дополнением конъюнкции К по переменной х,.

Определение 18. Фиксированием значений некоторых переменных ДНФ D относительно конъюнкции К является вычеркивание всех конъюнкций, ортогональных К, а также вычеркивание всех букв из оставшихся конъюнкций ДНФ Д которые присутствуют в К. Результат фиксирования представляется ДНФ, которую будем обозначать D(K).

Для построения «-тестового набора, обнаруживающего исчезновение некоторой конъюнкции Kj из D, получим D путем вычеркивания конъюнкции К, из D. Строим D', D' = D'(K,). Пусть г, конъюнкция, представляющая корень логического уравнения D' = 0, тогда всякий набор значений переменных БДНФ, обращающий в единицу логическое произведение К" = г, Л Kh есть а-тестовый набор. Здесь К" - конъюнкция, представляющая тестовые наборы.

Обозначим символом А множество «-тестовых наборов (по одному на каждую неисправность), обнаруживающих все а-неисправности БДНФ.

Для построения ¿-тестового набора, обнаруживающего исчезновение переменной х, из конъюнкции К, полагаем D' = D(K*(x,)) и решаем уравнение D' = 0. Пусть г. конъюнкция, представляющая корень этого уравнения. Всякий набор значений переменных БДНФ, обращающий в единицу логическое произведение K,h = г, Л К*(х,), есть ¿-тестовый набор. Здесь К,ь- конъюнкция, представляющая тестовые наборы.

Обозначим символом В множество ¿-тестовых наборов (по одному на каждую неисправность), обнаруживающих все ¿-неисправности БДНФ.

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

БДНФ. Тест Т может быть получен путем объединения всех а,¿-тестовых наборов, построенных по БДНФ. Длина проверяющего теста Т не превосходит суммы длин А, В тестов.

Сокращение длины А теста для БДНФ невозможно, а В тест можно сократить за счет того, что один и тот же тестовый набор в общем случае может обнаруживать некоторое подмножество ¿-неисправностей. Таким образом, сокращение проверяющего теста БДНФ осуществляется за счет сокращения длины В теста.

Предлагается алгоритм сокращения длины В теста, который состоит из трех этапов:

1. Построение А'* - конъюнкций, представляющих ¿-тестовые наборы. При реализации этого этапа отыскивается корень г, уравнения. Предложена модификация известного алгоритма А.Д. Закревского поиска одного корня логического уравнения £>'=0, позволяющая найти корень уравнения по возможности меньшего ранга. Эффективность предложенной модификации подтверждается компьютерными экспериментами, приведенными в диссертации.

2. Выделение среди множества {AT,*} конъюнкций максимально совместимых подмножеств.

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

Множество конъюнкций называется совместимым, если их пересечение не пусто.

Совместимое множество конъюнкций называется максимальным относительно некоторого заданного множества конъюнкций Р, если в него нельзя добавить ни одной конъюнкции из Р.

Рассмотрим множество конъюнкций Е. Напомним, что множество конъюнкций можно интерпретировать как ДНФ. Множество (ДНФ) монотонно по переменной xh если эта переменная встречается в нем с одним и тем же знаком инверсии. Иначе множество не монотонно по рассматриваемой переменной.

Предложено выделять максимально совместимые подмножества из Е в процессе построения дерева разложений (ДР). Порядок разложения по переменным заранее не определен.

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

В не концевой вершине v дерева выполняется разложение по немонотонной, максимально встречающейся в подмножестве Pv переменной. Вер-

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

Пусть Р1 - произвольное максимальное совместимое подмножество из

Е.

Теорема 6. В ДР, построенном для множества Е, найдется концевая вершина V,, такая что сопоставляемое ей подмножество />"'' , есть Р1'' = Л-Построим все максимально совместимые подмножества для Е = {-100— , 01—0, 10-0-, -0-0-1, -0-000, 001-1-, 0010-, -0000}, используя ДР. Здесь конъюнкции представлены троичными векторами. Подмножества для внутренних вершин обозначим М,(х,), для концевых - (рис.2).

1о--о--0-0-1

Рисунок 2 —Дерево разложений

Построим матрицу М, в которой строкам сопоставлены конъюнкции множества Е, а столбцам - максимально совместимые подмножества из этих конъюнкций. Кратчайшее покрытие строк такой матрицы ее столбцами представляет множество ртт={рь р2, ..., ['<} максимально совместимых подмножеств. Сопоставим максимально совместимому подмножеству Р1 логическое произведение Р- конъюнкций этого подмножества, получим множество

Если в качестве множества Е выбрано множество конъюнкций, представляющее тестовые наборы для всех Ь - неисправностей, тогда логические произведения {/у, Р2', ..., /У} представляют Б тест. Вместо кратчайшего по-

крытая строк матрицы М можно строить безызбыточное покрытие, по возможности близкое к минимальному.

Сформулируем алгоритм построения проверяющего теста для системы БДНФ. Алгоритм включаете себя следующие шаги.

Ш.1. Строим множество конъюнкций {К,"}, представляющих я-тестовые наборы для всех БДНФ системы.

Ш.2. Строим множество конъюнкций {А'/}, представляющих 6-тестовые наборы для всех БДНФ системы.

Ш.З. Объединяем {А',"} и {А'/}, находим множество Е, выделяем в нем максимально совместимые подмножества конъюнкций.

Ш.4. Находим безызбыточное покрытие неисправностей системы БДФ максимально совместимыми подмножествами. Покрытие представляет проверяющий тест для системы БДНФ.

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

В таблице 6 введены следующие обозначения: /С - количество конъюнкций в системе БДНФ; ¿-количество букв в системе БДНФ; Вт - длина теста Т, построенного предложенным алгоритмом; Дг*-длина теста Т', построенного путем объединения всех а, Ъ тестовых наборов системы БДНФ; о% - отношение длины проверяющего теста Т к длине теста Т, выраженное в процентах.

Таблица 6

Наз-е примера К I пг /Г 0%

ЬЬй5С 44 218 77 220 35

ЬЫая 18 48 24 45 53

Ьеесоиги 24 79 27 71 38

с!к16 120 583 113 ~ЗУ5 29

с1опП1с 166 987 128 327 39

ех1 108 540 98 440 22

кеуЬ 87 727 211 599 35

р1ап(Л 218 1153 187 1024 18

105 548 165 619 27

болс! 184 1179 240 1088 22

354 2493 253 1146 22

эупс 117 521 116 483 24

Лк 243 2130 529 1255 42

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

Сокращение длины теста позволяет в рамках В1БТ-технологий сократить время тестирования синхронных автоматов и объем памяти, необходи-

мой для хранения тестовых наборов.

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

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

Пусть задано описание функционирования синхронного автомата, например, БТС -описание. Требуется построить схему, обеспечивающую заданное функционирование, и устойчивую к неисправностям.

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

Рисунок 3 —Архитектура отказоустойчивого дискретного устройства

Схема, устойчивая к неисправностям, представлена на рис. 3. Ее компонентами являются две идентичные самопроверяемые схемы, схема из элементов И, схема из элементов ИЛИ, мультиплексор и детектор кодов.

Здесь К] и К2 - комбинационные составляющие идентичных самопроверяемых синхронных устройств ССУь ССУ2, обеспечивающие монотонное проявление допустимых для этих устройств неисправностей на выходах. В качестве допустимых неисправностей рассматриваются одиночные константные неисправности на полюсах логических элементов комбинационной составляющей, а также одиночные константные неисправности на полюсах ¿/-триггеров синхронного устройства.

Подсхема ИЛИ состоит из двухвходовых элементов ИЛИ, так что входами одного и того же элемента ИЛИ являются одноименные выходы комбинационных схем К} и Кг. Эта подсхема имеет я+р выходов, то есть выходы элементов ИЛИ являются выходами подсхемы.

Подсхема И состоит из я+р двухвходовых элементов И, так что входами одного и того же элемента И являются одноименные выходы комбинационных схем К| и К2. Эта подсхема имеет выходов, то есть выходы элементов И являются выходами схемы.

Выходы подсхемы ИЛИ являются входами подсхемы детектора (ДК-подсхемы) равновесных кодов. ДК-подсхема имеет два выхода: иьи2-

Выходы подсхемы И являются входами подсхемы мультиплексора. Мультиплексор МХ связывает линии У\, ...,ут'', ■••, "р с линиями у,,...,гь ...,г;„ если на входах и,, и2 мультиплексора достигаются значения 01 (10). Иначе мультиплексор связывает линии ...,ут"\ г",...,:р"с линиями^,, ...,у„;г,,

Допустимыми неисправностями подсхем ИЛИ (И) являются одиночные константные неисправности на полюсах составляющих эти подсхемы элементов.

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

Неисправности мультиплексора могут привести к замене связей некоторых линий из ряда у\,—,ут\ •••,на одноименные линии ряда У",---,Ут"', -Г, • -/>''• Допускаются также одиночные константные неисправности на линиях связей между подсхемами, кроме линий хи ..., х„;у\,..., ут; гь ..., :р. Если линия разветвляется, то неисправность имеет место на одной из ветвей линии.

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

Обозначим через Уд множество допустимых неисправностей несамо-тестируемого детектора кодов. Пусть УИШ , УИ — множества допустимых неисправностей подсхем ИЛИ, И, соответственно. У\,Уг - множества неисправ-

ностей подсхем ССУЬССУ2; VL - множество неисправностей линий. Обозначим через Кобъединение этих множеств: V=V\ и У2и Уд и Уилн и Уи и VL .

Теорема 7. Неисправность v из V сохраняет корректное поведение синхронного последовательностного устройства.

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

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

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

В таблице 7 введены следующие обозначения: КП- контрольные примеры: 1 - sync, 2- sla, 3-dkl6, 4 -si, 5 - dkl4, б-opus, 7-ex4; n-число входов синхронного последовательностного устройства; т - число выходов; р — число конъюнкций в STG-описании; s - число состояний; q - число линий обратных связей после кодирования состояний; сложность последова-тельностной схемы при троировании без учета сложности схемы голосования и сложности ¿-триггеров; N- сложность предложенной архитектуры без учета сложности мультиплексора и ¿/-триггеров. Под сложностью понимается число двухвходовых элементов НЕ И и инверторов.

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

Заключение

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

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

Таблнца 7

КП п т Р s q N1 N

1 19 7 80 52 6 4584 2432

2 8 6 107 20 5 5349 2364

3 2 3 108 27 5 5427 2837

4 8 6 107 20 5 6387 3671

5 3 5 56 7 3 2382 1960

6 5 6 22 10 4 927 744

7 6 9 21 14 4 873 809

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

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

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

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

1. Матросова А.Ю., Андреева В.В. Минимизация систем булевых функций, представляющих задание на синтез самопроверяемых дискретных автоматов // Автометрия. - 2008. - Т. 44. — № 5.— С. 100-111.

2. Матросова А.Ю., Андреева В.В. Об одной проблеме синтеза самопроверяемых синхронных последовательностных устройств // Теория и техника передачи, приема и обработки информации : сборник научных трудов по материалам 7-й международной конференции. - Харьков, 2001. - С. 24-29.

3. Matrosova A., Andreeva V., Sedov Yu. Survivable Discrete Circuit Design // Proc. of the 8-th IEEE International On-Line Testing Workshop. - Isle of Bendor, 2002. - P. 44-^8.

4. Matrosova A., Andreeva V. Survivable Synchronous Sequential Circuit Design // The 8-th Biennial Baltic Electronic Conference. - Tallinn, 2002. - P. 133-136.

5. Матросова А.Ю., Останин C.A., Андреева В.В., Седов Ю.В. Автоматизированный синтез самопроверяемых синхронных последовательностных схем (синхронных автоматов) И Идентификация систем и задачи управления : труды 2-ой международной конференции. Москва, 29-31 января, 2003. - М., 2003. - С. 1756-1767.

6. Матросова А.Ю., Андреева В.В. Минимизация не полностью определенных систем булевых функций, допускающих монотонную или частично монотонную реализацию // Вестник ТГУ. Приложение. - 2003. - № 6. - С. 912.

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

8. Matrosova A., Andreeva V., Ostanin S. Easy Testable Combinational Circuit Design // Proc. The 6th International Workshop on Boolean Problems. -Freiberg, 2004. - P. 237-244.

9. Андреева В. В. Поиск максимальных расширений интервала булева пространства // Вестник ТГУ. Приложение - 2004. - № 9 (1), - С. 3-8.

10. Андреева В.В., Матросова А.Ю. Построение минимизированного проверяющего теста, обнаруживающий неисправности безызбыточной ДНФ // Вестник ТГУ. Приложение. - 2006. - № 18. - С. 34-39.

11. Андреева В. В. Поиск некоторых максимальных расширений интервала частичной булевой функции // Вестник ТГУ. Приложение. - 2007. -№23.-С. 12-15.

12. Матросова А.Ю., Андреева В.В., Николаева Е.А. Синтез синхронных последовательностных устройств, устойчивых к кратковременным и перемежающимся неисправностям // Вестник ТГУ. - 2008. - № 3 (4). - С. 99109.

13. Андреева В.В. Минимизация проверяющего теста, обнаруживающего неисправности системы безызбыточных ДНФ // Перспективы развития фундаментальных наук : труды 5-ой международной конференции студентов и молодых ученых. - Томск, 2008. - С. 230-232.

14. Matrosova A., Andreeva V., Melnikov A., Nikolaeva Е. Multiple stuck-at fault and path delay fault testable circuit // Proceedings 7, East-West De-sign&Test International Symposium. - Lviv, 2008. - P. 356-364.

Тираж 100 экз. Отпечатано в КЦ «Позитив» 634050 г. Томск, пр. Ленина 34а

Введение.

1. Методы контролепригодного проектирования.

1.1. Модели неисправностей.

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

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

1.4. Отказоустойчивые схемы.

1.5. Выводы по главе.

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

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

2.2. Реализация системы частичных булевых функций, полученной по ЭТО описанию.

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

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

2.5. Поиск максимальных расширений интервала частичной булевой функции.

2.5.1. Матрица ортогональности и ее свойства.

2.5.2. Построение всех максимальных расширений интервала частичной булевой функции.

2.5.3. Построение некоторых максимальных расширений интервала частичной булевой функции.

2.5.4. Упрощение матрицы ортогональности.

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

2.6. Выводы по главе.

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

3.1. Модели неиправностей безызбыточной ДНФ и способы обнаружения неисправностей.

3.2. Построение проверяющего теста для одиночных неисправностей БДНФ

3.2.1. Поиск корня логического уравнения D = 0.

3.2.2. Построение всех максимально совместимых подмножеств конъюнкций

3.2.3. Построение проверяющего теста Г для БДНФ.

3.3. Построение проверяющего теста Тдля одиночных неисправностей системы БДНФ.

3.4. Выводы по главе.

4. Архитектура дискретных устройств, устойчивых к кратковременным и перемежающимся неисправностям.

4.1. Схема, устойчивая к неисправностям.

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

4.3. Выводы по главе.

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

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

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

В самопроверяемых дискретных устройствах отсутствует специальный режим тестирования. Обнаружение неисправностей происходит в процессе функционирования, как правило, в первый момент проявления неисправности заданного класса. Устройство состоит из самопроверяемой схемы и наблюдающим за некоторыми ее полюсами детектором кодов. Детектор выдает информацию об исправности или неисправности самопроверяемой схемы. Самопроверяемость схемы обеспечивается введением в нее аппаратурной избыточности, за счет которой на наблюдаемых детектором полюсах реализуются кодовые слова некоторого кода. В' работе решается проблема снижения аппаратурной избыточности самопроверяемых схем за счет минимизации, системы, частичных булевых функций; представляющей задание на синтез самопроверяемой'схемы. Предложена архитектура отказоустойчивых схем логического управления, способных не только- сохранять правильное функционирование в присутствии» неисправности из рассматриваемого класса, но- и восстанавливаться в условиях кратковременных и, перемежающихся неисправностей. Архитектура основана на использовании1 самопроверяемых схем. С целью снижения аппаратурной* избыточности^ предлагается минимизировать- систему частичных булевых функций разработанным в работе методом. Система представляет задание на синтез самопроверяемой схемы.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

- НИР «Разработка математических и программных средств обеспечения надежного и безопасного доступа к электронным ресурсам коллективного пользования», 2006-2007 гг.

Основные результаты диссертации внедрены в учебный процесс ТГУ.

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

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

2. The 8-th Biennial Baltic Electronic Conference (Tallinn, Estonia, 2002).

3. 2-ая Сибирская научная школа-семинар с международным участием «Проблемы компьютерной безопасности и криптографии» (Томск, Россия,

2003).

4. The 6th, International Workshop on Boolean Problems (Freiberg, Germany,

2004).

5. 5-ая Всероссийская конференция с международным участием «Новые информационные технологии в исследовании сложных структур» (Томск, Россия, 2004).

6. 4-ая Сибирская научная школа-семинар с международным участием «Компьютерная безопасность и криптография» (Шушенское, Россия, 2006)

7. 6-ая Сибирская научная школа-семинар с международным участием «Компьютерная безопасность и криптография» (Горно-Алтайск, Россия,

2007).

8. 5-ая Международная конференция студентов и молодых ученых «Перспективы развития фундаментальных наук» (Томск, Россия, 2008).

9. The 7-th East-West Design & Test international Symposium (Львов, Украина,

2008).

По результатам выполненных исследований' опубликовано- 14 печатных работ, в том числе одна из перечня изданий, рекомендованных ВАК РФ.

1. А.Ю. Матросова, В.В. Андреева. Минимизация систем булевых функций; представляющих задание на синтез, самопроверяемых дискретных автоматов // Автометрия. - 2008. - Том 44. - №5. - С. 100-111.

2. А.Ю Матросова, BIB. Андреева. Об одной проблеме синтеза самопроверяемых синхронных последовательностных устройств // Сборник научных трудов по материалам 7-й международной конференции «Теория и техника передачи, приема и обработки информации», Харьков, Украина, 2001.-С. 24-29.

3. A. Matrosova, V. Andreeva, Yu. Sedov. Survivable Discrete Circuit Design // Proc. of the 8-th IEEE International On-Line Testing Workshop. - Isle of Bendor, France; July 2002. - P. 44-48.

4. A. Matrosova, V. Andreeva. Survivable Synchronous Sequential Circuit Design // The 8-th Biennial Baltic Electronic Conference. - Tallinn; Estonia; 2002. - P. 133-136.

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

6. А.Ю. Матросова, В.В. Андреева. Минимизация, не полностью определенных систем булевых функций, допускающих монотонную или частично монотонную реализацию // Вестник ТГУ. Приложение. — 2003. № 6. - С. 9-12.

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

8. A. Matrosova, V. Andreeva, S. Ostanin. Easy Testable Combinational Circuit Design // Proc. The 6th International Workshop on Boolean Problems. - Freiberg, Germany, 2004. - P. 237-244.

9. Андреева; ВЯЗ'. Поиск максимальных расширений интервала булева пространства // Вестник ТЕУ. Приложение. - 2004. - №9(1), - С. 3-8.

10. В .В. Андреева, А.Ю. Матросова. Построение минимизированного проверяющего теста, обнаруживающий неисправности безызбыточной: ДНФ // Вестник ТЕУ. Приложение. - 2006; - №18. - С. 34-39.

11. Андреева ВЛЗ. Поиск некоторых, максимальных расширений интервала частичной булевой функции // Вестник ТГУ. Приложение. - 2007. - №23. - G. 12-15.

12. А.Ю. Матросова;. В .В; Андреева, Е. А. Николаева. Синтез» синхронных последовательностных: устройств,, устойчивых к кратковременным? и; перемежающимся неисправностям // Вестник ТГУ. - 2008. - №3(4). - С. 99109;

13. Андреева B-Bi Минимизация? проверяющего теста; обнаруживающего неисправности; системы, безызбыточных ДНФ // Труды 5-ой международной конференции студентов'; и молодых ученых «Перспективы развития фундаментальных наук». - Томск, Россия; 2008. - Изд-во ТПУ. — С. 230-232.

14. A. Matrosova,V. Andreeva, A. Melnikov, Е. Nikolaeva. Multiple; stuck-at fault and path, delay fault; testable circuit // Proceedings 7, East-West Design & Test International Symposium. - Kharkov, Ukraine, 2008, - P. 356-364.

Структурами объем диссертации. Диссертация« состоит из введения, 4-х глав;, заключения^ приложения и списка используемой литературы, включающий 109-наименований; Общий объем-диссертации составляет 128 страниц,текста;.включая« 14 рисунков и 15 таблиц.

4.3. Выводы по главе

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

Заключение

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

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

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

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

1. Wei S., Nag P., Blanton R., Gattiker A. and Maly W. To DFT or Not to DFT ? // Proc. 1.EE International Test Conf. - 1997. - P. 557-566.

2. Williams Т., Parker K. Design for Testability A Survey // Proc. of IEEE. -1983. - Vol. 71. - №. 1. - P. 98-112.

3. Robinson G. DFT, Test Lifecycles and the Product Lifecycle // Proc. IEEE International Test Conf. 1999. - P. 705-713.

4. Johnson J. Is DFT Right for You? // Proc. IEEE International Test Conf. -1999. -P. 1090-1097.

5. Уэйкерли Д. Ф. Проектирование цифровых устройств Москва: Постмаркет. -2002. - Том 2. - 528 с.

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

7. Согомонян Е. С., Слабаков Е. В. Самопроверяемые схемы и системы, защищенные от неисправностей — М.: Радио и связь. -1989. -158 с.

8. Stassinopoulos Е., Raymond J. The space radiation environment for electronics // Proceedings of the IEEE. New York, 1988. - v.16. -№ 11. - P. 1423-1442.

9. Barth J. Applying Computer Simulation Tools to Radiation Effects Problems // Proceedings IEEE Computer Society -1997. P. 1-83.

10. Baumann R. Soft errors in advanced semiconductor devices-part I: the three radiation sources // IEEE Transactions on Device and Materials Reliability. -New York, Mar. 2001. v. 1, №. 1. - P. 17-22.

11. Grout. I. A. Integrated Circuit test engineering: modern techniques -Springer-Yerlag London Limited, 2006. 359 p.

12. Mei K.C.Y. Bridging and Stuck-at Faults // IEEE Trans. Computers. 1974. -vol. C-23.-P. 720-727.

13. Rodriguez-Montanes R., Bruls E. and Figueras J. Bridging Defects Resistance Measurements in a CMOS Process // Proc. IEEE International Test Conf.-1992. P. 892-896,

14. Liou J.J., Krstic A., Jiang Y. M., Cheng K.T. Modeling, Testing, and Analysis for Delay Defects and Noise Effects in Deep Submicron Devices // IEEE Trans. On Computer Aided Design of Integrated Circuits and Systems. — 2003. — vol. 22, №6. -P. 756-769,

15. Stroud C., Emmert J., Bailey J. A New Bridging Fault Model for More Accurate Fault Behavior // Proc. IEEE Automatic Test Conference. -2000. -P. 481-485.

16. Stroud C., Emmert J., Bailey J., Chhor K. and Nickolic D. Bridging Fault Extraction from Physical Design Data for Manufacturing Test Development // Proc. IEEE International Test Conf. -2000. P. 760-769.

17. Sivaraman M. A, Strojwas A. Unified Approach,for. Timing Verification and Delay Fault Testing Boston, Kluwer Academic Publishers. - 1998. - 176 p.

18. Mei K. Bridging and Stuck-At Faults // IEEE Trans, on Computers. -1974. -vol. 23, №7. -P. 720-727.

19. Krstic A., Cheng K. Delay Fault Testing for VLSI Circuits Boston, Kluwer Academic Publishers. -1998. -212 p.

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

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

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

23. Мак G.P., Abraham J. A., Davidson E.S. The Design of PLAs with concurrent error detection // Proc. 12-th Int. Symp. on Fault Tolerant Computing. — 1982. -P. 303-310.

24. Tao D.L., Lala P.K., Hartmann C.R. A concurrent testing strategy for PLAs // Proc. Int. Test Conference. -1986. -P. 705-709.

25. Arevalo Z., Bredson J.G. A method to simplify a Boolean function onto a near minimal sum-of-products for programmable logic arrays // IEEE Trans.Computers. -C-27, 1978.-P. 1028-1039.

26. Mine.H., Koga Y. Basic properties and construction method for fail-safe logic systems // IEEE Trans. Electronic Computers. -1967. -P. 282-289.

27. Nicolaidis M. Fail-safe interfases for VLSI: theoretical foundations and implementations //IEEE Transactions on Computers, -vol. C-47, №1. -1998. -P. 62-77.

28. Goessel M., Sogomonyan E.S. Self-Parity Combinational Circuits for Self-Testing, Concurrent Fault Detection and Parity Scan Design // Proceedings VLSI 93. -P. 103-111.

29. Goessel M., Sogomonyan E.S. Code Disjoint Self-Parity Combinational Circuit for Self-Testing, Concurrent Fault Detection and Parity Scan Design // Proceedings 12th IEEE VLSI Test Symposium. 1994. - P. 151-157.

30. Touba N.A., McCluskey EJ. Logic Synthesis of Multilevel Circuits with Concurrent Error Detection // IEEE Transactions on Computer-Aided design. -1997. vol.16. - №7. - P. 783-789.

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

32. Закревский А.Д., Балаклей Л.И., Елисеева H.A. и др. Синтез асинхронных автоматов на ЭВМ- Минск: Наука и техника. —1975. -184 С.

33. Marouf M.A., Friedman A.D. Design of self-checking checkers for Berger codes // Proc. Int. Symposium Fault-Tolerant Computing. -1978. P. 179-184.

34. Piestrark S.J. Design of fast self-checking checkers of a class of Berger codes // IEEE Transactions on Computers. C-36. -1987. -P. 629-634.

35. J. Lo., Thanawastien S. The design of fast totally self checking Berger checkers based on Berger code portioning // Proc. 18-th Int. Symposium Fault-Tolerant Computing. - 1988. - P. 226-231.

36. Abramovici M. A., Breuer M. A., Friedman. A. D. Digital Systems Testing and Testable Design New York: W. H. Freeman and Company. -1990. 653 p.

37. Rao T.R.N., Feng G.L., Kolluru M.S., Lo J.C. Novel totally self-checking Berger code checker design based on generalized Berger code partitioning // IEEE Transactions on Computers. -1993. -P. 1020-1024.

38. Pierce D.A., Lala P.K. Modular implementation of efficient self-checking checkers for Berger code // Jour. Electronic Testing: Theory and Applications. —№ 9, 1996. -P. 279-294.

39. Anderson D. A., Metze G. Design of Totally Self-Checking Check Circuits for m-out-of-n Codes // IEEE Transactions on Computers. vol. C-22. -1973'. -P. 263-269.

40. Khakbas J. Totally Self-Checking Checker for l-out-of-и Code Using Two-Rail Codes // IEEE Transactions on Computers. vol. C-31. -1982. - P. 677-681.

41. Tohma Y. Coding Techniques in Fault-Tolerant, Self-Checking, and Fail-Safe Circuits- Englewood Cliffs, NJ: Prentice-Hall, Chap. 5 in Fault Tolerant Computing, -ed. Pradhan D. K. -1986. -P. 336^15.

42. Paschalis A. M., Metze G. Efficient Modular Design of TSC Checkers for M-out-of-2M Codes // IEEE Transactions on,Computers. vol. 37. - 1988. - P. 301— 309.

43. Sapozhnikov V. V., Sapozhnkov VI. V. Design of Self-Checking Checkers for l-out-of-3 code // Automation and Remote Control. vol. 52, №2. - 1991. - P. 289-296.

44. Сапожников В. В., Сапожников Вл. В. Самопроверяемые дискретные схемы JI: Энергоатомиздат. -1992. - 224 с.

45. Слабаков Е. В. Методы построения одновыходных самопроверяемых схем встроенного контроля для равновесных кодов //Автоматика и телемеханика. №8. -1982. -С. 108-119.

46. Matrosova A., Malgin A., Butorina N. Checker design for arbitrary subset of unordered codewords // Proc. IEEE East-West Design&Test Int. Symp. Ukraine, 2008.-P. 344-349.

47. Matrosova. A., Ostrovsky V., Levin I., Nikitin К. Designing FPGA based Self-Testing Checkers for m-out-n Codes // 9-th IEEE Int. On-Line Symposium. -Grees, 2003.-P. 49-53.

48. Матросова А.Ю., Никитин K.B. Синтез самотестируемого детектора (т,п) кодов на программируемых логических блоках // Вестник ТГУ. Приложение. -2003. -№6. -С.124-136.

49. Matrosova A.Yu., Ostanin S.A. Self-Checking Synchronous Sequential Circuit Design for Unidirectional Error // Compendium of papers. IEEE European Test Workshop. Barselona, Spain. -1998.

50. Matrosova A. Yu., Ostanin S.A. Self-Checking Synchronous FSM NetworkiL •

51. Design // Compendium of papers. 4 IEEE International On-Line Testing Workshop. -Italy ,1998. P. 162-166.

52. Stroud С. Е. A Designer's Guide to Built-in Self-Test Kluwer Academic Publishers. - 2002. - 319 p.

53. Touba N., McCluskey E. Transformed Pseudo-Random Patterns for BIST // Proc. IEEE VLSI Test Symposium. 1995. - P. 410^116.

54. McCluskey E. Verification Testing A Pseudo exhaustive Test Technique // IEEE Transactions on Computers. -1984. - vol. 33, № 6. - P. 541-546:

55. Kim: К., Tront J. On Using Signature Registers as Pseudorandom Pattern Generators in Built-in Self-Test // IEEE Transactions on Computer-Aided Design.- 1988- -vol: 7, №8:-P: 919-928;

56. BushnellM:, Agrawal V. Essentials of Electronic Testing for Digital, Memory and Mixed-Signal VLSI . Circuits — Kluwer Academic: Publishers, Boston.- 2000: 690 p.

57. Barzilai Z., Savir J., Markowsky G., Smith M. VLSI Self-Testing. Based: on Syndrome Techniques // Proc. IEEE International Test Conference. -1981. P. 102-109:

58. Agrawal V. D., Cheng К. Т., Johnson D. D. Designing Circuits with Partial Scan // IEEE Design and Test of Computers. -1988. P. 8-15.

59. Cheng К. Т., Agrawal V. D. A Partial Scan Method' for Sequential Circuits with Feedback // IEEE Transactions on Computers. —1990: — vol. 39; №4. — P. 544-548.

60. Gupta R., Breuer M: A. The BALLAST Methodology for structured Partial Scan,Design // IEEE Transactions on Computers. —1990. — vol. 39,- №4. — P. 538— 544.

61. Lala P. K. Self-checking and fault tolerant digital' design Academic press 2001.-216 p.

62. Barry W. J. Design and Analysis of Fault Tolerant Digital Systems Reading, Massachusetts: Addison-Wesley. - 1988. - 602 p.

63. Koren I:, Krishna C. Fault-Tolerant Systems Morgan Kaufmann Publishers. -2007. -400.p.78: Nelson V.P. Fault-tolerant computing: fundamental concepts // IEEE Computer. 1990. -№ 7. - P. 19-25.

64. Matrosova A. Yu., Levin Г., Ostanin S. A. Self-Checking Synchronous FSM Network Design with Low Overhead // Journal of VLSI Design. Overseas Publishers Assocoation. - vol. 11, № 1. - 2000, - P. 47-58.

65. Матросова А.Ю., Седов Ю.В. О свойствах неисправностей, порожденных многоуровневыми методами синтеза, примененными к частично монотонным системам булевых функций. Вестник ТГУ // Приложение. 2002. - №1(2). - С. 287-292.

66. Яблонский С.В. Введение в дискретную математику Москва: Высшая школа.-2002.-384 с.

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

68. Fiser P., Hlavicka J. Efficient Minimization Method for Incompletely Defined Boolean Functions // Proc. 4th Int. Workshop on Boolean Problems. Germany, 2000.-P. 91-98.

69. Fiser P., Hlavicka J. Implicant Expansion Method used in the BOOM Minimizer // Proc. IEEE Design and Diagnostics of Electronic Circuits and Systems Workshop. -2001. P. 291-298.

70. URL: http://service.felk.cvut.cz/vlsi/prj/BOOM/

71. Kohavi I., Kohavi Z. Detection of multiple faults in combinational logic networks //IEEE Transactions on Computers. -1975. vol. C-20, №6. — P. 556568.

72. Матросова А.Ю. Построение полного теста для схем, синтезированных методом факторизации / А.Ю. Матросова // Автоматика и вычислительная техника. 1978. - №5. С. 42^6.

73. Закревкий А.Д., Балаклей Л.И., Елисеева Н.А. и др. Синтез асинхронных автоматов на ЭВМ Изд. «Наука и техника». -1975. -184 с.

74. Murgai R., Brayton R., Sangiovani-Vincetelli A. Logic Synthesis for Field Programmable Gate Arrays Kluwer Academic Publisher. - 1995. - 425 p.

75. Матросова А.Ю., Жидкова E.B. Решение логических уравнений и анализ BDD графов // 5-ая Международная конференция «Проектирование дискретных систем». - Минск, Беларусь, 2004. - С. 51-55.

76. Матросова А.Ю., Никитин K.B. Синтез самопроверяемого комбинационного детектора равновесных кодов // Вестник ТГУ. 2000: - № 271.-С. 89-92.

77. Matrosova A., Andreeva V., Sedov Yu. Survivable Discrete Circuit Design // Proc. of the 8-th IEEE International On-Line Testing Workshop. Isle of Bendor, France, July 2002. - P. 44-48.

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

79. Matrosova A., Andreeva V., Ostanin S. Easy Testable Combinational Circuit Design // Proc. The 6th International Workshop on Boolean Problems. Freiberg, Germany, 2004. - P. 237-244:

80. Андреева B.B. Поиск максимальных расширений интервала булева пространства // Вестник ТГУ. Приложение. 2004. - №9(1), - С. 3-8.

81. Андреева В.В., Матросова А.Ю. Построение минимизированного проверяющего теста, обнаруживающий неисправности безызбыточной ДНФ' // Вестник ТГУ. Приложение. 2006. - №18. - С. ЗФ-39.

82. Андреева В.В. Поиск некоторых максимальных расширений интервала частичной булевой функции // Вестник ТГУ. Приложение. — 2007. №23. — С. 12-15.

83. Матросова А.Ю., Андреева В.В., Николаева Е.А. Синтез синхронных последовательностных устройств, устойчивых к кратковременным и перемежающимся неисправностям // Вестник ТГУ. — 2008. — №3(4). — С. 99-109.

84. Матросова А.Ю., Андреева В.В: Минимизация систем булевых функций, представляющих задание на синтез самопроверяемых дискретных автоматов // Автометрия. 2008. - Том 44. - №5. - С. 100-111.

85. Matrosova A., Andreeva V., Melnikov A., Nikolaeva Е. Multiple stuck-at fault and path delay fault testable circuit // Proceedings 7, East-West Design & Test International Symposium. Kharkov, Ukraine, 2008, — P. 356-364.