Fast binary multiplication by performing dot counting and complement recoding

Chia-Long Wu

doi:10.1016/j.amc.2007.02.136

Return

Fast binary multiplication by performing dot counting and complement recoding

2007-08-01

PRE

Chia-Long Wu *

Der‐Chyuan Lou

Te-Jen Chang

DOI：10.1016/j.amc.2007.02.136

Original

Original request for help

Save

Abstract

En 中文

In this paper, we present a new computation method by combining the dots counting method and the complement recoding method to efficiently evaluate modular multiplication in binary multiplications. The LUT (Look-Up Table) technique can be adopted in our proposed method to efficiently reduce the number of multiplications. And the proposed method can be easily implemented for the hardware. Numerous examples are provided to show the efficient and easy operations of the binary multiplication method. In average case, the worst case for the Hamming weight of the product X*Y is uv/4, where u is the bit-length of multiplicand X, v is the bit-length of multiplier Y. If the proposed method is applied, we could effectively reduce the Hamming weight of the product X*Y to 0.25u. (c) 2007 Elsevier Inc. All rights reserved.

Keywords:

look-up table

Hamming weight

binary multiplication

complement recoding method

dots counting method