Method and apparatus for evaluating effects of switching noise in digital and analog circuitry

[0002] 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.

[0003] 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.

[0004] 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.

[0005] 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.

[0006] 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.

[0007] 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.

[0008] FIG. 2 shows a model of a linear circuit.

[0009] FIG. 3 shows a general flowchart of the process for evaluating a plurality of noise sources in a circuit.

[0010] 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.

[0011] 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:

[0012] (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;

[0013] (b) the switching pattern of each gate is modeled as a stochastic process that approximates the gate's switching statistics;

[0014] (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.

[0015] 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's transfer function H(j2p𝑓) defined as S_yy(𝑓)=H(j2p𝑓)S_xx(𝑓)H*(j2p𝑓), where the superscript * denotes the complex conjugation of H.

[0016] 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_xxwill be mainly block-diagonal with relatively small blocks.

[0017] 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⁸g^c[n](t−nT) and T represents the clock period.

[0018] 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.

[0019] 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₁. . . , 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₁) . . . , 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.

[0020] 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: $\begin{array}{c}{P}_A=\left[\begin{array}{cc}1-a_A& a_A\end{array}\right]\\ \left[\begin{array}{cc}{b}_A& 1-b_A\end{array}\right]\end{array}$ $\begin{array}{c}{P}_B=\left[\begin{array}{cc}1-a_B& a_B\end{array}\right]\\ \left[\begin{array}{cc}{b}_B& 1-b_B\end{array}\right]\end{array}$

[0021] where a_Arepresents the probability of the digital signal A will switch from low to high, and b_Arepresents the probability of the digital signal A will switch from high to low. Similarly, a_Band b_Brepresent the probabilities that the digital signal B will switch from low to high, and high to low, respectively.

[0022] 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_Bwhere (x) denotes the Kronecker product for matrices, define d_{C[n] and dD}[n] as follows:

[0023] d_C=h_C(Z_CD)=[1,1,1,0] d_D=b_D(Z_CD)=[1,0,0,0].

[0024] 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:

[0025] d^e_A=h^e_A(Z_CD)=[0,0,1,1] d^e_B=h^e_B(Z_CD)=[0,1,0,1]

[0026] 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_Aand d^e_B, wherein d_C=NOT ((d^e_AAND d^c_B)), d_D=NOT ((d^e_AOR 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_Aand d^e_Band 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.

[0027] 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.

[0028] 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.

[0029] 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₁(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₁, . . , s₁}, 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.

[0030] For a complete spectral characterization, S_xxis computed for the M×1 vector stochastic process, x(t)−{x₁(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\left(t\text{:}{s}_i\right)=g_m^{\mathrm{bM}\left(\sigma i\right)}\left(t\right)\mathrm{where},m=1,\dots ,M,\mathrm{and}i=1,\dots ,1,\mathrm{and}$ $\begin{array}{c}g\left(t\right)=\left[\begin{array}{cccc}{g}_1\left(t\text{:}{s}_1\right)& g_1\left(t\text{:}{s}_2\right)& \dots & g_1\left(t\text{:}{s}_1\right)\end{array}\right]\\ \left[\begin{array}{cccc}{g}_2\left(t\text{:}{s}_1\right)& g_2\left(t\text{:}{s}_2\right)& \dots & g_2\left(t\text{:}{s}_1\right)\end{array}\right]\\ \left[\dots \right]\\ \left[\dots \right]\\ \left[\dots \right]\\ \left[\begin{array}{cccc}{g}_m\left(t\text{:}{s}_1\right)& g_m\left(t\text{:}{s}_2\right)& \dots & g_m\left(t\text{:}{s}_1\right)\end{array}\right].\end{array}$

[0031] 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: $\begin{array}{cc}{R}_{\mathrm{ss}}\left[k\right]=\{?P^k& \mathrm{if}k=0\\ \{{\left(P^t\right)}^{-k}?& \mathrm{if}k<0\end{array}$

[0032] where ? is a diagonal matrix with the stationary probabilities of the MC as entries, and the index k represents discretized time.

[0033] 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:

[0034] S_xx(𝑓)=S^c_xx(𝑓)+?_kδ(𝑓−𝑓^d_k)S^d_xxk.

[0035] 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.

[0036] 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.

[0037] 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:

[0038] (a) the current flowing into the V_ddmetal supply wire;

[0039] (b) the current flowing into the ground 22 supply wire;

[0040] (c) the current flowing into the p-type transistor substrate 24;

[0041] (d) the current flowing into the n-type transistor substrate 24; and

[0042] (e) the output voltage waveform.

[0043] 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.

[0044] 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.