Скобцовы Моделирование и тестирование
.pdfНАЦИОНАЛЬНАЯ АКАДЕМИЯ НАУК УКРАИНЫ Институт прикладной математики и механики МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ Донецкий национальный технический университет
Ю.А.Скобцов, В.Ю.Скобцов
ЛОГИЧЕСКОЕ МОДЕЛИРОВАНИЕ И ТЕСТИРОВАНИЕ ЦИФРОВЫХ УСТРОЙСТВ
Донецк 2005
УДК 519.713 : 681.3
Логическое моделирование и тестирование цифровых устройств/
Скобцов Ю.А., Скобцов В.Ю. – Донецк: ИПММ НАН Украины, ДонНТУ,
2005. –436с. – ISBN 966-02-3925-4.
Рассмотрены вопросы логического моделирования исправных и неисправных цифровых устройств. Исследованы методы построения проверяющих тестов для комбинационных и последовательностных схем.
Изложен эволюционный подход к построению тестов цифровых систем.
Рассмотрены вопросы программной реализации систем автоматизированного моделирования и генерации тестов цифровых систем.
Книга предназначена для научных сотрудников и инженеров,
работающих в области проектирования, производства и эксплуатации компьютерных систем и автоматизации проектирования. Она будет полезна также для студентов и аспирантов соответствующих
специальностей.
Ил. 168. Табл. 73, Библиогр.: 424-436с. (128 наим.).
Рецензенты:
Доктор технических наук, профессор Святный В.А.
Доктор технических наук, профессор Каргин А.А.
Утверждено к печати Ученым советом Института прикладной математики и механики НАН Украины
Донецкого национального технического университета
ISBN 966-02-3925-4 © Ю.А.Скобцов, В.Ю.Скобцов, 2005
|
|
ОГЛАВЛЕНИЕ |
|
ПРЕДИСЛОВИЕ |
9 |
||
1. |
Модели цифровых устройств |
13 |
|
|
1.1 |
Уровни и области моделирования |
13 |
|
1.2 |
Функциональные модели |
16 |
|
|
1.2.1 Модели комбинационных схем |
16 |
|
|
1.2.2 Модели последовательностных схем |
18 |
|
|
1.2.3 Альтернативные графы (бинарные диаграммы решений) |
22 |
|
1.3 |
Структурные модели |
24 |
|
|
1.3.1 Внешнее описание схемы |
25 |
|
|
1.3.2 Свойства структурных моделей |
28 |
|
|
1.3.3 Монтажная логика |
30 |
|
1.4 |
Модели уровня ЯРП |
31 |
2. |
Логическое моделирование |
35 |
|
|
2.1 |
Состав и назначение программ логического моделирования |
35 |
|
2.2. Общие принципы логического моделирования |
38 |
|
|
2.3 |
Модели сигналов |
41 |
|
2.4 |
Модели логических элементов в двоичном алфавите |
43 |
|
|
2.4.1 Таблицы истинности |
43 |
|
|
2.4.2 Таблицы zoom |
44 |
|
|
2.4.3 Программные функциональные модели |
45 |
|
|
2.4.4 Алгоритмические функциональные модели |
46 |
|
2.5 |
Модели логических элементов в многозначных алфавитах |
47 |
|
|
2.5.1 Табличные многозначные модели |
48 |
|
|
2.5.2 Компонентные многозначные модели |
49 |
|
|
2.5.3 Метод сканирования входов |
50 |
|
|
2.5.4 Метод счетчиков |
51 |
|
2.6 |
Модели задержек логических элементов |
52 |
3
2.7 |
Внутренние (машинные) модели схем |
58 |
|
2.7.1 Компилятивная модель |
58 |
|
2.7.2 Интерпретативная модель |
61 |
2.8 |
Управление процессом моделирования |
63 |
2.9 |
Анализ состязаний |
72 |
|
2.9.1 Явление состязания сигналов |
72 |
|
2.9.2 Анализ состязаний по методу Эйхельбергера |
76 |
3. Единая система многозначных алфавитов и функций |
82 |
|
3.1. Универсальный 16-значный алфавит B16 |
83 |
|
3.2. Многозначные функции |
86 |
|
3.3. Основные многозначные алфавиты как подмножества |
|
|
универсального 16-значного алфавита |
90 |
|
3.4 |
Алгебраическая структура многозначных алфавитов |
94 |
3.5 |
Моделирование шинных структур |
95 |
3.6 |
Комбинированные характеристические переменные и |
99 |
функции |
|
|
3.7 |
Многозначные модели функционального уровня |
104 |
|
3.7.1 Многозначные функции |
104 |
|
3.7.2 Многозначные функции основных операторов языков |
|
|
регистровых передач |
109 |
|
3.7.3 Характеристические функции |
112 |
4. Модели неисправностей |
114 |
|
4.1 |
Дефекты и неисправности |
114 |
4.2 |
Физические дефекты |
118 |
4.3 |
Типовые модели неисправностей |
120 |
4.4 |
Константные неисправности |
123 |
4.5 |
Сокращение списков неисправностей |
125 |
4.6 |
Замыкания |
131 |
4
4.7 |
Транзисторные неисправности (“устойчивый обрыв |
|
транзистора” и “устойчивое замыкание транзистора ”) |
133 |
|
4.8 |
Неисправности типа «задержка» |
138 |
4.9 |
Временные неисправности |
139 |
4.10 Функциональные неисправности |
140 |
|
|
4.10.1 Неисправности переменных данных и управления |
140 |
|
4.10.2 Неисправности уровня ЯРП |
141 |
|
4.10.3 Методы тестирования программ |
142 |
|
4.10.4 Функциональные модели неисправностей и меры |
|
|
полноты тестов для ЦС, описанных на HDL |
143 |
|
4.10.5 Неисправности текста программ HDL |
145 |
|
4.10.6 Меры покрытия функциональных неисправностей |
145 |
|
4.10.7 Тэги |
147 |
|
4.10.8 Функциональные модели неисправностей автоматного |
|
|
уровня |
152 |
|
4.10.9 Функциональные неисправности микропроцессоров |
153 |
|
4.10.10 Неисправности интерфейса |
155 |
5. Моделирование цифровых устройств с неисправностями |
156 |
|
5.1. Последовательное моделирование |
158 |
|
5.2 |
Параллельное моделирование |
160 |
|
5.2.1 Параллельное моделирование в двоичном алфавите |
160 |
|
5.2.2 Параллельное моделирование в троичном алфавите |
164 |
|
5.2.3 Параллельное моделирование в многозначных алфавитах |
166 |
5.3 |
Дедуктивный метод моделирования |
172 |
|
5.3.1 Дедуктивное моделирование в двоичном алфавите |
172 |
|
5.3.2 Дедуктивное моделирование в троичном алфавите |
177 |
|
5.3.3 Дедуктивное моделирование в многозначных алфавитах |
178 |
5.4 |
Конкурентный метод моделирования |
182 |
5
5.5 |
Одиночное распространение |
190 |
5.6 |
Моделирование неисправностей задержек распространения |
|
сигналов |
197 |
|
5.7 |
Метод обратного просматривания |
204 |
5.8 |
Результаты программ моделирования неисправных схем |
207 |
|
5.8.1 Полнота теста |
207 |
|
5.8.2 Словарь неисправностей |
208 |
6. Построение проверяющих тестов для комбинационных |
|
|
логических схем |
210 |
|
6.1 |
Псевдослучайный метод генерации тестов |
212 |
6.2 |
Метод критических путей |
214 |
6. 3 Метод различающей функции |
219 |
|
6.4 |
Метод булевых производных |
220 |
6.5 |
Метод активизации одномерного пути |
224 |
6.6 |
Многозначные алфавиты в генерации тестов |
227 |
6.7 |
D – алгоритм |
233 |
6.8 |
Метод PODEM |
243 |
6.9 |
Метод FAN |
250 |
6.10 Метод построения тестов в десятизначном алфавите |
251 |
|
6.11. Построение тестов в шестнадцатизначном алфавите |
255 |
|
6.12 Системы генерации тестов |
259 |
|
6.13 Сжатие тестов |
263 |
|
7. Построение тестов для устройств с памятью |
266 |
|
7.1 |
Структурный подход |
268 |
|
7.1.1 Итеративные комбинационные схемы |
268 |
|
7.1.2 Построение тестов для последовательностных схем в 16- |
|
|
значном алфавите |
273 |
6
7.2 Функциональный подход – построение тестов для устройств с |
|
памятью на основе экспериментов с автоматами |
282 |
7.2.1 Основы экспериментов с конечными автоматами |
283 |
7.2.2 Идентифицирующие последовательности конечных |
|
автоматов |
287 |
7.3 Комбинированный подход к построению тестов устройств с |
|
памятью |
291 |
7.3.1 Стратегия кратного наблюдения |
291 |
7.3.2 Аналитический метод построения тестов |
294 |
7.3.3 Структурный метод построения тестов |
306 |
7.3.4 Символьное моделирование последовательностных |
|
логических схем |
320 |
7.3.5 Построение идентифицирующих последовательностей |
323 |
7.3.6 Контрольные эксперименты для последовательностных |
|
схем |
330 |
7.3.7 Построение проверяющих тестов для функциональных |
|
неисправностей одиночного перехода |
335 |
8. Эволюционные методы построения проверяющих тестов |
344 |
8.1 Простой генетический алгоритм в генерации тестов |
|
комбинационных схем |
345 |
8.2 Модификации и обобщения ГА |
350 |
8.2.1 Создание исходной популяции |
351 |
8.2.2 Отбор родителей – селекция |
351 |
8.2.3 Операторы рекомбинации (кроссинговера) |
353 |
8.2.4 Мутация |
356 |
8.2.5 Сокращение промежуточной популяции |
357 |
8.3 ГА в генерации тестов слабо последовательностных схем |
359 |
7
8.4 |
Проблемно-ориентированные фитнесс-функции для генерации |
|
тестов |
361 |
|
8.5 |
Реализация генетического алгоритма генерации тестов |
367 |
8.6 |
Адаптивные ГА |
375 |
8.7 |
Параллельные ГА |
379 |
8.8 |
Иерархические ГА построения тестов для |
|
сильно последовательностных схем |
384 |
|
|
8.8.1 Функциональный подход |
384 |
|
8.8.2 Структурный подход |
386 |
8.9 |
Двухуровневый ГА построения тестов для микропроцессорных |
|
систем |
396 |
|
8.10 Генетическое программирование в генерации тестов для |
|
|
микропроцессорных систем |
402 |
|
9. Автоматизированная система моделирования и диагностики |
410 |
|
9.1 |
Функции и назначение системы |
410 |
9.2 |
Структуры данных |
412 |
9.3 |
Ввод схем |
416 |
9.4 |
Моделирование исправных схем |
417 |
9.5 |
Моделирование схем с неисправностями |
418 |
9.6 |
Генерация тестов |
419 |
9.7 |
Просмотр результатов |
420 |
9.8 |
Экспериментальные результаты |
421 |
Литература |
424 |
|
8
ПРЕДИСЛОВИЕ
Стремительное развитие компьютерной техники в последнее десятилетие обусловлено высокими технологиями производства элементной базы и систем автоматизированного проектирования (САПР).
Моделирование и тестирование логических схем являются одними из важнейших компонент САПР компьютерных систем. Наряду с эволюцией компьютерных систем идет эволюция методов и средств автоматизации проектирования. В настоящее время каждый этап проектирования автоматизирован. Сложность современных цифровых однокристальных систем (System On Chip – SOC) требует автоматизации проектирования всех этапов, включая моделирование и тестирование, на логическом и функциональном уровне. Это делает необходимым разработку соответствующих моделей и алгоритмов, которые частично представлены в данной работе.
Предлагаемая монография посвящена теоретическим и прикладным проблемам технической диагностики компьютерных систем. В ней, наряду с современными основными положениями моделирования и тестирования логических схем, изложены результаты, полученные авторами за последнее десятилетие, которые продолжают работы [1,2].
В первом разделе рассматриваются уровни и области моделирования цифровых систем, функциональные и структурные модели комбинационных и последовательностных схем. Материал раздела использует работы [1,2] и современную классификацию моделей цифровых систем.
Во втором разделе представлены общие принципы логического моделирования, двоичные и многозначные модели сигналов и логических элементов, компилятивные и интерпретативные модели логических схем,
анализ состязаний сигналов. Представленные результаты раздела являются
9
развитием работы [1] и освещают современный подход к логическому моделированию цифровых схем.
Третий раздел посвящен исследованию многозначных моделей базовых элементов. Разработана единая система основных многозначных алфавитов, используемых в моделировании и генерации тестов. На этой базе предложена универсальная многозначная модель, которая используется при моделировании исправных, неисправных логических схем и генерации тестов. Результаты раздела основаны на работах [3-7,
22].
В четвертом разделе описаны возможные физические дефекты для современной элементной базы, включая элементы, выполняемые по МОП
иКМОП технологиям. Рассмотрены модели этих дефектов –
неисправности на структурном и функциональном уровнях. Изложены методы сокращения множества моделируемых неисправностей.
В пятом разделе рассматриваются основные методы моделирования неисправных логических схем: последовательный, параллельные по неисправностям и наборам, дедуктивный, конкурентный. Особое внимание уделяется моделированию неисправностей в многозначных алфавитах.
Исследуется моделирование нового класса неисправностей – задержек распространения сигналов. При написании раздела использованы работы
[8-12].
Шестой раздел посвящен исследованию методов построения проверяющих тестов для комбинационных схем. Изложены основные методы генерации тестов: псевдослучайный, критических путей,
различающей функции и булевых производных, D-алгоритм, PODEM, FAN. Исследованы методы построения тестов с использованием различных многозначных алфавитов. Материал раздела использует результаты [13-15].
10