Apparatus and method for analyzing circuits using reduced-order modeling of large linear subcircuits

• US 6,023,573 A
• Filed: 01/29/1999
• Issued: 02/08/2000
• Est. Priority Date: 09/01/1998
• Status: Expired due to Term

• Current Assignee: Bell Semiconductor, LLC (Hilco Inc. (d/b/a Hilco Global))
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Freund, Roland W., Bai, Zhaojun, Feldmann, Peter
• Primary Examiner(s): Teska, Kevin J.
• Assistant Examiner(s): GARBOWSKI, LEIGH M
• Application Number:
  US09/240,432
• Time in Patent Office: 375 Days
• Field of Search: 395/500.23, 395/500.34, 395/500.05, 395/500.03
• US Class Current: 703/2
• CPC Class Codes: G06F 30/367 Design verification, e.g. using simulation, simulation program with integrated circuit emphasis [SPICE], direct methods or relaxation methods

Abstract

A method and apparatus for generating and analyzing reduced-order models of linear circuits. The method and apparatus generates a characteristic tridiagonal matrix using a look-ahead Lanczos procedure and then checks the matrix for stability and passivity. If the matrix is not stable and passive, the matrix is modified via a partial Pade via Lanczos approximation algorithm and then rechecked for passivity and stability. The process is iterated until a passive and stable model is generated. When a satisfactory matrix is generated, a Pade approximant of a transfer function of the circuit is computed and the frequency response of this circuit is generated and displayed.

Claims

1. An apparatus for generating a frequency response signal of a circuit, comprising:

a processing unit having;

a first program for generating, from circuit characteristic data, a block tridiagonal matrix relating to said circuit characteristic data;

a second program for determining if said block tridiagonal matrix is stable and passive;

a third program for modifying said block tridiagonal matrix to make it stable and passive, if said block tridiagonal matrix is not stable and passive;

a fourth program for generating a frequency response signal as a function of said stable and passive block tridiagonal matrix or modified block tridiagonal matrix; and

an output device for displaying said circuit frequency response signal.

2. An apparatus as set forth in claim 1 wherein said second program comprises a program for generating eigenvalues and eigenvectors of said tridiagonal matrix.

3. An apparatus as set forth in claim 2 wherein said third program comprises a program for determining a vector that can be added to a last column of said tridiagonal matrix that will make said matrix passive and stable and adds said vector to said last column to generate said modified block tridiagonal matrix.

4. An apparatus as set forth in claim 3 wherein said third program further comprises a program for determining eigenvalues and eigenvectors of said modified block tridiagonal matrix and determining if said modified block tridiagonal matrix is passive and stable.

5. An apparatus as set forth in claim 4 further comprising a program for running said third program repeatedly to further modify said modified block tridiagonal matrix, if said modified block tridiagonal matrix is not passive and stable.

6. An apparatus as set forth in claim 5 wherein said fourth program determines a transfer function of said block tridiagonal matrix or modified block tridiagonal matrix by calculating poles, zeros and residues from said eigenvalues and eigenvectors to generate a Pade approximant of a transfer function of said circuit.

7. An apparatus as set forth in claim 6 wherein said first program comprises a program for processing said circuit characteristic data to obtain a characteristic matrix and a characteristic vector of said circuit, and reducing the characteristic matrix to produce said block tridiagonal matrix by a look-ahead Lanczos procedure.

8. An apparatus as set forth in claim 1 wherein said third program comprises:

a program for computing a Pade approximation of a transfer function of said block tridiagonal matrix;

a program for identifying any misplaced poles and zeros that contribute to a lack of stability or passivity of said block tridiagonal matrix;

a program for prescribing alternative locations for said identified poles and zeros;

a program for computing a partial Pade approximation of a transfer function of said block tridiagonal matrix; and

a program for checking stability and passivity of said partial Pade approximation.

9. An apparatus as set forth in claim 8 wherein said third program further comprises a program for repeating said identifying, prescribing, computing and checking programs of claim 8 upon said modified block tridiagonal matrix to further modify it, if said partial Pad6 approximation is not passive and stable.

10. An apparatus as set forth in claim 1 wherein said third program comprises:

a program for computing a row vector φ

(θ

_j) for j=1,2, . . . ,k;

a program for computing a row vector ψ

(τ

_j) for j=1,2, . . . ,l

a program for computing a last column R_k (;

,n) of a matrix;

##EQU16## a program for computing a last column Sl(;

,n-1) of a matrix;

space="preserve" listing-type="equation">S.sub.l =Υ

.sub.l ψ

.sub.l -ψ

.sub.l T'"'"'.sub.n ;

=diag(τ

.sub.j)[ψ

(τ

.sub.j)]-[ψ

(τ

.sub.j)]T'"'"'.sub.n ; and

a program for solving for x_m the equation ##EQU17## or solving for x;

##EQU18##

11. An apparatus as set forth in claim 10 wherein said second program comprises:

a program for computing eigendecompositions of T_n =S_n diag (λ

_j)S^-1_n and T'"'"'_n diag(λ

'"'"'_j) (S'"'"'_n)^-1 and obtaining approximate poles and zeros

space="preserve" listing-type="equation">p.sub.j =s.sub.0 +1/λ

.sub.j and z.sub.j =s.sub.0 +1/'"'"'.sub.j,

respectively; and

a program for checking stability and/or passivity. If the reduced-order model defined by T_n is stable and/or passive.

12. An apparatus as set forth in claim 11 wherein said third program comprises:

a program for computing eigendecompositions of

space="preserve" listing-type="equation">T.sub.n =T.sub.n +xe.sub.n.sup.T =S.sub.n diag(λ

.sub.j)S.sub.n.sup.-1

and

space="preserve" listing-type="equation">T'"'"'.sub.n =T'"'"'.sub.n +x'"'"'e.sub.n-1.sup.T =S'"'"'.sub.n diag(λ

'"'"'.sub.j)(S'"'"'.sub.n).sup.-1

and obtaining the modified approximate poles and zeros

space="preserve" listing-type="equation">p.sub.j =s.sub.0 +1/λ

.sub.j and z.sub.j =s.sub.0 +1/λ

'"'"'.sub.j.

a program for checking stability and passivity; and

a program for computing the poles and zeros and residues of the modified reduced order model

space="preserve" listing-type="equation">H.sub.n (s.sub.0 +σ

)=(l.sup.T r)e.sub.l.sup.T (I-σ

T.sub.n).sup.-1 e.sub.l.

13. An apparatus for generating a frequency response signal indicative of a frequency response of a circuit, the apparatus comprising:

a data source providing circuit characteristic data representing the circuit; and

a processing unit having;

a memory for receiving and storing the circuit characteristic data from the data source;

a first program for `generating`, from circuit characteristic data, a block tridiagonal matrix relating to said circuit characteristic data;

a second program for determining if said block tridiagonal matrix is stable and passive;

a third program for modifying said block tridiagonal matrix to make it stable and passive, if said block tridiagonal matrix is not stable and passive; and

a fourth program for generating a frequency response signal as a function of said stable and passive block tridiagonal matrix or said modified block tridiagonal matrix.

14. An apparatus as set forth in claim 13 wherein said second program comprises a program for generating eigenvalues and eigenvectors of said tridiagonal matrix.

15. An apparatus as set forth in claim 14 wherein said third program comprises a program for determining a vector that can be added to a last column of said tridiagonal matrix that will make said matrix passive and stable and a program for adding said vector to said last column to generate said modified block tridiagonal matrix.

16. An apparatus as set forth in claim 15 wherein said third program further comprises a program for determining eigenvalues and eigenvectors of said modified block tridiagonal matrix and determining if said modified block tridiagonal matrix is passive and stable.

17. An apparatus as set forth in claim 16 further comprising a program for running said third program repeatedly to further modify said modified block tridiagonal matrix, if said modified block tridiagonal matrix is not passive and stable.

18. An apparatus as set forth in claim 17 wherein said fourth program determines a transfer function of said stable and passive block tridiagonal matrix or said modified block tridiagonal matrix by calculating poles, zeros and residues from said eigenvalues and eigenvectors to generate a Pade approximant of a transfer function of said circuit.

19. An apparatus as set forth in claim 13 wherein said third program comprises:

a program for computing a Pade approximation of a transfer function of said block tridiagonal matrix;

a program for identifying any misplaced poles and zeros that contribute to a lack of stability or passivity of said block tridiagonal matrix;

a program for prescribing alternative locations for said identified poles and zeros;

a program for computing a partial Pade approximation of a transfer function of said matrix; and

a program for checking stability and passivity of said partial Pade approximation.

20. An apparatus as set forth in claim 19 wherein said third program comprises a program for repeating said identifying, prescribing, computing and checking programs set forth in claim 19 upon said modified block tridiagonal matrix to further modify it, if said partial Pade approximation is not passive and stable.

21. An apparatus as set forth in claim 13 wherein said third program comprises:

a program for computing a row vector φ

(θ

_j) for j=1,2, . . . ,k;

a program for computing a row vector ψ

(τ

_j) for j=1,2, . . . ,l

a program for computing a last column R_k (;

,n) of a matrix;

##EQU19## a program for computing a last column Sl(;

,n-1) of a matrix;

space="preserve" listing-type="equation">S.sub.l =Υ

.sub.l ψ

.sub.l -ψ

.sub.l T'"'"'.sub.n ;

=diag(τ

.sub.j)[ψ

(τ

.sub.j)]-[ψ

(τ

.sub.j)]T'"'"'.sub.n ; and

a program for solving for x_m the equation ##EQU20## or solving for x;

##EQU21##

22. An apparatus as set forth in claim 21 wherein said second program comprises:

a program for computing eigendecompositions of

T_n =S_n diag(λ

_j)S^-1_n and T'"'"'_n diag(λ

'"'"'_j)(S'"'"'_n)^-1 and obtaining approximate poles and zeros

space="preserve" listing-type="equation">p.sub.j =s.sub.0 +1/λ

.sub.j and z.sub.j =s.sub.0 +1/'"'"'.sub.j,

respectively; and

a program for checking stability and/or passivity. If the reduced-order model defined by T_n is stable and/or passive.

23. An apparatus as set forth in claim 22 wherein said third program comprises:

a program for computing eigendecompositions of

space="preserve" listing-type="equation">T.sub.n =T.sub.n +xe.sub.n.sup.T =S.sub.n diag(λ

.sub.j)S.sub.n.sup.-1

and

space="preserve" listing-type="equation">T'"'"'.sub.n =T'"'"'.sub.n +x'"'"'e.sub.n-1.sup.T =S'"'"'.sub.n diag(λ

'"'"'.sub.j)(S'"'"'.sub.n).sup.-1

and obtaining the modified approximate poles and zeros

space="preserve" listing-type="equation">p.sub.j =s.sub.0 +1/λ

.sub.j and z.sub.j =s.sub.0 +1/λ

'"'"'.sub.j.

a program for checking stability and passivity; and

a program for computing the poles and zeros and residues of the modified reduced order model

space="preserve" listing-type="equation">H.sub.n (s.sub.0 +σ

)=(l.sup.T r)e.sub.l.sup.T (I-σ

T.sub.n).sup.-1 e.sub.l.

24. A method for generating a frequency response signal of a circuit, the method comprising the steps of:

providing circuit characteristic data associated with the circuit;

generating, from circuit characteristic data, a block tridiagonal matrix relating to the circuit characteristic data;

determining if said block tridiagonal matrix is stable and passive;

modifying said block tridiagonal matrix to make it stable and passive, if said block tridiagonal matrix is not stable and passive; and

producing a frequency response signal as a function of said stable and passive block tridiagonal matrix or modified block tridiagonal matrix.

25. A method as set forth in claim 24 wherein said determining step comprises generating eigenvalues and eigenvectors of said tridiagonal matrix.

26. A method as set forth in claim 25 wherein said modifying step comprises the steps of:

determining a vector that can be added to a last column of said tridiagonal matrix that will make said matrix passive and stable; and

adding said vector to said last column to generate said modified block tridiagonal matrix.

27. A method as set forth in claim 26 wherein said modifying step further comprises;

determining eigenvalues and eigenvectors of said modified block tridiagonal matrix; and

determining if said modified block tridiagonal matrix is passive and stable.

28. A method as set forth in claim 27 further comprising the step of:

repeating said modifying step to further modify said modified block tridiagonal matrix, if said modified block tridiagonal matrix is not passive and stable.

29. A method as set forth in claim 28 wherein said producing step comprises the step of determining said transfer function by calculating poles, zeros and residues from said eigenvalues and eigenvectors to generate a Pade approximant of a transfer function of said circuit.

30. A method as set forth in claim 29 wherein said generating step comprises the steps of:

processing said circuit characteristic data to obtain a characteristic matrix and a characteristic vector of said circuit; and

reducing the characteristic matrix to produce said block tridiagonal matrix by a look-ahead Lanczos procedure.

31. A method as set forth in claim 24 wherein said modifying step comprises the steps of:

identifying any misplaced poles and zeros that contribute to a lack of stability or passivity of said block tridiagonal matrix;

prescribing alternative locations for said identified poles and zeros to generate said modified block tridiagonal matrix;

computing a partial Pade approximation of a transfer function of said modified block tridiagonal matrix; and

checking stability and passivity of said partial Pade approximation.

32. An apparatus as set forth in claim 31 wherein said modifying step further comprises repeating said identifying, prescribing, computing and checking steps set forth in claim 31 upon said modified block tridiagonal matrix to further modify it, if said partial Pade approximation is not passive and stable.

33. An apparatus as set forth in claim 24 wherein said modifying step comprises the steps of:

computing a row vector φ

(θ

_j) for j=1,2, . . . ,k;

computing a row vector ψ

(τ

_j) for j=1,2, . . . ,l

computing a last column R_k (;

,n) of a matrix;

##EQU22## computing a last column Sl(;

,n-1) of a matrix;

space="preserve" listing-type="equation">S.sub.l =Υ

.sub.l ψ

.sub.l -ψ

.sub.l T'"'"'.sub.n ;

=diag(τ

.sub.j)[ψ

(τ

.sub.j)]-[ψ

(τ

.sub.j)]T'"'"'.sub.n ; and

solving for x_m the equation ##EQU23## Or solve for x;

##EQU24##

34. An apparatus as set forth in claim 33 wherein said determining step comprises the steps of:

computing eigendecompositions of T_n =S_n diag(λ

_j)S^-1_n and T'"'"'_n diag(λ

'"'"'_j)(S'"'"'_n) and obtaining approximate poles and zeros

space="preserve" listing-type="equation">p.sub.j =s.sub.0 +1/λ

.sub.j and z.sub.j =s.sub.0 +1/'"'"'.sub.j,

respectively; and

checking stability and/or passivity; and

if the reduced-order model defined by T_n is stable and/or passive, then setting

space="preserve" listing-type="equation">T.sub.n =T.sub.n.

35. An apparatus as set forth in claim 34 wherein said modifying step comprises the steps of:

computing eigendecompositions of

space="preserve" listing-type="equation">T.sub.n =T.sub.n +xe.sub.n.sup.T =S.sub.n diag(λ

.sub.j)S.sub.n.sup.-1

and

space="preserve" listing-type="equation">T'"'"'.sub.n =T'"'"'.sub.n +x'"'"'e.sub.n-1.sup.T =S'"'"'.sub.n diag(λ

'"'"'.sub.j)(S'"'"'.sub.n).sup.-1

and obtaining modified approximate poles and zeros

space="preserve" listing-type="equation">p.sub.j =s.sub.0 +1/λ

.sub.j and z.sub.j =s.sub.0 +1/λ

'"'"'.sub.j.

checking stability and passivity; and

computing poles and zeros and residues of said modified block tridiagonal matrix

space="preserve" listing-type="equation">H.sub.n (s.sub.0 +σ

)=(l.sup.T r)e.sub.l.sup.T (I-σ

T.sub.n).sup.-1 e.sub.l.

36. An apparatus comprising:

a processing unit having;

a memory for storing circuit characteristic data representing a circuit;

a first program for generating, from circuit characteristic data, a block tridiagonal matrix relating to the circuit characteristic data;

a second program for determining if said block tridiagonal matrix is stable and passive;

a third program for modifying said block tridiagonal matrix to make it stable and passive, if said block tridiagonal matrix is not stable and passive; and

a fourth program for generating a frequency response signal as a function of said stable and passive block tridiagonal matrix or modified block tridiagonal matrix; and

an output device for displaying said circuit frequency response signal.

37. An apparatus comprising:

a memory for storing circuit characteristic data representing a circuit;

a first program for generating, from circuit characteristic data, a block tridiagonal matrix relating to the circuit characteristic data;

a second program for determining if said block tridiagonal matrix is stable and passive; and

a third program for modifying said block tridiagonal matrix to make it stable and passive, if said block tridiagonal matrix is not stable and passive;

a processor for executing the programs; and

means for generating a frequency response signal in response to the matrix transfer function data.