Formal verification of analog and mixed signal circuits using deductive and bounded approaches
This thesis presents novel formal verification techniques to verify the important property of inevitability of states in analog and mixed signal (AMS) circuits. Two techniques to verify the inevitability of phase locking in a Charge Pump Phase Lock Loop (PLL) circuit are presented: mixed deductivebounded and deductive-only verification approaches. The deductive-bounded approach uses Lyapunov-like certificates with bounded advection of sets to verify the inevitability of phase locking. The deductive-only technique uses a combination of Lyapunov and Escape certificates to verify the inevitability property. Both deductive-only and deductive-bounded verification approaches involve positivity/negativity checks of polynomials over semi-algebraic sets, which both belong to the NP-hard set of problems. The Sum of Squares (SOS) programming technique is used to transform the positivity tests of polynomials to the feasibility of semi-definite programs. The efficacy of the approach is demonstrated by verifying the inevitability of phase locking for a third and fourth order CP PLL. Similarly, the inevitability of oscillation in ring oscillators (ROs) is verified using a numeric-symbolic deductive approach. The global inevitability (of oscillation) property is specified as a conjunction of several sub-properties that are verified via different Lyapunov-like certificates in different subsets of the state space. The construction of these certificates is posed as the verification of First Order Formulas (FOFs) having Universal-Existential quantifiers. A tractable numeric-symbolic approach, based on SOS programming and Quantifier Elimination (QE), is used to verify these FOFs. The approach is applied to the verification of inevitability of oscillation in ROs with odd and even topologies. Furthermore, frequency domain properties specification and verification for analog oscillators is presented. The behaviour of an oscillator in the frequency domain is specified, while it operates in close proximity to the desired limit cycle, employing finite Fourier series representation of a periodic signal. To be sufficiently robust enough against parameter variations, robustness of parameters is introduced in these specifications. These frequency domain properties are verified using a mixed time-frequency domain technique based on Satisfiability Modulo Ordinary Differential Equation (SMODE). The efficacy of the technique is demonstrated for the benchmark voltage controlled and tunnel diode oscillators.
TK Electrical engineering. Electronics Nuclear engineering
Networked Digital Library of Theses and Dissertations