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 timeinvariant filtering, sampling rate conversion, and statistical signal processing.
The DFT and its Inverse Restated
Let , denote an sample complex sequence, i.e., . Then the spectrum of is defined by the Discrete Fourier Transform (DFT):
Notation and Terminology
If is the DFT of , we say that and form a transform pair and write
If we need to indicate the length of the DFT explicitly, we will write and . As we've already seen, timedomain signals are consistently denoted using lowercase symbols such as ``,'' while frequencydomain 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,
Moreover, the DFT also repeats naturally every samples, since
Definition (Periodic Extension): For any signal
, we define
As a result of this convention, all indexing of signals and spectra^{7.2} can be interpreted modulo , and we may write to emphasize this. Formally, `` '' is defined as with chosen to give in the range .
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 timedomain 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].
Signal Operators
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 signalvalued function of a signal. Thus, for the space of length complex sequences, an operator is a mapping from to :
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 signalprocessing 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
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 .
Shift Operator
The shift operator is defined by
Figure 7.2 illustrates successive onesample delays of a periodic signal having first period given by .
Examples

(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
Cyclic convolution can be expressed in terms of previously defined operators as
Commutativity of Convolution
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 .
Convolution as a Filtering Operation
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 :
As discussed below (§7.2.7), one may embed acyclic convolution within a larger cyclic convolution. In this way, realworld systems may be simulated using fast DFT convolutions (see Appendix A for more on fast convolution algorithms).
Note that only linear, timeinvariant (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
Filter
input signal .
Filter impulse response .
Filter output signal . 
Figure 7.3 illustrates convolution of
as graphed in Fig.7.3(c). In this case, can be viewed as a ``moving threepoint average'' filter. Note how the corners of the rectangular pulse are ``smoothed'' by the threepoint 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
Convolution Example 2: ADSR Envelope
Filter 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 smoothingfilter 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 timeconstants 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, socalled virtual analog synthesizers. Such an ADSR envelope is typically used to multiply the output of a waveform oscillator such as a sawtooth or pulsetrain oscillator. For more on virtual analog synthesis, see, for example, [78,77].
Convolution Example 3: Matched Filtering
Figure 7.5 illustrates convolution of
to get
For example, could be a ``rectangularly windowed signal, zeropadded by a factor of 2,'' where the signal happened to be dc (all s). For the convolution, we need
Graphical Convolution
As mentioned above, cyclic convolution can be written as
Polynomial Multiplication
Note that when you multiply two polynomials together, their coefficients are convolved. To see this, let denote the thorder polynomial
Denoting by
where and are doubly infinite sequences, defined as zero for and , respectively.
Multiplication of Decimal Numbers
Since decimal numbers are implicitly just polynomials in the powers of 10, e.g.,
Correlation
The correlation operator for two signals and in is defined as
We may interpret the correlation operator as
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.
A stretch by factor is defined by
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:
where , with for odd, and for even. For example,
Figure 7.7 illustrates zero padding from length out to length . Note that and could be replaced by and in the figure caption.
Note that we have unified the timedomain and frequencydomain definitions of zeropadding by interpreting the original time axis as indexing positivetime samples from 0 to (for even), and negative times in the interval .^{7.8} Furthermore, we require when is even, while odd requires no such restriction. In practice, we often prefer to interpret timedomain samples as extending from 0 to , i.e., with no negativetime samples. For this case, we define ``causal zero padding'' as described below.
Causal (Periodic) Signals
A signal may be defined as causal when for all ``negativetime'' samples (e.g., for when is even). Thus, the signal is causal while is not. For causal signals, zeropadding is equivalent to simply appending zeros to the original signal. For example,
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 starttime of the frame as zero, with no negativetime samples. In other words, represents an sample signalsegment that is translated in time to start at time 0. In this case (no negativetime samples in the frame), it is proper to zeropad by simply appending zeros at the end of the frame. Thus, we define e.g.,
In summary, we have defined two types of zeropadding that arise in practice, which we may term ``causal'' and ``zerocentered'' (or ``zerophase'', or even ``periodic''). The zerocentered case is the more natural with respect to the mathematics of the DFT, so it is taken as the ``official'' definition of ZEROPAD(). In both cases, however, when properly used, we will have the basic Fourier theorem (§7.4.12 below) stating that zeropadding in the time domain corresponds to ideal bandlimited interpolation in the frequency domain, and vice versa.
Zero Padding Applications
Zero padding in the time domain is used extensively in practice to compute heavily interpolated spectra by taking the DFT of the zeropadded 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 timelimited 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 timelimited unless it is the zero signal. On the other hand, the interpolation of a timelimited signal's spectrum is nonzero almost everywhere between the original spectral samples. Thus, zeropadding is often used when analyzing data from a nonperiodic signal in blocks, and each block, or frame, is treated as a finiteduration signal which can be zeropadded on either side with any number of zeros. In summary, the use of zeropadding corresponds to the timelimited assumption for the data frame, and more zeropadding yields denser interpolation of the frequency samples around the unit circle.
Sometimes people will say that zeropadding 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 paddingi.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, zeropadding in one domain corresponds to a higher interpolationdensity in the other domainnot 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.9}In other words, for truly timelimited signals , taking the DFT of the entire nonzero portion of extended by zeros yields exact interpolation of the complex spectrumnot an approximation (ignoring computational roundoff error in the DFT itself). Because the fast Fourier transform (FFT) is so efficient, zeropadding followed by an FFT is a highly practical method for interpolating spectra of finiteduration 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
Interpolation Operator
The interpolation operator interpolates a signal by an integer factor using bandlimited interpolation. For frequencydomain 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 timelimited spectral interpolation in this case).
For timedomain 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
A frequencydomain 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 rightrear 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 .
The repeat operator is used to state the Fourier theorem
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 timevarying operators. They can be modeled using timevarying switches controlled by the sample index .
The following example of is illustrated in Fig.7.10:
Note that the term ``downsampling'' may also refer to the more elaborate process of samplingrate 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 lowpassfilter is needed, in general, prior to downsampling so that aliasing is avoided. This topic is address in Appendix D. Early samplingrate converters were in fact implemented using the operation, followed by an appropriate lowpass filter, followed by , in order to implement a samplingrate conversion by the factor .
Alias Operator
Aliasing occurs when a signal is undersampled. If the signal sampling rate is too low, we get frequencydomain aliasing.
The topic of aliasing normally arises in the context of sampling a continuoustime 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 discretetime signals, in order to keep the math as simple as possible. Aliasing in this context occurs when a discretetime signal is downsampled to reduce its sampling rate. You can think of continuoustime 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 highfrequency sinusoid is indistinguishable from the lowerfrequency sinusoid due to aliasing. We say the higher frequency aliases to the lower frequency.
Undersampling in the frequency domain gives rise to timedomain aliasing. If time or frequency is not specified, the term ``aliasing'' normally means frequencydomain 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 timedomain aliasing; if it is a spectrum, we call it frequencydomain 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)
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.12bc) cover frequencies 0 to .
In general, aliasing by the factor corresponds to a samplingrate reduction by the factor . To prevent aliasing when reducing the sampling rate, an antialiasing lowpass filter is generally used. The lowpass filter attenuates all signal components at frequencies outside the interval 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
, 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
,
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:
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
skewHermitian.
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 negativefrequency spectral samples of a real signal and regenerate them later if needed from the positivefrequency 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:
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 zerophase over at least some band
containing dc (up to the first zerocrossing in frequency). When the
phase switches between 0 and at the zerocrossings of the
(real) spectrum, the spectrum oscillates between being zero phase and
``constant phase''. We can say that all real spectra are
piecewise constantphase spectra, where the two constant values
are 0 and (or , which is the same phase as ). In
practice, such zerocrossings typically occur at low magnitude, such
as in the ``sidelobes'' of the DTFT of a ``zerocentered 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
Linear Phase Terms
The reason is called a linear phase term is that its phase is a linear function of frequency:
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 zerophase signal is thus a linearphase signal for which the phaseslope is zero. As mentioned above (in §7.4.3), it would be more precise to say ``0orphase signal'' instead of ``zerophase signal''. Another better term is ``zerocentered signal'', since every real (even) spectrum corresponds to an even (real) signal. Of course, a zerocentered symmetric signal is simply an even signal, by definition. Thus, a ``zerophase 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 Transform^{7.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 oddlength real
symmetric signals are ``linear phase'', including FFT windows.
When is even, the window midpoint at time lands halfway between samples, so we cannot simply translate the window to zerocentered 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 FFTbased convolution requires on the order of operations, where denotes the logarithmbase2 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 builtin function in both cases.)
N = 1024; % FFT much faster at this length t = 0:N1; % [0,1,2,...,N1] 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 directconvolution time = %0.2f msec\n',... 'Average FFTconvolution time = %0.2f msec\n',... 'Ratio = %0.2f (Direct/FFT)'],... t1/Nrep,t2/Nrep,t1/t2)); % =================== EXAMPLE RESULTS =================== Octave: Average directconvolution time = 69.49 msec Average FFTconvolution time = 0.23 msec Ratio = 296.40 (Direct/FFT) Matlab: Average directconvolution time = 15.73 msec Average FFTconvolution 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 length4 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 dual^{7.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 zeropadding). 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:
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
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 timelimited 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 zeropadding in spectrum analysis.
Periodic Interpolation (Spectral Zero Padding)
The dual of the zeropadding 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, zeropadding a DFT by the factor in the frequency domain (by inserting zeros at bin number corresponding to the folding frequency^{7.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 timealiased 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 nonperiodic 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 ``zerocentered rectangular window'' operator:
Definition: For any
and any odd integer we define the
length even rectangular windowing operation by
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 TimeLimited Signals
The previous result can be extended toward bandlimited interpolation of which includes all nonzero samples from an arbitrary timelimited 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 zeropadding in the time domain to convert the cyclic convolution between and into an acyclic convolution between them (recall §7.2.4).
The approximation symbol `' approaches equality as the spectral window approaches (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 highquality samplingrate 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 upsampled blocks using overlapadd. 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 timedomain signal for downsampling, say by :
DFT Theorems Problems
See http://ccrma.stanford.edu/~jos/mdftp/DFT_Theorems_Problems.html
Next Section:
Example Applications of the DFT
Previous Section:
Derivation of the Discrete Fourier Transform (DFT)