Stochastic oscillations in circuit simulation

We consider the simulation of noisy electronic circuits with oscillatory solutions. For their transient noise simulation we use variable step-size two-step schemes for stochastic differential-algebraic equations. The performance of these methods in combination with a suitable step-size control strategy is illustrated by an industrial test application. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

On circuit generating processes

Two Markov processes that give rise to common directed circuits occurring along almost all their sample paths are called circuit generating processes . We here study the existence of such processes together with certain features that are common stochastic properties for both processes (as communication relation ,recurrent-transient behaviour)     

The circuit basis in binary matroids

The concept of a circuit basis for a matroid is introduced, as an algorithmically rapid way of determining several characteristics of a given matroid. It is used to give a short search for planarity in graphs, and also to begin the answer to a question of G.-C. Rota about “dependency among dependencies.” A circuit basis for a matroid is a least set of circuits which will generate all the circuits of the matroid by repeated use of symmetric differences of cells.     

Broken circuit complexes and hyperplane arrangements

We study Stanley–Reisner ideals of broken circuit complexes and characterize those ones admitting linear resolutions or being complete intersections. These results will then be used to characterize hyperplane arrangements whose Orlik–Terao ideal has the same properties. As an application, we improve a result of Wilf on upper bounds for the coefficients of the chromatic polynomial of a maximal planar graph. We also show that for a matroid with a complete intersection broken circuit complex, the supersolvability of the matroid is equivalent to the Koszulness of its Orlik–Solomon algebra.     

Shorter signed circuit covers of graphs

A signed circuit is a minimal signed graph (with respect to inclusion) that admits a nowhere-zero flow. We show that each flow-admissible signed graph on edges can be covered by signed circuits of total length at most , improving a recent result of Cheng et al. To obtain this improvement, we prove several results on signed circuit covers of trees of Eulerian graphs, which are connected signed graphs such that removing all bridges results in a collection of Eulerian graphs.     

A characterisation of rigid circuit graphs

Let G_n be a graph of n vertices, having chromatic number r which contains no complete graph of r vertices. Then G_n contains a vertex of degree not exceeding n(3r?7)/(3r?4). The result is essentially best possible.     

Semidefinite programming and arithmetic circuit evaluation

We address the exact semidefinite programming feasibility problem (SDFP) consisting in checking that intersection of the cone of positive semidefinite matrices and some affine subspace of matrices with rational entries is not empty. SDFP is a convex programming problem and is often considered as tractable since some of its approximate versions can be efficiently solved, e.g. by the ellipsoid algorithm.We prove that SDFP can decide comparison of numbers represented by the arithmetic circuits, i.e. circuits that use standard arithmetical operations as gates. Our reduction may give evidence to the intrinsic difficulty of SDFP (contrary to the common expectations) and clarify the complexity status of the exact SDP—an old open problem in the field of mathematical programming.     

Time domain analog circuit simulation

Recent developments of new methods for simulating electric circuits are described. Emphasis is put on methods that fit existing datastructures for backward differentiation formulae methods. These methods can be modified to apply to hierarchically organized datastructures, which allows for efficient simulation of large designs of circuits in the electronics industry.     

Minimization of circuit registers: Retiming revisited

We address the following problem: given a synchronous digital circuit, is it possible to construct a new circuit computing the same function as the original one but using a minimal number of registers? We show that the minimal number of registers is the size of the minimal cut on a bi-infinite graph, namely the unfolding of the dependencies in the digital circuit. Furthermore, the construction of such a cut and the corresponding circuit can be done in polynomial time, using a max-flow min-cut result of Orlin for one-periodic bi-infinite graphs. Finally, we show the relation between this construction and the retiming technique introduced by Leiserson and Saxe.     

Integrated circuit design: dealing with variations

In the following, a practicable methodology to analyze and optimize the yield of an electronic circuit, i.e. the percentage of manufactured circuits that satisfy the circuit specification, is formulated. It is based on a “spec-wise” partitioning of the problem by considering each circuit specification bound individually, and on a geometric yield approximation. EDA tools following the described approach are available meanwhile. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Graphs with exactly one hamiltonian circuit

Let h(n) be the largest integer such that there exists a graph with n vertices having exactly one Hamiltonian circuit and exactly h(n) edges. We prove that h(n) = [n²/4]+1 (n ≧ 4) and discuss some related problems.     

Random number generation using a chaotic circuit

Summary A simple method to generate pseudorandom numbers is presented. The basic part of the circuit consists of two identical nonautonomous chaotic oscillators, which are driven by an external clock signal. The well-known chaotic circuits are extremely simple, as they are composed only of an inductor and a capacitance diode, and thus it is easy to get the generator to work reliably. The output of the oscillators is discretized by a comparator, and these signals are mixed together using a D flip-flop. The distribution, the spectrum, the return map, and the autocorrelation of random numbers obtained by this circuit are shown. We have studied the system also using the correlation integral method and the local prediction technique. The results of these analyses demonstrate that the number sequence is highly random.     

An algebraic multigrid-based algorithm for circuit clustering

Digital circuits have grown exponentially in their sizes over the past decades. To be able to automate the design of these circuits, efficient algorithms are needed. One of the challenging stages of circuit design is the physical design where the physical locations of the components of a circuit are determined. Coarsening or clustering algorithms have become popular with physical designers due to their ability to reduce circuit sizes in the intermediate design steps such that the design can be performed faster and with higher quality. In this paper, a new clustering algorithm based on the algebraic multigrid (AMG) technique is presented. In the proposed algorithm, AMG is used to assign weights to connections between cells of a circuit and find cells that are best suited to become the initial cells for clusters, seed cells. The seed cells and the weights between them and the other cells are then used to cluster the cells of a circuit. The analysis of the proposed algorithm proves linear-time complexity, O(N), where N is the number of pins in a circuit. The numerical experiments demonstrate that AMG-based clustering can achieve high quality clusters and improve circuit placement designs with low computational cost.