Discrete-Time Fourier Transform

Discrete-time Fourier transform
In mathematics, the discrete-time Fourier transform

(DTFT) is a form of Fourier analysis that is applicable to
the uniformly-spaced samples of a continuous function.
The term discrete-time refers to the fact that the transform
operates on discrete data (samples) whose interval often
has units of time. From only the samples, it produces a
function of frequency that is a periodic summation of the
continuous Fourier transform of the original continuous
function. Under certain theoretical conditions, described
by the sampling theorem, the original continuous function can be recovered perfectly from the DTFT and thus
from the original discrete samples. The DTFT itself is a
continuous function of frequency, but discrete samples of
it can be readily calculated via the discrete Fourier transform (DFT) (see Sampling the DTFT), which is by far
the most common method of modern Fourier analysis.
Fig 1. Depiction of a Fourier transform (upper left) and its periodic summation (DTFT) in the lower left corner. The lower
right corner depicts samples of the DTFT that are computed by a
discrete Fourier transform (DFT).
Both transforms are invertible. The inverse DTFT is the

original sampled data sequence. The inverse DFT is a
periodic summation of the original sequence. The fast
Fourier transform (FFT) is an algorithm for computing
one cycle of the DFT, and its inverse produces one cycle
of the inverse DFT.
and combined by addition. For suciently large fs the

k=0 term can be observed in the region [fs/2, fs/2] with
little or no distortion (aliasing) from the other terms. In
Fig.1, the extremities of the distribution in the upper left
corner are masked by aliasing in the periodic summation
(lower left).
We also note that ei2f T n is the Fourier transform of
(tnT ). Therefore, an alternative denition of DTFT
is:[note 1]
Denition
The discrete-time Fourier transform of a discrete set of

real or complex numbers: x[n], for all integers n, is a
Fourier series, which produces a periodic function of a
frequency variable. When the frequency variable, , has
normalized units of radians/sample, the periodicity is 2, The modulated Dirac comb function is a mathematical
abstraction sometimes referred to as impulse sampling.[1]
and the Fourier series is:
2 Inverse transform
The utility of this frequency domain function is rooted in
the Poisson summation formula. Let X(f) be the Fourier
transform of any function, x(t), whose samples at some
interval, T (seconds), are equal (or proportional to) the
x[n] sequence, i.e. T x(nT ) = x[n] . Then the periodic
function represented by the Fourier series is a periodic
summation of X(f). In terms of frequency f in hertz (cycles/sec):
An operation that recovers the discrete data sequence

from the DTFT function is called an inverse DTFT. For
instance, the inverse continuous Fourier transform of
both sides of Eq.3 produces the sequence in the form of
a modulated Dirac comb function:
n=
{
} def
x[n](tnT ) = F 1 X1/T (f ) =
X1/T (f )ei2f t df.
The integer k has units of cycles/sample, and 1/T is the However, noting that X/T(f) is periodic, all the necessample-rate, fs (samples/sec). So X/T(f) comprises ex- sary information is contained within any interval of length
act copies of X(f) that are shifted by multiples of fs hertz 1/T. In both Eq.1 and Eq.2, the summations over n are a
1
4 SAMPLING THE DTFT
Fourier series, with coecients x[n]. The standard formulas for the Fourier coecients are also the inverse
transforms:
Xk
x[n] = T
1
T
1
=
2
(
)
kn
k
X1/T
=
x[n] ei2 N
NT
|
{z
} n=
X1/T (f ) e
i2f nT
df
length of interval any over (integral1/T )
xN [n] ei2 N ,
kn
X2 () ein d
{z
any over (sumn length of -sequenceN )
DF T
length of interval any over (integral2)
k = 0, . . . , N 1
where xN is a periodic summation:
Periodic data
def
x[n mN ].
When the input data sequence x[n] is N-periodic, Eq.2
m=
can be computationally reduced to a discrete Fourier
The xN sequence is the inverse DFT. Thus, our sampling
transform (DFT), because:
of the DTFT causes the inverse transform to become periodic.
All the available information is contained within N
In order to evaluate one cycle of xN numerically, we resamples.
quire a nite-length x[n] sequence. For instance, a long
X1/T (f ) converges to zero everywhere except integer sequence might be truncated by a window function of
length L resulting in two cases worthy of special mention:
multiples of N1T , known as harmonic frequencies.
L N and L = IN, for some integer I (typically 6 or 8).
The DTFT is periodic, so the maximum number of For notational simplicity, consider the x[n] values below
unique harmonic amplitudes is T1 / N1T =N.
to represent the modied values.
xN [n] =
When L = IN a cycle of xN reduces to a summation of

The kernel x[n]ei2f T n is N-periodic at the
harmonic I blocks of length N. This goes by various names, such
frequencies, f = NkT . Introducing the notation N to rep- as multi-block windowing and window presum-DFT.
resent a sum over any n-sequence of length N, we can [2] [3] A good way to understand/motivate the technique is
write:
to recall that decimation of sampled data in one domain
(time or frequency) produces aliasing in the other, and
vice)versa. The xN summation is mathematically equiva(
(
)
k
k
lent
i2 N
(nmN
) to aliasing, leading to decimation in frequency, leavX1/T
=
x[n mN ] e
ing
only DTFT samples least aected by spectral leakNT
m=
N
) (
) (
) implementing an FFT
(
age. That is usually
a priority
when
k
k
lter-bank
With
Nn
=
x[n] ei2 N n =
x[n] ei2(channelizer).
1 .a conventional window
function
of
length
L,
scalloping
loss would be unacceptm=
m=
N
N
|
} windows are created using FIR lter
able.{z
So multi-block
X[k] (DFT)
design
tools. Their frequency prole is at at the highest
point
and
falls o quickly at the midpoint between the reTherefore, the DTFT diverges at the harmonic frequenmaining
DTFT
samples. The larger the value of paramcies, but at dierent frequency-dependent rates. And
eter
I
the
better
the potential performance. We note that
those rates are given by the DFT of one cycle of the x[n]
the
same
results
can be obtained by computing and decisequence. In terms of a Dirac comb function, this is repmating
an
L-length
DFT, but that is not computationally
resented by:
ecient.
(
)
1
k
X[k]
f
.
X1/T (f ) =
NT
NT
k=
|
{z
}
When L N the DFT is usually written in this more familiar form:
sequence periodic a of DTFT
Xk =
N
1
x[n] ei2 N .
kn
n=0
Sampling the DTFT
In order to take advantage of a fast Fourier transform algorithm for computing the DFT, the summation is usually
When the DTFT is continuous, a common practice is to performed over all N terms, even though N-L of them are
compute an arbitrary number of samples (N) of one cycle zeros. Therefore, the case L < N is often referred to as
of the periodic function X1/T:
zero-padding.
6.1
Alternative notation
Spectral leakage, which increases as L decreases, is detrimental to certain important performance metrics, such
as resolution of multiple frequency components and the
amount of noise measured by each DTFT sample. But
those things don't always matter, for instance when the
x[n] sequence is a noiseless sinusoid (or a constant),
shaped by a window function. Then it is a common practice to use zero-padding to graphically display and compare the detailed leakage patterns of window functions.
To illustrate that for a rectangular window, consider the
sequence:
1
x[n] = ei2 8 n ,
X(z) = n= x[n] z n , where z is a complex variable.

On the unit circle, z is constrained to values of the form
ei . Then one cycle of X(ei ), 0 2 is equivalent
to one period of the DTFT. What varies with samplerate is the width of a signals spectral distribution. When
the width exceeds 2, because of a sub-Nyquist rate, the
distribution lls the circle, and aliasing occurs. With a
DTFT in units of hertz (Eq.2), its not the bandwidth that
changes, but the periodicity of the aliases.
and L = 64.
6.1 Alternative notation

The two gures below are plots of the magnitude of two
dierent sized DFTs, as indicated in their labels. In both The notation, X(ei ) , is also often used to denote a norcases, the dominant component is at the signal frequency: malized DTFT (Eq.1), which has several desirable feaf = 1/8 = 0.125. Also visible on the right is the spectral tures:
leakage pattern of the L = 64 rectangular window. The
illusion on the left is a result of sampling the DTFT at all
1. highlights the periodicity property, and
of its zero-crossings. Rather than the DTFT of a nite2. helps distinguish between the DTFT and the unlength sequence, it gives the impression of an innitely
derlying Fourier transform of x(t); that is, X(f) (or
long sinusoidal sequence. Contributing factors to the ilX()), and
lusion are the use of a rectangular window, and the choice
of a frequency (1/8 = 8/64) with exactly 8 (an integer) cy3. emphasizes the relationship of the DTFT to the Zcles per 64 samples.
transform.
Convolution
The convolution theorem for sequences is:

x y = DTFT1 [DTFT{x} DTFT{y}] .
However, its relevance is obscured when the DTFT is expressed as its equivalent periodic summation. So the notation X() is also commonly used, as in the table below.
7 Table of discrete-time Fourier

transforms
An important special case is the circular convolution

of sequences x and y dened by xN * y where xN is a
periodic summation. The discrete-frequency nature of Some common transform pairs are shown in the table beDTFT{xN} selects only discrete values from the con- low. The following notation applies:
tinuous function DTFT{y}, which results in considerable
simplication of the inverse transform. As shown at
= 2fT is a real number representing continuous
Convolution_theorem#Functions_of_discrete_variable_sequences:
angular frequency (in radians per sample). (f is in
cycles/sec, and T is in sec/sample.) In all cases in
the table, the DTFT is 2-periodic (in ).
xN y = DTFT1 [DTFT{xN } DTFT{y}] = DFT1 [DFT{xN } DFT{yN }] .
X() designates a function dened on < <
For x and y sequences whose non-zero duration is less
.
than or equal to N, a nal simplication is:
X() designates a function dened on < ,
and zero elsewhere. Then:
1
xN y = DFT [DFT{x} DFT{y}] .
The signicance of this result is expounded at Circular
convolution and Fast convolution algorithms.
def
X2 () =
X( 2k).
k=
Relationship to the Z-transform
The bilateral Z-transform is dened by:
() is the Dirac delta function

sinc(t) is the normalized sinc function
12
12 References
rect(t) is the rectangle function

tri(t) is the triangle function
n is an integer representing the discrete-time domain
(in samples)
u[n] is the discrete-time unit step function
Alan V. Oppenheim and Ronald W. Schafer (1999).

Discrete-Time Signal Processing (2nd ed.). Prentice
Hall Signal Processing Series. ISBN 0-13-7549202.
William McC. Siebert (1986). Circuits, Signals, and
Systems. MIT Electrical Engineering and Computer
Science Series. Cambridge, MA: MIT Press.
[n] is the Kronecker delta n,
Properties
This table shows some mathematical operations in the

time domain and the corresponding eects in the frequency domain.
Boaz Porat. A Course in Digital Signal Processing.

John Wiley and Sons. pp. 2729 and 104105.
ISBN 0-471-14961-6.
is the discrete convolution of two sequences

x[n]* is the complex conjugate of x[n]
X(ei ) is the alternative notation (described above)
for X()
See also
Multidimensional transform
Zak transform
10
Notes
[1] In fact Eq.2 is often justied as follows:

{
}
{
}
F
T x(nT ) (t nT ) = F x(t) T
(t nT )
n=
{
= X(f ) F
n=
n=
}
(t nT )
(
)
k
f
T
k=
)
(
k
.
=
X f
T
= X(f )
k=
11
REFERENCES
Citations
[1] Rao, R. Signals and Systems. Prentice-Hall Of India Pvt.

Limited. ISBN 9788120338593.
[2] Gumas, Charles Constantine (July 1997). Windowpresum FFT achieves high-dynamic range, resolution.
Personal Engineering & Instrumentation News: 5864.
[3] Lyons, Richard G. (June 2008). DSP Tricks: Building a
practical spectrum analyzer. EE Times.
13
13.1
Text and image sources, contributors, and licenses

Text
Discrete-time Fourier transform Source: https://en.wikipedia.org/wiki/Discrete-time_Fourier_transform?oldid=710077436 Contributors: Michael Hardy, Ahoerstemeier, Stevenj, Furrykef, Giftlite, Dirk Gently, Discospinster, Rbj, LutzL, PAR, Cburnett, Oleg Alexandrov,
Mwilde, Btyner, Fred Bradstadt, Alejo2083, Mathbot, YurikBot, RobotE, Axfangli, Zukeeper, Oli Filth, Metacomet, Nbarth, Darth Panda,
Bob K, Ligulembot, Dicklyon, INkubusse, Goose240, Thijs!bot, Hazmat2, Frozenport, John254, Neilbartlett, Leyo, Krishnachandranvn,
Anna Lincoln, SieBot, Jojalozzo, Kanonkas, Davyzhu, Wdwd, Addbot, AndersBot, Publicly Visible, Luckas-bot, Sz-iwbot, Citation bot,
FrescoBot, Vaamarnath, RjwilmsiBot, JacobDang, GoingBatty, HiW-Bot, ZroBot, Maschen, Alexander Misel, 28bot, Sitar Physics, ClueBot NG, Jack Greenmaven, Mattgately, Winner245, HMSSolent, BattyBot, Arcandam, Jiejie9988, Mark viking, Cupitor, Upputuri92,
Monkbot and Anonymous: 75
13.2
Images
File:Fourier_transform,_Fourier_series,_DTFT,_DFT.gif Source: https://upload.wikimedia.org/wikipedia/commons/c/ca/Fourier_

transform%2C_Fourier_series%2C_DTFT%2C_DFT.gif License: CC0 Contributors: Own work Original artist: Bob K
File:No-zeropad.png Source: https://upload.wikimedia.org/wikipedia/commons/1/17/No-zeropad.png License: CC-BY-SA-3.0 Contributors: ? Original artist: ?
File:Trapezoid_signal.svg Source: https://upload.wikimedia.org/wikipedia/commons/7/7c/Trapezoid_signal.svg License: CC BYSA 3.0 Contributors: This le was derived from Trapezoid signal.png: <a href='//commons.wikimedia.org/wiki/File:Trapezoid_
signal.png' class='image'><img alt='Trapezoid signal.png' src='https://upload.wikimedia.org/wikipedia/commons/thumb/d/d2/Trapezoid_
signal.png/50px-Trapezoid_signal.png' width='50' height='20' srcset='https://upload.wikimedia.org/wikipedia/commons/thumb/d/d2/
Trapezoid_signal.png/75px-Trapezoid_signal.png 1.5x, https://upload.wikimedia.org/wikipedia/commons/thumb/d/d2/Trapezoid_signal.
png/100px-Trapezoid_signal.png 2x' data-le-width='1001' data-le-height='391' /></a>
Original artist: Trapezoid_signal.png: Alejo2083
File:Zeropad.png Source: https://upload.wikimedia.org/wikipedia/commons/5/52/Zeropad.png License: CC-BY-SA-3.0 Contributors: ?
Original artist: ?
13.3
Content license
Creative Commons Attribution-Share Alike 3.0

Discrete-Time Fourier Transform

Uploaded by

Copyright:

Available Formats

Discrete-Time Fourier Transform

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Discrete-Time Fourier Transform

Uploaded by

Copyright:

Available Formats

Discrete-time Fourier transform

In mathematics, the discrete-time Fourier transform

Both transforms are invertible. The inverse DTFT is the

and combined by addition. For suciently large fs the

The discrete-time Fourier transform of a discrete set of

An operation that recovers the discrete data sequence

X1/T (f )ei2f t df.

4 SAMPLING THE DTFT

length of interval any over (integral1/T )

any over (sumn length of -sequenceN )

length of interval any over (integral2)

where xN is a periodic summation:

When L = IN a cycle of xN reduces to a summation of

When L N the DFT is usually written in this more familiar form:

sequence periodic a of DTFT

Sampling the DTFT

X(z) = n= x[n] z n , where z is a complex variable.

6.1 Alternative notation

The convolution theorem for sequences is:

7 Table of discrete-time Fourier

An important special case is the circular convolution

Relationship to the Z-transform

The bilateral Z-transform is dened by:

() is the Dirac delta function

rect(t) is the rectangle function

Alan V. Oppenheim and Ronald W. Schafer (1999).

[n] is the Kronecker delta n,

This table shows some mathematical operations in the

Boaz Porat. A Course in Digital Signal Processing.

is the discrete convolution of two sequences

[1] In fact Eq.2 is often justied as follows:

[1] Rao, R. Signals and Systems. Prentice-Hall Of India Pvt.

Text and image sources, contributors, and licenses

File:Fourier_transform,_Fourier_series,_DTFT,_DFT.gif Source: https://upload.wikimedia.org/wikipedia/commons/c/ca/Fourier_

Creative Commons Attribution-Share Alike 3.0

You might also like