NationMaster - Encyclopedia: Discrete time Fourier transform

The discrete-time Fourier transform (or DTFT) is part of the family of Fourier transforms. It transforms a function $f [n]$ of a discrete "time" variable n where $n in mathbb{Z}$ . The DTFT produces a continuous, periodic spectrum $F (e i ω)$ . The Fourier transform, named after Joseph Fourier, is an integral transform that re-expresses a function in terms of sinusoidal basis functions, i. ... In mathematics, the continuous Fourier transform is a certain linear operator that maps functions to other functions. ... The Fourier series, named in honor of Joseph Fourier (1768-1830), is an extremely useful mathematical tool. ... In mathematics, the discrete Fourier transform (DFT), sometimes called the finite Fourier transform, is a Fourier transform widely employed in signal processing and related fields to analyze the frequencies contained in a sampled signal, solve partial differential equations, and to perform other operations such as convolutions. ... This is a list of linear transformations of functions related to the Fourier transform. ... The Fourier transform, named after Joseph Fourier, is an integral transform that re-expresses a function in terms of sinusoidal basis functions, i. ...

1 Definition
2 Periodicity of the DTFT
3 Difference between the DTFT and DFT
- 3.1 Frequency interpolation of the DTFT via the DFT
- 3.2 DTFT from the DFT by infinite zero padding
4 Difference between the DTFT and the Fourier series
5 Relationship with the Z-transform
6 Table of Discrete-time Fourier transforms
7 Properties
8 References

Definition

The DTFT of $f [n]$ is given by the following equation.

$F(e^{i omega}) = sum_{n=-infty}^{infty} f [n] ,e^{-inomega}$

We can recover f[n] via the inverse DTFT.

$f[n] =frac{1}{2 pi}int_{-pi}^{pi} F(e^{i omega}),e^{i n omega} , d omega$

Periodicity of the DTFT

The DTFT is $2π$ periodic, i.e.,

$F(e^{i omega}) qquad = F(e^{i (omega + 2pi)})$

as shown by the following proof.

$F(e^{i (omega + 2 pi)}) = sum_{n=-infty}^{infty} f[n] ,e^{-i n (omega + 2pi)} = sum_{n=-infty}^{infty} f[n] ,e^{-i n omega} e^{-i n 2pi}$

Since $e^{i 2 pi} = quad 1$ (See complex numbers), the above equals In mathematics, a complex number is an expression of the form a + bi, where a and b are real numbers, and i stands for the square root of minus one (âˆ’1), which cannot be represented by any real number. ...

$sum_{n=-infty}^{infty} f[n] ,e^{-i n omega} 1^{-n} = sum_{n=-infty}^{infty} f[n] ,e^{-i n omega} = F(e^{i omega})$

thereby proving the periodicity. Thus, we see that the discreteness in one domain leads to periodicity in the conjugate domain because of the result from complex number theory that $e^{i 2 pi} = quad 1$ . In mathematics, a complex number is an expression of the form a + bi, where a and b are real numbers, and i stands for the square root of minus one (âˆ’1), which cannot be represented by any real number. ...

Difference between the DTFT and DFT

The DTFT differs from the discrete Fourier transform (DFT) in that the latter transforms a discrete-time function $f [n]$ that is periodic. For a length $N$ finite signal $f[n] : n in {0, 1, dots, N-1 }$ , the DFT actually samples the DTFT at uniform intervals $k in { 0, 1, dots, N-1 }$ in the frequency domain. In mathematics, the discrete Fourier transform (DFT), sometimes called the finite Fourier transform, is a Fourier transform widely employed in signal processing and related fields to analyze the frequencies contained in a sampled signal, solve partial differential equations, and to perform other operations such as convolutions. ...

$F(k) = left. F(e^{i omega}) , right|_{omega = 2 pi frac{k}{N}} = left. sum_{n=0}^{N-1} f[n] ,e^{-i omega n} , right|_{omega = 2 pi frac{k}{N}} = sum_{n=0}^{N-1} f[n] ,e^{-i 2 pi frac{k n}{N}}$

Frequency interpolation of the DTFT via the DFT

A common technique to obtain more resolution in the frequency domain is to zero pad $f [n]$ . Zero padding a signal simply means that we append a finite number of zeros to the end of the signal. So, if we add $M - N$ zeros to the end of $f [n]$ so that the signal is of length $M$ , the DFT becomes the following.

$sum_{n=0}^{M-1} f[n] ,e^{-i 2 pi frac{k n}{M}} mbox{ where } k in {0, 1, dots, M - 1}$

Since the values of $f [n]$ from $N$ to $M - 1$ are zero, the above reduces to the following.

$sum_{n=0}^{N-1} f[n] ,e^{-i 2 pi frac{k n}{M}} + sum_{n=N}^{M-1} f[n] ,e^{-i 2 pi frac{k n}{M}} = sum_{n=0}^{N-1} f[n] ,e^{-i 2 pi frac{k n}{M}}$

Thus, we have obtained more resolution in the frequency domain since we have M discrete frequencies rather than N discrete frequencies.

As an example, we performed the DFT on the length 64 signal $e^{i frac{pi}{4} n}$ where $n in {0, 1, dots, 63 }$ .

DFT of the signal without zero padding.

DFT of the signal after zero padding.

The figure on the left is the plot of the magnitude of the DFT. As expected, it is an impulse at $π / 4$ . Then, we zero padded the signal with 192 zeros and took the DFT. The plot on the right shows the magnitude of this DFT. In the plot on the right, we obtain more resolution in the frequency domain from zero padding.

DTFT from the DFT by infinite zero padding

If we append an infinite number of zeros to f[n], then the DFT approaches the DTFT. This padding is equivalent to having $M rightarrow infty$ and $k rightarrow infty$ at different rates. As a result, the quantity given below approaches the continuous variable $ω$ .

$lim_{M to infty, k to infty} frac{2 pi k}{M} = omega$

and it follows that

$lim_{M to infty, k to infty} sum_{n=0}^{N-1} f[n] ,e^{-i 2 pi frac{k n}{M}} = sum_{n=0}^{N-1} f[n] ,e^{-i omega n}$

Thus, we obtain the DTFT by zero padding the signal f[n] with an infinite number of zeros.

Difference between the DTFT and the Fourier series

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 Fourier series, named in honor of Joseph Fourier (1768-1830), is an extremely useful mathematical tool. ...

Relationship with the Z-transform

The DTFT is a special case of the Z-transform. The Z-transform is defined as follows. In mathematics and signal processing, the Z-transform converts a discrete time domain signal, which is a sequence of real numbers, into a complex frequency domain representation. ...

$F(z) = sum_{n=-infty}^{infty} f[n] ,z^{-n}$

If we evaluate the Z-transform at $z = e i ω$ , then we recover the DTFT. (For this reason, the notation $F (e i ω)$ is generally preferred over the notation $F (ω)$ for representing the DTFT.) In mathematics and signal processing, the Z-transform converts a discrete time domain signal, which is a sequence of real numbers, into a complex frequency domain representation. ...

$left. F(z) right|_{z = e^{i omega}} = sum_{n=-infty}^{infty} f[n] ,e^{-inomega} = F(e^{i omega})$

Note that evaluating at $z = e i ω$ is equivalent to evaluating the Z-transform along the unit circle in the complex plane. In mathematics and signal processing, the Z-transform converts a discrete time domain signal, which is a sequence of real numbers, into a complex frequency domain representation. ... Illustration of a unit circle. ... In mathematics, the complex plane is a way of visualising the space of the complex numbers. ...

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(t) is the unit step
sinc(t) is the sinc function
$δ(t)$ is the Dirac delta function
$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: The Heaviside step function, sometimes called the unit step function and named in honor of Oliver Heaviside, is a discontinuous function whose value is zero for negative argument and one for positive argument: The function is used in the mathematics of control theory and signal processing to represent a signal... The sinc function sinc(x) from x=-8π to 8π. ... The Dirac delta function, sometimes referred to as the unit impulse function and introduced by the British theoretical physicist Paul Dirac, can usually be informally thought of as a function Î´(x) that has the value of infinity for x = 0, the value zero elsewhere. ...

$f [n]$	$F (e i n ω)$
u[n]	$frac{1}{1-e^{j omega}}$
cos [a n]	$frac{1}{2} left[ delta (omega - a) + delta (omega + a) right]$
sin [a n]	$frac{1}{2 i} left[ delta (omega - a) - delta ( omega + a) right]$
$operatorname{sinc} [pi (a + n)]$ ; generic a	$e i a ω$
$δ[n + a]$ ; integer a	$e i a ω$
$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^{j a 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^{j a omega}$
$frac{1}{pi n^2} [(-1)^n - 1]$	$\| ω \|$
$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
$overline{x} [n]$ is the complex conjugate of the function x[n]
$ρ x y [n]$ represents the correlation between x[n] and y[n].

The first column shows the function in the time domain, the second one in the frequency domain: For the computer science usage see convolution (computer science) . In mathematics and in particular, functional analysis, convolution is a mathematical operator which takes two functions f and g and produces a third function that in a sense represents the amount of overlap between f and a reversed and translated version... In mathematics, the complex conjugate of a complex number is given by changing the sign of the imaginary part. ... In probability theory and statistics, correlation, also called correlation coefficient, is a numeric measure of the strength of linear relationship between two random variables. ...

x[n]	$X (ω)$
a x[n] + b y[n]	$a X (ω) + b Y (ω)$
x[n + K]	$X (ω) e i ω k$
$x[n] e^{- i omega_0 n}$	$X (ω + ω 0)$
x[- n]	$X ( - ω)$
$overline{x} [n]$	$overline{X} (-omega)$
$overline{x} [-n]$	$overline{X} (omega)$
$frac{n}{i} x[n]$	$frac{d X(omega)}{d omega}$
$frac{i}{n} x[n]$	$int_{-pi}^{omega} X(vartheta) d vartheta$
x[n] * y[n]	$X(omega) cdot Y (omega)$
$x[n] cdot y[n]$	$frac{1}{2 pi} X(omega) * Y(omega)$
$rho_{xy} [n] = overline{x} [-n] * y[n]$	$overline{X} (omega) cdot Y (omega)$

References

Alan V. Oppenheim and Ronald W. Schafer : Discrete-Time Signal Processing, Prentice Hall Signal Processing Series, ISBN 0-13-754920-2

Boaz Porat : A Course in Digital Signal Processing, pp. 27-29, pp. 104-105, John Wiley and Sons, ISBN 0-471-14961-6

Categories: Transforms | Fourier analysis | Digital signal processing

COMMENTARY

Share your thoughts, questions and commentary here

Want to know more?
Search encyclopedia, statistics and forums:

Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms.

Contents

Definition var ACE_AR = {Site: '756743', Size: '300250'};