FANアルゴリズム
(FAN-out oriented test generation algorithm から転送)
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/12/04 13:43 UTC 版)
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アルゴリズムは、開発時点では最も早く探索を行えるアルゴリズムであった。
脚注
注釈
- ^ ATPGは一般にNP完全であり、大規模な集積回路では全探索は現実的ではないため、可能な限り効率的に検査を行いカバレッジを高める必要があるためである。
- ^ 時間当たりの探索量が変化しないまま探索範囲だけが増大したことで、検査時間の増加を招いた。
- ^ ATPGでは、回路に仮に割り当てた値が整合性が取れないなどの矛盾を引き起こすことがある。このような時に、この矛盾を引き起こした決定の直前まで戻り、矛盾を引き起こした決定と違う決定を行うことをバックトラックという。
出典
- ^ a b c 藤原秀雄『ディジタルシステムの設計とテスト』工学図書株式会社、2004年。ISBN 4769204590。
- ^ 日経クロステック（xTECH） (2009年1月13日). “ATPG | 日経クロステック（xTECH）”. xtech.nikkei.com. 2025年11月28日閲覧。
参考文献
- 藤原秀雄（英語）『FAN: A FANOUT-ORIENTED TEST PATTERN GENERATION ALGORITHM』（PDF）。2025年11月28日閲覧。
- 藤原秀雄; 下野武志「On the Acceleration of Test Generation Algorithms」（英語）『IEEE Transactions on Computers』C-32巻、第12号、1983年12月31日。doi:10.1109/TC.1983.1676174。
ISSN 1557-9956。2025年11月28日閲覧。(
要登録) - 藤原秀雄『テスト生成アルゴリズム』1992年5月。
- FANアルゴリズムのページへのリンク
