Algorithms for Multiplierless Multiple Constant Multiplication in Online Arithmetic

作     者：Joseph, Georgina Binoy Devanathan, R. 

作者机构：Toc H Inst Sci & Technol Dept Elect & Commun Engn Kochi Kerala India Hindustan Inst Technol & Sci Sch Elect Engn Madras Tamil Nadu India 

出 版 物：《CIRCUITS SYSTEMS AND SIGNAL PROCESSING》 (电路、系统和信号处理)

年 卷 期：2018年第37卷第11期

页      面：5127-5142页

核心收录：

学科分类：0808[工学-电气工程] 0809[工学-电子科学与技术（可授工学、理学学位）] 08[工学] 

主　　题：Online arithmetic Digital signal processing Constant coefficient multiplication Graph-based algorithms Field-programmable gate arrays 

摘      要：Online arithmetic operators offer advantages of reduction in resource utilization and interconnection complexity besides providing pipelining at digit level. Multiplierless constant coefficient multiplication using the shift-and-add technique is widely used in digital signal processing applications. This paper proposes a novel bit serial adaptation of the parallel shift-and-add algorithm to online arithmetic. The proposed multipliers use right shifts instead of the traditional left shifts resulting in causal online implementations. Graph-based and hybrid algorithms are developed for the estimation of the distance of a constant from a set of constants in terms of the number of additions and for the synthesis of online multiple constant multipliers under area and online delay constraints. The computational complexity of the algorithms is determined. Results of implementation on randomly generated constant sets and FIR filter instances show substantial improvements in the number of operations required using the distance heuristic. Further, it is shown that the proposed techniques and algorithms result in significant savings in resource utilization, logic depth, and clock frequency compared to parallel and digit-serial algorithms.