Методы генерации тестов PODEM, FAN и SOCRATES

Рассмотрим работу метода FAN на примере схемы рис. 19.8. Здесь входы $$A$$,$$B$$ являются внешними, в то время как $$C$$, $$D$$, $$E$$ и $$F$$ соединены с выходами подсхем и имеют худшие показатели управляемости. Результаты работы FAN-алгоритма представлены в табл. 19.3[19.3]. Алгоритм стартует с начальными целями $$R$$, $$T$$ и $$U$$. Отметим, что в узле разветвления S суммирование значений схем $$T$$ и $$U$$ дает $$(S,2,0)$$. Аналогично триплеты $$N$$ и $$P$$ дают триплет $$(M,0,3)$$. Это требует установки значения 0 на одном из входов $$M$$. Для удобства предположим, что $$K$$ имеет лучший показатель управляемости. Поскольку вентиль $$M$$ инвертирующего типа, то значения $$n_{0}$$ и $$n_{1}$$ триплета меняются местами. Таким образом, выполняется обратное распространение через каждый логический элемент, в результате чего мы достигаем узла разветвления $$G$$. Здесь имеет место конфликтная ситуация, поскольку оба значения $$n_{0}$$ и $$n_{1}$$ не равны нулю. Поскольку ветвь $$H$$ имеет больший вес, то при разрешении конфликта мы в качестве первого варианта принимаем значение $$G=1$$. Поскольку $$G$$ является головным элементом подсхемы, то присваивание значений входам $$A$$ и $$B$$ откладывается. Присвоенное значение $$G=1$$ вызывает конфликт на линии $$L$$, где значение $$L=1$$ обусловлено целью $$(Q,0,2)$$. Но эта цель может быть достигнута путем присваивания $$F==1$$, что позволяет разрешить конфликт на $$G$$. Если бы конфликт не удалось разрешить вследствие невозможности присваивания $$F==1$$, мы были бы вынуждены рассмотреть альтернативный вариант для узла разветвления $$G=0$$. В этом случае конфликт можно разрешить путем присваивания $$D=0$$. При этом ответствующие триплеты должны быть вычислены заново. После разрешения конфликта процедура продвижения назад MBack выбирает узел разветвления, который определяет новые текущие цели.

В заключение рассмотрим укрупненный алгоритм метода FAN [19.3] в виде псевдокода, который представлен на рис. 19.9 в конце настоящего раздела. Здесь, прежде всего, выполняется активизация неисправности путем присваивания соответствующего значения $$D$$ или $$D'$$ на неисправной линии. Далее устанавливается значение признака $$b_flag$$, который позволяет процедуре продвижения назад MBack различать случаи, когда она стартует из множества начальных целей ($$b_flag=A$$), или множества целей, соответствующим узлам разветвления ($$b_flag=B$$). Второй вариант встречается, когда процедура продолжает распространение назад от узла разветвления. Далее выполняется D-распространение от неисправной линии до одного из внешних выходов схемы. При распространении $$D$$-значения через логический элемент его соседним входам присваиваются не блокирующие значения ( 1(0) для И (ИЛИ) ), которые заносятся в множество начальных целей. Если $$D$$-граница содержит два или более элемента, то FAN исследует эти элементы на приемлемость - допускают ли они $$D$$-распространение (выполняется проверка на наличие блокирующих значений соседних входов элементов). Далее FAN производит упорядочение возможных путей $$D$$-распространения в соответствии с показателями наблюдаемости. Отметим, что подобно $$D$$- алгоритму данный метод в случае необходимости выполняет одномерную и многомерную активизацию ($$D$$-распространение).

Входной параметр процедуры обратного распространения MBack имеет два значения : $$A$$ и $$B$$. Значение A соответствует случаю, когда множество текущих целей $$\{СО\}$$ не пусто. В этом случае производится выбор цели. В процессе обратного распространения в случае достижения головной линии (head) она добавляется во множество головных целей $$\{HO\}$$. При обратном проходе через логический элемент прежде всего необходимо определить какие значения - контролирующие или неконтролирующие необходимо присвоить его входам. Как сказано выше, правила, приведенные в табл. 19.2 позволяют выбрать вход и логическое значение. Схема, которая питает этот вход, добавляется во множество текущих целей {СО}. При достижении узла разветвления значения $$n_{0}$$ и $$n_{1} $$ изменяются.

Значение $$B$$ входного параметра процедуры MBack используется, если множество текущих целей пусто. В этом случае узел разветвления FPO выбирается из множества целей $$\{FPO\}$$. Однако, если выбранная цель содержит конфликт, то он должен быть разрешен. Это производится путем возврата к выбору других значений для данного узла разветвления.

При инициализации признак $$b_flag$$ устанавливается в 1, если по окончании фазы импликации остались неподтвержденные значения в схеме. В этой точке все множества целей инициализируются (присваивается пустое множество) и производится сброс флага $$b_flag$$. Если есть неподтвержденные линии, то они образуют множество начальных целей $$\{IO\}$$. Если $$D$$-значение не достигает внешнего выхода, элемент из $$D$$-границы добавляется в $$\{IO\}$$. Как уже отмечалось алгоритм обратного распространения реализуется в MBack. Если $$b_flag$$ не установлен в 1, то нет неподтвержденных линий, которые ожидают присвоения значений. В этом случае исследуется множество целей, соответствующих узлам разветвлений $$\{FPO\}$$. Если оно не пусто, то обратное распространение выполняется от выбранного узла разветвления. По завершению кратного распространения назад в случае отсутствия конфликтов на узлах разветвления обрабатывается множество головных целей {HO}.Если есть конфликт на узле разветвления (оба значения $$n_{0}$$ и $$n_{1}$$ не равны нулю), то, как неоднократно отмечалось, присваивается значение с большим весом.

FAN()  / / аргументы -номер элемента и линии с константной неисправностью
{
инициализация неисправности;  // присваивание D или D' неисправной линии
b_flag=A; //режим обратного распространения от неподтвержденных линий
for(::)  //основной цикл
  {
     импликация;    //прямая и обратная
      if(необходимо обратное распространение)
         b_flag=B;  // обработка разветвлений
      if(значение D достигло внешнего выхода) {
         if(число неподтвержденных линий==0)     {
              подтверждение свободных линий;
               return(тест);
}         
         else{
              конечная_цель();
              присваивание значений линиям конечной цели;
}         
}     
     else {
          if(число элементов в D-границе >1) {  
//выбор вентиля, ближайшего к выходу
              конечная_цель();
                присваивание значений линиям конечной цели;
}           
           else if(число вентилей в D-границе ==1)
           одномерная активизация;
       else {                  //число вентилей ==0
           if (есть нерассмотренные варианты)  {
                установка нерассмотренного варианта;
                b_flag=B;
}              
               else
                     return (нет теста);
}                
}        
}    
} 

конечная_цель()
 {
    mb = 0:
    if(b_flag==A)
        mb=Mback(A);
     else if (множество целей разветвлений не пусто)
        mb=Mback(A);
      if (mb==D) {  
           конечная_цель=FPO;  //узел разветвления
           return;
}
for(;;)
     {
        if (множество головных целей пусто)
         mb=Mback(A);
         выбор головной цели;
         if(головная линия не определена)
             break;
}       
      головная цель= конечная цель;               
}   

Mback(flag)
 {
    if(flag==A)  {
       b_flag=0;
       if (число неподтвержденных линий>0)
           {Начальная цель} =неподтвержденные линии;
       if(D-значение не достигло внешнего выхода)
           добавить элемент в D-границе в начальные цели;
           {текущая_цель}={начальная_цель};
       if({текущая_цель} не пусто)  {
            выбор текущей цели;
             следущая_цель();
}     
      else {
            if (FPO ==пусто)
                return(C);
            else
                 flag=B; 
}        
}     
    if (flag==B) {
        выбор узла разветвления, ближайшего к внешнему выходу;
         if (p  достижимо от неисправной линии) или ( (n_{0}==0) или (n_{1}==0)  )
             следующая_цель();
         else
              return(D):
}          
}    

следующая_цель()
   {
      if (текущая_цель==головная линия)
          добавить текущую_цель в головные цели;
      else if (текущая_цель питается узлом разветвления)
             добавить n_{0} и n_{1} к  FPO    //согласно правилу 10 табл. 19.2
      else                           // определить следующую цель
       распространение назад согласно правилам табл. 19.2
}      

19.3 Метод SOCRATES

Метод SOCRATES (structure-oriented cost-reducing automatic test pattern generation) [19.4] основан на алгоритме FAN с улучшенными процедурами импликации, уникальной активизации путей и кратной процедуры обратного распространения. Кроме этого, в этом алгоритме сокращается число возвратов за счет раннего обнаружения конфликтов и используется несколько эвристик на разных этапах алгоритма, которые также повышают эффективность метода. Кроме этого, в данном методе могут обрабатываться (выступают в роли примитивов - базовых элементов) сложные логические элементы такие как мультиплексоры, сумматоры, кодеры и декодеры, исключающее ИЛИ с произвольным числом входов.

Рассмотрим сначала процедуру импликации на примере схемы рис. 19.9 [19.3].

Здесь входной сигнал $$A=1$$ (рис. 19.9а)) имплицирует 1 на выходах вентилей ИЛИ и И. С другой стороны, на рис. 19.9b) значение $$D=0$$ имплицирует значение $$A=0$$, что следует из тождества контрапозиции импликации $$(A\Rightarrow D)\Leftrightarrow (\thicksim D\Rightarrow \thicksim A)$$, где $$\thicksim$$ обозначает дополнение. Из этого следует, что если в процессе обратного распространения выходу вентиля И будет присвоено значение $$D=0$$, то отсюда вытекает значение входа $$A=0$$. Такая импликация, в свою очередь, может привести к раннему обнаружению конфликтов и сокращению числа возвратов при поиске решения.

Для распознавания таких ситуаций перед фазой генерации тестов выполняется фаза обучения. В процессе обучения значение 0 присваивается схеме $$n_{i}$$ с последующей импликацией и анализом результатов. Этот процесс повторяется для значения 1. Предположим, что в процессе импликации $$n_{i}$$ инициализируется значением $$v_i,v_i\in \{0,1\}$$ и схема $$n_{i}$$принимает значение $$v_j\in \{0,1\}$$ в результате выполнения импликации, то есть $$(значение(n_i)=v_i)\Rigtharrow(значение(n_j)=v_j)$$. Пусть $$n_{j}$$ управляется вентилем $$g$$. Таким образом, если: 1) $$v_j$$ требует, чтобы все входы $$g$$ имели неконтролирующие значения и 2) прямая импликация дает значение $$v_j$$ схеме $$n_{j}$$ , то импликация $$(значение(n_i)=\overline{v}_i)\Rigtharrow(значение(n_j)=\overline{v}_j)$$имеет место. Условие 1) удовлетворяется, если $$v_j$$ имеет значение 0(1) и $$g$$ является вентилем типа И/НЕ -И(ИЛИ/НЕ-ИЛИ) или исключающее ИЛИ. При этом дополнительная функция проверяет отсутствие прямого пути от $$n_{j}$$ к $$n_{i}$$ . Для комбинационной ранжированной схемы при $$j>i$$ эта функция дает значение 0. Это подтверждает выполнение условия 2). Возможно, что описанная выше процедура не всегда найдет все возможные импликации, но в целом затраты на этапе обучения окупаются за счет сокращения возвратов в поиске решения.

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

Определение 19.1. Говорят, что сигнал $$y$$ доминирует над сигналом $$x$$-$$y\in dom(x)$$, если все ориентированные пути от $$x$$ ко внешним выходам схемы проходят через $$y$$.

Пусть $$x$$ является единственным в $$D$$-границе и множество сигналов $$dom(x)=\{y_{1}, y_{2},…, y_{n}\}$$ - выходы сигналов соответствующих вентилей множества $$G=\{g_{1}, g_{2},…, g_{n}\}$$. Тогда для всех вентилей $$g\in G$$ неконтролирующие значения присваиваются всем входам $$g$$, которые могут быть достигнуты из $$x$$ любым путем. Это иллюстрируется на рис. 19.10.

Здесь выход вентиля $$a$$ имеет D-значение, который разветвляется на вентили $$b$$ и $$c$$, которые далее сходятся на вентиле $$g$$. Очевидно, в этой ситуации сигнал $$d$$ должен быть установлен в неконтролирующее значение $$d=1$$.

Определение 19.2. Сигнал $$y$$ называется непосредственным доминатором сигнала $$x$$, если $$y\in dom(x)$$ и $$y$$ является элементом $$dom(x)$$ с минимальным рангом схемы.

Если непосредственные доминаторы всех сигналов известны, то доминаторы любого сигнала могут быть определены рекурсивно. Например, если сигнал $$y$$ является непосредственным доминатором сигнала $$x$$, и сигнал $$z$$ является непосредственным доминатором $$y$$, то сигнал $$z$$ является доминатором $$x$$.

Предложено дополнительное правило для уникальной активизации, которое требуется для обработки ситуаций, представленных на рис. 19.11.

Предположим, что сигнал $$a$$ является единственным сигналом D-границы или доминатором такого единственного сигнала. Он разветвляется на три вентиля И, на вход которых поступает сигнал $$b$$. Кроме этого, один из И вентилей имеет третий вход c. Предположим, что сигнал $$a$$ - единственный сигнал в D-границе, или доминатор такого сигнала и разветвляется на вентили $$g_{1}, g_{2},…, g_{n}$$ , которые все требуют одинаковых неконтролирующих значений - 0 или 1. Если сигнал $$b$$ разветвляется на те же вентили $$g_{1}, g_{2},…, g_{n}$$ , то $$b$$ присваивается неконтролирующее значение.

Кратное обратное распространение в SOCRATES использует тот факт, что некоторые часто встречающиеся схемные конфигурации обрабатываются как примитивы (базовые элементы). Например, это относится к схемам, реализующим исключающее ИЛИ. Важнейшим свойством этого элемента является то, что активизированный путь на входе двухвходового элемента распространяется на его выход независимо от значения второго входа. Например, значения $$(D,0)$$ дают на выходе значение $$D$$, а $$(D,1)$$ соответственно - $$D'$$. Более того, при распространении через (НЕ) исключающее ИЛИ необходимо только следить за тем, чтобы входы имели определенные значения и не имели одновременно два $$D$$-значения. Это можно расширить на произвольное число входов элементов исключающее ИЛИ, которые SOCRATES также поддерживает.

Отметим, что метод PODEM не поддерживает исключающее ИЛИ (как примитив) в отличие от $$D$$-алгоритма, который имеет примитивные $$D$$-кубы для этого элемента.

В методе SOCRATES исключающее ИЛИ обрабатывается в соответствии с правилами, представленными в табл. 19.4. Здесь $$c_{ij}$$ представляют значения управляемости, которые отражают сложность установки $$x_{1}$$ в $$i$$ и $$x_{2}$$ в $$j$$ для $$i,j\in\{0,1\}$$, где $$x_{1}$$ и $$x_{2}$$ - входы для двухвходового вентиля исключающего ИЛИ и $$y$$ - его выход. Этот подход можно использовать и для других примитивов высокого уровня, для которых получены соответствующие формулы. Основное преимущество этих примитивов лежит в сокращении числа разветвлений (потенциальных конфликтов). Но иногда это можно реализовать и на вентильном уровне. Например, если двухвходовой мультиплексор имеет 1 на обоих входах данных, то выходу следует установить значение 1 даже при наличии неопределенного значения на управляющем входе.

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

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

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

Прямая импликация - процедура снятия неопределённости на линиях схемы, выполняемая в прямом порядке от входов к выходам.

Обратная импликация - процедура снятия неопределённости на линиях схемы, выполняемая в обратном порядке от выходов ко входам.

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

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

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

В разделе 19.2 представлен метод- FAN, который является развитием метода и использует улучшенные процедуры кратного продвижения назад и уникальной активизации путей.

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

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

Чем отличается метод PODEM от $$D$$-алгоритма?

Опишите процедуру продвижения назад в методе PODEM.

Что такое "тяжелый" и "легкий" вход?

Как определяется цель в методе PODEM?

Как обрабатывается конфликт в методе PODEM?

Приведите общий алгоритм PODEM.

Постройте тест методом PODEM для неисправности $$x_{8}=0$$ приведенной ниже схемы рис. 19.12. (рис 19.12) Схема для упражнения 7, 12

Чем отличается метод FAN от PODEM?

Чем отличается процедура кратного продвижения назад?

Опишите улучшения в импликации по сравнению с предыдущими методами.

Прокомментируйте псевдокод алгоритма FAN.

Постройте тест методом FAN для неисправности const.0 выхода второго вентиля первого уровня приведенной ниже схемы рис. 19.12.

Чем отличается метод SOCRATES от метода FAN?

Приведите пример уникальной активизации.

В чем суть фазы обучения?

Приведите пример функционального примитива.

Что дает использование более крупных примитивов?