D-алгоритм

Недостаток метода существенных путей состоит в необходимос­ти перебора вариантов при поиске проверяющих входных наборов. Другой подход состоит в «конструировании» проверяющего набо­ра по структуре схемы без анализа ее работы на входных наборах.

Наряду с понятиями сжатого куба и D-куба вводится понятие D-куба неисправности элемента, который образуется из тестовых наборов: приписыванием выходу ЛЭ сигнала D, если на тестовом наборе на выходе имеется изменение сигнала 1 → 0, и приписыва­нием сигнала , если имеется изменение сигнала 0 → 1. D-кубы неисправности приведены на рис. 4.20. Они определяют условие проявления неисправности элемента указанием сигналов на вхо­дах элемента.

Например, D-куб неисправности элемента ИЛИ об­разуется из тестовых наборов (00, 10, 01) приписыванием набору 00 сигнала , так как обнаружение неисправностей на этом набо­ре связано с изменением сигнала на выходе элемента вида 0 → 1, а также приписыванием наборам 10 и 01 сигналов D, так как обна­ружение неисправностей на них связано с изменением сигнала на выходе элемента вида 1 → 0.

D-алгоритм состоит из двух этапов:

1) D-продвижение;

2) обратное доопределение.

На первом этапе осуществляется «продвижение» символа D на выход схемы, т.е. создается хотя бы один существенный для неис­правности D-путь. Для этого рассматриваются все возможные пути от места неисправности до выхода схемы. Записывается расширенный D-куб неисправности. При этом предполагается, что все координаты, кроме уже определенных в основном кубе, равны х.

Задача D-алгоритма заключается в том, чтобы в соответствии с логикой схемы заменить неопределенные координаты х на симво­лы из множества {0,1, D, } так, чтобы выходная линия схемы имела символ D или .

Вводится операция D-пересечения (обозначается символом ) над элементами из множества {0,1, х, D, }. Пусть а,b {0,1, х, D, }. Тогда операция D-пересечения задается следующими равенствами:

1) а а = а (совпадение сигналов);

2) a x = a (доопределение сигнала);

3) a b = , если а ≠ b, а ≠ x и b ≠ x

Символ означает, что пересечение является пустым (или про­тиворечивым). Пересечение является пустым (противоречивым), если хотя бы одна координата вектора a b равна .

В результате выполнения первого этапа D-алгоритма определя­ются значения некоторых входных переменных. Значения остальных входных переменных находятся при выполнении второго этапа D-ал­горитма — обратного доопределения.

Процедура доопределения начинается с выходного элемента, а затем рассматриваются последовательно элементы с убывающими номерами, выходам которых приписаны 0 или 1. При этом реша­ется следующая задача. По известному сигналу на выходе элемен­та (0 или 1) определяются сигналы на входах элемента (если они не определены). Для этого выполняется операция D-пересечения по­лученных в результате выполнения первого этапа D-алгоритма D-кубов со сжатыми кубами таблицы истинности элемента. Если получено непустое D-пересечение, то оно определяет входной на­бор, проверяющий данную неисправность.

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