ZHANG Qiaowen, WANG Pengjun, HU Jiang, ZHANG Huihong. Cube-Based Synthesis of ESOPs for Large Functions[J]. Chinese Journal of Electronics, 2018, 27(3): 527-534. doi: 10.1049/cje.2018.01.006
Citation: ZHANG Qiaowen, WANG Pengjun, HU Jiang, ZHANG Huihong. Cube-Based Synthesis of ESOPs for Large Functions[J]. Chinese Journal of Electronics, 2018, 27(3): 527-534. doi: 10.1049/cje.2018.01.006

Cube-Based Synthesis of ESOPs for Large Functions

doi: 10.1049/cje.2018.01.006
Funds:  This work is supported by the Natural Science Foundation of Zhejiang Province (No.LY14F040002, No.16F010005), the National Natural Science Foundation of China (No.61474068, No.61234002), the Natural Science Foundation of Ningbo City (No.2013A610006, No.2013A610008), and the K. C. Wong Magna Fund in Ningbo University.
More Information
  • Corresponding author: WANG Pengjun (corresponding author) was born in 1966. He received the Ph.D. degree in electronic engineering from East China University of Chemical Technology. He is now a professor of Ningbo University. His research interests include multi-valued logic circuits and low power integrated circuit design theory. (Email:wangpengjun@nbu.edu.cn)
  • Received Date: 2017-06-20
  • Rev Recd Date: 2017-09-19
  • Publish Date: 2018-05-10
  • This study focuses on low-complexity synthesis of Exclusive-or sum-of-products expansions (ESOPs). A scalable cube-based method, which only uses iterative executions of cube intersection and subcover minimization for cube set expressions, is presented to obtain quasi-optimal ESOPs for completely specified multi-output functions. For deriving canonical Reed-Muller (RM) forms, four conversion rules of cubes are proposed to achieve fast conversion between a canonical form and an Exclusiveor sum-of-products (ESOP) or between different canonical forms. Numerical examples are given to verify the correctness of cube-based minimization and conversion methods. The proposed methods have been implemented in C language and tested on a large set of MCNC benchmark functions (ranging from 5 to 201 inputs). Experimental results show that, compared with existing methods, ours can reduce the number of cubes by 27% and save the CPU time by 74% on average in the final solution of minimization, and consume less time as well during the conversion process. As a whole, our methods are efficient in terms of both memory space and CPU time and can be able to deal with very large functions.
  • loading
  • Z.X. He, L.M. Xiao, R. Li, et al., "A power and area optimization approach of mixed polarity Reed-Muller expression for incompletely specified Boolean functions", Journal of Computer Science & Technology, Vol.32, No.2, pp.297-311, 2017.
    W.W. Shan, X. Chen, Y.C. Liu, et al., "A novel combinatoricsbased reconfigurable bit permutation network and its circuit implementation", Chinese Journal of Electronics, Vol.24, No.3, pp.513-517, 2015.
    N. Tara and H.M.H. Babu, "Synthesis of reversible PLA using products sharing", Journal of Computational Electronics, Vol.15, No.2, pp.420-428, 2016.
    M. Soeken, R. Wille, O. Keszocze, et al., "Embedding of large Boolean functions for reversible logic", ACM Journal on Emerging Technologies in Computing Systems, Vol.12, No.4, pp.41-53, 2016.
    K. Datta, I. Sengupta and H. Rahaman, "A post-synthesis optimization technique for reversible circuits exploiting negative control lines", IEEE Transactions on Computers, Vol.64, No.4, pp.1208-1214, 2015.
    M. Chrzanowskajeske, A. Mishchenko and M. Perkowski, "Generalized inclusive forms-new canonical Reed-Muller forms including minimum ESOPs", VLSI Design, Vol.14, No.1, pp.13-21, 2002.
    T. Hirayama, M. Takahashi and Y. Nishitani, "Simplification of exclusive-or sum-of-products expressions through function transformation", Proc. of the IEEE Asia-Pacific Conference on Circuits and Systems, Singapore, pp.1482-1485, 2006.
    B.J. Falkowski and C.H. Chang, "An efficient algorithm for the calculation of generalized adding and arithmetic transforms from disjoint cubes of Boolean functions", VLSI Design, Vol.9, No.2, pp.135-146, 2007.
    A. Mishchenko and M. Perkowski, "Fast heuristic minimization of exclusive-sums-of-products", Proc. of 5th Int. Workshop on Applications of the Reed Muller Expansion in Circuit Design, Mississippi, USA, pp.242-250, 2001.
    T. Hirayama and Y. Nishitani, "Exact minimization of ANDEXOR expressions of practical benchmark functions", Journal of Circuits Systems & Computers, Vol.18, No.3, pp.465-486, 2009.
    M. Sampson, M. Kalathas, D. Voudouris, et al., "Exact ESOP expressions for incompletely specified functions", Integration, the VLSI Journal, Vol.45, No.2, pp.197-204, 2012.
    G. Papakonstantinou, "A parallel algorithm for minimizing ESOP expressions", Journal of Circuits Systems & Computers, Vol.23, No.1, pp.72-85, 2014.
    G. Papakonstantinou, "Exclusive or sum of complex terms expressions minimization", Integration, the VLSI Journal, Vol.56, pp.44-52, 2017.
    L. Wang and A.E.A. Almaini, "Fast conversion algorithm for very large Boolean functions", Electronics Letters, Vol.36, No.16, pp.1370-1371, 2000.
    P.J. Wang, et al., "Conversion algorithm for MPRM expansion", Journals of Semiconductors, Vol.35, No.3, pp.150-155, 2014.
    D.L. Bu and J.H. Jiang, "Dual logic based polarity conversion and optimization of mixed polarity RM circuits", Acta Electronica Sinica, Vol.43, No.1, pp.79-85, 2015. (in Chinese)
    A. Bossard and K. Kaneko, "k-pairwise disjoint paths routing in perfect hierarchical hypercubes", The Journal of Supercomputing, Vol.67, No.2, pp.485-495, 2014.
  • 加载中


    通讯作者: 陈斌, bchen63@163.com
    • 1. 

      沈阳化工大学材料科学与工程学院 沈阳 110142

    1. 本站搜索
    2. 百度学术搜索
    3. 万方数据库搜索
    4. CNKI搜索

    Article Metrics

    Article views (126) PDF downloads(166) Cited by()
    Proportional views


    DownLoad:  Full-Size Img  PowerPoint