evolutionary algorithms, digital circuit design, test compaction problem, set coverage problem, test generation, greedy algorithm, optimization, don't care value, Electrical engineering. Electronics. Nuclear engineering, TK1-9971, Computer engineering. Computer hardware, TK7885-7895

The test compaction is one of most important requirement regarding the large scale integration (LSI) testing. The overall cost of a VLSI circuit's testing depends on the length of its test sequence; therefore the reduction of this sequence, keeping the coverage of error prone points, will lead to a reduction of used resources in the testing process. This problem is NP-complete. Consequently an optimal algorithm doesn't have applicability in practice. In this paper we describe an evolutionary algorithm (GATC) and we introduce the term of compaction factor (cf), i.e. the "expected" percentage of compacted test sequence. GATC provides in praxis better results than a greedy approach (GR) for many configurations. This improvement comes from the freedom to merge randomly pairs of compatible tests for different candidates to solution and keeps the ones with more "Don't care" positions, thus there is an increased probability to find for them compatible tests in the next stage. Also the C++ implementation was optimized, using compact data structures and the Standard Template Library.