MATLAB Central Newsreader - FFT and DFT in matlab

FFT and DFT in matlab

akshay — Tue, 28 Apr 2009 18:14:24 -0400

Hey,

I have written a simple DFT code for my randomly sampled signal,
but my results are different from those of matlab dft..

Any comments will be appreciated

Thanks

Re: FFT and DFT in matlab

Matt — Tue, 28 Apr 2009 18:25:17 -0400

akshay <gulatiakshay@gmail.com> wrote in message <32904364.31308.1240942509387.JavaMail.jakarta@nitrogen.mathforum.org>...
> Hey,
>
> I have written a simple DFT code for my randomly sampled signal,
> but my results are different from those of matlab dft..
>
> Any comments will be appreciated

Comments on what exactly? On your DFT code, which you haven't posted, or on the differences from MATLAB, which you haven't described.

Re: FFT and DFT in matlab

TideMan — Tue, 28 Apr 2009 20:45:16 -0400

On Apr 29, 6:14=A0am, akshay <gulatiaks...@gmail.com> wrote:
> Hey,
>
> I have written a simple DFT code for my randomly sampled signal,
> but my results are different from those of matlab dft..
>
> Any comments will be appreciated
>
> Thanks

Thousands and thousands of people around the world are using Matlab's
FFT routine every day, myself included. What makes you think that you
have somehow found a problem with it that no one else has discovered?

You asked for comments. Well, here is my carefully considered comment:
you have a bug in your DFT code.

Re: FFT and DFT in matlab

akshay — Mon, 01 Jun 2009 22:08:01 -0400

x=time
f_hat= amplitude in time domain
M=length(x);

freq=(-N/2):(N/2-1);

f=zeros(M,1);
      for k=1:N
        f=f+f_hat(k).*exp(-2*pi*i*x*freq(k));
      end;

isnt this is a simple version of DFT ....i am applying it non uniform samples .....can any one tell me how this code is different from matlab dft

ideMan <mulgor@gmail.com> wrote in message <24260d5b-01ed-4554-8e60-6b360f16849f@s1g2000prd.googlegroups.com>...
> On Apr 29, 6:14=A0am, akshay <gulatiaks...@gmail.com> wrote:
> > Hey,
> >
> > I have written a simple DFT code for my randomly sampled signal,
> > but my results are different from those of matlab dft..
> >
> > Any comments will be appreciated
> >
> > Thanks
>
> Thousands and thousands of people around the world are using Matlab's
> FFT routine every day, myself included. What makes you think that you
> have somehow found a problem with it that no one else has discovered?
>
> You asked for comments. Well, here is my carefully considered comment:
> you have a bug in your DFT code.

Re: FFT and DFT in matlab

Haroun Youssef — Wed, 05 Aug 2009 15:16:03 -0400

Hello

Matlab is using FFT not DFT, so it is considering that the samples are unifrom. If you input samples that are not uniform, the answer will probably different from the Matlab m file. Your code will give the right answer as it is not right to use FFT for non uniform samples. If you still need to use FFT, you have to consider to program another code for non uniform FFT

akshay <gulatiakshay@gmail.com> wrote in message <32904364.31308.1240942509387.JavaMail.jakarta@nitrogen.mathforum.org>...
> Hey,
>
> I have written a simple DFT code for my randomly sampled signal,
> but my results are different from those of matlab dft..
>
> Any comments will be appreciated
>
> Thanks

Re: FFT and DFT in matlab

Steven G. Johnson — Wed, 05 Aug 2009 22:39:54 -0400

On Aug 5, 11:16 am, "Haroun Youssef" <aga...@yahoo.com> wrote:
> Matlab is using FFT not DFT, so it is considering that the samples are unifrom.

An FFT is an algorithm for computing the DFT (the name of the abstract
mathematical transformation, not a specific method to compute this
transformation).

It would be more accurate to say that a transform with non-equispaced
data is not a DFT.

Regards,
Steven G. Johnson

Re: FFT and DFT in matlab

Greg — Tue, 11 Aug 2009 18:10:19 -0400

On Aug 5, 6:39 pm, "Steven G. Johnson" <stev...@alum.mit.edu> wrote:
> On Aug 5, 11:16 am, "Haroun Youssef" <aga...@yahoo.com> wrote:
>
> > Matlab is usingFFTnot DFT, so it is considering that the samples are unifrom.
>
> AnFFTis an algorithm for computing the DFT (the name of the abstract
> mathematical transformation, not a specific method to compute this
> transformation).
>
> It would be more accurate to say that a transform with non-equispaced
> data is not a DFT.

Given the amount of literature on NDFTs (NUDFTs, etc) this
appears to be a personal view point.

Speaking of viewpoints, I think there are basically 2:

1. Approximations for the analysis of continuous signals
and systems.
2. Analysis of discrete signals and systems.

Taking the former viewpoint, a DFT should be just what the
initials imply: A specific sum-based approximation to the
continuous CFT integral for functions sampled over a finite
interval T = t2-t1. There should be no constraint that
samples are uniformly spaced.

The primary constraint should be that the discrete time
transform converge to the continuous time transfornm as
N --> inf but sum(dti,i = 1:N) = T.

A secondary constraint should be that the DFT reduce to
the well known formula when t1 = 0, dti = dt = T/N =
constant and tN = (N-1)*dt = T-dt.

However, the best rectangular approximation to the integral
approximates the area from t1 to t2 with endpoint rectangles
of width dt/2. Whereas the traditional uniformly spaced DFT
best approximates the area from t1-dt/2 to tN+dt/2 with the
time sample centered at the middle of a rectangle.

So ... when applying a NDFT formula to uniformly spaced
points take the endpoint factors of 2 into account when
comparing with the traditional result.

Hope this helps.

Greg

Re: FFT and DFT in matlab

dbd — Wed, 12 Aug 2009 05:25:23 -0400

On Aug 11, 11:10 am, Greg <he...@alumni.brown.edu> wrote:
> On Aug 5, 6:39 pm, "Steven G. Johnson" <stev...@alum.mit.edu> wrote:
>> ...
> > It would be more accurate to say that a transform with non-equispaced
> > data is not a DFT.
>
> Given the amount of literature on NDFTs (NUDFTs, etc) this
> appears to be a personal view point.

The authors of such literature take pains to differentiate their works
for works labelled simply 'DFT' or 'FFT' by adding leading qualifiers
to their use. The nearly universal usage of 'DFT' alone to only apply
to uniformly spaced data when used as a transform between time and
frequency domain data samples makes it fair to assume that the use of
'DFT' alone for non-uniformly sampled data is either ignorant or mean-
spirited.

>
> Speaking of viewpoints, I think there are basically 2:
>
> 1. Approximations for the analysis of continuous signals
> and systems.
> 2. Analysis of discrete signals and systems.

There are far more than two viewpoints on the applications of the DFT.
Those whose experience is primarily limited to these two often can't
even tell these two apart and end up trying to make 2 resemble 1 even
when application drive no such requirement.

The great growth in the number of available applications,
implementations and instrumentation of the DFT to uniformly spaced
time and frequency samples took place in the 1970s and 1980s. A good
example of the interpretation of the DFT as it has been widely
understood and implemented then and ever since can be found in:

On the use of windows for harmonic analysis with the discrete Fourier
transform
Harris, F.J.
Proceedings of the IEEE
Publication Date: Jan. 1978
Vol: 66, Issue: 1,
On page(s): 51- 83

in particular for this topic, section II:
Harmonic Analysis of Finite Extent Data and the DFT

Available many places including:

http://web.mit.edu/xiphmont/Public/windows.pdf

> ...

>
> So ... when applying a NDFT formula to uniformly spaced
> points take the endpoint factors of 2 into account when
> comparing with the traditional result.

Can you provide references to this in the literature?

> ...
>
> Greg

Dale B. Dalrymple

Re: FFT and DFT in matlab

Greg — Thu, 13 Aug 2009 03:38:54 -0400

On Aug 12, 1:25 am, dbd <d...@ieee.org> wrote:
> On Aug 11, 11:10 am, Greg <he...@alumni.brown.edu> wrote:
>
> > On Aug 5, 6:39 pm, "Steven G. Johnson" <stev...@alum.mit.edu> wrote:
> >> ...
> > > It would be more accurate to say that a transform with non-equispaced
> > > data is not a DFT.
>
> > Given the amount of literature on NDFTs (NUDFTs, etc) this
> > appears to be a personal view point.
>
> The authors of such literature take pains to differentiate their works
> for works labelled simply 'DFT' or 'FFT' by adding leading qualifiers
> to their use. The nearly universal usage of 'DFT' alone to only apply
> to uniformly spaced data when used as a transform between time and
> frequency domain data samples makes it fair to assume that the use of
> 'DFT' alone for non-uniformly sampled data is either ignorant or mean-
> spirited.

Point taken.

> > Speaking of viewpoints, I think there are basically 2:
>
> > 1. Approximations for the analysis of continuous signals
> > and systems.
> > 2. Analysis of discrete signals and systems.
>
> There are far more than two viewpoints on the applications of the DFT.

Agreed. However, most arguments seem to stem from one of those two.

> Those whose experience is primarily limited to these two often can't
> even tell these two apart and end up trying to make 2 resemble 1 even
> when application drive no such requirement.

This thread is a case in point.

-----SNIP

> > So ... when applying a NDFT formula to uniformly spaced
> > points take the endpoint factors of 2 into account when
> > comparing with the traditional result.
>
> Can you provide references to this in the literature?

This comment was w.r.t. akshay's request

"I have written a simple DFT code for my randomly sampled
signal, but my results are different from those of matlab dft.

Any comments will be appreciated"

The viewpoint of my comment is from that of an approximation
to the CFT integral.

However, since I don't know exactly what he did, I can only
conjecture:

Let

fi = f(t(i))
dti = t(i+1)-t(i)
tmi = (t(i+1)+t(i))/2
fmi = f(tmi)

Then the three simplest sum of rectangles aproximations to the
integral are

I1 = SUM(i=1:N-1){ fi * dti },
I2 = SUM(i=1:N-1){ fi+1 * dti },
I3 = SUM(i=1:N-1){ fmi * dti }.

When applied directly to the DFT with dti = dt = constant, none
of the above reduce to the familiar N term result.

Two obvious modifications are

1. I4 = (I1+I2)/2
2. I5 = I3 with fmi = (fi+1+fi)/2

Both lead to the well known trapezoidal approximation

http://en.wikipedia.org/wiki/Numerical_integration

which downweights the endpoints by a factor of two.

Therefore, my comment to ashkay is

"Check to see if this is why your result doesn't match with
the fft result."

Hope this helps.

Greg

Re: FFT and DFT in matlab

dbd — Thu, 13 Aug 2009 18:47:32 -0400

On Aug 12, 8:38 pm, Greg <he...@alumni.brown.edu> wrote:
> ...
>
> http://en.wikipedia.org/wiki/Numerical_integration
>
> which downweights the endpoints by a factor of two.
>
> ...
> Greg

Thank you for providing the reference. I think that a comparison of
the references in this thread show that "numerical integration" and
"harmonic analysis" are significantly different viewpoints on:

> 2. Analysis of discrete signals and systems.

One of the obvious differences is that "harmonic analysis" deals with
an extent of N sample intervals on the basis of N samples while
"numerical integration" deals with an extent of N-1 sample intervals
on the basis of N samples. This is what seems to require the different
weighting of the end samples.

I have not found any published uniform or nonuniform DFT algorithm
that takes the "numerical integration" viewpoint. Have you? The wiki/
Numerical_Integration article makes no pretense of representing a DFT.
This makes your suggestion to the OP about failure to properly
numerically integrate seem an unlikely source of error between the
OP's implementation and any other DFT or non-uniform DFT algorithm
implementation.

Dale B. Dalrymple

Re: FFT and DFT in matlab

Steven G. Johnson — Fri, 14 Aug 2009 03:19:56 -0400

On Aug 12, 11:38 pm, Greg <he...@alumni.brown.edu> wrote:
> Both lead to the well known trapezoidal approximation
>
> http://en.wikipedia.org/wiki/Numerical_integration
>
> which downweights the endpoints by a factor of two.

No, this is not correct. If you are viewing the DFT as a sampled
approximation for Fourier series coefficients, the endpoints are 0 and
N, not 0 and N-1. If you weight each of these by 1/2 as per the
trapezoidal rule, due to aliasing you get back exactly the DFT
formula.

Regards,
Steven G. Johnson