Back to Search
Start Over
A Data-Flow Methodology for Accelerating FFT
- Source :
- MECO
- Publication Year :
- 2019
- Publisher :
- IEEE, 2019.
-
Abstract
- The native implementation of the N-point digital Fourier Transform involves calculating the scalar product of the sample buffer (treated as an N-dimensional vector) with N separate basis vectors. Since each scalar product involves N multiplications and N additions, the total time is proportional to $N^{2}$ , in other words, its an $O(N^{2})$ algorithm. However, it turns out that by cleverly re-arranging these operations, one can optimize the algorithm down to $O(Nlog_{2}(N))$ , which for large N makes a huge difference. The optimized version of the algorithm is called the Fast Fourier Transform, or the FFT. In this paper, we discuss about an efficient way to obtain Fast Fourier Transform algorithm (FFT). According to our study, we can eliminate some operations in calculating the FFT algorithm thanks to property of complex numbers and we can achieve the FFT in a better execution time due to a significant reduction of $N/8$ of the needed twiddle factors and to additional factorizations.
- Subjects :
- 0209 industrial biotechnology
Cooley–Tukey FFT algorithm
Scalar (mathematics)
Fast Fourier transform
02 engineering and technology
Execution time
Data flow diagram
symbols.namesake
020901 industrial engineering & automation
Fourier transform
0202 electrical engineering, electronic engineering, information engineering
symbols
020201 artificial intelligence & image processing
Complex number
Algorithm
Twiddle factor
Mathematics
Subjects
Details
- Language :
- English
- Database :
- OpenAIRE
- Journal :
- MECO
- Accession number :
- edsair.doi.dedup.....754dfd08aabb8e1377a97a334f479392