Sarbajit Mazumdar

Jyotishka Ray Choudhury

Partition Function : Some Properties & A New Bound on p(n)

This small project comprises of some introductory properties and topics of the partition function p(n). Actually in this project, we have tried to show a new bound on the partition function and some simplified proofs of various properties of the same.In section 6 we give a simplified proof of MacMahon's Identity's using Euler's Partition Theorem and in Section 7, we have shown an upper bound on p(n) with the help of simple algebra and basic properties of inequality. In section 8, we have shown a lower bound using the basics of Dilogarithm and Hurwitz Zeta function.

Introduction

We start by defining partitions in a few simple words.

A Partition of a positive integer n is a way of writing that integer as a sum of positive integers, where the order of the summands is considered to be irrelevant. For example, the positive integer 4 can be partitioned in exactly 5 different ways: 4, (3 + 1), (2 + 2), (2 + 1 + 1), (1 + 1 + 1 + 1).

Definition

In this section, we'll define 'Partition' again formally. A Partition of a positive integer n is a way of writing that integer as a sum of positive integers, where the order of the summands is considered to be irrelevant. The Partition Function signifies the total number of partitions of a positive integer.

The partition function of a positive integer n is denoted by p(n). So, by simple calculations, we can find that p(1) = 1, p(2) = 2, p(3) = 3, p(4) = 5, p(5) = 7, p(6) = 11 and p(7) = 11. It is to noted that p(0) is considered to be 1 conventionally though it is not a positive integer.

Throughout this article, we'll denote the number of summands in any particular partition of an integer by the term "length of partition".

There are also some formal notations which, we think, should be mentioned as we'll use these notations in our article later.

p m (n): The number of partitions of n of length no longer than m p o (n): The number of partitions of n into odd parts p d (n): The number of partitions of n into distinct parts q e (n): The number of partitions of n into an even number of distinct parts q o (n): The number of partitions of n into an odd number of distinct parts We'll follow the conventions that p m (0) = p o (0) = p d (0) = q e (n) = 1 and q o (0) = 0.

Some Quick Facts and Observations

The partition function is considered as one of the toughest number-theoretic functions.

The interesting thing about this is that the number of partitions of first few positive integers can be easily calculated, but as the value of n increases, the partition function grows very rapidly and soon, it becomes impossible to compute easily. From the early beginning of Mathematics (especially, number theory), no mathematician could find out a precise formula for p(n). In the eighteenth century, Leonhard Euler found a generating function for p(n). In 1918, Srinivasa Ramanujan, the great Indian mathematician, came up with a formula for approximating the value of p(n), which is considered as a major breakthrough in number theory. Ramanujan expressed the formula as

p(n) ≈ e c √ n 4n √ 3
where e = Euler's Number and the constant c = π 2 3 . There are many other ways to define p(n) as generating functions.

Generating Functions of p(n)

Generating functions can be used to deal with some problems involving partitions. Here we derive the generating function for the number of partitions of a positive integer n.

Consider partitioning n into addends that are equal to 1. The generating function for this is 1

• x 0 + 1 • x + 1 • x 2 + .
. . since there is only one way to represent n as the sum of 1 ′ s.

Consider partitioning numbers using just 2 ′ s as summands. There is one way to partition 0 into 2 ′ s, zero ways to partition 1 into 2 ′ s, one way to partition 2 into 2 ′ s, and so forth. Therefore, the generating function for this type of partition is 1 +

x 2 + x 4 + • • • .
We can proceed in this manner to find that the generating function for the number of ways to partition n into addends equal to k is 1 +

x k + x 2k + x 3k + • • •
Now, we generate every partition of n by choosing some number of parts to be equal to 1, some other number of parts to be equal to 2, and so on. Thus, we get the generating function for the partition function of n by multiplying the generating functions for partitions into just 1 ′ s, partitions into just 2 ′ s, and so on. This gives us the expression

(1 + x + x 2 + • • • +)(1 + x 2 + x 4 + • • • )(1 + x 3 + x 6 + • • • ) • • • = 1 + ∞ n=1 p(n).x n
Using the formula for the sum of an infinite geometric sequence we can express this in the more compact form

1 + ∞ n=1 p(n).x n = 1 1 -x • 1 1 -x 2 • 1 1 -x 3 • • • = ∞ n≥1 1 1 -x n

Theorems and Corollaries

Here we have submitted some theorems and corollaries:

(1) The number of partitions of n in which the part 1 consists minimum j times is p(nj).

Proof: Suppose we take a partition of n now if the particular partition contains at least one 1 in the summand then we just pulled it into the right hand side and we find a completely different partition of (n -1) and now similarly, if there exist at least two 1 ′ s in a partition of n the we just pulled it into the right hand side then we find a completely different partition of (n -2) and inductively, if there is j 1 ′ s then (nj) gives us a completely different partition. So we can conclude that this process only valid for those partitions in which at least one 1 occurs otherwise there is a chance of repeatation and over counting. So by inductively we can conclude that the number of 1 ′ s in the partitions of n is p(nj). An example clears it completely. Suppose p(5) := 5, 4 + 1, 2 + 2 + 1, 3 + 2, 3 + 1 + 1, 1 + 1 + 1 + 1 + 1, 2 + 1 + 1 + 1 now if we take any partition of 5 which at least contains one 1 is p(4) = 5 because we simply pulled one 1 from every partition of 5 which consists at least one 1 and we get 5 distinct partitions which is actually p(5 -1) = p(4) = 5

(2) The number of partitions of n in which 1 doesn't occur as a summand is F (n). Then we have F (n) = p(n) -p(n -1).

Proof: After proving (1) this is very easy to show. the number of partitions of n in which 1 occur at least one time is p(n -1) so the rest i.e. p(n) -p(n -1) is the number of partitions in which 1 does not occur as a summand.

(3) Show that the number of partitions of a number into parts which have at most one of each distinct even parts (e.g. 1+1+1+2+3+4) equals the number of partitions of the number in which each part can appear at most three times (e.g. 1+1+1+2+2+4+4+4).

Proof: We'll consider the two given statements as two distinct cases and by using generating functions, we'll show that the two statements are actually equivalent.

First Case: The first statement says that 2, 4, 6, • • • can appear in the partitions either 0 or 1 time. So, the contributing factors of the even numbers are

2 → 1 + x 2 4 → 1 + x 4 . . .
For the odd integers, there are no certain bounds. So, the contributing factors of the odd integers are

1 → 1 + x + x 2 + x 3 + • • • = 1 1 -x 3 → 1 + x 3 + x 6 + x 9 + • • • = 1 1 -x 3 . . .
So, the combined contributing factor is

(1 + x 2 )(1 + x 4 )(1 + x 6 ) • • • (1 -x)(1 -x 3 )(1 -x 5 ) • • •
Second Case: According to the second statement, the summands can be used at most 3 times in each partition, so the contributing factors in the generating function are

1 → 1 + x + x 2 + x 3 = 1 -x 4 1 -x 2 → 1 + x 2 + x 4 + x 6 = 1 -x 8 1 -x 2 3 → 1 + x 3 + x 6 + x 9 = 1 -x 12 1 -x 3 . . .
Hence, the combined contributing factor is

(1 -x 4 )(1 -x 8 )(1 -x 12 ) • • • (1 -x)(1 -x 2 )(1 -x 3 ) • • • = 1 (1 -x)(1 -x 3 ) • • • • 1 -x 4 1 -x 2 • 1 -x 8 1 -x 4 • • • = (1 + x 2 )(1 + x 4 )(1 + x 6 )(1 + x 8 ) • • • • • • (1 -x)(1 -x 3 )(1 -x 5 )(1 -x 7 ) • • • • • •
Observe that, the resulting generating functions in both cases are equal. Thus, we conclude that both the statements are equivalent, i.e. the number of partitions of a number into parts which have at most one of each distinct even parts equals the number of partitions of the number in which each part can appear at most three times.

(4) For every positive integer n ≥ 1, prove that p o (n) = p d (n). Proof: This problem can be solved by logical reasoning, which is a bit complicated. So, we'll use generating functions to kill the problem.

To find the generating function for p o (n), we calculated the contributing factors of each of the odd numbers and then multiply them. We have,

1 → 1 + x + x 2 + x 3 + • • • = 1 1 -x 3 → 1 + x 3 + x 6 + x 9 + • • • = 1 1 -x 3 5 → 1 + x 5 + x 10 + x 15 + • • • = 1 1 -x 5 . . . Therefore, the combined generating function for p o (n) is 1 (1 -x)(1 -x 3 )(1 -x 5 ) • • •
In case of p d (n), the distinct summands can be used in any partition of n exactly 0 or 1 time. So, their contributing factors are

1 → 1 + x 2 → 1 + x 2 3 → 1 + x 3 4 → 1 + x 4 . . .
So, their combined contributing factor is

(1 + x)(1 + x 2 )(1 + x 3 )(1 + x 4 ) • • • = (1 -x 2 )(1 -x 4 )(1 -x 6 ) • • • (1 -x)(1 -x 2 )(1 -x 3 )(1 -x 4 ) • • •
Notice that, the numerator consists of the numbers of the form (1 -x 2f ) and the denominator contains the numbers of the form (1 -x f ), where f ∈ N. So, the numbers in the numerator and the numbers of the form (1 -x 2f ) in the denominator gets cancelled out. So, the final outcome is 1

(1 -x)(1 -x 3 )(1 -x 5 ) • • • which is identical to the generating function of p o (n).
Hence, it is proved that p o (n) = p d (n).

(5) Prove that for every positive integer n the number of ways to write n as the sum of ordered pairs is 2 n-1 .

Proof: Let us consider an ordered sum

a 1 + a 2 + • • • + a k = n
where a i ≥1 which is represented by n 1 ′ s in a row separated by (k -1) "strokes" / 11.....1

a 1 / 11....1 a 2 / 11....1 a 3 / • • • • • • / 11....1 a k
To obtain all such displays (∀1 ≤ k ≤ n) ,line up n 1 ′ s and for each n spaces between adjacent pairs , either put a stroke or do not put in a stroke. and this can be done

2 * 2 * 2 • • • * 2 (n-1)times = 2 n-1 ways.
6 Formal Power Series and Euler's Identity

(1) Euler's Identity: For any positive integer n,

∞ n=1 (1 -n ) = 1 + ∞ j=1 (-1) j x 3j 2 +j 2 + x 3j 2 -j 2
From this theorem, we can easily derive an useful identity which is known as MacMahon's Identity which is as follows.

p(n) = p(n -1) + p(n -2) -p(n -5) -p(n -7) + p(n -12) + p(n -15) -• • • ∞
Here we submit a rigorous proof of this identity by using Euler's Partition Theorem.

Proof: We know that

p(n) = ∞ k=1 p(k).x k = ∞ k≥1 1 1 -x k
Now, the left hand side of Euler's formula is

∞ k=1 1 (1 -x k ) = 1 ∞ k=1 (1 -x k ) = 1 p(n)
So, according to the formula of Euler the identity reforms into

1 + ∞ j=1 (-1) j x 3j 2 +j 2 + x 3j 2 -j 2 ∞ k=1 p(k).x k = 1
Now, if we expand the summation of the 1 st bracket, we get the following

(1 -x -x 2 + x 5 + x 7 -x 12 -x 15 + • • • ∞) ∞ k=1 p(k).x k = 1
Now, equating co efficient of x n on both side, we get in L.H.S.,

p(n) -p(n -1) -p(n -2) + p(n -5) + p(n -7) -p(n -12) -p(n -15) + • • • ∞ = 0
And thus

p(n) = p(n -1) + p(n -2) -p(n -5) -p(n -7) + p(n -12) + p(n -15) -• • • ∞ Q.E.D.
7 An Upper Bound on p(n)

Here we give a crude bound for p(n) which involves exponential functions.Here we submit a simple algebraic proof of the upper bound of p(n).

Claim : If n≥1, then we have p(n) < e 2nπ √ 6n

Proof: Let

f (x) := ∞ k≥1 1 1 -x k = 1 + ∞ k=1 p(k).
x k and here 0 < x < 1. Then we have p(n).x n < f (x) by taking logarithm in both sides, we get log e f (x) > log e p(n) + n log e x which is equivalent to

log e p(n) < log e f (x) + n log e 1 x Now, log e f (x) = log e ∞ k≥1 1 1 -x k = ∞ k=1 log e 1 1 -x k = - ∞ k=1 log e (1 -x k ) Now, for 0 < x < 1 , log e (1 -x k ) = - ∞ m=1 (x k ) m k = - ∞ m=1
x mk k Now, putting the value of the summation, we get

log e f (x) = - ∞ k=1 log e (1 -x k ) = ∞ k=1 ∞ m=1 x mk m = ∞ m=1 ∞ k=1 x mk m = ∞ m=1 1 m ∞ k=1
x mk Therefore, we obtain

log e f (x) = ∞ m=1 x m m(1 -x m ) • • • (1) We know that, 1 -x m 1 -x = 1 + x + x 2 + x 3 + • • • For 0 < x < 1 and m > 1, 1 > x m-1 x > x m-1 . . . x m-2 > x m-1
Adding all these and adding x m-1 on both sides, we get

1 -x m 1 -x > mx m-1
and now a trivial inequality is

m > 1 -x m 1 -x > mx m-1 which leads to m(1 -x) x m > 1 -x m x m > mx m-1 x m ⇒ m(1 -x) x m > 1 -x m x m > m(1 -x)
x now reversing the inequality we get...

x m m(1 -x) < x m 1 -x m < x m(1 -x)
now multiplying 1 m to both sides we get...

x m m 2 (1 -x) < x m m(1 -x m ) < x m 2 (1 -x)
now taking summation and using right hand side of our inequality we get..

∞ m=1 x m m(1 -x m ) < ∞ m=1 x m 2 (1 -x)
From (1) we can obtain..

log e f (x) = ∞ m=1 x m 2 (1 -x)
now the right hand side has a closed result.. A special approximation of Dilog can be got by Hurwitz zeta function defined as

log e f (x) = π 2 6 • x 1 -x now let's take x 1-x = 1
ζ(s, q) = ∞ n=0 1 (q + n) s
where it is formally defined for complex arguments s with Re(s) > 1 and q with Re(q) > 0. as compared to the Dilog, Hurwitz calculated that Li s (z) > (2π)

1 s Γ( 1 s ) ζ 1-

=

  For a simplified lower bound of p(n) we can follow the right hand side of our inequality.. iLi 2 (x)where Li 2 (x) is In mathematics, Spence's function, or dilogarithm,Li 2 (z) = -z 0 ln(1 -u) u du, z ∈ C


Hua Tang
email: htang@ece.sunysb.edu

Ying Wei
email: ywei@ece.sunysb.edu

Alex Doboli
email: adoboli@ece.sunysb.edu

MINLP Based Topology Synthesis for Delta Sigma Modulators Optimized for Signal Path Complexity, Sensitivity and Power Consumption

This paper proposes a novel architecture synthesis algorithm for single-loop single-bit ∆Σ modulators. We defined a generic modulator architecture and derived its noise and signal transfer function (NTF/STF) in symbolic forms. We then used the TF in MINLP to generate optimal topologies for a variety of design requirement, such as modulator complexity, sensitivity and power consumption, which appeard as cost functions. Experiments show the superiority of synthesized topologies as compared to traditional solutions.

Introduction

Because of its promise to deliver short design closure at much lesser costs, high-level synthesis (HLS) is rapidly becoming a main topic in today's system-onchip (SoC) design [START_REF] Antao | ARCHGEN: Automated Synthesis of Analog Systems[END_REF][START_REF] Doboli | Exploration-Based High-Level Synthesis of Linear Analog Systems Operating at Low/Medium Frequencies[END_REF][START_REF] Gielen | Computer Aided Design of Analog and Mixedsignal Integrated Circuits[END_REF][START_REF] Tang | Towards High-Level Synthesis of Analog and Mixed-Signal Systems from VHDL-AMS Specifications -A Case Study for a Sigma-Delta Analog-Digital Converter[END_REF]. Though HLS is well defined for digital circuits, there is a lack of systematic system design methodologies for analog and mixed-signal circuits, which are essential components of any modern SoC. Current research on analog and mixed-signal CAD mostly addresses transistor sizing and layout generation, which are activities at low level of abstraction [START_REF] Gielen | Computer Aided Design of Analog and Mixedsignal Integrated Circuits[END_REF]. Analog and mixed-signal high-level synthesis (AMS-HLS) consists of four main tasks [START_REF] Antao | ARCHGEN: Automated Synthesis of Analog Systems[END_REF][START_REF] Doboli | Exploration-Based High-Level Synthesis of Linear Analog Systems Operating at Low/Medium Frequencies[END_REF][START_REF] Doboli | Behavioral Modeling for High-Level Synthesis of Analog and Mixed-Signal Systems from VHDL-AMS[END_REF][START_REF] Gielen | Computer Aided Design of Analog and Mixedsignal Integrated Circuits[END_REF]: (i) system specification, (ii) architecture synthesis (architecture generation and selection), (iii) constraint transformation, and (iv) design verification. High level activities, such as exploring for feasible system topologies and optimizing their parameters, are critical to developing constraint-satisfying or optimal system design [START_REF] Doboli | Exploration-Based High-Level Synthesis of Linear Analog Systems Operating at Low/Medium Frequencies[END_REF][START_REF] Gielen | Computer Aided Design of Analog and Mixedsignal Integrated Circuits[END_REF].

Inspite of their importance, AMS high-level activities remain purely manual, being accessible only to a small number of expert analog designers. In real-life, mixed-signal designers may have a library of popular architectures to choose from. Then, architectures are selected from the library based on the designer's experience. This is obviously an expensive and lengthy process that does not guarantee any optimality for the selected architecture. Recently, several methods were at-tempted to tackle the very challenging problem of automatically generating and selecting optimal topologies. Doboli and Vemuri [START_REF] Doboli | Exploration-Based High-Level Synthesis of Linear Analog Systems Operating at Low/Medium Frequencies[END_REF] present an architecture generation and selection technique based on tabu search exploration guided by the signal flow graph of a system. Antao and Brodersen [START_REF] Antao | ARCHGEN: Automated Synthesis of Analog Systems[END_REF] use the state-space equations of a filter to create different signal flow graphs, which are then used (through a mapping process) to create filter implementations. In spite of their novelty, these methods cannot be used for automatically synthesizing topologies for more complex systems, like ∆Σ modulators.

In this paper, we presented an original method for systematically and automatically generating architectures for single-loop single-bit ∆Σ modulators. These modulators are important components of many mixedsignal SoC. The crux of the synthesis method is a generic representation that describes all possible modulator topologies. The symbolic expressions for Noise Transfer Function (NTF) [START_REF] Norsworthy | Delta-Sigma Data Converters: Theory, Design, and Simulation[END_REF] and Signal Transfer Function (STF) [START_REF] Norsworthy | Delta-Sigma Data Converters: Theory, Design, and Simulation[END_REF] were derived for the generic topology. A MINLP (Mixed Integer Nonlinearly Constrained Programming) description was formulated to simultaneously generate and select the best topology under various design requirements, such as system hardware complexity, sensitivity under parameter variation, and power consumption. Experiments for 3 rd and 4 th order ∆Σ modulators showed that the synthesized topologies are significantly superior to traditional topologies.

We assumed that the topology for a single-loop, single-bit ∆Σ modulator is a signal flow graph containing integrators and having all its signal paths and coefficients of the signal paths defined, so that it realizes a desired TF (NTF and STF). Hence, a modulator topology differs from another one in terms of (1) the type of their integrators (delayed or delayless integrators), (2) their signal paths (whether they have the same signal paths or not), and (3) the numerical coefficients of their signal paths. For AMS-HLS, the three categories define the control parameters for topology synthesis, as they uniquely determine a topology. Then, generating optimal ∆Σ modulator topologies is equivalent to having all control parameters as unknowns and solving for their values that optimize certain performance criteria, This paper is organized as follows. Section 2 reviews similar work. Section 3 presents the generic topology for ∆Σ modulator and the related TF. Section 4 discusses MINLP formulation for obtaining optimal ADC topologies. Experiments are offered in Section 5. Finally, conclusions are provided.

U a1 1 a2 1 1 a3 Y V U b1 a1 1 1 a2 a3 1 Y V D/A z-1 z-1 z-1 z-1 z-1 z-1 D/A (c) ( d) b2 t32 b3 U 1 1 1 a1 Y V D/A z-1 z-1 z-1 U a1 1 1 1 Y V t32 z-1 z-1 D/A z-1 t14 t34 t24 t24 t14 t34 (b) (a)

Previous work on ∆Σ modulator synthesis

The related literature presents several ways of exploring for possible Σ∆ modulator topologies. One way is to pre-set the integrator types and signal paths, and explore only for the coefficient values [START_REF] Marques | Optimal Parameters for Delta-Sigma Modulator Topologies[END_REF][START_REF] Schreier | The Delta-Sigma Toolbox 5.2[END_REF]. By setting the first two types of control parameters, a set of incomplete topologies is defined. Several types of incomplete topologies are quite popular for different orders of single-bit, single-loop ∆Σ modulator [START_REF] Fischer | Alternative Topologies for Sigma-Delta Modulators -A Comparative Study[END_REF][START_REF] Kuo | Automatic Coefficients Design for High-Order Sigma-Delta Modulators[END_REF][START_REF] Norsworthy | Delta-Sigma Data Converters: Theory, Design, and Simulation[END_REF][START_REF] Ribner | A Comparison of Modulator Networks for High-Order Oversampled Delta-Sigma Analog-to-Digital Converters[END_REF]. Figure 1 depicts some well-known topologies for 3 rd order ∆Σ modulator. In this methodology, designers first decide with regard to which of the incomplete topologies should be used. Then, coefficients of the chosen topology are calculated for the desired TF, thus completing the process of topology design [START_REF] Marques | Optimal Parameters for Delta-Sigma Modulator Topologies[END_REF][START_REF] Medeiro | Top-down Design of High-Performance ∆Σ Modulators[END_REF][START_REF] Schreier | The Delta-Sigma Toolbox 5.2[END_REF]. As it can be noticed, there is no scheme to get an optimal topology. Designers have to select an incomplete topology based on their experience. One straightforward way to improve this methodology is to let designers try out all pre-selected topologies and then decide which one is optimal. The methodology implemented in DAISY [START_REF] Francken | DAISY: A Simulation-based High-level Synthesis Tool for Delta-Sigma Modulators[END_REF] follows this idea. A similar concept is also suggested by Bajdechi et al [START_REF] Bajdechi | Systematic Design Exploration of Delta-Sigma ADCs[END_REF]. Given the design specification, e.g., SNR and DR, the tool selects one from a set of topologies with the smallest power consumption.

The main limitation of existing synthesis techniques is that most of the topology control parameters (integrator types, signal paths, and coefficient values) are pre-set, which severely restricts the solution space for topology generation. As a result, solutions are actually representing only local optima for a given set of requirements. To find the real mathematical optima, all control parameters ought to be considered. This paper proposes a MINLP based topology synthesis method that considers all control variables as unknowns, and is capable of finding mathematical optima through solving mixed-integer nonlinear equations.

Generic topology for ∆Σ modulators

The crux of the proposed topology synthesis method is a generic representation that describes all possible topologies for single-bit single-loop ∆Σ modulators. Figure 2 shows the representation for 3 rd order ∆Σ modulators, but similar representations exist for higher order modulators also.

The generic representation includes all possible feedback and feedforward signal paths. Y i represents the output of the i th integrator, and Y is the input to the quantizer. A i stand for the feedback coefficients from the output to the i th adder, b i are the feedforward coefficients from the input to the i th adder, and t ji are the coefficients from Y j to the i th adder in the modulator. There are negative signs for all t ji and a i coefficients. Please note that some of the signal paths in the generic topology may seem redundant to expert designers: for example, in Figure 2, signal path with design coefficient a 4 never exists in the generated topology. However, for the sake of completeness, these paths were also considered.

Let N be the modulator order. Then, following expressions hold as a general rule:

t ji ≥ 0, if j ≥ i, j = 1, ...N, i = 1, ...N + 1 t ji ≤ 0, if j < i, j = 1, ...N, i = 1, ...N + 1 a i ≥ 0, b i ≥ 0, i = 1, ...N + 1 (1)
There are (N + 1)× (N + 2) coefficients in the generic topology. It can be seen that all "classic" topologies in Figure 1 can be derived from the generic topology by removing some of the signal paths. Note also that integrators could be either delayed or delayless.

For the generic topology, we derived its NTF and STF in terms of the coefficients of all signal paths. We assumed that the quantization noise E is additive whitenoise [START_REF] Norsworthy | Delta-Sigma Data Converters: Theory, Design, and Simulation[END_REF]. By generalizing, we calculated symbolic expressions for NTF and STF of single-bit single-loop ∆Σ modulators of any order.

Lemma: Numerator (N T F n ) and denominator (N T F d ) of NTF of ∆Σ modulator of order N are expressed as:

N T Fn = N K=0 (-1) K+1 C K N -C K-1 N -1 N i=1 t ii + .. + (-1) K C K-K N -K N i 1 = N i 2 = .. N i K t i 1 (i 1 ,i 2 ,..i K ) t i 2 (i 1 ,i 2 ,..i K ) t i K (i 1 ,i 2 ,..i K ) z N -K N T F d = N K=0 (-1) K+1 C k N -C K-1 N -1 N i=1 t ii + .. + (-1) K C K-K N -K N i 1 = N i 2 = .. N i K t i 1 (i 1 ,i 2 ,..i K ) t i 2 (i 1 ,i 2 ,..i K ) t i K (i 1 ,i 2 ,..i K ) + (-1) K+1 C K-1 N -1 N i=1 a i t i,N +1 + C K-2 N -2 N i=1 a i N j 1 = N j 2 t j 1 (N +1,j 2 ) t j 2 (N +1,j 2 ) + .. + C K-K N -K N i=1 a i N j 1 = N j 2 = .. N j K t j 1 (N +1,j 2 ,..j K ) t j 2 (N +1,j 2 ,..j K ) ..t j k (N +1,j 2 ,..j K ) + a N +1 (-1) K+1 C K N -C K-1 N -1 N i=1 t ii + .. + (-1) K C K-K N -K N i 1 = N i 2 = .. N i K t i 1 (i 1 ,i 2 ,..i K ) t i 2 (i 1 ,i 2 ,..i K ) t i K (i 1 ,i 2 ,..i K ) z N -K
In the above expression, (i 1 , i 2 , ..i K ) means selecting only one of the them, similarly for (N + 1, j 2 , ..j K ).

Optimal topology generation using MINLP

MINLP problem formulation

By equating the symbolic TF to the desired TF (desired STF is assumed to be 1), 3 × (N + 1) equations are obtained. Obviously, there are an infinite number of solutions considering that the number of unknowns -(N + 1) × (N + 2), is always larger than the number of equations -3 × (N + 1).

After carefully analyzing the symbolic expression for NTF and STF, we found following interesting properties: (i) all terms in the expression are nonlinear equations of the defined coefficient variables and (ii) there are no quadratic terms for any of the coefficients. As a result, this formulation is suitable to be solved by Nonlinear Programming (NLP) [START_REF] Fletcher | MINCO:MINLP-AMPL[END_REF]. Also, in order to select any signal path in the generic topology, a corresponding binary 0/1 variable was defined to denote whether the signal path is present or not.

For a given a cost function f , we formulated the topology synthesis problem as:

minimize cost f (x i , wx i );
subject to : g(x i ) = 0; subject to : h(x i , wx i ) ≤ 0; subject to : x i satisf y (1), wx i ∈ {0, 1}; where x i denotes any of the unknown coefficients a i , b i and t ji defined in (1), g are the 3 × (N + 1) equality constraints obtained from equating the symbolic NTF and STF to the desired NTF and STF, and h are the inequality constraints relating the coefficient variables to the binary variables, so that wx i correclty identify whether the signal path with coefficient x i is present or not.

The resulting problem can be optimally solved using mixed-integer nonlinear programming (MINLP) [START_REF] Fletcher | MINCO:MINLP-AMPL[END_REF]. Thus, MINLP solving offers the best topology with respect to the cost function f . MINLP formulation is scalable, and it is easy to add additional constraints.

Different cost function formulation

Cost function formulation is an important issue for optimal topology synthesis. proposed method supports three types of cost functions: (1) for minimizing the signal path (hardware) complexity of ∆Σ modulator, (2) for minimizing the sensitivity of the modulator with respect to coefficient variations, and (3) for minimizing the power consumption. These functions are discussed next.

A. Signal path minimization. Since binary variables denote whether the corresponding signal paths are present or not, the cost function f was formulated as:

M inimize (N +1)(N +2) i=1 wx i B.
Sensitivity minimization. This function considers the total sensitivity of the ∆Σ modulator with respect to variations of the coefficient variables. This optimization is very useful, since process and mismatch induced variations are expected to shift coefficient values away from their nominal values. Minimizing the total sensitivity results in a more stable modulator, and thus improves yield.

Suppose NTF is

T (z) = N T F n N T F d = p 1 z N + p 2 z N -1 + ... + p N -1 z + p N q 1 z N + q 2 z N -1 + ... + q N -1 z + q N
Then, the cost function f could be written as:

M inimize(

(N +1)(N +2) i=1 N j=1 δp j δx i + (N +1)(N +2) i=1 N k=1 δq k δx i ) 2
The sensitivity value was squared to encourage getting a value close to zero (corresponding to no sensitivity with respect to small variations of the coefficient variables).

The calculation of the sensitivity function δpj δxi and δq k δxi is quite easy, since we already derived the symbolic expressions for NTF. Each of the coefficients for NTF was symbolically calculated too. Note that STF could be part of the cost function too. C. Power consumption minimization. We used a power consumption estimation method based on the work by Medeiro et al [START_REF] Medeiro | Top-down Design of High-Performance ∆Σ Modulators[END_REF]. For a switch-capacitor circuit implementation of the modulator, the power consumption mainly consist of static power consumption of OpAmp circuits, and dynamic power consumption of capacitors. Static power consumption can be approximated as P s = I bias V supply N , where V supply is the supply voltage and N represents the order of the modulator. To minimize static power consumption, we need to minimize I bias , which comes down to minimize C eq , the equivalent load for the input integrator [START_REF] Medeiro | Top-down Design of High-Performance ∆Σ Modulators[END_REF]. For example, for the generic topology in Figure 2,

C eq = C s (1 + β + a1 b1 + t11 b1 + t21 b1 + t31 b1 + α + α(b 1 + β + a 1 + t 11 + t 21 + t 31 ))
, where C s is the sampling capacitor and parasitic capacitors C p = βC s and C l = αC s (0 ≤ α, β ≤ 1). So, once C s is set from thermal noise consideration [START_REF] Medeiro | Top-down Design of High-Performance ∆Σ Modulators[END_REF], C eq satisfy C eq = KC s , where K ∈ R. Dynamic power consumption is dissipated to charge a capacitor of value C at frequency of f s between reference voltages V r . It can be estimated as P d = (2V r ) 2 Cf s (considering fully differential circuitry). To minimize it, we need to minimize the total capacitance of the modulator. Similar to the way of deriving C eq , C total was formulated as

C total = C s ((1 + 1 b1 + a1 b1 + N j=1 tj1 b1 ) + N i=2 (1 + 1 t (i-1)(i) + ai t (i-1)(i) + bi t (i-1)(i) + N j =(i-1) tji t (i-1)(i) ) + (1 + aN+1 t (N )(N +1) + bN+1 t (N )(N +1) + N j =N t (j)N +1 t (N )(N +1) )).

Topology exploration flow

The proposed topology synthesis flow for ∆Σ modulators is shown in Figure 3. The inputs to the flow are design specifications, such as desired SNR, and DR. Based on the desired performance, an initial order N init of the ∆Σ modulator is estimated (1 ≤ N ≤ 8). Also, two additional design parameters are considered, the Oversampling Ratio (OSR) and maximum NTF magnitude (MAG). These two design parameters are confined within certain ranges, and initially set to their minimal values. For example, OSR init can be set to 16 (16 ≤ OSR ≤ 256), and M AG init to 1.2 (1.2 ≤ M AG ≤ 2.0 according to Lee's rule [START_REF] Schreier | The Delta-Sigma Toolbox 5.2[END_REF]).

Next, the method sets the type for each of the integrators in the modulator. This has to be done first, because different combinations of integrator types lead to different symbolic expression for NTF and STF. There maybe a large number of combinations of integrator types for an N th order ∆Σ modulator, considering that each integrator can be either of delayed or delayless type. Theoretically the total number of combinations is 2 N . In theory, to obtain the optimal topology, all these combinations should be considered. In our flow, we considered a library of combinations of integrator types. Figure 4 shows some combinations of the integrator types for 3 rd and 4 th order ∆Σ modulators.

After integrator types are set, based on N init , OSR init and M AG init , a NTF is generated similar to [START_REF] Schreier | The Delta-Sigma Toolbox 5.2[END_REF]. Then, using the symbolic formulas in Section 3, MINLP description is generated, and solved with an NLP solver [START_REF] Fletcher | MINCO:MINLP-AMPL[END_REF]. The topology obtained after solving the MINLP program is behaviorally simulated to test whether the SNR and DR meet the specification. If yes, an optimal topology is generated for the current combination of integrator types. Otherwise, first it considers increasing M AG until its maximum limit is reached. Then, it considers increasing OSR until its maximum limit is reached, and finally it considers increasing the modulator order until the order is out of range. If an optimal solution is obtained for a combination of minimal M AG and OSR values, the solution is saved as optimal for the current combination of integrator types. If there are some other combinations of integrator types that are not yet explored, the design shifts to another combination, and the process is repeated until all combinations are analyzed.

After this, a set of solutions, each of which is actually a local optima for a particular combination of integrator types, is passed to the final synthesis stage, where it is subject to one or more tests for picking the global optimal solution. For example, if we are using the cost function of minimum total sensitivity, the set of local optima is subject to minimum sensitivity test via Monte-Carlo analysis. The solution with least sensitivity and most

Z-1 1 Z-1 Z-1 1 Z-1 Z Z Z-1 1 Z-1 1 Z-1 Z-1 1 Z-1 Z-1 Z Z Z Z-1 1 1 Z-1 1 Z-1 Z-1 1 Z-1 1 Z-1 Z-1 Z Z (b) 4th order (a) 3rd order

Experiments

We presented experiments for topology synthesis of 3 rd and 4 th order ∆Σ modulators, and compared our results against traditional topologies.

3rd order ∆Σ modulator

The specification was DR ≥ 70db, or equivalently 11 bits of resolution. Hence, the estimated least order ∆Σ modulator was 3. The initial combination for integrator types corresponded to the first combination in Figure 4(a). The minimum OSR was set to 32 and minimum M AG was set to 1.5. Based on these information, N T F was calculated next. Using the ∆Σ toolbox [START_REF] Schreier | The Delta-Sigma Toolbox 5.2[END_REF], the synthesized NTF was

N T F 1 = (z-1)(z 2 -1.994z+1) (z-0.6685)(z 2 -1.529z+0.6629) .
With this NTF, the design flow was able to generate an optimal solution with DR of 75db and peak SN R of 67db, which met the specification. For the cost function minimizing the total sensitivity, the optimal topology solutions obtained for the first two combinations of integrator types in Figure 4(a) are shown in Figure 5(a) and (b) respectively. For both topologies the minimized sensitivity is very close to 0. In order to more accurately determine the global optima, Monte-Carlo analysis was carried out for the two topologies. The analysis considered a maximum 10% variation from the nominal value for each of the coefficient variables, and a uniform distribution in the -5% to +5% range for the variation. From the analysis, the second topology turned out to be the least sensitive one.

We compared our solutions with traditional topologies from [START_REF] Schreier | The Delta-Sigma Toolbox 5.2[END_REF]. In [START_REF] Schreier | The Delta-Sigma Toolbox 5.2[END_REF], there is no optimization scheme to

(a) U E 1 b4=1 (b) U E D/A 1 b4=1 Z-1 Z-1 1 1 Z-1 1 Z-1 Z-1 Z Z-
Z-1 Z 1 Z-1 Z-1 Z 1 Z-1
Figure 6: 3 rd and 4 th order topology from the toolbox in [START_REF] Schreier | The Delta-Sigma Toolbox 5.2[END_REF] generate and select an optimal topology. Instead, 4 sets of incomplete topologies with combination of integrator types and signal paths pre-set are stored in a library, and one of these is chosen to derive the complete topology. Figure 6(a) shows one of the complete topologies.

To compare its sensitivity, we run Monte-Carlo analysis on the modulator topology. The analysis setting was the same as for the previous experiment. The resulting DR and SN R were compared with those for the topology in Figure 5(b). The first case considered the feasibility of DR and SN R, that is whether the resulting topology can still function as a modulator with an working DR and SN R. The other case considered the deviation of DR and SN R of the resulting topology from the nominal values. In terms of feasibility, a test scheme based on linear regression lines was used, similar to [START_REF] Bajdechi | Systematic Design Exploration of Delta-Sigma ADCs[END_REF]. The results show that 646 out of the total of 1,000 Monte-Carlo runs are still feasible for the topology, as shown in Figure 6(a). 961 out of the 1,000 runs are feasible for the topology with minimum total sensitivity shown in Figure 5(b) (which was generated using the proposed method). In terms of deviation, we consider the DR deviation from the nominal value (75db) for all feasible solutions. The histograms of DR deviation for both topologies are shown in Figure 7. It can be seen that the DR deviation is significant for the topology in Figure 6(a) -produced using the tool in [START_REF] Schreier | The Delta-Sigma Toolbox 5.2[END_REF], and many feasible solutions have DR deviations higher than |3db|. On the other hand, the optimal topology in Figure 5(b) has most of its solutions concentrated in the region of DR deviation less than |2db|. So, the synthesized topologies are more tolerant to design parameter variations not only in terms of yield (number of feasible solutions) but also performance deviations.

For the cost function minimizing power consumption, the optimal synthesized topology is shown in Figure 8(a). Note that it used the 2 nd combination in Figure 4(a). This topology achieves a total capacitance equal to about 18 units of C s . Compared to the topology from [START_REF] Schreier | The Delta-Sigma Toolbox 5.2[END_REF] shown in Figure 6(a), which has a total capacitance of 32 units of C s , it saved power by 44%.

¡ ¡ ¡ ¡ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¤ ¤ ¤ ¤ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¦ ¦ ¦ ¦ § § § § ¨© © ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !

4th order ∆Σ modulator

The design specification was DR ≥ 80db or equivalently 13 bits of resolution. The estimated order for this DR is 4. In this experiment, the initial OSR was set to 16 (16 ≤ OSR ≤ 256) and M AG was fixed to 1.5. The design flow started with the first combination of integrator types shown in Figure 4(b).

We first used the cost function for minimum signal paths complexity. The optimal topology generated in the first iteration does not meet the DR specification. Since M AG was fixed, OSR was increased to 32. Next, using the toolbox [START_REF] Schreier | The Delta-Sigma Toolbox 5.2[END_REF] the design flow generates following NTF2:

N T F 2 = (z 2 -1.999z+1)(z 2 -1.993z+1) (z 2 -1.492z+0.563)(z 2 -1.7z+0.7861)
This time, the generated topology had a DR of 84db. Since the specification was met, the design flow went to the other combination of integrator types to generate an optimal topology for that combination. The two optimal topologies generated for the two combinations in Figure 4(b) are depicted in Figure 9 (coefficient values are not shown). There are 12 and 13 signal paths for the topologies in Figure 9, respectively. So, the topology in Figure 9(a) was the global optima with respect to the minimum path cost function. For minimum total sensitivity, the two optimal topologies synthesized for the two combinations of integrator types are presented in Figure 10. Both topologies have their cost value very close to zero. Monte-Carlo analysis shows that the first one is the global optima. We compared these topologies with those from [START_REF] Schreier | The Delta-Sigma Toolbox 5.2[END_REF]. The toolbox generated the complete topology in Figure 6 For the topology from [START_REF] Schreier | The Delta-Sigma Toolbox 5.2[END_REF], feasible solutions are scattered in various regions, and there are many solutions that have DR deviation more than |3db|. For the optimal topology generated using the proposed methodology, feasible solutions are highly concentrated in the region where DR deviation is less that |3db|, and only a small number solutions go beyond that region. Finally, using the cost function for minimizing power consumption, the optimal topology generated with our method is shown in Figure 8(b). This topology achieves a total capacitance of about 26 units of C s . Compared to the topology from [START_REF] Schreier | The Delta-Sigma Toolbox 5.2[END_REF] and shown in Figure 6(b), which has a total capacitance of 38 units of C s , it saves power by 32%.

To show that the synthesized topologies are effective in terms of DR, the DRs for three topologies (the traditional topology in Figure 6

Conclusion

This paper presented a methodology for automated synthesis of single-loop single-bit ∆Σ modulator topologies. To consider all possible topologies, a generic ∆Σ modulator topology was defined, and symbolic TF for this topology were derived. We then formulated the synthesis problem as MINLP. This guarantees finding an optimal solution with respect to the requirements. Experiments showed that the optimal topologies generated by the proposed method are less complex in terms of the number of signal paths, much more resistant to coefficient variations in terms of the yield and performance deviation, and more power efficient when compared to traditional modulator topologies. Ongoing % % % % %

Figure 1 : 3

 13 Figure 1: 3 rd order ∆Σ modulator topologies such as SNR, DR, system complexity, sensitivity, and power consumption.This paper is organized as follows. Section 2 reviews similar work. Section 3 presents the generic topology for ∆Σ modulator and the related TF. Section 4 discusses MINLP formulation for obtaining optimal ADC topologies. Experiments are offered in Section 5. Finally, conclusions are provided.

Figure 3 :

 3 Figure 3: Topology synthesis methodology

Figure 4 :

 4 Figure 4: Combinations of integrator types stability is the global optima. If a test can not differentiate between solutions, other tests, like power consumption, are used.

Figure 5 :

 5 Figure 5: Two synthesized topologies using minimum total sensitivity cost function

Figure 7 :Figure 8 :

 78 Figure 7: Histograms of DR deviation

Figure 9 :Figure 10 :

 910 Figure 9: Two synthesized topologies using minimum signal path cost function

  (b), the one in Figure 8(b) optimized for power consumption, and the one in Figure 10(a) optimized for total sensitivity) are plotted in Figure 12. It can be seen that they have similar DR performance.

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05)

& & & & & &

Proc. of Forum on Specification and Design Languages, 2003. Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05) 1530-1591/05 $ 20.00 IEEE

' ' ' ' ' ' ' ' ' ' ' ' ( ( (

* Supported by Defense Advanced Research Projects Agency (DARPA) and managed by the Sensors Directorate of the

 ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( (0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ? ? ? ? ? ? @ @ @ @ @ @ @ @ @ @ @ @ @ A


C Soens

G Van Der Plas

P Wambacq

S Donnay

Simulation Methodology for Analysis of Substrate Noise Impact on Analog / RF Circuits Including Interconnect Resistance

This paper reports a novel simulation methodology for analysis and prediction of substrate noise impact on analog / RF circuits taking into account the role of the parasitic resistance of the on-chip interconnect in the impact mechanism. This methodology allows investigation of the role of the separate devices (also parasitic devices) in the analog / RF circuit in the overall impact. This way is revealed which devices have to be taken care of (shielding, topology change) to protect the circuit against substrate noise. The developed methodology is used to analyze impact of substrate noise on a 3 GHz LC-tank Voltage Controlled Oscillator (VCO) designed in a high-ohmic 0.18 µm 1PM6 CMOS technology. For this VCO (in the investigated frequency range from DC to 15 MHz) impact is mainly caused by resistive coupling of noise from the substrate to the non-ideal on-chip ground interconnect, resulting in analog ground bounce and frequency modulation. Hence, the presented test-case reveals the important role of the onchip interconnect in the phenomenon of substrate noise impact.

Introduction

The continuous downscaling of CMOS technology has stimulated the trend to integrate RF circuits and digital base-band processing circuits onto one single chip. This has enabled a cost reduction and therefore a proliferation of mixed-mode designs during the past years. However, this single chip solution is facing the problem of analog performance degradation due to impact of digital switching noise, also called substrate noise. The problem of substrate noise coupling is in general divided into three main fields of study [START_REF] Donnay | Substrate noise coupling in mixed-signal IC's[END_REF]: generation, propagation and impact of substrate noise. Actual simulation methods contain an RC-model of the substrate and a package model [START_REF] Clement | LAYIN: Toward a global solution for parasitic coupling modeling and visualization[END_REF][START_REF] Chu | A Substrate Noise Analysis Methodology for Large-Scale Mixed-Signal ICs[END_REF][START_REF] Singh | A review of substrate coupling issues and modeling strategies[END_REF]. These are used to simulate substrate noise coupling from a digital circuit to any location on the substrate (e.g. under a sensitive analog circuit). These simulation methods are extended with macro-modeling techniques to efficiently simulate the substrate noise generation of large digital circuits [START_REF] Miliozzi | SUBWAVE: a methodology for modeling digital substrate noise injection in mixed-signal ICs[END_REF][START_REF] Van Heijningen | High-Level simulation of substrate noise generation including power supply noise coupling[END_REF]. For the analysis of substrate noise impact on the sensitive analog / RF circuits up to now no satisfying simulation method exists. The substrate noise simulation methodology presented in [START_REF] Chu | A Substrate Noise Analysis Methodology for Large-Scale Mixed-Signal ICs[END_REF] for instance, only models the substrate noise waveforms up to the sensitive nodes at the interface of the substrate and the analog / RF circuit. A comprehensive simulation approach taking all the important effects into account to model the impact of these waveforms remains elusive. Interconnect, for instance, is so far studied as a source of substrate noise [START_REF] Schrik | Coherent interconnect / substrate modeling using SPACE -an experimental study[END_REF] (capacitive coupling of noise from noise source interconnect into substrate) or as a path for substrate noise coupling (capacitive coupling of noise from substrate into interconnect of analog victim) [START_REF] Martorell | Modeling and evaluation of substrate noise induced by interconnects[END_REF]. However, the role in the impact mechanism (coupling of noise from substrate into interconnect of the analog circuit resulting in a voltage drop in the circuit) is not yet taken into account. This work reports a simulation methodology for analysis and prediction of the impact of substrate noise on an analog / RF circuit. The method takes interconnect parasitics into account in addition to all previously known effects. The waveforms, resulting from substrate noise impact, can be predicted by simulation for all the nodes at the interface between the substrate and the circuit as well as within the circuit (including the circuit output node). This allows detailed analysis of the impact mechanism. The presented method is validated by comparison of simulation results with measurements on an LC-tank VCO. A simulation accuracy of 2 dB is obtained. The analysis of the test chip reveals that the on-chip ground wire parasitics have an important influence on the level of substrate noise impact. Based on this, a model for impact of substrate noise on an LC-tank VCO was developed [START_REF] Soens | Performance degradation of an LC-tank VCO by impact of digital switching noise, accepted for[END_REF]. The presented impact simulation methodology when combined with a generation modeling methodology [START_REF] Badaroglu | High-level simulation of substrate noise generation from large digital circuits with multiple supplies[END_REF] would permit mixed-signal chip verification and sign-off of substrate noise coupling issues.

Section 2 briefly describes the phenomenon of substrate noise impact on an analog / RF circuit. In Section 3 the impact simulation methodology is explained and validated by applying it to a simple one-transistor circuit. In section 4 the VCO used for further validation of the simulation methodology is described. Section 5 explains the mechanisms behind coupling and impact of substrate noise on an LC-tank VCO. Section 6 resumes the experimental and simulation results on the 0.18 µm VCO. Finally conclusions are drawn in section 7.

Substrate noise coupling and impact

Figure 1 illustrates the problem of the impact of substrate noise on an analog / RF circuit as well as the parasitic contributions influencing this impact. A substrate noise signal generated at a distant location from its analog victim will first travel trough the substrate (Figure 1 (a)) up to the different sensitive nodes at the interface between the substrate and the circuit (Figure 1 (b)), for instance an NMOS back-gate. The substrate signal will then couple into the circuit via this back-gate (Figure 1 (I)) and propagate through the circuit to finally impact its output. It is thus necessary to extract a good model for the substrate, the circuit but as well the interface between both. In addition, supply network parasitics (Figure 1 (c)) can influence the substrate noise coupling and impact. Last but not least, the parasitics of the on-chip interconnect play an important role. A substrate noise signal can couple resistively (via e.g. substrate contacts connecting the on-chip metal ground lines with the substrate, Figure 1 (II)) or capacitively to the circuit interconnect causing a voltage drop in this interconnect and resulting in a voltage variation in the circuit. This voltage variation will then further propagate through the circuit to its output node. This 'interconnect related impact' can seriously harm the analog / RF performance. Hence a good model of the on-chip interconnect is mandatory for prediction of substrate noise impact. Therefore, unlike the classical simulation methodologies [START_REF] Clement | LAYIN: Toward a global solution for parasitic coupling modeling and visualization[END_REF][START_REF] Chu | A Substrate Noise Analysis Methodology for Large-Scale Mixed-Signal ICs[END_REF][START_REF] Singh | A review of substrate coupling issues and modeling strategies[END_REF][START_REF] Schrik | Coherent interconnect / substrate modeling using SPACE -an experimental study[END_REF][START_REF] Martorell | Modeling and evaluation of substrate noise induced by interconnects[END_REF], the proposed methodology (Figure 2) employs a model of the interconnect parasitics for simulation of the impact of substrate noise on analog / RF circuits.

Impact simulation methodology

Analysis starts from the layout of the analog / RF circuit (Figure 2). Process technology information is fed to the substrate modeler, the circuit extractor and the interconnect modeler to extract an RC-model for the substrate, an analog / RF circuit model and an interconnect model respectively. To these models a package model is added to obtain a simulation model for the entire system. This complete model is fed to the impact simulator together with the substrate noise waveforms. Finally, waveforms resulting from substrate noise impact can be predicted for the nodes at the interface between the substrate and the analog / RF circuit, as well as all the nodes within the circuit, including the circuit output node. For more detailed substrate noise impact investigations, impact through the different sensitive (parasitic) devices of the circuit (important devices for a VCO are illustrated in Figure 1) can be analyzed separately. It provides an analog designer with crucial information on which devices in the circuit have to be carefully shielded or which topology changes can be made to increase the substrate noise immunity of the circuit.

As an example, this paragraph will compare measurement and simulation of the impact of a substrate signal on an NMOS. The NMOS back-gate is the node in an analog circuit that is commonly suggested as the path via which substrate noise is likely to enter the circuit. In The following paragraph will describe more in detail the models for the substrate, the NMOS and the interconnect extracted with Substratestorm [11] and DIVA [START_REF] Diva | [END_REF] and simulated with Spectre RF [START_REF]Spectre RF[END_REF].

Test chip

This section briefly describes the test chip and the experiment used to validate the simulation methodology described in section 3. A VCO designed in a high-ohmic (20 ohm cm) twin-well 1P6M 0.18 µm CMOS technology (schematic shown in Figure 5 and microphotograph shown in Figure 6) is used as a substrate noise victim. It uses an NMOS / PMOS cross-coupled pair and an LC-tank formed by an on-chip inductor and an accumulation mode NMOS varactor. It operates around 3 GHz and has a phase noise of -100 dBc / Hz @ 100 kHz with a current consumption of 5 mA (VCO core) and a supply voltage of 1.8 V. A -5 dBm sinusoidal signal is injected into the substrate in the vicinity of the circuit (Figure 6 SUB). The impact of this substrate signal is measured and simulated. The circuit is powered with RF probes and its output is measured single ended with a spectrum analyzer (HP 8565E). The references (ground) for on one hand the sinusoidal signal injected into the substrate and, on the other hand the VCO input and output signals are connected on-chip.

Substrate noise impact mechanism for an LC-tank VCO

Substrate noise can couple into an LC-tank VCO (LC-tank consisting of an accumulation mode NMOS varactor and an on-chip inductor) through several sensitive components of the circuits:

resistively and capacitively to the non-ideal metal ground interconnect; resistively to the NMOS transistor back-gates; capacitively through the n-well to the PMOS transistor back-gates; capacitively to the inductors; capacitively through the n-well of the accumulation mode NMOS varactor, to its back-gate node; capacitively to the on-chip power supply interconnect; Resistive coupling to the VCO is independent of the noise frequency while capacitive coupling is proportionally increasing with the noise frequency. All these effects are taken into account in the proposed methodology. When a substrate noise signal couples into the VCO, it will modulate the oscillator signal both in amplitude and frequency. The output voltage of the VCO, V out , can be expressed as follows (n = number of entries for substrate noise in VCO):

1 • © § * + 1 • © § * + = ¦ ³ ¦ n i noise i sub i c n i noise i sub i AM c out dt t v t h K t f t v t h G A t v ) ) ( ) ( ( 2 cos ) ( ) ( 1 ) ( π with ) 2 ( cos ) ( t f A t v noise noise noise π = (1)
With h i sub the attenuation by the substrate from the noise source to a sensitive component i in the circuit (NMOS back-gate etc), A noise the noise amplitude, f noise the noise frequency, A c the local oscillator amplitude, and f c the local oscillator frequency. Further, K i (Hz / V) represents the sensitivity of the oscillator frequency to a voltage variation on component i, and G i AM (V -1 ) the AM gain associated to a component i. Since the substrate noise power is typically small compared to the local oscillator power, narrow-band frequency modulation (FM) can be assumed. Moreover superposition can be used to calculate the overall impact from the contributions of the separate components in the VCO. At the VCO output spurs appear at both sides of the local oscillator (Figure 7) at frequencies f c ±f noise . After some calculations the FM spur amplitude can be written as:

| 2 ) ( | | ) ( | ¦ = ± n i noise i noise i sub c noise c FM out f K A f H A f f V (2)
Since a VCO is often used in front of a limiting circuit (e.g. a switching mixer), FM is the most relevant mechanism. The amplitude modulation (AM) spurs can be written as:

| 2 ) ( | | ) ( | ¦ = ± n i i AM noise i sub c noise c AM out G A f H A f f V (3)
From equations ( 2) and (3) it is clear that in case of resistive coupling (H sub independent of frequency) followed by pure FM the spur voltage is inversely proportional to the noise frequency while for AM it is independent of frequency. These relations will be used in section 6 to investigate the dominant mechanism behind substrate noise impact on the 0.18 µm CMOS VCO.

Experimental and simulation analysis of substrate noise impact on the VCO

In this section, the simulation methodology described in section 3 is validated with measurements. It is used to investigate the dominant path and mechanism for impact of substrate noise on the 0.18 µm VCO. Models for the substrate, the VCO circuit and the interconnect are extracted with Substratestorm and DIVA. The resulting impact model is simulated using Spectre RF. As mentioned earlier in this paper, the waveform resulting from impact of substrate noise on the analog / RF victim can be obtained for any node at the interface of substrate and circuit and within the circuit. This allows one to find out what device(s) in the circuit play(s) a dominant role in the overall impact of substrate noise on the circuit performance. It is verified with simulations, that for the studied VCO the non-ideal on-chip ground interconnect (due to the inevitable resistance in this interconnect) is the dominant path for substrate noise impact. Impact via the NMOS transistor back-gate will be shown to be of lesser importance. The impact of a substrate noise signal with a frequency up to 15 MHz is analyzed. Substrate noise signals having these frequencies give rise to spurs close to the local oscillator frequency where disturbing signals are the most harmful. Moreover, the spurs resulting from FM (as will be proven further to be dominant compared to AM) are the largest for this frequency range. Figure 8 shows the comparison between measured and simulated spur power at f c ±f noise (for different tuning voltages, Vtune) when a -5 dBm sinusoidal signal is injected into the substrate in the vicinity of the VCO (via SUB in Figure 6). Simulations of the spur power at left and right side of the local oscillator (f c ±f noise ) agree with measurements with a maximal error of 2 dB, validating the presented methodology. Resistive coupling followed by FM is clearly the dominant mechanism behind impact of substrate noise since the spur power is proportional to the logarithm of the noise frequency. A small difference between left and right spur is observed caused by negligible AM of the local oscillator. In case of resistive coupling followed by AM the spur power would have been independent of the noise frequency. In case of capacitive coupling followed by FM or AM it would have been respectively independent or increasing with frequency. Since capacitive coupling is negligible, it can be concluded that impact via PMOS, inductor and NMOS varactor is negligible as well. The resistive coupling can occur only via the NMOS back-gate or the interconnect parasitic resistance. It will be proven with simulations that the latter is the dominant path via which substrate noise impacts the circuit. Figure 9 shows the contribution in the overall impact of the separate components (relevant for the investigated frequency range) in the VCO in terms of spur power in function of noise frequency. The dominant contribution is clearly coming from the parasitic resistance in the on-chip ground interconnect. The inversely proportional relation between spur amplitude and the substrate noise frequency proves that this impact is resulting from a resistive coupling followed by frequency modulation. More precisely substrate noise couples resistively to the ground interconnect, resulting in a voltage drop over its parasitic resistance and causing the voltage over the variable circuit capacitances (NMOS and PMOS capacitances, accumulation mode NMOS varactor capacitance) to vary, which results in modulation of the local oscillator frequency. Impact via the inductor is significantly lower because it results from capacitive coupling (C ind =120 fF per inductor) which is negligible for the studied substrate noise frequencies. It is interesting to note that this impact is constant with frequency proving hat the capacitive coupling is followed by frequency modulation. Impact via the NMOS back-gate is as well inversely proportional to the noise frequency but low compared to the impact via the non-ideal ground interconnect. For our test case a difference of approximately 20 dB, is obtained from simulation in Figure 9. Further, impact through the PMOS transistors and the varactor (both in an n-well) is less important than the inductor impact because of the even lower capacitance between the substrate and the n-well they are located in.

Starting from these observations a designer could improve the noise immunity of his circuit by lowering the resistance in the on-chip ground interconnect. A reduction by half of this resistance will lead to a reduction of approximately 6dB in the impact. To test this, a second extraction was done after enlarging where possible the ground interconnect lines in the VCO layout by a factor of two. This yields a prediction of a 4.5 dB lower impact (Figure 10).

Conclusions

This paper reports a novel simulation methodology for analysis and prediction of substrate noise impact on analog / RF circuits taking into account the parasitic resistance of on-chip interconnect. This methodology allows investigation of the contributions of the separate devices (also parasitic devices) in the analog / RF circuit in the overall impact. This way is revealed which devices have to be taken care of (shielding, topology change) to protect the circuit against substrate noise. The simulation model is validated by comparing measurements to simulations on a 3 GHz VCO designed in a 0.18 µm high-ohmic 1PM6 CMOS technology. Simulations show, that taking the (inevitable) resistance in the on-chip interconnect into account is crucial for accurate prediction of impact of substrate noise on an analog / RF circuit. This methodology has revealed that layout details such as on-chip ground line parasitic resistance can make an analog/RF circuit very sensitive to substrate noise.

Figure 1

 1 Figure 1 The presented simulation method allows the analysis of impact of substrate noise through the different sensitive components in the analog / RF circuit. For a VCO important entries into the circuit are the interconnect, the NMOS back-gate and the inductors.

Figure 2

 2 Figure 2 Substrate noise impact simulation methodology.

Figure 3

 3 measurements of the transfer from the substrate to the NMOS output are compared to simulations. The coupling from the substrate to the circuit via the NMOS back-gate is modeled taking into account the influence of the interconnect resistance. The resistance from the ground ring of the NMOS to the off-chip ground increases the voltage division from the substrate noise source to the back-gate voltage v bs by almost a factor two. This model is sufficient to explain the impact on the circuit within a maximal error of 1 dB.

Figure 3

 3 Figure 3 Measured transfer of a sinusoidal signal in the substrate to the NMOS output agrees well with simulations. This reveals that the NMOS backgate in combination with the parasitic resistance in the ground interconnect is the dominant path via which substrate noise impacts the NMOS.

Figure 4

 4 (a) shows the layout of the studied RF NMOS surrounded by a ring of contacts (here called NMOS Ground Ring (MOS GR)) connecting the substrate to the ground. Figure4 (b)shows the layout of the NMOS measurement structure. Four NMOS transistors are connected in parallel to realize a high enough back-gate transconductance (g mb ) for sufficient measurement accuracy. Figure4(c) shows a simplified view of the NMOS measurement structure with the locations on the substrate of the four important 'nodes' of the problem: the contact via which a signal is injected into the substrate (SUB) the NMOS back-gates (Back-gate), the NMOS ground ring (MOS GR) and the ground ring surrounding the complete measurement structure (GR).

Figure 4 Figure 4

 44 Figure 4 Overview of (a) the NMOS measurement structure, (b) the RF NMOS layout, (c) a simplified view of the measurement structure, (d) the extracted substrate and interconnect model and (e) the RF NMOS model.

Figure 5 Figure 6

 56 Figure 5 Schematic of the 0.18 µ µ µ µm CMOS LC-tank VCO: two entries to the circuit for substrate noise are indicated: the on-chip ground (V GND ) and the NMOS back-gate (V back-gate ).

Figure 7

 7 Figure 7 Power spectrum at the VCO output in presence of a -5 dBm 10 MHz substrate signal: spurs appear at both sides of the local oscillator.

Figure 8

 8 Figure 8 The total spur power at f c ±f noise at the VCO output caused by impact of a -5 dBm sinusoidal substrate signal: a linear relation between the power and the logarithm of f noise is observed.

Figure 9

 9 Figure 9 Simulation of the contributions of the separate devices in the VCO to the overall impact (at f c ±f noise , Vtune = 0V, Pnoise = -5dBm). The ground interconnect is the dominant path for substrate noise impact.

Figure 10

 10 Figure 10 Simulation of impact (at f c ±f noise ) of a -5 dBm substrate noise signal (1) on the real VCO, (2) a VCO layout with ground interconnect resistance reduced by half.For these results simulation requires approximately 35 minutes run time on an HP-UX L2000/4 (4 PA-8600 @ 540MHz) server (extraction time 20 minutes, simulation time 15 minutes for results in figure10).

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05) 1530-1591/05 $ 20.00 IEEE

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05)

Acknowledgements

The authors wish to tank the IWT Flanders for its financial support and D. Linten for designing the VCO.