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

15.1 Метод обратного просматривания

Рассмотренные методы моделирования неисправностей требуют значительных вычислительных ресурсов. В приближенных методах оценка полноты теста основана на неявном анализе неисправностей по результатам моделирования только исправной схемы. Такой анализ требует существенно меньше вычислительных ресурсов. В [15.1,15.2] предложен метод моделирования неисправностей, в котором оценка полноты теста выполняется за два прохода.

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

Здесь сначала производится моделирование исправной схемы, в процессе которого каждая линия схемы получила двоичное значение 0 или 1. Далее выполняется обратная фаза от внешнего выхода схемы по направлению к внешним входам. При этом расставляется признак (на рис. 15.1 символ *), показывающий проверяемость одиночных константных неисправностей на соответствующих линиях схемы. В результате процедуры обратного прослеживания активизированные пути отмечаются символом *. Очевидно, на данном тестовом наборе проверяются константные неисправности, имеющие противоположное значение на активизированных линиях. Для данного примера проверяются неисправности: $$х_{4}\equiv 1$$, $$х_{11}\equiv 0$$, $$х_{10}\equiv 0$$, $$х_{15}\equiv 0$$, $$х_{17}\equiv 0$$. При определении активизированных путей часто используется техника критических кубов [15.3].

(рис 15.1) Обратное просматривание.

При выполнении обратного прохода узлы разветвления требуют специальной обработки, что показано на рис. 15.2. Основная проблема заключается в расстановке * на узле разветвления, если хотя бы одна из его ветвей имеет *. Например, возникает проблема - ставить или не ставить * на узле $$х_{2}$$ если ветвь $$x_{21}=1^*$$. Следует отметить, что константная неисправность на линии $$х_{21}$$ не эквивалентна константной неисправности $$х_{12}$$ (узел разветвления). Прямая проверка показывает, что $$х_{2}\equiv 0$$ не проверяется из-за так называемого явления компенсации влияния неисправности по нижнему пути в схеме ($$х_{2}, х_{12}, х_{5}, х_{6}$$). Если же подать на вход $$x_{3}=0$$, то неисправность $$x_{2}\equiv 0$$ становится проверяемой. Обработка узлов разветвления может выполняться различными способами.

(рис 15.2) Обратное просматривание в схеме с разветвлением

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

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

15.2 Статистический анализ неисправностей.

Статистический метод STAFAN [15.4,15.5] позволяет получить оценку полноты тестовой последовательности без моделирования всех неисправностей. Он использует данные, полученные при логическом моделировании исправной схемы, и позволяет приблизительно найти вероятность обнаружения неисправностей. В течение моделирования собирается статистика данных моделирования на внутренних линиях схемы. Для каждой линии схемы вычисляются следующие характеристики:

$$с1(n)$$ - управляемость линии $$n$$, т. е. вероятность появления на этой линии единицы на случайно выбранном входном наборе;

$$c0(n)$$ - 0-управляемость линии $$n$$, вероятность появления на линии значения 0 на случайно выбранном входном наборе;

$$В_{1}(n)$$ - 1-наблюдаемость линии $$n$$, вероятность наблюдения линии $$n$$ на внешнем выходе схемы при значении $$n =1$$ (фактически условная вероятность активизации пути от линии $$n$$ до внешнего выхода схемы при $$n =1$$);

$$В0(n)$$ - 0-наблюдаемость линии $$n$$, вероятность активизации пути от линии $$n$$ до внешнего выхода линии схемы при $$n =0$$.

Для каждой линии схемы определим два счетчика. Первый 0-счетчик предназначен для подсчета нулевых значений на данной линии в процессе моделирования и 1-счетчик для подсчета единичных значений. Когда в процессе моделирования данная линия принимает значение 0 (1) , то ее 0 (1) -счетчик увеличивается на единицу. Если значение сигнала на линии неопределенное $$u$$, то счетчики не изменяются. Если на линии $$n$$ получается значение, соответствующее высокому импедансу, то обычно увеличивается значение того счетчика, чье значение изменялось в последний раз.

После логического моделирования исправной схемы на $$N$$ входных наборах значения 1-управляемости и 0-управляемости можно определить следующим образом:

$$ c_1(n) = \cfrac{1-счетчик}{N}\\ c_0(n) = \cfrac{0-счетчик}{N}$$

Фактически 0-управляемость характеризует частоту (вероятность) установки данной линии схемы в нулевое значение, а 1-управляемость соответственно в единичное.

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

$$S(n)=\cfrac{счетчик-активизации}{N}$$

В начале моделирования значения наблюдаемости полагаются равными $$В_{1}(n) = В_{0}(n) = 1.0$$. для всех внешних выходов схемы. Значения наблюдаемости остальных линии схемы последовательно вычисляются, двигаясь от выходов схемы к ее входам, с помощью специальных формул. Рассмотрим их на примере вентиля И с распределением сигналов, показанным на рис.15.3.

(рис 15.3) Вычисление наблюдаемости входа вентиля.

Проблема состоит в том, как по данному значению 1-наблюдаемости $$В_{1}(m)$$ выхода вентиля И получить 1-наблюдаемость его входа $$В_{1}(n)$$. Для этого используем формулу Байеса:

$$ c1(m)= Prob(i=1, j=1, k=1, n=1) = Prob(i=1, j=1, k=1 / n=1)*c1(n) $$

Из этого выражения получаем:

$$ Prob(i=1, j=1, k=1 / n=1)=\cfrac{c_1(m)}{c_1(n)}$$

Поэтому:

$$ B1(n)=B1(m)= Prob(i=1, j=1, k=1 / n=1)= \cfrac{B1(m)*C_1(m)}{C_1(n)}$$

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

Далее найдем выражение для расчета 0-наблюдаемости этого же вентиля И.

Поскольку $$S(n)$$ - вероятность активизации входа $$n$$, то

$$ S(l) = Prob(i=1, j=1, k=1) = Prob(i=1, j=1, k=1, n=1) +Prob(i=1, j=1, k=1 / n=0) * C0(1).$$

Отсюда следует:

$$ Prob(i=1, j=1, k=1 / n=0)=\cfrac{S(n)-C1(n)}{C0(n)},\\ B0(n)=B0(m)* Prob(i=1, j=1, k=1 / n=0)$$

Окончательно получаем следующую формулу для вычисления 0-наблюдаемости.

$$B0(n)=B0(m)\left [\cfrac{S(n)-C1(m)}{C0(n)}\right ]$$

Таким образом, 0-наблюдаемость входа $$n$$ вычисляется, исходя из значений 0-наблюдаемости выхода $$m$$, значения счетчика активизации этого входа $$S(n)$$ и двух значений управляемости $$C_{0}(l)$$ и $$C_{1}(m)$$ (0-управляемость и 1-управляемость выхода).

Аналогично можно получить формулы вычисления 0-, 1- наблюдаемости для:

вентиля ИЛИ

$$ B1(n)=B_1(m) \left [\cfrac{S(l)-C0(m)}{C1(l)} \right ],\\ B0(n)=B_0(m) \cdot C0(m) / C1(n),$$

вентиля НЕ-И

$$ B1(n)=B0(m)\cdot C0(m) / C1(n),\\ B0(l)=B1(m)\left [\cfrac{S(l)-C0(m)}{C0(n)} \right ], $$

вентиля НЕ-ИЛИ:

$$ B1(n)=B0(m)\left [\cfrac{S(n)-C1(m)}{C1(n)} \right ], \\ B0(n)=B1(m)\cdot C1(m) / C0(n),$$

вентиля НЕ:

$$ B1(n)=B0(m),\\ B0(n)=B1(m),$$

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

(рис 15.4) Вычисление наблюдаемости для узла разветвления.

При этом известны значения 0- (1-) наблюдаемости на ветвях разветвления $$i$$, $$j$$. Требуется определить значение 0- (1-) наблюдаемости в узле $$n$$. Очевидно, так как линия $$n$$ может наблюдаться только через линии $$i$$, $$j$$, то:

$$В1(n)>=B1(i)$$, $$В1(n)>=B1(j)$$ и $$B1(n)>=max[B1(i),B1(j)]$$.

Если пути наблюдения линии $$n$$ через линии $$i$$ и $$j$$ независимы, то:

$$ В1(n)=B1(i)\cup В1(j)=B1(i)+ В1(j) - B_{1}(i)В_{1}(j).$$

В общем виде имеет место следующая оценка

$$ max{[B_1(i);B_1(j)]}\le B_1(l)\le\bigcup\limits_{k=i,j}{B_1(i_k)}$$

Для многих ветвей разветвлении эта оценка имеет следующий вид

$$ max{[B_1(i_k)]}\le B_1(l)\le\bigcup\limits_{k=1}^m{B_1(i_k)}$$

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

$$B_1(n)=(1-\alpha)max[B_1(j_k)]+\alpha[\bigcup\limits_{k=1}^{m}{B_1(j_k)}]$$

Здесь $$j_{k}$$ обозначает ветвь разветвления узла $$n$$. При $$\alpha =1$$ значение $$B1(n)$$ наблюдается независимо через каждую ветвь разветвления и поэтому наблюдаемость определяется суммой значений наблюдаемости этих ветвей. При $$\alpha =0$$ значение $$B1(n) $$наблюдается сходящиеся ветви разветвления и поэтому значение $$B1(n)$$, по крайней мере, не меньше максимального значения наблюдаемости отдельной ветви.

До сих пор мы неявно предполагали, что обрабатываются комбинационные схемы. В последовательностных схемах при вычислении наблюдаемости есть проблемы с обработкой линий обратной связи. Они могут быть решены с применением полученных расчетных формул, но требуют дополнительных усилий [15.4,15.5].

Далее рассмотрим оценку вероятности обнаружения неисправности. Для проверки одиночной константной неисправности $$n=1$$ надо подать на эту линию значение 0 и обеспечить распространение влияния неисправности до внешнего выхода схемы. Поэтому вероятность проверки константной неисправности $$n \equiv 1$$ можно оценить с помощью совместной вероятности установки линии $$n$$ в 0 и наблюдения на внешнем выходе:

$$D1(n)=C0(n)\cdot B0(n)$$

Аналогично для констатной неисправности $$n \equiv 0$$ вероятность ее проверки можно оценить с помощью

$$D0(n)=C1(n)\cdot B1(n)$$

Таким образом можно найти для каждой неисправности ее вероятность обнаружения на данном одном тестовом наборе. Далее необходимо оценить вероятность обнаружения неисправности на всех $$N $$ наборах проверяющего теста. Пусть $$x$$ обозначает вероятность проверки данной неисправности на одном тестовом наборе (определяется $$D1(n)$$ или $$D0(n)$$ в зависимости от типа неисправности). Тогда вероятности проверки этой неисправности на тестовой последовательности из $$N$$ входных наборов можно оценить по известной формуле:

$$X(N)=1-(1-x)^N$$

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

$$W(x)=1-\cfrac{N-1}{6}\beta^2\cfrac{x}{1-x}$$

Здесь $$\beta$$ - коэффициент пропорциональности, который определяется эмпирически. С учетом корректирующего фактора вероятность проверки неисправности $$x_{i }$$ тестовой последовательностью , содержащей $$N$$ входных наборов, определяется следующим выражением:

$$ f_i(N)=1-\prod\limits_{m=1}^{N}{\cfrac{(1-x_{im})}{W(x_{im})}}$$

Если вероятность проверки каждой неисправности на $$N$$ наборах известна, то интегральная полнота для всех $$k$$ неисправностей и $$N$$ тестовых наборов можно определить следующей формулой

$$ F(N)=\cfrac{1}{K}\sum\limits_{i=1}^{K}{f_i(N)}$$

Анализ этой процедуры показывает, что она имеет линейную сложность, т.е. сложность пропорциональна $$N$$, в отличие от предыдущих, со сложностью пропорциональной $$N^{2}$$. Этот метод является приближенным. Авторы данного метода провели экспериментальное сравнение с результатами детерминированного моделирования неисправностей [15.5] схемы 64-разрядного АЛУ с 4376 неисправностями. Проверяющий тест из 155 наборов согласно данным детерминированного моделирования с неисправностями дал полноту проверки неисправностей 75.09%. Затем было проведено статистическое моделирование неисправностей, по результатам которого неисправности ранжированы по значениям вероятности проверки. Исходя из полноты 75.09% 3286 неисправностей, имеющих большие значения вероятности проверки считались обнаруженными, а оставшиеся 1090 неисправностей признаны непроверенными. Из этих 1090 неисправностей 1036 неисправностей не проверялись и детерминированном моделировании. Из3286 неисправностей, проверяемых по данным STAFAN, все, кроме 46 неисправностей, проверялись и детерминированным методом. В експериментах использовались следующие значения параметров: $$\alpha =1$$ (независимые пути разветвления) и $$\beta^2/6=5.0$$, которые дали хорошое совпадение с данными детерминированного моделирования.

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

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

15.3.1 Полнота теста

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

$$P_u=\cfrac{m}{N}\cdot 100%$$, где $$m$$ - число проверяемых неисправностей;

$$P_u=\cfrac{m+m_u}{N}\cdot 100%$$, где $$m_{u}$$ - число условно проверяемых неисправностей, $$N $$- общее число неисправностей схемы.

Очевидно, что для более точной оценки следовало бы вместо $$N$$ использовать $$N_{t}$$ - число тестируемых неисправностей. Здесь $$N_{t}=N-N_{r}$$, где $$N_{r}$$ - число нетестируемых (избыточных) неисправностей. К сожалению, $$N_{r}$$ не всегда просто определить. Если до моделирования производилось сокращение списка неисправностей, то, очевидно, каждая из моделируемых неисправностей представляет класс эквивалентных неисправностей и это желательно учитывать при определении полноты теста. Отметим, что поскольку модели неисправностей представляют не все физические дефекты, то тест даже с полнотой $$P=100%$$ может проверять не все физические дефекты. Кроме полноты теста $$P$$ важнейшей информацией является список непроверяемых данным тестом неисправностей. Этот список может быть использован, например, для улучшения тестовой последовательности в методах генерации тестов и т.п. Кроме этого, часто по результатам моделирования неисправных схем строятся словари неисправностей для локализации дефектов в схеме.

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

Ключевые термины:

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

Статистический анализ неисправностей - определение вероятностей проверки неисправностей на заданном тесте.

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

Краткие итоги

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

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

В разделе 15.2 рассматривается статистический метод определения полноты теста, основанный на вычислении вероятностей проверки неисправностей по статистическим данным логического моделирования исправной схемы.

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

Вопросы и упражнения

Какие этапы имеет метод обратного прослеживания?

Что выполняется на первом этапе этого метода?

Какие действия производятся на втором этапе этого метода?

Что означает символ '*' в обратном прослеживании?

Как обрабатываются узлы разветвления при обратном прослеживании?

Определите проверяемые одиночные константные неисправности методом обратного прослеживания на прилагаемой схеме 15.4. (рис 15.4) Схема для упражнения 6.

Какие счетчики используются в методе STAFAN.

Как вычисляется 0- (1-) управляемость?

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

Выведите формулу для вычисления 0- (1-) наблюдаемости входа вентиля ИЛИ.

Выведите формулу для вычисления 0- (1-) наблюдаемости входа вентиля НЕ-И.

Как вычисляется вероятности проверки данной неисправности на одном тестом наборе?

Как вычисляется вероятность проверки данной неисправности на всей тестовой последовательности?

Как вычисляется интегральная полнота теста?

Что определяет условная и безусловная полнота теста?

Какой смысл имеет один элемент матрицы словаря?

Зачем нужен диагностический словарь?

Как процесс диагностирования зависит от используемого тестового оборудования?