Комбинационных схем icon

Комбинационных схем




Скачати 209.98 Kb.
НазваКомбинационных схем
Дата01.07.2012
Розмір209.98 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аблюдаемость и активизация путей схемы Наблюдаемость кт теснейшим образом связана с понятием схемного пути. Схемный путь
Синтез тестов кн комбинационных схем по методу булевой производной
Машинно-ориентированный синтез тестов

Л е к ц и я 10


ПОДХОДЫ ПОСТРОЕНИЯ ПРОИЗВОДСТВЕННЫХ ТЕСТОВ

КОМБИНАЦИОННЫХ СХЕМ


Как правило, перед разработчиком диагностического обеспечения (ДО) возникает задача синтеза тестов ВУ в целом, а не отдельной его неисправности. Рассмотрим основные подходы, которые предложены теоретиками для решения подобного рода задач.

Сложившиеся к настоящему времени методы и алгоритмы структурного синтеза тестов КЛС условно можно представить тремя основными подходами. Это :


  • классический подход ;

  • "одномерная активизация" ;

  • "синтез + моделирование" ;



Классический подход синтеза теста ВУ



К л а с с и ч е с к и й п о д х о д тестирования базируется на синтезе тестовых наборов для каждой неисправности из множества всевозможных КН схемы по уравнению тестируемости вида. Подход включает следующие этапы.


1. Составление полного Нп (минимального Нmin) списка КН схемы.

2. Синтез тестовых наборов неисправностей.


Для каждой неисправности hk из списка Нп (Hmin) составляется уравнение тестируемости и находится входной (тестовый ) набор t(hk) как одним из его корней ( с максимальным числом неопределенностей ).


3. Построение предвартельного теста - Т1 .

Т1 строится путем объединения тестовых наборов, полученных на этапе 2:


Т1 = | { t(hk) } | .


5. Построение результирующего ( производственного Тпр) теста. Тпр получается в результате процедур минимизации и доопределения векторов теста Т1. Минимизация выполняется на основе операции попарного "пересечения" векторов. Результатом пересечения двух векторов является вектор, каждый элемент которого получается по следующему правилу :


х ? x = x ,

a ? x = x ? a = a ,

а ? a = a ,

_ _

а ? a = a ? a = y ,


где а принадлежит множеству { 0,1 } ;

y - символ пустого пересечения .

Вектор, полученный в результате пересечения и содержащий хотя бы один пустой элемент называется пустым. В ходе минимизации операция пересечения выполняется над всевозможными парами Т1. При этом вектора А и В заменяются вектором С = А ? В, если он не является пустым . В противном случае А и В остаются неизменными.

Полученные после процедуры минимизации вектора теста Т1 могут содержать неопределенности. Все они могут быть доопределены до произвольного двоичного значения. После процедуры доопределения получается искомый производственный тест.


В качества примера синтезируем тест всевозможных КН схемы переноса (СхП) одного разряда сумматора с черезразрядной инверсией:


1 4 ┌────┐

e ──x─*───────x─┤ & │ 10

2 │ 5 │ ├──x───┐

a ──x─┼───*───x─┤ │ │

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

│ │ 6 ┌────┐ └──x──┤ 1 │

│ └───x─┤ & │ 11 14 │ │ 16

│ 7 │ ├──x──────x──┤ ├──x── E

│ ┌───x─┤ │ 15 │ │

│ │ └────┘ ┌──x──┤ │

3 │ │ 8 ┌────┐ │ └─────┘

b ──x─┼───*───x─┤ & │ 12 │

│ 9 │ ├──x───┘

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

└────┘

В рассматриваемой схеме КН моделируются в 16 отмеченных КТ.

В каждой из этих точек может моделироваться =0 и =1, поэтому список всевозможных КН СхП состоит из 32-х неисправностей:


|Hп|= 16·2 = 32.


После выполнения алгоритма "Hmin" в списoк Hmin будет содержать 6 КН, отмеченные на схеме:


4=1┌────┐

e ──x─*───────x─┤ & │10=0

│ 5=1│ ├──x───┐

a ──x─┼───*───x─┤ V1 │ │

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

│ │ 6=1┌────┐ └──x──┤ 1 │

│ └───x─┤ & │11=0 │ │

│ │ ├──x──────x──┤ о──x── E

│ ┌───x─┤ V2 │ │ │

│ │ └────┘ ┌──x──┤ V4 │

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

b ──x─┼───*───x─┤ & │12=0 │

│ │ ├──x───┘

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

└────┘ Hmin = { 4=1 5=1 6=1 10=0 11=0 12=0 }


Оценим эффективность алгоритма "Hmin" на выполненном примере. Эффективность алгоритма можно вычислить по формуле:


,

где | Hп | = 32 - число всевозможных КН СхП;

|Hmin| = 6 - число КН в списке Hmin.


Переходим к п.2 классического подхода.

Из списка Hmin выбираем первую по порядку неисправность 4=1 и для нее составляем функции управляемости

_

U(4=1) = е ,


наблюдаемости





и уравнение тестируемости

_ _

U(4=1) & Н(4) = e & ab =1.


В качестве теста неисправности принимаем единственный корень уравнения тестируемости в формате { e a b }


t(4=1) = { 0 1 0 }.


Аналогично поступаем с неисправностями 5=1 и 6=1:

_ _

U(5=1) & Н(5) = a & eb, t(5=1) = {1 0 0 };

_ _

U(6=1) & Н(6) = a & eb, t(6=1) = {0 0 1 };


Находим тест неисправности 10=0, 11=0, 12=0:

_ _ _ _ _ _ _

U(10=0) & Н(10) = ea & = ea & y2 y3 = ea & (a + b)(e + b) = eab = 1,


t(10=0) = {1 1 0} ;


_ _ _ _ _ _ _

U(11=0) & Н(11) = ab & = ab & y1 y3 = ab & (e + a)(e + b) = eab = 1,


t(11=0) = {0 1 1} ;


_ _ _ _ _ _ _

U(12=0) & Н(12) = eb & = eb & y1 y2 = eb & (e + a)(a + b) = eab = 1,


t(12=0) = {1 0 1} .


Так как протестированы все неисправности, то переходим к построению предварительного теста:


│ e a b│

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

│ 0 1 0│ t(4=1)

│ 1 0 0│ t(5=1)

Т1 = │ 0 0 1│ t(6=1)

│ 1 1 0│ t(10=1)

│ 0 1 1│ t(11=1)

│ 1 0 1│ t(12=1)


Попарное пересечение векторов Т1 дает только пустые пересечения. Доопределение выполнять не нужно, так как в Т1 не неопределенностей. Поэтому производственный тест совпадает с предварительным : Тпр = Т1.

Недостатком классического подхода является его высокая трудоемкость, обусловленная необходимостью применения громоздких процедур для каждой тестируемой неисправности схемы. Трудоемкость подхода в зависимости от выбранного исходного списка КН может быть оценена по одной из формул


Qкл = Kут |Нп| либо Qкл = Kут |Нmin| ,


где Ккл - коэффициент пропорциональности, отражающий сложность синтеза и решения одного уравнения тестируемости КН.

Для рассмотренного выше примера имеем Qкл = 32Kут на базе Нп и Qкл = 6Kут на базе Нп. Эффективность алгоритма "Hmin" в данном случае составляет :





Замечаем также, что применение алгоритма "Hmin" в рассматриваемом примере позволило избежать процедуры минимизации тестовых векторов.

Подход одномерной активизации



Определение Переключающей парой ( ПП ) пути l(xi) КЛС, порожденного внешним входом хi схемы, называются два вектора t(хi) / t(хi), полученные по следующему правилу :

t(хi) = А(хi) ? хi ,

_ _

t(хi) = А(хi) ? хi ,


где А(хi) - вектор активности пути l(xi) .


Справедливо

Утверждение Переключающая пара одномерного пути, покрывает все КН этого пути.


( Доказать самостоятельно ).


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


1. Cоставляется список всевозможных ОП схемы Lп={lj(хi)}.

2. Из списка Lп выделяется минимальный список ОП Lmin, покрывающих все схемные ветви ОД:

Lп ? Lmin , Lп = Lп \ Lmin .


3. Активизация ОП.

Для каждого ОП lj(хi) из списка Lmin находится вектор активности Xaj(хi). Неопределенные координаты в векторе Хаj(xi), кроме координаты хi, заменяются символическими константами. На основе вектора активности составляются ПП tj(хi) / tj(хi) :


tj(хi) = Xaj(хi) ? (*,...,*,хi=1,*,...,*) ,

_

tj(хi) = Xaj(хi) ? (*,...,*,хi=0,*,...,*) ,


где "?" - операция пересечения векторов, выполняемая по правилам:


0 ? 0 = 0

1 ? 1 = 1

0 ? 1 = 0 ? 1 = y - пустое пересечение

0 ? s = 0, s = 0

1 ? s = 0, s = 1

s1 ? s2 = s1, s2 = s1 ,


где s, s1, s2 - символические константы .


Помечаются все ветви ОД активизированного пути.

Если успешно актвизированы все ОП, то переход на этап 4, иначе - на п.5.

4. На основе ПП, построенных в п. 3 составляется искомый производственный тест, который в данном случае совпадает с предварительным:

_

Тпр = Т1 = | { tj(хi) / tj(хi)} | .


Переход на п.10.

5. Из списка Lп, если он не пуст, составляется новый список Lmin, покрывающий непомеченные на этапе 3 ветви ОД, Lп = Lп \ Lmin и осуществляется переход на п.3. Если Lп = 0, то переход на п.6.

6. Построение списка необнаруживаемых неисправностей. Относительно КТ непомеченных ветвей составляется список Н1 КН, из которого далее выделяется список Н1min, построенный с учетом эквивалентности и доминирования неисправностей списка Н1 по правилам Э1 - Э12 и Д1 - Д8.

7. Тестирование необнаруживаемых неисправностей. Для каждой неисправности hk из списка Н1 составляется уравнение тестируемости, путем решения которого находится тест t(hk) .

8. Построение предварительного теста - Т1 .

Т1 строится путем объединения ПП и тестовых наборов, полученных на этапах 2 и 3 соответственно :


_

Т1 = {tj(хi) / tj(хi)}

{t(hк)} .


9. Построение производственного теста - Тпр .

Тпр получается в результате процедур минимизации и доопределения векторов теста Т1.

10. Конец.


П р и м е р . Синтезировать производственный тест по подходу "одномерная активизация" следующей КЛС


┌────┐

x1 >────┤ & │

x2 >────┤ │ y1 ┌─────┐

x3 >────┤ ├───────┐ │ │

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

└────┘ │ ├──────> Y

┌────┐ │ │

z1 >────┤ 1 │ ┌──────┤ │

z2 >────┤ o───────┘ │ │

z3 >────┤ │ y2 └─────┘

z4 >────┤ │

└────┘


Так как в схеме нет разветвлений, то Lmin = Lп.

Вектор активизации пути l(x1) = { x1, y1, Y }, полученный путем решения уравнения




имеет следующий вид:


x1 x2 x3 x4 z1 z2 z3 z4




Xa(x1) = { * 1 1 1 1 * * * } .


В векторе Ха(х1) неопределенные координаты, кроме координаты х1, заменяем символическими константами а1, а2, а3:


x1 x2 x3 x4 z1 z2 z3 z4



Xa(x1) = { * 1 1 1 1 а1 а2 а3 } .


Переключающая пара пути l(x1) примет следующий вид :


x1 x2 x3 x4 z1 z2 z3 z4



t(x1) = { 1 1 1 1 1 а1 а2 а3 } ,

t`(x1)= { 0 1 1 1 1 а1 а2 а3 } .


Аналогично активизируем остальные ОП схемы. Полученные в ходе активизации ПП сносим в предварительный тест Т1:


x1 x2 x3 x4 z1 z2 z3 z4

─────────────────────────

│ 1 1 1 1 1 а1 а2 а3 │ t(x1) _

│ 0 1 1 1 1 а1 а2 а3 │ t(x1)

│ │

│ 1 1 1 1 1 b1 b2 b3 │ t(x2) _

│ 1 0 1 1 1 b1 b2 b3 │ t(x2)

│ │

│ 1 1 1 1 1 c1 c2 c3 │ t(x3) _

│ 1 1 0 1 1 c1 c2 c3 │ t(x3)

│ │

│ 1 1 1 1 1 d1 d2 d3 │ t(x4) _

│ 1 1 1 0 1 d1 d2 d3 │ t(x4)

T1` = │ │

│ 0 e1 e2 e3 1 0 0 0 │ t(z1) _

│ 0 e1 e2 e3 0 0 0 0 │ t(z1)

│ │

│ 0 f1 f2 f3 0 1 0 0 │ t(z2) _

│ 0 f1 f2 f3 0 0 0 0 │ t(z2)

│ │

│ 0 g1 g2 g3 0 0 1 0 │ t(z3) _

│ 0 g1 g2 g3 0 0 0 0 │ t(z3)

│ │

│ 0 h1 h2 h3 0 0 0 1 │ t(z4) _

│ 0 h1 h2 h3 0 0 0 0 │ t(z4)


Выполняем минимизацию Т1` :


x1 x2 x3 x4 z1 z2 z3 z4

─────────────────────────

│ 1 1 1 1 1 а1 а2 а3 │ t(x1) _

│ 0 1 1 1 1 а1 а2 а3 │ t(x1)

│ │

- │ 1 1 1 1 1 b1 b2 b3 │ t(x2) _ bi=ai, i=1,2,3

│ 1 0 1 1 1 b1 b2 b3 │ t(x2)

│ │

- │ 1 1 1 1 1 c1 c2 c3 │ t(x3) _ ci= ai

│ 1 1 0 1 1 c1 c2 c3 │ t(x3)

│ │

- │ 1 1 1 1 1 d1 d2 d3 │ t(x4) _ di=ai

│ 1 1 1 0 1 d1 d2 d3 │ t(x4)

T1` = │ │

│ 0 e1 e2 e3 1 0 0 0 │ t(z1) _ ei=1, ai=0

- │ 0 e1 e2 e3 0 0 0 0 │ t(z1)

│ │

│ 0 f1 f2 f3 0 1 0 0 │ t(z2) _ fi=1

- │ 0 f1 f2 f3 0 0 0 0 │ t(z2)

│ │

│ 0 g1 g2 g3 0 0 1 0 │ t(z3) _ gi=1

- │ 0 g1 g2 g3 0 0 0 0 │ t(z3)

│ │

│ 0 h1 h2 h3 0 0 0 1 │ t(z4) _ hi=1

- │ 0 h1 h2 h3 0 0 0 0 │ t(z4)


В результате минимизации получаем предварительный тест


x1 x2 x3 x4 z1 z2 z3 z4

─────────────────────────

│ 1 1 1 1 1 0 0 0 │

│ 0 1 1 1 1 0 0 0 │

│ 1 0 1 1 1 0 0 0 │

│ 1 1 0 1 1 0 0 0 │

│ 1 1 1 0 1 0 0 0 │

T1 = │ │

│ 0 1 1 1 0 0 0 0 │

│ 0 1 1 1 0 1 0 0 │

│ 0 1 1 1 0 0 1 0 │

│ 0 1 1 1 0 0 0 1 │


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


Тпр = T1 .


П р и м е р . Синтезировать производственный тест по подходу "одномерная активизация" схемы Шнейдера


┌────┐

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

│ =1 ┌────┐ ┌────┤ o───────┐

┌──┼──1────┤ 1 o────┘ └────┘ │

│ │ ┌─x1 ┤ │ y1 │

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

x1 >──┼──┼──*───────────────x1"─┤ 1 │ y5 │ ┌────┐

│ │ =1 ┌────┐=0=1┌─6──┤ o────┐ └────┤ 1 │

x2 >──┼──*──2────┤ 1 o─5──* =1 └────┘ └───────┤ o───> Y

x3 >──*──┼──3────┤ │ y2 │ =1 ┌────┐ ┌───────┤ │

│ │ =1 └────┘ └─7──┤ 1 o────┘ ┌────┤ │

x4 >──┼──┼──*───────────────────┤ │ y6 │ └────┘

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

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

│ └──4────┤ o────┐ ┌────┐ │

│ =1 └────┘ └────┤ 1 o───────┘

└─────────────────────────┤ │ y7

└────┘


В схеме Шнейдера 12 ОП, т.е. |Lп| = 12.

КТ х1 образует 2 ОП, которые должны быть включены в список Lmin:


l1(x1) = {x1, y1, y4, Y }, l2(x1) = {x1, y5, Y }.


Выполним активизацию l1(x1). Вначале получим функцию активизации пути:





Далее на основе функцию активизации составляем вектор активности пути


x1 x2 x3 x4




Xa1(x1) = { * 0 0 0 } .


По вектору активности составляем ПП :


t1(х1) = Xa1(х1) ? (*,...,*,х1=1,*,...,*) = { 1 0 0 0 } ,


t'1(х1) = Xa1(х1) ? (*,...,*,х1=0,*,...,*) = { 0 0 0 0 } .


Aктивизируем ОП l2(x1):

A1(x1) = x2 x3 x4 ,

Xa2(x1) = { * 1 1 1 } ,

t2(х1) = { 1 1 1 1 } ,

t'2(х1) = { 0 1 1 1 } .


Далее выполняем активизацию ОП по входным переменным х2, х3, х4. Среди всевозможных ОП, порождаемых входом х2 b и х3 активизируется только по одному пути l1(x2) = {x2, y4, Y} и l4(x3) = {x3, y7, Y }. По входу х4 активизируются все ОП l1(x4) = { x4, y3, y7, Y } и l2(x4) = {x4, y6, Y }. Полученные в ходе активизации ПП сносим в тестовый набор Т1`


x1 x2 x3 x4

------------

│ 1 0 0 0 │ t1(х1) _

│ 0 0 0 0 │ t1(х1)

│ │

│ 1 1 1 1 │ t2(х1) _

│ 0 1 1 1 │ t2(х1)

│ │

│ 1 1 1 1 │ t1(х2) _

Т1`= │ 1 0 1 1 │ t1(х2)

│ │

│ 1 1 1 1 │ t4(х3) _

│ 1 1 0 1 │ t4(х3)

│ │

│ 0 0 0 1 │ t1(х4) _

│ 0 0 0 0 │ t1(х4)

│ │

│ 1 1 1 1 │ t2(х4) _

│ 1 1 1 0 │ t2(х4)


После минимизации векторов Т1` получаем


x1 x2 x3 x4

------------

│ 1 0 0 0 │

│ 0 0 0 0 │

│ 1 1 1 1 │

Т1 = │ 0 1 1 1 │ .

│ 1 0 1 1 │

│ 1 0 1 1 │

│ 0 0 0 1 │

│ 1 1 1 0 │


Так в тестируемой схеме активизируются не все ОП, то имеются КН, которые возможно не обнаруживаются тестом Т1. Для поиска таких неисправностей пометим порядковыми номерами ветви схемы, через которые не пролегает ни один из активизированных ОП. В число кандидатов может быть включены неисправности =0 и =1 в каждой из помеченных

КТ. Поэтому полный список КН, возможно необнаруживаемых тестом Т1 примет следующий вид


Н1 = { 1=0 1=1 2=0 2=1 3=0 3=1 4=0 4=1 5=0 5=1 6=0 6=1 7=0 7=1 } .


Проанализировав эквивалентность по правилам Э1 - Э12 и доминирование по правилам Д1 - Д8 неисправностей из списка Н1 находим, что:


x3=0 ~ 1=0 ~ 3=0 ,

x2=0 ~ 2=0 ~ 4=0 ,

y1=0 ~ 1=1 ,

y5=0 ~ 6=1 ,

y6=0 ~ 7=1 ,


Так как через КТ х2, х3, y1, y5,y6 пролегают активизированные пути, то Т1 содержит в себе тесты неисправностей х2=0, х3=0, y1=0, y5=0, y6=0 а значит КН, которым эквивалентны данные неисправности. Поэтому из Н1 можно удалить 1=0, 3=0, 2=0, 4=0, 1=1, 6=1, 7=1. Кроме того


5=0 ~ 6=0 ~ 7=0 ,

2=1 ~ 3=1 ~ 5=0 ,


поэтому из Н1 можно удалить 6=0, 7=0, 3=1 и 2=1.

После проведенных удалений в списке Н1 осталась единственная неисправность - 5=0 :


Нmin = { 5=0 } .


Далее составляем уравнение тестируемости и на его основе синтезируем тест для неисправности 5=0:


Т(5=0) = U(5=0) & H(5) ;


U(5=0) = x2 v x3 ;




_ _ _ _ _ _

= y4 & y7 x1 & x4 = ( x2 v y1 ) & ( x3 v y3 ) & x1 & x4 =

_ _ _ _ _ _

= ( x2 v x1 x3 ) & ( x3 v x4 x2 ) & x1 x4 =

_ _ _ _ _ _ _ _ _ _ _ _

= ( x2 x3 v x1 x2 x3 x4 ) & x1 x4 = x2 x3 x1 x4 v x1 x2 x3 x4 ,


t(5=0) = { 0 0 0 0 } .


На основе Т1 и тестового вектора t(5=0) составляем


x1 x2 x3 x4

------------

│ 1 0 0 0 │

│ 0 0 0 0 │

│ 1 1 1 1 │

│ 0 1 1 1 │

│ 1 0 1 1 │

Tпр` = │ 1 0 1 1 │ .

│ 0 0 0 1 │

│ 1 1 1 0 │

│ ---------- │

│ 0 0 0 0 │


После минимизации Тпр` получаем Тпр = Т1 .


Проведем сравнительный анализ метода "одномерной активизации" с классическим методом. Для этого вначале построим список Нmin для тестируемой схемы в целом. Неисправности из списка Hmin нанесем на схему так, как показано на следующем рисунке


┌────┐

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

│ ┌────┐ ┌───┤ o─y4────┐

┌──┼─────┤ 1 o─y1─┘ └────┘ │

│ │ ┌──┤ │ │

=0 │ │ │ └────┘ ┌────┐ │

x1 >─────┼──┼──*────────────────┤ 1 │ =0 │ ┌────┐

=0 │ │ ┌────┐ =0 ┌───┤ o─y5─┐ └───┤ 1 │ =0

x2 >─────┼──*─────┤ 1 o─y2─* └────┘ └──────┤ o───> Y

x3 >─────*──┼─────┤ │ │ ┌────┐ ┌──────┤ │

=0 │ │ └────┘ └───┤ 1 o─y6─┘ ┌───┤ │

x4 >─────┼──┼──*────────────────┤ │ =0 │ └────┘

=0 │ │ │ ┌────┐ └────┘ │

│ │ └──┤ 1 │ │

│ └─────┤ o─y3─┐ ┌────┐ │

│ └────┘ └───┤ 1 o─y7────┘

└──────────────────────┤ │ =0





Как видно из рисунка построенный список Нmin включает 10 неисправностей, т. е. |Hmin| = 10 . Эффект от использования алгоритма "Hmin" составляет 60 / 10 = 6. Классический подход предполагает синтез и решение уравнения тестируемости (УТ) для каждой неисправности из списка Нп (Hmin). Поэтому трудоемкость синтеза производственного теста по классическому подходу для схемы Шнейдера пропорциональна 10 :


Qкл ~ Kут │Hп│ = 60 Кут,

либо

Qкл ~ Kут │Hmin│ = 10 Кут,


где Ккл - коэффициент пропорциональности, отражающий сложность синтеза и решения одного УТ.

С другой стороны в ходе реализации подхода одномерной активизации было синтезировано и разрешено 12 уравнений активизации ОП и 1 УТ. Поэтому трудоемкость в этом случае можно оценить по следующей формуле


Qоа ~ 12Kуа + 1 Кут ,


где Коа - коэффициент пропорциональности, отражающий сложность синтеза и решения одного уравнения активизации схемного пути.


Синтез и решение уравнения тестируемости КН и уравнения активности схемного пути по сложности сопоставимы, т. е. коэффициенты Кут и Коа можно считать приблизительно равными: Кут = Коа = К. Поэтому эффект от снижения трудоемкости подхода одномерной активизации по сравнению с классическим подходом для схемы Шнейдера можно оценить по следующей формуле





Либо




Рассмотренный пример подтвердил среднестатистическую закономерность: подход одномерной активизации cущественно снижает трудоемкость синтеза производственного теста по сравнению с классическим подходом на базе полного списка КЛС. Это объясняется тем, что в среднестатистической схеме активизируется большая часть ОП.

Снижение трудоемкости - основное достоинство одномерной активизации. Другим достоинством является то, что упрощается обработка списков неисправностей. Однако применение алгоритма "Нmin" практически сводит "на нет" эффект одномерной активизации. Подход одномерной активизации имеет также следующие недостатки:


1. Большинство неисправностей, содержащихся в списке Н1, покрываются тестом Т1, поэтому синтез тестов для этих неисправностей сопряжен с непроизводительными затратами. Имеется ввиду то, что ПП tj(хi) / t'j(хi) помимо неисправностей, лежащих на ОП lj(хi), часто обнаруживает и другие неисправности, благодаря чему множество необнаруженных неисправностей H1 могло бы быть значительно меньше. Формальное определение таких неисправностей пока не предложено, однако может быть выполнено на основе машинного моделирования неисправных состояний ОД.


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

необходимости моделирования схемы на векторах наблюдаемости входов с тем, чтобы определить какой из этих векторов является вектором активности ОП, порождаемого данным входом.


3) по сравнению с классическим подходом возрастает длина производственного теста.


Устранению указанных недостатков посвящен следующий подход.

Подход "синтез + моделирование"



Вначале предлагаемого подхода ("синтез + моделирование") строится предварительный тест Т1, далее моделируются всевозможные КН схемы и определяется таким образом точное множество неисправностей, необнаруживаемых тестом Т1. Для каждой такой неисправности на последующих этапах строятся тестовые векторы {t(hк)}, которые в совокупности с Т1 образуют искомый производственный тест.


Основные этапы подхода "синтез + моделирование" .


1. Построение предварительного теста Т1.

2. Моделирование неисправностей .

Путем моделирования всевозможных КН схемы на тесте Т1 определяется список H1 неисправностей, не покрываемых тестом Т1.

3. Построение эквивалентного списка неисправностей.

На основе правил эквивалентности и доминирования из списка H1 удаляются эквивалентные и подчиненные КН. Оставшиеся после удаления неисправности образуют список Н1min.

4. Тестирование необнаруживаемых неисправностей.

Для каждой неисправности hk из списка H1min составляется уравнение тестируемости, путем решения которого находится тест t(hk) .

5. Построение производственного теста.

Тпр составляется путем дополнения Т1 тестовыми наборами {t(hk)}, предварительно проминимизированными и доопределенными:




Т1

Тпр = {t(hk)}


Предварительный тест описанного подхода может быть синтезирован одним из следующих способов.


1. Активизация всевозможных ОП:

_

Т1 = │ {tj(хi) / tj(хi)} │


Построение Т1 в этом случае выполняется по аналогии с подходом одномерной активизации.


2. Активизация произвольного пути.

Для каждого входа хi находится вектор активности одного произвольного ( одномерного или многомерного ) пути l(xi) и на его основе строится ПП t(хi) / t(хi). ПП минимизируются, доопределяются и включаются в тест Т1 :

_

Т1 = │ {t(хi) / t(хi)} │


Так как для построения Т1 может быть активизирован любой схемный путь порождаемый внешним входом ОД, то функция активности любого такого пути является частью функции наблюдаемости входа схемы.

Действительно, как было показано ранее, функция наблюдаемости входа хi связана с функциями активизации путей l1(xi), l2(xi),...,ln(xi) (как одномерных, так и многомерных), порождаемых этим входом, следующей зависимостью:


H(xi) = A(l1(xi)) V A(l2(xi)) V ... V A(ln(xi)).


Отсюда следует, что вектор наблюдаемости входа xi совпадает с вектором активности одного из путей l(xi). Поэтому активизацию произвольного пути, порождаемого входом xi можно выполнить на основе вектора наблюдаемости данного входа.


3. Тестирование входных неисправностей.

Тестовые наборы синтезируются для КН входов схемы : хi=0, хi=1 по аналогии с классическим подходом, т.е. путем составления и разрешения уравнения тестируемости:


t(хi=0)

Т1 =

t(хi=1)


П р и м е р . Синтезировать производственный тест по подходу "одномерная активизация" схемы Шнейдера. Т1 построить на основе активизации ОП.


Так как Т1 синтезирован в предыдущем примере, то процесс его построения здесь показывать не будем. Моделирование всевозможных КН схемы Шнейдера на тесте Т1 показывает, что он покрывает (обнаруживает ) все неисправности. Поэтому множество Н1 является пустым, необходимость в выполнении п.3 подхода отпадает и


Тпр = Т1.


Оценим по приведенному примеру эффективность по трудоемкости подхода "синтез + моделирование" по сравнению с другими подходами:


а) по сравнению с классическим подходом на базе Нп:


;

б) по сравнению с классическим подходом на базе Нmin


;


в) по сравнению с подходом одномерной активизации на базе Н1:


;


г) по сравнению с подходом одномерной активизации на базе Н1min:


;


где "12 К" - трудоемкость подхода "синтез + моделирование" .


П р и м е р . Синтезировать производственный тест схемы Шнейдера по подходу "синтез + моделирование" . Т1 построить на основе активизации произвольного схемного пути.


Для каждого входа схемы Шнейдера по одному вектору активизации произвольного пути на основе вектора наблюдаемости входа.

Для входа x1 вычисляем функцию наблюдаемости входа





В качестве вектора активизации произвольного пути выбираем вектор наблюдаемости как одно из возможных решений уравнения наблюдаемости


Xa(l(x1)) = Xн(х1) = { * 0 0 0 }


По вектору Xa(l(x1)) построим ПП :

_

t(х1) = { 1 0 0 0 }, t(х1) = { 0 0 0 0 }


Аналогично активизируем по одному произвольному пути по входам х2, х3, х4. Полученные ПП сносим в тест Т1` :


x1 x2 x3 x4

------------

│ 1 0 0 0 │ t(х1) _

│ 0 0 0 0 │ t(х1)

│ │

│ 1 1 1 1 │ t(х2) _

Т1`= │ 1 0 1 1 │ t(х2)

│ │

│ 1 1 1 1 │ t(х3) _

│ 1 1 0 1 │ t(х3)

│ │

│ 0 0 0 1 │ t(х4) _

│ 0 0 0 0 │ t(х4)


После минимизации Т1` получаем


x1 x2 x3 x4

------------

│ 1 0 0 0 │

│ 0 0 0 0 │

│ 1 1 1 1 │

Т1 = │ 1 0 1 1 │ .

│ 1 1 0 1 │

│ 0 0 0 1 │


Моделирование всевозможных КН схемы Шнейдера показывает, что Т1 не обнаруживает КН, показанные на рисунке


┌────┐

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

│ ┌────┐ ┌────┤ o───────┐

┌──┼───────┤ 1 o────┘ └────┘ │

│ │ ┌────┤ │ y1 │

│ │ │ └────┘ =1 ┌────┐ │

x1 >──┼──┼──*──────х1 ────────5─┤ 1 │ =0 │ ┌────┐

│ │ ┌────┐=1 ┌──6─┤ o──9─┐ └────┤ 1 │

x2 >──┼──*──2────┤ 1 o─4──* =1 └────┘ y5 └───────┤ o───> Y

x3 >──*──┼──3────┤ │ y2 │ =1 ┌────┐ ┌───────┤ │

│ │ └────┘ └──7─┤ 1 o─10─┘ ┌────┤ │

x4 >──┼──┼──*─────────────────8─┤ │ =0 │ └────┘

│ │ │ ┌────┐ =1 └────┘ │

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

│ └───────┤ o────┐ ┌────┐ │

│ └────┘ └────┤ 1 o───────┘

└─────────────────────────┤ │ y7

└────┘


Н1, таким образом, включает следующие КН:


Н1 = { 4=1 5=1 6=1 7=1 8=1 9=0 10=0 }, |Н1| = 7 .


Учитывая эквивалентность и доминирование КН находим, что


5=1 ~ 6=1 ~ 9=0 ,

7=1 ~ 8=1 ~ 10=0 ,

5=1 ? 4=1 .


Исходя из этого строим Н1min = { 9=0 10=0 }.


Далее для каждой неисправности из H1min синтезируем тест. Для 9=0 cоставляем функцию тестируемости:





Поэтому t(9=0) = { 1 0 0 0 } . Аналогично синтезируем тест неисправности 10=0. Построенные тесты совместно с Т1 включаем в


x1 x2 x3 x4

------------

│ Т1 │

│ │

│ 0 1 1 1 │ t(9=0)

Тпр` = │ │

│ 1 1 1 0 │ t(10=0)


Mинимизация тестов отдельных неисправностей не приводит к сокращению тестовых наборов. Поэтому


x1 x2 x3 x4 x1 x2 x3 x4

------------ ------------

│ Т1 │ │ 1 0 0 0 │

│ │ │ 0 0 0 0 │

Тпр = Т'пр =│ 0 1 1 1 │ = │ 1 1 1 1 │

│ 1 1 1 0 │ │ 1 0 1 1 │

│ 1 1 0 1 │

│ 0 0 0 1 │

│ 0 1 1 1 │

│ 1 1 1 0 │


Сравнительный анализ подхода "синтез + моделирование" дает следующие результаты:

а) по сравнению с классическим подходом на базе Нп:


;


б) по сравнению с классическим подходом на базе Нmin:


;


в) по сравнению с подходом одномерной активизации на базе Н1:


;


г) по сравнению с подходом одномерной активизации на базе Н1min:


;


где "4" - число уравнений наблюдаемости, составляемых и разрешаемых при активизации произвольных путей;

"7" - число неисправностей списка Н1.

"2" - число неисправностей списка Н1min.


Проанализируем достоинства и недостатки подхода "синтез + моделирование".


Основным достоинством данного подхода является наиболее низкая трудоемкость синтеза теста по сравнению со всеми другими рассмотренными выше походами. Для среднестатистической схемы удается снизить трудоемкость в 2.0 - 2.5 раза по сравнению с классическим подходом и в 1.4 - 1.8 раза по сравнению с подходом одномерной активизации. Наибольший эффект достигается при использовании данного подхода в сочетании с учетом эквивалентности и доминирования КН. Однако такой эффект возможен при наличии системы моделирования КН, так как моделирование неисправностей вручную практически нереализуемо. Другим достоинством подхода является то, активизация схемных путей может


выполняться посредством вычисления наблюдаемости внешних входов схемы.

Недостатком подхода "синтез + моделирование" является необходимость в наличии системы моделирования неисправностей.

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



1. Как вы понимаете подход синтеза тестов ОД и какие вам известны подходы структурного синтеза тестов КЛС?

2. В чем сущность классического подхода? Перечислите его этапы.

3. Охарактеризуйте подход "одномерной активизации".

4. Докажите утверждение 4.1.

5. Чем по вашему мнению вызваны недостатки подхода "одномерной активизации"? Обладает ли этими недостатками подход "синтез + моделирование"

6. Назовите этапы подхода "синтез + моделирование" .

7. Какие вам известны способы построения предварительного теста для подхода "синтез + моделирование" ?

8. Чем совпадают и чем отличаются второй и третий подходы синтеза Т1. Приведите соответствующие примеры.

Схожі:

Комбинационных схем iconКваліметричне оцінювання ефективності схем суперфінішування шийок великогабаритних колінчастих валів
У статті наведено результати комплексного оцінювання схем обробки при суперфінішуванні на основі модифікованого методу зворотного...
Комбинационных схем iconКнига для учащихся / В. К. Кононенко. Мн. Нар асвета, 1985. 127с ил. 15коп. Кільк прим.: 4
Сто схем с индикаторами [Текст] / Ю. А. Быстров, А. П. Гапунов, Г. М. Персианов. – М. Радио и связь, 1990. – 111с.;схем. – (мрб:...
Комбинационных схем iconПрограма спецкурс «Моделювання та аналіз аналогових І цифрових радіоелектронних схем» Спецiальнiсть: 070203 прикладна фiзика
У спецкурсі вивчаються методи формування математичних моделей радіоелектронних схем на макрорівні у вигляді системи звичайних диференційних...
Комбинационных схем icon2. Код модуля: Тип модуля: обов’язковий Семестр
Вп ес. Вимоги до схем живлення вп ес. Загальні положення. Електричні схеми живлення системи вп кес. Визначення номінальної потужності...
Комбинационных схем iconМетодичні вказівки до виконання лабораторної роботи «Застосування Electronics Workbench для моделювання електронних схем»
Методичні вказівки до виконання лабораторної роботи «Застосування Electronics Workbench для моделювання електронних схем» із дисципліни...
Комбинационных схем iconВаріанти електричних схем

Комбинационных схем iconВаріанти електричних схем

Комбинационных схем iconТестування штучних структур схем цифрових пристроїв генераторним способом

Комбинационных схем iconПринципы построения технологических схем получения кремния полупроводниковой чистоты

Комбинационных схем iconПрограма фахового іспиту
Основні класи інтерферометричних схем та їх використання для вимірювання когерентності світла
Додайте кнопку на своєму сайті:
Документи


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