Fast Fourier Transform

Evaluation of the Fourier coefficients for a periodic function and of the Fourier transform for a pulse-type func- tion require the evaluation of definite integrals. By thinking of the definite integral as an area under a curve, the rectangular rule can be used to approximate the integral by a summation, as already shown in Section 2.12.

To apply the rectangular rule, samples are taken at uniform intervals T_sin the time domain, a total of N samples being taken. Denoting the sample number by an integer k, where 0 k N 1, then the variable t in the integral is replaced by kT_s, and the limits on the integral are replaced by the summation limits 0 and

v(t)↔V(f) v(t) F¹[V(f)]

N1. In the rectangular rule approximation to the integral, the dtunder the integral sign is replaced by T_s outside the summation sign.

As shown in Section 2.12, the exponential coefficients are given by

(2.14.1) Applying a similar argument to the Fourier transform integral of Eq. (2.13.2) gives

(2.14.2) The fast Fourier transform algorithm provides a computationally efficient way of evaluating the sum- mations. For the versions most commonly in use, the number of samples is always an integral power of 2.

WhenN samples are taken in the time domain, the transform computation will produceN values in the fre- quency domain also. However, computer printouts will usually show only the positive frequency half of the spectrum, since the negative half is known to be the complex conjugate of the positive half. The printout for the frequency domain usually contains (N/2 1) values, where the last value is known as the fold-over value.

The reason for this will be explained shortly in connection with the inverse transform. For example, ifN 32 samples in the time domain, the printout will contain 17 spectrum values. WithN a power of 2,N 2^m, where mis an integer, and the printout will contain 2^m1 components.

Figure 2.14.1(a) shows the relationships between sample points in the time domain, and Figure 2.14.1(b) the relationships in the frequency domain for a pulse waveform.

For periodic functions, the harmonics c_nare spaced by nf₀in the frequency domain, where f₀1/T₀and T₀is the periodic time. For aperiodic signals (for example, a pulselike function),T₀represents the time base over which the pulse is sampled, and the spacing of the V(n) values in the frequency domain are spaced by nF₀, where F₀1/T₀. Although the equation form is the same, uppercase Fis used to emphasize the fact that the values obtained for the aperiodic function are not harmonics, but point values on the continuous spectrum den- sity curve.

When analyzing time functions, the sampling frequency is set at twice the highest frequency component in the spectrum of the waveform being analyzed, as required by the Nyquist sampling theorem(which is dis- cussed more fully in Chapter 11). This would seem to be a catch, since the point of the analysis is to find the spectrum, and hence by definition the highest frequency is not known. However, in practice certain physical con- straints, which are known, will limit the spectrum. For example, the signal will usually be filtered and the filter characteristics known. Assuming therefore that the highest significant frequency in the spectrum is known, and denoting this by f_h, the sampling frequency is given by f_s2f_n. The sampling interval is T_sl/f_s. The mini- mum number of samples would be T₀/T_s, where T₀is the periodic time (or time base for a pulse), but the T₀/T_s has to be rounded up to the nearest integer power of 2. For example, if T₀/T_swere to equal 120, thenN 128 samples should be used.

In applying computer packages that provide the fft function, in order to be able to correctly interpret the results we must be aware that various versions of the summation formula exist. For example, the Mathcad formulation for the fft is of the form

(2.14.3) To obtain cnfrom the Mathcad gn, the complex conjugate of the gnvalues must be taken and the result multiplied by 1N so that the final multiplier is 1/N, as required by Eq. (2.14.1). To obtain V(n) from g_n,

g_n 1

N^k_k

V(n) T_s^k_k

c_n 1

N^k_k

EXAMPLE 2.14.1

For the periodic waveform shown in Fig. 2.12.2, it is known that the highest harmonic is the third. Apply the Mathcad fft function to find the exponential Fourier series.

SOLUTION Since the highest harmonic is the third, the number of samples should be at least 2 3 6;

but to meet the fft requirements, eight will be used. SetN 8 and define an index kfor eight samples:

Denote the sample values by s. These are shown in Fig. 2.12.2 as N 8 k 0 …7

v(t)

T_s

T_o

N

V(_f)

To

F_o =

f_s=

1 = NT_s

Nth sample N =32 samples

k = 0 2

2

1

spectrum values

Fold over point (a)

(b)

4 6 8 10 12 14 16 18 20 22 24 26 28 30 31 τ

n = 0 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

T1_s

Figure 2.14.1 (a) Sampling a rectangular pulse. (b) Computed spectrum density samples.

again the complex conjugate must be used and the result multiplied by so that the final multiply- ing factor is T_s, as required by Eq. (2.14.2).

To check the results of any computer applications package, the best procedure is to apply it first to a known function and check the result. This is illustrated in the following example using the Mathcad package.

T_sN

s_k: k

Take the fft: S : fft(s)

Form the complex conjugate:

The required spectrum is:

These can be shown as:

These are the values for the positive half of the spectrum. Note that the last value, the fold-over value, is zero. The coefficients for the negative half are the complex conjugates of these.

c

c 1

NS S S