Abstract
The binary decision diagrams (BDDs) can give canonical representation to Boolean functions; they have wide applications in the design and verification of digital systems. A new method based on cultural algorithms for minimizing the size of BDDs is presented in this paper. First of all, the coding of an individual representing a BDDs is given, and the fitness of an individual is defined. The population is built by a set of the individuals. Second, the implementations based on cultural algorithms for the minimization of BDDs, i.e., the designs of belief space and population space, and the designs of acceptance function and influence function, are given in detail. Third, the fault detection approaches using BDDs for digital circuits are studied. A new method for the detection of crosstalk faults by using BDDs is presented. Experimental results on a number of digital circuits show that the BDDs with small number of nodes can be obtained by the method proposed in this paper, and all test vectors of a fault in digital circuits can also be produced.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
K. Osnat. Reduction of average path length in binary decision diagrams by spectral methods. IEEE Transactions on Computers, vol. 57, no. 4, pp. 520–531, 2008.
D. Sawitzki. Lower bounds on the OBDD size of two fundamental functions’ graphs. Information Processing Letters, vol. 101, no. 2, pp. 66–71, 2007.
M. Matsuura, T. Sasao. BDD representation for incompletely specified multiple-output logic functions and its applications to the design of LUT cascades. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, vol. 90, no. 12, pp. 2762–2769, 2007.
R. S. Shelar, S. S. Sapatnekar. BDD decomposition for delay oriented pass transistor logic synthesis. IEEE Transactions on Very Large Scale Integration Systems, vol. 13, no. 8, pp. 957–970, 2005.
M. B. Song, H. Chang. A variable reordering method for fast optimization of binary decision diagrams. In Proceedings of the 6th Asian Test Symposium, Akita, Japan, pp. 228–233, 1997.
R. Ebendt, W. Gunther, R. Drechsler. Combining ordered best-first search with branch and bound for exact BDD minimization. IEEE Transactions on Computer-aided Design of Integrated Circuits and Systems, vol. 24, no. 10, pp. 1515–1529, 2005.
W. N. N. Hung, X. Song, E.M. Aboulhamid, M. A. Driscoll. BDD minimization by scatter search. IEEE Transactions on Computer-aided Design of Integrated Circuits and Systems, vol. 21, no. 8, pp. 974–979, 2002.
A. L. Oliveira, L. P. Carloni, T. Villa, A. L. Sangiovanni-Vincentelli. Exact minimization of binary decision diagrams using implicit techniques. IEEE Transactions on Computers, vol. 47, no. 11, pp. 1282–1296, 1998.
L. Heinrich-Litan, P. Molitor. Least upper bounds for the size of OBDDs using symmetry properties. IEEE Transactions on Computers, vol. 49, no. 4, pp. 360–368, 2000.
W. Gänther, R. Drechsler. Efficient minimization and manipulation of linearly transformed binary decision diagrams. IEEE Transactions on Computers, vol. 52, no. 9, pp. 1196–1209, 2003.
B. K. Kaushik, S. Sarkar. Crosstalk analysis for a CMOS-gate-driven coupled interconnects. IEEE Transactions on Computer-aided Design of Integrated Circuits and Systems, vol. 27, no. 6, pp. 1150–1154, 2008.
T. Ciamulski, W. K. Gwarek. Coupling compensation concept applied to crosstalk cancelling in multiconductor transmission lines. IEEE Transactions on Electromagnetic Compatibility, vol. 50, no. 2, pp. 437–441, 2008.
K. Agarwal, D. Sylvester, D. Blaauw. Modeling and analysis of crosstalk noise in coupled RLC interconnects. IEEE Transactions on Computer-aided Design of Integrated Circuits and Systems, vol. 25, no. 5, pp. 892–901, 2006.
M. S. Wu, C. L. Lee. Using a periodic square wave test signal to detect crosstalk faults. IEEE Design and Test of Computers, vol. 22, no. 2, pp. 160–169, 2005.
Z. Yang, S. Mourad. Crosstalk induced fault analysis and test in DRAMs. Journal of Electronic Testing: Theory and Applications, vol. 22, no. 2, pp. 173–187, 2006.
J. Liu, W. B. Jone, S. R. Das. Crosstalk test pattern generation for dynamic programmable logic arrays. IEEE Transactions on Instrumentation and Measurement, vol. 55, no. 4, pp. 1288–1302, 2006.
B. Bollig, I. Wegener. Improving the variable ordering of OBDDs is NP-complete. IEEE Transactions on Computers, vol. 45, no. 9, pp. 993–1002, 1996.
E. P. K. Tsang. Computational intelligence determines effective rationality. International Journal of Automation and Computing, vol. 5, no. 1, pp. 63–66, 2008.
C. A. C. Coello, R. L. Becerra. Evolutionary optimization through the use of a cultural algorithm. Engineering Optimization, vol. 36, no. 2, pp. 219–236, 2004.
F. G. Zhao, J. S. Sun, S. J. Li, W. M. Liu. A hybrid genetic algorithm for the traveling salesman problem with pickup and delivery. International Journal of Automation and Computing, vol. 6, no. 1, pp. 97–102, 2009.
T. K. Liu, C. H. Chen, Z. S. Li, J. H. Chou. Method of inequalities-based multiobjective genetic algorithm for optimizing a cart-double-pendulum system. International Journal of Automation and Computing, vol. 6, no. 1, pp. 29–37, 2009.
X. Yuan, Y. Yuan. Application of cultural algorithm to generation scheduling of hydrothermal systems. Energy Conversion and Management, vol. 47, no. 15–16, pp. 2192–2201, 2006.
K. I. Smith, E. M. Everson, J. E. Fieldsend. Dominancebased multi-objective simulated annealing. IEEE Transactions on Evolutionary Computation, vol. 12, no. 3, pp. 323–342, 2008.
D. J. Chen, C. Y. Lee, C. H. Park, P. Mendes. Parallelizing simulated annealing algorithms based on high-performance computer. Journal of Global Optimization, vol. 39, no. 2, pp. 261–289, 2007.
Author information
Authors and Affiliations
Corresponding author
Additional information
This work was supported by Natural Science Foundation of Guangdong Provincial of China (No. 7005833).
Zhong-Liang Pan received the M. Sc. degree from Tsinghua University, PRC in 1991, and the Ph.D. degree from University of Electronic Science and Technology of China, PRC in 1997. He is currently a professor with the South China Normal University, PRC.
His research interests include circuits and systems, very large scale integrated (VLSI) design and test, design for testability, and image processing.
Ling Chen received the B. Sc. degree in communication engineering from South China Normal University, PRC in 2004. She is currently an engineer with the South China Normal University.
Her research interests include circuits design and test, image processing, and intelligent information systems.
Guangzhao Zhang is currently a professor in the Department of Electronics and Communications at Sun Yat-sen University, PRC.
His research interests include computer networks, optoelectronics, multimedia and communication technology, and circuits and systems.
Rights and permissions
About this article
Cite this article
Pan, ZL., Chen, L. & Zhang, GZ. Cultural algorithm for minimization of binary decision diagram and its application in crosstalk fault detection. Int. J. Autom. Comput. 7, 70–77 (2010). https://doi.org/10.1007/s11633-010-0070-2
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11633-010-0070-2