Why Does the DFT Assume the Transformed Signal Is Periodic?

Question

In many signal processing books, it is claimed that the DFT assumes the transformed signal to be periodic (and that this is the reason why spectral leakage for example may occur).

Now, if you look at the definition of the DFT, there is simply no that kind of assumption. However, in the Wikipedia article about the discrete-time Fourier transform (DTFT), it is stated that

When the input data sequence $x[n]$ is $N$-periodic, Eq.2 can be computationally reduced to a discrete Fourier transform (DFT)

• So, does this assumption stems from the DTFT?
• Actually, when calculating the DFT, am I in fact calculating the DTFT with the assumption that the signal is periodic?

Answer 1

There are already some good answers, but I still feel like adding yet another explanation, because I consider this topic extremely important for the understanding of many aspects of digital signal processing.

First of all it is important to understand that the DFT does not 'assume' periodicity of the signal to be transformed. The DFT is simply applied to a finite signal of length $N$ and the corresponding DFT coefficients are defined by

$$X[k]=\sum_{n=0}^{N-1}x[n]e^{-j2\pi nk/N},\quad k=0,1,\ldots,N-1\tag{1}$$

From (1) it is obvious that only samples of $x[n]$ in the interval $[0,N-1]$ are considered, so no periodicity is assumed. On the other hand, the coefficients $X[k]$ can be interpreted as Fourier coefficients of the periodic continuation of the signal $x[n]$. This can be seen from the inverse transform

$$x[n]=\sum_{k=0}^{N-1}X[k]e^{j2\pi nk/N}\tag{2}$$

which computes $x[n]$ correctly in the interval $[0,N-1]$, but it also computes its periodic continuation outside this interval because the right-hand side of (2) is periodic with period $N$. This property is inherent in the definition of the DFT, but it need not bother us because normally we're only interested in the interval $[0,N-1]$.

Considering the DTFT of $x[n]$

$$X(\omega)=\sum_{n=-\infty}^{\infty}x[n]e^{-jn\omega}\tag{3}$$

we can see by comparing (3) with (1), that if $x[n]$ is a finite sequence in the interval $[0,N-1]$, the DFT coefficients $X[k]$ are samples of the DTFT $X(\omega)$:

$$X[k]=X(2\pi k/N)\tag{4}$$

So one use of the DFT (but certainly not the only one) is to compute samples of the DTFT. But this only works if the signal to be analyzed is of finite length. Usually this finite length signal is constructed by windowing a longer signal. And it is this windowing which causes spectral leakage.

As a last remark, note that the DTFT of the periodic continuation $\tilde{x}[n]$ of the finite sequence $x[n]$ can be expressed in terms of the DFT coefficients of $x[n]$:

$$\tilde{x}[n]=\sum_{k=-\infty}^{\infty}x[n-kN]\tag{5}$$ $$\tilde{X}(\omega)=\frac{2\pi}{N}\sum_{k=-\infty}^{\infty}X[k]\delta(\omega-2\pi k/N)\tag{6}$$

EDIT: The fact that $\tilde{x}[n]$ and $\tilde{X}(\omega)$ given above are a DTFT transform pair can be shown as follows. First note that the DTFT of a discrete time impulse comb is a Dirac comb:

$$\sum_{k=-\infty}^{\infty}\delta[n-kN]\Longleftrightarrow\frac{2\pi}{N}\sum_{k=-\infty}^{\infty}\delta(\omega-2\pi k/N)\tag{7}$$

The sequence $\tilde{x}[n]$ can be written as the convolution of $x[n]$ with an impulse comb:

$$\tilde{x}[n]=x[n]\star \sum_{k=-\infty}^{\infty}\delta[n-kN]\tag{8}$$

Since convolution corresponds to multiplication in the DTFT domain, the DTFT $\tilde{X}(\omega)$ of $\tilde{x}[n]$ is given by the multiplication of $X(\omega)$ with a Dirac comb:

$$\begin{align}\tilde{X}(\omega)&=X(\omega)\cdot\frac{2\pi}{N}\sum_{k=-\infty}^{\infty}\delta(\omega-2\pi k/N)\\&=\frac{2\pi}{N}\sum_{k=-\infty}^{\infty}X(2\pi k/N)\delta(\omega-2\pi k/N)\end{align}\tag{9}$$

Combining $(9)$ with $(4)$ establishes the result $(6)$.

Answer 2

It's an un-necessary (and often false) assumption. The DFT is just a basis transform of a finite vector.

The basis vectors of the DFT just happen to be snippets of infinitely extensible periodic functions. But there is nothing inherently periodic about the DFT input or results unless you extend the basis vectors outside the DFT aperture. Many forms of signal analysis do not require any extension or assumptions outside the sampled window or finite data vector.

Any "leakage" artifacts can also be assumed to be from a convolution of the default rectangular window with a signal that is not periodic or is of unknown periodicity or stationarity. This makes much more sense when analyzing overlapped FFT windows, where any assumption of periodicity outside of any one DFT or FFT window can be inconsistent with the data in other windows.

Periodicity may make the math relating the DFT to the DTFT more tractable. But any relationship to the DTFT may or may not be necessary when actually using an FFT for signal processing (depending on exactly which Fourier transform properties are needed for further analysis of the processing method).

Answer 3

It comes from the definition of the time domain signal:

$$ x \left[ n \right] = \sum_{k = 0}^{N - 1} X \left[ k \right] {e}^{\frac{2 \pi i n k}{N}} $$

You can see by definition that $ x \left[ n \right] = x \left[ n + N \right] $.
On the other hand the DFT reconstruct perfectly the N samples of the signal.
Hence you can conclude it assumes a periodic continuation of it.

Another point of view would be looking at the DFT as a Finite Discrete Fourier Series (It actually is, Have a look at Discrete Fourier Series - DFS), which of course points that the signal is periodic (Finite summation of signals with period $ T $ is a signal which has a period $ T $).

Answer 4

Ok, my answer will be somewhat different than the other answers. My answer accepts the premise of the question rather than denies the premise of the question.

The reason that the DFT "assumes" the input signal (the signal to be transformed, what I assume the OP means by "transformed signal") is periodic is because the DFT fits a collection of basis functions to that input signal, all of which are periodic.

Consider a different set of basis functions:

$$ g_k(u) \triangleq u^k \quad \quad 0 \le k < N $$

and given $N$ input samples:

$$ x[n] \quad \quad 0 \le n < N $$

We can fit a linear sum of these basis functions $g_k(n)$ to the input sequence

$$ \begin{align} x[n] & = \sum\limits_{k=0}^{N-1} X[k] g_k(n) \\ & = \sum\limits_{k=0}^{N-1} X[k] n^k \\ \end{align}$$

with judicious selection of the coefficients $X[k]$. Calculating all $X[k]$ requires solving $N$ linear equations with $N$ unknowns. You can use Gaussian elimination to do it.

With the $N$ correct values for $X[k]$ for $0 \le k \le N-1$, we can make sure that the sum of these power functions (which is an $(N-1)$th-order polynomial) will evaluate exactly to $x[n]$ for each $n$ such that $0 \le n \le N-1$.

Now what if you use that summation to go beyond the interval of $0 \le n \le N-1$? you can evaluate it for any $n$. You will notice that the behavior of that function will be that of an $(N-1)$th-order polynomial because that is what it is. For $n$ large enough, only the highest power with a non-zero coefficient will set the trend for the extrapolated $x[n]$.

So now, with the DFT we are fitting a different set of basis functions to our input sequence:

$$ g_k(u) \triangleq \frac{1}{N} e^{+j 2 \pi k u/N} \quad \quad 0 \le k < N $$

$$ \begin{align} x[n] & = \sum\limits_{k=0}^{N-1} X[k] g_k(n) \\ & = \frac{1}{N} \sum\limits_{k=0}^{N-1} X[k] e^{+j2\pi n k/N} \\ \end{align}$$

and the coefficients, $X[k]$, can be solved for and are:

$$ X[k] = \sum\limits^{N-1}_{n=0} x[n] \ e^{-j2\pi n k/N} $$

The placement of that $\frac{1}{N}$ is a matter of convention. I am putting it where most of the literature puts the $\frac{1}{N}$ factor. It could be removed from the $x[n]$ equation and put in the $X[k]$ equation, instead. or "half" of it ($\sqrt{\frac{1}{N}}$) could be placed with both equations. It's just a matter of convention.

But here we are fitting a set of basis functions that are all periodic with period $N$ to the original $x[n]$. So even if $x[n]$ came from a longer sequence was not periodic, the DFT is considering that $x[n]$ is the sum of a bunch of basis functions each that are periodic with period $N$. If you add up a bunch of periodic functions, all with the same period, the sum must also be periodic with the same period.

Answer 5

DFT is discrete. DTFT is continuous. We can get DFT from DTFT by sampling it with the pulse train of the right period, which is actually equal to multiplying it with the pulse train. Multiplication in the transform domain is equal to convolution in discrete-time domain, this implies periodicity of signal.

Answer 6

Only DFT is practical in discrete digital world because of periodic assumption on both domains. (If you call it like that.) Because non periodic signal on one domain cause continuous signal on the other and you can only store discrete signal in digital memory. So you need to assume the signals are periodic on both domains to make it discrete on both domains.

When you calculate DTFT you get continuous signal in frequency domain as the output.
I don't think you will use the same procedure when you calculate DFT in practical. When you actually calculated both DTFT and DFT you will understand that both transform calculation are different stories.

Answer 7

Since the signal is periodic, the time shifted signal doesn't change the absolute magnitude of the frequency domain.

$$ X \left[ k \right] = \sum_{k = 0}^{N - 1} x \left[ n \right] {e}^{\frac{2 \pi i n k}{N}} $$

$$ {e}^{\frac{-2 \pi i D k}{N}}X \left[ k \right] = \sum_{k = 0}^{N - 1} x \left[ n - D \right] {e}^{\frac{2 \pi i n k}{N}}{e}^{\frac{-2 \pi i D k}{N}} $$

By the way, there is nothing stopping you from taking the FFT of a non-periodic signal, but there it little practical use if none of the transformations work.

Answer 8

I have a different way of describing this so will add an additional answer. How I interpret any comment that "the DFT assumes the input is periodic" is that the resulting answer in the DFT will be identical to what we would get if the input waveform periodically repeated at the same original sampling rate (and not that the DFT has achieved consciousness and sentience), with some very important caveats that I will add here.

To be identical, we must consider only the resulting values at the original frequency locations, AND the DFT must be scaled by the total number of samples. Every time we repeat a sequence in time, the resulting DFT will have a zero inserted in between every original sample in frequency, with the number of zeros consistent with the number of repetitions of the time domain waveform. If we assume the sampling rate has not changed, the resulting values at the original frequency locations for the original sequence will grow by the number of repetitions. So if we scale by the total number of samples, then in the limit as the time domain approach infinity in both directions with a periodic input waveform, the resulting DFT will become a continuous function in frequency with the non-zero values identical to our original result. Note too interestingly that as the number of samples in the time domain increases (as we consider more and more repetitions in time), it will match the total number of samples in frequency from DC up to one sample less than the sampling rate: As we extend the time axis toward infinity; this maps to an infinite number of samples in this limited frequency range! (We can also show how there is a similar equivalence to periodicity in the frequency domain which would equivalently map to additional zeros in between the samples in the time domain, with the time domain in the limit also becoming a continuous function!).

I add a simple demonstration below to be very clear on the conditions where the resulting DFT is "identical" starting with the DFT of an example sequence given as [5, -4, 6, 6, -4]. For convenience, I chose an example sequence that would always result in a real DFT.

The resulting DFT scaled by the total number of samples is given by:

$$X[k] = \frac{1}{N}\sum_{n=0}^{N-1}x[n]e^{-j2 \pi n k/N}$$

and is plotted below. I plotted using fftshift which centers the spectrum on DC ($k=0$) and is equivalent to indexing through k as given below:

X[k] for x[n] = [5, -4, 6, 6, -4], with n=[0,1,2,3,4] and k = [-2,-1,0,1,2]

Below shows the result for another sequence that is this same sequence repeated three times as

x[n] = [5, -4, 6, 6, -4, 5, -4, 6, 6, -4, 5, -4, 6, 6, -4]:

DFT Repeating Same Sequence 3 Times

To make it clear under what condition the result is equivalent, I scaled the index so that what is shown on the horizontal axis is the same frequency value, consistent with a condition that the sampling rate hasn't changed. Thus all the original frequencies from the original sequence will have the same result, as long as the DFT itself is also scaled as described above.

And again after repeating the original sequence 9 times.

DFT Repeating Same Sequence 9 Times

Hopefully these examples make it clear under what is meant by the equivalence to a periodic time domain signal. We see how in the limit the DFT result for an actual periodic signal that extended to $\pm \infty$ would be a continuous function in frequency (and in the limit become a Discrete Time Fourier Transform or DTFT, but in this case for an actual periodic waveform where a DTFT for a finite length sequence would extend the time index to infinity with zero padding, still resulting in a continuous function in frequency).

The stated equivalence is with the result for the original frequency locations specifically: If we maintain the same sampling rate in time (simply repeat the original sequence periodically), and if we scale the DFT result by the total number of samples, then we can repeat the waveform any number of integer times and get the same result at each of the original frequencies (and zero elsewhere).