Машинно-ориентированный синтез тестов icon

Машинно-ориентированный синтез тестов




Скачати 114.08 Kb.
НазваМашинно-ориентированный синтез тестов
Дата01.07.2012
Розмір114.08 Kb.
ТипЛекция
1. /lec1 Надежность вычислительных устройств.doc
2. /lec10 Подходы построения производственных тестов комбинационных схем.doc
3. /lec11 Случайное тестирование ВУ.doc
4. /lec12 Проектирование генераторов псевдослучайных тестов.doc
5. /lec13 Элементы вероятностной логики.doc
6. /lec14 Показатели неисправности при случайном тестировании.doc
7. /lec15 Построение зависимости длины случайного теста от вероятности обнаружения неисправностей.doc
8. /lec16 Оптимизация случайного теста ВУ.doc
9. /lec2 Дефекты элементов вычислительной техники.doc
10. /lec3 Структурные методы синтеза тестов комбинационных схем.doc
11. /lec4 Показатели тестируемости неисправностей.doc
12. /lec5 Булева производная и ее применение для вычисления наблюдаемости.doc
13. /lec6 Наблюдаемость и активизация путей схемы.doc
14. /lec7 Эквивалентность доминирование и совмещение КН.doc
15. /lec8 Синтез тестов КН комбинационных схем по методу булевой производной.doc
16. /lec9 Машинно-ориентированный синтез тестов комбинационных схем по D-алгоритму.doc
Лекция 1 надежность вычислительных устройств двумя важнейшими техническими категориями изделия вообще и вычислительного устройства, в частности, являются качество и надежность. Качеств о
Комбинационных схем
Тестирование ву на случайных тестовых воздействиях называется случайным
Проектирование генераторов псевдослучайных тестов
Аксиомы теории вероятностей
Лекция 15 построение зависимости длины случайного теста
Дефекты элементов вычислительной техники
Структурные методы синтеза тестов комбинационных схем
Лекция 4 показатели тестируемости неисправностей
Лекция 5 Булева производная и ее применение для вычисления наблюдаемости Определение бпx
Лекция 6 Hаблюдаемость и активизация путей схемы Наблюдаемость кт теснейшим образом связана с понятием схемного пути. Схемный путь
Синтез тестов кн комбинационных схем по методу булевой производной
Машинно-ориентированный синтез тестов

Л е к ц и я 9


МАШИННО-ОРИЕНТИРОВАННЫЙ СИНТЕЗ ТЕСТОВ

КОМБИНАЦИОННЫХ СХЕМ ПО D-АЛГОРИТМУ


D-алгоритм является дальнейшим развитием концепции активизации путей проверяемой схемы. В отличие от метода одномерной активизации данный алгоритм основан на возможности одновременной активизации всевозможных путей ( как одномерных так и многомерных ) от места возникновения неисправности ко всем выходам схемы. Формальное описание алгоритма базируется на D-исчислении – модифицированном кубическом исчислении булевых функций .


1. D-исчисление


D - и с ч и с л е н и е представляет собой р - исчисление, дополненное следующими понятиями и определениями.

D - к у б . Это определенное над опорными координатами вентиля либо схемы множество, состоящее из элементов {0,1,х,d,d} и составленное таким образом, чтобы хотя бы одной входной и одной выходной координатам соответствовал символ d либо d. Символы d, d могут принимать значения из множества {0,1}.

D-куб имеет к р а т н о с т ь k ( будем также называть такой его n-мерным кубом) , если символы d либо d соответсвуют k входным координатам. D - куб кратности 1 называется п р о с т ы м .

Формально построение d-куба сводится к попарному пересечению кубов из единичного и нулевого вырожденных покрытий по следующим соотношениям:


0 ? 0 = 0 ? х = 0 ,

1 ? 1 = 1 ? х = 1 ,

х ? х = х ,

1 ? 0 = d ,

0 ? 1 = d .


Например, для элемента 2 ИЛИ d-кубы можно построить следующим образом:


│ 1 2 3 │

├────────────┤

С1│ 1 х 1 │

С2│ х 1 1 │

С3│ 0 0 0 │

├────────────┤

простой d-куб С4│ d 0 d │ С1 ? С3

простой d-куб С5│ 0 d d │ С2 ? С3

d-куб кратности 2 С6│ d d d │(С1 ? С2 ) ? С3

простой d-куб С7│ 0 d d │ C5


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


Ф и з и ч е с к а я и н т е р п р е т а ц и я d - к у б а.

В простом d-кубе отражается факт управляемости выхода вентиля от одного входа; в кратном кубе выходом управляют одновременно несколько входов.


D - к у б н е и с п р а в н о с т и.

Это понятие используется для выражения теста неисправности вентиля либо схемы в целом через входные и выходные координаты. D - куб неисправности состоит из входного набора ( локального теста ) и символов d, d на выходных координатах. Локальный тест строится над входными координатами вентиля таким образом, чтобы под его воздействием неисправность проявлялась (наблюдалась) на выходе вентиля ( схемы ). Символ d говорит о том, что элемент ( схема ) в исправном состоянии на выходе должен иметь 1, в неисправном - 0; для символа d - наоборот. Различают примитивный и сложный d-кубы неисправности вентиля и d-куб неисправности схемы. П р и м и т и в н ы й d-куб строится над координатами одного вентиля, с л о ж н ы й d-куб - над координатами нескольких вентилей. D - к у б н е и с п р а в н о с т и с х е м ы задается над входными и выходными координатами схемы. Например, для неисправности =0 на выходе элемента 2 ИЛИ примитивный d-куб неисправности вентиля


1 2 │ 3

─────┼──

1 х │ d


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

- если KТ, в которой моделируется неисправность, является внешним входом схемы, то D-куб неисправности составляется относительно одного или нескольких вентилей, которые питает данный вход, в зависимости от того какой путь ( одномерный или много-

мерный ) будет активизироваться. Так, например, для приводимого ниже фрагмента схемы D-куб неисправности х1=1 при попытке ак-


┌─────┐

x1 ────────┤ & o───>

┌────┤ │

│ │ V1 │

x2 ───* └─────┘

│ ┌─────┐

└────┤ 1 │───>

x3 ────────┤ │

│ V2 │

└─────┘


тивизации одномерного пути {x2,V1,...} необходимо составлять относительно одного вентиля - V1:


x1 x2│ V1

────────┼───

1 0 │ d

V1 ?

Если же требуется активизировать многомерный путь { x2 < ...},

V2 ?

то D-куб неисправности должен быть построен относительно вентилей V1 и V2 :


x1 x2 │ V1 x2 x3 │ V2 x1 x2 x3 │ V1 V2

────────┼─── ? ────────┼─── = ───────────┼─────── .

1 0 │ d d 0 0 │ d 1 0 0 │ d d


При моделировании неисправности на непосредственном входе (выходе ) элемента схемы D-куб неисправности составляется относительно вентиля, которому принадлежит рассматриваемый вход, вне зависимости от того, кто питает этот вход ( выход другого

элемента или внешний вход схемы ) и имеются ли ответвления в цепи данной КТ. Например, D-кубы неисправностей V1.вх2=1, V1.вых=0 в приведенном выше фрагменте схемы строятся относительно вентиля V1:


x1 x2│ V1 x1 x2│ V1

V1.вх2=1 : ───────┼─── , V1.вых =0 : ──────┼─── .

1 0 │ d 0 х │ d


D-куб неисправности на внешнем выходе схемы строится относительно вентиля, выход которого является выходом схемы.


D - п е р е с е ч е н и е. Эта операция выражает формализм активизации пути от места возникновения неисправности до выходов схемы. Этим обеспечивается наблюдаемость неисправности. Операция обозначается как d и определяется над d-кубами на основе следующих соотношений:





Рассмотрим пример d-пересечения кубов:


│ 1 2 3 4 5 │

├───────────┤

С1│ х 0 d d d │

С2│ 0 х d d d │

С3│ 0 х d d d │ C2

С4│ 1 0 d d d │

├───────────┤

С5│ 0 0 j j j │ C1 ? C2

│ │ d

С6│ 0 0 m m m │ C1 ? C3

│ │ d

С7│ 1 0 j m m │ C1 ? C4

│ │ d


П р а в и л о d-пересечения кубов.

Куб, являющийся результатом d-пересечения двух d-кубов неопределен, если он содержит символы y, p либо одновременно встречаются символы j и m. Если в кубе имеются символы j, но не m, то вместо пересечения А d ? В необходимо выполнить А d ?В. В случае наличия символов m пересечение производить по соотношениям:







2. Тестирование КЛС по D-алгоритму


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


*******************************************************************

А л г о р и т м D1

( Алгоритм тестирования отдельной неисправности k=h

на базе D-исчисления).

*******************************************************************


1. Относительно выбранного вентиля составляется D-куб Сh0 заданной неисправности .


2. Описываются всевозможные пути L = {li}, порождаемые Кт k.


3. D-проход (D-продвижение, прямая фаза). Из списка L выбирается путь li (одномерный или многомерный и выполняется его активизация путем последовательного D-пересечения куба Сh0 с D-кубами вентилей, лежащих на пути li. При этом на каждом шаге символ d либо d "продвигается" по данному пути на выход очередного вентиля. Эта заканчивается по получении на выходной координате символа d либо d. В результате на некотором n-шаге получаем D-куб неисправности схемы D"(li) с неопределенными выходными координатами вентилей.


4. Доопределение (обратная фаза).

Этап предназначен для установки (доопределения) требуемых выходных значений куба D"(li), которые после d-прохода не обязательно обеспечены соответствующими входными значениями. Доопределение выполняется на основе операции D-пересечения куба D"(li) с соответствующими сингулярными кубами вырожденных покрытий вентилей. Если же какую-либо из координат не удается доопределить, т. е. всевозможные варианты пересечений образуют пустые либо неопределенные кубы, то активизация пути li прекращается, путь вычеркивается из списка L и производится переход на п.3 данного алгоритма. При этом, если список L окажется пустым, то это говорит о том, что ни один из путей, порождаемых КТ k, не активизируется и теста данной неисправности не существует. В этом случае она объявляется несущественной, и алгоритм прекращается. В случае же успешного доопределения получаем D-куб неисправности схемы D(li).


5. Составление теста.

Искомый тест t(k=h) составляется по входным координатам куба D(li).


П р и м е р Синтезировать тест неисправности V2.вых=0 схемы Шнейдера (рис.9.1) по алгоритму D1 .


┌───┐

┌────────────────────────────┤1 │

│ │ о──────┐

│ ┌─────┤V4 │ │

│ │ └───┘ │

│ ┌───┐ │ │

│ ┌──────┤1 │ │ │

│ │ │ о──────┘ │

│ │ ┌────┤V1 │ │

│ │ │ └───┘ ┌───┐ │

x1 ───────┼────x─┼─────────────────────┤1 │ │

│ │ │ о────┐ │

│ │ ┌───────┤V5 │ │ │

│ │ │ └───┘ │ │

│ │ ┌───┐ │ │ │ ┌────┐

x2 ───────x────x─┼────┤1 │ │ │ └────┤ │

│ │ │ о────x └──────┤ 1 │

x3 ─────x──────┼─x────┤V2 │ │ ┌───┐ ┌──────┤ о───> Y

│ │ └───┘ └───────┤1 │ │ ┌────┤V8 │

│ │ │ о────┘ │ └────┘

x4 ─────┼──x───┼───────────────────────┤V6 │ │

│ │ │ └───┘ │

│ │ │ ┌───┐ │

│ │ └──────┤1 │ │

│ │ │ о──────┐ │

│ └──────────┤V3 │ │ │

│ └───┘ │ │

│ │ ┌───┐ │

│ └─────┤1 │ │

│ │ о──────┘

└──────────────────────────────┤V7 │

└───┘


Рис.9.1 Cинтез теста КН V2=0 cхемы Шнейдера по одномерному пути l1


Для большей иллюстративности процесс построения теста будем отражать на схеме ОД ( см. рис.9.2,9.3 ).


1. Составляем D-куб заданной неисправности относительно вентиля V2:


х2 х3 │ V6

Ch1 = ───────┼────

  1. 0 │ d



и показываем его на схеме.


2. КТ с неисправностью порождает два одномерных ( l1 и l2 ) и один многомерный ( l3 ) пути.


3. D-проход по пути l1 = { V2,V5,V8 }.


Относительно вентилей схемы, через которые проходит путь l1, составляем D-кубы С2 и С3 так, чтобы обеспечить распространение символа d (d) на выход Y.


Так как получили символ "d" на выходной координате схемы, то D-проход завершен; в результате него получили d-куб схемы D"(l1) :


x1 x2 x3 x4 │ V1 V2 V3 V4 V5 V6 V7 │V8

D"(l1) = Ch1 ? C2 ? C3 = ─────────────┼───────────────────────┼─── .

d d x x x x │ x d x x d 0 0 │ d


4. Доопределение входных координат схемы .


В процессе d-прохода потребовались определенные координаты выходов вентилей V4, V6 и V7.


Так как выход элемента V4 необходимо установить в нулевое состояние, то составляем нулевое вырожденное покрытие вентиля V4:


x2 V1│ V4 │

─────┼────┼───────────────

П '(V4) = 1 x │ 0 │ ? D"(l1) = Y

│ │ d

x 1 │ 0 │ С5


Первый куб покрытия противоречит кубу Сh1 по координате х2 (образует с ним пустое пересечение). Поэтому выбираем куб С5, который дает не пустое пересечение с кубом Сh1. В свою очередь С5 дополнительно потребовал определенное значение по координате V1, для определения которого составляем единичное вырожденное покрытие вентиля V1,из которого выбираем единственно возможный сингулярный куб С6, который не противоречит другим координатам схемы.

Последняя операция не внесла новых неопределенных выходных координат, поэтому доопределение V1 и V4 обеспечено.


Для допределения V6=0, выбираем из нулевого вырожденного покрытия вентиля V6 сингулярный куб С6, не противоречащий кубу Сh1. По аналогии с V4 доопределяем V7=0, для чего находим кубы С7 и С8. Так как в единичном покрытии вентиля V3 имеется всего один куб и он дает пустое пересечение с кубом C6, то доопределение V3 а значит и V7, противоречат сделанным ранее шагам. В тоже время других вариантов доопределения V4, V6 и V7 не существует. На основании этого заключаем, что активизация пути l1 невозможна.


Аналогична можно показать, что не активизируется и путь


l2 = { V2,V6,V8 } .


Так как не удалось активизировать ни один из одномерных путей, то переходим к активизации многомерного пути


V5

l3 = { V2 < > V8 } .

V6

Процесс активизации l3 отражен на рис.9.3.


D - п р о х о д . Продвигаем символ "d" с выхода вентиля V2 на выход V5, V6 одновременно. Для этого исходный d-куб неисправности Сh1 пересекаем с d-кубами С2 и С3 (см. рис. .2 ). Cимвол d далее продвигаем на выход Y с помощью 2-мерного d-куба С4.


Д о о п р е д е л е н и е .

На этом этапе необходимо доопределить следующие координаты: V4=0 и V8. Для этого находим сингулярные кубы С5 - С8, которые не противоречат другим, определенным ранее, координатам схемы. Так как доопределены все координаты схемы и нет противоречивых (пустых) пересечений, то процесс построения теста можно считать завершенным. Искомый тест содержится в кубе С9, образованном в результате пересечения всех показанных на схеме кубов:





C9 имеет следующую структуру :


x1 x2 x3 x4 │ V1 V2 V3 V4 V5 V6 V7 │V8

C9 = D(l3) = ─────────────┼───────────────────────┼─── .

0 0 0 0 │ 1 d 1 0 d d 0 │ d


По входным координатам куба D(l3) составляем искомый тестовый вектор:


x1 x2 x3 x4




t( V2.вых =0 ) = 0 0 0 0


C4

┌───┐

┌──────────────────────────x─┤1 │

│ │ о──────┐

│ ┌───1─┤V4 │ │

│ C5 │ └───┘ │

│ ┌───┐ │ │

│ ┌────0─┤1 │ │ │

│ │ │ о──────┘ │

│ │ ┌──0─┤V1 │ C2 │

│ │ │ └───┘ ┌───┐ │

x1 ───────┼────x─┼───────────────────0─┤1 │ │

│ │ │ о─d ─┐ │

│ │ ┌─────d─┤V5 │ │ │

│ │ Ch1 │ └───┘ │ │ C3

│ │ ┌───┐ │ │ │ ┌────┐

x2 ───────x────x─┼──0─┤1 │ │ │ └─0──┤ │

│ │ │ о─d──x C6 └──────┤ 1 │

x3 ─────x──────┼─x──0─┤V2 │ │ ┌───┐ ┌───0──┤ о─d─> Y

│ │ └───┘ └─────x─┤1 │ │ ┌─0──┤V8 │

│ │ │ о────┘ │ └────┘

x4 ─────┼──x───┼─────────────────────1─┤V6 │ │

│ │ │ C8 └───┘ │

│ │ │ ┌───┐ │

│ │ └────0─┤1 │ │

│ │ │ о──────┐ │

│ └────────0─┤V3 │ │ │

│ └───┘ │ C7 │

│ │ ┌───┐ │

│ └───1─┤1 │ │

│ │ о──────┘

└────────────────────────────x─┤V7 │

└───┘


Рис. Cинтез теста КН V2=0 cхемы Шнейдера по одномерному пути l1


C5

┌───┐

┌──────────────────────────x─┤1 │

│ │ о──────┐

│ ┌───1─┤V4 │ │

│ C6 │ └───┘ │

│ ┌───┐ │ │

│ ┌────0─┤1 │ │ │

│ │ │ о──────┘ │

t(V2=0)│ │ ┌──0─┤V1 │ C2 │

│ │ │ └───┘ ┌───┐ │

x1 ──0────┼────x─┼───────────────────0─┤1 │ │

│ │ │ о─d ─┐ │

│ │ ┌─────d─┤V5 │ │ │

│ │ C1 │ └───┘ │ │ C4

│ │ ┌───┐ │ │ │ ┌────┐

x2 ──0────x────x─┼──0─┤1 │ │ │ └─0──┤ │

│ │ │ о─d──x C2 └──────┤ 1 │

x3 ──0──x──────┼─x──0─┤V2 │ │ ┌───┐ ┌──────┤ о─d─> Y

│ │ └───┘ └─────d─┤1 │ │ ┌─0──┤V8 │

│ │ │ о─d ─┘ │ └────┘

x4 ──0──┼──x───┼─────────────────────0─┤V6 │ │

│ │ │ C8 └───┘ │

│ │ │ ┌───┐ │

│ │ └────0─┤1 │ │

│ │ │ о──────┐ │

│ └────────0─┤V3 │ │ │

│ └───┘ │ C7 │

│ │ ┌───┐ │

│ └───1─┤1 │ │

│ │ о──────┘

└────────────────────────────x─┤V7 │

└───┘


Рис. Cинтез теста КН V2=0 cхемы Шнейдера по двумерному пути L3


Вопросы для самоконтроля



1. В чем преимущества многомерной активизации путей по сравнению с одномерной ?

2. Дайте общее определение d-куба.

3. Что такое кратность d-куба? Что такое простой d-куб?

4. Как строится d-куб?

5. Дайте физическую интерпретацию d-куба.

6. Что такое примитивный d-куб неисправности вентиля, схемы?

7. Назовите особенности составления d-куба неисправности вентиля для различных точек КЛС .

8. Чем d-куб отличается от примитивного d-куба неисправности вентиля?

9 . Перечислите правила d-пересечения скалярных величин.

10. Сформулируйте правило пересечения d-кубов.Что интерпретируют символы m, y, j, p ?

11. Приведите пример противоречивого и непротиворечивого d-пересечений кубов.

12. Перечислите этапы алгоритма D1.

13. Поясните термины: прямая (обратная) фаза, d-проход, d-продвижение, доопределение входов.

Схожі:

Машинно-ориентированный синтез тестов iconСборник тестов по инженерной графике
Сборник тестов по инженерной графике. Сборник тестовых заданий для самостоятельного контроля знаний студентов 1 курса бакалавров...
Машинно-ориентированный синтез тестов iconМіністерство освіти І науки, молоді та спорту україни херсонський державний університет затверджую
Програма розроблена на основі Программы педагогических институтов. Сборник 18. Органический синтез. Неорганический синтез. Биологическая...
Машинно-ориентированный синтез тестов iconМіністерство освіти І науки, молоді та спорту україни херсонський державний університет затверджую
Програма розроблена на основі Программы педагогических институтов. Сборник 18. Органический синтез. Неорганический синтез. Биологическая...
Машинно-ориентированный синтез тестов iconМіністерство освіти І науки, молоді та спорту україни херсонський державний університет затверджую
Програма розроблена на основі Программы педагогических институтов. Сборник 18. Органический синтез. Неорганический синтез. Биологическая...
Машинно-ориентированный синтез тестов iconТемченко С. А. Сумский государственный университет
Объектно-ориентированный подход к синтезу системы управления винтовым компрессором
Машинно-ориентированный синтез тестов iconСинтез та дослідження біологічної активності деяких синтетичних та природних сполук. Ключові слова
Ключові слова: синтез нітрогеновмісних гетероциклічних сполук, флуоровмісні замісники, біологічна активність, рістрегулююча активність,...
Машинно-ориентированный синтез тестов iconФілософія удк 130. 123. 1(130)Геґель геґель та проблема розуміння діалектики як синтезу теоретичного І практичного василь Лисий
Тільки в системі Геґеля вперше проаналізовано логічну діалектику як єдність (синтез) теоретичного й практичного. Такий синтез виявляється...
Машинно-ориентированный синтез тестов iconФілософія удк 130. 123. 1(130)Геґель геґель та проблема розуміння діалектики як синтезу теоретичного І практичного василь Лисий
Тільки в системі Геґеля вперше проаналізовано логічну діалектику як єдність (синтез) теоретичного й практичного. Такий синтез виявляється...
Машинно-ориентированный синтез тестов iconДокументи
1. /Кляйн/Кляйн Мелани Зависть и благодарность.pdf
2. /Кляйн/МЕЛАНИ...

Машинно-ориентированный синтез тестов iconДокументи
1. /Кляйн/Кляйн Мелани Зависть и благодарность.pdf
2. /Кляйн/МЕЛАНИ...

Додайте кнопку на своєму сайті:
Документи


База даних захищена авторським правом ©zavantag.com 2000-2013
При копіюванні матеріалу обов'язкове зазначення активного посилання відкритою для індексації.
звернутися до адміністрації
Документи