Path: news.mathworks.com!newsfeed-00.mathworks.com!newsfeed2.dallas1.level3.net!news.level3.com!postnews.google.com!d21g2000vbm.googlegroups.com!not-for-mail
From: Greg <heath@alumni.brown.edu>
Newsgroups: comp.soft-sys.matlab
Subject: Re: FFT and DFT in matlab
Date: Wed, 12 Aug 2009 20:38:54 -0700 (PDT)
Organization: http://groups.google.com
Lines: 94
Message-ID: <f4361ce2-0623-4eab-babd-afeaa3475f2f@d21g2000vbm.googlegroups.com>
References: <32904364.31308.1240942509387.JavaMail.jakarta@nitrogen.mathforum.org> 
	<h5c7nj$6ba$1@fred.mathworks.com> <5d217906-c5db-4cc7-97bf-ef26c62e04a2@t13g2000yqt.googlegroups.com> 
	<863221bc-5347-4d03-b46b-1855f757921e@k30g2000yqf.googlegroups.com> 
	<45cdf7c7-251c-4f3b-b448-6cd2364c0859@d9g2000prh.googlegroups.com>
NNTP-Posting-Host: 69.141.163.135
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
X-Trace: posting.google.com 1250134734 12353 127.0.0.1 (13 Aug 2009 03:38:54 GMT)
X-Complaints-To: groups-abuse@google.com
NNTP-Posting-Date: Thu, 13 Aug 2009 03:38:54 +0000 (UTC)
Complaints-To: groups-abuse@google.com
Injection-Info: d21g2000vbm.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)
Xref: news.mathworks.com comp.soft-sys.matlab:562886


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