Cultural Algorithm for Minimization of Binary Decision Diagram and Its Application in Crosstalk Fault Detection

Zhong-Liang Pan Ling Chen Guang-Zhao Zhang

Zhong-Liang Pan, Ling Chen, Guang-Zhao Zhang. Cultural Algorithm for Minimization of Binary Decision Diagram and Its Application in Crosstalk Fault Detection[J]. 国际自动化与计算杂志(英)/International Journal of Automation and Computing, 2010, 7(1): 70-77. doi: 10.1007/s11633-010-0070-2
引用本文: Zhong-Liang Pan, Ling Chen, Guang-Zhao Zhang. Cultural Algorithm for Minimization of Binary Decision Diagram and Its Application in Crosstalk Fault Detection[J]. 国际自动化与计算杂志(英)/International Journal of Automation and Computing, 2010, 7(1): 70-77. doi: 10.1007/s11633-010-0070-2
Zhong-Liang Pan, Ling Chen and Guang-Zhao Zhang. Cultural Algorithm for Minimization of Binary Decision Diagram and Its Application in Crosstalk Fault Detection. International Journal of Automation and Computing, vol. 7, no. 1, pp. 70-77, 2010 doi:  10.1007/s11633-010-0070-2
Citation: Zhong-Liang Pan, Ling Chen and Guang-Zhao Zhang. Cultural Algorithm for Minimization of Binary Decision Diagram and Its Application in Crosstalk Fault Detection. International Journal of Automation and Computing, vol. 7, no. 1, pp. 70-77, 2010 doi:  10.1007/s11633-010-0070-2

Cultural Algorithm for Minimization of Binary Decision Diagram and Its Application in Crosstalk Fault Detection

doi: 10.1007/s11633-010-0070-2
基金项目: 

supported by Natural Science Foundation of Guangdong Provincial of China (No.7005833)

Cultural Algorithm for Minimization of Binary Decision Diagram and Its Application in Crosstalk Fault Detection

Funds: 

supported by Natural Science Foundation of Guangdong Provincial of China (No.7005833)

More Information
    Author Bio:

    Ling Chen received the B.Sc.degree in communication engineering from South China Normal University,PRC in 2004.

    Corresponding author: Zhong-Liang Pan received the M.Sc. degree from Tsinghua University,PRC in 1991,and the Ph.D.
  • 摘要: 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.
  • [1] K.Osnat.Reduction of average path length in binary deci-sion diagrams by spectral methods.IEEE Transactions on Computers,vol.57,no.4,pp.520-531,2008.
    [2] D.Sawitzki.Lower bounds on the OBDD size of two funda-mental functions graphs.Information Processing Letters, vol.101,no.2,pp.66-71,2007.
    [3] M.Matsuura,T.Sasao.BDD representation for incom-pletely specified multiple-output logic functions and its ap-plications to the design of LUT cascades.IEICE Transac-tions on Fundamentals of Electronics,Communications and Computer Sciences,vol.90,no.12,pp.2762-2769,2007.
    [4] 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.
    [5] R.Ebendt,W.Gunther,R.Drechsler.Combining ordered best-first search with branch and bound for exact BDD min-imization.IEEE Transactions on Computer-aided Design of Integrated Circuits and Systems,vol.24,no.10,pp.1515-1529,2005.
    [6] 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.
    [7] A.L.Oliveira,L.P.Carloni,T.Villa,A.L.Sangiovanni-Vincentelli.Exact minimization of binary decision diagrams using implicit techniques.IEEE Transactions on Comput-ers,vol.47,no.11,pp.1282-1296,1998.
    [8] L.Heinrich-Litan,P.Molitor.Least upper bounds for the size of OBDDs using symmetry properties.IEEE Transac-tions on Computers,vol.49,no.4,pp.360-368,2000.
    [9] W.Ga¨nther,R.Drechsler.E?cient minimization and ma-nipulation of linearly transformed binary decision diagrams. IEEE Transactions on Computers,vol.52,no.9,pp.1196-1209,2003.
    [10] 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.
    [11] T.Ciamulski,W.K.Gwarek.Coupling compensation con-cept applied to crosstalk cancelling in multiconductor trans-mission lines.IEEE Transactions on Electromagnetic Com-patibility,vol.50,no.2,pp.437-441,2008.
    [12] K.Agarwal,D.Sylvester,D.Blaauw.Modeling and anal-ysis of crosstalk noise in coupled RLC interconnects.IEEE Transactions on Computer-aided Design of Integrated Cir-cuits and Systems,vol.25,no.5,pp.892-901,2006.
    [13] 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.
    [14] 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.
    [15] J.Liu,W.B.Jone,S.R.Das.Crosstalk test pattern genera-tion for dynamic programmable logic arrays.IEEE Transac-tions on Instrumentation and Measurement,vol.55,no.4, pp.1288-1302,2006.
    [16] 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.
    [17] E.P.K.Tsang.Computational intelligence determines ef-fective rationality.International Journal of Automation and Computing,vol.5,no.1,pp.63-66,2008.
    [18] C.A.C.Coello,R.L.Becerra.Evolutionary optimization through the use of a cultural algorithm.Engineering Opti-mization,vol.36,no.2,pp.219-236,2004.
    [19] F.G.Zhao,J.S.Sun,S.J.Li,W.M.Liu.A hybrid ge-netic algorithm for the traveling salesman problem with pickup and delivery.International Journal of Automation and Computing,vol.6,no.1,pp.97-102,2009.
    [20] K.I.Smith,E.M.Everson,J.E.Fieldsend.Dominance-based multi-objective simulated annealing.IEEE Transac-tions on Evolutionary Computation,vol.12,no.3,pp.323-342,2008.
    [21] 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.
  • [1] Yu Zhang, Chris Bingham, Mike Garlick, Michael Gallimore.  Applied Fault Detection and Diagnosis for Industrial Gas Turbine Systems . International Journal of Automation and Computing, 2017, 14(4): 463-473. doi: 10.1007/s11633-016-0967-5
    [2] Sunil Nilkanth Pawar, Rajankumar Sadashivrao Bichkar.  Genetic Algorithm with Variable Length Chromosomes for Network Intrusion Detection . International Journal of Automation and Computing, 2015, 12(3): 337-342. doi: 10.1007/s11633-014-0870-x
    [3] Yuan-Qing Xia, Yu-Long Gao, Li-Ping Yan, Meng-Yin Fu.  Recent Progress in Networked Control Systems-A Survey . International Journal of Automation and Computing, 2015, 12(4): 343-367. doi: 10.1007/s11633-015-0894-x
    [4] René Lozi.  Designing Chaotic Mathematical Circuits for Solving Practical Problems . International Journal of Automation and Computing, 2014, 11(6): 588-597. doi: 10.1007/s11633-014-0839-9
    [5] Nassim Laouti, Sami Othman, Mazen Alamir, Nida Sheibat-Othman.  Combination of Model-based Observer and Support Vector Machines for Fault Detection of Wind Turbines . International Journal of Automation and Computing, 2014, 11(3): 274-287. doi: 10.1007/s11633-014-0790-9
    [6] Roland E. Best, Nikolay V. Kuznetsov, Gennady A. Leonov, Marat V. Yuldashev, Renat V. Yuldashev.  Simulation of Analog Costas Loop Circuits . International Journal of Automation and Computing, 2014, 11(6): 571-579. doi: 10.1007/s11633-014-0846-x
    [7] Hai-Gang Guo, Bao-Jie Zhang.  Observer-based Variable Universe Adaptive Fuzzy Controller Without Additional Dynamic Order . International Journal of Automation and Computing, 2014, 11(4): 418-425. doi: 10.1007/s11633-014-0808-3
    [8] Qing-Yu Su, Yan-Cheng Li, Xing-Ze Dai, Jian Li.  Fault Detection for a Class of Impulsive Switched Systems . International Journal of Automation and Computing, 2014, 11(2): 223-230. doi: 10.1007/s11633-014-0784-7
    [9] Yu-Yan Zhang,  Jun-Ling Zhang,  Xiao-Yuan Luo,  Xin-Ping Guan.  Sensor/Actuator Faults Detection for Networked Control Systems via Predictive Control . International Journal of Automation and Computing, 2013, 10(3): 173-180. doi: 10.1007/s11633-013-0710-4
    [10] Analysis of Nonlinear Electrical Circuits Using Bernstein Polynomials . International Journal of Automation and Computing, 2012, 9(1): 81-86. doi: 10.1007/s11633-012-0619-3
    [11] Sami E. I. Baba,  Lala Z. Krikor,  Thawar Arif,  Zyad Shaaban.  Watermarking of Digital Images in Frequency Domain . International Journal of Automation and Computing, 2010, 7(1): 17-22. doi: 10.1007/s11633-010-0017-7
    [12] Xiao-Fen Wang, Ying-Rui Liu, Wen-Sheng Zhang.  Research on Modelling Digital Paper-cut Preservation . International Journal of Automation and Computing, 2009, 6(4): 356-363. doi: 10.1007/s11633-009-0356-4
    [13] An Imperfect-debugging Fault-detection Dependent-parameter Software . International Journal of Automation and Computing, 2007, 4(4): 325-328. doi: 10.1007/s11633-007-0325-8
    [14] Mohamed-Faouzi Harkat,  Salah Djelel,  Noureddine Doghmane,  Mohamed Benouaret.  Sensor Fault Detection, Isolation and Reconstruction Using Nonlinear Principal Component Analysis . International Journal of Automation and Computing, 2007, 4(2): 149-155. doi: 10.1007/s11633-007-0149-6
    [15] Marek Kowal,  Józef Korbicz.  Fault Detection under Fuzzy Model Uncertainty . International Journal of Automation and Computing, 2007, 4(2): 117-124. doi: 10.1007/s11633-007-0117-1
    [16] Sing Kiong Nguang, Ping Zhang, Steven X. Ding.  Parity Relation Based Fault Estimation for Nonlinear Systems: An LMI Approach . International Journal of Automation and Computing, 2007, 4(2): 164-168. doi: 10.1007/s11633-007-0164-7
    [17] Ping Zhang,  Steven X. Ding.  A Model-free Approach to Fault Detection of Continuous-time Systems Based on Time Domain Data . International Journal of Automation and Computing, 2007, 4(2): 189-194. doi: 10.1007/s11633-007-0189-y
    [18] Bibhrajit Halder,  Nilanjan Sarkar.  Robust Nonlinear Analytic Redundancy for Fault Detection and Isolation in Mobile Robot . International Journal of Automation and Computing, 2007, 4(2): 177-182. doi: 10.1007/s11633-007-0177-2
    [19] James F. Whidborne, John McKernan, Da-Wei Gu.  Kolmogorov-Chaitin Complexity of Digital Controller Implementations . International Journal of Automation and Computing, 2006, 3(3): 314-322. doi: 10.1007/s11633-006-0314-3
    [20] Min-Ze Chen,  Qi Zhao,  Dong-Hua Zhou.  A Robust Fault Detection Approach for Nonlinear Systems . International Journal of Automation and Computing, 2006, 3(1): 23-28. doi: 10.1007/s11633-006-0023-y
  • 加载中
计量
  • 文章访问数:  4113
  • HTML全文浏览量:  36
  • PDF下载量:  2503
  • 被引次数: 0
出版历程
  • 收稿日期:  2009-03-03
  • 修回日期:  2009-03-26
  • 刊出日期:  2010-01-15

Cultural Algorithm for Minimization of Binary Decision Diagram and Its Application in Crosstalk Fault Detection

doi: 10.1007/s11633-010-0070-2
    基金项目:

    supported by Natural Science Foundation of Guangdong Provincial of China (No.7005833)

    作者简介:

    Ling Chen received the B.Sc.degree in communication engineering from South China Normal University,PRC in 2004.

摘要: 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.

English Abstract

Zhong-Liang Pan, Ling Chen, Guang-Zhao Zhang. Cultural Algorithm for Minimization of Binary Decision Diagram and Its Application in Crosstalk Fault Detection[J]. 国际自动化与计算杂志(英)/International Journal of Automation and Computing, 2010, 7(1): 70-77. doi: 10.1007/s11633-010-0070-2
引用本文: Zhong-Liang Pan, Ling Chen, Guang-Zhao Zhang. Cultural Algorithm for Minimization of Binary Decision Diagram and Its Application in Crosstalk Fault Detection[J]. 国际自动化与计算杂志(英)/International Journal of Automation and Computing, 2010, 7(1): 70-77. doi: 10.1007/s11633-010-0070-2
Zhong-Liang Pan, Ling Chen and Guang-Zhao Zhang. Cultural Algorithm for Minimization of Binary Decision Diagram and Its Application in Crosstalk Fault Detection. International Journal of Automation and Computing, vol. 7, no. 1, pp. 70-77, 2010 doi:  10.1007/s11633-010-0070-2
Citation: Zhong-Liang Pan, Ling Chen and Guang-Zhao Zhang. Cultural Algorithm for Minimization of Binary Decision Diagram and Its Application in Crosstalk Fault Detection. International Journal of Automation and Computing, vol. 7, no. 1, pp. 70-77, 2010 doi:  10.1007/s11633-010-0070-2
参考文献 (21)

目录

    /

    返回文章
    返回