Path: news.mathworks.com!newsfeed-00.mathworks.com!newsfeed2.dallas1.level3.net!news.level3.com!postnews.google.com!j14g2000vbp.googlegroups.com!not-for-mail
From: Greg <heath@alumni.brown.edu>
Newsgroups: comp.soft-sys.matlab
Subject: Re: FFT,IFFT, and NDFT,NFFT
Date: Sun, 28 Jun 2009 09:33:33 -0700 (PDT)
Organization: http://groups.google.com
Lines: 111
Message-ID: <6ced5282-e4f9-4712-9546-158d71c222b0@j14g2000vbp.googlegroups.com>
References: <h25v6u$5ia$1@fred.mathworks.com>
NNTP-Posting-Host: 68.39.98.10
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
X-Trace: posting.google.com 1246206817 17714 127.0.0.1 (28 Jun 2009 16:33:37 GMT)
X-Complaints-To: groups-abuse@google.com
NNTP-Posting-Date: Sun, 28 Jun 2009 16:33:37 +0000 (UTC)
Complaints-To: groups-abuse@google.com
Injection-Info: j14g2000vbp.googlegroups.com; posting-host=68.39.98.10; 
	posting-account=mUealwkAAACvQrLWvunjg50tRAnsNtJR
User-Agent: G2/1.0
X-HTTP-UserAgent: Mozilla/4.0 (compatible; MSIE 7.0; Windows NT 5.1; Comcast 
	Install 1.0; GTB6; Mozilla/4.0 (compatible; MSIE 6.0; Windows NT 5.1; SV1) ; 
	.NET CLR 1.1.4322; .NET CLR 2.0.50727; .NET CLR 3.0.04506.30; Seekmo 
	10.0.341.0),gzip(gfe),gzip(gfe)
Xref: news.mathworks.com comp.soft-sys.matlab:551230


On Jun 27, 4:25 pm, "guj " <gulatiaks...@gmail.com> wrote:
> 1. When we have irregular sampling, we can use NDFT on it instead of FFT
> NDFT equation
> f_j = \sum_{k=-N/2}^{N/2-1} \hat f_k e^{(-2 *pi*i*k*x_j)}
>
> k= (-N/2:N/2-1)
> x_j=time domain (j=0,1,2____M-1)
>
> So what my question is, whenever we have non uniform sampling in the one domain will we get uniform sampling in another domain. For ex if my time domain >is irregular, will i be getting regular sampling in frequency domain

Using the DFT you can specify whatever spectral sampling you wish.
See below.

> 2. Inverting NDFT is not a easy task as in FFT, In ifft A inverse is equal to A conjugate, because of uniform sampling or fixed sampling in time domain that >why IFFT is easy to apply. Please correct me if am wrong.

Correct.

In the DFT function below, two forms of spectra
(Fourier and Least-Squares) are calculated for arbitrary
temporal sampling.

Then their inverses are calculated and compared with
the original function.

This DFT function was written more for understanding than
for practicality.

Much faster versions of the DFT can be found by searching
with the keyword "nfft"

From

http://groups.google.com/group/comp.soft-sys.matlab/
msg/a7a4479b8b402719

Newsgroups: comp.soft-sys.matlab, comp.dsp, sci.math.num-analysis
From: Greg Heath <he...@alumni.brown.edu>
Date: Tue, 13 May 2008 23:16:00 -0700 (PDT)
Subject: Re: Non-uniform Spacing

function   [XFT,XLS,NMSEFT,NMSELS] = DFTgh1(x,t,f)

% function [XFT,XLS,NMSEFT,NMSELS] = DFTgh1(x,t,f)
%
% Modification of AJ Johnson's dft for nonuniform sampling
%
% Computes XFT (Discrete Fourier Transform) at frequencies
% given in f, given samples x taken at times t:
%
% XFT(f) = sum(k=1,N){ dts(k) *x(k) * exp(-2*pi*j*t(k)*f) }
%        = W *(x.*dts)
%
% where dts is a symmetrized modification of diff(t).
%
% Also computes the Least-Squared-Error Spectrum at
% frequencies given in f, given samples x taken at
% times t:
%
% XLS(f) = (W'\x)./dfs;
%
% where dfs is a symmetrized modification of diff(f).
%
% NMSEFT is the normalized mean-square-error of reconstucting
% x from X using the Inverse Fourier Transform formula. If
% mean(x) = 0, then the MSE is unnormalized.
%
% NMSELS is the normalized mean-square-error of reconstucting
% x from X using Least Squares. If mean(x) = 0, then the MSE
% is unnormalized.
%
% For comparison with MATLAB's FFT when the spacing is uniform,
% double the end values x(1) and x(end) and divide X by dt0 =
% mean(diff(t))

x = x(:); % Format 'x' into a column vector
t = t(:); % Format 't' into a column vector
f = f(:); % Format 'f' into a column vector

N = length(x);
if length(t)~= N
   error('x and t do not have the same length')
end;

dt    = diff(t);                % asymmetric "dt"
dts   = 0.5*([dt; 0]+[0; dt]);  % symmetric "dt"
meanx = sum(x.*dts)/sum(dts);

df   = diff(f);                 % asymmetric "df"
dfs  = 0.5*([df; 0]+[0; df]);   % symmetric "df"

W    = exp(-2*pi*j * f*t');

XFT  = W * (x.*dts);
XLS  = (W'\x)./dfs;

xFT = real(W'*(XFT.*dfs));
xLS = real(W'*(XLS.*dfs));

MSE0  = mse(abs(x-meanx));
if MSE0 == 0, MSE0 = 1, end;

NMSEFT = mse(abs(x-xFT))/MSE0;
NMSELS = mse(abs(x-xLS))/MSE0;

return