Real-Time Fourier Transformation
As you know generally most of time is consumed for the calculation of convolution on Fourier transformation. If the method doesn't need the convolution, we'll expect the calculation for Fourier transformation with much shorter time. Here I offer a new Fourier transformation method which doesn't need any convolution. The algorithm is much simpler than any other Fourier transformation methods. First, as shown in the figure below, the time series data are interpolated with the sequence of triangles.



Extracting individual triangle as,



The Fourier transformation for that triangle is expressed as,

F(u) = v·exp(-iau){1/(d1u2)+1/(d2u2)-exp(id1u)/(d1u2)-exp(-id2u)/(d2u2)}

(I appreciate the suggestion from Dr P.Castiglioni for that formula)

Therefore the Fourier transformation for time series data is expressed as the sum of Fourier transformations for individual triangle owing to the linearity of Fourier transformation as,

F(u) = SjFj(u)
       = Sjvjexp(-iaju){1/(dj1u2)+1/(dj2u2)-exp(idj1u)/(dj1u2)-exp(-idj2u)/(dj2u2)}

As you notice, you are not requested to prepare the whole input data at the same time for Fourier transformation, but you can carry out it with transforming each triangle one by one, namely successively.

The following picture was taken from the Fourier analyzer: FerFT developed by HECO. The above method is used for real-time Fourier transformation of input voltage in this software.



As shown in the following example, the twe components of sine waves composing input signal (upper) are clearly distinguished as power spectre (lower). For details of FerFT, please visit: FerFT - Real Time Fourier Analyzer or FBT - New Style Fast Fourier Analyzer (about the hardware used for it, please visit: Minute Man Electronics - Pocket Sampler/Data Logger for PC Philmore DATAKit # 80-112)





For the application of this method to FM demodulation, please click here

For the application of this method to measure the frequency of bioelectric current, please click here

Thanks to Dr P. Castiglioni, this technology was introduced in his paper "Computationally Efficient Algorithm for On-Line Spectrum Analysis of Beat-to-Beat Signals (PDF file 418kb)".


Any Comment Welcome