Full Text:   <2012>

CLC number: TP391

On-line Access: 2011-04-11

Received: 2010-06-12

Revision Accepted: 2010-11-30

Crosschecked: 2011-03-01

Cited: 4

Clicked: 4724

Citations:  Bibtex RefMan EndNote GB/T7714

-   Go to

Article info.
1. Reference List
Open peer comments

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

Lun-yao Wang, Yin-shui Xia, Xie-xiong Chen, A. E. A. Almaini. Reed-Muller function optimization techniques with onset table[J]. Journal of Zhejiang University Science C, 2011, 12(4): 288-296.

@article{title="Reed-Muller function optimization techniques with onset table",
author="Lun-yao Wang, Yin-shui Xia, Xie-xiong Chen, A. E. A. Almaini",
journal="Journal of Zhejiang University Science C",
publisher="Zhejiang University Press & Springer",

%0 Journal Article
%T Reed-Muller function optimization techniques with onset table
%A Lun-yao Wang
%A Yin-shui Xia
%A Xie-xiong Chen
%A A. E. A. Almaini
%J Journal of Zhejiang University SCIENCE C
%V 12
%N 4
%P 288-296
%@ 1869-1951
%D 2011
%I Zhejiang University Press & Springer
%DOI 10.1631/jzus.C1000193

T1 - Reed-Muller function optimization techniques with onset table
A1 - Lun-yao Wang
A1 - Yin-shui Xia
A1 - Xie-xiong Chen
A1 - A. E. A. Almaini
J0 - Journal of Zhejiang University Science C
VL - 12
IS - 4
SP - 288
EP - 296
%@ 1869-1951
Y1 - 2011
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/jzus.C1000193

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.

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


[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


Please provide your name, email address and a comment

Journal of Zhejiang University-SCIENCE, 38 Zheda Road, Hangzhou 310027, China
Tel: +86-571-87952783; E-mail: cjzhang@zju.edu.cn
Copyright © 2000 - 2022 Journal of Zhejiang University-SCIENCE