A Mathematical Framework for Online Constant Coefficient Multiplication
Single and Multiple constant multiplications are key operations in several digital signal processing algorithms. This paper develops a mathematical framework for a novel adaptation of the parallel shift-and-add multiplication algorithm for online arithmetic. Based on this adaptation, online constant coefficient multipliers for single constant multiplication (SCM) and multiple constant multiplications (MCM) of streaming floating-point inputs are presented. A finite impulse response filter implementation on Xilinx Virtex 6 Field programmable gate array (FPGA) is used as an example to illustrate the merits of these filters. The results of this implementation show that online multipliers reduce resource utilization, online delay and increase clock frequency in comparison to existing designs. Online multiple constant multipliers also show an average reduction of 65% in the number of slice LUTs and 37% in the number of slice registers required when compared to existing digit-serial multiple constant multipliers. Thus, the proposed online arithmetic operators appear to be good alternatives for constant coefficient multiplication
D. R. Bull and D. H. Horrocks, “Primitive operator digital filters,” IEE Proceedings G - Circuits, Devices and Systems, vol. 138, no. 3, pp. 401-412, June 1991.
A. G. Dempster and M. D. Macleod, “Constant integer multiplication using minimum adders,” IEE Proceedings - Circuits, Devices and Systems, vol. 141, no. 5, pp. 407-413, October 1994.
Y. Voronenko and M. Püschel, “Multiplierless multiple constant multiplication,” ACM Transactions on Algorithms, vol. 3, no. 2, p. 11, May 2007.
L. Aksoy, E. Costa, P. Flores, and J. Monteiro, “Exact and approximate algorithms for the optimization of area and delay in multiple constant multiplications,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 27, no. 6, pp. 1013-1026, June 2008.
L. Aksoy, E. O. Güneş, and P. Flores, “Search algorithms for the multiple constant multiplications problem: exact and approximate,” Microprocessors and Microsystems, vol. 34, no. 5, pp. 151-162, August 2010.
L. Aksoy, E. Costa, P. Flores, and J. Monteiro, “Finding the optimal tradeoff between area and delay in multiple constant multiplications,” Microprocessors and Microsystems, vol. 35, no. 8, pp. 729-741, November 2011.
L. Aksoy, C. Lazzari, E. Costa, P. Flores, and J. Monteiro, “Optimization of area in digit-serial multiple constant multiplications at gate-level,” Proc. IEEE Symp. Circuits and Systems (ISCAS 2011), IEEE Press, May 2011, pp. 2737-2740.
L. Aksoy, C. Lazzari, E. Costa, P. Flores, and J. Monteiro, “High-level algorithms for the optimization of gate-level area in digit-serial multiple constant multiplications,” Integration, the VLSI Journal, vol. 45, no. 3, pp. 294-306, June 2012.
K. Johansson, O. Gustafsson, A. Dempster, and L. Wanhammar, “Algorithm to reduce the number of shifts and additions in multiplier blocks using serial arithmetic,” Proc. IEEE Mediterranean Electrotechnical Conference, IEEE press, May 2004, pp. 197-200.
K. Johansson, O. Gustafsson, and L. Wanhammar, “Multiple constant multiplication for digit-serial implementation of low power FIR filters,” WSEAS Transactions on Circuits and Systems, vol. 5, no. 7, pp. 1001-1008, July 2006.
W. Vanderbauwhede and K. Benkrid, High-performance computing using FPGAs, New York: Springer, 2013.
M. Kumm, K. Liebisch, and P. Zipf, “Reduced complexity single and multiple constant multiplication in floating point precision,” Proc. Conf. Field Programmable Logic and Applications (FPL 2012), IEEE press, August 2012, pp. 255-261.
M. Faust and C. H. Chang, “Bit-parallel multiple constant multiplication using look-up tables on FPGA,” Proc. IEEE Symp. Circuits and Systems (ISCAS 2011), IEEE press, May 2011, pp. 657-660.
Q Wang, Y Li, B Shao, S Dey, and P Li, “Energy efficient parallel neuromorphic architectures with approximate arithmetic on FPGA, “ Neurocomputing, vol. 221, pp. 146-158, January 2017.
R. Zendegani, M. Kamal, M. Bahadori, A. Afzali-Kusha, and M. Pedram, “RoBA multiplier: A rounding-based approximate multiplier for high-speed yet energy-efficient digital signal processing,” Transactions on Very Large Scale Integration (VLSI) Systems, vol. 25, no. 2, pp. 393-401, February 2017.
G. B. Joseph and R. Devanathan, “Radix-2h online floating point multipliers,” Proc. IEEE Conf. Dallas Circuits and Systems (DCAS 14), IEEE press, October 2014, pp. 1-4.
J. Olivares, J. Hormigo, J. Villalba, I. Benavides, E. L. Zapata, “SAD computation based on online arithmetic for motion estimation,” Microprocessors and Microsystems, vol. 30, no. 5, pp. 250-258, August 2006.
M. Faust and C. H. Chang, “Minimal logic depth adder tree optimization for multiple constant multiplication,” Proc. IEEE Symp. Circuits and Systems (ISCAS 2010), IEEE press, May-June 2010, pp. 457-460.
Copyright (c) 2017 International Journal of Engineering and Technology Innovation
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
Submission of a manuscript implies: that the work described has not been published before that it is not under consideration for publication elsewhere; that if and when the manuscript is accepted for publication. Authors can retain copyright in their articles with no restrictions. Also, author can post the final, peer-reviewed manuscript version (postprint) to any repository or website.
Since Jan. 01, 2019, IJETI will publish new articles with Creative Commons Attribution Non-Commercial License, under Creative Commons Attribution Non-Commercial 4.0 International (CC BY-NC 4.0) License.
The Creative Commons Attribution Non-Commercial (CC-BY-NC) License permits use, distribution and reproduction in any medium, provided the original work is properly cited and is not used for commercial purposes.