Fourier Theorems for the DFT
This chapter derives various
Fourier theorems for the case of the
DFT.
Included are symmetry relations, the
shift theorem,
convolution theorem,
correlation theorem,
power theorem, and theorems pertaining to interpolation
and
downsampling. Applications related to certain theorems are outlined,
including
linear time-invariant filtering,
sampling rate conversion, and
statistical signal processing.

Let

, denote an

-sample complex sequence,
i.e.,

. Then the
spectrum of

is defined by the
Discrete Fourier Transform (DFT):
The
inverse DFT (
IDFT) is defined by
In this chapter, we will omit mention of an explicit
sampling interval

, as this is most typical in the
digital signal processing
literature. It is often said that the
sampling frequency is

.
In this case, a radian frequency

is in
units of ``radians per sample.'' Elsewhere in this book,

usually means ``radians per
second.'' (Of course, there's no
difference when the
sampling rate is really

.) Another term we use
in connection with the

convention is
normalized
frequency: All normalized radian frequencies lie in the range

, and all normalized frequencies in Hz lie in the range

.
7.1 Note that physical units
of seconds and
Hertz can be reintroduced by the substitution
Notation and Terminology
If

is the
DFT of

, we say that

and

form a
transform
pair and write
Another notation we'll use is
If we need to indicate the length of the DFT explicitly, we will write

and

.
As we've already seen,
time-domain signals are consistently denoted
using
lowercase symbols such as ``

,'' while
frequency-domain
signals (
spectra), are denoted in
uppercase (``

'').
Modulo Indexing, Periodic Extension
The
DFT sinusoids

are all
periodic
having
periods which divide

. That is,

for any
integer

. Since a length
signal 
can be expressed as a
linear
combination of the
DFT sinusoids in the time domain,
it follows that the ``automatic'' definition of

beyond the
range
![$ [0,N-1]$](http://www.dsprelated.com/josimages_new/mdft/img1128.png)
is
periodic extension,
i.e.,

for every integer

.
Moreover, the DFT also repeats naturally every

samples, since
because

. (The DFT
sinusoids behave identically as functions of

and

.) Accordingly, for purposes of DFT studies, we may define
all
signals in

as being single periods from an infinitely long
periodic
signal with period

samples:
Definition (Periodic Extension): For any signal

, we define
for every integer

.
As a result of this convention, all indexing of signals and
spectra7.2 can be interpreted
modulo 
, and we may write

to emphasize this. Formally, ``

'' is defined as

with

chosen to give

in the range
![$ [0,N-1]$](http://www.dsprelated.com/josimages_new/mdft/img1128.png)
.
As an example, when indexing a
spectrum 
, we have that

which can be interpreted physically as saying that the
sampling rate
is the same frequency as
dc for discrete time signals. Periodic
extension in the time domain implies that the signal input to the DFT
is mathematically treated as being
samples of one period of a
periodic signal, with the period being exactly

seconds (

samples). The corresponding assumption in the
frequency domain is
that the
spectrum is
exactly zero between frequency samples

. It is also possible to adopt the point of view that the
time-domain signal

consists of

samples preceded and
followed by
zeros. In that case, the
spectrum would be
nonzero between spectral samples

, and the spectrum
between samples would be reconstructed by means of
bandlimited
interpolation [
72].
It will be convenient in the
Fourier theorems of §
7.4 to
make use of the following
signal operator definitions.
Operator Notation
In this book, an
operator is defined as a
signal-valued function of a signal. Thus, for the space
of length

complex sequences, an operator

is a mapping
from

to

:
An example is the
DFT operator:
The argument to an operator is always an entire signal. However, its
output may be subscripted to obtain a specific sample,
e.g.,
Some operators require one or more
parameters affecting their
definition. For example the
shift operator (defined in
§
7.2.3 below) requires a
shift amount

:
7.3
A time or frequency index, if present, will always be the last
subscript. Thus, the signal

is obtained from

by shifting it

samples.
Note that operator notation is
not standard in the field of
digital signal processing. It can be regarded as being influenced by
the field of computer science. In the
Fourier theorems below, both
operator and conventional signal-processing notations are provided. In the
author's opinion, operator notation is consistently clearer, allowing
powerful expressions to be written naturally in one line (
e.g., see
Eq.

(
7.8)), and it is much closer to how things look in
a readable computer program (such as in the
matlab language).
Flip Operator
We define the
flip operator by
 |
(7.1) |
for all sample indices

.
By
modulo indexing,

is the same as

. The

operator
reverses the order of samples

through

of a sequence, leaving
sample 0 alone, as shown in Fig.
7.1a. Thanks to modulo
indexing, it can also be viewed as ``flipping'' the sequence about the
time 0, as shown in
Fig.
7.1b. The interpretation of Fig.
7.1b is usually the one we
want, and the

operator is usually thought of as ``time reversal''
when applied to a
signal 
or ``frequency reversal'' when applied to a
spectrum 
.
figure[htbp]
Shift Operator
The
shift operator is defined by
and

denotes the entire shifted
signal. Note that
since indexing is modulo

, the shift is
circular (or
``cyclic''). However, we normally use it to represent
time
delay by

samples. We often use the shift operator in
conjunction with
zero padding (appending zeros to the signal

, §
7.2.7) in order to avoid the ``wrap-around''
associated with a circular shift.
Figure 7.2:
Successive one-sample shifts of a
sampled periodic sawtooth waveform having first period
.
![\includegraphics[width=\twidth]{eps/shift}](http://www.dsprelated.com/josimages_new/mdft/img1153.png) |
Figure
7.2 illustrates successive one-sample delays of a
periodic signal
having first period given by
![$ [0,1,2,3,4]$](http://www.dsprelated.com/josimages_new/mdft/img41.png)
.
-
(an impulse delayed one sample).
-
(a circular shift example).
-
(another circular shift example).
Convolution
The
convolution of two
signals 
and

in

may be
denoted ``

'' and defined by
Note that this is
circular convolution (or ``cyclic''
convolution).
7.4 The importance of convolution in
linear systems theory is discussed in §
8.3.
Cyclic convolution can be expressed in terms of previously defined
operators as
where

and

. This expression suggests
graphical convolution, discussed below in §
7.2.4.
Convolution (cyclic or acyclic) is
commutative,
i.e.,
Proof:
In the first step we made the change of summation variable

, and in the second step, we made use of the fact
that any sum over all

terms is equivalent to a sum from 0 to

.
In a convolution of two
signals

, where both

and

are signals of length

(real or complex), we may interpret either

or

as a
filter that operates on the other signal
which is in turn interpreted as the filter's ``input signal''.
7.5 Let

denote a length

signal that is interpreted
as a filter. Then given any input signal

, the filter output
signal

may be defined as the
cyclic convolution of

and

:
Because the convolution is cyclic, with

and

chosen from the
set of (periodically extended) vectors of length

,

is most
precisely viewed as the
impulse-train-response of the
associated filter at time

. Specifically, the impulse-train
response

is the response of the filter to the
impulse-train signal
![$ \delta\isdeftext [1,0,\ldots,0]\in{\bf R}^N$](http://www.dsprelated.com/josimages_new/mdft/img1169.png)
,
which, by
periodic extension, is equal to
Thus,

is the
period of the impulse-train in samples--there
is an ``impulse'' (a `

') every

samples. Neglecting the assumed
periodic extension of all signals in

, we may refer to

more simply as the
impulse signal, and

as the
impulse
response (as opposed to impulse-
train response). In contrast,
for the
DTFT (§
B.1), in which the discrete-time axis is
infinitely long, the impulse signal

is defined as
and no periodic extension arises.
As discussed below (§
7.2.7), one may embed
acyclic
convolution within a larger cyclic convolution. In this way,
real-world systems may be simulated using fast
DFT convolutions (see
Appendix
A for more on fast convolution algorithms).
Note that only linear, time-invariant (
LTI) filters can be completely
represented by their impulse response (the filter output in response
to an impulse at time 0). The
convolution representation of LTI
digital filters is fully discussed in Book II [
68] of the
music signal processing book series (in which this is Book I).
Convolution Example 1: Smoothing a Rectangular Pulse
Figure 7.3:
Illustration of the convolution of a rectangular pulse
and the impulse response
of an ``averaging filter''
(
).
Filter output signal  .
|
Figure
7.3 illustrates convolution of
with
to get
![$\displaystyle y = x\circledast h = \left[0,0,0,0,\frac{1}{3},\frac{2}{3},1,1,1,1,\frac{2}{3},\frac{1}{3},0,0\right] \protect$](http://www.dsprelated.com/josimages_new/mdft/img1178.png) |
(7.2) |
as graphed in Fig.
7.3(c).
In this case,

can be viewed as a ``moving three-point average''
filter. Note how the corners of the rectangular pulse are ``smoothed''
by the three-point filter. Also note that the pulse is smeared to the
``right'' (forward in time) because the filter impulse response starts
at time zero. Such a filter is said to be
causal (see
[
68] for details). By shifting the impulse response left one
sample to get
(in which case

), we obtain a noncausal filter

which is
symmetric about time zero so that the input signal is smoothed ``in
place'' with no added delay (imagine Fig.
7.3(c) shifted left
one sample, in which case the input pulse edges align with the
midpoint of the rise and fall in the output signal).
Figure 7.4:
Illustration of the convolution of two rectangular pulses with a truncated
exponential impulse response.
Filter output signal  .
|
In this example, the input signal is a sequence of two
rectangular pulses, creating a piecewise constant function, depicted
in Fig.
7.4(a). The filter impulse response, shown in
Fig.
7.4(b), is a truncated
exponential.
7.6
In this example,

is again a
causal smoothing-filter impulse
response, and we could call it a ``moving weighted average'', in which
the weighting is exponential into the past. The discontinuous steps
in the input become exponential ``asymptotes'' in the output which are
approached exponentially. The overall appearance of the output signal
resembles what is called an
attack, decay, release, and sustain
envelope, or
ADSR envelope for short. In a practical ADSR
envelope, the
time-constants for attack, decay, and release may be set
independently. In this example, there is only one time constant, that
of

. The two constant levels in the input signal may be called the
attack level and the
sustain level, respectively. Thus,
the envelope approaches the attack level at the attack rate (where the
``rate'' may be defined as the reciprocal of the time constant), it
next approaches the sustain level at the ``decay rate'', and finally,
it approaches zero at the ``release rate''. These envelope parameters
are commonly used in analog synthesizers and their digital
descendants, so-called
virtual analog synthesizers. Such an
ADSR envelope is typically used to multiply the output of a waveform
oscillator such as a sawtooth or pulse-train oscillator. For more on
virtual analog synthesis, see, for example,
[
78,
77].
Figure 7.5:
Illustration of convolution of
and ``matched filter''
(
).
![\includegraphics[width=2.5in]{eps/conv}](http://www.dsprelated.com/josimages_new/mdft/img1185.png) |
Figure
7.5 illustrates convolution of
to get
![$\displaystyle y\circledast h = [4,3,2,1,0,1,2,3]. \protect$](http://www.dsprelated.com/josimages_new/mdft/img1187.png) |
(7.3) |
For example,

could be a ``rectangularly windowed
signal, zero-padded by
a factor of 2,'' where the signal happened to be
dc (all

s).
For the
convolution, we need
which is the same as

. When

, we say that

is a
matched filter for

.
7.7 In this case,

is matched to look for a
``dc component,'' and also zero-padded by a factor of

. The
zero-padding serves to simulate acyclic convolution using
circular
convolution. Note from Eq.

(
7.3) that the maximum is obtained
in the convolution output at time 0. This peak (the largest
possible if all input signals are limited to
![$ [-1,1]$](http://www.dsprelated.com/josimages_new/mdft/img1190.png)
in magnitude),
indicates the matched filter has ``found'' the dc signal starting at
time 0. This peak would persist in the presence of some amount of
noise and/or
interference from other signals. Thus, matched filtering
is useful for detecting known signals in the presence of
noise and/or
interference [
34].
As mentioned above,
cyclic convolution can be written as
where

and

. It is instructive to interpret this
expression
graphically, as depicted in Fig.
7.5 above. The
convolution result at time

is the
inner product of

and

, or

. For the next time instant,

, we shift

one sample to the right and repeat the
inner product operation to obtain

,
and so on. To capture the cyclic nature of the convolution,

and

can be imagined plotted on a
cylinder.
Thus, Fig.
7.5 shows the cylinder after being ``cut'' along the
vertical line between

and

and ``unrolled'' to lay flat.
Polynomial Multiplication
Note that when you multiply two polynomials together, their
coefficients are
convolved. To see this, let

denote the

th-order polynomial
with coefficients

, and let

denote the

th-order polynomial
with coefficients

. Then we have [
1]
Denoting

by
we have that the

th coefficient can be expressed as
where

and

are doubly infinite sequences, defined as
zero for

and

, respectively.
Since decimal numbers are implicitly just polynomials in the powers of 10,
e.g.,
it follows that
multiplying two numbers convolves their digits. The
only twist is that, unlike normal
polynomial multiplication, we have
carries. That is, when a
convolution result (output digit)
exceeds 10, we subtract
10 from the result and add 1 to the digit in the next higher place.
Correlation
The
correlation operator for two
signals 
and

in

is defined as
We may interpret the correlation operator as
which is

times
the
coefficient of projection onto

of
advanced by

samples (shifted circularly to the
left by

samples). The
time shift

is called the
correlation lag, and

is called a
lagged product. Applications of correlation
are discussed in §
8.4.
Stretch Operator
Unlike all previous operators, the

operator maps
a length
signal to a length

signal, where

and

are integers.
We use ``

'' instead of ``

'' as the time index to underscore this fact.
Figure:
Illustration of
.
![\includegraphics[width=4in]{eps/stretch}](http://www.dsprelated.com/josimages_new/mdft/img1216.png) |
A
stretch by factor 
is defined by
Thus, to stretch a signal by the factor

, insert

zeros between each
pair of samples. An example of a stretch by factor three is shown in Fig.
7.6.
The example is
The stretch operator is used to describe and analyze
upsampling,
that is, increasing the
sampling rate by an integer factor.
A stretch by

followed by lowpass
filtering to the frequency band

implements
ideal bandlimited interpolation
(introduced in Appendix
D).
Zero Padding
Zero padding consists of extending a
signal (or
spectrum)
with zeros. It maps a length

signal to a length

signal, but

need not divide

.
Definition:
![$\displaystyle \hbox{\sc ZeroPad}_{M,m}(x) \isdef \left\{\begin{array}{ll} x(m),...
...ert m\vert < N/2 \\ [5pt] 0, & \mbox{otherwise} \\ \end{array} \right. \protect$](http://www.dsprelated.com/josimages_new/mdft/img1223.png) |
(7.4) |
where

, with

for

odd,
and

for

even.
For example,
In this example, the first sample corresponds to time 0, and five
zeros have been inserted between the samples corresponding to times

and

.
Figure
7.7 illustrates zero padding from length

out to length

. Note that

and

could be replaced by

and

in the
figure caption.
Figure 7.7:
Illustration of zero padding:
a) Original signal (or spectrum)
plotted over the
domain
where
(i.e., as the samples would
normally be held in a computer array).
b)
.
c) The same signal
plotted over the domain
which
is more natural for interpreting negative times (frequencies).
d)
plotted over the zero-centered domain.
![\includegraphics[width=\twidth]{eps/zpad}](http://www.dsprelated.com/josimages_new/mdft/img1232.png) |
Note that we have unified the time-domain and
frequency-domain
definitions of zero-padding by interpreting the original time axis
![$ [0,1,\dots,N-1]$](http://www.dsprelated.com/josimages_new/mdft/img1233.png)
as indexing positive-time samples from 0 to

(for

even), and negative times in the interval
![$ n\in[N-N/2+1,N-1]\equiv[-N/2+1,-1]$](http://www.dsprelated.com/josimages_new/mdft/img1235.png)
.
7.8 Furthermore, we require

when

is even, while odd

requires no such
restriction. In practice, we often prefer to interpret time-domain
samples as extending from 0 to

,
i.e., with no negative-time
samples. For this case, we define ``
causal zero padding'' as
described below.
A signal

may be defined as
causal when

for all ``negative-time'' samples (
e.g., for

when

is even). Thus, the signal
![$ x=[1,2,3,0,0]\in{\bf R}^5$](http://www.dsprelated.com/josimages_new/mdft/img1239.png)
is causal while
![$ x=[1,2,3,4,0]$](http://www.dsprelated.com/josimages_new/mdft/img1240.png)
is not.
For
causal signals,
zero-padding is equivalent to simply
appending zeros to the original signal. For example,
Therefore, when we simply append zeros to the end of signal, we call it
causal zero padding.
In practice, a
signal

is often an

-sample
frame of
data taken from some longer signal, and its true starting time can be
anything. In such cases, it is common to treat the start-time of the
frame as zero, with no negative-time samples. In other words,

represents an

-sample signal-segment that is translated in time to
start at time 0. In this case (no negative-time samples in the
frame), it is proper to
zero-pad by simply appending zeros at the end
of the frame. Thus, we define
e.g.,
Causal zero-padding should not be used on a
spectrum of a real signal
because, as we will see in §
7.4.3 below, the
magnitude
spectrum of every real signal is symmetric about frequency zero.
For the same reason, we cannot simply append zeros in the time domain
when the signal frame is considered to include negative-time samples,
as in ``zero-centered
FFT processing'' (discussed in Book IV
[
70]). Nevertheless, in practice, appending zeros is perhaps
the most common form of zero-padding. It is implemented
automatically, for example, by the
matlab function
fft(x,N) when the FFT size
N exceeds the length of the
signal vector
x.
In summary, we have defined two types of zero-padding that arise in
practice, which we may term ``causal'' and ``zero-centered'' (or
``
zero-phase'', or even ``
periodic''). The zero-centered case is the
more natural with respect to the
mathematics of the DFT, so it is
taken as the ``official'' definition of Z
EROP
AD(). In both cases,
however, when properly used, we will have the basic
Fourier theorem
(§
7.4.12 below) stating that
zero-padding in the time domain
corresponds to ideal bandlimited interpolation in the frequency
domain, and vice versa.
Zero padding in the time domain is used extensively in practice to
compute heavily
interpolated spectra by taking the
DFT of the
zero-padded
signal. Such spectral interpolation is ideal when the
original signal is
time limited (nonzero only over some finite
duration spanned by the orignal samples).
Note that the
time-limited assumption directly contradicts our
usual assumption of
periodic extension. As mentioned in
§
6.7, the interpolation of a
periodic signal's
spectrum
from its
harmonics is always zero; that is, there is no spectral
energy, in principle, between the
harmonics of a
periodic signal, and
a periodic signal cannot be time-limited unless it is the zero signal.
On the other hand, the interpolation of a time-limited signal's
spectrum is nonzero almost everywhere between the original spectral
samples. Thus, zero-padding is often used when analyzing data from a
non-periodic signal in blocks, and each block, or
frame, is treated as a finite-duration signal which can be
zero-padded on either side with any number of zeros. In summary, the
use of zero-padding corresponds to the
time-limited assumption
for the data frame, and more zero-padding yields denser interpolation
of the frequency samples around the unit circle.
Sometimes people will say that zero-padding in the time domain yields
higher spectral
resolution in the
frequency domain. However,
signal processing practitioners should not say that, because
``resolution'' in signal processing refers to the ability to
``resolve'' closely spaced features in a
spectrum analysis (see Book
IV [
70] for details). The usual way to increase
spectral
resolution is to take a longer DFT
without zero padding--
i.e.,
look at more data. In the field of
graphics, the term
resolution refers to pixel density, so the common terminology
confusion is reasonable. However, remember that in signal processing,
zero-padding in one domain corresponds to a higher
interpolation-density in the other domain--not a higher resolution.
Ideal Spectral Interpolation
Using
Fourier theorems, we will be able to show (§
7.4.12) that
zero padding in the time domain gives
exact bandlimited interpolation in
the frequency domain.
7.9In other words, for truly time-limited
signals 
,
taking the
DFT of the entire nonzero portion of

extended by zeros
yields
exact interpolation of the complex
spectrum--not an
approximation (ignoring computational round-off error in the DFT
itself). Because the
fast Fourier transform (
FFT) is so efficient,
zero-padding followed by an FFT is a highly practical method for
interpolating
spectra of finite-duration signals, and is used
extensively in practice.
Before we can interpolate a
spectrum, we must be clear on what a
``
spectrum'' really is. As discussed in Chapter
6, the
spectrum of a signal

at frequency

is
defined as a
complex number 
computed using the
inner
product
That is,

is the unnormalized
coefficient of projection of

onto the
sinusoid 
at frequency

. When

, for

, we obtain the
special set of spectral samples known as the DFT. For other values of

, we obtain spectral points in between the DFT samples.
Interpolating DFT samples should give the same result. It is
straightforward to show that this ideal form of interpolation is what
we call
bandlimited interpolation, as discussed further in
Appendix
D and in Book IV [
70] of this series.
Interpolation Operator
The
interpolation operator

interpolates a
signal
by an integer factor

using
bandlimited interpolation. For
frequency-domain signals

,

, we may
write spectral interpolation as follows:
Since

is initially only defined over
the
roots of unity in the

plane, while

is defined
over

roots of unity, we define

for

by
ideal bandlimited interpolation (specifically
time-limited
spectral interpolation in this case).
For time-domain signals

, exact interpolation is similarly
bandlimited interpolation, as derived in Appendix
D.
Repeat Operator
Like the

and

operators, the

operator maps a length
signal to a length

signal:
Definition: The
repeat
times operator is defined for any

by
where

, and indexing of

is modulo

(
periodic extension).
Thus, the

operator simply repeats
its input signal

times.
7.10 An example of

is shown in
Fig.
7.8. The example is
Figure:
Illustration of
.
![\includegraphics[width=\twidth]{eps/repeat}](http://www.dsprelated.com/josimages_new/mdft/img1261.png) |
A
frequency-domain example is shown in Fig.
7.9.
Figure
7.9a shows the original
spectrum 
, Fig.
7.9b
shows the same
spectrum plotted over the unit circle in the

plane,
and Fig.
7.9c shows

. The

point (
dc) is on
the right-rear face of the enclosing box. Note that when viewed as
centered about

,

is a somewhat ``triangularly shaped''
spectrum. We see three copies of this shape in

.
Figure:
Illustration of
.
a) Conventional plot of
.
b) Plot of
over the unit circle in the
plane.
c)
.
![\includegraphics[width=4in]{eps/repeat3d}](http://www.dsprelated.com/josimages_new/mdft/img1263.png) |
The repeat operator is used to state the
Fourier theorem
where

is defined in §
7.2.6. That is, when you
stretch a signal by the factor

(inserting zeros between the
original samples), its spectrum is repeated

times around the unit
circle. The simple proof is given on page
![[*]](../icons/crossref.png)
.
Downsampling Operator
Downsampling by 
(also called
decimation by

) is defined
for

as taking every

th sample, starting with sample zero:
The

operator maps a length
signal down to a length

signal. It is the inverse of the

operator (but not vice
versa),
i.e.,
The stretch and downsampling operations do not commute because they are
linear
time-varying operators. They can be modeled using
time-varying
switches controlled by the sample index

.
Figure:
Illustration of
.
![\includegraphics[width=4in]{eps/downsamplex}](http://www.dsprelated.com/josimages_new/mdft/img1271.png) |
The following example of

is illustrated in Fig.
7.10:
Note that the term ``downsampling'' may also refer to the more
elaborate process of
sampling-rate conversion to a lower
sampling rate, in which a signal's
sampling rate is lowered by
resampling
using
bandlimited interpolation. To distinguish these cases, we can call
this
bandlimited downsampling, because a lowpass-
filter is
needed, in general, prior to downsampling so that
aliasing is
avoided. This topic is address in Appendix
D. Early
sampling-rate converters were in fact implemented using the

operation, followed by an appropriate
lowpass filter,
followed by

, in order to implement a sampling-rate
conversion by the factor

.
Alias Operator
Aliasing occurs when a
signal is
undersampled. If the signal
sampling rate 
is too low, we get
frequency-domain
aliasing.
The topic of aliasing normally arises in the context of
sampling a continuous-time signal. The
sampling theorem
(Appendix
D) says that we will have no aliasing due to sampling
as long as the sampling rate is higher than twice the highest
frequency present in the signal being sampled.
In this chapter, we are considering only discrete-time signals, in
order to keep the math as simple as possible. Aliasing in this
context occurs when a discrete-time signal is
downsampled to reduce its
sampling rate. You can think of continuous-time sampling as the
limiting case for which the starting sampling rate is infinity.
An example of aliasing is shown in Fig.
7.11. In the figure,
the high-frequency
sinusoid is indistinguishable from the
lower-frequency
sinusoid due to aliasing. We say the higher frequency
aliases to the lower frequency.
Figure 7.11:
Example of
frequency-domain aliasing due to undersampling in the time domain.
![\includegraphics[scale=0.5]{eps/aliasing}](http://www.dsprelated.com/josimages_new/mdft/img1275.png) |
Undersampling in the frequency domain gives rise to
time-domain
aliasing. If time or frequency is not specified, the term
``aliasing'' normally means frequency-domain aliasing (due to
undersampling in the time domain).
The
aliasing operator for

-sample signals

is defined by
Like the

operator, the

operator maps a
length

signal down to a length

signal. A way to think of
it is to partition the original

samples into

blocks of length

, with the first block extending from sample 0 to sample

,
the second block from

to

, etc. Then just add up the blocks.
This process is called
aliasing. If the original signal

is
a time signal, it is called
time-domain aliasing; if it is a
spectrum, we call it
frequency-domain aliasing, or just
aliasing. Note that aliasing is
not invertible in general.
Once the blocks are added together, it is usually not possible to
recover the original blocks.
Example:
The alias operator is used to state the
Fourier theorem (§
7.4.11)
That is, when you downsample a signal by the factor

, its
spectrum is
aliased by the factor

.
Figure:
Illustration of aliasing in
the frequency domain.
a)
from Fig.7.9c.
b) First half of the original unit circle (0 to
) wrapped around the
new, smaller unit circle (which is magnified to the original size).
c) Second half (
to
), also wrapped around the new unit circle.
d) Overlay of components to be summed.
e) Sum of components (the aliased spectrum).
f) Both sum and overlay.
![\includegraphics[width=4.5in]{eps/aliasingfd}](http://www.dsprelated.com/josimages_new/mdft/img1282.png) |
Figure
7.12 shows the result of

applied to

from Figure
7.9c. Imagine the spectrum of
Fig.
7.12a as being plotted on a piece of paper rolled
to form a cylinder, with the edges of the paper meeting at

(upper
right corner of Fig.
7.12a). Then the

operation can be
simulated by rerolling the cylinder of paper to cut its circumference in
half. That is, reroll it so that at every point,
two sheets of paper
are in contact at all points on the new, narrower cylinder. Now, simply
add the values on the two overlapping sheets together, and you have the

of the original spectrum on the unit circle. To alias by

,
we would shrink the cylinder further until the paper edges again line up,
giving three layers of paper in the cylinder, and so on.
Figure
7.12b shows what is plotted on the first circular wrap of the
cylinder of paper, and Fig.
7.12c shows what is on the second wrap.
These are overlaid in Fig.
7.12d and added together in
Fig.
7.12e. Finally, Figure
7.12f shows both the addition
and the overlay of the two components. We say that the second component
(Fig.
7.12c) ``aliases'' to new frequency components, while the
first component (Fig.
7.12b) is considered to be at its original
frequencies. If the unit circle of Fig.
7.12a covers frequencies
0 to

, all other unit circles (Fig.
7.12b-c) cover
frequencies 0 to

.
In general, aliasing by the factor

corresponds to a
sampling-rate reduction by the factor

. To prevent aliasing
when reducing the sampling rate, an
anti-aliasing lowpass
filter is generally used. The
lowpass filter attenuates all signal
components at frequencies outside the interval
![$ [-f_s/(2K),f_s/(2K)]$](http://www.dsprelated.com/josimages_new/mdft/img1285.png)
so that all frequency components which would alias are first removed.
Conceptually, in the frequency domain, the unit circle is reduced by

to a unit circle
half the original size, where the two halves are summed. The inverse
of aliasing is then ``repeating'' which should be understood as
increasing the unit circle circumference using ``
periodic
extension'' to generate ``more spectrum'' for the larger unit circle.
In the time domain, on the other hand,
downsampling is the inverse of
the
stretch operator. We may interchange ``time'' and ``frequency''
and repeat these remarks. All of these relationships are precise only
for
integer stretch/downsampling/aliasing/repeat factors; in
continuous time and frequency, the restriction to integer factors is
removed, and we obtain the (simpler)
scaling theorem (proved
in §
C.2).
Even and Odd Functions
Some of the
Fourier theorems can be succinctly expressed in terms of even
and odd symmetries.
Definition: A function

is said to be
even if

.
An even function is also
symmetric, but the
term symmetric applies also to functions symmetric about a point other
than 0.
Definition: A function

is said to be
odd if

.
An odd function is also called
antisymmetric.
Note that every finite odd function

must satisfy

.
7.11 Moreover, for any

with

even, we also have

since

; that is,

and

index
the same point when

is even.
Theorem: Every function

can be decomposed into a sum of its even part

and odd part

, where
Proof: In the above definitions,

is even and

is odd by construction.
Summing, we have
Theorem: The product of even functions is even, the product of odd functions
is even, and the product of an even times an odd function is odd.
Proof: Readily shown.
Since even times even is even, odd times odd is even, and even times odd is
odd, we can think of even as

and odd as

:
Example:

,

, is an
even signal since

.
Example:

is an
odd signal since

.
Example:

is an
odd signal (even times odd).
Example:

is an
even signal (odd times odd).
Theorem: The sum of all the samples of an odd signal

in

is zero.
Proof: This is readily shown by writing the sum as
![$ x_o(0) + [x_o(1) + x_o(-1)]
+ \cdots + x(N/2)$](http://www.dsprelated.com/josimages_new/mdft/img1309.png)
, where the last term only occurs when

is even. Each
term so written is zero for an odd signal

.
Example: For all
DFT sinusoidal frequencies

,
More generally,
for
any even signal

and odd signal

in

. In
terms of
inner products (§
5.9), we may say that the even part
of every real signal is
orthogonal to its odd part:
Fourier Theorems
In this section the main Fourier theorems are stated and proved. It
is no small matter how simple these theorems are in the
DFT case
relative to the other three cases (
DTFT,
Fourier transform, and
Fourier series, as defined in Appendix
B). When infinite
summations or integrals are involved, the conditions for the existence
of the Fourier transform can be quite difficult to characterize
mathematically. Mathematicians have expended a considerable effort on
such questions. By focusing primarily on the DFT case, we are able to
study the essential concepts conveyed by the Fourier theorems without
getting involved with mathematical difficulties.
Linearity
Theorem: For any

and

, the
DFT satisfies
where

and

, as always in this book.
Thus, the DFT is a
linear operator.
Proof:
Conjugation and Reversal
Theorem: For any

,
Proof:
Theorem: For any

,
Proof: Making the change of summation variable

, we get
Theorem: For any

,
Proof:
Corollary:
For any

,
Proof: Picking up the previous proof at the third formula, remembering that

is real,
when

is real.
Thus,
conjugation in the
frequency domain corresponds to
reversal in the time domain.
Another way to say it is that
negating spectral phase flips the signal around backwards in
time.
Corollary:
For any

,
Proof: This follows from the previous two cases.
Definition: The property

is called
Hermitian symmetry
or ``conjugate symmetry.'' If

, it may be called
skew-Hermitian.
Another way to state the preceding corollary is
Symmetry
In the previous section, we found

when

is
real. This fact is of high practical importance. It says that the
spectrum of every real
signal is
Hermitian.
Due to this symmetry, we may discard all
negative-frequency spectral
samples of a real signal and regenerate them later if needed from the
positive-frequency samples. Also, spectral plots of real signals are
normally displayed only for positive frequencies;
e.g.,
spectra of
sampled signals are normally plotted over the range 0 Hz to

Hz. On the other hand, the
spectrum of a
complex signal must
be shown, in general, from

to

(or from 0 to

),
since the positive and negative frequency components of a complex
signal are independent.
Recall from §
7.3 that a signal

is said to be
even if

, and
odd if

. Below
are are
Fourier theorems pertaining to even and odd signals and/or
spectra.
Theorem: If

, then
re

is
even and
im

is
odd.
Proof: This follows immediately from the conjugate symmetry of

for real signals

.
Theorem: If

,

is
even and

is
odd.
Proof: This follows immediately from the conjugate symmetry of

expressed
in polar form

.
The conjugate symmetry of spectra of real signals is perhaps the most
important symmetry theorem. However, there are a couple more we can readily
show:
Theorem: An even signal has an even transform:
Proof:
Express

in terms of its real and imaginary parts by

. Note that for a complex signal

to be even, both its real and
imaginary parts must be even. Then
Let
even

denote a function that is even in

, such as

, and let
odd

denote a function that is odd in

, such as

, Similarly, let
even

denote a
function of

and

that is even in both

and

, such as

, and
odd

mean odd in both

and

.
Then appropriately labeling each term in the last formula above gives
Theorem: A real even signal has a real even transform:
 |
(7.6) |
Proof: This follows immediately from setting

in the preceding
proof. From Eq.

(
7.5), we are left with
Thus, the
DFT of a real and
even function reduces to a type of
cosine transform,
7.12
Instead of adapting the previous proof, we can show it directly:
Definition: A signal with a real
spectrum (such as any real, even signal)
is often called a
zero phase signal. However, note that when
the spectrum goes
negative (which it can), the phase is really

, not 0. When a real spectrum is positive at
dc (
i.e.,

), it is then truly zero-phase over at least some band
containing dc (up to the first zero-crossing in frequency). When the
phase switches between 0 and

at the zero-crossings of the
(real) spectrum, the spectrum oscillates between being zero phase and
``constant phase''. We can say that all real spectra are
piecewise constant-phase spectra, where the two constant values
are 0 and

(or

, which is the same phase as

). In
practice, such zero-crossings typically occur at low magnitude, such
as in the ``
side-lobes'' of the
DTFT of a ``zero-centered symmetric
window'' used for
spectrum analysis (see Chapter
8 and Book IV
[
70]).
Shift Theorem
Theorem: For any

and any integer

,
Proof:
The shift theorem is often expressed in shorthand as
The shift theorem says that a
delay in the time domain corresponds to
a
linear phase term in the
frequency domain. More specifically, a
delay of

samples in the time waveform corresponds to the
linear
phase term

multiplying the
spectrum, where

.
7.13Note that spectral magnitude
is unaffected by a linear phase term. That is,

.
Linear Phase Terms
The reason

is called a
linear phase term is
that its phase is a linear function of frequency:
Thus, the
slope of the phase, viewed as a linear function of
radian-frequency

, is

. In general, the
time
delay in samples equals
minus the slope of the linear phase
term. If we express the original
spectrum in polar form as
where

and

are the magnitude and phase of

, respectively
(both real), we can see that a linear phase term only modifies the
spectral
phase 
:
where

. A positive time delay (waveform shift to
the right) adds a
negatively sloped linear phase to the original
spectral phase. A negative time delay (waveform shift to the left) adds a
positively sloped linear phase to the original spectral phase. If we
seem to be belaboring this relationship, it is because it is one of the
most useful in practice.
In practice, a
signal may be said to be
linear phase
when its phase is of the form
where

is any real constant (usually an integer), and

is an
indicator function which takes on the
values 0 or

over the points

,

.
An important class of examples is when the signal is regarded as a
filter impulse response.
7.14 What all such
signals have in common is that they are
symmetric about the time

in the time domain
(as we will show on the next page). Thus, the term ``linear phase
signal'' often really means ``a signal whose phase is linear between

discontinuities.''
A
zero-phase signal is thus a
linear-phase signal for which the
phase-slope

is zero. As mentioned above (in
§
7.4.3), it would be more precise to say ``0-or-

-phase
signal'' instead of ``zero-phase signal''. Another better term is
``zero-centered signal'', since every real (even)
spectrum corresponds
to an even (real) signal. Of course, a zero-centered symmetric signal
is simply an
even signal, by definition. Thus, a ``zero-phase
signal'' is more precisely termed an ``even signal''.
In practical
spectrum analysis, we most often use the
Fast
Fourier Transform7.15 (FFT) together with a
window function

. As discussed
further in Chapter
8, windows are normally positive (

),
symmetric about their midpoint, and look pretty much like a ``
bell
curve.'' A window multiplies the
signal 
being analyzed to form a
windowed signal

, or

, which
is then analyzed using an FFT. The window serves to
taper the
data segment gracefully to zero, thus eliminating spectral
distortions
due to suddenly cutting off the signal in time. Windowing is thus
appropriate when

is a short section of a longer signal (not a
period or whole number of periods from a
periodic signal).
Theorem: Real symmetric FFT windows are
linear phase.
Proof: Let

denote the window samples for

.
Since the window is symmetric, we have

for all

.
When

is odd, there is a sample at the midpoint at time

. The midpoint can be translated to the time origin to
create an even signal. As established on page
![[*]](../icons/crossref.png)
,
the
DFT of a real and even signal is real and even. By the shift
theorem, the DFT of the original symmetric window is a real, even
spectrum multiplied by a
linear phase term, yielding a
spectrum
having a phase that is linear in frequency with possible
discontinuities of

radians. Thus, all odd-length real
symmetric signals are ``linear phase'', including FFT windows.
When

is even, the window midpoint at time

lands
half-way between samples, so we cannot simply translate the window to
zero-centered form. However, we can still factor the window
spectrum

into the product of a linear phase term
![$ \exp[-\omega_k(M-1)/2]$](http://www.dsprelated.com/josimages_new/mdft/img1391.png)
and a real spectrum (verify this as an
exercise), which satisfies the definition of a linear phase signal.
Theorem: For any

,
Proof:
This is perhaps the most important single
Fourier theorem of all. It
is the basis of a large number of
FFT applications. Since an FFT
provides a
fast Fourier transform, it also provides
fast
convolution, thanks to the convolution theorem. It turns out that
using an FFT to perform convolution is really more efficient in
practice only for reasonably long convolutions, such as

. For
much longer convolutions, the savings become enormous compared with
``direct'' convolution. This happens because direct convolution
requires on the order of

operations (multiplications and
additions), while FFT-based convolution requires on the order of

operations, where

denotes the logarithm-base-2 of

(see §
A.1.2 for an explanation).
The simple
matlab example in Fig.
7.13 illustrates how much faster
convolution can be performed using an FFT.
7.16 We see that
for a length

convolution, the
fft function is
approximately 300 times faster in Octave, and 30 times faster in
Matlab. (The
conv routine is much faster in Matlab, even
though it is a built-in function in both cases.)
Figure 7.13:
Matlab/Octave program for comparing the
speed of direct convolution with that of FFT convolution.
N = 1024; % FFT much faster at this length
t = 0:N-1; % [0,1,2,...,N-1]
h = exp(-t); % filter impulse reponse
H = fft(h); % filter frequency response
x = ones(1,N); % input = dc (any signal will do)
Nrep = 100; % number of trials to average
t0 = clock; % latch the current time
for i=1:Nrep, y = conv(x,h); end % Direct convolution
t1 = etime(clock,t0)*1000; % elapsed time in msec
t0 = clock;
for i=1:Nrep, y = ifft(fft(x) .* H); end % FFT convolution
t2 = etime(clock,t0)*1000;
disp(sprintf([...
'Average direct-convolution time = %0.2f msec\n',...
'Average FFT-convolution time = %0.2f msec\n',...
'Ratio = %0.2f (Direct/FFT)'],...
t1/Nrep,t2/Nrep,t1/t2));
% =================== EXAMPLE RESULTS ===================
Octave:
Average direct-convolution time = 69.49 msec
Average FFT-convolution time = 0.23 msec
Ratio = 296.40 (Direct/FFT)
Matlab:
Average direct-convolution time = 15.73 msec
Average FFT-convolution time = 0.50 msec
Ratio = 31.46 (Direct/FFT)
|
A similar program produced the results for different FFT lengths shown
in Table
7.1.
7.17 In this software environment, the
fft function
is faster starting with length

, and it is never significantly
slower at short lengths, where ``calling overhead'' dominates.
Table 7.1:
Direct versus FFT convolution times in milliseconds
(convolution length =
) using Matlab 5.2 on an 800 MHz Athlon Windows PC.
M |
Direct |
FFT |
Ratio |
1 |
0.07 |
0.08 |
0.91 |
2 |
0.08 |
0.08 |
0.92 |
3 |
0.08 |
0.08 |
0.94 |
4 |
0.09 |
0.10 |
0.97 |
5 |
0.12 |
0.12 |
0.96 |
6 |
0.18 |
0.12 |
1.44 |
7 |
0.39 |
0.15 |
2.67 |
8 |
1.10 |
0.21 |
5.10 |
9 |
3.83 |
0.31 |
12.26 |
10 |
15.80 |
0.47 |
33.72 |
11 |
50.39 |
1.09 |
46.07 |
12 |
177.75 |
2.53 |
70.22 |
13 |
709.75 |
5.62 |
126.18 |
14 |
4510.25 |
17.50 |
257.73 |
15 |
19050.00 |
72.50 |
262.76 |
16 |
316375.00 |
440.50 |
718.22 |
|
A table similar to Table
7.1 in Strum and Kirk
[
79, p. 521], based on the number of real
multiplies, finds that the
fft is faster starting at length

,
and that direct convolution is significantly faster for very short
convolutions (
e.g., 16 operations for a direct length-4 convolution,
versus 176 for the
fft function).
See Appendix
A for further discussion of FFT algorithms and their applications.
The
dual7.18 of the
convolution
theorem says that
multiplication in the time domain is
convolution in the frequency domain:
Theorem:
Proof: The steps are the same as in the convolution theorem.
This theorem also bears on the use of
FFT windows. It implies
that
windowing in the time domain corresponds to
smoothing in the frequency domain.
That is, the
spectrum of

is simply
filtered by

, or,

. This
smoothing reduces
sidelobes associated with the
rectangular window, which is the window one is using implicitly
when a data frame

is considered
time limited and therefore
eligible for ``windowing'' (and
zero-padding). See Chapter
8 and
Book IV [
70] for further discussion.
Theorem: For all

,
where the correlation operation `

' was defined in §
7.2.5.
Proof:
The last step follows from the
convolution theorem and the result

from §
7.4.2. Also, the
summation range in the second line is equivalent to the range
![$ [N-1,0]$](http://www.dsprelated.com/josimages_new/mdft/img1409.png)
because all indexing is modulo

.
Power Theorem
Theorem: For all

,
Proof:
As mentioned in §
5.8, physical
power is
energy per unit time.
7.19 For example, when a
force produces a motion,
the power delivered is given by the
force times the
velocity of the motion. Therefore, if

and

are in
physical units of force and velocity (or any analogous quantities such
as voltage and current, etc.), then their product

is proportional to the
power per sample at time

,
and

becomes proportional to the total
energy
supplied (or absorbed) by the driving force. By the power theorem,

can be interpreted as the
energy per bin in
the
DFT, or
spectral power,
i.e., the energy associated with a
spectral
band of width

.
7.20
Note that the power theorem would be more elegant if the
DFT were
defined as the
coefficient of projection onto the
normalized DFT sinusoids
That is, for the
normalized DFT (§
6.10), the power
theorem becomes simply

(Normalized DFT case)
We see that the power theorem expresses the invariance of the
inner
product between two
signals in the time and
frequency domains. If we
think of the inner product
geometrically, as in Chapter
5,
then this result is expected, because

and

are merely
coordinates of the same geometric object (a signal) relative to two
different sets of basis signals (the shifted
impulses and the
normalized
DFT sinusoids).
Rayleigh Energy Theorem (Parseval's Theorem)
Theorem:
For any

,
I.e.,
Proof: This is a special case of the
power theorem.
Note that again the relationship would be cleaner (

)
if we were using the
normalized DFT.
Stretch Theorem (Repeat Theorem)
Theorem: For all

,
Proof:
Recall the
stretch operator:
Let

, where

,

. Also
define the new denser frequency grid associated with length

by

, and define

as usual. Then
But
Thus,

, and by the
modulo indexing of

,

copies of

are generated as

goes from 0 to

.
Theorem: For all

,
Proof: Let
![$ k^\prime \in[0,M-1]$](http://www.dsprelated.com/josimages_new/mdft/img1440.png)
denote the frequency index in the
aliased spectrum, and
let

. Then

is length

,
where

is the downsampling factor. We have
Since

, the sum over

becomes
using the closed form expression for a
geometric series derived in
§
6.1. We see that the sum over

effectively
samples 
every

samples. This can be expressed in the
previous formula by defining

which ranges only over the
nonzero samples:
Since the above derivation also works in reverse, the theorem is proved.
An illustration of aliasing in the
frequency domain is shown in
Fig.
7.12.
>> N=4;
>> x = 1:N;
>> X = fft(x);
>> x2 = x(1:2:N);
>> fft(x2) % FFT(Downsample(x,2))
ans =
4 -2
>> (X(1:N/2) + X(N/2 + 1:N))/2 % (1/2) Alias(X,2)
ans =
4 -2
Zero Padding Theorem (Spectral Interpolation)
A fundamental tool in practical
spectrum analysis is
zero
padding. This theorem shows that zero padding in the time domain
corresponds to
ideal interpolation in the frequency domain (for
time-limited
signals):
Theorem: For any
where

was defined in Eq.

(
7.4), followed by the
definition of

.
Proof: Let

with

. Then
Thus, this theorem follows directly from the definition of the ideal
interpolation operator

. See §
8.1.3 for an
example of zero-padding in
spectrum analysis.
The
dual of the
zero-padding theorem states formally that
zero padding in the frequency domain corresponds to
periodic
interpolation in the time domain:
Definition: For all

and any integer

,
 |
(7.7) |
where zero padding is defined in §
7.2.7 and illustrated in
Figure
7.7. In other words, zero-padding a
DFT by the factor

in
the frequency domain
(by inserting

zeros at
bin number 
corresponding to
the
folding frequency7.21)
gives rise to ``periodic interpolation'' by the factor

in the time
domain. It is straightforward to show that the interpolation kernel
used in periodic interpolation is an
aliased sinc function,
that is, a
sinc function

that has been
time-
aliased on a block of length

. Such an
aliased sinc function
is of course periodic with
period 
samples. See Appendix
D
for a discussion of
ideal bandlimited interpolation, in which
the interpolating
sinc function is not aliased.
Periodic interpolation is ideal for
signals that are
periodic
in

samples, where

is the DFT length. For non-
periodic
signals, which is almost always the case in practice, bandlimited
interpolation should be used instead (Appendix
D).
It is instructive to interpret the
periodic interpolation theorem in
terms of the
stretch theorem,

.
To do this, it is convenient to define a ``zero-centered rectangular
window'' operator:
Definition: For any

and any odd integer

we define the
length
even rectangular windowing operation by
Thus, this ``
zero-phase rectangular window,'' when applied to a
spectrum 
, sets the
spectrum to zero everywhere outside a
zero-centered interval of

samples. Note that

is
the
ideal lowpass filtering operation in the frequency domain.
The ``cut-off frequency'' is
![$ \omega_c = 2\pi[(M-1)/2]/N$](http://www.dsprelated.com/josimages_new/mdft/img1463.png)
radians per
sample.
For even

, we allow

to be ``passed'' by the window,
but in our usage (below), this sample should always be zero anyway.
With this notation defined we can efficiently restate
periodic interpolation in terms of the

operator:
Theorem: When

consists of one or more
periods from a
periodic
signal

,
In other words, ideal periodic interpolation of one period of

by
the integer factor

may be carried out by first stretching

by
the factor

(inserting

zeros between adjacent samples of

), taking the
DFT, applying the ideal
lowpass filter as an

-point rectangular window in the frequency domain, and performing
the inverse DFT.
Proof: First, recall that

. That is,
stretching a signal by the factor

gives a new signal

which has a
spectrum 
consisting of

copies of

repeated around the unit circle. The ``baseband copy'' of

in

can be defined as the

-sample sequence centered about frequency
zero. Therefore, we can use an ``ideal filter'' to ``pass'' the
baseband spectral copy and zero out all others, thereby converting

to

.
I.e.,
The last step is provided by the
zero-padding theorem (§
7.4.12).
The previous result can be extended toward
bandlimited interpolation
of

which includes all nonzero samples from an
arbitrary time-limited
signal

(
i.e., going beyond the interpolation of only
periodic bandlimited
signals given one or more
periods

) by
- replacing the rectangular window
with a
smoother spectral window
, and
- using extra zero-padding in the time domain to convert the
cyclic convolution between
and
into an
acyclic convolution between them (recall §7.2.4).
The smoother spectral window

can be thought of as the
frequency response of the FIR
7.22 filter 
used as the
bandlimited interpolation kernel in the time domain. The number of
zeros needed in the zero-padding of

in the time domain is simply
length of

minus 1, and the number of zeros to be appended to

is the length of

minus 1. With this much
zero-padding, the
cyclic convolution of

and

implemented using
the
DFT becomes equivalent to acyclic convolution, as desired for the
time-limited signals

and

. Thus, if

denotes the nonzero
length of

, then the nonzero length of

is

, and we require the DFT length to be

, where

is the filter length. In operator
notation, we can express bandlimited
sampling-rate up-conversion by
the factor

for time-limited signals

by
 |
(7.8) |
The approximation symbol `

' approaches equality as the
spectral window

approaches
![$ \hbox{\sc Chop}_{N_x}([1,\dots,1])$](http://www.dsprelated.com/josimages_new/mdft/img1484.png)
(the
frequency response of the ideal
lowpass filter passing only the
original
spectrum 
), while at the same time allowing no time
aliasing (convolution remains acyclic in the time domain).
Equation (
7.8) can provide the basis for a high-quality
sampling-rate conversion algorithm. Arbitrarily long signals can be
accommodated by breaking them into segments of length

, applying
the above algorithm to each block, and summing the up-sampled blocks using
overlap-add. That is, the lowpass filter

``rings''
into the next block and possibly beyond (or even into both adjacent
time blocks when

is not
causal), and this ringing must be summed
into all affected adjacent blocks. Finally, the filter

can
``window away'' more than the top

copies of

in

, thereby
preparing the time-domain signal for
downsampling, say by

:
where now the lowpass filter frequency response

must be close to
zero for all

. While such a
sampling-rate conversion algorithm can be made more efficient by using
an
FFT in place of the DFT (see Appendix
A), it is not necessarily
the most efficient algorithm possible. This is because (1)

out
of

output samples from the IDFT need not be computed at all, and
(2)

has many zeros in it which do not need explicit
handling. For an introduction to time-domain sampling-rate
conversion (bandlimited interpolation) algorithms which take advantage
of points (1) and (2) in this paragraph, see,
e.g., Appendix
D and
[
72].
See
http://ccrma.stanford.edu/~jos/mdftp/DFT_Theorems_Problems.html
Next Section: Example Applications of the DFTPrevious Section: Derivation of the Discrete Fourier Transform (DFT)