DFT or DFS: Are they the same thing?

"commengr" <communications_engineer@yahoo.com> writes:

> 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

[...let me try again...]

You are correct on all counts.  According to [signalsandsystems,
pp.297,321], the only difference is in what is assumed, as you've
stated.

I disagree with Oppenheim et al. and all who assert the "DFT" is for
aperiodic sequences because the fact that the output is a discrete set
of samples means the input was necessarily periodic. So whether the
input came from a periodic or aperiodic set, the output is for the
equivalent periodic set.

Sure, you can interpolate those outputs to get a continuous set of
output frequencies, but then that isn't the DFT but rather the DFT +
something else.

To summarize, I would say there is absolutely no difference between the
DFS and the DFT. 

--Randy


@BOOK{signalsandsystems,
  title = "{Signals and Systems}",
  author = "{Alan~V.~Oppenheim, Alan~S.~Willsky, with Ian~T.~Young}",
  publisher = "Prentice Hall",
  year = "1983"}

-- 
Randy Yates                      % "And all that I can do
Digital Signal Labs              %  is say I'm sorry, 
mailto://yates@ieee.org          %  that's the way it goes..."
http://www.digitalsignallabs.com % Getting To The Point', *Balance of Power*, ELO

On 17 Aug, 10:25, "Phil O. Sopher" <inva...@invalid.invalid> wrote:
> "glen herrmannsfeldt" <g...@ugcs.caltech.edu> wrote in message
>
> news:h5i9nr$c7r$3@naig.caltech.edu...
>
> > robert bristow-johnson <r...@audioimagination.com> wrote:
> > < or are these several variants of the Fourier Transform merely
> > < degenerate or special cases of one unified Fourier Transform
> > < definition.
> > I think there is some advantage to the discrete transforms
> > over continuous integrals of delta functions. &#4294967295;It is easier
> > to think about, which is often reason enough.
> > Also, some people don't like delta functions.
>
> The proto-Bible (or proto-Koran, etc, &#4294967295;depending upon into which version
> of make-believe you were brain-washed when young) of DSP,
> Oppenheim & Schafer, 1975,
...
> It is unfortunate IMHO that a throw-away remark targetted at the
> mathematically
> juvenile should have been seized upon and promulgated by later authors when
> a simpler and more rigorous presentation has been available from the very
> early days via O&S.

I don't see what sampling/reconstruction has to do
with the relation between the DFT and the DTFT?

Oppeheim & Schafer didn't have the best starting point for
their treatment of the DFT. The paper

Cooley, Tukey & Lewis: "The Finite Fourier Transform"
  IEEE Trans. Audio & Electronics, Vol 17 No 2, 1969,

seems to be where the mess starts.

In the introduction the authors start out right.
They point out that one usually wants to discuss
functions on a continuous domain, but have to use
discrete sequences of finite length for numerical
computations:

"Given that we have to operate on such sequences,
say, X(j) for j = 0,1,...,N-1, it is natural to
develop a spectral theory for them, i.e., to define
a particular orthogonal transformation which takes
the sequence X(j) into another sequence, say A(n),
of the same length as X(j) and which describes
the frequency structure of X(j)."

The next paragraph shows how the authors totally
underestimate the topic, as well as their readers:

"There are few specific and extensive expositions
of the [DFT] in th eliterature and in particular
in books on Fourier analysis. This is probably
because the theory is relatively simple, and
because it can be subsumed under the theory of
Fourier analysis on locally compact Abelian groups."

So the authors consider the theory of the DFT to
be trivial, if the readers know Abelian groups.
They may be right, I don't know. I don't know
Abelian groups.

At last the damage is done:

"[I]t will be shown below that both computationally
and mathemathically the defining relationship of the
[DFT] automatically forces the assumption that the
sequence X(j) repeats itself periodically on all
integers outside the of the range j=0,1,...,N-1.
Any other assumption, say, that the X(j) has the
value zero for j outside the range 0,1,...,N-1,
produces a different theory, i.e., the theory
of Fourier series."

The blunder, of course, is that the authors don't
see or understand the difference between the statements
"X(j) is infinitely long and periodic with period N"
and "The DFT behaves as if the input sequence is
infinitely long and periodic with period N."

Again, I don't know what an "Abelian group" is.
Maybe this periodic *behaviour* of the DFT is a
consequence of it satisfying the axioms of an
Abelian group.

As for O&S' 1975 book, it is clear from the phrase
on page 87,

"There are several points of view that can be taken
toward the derivation and interpretation of the DFT
representation of a finite-duration sequence"

that Oppenheim & Schafer are fully aware of the blunder
made by Cooley & al being so unequivocal about the
interpretation of the DFT.

Rune

Rune Allnor <allnor@tele.ntnu.no> writes:
> [...]

> This is probably because the theory is relatively simple, and because
> it can be subsumed under the theory of Fourier analysis on locally
> compact Abelian groups."

> [...] Abelian groups [...]

Hey Rune,

Apparently the extra two words "locally compact," when placed next to
"Abelian groups," make the subject much more complicated! I know what
Abelian groups are and don't see what the DFT has to do with them. From
a quick Wikipedia reading it seems that the entire phrase "locally
compact Abelian groups" involves topology as well as abstract algebra,
and I believe that's a much deeper, complicated subject. 
-- 
Randy Yates                      % "The dreamer, the unwoken fool - 
Digital Signal Labs              %  in dreams, no pain will kiss the brow..."
mailto://yates@ieee.org          %  
http://www.digitalsignallabs.com % 'Eldorado Overture', *Eldorado*, ELO

On 17 Aug, 18:05, Randy Yates <ya...@ieee.org> wrote:
> Rune Allnor <all...@tele.ntnu.no> writes:
> > [...]
> > This is probably because the theory is relatively simple, and because
> > it can be subsumed under the theory of Fourier analysis on locally
> > compact Abelian groups."
> > [...] Abelian groups [...]
>
> Hey Rune,
>
> Apparently the extra two words "locally compact," when placed next to
> "Abelian groups," make the subject much more complicated! I know what
> Abelian groups are and don't see what the DFT has to do with them. From
> a quick Wikipedia reading it seems that the entire phrase "locally
> compact Abelian groups" involves topology as well as abstract algebra,
> and I believe that's a much deeper, complicated subject.

I have no idea, I'm not a mathematician. I heard about
groups in an intro class on coding theory ages ago, and
one of the properties we used was modulo N arithmetics.
I think I also heard about Fourier techniques to analyze
polynomials. But again, this was 15-20 years ago.

Still, Cooley & al did a fundamental blunder when they
failed to realize that

1) Infinitely long periodic sequences are a special
   case of infinitely long sequences and thus need
   no special treatement (the are covered by the DTFT)
2) The DFT maps a finite, discrete sequence of data
   onto a finite, discrete set of Fourier coeffcients
   whereas the DTFT maps an infinitely long discrete
   sequence onto a finite, continuous Fourier domain.

As is so often the case, people who have impressive
credentials (and maybe even experience) totally
underestimate and misjudge the details in the 'menial',
'trivial' tasks they reluctantly condescend to take on.

Rune

"Rune Allnor" <allnor@tele.ntnu.no> wrote in message 
news:b6072781-2e76-4115-b525-7d451a787444@w41g2000yqb.googlegroups.com...
On 17 Aug, 10:25, "Phil O. Sopher" <inva...@invalid.invalid> wrote:
> "glen herrmannsfeldt" <g...@ugcs.caltech.edu> wrote in message
> news:h5i9nr$c7r$3@naig.caltech.edu...
> > robert bristow-johnson <r...@audioimagination.com> wrote:
> > < or are these several variants of the Fourier Transform merely
> > < degenerate or special cases of one unified Fourier Transform
> > < definition.
> > I think there is some advantage to the discrete transforms
> > over continuous integrals of delta functions. It is easier
> > to think about, which is often reason enough.
> > Also, some people don't like delta functions.
> The proto-Bible (or proto-Koran, etc, depending upon into which version
> of make-believe you were brain-washed when young) of DSP,
> Oppenheim & Schafer, 1975,
...
> It is unfortunate IMHO that a throw-away remark targetted at the
> mathematically
> juvenile should have been seized upon and promulgated by later authors 
> when
> a simpler and more rigorous presentation has been available from the very
> early days via O&S.

> I don't see what sampling/reconstruction has to do
> with the relation between the DFT and the DTFT?

I responded to your comment, "some people don't like delta functions", and
so my response has the relevance that your comment had.

"Rune Allnor" <allnor@tele.ntnu.no> wrote in message 
news:b6072781-2e76-4115-b525-7d451a787444@w41g2000yqb.googlegroups.com...

> "There are few specific and extensive expositions
> of the [DFT] in th eliterature and in particular
> in books on Fourier analysis. This is probably
> because the theory is relatively simple, and
> because it can be subsumed under the theory of
> Fourier analysis on locally compact Abelian groups."

The earliest publication that I have that shows how to
(manually!) evaluate a DFT is "The Royal Signals Handbook
of LINE COMMUNICATIONS"; a 1952 reprint of
a 1947 original.

This is done from a graph of the waveform to be analysed,
and by measuring theordinates with a ruler!

How easy we have it with computers coming out of our ears!

And the foreword for the book starts, "A modern text book ....."   :-)

On 17 Aug, 19:20, "Phil O. Sopher" <inva...@invalid.invalid> wrote:
> "Rune Allnor" <all...@tele.ntnu.no> wrote in message
>
> news:b6072781-2e76-4115-b525-7d451a787444@w41g2000yqb.googlegroups.com...
> On 17 Aug, 10:25, "Phil O. Sopher" <inva...@invalid.invalid> wrote:
>
>
>
>
>
> > "glen herrmannsfeldt" <g...@ugcs.caltech.edu> wrote in message
> >news:h5i9nr$c7r$3@naig.caltech.edu...
> > > robert bristow-johnson <r...@audioimagination.com> wrote:
> > > < or are these several variants of the Fourier Transform merely
> > > < degenerate or special cases of one unified Fourier Transform
> > > < definition.
> > > I think there is some advantage to the discrete transforms
> > > over continuous integrals of delta functions. It is easier
> > > to think about, which is often reason enough.
> > > Also, some people don't like delta functions.
> > The proto-Bible (or proto-Koran, etc, depending upon into which version
> > of make-believe you were brain-washed when young) of DSP,
> > Oppenheim & Schafer, 1975,
> ...
> > It is unfortunate IMHO that a throw-away remark targetted at the
> > mathematically
> > juvenile should have been seized upon and promulgated by later authors
> > when
> > a simpler and more rigorous presentation has been available from the very
> > early days via O&S.
> > I don't see what sampling/reconstruction has to do
> > with the relation between the DFT and the DTFT?
>
> I responded to your comment, "some people don't like delta functions",

it wasn't me who made that comment.

Rune

On Aug 17, 8:45&#4294967295;am, Rune Allnor <all...@tele.ntnu.no> wrote:
>
> I don't see what sampling/reconstruction has to do
> with the relation between the DFT and the DTFT?

really, Rune?

you see no connection of the sampling and reconstruction theorem to
the action of picking out N uniformly spaced (in linear frequency)
values out of the continuous-frequency results of the DTFT?

that's virtually the only connection i see between the two.

r b-j

On Aug 17, 12:05&#4294967295;pm, Randy Yates <ya...@ieee.org> wrote:
> Rune Allnor <all...@tele.ntnu.no> writes:
> > [...]
> > This is probably because the theory is relatively simple, and because
> > it can be subsumed under the theory of Fourier analysis on locally
> > compact Abelian groups."
> > [...] Abelian groups [...]
>
>
> Apparently the extra two words "locally compact," when placed next to
> "Abelian groups," make the subject much more complicated! I know what
> Abelian groups are and don't see what the DFT has to do with them. From
> a quick Wikipedia reading it seems that the entire phrase "locally
> compact Abelian groups" involves topology as well as abstract algebra,
> and I believe that's a much deeper, complicated subject.

well, there is a bunch of formal language that i am unfamiliar with in
that Wikipedia article, but looking at the definition section (
http://en.wikipedia.org/wiki/Abelian_group#Definition ), it appears
that finite Abelian groups ( http://en.wikipedia.org/wiki/Abelian_group#Finite_abelian_groups
) are directly apropos to the DFT.  with an infinite and periodic
sequence (with finite integer period N), plug in either point-by-point
multiplication (or plug in circular convolution) in for the raised dot
operator in the definition and it satisfies all of the qualifications
of an Abelian group.  without the periodicity (or the modulo N
arithmetic done to the indices), it appears to me that it does *not*
satisfy the requirements of the definition.  so, all of these neat
theorems and facts regarding Abelian groups are available to us for
the periodically extended DFT but are not, if you (artificially) limit
yourself to non-periodically extended (or not extended at all).

infinite periodic sequences (or finite sequences where index
arithmetic is always modulo N) and either point-by-point
multiplication or circular convolution fit the definition like a
glove.  it appears to me that Oppenheim, Schafer, Cooley, Tukey,
Lewis, [Crosby, Stills, Nash, Young, Sacco, and Vanzetti] were spot on
the money.

just because the subject of Abelian groups is much deeper and
sophisticated than what most of us like to think about when
considering the DFT, does not mean that it is not applicable.  we
Neanderthal electrical engineers just may not have much use for it.
nonetheless, it doesn't mean that the DFT does not inherently
periodically extend either the data going in or the data coming out of
it.  i'm still waiting for the counter-example that shows that this
"assumption" of periodic extension (i consider it a recognition of
periodic extension) causes an error.  and i have shown two (actually
it's just one, shifting is a subset of the more general convolution)
examples where you get your ass burned by not periodically extending
the data in the DFT.

why is the DFT *not* the DFS?

r b-j

As r b-j has quoted to us in this thread, Oppenheim and Schafer state
that periodic extension is one of a number of interpretations of the
DFT, and one which they find convenient to use. Cooley, Tukey and
Lewis say periodic extension isn't necessary, but is a convenient
notation which they choose to use. As for "[Crosby, Stills, Nash,
Young, Sacco, and Vanzetti]" I'll paraphrase the r b-j style stance in
this thread and say:

"My membership in the IEEE does not give me free access to the works
of Crosby, Stills, Nash, Young, Sacco, and Vanzetti, so I'll pretend
that they don't exist until someone sends me copies of their relevant
works in violation of their copyrights." :)

I think Oppenheim, Schafer, Cooley, Tukey, Lewis, Crosby, Stills,
Nash, and Young are right on the money and it is a shame to see -some-
of them misrepresented here.

I don't think anyone argues that there aren't applications that can be
usefully explained with the assumption of periodic extension to make
the DFT correspond to a special case of a previously learned transform
of greater extent. That's not the same thing as saying the periodic
extension is inherent in or necessary to the DFT. The defining
equation of the DFT can be applied on it's own without recourse to
other transforms. The DFT definition contains no calculations that are
performed on periodic extensions. When I call the DFT with a small set
of contiguous samples from a larger, finite, discrete set of samples
from an anti-aliased, signal of time varying frequency content, the
defining equationn of the DFT can be interpreted as a set of linear
convolutions with a set of coefficients that are also a part of the
DFT definition. There is no frequency content requiring periodic
extension to explain and no calculation with periodic extended
samples. To find periodic extension it must be assumed (and has been
by some). Argument by assumption is circular reasoning not periodic
extension.

Now I didn't make this post expecting to change the minds of any of
the participants. I just wanted to get the phrase "circular reasoning"
into the thread, just in case the thread ever gets archived somewhere,
so that I can tell people to search on "periodic extension" and
"circular reasoning" for a great example.

Dale B. Dalrymple