REVISED FAST FOURIER TRANSFORM

Authors

  • R. Pupeikis Vilnius University, Vilnius, Lithuania, Lithuania

DOI:

https://doi.org/10.15588/1607-3274-2015-1-9

Keywords:

digital signal processing, discrete Fourier transform, fast Fourier transform

Abstract

The problem of realisation of the Discrete Fourier Transform in on-line is analysed because of non-efficient consuming a time for a new
recalculation of spectrum samples if one discrete-time signal sample or even some small portion of samples in period are replaced by new
sample or by new samples, respectively. Using Fast Fourier Transform (FFT) procedure it is assumed that some signal samples in the respective period available for processing digitally are updated by a sensor in real time. It is urgent for every new sample that emerges to have a new spectrum. The ordinary recalculation of spectrum samples even with highly efficient Cooley-Tukey FFT algorithm is not suitable due to speedy varying in time real process to be observed. The idea is that FFT procedure should not be recalculated with every new sample, it is needed just to modify it when the new sample emerges and replaces the old one. We retrieve the recursive formulas for FFT algorithms that refer to the spectrum samples modification. In a case of appearing one new sample, the recursive algorithm calculates a new spectrum samples by simple addition of a residual between an old and new samples, multiplied on respective row of Fourier ‘code’ matrix, to a vector of old spectrum samples. An example of 8-point FFT is presented.

References

Deziel J. P. Applied introduction to digital signal processing / J. P. Deziel. – New Jersey : Prentice Hall, Inc., 2000. – 388 p. 2. Gonzalez R. C. Digitale Image Processing / R. C. Gonzalez. – New Jersey : Prentice Hall, Inc., 2007. – 976 p. 3. Oppenheim A. V. Discrete-time signal processing / A. V. Oppenheim, R. W. Shafer. – New Jersey : Prentice Hall, Inc., 2009. – 1120 p. 4. Proakis J. G. Digital signal processing. Principles, algorithms, and applications / J. G. Proakis, D. G. Manolakis. – New Jersey : Prentice Hall, Inc., 2006. – 1004 p. 5. Proakis J. G. Student manual for digital signal processing with Matlab / J. G. Proakis, V.K. Ingle. – New Jersey : Prentice Hall, Inc., 2006. – 264 p. 6. Lyons R. G. Understanding digital signal processing / R. G. Lyons. – New Jersey : Prentice Hall, Inc., 2010. – 984 p. 7. Richardson M. H. Fundamentals of the discrete Fourier transform / M. H. Richardson // Sound & Vibration Magazine. – 1978. – March. – P. 1–8. 8. Smith S. W. Digital signal processing. A practical guide for engineers and scientists / S.W. Smith. – San Diego : California Technical Publishing, 2003. – 640 p. 9. Pupeikis R. Vaizdu apdorojimo Matlab’o terpėje pagrindai / R. Pupeikis. – Vilnius : Technika, 2008. – 107 p. 10. Pupeikis R. Self-tuning minimum variance control of linear systems followed by saturation nonlinearities in a noisy frame / R. Pupeikis / / International Journal of Robust and Nonlinear Control. – 2014. – Vol. 24, № 2. – P. 313–325. DOI: 10.1002/rnc.2888 11. Казлаускас К. Цифровые системы обработки данных. Монография./ К. Казлаускас, Р. Пупейкис. – Вильнюс : Мокслас, 1991. – 220 с. 12. Cooley J. W. An algorithm for the machine calculation of complex Fourier series/ J. W. Cooley, J. Tuke // Mathematics Computation. – 1965. – Vol. 19 – P. 297–301. 13. Brigham E. Fast Fourier transform and its applications / E. Brigham. – New Jersey : Prentice Hall, Inc., 1988. – 446 p.

Downloads

Published

2014-12-25

How to Cite

Pupeikis, R. (2014). REVISED FAST FOURIER TRANSFORM. Radio Electronics, Computer Science, Control, (1). https://doi.org/10.15588/1607-3274-2015-1-9

Issue

No. 1 (2015): Radio Electronics, Computer Science, Control

Section

Progressive information technologies

License

Copyright (c) 2015 R. Pupeikis

Creative Commons License

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

Creative Commons Licensing Notifications in the Copyright Notices

The journal allows the authors to hold the copyright without restrictions and to retain publishing rights without restrictions.

The journal allows readers to read, download, copy, distribute, print, search, or link to the full texts of its articles.

The journal allows to reuse and remixing of its content, in accordance with a Creative Commons license СС BY -SA.

Authors who publish with this journal agree to the following terms:

  • Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License CC BY-SA that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.

  • Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.

  • Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.