How is the DTFT of a periodic, sampled signal linked to the DFT?

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

@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:

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!