Discrete-time Fourier transform

Fourier transforms
	Continuous Fourier transform
	Fourier series
	Discrete Fourier transform
	Discrete-time Fourier transform
	Related transforms

From Wikipedia, the free encyclopedia

Jump to: navigation, search

In mathematics, the discrete-time Fourier transform (DTFT) is one of the specific forms of Fourier analysis. As such, it transforms one function into another, which is called the frequency domain representation, or simply the "DTFT", of the original function (which is often a function in the time-domain). But the DTFT requires an input function that is discrete. Such inputs are often created by sampling a continuous function, like a person's voice.

The DTFT frequency-domain representation is always a periodic function. Since one period of the function contains all of the unique information, it is sometimes convenient to say that the DTFT is a transform to a "finite" frequency-domain (the length of one period), rather than to the entire real line. It is Pontryagin dual to the Fourier series, which transforms from a periodic domain to a discrete domain.

[edit] Definition

Given a discrete set of real or complex numbers: $x[n], \; n\in\mathbb{Z}$ (integers), the discrete-time Fourier transform (or DTFT) of $x[n]\,$ is usually written:

$X(\omega) = \sum_{n=-\infty}^{\infty} x[n] \,e^{-i \omega n}.$

(Eq.1)

[edit] Relationship to sampling

Often the $x[n]\,$ sequence represents the values (aka samples) of a continuous-time function, $x(t)\,$ , at discrete moments in time: $t = nT\,$ , where $T\,$ is the sampling interval (in seconds), and $1/T = f_s\,$ is the sampling rate (samples per second). Then the DTFT provides an approximation of the continuous-time Fourier transform:

$X(f) = \int_{-\infty}^\infty x(t)\cdot e^{- i 2\pi f t}\,dt.$

To understand this, consider the Poisson summation formula, which indicates that a periodic extension of function $X(f)\,$ can be constructed from the samples of function $x(t).\,$ The result is:

$X_T(f)\ \stackrel{\mathrm{def}}{=} \sum_{k=-\infty}^{\infty} X\left(f - k f_s\right) \equiv T \sum_{n=-\infty}^{\infty} x(nT)\ e^{-i 2\pi f T n}.$

(Eq.2)

The right-hand sides of Eq.2 and Eq.1 are identical with these associations:

$x[n] = T\cdot x(nT)\,$

$\omega = 2\pi f T = 2\pi \left( \frac{f}{f_s}\right).\,$

$X_\mathrm{T}(f)\,$ comprises exact copies of $X(f)\,$ that are shifted by multiples of ƒ_s and combined by addition. For sufficiently large ƒ_s, the k=0 term can be observed in the region [−ƒ_s/2, ƒ_s/2] with little or no distortion (aliasing) from the other terms.

Normalized frequency

Since $f\,$ represents ordinary frequency (cycles per second) and $f_s\,$ has units of samples per second, the units of $f / f_s\,$ are cycles per sample. It is common notational practice to replace this ratio with a single variable, called normalized frequency, which represents actual frequencies as multiples (usually fractional) of the sample rate. $\omega\,$ , as defined above, is also a normalized frequency, but its units are radians per sample. The normalized frequency has the added bonus that the function $X (ω)$ is periodic with period $2π$ . So the inverse transform need only be evaluated in the interval $2π$ .

[edit] Periodicity

Sampling $x(t)\,$ causes its spectrum (DTFT) to become periodic. In terms of ordinary frequency, $f\,$ (cycles per second), the period is the sample rate, $f_s\,$ . In terms of normalized frequency, $f / f_s\,$ (cycles per sample), the period is $1$ . And in terms of $\omega\,$ (radians per sample), the period is $2π$ , which also follows directly from the periodicity of $e^{-i \omega n}\,$ . That is:

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

where both n and k are arbitrary integers. Therefore:

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

The popular alternate notation $X(e^{i \omega})\,$ for the DTFT $X(\omega)\,$ :

highlights the periodicity property, and
helps distinguish between the DTFT and underlying Fourier transform of $x(t)\,$ ; that is, $X(f)\,$ (or $X(\omega)\,$ ), and
emphasizes the relationship of the DTFT to the Z-transform.

However, its relevance is obscured when the DTFT is formed by the frequency domain method (superposition), as discussed above. So the notation $X(\omega)\,$ is also commonly used, as in the table to follow.

[edit] Inverse transform

The following inverse transforms recover the discrete-time sequence:

$x[n]\,$	$= \frac{1}{2 \pi}\int_{-\pi}^{\pi} X(\omega)\cdot e^{i \omega n} \, d \omega$
	$= T \int_{-\frac{1}{2T}}^{\frac{1}{2T}} X_T(f)\cdot e^{i 2 \pi f nT}\, df.$

The integrals span one full period of the DTFT, which means that the x[n] samples are also the coefficients of a Fourier series expansion of the DTFT. Infinite limits of integration change the transform into a continuous-time Fourier transform [inverse], which produces a sequence of Dirac impulses. That is:

$\begin{align} \int_{-\infty}^\infty X_T(f)\cdot e^{i 2 \pi f t}\, df &=\int_{-\infty}^\infty \left(T \sum_{n=-\infty}^{\infty} x(nT)\ e^{-i 2\pi f T n}\right)\cdot e^{i 2 \pi f t}\, df \\ &=\sum_{n=-\infty}^{\infty} T\cdot x(nT) \int_{-\infty}^\infty e^{-i 2\pi f T n}\cdot e^{i 2 \pi f t}\, df \\ &=\sum_{n=-\infty}^{\infty} x[n]\cdot \delta(t - n T). \end{align}$

[edit] 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 (ω)$ 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^{-i 2 \pi \frac{k}{N} n}$

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

$X[k] = \sum_{n=0}^{N-1} x[n] \,e^{-i 2 \pi \frac{k}{N} n}$ , because we define $x[n] = 0\,$ for $n \ge 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^{i 2\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.

DFT for L = 64 and N = 64

DFT for L = 64 and N = 256

[edit] Difference between the DTFT and other Fourier transforms

The DTFT is the reverse of the Fourier series, in that the latter has a continuous, periodic input and a discrete spectrum: formally, they are Pontryagin dual. 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.

One can summarize this data in terms of the original domain and the transform domain:

Transform	Original domain	Transform domain
Fourier transform	R	R
Fourier series	S¹	Z
DTFT	Z	S¹
DFT	Z/nZ	Z/nZ

where R is the real line, S¹ is the circle (the domain for periodic functions), Z is the integers (the domain for discrete functions), and Z/nZ is the integers modulo n (as in modular arithmetic), the domain for periodic discrete functions.

From the point of view of Pontryagin duality, the Fourier transform and the DFT are self-dual, as the original domain and transform domain are isomorphic (the original domain and transform domain should be thought of as two separate copies of R, respectively Z/nZ, not as the same space) while Fourier series and the DTFT are dual to each other.

[edit] Relationship to the Z-transform

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

$X(z) = \sum_{n=-\infty}^{\infty} x[n] \,z^{-n}$

So the special case is: $z = e^{i \omega}\,$ . Since $|e^{i \omega}| = 1\,$ , it is the evaluation of the Z-transform around the unit circle in the complex plane.

[edit] Table of discrete-time Fourier transforms

Some common transform pairs are shown below. The following notation applies:

$n \!$ is an integer representing the discrete-time domain (in samples)
is a real number in , representing continuous angular frequency (in radians per sample).
- The remainder of the transform $(|\omega| > \pi \,)$ is defined by: $X(\omega + 2\pi k) = X(\omega)\,$
$u[n] \!$ is the discrete-time unit step function
$\operatorname{sinc}(t) \!$ is the normalized sinc function
$\delta (\omega) \!$ is the Dirac delta function
$\delta [n] \!$ is the Kronecker delta $\delta_{n,0} \!$
$\operatorname{rect}(t)$ is the rectangle function for arbitrary real-valued t:

$\mathrm{rect}(t) = \sqcap(t) = \begin{cases} 0 & \mbox{if } |t| > \frac{1}{2} \\[3pt] \frac{1}{2} & \mbox{if } |t| = \frac{1}{2} \\[3pt] 1 & \mbox{if } |t| < \frac{1}{2} \end{cases}$

$\operatorname{tri}(t)$ is the triangle function for arbitrary real-valued t:

$\operatorname{tri}(t) = \and (t) = \begin{cases} 1 + t; & - 1 \leq t \leq 0 \\ 1 - t; & 0 < t \leq 1 \\ 0 & \mbox{otherwise} \end{cases}$

Time domain $x[n] \,$	Frequency domain $X(\omega) \,$	Remarks
$\delta [n] \!$	$1 \!$
$\delta [n - M] \!$	$e^{-i \omega M} \!$	integer M
$\sum_{m = -\infty}^{\infty} \delta[n - M m] \,$	$\sum_{m = -\infty}^{\infty} e^{-i \omega M m} = \frac{1}{M}\sum_{k = -\infty}^{\infty} \delta \left( \frac{\omega}{2\pi} - \frac{k}{M} \right) \,$	integer M
$u[n]\!$	$\frac{1}{1-e^{-i \omega}} \!$
$e^{-ian} \!$	$2\pi \delta (\omega + a) \,$	real number a
$\cos (a n) \!$	$\pi \left[ \delta (\omega - a) + \delta (\omega + a) \right]$	real number a
$\sin (a n) \!$	$\frac{\pi}{i} \left[ \delta (\omega - a) - \delta ( \omega + a) \right]$	real number a
$\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} [(a + n)]$	$e^{i a \omega} \!$	real number a
$W\cdot \operatorname{sinc}^2(W n)\,$	$\operatorname{tri} \left( { \omega \over 2\pi W } \right)$	real number W $0 < W \le 0.5$
$W\cdot \operatorname{sinc} [ W (n + a)]$	$\operatorname{rect} \left( { \omega \over 2\pi W } \right) \cdot e^{j a \omega}$	real numbers W, a $0 < W \le 1$
$\begin{cases} 0 & n=0 \\ \frac{(-1)^n}{n} & \mbox{elsewhere} \end{cases}$	$j ω$	it works as a differentiator filter
$\frac{W}{(n + a)} \left\{ \cos [ \pi W (n+a)] - \operatorname{sinc} [ W (n+a)] \right\}$	$j \omega \cdot \operatorname{rect} \left( { \omega \over \pi W } \right) e^{j a \omega}$	real numbers W, a $0 < W \le 1$
$\frac{1}{\pi n^2} [(-1)^n - 1]$	$\| \omega \| \!$
$\begin{cases} 0; & n \mbox{ odd} \\ \frac{2}{\pi n} ; & n \mbox{ even} \end{cases}$	$\begin{cases} j & \omega < 0 \\ 0 & \omega = 0 \\ -j & \omega > 0 \end{cases}$	Hilbert transform
$\frac{C (A + B)}{2 \pi} \cdot \operatorname{sinc} \left[ \frac{A - B}{2\pi} n \right] \cdot \operatorname{sinc} \left[ \frac{A + B}{2\pi} n \right]$		real numbers A, B complex C

[edit] 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	$a x[n] + b y[n] \!$	$a X(e^{i \omega}) + b Y(e^{i \omega}) \!$
Shift in time	$x[n - k] \!$	$X(e^{i \omega}) e^{-i \omega k} \!$	integer k
Shift in frequency (modulation)	$x[n]e^{ian} \!$	$X(e^{i (\omega-a)}) \!$	real number a
Time reversal	$x[- n] \!$	$X(e^{-i \omega}) \!$
Time conjugation	$x[n]^* \!$	$X(e^{-i \omega})^* \!$
Time reversal & conjugation	$x[-n]^* \!$	$X(e^{i \omega})^* \!$
Derivative in frequency	$\frac{n}{i} x[n] \!$	$\frac{d X(e^{i \omega})}{d \omega} \!$
Integral in frequency	$\frac{i}{n} x[n] \!$	$\int_{-\pi}^{\omega} X(e^{i \vartheta}) d \vartheta \!$
Convolve in time	$x[n] * y[n] \!$	$X(e^{i \omega}) \cdot Y(e^{i \omega}) \!$
Multiply in time	$x[n] \cdot y[n] \!$	$\frac{1}{2 \pi} X(e^{i \omega}) * Y(e^{i \omega}) \!$
Correlation	$\rho_{xy} [n] = x[-n]^* * y[n] \!$	$R_{xy} (\omega) = X(e^{i \omega})^* \cdot Y(e^{i \omega}) \!$

[edit] Symmetry Properties

The Fourier Transform can be decomposed into a real and imaginary or into even and odd.
$X(e^{i \omega}) = X_R(e^{i \omega}) + iX_I(e^{i \omega}) \!$
or
$X(e^{i \omega}) = X_E(e^{i \omega}) + X_O(e^{i \omega}) \!$

Time Domain $x[n] \!$	Frequency Domain $X(e^{i \omega}) \!$
$x^*[n]\!$	$X^*(e^{-i \omega}) \!$
$x^*[-n]\!$	$X^*(e^{i \omega}) \!$

[edit] References

Alan V. Oppenheim and Ronald W. Schafer (1999). Discrete-Time Signal Processing (2nd Edition ed.). Prentice Hall Signal Processing Series. ISBN 0-13-754920-2.
William McC. Siebert (1986). Circuits, Signals, and Systems. MIT Electrical Engineering and Computer Science Series. Cambridge, MA: MIT Press.
Boaz Porat. A Course in Digital Signal Processing. John Wiley and Sons. pp. 27–29 and 104–105. ISBN 0-471-14961-6.

Discrete-time Fourier transform

From Wikipedia, the free encyclopedia

Contents

[edit] Definition

[edit] Relationship to sampling

[edit] Periodicity

[edit] Inverse transform

[edit] Finite-length sequences

[edit] Difference between the DTFT and other Fourier transforms

[edit] Relationship to the Z-transform

[edit] Table of discrete-time Fourier transforms

[edit] Properties

[edit] Symmetry Properties

[edit] References

Views

Personal tools

Navigation

Search

Interaction

Toolbox

Languages