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.

Verdoscia, L., Sahebi, A., Giorgi, R. (2019). A Data-Flow Methodology for Accelerating FFT. In A Data-Flow Methodology for Accelerating FFT (pp.471-474). New York : IEEE [10.1109/MECO.2019.8760044].

A Data-Flow Methodology for Accelerating FFT

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.
Scheda breve Scheda completa Scheda completa (DC)
2019
978-1-7281-1739-3
Verdoscia, L., Sahebi, A., Giorgi, R. (2019). A Data-Flow Methodology for Accelerating FFT. In A Data-Flow Methodology for Accelerating FFT (pp.471-474). New York : IEEE [10.1109/MECO.2019.8760044].
File in questo prodotto:
File
A_Data-Flow_Methodology_for_Accelerating_FFT.pdf

accesso solo dalla rete interna

Tipologia: PDF editoriale
Licenza: NON PUBBLICO - Accesso privato/ristretto
Dimensione 448.88 kB