Abstract:
The present invention is for a method and apparatus for analyzing the effect of a plurality of noise sources in a circuit, wherein each one of the noise sources is associated with a discrete stochastic process defined on a state-set of Markov chains. Each discrete stochastic process is modulated with a set of continuous signals that represents the noise generated by the corresponding noise source at each noise generating event. A spectral power density of the signals resulting from the modulation is computed and transferred through a linear system that represents a platform that supports the circuit. The output of the linear system comprises the spectral power density of interference signals at the points of interest and their correlations.

Description:
FIELD OF THE INVENTION 
     This invention relates to circuit analysis, and more particularly to evaluating the effect of interference noise generated by switching elements at points of interest in a circuit comprised of both digital and analog components. 
     BACKGROUND OF THE INVENTION 
     Increasing numbers of circuit components are built on the same silicon substrate. Inevitably, some of the circuit components include sensitive analog and RF circuits, the performance which can be significantly degraded by the presence of interference signals. In a circuit comprised of both digital and analog components implemented on the same silicon substrate, the switching of the digital gates constitutes a significant source of interference noise, which propagate through, for example, the power supply grid, the silicon substratum signal wires and package pins. 
     Most of conventional analysis tools use traces from logic simulation to model the switching activity of digital gates. For example, a conventional method uses an inverter chain to model the digital switching activity. The digital signals are converted to time domain, and transient simulation is used to obtain the time-domain interference signal at points of interest. Another conventional approach has been to use logic simulation together with cell-library characterization. The individual contributions are combined at the output node into a long time-domain waveform. The corresponding power spectrum is estimated from this long time-domain waveform using standard techniques. 
     The conventional methods suffer from significant drawbacks. First, important features of the power spectrum are lost when spectral estimation is performed on time-domain sequences. Another disadvantage is the difficulty of incorporating nontrivial effects from the substrate and the power-ground grid. The substrate is assumed to be purely resistive, and the parasitics of the on-chip digital power-ground grid are usually ignored. 
     SUMMARY 
     We have developed in accordance with the principles of the invention a method and apparatus for analyzing noise generated by switching elements in a circuit comprised of digital and analog components, wherein each switching element is associated with a random and discrete sequence of switching events having a plurality of possible values. Each one of the random and discrete sequences is modulated at each switching event with a set of continuous signals that represents the actual current injected by the corresponding switching element into the circuit. A spectral power density of the signals resulting from the modulation is transferred through a linear system that models the ensemble of power and ground wires, the substrate, the IC package, and the circuit board. The output of the linear system comprises the spectral power density of the interference signals at the points of interest. 
    
    
     BRIEF DESCRIPTION OF THE DRAWING 
     FIG. 1 shows an exemplary illustration of how the present invention analogizes the propagation of interference noise from switching elements to modulation in digital communication. 
     FIG. 2 shows a model of a linear circuit. 
     FIG. 3 shows a general flowchart of the process for evaluating a plurality of noise sources in a circuit. 
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     The present invention uses modulated stochastic switching activity propagation (MSSAP) to analyze the effect of the interference noise generated by millions of switching gates at points of interest in an IC. The points of interest will generally be certain critical nodes that host sensitive analog circuitry. 
     The present invention performs a frequency domain based anualysis and outputs a power spectral density of the interference signals at the points of interest to help engineers in making system and circuit design decisions. The present invention uses the following approximations to analyze the effect of such interference: 
     (a) the contribution of each switching gate is treated as ideal sources that model the currents injected or sinked from the power grid and substrate as the gate switches; 
     (b) the switching pattern of each gate is modeled as a stochastic process that approximates the gate&#39;s switching statistics; 
     (c) the ensemble of power, ground  22 , transistor substrate  24 , IC package  26 , and board  28  is treated as a linear circuit  21 , and is modeled using conventional extraction tools, as shown in FIG.  2 . 
     These approximations reduce the problem of evaluating the effect of millions of switching gates at points of interest as a problem of evaluating stochastic processes, as they propagate through a linear system. The quantity of interest is the spectral power density S yy (ƒ) of the interference signals at the points of interest. S yy (ƒ) is a matrix, wherein the quantities on the matrix diagonal represent the spectral power density of the interference signal at each point of interest. The off-diagonal quantities represent correlations between the interference signals. S yy (ƒ) is a function of the input cross-spectral power density matrix S xx (ƒ) and the linear system&#39;s transfer function H(j2pƒ) defined as S yy (ƒ)=H(j2pƒ)S xx (ƒ)H*(j2pƒ), where the superscript * denotes the complex conjugation of H. 
     The input cross-spectral power density matrix S xx (ƒ) is a square matrix that contains signal statistics for all interference sources. The size of the matrix is proportional to the number of the switching gates. The diagonal matrix-elements represent the spectrum of interference noise generated by each switching gate, and the off-diagonal elements represent correlations between the gates. Strong correlations tend to be localized within the same logic function. Thus, in general, S xx  will be mainly block-diagonal with relatively small blocks. 
     The matrix-transfer function H(j2pƒ) models the ensemble of power, ground  22 , substrate  24 , package  26 , and board  28  as a multi-input and multi-output linear system. The number of inputs is equal to the number of interference sources. The number of outputs is equal to the number of the points of interest. The input cross-spectral power density matrix S xx (ƒ) is obtained using modulation theory. Each switching gate is associated with a random, discrete, four valued signal, c[n], that models its transitions: high-high, high-low, low-high, and low-low. Each of the four possible values of c[n]  11  is assigned with a different set of continuous waveforms g c[n] (t)  12 ,  13 ,  14  and  15  representing the actual currents that the gate injects into the power, ground and substrate system during the corresponding transition. At each switching event, c[n] is modulated with the corresponding set of continuous waveforms g c[n] (t)  12 ,  13 ,  14  and  15 . The result of the modulation x(t)  16  represents the continuous signals injected by a switching gate into the ensemble of power, ground  22 , transistor substrate  24 , IC package  26  and board  28 , where x(t) is defined as x(t)=? n=−8   8  g c[n] (t−nT) and T represents the clock period. 
     FIG.  1  and FIG. 3 show how the present invention analogizes the problem of solving the effect of interference noise generated by millions of switching gates to modulation in digital communications. In a signal propagation channel  10 , an encoded signal c(n),  11 , is transmitted. C[n] has four possible values, and depending on the value of c[n], one set of continuous waveforms,  12 ,  13 ,  14  or  15 , is used to modulate c(n)  11 , at step  110 . At Steps  115  and  120 , the modulation x(t)  16  is output and the output of the modulation x(t),  16 , propagates through channel  17 , which represents the ensemble of the power, ground  22 , transistor substrate  24 , IC package  26  and board  28 . The output of channel  17  is the interference signal y(t),  18  which is output at Step  125 . 
     At step  105 , the random signal c[n]  11  is modeled by functions defined on the state-set of Markov chains (MCs). The MC is characterized by a state set Z={s 1  . . . , s l } and a 1×1 state transition probability matrix (TPM) P. The digital transition signal is defined as a function h: Z→{LL, LH, HL, HH} represented by a 1×1 column vector d={h(s 1 ) . . . , h(s l )} T . For example, for a 2-input NAND gate and a 2-input NOR gate that share the same digital input signals A and B, the outputs of the NAND and NOR gates are digital signals C and D, respectively. 
     The digital input signals A and B are modeled as {0, 1)}-valued stochastic processes d A [n] and d B [n] defined as functions on two statistically independent, two-state MCs z A [n] and z B [n] with state sets Z A ={s A1 , s A2 } and Z B ={S B1 , S B2 }, respectively, having the following TPMs:                P   A     =                [           1   -     a   A             a   A           ]                              [           b   A           1   -     b   A             ]                           P   B     =                [           1   -     a   B             a   B           ]                              [           b   B           1   -     b   B             ]                                  
     where a A  represents the probability of the digital signal A will switch from low to high, and b A  represents the probability of the digital signal A will switch from high to low. Similarly, a B  and b B  represent the probabilities that the digital signal B will switch from low to high, and high to low, respectively. 
     The digital output signals C and D are modeled as stochastic processes d C [n] and d D [n]. A four-state MC z CD [n] with the state Set Z CD ={s CD1 , s CD2 , s CD3 , s CD4 }={{s A1 , s B1 }; {s A1 , s B2 }, {s A2 , s B1 }, {s A2 , s B2 }} having TPM P CD =P A (x)P B  where (x) denotes the Kronecker product for matrices, define d C[n] and d   D [n] as follows: 
     
       
           d   C   =h   C ( Z   CD )=[1,1,1,0 ] d   D   =b   D ( Z   CD )=[1,0,0,0]. 
       
     
     The input stochastic processes d A [n] and d B [n] can be defined as functions on the four-state MC z CD [n] as follows: 
     
       
           d   e   A   =h   e   A ( Z   CD )=[0,0,1,1]  d   e   B   =h   e   B ( Z   CD )=[0,1,0,1] 
       
     
     where the superscript “e” stands for “expanded” to differentiate the functions and vectors on the four-sate chain from the ones that were defined on the 2-state MCs. Accordingly. the outputs of the NAND and NOR gates represented as vectors d C [n] and d D [n] are functions of d c   A  and d e   B , wherein d C =NOT ((d e   A  AND d c   B )), d D =NOT ((d e   A  OR d c   B )), and where AND and OR operate on the vectors d C [n] and d D [n] element-wise. Thus, the four-state MC z CD [N] along with the functions d e   A  and d e   B  and d C [n] and d D [n] represent the inputs and the outputs of the logic circuit comprised of the NAND and the NOR gate. 
     Correlations between digital signals A, B, C, and D are represented as they are modeled on the same underlying MC. Specifically, the output of the NAND gate and the NOR gate are correlated if the signal at the output of the NOR gate has value 1 during a clock interval, the NAND gate output has to be also 1. The foregoing example can be generalized for an arbitrary combinational circuit having any number of inputs and outputs. All signals of any such combinational circuit can he represented on a MC obtained from the MCs of the primary inputs. This modeling process captures both the individual switching statistics of all signals and their correlations. 
     The sizes of the vectors that define the digital signals and the TPMs that define the MCs grow exponentially with the number of inputs to a logic circuit. The vectors and matrices are efficiently manipulated exploiting their special structure and efficient data structures similar to binary decision diagrams (BDDs). Typically, each switching event in the random sequence c[n]  11  is associated with noise source signals, such as injection current patterns for the power, ground, and substrate. In a cell-based design environment the injection patterns are determined off-line and are stored in parameterized form during the library characterization procedure. The injection-current waveforms stored in the library are time-referenced from the clock transition time. 
     At step  110 , the continuous-time stochastic process x(t)  16  models the signal injected by a switching gate and the discrete-time stochastic process, c|n|  11 , takes values in Q={LL, LH, HL, HH} such that for every digital signal, there is a set of four injection waveforms g LL (t), g LH (t), g HL (t) and g HH (t). For example, for M switching gates x 1 (t), . . . , x M (t) associated with M discrete stochastic processes c l (n), . . . , c M (n), all of which are modeled as functions on the same MC with the state set Z={s 1 , . . , s 1 }, the digital transition signal h m : Z→Q={LL, LH, HL, HH}, m=1, . . . , M defines c m [n], m=1, . . . , M on the MC. 
     For a complete spectral characterization, S xx  is computed for the M×1 vector stochastic process, x(t)−{x 1 (t), . . . , x M (t)} T , where the function g m (t:S j ) and a corresponding M×1 matrix function g(t) are defined, respectively, as follows:              g   m          (     t        :          s   i       )       =         g   m     bM        (     σ                 i     )              (   t   )                     where       ,     m   =   1     ,   …              ,   M   ,       and                 i     =   1     ,   …              ,   1   ,   and                   g        (   t   )       =                [             g   1          (     t        :          s   1       )               g   1          (     t        :          s   2       )           …           g   1          (     t        :          s   1       )             ]                              [             g   2          (     t        :          s   1       )               g   2          (     t        :          s   2       )           …           g   2          (     t        :          s   1       )             ]                              [   …   ]                              [   …   ]                              [   …   ]                                [             g   m          (     t        :          s   1       )               g   m          (     t        :          s   2       )           …           g   m          (     t        :          s   1       )             ]     .                                  
     The spectral density matrix of x(t)  16  is defined as S xx (ƒ)=(1/T)G*(ƒ)W ss (e j2pfT )G T (ƒ) where the superscript * denotes the complex conjugation of G, the M×1 matrix function G(ƒ) is the Fourier transform of the M×1 matrix function g(t), and W ss(e   j2pfT ) is the z-transform of an autocorrelation matrix R ss [k] that characterizes the discrete stochastic process c[n] as follows:                    R   ss          [   k   ]       =                {     ?     P   k                                if                 k     =   0                              {         (     P   t     )       -   k       ?                              if                 k     &lt;   0                                       
     where ? is a diagonal matrix with the stationary probabilities of the MC as entries, and the index k represents discretized time. 
     The z-transform is based on the eigendecomposition of P. TPMs always have one eigenvalue equal to 1 and all the other eigenvalues having magnitudes less than or equal to 1. Eigenvalues of magnitude 1 result in δ-functions in the spectrum W ss (e j2pfT ) and correspond to pure tones such that the spectral density matrix S xx (ƒ) consists of continuous and discrete components defined as follows: 
     
       
           S   xx (ƒ)= S   c   xx (ƒ)+? k δ(ƒ−ƒ d   k ) S   d   xxk . 
       
     
     The discrete spectral component reflects the fact that the interference signals are triggered by discrete events that occur at periodic clock intervals. The continuous spectral component results from the randomness of these events. 
     The present invention requires computing the propagation of a large number of stochastic processes through a complex linear system. The number of matrix solutions, however, is determined only by the number of the points of interest, and does not depend of the number of switching noise sources. In fact, the computation for spectral power density at the points of interest is similar to the circuit noise analysis problem. Efficient analysis methods based on the adjoint system and reduced-order modeling are employed for propagating the spectral densities of the switching gates through the linear system that models the ensemble of power, ground  22 , transistor substrate  24 , IC package  26 , and board  28 . 
     The present invention requires delimiting the boundary of a switching gate. Every noise signal generated by a switching gate is to be accounted for only once. The contribution of a switching gate is accounted for by modeling the following signals: 
     (a) the current flowing into the V dd  metal supply wire; 
     (b) the current flowing into the ground  22  supply wire; 
     (c) the current flowing into the p-type transistor substrate  24 ; 
     (d) the current flowing into the n-type transistor substrate  24 ; and 
     (e) the output voltage waveform. 
     The output voltage waveform is characterized for each transition, and is used together with extracted interconnect models to determine the currents that flow into the power grid through interconnect wires. In general, currents that flow directly into the substrate are about two orders of magnitude smaller than the currents flowing into the power lines. Thus, in most cases, they can be neglected altogether. In certain applications, however, correct modeling of substrate effect becomes very important, and may constitute the ultimate limitation in isolating the sensitive circuits. 
     Numerous modifications to and alternative embodiments of the present invention will be apparent to those skilled in the art in view of the foregoing description. Accordingly, this description is to be construed as illustrative only and is for the purpose of teaching those skilled in the art the best mode of carrying out the invention. Details of the embodiment may be varied without departing from the spirit of the invention, and the exclusive use of all modifications which come within the scope of the appended claims is reserved.