Extended DFT

版本 1.49.4.0 (17.9 KB) 作者: Vilnis Liepins
Program EDFT produce high-resolution N-point DFT for N greater than the length of data vector X.
4.8
(9)
10.7K 次下载
更新时间 2024/5/12

查看许可证

EDFT (Extended Discrete Fourier Transform) algorithm produces N-point DFT of sequence X where N is greater than the length of input data. Unlike the Fast Fourier Transform (FFT), where unknown readings outside of X are zero-padded, the EDFT algorithm for calculation of the DFT using only available data and the extended frequency set (therefore, named 'Extended DFT'). EDFT function application is simple and similar to the FFT, besides EDFT have the following additional features:
1. EDFT can extrapolate input sequence X to length N. That is, if applied EDFT to N>length(X), get the results:
F=edft(X,N)=edft(Y)=fft(Y), where Y=ifft(F) and the length(Y)=N.
Y is X plus non-zero forward and backward extrapolation of X to length N and/or 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 the length of sequence length(X)*T. Of course, there is no magic, just FFT resolution is equal on all N frequencies, while EDFT is able to increase the resolution on some frequencies and decrease on others. The sum of reciprocals of resolutions along the frequency axis for both algorithms remain equal to N*length(X)*T. Thus, an increase in resolution is dictated by well-known laws of physics, from where, the longer data, the higher the resolution has been achieved.
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) or [F,S,f]=edft(X,N), where also frequency set used by EDFT is returned in f.
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. Is it possible to estimate DFT of nonuniformly (irregularly) sampled input sequence by the proposed algorithm? Yes, it is.
[F,S]=edft(X,N,tk) computes the EDFT of X using the sample points tk.
If N is a vector then EDFT is computed at the query points fn defined in N and N set to be equal length(fn).
If N is a scalar then the query points default to fn=ifftshift(-ceil((N-1)/2):floor((N-1)/2))/N.
If tk is not specified ([]) then tk=(0:length(X)-1).
If the data is nonuniform and/or frequencies fn are not in FFT grid, then Matlab function NUFFT, call line: Y=nufft(F,f,-tk)/N; or slower inverse EDFT function, call line: Y=iedft(F,f,tk); can be used as the inverse Fourier transform. Otherwise, Matlab function IFFT can be applied to get uniformly re-sampled version of input sequence X.
6. EDFT can run with a limit to the maximum number of iterations (input argument I) or either in non-iterative (I=1) mode
[F,S,f]=edft(X,N,tk,I) or [F,S,f,Stopit]=edft(X,N,tk,I,W),
where W is the weight vector and consisting of specific weights for each frequency in F. W is proportional to the amplitude spectrum of the signal. So, a`priori knowledge about the form of the input sequence amplitude spectrum S can be used to setup appropriate weight vector W, otherwise the default (equal) weight W=ones(size(F)) will be applied for the first iteration.
'Stopit' is an informative (optional) output parameter. The first row of 'Stopit' showing the number of the performed iterations, the second row indicates breaking of iteration reason and the third row output the algorithm used to compute EDFT.
7. Two-dimensional EDFT of array X can be calculated by applying function edft2.m, call line: F=edft2(x,mrows,ncols). The inverse transform to two-dimensional EDFT is Matlab ifft2 function, call line: Y=ifft2(F).
See programs edft.m, iedft.m and edft2.m help for detailed info.
Launch also DEMO program. Demoedft.m allows to verify the proposed algorithm performance over iterations for the simulated test signal and make a comparison with the Matlab function NUFFT.
Download pdf file on site http://arxiv.org/abs/1303.2033 to get more comprehensive insight into suggested algorithm.

引用格式

Vilnis Liepins (2024). Extended DFT (https://www.mathworks.com/matlabcentral/fileexchange/11020-extended-dft), MATLAB Central File Exchange. 检索来源 .

MATLAB 版本兼容性
创建方式 R11.1
兼容任何版本
平台兼容性
Windows macOS Linux

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

版本 已发布 发行说明
1.49.4.0

Updated and returned the iedft.m function as an alternative way to calculate the inverse Fourier transform of nonuniform data.
1.49.3.0

Add reference to nufft in the edft.m description.
1.49.2.0

Remove function iedft.m as it is covered by adjoint Matlab function nufft.
1.49.1.0

Repeat update of edft2
1.49.0.0

Update edft2.m
1.48.9.0

Refactoring of edft.m input parameters
1.48.8.0

Change image only
1.48.7.0

edft.m updated to return the frequency set f used in calculations.
1.48.6.0

Image update 2x
1.48.5.0

Domo programs and image updated
1.48.4.0

Minor changes
1.48.3.0

Removed unused output argument in edft.m
1.48.2.0

Demo programs updated
1.48.1.0

edft.m updated to use nested functions

1.48

Improve handling of ill-conditioned matrices in edft.m
1.47.9.0

Stop iteration condition updated in edft.m
1.47.8.0

Function iedft.m updated
1.47.7.0

edft.m updated
1.47.6.0

Minor changes
1.47.5.0

Demo program updated
1.47.4.0

Minor update to edft.m
1.47.3.0

Special case processing updated.
1.47.2.0

Updated help texts and added additional input parameter validations.
1.47.1.0

description updated
1.47.0.0

Program edft.m merged with nedft.m, all functionality is preserved.
1.46.5.0

The demo programs have been updated to compare with the Matlab function NUFFT.
1.46.4.0

cleanup code
1.46.3.0

minor changes after code review
1.46.2.0

Help text updates
1.46.1.0

Mirror corrections
1.46.0.0

Program nedft.m updated
1.45.0.0

Code update for nedft.m and edft.m functions.
1.44.0.0

The default matrix inversion method changed in edft.m
1.43.0.0

Documetation related update
1.42.0.0

A small corrections made in demoedft output.
1.41.0.0

)
1.40.0.0

Mirror changes
1.39.0.0

Demo files updated
1.38.0.0

Bug in edft.m line 135 corrected. Thanks David M.-S. for your quick response.
1.37.0.0

Minor changes - just a code refactoring.

1.10.0.0

EDFT package updated. Pdf file removed as a latest version of it will be available on arxiv site.

1.9.0.0

Added the link to external document

1.7.0.0

Obsolete finite function romoved from code (thanks Sean for your comment). Documentation updated.
1.6.0.0

mirror changes
1.5.0.0

Update contacts info and pdf file.
1.4.0.0

Programs edft_f2.m and edft_f3.m added
1.3.0.0

Small changes in stopping iterations criteria
1.2.0.0

minor changes
1.1.0.0

Update ExtendedDFT.pdf file
1.0.0.0

Documentation update