Discrete-time Fourier transform

The Fourier transform of a function $x[n]\,$ of a discrete "time" variable $n\,$ (where $n\,$ is an integer) is called the discrete-time Fourier transform (or DTFT), and is mathematically the inverse of a Fourier series expansion. Equivalently, it can be derived from the continuous Fourier transform of a sequence of regularly spaced impulses with amplitudes $x[n]\,$ . If frequency ( $f$ ) is expressed in terms of cycles per sample, the transform becomes:

\sum _{n=-\infty }^{\infty }x[n]\,e^{-i2\pi fn}\,

But with the customary substitution: $\omega =2\pi f\,$ (radians per sample), it is written:

X(\omega )=\sum _{n=-\infty }^{\infty }x[n]\,e^{-i\omega n}\,

This frequency spectrum is a function of a continuous frequency domain.

In addition:

$e^{-i(\omega +2\pi )n}\,$	$=e^{-i\omega n}\cdot e^{-i2\pi n}=e^{-i\omega n}\cdot {(e^{-i2\pi })}^{n}=e^{-i\omega n}\cdot {(1)}^{n}\,$
	$=e^{-i\omega n}\,$

from which it follows that the DTFT spectrum is periodic in 2π:

X(\omega )=X(\omega +2\pi )=X(\omega +2\pi k)\,

for any integer k. Consequently, the inverse transform requires integration over only one period:

x[n]={\frac {1}{2\pi }}\int _{-\pi }^{\pi }X(\omega )\,e^{i\omega n}\,d\omega

which is identical to a Fourier series expansion/decomposition.

An alternative notation for the transformed function is frequently used:

X(e^{i\omega })\equiv X(\omega )

The use of this notation emphasizes the relationship of the DTFT to the Z-transform.

Finite length sequences

For practical evaluation of the DTFT numerically, a finite-length sequence is obviously needed. For instance, a long sequence might be modified by a rectangular window function, resulting in:

X(\omega )=\sum _{n=0}^{L-1}x[n]\,e^{-i\omega n}\,

, where

L\,

is the modified sequence length.

This is often a useful approximation of the spectrum of the unmodified sequence. The difference is a loss of clarity (resolution), which improves as L increases.
It is common to evaluate $X(\omega )$ at an arbitrary number $(N)$ of uniformly-spaced frequencies across one period (2π):

\omega _{k}={\frac {2\pi }{N}}k\,

, for

k=0,1,\dots ,N-1\,

which gives:

X[k]=X(\omega _{k})=\sum _{n=0}^{L-1}x[n]\,e^{-i2\pi {\frac {k}{N}}n}

When $N\geq L\,$ , this can also be written:

X[k]=\sum _{n=0}^{N-1}x[n]\,e^{-i2\pi {\frac {k}{N}}n}

, because we define

x[n]=0\,

for

n\geq L\,

.

With that cosmetic adjustment, the $X[k]\,$ sequence is now recognizable as a discrete Fourier transform (DFT). While $N$ defines the resolution at which we sample the DTFT, $L$ limits the inherent resolution of the DTFT itself. So they are usually similar (or equal) values. And while it is common to choose $N>L$ , the only reason to include the zero-valued terms in the summation is to take advantage of a fast Fourier transform algorithm for computing the DFT. However, when that is done it is often given undue significance, such as zero-padded DFT and/or interpolated DFT. But obviously the exact same DFT can be calculated straightforwardly without the zero-valued terms. One can also compute the DTFT for the case of $N<L$ (or for other frequency samplings) where it is not equivalent to a DFT.

To illustrate why $N>L$ is common, consider the sequence:

x[n]=e^{i2\pi {\frac {1}{8}}n}

, and

L=64

.

The two figures below are plots of the magnitude of two different sized DFTs, as indicated in their labels. In both cases, the dominant component is at the signal frequency: $f={\begin{matrix}{\frac {1}{8}}\end{matrix}}=0.125\,$ . Also visible on the right is the spectral leakage pattern of the $L=64$ rectangular window. The illusion on the left is a result of sampling the DTFT at all of its zero-crossings. Rather than the DTFT of a finite-length sequence, it gives the impression of an infinitely long sinusoidal sequence. Contributing factors to the illusion are the use of a rectangular window, and the choice of a frequency ( ${\begin{matrix}{\frac {1}{8}}\end{matrix}}={\begin{matrix}{\frac {8}{64}}\end{matrix}}$ ) with exactly 8 (an integer) cycles per 64 samples.

Difference between the DTFT and other Fourier transforms

Essentially, the DTFT is the reverse of the Fourier series, in that the latter has a continuous, periodic input and a discrete spectrum. The applications of the two transforms, however, are quite different.

The DFT and the DTFT can be viewed as the logical result of applying the standard continuous Fourier transform to discrete data. From that perspective, we have the satisfying result that it's not the transform that varies, it's just the form of the input:

If it is discrete, the Fourier transform becomes a DTFT.
If it is periodic, the Fourier transform becomes a Fourier series.
If it is both, the Fourier transform becomes a DFT.

Relationship to the Z-transform

The DTFT is a special case of the Z-transform. The Z-transform is defined as the sum.

\sum _{n=-\infty }^{\infty }x[n]\,z^{-n}

If we evaluate the Z-transform at $z=e^{i\omega }$ , then we recover the DTFT. For this reason, the notation $X(e^{i\omega })$ is sometimes preferred over the notation $X(\omega )$ for representing the DTFT.

Note that evaluating at $z=e^{i\omega }$ is equivalent to evaluating the Z-transform at on the unit circle in the complex plane.

Table of Discrete-time Fourier transforms

Here is a table with the list of the most common transforms. The following notation will be used:

$u[n]\!$ is the discrete-time unit step function
$\operatorname {sinc} (t)\!$ is the sinc function for real-valued argument t
$\delta (\omega )\!$ is the Dirac delta function
$\delta [n]\!$ is the Kronecker delta $\delta _{n,0}\!$
$\operatorname {rect} _{2\Delta }(t)={\begin{cases}1&-\Delta \leq t\leq \Delta \\0&{\mbox{otherwise}}\end{cases}}$
$\operatorname {tri} _{2\Delta }(t)={\begin{cases}1+{\frac {t}{\Delta }};&-\Delta \leq t\leq 0\\1-{\frac {t}{\Delta }};&0<t\leq \Delta \\0&{\mbox{otherwise}}\end{cases}}$

The first column shows the function in the time domain, the second one in the frequency domain:

Time domain $x[n]\,$	Frequency domain $X(\omega )\,$	Remarks
$u[n]\!$	${\frac {1}{1-e^{j\omega }}}\!$
$\cos[an]\!$	${\frac {1}{2}}\left[\delta (\omega -a)+\delta (\omega +a)\right]$
$\sin[an]\!$	${\frac {1}{2i}}\left[\delta (\omega -a)-\delta (\omega +a)\right]$
$\mathrm {rect} \left[{(n-M/2) \over M}\right]$	${\sin[\omega (M+1)/2] \over \sin(\omega /2)}\,e^{-i\omega M/2}$	integer M
$\operatorname {sinc} [\pi (a+n)]$	$e^{ia\omega }\!$	real number a
$\delta [n]\!$	$1\!$
$\delta [n-k]\!$	$e^{-ik\omega }\!$	integer k
${\frac {\Delta }{2\pi }}\operatorname {sinc} ^{2}\left[{\frac {\Delta }{2}}n\right]$	$\operatorname {tri} _{2\Delta }(\omega )$
${\frac {\Delta }{\pi }}\operatorname {sinc} [\Delta (n+a)]$	$\operatorname {rect} _{2\Delta }(\omega )\cdot e^{ja\omega }$
${\frac {\Delta }{\pi (n+a)}}\left\{\cos[\Delta (n+a)]-\operatorname {sinc} [\Delta (n+a)]\right\}$	$j\omega \operatorname {rect} _{2\Delta }(\omega )e^{ja\omega }$
${\frac {1}{\pi n^{2}}}[(-1)^{n}-1]$	$\|\omega \|\!$
${\frac {C(A+B)}{2\pi }}\cdot \operatorname {sinc} \left[{\frac {A-B}{2}}n\right]\cdot \operatorname {sinc} \left[{\frac {A+B}{2}}n\right]$

Properties

This table shows the relationships between generic discrete-time Fourier transforms. We use the following notation:

$*\!$ is the convolution between two signals
$x[n]^{*}\!$ is the complex conjugate of the function x[n]
$\rho _{xy}[n]\!$ represents the correlation between x[n] and y[n].

The first column provides a description of the property, the second column shows the function in the time domain, the third column shows the spectrum in the frequency domain:

Property	Time domain $x[n]\!$	Frequency domain $X(\omega )\!$	Remarks
Linearity	$ax[n]+by[n]\!$	$aX(\omega )+bY(\omega )\!$
Shift in time	$x[n-k]\!$	$X(\omega )e^{-i\omega k}\!$	integer k
Shift in frequency	$x[n]e^{ian}\!$	$X(\omega -a)\!$	real number a
Time reversal	$x[-n]\!$	$X(-\omega )\!$
Time conjugation	$x[n]^{*}\!$	$X(-\omega )^{*}\!$
Time reversal & conjugation	$x[-n]^{*}\!$	$X(\omega )^{*}\!$
Derivative in frequency	${\frac {n}{i}}x[n]\!$	${\frac {dX(\omega )}{d\omega }}\!$
Integral in frequency	${\frac {i}{n}}x[n]\!$	$\int _{-\pi }^{\omega }X(\vartheta )d\vartheta \!$
Convolve in time	$x[n]*y[n]\!$	$X(\omega )\cdot Y(\omega )\!$
Multiply in time	$x[n]\cdot y[n]\!$	${\frac {1}{2\pi }}X(\omega )*Y(\omega )\!$
Correlation	$\rho _{xy}[n]=x[-n]^{}y[n]\!$	$R_{xy}(\omega )=X(\omega )^{*}\cdot Y(\omega )\!$