MATHEMATICAL FOUNDATIONS OF FAST FOURIER TRANSFORM DESIGN AND ANALYSIS: A COMPUTATIONAL PERSPECTIVE AT THE PHYSICAL LEVEL
Abstract
This paper presents an attempt is made to combine the ideas of Vedic mathematics with the technology of very large-scale integration (VLSI) 90nm in order to create and evaluate a physical level device for the Fast Fourier Transform (FFT). The application of Vedic mathematics has the ability to increase the speed at which computations are performed by providing computational advantages over traditional methods in some domains. Through the utilization of Vedic Mathematics in the development of a Fast Fourier Transform (FFT) chip, it is possible to enhance the efficiency of computation, hence reducing the amount of time that is required. Considering the importance of FFT in a wide variety of digital signal processing applications, time optimization is considered to be of the utmost importance. Hardware Description Language (HDL) code is utilized in the implementation of the Vedic Mathematics method, and the design compiler tool developed by Synopsys, Inc. is utilized to assess the results of the implementation.
Keyword : VLSI, nanotechnology, mathematics, binary sequences, computational efficiency.
This work is licensed under a Creative Commons Attribution 4.0 International License.
References
[1] A. R. Prakash, S. Kirubaveni, “Performance evaluation of FFT processor using conventional and Vedic algorithm”, IEEE International Conference on Emerging Trends in Computing, Communication and Nanotechnology (ICECCN), Tirunelveli, March 2013, pp. 89-94. [2] A. Kumar, A. Raman, “Low Power ALU Design by Ancient Mathematics”, IEEE ICAAE, Singapore, Feb. 2010, pp. 862-865. [3] M. C. Hanumantharaju, H. Jayalaxmi, R. K. Renuka, M. Ravishankar, “A High Speed Block Convolution Using Ancient Indian Vedic Mathematics”, IEEE International Conference on Computational Intelligence and Multimedia Applications, Sivakasi, Tamil Nadu, December 13-15, 2007, pp. 169-173. [4] Bansal, Y.; Madhu, C.; Kaur, P. "High speed vedic multiplier designs-A review", Engineering and Computational Sciences (RAECS), 2014 Recent Advances, On page(s): 1 -6. [5] Kumar, Anvesh, et al. "Small area reconfigurable FFT design by Vedic Mathematics", Computer and Automation Engineering (ICCAE), 2010 The 2nd International Conference on. Vol. 5. IEEE, 2010. [6] K. Thanushkodi, K. Deena Dayalan, P. Dharani, “A Novel Time and Energy Efficient Cubing Circuit Using Vedic Mathematics for Finite Field Arithmetic,” IEEE International Conference on Advances in Recent Technologies in Communication and Computing, Kottayam, Kerala, 27-28 Oct. 2009, pp. 873 – 875. [7] H. D. Tiwari, G. Gankhuyag, M. Kim, B. Cho, “Multiplier design based on ancient Indian Vedic Mathematics”, IEEE Proc. International SoC Design Conference, ISOCC, Busan, 2008, pp. II-65 - II-68. [8] V. Kunchigi, L. Kulkarni, S. Kulkarni.: “High speed and area efficient Vedic multiplier,” Proc. IEEE International Conference on Devices, Circuits and Systems (ICDCS), Coimbatore, 2012, pp. 360 – 364. [9] J. W. Cooley and J. W. Tukey, "An Algorithm for the Machine Calculation of Complex Fourier Series," Mathematics of Computation, vol. 19, no. 90, pp. 297-301, 1965. [10] C. M. Rader, "Discrete Fourier Transforms when the Number of Data Samples Is Prime," Proceedings of the IEEE, vol. 56, no. 6, pp. 1107-1108, 1968. [11] S. Masuzawa and S. Kawamura, "Vedic multiplication architecture based on ancient Indian mathematics," IEEE Transactions on Computers, vol. 54, no. 7, pp. 839-849, 2005. [12]. António M. Grilo, Jaime Chen, Manuel Díaz, Daniel Garrido, and Augusto Casaca, “An Integrated WSAN and SCADA System for Monitoring a Critical Infrastructure”, IEEE Transactions on Industrial Informatics, Vol. 10, No. 3, pp. 1755-1764, August 2014. [13]. Debalina Ghosh, Depanwita Debnath, Dr. Amlan Chakrabarti ”FPGA Based Implementation of FFT Processor Using Different Architectures”, IJAITI VOLUME 1 NUMBER 1, PP 24-33, Jan/Feb 2012. [14]. Nisha John, Prof. Sadanandan G.K, “FPGA Implementation of a Novel Efficient Vedic FFT/IFFT Processor For OFDM”, International Journal of Advanced Research in Electrical, Electronics and Instrumentation Engineering, Vol. 3, Issue 3, September 2014. [15]. More T.V.,PanatA.R. “FPGA implementation of FFT using vedic algorithm”, Computational intelligene and Computing Research(ICCIC),pp-1-5 , 2013. [16]. Harpreet Singh Dhillon, AbhijitMitra, “A Digital Multiplier Architecture using UrdhvaTiryakbhyam Sutra of Vedic Mathematics”,IITG , pp-1-4 , 2010. [17]. AsmitaHaveliya, “FPGA implementation of a Vedic convolution algorithm”, International Journal of Engineering Research and Applications, Vol. 2, Issue 1, pp.678-684,Jan-Feb 2012. [18]. A.Ronisha Prakash, S. Kirubaveni, “Performance Evaluation of FFT Processor Using Conventional and Vedic Algorithm”, IEEE International Conference on Emerging Trends in Computing, Communication and Nanotechnology, pp-1-6, 2013. [19] Duhamel, P., & Vetterli, M. (1990). Fast Fourier transforms: a tutorial review and a state of the art. Signal processing, 19(4), 259-299. [20] Marks, R. J. (2009). Handbook of Fourier analysis & its applications. Oxford University Press. [21] Marks, R. J. (2009). Handbook of Fourier analysis & its applications. Oxford University Press. [22] Beylkin, G. (1995). On the fast Fourier transform of functions with singularities. Applied and Computational Harmonic Analysis, 2(4), 363-381.