FAN algorithm

Uses your system voice; voice and rate in settings.

Snapshot

≈ 3 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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. 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. 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.

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. 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. 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.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1354400290 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-001354400290 · captured 1778900764.0 · version history

Cite this page as: encyclopegia.org, “FAN algorithm”, snapshot enwiki-001354400290. https://encyclopegia.org/a/fan-algorithm

Sources cited in this revision

No external citation was extracted for this revision. That is a statement about the source, not a claim that none exists.