Graph-Pair Decision Diagram Construction for Topological Symbolic Circuit Analysis
Graph-Pair Decision Diagram Construction for Topological Symbolic Circuit Analysis
复制标题
拓扑符号电路分析的图对决策图构建
DOI：
10.1109/tcad.2012.2217963
复制
发表时间：
2013-02
影响因子：
2.9
通讯作者：
Shi, Guoyong
中科院分区：
文献类型：
--
作者：
Shi, Guoyong
符号电路分析涉及电路响应在频域（或时域）的解析构造，为此需要一种有效的数据结构。近年来的研究证明，二进制决策图是一种优越的数据结构，具有以下特点：大量的乘积项可以用二进制决策图紧凑地表示，可以直接在其上进行数值计算和分析推导。使用BDD进行符号电路分析需要一种有效的构造方法。本文提出了一种基于图的决策图构建方法——图对决策图（GPDD）。给定一个小信号电路，创建一对表示该电路的图，然后通过依次约简图对来构造GPDD。GPDD算法与现有的行列式决策图（DDD）算法不同，它产生不相互抵消的符号项。提出了GPDD构建的详细理论和可实现算法，并与DDD进行了运行时性能比较。尽管GPDD算法必须生成大量的符号乘积项，但在精确符号分析的时间和内存复杂度方面，使用GPDD的运行时性能与DDD相当。
Symbolic circuit analysis is concerned with analytical construction of circuit response in the frequency (or time) domain, for which an efficient data structure is required. Recent research has justified that the binary decision diagram (BDD) is a superior data structure with the following distinguishing feature: a large number of product terms can be compactly represented by a BDD, on which numerical computations and analytical deductions can be performed directly. Using BDD for symbolic circuit analysis requires an efficient method for construction. In this paper, a graph-based construction method, called graph-pair decision diagram (GPDD), is developed. Given a small-signal circuit, a pair of graphs representing the circuit is created, from which a GPDD is constructed by successively reducing the graph pair. The GPDD algorithm, which generates cancellation-free symbolic terms, differs from the existing determinant decision diagram (DDD) algorithm. Detailed theory and implementable algorithms for the GPDD construction are developed, and a runtime performance comparison to DDD is made. It is demonstrated that the runtime performance using GPDD is comparable to that of DDD in terms of time and memory complexity for exact symbolic analysis, although the GPDD algorithm has to generate a much larger number of symbolic product terms.
登录
查看更多内容
DOI：
10.1049/ep.1978.0296
发表时间：
1993
期刊：
--
影响因子：
--
作者：
P. Gray;R. Meyer
通讯作者：
P. Gray;R. Meyer
DOI：
10.1109/mwscas.2011.6026581
发表时间：
2011-09
期刊：
2011 IEEE 54th International Midwest Symposium on Circuits and Systems (MWSCAS)
影响因子：
--
作者：
He Zhang;G. Shi
通讯作者：
He Zhang;G. Shi
影响因子：
5.1
作者：
W. Daems;Wim Verhaegen;P. Wambacq;G. Gielen;W. Sansen
通讯作者：
W. Daems;Wim Verhaegen;P. Wambacq;G. Gielen;W. Sansen
DOI：
10.1109/tct.1965.1082385
发表时间：
1965-03
期刊：
IEEE Transactions on Circuit Theory
影响因子：
--
作者：
G. Minty
通讯作者：
G. Minty
DOI：
10.1109/aspdac.2007.357985
发表时间：
2007-01
期刊：
2007 Asia and South Pacific Design Automation Conference
影响因子：
--
作者：
G. Shi;Weiwei Chen;C. Shi
通讯作者：
G. Shi;Weiwei Chen;C. Shi