Satu algoritma pendaraban baru yang bernama Digit Besar tetingkap (wBD) telah dicadangkan
kebelakangan ini. Algoritma ini berasaskan sistem penomboran Digit Besar (BD)
dan bersasarkan nombor besar yang beribu-ribu bit. Berat Hamming bagi sistem pernomboran
wBD hanya n 4:6 berbanding dengan n2 bagi sistem binari, n 3 bagi nombor tanpa bersebelahan (NAF) dan n w+1 bagi NAF tetingkap (wNAF). Berat Hamming yang rendah bermaksud bilangan
daraban separa yang rendah, yang mana akan mengurangkan bilangan langkah yang diperlukan
dalam sesuate operasi pendaraban. Oleh itu, sistem pernomboran wBD dapat mempercepatkan
proses pendaraban secara keseluruhan. Algoritma wBD telah dianalisis dan dibandingkan
dengan kaedah pendaraban yang lain di tahap algoritma. Namun, belum ada karya yang mengenai
pelaksanaan in peringkatan perkakasan diterbit. Untuk membolehkan penggunaan sistem
penomboran wBD secara meluas dalam sistem terbenam, sesuatu rekabentuk sistem pengecutan
pendarab wBD yang optimum telah diperkenalkan dalam kerja ini. Dalam kajian ini, satu
sistem pengecutan pendarab wBD telah direka dengan menggunakan Verilog dan diprototaipkan
dalam platform FPGA. Sistem pengecutan ini dilengkapi dengan port AXI dan disepadukan
ke dalam sistem SoC yang berasaskan pemproses ARM bagi tujuan perbandingan. Pendaraban
256-bit dengan menggunakan sistem pengecut ini didapati adalah 340 kali ganda lebih cepat
daripada pendaraban klasik yang dijalankan melalui teknik perisian. Ini menunjukkan bahawa
sistem pendaraban wBD boleh dilaksanakan dengan optimumnya dalam peringkat perkakasan
dan dapat mempercepatkan operasi pendaraban yang cuma berdasarkan perisian.
_______________________________________________________________________________________________________
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.
Hardware acceleration of window big-digit (wbd) multiplication for embedded applications / Lim Ee Wah