FAN algorithm
 | This article, FAN algorithm, has recently been created via the Articles for creation process. Please check to see if the reviewer has accidentally left this template after accepting the draft and take appropriate action as necessary.
Reviewer tools: Inform author |
| This article, FAN algorithm, has recently been created via the Articles for creation process. Please check to see if the reviewer has accidentally left this template after accepting the draft and take appropriate action as necessary.
Reviewer tools: Inform author |
FAN algorithm is an algorithm for automatic test pattern generation (ATPG). It was invented in 1983 by Fujiwara et al.,[1] which was the fastest ATPG algorithm at that time and was adopted by industry. The FAN algorithm succeeded in reducing the number of backtracks by adopting new heuristics such as unique sensitization and multiple backtracing.[1] 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[2][3] and many conference papers such as ACM/IEEE Design Automation Conference, et al.[4].
Implementations
- Atalanta : An automatic test pattern generator implementing the FAN algorithm.
- FanWorks : A visual circuit simulator including the ATPG mode by using the FAN algorithm.
References
- ^ a b Fujiwara, Hideo; Shimono, Takeshi (December 1983). "On the acceleration of test generation algorithm". IEEE Trans. on Computers. C-32 (12): 1137–1144. doi:10.1109/TC.1983.1676174.
- ^ Fujiwara, Hideo (September 1985). Logic Testing and Design for Testability. MIT Press. ISBN 9780262561990.
- ^ Abramovici, Miron; Breuer, Melvin A.; Friedman, Arthur D. (1990). Digital Systems Testing and Testable Design. IEEE Press. ISBN 9780780310629.
- ^ Kirkland, Tom; Mercer, M. Ray (1987). "A topological search algorithm for ATPG". 24th ACM/IEEE Design Automation Conference: 502–508. doi:10.1145/37888.37963.