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