New techniques for selecting test frequencies for linear analog circuits

Mohand Bentobache; Ahcene Bounceur; Reinhardt Euler; Yann Kieffer; Salvador Mir

doi:10.1109/VLSI-SoC.2013.6673256

New techniques for selecting test frequencies for linear analog circuits

Mohand Bentobache, Ahcene Bounceur, Reinhardt Euler, Yann Kieffer, Salvador Mir

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

2 Scopus citations

Abstract

In this paper we show that the problem of minimizing the number of test frequencies necessary to detect all possible faults in a multi-frequency test approach for linear analog circuits can be modeled as a set covering problem. We will show in particular, that under some conditions on the considered faults, the coefficient matrix of the problem has the strong consecutive-ones property and hence the corresponding set covering problem can be solved in polynomial time. For an efficient solution of the problem, an interval graph formulation is also used and a polynomial algorithm using the interval graph structure is suggested. The optimization of test frequencies for a case-study biquadratic filter is presented for illustration purposes. Numerical simulations with a set of randomly generated problem instances demonstrate two different implementation approaches to solve the optimization problem very fast, with a good time complexity.

Original language	English
Title of host publication	2013 IFIP/IEEE 21st International Conference on Very Large Scale Integration, VLSI-SoC 2013 - Proceedings
Publisher	IEEE Computer Society
Pages	90-95
Number of pages	6
ISBN (Print)	9781479905249
DOIs	https://doi.org/10.1109/VLSI-SoC.2013.6673256
State	Published - 2013
Externally published	Yes

Publication series

Name	IEEE/IFIP International Conference on VLSI and System-on-Chip, VLSI-SoC
ISSN (Print)	2324-8432
ISSN (Electronic)	2324-8440

Keywords

Analog circuit testing
Consecutive-ones property
Interval graphs
Linear programming
Set covering problem

ASJC Scopus subject areas

Hardware and Architecture
Software
Electrical and Electronic Engineering

Access to Document

10.1109/VLSI-SoC.2013.6673256

Cite this

Bentobache, M., Bounceur, A., Euler, R., Kieffer, Y., & Mir, S. (2013). New techniques for selecting test frequencies for linear analog circuits. In 2013 IFIP/IEEE 21st International Conference on Very Large Scale Integration, VLSI-SoC 2013 - Proceedings (pp. 90-95). Article 6673256 (IEEE/IFIP International Conference on VLSI and System-on-Chip, VLSI-SoC). IEEE Computer Society. https://doi.org/10.1109/VLSI-SoC.2013.6673256

@inproceedings{5c0854620dba44bd89d66e918b519b98,

title = "New techniques for selecting test frequencies for linear analog circuits",

abstract = "In this paper we show that the problem of minimizing the number of test frequencies necessary to detect all possible faults in a multi-frequency test approach for linear analog circuits can be modeled as a set covering problem. We will show in particular, that under some conditions on the considered faults, the coefficient matrix of the problem has the strong consecutive-ones property and hence the corresponding set covering problem can be solved in polynomial time. For an efficient solution of the problem, an interval graph formulation is also used and a polynomial algorithm using the interval graph structure is suggested. The optimization of test frequencies for a case-study biquadratic filter is presented for illustration purposes. Numerical simulations with a set of randomly generated problem instances demonstrate two different implementation approaches to solve the optimization problem very fast, with a good time complexity.",

keywords = "Analog circuit testing, Consecutive-ones property, Interval graphs, Linear programming, Set covering problem",

author = "Mohand Bentobache and Ahcene Bounceur and Reinhardt Euler and Yann Kieffer and Salvador Mir",

year = "2013",

doi = "10.1109/VLSI-SoC.2013.6673256",

language = "English",

isbn = "9781479905249",

series = "IEEE/IFIP International Conference on VLSI and System-on-Chip, VLSI-SoC",

publisher = "IEEE Computer Society",

pages = "90--95",

booktitle = "2013 IFIP/IEEE 21st International Conference on Very Large Scale Integration, VLSI-SoC 2013 - Proceedings",

address = "United States",

}

Bentobache, M, Bounceur, A, Euler, R, Kieffer, Y & Mir, S 2013, New techniques for selecting test frequencies for linear analog circuits. in 2013 IFIP/IEEE 21st International Conference on Very Large Scale Integration, VLSI-SoC 2013 - Proceedings., 6673256, IEEE/IFIP International Conference on VLSI and System-on-Chip, VLSI-SoC, IEEE Computer Society, pp. 90-95. https://doi.org/10.1109/VLSI-SoC.2013.6673256

New techniques for selecting test frequencies for linear analog circuits. / Bentobache, Mohand; Bounceur, Ahcene; Euler, Reinhardt et al.
2013 IFIP/IEEE 21st International Conference on Very Large Scale Integration, VLSI-SoC 2013 - Proceedings. IEEE Computer Society, 2013. p. 90-95 6673256 (IEEE/IFIP International Conference on VLSI and System-on-Chip, VLSI-SoC).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - New techniques for selecting test frequencies for linear analog circuits

AU - Bentobache, Mohand

AU - Bounceur, Ahcene

AU - Euler, Reinhardt

AU - Kieffer, Yann

AU - Mir, Salvador

PY - 2013

Y1 - 2013

N2 - In this paper we show that the problem of minimizing the number of test frequencies necessary to detect all possible faults in a multi-frequency test approach for linear analog circuits can be modeled as a set covering problem. We will show in particular, that under some conditions on the considered faults, the coefficient matrix of the problem has the strong consecutive-ones property and hence the corresponding set covering problem can be solved in polynomial time. For an efficient solution of the problem, an interval graph formulation is also used and a polynomial algorithm using the interval graph structure is suggested. The optimization of test frequencies for a case-study biquadratic filter is presented for illustration purposes. Numerical simulations with a set of randomly generated problem instances demonstrate two different implementation approaches to solve the optimization problem very fast, with a good time complexity.

AB - In this paper we show that the problem of minimizing the number of test frequencies necessary to detect all possible faults in a multi-frequency test approach for linear analog circuits can be modeled as a set covering problem. We will show in particular, that under some conditions on the considered faults, the coefficient matrix of the problem has the strong consecutive-ones property and hence the corresponding set covering problem can be solved in polynomial time. For an efficient solution of the problem, an interval graph formulation is also used and a polynomial algorithm using the interval graph structure is suggested. The optimization of test frequencies for a case-study biquadratic filter is presented for illustration purposes. Numerical simulations with a set of randomly generated problem instances demonstrate two different implementation approaches to solve the optimization problem very fast, with a good time complexity.

KW - Analog circuit testing

KW - Consecutive-ones property

KW - Interval graphs

KW - Linear programming

KW - Set covering problem

UR - https://www.scopus.com/pages/publications/84899510332

U2 - 10.1109/VLSI-SoC.2013.6673256

DO - 10.1109/VLSI-SoC.2013.6673256

M3 - Conference contribution

AN - SCOPUS:84899510332

SN - 9781479905249

T3 - IEEE/IFIP International Conference on VLSI and System-on-Chip, VLSI-SoC

SP - 90

EP - 95

BT - 2013 IFIP/IEEE 21st International Conference on Very Large Scale Integration, VLSI-SoC 2013 - Proceedings

PB - IEEE Computer Society

ER -

Bentobache M, Bounceur A, Euler R, Kieffer Y, Mir S. New techniques for selecting test frequencies for linear analog circuits. In 2013 IFIP/IEEE 21st International Conference on Very Large Scale Integration, VLSI-SoC 2013 - Proceedings. IEEE Computer Society. 2013. p. 90-95. 6673256. (IEEE/IFIP International Conference on VLSI and System-on-Chip, VLSI-SoC). doi: 10.1109/VLSI-SoC.2013.6673256

New techniques for selecting test frequencies for linear analog circuits

Abstract

Publication series

Keywords

ASJC Scopus subject areas

Access to Document

Fingerprint

Cite this