FAN algorithm: Difference between revisions

Revision as of 12:00, 16 June 2022

Latest revision as of 14:09, 7 June 2024

(15 intermediate revisions by 8 users not shown)

Line 1:

'''FAN algorithm''' is an algorithm for [[Automatic test pattern generation|automatic test pattern generation (ATPG)]]. It was invented in 1983 by [[Hideo Fujiwara]] etand al.[[Takeshi Shimono]] at the Department of Electronic Engineering, [[Osaka University]], Japan.<ref name="FAN Algorithm">{{Cite journal | last1 = Fujiwara | first1 = Hideo | last2 = Shimono | first2 = Takeshi | title = On the acceleration of test generation algorithm | doi = 10.1109/TC.1983.1676174 | journal = IEEE Trans.Transactions on Computers | volume = C-32 | issue = 12 | pages = 1137-11441137–1144 | date = December 1983| s2cid = 9547677 }}</ref> whichIt 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 heuristics[[heuristic]]s such as unique sensitization and multiple backtracingback tracing.<ref name="FAN Algorithm"/>

{{Draft topics|computing}}

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<ref>{{Cite book | last1 = Fujiwara | first1 = Hideo | title = Logic Testing and Design for Testability | isbn = 9780262561990 | publisher = MIT Press | date = September 1985}}</ref><ref>{{Cite book | last1 = Abramovici | first1 = Miron | first2 = Melvin A. | last2 = Breuer | first3 = Arthur D. | last3 = Friedman | title = Digital Systems Testing and Testable Design | publisher = IEEE Press | date = 1990 | isbn = 9780780310629}}</ref><ref>{{Cite book | last1 = Niraj | first1 = Jha | first2 = Sandeep | last2 = Gupta | title = Testing of Digital Systems | publisher = Cambridge University Press | date = 2003 | isbn = 0521773563}}</ref> and many conference papers such as ACM/IEEE Design Automation Conference, et al.<ref>{{Cite book | first1 = Tom | last1 = Kirkland | first2 = M. Ray | last2 = Mercer | title = 24th ACM/IEEE conference proceedings on Design automation conference - DAC '87 | chapter = A topological search algorithm for ATPG | pages = 502–508 | date = 1987 | doi = 10.1145/37888.37963| isbn = 0818607815 | doi-access = free }}</ref>

{{AfC topic|stem}}

{{AfC submission|||ts=20220616112831|u=Kfakt|ns=118}}

{{AfC submission|t||ts=20220616112440|u=Kfakt|ns=118|demo=}}<!-- Important, do not remove this line before article has been created. -->

== Implementations ==

'''FAN algorithm''' is an algorithm for [[Automatic test pattern generation|automatic test pattern generation (ATPG)]]. It was invented in 1983 by Fujiwara et al.,<ref name="FAN Algorithm">{{Cite journal | last1 = Fujiwara | first1 = Hideo | last2 = Shimono | first2 = Takeshi | title = On the acceleration of test generation algorithm | doi = 10.1109/TC.1983.1676174 | journal = IEEE Trans. on Computers | volume = C-32 | issue = 12 | pages = 1137-1144 | date = December 1983}}</ref> 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.<ref name="FAN Algorithm"/>

* [https://github.com/hsluoyz/Atalanta Atalanta] : An automatic test pattern generator implementing the FAN algorithm.

* [http://apps.fujiwaralab.net/fanworks/index-e.html FanWorks] : A visual circuit simulator including the ATPG mode by using the FAN algorithm.

== References ==

{{reflist}}

[[:Category:Electronic circuit verification]]