6
$\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$
6
  • $\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
    Commented Sep 8, 2014 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$ Commented Sep 8, 2014 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
    Commented Sep 8, 2014 at 19:27
  • $\begingroup$ perhaps not @YvesDaoust, but periodic extension of the signal is what the DFT (or the DFS) does. $\endgroup$ Commented Sep 8, 2014 at 20:11
  • $\begingroup$ For googlers, further reading is "DFT periodicity". Only DFS has periodicity baked into the definition, while it sometimes makes sense to assume it of DFT (and that's poor wording). See e.g. 1, 2, 3 $\endgroup$ Commented Feb 8, 2023 at 16:23

5 Answers 5

9
$\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$
19
  • 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$ Commented Sep 8, 2014 at 20:13
  • 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$ Commented Jan 13, 2018 at 18:02
  • 2
    $\begingroup$ @CedronDawg well, there's a sorta circularity involved when using a wikipedia article that BobK wrote as a justification for BobK's position that you apparently like. i'm not particularly impressed with circular justification of reasoning regarding a simply clear mathematical notion. $\endgroup$ Commented Aug 27, 2020 at 2:42
  • 1
    $\begingroup$ @robertbristow-johnson I wasn't addressing the "authoritay" of the reference. Let's just get it straight (and you are oriented backwards mathematically).$$ $$1)The DTFT is a generalization of the DFT, not the DFT is a sampling of the DTFT. Other generalizations are possible. (Thus your "what does sampling.." question is meaningless)$$ $$2) The bin values of the 1/N DFT form the coefficients of the continuous Fourier Series.$$ $$3) The continuous FS, or the discrete FS, can be extrapolated (and will repeat), but that is not part of the definition of the DFT, or its inverse (not reciprocal). $\endgroup$ Commented Aug 27, 2020 at 11:53
  • 2
    $\begingroup$ //3) The continuous FS, or the discrete FS, can be extrapolated (and will repeat), but that is not part of the definition of the DFT, or its inverse (not reciprocal).// Operators (or "transforms" or "mappings" in the sense of metric spaces) have inverses if they are bijective (or "one-to-one"). But I was using the term "reciprocal" not as a property or attribute of an operator, but as applied to domains. It's not an "inverse domain". $$ $$ Now will either one of you even begin to answer any of the questions I asked? $\endgroup$ Commented Aug 28, 2020 at 9:16
8
$\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. The direct relationship between the periodic $\tilde{x}[n]$ and the "finite-length" $x[n]$ is

$$ \tilde{x}[n] = x[(\!(n)\!)_N] = x[n \bmod N] \qquad \forall n \in \mathbb{Z}, \ N \in \mathbb{Z}>0$$

where $ \qquad\qquad\qquad (\!(n)\!)_N \triangleq n \bmod N = n - N \left\lfloor \frac{n}{N} \right\rfloor $.

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$
3
  • $\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$ Commented Sep 9, 2014 at 17:30
  • 1
    $\begingroup$ I don't think this topic is fully clarified. I have in front of me the book of Oppenheim & Willsky, "Signals and Systems" (2nd Edition) and, on page 396, there's a table named "TABLE 5.3 SUMMARY OF FOURIER SERIES AND TRANSFORM EXPRESSIONS". On this table we can see four cases, and two of them are for discrete time signals, or sequences, if you prefer. On the same table, it is called Discrete Fourier Series (DFS) to a Fourier Analysis of a discrete time periodic signal, and a Discrete Fourier Transform (DFT) to a Fourier Analysis of a discrete time aperiodic signal (which, I guess, it's not cor $\endgroup$ Commented Feb 8, 2023 at 15:29
  • $\begingroup$ I have read your deleted answer. I have to disagree with @PeterK. about deleting the answer, since it doesn't fit into a comment. I do not have Oppenheim and Wilsky, so I cannot see what they did but normally I break the pedagogy into a 2-by-2 matrix of concepts as shown in Table 4.1 in this short document. $\endgroup$ Commented Feb 10, 2023 at 6:04
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$
5
  • $\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$ Commented Sep 8, 2014 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
    Commented Sep 8, 2014 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$ Commented Sep 9, 2014 at 14:25
  • $\begingroup$ A matrix multiply doesn’t inherently do anything except multiply. A DFT is just a matrix multiply. $\endgroup$
    – hotpaw2
    Commented Dec 25, 2017 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$ Commented Dec 25, 2017 at 22:24
2
$\begingroup$

The periodic summation $\ \tilde{x}[n] \triangleq \sum_{k=-\infty}^{\infty} x[n + kN]\ $ reduces to a periodic extension when the non-zero duration of $x$ is $\le N$.

And in that case, $\ \tilde{X}[k] \equiv X[k],\ \forall k$.

Otherwise, $X[k]$ is undefined, and $\ \tilde{X}[k]\ $ is a sample of the continuous and periodic DTFT (discrete-time Fourier transform) of the $x$ sequence.

Reference: https://en.wikipedia.org/wiki/Discrete-time_Fourier_transform#Sampling_the_DTFT

As I recall from Oppenheim & Shafer, the case of $x$ having longer duration than $N$ does not serve any of their purposes, so they do not even mention it.
Update: Upon refreshing my memory, they do mention it. pp 557-58 (2nd edition, 1999).

$\endgroup$
26
  • 1
    $\begingroup$ Okay, Bob, we got your comment. First of all, I would ask @PeterK or the other admins to please give BobK the initial 100 points that I got when I came here from out of the cold. $$ $$ Secondly, I would be happy to have a discussion (debate?) about this here. But I am not sure that the SE powers that be want a debate in the comments. BobK, can you comment on your own answer? try that. $\endgroup$ Commented Aug 26, 2020 at 0:11
  • 1
    $\begingroup$ //The DFT is a matrix multiplication// No, it's a specific mapping that is implemented with a specific matrix multiplication. //It does not care what is between the bins nor outside its domain.// i didn't say anything about what is between the bins so the first part of your assertion is not contested and the latter part of your statement is simply false, if you mean that the DFT does not care about what is $x[n]$ outside of the set $n: 0 \le n <N$. it most certainly cares. $\endgroup$ Commented Aug 27, 2020 at 2:51
  • 1
    $\begingroup$ //Wikipedia holds us to a higher standard than here, // where did you come up with that? Did you respond to any of the points I made? You can call it "Undefined", you can call it "$0$". Outside of the principal interval of $0 \le n \le N-1$ it doesn't matter what you call it, because if you do anything that requires shifting, you must use modulo arithmetic and that is explicitly periodic extension. Again, the relationship between $x[N-1]$ and $x[0]$ is exactly the same relationship as between $x[0]$ and $x[1]$. Always. $\endgroup$ Commented Aug 29, 2020 at 17:51
  • 1
    $\begingroup$ Yes Olli. That convolution result is the periodic summation in the top line of this Answer (Aug 25'20). The non-zero portions of the $x$ sequence Over-Lap and are Added. Then the $N$-length DFT is the line labeled "Eq (8.11)" in RBJ's previous Answer (Sep 9'14). The result is $N$ samples of one cycle of the DTFT of the original $x$ sequence. (see dsp.stackexchange.com/questions/16586/…) As I already mentioned (Aug 26'20, 11:33), an acronym for this procedure is WOLA (Weighted Over-Lap Add). $\endgroup$
    – Bob K
    Commented Sep 4, 2020 at 14:19
  • 1
    $\begingroup$ Part 2 (because of the character limit per comment): By design, the more overlap, the better the potential suppression of crosstalk in a WOLA channelizer. In a high dynamic range application, an $x$ sequence length in the range $6N$ - $8N$ would not be surprising. $\endgroup$
    – Bob K
    Commented Sep 5, 2020 at 10:55
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 and acknowledge you have read our privacy policy.

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