21.1 Выполнимость булевых функций
Рассмотренные ранее методы построения проверяющих тестов для заданной неисправности комбинационной схемы можно разбить на два класса:
структурные методы, осуществляющие поиск решения непосредственно по логической схеме на основе активизации путей;
аналитические методы, где построение теста выполняется путем манипуляций с формулами (метод различающей функции и булевых производных).
Относительно недавно разработан метод построения тестов на основе решения задачи выполнимости булевых функций [21.1], который занимает промежуточное положение между этими двумя подходами.
Здесь строится различающая функция между булевыми функциями, реализующими исправную и неисправную схемы, которая далее преобразуется в конъюнктивную нормальную форму (КНФ) и решается задачи выполнимости КНФ.
Рассмотрим задачу построения КНФ по заданной логической схеме [21.1,21.2]. Для начала возьмем уравнение $$Z=X$$ .
В логических терминах это уравнение эквивалентно следующему: $$(Z\to X)\cdot(X\to Z)$$. Но в выражение $$(Z\to X)$$ эквивалентно $$(\overline{Z}\vee X)$$, поэтому $$(Z\to X)\cdot(X\to Z)$$ можно представить в виде $$(\overline{Z}\vee X) (Z\vee \overline{X})$$. Заметим, чтобы это выражение приняло значение "истина", необходимо чтобы оба значения $$Z$$ и $$X$$ были истинны, либо наоборот оба значения были ложными.
Далее рассмотрим уравнение $$(Z=X\cdot Y)$$ для вентиля И, которое можно преобразовать к виду $$(Z\to X\cdot Y)\cdot(X\cdot Y\to Z)$$ [21.1,21.2]. Действуя по приведенной выше схеме, на следующем шаге получаем
$$
(\overline{Z}\vee X\cdot Y)\cdot(\overline{X}\overline{Y}\vee Z)=
(\overline{Z}\vee X)\cdot(\overline{Z}\vee Y)\cdot(\overline{X}\vee \overline{Y}\vee Z)$$
В полученной КНФ отдельные дизъюнкты (сомножители) могут иметь один, два или три терма ("слагаемых"). Известно[21.1,21.2], что подобные преобразования можно выполнить для типовых логических вентилей - окончательные результаты представлены в табл. 21.1
| Формула |
Тип вентиля |
| |
буфер |
| |
инвертор |
| |
Двухвходовой И |
| |
Двухвходовой НЕ-И |
| |
Двухвходовой ИЛИ |
| |
Двухвходовой НЕ-ИЛИ |
| |
Двухвходовой ИЛИ |
Далее перейдем от преобразования отдельных логических элементов к схеме в целом на примере схемы рис. 21.1[21.2]. Здесь исходная (исправная) схема выделена пунктиром.
(рис 21.1) Пример схемы для проверки выполнимости булевых функций.
Поведение этой (исправной) схемы может быть описано с помощью следующей КНФ
$$
(\overline{n}_1\vee A)\cdot(\overline{n}_1\vee B)\cdot(\overline{A}\vee\overline{B}\vee n_1)\cdot(\overline{n}_2\vee C)\cdot(\overline{n}_2\vee D)\cdot(\overline{C}\vee\overline{D}\vee n_2)\cdot\\
(Z\vee\overline{n}_1)\cdot(Z\vee\overline{n}_2)\cdot(n_1\vee n_2\vee\overline{Z})$$
которая построена с помощью приведенных выше преобразований. Отметим, что здесь наряду с входными переменными $$(A, B, C, D)$$ содержатся и "внутренние" переменные $$(n_{1}, n_{2}, Z)$$, которые ассоциированы с внутренними линиями схемы.
Далее перейдем, к задаче построения проверяющего теста на примере константной неисправности $$C\equiv 1$$. Согласно методу различающей функции мы должны решить булево уравнение $$Z\oplus Z^{*}=1$$, где $$Z^{*}$$ описывает поведение неисправной схемы. На рис. 21.1 представлена схема, которая реализует эту различающую функцию. Заметим, что здесь исправная и неисправная схемы содержат общую подсхему. Далее по изложенной выше методике с использованием преобразований табл. 21.1 построим КНФ для схемы рис. 21.1
$$
(\overline{n}_1\vee A)\cdot
(\overline{n}_1\vee B)\cdot
(\overline{A}\vee\overline{B}\vee n_1)\cdot
(\overline{n}_2\vee C)\cdot
(\overline{n}_2\vee D)\cdot
(\overline{C}\vee\overline{D}\vee n_2)\cdot\\
(Z\vee\overline{n}_1)\cdot
(Z\vee n_2)\cdot
(n_1\cdot n_2\cdot \overline{Z})\cdot\\
(\overline{n'}_2\vee C')\cdot
(\overline{n'}_2\vee D)\cdot
(\overline{C'}\vee\overline{D}\vee n'_2)\cdot
(C')\cdot
(Z^{*}\vee\overline{n'}_1)\cdot
(Z^{*}\vee\overline{n'}_2)\cdot
(n_1\vee n'_2\vee\overline{Z}^{*})\cdot\\
(\overline{Z}\vee Z^{*}\vee BD)\cdot
(Z\vee\overline{Z}^{*}\vee BD)\cdot
(\overline{Z}\vee\overline{Z}^{*}\vee \overline{BD})\cdot
(Z\vee {Z}^{*}\vee \overline{BD})$$
В полученной формуле первые две строки соответствуют исправной схеме, которая на рис. 21.1 выделена пунктиром. Третья строка соответствует неисправной схеме. Отметим, что здесь включено дополнительное требование на активизацию неисправности в виде терма $$C'$$, который принимает значение "истина" при $$C'=1$$. Наконец, четвертая строка представляет элемент исключающее ИЛИ (сумма по mod2). Конечно, для маленькой схемы рис. 21.1 это выражение достаточно громоздко, но методы решения выполнимости булевых функций и высокая производительность компьютерных систем позволяют решать задачу генерации тестов для реальных больших схем. Решением, то есть проверяющим тестовым набором является множество значений входных переменных, обращающих КНФ в 1.
Эффективность решения выполнимости булевых функций зависит от числа термов в дизъюнктах. Известно, что в общем случае (произвольного числа термов в дизъюнктах) эта задача является NP-полной (относительно числа переменных) то есть имеет экспоненциальную сложность. Решение полиномиальной сложности имеет случай 1- и 2-выполнимости, когда число термов в любом дизъюнкте не превышает 1 или 2. Для 2-выполнимости известен эффективный алгоритм на основе метода резолюций [21.3]. Для 3-выполнимости задача уже является NP-полной. Задача с произвольным числом термов может быть сведена к 3-выполнимости[21.3]. Заметим, что для нашого примера схема содержит логические элементы, имеющие два входа. Потому, согласно табл..21.1, построенная КНФ в этом случае имеет 66,6% дизъюнктов с двумя термами. На практике 80% или даже 90% дизъюнктов имеют два терма. Поэтому часто при построении тестов используется следующий подход к решению задачи выполнимости:
находятся значения переменных, входящие в дизъюнкты с двумя термами;
дизъюнкты с тремя термами используются в качестве ограничений.
Подобный подход используется в [21.1,21.2] на основе линейного алгоритма для 2- выполнимости [21.4] следующим образом. Определяется массив $$V$$ для 2-КНФ переменных, входящих в дизъюнкты с 2 термами. Массив определяет порядок обработки этих переменных. Используется указатель $$i$$, который указывает на первую неограниченную переменную и инициализируется в 0. Переменная $$dir$$ используется для хранения текущего направления обработки (прямой или обратный порядок).
В течение обработки $$i>0$$ и последовательность ограниченных значений $$V[0], V[1],…, V[i-1]$$ представляет текущий префикс $$V$$. Все элементы массива $$V$$, которые больше или равны 0 и меньше $$i$$ являются ограниченными. Целью является множество двоичных значений переменных $$V$$, которые совместимы с дизъюнктами, содержащими 3 терма. При этом в случае несовместимости это желательно обнаружить как можно раньше. Укрупненный псевдокод алгоритма решения выполнимости КНФ представлен ниже на рис. 21.2.
SAT()
{
dir=0; // устанавливается прямой порядок
V=NULL; // все переменные неограниченны
i=0; // значение указателя на первую неограниченную переменную
for(;;) {
if(dir=прямой порядок) {
for(;i<размер V;i=i+1)
if(V[i] ограничена)
break;
if(i==размер V)
return(успех);
V[i-1]=0;
Выполнение импликации V[i-1];
i =i+1;
}
else { // dir=обратный порядок
if(i==0)
return(неудача);
temp=V[i]; // сохранение последнего значения
отменить импликацию V[i-1];
}
else
i=i-1;
}
if(нет нулевого дизъюнкта)
dir= прямой порядок;
else
dir= обратный порядок;
}
}
Поиск решения прекращается если:
Найдены значения, при которых булева функция выполнима;
Доказано, что таких значений не существует;
Превышены ограничения по выделенным вычислительным ресурсам.
Представленный алгоритм является полным - то есть он гарантирует построение тестового набора для не избыточной неисправности в комбинационной схеме или показывает ее избыточность. Однако для ускорения поиска можно ввести в КНФ некоторые дополнительные дизъюнкты, которые позволяют сузить пространство поиска решений. Подобно структурным методам эти дизъюнкты могут отражать топологию схемы и некоторые эвристики [21.1].
Как отмечалось в предыдущей лекции, где представлен метод SOCRATES, на этапе препроцессорной обработки можно найти нелокальные импликации, которые позволяют сократить число откатов в процессе поиска и тем самым его ускорить. Напомним, что для схемы рис. 19.9 имеет место нелокальная импликация: если $$A=1$$, то отсюда следует $$D=1$$, и наоборот, равенство $$D=0$$ имплицирует $$A=0$$. В соответствии с этим, в КНФ схемы можно явным образом добавить дизъюнкт $$(\overline{A}\vee D)$$, что в результате дает для схемы следующую КНФ
$$
(E\vee \overline{B})\cdot(E\vee\overline{A})\cdot(\overline{E}\vee A\vee B)\cdot\\
(F\vee\overline{A})\cdot(F\vee\overline{C})\cdot(\overline{F}\vee A\vee C)\cdot\\
(\overline{D}\cdot E)\cdot(\overline{D}\vee F)\cdot(D\vee\overline{E}\vee\overline{F})\cdot\\
(A\vee\overline{D})$$
Таким образом, можно дополнительно ввести нелокальные импликации. Однако, на практике они обычно вводятся в случае неудачи с использованием основной КНФ поскольку требуют дополнительных ресурсов.
Кроме этого, можно дополнительно ввести информацию об активизированных путях в схеме, которая используется в структурных методах. Если неисправность обнаружима, то существует, по крайней мере, один активизированный путь между неисправной линией и выходом схемы. Таких путей может быть несколько, но мы выбираем только один активный путь. Каждую линию этого пути назовем активной линией. Для определения активного пути мы для каждого элемента (входящего в путь) дополнительно вводим дизъюнкты, которые для каждой линии этого пути используют вспомогательные переменные. При этом для переменной $$X$$ вводится активная переменная $$Act_{X}$$ .
Для каждого вентиля с входом $$X$$ и выходом $$Y$$ (входящими в активный путь) мы добавляем дизъюнкт $$(\overline{ Act_{X}}\vee Act_{Y})$$, который показывает, что если активно $$X$$, то активно $$Y$$. Для элемента, имеющего несколько выходов (например, разветвление) со входом $$X$$ и выходами $$Y$$, $$Z$$ добавляем дизъюнкт $$(\overline{ Act_{X}}\vee Act_{Y}\vee Act_{Z})$$ (если активно $$X$$, то активно $$Y$$ или $$Z$$). На рис. 21.2, 21.3 представлены примеры таких дизъюнктов.
(рис 21.2)
Если активно $$X$$, то должно быть активно $$(\overline{Act_{X}}\vee Act_{Y})$$.
(рис 21.3)
Если активно $$X$$, то должно быть активно $$X_{1}$$ или $$X_{2}$$ :
$$
(\overline{Act_{X}}\vee Act_{X_1}\vee Act_{X_2}).$$
Введение таких дизъюнктов может существенно повысить эффективность системы генерации тестов.
Если вентиль входит в активный путь, то его входы должны иметь неконтролирующие значения, которые позволяют распространять влияние неисправности. Например для вентиля И ни один из неактивных входов не должен иметь значение 0, которое блокирует активизацию. С другой стороны, неактивный вход вентиля И, входящего в активный путь, может также иметь различные сигналы для исправной и неисправной схемы. При этом значения сигналов могут быть согласованы инее согласованы. Эта ситуация показана на рис. 21.4 и рис. 21.5.
(рис 21.4) Согласованная разница сигналов.
(рис 21.5) Не согласованная разница сигналов.
На этом основании мы можем добавить дизъюнкты , требующие неконтролирующих значений. Например, для вентиля ИЛИ с активным входом $$D$$ и неактивным $$E$$ можно вести дизъюнкт $$(\overline{Act_{D}}\vee \overline{E})$$ (если $$D$$ активно, то и $$E$$ должно быть активно).
Отметим, что учет требования неконтролирующих значений для входов активных элементов в структурных методах имеет очень большое значение, в данном методе это не так, но они позволяют сузить пространство поиска решений.
Кроме этого, на этапе препроцессорной обработки можно идентифицировать линии уникальной активизации для каждой неисправности и добавить в КНФ активные дизъюнкты для каждого вентиля. Например, для схемы рис. 19.9 аналогично дополнительному дизъюнкту $$(\overline{A}\vee D) $$ можно генерировать дизъюнкт $$(\overline{Act_{A}}\vee Act_D)$$, который показывает, что если $$B$$ активно, то $$D$$ также должно быть активно.
В некоторых случаях в КНФ можно удалить отдельные переменные, если это не вредит окончательному решению. Будем говорить, что переменная $$V$$ определяет переменную $$W$$, если присваивание $$V$$ значения 0 или 1 ведет к тому, что переменная $$W$$ везде входит в формулу либо с отрицанием, либо без него.
В этом случае мы можем удалить из формулы все дизъюнкты, содержащие $$W$$, и отложить присваивание переменной $$W$$ до тех пор, пока не будет определено окончательное значение для $$V$$. Например, все дизъюнкты, содержащие $$A$$,$$B$$,$$C$$ могут быть удалены из КНФ схемы рис. 21.6.
$$
(E\vee B)\cdot(E\vee C)\cdot(\overline{E}\vee\overline{B}\vee\overline{C})\cdot\\
(E\vee\overline{E_1})\cdot(\overline{E}\vee E_1)\cdot(E\vee\overline{E_2})\cdot(\overline{E}\vee E_2)\cdot\\
(F\vee A)\cdot(F\vee E_1)\cdot(\overline{F}\vee\overline{A}\vee\overline{E_1})\cdot\\
(G\vee F)\cdot(G\vee E_2)\cdot(\overline{G}\vee\overline{F}\vee\overline{E_2})$$
В заключение, отметим, что порядок рассмотрения переменных в процессе решения влияет на его скорость. Поэтому, иногда предварительно определяется порядок рассмотрения переменных, что также способствует улучшению характеристик алгоритма.
(рис 21.6) Все дизъюнкты, содержащие A,B,C могут быть удалены из КНФ.
21.2 Бинарные диаграммы в генерации тестов
Бинарные диаграммы решений (binary diagrams decisions -BDD), приведенные в [лекции 2.1.3, широко применяются в проектировании цифровых систем [21.6,21.7]. В отечественной литературе, кроме термина BDD, также часто используется термин "альтернативные графы"[21.8]. Эта модель применятся также и при решении задач диагностики цифровых систем, в первую очередь, генерации тестов, где пионером является Р.Убар [21.8].]
Отметим, что бинарные диаграммы (альтернативные графы - АГ) позволяют представлять ЦУ на различных уровнях[21.8]: 1) структурном, где сохраняется структура исходной логической схемы; 2) функциональном, где структурные соотношения исходной схемы не сохраняются, благодаря чему они имеют меньшую сложность;3) уровне ЯРП, где терминальные вершины могут помечаться переменными, соответствующими регистрам или шинам.
Модель бинарных диаграмм достаточно удобна (и эффективна) при решении многих задач диагностики цифровых систем, таких как:
моделирование исправных логических схем в двоичном и многозначных алфавитах;
анализ тестов - моделирование неисправностей с оценкой полноты;
генерация тестов с использованием процедур распространения влияния неисправностей (fault propagation), подтверждения (justification) и импликации.
В конечном счете, эти задачи сводятся к стандартным процедурам отслеживания (трассировки) или поиска определенных путей на ориентированных графах.
Бинарные диаграммы при решении задачи построения проверяющих тестов можно использовать по-разному, и для этого предложены различные подходы. Наиболее очевидным (прямолинейным) является применение бинарной диаграммы для схемы, которая реализует различающую функцию $$D(\varphi,X)$$ (исключающее ИЛИ для функций, реализующих исправную и неисправную схемы) [21.2].
Этот подход близок к изложенному в предыдущем разделе методу, основанному на решении задачи выполнимости. Различие в том, что при решении логического уравнения $$D(\varphi,X)=1$$в первом случае используется представление схемы в виде КНФ и методы решения задачи выполнимости, а во втором случае - представление схемы в виде бинарной диаграммы и методы анализа и поиска путей на графах. Рассмотрим этот подход на примере схемы рис. 21.7 [21.2].
(рис 21.7) Пример схемы для метода бинарной диаграммы.
(рис 21.8) Приведенная бинарная диаграмма исправной схемы рис. 21.7.
На следующем рис. 21.8 представлена приведенная (сокращенная) бинарная диаграмма для этой исправной схемы. Далее на рис. 21.9 показана бинарная диаграмма этой же схемы с константной неисправностью на третьем сверху входе вентиля $$K$$. На следующем рис. 21.10 представлена приведенная бинарная диаграмма для различающей функции двух предыдущих схем [21.2]. Детали преобразований можно найти в [21.2].
(рис 21.9) Приведенная бинарная диаграмма для неисправной схемы.
(рис 21.10) Приведенная бинарная диаграмма для различающей функции.
Далее необходимо решить логическое уравнение $$D(\varphi,X)=1$$, где различающая функция $$D(\varphi,X)$$ задана в виде бинарной диаграммы (для нашего примера рис. 21.10). Решение этого уравнению сводится к поиску пути на соответствующем графе, связывающего корень диаграммы (верхний уровень) с единичной вершиной 1 (нижнего уровня).
Для нашего примера это может быть путь (1,2,3,4,1), что соответствует значениям входных переменных $$I_{1}=1$$, $$I_{2}=1$$, $$I_{3}=1$$, $$I_{4}=0$$.
В сжатой форме всевозможные значения тестовых наборов, описывающие все пути на бинарной диаграмме, можно представить выражением $$I_1\cdot I_2\cdot(I_3 +I_4)$$
Другой подход к построению тестов состоит в том, что генерируются входные наборы, которые активизируют все пути на двоичной диаграмме. Рассмотрим это на примере схемы рис. 21.11 [21.2]. Здесь на рис. 21.11а) показана функциональная бинарная диаграмма, а на рис. 21.11б) схемная реализация этой функции на основе мультиплексоров.
(рис 21.11) Бинарная диаграмма и ее реализация на основе мультиплексоров.
Для рис. 21.11а) множество значений входных переменных $$x_{1}, x_{2}, x_{3}$$, которые активизируют все пути на диаграмме составляют $$\{0u0, 0u1, 100, 101, 11u\}$$. Отметим, что поскольку генерации теста используется функциональный бинарный граф, который не отражает структурные свойства схемы, то эти тестовые наборы гарантируют проверку константных неисправностей только на внешних входах схемы рис. 21.11б). Этот тест не гарантирует проверку константных неисправностей на внутренних линиях этой схемы.
Отметим, что модель бинарных диаграмм позволяет использовать следующие модели неисправностей, которые ориентированы непосредственно на эту модель [21.9]:
дуга узла всегда активна;
обрыв дуги узла;
вместо данной дуги активна другая дуга (или множество дуг).
В этих моделях "ломается" не схема, а представляющая ее бинарная диаграмма. Это приводит к появлению и изменению путей в соответствующем графе. Известны работы, где бинарные диаграммы и подобные модели применяются при построении тестов микропроцессорных систем [21.9,21.10].
В [21.10] предложен также подход, основанный на покрытии путей в бинарной диаграмме. Основу теста здесь составляют 0-эксперименты (пути из корневой вершины в нулевую вершину) и 1-эксперименты (пути из корневой вершины в единичную вершину). Например, для бинарной диаграммы рис. 21.12 [21.2] 0-эксперименты составляют $$\{00u, 011, 1u0\}$$, где значения приведены в порядке входных переменных $$(A,B,C)$$. Аналогично 1-эксперимент составляют $$\{010, 1x1\}$$. На рис. 21.12 видно, что 1-эксперименты активизируют соответствующие пути, заканчивающиеся в нулевой или единичной выходной вершине. Напомним, что "жирная" точка на диаграмме соответствует инверсии значения.
(рис 21.12) Пример бинарной диаграммы для 0-,1-экспериментов.
Авторы [21.10] при построении теста рассматривают так называемые "боковые эффекты" текущего эксперимента, в которые входят другие эксперименты, чьи выходные значения противоположны текущему и некотрые позиции отличны от исходного эксперимента. Например, для текущего 1-эксперимента $$\{011\}$$ ожидаемый выход равен 0.
Тогда в "боковой эффект" входит эксперимент $$\{010\}$$. Это означает, что константная неисправность $$C\equiv 0$$ вызывает 1 на выходе. С другой стороны для текущего 0-эксперимента $$\{00u\}$$ ожидаемый выход равен 0. В этом случае в "боковой эффект" входит експеримент $$\{010\}$$ поскольку изменяет 0-ребро из B на 1-ребро . Тогда при константной неисправности $$C\equiv 0$$ выход равен 1, что говорит об ее обнаружении.
21.3 Сжатие тестов
На последнем этапе генерации тестов анализируются и объединяются фрагменты тестов, полученных на разных этапах и для различных неисправностей. При этом часто выполняется моделирование неисправностей входных наборов построенного теста в порядке, обратном их генерации. То есть тесты, построенные во второй фазе, моделируются первыми, а затем обрабатываются тесты, полученные в первой фазе. При этом контролируется полнота тестов. Когда полнота достигает 100% (или заданной величины), оставшиеся входные наборы из первой фазы исключаются из теста. Таким образом, обычно удается сократить тестовую последовательность. Обуславливается это тем, входные наборы, построенные псевдослучайными методами, как правило, проверяют меньше неисправностей чем, тесты, полученные во второй фазе.
Кроме этого, тесты, построенные во второй фазе, обычно имеют достаточно много входов с неопределенными значениями и это можно использовать для сокращения теста. Два входных тестовых набора называются совместимыми, если они не имеют противоположных (определенных) значений для любых внешних входов. Два совместимых входных тестових набора $$t_{i}$$ и $$t_{j}$$ могут быть объединены в один $$t_{ij}=t_i \cap t_j$$ путем выполнения операции пересечения. При этом множество проверяемых набором $$t_{ij}$$ неисправностей является объединением множеств неисправностей, проверяемых по отдельности наборами $$t_{i}$$ и $$t_{j}$$.
Таким образом, наборы $$t_{i}$$ и $$t_{j}$$ в тесте могут быть заменены $$t_{ij}$$. Этот метод можно использовать итеративно для сокращения теста. Такой процесс называется статическим сокращением тестов. В общем случае результат статического сокращения тестов зависит от порядка, в котором обрабатываются входные наборы.
Например, для теста $$t_{1}=01u$$, $$t_{2}=0u1$$, $$t_{3}=0u0$$, $$t_{4}=u01$$ в том случае, если мы объединим $$t_{1}$$ и $$t_{2}$$, мы получим множество $$t_{12}=011$$, $$t_{3}=0u0$$, $$t_{4}=u01$$, которое далее невозможно сократить. Если же мы сначала объединим $$t_{1}$$ и $$t_{3}$$ , то далее возможно также объединение $$t_{2}$$ и $$t_{4}$$, что дает более короткий тест: $$t_{13}=010$$, $$t_{24}=001$$.
Оптимальное сжатие этим методом требует больших вычислительных ресурсов, так как фактически сводится к перебору различных вариантов решения. Таким образом, статическое сжатие выполняется на этапе постпроцессорной обработки.
(рис 21.13) Динамическое сжатие теста
В отличие от статического, динамическое сжатие выполняется сразу же после построения текущего входного тестового набора путем подбора двоичных значений, которые присваиваются неопределенным входам. На рис. 21.13 приведен псевдокод укрупненного алгоритма динамического сжатия тестовой последовательности. Отметим, что здесь выполняется проверка перспективности текущего тестового набора путем, например, вычисления процента числа входов с неопределенными значениями.
Если текущий тестовый набор $$t$$ перспективен для сжатия, то выбирается вторичная неисправность и значения входов доопределяются таким образом, чтобы она проверилась на $$t$$. Наиболее важным при этом является метод выбора вторичной неисправности. Эксперименты показали, что динамическое сжатие позволяет получить тесты меньшей длины.
Ключевые термины:
Конъюнктивнаян нормальная форма - нормальная форма, в которой булева формула имеет вид конъюнкции нескольких дизъюнкций литералов.
Выполнимость булевой функции - булева функция $$F(X)$$ выполнима, если существует хотя бы один набор значений ее аргументов, такой, что она истинна ($$F(X)=1$$).
Бинарная диаграмма(альтернативный граф) - ациклический ориентированный граф, который представляет булевы функции.
Краткие итоги
В лекции рассмотрены современные методы построения проверяющих тестов для заданной неисправности комбинационной схемы на основе выполнимости булевых функций и бинарных диаграмм.
В [разделе 21.1 изложено приведение задачи построения теста для данной неисправности к конъюктивной нормальной форме. Показано как задача построения проверяющего теста сводится к задаче выполнимости булевой функции. Изложен метод решения задачи выполнимости применительно к построению теста.]
В [разделе 21.2 описано применение бинарных диаграмм (альтернативных графов) к решению задачи построения проверяющего теста. При этом строится бинарная диаграмма различающей функции и далее построение теста сводится к поиску определенного пути на графе. ]
[Раздел 21.3 посвящен задаче сжатия построенных тестов с помощью статических или динамических методов. ]
Вопросы и упражнения
Как можно построить КНФ для логической схемы? Какие преобразования при этом используются? Как строится КНФ для различающей функции? Как эффективность решения выполнимости булевых функций зависит от числа термов в дизъюнктах? Приведите алгоритм решения задачи выполнимости, применяемый при построении теста. Как можно внести в КНФ нелокальные импликации? Как в КНФ можно дополнительно ввести информацию об активизированных путях в схеме? Как можно добавить в КНФ дизъюнкты, учитывающие неконтролирующие значения? При решении каких задач диагностики ЦС можно использовать бинарные диаграммы?
Опишите подход, использующий бинарную диаграмму различающей функции?
К чему сводится поиск тестового набора на бинарной диаграмме?
Какие модели неисправностей можно определить на бинарных диаграммах?
Что такое 0- (1-) эксперименты на бинарной диаграмме?
Зачем нужно сжатие построенных тестов?
Какие подходы существуют к сжатию теста?
Опишите статический подход к сжатию тестов.
Чем динамический подход отличается от статического?
21.1 Выполнимость булевых функций
Рассмотренные ранее методы построения проверяющих тестов для заданной неисправности комбинационной схемы можно разбить на два класса:
структурные методы, осуществляющие поиск решения непосредственно по логической схеме на основе активизации путей;
аналитические методы, где построение теста выполняется путем манипуляций с формулами (метод различающей функции и булевых производных).
Относительно недавно разработан метод построения тестов на основе решения задачи выполнимости булевых функций [21.1], который занимает промежуточное положение между этими двумя подходами.
Здесь строится различающая функция между булевыми функциями, реализующими исправную и неисправную схемы, которая далее преобразуется в конъюнктивную нормальную форму (КНФ) и решается задачи выполнимости КНФ.
Рассмотрим задачу построения КНФ по заданной логической схеме [21.1,21.2]. Для начала возьмем уравнение $$Z=X$$ .
В логических терминах это уравнение эквивалентно следующему: $$(Z\to X)\cdot(X\to Z)$$. Но в выражение $$(Z\to X)$$ эквивалентно $$(\overline{Z}\vee X)$$, поэтому $$(Z\to X)\cdot(X\to Z)$$ можно представить в виде $$(\overline{Z}\vee X) (Z\vee \overline{X})$$. Заметим, чтобы это выражение приняло значение "истина", необходимо чтобы оба значения $$Z$$ и $$X$$ были истинны, либо наоборот оба значения были ложными.
Далее рассмотрим уравнение $$(Z=X\cdot Y)$$ для вентиля И, которое можно преобразовать к виду $$(Z\to X\cdot Y)\cdot(X\cdot Y\to Z)$$ [21.1,21.2]. Действуя по приведенной выше схеме, на следующем шаге получаем
$$
(\overline{Z}\vee X\cdot Y)\cdot(\overline{X}\overline{Y}\vee Z)=
(\overline{Z}\vee X)\cdot(\overline{Z}\vee Y)\cdot(\overline{X}\vee \overline{Y}\vee Z)$$
В полученной КНФ отдельные дизъюнкты (сомножители) могут иметь один, два или три терма ("слагаемых"). Известно[21.1,21.2], что подобные преобразования можно выполнить для типовых логических вентилей - окончательные результаты представлены в табл. 21.1
| Формула |
Тип вентиля |
| |
буфер |
| |
инвертор |
| |
Двухвходовой И |
| |
Двухвходовой НЕ-И |
| |
Двухвходовой ИЛИ |
| |
Двухвходовой НЕ-ИЛИ |
| |
Двухвходовой ИЛИ |
Далее перейдем от преобразования отдельных логических элементов к схеме в целом на примере схемы рис. 21.1[21.2]. Здесь исходная (исправная) схема выделена пунктиром.
(рис 21.1) Пример схемы для проверки выполнимости булевых функций.
Поведение этой (исправной) схемы может быть описано с помощью следующей КНФ
$$
(\overline{n}_1\vee A)\cdot(\overline{n}_1\vee B)\cdot(\overline{A}\vee\overline{B}\vee n_1)\cdot(\overline{n}_2\vee C)\cdot(\overline{n}_2\vee D)\cdot(\overline{C}\vee\overline{D}\vee n_2)\cdot\\
(Z\vee\overline{n}_1)\cdot(Z\vee\overline{n}_2)\cdot(n_1\vee n_2\vee\overline{Z})$$
которая построена с помощью приведенных выше преобразований. Отметим, что здесь наряду с входными переменными $$(A, B, C, D)$$ содержатся и "внутренние" переменные $$(n_{1}, n_{2}, Z)$$, которые ассоциированы с внутренними линиями схемы.
Далее перейдем, к задаче построения проверяющего теста на примере константной неисправности $$C\equiv 1$$. Согласно методу различающей функции мы должны решить булево уравнение $$Z\oplus Z^{*}=1$$, где $$Z^{*}$$ описывает поведение неисправной схемы. На рис. 21.1 представлена схема, которая реализует эту различающую функцию. Заметим, что здесь исправная и неисправная схемы содержат общую подсхему. Далее по изложенной выше методике с использованием преобразований табл. 21.1 построим КНФ для схемы рис. 21.1
$$
(\overline{n}_1\vee A)\cdot
(\overline{n}_1\vee B)\cdot
(\overline{A}\vee\overline{B}\vee n_1)\cdot
(\overline{n}_2\vee C)\cdot
(\overline{n}_2\vee D)\cdot
(\overline{C}\vee\overline{D}\vee n_2)\cdot\\
(Z\vee\overline{n}_1)\cdot
(Z\vee n_2)\cdot
(n_1\cdot n_2\cdot \overline{Z})\cdot\\
(\overline{n'}_2\vee C')\cdot
(\overline{n'}_2\vee D)\cdot
(\overline{C'}\vee\overline{D}\vee n'_2)\cdot
(C')\cdot
(Z^{*}\vee\overline{n'}_1)\cdot
(Z^{*}\vee\overline{n'}_2)\cdot
(n_1\vee n'_2\vee\overline{Z}^{*})\cdot\\
(\overline{Z}\vee Z^{*}\vee BD)\cdot
(Z\vee\overline{Z}^{*}\vee BD)\cdot
(\overline{Z}\vee\overline{Z}^{*}\vee \overline{BD})\cdot
(Z\vee {Z}^{*}\vee \overline{BD})$$
В полученной формуле первые две строки соответствуют исправной схеме, которая на рис. 21.1 выделена пунктиром. Третья строка соответствует неисправной схеме. Отметим, что здесь включено дополнительное требование на активизацию неисправности в виде терма $$C'$$, который принимает значение "истина" при $$C'=1$$. Наконец, четвертая строка представляет элемент исключающее ИЛИ (сумма по mod2). Конечно, для маленькой схемы рис. 21.1 это выражение достаточно громоздко, но методы решения выполнимости булевых функций и высокая производительность компьютерных систем позволяют решать задачу генерации тестов для реальных больших схем. Решением, то есть проверяющим тестовым набором является множество значений входных переменных, обращающих КНФ в 1.
Эффективность решения выполнимости булевых функций зависит от числа термов в дизъюнктах. Известно, что в общем случае (произвольного числа термов в дизъюнктах) эта задача является NP-полной (относительно числа переменных) то есть имеет экспоненциальную сложность. Решение полиномиальной сложности имеет случай 1- и 2-выполнимости, когда число термов в любом дизъюнкте не превышает 1 или 2. Для 2-выполнимости известен эффективный алгоритм на основе метода резолюций [21.3]. Для 3-выполнимости задача уже является NP-полной. Задача с произвольным числом термов может быть сведена к 3-выполнимости[21.3]. Заметим, что для нашого примера схема содержит логические элементы, имеющие два входа. Потому, согласно табл..21.1, построенная КНФ в этом случае имеет 66,6% дизъюнктов с двумя термами. На практике 80% или даже 90% дизъюнктов имеют два терма. Поэтому часто при построении тестов используется следующий подход к решению задачи выполнимости:
находятся значения переменных, входящие в дизъюнкты с двумя термами;
дизъюнкты с тремя термами используются в качестве ограничений.
Подобный подход используется в [21.1,21.2] на основе линейного алгоритма для 2- выполнимости [21.4] следующим образом. Определяется массив $$V$$ для 2-КНФ переменных, входящих в дизъюнкты с 2 термами. Массив определяет порядок обработки этих переменных. Используется указатель $$i$$, который указывает на первую неограниченную переменную и инициализируется в 0. Переменная $$dir$$ используется для хранения текущего направления обработки (прямой или обратный порядок).
В течение обработки $$i>0$$ и последовательность ограниченных значений $$V[0], V[1],…, V[i-1]$$ представляет текущий префикс $$V$$. Все элементы массива $$V$$, которые больше или равны 0 и меньше $$i$$ являются ограниченными. Целью является множество двоичных значений переменных $$V$$, которые совместимы с дизъюнктами, содержащими 3 терма. При этом в случае несовместимости это желательно обнаружить как можно раньше. Укрупненный псевдокод алгоритма решения выполнимости КНФ представлен ниже на рис. 21.2.
SAT()
{
dir=0; // устанавливается прямой порядок
V=NULL; // все переменные неограниченны
i=0; // значение указателя на первую неограниченную переменную
for(;;) {
if(dir=прямой порядок) {
for(;i<размер V;i=i+1)
if(V[i] ограничена)
break;
if(i==размер V)
return(успех);
V[i-1]=0;
Выполнение импликации V[i-1];
i =i+1;
}
else { // dir=обратный порядок
if(i==0)
return(неудача);
temp=V[i]; // сохранение последнего значения
отменить импликацию V[i-1];
}
else
i=i-1;
}
if(нет нулевого дизъюнкта)
dir= прямой порядок;
else
dir= обратный порядок;
}
}
Поиск решения прекращается если:
Найдены значения, при которых булева функция выполнима;
Доказано, что таких значений не существует;
Превышены ограничения по выделенным вычислительным ресурсам.
Представленный алгоритм является полным - то есть он гарантирует построение тестового набора для не избыточной неисправности в комбинационной схеме или показывает ее избыточность. Однако для ускорения поиска можно ввести в КНФ некоторые дополнительные дизъюнкты, которые позволяют сузить пространство поиска решений. Подобно структурным методам эти дизъюнкты могут отражать топологию схемы и некоторые эвристики [21.1].
Как отмечалось в предыдущей лекции, где представлен метод SOCRATES, на этапе препроцессорной обработки можно найти нелокальные импликации, которые позволяют сократить число откатов в процессе поиска и тем самым его ускорить. Напомним, что для схемы рис. 19.9 имеет место нелокальная импликация: если $$A=1$$, то отсюда следует $$D=1$$, и наоборот, равенство $$D=0$$ имплицирует $$A=0$$. В соответствии с этим, в КНФ схемы можно явным образом добавить дизъюнкт $$(\overline{A}\vee D)$$, что в результате дает для схемы следующую КНФ
$$
(E\vee \overline{B})\cdot(E\vee\overline{A})\cdot(\overline{E}\vee A\vee B)\cdot\\
(F\vee\overline{A})\cdot(F\vee\overline{C})\cdot(\overline{F}\vee A\vee C)\cdot\\
(\overline{D}\cdot E)\cdot(\overline{D}\vee F)\cdot(D\vee\overline{E}\vee\overline{F})\cdot\\
(A\vee\overline{D})$$
Таким образом, можно дополнительно ввести нелокальные импликации. Однако, на практике они обычно вводятся в случае неудачи с использованием основной КНФ поскольку требуют дополнительных ресурсов.
Кроме этого, можно дополнительно ввести информацию об активизированных путях в схеме, которая используется в структурных методах. Если неисправность обнаружима, то существует, по крайней мере, один активизированный путь между неисправной линией и выходом схемы. Таких путей может быть несколько, но мы выбираем только один активный путь. Каждую линию этого пути назовем активной линией. Для определения активного пути мы для каждого элемента (входящего в путь) дополнительно вводим дизъюнкты, которые для каждой линии этого пути используют вспомогательные переменные. При этом для переменной $$X$$ вводится активная переменная $$Act_{X}$$ .
Для каждого вентиля с входом $$X$$ и выходом $$Y$$ (входящими в активный путь) мы добавляем дизъюнкт $$(\overline{ Act_{X}}\vee Act_{Y})$$, который показывает, что если активно $$X$$, то активно $$Y$$. Для элемента, имеющего несколько выходов (например, разветвление) со входом $$X$$ и выходами $$Y$$, $$Z$$ добавляем дизъюнкт $$(\overline{ Act_{X}}\vee Act_{Y}\vee Act_{Z})$$ (если активно $$X$$, то активно $$Y$$ или $$Z$$). На рис. 21.2, 21.3 представлены примеры таких дизъюнктов.
(рис 21.2)
Если активно $$X$$, то должно быть активно $$(\overline{Act_{X}}\vee Act_{Y})$$.
(рис 21.3)
Если активно $$X$$, то должно быть активно $$X_{1}$$ или $$X_{2}$$ :
$$
(\overline{Act_{X}}\vee Act_{X_1}\vee Act_{X_2}).$$
Введение таких дизъюнктов может существенно повысить эффективность системы генерации тестов.
Если вентиль входит в активный путь, то его входы должны иметь неконтролирующие значения, которые позволяют распространять влияние неисправности. Например для вентиля И ни один из неактивных входов не должен иметь значение 0, которое блокирует активизацию. С другой стороны, неактивный вход вентиля И, входящего в активный путь, может также иметь различные сигналы для исправной и неисправной схемы. При этом значения сигналов могут быть согласованы инее согласованы. Эта ситуация показана на рис. 21.4 и рис. 21.5.
(рис 21.4) Согласованная разница сигналов.
(рис 21.5) Не согласованная разница сигналов.
На этом основании мы можем добавить дизъюнкты , требующие неконтролирующих значений. Например, для вентиля ИЛИ с активным входом $$D$$ и неактивным $$E$$ можно вести дизъюнкт $$(\overline{Act_{D}}\vee \overline{E})$$ (если $$D$$ активно, то и $$E$$ должно быть активно).
Отметим, что учет требования неконтролирующих значений для входов активных элементов в структурных методах имеет очень большое значение, в данном методе это не так, но они позволяют сузить пространство поиска решений.
Кроме этого, на этапе препроцессорной обработки можно идентифицировать линии уникальной активизации для каждой неисправности и добавить в КНФ активные дизъюнкты для каждого вентиля. Например, для схемы рис. 19.9 аналогично дополнительному дизъюнкту $$(\overline{A}\vee D) $$ можно генерировать дизъюнкт $$(\overline{Act_{A}}\vee Act_D)$$, который показывает, что если $$B$$ активно, то $$D$$ также должно быть активно.
В некоторых случаях в КНФ можно удалить отдельные переменные, если это не вредит окончательному решению. Будем говорить, что переменная $$V$$ определяет переменную $$W$$, если присваивание $$V$$ значения 0 или 1 ведет к тому, что переменная $$W$$ везде входит в формулу либо с отрицанием, либо без него.
В этом случае мы можем удалить из формулы все дизъюнкты, содержащие $$W$$, и отложить присваивание переменной $$W$$ до тех пор, пока не будет определено окончательное значение для $$V$$. Например, все дизъюнкты, содержащие $$A$$,$$B$$,$$C$$ могут быть удалены из КНФ схемы рис. 21.6.
$$
(E\vee B)\cdot(E\vee C)\cdot(\overline{E}\vee\overline{B}\vee\overline{C})\cdot\\
(E\vee\overline{E_1})\cdot(\overline{E}\vee E_1)\cdot(E\vee\overline{E_2})\cdot(\overline{E}\vee E_2)\cdot\\
(F\vee A)\cdot(F\vee E_1)\cdot(\overline{F}\vee\overline{A}\vee\overline{E_1})\cdot\\
(G\vee F)\cdot(G\vee E_2)\cdot(\overline{G}\vee\overline{F}\vee\overline{E_2})$$
В заключение, отметим, что порядок рассмотрения переменных в процессе решения влияет на его скорость. Поэтому, иногда предварительно определяется порядок рассмотрения переменных, что также способствует улучшению характеристик алгоритма.
(рис 21.6) Все дизъюнкты, содержащие A,B,C могут быть удалены из КНФ.
21.2 Бинарные диаграммы в генерации тестов
Бинарные диаграммы решений (binary diagrams decisions -BDD), приведенные в [лекции 2.1.3, широко применяются в проектировании цифровых систем [21.6,21.7]. В отечественной литературе, кроме термина BDD, также часто используется термин "альтернативные графы"[21.8]. Эта модель применятся также и при решении задач диагностики цифровых систем, в первую очередь, генерации тестов, где пионером является Р.Убар [21.8].]
Отметим, что бинарные диаграммы (альтернативные графы - АГ) позволяют представлять ЦУ на различных уровнях[21.8]: 1) структурном, где сохраняется структура исходной логической схемы; 2) функциональном, где структурные соотношения исходной схемы не сохраняются, благодаря чему они имеют меньшую сложность;3) уровне ЯРП, где терминальные вершины могут помечаться переменными, соответствующими регистрам или шинам.
Модель бинарных диаграмм достаточно удобна (и эффективна) при решении многих задач диагностики цифровых систем, таких как:
моделирование исправных логических схем в двоичном и многозначных алфавитах;
анализ тестов - моделирование неисправностей с оценкой полноты;
генерация тестов с использованием процедур распространения влияния неисправностей (fault propagation), подтверждения (justification) и импликации.
В конечном счете, эти задачи сводятся к стандартным процедурам отслеживания (трассировки) или поиска определенных путей на ориентированных графах.
Бинарные диаграммы при решении задачи построения проверяющих тестов можно использовать по-разному, и для этого предложены различные подходы. Наиболее очевидным (прямолинейным) является применение бинарной диаграммы для схемы, которая реализует различающую функцию $$D(\varphi,X)$$ (исключающее ИЛИ для функций, реализующих исправную и неисправную схемы) [21.2].
Этот подход близок к изложенному в предыдущем разделе методу, основанному на решении задачи выполнимости. Различие в том, что при решении логического уравнения $$D(\varphi,X)=1$$в первом случае используется представление схемы в виде КНФ и методы решения задачи выполнимости, а во втором случае - представление схемы в виде бинарной диаграммы и методы анализа и поиска путей на графах. Рассмотрим этот подход на примере схемы рис. 21.7 [21.2].
(рис 21.7) Пример схемы для метода бинарной диаграммы.
(рис 21.8) Приведенная бинарная диаграмма исправной схемы рис. 21.7.
На следующем рис. 21.8 представлена приведенная (сокращенная) бинарная диаграмма для этой исправной схемы. Далее на рис. 21.9 показана бинарная диаграмма этой же схемы с константной неисправностью на третьем сверху входе вентиля $$K$$. На следующем рис. 21.10 представлена приведенная бинарная диаграмма для различающей функции двух предыдущих схем [21.2]. Детали преобразований можно найти в [21.2].
(рис 21.9) Приведенная бинарная диаграмма для неисправной схемы.
(рис 21.10) Приведенная бинарная диаграмма для различающей функции.
Далее необходимо решить логическое уравнение $$D(\varphi,X)=1$$, где различающая функция $$D(\varphi,X)$$ задана в виде бинарной диаграммы (для нашего примера рис. 21.10). Решение этого уравнению сводится к поиску пути на соответствующем графе, связывающего корень диаграммы (верхний уровень) с единичной вершиной 1 (нижнего уровня).
Для нашего примера это может быть путь (1,2,3,4,1), что соответствует значениям входных переменных $$I_{1}=1$$, $$I_{2}=1$$, $$I_{3}=1$$, $$I_{4}=0$$.
В сжатой форме всевозможные значения тестовых наборов, описывающие все пути на бинарной диаграмме, можно представить выражением $$I_1\cdot I_2\cdot(I_3 +I_4)$$
Другой подход к построению тестов состоит в том, что генерируются входные наборы, которые активизируют все пути на двоичной диаграмме. Рассмотрим это на примере схемы рис. 21.11 [21.2]. Здесь на рис. 21.11а) показана функциональная бинарная диаграмма, а на рис. 21.11б) схемная реализация этой функции на основе мультиплексоров.
(рис 21.11) Бинарная диаграмма и ее реализация на основе мультиплексоров.
Для рис. 21.11а) множество значений входных переменных $$x_{1}, x_{2}, x_{3}$$, которые активизируют все пути на диаграмме составляют $$\{0u0, 0u1, 100, 101, 11u\}$$. Отметим, что поскольку генерации теста используется функциональный бинарный граф, который не отражает структурные свойства схемы, то эти тестовые наборы гарантируют проверку константных неисправностей только на внешних входах схемы рис. 21.11б). Этот тест не гарантирует проверку константных неисправностей на внутренних линиях этой схемы.
Отметим, что модель бинарных диаграмм позволяет использовать следующие модели неисправностей, которые ориентированы непосредственно на эту модель [21.9]:
дуга узла всегда активна;
обрыв дуги узла;
вместо данной дуги активна другая дуга (или множество дуг).
В этих моделях "ломается" не схема, а представляющая ее бинарная диаграмма. Это приводит к появлению и изменению путей в соответствующем графе. Известны работы, где бинарные диаграммы и подобные модели применяются при построении тестов микропроцессорных систем [21.9,21.10].
В [21.10] предложен также подход, основанный на покрытии путей в бинарной диаграмме. Основу теста здесь составляют 0-эксперименты (пути из корневой вершины в нулевую вершину) и 1-эксперименты (пути из корневой вершины в единичную вершину). Например, для бинарной диаграммы рис. 21.12 [21.2] 0-эксперименты составляют $$\{00u, 011, 1u0\}$$, где значения приведены в порядке входных переменных $$(A,B,C)$$. Аналогично 1-эксперимент составляют $$\{010, 1x1\}$$. На рис. 21.12 видно, что 1-эксперименты активизируют соответствующие пути, заканчивающиеся в нулевой или единичной выходной вершине. Напомним, что "жирная" точка на диаграмме соответствует инверсии значения.
(рис 21.12) Пример бинарной диаграммы для 0-,1-экспериментов.
Авторы [21.10] при построении теста рассматривают так называемые "боковые эффекты" текущего эксперимента, в которые входят другие эксперименты, чьи выходные значения противоположны текущему и некотрые позиции отличны от исходного эксперимента. Например, для текущего 1-эксперимента $$\{011\}$$ ожидаемый выход равен 0.
Тогда в "боковой эффект" входит эксперимент $$\{010\}$$. Это означает, что константная неисправность $$C\equiv 0$$ вызывает 1 на выходе. С другой стороны для текущего 0-эксперимента $$\{00u\}$$ ожидаемый выход равен 0. В этом случае в "боковой эффект" входит експеримент $$\{010\}$$ поскольку изменяет 0-ребро из B на 1-ребро . Тогда при константной неисправности $$C\equiv 0$$ выход равен 1, что говорит об ее обнаружении.
21.3 Сжатие тестов
На последнем этапе генерации тестов анализируются и объединяются фрагменты тестов, полученных на разных этапах и для различных неисправностей. При этом часто выполняется моделирование неисправностей входных наборов построенного теста в порядке, обратном их генерации. То есть тесты, построенные во второй фазе, моделируются первыми, а затем обрабатываются тесты, полученные в первой фазе. При этом контролируется полнота тестов. Когда полнота достигает 100% (или заданной величины), оставшиеся входные наборы из первой фазы исключаются из теста. Таким образом, обычно удается сократить тестовую последовательность. Обуславливается это тем, входные наборы, построенные псевдослучайными методами, как правило, проверяют меньше неисправностей чем, тесты, полученные во второй фазе.
Кроме этого, тесты, построенные во второй фазе, обычно имеют достаточно много входов с неопределенными значениями и это можно использовать для сокращения теста. Два входных тестовых набора называются совместимыми, если они не имеют противоположных (определенных) значений для любых внешних входов. Два совместимых входных тестових набора $$t_{i}$$ и $$t_{j}$$ могут быть объединены в один $$t_{ij}=t_i \cap t_j$$ путем выполнения операции пересечения. При этом множество проверяемых набором $$t_{ij}$$ неисправностей является объединением множеств неисправностей, проверяемых по отдельности наборами $$t_{i}$$ и $$t_{j}$$.
Таким образом, наборы $$t_{i}$$ и $$t_{j}$$ в тесте могут быть заменены $$t_{ij}$$. Этот метод можно использовать итеративно для сокращения теста. Такой процесс называется статическим сокращением тестов. В общем случае результат статического сокращения тестов зависит от порядка, в котором обрабатываются входные наборы.
Например, для теста $$t_{1}=01u$$, $$t_{2}=0u1$$, $$t_{3}=0u0$$, $$t_{4}=u01$$ в том случае, если мы объединим $$t_{1}$$ и $$t_{2}$$, мы получим множество $$t_{12}=011$$, $$t_{3}=0u0$$, $$t_{4}=u01$$, которое далее невозможно сократить. Если же мы сначала объединим $$t_{1}$$ и $$t_{3}$$ , то далее возможно также объединение $$t_{2}$$ и $$t_{4}$$, что дает более короткий тест: $$t_{13}=010$$, $$t_{24}=001$$.
Оптимальное сжатие этим методом требует больших вычислительных ресурсов, так как фактически сводится к перебору различных вариантов решения. Таким образом, статическое сжатие выполняется на этапе постпроцессорной обработки.
(рис 21.13) Динамическое сжатие теста
В отличие от статического, динамическое сжатие выполняется сразу же после построения текущего входного тестового набора путем подбора двоичных значений, которые присваиваются неопределенным входам. На рис. 21.13 приведен псевдокод укрупненного алгоритма динамического сжатия тестовой последовательности. Отметим, что здесь выполняется проверка перспективности текущего тестового набора путем, например, вычисления процента числа входов с неопределенными значениями.
Если текущий тестовый набор $$t$$ перспективен для сжатия, то выбирается вторичная неисправность и значения входов доопределяются таким образом, чтобы она проверилась на $$t$$. Наиболее важным при этом является метод выбора вторичной неисправности. Эксперименты показали, что динамическое сжатие позволяет получить тесты меньшей длины.
Ключевые термины:
Конъюнктивнаян нормальная форма - нормальная форма, в которой булева формула имеет вид конъюнкции нескольких дизъюнкций литералов.
Выполнимость булевой функции - булева функция $$F(X)$$ выполнима, если существует хотя бы один набор значений ее аргументов, такой, что она истинна ($$F(X)=1$$).
Бинарная диаграмма(альтернативный граф) - ациклический ориентированный граф, который представляет булевы функции.
Краткие итоги
В лекции рассмотрены современные методы построения проверяющих тестов для заданной неисправности комбинационной схемы на основе выполнимости булевых функций и бинарных диаграмм.
В [разделе 21.1 изложено приведение задачи построения теста для данной неисправности к конъюктивной нормальной форме. Показано как задача построения проверяющего теста сводится к задаче выполнимости булевой функции. Изложен метод решения задачи выполнимости применительно к построению теста.]
В [разделе 21.2 описано применение бинарных диаграмм (альтернативных графов) к решению задачи построения проверяющего теста. При этом строится бинарная диаграмма различающей функции и далее построение теста сводится к поиску определенного пути на графе. ]
[Раздел 21.3 посвящен задаче сжатия построенных тестов с помощью статических или динамических методов. ]
Вопросы и упражнения
Как можно построить КНФ для логической схемы? Какие преобразования при этом используются? Как строится КНФ для различающей функции? Как эффективность решения выполнимости булевых функций зависит от числа термов в дизъюнктах? Приведите алгоритм решения задачи выполнимости, применяемый при построении теста. Как можно внести в КНФ нелокальные импликации? Как в КНФ можно дополнительно ввести информацию об активизированных путях в схеме? Как можно добавить в КНФ дизъюнкты, учитывающие неконтролирующие значения? При решении каких задач диагностики ЦС можно использовать бинарные диаграммы?
Опишите подход, использующий бинарную диаграмму различающей функции?
К чему сводится поиск тестового набора на бинарной диаграмме?
Какие модели неисправностей можно определить на бинарных диаграммах?
Что такое 0- (1-) эксперименты на бинарной диаграмме?
Зачем нужно сжатие построенных тестов?
Какие подходы существуют к сжатию теста?
Опишите статический подход к сжатию тестов.
Чем динамический подход отличается от статического?
