TAO: Regular expression based high-level testability analysis and optimization

In this paper, we present TAO, a novel methodology for high-level testability analysis and optimization of register-transfer level controller/data path circuits. Unlike existing high-level testing techniques that cater restrictively to certain classes of circuits or design styles, TAO exploits the algebra of regular expressions to provide a unified framework for handling a wide variety of circuits including application-specific integrated circuits, application-specific programmable processors, application-specific instruction processors, digital signal processors and microprocessors. We also augment TAO with a design-for-test framework that can provide a low-cost testability solution by examining the trade-offs in choosing from a diverse array of testability modifications like partial scan or test multiplexer insertion in different parts of the circuit. Test generation is symbolic and, hence, independent of bit-width. Experimental results on benchmark circuits show that TAO is very efficient, in addition to being comprehensive. The fault coverage obtained is above 99% in all cases. The average area and delay overheads for incorporating testability into the benchmarks are only 3.3% and 1.1%, respectively. The test application time is comparable to that associated with gate-level sequential test generators.