EDFT (Extended Discrete Fourier Transform) produce Discrete N-point Fourier Transform (DFT) for shorter then N sequence X. Unlike Fast Fourier Transform (FFT), where unknown readings outside of X are zero-padded, the proposed EDFT algorithm for calculation of DFT using only available data. Application of EDFT function is simple and similar to FFT, besides EDFT have the following additional features:
1. EDFT can extrapolate input sequence X to length N. That is, if apply EDFT for N>length(X), get the results:
F=edft(X,N)=edft(Y)=fft(Y); Y=ifft(F),
where Y is X plus non-zero forward and backward extrapolation of X to length N or/and interpolation if unknown data inside of X have been replaced by NaN (Not-a-Number).
2. EDFT can increase frequency resolution up to 1/(N*T), where T is sampling period. It is well known, that zero-padding do not increase frequency resolution of DFT, therefore the resolution of FFT algorithm is limited by length of sequence length(X)*T. Of course, there is no magic- FFT just have equal resolution on all N frequencies, while EDFT have ability to increase the resolution on some frequencies and decrease on others. The sum of resolutions along the frequency axis for both algorithms remain equal to N*length(X)*T.
3. EDFT can estimate amplitudes and phases of sinusoidal components in sequence X. Like as FFT output fft(X,N)/length(X) is proportional to amplitudes of sinusoids in X, also adding a second output argument for EDFT return the amplitude spectrum S of sequence X:
[F,S]=edft(X,N).
4. Input sequence of EDFT may contain NaN. The proposed algorithm can interpolate and reconstruct of missing readings or even data segments (gaps) inside of sequence X. You just need to replace unknown readings by NaN and run edft(X) or edft(X,N).
5. EDFT can run with limit to maximum number of iterations (input argument I) or either in non-iterative (I=1) mode
[F,S]=edft(X,N,I) or
[F,S,Stopit]=edft(X,N,I,W),
where W is weight vector and consisting of specific weights for each frequency in F. W is propotional to the amplitude spectrum of the signal. So, a`priori knowledge about form of the input sequence amplitude spectrum S can be used to setup appropriate weight vector W, otherwise default (equal) weight W=ones(size(F)) will be applied. Stopit is an informative (optional) output parameter. The first row of Stopit showing the number of performed iteration, the second row indicate breaking of iteration reason (see EDFT help).
6. Is it possible to estimate DFT of nonuniformly (irregularly) sampled input sequence by proposed algorithm? Yes, it is. As result, the Nonuniform EDFT (NEDFT) program introduced for processing of input sequence X sampled at arbitrary time moments tk. NEDFT call line: [F,S]=nedft(X,tk,fn) will perform DFT of sequence X(tk) and return outputs F(fn) and S(fn). If frequencies fn are on different grid then used by FFT and EDFT algorithms, a simple Inverse NEDFT (INEDFT) program should be applied to reconstruct Y(tn), call line: Y=inedft(F,fn,tn).
7. Two-dimensional EDFT of array X can be calculated by applying function edft2.m, call line F=edft2(X, mrows, ncols).
See programs edft.m, edft2.m nedft.m and inedft.m help for detailed info.
Launch also DEMO programs demoedft.m and demonedft.m to check proposed algorithm performance for the simulated test signal.
Read attached ExtendedDFT.pdf to get more comprehensive insight into suggested algorithm.