Efficient Modulo Multiplier
Rekib Uddin Ahmed, Sheba Diamond Thabah, Mridul Haque, and Prabir Saha
The paper presents the methodology to compute
modulo multiplication with the moduli set 2n, 2n−1, 2n+1. In
addition to this, designs of the modulo multipliers, namely 2n,
2n−1, and 2n+1 (with n = 4, 8, and 16), have been proposed
which are based on half adders, full adders, 4:3 compressor,
7:3 compressor, and the multi-column compressor namely 5,5:4.
The gate level design of 4:3 compressor is carried out by
solving the truth table using the K-map reduction. To verify
the functionalities we have implemented the proposed modulo
multipliers using VHDL coding in Xilinx 14.2 design suite.
Simulation using Virtex-6 device has been performed to estimate
delay, power consumption, and power-delay product (PDP).
Moreover, the modulo multipliers are simulated in Cadence RC
compiler using 0.18 µm technology to estimate the area. One
of the major contributions to the arts of this work is in the
partial product reduction stage which utilizes the multi-column
5,5:4 compressor to reduce power and area. The modulo 2n−1
multiplier of operand size 4-bit shows an improvement of 66.34%
in terms of area over the best-reported paper. On the other
hand, the modulo 2n+1 multiplier of operand size 4-bit shows an
improvement of 58.59% terms of in area and the same of operand
size 8-bit shows an improvement of 22.72% over the best-reported
paper. The proposed algorithms of moduli multiplication are
applicable to Booth multiplication of signed numbers.