基于優(yōu)化ATPG的可測試性設計與實現(xiàn).pdf

1、自動測試模式產生(Automatic Test Pattern Generation:ATPG)技術在針對芯片制造缺陷的生產測試中得到廣泛應用。ATPG作為測試向量的生成工具，它能根據輸入的故障模型，生成簡潔、高覆蓋率的測試向量(Test Vectors)。
　　但是傳統(tǒng)的基于結構化搜索的ATPG算法，如果要提高測試故障覆蓋率，需要對電路進行大量的試探性的反復回溯搜索，這樣就要耗費大量冗余時間，使得測試成本非常昂貴。而本文提出基于

2、代數公式的二叉判決圖和布爾可滿足性SAT這兩種算法能有效壓縮測試時間，它通過將門級電路模塊轉化為數學邏輯，用求解命題邏輯的代數問題，來達到快速遍歷的目的，這樣既能解決冗余回溯搜索的時間過長問題，又能提高覆蓋率。
　　但對于單純基于布爾可滿足性SAT的算法，由于是以整個變量空間的回溯搜索為基本框架，所以搜索空間很大，時間復雜度較高，會導致算法超時。因為搜索空間越大，就需要越多的回溯搜索時間，特別是對于未知的故障時間將更長。而那些只基

3、于二叉判決圖BDD的算法又在構造二叉判決圖BDD時可能導致內存溢出等棘手問題，為改善上述缺陷，本文又提出一種不同于遍歷式搜索的啟發(fā)式策略，用增量的方法盡早識別出不可測故障，節(jié)省不必要的搜索判定時間。這種二叉判決圖BDD與可滿足性SAT相混合的一種代數方法，采用布爾差分方程的思想，有效發(fā)揮BDD和SAT的各自在時間和空間上的優(yōu)勢，在結點數上做閥值判斷，做啟發(fā)式策略進行算法的互相切換、替代運行。同時避免了在設計BDD時會出現(xiàn)的內存溢出問題和

4、SAT算法超時問題。
　　本研究采用BDD算法的工具開發(fā)包CUDD和SAT操作的工具包Zchaff，編寫了C++語言代碼在基準電路上實現(xiàn)了上述混合算法的仿真驗證和應用分析，通過和其他算法的數據對比，發(fā)現(xiàn)這種使用智能啟發(fā)式策略的混合算法比傳統(tǒng)的搜索算法或者單一的SAT算法在測試運行時間、回溯次數、故障傳遞路徑、內存占有率上性能都有大幅提升，還能提高ATPG工具生成向量的效率。
　　通過該算法在TetraMAX工具平臺上的實踐驗