Open Access Open Access  Restricted Access Subscription or Fee Access

Equivalence Verification of the Digital Circuits with the Strategy of the Simulating Annealing

R. Zouaoui, N. Khalfaoui

Abstract


In this paper new algorithm for the verification of the equivalence of the sequential digital circuits is proposed in which it allocated a combinational block and a block from the state of the elements represented by D-triggers. In the construction of evaluation functions using the task of modeling of a circuit intact or defective. This is done by breaking the feedback lines and using an iterative modeling of combinatorial equivalent. This algorithm is based on a new strategy for the evolution of simulated annealing. This approach uses an iterative improvement of the properties of the one input sequence. The algorithm is presented as an iterative process for improving the properties of a potential solution. The exact formal verification of ownership equivalence is a difficult mathematical problem, for this reason we have reformulated the opposite: we show the non-equivalence of scheme. Fault-free simulation of the digital circuits is used for the estimating the quality of the potential solutions. The effectiveness of the proposed algorithm is shown by its approbation on the ISCAS-89 benchmarks.


Keywords


Simulating Annealing, Genetic Algorithms, Verification of the Equivalence, Digital Circuits, Parallel Modeling

Full Text:

PDF

References


Niermann T., Patel J.H. HITEC: A Test Generation Package for Sequential Circuits // Proc. European Design Automation Conf. – 1991. – Р. 214-218.

Ghosh, A., S. Devadas and A. R. Newton. Sequential Logic Testing and Verification. – Kluwer Academic Publishers. – 1992. – 214p.

Corno F., Prinetto P., Rebaudengo M., Sonza Reorda M., GATTO: a Genetic Algorithm for Automatic Test Pattern Generation for Large Synchronous Sequential Circuits // IEEE Transactions on Computer-Aided Design, August 1996. – Vol. 15, №8. – Р. 943-951.

Niermann T.M., Cheng W.-T., Patel J.H. PROOFS: A Fast, Memory-Efficient Sequential Circuits Fault Simulator // IEEE Trans. CAD. – 1992.– P.198-207.

Goldberg D.E., Genetic Algorithm in Search, Optimization, and Machine Learning. – Addison- Wesley. – 1989.

Y.A Ckobtsov. "The principles of calculating the evolution." - Donetsk: DonNTU, 2008. - PP.326.

.E Ivanov, YA Ckobtsov. Test generation for digital devices using genetic algorithms // Proceedings of the Institute of Applied Mathematics and Mechanics NAN UKRAINE – Т.4. – Donetsk, IPMM. – 1999. – PP.82-88.

D.E Ivanov, Y.A Ckobtsov, A.I EL-Khatib, “The construction of initialization sequences for synchronous digital circuits using genetic algorithms. The problems of information technologies”. -2007. – N°1 pp. 158-164.

D.E Ivanov. The genetic approach to the verification of the equivalence of Sequential Circuits // Radioelectronics. Informatics. Office - Zaparojia, ZNTU. – 2009. – №1(20). – PP.118-123.

Metropolis N., Rosenbluth A.W., Rosenbluth M.N., Teller A.H., Teller E., Equation of State Calculation by Fast Computing Mashines. // J. of Chem.Phys. – 1953. – Vol.21, No.6. – Р.1087-1092.

Kirkpatrick S., Gelatt C.D., Vecchi M.P. Optimization by simulating annealing. // Science, 220. – 1983. – Р.671-680.

Cerny V. Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm. // J. Optim. Theory Appl. – 1985. – v.45. – Р.41-51.

D.E Ivanov, P Zouaoui. Applying a simulated annealing strategy for the problem of initialization sequences construction of digital circuits // Bulletin of the East-Ukrainien National University named V.Dalia. 2009. Vol.1(131), part 2.– PP.161-168.

R. ZOUAOUI, N. KHALFAOUI. Implementation of Simulated Annealing Strategies for the Initialization Sequences Construction of Digital Circuits // “CiiT International Journals of Artificial Intelligent Systems and Machine Learning” Vol 4, No 5, May 2012, pp.271-275

A.S Barashko, Y.A Ckobtsov, D.V Cperancki. Modeling and testing of discrete devices. – Kiev: Scientific Thought, 1992. – PP 288.

Brgles F., Bryan D., Kozminski K. Combinational profiles of sequential benchmark circuits // International symposium of circuits and systems, ISCAS-89.– 1989.– Р.1929-1934.

F. Corno, M. Sonza Reorda, G. Squillero VEGA: A Verification Tool Based on Genetic Algorithms // ICCD98, International Conference on Circuit Design, Austin, Texas (USA). – 1998. – Р.321-326.

Shi-Yu Huang, Kwang-Ting Cheng , Kuang-Chien Chen, Forrest Brewer, Chung-Yang Huang, AQUILA: An Equivalence Checking System for Large Sequential Designs. // IEEE Transactions on Computers. – 2000. – v.49, N.5. – Р.443-464,.

Y.S Zatouliver, E.A Fitshenko Computer PC 2000: Multiprocessor architecture, outstripped time // Plenary and selected papers of the 4th International Conference "Parallel Computing and Control Problems", Moscow, 27-29 October 2008.

V.P Guerguel., R.G Strongin. Introduction to the Parallel Programming for a multiprocessor computing systems. Textbook. - Nizhny Novgorod Acad NNSU. NI Lobachevsky, 2003. – PP 184.


Refbacks

  • There are currently no refbacks.