Evolutionary Algorithms of Test Generation for Crosstalk Faults of Digital Circuits

Skobtsov Y.A. (Saint Petersburg State University of Aerospace Instrumentation)
Abstract - Technological progress leads to density increasing on chip, rising number of crossings in conductive layers and speeding-up time frequency. As a result – model of classical stuck-at faults is not enough effective and adequate because the analysis of physical defects affected on time parameters of a circuit is need. Especially it is typical for deep submicron (DSM) designing. In the paper there was considered some approach to pulse-induced crosstalk faults test generation. Besides it was considered some approach to multiple aggressor crosstalk faults test generation. It is considered two basic types of crosstalk faults: crosstalk induced pulses; crosstalk induced delays. Under test generation for crosstalk faults it is necessary: find out input patterns, which cause required signal transient on aggressor line; find out input patterns guaranteeing necessary static signal on victim line and propagating arisen pulse from victim line to primary outputs. The solution of both problems is based on multi-valued logic and genetic algorithm application. At that the genetic algorithm provides a mechanism of random direct search of test patterns pairs, which satisfy noted conditions. To our point of view, application of evolutionary methods in test generation for considered faults is more justified then for classical stuck-at faults. It is necessary to note that genetic algorithms allow reduce synthesis problem to analysis problem (in some sense). Under condition of analysis tools presence (fault-free or faulty circuit simulators) genetic algorithms provide direct random search for synthesis problem solution.To evaluate fitness-function value results of logical simulation in multi-valued alphabet is used [1]. In this way we define new detected faults for given input pattern pair (potential solution). It was shown for combinational digital circuits that application of genetic algorithms and multivalued event-driven simulation in C8 alphabet allows effectively solve test generation problem for crosstalk faults and gives high fault coverage.

Keywords - test generation, crosstalk faults, genetic algorithm, multivalued modeling, fault simulation

Эволюционные алгоритмы построения проверяющих тестов для перекрестных неисправностей цифровых схем

Скобцов Ю.А. (Санкт-Петербургский государственный университет аэрокосмического приборостроения, г. Санкт-Петербург)
Аннотация - Рассмотрены основные модели перекрестных неисправностей (crosstalk faults): индуцированные положительные и отрицательные импульсы, индуцированные задержки. Получил развитие метод моделирования перекрестных неисправностей в 9-значном алфавите. На этой основе разработан генетический алгоритм построения проверяющих тестов для одиночных перекрестных неисправностей. Рассмотрена задача генерации проверяющего теста для неисправности индуцированная задержка Предложен генетический алгоритм построения проверяющих тестов для неисправности индуцированная задержка со многими линиями-агрессорами.

Ключевые слова - генерация тестов, перекрестные неисправности, генетический алгоритм, многозначная логика, моделирование неисправностей.