FANアルゴリズム

FANアルゴリズム（英: FAN-out oriented test generation algorithm）は、組合せ回路を対象とした自動テストパターン生成（ATPG）のアルゴリズムの一種である。1983年に藤原秀雄らによって考案された^[1]。 テスト生成アルゴリズムの高速化のためには、バックトラックの発生回数の削減と、バックトラック間の処理の高速化が必要であり、FANアルゴリズムは、種々の発見的技法（ヒューリスティック）を採用することにより、バックトラックの発生回数を大幅に減らすことに成功した。バックトラックの発生を減らすために、先頭信号線と分岐点でのみバックトラックが発生するように制限し、また様々な手法を駆使することで高速化を実現した^[1]。

背景

→「自動テストパターン生成」も参照

集積回路の良品と不良品の選別に用いられる半導体試験装置の核となる、試験用の入力信号（テストパターン）を自動的に生成する技術である自動テストパターン生成のアルゴリズムは、集積回路の全探索を行うDアルゴリズムや、探索範囲を狭め高速化したPODEMアルゴリズムなど様々な手法が提案されてきた^{[2][注釈 1]}。

しかし、1980年代になると、大規模集積回路（VLSI）が登場し、既存のアルゴリズムでは対応が難しくなり^{[注釈 2]}新たな手法の開発が行われた。それがFANアルゴリズムである。

概説

FANアルゴリズムは、一意活性化（英: Unique Sensitization）や多重後方追跡（英: Multiple Backtrace）などの新しい手法を取り入れることでバックトラック^{[注釈 3]}を削減し、探索時間を削減した^[1]。FANアルゴリズムは、開発時点では最も早く探索を行えるアルゴリズムであった。