背景介紹

Combinational ATPG是一個Branch and Bound的演算法，它的本質是在組合電路（Combinational Circuit）內找到適合的輸入向量（Input Vector）工具。所有輸入訊號的可能組合形成輸入空間（Input Space）。這個輸入空間的大小主要和組合電路內Primary Inputs的數量有關，它會形成一個二元樹（Binary Tree），每個節點（Node）有兩個分支（Branch），節點上的符號代表輸入訊號的代號，假定左邊的分支代表該Node輸入值為0，右邊的分支代表該Node輸入值為1。ATPG用DFS（Depth First Search）可以在輸入空間內找到一條路徑（Tour），當所有輸入訊號（Input）的值依照這條路徑輸入進去電路設計的時候，能夠滿足某個我們想觀察的性質（Property）。

由於輸入空間這個二元樹的節點數量太大，需要一個更有效率的資料結構才能夠在有限的記憶體空間內表示它；另外一方面人們也致力於發展如何縮小這個輸入空間以及更聰明的尋訪該輸入空間的方法。
...
...