SHORTEST SYNCHRONIZING SEQUENCE SEARCH FOR A SEQUENTIAL NETWORK WITH MEMORY ON D FLIP-FLOPS
Abstract
The problem under consideration is to find a synchronizing sequence of a minimal size for a logical network having flipflop primitives of type D as memory elements. A novel method is proposed, which is based on the formulation of the task as the Boolean satisfiability problem solved with any standard SAT-solver. The method is based on forming the conventional conjunctive normal form representation for combinational block, implementing excitation functions of the flip-flops.
About the Author
L. D. Cheremisinova
United Institute of Informatics Problems of the National Academy of Sciences of Belarus, Minsk
Belarus
Belarus
References
1. Strunz, B. Design for Testability in Digital Integrated circuits [Electronic resourсe] / B. Strunz , C. Flanagan , T. Hall ; University of Limerick, Ireland. – Mode of access: http://www.cs.colostate.edu/~cs530/digital_testing.pdf. – Date of access: 01.07.2015.
2. Logic BIST: State-of-the-Art and Open Problems [Electronic resourсe] / N. Li [et al.]. – Mode of access: http://arxiv.org/ pdf/1503.04628.pdf. – Date of access: 01.07.2015.
3. Chakrabarty, K. DFBT: A Design-for-Testability Method Based on Balance Testing [Electronic resourсe] / K. Chakrabarty, P. Hayes; Department of Electrical Engineering and Computer Science University of Michigan. – Mode of access: http://citeseerx. ist.psu.edu/viewdoc/download?doi=10.1.1.380.9873&rep=rep1&type=pdf. – Date of access: 01.07.2015.
4. Rene, D. Random testing of digital circuits. Theory and application / D. Rene. – [S. l.]: Marcel Dekker, Inc. 1998.
5. Crouch, A. Design-for-Test for Digital IC’s and Embedded Core Systems / A. Crouch. – [S. l.]: Prentice Hall, 1999.
6. Bushnell, M. L. Essentials of electronic testing for digital, memory and mixed-signal VLSI circuits / M. L. Bushnell, V. D. Agrawal. – [S. l.]: Kluwer Academic Publishers, 2002.
7. Kohavi, Z. Switching and Finite Automata Theory / Z. Kohavi. – 2nd ed. – Cambridge [et al.]: Cambridge Univ. Press, 1978.
8. Gill, A. Introduction to the Theory of Finite-state Machines / A. Gill. – [S. l.]: McGraw-Hill, 1962.
9. Lee, D. Principles and methods of testing finite state machine – a survey / D. Lee, M. Yannakakis // Proc. of the IEEE. – 1996. – Vol. 84 (8). – P. 1090–1123.
10. Eppstein, D. Reset sequences for monotonic automata / D. Eppstein // SIAM J. on Computing. – 1990. – Vol. 19, no. 3. – P. 500–510.
11. Biere, A. PicoSAT essentials / A. Biere // J. on Satisfiability. Boolean Modeling and Computation. – 2008. – Vol. 4. – P. 75–97.
12. Mahajan, Y. Zchaff 2004: an efficient SAT solver / Y. Mahajan, Z. Fu, S. Malik // Theory and Applications of Satisfiability Testing (2004 SAT Solver Competition and QBF Solver Evaluation (Invited Papers)). – Berlin; Heidelberg: Springer, 2005. – P. 360–375.
13. Goldberg, E. BerkMin: afast and robust SAT-solver / E. Goldberg, Y. Novikov // 2002 Design, Automation and Test in Europe Conference and Exposition (DATE 2002), 4–8 March 2002, Paris, France. – [S. l.]: IEEE Computer Society, 2002. – P. 142–149.
14. Kuehlmann, A. Combinational and Sequential Equivalence Checking / A. Kuehlmann A., C. A. J. van Eijk. // Logic synthesis and Verification / eds S. Hassoun, T. Sasao, R. K. Brayton. – [S. l.]: Kluwer Academic Publishers, 2002. – P. 343–372.
Review
Views: 416
Email this article 