A Graph Partitioning Approach to Optimize Test Patterns

Digital devices in modern world are reducing towards Nano scale, also density of Integrated Circuit is increasing which makes it difficult for testing. Modern digital devices are equipped with in built testing. In test mode of operation, these devices consume more power compared to normal mode of operation. In order to reduce test power consumption, proper ordering of input test patterns are mandatory. In this work, a new test pattern ordering method is proposed based on travelling salesman problem. Initially test patterns are generated using Automatic Test Pattern Generator. Hamming Distance among these test patterns are minimized by applying Kernighan Lin algorithm. Overall circuit switching activity reduction is achieved with test patterns having minimal hamming distance. Similarly, Prim’s algorithm is applied to test patterns and results of both algorithms are compared. The proposed test pattern ordering algorithm is implemented in ISCAS’89 Benchmark sequential circuits. Experimental results proves that switching activity reduction using prim’s algorithm is better compared to Kernighan Lin algorithm. For a hardware realization of benchmark circuit, a PCB Board is designed for s27 benchmark circuit along with a clock generator using NE555 timer IC.