The Testing Analysis of Cyclic Combinational Circuits and its Application on SAT-based Test Generation

迴路化組合電路之測試分析及其滿足性基礎之測試型樣產生之應用

陳亮元(Chen, Liang Yuan)

指導教授 ： 王俊堯

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

摘要

邏輯電路可分做兩類：組合(combinational)電路與循序(sequential)電路。然而，組合電路是可以被迴路化的。而迴路化組合電路為含有迴圈的組合電路。換言之，在迴路化組合電路內部的值皆為固定且穩態。目前已有一些探討迴路化組合電路於合成方面的研究，迴路化的組合電路具備降低面積及時間的優點。然而，在電路測試方面，相對於非迴路化組合電路，迴路化組合電路更為複雜且較少被探討。這篇論文分析迴路化組合電路上的測試問題，並且提出以滿足性為基礎的自動測試型樣產生(satisfiability-based automatic test pattern generation)。實驗結果顯示我們所提出的方法對於迴路化組合電路可達高的錯誤涵蓋率。

關鍵字

迴路化組合電路

並列摘要

Logic circuits are classified into two categories: combinational circuits and sequential ones. However, combinational circuits could be cyclic, and cyclic combinational circuits are combinational circuits with feedback loops. That is, all the values in the cyclic combinational circuits are still fixed. Recently, some works have focused on the synthesis of cyclic combinational circuits such that the cyclic version of a combinational circuit can be available if it exists. Cyclified combinational circuits could take advantages of reducing area and timing. However, its testing problem is more complex than acyclic combinational circuits, and is still seldom discussed. In this work, we analyze the testing issue of cyclic combinational circuits and propose satisfiability-based automatic test pattern generation. The experimental results show that the proposed method can reach a high fault coverage for a set of cyclic combinational circuits.

並列關鍵字

cyclic combinational circuit

參考文獻

[2] G. S. Tseitin, “On the complexity of derivation in propositional calculus,” Au- tomation of Reasoning. Springer. pp. 466-483, 1983.

[3] J.-H. Chen, Y.-C. Chen, W.-C. Weng, C.-Y. Huang, and C.-Y. Wang, “Synthesis and verification of cyclic combinational circuits,” 2015 IEEE International SOC Conference, pp. 257-262, September 2015.

[4] L. Hellerman, “A catalog of three-variable or-invert and and-invert logical circuits,” IEEE Trans. Electronic Computers., vol. EC-12, no. 3, pp. 198-223, 1963.

[5] M. D. Riedel and J. Bruck, “The synthesis of cyclic combinational circuits,” in Proc. Design Automation Conference, pp. 163-168, 2003.

[7] M. D. Riedel and J. Bruck, “Timing analysis of cyclic combinational circuits,” in Proc. International Workshop on Logic and Synthesis, pp. 69-77, 2004.