Моделирование, тестирование и диагностика цифровых устройств

Упражнение 1:

Номер 1


Пусть схема ЦУ с четырьмя входами и двумя выходами представлена в таблице, помещенной ниже. Предполагается, что это ЦУ содержит множество возможных неисправностей. Пусть в качестве теста используются входные наборы Исправное ЦУ (эталон) на эти входные наборы выдает следующие реакции: 
00 00 00 01 01 01 01 01 00 00 00 01 11 11 11 01

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


00	00	00	01	01	01	01	01	00	00	00	01	11	11	11	01

Ответ:

(1)



	10	00
	00	00
	11	11
	11	11
	10	10
	01	01

(2)



	01	11
	01	11
	01	00
	01	10
	01	01
	00	10

(3)



	01	11
	01	11
	01	00
	01	00
	01	01
	00	10

(4)



	10	11
	01	00
	11	11
	11	11
	10	10
	00	01

Номер 2


Пусть схема ЦУ с четырьмя входами и двумя выходами представлена в таблице, помещенной ниже. Предполагается, что это ЦУ содержит множество возможных неисправностей. Пусть в качестве теста используются входные наборы Исправное ЦУ (эталон) на эти входные наборы выдает следующие реакции: 
00 00 00 01 01 01 01 01 00 00 00 01 11 11 11 01

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


00	00	00	01	01	01	01	01	00	00	00	01	11	11	11	01

Ответ:

(1)



	10	00
	00	00
	11	11
	11	11
	10	10
	01	01

(2)


	,
	01	11
	01	11
	01	00
	01	10
	01	01
	00	10

(3)


	,
	1	1
	0	0
	0	1
	1	1
	1	1
	0	0

(4)


	,
	1	0
	0	0
	1	1
	1	1
	1	1
	1	1

Упражнение 2:

Номер 1


Пусть схема ЦУ с четырьмя входами и двумя выходами представлена в таблице, помещенной ниже. Предполагается, что это ЦУ содержит множество возможных неисправностей. Пусть в качестве теста используются входные наборы Исправное ЦУ (эталон) на эти входные наборы выдает следующие реакции: 
00 00 00 01 01 01 01 01 00 00 00 01 11 11 11 01

Условимся далее представленное ЦУ  обозначать как ЦУ-1.
Постройте словарь неисправностей с использованием компактных сверток по выходу для диагностического теста ,	 
В качестве множества неисправностей использовать  Предполагается, что выход 1-это линия 10, а выход 2- это линия 11 ЦУ-1.


00	00	00	01	01	01	01	01	00	00	00	01	11	11	11	01

Ответ:

(1)


,		Вых. 10	Вых. 11
10	00	1	0
00	00	0	0
11	11	1	1
11	11	1	1
10	10	1	0
01	01	0	1

(2)


,		Вых. 10	Вых. 11
1	0	1	0
0	0	0	0
1	1	1	1
1	1	1	1
1	1	1	0
1	1	0	1

(3)


		Вых. 10	Вых. 11
1	0	1	0
0	0	0	0
1	1	1	1
1	1	1	1
1	1	1	1
1	1	1	1

(4)


		Вых. 10	Вых. 11
00	00	0	0
00	00	0	0
11	00	1	0
11	11	1	1
10	10	1	10
01	01	1	1

Номер 2


Пусть схема ЦУ с четырьмя входами и двумя выходами представлена в таблице, помещенной ниже. Предполагается, что это ЦУ содержит множество возможных неисправностей. Пусть в качестве теста используются входные наборы Исправное ЦУ (эталон) на эти входные наборы выдает следующие реакции: 
00 00 00 01 01 01 01 01 00 00 00 01 11 11 11 01

Условимся далее представленное ЦУ  обозначать как ЦУ-1.
Используя Т-ТФН, построенную для ЦУ-1, постройте словарь неисправностей с ориентацией на выходы  для диагностического теста ,	 
В качестве множества неисправностей использовать множество  Предполагается, что выход 1-это линия 10, а выход 2- это линия 11 ЦУ-1.


00	00	00	01	01	01	01	01	00	00	00	01	11	11	11	01

Ответ:

(1)



Выход 10	1	1	0	1	0	0
Выход 11	1	0	1	1	1	0

(2)



Выход 10	1	0	1	1	1	0
Выход 11	0	0	1	1	0	1

(3)



Выход 10	10	00	11	11	10	01
Выход 11	00	00	11	11	10	01

(4)



Выход 10	10	00	11	11	11	00
Выход 11	00	00	11	11	00	11

Упражнение 3:

Номер 1

Представленная  ниже таблица - словарь полной реакции (СПР) некоторого ЦУ на тест  Пусть - разбиение множества состояний  ЦУ (- исправное ЦУ, - ЦУ с -ой неисправностью), а - элементы этого разбиения. Каждому состоянию соответствует маска , и пусть - множество всех масок  Предполагается, что каждое  содержит одно состояние Требуется построить для различных типов масок (общих и индивидуальных) при заданном множестве 
                 
 
11 00 11 10
10 10 11 10
00 00 11 10
00 00 00 10
01 00 00 10
01 00 01 10
01 00 01 00
10 00 10 10
11 11 11 10

 Построить , где множество содержит единую (общую) маску для всех и эта маска


11	00	11	10
10	10	11	10
00	00	11	10
00	00	00	10
01	00	00	10
01	00	01	10
01	00	01	00
10	00	10	10
11	11	11	10

Ответ:

(1)


	1011
	1111
	0011
	0001
	0001
	0001
	0000
	1011
	1111

(2)


	1100
	1010
	0000
	0000
	0100
	0100
	0100
	1000
	1111

(3)


	1010
	0010
	0010
	0000
	1000
	1010
	1010
	0000
	1110

Ответ4


	1011
	0011
	0011
	0001
	1001
	1001
	1000
	0011
	1111

Номер 2

Представленная  ниже таблица - словарь полной реакции (СПР) некоторого ЦУ на тест  Пусть - разбиение множества состояний  ЦУ (- исправное ЦУ, - ЦУ с -ой неисправностью), а - элементы этого разбиения. Каждому состоянию соответствует маска , и пусть - множество всех масок  Предполагается, что каждое  содержит одно состояние Требуется построить для различных типов масок (общих и индивидуальных) при заданном множестве 
                     
 
11 00 11 10
10 10 11 10
00 00 11 10
00 00 00 10
01 00 00 10
01 00 01 10
01 00 01 00
10 00 10 10
11 11 11 10

Построить , где множество содержит  следующие маски:
,
,
,
,
,


11	00	11	10
10	10	11	10
00	00	11	10
00	00	00	10
01	00	00	10
01	00	01	10
01	00	01	00
10	00	10	10
11	11	11	10

Ответ:

(1)


	1100
	1010
	0000
	0000
	0100
	0100
	0100
	1000
	1110

(2)


	1011
	1111
	0010
	01
	01
	11
	111
	0
	111

(3)


	1010
	1110
	01
	01
	01
	11
	110
	1
	111

(4)


	010
	110
	101
	011
	101
	111
	110
	010
	111

Упражнение 4:

Номер 1

 
Можно ли задачу сокращения диагностической информации свести к классической задаче о классификации объектов?

Ответ:

(1) да, для этого в качестве множества классифицируемых объектов следует рассматривать множество всех возможных неисправных модификаций ЦУ. Далее можно использовать любой алгоритм классификации

(2) да, для этого можно воспользоваться структурой дерева решений, а в узлах дерева применять классифицирующие правила типа "если … то"

(3) нет, поскольку в задачах классификации каждый объект характеризуются, как правило, большим количеством числовых признаков, а в задачах сокращения диагностической информации такого рода признаки отсутствуют

Номер 2

Жадный алгоритм поиска масок, описанный в лекции 31,базируется на применении конструкции дерева решений. Проиллюстрируйте конструкцию классического дерева решений для решения следующей задачи: имеется 8 одинаковых монет, среди которых одна фальшивая (она легче, чем стандартная). Монеты пронумерованы числами 1,2,…,8. Требуется найти фальшивую монету, используя равновесные весы с двумя чашками (пусть левая чашка имеет №1, правая - №2).

Ответ:

(1) на чашку №1 кладутся монеты 1-4, на чашку №2 - монеты 5-8 и производится первое взвешивание. Если чашка №1 легче, то на чашку №1 кладутся монеты 1,2, а на чашку №2 -монеты 3,4 и производится второе взвешивание. Если чашка №1 легче, то на чашку №1 кладется монета 1, на чашку №2 - монета 2 и производится третье взвешивание. Если чашка №1 легче, то монета 1-фальшивая, в противном случае монета 2-фальшивая. Аналогичные действия производятся с монетам 5-8 после первого взвешивания, если чашка №2 оказалась легче

(2) на чашки весов последовательно кладутся монеты 1 и 2, затем 3 и 4 и т.д. Алгоритм определения фальшивой монеты при таком взвешивании очевиден

Упражнение 5:

Номер 1

 Для некоторого ЦУ задается СПР в виде таблицы, где - множество технических состояний ЦУ, - диагностический тест для этого ЦУ. Используя жадный алгоритм поиска масок, изложенный в лекции 31, найти для заданного СПР единую маску минимального объема.
Решить задачу для СПР, заданного табл.
                   
10 01 11 10
10 10 11 10
00 11 11 10
00 00 00 11
01 00 10 10
01 00 01 10
01 00 01 00
10 00 10 10
11 11 11 10


10	01	11	10
10	10	11	10
00	11	11	10
00	00	00	11
01	00	10	10
01	00	01	10
01	00	01	00
10	00	10	10
11	11	11	10

Ответ:

(1)

(2)

(3)

(4)

Номер 2

 Для некоторого ЦУ задается СПР в виде таблицы, где - множество технических состояний ЦУ, - диагностический тест для этого ЦУ. Используя жадный алгоритм поиска масок, изложенный в лекции 31, найти для заданного СПР единую маску минимального объема.
Решить задачу для СПР, заданного табл
                   
01 10 01 00
00 01 00 10
00 00 10 11
01 00 10 10
11 01 11 10
10 00 10 10
10 01 11 01
10 00 11 10
01 00 01 10


01	10	01	00
00	01	00	10
00	00	10	11
01	00	10	10
11	01	11	10
10	00	10	10
10	01	11	01
10	00	11	10
01	00	01	10

Ответ:

(1)

(2)

(3)

(4)

Упражнение 6:

Номер 1

Для некоторого ЦУ задается СПР в виде таблицы, где  - множество технических состояний ЦУ, - диагностический тест для этого ЦУ. Используя жадный алгоритм поиска индивидуальных  масок, изложенный в лекции 32, найти для заданного СПР множество индивидуальных масок минимального суммарного объема.
 
Решить задачу для СПР, заданного табл. 
10 01 11 10
10 10 11 10
00 11 11 10
00 00 00 11
01 00 10 10
01 00 01 10
01 00 01 00
10 00 10 10
11 11 11 10


10	01	11	10
10	10	11	10
00	11	11	10
00	00	00	11
01	00	10	10
01	00	01	10
01	00	01	00
10	00	10	10
11	11	11	10

Ответ:

(1)

;

(2)

;

(3)

h_0= \{2:1,2:2\}, h_1=h_3=\{4:2\}, h_2=\{1:1,2:2,4:2\},h_4=\{1:2,3:2\}, h_5=\{1:2,3:1,4:1\}, h_6=\{4:1\}, h_7=\{1:1,3:2\}, h_8=\{1:2,2:1\}

;

(4)

h_0= \{2:1,2:2\}, h_1=h_3=\{4:1,4:2\}, h_2=\{1:1,2:2,4:2\},h_4=\{1:2,3:2\}, h_5=\{1:2,3:1,4:1\}, h_6=\{4:1\}, h_7=\{1:1,3:2\}, h_8=\{1:2,2:1\}

Номер 2

Для некоторого ЦУ задается СПР в виде таблицы, где  - множество технических состояний ЦУ, - диагностический тест для этого ЦУ. Используя жадный алгоритм поиска индивидуальных  масок, изложенный в лекции 32, найти для заданного СПР множество индивидуальных масок минимального суммарного объема.
 
Решить задачу для СПР, заданного табл. 
01 10 01 00
00 01 00 10
00 00 10 11
01 00 10 10
11 01 11 10
10 00 10 10
10 01 11 01
10 00 11 10
01 00 01 10


01	10	01	00
00	01	00	10
00	00	10	11
01	00	10	10
11	01	11	10
10	00	10	10
10	01	11	01
10	00	11	10
01	00	01	10

Ответ:

(1)

h_0= h_1=\{2:1\}, h_2=\{1:1,4:2\}, h_3=\{1:1,3:2\},h_4=\{1:2,2:2\}, 
h_5=\{1:2,3:2\}, h_6=\{1:1,4:1\}, h_7=\{1:1,2:2,3:2\}, h_8=\{2:1,3:1\}

;

(2)

h_0= h_1=\{1:1,2:2\}, h_2=\{1:1,4:2\}, h_3=\{1:2,3:2\},h_4=\{1:2,2:2\}, 
h_5=\{1:1,3:2\}, h_6=\{1:1,4:1\}, h_7=\{1:1,2:2,3:2\}, h_8=\{2:1,3:1\}

;

(3)

h_0= \{2:1\}, h_1=\{1:1,2:2\}, h_2=\{1:1,4:2\},h_3=\{1:1,3:2\},h_4=\{1:2,2:2\}, 
h_5=\{1:1,3:2\}, h_6=\{1:1,4:1\}, h_7=\{1:1,2:2,3:2\}, h_8=\{2:1,3:1\}

;

(4)

h_0= h_8=\{2:1,3:1\}, h_1=h_5=h_7=\{1:1,2:2,3:2\}, h_2=\{1:1,4:2\},h_3=\{1:2,3:2\}, 
h_4=\{1:2,2:2\}, h_6=\{1:1,4:1\}

Номер 3

 
Целесообразно ли при поиске единой маски или множества индивидуальных масок с помощью жадных алгоритмов 1 или 2, описанных в лекциях 31 и 32, к исходной ДИ, представленной в виде СПР, применять какие-либо методы ее предварительного сокращения (к примеру, преобразования СПР в таблицу неисправностей)? Дайте обоснование любого варианта вашего ответа.

Ответ:

(1) Да, поскольку предварительное сокращение ДИ может быть весьма существенным и, следовательно, можно ожидать значительного эффекта (как по качеству, так и по времени поиска) при поиске масок для ДИ меньшего объема. Этот вывод подтверждается анализом экспериментальных данных, приведенных в лекции 33.

(2) Нет, поскольку применение предварительного сокращения исходной ДИ требует дополнительных временных затрат. Вместе с тем результат применения жадных алгоритмов как к исходной, так и к сокращенной ДИ, может отличаться столь незначительно, что не оправдает упомянутых предварительных временных затрат.


11	00	11	10
10	10	11	10
00	00	11	10
00	00	00	10
01	00	00	10
01	00	01	10
01	00	01	00
10	00	10	10
11	11	11	10


11	00	11	10
10	10	11	10
00	00	11	10
00	00	00	10
01	00	00	10
01	00	01	10
01	00	01	00
10	00	10	10
11	11	11	10


10	01	11	10
10	10	11	10
00	11	11	10
00	00	00	11
01	00	10	10
01	00	01	10
01	00	01	00
10	00	10	10
11	11	11	10


01	10	01	00
00	01	00	10
00	00	10	11
01	00	10	10
11	01	11	10
10	00	10	10
10	01	11	01
10	00	11	10
01	00	01	10


10	01	11	10
10	10	11	10
00	11	11	10
00	00	00	11
01	00	10	10
01	00	01	10
01	00	01	00
10	00	10	10
11	11	11	10


01	10	01	00
00	01	00	10
00	00	10	11
01	00	10	10
11	01	11	10
10	00	10	10
10	01	11	01
10	00	11	10
01	00	01	10


11	00	11	10
10	10	11	10
00	00	11	10
00	00	00	10
01	00	00	10
01	00	01	10
01	00	01	00
10	00	10	10
11	11	11	10


11	00	11	10
10	10	11	10
00	00	11	10
00	00	00	10
01	00	00	10
01	00	01	10
01	00	01	00
10	00	10	10
11	11	11	10


10	01	11	10
10	10	11	10
00	11	11	10
00	00	00	11
01	00	10	10
01	00	01	10
01	00	01	00
10	00	10	10
11	11	11	10


01	10	01	00
00	01	00	10
00	00	10	11
01	00	10	10
11	01	11	10
10	00	10	10
10	01	11	01
10	00	11	10
01	00	01	10


10	01	11	10
10	10	11	10
00	11	11	10
00	00	00	11
01	00	10	10
01	00	01	10
01	00	01	00
10	00	10	10
11	11	11	10


01	10	01	00
00	01	00	10
00	00	10	11
01	00	10	10
11	01	11	10
10	00	10	10
10	01	11	01
10	00	11	10
01	00	01	10

Моделирование, тестирование и диагностика цифровых устройств - тест 33


11	00	11	10
10	10	11	10
00	00	11	10
00	00	00	10
01	00	00	10
01	00	01	10
01	00	01	00
10	00	10	10
11	11	11	10


11	00	11	10
10	10	11	10
00	00	11	10
00	00	00	10
01	00	00	10
01	00	01	10
01	00	01	00
10	00	10	10
11	11	11	10


10	01	11	10
10	10	11	10
00	11	11	10
00	00	00	11
01	00	10	10
01	00	01	10
01	00	01	00
10	00	10	10
11	11	11	10


01	10	01	00
00	01	00	10
00	00	10	11
01	00	10	10
11	01	11	10
10	00	10	10
10	01	11	01
10	00	11	10
01	00	01	10


10	01	11	10
10	10	11	10
00	11	11	10
00	00	00	11
01	00	10	10
01	00	01	10
01	00	01	00
10	00	10	10
11	11	11	10


01	10	01	00
00	01	00	10
00	00	10	11
01	00	10	10
11	01	11	10
10	00	10	10
10	01	11	01
10	00	11	10
01	00	01	10