Cube-Based Synthesis of ESOPs for Large Functions

ZHANG Qiaowen; WANG Pengjun; HU Jiang; ZHANG Huihong

doi:10.1049/cje.2018.01.006

Volume 27 Issue 3

Turn off MathJax

Article Contents

Article Navigation > Chinese Journal of Electronics > 2018 > 27(3): 527-534

ZHANG Qiaowen, WANG Pengjun, HU Jiang, et al., “Cube-Based Synthesis of ESOPs for Large Functions,” Chinese Journal of Electronics, vol. 27, no. 3, pp. 527-534, 2018, doi: 10.1049/cje.2018.01.006

Citation:

ZHANG Qiaowen, WANG Pengjun, HU Jiang, et al., “Cube-Based Synthesis of ESOPs for Large Functions,” Chinese Journal of Electronics, vol. 27, no. 3, pp. 527-534, 2018, doi: 10.1049/cje.2018.01.006

ZHANG Qiaowen, WANG Pengjun, HU Jiang, et al., “Cube-Based Synthesis of ESOPs for Large Functions,” Chinese Journal of Electronics, vol. 27, no. 3, pp. 527-534, 2018, doi: 10.1049/cje.2018.01.006

Citation:

PDF( 344 KB)

Cube-Based Synthesis of ESOPs for Large Functions

doi: 10.1049/cje.2018.01.006

1.
Institute of Circuits and Systems, Ningbo University, Ningbo 315211, China;
2.
Ningbo Key Laboratory of Digital Signal Processing, Zhejiang Wanli University, Ningbo 315100, China

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

Abstract

Abstract

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.
- Logic synthesis,
- Exclusive-or sum-ofproducts (ESOP),
- Canonical forms,
- Large functions

FullText(HTML)

References(17)

References

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.

Relative Articles

Supplements(0)

Cited By

Proportional views