FAN algorithm

FAN algorithm (FAN-out oriented 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, Japan.[1] 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 heuristics such as unique sensitization and multiple back tracing.[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][4] and many conference papers such as ACM/IEEE Design Automation Conference, et al.[5]

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

  1. ^ a b Fujiwara, Hideo; Shimono, Takeshi (December 1983). "On the acceleration of test generation algorithm". IEEE Transactions on Computers. C-32 (12): 1137–1144. doi:10.1109/TC.1983.1676174. S2CID 9547677.
  2. ^ Fujiwara, Hideo (September 1985). Logic Testing and Design for Testability. MIT Press. ISBN 9780262561990.
  3. ^ Abramovici, Miron; Breuer, Melvin A.; Friedman, Arthur D. (1990). Digital Systems Testing and Testable Design. IEEE Press. ISBN 9780780310629.
  4. ^ Niraj, Jha; Gupta, Sandeep (2003). Testing of Digital Systems. Cambridge University Press. ISBN 0521773563.
  5. ^ Kirkland, Tom; Mercer, M. Ray (1987). "A topological search algorithm for ATPG". 24th ACM/IEEE conference proceedings on Design automation conference - DAC '87. pp. 502–508. doi:10.1145/37888.37963. ISBN 0818607815.

Content Disclaimer

Informasi ini disarikan dari Wikipedia dan disajikan kembali untuk tujuan edukasi. Konten tersedia di bawah lisensi CC BY-SA 3.0. Kami tidak bertanggung jawab atas ketidakakuratan data yang bersumber dari kontribusi publik tersebut.

  1. The information displayed on this website is sourced in part or in whole from Wikipedia and has been adapted for the purpose of restating it. We strive to provide accurate and relevant information, however:
  2. There is no guarantee of absolute accuracy. Wikipedia is an open, collaborative project that can be edited by anyone, so information is subject to change.
  3. It is not intended to constitute professional advice. The content displayed is for informational and educational purposes only. For important decisions (e.g., medical, legal, or financial), please consult a professional.
  4. Content copyright. Wikipedia is licensed under the Creative Commons Attribution-ShareAlike License (CC BY-SA). This means that content may be reused with appropriate attribution and shared under a similar license.
  5. Responsible use. Any risk arising from the use of information from this website is entirely the responsibility of the user.