Applications of the Fourier Transform to Digital Signal Processing (DSP) Part I

IMAG0234 IMAG0235 IMAG0236 IMAG0237 (1)In the previous blogs, we invested our time and energy understanding the continuous signal theory because many of the signals that find their way into digital signal processing are thought to arise from some underlying continuous function. In the next few blogs, we discuss the relationship between these underlying continuous signals and the discrete signals that are produced by their sampling. Fundamental problems will be encountered. A parallel development of the sampling process, in both the time and frequency domains, will clarify thse problems and show how to cope with them. However, the deeper insight provided by this development will permit us to evaluate the severity of the limitations encountered in a given circumstance. Finally, after we understand the relationship between the Fourier integral transform and the DFT, new useful ideas will emerge on interpolation, decimation and modulation.

Uptil now we have followed (or assumed to have followed!) a natural course through three kinds of time-frequency transformations: First, evaluation of the frequency response of discrete LTI systems led to the discrete time/continuous frequency description of digital impulse responses and their spectra. Then, by computing this spectra at discrete points in frequency, we were led to the discrete time/discrete frequency domain of the DFT. Lastly, suitable limits took the DFT over into the Fourier integral transform of continuous time and frequency.

To complete our journey into time-frequency transformations, we next address the fourth possibility:  continuous time and discrete frequency.

Continuous Time, Discrete Frequency: The Fourier Series

Discrete spectra are familiar from areas such as spectroscopy, where they are called line spectra. Viewed mathematical entity by itself, apart from continuous signals, we know that the DFT relates equally spaced discrete spectra to equally spaced data points in time. We now ask what are the consequences of demanding equally spaced discrete spectra from a set of continuous time domain data. That is, we require that

F(\omega)=2\pi\sum_{n=-\infty}^{\infty}a_{n}\delta(\omega - n\omega_{0}) Eqn 1

which places spectral lines of magnitude 2\pi a_{n} at multiples of the fundamental frequency \omega_{0}. The time domain signal with such a spectrum is

f(t)=\frac{1}{2\pi}\int_{-\infty}^{\infty}F(\omega)e^{i \omega t}dt, which in turn is equal to

\frac{1}{2\pi}\int (2\pi)\sum a_{n} \delta(\omega - n \omega_{0})e^{i \omega t}

or f(t)=\sum_{n=-\infty}^{\infty}a_{n}e^{i n \omega_{0}t} Eqn 2

Clearly, f(t) is still a continuous function of time, but the discrete, equally spaced spectrum has produced periodicity in the time domain of period

T=\frac{2\pi}{\omega_{0}}

since f(t+(2\pi)/\omega_{0})=f(t)

Equation 2 is exactly equivalent to the equation connecting discrete, equally spaced time domain data to continuous periodic spectra with the roles of time and frequency interchanged.

To complete the continuous time/discrete frequency picture,we should find the forward transform that takes f(t) into F(\omega). Because f(t) is periodic, no new information is contained outside of the interval \frac {-T}{2} to

\frac{T}{2}.

Thus motivated, we integrate equation II over these limits with the appropriate Fourier kernel:

\int_{(-T)/2}^{T/2}f(t)e^{-im\omega_{0}t}dt which is equal to

\sum_{n}\int_{(-T)/2}^{T/2}e^{i(n-m)\omega_{0}t}dt

Direct elementary integration shows that

\int_{(-T)/2}^{T/2}e^{i(n-m)\omega_{0}t}dt=T\delta (nm) Eqn III

giving \int_{(-T)/2}^{T/2}f(t)e^{-im\omega_{0}t}dt=Ta_{m}

This result, combined with equation II, provides the desired pair of transformations, relating continuous time periodic functions with their equally spaced discrete spectra:

a_{n}=(1/T)\int_{(-T)/2}^{T/2}f(t)e^{-in\omega_{0}t}dt Eqn IVa

f(t)=\sum_{n=-\infty}^{\infty}a_{n}e^{in\omega_{0}t} Eqn IVb

Equations IV called the Fourier Series, play a major role in continuous theory because periodic, continuous time signals are so common place in many applications. Equation IVa is sometimes called the analysis equation because it separates the periodic time signal into its component line spectra, a_{n}. Equation IVb represents the Fourier synthesis of a periodic, continuous time signal from the superposition of complex sinusoids with frequencies that are multiples of the fundamental. The sum may or may not extend to infinity. The a_{n} are called Fourier coefficients. Three common examples of Fourier series, the square wave, the triangle wave, and the full wave rectified sine wave are shown in Figure 1.

It is interesting to note that the Fourier series, which has dominated Fourier theory since its inception, takes on only a very minor part in digital signal processing. In fact, we introduce it here mainly to complete the discussion of the four types of Fourier transforms arising from the four possible combinations of discrete/continuous-time, discrete-frequency Fourier series in our discussion for two purposes to examine its least-squares convergence properties and to introduce the sampling function.

For reference, we summarize the four types of Fourier transformations in Figure 2, reviewing just how they arise in our (assumed, if need be) natural course of discussion. Clearly, there are two types of transformations that might properly be called Fourier series discrete time and continuous time Fourier series. Mathematically, these two transformations are identical, but with the roles of time and frequency interchanged. Next, we explore the interesting convergence properties of these two types of Fourier series.

The Least Squares Convergence of the Fourier Series

The convergence property of the Fourier series is both curious and interesting in its own right; additionally, it has important implications for digital filter design. Our approach is to pretend that we do not know how to compute the Fourier coefficients as given in equation IVa. Instead, we wish to take an alternate tack to the course of the previous section and determine the

a_{n} by curve fitting. That is, following the notion of Fourier synthesis, suppose that we wish to synthesize a given continuous periodic function f(t) from a superposition of a finite number of sinusoids equally spaced in frequency. The result of such a superposition of N sinusoids is

\hat{f}(t)=\sum_{n=0}^{N}a_{n}e^{in\omega t} Eqn V

Generally, when the finite sum is used, \hat{f}(t) will be different from f(t). Of all the possible criteria for minimizing this difference, we choose to minimize the total squared error over the period of f(t); that is, we wish to determine the a_{n} that minimizes:

the-sum - squared - error =\int_{(-T)/2}^{T/2}|f(t)-\hat{f}(t)|^{2}dt Eqn 6

The minimum is found by differentiating with respect to a_{m}^{*} (note that

a_{m} and a_{m}^{*} are independent):

\frac{\partial}{\partial a_{m}^{*}}\int_{(-T)/2}^{T/2}|f(t)-\sum_{n=0}^{N}e^{in\omega t}|^{2}dt=0

giving

\int_{-T/2}^{T/2}(f(t)-\sum a_{n})e^{-im\omega t}dt=0, or

\int f(t)e^{-im\omega t}dt=\sum_{n}a_{n}\int_{(-T)/2}^{T/2}e^{i(n-m)\omega t}dt, which, in turn is equal to

T\sum_{n}a_{n}\delta(nm)

Thus, the coefficient that minimizes the total squared error is

a_{m}=(1/T)\int_{(-T)/2}^{T/2}f(t)e^{-im\omega t}dt just the normal Fourier series coefficient.

The conclusion is somewhat surprising: simple truncation of a function’s Fourier series expansion approximates the function in the least-squares sense. This serendipitous result allows us to take satisfaction in the knowledge that as each term is added to the partial sum in Equation V, the best possible fit to f(t) is obtained, for that number of terms, in the least squares sense. In addition, a second surprise concerning the nature of Fourier series convergence occurs as a discontinuity.

Three examples of partial sums for a square wave synthesis are shown in Figure V. In each case, an overshoot occurs near the discontinuity, and the partial sums equal the average value of the jump at the discontinuity. The unexpected behaviour of the convergence is that the amount of overshoot remains constant as more terms are added. In fact, it can be shown that this overshoot approaches a constant 8.9% of the jump at the discontinuity as the number of terms in the partial sum tends to infinity. It might be natural to expect that this overshoot tends to zero with an increasing number of terms, but this is not the case. This unexpected convergence behaviour was first described by the British mathematician H. Wilbraham, but it was made more well known by a public exchange in “Nature” journal between American physicists A. Michelson and J. W. Gibbs. In a 1898 letter to “Nature”, Michelson explained that he was having difficulty synthesizing a discontinuity from the summation of the first 80 terms of a Fourier series. He suspected that the device he used to determine the Fourier coefficients, called a harmonic analyzer, was defective or that the mathematicians were all wet in saying that a discontinuity could be replaced by a summation of continuous functions. In a responding letter, one year later, Gibbs explained the true nature of convergence, which is now called the Gibbs phenomenon.

As terms are added to the partial sum, the integrated squared error of Equation VI does indeed decrease uniformly, the wriggles of the Gibbs phenomenon increase in frequency and shift toward the discontinuity as seen in Figure 3, decreasing the squared area between them and the desired function. The amplitude of the largest wriggle does not decrease, but the integrated squared error does decrease uniformly.

The importance of the Gibbs phenomenon to digital signal processing can be appreciated by considering the design of an ideal lowpass filter. The frequency response of such a filter is a continuous periodic function with a discontinuity at the cutoff frequency. The discrete time domain operator consists of the Fourier coefficients of this frequency response function. These coefficients are easily computed for any cut off frequency, but the operator will be infinitely long. The situation is similar to that shown in Figure 5, with the roles of time and frequency interchanged. If the infinitely long time domain operator is simply truncated to produce a workable digital filter, the Gibbs phenomenon is produced in the frequency response, making the ideal low pass filter unobtainable with a finite length operator. The question then of how to obtain the best time domain coefficients of a given length becomes the interesting and challenging problem of digital filter design. Later, in these blogs, we will see several approaches to designing digital filters, given their desired frequency response.

The Sampling Function

We next exploit the continuous time Fourier series to introduce the sampling function, a transform pair that will serve as a major structural element in building a bridge of insight and interpretation between continuous signals and the DFT. In the continuous time Fourier series representation, f(t) is periodic of period T. By selecting f(t)=\delta(t), a series of delta function spikes is formed in the time domain equally spaced by T. Such a series of spikes would be written as:

f(t)=\sum_{n=-\infty}^{\infty}\delta(t-nT)

The Fourier coefficients of this spike train are given by

a_{n}=(1/T)\int_{(-T)/2}^{T/2}\delta(t)e^{-in\omega_{0}t}dt where

\omega_{0}=\frac{2\pi}{T}

or a_{n}=1/T

So, the spectrum is also a series of equally spaced spikes, with frequency spacing

\omega-{0}=\frac{2\pi}{T}. Rewriting this time domain function and substituting

a_{n}=1/T in Equation I gives for this transform pair of equally spaced spikes

f(t)=\sum_{-\infty}^{\infty}\delta(t-nT) Eqn VIIa

F(\omega)=\frac{2\pi}{T}\sum_{n=-\infty}^{\infty}\delta(\omega -n \omega_{0}) Eqn VIIb

Either member of this transfom pair, shown in Figure 4, is called a sampling function because multiplication (in either domain) with a continuous function just produces equally spaced samples of that function. Notice again the reciprocal relationship  between time spacing T and frequency spacing \omega_{0} of this pair T\omega_{0}=2\pi. The sampling function, like the Gaussian, is one of those rare functions that is its own transform, that is, the functional dependence is the same in both domains.

In the course of these blogs, we have taken or have assumed to taken a circuitous route via the continuous time Fourier series to introduce the sampling function because it seems like the easiest approach. Indeed, the computation of the spectrum of the Equation VIIa, using the continuous Fourier integral formulation is impossible since all the conditions for the existence of the Fourier integral are violated. The sampling function with its infinite number of infinite discontinuities and its nonconvergent Fourier integral is the most pathological function that we will need. Yet, in the next blog it will prove most easy to manipulate and useful in understanding the sampling of signals.

More later,

Nalin Pithwa

 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s