Детерминированные методы построения тестов

Направленные алгоритмы, наоборот, формируют «кандидаты в тесты», предназначенные для проверки заданной неисправности либо заданного участка пути в схеме. Используемые алгоритмы, как правило, представляют собой развитие соответствующих алгоритмов для комбинационных схем. Мы рассмотрим получивший широкое распространение эвристический алгоритм активизации путей, основанный на D-алгоритме для комбинационных схем. Все направленные алгоритмы связаны с перебором вариантов, иногда чрезвычайно большим, поэтому время поиска «кандидатов в тесты» для заданной неисправности обычно ограничивается программно. 

Детерминированное построение тестов ==> NP-полная задача

Задача построения теста :

-выбор цепочки элементов (пути к внешнему выходу);

-обеспечение условий транспортирования неисправности на выход;

-доопределение условий транспортирования на внешних входах.

Характеристики:

-процедуры импликации

прямая импликация - вычисление выходных значений по входным;

обратная импликация - вычисление входных значений по выходным

Методы:

-метод активизации путей ;

-метод эквивалентных нормальных форм ;

-метод булевых разностей ;

-метод активизации путей (D-алгоритм и его модификации) .

20. Логические основы проверки неисправностей.

Сущность моделирования неисправностей состоит в определении влияния одного или нескольких дефектов на состояния линий объекта при подаче тестовых последовательностей.

Если значения наблюдаемых выходных линий искажаются при наличии дефектов, последние являются проверяемыми на заданном тесте, который называется проверяющим. Под дефектом будем понимать каждое отдельное несоответствие объекта нормативно-технической и/или конструкторской документации, приводящее объект в неработоспособное состояние. Математическую модель дефекта будем называть неисправностью.

Правило. Неисправность проверяется на тесте (двоичном векторе), если она изменяет состояние хотя бы одного наблюдаемого выхода.

На сегодня известны десятки типов дефектов цифровых схем, реализованных на дискретных логических элементах, сгруппированных в классы. Здесь и далее рассматриваются константные неисправности, если не оговорено иное. Под константной неисправностью понимается постоянное значение "логический 0" или "логическая 1" на линии цифровой схемы. Если в схеме возникает одна константная неисправность, она называется одиночной константной неисправностью (ОКН).

Обозначаются константные неисправности следующим образом : 1⁰ - константная неисправность нуля на первой линии, 5¹ - константная неисправность единицы на пятой линии.

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

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

21. Моделирование неисправностей, явные, неявные методы.

20+ Все методы моделирования неисправностей по способу реализации можно разделить на явные и неявные. При реализации явных методов моделирования выполняется математическое "внесение" в схему неисправностей (по одной или группами) и моделирование схемы с этими неисправностями. К явным методам моделирования относятся метод одиночного моделирования неисправностей и метод параллельного моделирования При реализации явных методов количество циклов моделирования схемы на одном наборе равно числу неисправностей (числу вносимых групп неисправностей). При реализации неявных методов выполняется вычисление списка неисправностей, проверяемых (обнаруживаемых) на одном наборе. При этом число циклов моделирования схемы равно числу наборов. При неявных методах моделирования неисправностей "внесение" неисправностей заменяется специальными формулами или процедурами обработки списков неисправностей на примитивах схемы. К неявным методам относятсядедуктивный, совместный и кубический методы моделирования неисправностей.

22. Одиночное моделирование неисправностей, пример.

В основу одиночного моделирования неисправностей положена идея "математического" внесения ОКН эквипотенциальной линии в схему с целью анализа её проявления на внешних выходах объекта при подаче тестовых последовательностей. Если внесённый дефект изменяет состояние исправного поведения хотя бы одного наблюдаемого выхода при подаче теста (одна или более входных последовательностей), то он является проверяемым. ОКН вносятся в схему последовательно друг за другом и для каждой неисправности вычисляются реакции на всех линиях.

Внесение неисправности в схему принято обозначать "крестиком" на соответствующей линии, а тип неисправности обозначается =0 (константа 0) или =1 (константа 1). При моделировании неисправностей исправное значение на линии схемы обозначается до наклонной черты, а неисправное - после нее. Например, значение на линии схемы 0/1 обозначает, что на рассматриваемой линии в исправном состоянии получается нулевое значение а в неисправном - единичное. Признаком проверяемости неисправности является разные значения до наклонной черты и после нее. При одиночном моделированиии неисправностей в качестве наблюдаемых выходов обычно рассматриваются внешние выходы схемы и изменение значения при наличии неисправности фиксируется именно там.

Для схемы, имеющей К линий, число неисправностей равно 2*К (за счет констант нуля и единицы).

Обычно при реализации одиночного моделирования неисправностей в компьютерной программе для обработки неисправных значений на координатах моделируемого вектора используются регистровые машинные команды, позволяющие параллельно обрабатывать 16 (32, 64) разряда в зависимости от типа компьютера. Реализованную таким образом процедуру моделирования принято называть, параллельным моделированием неисправностей.

Достоинством одиночного моделирования неисправностей является простота и отсутствие каких-либо специальных процедур для выполнения моделирования. Основным недостатком является необходимость проведения ( 2*n + 1 ) циклов моделирования для каждого набора, где n - число линий схемы ( моделирование всех нулевых и единичных неисправностей плюс исправный набор ). Указанный недостаток делает одиночное моделирование неисправностей сугубо теоретическим учебным методом, который реально па практике не применяется.

Пример:

В приведенной ниже таблице показаны результаты исправного моделирования набора 010 для схемы y = not( x1&x2 V x3 ) и одиночного моделирования всех её ОКН.

Первая строка таблицы показывает результат исправного моделирования указанного набора, а остальные строки - результат одиночного моделирования ОКН, причем тип моделируемой неисправности указывается в первой ячеке соответствующей строки. В последнем столбце каждой строки приведен результат суммы по модулю 2 соответствующего значения на выходе схемы с неисправностью в данной строке с результатом на выходе в первой строке (для исправного моделирования). Таким образом в последем столбце 1 стоит там, где результаты неисправного моделирования на внешнем выходе отличаются от исправного значения, т.е. указанная в первом столбце неисправность обнаруживается на внешнем выходе схемы (линия 5). В выделенной строке таблице квадрат обозначает линию, на которой моделируется неисправность. При этом на рисунке она означается крестиком на линии.

23. Представление диагностической информации, ТФН, ТН, примеры.

Результаты моделирования неисправностей могут быть представлены в форме таблицы неисправностей (ТН). ТН может быть классической или многозначной(совмещенной). Количество столбцов совмещенной ТН равно числу линий схемы, количество строк - числу тестовых наборов. В ячейке таблицы стоит 1 если на тестовом наборе (в соответствующей строке) на рассматриваемой линии (соответстующий столбец) проверяется неисправность "константа 1"; в ячейке таблицы стоит 0 если на тестовом наборе (строка) на рассматриваемой линии (столбец) проверяется неисправность "константа 0". Если ни одна неисправность на рассматриваемой линии не проверяется этим тестовым набором, то в ячейке таблицы стоит "-".

Совмещенная (многозначная) ТН получается в результате моделирования неисправностей учебной системой интрерпретативного моделирования неисправностей DCP (Deductive Circuit Processor), и пример такой ТН для рассматриваемой схемы приведен ниже .

Для перехода от совмещенной ТН к классической необходимо выполнить следующее.

1) Количество столбцов в классической ТН по отношению к совмещенной удваивается. При этом левая половина классической ТН представляет собой столбцы, соответствующие неисправностям "константа 0" на соответствующих линиях, а правая половина данной ТН представляет собой столбцы, соответствующие неисправностям "константа 1" на соответствующих линиях.

2) В левой части классической ТН, в столбце для рассматриваемой линии, единица ставится в той строке, где в совмещенной ТН в соответствующем столбце стоит "0".

3) В правой части классической ТН в столбце для рассматриваемой линии единица ставится в той строке, где в совмещенной ТН в соответствующем столбце стоит "1".

4) Остальные ячейки классической ТН остаются пустыми (в некоторых литературных источниках пустые ячейки ТН заполняются нулями).

Классическая ТН для рассматриваемой схемы приведена ниже. 

Классическая ТН (которую в дальнейшем будем называть просто ТН) должна отвечать таким условиям.

1) Обнаруживаемость - в каждом столбце ТН должна стоять хотя бы одна 1.

2) Различимость - в ТН не должно быть двух одинаковых столбцов.

3) Минимальность - при удалении из ТН любой строки будет нарушаться условие обнаруживаемости. 

В рассматриваемой ТН нарушен принцип различимости, т.е имеются одинаковые столбцы, например, столбцы 1¹, 4¹, 5¹, 2⁰, 3⁰, 6⁰, 7⁰, 8⁰ имеют по одной единице в первой строке. Остальные условия в этой таблице соблюдаются. Для восстановления условия различимости одинаковые столбцы объединяются в классы эквивалентных дефектов (КЭД). Ниже приведена ТН с разбиением на КЭД, где различные КЭД обозначаются буквой К_i и перечислены под самой ТН. 

Разбиение столбцов рассматриваемой ТН на классы эквивалентных дефектов. Результирующая таблица для КЭД приведена ниже. В этой ТН восстановлено условие различимости (нет одинаковых столбцов).

24. Неявные методы моделирования неисправностей, достоинства, недостатки.

Все методы моделирования неисправностей по способу реализации можно разделить на явные и неявные. При реализации неявных методов выполняется вычисление списка неисправностей, проверяемых (обнаруживаемых) на одном наборе. При этом число циклов моделирования схемы равно числу наборов. При неявных методах моделирования неисправностей "внесение" неисправностей заменяется специальными формулами или процедурами обработки списков неисправностей на примитивах схемы. К неявным методам относятся дедуктивный, совместный и кубический методы моделирования неисправностей.

Простейшим неявным методом моделирования неисправностей является дедуктивный метод.

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

25. Существенность переменных, булева производная, пример.

Любая комбинационная схема Y=f(x₁,x₂, .....x_n), где x_i - входные переменные, а Y - выходная переменная, может быть описана таблицей истинности или кубическим покрытием.

Булева переменная x_i существенна на двоичном наборе (x₁, x₂, ....., x_n), если изменение ее значения на противоположное приведет к изменению на противоположное значения функции Y на этом наборе.

Булева переменная x_i является существенной, если булева производная данной функции по переменной x_i равна 1, т.е остальные переменные функции имеют такие значения, чтобы производная равнялась 1.

Существенная переменная x_i на двоичном наборе (x₁,x₂, ..... x_n) определяется значением булевой производной на этом наборе. Если булева производная на двоичном наборе (x₁,x₂, ..... x_n) принимает значение 1, то она существенна на этом наборе. В противном случае переменная x_i несущественна на данном наборе. Группа булевых переменных x_i...х_j существенна на двоичном наборе (x₁,x₂, ..... x_n), если одновременное изменение всех значений указанных переменных на противоположные приведет к изменению значения функции Y.

26. Списки неисправностей, списки предыдущих рангов, формула получения списков. Алгоритм неявного моделирования.

27. Дедуктивное моделирование, пример.

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

Алгоритм дедуктивного моделирования неисправностей состоит из следующих шагов.

1. Построение структурно-функциональной модели схемы.

2. Выполнение исправного моделирования заданного входного набора.

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

4. Выбираются по порядку ПЭ схемы, и для каждого из них выполняется формирование выходных списков неисправностей на основании результатов исправного моделирования и дедутивных формул для элементов логического базиса (И, ИЛИ, НЕ, И-НЕ, ИЛИ-НЕ). Следует отметить, что инверсия не влияет на вид формул дедуктивного моделирования. Ниже приведены дедуктивные формулы для элементов И и ИЛИ.

5. Пункт 4 выполняется до тех пор, пока не будут составлены списки проверяемых неисправностей для всех ПЭ.

6. На основании результирующего списка неисправностей на внешнем выходе (выходах) схемы формируется строка таблицы неисправностей.

S⁰ - вход равен 0; S¹  равен 1 (0 - существенное значение) S_вых = S⁰ \ U S¹ S_вых = US¹, если все 1

S¹ - вход равен 1; S⁰  равен 0

(1 - существенное значение) S_вых = S¹ \ U S⁰ S_вых = US⁰, если все 0

28. Особенности кубического представления ПЭ с точки зрения существенности. Определение существенности переменной на наборе.

29. Кубическое моделирование неисправностей формулы и процедуры получения частичных списков.

Общий список неисправностей ПЭ формируется на основании суммирования частичных списков для каждого куба плюс собственная неисправность выхода

где m - количество кубов КП,

30. Алгоритм кубического моделирования неисправностей, пример.