Generating all test patterns for a given stuck-at fault of a logical circuit and its ROBDD implementation.pdf Построение проверяющих тестов для комбинационных схем в классе одиночных константных неисправностей сводится к нахождению одного тестового набора для неисправности рассматриваемого класса. Последняя проблема широко исследовалась в России и за рубежом, были разработаны различные методы ее решения [1]. Нахождение всех тестовых наборов для неисправности из заданного класса может потребоваться, например, при поиске проверяющего теста минимальной длины. Решение обеих задач традиционными методами, т.е. поиск всех тестовых наборов и построение проверяющего теста минимальной длины, связано с большими вычислительными затратами и потребностью хранить огромные объемы информации. Поэтому на практике ограничиваются поисками нескольких или одного тестового набора для заданной неисправности и построением минимизированных проверяющих тестов, достаточно близких к минимальным. В приложениях, связанных с тестированием неисправностей задержек путей схемы [2, 3], требуется находить все тестовые наборы, порождаемые конкретной конъюнкцией ДНФ, описывающей поведение схемы. Известно, что поведение подсхемы в условиях включения ее в схему может быть описано частичной булевой функцией [4, 5]. Этот факт используется для минимизации схемы в целом. Множества единичных и нулевых наборов частичной функции подсхемы могут, на наш взгляд, быть представлены с помощью всех тестовых наборов для соответствующих константных неисправностей. Один из подходов к синтезу частично программируемых логических схем высокой производительности [6] основан на описании поведения подсхемы, включенной в заданную схему, в виде реализации частичной функции. Реализаций может быть множество. Точное знание частичной функции позволяет найти более качественную в том или ином смысле реализацию и определить места включения в схему из вентилей программируемых блоков с целью маскирования возможных неисправностей. Речь идет о неисправностях, обнаруживаемых на заключительных этапах проектирования схем. Для коррекции схемы необходимо вернуться на ранние этапы проектирования, что существенно увеличивает стоимость проектирования схемы. Присутствующие в схеме резервные программируемые блоки позволяют маскировать обнаруженную неисправность и тем самым избежать возвращения к ранним этапам проектирования. Исходя из вышесказанного, важно уметь находить множество всех тестовых наборов для заданной неисправности и компактно его представлять. В данной работе предлагается находить множество всех тестовых наборов для константной неисправности на полюсе логического элемента на основе разработанного нами ранее метода достраивания конъюнкций. Используется представление схем и подсхем в виде ROBDD-графов. Построение множества всех тестовых наборов выполняется путем перемножения ROBDD-графов подсхем заданной схемы. Как известно, графовое представление булевых функций является более компактным по сравнению с аналитическими способами задания функций в виде ДНФ или КНФ, а операции над ROBDD-графами обладают полиномиальной сложностью. В 1-м разделе работы обсуждается метод достраивания конъюнкций, что необходимо для понимания предлагаемого нами алгоритма построения всех тестовых наборов для заданной неисправности в комбинационной схеме. Во 2-м разделе предлагается алгоритм построения множества всех тестовых наборов, приводится пример, его иллюстрирующий, и обсуждается распространение алгоритма на комбинационный эквивалент схемы с памятью в условиях описания поведения последова-тельностной схемы системой частичных булевых функций. 1. Метод достраивания конъюнкций для построения одного (любого) тестового набора В работе [1] нами был предложен метод достраивания конъюнкций, в котором выявлены возможности сокращения перебора при поиске одного (любого) тестового набора для одиночной константной неисправности полюса логического элемента схемы. Предполагается, хотя это и не обязательно, что схема построена из вентилей OR, NOR, AND, NAND, NOR, EXOR. Заданы одна выходная комбинационная схема и неисправный полюс v. Обозначим через ф(Х), ф'(Х) булевы функции, реализуемые схемой в исправном и неисправном состояниях, гдеХ = {xb.. ,xn} -множество входных переменных схемы. Отыскание теста для данной неисправности сведем к отысканию корня булева уравнения А Рис. 2. Подсхема, реализующая функцию g(X,v) Рис. 1. Комбинационная схема С D (Ф) D (Ф") v D (Ф) D (Ф") = 1. По заданной схеме С (рис. 1) и заданному неисправному полюсу v выделим подсхему (рис. 2), реализующую функцию c;(X,v), при условии, что переменная v рассматривается в качестве входной наряду с переменными x1,...,x„. Выделим также подсхему (рис. 3), выходом которой является неисправный полюс v, а входами - переменные x1,...,xn. Эта подсхема реализует функциюfX). Х| х2 Хз Рис. 3. Подсхема, реализующая функцию f(X) Для схемы на рис. 2 функция c;(X,v) в виде ДНФ представляется выражением x1v v x1v v x4v, а функция f(X) - выражением x: x2 v x3. Обозначим через о тип неисправности на полюсе v, о е {0,1}. Из построения функций c;(X,v) и f(X) следует, что ф(Х) = c(X, AX), 9v(X) = q(X, о). Обозначим через D(q) ДНФ функции c;(X,v). Представим эту ДНФ в виде K v Kv v Kv; в ДНФ K - конъюнкции, не содержащие литер v, v; в ДНФ Kv включаются конъюнкции, содержащие литеру v; в ДНФ Kv - конъюнкции, содержащие литеру v . Если о = 0 (1), то Kv (Kv ) обращается в ноль, а Kv (Kv) обращается в Kv' (Kv), причем ДНФ Kv' (Kv) получается из ДНФ Kv (Kv ) вычеркиванием литеры v (v). Тогда для о = 0(1) D^v) = K v Kv (K vKv ). Пусть ДНФ Kv (Kv ) получается из Kv (Kv) подстановкой вместо литеры v (v) функции A (X) AX)), представленной в виде ДНФ. Обозначим через в набор значений переменных хь..., x„. Теорема 1. в - тест для неисправности о = 0(1) и ф(в) = 1, если и только если Kv" (в) = 1 ( Kv' (в) = 1), K (в) = 0, Kv' (в) = 0 (Kv (в) = 0). Доказательство этой теоремы приведено в работе [1]. Пусть ф(X),

Скачать электронную версию публикации