FAN algorithm is an algorithm for
automatic test pattern generation (ATPG). It was invented in 1983 by
Hideo Fujiwara and
Takeshi Shimono at the Department of Electronic Engineering,
Osaka University
The , abbreviated as UOsaka or , is a List of national universities in Japan, national research university in Osaka, Japan. The university traces its roots back to Edo period, Edo-era institutions Tekijuku (1838) and KaitokudÅ, Kaitokudo (1724), ...
, Japan.
It was the fastest ATPG algorithm at that time and was subsequently adopted by industry. The FAN algorithm succeeded in reducing the number of backtracks by adopting new
heuristic
A heuristic or heuristic technique (''problem solving'', '' mental shortcut'', ''rule of thumb'') is any approach to problem solving that employs a pragmatic method that is not fully optimized, perfected, or rationalized, but is nevertheless ...
s such as unique sensitization and multiple back tracing.
Unique sensitization is to determine as many signal values as possible that can be uniquely implied. Multiple backtracing is concurrent backtracing of more than one path, which is more efficient than backtracing along a single path. In order to reduce the number of backtracks, it is important to find the nonexistence of the solution as soon as possible. When we find that there exists no solution we should backtrack immediately to avoid the subsequent unnecessary search. These heuristics can lead to the early detection of inconsistency and decrease the number of backtracks. FAN algorithm has been introduced in several books and many conference papers such as ACM/IEEE Design Automation Conference, et al.
Implementations
Atalanta: An automatic test pattern generator implementing the FAN algorithm.
: A visual circuit simulator including the ATPG mode by using the FAN algorithm.
References
{{reflist
Electronic circuit verification