Path: news.mathworks.com!newsfeed-00.mathworks.com!nlpi057.nbdc.sbc.com!prodigy.net!border1.nntp.dca.giganews.com!nntp.giganews.com!postnews.google.com!h11g2000yqb.googlegroups.com!not-for-mail
From: Greg <heath@alumni.brown.edu>
Newsgroups: comp.soft-sys.matlab
Subject: Re: FFT,IFFT, and NDFT,NFFT
Date: Mon, 6 Jul 2009 21:03:24 -0700 (PDT)
Organization: http://groups.google.com
Lines: 194
Message-ID: <7bdc64ef-1a65-45b9-8f2e-82fd3c4bbfa2@h11g2000yqb.googlegroups.com>
References: <h25v6u$5ia$1@fred.mathworks.com> <6ced5282-e4f9-4712-9546-158d71c222b0@j14g2000vbp.googlegroups.com> 
	<e104f561-edaa-4505-84c2-cf6bcfb49179@s31g2000yqs.googlegroups.com> 
	<h2tns4$a1h$1@fred.mathworks.com>
NNTP-Posting-Host: 69.141.163.135
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
X-Trace: posting.google.com 1246939405 13739 127.0.0.1 (7 Jul 2009 04:03:25 GMT)
X-Complaints-To: groups-abuse@google.com
NNTP-Posting-Date: Tue, 7 Jul 2009 04:03:25 +0000 (UTC)
Complaints-To: groups-abuse@google.com
Injection-Info: h11g2000yqb.googlegroups.com; posting-host=69.141.163.135; 
	posting-account=mUealwkAAACvQrLWvunjg50tRAnsNtJR
User-Agent: G2/1.0
X-HTTP-UserAgent: Mozilla/4.0 (compatible; MSIE 7.0; Windows NT 5.1; .NET CLR 
	2.0.50727; .NET CLR 3.0.4506.2152; .NET CLR 3.5.30729),gzip(gfe),gzip(gfe)
Bytes: 6860
Xref: news.mathworks.com comp.soft-sys.matlab:553280


On Jul 6, 4:47 pm, "guj " <gulatiaks...@gmail.com> wrote:
> Greg <he...@alumni.brown.edu> wrote in message <e104f561-edaa-4505-84c2-cf6bcfb49...@s31g2000yqs.googlegroups.com>...
> > On Jun 28, 12:33 pm, Greg <he...@alumni.brown.edu> wrote:
> > > On Jun 27, 4:25 pm, "guj " <gulatiaks...@gmail.com> wrote:
> > -----SNIP
> > > 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.
>
> > Correction:
>
> > If   mean(x) = x, i.e., x is constant, 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.
>
> > Correction:
>
> > If   mean(x) = x, i.e., x is constant, then the MSE is unnormalized.
>
> > > % For comparison with MATLAB'sFFTwhen the spacing is uniform,
> > > % double the end values x(1) and x(end) and divide X by dt0 =
> > > % mean(diff(t))
>
> > -----SNIP
>
> > Hope this helps.
>
> > Greg
>
> What are your comments on the code below:
> FFT is giving the same result as DFT for Non uniform sampling.

Both are inappropiarte for nonuniform sampling. See the above
code where nonconstant dt is taken into account.

> I am curious to know the difference between NDFT and DFT ...Notation
>
> clear
> dt=.01;
> N=101;
> func=sin([0:N-1]/4);

BETTER TO USE A COLUMN VECTOR

> f=1/dt/N/2*[-N:2:N-2];

INCORRECT FOR N ODD

> figure(1)
> clf
> subplot(3,1,1)
> plot(dt*[0:N-1],func)
> subplot(3,1,2)
> plot(f,fftshift(abs(fft(func))))

DIVIDE BY N TO GET CORRECT SCALE

> k=1:N;
> n=1:N;
> DFT=exp(-i*2*pi*((k(:)-1)*(n-1)/N));

POOR TERMINOLOGY CHANGE "DFT" TO "W"

> subplot(3,1,3)
> plot(f,fftshift(abs(DFT*func(:))))
>
> z=round(rand(1,N));
> temp1=func;
> temp2=z.*func;
> lives=find(z~=0);
> func=temp2(lives);

POOR TERMINOLOGY. 50% DIMENSION REDUCTION.
==> CHANGE NAME OF SAMPLED FUNC TO FUNCZ
HOWEVER, A 50% REDUCTION STILL LEAVES
~ 50 POINTS FOR 4 PERIODS OF FUNC.
MUCH MORE INSTUCTIVE TO HAVE LESS
THAN ~8 SAMPLES PER PERIOD. TRY A 2/3
REDUCTION

> DFT=DFT(:,lives);
>
> figure(2)
> clf
> subplot(3,1,1)
> plot(dt*[0:N-1],temp1,dt*[0:N-1],temp2)

NEED A PLOT OF FUNC AND FUNCZ

> subplot(3,1,2)
> plot(f,fftshift(abs(fft(temp2))))
> subplot(3,1,3)
> plot(f,fftshift(abs(DFT*func(:))))
>
> Here is NDFT, algorithm
>
> freq=(-N/2):(N/2-1);

WHY IS df = 1?
WHAT HAPPENS WHEN N is odd?

>f_hat=a;

WHAt IS a ???

>       f=zeros(M,1);
>       for k=1:N
>         f=f+f_hat(k).*exp(-2*pi*i*x*freq(k));
>       end;
> So question is Which one is right for Non uniform sampling

What are you comparing?
The previous examples go from time to frequency
Whereas your NDFT code goes from frequency to time.
????

If the DFT and IDFT are to be approximations to the
continuous time FT and IFT, the nonuniform differentials
dt and df have to be taken into account.

Go back to the code I posted (DFTgh1) to see how the nonuniform
factors dt and df affect the calculation.

In particular, the IDFT formula is not the inverse of
the DFT formula, or vice versa, when either spacing is nonuniform!

>..Is matlab DFT formula (which i have taken from help) is same
> as FFT and can handle only fixed sample...

The MATLAB formula, AS WELL AS YOUR NDFT, are only valid for
uniform sampling.

>what factor in DFT algorithm constraining it for fixed sampling.

The lack of nonconstant dt. See the formula in DFTgh1

> In DFT, algorithm we are multiplying our Coefficient with twiddle
< factor, that twiddle factor is equally spaced ...is that the
constrain...
>
> twiddle factor= exp(-2*pi*i*k*n/N)

Yes. That is a special case for dt and df constant.

The general form is W(k,n) = exp(-2*pi*i*f(k)*t(n))


>   ..IN this when we divide it by N, we only mean to normalise it..isnt
> it..also 2pi is my sampling frequency ...

???

> All these doubts are there because of the code which i have written above and i am dubious why its giving same result as fft ..Also what FFT do when it incur a irregular sampling....although it give wrong result but what is its working on such kind of input.

Go back to the continuous time Fourier integral for a
function that is zero outside of [0,T]. Then approximate
the integral with a sum over N nonuniformly spaced samples.
Notice that you cannot ignore the nonconstant differential
dt. If you do it right, you should come up with something
that looks like the formula in DFTgh1.

Hope this helps.

Greg