Hard multiple generator for higher radix modulo 2^n-1 multiplication

Abstract

High-speed modulo multipliers are essential elements in RNS datapath. Booth recoding algorithm can be used to improve the performance of the multiplier by reducing the number of partial products. In radix-8 booth encoding, the number of partial products is reduced to one-third. However, the inevitable carry propagation adder required to generate the hard multiple, 3X, where X is the multiplicand, falls on the critical path of the multiplier. This paper presents an efficient modulo 2n-1 hard multiple generator based on the parallel-prefix addition. The proposed hard multiple generator employs prefix levels, making radix-8 Booth encoding a feasible choice for high-speed modulo 2n-1 multiplier design. The merit of the design is corroborated by synthesis results based on TSMC 0.18 CMOS standard-cell library.