8
$\begingroup$

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?
$\endgroup$
  • $\begingroup$ Because DFT X[k] of x[n] is the first period of the Discrete Fourier Series (DFS) of the periodic signal xp[n] whose first period is taken as x[n] $\endgroup$ – Fat32 Feb 18 '15 at 11:41
  • 1
    $\begingroup$ looks like i will have to write a dissenting answer to this. the DFT assumes the transformed signal is periodic because it is fitting a set of basis functions to the transformed signal, all of which are periodic. $\endgroup$ – robert bristow-johnson Feb 27 '15 at 0:14
  • 1
    $\begingroup$ The DFT is just the simplified expression of the DFS, thus the periodic assumption inherently exists. $\endgroup$ – lxg Oct 5 '16 at 4:49
10
$\begingroup$

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)$.

$\endgroup$
  • $\begingroup$ down arrowed this answer for the same reason i have @hotpaw2 's more recent answer. in this statement: "From (1) it is obvious that only samples of $x[n]$ in the interval $[0,N−1]$ are considered, so no periodicity is assumed." the conclusion does not follow from the premise. $\endgroup$ – robert bristow-johnson Feb 27 '15 at 0:08
  • 3
    $\begingroup$ @robertbristow-johnson: It does. Give me $N$ consecutive samples, and I give you the DFT. I do not need to assume anything about the signal outside the range $[0,N-1]$, not even its existence. This is the only thing I claim in that sentence, and it is obviously true. For computing the DFT I don't need to know anything except the values in the interval $[0,N-1]$. Not sure how you could misunderstand or misread my statement. If it's a formulation issue then I'd be glad to clarify my sentence, but content-wise it is actually trivial. $\endgroup$ – Matt L. Feb 27 '15 at 10:03
  • 4
    $\begingroup$ read the other answer below and my answer at the other thread. it's not about what you assume about $x[n]$ outside of $0 \le n \le N-1$. it's about what the transform "assumes" (if we are allowed to anthropomorphize a little) about $x[n]$ outside of $0 \le n \le N-1$. we can find out what the transform assumes when we invoke an operation in one domain that shifts the other domain by an integer amount. $\endgroup$ – robert bristow-johnson Feb 27 '15 at 13:45
8
$\begingroup$

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), which of course points that the signal is periodic (Finite summation of signals with period $ T $ is a signal which has a period $ T $).

$\endgroup$
  • 2
    $\begingroup$ I don't see how it comes from the definition. $\endgroup$ – user10839 Aug 17 '14 at 11:37
  • 1
    $\begingroup$ @user10839: Just evaluate $x[n+N]$ and you'll see that it equals $x[n]$. As pointed out in the answer, the DFT is just a Fourier series of the time domain signal. The finite length of the time domain signal is considered the fundamental period. $\endgroup$ – Matt L. Aug 17 '14 at 12:04
  • $\begingroup$ @user10839, Just plug it into the equation. The exponent can be defined with the Cosine and Sine functions, which as can be seen have period of $ \frac{nk}{N} $. $\endgroup$ – Royi Feb 18 '15 at 11:38
  • 1
    $\begingroup$ DFT isn't the DFS. This is pedantic, but DFT gives you the Fourier series coefficients. It's important to note that DFT is just like any other linear transforms. It's a matrix multiplication. The matrix is orthonormal, which makes it nice. It can also be shown that the output equal coefficients of the corresponding Fourier series expansion of the data, but the Fourier transform is not the Fourier series (type mismatch :p). $\endgroup$ – thang Feb 27 '15 at 5:12
5
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ down arrowed for the same reason i down-arrowed your more recent answer about this. $\endgroup$ – robert bristow-johnson Feb 27 '15 at 0:10
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ for a little more polemic, where i dispute the notion that the DFT does not necessarily periodically extend the data passed to it, please look at this previous answer from me. i would rather not repeat it here. $\endgroup$ – robert bristow-johnson Feb 27 '15 at 4:44
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ DTFT is continuous? How come? $\endgroup$ – jojek Aug 17 '14 at 14:26
  • 2
    $\begingroup$ The result of the DTFT is continous (in frequency). $\endgroup$ – Deve Aug 17 '14 at 14:37
  • $\begingroup$ Indeed - thus you should state it clearly to avoid any misunderstanding and supply adequate equations. $\endgroup$ – jojek Aug 17 '14 at 15:03
  • $\begingroup$ @jojek Thats true, I also think this answer could be improved by some equations $\endgroup$ – Deve Aug 17 '14 at 15:05
  • 1
    $\begingroup$ Ill add more details very soon. $\endgroup$ – learner Aug 17 '14 at 15:13
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

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.