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

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

НИКОЛАЕВА Екатерина Александровна

Алгоритмы синтеза легко тестируемых комбинационных схем и

тестов для кратных константных неисправностей ii неисправностей задержек путей

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

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

2 8 АПР 2011

Томск-2011

4844630

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

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

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

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

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

кандидат технических наук, доцент Липский Валерий Борисович

Ведущая организация: гоу впо <<Национальный

исследовательский Томский политехнический университет»

Защита состоится: 12 мая 2011 г. в 10.30 час. на заседании диссертационного совета Д 12.267.12 при ГОУ ВПО «Томский государственный университет» по адресу: 634050, г. Томск, пр. Ленина, 36, 2 уч. корпус, ауд. 2126.

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

Автореферат разослан 8 апреля 2011 г.

Ученый секретарь диссертационного совета, к.ф.-м.н, доцент П.Ф. Тарасенко

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

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

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

Цель работы. Целью диссертационной работы является исследование контролепригодных свойств схем, сохраняющих системы ДНФ. Для ее реализации были рассмотрены существующие методы синтеза схем, использующие в качестве задания на синтез либо системы ДНФ, либо системы BDD (Binary Decision Diagram)-rpa$oa. Для методов синтеза по системе ДНФ, обеспечивающих сохранение систем ДНФ, были предложены эвристики, ориентированные на сокращение аппаратурных затрат, а для методов синтеза по системе BDD-графов сформулированы требования к покрытию графов программируемыми логическими блоками (ПЛБ), обеспечивающие сохранение систем ОДНФ. Для схем, полученных покрытием систем SDD-графов программируемыми логическими блоками, разработаны алгоритмы построе-

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

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

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

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

-Для схем, полученных покрытием системы бО£>-графов программируемыми логическими блоками (ПЛБ) и сохраняющих системы ОДНФ, предложен алгоритм построения проверяющего теста для кратных константных неисправностей на полюсах ПЛБ, не требующий перечисления всевозможных кратных неисправностей и получающийся расширением проверяющего теста для одиночных неисправностей.

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

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

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

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

-«Участник молодежного научно-инновационного конкурса 2008» («УМНИК») по направлению Информационные технологии.

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

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

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

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

1. The 22lh IEEE international Symposium on Defect and Fault-Tolerance in VLSI System (Rome, Italy, 2007).

2. The 7th East-West Design & Test International Symposium (Lviv, Ukraine, 2008).

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

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

5. The 8th East-West Design & Test International Symposium (Moscow, Russia, 2009).

6. The 9'h East-West Design & Test International Symposium (St. Petersburg, Russia, 2010).

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

Структура и объем диссертации. Диссертация состоит из введения, 4-х глав, заключения и списка используемой литературы, включающий 95 наименований. Общий объем диссертации составляет 134 страницы текста, включая 33 рисунка и 7 таблиц.

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

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

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

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

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

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

К методам синтеза, сохраняющим систему ДНФ, относятся факторизаци-онные методы синтеза, которые разделяются на двухуровневые и многоуровневые.

Рассмотрим метод многоуровневого факторизационного синтеза, представленный в книге Murgai R., Brayton R., Sangiovanni-Vincentelli A. «Logic Synthesis for Field Programmable Gâte» (Kluver Academic Publishers. 1995. P. 425) и основанный на выделении ядер и соядер.

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

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

Определение 3. Представление ДНФ в виде D = ДД v Д, где Д - делитель, Д, - частное, Д - остаток от деления, называется делением ДНФ Д Если ДД - алгебраическое произведение, то деление ДНФ D называется алгебраическим.

Если ДНФ нельзя представить в виде: D^kD^ где к - элементарная конъюнкция, то говорят, что D не разложима по конъюнкциям.

Главные делители ДНФ D есть ДНФ Д,, ..., Д,, такие, что D = DuK2X v Dn,...D = DuK2r v D)r, и Dn,..., Дг не разложимы по конъюнкциям. Главные делители Дь ..., Dlrназываются ядрами этой ДНФ, а соответствующие им частные (конъюнкции) - соядрами.

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

1. Сопоставление ядру (соядру) С новой переменной и,-.

2. Замена ядра (соядра) С в каждой ДНФ, его содержащей, на эту переменную.

3. Введение нового уравнения и, = Д в систему, где Д, представляющая ядро (или соядро) ДНФ, aiij- внутренняя переменная.

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

тему ДНФ имеет смысл заменить новой системой. Буквой будем называть переменную вместе с ее знаком инверсии.

Теперь в новой системе выделяем ядра (или соядра) и выбираем в определённом выше смысле лучшее из них; заменяем систему и так далее, пока переход к более простой системе оказывается возможным.

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

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

Предлагается две оценки качества выделяемого соядра.

Пусть К - некоторое оцениваемое соядро, К, -]-ая конъюнкция системы, г - ранг соядра К,г}- ранг конъюнкции Кр п - количество различных конъюнкций системы, N = {1, ..., я} - множество номеров конъюнкций, У - множество номеров конъюнкций, разложимых по К, то есть поглощаемых К, т-количество функций в системе.

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

Преобразуем систему, заменив соядро К промежуточной переменной.

Пусть ег — число букв в системе, в которой соядру К сопоставлена новая переменная щ и произведена замена каждого вхождения соядра этой переменной. При замене ранги конъюнкций /Г, системы, где , уменьшатся на г-1. В систему также будет добавлена новая конъюнкция ранга г. Тогда:

= Ек/,+Еи е* = Xкп+Е (г/-г+1)+г

Следовательно:

= X 0/ ~ Гг + г ~ О]" г = (г -1)^ - г = г* - А - г.

¡ъ!

к

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

тему добавлена функция вида и = К, где и промежуточная переменная. Значения рангов преобразованных конъюнкций, изменились: г} - г,—г+1, где jsJ.

Пусть /2 - множество номеров ДНФ, в которых можно выделить ядро, соответствующее соядру К, и р = |/2|. Пусть п' - количество ДНФ, в которые

входит хотя бы одна конъюнкция, содержащая промежуточную переменную, сопоставленную соядру К. Пусть /1={1 ...т}\12.

Обозначим символом ./, множество номеров конъюнкций, которые составляют /'-ую ДНФ. ./' - множество номеров конъюнкций, составляющих /'ую ДНФ и содержащих промежуточную переменную, сопоставленную К. У" - множество номеров конъюнкций, составляющих /-ую ДНФ и не содержащих промежуточную переменную, сопоставленную К.

= Е Е г/ + г = Е Е 0 + Е Е Г, + г •

'=) уеЛ /с/, /с/2 уе./*

Сопоставим промежуточные переменные ядрам (делителям), порожденным рассматриваемым соядром К (частным). Изменения коснутся только функций, номера которых принадлежат /2. Конъюнкции, соответствующие множеству ^ (/ е /2) в /-ой функции, будут заменены конъюнкцией вида и,и, где ui - переменная, сопоставленная очередному ядру. Таким образом, число букв в ДНФ, номер которой (/) содержится в 12: 2 + ЕГ/- В систему также

м

будут добавлены ДНФ, соответствующие ядрам. Число букв в каждой такой

ДНФ определяется выражением: Е(о -1).

№

Обозначим символом е3 число букв в системе, полученной заменой выделенных ядер внутренними переменными и добавлением ДНФ, сопоставленных ядрам.

/ \

= Е Е+ Е 2 + Е г> + Е Е - ' и

/€/5 jcJ, /2 ^ ) /е./,'

/с/г ^ /еу; ¡<у, Л' j€^; ) ¡е[2

Значение параметра к можно выразить следующим образом: * = £ к'! = Е И + ЕI-7'!= " р + Е И - следовательно:

г=1 /е./| /с/2 '"е/г

Д 2 = е1 - еъ - (е, - сг) + (е2 - с,) - кг - г - п' - р .

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

сложно, чем Д^ так как требует дополнительного определения значений п' и р.

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

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

Алгоритм выделения соядра.

1. В корень дерева поместим фиктивное значение - конъюнкцию, множество букв которой пусто.

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

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

3. Продолжаем построение дерева в соответствие с пунктом 2, пока это возможно.

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

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

Структуру минимизированной системы ДНФ, полученной из исходной системы ДНФ, в упомянутой выше книге предлагается представлять комбинационной логической сетью. Эта сеть используется в дальнейшем для построения .s'-графа (subject graph).

Процедура построения ¿-графа заключается в реализации фиктивными базисными элементами каждой ДНФ, сопоставленной вершине комбинационной логической сети. В качестве фиктивных базисных элементов выбираются двухвходовой элемент НЕ-И (НЕ-ИЛИ) и элемент НЕ. Реализация со-

храняет ДНФ, сопоставляемую вершине сети. Затем происходит замещение вершин исходной сети соответствующими подграфами.

Утверждение 1. Схема, представляемая ¿-графом, сохраняет исходную систему ДНФ.

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

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

Пусть Г = } - система ДНФ, являющаяся заданием на син-

тез комбинационной схемы.

Определение 1. ДНФ О' является дизъюнктивным фактором системы Ь\ если Т>' получается из ^(г е {1,...,от}) вычеркиванием некоторых конъюнкций, £)' с Г,.

Будем говорить, что В* является частью Г?

Определение 2. Порождающим множеством дизъюнктивного фактора £)' будем называть множество ДНФ системы, для которых £>* является частью. В порождающее множество могут быть включены не все такие ДНФ.

Пусть К = {К1,К2,...,Кг1} - множество всех конъюнкций системы

Определение 3. Конъюнкция К' является конъюнктивным фактором системы ДНФ, если К' получена из конъюнкции АГ, системы Е вычеркиванием некоторых букв, К' а К..

Будем говорить, что К' является частью К,.

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

В двухуровневых методах синтеза предполагается выполнение следующих шагов:

- выбор множества £>*,£)*,..., /У дизъюнктивных факторов системы и

построения для каждого фактора порождающего множества;

- выбор множества /С,', К'1,...,К'1 конъюнктивных факторов системы и построения для каждого фактора порождающего множества;

- построение на основе выбранных факторов и порождающих множеств схемы С, реализующей систему{ ,...,/■"„,}.

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

и

щихся букв в конъюнкциях и повторяющихся конъюнкций. Обозначим полученную систему ДНФ D'.

Определение 5. Будем говорить, что конъюнкции являются пересекающимися по буквам, если пересечение составляющих их букв не пусто.

Определение 6. Две ДНФ будем называть пересекающимися, если они содержат одинаковые конъюнкции.

Утверждение 2. Если конъюнкция системы F принадлежит порождающим множествам пресекающихся по буквам конъюнктивных факторов, то в системе D' присутствуют конъюнкции, содержащие повторяющиеся буквы.

Утверждение 3. Если ДНФ системы F принадлежит порождающим множествам пресекающихся дизъюнктивных факторов, то в системе D' присутствуют ДНФ, содержащие повторяющиеся конъюнкции.

Утверждение 4. Схема С , построенную при условии, что порождающие множества пересекающихся конъюнктивных (дизъюнктивных) факторов не содержат одинаковых конъюнкций (дизъюнкций), сохраняет систему ДНФ F.

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

Были составлены программы, реализующие приведенные во второй главе методы синтеза комбинационных схем по системам ДНФ, сохраняющие эти системы. Использовалось STG (State Transition Graph)-onисание поведения синхронного последовательностного устройства, в котором входные и выходные состояния реализуемого им автомата уже закодированы. Внутренние состояния автомата кодировались плотным кодом.

При переходе от системы частичных функций к системам полностью определенных функций строилась безызбыточная система ДНФ, представляющая комбинационную составляющую последовательностного устройства. Использовалась программа, разработанная A.B. Мельниковым, реализующая метод конкурирующих интервалов, предложенный А.Д. Закревским. Далее применялась описанная во второй главе процедура минимизации, основанная на выделение ядер и соядер. Для построения s-графа использовался фиктивный базис <НЕ, НЕ-И>.

Экспериментальные результаты показали, что применение предложенной процедуры позволяет в среднем уменьшить сложность схемы на 36,58%, тогда как использование случайного выбора - на 31,94%. Также экспериментальные результаты показали что применение модифицированного двухуровневого метода, по сравнению с многоуровневым методом, требует значительно больших временных и вычислительных затрат и не даёт существенного сокращения аппаратурных затрат.

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

SDD-графы являются компактным представлением систем ортогональных ДНФ (ОДНФ). В разделе 2.2 приводится описание известного подхода к построению комбинационных схем покрытием системы /ШО-графов программируемыми логическими блоками (ПЛБ) и выделяются требования к покрытию, сохраняющему систему. Под покрытием системы ДОДграфов ПЛБ здесь и далее понимается покрытие системы BDD-графов BDD-деревьями, реализующими функции не более чем от к переменных. Здесь к -число входов ПЛБ, причем ПЛБ реализует функцию, представленную соответствующим покрывающим деревом.

Пусть_Ддгь х2,...,х„) - булева функция от п переменных.

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

- вершины, не имеющие исходящих дуг, называемые терминальными, отмечаются символом 0 или 1;

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

Каждой нетерминальной вершине v ставится в соответствие функция /,, корню - функция / Построение ЯОДграфа основано на использовании разложения Шеннона в каждой нетерминальной вершине v.

Каждой нетерминальной вершине v ВДО-графа соответствует функция/,, (/,), представленная в виде ОДНФ соответствующими простыми цепями, соединяющими v с 1(0)-концевой вершиной ВОДграфа.

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

Определение 9. BDD-граф называется сокращенным, если он не содержит ни изоморфных подграфов, ни вершин v, для которых обе дуги, исходящие из вершины, заходят в изоморфные подграфы.

Определение 10. Упорядоченный сокращенный BDD-граф называется ROBDD (Reduced Ordered Binary Decision Д'я^гяот)-графом

При построении Free 2ШДграфа порядок переменных, по которым производится разложение, заранее не фиксирован. Free BDD-граф может быть сокращённым, т.е. может не содержать ни изоморфных подграфов, ни вершин v, дуги которых заходят в изоморфные подграфы. В каждой нетерминальной вершине переменная разложения выбирается по тому или иному критерию независимо от других нетерминальных вершин, что позволяет в некоторых случаях сократить число вершин ВДДграфа.

Процедура построения BDD-графа системы функций или SBDD-графа (Shared Binary Decision Diagram) состоит в следующем. Первоначально каждая функция в системе представляется в виде BDD-графа одного и того же

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

Удалим из системы SBDD-графа все дуги, заходящие в 0-концевую вершину, и получим SÔDD-граф, представляющий поведение комбинационной схемы. Назовем его ЛЖЮ-графом схемы. Покроем его программируемыми логическими блоками (ПЛБ), создаваемыми на базе LUT (Look up Table)-технологий. Рассматриваемым в работе условием построения покрытия является сохранение системы ОДНФ, порожденной ,ШЗ£>-графом схемы. Это значит, что, выполнив по синтезированной схеме подстановки функций, реализуемых соответствующими ПЛБ с учетом запрета на упрощения формул при раскрытии скобок, получим систему ОДНФ, содержащую все конъюнкции, порожденные простыми цепями, соединяющими корни SSDD-графа схемы с его 1-концевой вершиной, и только их.

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

- выходу ПЛБ ставится в соответствие либо корневая вершина, либо нетерминальная вершина SBDD-графа схемы;

- булева функция, реализуемая ПЛБ, представляется соответствующим подграфом 55£>£>-графа схемы, покрытым этим ПЛБ;

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

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

В третьей главе исследуются контролепригодные свойства схемы, построенной путём покрытия SBDD-графа программируемыми логическими блоками. Используются введенные в работе А. Ю. Матросовой, Е. С. Луков-никовой «Построение проверяющих тестов для одиночных и кратных неисправностей на полюсах элементов схем, синтезированных на базе ПЛИС (FPGA)-техпологий» Приложение № 23. Доклады Сибирской научной школы-семинара с международным участием «Компьютерная безопасность и криптография». - 2007. - С. 229—241. базовые неисправности SBDD-графа, представляющие одиночные константные неисправности на полюсах ПЛБ комбинационной схемы, полученной покрытием графа с сохранением соответствующей системы ОДНФ. Предлагается алгоритм построения тестового набора для произвольной кратной константной неисправности на полюсах

ПЛБ рассматриваемой комбинационной схемы и алгоритм построения проверяющего теста для всех кратных константных неисправностей схемы.

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

Определение 11. Неисправность нетерминальной вершины v SBDD-графа, в присутствии которой функция fv обращается в константу 0(1)

и /, обращается в константу 1(0), будем называть неисправностью константа

0(1) вершины v.

Определение 12. 01(10)-неисправностью нетерминальной вершины 5Ж)£>-графа будем называть неисправность дуг вершины, в присутствии которой дуга, отмеченная символом 0, заменяется константой 0(1), а дуга, отмеченная символом 1, заменяется константой 1(0). Дугу, заменённую в SSDD-графе константой 0(1), будем называть 0(1)-дугой.

Так как порядок разложения по переменным при построении Free BDD-графа не фиксирован, в SBDD-графе возможно существование вершины v, отмеченной индексом /, для которой = fj'°l, то есть существование неизоморфных подграфов, реализующих одну и ту же функцию. Неисправность 10 (01) в вершине такого типа не существенна, так как при замене соответствующими константами переменных Зс и х, функции /„и fv не изменяются.

Пусть вершина v соединяется су'-м корнем SBDD-графа.

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

В упомянутой в третьей главе работе для схем, полученных покрытием системы ROBDD-графов программируемыми логическими блоками, и константной неисправности на входном полюсе некоторого ПЛБ, совпадающем с входным полюсом х, схемы, установлен следующий факт. Для нахождения тестового набора, обнаруживающего 10(01 ^неисправность, достаточно ограничиться рассмотрением 10(01)-неисправности только одной из вершин v SBDD-графа, покрытой рассматриваемым ПЛБ и помеченной символом i, и одной простой цепью, заходящей в эту вершину из j-го корня SBDD-графа.

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

Рассмотрим кратную неисправность V^ составленную из произвольного множества vb ..., v* базовых неисправностей ¿VJDD-графа. Составляющие неисправности множества представляются 0(1)- и 01(10)-неисправностями SfiDD-графа.

Некоторые из базовых 01(10)-неиеправностей могут быть несущественными. Неисправности и представляющие их вершины в дальнейшем будем отождествлять, используя термин «неисправная вершина», если это удобно.

Определение 13. Пара базовых неисправностей связана отношением подчинения, если представляющие эти неисправности вершины лежат на одной и той же простой цепи, соединяющей некоторый корень 5ЖШ-графа с его ](0)-концевой вершиной.

Определение 14. Базовая неисправность, представленная ближайшей к корню вершиной, называется подчиняющей; неисправность, представленная более удаленной вершиной, - подчиненной.

Определение 15. Базовую подчиняющую неисправность V, будем называть доминирующей по отношению к подчиненной базовой неисправности \'р если в присутствии неисправности V, ¿ЖЮ-граф представляет ту же систему булевых функций, что и в присутствии кратной неисправности (V/, V,).

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

Рассмотрим базовую 0(1 ^неисправность V, из \\р. Ее проявление в БВОО-графе приводит к совмещению вершины V, с 0(1) -концевой вершиной графа.

Пусть К, множество подчиненных V, одиночных неисправностей из Укр, не содержащее V/. Вершина V, является корневой для подграфа, в пределах которого находятся неисправности из К/.

Теорема 1. Базовая 0(1)-неисправность V, является доминирующей по отношению к любой базовой неисправности из К/.

Следствие. Базовая 0(1 ^неисправность V, является доминирующей по отношению к кратной неисправности V,.

Рассмотрим базовую 01(10)-неисправность V,. Её присутствие в БВОО-графе приводит к отсоединению от V, (путем обрыва 0-дуги) подграфа, корнем которого является вершина, в которую эта дуга заходит, и совмещению вершины V/ с вершиной, в которую заходит 1-дуга вершины V,.

Обозначим через V'.1' множество неисправностей из К/, лежащих в отсоединяемом подграфе. Будем говорить, что подграф подчинен 0-дуге.

Обозначим через V' множество неисправностей из V,, подчиненных 1-дуге вершины V,. Неисправности множества К1 лежат в подграфе, корнем которого является вершина, в которую заходит 1-дуга. Множества К1, могут пересекаться при наличии общих вершин в соответствующих им подграфах. Заметим, что если V' пусто, то базовые неисправности из К" не подчинены 1-дуге.

Теорема 2. Базовая 01(10)-неисправность V, является доминирующей по отношению к множеству неисправностей И", если V' пусто.

Теорема 3. Кратная неисправность (v. К1) является доминирующей по отношению к кратной неисправности (v, V] , V°).

Из теорем 2, 3 следует, что неисправности множества можно исключить из рассмотрения при анализе влияния подчиненных неисправностей на 01(10)-неисправность v(. Отметим, что это справедливо и в случае если 01(10)-неисправность вершины v, не существенна.

Определение 16. Будем говорить, что неисправность v, разрушает тестовый набор а для существенной неисправности v„ если тестовый набор для v, перестает быть таковым, когда к v, добавляется неисправность v7.

Теорема 4. Подчиненная существенная 0(1)-неисправность или 01(10)-неисправность нетерминальной вершины v, из У/ может быть обнаружима в присутствии несущественной подчиняющей 01(10)-неисправности v,.

Теорема 5. Подчиненная 0(1)-неисправность нетерминальной вершины v, из V' может разрушить тестовый набор а для существенной подчиняющей 01(10)-неисправности v,.

Теорема 6. Существенная, подчиненная 01(10)-неисправность v, из V' может разрушить тестовый набор для существенной подчиняющей 01(10)-неисправности v,.

Теорема 7. Тестовый набор а, построенный для подчиненной 0(1)- или существенной 01(10)-неисправности v„ может быть разрушен другой подчиняющей неисправностью v, из VKp, если представляющая последнюю неисправность вершина принадлежит простой цепи s, соединяющей v, с j-м корнем SBDD-графа, и эта простая цепь используется для получения тестового набора а.

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

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

Для построения проверяющего теста для кратных константных неисправностей нужно рассмотреть все сопоставляемые одиночным константным неисправностям на полюсах ПЛБ базовые неисправности SBDD-графа и

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

1. Найти все простые цепи, соединяющие выбранную неисправную вершину v, с j - м корнем SBDD-графа, причем, в случае, если рассматривается 0(1)-неисправность, сопоставляется входному полюсу ПЛБ, то эти простые цепи одновременно проходят через полюс 5Ж>£>-графа, соответствующий выходу неисправного ПЛБ.

2. Найти множество конъюнкций Kh представляемое этими цепями (из построения 5Ж>£)-графа следует, что конъюнкции множества попарно ортогональны).

3. Выполнить шаги 1, 2 для всех корней SBDD-rpафа. Найти минимальное по мощности множество Kh Полученное множество обозначаем К*. Пусть q - его мощность.

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

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

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

пример r 0 I V число входов ПЛБ: 4 число входов ПЛБ: 8

и Т. L п т Тя

BBARA 4 1 4 74 40 57 70 6 31 54

CSE 7 7 4 235 140 194 243 23 81 233

DK14 3 5 3 76 44 47 58 8 28 43

DK15 3 5 2 48 19 21 23 7 18 23

DK27 1 2 3 21 5 И 15 5 11 15

ЕХ2 2 2 5 119 59 87 107 7 30 66

KIRKMAN 12 6 4 416 253 732 4122 124 974 1960

PMA 8 8 5 340 254 407 668 33 123 491

SlA В 6 5 1012 867 1546 3432 104 486 2391

S386 7 7 4 252 150 208 348 25 97 331

SAND 11 9 5 2648 2434 3389 16877 365 1479 13428

SSE 7 7 4 189 124 184 271 15 52 222

STYR 9 10 5 689 517 638 1138 75 255 987

В таблице 1 использовались следующие обозначения: i, о, I, v - числа входов, выходов, линий обратной связи и вершин SBDD-графа; п - число ПЛБ; 7], Г - число тестовых наборов в проверяющем тесте, обнаруживающим одиночные и кратные константные неисправности на полюсах ПЛБ схемы соответственно. Анализ экспериментальных результатов показал, что число тестовых наборов в проверяющем тесте, обнаруживающем кратные константные неисправности на полюсах ПЛБ схемы, превышает число тестовых наборов в проверяющем тесте, обнаруживающем одиночные константные неисправности, в среднем в 2.5 раза, и не более чем в 9 раз.

Четвертая глава посвящена тестированию неисправностей задержек путей в схемах, построенных путём покрытия 5Ж>£>-графа программируемыми логическими блоками, сохраняющими систему ОДНФ, представляемую SßDD-графом. Предлагается алгоритм построения пар тестовых наборов для обнаружения неисправностей задержек путей схемы. Устанавливается, что для каждого пути в схеме существует пара тестовых наборов, на которой неисправность задержки пути проявляется как робастная. В отличие от результатов, полученных в работе: R. Drechsler, J. Shi, G. Fey "Synthesis of Fully Testable Circuits From BDDs", IEEE Trans, on CAD, vol. 23, No. 3, pp. 440-443 в комбинационную схему не требуется вводить дополнительный вход для обеспечения аналогичных свойств пар тестовых наборов неисправностей задержек путей. Введение дополнительных входов, как правило, не приемлемо на практике. Исследуются свойства построенного теста. Показывается, что тест, обнаруживающий все одиночные робастные неисправности задержек путей в схеме, является так же проверяющим тестом для одиночных константных неисправностей на полюсах логических элементов схемы.

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

i__Пусть комбинационная

_J схема получена покрытием SßOD-графа схемы про-J граммируемыми логически-

4 I ми блоками, причем SBDD-

Рисунок 1 - ROBDD-Граф схемы С

4 5 3 2 Рисунок 2 -схема С

граф построен объединением ЯОВОО-графов. На рис. 1 изображен ЛОВДО-граф, а на рис. 2 соответствующая ему схема. Припишем программируемым логическим блокам комбинационной схемы номера в порядке воз-

растания от входов к выходам схемы.

Путь а представляется последовательностью программируемых логических блоков (ПЛБ), проходимых на этом пути: рп,...,р,г. Пусть х, - переменная, сопоставляемая входу схемы на рассматриваемом пути, выход элемента р1Г является выходом / схемы, сопоставляемым этому пути.

Замечание 1. Поскольку рассматриваются ПЛБ, создаваемые на базе £ОТ-технологий, то естественно предполагать, что время прохождения сигнала по любому из путей графа, покрытого одним и тем же ПЛБ, одинаково и определяется параметрами конкретного ПЛБ. Это значит, что при рассмотрении некоторого пути схемы не имеет значения, какой путь выбран в подграфе конкретного ПЛБ, проходимого на этом пути.

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

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

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

Пусть путь а начинается с входной переменной х4 и проходит через ПЛБЬ ПЛБ3, ПЛБ5, выход ПЛБ5 является выходом подсхемы. Этот путь на рис. 2 выделен жирной линией.

В примере для пути а получаем из усеченных ОДНФ после первой подстановки выражение: Зс^с,. Заменив п'1 усеченной ОДНФ, далее имеем выражение: 3с,3с2дг4.т5 ух,х2х,х5 . Оно представляет множество Ка.

Теорема 9. Каждой конъюнкции из Ка соответствует путь в РХЛЮО-графе схемы от корня, сопоставляемого выходу I схемы, до 1-концевой вершины графа.

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

Другой набор v2 тестовой пары должен обратить в единицу К и в ноль все конъюнкции из F,.

Построим минимально покрывающий интервал для наборов v,, v2, обозначим его символом и. Пусть к„- конъюнкция, его представляющая.

В диссертационной работе показывается, что в Ка найдется конъюнкция К, такая, что для конъюнкций К, К_ существует пара наборов vb v2, причем k„ ортогональна всем конъюнкциям ОДНФ F„ кроме К. Алгоритм построения одного из тестовых наборов пары совпадает с алгоритмом построения тестового набора для 01(10)-неисправности вершины v. Второй набор тестовой пары находится из полученного набора заменой /-ой компоненты инверсным значением. Здесь /' - индекс переменной х„ сопоставляемой вершине v.

Показывается, что пара тестовых наборов обнаруживает инверсные перепады значений сигналов пути а при изменении порядка их поступления на тестируемую схему. Это дает возможность для одного пути использовать вместо 4-х наборов, как это обычно делается, три набора vb v2, Vi или v2, vb v2 и тем самым на 'Л часть сократить длину проверяющего теста для неисправностей задержек путей комбинационной схемы.

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

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

Теорема 11. Проверяющий тест Т, обнаруживающий все одиночные ро-бастные неисправности задержек путей, обнаруживает все кратные неисправности задержек путей.

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

Для контрольных примеров (bench-marks) из набора LGSynth'91, строились SBDD-графы путем объединения ROBDD-графов, далее строились соответствующие графы схемы, которые покрывались ПЛБ с числом входов равным 2. В построенной схеме подсчитывались числа путей и числа элементов схемы.

Столбцы MUX и LUT таблицы содержат информацию о схемах, полученных покрытием соответствующих 5йО£>-графов мультиплексорами, и о схемах, построенных покрытием соответствующих 52Ш£)-графов ПЛБ с тремя входами. NoN - число мультиплексоров, Cld - число ПЛБ, NoP - число путей в схеме, которые должны быть протестированы, PDFC - процент путей, для которых возможно построить тестовую пару.

Анализ экспериментальных результатов показывает, что числа ПЛБ и числа путей в схемах, построенных покрытием SAD-D-графов ПЛБ, как правило, меньше чисел мультиплексоров и чисел путей в схемах, построенных покрытием ¿7Ю/>графов мультиплексорами.

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

Пара тестовых наборов vb v2, обнаруживающая робастную неисправность задержки пути в схемах, построенных покрытием 55£)0-графов ПЛБ, может быть использована для тестирования обоих перепадов значений сигналов пути. Это значит, что для тестирования неисправностей задержек обоих перепадов значений сигналов пути достаточно тройки v,, v2, vi, тестовых наборов вместо обычно используемых четырех наборов. Это позволяет сократить длину проверяющего теста схемы.

Заключение

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

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

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

Исследованы контролепригодные свойства схем, построенных покрытием ЖОО-графов, полученных объединением ROBDD или Free ВДО-графов программируемыми логическими блоками (ПЛБ).

Разработан алгоритм построения тестового набора для кратной константной неисправности на полюсах ПЛБ комбинационной схемы.

Построение проверяющего теста для кратных константных неисправностей на полюсах ПЛБ комбинационной схемы сведено к расширению прове-

Таблица 2_ _

пример i 0 MUX LUT

NoN NoP PDFC clb NoP PDFC

5хр1 7 10 90 273 89.0 69 175 100

С17 5 2 12 22 68.1 6 12 100

alu2 10 6 259 873 86.9 246 929 100

Ь9 41 21 237 1773 64.6 141 380 100

clip 9 5 256 954 79.4 235 597 100

conl 7 2 20 47 74.4 9 18 100

count 35 16 251 2248 66.1 199 642 100

il 25 13 60 137 74.4 41 85 100

i5 133 66 313 44198 61.3 169 941 100

1481 16 1 34 4518 86.1 26 1226 100

tcon 17 16 34 40 100.0 16 32 100

9sym 9 1 35 328 72.5 27 195 100

film 8 8 72 326 99.3 58 139 100

z4ml 7 4 66 175 77.1 50 118 100

x2 10 7 75 188 72.3 61 251 100

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

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

Для схем, построенных покрытием 55/)£>-графов, полученных объединением ROBDD или Free ADD-графов, программируемыми логическими блоками, предложен алгоритм построения проверяющего теста, обнаруживающего неисправности задержек путей.

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

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

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

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

- Алгоритм построения проверяющего теста, гарантированно обнаруживающий всевозможные неисправности задержек путей в схеме, построенной покрытием 5В£)£>-графа программируемыми логическими блоками.

СПИСОК ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Николаева Е. А. Синтез проверяющих тестов для неисправностей задержек путей схем, построенных по системе ROBDD-графов / Е. А. Николаева, А. Ю. Матросова // Известия Томского политехнического университета. -2009. - Т. 315, № 5. - С. 153 -159.

2. Николаева Е. А. Некоторые оценки метода минимизации систем ДНФ путем выделения ядер и соядер / Е. А. Николаева, Ю. В. Седов // Доклады VI Сибирской научной школы-семинара с международным участием «Компьютерная безопасность и криптография» - SIBECRYPT'07 (Республика Алтай, Горно-Алтайск, ГАГУ, 4-7 сентября 2007 г.). Томск, 2007. С. 256-264. (Вестник Томского государственного университета. Приложение; № 23, Август

2007) (Серия «Математика. Кибернетика. Информатика»), - 2007. - С. 256264.

3. Matrosova A. Test Generation for Single and Multiple Stuck-at Faults of a Combinational Circuit Designed by Covering Shared ROBDD with CLBs / A. Matrosova, E. Lukovnikova, S. Ostanin, A. Zinchyk, E. Nikolaeva // Proc. The 22nd IEEE International Symposium on Defect and Fault-Tolerance in VLSI Systems (DTF 2007). Rome, Italy, 26-28 September, 2007. - [S. 1.], 2007. - P. 356-364.

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

5. Matrosova A. Multiple Stuck-at Fault and Path Delay Fault Testable Design of Combinational Circuits / A. Matrosova. A. Melnikov, E. Nikolaeva // Proc. IEEE East-West Design & Test Symposium (EWDTS'08). Lviv, Ukraine, 9-12 October, 2008. - [S. 1.], 2008. - P. 350-355.

6. Matrosova A. Multiple stuck-at fault and path delay fault testable circuit / A. Matrosova, V. Andreeva, A. Melnikov, E. Nikolaeva // Proc. IEEE East-West Design & Test Symposium (EWDTS'08). Lviv, Ukraine, 9-12 October, 2008. - [S. 1.], 2008.-P. 356-364.

7. Николаева E. А. Построение проверяющих тестов для одиночных и кратных константных неисправностей на полюсах элементов схем, синтезированных на базе ПЛИС(/*УС/1)-технологий по системе Free BOD-графов/ Е. А. Николаева // Вестник ТГУ. Управление, вычислительная техника и информатика. - 2009. -№ 1 (6). - С. 81-98.

8. Matrosova A. Path Delay Fault Classification Based on ENF Analysis / A. Matrosova, E. Nikolaeva // Proc. IEEE East-West Design & Test Symposium (EWDTS'09). Moscow, Russia, 18-21 Septembe, 2009. - [S. 1.], 2009 - P. 526531.

9. Nikolaeva E. PDFs Testing of Combinational Circuits Based on Covering ROBDDs / A. Matrosova, E. Nikolaeva // Proc. IEEE East-West Design & Test Symposium (EWDTS'10). St. Petersburg, Russia, 17-29 Septembe, 2010. - [S. 1.], 2010-P. 160-163.

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

Введение

1 Основные понятия

1.1 Конечные автоматы

1.2 Программируемые логические блоки

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

1.4 Методы диагностирования

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

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

1.5 Контролепригодное проектирование

1.6 Выводы

2 Методы синтеза комбинационных схем, сохраняющие системы ДНФ-задание на синтез

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

2.1.1 Многоуровневый факторизационный метод синтеза

2.1.2 Модифицированный факторзационный двухуровневый метод синтеза

2.2 Синтез схем по системе ЖЮ-графов

2.2.1 ££>£>-графы

2.2.2 Построение покрытия графа программируемыми логическими блоками (ПЛБ)

2.3 Экспериментальные результаты 67 2.3.1 Форматы представления входных и выходных данных

2.4 Выводы

3 Построение проверяющих тестов для кратных константных неисправностей на полюсах логических элементов комбинационных схем, построенных покрытием ЯО£>-графов программируемыми логическими блоками

3.1 Базовые неисправности графа

3.2 Свойства тестовых наборов базовых неисправностей БВОО-графа

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

3.4 Построение тестового набора для кратной неисправности бЖЮ-графа

3.5 Построение проверяющего теста для кратных константных неисправностей на полюсах логических элементов схемы

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

3.7 Выводы

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

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

4.1.1 Выделение множества конъюнкций, содержащих переменную, сопоставляемую началу пути в схеме

4.1.2 Построение пары тестовых наборов

4.2 Свойство проверяющего теста, обнаруживающего неисправности задержек путей

4.3 Построения пар тестовых наборов для схем, полученных покрытием систем Free 5/)£)-графов

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

4.5 Выводы

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

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

Цель работы. Целью диссертационной работы является исследование контролепригодных свойств схем, сохраняющих системы ДНФ. Для ее реализации были рассмотрены существующие методы синтеза схем, сохраняющие задание на синтез и использующие в качестве задания либо системы ДНФ, либо системы BDD {Binary Decision Diagram) - гр аф о в. Для методов синтеза по системе ДНФ были предложены эвристики, ориентированные на сокращение аппаратурных затрат, а для методов синтеза по системе .RDD-графов сформулированы требования к покрытию графов программируемыми логическими блоками (ПЛБ), обеспечивающие сохранение систем ОДНФ. Для схем, полученных покрытием систем BDD-графов программируемыми логическими блоками, разработаны алгоритмы построения проверяющих тестов для кратных константных неисправностей на полюсах логических элементов схем и неисправностей задержек путей этих схем.

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

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

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

Для схем, полученных покрытием системы ЖЮ-графов программируемыми логическими блоками (ПЛБ) и сохраняющих системы ОДНФ, предложен алгоритм построения проверяющего теста для кратных константных неисправностей на полюсах ПЛБ, не требующий перечисления всевозможных кратных неисправностей и получающийся расширением проверяющего теста для одиночных неисправностей.

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

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

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

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

Участник молодежного научно-инновационного конкурса 2008» («УМНИК») по направлению «Информационные технологии».

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

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

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

1. The 22th IEEE international Symposium on Defect and Fault-Tolerance in VLSI System (Rome, Italy, 2007).

2. The 7th East-West Design & Test international Symposium (Lviv, Ukraine, 2008).

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

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

5. The 8th East-West Design & Test international Symposium (Moscow, Russia, 2009).

6. The 9th East-West Design & Test international Symposium (St. Petersburg, Russia, 2010).

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

В журналах перечня ВАК (редакция от 19 февраля 2010):

1. Николаева Е. А. Синтез проверяющих тестов для неисправностей задержек путей схем, построенных по системе ROBDD-графов / Е. А. Николаева, А. Ю. Матросова // Известия Томского политехнического университета.-2009.-Т. 315, № 5.-С. 153- 159.

В других изданиях:

1. Николаева Е. А. Некоторые оценки метода минимизации систем ДНФ путем выделения ядер и соядер / Е. А. Николаева, Ю. В. Седов // Доклады VI Сибирской научной школы-семинара с международным участием «Компьютерная безопасность и криптография» — SIBECRYPT'07

Республика Алтай, Горно-Алтайск, ГАГУ, 4—7 сентября 2007 г.). Томск, 2007. С. 256-264. (Вестник Томского государственного университета. Приложение; № 23, Август 2007) (Серия «Математика. Кибернетика. Информатика»). - 2007. - С. 256-264.

2. Matrosova A. Test Generation for Single and Multiple Stuck-at Faults of a Combinational Circuit Designed by Covering Shared ROBDD with CLBs / A. Matrosova, E. Lukovnikova, S. Ostanin, A. Zinchyk, E. Nikolaeva // Proc. The 22nd IEEE International Symposium on Defect and Fault-Tolerance in VLSI Systems (DTF 2007). Rome, Italy, 26-28 September, 2007. - [S. 1.], 2007. - P. 356-364.

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

4. Matrosova A. Multiple Stuck-at Fault and Path Delay Fault Testable ! Design of Combinational Circuits / A. Matrosova, A. Melnikov, E. Nikolaeva // Proc. IEEE East-West Design & Test Symposium (EWDTS'08). Lviv, Ukraine, 9-12 October, 2008. - [S. 1.], 2008. - P. 350-355.

5. Matrosova A. Multiple stuck-at fault and path delay fault testable circuit / A. Matrosova, V. Andreeva, A. Melnikov, E. Nikolaeva // Proc. IEEE East-West Design & Test Symposium (EWDTS'08). Lviv, Ukraine, 9-12 October, 2008. -[S. 1.], 2008.-P. 356-364.

6. Николаева E. А. Построение проверяющих тестов для одиночных и кратных константных неисправностей на полюсах элементов схем, синтезированных на базе ПЛИС(РРОА)-технологий по системе Free BDD-графов/ Е. А. Николаева // Вестник ТГУ. Управление, вычислительная техника и информатика. - 2009. - №1(6).- С. 81-98.

7. Matrosova A. Path Delay Fault Classification Based on ENF Analysis / A. Matrosova, E. Nikolaeva // Proc. IEEE East-West Design & Test Symposium

EWDTS'09). Moscow, Russia, 18-21 Septembe, 2009. - [S. I.], 2009 - P. 526531.

8. Nikolaeva E. PDFs Testing of Combinational Circuits Based on Covering ROBDDs / A. Matrosova, E. Nikolaeva // Proc. IEEE East-West Design & Test Symposium (EWDTS'10). St. Petersburg, Russia, 17-29 Septembe, 2010. - [S. 1.], 2010-P. 160-163.

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

Диссертация состоит из введения, 4-х глав, заключения и списка используемой литературы. Объем диссертации составляет 134 страницы текста, набранного в редакторе MS Word 2003 (шрифт - Times New Roman, размер шрифта - 14 pt, межстрочный интервал —1.5 строки), в том числе: титульный лист - 1 стр., оглавление — 2 стр., основной текст, включающий 33 рисунка и 7 таблиц, - 120 стр., библиография из 95 наименований - 10 стр, приложение - 1 стр.

4.5 Выводы

Рассмотрены схемы, полученные покрытием 5Ш)0-графа, построенного объединением ROBDD или Free BDD-графов, программируемыми логическими блоками. Предложен алгоритм построения пары vb v2 тестовых наборов для неисправности задержки пути. Показано, что пара тестовых наборов порождается тестовым набором для одной из константных неисправностей на входном полюсе ПЛБ, непосредственно соединенном со входом схемы и являющимся началом пути а. В отличие от [86] в комбинационную схему не требуется вводить дополнительный вход для тестирования неисправностей задержек. Введение дополнительных входов, как правило, не приемлемо на практике.

Установлено, что неисправность задержки каждого пути схемы проявляется как робастная. Найденная пара тестовых наборов может быть использована для тестирования обоих перепадов значений сигналов пути. Объединение троек тестовых наборов VI, у2, V] для различных путей схемы представляет проверяющий тест, обнаруживающий все неисправности задержек путей схемы.

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

Заключение

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

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

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

Исследованы контролепри годные свойства схем, построенных покрытием £5£>./>графов, полученных объединением ROBDD или Free BDD-графов программируемыми логическими блоками (ПЛБ).

Разработан алгоритм построения тестового набора для кратной константной неисправности на полюсах ПЛБ комбинационной схемы.

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

Установлено, что в комбинационных схемах, построенных покрытием систем из Free 2Ш£)-графов, не все одиночные константные неисправности являются существенными.

Для схем, построенных покрытием £#/)£>-графов, полученных объединением ROBDD или Free МЮ-графов, программируемыми логическими блоками, предложен алгоритм построения проверяющего теста, обнаруживающего неисправности задержек путей.

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

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

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

Эвристики для многоуровневого и двухуровневого факторизационных методов синтеза, ориентированные на сокращение аппаратурных затрат получаемых комбинационных схем. Модифицированный двухуровневый метод синтеза, позволяющий сохранять систему ДНФ. Если в качестве систем ДНФ используются системы безызбыточных ДНФ, то синтезируемые схемы допускают существование для них проверяющего теста для одиночных константных неисправностей, обнаруживающего и все кратные константные неисправности на полюсах логических элементов схемы. Кроме того, неисправности задержек путей в таких схемах более чем в 95% случаев проявляются как робастные.

Алгоритм построения тестового набора, обнаруживающего кратную константную неисправность на полюсах ПЛБ схемы, построенной покрытием 5ЖЮ-графа; алгоритм построения проверяющего теста для всех кратных константных неисправностей на полюсах ПЛБ схемы, не требующий явного перечисления всевозможных кратных неисправностей и получаемый путем расширением проверяющего теста для одиночных константных неисправностей.

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

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

2. Kuon I. Fpga architecture: Survey and challenges / 1. Kuon, R. Tessier, J. Rose // Foundations and Trends in Electronic Design Automation. 2007. - vol.2, № 2. - P.135-253.

3. BIST of FPGA Interconnect / Stroud С. E. et al. // Proc. IEEE International Test Conf. 1998. - P.404-411.

4. Martinez D. R. High Performance Embedded Computing Handbook / D. R. Martinez, M. Michael, R. A. Bond // CRC Press. 2008. - 600 p.

5. Бадашин Д. В. Сверхбольшие специализированные ИС в оборудовании цифровых систем передачи / Д. В. Бадашин, А. В. Савчук // Технология и конструирование в электронной аппаратуре. 1998. - № 4. - С.9-14.

6. Xilinx, "Virtex-4 User Guide, " UG070 (vl.5), Xilinx, Inc., 2006. www. xilinx. com/bvdocs/userguides/ug070. pdf.

7. Xilinx, "Virtex-4 Configuration Guide, " UG071 (vl.5), Xilinx, Inc., 2007. www. xilinx. com/bvdocs/userguides/ug071. pdf.

8. Cosoroaba A. Achieving Higher System Performance with the,Virtex-5 Family of FPGAs / A. Cosoroaba, F. Rivoallon // XILINK WP245 . 2006.

9. ACTTM Family FPGA Data Book // Actel Corporation. — Sunny vale, California. — 1992.

10. FPGA Data Book and Design Guide / Ibid. — 1993.

11. XILIX. The Programmable Logic Data Book // San Jose, California. 2000.

12. Component Selector Guide // Altera Corporation. San Jose, California. -1995.

13. Smith G. L. Model for Delay Faults Based upon Paths / G. L. Smith // Proc. Int'l Test Conf. 1985. - P.342-349.

14. Krstic A. Delay Fault Testing for VLSI Circuits (Frontiers in Electronic Testing) / A. Krstic, К. -T. Cheng // Springer, 1998. 208 p.

15. Devadas S. Synthesis of Robust Delay-Fault-Testable Circuits: Theoiy / S. Devadas, K. Keitzer // IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. 1992.-vol.11, № 1. — P.87—101

16. Cheng К. -T. Classification and identification of nonrobust untestable path delay faults / . Cheng, К. -T. ;Chen, H. -C. // Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on. 1996. - vol 15., № 8. - P.845-853.

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

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

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

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

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

22. Re inert D. Entwurf und Diagnose komplexer digitaler Systeme / D. Reinert. -Berlin: VEB Verlag Technik, 1983. 270 p.

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

24. Betrand J. C. Totally Self-Checking Sequential Circuits / J. C. Betrand, N. Gambiasi, J. J. Mercier // Proc. Int. Sympos. «Discrete Systems». 1974. - P.36-44.

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

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

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

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

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

30. Kiefer G. Using BIST Control for Pattern Generation / G. Kiefer, H. Wunderlich // Proc. IEEE International Test Conf. 1997. - P.347-355.

31. Damarla T. Multiple Error Detection and Identification via Signature Analysis / T. Damarla, C. Stroud, A. Sathaye // Jour, of Electronic Testing: Theory and Applications. 1995. - vol.6, №.6. - P. 193-207.

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

33. McLeod G. BIST Techniques for ASIC Design / McLeod G // Proc. IEEE International Test Conference. 1992. - P.496-505.

34. McCluskey E. Built-in Self-Test Techniques / E. McCluskey // IEEE Design & Test of Computers. -1985. vol.2, №.2. - P.21-28.

35. Agrawal V. A Tutorial on Built-in Self-Test: Principles / V. Agrawal, C. Kime, К Saluja // IEEE Design & Test of Computers. 1993. - vol.10, №1. - P.73-82.

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

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

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

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

40. Lin C. Integration of Partial Scan with Built-in Self-Test / C. Lin, Y. Zorian, S. Bhawmik // Jour. Electronic Testing: Theory and Applications. 1995. - vol.7, № 2. —P.125-137.

41. Ubar R. Test Generation for Digital Circuits Using Alternative Graphs / R. Ubar // Proc. of Tallinn Technical University. 1976. - № 409. - P.75-81.

42. Roth G. P. Programmed Algorithm to Compute Tests to Detect and Distinguish Between Failures in Logic Circuits / G. P. Roth, W. G. Boricios, P. R. Shneider // Electronic Computers, IEEE Transactions on. 1967. — vol.16. - P.567-580.

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

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

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

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

47. Rahaman H. A Simple Delay Testable Synthesis of Symmetric Functions /

48. H. Rahaman, D. K. Das. // Lecture Notes in Computer Science. 2004. - vol.3285. -P.263-270

49. Chakrabarty K. Balance testing and balance-testable design of logic circuits / K. Chakrabarty, J. P. Hayes. // Journal of Electronic Testing: Theory and Applications. 1996. - vol.8, № 1.-P.71-86.

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

51. Pomeranz I. Design-for-Testability for Path Delay Faults in Large Combinational Circuits Using Test Points / I. Pomeranz, S. M. Reddy// Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on. 1998. -vol.17, № 4.-P.332-343.

52. Pomeranz I. On Synthesis-for-Testability of Combinational Logic Circuits /

53. Pomeranz, S. M. Reddy // Proc. DAC '95, 32nd Conference. 1995. - P.126—132.

54. Chakraborty Т. J. Design for Testability for Path Delay Faults in Sequential Circuits / T. J. Chakraborty, V. D. Agrawal, M. L. Bushnell // Proc. The 30th Design Automation Conference. 1993. - P .453^157.

55. Uppaluri P. On minimizing the number of test points needed to achieve complete robust path delay fault testability / P. Uppaluri; U. Sparmann; I. Pomeranz // Proc. The 14th VLSI Test Symposium. 1996. - P.288-295.

56. Krstic A. Resynthesis of comdinational circuits for path count reduction path delay fault testability / A. Krstic, K. -T. Cheng // Journal of Electronic Testing: Theory and Applicatoins. 1997. - vol 11, № 1. - P.43-54.

57. Iyengar V. S. Optimized test application timing for AC test. / V. S. Iyengar, G. Vijayan // Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on. 1992. - vol 11, №11. - P. 1439-1449.

58. Mao W. W. A variable observation time method for testing delay faults/ W. W. Mao, M. D. Ciletti // Proc. The 27th АСМЛЕЕЕ Design Automation Conference. -1991. P.728-731.

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

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

61. Kohavi I. Detection of Multiple Faults in Combinational Logic Networks / I. Kohavi, Z. Kohavi // IEEE Transactions on Computers. 1972. - vol 21, № 6. -P.556-568.

62. Е. А. Николаева Синтез проверяющих тестов для неисправностей задержек путей схем, построенных по системе ROBDD графов / Е. А.

63. Николаева, А. Ю. Матросова // Известия Томского политехнического университета. -2009. Т.315, № 5. - С.153 - 159.

64. Матросова А. Ю. Синтез самопроверяемых дискретных устройств по BDD-реализациям их функционирования / М. В. Астафьев, А. Ю. Матросова // Вестник томского государственного университета. 2000. - № 271. — С.89-92.

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

66. Matrosova A. Multiple Stuck-at Fault and Path Delay Fault Testable Design of Combinational Circuits / A. Matrosova, A. Melnikov, E. Nikolaeva // Proc. 23nd IEEE International Symposium on Defect and Fault Tolerance in VLSI Systems. -2008.-P. 350-355.

67. Matrosova A. Path Delay Fault Classification Based on ENF Analysis / A. Matrosova, E. Nikolaeva // Proc. EWDTS'09. 2009. - P. 526-531.

68. Matrosova A. PDFs Testing of Combinational Circuits Based on Covering ROBDDs / A. Matrosova, E. Nikolaeva // Proc. EWDTS'10. 2010. - P. 160-163.

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

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

71. Матросова А. Ю. Построение проверяющих тестов для константных неисправностей и неисправностей задержек путей в схемах, синтезированных факторизационным методом / В. В. Андреева, А. Ю. Матросова, А. В.

72. Мельников, А. В. Морозова // Прикладная и Дискретная Математика. 2009. -приложение № 1. - С.65-66.

73. Matrosova A. Multiple Stuck-at Fault and Path Delay Fault Testable Circuits / A. Matrosova, A. Andreeva, A. Melnikov, E. Nikolaeva. // Proc. TWDTS'08. -2008. — P.356—364.

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

75. Baranov S. Logic synthesis for control automata / S. Baranov // Dordrecht; Boston; London: Kluwer academic publishers, 1994. 412 p.

76. Brayton K. MIS: A multi-level logic optimization program / K. Bray ton, R. Rudell, A. Sangiovanni-Vincentelli, A. R. Wong // Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on. 1987. - vol.7. - P. 10621081.

77. Bhattacharya D. Test generation for path delay faults using binary decision diagrams / D. Bhattacharya, P. Agrawal, V. D. Agrawal // Computers, IEEE Transactions on. 1995. - vol.44, № 3. - P.434^147.

78. Drechsler R. Synthesis of Fully Testable Circuits From BDDs / R. Drechsler, J. Shi , G. Fey // Computer-Aided Design of Integrated Circuits and Systems, IEEE transactions on. 2004. - vol.23, № 3. - P.440-443.

79. Ashar P. Gate-delay-fault Testability properties of Multiplexor-based Networks / P. Ashar, S. Devadas, K. Keutzer // Proc. IEEE International Test Conf. on Test: Faster, Better, Sooner. 1991. - P.887-896.

80. Ashar P. Testability Properties of Multilevel Logic Networks Derived from Binary Decision Diagrams / P. Ashar, S. Devadas, K. Keutzer // Proc. Advanced Research in VLSI. 1991. - P.33 - 54.

81. Ashar P. Path-delay-fault Testability Properties of Multiplexor-based Networks / P. Ashar, S. Devadas, K. Keutzer // INTEGRATION, the VLSI Jour. -1993.-vol.15, № 1. P.1-23.

82. Becker B. Synthesis for Testbility: Binary Decision Diagrams / B. Becker // Lecture Notes in Computer Science. 1992. - vol.577. - P.501-512.

83. Shi J. BDD Based Synthesis of Symmetric Functions with Full Path-Delay Fault Testability / J. Shi, G. Fey, R. Drechsler //Proc. The 12th Asian Test Symposium (ATS'03). 2003. - P.290-293.

84. Murgai R. Logic Synthesis for Field Programmable Gate Arrays / R. Murga, R. Brayton, A. Sangiovanni-Vincentelli // Kluver Academic Publishers, 1995. — 425 P

85. Akers S. B. Binary Decision Diagram / S. B. Akers // IEEE Trans, on Computers. 1978. - vol.27, № 6. - P.509-516.

86. Bryant R. E. Graph-Based Algorithms for Boolean Function Manipulation / R. E. Bryant // IEEE Trans, on Computers. 1986. - vol.35, № 8. - P.677-691.

87. Minato S. Shared binary decision diagram with attributed edges for efficient Boolean function manipulation / S. Minato, N. Ishiura, S. Yajima // Proc. The 27th ACM/IEEE Design Automation Conference. 1991. - P.52-57.

88. Murgai R. Logic Synthesis for Field-Programmable Gate Arrays / R. Murgai, R. K. Brayton, A. L. Sangiovanni-Vincentelli // Springer, 1995. 452 p.

89. Yang S. Logic Synthesis and Optimization Benchmarks User Guide: Version 3. 0. / S. Yang// North Carolina: Microelectronics Center of North Carolina, 1991. -43 p.

90. Brglez F. Combination profiles of sequential benchmarks circuits / F. Brglez, D. Bryan, K. Kozmincki // Proc. Int. Symp. Circuits and Systems. 1989. - P. 19291934.

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

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

93. Bushnell М. L. Essentials of Electronic Testing for Digital, Memory, And Mixed-Signal VLSI Circuits / M. L. Bushnell, V. D. Agrawal // Hingham, MA, USA: Kluwer Academic Publishers, 2000. 432 p.

94. Matrosova A. Path Delay Faults and ENF / A. Matrosova, V. Lipsky, A. Melnikov, V. Singh// Proc. EWDTS'10. 2010. - P. 164-167.