A Mathematical Framework for Online Constant Coefficient Multiplication

Georgina Binoy Joseph; R Devanathan

Authors

Georgina Binoy Joseph Toc H Institute of Science & Technology
R Devanathan Hindustan Institute of Technology & Science, Hindustan University

Keywords:

Real time, online arithmetic, digital signal processing, single constant multiplication, multiple constant multiplication, Field Programmable Gate Array, floating point

Abstract

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

Author Biographies

Georgina Binoy Joseph, Toc H Institute of Science & Technology

Associate Professor

Department of Electronics & Communication

R Devanathan, Hindustan Institute of Technology & Science, Hindustan University

Professor Emeritus

Department of Electrical and Electronics Engineering

References

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.