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



Proof:

Conjugation and Reversal
Theorem: For any
,

Proof:

Theorem: For any
,

Proof: Making the change of summation variable
, we get

Theorem: For any
,

Proof:
![\begin{eqnarray*}
\hbox{\sc DFT}_k[\hbox{\sc Flip}(x)] &\isdef & \sum_{n=0}^{N-1...
...-1}x(m) e^{j 2\pi mk/N} \isdef X(-k) \isdef \hbox{\sc Flip}_k(X)
\end{eqnarray*}](http://www.dsprelated.com/josimages_new/mdft/img1326.png)
Corollary:
For any
,


Proof: Picking up the previous proof at the third formula, remembering that 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















![\begin{eqnarray*}
X(k)&=&\sum_{n=0}^{N-1}\mbox{even}_n\cdot\mbox{even}_{nk}
+ ...
...10pt]
&=& \mbox{even}_k + j \cdot \mbox{even}_k = \mbox{even}_k.
\end{eqnarray*}](http://www.dsprelated.com/josimages_new/mdft/img1356.png)
Theorem: A real even signal has a real even transform:
Proof: This follows immediately from setting in the preceding
proof. From Eq.
(7.5), we are left with

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
,
![$\displaystyle \zbox {\hbox{\sc DFT}_k[\hbox{\sc Shift}_\Delta(x)] = e^{-j\omega_k\Delta} X(k).}
$](http://www.dsprelated.com/josimages_new/mdft/img1364.png)
Proof:
![\begin{eqnarray*}
\hbox{\sc DFT}_k[\hbox{\sc Shift}_\Delta(x)] &\isdef & \sum_{n...
...}x(m) e^{-j 2\pi mk/N} \\
&\isdef & e^{-j \omega_k \Delta} X(k)
\end{eqnarray*}](http://www.dsprelated.com/josimages_new/mdft/img1365.png)
The shift theorem is often expressed in shorthand as





Linear Phase Terms
The reason
is called a linear phase term is
that its phase is a linear function of frequency:








![$\displaystyle e^{-j \omega_k \Delta} X(k) \isdef
e^{-j \omega_k \Delta} G(k) e^{j\Theta(k)}
= G(k) e^{j[\Theta(k)-\omega_k\Delta]}
$](http://www.dsprelated.com/josimages_new/mdft/img1378.png)

Linear Phase Signals
In practice, a signal may be said to be linear phase when its phase is of the form








Zero Phase Signals
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''.
Application of the Shift Theorem to FFT Windows
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
,
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
and a real spectrum (verify this as an
exercise), which satisfies the definition of a linear phase signal.
Convolution Theorem
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.)
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.
|
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.
Dual of the Convolution Theorem
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.
Correlation Theorem
Theorem: For all
,


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
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
Normalized DFT Power Theorem
Note that the power theorem would be more elegant if the DFT were defined as the coefficient of projection onto the normalized DFT sinusoids





Rayleigh Energy Theorem (Parseval's Theorem)
Theorem:
For any
,


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:
![$\displaystyle \hbox{\sc Stretch}_{L,m}(x) \isdef
\left\{\begin{array}{ll}
x(...
...=\mbox{integer} \\ [5pt]
0, & m/L\neq \mbox{integer} \\
\end{array} \right.
$](http://www.dsprelated.com/josimages_new/mdft/img1430.png)















Downsampling Theorem (Aliasing Theorem)
Theorem: For all
,

Proof: Let
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
![$\displaystyle \sum_{l=0}^{L-1}\left[e^{-j2\pi n/L}\right]^l =
\frac{1-e^{-j2\p...
...ht) \\ [5pt]
0, & n\neq 0 \left(\mbox{mod}\;L\right) \\
\end{array} \right.
$](http://www.dsprelated.com/josimages_new/mdft/img1447.png)





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.
Illustration of the Downsampling/Aliasing Theorem in Matlab
>> 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




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.
Periodic Interpolation (Spectral Zero Padding)
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
,
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







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).
Relation to Stretch Theorem
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




![$ \omega_c = 2\pi[(M-1)/2]/N$](http://www.dsprelated.com/josimages_new/mdft/img1463.png)



Theorem: When
consists of one or more periods from a periodic
signal
,








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.,

Bandlimited Interpolation of Time-Limited Signals
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 approximation symbol `


![$ \hbox{\sc Chop}_{N_x}([1,\dots,1])$](http://www.dsprelated.com/josimages_new/mdft/img1484.png)

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
:






Next Section:
DFT Theorems Problems
Previous Section:
Even and Odd Functions