Fourier Transform

The Fourier Transform

The Fourier transform decomposes or separates a waveform or function into sinusoids of different frequency which sum to the original waveform. It identifies or distinguishes the different frequency sinusoids and their respective amplitudes. The Fourier transform of f(x) is defined as

F(s) = ò   f(x) exp(-i 2pxs) dx

Applying the same transform to F(s) gives

f(w) = ò   F(s) exp(-i 2pws) ds

If f(x) is an even function of x, that is f(x) = f(-x), then f(w) = f(x). If f(x) is an odd function of x, that is f(x) = -f(-x), then f(w) = f(-x). When f(x) is neither even nor odd, it can often be split into even or odd parts.

To avoid confusion, it is customary to write the Fourier transform and its inverse so that they exhibit reversibility:

F(s) =ò   f(x) exp(-i 2pxs) dx

f(x) =ò   F(s) exp(i 2pxs) ds

so that

f(x) = ò  [ò  f(x) exp(-i 2pxs) dx] exp(i 2pxs) ds

as long as the integral exists and any discontinuities, usually represented by multiple integrals of the form ½[f(x+) + f(x-)], are finite. The transform quantity F(s) is often represented as f(s) and the Fourier transform is often represented by the operator.

            There are functions for which the Fourier transform does not exist and there is no relevant physical meaning; however, most physical functions have a Fourier transform, especially if the transform represents a physical quantity. It is still possible to interpret the transform in a way similar to a continuous time signal spectrum as a function of frequency. Other functions can be treated with Fourier theory as limiting cases. Many of the common theoretical functions are actually limiting cases in Fourier theory.

Usually functions or waveforms can be split into even and odd parts as follows

f(x) = E(x) + O(x)                   where               E(x) = ½ [f(x) + f(-x)]

O(x) = ½ [f(x) - f(-x)]

and E(x), O(x) are complex in general.

In this representation, the Fourier transform reduces to

f(x) =  2ò   E(x) cos(2pxs) dx - 2iò   O(x) sin(2pxs) dx

It follows then that an even function has an even transform and that an odd function has an odd transform. Additional symmetry properties are shown in Table 1.

Table 1: Symmetry Properties of the Fourier Transform

An important case from Table 1 is that of an Hermitian function, one in which the real part is even and the imaginary part is odd, i.e., f(x) = f*(-x). The Fourier transform of a Hermitian function is even. In addition, the Fourier transform of the complex conjugate of a function f(x) is F*(-s), the reflection of the conjugate of the transform.

The cosine transform of a function f(x) is defined as

F_c(s) = 2ò   f(x) cos 2psx dx.

This is equivalent to the Fourier transform if f(x) is an even function. In general, the even part of the Fourier transform of f(x) is the cosine transform of the even part of f(x). The cosine transform has a reverse transform given by

f(x) = 2ò   F_c(s) cos 2psx ds.

Likewise, the sine transform of f(x) is defined by

F_S(s) = 2ò   f(x) sin 2psx dx.

As a result, i times the odd part of the Fourier transform of f(x) is the sine transform of the odd part of f(x).

Combining the sine and cosine transforms of the even and odd parts of f(x) leads to the Fourier transform of the whole of f(x):

f(x) =    _CE(x) – i    _SO(x)

where   ,    _C, and    _S stand for -i times the Fourier transform, the cosine transform, and the sine transform respectively, or

F(s) = ½F_C(s) - ½iF_S(s)

Since the Fourier transform F(s) is a frequency domain representation of a function f(x), the s characterizes the frequency of the decomposed cosinusoids and sinusoids and is equal to the number of cycles per unit of x. If a function or waveform is not periodic, then the Fourier transform of the function will be a continuous function of frequency.

 The diagram below shows how a square wave can be made up by adding together pure sine waves at the harmonics of the fundamental frequency. Any signal can be made up by adding together the correct sine waves with appropriate amplitude and phase. The Fourier transform is an equation to calculate the frequency, amplitude and phase of each sine wave needed to make up any given signal.

0…

Discrete Fourier Transform (DFT)

A digital computer can only work with discrete data and therefore the numerical computation of the Fourier transform of f(t) requires discrete sample values of f(t) which is called f_k. In addition, a computer can compute the transform F(s) only at discrete values of s. It can only provide discrete samples of the transform, F_r. If f(kT) and F(rs₀) are the kth and rth samples of f(t) and F(s) respectively and N₀ is the number of samples in the signal in one period T₀, then

f_k = T f(kT) = T₀N₀^-1 f(kT)

F_r = F(rs₀)                        where  s₀ = 2p ₀  = 2p T₀^-1

The discrete Fourier transform (DFT) is defined as

F_r = Sf_k exp(-i rW₀k)                           where W₀ = 2pN₀^-1

Its inverse is                              f_k = N₀^-1 SF_r exp(i rW₀k)

These equations can be used to compute transforms and inverse transforms of appropriately sampled data.

Windows

Windows are needed for any time when a signal is chopped into buffers and the signal is taken to be periodic (rather than zero) outside the observation buffer. This is very frequent occurrence in DSP. When calculating autocorrelations the use of windows is almost universal; a popular technique of designing finite impulse response (FIR) filters is based on truncating the desired impulse response by a window; the sample buffers are windowed before Linear Predictive Coding (LPC) analysis; and the list goes on by on. Yet windowing as a preprocessing stage for the periodogram is probably the best-known use.

The computer programming convention that the buffer index runs from 0 to N-1 is usually used with a window that obeys w₀= 0 and w_N=0. The first point in the output buffer is set to zero but the last point is not (N^th point, which is zero, belongs to the next buffer). The conventions such as w₀= 0, w_N-1=0 or w_N=0, w_-1=0 should be avoided. The former implies two zeroed samples in the replicated signal. In theoretical treatments, the symmetric buffer indexation –M…M with M =N/2 is common, and here only one of the endpoints is to be considered as belongings to the present buffer. To make things worse the buffer may be even or odd, although Fast Fourier Transform (FFT) buffers will usually be of even length. The expressions are to be in two formats, the practical 0…N-1 with even N and w₀= 0, w_N=0 and the symmetric odd length –M…M with w_±m= 0 and thus N = 2M+1. An index n is used to differentiate the former case and m for the latter. Some common window functions that are used: 

1. Rectangle
2. Hanning/Hamming

(i) Rectangular Window

The rectangle window is used to produce a finite signal from the infinite signal (basically used whenever any signal is sampled). Measuring analog time in units of sampling interval, an analog window function w(t) that is one between t = -M and t= +M and zero elsewhere.

With the frequency response of

Its main lobe (defined between the first zeros) is of width 2p/M. As M increases the main lobe becomes narrower and taller. If the frequency resolution is increased, as allowed by the uncertainty theorem, the number of frequency bins remains the same. In the digital domain the N = 2M point FFT has a frequency resolution of 1/N (the sampling frequency is one) and thus the main lobe is two frequency bins in width for all M. The digital window is w_m = 1 for –M £m£ +M and w_m = 0 elsewhere. The Discrete Fourier Transform (DFT) is given by

          W_k =  Se^-ikm

= e^-ikM [1-e^ike^-2ikM/ (1-e^-ik)]

                                                   = sin (1/2 Nk)/ sin(1/2k)                        where N = 2M+1

Its main lobe is two bins in width and it has and infinite number of sidelobes with each lobe in width. Its highest sidelobe is attenuated 13.3dB with respect to the main lobe and the sidelobes decay by 6dB peroctave as expected of a window with a discontinuity.

Before continue, some consistent quantities with which to compare windows are needed. The noise bandwidth is one commonly used measure. It is defined as the bandwidth of an ideal filter with the same maximum gain that will pass the same amount of power from a white noise source. The noise bandwidth of the rectangular window is precisely one, but is larger than one for all other windows. Larger main lobes imply larger noise bandwidths. Another important parameter is the ripple of the frequency response in the pass-band. The rectangular window has almost 4dB pass-band ripple, while many other windows have much smaller ripple.