Efficient STFT

Small perturbations in signals (or any time series), at some particular instant, affect the whole frequency spectrum due to the global function e/sup j omega t/ in Fourier Transform formulation. However, the Fourier spectrum does not convey the time instant at which the perturbation occurred. Consequently the information on the particular time instance of occurrence of that perturbation is lost when spectrum is observed. Apparently Fourier analysis seems to be inadequate in such situations. This inadequacy is overcome by the use of Short Time Fourier Transform (STFT), which keeps track of time as well as frequency information. In STFT analysis, a fixed length window, say of length N, is moved sample by sample as the data arrives. The Discrete Fourier Transform (DFT) of this fixed window of length N is calculated using Fast Fourier Transform (FFT) algorithm. If the total number of points is M > N, the computational complexity of this scheme works out to be at least ((M-N) N log/sub 2/N). On the other hand, STFT is shown to be of computational complexity 6NM and 8NM in the literature. In this paper, two algorithms are presented which compute the same STFT more efficiently. The computational complexity of the proposed algorithms works out to be MN of one algorithm and even lesser in the other algorithm. This reduction in complexity becomes significant for large data sets. This algorithm also remains valid if a stationary part of signal is skipped. (author)