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

МОСКОВСКИЙ ордена ЛЕНИНА и ордена ОКТЯБРЬСКОЙ РЕВОЛЮЦИИ ЭНЕРГЕТИЧЕСКИЙ ИНСТИТУТ

На правах рукописи УДК 621.382.049.775.014.001.573(043)

ГОЛЕМБИОВСКИЙ ДМИТРИЙ ЮРЬЕВИЧ

Разработка и исследование методов оценки достоверности встроенного псевдослучайного тестирования БИС

05.13.13 - Вычислительные машины, комплексы, системы и сети

05.13.05 - Элементы и устройства вычислительной техники и систем управления

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

Москва - 1989

Работа выполнена на кафедре Системотехники Московского ордена Ленина и ордена Октябрьской Революции энергетического института

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

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

кандидат технических наук, доцент Ярыолик В.Н.

Ведущая организация: Институт прикладной математики и механики АН УССР

Защита состоится " /</ " 1990 года в ///> час.

¿^'С' мин, б аудитории /З^на заседании специализированного Совета Д-053.16.09 при Московском энергетическог.Гинстктутё

Отзывы на автореферат (в двух экземплярах), заверенные печатью учреждения, просим направлять по адресу: 105835, ГСП, Москва, Е-250, Красноказарменная ул., д. 14, Ученый Совет МЭИ.

С диссертацией можно ознакомиться в библиотеке МЭИ Автореферат разослан " 16 " ан^^сМ 1990г.

Ученый секретарь специализированного Совета к.т.н., доцент „ • п п А.В.Князев

иш4

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

Актуальность теш. Для анализа выходных последовательностей БИС при встроенном псевдослучайном тестировании (ВГГГ) попользуются способы сжатия их в сигнатуру с последующим сравнением ее с эталонкыг.1 значением, полученном на заведомо исправной схеме. При ВПТ БИС, реализованных на базовых матричных кристаллах с интеграцией не более 5-6 тыс. вентилей, устройства, осуществ-ляюиде сжатие выходных реакций, содержат, как правило, малое количество триггеров, что обусловлено ограниченностью площади кристалла. В этих условиях потери достоверности при сжатии информации становятся соизмеримыми с недостоверностью тестирования самого объекта. Поэтому при оценке достоверности контроля традиционным методом - с помощью моделирования неисправностей - кавдая из них должна быть промоделирована на всей тестовой последовательности, а не только до момента ее проявления на выходных контактах с хеш. Это приводит к резком/ увеличению затрат времени, так как подавляющее большинство неисправностей проявляется на относительно коротких отрезках тестовой последовательности.

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

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

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

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

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

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

На основе данной теории получены аналитические зависимости вероятности обнаружения заданной неисправности от длины псевдослучайной тестовой последовательности при различных способах сжатия выходных реакций для синхронных последовательноетных схем с цепями начальной установки (в дальнейшем - Р^-завнсимости).

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

Описанная в зарубежной литературе методика PREDICT обобщена на случай многовыходных устройств и развита для оценки параметров Р1"-зависимостей схем комбинационного типа.

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

Цредложена имитационно-статистическая методика оценки параметров Р^-занисимостей и прогнозирования достоверности ВПТ по результатам моделирования неисправностей БИС на.небольших выборках тестовых векторов после их проявления на выходных контактах схемы.

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

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

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

устройств, реализованных в впде БИС ПЗУ. Затраты времена на ее получение линейны по чисду входов тестируемой комбинационной схемы.

Предложенная адалитико-имитационная методика оценки достоверности ВИГ позволяет оценивать достоверность тестирования как комбинационных, так и последовательностных дискретных устройств при налички любых неисправностей, которые могут быть смоделированы программно. Затраты машинного времени для схем, на которых проводилось экспериментальное исследование данной методики, оказалось в 1,5-3 раза меньше, чем при моделировании всех неисправностей на полной тестовой последовательности.

Применение всех разработанных методов оценки достоверности встроенного псевдослучайного тестирования целесообразно для БИС, реализуемых на базовых матричных кристаллах с интеграцией не более 5-6 тыс. логических вентилей. Необходимая для расчетов производительность обеспечивается ЭВМ ЕС-1045 и старшими моделями.

Реализация и внедрение результатов работы. Все предлояенные в диссертационной работе методы доведены до практических алгоритмов и реализованы на алгоритмическом языке ПД/1 ЕС ЭВМ. Метод оценки достоверности ВПТ на основе РЙс^ГСТ и аналитико-ишта-цнонная методика реализованы в составе системы САНТИМ (синтез, анализ тестов и моделирование), разработанной на кафеДР6 математического моделирования МЭИ. Объем программных комплексов без системы САНТИМ составляет соответственно 1470 и 1330 операторов языка ПЛ/1. Создана отдельная программа оценки достоверности ВПТ в классе произвольных логических неисправностей для БИС со сканирующими путями, использующая соответствующий метод (около 100 операторов 1Щ/1)•

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

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

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

Алпобапня работы. Результаты работы докладывались на 2-ом Всесоюзном совещании-семинаре по методам синтеза и планирования развития структур крупномасштабных систем (Саратов, 1986г.), семинаре "Вероятностные методы тестирования цифровой аппаратуры" (Минск, 1987г.), 1-ой зимней иколе-семинаре "Методы и системы управления вычислительными и контрольно-измерительными комплексами" (Саратов, 1988г.), &-ой конференции молодых ученых и специалистов ЮИ в 1987г.

В полном объеме материалы диссертационной работы докладывались и получили поло;хительцую оценку в Институте прикладной математики и механики АН УССР (Донецк, 1988 г.).

Объем и структура работы. Диссертация состоит йз введения, четырех глав, заключения, 6-ти приложений и списка литературы, включающего 107 наименований. Основная часть содержит 140 страниц машнописного текста, 54 рисунка и 13 таблиц.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОШ

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

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

Далее проводится анализ имитационного моделирования неисправностей как метода оценки достоверности ВПТ. Формулируется

критерий достоверности, традиционно используемый при моделировании: ¿ ;

, (I)

где Р"" - вероятность возникновения ¿-ой неисправности в БИС, /,- количество рассматриваемых неисправностей, если ¿-я

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

Распространенным критерием при вероятностной оценке достоверности псевдослучайных тестов дискретных устройств является следующий: ¿ ; ;

где Р - вероятность обнаружения ¿-ой неисправности. В главе I показано, что критерий (2) является аппроксимацией (Г), точность которой тем выше, чем больше число неисправностей ¿.

Во второй главе получаются аналитические зависимости обна-руяепия отдельной неисправности Р' (см. (2)) от длины псевдослучайной тестовой последовательности для синхронных последователь-ностных схем с цепями начальной установки. Анализ выходных реакций производится способами СР, ОТ и счета выходных состояний по модулю , где I- разрядность счетчика. Для точного подсчета числа появлений заданных контрольных векторов на выходе дискретного устройства количество триггеров счетчика должно удовлетворять условию I) Ссд2 л/, где У - длина теста, то есть разрядность счетчика возрастает с увеличением длины тестовой последовательности .

Современные цифровые БИС, строящиеся на базе потенциальных систем элементов, естественным образом описываются конечными автоматами ГДура. Пусть Ч10 > - автомат, описывающий функционирование исправного устройства. Здесь X и У- соответственно входной и выходной алфавиты, 2° - множество . состояний, 2/ - начальное состояние автомата, и функции переходов и выходов соответственно. А" - автомат Мура, значение 4>°в каждом такте однозначно определяется значением f0 . Предметом исследования являются цифровые устройства, поэтому элементы множеств X , У и 2° суть двоичные векторы. Предполагается, что Ае обладает свойством сильной связности, что практически всегда выполняется для реальных устройств. Входной сигнал начальной установки автомата обозначен -Яу, / " , Х^) = 5у .

Автомат, соответствующий устройству с ¿-ой неисправностью, есть А1" - (Х,2С, V",/', > . Этот автомат в общем случае не является инициальным. Смысл символов, входящих в определение А1' , аналогичен описанному выше для автомата А". А1 не предполагается сильносвяз ним, так как для реальных дискретных устройств с неисправностями данное свойство может не выполняться. Предполагается, однако, что каждый автомат А1 содержит только один тупиковый подавтомат или, что то же самое, множество содержит единственное эргодическое подмножество состояний 2^ . Подавляющее большинство реальных дискретных устройств обладают постулированным свойством для достаточно широкого класса неисправностей.

Для анализа процесса контроля рассматривается работа автоматов /?1и А 'при подаче на их входы одинаковой тестовой последовательности. Данной паре автоматов с общим входом эквивалентен автомат /? являющийся результатом операции декартова произведениями Л". Состояния автомата ^соответствуют парам состояний автоматов /}'и А6, выходные сигналы - парам выходных символов этих автоматов. Функции переходов fL л выходов определяются через соответствующие функции автоматов А1 и А". Подмножество "состояний /^"содержит все состояния, в которые он может быть переведен подачей сигнала инициализации Ху .

Обозначим ¿¿"подмножество состояний ЛсС, достижимых хотя бы из одного состояния Так как начальное состояние А1"принадлежит подмножеству 2^с, процесс переходов этого автомата ограничен состояниям подмножества 21°*2}е1/2}. Доказано, что 2^ имеет

единственное эргодическое подмножество состояний.

Для построения Р'-зависимости, соответствующей способу СС, вводится автомат где и - , V' - алфавит

выходных сигналов, М/ = 2у . Функция У отличается от соответствующей функции автомата Л1е только областью определения, а функция от - еще и своим значением: выходной сигнал М~ равен единице, когда на выходе тестируемого автомата Я1 присутствует комбинация, принадлежащая подмножеству выходных векторов V*, количество появлений которых подсчитывается, а выходной вектор эталонного автомата А' не принадлежит У* ; равен нулю, если выходы А1 и А" совпадают; и равен "-1" при условии, что выходная комбинация А" входит в У*, а выходной набор А1 не принадлежит этому множеству.

Неисправность не обнаруживается при контроле по способу СС, если количества появлений контрольных векторов из У* в выходных последовательностях автоматов й'и А0 различаются на число, кратное гь : . вн- м- - с

^ы-ЪЪЧ « = (3)

Здесь - количество состояний автомата М~ , ^ - количество его пищаний в ^ -ое состояние за все время тестирования, V* Из единственности эргодического подмножества состояний автомата АГ.следует, что в большинстве практических случаев распределение дается локальной предельной теоремой для сумы случайных величин, связанных в цепь Маркова, в виде

п'а/а) У й ~ 2^

Р (¿.Ь'гЩРв-1- . >

где ¿ - значение у аУ\\ имеют смысл предельного матема-

тического ожидания и дисперсии:

¿'V = М Сс МЗ + О (А/), 4)

Р1 - зависимость для способа счета выходных состояний имеет вид:

_ (5)

Здесь *7- наименьшее целое число, такое, что к4-2':>а ы-дЪчы ; аналогично Кг - наибольшее целое число, для которого выполняется условие ь а'М+Зб1)//?.

Рассматриваемый способ сжатия СС состоит в подсчете числа единиц на выходе схемы выделения заданного множества выходных

состояний У* го модулю 2е, где t- число триггеров счетчика. Процесс смены состояний суперпозиции счетчика, для которого допускается переполнение, и тестируемого автомата описывается конечной цепью Маркова. Это указывает на существование финальных вероятностей состояний счетчика и, следовательно, предельной вероятности обнаружения неисправности.' Показано, что в большинстве практических случаев данная вероятность равна 1-1/2 . Однако процесс установления предельной вероятности обнаружения неисправности способом СС происходит медленно, поэтому для оценки его достоверности следует использовать соотношение (5).

В качестве оценки вероятности обнаружения неисправности способом 0Ф предлагается использовать финальную вероятность несовпадения выходных сигналов автоматов Л' и Лс. Таким образом,

2е - зависимость для способа СФ есть константа:

^ ^ = < <6>

Известно, что при сжатии последовательности двоичных сигналов бернуллиевского типа финальные вероятности состояний сигнатурного анализатора на основе регистра сдвига одинаковы. При сжатии выходной последовательности конечного автомата данное положение может не выполняться. Достаточным условием его осуществления является сильная связность суперпозиции конечного автомат та и сдвигового регистра при условии, что свободный член его обт разующего полинома отличен от нуля. На основе данного результата в диссертации показано, что в большинстве практических случаев предельная вероятность обнаружения неисправности последователь-носгного устройства способом СР есть 1-1/2^, где С - разрядность анализатора.

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

Р^ Ы) - & '//), (?)

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

от длины тестовой последовательности для способа сравнения с эталоном (СЭ).

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

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

В третьей главе разрабатываются методы определения параметров g-', и PLCJ jP'-зависимостей (5), (6) и (7) для реальных дискретных устройств.

Если БКС содержит сканирующие пути,- то в режиме контроля производится реконфигурация.её в комбинационную схему. Taie как текущий выходной сигнал схем данного типа не зависит от предыстории их работы, применение способа 05 для анализа выходных реакций не является целесообразным. Одним из подходов к определению значений параметров и оценке достоверности сигнатурного анализа комбинационного устройства является допущение об искажении любой клетки таблицы его истинности с одинаковой вероятностью 4-f • Такое допущение справедливо для БИС, построенных на базе ШШ, а также "для комбинационных схем, реализованных на основе БИС ПЗУ.

На базе принятого допущения для расчета вероятности необна-рукения случайно возникающей неисправности способом СЭ получено следующее рекуррентное соотношение:

5Г LL-M)3-

где , (jf-!fz)jkc (Pj)2 , Pj - вероятность появления ^ -го двоичного набора в тестовой последовательности. Начальные члены соответствующей последовательности вероятностей определяются как Pe3(d)*f = Очевидно, = . Достоверность контроля способом СР монет быть теперь определена на основе (7):

рсрм Л и- v// -о-'/¿e)£p/ùd'f'-'/¿ъм.

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

приводятся определения вероятностных характеристик линий, используемых з РЧЕЯН'Т.

1-упразллемостью С!^)(О-управляемостью СоЦ) ) линии/ кг-зыв^ется вероятность присутствия единицы (нуля) в этой линии при заданном распределении входных сигналов.

1-дбтектируемостью (О-детектируемостью) линии называется вероятность совмещения двух событий: I - данная линия находится з единичном (нулевом) состоянии и 2 - значение логического сигнала в зтей линии влияет на выходной сигнал схемы. Обозначим величины детектируемоети через Л/^и ^О(^). К^Ц) есть вероятность обнаружения неисправности "константный 0" в линии ^ , а йсЦ)- неисправности "константная I".

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

Если логический вентиль расположен в той части схемы, где отсутствуют разветвления, он рассматривается только один раз. Для расчета данных вероятностных характеристик цри наличии разветвляющихся путей, .сигналы в которых являются статистически зависимыми, в методике Ривк]сТиспользуется концепция супервенти-лд. С содержательной точки зрения супервентилю лиши </ соответствует наименьшая предшествующая ] логическая подсхема, сигналы на входе которой статистически независимы. При расчетах в су-перзентпле производится многократное прохождение составляющих его зле,ментов.

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

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

Методика РИВЛ/СТ позволяет рассчитывать вероятность проявления любой неисправности комбинационной схема ка ее выходных полюсах. Этого достаточно для определения вероятности Р^^) и оценки достоверности СР по (2) и (7). Дяя оценки Еерсятксст:: обнаружения неисправности способом СС важен не только факт проявления неисправности, но также и вид искажения выходного сигнала дополнительной комбинационной схемы, осуществляющей выделение заданного подмножества выходных векторов. Обозначим через $¿¿¡-¡1) вероятность передачи нулевого сигнала линиина вход контрольного счетчика значением "I". Аналогично определяются показатели детектируемости •»(■¥ ф) и МН^) . В диссертации по-

лучены соотношения для расчета введенных характеристик. Параметры й1- и 'У* соотношения (5) выражены через вероятности лсо/"^) , ■АО!ф) , Л/сф) , АНф) •

Уточнены такие некоторые формулы, содержащиеся з первоисточниках по РЙСЙ7СГ .

Зависимость времени расчетов достоверности ВИТ полученном методом является линейной по числу линий схемы, тогда как временная сложность алгоритмов наиболее распространенного параллельного моделирования неисправностей квадратична по это:.:/ показателю. Точность результатов расчета возрастает с увеличением размерности с хеш. Проведенные для пяти комбинационных схем расчеты и имитационные эксперименты подтвердили данные теоретические положения. Время расчета достоверности псевдослучайного теста, содержащего 400 наборов, для наибольшей из рассмотренных схем (1529 линий) на ЭВМ ЕС-1051 составило около 5 часов, а время моделирования того же теста около 15 часов.

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

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

Параметры й1 и <3\1 соотношения (5) могут быть определены по реализациям величины' 4>се , получаемым в соответствии с (3). Рассмотрим случайный процесс (УУ/У , //= 2, — Как следует из (4), он является асимптотически стационарным по математическому ожиданию, предельное значение которого равно а1- . При этом дисперсия процесса убывает с ростом числа испытаний. Следовательно, величина стрештся с ростом д/ к своему математичес-

кому ожиданию Л1- и может служить его оценкой. Для уменьшения дисперсии можно использовать усреднение или экспоненциальное сглаживание оценок.

Для оценка параметра 0" рассмотрим другой случайный процесс - » -/,2,... . В_ соответствии с (4), его дисперсия стрештся с ростом N к , а математическое ожидание медленно возрастает:

• м [М/6Г.7 = о (Ж).

Для оцешси <з' необходимо выделить тренд рассматриваемого процесса, для чего вновь воспользуемся фильтром экспоненциального сглаживания: , . .. ;

Ш) = X t /у-у; * ц-ь) (%"сс, ^/У

Тогда математическое ожидание процесса ^сс

стрештся к ¡б1)"* . Оценка данной величины монет быть подучена •

по методу расчета среднего или экспоненциального сглаживания.

Для оцешси вероятности обнаружения неисправности способом финального состояния Р^ можно воспользоваться известным из теории марковских цепей соотношением: Р^ -/¡^ , где

У/р^/д// - количество несовпадений выходных сигналов исправной и неисправной схем 'за л/ тактов тестирования, или применить фильтрацию данной частотной оценки по методу среднего или экспоненциального сглаживают.

Как следует из (7), моделирование неисправностей для оценки достоверности способа СР достаточно проводить так же, как и в случае непрерывного сравнивания выходов неисправного и эталон-

ного устройств, до момента несовпадения состоя;::;!; этих выходов. Тогда Pf3 -J и фор:<ула (7) принимает более простой вид: Pep - V - //3 <

Для экспериментальной проверки алгоритмов предложенной ана-литико-имитационной методики оценки достоверности ВИТ были промоделированы 4 последовательностные схемы различней сложности при скатии выходных реакций способа:.:-! С?, СС a CQ. Точность результатов методики и выигрыш зо времени возрастав? с увеличением сложности устройств и длины тестов. При этом лучшие результаты дает применение для оценка параметров фильтра экспоненциального сглаживания. Наиболее сложная из рассмотренных схем содер?.:п? 1128 линий. При оценке достоверности псевдослучайного теста, содержащего 600 входных наборов, использование фильтра экспонепцп-ального сглаживания обеспечило для этой схемз сохранение затрат машинного времени по сравненаа с полным моделированием неисправностей для способов СС и СФ приблизительно в 2 и 1,7 раза.

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

Комплекс программ (КП) PREFECT предназначен для расчета достоверности ВПТ цифровых устройств комбинационного типа з классе одиночных константных неисправностей. При этом анализ выходных сигналов может осуществляться способами CP, СС, СЭ. Комплекс реализован в среде системы синтеза, анализа моделирования тестов САНТИМ, разработанной на кафедре математического моделирования МЭИ. Программы КП PREA1C-7 написаны на алгоритмическом языке 1Щ/1. Возможна экспериментальная проверка результатов расчета с помощью имитационного моделирования. При этом РИёЩСГ взаимодействует с подсистемой моделирования САНТИМ.

Далее описаны основные алгоритмы РРЕЯТОГц даны примеры ::х работы.

КП COMPACT предназначен для исследования точности и эффективности аналитико-лмитацпокной методики оценки достоверности ВПТ БИС. Анализ выходных реакций тестируемого объекта может производиться способами CP, СС а 03. Область применения комплекса ограничена синхронным:! последовательностными схемой с цепями

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

Программа моделирования системы САНТИМ, в среде которой реализован КП C0I.PACT, не позволяет исключать из процесса моделирования какие-либо неисправности, поэтому экономия машинного времени, предоставляемая разработанной аналитико,-имитационной методикой, монет быть рассчитана лишь теоретически. Комплекс COMPACT вместе с СА1ГГШ.1 представляет собой системы для исследования точности и эффективности предложенной методики. При этом исследования могут проводиться для случая одиночных константных неисправностей схемы, так как программы САНТИМ моделируют неисправности только этого класса.

Схема двоично-десятичного накопителя с изменяемой емкостью реализуется на базовом матричном кристалле, содержащем 3200 логических ьентилей. При производственном контроле изделий на пластину полупроводникового материала опускаются контактные иголки, подводящие питающие напряжения и тестовые воздействия к внеинпм контактам микросхем. Имеющиеся в наличии средства -электроники позволяют производить тестирование кристаллов на частоте не выше I кГц. С другой стороны, технологически допустимое время контакта иголок с поверхностью пластины составляет не более 0,5с., что обусловлено соображениями сохранности изделий. Полнота производственного контроля БИС, достигаемая в этих условиях, является неудовлетворительной. Значительная часть кристаллов, признанных годными на данном этапе, бракуется при тестировании па рабочих частотах микросхем после установки кристаллов в корпуса (20$), что приводит к непроизводительным затратам труда и расхода- корпусов.

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

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

Оценка достоверности ВПТ рассматриваемой БИС проводилась путем полного и приближенного моделирования неисправностей с применением фильтра экспоненциального сглаживания для получения значений параметров Р1-зависимостей. Результаты полного моделирования и аналитико-имитационней методики оказались практически совпадающими. Достоверность ВПТ БИС накопителя, рассчитанная согласно (2), составила около 255/255.

Разработанная на логическом уровне система ЗПТ для рассмотренной БИС принята к технологическому проектированию на одном из НПО г.Москвы.

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

В приложении 2 получаются характеристики элементов комбинационного базиса системы САНТИМ, необходимые для реализации метода расчета достоверности ВПТ комбинационных устройств на основе РНЕ ШТ. .

3 приложении 3 помещены руководства программиста по эксплуатации программных систем оценки достоверности встроенного псевдослучайного тестирования РКья1(?Т и СОМРАСТ, а

в приложения 4 - распечатки программ.

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

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

ЗАКЛЮЧЕНИЕ

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

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

ля с помощью моделирования неисправностей.

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

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

4). Предложен позы:! способ контроля выходных последователь-костей Б 'АО при ВПТ, состоящий в сравнении последних выходных наборов исправного и неисправного устройств. Способ не требует дополнительных аппаратурных затрат и в ряде случаев обеспечивает высокую достоверность контроля. Оценкой вероятности обнаружения конкретной неисправности данным способом может служить финальная вероятность несовпадения выходных сигналов неисправного и эталонного устройств.'

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

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

ки вероятности хорошо согласуются с результатам: имитационного моделирования.

Для расчета параметров Р1 -зависимостей и оценка достоверности ВПТ реальных цифровых EIC в диссертации разработаны три основных подхода.

7). Для БИС со сканирующими путям, приводящихся в режиме контроля к комбинационному виду и выполненных ка базе ILT.i, в качестве моделей' неисправностей рассмотрены равновероятные независимые искажения любой клетки таблицы истинности. Получено рекуррентное выражение для расчета достоверности тестирования БИС в данном классе неисправностей при контроле выходных реакций способом сигнатурного анализа на основе регистра сдвига. Сложность расчета достоверности для теста фиксированной длины линейна по числу, входов контролируемой комбинационной схемы.

. 8). Для оценки достоверности ВПТ БКС со сканирующими путями в классе одиночных константных неисправностей использована описанная в зарубежных источниках методика РйЕЯГСГ . Данная методика обобщена на случай многозыходннх комбинационных устройств, уточнен ряд ее положений и расширен набор рассчитываемых вероятностных характеристик схемы, что позволило использовать Р?£ЯГСГ для сценки параметров Р1 -зависимостей, соответствующих неисправностям схемы. Создан одноименный комплекс программ и осуществлена экспериментальная проверка точности разработанного метода путем моделирования неисправностей. Точность вероятностной оценки полноты контроля возрастает с увеличением числа элементов схемы. При этом времл расчетов линейно зависит от данного показателя, тогда как времл параллельного моделирования неисправностей возрастает с квадратом числа вентилей. Скидаемый экономический эффект от внедрения комплекса программ PREDICT составляет 22,5 тыс.руб.

9). Для оценки достоверности ВПТ БИС в последовательностном виде, а также при наличии более сложных неисправностей разработана аналитико-имитационнал методика, позволяющая сократить время моделирования. При этом моделирование катдой неисправности мо^е? продолжаться до момента получения статистической выборки, достаточной для оценки параметров соответствующих P~L -зависимостей с помощью статистической обработки случайных процессов.

Разработанный комплекс программ COI.iPACT позволяет производить исследование точности и эффективности данной методики. Про-

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

10). Метод контроля по последнее выходному набору использован при проектировании БИТ БИС двоично-десятичного накопителя с изменяемой.емкостью. Разработанные средства позволяют существенно повысить достоверность производственного контроля изделий и снизить расход корпусов БИС. Ожидаемый экономический эффект от внедрения разработки составляет 14,5 тыс.руб. в год.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИИ ОТРАЖЕНЫ В СЛЕДШЩ ПУБЛИКАЦИЯХ:

1. Афонин В.А., Голембиовский Д.Ю. Модели вероятностного компактного тестпрования дискретных устройств//Методы синтеза и планирования развития структур крупномасштабных систем. Тез. докл. II Бсесоюз. совещания-семинара. Саратов,- 1986.-С. 43-44.

2. Афонин В.А., Голембиовский Д.Ю. Вероятностный контроль конечных автоматов методом контрольных сумад//Макропроцессорная техника, техническая диагностика и структуры систем управления. Саратов.- 1987,- С. 58-64.

3. Афонин В.А., Голембиовский Д.Ю. Финальные вероятности состояний сдвигового регистра при сигнатурном анализе конечного автомата//Автоматика и телемеханика.- 1988.- ЩО.- С. 178-183.

4. Афонин В.А1, Голембиовский Д.Ю. Аналитические зависимости вероятности необнаружеш:я неисправности дискретного устройства от длины псевдослучайной тестовой последовательности//!©!!.- ■ 1.1., 1987.- 15с.- Деп. в ВИНИТИ 10.08.87, К 5778-В87.

5. Голембиовский Д.Ю. Метод оценки достоверности вероятностного тестирования комбинационных устройств//Методы и системы технической диагностики. Саратов, 1988.- вып.9.- С. 140.

6. Голембиовский Д.Ю. Некоторые подходы к оценке достоверности встроенного псевдослучайного тестирования БИС/МЭИ - М., 1988.- 12с.- Деп. в ВИНИТИ 2S.07.88, В 60П-В88.

подписано к печати 25.ЮЖ Л-'ПОМОГ' Уч.-изд. л. 1,0 печ.л./,25

Заказ -^'-^Изл. номер А кб Тираж 100 Бесплатно Типография издательства МЭИ, Красноказарменная, 13.