Research Output

An efficient transformation method for DFRM expansions.

  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). An efficient transformation method for DFRM expansions. In 7th International Conference on ASIC, 2007. ASICON '07, 1158-1161. doi:10.1109/ICASIC.2007.4415839. ISBN 978-1-4244-1132-0

Authors

Keywords

Integrated circuits; Logic circuits; Power supply; Dual Form Reed-Muller; Transformation methods; Computational speed;

Available Documents