FANアルゴリズム()は、組合せ回路を対象とした自動テストパターン生成(ATPG)のアルゴリズムの一種である。1983年に藤原秀雄らによって考案された。 テスト生成アルゴリズムの高速化のためには、バックトラックの発生回数の削減と、バックトラック間の処理の高速化が必要であり、FANアルゴリズムは、種々の発見的技法(ヒューリスティック)を採用することにより、バックトラックの発生回数を大幅に減らすことに成功した。バックトラックの発生を減らすために、先頭信号線と分岐点でのみバックトラックが発生するように制限し、また様々な手法を駆使することで高速化を実現した。
背景
集積回路の良品と不良品の選別に用いられる半導体試験装置の核となる、試験用の入力信号(テストパターン)を自動的に生成する技術である自動テストパターン生成のアルゴリズムは、集積回路の全探索を行うDアルゴリズムや、探索範囲を狭め高速化したPODEMアルゴリズムなど様々な手法が提案されてきたATPGは一般にNP完全であり、大規模な集積回路では全探索は現実的ではないため、可能な限り効率的に検査を行いカバレッジを高める必要があるためである。。
しかし、1980年代になると、大規模集積回路(VLSI)が登場し、既存のアルゴリズムでは対応が難しくなり時間当たりの探索量が変化しないまま探索範囲だけが増大したことで、検査時間の増加を招いた。新たな手法の開発が行われた。それがFANアルゴリズムである。
概説 FANアルゴリズムは、一意活性化()や多重後方追跡()などの新しい手法を取り入れることでバックトラックATPGでは、回路に仮に割り当てた値が整合性が取れないなどの矛盾を引き起こすことがある。このような時に、この矛盾を引き起こした決定の直前まで戻り、矛盾を引き起こした決定と違う決定を行うことをバックトラックという。を削減し、探索時間を削減した。FANアルゴリズムは、開発時点では最も早く探索を行えるアルゴリズムであった。
脚注
注釈
出典
参考文献