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

научно - исследовательский центр

электронной вычислительной техники

НА правах рукописи УЛК 681.323

френкель сергеи лазаревич

вероятностный ыетод оценки полноты тестов контроля цифровых устройств

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

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

Москва - 1994

Работа выполнена в ГШП "Импульс" (г. Москва),

Консультант:

- кандидат технических наук,

ст. научный сотрудник Святский ' .А.

Официальные оппоненты:

- доктор технических наук, профессор Татарников ..Ю.Д.

- кандидат„технических наук, доцент Кривошапко в. 11.

Ведущее предприятие: ИНЭУМ, г. Москва

Защита состоится "-"-;—1994г. в —г- часов

на заседании специализированного совета Д1Х5.01.01. НИЦЭВТ Москва, 113405

С диссертацией иоано ознакомится в библиотеке НИЦЭВТ

Автореферат разослан "■

•1994г.

Ученый секретарь специализированного совета Д115.01.01. доктор;технических наук, профессор

Кузин Е.С.

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

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

Цель работа. Основной целью выполненной работы является:

-Сравнительный анализ вероятностных методов оценки полноты тестов контроля цифровых устройств;

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

-исследование сходимости вычислительных процедур, лежащих в основе вычисления вероятностей, обнаруаения неисправностей по результатам: моделирования исправных Схем,-;',

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

повысить эффективность использования вероятностных методов оценки полноты, базирующихся на результатах моделирования исправных схем, & именно)

* 1

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

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

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

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

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

Научная новизна результатов состоит в следующем

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

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

последовательности;

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

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

- выявлены и описаны различные Факторы { в терминах структурно-Функциональных свойств вентильных сетей), влияющие на точность вероятностной оценки полноты, и на

точность построения списка необнаруженных неисправностей!

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

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

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

существенно повышающей его эффективность, а такге в реализации на основе полученных результатов программных средств, использованных • при построении тестов контроля ряда изделий, разрабатываемых и выпускаемых в ГНПП " Импульс" а 1985г1991гг.. а такяе на ряде других предприятий.

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

Республиканская научно-техническая конференция "Автоматизация проектирования средств вычислительной техники и радиоэлектроники". Каунас, июнь, 1985.'

- Отраслевой семинар "Автоматизация средств контроля и диагностики РЭА", Иосква. декабрь. 1987г..

- Всесоюзный семинар "Опыт и практическое использование систем автоматизированного проектирования (САПР)", Москва. 2426 сентября, 1987г..

-Зональная конференция "Математические и программные методы проектирования информационных и управляющих систем", Пенза, 2S-29 мая, 1990г..

- Конференция по автоматизации проектирования "АРКЭ1". .Каунас З-б июня, 1991г.

2nd International Design Automation Workshop

( "Russian WorJtshop92") . Moscow. June 29-30. 1992.

("Russian Workshop93") , Moscow, July 19-20, 1993, а также на семинарах в ГНПП "Импульс", ИЛИ РАН.

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

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

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

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

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

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

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

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

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

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

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

- структурно ,- Функциональные методы, в которых

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

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

-s-

Функцию, и при этом учитываются некоторые топологические особенности вентильной сети;

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

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

На основании выполненного анализа рассмотренных методов делается вывод, что указанным выше критериям выбора метода оценки полноты в наибольшей степени удовлетворяют методы, основанные на оценке полноты тестов по результатам моделирования исправной схемы. В данных методах вычисление полноты контроля заданным тестом выполняется по значениям оценок вероятностей обнаружения неисправностей, впервые предложенных авторами статистического метода оценки полноты STAFAN (Statistical Fault Analysis). Вгдиссертации эти оценки названы STAFAN-оценками соответствующих вероятностей. Используются следующие STAFAN-оценки:

- Cz(m) - оценка вероятности установки линии m вентильной сети в логическое значение z-О или 1 соответственно. Эта величина называется О или 1- управляемостью линии т.

Bz(m)- оценка условной вероятности создания существенного пути для логического значения z на линии ш на случайно выбранном наборе тестовой последовательности. Bz(m) называется 0 или 1-наблюдаемостью линии т.- Dz<m)-Cz(m)Bz(fti) - оценка вероятности обнаружения неисправности m/z на случайно выбранном в исследуемой тестовой последовательности входном наборе, где т-линия вентильной сети, z - логическое значение, соответствующее данной константной неисправности("константа О"

или "константа 1"). z- инверсное логическое значение;

- Xztm)- вероятность обнаружения ОКН m/z хотя бы на одном наборе тестовой'последовательности;

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

1

fc- -Е Xz(m) (1).

NF <m,z>

где <m,z> - множество неисправностей из - рассматриваемого списка одиночных константных неисправностей в схеме. NF-число данных неисправностей в схеме.

Величина Cz(m) вычисляется непосредственно по результатам моделирования схемы, Bz(m) - через величины Cz(m) и S(m)-оценку вероятности активизации пути со входа га вентиля на его выход. При этом алгоритм вычисления Bz(m) представляет собой обратный проход с выходов сети ко всем линиям схемы, с вычислением на каждом шаге значений наблюдаемости входа m вентиля по известным значениям наблюдаемости выхода вентиля и значониям Cz(m),,S(m). Наблюдаемость Bz(f) любого выхода f сети считается равной 1..при Cz(f)>0 , и равной О при Cz(f)=0.

Основываясь на результатах анализа современных

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

следующие группы вопросов:

- Формализация оценки точности методов, основанных на STAFAN-оценках вероятностей;

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

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

В главе 2 изучаются математические свойства STAFAN-оценок, Н их связь с различными характеристиками схем и

тестовых последовательностей.

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

Показано. . что используемая в STAFAN методика, вычисления Bz(m) не приводит' к вычислению условной вероятности наблюдаемости линии т, т.е. условной вероятности того, что для всех вентилей пути выполняются условия очувствления на входном наборе, на котором линия m установлена в проявляющее для неисправности m/z значение. Из этого результата следует вывод, что погрешность вычисления z-наблюдаемости Bz(m) имеет модельный характер.

В связи с получанным результатом. ставится вопрос о критериях оценки точности STAFAN-оценок и рассматриваются возмогшие подходы к выбору критерия качества. Показывается нецелесообразность использования принятых в математической статистике характеристик достоверности для исследования эффективности STAFAN - оценок. Показано, что применимость STÄFAN-oöeiiKK для конкретной неисправности удобно охарактеризовать с помощью следующего понятия:

STAFAN- оценка адекватна для неисправности m/z, если:

а) Dz(m)>0 и ni/z обнаруживается на исследуемом тесте.•

или

б) Dz(m)-0 и m/z не обнаруживается на исследуемом тесте. Свойства STAFAN-оценок для неисправностей участков схем с различными Функциональными • и структурными характеристиками изучаются с - точки зрения их влияния на адекватность( в указанном смысле). Показывается, что если на исследуемом тесте для неисправности m/s на линии m древовидной сети вычислено значение Dz(m)-0. . то данная неисправность кепроверяема на тесте, т.е. нулевая STAFAN-оценка Dz(m) адекватна для данного класса непроверяемых неисправностей. При этом ненулевые значения STAFAN-

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

2.Показано, что для неисправностей в узлах сходящихся разветвлений адекватность "" STAFAN-оценок в общем случае определяется распределением логических значений в их ветвях на входных наборах исследуемой тестовой, последовательности. что связано с хорошо известными явлениями "самомаскирования неисправностей" (self-marking" (SM)), и многомерного, пути распространения ("multiple path propagation" (МРР)). При этом явление самомаскирования приводит к неадекватности STAFAN-оценок для необнаруживаемых неисправностей в узле сходящегося разветвления, а ММР - к их неадекватности для обнаруживаемых на исследуемом тесте неисправностей.

3. Рассматривалась применимость STAFAN-оценок для неисправностей на линиях участков вентильных сетей с обратными связями. ( максимальных сильносвязных подсетей -МССП ). В этом случае проблема применимости возникает уже на уровне структуры „ события, соответствующего проверяемости неисправности. Дело в том. что в общем случае данное событие в последовательностной схеме может быть представлено только на некоторой последовательности наборов теста, в то время как Dz(m) вычисляется как вероятность создания существенного пути для .неисправности на случайно выбранном •из входной последовательности) наборе. Тен, не менее. как

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

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

Фиксирующий реаим запоминания наборы, алгоритм ЭТАГАИ приводит к вычислению адекватных ЭТАКЛИ-оценок для неисправностей на контурных линиях.

Возмоаность получения адекватных ЭТАГАИ - оценок - для неисправностей в схемах с памятью обеспечивается также обнаруяиваемостыэ некоторых неисправностей внешних входов элементов контуров на однотактных последовательностях.

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

4.Рассмотрен вопрос о точности вычисления Хг(т)- вероятности проверяемости неисправности хотя бы на одном наборе теста. Исследуется правомерность предлояенной в БТАГАМ модели представления погрешности, как смещения оценки вероятности хотя бы одного успеха а последовательности независимых испытаний.

Показывается возможность интерпретации вероятности Ъг (гп) , как вероятности успеха в указанной последовательности испытания. и правомерность используемой авторами ЗТАГАИ аппроксимации выражения для оаибки смещения. Ввиду того, что вероятность Ог(т) вычисляется в ЭТАТ^И в рамках соответствующей вероятностной модели, а не " оценивается по результатам

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

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

Задача Формулируется следующим образом: выбрать пороговое значение q вероятности Xz(m) таким образом, чтобы обеспеченить минимальные вероятности следующих ошибок:

а) "ud->d" - . ошибки отнесения необнаруживаемой на тестовой последовательности OICH к проверяемой, при применении порогового правила:

ОКН m/z обнаруживается на данном тесте, если Xz(m)>q,

(2)

ОКН m/z не обнаруживается на данном тесте, в противном случае;

б) "d->ud"~ ошибки отнесения обнаруживаемой ОКН к необнаруживаемой, при применении указанного порогового правила. Делается вывод, что . для решения данной задачи необходима модификация метода STAFAN.

Выполненный в главе 2 анализ адекватности STAFAN-оценок является основой для оценки точности решения задачи интерактивного построения тестов с использоьгчием вероятностного метода оценки полноты.

В глава 3 исследуются вопросы сходимости процесса вычисления STAFAN - оценок для сетей с обратными связями. Показывается, что задача вычисления z-наблюдаемостей линий ИССП по алгоритму STAFAN вквивалентна решению системы нелинейных уравнений с L-I уравнениями, где L- число элементарных контуров в ЫССП, I- число элементов в пересечении многеста линий НССП. являющихся выходами элементарных контуров. Исследуются свойства правых частей уравнений, определяющих сходимость итераций. Доказано следующее свойство решений:

При любых начальных условиях из [0,1]. итерации сходятся к

вектору решения х-{х(1).х(2).....х(к)), где к-число строк в

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

справедливо; _ .

х £i) < x(i) i x1(i).

где х®(1)- 1-я координата вектора, к которому сходится решение при нулевом начальном приблияении (т.е.нулевых

начальных значениях всех переменных). х1 (1)

соответственно, при единичном начальном приблигенин. Доказана сходимость итерационного процесса с вероятностьв 1 к единственному решению при любых начальных приблиаениях из [0.1]. при единичном значении эмпирического коэффициента а . учитывающего в БТАГАН степень зависимости событий, связанных с активизацией простых путей, образующих узлы разветвлений в рассматриваемой сети (значение а=1 соответствует предполовению об их независимости ). Полученные результаты показывают принципиальную возмоаность использования БТАГДЛ-оценок для произвольных схем с памятью. При зтом отмечается, что скорость сходимости итераций для слозных контуров моает быть довольно медленной, и зависит от организации итерационного процесса. Это обстоятельство указывает на актуальность задачи повышения быстродействия вычислений етАРАН-оценок, решение которой излагается в главе 5. '

В Главе 4 • исследуется влияние различных Факторов на точность ^оценки полноты контроля по результатам моделирования исправной схемы с использованием ЗТАГАЫ -оценок. Погрешность БТАГАЫ- оценки полноты представляется следующим образом: Л-^С — Е в (ш\г) +Е в (т/2)) - Е<1+Еи (3)

т/геГ<1 т/геГи

где:

в(т\г)- погрешность; вносимая в суммарную

погрешность оценки полноты (относительно точного значения, которое могло бы быть вычислено по результатам моделирования схемы с неисправностями) значением вероятности Хг(т) кавдой из неисправностей тЧг в Формуле оценки полноты (1). Рс1-мнояество обнаруживаемых на тесте неисправностей, Ги- множество необнаруаиваемых неисправностей. Ес1- суммарная погрешность, вносимая оценками Хг(т), вычисленными для обнаруживаемых неисправностей. Ей- суммарная погрешность, вносимая в оценку полноты значениями Хг(т). вычисленными для необнарузиваемых неисправностей.

Слагаемые в (3) иогут вносить как положительный, так и отрицательный вклады в оценку погрешности. Соответственно.. структурно-Функциональные свойства участков сети, определяющие адекватность БТАГАЛ- оценок для неисправностей на принадлеяащих им линиях, и математические свойства ЭТАКАН-оценок могут характеризоваться согласно знаку погрешности, вносимому в (3) соответствующим слагаемым •.

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

"несинхронность" (в комбинациои-. ных и последова-тельностных схемах) +

"Самомаскирование" в узле схрд.разветвления +

"множественный путь распространения" -

неисправности в контурах.проверяемые на установочных наборах -

смещенность оценки Хг(го). -

Взаимная компенсация вкладов в погрешность й выражении (3) является одной из причин, обеспечивающей высокую точность ЗТАГАЫ-оценки полноты, несмотря на то. что используемая вероятностная модель во многих случаях противоречит логическим условиям очувствления комбинационных ' и последовательностей* путей. Другая причина состоит в , том, -что ряд Факторов, определяющих данное противоречие, проявляется крайне редко в реальных схемах на реальных тестах. Прежде всего. это относится к явлениям "самомаскирования" и "многомерного пути распространения" в узлах сходящихся разветпленип. Делается вывод, что отмеченный компенсационный характер точности оценки полноты может приводить к ошибкам при решении второй подзадачи общей задачи построения тостов -

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

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

обоснована возможность использования единичного значения коэффициента в, а такае получено уравнение для. выбора величины эмпирического коэффициента, используемого для уменьшения ошибки смещения при оценке вероятности Xz(m).

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

1. Воэмоаность расширение базиса сетей основана на

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

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

реализующего булеву Функцию п переменных F(х,...,х ). где i- вход, соответствующий переменной Xj:

I D(x.-z) | PiSx^x^-z)- —!----

F

(z)|

где Sxj- событие, состоящее в очувствлении пути со входа х4при наличии на нем логического сигнала z на выход модуля,

DlXj-z)- множество входных наборов, на которых.

Fix,.... (x.-z)e 1,...х )-/=F(x.____(x.-z),..x_).

1 1 П 1 1 n

F (z) - множество входных наборов, на которых х =z. i i

9 -слоаение по Mod 2.

Данный подход использован . для сетей, . ■ содерзащих помимо элементарных вентилей, такзе и элементы И-ИЛИ-НЕ, ИСКЛЮЧАОТЕЕ ИЛИ. При этом вычислительные затраты по сравнению со случаем преобразования данных компонентов в сеть элементарных вентилей не возрастают. Полезность такой доработки объясняется тем. что данные элементы, как правило, содержатся в доступных разработчику тестов Функциональных

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

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

Показывается, что итерационный характер вычислений z-

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

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

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

В главе 6. рассматривается возможность о"основанного

построения списка необнаруженных неисправностей по информации, получаемой при моделировании исправной схемы.. При этом используется тот Факт, что практически вычисление ЭТАГАН-оценок выполняется по интервалам, на которые разбиваются тестовые последовательности, т.е. на каждом интервале с номером 1 длиной N1 входных наборов вычисляются свои величины Сз:(т.1), ВгСтЛ), СиСтЛ). . 1-1,к, где к- число интервалов, и вероятность Хг(т) вычисляется, как:

^ (1-0г(т.Шт

Хг (1) - 1-: П -:-

1-1 и(№.02(т.1})

где И(...)-■поправочный множитель, зависящий от. значений Ш и Эг(гз.) на 1-т интервале, а также от некоторого эмпирического коэффициента Ь, выбор которого рассмотрен в, главе 4. поправочный множитель вводится с целью уменьшения ошибки смещения оценки данной вероятности. Заметим, что длины интервалов разбиения берутся одинаковыми. Приведенная Формула определяет наличие следующего свойства у БТАРДЫ-оценки вероятности Хг(га):

значения Хг(т)>0 тогда и только тогда, когда хотя бы на одном из интервалов 1 разбиения тестовой последовательности В2(ш,1)>0. Показывается, что для неисправности на' линии

дрезовидной сети, из данного свойства следует, что уменьшая вероятность события "Иг(т.1)>0", уменьшается вероятность ненулевого значения Хг(т) для ' необнарувиваемой на данном тесте неисправности. При этом веротность ошибки <1->и<1 не возрастает. Показывается, что ввиду невозмояности оценки с приемлемой точностью различных условных распределений вероятностей для ошибок иа-М. с!->ис1, необходимых для строгого ( с точки Зрения математической статистики) решения задачи выбора порога в пороговом правиле (2). предпочтительный путь решения задачи построения, списка необнаруяенных неисправностей состоит в следующем:

-использовать нулевой порог в правиле 2). т.е. счйтать

неисправность обнаруаиваемой. если Х2(ш)>0, и необнаруаиваемой - в противном случае,-

длину интервала N1 выбирать исходя из условия ограничения вероятности ошибки иЛ-'М (при я»0)-. оценка сверху которой может быть выражена через значения у(;П- частоты активизаций путей

череэ каждый из вентилей J. входящих в состав простых путей, проходимых при реализации алгоритма STAFAN. При этом для неисправностей древовидных участков сети гарантировано отсутствие онибки типа d->ud.

Снижение вероятности овибки ud->d достигается уменьшением интервала N1. В этом случае, однако, для неисправностей на линиях, принадлежащих нноготактным последовательности!»! подсхемам возможно появление ошибки типа d->ud, если Ni < td, где td -минимальное число тактов входной последовательности, которое необходимо для создания существенного пути для рассматриваемой неисправности.

В случае же комбинационных схем. время вычислений STAFAN-оцёнок увеличивается с , ростом числа сегментов ]T/Ni[ разбиения теста, что также может рассматриваться как условие ограничения снизу длины интервала. Предложена методика компромиссного выбора величины N1.

Опибка ud->d при использовании нулевого порога однозначно определяется долей необнаруживаемых на исследуемом тесте неисправностей, для которых были вычислены ненулевые значения Xz(m). Таблица 1. показывает влияние длрны интервала Ni на долю непроверяемых ОКН. с ненулевыми Xz(m):

Таблица 1.Зависимость числа ошибок ud->d и точности вычисления полноты от длины интервала разбиения теста.

схе- тип СХе-

ма ♦NF ♦ud->d Ni; |Т| t/to МЫ

SS

642 146 50 1054 1 -4.1

1 28 80 1.75 -4.9 последов,

1 28 20 4.9 -5.3

1750 32 .139 139 1 - 0.9

26. ■80 1.4 -1.1 комбинац

28. 20 1-9 -1.1

з ■ 1307 132 294 294 -,1 • ' +2.1

46 80 >2.1 +2.4 последов

34 20 1.7 -3.1

Здесь: tud-M-число необнаруженных неисправностей с Xz(m)>0. при данном Ni,

| Т | -длина тестовой последовательности,

N1- длина интервала разбиения тестовой

последовательности,

t/tO - относительное увеличение времени оценк1 полноты относительно времени оценки при |Т|/Ш-1,

число неисправностей в схеме, Д(с- относительная погрешность оценки полноты относительно метода параллельного компилятивного моделирования.

На величину относительного увеличения времени оценки полноты влияет не только число интервалов разбиения тестовой последовательности, но и сокращение с уменьшением Ш числа путей, 2-наблюдаемость вдоль которых выше принятого порогового значения. При этом, как показывают полученные данные, число путей моает сокращаться довольно быстро с уменьшением N1, чем и объясняется сравнительно медленное увеличение ^Ъо.

В главе 7 рассматривается программная реализация предложенных подходов к вычислению ЗТАГАЫ-оценок и методология

I *

использования вероятностной оценки полноты при интерактивной разработке тестов. Программы реализованы на языне ПЛ/1. как составная часть программной системы синтеза тестов

контроля цифровых устройств АССТ-ЕС. Данная система является реализацией в среде ОС-ЕС 6.1 на ЭВЫ ЕС-1045 существенно модифицированной (в части входных языков, средств ведения библиотек, а такае возможности иерархического описания схем) широко известной Автоматизированой Системы Синтеза Тестов . ( АССТ ). Подсистема вероятностной оценки полноты

использовалась, наряду с входящим в состав АССТ-ЕС модулем оценки полноты на основе параллельного компилятивного моделирования (ПКЫ) для построения качественных

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

результатов вычисления ЭТАРАМ-оценок позволяет существенно снизить временные затраты на выполнение отдельных шагов

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

не-

полученных (к данному шагу) тестовых последовательностях^

Таблица 2 иллюстрирует снижение затрат машинного времени на оценку полноты, по сравнению с ПКМ, а также с ранее предложенным методом вычисления БТАГАН-оценок, достигаемое благодаря использованию предложенным модификациям. :

таблица '2

N0 ♦а #<ЗГ Тт сек ¿с. '/с А^ (■/с |Т|

а Ь- с Ь с

Г 201 б 2 43 29 23 84.3 -3.2 -2.9 69

б 249 28 в 604 216 165 63 +8.2 -2.1 370

в 374 0 0 184 161 147 97.7 + 1.8 +1.6 139

здесь:

столбцы а, Ь, с-соответствуют ПКЫ. БТАГАМ. и предложенной в диссертации модификации БТАГАИ, Но- условный номер схемы.

♦в- число элементов в схеме(включая И-ИЛИ-НЕ,

ИСКЛЮЧАЮЩЕЕ ИЛИ).

«Ер- число И-Б-триггеров,

«бГ- число глобальных обратных связей.

общие затраты машинного времени. 1 с- полнота контроля построенным тестом. ДГс-погрешность оценки полноты относительно.ПКЫ,• /Т|- число наборов в тестовой последовательности, делается вывод, что накопленный опыт использования ЭТАГАЫ-оценок при интерактивном построении тестов на базе ЭВМ с небольшой (по современным понятиям) производительностью и оперативной памятью, показывает целесообразность реализации данных подходов на ПЭВМ.

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ.

1. Исследована теоретико-вероятностная модель,

соответствующая эвристическим вычислениям вероятностного метода оценки полноты тестов БТАГДЫ. . Показано, что вычисляемые

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

2. Обоснованы критерии адекватности БТАГАЫ - оценок вероятностей обнаружения одиночных константных неисправностей в вентильных сетях.

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

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

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

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

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

8. Разработаны программы, реализующие вычислительную процедуру вероятностной оценки полноты тестов,на основе соответствующим образом модифицированной вычислительной процедуры СТАРА!*, для цифровых устройств, описанных в виде сетей элементарных вентилей и элементов И-ИЛИ(НЕ,ДА). ИСКЛЮЧАЮЩЕЕ ИЛИ. Данное программное обеспеченна включено в состав широко используемой Автоматизированной Системы Синтеза Тестов (АССТ).

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

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕЫЕ ДИССЕРТАЦИИ.

1. Френкель С.Л. Автоматизация поиска неисправностей в цифровых устройствах /У Передовой производственный опыт. 1984. стр.9-12.

2. Френкель С.Л. Подсистена САПР разработки тестов контроля И диагностики неисправностей в цифровых. устройствах на микропроцессорных БИС. // Опыт и практическое использование систем автоматизированного проектирования. Материалы Всесоюзного научно-технического семинара. Москва, 24-26 сентября 1987г.. стр.99-100.

3.Френкель С.Л.. К вопросу об оценке контролепригодности цифровых схем, // Тезисы докладов к Всесоюзному семинару " Измерение и контроль в РЭА".И.:.1987, стр.101-103.

4.Френкель С.Л. Об одном вероятностном методе оценки

полноты тестов контроля цифровых устройств //Методы и средства автоматизации проектирования средств вычислительной техники. Н.:, Тр.ИНЭУН,1988. с.166-173.

З.Гробман Д.Н..Френкель С.Л.. О сходимости итерационного процесса вычисления вероятности событий в логических сетях с обратными связями // Натематические и програмные нетоды проектирования информационных и управляющих систем. Тезисы докладов к зональной конференции, 28-29 мая 1990г., стр.41-42.

6.Френкель С.Л. О возмозности использования вероятностных методов оценки полноты в интерактивных системах синтеза тестов // Конференция по автоматизации проектирования "АРК91", Каунас, 3-6 июня. 1991г., стр. 132-136.

7.Френкель -С.Л.-.- О возможности использования ПЭВМ для решения задач синтеза тестов контроля цифровых устройств // Системы и средства информатики. М.: Наука, вып. 4.1993. стр.283-290.

8.Frenkel S.L. Problem of fault classification by usage of . statistical method of fault coverage for sequential circuits. // Proc.. 2nd International Design Automation