14.1. Introduction to the Fourier Transform

Given a function h(t) specified for all t, we define the continuous Fourier transform (FT) of h(t) as

The inverse transform may then be shown to be

You should note carefully the sign convention in these definitions, and the presence of the factor in the exponent. Other definitions of the Fourier transform may have a different sign convention and may use w, the angular frequency, rather than f.

If t is regarded as the time in seconds, then f is the frequency in cycles per second. Of course, FT pairs apply not only to the time/frequency double, but also to many other pairs. For example, in optics and antenna theory, position in the electromagnetic field distribution across an aperture produces an FT pair with the angular distribution of the far-field electromagnetic field.

The continuous Fourier Transform defined here can be related to the Fourier series that you have studied in Chapter 1 by allowing the period of the function to trend to infinity. The fundamental then tends to zero frequency, and the overtones become more and more closely spaced. The summation of harmonics is replaced by the corresponding integral over frequency.

14.2. Sampling and the Sampling Theorem

Frequently, the function h(t) is not measured or specified continuously, but rather is measured at fixed intervals of time, or sampled. If h(t) is measured at the discrete times given by

t_n =n n= ...-3,-2,-1,0,1,2,3...

where is known as the sampling interval, we may write

h_n = h(t_n)

and h_n is a discrete representation of h(t).

The function h(t) is said to be band limited if its Fourier transform H(f) = 0 for |f| > f_c, where f_c is a finite `critical' frequency. A function may be band limited because it has been passed through a filter (e.g, an FM radio signal must be restricted by the station operators to the allowed band), or perhaps because it is generated by a process that has an upper limit to its frequency content (e.g. human speech).

The sampling theorem is very important, and states that a band-limited function f(t) is completely specified by the sampled values f(t_n), provided that the sampling interval is no longer than

The frequency f_c is then known as the Nyquist frequency, for the given sampling interval .

14.3. The Discrete Fourier Transform

Suppose that the function h(t) has been measured only at the discrete times t_k (either at the given times, or averaged over the corresponding time interval) given by

t_k =k k= 0,1,2,...,N-1

where N is the number of samples. (We will consider only cases in which N is even and, indeed, a power of 2.) The Discrete Fourier Transform (DFT) is then defined as

where the frequencies f_n are given by

This definition is based on the idea that the sampled function h_k is replicated indefinitely, in the sense that k₀ = k_N = k_2N = ..., k₀ = k_-N = k_-2N = ... and so forth for all the other elements. There is clearly a close relationship between the DFT and the continuous Fourier integral.

14.4. The Fast Fourier Transform -- FFT

The DFT requires the calculation of the sums

where . At first sight, this requires at least N² multiplications to generate all N of the coefficients H_n. But this is not the case. As explained in "Numerical Recipes", the summation may be broken into two parts, one over the even-numbered elements (k = 0,2,4,...) and the other over the odd-numbered elements (k = 1,3,5,..). In turn, each one of these parts can be broken into its even-numbered and odd-numbered parts, and the process can be continued, with careful book-keeping, until the summation has become divided into 1-point Fourier transforms (which are identity transforms). This repeated dissection of the series into even- and odd-numbered parts can be implemented in the computer by reversing the bit-pattern of the addresses of the data elements. After this is done, the required N values of H_n can be generated by making a sequence of 2,4,8,...-point summations. The total time for the operation scales not as N² but as NlogN, so that for large transforms there is a enormous saving in time.

As a consequence of the bit-reversal process, the application of the FFT to a vector of data in a computer leaves the resulting components of the transform in a rather mixed-up state. For the programs you will use in this course, this mixed-up state has been sorted out for you, so that the vector available after the FFT consists of values at the following frequency components in increasing order:

f(n=-N/2), f(n=-N/2+1), f(n=-N/2+2),...f(0), f(1),...f(N/2-2), f(N/2-1)

[Recall that f(n) = n/(2), so that the first frequency point is f=-1/2 and the last+1 (equal to the first) is f=1/2, if we define = 1.]