Структурное построение тестов для устройств с памятью

Наиболее распространённым на практике подходом к построению тестов для последовательностных схем является преобразование их в итеративные комбинационные схемы (ИКС), элементом которых является так называемый комбинационный эквивалент (КЭ), и обобщение для них рассмотренных в лекциях 16-20 методов для комбинационных схем.

23.1 Итеративные комбинационные схемы

Согласно каноническому представлению последовательностное устройство можно представить в виде комбинационного блока и блока памяти, которые соединены линиями обратной связи $$Y=(y_1,y_2,\ldots,y_n)$$ (рис. 23.1- а, лекция 2). Комбинационный эквивалент получается из исходного устройства с памятью путём условного обрыва обратных связей. При этом вектор обратных связей $$Y=(y_1,y_2,\ldots,y_n)$$ разбивается на вектор $$Y=(y_1,y_2,\ldots,y_n)$$ так называемых псевдовходов и вектор псевдовыходов $$\tilde{Y}=(\tilde{y}_1,\tilde{y}_2,\ldots,\tilde{y}_n)$$ (рис. 23.1 - б) [23.1-23.3].

Если рассматривается поведение последовательностной схемы в течение $$t$$ тактов, то $$t$$ комбинационных эквивалентов соединяются последовательно в итеративную комбинационную схему, как показано на рис. 23.2. Здесь произвольная $$j$$-я итерация $$I_j$$ итеративной комбинационной схемы соответствует состоянию исходной последовательностной схемы на $$j$$-м такте времени. При этом компоненты векторов $$X_j$$, $$Z_j$$ соответствуют линиям первичных входов и выходов соответственно, $$Y_j$$, $$\tilde{Y}_j$$ - псевдовходам и псевдовыходам соответственно на $$j$$-м такте. Также очевидно, что $$Y_j$$, $$\tilde{Y}_j$$ - это линии, определяющие состояние последовательностного ЦУ в начале и в конце $$j$$-го такта соответственно.

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

(рис 23.3) Триггер

(рис 23.4) Комбинационный эквивалент триггера

Рассмотрим построение теста, который проверяет константную неисправность const1 - $$V\equiv 1$$ на нижнем плече триггера на основе методов с использованием шестизначного алфавита $$T_{6}$$, рассмотренных в лекциях 18, 19.. Процесс построения теста начинается с внесения значения $$V_{1}=D'$$, соответствующего неисправности const 1, в итеративной схеме из одного комбинационного эквивалента, как это показано на рис. 23.5.

Из примера видно, что в итеративной комбинационной схеме, как и ранее, надо выполнить распространение критического значения, в данном случае $$D'$$, от места неисправности до внешних выходов схемы при условии неопределенности начального состояния ЦУ, т.е. неопределённых значениях на псевдовходах первого комбинационного эквивалента итеративной комбинационной схемы. Поскольку в процессе доопределения мы получаем для псевдовхода $$y_{1}=1$$ вместо неопределенного значения $$y=u$$, то это говорит о невозможности построения теста для итеративной схемы из одного эквивалента (единичной длины). Отметим, что мы строим тест, исходя из предположения, что начальное состояние ЦУ не известно.

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

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

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

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

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

Кроме того, при разворачивании последовательностной схемы в итеративную комбинационную неисправности "размножаются". Так, в приведенном примере одиночная константная неисправность на нижнем плече триггера в итеративной комбинационной схеме соответствует двум константным неисправностям $$V_{1}\equiv 1$$ и $$V_{2}\equiv 1$$. Поэтому методы генерации тестов для последовательностных схем должны учитывать этот эффект.

При построении тестов производится активизация путей в многозначных алфавитах от неисправных линий до одного из выходов последней $$t$$-й копии итеративной комбинационной схемы. При этом число копий КЭ $$k$$ определяется условием появления неопределённых значений на псевдовходах $$(t-k)$$-й копии.

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

23.2 Построение тестов для последовательностных схем в 16-значном алфавите

Большинство структурных методов построения тестов последовательностных схем для активизации критических путей в схеме используют многозначные алфавиты [23.1-23.3]. Последние позволяют с различной точностью описывать возможные комбинации значений сигналов в исправном и неисправном ЦУ. В лекции 7 рассматривался универсальный 16-значный алфавит $$B_{16}$$ (лекции 18, элементы этого алфавита, в контексте задачи построения проверяющих тестов, имеют следующую интерпретацию: $$0,1 (00, 11)$$ - значения сигналов одинаковы, $$D', D (01, 10)$$ - значения сигналов различны в исправном и неисправном ЦУ.

Основные многозначные алфавиты, используемые при генерации тестов, также являются подмножествами универсального алфавита $$B_{16}$$ (лекции 18-20). Так, наиболее распространенные на практике современные модификации $$D$$-алгоритма [23.1,23.2], метод PODEM [23.4] и его дальнейшее развитие - метод FAN [23.5], используют шестизначный алфавит $$T_6 = \{\varnothing , 0, 1, D, D', u\} $$(здесь и далее символ \varnothing используется для обозначения конфликтных ситуаций). В общем случае эти методы требуют многомерной активизации путей (распространения значений $$D, D' $$ по нескольким путям одновременно).

Следующая группа методов типа "9V" [23.6] (один из методов изложен в лекции 20) использует десятизначный алфавит $$T_{10}$$,который, кроме символов, входящих в $$T_6$$, содержит символы $$G0, F0, G1, F1$$, позволяющие более точно описывать возможные комбинации значений сигналов. К ним относится также метод, основанный на SPLIT-модели, который использует фактически 12-значный алфавит $$T_{12} = \{\varnothing , 0, 1, D, D', F0, F1, G0, G1, D^*, С, u\} $$[23.7]. Благодаря использованию более мощных алфавитов, этим методам для построения теста достаточно одномерной активизации путей в схеме. Следует отметить, что чем больше мощность алфавита, тем дальше удается отодвинуть "перебор" вариантов и тем самым сузить пространство поиска в процессе генерации тестового набора. В этом смысле универсальный алфавит $$B_{16}$$ представляет существенно большие возможности, чем остальные рассмотренные алфавиты. Поэтому по мере развития методов построения тестов значность используемых алфавитов постоянно растет. Далее мы рассмотрим метод построения тестов для последовательностных схем в 16-значном алфавите, который является развитием метода, изложенного в лекции 20.

Как было сказано выше, наиболее распространенный на практике подход к построению тестов для последовательностных устройств основан на преобразовании его в так называемый комбинационный эквивалент, получаемый путем условного обрыва обратных связей [23.1-23.3,23.6,23.8-23.11]. При построении теста для данной неисправности проводится активизация путей с помощью многозначных алфавитов до одного из выходов последней копии ИКС. Число копий $$k$$ определяется из условий активизации путей и при необходимости может наращиваться. Различают два основных подхода к решению этой задачи: прямой и обратный [23.7-23.10]. В большинстве случаев применяется обратный подход, при котором в случае невозможности решения задачи при данном числе копий они наращиваются в обратном направлении (от $$k$$ до $$k-1$$,$$k-2$$ и т. д.). Пример обратного подхода приведен в предыдущем разделе 23.1 данной лекции (рис. 23.5, 23.6).

При прямом подходе копии наращиваются в прямом порядке (от $$1$$ ко $$2, 3,\ldots, k-1, k$$). Иногда применяется и смешанная стратегия. Например, процедура D-распространения выполняется в прямом порядке, а процедура подтверждения и установки схемы в необходимое состояние в обратном порядке. Каждый из этих подходов имеет свои преимущества и недостатки.

Мы будем применять прямой подход и метод генерации тестов в универсальном алфавите $$B_{16}$$ [лекции 20, и требует меньшего числа дополнительных процедур. С другой стороны, этот подход при реализации использует больше оперативной памяти.

Когда начинается процесс генерации теста, неизвестно, какое из четырех значений алфавита $$B_4$$ может иметь место, и предполагается, что на каждой линии устройства возможны любые комбинации значений сигналов: $$00, 01, 10, 11$$. Поэтому сначала всем линиям схемы присваивается неопределенное значение u алфавита $$B_{16}$$. Затем, используя свойства структуры схемы и знание местоположения данной неисправности, исключают ненужные (или невозможные) комбинации сигналов для линий ЦУ, снимая, таким образом, неопределенность. Прежде всего всем линиям схемы, на которые неисправность не оказывает влияния, необходимо присвоить значение $$C$$ (возможны только две комбинации $$00, 11$$). Описанные действия называются структурной импликацией. После этого необходимо внести влияние неисправности. Для этого можно выполнить условный разрыв на неисправной линии $$x_i$$ и присвоить начальные значения $$x_i =1$$ до разрыва и $$x_i =D$$ после разрыва для константной неисправности $$x_i \equiv 0$$ и соответственно $$x_i =0$$ до разрыва и $$x_i=D'$$ после разрыва для константной неисправности $$x_i\equiv 1$$ (иногда целесообразно присваивать значения $$F0$$ и $$F1$$ вместо $$D$$ и $$D'$$) [23.1,23.12].

При структурной импликации учитывались только топологические свойства схемы. Кроме того, необходимо использовать и свойства логических элементов [23.1,лекция 7) для вентиля "И" получаем новые значения $$f^0_n=1$$, $$f_n^{D'}=0$$, $$f_n^{D}=1$$, $$f_n^{1}=0$$, т.е. $$f_n=F0$$. Выполнив пересечение кодов старого и нового значений с помощью покомпонентной конъюнкции, получим $$f^{0}= f^{0}\cdot f^{0}_n=0\cdot 1=0$$, $$f^{D'}= f^{D'}\cdot f^{D'}_n=1\cdot 0=0$$, $$f^{D}= f^{D}\cdot f^{D}_n=1\cdot 1=1$$, $$f^{1}= f^{1}\cdot f^{1}_n=0\cdot 0=0$$. Таким образом, в результате прямой логической импликации неопределенность на выходе вентиля уменьшилась до единственной комбинации $$f=D(10)$$. Если в результате покомпонентной конъюнкции получается символ $$\varnothing$$ - $$f^0=0, f^{D'}=0, f^D=0, f^1=0$$, то это говорит о конфликтной ситуации (невозможность ни одной из четырех комбинаций). Аналогично прямая импликация выполняется и для других элементов.

Для обратной импликации следует использовать обратные функции $$a^0, a^{D'}, a^D, a^1$$ из табл. 7.7 (лекция 7), которые позволяют по заданным значениям выхода и одного из входов получить значение второго входа. Поскольку входы основных вентилей симметричны, то функции для второго входа можно получить из функций первого простой заменой переменных. Продолжим наш пример для вентиля "И". Проведя обратную импликацию для входа $$а$$, получим: $$a^0=0, a^{D'}=0, a^D=0, a^1=1(а = 1)$$. В данном случае неопределенность на входе $$а$$ также уменьшилась до одной комбинации - $$1(11)$$. Далее, считая значения $$а$$ и $$f$$ известными, выполняем обратную импликацию для второго входа $$b$$ и получаем: $$b^0=0, b^{D'}=0, b^D=1, b^1=0 (а = 1) ( )$$. Таким образом, в результате прямой и обратной логической импликации на вентиле установились все определенные значения.

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

Далее с помощью описанных выше процедур необходимо, насколько возможно, снять неопределенность и попытаться распространить значения $$D$$ или $$D'$$ до одного из внешних выходов итеративной комбинационной схемы $$Z_{1}$$. В общем случае при этом значения псевдовходов $$Y_{1}$$ должны оставаться равными $$C=\{0\cup 1\}$$ (если неисправность не расположена на линиях обратных связей). Если же вследствие импликации хотя бы одна из переменных $$Y_{1}$$ примет значение 0 или 1, то это означает конфликт по переменным состояний и необходимо искать другое решение. Если для первой копии не удастся распространить значения $$D$$, $$D'$$ до одного из внешних выходов $$Z_{1}$$, необходимо в ИКС добавить вторую копию комбинационного эквивалента и попытаться получить $$D$$, $$D'$$ на выходах второй копии ИКС. В случае неудачи этот процесс продолжается до тех пор, пока на выходе $$Z_{k}$$ не появятся значения $$D$$, $$D'$$ или же число копий $$k$$ превысит максимально допустимое число копий ИКС. В последнем случае неисправность считается избыточной, т.е. непроверяемой (при данной постановке задачи). В случае успеха входные вектора копий ИКС $$X_1,X_2,\ldots,X_k$$ образуют искомую проверяющую последовательность. Следует отметить, что на практике значительная часть последовательностных ЦУ для большинства переменных состояний имеет специальные цепи сброса и это можно использовать при построении теста, установив переменные состояния $$Y_{1}$$ в соответствующие значения. При прямом подходе эту информацию использовать значительно легче (и естественнее, поскольку это ведет к значительному снятию неопределенности в схеме).

Суть метода рассмотрим на примере схемы, приведенной на рис. 23.7. Прежде всего, необходимо выполнить условный обрыв обратных связей и получить комбинационный эквивалент (рис. 23.8). Допустим, что требуется построить тест для константной неисправности $$x_4\equiv 1$$. Структурная импликация для нашего примера дает $$x_{11}= x_{21}= x_{31}= x_{51}=C$$. Затем внесем влияние неисправности, положив $$x_{41}=D'$$. Попытаемся распространить значения $$D, D' $$ до выхода $$z_1$$ (при $$y_1=C$$) сначала для схемы из одного КЭ (рис. 23.8). Можно убедиться, что для данной неисправности это невозможно сделать. Но для псевдовыхода $$\tilde{y}_1$$, как показано на рис. 23.8, можно снизить неопределенность до $$\tilde{y}_1=G1$$ с помощью присваивания входам следующих значений: $$x_{11}=1$$, $$x_{21}=0$$, $$x_{31}=1$$. Затем наращиваем итеративную схему путем дополнения ее второй копией комбинационного эквивалента (рис. 23.9). Вносим влияние неисправности во вторую копию, полагая $$x_{42}=D'$$, и имеем теперь неисправность с кратностью $$2$$. Попытаемся распространить значения $$D, D' $$ к выходу $$z_2$$. На этот раз это удается сделать с помощью значений входов второй копии: $$x_{12}=1$$, $$x_{22}=0$$, $$x_{32}=1$$. Таким образом, получаем проверяющую последовательность $$x_{11}=1$$, $$x_{2}^1=0$$, $$x_{31}=1$$; $$x_{12}=1$$, $$x_{22}=0$$, $$x_{32}=1$$ длиной в два набора для данной неисправности.