Iterative FFT-algorithms with high frequency resolution

Authors

DOI:

https://doi.org/10.26089/NumMet.v22r209

Keywords:

fast Fourier transform (FFT), computational graph, high resolution, frequency shift, time-frequency resolution, digital signal processing (DSP) problems, numerical iterative FFT algorithm, forward FFT, amplitude-frequency response, decimation in time

Abstract

This paper presents three iterative algorithms for fast Fourier transform with decimation in time; these algorithms have the algorithmic complexity O (N·R·log2N), where R is the frequency resolution of the spectral characteristic (the ratio of the length of the frequency set to the length of the N set of samples of the source signal). The algorithms differ in the way they organize calculations: some use reverse bit permutation, while the others use additional arrays. Detailed computational graphs and flowcharts of the developed algorithms are provided. The results obtained can be used to improve domestic electronics and software as well as may be included in the training process for engineers in the field of digital signal processing.

Author Biography

O.V. Osipov

References

  1. E. A. Al’tman, “Optimization of Computational Scheme of Fast Fourier Transformation,” Omsk. Nauch. Vestn., No. 1 (64), 149-151 (2008).
  2. L. M. Gol’denberg, B. D. Matyushkin, and M. N. Polyak, Digital Processing of Signals (Radio Svyaz, Moscow, 1990) [in Russian].
  3. L. R. Rabiner, B. Gold, and C. K. Yuen, Theory and Application of Digital Signal Processing (Prentice-Hall, Englewood Cliffs, 1975; Mir, Moscow, 1978).
  4. Fast Fourier Transform for O(Nlog N).
    https://e-maxx.ru/algo/fft_multiply . Cited May 15, 2021.
  5. O. V. Osipov, “Spectral Analysis of Discrete Signals with High Frequency Resolution,” Vychisl. Metody Programm. 20, 270-282 (2019).
  6. N. V. Ponomareva, “Fast Parametric Fourier Transform for Spectral Analysis of Signals with High Resolution in a Given Frequency Range,” DSPA: Voprosy primeneniya cifrovoj obrabotki signalov 9 (1), 28-32 (2019).
  7. V. N. Chan and V. N. Dam, “Implementation of the Spectrum Analyzer with High-Resolution on FGPA,” DSPA: Voprosy primeneniya cifrovoj obrabotki signalov 6 (4), 725-729 (2016).
  8. M. Gasior and J. L. Gonzalez, “Improving FFT Frequency Measurement Resolution by Parabolic and Gaussian Spectrum Interpolation,” AIP Conf. Proc. 732 (1), 276-285 (2004).
  9. I. A. Sidorenko and P. A. Kuskova, “On Improving the Accuracy of the Spectral Analysis of Phonemes when Using Sound Editors,” Belgorod State Univ. Sci. Bull. Ser.: Econ. Inform., No. 7, 188-193 (2015).
  10. D. D. Poleshenkov and O. O. Basov, “Pitch Frequency Separation Method Based on a Frequency Demodulation,” Belgorod State Univ. Sci. Bull. Ser.: Econ. Inform. 46 (2), 359-366 (2019).
  11. B. Gold and C. M. Rader, Digital Signal Processing (McGraw-Hill, New York, 1969; Sov. Radio, Moscow, 1973).
  12. V. I. Belov and E. I. Panimaskin, “The Fast Fourier Transform (FFT) with Decimation in Time,”
    https://docplayer.ru/25793573-Belov-v-i-panimaskin-e-i-bystroe-preobrazovanie-fure-bpf-s-prorezhivaniem-po-vremeni.html . Cited May 15, 2021.
  13. N. A. Galanina, “Synthesis of FFT Functional Modules in RNS,” Vestn. Chuvash. Gos. Univ., No. 2, 124-127 (2005).
  14. J. W. Cooley and J. W. Tukey, “An Algorithm for the Machine Calculation of Complex Fourier Series,” Math. Comput. 19 (90), 297-301 (1965).
  15. D. F. Vydrin, Yu. R. Abzalilova, and A. K. Vdovin, “Fast Fourier Transformation at Digital Signal Processing,” Teor. Prakt. Sovremen. Nauki, No. 2, 161-163 (2017).
  16. L. I. Timoshenko, “Discrete Transformation of Fourier and His Fast Algorithms,” Sovremen. Naukoemk. Tekhnol., No. 12-2, 188-193 (2014).
  17. A. I. Solonina, D. A. Ulakhovich, and L. A. Yakovlev, Algorithms and Processors for Digital Signal Processing (BHV-Petersburg, St. Petersburg, 2001) [in Russian].
  18. B. Lerner, Writing Efficient Floating-Point FFTs for ADSP-TS201 TigerSHARC® Processors.
    https://www.analog.com/media/en/technical-documentation/application-notes/EE-218.pdf . Cited May 15, 2021.
  19. V. E. Loginov and P. A. Ishin, “32-bit Floating-Point Fast Fourier Transform Optimization for Elbrus Processor,” Voprosy Radioelektron. 4 (3), 108-118 (2012).

Published

25-05-2021

How to Cite

Осипов О. В. Iterative FFT-Algorithms With High Frequency Resolution // Numerical Methods and Programming (Vychislitel’nye Metody i Programmirovanie). 2021. 22. 121-134. doi 10.26089/NumMet.v22r209

Issue

Section

Methods and algorithms of computational mathematics and their applications