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

Iterative FFT-algorithms with high frequency resolution

Authors

  • O.V. Osipov

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.

Downloads

Published

2021-05-25

Issue

Vol. 22 (2021): Issue 2.

Section

Methods and algorithms of computational mathematics and their applications

Author Biography

O.V. Osipov

V.G. Shukhov Belgorod State Technological University,
• Associate Professor

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).

License

Copyright (c) 2021 О. В. Осипов

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.