Exact minimization of large fixed polarity dual form of reed-muller functions

Yang, Meng; Xu, H; Wang, Lun Yao; Tong, Jiarong R; Almaini, A E A

Abstract

Dual form of Reed-Muller (DFRM) expansions are implemented in OX/XNOR logic, which are based on the features of coincidence operation and are known as fixed polarity Canonical OR-Coincidence (COC) expansions. An efficient minimization method is proposed to find the best polarity COC expansion for large functions. The method derives one expansion from another adjacent polarity expansion using gray code, resulting in small space complexity O(M) and time complexity O(2nthMlogM), where n and M are the number of input variables and the number of on-set COC maxterms. Hence, it makes minimization for large functions practical.

Citation

Yang, M., Xu, H., Wang, L. Y., Tong, J. R., & Almaini, A. E. A. (2007). Exact minimization of large fixed polarity dual form of reed-muller functions. Solid-State and Integrated Circuit Technology, 1931-1933. https://doi.org/10.1109/ICSICT.2006.306532

• Journal Article Type: Article
• Publication Date: 2007
• Deposit Date: Apr 17, 2009
• Peer Reviewed: Peer Reviewed
• Pages: 1931-1933
• DOI: https://doi.org/10.1109/ICSICT.2006.306532
• Keywords: Integrated circuits; Computer logic; Boolean algebra; Data processing; Optimization
• Public URL: http://researchrepository.napier.ac.uk/id/eprint/2551
• Publisher URL: http://dx.doi.org/10.1109/ICSICT.2006.306532