Автоматика и телемеханика, № 11, 2021

Оптимизация, системный анализ

и исследование операций

С.В. ЧЕРНЫШОВ, (svchernyshov@mail.ru),

О.Х. КИМ, (oh.kim@yandex.ru),

Е.А. НИКОЛАЕВА, канд. техн. наук (nikolaeve-ea@yandex.ru)

(Национальный исследовательский Томский государственный университет)

ПОСТРОЕНИЕ ПОСЛЕДОВАТЕЛЬНОСТИ, ОБНАРУЖИВАЮЩЕЙ

РОБАСТНО ТЕСТИРУЕМЫЕ НЕИСПРАВНОСТИ ЗАДЕРЖЕК ПУТЕЙ

В СХЕМАХ С ПАМЯТЬЮ

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

входных переменных, доставляющей тестовые пары (v₁, v₂) соседних век-

торов в пространстве входных и внутренних переменных для робастно те-

стируемых неисправностей задержек путей (робастных Path Delay Faults

(PDFs)) в логических схемах с памятью. Целью данной работы являет-

ся выяснение возможности построения тестовой последовательности для

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

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

на длину последовательности для отдельного пути. Проведенные экспе-

рименты показывают, что тестовые последовательности удается постро-

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

тестовые пары в комбинационной составляющей схемы с памятью.

Ключевые слова: логическая схема с памятью, установочная последо-

вательность, Reduced Ordered Binary Decision Diagram (ROBDD), ро-

бастно тестируемая неисправность задержки пути (PDF), rising (falling)

transition.

DOI: 10.31857/S0005231021110106

1. Введение

Одним из основных параметров логических схем высокой производитель-

ности является высокая тактовая частота, т.е. высокая скорость функциони-

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

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

мы. Производители стремятся к увеличению тактовой частоты.

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

задержкой — критический путь. Задержка этого пути определяет скорость

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

ния и высоком уровне интеграции в схемах возникают непредусмотренные

148

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

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

и снижению ее расчетного быстродействия, что нежелательно. Модель неис-

правности задержки пути (Path Delay Fault (PDF) является одной из наи-

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

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

неисправности задержки пути предполагают, что задержки отдельных эле-

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

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

ты и искажать функционирование схемы. Выделяют робастно и не робастно

тестируемые неисправности задержек путей. Под робастно тестируемой неис-

правностью понимают неисправность задержки пути, которая обнаруживает-

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

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

не робастно тестируемой. При проявлении робастно тестируемой неисправ-

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

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

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

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

сохранения ее расчетного быстродействия или замаскировать действие обна-

руженной задержки [1] с той же целью. Для тестирования задержек путей

используются пары векторов (v₁, v₂). Векторы каждой пары могут отличать-

ся друг от друга по переменной, отмечающей начало рассматриваемого пути,

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

векторы (булевы) и наборы тестовой пары использовать как синонимы. За-

держки противоположных перепадов значений сигналов (rising transition и

falling transition) могут отличаться, поэтому необходимо для каждого пути

в общем случае иметь две тестовые пары. Под rising transition будем, как

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

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

ем нулевого сигнала на единичный. Соответственно, под falling transition —

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

на его выходе изменением единичного сигнала на нулевой сигнал. Пусть в

момент времени t c приходом синхросигнала на схему поступает вектор v₁

тестовой пары. При поступлении следующего синхросигнала на схему посту-

пает вектор v₂. Если с приходом третьего синхросигнала на выходе схемы

наблюдается сигнал, значение которого отличается от ожидаемого, то счита-

ем, что в схеме имеет место задержка в ее путях.

На практике при тестировании задержек путей используют различные ме-

тоды сканирования. При реализации этих методов в рамках Launch-on-Shift

(LOS) технологии одним из векторов пары является тестовый набор для кон-

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

ется сдвигом первого. При использовании Launch-on-Capture (LOC) техноло-

гии второй вектор получается на основе реакции комбинационной составляю-

щей схемы на первый вектор. Понятно, что при таких способах формирования

пар векторов далеко не всегда удается получать тестовые пары для робаст-

149

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

этих технологий удается обнаруживать около 20% таких неисправностей, в

то время как использование точных методов [2], гарантирующих построение

тестовой пары для робастно тестируемой неисправности, если она существу-

ет, позволяет обнаруживать от 40 до 90% и более таких неисправностей для

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

тью. Точные методы ориентированы на снижение потребляемой мощности.

Проблема снижения потребляемой мощности при тестировании задержек ис-

следуется во многих публикациях [3-7]. Другой проблемой при тестировании

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

тестов в рамках технологий сканирования. Как известно [8, 9], в технологиях

сканирования используют в линиях обратных связей специальные тригге-

ры, более сложные, чем D-триггеры. В рабочем режиме функционирования

схемы они выполняют, как D-триггеры, задержку на один такт сигнала, со-

поставляемого переменной состояния (внутренней переменной), а в режиме

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

вносится составляющая тестового вектора, соответствующая внутренним пе-

ременным. Дополнительная аппаратура требуется также для разделения ре-

жимов функционирования и тестирования схемы с памятью. Точные методы

могут быть применены в рамках Random Access Scan (RAS) технологий, реа-

лизация которых требует, к сожалению, больших аппаратурных затрат, чем

использование LOS или LOC технологий. Итак, перечисленные способы те-

стирования задержек путей связаны с существенными аппаратурными затра-

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

работе, позволяют выяснить, всегда ли это возможно.

Имеется множество тестовых пар соседних булевых векторов (всех или

некоторых), обнаруживающих робастно тестируемую неисправность задерж-

ки пути в комбинационной составляющей схемы с памятью. Требуется по-

строить входную последовательность, доставляющую одну (любую) тесто-

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

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

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

отмечено входной переменной и 2) когда начало пути отмечено переменной

состояний (внутренней переменной) схемы. Если искомые последовательно-

сти удается найти для каждого из путей заданного множества, то, совместив

их, обнаружим задержки путей без дополнительных аппаратурных затрат.

Во втором разделе обсуждаются свойства пар наборов для робастно те-

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

процедура получения Reduced Ordered Binary Decision Diagram (ROBDD-гра-

фа), представляющего множество всех тестовых пар соседних наборов для

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

приводятся алгоритмы построения последовательности, доставляющей из на-

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

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

экспериментов.

150

2. Некоторые свойства тестовых пар наборов

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

Имеем одновыходную схему C и соответствующую эквивалентную нор-

мальную форму (ЭНФ). В [10] рассматривается задача построения пар те-

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

держек путей на основе анализа ЭНФ. Наборы v₂ тестовых пар являются

тестовыми наборами для константных неисправностей литер ЭНФ.

В случае rising transition тестируется 0-константная неисправность лите-

ры ЭНФ, соответствующей пути α (a_p-неисправность). В присутствии неис-

правности все вхождения литеры заменяются в ЭНФ константой 0. Тестовый

набор, обнаруживающий эту неисправность, является набором v₂ тестовой

пары, который порождает смену сигнала на выходе схемы с нулевого на еди-

ничное значение.

В случае falling transition тестируется 1-константная неисправность лите-

ры ЭНФ, соответствующей пути α (b_p-неисправность). В присутствии неис-

правности все вхождения литеры заменяются в ЭНФ константой 1. Тестовый

набор, обнаруживающий эту неисправность, является набором v₂ тестовой

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

нулевое значение.

В [10] показано, что для тестовых пар, обнаруживающих робастно тести-

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

1) если v₂ есть a_p-тестовый набор, то v₁ есть b_p-тестовый набор тестовой

пары и наоборот;

2) на наборах тестовой пары функция, реализуемая схемой C, принимает

противоположные значения;

3) минимально покрывающий интервал u векторов v₁, v₂ ортогонален всем

конъюнкциям ЭНФ, не содержащим литеру, сопоставляемую пути α;

4) наборы (v₁, v₂) тестовой пары порождаются одной и той же непустой

конъюнкцией.

При замене набора v₁ набором v₂ схема может попасть в промежуточное

состояние, являющееся тестовым набором v₁ для другого пути схемы. В ре-

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

Такая ситуация исключается при выполнении условия 3. Для проверки усло-

вия 3 в [10] предлагается воспользоваться ЭНФ схемы. Однако ЭНФ, как

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

наборов тестовой пары (v₁, v₂) при переходе от v₁ к v₂ промежуточных состоя-

ний не возникает. Использование этого факта избавляет от необходимости

анализировать ЭНФ.

Теорема 1. Соседние наборы тестовой пары (v₁,v₂), в которой v₂ есть

a_p-тестовый набор, а v₁ — b_p-тестовый набор или наоборот, обнаруживают

робастно тестируемую неисправность задержки пути для обоих перепадов

значений сигналов этого пути (для rising transition и falling transition).

151

Теорема 2. Если существует тестовая пара наборов (b_p,a_p), не являю-

щихся соседними и обнаруживающих робастно тестируемую неисправ-

ность задержки пути α, то существует тестовая пара соседних наборов,

обнаруживающая эту задержку.

Сам факт существования тестовой пары соседних наборов для робастно те-

стируемых неисправностей при существовании тестовой пары для несоседних

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

ЭНФ при подстановке в нее одинаковых для соседних наборов констант [11].

От ЭНФ остается дизъюнкция из литер, сопоставляемых переменной, отме-

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

кой тип задержки пути тестируется предъявленной парой соседних наборов.

В теореме 2 подтверждается этот результат на основе исследования свойств

конъюнкций ЭНФ (в них никакие переменные константами не заменяются),

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

неисправностей задержек путей [10].

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

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

наборов.

Это также означает, что для установления существования тестовой пары

для робастно тестируемой неисправности задержки пути достаточно ограни-

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

ный в [12] алгоритм построения всех тестовых пар соседних наборов для обна-

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

нахождение в схеме всех робастно тестируемых путей.

Для построения множества всех тестовых пар соседних векторов для ро-

бастно тестируемых неисправностей рассматриваемого пути в [12] предлага-

ется предварительно вычислять булеву разность (булеву производную) это-

го пути. Метод вычисления булевой разности и представления ее в виде

ROBDD-графа R(D_path) основан на выполнении операций над ROBDD-гра-

фами, извлекаемыми из фрагментов комбинационной схемы, характеризую-

щихся полиномиальной сложностью.

3. Получение тестовых пар соседних наборов для робастно тестируемых

неисправностей из ROBDD R(D_path)

Всевозможные тестовые наборы v₂ для обоих перепадов значений сигна-

лов представлены в виде ROBDD R(D_path) [12]. Напомним, что в случае rising

transition v₂ является тестовым набором для a_p-неисправности литеры, отме-

чающей начало пути α. Для falling transition v₂ является тестовым набором

для b_p-неисправности литеры, отмечающей начало пути α. Приведем проце-

дуру извлечения всех тестовых пар [12] для рассматриваемого пути. Пусть

начало пути α отмечено переменной x_i без инверсии.

R_rise = R(D_path)& x_i(R(D_path)& x_i) — ROBDD-граф, представляющий все

наборы v₂ для rising transition.

152

R_fall = R(D_path)& x_i(R(D_path)& x_i) — ROBDD-граф, представляющий все

наборы v₂ для falling transition.

Для каждого типа перепадов значений сигналов пути α приведены две

формулы, поскольку литера ЭНФ, сопоставляемая рассматриваемому пути,

может иметь различные знаки инверсии.

Обозначим через R^′rise ROBDD-граф, полученный из R_rise удалением пе-

ременной x_i, а через R^′fall ROBDD-граф, полученный из R_fall удалением пе-

ременной x_i. В обоих случаях знаки переменной x_i не имеют значения.

Обозначим символом R_rob ROBDD-граф, представляющий тестовые пары

соседних по переменной x_i наборов для робастно тестируемых неисправно-

стей задержек пути α.

R_rob = R^′rise & R^′fall.

Из процедуры построения R_rob следует, что граф не содержит перемен-

ную x_i, отмечающую начало пути. Путь от корня графа R_rob до его 1-кон-

цевой вершины представляет конъюнкцию такую, что булев вектор в про-

странстве переменных x₁, . . . , xi-1, xi+1, . . . , x_n задает тестовую пару в про-

странстве n переменных для рассматриваемого пути. Один из векторов пары

получается приписыванием переменной x_i значения 0, а другой — значения 1.

Если на векторе v₂ и выходе одновыходной схемы (для многовыходной схе-

мы на выходе, сопоставляемом пути α) достигается значение 1, то v₂ — вектор

для rising transition, если значение 0, то v₂ — вектор для falling transition.

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

ROBDD-графом R_rob, сопоставляются полным состояниям, т.е. в векторах

пары выделяются входные составляющие и составляющие по переменным

состояния.

Из тестовой пары формируются тройки векторов, обнаруживающие

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

v₂-v₁-v₂, либо v₁-v₂-v₁. Это значит, что при использовании тестовых пар

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

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

онной составляющей тремя векторами вместо четырех.

Однако если переменные состояния в комбинационной составляющей не

доступны, предлагается из начального состояния q₀ последовательностной

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

перепадов рассматриваемого пути. Дело здесь в том, что необходимо не толь-

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

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

мой тройкой тестовых векторов, чем длиннее цепочка, тем ниже вероятность

попадания в нее.

4. Алгоритмы построения последовательности, обнаруживающей робастно

тестируемую неисправность задержки пути в схеме с памятью

Приведем алгоритмы построения последовательности векторов входных

переменных последовательностной схемы, доставляющей тестовую пару на

153

входы комбинационной составляющей схемы из начального состояния q₀. На-

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

менной, отмечающей начало исследуемого пути. Эти алгоритмы формируют

вместе с соответствующими тестовыми парами последовательности, обнару-

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

входной последовательности для каждой последовательности перепадов зна-

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

Пусть последовательностная схема получена из State Transition Graph

(STG) описания, в котором выполнено кодирование состояний. STG-описание

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

публикациях с прошлого века. Оно применяется в условиях, когда симво-

лы входного и выходного алфавита конечного автомата (абстрактной модели

поведения устройства с памятью) уже закодированы разработчиком устрой-

ства. В STG-описании условие перехода из одного состояния в другое (с од-

новременным формированием выходного символа) представлено в виде тро-

ичного вектора в пространстве входных переменных и переменных состояний

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

ство условий этого перехода по сравнению с таблицами переходов-выходов,

используемых в теории конечных автоматов. B табл. 1 приведен пример тако-

го описания. Здесь множество состояний представлено символами {1, 2, 3, 4}.

Сопоставив состояниям булевы векторы в пространстве переменных z₁, z₂

следующим образом: 1 —

0, 2 —

1, 3 —

0, 4 —

1, получим таблицу,

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

ных переменных и переменных состояний (табл. 2). В таблице функции пере-

ходов отмечены переменными z′1, z′2, а функции выходов переменными y₁, y₂,

и т.д.

Эта таблица есть задание на синтез устройства. Для кодирования состоя-

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

тез часто используют другие коды, например равновесные коды, коды Бер-

гера и их модификации [13, 14] и др.

Необходимо принять во внимание следующие факты:

1) если в диаграмме переходов, соответствующей STG-описанию, отсут-

ствуют петли, то невозможно построить последовательность, доставляющую

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

мы;

2) если в результате кодирования состояний в полученном множестве кодов

(в рабочей области, задаваемой STG-описанием) отсутствуют соседние векто-

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

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

ней переменной) в последовательностной схеме.

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

состояния схемы и обнаруживающих робастно тестируемые неисправности

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

ностной схемы, представлено ROBDD-графом R_rob. В ROBDD R_rob снача-

154

Таблица 1. STG-описание поведения схемы с памятью

x₁

x₂

x₃

q^′

y₁

y₂

y₃

y₄

y₅

–

Таблица 2. Описание поведения схемы с памятью после кодирования состояний

x₁

x₂

x₃

z₁

z₂

z′1

z′2

y₁

y₂

y₃

y₄

y₅

–

ла выполняется разложение Шеннона по внутренним, а затем по входным

переменным. Это следует из метода его построения [12].

Имея в виду, что тестовые пары (v₁, v₂), задаваемые R_rob, состоят из вход-

ной и внутренней составляющих, представим их как: v₁ = vin1, vs1; v₂ = vin2, vs2,

т.е. тестовую пару далее будем задавать следующим образом: (vin1, vs1; vin2, vs2).

Рассматриваются следующие ситуации:

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

переменной;

б) соседние булевы векторы, извлекаемые из R_rob, отличаются по внутрен-

ней переменной.

Случай а).

Рассмотрим тестовую пару (vin1, vs1; vin2, vs1) векторов, которую необходимо

подать на комбинационную составляющую последовательностной схемы для

обнаружения задержки заданного пути α в условиях отличия векторов тесто-

вой пары (составляющих vin1, vin2) по входной переменной x_i и при совпадении

составляющих по переменным состояния. Для простоты положим, что пере-

155

Момент t₁

Момент t₂

Момент t₃

Рис. 1.

менная, отмечающая заданный путь, не имеет инверсии. Опишем процедуру

доставки тестовой пары в соответствующие моменты времени:

1) предварительно с помощью подходящей входной последовательности,

построение которой будет описано далее, устанавливаем схему (в момент t₁)

в состояние vs1. В данном случае не важен ни входной сигнал, ни состояние,

из которого выполняется переход в состояние vs1;

2) из состояния vs1 под действием входного сигнала vin1, поступающего в

момент t₂ (именно в этот момент обеспечивается подача на входы комбина-

ционной составляющей последовательностной схемы первого вектора vin1, vs1

тестовой пары) переходим в состояние vs1, т.е. реализуем петлю в автоматной

диаграмме переходов с целью достижения состояния vs1 в момент t₃;

3) в состоянии vs1 в момент t₃ подаем на входы схемы вектор vin2, т.е.

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

комбинационной составляющей. Неважно, каким будет следующее состояние

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

сопоставляемом рассматриваемому пути.

В момент t₄ наблюдаем неисправность задержки на соответствующем пути

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

место.

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

друг за другом моменты времени. Переходы в моменты времени t₁, t₂, t₃ ил-

люстрирует рис. 1.

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

попасть в состояние vs1. Это можно сделать, построив последовательность,

устанавливающую схему из начального состояния в некоторое состояние из

множества состояний типа vs1. Причем представляют интерес не все состоя-

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

ной составляющей vin1 , содержащейся среди полных состояний, представлен-

ных R_rob. Обеспечив поступление в этом состоянии входной составляющей,

далее формируем вектор vin2, vs1, заменив в vin1 значение переменной x_i ин-

версным.

Для построения установочной последовательности из начального состоя-

ния q₀ в состояние из заданного множества воспользуемся алгоритмом, пред-

ложенным в [15]. В нем множество состояний представлено ROBDD-гра-

фом Rs0. Построение установочной последовательности из начального со-

стояния является общей частью для различных типов перепадов сигналов

156

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

этих ситуаций приходится строить свой граф Rs0 .

Итак, строим множество Rs0 для тестовой пары, в которой соседние векто-

ры отличаются по входной переменной x_i. Из STG-описания выделяем фраг-

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

ного автомата. Фрагмент состоит из строк вида:

k₁q_i → q_i

k₂q_i → q_i

k_mq_i → q_i

km+1q_j → q_j

km+sq_j → q_j

Здесь k_i — конъюнкции (троичные векторы) на множестве входных пере-

менных схемы, q_i, q_j , . . . — состояния STG-описания (состояния конечного ав-

томата), представленные булевыми векторами при кодировании. Левую часть

рассматриваемого фрагмента, т.е. конъюнкции от входных переменных вме-

сте с приписанными им состояниями представляем в виде ROBDD R_p. Этот

граф пригодится при рассмотрении всех путей из предъявленного множества,

начала которых отмечены входными переменными последовательностной схе-

мы. Перейдем к рассмотрению заданного пути α.

Последовательность шагов для falling transition пути α:

1) из R_rob формируем a_p-тестовые наборы (наборы vin1, vs1) тестовой па-

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

ROBDD-графом: Rrob/xi = R_rob & x_i;

2) среди a_p-тестовых наборов выбираем такие, которые порождают пет-

ли: R_a/p = Rrob/xi & R_p, т.е. получаем множество всех векторов вида vin1, vs1,

сопоставляемых моменту времени t₂ при тестировании задержки пути;

3) выделяем в R_a/p множество внутренних состояний и представляем его

графом Rs0 ;

4) получив вектор vin1, vs1, далее формируем вектор vin2, vs1, который по-

рождается графом R_rob, и подаем его в момент t₃. Вектор vin2 отличается от

вектора vin1 по переменной x_i.

При нахождении тестовой пары для rising transition выполняем следующие

шаги алгоритма для b_p-тестовых наборов.

Последовательность шагов для rising transition пути α:

1) из R_rob формируем b_p-тестовые наборы (наборы vin1, vs1) тестовой па-

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

ROBDD-графом: Rrob/xi = R_rob & x_i;

157

0(0)

0(1)

1(1)

0(0)

1(0)

0(1)

Рис. 2. Диаграмма переходов схемы с памятью.

2) среди b_p-тестовых наборов выбираем такие, которые порождают пет-

ли: R_b/p = Rrob/xi & R_p, т.е. получаем множество всех векторов вида vin1, vs1,

сопоставляемых моменту времени t₂, при тестировании задержки пути;

3) выделяем в R_b/p множество внутренних состояний и представляем его

графом Rs0 ;

4) получив вектор vin1, vs1, далее формируем вектор vin2, vs1, который по-

рождается графом R_rob, и подаем его в момент t₃. Вектор vin2 отличается от

вектора vin1 по переменной x_i.

Рассмотрим иллюстрирующий пример. Пусть поведение автомата пред-

ставляется диаграммой переходов, представленной на рис. 2. В диаграмме

переходов состояния закодированы следующим образом: 1 —

0, 2 —

3—

0,4—

1. Имеем частный случай STG-описания, когда условия пере-

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

представляется вектором

0, сопоставляемым символу 1.

В диаграмме на дугах записаны входные и выходные (в скобках) векторы.

В данном случае это однокомпонентные векторы. При кодировании состояний

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

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

z₁

z₂

z′1

z′2

158

z₂'

z₁'

z₁

z₂

Рис. 3. Начало пути в схеме отмечено переменной x.

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

стемы ДНФ от входных переменных и переменных состояний:

z′1 = xz₁z₂ ∨ xz₁z₂;

z′2 = x ∨ z₁z₂;

y = xz₂ ∨ xz₂.

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

показанной на рис. 3.

Рассмотрим путь x → 4 → 7 → y.

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

рации над ДНФ, а не над ROBDD-графами для простоты. Чтобы сохранить

соответствие тексту алгоритма, символ D (вместо ДНФ) будем сопровождать

в скобках обозначением соответствующего ROBDD-графа из текста. Здесь

символами U₁, U₂, . . . обозначены выходы соответствующих элементов схемы.

DU7 /DU4 = (U₁ ∨ U₄)|U4=0 ⊕ (U1 ∨ U4)|U₄=1 = U1;

DU4 /D_x = (xz₂)|x=0 ⊕ (xz₂)|x=1 = z₂;

D_path = (xz₂)z₂ = (x ∨ z₂)z₂ = z₂.

Итак, D_path = z₂.

Вычисляем далее D(R_rob).

D(R_rise) = xz₂;

D(R_fall) = xz₂;

D(R^′rise) = z₂;

D(R^′fall) = z₂;

D(R_rob) = z₂.

159

Из табл. 3 выделяем переходы, сопоставляемые петлям в диаграмме пе-

реходов. Условия, обеспечивающие эти переходы, задаем соответствующей

ДНФ.

D(R_p) = xz₁z₂ ∨ xz₁z₂.

Для falling transition выполняем пп. 1-3 алгоритма и получаем состояние

D(Rs0 ) =

1. D(R_rob/x) = R_robx = xz₂;

2. D(R_a/p) = xz₁z₂;

3. D(Rs0 ) = z₁z₂.

Далее строим последовательность, доставляющую схему из начального со-

стояния q₀(

0) в состояние

Пытаемся найти последовательность длины один, перемножая ДНФ, со-

ответствующие переменным состояния: D(Rs1 ) = xz₁ ∨ xz₂ ∨ xz₁z₂.

Из полученной ДНФ следует, что из состояния

0 под действием входного

символа

1 попадаем в состояние

1. Из состояния

1 под действием входно-

го символа

0 оказываемся в том же состоянии

1 (рис. 2). Это значит, что,

воспользовавшись последовательностью длины один, в момент времени t₁

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

тестовой пары. А именно, под действием входного сигнала

0 формируем пер-

вый вектор тестовой пары в момент t₂. Оказавшись в следующий момент t₃ в

том же состоянии

1, подаем входной сигнал

1 и формируем второй вектор

тестовой пары. Это можно увидеть из диаграммы переходов (рис. 2).

Для rising transition выполняем пп. 1, 2 алгоритма.

1. D(R_rob/x) = xz₂;

2. D(R_b/p) = 0.

Поскольку D(R_b/p) = 0, приходим к заключению, что невозможно доста-

вить тестовую пару для rising transition для рассматриваемого пути.

Случай б).

Рассмотрим тестовую пару (vin1, vs1; vin1, vs2) векторов, которую необходимо

подать на комбинационную составляющую последовательностной схемы для

обнаружения задержки заданного пути α в условиях отличия векторов тесто-

вой пары (составляющих vs1, vs2) по переменной состояния z_i и при совпадении

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

менная, отмечающая заданный путь, не имеет инверсии. Опишем процедуру

доставки тестовой пары в соответствующие моменты времени:

1) предварительно с помощью подходящего входного воздействия уста-

навливаем схему (в момент t₁) в состояние vs1. В данном случае не важен

ни входной сигнал, ни состояние, из которого выполняется переход в состоя-

ние vs1;

160

Момент t₁

Момент t₂

Момент t₃

Рис. 4.

2) из состояния vs1 под действием входного сигнала vin1, поступающего в

момент t₂ (именно в этот момент обеспечивается подача на входы комбина-

ционной составляющей последовательностной схемы первого вектора vin1, vs1

тестовой пары), переходим в состояние vs2, т.е. переходим в соседнее состоя-

ние, отличающееся от vs1 по переменной z_i;

3) в состоянии vs2 в момент t₃ подаем на входы схемы вектор vin1, т.е.

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

комбинационной составляющей. Неважно, каким будет следующее состояние

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

сопоставляемом рассматриваемому пути.

В момент t₄ наблюдаем неисправность задержки на соответствующем пути

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

место.

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

друг за другом моменты времени. Переходы в моменты времени t₁, t₂, t₃ ил-

люстрируются рис. 4.

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

необходимо из начального состояния q₀ попасть в состояние vs1. Причем инте-

рес представляют не все состояния, имеющие переходы в соседние состояния,

а только те, в которых переход реализуется по входной составляющей vin1,

содержащейся среди полных состояний, представленных R_rob. Обеспечив по-

ступление в этом состоянии входной составляющей, далее формируем вектор

vin1, vs2, заменив в vs1 значение переменной z_i на инверсное.

Из STG-описания выделяем фрагмент, представляющий переходы в сосед-

ние состояния. Фрагмент состоит из строк вида:

k₁qi1 → qj1

k₂qi1 → qj1

k_mqi1 → qj1

km+1qi2 → qj2

km+sqi2 → qj2

161

Здесь k_i - конъюнкции (троичные векторы) на множестве входных пе-

ременных схемы, qi1 , qj1 , qi2 , qj2 . . . - состояния STG-описания (состояния ко-

нечного автомата), представленные булевыми векторами при кодировании.

Левую часть рассматриваемого фрагмента, т.е. конъюнкции от входных пе-

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

ROBDD R_s. Этот граф пригодится при рассмотрении всех путей из предъ-

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

следовательностной схемы. Перейдем к рассмотрению заданного пути α.

Последовательность шагов для falling transition пути α:

1) из R_rob формируем a_p-тестовые наборы (наборы vin1, vs1) тестовой пары,

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

ROBDD-графом: Rrob/zi = R_rob & z_i;

2) среди a_p-тестовых наборов выбираем такие, которые порождают перехо-

ды в соседние состояния по переменной z_i: R_a/s = Rrob/zi & R_s, т.е. получаем

множество всех векторов вида vin1, vs1, сопоставляемых моменту времени t₂

при тестировании задержки пути;

3) выделяем в R_a/s множество внутренних состояний и представляем его

графом Rs0 ;

4) получив вектор vin1, vs1, далее формируем вектор vin1, vs2, который порож-

дается R_rob, и подаем его в момент t₃. Вектор vs2 отличается от вектора vs1 по

переменной z_i.

При нахождении тестовой пары для rising transition выполняем следующие

шаги алгоритма для b_p-тестовых наборов.

Последовательность шагов для rising transition пути α:

1) из R_rob выбираем b_p-тестовые наборы (наборы vin1, vs1) тестовой пары, со-

поставляемые входной литере z_i, представляя их соответствующим ROBDD-

графом: Rrob/zi = R_rob & z_i;

2) среди b_p-тестовых наборов выбираем такие, которые порождают перехо-

ды в соседние состояния по переменной z_i: R_b/s = Rrob/zi & R_s, т.е. получаем

множество всех векторов вида vin1, vs1, сопоставляемых моменту времени t₂

при тестировании задержки пути;

3) выделяем в R_b/s множество внутренних состояний и представляем его

графом Rs0 ;

4) получив вектор vin1, vs1, далее формируем вектор vin1, vs2, который порож-

дается R_rob, и подаем его в момент t₃. Вектор vs2 отличается от вектора vs1 по

переменной z_i.

Итак, во всех выше перечисленных алгоритмах (п. 3) для отыскания те-

стовых пар формируется соответствующее множество Rs0 .

Находим последовательность [15], устанавливающую схему из начального

состояния q₀ в одно из состояний соответствующего отыскиваемой паре мно-

жества Rs0 , т.е. в состояние vs1. Получив это состояние, используем для тесто-

вой пары этого же типа ROBDD-граф из множества {R_a/p, R_a/s, R_b/p, R_b/s} и

162

z₂'

z₁'

z₁

z₂

Рис. 5. Начало пути в схеме отмечено переменной z₁.

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

бом, указанными в п.4 соответствующего отыскиваемой паре алгоритма.

Рассмотрим пример. В схеме задан путь z₁ → 3 → 8 → 9 → z′1 (см. рис. 5).

Начало пути отмечено переменной z₁.

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

DU9 /DU8 = (U₈ ∨ U₆)|U8=0 ⊕ (U8 ∨ U6)|U₈=1 = U6 ⊕ 1 = U6;

DU8 /DU3 = (U₃x)|U3=0 ⊕ (U3x)|U₃=1 = x;

DU3/Dz1 = (z₁z₂)|z1=0 ⊕ (z1z2)|z₁=1 = z2;

D_path = (xz₁z₂)xz₂ = (x ∨ z₁ ∨ z₂)xz₂ = xz₂.

Итак, булева разность представляется в виде D_path = xz₂.

Вычисляем далее D(R_rob).

D(R_rise) = xz₁z₂;

D(R_fall) = xz₁z₂;

D(R^′rise) = xz₂;

D(R^′fall) = xz₂;

D(R_rob) = xz₂.

Получили единственную конъюнкцию, не содержащую переменную, отме-

чающую начало рассматриваемого пути. Конъюнкция порождает единствен-

ную тестовую пару. Получена (1

1,1

1 ).

Из табл. 3 выделяем переходы, представляемые соседними векторами на

множестве переменных z₁, z₂. Условия, обеспечивающие эти переходы, задаем

в виде ДНФ.

D(R_s) = xz₁z₂ ∨ xz₁z₂ ∨ xz₁z₂ ∨ xz₁z₂ ∨ xz₁z₂.

163

Рассматриваем falling transition. Выбираем вектор

1. Это a_p-тестовый

набор, поскольку он обращает в единицу ДНФ одновыходной подсхемы, ко-

торой принадлежит рассматриваемый путь.

Для falling transition выполняем пп. 1-3 алгоритма и получаем состояние

D(Rs0 ) =

1. D(Rrob/z1 ) = xz₁z₂;

2. D(R_a/s) = xz₁z₂;

3. D(Rs0 ) = z₁z₂.

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

стояния q₀, представляемого вектором

0, попасть в состояние

1. Ранее

было показано, что в состояние

1 можно попасть из начального состоя-

ния

0 по входному символу

1 (D(Rs1 ) = xz₁ ∨ xz₂ ∨ xz₁z₂.). В состоянии

1 формируем тестовые пары

1 и

1. Эту ситуацию можно видеть из

диаграммы переходов (рис. 2).

Рассматриваем rising transition. Выбираем вектор

1. Это b_p-тестовый

набор, поскольку он обращает в ноль ДНФ одновыходной подсхемы, которой

принадлежит рассматриваемый путь.

Пытаемся найти последовательность длины один, перемножая ДНФ, со-

ответствующие переменным состояния: D(Rs1 ) = xz₁z₂. Полученная ДНФ в

начальном состоянии

0 не обращается в единицу. Следовательно, не суще-

ствует последовательности длины 1, доставляющей нужную тестовую пару.

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

условия перехода из начального состояния в состояние

1. Ранее эти условия

уже находили и представляли в виде ДНФ. Под действием входного симво-

ла x = 1 из начального состояния

0 попадаем в состояние

1. Далее из

состояния

1 под действием входного символа

1 попадаем в состояние

Итак, получили входную последовательность

1, приводящую схему в со-

стояние

1. Это можно видеть по диаграмме переходов (рис. 2). Формируем

первый вектор тестовой пары

1. Под действием входного сигнала x = 1 пе-

реходим в состояние

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

rising transition. Эту ситуацию также можно видеть из диаграммы переходов

(рис. 2).

Строим для каждого пути из заданного множества и типа перепадов зна-

чений сигналов соответствующие последовательности, обнаруживающие за-

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

заданного множества путей. Отметим, что полученная тестовая последова-

тельность состоит из фрагментов, начинающихся в состоянии q₀.

164

5. Результаты экспериментов

Описанные выше алгоритмы были реализованы в виде программы. Для

операций над ROBDD-графами использовалась библиотека CUDD. Были

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

ведены в табл. 4. В схемах, представленных в бенчмарках, рассматривались

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

ничивалась тысячью входными векторами, однако в процессе эксперимента

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

В последнем столбце таблицы показана доля (в процентах) путей, для ко-

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

вить тестовую пару, обнаруживающую робастно тестируемую неисправность

задержки пути. Эта доля определяется по отношению ко всем путям, для

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

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

составляющей.

Результаты экспериментов, проведенных на контрольных схемах, показа-

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

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

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

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

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

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

Обозначения:

— name - название бенчмарка;

— i - количество входов;

— s - количество переменных состояний;

— xr - количество путей, начало которых помечено входной переменной и

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

Тестовая пара предназначена для rising transition;

— xf - количество путей, начало которых помечено входной переменной и

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

Тестовая пара предназначена для falling transition;

Таблица 4. Результаты экспериментов

name i s xf xr zf

zr xob zob ob

s27

17,2%

s208

643

s298

1179

s386

320

572

160

1351

11,8%

s510

906

724

575

1373

41,9%

s820

451

1860

1392

1313

3055

42,87%

s832

450

1859

1391

1312

3052

42,98%

s1488

2578

2209

1612

5384

29,94%

s1494

2628

2247

1626

5351

30,39%

165

— zr - количество путей, начало которых помечено переменной состояния и

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

Тестовая пара предназначена для rising transition;

— zf - количество путей, начало которых помечено переменной состояния и

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

Тестовая пара предназначена для falling transition;

— xob - количество путей, начало которых помечено входной переменной и

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

сигналов из начального состояния схемы;

— zob - количество путей, начало которых помечено переменной состояний

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

сигналов из начального состояния схемы;

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

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

— N - количество путей, для которых существуют непустые графы R_rob;

— % - доля (в процентах) робастно тестируемых путей, для которых уда-

лось доставить тестовую пару, среди путей, для которых существуют непу-

стые графы R_rob.

6. Заключение

Ранее был предложен метод отыскания всех тестовых пар, состоящих из

соседних наборов булевых векторов, обнаруживающих робастно тестируемые

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

онной составляющей схемы с памятью. В данной работе предложен способ

доставки таких тестовых пар из начального состояния q₀ схемы с памятью в

условиях ограничения на длину последовательности, основанный на опера-

циях над ROBDD-графами. Работа ориентирована на исследование возмож-

ности отказа от использования техник сканирования, требующих больших

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

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

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

контрольных примерах (benchmarks) показали, что далеко не всегда удается

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

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

ступности ее переменных состояния. Это значит, что для некоторых схем с

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

без существенных аппаратурных затрат может оказаться невозможным.

ПРИЛОЖЕНИЕ

Доказательство теоремы 1. Будем иметь в виду, что a_p-тестовый

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

обращает в единицу в общем случае несколько непустых конъюнкций ЭНФ

(в непустых конъюнкциях ЭНФ отсутствуют взаимно инверсные перемен-

ные). Каждая из таких конъюнкций содержит литерал ЭНФ, сопоставляе-

мый пути α (литерал ЭНФ — это символ переменной с подходящим знаком

166

инверсии и последовательностью индексов, представляющих путь α). Сопо-

ставляемая литералу переменная присутствует в такой конъюнкции только

один раз. Это объясняется тем, что b_p-тестовый набор тестовой пары (b_p, a_p)

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

от литерала, сопоставляемого пути α только последовательностью индексов,

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

рассматриваемой пары порождаются одной и той же непустой конъюнкцией

ЭНФ (условие 4). Отметим, что тестовый набор для a_p-неисправности (по по-

строению) ортогонален каждой конъюнкции ЭНФ, не содержащей литерала,

сопоставляемого пути α. Тестовый набор для b_p-неисправности (по построе-

нию) ортогонален всем конъюнкциям ЭНФ. Примем во внимание, что любой

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

пустой конъюнкции. Это значит, что минимально покрывающий интервал u,

порожденный соседними векторами (b_p, a_p), ортогонален каждой конъюнк-

ции ЭНФ, не содержащей литерал, сопоставляемый пути α. Итак, для рас-

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

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

нее в работе. Имея в виду теорему 5 работы [7], приходим к заключению, что

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

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

доказана.

Доказательство теоремы 2. Пусть u — минимально покрывающий

интервал наборов (b_p, a_p) тестовой пары для робастно тестируемой неисправ-

ности задержки пути. Рассмотрим тестовый набор a_p. Этот набор (по построе-

нию) ортогонален каждой конъюнкции, не содержащей литерал, сопоставляе-

мой пути α, и, возможно, пересекается с некоторыми остальными конъюнк-

циями рассматриваемой ЭНФ. Построим для a_p соседний по переменной x_i

набор b^′. Здесь x_i — переменная, отмечающая начало пути, для которого

построена тестовая пара (b_p, a_p). Набор b^′ поглощается интервалом u, сле-

довательно, тоже ортогонален каждой конъюнкции, не содержащей литерал,

сопоставляемой пути α. Кроме того, b^′ ортогонален всем конъюнкциям, со-

держащим литерал, сопоставляемый пути α, по переменной x_i, т.е. b^′ ортого-

нален конъюнкциям ЭНФ в целом. Это значит, что он принадлежит области

нулевых значений функции, представляемой ЭНФ, и является b_p-тестовым

набором. Теорема доказана.

СПИСОК ЛИТЕРАТУРЫ

1. Matrosova A., Ostanin S., Chernyshov S. Masking Robust Testable PDFs //

Proceedings of

2019

IEEE East-West Design & Test Symposium (EWDTS),

13-16 september 2019, Batumi. Kharkov: IEEE, 2019. P. 420-423.

2. Matrosova A.Yu., Andreeva V.V., Tychinskiy V.Z., Goshin G.G. Applying ROBDDs

for delay testing of logical circuits. // Russ. Physics J. 2019. V. 62. No. 5. P. 615-621.

3. Lindgren P., Kerttu M., Thornton M., Drechsler R. Low power optimization

technique for BDD mapped circuits // In Proceedings of the 2001 Asia and South

Pacific Design Automation Conference (ASP-DAC ’01), Association for Computing

Machinery, New York, NY, USA, P. 615-621.

167

Shelar R.S., Sapatnekar S.S. An efficient algorithm for low power pass transistor

logic synthesis // Proceedings of ASP-DAC/VLSI Design 2002, 7th Asia and South

Pacific Design Automation Conference and 15h International Conference on VLSI

Design, Bangalore, India, 2002, P. 87-92.

Gekas G., Nikolos D., Kalligeros E., Kavousianos X. “Power aware test-data

compression for scan-based testing”, ICECS 2005 // 12th IEEE International

Conference on Electronics, Circuits and Systems, Gammarth, Tunisia, 2005, P. 1-4.

Tudu J.T., Larsson E., Singh V., Agrawal V.D. On Minimization of Peak Power

for Scan Circuit during Test // Test Symposium 2009 14th IEEE European, 2009,

P. 25-30.

Kotasek Z., Skarvada J., Strnadel J. Reduction of Power Dissipation Through

Parallel Optimization of Test Vector and Scan Register Sequences // IEEE

International Symposium on Design and Diagnostics of Electronic Circuits and

Systems, 2010, P. 364-369.

Eichelberger E.B., Williams T.W. A Logic Design Structure for LSI // Proc. 14th

Design Automation Conference. 1977. P. 462-468.

Agrawal V.D., Cheng K.T., Johnson D.D. Designing Circuits with Partial Scan //

IEEE Design and Test of Computers. 1988. P. 8-15.

10.

Матросова А.Ю., Липский В.Б. Свойства пар тестовых наборов, обнаружива-

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

водительности // АиТ. 2015. № 4. С. 135-148.

Matrosova A.Yu., Lipskii V.B. Properties of pairs of test vectors detecting path delay

faults in high performance VLSI logical circuits // Autom. Remote Control. 2015.

No. 4. P. 135-148.

11.

Сапожников В.В., Сапожников Вл.В., Лыков А.А. Теоремы анализа для обна-

ружения неисправности типа “временная задержка” // Электрон. моделирова-

ние. 2004. Т. 26б. No. 3. С. 83-93.

12.

Matrosova A.Yu., Andreeva V.V., Nikolaeva E.A. Finding Test Pairs for PDFs in

Logic Circuits Based on Using Operations on ROBDDs // Russ. Physics J. 2018.

V. 61. No. 5. P. 994-999.

13.

Efanov D., Sapozhnikov V., Sapozhnikov Vl., Nikitin D. Sum Code Formation with

Minimum Total Number of Undetectable Errors in Data Vectors // Proceedings of

13th IEEE East-West Design & Test Symposium (EWDTS‘2015), Batumi, Georgia,

September 26-29, 2015, P. 141-148.

14.

Efanov D.V., Sapozhnikov V., Sapozhnikov Vl. Two-Modulus Codes with Summation

of One-Data Bits for Technical Di-agnostics of Discrete Systems // Automatic

Control and Computer Sciences. 2018. V. 52. Issue 1. P. 5-21.

15.

Matrosova A., Andreeva V., Melnikov A. ROBDDs Application for Finding the

Shortest Transfer Sequence of Sequential Circuit or Only Revealing Existence of

this Sequence without Deriving the Sequence itself //Proceedings of IEEE East-

West Design & Test Symposium (EWDTS’2016). Yerevan: IEEE Computer Society,

2016. P. 513-516.

Статья представлена к публикации членом редколлегии М.Ф. Караваем.

Поступила в редакцию 22.05.2020

После доработки 01.02.2021

Принята к публикации 16.03.2021

168