14
$\begingroup$

In the literature, I've found that DFS and DFT are one and the same. If they are one and the same why to use two different names for them? If there is really a difference what is it and what is the significance of discrete Fourier series?

$\endgroup$
2
  • $\begingroup$ They're not the exact same thing. The only difference is a factor, specifically, in which equation (analysis equation/forward transform or synthesis equation/inverse transform) such factor is written. $\endgroup$
    – alejnavab
    Jun 21, 2021 at 5:30
  • 1
    $\begingroup$ It's about digital COMPUTERS... Its fundamental limitation which is manifested as finite-length, discrete-time, and quantized-magnitude representation of DATA, leads to a number of continuous and discrete transforms to be modified so that they can be PRACTICALLY processed on a digital-computer. The modified version of DFS is named DFT. The modification is an interpretation that one period of DFS is considered as DFT. So the modification leaved DFS effectively same as DFT. $\endgroup$
    – Fat32
    May 21, 2023 at 15:25

7 Answers 7

3
$\begingroup$

We have had this fight many, many, many times at comp.dsp.

The DFT is the same thing as the DFS.

The DFT maps a discrete and periodic sequence of numbers with period length of $N$ to another discrete and periodic sequence of numbers with period length of $N$ and the iDFT (which has the same form as the DFT) maps it back.

Some people don't like anthropomorphizing algorithms or procedures, but I do. The DFT "assumes" that the $N$ samples passed to it are one period of a periodic sequence. The DFT periodically extends the data passed to it.

It is clear in the math, both in the definition of the DFT (and iDFT), and in any theorem applicable to the DFT other than linearity (the periodic nature of the DFT is not evident in the linearity property, but it is evident in anything that causes shifting or convolution in one domain or multiplication by a non-constant in the other domain).

This is why, if periodicity is not assumed (a better word would be "recognized"), then people need to use this clunky modulo notation in the indices, like $x[ ((n))_N ]$ (this is the notation that O&S use) and that, in my opinion, is a pathetic confession from the periodicity deniers that, when it comes down to the bottom line, even they recognize that the DFT is inherently periodic.

To be explicit, the periodic extension of the $N$ samples of $x[n]$ passed to the DFT is:

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

where $ \qquad\qquad\qquad ((n))_N \triangleq n\operatorname{mod}_N = n - N\left\lfloor \frac{n}{N} \right\rfloor $

The notation $\lfloor \cdot \rfloor$ means the floor() function which is the largest integer that does not exceed the argument.

To use any of the shifting or convolution theorems of the DFT, this modulo arithmetic of the indices is absolutely required. for the scaling or superposition theorems, this modulo arithmetic is not required, but does not break those theorems in any case.

Therefore, to be consistent, when using the DFT for any theorems to do any real work with the DFT, one should simply apply the modulo arithmetic all of the time. Doing so explicitly periodically extends the $N$-sample sequence, $x[n]$ passed the DFT.

For me, it's just easier to drop the tilde "$\tilde{\ }$" and simply say that $\tilde{x}[n]$ is the same as $x[n]$ and that $\tilde{X}[k]$ is the same as $X[k]$ and just stop fucking around with this DFT business.

People should read this other answer I wrote a long time ago regarding the inherent periodic nature of the DFT.

$\endgroup$
1
7
$\begingroup$

I think part of the problem is an awkward and inconsistent naming convention. There are 4 flavors of Fourier Transforms depending on which domain is continuous or discrete (which maps to being aperiodic or perodic in the other domain). So we have

         Name                  Time                  Frequency
Fourier Transform    continous/aperiodic     continous/aperiodic 
Fourier Series       continous/periodic      discrete/aperiodic 
Discrete Time FT     discrete/aperiodic      continous/periodic
DFT or DFS           discrete/periodic       discrete/periodic

A better naming would have been

         Name                  Time                  Frequency
Fourier Transform    continous/aperiodic     continous/aperiodic 
Fourier Series       continous/periodic      discrete/aperiodic 
Discrete FT          discrete/aperiodic      continous/periodic
Discrete FS          discrete/periodic       discrete/periodic

so that discrete refers to "discrete in time and periodic in frequency" and "series" refers "discrete in frequency and periodic in time". In other words "series" means sums and "transform" means integrals. Discrete mean sums and continuous means integrals.

$\endgroup$
1
  • $\begingroup$ maybe to add a coda to Hilmar's answer: discrete in either the Time or Frequency domains is equivalent to uniform sampling of a continuous-time/frequency function. and uniform sampling of one continuous domain corresponds to periodicity in the other. so discrete-time must correspond to periodic frequency and discrete-frequency must correspond to periodic time. discrete time and frequency on one side of the transform must correspond to discrete frequency and time on the other side. $\endgroup$ May 8, 2014 at 18:48
2
$\begingroup$

Basically, DFS is used for periodic and infinite sequence. Whereas, DFT is used for non-periodic and finite sequence. Although, They are same Mathematically. But they differ in properties. Practically, we do not have infinite signal. We can say that DFT is extraction of one period from DFS. In other words, DFS is sampling of DFT equally spaced at integer multiple of $\frac{2 \pi}{N}$. DFT is fast and efficient algorithms exits for the computation of the DFT. DFS is adequate for most cases. But FT(Fourier Transform) leads to simpler expression.

$\endgroup$
4
  • $\begingroup$ //"But they differ in properties."// -------------- Abdul, would you care to identify the properties of the DFT and DFS that are operationally different? $\endgroup$ Nov 15, 2021 at 3:30
  • $\begingroup$ //"DFS is sampling of DFT equally spaced at integer multiple of $\frac{2\pi}{N}$ ."// No, both the DFS and DFT (being the same thing) are sampling the DTFT at $N$ equally-spaces points on the unit circle in the z plane. $\endgroup$ Nov 15, 2021 at 4:49
  • $\begingroup$ DFS can be used for finite continuous time sequences as well. As far as “implied periodicity” with either, I prefer to say that the DFT result can be shown to be mathematically equivalent to a waveform where the same N samples repeat (any amount of times). Mathematically meaning the non zero values will be identical with proper scaling as I demonstrate at this link. Periodic extension of the time and frequency axis can be helpful to intuitive understanding. dsp.stackexchange.com/a/83490/21048 $\endgroup$ Mar 16, 2023 at 16:23
  • $\begingroup$ Abdul, in "DFS is sampling of DFT", I suppose you are meant to say that "DFS is sampling of DTFT". The DFT is already discrete, it is not possible to sample something that is already discrete (you can downsample or upsample, though, but this is different from sampling). Moreover, the DFS is in fact the sampling of DTFT spaced in intervals of $\frac{2\pi}{N}$, as you said. $\endgroup$ May 17, 2023 at 19:09
1
$\begingroup$

DFS coefficient can be computed from DFT coefficients only when certain conditions are met.

1. DFS is a generic term for any discrete harmonic sum

From Wikipedia:

Discrete Fourier series (DFS) is any periodic discrete-time signal comprising harmonically-related discrete real sinusoids or discrete complex exponentials, combined by a weighted summation.

2. IDFT is a case of DFS

IDFT matches with the definition of a DFS. IDFT is a particular case of DFS.

  • DFS is the weighted sum of harmonics in the signal.

  • IDFT is the weighted sum of harmonics. The weights are the spectral coefficients of DFT. At certain conditions, DFS weights are DFT coefficients divided by the length of the DFT.

From Wikipedia:

When the coefficients are derived from an $N$-length DFT, and a factor of $1 / N$ is inserted, this becomes an inverse DFT.

This is the crucial point, for DFS and DFT coefficients to be exactly related by $1/N$, $N$ must be equal to the periodicity of the signal, and $1/N$ must correspond to the normalized fundamental frequency.

Practical case

To illustrate, consider a signal which fundamental frequency is 100Hz, and contains harmonics 2, 4, 5, 16, 17 with the following amplitude and phases:

f = [200, 400, 500, 1600, 1700]
a = [2, 4, 6, 8, 10]
p = [1, 0, 0.5, -0.5, 0]

So for this signal the DFS coefficients are 1, 2, 3, 4 and 5 and the same for the conjugates.

In order to have the DFT containing these harmonics, N must be at least 2x17=34 and the sampling frequency must be N*100Hz. These constraints are satisfied by selecting N=40 and fs=4kHz. The corresponding samples and the DFT:

enter image description here

Now let's take either the sampling frequency or the number of samples in a way fs=100*N is not satisfied:

enter image description here
enter image description here

DFS coefficients are not a scaled version of DFT coefficients.

Let's satisfy again the relationship with N=41 and fs=4100Hz:

enter image description here

The correct scaling is back.

$\endgroup$
2
  • $\begingroup$ This is really missing the point of the discussion. It's downvote-worthy with "IDFT is a particular case of DFS." but not into net-negatives. The answer would be improved if it explicitly states the equivalence to be computational-only, as that's all the answer demonstrates. $\endgroup$ Mar 19, 2023 at 13:50
  • 1
    $\begingroup$ DFT is also a case of DFS. And DFS is a case of DFT. If you take out the tilde, the equations are exactly the same. $\endgroup$ Mar 19, 2023 at 13:54
1
$\begingroup$

This answer documents an important exchange in the periodicity and DFT-DFS debate, for "meta reasons". Comments are from under the accepted answer, with my votes removed:

$\endgroup$
3
  • $\begingroup$ How did you get this O? Once it was moved to chat, it sorta lost all of the $\LaTeX$ formatting. Was it in the Wayback Machine? $\endgroup$ May 24, 2023 at 17:50
  • 1
    $\begingroup$ Snapped before Peter's imminent exterminatus $\endgroup$ May 24, 2023 at 17:54
  • 1
    $\begingroup$ I don't understand this policy. Those are great comments. Peter, I think it is better to leave technical comments even when it is gray. $\endgroup$
    – Royi
    Jun 18, 2023 at 7:48
0
$\begingroup$

So @OverLordDragon found a way to see one of the old comp.dsp discussions about this and reminded me of something.

So the Discrete Fourier Transform (DFT) is being defined as:

$$ 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} $$

$$ 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} $$

And the Discrete Fourier Series (DFS) is defined as:

$$\tilde{X}[k]= \sum\limits^{N-1}_{n=0} \tilde{x}[n] \ e^{-j2\pi n k/N} \qquad \forall k \in \mathbb{Z}$$

$$\tilde{x}[n] = \tfrac{1}{N} \sum\limits^{N-1}_{k=0} \tilde{X}[k] \ e^{+j2\pi n k/N} \qquad \forall n \in \mathbb{Z} $$


Now consider this relationship:

$$ Y[k] = e^{-j 2 \pi k/N} X[k] $$

What is $y[n]$ in terms of $x[n]$? Specifically what is $y[0]$?

Is it?

A: $\qquad \qquad y[n] = x[n-1] \qquad \qquad y[0] = x[-1] $

or

B: $\qquad \qquad y[n] = x[n-1] \qquad \qquad y[0] = 0 $

or

C: $\qquad \qquad y[n] = x[(n-1)\operatorname{mod}_N] \qquad \qquad y[0] = x[N-1] $

$\qquad \qquad$ where $ \qquad n\operatorname{mod}_N = n - N\left\lfloor \frac{n}{N} \right\rfloor $

or

D: $\qquad \qquad \text{none of the above}$

Which is it? A, B, C or D?


(If you answer B or D, you're just wrong.)

Now if you say if it's the DFS, it's A and if it's the DFT it's C, then what about the fact that C works for both the DFS and DFT?

So, would it kill the DFS if the time-shifting and convolution properties where changed to:

$$ Y[k] = e^{-j 2 \pi \frac{mk}{N}} \, X[k] \quad \Rightarrow \quad y[n] = x[(n-m)\operatorname{mod}_N] \qquad m \in \mathbb{Z} $$

$$ Y[k] = H[k]\, X[k] \quad \Rightarrow \quad y[n] = \sum\limits_{m=0}^{N-1} x[(n-m)\operatorname{mod}_N] \ h[m] $$ ?

Would that break the Discrete Fourier Series? If the answer is "no", then that means every theorem that the DFS and DFT have are identical to the other corresponding theorem. The DFS and DFT have these different initial definitions above but exactly the same theorems. So, tilde or not, they behave exactly the same.

So, is that "$0$" in the DFT definition ever getting used in the DFT or any theorems associated with the DFT? If that "$0$" changed to:

$$ 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{ten guzzillion ...} & \text{otherwise} \end{cases} $$

$$ 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{... something else}, & \text{otherwise} \end{cases} $$

Would it change anything w.r.t. the DFT? Where would that "otherwise" argument find use in any of the DFT mathematics?

Now, if you concede that changing 0 to ten gazzillion in the DFT and iDFT definitions make no difference with any DFT theorem, then what else is different, semantically, between the DFT and the DFS? What other semantic is different between the DFT and the DFS?

If the only semantic difference between the DFT and DFS makes absolutely no difference in any of the theorems that the DFT and DFS share (and they are all shared because we slipped that little modulo into the DFS theorems because it doesn't break them), then this is precisely a distinction without a difference. It makes no operational difference. It doesn't change any mathematics.

It makes no difference.

Then, since we normally express the DFT exactly like the DFS above (but without the tildes), and their theorems are exactly the same, and the only semantic difference makes no operational difference in any manner contained within the context of the DFT, then to claim there is any meaningful difference has no basis.

$\endgroup$
10
  • 1
    $\begingroup$ btw agreed on "moon man" etc -- good, move chat away from main answer before mods collapse Jazz sorcery -- also, the case you've been trying to prove all along is most likely a semantic, not substantive one, as by your own admission, $x$ outside of $[0, N - 1]$ can be moon man -- lastly, one'd think after 12 years you'd sit down and hammer out an indestructible proof of this die-hill issue $\endgroup$ May 22, 2023 at 2:41
  • 1
    $\begingroup$ I don't agree that there is any Jazz sorcery. Not sure why, but Jazz thinks that I am picking on him and I ain't. And, on this issue, there are several others that I am arguing with. It's not just Jazz. $\endgroup$ May 22, 2023 at 3:23
  • $\begingroup$ I mean Jazz's substance. I've seen most if not all DFT periodicity debates on DSP.SE, his stuff's unique. -- Yes, I can say with confidence that you don't intend to pick on him. Whether it happens anyway or is fair is separate. $\endgroup$ May 22, 2023 at 23:56
  • $\begingroup$ Also, while I generally agree with "any theorems", I'm unsure about "any" even in Fourier context; from my sine DFT answer. Since I don't fully understand "DFT samples DTFT" I can't say if it's a meaningful counterexample, but figured it may interest you. Let's keep the discussion here if it does interest you though, rather keep my Q&A on-topic. $\endgroup$ May 23, 2023 at 0:19
  • $\begingroup$ Here is a connection between DTFT and DFT.. $\endgroup$ May 23, 2023 at 0:26
0
$\begingroup$

Conceptually, DFS $\neq$ DFT.

DFS is, by definition, the Fourier transform of discrete-time, infinite-length, and periodic signals, which are denoted as $\tilde{x}[n]$. Therefore, DFS is given by $$ \tilde{X}[k] = \frac{1}{N} \sum_{n= 0}^{N-1} \tilde{x}[n] e^{-\frac{2\pi n k}{N}} $$

Although $\tilde{x}[n]$ is a infinite-length signal, we can store it in a computer by using only the samples within a period, and then computing the DFS. Likewise, since $\tilde{X}[k]$ is also periodic, we can store only the samples within its period as well. Although the DFS allow us to compute the Fourier transform of discrete signals, it is restricted to periodic and infinite-length signals.

The DFT, on the other hand, extends this computation beyond infinite-length and periodic signals: It computes the Fourier transform for a non-periodic and discrete-time sequence by assuming that this sequence is one period of a periodic signal. Consequently, all signal shifting is made on the basis of the so-called "circular shifting" (denoted by Oppenheim as $((n))_N$).

The fact that DFT constructs a circularly periodic signal from a finite-length and non-periodic sequence leads some people to claim that the DFT is also defined for periodic signals, and therefore would have no difference. But it is wrong.

Stick with the fundamentals

Sadly, there is a lot of misinformation on the internet. The best you can find is quotes of authoritative source that might enlighten this issue. From the fact that Oppenheim is an authoritative author in the field of DSP,. He clearly defines that $x[n]$ is 0 outside $\{0,1, \dots, N-1\}$:

In recasting Eqs. (8.11) and (8.12) [DFS equations] in the form of Eqs. (8.67) and (8.68) [DFT equations] for 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.68) is evaluated for values of $n$ outside the interval $0 ≤ n ≤ 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. In defining the DFT representation, we are simply recognizing that we are interested in values of $x[n]$ only in the interval $0 ≤ n ≤ N − 1$, because $x[n]$ is really zero outside that interval, and we are interested in values of $X [k]$ only in the interval $0 ≤ k ≤ N −1$ because these are the only values needed in Eq. (8.68) to reconstruct $x[n]$

Therefore, $x[n]$ is not $5$,$5000$, "man on the moon", or any other flat-earth-like crazy "theory" you came across in this community. Stick with the fundamentals.

FAQ

"Why should $x[n]$ be $0$ outside $\{0,1, \dots, N-1\}$?

That is an axiom which is given in the context of expanding the DFS to a broader class of signals which may not be periodic: the rationale for setting it to zero makes $x[n]$ finite-length and, therefore, nonperiodic.

For instance, in probability theory, It is not because $0\geq P[X] \geq 1$ is an axiom that we can state that $0\geq P[X] \geq \text{his hot girlfriend}$. That would be as aberrant as misleading. The same thing applies to DFS and DFT. So stop messing well-established theories up.

"This is a meaningless difference."

By assuming that there is no difference between DFT and DFS, you are presuming that Oppenheim, Proakis, Simon Haykin, and many other authoritative source have been doing tautology over the decades by sheer will. And yes, authoritative source is important, it is not a fallacy. Otherwise we create nonsense conjectures about the fundamentals. And the reason to have such a distinct difference is obvious: $x[n]$ in nonperiodic and finite-length, which enable us to use DFT for a much broader class of signals beyond the periodic and infinite-length ones.

"If you apply the DFS to $\tilde{x}[n]$, you would get the same result if would applied DFT to $x[n]$.

Of course you will. That is due to the inherent periodicity of the DFT, which extends a finite-length to a periodic in infinite-length signal.

What is true about the relationship of DFT and DFS?

  • The mathematical computation of DFT and DFS and absolutely identical. There is no different in the mathematical computation between the them. However, this does not make them equal.

  • The DFT inherently extends the periodicity of the finite length signal. By applying the DFT, we extends the periodicity of the finite-length signal.

  • The symbol $((n))_N$ is ugly and I really dislike it. So do I.

$\endgroup$
25
  • 1
    $\begingroup$ One thing, @PeterK. , the chat location does not support $\LaTeX$ or Mathjax or whatever it is we used to express equations. That makes it a sorta useless destination. I know having disputes publicly in the comments is something that SE views as dirty laundry, but I think this discussion/dispute should be visible and transparent. $\endgroup$ May 21, 2023 at 21:29
  • 1
    $\begingroup$ @robertbristow-johnson if it takes 20 comments to resolve its too long. The OP should be edited with the changes and any relevant comments deleted. $\endgroup$
    – Peter K.
    May 22, 2023 at 0:42
  • 1
    $\begingroup$ I wanted to upvote a dissenting answer, but if you argue against moon man, you're really missing the point. This line of reasoning is actually forced to agree with @robert on periodicity; if there's a forbidden value, then all values are forbidden except for ones that extend periodically. There's no meaningfully consistent case against this conclusion. Zeros are special in certain ways (operational equivalence of aggregate operators, e.g. integrals), but not to be confused with this debate. $\endgroup$ May 23, 2023 at 21:13
  • 1
    $\begingroup$ $$ X[k] = \begin{cases} \sum\limits^{N-1}_{n=0} x[n] \ e^{-j2\pi n k/N}, & 0 \le k \le N-1 \\ a, & \text{otherwise} \end{cases} $$ $$ 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 \\ a, & \text{otherwise} \end{cases} $$ Okay, we'll give it another symbol, $a$, which is a number that Rubem is insisting must be zero. Now, can someone show us a single DFT theorem that has a role for $a$? $\endgroup$ Jun 18, 2023 at 6:38
  • 1
    $\begingroup$ Rubem you are wrong. The authors you refer are clearly stating in their books that DFT is just one period of DFS. They are identical. Nobody can show a single operation that would differ between DFT and DFS . Hence effectively, they represent the same thing from outside. DFT is a name ALIAS for DFS (codingwise). Case closed for any practically speaking engineer. Or if you wish you can also indulge in a discussion of whether $\sin(x)$ and $\cos(\pi/2 - x)$ are the same identical things or not. Sure you'll find pathetics to aruge that one is sine and the other is cosine, etc.. :-)) $\endgroup$
    – Fat32
    Jun 18, 2023 at 15:35

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.