ComputingComputer ScienceElectrical EngineeringAlgorithmsAnalog ElectronicsDiagrammingAnalog DesignCircuit ComplexityComputational ComplexityDesign For TestabilitySmall-signal AnalysisAnalog TestabilityCircuit Matrix AnalysisCpu OptimizationSymbolic AnalysisSymbolic ComputationTestabilityTestability Engineering
Symbolic analog-circuit analysis has many applications, and is especially useful for analog synthesis and testability analysis. We present a new approach to exact and canonical symbolic analysis by exploiting the sparsity and sharing of product terms. It consists of representing the symbolic determinant of a circuit matrix by a graph-called determinant decision diagram (DDD)-and performing symbolic analysis by graph manipulations. We showed that DDD construction and DDD-based symbolic analysis can be performed in time complexity proportional to the number of DDD vertices. We described a vertex ordering heuristic, and showed that the number of DDD vertices can be quite small-usually orders-of-magnitude less than the number of product terms. The algorithm has been implemented. An order-of-magnitude improvement in both CPU time and memory usage over existing symbolic analyzers ISAAC and Maple-V has been observed for large analog circuits.
17
Graph-Based Algorithms for Boolean Function Manipulation
Bryant · IEEE Transactions on Computers · 1986 · 8.9K citations · Full text