Abstract
By mapping a fixed polarity Reed-Muller (RM) expression into an onset table and studying the properties of the onset table, an algorithm is proposed to obtain a compact multi-level single-output mixed-polarity RM function by searching for and extracting the common variables using the onset table. Furthermore, by employing the multiplexer model, the algorithm is extended to optimize multi-level multi-output mixed-polarity RM forms. The proposed algorithm is implemented in C language and tested using some MCNC benchmarks. Experimental results show that the proposed algorithm can obtain a more compact RM form than that under fixed polarity. Compared with published results, the proposed algorithm makes a significant speed improvement, with a small increase in the number of literals.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Al Jassani, B.A., Urquhart, N., Almaini, A.E.A., 2008. Optimization of MPRM functions using tabular techniques and genetic algorithms. Mediterr. J. Electron. Commun., 4(4):115–125.
Almaini, A.E.A., Thomson, P., Hanson, D., 1991. Tabular techniques for Reed-Muller logic. Int. J. Electron., 70(1):23–24. [doi:10.1080/00207219108921253]
Balasubramanian, P., Edwards, D.A., Narayanan, C.H., 2007. Low Power Synthesis of XOR-XNOR Intensive Combinational Logic. IEEE Conf. on Electrical and Computer Engineering, p.243–246. [doi:10.1109/CCECE.2007.66]
Green, D.H., 1990. Reed-Muller canonical forms with mixed polarity and their manipulations. IEE Proc. E: Comput. Dig. Techn., 137(1):103–113. [doi:10.1049/ip-e.1990.0010]
Gupta, P., Agrawal, A., Jha, N.K., 2006. An algorithm for synthesis of reversible logic circuits. IEEE Trans. Comput.-Aid. Des. Integr. Circ. Syst., 25(11):2317–2330. [doi:10.1109/TCAD.2006.871622]
Jankovic, D., Stankovic, R.S., Moraga, C., 2009. Optimization of polynomial expressions by using the extended dual polarity. IEEE Trans. Comput., 58(12):1710–1725. [doi:10.1109/TC.2009.113]
Pradhan, S.N., Chattopadhyay, S., 2008. Two-level AND-XOR networks synthesis with area-power trade-off. Int. J. Comput. Sci. Network Secur., 8(9):365–375.
Tran, A., Lee, E., 1993. Generalization of tri-state map and a composition method for minimization of Reed-Muller polynomials in mixed polarity. IEE Proc. E, 140(1): 59–64.
Tran, A., Wang, J., 1993. Decomposition method for minimization of Reed-Muller polynomials in mixed polarity. IEE Proc. E, 140(1):65–68.
Tsai, C.C., Marek-Sadowska, M., 1997. Boolean functions classifications via fixed polarity Reed-Muller forms. IEEE Trans. Comput., 46(2):173–186. [doi:10.1109/12.565592]
Wang, L., Almaini, A.E.A., 2002. Optimization of Reed-Muller PLA implementations. IEE Proc.-Circ. Dev. Syst., 149(2):119–128. [doi:10.1049/ip-cds:20020354]
Wang, L., Xia, Y., 2008. A Fast Algorithm for Multi-level Mixed-Polarity Reed-Muller Functions Optimization. 11th IEEE Int. Conf. on Communication and Technology, p.509–512. [doi:10.1109/ICCT.2008.4716096]
Wang, L., Xia, Y., Yang, M., Almaini, A.E.A., 2006. An approach to obtain compacted multi-level mixed polarity Reed-Muller functions. WSEAS Trans. Circ. Syst., 5(5): 625–632.
Xia, Y., Wang, L., Zhou, Z., Ye, X., Hu, J., Almaini, A.E.A., 2005. Novel synthesis and optimization of multi-level mixed polarity Reed-Muller functions. J. Comput. Sci. Technol., 20(6):895–900. [doi:10.1007/s11390-005-0895-2]
Author information
Authors and Affiliations
Corresponding author
Additional information
Project supported by the National Natural Science Foundation of China (Nos. 60871022 and 61041001), the Natural Science Foundation of Zhejiang Province (Nos. Z1090622 and Y1080654), and the Ningbo Natural Science Foundation, China (No. 2010A610183)
Rights and permissions
About this article
Cite this article
Wang, Ly., Xia, Ys., Chen, Xx. et al. Reed-Muller function optimization techniques with onset table. J. Zhejiang Univ. - Sci. C 12, 288–296 (2011). https://doi.org/10.1631/jzus.C1000193
Received:
Accepted:
Published:
Issue date:
DOI: https://doi.org/10.1631/jzus.C1000193