## 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

 (7.5)

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.

#### Linear PhaseSignals

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

#### Zero PhaseSignals

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.

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.

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

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 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 DFTPower 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

That is, for the normalized DFT6.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 .

### 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

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.

#### 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

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.

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

 (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).

#### 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

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 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 theorem7.4.12).

#### 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

1. replacing the rectangular window with a smoother spectral window , and
2. 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 FIR7.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 (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].

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