{'fraction_non_alphanumeric': 0.042309541500939726, 'fraction_numerical': 0.011976047904191617, 'mean_word_length': 4.053003533568905, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 13, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Minimizing Test Frequencies for Linear Analog Circuits: New Models and Efficient Solution Methods

. This work presents new approaches to minimize the number of test frequencies for linear analog circuits. The cases of single and multiple fault detection regions for multiple test measures are considered. We ﬁrst address the case when the injected faults have a single detection region in the frequency band. We show that the problem can be formulated as a set covering problem with a matrix having the consecutive-ones property for which the network simplex algorithm turns out to be very ef ﬁcient. A second approach consists in modeling the problem by means of an interval graph, leading to its solution with a speciﬁc polynomial-time algorithm. A case-study of a biquadratic ﬁlter is presented for illustration purposes. Numerical simulations demonstrate that the two different approaches solve the optimization problem very fast. Finally, the optimization problems arising from multiple detection regions are modeled and solution approaches are discussed.


Introduction
Testing of analog circuits to verify their functionality is a time consuming and expensive task. In order to reduce costs, testing for the presence of faults that affect the device structure leads to more structured and cheaper test sets. Although the number of faults to be tested may indeed be very large, a reduced set of tests that are simple to apply may be sufficient to achieve high fault coverage values. There is today a pressing need from the Semiconductors Industry to provide these fault coverage measures and optimized tests, especially in the context of SoC (System-on-Chip) devices that embed digital and mixed-signal blocks in a single chip.
Multi-frequency tests (i.e., multi-tone sinusoidal signals) have been classically considered for the test and diagnosis of linear analog devices such as analog filters. Since the effect of parametric and catastrophic faults varies as a function of frequency, it is possible to derive a minimal set of test frequencies either for the detection or for the diagnosis of all potential faults. To optimize the set of test frequencies, the approaches based on sensitivity analysis have typically addressed parametric faults [1,2]. However, these approaches are not accurate for very large deviations, such as those that result from catastrophic faults. On the other hand, the approaches based on fault simulation can handle catastrophic faults, but at the expense of very time consuming simulations when realistic faults at transistor-level are considered. Today, it is evident that fault simulation of analog circuits is becoming essential in order to optimize test sets relying on new techniques to accelerate fault simulation.
In this context, this work proposes a new technique for the optimization of multifrequency tests for linear analog circuits. Fault simulation is used to obtain the frequency intervals for the detection of each fault. New efficient algorithms are then presented for the selection of the optimal set of test frequencies within these intervals for the detection of all faults. A simple case-study is used to illustrate the algorithms. Numerical simulations with randomly generated problem instances demonstrate the good time complexity of the proposed algorithms, with a large improvement over previous approaches [3]. We notice that the test optimization algorithms are general, applicable to any case-study requiring an optimization of multi-frequency tests based on fault simulation data. This technique is today feasible for analog filters, but it is also applicable to other analog devices such as analog-to-digital converters or radio-frequency front-ends requiring multi-tone tests, provided that fault simulation data are made available.
This work is organized as follows: in Section 2, the mathematical formulation of the Set Covering Problem (SCP) is reviewed and some definitions are given. In Section 3, we present the mathematical formulation of the problem of minimizing the number of frequency intervals necessary to detect the faults of an analog circuit, and we study the specific structure of the related coefficient matrix. In Section 4, we present two approaches for solving the problem: the Linear Programming (LP) approach and the interval graph approach, and a numerical example is given for illustration purposes. In Section 5, we present a mathematical formulation of the problem to minimize the number of test measures necessary for detecting the faults of an analog circuit. In Section 6, we present a case-study of testing a biquadratic filter. In Section 7, we carry out a large-scale numerical study in order to compare both approaches and to evaluate their time complexity. Finally, Section 8 concludes the work and provides some perspectives.

Overview
The Set Covering Problem is one of the most important models in combinatorial optimization. Indeed, a wide range of real-world problems can be modeled as SCP, namely: railway crew scheduling, airline crew scheduling, facility location, etc. The practical importance of the SCP has motivated many researchers to develop efficient algorithms and heuristics for finding good solutions in reasonable time. We can cite: exact algorithms based on branch-and-bound or branch-and-cut [4], greedy heuristics [5], Lagrangian-based heuristics [6], genetic algorithms [7], etc. In order to test the efficiency of the proposed algorithms, there exists a library of SCP Benchmarks (Beasley's OR Library [8]).
The set covering problem is known to be NP-hard [9]. However, there exist some particular forms of the SCP which are polynomial-time solvable such as the SCP with a constraint matrix having the consecutive-ones property (i.e., the ones in each row appear consecutively). This particular case, denoted in the following by SCP-C1P, can be solved efficiently with LP algorithms.

Some definitions
Let M = {1, . . . , m} and N = {1, . . . , n} be two sets of indices. Let A = (a ij , i ∈ M, j ∈ N ) be a binary (m × n)-matrix and c = (c j , j ∈ N ) be an integer n-vector. The value c j , j ∈ N, may represent the cost of column j. We assume without loss of generality that c j > 0 for all j ∈ N . We say that a column j ∈ N covers a row i ∈ M if a ij = 1. A set S ⊆ N is called a cover if each row i ∈ M is covered by at least one column j ∈ S. The problem of finding a cover S of minimum cost can be formulated as an ILP (Integer Linear Programming) problem as follows: where 1 m is the m-vector of ones. When c j = 1, for all j ∈ N , problem (1) is called a unicost set covering problem.

Minimization of test frequencies to detect all the faults of an analog circuit
In [3], the problem of selecting a minimum number of test frequencies is formally presented and solved using boolean expressions. However, when the number of faults is large, the technique used is not efficient. In this section, we present a mathematical formulation of the general problem as a set covering problem. We show that, under some special conditions on the considered faults, the coefficient matrix of the SCP will have the C1P. Moreover, we suggest an interval graph formulation of the problem.

Mathematical formulation of the problem as an SCP-C1P
Consider a given linear analog circuit C.
Then, we compute a set of n frequency intervals I = {I 1 , I 2 , . . . , I n } as follows: We denote by A = (a ij , i = 1, . . . , m, j = 1, . . . , n) the matrix which is defined as follows: The problem consists in finding a minimal-cardinality set of frequency intervals S ⊆ I which can detect all the possible considered faults. One frequency for each selected frequency interval (typically in the middle of the interval) can be used in the optimized test set. This problem can be formulated as a unicost set covering problem: for each S ⊆ I and each frequency interval I j , j ∈ {1, . . . , n}, we define a binary variable as follows: Now, if x = (x j , j = 1, . . . , n) is any vector of binary variables, then the mathematical model corresponding to this problem will be given by: , each fault has a unique detection region, then the matrix A will have the strong consecutive-ones property.
Proof. Let F i , i ∈ M, be a given detected fault and R i1 = [α i , β i ] be the unique detection region of fault i. By construction, R i1 can be written as a union of k consecutive intervals I j1 , I j2 , . . . , I j k , where α i is the lower bound of I j1 and β i is the upper bound of I j k . (Two intervals are consecutive if they have a common bound). Since the intervals I j r correspond to the consecutive columns a j r of A for r = 1, . . . , k, the detection regions correspond to the rows of A, and I j r ⊆ R i1 , i.e., a ij r = 1 for r = 1, . . . , k.
Note, that the previous proposition is very important because it gives a simple sufficient condition for the matrix arising in our application to have the strong C1P.
In the following we consider only problems with faults having one detection region. Following Proposition 1, ILP problem (6) is a unicost set covering problem with a coefficient matrix having the strong C1P (SCP-C1P). More precisely, it is given by: where for each row i, lx(i) denotes the leftmost index l for which a il = 1 and rx(i) the rightmost index r for which a ir = 1. To get the LP-relaxation of the above problem, we simply exchange the integrality constraints against the non-negativity constraints [11]. Thus, we get the following LP problem:

Graph formulation of the problem
Previously, we have formulated the problem of minimizing the number of frequency intervals to detect all the faults of an analog circuit using an ILP model. In this subsection, we suggest a new formulation based on the concept of interval graph: we denote the detection region of fault i by the interval [a i , b i ] for i ∈ M . Let the interval graph G = (F, E F ) be defined as follows: In the next section we will suggest a polynomial algorithm using this interval graph for solving the considered problem.

Approaches for solving the minimization problem of frequency intervals
In this section, we suggest two approaches for solving the problem of minimizing the number of frequency intervals necessary to detect all the faults of an analog circuit.

LP Approach
Let us recall the following results: Theorem 1. ( [12]). Any matrix A having the C1P fulfills the conditions of Theorem 1 and, hence, is totally unimodular.

An (m × n)-matrix A with entries 0, 1 and -1 is totally unimodular if and only if each collection of columns from A can be partitioned into two column sets such that in each
Following Theorem 2 and Remark 2, any basic feasible solution of the LP problem (8) represents a cover for the SCP-C1P (7). Therefore, we can find an optimal solution using LP algorithms such as the primal or dual simplex method [14], the support method [15], the hybrid direction algorithm [19], etc. However, it is more efficient to transform the SCP-C1P into a min-cost network flow problem [10].
Let us make the Veinott-Wagner transformations [20] for the variables of problem (8): we introduce the variables y j , j = 1, . . . , n + 1 such that x j = −y j + y j+1 , j = 1, . . . , n. Hence, we obtain the following equivalent LP problem: The dual of the above problem has m + n variables v 1 , v 2 , . . . , v m+n and n + 1 constraints and it is given by: where A = (a ij , i = 1, . . . , n + 1, j = 1, . . . , m + n), and A has exactly one 1 and one -1 in each column. Remark that the LP problem (11) is a min-cost network flow problem. Thus, it can be solved by the network simplex algorithm. The scheme of the LP approach to solve the problem is described in the following steps: Step 1. Compute the frequency intervals necessary to detect the different faults using relation (2); Step 2. Compute the constraint matrix of the SCP-C1P using relation (4) Step 5. Solve the min-cost network flow problem with the network simplex algorithm.

Interval graph approach
In order to solve the problem using the interval graph G defined by (9), we suggest the following algorithm: Algorithm 1 • Sort the vertices F i , i = 1, m by increasing order of their upper bounds b i ; • Compute the frequencies f k , k = 0, n with (2); The input of this polynomial algorithm is the interval graph G and the output is a minimal-cardinality set S of frequency intervals, which detects all the faults.
Note, that it is not necessary to construct the whole interval graph: we can use only its vertices, i.e., detection regions of the different faults, and replace the test "If F j is adjacent to F i in G" by the test "If a j < b i ≤ b j ".

Remark 3.
Contrarily to the LP approach, the interval graph approach uses the detection regions of the considered faults directly, i.e., without transforming the problem. In order to answer this question, we solve the following ILP problem:

Case of multiple detection regions
Let us illustrate this case by the following numerical example: The vector of frequencies computed by (2) Let us remark that this matrix loses the consecutive-ones property because the second row does not have consecutive ones. Therefore, we cannot apply the techniques suggested above to solve it. If this case occurs in practice, the branch-and-cut algorithm of CPLEX can be applied to solve the ILP problem. For this example, CPLEX gives us the optimal solution: x * = (1, 0, 0, 0, 0, 0, 1, 0, 0) T . So a minimal-cardinality set of frequency intervals is Remark 4. Although the constraint matrix of the previous SCP does not possess the consecutive-ones property, solving the LP relaxation gives us the optimal solution x * = (1, 0, 0, 0, 0, 0, 1, 0, 0) T . This means that for this type of problems the LP relaxation can give a good approximate solution for the optimal one (good upper bound for the optimal value). That is why we expect the branch-and-cut algorithm of CPLEX (or any other solver) to produce an optimal solution in a few iterations in case that the optimal solution of the LP-relaxation is not optimal for the SCP. Further numerical experiments have to be carried out in order to confirm this assertion.

Minimization of the number of test measures necessary for detecting all the faults of an analog circuit
Previously, we have assumed that only one test measure is used in the testing process. However, in practice, often we use several test measures. So if k is the number of the used test measures, we need to solve k SCPs for solving the problem of frequency interval minimization. Therefore, solving the problem of minimization of test measures beforehand can dramatically reduce the CPU time of solving the whole optimization process. Consider a given analog circuit C. Let F = {F 1 , F 2 , . . . , F m } be the set of all faults which can occur in C. Let T = {T 1 , T 2 , . . . , T k } be the set of k test measures to be used in the fault detection process. We denote by H = (h ij , i = 1, . . . , m, j = 1, . . . , k) the Fault-Test-Measure (FTM) matrix which is defined as follows: The problem consists in finding the minimal-cardinality set of test measures which can detect all the considered faults. This problem can also be formulated as a unicost set covering problem: for each test measure T j , j = 1, 2 . . . , k and any set S ⊆ T , we define a binary variable as follows: Hence, the mathematical model corresponding to this problem is given by: The optimal solution for this integer linear programming problem constitutes a desired minimal-cardinality set of test measures which detect all the faults. Note that, in general, the coefficient matrix of this problem does not have a specific structure, so the branchand-cut algorithm of CPLEX can be used to solve this problem. Once a minimal-cardinality set of test measures determined, we can solve the problem of frequency interval minimization for each test measure in this set.
The global optimization scheme for testing a linear analog circuit with multiple test measures is shown in Figure 1.

Case-study
To illustrate our approach, similar to [3], we will now present a case-study biquadratic filter as shown in Figure 2. There are 6 test measures for this circuit that correspond to the common-mode signal at the input and at the output of each operational amplifier.    Fig. 3. Output signals using test measure T 1 components are considered. Due to the differential design, only 16 different faults need to be considered.
We denote the test measures by T 1 , T 2 , . . . , T 6 and the faults by F 1 , F 2 , . . . , F 16 . Figure 3 shows the frequency behavior of test measure T 1 for some of these faults. The detection regions of each fault F i , i = 1, 2, . . . , 16 using test measures T j , j = 1, 2, . . . , 6 are computed using the fault simulator developed in [21,22]. Note, that the simulation results obtained in [21] indicate that test measures T 2 , T 4 and T 6 do not detect any fault. Hence, we only consider test measures T 1 , T 3 and T 5 . For simplicity also, we have only considered nominal simulations of the catastrophic faults. In practice, Monte Carlo simulations of each catastrophic fault should be considered, and worstcase detection regions be computed (that is, the intersection of the detection regions for each Monte Carlo instance).
First, we start by minimizing the number of test measures necessary for the detection of the sixteen faults. Following simulation results, test measure T 1 detects the faults: F 1 , F 2 , . . . , F 8 ; T 3 detects the faults F 9 , F 10 , F 11 , F 12 and T 5 detects the faults   10 5 ] .
When we sort in increasing order the bounds of the different detection regions, we find the following vector of frequencies: where each row i, i = 1, . . . , 8, corresponds to the detection region R i1 and each column j, j = 1, . . . , 9, to the frequency interval I j .
Since the matrix A has the consecutive-ones property (each fault has a unique detection region), the optimal solution of the SCP (6) can be obtained using the network simplex algorithm. In our example, this leads to the following optimal solution: x * = (0, 0, 0, 1, 0, 0, 0, 0) T and r * = 1, i.e., a minimal-cardinality set of intervals detecting all the faults is S = {I 4 }. Therefore, it is sufficient to use a single test frequency belonging to the interval [647Hz, 1014Hz[ to detect all the faults F 1 , F 2 , . . . , F 8 .
Similarly, when we use the test measure T 3 , we detect the faults F 9 , F 10 , F 11 and Hence, for the test measure T 3 , the solution of the SCP (6)

The constraint matrix of the SCP is
Thus, for the test measure T 5 , the solution is obvious again, that is, the frequency interval which detects all the faults F 13 , F 14 , F 15 and F 16 is I 1 = [1Hz, 1412Hz[, and a single test frequency belonging to this interval is required.

Numerical experiments
In order to compare the efficiency of the two approaches presented in Section 4 (LP approach and the interval graph one), we have implemented them in C++ programming language and carried out large-scale numerical experiments on a set of randomly generated test instances using an Intel(R) Core(TM)2 Duo CPU P8600 @ 2.40GHz machine with 4 GB of RAM.
The detection region bounds are generated in the interval [1Hz, 10 5 Hz]. For each class of test problems with m faults, we generate ten problems. We have solved the different instances with the LP approach (LPA) using the network simplex method of the LP and ILP solver CPLEX [23] and the suggested interval graph algorithm (IGA). The CPU time of the two approaches IGA and LPA are reported in Table 1.
Let [a i , b i ] be the detection regions of the faults F i , i = 1, . . . , m. In the following, we give the implementation details for the LP approach: Step 1. Compute the set of frequency intervals I as follows: - -for i = m + 1, . . . , n + 1; for j = 1, . . . , m + n: Step 4. Compute the constraint matrix A , the (n + 1)-vector of right-hand-sides b and the cost (m + n)-vector c of the min-cost network flow problem (11): Step 5. Solve the min-cost network flow problem with the network simplex algorithm.
Note, that the efficient implementation presented above computes the constraint matrices of the SCP-C1P and the min-cost network flow problem of the LP approach in small CPU times (less than 1 second on average for all the test problems). That is why we have not reported the CPU times of computing the constraint matrices of the SCP-C1P and the min-cost network flow problem in Table 1.
The average optimal values found by the two approaches IGA and LPA for the different test problems are shown in column OptVal. We compute the ratios of the CPU time of IGA over LPA. These ratios are shown in column CPU Ratio. Finally, the CPU time of the two approaches are plotted in Figure 4. The LPA shows a time complexity O(m), while IGA shows a time complexity O(m 2 ), where m is the number of faults.
The graphs of Figure 4 indicate that transforming the problem into a min-cost network flow problem and solving it with the network simplex algorithm is more efficient than the interval graph algorithm. Indeed, LPA is, on average, two times faster than IGA. However, the computation time is very small even for problems with an extremely large number of faults. Therefore, the interval graph algorithm can also be used in practice by test engineers because of its simple implementation; the good CPU times (an average of 16 seconds for optimizing the test of analog circuits with 1,000,000 faults); and the fact that it solves the original problem directly.

Conclusion
In this work, we have formulated as an SCP the problem of minimizing the number of test frequencies necessary to detect a set of faults injected into an analog circuit. We have shown that when the considered faults have a unique detection region, the constraint matrix of the SCP will have the strong consecutive-ones property. After that, we have reformulated this special case using interval graphs and an algorithm working directly with this graph is suggested. In order to solve the problem efficiently, two approaches are compared: an LP approach and an interval graph approach. The obtained numerical results show that the approach which transforms the problem into a mincost network flow problem to solve it by the network simplex algorithm is the most efficient. However, the interval graph approach can also be used by test engineers because it solves the original problem directly; its implementation is very simple and it is extremely fast with CPU times of a few tenths of seconds even for large-scale problems. Moreover, the optimization problem associated with multiple detection regions and multiple test measures is studied. Future work will focus on developing a branchand-cut algorithm for solving efficiently the set covering problem corresponding to the case of multiple detection regions.