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

РГБ ОД

Томский государственный университет ; ,

! '. л1

УДК 681.325.5 На правах рукописи

Останин Сергей Александрович

МЕТОДЫ СИНТЕЗА КОНТРОЛЕПРИГОДНЫХ ДИСКРЕТНЫХ

УСТРОЙСТВ

Специальность 05.13.01 "Управление в технических системах"

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

Томск-2000

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

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

доктор технических наук, профессор Матросова А. Ю.

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

профессор Евтушенко Н. В.

кандидат технических наук, доцент Тюнина Л. В.

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

Томский политехнический университет, г. Томск.

Защита состоится " июня 2000 г. в 14.30 на заседании диссертационного совета Д063.53.03 при Томском государственном университете по адресу 634050. г. Томск, пр. Ленина 36.

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

Автореферат разослан " мая 2000 г.

Ученый секретарь диссертационного совета,

к. ф.-м. н., доцент

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

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

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

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

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

Разработан метод синтеза самопроверяемых синхронных дискретных устройств. В самопроверяемом устройстве, синтезированном данным мето-

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

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

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

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

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

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

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

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

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

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

4) Проекты министерства образования по разделу "Автоматика и телемеханика", направление - "Элементы, узлы и устройства автоматики, телемеханики и вычислительной техники" - 1996-1997 гг. "Исследование проблемы повышения качества тестирования и контролепригодного проектирования", - 1998-2000 гг.: "Исследование проблемы синтеза самотестируемых устройств и проблемы повышения качества тестирования".

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

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

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

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

- 4th IEEE International On-Line Testing Workshop (IOLTW'98) (Capri, Italy, July, 1998);

Международная сибирская конференция по исследованию операций (SCOR98) (Россия, Новосибирск. 1998);

The third international symposium "Application of the conversion research results for international cooperation" (SIBCONVERS'99) (Russia, Tomsk, 1999);

- 5th IEEE International On-Line Testing Workshop (IOLTW'99) (Rhodes, Greece. July, 1999).

Структура и объем диссертации. Диссертация состоит из введения, 4 глав, заключения и списка используемой литературы. Объем диссертации составляет и^-стр., в том числе: титульный лист - 1 стр., оглавление -3 стр., основной текст - \<аэ стр., библиография из 91 наименования - 9 стр., приложение - 5 стр.

Основное содержание работы

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

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

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

Формально частичная булева функция может быть задана посредством множеств и М) (¡=1,2,...,т) входных векторов или интервалов. Здесь т - число функций системы. Множество М\ (Л/,0) состоит из всех булевых векторов (интервалов), на которых данная функция принимает значите 1 (0). Причем Л/,0, М] с В" (/=1,2,...,»/), где В" - //-мерное булево пространство, и Л/;° п М) =0 (пустое множество).

Интервал можно представить троичным вектором с компонентами {0,1,}. Например, троичный вектор 01-1 представляет интервал {0101,0111}.

Между множеством интервалов и множеством конъюнкций из входных переменных имеет место взаимно однозначное соответствие. Интервалу 01-1

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

Вводится ряд определений.

Определение 1. Р-иптервал - это пара (и,И), состоящая из интервала и с В" и некоторого подмножества функций /? с Р. Здесь Р - множество функций системы. Подмножество функций И, входящее в состав пары (и, к), называют характеристикой интервала.

Определение 2. Р-ингервал (и,к) называется максимальным, если нельзя построить другой Р-интервал (и',1г), такой что и' з и .

Определение 3. ¡'"-элементом называется пара (у,И\), где у е В" и /,(У) = с для любой такой, что ]\ е И с: , ее /1,0} .

Определение 4. Будем говорить, что Р-интервал (и,И) покрывает Р-элеметн (у^), если уея, gc /7.

В рамках введенных определений исходную систему булевых функций можно представить множествами Р и О Р-элементов: Р = {(8. Ь)\ .....}, О = {(е,И):,.....Ь)1}, которые задают области единичных и нулевых значений функций системы. Множество //Т-интервалов. покрывающих в совокупности все Р-элементы множества Р и не покрывающих ни одного Р-элемснта множества О, называется множеством, реализующим систему.

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

В качест ве критерия выбирается условие реализации множеством IV безызбыточной системы ДНФ. Система ДНФ называется безызбыточной, если го множества И'реализующих ее Р-интервалов нельзя выбросить:

а) ни одной функции из характеристики интервала;

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

Множество ГГ, реализующее безызбыточную систему, будем называть безызбыточным. Безызбыточное множество Г-Г состоит из максимальных Р-интервалов.

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

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

Рассматриваются одиночные неисправности безызбыточной системы: исчезновение элемента /1 в характеристике И пары (к,И). Здесь к - сопоставляемая интервалу и конъюнкция, исчезновение переменной в конъюнкции к пары (к,И). В качестве кратных неисправностей безызбыточной системы рассматриваются всевозможные комбинации одиночных неисправностей. Вводятся понятия "а"- и "Ь"-тесгов.

Для каждой конъюнкции к пары (к,И) из IV отыскивается множество наборов значений переменных л- системы, называемых "а"-тестами. Каждый "а"-тест обращает в единицу только рассматриваемую конъюнкцию хотя бы для одной из функций /), упомянутых в характеристике /;. Для любой

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

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

набор принимается в качестве "Ь "-теста. Один и тот же набор может быть "Ь"-тсстом для нескольких конъюнкций из IV. С помощью "Ь"-тестов, построенных для всех букв всех конъюнкций (Г, гарантируется обнаружение любой из одиночных неисправностей, связанных с исчезновением переменных в конъюнкциях. Построение "а"("Ь")-теста сводится к отысканию одного корня соответствующего булева уравнения. Множества "а" - тестов и "Ь" -тестов, построенные для IV, объединяются в множество ©.

Теорема 1. Множество © "а"- и "Ь"-тестов обнаруживает все кратные неисправности безызбыточной системы ДНФ.

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

Теорема 2. Константная неисправность, одиночная и кратная, на полюсах элементов схемы С°ф эквивалентна кратной неисправности безызбыточной системы ДНФ.

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

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

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

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

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

1, ^ .V, О,, [ = (\,К;(МН)),

где /( - троичный вектор длины //, представляющий соответствующий входной интервал, - текущее состояние автомата, - следующее состояние, О, - выходной вектор длины т, \Г(МП) - число строк в списке.

Применив некоторое кодирование К (с длиной кодовых слов р) для вну тренних состояний, можно перейти к заданию функционирования автомата системой булевых функций в интервальной форме Р. I/ множество всех интервалов системы /\ Интервал и, е II, представленный троичным вектором длины п-р, получен конкатенацией входного интервала /( и кодового слова

К(5) для состояния .V,. Интервал)' и1 соответствует выходной вектор V,

длины т+р, полученный конкатенацией кодового слова ) для состояния

¿>, и выходного вектора 01. Итак, имеется описание системы Р частичных

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

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

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

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

Договоримся отождествлять интервалы и представляющие их троичные векторы.

Определение 5. Интервалы и1 из и ортогональны по х , если в и, компонента х принимает значение 1, а в ик - значение 0. Если и, ,ик ортогональны только по одной переменной, они 1-ортогональны, по двум - 2-ортогопалъпы, и т.д.

Определение 6. Если ч,,ик 2-ортогональны, и одна компонента в и, принимает значение 1, а в г/, - значение 0, а вторая в и, - значение 0, а в ик - значение 1, то интервалы и ик инверсно 2-ортогональны.

Теорема 3. Для того чтобы одиночные константные неисправности на входных полюсах схемы С проявляли себя на ее выходах однонаправлено, необходимо, чтобы любые интервалы и1,ик системы Р с разными выходными векторами, V, ^ \>к, были 2-ортогональны.

Обеспечение условия Теоремы 3 требует введения в систему Р дополнительных переменных.

В параграфе 3.3 рассматривается метод синтеза самопроверяемых синхронных дискретных устройств (синхронных автоматов) с наблюдением выходов устройства и линий обратных связей. Общая структура такого самопроверяемого синхронного устройства представлена на рис. 1.

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

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

Закодировав внутренние состояния автомата равновесным кодом, получаем из У7 систему Fl, такую что любые два интервала в множестве (У1, соответствующие различным внутренним состояниям, инверсно 2-ортогональны.

Вводятся дополнительные выходные переменные для обеспечения на выходах комбинационной схемы С кода, обнаруживающего все однонаправленные ошибки. В качестве такого кода можно использовать, например, код Бергера или равновесный код. Код Бергера предпочтительнее для обнаружения однонаправленных ошибок в том смысле, что он требует меньшего числа контрольных разрядов при заданном числе информационных разрядов. Длина кодовых слов в коде Бергера равна {т +р+\1о£г(т +р + \)\) ([~А' ] есть наименьшее целое, большее или равное А'), (»/+/>) - число информационных разрядов.

Получается система Р"1. выходные векторы v,2 в р~ строятся конкатенацией выходного вектора v,1 из Fl и булева вектора с, дайны

4

Рис. 1

в котором записано двоичное представление количества нулей в у' . Система Р~ содержит дополнительные функции по сравнению с Р.

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

Через и] обозначается множество интервалов системы Р2, не отличающихся по внутренним переменным, ] = 1,5, где л - число внутренних состояний ДУ. I!) разбивается на подмножества (У* . Каждому подмножеству сопоставляется в Р2 один и тот же выходной вектор. Интервалы ю разных подмножеств не обязательно 2-ортогональны друг другу. Обеспечивается 2-ортогональность таких интервалов.

Алгоритм.

1) Сопоставим каждому подмножеству вершину графа С]. Вершины е, и' соединены ребром, если найдется пара еС^.к^еО^, такая что интервалы 1-ортогональны (множества 1Р,и2рг не пересекаются, так как им соответствуют различные выходные векторы), е, v,-1 <е (\,...,г ] .

2) Выполним раскраску вершин графа С?; минимальным числом цветов.

3) Раскрасим таким образом все графы С. и определим требуемое количество цветов для системы Р2 в целом.

4) Представим цвета различными булевыми векторами в дополнительных входных переменных, выбрав минимальное число 8, дополнительных переменных.

5) Припишем ко всем троичным векторам, представляющим интервалы из С/* булев вектор длины 5,, представляющий один и тот же цвет.

В результате выполнения алгоритма получаем систему Р~. Система Р" содержит 5, дополнительных переменных по сравнению с Р~. Показывается, что, применив к Р" факторизационный метод синтеза, получаем схем)' С, в которой все неисправности из Т проявляются на ее выходах однона-правлено.

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

щихся различными выходными векторами. Такая система обозначается Р". Для получения Р" ко всем троичным векторам, представляющим интервалы из И\ (е = (Гг)) приписывается булев вектор одного и того же веса. Различным подмножествам 1'7Г,I'],, приписываются различные булевы векторы.

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

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

Далее в работе предлагается замена всех компонент со значением 0 на символ "-" для троичных векторов, представляющих интервалы системы /'". Получается система частичных булевых функций р"", в которой все компоненты троичных векторов, представляющих интервалы системы, принимают значение 1 или"-".

Теорема 4. Система Р""" реализует систему Р".

Показывается, что в схеме, полученной по системе /<....." методом факто-

ризационного синтеза, неисправности из класса Г проявляют себя однона-правлено.

Вводится ряд определений.

Определение 7. Для двух векторов а = (а,,...,^) и р=(р1>...Д1) в булевом пространстве В" выполняется отношение предшествования а < р , если а, <р,.....а„<р„.

Например, (0101) < (1101).

Определение 8. Если для двух векторов а = (а1,...,ал) и Р=(Р,.....Р„) в

булевом пространстве В" выполняется а < р или а > р , то такие векторы называются сравнимыми, иначе векторы называются несравнимыми.

Определение 9. Система булевых функций Р(х)-{/¡(х),...,/^х)} , называется монотонной, если для любых двух векторов а, ¡3 е В", таких что а < р . имеет место Р(а) < Р( р) .

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

Теорема 5. Система Р- монотонна.

При возникновении неисправности из Т схема реализует некоторую систему полностью определенных булевых функций /<'~и , отличающуюся от

Теорема 6. Для любой неисправности из Г система Р~'и монотонна.

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

Определение 10. Система /•'' имплицирует Р" (Р' > Р"), если для любых наборов а е Втр^ , Р'(а) > Р"(а) .

Класс неисправностей Т в схеме С разделяется на два подкласса:

- подкласс 7"', содержащий все неисправности в схеме, которые приводят к конвертированию некоторых компонент в выходных векторах для некоторых интервалов в системе Р из 1 в 0;

- подкласс Г1, содержащий все неисправности в схеме, которые приводят либо к исчезновению некоторых компонент некоторых интервалов Р~Л1 , либо к конвертированию некоторых компонент в выходных векторах для некоторых интервалов в системе /•"*" из 0 в 1.

Теорема 7. 1) Если ( е Т°, то Р~" > ; 2) если I е Г1, то Р~"' < Р"м .

Теорема 8. Неисправность г е 7' в схеме, синтезированной по системе Р"!"' факторизационным методом, проявляет себя на выходах схемы одно-направлено.

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

В параграфе 3.4 рассматривается построение самопровсрясмого синхронного дискретного устройства с наблюдением только его выходов. Вы-

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

Функционирование схемы С в исправном состоянии задается системой полностью определенных булевых функций 1Т~"". По Теореме 6 система монотонна.

При наличии неисправности г еТ функционирование схемы С задается

системой полностью определенных булевых функций . По Теореме 7

система У7*"1' монотонна.

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

вательностной схемы (рис. 2). Некоторые неисправности из Т могут не проявить себя на этих выходах. Их первое проявление, например, имеет место только на тех выходах С, которые соответствуют линиям обратных связей. Такие неисправности могут проявить себя на выходах у1,...,уш5 синхронного дискретного устройства (синхронной последователыюстной схемы) в последующие моменты времени его функционирования.

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

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

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

Определение 11. Последовательность ос --= (а, ,а,.....ая) предшествует

последовательности р = ({$,, (32.....|5в) (а < Р ). если а, < (3,, а, < ,.. • ,аа < (?а.

Рис. 2

Рассматривается произвольная входная последовательность у=(%%.....уа) из рабочей области функционирования синхронного устройства, где у,,I = (],я) - булевы векторы длины (п+Ь() . Последовательность у порождает последовательность а = (а,,а2.....аа) входных векторов

для комбинационной схемы С. Здесь а1= (|,а) булевы векторы длины (п + р+Ь.) . Воздействие последовательности а на входы схемы С приводит к последовательности = выходных векторов схемы.

При наличии неисправности / е Т схема реализует систему /*"""''. Входной последовательности а соответствует последовательность

а' - для . Результат воздействия последовательности а' на входы схемы с неисправностью приводит к последовательности выходных векторов = (р-'и(а[),р~и(а[)......

Теорема 9 1) Р*""(а) й )дпн любой последовательностей у и

любой неисправности / е 7Л ; 2) 1г~"(а) > (<х') хш любой последовательности у и любой неисправности г е. Т".

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

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

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

Рассматривается сеть, состоящая из к автоматных компонент А1,Аг,...,Лк ■ Каждая компонента сети есть автомат, функционирование которого заданно микропрограммным описанием.

Пусть Л'( и Г - множество входных и выходных полюсов автомата А1. Выделим из множества Л' = (^Х, всех входных полюсов всех компонент

ы\

к

сети некоторое подмножество I, а из множества 7 = У] всех выходных

ы

полюсов некоторое подмножество О. Рассмотрим отображение К : XV —> У. Будем считать, что это отображение задает множество связей между' элементами множества X' с одной стороны и множества Г с другой. Полученную таким образом структуру будем называть сетью N. Элементы множества 1 -входными полюсами, а элементы множества О - ее выходными полюсами.

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

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

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

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

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

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

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

(полюсах) компонент сети. Следовательно класс 7"'" неисправностей сети

к

Л" есть объединение неисправностей каждой компоненты 7,Л" -.

ы

Любая неисправность из Т1 проявляется однонаправлено на выходах компоненты Д (по Теореме 8). Анализируется распространение последствий неисправности компоненты на выходы сети.

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

1с

сети: |2| = > гас - множество внутренних переменных для Д ,

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

Ф(Х,2) - система полностью определенных булевых функций, полученная суперпозицией систем функций в соответствии с отображением N , задающем структуру сети. Здесь А' - множество входных переменных сети. Система Ф(Х,2) содержит функций. Здесь У -

множество выходов сети.

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

Теорема 10. Ф(Х,2) - монотонная система.

Рассматривается произвольная входная последовательность у из рабочей области функционирования сети. Последовательность у состоит из булевых векторов длины |А'|. Каждая последовательность у начинается с

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

Последовательность а булевых векторов длины |Л'|+|/?| порождается входной последовательностью у .

Для произвольной неисправности Л г е Т'%" система Ф'(Х, 2) описывает функционирование неисправной сети.

Под действием неисправности ? последовательность а трансформируется в последовательность а'.

Теорема 11. Система Ф'(Х,1) - монотонна.

Теорема 12. Для любой неисправности /, I е 7,Л', система Ф(Х,2) имплицирует Ф'(Х,1) (Ф(Х,И)>Ф'(Х/£)). либо Ф'(Х//) имплицирует Ф(Х,2) (Ф'(Х,2)>Ф(Х,г)).

Пример структуры самопроверяемой сети приведен на рис. 3.

выход 1 выход 2

Рис. 3

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

В параграфе 3.6 приводятся результаты экспериментов на бенчмарках, показавшие, что число требуемых дополнительных входных пере-

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

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

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

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

Напомним, что кодирование состояний называется противогоночньш, тс есть гарантирующим отсутствие опасных состязаний при исправном функционировании схемы, если и только если для любой пары переходов , (х,к,1) имеет место условие: \К(1),К() ;]Л [К(к), К(1.)] = 0 .

Здесь К(¡) - двоичный вектор, представляющий код состояния /, х ■ входной двоичный вектор, \К(¡), К(])\ - минимально покрывающий интервал для элементов, представленных двоичными векторами.

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

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

Теорема 13. Если для любой пары переходов (х,1,]),(х,к,1) имеет место условие: [КП), К(])\ и \К(к),К(!)\ - инверсно 2-ортогональны, то кодирование К является противогоночным для схемы с неисправностью из класса Т.

Синтез асинхронного самопроверяемого автомата выполняется по микропрограммном}' заданию его функционирования. Кодирование внутренних состояний обеспечивает выполнение условий Теоремы 13. Остальные этапы синтеза совпадают с этапами, описанными в параграфе 3.3.

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

Заключение

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

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

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

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

3) Метод синтеза самопроверяемых автоматных сетей, сохраняющий исходное разбиение сети на компоненты.

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

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

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

1) Матросова А. 10., Останин С. А. К синтезу комбинационных схем, обеспечивающему их контролепригодность для кратных константных неисправностей// XXIV Международная конференция и дискуссионный научный клуб "Информационные технологии в науке, образовании, телекоммуникации и бизнесе" (IT+SE'97): Тр. конф. Украина, Крым, Ялта-Гурзуф, 1997. С. 143-144.

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

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

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

5) Матросова АЛО., Останин С.А. Синтез самопроверяемых синхронных посдедовательностных устройств// Международная сибирская конференция по исследованию операций: Тез. докл., 22-27 июня, 1998г. Новосибирск, 1998. С. 132.

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

7) MatrosovaA.Yu., Ostanin S.A. Self-Checking Synchronous Sequential Circuit Design for Unidirectional Error// IEEE European Test Workshop: Compendium of papers, May 27-29, 1998. Sitgcs, Barcelona, Spain. 1998.

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

9) Levin I., Matrosova A. Yu., Sinelnikov V., Ostanin S. A. Totally Self-Checking FPGA based FSM'/ 5d; IEEE Intl. On-Line Testing Workshop: Compendium of papers, July 1999. Rhodes, Greece. 1999.

10) Матросова A.10., Останин С.А. Синтез самопровсряемых синхронных устройств и сетей из них// Конференция "Новые информационные тех-

нологии в исследовании дискретных структур": Тез. докл. Екатеринбург. 1998. С. 173-179.

11) Afatrosova A. Yu., Levin /., Ostanin S. A. Self-Checking Synchronous FSM Network Design with Low Overhead// Journal of VLSI Design.-Overseas Publishers Assocoation.volOO, .№00. 2000.pp. L-L2.

12) Оспшшш C.A. Синтез самопроверяемых асинхронных последовательно-стных схем с нормальными функциями переходов/выходов// Third international symposium "Application of the conversion research results for international cooperation" (SIBCONVERS'99): Proceedings. Russia, Tomsk. 1999. pp. 222-224.

13) Ocmainni С. А. Синтез самопроверяемых асинхронных автоматов с нормальными функциями переходов/выходов// Математическое моделирование. Кибернетика. Информатика: Сб. статей. Томск: Изд-во Том. Ун-та, 1999. С. 120-126.

ВВЕДЕНИЕ.

1. ОБЗОР МЕТОДОВ САМОПРОВЕРКИ И САМОТЕСТИРОВАНИЯ ДИСКРЕТНЫХ УСТРОЙСТВ.

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

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

1.2.1. Методы генерации тестовых наборов (тестовых последовательностей).

1.2.2. Методы анализа выходных реакций.

1.2.3. Самотестируемые последовательностные схемы.

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

1.4. Выводы.

2. СИНТЕЗ ЛЕГКОТЕСТИРУЕМЫХ КОМБИНАЦИОННЫХ УСТРОЙСТВ.

2.1. Введение.

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

2.3. Безызбыточные системы ДНФ.

2.4. Факторизационные методы синтеза.

2.5. Анализ процедуры синтеза.

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

2.7. Выводы.

3. СИНТЕЗ САМОПРОВЕРЯЕМЫХ СИНХРОННЫХ АВТОМАТОВ

И АВТОМАТНЫХ СЕТЕЙ.

3.1. Введение.

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

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

3.3.1. Исследование неисправностей схемы.

3.3.2. Кодирование внутренних состояний.

3.3.3. Введение дополнительных выходных переменных.

3.3.4. Введение дополнительных входных переменных.

3.3.5. Упрощение системы функций.

3.3.6. Получение однородной системы.

3.3.7. Монотонные системы и их свойства.

3.4. Синтез самопроверяемых синхронных автоматов с наблюдением только выходов схемы.

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

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

3.7. Выводы.

4. СИНТЕЗ САМОПРОВЕРЯЕМЫХ АСИНХРОННЫХ АВТОМАТОВЮ

4.1. Введение.

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

4.3. Кодирование внутренних состояний автомата.

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

4.7. Выводы.

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

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

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

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

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

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

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

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

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

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

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

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

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

4) Проекты министерства образования по разделу "Автоматика и телемеханика", направление - "Элементы, узлы и устройства автоматики, телемеханики и вычислительной техники" - 1996-1997 гг. "Исследование проблемы повышения качества тестирования и контролепригодного проектирования", - 1998-2000 гг.: "Исследование проблемы синтеза самотестируемых устройств и проблемы повышения качества тестирования".

Результаты работы также используются в курсе лекций "Диагностика дискретных устройств" на факультете прикладной математики и кибернетики Томского государственного университета (ТГУ).

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

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

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

2) 4th IEEE International On-Line Testing Workshop (IOLTW'98) (Capri, Italy, July, 1998);

3) Международная сибирская конференция по исследованию операций (SCOR98) (Россия, Новосибирск, 1998);

4) The third international symposium "Application of the conversion research results for international cooperation" (SIBCONVERS'99) (Russia, Tomsk, 1999);

5) 5th IEEE International On-Line Testing Workshop (IOLTW'99) (Rhodes, Greece, July, 1999).

Структура и объем диссертации. Диссертация состоит из введения, 4 глав, заключения и списка используемой литературы. Диссертация содержит 12 рисунков и 12 таблиц. Объем диссертации составляет 126 стр., в том числе: титульный лист - 1 стр., оглавление - 3 стр., основной текст - 107 стр., библиография из 91 наименования - 9 стр., приложение - 5 стр.

4.7. Выводы

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

Введено понятие монотонной системы и отношение импликации между системами.

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

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

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

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

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

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

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

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

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

3. Wadsack R. L. Fault Modeling and Logic Simulation of CMOS and MOS Integration Circuits//Bell System Technical Journal. -May-June, -1978. -Pp. 14491474.

4. Rajsuman R. Digital Hardware Testing: Transistor-Level Fault Modeling and Testing. -Boston-London.: Artech House, 1992.

5. Menger K. Checkups for Combinational Gates// IEEE Trans. On Airospace. -1963. AS-l,-№ 2. -Pp. 954-960.

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

7. McCluskey E. J. Built-in Self-Test Techniques// IEEE Design & Test of Computers. -April 1985. -Pp. 21-28.

8. Bardell P. H., McAnney W. H., Savir J. Built-in Test for VLSI Pseudorandom Techniques. New York: John Wiley&Sons Inc. -1987.

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

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

11. Savir J., Bardell P. H. Built-in-Self-Test: Milestones and Challenges// VLSI design. -Vol. 1, -№i. -1993. pp. 23-44.

12. McCluskey E. J. Verification Testing-A Pseudo-Exhausted Test Technique// IEEE Tran. on Computers. -Vol.C-33, -№6. -1984. -Pp. 541-546.

13. Tang D. T., Chen C. L. Iterative Exhaustive Pattern Generation for Logic Testing// IBM J. Res. Develop. -Vol. 28, -№2. -1984. -Pp. 212-219.

14. Min Y., Li Z. Pseudo-Exhausted Testing Strategy for Large Combinational Circuits// Computer Systems Science and Engineering. -Vol. 1, -№4. -1986. -Pp. 213-220.

15. Furuya K. A Probabilistic Approach to Locally Exhaustive Testing// Tran. of the IEICE. -Vol. E-72. -1989. -Pp. 656-660.

16. Hellebrand S. Sythese vollstanding testbarer Schaltungen// VDI Verlag. Reihe 10, -№177. -1991.

17. Rajski J., Tyszer J. Recursive Pseudo-Exhaustive Test Pattern Generator// IEEE Tran. on Computers. -Vol. 42, -№12. -1993. -Pp. 1517-1521.

18. Wunderlich H. J. Self Test Using Uniquiprobable Random Patterns// Proc. IEEE Int. Symposium on Fault Tolerant Computing. -1987. -Pp. 258-263.

19. Wunderlich H. J. Multiple Distributions for Biased Random Test Patterns// Proc. IEEE Int. Test Conference. -1988. -Pp. 236-244.

20. Hartmann J. The Random Testability of the n-Input AND Gate// Proc. 8th Annual Symposium on Theoretical Aspects of Computer Science. -1991. -Pp. 488498.

21. Hartmann J. On Numerical Weight Optimization for Random Testing// Proc. EDAC-EUROASIC. -1993. -Pp. 223-230.

22. Pateras S., Rajski J. Generation of Correlated Random Patterns for the Complete Testing of Synthesized Multi-Level Circuits// Proc. 28th Design Automation Conference. -1991. -Pp. 347-352.

23. Pateras S., Rajski J. Cube-Contained Random Patterns and their Application to the Complete Testing of Synthesized Multi-Level Circuits// Proc. IEEE Int. Test Conference. -1991. -Pp. 473-482.

24. Agarwal V. K., Cerny E. Store and Generate Built-in Testing Approach// Proc. 11th Int. Symposium on Fault-Tolerant Computing. -1981. -Pp. 35-40.

25. Daehn W. Deterministische Test. Dissertation. Universität Hannover. -1993.

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

27. Eichelberger Е. В., Williams Т. W. A Logic Design Structure for LSI// Proc. 14th Design Automation Conference. -1977.- Pp. 462-468.

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

29. Cheng К. Т., Agrawal V. D. A Partial Scan Method for Sequential Circuits with Feedback// IEEE Tran, on Computers. -Vol. 39, -№4. -1990. -Pp. 544548.

30. Gupta R., Gupta R., Breuer M. A. The BALLAST Methodology for structuted Partial Scan Design// IEEE Tran, on Computers. -Vol. 39, -№4. -1990. -Pp. 538-544.

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

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

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

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

35. Reinert D. Entwurf und Diagnose komplexer digitaler Systeme. -Berlin: VEB Verlag Technik. -1983.

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

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

38. Minero R. H., Anello A. J., Furey R. G., Palounek L. R. Checking by pseu-doduplication/ US PS 3660646, G06F 11/00. -1972.

39. Murayama N. Matrix Collating System/ US PS 3548376, НОЗК 13/34. -1970.

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

41. Горожин А. Д., Крайнов К. M. Построение полностью самопроверяемых комбинационных устройств с использованием полиномиальных форм// Автоматика и телемеханика. -№12. -1979.- с. 159-166.

42. Аксенова Г. П. Необходимые и достаточные условия построения полностью проверяемых схем свертки по модулю 2// Автоматика и телемеханика. -№9.-1979. -с. 126-135.

43. Niraj К. J., Abraham J. A. The Design of Totally Self-Checking Embeddedth

44. Checkers// Digest 14 Ann. Int. Conf. on Fault-tolerant Computing. -1984. -p. 265-270.

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

46. Bums S. W. and Jha N. K. A Totally Self-Checking Checker for a Parallel Unordered Coding Scheme// Proc. IEEE VLSI Test Symposium. -1992. -p. 165170.

47. Dong H. Modified Berger Codes for Detection of Unidirectional Errors// Digest of Papers 12th Annual Symp. On Fault-Tolerant Concurrent Computing. -1982.-pp. 317-320.

48. Anderson D. A., Metze G. Design of Totally Self-Checking Check Circuits for m-out-oi-n Codes// IEEE Tran. on Computers, -vol. C-22. -1973. -pp. 263-269.

49. Khakbas J. Totally Self-Checking Checker for 1-out-of-rc Code Using Two-Rail Codes// IEEE Tran. on Computers, -vol. C-31. -1982. -pp. 677-681.

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

51. Paschalis A. M., Nikolos D., Halatsis C. Efficient Modular Design of TSC Checkers for M-out-of-2MCodes//IEEE Tran. on Computers, -vol. 37. -1988. -pp. 301-309.

52. 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. -pp. 289-296.

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

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

55. Согомонян Е. С. Построение самопроверяемых схем встроенного контроля для комбинационных устройств// Автоматика и телемеханика. -№2. -1974. -с. 121-133.

56. Аксенова Г. П., Согомонян Е. С. Построение самопроверяемых схем встроенного контроля для автоматов с памятью// Автоматика и телемеханика. -№7.-1975.- с. 132-142.

57. Гессель М., Согомонян Е. С. Построение самотестируемых и самопроверяемых комбинационных устройств со слабонезависимыми выходами// Автоматика и телемеханика. -№3. -1992.- с. 150-160.

58. Sogomonyan E. S., Goessel M. Design of Self-Testing and On-Line Fault Detection Combinational Circuit with Weakly Independent Outputs// Journal of Electronic Testing: Theory and Application. -№4. -1993.- pp. 267-281.

59. Гессель M., Морозов А. А., Сапожников В. В., Сапожников Вл. В. Построение комбинационных самопроверяемых устройств с монотонно независимыми выходами// Автоматика и телемеханика. -1994. —с. 148-160.

60. Goessel М., Sogomonyan Е. 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.

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

62. Rao Т., Fujiwara E. Error Control Coding for Computer System. -Englewood Cliffs, NJ: Prentice Hall, -1989.

63. Jha N. K. Separable for Detecting Unidirectional Errors// IEEE Tran. on Computer-Aided Design. -Vol.8, -№5. -1989. -pp. 571-574.

64. Busaba F. Y., Lala P. K. Input and Output Encoding Techniques for On-Line Error Detection in Combinational Logic Circuits// Proc. 11th IEEE VLSI Test Symp.-1993.-pp. 48-54.

65. Busaba F. Y., Lala P. K. Self-Checking Combinational Circuit Design for Single and Unidirectional Multibit Error// JETTA. -№5. -1994. -pp. 19-28.

66. Sciuto D., Silvano C., Stefanelli R. Systematic AUED Codes for Self-Checking Architectures// Int. Symp. on Defects on Fault Tolerance in VLSI Systems. -1998, November.

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

68. Варшавский В. И., Розенблюм Л. Я., Таубин А. Р. Полностью самопроверяемые асинхронные комбинационные схемы и свойство индицируемости//Автоматика и телемеханика. -№5. -1982. -с. 138-146.

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

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

71. Матросова А.Ю., Байда В.Д., Сафронов В.В. Синтез легкодиагностируе-мых автоматов// Методы и системы технической диагностики. Вып. 1. Изд-во Саратовского университета. -1980. -С. 17-26.

72. Kohavi I., Kohavi Z. Detection of Multiple Faults in Combinational Logic Networks// IEEE Tran, on Computers. -VC-20, -№6. 1-975. -Pp.556-568.

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

74. Lisanke R. Logic Synthesis and Optimization Benchmarks User Guide: Version 3.0/ Technical Report, Microelectronics Center of North Caroline. -Dec. 1991.

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

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

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

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

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

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

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

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

83. 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.120

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

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

86. Ангер С. Асинхронные последовательностные схемы. -М.: Наука, -1977. -400 с.

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

88. Декан факультете " " "г"г"'г

89. Зав. кафедрой программирования ФПМК, профессор /фЛСбЬл Матросова А.Ю.1. УТВЕРЖДАЮ»1. СПРАВ!

90. Руководитель проекта, Агибалов Т.П.1. СПРАВКА

91. Колесник А.Г. » мая 2000 г.1. СПРАВКА

92. Заведующий отделом 102 профессор ^^^—■———3 Семенов B.C.