DSPRelated.com
Forums

DFT or DFS: Are they the same thing?

Started by commengr August 7, 2009
Hello,

I have a question, it may be simple but its bugging me, so I need your
help. What is the difference between Discrete Fourier Series (DFS) and the
Discrete Fourier Transform (DFT) both theoretically and practically

Now, I know that we use DFS for the spectral analysis of Periodic
sequences and DFT for Aperiodic. (My concept is that in DFT, we have an
aperiodic sequence so we decide on the length of the sequence N to use for
spectral analysis, since we don't have a 'period', we repeat the sequence
as after those N samples, so its like an artificial periodic sequence)

However, if I give the same sequence of length N to a DFS algorithm, would
I not get the same results? The algorithm assumes, if I'm not mistaken,
that the sequence will be periodic.

Further, if I take a periodic sequence, feed it to a DFT algorithm like
FFT, I would get the correct results?

I can't seem to find a good book to clear this confusion (I have not made
an exhaustive search) but one that comes close is the book on DSP by Li Tan
On Aug 7, 12:06&#4294967295;am, "commengr" <communications_engin...@yahoo.com>
wrote:
> Hello, > > I have a question, it may be simple but its bugging me, so I need your > help. What is the difference between Discrete Fourier Series (DFS) and the > Discrete Fourier Transform (DFT) both theoretically and practically?
nothing.
> Now, I know that we use DFS for the spectral analysis of Periodic > sequences and DFT for Aperiodic.
that the DFT is for aperiodic input is an illusion. the DFT effectively periodically extends your input.
> (My concept is that in DFT, we have an > aperiodic sequence so we decide on the length of the sequence N to use for > spectral analysis, since we don't have a 'period', we repeat the sequence > as after those N samples, so its like an artificial periodic sequence) > > However, if I give the same sequence of length N to a DFS algorithm, would > I not get the same results?
are the mathematics the same?
> The algorithm assumes, if I'm not mistaken, > that the sequence will be periodic. > > Further, if I take a periodic sequence, feed it to a DFT algorithm like > FFT, I would get the correct results? > > I can't seem to find a good book to clear this confusion (I have not made > an exhaustive search) but one that comes close is the book on DSP by Li Tan
O&S (or now it's O,S,&B) about a decade ago, we had a slugfest here about this issue. at one time, Google Groups would search out old posts for me, but i can't get it to do that anymore. r b-j
On Thu, 06 Aug 2009 21:29:22 -0700, robert bristow-johnson wrote:

> On Aug 7, 12:06&nbsp;am, "commengr" <communications_engin...@yahoo.com> > wrote: >> Hello, >> >> I have a question, it may be simple but its bugging me, so I need your >> help. What is the difference between Discrete Fourier Series (DFS) and >> the Discrete Fourier Transform (DFT) both theoretically and >> practically? > > nothing. > > >> Now, I know that we use DFS for the spectral analysis of Periodic >> sequences and DFT for Aperiodic. > > that the DFT is for aperiodic input is an illusion. the DFT effectively > periodically extends your input. > >> (My concept is that in DFT, we have an aperiodic sequence so we decide >> on the length of the sequence N to use for spectral analysis, since we >> don't have a 'period', we repeat the sequence as after those N samples, >> so its like an artificial periodic sequence) >> >> However, if I give the same sequence of length N to a DFS algorithm, >> would I not get the same results? > > are the mathematics the same? > >> The algorithm assumes, if I'm not mistaken, that the sequence will be >> periodic. >> >> Further, if I take a periodic sequence, feed it to a DFT algorithm like >> FFT, I would get the correct results? >> >> I can't seem to find a good book to clear this confusion (I have not >> made an exhaustive search) but one that comes close is the book on DSP >> by Li Tan > > O&S (or now it's O,S,&B) > > about a decade ago, we had a slugfest here about this issue. at one > time, Google Groups would search out old posts for me, but i can't get > it to do that anymore. > > r b-j
I would call the non-difference a "useful approximation" rather than an "illusion". You can do a 'real' Fourier transform on discrete-time sampled data; you get a continuous function that repeats every 2 pi radians. But I haven't seen it used anywhere. -- http://www.wescottdesign.com
commengr <communications_engineer@yahoo.com> wrote:
 
< I have a question, it may be simple but its bugging me, so I need your
< help. What is the difference between Discrete Fourier Series (DFS) and the
< Discrete Fourier Transform (DFT) both theoretically and practically

I started a discussion not so long ago, that the FFT should instead
be called FFS, that is Fast Fourier Series.
 
< Now, I know that we use DFS for the spectral analysis of Periodic
< sequences and DFT for Aperiodic. (My concept is that in DFT, we have an
< aperiodic sequence so we decide on the length of the sequence N to use for
< spectral analysis, since we don't have a 'period', we repeat the sequence
< as after those N samples, so its like an artificial periodic sequence)

It is the same transform.  You can increase N as an approximation
to infinity.  For sufficiently large N you get close enough results.
If, for example, you want to see that the transform of a Gaussian
is a Gaussian, transform one with long enough tails and the result
will look close, though it will be periodic.  Also, zero comes at
the beginning as usual.
 
< However, if I give the same sequence of length N to a DFS algorithm, 
< would I not get the same results? The algorithm assumes, 
< if I'm not mistaken, that the sequence will be periodic.

Same transform, same result.

If you do a Fourier integral transfrom on a periodic function,
you get delta functions at the appropriate points.  

-- glen 
On Aug 7, 11:00&#4294967295;am, glen herrmannsfeldt <g...@ugcs.caltech.edu> wrote:
> commengr <communications_engin...@yahoo.com> wrote: > > < I have a question, it may be simple but its bugging me, so I need your > < help. What is the difference between Discrete Fourier Series (DFS) and the > < Discrete Fourier Transform (DFT) both theoretically and practically > > I started a discussion not so long ago, that the FFT should instead > be called FFS, that is Fast Fourier Series. > > < Now, I know that we use DFS for the spectral analysis of Periodic > < sequences and DFT for Aperiodic. (My concept is that in DFT, we have an > < aperiodic sequence so we decide on the length of the sequence N to use for > < spectral analysis, since we don't have a 'period', we repeat the sequence > < as after those N samples, so its like an artificial periodic sequence) > > It is the same transform. &#4294967295;You can increase N as an approximation > to infinity. &#4294967295;For sufficiently large N you get close enough results. > If, for example, you want to see that the transform of a Gaussian > is a Gaussian, transform one with long enough tails and the result > will look close, though it will be periodic. &#4294967295;Also, zero comes at > the beginning as usual. > > < However, if I give the same sequence of length N to a DFS algorithm, > < would I not get the same results? The algorithm assumes, > < if I'm not mistaken, that the sequence will be periodic. > > Same transform, same result. > > If you do a Fourier integral transfrom on a periodic function, > you get delta functions at the appropriate points. &#4294967295; > > -- glen
So why does text create such confusion? I believe it should be sorted out. Either call it Discrete Fourier Series or Discrete Fourier Transform.
> I started a discussion not so long ago, that the FFT should instead > be called FFS, that is Fast Fourier Series.
Yeah, it should be called Fast Fourier Series, since we manipulate the algorithm of DFS
On 7 Aug, 06:06, "commengr" <communications_engin...@yahoo.com> wrote:
> Hello, > > I have a question, it may be simple but its bugging me, so I need your > help. What is the difference between Discrete Fourier Series (DFS) and the > Discrete Fourier Transform (DFT) both theoretically and practically > > Now, I know that we use DFS for the spectral analysis of Periodic > sequences and DFT for Aperiodic.
You haven't defined the terms very detailed, but the DFS, as I understadn the term, is the trannsform of an infinitely long but periodic sequence. The DFT is a special case of the Discrete-Time Fourier Transform, which handles infinitely long sequences arbitrary sequences.
> (My concept is that in DFT, we have an > aperiodic sequence so we decide on the length of the sequence N to use for > spectral analysis, since we don't have a 'period', we repeat the sequence > as after those N samples, so its like an artificial periodic sequence)
Wrong. The DFT is the transform of a sequence with a finite number of elements.
> However, if I give the same sequence of length N to a DFS algorithm, would > I not get the same results? The algorithm assumes, if I'm not mistaken, > that the sequence will be periodic.
Most newbies don't understand that there are several variants of the Fourier transform around. The different variants take either discrete or continuous data as input, and the data are of either finite or infinite extent. The DFT takes a finite siquence of discrete data as input, and thus happens to be the variant that can be computed with what we understand as a 'computer' (there used to be analog computers in the past). There are no assumptions or constraints whatsoever imposed by the DFT on anything. The DFS is an ad hoc attempt for people to conceptually link the results of computations on finite discrete sequences to the desired results, that are computations on infinite length discrete sequences.
> Further, if I take a periodic sequence, feed it to a DFT algorithm like > FFT, I would get the correct results? > > I can't seem to find a good book to clear this confusion (I have not made > an exhaustive search) but one that comes close is the book on DSP by Li Tan
That's because the *good* books wouldn't mention the DFS at all. They would elaborate on what I just said, that the DFT is the form of the FT that can conveniently be computed, and that one needs to allow for the fact that one usually wants a different result than the one one gets. Rune
On 7 Aug, 08:56, Rune Allnor <all...@tele.ntnu.no> wrote:

> > Now, I know that we use DFS for the spectral analysis of Periodic > > sequences and DFT for Aperiodic. > > You haven't defined the terms very detailed, but the DFS, as I > understadn the term, is the trannsform of an infinitely long but > periodic sequence. The DFT is a special case of the Discrete-Time > Fourier Transform, which handles infinitely long sequences > arbitrary sequences.
Bad typo! The DF*S* is the special case of the DTFT. Rune
On Aug 7, 3:04&#4294967295;am, Rune Allnor <all...@tele.ntnu.no> wrote:
> On 7 Aug, 08:56, Rune Allnor <all...@tele.ntnu.no> wrote: > > > > Now, I know that we use DFS for the spectral analysis of Periodic > > > sequences and DFT for Aperiodic. > > > You haven't defined the terms very detailed, but the DFS, as I > > understadn the term, is the trannsform of an infinitely long but > > periodic sequence. The DFT is a special case of the Discrete-Time > > Fourier Transform, which handles infinitely long sequences > > arbitrary sequences. > > Bad typo! > > The DF*S* is the special case of the DTFT. >
Rune, we have heard the very same thing said about the DF*T*! the mathematics are the same. exactly the same. the DFT maps a discrete, infinite, and periodic sequence of period N in one domain (usually we call it the "time domain") to another discrete, infinite, and periodic sequence of the same period N in the reciprocal domain (usually we call it the "frequency domain") and the iDFT maps it back. but, since both infinite and periodic sequences are fully described by one period, all we pass to the DFT or iDFT are the N samples of one period. when someone claims that the N samples are *not* drawn from one contiguous period of a periodic sequence, when any of the shifting or convolution operations are done, modulo arithmetic *must* be used with the indices of the shifted sequence and that, essentially, implies periodically extending the N samples passed to the DFT. Rick Lyons (and some others) doesn't like this language of anthropomorohizing, but i'll say again: the DFT "assumes" that the N samples passed to it are N contiguous samples of a single period of a periodic sequence. you may not have intended them to be yanked from a periodic sequence, but when you pass the N samples to the DFT, that's what the DFT assumes. the DFT periodically extends the data set passed to it. remember: periodic in one domain implies discrete in the reciprocal domain. and vise versa. no matter how you look at it, this is always true. r b-j
On 7 Aug, 17:21, robert bristow-johnson <r...@audioimagination.com>
wrote:
> On Aug 7, 3:04&#4294967295;am, Rune Allnor <all...@tele.ntnu.no> wrote: > > > On 7 Aug, 08:56, Rune Allnor <all...@tele.ntnu.no> wrote: > > > > > Now, I know that we use DFS for the spectral analysis of Periodic > > > > sequences and DFT for Aperiodic. > > > > You haven't defined the terms very detailed, but the DFS, as I > > > understadn the term, is the trannsform of an infinitely long but > > > periodic sequence. The DFT is a special case of the Discrete-Time > > > Fourier Transform, which handles infinitely long sequences > > > arbitrary sequences. > > > Bad typo! > > > The DF*S* is the special case of the DTFT. > > Rune, we have heard the very same thing said about the DF*T*!
You might have. I don't want or need another war. Robert, I know you are a smart guy who is both passionate and knowledgeable about your trade. I think it's too sad that your teachers weren't up to your standards. Rune
On Aug 7, 11:48&#4294967295;am, Rune Allnor <all...@tele.ntnu.no> wrote:
> On 7 Aug, 17:21, robert bristow-johnson <r...@audioimagination.com> > wrote: > > > > > On Aug 7, 3:04&#4294967295;am, Rune Allnor <all...@tele.ntnu.no> wrote: > > > > On 7 Aug, 08:56, Rune Allnor <all...@tele.ntnu.no> wrote: > > > > > > Now, I know that we use DFS for the spectral analysis of Periodic > > > > > sequences and DFT for Aperiodic. > > > > > You haven't defined the terms very detailed, but the DFS, as I > > > > understadn the term, is the trannsform of an infinitely long but > > > > periodic sequence. The DFT is a special case of the Discrete-Time > > > > Fourier Transform, which handles infinitely long sequences > > > > arbitrary sequences. > > > > Bad typo! > > > > The DF*S* is the special case of the DTFT. > > > Rune, we have heard the very same thing said about the DF*T*! > > You might have. > > I don't want or need another war. Robert, I know you are a > smart guy who is both passionate and knowledgeable about > your trade.
i don't want a war either. i think those other wars were before your debut here, Rune.
> I think it's too sad that your teachers weren't up to your standards.
most of my undergrad and grad profs at U of North Dakota were fine. we didn't have the "Linear System Theory" or "Signals and Systems" course that are common now. we *did* have a "Linear Electric Circuits" course with a textbook from Van Valkenburg, but it was all continuous-time and the discrete-time stuff wasn't taught until my junior or senior year and it was so ad-hoc when it could have been tied together nicely and elegantly. (this "T factor" thingie in the sampling theorem was another screwup that, we have seen here, leads some students to ask "how do i build a LPF with passband gain of T?" it also leads some profs to mistakenly teach that the ZOH effect comes from sampling. and they get that off by a factor of T also.) but, other than that, i think i got a better undergraduate education than i would have if i were at many of these "prestigious" institutions. when i was a PhD student at Northwestern in the '80s, i was amazed at how poorly taught the undergraduates were. the profs, with their research and publication pressures, clearly did not prioritize teaching these fundamentals clearly. it was ad hoc over there, too. even more so. i think, with books and courses titled "Signals and Systems" that the trend is now to correct this and to both integrate the signals and systems concepts, while separating them from concepts of R, L, C, op- amps, and the like that should be left to a device and circuits course. these "Signals and Systems" fundamentals are so important because they support not only a linear circuits or electronics course, they support Communications Engineering, Control Systems, DSP, Stochastic Communications, even stuff in transmission lines and antennae theory (that linearity and time-invariance comes in handy when designing arrays). r b-j