JZUS - Journal of Zhejiang University SCIENCE

Journal of Zhejiang University SCIENCE C 2011 Vol.12 No.4 P.288-296

Reed-Muller function optimization techniques with onset table

Author(s): Lun-yao Wang, Yin-shui Xia, Xie-xiong Chen, A. E. A. Almaini
Affiliation(s): Department of Information Science and Electronic Engineering, Zhejiang University, Hangzhou 310027, China, Faculty of Information Science and Engineering, Ningbo University, Ningbo 315211, China, School of Engineering, Napier University, Edinburgh EH10 5DT, UK
Corresponding email(s): wanglunyao@nbu.edu.cn
Key Words: Logic optimization, Reed-Muller functions, Multi-level, Mixed polarity, Onset table

Share this article to： More <<< Previous Article \|Next Article >>>

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.

Reference

[1]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.

[2]Almaini, A.E.A., Thomson, P., Hanson, D., 1991. Tabular techniques for Reed-Muller logic. Int. J. Electron., 70(1):23-24.

[3]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.

[4]Green, D.H., 1990. Reed-Muller canonical forms with mixed polarity and their manipulations. IEE Proc. E: Comput. Dig. Techn., 137(1):103-113.

[5]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.

[6]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.

[7]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.

[8]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.

[9]Tran, A., Wang, J., 1993. Decomposition method for minimization of Reed-Muller polynomials in mixed polarity. IEE Proc. E, 140(1):65-68.

[10]Tsai, C.C., Marek-Sadowska, M., 1997. Boolean functions classifications via fixed polarity Reed-Muller forms. IEEE Trans. Comput., 46(2):173-186.

[11]Wang, L., Almaini, A.E.A., 2002. Optimization of Reed-Muller PLA implementations. IEE Proc.-Circ. Dev. Syst., 149(2):119-128.

[12]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.

[13]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.

[14]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.

Open peer comments: Debate/Discuss/Question/Opinion

<1>

Similar articles

- Go to

Darkslateblue:Affiliate; Royal Blue:Author; Turquoise:Article

Reference