Разработка и исследование методов и алгоритмов построения тестов последовательностных схем на основе непрерывного подхода тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат технических наук Данилов, Сергей Олегович

• Данилов, Сергей Олегович
• кандидат технических наук
• 2004

Оглавление диссертации кандидат технических наук Данилов, Сергей Олегович

ВВЕДЕНИЕ.

ГЛАВА 1. АНАЛИЗ ПРОБЛЕМЫ ГЕНЕРАЦИИ ТЕСТОВ ДЛЯ СИНХРОННЫХ ПОСЛЕДОВ ATE ЛЬНОСТНЫХ СХЕМ.

1.1. Виды неисправностей логических схем.

1.2. Существующие методы и алгоритмы тестирования последовательностных схем.

1.2.1. Функциональные подходы.

1.2.2. Эвристические методы.

1.2.3. Подходы, подразумевающие известное начальное состояние схемы.

1.2.4. Контролепригодный сканируемый дизайн схемы.

1.2.5. Методы высших уровней абстракции.

1.3. Сложность проблемы генерации тестов.

Выводы и постановка задачи.

ГЛАВА 2. РАЗРАБОТКА НЕПРЕРЫВНОГО ПОДХОДА К ТЕСТИРОВАНИЮ СИНХРОННЫХ ПОСЛЕДОВАТЕЛЬНОСТНЫХ СХЕМ.

2.1. Общая структура взаимодействия разработанных алгоритмов.

2.2. Необходимые определения.

2.3. Алгоритмы преобразования последовательностной схемы в итеративный логический массив.

2.4. Используемая в работе модель неисправностей.

2.5. Подход к поиску тестовых последовательностей путем поиска максимума построенной непрерывной целевой функции.

2.6. Непрерывная целевая функция для задачи поиска тестовой последовательности.

2.7. Сложность целевой функции.

Выводы.

ГЛАВА 3. ИССЛЕДОВАНИЕ ЭФФЕКТИВНОСТИ МЕТОДОВ ЛОКАЛЬНОЙ ОПТИМИЗАЦИИ ПРИМЕНИТЕЛЬНО К ЗАДАЧАМ ПОИСКА ТЕСТОВ.

3.1. Объект и методы исследования.

3.2. Исследование алгоритмов на примере схемы s27.

3.3. Исследование алгоритмов на примере схемы s344.

3.4. Исследование алгоритмов на примере схемы si 196.

Выводы.

ГЛАВА 4. МЕТОДЫ ПОВЫШЕНИЯ ЭФФЕКТИВНОСТИ ПОИСКА ТЕСТОВ.

4.1. Вычисление количества предваряющих и замыкающих временных кадров.

4.2. Сортировка неисправностей в списке.

4.3. «Заморозка» схемы.

4.4. Анализ нетестируемых неисправностей.

4.5. Алгоритмы моделирования неисправностей.

4.5.1. Моделирование неисправностей на очувствленном пути.

4.5.2. Полное моделирование неисправностей.

4.5.3. Моделирование с доопределением значений.

4.5.4. Адаптивное моделирование неисправностей.

4.6. Пакетное тестирование.

4.7. Адаптивное изменение величины начального шага.

4.8. Фантомные (мнимые) первичные входы.

4.9. Контроль первого вектора.

4.10. Исследование зависимости покрытия и быстродействия алгоритма от значения неопределенного сигнала на линии.

4.11. Сравнение алгоритма SECONT с существующими алгоритмами. 136 Выводы.

Введение диссертации (часть автореферата) на тему «Разработка и исследование методов и алгоритмов построения тестов последовательностных схем на основе непрерывного подхода»

Актуальность работы

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

Практически невозможно устранить неисправность в уже изготовленной микросхеме. После того, как спецификация схемы поступила на завод по производству микросхем, требуется еще несколько недель [130], чтобы начать производство. Если ошибка обнаружена уже в произведенной микросхеме, требуется повторное проектирование и подготовка к производству. Это приводит к дополнительным затратам и временным задержкам, которые неприемлемы при заданном календарном плане и бюджете. Следовательно, значительная часть ресурсов при проектировании схемы должна быть занята проверкой правильности разработанной схемы.

Цель тестирования — удостовериться, что разработанная схема функционирует правильно и отвечает требованиям, заложенным разработчиком.

Учитывая, что тестирование играет ключевую роль в процессе производства микросхем (согласно [40], до 70% общих затрат на производство микросхемы расходуется на тестирование), оптимальная стратегия тестирования является насущной необходимостью. Поэтому не удивительно, что тестирование является ключевым компонентом значительной важности [85].

В настоящее время для тестирования последовательностных схем широко используются автоматические генераторы тестов, основанные на FAN-алгоритме [67][121]. Автоматическая генерация тестов для константных неисправностей в комбинационных и последовательностных схемах была исследована многими учеными, и было опубликовано впечатляющее количество алгоритмов и моделей, в частности: Seshu и Freeman (1962 г.) [124]; Kubo (1968 г.) [87]; Putzolu и Roth (1971 г.) [111]; Пархоменко (1971 г.) [31]; Гольдман и Чипулис (1976 г.) [20]; Muth (1976 г.) [99]; Матросова (1977 г.) [28]; Marlett (1978 г.) [95]; Биргер (1978 г.) [18]; Goel (1981 г.) [64]; Гуляев и др. (1981 г.) [23]; Fujiwara и Shimono (1983 г.) [60]; Тоценко (1985 г.) [33]; Горяшко (1987 г.) [21]; Kirkland и Mercer (1987 г.) [83]; Cheng (1988 г.) [51]; Убар (1988 г.) [34]; Schulz и Auth (1989 г.) [121]; Cheng и Davidson (1989 г.) [53]; Матросова (1990 г.) [29]; Niermann и Patel (1991 г.) [101]; Larrabee (1992 г.) [88]; Lee и На (1993 г.) [90]; Kelsey и Saluja (1993 г.) [82]; Teramoto (1993 г.) [131]; Silva и Sakallah (1994 г.) [125]; Ривин И., Chakradhar S.T. (1994 г.) [14]; Евтушенко, Лебедев и Петренко (1994 г.) [24]; Glaser и Vierhaus (1995 г.) [63]; Гессель и Согомонян (1996 г.) [18]; Куфарева и др. (1998 г.) [26]; Куфарева (2000 г.) [27].

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

Поскольку схемы содержат до миллионов логических элементов и линий соединения, тестирование схем в настоящее время является длительным и дорогостоящим процессом. Так как размер пространства поиска, внутри которого производится поиск тестовой последовательности векторов, растет экспоненциально от числа первичных входов и собственных состояний схемы, то проблема генерации тестов отнесена к классу NP-полных [79].

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

Цель работы

Целью работы является разработка и исследование эффективных методов построения тестов для синхронных последователыюстных схем на основе непрерывного подхода к моделированию схемы.

На защиту выносятся:

1. Способ поиска тестов для синхронных последовательностных схем путем нахождения максимума непрерывной целевой функции.

2. Алгоритмы построения тестов, использующие методы непрерывной оптимизации.

3. Анализ эффективности разработанных методов и алгоритмов.

4. Программное обеспечение для исследований алгоритмов поиска тестов на основе непрерывного подхода.

5. Экспериментальные исследования различных методов поиска тестов на стандартном наборе тестовых схем формата ISCAS'89 [47].

Методы исследования

Работа базируется на методах технической диагностики, теории построения проверяющих тестов, теории графов, теории конечных автоматов, булевой алгебры, методах прямого поиска.

Научная повнзна

Научная новизна работы состоит в следующем:

1. Разработан способ построения тестов синхронных последовательностных устройств на основе непрерывной оптимизации целевой функции.

2. Разработаны высокоэффективные алгоритмы моделирования схемы непрерывными функциями, позволившие значительно сократить время поиска тестовых последовательностей.

3. Предложены быстродействующие и не требовательные к объему оперативной памяти алгоритмы обработки последовательностных схем, насчитывающих сотни входов и десятки тысяч вентилей.

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

Практическая ценность

На базе разработанных алгоритмов и методов, используя написанное в рамках диссертации программное обеспечение, решены следующие прикладные задачи:

1. Разработаны алгоритмы преобразования исходной логической последовательностной схемы в итеративный массив из временных кадров, включающие в себя: алгоритм представления разветвлений, алгоритм преобразования триггеров и топологическую сортировку вентилей.

2. Реализован алгоритм поиска тестовых последовательностей на основе повторного использования единственного временного кадра в памяти программы.

3. Получены численные характеристики эффективности каждого из разработанных алгоритмов.

4. Реализована программная платформа для исследования эффективности алгоритмов построения тестов на основе непрерывных методов оптимизации.

5. Построены тестовые последовательности для последовательностных схем из стандартного тестового набора схем ISCAS'89.

Апробация работы

Основные положения работы доложены и апробированы на 7 научных конференциях:

- На конференции «Информационные системы и технологии ИСТ-2002» (г. Нижний Новгород, НГТУ, Апрель 2002);

- На конференции «Информационные системы и технологии ИСТ-2003» (г. Нижний Новгород, НГТУ, Апрель 2003);

- На региональном молодежном научно-техническом форуме «Будущее технической науки нижегородского региона» (г. Нижний Новгород, 2002);

- На девятой нижегородской сессии молодых ученых (технические науки) (г. Нижний Новгород, 2004);

- На международной конференции «Informatics, Mathematical Modelling and Design in the Technics, Controlling and Education», (IMMD'2004, Vladimir city, May 2004);

- На конференции «Мехатроника, автоматизация, управление» (МАУ, г. Владимир, Июнь 2004);

- На конференции East-West Design & Test Workshop - EDTW'04, (Ялта, Алушта - Крым, Украина, Сентябрь 2004).

Публикации

Основное содержание работы отражено в 10 печатных работах [1] —

Структура и объем работы

Текст диссертации состоит из введения, четырех глав, заключения, библиографического списка и приложения, содержит 158 стр. машинописного текста, 50 рисунков, 5 таблиц, библиографию из 132 наименований.

Заключение диссертации по теме «Системный анализ, управление и обработка информации (по отраслям)», Данилов, Сергей Олегович

Выводы

1. Реализован алгоритм, позволяющий оценить необходимое количество временных кадров для активизации и распространения неисправности.

2. Предложен алгоритм сортировки неисправностей в схеме, эффективный для больших схем.

3. Экспериментально показано, что алгоритм «заморозки» схемы, эффективный для комбинационных схем, не эффективен для последовательностных схем.

4. Разработан эффективный эвристический алгоритм анализа нетестируемых неисправностей.

5. Представлены три алгоритма моделирования неисправностей, их экспериментальное сравнение на схемах тестового набора ISCAS'89, и показана их высокая эффективность.

6. Введен алгоритм пакетного тестирования, позволяющий прикладывать очередной тест, используя информацию от предыдущего теста.

7. Предложен метод обработки «фантомных» первичных входов, позволяющий оптимизировать обработку итеративного массива.

8. Исследована зависимость эффективности генератора тестов от величины неопределенного значения на линии. Экспериментально показано, что значение 0.5 не всегда приводит к оптимальным результатам.

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

ЗАКЛЮЧЕНИЕ

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

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

2. Предложены эффективные алгоритмы обработки модели схемы, алгоритмы моделирования неисправностей алгоритмы поиска тестов.

3. Разработан механизм, позволяющий использовать любой метод локальной оптимизации для поиска тестов последовательностных схем. На базе данного механизма были применены 4 метода локальной оптимизации и исследована их эффективность.

4. Разработанные алгоритмы и методы экспериментально апробированы на широко известном тестовом наборе схем ISCAS'89. Эксперименты показали высокую эффективность предложенного подхода, сравнимую с лучшими классическими методами поиска тестов, основанными на дискретном подходе.

5. На ряде схем тестового набора ISCAS'89 достигнуто 100%-ное покрытие множества тестируемых неисправностей, что говорит о практической ценности и применимости представленных в диссертации алгоритмов.

Список литературы диссертационного исследования кандидат технических наук Данилов, Сергей Олегович, 2004 год

1. ДАНИЛОВ С. О. "Алгоритм генерации тестов последовательностных схем на основе непрерывной модели". // Тез. докл. научно — техн. форума "Будущее технической науки Нижегородского региона". Н. Новгород, 2002. стр. 118-119.

2. ДАНИЛОВ С.О. "Построение тестов последовательностных схем на основе непрерывного подхода". // Тез. докл. девятой нижегородской сессии молодых ученых. Н. Новгород, 2004. стр. 10 - 11.

3. ДАНИЛОВ С.О. "Транслятор для системы автономного тестирования". // Тез. докл. Всероссийской научно — техн. конф. "Информационные системы и технологии". Н. Новгород, 2001. стр. 130-131.

4. ДАНИЛОВ С.О., КАЩЕЕВ Н.И. "Алгоритм поиска тестовых последовательностей для тестирования последовательностных схем". // Межвуз. сб. науч. тр. "Труды НГТУ: Системы обработки информации и управления". Том 35, выпуск 9. Н. Новгород, 2002. стр. 79-81.

5. ДАНИЛОВ С.О., КАЩЕЕВ Н.И. "Использование методов непрерывной оптимизации для задач построения тестов последовательностных схем". // Тез. докл. Всероссийской научно - техн. конф. "Информационные системы и технологии". — Н. Новгород, 2002. стр. 186 - 187.

6. ДАНИЛОВ С.О., КАЩЕЕВ Н.И. "Выбор оптимального числа временных кадров для поиска тестовой последовательности". // Межвуз. сб. науч. тр. "Труды НГТУ: Системы обработки информации и управления". — Том 37, выпуск 10, — Н. Новгород, 2003. стр. 103 105.

7. ДАНИЛОВ С.О., КАЩЕЕВ Н.И. "Модифицированный метод градиентного подъема". // Тез. докл. Всероссийской научно — техн. конф. "Информационные системы и технологии". Н. Новгород, 2003. стр. 127-128.

8. ДАНИЛОВ C.O. "Непрерывный подход к построению тестов последовательностных схем" // Труды I Всеросс. научн. — техн. конф. "Мехатроника, автоматизация, управление". — Москва, 2004. стр. 352-355.

9. МИНДРОВ A.E., КАЩЕЕВ Н.И., "Использование непрерывной модели схемы для генерации тестов", Simulation and CAD systems, pp. 47-50, 1989.

10. Техническая диагностика электронных схем". Сборник научных трудов, Киев, "Наукова думка", 1982.

11. БИРГЕР А.И. "Техническая диагностика". М.: Машиностроение, 1978.-238 с.

12. ГЕССЕЛЬ М., СОГОМОНЯН Е.С. "Построение кодоразделительных самопаритетных комбинационных схем для самотестирования и функционального диагностирования" // Автоматика и телемеханика, 1996 —№11.

13. ГОЛЬДМАН Р. С., ЧИПУЛИС В. П. "Техническая диагностика цифровых устройств", М., Энергия, 1976.

14. КНУТ Д. "Искусство программирования", Т. 1, "Основные алгоритмы", М., 2001.

15. КУФАРЕВА И.Б., ЕВТУШЕНКО Н.В., ПЕТРЕНКО А.Ф. "Синтез проверяющих тестов для недетерминированного автомата относительно редукции" // Автоматика и вычислительная техника. — 1998. -№ 3.

16. ПАРХОМЕНКО П. П. "Методы построения надежных систем из недостаточно надежных элементов", Семинар, Общество "Знание", Киев, 1969.

17. SAR reference manual", version 6, Trademark of Teradyne, Inc., Boston, MA, 1987.

18. ABRAMOVICI M., BREUER M. A., FRIEDMAN A. D., "Digital systems testing and testable design", Computer Science Press, 1990.

19. AGARWAL V. D., MERCER M. R., "Testability Measures what do they tell us?" Digest of papers 1982 International Test conference, pp. 391 -396, November 1982.

20. AGRAWAL V. D., CHENG К. Т., AGRAWAL P. "CONTEST: A Concurrent Test Generator for Sequential Circuits", Proc. 25th Design Automation Conf., pp. 84 89, 1988.

21. BARDELL P. H., MCANNEY W. H., SAVIR J. "Built in Pseudorandom Testing of Digital Circuits", John Wiley, 1987. BENNETTS R„ "Design of Testable Logic Circuits", Addison Wesley, 1984.

22. BHATTACHARYYA A. "On a novel approach of fault detection in an easily testable sequential machine with extra inputs and extra outputs", IEEE Trans, on Computers, Vol. С 32, No. 3, pp. 323 - 325, Mar. 1983.

23. BILLINGTON D. P. "Engineering in the Modern World: A Freshman Course in Engineering", Princeton University, IEEE Frontiers in Education Conference, 1993.

24. CARTER W. С., MONTGOMERY H. C., PREISS R. J., REINHEIMER H J. "Design of serviceability features of the IBM system/360", IBM Journal of R&D. 1964.

25. CHENG К. Т., AGRAWAL V. D. "A partial scan method for sequential circuits with feedback". IEEE Trans. Comput. 39, 4, 544 548. April 1990.

26. CHENG К. Т., AGRAWAL V. D. "Unified Methods for VLSI Simulation and Test Generation". Kluwer Academic, Norwell, MA. 1989.

27. CHENG W. T. "The BACK Algorithm for Sequential Test Generation", Prec. Int. Conf. Computer Design (ICCD 88), Rye Brook, NY, pp. 66 -69, October 1988.

28. CHENG W. T. "Split Circuit Model For Test Generation", AT&T

29. Engineering Research Center Princeton, NJ 08540, 1988

30. CHENG W. Т., DAVIDSON S. "Sequential circuit test generator (STG)benchmark results", ISCAS'89: IEEE International Symposium on

31. Circuits And Systems, Portland, OR (USA), pp. 1939- 1941, May 1989.

32. CHO H., JEONG S., SOMENZI F., PIXLEY C. "Synchronizingsequences and symbolic traversal techniques in test generation". J.

33. Electron. Testing, Theor. Appl. 4, 1, 19 -31. 1993.

34. DORF Richard C., "The Electrical Engineering Handbook", Boca Raton:1. CRC Press LLC, 2000.

35. FLETCHER R., POWELL M. J. D., "A rapidly convergent descent method for minimization", The Computer Journal, 6, pp. 163 168. 1963.

36. FRIEDMAN A. D., MENON P. "Restricted Checking Sequences for Sequential Machines", IEEE Trans, on Computers, Vol. С — 22, No. 4, pp. 397-399, Apr. 1973.

37. FUJIWARA H., KINOSHITA К. "Design of Diagnosable Sequential Machines Utilizing Extra Outputs", IEEE Trans, on Computers, Vol. С — 23, No. 2, pp. 138 145, Feb. 1974.

38. FUJIWARA H., NAGAO Y., SASAO Т., KINOSHITA K. "Easily Testable Sequential Machines with Extra inputs", IEEE Trans, on Comput., vol. С 24, pp. 821 - 826, Aug. 1975.

39. FUJIWARA H., SHIMONO T. "On the Acceleration of Test Generation Algorithms", Proc. 13th International Symposium on Fault — Tolerant Computing (FTCS 13), Milan, Italy, IEEE CS Press, pp. 98 - 105, June 28-30, 1983.

40. GLAESER U., VIERHAUS H. T. "FOGBUSTER: An efficient algorithm for sequential test generation". In Proceedings of the European Design Automation Conference (EURODAC' 95), IEEE Computer Society Press, 230-235. Sept. 1995.

41. GOEL P. "An Implicit Enumeration Algorithm to Generate Tests for Combinational Logic Circuits", IEEE Transactions on Computers, Vol. С 30, No. 3„ pp. 215 - 222, March 1981.

42. HAMZAOGLU I. "Test Pattern Generation And Test Application Time Reduction Algorithms For Vlsi Circuits", 1999.

43. HAMZAOGLU I., PATEL J. H. "Deterministic Test Pattern Generation Techniques for Sequential Circuits", University of Illinois, Urbana, IL, November 2000.

44. HSIAO M. S. "A Fast, Accurate, and Non statistical Method for Fault Coverage Estimation", Department of Electrical and Computer Engineering, Rutgers University, Piscataway, NJ. Inernational Conf. on Computer-Aided Design, pp. 155- 161. 1998.

45. ARRA О. H., SAHNI S. К. "Polynomially Complete Fault Detection Problems", IEEE Trans, on Computers, vol. С 24, pp. 242 - 249, March 1975.

46. KEIM M., BECKER В., STENNER B. "On the (non-)resettability of synchronous sequential circuits". In Proceedings of the IEEE VLSI Test Symposium, 240 245. April 1996.

47. KIRKLAND Т., MERCER M. R. "A topological search algorithm for ATPG". In Proceedings of the 24th ACM/IEEE Design Automation Conference, 502 508. June 1987.

48. KOHAVI I., LAVELLEE P. "Design of sequential machines with fault -tolerant capabilities", IEEE Trans, on Computers, Vol. EC 16, pp. 473 -484, Aug. 1967.

49. KUBO H. "A procedure for generating test sequences to detect sequential circuit failures", NEC Research 85 Development, No. 12, pp. 69-78, Oct. 1968.

50. RRABEE, T. "Test pattern generation using Boolean satisfability". IEEE Trans, on Сотр. Aided Design 11, pp. 4—15, January 1992.

51. LEE D. H., REDDY S. M. "A new test generation method for sequential circuits". In Proceedings of the IEEE International Conference on Computer Aided Design (ICCAD - 91), 446 - 449, Nov. 1991.

52. LEE H. К., HA D. S. "On the generation of test patterns for combinational circuits". Technical Report #12 — 93, Department of Electrical Engineering, Virginia Polytechnic Institute and State University. 1993.

53. LEE J., PATEL J. H. "A signal driven discrete relaxation technique for architectural level test generation". In Proceedings of the IEEE International Conference on Computer — Aided Design, 458 — 461. Nov. 1991.

54. LEE J., PATEL J. H. "Architectural level test generation for microprocessors". IEEE Trans. CAD, 13, 10, 1288 1300. Oct. 1994.

55. LOT H. Y., SU С. C. "A Distributive D Algorithm for Generating the Test Pattern for Faulty Combinational Circuit", Int. J. Electronics, vol. 66, no. l,pp. 35-42, 1989.

56. MARCHOK Т. E., EL MALEH A., MALY W., RAJSKI J. "Complexity of sequential ATPG". In Proceedings of the European Design and Test Conference, IEEE Computer Society Press, 252 — 261. March 1995.

57. MARLETT R. A. "EBT, a comprehensive test generation technique for highly sequential circuits", 15th Design Automation Conference, Las Vegas, USA, pp. 332 339, June 1978.

58. MARTIN R. L. "The design of diagnosable sequential machines", Proc. Hawaii Int'l Conf. Syst. Sci., 1968.

59. MICZO A. "Digital Logic Testing and Simulation", Harper and Row, New York. 1986.

60. MOORE E. F. "Gedanken — experiments on sequential machines", Automota Studies, Princeton University Press, pp. 129 153, Princeton, NJ 1965.г

61. MUTH P. "A nine valued circuits model for test generation", IEEE Transactions on Computers, Vol. С - 25, n. 6, pp. 630 - 636, June 1976.

62. NELDER J. A., MEAD R. "A simplex method for function minimization", The Computer Journal, 7, pp. 308 313. 1965.

63. NIERMANN Т., PATEL J. H. "HITEC: A Test Generation Package for Sequential Circuits", European Design Autom. Conf., pp. 214 218, 1991.

64. NIERMANN Т., PATEL J. H. "HITEC: A test generation package for sequential circuits". In Proceedings of the European Design Automation Conference, 214-218. Feb. 1991.

65. PATIL S., "Parallel algorithms for test generation and fault simulation", University of Illinois at Urbana Champaign, 1991.

66. PIXLEY C. "A computational theory and implementation of sequential hardware equivalence". In DIMACS Tech. Rep. 90-31. In Workshop on Computer Aided Verification, vol. 2. AMS, Providence, R. I. 293 — 320. 1990.

67. PIXLEY C., BEIHL G. "Calculating resettability and reset sequences". In Proceedings of the IEEE International Conference on Aided Design, 376-379. Nov. 1991.

68. POAGE J. F. MCCLUSKEY E. J. "Derivation of optimum Kst sequences for sequential machines", Proc. 5th Symp. on Switching Theory and Logical Design, 1964.

69. POMERANZ I., REDDY S. M., "Classification of Faults in Synchronous Sequential Circuits", IEEE Trans, on Computers, vol. 42, pp. 1066-1077, Sept. 1993.

70. PRADHAN D. K. "Sequential Network Design using Extra Inputs for Fault Detection", IEEE Trans, on Computers, Vol. С 32, No. 3, pp. 319 -323, March 1983.

71. PRATT V., "Anatomy of the Pentium Bug", Dept. of Computer Science, Stanford University, Stanford, CA, June 11, 1995.

72. PRINETTO P., REBAUDENGO M., REORDA M. S. "An automatic test pattern generator for large sequential circuits based on genetic algorithm". In Proceedings of the IEEE International Test Conference, 240-249. Oct. 1994.

73. PUTZOLU G. R., ROTH J. P. "A heuristic algorithm for the testing of asynchronous circuits", IEEE Transactions on Computers, vol С — 20, n. 6, pp. 639-647, June 1971.

74. PUTZOLU G. R., ROTH J. P. "A heuristic algorithm for the testing of asynchronous circuits". IEEE Trans. Comput. С — 20, 639 647, June 1971.

75. RHO J., SOMENZI F., PIXLEY C. "Minimum length synchronizing sequences of finite state machines". In Proceedings of the ACM/IEEE Design Automation Conference, 463 468. June 1993.

76. ROSENBROCK H. H. "An automatic method for finding the greatest or least value of a function", The Computer Journal, 3, pp. 175 — 184. 1960.

77. ROTH J. P. "Diagnosis of automata failures: A calculus and a method". IBM Journal, Res. Dev. 10, 278 291. July 1966.

78. RUDNICK E. M., HOLM J. G., SAAB D. G., PATEL J. H. "Application of simple genetic algorithms to sequential circuit test generation". In Proceedings of the European Design and Test Conference, 40 — 45. March 1994.

79. SAAB D. G., SAAB Y. G., ABRAHAM J. A. "CRIS: A test cultivation program for sequential VLSI circuits". In Proceedings of the IEEE International Conference on Computer Aided Design, 216 — 219. Nov. 1992.

80. SABNANI K., DAHBURA A. "A protocol test generation procedure". Comput. Netw. 15, 285 297. April 1988.

81. SALUJA К. K., DANDAPANI R. "Testable design for single output sequential machines using checking experiments", IEEE Trans, on Сотр. Vol. С - 35, No. 7, pp. 658 - 662, July 1986.

82. SANGIOVANNI VINCENTELLI A., MA H. К. Т., DEVADAS S., NEWTON A. R., "Test generation for sequential circuit". IEEE Trans. Comput. Aided Des., 1081 - 1093. Oct. 1988.

83. SCHULZ M. H., AUTH E. "ESSENTIAL: An efficient self learning test pattern generation algorithm for sequential circuits". In Proceedings of the International Test Conference, 28 - 37. Aug. 1989.

84. SCHULZ M. H., TRISCHLER E., SARFERT Т. M. "SOCRATES: A highly efficient automatic test pattern generation system". IEEE Trans. CAD, 126-137. Jan. 1988.

85. SESHU S. "On an improved diagnosis program". IEEE Trans. Electron. Comput. EC 14, 2, 76 - 79. Feb. 1965.

86. SESHU S., FREEMAN D. N. "The diagnosis of asynchronous sequential switching systems", IRE Trans. Electron. Comput, vol. EC —11, pp. 459 — 465, Aug. 1962.

87. SILVA J. P. M., SAKALLAH K. A. "Dynamic search space pruning techniques in path sensitization". In Proc. of Design Automation Conf. pp. 705-711. 1994.

88. SNETHEN T. J. "Simulator oriented fault test generator". In Proceedings of the 14th ACM/IEEE Design Automation Conference, 88 -93. June 1977.

89. SO B. "Time Efficient Automatic Test Pattern Generation Systems", Ph. D. thesis, University Of Wisconsin — Madison, 1994.

90. SPENDLEY W., HEXT G. R., HIMSWORTH F. R. "Sequential application of simplex designs in optimisation and evolutionary operation", Technometrics, 4, pp. 441 461. 1962.

91. SRIVAS M. K., STEVEN P. M., "Applying Formal Verification to a Commercial Microprocessor", Computer Science Laboratory SRI International, Menlo Park, CA 94025 USA, 1994.

92. STOFFEL D., "Formal Verification of Sequential Circuits Using Reasoning Techniques", University'at Frankfurt at Main, 1999.

93. TERAMOTO M. "A method for reducing the search space in test pattern generation". In Proc. of Int. Test Conf. 429 435. 1993.

94. VENKARTRAMAN C. S., SALUJA К. K. "Transition count testing of sequential machines", Dig. 10th Symp. Fault Tolerant Comput., pp. 167 172, Kyoto, Japan, Oct. 1980.9V 9-valued, 9-ти-значная логика.

95. DAC Design and Automation Conference, Конференция поразработке и автоматизации.

96. DFF D flip-flop, D-триггер.

97. ЕВТ Extended Back Trace, алгоритм расширенной трассировки вобратном направлении.

98. FAN Fanout-Oriented Test Generation, алгоритм генерации тестов,ориентированный на обработку разветвлений.1С Integrated circuit, интегральная схема.

99. CAS International Symposium on Circuits and Systems,международный симпозиум по схемам и системам.

100. C International Test Conference, международная конференцияпо тестированию.

101. NP Nondeterministic polynomial time, недетерминированный вполиномиальное время.

102. PI Primary input, первичный вход.

103. РО Primary output, первичный выход.

104. PODEM Path oriented decision making, алгоритм принятия решений на основе анализа путей.

105. PPI Pseudo primary input, псевдопервичный вход.

106. РРО Pseudo primary output, псевдопервичный выход.

107. RTP Reverse time processing, обработка времени в обратномпорядке следования времени.

108. SCOAP Sandia controllability/observability analysis program, программа анализа контролируемости и наблюдаемости, разработанная в институте Sandia.

109. SECONT Sequential Test Generator based on Continuous approach, последовательностный генератор тестов, основанный на непрерывном подходе.

110. SOCRATES Structure-Oriented, Cost-Reducing Automatic test pattern generation system, структурированная, оптимизирующая система автоматической генерации тестов.

111. SOFTG Simulator-Oriented Fault Test Generator, генератор тестов для неисправностей, основанный на моделировании.

112. НГТУ Нижегородский Государственный Технический1. Университет.

113. ОКН Модель одиночных константных неисправностей.