Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

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







Дата добавления: 2015-04-19; просмотров: 625. Нарушение авторских прав

Studopedia.info - Студопедия - 2014-2017 год . (0.005 сек.) русская версия | украинская версия