3bit compaction と冗長2進を用いたFPGA向き乗算器 Multiplier on FPGAs with 3bit Compaction and Redundant Binary Representation

FPGA向きの冗長2進を内部表現に用いた2進乗算アルゴリズムを提案する。本稿では、乗数を3bitずつひとまとめにして中間積を求める3bit compactionという手法を提案する。また、one-minus-oneというエンコーディングによって冗長2進を表現している。特に、回路の規模よりも段数を小さくすることに注目した。その結果、24bit乗算器が4-LUTで14段で、16bit乗算器が4-LUTで12段で実現できた。

In this paper, we propose binary multiplication algorithm with redundant binary representation on LUT FPGAs. Our key idea is 3bit compaction, in which the 24bit multiplicator is divided into 8 octals then the multiplicand is multiplied with each octal into a middle-product. And our second idea is one-minus-one encoding for the redundant binary representation. Our goal is the minimization of the number of levels of 4-LUTs on FPGA, and as a result, we have been able to construct 24bit and 16bit binary multipliers with 4-LUTs in 14 levels and 12 levels, respectively.