Скобцовы Моделирование и тестирование

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

D2=D2t c D1tc , так как в зависимости от пары начальных состояний неисправность может быть обнаружена на первой или второй итерации.

Произвольная функция Di имеет вид дизъюнктивной формы вида (7.2), как и произвольная функция Dit . Однако, в отличие от различающей функции

Dit , в функции Di из произвольного терма fi(X) gi(Y) определяются пары начальных состояний, различаемые соответствующей входной последовательностью при условии стратегии кратного наблюдения. Если из функции D2 также не можем найти тест, то из D2t c находим D3t путем

~

рекуррентной подстановки Yt-1=Yt-2 . И так до тех пор, пока либо не будет найден тест, либо на каком-то шаге полученная сокращенная различающая функция станет равной нулю, либо количество итераций достигнет своего ограничения.

В символьном выражении Di, получаемом в процессе построения теста, из произвольного терма вида fi(X) gi(Y) определяются все пары начальных состояний, различаемые соответствующей входной последовательностью при условии стратегии кратного наблюдения. В ОРД из A-группы, связанной с произвольной вершиной, также определяются все пары начальных состояний, различаемые входной последовательностью,

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

Проиллюстрируем работу данного метода на примере схемы,

изображенной на рис.7.10. Найдем тест для неисправности f2≡0 данного

301

устройства. Исходя из типа ошибки const0, можно сказать, что линия f2

может принимать только значения D или 0. Отсюда следует, что f2F1 =0, а

f2F 0 =1. Будем учитывать эту особенность в последующих вычислениях.

Отметим также, что в данной схеме все линии, кроме линии входа x (x B2), могут принимать значения из алфавита B16. Ищем различающую

функцию для итеративной схемы, состоящей из одного КЭ (длиной 1):

D1t=ztD′ ztD=xt ( y2Dt y2Dt′ ) xt ( y1Dt y1Dt ′ ) .

Так как D1t не содержит термов, зависящих только от x, то из D1t

искомый тест определить нельзя. Из терма xt (y2Dt y2Dt′ ) определяем, что

пары начальных состояний (B,a), (B,c), (D,a), (D,c), (A,b), (A,d), (C,b), (C,d)

исправной и неисправной схем различаются входной последовательностью из одного набора T=(0). Заметим, что полученное множество различаемых пар начальных состояний совпадает с множеством различаемых пар начальных состояний, которое можно определить из A-группы 1-го уровня

неисправной схем (A,c), (A,d), (B,c), (B,d), (C,a), (C,b), (D,a), (D,b)

различаются входной последовательностью из одного набора T=(1).

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

которое можно определить из A-группы 1-го уровня {CDcd}{ABab},

связанной с вершиной, соответствующей последовательности T=(1) на ОРД (Рис.7.12). Эти факты говорят об аналогичности процесса построения теста нашим методом и построения теста методом ОРД.

характеристических переменных

При вычислении D2t мы активизировали данную неисправность f2≡0.

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

также не удается. Поэтому, находим сокращенную различающую функцию

Функция D3 тоже не позволяет нам решить поставленную задачу. Далее

находим

D4t = xt xt-1 (xt-3 y2Gt-03 xt-3 y2Gt1-3 ) .

Из полученной различающей функции также не находим искомый тест. Поэтому вычисляем D4t c = xt xt-1 xt-3 y2Gt-03 и D4:

303

чтобы значение терма было равным 1: x1=1, x2=1, x3=1, x4=1. Равенство единице терма обуславливает равенство всей различающей функции D4=1,

что является признаком обнаруживаемости данной неисправности. Таким образом, входная последовательность T4=(1,1,1,1), определяемая из D4,

является тестом данной неисправности f2≡0.

Обобщая все выше сказанное, приводим алгоритм обратного метода генерации тестов, реализующего на структурном уровне преимущества автоматного метода построения ОРД.

t n D′ D

1V(zit zit ) , где n - число внешних выходов.

i=1

2.Если в D1t имеются термы, не содержащие переменные1. =

внутреннего состояния и, следовательно, определяющие тестовые

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

Конец.

3. 3. D1tc = D1t . 4. i=2.

5. Вычисляем Dit из Dit-1c , выполняя рекуррентные подстановки

= ~

Yt − i + 2 Yt − i +1 .

6. Если в Dit имеются термы, не содержащие переменные внутреннего состояния и, следовательно, определяющие тестовые последовательности, то искомые тесты минимальной длины найдены.

Конец.

304

7. Применяя к Dit процедуру исключения повторных термов,

находим Dict .

8. Если Dict =0, то искомого теста не существует. Конец.

i

9. Вычисляем Di= V Dkct-i+k .

k=1

10. Если в Di имеются термы, не содержащие переменные внутреннего состояния и, следовательно, определяющие тестовые последовательности, то искомые тесты минимальной длины найдены.

Конец.

11. i=i+1.

12. Если i не превышает допустимое число итераций, то переход

на шаг 5. Иначе - конец.

Выше изложенный алгоритм построения проверяющих тестов предназначен для синхронных последовательностных схем. В общем случае он может применяться и для асинхронных схем. Однако, в этом случае, построенные тесты подлежат дополнительной проверке процедурой моделирования ДУ с неисправностями, так как модель итеративной комбинационной схемы не вполне адекватно отражает поведение асинхронного последовательностного ДУ. Можно показать, что если проверяющий тест существует, то он будет найден за k ≤ 2m+1-1

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

принадлежащий классу, который содержит пару автоматов,

соответствующих исправному и неисправному ДУ [95]. Данный метод объединяет в себе возможности точных автоматных методов построения проверяющих экспериментов и структурных методов генерации тестов.

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

305

7.3.3 Структурный метод построения тестов

Основываясь на изложенном выше аналитическом методе,

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

Его ключевыми пунктами, также как и в предыдущем алгоритме, являются: 1) применение стратегии кратного наблюдения; 2) использование универсальной 16-значной логики и системы многозначных функций.

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

значном алфавите B16 на линиях схемы.

В начале процесса генерации теста мы полагаем, что любая комбинация значений сигналов 0, D’, D, 1 возможна на произвольной линии рассматриваемого устройства, кроме неисправной линии. Поэтому сначала мы устанавливаем на всех линиях схемы, за исключением неисправной линии, неопределенное значение u алфавита B16 (Табл.1.3). На линии, содержащей неисправность, в зависимости от типа неисправности устанавливается значение F1 или F0: F1 - для неисправности const1, F0 -

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

При наличии на некоторой линии устройства константной неисправности consta (a{0,1}) в неисправном ДУ устанавливается значение a, в

исправном же ДУ значение неизвестно - это может быть 0 или 1. Поэтому на неисправной линии возможны следующие комбинации сигналов: 0a, 1a. Для a=0 это соответствует 00=0, 10=D, то есть, имеем значение F0={0 D}. Аналогично для a=1 имеем 01=D’, 11=1 – F1={D’ 1}. Так, в уже

306

рассматриваемой схеме (Рис.7.10) на линии f2 устанавливается значение F0,

поскольку на данной линии присутствует неисправность const0. Затем для рассматриваемой схемы выполняется структурная импликация,

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

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

~

ДУ. Так как линии состояния Y, Y последовательностного ДУ могут

принимать любое из четырех значений 0, D’, D, 1, то на линиях состояния ДУ и на их линиях-последователях оставляется неопределенное значение u. Для этой же схемы (рис.7.10) в результате структурной импликации

Рис.7.17 Итеративная комбинационная схема из 1 КЭ

Далее исходное последовательностное ДУ трансформируется в комбинационную итеративную схему, как это было показано в предыдущем разделе 7.1. Например, обрыв обратных связей в последовательностной схеме на рис.7.10 дает комбинационный эквивалент, изображенный на Рис.7.16. Сначала рассматривается комбинационная итеративная схема,

состоящая из одного КЭ (рис.7.17). Как известно, неисправность будет обнаруживаться, если на каком либо внешнем выходе схемы устанавливается значение D’ или D. Поэтому на внешних выходах

307

комбинационной итеративной схемы длины один устанавливаются значения D*={D’ D} (D’ или D) и распространяются к внешним входам и псевдовходам. Процедура распространения выполняется при помощи обратной логической импликации, описанной в подразделе 7.1.2 и

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

устанавливаются соответственно определенные значения. Значения на внешних входах определяют входную последовательность, при подаче которой на некотором внешнем выходе устанавливается критическое значение D’ или D. Значения линий начального состояния определяют пары начальных состояний исправного и неисправного ДУ, различаемые этой входной последовательностью. Распространение значения D* с

внешнего выхода z1 итеративной комбинационной схемы длины один устанавливает на линиях f31 и f41 значение D0, дальнейшее распространение которого не снимает неопределенности на линиях начального состояния.

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

Сначала устанавливаем на внешнем входе значение x1=0. В результате распространения данного значения с помощью прямой логической импликации получаем f21=f41=0. Затем опять выполняется обратное распространение значения z=D*. В результате получаем y11=u, y21=D*.

Следует отметить, что данные значения линий начального состояния соответствуют терму xt ( y2Dt y2Dt′ ) из различающей функции D1t (смотри подпункт 7.3.2.). То есть наблюдается соответствие между данными методами. Полученные значения линий начального состояния y21=D*, y11=u

определяют следующие значения линий исправного и неисправного устройств соответственно: (y1=u,y2=0) и (y1н=u,y2н=1), (y1=u,y2=1) и (y1н=u,y2н=0). Последние в свою очередь определяют пары начальных состояний исправного (Табл.7.1) и неисправного (Табл.7.2) устройств:

308

(B,a), (B,c), (D,a), (D,c), (A,b), (A,d), (C,b), (C,d), различаемые входной последовательностью (x1=0). Заметим, что полученное множество различаемых пар начальных состояний совпадает с множеством различаемых пар начальных состояний, которое можно определить из A-

группы 1-го уровня {BDbd}{ACac}, связанной с вершиной,

соответствующей последовательности T=(0) на ОРД (Рис.7.12). Далее устанавливаем на внешнем входе значение x1=1. В результате распространения данного значения с помощью прямой логической импликации получаем f11=f31=0. Затем снова выполняется обратное распространение значения z=D*. В результате получаем y11=D*, y21=u.

Отметим, что данные значения линий начального состояния также соответствуют терму xt ( y1Dt y1Dt ′ ) в различающей функции D1t . Таким образом, наблюдается соответствие между символьным и структурным методами. Полученные значения линий начального состояния y11=D*, y21=u

определяют следующие значения линий исправного и неисправного устройств соответственно: (y1=0,y2=u) и (y1н=1,y2н=u), (y1=1,y2=u) и (y1н=0,y2н=u). Последние в свою очередь определяют пары начальных состояний исправного (Табл.7.1) и неисправного (Табл.7.2) устройств: (A,c), (A,d), (B,c), (B,d), (C,a), (C,b), (D,a), (D,b), различаемых входной последовательностью (x1=1). Отметим, что полученное множество различаемых пар начальных состояний совпадает с множеством различаемых пар начальных состояний, которое можно определить из A-

группы 1-го уровня {CDcd}{ABab}, связанной с вершиной,

соответствующей последовательности T=(1) на ОРД (Рис.7.12). Так как полученные входные последовательности T11=(0) и T12=(1) не различают все возможные пары начальных состояний исправной и неисправной схем,

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

309

Рис.7.18 Итеративная комбинационная схема из 2 КЭ

Если с помощью распространения значения D* для итеративной схемы из одного КЭ тест не был найден, как в рассматриваемом примере, то необходимо продолжить построение теста в итеративной комбинационной схеме длины два (Рис.7.18). Данная схема получается из схемы единичной длины присоединением слева одного дополнительного КЭ. При этом номера всех ячеек, находящихся справа от вновь присоединенного КЭ,

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

итеративную комбинационную схему из двух КЭ (Рис.7.18). На предыдущей итерации нами было получено два варианта: 1) x2=0, y12=u, y22=D*; 2) x2=1, y12=D*, y22=u. Рассмотрим сначала первый вариант.

Распространение значения y12=u не определяет новых значений, поэтому оно не выполняется. Распространяем значение y22=D* на псевдовыходы

следующие результаты: x1=C, y11=D*, y21=u. Очевидно, что полученная входная последовательность T21=(C,0) не является тестом. Кроме того, как видно из значений линий начального состояния, ею различаются те же

310