SEMICONDUCTOR INTEGRATED CIRCUITS

Discrete ternary particle swarm optimization for area optimization of MPRM circuits

Haizhen Yu, Pengjun Wang, Disheng Wang and Huihong Zhang

+ Author Affiliations

 Corresponding author: Wang Pengjun, Email:wangpengjun@nbu.edu.cn;memaid0126@hotmail.com

PDF

Abstract: Having the advantage of simplicity, robustness and low computational costs, the particle swarm optimization (PSO) algorithm is a powerful evolutionary computation tool for synthesis and optimization of Reed-Muller logic based circuits. Exploring discrete PSO and probabilistic transition rules, the discrete ternary particle swarm optimization (DTPSO) is proposed for mixed polarity Reed-Muller (MPRM) circuits. According to the characteristics of mixed polarity OR/XNOR expression, a tabular technique is improved, and it is applied in the polarity conversion of MPRM functions. DTPSO is introduced to search the best polarity for an area of MPRM circuits by building parameter mapping relationships between particles and polarities. The computational results show that the proposed DTPSO outperforms the reported method using maxterm conversion starting from POS Boolean functions. The average saving in the number of terms is about 11.5%; the algorithm is quite efficient in terms of CPU time and achieves 12.2% improvement on average.

Key words: area optimizationDTPSO algorithmMPRM circuitspolarity conversion



[1]
Qu L, Feng K, Liu F, et al. Constructing symmetric Boolean functions with maximum algebraic immunity. IEEE Trans Information on Information Theory, 2009, 55(5):4206 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.150.5131&or=1
[2]
Mozammel H, Khan A. An ASIC architecture for generating optimum mixed polarity Reed-Muller expression. Eng Lett, 2006, 13(3):1 http://www.oalib.com/paper/2835502
[3]
Yang M, Xu H, Almaini A E A. Optimization of mixed polarity Reed-Muller functions using genetic algorithm. The 3rd International Conference on Computer Research and Development, Shanghai, China, 2011:293 http://ieeexplore.ieee.org/xpl/articleDetails.jsp?reload=true&arnumber=5412318
[4]
Wang L, Almaini A E A. Efficient polarity conversion for large Boolean functions. IEE Proc Comput Digit Tech, 1999, 146(4):197 doi: 10.1049/ip-cdt:19990525
[5]
Wang Pengjun, Lu Jingang, Chen Ken, et al. Low power polarity conversion based on the whole annealing genetic algorithm. Journal of Semiconductors, 2008, 29(2):298 http://www.jos.ac.cn/bdtxbcn/ch/reader/view_abstract.aspx?file_no=07051302&flag=1
[6]
Falkowski B J, Chang C H. Generalized k-variable-mixed-polarity Reed-Muller expansions for system of boolean functions and their minimization. IEEE Proc Circuits Devices Syst, 2000, 147(4):201 doi: 10.1049/ip-cds:20000588
[7]
Tan E, Yang H. Optimization of fixed-polarity Reed-Muller circuits using dual-polarity property. Circuits, Systems, and Signal Processing, 2000, 19(6):535 doi: 10.1007/BF01271287
[8]
Al Jassani B A, Urquhart N, Almaini A E A. Minimization of incompletely specified mixed polarity Reed-Muller functions using genetic algorithm. International Conference on Signals, Circuits and Systems, 2009:1 http://web.cecs.pdx.edu/~mperkows/CAPSTONES/HAAR/PRIP'99.pdf
[9]
Wang Pengjun, Li Hui. Low power mapping for AND-XOR circuits and its application in searching the best mixed-polarity. Journal of Semiconductors, 2011, 32(2):025007 doi: 10.1088/1674-4926/32/2/025007
[10]
Green D H. Dual forms of Reed Muller expansions. IEE Proc Comput Digit Tech, 1994, 141(3):184 doi: 10.1049/ip-cdt:19941097
[11]
Finder A, Drechsler R. An evolutionary algorithm for optimization of pseudo kronecker expression. 40th IEEE International Symp on Multi-Valued Logic, Barcelona, Spain, 2010:150 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.637.7742
[12]
Al Jassani B A, Urquhart N, Almaini A E A. Manipulation and optimisation techniques for Boolean logic. IET Computers & Digital Techniques, 2010, 4(3):227
[13]
Kennedy J, Eberhart R. Particle swarm optimization. Proceedings of the IEEE International Conference on, Neural Networks, Washington, DC, USA, 1995:1942
[14]
Cheng J, Chen X, Faraj K M. Expansion of logical function in the OR-coincidence system and the transform between it and maxterm expansion. Computers and Digital Techniques, 2003, 150(6):397 doi: 10.1049/ip-cdt:20030969
[15]
Zhang X Y, Wang L L, Zhou X G. Efficient RM conversion algorithm for large multiple output functions. ICSICT, 2008:2300 http://sme.fudan.edu.cn/faculty/personweb/wanglingli/pdf/Fast%20Conversion%20Algorithm%20for%20Very%20Large%20Boolean%20Functions.pdf
[16]
Wang Pengjun, Chen Xiexiong. Tabular techniques for OR-coincidence logic. Journal of Electronics, 2006, 23(2):269 doi: 10.1007%2Fs11767-005-0081-2.pdf
[17]
Li Li, Niu Beng. Particle swarm optimization algorithm. 1st ed. Peking:Metallurgical Industry Press, 2009(in Chinese)
[18]
Kennedy J, Eberhart R. A discrete binary version of the particle swarm algorithm. Proc IEEE Int Conf Systems, Man, Cybernetics, 1997:4104 http://citeseerx.ist.psu.edu/showciting?cid=103970
Fig. 1.  Mixed polarity conversion using a tabular technique.

Fig. 2.  DTPSO algorithm for minimizing the area of MPRM circuits.

Fig. 3.  Optimal curves of DTPSO, DPSO and GA[12] for MPRM circuits.

Table 1.   Comparison results.

[1]
Qu L, Feng K, Liu F, et al. Constructing symmetric Boolean functions with maximum algebraic immunity. IEEE Trans Information on Information Theory, 2009, 55(5):4206 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.150.5131&or=1
[2]
Mozammel H, Khan A. An ASIC architecture for generating optimum mixed polarity Reed-Muller expression. Eng Lett, 2006, 13(3):1 http://www.oalib.com/paper/2835502
[3]
Yang M, Xu H, Almaini A E A. Optimization of mixed polarity Reed-Muller functions using genetic algorithm. The 3rd International Conference on Computer Research and Development, Shanghai, China, 2011:293 http://ieeexplore.ieee.org/xpl/articleDetails.jsp?reload=true&arnumber=5412318
[4]
Wang L, Almaini A E A. Efficient polarity conversion for large Boolean functions. IEE Proc Comput Digit Tech, 1999, 146(4):197 doi: 10.1049/ip-cdt:19990525
[5]
Wang Pengjun, Lu Jingang, Chen Ken, et al. Low power polarity conversion based on the whole annealing genetic algorithm. Journal of Semiconductors, 2008, 29(2):298 http://www.jos.ac.cn/bdtxbcn/ch/reader/view_abstract.aspx?file_no=07051302&flag=1
[6]
Falkowski B J, Chang C H. Generalized k-variable-mixed-polarity Reed-Muller expansions for system of boolean functions and their minimization. IEEE Proc Circuits Devices Syst, 2000, 147(4):201 doi: 10.1049/ip-cds:20000588
[7]
Tan E, Yang H. Optimization of fixed-polarity Reed-Muller circuits using dual-polarity property. Circuits, Systems, and Signal Processing, 2000, 19(6):535 doi: 10.1007/BF01271287
[8]
Al Jassani B A, Urquhart N, Almaini A E A. Minimization of incompletely specified mixed polarity Reed-Muller functions using genetic algorithm. International Conference on Signals, Circuits and Systems, 2009:1 http://web.cecs.pdx.edu/~mperkows/CAPSTONES/HAAR/PRIP'99.pdf
[9]
Wang Pengjun, Li Hui. Low power mapping for AND-XOR circuits and its application in searching the best mixed-polarity. Journal of Semiconductors, 2011, 32(2):025007 doi: 10.1088/1674-4926/32/2/025007
[10]
Green D H. Dual forms of Reed Muller expansions. IEE Proc Comput Digit Tech, 1994, 141(3):184 doi: 10.1049/ip-cdt:19941097
[11]
Finder A, Drechsler R. An evolutionary algorithm for optimization of pseudo kronecker expression. 40th IEEE International Symp on Multi-Valued Logic, Barcelona, Spain, 2010:150 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.637.7742
[12]
Al Jassani B A, Urquhart N, Almaini A E A. Manipulation and optimisation techniques for Boolean logic. IET Computers & Digital Techniques, 2010, 4(3):227
[13]
Kennedy J, Eberhart R. Particle swarm optimization. Proceedings of the IEEE International Conference on, Neural Networks, Washington, DC, USA, 1995:1942
[14]
Cheng J, Chen X, Faraj K M. Expansion of logical function in the OR-coincidence system and the transform between it and maxterm expansion. Computers and Digital Techniques, 2003, 150(6):397 doi: 10.1049/ip-cdt:20030969
[15]
Zhang X Y, Wang L L, Zhou X G. Efficient RM conversion algorithm for large multiple output functions. ICSICT, 2008:2300 http://sme.fudan.edu.cn/faculty/personweb/wanglingli/pdf/Fast%20Conversion%20Algorithm%20for%20Very%20Large%20Boolean%20Functions.pdf
[16]
Wang Pengjun, Chen Xiexiong. Tabular techniques for OR-coincidence logic. Journal of Electronics, 2006, 23(2):269 doi: 10.1007%2Fs11767-005-0081-2.pdf
[17]
Li Li, Niu Beng. Particle swarm optimization algorithm. 1st ed. Peking:Metallurgical Industry Press, 2009(in Chinese)
[18]
Kennedy J, Eberhart R. A discrete binary version of the particle swarm algorithm. Proc IEEE Int Conf Systems, Man, Cybernetics, 1997:4104 http://citeseerx.ist.psu.edu/showciting?cid=103970
  • Search

    Advanced Search >>

    GET CITATION

    shu

    Export: BibTex EndNote

    Article Metrics

    Article views: 1887 Times PDF downloads: 11 Times Cited by: 0 Times

    History

    Received: 20 June 2012 Revised: 02 August 2012 Online: Published: 01 February 2013

    Catalog

      Email This Article

      User name:
      Email:*请输入正确邮箱
      Code:*验证码错误
      Haizhen Yu, Pengjun Wang, Disheng Wang, Huihong Zhang. Discrete ternary particle swarm optimization for area optimization of MPRM circuits[J]. Journal of Semiconductors, 2013, 34(2): 025011. doi: 10.1088/1674-4926/34/2/025011 H Z Yu, P J Wang, D S Wang, H H Zhang. Discrete ternary particle swarm optimization for area optimization of MPRM circuits[J]. J. Semicond., 2013, 34(2): 025011. doi: 10.1088/1674-4926/34/2/025011.Export: BibTex EndNote
      Citation:
      Haizhen Yu, Pengjun Wang, Disheng Wang, Huihong Zhang. Discrete ternary particle swarm optimization for area optimization of MPRM circuits[J]. Journal of Semiconductors, 2013, 34(2): 025011. doi: 10.1088/1674-4926/34/2/025011

      H Z Yu, P J Wang, D S Wang, H H Zhang. Discrete ternary particle swarm optimization for area optimization of MPRM circuits[J]. J. Semicond., 2013, 34(2): 025011. doi: 10.1088/1674-4926/34/2/025011.
      Export: BibTex EndNote

      Discrete ternary particle swarm optimization for area optimization of MPRM circuits

      doi: 10.1088/1674-4926/34/2/025011
      Funds:

      the S & T Plan of Ningbo University xkl089

      Project supported by the National Natural Science Foundation of China (No. 61076032), the S & T Plan of Zhejiang Provincial Science and Technology Department (No. 2010C31012), the S & T Plan of Zhejiang Provincial Education Department (No.Y201016317), the S & T Plan of Ningbo University (No. xkl089), and the K. C. Wong Magna Fund in Ningbo University

      the S & T Plan of Zhejiang Provincial Science and Technology Department 2010C31012

      the S & T Plan of Zhejiang Provincial Education Department Y201016317

      the K. C. Wong Magna Fund in Ningbo University. 

      the National Natural Science Foundation of China 61076032

      More Information
      • Corresponding author: Wang Pengjun, Email:wangpengjun@nbu.edu.cn;memaid0126@hotmail.com
      • Received Date: 2012-06-20
      • Revised Date: 2012-08-02
      • Published Date: 2013-02-01

      Catalog

        /

        DownLoad:  Full-Size Img  PowerPoint
        Return
        Return