以模擬為基礎之組合電路冗餘線路識別器

A Simulation-based Redundancy Identification in Combinational Circuits

黃意元(Yi-Yuan Huang)

指導教授 ： 王俊堯

國立清華大學/電機資訊學院/資訊工程學系/碩士(2007年)

https://doi.org/10.6843/NTHU.2007.00449

摘要

冗餘線路的移除在組合電路的最佳化中是重要的一環。傳統的冗餘線路辨別的演算法是建立在自動測試圖樣產生之上。然而，自動測試圖樣產生系統需要耗費大量的時間去確定一個錯誤是不可測試的，即此錯誤是冗餘的。一條線路要確定是冗餘的並非那麼容易，然而，要確定它不是冗餘的卻是容易的多。在這篇論文中，我們提出了一個有效率的冗餘線路識別器以至於非冗餘的線路可輕易得被辨別出來。實驗結果顯示我們所提出的方法對於大部份的測試電路可辨別出全部的非冗餘線路。

關鍵字

冗餘線路 ； 組合電路 ； 最佳化

並列摘要

Redundancy removal is an important operation in combinational logic optimization. Traditional redundancy identification algorithms are based on automatic test pattern generation algorithms. However, automatic test pattern generation algorithms spend much CPU time to determine if a fault on a wire is untestable, and thus redundant. To determine if a wire is redundant is not easy, however, to determine if a wire is irredundant is much easier. In this thesis, we present an efficient redundancy identifier such that irredundant wires can be easily filtered out. The experimental results show that the presented method can identify all irredundant wires in most benchmark circuits.

並列關鍵字

redundant ； combinational circuit ； optimization

參考文獻

[1] M. Abramovici, P. R. Menon, and D. T. Miller, “Critical Path Tracing—An Alternative

to Fault Simulation,”in Proc. 20th Design Automation Conf., pp. 214–220, June 1983.

[2] V. D. Agrawal and S. C. Seth, Test Generation for VLSI Chips, IEEE Computer Society Press, 1988.

[3] D. B. Armstrong,“A Deductive Method for Simulating Faults in Logic Circuits,”IEEE Trans. on Computers, vol. C-21, no. 5, pp. 464–471, May 1972.

[4] K. J. Antreich and M. H. Schulz,“Accelerated Fault Simulation and Fault Grading in Combinational Circuits,”IEEE Trans. on Computer-Aided Design., vol. CAD-6, no. 5, Sep. 1987.