© The Institution of Engineering and Technology
An efficient design methodology and a systematic approach for the implementation of multiplication and squaring functions for unsigned large integers, using small-size embedded multipliers are presented. A general architecture of the multiplier and squarer is proposed and a set of equations is derived to aid in the realisation. The inputs of the multiplier and squarer are split into several segments leading to an efficient utilisation of the small-size embedded multipliers and a reduced number of required addition operations. Various benchmarks were tested for different segments ranging from 2 to 5 targeting Xilinx Spartan-3 FPGAs. The synthesis was performed with the aid of the Xilinx ISE 7.1 XST tool. The approach was compared with the traditional technique using the same tool. The results illustrate that the design approach is very efficient in terms of both timing and area savings. Combinational delay is reduced by an average of 7.71% for the multiplier and 21.73% for the squarer. In terms of 4-inputs look-up tables, area is lowered by an average of 11.63% for the multiplier and 52.22% for the squarer. In the case of the multiplier, both approaches use the same number of embedded multipliers. For the squarer, the proposed approach reduces the number of required embedded multipliers by an average of 32.77% compared with the traditional technique.
References
-
-
1)
-
B. Parhami
.
(2000)
Computer arithmetic algorithms and hardware designs.
-
2)
-
Gao, S., Chabini, N., Al-Khalili, D., Langlois, P.: `Efficient realization of large integer multipliers and squarers', Proc. 4th Int. IEEE-NEWCAS Conf, June 2006, Gatineau, Canada, p. 237–240.
-
3)
-
W. Stallings
.
(2002)
Cryptography and network security: principles and practice.
-
4)
-
M.-H. Sheu ,
S.-H. Lin
.
Fast compensative design approach of the approximate squaring function.
IEEE J. Solid State Circuits
,
1 ,
95 -
97
-
5)
-
A.A. Hiasat ,
H.S. Abdel-Aty-Zohdy
.
Combinational logic approach for implementing an improved approximate squaring function.
IEEE J. Solid state Circuits
,
2 ,
236 -
240
-
6)
-
D. De Caro ,
A.G.M. Strollo
.
Parallel squarer using Booth-folding technique.
IEE Electron. Lett.
,
6 ,
346 -
347
-
7)
-
J.M.P. Langlois ,
D. Al-Khalili
.
Carry-free approximation squaring function with O(n) complexity and O(1) delay.
IEEE Trans. Circuits Syst. II, Analog and Digit. Signal Process.
,
5 ,
374 -
378
-
8)
-
Xilinx Inc, http://www.xilinx.com/.
-
9)
-
Nedjah, N., de Macedo Mourelle, L.: `A reconfigurable recursive and efficient hardware for Karatsuba-Ofman's multiplication algorithm', Proc. IEEE Conf. on Control Applications, June 2003, Istanbul, Turkey, 2, p. 1076–1081.
-
10)
-
Phillips, B., Burgess, N.: `Optimized squaring with sliding windows', Conference Record of the 34th Asilomar Conf. on Signals, Systems and Computers, October 2000, 1, Pacific Grove, CA, USA, p. 130–133.
-
11)
-
Walters, E., Arnold, M.G., Schulte, M.J.: `Using truncated multipliers in DCT and IDCT hardware accelerators', Proc. SPIE Advanced Signal Processing Algorithms, Architectures, and Implementations XIII, August 2003, San Diego, California, p. 573–584.
-
12)
-
K.F. Smith ,
G. Gopalakrishnan
.
A fast parallel squarer based on divide-and-conquer.
IEEE J. Solid State Circuits
,
6 ,
909 -
12
-
13)
-
Gao, S., Chabini, N., Al-Khalili, D., Langlois, P.: `Optimized multipliers for large unsigned integers', Proc. 23rd IEEE NORCHIP Conf., November 2005, Oulu, Finland, p. 78–81.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-cdt_20060074
Related content
content/journals/10.1049/iet-cdt_20060074
pub_keyword,iet_inspecKeyword,pub_concept
6
6