4
$\begingroup$

I am new to the field of signal processing. I am wondering what is the difference between DFS(Fourier Series) vs. DFT(Fourier Transform).

For common applications, usually we get a segment(length N) of digital waveform(like a audio segment), and then we apply FFT(DFT) and then do post-analysis with it.

I am wondering if we can use DFS(thus not using DFT at all) all the time and just assume the waveform segment is repeated with period N. Would this naive thinking/approach cause any problems?

$\endgroup$
  • $\begingroup$ Thanks for the quick reply. As you mentioned, there is a transform for discrete periodic signal. Why can't we assume the digital signal we received(in a buffer of length N) to be always periodic with period N ? (cause if you do this you will get perfect reconstruction as well) $\endgroup$ – aha Sep 8 '14 at 19:15
  • $\begingroup$ the point is @YvesDaoust, is that aha asked about the difference between the Discrete Fourier Series and the DFT. the answer is ... (below). $\endgroup$ – robert bristow-johnson Sep 8 '14 at 19:23
  • $\begingroup$ but the reconstruction will be perfect for the signal within the region of interest right (the sampled and stored N values) ? for example, if you load your entire MP3 music song into a big array(length is N) and just assume the music is repeated outside this array(with period N). Would there be any problems if you proceed frequency analysis like this? (thanks for your patience :) ) $\endgroup$ – aha Sep 8 '14 at 19:27
  • $\begingroup$ perhaps not @YvesDaoust, but periodic extension of the signal is what the DFT (or the DFS) does. $\endgroup$ – robert bristow-johnson Sep 8 '14 at 20:11
6
$\begingroup$

There is no operational difference between what is commonly called the Discrete Fourier Series (DFS) and the Discrete Fourier Transform (DFT). On the USENET newsgroup comp.dsp, we have had fights about this topic multiple times (if Google Groups wasn't so badly broken and messed up, I might be able to point you to the threads) and, despite the deniers, there is no, none whatsoever, operational difference between what is sometimes labeled as the DFS but most commonly labeled as the DFT. (The "FFT" is essentially an efficient or fast method of calculating the DFT.)

$\endgroup$
  • $\begingroup$ Thanks for the clarification !! I'll keep the question open for a few hours just to see if I get more opinions. $\endgroup$ – aha Sep 8 '14 at 19:32
  • 1
    $\begingroup$ @YvesDaoust, please get a copy of Oppenheim and Schafer (and Buck) and take a look at their chapter on the DFT. i have the 1989 version, so my page numbers might be different, but i can quote them and they put it in as stark language as me: the DFT and DFS are one-and-the-same. $\endgroup$ – robert bristow-johnson Sep 8 '14 at 20:13
  • $\begingroup$ @YvesDaoust: They're talking about the DISCRETE Fourier series, so there's no integral involved. $\endgroup$ – Matt L. Sep 9 '14 at 20:07
  • $\begingroup$ For very short sequences though, as with short Filter Banks, the difference can show IMO $\endgroup$ – Laurent Duval Jan 13 '18 at 14:50
  • 2
    $\begingroup$ i would be interested in seeing any operational difference between DFS and DFT that you can show, @LaurentDuval. i have to confess that i have my doubts. $\endgroup$ – robert bristow-johnson Jan 13 '18 at 18:02
7
$\begingroup$

okay, i'm gonna expound a little.

quoting (except for any typos that may result) from the 1989 text of O&S (Introduction to Chapter 8, The Discrete Fourier Transform, p 514):

Although several points of view can be taken toward the derivation and interpretation of the DFT representation of a finite-duration sequence, we have chosen to base our presentation on the relationship between periodic sequences and finite-length sequences. We will begin by considering the Fourier series representation of periodic sequences. While this representation is important in its own right, we are most often interested in the application of Fourier series results to the representation of finite-length sequences. We accomplish this by constructing a periodic sequence for which each period is identical to the finite-length sequence. As we will see, the Fourier series representation of the periodic sequence corresponds to the DFT of the finite-length sequence. Thus our approach is to define the Fourier series representation for periodic sequences and to study the properties of such representations. Then we repeat essentially the same derivations assuming that the sequence to be represented is a finite-length sequence. This approach to the DFT emphasizes the fundamental inherent periodicity of the DFT representation and ensures that this periodicity is not overlooked in applications of the DFT.

section 8.1, p 516 on the DFS:

Eq. (8.11) $\quad \tilde{X}[k] = \sum\limits^{N-1}_{n=0} \tilde{x}[n] \ e^{-j2\pi n k/N} $

Eq. (8.12) $\quad \tilde{x}[n] = \frac{1}{N} \sum\limits^{N-1}_{k=0} \tilde{X}[k] \ e^{+j2\pi n k/N} $

regarding the DFS, $\tilde{x}[n]$ (with the tilde) is defined to be periodic with period $N$ such that $$ \tilde{x}[n+N] = \tilde{x}[n] \quad \forall n $$ and $\tilde{X}[k]$ turns out to also be periodic with period $N$ (so $ \tilde{X}[k+N] = \tilde{X}[k] \quad \forall k $)

later, in section 8.6, p 532 on the DFT:

Eq. (8.59) $\quad X[k] = \begin{cases} \sum\limits^{N-1}_{n=0} x[n] \ e^{-j2\pi n k/N}, & 0 \le k \le N-1 \\ 0, & \text{otherwise} \end{cases} $

Eq. (8.60) $\quad x[n] = \begin{cases} \frac{1}{N} \sum\limits^{N-1}_{k=0} X[k] \ e^{+j2\pi n k/N}, & 0 \le n \le N-1 \\ 0, & \text{otherwise} \end{cases} $

Generally the DFT analysis and synthesis equations are written as

Eq. (8.61) $\quad X[k] = \sum\limits^{N-1}_{n=0} x[n] \ e^{-j2\pi n k/N} $

Eq. (8.62) $\quad x[n] = \frac{1}{N} \sum\limits^{N-1}_{k=0} X[k] \ e^{+j2\pi n k/N} $

In recasting Eqs. (8.11) and (8.12) in the form of Eqs. (8.61) and (8.62) for the finite-duration sequences, we have not eliminated the inherent periodicity. As with the DFS, the DFT $X[k]$ is equal to samples of the periodic Fourier transform $X(e^{j\omega})$, and if Eq. (8.62) is evaluated for values of $n$ outside the interval $0 \le n \le N-1$, the result will not be zero but rather a periodic extension of $x[n]$. The inherent periodicity is always present. Sometimes it causes us difficulty and sometimes we can exploit it, but to totally ignore it is to invite trouble.

so the first obvious thing i would say is that the tildes used for the DFS (to explicitly depict a periodic sequence) are symbols and still do not change any mathematical fact. now i know some folks will point to the Eqs. (8.59) and (8.60) definition of the DFT that has truncated (to $0$) values outside of the interval $0 \le n,k \le N-1$.

however, that definition is contrived. it could just as well be expressed as

$\quad X[k] = \begin{cases} \sum\limits^{N-1}_{n=0} x[n] \ e^{-j2\pi n k/N}, & 0 \le k \le N-1 \\ 5, & \text{otherwise} \end{cases} $

$\quad x[n] = \begin{cases} \frac{1}{N} \sum\limits^{N-1}_{k=0} X[k] \ e^{+j2\pi n k/N}, & 0 \le n \le N-1 \\ 5, & \text{otherwise} \end{cases} $

or

$\quad X[k] = \begin{cases} \sum\limits^{N-1}_{n=0} x[n] \ e^{-j2\pi n k/N}, & 0 \le k \le N-1 \\ 5000, & \text{otherwise} \end{cases} $

$\quad x[n] = \begin{cases} \frac{1}{N} \sum\limits^{N-1}_{k=0} X[k] \ e^{+j2\pi n k/N}, & 0 \le n \le N-1 \\ 5000, & \text{otherwise} \end{cases} $

or

$\quad X[k] = \begin{cases} \sum\limits^{N-1}_{n=0} x[n] \ e^{-j2\pi n k/N}, & 0 \le k \le N-1 \\ \text{the man on the moon}, & \text{otherwise} \end{cases} $

$\quad x[n] = \begin{cases} \frac{1}{N} \sum\limits^{N-1}_{k=0} X[k] \ e^{+j2\pi n k/N}, & 0 \le n \le N-1 \\ \text{and his hot girlfriend}, & \text{otherwise} \end{cases} $

because that $0$ in that contrived DFT definition will never ever be used in any theorems regarding the DFT. when that contrived definition is used for the DFT, then when using any DFT theorems to do any real work (other than the linearity and scaling by constant theorems), then one must use modulo arithmetic in the arguments of $x[n]$ or $X[k]$. and using that modulo arithmetic is explicitly periodically extending the sequence.

so (sorta responding to hotpaw) there are two or three processes that you should think about when using the DFT on a real signal.

  1. the sampling process. what happens to the spectrum of $x(t)$ when you sample it with a "dirac comb" or whatever you want to call the sampling function?

  2. windowing to finite length. what happens when you window either $x(t)$ or the sampled version, $x[n]$, with a rectangular window of length $N$?

  3. periodic extension. what happens when you periodically extend it by repeatedly shifting the windowed $x[n]$ by $N$ samples and overlap and add it?

deal with each step by itself.

$\endgroup$
  • $\begingroup$ one little factoid to add is this: Uniform sampling of a signal in one domain (say, the "time domain") corresponds to periodic extension of the Fourier Transform of that signal in the reciprocal domain (say, the "frequency domain"). and because of the symmetry of the Fourier Transform and its inverse, the converse is also just as true. $\endgroup$ – robert bristow-johnson Sep 9 '14 at 17:30
2
$\begingroup$

If the assumption matches the actual data (the FFT length comes from shaft synchronous sampling, etc.) then it may be useful. If the assumption is false, as it often is for a random audio frame, then false assumptions can produce false or misleading results. For example, windowing artifacts ("leakage") are often not actual spectral frequencies present in the longer audio stream. An extended reconstruction with these artifacts would contain stuff not present in the actual longer audio stream.

$\endgroup$
  • $\begingroup$ hot, as was the discussion years ago on comp.dsp, the windowing artifacts come from windowing and are not a consequence of the DFT. the DFT takes its finite set of adjacent samples and periodically extends that sequence. exactly as the DFS does. window is as windowing does, and the correct place to assign blame for windowing artifacts is the windowing operation itself. $\endgroup$ – robert bristow-johnson Sep 8 '14 at 20:10
  • $\begingroup$ The DFT transform matrix is of finite size, not infinite. And it is impossible to do any finite length DFT without windowing the real world. Therefore a windowing artifact is inherent in doing a DFT for almost all practical purposes (other than shaft synchronous sampled, etc.). For imaginary purposes, perhaps otherwise. $\endgroup$ – hotpaw2 Sep 8 '14 at 20:43
  • $\begingroup$ no, the DFT does not do the windowing. what the DFT does inherently do is periodically extend the data passed to it. the DFT maps a given $N$-periodic sequence in one domain (call it the "time domain" if you like) to another $N$-periodic sequence in the reciprocal domain. and the iDFT maps it back. that's what it does. $\endgroup$ – robert bristow-johnson Sep 9 '14 at 14:25
  • $\begingroup$ A matrix multiply doesn’t inherently do anything except multiply. A DFT is just a matrix multiply. $\endgroup$ – hotpaw2 Dec 25 '17 at 17:11
  • $\begingroup$ but the vectors that the matrix multiplies are circular. there is nothing special about $x[0]$ (except that it is the average of all of the $X[k]$). $x[N-1]$ comes before $x[0]$ as naturally as any $x[n]$ comes before $x[n+1]$. $\endgroup$ – robert bristow-johnson Dec 25 '17 at 22:24
0
$\begingroup$

I'll give you my gut feeling on the subject...

DFS (Discrete Fourier Series) vs. DFT (Discrete Fourier Transform)

Tilda vs. no Tilda.

DFS time sequence $\tilde{x}[n]$ includes only the first $N$ samples of sequence $x[n]$ by definition:

$$ \tilde{x}[n] = \sum_{k=-\infty}^{\infty} x[n + kN] $$

and they are repeated over and over ad infinitum...thus, the DFS doesn't have any statistical variations...its mathematically pure and unchanging... variance and standard deviation = 0 forever.

In comparison, the assumption of the DFT is that its taken over a statically "average" periodic period of the samples of $x[n]$… a crude application of the DFT is that since you don't know which of the $k$ periods is most statically average, then you just guess its whatever period you are observing.. and all other periods may have possible additive noise... now since $x[n]$ can have statistical variation in the periodic $x[n]$ signal, and variance is not zero, by central limit theorem as you approach infinity the noise cancels out over time if you average each of the terms of the periodic sequence over time... (a common statistical variation being additive gaussian white noise (AGWN) which averages itself out as n approaches infinity...assuming you are taking an average value for each coefficent over time...)

So in summary DFS and DFT may look mathematically the same, but statistically they are different animals. So if you like to nerd out on the use of tilda's there's an explanation... Along that line of thought, I would like to make a Platonic allegory of the distinguish between the "world of images" verse the "world of ideal forms". DFS is from the "world of ideal forms", in contrast DFT is a transform made for a "world of images" that are really just "projections of an underlying ideal form"...

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.