Вставьте картинку Рассматривается поиск одиночных константных неисправностей типа const=0, const=1 на входах и выходах элементов; Состояние тестируемой схемы описывается тестовым кубом TK={t1,t2,...,tn}, элементы которого первоначально не определены (ti=Х); В процессе построения теста элементы тестового куба доопределяются значениями из алфавита {0,1,x,D, } Выделяют 4 этапа алгоритма Рота: Нахождение условий проявления заданной неисправности на выходе элемента; Активизации пути от проверяемого элемента до выхода схемы; Обеспечение условий активизации пути; Доопределение входного набора до алфавита (0,1). АЛГОРИТМ АКТИВИЗАЦИИ ПУТИ (D-АЛГОРИТМ)

ЭТАП 1. Нахождение условий проявления заданной неисправности на выходе элемента. задана неисправность const=h на входе или выходе элемента e. Правило построения D-кубов неисправности элемента ДЛЯ ВХОДНОЙ неисправности выбираются вырожденные D- кубы со значением соответствующего входа противоположным ошибке, остальным входам присваиваются 1 (для И, И-НЕ), или 0 ( для ИЛИ, ИЛИ-НЕ), а выходной координате присваивается значение D (при e=1 исправной схемы) и (при e=0). ДЛЯ ВЫХОДНОЙ неисправности выбираются вырожденные кубы со значением выхода НЕ h, выходу присваивается значение D (при e=1 исправной схемы) и (при e=0). Для пересечения с TK берется один из D-кубов неисправности, при неудовлетворительном результате берется очередной D-куб и т.д. 1

Примеры построения DKN на 2 на D на 2 на D на 4 на Х Х D 0 Х Х D X 1 Х D X 0 Х D X Х 1 D X Х 0 D на 4 на &

ЭТАП 2. Активизация пути от проверяемого элемента до выхода схемы Присоединение очередного элемента к активизированному пути с проверкой непротиворечивости сигналов на вх. и вых. элементов ПРИСОЕДИНЕНИЕ: 1) Формируется вектор активности VA в виде списка номеров элементов, связанных по входам с выходом последнего активизированного элемента. 2) Из VA выбирается очередной элемент в соответствии со стратегией «вглубь» или «вширь». 3) Осуществляется D-движение через элемент поиском непустого пересечения D-кубов подсоединяемого элемента с тестовым кубом ТК: Здесь ai, ti – значения сигналов в DK и ТК соответственно. Если D-движение невозможно – делается попытка подсоединить другой элемент из VA. 3

4 ПРОВЕРКА НЕПРОТИВОРЕЧИВОСТИ СИГНАЛОВ ИМПЛИКАЦИЯ - поиск противоречивых сигналов на входах/выходах элементов, у которых появилось фиксированное значение 0/1 на входе (при фиксированном выходе) или выходе. МЕТОД ПРОВЕРКИ: Поиск непустого пересечения вырожденного VK или тупикового TDK с тестовым кубом. Правило выбора VK или TDK VK берется в случае, если входной алфавит проверяемого элемента {0,1,X}, TDK – выбирается при входном алфавите проверяемого элемента {0,1,X, D, }. Если все пересечения пусты – возврат к п.3.

5 ПРИМЕРЫ D-ДВИЖЕНИЙ & & & & 9

6 D- движение через элемент линий ЗначенияХХDX10X00 Состояние линий схемы в ТК А) Выполним d-движение через е 7, т.к. на входе сигнал D VK e7 DK e X 1 1 D X 0 1 D 1 TK DK е 7 = XDX 1D = 1D D d d 1 D Новое значение ТК записывается в таблицу. линий Значения 1ХХDX10X00 Значения 2Х1DX100 0

7 ПРИМЕР ПРОВЕРКИ НЕПРОТИВОРЕЧИВОСТИ СИГНАЛОВ На линии 2 появилось фиксированное значение 1. Можно выполнить импликацию на элементах 5 и 9, т.к. линия 2 является для них входной, а на выходах – фиксированные значения ! а) VK е 5 TK = Х 0 Х 1 1 Х б ) Для импликации е 9 следует использовать тупиковый D-куб т.к. тестовый куб ТК на линиях 2,7,9 имеет значения в алфавите {1,,0}. VK е 9 TDKe9 ТК = Х Х 0 0 D D 0 0 0

ЭТАП 3. ОБЕСПЕЧЕНИЕ УСЛОВИЙ АКТИВИЗАЦИИ ПУТИ Просмотр элементов схемы от выходов ко входам и присвоение входным линиям каждого элемента значений, обеспечивающих заданный (1/0) выход. Порядок обеспечения значений: Составляется список S кандидатов на обеспечение входов из элементов с фиксированными значениями выходов в ТК и неопределенными входами. Из списка выбирается элемент с МАХ номером и осуществляется поиск непустого пересечения ТК и VK. Если все пересечения, возврат к этапу 2. В процессе определения список S может пополняться новыми кандидатами. 8

ПРИМЕР ОБЕСПЕЧЕНИЯ УСЛОВИЙ АКТИВИЗАЦИИ ПУТИ Линии ТК1X11X10D 9 1 & & &

ПРИМЕР ОБЕСПЕЧЕНИЯ УСЛОВИЙ АКТИВИЗАЦИИ.1 а) Список на обеспечение S={е 8, е 6} включает элементы, на выходах которых фиксированные значения, а на входах есть неопределенные сигналы (линии 2,5). б) Выбираем элемент е 8 и доопределяем входы: VK e8 TK ТК1 – 1 Х 0 1 X 0 X X 0 = - 2 варианта X 1 0 ТК2 – Х Линии ТК1X11X10D ТК11111X10D ТК21X11110D

ПРИМЕР ОБЕСПЕЧЕНИЯ УСЛОВИЙ АКТИВИЗАЦИИ.2 Для состояния схемы ТК1 продолжим обеспечение е 6. VK e6 TK X = - отменяем состояние ТК1, X 0 1 и выбираем ТК VK e6 TK X 1 1 Х 1 = – итог. X Результат Т={(10111),1}. 11 Линии ТК2 1X11110D D

ЭТАП 4. Доопределение входного набора до алфавита 0,1 Набор входных значений из тестового куба Т доопределяется из алфавита {0,1,x,D, } в алфавит { 0,1 } по правилу: 12

ПРИМЕР ПОСТРОЕНИЯ ТЕСТА Этап 1. Построение D-куба неисправности на 3 входе е 6 VK e X 0 DKN={1 1 D}. X & & & & Тестовый куб Актив- ность VA Х 1 1 Х Х D Х Х Хe6e6e8e8

Тестовый куб Актив- ность VA Х 1 1 Х Х D Х Х Хe6e6e8e8 14 Этап 2. АКТИВИЗАЦИЯ ПУТИ D-движение через е Импликация - 0 на выходе е 5. DKe8 TK = 0DD VKe5 TK - принято D X D X 0 X 1 X D D X Тестовый куб Актив- ность VA Х 1 1 Х Х D Х Х Хe6e6e8e8 Х 1 1 Х 0 D Х D Хe6, e8e9

Этап 2. АКТИВИЗАЦИЯ ПУТИ. 2 Тестовый куб Актив- ность VA Х 1 1 Х Х D Х Х Хe6e6e8e8 Х 1 1 Х 0 D Х D Хe6, e8e D-движение через е Импликация - 1 на выходе е 7. DKe9 TK = 11D VKe7 TK - принято D X X D X 0 X 1 1 X 1.…….. X Тестовый куб Актив- ность VA Х 1 1 Х Х D Х Х Хe6e6e8e8 Х 1 1 Х 0 D Х D Хe6, e8e9 Х 1 1 Х 0 D 1 D Хe6, e8,е 9 выход

ЭТАП 3. ОБЕСПЕЧЕНИЕ ЗНАЧЕНИЙ {e7,e5}. Тестовый куб Актив- ность VA Х 1 1 Х Х D Х Х Хe6e6e8e8 Х 1 1 Х 0 D Х D Хe6, e8e9 Х 1 1 Х 0 D 1 D Хe6, e8,е 9 выход Х D 1 D Хe6, e8,е 9 выход VKe7 TK = VKe5 TK - принято X 1 1 X 1 0 X X T= {(1110), 0}

17 Этап 2. АКТИВИЗАЦИЯ ПУТИ D-движение через е Импликация - 0 на выходе е 5. DKe8 TK = 0DD VKe5 TK - принято D X D X 0 X 1 X D D X Тестовый куб Актив- ность VA Х 1 1 Х Х D Х Х Хe6e6e8e8 Х 1 1 Х 0 D Х D Хe6, e8e9

ПРИМЕР ЛОГИЧЕСКОЙ СХЕМЫ 18 & 1 1 & & 1 & ВХОДЫВХОДЫ

ПРИМЕР МАТЕМАТИЧЕСКОЙ МОДЕЛИ СХЕМЫ (вырожденные кубы элементов) элемента Номер линии x01x 0x10x x10x1 x01x x01x 0x10x x10x1 x01x x01x0 10x10x x10x1 01x01x x01x01 0x10x

ПРИМЕРЫ D–КУБОВ ЭЛЕМЕНТОВ элемента Номер линии D D 6 0D00D0 00D00D DDDD 7 1D11D1 11D11D DDDD 20

ПРИМЕРЫ ТУПИКОВЫХ D–КУБОВ ЭЛЕМЕНТОВ 21 элемента Номер линии D11D D11D D00D00 00D00D D11D D11D