Full Text:
<2530>
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: 6403
Reed-Muller function optimization techniques with 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",
volume="12",
number="4",
pages="288-296",
year="2011",
publisher="Zhejiang University Press & Springer",
doi="10.1631/jzus.C1000193"
}
%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
TY - JOUR
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
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.
[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>