Синтез тестов для заданной неисправности

17. 1 Метод различающей функции

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

Пусть $$f(X)$$ - булева функция, реализуемая исправной комбинационной схемой, а $$\varphi (X)$$ - булева функция, реализуемая неисправной схемой.

Назовем различающей функцией следующее выражение [17.1]:

$$D(\varphi )=f(X)\oplus \varphi (X).$$

Очевидно, что наборы значений входных переменных $$X$$, на которых $$D(\varphi )=1$$, являются проверяющими тестами для данной неисправности $$\varphi $$.

Для примера рассмотрим схему, изображенную на рис. 17.1.

(рис 17.1) Пример схемы для метода различающей функции

Применим метод различающей функции для построения проверяющего входного набора для константной неисправности $$х_{1}\equiv 1$$. В этом случае имеем:

функцию, реализуемую исправной схемой $$f(x)=(x_1\x_2)\vee(x_2\\overline{x}_3)$$;

функцию, которая реализуется неисправной схемой, $$\varphi(x)=x_2\vee(x_2\\overline{x}_3)=x_2$$.

Тогда различающая функция равна: $$D(х_{1}\equiv 1)=f(x)\oplus \varphi(x)= =((x_1\x_2)\vee(x_2\\overline{x}_3)) \oplus x_{2}=x_{2}((x_{1}\vee\overline{x}_3)\oplus 1)=x_2\overline{(x_{1}\vee\overline{x}_3)}=x_2\overline{x}_1x_3$$.

Очевидно, что равенство $$D(x_{1}\equiv 1)=1$$ обеспечивает набор значений входных переменных $$x_{1}=0$$, $$x_{2}=1$$, $$x_{3}=1$$, который и является проверяющим тестом для данной неисправности. Для больших схем этот метод становится слишком громоздким и требует больших вычислительных ресурсов. Однако следует отметить, что современные методы символьных вычислений (над булевыми выражениями) позволяют расширить его возможности.

17.2 Метод булевых производных

Булева производная функции $$f(X)$$ по переменной $$x_{i}$$ определяется следующим выражением: $$\cfrac{df}{dx_i}=f(x_i=0)\oplus f(x_i=1)$$ [17.2]. Существует и другое, эквивалентное приведённому, определение булевой производной: $$\cfrac{df}{dx_i}=f(x_1,\ldots,x_{i-1},x_i,x_{i+1},\ldots,x_n)\oplus f(x_1,\ldots,x_{i-1},\overline{x}_i,x_{i+1},\ldots,x_n)$$ .

Например, для булевой функции $$f=x_1x_2\vee x_2\overline{x}_3$$, булева производная $$ \cfrac{df}{dx_1}= x_2x_3\oplus(x_2\vee x_2\overline{x}_3) = x_{2}(x_{3}\oplus 1) = x_2\overline{x}_3$$ .

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

$$\cfrac{d1}{dx_i}=0, \cfrac{d0}{dx_i}=0$$;

$$\cfrac{d}{dx_i}(\cfrac{df}{dx_i})=0$$;

$$\cfrac{d}{dx_i}(\cfrac{df}{dx_j})=\cfrac{d}{dx_j}(\cfrac{df}{dx_i})$$;

$$\cfrac{d\overline{f}}{dx_i}=\cfrac{df}{dx_i}$$;

$$\cfrac{d}{dx_i}(f\oplus\varphi)= \cfrac{df}{dx_i}\oplus\cfrac{d\varphi}{dx_i}$$;

$$\cfrac{d}{dx_i}(f\cdot\varphi)= f\cfrac{d\varphi}{dx_i}\oplus\varphi\cfrac{df}{dx_i}\oplus\cfrac{df}{dx_i}\cdot\cfrac{d\varphi}{dx_i}$$;

$$\cfrac{d}{dx_i}(f\vee\varphi)=\overline{f}\cfrac{d\varphi}{dx_i}\oplus\overline{\varphi}\cfrac{df}{dx_i}\oplus\cfrac{df}{dx_i}\cdot\cfrac{d\varphi}{dx_i}$$.

Важны следующие частные случаи этих формул для функции $$g$$, не зависящей от переменной $$x_{i}$$:

$$\cfrac{d}{dx_i}(f\oplus g)= \cfrac{df}{dx_i}$$;

$$\cfrac{d}{dx_i}(f\vee g)=\overline(g) \cfrac{df}{dx_i}$$;

$$\cfrac{d}{dx_i}(g\cdot f)=g\cfrac{df}{dx_i}$$;

для $$f=x_1x_2\ldots x_{i-1}x_ix_{i+1}\ldots x_n\\\cfrac{df}{dx_i}= x_1x_2\ldots x_{i-1}x_ix_{i+1}\ldots x_n$$;

для $$ f=x_1\vee x_2\vee\ldots\vee x_{i-1}\vee x_i\vee x_{i+1}\vee \ldots\vee x_n\\ \cfrac{df}{dx_i}= \overline{x}_1\overline{x}_2\ldots \overline{x}_{i-1}\overline{x}_i\overline{x}_{i+1}\ldots \overline{x}_n$$

На практике важным является дифференцирование сложных функций, когда функция $$F$$ явно не зависит от переменной $$x_{i}F = F(f(x_{1},..,x_{i},..,x_{n}),x_{1},..,x_{i}_{-1},x_{i}_{+1},..,x_{n})$$.

В этом случае имеет место $$\cfrac{dF}{dx_i}=\cfrac{dF}{df}\cdot\cfrac{df}{dx_i}$$.

Для булевых функций справедливо следующее разложение Тейлора по переменной $$x_{i}$$ в точке $$x_{i}=h_{i}$$ с использованием булевой производной:

$$f=f(x_i=h_i)\oplus\cfrac{df}{dx_i}(x_i\oplus h_i)$$

Тогда различающая функция неисправности для $$h_{i}$$ может быть представлена следующим образом:

$$D(h_i)=F(x,x_i)\oplus F(x,x_i=h_i)$$, где $$h_{i} =0,1$$.

Используя разложение Тейлора функции $$F$$ по переменной $$x_{i}$$ в точке $$h_{i}$$, получаем:

$$D(h_i)=F(X,x_i=h_i)\oplus\cfrac{dF}{dx_i}(x_i\oplus h_i)\oplus F(X,x_i=h_i)= \cfrac{dF}{dx_i}(x_i\oplus h_i)$$

Здесь второй сомножитель $$(x_i\oplus h_i)$$ даёт условие различения сигналов $$x_{i}$$ и $$h_{i}$$ в исправной и неисправной схеме на линии $$i$$. Первый же сомножитель определяет условие распространения рассогласования сигнала в исправной и неисправной схеме до выхода схемы $$F$$. Это соотношение является основой для метода булевых производных.

Таким образом, для построения теста для константной неисправности $$h_{i}\equiv 0 $$необходимо решить булево уравнение (найти значения входных переменных) $$x_i\cfrac{dF}{dx_i}=1$$, а для неисправности $$h_{i}\equiv 1$$ - уравнение $$\overline{x}_i\cfrac{dF}{dx_i}=1$$.

Рассмотрим метод булевых производных на примере построения теста неисправности $$x_{1}\equiv 0$$ для схемы рис. 17.2. Для построения теста нам необходимо решить уравнение $$x_1\cfrac{df}{dx_1}=1$$.

(рис 17.2) Иллюстрация метода булевых производных

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

$$ \cfrac{df}{dx_1}=\cfrac{df}{dx_8}\cfrac{dx_8}{dx_6}\cfrac{dx_6}{dx_1}\\ \cfrac{df}{dx_8}=\overline{x_9}=\overline{x_7\overline{x_3}}=x_3\vee\overline{x_4}\,\overline{x_5}\\ \cfrac{dx_8}{dx_6}=x_3\\ \cfrac{dx_6}{dx_1}=\overline{x_2}\\ \cfrac{df}{dx_1}=( x_3\vee\overline{x_4}\,\overline{x_5})x_3\overline{x_2}= x_3\overline{x_2}=1\\ x_1\cfrac{df}{dx_1}=x_1x_3\overline{x_2}=1$$

Из этого выражения следует, что набор значений входов $$x_{1}=1$$, $$x_{2}=0$$, $$x_{3}=1$$ является проверяющим тестом для данной неисправности.

Рассмотрим построение теста для неисправности $$x_{7}\equiv 1$$ внутренней линии той же схемы.

$$ \overline{x_7}\cfrac{df}{dx_7}=1\\ \cfrac{df}{dx_7}=\cfrac{df}{dx_9}\cdot\cfrac{dx_9}{dx_7}\\ \cfrac{df}{dx_9}=\overline{x_8}=\overline{x_3x_6}=\overline{x_3(x_1\vee x_2)}=\overline{x_3}\vee\overline{x_1}\,\overline{x_2}\\ \cfrac{dx_9}{dx_7}=\overline{x_3}\\ \cfrac{df}{dx_7}=(\overline{x_3}\vee\overline{x_1}\,\overline{x_2})\overline{x_3}=\overline{x_3}\\ \overline{x_7}\,\overline{x_3}=1\\ \overline{x_4x_5}\,\overline{x_3}=1\\ (\overline{x_4}\vee\overline{x_5})\overline{x_3}=1\\ \overline{x_4}\,\overline{x_3}\vee\overline{x_5}\,\overline{x_3}=1$$

Таким образом, для проверки данной неисправности можно использовать наборы $$x_{4}=0$$, $$x_{3}=0$$ или $$x_{5}=0$$, $$x_{3}=0$$, что следует из последнего выражения для различающей функции.

17.3 Метод активизации одномерного пути

Основная идея этого метода заключается в выборе и активизации пути от места неисправности через последовательность вентилей до некоторого внешнего выхода [17.3]. Этот процесс выполняется в три этапа [17.4]:

Активизация (sensitization) неисправности, при которой на неисправную линию подается сигнал, противоположный неисправному значению.

Распространение (propagation) неисправности от места неисправности до одного из внешних выходов.

Доопределение (justification) необходимых для активизации и распространения значений сигналов.

На втором этапе соседним входам вентилей, вошедших в активизированный путь, присваиваются такие значения сигналов, при которых выход вентиля зависит от входа, входящего в этот активизированный путь. Таким образом, для элементов типа И, НЕ-И соседние входы получают значение 1, а для ИЛИ, НЕ-ИЛИ соседние входы получают значение 0. Иногда этот этап называют прямой фазой, а выбранный путь - активизированным путём.

Выбрав и установив активизированный путь на третьем этапе необходимо найти значения сигналов на внешних входах схемы, которые дают требуемые значения на входах вентилей активизированного пути. Для этого по схеме прослеживаются необходимые значения сигналов до внешних входов схемы. Этот процесс иногда называют обратной фазой. Рассмотрим этот простой метод на примере построения теста для неисправности $$x_{7}\equiv 1$$ схемы, представленной на рис. 6.5.

(рис 17.3) Одномерная активизация путей

Выполняем первый этап - активизацию неисправности. Очевидно, в исправной схеме необходимо получить $$x_{7}=0$$ (значение сигнала, противоположное неисправности), что обеспечивается значением внешнего входа $$x_{3}=1$$. Далее выбираем (произвольно) путь $$x_{7}$$, $$x_{10}$$, $$x_{11}, x_{13}$$ от места неисправности до выхода схемы $$F_{2}$$. Необходимым условием активизации этого пути является равенство значений сигналов соседних входов, обеспечивающих распространение влияния неисправности: $$x_{4}=1$$ для активизации пути от $$x_{7}$$ к $$x_{10}$$; $$x_{5}=0$$ для активизации пути от $$x_{10}$$ к $$x_{11}$$; $$x_{8}=1$$ для активизации пути от $$x_{11}$$ к $$F_{2}$$.

Этим завершается прямая фаза (этап активизации). Далее необходимо найти значения внешних входов схемы, обеспечивающие полученные на предыдущем этапе условия распространения влияния неисправности. В данном случае надо найти значения $$x_{1}$$ и $$x_{2}$$, обеспечивающие равенство $$x_{8}=1$$. Из трех возможных комбинаций выбираем $$x_{1}=1$$, $$x_{2}=0$$. В результате получаем тестовый набор $$x_{1}=1$$, $$x_{2}=0$$, $$x_{3}=1$$, $$x_{4} =1$$, $$x_{5}=0$$. Когда этот набор подается на схему, то выход схемы $$F_{2}=1$$ при наличии неисправности и $$F_{2}=0$$ при ее отсутствии. Следовательно, построенный входной набор действительно является тестовым.

Отметим, что при выполнении этапа подтверждения (обратной фазы) возможен перебор различных вариантов значений входных сигналов и неудачный выбор может привести в дальнейшем к несовместимости полученных значений сигналов на некоторых линиях схемы. В этом случае необходимо "дать задний ход" и выполнить перебор других вариантов до тех пор, пока несовместимость не будет устранена. Таким образом, задача построения теста для заданной неисправности носит переборный характер.

(рис 17.4) Контрпример для метода одномерной активизации.

К сожалению, рассмотренный метод не является алгоритмом, т.е. он не гарантирует построение теста для отдельных неисправностей некоторых схем. Например, для приведённой на рис. 17.4 схемы для неисправности $$х_{2}\equiv 1$$ этот метод не может построить тест.

Активизация одиночного пути $$x_{2}$$, $$x_{4}$$, $$x_{6}$$ требует значения $$x_{5}=0$$, что невозможно, так как для активизации неисправности $$х_{2}\equiv 1$$ необходимо подать $$х_{2}=0$$, что ведет к требованию $$x_{5}=1$$(т.е. возникновению противоречия - конфликта на линии $$x_{5}$$). В силу симметрии невозможно также активизировать второй одиночный путь $$x_{2}$$, $$x_{5}$$, $$x_{6}$$. Тем не менее, тест для этой неисправности существует - $$x_{1}=1$$, $$x_{2}=0$$, $$x_{3}=1$$. Действительно, на этом наборе $$F=1$$ при отсутствии неисправности и $$F=0$$ при ее наличии. Этот тест не может быть построен данным методом, так как в этом случае необходимо активизировать одновременно два пути от места неисправности до внешнего выхода схемы. Все последующие методы построения тестов основаны на многомерной активизации (нескольких) путей с использованием многозначных алфавитов.

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

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

Булева производная - определяет зависимость булевой функции от переменной.

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

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

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

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

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

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

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

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

Приведите определение различающей функции.

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

Постройте методом различающей функции проверяющий тест для неисправности const0 на выходе второго вентиля первого уровня, приведенной на рис. 17.5. (рис 17.5) Схема для упражнения 4.

Дайте определение булевой производной.

Приведите основные свойства булевых производных.

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

Какое булево уравнение необходимо решить для построения теста для неисправности константа 0?

Какое булево уравнение необходимо решить для построения теста для неисправности константа 1?

Постройте методом булевой производной проверяющий тест для неисправности $$x_{8}=1$$, приведенной на рис. 17.6. (рис 17.6) Схема для упражнения 10.

Опишите этапы одномерной активизации пути.

Постройте методом активизации путей проверяющий тест для неисправности $$x_{8}=0$$, приведенной на схеме рис. 17.6. (рис 17.7) Схема для упражнения 12.