The Fastest Multiplier on FPGAs with Redundant Binary Representation

摘要

In this paper, we propose the fastest binary multiplication algorithm on 4-LUT FPGAs. Our key idea is k-bit compaction, in which the n-bit multiplier is divided into n/k digits in 2~k -nary's, then the multiplicand is multiplied with each digit into a middle-product. And our second idea is one-minus-one encoding for the redundant binary representation. We've compared 2-bit, 3-bit and 4-bit compactions. And we have been able to construct 16-bit and 24-bit binary multipliers in 11 levels and 13 levels of 4-LUTs, respectively.