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

12.1 Дедуктивный метод моделирования в двоичном алфавите

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

Сначала для каждого входного набора выполняется моделирование исправной схемы в двоичном алфавите. А далее для каждой линии схемы (в том числе и внешних выходов) определяются списки неисправностей, при которых значение сигнала меняется на противоположное. Поэтому здесь с каждой линией схемы связывается список неисправностей, изменяющих значения сигналов на этом входе или выходе, как это показано на рис. 11.1 [12.2]. Здесь малыми буквами обозначены переменные значений сигналов, а большими - списки неисправностей, связанные с соответствующими линями. Каждый список содержит неисправности, которые дают значения сигналов на данной линии противоположные значениям сигналов в исправной схеме. Например, для $$a=0$$ список $$A$$ содержит все неисправности схемы, при которых $$a=1$$.

(рис 12.1) Списки неисправностей вентиля

Основной проблемой в дедуктивном методе является получение списка неисправностей, связанного с выходом логического элемента, по спискам неисправностей его входов[12.3]. При этом неисправности, изменяющие значение выхода элемента, определяются по спискам неисправностей, изменяющих сигналы на его входах, с помощью специальных теоретико-множественных операций, определяемых законом функционирования данного элемента. Существенной особенностью дедуктивного метода является то, что в результате одного шага моделирования, который соответствует подаче данного тестового набора, определяются все неисправности, проверяемые на этом наборе. Шаг моделирования при этом существенно удлиняется. Вычисления проводятся только вдоль путей схемы, по которым распространяется влияние неисправностей.

Основной проблемой является получение теоретико-множественных формул для распространения списков неисправностей через вентиль. То есть, как по данным спискам неисправностей входов вентиля получить список неисправностей, связанный с его выходом. Рассмотрим логический элемент И (рис. 12.1), на входах и выходах которого в исправной схеме на данном тестовом наборе устанавливаются определённые значения 0 или 1 (рассмотрим сначала моделирование в двоичном алфавите).

Тип	Значения входов	Список выхода
И, НЕ-И	$$I^0= \varnothing$$	$$ F=\bigcup{X_i}$$
	$$I^0\neq\varnothing$$	$$ F=\bigcap{X_i}-\bigcap{X_j}=\bigcap{X_i\cap(\overline {\bigcap{X_j}})}\\ X_i\in I_1, X_j\in I_0$$
ИЛИ, НЕ-ИЛИ	$$I^1=\varnothing$$	$$F=\bigcup{X_i}$$
	$$I^1\neq\varnothing $$	$$ F=\bigcap{X_i}-\bigcap{X_j}=\bigcap{X_i\cap(\overline {\bigcap{X_j}})}\\ X_i\in I_1, X_j\in I_0$$
НЕ		$$X_1$$

Рассмотрим первую типовую ситуацию. Пусть $$a=1$$, $$b=1$$, $$c=0$$ и $$f=0$$. Тогда неправильное значение $$f=1$$ на выходе этого вентиля вызывает любая неисправность из списка $$С$$, которая не содержится в списках $$А$$ и $$В$$. Поэтому в данном случае при распространении списка неисправностей через данный логический элемент имеем: $$F=C - (A\cup B)$$ (здесь минус - означает вычитание множеств - $$F=C \cap (A\cup B)$$). Очевидно, что к полученному списку $$F$$ необходимо добавить неисправность $$f\equiv 1$$ выхода вентиля. Поэтому окончательное выражение для распространения списков неисправностей в этом случае имеет вид $$F=(C - (A\cup B))\cup f_1$$.

Рассмотрим вторую типовую ситуацию для этого вентиля, при которой $$a=1$$, $$b=1$$, $$c=1$$, $$f=1$$. Очевидно, что в этом случае значение $$f=0$$ может вызвать любая неисправность из списков $$A, B, C$$ и неисправность $$f\equiv 1$$. Поэтому получаем следующее теоретико-множественное правило для распространения неисправностей $$F=A\cup B\cup C\cup f_1$$. В табл. 11.1 в общем виде приведены правила распространения неисправностей для типовых вентилей в стандартных ситуациях. Здесь $$I^0$$ - множество входов вентиля, имеющих значение 0, $$I^1$$ - множество входов вентиля, имеющих значение 1.

(рис 12.2) Пример схемы для дедуктивного метода

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

изменение значений сигналов исправной схемы;

изменение списков неисправностей (при чём оно может быть без изменения значений сигналов).

Рассмотрим данный метод на примере схемы, представленной на рис. 12.2. Очевидно, что для внешних входов схемы связанные с ними списки неисправностей содержат по одной константной неисправности (значения констант противоположны значениям внешних входов). Поскольку мы моделируем схему на входном наборе $$a=1, b=1, d=0, i=1, h=1, f=1$$, то получаем:

$$ A = \{a_{0}\}, B = \{b_{0}\}, D = \{d_{1}\}, I = \{i_{0}\}, H = \{h_{0}\}, F = \{f_{0}\}.$$

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

$$ C=A\cup B\cup c_1=\{a_0,b_0,c_1\};\\ E=D\cup C\cup e_1=\{a_0,b_0,c_1,d_1,e_1\};\\ G=E\cup g_1=\{a_0,b_0,c_1,d_1,e_1,g_1\};\\ J=E\cup j_1=\{a_0,b_0,c_1,d_1,e_1,j_1\};\\ K=I\cup H\cup k_1=\{i_0,h_0,k_1\};\\ L=J\cup l_0=\{a_0,b_0,c_1,d_1,e_1,j_1,l_0\};\\ M=(K-L)\cup m_1=\{i_0,h_0,k_1,m_1\};\\ N=(G-F)\cup n_1=\{a_0,b_0,c_1,d_1,e_1,g_1,n_1\};\\ P=N\cup M\cup p_1=\{a_0,b_0,c_1,d_1,e_1,g_1,n_1,i_0,h_0,k_1,m_1,p_1 \};\\$$

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

Мы уже говорили о том, что в дедуктивном методе используется событийное моделирование. Далее рассмотрим события, вызываемые изменением входа схемы $$h:1\to 0$$. Прежде всего, изменяется список $$H=\{h_1\}$$. Это изменение вызывает следующие события:

$$ k:0\to 1,\, K=(H-I)\cup k_0=\{h_1,k_0\};\\ m:0\to 1,\, M=L\cup K\cup m_0 =\{a_0,b_0,c_1,d_1,e_1,j_1,l_0,h_1,k_0,m_0\};\\ p:0\to 1,\, P=(M-N)\cup p_0=\{h_1,k_0,m_0,j_1,l_0,p_0\}.$$

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

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

12.2 Дедуктивное моделирование в троичном алфавите

Распространение дедуктивного метода моделирования на троичный алфавит можно реализовать несколькими способами [12.4]. Рассмотрим один из них. При этом каждой $$i$$-ой линии схемы ставятся в соответствие двоичные переменные $$x_i^0, x_i^1$$ и два списка неисправностей $$X_i^0, X_i^1$$. Правила обработки списков неисправностей зависят от логической функции элемента и применяемого способа кодирования алфавита. Как и для параллельного метода , в троичном алфавите, мы будем использовать дизъюнктивный метод кодирования, представленный табл. 11.2. При этом, как уже говорилось, фактически моделирование каждого вентиля в троичном алфавите заменяется моделированием двух вентилей в двоичном алфавите (рис. 5.4). Но схему в двоичном алфавите мы уже умеем моделировать дедуктивным методом. Поэтому для каждого из этих двух вентилей можно применять приведенные выше правила распространения неисправностей (в двоичном алфавите), что решает проблему обобщения дедуктивного моделирования на троичный алфавит. На рис. 12.3 это представлено в графическом виде. Так, например, для $$a^*=1, b^*=1, f^*=1$$ получаем в соответствии с дизъюнктивным кодированием $$a^{0}=0, a^{1}=1, b^{0}=0, b^{1}=1, f^0=0, f^1=1$$ (показано на рис. 12.3) следующие правила распространения:

$$ F^0=A^0\cup B^0\cup f_1^0,\, F^1=A^1\cup B^1\cup f_0^1$$

Здесь $$f_1^0$$ означает неисправность константа 1 нулевой компоненты троичного алфавита переменной $$f$$, и $$f_0^1$$ - константа 0 единичной компоненты.

(рис 12.3) Дедуктивное моделирование в троичном алфавите

12.3 Дедуктивное моделирование в многозначных алфавитах

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

При дедуктивном методе моделирования в многозначном алфавите, например $$Е_5$$, каждой линии $$i$$ ДУ поставим в соответствие четыре переменные $$x_i^0,x_i^{D'},x_i^D,x_i^1$$, принимающие двоичные значения $$\{0;1\}$$ и четыре списка неисправностей $$X_i^0, X_i^{D'}, X_i^D, X_i^1$$ , связанные с этими переменными. Например, на рис. 12.4 представлены соответствующие списки неисправностей и покомпонентные переменные для вентиля $$f=ab$$.

(рис 12.4) Дедуктивное моделирование в многозначных алфавитах

Ключевым вопросом является распространение списков неисправностей через логический элемент (для нашего примера по заданным спискам $$A_i^0,A_i^{D'},A_i^D,A_i^1$$ и $$B_i^0,B_i^{D'},B_i^D,B_i^1$$ определение списков $$F_i^0,F_i^{D'},F_i^D,F_i^1$$). Суть предлагаемого метода заключается в том, что каждой из двоичной компонент ставится в соответствие список неисправностей, изменяющих значение этой компоненты на противоположное, а теоретико-множественные операции $$F_i^0,F_i^{D'},F_i^D,F_i^1$$ для распространения входных списков неисправностей выводятся из булевых функций $$f_i^0,f_i^{D'},f_i^D,f_i^1$$.

Рассмотрим неисправность $$\alpha$$, при которой в исправном ДУ $$x_i=0$$, а в неисправном $$x_{if}=1$$. Тогда неисправность $$\alpha$$ может быть представлена следующим образом: $$ x_i^0=1\{\alpha\},x_i^{D'}=0\{\},x_i^D=0\{\},x_i^1=0\{\alpha\}$$. Эта нотация означает, что неисправность $$\alpha$$ входит в списки неисправностей $$X_i^0,X_i^1$$ и не входит в списки $$X_i^{D'},X_i^D$$. Поскольку в исправном ДУ $$\tilde{x}_i=0$$, что соответствует $$x_i^0=1,x_i^{D'}=0, x_i^D=0,x_i^1=0$$ согласно кодированию табл. 12.1, и неисправность $$\alpha$$ меняет значения компонент $$x_i^0,x_i^1$$ на противоположное, так как она входит списки $$X_i^0,X_i^1$$, получаем значения $$x_i^0=0,x_i^{D'}=0, x_i^D=0,x_i^1=1$$ , которые являются кодом $$\tilde{x}_{if}=1$$. Аналогично неисправность $$\beta$$, при которой $$\tilde{x}_i=1$$ и $$\tilde{x}_{if}=E$$ представляется $$ x_i^0=1\{\beta\},x_i^{D'}=0\{\beta\},x_i^D=0\{\},x_i^1=0\{\}$$. В табл. 11.1 приведены всевозможные комбинации значений $$x_i$$ и $$x_{if}$$ (в исправном и неисправном ДУ) и их представления в указанной нотации. Теоретико-множественные операции над входными списками для получения выходных списков $$F_i^0,F_i^{D'},F_i^D,F_i^1$$ выводятся из функций $$f_i^0,f_i^{D'},f_i^D,f_i^1$$.

$$x_i$$	$$x_{if}$$	$$x_i^{0}/X_i^{0}$$	$$x_i^{D'}/X_i^{D'}$$	$$x_i^{D}/X_i^{D}$$	$$x_i^{1}/X_i^{1}$$
$$0$$	$$0$$	$$1\{\varnothing \}$$	$$0\{\varnothing \}$$	$$0\{\varnothing \}$$	$$0\{\varnothing \}$$
$$0$$	$$1$$	$$1\{\alpha \}$$	$$0\{\varnothing \}$$	$$0\{\varnothing \}$$	$$0\{\alpha \}$$
$$0$$	$$E$$	$$1\{\varnothing \}$$	$$0\{\alpha \}$$	$$0\{\varnothing \}$$	$$0\{\alpha \}$$
$$0$$	$$H$$	$$1\{\varnothing \}$$	$$0\{\varnothing \}$$	$$0\{\alpha \}$$	$$0\{\alpha \}$$
$$0$$	$$u$$	$$1\{\varnothing \}$$	$$0\{\alpha \}$$	$$0\{\alpha \}$$	$$0\{\alpha \}$$
$$1$$	$$0$$	$$0\{\varnothing \}$$	$$0\{\varnothing \}$$	$$0\{\varnothing \}$$	$$1\{\alpha \}$$
$$1$$	$$1$$	$$0\{\varnothing \}$$	$$0\{\varnothing \}$$	$$0\{\varnothing \}$$	$$1\{\varnothing \}$$
$$1$$	$$E$$	$$0\{\alpha \}$$	$$0\{\alpha \}$$	$$0\{\varnothing \}$$	$$1\{\varnothing \}$$
$$1$$	$$H$$	$$0\{\alpha \}$$	$$0\{\varnothing \}$$	$$0\{\alpha \}$$	$$1\{\varnothing \}$$
$$1$$	$$u$$	$$0\{\alpha \}$$	$$0\{\alpha \}$$	$$0\{\alpha \}$$	$$1\{\varnothing \}$$
$$E$$	$$0$$	$$1\{\varnothing \}$$	$$1\{\alpha \}$$	$$0\{\varnothing \}$$	$$1\{\varnothing \}$$
$$E$$	$$1$$	$$1\{\alpha \}$$	$$1\{\alpha \}$$	$$0\{\varnothing \}$$	$$1\{\varnothing \}$$
$$E$$	$$E$$	$$1\{\varnothing \}$$	$$1\{\varnothing \}$$	$$0\{\varnothing \}$$	$$1\{\varnothing \}$$
$$E$$	$$H$$	$$1\{\varnothing \}$$	$$1\{\alpha \}$$	$$0\{\alpha \}$$	$$1\{\varnothing \}$$
$$E$$	$$u$$	$$1\{\varnothing \}$$	$$1\{\varnothing \}$$	$$0\{\alpha \}$$	$$1\{\varnothing \}$$
$$H$$	$$0$$	$$1\{\varnothing \}$$	$$0\{\varnothing \}$$	$$1\{\alpha \}$$	$$1\{\alpha \}$$
$$H$$	$$1$$	$$1\{\alpha \}$$	$$0\{\varnothing \}$$	$$1\{\alpha \}$$	$$1\{\varnothing \}$$
$$H$$	$$E$$	$$1\{\varnothing \}$$	$$0\{\alpha \}$$	$$1\{\alpha \}$$	$$1\{\varnothing \}$$
$$H$$	$$H$$	$$1\{\varnothing \}$$	$$0\{\varnothing \}$$	$$1\{\varnothing \}$$	$$1\{\varnothing \}$$
$$H$$	$$u$$	$$1\{\varnothing \}$$	$$0\{\alpha \}$$	$$1\{\varnothing \}$$	$$1\{\varnothing \}$$
$$u$$	$$0$$	$$1\{\varnothing \}$$	$$1\{\alpha \}$$	$$1\{\alpha \}$$	$$1\{\alpha \}$$
$$u$$	$$1$$	$$1\{\alpha \}$$	$$1\{\alpha \}$$	$$1\{\alpha \}$$	$$1\{\varnothing \}$$
$$u$$	$$E$$	$$1\{\varnothing \}$$	$$1\{\varnothing \}$$	$$1\{\alpha \}$$	$$1\{\varnothing \}$$
$$u$$	$$H$$	$$1\{\varnothing \}$$	$$1\{\alpha \}$$	$$1\{\varnothing \}$$	$$1\{\varnothing \}$$
$$u$$	$$u$$	$$1\{\varnothing \}$$	$$1\{\varnothing \}$$	$$1\{\varnothing \}$$	$$1\{\varnothing \}$$

Поскольку это "обычные" булевы функции, то для этих операций можно использовать известные методы, например, изложенные в [12.4,12.5]. Как правило, указанные методы ориентированы на вывод теоретико-множественных операций для определенных входных наборов двоичных значений данной булевой функции.

Рассмотрим распространение входных списков неисправностей в пятизначном алфавите $$Е_5$$ на примере вентиля $$f=ab$$. Его поведение в алфавите $$Е_5$$ описывается следующими компонентами:

$$ f^0=a^0b^0\vee a_{D'}b^D\vee a^{D}b^{D'}, f^{D'}=a^{D'}b^1\vee a^{1}b^{D'}\vee a^{D'}b^{D'},\\ f^{D}=a^{D}b^1\vee a^{1}b^{D}\vee a^{D}b^{D}, f^1=a^1b^1.$$

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

$$ a^0=0,\,A^0=\{a_0,a_E,a_H,a_u\};\\ a^{D'}=0,\,A^{D'}=\{a_E,a_u\};\\ a^{D}=0,\,A^{D}=\{a_H,a_u\};\\ a^{1}=0,\,A^{1}=\{a_0\};\\ b^{0}=0,\,B^{0}=\{b_1\};\\ b^{D'}=0,\,B^{D'}=\{b_E,b_u\};\\ b^{D}=0,\,B^{D}=\{b_H,b_u\};\\ b^1=0,\,B^1=\{b_1,b_E,b_H,b_u\}.$$

Результаты показывают, что в исправном ДУ $$\tilde{f}=0$$, а при неисправности $$b_1$$ имеет место $$\tilde{f}_f=E$$. Аналогично при неисправностях $$b_H-\tilde{f}=H,\, b_u-\tilde{f}=u$$. Таким образом, неисправности $$a_0,a_E,a_H,a_u$$ на выходе вентиля не проявляются, а неисправности $$b_1,b_E,b_H,b_u$$ распространяются на его выход. Если во множество моделируемых неисправностей входят const0 и const1 на выходе вентиля, то мы должны добавить неисправность $$f_1$$ в списки ($$f_0$$ не проверяется). В результате получим $$F^0 =\{b_1,f_1\},\, F_{D'}=\{b_E,b_u\},\, F_{D}=\{b_H,b_u\},\, F_{1}=\{b_1,b_H,b_E,b_u,f_1\}.$$

Основным преимуществом предлагаемого подхода является то, что при разработке моделей цифровых микросхем (правил распространения входных списков неисправностей) не нужно строить новые модели, а можно использовать универсальные модели для многозначных алфавитов, предложенные в лекции 7. Поскольку разработаны формальные методы построения моделей, вывод их может быть автоматизирован. Данные модели по сложности не превосходят предложенные в работах [12.4,12.5].

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

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

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

Троичный алфавит - включаетсимволы $$Е_3 = \{0,1,u\}$$, где символ $$u$$ соответствует неопределенному значению сигнала.

Многозначный алфавит - включает много (больше 3) символов, отражающих различные распределения сигналов в схеме.

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

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

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

Раздел 11.2 посвящен распространению дедуктивного метода на троичный алфавит. В этом случае используется дизъюнктивное кодирование троичного алфавита и с каждой линией связывается два списка неисправностей. Это позволяет свести троичное моделирование к двоичному и использовать стандартную технику дедуктивного метода.

В разделе 10.3 изложено распространение дедуктивного метода на многозначный алфавит, В этом случае с каждой линией связывается четыре списка неисправностей и исползуется двоичное кодирование многозначного алфавита.

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

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

Выведите правило распространения неисправностей для элемента $$f=\overline{x\y\z}$$ при $$x=0, y=1, z=1$$.

Выведите правило распространения неисправностей для элемента $$f=\overline{x\vee y\vee z}$$ при $$x=0, y=0, z=0$$.

Выполните дедуктивное моделирование в двоичном алфавите для всех одиночных константных неисправностей приведенной схемы рис. 12.5 на тестовом наборе (111111). (рис 12.5) Схема для упражнения 4 (дедуктивное моделирование неисправностей).

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

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

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

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

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

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

Как выполняется распространение неисправностей в многозначном алфавите?.