2
$\begingroup$

I am trying to understand the connection between FT, DTFT and ultimately the DFT. But I am failing to link the DTFT to the DFT.

This is how far I am getting: Say I have a function $f(t)$, and its Fourier Transform $F(t)=\mathcal{F}\{f(t)\}(\nu)$ defined as $F(t)= \int_{-\infty}^{\infty} dt \, f(t)\exp(-i \,2\pi\nu t)$. Lets then say we have ideally sampled the signal at time intervals $\Delta T$ like so:

$$\bar{f}(t)=f(t)\sum_{n=-\infty}^{\infty} \delta(t-n\Delta T).$$

I understand that the FT of this signal leads me to the DTFT:

$$\bar{F}(\nu) = \mathcal{F}\{\bar{f}(t)\}(\nu) = \sum_{n=-\infty}^{\infty} f_n \exp(-i\,2\pi \nu n\,\Delta T), \, f_n = f(n \, \Delta T)$$

I also understand that $\bar{F}(\nu)$ is linked to the (continous time) Fourier Transform via:

$$\bar{F}(\nu) = \frac{1}{\Delta T}\sum_{n=-\infty}^{\infty}F\left(\nu - \frac{n}{\Delta T}\right),$$

which is a periodic function with period $1/\Delta T$. If $f(t)$ is bandlimited then the values of the DTFT at discrete frequencies $\nu_m = m/M \cdot \Delta T, \, m=0,1,...,M-1$ will give me a value proportional to the FT of $f$ at these frequencies. I also understand that I only need $M$ samples in Fourier space due to the periodicity of $\bar{F}$

Where I am struggling is to understand how to get from here to the DFT. I'll plug the discrete frequencies into the DTFT above and I further assume that the sequence $f_n$ is $M$-perdiodic such that $f_{n-kM}=f_{n}, \, k\in \mathbb{Z}$. Following this wiki article I write:

$$\begin{eqnarray} \bar{F}(\nu_m)=\bar{F}_m &=& \sum_{n=-\infty}^{\infty} f_n \exp\left(-i \,2\pi \frac{m}{M}n\right) \\ &=& \sum_{k=-\infty}^{\infty} \left(\sum_{n=0}^{M-1}\exp\left(-i \,2\pi \frac{m}{M}n\right) f_{n-kM}\right) \\ &=& \sum_{n=0}^{M-1} \exp\left(-i \,2\pi \frac{m}{M}n\right) \sum_{k=-\infty}^{\infty}f_{n-kM} \end{eqnarray}$$

The wikipedia article then calls the inner sum $\tilde{f}[n]$, which leads us to the DFT. But I fail to see how this infinite sum of a periodic series relates to the cyclic extension of a finite series. I just don't see it.

I know that this topic is a perpetual source of confusion for people and we have excellent answers e.g. here, here, and here. But I don't quite get it yet.

$\endgroup$
2
$\begingroup$

I think that your misunderstanding comes from the fact that you assume that $f[n]$ is periodic. If $f[n]$ were periodic then its DTFT would be a Dirac comb. What is happening here is that you want to find the $N$-periodic sequence whose DFT coefficients equal equidistant samples of the DTFT of $f[n]$. And it turns out that that sequence is given by

$$\tilde{f}[n]=\sum_{k=-\infty}^{\infty}f[n-kN]\tag{1}$$

which is - as expected - an aliased version of the original sequence. Remember that sampling in one domain corresponds to aliasing in the other domain.

A derivation of $(1)$ is given in this answer.

$\endgroup$
4
  • $\begingroup$ Thanks! I think that is exactly where my trouble is. So does that mean that $f[n]$ is a sequence which is not necessarily periodic and can be nonzero for all $n\in\mathbb{Z}$? I can see that the constructed sequence is obviously $N$-periodic and has something to do with my finite set of captured samples, but how does it relate intuitively? If I have captured N samples $f[n],\, n \in [0,N-1]$, do I then assume the elements outside this range to be zero? Is this the origin of the periodic extension of the samples that we always refer to when talking about the DFT? $\endgroup$
    – geo
    Dec 27 '20 at 12:37
  • 1
    $\begingroup$ Yes, $f[n]$ is generally a non-periodic and infinite sequence. The DFT considers one period of the periodic sequence $\tilde{f}[n]$ but we know that $\tilde{f}[n]$ is actually periodic and that the DFT is just a Fourier series representation of that periodic sequence. $\endgroup$
    – Matt L.
    Dec 27 '20 at 12:46
  • $\begingroup$ Thanks again. Is my intuition on why this sequence is a periodic extension of a finite dataset also justified? (The last question in the comment above) $\endgroup$
    – geo
    Dec 27 '20 at 12:51
  • 1
    $\begingroup$ @geo: If $f[n]$ is a finite length-$N$ sequence and if its DTFT is sampled at $N$ equidistant points then there is no time-domain aliasing, and $\tilde{f}[n]$ is simply a periodically extended version of $f[n]$. $\endgroup$
    – Matt L.
    Dec 27 '20 at 12:58
2
$\begingroup$

All your algebra is for infinite-length sequences, and you cannot compute a DFT of an infinite-length sequence. So let's talk about finite-length sequences. Please realize that the DTFT of a finite-length sequence is an equation where the frequency variable is a continuous variable.

And because the DTFT's frequency variable is continuous we cannot compute DTFTs using a computer. But what we CAN do is compute a single sample of a DTFT by assigning a single value (in the range of 0 –to- $2\pi$) to the DTFT's frequency variable. Doing that gives us one sample of the DTFT. The DFT, on the other hand, assigns $N$ different equally-spaced values to the DTFT's frequency variable allowing us to compute $N$ samples of the DTFT.

$\endgroup$
1
$\begingroup$

The DFT is an orthogonal matrix transform of a finite vector of data. The DTFT is the transform of potentially an infinite span of data or a function with infinite support.

If you have a function with infinite support or an infinite span of data, then you need to window it to fit it in any finite length DFT. Thus the DFT will be different due to this inherent windowing; and multiplication of a window (rectangular or otherwise) in one domain will cause a circular convolution of the two transforms in the other domain.

This is true whether (or if) the data is periodic in aperture or not.

$\endgroup$
1
$\begingroup$

I believe I answered your original 'DFT versus DTFT' question. I see from your Comment following Matt L's Answer that you are contemplating a DFT topic that is commonly misunderstood. An input sequence to the DFT can NEVER be periodic because periodic sequences are ALWAYS infinite in length---and by definition we cannot perform an infinite-length DFT.

A periodic sequence is an abstract concept, like a perfect circle or one of Euclid's lines that has infinite length but zero thickness. Such abstract concepts (such as a periodic sequence) can be useful to think about but they do not exist in the physical world.

Beware of any text that says, "The DFT assumes, views, interprets, considers, or thinks its input sequence is periodic." Such a notion is not valid. Only a living creature with a brain can make assumptions, interpret, or think.

geo, if you have a DFT input sequence of four numbers such as [2, 4, 6, 8] there are no numbers before the 2 and there are no numbers after the 8. There's no need to assume there are an infinite number of zeros before the 2 or an infinite number of zeros after the 8. A four-point DFT of four numbers produces four new numbers, no more and no less.

However(!), the mathematics of the DFT and inverse DFT does reveal that there is a "circularly repetitive" or "circularly periodic" (for the lack of better terminology) relationship between an N-sample sequence and that sequence's N-point DFT. That "circular" notion is described in many DSP textbooks.

$\endgroup$
3
  • $\begingroup$ Thank you for your answers. They were both very helpful in understanding the big picture relation between FT, DTFT and DFT. Matt L.'s answer helped me with the concrete problem I had about how the sequences relate, which is why I accepted it. $\endgroup$
    – geo
    Dec 28 '20 at 7:58
  • 1
    $\begingroup$ @geo. I just now posted a third Answer that might be mildly interesting to you. $\endgroup$ Dec 28 '20 at 12:17
  • $\begingroup$ yes, I think that is exactly the thought of text where my mental hurdle stems from. $\endgroup$
    – geo
    Dec 28 '20 at 14:05
1
$\begingroup$

@geo. To show an example of why there's so much confusion regarding "DFT periodicity", below is a paragraph from a famous college DSP textbook:

enter image description here

Think, now, of what the book is saying. It's saying we can compute an N-point DFT of an L-length x(n) input sequence that was zero-padded out to a length of N samples. That is true. But then the book says the DFT we just computed is equal to the DFT of an infinite-length x_p(n) sequence. Well how can that be true? There is no such thing as the DFT of an infinite-length sequence!

$\endgroup$
7
  • 1
    $\begingroup$ The DFT can be interpreted as a Fourier series representation of a periodic sequence. In that sense it is common (and understandable) to talk about the DFT of a periodic sequence. Of course, we just need one period to compute it, just as in the continuous-time case where we can compute Fourier series coefficients from one period of a periodic (thus infinitely long) signal. $\endgroup$
    – Matt L.
    Dec 28 '20 at 13:28
  • $\begingroup$ @Matt L. I contend that "the DFT of a periodic sequence" does not exist because the DFT algorithm cannot be performed on infinite length sequences. If I may so bold as to paraphrase Hannibal Lecter, "First principles, Matt L. Simplicity! Read Marcus Aurelius. Of each particular transform ask: what is it in itself? What is its nature? What does it do, this transform you seek?" Regarding your last sentence, What sort of machine could we use to compute the Fourier series coefficients of one period of a continuous signal? $\endgroup$ Dec 29 '20 at 19:44
  • $\begingroup$ I think we all understand that we don't take infinitely many values as the input to the DFT. As mentioned in my previous comment, the DFT is just a Fourier series of a periodic sequence. Would you also claim that we can't compute the Fourier series of a continuous-time periodic function because the function extends over the infinite interval $(-\infty,\infty)$? With periodic functions and sequences we always just need and use one single period to compute anything we ever might want to know about that function or sequence. $\endgroup$
    – Matt L.
    Dec 29 '20 at 19:52
  • $\begingroup$ @Matt L. Two questions: Do you agree that periodic sequences do not exist in our physical world? And again, What sort of machine could we use to compute the Fourier series coefficients of one period of a continuous signal? $\endgroup$ Dec 29 '20 at 20:11
  • $\begingroup$ I'm afraid this doesn't get us anywhere. The DFT is a Fourier series expansion of a periodic sequence, and this is what is meant when people talk about the DFT of a periodic sequence. I assume that you agree that such an expansion exists and that it is given by the DFT, regardless of the existence of periodic sequences in the physical world. The rest is semantics ... $\endgroup$
    – Matt L.
    Dec 29 '20 at 21:06

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.