Sequential automatic test pattern generation (ATPG) is important for functional testing of ASICs or custom hardware. It is required in cases where the circuit cannot be full-scanned due to performance limitations or when true at-speed testing is necessary which scan based methods either cannot provide or do so with considerable overheads.

Since sequential ATPG algorithms at the logic level are NP-hard and thus extremely expensive in terms of time and computing resources, they mostly do not succeed even for circuits containing a few hundred latches. Performing the test generation at higher levels of design abstraction provides for several advantages. Since the number of primitive elements at the higher level is usually lesser than the logic level, the problem size is reduced leading to a reduction in the test generation time over logic-level ATPG. Also a reduction in the number of backtracks can lead to improved fault coverage and reduced test application time over logic-level techniques.

This talk will focus on an industrial effort to generate sequential test patterns automatically from functional register transfer level (RTL) circuits that target detection of stuck-at faults in the circuit at the logic level. The RTL circuit is assumed to be described in some high level description language (HDL) like VHDL or Verilog which is currently a standard practice in industrial ASIC designs. Currently only block level circuits of the order of tens of thousands of HDL lines are targeted.

The algorithm works by first converting the RTL circuit into a data structure named assignment decision diagram (ADD) which has been proposed previously in the field of high level synthesis. Then an unique 10-valued algebra is utilized to model the ATPG algorithm on the ADD. A branch and bound search procedure is then utilized to perform the ATPG. The ATPG algorithm first generates a test environment for each RTL objective, which may include variable assignments, conditional statements, and arithmetic expressions in the HDL description. A test environment for a given validation objective is a set of symbolic conditions that allow for full controllability and observability of that objective. After the RTL ATPG terminates, a back-end translator intelligently translates the test environments into validation vectors by filling in the necessary values. Several smart heuristics are used to improve the efficiency