Please wait a minute...
Front. Inform. Technol. Electron. Eng.  2011, Vol. 12 Issue (4): 288-296    DOI: 10.1631/jzus.C1000193
    
Reed-Muller function optimization techniques with onset table
Lun-yao Wang*,1,2, Yin-shui Xia2, Xie-xiong Chen1, A. E. A. Almaini3
1 Department of Information Science and Electronic Engineering, Zhejiang University, Hangzhou 310027, China 2 Faculty of Information Science and Engineering, Ningbo University, Ningbo 315211, China 3 School of Engineering, Napier University, Edinburgh EH10 5DT, UK
Download:   PDF(224KB)
Export: BibTeX | EndNote (RIS)      

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.

Key wordsLogic optimization      Reed-Muller functions      Multi-level      Mixed polarity      Onset table     
Received: 12 June 2010      Published: 11 April 2011
CLC:  TP391  
Cite this article:

Lun-yao Wang, Yin-shui Xia, Xie-xiong Chen, A. E. A. Almaini. Reed-Muller function optimization techniques with onset table. Front. Inform. Technol. Electron. Eng., 2011, 12(4): 288-296.

URL:

http://www.zjujournals.com/xueshu/fitee/10.1631/jzus.C1000193     OR     http://www.zjujournals.com/xueshu/fitee/Y2011/V12/I4/288


Reed-Muller function optimization techniques with onset table

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.

关键词: Logic optimization,  Reed-Muller functions,  Multi-level,  Mixed polarity,  Onset table 
[1] Wen-jia LIU, Xiao-lin HOU, Lan CHEN. Enhanced uplink non-orthogonal multiple access for 5G and beyond systems[J]. Front. Inform. Technol. Electron. Eng., 2018, 19(3): 340-356.