EFFICIENT FLOATING POINT FAST FOURIER TRANSFORM BUTTERFLY ARCHITECTURE USING BINARY SIGNED DIGIT MULTIPLIER AND ADDERS

Shivani Acharya; Augusta Sophy Beulet

doi:10.22159/ajpcr.2017.v10s1.19568

Authors

Shivani Acharya Department of Computer Science & Engineering Specialization in Big Data Analytics, VIT University, Chennai, Tamil Nadu, India.
Augusta Sophy Beulet Department of Computer Science & Engineering Specialization in Big Data Analytics, VIT University, Chennai, Tamil Nadu, India.

DOI:

https://doi.org/10.22159/ajpcr.2017.v10s1.19568

Keywords:

Binary signed digit, Floating point, Fused dot product add, Fast Fourier transform, Redundant number system

Abstract

Fast Fourier transform (FFT) is one of the most important tools in digital signal processing as well as communication system because transforming time domain to S-plane is very convenient using FFT. As FFT uses various techniques to convert a signal from time domain to S-domain and inverse, out of which butterfly technique is the one on which paper is focused on. Butterfly technique uses additions and multiplications of operands to get the required output. Floating point (FP) is used as operands due to their flexibility. As the computations involving FP has less speed, we have used binaryÂ signed digit (BSD). BSD will take the less time for addition and subtraction. Three bit BSD adder and FP adder together will make a fused dot product add (FDPA) unit. In FDPA, unit addition and subtraction will be one group and multiplication will be one group and then their respective results will be fused. Modified booth encoding and decoding algorithm are used here to make the complex multiplication with ease.

Â

Downloads

Download data is not yet available.

References

Swartzerlander EE Jr, Saleh HH. FFT implementation with fused floating point operations. IEEE Trans Comput 2012;61(2):284-8.

Sohn J, Swatzerlander EE Jr. Improved architectures for a floating point fused dot product unit. In: Proceeding IEEE, 21st Symposium on Computer Arithmetic. April; 2013. p. 41-8.

IEEE Standard for Floating Point Arithmatic, IEEE Standard, 754, 2008, August; 2008. p. 1-58.

Cooley JW, Tukey JW. An algorithm for machine calculation of

AQ8 complex Fourier Series. Math Comput 1965;19(90):297301.

Baba SK, Rajaramesh D. Design and implementation of advanced modified booth encoding multiplier. Int J Eng Sci Invent 2013;2(8):60-8. Available from: http://www.ijesi.org.

Schneider K, Willenbucher A. A New Algorithm for Carry Free Addition of BinarySigned-Digit Numbers, IEEE 22nd International Symposium on Field-Programmable Custom Computing Machines; 2014.

Min JH, Kim SW, Swatzerlander EE Jr. A floating point fused FFT butterfly arithmetic unit with mergerd multipliers. In: Proceeding 45th Asilomar Conference on Signals, Systems, and Computers.

November; 2011. p. 520-4.

Tenca AF. Multi-operand floating point addition. In: Proceeding 19th Computer Arithmetic, June; 2009. p. 161-8.

Palnitkar S. Verilog HDL: A Guide to Digital Design and Synthesis, IEEE 1364-2001 Compliant. 2nd ed. Upper Saddle River, NJ: Pearson; 2003.

Prokis JG, Manolkis DG. Digital Signal Processing. 4th ed. Englewood Cliffs, NJ: Pearson Prentice Hall; 2007.

Kuang SR, Wang JP, Guo CY. Modified booth multipliers with a regular partial product array. IEEE Trans Circuits Syst II 2009;56(5):404-8.

Wang LR, Jou SJ, Lee CL. A Well-structured modified booth multiplier design. IEEE International Symposium on VLSI Design, Automation and Test. VLSI-DAT; 2008 Apr 23-25; Hsinchu. IEEE. p. 85-8.