Многомерная активизация путей в шестизначном алфавите

Разбить на страницы

Показывать лекцию целиком

18.1 Шестизначный алфавит в генерации тестов

Булевы функции в двузначном алфавите $$В_{2}=\{0,1\}$$ широко используются для моделирования исправных комбинационных схем, но для описания работы схемы с неисправностью удобно использовать алфавиты большей значности [18.1]. В этом случае анализ двух схем (исправной и неисправной) в двоичном алфавите заменяется анализом одной схемы в многозначном алфавите. При поданном некотором тестовом наборе для каждой линии в исправной и неисправной схеме возможны четыре комбинации значений сигналов:

00 - 0 в исправной схеме, и 0 в неисправной (соответствует символу 0 универсального алфавита $$B_{16}$$, рассмотренного в лекции 7);

11 - 1 в исправной схеме и 1 в неисправной (символ 1 алфавита $$B_{16}$$);

10 - 1 в исправной схеме и 0 в неисправной (символ $$D$$ алфавита $$B_{16}$$);

01 - 0 в исправной схеме и 1 в неисправной (символ $$D'$$ алфавита $$B_{16}$$);

Мы не знаем, какие именно из этих четырёх комбинаций могут присутствовать для данной неисправности, поэтому в начале построения теста предполагается, что на каждой линии схемы возможны все 4 комбинации - максимально возможная неопределённость. Суть методов генерации тестов в многозначных алфавитах заключается в том, что, используя свойства структуры схемы и знания местоположения неисправностей далее, исключаются ненужные или невозможные комбинации [18.1]. То есть, в процессе генерации тестов неопределённость постепенно снимается и значения 0, 1 на внешних входах схемы, которые получаются в результате снятия неопределённости, определяют проверяющий тест для данной неисправности. При снятии неопределённости для произвольной линии схемы возможны различные ситуации, описываемые универсальным 16-значным алфавитом $$В_{16}$$. Таким образом, в начале построения теста всем линиям схемы присваивается неопределённое значение $$u$$ алфавита $$В_{16}$$, а далее эта неопределённость постепенно снимается. Например, если мы строим тест для константы неисправности $$x_{i}\equiv 0$$, то, очевидно, что этой линии надо присвоить значение $$D$$ из $$В_{16}$$, а в случае неисправности $$x_{i}\equiv 1 - D'$$. Затем эти значения стараются распространить к внешнему выходу схемы, чтобы обеспечить наблюдение влияния неисправностей на внешнем выходе. При этом снимается неопределённость для линий, попавших в активизированные пути и получивших, например, значение $$D$$ или $$D'$$. Этот процесс является аналогом прямой фазы активизации одномерных путей. Далее надо отработать назад к внешним входам схемы, чтобы обеспечить условие активизации путей. Этот процесс является аналогом обратной фазы метода активизации одномерных путей. При этом также снимается неопределённость. алРезультаты этого процесса для неисправности представлены на рис. 18.1.

Различные методы генерации тестов используют разные подмножества универсального алфавита $$В_{16} $$[18.1]. Наименьшим подмножеством $$В_{16}$$, которое используется в распространенных на практике методах генерации тестов, является алфавит $$T_{6}=\{\varnothing ,0,1,D,D',u\}$$. Здесь символы $$D$$ и $$D'$$ представляют рассогласование сигналов в исправной и неисправной схемах и фактически показывают влияние данной неисправности в схеме. Символы 0,1 представляют одинаковые значения сигналов в исправной и неисправной схемах. Символ $$u$$ соответствует неопределенным значения в исправной и неисправной схемах. Наконец, символ \varnothing используется для описания конфликтов (противоречия сигналов), которые могут быть в процессе построения тестов.

(рис 18.1) Использование многозначных алфавитов

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

Активизация (sensitization) данной неисправности. При этом вносится влияние данной неисправности на соответствующей линии путем присваивания ей значения $$D$$ (для неисправности const0) или $$D'$$ (для неисправности const1).

D-распространение (D-propagation), при котором значения $$D$$ или $$D'$$ распространяются до одного из внешних выходов схемы. Эта процедура обеспечивает наблюдение влияния неисправности на внешних выходах.

Доопределение (justification), при котором определяются значения внешних входов схемы, обеспечивающих значения, получаемые на этапах (1) и (2).

Импликация, которая используется для снятия неопределённости на линиях схемы, которые возможны в результате присваивания некоторым линиям определённых значений.

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

Аналогично при выполнении этапа доопределения (justification) также возможен выбор различных вариантов продвижения к внешним входам. Множество элементов, у которых выходное значение определено (имеют значения 0 или 1), но не подтверждается входными значениями (входы имеют неопределенные значения $$u$$) называется J-границей.

Так как при генерации тестов мы используем не двоичные, а многозначные алфавиты, функционирование логических элементов также должно быть описано в многозначном алфавите. Часто это делается с помощью специальных таблиц такого же типа, как и при моделировании многозначных алфавитов, которые были представлены в разделах 2 и 3. Например, в табл. 18.1 - 18. представлены модели основных вентилей в алфавите $$T_{6}$$. Следует отметить, что различные методы генерации тестов могут использовать не только разные подмножества универсального многозначного алфавита $$В_{16}$$, но и различные формы многозначных моделей, которые мы рассмотрим далее.


И	$$0$$	$$1$$	$$D$$	$$D'$$	$$u$$
$$0$$	$$0$$	$$0$$	$$0$$	$$0$$	$$0$$
$$1$$	$$0$$	$$1$$	$$D$$	$$D'$$	$$u$$
$$D$$	$$0$$	$$D$$	$$D$$	$$0$$	$$u$$
$$D'$$	$$0$$	$$D'$$	$$0$$	$$D'$$	$$u$$
$$U$$	$$0$$	$$u$$	$$u$$	$$u$$	$$u$$


ИЛИ	$$0$$	$$1$$	$$D$$	$$D'$$	$$u$$
$$0$$	$$0$$	$$1$$	$$D$$	$$D'$$	$$u$$
$$1$$	$$1$$	$$1$$	$$1$$	$$1$$	$$1$$
$$D$$	$$D$$	$$1$$	$$D$$	$$1$$	$$u$$
$$D'$$	$$D'$$	$$1$$	$$1$$	$$D'$$	$$u$$
$$U$$	$$u$$	$$1$$	$$u$$	$$u$$	$$u$$


НЕ	$$0$$	$$1$$	$$D$$	$$D'$$	$$u$$
	$$1$$	$$0$$	$$D'$$	$$D$$	$$u$$


$$\oplus$$	$$0$$	$$1$$	$$D$$	$$D'$$	$$u$$
$$0$$	$$0$$	$$1$$	$$D$$	$$D'$$	$$u$$
$$1$$	$$1$$	$$0$$	$$D'$$	$$D$$	$$u$$
$$D$$	$$D$$	$$D'$$	$$0$$	$$1$$	$$u$$
$$D'$$	$$D'$$	$$D$$	$$1$$	$$0$$	$$u$$
$$U$$	$$u$$	$$u$$	$$u$$	$$u$$	$$u$$

Процедура импликации используется для максимально возможного снятия неопределенности на линиях схемы, которое возможно вследствие присваивания некоторым линиям определенных значений (как на этапе D-распространения, так и на этапе доопределения). Например, если в схеме рис. 18.2 установить значение $$x_{4}=0$$, то из этого, очевидно, следует, что сигналы $$x_{41}= x_{42}=0$$. Из равенства $$x_{41}=0$$ следует однозначно $$x_{6}=1$$. Аналогично $$x_{42}=0$$ имплицирует $$x_{5}=1$$. Кроме этого, из равенства $$x_{4}=0$$ однозначно следует равенства $$x_{2}=1$$, $$x_{3}=1$$.

(рис 18.2) Пример схемы для иллюстрации импликации

Различают прямую и обратную импликацию. При прямой импликации снимается неопределенность на линиях элементов - последователей данной линии (для нашего примера $$x_{4} =0\to x_{42}=0, x_{5}=1, x_{6}=1$$). Обратная импликация снимает неопределенность у линий, являющихся предшественниками данной линии (для нашего примера $$х_{4}=0\to x_{2}=1, x_{3}=1$$).

Прямая импликация фактически сводится к логическому моделированию в алфавите $$T_{6}$$ фрагмента схемы, последователей линии с изменившимся сигналом. Это может быть выполнено, например, с помощью табличных многозначных моделей, приведенных в табл. 18.1-18.4.

Типовые ситуации, где может быть выполнена обратная импликация, представлены на рис. 18.3.

(рис 18.3) Обратная импликация

18.2 D - алгоритм

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

Основным рабочим инструментом в D-алгоритме является техника кубов. Модели логических элементов представляются также с помощью кубов. Например, в табл. 18.5 представлены 0-кубы для вентиля И. Легко видеть, что данная таблица в сжатой форме содержит все условия, при которых на выходе вентиля И возможно значение 0. Можно показать, что множество сжатых кубов, используемое в D-алгоритме, определяется соответствующей функцией $$f^{0}$$. Так, например, каждый терм функции $$f^{0}$$ вентиля соответствует строке табл. 18.5. Аналогично функция $$f^{1}$$ соответствует табл. 18.6, которая содержит 1-кубы и определяет условия, при которых на выходе вентиля И возможна 1.

Распространение символов $$D'$$ и $$D$$ через логические элементы осуществляется с помощью $$D'$$- и $$D$$-кубов, которые определяются функциями многозначными функциями $$f^{ D'}, f^{ D}$$ соответственно. Так, табл. 18.7, содержащая $$D$$-кубы вентиля И, получена из функции $$f^{ D}$$ вентиля И. Аналогично, функция $$f^{D'}$$ определяет $$D'$$-кубы табл. 18.8.


$$A$$	$$B$$	$$c$$
$$0$$	$$U$$	$$0$$
$$u$$	$$0$$	$$0$$
$$D$$	$$D'$$	$$0$$
$$D'$$	$$D$$	$$0$$


$$a$$	$$b$$	$$c$$
$$1$$	$$1$$	$$1$$


$$A$$	$$B$$	$$c$$
$$D$$	$$1$$	$$D$$
$$1$$	$$D$$	$$D$$
$$D$$	$$D$$	$$D$$


$$a$$	$$b$$	$$c$$
$$D'$$	$$1$$	$$D'$$
$$1$$	$$D'$$	$$D'$$
$$D'$$	$$D'$$	$$D'$$

Простым кубом неисправности $$h \equiv 0,1$$ на выходе вентиля называется $$D$$($$D'$$)-куб ($$D$$ для неисправности $$h\equiv 0$$, $$D'$$ для неисправности $$h\equiv 1$$), в котором выходу вентиля присваивается $$D$$($$D'$$), а значения входам присваиваются таким образом, чтобы на выходе исправного вентиля было значение, инверсное $$h$$. Например, $$11D$$ является простым $$D$$-кубом для неисправности $$h\equiv 0$$ на входе вентиля И. Очевидно, что простой $$D$$-куб служит средством активизации неисправности на соответствующей линии схемы (он вносит влияние неисправности в месте ее возникновения).

(рис 18.4) Пример схемы для иллюстрации D-алгоритма

Основной моделью логической схемы в $$D$$-алгоритме является система таблиц кубов, в которых столбцы соответствуют линиям схемы, а строки - кубам. Например, табл. 18.9 содержит $$D'$$ кубы для схемы, изображенной на рис. 18.4. Пустые клеточки соответствуют неопределенным значениям $$u$$. Вторая таблица содержит 0(1)-кубы. Для нашего примера она представлена в табл. 18.10.


Куб Линии		$$X_{1}$$	$$x_{2}$$	$$x_{3}$$	$$x_{4}$$	$$x_{5}$$	$$x_{6}$$	$$x_{7}$$	$$x_{8}$$	$$x_{9}$$	$$x_{10}$$	$$x_{11}$$	$$x_{12}$$
1	2	3	4	5	6	7	8	9	10	11	12	13	14
$$G1$$	$$t1$$		$$D$$	$$1$$			$$D$$
	$$t2$$		$$1$$	$$D$$			$$D$$
	$$t3$$		$$D$$	$$D$$			$$D$$
	$$t4$$		$$D'$$	$$1$$			$$D'$$
	$$t5$$		$$1$$	$$D'$$			$$D'$$
	$$t6$$		$$1$$	$$D'$$			$$D'$$
$$G2$$	$$t7$$				$$D$$	$$1$$				$$D$$
	$$t8$$				$$1$$	$$D$$				$$D$$
	$$t9$$				$$D$$	$$D$$				$$D$$
	$$t10$$				$$1$$	$$D'$$				$$D'$$
	$$t11$$				$$D'$$	$$1$$				$$D'$$
	$$t12$$				$$D'$$	$$D'$$				$$D'$$
$$G3$$	$$t13$$	$$D'$$						$$0$$			$$D$$
	$$t14$$	$$0$$						$$D'$$			$$D$$
	$$t15$$	$$D'$$						$$D'$$			$$D$$
	$$t16$$	$$D$$						$$0$$			$$D'$$
	$$t17$$	$$0$$						$$D$$			$$D'$$
	$$t18$$	$$D$$						$$D$$			$$D'$$
$$G4$$	$$t19$$								$$D'$$	$$1$$		$$D$$
	$$t20$$								$$1$$	$$D'$$		$$D$$
	$$t21$$								$$D'$$	$$D'$$		$$D$$
	$$t22$$								$$D$$	$$1$$		$$D'$$
	$$t23$$								$$1$$	$$D$$		$$D'$$
	$$t24$$								$$0$$	$$D$$		$$D'$$
$$G5$$	$$t25$$										$$D$$	$$0$$	$$D$$
	$$t26$$										$$0$$	$$D$$	$$D$$
	$$t27$$										$$D$$	$$D$$	$$D$$
	$$t28$$										$$D'$$	$$0$$	$$D'$$
	$$t29$$										$$0$$	$$D'$$	$$D'$$
	$$t30$$										$$D'$$	$$D'$$	$$D'$$
Разветвление	$$t28$$					$$D$$	$$D$$	$$D$$
Разветвление	$$t29$$					$$D'$$	$$D'$$	$$D'$$


Куб Линии		$$x_{1}$$	$$x_{2}$$	$$x_{3}$$	$$x_{4}$$	$$x_{5}$$	$$x_{6}$$	$$x_{7}$$	$$x_{8}$$	$$x_{9}$$	$$x_{10}$$	$$x_{11}$$	$$x_{12}$$
$$1$$	$$2$$	$$3$$	$$4$$	$$5$$	$$6$$	$$7$$	$$8$$	$$9$$	$$10$$	$$11$$	$$12$$	$$13$$	$$14$$
$$G1$$	$$С1$$		$$0$$	$$u$$			$$0$$
	$$С2$$		$$u$$	$$0$$			$$0$$
	$$С3$$		$$D$$	$$D'$$			$$0$$
	$$С4$$		$$D'$$	$$D$$			$$0$$
	$$С5$$		$$1$$	$$1$$			$$1$$
$$G2$$	$$С6$$				$$0$$	$$u$$				$$0$$
	$$С7$$				$$u$$	$$0$$				$$0$$
	$$С8$$				$$D$$	$$D'$$				$$0$$
	$$C9$$				$$D'$$	$$D$$				$$0$$
	$$C10$$				$$1$$	$$1$$				$$1$$
$$G3$$	$$C11$$	$$1$$						$$u$$			$$0$$
	$$C12$$	$$u$$						$$1$$			$$0$$
	$$C13$$	$$D$$						$$D'$$			$$0$$
	$$C14$$	$$D'$$						$$D$$			$$0$$
	$$C15$$	$$0$$						$$0$$			$$1$$
$$G4$$	$$C16$$								$$1$$	$$1$$		$$0$$
	$$C17$$								$$0$$	$$u$$		$$1$$
	$$C18$$								$$u$$	$$0$$		$$1$$
	$$C19$$								$$D$$	$$D'$$		$$1$$
	$$C20$$								$$D'$$	$$D$$		$$1$$
$$G5$$	$$C21$$										$$0$$	$$0$$	$$0$$
	$$C22$$										$$1$$	$$u$$	$$1$$
	$$C23$$										$$u$$	$$1$$	$$1$$
	$$C24$$										$$D$$	$$D'$$	$$1$$
	$$C25$$										$$D'$$	$$D$$	$$1$$

Кроме этих таблиц используется куб $$K$$ для текущих значений линий схемы и несколько стеков. Сначала всем линиям в кубе $$K$$ присваиваются неопределенные значения $$u$$. Затем в $$K$$ вносится простой куб данной неисправности. Далее выполняется $$D$$-распространение к одному из выходов схемы. Оно выполняется путем выбора последователя неисправного вентиля и пересечения с одним из его $$D$$-кубов с текущим кубом $$K$$. При $$D$$-распространении обычно производится выбор $$D$$ или $$D'$$-куба данного элемента, оставшиеся варианты хранятся в стеке. Операция пересечения определена в табл. 18.11. Если при пересечении кубов, возникает хотя бы один символ $$\varnothing$$, то это показывает противоречие, возникающее на данной линии вследствие различных требований (например, из простого $$D$$-куба следует, что данная линия должна иметь значение 0, а из условий $$D$$ распространения здесь должна быть 1.


$$N$$	$$0$$	$$1$$	$$D$$	$$D'$$	$$u$$
$$0$$	$$0$$	$$\varnothing $$	$$\varnothing $$	$$\varnothing $$	$$0$$
$$1$$	$$\varnothing $$	$$1$$	$$1$$	$$\varnothing $$	$$1$$
$$D$$	$$\varnothing $$	$$\varnothing $$	$$D$$	$$\varnothing $$	$$D$$
$$D'$$	$$\varnothing $$	$$\varnothing $$	$$\varnothing $$	$$D'$$	$$D'$$
$$U$$	$$0$$	$$1$$	$$D$$	$$D'$$	$$u$$

$$D$$-алгоритм можно сформулировать следующим образом в виде псевдокода.

D-алгоритм( неисправность h_{i})
{
 Ранжирование элементов схемы от входов к выходам;
 Выбор простого D-куба для неисправности h_{i};
 Занесение элементов-последователей h_{i}  в D-границу;
 D-распространение();
 Доопределение();
 Return(); 
}

 D-распространение()
//активизирует пути с D,D'-значениями от неисправности до внешнего выхода                
{
 while(есть необработанные элементы в D-границе)
  {
  Выбор следующего необработанного элемента из D-границы;
 while(есть необработанные последователи  элемента)
   {
    Выбор следующего элемента-последователя;
    Выбор D-куба для элемента-последователя;
    D-пересечение выбранного D-куба с текущим тест-кубом К;
    if(пересечение пусто или неопределено)continue; 
    //переход на конец цикла
    if(все D-кубы элемента использовались и не дали результата) break;
    if(пересечение D-кубов успешно)
         {
           Занесение элементов-последователей D-значений в D-границу;
           Сохранение состояния алгоритма в стеки;
           break;
}         
        else if (пересечение D-куба с тестовым кубом пусто) возврат();
       else if ( противоречие при операции пересечения кубов) break;
}     
    if(ни один из вариантов не дал D-распространения) 
    Возврат();
}  
   return;
}

 Доопределение()
//дает значения внешних входов, обеспечивающие условия D-распространения 
 {
  J=координаты тестового куба К с определенными значениями 0,1 ;
 if(J содержит только внешние входы) 
тест построен, останов; 
  for(каждого неподтвержденного сигнала в G)
      {
       выбор 0,1 сигнала z из J с наибольшим рангом;
      if(входы элемента с выходом z все равны D или D') 
      break;
      while(есть необработанные 0,1-кубы вентиля z) 
       {
        Выбор следующего необработанного 1- или 0- куба вентиля z;
        if(нет необработаных 1- или 0- кубов)
          {
           if(нет выбора в стеке импликации) stop;
           неисправность избыточна;
           else if(есть альтернативный выбор) 
           then  извлечение из стека альтернативного значения;
        else
          {
            Возврат();
            D-распространение();
}           
}          
 if(0,1-куб пересекается с z) удаление z из J и занесение в J-границу           значений входов z;
 break;
if(пересечение пусто) отметка текущего 0,1-куба как отработанного;
}        
}      
       return;
} 

Возврат()
 {
  if( внешний выход содержится в D-границе) 
   Доопределение();
  else if(извлечение из стека импликации альтернативного значения);
   if(нет вариантов в стеке импликации)  stop; 
   неисправность избыточна;
    else return;
}

D-алгоритм

Рассмотрим применение $$D$$-алгоритма к построению теста для неисправности $$x_{6}\equiv 0$$ схемы, изображенной на рис. 18.4.

При инициализации мы получаем куб $$K$$, представленный в табл. 18.12. Элементы $$G3$$ и $$G4$$ одинаково близко расположены к выходу, $$D$$-граница содержит элементы $$\{G4, G3\}$$. Выбираем для $$D$$-распространения элемент $$G3$$. Пересекая $$D$$-куб узла разветвления элемента $$G3$$ с кубом $$K$$, как это показано в табл. 18.12 б), в), получаем куб $$K_{1}$$. Пополняем $$D$$-границу $$\{G5, G3\}$$. Далее выбираем $$D'$$-куб элемента $$G5$$ и, пересекая его с $$K_{2}$$, получаем $$K_{3}$$, как показано в табл. 18.12 г). Так как мы достигли внешнего выхода, то этап D-распространения заканчивается. Далее нужно выполнить процедуру доопределения. Стек доопределения в этот момент должен содержать элементы $$\{G2, G3\}$$. Выбираем 1-куб элемента $$G2$$ и, выполняя пересечение его с кубом $$K_{3}$$, как показано в табл. 18.12 д), получаем $$K_{4}$$. Аналогично доопределяем входы $$G3$$ ( табл. 18.12 е). В результате получаем тест $$х_{2}=0, x_{3}=1, x_{4}=1, x_{5}=1$$.


Куб	1	2	3	4	5	6	7	8	9	10	11	12
$$K_{0}$$	$$U$$	$$1$$	$$1$$	$$u$$	$$u$$	$$D$$	$$u$$	$$U$$	$$u$$	$$u$$	$$u$$	$$U$$
a)
$$K_{0}$$	$$U$$	$$1$$	$$1$$	$$u$$	$$u$$	$$D$$	$$u$$	$$U$$	$$u$$	$$u$$	$$u$$	$$U$$
$$t_{31}$$	$$U$$	$$U$$	$$u$$	$$u$$	$$u$$	$$D$$	$$D$$	$$D$$	$$u$$	$$u$$	$$u$$	$$U$$
$$K_{1}$$	$$U$$	$$1$$	$$1$$	$$u$$	$$u$$	$$D$$	$$D$$	$$D$$	$$u$$	$$u$$	$$u$$	$$U$$
б)
$$K_{1}$$	$$U$$	$$1$$	$$1$$	$$u$$	$$u$$	$$D$$	$$D$$	$$D$$	$$u$$	$$u$$	$$u$$	$$U$$
$$t_{22}$$	$$U$$	$$U$$	$$u$$	$$u$$	$$u$$	$$u$$	$$u$$	$$D$$	$$1$$	$$u$$	$$D'$$	$$U$$
$$K_{2}$$	$$U$$	$$1$$	$$1$$	$$u$$	$$u$$	$$D$$	$$D$$	$$D$$	$$1$$	$$u$$	$$D'$$	$$U$$
в)
$$K_{2}$$	$$U$$	$$1$$	$$1$$	$$u$$	$$u$$	$$D$$	$$D$$	$$D$$	$$1$$	$$u$$	$$D'$$	$$U$$
$$t_{29}$$	$$U$$	$$U$$	$$u$$	$$u$$	$$u$$	$$u$$	$$u$$	$$U$$	$$u$$	$$0$$	$$D'$$	$$D'$$
$$K_{3}$$	$$U$$	$$1$$	$$1$$	$$u$$	$$u$$	$$D$$	$$D$$	$$D$$	$$1$$	$$0$$	$$D'$$	$$D'$$
г)
$$K_{3}$$	$$U$$	$$1$$	$$1$$	$$u$$	$$u$$	$$D$$	$$D$$	$$D$$	$$1$$	$$0$$	$$D'$$	$$D'$$
$$C_{10}$$	$$U$$	$$U$$	$$u$$	$$1$$	$$1$$	$$u$$	$$u$$	$$U$$	$$1$$	$$u$$	$$u$$	$$U$$
$$K_{4}$$	$$U$$	$$1$$	$$1$$	$$1$$	$$1$$	$$D$$	$$D$$	$$D$$	$$1$$	$$0$$	$$D'$$	$$D'$$
д)
$$K_{4}$$	$$U$$	$$1$$	$$1$$	$$1$$	$$1$$	$$D$$	$$D$$	$$D$$	$$1$$	$$0$$	$$D'$$	$$D'$$
$$C_{11}$$	$$1$$	$$U$$	$$u$$	$$u$$	$$u$$	$$u$$	$$u$$	$$U$$	$$u$$	$$0$$	$$u$$	$$U$$
$$K_{5}$$	$$1$$	$$1$$	$$1$$	$$1$$	$$1$$	$$D$$	$$D$$	$$D$$	$$1$$	$$0$$	$$D'$$	$$D'$$

Как было показано выше, в $$D$$-алгоритме используется следующая стратегия при построении теста. Сначала значения $$D, D'$$ распространяются до внешнего выхода, а затем с помощью процедуры доопределения находится тестовый набор. Если во время выполнения процедуры доопределения возникает противоречие, то это приводит к поиску другого пути $$D$$-распространения. Если противоречивые ситуации возникают часто, то существенно увеличивается время генерации теста. Например, для схем, содержащих много элементов "исключающее ИЛИ" (схем контроля четности и т.п.), процедура $$D$$-распространения выполняется достаточно легко, однако при выполнении процедуры доопределения часто возникают противоречия и для таких схем $$D$$-алгоритм требует значительных затрат времени. Для этого класса схем был разработан метод РОDЕМ, который хорошо зарекомендовал себя и для других типов схем.

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

Многозначный алфавит - определяет множество ситуаций, возможных при построениитеста в исправной и неисправной схеме.

D-распространение - распространение в схеме символовс, $$D'$$, характеризующих различие значений сигналов в исправной и неисправной схеме.

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

Импликация - процедура снятия неопределённости на линиях схемы, которые возможны в результате присваивания некоторым линиям определённых значений.

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

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

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

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

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

Что лежит в основе 6-значного алфавита?

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

В чем суть использования многозначных алфавитов в построении тестов?

Приведите основные этапы построения теста с использованием многозначных алфавитов.

Как выполняется активизация неисправности?

Как выполняется этап $$D$$-распространения?

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

Зачем нужен этап импликации?

Чем прямая импликация отличается от обратной?

Что является рабочим инструментов в $$D$$-алгоритме?

Приведите 1-куб для вентиля ИЛИ.

Приведите 0-куб для вентиля НЕ-И.

Приведите $$D$$-куб для вентиля НЕ-ИЛИ.

Приведите $$D'$$-куб для вентиля НЕ-И.

Что такое к-куб?

Как выполняется пересечение кубов.

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

Постройте с помощью $$D$$-алгоритма проверяющий тест для неисправности $$x_{7}=0$$, приведенной на схеме рис. 18.6.

(рис 18.6) Схема для упражнения 13

Страницы:

18.1 Шестизначный алфавит в генерации тестов

11 - 1 в исправной схеме и 1 в неисправной (символ 1 алфавита $$B_{16}$$);

10 - 1 в исправной схеме и 0 в неисправной (символ $$D$$ алфавита $$B_{16}$$);

01 - 0 в исправной схеме и 1 в неисправной (символ $$D'$$ алфавита $$B_{16}$$);

(рис 18.1) Использование многозначных алфавитов


И	$$0$$	$$1$$	$$D$$	$$D'$$	$$u$$
$$0$$	$$0$$	$$0$$	$$0$$	$$0$$	$$0$$
$$1$$	$$0$$	$$1$$	$$D$$	$$D'$$	$$u$$
$$D$$	$$0$$	$$D$$	$$D$$	$$0$$	$$u$$
$$D'$$	$$0$$	$$D'$$	$$0$$	$$D'$$	$$u$$
$$U$$	$$0$$	$$u$$	$$u$$	$$u$$	$$u$$


ИЛИ	$$0$$	$$1$$	$$D$$	$$D'$$	$$u$$
$$0$$	$$0$$	$$1$$	$$D$$	$$D'$$	$$u$$
$$1$$	$$1$$	$$1$$	$$1$$	$$1$$	$$1$$
$$D$$	$$D$$	$$1$$	$$D$$	$$1$$	$$u$$
$$D'$$	$$D'$$	$$1$$	$$1$$	$$D'$$	$$u$$
$$U$$	$$u$$	$$1$$	$$u$$	$$u$$	$$u$$


НЕ	$$0$$	$$1$$	$$D$$	$$D'$$	$$u$$
	$$1$$	$$0$$	$$D'$$	$$D$$	$$u$$


$$\oplus$$	$$0$$	$$1$$	$$D$$	$$D'$$	$$u$$
$$0$$	$$0$$	$$1$$	$$D$$	$$D'$$	$$u$$
$$1$$	$$1$$	$$0$$	$$D'$$	$$D$$	$$u$$
$$D$$	$$D$$	$$D'$$	$$0$$	$$1$$	$$u$$
$$D'$$	$$D'$$	$$D$$	$$1$$	$$0$$	$$u$$
$$U$$	$$u$$	$$u$$	$$u$$	$$u$$	$$u$$

(рис 18.2) Пример схемы для иллюстрации импликации

Типовые ситуации, где может быть выполнена обратная импликация, представлены на рис. 18.3.

(рис 18.3) Обратная импликация

18.2 D - алгоритм


$$A$$	$$B$$	$$c$$
$$0$$	$$U$$	$$0$$
$$u$$	$$0$$	$$0$$
$$D$$	$$D'$$	$$0$$
$$D'$$	$$D$$	$$0$$


$$a$$	$$b$$	$$c$$
$$1$$	$$1$$	$$1$$


$$A$$	$$B$$	$$c$$
$$D$$	$$1$$	$$D$$
$$1$$	$$D$$	$$D$$
$$D$$	$$D$$	$$D$$


$$a$$	$$b$$	$$c$$
$$D'$$	$$1$$	$$D'$$
$$1$$	$$D'$$	$$D'$$
$$D'$$	$$D'$$	$$D'$$

(рис 18.4) Пример схемы для иллюстрации D-алгоритма


Куб Линии		$$X_{1}$$	$$x_{2}$$	$$x_{3}$$	$$x_{4}$$	$$x_{5}$$	$$x_{6}$$	$$x_{7}$$	$$x_{8}$$	$$x_{9}$$	$$x_{10}$$	$$x_{11}$$	$$x_{12}$$
1	2	3	4	5	6	7	8	9	10	11	12	13	14
$$G1$$	$$t1$$		$$D$$	$$1$$			$$D$$
	$$t2$$		$$1$$	$$D$$			$$D$$
	$$t3$$		$$D$$	$$D$$			$$D$$
	$$t4$$		$$D'$$	$$1$$			$$D'$$
	$$t5$$		$$1$$	$$D'$$			$$D'$$
	$$t6$$		$$1$$	$$D'$$			$$D'$$
$$G2$$	$$t7$$				$$D$$	$$1$$				$$D$$
	$$t8$$				$$1$$	$$D$$				$$D$$
	$$t9$$				$$D$$	$$D$$				$$D$$
	$$t10$$				$$1$$	$$D'$$				$$D'$$
	$$t11$$				$$D'$$	$$1$$				$$D'$$
	$$t12$$				$$D'$$	$$D'$$				$$D'$$
$$G3$$	$$t13$$	$$D'$$						$$0$$			$$D$$
	$$t14$$	$$0$$						$$D'$$			$$D$$
	$$t15$$	$$D'$$						$$D'$$			$$D$$
	$$t16$$	$$D$$						$$0$$			$$D'$$
	$$t17$$	$$0$$						$$D$$			$$D'$$
	$$t18$$	$$D$$						$$D$$			$$D'$$
$$G4$$	$$t19$$								$$D'$$	$$1$$		$$D$$
	$$t20$$								$$1$$	$$D'$$		$$D$$
	$$t21$$								$$D'$$	$$D'$$		$$D$$
	$$t22$$								$$D$$	$$1$$		$$D'$$
	$$t23$$								$$1$$	$$D$$		$$D'$$
	$$t24$$								$$0$$	$$D$$		$$D'$$
$$G5$$	$$t25$$										$$D$$	$$0$$	$$D$$
	$$t26$$										$$0$$	$$D$$	$$D$$
	$$t27$$										$$D$$	$$D$$	$$D$$
	$$t28$$										$$D'$$	$$0$$	$$D'$$
	$$t29$$										$$0$$	$$D'$$	$$D'$$
	$$t30$$										$$D'$$	$$D'$$	$$D'$$
Разветвление	$$t28$$					$$D$$	$$D$$	$$D$$
Разветвление	$$t29$$					$$D'$$	$$D'$$	$$D'$$


Куб Линии		$$x_{1}$$	$$x_{2}$$	$$x_{3}$$	$$x_{4}$$	$$x_{5}$$	$$x_{6}$$	$$x_{7}$$	$$x_{8}$$	$$x_{9}$$	$$x_{10}$$	$$x_{11}$$	$$x_{12}$$
$$1$$	$$2$$	$$3$$	$$4$$	$$5$$	$$6$$	$$7$$	$$8$$	$$9$$	$$10$$	$$11$$	$$12$$	$$13$$	$$14$$
$$G1$$	$$С1$$		$$0$$	$$u$$			$$0$$
	$$С2$$		$$u$$	$$0$$			$$0$$
	$$С3$$		$$D$$	$$D'$$			$$0$$
	$$С4$$		$$D'$$	$$D$$			$$0$$
	$$С5$$		$$1$$	$$1$$			$$1$$
$$G2$$	$$С6$$				$$0$$	$$u$$				$$0$$
	$$С7$$				$$u$$	$$0$$				$$0$$
	$$С8$$				$$D$$	$$D'$$				$$0$$
	$$C9$$				$$D'$$	$$D$$				$$0$$
	$$C10$$				$$1$$	$$1$$				$$1$$
$$G3$$	$$C11$$	$$1$$						$$u$$			$$0$$
	$$C12$$	$$u$$						$$1$$			$$0$$
	$$C13$$	$$D$$						$$D'$$			$$0$$
	$$C14$$	$$D'$$						$$D$$			$$0$$
	$$C15$$	$$0$$						$$0$$			$$1$$
$$G4$$	$$C16$$								$$1$$	$$1$$		$$0$$
	$$C17$$								$$0$$	$$u$$		$$1$$
	$$C18$$								$$u$$	$$0$$		$$1$$
	$$C19$$								$$D$$	$$D'$$		$$1$$
	$$C20$$								$$D'$$	$$D$$		$$1$$
$$G5$$	$$C21$$										$$0$$	$$0$$	$$0$$
	$$C22$$										$$1$$	$$u$$	$$1$$
	$$C23$$										$$u$$	$$1$$	$$1$$
	$$C24$$										$$D$$	$$D'$$	$$1$$
	$$C25$$										$$D'$$	$$D$$	$$1$$


$$N$$	$$0$$	$$1$$	$$D$$	$$D'$$	$$u$$
$$0$$	$$0$$	$$\varnothing $$	$$\varnothing $$	$$\varnothing $$	$$0$$
$$1$$	$$\varnothing $$	$$1$$	$$1$$	$$\varnothing $$	$$1$$
$$D$$	$$\varnothing $$	$$\varnothing $$	$$D$$	$$\varnothing $$	$$D$$
$$D'$$	$$\varnothing $$	$$\varnothing $$	$$\varnothing $$	$$D'$$	$$D'$$
$$U$$	$$0$$	$$1$$	$$D$$	$$D'$$	$$u$$

$$D$$-алгоритм можно сформулировать следующим образом в виде псевдокода.

D-алгоритм( неисправность h_{i})
{
 Ранжирование элементов схемы от входов к выходам;
 Выбор простого D-куба для неисправности h_{i};
 Занесение элементов-последователей h_{i}  в D-границу;
 D-распространение();
 Доопределение();
 Return(); 
}

 D-распространение()
//активизирует пути с D,D'-значениями от неисправности до внешнего выхода                
{
 while(есть необработанные элементы в D-границе)
  {
  Выбор следующего необработанного элемента из D-границы;
 while(есть необработанные последователи  элемента)
   {
    Выбор следующего элемента-последователя;
    Выбор D-куба для элемента-последователя;
    D-пересечение выбранного D-куба с текущим тест-кубом К;
    if(пересечение пусто или неопределено)continue; 
    //переход на конец цикла
    if(все D-кубы элемента использовались и не дали результата) break;
    if(пересечение D-кубов успешно)
         {
           Занесение элементов-последователей D-значений в D-границу;
           Сохранение состояния алгоритма в стеки;
           break;
}         
        else if (пересечение D-куба с тестовым кубом пусто) возврат();
       else if ( противоречие при операции пересечения кубов) break;
}     
    if(ни один из вариантов не дал D-распространения) 
    Возврат();
}  
   return;
}

 Доопределение()
//дает значения внешних входов, обеспечивающие условия D-распространения 
 {
  J=координаты тестового куба К с определенными значениями 0,1 ;
 if(J содержит только внешние входы) 
тест построен, останов; 
  for(каждого неподтвержденного сигнала в G)
      {
       выбор 0,1 сигнала z из J с наибольшим рангом;
      if(входы элемента с выходом z все равны D или D') 
      break;
      while(есть необработанные 0,1-кубы вентиля z) 
       {
        Выбор следующего необработанного 1- или 0- куба вентиля z;
        if(нет необработаных 1- или 0- кубов)
          {
           if(нет выбора в стеке импликации) stop;
           неисправность избыточна;
           else if(есть альтернативный выбор) 
           then  извлечение из стека альтернативного значения;
        else
          {
            Возврат();
            D-распространение();
}           
}          
 if(0,1-куб пересекается с z) удаление z из J и занесение в J-границу           значений входов z;
 break;
if(пересечение пусто) отметка текущего 0,1-куба как отработанного;
}        
}      
       return;
} 

Возврат()
 {
  if( внешний выход содержится в D-границе) 
   Доопределение();
  else if(извлечение из стека импликации альтернативного значения);
   if(нет вариантов в стеке импликации)  stop; 
   неисправность избыточна;
    else return;
}

D-алгоритм


Куб	1	2	3	4	5	6	7	8	9	10	11	12
$$K_{0}$$	$$U$$	$$1$$	$$1$$	$$u$$	$$u$$	$$D$$	$$u$$	$$U$$	$$u$$	$$u$$	$$u$$	$$U$$
a)
$$K_{0}$$	$$U$$	$$1$$	$$1$$	$$u$$	$$u$$	$$D$$	$$u$$	$$U$$	$$u$$	$$u$$	$$u$$	$$U$$
$$t_{31}$$	$$U$$	$$U$$	$$u$$	$$u$$	$$u$$	$$D$$	$$D$$	$$D$$	$$u$$	$$u$$	$$u$$	$$U$$
$$K_{1}$$	$$U$$	$$1$$	$$1$$	$$u$$	$$u$$	$$D$$	$$D$$	$$D$$	$$u$$	$$u$$	$$u$$	$$U$$
б)
$$K_{1}$$	$$U$$	$$1$$	$$1$$	$$u$$	$$u$$	$$D$$	$$D$$	$$D$$	$$u$$	$$u$$	$$u$$	$$U$$
$$t_{22}$$	$$U$$	$$U$$	$$u$$	$$u$$	$$u$$	$$u$$	$$u$$	$$D$$	$$1$$	$$u$$	$$D'$$	$$U$$
$$K_{2}$$	$$U$$	$$1$$	$$1$$	$$u$$	$$u$$	$$D$$	$$D$$	$$D$$	$$1$$	$$u$$	$$D'$$	$$U$$
в)
$$K_{2}$$	$$U$$	$$1$$	$$1$$	$$u$$	$$u$$	$$D$$	$$D$$	$$D$$	$$1$$	$$u$$	$$D'$$	$$U$$
$$t_{29}$$	$$U$$	$$U$$	$$u$$	$$u$$	$$u$$	$$u$$	$$u$$	$$U$$	$$u$$	$$0$$	$$D'$$	$$D'$$
$$K_{3}$$	$$U$$	$$1$$	$$1$$	$$u$$	$$u$$	$$D$$	$$D$$	$$D$$	$$1$$	$$0$$	$$D'$$	$$D'$$
г)
$$K_{3}$$	$$U$$	$$1$$	$$1$$	$$u$$	$$u$$	$$D$$	$$D$$	$$D$$	$$1$$	$$0$$	$$D'$$	$$D'$$
$$C_{10}$$	$$U$$	$$U$$	$$u$$	$$1$$	$$1$$	$$u$$	$$u$$	$$U$$	$$1$$	$$u$$	$$u$$	$$U$$
$$K_{4}$$	$$U$$	$$1$$	$$1$$	$$1$$	$$1$$	$$D$$	$$D$$	$$D$$	$$1$$	$$0$$	$$D'$$	$$D'$$
д)
$$K_{4}$$	$$U$$	$$1$$	$$1$$	$$1$$	$$1$$	$$D$$	$$D$$	$$D$$	$$1$$	$$0$$	$$D'$$	$$D'$$
$$C_{11}$$	$$1$$	$$U$$	$$u$$	$$u$$	$$u$$	$$u$$	$$u$$	$$U$$	$$u$$	$$0$$	$$u$$	$$U$$
$$K_{5}$$	$$1$$	$$1$$	$$1$$	$$1$$	$$1$$	$$D$$	$$D$$	$$D$$	$$1$$	$$0$$	$$D'$$	$$D'$$

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

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

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

Что лежит в основе 6-значного алфавита?

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

В чем суть использования многозначных алфавитов в построении тестов?

Приведите основные этапы построения теста с использованием многозначных алфавитов.

Как выполняется активизация неисправности?

Как выполняется этап $$D$$-распространения?

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

Зачем нужен этап импликации?

Чем прямая импликация отличается от обратной?

Что является рабочим инструментов в $$D$$-алгоритме?

Приведите 1-куб для вентиля ИЛИ.

Приведите 0-куб для вентиля НЕ-И.

Приведите $$D$$-куб для вентиля НЕ-ИЛИ.

Приведите $$D'$$-куб для вентиля НЕ-И.

Что такое к-куб?

Как выполняется пересечение кубов.

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

Постройте с помощью $$D$$-алгоритма проверяющий тест для неисправности $$x_{7}=0$$, приведенной на схеме рис. 18.6.

(рис 18.6) Схема для упражнения 13

Занятие пройдено

Предыдущее занятие Занятие пройдено Следующее занятие

Вернуться к учебному плану

Многомерная активизация путей в шестизначном алфавите

18.1 Шестизначный алфавит в генерации тестов

18.2 D - алгоритм

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

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

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

18.1 Шестизначный алфавит в генерации тестов

18.2 D - алгоритм

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

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

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

Купить дополнительную попытку

Вы действительно хотите купить ещё одну попытку для прохождения тестирования?

Успешно!

Напишите нам, если у вас есть вопросы

Уважаемые пользователи ИНТУИТ!

Уважаемые пользователи ИНТУИТ!

Добро пожаловать на обновлённый сайт НОУ «ИНТУИТ»!