Revised fast Fourier transform

Abstract

EN: 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. UK: Проблема реалізації дискретного перетворення Фур’є в режимі он-лайн аналізується через неефективні витрати часу для нового перерахунку відліків спектру, якщо відлік одного сигналу з дискретним часом або навіть невелика частина відліків в періоді замінені на новий відлік або нові відліки, відповідно. Використання процедури швидкого перетворення Фур’є (ШПФ) припускає, що деякі відліки сигналу у відповідному періоді, доступні для цифрової обробки, оновлюються за допомогою датчика в режимі реального часу. Це актуально для кожного нового відліку, який призводить до отримання нового спектра. Звичайний перерахунок відліків спектру навіть з високоефективним алгоритмом ШПФ Кулі-Тьюки не підходить через швидко мінливого у часі спостережуваного реального процесу. Ідея полягає в тому, що процедура ШПФ не повинна перераховуватися з кожним новим відліком, потрібно просто модифікувати його, коли новий відлік з’являється і замінює старий. Отримано рекурентні формули для алгоритмів ШПФ, які відносяться до модифікації відліків спектру. У разі виникнення одного нового відліку, рекурсивний алгоритм обчислює нові відліки спектру простим додаванням до вектора старих відліків спектру різниці між старими і новими відліками, помноженої на відповідний ряд матриці «коду» Фур’є. Наведено приклад 8-точкового ШПФ.