Hardware acceleration of window big-digit (wbd) multiplication for embedded applications

Loading...
Thumbnail Image
Date
2015-08-01
Authors
Lim Ee Wah
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Window Big-Digit (wBD) is a recently proposed multiplication algorithm. This algorithm relies on Big-Digit (BD) numbering system and is targeting big integer with thousands bits. The hamming weight of wBD representation is only n 4:6 compared to n2 for binary, n 3 for Nonadjacent form (NAF) and to n w+1 for window-NAF (wNAF). Low hamming weight of multiplicand proportionately reduces the number of immediate partial products, which in turn will reduce the number of steps required in a multiplication function. Hence, wBD number system could be an excellent candidate to speed up overall multiplication process. The wBD algorithm has been analyzed and benchmarked against other multiplication methods in algorithmic level. However, there is no published works regarding hardware implementation of the algorithm yet. In order to enable boarder adoption of the wBD numbering system in resource constrained embedded systems, an optimized hardware accelerator design is introduced in this work. In this study, the hardware implementation of wBD multiplier is designed using Verilog and prototyped in FPGA platform. The accelerator is equipped with AXI interface and integrated into an ARM-based SoC system for benchmarking purpose. The test programs are The hardware-accelerated 256-bits multiplication is found that to be 340 fold faster than pure software implementation of classical multiplication. This shows that wBD algorithm can be optimally implemented in hardware and demonstrates excellent speed gain over pure software implementation.
Description
Keywords
Citation