Синтез тестов для комбинационных схем

Генерация проверяющих тестов даже для комбинационных схем цифровых систем является сложной как в математическом, так и в техническом плане проблемой. Ее важнейшими аспектами являются:

Прежде всего, следует различать функциональные и структурные тесты. Алгоритмы построения функциональных тестов генерируют полное множество всевозможных тестовых наборов, которые позволяют полностью проверить функцию, реализуемую данной схемой. Например, для комбинационной схемы с $$n$$ входами и одним выходом функциональным тестом является множество всевозможных $$2^{n}$$ тестовых двоичных наборов, позволяющее восстановить булеву функцию, которая реализуется тестируемой схемой. Очевидно, что для схем большой размерности такой подход не всегда приемлем.

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

В теоретическом аспекте показано [16.1], что генерация тестов относится к классу NP-полных проблем (т.е. переборного типа), для которых не существует алгоритмов решения полиномиальной сложности. В практическом аспекте сложность ее решения зависит от применяемого алгоритма генерации теста. Эффективность разрабатываемых алгоритмов принято проверять на схемах из различных международных каталогов (benchmarks): ISCAS85 [16.2], ISCAS89 [16.3], ITC99 [16.4] и др. Псевдослучайные методы генерации тестов имеют низкую сложность алгоритма, но дают длинные тестовые последовательности и невысокую полноту. Детерминированные методы генерации дают тесты лучшего качества, но имеют большую сложность. Качество построенных тестов определяется, как правило, с помощью программ моделирования неисправных схем, в которых реализуются методы, рассмотренные в предыдущем разделе. Непосредственно процесс тестирования производится на специальном оборудовании - тестерах, которые обеспечивают подачу входных тестовых воздействий на схемы, съем выходных сигналов и их сравнение с эталонными значениями. Важнейшими характеристиками тестеров являются тактовая частота и объем памяти для хранения тестовых воздействий.

Структурные методы генерации тестов разделяются на два класса:

В первом разделе рассматривается структура системы генерации тестов, в последующих двух разделах 16.2-16.3 описаны методы построения тестов, которые используются на начальном этапе генерации проверяющих тестов для всей схемы. В последующих разделах будут изложены методы построения тестов для конкретной неисправности, которые, как правило, используются на заключительном этапе генерации тестов. С нашей точки зрения, их целесообразно применять на последнем этапе, когда осталось относительно небольшое число непроверенных неисправностей. На начальном этапе лучше применять другую стратегию. Нужны быстродействующие и простые в реализации методы построения тестов, которые позволяют с малыми затратами времени получить тест для большей части неисправностей. Одним из таких методов является псевдослучайный метод генерации тестов, достаточно подробно описанный в литературе [16.5,16.6].

16.1 Системы генерации тестов

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

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

Следует отметить, что полнота теста должна определяться относительно проверяемых (неизбыточных) неисправностей. Так, например, для схемы, имеющей 5% избыточных несправностей, полнота теста 96% является явно недостижимой. Потому иногда различают полноту и эффективность теста, которые определяются следующим образом. Полнота - $$P=\cfrac{O}{N}$$, где $$N$$ - общее число неисправностей и $$O$$ - число проверяемых на данном тесте неисправностей. Эффективность - $$P=\cfrac{O}{N-R}$$, где $$R$$ - число избыточных неисправностей.

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

Современная система генерации тестов включает в себя следующие основные компоненты:

Структура системы генерации тестов представлена на рис. 16.1. Здесь в первой фазе обычно используются псевдослучайные алгоритмы (или методы критических путей и т.п.), которые достаточно быстро позволяют достичь приемлемой полноты начального теста 50-80%. После этого выполняется моделирование неисправностей и определяется множество непроверенных неисправностей, которое обрабатывается на втором этапе.

Псевдокод укрупненного алгоритма генерации тестов первого этапа представлен ниже.

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

Первая фаза(схема)
  {
While(полнота или время не достигнуты)
{    
     Генерация теста(t);
     Моделирование неисправностей(t);
     p=число вновь проверяемых неисправностей(t);
     if(p приемлемо) then включение t в тест;
      } 
   } 

Вторая фаза(схема, множество неисправностей)
  {
   while(есть необработанные неисправности)
      {
         выбор новой неисправности f;
         генерация теста t для f;
          if(тест для f построен) then
              {
                 включение t  в тест;
                 моделирование неисправностей на наборе t;
                 исключение неисправностей, проверяемых t;  
               } 
       }
  }

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

Если оно превышает некоторый задаваемый пользователем порог, то неисправность исключается из дальнейшей обработки и объявляется непроверяемой. Наибольшие затраты времени имеют место для избыточных несправностей, для которых в худшем случае может потребоваться полный перебор всевозможных входных значений.

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

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

16.2 Псевдослучайный метод генерации тестов

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

В простейшем случае псевдослучайный двоичный набор обрабатывается следующим образом. Для текущего случайного двоичного вектора $$X_{i}$$ с помощью программы моделирования с неисправностями определяется величина $$n(X_{i})$$, которая характеризует число неисправностей, проверяемых на наборе $$X_{i}$$ без учета тех неисправностей, которые проверяются ранее построенной тестовой последовательностью $$X_{1}, X_{2},…, X_{i-1}$$.

Далее если $$n(X_{i})\ge Т$$ (порог), то набор $$X_{i}$$ включается в тестовую последовательность и генерируется следующий псевдослучайный набор. Если $$n(X_{i})<Т,$$ то этот входной набор бракуется и не включается в тест. Кроме этого, набор может браковаться и по некоторым другим причинам (например, если при переходе от предыдущего набора к текущему возникает опасное состязание сигналов). Этот процесс продолжается, пока не будет достигнута заданная пользователем полнота тестовой последовательности или пороговая величина длины или времени генерации теста. Упрощенная блок-схема алгоритма псевдослучайной генерации тестов представлена на рис. 16.2.

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

Кроме этого, был разработан ряд эвристических алгоритмов, которые генерируют псевдослучайные наборы с более сложным распределением вероятностей. При этом для каждого входного набора схемы рассчитываются вероятности подачи на него 0 и 1. Для определения этих вероятностей обычно на этапе препроцессорной обработки предварительно анализируют структуру схемы, либо используют адаптивные алгоритмы управления датчиками случайных чисел [16.7].

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

16.2 Метод критических путей

Из структурных методов на начальном этапе хорошо зарекомендовали себя на практике алгоритмы, основанные на методе критических путей [16.8-16.10]. Они дают неплохую полноту теста и относительно просты в реализации. Метод основан на том, что половина одиночных константных неисправностей на критических (активизированных) путях проверяется тестом. Поэтому желательно строить тесты, порождающие как можно больше критических путей, на которых изменение сигнала на любой линии схемы, входящей в такой путь, вызывает изменение сигнала на выходе схемы. Такие тесты строятся с использованием так называемых критических кубов логических элементов схемы (они будут описаны ниже). Начиная с выхода, где значение полагается равным $$0^{*}$$ или $$1^{*}$$ (звездочкой обозначается критичность), критические пути строятся по направлению к входам схемы. Для каждого логического элемента, выход которого получил критическое значение, осуществляется выбор критического куба - его входам присваиваются такие значения, чтобы один или более входов были критическими, т.е. чтобы при изменении значения на входе изменялось значение сигнала на выходе элемента. Например, если вентиль НЕ-И с входами $$х_{1}, х_{2}$$ имеет значение на выходе $$f=1^{*}$$, то значения на его входах $$х_{1}=0^{*}$$, $$х_{2}=1$$ критичны по отношению к $$х_{1}$$. Аналогично входные значения $$х_{1}=1, х_{2}=0^{*}$$ критичны по отношению к $$х_{2}$$. Набор $$х_{1}=0$$, $$х_{2}=0$$ не имеет критических значений, так как изменение $$х_{1}$$ или $$х_{2} $$ на единицу не вызывает изменения выхода вентиля $$f$$. Если выход вентиля $$f=0^{*}$$, то набор $$х_{1}=1^{*}, х_{2}=1^{*}$$ критичен по отношению к обоим входам. Суть метода заключается в том, что мы пытаемся распространить критические значения от выхода схемы к входам с помощью критических кубов элементов. Прежде чем формально описать алгоритм генерации тестов методом критических путей, рассмотрим его на небольшом примере схемы, изображенной на рис. 16.3.

Выбираем начальное значение выхода схемы $$х_{7}=0^{*}$$. Из табл. 6.1 критических кубов (методы их построения будут рассмотрены ниже) для вентиля И видно, что существуют два критических куба со значениями на выходе $$0^{*}10^{*}$$ и $$10^{*}0^{*}$$ (здесь значения записаны в порядке $$х_{5}, х_{6}, х_{7}$$). Выбирая первый из них, получаем $$х_{5} =0^{*}$$, $$х_{6}=1$$.

Из табл. 6.1 выбираем единственный для вентиля НЕ-И со значением $$0^{*}$$ на выходе критический куб $$1^{*}1^{*}0^{*}$$, который определяет $$х_{1}=1^{*}$$, $$х_{2}=1^{*}$$. Чтобы получить значение $$х_{6}=1$$, из трех возможных комбинаций значений входов выбираем $$х_{3}=0, x_{4}=0$$. Таким образом, мы получили тестовый набор $$х_{1}=1$$, $$х_{2}=1$$, $$х_{3}=0$$, $$x_{4}=0$$. Очевидно, что этот набор проверяет одиночные константные неисправности, противоположные критическим значениям, т.е. если линия помечена $$1^{*}$$, то проверяется неисправность const0 на этой линии. Если же она помечена $$0^{*}$$, то проверяется неисправность соnst1. На рис. 6.2 приведены еще три набора, которые построены аналогичным способом и вместе с первым набором составляют полный проверяющий тест на одиночные константные неисправности для рассматриваемой схемы.