An efficient transformation method for DFRM expansions.

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

Abstract

Dual Form of Reed-Muller (DFRM) expansions with fixed poarity are derived from Reed-Muller (RM) expansions by using the operation of Kronecker matrix products. An efficient decomposition method is proposed based on the formulation. The method can be used for the trasnformation from DFRM expansions to RM expnsions within the same fixed polarity as well. Hence, the proposed method is bidirectional. After decomposition, the calculation of the duplicated matrix is avoided, resulting in less computation time. Time complexity
of the algorithm is O(2 to the power 1.5n). The time used for small variables is virtually zero for the tested MCNC benchmark. For large variables, it still works very well and achieves less than 20 seconds for the 25-variable benchmark. In the implementation, only on-set coefficients are used. Consequently, the space complexity is O(M), where M is the number of on-set coefficients. It makes simultaneous optimization in both RM and DFRM expansions possible.

Citation

Xu, H., Yang, M., Wang, L. Y., Tong, J. R., & Almaini, A. E. A. (2007, October). An efficient transformation method for DFRM expansions

• Start Date: Oct 22, 2007
• End Date: Oct 25, 2007
• Publication Date: Oct 26, 2007
• Deposit Date: May 4, 2009
• Peer Reviewed: Peer Reviewed
• Pages: 1158-1161
• Book Title: 7th International Conference on ASIC, 2007. ASICON '07
• ISBN: 978-1-4244-1132-0
• DOI: https://doi.org/10.1109/ICASIC.2007.4415839
• Keywords: Integrated circuits; Logic circuits; Power supply; Dual Form Reed-Muller; Transformation methods; Computational speed
• Public URL: http://researchrepository.napier.ac.uk/id/eprint/2565
• Publisher URL: http://dx.doi.org/10.1109/ICASIC.2007.4415839